Кон'юнктивні нормальні форми

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

Нехай, як і раніше, зафіксовано множинуХ={х₁, х₂,..., х_п). Елемен­тарною диз'юнкцією називають вираз , уякому всі х_ijрізні. Числоrназивають рангом диз'юнкції. У разіr=0 диз'юнкцію називають порожньою і вважають рівною 0. Приклади елементарних диз'юнкцій: .

Кон'юнктивною нормальною формою (КНФ) називають кон'юнк­цію d ₁∧ d₂∧ …∧ d_s елементарних диз'юнкцій d_j(J=1, 2, …, S), у якій всі d_j різні.

Є алгоритм, який дає можливість для будь-якої формули булевої алгебри знайти рівну їй КНФ. Перший етап цього алгоритму такий же, як і для ДНФ. На другому етапі досягають, щоб усі диз'юнкції виконувались раніше кон'юнкцій. Для цього потрібно скористатись дистрибутивним законом або його наслідком (див. приклад 8.6 б). Далі, на основі спів­відношень для констант і закону виключеного третього позбуваються одиниць та за законами ідемпотентності об'єднують рівні члени.

Приклад 8.14. Знайдемо КНФ для формули . Вико­ристовуючи сформульований алгоритм, одержимо

.▲

Елементарну диз'юнкцію рангу п називають конституентою нуля. Іншими словами, конституента нуля - це елементарна диз'юнк­ція, у яку входять всі змінні з множини X.

Кожному двійковому набору взаємно однознач­но відповідає конституента нуля , яка перетворю­ється на ньому в 0. Усі інші констшуенти нуля на цьому наборі пере­творюються в 1. Наприклад, набору 0111 відповідає конституента нуляx₁∨ х₂∨ x₃∨ х₄.

Досконалою кон'юнктивною нормальною формою (ДКНФ) нази­вають КНФ, у якої кожна елементарна диз'юнкція d_j(j= 1,..., s) є конституентою нуля.

Покажемо, що кожну булеву функцію f (x ₁, …, х_п) можна зобра­зити досконалою кон'юнкгивною нормальною формою. Для цього запишемо ДДНФ f * (зазначимо, щоf^*≠ 0).

^{f* (τ 1, …, τ n )}

Візьмемо тотожність для двох формул

Ліва частина дорівнює , а праву перетворюємо далі

Отже,

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

Приклад 8.15. Побудуємо ДКНФ функції, заданої табл. 8.5. Функція приймає значення 0 на наборах 01 та 10. Отже

.▲

Зазначимо, що на основі тотожних перетворень будь-яку КНФ можна перетворити у ДКНФ. Якщо в деяку елементарну диз'юнкціюdне входить змінна х, то потрібно записати рівносильний вираз і скористатись дистрибутивним законом: . Після тривіальних перетворень отримаємо ДКНФ.

Приклад 8.16. Перетворимо КНФу досконалу КНФ. Використовуючи розщеплення диз'юнкцій, можемо записати

.▲

Зазначимо, що досконала КНФ єдина.