66
правок
Изменения
Нет описания правки
== Общие соображения ==
* В каждой $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$ любой ее единичный аргумент (с учетом возможных отрицаний). $s_i$ имеет самостоятельную единицу на месте $j, (j > 0)$, если $j$-ый аргумент имеет значение $1$.
{{Утверждение
#* При четном количестве у нас найдется особенная пара, а в этих $s_i$ и $\neg s_{i}$ ровно по $m$ самостоятельных единиц, а значит, они обе будут равны $1$, ведь вместе с $x_0 = 1$ среди аргументах медиан будет по $m + 1$ единиц. Тогда всего среди $s_i$ будет $\geqslant m + 1$ $s_i = 1$, значит, конечная медиана вернет $1$, что и нужно при $\oplus$ четного числа единиц.
}}
== См. также ==
* [[Представление функции формулой, полные системы функций]]
* [[Представление функции класса DM с помощью медианы]]
* [[Определение булевой функции]]
