Визначення 4. Елементарної діз'юнкціейn змінних називається диз'юнкція змінних або їх заперечень.
Визначення 5. кон'юнктивний нормальною формою (КНФ) формули А називається рівносильна їй формула, що представляє собою кон'юнкцію елементарних диз'юнкцій.
Визначення 6. Зробленої кон'юнктивній нормальній формули А (СКНФ А) називається КНФ А. задовольняє таким умовам:
1. всі елементарні диз'юнкції, що входять до КНФ А. містять всі змінні;
2. всі елементарні диз'юнкції, що входять до КНФ А. різні;
3. кожна елементарна диз'юнкція, що входить в КНФ А. містить змінну один раз;
4. жодна елементарна диз'юнкція, що входить в КНФ А. не містить змінного с ую і її заперечення.
СКНФ А можна отримати двома способами:
а) за допомогою таблиці істинності (використовуючи закон подвійності) (див. 5.1);
б) за допомогою рівносильних перетворень.
Правило отримання СКНФ з формули А за допомогою рівносильних перетворень.
1. Для формули А отримуємо будь-яку КНФ А.
2. З КНФ А шляхом рівносильних перетворень отримуємо СКНФ А. послідовно домагаючись виконання чотирьох властивостей СКНФ А.
1) Якщо елементарна диз'юнкція В, що входить в КНФ А. не містить змінну. тоді замінюємо В на.
2) Якщо в деяку елементарну диз'юнкцію В змінна входить двічі, то зайву змінну потрібно відкинути, так як.
3) Якщо КНФ А містить дві однакових елементарних диз'юнкцій, то одну можна відкинути, так як.
4) Якщо в елементарну диз'юнкцію входить пара. то її можна відкинути так як. а справжнє висловлювання з кон'юнкції можна викинути (в силу равносильности).
Приклад 1. Для формули знайти СДНФ і СКНФ, кожну двома способами.