66
правок
Изменения
Нет описания правки
И весь этот набор ${s_i}$, вместе с $\neg x_0$, передается на вход еще одной медиане: $\langle \neg x_0, s_1, s_2, \ldots, s_{2m} \rangle$
Далее исключим на время исключим $x_0$ из рассмотрения аргументов $s_i x_0$.
== Общие соображения ==
* В каждой $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$ "достаточно много" (а сколько именно, будет зависеть от $x_0$), то в $\neg s_i$ их будет "достаточно мало".
{{Утверждение
|statement=Если в $s_i $ ровно $n$ самостоятельных единиц, то в $\neg s_i $ их будет $(2m - n)$ самостоятельных единиц.|proof=Пусть $A$ - множество переменных аргументов $s_i$ с отрицанием, $B$ - без отрицания. Оба множества по условию мощности $m$.Пусть среди $A$ ровно $a$ переменных равны $1$. Тогда , тогда оставшиеся $(m - a)$ из них {{---}} нули. Пусть Аналогично среди $B$ ровно $b$ переменных равны $1$. Тогда оставшиеся единиц и $(m - b)$ из них {{---}} нулинулей.
Самостоятельные единицы $s_i$ получаются из нулей среди $A$ и единиц среди $B$. Тогда в $s_i$ будет $(m - a) + b$ самостоятельных единиц.
В двойственной $s_i$ переменные заменятся на их отрицания, поэтому самостоятельные единицы $\neg s_i$ получаются из единиц среди $A$ и нулей среди $B$.
{{Утверждение
|statement=Среди ${x_i}$ четное число единиц $\Leftrightarrow $ найдется двойственная пара с одинаковым количеством самостоятельных единиц, равным $m$.
|proof=Импликация влево.
Из утверждения выше мы поняли структуру аргументов $s_i$. Нужно приравнять количества (в обозначениях выше): $(m - a) + b = a + (m - b) \Leftrightarrow a = b$
А $a$ и $b$ {{---}} количества единиц в $A$ и в $B$ соответственно, и, так как множество всех аргументов $s_i$ это $A \cup B$, то $(a+b)$ и есть количество единиц среди ее аргументов.
Но $a = b$, значит $a + b$ четное.
Вообще, утверждения "нашлась двойственная пара с одинаковым числом самостоятельных единиц" (1) и "нашлась $s_i$ с количеством самостоятельных единиц, равным $m$" (2) равносильны.
И правда, выше мы поняли, что (1) $\Leftrightarrow a = b$. Посчитаем количества самостоятельных единиц в $s_i$. $((m - a) + b) = m \Leftrightarrow a = b$. Таким образом, равносильность доказана.
Импликация вправо.
}}
