66
правок
Изменения
Нет описания правки
== Общие соображения ==
* В каждой $s_i$ ровно $m$ переменных с отрицанием и столько же без него.
* Каждой $s_i$ можно однозначно сопоставить в пару такую $s_j$, что все переменные с отрицанием из $s_i$ в $s_j$ будут без отрицания и наоборот. Это следует из того, как мы строим набор ${s_i}$ {{---}} циклически сдвигаем отрезок отрицания переменных, пока не получим все возможные. Для нахождения нужно сдвинуть отрезок ровно на $m$ позиций (вправо или влево, это не важно {{---}} получится одно и то же). Назовем такую пару $(s_i, s_j)$ '''двойственной''', и пусть $s_j = \neg s_i$ (на самом деле $. \neg s_i = s_$ {{i+m---}}такое обозначение двойственной $s_i$)паре. * Назовем '''самостоятельной единицей''' для $s_i$ любой ее единичный аргумент (с учетом возможных отрицаний). $s_i$ имеет самостоятельную единицу на месте $j , (j > 0)$, если $j$-ый аргумент имеет значение $1$.
То есть если $x_j = 1$ и в $s_i$ он стоит без отрицания, то это будет самостоятельная единица. Также $x_j$ будет самостоятельной единицей, если $x_j = 0$ и в $s_i$ он стоит с отрицанием. В остальных случаях $x_j$ не является самостоятельной единицей.
{{Утверждение
}}
{{Теорема|statement=$x_0 \oplus x_1 \oplus \ldots \oplus x_{2m} = Решение \langle \neg x_0, s_1, s_2, \ldots, s_{2m} \rangle$, $s_j =\langle x_0, x_j, x_{j+1}, \ldots, x_{j+m-1}, \neg x_{j+m}, \neg x_{j+m+1}, \ldots, \neg x_{j+2m-1} \rangle$|proof=
Пусть $k_i$ {{---}} количество самостоятельных единиц у $s_i$.
Рассмотрим два случая.
# $x_0 = 0$.
