Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

1.4. Введение в логику высказываний

Табличный способ доказательства

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

Введем обозначения для высказываний:

А = Кассир сказала правду,
В = Водитель находился в комнате отдыха,
С = Комната отдыха находится вблизи склада,
D = Водитель слышал выстрелы,
Е = Водитель сказал правду.

Посылки следователя:

Если кассир сказала правду, то водитель находился в комнате отдыха —

Р₁ = А → В.

Если водитель находился в комнате отдыха, то он должен был слышать все, что делается на складе —

Р₂ = В → С.

Если он имел возможность слышать, что делается на складе, то он слышал и выстрелы —

Р₃ = С → D.

Если верить водителю, то он не слышал выстрелов —

Р₄ = Е → D.

Заключение следователя:

Водитель обманывает при условии, что кассир говорит правду —

С₁ = А → Е.

Кассир и водитель одновременно говорят правду —

С₂ = А ∧ Е.

Формальная запись легенды:

А → В, В → С, С → D, Е → D ⇒  С₁.

Доказать истинность следствия С₁ аксиоматическим методом не составит труда. Для этого нужно воспользоваться тождеством:

Е → D = D → Е,

и затем трижды применить закон транзитивности. Заключение С₂ ошибочно, так как

А → Е ⇒  А ∧ Е,

что означает

А ∨ Е ⇒  А ∧ Е или А ∧ Е ⇒  А ∧ Е,

а это противоречит аксиоме порядка.

Составим таблицу истинности (табл. 1.22), в которой под Р понимается обобщенная причина, т.е. конъюнкция всех Р_i.

Таблица 1.22

Клауза считается истинной, если единицы следствия (С) накрывают все единицы обобщенной причины (Р), т.е. единицы обобщенной причины образуют подмножество единиц следствия. Это требование выполняется для следствия С₁, так как

P = {0, 8,12, 14, 15, 16} ⊂ {0, ... 16, ...} = С₁,

но не для С₂ (С₁ = С₂), так как

P = {0, 8,12, 14, 15, 16} ⊄ {18, 20, 22, 24, 26, 28, 30} = С₂.

С помощью скорректированной табл. 1.22 нетрудно установить справедливость тавтологии, составленной из этих же посылок, —

1 ⇒  Р₁ ; Р₂; Р₃ ; Р₄ ; С₁,

и противоречия —

Р₁, Р₂, Р₃, Р₄, С₁ ⇒ 0,

а также любых других клауз, полученных из первоначальной путем эквивалентных преобразований, например:

Р₂, Р₄, ⇒  Р₁ ; С₁ ; Р₃.

Если С₁ заменить на С₂, то во всех указанных случаях условие причинно-следственного отношения нарушится и клаузы обратятся в ложные метавысказывания.

Заключения С₁ и С₂, настолько очевидны, что никакой следователь в этом случае не стал бы прибегать к таблицам истинности. Но трудно найти такого следователя, который только путем одних рассуждений смог бы правильно выбрать из двух нижепредствленных заключений истинное:

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

С₃ = (A ∨ D) → (E ∧ B ∧ C).

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

С₄ = (A ∨ B) → (E ∧ D ∧ C).

Единичные наборы для заключений С₃ и С₄ тоже приведены в табл. 1. 22. Для заключения С₃ в строках 8 и 12 стоят нули, следовательно, условие причинно-следственного отношения не выполняется, и поэтому С₃ — ложное заключение. Для заключения С₄ все его единицы накрывают единицы обобщенной посылки Р. Следовательно, С₄ — истинное заключение:

P = {0, 8, 12, 14,15, 16} ⊄ {0, 2, 4, 6, 7, 14, 15, 16, 18, 20, 22} = С₃,
P = {0, 8, 12, 14,15, 16} ⊂ {0, 4, 8, 12, 13, 14, 15, 16, 20, 24, 28} = С₄.

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

Вообще, опытный логик прежде всего должен построить все совместимые ряды событий. В нашем случае таких рядов 6 (они соответствуют 0, 8, 12, 14, 15, 16 строкам табл. 1. 22). Их объединение даст условия выполнения причинно-следственного отношения:

A, B, C, D, E ; A, B, C, D, E ; A, B, C, D, E ;
A, B, C, D, E ; A, B, C, D, E ; A, B, C, D, E

Перед нами СДНФ, отвечающая нашей обобщенной причине Р. Всевозможные покрытия шести конституент дают множество истинных следствий. Так, заключения —

С₁ = А; Е , С₄ = (А, В) ; (C, D, E),

покрывают все шесть конституент; они — истинные. Что касается двух других заключений —

С₂ = А, Е , С₃ = (А, D) ; (C, В, E),

то они не покрывают все или отдельные конституенты, значит являются ложными следствиями.

Не надо знать комбинаторный анализ, чтобы ощутить все многообразие возможных покрытий, т.е. истинных следствий из заданных причин. Однако опытный следователь должен уметь определять три вещи — минимальную нормальную форму (МНФ), минимальное и трансверсальное покрытия.

Ранее было рассмотрено нахождение точных МНФ по известной СДНФ. Минимизируя одним из известных способов нашу СДНФ, получим следующую МНФ:

A, B, C, D ;   A, B, D, E ;   B, C, D, E ;

Минимальное покрытие — это покрытие с наименьшим числом термов. Мы его уже знаем — это заключение С₁. В него входят два решающих высказывания, связанные с правдивостью кассира (А) и правдивостью водителя (Е). Все остальные утверждения (B, C, D) являются второстепенными и могут выступать в результирующем заключении совместно с А и Е.

Трансверсальное покрытие должно включать все имеющиеся термы. Для нашего примера существуют четыре таких покрытия:

A; B, C, D, E          A, B; C, D, E
A, B, C; D, E         A, B, C, D; E.

Как видим, среди выписанных покрытий находится и заключение С₄, которое мы уже проинтерпретировали в импликативной форме. Интерпретация заключений через ДНФ может показаться более предпочтительной. Возьмем для примера заключение

С₅ = A, B, C; D, E.

Оно предполагает три исхода истинного значения при совместном действии всех пяти факторов:

A, B, C = 1         D, E = 0,
A, B, C = 0         D, E = 1,
A, B, C = 1         D, E = 1.

Именно трансверсальные покрытия дают наиболее полную картину возможных следствий из сформулированных посылок.