Обсуждение участника:Sancho20021 — различия между версиями
(Новая страница: «== Теорема о нижней оценке на число элементов в схеме == {{Теорема |statement=Большинство булев…») |
(→Теорема о нижней оценке на число элементов в схеме) |
||
| Строка 2: | Строка 2: | ||
{{Теорема | {{Теорема | ||
| − | |statement=Большинство булевых функций требуют для реализации порядка <tex>\Omega(\frac{2^n}{n})</tex> функциональных элементов, где <tex>n</tex> — количество аргументов функции. | + | |statement=Большинство [[Определение_булевой_функции | булевых функций]] требуют для реализации порядка <tex>\Omega(\frac{2^n}{n})</tex> [[Реализация_булевой_функции_схемой_из_функциональных_элементов | функциональных элементов]], где <tex>n</tex> — количество аргументов функции. |
| + | Формальная запись теоремы: | ||
| + | <tex>f(n) = \frac{2^n}{n} \; \; \; g(n): \frac{g}{f} \longrightarrow 0</tex> | ||
| + | |||
| + | <tex>F_g = \{\text{Булевы функции, } size \leq g(n)\}</tex> | ||
| + | Тогда <tex>\frac{|F_g|}{2^{2^n}} \longrightarrow 0</tex> | ||
|proof= | |proof= | ||
Алабудай балабулабудай. тудудум. | Алабудай балабулабудай. тудудум. | ||
}} | }} | ||
Версия 13:34, 4 июня 2020
Теорема о нижней оценке на число элементов в схеме
| Теорема: |
Большинство булевых функций требуют для реализации порядка функциональных элементов, где — количество аргументов функции.
Формальная запись теоремы: Тогда |
| Доказательство: |
| Алабудай балабулабудай. тудудум. |
