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

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

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

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

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

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

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

СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА И СОВЕРШЕННАЯ КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА.

Известно два способа задания логических функций: с помощью формулы и с помощью таблицы истинности. По формуле легко составляется таблица. На практике при конструировании различных электронных устройств часто возникает обратная задача – от таблицы истинности перейти к формуле, чтобы на ее основе построить функциональную схему.

Введем следующие определения:

 

Приведем примеры формул, соответствующих и не соответствующих этим определениям:

 

НАЗВАНИЕ ФОРМУЛЫ В ОПРЕДЕЛЕНИИ Формула, соответствующая определению ФОРМУЛА, НЕ СООТВЕТСТВУЮЩАЯ ОПРЕДЕЛЕНИЮ
Элементарная дизъюнкция
Элементарная конъюнкция
ДНФ ДНФ можно построить для всякой формулы (путем преобразования)
КНФ КНФ можно построить для всякой формулы (путем преобразования)
СДНФ
СКНФ

Этот факт является теоремой алгебры логики. Из него следует, что любая формула (кроме констант 0 и 1) может быть преобразован к виду как СДНФ, так и СКНФ. Константа 0 может быть представлена только СКНФ (), а константа 1 – только СДНФ (). Из вышесказанного следует, что если надо построить формулу некоторой функции по таблице истинности этой функции, то всегда можно получить СКНФ или СДНФ этой функции.

 

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

  1. Отметить те строчки таблицы истинности, в последнем столбце которых стоят 1:

 

X Y F(X,Y)
0 0
0 1 1*
1 0 1*
1 1 0

 

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

– для 2-й строки;

– для 3-й строки.

  1. Все полученные конъюнкции связать в дизъюнкцию: .

 

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

  1. Отметить те строки таблицы истинности, в последнем столбце которых стоит 0:

 

X Y F(X,Y)
0 0*
0 1 1
1 0 1
1 1 0*

 

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

– для 1-й строки;

– для 4-й строки.

  1. Все полученные дизъюнкции связать в конъюнкцию: .

 

Покажем, что полученные по двум алгоритмам СДНФ и СКНФ эквивалентны. Преобразуем СКНФ по правилам алгебры логики: .

Примечание: для нахождения формулы по таблице истинности рекомендуется использовать тот из двух алгоритмов, в котором в таблице помечается меньше строк.