54
правки
Изменения
КНФ
,→СКНФ
Применяя дважды к полученному в правой части выражению правило де Моргана, получаем:
<tex> f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... ,x^{\sigma_{n}}) = 0} (\overline{x_{1}^{\overline{\sigma_{1}}} \vee \overline{x_{2}^{\overline{\sigma_{2}}} \vee ... \vee \overline{x_{n}^{\overline{\sigma_{n}}}) </tex>
Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, то теорема доказана.
