Изменения
Нет описания правки
{{Утверждение
|statement= Любую монотонную самодвойственную [[Определение булевой функции|булеву функцию]] (self-'''D'''ual, '''M'''onotone) можно представить с использованием медианы(majority function, median operator).
|proof=
Единственная унарная функция из класса DM <tex> {{---</tex> }} проектор. С помощью медианы её можно выразить так: <tex> p_1 P_1(x) = <x, x, x> </tex>.
Бинарных функций из класса DM всего две.
Рассмотрим эти функции ''':'''
#<tex> ~f(0,0)<f(1,1) \land </tex> и <tex> f(0,0) = \bar lnot f(1,1)\Rightarrow </tex>, следовательно <tex> f(0,0)=0 \land </tex> и <tex> f(1,1)=1 </tex>#<tex> ~f(0,1) = \bar lnot f(1,0)</tex>Из первого и второго пункта видно, что подходят только функции проекторы {{---}} <tex> p_1P_1,p_2 P_2 </tex>
Теперь покажем, как эти функции можно представить с помощью медианы ''':'''
Только четыре тернарные функции принадлежат классу DM.Рассмотрим эти функции ''':'''
Заметим, что для всех таких функций
<tex> f(0,0,0) < f(1,1,1) \land f(0,0,0) = \bar lnot f(1,1,1) \Rightarrow </tex> следовательно <tex> 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
\\ 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>
#<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 </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 </tex>
#<tex>f(1,0,0) = f(0,1,0) = f(0,0,1) = 0 \Rightarrow </tex> следовательно <tex> f= <x_1,x_2,x_3> </tex>
Покажем как эти функции представляются с помощью медианы ''':'''
#<tex> p_1 = <x, x, y></tex>
Теперь рассмотрим произвольную монотонную самодвойственную функцию <tex> f : \mathbb{B}^n \rightarrow \mathbb{B} </tex> для '''n > 3'''. Обозначим аргументы <tex> x_4, x_5 \dots x_n </tex> за <tex> \bar lnot x </tex>, то есть <tex> f(x_1, x_2, x_3, x_4 \dots x_n) = f(x_1, x_2, x_3, \bar lnot x) </tex>. Тогда введем три функции от n - 1 аргумента:: <tex> f_1(xx_1, yx_2, \bar lnot x) = f(xx_1, yx_2, yx_2, \bar lnot x) </tex>: <tex> f_2(xx_2, yx_3, \bar lnot x) = f(yx_3, xx_2, yx_3, \bar lnot x) </tex>: <tex> f_3(xx_3, yx_1, \bar lnot x) = f(yx_1, yx_1, xx_3, \bar lnot 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) = <f_1(x_1, x_2, \bar lnot x), f_2(x_2, x_3, \bar lnot x), f_3(x_3, x_1, \bar lnot x)> </tex>Докажем, что это так. Для удобства обозначений пусть #<tex> x_1 = a, x_2 = b, x_3 = c </tex>. Тогда есть несколько случаев:* <tex> a = b = c </tex>. Очевидно, выполняется.* #<tex> a x_1 = b x_2 \ne c x_3 </tex>. Тогда''':*: '''<br><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 случая''':** '''<br><br><tex> a = b = 0, c = 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>.** <br><br><tex> a = b = 1, c = 0 </tex>. Доказывается аналогично.* # <tex> a x_1 = c x_3 \ne b x_2 </tex> - симметричный случай.* # <tex> b x_2 = c x_3 \ne a x_1 </tex> - симметричный случай.
}}
