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


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

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

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

а) Ø х = х Å1,

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

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

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

Ú (К1 , ... , Кр ) = К1Å ... Å Кр ,

Ø ¯ ( К1 , ... , Кр ) = К1Å ... Å Кр .

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

а) х Å х = 0.

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

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

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

К 1= `x `y z, К 2= `x y z , К 3= x y`z.

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

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

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

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

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

К3 = 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;

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

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

г) x Å х = 0.

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

а)Ú (К1 , ... , Кр ) = К1Å ... Å Кр ;

б) Ø ¯ ( К1 , ... , Кр ) = К1Å ... Å Кр .

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

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

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

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

 



Дата добавления: 2020-10-14; просмотров: 429;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.009 сек.