Совершенная дизъюнктивная нормальная форма.
Любую функцию алгебры логики можно представить в виде (СДНФ). СДНФ представляет двоичную функцию в виде логической суммы (дизъюнкии) нескольких. логических произведений (конъюнкций), каждое из которых включает в себя все логические переменные функции, взятые с отрицанием или без.
В СДНФ
· нет двух одинаковых слагаемых;
· ни одно слагаемое не содержит двух одинаковых множителей;
· ни одно слагаемое не содержит переменной вместе с ее отрицанием;
· в каждом слагаемом в произведение увязана либо сама переменная, либо еэ отрицание.
Алгоритм построения СДНФ
1. Отметить в таблице истинности функции все наборы, на которых функция равна 1
2. По каждому из отмеченных наборов построить логическое произведение (конъюнкцию) из всех переменных, где переменная
Þ входит без знака отрицания, если в наборе ей соответствует 1
Þ входит со знаком отрицания, если в наборе ей соответствует 0
3. Все построенные логические произведения объединяются в логическую сумму (дизъюнкцию)
Если обозначить 
, где 
- переменная, 
- значение этой
переменной на 
-м наборе, то СДНФ формально можно записать в виде выражения
Пример 2. Построить СДНФ функции из примера 1.
Анализируемая функция равна 1 на наборах 0, 1, 2, 4, 6, 7
Совершенная конъюнктивная нормальная форма.
Любую логическую функцию можно представить в виде совершенной конъюнктивной нормальной формы (СКНФ). СКНФ представляет двоичную функцию в виде логического произведения (конъюнкии) нескольких. Заключенных в скобки логических сумм (дизъюнкций), каждая из которых включает в себя все логические переменные функции, взятые с отрицанием или без
В СКНФ
· нет двух одинаковых сомножителей;
· ни один из сомножителей не содержит двух одинаковых слагаемых;
· ни один из сомнокителей не содержит переменной и ее отрицание;
· в каждом из сомножителей содержится либо сама переменная, либо ее отрицание.
Алгоритм построения СКНФ
1. Отметить в таблице истинности функции все наборы, на которых функция равна 0
- По каждому из отмеченных наборов построить логическую сумму (дизъюнкцию) из всех переменных, где переменная
Þ входит без знака отрицания, если в наборе ей соответствует 0
Þ входит со знаком отрицания, если в наборе ей соответствует 1
- Все построенные логические суммы заключаются в скобки и объединяются в логическое произведение (конъюнкцию)
СКНФ формально можно записать в виде выражения
Пример 3. Построить СКНФ функции из примера 1.
Анализируемая функция равна 0 на наборах 3, 5
