§3. Логическое следование и равносильность формул. Связь с булевыми алгебрами.

3.1. Логическое следование и равносильность формул. Пусть А и В — произвольные формулы логики высказываний.

Определение 6. Если формула АВ является тавтологией, то говорят, что из формулы А логически следует формула В, или говорят, что В является логическим следствием А. В этом случае пишут А  В. Если же формула АВ является тавтологией, то говорят, что формулы А и В логически эквивалентны или просто эквивалентны. Пишут АВ или АВ. Мы будем придерживаться второго обозначения

Из этого определения вытекает следующее утверждение: если из формулы А логически следует формула В и из формулы В логически следует формула А, то формулы А и В логически эквивалентны, и обратно. Это утверждение легко доказать с помощью тавтологии: (аb)(bа)(аb) в которой пропозициональную переменную а следует заменить формулой А, и переменную b — формулой В.

Упражнение 3.1.Доказать, что имеют место следующие логические следствия:

а) АA;

б) (АВ)(ВС))(АC);

в) АВ(ВС)(АC);

г) (АВ)C(АВ)(АC);

д) А(ВC)В( А C);

е) АВВА;

ж) ААВ;

з) АВАВ;

и) (АВ)(АC)АC;

к) (АВ)CА(ВC);

л) А(ВC)(АВ)C;

м) АВ(АС)(ВС);

н) АВ(АС)(ВС).

Решение. б) Так как формула (ab)(bc))(ac) является тавтологией (см. §2, тавтология 2)), то согласно определения логического следования данное следование имеет место.

Упражнение 3.2. Используя определение и тавтологии из §2, установите следующие равносильности:

а) АВ~ВА (коммутативность конъюнкции);

б) АВ~ВА (коммутативность дизъюнкции);

в) (АВ)C~А(ВC) (ассоциативность конъюнкции);

г) (АВ)C~А(ВC) (ассоциативность дизъюнкции);

д) А(ВC)~(АВ)(АC) (дистрибутивность конъюнкции относительно дизъюнкции);

е) А(ВC)~(АВ)(АC) (дистрибутивность дизъюнкции относительно конъюнкции);

ж) АА~А (идемпотентность конъюнкции);

з) АА~А (идемпотентность дизъюнкции);

и) АА~ (закон противоречия);

к) А~А, А~;

л) АА~ (закон исключённого третьего);

м) А~, А~А;

н) А(ВА)~А (законы

о) А(ВА)~А поглощения);

п) АВ~АВ;

р) (АВ)~АВ (законы;

с) (АВ)~АВ де Моргана;

т) АВ~(АВ)(ВА);

у) А~А(закон снятия двойного отрицания).

Как видим, операции  и  обладают свойствами коммутативности (а) и б)), ассоциативности ((в) и г)), дистрибутивности относительно друг друга (д) и е)), идемпотентности (ж) и з)). Свойства и) и к) носят название законов нуля, при этом свойство и) называется также законом противоречия. Свойства л) и м)  законы единицы, при этом закон л) называется также законом исключённого третьего. Свойства н) и о)  законы поглощения. Свойства р) и с)  законы де Моргана. Свойство у)  закон снятия двойного отрицания.

Очевидно, эти свойства естественным образом обобщаются. Например, свойство а) обобщается на произвольное число конъюнкций: a&b&c~a&c&b~b&a&c и т.д. Кстати, возможность опускать скобки вытекает из в). Вообще, в конъюнкции вида (…((a₁&a₂)&a₃)&…&a_n) скобки можно проставлять произвольным образом, то есть результат не зависит от расстановки скобок. В силу этого в такого рода конъюнкциях скобки не ставятся. Всё сказанное распространяется и на дизъюнкции.

Далее, д) и е) имеют естественные обобщения:

а&(b₁b₂…b_k)~a&b₁a&b₂…a&b_k,

а(b₁&b₂&…&b_k)~(ab₁)&(ab₂)&… &(ab_k).

И т.д.

Используя равносильности 3.2 их следствия, можно формулу или её подформулу заменить равносильной ей. Это означает, что если АВ  некоторая формула, где  одна из операций , , , , , |, , , и В~С (A~С), то АВ~АС(АВ~CB). Такие преобразования формул называются равносильными.

Равносильные преобразования используются для доказательства равносильностей, для приведения формул к заданному виду, в частности, для упрощения формул. Формула А считается проще равносильной ей формулы В, если она содержит меньше букв (по вхождению или наименованию) и меньше логических операций. При этом операции эквивалентность, импликация, штрих Шеффера, стрелка Пирса и логическое сложение заменяются операциями конъюнкции и дизъюнкции, а отрицание относят к пропозициональным переменным (к элементарным высказываниям).

Упражнение 3.3.С помощью равносильных преобразований доказать следующие равносильности.

а) (ху)&(ху)~x;

б) х(х&y)~ху;

в) ху~ху;

г) (х&у)(х&у)(х&у)~ху;

д) ху~yx;

е) х(yz)~ х&yz;

ж) х~(х&y&z)(х&y&z)(x&у&z)(х&у&z);

з) (хy)&(zt)~(х&z)(y&z)(x&t)(y&t);

и) (х&y)(z&t)~(хz)&(yz)&(xt)&(yt).

Решение. 1. (ху)&(ху)х(у&у)х0x

(1) Воспользовались дистрибутивностьюотносительно &.

(2) Воспользовались законом противоречия.

(3) Воспользовались одним из законов нуля.

Упражнение 3.4.Упростить формулы:

а) х(xx);

б) х(ху);

в) (х&у)(ху)&x;

г) (ху)&(ху);

д) (ху)&(уz)(zx);

е) (ху)&(уz)(хz);

ж) (xy)(y);

з) (x|)(z.

Решение. в)

(х&у)(ху)&x(ху)(ху)&x(ху)(х&х)(у&x)(ху)0(у&x)(ху)(у&x)х(у(у&x))ху.

(1) Воспользовались законом де Моргана и равносильностью п) упражнения 3.2.

(2) Воспользовались законом снятия двойного отрицания и дистрибутивностью & относительно .

(3) Воспользовались законом противоречия.

(4) Воспользовались одним из законов нуля.

(5) Воспользовались ассоциативностью операции .

(6) Воспользовались законом поглощения.

3.2. Связь с булевыми алгебрами. Если между формулами установить отношение равенства «=» по правилу А=В  А~В, то на множестве B высказываний определяется алгебра B; &, ; ; 0, 1, которая является булевой. Это следует из свойств операций &, , рассмотренных в упражнении 3.2. Эта алгебра изоморфна некоторой алгебре Кантора P(U); , ; ; , U (определение алгебры Кантора см. в Части II). Не вдаваясь в подробности отметим только, что если   этот изоморфизм, то (a&b)=(a)(b), (ab)=(a)(b), (a)=,(0)=, (1)=U и др. В частности, (a&)=(a)=(a)\(b). Отсюда следует, что понятия и факты, связанные с алгеброй высказываний, можно соответствующим образом переносить на множества и обратно. Например, тождества теории множеств можно доказывать или опровергать на языке алгебры логики.

Пример 3.1. Проверим с помощью алгебры логики тождества:

а) (АВ)\(СА)=(В\С)\(АС);

б) А\(В\С)=(А\В)(АС).

а) Переведём сначала правую и левую части на язык алгебры логики. При этом А, В и С соответствуют a, b и c соответственно: (АВ)\(СА)(ab)&, (В\С)\(АС)(b&)&. Осталось показать, что (ab)&~(b&)&. Построим (сокращённую) таблицу истинности сразу для обеих частей, при этом достаточно построить таблицу до первого несовпадения значений формул. Так как значения формул хотя бы на одном наборе значений не совпадает, то эквивалентности формул нет. Значит, (АВ)\(СА)(В\С)\(АС).

a	b	c	(ab)	&		(b&)	&
0	0	0	0	0	1	0	0	1
0	0	1	0	0	1	0	0	1
0	1	0	1	1	1	1	1	1
0	1	1	1	1	1	0	0	0
1	0	0
1	0	1
1	1	0
1	1	1

б) А\(В\С)a&, (А\В)(АС)(a&)(a&c)

Имеем

a&~a&(c)~(a&)(a&c),

то есть a&~(a&)(a&c). Это означает, что А\(В\С)=(А\В)(АС).

Ясно, что операции кольцевой суммы в алгебре логики и теории множеств соответствуют друг другу. В частности, алгебра B; &,   ассоциативное, коммутативное кольцо с единицей. Оно, как известно, является булевым (см. Часть II).

В частности, это означает, что кроме перечисленных выше эквивалентностей имеют место следующие:

1) аb~ba;

2) (ab)c~a(bc);

3) a0~a;

4) a&(bc)~(a&b)(a&c).

Кроме того, этот список можно продолжить:

5) ab~ab(a&b);

6) ~a1;

7) a=0.

Доказательство этих равенств предлагается провести в качестве упражнения 3.5.