2.3. Эквивалентность формул. Свойства элементарных функций. Принцип двойственности
Мы видели, что каждой формуле над В соответствует функция алгебры логики, причем различным формулам могут соответствовать равные функции.
Определение. Формулы М и N над В будем называть эквивалентными, если соответствующие им функции fM и fN равны. Запись M=N будет означать, что M и N эквивалентны.
Пример 6:
1) 0=(xΛ );
2)
(
Λ(x2+x3))=(
);
3)
(x→y)=
(
→
).
Приведем список эквивалентностей (тождеств), характеризующих свойства некоторого множества элементарных функций.
Обозначим через (x1◦x2) любую из функций (x1Λx2), (x1Vx2), (x1+x2).
1) Функция (x1◦x2) обладает свойством ассоциативности:
((x1◦x2) ◦x3)= (x1◦(x2◦x3)).
2) Коммутативность (x1◦x2)= (x2◦x1)
3) Для конъюнкции и дизъюнкции выполняются дистрибутивные законы:
((x1Vx2) Λx3)= ((x1Λx3)V(x2Λx3))
((x1Λx2) Vx3)= ((x1Vx3)Λ(x2Vx3)).
4) Имеют место следующие соотношения между отрицанием, конъюнкцией и дизъюнкцией:
=x;
;
.
5) Выполняются следующие свойства конъюнкции и дизъюнкции:
(xΛx)=x; (xVx)=x
(xΛ )=0; (xV )=1
(xΛ0)=0; (xV0)=x
(xΛ1)=x; (xV1)=1.
Тождества можно проверить сопоставляя функции, соответствующие правой и левой частям тождеств.
Замечание 1. С целью упрощения записи формул условимся, что операция Λ сильнее операции V, т.е. если нет скобок, то сначала выполняется Λ, а потом V. (Например, x1Λx2Vx3= ((x1Λx2)Vx3))
Замечание 2. В силу закона ассоциативности и вместо формул ((x1◦x2) ◦x3), (x1◦(x2◦x3)) можно использовать выражение (x1◦x2 ◦x3), которое, вообще говоря, не является формулой, но превращается в нее расстановкой скобок.
Замечание 3. В формулах, у которых внешняя функция является элементарной, внешние скобки опускаются.
Например: вместо (x1Vx2) пишем x1Vx2
.
Замечание 4. Используются следующие обозначения
,
имеющие смысл при s≥1.
Удобно сформулировать ряд правил, вытекающих из п.2 и 5 списка тождеств элементарных функций.
Если в логическом произведении один из сомножителей равен 0, то и все произведение равно 0.
Если в логическом произведении, содержащем не менее двух множителей, имеется множитель, равный 1, то его можно зачеркнуть.
Если в логической сумме не менее двух слагаемых, одно из которых 0, его можно зачеркнуть.
Если в логической сумме одно из слагаемых равно 1, то и вся логическая сумма равна 1.
Нетрудно видеть, что если М' – подформула формулы М и если заменить любое из ее вхождений на эквивалентную формулу N', то формула М перейдет в формулу N, которая эквивалентна М.
Этот принцип вместе с тождествами для элементарных функций, к которым присоединяются все тождества, полученные подстановкой вместо переменных х, x1, x2, x3 … любых формул, позволяет осуществлять эквивалентные преобразования и получать новые тождества.
Пример 7.
x1Vx1
Λx2=
(x1Λ1)V(x1Λx2)=
x1Λ(x2V
)V(x1Λx2)=
x1Λx2Vx1Λ
Vx1Λx2
= (x1Λx2Vx1Λ
x2)V
x1Λ
=
x1Λ
x2V
x1Λ
=
x1Λ(x2V
)=
x1Λ1=
x1.
Таким образом получили так называемое правило поглощения произведения x1Λx2 множителем x1.
Существует еще один способ для получения тождеств. Он основан на использовании так называемого принципа двойственности.
Определение.
Функция
,
называется двойственной
функцией к функции f(x1,
…, xn).
Очевидно, что таблица для двойственной функции (при выбранном порядке наборов x1, …, xn) получается из таблицы для функции f(x1, …, xn) инвертированием (т.е. заменой 0 на 1 и 1 на 0) столбца функции и его переворачиванием.
Таблица 7
-
x1
x2
x3
f(x1, x2, x3)
[f(x1, x2, x3)]*
0
0
0
1
0
0
0
1
1
1
0
1
0
0
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
1
1
1
0
0
0
1
1
1
1
0
Из определения двойственности следует, что f**=(f*)*=f (свойство взаимности).
Нетрудно видеть, что среди функций 0, 1, х, , x1Λx2, x1Vx2,
функция 0 двойственна 1
1 0
х х
x1Λx2 x1Vx2
x1Vx2 x1Λx2
Принцип двойственности. Если формула M=C[f1, …, fs] реализует функцию f(x1, …, xn), то формула C[f*1, …, f*s], т.е. формула, полученная из М заменой функций f1, …, fs соответственно на (f*1, …, f*s) реализует функцию f*(x1, …, xn).
Эту формулу будем называть формулой двойственной к М и обозначать через М*. Таким образом,
M*=C(f*1, …, f*s).
Для формул над множеством B={0, 1, , x1Λx2, x1Vx2} принцип двойственности можно сформулировать так:
Для получения формулы М*, двойственной к формуле М, нужно в формуле М всюду заменить
0 на 1; 1 на 0; Λ на V; V на Λ, или если
М=С(0, 1, , x1Λx2, x1Vx2), то
М*=С(1, 0, , x1Vx2, x1Λx2).
Пример 8.
1) М1(x1; x2)= x1Λx2; М*1(x1; x2)= x1Vx2
2)
М2(x1;
x2)=
x1Λx2V
Λ
М*2(x1; x2)= (x1Vx2)Λ( V ).
Из принципа двойственности вытекает, что если
М(x1, …, xn)= N(x1, …, xn), то
М*(x1, …, xn)= N*(x1, …, xn).
Пример
9. Из тождества
вытекает тождество
.