Тождественно-истинные и тождественно-ложные формулы

До сих пор мы имели дело с формулами, которые при одних логических значениях своих переменных были истинными, а при других значениях — ложными. Но существуют формулы, которые при любых наборах логических значений переменных получают в заключительном столбце таблицы логическое значение «истина». Такие формулы называют тождественно-истинными формулами или логическими тождествами.

Рассмотрим, например, формулу

p ® p

и построим ее таблицу:

Мы видим, что независимо от того, принимает пропозициональная переменная р значение «истина» или «ложь», формула р ® р имеет значение «истина». Так, высказывания Если Ленинград большой, город, то Ленинград большой город; Если сегодня пасмурный день, то сегодня пасмурный день и Если 12 простое число, то 12 простое число — истинны независимо от того истинно или ложно фактически, что Ленинград большой город и сегодня пасмурный день, и является ли действительно 12 простым числом.

Построим теперь для формулы

p Ú ~ p

ее таблицу:

Мы видим, что независимо от того, принимает переменная р значения «истина» или «ложь», формула р Ú ~р имеет значение «истина». Например, высказывания Волга впадает в Каспийское море или Волга не впадает в Каспийское море; 12 делится на 5 без остатка, или неверно, что 12 делится на 5 без остатка — истинны независимо от того, впадает Волга в Каспийское море и делится ли 12 на 5 без остатка.

Каждая тождественно-истинная формула выражает какой-то логический закон. Формула р ® р есть известный логический закон тождества, а формула p Ú ~ р — закон исключенного третьего (закон исключенного среднего).

Рассмотрим еще два примера тождественно-истинных формул. Формула

p ® (q ® р)

имеет таблицу:

а формула

((p ® q) Ù ((q ® r)) ® (p ® r)

(закон гипотетического силлогизма) — таблицу:

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

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

Рассмотрим, например, формулу

p Ù ~p,

которая имеет таблицу:

Так, высказывания Ленинград расположен в дельте Невы, и неверно, что Ленинград расположен в дельте Невы; Этот лист бумаги белый, и неверно, что этот лист бумаги белый; 2 — простое число, и неверно, что 2 — простое число, — ложны независимо от того, где расположен Ленинград, каков цвет данного листа бумаги и считается ли 2 простым числом.

Рассмотрим далее формулы

p «~р и ~p Ù ~(~p Ú q),

которые имеют таблицы:

Например, высказывания Он умеет играть в шахматы, если и только если неверно, что он умеет играть в шахматы, и Неверно, что это число четное, и неверно, что это число не является четным или оно делится на 3, — ложны независимо от того, умеет тот, о ком идет речь, играть в шахматы и делится ли данное число на 2 и на 3.

Ясно, что все тождественно-ложные формулы равносильны друг другу. Отрицание тождественно-истинной формулы есть тождественно-ложная формула, и наоборот. Так, если формулы p Ú ~ p и ~(р Ù ~ р) тождественно-истинны, то формулы ~(p Ú ~ р) и ~~(p Ù ~ р) тождественно-ложны.

Если теперь мы обозначим заглавной буквой «И» формулу, которая тождественно-истинна, а заглавной буквой «Л» формулу, которая тождественно-ложна, то будут иметь место следующие равносильности:

~И равносильно Л; (43)

~ Л равносильно И; (44)

А «И равносильно А; (45)

А «Л равносильно ~ А; (46)

А Ù И равносильно А; (47)

И Ù А равносильно А; (47¢)

А Ù Л равносильно Л; (48)

Л Ù А равносильно Л; (48¢)

А Ú И равносильно И; (49)

И Ú А равносильно И; (49¢)

Л Ú А равносильно А; (50)

Л Ú А равносильно А. (50¢)

Ясно, что если формула А тождественно-истинна (тождественно-ложна), то любая ее таблица с любым перечнем пропозициональных переменных E ₁, Е ₂ ,..., E_n во всех строках заключительного столбца будет иметь значение «истина» («ложь»).

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

Теорема. Если формулыА ® В и В ® С тождественно-истинны, то тождественно-истинна формула А ® С.

Доказательство. Пусть E ₁, Е ₂ ,..., E_n — перечень всех пропозициональных переменных, входящихв А, В и С. Построим таблицы формул А ® В, В ® С и А ® С с данным перечнем переменных. Предположим теперь, что формула А ® С не тождественно-истинна и при некотором наборе логических значений переменных E ₁, Е ₂ ,..., E_n получает в заключительном столбце своей таблицы логическое значение «ложь». Ясно, что при данных значениях переменных формула А истинна, а формула С ложна. Но тогда, если при этом же наборе логических значений переменных формула В истинна, то ложна формула В ® С, а если формула В ложна, то ложна формула А ® В. Одно и другое противоречит условиям теоремы,и, следовательно, формула А ® С тождественно-истинна.

Докажем, наконец, следующую теорему.

Теорема. А равносильно В тогда и только тогда, когда формулаА «В тождественно-истинна.

Доказательство. Пусть А равносильно В. Тогда если при некотором наборе логических значении переменных E ₁, Е ₂ ,..., E_n (где E ₁, Е ₂ ,..., E_n — совокупность всех переменных, входящих в А и В) формула А истинна, то формула В тоже истинна. Но в этом случае согласно таблице для эквивалентности истинна и формула А «В. Если же при некотором наборе логических значений E ₁, Е₂,..., E_n формула А ложна, то В тоже ложна и согласно таблице для эквивалентности формула А «В истинна.

Обратно, пусть формула А «В тождественно-истинна. Тогда согласно равносильности (26) тождественно-истинны формулы А ® В и В ® А. Если при некотором наборе логических значении E ₁, Е ₂ ,..., E_n формула А истинна, то согласно таблице для эквивалентности формула В не может быть ложной, так как в этом случае была ложна формула А ® В. Если же при некотором наборе логических значений переменных формула А ложна, то формула В не может быть истинной, так как в этом случае была бы ложна формула В ® А. Таким образом, А равносильно В.

Упражнения

I. Установить, какой из следующих четырех формул: А, ~ А, И или Л равносильны формулы:

1) А ® И,

2) А ® Л ,