Елементарної кон'юнкціейn змінних називається кон'юнкція змінних або їх заперечень.
Елементарна кон'юнкція n змінних може бути записана у вигляді:
Диз'юнктивній нормальною формою (ДНФ) формули А називається рівносильна їй формула, що представляє собою диз'юнкцію елементарних кон'юнкція.
Для будь-якої формули алгебри логіки шляхом рівносильних перетворень можна отримати її ДНФ, причому не єдину.
Наприклад, для формули A º х (Х ®у) маємо
Очевидно, що 1-я ДНФ не задовольняє одному з властивостей (С), а саме 3-му властивості. 2-я ДНФ задовольняє всім властивостям (С).
Серед численних ДНФ A існує єдина ДНФ A. для якої виконуються перераховані вище чотири властивості досконалості (властивості (С)).
Така ДНФ A називається досконалою диз'юнктивній нормальною формою формули A (СДНФ A), тобто це така ДНФ, для якої виконуються властивості досконалості.
Як уже зазначалося, СДНФ будь-якої формули A може бути отримана за допомогою таблиці істинності. Продемонструємо це на прикладі вищенаведеної формули х (Х ®у) (табл. 6, 10).
Таблиця істинності для формули х (Х ®у)
Так як 1 є тільки для одного набору (1, 1), то СДНФ матиме тільки один доданок, а саме x y.
Елементарної діз'юнкціейn змінних називається диз'юнкція змінних або їх заперечень.
Елементарна диз'юнкція n змінних може бути записана у вигляді
Кон'юнктівной нормальною формою (КНФ) формули А називаетсяравносільная їй формула, що представляє собою кон'юнкцію елементарних диз'юнкцій.
Для будь-якої формули алгебри логіки шляхом рівносильних перетворень можна отримати її КНФ, причому не єдину.
Наприклад, для формули, використовуючи закони равносильности, маємо
Це одна з форм КНФ, яка далі може бути спрощена (наприклад x Úx ºx. y Úy ºy).
КНФ A називається досконалою кон'юнктівной нормальною формою формули A (СКНФ A), якщо для неї виконані наступні умови.
1. Всі елементарні диз'юнкції, що входять до КНФ A. різні.
2. Всі елементарні диз'юнкції, що входять до КНФ A. містять всі змінні.
3. Кожна елементарна диз'юнкція, що входить в КНФ A. не містить двох однакових змінних.
4. Кожна елементарна диз'юнкція, що входить в КНФ A. не містить змінну і її заперечення.
Можна довести, що кожна не тотожне справжня формула має єдину СКНФ.
Один із способів отримання СКНФ полягає у використанні таблиці істинності для формули # 256; .
Дійсно, отримавши за допомогою таблиці істинності СДНФ # 256 ;. ми отримаємо СКНФ A. взявши заперечення СДНФ # 256 ;.
Продемонструємо це на прикладі все тієї ж формули (табл. 11).
Таблиця істинності для формули