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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
{{Теорема
 
{{Теорема
 
  |statement= Любую монотонную самодвойственную [[Определение булевой функции|булеву функцию]] (self-'''D'''ual, '''M'''onotone) можно представить как некоторую [[Суперпозиции|суперпозицию]] функции медианы(majority function, median operator).
 
  |statement= Любую монотонную самодвойственную [[Определение булевой функции|булеву функцию]] (self-'''D'''ual, '''M'''onotone) можно представить как некоторую [[Суперпозиции|суперпозицию]] функции медианы(majority function, median operator).

Текущая версия на 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]

Ссылки