Логические основы ЭВМ. СДНФ и СКНФ

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

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

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

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

Всякую дизъюнкцию элементарных конъюнкций назовем дизъюнктивной нормальной формой (ДНФ).

Всякую конъюнкцию элементарных дизъюнкций назовем конъюнктивной нормальной формой (КНФ).

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

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

Название формулы в определении

Название формулы в определении

Элементарная дизъюнкция

Формула, соответствующая определению

Элементарная дизъюнкция

Формула, соответствующая определению

X ˅

Элементарная конъюнкция

Элементарная конъюнкция

Формула, не соответствующая определению

Формула, не соответствующая определению

ДНФ

X ˅

ДНФ

X &

X ˅ Y & X

X ˅ Y & X

X & Z

X & ˅ X & Y &

КНФ

КНФ

X ˅ Y & X

˅ Y ˅

X ˅ Y & X

X & Y ˅ ˅ X & Z

(X ˅ Y ˅ ) & ( ˅ Z)

X & &

СДНФ

ДНФ можно построить для всякой формулы (путем преобразования)

ДНФ можно построить для всякой формулы (путем преобразования)

СДНФ

X & ( ˅ Y) & (Y ˅ )

СКНФ

X & Y & ˅ X & Y & Z

& Y &

СКНФ

КНФ можно построить для всякой формулы (путем преобразования)

КНФ можно построить для всякой формулы (путем преобразования)

( ˅ Y ˅ Z) & (X ˅ ˅ Z)

X & Y ˅ ˅ X &

(X ˅ Y ˅ ) & ( ˅ Z)

Любую функцию, кроме констант 0 и 1, можно представить в виде как СДНФ, так и СКНФ.

Константа 0 может быть представлена только СКНФ ( 0 = X & ),

а константа 1 – только СДНФ (1= X ˅ ).

Алгоритм получения СДНФ по таблице истинности.

• Отметить те строки таблицы истинности, в последнем столбце которых стоят 1.
• Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 1, то в конъюнкцию включить саму эту переменную, если равно 0, то её отрицание.
• Все полученные конъюнкции связать в дизъюнкцию.

X

0

Y

F (X, Y)

0

0

0

1

1

1

1

0

1

1

0

& Y

*

X &

*

F (X, Y) = ( & Y) ˅ ( X & )

Алгоритм получения СКНФ по таблице истинности.

• Отметить те строки таблицы истинности, в последнем столбце которых стоят 0.
• Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 0, то в дизъюнкцию включить саму эту переменную, если равно 1, то её отрицание.
• Все полученные дизъюнкции связать в конъюнкцию.

X

0

Y

F (X, Y)

0

0

0

1

1

1

0

1

1

1

0

X ˅ Y

*

˅

*

F (X, Y) = (X ˅ Y) & ( ˅ )