Представление функции класса DM с помощью медианы

Утверждение:

Любую монотонную самодвойственную булеву функцию (self-Dual, Monotone) можно представить с использованием медианы(majority function, median operator).

[math]\triangleright[/math]

Единственная унарная функция из класса DM — проектор. С помощью медианы её можно выразить так: [math] P_1(x) = \lt x, x, x\gt [/math]. Бинарных функций из класса DM всего две. Рассмотрим эти функции : [math] ~f(0,0)\lt f(1,1)[/math] и [math] f(0,0) = \lnot f(1,1)[/math], следовательно [math] f(0,0)=0[/math] и [math] f(1,1)=1 [/math] [math] ~f(0,1) = \lnot f(1,0)[/math] Из первого и второго пункта видно, что подходят только проекторы — [math] P_1,P_2 [/math] Теперь покажем, как эти функции можно представить с помощью медианы : [math] p_1 = \lt x, x, y\gt , p_2 = \lt x, y, y\gt [/math]. Только четыре тернарные функции принадлежат классу DM. Рассмотрим эти функции : Заметим, что для всех таких функций [math] f(0,0,0) \lt f(1,1,1) \land f(0,0,0) = \lnot f(1,1,1)[/math] следовательно [math] f(0,0,0) = 0 \land f(1,1,1) = 1 [/math] [math]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 [/math]   [math]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 [/math]   [math]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 [/math] [math]f(1,0,0) = f(0,1,0) = f(0,0,1) = 0 [/math] следовательно [math] f = \lt x_1,x_2,x_3\gt [/math] Покажем как эти функции представляются с помощью медианы : [math] p_1 = \lt x, x, y\gt [/math] [math] p_2 = \lt x, y, y\gt [/math] [math] p_3 = \lt x, z, z\gt [/math]. Теперь рассмотрим произвольную монотонную самодвойственную функцию [math] f : \mathbb{B}^n \rightarrow \mathbb{B} [/math] для n > 3. Обозначим аргументы [math] x_4, x_5 \dots x_n [/math] за [math] \lnot x [/math], то есть [math] f(x_1, x_2, x_3, x_4 \dots x_n) = f(x_1, x_2, x_3, \lnot x) [/math]. Тогда введем три функции от n - 1 аргумента: [math] f_1(x_1, x_2, \lnot x) = f(x_1, x_2, x_2, \lnot x) [/math] [math] f_2(x_2, x_3, \lnot x) = f(x_3, x_2, x_3, \lnot x) [/math] [math] f_3(x_3, x_1, \lnot x) = f(x_1, x_1, x_3, \lnot x) [/math] Очевидно, они также самодвойственны и монотонны из определения [math]f[/math], и [math]f[/math] можно выразить одной из функций [math] f_1, f_2, f_3 [/math], так как 2 из 3 аргументов точно совпадут. Теперь выразим [math]f[/math] через [math] f_1, f_2, f_3 [/math]: [math] f(x_1 \dots x_n) = \lt f_1(x_1, x_2, \lnot x), f_2(x_2, x_3, \lnot x), f_3(x_3, x_1, \lnot x)\gt [/math] [math] x_1 = x_2 = x_3 [/math]. Очевидно, выполняется. [math] x_1 = x_2 \ne x_3 [/math]. Тогда: [math] 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). [/math] Получили 2 случая: [math] a = b = 0, c = 1.[/math] Тогда можно упорядочить [math] f_1, f_2, f_3 [/math] по возрастанию наборов их переменных(используя свойство их монотонности): [math] f(0, 0, 0, \bar x) \le f(0, 0, 1, \bar x) \le f(1, 0, 1, \bar x) [/math]. Так как [math] f(0, 0, 1, \bar x) [/math] - между остальными, то оно и будет медианой [math] f_1, f_2, f_3 [/math]. [math] a = b = 1, c = 0 [/math]. Доказывается аналогично. [math] x_1 = x_3 \ne x_2 [/math] - симметричный случай. [math] x_2 = x_3 \ne x_1 [/math] - симметричный случай.

[math]\triangleleft[/math]

Интересный сайт,где можно посмотреть количество таких функций при каждом n.