1679
правок
Изменения
м
конспект сделан в самообразовательных целях и не претендует на бонусные баллы(хотя я и не против :D )
Задача из ДЗ №2. Доказать, что любую монотонную самодвойственную функцию(self-'''D'''ual, '''M'''onotone), можно представить с использованием медианы.
Рассмотрим монотонную самодвойственную функцию <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 можно выразить одной из функций <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> - симметричный случай.
Рассмотрим монотонную самодвойственную функцию <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 можно выразить одной из функций <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> - симметричный случай.
