Изменения

Задача из ДЗ №2. Доказать, что любую {{Теорема |statement= Любую монотонную самодвойственную [[Определение булевой функции|булеву функцию]] (self-'''D'''ual, '''M'''onotone), можно представить с использованием как некоторую [[Суперпозиции|суперпозицию]] функции медианы(majority function, median operator). |proof= Единственная унарная функция из класса DM {{---}} проектор. С помощью медианы её можно выразить так: <tex> P_1(x) = \langle x, x, x\rangle </tex>.

Для n Бинарных функций из класса DM всего две.Рассмотрим эти функции :#<tex> ~f(0,0) < f(1,1)</tex> и <tex> f(0,0) = \lnot f(1, удовлетворяют DM 1)</tex>, следовательно, <tex> f(0,0)=0</tex> и <tex> p_1. p_1 f(1,1)= 1 <x/tex>#<tex> ~f(0, x1) = \lnot f(1,0)</tex>Из первого и второго пункта видно, xчто подходят только проекторы {{---}} <tex> P_1,P_2 </tex>.

Для n = 2Теперь покажем, удовлетворяют DM <tex> p_1, p_2. p_1 = <x, x, y>. p_2 = <x, y, y></tex>.как эти функции можно представить с помощью медианы :

Для n = 3, удовлетворяют DM <tex> p_1, p_2, p_3 </tex> и собственно медиана. <tex> p_1 P_1 = <\langle x, x, y>\rangle, p_2 P_2 = <\langle x, y, y> , p_3 = <x, z, z> \rangle</tex>.   Только четыре тернарные функции принадлежат классу DM. Рассмотрим эти функции : Заметим, что для всех таких функций

<tex> f(0,0,0) < f(1,1,1)</tex> и <tex> f(0,0,0) = \lnot f(1,1,1), </tex> следовательно <tex>, f(0,0,0) = 0 </tex> и <tex> f(1,1,1) = 1 </tex> #<tex>f(1,0,0)= 1 \Rightarrow\left\{\begin{matrix} f(0,1,1) = \lnot f(1,0,0) = 0 \\ f(0,0,1) = f(0,1,0)= 0 \\ f(1,0,1) = f(1,1,0) = 1\end{matrix}\right.\Rightarrow f=P_1 </tex> &nbsp;#<tex>f(0,1,0)= 1 \Rightarrow\left\{\begin{matrix} f(1,0,1) = \lnot f(0,1,0) = 0 \\ f(0,0,1) = f(1,0,0)= 0 \\ f(1,1,0) = f(0,1,1)= 1\end{matrix}\right.\Rightarrow f=P_2 </tex> &nbsp;#<tex>f(0,0,1)= 1 \Rightarrow\left\{\begin{matrix} f(1,1,0) = \lnot f(1,0,0) = 0 \\ f(1,0,0) = f(0,1,0) = 0 \\ f(1,0,1) = f(0,1,1) = 1\end{matrix}\right.\Rightarrow f=P_3 </tex> #<tex>f(1,0,0) = f(0,1,0) = f(0,0,1) = 0, </tex> следовательно, <tex> f = \langle x_1,x_2,x_3\rangle </tex> Покажем как эти функции представляются с помощью медианы :#<tex> P_1 = \langle x, x, y\rangle </tex>#<tex> P_2 = \langle x, y, y\rangle </tex> #<tex> P_3 = \langle x, z, z\rangle </tex>.   Теперь рассмотрим произвольную монотонную самодвойственную функцию <tex> f : \mathbb{B}^n \rightarrow \mathbb{B} </tex> для '''<tex> n > 3'''</tex>. Обозначим аргументы <tex> x_4, x_5 \dots x_n </tex> за <tex> \bar x </tex>, то есть <tex> f(x_1, x_2, x_3, x_4 \dots x_n) = f(x_1, x_2, x_3, \bar x) </tex>. Тогда введем три функции от <tex>n - 1 </tex> аргумента:: <tex> f_1(xx_1, yx_2, \bar x) = f(xx_1, yx_2, yx_2, \bar x) </tex>: <tex> f_2(xx_2, yx_3, \bar x) = f(yx_3, xx_2, yx_3, \bar x) </tex>: <tex> f_3(xx_3, yx_1, \bar x) = f(yx_1, yx_1, xx_3, \bar x) </tex>Очевидно, они также самодвойственны и монотонны из определения <tex>f</tex>, и <tex>f </tex> можно выразить одной из функций <tex> f_1, f_2, f_3 </tex>, так как 2 два из 3 трех аргументов точно совпадут. Теперь выразим <tex>f </tex> через <tex> f_1, f_2, f_3 </tex>:: <tex> f(x_1 \dots x_n) = <\langle f_1(x_1, x_2, \bar x), f_2(x_2, x_3, \bar x), f_3(x_3, x_1, \bar x)> \rangle </tex>Докажем, что это так. Для удобства обозначений пусть #Все три аргумента равны : <tex> x_1 = a, x_2 = b, x_3 = c </tex>, тогда, очевидно, что равенство выполняется. Тогда есть несколько случаев#Равны два аргумента :* <tex> a x_1 = b x_2 \ne x_3 </tex> (случаи <tex> x_1 = c x_3 \ne x_2 </tex>. Очевидно, выполняется.* и <tex> a x_2 = b x_3 \ne c x_1 </tex>доказываются аналогично). Тогда:*:: <tex> f = f(ax_1, ax_1, cx_3, \bar x). </tex>, <tex> f_1 = f(ax_1, ax_1, ax_1, \bar x)</tex>, <tex>f_2 = f(cx_3, ax_1, cx_3, \bar x)</tex>, <tex>f_3 = f(ax_1, ax_1, cx_3, \bar x). </tex> Получили 2 .Рассмотрим два случая:*:::* <tex> a x_1 = b x_2 = 0, c x_3 = 1. </tex>**: <br> Тогда можно упорядочить <tex> f_1, f_2, f_3 </tex> по возрастанию наборов их переменных(используя свойство их монотонности):**: <br> <tex> f(0, 0, 0, \bar x) \le f(0, 0, 1, \bar x) \le f(1, 0, 1, \bar x) </tex>. Так как <tex> f(0, 0, 1, \bar x) </tex> - зажато между двумя остальнымифункциями, то оно она и будет медианой <tex> f_1, f_2, f_3 </tex>.*:::* <tex> a x_1 = b x_2 = 1, c x_3 = 0 </tex>. Доказывается аналогично. }}== Ссылки ==* <tex> a = c \ne b <[http://tex> - симметричный случайoeis.* <tex> b = c \ne a <org/tex> - симметричный случайA001206 Количество монотонных самодвойственных булевых функций от n аргументов].Все!

P* [http://math.Sstackexchange. У меня такое чувство, что классу DM принадлежат только проекторы и их комбинации(точнее, дизъюнкция попарных конъюнкций). Если представить вектора значений аргументов в виде n com/questions/5523/monotone-self-dual-boolean- мерного куба, то если функция на всех его гранях, содержащих вершину <tex> (1 \dots 1) </tex>, будет равна 1, то на противоположной грани, везде будет 0. Это для проекторов. А дизъюнкция попарных конъюнкций проекторов functions- попарные пересечения граней, то есть все ребра nclone Monotone self-мерного куба, содержащие вершину <tex> (1 \dots 1) </tex>dual boolean functions clone]. Такая функция также будет самодвойственной [[Категория: Дискретная математика и монотонной. Не знаю только как более математически это обосновать.алгоритмы]][[Категория: Булевы функции]]