Досконала диз'юнктивна нормальна форма (дднф). Теорема про існування дднф логічної функції. Доведення. Алгоритм одержання конституенти одиниці та дднф. Приклад

Доскона́лою диз'юнкти́вною норма́льною фо́рмою (ДДНФ) булевої функції називається диз'юнкція тих конституент одиниці, які перетворюються в одиницю на тих самих наборах змінних, що й задана функція. ДДНФ повинна задовольняти наступним умовам:

· в ній немає однакових доданків;

· жоден із доданків не містить двох однакових співмножників;

· жоден із доданків не містить змінну разом із її запереченням;

· в кожному окремому доданку є як співмножник або змінна x_i, або її заперечення для будь-якого i = 1, 2, …, n.

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

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

В комірках результату відмічаються лишень ті комбінації, які приводять логічний вираз до одиниці.
Далі розглядається значення змінних при яких функція дорівнює 1. Якщо значення змінної дорівнює 0, то вона записується з інверсією. Якщо значення змінної дорівнює 1, то вона записується без інверсії. Перший стовпець містить 1 в заданому полі. Відмічаються значення всіх чотирьох змінних це:

· = 0

· = 0

· = 0

· = 0

Нульові значення — тут всі змінні представлені нулями — записуються в кінцевому виразі інверсією цієї змінної. Перший член ДДНФ даної функції має такий вигляд:
Змінні другого члена:

· = 0

· = 0

· = 0

· = 1

в цьому випадку буде представлений без інверсії:

Таким чином аналізуються всі комірки . ДДНФ цієї функції буде диз'юнкцією всіх отриманих членів (елементарних кон'юнкцій).

Досконала ДНФ цієї функції:

 

 

 

Поняття імпліканти і простої імпліканти. Основні теореми - властивості імпліканти. Доведення. Приклади.

 

Поняття скороченої ДНФ. Операції, які застосовуються при отриманні скороченої ДНФ, їх логічний запис та доведення. Приклад.

Операції повного і неповного склеювання в ДНФ, операція поглинання і розгорнення. Приклади. Доведення.

Теорема Квайна для ДДНФ. Доведення. Особливості застосування.

Алгоритм мінімізації ДДНФ за Квайном. Приклад.

27. Імплікантні матриці для одержання мінімальної ДНФ. Тупікові і мінімальні ДНФ. Приклад.

28. Поняття про кон'юнктивну нормальну форму (КНФ). Елементарна сума. Конституента нуля. Основні теореми для констигуенти нуля і її наслідки.

 

29. Досконала кон'юнктивна нормальна форма (ДКНФ). Теорема про існування ДКНФ логічної функції. Доведення. Алгоритм одержання конституенти нуля і ДКНФ. Приклади.

 

 

30. Поняття імпліценти і простої імпліценти. Основні теореми - властивості імпліценти. Доведення. Приклади.

 

 

31. Поняття скороченої КНФ. Операції, які застосовуються при отриманні скороченої КНФ, їх логічний запис та доведення. Приклад.

 

 

32. Операції повного і неповного склеювання в КНФ. Операції поглинання і розгорнення. Приклади. Доведення.

 

 

 

33. Теорема Квайна для ДКНФ. Доведення. Особливості застосування.

Теорема Квайнадля ДКНФ. Якщо в ДКНФ логічної функції F виконати всі операції неповного склеювання, а потім усі операції поглинання, то отримаємо скорочену КНФ цієї функції, тобто конюнкцію всіх її простих імпліцент.

Доведення. Припустимо, що після виконання всіх операцій неповного склеювання, а потім поглинання отримана ДНФ буде містити у вигляді кон'юнкції член q, який не є простою імплікантою. Тоді до цієї функції, крім члена q, самостійно входить також у вигляді кон'юнкції якась його частина р, яка є простою імплікантою. Це означає,що функція F буде містити імпліканту q і просту імпліканту р увигляді їх диз'юнкції р\/q. Але q = р. Тоді член q згідно з рівністю р\/q= р\/ р = р поглинатиметься простою імплікантою р, і, відповідно, ДНФ буде містити лише цю імпліканту. Отже, ця ДНФ складатиметься лише з простих імплікант, об'єднаних операціями диз'юнкції, тобто наше вихідне припущення не правильне, і вона буде надана у вигляді скороченоїДНФ.

Особливості

Для мінімізації логічної функції Р, поданої в КНФ, з допомогою теореми Квайна її спочатку треба перетворити на ДКНФ.

 

34. Алгоритм мінімізації ДКНФ за Квайном. Приклад.