17
правок
Изменения
КНФ
,1) Изменены "..." на "\ldot" 2) Добавлена СКНФ для медианы от 5 аргументов
|proof =
Поскольку инверсия функции <tex>\neg{f}(\vec x)</tex> равна единице на тех наборах, на которых <tex>f(\vec x)</tex> равна нулю, то СДНФ для <tex>\neg{f}(\vec x)</tex> можно записать следующим образом:
<tex>\neg{f}(\vec x) = \bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \ldots \wedge x_{n}^{\sigma_{n}}) </tex>, где <tex> \sigma_{i} </tex> обозначает наличие или отсутствие отрицание при <tex> x_{i} </tex>
Найдём инверсию левой и правой части выражения:
<tex> f(\vec x) = \neg ({\bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \ldots \wedge x_{n}^{\sigma_{n}})}) </tex>
Применяя дважды к полученному в правой части выражению правило де Моргана, получаем:
<tex> f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... \ldots ,x^{\sigma_{n}}) = 0} (\neg{x_{1}^{\sigma_{1}}} \vee \neg{x_{2}^{\sigma_{2}}} \vee ... \ldots \vee \neg{x_{n}^{\sigma_{n}}} ) </tex>
Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, не равной тождественному нулю, то теорема доказана.
Исключающее или: <tex> x \oplus y \oplus z = (\neg {x} \lor \neg {y} \lor z) \land (\neg {x} \lor y \lor \neg {z}) \land (x \lor \neg {y} \lor \neg {z}) \land (x \lor y \lor z)</tex>
Медиана 5 аргументов:
<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land \\ (x_1 \lor \overline{x_2} \lor x_3 \lor x_4 \lor x_5) \land (\overline{x_1} \lor \overline{x_2} \lor x_3 \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4 \lor x_5) \land \\ (\overline{x_1} \lor x_2 \lor \overline{x_3} \lor x_4 \lor x_5) \land (x_1 \lor \overline{x_2} \lor \overline{x_3} \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4} \lor x_5) \land \\ (\overline{x_1} \lor x_2 \lor x_3 \lor \overline{x_4} \lor x_5) \land (x_1 \lor \overline{x_2} \lor x_3 \lor \overline{x_4} \lor x_5) \land (x_1 \lor x_2 \lor \overline{x_3} \lor \overline{x_4} \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor x_4 \lor \overline{x_5}) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4 \lor \overline{x_5}) \land (x_1 \lor \overline{x_2} \lor x_3 \lor x_4 \lor \overline{x_5}) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4 \lor \overline{x_5}) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4} \lor \overline{x_5}) </tex>
== Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%9A%D0%9D%D0%A4 Википедия {{---}} СКНФ]
