DisMathTPU
.pdf131
дистрибутивности, получим сумму положительных конъюнкций, которая не является полиномом Жегалкина, если в ней конъюнкции повторяются. Используя равносильности x x = 0 è x 0 = x, удалим пары одинаковых
конъюнкций. В результате получим полином Жегалкина.
Лемма о числе положительных конъюнкций. Число различных положительных конъюнкций переменных из множества X = fx1; : : : ; xng равно 2n.
Доказательство. Каждая положительная конъюнкция состоит из подмножества переменных из X, то есть представляется булевым вектором
длины n, и наоборот, каждый вектор длины n задает положительную конъюнкцию подмножества переменных X. Значит, число различных положительных конъюнкций равно числу векторов длины n, то есть равно 2n.
Определение. Форму представления полинома Жегалкина
P = c0K0+ c1K1+ : : : c2n 1K2+n 1
булевой функции f(x1; : : : ; xn), ãäå ci булевы константы, назовем формой
с коэффициентами.
Число 2n положительных конъюнкций Ki+ определяется леммой. Дого- воримся однозначно связывать с номером конъюнкции Ki+ åå âèä ïî ñëå-
дующему правилу: число i представлять булевым вектором a1 : : : an, êî-
торый, в свою очередь, задаст подмножество переменных, составляющих конъюнкцию Ki+.
Пример. При n = 3 конъюнкция K5+ = x1x3, так как число 5 предста- вляется булевым вектором 101, который задает подмножество переменных fx1; x3g множества fx1; x2; x3g.
Таким образом, полином Жегалкина булевой функции n аргументов од-
нозначно определяется вектором своих коэффициентов = c0c1 : : : c2n 1, è наоборот, любой булев вектор длины 2n однозначно определяет полином
Жегалкина функции n аргументов. Пример. Полином Жегалкина
P= 1 x xz yz xyz = K0+ K4+ K5+ K3+ K7+ =
=1K0+ 0K1+ 0K2+ 1K3+ 1K4+ 1K5+ 0K6+ 1K7+
представляется вектором коэффициентов = 10011101.
Из последних рассуждений следует, что число различных полиномов Жегалкина булевых функций n аргументов равно числу различных булевых векторов длины 2n.
132
Теорема о единственности полинома Жегалкина. Каждая булева функция имеет единственный полином Жегалкина.
Доказательство. Как только что было замечено, число различных полиномов Жегалкина булевых функций n аргументов равно числу буле- вых векторов длины 2n, то есть равно 22n. Но количество различных бу- левых функций n аргументов тоже равно 22n (по теореме о числе булевых
функций), и каждая булева функция представима полиномом Жегалкина (по теореме о существовании полинома), следовательно, на каждую булеву функцию приходится ровно по одному полиному Жегалкина.
Таким образом, наряду с совершенной ДНФ, совершенной КНФ и сокращенной ДНФ, полином Жегалкина является еще одной канонической формой представления булевых функций.
15.3.2. Алгоритмы построения полинома Жегалкина
Рассмотрим алгоритмы построения полинома Жегалкина булевой функции, заданной различными способами, а именно: совершенной ДНФ, произвольной ДНФ, формулой и таблицей истинности.
Алгоритм построения полинома Жегалкина по СовДНФ (основан на доказательстве теоремы о существовании полинома Жегалкина).
Начало. Задана совершенная ДНФ функции f(x1; : : : ; xn).
Шаг 1. Заменяем каждый символ дизъюнкции на символ дизюнкции с исключением.
Шаг 2. Заменяем каждую переменную с инверсией x равносильной формулой x 1:
Шаг 3. Раскрываем скобки.
Шаг 4. Вычеркиваем из формулы пары одинаковых слагаемых. Конец. Получен полином Жегалкина функции f(x1; : : : ; xn).
Пример. Найдем полином Жегалкина мажоритарной булевой функции по ее совершенной ДНФ.
СовДНФ = x y z _ x y z _ x y z _ x y z = = x y z x y z x y z x y z =
= (1 x) y z x (1 y) z x y (1 z) x y z =
= y z x y z x z x y z x y x y z x y z = |
|||
|
|
|
|
|
|
|
|
= y z x z x y = P:
133
Алгоритм построения полинома Жегалкина по ДНФ (основан на равносильности K1 _ K2 = K1 K2 K1K2).
Начало. Задана произвольная ДНФ функции f(x1; : : : ; xn).
Шаг 1. Разбиваем ДНФ на пары конъюнкций, предпочтительно ортогональных (если число конъюнкций нечетно, одна из них остается без пары).
Шаг 2. Заменяем дизъюнкцию каждой пары конъюнкций K1 _ K2 ôîð- мулой K1 K2 K1K2 или формулой K1 K2, åñëè K1 è K2 ортогональны.
Шаг 3. В полученной формуле находим очередную дизъюнкцию A1 _A2 и заменяем ее формулой A1 A2 A1A2. Повторяем шаг 3 до тех пор, пока это возможно.
Шаг 4. Заменяем каждую переменную с инверсией x равносильной формулой x 1:
Шаг 5. Раскрываем скобки.
Шаг 6. Вычеркиваем из формулы пары одинаковых слагаемых. Конец. Получен полином Жегалкина функции f(x1; : : : ; xn).
Пример. Найдем полином Жегалкина мажоритарной функции по ДНФ. ДНФ = x y z _ x z _ y z = (x y z _ x z) _ y z =
= (x y z x z) _ y z = (x y z x z) y z (x y z x z) y z =
= x y |
|
x z y z x y z = x y (1 z) x z y z x y z = |
|
z |
|||
= x y x y z x z y z x y z = x y x z y z = P: |
|||
|
|
|
|
|
|
|
|
Отметим, что полиномы мажоритарной функции, полученные в двух последних примерах, совпадают с точностью до порядка конъюнкций, и это естественно (по теореме о единственности полинома Жегалкина).
Алгоритмы построения полинома Жегалкина по формуле.
Способ 1 основан на предварительном преобразовании формулы в ДНФ (любым известным нам способом). Затем ДНФ преобразуется в полином Жегалкина по только что изученному алгоритму.
Примеры. Получим полиномы Жегалкина двух элементарных булевых функций: импликации и эквивалентности, представив их предварительно кратчайшими ДНФ.
a ! b = a _ b = a b a b = (1 a) b (1 a)b =
|
|
|
= 1 a b b a b = 1 a a b; |
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
= |
|
|
|
_ |
|
= |
|
|
|
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
a |
|
b |
|
|
|
b |
|
a b |
|
|
|
b |
a b |
(1 |
a)(1 |
|
b) |
|
a b = |
|
|
a |
|
|
a |
|
|
||||||||||||
|
|
|
= 1 a b a b a b = 1 a b: |
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
134
Аналогично можно получить полиномы Жегалкина всех элементарных булевых функций (оставим читателю их вывод).
a _ b=a b a b |
a ! b=1 a a b |
|
a b=1 a b |
a |
b=1 b a b |
a # b=1 a b a b |
a ,! b=a a b |
|
a=b=1 a b |
a |
- b=b a b |
Константы 0 и 1, тождественная функция, а также конъюнкция a b и дизъюнкция с исключением a b уже являются полиномами Жегалкина. Полином Жегалкина инверсии a = 1 a.
Заметим, что некоторые из приведенных полиномов могут быть получе- ны гораздо проще, в частности,
a b = a b = 1 a b:
Способ 2. Если булева функций задана произвольной формулой, то ее полином Жегалкина можно получить подстановкой в формулу вместо элементарных булевых функций их полиномов.
Пример. Найдем полином Жегалкина мажоритарной функции, заданной формулой:
F = x y z = (x ! y) = ((x y) z) = (x ! y) =
[ подставим в формулу полином Жегалкина штриха Шеффера 1 ab ïðè a = (x y) z, b = x ! y ]
= 1 ((x y) z) (x ! y) =
[ подставим полиномы Жегалкина обратной импликации 1 b ab ïðè a = x y, b = z и импликации 1 a ab ïðè a = x, b = y ]
= 1 (1 z (x y) z) (1 x x y) =
[ подставим полином Жегалкина эквивалентности 1 x y, раскроем скобки, и вычеркнем появившиеся при этом пары одинаковых слагаемых ]
= 1 (1 z (1 x y) z) (1 x x y) = |
||||||||
= 1 (1 z z x z y z) (1 x x y) = |
||||||||
|
|
|
) |
|
|
|
|
|
= 1 (1 |
x z |
y z |
x |
x y) = |
||||
|
|
(1 |
|
|
= 1 1 x z y z x x z x y z x y x y z = |
||
|
|
|
136
Алгоритм построения полинома Жегалкина по таблице истинности (основан на методе неопределенных коэффициентов).
Продемонстрируем идею метода на примере произвольной булевой функции двух аргументов f(x; y). Представим ее полиномом Жегалкина в фор-
ме с коэффициентами
Pf = c0 c1y c2x c3xy:
Подставив в данное равенство наборы значений аргументов, получим систему из четырех линейных уравнений с четырьмя неизвестными коэффициентами: c0, c1, c2, c3.
f(0; 0)=c0 |
c10 c20 |
c3 |
00=c0 |
c1 |
f(0; 1)=c0 |
c11 c20 |
c3 |
01=c0 |
|
f(1; 0)=c0 |
c10 c21 |
c3 |
10=c0 |
c2 |
f(1; 1)=c0 |
c11 c21 |
c3 |
11=c0 |
c1 c2 c3 |
Заметим, что наборы подставлены в равенство в естественном порядке, и система имеет треугольный вид: в первом уравнении обратились в ноль все слагаемые, следующие за c0, во втором следующие за c1, и так далее.
Значит, коэффициент c0 можно получить из первого уравнения и подста- вить его в остальные. Тогда c1 можно получить из второго уравнения, и так далее.
В общем случае для функции n аргументов получается система треугольного вида из 2n линейных уравнений с 2n неизвестными коэффици-
ентами полинома Жегалкина.
Пример. Найдем полином Жегалкина мажоритарной булевой функции, заданной таблицей истинности, последовательно вычисляя коэффициенты полинома и подставляя их в остальные уравнения.
x y z f = c0 c1z c2y c3yz c4x c5xz c6xy c7xyz
0 0 0 0 |
= c0 |
c1 |
|
|
|
|
|
0 0 1 0 |
= 0 |
|
|
|
|
|
|
0 1 0 0 = 0 |
0 c2 |
|
|
|
|
||
0 1 1 1 = 0 |
0 0 c3 |
c4 |
|
|
|||
1 0 0 0 |
= 0 |
0 |
0 |
100 |
c5 |
|
|
1 0 1 1 |
= 0 |
0 |
0 |
101 |
0 |
c6 |
|
1 1 0 1 |
= 0 |
0 |
0 |
110 |
0 |
110 |
|
1 1 1 1 |
= 0 |
0 |
0 |
111 |
0 |
111 |
111 c7 |
Из первого уравнения следует, что c0 = 0. Из второго и третьего уравнений следует, что c1 = 0 è c2 = 0, значит, c1z è c2y тождественно равны нулю. Из четвертого уравнения получаем c3 = 1, значит, надо вычислять значения
138
f0(y1; : : : ; ym)= 0 1y1 : : : mym; f1(x1; : : : ; xn)= 01 11x1 : : : n1xn;
;
fm(x1; : : : ; xn)= 0m 1mx1 : : : nmxn:
Подставив эти полиномы в суперпозицию, получим:
f(x1; : : : ; xn) = 0 1f1(x1; : : : ; xn) : : : mfm(x1; : : : ; xn) =
=0 1( 01 11x1 : : : n1xn) : : :
:: : m( 0m 1mx1 : : : nmxn) =
=( 0 1 01 : : : m 0m)
( 1 11 : : : m 1m)x1 : : : ( 1 n1 : : : m nm)xn:
Поскольку в последней формуле каждая скобка есть булева константа, то получен линейный полином Жегалкина. Значит, функция f(x1; : : : ; xn) линейная, и класс L замкнут.
Лемма о нелинейной булевой функции. Если булева функция нелинейная, то из нее подстановкой вместо аргументов констант, переменных x, y, их инверсий x, y и, возможно, инверсией самой функции можно
получить конъюнкцию x y.
Доказательство. Рассмотрим полином Жегалкина нелинейной функции f(x1; : : : ; xn). Выберем в нем конъюнкцию K ранга больше единицы (такая конъюнкция существует, так как функция нелинейна). Не умаляя общности, можно считать, что K содержит переменные x1, x2. Разобьем множество конъюнкций полинома на четыре группы:
первую образуем из конъюнкций, содержащих x1 è x2,
вторую из конъюнкций, содержащих x1 и не содержащих x2,
третью из конъюнкций, содержащих x2 и не содержащих x1,
остальные конъюнкции отнесем к четвертой группе.
Âпервых трех группах вынесем за скобки соответственно x1x2, x1 è x2:
f(x1; : : : ; xn) = x1x2p(x3; : : : ; xn) x1q(x3; : : : ; xn)x2r(x3; : : : ; xn) s(x3; : : : ; xn):
Первая группа не пуста, так как есть по крайней мере одна конъюнкция K, содержащая x1 è x2. Значит, найдется набор a3 : : : an
p(a3; : : : ; an) = 1. Подставим его в функцию f(x1; : : : ; xn) (подстановка констант допустима по условию теоремы):
f(x1; x2; a3; : : : ; an) = x1x2 x1q(a3; : : : ; an) x2r(a3; : : : ; an)s(a3; : : : ; an) = x1x2 x1a x2b c;
ãäå a, b, c булевы константы.
139
Åñëè a = b = c = 0, конъюнкция получена. Иначе положим в последней формуле x1 = x b, è x2 = y a (подстановка переменных x, y и их инверсий x 1, y 1 допустима по условию теоремы), раскроем скобки и удалим пары одинаковых конъюнкций:
(x b)(y a) (x b)a (y a)b c =
= xy ax by ab ax ab by ab c =
= xy ab c = xy d = g(x; y):
Если булева константа d = 0, конъюнкция xy получена. Иначе функция g(x; y) = xy. Тогда, инвертировав исходную функцию (что допустимо по условию теоремы), получим конъюнкцию xy.
Пример. Рассмотрим нелинейную булеву функцию, заданную полиномом Жегалкина.
P = x1x2x3x4 x1x4 x1x2x3 x2x4 x1x3 x3x4 1 =
[ выберем первую конъюнкцию x1x2x3x4, в ней выберем переменные x1, x2 и сгруппируем конъюнкции ]
=x1x2(x3x4 x3) x1(x4 x3) x2x4 (x3x4 1)= p q r s
[ p(x3; x4) = 1 ïðè x3 = 1, x4 = 0, подставим эти значения переменных в формулу ]
= x1x2 x1(0 1) x20 (10 1)= x1x2 x1 1 = a b c
[положим x1 = x b = x, x2 = y a = y 1 ]
=x(y 1) x 1 = xy x x 1 = xy 1:
d
Инвертировав исходную функцию, получим конъюнкцию xy.
15.4. Класс самодвойственных булевых функций
Определение. Булева функция f(x1; : : : ; xn) самодвойственна (принадлежит классу S), если она равна двойственной себе функции, то есть
f(x1; : : : ; xn) = f (x1; : : : ; xn) = f(x1; : : : ; xn):
140
Примеры. Мажоритарная функция самодвойственна:
x y z f(x; y; z) f (x; y; z)
0 0 0 |
0 |
0 |
0 0 1 |
0 |
0 |
0 1 0 |
0 |
0 |
0 1 1 |
1 |
1 |
1 0 0 |
0 |
0 |
1 0 1 |
1 |
1 |
1 1 0 |
1 |
1 |
1 1 1 |
1 |
1 |
Из элементарных функций самодвойственными являются лишь тождественная функция и инверсия. Остальные функции, в частности, штрих Шеффера и стрелка Пирса, несамодвойственны.
Алгоритм распознавания самодвойственной функции, заданной таблицей истинности. Очевидно, что для проверки самодвойственности булевой функции можно не получать двойственную ей функцию в явном виде, а лишь сравнивать значения исходной функции на противоположных наборах. Функция самодвойственна, если и только если на противоположных наборах принимает противоположые значения.
Достаточное условие несамодвойственности булевой функции.
Если число единиц в столбце значений функции не совпадает с числом нулей, то функция не является самодвойственной.
Доказательство очевидно.
Примеры. Рассмотрим три булевы функции.
x y z f(x; y; z) g(x; y; z) h(x; y; z)
0 0 0 |
1 |
1 |
1 |
0 0 1 |
0 |
0 |
0 |
0 1 0 |
0 |
0 |
0 |
0 1 1 |
1 |
1 |
1 |
1 0 0 |
1 |
0 |
0 |
1 0 1 |
1 |
0 |
1 |
1 1 0 |
1 |
1 |
1 |
1 1 1 |
1 |
1 |
0 |