Совершенная дизъюнктивная нормальная форма.

Любую функцию алгебры логики можно представить в виде (СДНФ). СДНФ представляет двоичную функцию в виде логической суммы (дизъюнкии) нескольких. логических произведений (конъюнкций), каждое из которых включает в себя все логические переменные функции, взятые с отрицанием или без.

В СДНФ

· нет двух одинаковых слагаемых;

· ни одно слагаемое не содержит двух одинаковых множителей;

· ни одно слагаемое не содержит переменной вместе с ее отрицани­ем;

· в каждом слагаемом в произведение увязана либо сама переменная, либо еэ отрицание.

Алгоритм построения СДНФ

1. Отметить в таблице истинности функции все наборы, на которых функция равна 1

2. По каждому из отмеченных наборов построить логическое произведение (конъюнкцию) из всех переменных, где переменная

Þ входит без знака отрицания, если в наборе ей соответствует 1

Þ входит со знаком отрицания, если в наборе ей соответствует 0

3. Все построенные логические произведения объединяются в логическую сумму (дизъюнкцию)

Если обозначить , где - переменная, - значение этой
переменной на -м наборе, то СДНФ формально можно записать в виде выражения

Пример 2. Построить СДНФ ф у нкции из примера 1.

Анализируемая функция равна 1 на наборах 0, 1, 2, 4, 6, 7

Совершенная конъюнктивная нормальная форма.

Любую логическую функцию можно представить в виде совершенной конъюнктивной нормальной формы (СКНФ). СКНФ представляет двоичную функцию в виде логического произведения (конъюнкии) нескольких. Заключенных в скобки логических сумм (дизъюнкций), каждая из которых включает в себя все логические переменные функции, взятые с отрицанием или без

В СКНФ

· нет двух одинаковых сомножителей;

· ни один из сомножителей не содержит двух одинаковых слагаемых;

· ни один из сомнокителей не содержит переменной и ее отрицание;

· в каждом из сомножителей содержится либо сама переменная, либо ее отрицание.

Алгоритм построения СКНФ

1. Отметить в таблице истинности функции все наборы, на которых функция равна 0

1. По каждому из отмеченных наборов построить логическую сумму (дизъюнкцию) из всех переменных, где переменная

Þ входит без знака отрицания, если в наборе ей соответствует 0

Þ входит со знаком отрицания, если в наборе ей соответствует 1

1. Все построенные логические суммы заключаются в скобки и объединяются в логическое произведение (конъюнкцию)

 

СКНФ формально можно записать в виде выражения

Пример 3. Построить СКНФ ф у нкции из примера 1.

Анализируемая функция равна 0 на наборах 3, 5