Метод построения полинома Жегалкина по СДНФ (СВНФ)

Для построения полинома для заданной булевой функции f(хⁿ). выполняют следующие действия.

1. Вначале строят СДНФ (СВНФ) функции f(`хⁿ), в которых используется базисный набор {Ø,&,Ú} ({Ø , ¯ }).

2. Преобразуются внутренние функции построенной формы. С использованием эквивалентных преобразований

а) Ø х = х Å1,

б) х ¯ у = 1Å хÅ у Å ху,

осуществляется переход к базису {0, 1, &, Å}во всех внутренних функциях формы.

3. Заменяется внешняя функция формы. СДНФ и СВНФ представляют собой суммы конституент единицы, которые никогда не принимают значение 1 на одинаковых наборах. Поэтому для соединения данных конституент вместо эквивалентного правила x Ú y = х Å у Å ху и вышеприведенной для функции Вебба формулы б) можно использовать неэквивалентные в общем случае правила замены:

Ú (К₁ , ... , К_р ) = К₁Å ... Å К_р ,

Ø ¯ ( К₁ , ... , К_р ) = К₁Å ... Å К_р .

4. После раскрытия скобок в произведениях, получаемых во внутренних функциях, их общая сумма упрощается путем устранения из нее парных слагаемых. При этом используется эквивалентное преобразование:

а) х Å х = 0.

5. Полученная в итоге сумма произведений над множеством переменных Х=(х₁, ... , х_n)является искомым полиномом Жегалкина функции f(`хⁿ).

Пример 6. Построить полином Жегалкина для функции f = (01010010)из Примера 1 с использованием ее СДНФ.

Решение. Внутренние конъюнкции элементарных наборов и СДНФ будут следующие:

К ₁= `x `y z, К ₂= `x y z , К <sub>3</sub>= x y`z.

СДНФ имеет вид:

f =`x `y z Ú`x y z Ú x y`z = Ú (`x `y z , x y z, x y`z).

Преобразуем внутренние конъюнкции, выполняя замену Ø х = х Å1 и раскрывая скобки в произведениях:

К₁= (x Å1)(y Å1) z = (ху Å х Å у Å 1) z = х у z Å х z Å у z Å z,

К₂= (x Å1) y z = х у z Å у z ,

К₃ = x y (z Å1) = х у z Å х у .

Заменяя внешнюю функцию логического сложения конституент единицы сложением по модулю 2, получим сумму произведений следующего вида:

f = х у z Å х z Å у z Å z Å х у z Å у zÅ х у z Å х у .

Устраняя из нее парные слагаемые по правилу х Å х = 0, получим в итоге искомый полином Жегалкина:

f = z Å х у Å х z Å х у z.

Замечание. Булевы функции могут быть разложены в полином Жегалкина, в отличие от нормальных форм, единственным способом. Это несложно доказать от противного.

ЗАДАЧИ

1. Привести пример задания одной и той же булевой функции при помощи двух различных ДНФ.

2. Построить СДНФ и СВНФ следующих функций:

а) ((х® у)® z)&х; б) (х½ у) Å z; в) Ø(ху® уz);г) (01101000); д) (1001101000001001); е) (0001001001010001) ; ж) (0100101000101001).

3. Построить СКНФ и СШНФ следующих функций:

а) ((хÚ у)® z);б) (х¯у)Å z; в) (ху ® уz); г) (11101001);д) (0111101011101101) ; е) (1011001101110111) ; ж) (1100110001011111).

4. Доказать эквивалентность в общем случае правил:

а)Ø х = х Å 1;

б) х ¯ у = 1Å хÅ у Å х у;

в) x Ú y = х Å у Å х у;

г) x Å х = 0.

5. Доказать справедливость для конституент К₁ , ... , К_р СДНФ и СВНФ правил замены:

а)Ú (К₁ , ... , К_р ) = К₁Å ... Å К_р ;

б) Ø ¯ ( К₁ , ... , К_р ) = К₁Å ... Å К_р .

6. Построить методом неопределенных коэффициентов полиномы Жегалкина следующих функций: а)`х½у Å z;б)( х º у )® (`у ®`х);в)(хÚ у)Å (х® у);г)(х¯у х)® х у ;д) х ®(у ® z) ; е)(х½у)Å (х® z); ж)(х º у)® (х º z).

7. Построить при помощи СДНФ полиномы Жегалкина функций 6а) — ж).

8. Построить при помощи СВНФ полином Жегалкина функций 6 а) —ж).

9. Доказать единственность разложения булевых функций в полином Жегалкина.