Равносильные формулы. 
Математика: логика, теория множеств и комбинаторика

В первом парафафе было дано понятие равносильных предложений. Аналогичным образом можно понимать равносильность формул. Рассмотрим вначале случай, когда формулы зависят только от переменных, вместо которых можно подставлять конкретные высказывания.

Обозначим буквами Р и Q две произвольные формулы.

Формулы Р и Q называются равносильными (или логически равными), если при любых значениях переменных эти формулы принимают одинаковые истинностные значения.

Пример 2.3.1. Формула (A—«1/?)a (~U—>В), рассмотренная в примере.

2.1.1, равносильна формуле 1 (АВ). Построим для последней формулы таблицу истинности.

Видим, что формула 1(Л/?), принимает значение истины только в двух случаях: А-и, В=л и А=л, В-и. Если изобразить две таблицы рядом и сохранить порядок записи строк, то столбцы значений этих формул совпадут. •.

Таким же способом можно доказать равносильность формул А<�г*В и (Л—"/?)л (Л—"#), что уже было установлено при определении операции эквиваленции.

Упражнение. В примере 2.2.1 была построена таблица истинности формулы (Л—>T#vC)a1C—"~U. Докажите, что эта формула равносильна более простой формуле A->BvC.

Отношение равносильности тесно связано с операцией эквиваленции. Пусть формулы Р и Q равносильны. Образуем новую формулу P Эта формула будет принимать уже только истинные значения. Действительно, если формула примет значение лжи при некоторых значениях переменных, значит, в этом случае формулы Р и Q принимают разные значения (по определению операции), чего нс может быть по причине равносильности этих формул. И наоборот, если формула P<-*Q принимает только истинные значения, значит, формулы Р и Q равносильны.

Для обозначения равносильных формул будем использовать знак = (подобно знаку равенства = для алгебраических выражений). Тогда предложение «Формулы Р и Q равносильны» можно записать кратко: P=Q.

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

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

Пример 2.3.2. Убедимся, что формула (Л-«#)лЛ—>? является тавтологией. Для этого составим таблицу истинности.

Тавтологиями также являются следующие формулы:

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

На языке тавтологий можно выразить понятие равносильности: равносильность формул Р и Q означает, что формула P<-*Q является тавтологией.

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

Рассмотрим для примера формулы l (Vx4(jf)) и 3aTU (.v). Они равносильны, так как, взяв вместо буквы А любой предикат, зависящий от х, мы получим одинаковые по логическому значению высказывания. Предложение «Неверно, что все допустимые значения х удовлетворяют свойству А (х)» означает то же, что предложение «Существует *, при котором свойство А{х) не выполняется». Итак, |(Vj&4(*)) = 3xL4(jc). Аналогичными рассуждениями можно покатать, что Т (3×4(л')) = V. v" W (.r).