Приведення булевих функцій до досконалих диз’юнктивних і кон’юнктивних нормальних форм

Існує два способи приведення булевих функцій до досконалих нормальних форм, які випливають з двох способів задання булевих функцій: за допомогою таблиці істинності або за допомогою формули.

Якщо булева функція задана таблицею, то мають місце формули, які дають зображення булевої функції досконалою диз’юнктивною або кон’юнктивною нормальною формою.

Теорема (про зображення булевих функцій досконалими нормальнимиформами).

1. Будь-яку булеву функцію, відмінну від константи нуль: (), можна єдиним чином з точністю до перестановки диз’юнктивних доданків зобразити ДДН формою:

, де

2. Будь-яку булеву функцію, відмінну від константи одиниця (), можна єдиним чином з точністю до перестановки кон’юнктивних доданків зобразити ДКН формою:

, де

Наслідок. Будь-яка булева функція може бути зображена у вигляді формули через .

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

З теореми випливає

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Досконалі диз’юнктивна і кон’юнктивна нормальні форми	\|	Алгоритм знаходження ДДНФ (ДКНФ) для даної булевої функції

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.