210
правок
Изменения
м
Нет описания правки
{{Определение
|definition= <tex> f(n) \lesssim g(n) </tex> означает, что <tex>\varlimsup\limits_{n \to \infty}\frac{f(n)}{g(n)} \le 1</tex>
}}
{{Определение|definition= Пусть есть булева функция от <tex> n </tex> аргументов <tex> f(: \lbrace0, 1\rbrace^n) \lesssim g(rightarrow \lbrace0, 1\rbrace </tex> и набор из <tex> n) </tex> означаетбулевых функций <tex> g_1 \dotsc g_n </tex>, таких что <tex>g_i :\varlimsuplbrace0, 1\limits_rbrace^{n m_i} \rightarrow \to lbrace0, 1\inftyrbrace </tex>. Тогда системой булевых функций называется функция <tex> S </tex> от аргументов, которая определяется как <tex> S ( x_{11},\fracdotsc, x_{f1(nm_1)}, x_{21}, \dotsc, x_{g2(m_2)}, \dotsc, x_{n1}, \dotsc, x_{n(m_n)} )=f(g_1(x_{11},\le dotsc,x_{1(m_1)}),g_2(x_{21},\dotsc,x_{2(m_2}),\dotsc,g_n(x_{n1},\dotsc,x_{n(m_n)}))</tex>
}}
'''Примечание'''
