Глава IV. Занимательные задачи по логике

1. Два юных синоптика трижды в день (утром, днём и вечером) одновременно ведут наблюдения за погодой. Если хотя бы в одно из наблюдений шёл дождь, первый записывает в дневник наблюдений “–“, а в противном случае – “+”. Второй же ставит “+”, если хотя бы во время одного наблюдения дождя не было, во всех остальных случаях он пишет “–“. Какие из возможных четырёх комбинаций “+ +”, “+ –“, “– +”, “– –“ могут встретиться в их дневнике?

2. К юным синоптикам из задачи 2 присоединился третий, который ведёт наблюдения одновременно с ними и пишет в дневнике “–“, если по крайней мере во время двух наблюдений из трёх шёл дождь, и “+” – в противном случае. Какие из возможных восьми комбинаций плюсов и минусов теперь могут встретиться в дневнике наблюдений?

3. а) Среди математиков каждый пятый – шахматист, а среди шахматистов каждый двадцатый является математиком. Кого больше – математиков или шахматистов, и во сколько раз?

б) Является ли старейший шахматист среди математиков старейшим математиком среди шахматистов?

в) Является ли лучший шахматист среди математиков лучшим математиком среди шахматистов?

4. Докажите, что a > 0, b > 0, c > 0, если .

5. Какие знаки могут иметь числа a, b, c Î R, если в условии предыдущей задачи заменить все знаки “>” на “<”?

6. а) Четыреста человек построены в виде прямоугольника, в котором сорок шеренг и десять колонн. В каждой шеренге выбрали самого высокого, а затем – из отобранных сорока человек – самого низкого. На следующий день повторили построение и выбрали самого низкого в каждой колонне, а затем из десяти отобранных – самого высокого. В какой из дней будет в итоге выбран более высокий человек?

б) Изменится ли ответ, если исходное построение осуществить в виде квадрата?

в) А если построить людей в виде буквы “Г”? Зависит ли ответ от размеров этой буквы?

7. Навстречу Вам идут пять человек. Докажите, что среди них обязательно есть либо три Ваших знакомых, либо три незнакомца.

8. Докажите, что в компании из шести человек всегда найдутся либо трое попарно знакомых, либо трое попарно незнакомых друг с другом людей.

9. К полёту на Марс готовятся 7000 космонавтов. Известно, что среди любых четырёх из них всегда можно выбрать трёх, составляющих слаженный экипаж. Докажите, что найдутся пять космонавтов, любые три из которых составляют слаженный экипаж.

10. Найдите все такие точки на Земле, выйдя из которых можно вернуться в эту же точку, пройдя вначале 100 км по меридиану на север, затем – 100 км по широте на восток, и наконец – 100 км по меридиану на юг.

11. Имеется двадцать одинаковых на вид монет, из которых семнадцать весят по 10г, одна – 9,9 г. и две – по 9,8 г. Можно ли за два взвешивания на чашечных весах без гирь выявить хотя бы одну десятиграммовую монету?

12. На одном из затерянных в океане островков чудом сохранилось племя людей, говорящих только правду. Однако цивилизация принесла на этот остров болезнь, заразившись которой человек начинает всегда лгать. Перед Вами три аборигена – А, В и С. Определите, кто из них болен, а кто здоров в следующих ситуациях (если решений несколько, перечислите все возможности): а) Вы задали А вопрос: “Сколько здоровых среди вас?”. Он ответил, но очень неразборчиво. Зато В сказал: “Он говорит, что среди нас один здоров”, а С закричал: “Не верьте ему! Он лжёт!”; б) А говорит: “Мы все больны”, а В возражает: “Среди нас один здоров”; в) А говорит: “Мы все больны”, а В возражает: “Среди нас один болен”. Сколько вопросов Вам понадобится задать, чтобы безошибочно определить состоянье здоровья каждого?

13. На островке из предыдущей задачи поселились колонисты, имеющие иммунитет к болезни, поскольку и без того то лгут, то говорят правду. Они составили табель о рангах и мнят себя особами высшего ранга, здоровых аборигенов считают людьми среднего ранга, а больных аборигенов – людьми низшего ранга. Перед Вами три жителя острова – А, В и С, среди которых присутствуют люди всех рангов. Определите, кто из них болен, кто здоров и кто колонист в следующих ситуациях (если решений несколько, перечислите все возможности): а) А сказал: “Мой ранг выше, чем у В и С ”, В добавил: “Мой ранг ниже, чем у С, но выше, чем у А ”, а С промолвил: “Я – особа низшего ранга”; б) А говорит: “Мы все – особы высшего ранга”, В с нимне согласен: “Нет, мы все люди низшего ранга”, а С противоречит обоим: “По крайней мере я – человек среднего ранга”; в) А говорит: “ В по рангу выше, чем С ”, В добавляет: “Ранг С выше, чем ранг А ”, а С окончательно запутывает ситуацию: “Зато ранг А выше, чем ранг В ”.

14. В одной из трёх шкатулок лежит приз. Постарайтесь угадать шкатулку с призом в следующих ситуациях:

а) На шкатулках выгравированы надписи: I – “Приз в этой шкатулке”, II – “Здесь приза нет”, III – “Приз не в первой шкатулке” и известно, что из трёх надписей по крайней мере одна истинна;

б) На шкатулках выгравированы надписи: I – “Приз не во II-й шкатулке”, II – “Здесь приза нет”, III – “Приз в этой шкатулке” и известно, что из трёх надписей по крайней мере одна истинна и одна ложна;

в) На шкатулках выгравированы по две надписи: I – “Приз не в этой шкатулке” и “Приз – поездка в Венецию”, II – “Приз не в I-й шкатулке” и “Приз – поездка во Флоренцию”, III – “Здесь приза нет” и “Приз во II-й шкатулке”. Кроме того известно, что на каждой шкатулке ложна не более чем одна надпись;

г) На шкатулках выгравированы по две надписи: I – “Приз не в этой шкатулке” и “Приз во второй шкатулке”, II – “Приз не в I-й шкатулке” и “Приз в III-й шкатулке”, III – “Здесь приза нет” и “Приз в I-й шкатулке”. Кроме того известно, что на одной из шкатулок обе надписи истинны, на одной – обе ложны и на одной – одна истинна, а другая ложна.

15. Вам предлагают либо стать мужем принцессы-миллиардерши (женою принца-миллиардера), либо получить 1 (один) рубль. Для осуществления первого достаточно угадать в какой из двух шкатулок лежит её (его) портрет и в случае неудачи расстаться с жизнью, второе же можно получить даром. Что Вы выберете в следующих ситуациях: а) На шкатулках выгравированы надписи: I – “Здесь портрета нет», II – “Ровно одна из двух выгравированных надписей истинна”; б) На шкатулках выгравированы надписи: I – “Портрет здесь”, II – “Эта шкатулка пуста” и “Не более чем одна из двух прочитанных Вами надписей ложна”

16. Трём логикам – А, В и С, обладающим абсолютными логическими способностями и умеющим решить любую логическую задачу, имеющую решение, показали семь карточек: две красных, две жёлтых и три зелёных. Затем им завязали глаза и наклеили каждому на лоб по карточке, спрятав оставшиеся четыре в коробку. После этого повязки сняли и спросили у А: “Можете ли Вы сказать, карточки какого из трёх цветов на Вас точно нет?”. А ответил: “Нет”. Тот же вопрос был задан В, и он ответил так же. Может ли С сказать какого цвета карточки у каждого логика на лбу? А Вы можете это сделать?

17. В некоторой компании из n ³ 2 человек все знакомые между собой люди пожали друг другу руки. Докажите, что количество всех рукопожатий равно удвоенному числу пар знакомых людей. Докажите, что количество людей, совершивших нечётное число рукопожатий чётно. Докажите, что в компании есть два человека, имеющие одинаковое число знакомых.

 

18. В условиях предыдущей задачи докажите, что а) если каждый из n человек имеет не менее (n–1) / 2 знакомых, то любые два человека связаны цепочкой знакомств (т.е. для любых двух членов a и b компании найдётся такая цепочка а₁, …, а_k членов компании, что a знаком с a₁, a_i+1 – с a_i (1 £ i < k) и a_k знаком с b); б) заключение пункта а) останется в силе, если компанию покинет любое число людей (меньшее n – 1).

 

 

Приложение 1

Теорема (об основных законах логики). Для любых формул A, B, C следующие формулы являются законами логики:

(1) A «A закон тождества	(2) (A Ù A) «A, (A Ú A) «A законы идемпотентности	(3) (A Ù B) «(B Ù A), (A Ú B) «(B Ú A) законы коммутативности
(4) ((A Ù B) Ù C) «(A Ù (B Ù C)), ((A Ú B) Ú C) «(A Ú (B Ú C)) законы ассоциативности	(5) ((A Ú B) Ù C) «((A Ù С) Ú (B Ù C)), ((A Ù B) Ú C) «((A Ú С) Ù (B Ú C)) законы дистрибутивности	(6) , законы де Моргана
(7) «A закон двойного отрицания	(8) (A ® B) «( ® ) закон контрапозиции	(9) (A «B) «( «) закон противоположности
(10) (A Ú (A Ù B)) «A закон поглощения	(11) (A Ù (A Ú B)) «A закон ограничения	(12) (A ® (B ® C)) «(B ® (A ® C)) закон перестановки посылок
(13) (A Ù B) Ú (A Ù ) «A, (A Ú B) Ù (A Ú ) «А законы склеивания по B	(14) (A Ú ( Ù B)) «(A Ú B) (A Ù ( Ú B)) «(A Ù B) законы удаления	(15) ((A ® B) Ù (B ® C)) ® (A ® C) закон силлогизма
(16) (A Ù B) ® A, (A Ù B) ® B законы удаления конъюнкции	(17) A ® (A Ú B), B ® (A Ú B) законы введения дизъюнкции	(18) ( ® B) Ù ( ® ) «A закон рассуждений от противного
(19) (A Ú B) Ù (A ® C) Ù (B ® C) ® C закон разбора случаев	(20) (A Ú B) Ù (C Ú ) ® (A Ú C), общий закон резолюций	(21) B Ù (C Ú ) ® C частный закон резолюций
законы, выражающие одни логические связки через другие: (1) (A ® B) «( Ú B), (A ® B) «, (2) (A «B) «(A ® B) Ù (B ® A), (A «B) «, (A «B) «, (A «B) «(A Ù B) Ú ( Ù ), «(A Ù ) Ú ( Ù B), (3) (A Ù B) «, (A Ù B) «, A Ù «, (4) (A Ú B) «( ® B), (A Ú B) «
законы действий с тавтологиями и противоречиями: (1) (А Ù 1) «А, (A Ú 1) «1, (2) (А Ù 0) «0, (A Ú 0) «A, (3) (A Ù ) «0, (A Ú ) «1, (4) (A ® A) «1, (0 ® A) «1, (1 ® A) «A, (A ® 0) «, (A ® 1) «1, (5) (A «A) «1, (A «) «0, (A «1) «A, (A «0) «, (6) «0, «1.

Приложение 2

Теорема (об основных равносильностях). Для любых формул A, B, C справедливы следующие равносильности:

(1) A º A закон тождества	(2) (A Ù A) º A, (A Ú A) º A законы идемпотентности	(3) (A Ù B) º (B Ù A), (A Ú B) º (B Ú A) законы коммутативности
(4) ((A Ù B) Ù C) º (A Ù (B Ù C)), ((A Ú B) Ú C) º (A Ú (B Ú C)) законы ассоциативности	(5) ((A Ú B) Ù C) º ((A Ù С) Ú (B Ù C)), ((A Ù B) Ú C) º ((A Ú С) Ù (B Ú C)) законы дистрибутивности	(6) законы де Моргана
(7) º A закон двойного отрицания	(8) (A ® B) º ( ® ) закон контрапозиции	(9) (A «B) º ( «) закон противоположности
(10) (A Ú (A Ù B)) º A закон поглощения	(11) (A Ù (A Ú B)) º A закон ограничения	(12) (A ® (B ® C)) º (B ® (A ® C)) закон перестановки посылок
(13) (A Ù B) Ú (A Ù ) º A, (A Ú B) Ù (A Ú ) º A законы склеивания по А	(14) (A Ú ( Ù B)) º (A Ú B) (A Ù ( Ú B)) º (A Ù B) законы удаления	(18) (( ® B) Ù ( ® )) º A закон рассуждений от противного
законы, выражающие одни логические связки через другие: (1) (A ® B) º ( Ú B), (A ® B) º , (2) (A «B) º (A ® B) Ù (B ® A), (A «B) º , (A «B) º , (A «B) º (A Ù B) Ú ( Ù ), º (A Ù ) Ú ( Ù B), (3) (A Ù B) º , (A Ù B) º , A Ù º , (4) (A Ú B) º ( ® B), (A Ú B) º
законы действий с тавтологиями и противоречиями: (1) (А Ù 1) º А, (A Ú 1) º 1, (2) (А Ù 0) º 0, (A Ú 0) º A, (3) (A Ù ) º 0, (A Ú ) º 1, (4) (A ® A) º 1, (0 ® A) º 1, (1 ® A) º A, (A ® 0) º , (A ® 1) º 1, (5) (A «A) º 1, (A «) º 0, (A «1) º A, (A «0) º , (6) º 0, º 1.

Приложение 3

Теорема (об основных правилах логического вывода). Справедливы следующие основные правила логического вывода:

modus ponens	перестановки посылок	удаления конъюнкции	расширенное силлогизма
extra modus ponens	объединения посылок	введения конъюнкции	modus tollens
дедукции	разделения посылок	введения дизъюнкции	опровержения
расширения посылок	контрапозиции	силлогизма	резолюций

Приложение 4