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

Задача из ДЗ №2. Доказать, что любую монотонную самодвойственную функцию(self-Dual, Monotone), можно представить с использованием медианы.

Рассмотрим монотонную самодвойственную функцию [math] f : \mathbb{B}^n \rightarrow \mathbb{B} [/math]. Пусть n > 3, тогда обозначим аргументы [math] x_4, x_5 \dots x_n [/math] за [math] \bar x [/math], то есть [math] f(x_1, x_2, x_3, x_4 \dots x_n) = f(x_1, x_2, x_3, \bar x) [/math]. Тогда введем три функции от n - 1 аргумента:

[math] f_1(x, y, \bar x) = f(x, y, y, \bar x) [/math]

[math] f_2(x, y, \bar x) = f(y, x, y, \bar x) [/math]

[math] f_3(x, y, \bar x) = f(y, y, x, \bar x) [/math]

Очевидно, они также самодвойственны и монотонны из определения, и f можно выразить одной из функций [math] f_1, f_2, f_3 [/math], так как 2 из 3 аргументов точно совпадут. Теперь выразим f через [math] f_1, f_2, f_3 [/math]:

[math] f(x_1 \dots x_n) = \lt f_1(x_1, x_2, \bar x), f_2(x_2, x_3, \bar x), f_3(x_3, x_1, \bar x)\gt [/math]

Докажем, что это так. Для удобства обозначений пусть [math] x_1 = a, x_2 = b, x_3 = c [/math]. Тогда есть несколько случаев:

• [math] a = b = c [/math]. Очевидно, выполняется.
• [math] a = b \ne c [/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] a = c \ne b [/math] - симметричный случай.
• [math] b = c \ne a [/math] - симметричный случай.