66
правок
Изменения
Нет описания правки
{{Утверждение
|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$.
Давайте найдем $s_j$, в которой среди $A_j$ единиц столько же, сколько и среди $B_j$. Тогда в ней будет $a_j = b_j$, из чего и будет следовать требуемое.
Рассмотрим любую $s_k$. Будем считать, что в $A_k$ меньше половины единиц ($a_k < t$), иначе рассмотрим двойственную ей, в ней будет меньше половины, или, если равенство, то мы уже нашли такую.
Будем последовательно сдвигать отрицания вправо на одну позицию, переходя от $s_l$ к $s_{l+1}$. То есть мы начинаем с $s_l = s_k$, а дальше перебираем $s_l$-ые, переходя к следующей (и увеличивая параметр $l$ на единицу). За каждый сдвиг количество единиц в $A_l$ может измениться только на 1.
Действительно, если в $A_l$ добавились и ушли разные числа, то количество единиц изменилось на $1$ (увеличилось или уменьшилось), а если одинаковые {{---}} то не поменялось.
Таким образом, сделав $m$ шагов, мы дойдем от $s_l$ до $\neg s_l$, причем количество единиц в $A_l$ будет изменяться не более, чем на $1$. Изначально оно было $a_l$, а станет {{---}} $2t - a_l$.
