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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (hell yeah!)
м (rollbackEdits.php mass rollback)
 
(не показано 27 промежуточных версий 6 участников)
Строка 1: Строка 1:
Задача из ДЗ №2. Доказать, что любую монотонную самодвойственную функцию(self-'''D'''ual, '''M'''onotone), можно представить с использованием медианы.
+
{{Теорема
 +
|statement= Любую монотонную самодвойственную [[Определение булевой функции|булеву функцию]] (self-'''D'''ual, '''M'''onotone) можно представить как некоторую [[Суперпозиции|суперпозицию]] функции медианы(majority function, median operator).
 +
|proof=
 +
Единственная унарная функция из класса DM {{---}} проектор. С помощью медианы её  можно выразить так:
 +
<tex>  P_1(x) = \langle x, x, x\rangle  </tex>.  
  
Для n = 1, удовлетворяют DM <tex> p_1. p_1 = <x, x, x> </tex>.
+
Бинарных функций из класса DM всего две.
 +
Рассмотрим эти функции :
 +
#<tex> ~f(0,0) < f(1,1)</tex> и <tex> f(0,0) = \lnot f(1,1)</tex>, следовательно, <tex> f(0,0)=0</tex> и <tex> f(1,1)=1 </tex>
 +
#<tex> ~f(0,1) = \lnot f(1,0)</tex>
 +
Из первого и второго пункта видно, что  подходят только проекторы {{---}} <tex> P_1,P_2 </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> P_1 = \langle  x, x, y \rangle, P_2 = \langle  x, y, y\rangle</tex>.
 +
 
 +
 
 +
 
 +
Только четыре тернарные  функции принадлежат классу DM. Рассмотрим эти функции :
 +
 
 +
Заметим, что для всех таких функций
 
   
 
   
Теперь рассмотрим произвольную монотонную самодвойственную функцию <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(0,0,0) < f(1,1,1)</tex> и <tex> f(0,0,0) = \lnot f(1,1,1), </tex> следовательно <tex>, f(0,0,0) = 0 </tex> и <tex> f(1,1,1) = 1 </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(1,0,0)= 1 \Rightarrow\left\{\begin{matrix} f(0,1,1) = \lnot f(1,0,0) = 0
: <tex> f_3(x, y, \bar x) = f(y, y, x, \bar x) </tex>
+
\\ f(0,0,1) = f(0,1,0)= 0
Очевидно, они также самодвойственны и монотонны из определения f, и f можно выразить одной из функций <tex> f_1, f_2, f_3 </tex>, так как 2 из 3 аргументов точно совпадут. Теперь выразим f через <tex> f_1, f_2, f_3 </tex>:
+
\\ f(1,0,1) = f(1,1,0) = 1
: <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>
+
\end{matrix}\right.\Rightarrow f=P_1 </tex> &nbsp;
Докажем, что это так. Для удобства обозначений пусть <tex> x_1 = a, x_2 = b, x_3 = c </tex>. Тогда есть несколько случаев:
+
#<tex>f(0,1,0)= 1 \Rightarrow\left\{\begin{matrix} f(1,0,1) = \lnot f(0,1,0) = 0
* <tex> a = b = c </tex>. Очевидно, выполняется.
+
\\ f(0,0,1) = f(1,0,0)= 0
* <tex> a = b \ne c </tex>. Тогда:
+
\\ f(1,1,0) = f(0,1,1)= 1
*: <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 случая:
+
\end{matrix}\right.\Rightarrow f=P_2 </tex> &nbsp;
** <tex> a = b = 0, c = 1. </tex>
+
#<tex>f(0,0,1)= 1 \Rightarrow\left\{\begin{matrix} f(1,1,0) = \lnot f(1,0,0) = 0
**: Тогда можно упорядочить <tex> f_1, f_2, f_3 </tex> по возрастанию наборов их переменных(используя свойство их монотонности):
+
\\ f(1,0,0) = f(0,1,0) = 0
**: <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>.
+
\\ f(1,0,1) = f(0,1,1) = 1
** <tex> a = b = 1, c = 0 </tex>. Доказывается аналогично.
+
\end{matrix}\right.\Rightarrow f=P_3 </tex>
* <tex> a = c \ne b </tex> - симметричный случай.
+
#<tex>f(1,0,0) = f(0,1,0) = f(0,0,1) = 0, </tex> следовательно, <tex> f = \langle x_1,x_2,x_3\rangle  </tex>
* <tex> b = c \ne a </tex> - симметричный случай.
+
Покажем как эти функции представляются с помощью медианы :
Все!
+
#<tex> P_1 = \langle x, x, y\rangle </tex>
 +
#<tex> P_2 = \langle x, y, y\rangle </tex>
 +
#<tex> P_3 = \langle x, z, z\rangle  </tex>.
 +
 
 +
 
 +
 
 +
Теперь рассмотрим произвольную монотонную самодвойственную функцию <tex> f : \mathbb{B}^n \rightarrow \mathbb{B} </tex> для <tex> n > 3 </tex>. Обозначим аргументы <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>. Тогда введем три функции от <tex>n - 1</tex> аргумента :
 +
: <tex> f_1(x_1, x_2, \bar x) = f(x_1, x_2, x_2, \bar x) </tex>
 +
: <tex> f_2(x_2, x_3, \bar x) = f(x_3, x_2, x_3, \bar x) </tex>
 +
: <tex> f_3(x_3, x_1, \bar x) = f(x_1, x_1, x_3, \bar x) </tex>
 +
Очевидно, они также самодвойственны и монотонны из определения <tex>f</tex>, и <tex>f</tex> можно выразить одной из функций <tex> f_1, f_2, f_3 </tex>, так как два из трех аргументов точно совпадут. Теперь выразим <tex>f</tex> через <tex> f_1, f_2, f_3 </tex> :
 +
: <tex> f(x_1 \dots x_n) = \langle f_1(x_1, x_2, \bar x), f_2(x_2, x_3, \bar x), f_3(x_3, x_1, \bar x) \rangle  </tex>
 +
#Все три аргумента равны : <tex> x_1 = x_2 = x_3 </tex>, тогда, очевидно, что равенство выполняется.
 +
#Равны два аргумента : <tex> x_1 = x_2 \ne x_3 </tex>  (случаи <tex> x_1 = x_3 \ne x_2 </tex> и <tex> x_2 = x_3 \ne x_1 </tex> доказываются аналогично). Тогда :
 +
::<tex> f = f(x_1, x_1, x_3, \bar x)</tex>, <tex> f_1 = f(x_1, x_1, x_1, \bar x)</tex>, <tex>f_2 = f(x_3, x_1, x_3, \bar x)</tex>, <tex>f_3 = f(x_1, x_1, x_3, \bar x)</tex>.Рассмотрим два случая :
 +
:::*<tex> x_1 = x_2 = 0, x_3 = 1.</tex> <br> Тогда можно упорядочить <tex> f_1, f_2, f_3 </tex> по возрастанию наборов их переменных (используя свойство их монотонности):<br> <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> x_1 = x_2 = 1, x_3 = 0 </tex>. Доказывается аналогично.
 +
 
 +
}}
 +
== Ссылки ==
 +
* [http://oeis.org/A001206 Количество  монотонных самодвойственных булевых функций от n аргументов].
  
P.S. У меня такое чувство, что классу DM принадлежат только проекторы и их комбинации(точнее, дизъюнкция попарных конъюнкций). Если представить вектора значений аргументов в виде n - мерного куба, то если функция на всех его гранях, содержащих вершину <tex> (1 \dots 1) </tex>, будет равна 1, то на противоположной грани, везде будет 0. Это для проекторов. А дизъюнкция попарных конъюнкций проекторов - попарные пересечения граней, то есть все ребра n-мерного куба, содержащие вершину <tex> (1 \dots 1) </tex>. Такая функция также будет самодвойственной и монотонной. Не знаю только как более математически это обосновать.
+
* [http://math.stackexchange.com/questions/5523/monotone-self-dual-boolean-functions-clone Monotone self-dual boolean functions clone].
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Булевы функции]]

Текущая версия на 19:35, 4 сентября 2022

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

Единственная унарная функция из класса DM — проектор. С помощью медианы её можно выразить так: [math] P_1(x) = \langle x, x, x\rangle [/math].

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

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

Из первого и второго пункта видно, что подходят только проекторы — [math] P_1,P_2 [/math]

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

[math] P_1 = \langle x, x, y \rangle, P_2 = \langle x, y, y\rangle[/math].


Только четыре тернарные функции принадлежат классу DM. Рассмотрим эти функции :

Заметим, что для всех таких функций

[math] f(0,0,0) \lt f(1,1,1)[/math] и [math] f(0,0,0) = \lnot f(1,1,1), [/math] следовательно [math], f(0,0,0) = 0 [/math] и [math] f(1,1,1) = 1 [/math]

  1. [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]  
  2. [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]  
  3. [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]
  4. [math]f(1,0,0) = f(0,1,0) = f(0,0,1) = 0, [/math] следовательно, [math] f = \langle x_1,x_2,x_3\rangle [/math]

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

  1. [math] P_1 = \langle x, x, y\rangle [/math]
  2. [math] P_2 = \langle x, y, y\rangle [/math]
  3. [math] P_3 = \langle x, z, z\rangle [/math].


Теперь рассмотрим произвольную монотонную самодвойственную функцию [math] f : \mathbb{B}^n \rightarrow \mathbb{B} [/math] для [math] n \gt 3 [/math]. Обозначим аргументы [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]. Тогда введем три функции от [math]n - 1[/math] аргумента :

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

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

[math] f(x_1 \dots x_n) = \langle f_1(x_1, x_2, \bar x), f_2(x_2, x_3, \bar x), f_3(x_3, x_1, \bar x) \rangle [/math]
  1. Все три аргумента равны : [math] x_1 = x_2 = x_3 [/math], тогда, очевидно, что равенство выполняется.
  2. Равны два аргумента : [math] x_1 = x_2 \ne x_3 [/math] (случаи [math] x_1 = x_3 \ne x_2 [/math] и [math] x_2 = x_3 \ne x_1 [/math] доказываются аналогично). Тогда :
[math] f = f(x_1, x_1, x_3, \bar x)[/math], [math] f_1 = f(x_1, x_1, x_1, \bar x)[/math], [math]f_2 = f(x_3, x_1, x_3, \bar x)[/math], [math]f_3 = f(x_1, x_1, x_3, \bar x)[/math].Рассмотрим два случая :
  • [math] x_1 = x_2 = 0, x_3 = 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] x_1 = x_2 = 1, x_3 = 0 [/math]. Доказывается аналогично.
[math]\triangleleft[/math]

Ссылки