Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

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

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

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 формула А истинна, то согласно таблице для эквивалентности формула В не может быть ложной, так как в этом случае была ложна формула А ® В. Если же при некотором наборе логических значений переменных формула А ложна, то формула В не может быть истинной, так как в этом случае была бы ложна формула В ® А. Таким образом, А равносильно В.