Задачи повышенной трудности

Дата добавления: 2014-11-24 | Просмотров: 1824

1. Пусть в формуле F встречаются только операции отрицания, конъюнкции и дизъюнкции. Обозначим через F* формулу, которая получается из F заменой Ú на Ù и Ù на Ú, атомов на их отрицание, а отрицания атомов на сами атомы. Докажите, что F « F* - тавтология.

2. Пусть F – формула, в которой выделено некоторое вхождение формулы F₁, пусть F* - формула, которая получается из F заменой этого вхождения F₁на F₂, причем F₁º F₂. Докажите, что F « F* - тавтология.

3. Было совершено ограбление. Трое бродяг Луи, Франсуа и Этьен дали инспектору Мегрэ следующие показания:

Л.: Чтобы обвинить меня, достаточно доказать, что Франсуа участвует в ограблении только тогда, когда в нем участвует Этьен, но я не виновен.

Ф.: Если Луи невиновен, то, чтобы обвинить меня достаточно признать Этьена тоже невиновным. Но Этьен виновен тогда и только тогда, когда виновен Луи. А если Этьен виновен, то я невиновен.

Э.: Виновен либо я, либо Франсуа и Луи.

Мегре знал, что Этьен всегда лжет, а Луи и Франсуа говорят правду. Кто причастен к ограблению?

4. В школьном шахматном турнире участвовал Иванов, Петров и Сидоров. Отца одного из них попросили быть судьей. Перед началом турнира его участники высказали следующие предположения:

И.: Не может быть, чтобы победили Петров и Сидоров вместе. Не может быть также, чтобы победил либо Петров, либо Сидоров. Значит, не смогу быть победителем и я.

П.: Если Иванов проиграет, то Петров будет победителем только тогда, когда выяснится, что Сидоров проиграл. Если Иванов проиграет, то проиграет и Сидоров. А я выиграть не смогу.

С.: Не может быть, чтобы проиграли и Иванов, и Петров, а я бы победил.

После окончания турнира выяснилось, что подтвердилось только высказывание сына судьи. Кто был победителем турнира? Как фамилия судьи?

Тема 2. Теоремы. Необходимые и достаточные условия.