Изменения

Перейти к: навигация, поиск

Выражение функции XOR через медианы

202 байта убрано, 11:14, 24 октября 2018
Нет описания правки
== Вспомогательные утверждения ==
Далее исключим $x_0$ из рассмотрения аргументов $s_i$.
{{Лемма
|statement=В каждой $s_i$ ровно $m$ переменных с отрицанием и столько же без него.
|proof=Очевидно из определения.
}}
{{Лемма
|statement=Каждой $s_i$ можно однозначно сопоставить в пару такую $s_j$, что все переменные с отрицанием из $s_i$ в $s_j$ будут без отрицания и наоборот.
66
правок

Навигация