4.9. Логические задачи

 

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

Пример 4.6. (Задача Кислера). Иванов, Петров и Сидоров подозреваются в совершении преступления. В ходе следствия они дали следующие показания:

Иванов: Петров виновен, а Сидоров нет.

Петров: Если Иванов виновен, то виновен и Сидоров. (Они всегда действуют сообща).

Сидоров: Я невиновен, но хотя бы один из них двоих виновен.

         Необходимо установить:

а) Совместимы ли показания всех троих подозреваемых, т.е. могут ли они быть одновременно истинны?

б) Предполагая, что показания всех обвиняемых истинны, укажите, кто виновен, а кто нет?

в)  Если невиновный говорит истину, а виновный лжет, то кто невиновен, а кто виновен?

г)  Если все трое невиновны, то кто лжесвидетельствует?

Решение. Обозначим через I высказывание «Виноват Иванов», P — «Виноват Петров», S — «Виноват Сидоров». Именно эти высказывания являются простыми, исходными. Тогда показания подозреваемых описываются следующими формулами алгебры высказываний:

Иванов:     P Ù .

Петров:     I ® S.

Сидоров:   Ù (I Ú P) .

Построим таблицу истинности, поместив в ее первые три столбца значения исходных высказываний I, P, S , а в следующие столбцы значения высказываний подозреваемых и вспомогательных формул.

			Вспомогательные формулы		Утверждения			Пункты задачи
					Иванова:	Петрова:	Сидорова:
I	P	S		I Ú P	P Ù	I ® S	Ù (I Ú P)
1	1	1	0	1	0	1	0
1	1	0	1	1	1	0	1
1	0	1	0	1	0	1	0	в)
1	0	0	1	1	0	0	1
0	1	1	0	1	0	1	0
0	1	0	1	1	1	1	1	а), б)
0	0	1	0	0	0	1	0
0	0	0	1	0	0	1	0	г)

Теперь ответим на вопросы задачи.

а) Показания Иванова, Петрова и Сидорова одновременно истинны, т.е. имеют значение 1, в шестой строке таблицы. Таким образом, показания всех подозреваемых совместны.

б) Если показания всех обвиняемых истинны ( пункт а) – шестая строка таблицы), то в этом случае P=1, а I=0 и S=0, т.е. виновен Петров, а Иванов и Сидоров – невиновны.

в) Случай, когда невиновный говорит истину, а виновный лжет, описывается третьей строкой. При этом виновны Иванов и Сидоров (I=1, S=1), а Петров – нет (P=0).

г) И, наконец, если все подозреваемые невиновны P=0, I=0, S=0 (восьмая строка),  то лишь Петров говорит правду, а Иванов и Сидоров по какой-то причине лжесвидетельствуют.

Пример 4.7. Один из четырех задержанных (Михайлов, Костин, Викторов, Тимофеев) подозревается в краже. На вопрос следователя «Кто совершил кражу?» были получены такие ответы:

1)  «Это сделал или Михайлов, или Костин»;

2)  «Это сделал или Викторов, или Костин»;

3)  «Это не могли сделать ни Тимофеев, ни Михайлов»;

4)  «Это сделал или Викторов, или Михайлов».

Можно ли по этим данным установить, кто виновен в совершении преступления, если известно, что из четырех высказываний три истинны?

Решение. Обозначим высказывание «Кражу совершил Михайлов» через М, «Кражу совершил Викторов» через В, «Кражу совершил Костин» через К, «Кражу совершил Тимофеев» через Т. Тогда ответы на вопрос следователя о том, кто совершил кражу, описываются следующими формулами алгебры высказываний:

1) М Ú К;

2) B Ú K;

3) Ù;

4)  В Ú M.

В первые четыре столбца таблицы поместим значения высказываний М, В, К и Т, в столбцы с 5-го по 10-й поместим значения вспомогательных формул и высказываний 1) - 4). Так как виноват только один из четырех задержанных, количество строк в таблице равно 4, причем первые четыре столбца таблицы содержат только по одному значению «истина» (единицу), а остальные — «ложь» (нуль). Значения в столбцах с 5-го по 10-й вычисляем в соответствии с записанными формулами.

						1)	2)	3)	4)
М	В	К	Т			М Ú К	B Ú K	Ù	В Ú M
1	0	0	0	1	0	1	0	0	1
0	1	0	0	1	1	0	1	1	1
0	0	1	0	1	1	1	1	1	0
0	0	0	1	0	1	0	0	0	0

 

Из таблицы видно, что возможны два варианта одновременной истинности трех ответов: из четырех строк таблицы в двух (во 2-й и в 3-й) три из четырех сделанных высказываний истинны и одно ложно. Эти строки соответствуют значениям истинности для высказыва­ний В и К. Следовательно, виноват или Викторов, или Костин, т. е. однозначно ответить на вопрос «Кто совершил кражу?» при заданных условиях нельзя.

 

Весьма интересен еще один тип логических задач, в которых одни из участников всегда говорят только правду (в литературе по математической логике их называют «рыцарями»), другие всегда лгут («лжецы»).

Пример 4.8. Известно, что каждый из двух человек a и b является либо рыцарем, либо лжецом. Выясните, кто есть кто, если a утверждает следующее: «По крайней мере, один из нас — лжец».

Решение. Сделаем следующие обозначения: высказывание «a – рыцарь» - А, высказывание «b – рыцарь» - В. Тогда высказывание a: «По крайней мере, один из нас — лжец» - запишется так  Ú .

Составим таблицу истинности, в первых двух столбцах которой разместим всевозможные варианты высказываний А и В, а в других столбцах вычислим соответствующие значения логической формулы  Ú .

 

 

Теперь проанализируем строки таблицы, сравнив роль а (рыцарь или лжец) и значение его высказывания (истинное или ложное). Мы помним, что высказывания рыцаря всегда истинны по определению. В первой строке (А=1) а является рыцарем, но его утверждение ложно – этого не может быть. Следовательно, этот вариант неверен. Третья и четвертая строки также противоречивы. В них а – лжец (А=0), но говорит он правду. Этого также не может быть по определению лжеца. А вот во второй строке противоречий нет. В ней а – рыцарь и его утверждение истинно. Итак, а – рыцарь, а b – лжец.

Для решения задачи можно также в дополнительном столбце таблице истинности рассчитать эквивалентность высказываний А (a является рыцарем) и Ú(высказывание а): А«Ú. Такая эквивалентность должна быть истинной – рыцарь говорит истину, лжец – ложь. Действительно, А«Ú=1 лишь во второй строчке. Именно она и не дает противоречия между ролью а и его высказыванием. Таким образом, А=1 (а – рыцарь), В=0 (b – не рыцарь, т.е. b – лжец).

Говоря о рыцарях и лжецах, следует упомянуть, что никто из них не может сказать, что он является лжецом, т.е. всегда говорит неправду. Действительно, если человек – лжец, то, на сей раз, он сказал правду, а этого не может быть по определению лжеца. А если человек – рыцарь, то данное его высказывание – ложно, чего также не может быть. Это, так называемый, парадокс лжеца. В простейшем варианте он выглядит следующим образом. Человек произносит фразу: «Высказывание, которое я сейчас говорю, ложно» или «Я лгу». Если его высказывание – истинно, то есть он лжет, то на самом деле говорит правду. А если его высказывание – ложно, то значит он должен говорить правду и не говорить ложь.

В средние века была распространена такая формулировка: «Сказанное Платоном – ложно, говорит Сократ. – То, что сказал Сократ, – истина, говорит Платон». При этом выяснить кто из них лжет, а кто говорит правду в рамках логики высказываний невозможно. Парадокс лжеца, открытый еще в IV в. до нашей эры, остается притягательным для изучения до сих пор. Ему посвящена обширная научная литература. Нередко он называется «королем логических парадоксов».

Предыдущая | Главная | Глава 4 | Следующая