2232
.pdf1.3. Эквивалентность формул. Свойства элементарных функций. Принцип двойственности
Мы видели, что каждой формуле над В соответствует функция алгебры логики, причем различным формулам могут соответствовать равные функции.
Определение. Формулы М и N над В будем называть эквивалентными, если соответствующие им функции fM и fN равны. Запись M=N будет означать, что M и N эквивалентны.
Пример 1.6:
1) 0=(xΛ x );
2) ( x1 Λ(x2+x3))=( x1 x2 x3 x3 x2 );
3) (x→y)= ( y → x ).
Приведем список эквивалентностей (тождеств), характеризующих свойства некоторого множества элементарных функций.
Обозначим через (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 =x; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
x1 x2 |
|
|
|
x1 x2 ; x1 x2 |
|
x1 x2 . |
|||||||||||
5) Выполняются следующие свойства конъюнкции и дизъ- |
||||||||||||||||||
юнкции: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
(xΛx)=x; |
(xVx)=x |
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
(xΛ x )=0; |
(xV x )=1 |
|
|
|
|
|
||||||||||||
(xΛ0)=0; |
(xV0)=x |
|
|
|
|
|
||||||||||||
(xΛ1)=x; |
(xV1)=1. |
|
|
|
|
|
Тождества можно проверить сопоставляя функции, соответствующие правой и левой частям тождеств.
11
Замечание 1. С целью упрощения записи формул условимся, что операция Λ сильнее операции V, т.е. если нет скобок, то сначала выполняется Λ, а потом V. (Например, x1Λx2Vx3= ((x1Λx2)Vx3))
Замечание 2. В силу закона ассоциативности и вместо формул ((x1◦x2) ◦x3), (x1◦(x2◦x3)) можно использовать выражение (x1◦x2 ◦x3), которое, вообще говоря, не является формулой, но превращается в нее расстановкой скобок.
Замечание 3. В формулах, у которых внешняя функция является элементарной, внешние скобки опускаются.
Например: вместо (x1Vx2) пишем x1Vx2
x1 x2 x1 x2 .
Замечание 4. Используются следующие обозначения
s |
|
|
|
|
|
i |
xi |
x1 |
x2 |
... |
xs |
1 |
|
|
|
|
|
s |
|
|
|
|
|
V xi |
x1 |
x2 |
... |
xs , имеющие смысл при s≥1. |
|
i |
1 |
|
|
|
|
Удобно сформулировать ряд правил, вытекающих из п.2 и 5 списка тождеств элементарных функций.
1.Если в логическом произведении один из сомножителей равен 0, то и все произведение равно 0.
2.Если в логическом произведении, содержащем не менее двух множителей, имеется множитель, равный 1, то его можно зачеркнуть.
3.Если в логической сумме не менее двух слагаемых, одно из которых 0, его можно зачеркнуть.
4.Если в логической сумме одно из слагаемых равно 1, то и вся логическая сумма равна 1.
Нетрудно видеть, что если М' – подформула формулы М и если заменить любое из ее вхождений на эквивалентную формулу N', то формула М перейдет в формулу N, которая эквивалентна М.
Этот принцип вместе с тождествами для элементарных функций, к которым присоединяются все тождества, полученные подста-
новкой вместо переменных х, x1, x2, x3 … любых формул, позволяет осуществлять эквивалентные преобразования и получать новые тождества.
12
Пример 1.7.
x1Vx1 Λx2= (x1Λ1)V(x1Λx2)= x1Λ(x2V x2 )V(x1Λx2)= x1Λx2Vx1Λ
x2 Vx1Λx2 = (x1Λx2Vx1Λ x2)V x1Λ x2 = x1Λ x2V x1Λ x2 = x1Λ(x2V x2 )=
x1Λ1= x1.
Таким образом получили так называемое правило поглощения произведения x1Λx2 множителем x1.
Существует еще один способ для получения тождеств. Он основан на использовании так называемого принципа двойственности.
Определение. Функция f x1,..., xn * f x1,..., xn , называется
двойственной функцией к функции 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, х, x , x1Λx2, x1Vx2,
функция 0 |
двойственна 1 |
1 |
0 |
х |
х |
|
|
|
|
|
|
|
x |
|
|
x |
|
x1Λx2 |
x1Vx2 |
||||
x1Vx2 |
x1Λx2 |
13
Принцип двойственности. Если формула 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, x , x1Λx2, x1Vx2} принцип двойственности можно сформулировать так:
Для получения формулы М*, двойственной к формуле М, нужно в формуле М всюду заменить
0 на 1; 1 на 0; Λ на V; V на Λ, или если
М=С(0, 1, x , x1Λx2, x1Vx2), то
М*=С(1, 0, x , x1Vx2, x1Λx2).
Пример 1.8.
1)М1(x1; x2)= x1Λx2; М*1(x1; x2)= x1Vx2
2)М2(x1; x2)= x1Λx2V x1 Λ x2
М*2(x1; x2)= (x1Vx2)Λ( x1 V x2 ).
Из принципа двойственности вытекает, что если
М(x1, …, xn)= N(x1, …, xn), то М*(x1, …, xn)= N*(x1, …, xn).
Пример 1.9. Из тождества x1 x2 x1 x2 вытекает тожде-
ство x1 x2 x1 x2 .
1.4. Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма
Возникает вопрос. Если в качестве В допустить некоторый запас элементарных функций, то всякая ли функция алгебры логики может быть выражена в виде формулы? Ближайшие рассмотрения направлены на решение этого вопроса.
Обозначим
xσ=xΛσV x Λ ,
где σ – параметр, равный либо 0, либо 1.
14
Очевидно, что |
|
|||
|
|
|
|
|
x |
x при |
0 |
||
x при |
1 |
|||
|
Легко видеть, что xσ=1, тогда и только тогда, когда x=σ. Теорема (о разложении функций по переменным)
Каждую функцию алгебры логики f(x1, …, xn) при каждом m=1…n можно представить в виде:
f x1,..., xm , xm 1,..., xn |
|
V x1 1 ... xmm f 1,..., m , xm 1,..., xn , |
(1.1) |
1 ,..., m |
|
где дизъюнкция берется по всем возможным наборам значений переменных x1, …, xm (это представление называется разложением функции по переменным x1, …, xm).
Доказательство:
Рассмотрим произвольный набор значений переменных (α1,…,αn) и подставим его в левую и правую части равенства (1.1).
Левая часть дает f(α1, …, αn). Правая
V |
1 |
... |
m |
m |
f |
1,..., |
m , m 1,..., |
n |
|
1 |
|
|
|
|
|
|
|
1 ,..., m |
|
|
|
|
1,..., |
m , |
m 1,..., n |
f 1,..., n |
1 |
... |
m |
f |
|
||||
1 |
|
m |
|
|
|
|
|
|
Т.е. на каждом наборе (α1, …, αn) левая и правая части совпадают, что и требовалось доказать.
В качестве следствий из этой теоремы получаем два специальных случая разложения.
1) Разложения по переменной
f(x1, …, xn-1, xn)= xnΛ f(x1, …, xn-1, 1)V xn Λ f(x1, …, xn-1, 0).
Функции f(x1, …, xn-1, 1) и f(x1, …, xn-1, 0) называются компонентами разложения.
2) Разложение по всем n переменным
f x1 ,..., xn |
V x1 1 x2 2 ... xn n |
f 1 ,..., n |
|
|
|
1 ,..., n |
|
|
V |
n |
(1.2) |
|
xi i |
|
|
|
1 ,..., n |
i 1 |
|
f |
1 ,..., n |
1 |
|
15
Это разложение (1.2) называется совершенной дизъюнктивной нормальной формой (совершенной д.н.ф.).
Имеет место Теорема: Каждая функция алгебры логики может быть выра-
жена в виде формулы через отрицание, конъюнкцию и дизъюнкцию. Доказательство:
1)Если f(x1, …, xn) ≡ 0, то f(x1, …, xn) = x1Λ x1 .
2)Если f(x1, …, xn) ≠ 0,
|
|
n |
|
|
|
|
|
то f x1,..., xn |
V |
xi |
i xi |
|
i . |
||
|
1 ,..., n |
i 1 |
|
|
|
|
|
f |
1 ,..., n |
1 |
|
|
|
|
|
Доказанная теорема носит конструктивный характер. Она позволяет для каждой функции построить формулу, ее реализующую (в виде совершенной д.н.ф.). Для этого:
1)В таблице истинности для функции f(x1, …, xn) отмечаем все строки (σ1, …, σn), в которых f(σ1, …, σn)=1.
2)Для каждой такой строки образуем логическое произведе-
|
n |
|
ние |
x |
i . |
|
i |
i1
3)Все полученные конъюнкции соединяем знаком дизъюнкции.
Пример 1.10.
1) Найти совершенную д.н.ф. для функции x1→x2.
Имеем три набора (0, 0), (0, 1), (1, 1), на которых эта функция равна 1. Поэтому
x1→x2=x1°Λx2°V x1°Λx21 V x11Λx21= x1 Λ x2 V x1 Λx2V x1Λx2.
2) Найти совершенную д.н.ф. для функции, заданной нижеследующей таблицей 8.
16
Таблица 8
x1 |
x2 |
x3 |
f(x1, x2, x3) |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
f(x1, x2, x3) = x1 Λ x2 Λ x3 V x1 Λ x2 Λx3V x1Λ x2 Λx3 V x1Λx2Λ x3.
Совершенная дизъюнктивная нормальная форма имеет вид ΣП. Нельзя ли для булевых функций получить выражение типа ПΣ? Покажем, что при f≠1 это возможно.
Для этого разложим двойственную функцию f* к функции f (f*≠0) в совершенную д.н.ф..
f * |
|
|
|
|
|
|
n |
|
|
|
|
|
|
x1,..., xn |
|
V |
|
|
xi |
i |
|
||||||
|
|
1 ,..., n |
|
i |
1 |
|
|
|
|
|
|||
|
|
f * |
|
1 ,..., n |
|
1 |
|
|
|
|
|
|
|
Возьмем тождество для двойственных функций |
|||||||||||||
f ** |
|
|
|
|
|
|
|
n |
|
|
|
|
|
x1,..., xn |
|
|
|
|
|
V xi i |
|
||||||
|
|
1 ,..., n |
|
|
i 1 |
|
|
|
|
|
|||
|
|
f * |
1 ,..., |
n |
1 |
|
|
|
|
|
|
||
Т.к. f**=f, то |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
n |
|
|
|
|
n |
f x1,..., xn |
|
|
|
|
|
V xi |
i |
V xi i |
|||||
|
|
1 ,..., n |
|
i |
1 |
1 ,..., n |
i 1 |
||||||
|
|
f * |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 ,..., n |
1 |
|
|
f 1 ,..., n |
0 |
||||||
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
1 ,..., n |
V xi i |
|
|
|
|
|
|
|
|
|||
|
i 1 |
|
|
|
|
|
|
|
|
|
|
|
|
f |
1 ,..., n |
0 |
|
|
|
|
|
|
|
|
|
|
|
Это выражение носит название совершенной конъюнктивной нормальной формы (совершенной к.н.ф.).
17
Пример 1.11.
1) Построить совершенную к.н.ф. для функции x1→x2. f(x1,x2)=0 только для набора (1, 0)
x1→x2= x11 V x2o =x1°Vx21 = x1 V x2.
2) Построить совершенную к.н.ф. для f(x1, x2, x3) из предыдущего примера
f(x1, x2, x3) =(x1V x2 Vx3)Λ(x1V x2 V x3 )Λ( x1 Λx2Λ x3)Λ
Λ( x1 V x2 Vx3).
Выводы: В качестве средства для задания булевых функций наряду с таблицами можно использовать язык формул над множеством функций, состоящим из отрицания, конъюнкции и дизъюнкции. Так как табличный язык по громоздкости примерно эквивалентен языку совершенных д.н.ф. (к.н.ф.), то язык формул не хуже языка таблиц. Можно показать, что на самом деле он существенно лучше таблицы.
К примеру, рассмотрим функцию
f(x1, …, x20) =x1V x2V…Vx20 .
Эта формула в правой части содержит 39 символов, ее же таблица содержит 220 строк, т.е. больше миллиона.
1.5. Полнота и замкнутость
Мы видели, что каждая булева функция может быть выражена
в виде формулы через элементарные функции x ; x1Λx2; x1Vx2. Является ли этот набор случайным? Или есть и другие наборы функции, обладающие тем же свойством?
Определение. Система функций {f1, f2, …, fs, …} из P2 называется полной, если каждая булева функция может быть записана в виде формулы через функции этой системы.
Примеры полных систем.
1.Система P2 – полная система.
2.Система B={ x ; x1Λx2; x1Vx2} – полная. Теорема. Пусть даны две системы функций из P2
B={f1, …, fs, …} (I) и G={g1, …} (II),
18
относительно которых известно, что система I полна и каждая функция системы I выражается через функции системы II в виде формулы. Тогда система II будет полной.
Доказательство очевидно.
3. Система B={ x ; x1Λx2} является полной.
Для доказательства этого используем теорему и тождество
x1Vx2= x1 x2
4. Система B={ x ; x1Vx2} является полной.
Это доказывается либо так же, как и в п.3, либо через принцип двойственности.
5. Система B={x1/x2} является полной.
Для доказательства в качестве системы I возьмем { x ; x1Λx2}, а за систему II – систему {x1/x2}.
Легко видеть, что выполняются эквивалентности
x1 = x1/x2; (x1/x2)/( x1/x2)= x1 / x2 = x1Λx2.
6. Система B={0; 1; x1Λx2; x1+x2} является полной.
Для доказательства за систему I возьмем { x ; x1Λx2}, а за систему II – рассматриваемую систему В. Имеем равенства
х1+1= x1 .
Конъюнкцию x1Λx2 будем обозначать для краткости и, по аналогии с обычным умножением, через x1x2.
Так как формула, построенная из полной системы 6 после раскрытия скобок и приведения подобных переходит в полином по модулю 2, получаем следующую теорему:
Теорема Жегалкина. Каждая функция из Р2 может быть выражена при помощи полинома по модулю 2 (полинома Жегалкина).
f x1,..., xn |
ai i |
...i |
S |
xi |
...xi |
S |
|
1 2 |
|
1 |
|
||
|
i1 ,...,iS |
|
|
|
|
|
Посчитаем число полиномов Жегалкина от n переменных, число членов xi1…xis равно числу подмножеств (i1, …, is) из n чисел (1, …, n), т.е. равно 2n. Поскольку ai1…is равно либо 0, либо 1, то ис-
комое число полиномов равно 22n , т.е. числу всех булевых функций от тех же переменных следует, что каждая булева функция пред-
ставляется полиномом Жегалкина единственным образом.
Пример 1.12. Выразить x1Vx2 в виде полинома Жегалкина.
19
Будем искать выражение для x1Vx2 в виде полинома с неопределенными коэффициентами.
x1Vx2= ax1x2+bx1+cx2+d
Таблица 9
x1 |
x2 |
(x1Vx2) |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
d |
a |
1 |
|
|
1 |
c |
b |
1 |
x1Vx2= -x1x2+x1+x2 |
|
1 |
b |
c |
1 |
||
|
|||||
1 |
a b |
c d |
0 |
|
С понятием полноты тесно связано понятие замкнутости. Определение: Пусть М – некоторое подмножество функций
из Р2. Замыканием М называется множество всех функций, представимых в виде формул через функции множества М.
Обозначается [M].
Нетрудно видеть, что замыкание инвариантно относительной операции введения и удаления фиктивных переменных.
Пример 1.13.
1)M=P2. Очевидно, что [M]=P2.
2)M={1, x1+x2}. Замыканием этого множества будет класс L всех линейных функций
f(x1, …, xn)= c0+ c1x1+…+ cnxn,
где ci=0; 1 (i=0, …, n); существенные переменные входят с коэффициентом 1, фиктивные – с коэффициентом 0.
Определение. Множество М называется замкнутым, если
[M]=M.
Пример 1.14.
1)Множество M=P2 является замкнутым.
2)M={1, x1+x2} не замкнуто.
20