66
правок
Изменения
Нет описания правки
{{ЗадачаТеорема|definition statement = Докажите, что $x_0 \oplus x_1 \oplus \ldots \oplus x_{2m} = \langle \neg x_0, s_1, s_2, \ldots, s_{2m} \rangle$, $s_j = \langle x_0, x_j, x_{j+1}, \ldots, x_{j+m-1}, \neg x_{j+m}, \neg x_{j+m+1}, \ldots, \neg x_{j+2m-1} \rangle$, где $x_{2m+k}$ обозначает то же, что и $x_k$, при $k \geqslant 1$.
}}
И весь этот набор ${s_i}$ (а их будет ровно $2m$ штук) передается (вместе с $\neg x_0$), на вход еще одной медиане: $\langle \neg x_0, s_1, s_2, \ldots, s_{2m} \rangle$
== Вспомогательные утверждения ==
Далее исключим $x_0$ из рассмотрения аргументов $s_i$.
{{Лемма
|statement=В каждой $s_i$ ровно $m$ переменных с отрицанием и столько же без него (без учета $x_0$).
|proof=Различных чисел-индексов от $j$ до $j + m - 1$ (с учетом того, что $x_{2m+k}$ = $x_k$) ровно $((j + m - 1) - j + 1 + 2m) \bmod 2m = m$. Поэтому с отрицанием будет ровно $m$ переменных.
А так как всего $2m$ переменных, то без отрицания будет тоже ровно $m$.
Назовем '''самостоятельной единицей''' для $s_i$ любой ее единичный аргумент (с учетом возможных отрицаний).
$s_i$ имеет самостоятельную единицу на месте $j, (j > 0)$, если $j$-ый аргумент имеет значение $1$.
{{Утверждение
}}
== Основное утверждение Доказательство теоремы ==
{{Теорема
* [https://www.researchgate.net/profile/Esam_Alkaldy/publication/277518459_A_Novel_Design_Approach_for_Multi-input_XOR_Gate_Using_Multi-input_Majority_Function/links/568b60df08ae051f9afa9b56/A-Novel-Design-Approach-for-Multi-input-XOR-Gate-Using-Multi-input-Majority-Function.pdf Multi-input XOR Gate Using Multi-input Majority Function]
* [http://sites.math.rutgers.edu/~sk1233/courses/topics-S13/lec1.pdf Upper bounds on formula size for specific functions]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции ]]
