1632
правки
Изменения
м
Задача из ДЗ №2. Доказать, что любую {{Теорема |statement= Любую монотонную самодвойственную [[Определение булевой функции|булеву функцию]] (self-'''D'''ual, '''M'''onotone), можно представить с использованием как некоторую [[Суперпозиции|суперпозицию]] функции медианы(majority function, median operator). |proof= Единственная унарная функция из класса DM {{---}} проектор. С помощью медианы её можно выразить так: <tex> P_1(x) = \langle x, x, x\rangle </tex>.
Для Бинарных функций из класса DM всего две.Рассмотрим эти функции :#<tex> ~f(0,0) < f(1,1)</tex> и <tex> f : (0,0) = \mathbb{B} \rightarrow \mathbb{B} lnot f(1,1)</tex>, удовлетворяют DM следовательно, <tex> f(0,0)=0</tex> и <tex> p_1. p_1 f(1,1)= 1 </tex>#<xtex> ~f(0,1) = \lnot f(1, x0)</tex>Из первого и второго пункта видно, xчто подходят только проекторы {{---}} <tex> P_1,P_2 </tex>.
ЗаметимТеперь покажем, что для функций <tex> f как эти функции можно представить с помощью медианы : \mathbb{B}^2 \rightarrow \mathbb{B} </tex> , всего 2 монотонных самодвойственных функции
Рассмотрим эти функции ''':'''#<tex> ~f(0,0)<f(1,1) P_1 = \land f(0langle x,0) = \bar f(1x,1)y \Rightarrow f(0rangle,0)P_2 =0 \land f(1langle x,1)=1 </tex>#<tex> ~f(0y,1) = y\bar f(1,0)</tex>Из пункта 1,2 видно, что подходят только функции <tex> p_1,p_2 rangle</tex>.
Теперь покажем, как эти функции можно представить с помощью медианы ''':'''
<tex> p_1 = <x, x, y>, p_2 = <x, y, y></tex>.
Для функций <tex> f : \mathbb{B}^3 \rightarrow \mathbb{B} </tex> только 4 функций принадлежат классу DMЗаметим, что для всех таких функций <tex> f(0,0,0) < f(1,1,1) \land f(0,0,0) = \bar f(1,1,1) \Rightarrow f(0,0,0) = 0 \land f(1,1,1) = 1 </tex> #<tex>f(1,0,0)= 1 \Rightarrow\left\{\begin{matrix} f(0,1,1) = \bar lnot f(1,0,0) = 0
Теперь рассмотрим произвольную монотонную самодвойственную функцию <tex> f : \mathbb{B}^n \rightarrow \mathbb{B} </tex> для '''n > 3'''. Обозначим аргументы <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>. Тогда введем три функции от n - 1 аргумента:
: <tex> f_1(x, y, \bar x) = f(x, y, y, \bar x) </tex>
: <tex> f_2(x, y, \bar x) = f(y, x, y, \bar x) </tex>
: <tex> f_3(x, y, \bar x) = f(y, y, x, \bar x) </tex>
Очевидно, они также самодвойственны и монотонны из определения f, и f можно выразить одной из функций <tex> f_1, f_2, f_3 </tex>, так как 2 из 3 аргументов точно совпадут. Теперь выразим f через <tex> f_1, f_2, f_3 </tex>:
: <tex> f(x_1 \dots x_n) = <f_1(x_1, x_2, \bar x), f_2(x_2, x_3, \bar x), f_3(x_3, x_1, \bar x)> </tex>
Докажем, что это так. Для удобства обозначений пусть <tex> x_1 = a, x_2 = b, x_3 = c </tex>. Тогда есть несколько случаев:
* <tex> a = b = c </tex>. Очевидно, выполняется.
* <tex> a = b \ne c </tex>. Тогда:
*: <tex> f = f(a, a, c, \bar x). f_1 = f(a, a, a, \bar x), f_2 = f(c, a, c, \bar x), f_3 = f(a, a, c, \bar x). </tex> Получили 2 случая:
** <tex> a = b = 0, c = 1. </tex>
**: Тогда можно упорядочить <tex> f_1, f_2, f_3 </tex> по возрастанию наборов их переменных(используя свойство их монотонности):
**: <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 = b = 1, c = 0 </tex>. Доказывается аналогично.
* <tex> a = c \ne b </tex> - симметричный случай.
* <tex> b = c \ne a </tex> - симметричный случай.
Внезапно, * [http://oeismath.orgstackexchange.com/questions/5523/A001206 количество таких функций при каждом nmonotone-self-dual-boolean-functions-clone Monotone self-dual boolean functions clone].[[Категория: Дискретная математика и алгоритмы]][[Категория: Булевы функции]]
rollbackEdits.php mass rollback
Только четыре тернарные функции принадлежат классу 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>
\\ 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 P_1 </tex> #<tex>f(0,1,0)= 1 \Rightarrow\left\{\begin{matrix} f(1,0,1) = \bar 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 P_2 </tex> #<tex>f(0,0,1)= 1 \Rightarrow\left\{\begin{matrix} f(1,1,0) = \bar 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 P_3 </tex> #<tex>f(1,0,0) = f(0,1,0) = f(0,0,1) = 0 \Rightarrow , </tex> следовательно, <tex> f= <\langle x_1,x_2,x_3> \rangle </tex> Покажем как эти функции представляются с помощью медианы ''':'''#<tex> p_1 P_1 = <\langle x, x, y>\rangle </tex>#<tex> p_2 P_2 = <\langle x, y, y>\rangle </tex> #<tex> p_3 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(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>.
:::*<tex> x_1 = x_2 = 1, x_3 = 0 </tex>. Доказывается аналогично.
}}
== Ссылки ==
* [http://oeis.org/A001206 Количество монотонных самодвойственных булевых функций от n аргументов].
