Изменения

Перейти к: навигация, поиск

Выражение функции XOR через медианы

685 байт добавлено, 19:33, 16 октября 2018
Нет описания правки
Далее на время исключим $x_0$ из рассмотрения аргументов $s_i$.
== Общие соображения Вспомогательные утверждения ==
* В каждой $s_i$ ровно $m$ переменных с отрицанием и столько же без него.
* Каждой $s_i$ можно однозначно сопоставить в пару такую $s_j$, что все переменные с отрицанием из $s_i$ в $s_j$ будут без отрицания и наоборот. Это следует из того, как мы строим набор ${s_i}$ {{---}} циклически сдвигаем отрезок отрицания переменных, пока не получим все возможные. Для нахождения нужно сдвинуть отрезок ровно на $m$ позиций (вправо или влево, это не важно {{---}} получится одно и то же). Назовем такую пару $(s_i, s_j)$ '''двойственной''', и будем обозначать через $\neg s_i$ двойственную $s_i$ пару.
Заметим также, что мы доказали наличие '''одной пары''', но на самом деле таких может быть больше. Давайте такие пары назовем '''особенными''', а остальные {{---}} обычными.
}}
 
== Основное утверждение ==
{{Теорема
* [[Представление функции класса DM с помощью медианы]]
* [[Определение булевой функции]]
 
== Источники информации ==
* [https://si2.epfl.ch/~demichel/publications/archive/2016/2016_ismvl_1.pdf Notes on Majority Boolean Algebra]
* [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]
54
правки

Навигация