Розглянемо технологію побудови поліному Жегалкіна від заданої булевої функції за допомогою еквівалентних перетворень диз'юнктивної нормальної форми (ДНФ).

У порівнянні з диз'юнктивною нормальною формою, у поліномі Жегалкіна відсутні операції АБО та НЕ.

Поліном Жегалкіна можна отримати з диз'юнктивної нормальної форми, представивши операції АБО та НЕ через операції кон’юнкції, додавання за модулем 2 і константу 1 за допомогою наступних співвідношень:

 

A v B = A Å B Å AB

/A = A Å 1

Приклад 5.

Перетворити диз'юнктивну нормальну форму виду XY v XY на поліном Жегалкіна.

Розв'язок завдання прикладу 5:

У процесі перетворень було використано наступні основні співвідношення алгебри Жегалкіна:

(A Å B ) C = AC Å BC

A Å A = 0

 

Розглянемо технологію побудови поліному Жегалкіна від заданої булевої функції за допомогою еквівалентних перетворень досконалої диз'юнктивної нормальної форми (ДДНФ).

ДДНФ має ту властивість, що, при будь-яких значеннях вхідних змінних, на одиницю звертається не більше одного елементу булевого виразу.

Для таких виразів, операція диз'юнкції є еквівалентною операції виключного АБО.

При перетворенні ДДНФ на поліном Жегалкіна, досить замінити всі диз'юнкції на операції виключного АБО, позбавляючися від інверсій за допомогою еквівалентного перетворення /A = A Å 1.

 

КОНТРОЛЬНІ ПИТАННЯ

1. Сформулювати поняття елементарної кон'юнкції.

2. Дати визначення диз'юнктивної нормальної форми (ДНФ).

3. Що називають правильною елементарною кон’юнкцією ?

4. Чим вирізняється повна правильна елементарна кон'юнкція ?

5. Пояснити поняття досконалої диз'юнктивної нормальної форми (ДДНФ).

6. Чи є справедливим твердження, що будь-яку булеву функцію f(x1, x2, ..., xn), яка тотожно не дорівнює нулю, можна подати за допомогою досконалої диз'юнктивної нормальної форми ?

7. Що розуміють під елементарною диз'юнкцією ?

8. Пояснити поняття кон’юнктивної нормальної форми (КНФ).

9. Які особливості має правильна елементарна диз'юнкція ?

10. Що означає поняття повної правильної елементарної диз'юнкції ?

11. Чим характеризується досконала кон’юнктивна нормальна форма ?

12. Чи можна будь-яку функцію f(x1, x2, ..., xn), яка є відмінною від тотожно дійсної, представити досконалою кон’юнктивною нормальною формою (ДКНФ) ?

13. Пояснити сутьтеореми про розкладання булевої функції по змінній.

14. Розкрити поняття залишкових функцій.

15. Охарактеризувати методи знаходження для булевих функцій, які задані аналітично, досконалих диз’юнктивних нормальних форм (ДДНФ) і досконалих кон’юнктивних нормальних форм (ДКНФ).

16. Сформулювати методи знаходження для булевих функцій, які задані таблично, досконалих диз’юнктивних нормальних форм (ДДНФ) і досконалих кон’юнктивних нормальних форм (ДКНФ).

17. Сформулювати поняття алгебри Жегалкіна.

18. Назвати основні тотожності (властивості) алгебри Жегалкіна.

19. Чи можна на основі операцій алгебри Жегалкіна представити всі інші булеві функції ?

20. Дати визначення поняттю поліному Жегалкіна.

21. Коли поліном Жегалкіна називають лінійним поліномом ?

22. Чи можна будь-яку булеву функцію представити у вигляді поліному Жегалкіна єдиним образом ?

23. Назвати основні методи побудови поліному Жегалкина для заданої булевої функції.

24. Пояснити суть технології побудови поліному Жегалкина для заданої булевої функції методом трикутника.

25. У чому полягає технологія побудови поліному Жегалкіна від заданої булевої функції за допомогою еквівалентних перетворень диз'юнктивної нормальної форми (ДНФ) ?

26. Які особливості має технологія побудови поліному Жегалкіна від заданої булевої функції за допомогою еквівалентних перетворень досконалої диз'юнктивної нормальної форми (ДДНФ) ?