Досконала кон’юнктивна нормальна форма

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

Отже, СДНФ будується за одиничними наборами. А що потрібно зробити, щоб нулі у графі функції перетворити на одиниці? Очевидно, треба досліджувати не функціюy, а інверсну, наведену в табл. 13.

Таблиця 13
№cbаy

Табл. 13 отримано з табл. 12 додаванням графи , в якій вміщені значення, інверсні по відношенню до значень функціїy(інверсні значення виходять заміною 0 на 1 та 1 на 0).

За правилами, викладеними вище, складемо досконалу диз'юнктивну нормальну форму для інверсної функції

= = 1.

Візьмемо заперечення отриманої формули і перетворимо її, використовуючи закони булевої алгебри:

Зауваження: 0 зазвичай не пишеться, але завжди мається на увазі.

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

Диз'юнкції, що входять до СКНФ, називаютьсямакстермамиабоконституентами нуля. Поняття «макстерм» та «конституента нуля» будуть пояснені нижче.

Отримана форма називається

досконалої, оскільки всі диз'юнкції містять усі змінні (з запереченням чи беззаперечення);

кон'юнктивною, тому що формула є кон'юнкцією диз'юнкцій;

нормальною, оскільки всі диз'юнкції є елементарними.

Якщо диз'юнкцію входять лише змінні чи його заперечення, вона називаєтьсяелементарной. Число змінних у диз'юнкції називається їїрангом. У разі ранг диз'юнкцій дорівнює 3.

Проведемо аналіз формули, що представляє СКНФ.

Функціяyдорівнює 0, якщо хоча б одна диз'юнкція (вираз у парі дужок) дорівнює 0.

Перша диз'юнкція дорівнюватиме 0 тільки тоді, колиa= 0,b= 0,c= 0, що відповідає нульовому набору змінних . (Згадаймо, якщоa= 0, то пишемо). Рівність нуля перевіряється підстановкою відповідних значень змінних.

Друга диз'юнкція дорівнюватиме 0 тільки тоді, колиa= 1,b= 0,c= 0, що відповідає першому набору .

Третя диз'юнкція дорівнюватиме 0 тільки тоді, колиa= 0,b= 1,c= 0, що відповідає другому набору .

Четверта диз'юнкція дорівнюватиме 0 тільки тоді, колиa= 0,b= 0,c= 1, що відповідає четвертому набору .

Таким чином, кожна диз'юнкція відповідає своєму набору змінних, на якому функціяyдорівнює 0.

На основі одержаних результатів можна сформулювати такі правила складання СКНФ.