Изменения

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

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

4 байта убрано, 23:43, 22 октября 2018
Нет описания правки
* Выпишем последовательность $x_1, x_2, \ldots, x_{2m}$
* Первую половину аргументов (а их ровно $m$) возьмем с отрицанием ($\neg x_1, \neg x_2, \ldots, \neg x_m, x_{m+1}, x_{m+2}, \ldots, x_{2m}$)
* Слева к этой последовательности припишем $x_0$ и подставим подадим в качестве аргументов медиане: $\langle x_0, \neg x_1, \neg x_2, \ldots, \neg x_m, x_{m+1}, x_{m+2}, \ldots, x_{2m} \rangle$ {{---}} так мы получили $s_{m+1}$
* Остальные $s_i$ получаются "циклическим сдвигом" отрицания (без учета $x_0$), например, вправо (так мы получим все "циклические сдвиги" отрицаний):
** $s_{1} = \langle x_0, x_1, x_2, x_3, \ldots, 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$
49
правок

Навигация