Изменения

Задача из ДЗ №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 : \mathbb{B}^n \rightarrow \mathbb{B} (0,0,0) </tex> для '''n > 3'''. Обозначим аргументы <tex> x_4f(1,1, x_5 \dots x_n 1)</tex> за <tex> \bar x </tex>, то есть и <tex> f(x_10, x_20, x_3, x_4 \dots x_n0) = \lnot f(x_11, x_21, x_31), \bar x) </tex>. Тогда введем три функции от n - 1 аргумента:: следовательно <tex> f_1(x, y, \bar x) = f(x0, y0, y, \bar x0) = 0 </tex>: и <tex> f_2f(x1, y1, \bar x1) = f(y, x, y, \bar x) 1 </tex>: #<tex> f_3f(x1, y0, \bar x0) = 1 \Rightarrow\left\{\begin{matrix} f(y0, y, x1, 1) = \bar x) </tex>Очевидно, они также самодвойственны и монотонны из определения lnot f(1, и f можно выразить одной из функций <tex> f_10, f_2, f_3 </tex>, так как 2 из 3 аргументов точно совпадут. Теперь выразим 0) = 0 \\ f через <tex> f_1(0, f_20, f_3 </tex>:: <tex> f(x_1 \dots x_n1) = <f_1f(x_10, x_21, 0)= 0 \bar x), f_2\ f(x_21, x_30, \bar x1), f_3= f(x_31, x_11, \bar x0)> </tex>= 1Докажем, что это так\end{matrix}\right. Для удобства обозначений пусть <tex> x_1 = a, x_2 = b, x_3 \Rightarrow f= c P_1 </tex>. Тогда есть несколько случаев:&nbsp;* #<tex> a = b = c </tex>. Очевидноf(0,1, выполняется.* <tex> a 0)= b 1 \Rightarrow\ne c </tex>. Тогда:*: <tex> left\{\begin{matrix} f (1,0,1) = \lnot f(a0, a1, c, \bar x0). f_1 = 0 \\ f(a0, a0, a, \bar x1), f_2 = f(c1, a0, c, \bar x0), f_3 = 0 \\ f(a1, a1, c, \bar x0). </tex> Получили 2 случая:** <tex> a = b = f(0, c 1,1)= 1\end{matrix}\right. \Rightarrow f=P_2 </tex>&nbsp;**: Тогда можно упорядочить #<tex> f_1f(0, f_20, f_3 </tex> по возрастанию наборов их переменных1)= 1 \Rightarrow\left\{\begin{matrix} f(используя свойство их монотонности1,1,0):**: <tex> = \lnot f(1,0, 0, ) = 0, \bar x) \le f(1,0, 0) = f(0, 1, 0) = 0 \bar x) \le f(1, 0, 1) = f(0, 1,1) = 1\bar x) end{matrix}\right.\Rightarrow f=P_3 </tex>. Так как #<tex> f(1,0, 0) = f(0, 1, \bar x0) = f(0,0,1) = 0, </tex> - между остальнымиследовательно, то оно и будет медианой <tex> f_1f = \langle x_1, f_2x_2, f_3 x_3\rangle </tex>.** Покажем как эти функции представляются с помощью медианы :#<tex> a P_1 = b = 1\langle x, x, c = 0 y\rangle </tex>. Доказывается аналогично.* #<tex> a P_2 = c \ne b langle x, y, y\rangle </tex> - симметричный случай.* #<tex> b P_3 = c \ne a 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(x_1, x_2, \bar x) = f(x_1, x_2, x_2, \bar x) </tex>: <tex> f_2(x_2, x_3, \bar x) = f(x_3, x_2, x_3, \bar x) </tex>: <tex> f_3(x_3, x_1, \bar x) = f(x_1, x_1, x_3, \bar x) </tex>Очевидно, они также самодвойственны и монотонны из определения <tex>f</tex>, и <tex>f</tex> можно выразить одной из функций <tex> f_1, f_2, f_3 </tex>, так как два из трех аргументов точно совпадут. Теперь выразим <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 = x_2 = x_3 </tex>, тогда, очевидно, что равенство выполняется.#Равны два аргумента : <tex> x_1 = x_2 \ne x_3 </tex> (случаи <tex> x_1 = x_3 \ne x_2 </tex> и второй<tex> x_2 = x_3 \ne x_1 </tex> доказываются аналогично). Тогда :::<tex> f = f(x_1, x_1, x_3, \bar x)</tex>, <tex> f_1 = f(x_1, x_1, x_1, \bar x)</tex>, <tex>f_2 = f(x_3, x_1, x_3, \bar x)</tex>, <tex>f_3 = f(x_1, x_1, x_3, \bar x)</tex>.Рассмотрим два случая ::::*<tex> x_1 = x_2 = 0, 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>.[[Файл:2::*<tex> x_1 = x_2 = 1, x_3 = 0 </tex>. Доказывается аналогично.png]]

И какая-то левая функция:}}== Ссылки ==* [[Файлhttp:5//oeis.png]org/A001206 Количество монотонных самодвойственных булевых функций от n аргументов].

Внезапно, * [http://oeismath.orgstackexchange.com/questions/5523/A001206 количество таких функций при каждом nmonotone-self-dual-boolean-functions-clone Monotone self-dual boolean functions clone].[[Категория: Дискретная математика и алгоритмы]][[Категория: Булевы функции]]