Пример 4.3.

А ┐A — тавтология, А & ┐ А — противоречие, А → ┐ А — выполнимая формула, она истинна при А = Л.

Теорема 4.1. Пусть А — некоторая формула. Тогда:

1. Если А — тавтология, то ┐А — противоречие, и наоборот;

2. Если А — противоречие, то ┐A — тавтология, и наоборот;

3. Если А — тавтология, то неверно, что А — противоречие, но не наоборот;

4. Если А — противоречие, то неверно, что А — тавтология, но не наоборот.

Доказательство. Очевидно из определений.

Теорема 4.2. Если формулы А и А → В — тавтологии, то формула В — тавтология.

Доказательство. От противного. Пусть 1(В) = Л. Но 1(А) = И, так как А — тавтология, значит, 1(А → В) = Л, что противоречит предположению о том, что А → В — тавтология.

Можно перечислить наиболее важные тавтологии (А, В, С – произвольные формулы):

1) А®А;

2) А®(В®А);

3) (А®В)®((В®С)®(А®С)) (цепное рассуждение);

4) (А®(В®С))®((А®В)®(А®С));

5) (А&В)®А, (А&В)®В; (4.1)

6) А®(В®(А&В));

7) А®(АÚВ), В®(АÚВ);

8) (┐В ®┐А)®((┐В®А)®В);

9) ((А ®В)®А)®А (закон Пирса).

Немаловажную роль играют логическое следование и логическая эквивалентность формул.

Говорят, что формула В логически следует из формулы А (обозначается А В), если формула В имеет значение И при всех интерпретациях, при которых формула А имеет значение И. Говорят, что формулы А и В логически эквивалентны (обозначается А В, или просто А = В), если они являются логическим следствием друг друга. Логически эквивалентные формулы имеют одинаковые значения при любой интерпретации.

Теорема 4.3. (Р® Q)Û(┐РÚQ).

Доказательство. Для доказательства достаточно проверить, что формулы действительно имеют одинаковые истин­ностные значения при всех интерпретациях.

Р	Q	P → Q	┐Р	┐Р Q
И	И	И	Л	И
Л	И	И	И	И
И	Л	Л	Л	Л
Л	Л	И	И	И

Теорема 4.4. Если А, В, С — любые формулы, то имеют место следующие логические эквивалент­ности:

1. A A=A, A & A = A;

2. А В = В А, A &В = B& A;

3. А (В С) = (А В) С,A &(В&С) = (A &В)&С;

4. A (B&C)=(A B)&(A C), A &(B C) = (A &B) (A &C);

5. (A&B) A=A, (A В)& A = A;

6. A Л = A, A &;Л = Л; (4.2)

7. A И = И, A & И = A;

8. ┐ (┐ A) = A; ┐ (A Ú B) = ┐ A&┐ B;

9. ┐ (A&B) = ┐ A ┐B,

10. A ┐A = И, A & ┐ A = Л

Доказательство всех эквивалентностей (они нам уже знакомы по разделу 3) непосредственно проводится построением таблиц истинности.

Анализируя все полученные результаты, можем, таким образом, заметить, что алгебра {И,JI}; ,&,┐ является булевой алгеброй, которая называется алгеб­рой высказываний.

Теорема 4.5. P₁ &... & P_n Q тогда и только тогда, когда (P₁ &... & P_n) Q тавтология.

Доказательство. Необходимость. Пусть I(P₁ &... & P_n) = И. Тогда

I(Q) = И и I(P₁ &... & P_n Q) = И.

Пусть I(P₁ &... & P_n) = Л. Тогда I(P₁ &... & P_n Q) = И при любой интерпретации I. Таким образом, формула P₁ &... & P_n Q общезначима.

Достаточность. Пусть I(P₁ &... & P_n) = И. Тогда I(Q) = И, иначе бы формула P₁ &... & P_n Q не была бы тавтологией. Таким образом, формула Q — логическое следствие формулы P₁ &... & P_n.

Теорема 4.6. P₁ &... & P_n Q тогда и только тогда, когда P₁ &... & P_n & ┐Q — противоречие.

Доказательство. По предыдущей теореме P₁ &... & P_n Q тогда и только тогда, когда формула P₁ &... & P_n Q — тавтология. По первой теореме подраздела 4.1.3 формула P₁ &... & P_n Q является тавтоло­гией тогда и только тогда, когда формула ┐ (P₁ &... & P_n Q) является противоречием. Имеем:

┐ (P₁ &... & P_n Q) = ┐( ┐ (P₁ &... & P_n) Ú Q)=

= ┐┐(P₁ &... & P_n) & ┐Q)=P₁ &... & P_n & ┐Q.

Определим преобразование логических фигур с помощью подстановки.

Пусть А — некоторая формула, в которую входит переменная х (обозначается А (... х...)) или неко­торая подформула В (обозначается A (… В...)), и пусть С — некоторая формула. Тогда

А (...х...){ С / / х }

обозначает формулу, полученную из формулы А подстановкой формулы С вместо всех вхождений переменной х, а А (... B...){ С / B } обозначает формулу, полученную из формулы А подстановкой формулы С вместо некоторых (в частности, вместо одного) вхождений подформулы В.

Теорема 4.7. Если А(... х...) — тавтология и В — любая формула, то А(...х...){В//х} — тав­тология.

Доказательство. Пусть С = A (... х...){В // х}. Пусть I — интерпретация С (она не содержит x). Пусть . Тогда , но = И, следовательно I(C) = И.

Теорема 4.8. Если А (... В...) и В = С, a D = А (... В...){ С/В }, то А=D.

Доказательство. Пусть I — любая интерпретация. Тогда I (В) = I (С), значит I (A) = I (D).