Досконала діз’юнктівная нормальна форма - студопедія

Вираз (3.2) записано з використанням операцій логічного додавання (диз'юнкції), логічного множення (кон'юнкції) і логічного заперечення (інверсії), які виконують найпростіші логічні елементи АБО, І та НЕ відповідно. Для кожного одиничного набору складається логічне твір вхідних змінних, в яке змінна входить з інверсією при нульовому її значенні на даному наборі. Ці логічні твори об'єднуються потім знаком логічного додавання (+ або Ú ).

На рис. 3.2 представлені таблиці істинності і умовні графічні позначення двухвходових логічних елементів. Крім зазначених вище, на практиці широко використовуються елементи І-НЕ, АБО-НЕ, виключає Або. Логічна функція останнього (функція «нерівнозначності» або сума по модулю два) в СДНФ записується у вигляді

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

Кожна кон'юнкція цієї диз'юнкції включає кожну змінну тільки один раз в прямому або інверсному вигляді, звертаючись в одиницю при певному наборі значень змінних, і носить назву минтерм.

Правило переходу від табличного завдання логічної функції до її запису в СДНФ (правило записи логічного функції по одиницях) полягає в наступному:

1. Скласти минтермов для рядків таблиці істинності, на яких функція F дорівнює 1. Якщо значення змінної в цьому рядку дорівнює 0, то в минтермов записується заперечення цієї змінної.

2. Записати диз'юнкцію складених минтермов, яка представлятиме Переключательная функцію в СДНФ.