Означення.Елементарною кон’юнкцією від змінних називається кон’юнкція деяких із зміннихабо їх заперечень.Формулу, яка зображає елементарну кон’юнкцію будемо позначати .
Приклад. Нехай задані змінні . Елементарними кон’юнкціями від них будуть, наприклад, такі:
; ; .
Вирази , не є елементарними кон’юнкціями: в першому виразі є спільне заперечення, а в другому є знак .
Означення.Диз’юнктивною нормальною формою (ДНФ) називається диз’юнкція елементарних кон’юнкцій (у виродженому випадку це може бути одна кон’юнкція), тобто вираз вигляду
,
де всі , – елементарні кон’юнкції (не обов’язково різні).
ПрикладДНФ..
Означення.Елементарна кон’юнкція від змінних називається повною, якщо до неї від кожної пари , , входить тільки одна змінна.
Приклад. Утворимо всі повні елементарні кон’юнкції від змінних :
, ,
, ,
, ,
, .
Двоїстим чином, тобто з використанням принципу двоїстості, визначається поняття кон’юктивної нормальної форми.
Означення.Елементарною диз’юнкцією від змінних називається диз’юнкція деяких із зміннихабо їх заперечень. Формулу, яка зображає елементарну диз’юнкцію будемо позначати .
Приклад. Нехай задані змінні . Елементарними диз’юнкціями від них будуть, наприклад, такі:
; ; .
Означення.Кон’юнктивною нормальною формою (КНФ) називається кон’юнкція елементарних диз’юнкцій (у виродженому випадку це може бути одна диз’юнкція), тобто вираз вигляду
,
де всі , , – елементарні диз’юнкції (не обов’язково різні).
Означення.Елементарна диз’юнкція від змінних називається повною, якщо до неї від кожної пари , входить тільки одна змінна.
Приклад. Утворимо всі повні елементарні диз’юнкції від змінних :
, ,
, ,
, ,
, .
ПрикладКНФ. .
Теорема.Для кожної формули, що реалізує булеву функцію, існує рівносильна їй диз'юнктивна нормальна форма (ДНФ) і кон'юнктивна нормальна форма (КНФ).
Доведення теореми полягає просто у наведенні алгоритмів знаходження для будь-якої формули рівносильних їй ДНФ і КНФ. Процес знаходження цих форм називається приведенням формули відповідно до ДНФ і КНФ.