Изменения

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

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

561 байт добавлено, 21:47, 17 октября 2018
Нет описания правки
== Вспомогательные утверждения ==
* {{Лемма|statement=В каждой $s_i$ ровно $m$ переменных с отрицанием и столько же без него(без учета $x_0$).|proof=Различных чисел-индексов от $j$ до $j + m - 1$ (с учетом того, что $x_{2m+k}$ = $x_k$) ровно $((j + m - 1) - j + 1 + 2m) \bmod 2m = m$.Поэтому с отрицанием будет ровно $m$ переменных.А так как всего $2m$ переменных, то без отрицания будет тоже ровно $m$.}}* {{Лемма|statement=Каждой $s_i$ можно однозначно сопоставить в пару такую $s_j$, что все переменные с отрицанием из $s_i$ в $s_j$ будут без отрицания и наоборот. Это следует из того, как мы |proof=Мы строим набор ${s_i}$ {{---}} , циклически сдвигаем сдвигая отрезок отрицания переменных, пока не получим все возможные. Для нахождения нужно сдвинуть отрезок Совершив ровно на $m$ позиций (вправо или влевотаких шагов, мы сдвинем начала отрезка отрицания на следующую позицию после его конца. Таким образом, там, где был отрезок отрицания, будет отрезок без отрицания, это не важно {{---и наоборот.}} получится одно и то же). Назовем такую пару $(s_i, s_j)$ '''двойственной''', и будем обозначать через $\neg s_i$ двойственную $s_i$ пару. * Назовем '''самостоятельной единицей''' для $s_i$ любой ее единичный аргумент (с учетом возможных отрицаний).
Назовем '''самостоятельной единицей''' для $s_i$ любой ее единичный аргумент (с учетом возможных отрицаний).
$s_i$ имеет самостоятельную единицу на месте $j, (j > 0)$, если $j$-ый аргумент имеет значение $1$.
66
правок

Навигация