§3. Логическое следование и логическая равносильность формул алгебры высказываний

В математике зачастую теоремы имеют вид импликации . Для доказательства их истинности достаточно из истинности высказывания A логическими рассуждениями вывести истинность высказывания B. В этом случае говорят, что из A логически следует B и пишут . При этом высказывание B называют также логическим следствием высказывания A . Аналогичное понятие можно ввести для формул алгебры высказываний.

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

Практически вопрос о том, является ли формула G логическим следствием формулы F , решается с помощью таблиц истинности. При этом надо составить всевозможные наборы истинностных значений для высказывательных переменных, вычислить для них соответствующие значения формул F и G и сравнивать только те значения этих формул, при которых формула F принимает значение 1. Если из структуры формулы F легко усматриваются те наборы истинностных значений для переменных, при которых она принимает значение 1, то можно ограничиться составлением фрагмента таблицы истинности.

Пример 1. Доказать, что .

Легко видеть, что первая формула принимает значение 1 для следующих наборов истинностных значений переменных: 1,1,1; 1,0,1; 0,1,1. Требуемое логическое следование вытекает из фрагмента таблицы истинности.

Таблица 1.

X	Y	Z
1 1 0	1 0 1	1 1 1	1 1 1	1 1 1

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

Т е о р е м а 1 (о свойствах логического следования для высказывательных формул). Для любых формул , и справедливы следующие свойства:

. , т.е. отношение логического следования рефлексивно;

. если и , то , т.е. отношение логического следования транзитивно;

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

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

Полезно иметь в виду следующее утверждение:

Т е о р е м а 2 (признак логического следования для высказывательных формул). Из формулы логически следует формула тогда и только тогда, когда импликация является тавтологией.

□ Пусть . Если для какого-нибудь набора истинностных значений имеет место , то . Поэтому . Если , то . Таким образом, формула является тавтологией.

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

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

Очевидна следующая

Т е о р е м а 3 . Из формул логически следует формула тогда и только тогда, когда из формулы логически следует формула , т.е. тогда и только тогда, когда .

Пример 2. Покажем, что . Ввиду теоремы 3 достаточно доказать, что . Введем обозначения: , и составим таблицу истинности.

Таблица 2.

X	Y
1 1 0 0	1 0 1 0	1 0 1 1	1 0 0 0	1 0 1 0

Как показывает эта таблица, формула принимает значение 1 для единственного набора , . Поскольку , делаем вывод о том, что .

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

Непосредственно из определения логического следования заключаем, что понятие равносильности формул совпадает с понятием логической равносильности: тогда и только тогда, когда . В частности, справедлива

Т е о р е м а 4 . Формула логически равносильна формуле тогда и только тогда, когда эквиваленция является тавтологией.

□ Доказательство вытекает из закона замены эквиваленции (см. равносильность 15 в §2) и теоремы 2.