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

Теория

Тавтологии. Формулы выполнимые и опровержимые. Теоремаоправиле modus ponens: Если
X и XY — тавтологии, тои Y — тавтология. ПодстановкаS(z1,z2,...,zn|Y1,Y2,...,Yn|X) (результат подстановки Yi вместо zi) — пропозициональная формула. Эквивалентность формул алгебры высказываний. Теорема о заменах. Следствие 1: если X — тавтология, то и S(z1,z2,...,zn|Y1,Y2,...,Yn|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 построены из переменных z1, ..., zn. Выберем для этих переменных какие-либозначения. Тогда об истинности формулы 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 вместо переменных z1, ..., znформул Y1, ..., Ynобозначают примерно так: S (z1,...,zn|Y1,...,Yn|X).
Следствие 2.1. Если X — тавтология, то и S (z1,...,zn|Y1,...,Yn|X) — тавтология. Можно рассуждать так. Тавтологии — это формулы, эквивалентные, например, формуле W = x ∨ ¬x. В качестве переменной x можно выбрать ту, которая не входит в формулу X. В силу теоремы, заменив в формулах X и W все вхождения переменных z1, ..., znформулами Y1, ..., Yn, мы получим эквивалентные формулы. Но формула W при этом не изменится.
Поэтому вновь построенная формула S (z1,...,zn|Y1,...,Yn|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. Согласно доказанной теореме такая замена приводит к эквивалентной формуле. Аналогичны рассуждения и для отрицания.▶