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