Обсуждение участника:Sancho20021 — различия между версиями
(→Теорема о нижней оценке на число элементов в схеме) (Метки: правка с мобильного устройства, правка из мобильной версии) |
(→Теорема о нижней оценке на число элементов в схеме) |
||
Строка 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> {{---}} индексы переменных. |
}} | }} | ||
'''Пример линейной программы''' | '''Пример линейной программы''' |
Версия 00:55, 18 июня 2020
Теорема о нижней оценке на число элементов в схеме
Теорема: |
Большинство булевых функций требуют для реализации порядка функциональных элементов, где — количество аргументов функции.
Формальная запись теоремы: Тогда |
Для доказательства этой теоремы нам понадобится доказать несколько вспомогательных утверждений.
Определение: |
Линейная программа — список строк вида , где (базис), , — индексы переменных. |
Пример линейной программы
Линейная программа для функции
над базисом
Длина линейной программы — количество строк.
Теорема: |
Для булевой функции существует линейная программа длины тогда и только тогда, когда существует схема, использующая функциональных элементов. |
Доказательство: |
Чтобы построить по схеме программу, можно занумеровать элементы схемы в порядке топологической сортировки, и для каждого элемента с функцией и входами сопоставить строчку линейной программы с номером вида . Построение функциональной схемы по линейной программе очевидно. |
Оценка на количество линейных программ над длины
— количество аргументов булевой функции.
— стрелка Пирса, является сама по себе базисом булевых функций.
В первой строчке мы можем выбрать одну из
переменных ( ) и применить к ней . Получим еще одну переменную . Во второй строчке программы нам на выбор доступны уже переменных ( ). В общем случае на -й строчке (нумерация с единицы) мы можем применить стрелку Пирса к одной из переменных. Из этого следует формула ниже.Количество линейных программ
Лемма: |
Существует булева функция |
Доказательство: |
Посчитаем число линейных программ длиной
Теперь возьмем все булевы функции, размер которых не превышает для какого-то .Тогда |
Таким образом, количество линейных программ длины
не большеВозвращение к теореме о нижней оценке