Перечислительные оценки для контактных схем зависят от того, какое отношение отождествляет схемы. Для приведённых (1,1)-π-схем сложности не более L от n переменных число попарно неэквивалентных схем не превосходит \((12n)^L\)
Для всех приведённых (1,1)-контактных схем из неориентированных контактов при тех же ограничениях число попарно неизоморфных схем не превосходит \((8nL)^L\). Это верхние оценки числа классов, а не точное число схем или булевых
Что важно запомнить
- Для π-схем число классов функциональной эквивалентности
- Для общих КС число классов изоморфизма
- Первая оценка следует из моделирования π-схем формулами с поднятыми отрицаниями.
- Вторая получается кодированием КС через остовную древовидную структуру и присоединение оставшихся рёбер.
- Нельзя сравнивать оценки, не указав отношение: эквивалентность и изоморфизм различны.
Какие множества схем оцениваются
Пусть \(U^\pi(L,n)\) — приведённые (1,1)-π-схемы от \(x_{1},\ldots,x_n\) со сложностью не более L, а \(U^K(L,n)\) — аналогичный класс всех неориентированных контактных схем. В лекциях различаются число попарно неизоморфных и число попарно неэквивалентных схем. Второе не превосходит
Оценка для π-схем
По лемме 6.1 каждой π-схеме сложности ≤L соответствует формула с поднятыми отрицаниями ранга ≤L, реализующая ту же функцию. Отсюда лемма 6.2:
число попарно неэквивалентных схем в \(U^\pi(L,n)\) не превосходит \((12n)^L\).
Оценка для общих контактных схем
Для произвольной приведённой КС выбирают остовное дерево, строят связанное наддерево и кодируют его как ориентированное упорядоченное дерево с пометками \(x_i\) или \(\neg x_i\). Затем указывают присоединение рёбер, не вошедших в остов. Такой подсчёт даёт лемму 6.3:
число попарно неизоморфных схем в \(U^K(L,n)\) не превосходит \((8nL)^L\).
Главная роль этих оценок — контролировать количество структур ограниченной сложности. Это основа последующих мощностных аргументов.
Пример простыми словами
Оценки \((12n)^L\) и \((8nL)^L\) нельзя сравнивать как два подсчёта одного и того же множества. Первая относится к классам функциональной эквивалентности \(\pi\)-схем, а вторая — к классам изоморфизма общих контактных схем. Дополнительный множитель \(L\) во второй оценке отражает более богатую сетевую структуру общих КС.
Частые ошибки
- Принимать \((12n)^L\) и \((8nL)^L\) за точные количества. Это только верхние границы.
- Путать число схем и число реализуемых ФАЛ. Эквивалентные схемы могут быть неизоморфны.
- Забывать условие приведённости и ограничение \(L(\Sigma)\)≤L.
