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

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

Поліном Жегалкіна можна отримати з диз'юнктивної нормальної форми, представивши операції АБО та НЕ через операції кон’юнкції, додавання за модулем 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. Які особливості має технологія побудови поліному Жегалкіна від заданої булевої функції за допомогою еквівалентних перетворень досконалої диз'юнктивної нормальної форми (ДДНФ)?