Поиск нетривиальных следствий и допущений

Относительно любой нейтральной в логическом отношении форму­лы каноническими являются два вопроса: что из нее следует с необхо­димостью и какие допущения являются достаточными для ее истиннос­ти.

Среди всех логических следствий особый интерес представляют сильные, а среди всех допущений - слабые. Те и другие можно назвать нетривиальными. Сильные следствия поглощают все слабые. Значит, зная сильные, мы всегда знаем слабые, но не наоборот. Слабые допущения ин­тересны тем, что указывают минимальные условия, при которых истинна рассматриваемая формула. Поиск сильных допущений неизбежно приво­дит к парадоксу. Так как из лжи следует все что угодно, то ложь должна быть признана единственным допущением любого знания.

дует добавить также требование, чтобы сильное следствие не совпадало с посылкой исходной формулы.

Логическое следствие формулы нетривиально, если оно не поглощается никаким другим ее следствием и не эквивалентно какой-нибудь ее посылке (под­формуле)

Формуласледует как из допущения А, так и из допущения (А

& В). Но из этих допущений последнее более слабое - из (А&В) следует А, но обратное неверно. Следовательно, А - нетривиальное допущение. Ведь очевидно, что формулу всегда легче доказать на основании более сильного допущения, чем более слабого. Следует также добавить, что нетривиальная посылка не должна совпадать с заключением исходной формулы.

Допущение формулы нетривиально, если оно не поглощает никакие другие ее допущения и не экви­валентно самой формуле

Частным случаем задачи поиска нетривиальных допущений является восстановление пропущенных посылок.

Дерево формулы, построенное согласно правилам П1 - П14, позво­ляет эффективно находить нетривиальные следствия и допущения логи­чески нейтральной формулы.

Допустим, построено дерево исследуемой формулы. Ее необходи­мым следствием будет дизъюнкция любых ее конъюнктов, по одному из каждой ветви. Из них нетривиальными будут те, которые не поглоща­ются никакими другими, и те, которые не совпадают с посылками. До­пущением формулы будет конъюнкция формул, эквивалентная любой ее полной (от вершины до основания) ветви. Из них нетривиальными будут те, которые не поглощают никакие другие, и те, которые не совпадают со всей формулой.

Читая дерево сверху вниз, обнаруживаем все необходимые следствия формулы:Ни одно из них не поглощает другое. Значит, они

оба нетривиальны.

Читая ветви дерева слева направо, находим все допущения формулы, в случае истинности которых она необходимо истинна:) или

Ни одно их них не поглощает другое. Следовательно, они оба нетривиальны.

Чтение дерева формулы по горизонтали (все комбинации по одному нетривиальны, так как ни одно из них не поглощает другие.

Следующая серия задач на поиск необходимых следствий заимство­вана из книг Р.М. Смаллиана «Как же называется эта книга?» (М., 1981), «Принцесса или тигр?» (М., 1985) и «Алиса в стране смекалки» (М., 1987).

Пример 1. Найти нетривиальное следствие.

Из троих (А, В и С) один рыцарь (всегда говорит правду), один лжец (всегда лжет) и один нормальный человек (иногда говорит правду, иногда ложь). Кто кем является, если А утверждает: «Я - нормальный человек»; В его поддерживает; С называет себя ненормальным.

Пусть А_р обозначает, что А - рыцарь, А_Н - что А - нормальный чело­век, А_Л - что А - лжец. Для остальных участников индексация такая же.

Утверждение А эквивалентно дизъюнкции (А_Нѵ А_Л), так как рыцарь не может назвать себя нормальным человеком. Утверждение В эквива­лентно дизъюнкции (B_pѵ В_Н), так как в противном случае, т.е. когда В - лжец, А должен быть рыцарем, что невозможно. Утверждение С эквива­лентно констатации истинности С_р, так как лжец не мог назвать себя не­нормальным человеком. Учитывая, что только один из троих может быть

рыцарем, лжецом или нормальным человеком, получаем следующую со-

Пример 2. Найти нетривиальное следствие

Любой, кто желает жениться на принцессе, должен угадать, в какой комнате она находится. Имеется две комнаты, в каждой из которых мо­жет находиться либо принцесса, либо тигр. Это означает, что правильный выбор гарантирует свадьбу, неправильный - смерть. На двери каждой комнаты висит табличка. На обеих табличках написано: «В обеих комна­тах находятся принцессы». Если в первой комнате принцесса, то надпись истинная, если же тигр, то ложная. Если во второй комнате принцесса, то надпись ложная, если же тигр, то истинная.

В какой из комнат (первой или второй) принцесса, а в какой тигр, учитывая, что в одной из комнат обязательно находится принцесса, а в другой тигр?

Нетривиальные следствия: (П₂& Т₁), т.е.

Пример 3. Найти нетривиальное следствие.

Королева Пик (КР) думает, что Король Пик (К) думает, что она не в своем уме. Кто из них в здравом уме, а кто нет (находящиеся не в своем уме обо всем судят превратно)? Допустим, отсутствие знака отрицания перед буквами КР или К обозначает находящегося не в своем уме.

Сначала формализуем, что думает Король Пик:

Теперь формализуем, что думает Королева Пик:

Дерево формулы: К.

Нетривиальное следствие: Король Пик не в своем уме.

Пример 4. Найти нетривиальное допущение.

Командир осажденной крепости послал три следующих сообщения.

1. «Если нам удастся получить продовольствие, то нам не будет угро­жать смерть от голода».

2. «Если нам не удастся получить продовольствие, то или нам будет угрожать смерть от голода, или мы попытаемся прорвать кольцо окруже­ния».

3. «Если нам будет угрожать смерть от голода, то мы попытаемся прорвать кольцо окружения»².

Можно ли сформулировать сообщение, эквивалентное трем указан­ным, но более простое в логическом смысле? Ответить на этот вопрос означает найти более простые допущения, которым были эквивалентны все три сообщения.

²Калбертсон Дж. Т. Математика и логика цифровых устройств. М., 1965. С. 214.

Дерево формулы (после упрощения):

Нетривиальные допущения: (B&A)или (B&C),т.е. все три сооб­щения истинны, если истинно допущение «Нам удастся получить про­довольствие, и нам не будет угрожать смерть от голода» или допущение «Нам не будет угрожать смерть от голода, и мы попытаемся прорвать кольцо окружения».

Пример 5. Найти нетривиальное допущение.

Путешественник попал в плен к жестоким туземцам и был поставлен перед дилеммой: умереть от яда или сгореть заживо. Чтобы сделать вы­бор, путешественник должен произнести только одну фразу - если при этом он скажет правду, его отравят, а если солжет - сожгут заживо. Какую фразу должен произнести путешественник, чтобы избежать смерти?

Это означает, что если путешественник произнесет «Меня отравят», то независимо от того, говорит ли он правду или ложь, ему не избежать смерти: если он скажет правду, его отравят, если солжет - сожгут заживо. Следовательно, чтобы гарантированно избежать смерти, ему следует ска­

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

6.9.