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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (конспект сделан в самообразовательных целях и не претендует на бонусные баллы(хотя я и не против :D ))
 
м (hell yeah!)
Строка 1: Строка 1:
 
Задача из ДЗ №2. Доказать, что любую монотонную самодвойственную функцию(self-'''D'''ual, '''M'''onotone), можно представить с использованием медианы.
 
Задача из ДЗ №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 аргумента:
+
Для n = 1, удовлетворяют DM <tex> p_1. p_1 = <x, x, x> </tex>.
 +
 
 +
Для n = 2, удовлетворяют DM <tex> p_1, p_2. p_1 = <x, x, y>. p_2 = <x, y, y></tex>.
 +
 
 +
Для n = 3, удовлетворяют DM <tex> p_1, p_2, p_3 </tex> и собственно медиана. <tex> p_1 = <x, x, y>, p_2 = <x, y, y> , 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>
 
: <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_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>
 
: <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>:
+
Очевидно, они также самодвойственны и монотонны из определения f, и 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> 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> x_1 = a, x_2 = b, x_3 = c </tex>. Тогда есть несколько случаев:
Строка 12: Строка 18:
 
*: <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> 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> a = b = 0, c = 1. </tex>
**: Тогда можно упорядочить <tex> f_1, f_2, f_3 </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> 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 = b = 1, c = 0 </tex>. Доказывается аналогично.
 
* <tex> a = c \ne b </tex> - симметричный случай.
 
* <tex> a = c \ne b </tex> - симметричный случай.
 
* <tex> b = c \ne a </tex> - симметричный случай.
 
* <tex> b = c \ne a </tex> - симметричный случай.
 +
Все!
 +
 +
P.S. У меня такое чувство, что классу DM принадлежат только проекторы и их комбинации(точнее, дизъюнкция попарных конъюнкций). Если представить вектора значений аргументов в виде n - мерного куба, то если функция на всех его гранях, содержащих вершину <tex> (1 \dots 1) </tex>, будет равна 1, то на противоположной грани, везде будет 0. Это для проекторов. А дизъюнкция попарных конъюнкций проекторов - попарные пересечения граней, то есть все ребра n-мерного куба, содержащие вершину <tex> (1 \dots 1) </tex>. Такая функция также будет самодвойственной и монотонной. Не знаю только как более математически это обосновать.

Версия 10:35, 3 января 2011

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

Для n = 1, удовлетворяют DM [math] p_1. p_1 = \lt x, x, x\gt [/math].

Для n = 2, удовлетворяют DM [math] p_1, p_2. p_1 = \lt x, x, y\gt . p_2 = \lt x, y, y\gt [/math].

Для n = 3, удовлетворяют DM [math] p_1, p_2, p_3 [/math] и собственно медиана. [math] p_1 = \lt x, x, y\gt , p_2 = \lt x, y, y\gt , 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] \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, и 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] - симметричный случай.

Все!

P.S. У меня такое чувство, что классу DM принадлежат только проекторы и их комбинации(точнее, дизъюнкция попарных конъюнкций). Если представить вектора значений аргументов в виде n - мерного куба, то если функция на всех его гранях, содержащих вершину [math] (1 \dots 1) [/math], будет равна 1, то на противоположной грани, везде будет 0. Это для проекторов. А дизъюнкция попарных конъюнкций проекторов - попарные пересечения граней, то есть все ребра n-мерного куба, содержащие вершину [math] (1 \dots 1) [/math]. Такая функция также будет самодвойственной и монотонной. Не знаю только как более математически это обосновать.