Оценки числа формул и схем из функциональных элементов

Оценки числа формул и СФЭ нужны для мощностных аргументов. Они показывают, сколько различных структур ограниченной сложности вообще может существовать. В базисе Б₀={∧,∨,¬} число попарно не изоморфных формул сложности не более L от n переменных оценивается сверху величиной \((10n)^{L+1}\), а число попарно не квазиизоморфных — \((8n)^{L+1}\). Для глубины не более D получается оценка \((8n)^{2^D}\).1

Для СФЭ с n входами и сложностью не более L число классов с точностью до квазиизоморфизма не превосходит \((8(L+n))^{L+1}\). Это именно верхние оценки числа структурных классов, а не точные значения и не число различных реализуемых функций.1

Что важно запомнить
  • Формулы сложности ≤L: число классов изоморфизма ≤\((10n)^{L+1}\).1
  • Формулы сложности ≤L с точностью до квазиизоморфизма: ≤\((8n)^{L+1}\).
  • Формулы глубины ≤D с точностью до квазиизоморфизма: ≤\((8n)^{2^D}\).1
  • СФЭ сложности ≤L с n входами: число классов квазиизоморфизма ≤\((8(L+n))^{L+1}\).1
  • Эти оценки считаются по структурам и используются как верхние границы, а не как точные количества функций.

Что именно подсчитывается

При перечислительных оценках важно заранее зафиксировать отношение, по которому схемы считаются одинаковыми. Для формул курс рассматривает классы с точностью до изоморфизма и квазиизоморфизма, а для СФЭ особенно удобен квазиизоморфизм. Поэтому речь идёт не о числе текстовых записей и не о числе различных булевых функций, а о числе структурных типов при ограничениях на сложность, глубину и набор входных переменных.1

Формулы

Обозначим через UΦ(L,n) формулы над Б₀ от переменных \(x_{1},\ldots,x_n\) со сложностью не более L. Лемма 4.2 даёт следующие верхние оценки.

Число попарно не изоморфных формул этого класса не превосходит \((10n)^{L+1}\).1

Если считать формулы с точностью до квазиизоморфизма, то упорядоченность аргументов симметрических операций можно частично снять, и оценка улучшается до \((8n)^{L+1}\). Для множества формул глубины не более D из структурного неравенства \(L\le 2^D-1\) следует оценка \((8n)^{2^D}\).1

Отдельное следствие для формул с поднятыми отрицаниями: число попарно не квазиизоморфных формул ранга не более R не превосходит \((12n)^R\).1

Схемы из функциональных элементов

У СФЭ возможны внутренние разветвления и совместное использование промежуточных результатов, поэтому одного дерева уже недостаточно. В доказательстве леммы 4.3 сначала выбирают остовную древовидную структуру с помеченными функциональными вершинами, а затем для её листьев выбирают присоединение либо к одному из n входов, либо к допустимой внутренней вершине. В результате для СФЭ сложности не более L получается

Число таких СФЭ с точностью до квазиизоморфизма не превосходит \((8(L+n))^{L+1}\).1

Главная роль таких оценок — показать, что число структур ограниченной сложности контролируемо. Позже это позволяет сравнивать мощность множества доступных схем с количеством функций, которые требуется реализовать.

Пример простыми словами

При \(n=2\) и \(L=1\) оценка для формул с точностью до квазиизоморфизма даёт \((8n)^{L+1}=16^2=256\). Это только верхняя граница: она не означает, что существует ровно 256 различных формул или функций. Для СФЭ в оценке появляется \(L+n\), потому что при кодировании лист может присоединяться не только к одному из исходных входов, но и к допустимой внутренней вершине.

Частые ошибки
  • Принимать приведённые выражения за точное число формул или схем. Это верхние оценки.
  • Путать число структурных классов с числом реализуемых ФАЛ. Разные схемы могут быть эквивалентны.
  • Не указывать, считается ли изоморфизм или квазиизоморфизм. От этого меняется сама оцениваемая совокупность.

Другие вопросы

Источники

  1. 1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 2, §4, леммы 4.2–4.3 и следствия, МГУ, факультет ВМК