Изменения

** $s_{m+21} = \langle x_0, x_1, \neg x_2, \neg x_3, \ldots, \neg x_{m-1}, x_m, \neg x_{m+1}, \neg x_{m+2}, \neg x_{m+3}, \ldots, \neg x_{2m-1}, \neg x_{2m} \rangle$,** $s_{m+3} = \langle x_0, \neg x_1, \neg x_2, \neg x_3, \neg x_4, \ldots, \neg x_{m-1}, x_m, \neg x_{m+1}, \neg x_{m+2}, x_{m+3}, \ldots, x_{2m-1}, \neg x_{2m} \rangle$,** $s_{m+2} = \langle x_0, \neg x_1, \neg x_2, \neg x_3, \ldots, \neg x_{m-1}, \neg x_m, \neg x_{m+1}, x_{m+2}, x_{m+3} \ldots, x_{2m-1}, \neg x_{2m} \rangle$,** $s_{1m+3} = \langle x_0, x_1, x_2, \neg x_3, \ldots, \neg x_{m-1}, \neg x_m, \neg x_{m+1}, \neg x_{m+2}, x_{m+3}, \ldots, \neg x_{2m-1}, \neg x_{2m} \rangle$,

* Каждой $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$ имеет самостоятельную единицу на месте $j (j > 0)$, если $j$-ый аргумент имеет значение $1$. То есть если $x_j = 1$ и в $s_i$ он стоит без отрицания, то это будет самостоятельная единица. Также $x_j$ будет самостоятельной единицей, если $x_j = 0$ и в $s_i$ он стоит с отрицанием. В остальных случаях $x_j$ не является самостоятельной единицей.

И правда, выше мы поняли, что (1) $\Leftrightarrow a_i = b_i$. Посчитаем количество самостоятельных единиц в $s_i$. $((m - a_i) + b_i) = m \Leftrightarrow a_i = b_i$. Таким образом, равносильность доказана.