bulevy-funktsii-i-postr.-log.-skhem (Методические документы), страница 7

Для полных конъюнкций справедлива формула:f  x1,..., xn  52Ki  K j  Ki  K j  Ki  K j  Ki  K j .В заданной СДНФ заменяем каждый символ дизъюнкции на символ суммы по модулю 2, применяя к каждой паре конъюнкцийформулу Ki  K j  Ki  K j . Получим:f  x1,..., xn  x11  x2 2  ...  xn n .1,..., n  | f 1,..., n 1Покажем, что xi i  xi   i :если  i  0 , то xi i  xi0  xi  xi  1  xi   i ;если  i  1 , то xi i  x1i  xi  xi  0  xi   i .Теперь вместо каждой переменной xi i подставляем равносильную формулу xi   i :f  x1,..., xn   x1  1    x2   2   ...   xn   n  .1,..., n  | f 1 ,..., n 1Применяя законы коммутативности x1  x2  x2  x1 , ассоциативности, x1   x2  x3    x1  x2   x3  x1  x2  x3 и дистрибутивности x1  x2  x3   x1x2  x1x3 , раскрываем в полученном выражении скобки.

Получим сумму конъюнкций, которая ещё не является полиномом Жегалкина, так как может содержать парыодинаковых конъюнкций. Удаляем эти конъюнкции, используяравносильности x  x  0 и x  0  x . В результате получим полином Жегалкина функции f  x1, x2 ,..., xn  . Существование доказано.2. Докажем единственность представления. Подсчитаем число различных всевозможных монотонных конъюнкций от n переменных. Для этого составим таблицу 10.1, где каждой переменной соответствует единица, если она присутствует в монотонной конъюнкции и ноль в противном случае. Константе 1 втаблице поставим в соответствие набор нулей.Очевидно, что построенная таблица реализует взаимно однозначное отображение между множеством монотонных конъюнкций от n переменных и множеством n -разрядных двоичныхнаборов.

Так как количество n -разрядных двоичных наборов53равно 2n , то и монотонных конъюнкций от n переменных будет2n .x1  x2  x3  ...  xn…x1  x2…x11Таблица 10.1.x3 … xnx1x211…1…10…1…001…0…00…1………………0…00Построим аналогичное взаимно однозначное отображениемежду всевозможными суммами монотонных конъюнкций и векторами длины 2n - числа конъюнкций. Для этого составим таблицу 10.2, где под соответствующей монотонной конъюнкциейстоит единица, если она входит в данную сумму, и ноль, если невходит. При этом константе ноль ставится в соответствие нулевой набор.Таблица 10.2.x1x2 x3 ...xn  ...

 x1x2  ...  1x1x2 x3...xn … x1 x2 … x1 11…1…………x1x2  1… … …0…1……10…00……00… … …… 0 1… 0 0………1011Очевидно, что такое отображение взаимнооднозначное. Всего различных сумм будет столько, сколько существует различныхnдвоичных векторов длины 2n , то есть - 22 . Мы получили, что54число различных полиномов Жегалкина от n переменных совпадает с числом булевых функций.Так как каждой функции от n переменных соответствует полином и число функций равно числу полиномов, то каждойфункции будет соответствовать единственный полином Жегалкина.

Единственность доказана.□Приведём некоторые наиболее известные способы построения полинома Жегалкина.Построение полинома Жегалкина по СДНФ опирается наформулуf  x1,..., xn   x1  1    x2   2   ...   xn   n 1,..., n  | f 1 ,..., n 1и описано при доказательстве теоремы 10.1.Метод неопределённых коэффициентов. Записываем булевуфункцию в виде полинома Жегалкина с неопределёнными коэффициентами. Приравниваем значения функции к значениям полинома на соответствующих наборах переменных и, решая полученную систему, находим неизвестные коэффициенты.Нахождение полинома Жегалкина при помощи треугольникаПаскаля.Назначенияхисходнойфункциистроим треугольник Паскаля. Вf  x1, x2 ,..., xn    0 ,1,..., n2 1первой строке треугольника выписываем значения 0 ,1,...,2n 1исходной функции f.

Вторую строку получаем из первой, суммируя по модулю 2 соседние элементы первой строки (рис. 10.1).021 0  1….1   2…. 2n  2 2n 1 2n 2   2n 1Рис. 10.1. Построение строк треугольника Паскаля.Третью строку получаем из второй, суммируя по модулю 2 соседние элементы второй строки. Продолжая процесс, получимтреугольник Паскаля, левая сторона которого выделяется жир-55ным шрифтом, так как она определяет коэффициенты при монотонных конъюнкциях полинома Жегалкина.Чтобы по треугольнику Паскаля построить полином Жегалкина, нужно каждой строке треугольника поставить в соответствие монотонную конъюнкцию полинома. Для этого, двигаясьпо строкам треугольника сверху вниз, ставим в соответствиекаждой строке двоичный набор из таблицы истинности.

Наборывыписываем в порядке возрастания их номеров. При доказательстве теоремы 10.1 было построено взаимно однозначное соответствие между множеством монотонных конъюнкций от n переменных и множеством n -разрядных двоичных наборов. Используя это соответствие, по единицам, входящим в двоичные наборы, составляем монотонные конъюнкции полинома. В полиномЖегалкина входят только те конъюнкции, коэффициенты которых равны 1 на левой стороне треугольника Паскаля.Пример 10.1. Для функции f  x, y, z   1110 1010 найти полином Жегалкина тремя способами. Построить логическую схему, реализующую полином Жегалкина функции f  x, y, z  , припомощи вентилей «И», «М2» и константы 1, которая считаетсяданной.Решение. Составим таблицу функции:xyzf00010011010101101001101011011110Способ 1.

Найдём полином Жегалкина данной функции, исходя из формулы:f  x, y , z  x  a y b z c   a,b,c  | f  a,b,c 156  x  a  y  b  z  c   0,0,0  0,0,1 0,1,0 1,0,0 1,1,0   x  0  y  0  z  0    x  0  y  0  z  1    x  0  y  1  z  0    x  1  y  0  z  0    x  1  y  1  z  0    x  1 y  1 z  1   x  1 y  1 z  0    x  1 y  0  z  1   x  0 y  1 z  1   x  0 y  0 z  1   x  1 y  1 z  1   x  1 y  1 z   x  1 y  z  1  x  y  1 z  1  xy  z  1   x  1 y  1 z  1  z    x  1 y  z  1  x  z  1 y  1  y    x  1 y  1   x  1 y  z  1  x  z  1  xy  x  y  1   x  1 yz  y   xz  x  xy  x  y  1  xyz  xy  yz  y  xz  x  1  xz  yz  xyzИтак, f  x, y, z   1  xz  yz  xyz .Способ 2.

Применим метод неопределённых коэффициентов.Будем искать полином для данной функции в виде:f  x, y, z   a0  a1x  a2 y  a3 z  a4 xy  a5 xz  a6 yz  a7 xyz .В данное соотношение, используя таблицу функции, будемподставлять наборы значений переменных и значения функции:f  0,0,0  1  a0  a1  0  a2  0  a3  0  a4  0  a5  0  a6  0  a7  0или a0  1 ;f  0,0,1  1  a0  a3 1 или a0  a3  1;f  0,1,0  1  a0  a2 1 или a0  a2  1;f  0,1,1  0  a0  a2 1  a3 1  a6 1 или a0  a2  a3  a6  0 ;f 1,0,0  1  a0  a1 1 или a0  a1  1;57f 1,0,1  0  a0  a1 1  a3 1  a5 1 или a0  a1  a3  a5  0 ;f 1,1,0  1  a0  a1 1  a2 1  a4 1 или a0  a1  a2  a4  1 ;f 1,1,1  0  a0  a1 1  a2 1  a3 1  a4 1  a5 1  a6 1  a7 1или a0  a1  a2  a3  a4  a5  a6  a7  0 .Составляем и решаем систему:a0  1,a0  1,a  a  1,a  0,03 1a0  a2  1,a2  0,a0  a2  a3  a6  0,a3  0,aa1,1 0a4  0,a0  a1  a3  a5  0,a5  1,a0  a1  a2  a4  1,a6  1,a  a  a  a  a  a  a  a  0,a  1. 71234567 0Подставляя найденные коэффициенты в выражениеf  x, y, z   a0  a1x  a2 y  a3 z  a4 xy  a5 xz  a6 yz  a7 xyzполучим, чтоf  x, y, z   1  0  x  0  y  0  z  0  xy  1 xz  1 yz  1 xyz  1  xz  yz  xyz .Полином Жегалкина имеет вид: f  x, y, z   1  xz  yz  xyz .Способ 3.

Строим треугольник Паскаля (табл. 10.3).Полином Жегалкина функции f будет состоять из четырёхслагаемых, т.к. левая сторона треугольника Паскаля содержит четыре единицы. Первой единице соответствует набор (000) и монотонная конъюнкция 1; второй единице соответствует набор(011) и монотонная конъюнкция yz; третьей единице соответствует набор (101) и монотонная конъюнкция xz; четвёртой единицесоответствует набор (111) и монотонная конъюнкция xyz.Полином Жегалкина имеет вид: f  x, y, z   1  yz  xz  xyz .58Таблица 10.3.Монотонные Двоичные наборыконъюнкции(xyz)1(000)z(001)y(010)yz(011)x(100)xz(101)xy(110)xyz(111)Треугольник Паскаля111010100011111010000110000100110011Логическая схема, реализующая полином Жегалкина функции f  x, y, z  при помощи вентилей «И», «М2» и заданной константы 1, показана на рис.

10.2.1 zу x&&М2&1 ярус2 ярусРис. 10.2. Логическая схема, реализующая полиномЖегалкина функции.Задержка логической схемы (рис.10.2) - T  2 , цена поКвайну - SQ=11.5911. Замкнутые классыПусть A   f1, f 2 ,...  P2 - система булевых функций.Определение 11.1. Множество всех булевых функций, которые можно выразить формулами над A , называется замыканиемсистемы A и обозначается  A .Имеют место следующие свойства:1) A   A ;2) A1  A2   A1    A2 , причём, если в левой части импликации строгое вложение, то из него вовсе не следует строгоевложение в правой части;3)  A   A .Определение 11.2.

Система A называется замкнутым классом, если замыкание системы A совпадает с самой системой A ,т.е.  A  A .11.1. Класс функций, сохраняющих константу 0Класс функций, сохраняющих константу 0, определяетсяследующим образом:T0   f  x1,..., xn   P2 | f  0,...,0   0 .Классу T0 принадлежат, например, функции 0, x , x  y , x  y ,x  y . Классу T0 не принадлежат функции 1, x , x  y , x | y ,x  y, x  y.11.2. Класс функций, сохраняющих константу 1Определим класс функций, сохраняющих константу 1:T1   f  x1,..., xn   P2 | f 1,...,1  1 .Классу T1 принадлежат, например, функции 1, x , x  y , x  y ,x  y , x  y .