<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="ru">
		<id>https://nerc.itmo.ru/wiki/index.php?action=history&amp;feed=atom&amp;title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0%3A%D0%9A%D0%B0%D0%BF%D0%B5%D0%BB%D1%8E%D1%88%D0%BE%D0%BA_%D0%93%D0%B5%D0%BE%D1%80%D0%B3%D0%B8%D0%B9_%D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87</id>
		<title>Обсуждение участника:Капелюшок Георгий Александрович - История изменений</title>
		<link rel="self" type="application/atom+xml" href="https://nerc.itmo.ru/wiki/index.php?action=history&amp;feed=atom&amp;title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0%3A%D0%9A%D0%B0%D0%BF%D0%B5%D0%BB%D1%8E%D1%88%D0%BE%D0%BA_%D0%93%D0%B5%D0%BE%D1%80%D0%B3%D0%B8%D0%B9_%D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87"/>
		<link rel="alternate" type="text/html" href="https://nerc.itmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:%D0%9A%D0%B0%D0%BF%D0%B5%D0%BB%D1%8E%D1%88%D0%BE%D0%BA_%D0%93%D0%B5%D0%BE%D1%80%D0%B3%D0%B8%D0%B9_%D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87&amp;action=history"/>
		<updated>2026-11-16T15:04:51Z</updated>
		<subtitle>История изменений этой страницы в вики</subtitle>
		<generator>MediaWiki 1.30.0</generator>

	<entry>
		<id>https://nerc.itmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:%D0%9A%D0%B0%D0%BF%D0%B5%D0%BB%D1%8E%D1%88%D0%BE%D0%BA_%D0%93%D0%B5%D0%BE%D1%80%D0%B3%D0%B8%D0%B9_%D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87&amp;diff=81123&amp;oldid=prev</id>
		<title>Капелюшок Георгий Александрович: Новая страница: «== Теорема о нижней оценке на число элементов в схеме из функциональных элементов ==  {{Тео…»</title>
		<link rel="alternate" type="text/html" href="https://nerc.itmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:%D0%9A%D0%B0%D0%BF%D0%B5%D0%BB%D1%8E%D1%88%D0%BE%D0%BA_%D0%93%D0%B5%D0%BE%D1%80%D0%B3%D0%B8%D0%B9_%D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87&amp;diff=81123&amp;oldid=prev"/>
				<updated>2021-06-27T17:30:29Z</updated>
		
		<summary type="html">&lt;p&gt;Новая страница: «== Теорема о нижней оценке на число элементов в схеме из функциональных элементов ==  {{Тео…»&lt;/p&gt;
&lt;p&gt;&lt;b&gt;Новая страница&lt;/b&gt;&lt;/p&gt;&lt;div&gt;== Теорема о нижней оценке на число элементов в схеме из функциональных элементов ==&lt;br /&gt;
&lt;br /&gt;
{{Теорема&lt;br /&gt;
|statement=Большинство [[Определение_булевой_функции | булевых функций]] требуют для реализации порядка &amp;lt;tex&amp;gt;\Omega(\frac{2^n}{n})&amp;lt;/tex&amp;gt; [[Реализация_булевой_функции_схемой_из_функциональных_элементов | функциональных элементов]], где &amp;lt;tex&amp;gt;n&amp;lt;/tex&amp;gt; — количество аргументов функции. &lt;br /&gt;
Формальная запись теоремы:&lt;br /&gt;
&amp;lt;tex&amp;gt;f(n) = \frac{2^n}{n} \; \; \; g(n): \frac{g}{f} \longrightarrow 0&amp;lt;/tex&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;tex&amp;gt;F_g = \{\text{Булевы функции, } size \leq g(n)\}&amp;lt;/tex&amp;gt;&lt;br /&gt;
Тогда &amp;lt;tex&amp;gt;\frac{|F_g|}{2^{2^n}} \longrightarrow 0&amp;lt;/tex&amp;gt;&lt;br /&gt;
}}&lt;br /&gt;
Для доказательства этой теоремы нам понадобится доказать несколько вспомогательных утверждений.&lt;br /&gt;
{{Определение&lt;br /&gt;
|definition=&lt;br /&gt;
'''[[Представление_булевых_функций_линейными_программами#Линейные_программы|Линейная программа]]''' {{---}} список строк вида &amp;lt;tex&amp;gt;(a, (i_1, \ldots, i_k))&amp;lt;/tex&amp;gt;, где &amp;lt;tex&amp;gt;a \in B&amp;lt;/tex&amp;gt; (базис), &amp;lt;tex&amp;gt;a: \mathbb B^k \rightarrow \mathbb B&amp;lt;/tex&amp;gt;, &amp;lt;tex&amp;gt;i_j&amp;lt;/tex&amp;gt; {{---}} индексы переменных.&lt;br /&gt;
}}&lt;br /&gt;
'''Пример линейной программы'''&lt;br /&gt;
&lt;br /&gt;
Линейная программа для функции &amp;lt;tex&amp;gt;x_1 \oplus x_2&amp;lt;/tex&amp;gt; над базисом &amp;lt;tex&amp;gt;\{ \land, \lor, \lnot \}&amp;lt;/tex&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;tex&amp;gt;y_1 = \lnot x_1&amp;lt;/tex&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;tex&amp;gt;y_2 = \lnot x_2&amp;lt;/tex&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;tex&amp;gt;y_3 = x_1 \land y_2&amp;lt;/tex&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;tex&amp;gt;y_4 = x_2 \land y_1&amp;lt;/tex&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;tex&amp;gt;y_5 = y_3 \lor y_4&amp;lt;/tex&amp;gt;&lt;br /&gt;
&lt;br /&gt;
'''Длина''' линейной программы {{---}} количество строк.&lt;br /&gt;
{{Теорема&lt;br /&gt;
|statement= Для булевой функции &amp;lt;tex&amp;gt;f &amp;lt;/tex&amp;gt; существует линейная программа длины &amp;lt;tex&amp;gt;r&amp;lt;/tex&amp;gt; тогда и только тогда, когда существует схема, использующая &amp;lt;tex&amp;gt;r&amp;lt;/tex&amp;gt; функциональных элементов.&lt;br /&gt;
|proof=Чтобы построить по схеме программу, можно занумеровать элементы схемы в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки#Топологическая_сортировка|топологической сортировки]], и для каждого элемента &amp;lt;tex&amp;gt;m&amp;lt;/tex&amp;gt; с функцией &amp;lt;tex&amp;gt;a&amp;lt;/tex&amp;gt; и входами &amp;lt;tex&amp;gt;i_1, \ldots, i_k&amp;lt;/tex&amp;gt; сопоставить строчку линейной программы с номером &amp;lt;tex&amp;gt;m&amp;lt;/tex&amp;gt; вида &amp;lt;tex&amp;gt;(a, (i_1, \ldots, i_k))&amp;lt;/tex&amp;gt;. &lt;br /&gt;
&lt;br /&gt;
Построение функциональной схемы по линейной программе очевидно.&lt;br /&gt;
}}&lt;br /&gt;
===Оценка на количество линейных программ над &amp;lt;tex&amp;gt;\{\downarrow\}&amp;lt;/tex&amp;gt; длины &amp;lt;tex&amp;gt;r&amp;lt;/tex&amp;gt;===&lt;br /&gt;
&amp;lt;tex&amp;gt;n&amp;lt;/tex&amp;gt; {{---}} количество аргументов булевой функции.&lt;br /&gt;
&lt;br /&gt;
&amp;lt;tex&amp;gt;\downarrow&amp;lt;/tex&amp;gt; {{---}} стрелка Пирса, является сама по себе базисом булевых функций.&lt;br /&gt;
&lt;br /&gt;
В первой строчке мы можем выбрать одну из &amp;lt;tex&amp;gt;n&amp;lt;/tex&amp;gt; переменных (&amp;lt;tex&amp;gt;x_1, \ldots, x_n&amp;lt;/tex&amp;gt;) и применить к ней &amp;lt;tex&amp;gt;\downarrow&amp;lt;/tex&amp;gt;. Получим еще одну переменную &amp;lt;tex&amp;gt;y_1&amp;lt;/tex&amp;gt;. Во второй строчке программы нам на выбор доступны уже &amp;lt;tex&amp;gt;n+1&amp;lt;/tex&amp;gt; переменных (&amp;lt;tex&amp;gt;x_1, \ldots, x_n, y_1&amp;lt;/tex&amp;gt;). В общем случае на &amp;lt;tex&amp;gt;i&amp;lt;/tex&amp;gt;-й строчке (нумерация с единицы) мы можем применить стрелку Пирса к одной из &amp;lt;tex&amp;gt;n+i-1&amp;lt;/tex&amp;gt; переменных. Из этого следует формула ниже.&lt;br /&gt;
&lt;br /&gt;
Количество линейных программ &amp;lt;tex&amp;gt;= K_{n, r} = n^2 \cdot (n+1)^2 \cdot (n+2)^2 \cdot \ldots \cdot (n+r-1)^2 \leq (n+r)^{2r}&amp;lt;/tex&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;tex&amp;gt;\log_2{K_{n, r}} \leq \log_2 {(n+r)^{2r}} = 2r \log_2 {(n+r)}&amp;lt;/tex&amp;gt;&lt;br /&gt;
{{Лемма&lt;br /&gt;
|id=Лемма1&lt;br /&gt;
|statement=Существует булева функция &amp;lt;tex&amp;gt;f: size_B(f) \geq \frac{2^n}{2n}&amp;lt;/tex&amp;gt;&lt;br /&gt;
|proof=Посчитаем число линейных программ длиной &amp;lt;tex&amp;gt;r &amp;lt; \frac{2^n}{2n} &amp;lt;/tex&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;tex&amp;gt;\log_2{K_{n, r}} \leq 2 r \log_2 {(n+r)}  &amp;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&amp;lt;/tex&amp;gt;&lt;br /&gt;
&amp;lt;tex&amp;gt;K_{n, r} &amp;lt; 2^{2^n} \Rightarrow \exists \; f_n: r \geq \frac{2^n}{2n} &amp;lt;/tex&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Теперь возьмем все булевы функции, размер которых не превышает &amp;lt;tex&amp;gt;\frac{2^n}{2cn}&amp;lt;/tex&amp;gt; для какого-то &amp;lt;tex&amp;gt;c &amp;gt; 1&amp;lt;/tex&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
Тогда&lt;br /&gt;
&amp;lt;tex&amp;gt;\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&amp;lt;/tex&amp;gt;&lt;br /&gt;
&amp;lt;tex&amp;gt;\Rightarrow K_{n,r} \leq 2^{\frac{2^n}{c}} \Rightarrow \exists \; f_n: r&amp;gt; \frac{2^n}{2cn} &amp;lt;/tex&amp;gt;&lt;br /&gt;
}}&lt;br /&gt;
Таким образом, количество линейных программ длины &amp;lt;tex&amp;gt;\leq \frac{2^n}{2cn}&amp;lt;/tex&amp;gt; не больше &amp;lt;tex&amp;gt;2^{\frac{2^n}{c}}&amp;lt;/tex&amp;gt;&lt;br /&gt;
&lt;br /&gt;
===Возвращение к теореме о нижней оценке===&lt;br /&gt;
&amp;lt;tex&amp;gt;|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{&amp;lt; 0}{\frac{1}{c}-1})}\rightarrow 0&amp;lt;/tex&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&lt;br /&gt;
== Теорема о верхней оценке на число элементов в схеме из функциональных элементов ==&lt;br /&gt;
{{Теорема&lt;br /&gt;
|statement =Для любой функции &amp;lt;tex&amp;gt; f(x_{1}, \ldots, x_{n}) &amp;lt;/tex&amp;gt; имеет место соотношение &amp;lt;tex&amp;gt; size_{B}(f)\lesssim 12\dfrac {2^{n}}{n} &amp;lt;/tex&amp;gt;.&lt;br /&gt;
|proof  = См. [[Простейшие_методы_синтеза_схем_из_функциональных_элементов | Простейшие методы синтеза схем из функциональных элементов]]&lt;br /&gt;
}}&lt;/div&gt;</summary>
		<author><name>Капелюшок Георгий Александрович</name></author>	</entry>

	</feed>