Тавтологии и эквивалентность формул

Тавтологии. Формулы выполнимые и опровержимые. Теоремаоправиле modus ponens: Если
X и X→Y — тавтологии, тои Y — тавтология. ПодстановкаS(z₁,z₂,...,z_n|Y₁,Y₂,...,Y_n|X) (результат подстановки Y_i вместо z_i) — пропозициональная формула. Эквивалентность формул алгебры высказываний. Теорема о заменах. Следствие 1: если X — тавтология, то и S(z₁,z₂,...,z_n|Y₁,Y₂,...,Y_n|X) — тавтология. Следствие 2: инвариантность эквивалентности относительно логических операций.

Среди формул алгебры высказываний выделяют:

1. выполнимые, имеющиезначение 1 хотя бы для одного набора значений пропозициональных переменных;
2. опровержимые, имеющие значение 0 хотя бы для одного набора значений пропозициональных переменных.

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

Пример 2.1. Формула (x ∨ ( ¬ y )) → z является одновременно выполнимой и опровержимой: она истинна, если значением переменной z является истинное высказывание, и ложна, если, например, значениями переменных y и z являются ложные высказывания. Это можно увидеть составив истинностную функцию, которая в данном случае описывается вектором 01110101. Формула (x ∨ ( ¬ x)) является тавтологией, а формула (x ∧ (¬ x)) — противоречием. #
Следующее утверждение отражает часто используемое на практике умозаключение, называемое modus ponens (модус поненс).

Теорема 2.2. Если формулы X и X → Y являются тавтологиями, то и формула Y есть тавтология.

◀Пусть формулы X и Y построены из переменных z₁, ..., z_n. Выберем для этих переменных какие-либозначения. Тогда об истинности формулы X →Y можно судить на основании истинности формул X и Y . Анализируя истинностную функцию для импликации, видим, что при истинности X и ложности Y формула X → Y является ложной. Но по условию теоремы эта формула тождественно истинная, как и формула X. Следовательно, формула Y не может быть ложной при выбранных значениях переменных. Поскольку значения переменных выбирались произвольно, заключаем, что формула Y тождественно истинна, т.е. тавтология. ▶

Как и в булевой алгебре, введем понятие эквивалентных формул алгебры высказываний — формул, имеющих равные истинностные значения при любых значениях входящих в формулы переменных. Альтернативное определение: формулы X и Y называются эквивалентными, если формула X ~ Y является тавтологией. Нетрудно показать, рассуждая как в последней теореме, что формула X ~ Y является тавтологией тогда и только тогда, когда при любых значениях переменных формулы X и Y одновременно или истинны, или ложны, т.е. истинностные функции этих формул совпадают. Для эквивалентных формул введем обозначение X ≡ Y .
Итак, X ≡ Y ⇔ X ~ Y — тавтология. Обратите внимание на три символа эквивалентности в последней фразе. Первый обозначает отношение эквивалентности формул, введенное на множестве формул алгебры высказываний, третий — операцию эквиваленции, а второй — по сути та же эквиваленция, новутверждении, в котором формулируется свойство самой алгебры высказываний, и ее следует отнести к сфере метаязыка.

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

Теорема 2.3.

1) Если X ≡ Y , то при замене всех вхождений какой-либо переменной и в X, и в Y какой-либо формулой Z получим эквивалентные формулы.
2) Если в формуле X заменить одно из вхождений подформулы Y эквивалентной формулой Z, то получим формулу, эквивалентную X.

Под подстановкой будем понимать замену всех вхождений в формулу одной или нескольких переменных некоторыми формулами. Результат подстановки в формулу X вместо переменных z₁, ..., z_nформул Y₁, ..., Y_nобозначают примерно так: S (z₁,...,z_n|Y₁,...,Y_n|X).
Следствие 2.1. Если X — тавтология, то и S (z₁,...,z_n|Y₁,...,Y_n|X) — тавтология. Можно рассуждать так. Тавтологии — это формулы, эквивалентные, например, формуле W = x ∨ ¬x. В качестве переменной x можно выбрать ту, которая не входит в формулу X. В силу теоремы, заменив в формулах X и W все вхождения переменных z₁, ..., z_nформулами Y₁, ..., Y_n, мы получим эквивалентные формулы. Но формула W при этом не изменится.
Поэтому вновь построенная формула S (z₁,...,z_n|Y₁,...,Y_n|X) будет эквивалентна формуле W, т.е. будет являться тавтологией.
Следствие 2.2. Пусть X ≡ Z и Y ≡ W. Тогда (X ∨ Y ) ≡ (Z ∨ W), (X ∧ Y ) ≡ (Z ∧ W), (X → Y ) ≡ (Z → W), (X ~ Y ) ≡ (Z ~ W), (¬X) ≡ (¬Z).
◀Формулу (Z ◦ W), где ◦ — одна из логических связок, можно рассматривать как результат замены в формуле (X ◦ Y ) сперва подформулы X эквивалентной формулой Z, а затем подформулы Y эквивалентной формулой W. Согласно доказанной теореме такая замена приводит к эквивалентной формуле. Аналогичны рассуждения и для отрицания.▶