210
правок
Изменения
м
::Будем считать, что схема Введем функцию <tex>S</tex> вычисляет систему булевых функцийx^{\sigma} = \begin{cases} x, если на каждый вход схемы подаются всевозможные наборы аргументов функции\sigma =1;\\ \overline{x}, а в выходах вычисляется функция от поданного на вход набора аргументов. Также будем считать, что <tex> size_\sigma =0\end{Bcases}(S)</tex> {{---}} это сложность схемы, вычисляющей систему булевых функций.
Введем функцию
<tex> x^{\sigma} = \begin{cases}
x, \sigma =1;\\
\overline{x}, \sigma =0
\end{cases}</tex>
Тогда
Нет описания правки
}}
'''Примечание'''
{{Лемма
|id = Lemma2
|about = 2
|statement = Пусть <tex> K_{n}(x_{1}^{\sigma_{1}},\dotsc,x_{n}^{\sigma_{n}}) </tex> {{---}} система всех <tex> 2^{n} </tex> конъюнкций <tex> x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{n}^{\sigma_{n}}</tex>, тогда для <tex> K_{n} </tex> имеет место соотношение <tex> size_{B}(K_{n}) \sim 2^n </tex>
|proof = [[Файл:Synschemes Lemma2.png|250px|thumb|right|Рис. 3]]
Разделим цепочки конъюнкций на две части. Каждая конъюнкция <tex> x_{1}\wedge\overline{x}_{2}\wedge{x}_{3}\wedge ... \wedge{x}_{i} </tex> может быть представлена в виде конъюнкции двух конъюнкций длины <tex> k </tex> и <tex> n-k </tex>:
|proof = [[Файл:Synschemes-Theorem2.png|300px|thumb|right|Рис. 4]]
Пусть <tex> f(x_{1},...,x_{n}) </tex> {{---}} произвольная булева функция. Рассмотрим разложение <tex> f </tex> по переменным <tex> x_{1},...,x_{m} </tex>, где <tex> 1 \le m \le n </tex>:
<tex>f(x_{1},...,x_{n})=\displaystyle\bigvee_{(\sigma_{1},\dotsc,\sigma_{m})}x_{1}^{\sigma_{1}}\wedge\dotsc\wedge x_{m}^{\sigma_{m}}\wedge f(\sigma_{1},\dotsc,\sigma_{m},x_{m+1},\dotsc,x_{n}) </tex>.
