Елементарна кон’юнкція, КНФ, ДКНФ. Теореми. Зведення формули до КНФ, ДКНФ.

Означення:
Елементарною кон’юнкцією від змінних  називається кон’юнкція деяких із змінних  або їх заперечень.Формулу, яка зображає елементарну кон’юнкцію будемо позначати  .

Означення:
Кон’юнктивною нормальною формою (КНФ) називається кон’юнкція елементарних диз’юнкцій (у виродженому випадку це може бути одна диз’юнкція), тобто вираз вигляду

,

де всі  ,  , – елементарні диз’юнкції (не обов’язково різні).

Досконалою кон'юнктивною нормальною формою (ДКНФ) деякої формули називається така її КНФ, яка задовольняє таким умовам:

1) у ній немає двох однакових кон'юнктів;

2) жоден кон'юнкт немає двох однакових диз’юнктів (А Ú В Ú А);

3) жоден кон'юнкт немає змінної і її заперечення (А Ú В Ú`А);

У кожному кон'юнкті наявні всі змінні, що входять до складу вихідної формули.

Теорема:

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

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