Изменения
Нет описания правки
Задача из ДЗ №2. Доказать, что любую монотонную самодвойственную функцию(self-'''D'''ual, '''M'''onotone), можно представить с использованием медианы(majority function, median operator).
Для n функций <tex> f : \mathbb{B} \rightarrow \mathbb{B} </tex>, удовлетворяют DM <tex> p_1. p_1 = <x, x, x> </tex>. Заметим, что для функций <tex> f : \mathbb{B}^2 \rightarrow \mathbb{B} </tex> , всего 2 монотонных самодвойственных функции Рассмотрим эти функции ''':'''#<tex> ~f(0,0)<f(1,1) \land f(0,0) = \bar f(1,1)\Rightarrow f(0,0)=0 \land f(1,1)=1 </tex>#<tex> ~f(0,1) = \bar f(1,0)</tex>Из пункта 1, удовлетворяют 2 видно, что подходят только функции <tex> p_1,p_2 </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 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 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 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 f= <x_1,x_2,x_3> </tex> Покажем как эти функции представляются с помощью медианы ''':'''#<tex> p_1 = <x, x, y></tex>#<tex> p_2 = <x, y, y></tex> #<tex> p_3 = <x, z, z> </tex>.
Теперь рассмотрим произвольную монотонную самодвойственную функцию <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>
