66
правок
Изменения
Нет описания правки
|statement=Среди ${x_i}$ четное число единиц $\Leftrightarrow$ найдется двойственная пара, элементы которой имеют одинаковое количество самостоятельных единиц.
|proof=
Пусть $A_i$ {{---}} множество аргументов (за исключением $x_0$) $s_i$ с отрицанием, $B_i$ {{---}} без отрицания(тоже за исключением $x_0$). Оба множества по условию мощности $m$.
Пусть среди $A_i$ ровно $a_i$ переменных равны единице, тогда оставшиеся $(m - a_i)$ из них {{---}} нули.
Аналогично среди $B_i$ ровно $b_i$ единиц и $(m - b_i)$ нулей.
$\Rightarrow$
Пусть среди ${x_i}(i > 0)$ будет $2t$ единиц.
Давайте найдем $s_j$, в которой среди $A_j$ единиц столько же, сколько и среди $B_j$. Тогда в ней будет $a_j = b_j$, из чего и будет следовать требуемое.
Рассмотрим любую $s_k$. Будем считать, что в $A_k$ меньше половины единиц ($a_k < t$), иначе рассмотрим двойственную ей, в ней будет меньше половины, или, если равенство, то мы уже нашли такую.
