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