Выражение функции XOR через медианы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Метки: правка с мобильного устройства, правка из мобильной версии)
(Метки: правка с мобильного устройства, правка из мобильной версии)
Строка 18: Строка 18:
 
** $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}, \ldots, \neg x_{2m-1}, \neg x_{2m} \rangle$
 
** $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}, \ldots, \neg x_{2m-1}, \neg x_{2m} \rangle$
  
И весь этот набор ${s_i}$, вместе с $\neg x_0$, передается на вход еще одной медиане: $\langle \neg x_0, s_1, s_2, \ldots, s_{2m} \rangle$
+
И весь этот набор ${s_i}$ (а их будет ровно $2m$ штук) передается (вместе с $\neg x_0$), на вход еще одной медиане: $\langle \neg x_0, s_1, s_2, \ldots, s_{2m} \rangle$
  
 
Далее на время исключим $x_0$ из рассмотрения аргументов $s_i$.
 
Далее на время исключим $x_0$ из рассмотрения аргументов $s_i$.
Строка 25: Строка 25:
 
* В каждой $s_i$ ровно $m$ переменных с отрицанием и столько же без него.
 
* В каждой $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+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+m}$).  
* Назовем '''самостоятельной единицей''' для $s_i$ любой ее единичный аргумент.
+
* Назовем '''самостоятельной единицей''' для $s_i$ любой ее единичный аргумент (с учетом возможных отрицаний). То есть если $x_j = 1$ и в $s_i$ он стоит без отрицания, то это будет самостоятельная единица. Также $a_j$ будет самостоятельной единицей, если $a_j = 0$ и в $s_i$ он стоит с отрицанием. В остальных случаях $a_j$ не является самостоятельной единицей.
 
* Если самостоятельных единиц в $s_i$ "достаточно много" (а сколько именно, будет зависеть от $x_0$), то в $\neg s_i$ их будет "достаточно мало".
 
* Если самостоятельных единиц в $s_i$ "достаточно много" (а сколько именно, будет зависеть от $x_0$), то в $\neg s_i$ их будет "достаточно мало".
  
 
{{Утверждение
 
{{Утверждение
 
|statement=Если в $s_i$ ровно $n$ самостоятельных единиц, то в $\neg s_i$ их будет $(2m - n)$.
 
|statement=Если в $s_i$ ровно $n$ самостоятельных единиц, то в $\neg s_i$ их будет $(2m - n)$.
|proof=Пусть $A$ - множество аргументов $s_i$ с отрицанием, $B$ - без отрицания. Оба множества по условию мощности $m$.
+
|proof=Пусть $A_i$ - множество аргументов $s_i$ с отрицанием, $B_i$ - без отрицания. Оба множества по условию мощности $m$.
Пусть среди $A$ ровно $a$ переменных равны $1$, тогда оставшиеся $(m - a)$ из них {{---}} нули.  
+
Пусть среди $A_i$ ровно $a_i$ переменных равны $1$, тогда оставшиеся $(m - a_i)$ из них {{---}} нули.  
Аналогично среди $B$ ровно $b$ единиц и $(m - b)$ нулей.
+
Аналогично среди $B_i$ ровно $b_i$ единиц и $(m - b_i)$ нулей.
Самостоятельные единицы $s_i$ получаются из нулей среди $A$ и единиц среди $B$. Тогда в $s_i$ будет $(m - a) + b$ самостоятельных единиц.
+
Самостоятельные единицы $s_i$ получаются из нулей среди $A_i$ и единиц среди $B_i$. Тогда в $s_i$ будет $(m - a_i) + b_i$ самостоятельных единиц.
В двойственной $s_i$ переменные заменятся на их отрицания, поэтому самостоятельные единицы $\neg s_i$ получаются из единиц среди $A$ и нулей среди $B$.
+
В $\neg s_i$ переменные заменятся на их отрицания, поэтому самостоятельные единицы в ней получаются из единиц среди $A_i$ и нулей среди $B_i$.
Поэтому количество самостоятельных единиц в $\neg s_i$ будет $a + (m - b)$.
+
Поэтому количество самостоятельных единиц в $\neg s_i$ будет $a_i + (m - b_i)$.
Нетрудно убедиться, что нужное соотношение выполняется: $(m - a) + b = 2m - (a + (m - b)) \Leftrightarrow m - a + b = 2m - a - m + b$
+
Нетрудно убедиться, что нужное соотношение выполняется: $(m - a_i) + b_i = 2m - (a_i + (m - b_i)) \Leftrightarrow m - a_i + b_i = 2m - a_i - m + b_i$
 
}}
 
}}
  
Строка 43: Строка 43:
 
|proof=Импликация влево.
 
|proof=Импликация влево.
  
Из утверждения выше мы поняли структуру аргументов $s_i$. Нужно приравнять количества (в обозначениях выше): $(m - a) + b = a + (m - b) \Leftrightarrow a = b$
+
Выше мы поняли структуру аргументов $s_i$. Нужно приравнять количества (в обозначениях выше): $(m - a_i) + b_i = a_i + (m - b_i) \Leftrightarrow a_i = b_i$
  
А $a$ и $b$ {{---}} количества единиц в $A$ и в $B$ соответственно, и, так как множество всех аргументов $s_i$ это $A \cup B$, то $(a+b)$ и есть количество единиц среди ее аргументов.
+
А $a_i$ и $b_i$ {{---}} количества единиц в $A_i$ и в $B_i$ соответственно, и, так как множество всех аргументов $s_i$ это $A_i \cup B_i$, то $(a_i+b_i)$ и есть количество единиц среди ее аргументов.
Но $a = b$, значит $a + b$ четное.
+
Но $a_i = b_i$, значит $a_i + b_i$ четное.
  
 
Вообще, утверждения "нашлась двойственная пара с одинаковым числом самостоятельных единиц" (1) и "нашлась $s_i$ с количеством самостоятельных единиц, равным $m$" (2) равносильны.
 
Вообще, утверждения "нашлась двойственная пара с одинаковым числом самостоятельных единиц" (1) и "нашлась $s_i$ с количеством самостоятельных единиц, равным $m$" (2) равносильны.
  
И правда, выше мы поняли, что (1) $\Leftrightarrow a = b$. Посчитаем количества самостоятельных единиц в $s_i$. $((m - a) + b) = m \Leftrightarrow a = b$. Таким образом, равносильность доказана.  
+
И правда, выше мы поняли, что (1) $\Leftrightarrow a_i = b_i$. Посчитаем количество самостоятельных единиц в $s_i$. $((m - a_i) + b_i) = m \Leftrightarrow a_i = b_i$. Таким образом, равносильность доказана.  
 +
 
 
Импликация вправо.
 
Импликация вправо.
 +
Пусть среди ${x_i}$ будет $2t$ единиц.
 +
Давайте найдем $s_j$, в которой среди $A_j$ единиц столько же, сколько и среди $B_j$. Тогда в ней будет $a_j = b_j$, из чего и будет следовать требуемое.
 +
Рассмотрим любую $s_k$. Будем считать, что в $A_k$ меньше половины единиц ($a_k < t$), иначе рассмотрим двойственную ей, в ней будет меньше половины, или, если равенство, то мы уже нашли такую.
 +
Будем последовательно сдвигать отрицания вправо на одну позицию, переходя от $s_l$ к $s_{l+1}$. За каждый сдвиг количество единиц в $A_l$ может измениться только на 1.
 +
Действительно, если в $A_l$ добавились и ушли разные числа, то количество единиц изменилось на $1$ (увеличилось или уменьшилось), а если одинаковые {{---}} то не поменялось.
 +
Таким образом, сделав $m$ шагов, мы дойдем от $s_l$ до $\neg s_l$, причем количество единиц в $A_l$ будет изменяться не более, чем на $1$. Изначально оно было $a_l$, а станет {{---}} $2t - a_l$.
 +
Тогда выполняются неравенства: $a_k \le t \le 2t - a_k$. Левый знак верен просто потому, что мы так выбрали $s_k$, а правый, очевидно, равносилен первому.
 +
Таким образом, мы, изменяя a_l не больше, чем на единицу, пришли из $a_k$ в $2t - a_k$, причем число $t$ было между ними. Поэтому мы обязательно на каком-то шаге оказались с $a_{l'} = t$, то есть ровно половина единиц попала в $A_{l'}$, чего мы и хотели.
 +
Заметим также, что мы доказали наличие '''одной пары''', но на самом деле таких может быть больше. Давайте такие пары назовем '''особенными''', а остальные {{---}} обычными.
 +
}}
  
}}
+
== А теперь решение ==
 +
Пусть $k_i$ {{---}} количество самостоятельных единиц у $s_i$.
 +
Наконец вспомним про $x_0$.
 +
Рассмотрим два случая.
 +
# $x_0 = 0$.
 +
* Тогда в каждой $s_i$ будет стоять вместо него $0$, то есть количество аргументов-единиц в точности равно количеству самостоятельных единиц.
 +
* Пусть $k_i /geqslant m + 1 \Rightarrow k_{i + m} \leqslant m - 1$ (и аналогично с противоположным знаком) $\Rightarrow$ в обычных парах одна $s_i$ будет равна $1$, а вторая $0$.
 +
* При нечетном количестве единиц особенных пар не будет, будет только ровно $m$ обычных пар, из каждой ровно одна $s_i$ даст единицу. Тогда среди всех $s_i$ будет ровно $m$ единиц, и, подставив их в конечную медиану, вместе с $\neg x_0 = 1$, получим ровно $m + 1$ аргумент, равный $1$. Тогда медиана вернет $1$, чего и должен вернуть $\oplus$ нечетного числа единиц.
 +
* При четном количестве у нас найдется особенная пара, а в этих $s_i$ и $\neg s_{i}$ ровно по $m$ самостоятельных единиц, а значит, они обе будут равны $0$. Тогда всего среди $s_i$ будет $\leqslant m - 1$ $s_i = 1$, значит, конечная медиана вернет $0$, что и нужно при $\oplus$ четного числа единиц.
 +
# $x_0 = 1$
 +
* Тогда в каждой $s_i$ будет стоять вместо него $1$, то есть количество аргументов-единиц для $s_i$ на один больше количества самостоятельных единиц.
 +
* Пусть $k_i /geqslant m + 1 \Rightarrow k_{i + m} \leqslant m - 1$ (и аналогично с противоположным знаком) $\Rightarrow$ по-прежнему (тут с учетом $x_0 = 1$) в обычных парах одна $s_i$ будет равна $1$, а вторая $0$.
 +
* При нечетном количестве единиц особенных пар нет, будет снова только ровно $m$ обычных пар, из каждой ровно одна $s_i$ даст единицу. Тогда среди всех $s_i$ будет ровно $m$ единиц, и, подставив их в конечную медиану, вместе с $\neg x_0 = 0$, получим ровно $m$ аргументов, равных $1$. Тогда медиана вернет $0$, чего и должен вернуть $\oplus$ четного числа единиц.
 +
* При четном количестве у нас найдется особенная пара, а в этих $s_i$ и $\neg s_{i}$ ровно по $m$ самостоятельных единиц, а значит, они обе будут равны $1$, ведь вместе с $x_0 = 1$ среди аргументах медиан будет по $m + 1$ единиц. Тогда всего среди $s_i$ будет $\geqslant m + 1$ $s_i = 1$, значит, конечная медиана вернет $1$, что и нужно при $\oplus$ четного числа единиц.

Версия 22:20, 9 октября 2018

Задача:
Докажите, что $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 \ge 1$.


Определение:
Медиана или функция большинства (англ. Majority function) — функция (в данном случае) с нечетным числом входов, возвращающая $1$ тогда и только тогда, когда среди ее аргументов не меньше половины единиц.


Разберемся с условием. Нам предлагается выразить $\mathrm {XOR}$ с $2m+1$ аргументами с помощью медианы с $2m+1$ аргументом. Ей на вход подается набор $\{s_i\}$, получаемый следующим образом:

  • Выпишем последовательность $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_{m+2} = \langle x_0, x_1, \neg x_2, \neg x_3, \ldots, \neg x_m, \neg x_{m+1}, x_{m+2}, \ldots, x_{2m} \rangle$,
    • $s_{m+3} = \langle x_0, x_1, x_2, \neg x_3, \neg x_4, \ldots, \neg x_m, \neg x_{m+1}, \neg x_{m+2}, x_{m+3}, \ldots, x_{2m} \rangle$,
    • $s_{m} = \langle x_0, \neg x_1, \neg x_2, \neg x_3, \ldots, \neg x_{m-1}, x_m, x_{m+1}, x_{m+2}, \ldots, x_{2m-1}, \neg x_{2m} \rangle$
    • $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}, \ldots, \neg x_{2m-1}, \neg x_{2m} \rangle$

И весь этот набор ${s_i}$ (а их будет ровно $2m$ штук) передается (вместе с $\neg x_0$), на вход еще одной медиане: $\langle \neg x_0, s_1, s_2, \ldots, s_{2m} \rangle$

Далее на время исключим $x_0$ из рассмотрения аргументов $s_i$.

Общие соображения

  • В каждой $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+m}$).
  • Назовем самостоятельной единицей для $s_i$ любой ее единичный аргумент (с учетом возможных отрицаний). То есть если $x_j = 1$ и в $s_i$ он стоит без отрицания, то это будет самостоятельная единица. Также $a_j$ будет самостоятельной единицей, если $a_j = 0$ и в $s_i$ он стоит с отрицанием. В остальных случаях $a_j$ не является самостоятельной единицей.
  • Если самостоятельных единиц в $s_i$ "достаточно много" (а сколько именно, будет зависеть от $x_0$), то в $\neg s_i$ их будет "достаточно мало".
Утверждение:
Если в $s_i$ ровно $n$ самостоятельных единиц, то в $\neg s_i$ их будет $(2m - n)$.
[math]\triangleright[/math]

Пусть $A_i$ - множество аргументов $s_i$ с отрицанием, $B_i$ - без отрицания. Оба множества по условию мощности $m$. Пусть среди $A_i$ ровно $a_i$ переменных равны $1$, тогда оставшиеся $(m - a_i)$ из них — нули. Аналогично среди $B_i$ ровно $b_i$ единиц и $(m - b_i)$ нулей. Самостоятельные единицы $s_i$ получаются из нулей среди $A_i$ и единиц среди $B_i$. Тогда в $s_i$ будет $(m - a_i) + b_i$ самостоятельных единиц. В $\neg s_i$ переменные заменятся на их отрицания, поэтому самостоятельные единицы в ней получаются из единиц среди $A_i$ и нулей среди $B_i$. Поэтому количество самостоятельных единиц в $\neg s_i$ будет $a_i + (m - b_i)$.

Нетрудно убедиться, что нужное соотношение выполняется: $(m - a_i) + b_i = 2m - (a_i + (m - b_i)) \Leftrightarrow m - a_i + b_i = 2m - a_i - m + b_i$
[math]\triangleleft[/math]
Утверждение:
Среди ${x_i}$ четное число единиц $\Leftrightarrow$ найдется двойственная пара с одинаковым количеством самостоятельных единиц, равным $m$.
[math]\triangleright[/math]

Импликация влево.

Выше мы поняли структуру аргументов $s_i$. Нужно приравнять количества (в обозначениях выше): $(m - a_i) + b_i = a_i + (m - b_i) \Leftrightarrow a_i = b_i$

А $a_i$ и $b_i$ — количества единиц в $A_i$ и в $B_i$ соответственно, и, так как множество всех аргументов $s_i$ это $A_i \cup B_i$, то $(a_i+b_i)$ и есть количество единиц среди ее аргументов. Но $a_i = b_i$, значит $a_i + b_i$ четное.

Вообще, утверждения "нашлась двойственная пара с одинаковым числом самостоятельных единиц" (1) и "нашлась $s_i$ с количеством самостоятельных единиц, равным $m$" (2) равносильны.

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

Импликация вправо. Пусть среди ${x_i}$ будет $2t$ единиц. Давайте найдем $s_j$, в которой среди $A_j$ единиц столько же, сколько и среди $B_j$. Тогда в ней будет $a_j = b_j$, из чего и будет следовать требуемое. Рассмотрим любую $s_k$. Будем считать, что в $A_k$ меньше половины единиц ($a_k < t$), иначе рассмотрим двойственную ей, в ней будет меньше половины, или, если равенство, то мы уже нашли такую. Будем последовательно сдвигать отрицания вправо на одну позицию, переходя от $s_l$ к $s_{l+1}$. За каждый сдвиг количество единиц в $A_l$ может измениться только на 1. Действительно, если в $A_l$ добавились и ушли разные числа, то количество единиц изменилось на $1$ (увеличилось или уменьшилось), а если одинаковые — то не поменялось. Таким образом, сделав $m$ шагов, мы дойдем от $s_l$ до $\neg s_l$, причем количество единиц в $A_l$ будет изменяться не более, чем на $1$. Изначально оно было $a_l$, а станет — $2t - a_l$. Тогда выполняются неравенства: $a_k \le t \le 2t - a_k$. Левый знак верен просто потому, что мы так выбрали $s_k$, а правый, очевидно, равносилен первому. Таким образом, мы, изменяя a_l не больше, чем на единицу, пришли из $a_k$ в $2t - a_k$, причем число $t$ было между ними. Поэтому мы обязательно на каком-то шаге оказались с $a_{l'} = t$, то есть ровно половина единиц попала в $A_{l'}$, чего мы и хотели.

Заметим также, что мы доказали наличие одной пары, но на самом деле таких может быть больше. Давайте такие пары назовем особенными, а остальные — обычными.
[math]\triangleleft[/math]

А теперь решение

Пусть $k_i$ — количество самостоятельных единиц у $s_i$. Наконец вспомним про $x_0$. Рассмотрим два случая.

  1. $x_0 = 0$.
  • Тогда в каждой $s_i$ будет стоять вместо него $0$, то есть количество аргументов-единиц в точности равно количеству самостоятельных единиц.
  • Пусть $k_i /geqslant m + 1 \Rightarrow k_{i + m} \leqslant m - 1$ (и аналогично с противоположным знаком) $\Rightarrow$ в обычных парах одна $s_i$ будет равна $1$, а вторая $0$.
  • При нечетном количестве единиц особенных пар не будет, будет только ровно $m$ обычных пар, из каждой ровно одна $s_i$ даст единицу. Тогда среди всех $s_i$ будет ровно $m$ единиц, и, подставив их в конечную медиану, вместе с $\neg x_0 = 1$, получим ровно $m + 1$ аргумент, равный $1$. Тогда медиана вернет $1$, чего и должен вернуть $\oplus$ нечетного числа единиц.
  • При четном количестве у нас найдется особенная пара, а в этих $s_i$ и $\neg s_{i}$ ровно по $m$ самостоятельных единиц, а значит, они обе будут равны $0$. Тогда всего среди $s_i$ будет $\leqslant m - 1$ $s_i = 1$, значит, конечная медиана вернет $0$, что и нужно при $\oplus$ четного числа единиц.
  1. $x_0 = 1$
  • Тогда в каждой $s_i$ будет стоять вместо него $1$, то есть количество аргументов-единиц для $s_i$ на один больше количества самостоятельных единиц.
  • Пусть $k_i /geqslant m + 1 \Rightarrow k_{i + m} \leqslant m - 1$ (и аналогично с противоположным знаком) $\Rightarrow$ по-прежнему (тут с учетом $x_0 = 1$) в обычных парах одна $s_i$ будет равна $1$, а вторая $0$.
  • При нечетном количестве единиц особенных пар нет, будет снова только ровно $m$ обычных пар, из каждой ровно одна $s_i$ даст единицу. Тогда среди всех $s_i$ будет ровно $m$ единиц, и, подставив их в конечную медиану, вместе с $\neg x_0 = 0$, получим ровно $m$ аргументов, равных $1$. Тогда медиана вернет $0$, чего и должен вернуть $\oplus$ четного числа единиц.
  • При четном количестве у нас найдется особенная пара, а в этих $s_i$ и $\neg s_{i}$ ровно по $m$ самостоятельных единиц, а значит, они обе будут равны $1$, ведь вместе с $x_0 = 1$ среди аргументах медиан будет по $m + 1$ единиц. Тогда всего среди $s_i$ будет $\geqslant m + 1$ $s_i = 1$, значит, конечная медиана вернет $1$, что и нужно при $\oplus$ четного числа единиц.