66
правок
Изменения
м
Назовем '''самостоятельной единицей''' для $s_i$ любой ее единичный аргумент (с учетом возможных отрицаний), причем $x_0$ за аргумент не считаем.$s_i$ имеет самостоятельную единицу Пусть на месте $j$, если $j$-ый аргумент имеет значение ом месте у $1s_i$ стоит единица ($j$ > 0). Назовем этот аргумент '''самостоятельной единицей'''.
Нет описания правки
== Вспомогательные утверждения ==
{{Лемма
|statement=Каждой $s_i$ можно однозначно сопоставить в пару такую $s_j$, что все переменные (кроме $x_0$) с отрицанием из $s_i$ в $s_j$ будут без отрицания и наоборот. Здесь исключим Аргументы $x_0$ из рассмотрения аргументов у всех $s_i$одинаковые, и поэтому будем считать, что у разбивать на пары без учета $s_ix_0$ $2m$ аргументов {{---}} $(x_1, x_2, \ldots, x_{2m})$ (некоторые из них с отрицанием).
|proof=Мы строим набор ${s_i}$, циклически сдвигая отрезок отрицания переменных, пока не получим все возможные. Совершив ровно $m$ таких шагов, мы сдвинем начало отрезка отрицания на следующую позицию после его конца. Таким образом, там, где был отрезок отрицания, будет отрезок без отрицания, и наоборот.
}}
Назовем такую пару $(s_i, s_j)$ '''двойственной''', и будем обозначать через $\neg s_i$ двойственную $s_i$ пару.
{{Утверждение
Но $a_i = b_i$, значит $a_i + b_i$ четное.
Вообще, утверждения "нашлась двойственная пара, элементы которой имеют одинаковое количество самостоятельных единиц" (1) и "нашлась $s_i$ с количеством самостоятельных единиц, равным $m$" (2) равносильны.
И правда, выше мы поняли, что (1) $\Leftrightarrow a_i = b_i$. Посчитаем количество самостоятельных единиц в $s_i$. $((m - a_i) + b_i) = m \Leftrightarrow a_i = b_i$.
$\Rightarrow$
