Обсуждение участника:Sancho20021 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема о нижней оценке на число элементов в схеме)
 
(не показано 15 промежуточных версий этого же участника)
Строка 12: Строка 12:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Линейная программа''' {{---}} список строк вида <tex>(a, (i_1, \ldots, i_k))</tex>, где <tex>a \in B</tex> (базис), <tex>a: \mathbb B^k \rightarrow \mathbb B</tex>, <tex>i_j</tex> {{---}} индексы переменных.
+
'''[[Представление_булевых_функций_линейными_программами#Линейные_программы|Линейная программа]]''' {{---}} список строк вида <tex>(a, (i_1, \ldots, i_k))</tex>, где <tex>a \in B</tex> (базис), <tex>a: \mathbb B^k \rightarrow \mathbb B</tex>, <tex>i_j</tex> {{---}} индексы переменных.
 
}}
 
}}
 
'''Пример линейной программы'''
 
'''Пример линейной программы'''
Строка 30: Строка 30:
 
'''Длина''' линейной программы {{---}} количество строк.
 
'''Длина''' линейной программы {{---}} количество строк.
 
{{Теорема
 
{{Теорема
|statement= Для булевой функции <tex>f \; \exists</tex> линейная программа длины <tex>r \Leftrightarrow \exists </tex> схема, использующая <tex>r</tex> функциональных элементов.
+
|statement= Для булевой функции <tex>f </tex> существует линейная программа длины <tex>r</tex> тогда и только тогда, когда существует схема, использующая <tex>r</tex> функциональных элементов.
 
|proof=Чтобы построить по схеме программу, можно занумеровать элементы схемы в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки#Топологическая_сортировка|топологической сортировки]], и для каждого элемента <tex>m</tex> с функцией <tex>a</tex> и входами <tex>i_1, \ldots, i_k</tex> сопоставить строчку линейной программы с номером <tex>m</tex> вида <tex>(a, (i_1, \ldots, i_k))</tex>.  
 
|proof=Чтобы построить по схеме программу, можно занумеровать элементы схемы в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки#Топологическая_сортировка|топологической сортировки]], и для каждого элемента <tex>m</tex> с функцией <tex>a</tex> и входами <tex>i_1, \ldots, i_k</tex> сопоставить строчку линейной программы с номером <tex>m</tex> вида <tex>(a, (i_1, \ldots, i_k))</tex>.  
  
Строка 37: Строка 37:
 
===Оценка на количество линейных программ над <tex>\{\downarrow\}</tex> длины <tex>r</tex>===
 
===Оценка на количество линейных программ над <tex>\{\downarrow\}</tex> длины <tex>r</tex>===
 
<tex>n</tex> {{---}} количество аргументов булевой функции.
 
<tex>n</tex> {{---}} количество аргументов булевой функции.
 +
 +
<tex>\downarrow</tex> {{---}} стрелка Пирса, является сама по себе базисом булевых функций.
 +
 +
В первой строчке мы можем выбрать одну из <tex>n</tex> переменных (<tex>x_1, \ldots, x_n</tex>) и применить к ней <tex>\downarrow</tex>. Получим еще одну переменную <tex>y_1</tex>. Во второй строчке программы нам на выбор доступны уже <tex>n+1</tex> переменных (<tex>x_1, \ldots, x_n, y_1</tex>). В общем случае на <tex>i</tex>-й строчке (нумерация с единицы) мы можем применить стрелку Пирса к одной из <tex>n+i-1</tex> переменных. Из этого следует формула ниже.
  
 
Количество линейных программ <tex>= K_{n, r} = n^2 \cdot (n+1)^2 \cdot (n+2)^2 \cdot \ldots \cdot (n+r-1)^2 \leq (n+r)^{2r}</tex>
 
Количество линейных программ <tex>= K_{n, r} = n^2 \cdot (n+1)^2 \cdot (n+2)^2 \cdot \ldots \cdot (n+r-1)^2 \leq (n+r)^{2r}</tex>
Строка 43: Строка 47:
 
{{Лемма
 
{{Лемма
 
|id=Лемма1
 
|id=Лемма1
|statement=<tex>\exists</tex> булева функция <tex>f: size_B(f) \geq \frac{2^n}{2n}</tex>
+
|statement=Существует булева функция <tex>f: size_B(f) \geq \frac{2^n}{2n}</tex>
|proof=Предположим противное, пусть размер всех линейных программ <tex>r < \frac{2^n}{2n} </tex>
+
|proof=Посчитаем число линейных программ длиной <tex>r < \frac{2^n}{2n} </tex>
  
 
<tex>\log_2{K_{n, r}} \leq 2 r \log_2 {(n+r)}  < \frac{2 \cdot 2^n}{2n} \log_2{(n+ \frac{2^n}{2n})} \leq \frac{2^n}{n} \log_2 {2^n} = 2^n \Rightarrow</tex>
 
<tex>\log_2{K_{n, r}} \leq 2 r \log_2 {(n+r)}  < \frac{2 \cdot 2^n}{2n} \log_2{(n+ \frac{2^n}{2n})} \leq \frac{2^n}{n} \log_2 {2^n} = 2^n \Rightarrow</tex>
 +
<tex>K_{n, r} < 2^{2^n} \Rightarrow \exists \; f_n: r \geq \frac{2^n}{2n} </tex>
  
<tex>\Rightarrow K_{n, r} < 2^{2^n}</tex> {{---}} такого быть не может, следовательно, <tex>\exists \; f_n: r> \frac{2^n}{2n} </tex>
+
Теперь возьмем все булевы функции, размер которых не превышает <tex>\frac{2^n}{2cn}</tex> для какого-то <tex>c > 1</tex>.
  
Обобщим для произвольного <tex>c</tex>
+
Тогда
 
+
<tex>\log_2 K_{n,r}\leq 2r\log_2(n+r) \leq \frac{2\cdot 2^n}{2cn}\log_2(n+\frac{2^n}{2cn})\leq \frac{2^n}{cn}\log_2 2^n=\frac{2^n}{c} \Rightarrow</tex>
<tex>r<\frac{2^n}{2cn}</tex>
+
<tex>\Rightarrow K_{n,r} \leq 2^{\frac{2^n}{c}} \Rightarrow \exists \; f_n: r> \frac{2^n}{2cn} </tex>
 +
}}
 +
Таким образом, количество линейных программ длины <tex>\leq \frac{2^n}{2cn}</tex> не больше <tex>2^{\frac{2^n}{c}}</tex>
  
<tex>\log_2 K_{n,r}\leq 2r\log_2(n+r)<\frac{2\cdot 2^n}{2cn}\log_2(n+\frac{2^n}{2cn})\leq \frac{2^n}{cn}\log_2 2^n=\frac{2^n}{c} \Rightarrow</tex>
+
===Возвращение к теореме о нижней оценке===
 
+
<tex>|F_g| \leq 2^{\frac{2^n}{c}} \Rightarrow \frac{|F_g|}{2^{2^n}} \leq \frac{2^\frac{2^n}{c}}{2^{2^n}} = 2^{2^n (\overset{< 0}{\frac{1}{c}-1})}\rightarrow 0</tex>
<tex>\Rightarrow K_{n,r}<2^{\frac{2^n}{c}} !!! </tex>
+
= См. также =
}}
+
* [[Определение булевой функции]]
 +
* [[Реализация булевой функции схемой из функциональных элементов]]
 +
* [[Представление булевых функций линейными программами]]

Текущая версия на 00:57, 18 июня 2020

Теорема о нижней оценке на число элементов в схеме

Теорема:
Большинство булевых функций требуют для реализации порядка [math]\Omega(\frac{2^n}{n})[/math] функциональных элементов, где [math]n[/math] — количество аргументов функции.

Формальная запись теоремы: [math]f(n) = \frac{2^n}{n} \; \; \; g(n): \frac{g}{f} \longrightarrow 0[/math]

[math]F_g = \{\text{Булевы функции, } size \leq g(n)\}[/math]

Тогда [math]\frac{|F_g|}{2^{2^n}} \longrightarrow 0[/math]

Для доказательства этой теоремы нам понадобится доказать несколько вспомогательных утверждений.

Определение:
Линейная программа — список строк вида [math](a, (i_1, \ldots, i_k))[/math], где [math]a \in B[/math] (базис), [math]a: \mathbb B^k \rightarrow \mathbb B[/math], [math]i_j[/math] — индексы переменных.

Пример линейной программы

Линейная программа для функции [math]x_1 \oplus x_2[/math] над базисом [math]\{ \land, \lor, \lnot \}[/math]

[math]y_1 = \lnot x_1[/math]

[math]y_2 = \lnot x_2[/math]

[math]y_3 = x_1 \land y_2[/math]

[math]y_4 = x_2 \land y_1[/math]

[math]y_5 = y_3 \lor y_4[/math]

Длина линейной программы — количество строк.

Теорема:
Для булевой функции [math]f [/math] существует линейная программа длины [math]r[/math] тогда и только тогда, когда существует схема, использующая [math]r[/math] функциональных элементов.
Доказательство:
[math]\triangleright[/math]

Чтобы построить по схеме программу, можно занумеровать элементы схемы в порядке топологической сортировки, и для каждого элемента [math]m[/math] с функцией [math]a[/math] и входами [math]i_1, \ldots, i_k[/math] сопоставить строчку линейной программы с номером [math]m[/math] вида [math](a, (i_1, \ldots, i_k))[/math].

Построение функциональной схемы по линейной программе очевидно.
[math]\triangleleft[/math]

Оценка на количество линейных программ над [math]\{\downarrow\}[/math] длины [math]r[/math]

[math]n[/math] — количество аргументов булевой функции.

[math]\downarrow[/math] — стрелка Пирса, является сама по себе базисом булевых функций.

В первой строчке мы можем выбрать одну из [math]n[/math] переменных ([math]x_1, \ldots, x_n[/math]) и применить к ней [math]\downarrow[/math]. Получим еще одну переменную [math]y_1[/math]. Во второй строчке программы нам на выбор доступны уже [math]n+1[/math] переменных ([math]x_1, \ldots, x_n, y_1[/math]). В общем случае на [math]i[/math]-й строчке (нумерация с единицы) мы можем применить стрелку Пирса к одной из [math]n+i-1[/math] переменных. Из этого следует формула ниже.

Количество линейных программ [math]= K_{n, r} = n^2 \cdot (n+1)^2 \cdot (n+2)^2 \cdot \ldots \cdot (n+r-1)^2 \leq (n+r)^{2r}[/math]

[math]\log_2{K_{n, r}} \leq \log_2 {(n+r)^{2r}} = 2r \log_2 {(n+r)}[/math]

Лемма:
Существует булева функция [math]f: size_B(f) \geq \frac{2^n}{2n}[/math]
Доказательство:
[math]\triangleright[/math]

Посчитаем число линейных программ длиной [math]r \lt \frac{2^n}{2n} [/math]

[math]\log_2{K_{n, r}} \leq 2 r \log_2 {(n+r)} \lt \frac{2 \cdot 2^n}{2n} \log_2{(n+ \frac{2^n}{2n})} \leq \frac{2^n}{n} \log_2 {2^n} = 2^n \Rightarrow[/math] [math]K_{n, r} \lt 2^{2^n} \Rightarrow \exists \; f_n: r \geq \frac{2^n}{2n} [/math]

Теперь возьмем все булевы функции, размер которых не превышает [math]\frac{2^n}{2cn}[/math] для какого-то [math]c \gt 1[/math].

Тогда [math]\log_2 K_{n,r}\leq 2r\log_2(n+r) \leq \frac{2\cdot 2^n}{2cn}\log_2(n+\frac{2^n}{2cn})\leq \frac{2^n}{cn}\log_2 2^n=\frac{2^n}{c} \Rightarrow[/math]

[math]\Rightarrow K_{n,r} \leq 2^{\frac{2^n}{c}} \Rightarrow \exists \; f_n: r\gt \frac{2^n}{2cn} [/math]
[math]\triangleleft[/math]

Таким образом, количество линейных программ длины [math]\leq \frac{2^n}{2cn}[/math] не больше [math]2^{\frac{2^n}{c}}[/math]

Возвращение к теореме о нижней оценке

[math]|F_g| \leq 2^{\frac{2^n}{c}} \Rightarrow \frac{|F_g|}{2^{2^n}} \leq \frac{2^\frac{2^n}{c}}{2^{2^n}} = 2^{2^n (\overset{\lt 0}{\frac{1}{c}-1})}\rightarrow 0[/math]

См. также