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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
Задача из ДЗ №2. Доказать, что любую монотонную самодвойственную функцию(self-'''D'''ual, '''M'''onotone), можно представить с использованием медианы(majority function, median operator).
+
{{Утверждение
 
+
|statement= Любую монотонную самодвойственную функцию(self-'''D'''ual, '''M'''onotone) можно представить с использованием медианы(majority function, median operator).
Для функций <tex> f : \mathbb{B} \rightarrow \mathbb{B} </tex>, удовлетворяют DM <tex> p_1. p_1 = <x, x, x> </tex>.  
+
|proof=
 
+
Единственная унарная функция из класса DM - проектор. С помощью медианы её  можно выразить так:  
Заметим, что для функций <tex> f : \mathbb{B}^2 \rightarrow \mathbb{B} </tex> , всего 2 монотонных самодвойственных  функции
+
<tex> p_1 = <x, x, x> </tex>.  
  
 +
Бинарных функций из класса DM всего две.
 
Рассмотрим эти функции ''':'''
 
Рассмотрим эти функции ''':'''
 
#<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,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>
 
#<tex> ~f(0,1) = \bar f(1,0)</tex>
Из пункта 1,2 видно, что  подходят только функции <tex> p_1,p_2 </tex>
+
Из первого и второго пункта видно, что  подходят только функции <tex> p_1,p_2 </tex>
  
 
Теперь покажем, как эти функции можно представить с помощью медианы ''':'''
 
Теперь покажем, как эти функции можно представить с помощью медианы ''':'''
Строка 16: Строка 17:
  
  
Для функций <tex> f : \mathbb{B}^3 \rightarrow \mathbb{B} </tex> только 4 функций принадлежат классу DM
+
Только четыре тернарные  функции принадлежат классу 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(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>
  
Строка 57: Строка 60:
 
* <tex> a = c \ne b </tex> - симметричный случай.
 
* <tex> a = c \ne b </tex> - симметричный случай.
 
* <tex> b = c \ne a </tex> - симметричный случай.
 
* <tex> b = c \ne a </tex> - симметричный случай.
 
+
}}
  
  
 
Внезапно, [http://oeis.org/A001206 количество таких функций при каждом n].
 
Внезапно, [http://oeis.org/A001206 количество таких функций при каждом n].

Версия 02:25, 5 декабря 2011

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

Единственная унарная функция из класса DM - проектор. С помощью медианы её можно выразить так: [math] p_1 = \lt x, x, x\gt [/math].

Бинарных функций из класса DM всего две. Рассмотрим эти функции :

  1. [math] ~f(0,0)\lt f(1,1) \land f(0,0) = \bar f(1,1)\Rightarrow f(0,0)=0 \land f(1,1)=1 [/math]
  2. [math] ~f(0,1) = \bar 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) = \bar f(1,1,1) \Rightarrow f(0,0,0) = 0 \land f(1,1,1) = 1 [/math]

  1. [math]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 [/math]  
  2. [math]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 [/math]  
  3. [math]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 [/math]
  4. [math]f(1,0,0) = f(0,1,0) = f(0,0,1) = 0 \Rightarrow f= \lt x_1,x_2,x_3\gt [/math]

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

  1. [math] p_1 = \lt x, x, y\gt [/math]
  2. [math] p_2 = \lt x, y, y\gt [/math]
  3. [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] \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] - симметричный случай.
[math]\triangleleft[/math]


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