§ 2. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ

Основные определения.

Пусть — формулы логики высказываний.

ОПРЕДЕЛЕНИЕ. Формула В называется логическим следствием формул если при любом выборе истинностных значений атомов, входящих в формулы , формула В получает значение «истина» всякий раз, когда каждая из формул получает значение «истина».

Запись

означает, что формула В — логическое следствие формул (формулы логически влекут формулу В).

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

Пример. что видно из таблицы:

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

ОПРЕДЕЛЕНИЕ. Формулы А и В называются равносильными (логически эквивалентными), если при любом выборе истинностных значений атомов, входящих в формулы А и В принимают одинаковые истинностные значения.

Запись означает, что формулы А и В равносильны.

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

Формула А равносильна В тогда и только тогда, когда

ТЕОРЕМА 2.1. Формулы А и В равносильны тогда и только тогда, когда формула является тавтологией.

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

ТЕОРЕМА 2.2. тогда и только тогда, когда тогда и только тогда, когда

Доказательство, (а) Пусть Импликация имеет истинностное значение A, когда А получает значение И и одновременно В получает значение A. Однако в силу условия такого распределения истинностных значений атомов, входящих в А и В, не существует. Следовательно, формула всегда получает значение И, т. е.

Предположим теперь, что Рассмотрим произвольное распределение истинностных значений атомов, входящих в A и В, при котором А имеет значение И. Так как по предположению получает значение И при этом распределении, то и В получает значение И при этом распределении. Таким образом,

Из определения конъюнкции следует, что тогда и только тогда, когда . Кроме того, в силу (а)

Следовательно, тогда и только тогда, когда

Пример. так как формула является тавтологией.

ТЕОРЕМА тогда и только тогда, когда

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

Предположим теперь, что и докажем, что Допустим, что существует такое распределение истинностных значений атомов, входящих в формулы , при котором формулы принимают значение И, а формулы С — значение A.

При этом же распределении истинностных значений атомов формулы приняли бы значение И, а формула В С — значение A, что противоречило бы предположению. Следовательно, такого распределения истинностных значений атомов не существует. Таким образом, если , то ?

СЛЕДСТВИЕ 2.4. тогда и только тогда, когда более общем виде: тогда и только тогда, когда

Для доказательства достаточно несколько раз применить теорему 2.3.

Из теоремы 2.3 следует, что тавтологическим эквиваленциям, приведенным в теореме 1.3, отвечают следующие равносильности (логические эквивалентности):