Совершенной ДНФ (СДНФ) формулы a(X1, X2, X3, ..., Xn), содержащей n различных переменных, называется ДНФ, обладающая следующими свойства-ми: 1) в ней нет двух одинаковых слагаемых; 2) ни одно слагаемое не содержит двух одинаковых множителей; 3) никакое слагаемое не содержит переменной вместе с ее отрицанием; 4) в каждом слагаемом содержится в качестве множителей либо перемен-ная Xi, либо ее отрицание, где i изменяется от 1 до n.
Совершенной КНФ (СКНФ) формулы a(X1, X2, X3, ..., Xn), содержащей n раз-личных переменных, называется КНФ, обладающая следующими свойствами: 1) в ней нет двух одинаковых множителей; 2) ни один множитель не содержит двух одинаковых слагаемых; 3) ни один множитель не содержит переменной вместе с ее отрицанием; 4) каждый множитель содержит в качестве слагаемого либо переменную Xi, либо ее отрицание, где i изменяется от 1 до n.
ПРИВЕДЕНИЕ к СКНФ и СДНФ с помощью равносильностей: сначала найдем нормальные формы (ДНФ для СДНФ, КНФ для СКНФ). Для СДНФ добавляем нехватающий множитель в кажое слагаемое. пример: было Y&Z\/..., меняем на Y&Z&(X\/(not X)))\/.... применяя законы все упрощаем например до X&Y&Z\/... или (not X)&Y&Z\/... . Для СКНФ все анлогично, только берем КНФ и добавляем нехватающее слагаемое в каждый множитель. пример: было (X\/Y)&..., меняем на (X\/Y\/Z&(not Z))&... . В итоге получаем (X\/Y\/Z)&... или (X\/Y\/(not Z))&... .
ПРИВЕДЕНИЕ к СКНФ и СДНФ с помощью таблицы истинности: сначала построим таблицу истинности. Затем для СДНФ рассмотрим комбинации значений, которые дают 1. Две комбинации A=0, B=1, C=1 и A=1, B=1, C=1. Объеденим их в конъюнкцию заменяя 0 значения отрицанием: (not A)&B&C и A&B&C. Затем все конъюнкции свяжем в дизъюнкцию: (not A)&B&C\/A&B&C. Для СКНФ рассмотрим оставшиеся комбинации, т.е. дающие значение 0: A=0, B=0, C=0 и A=1, B=0, C=1. Составим дизъюнкцию меняя значения с 1 на отрицания: A\/B\/C и (not A)\/B\/(not C). Затем объединяем все в дизъюнкцию: (A\/B\/C) &((not A)\/B\/(not C)).
