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