Для контактных схем при фиксированном числе n переменных конечная система \(\tau_n\) полна: любые две эквивалентные КС от \(x_{1},\ldots,x_n\) преобразуются друг в друга по \(\tau_n\). Следовательно, для каждого фиксированного n существует конечная полная система
Но для класса всех контактных схем, где n не ограничено, конечной полной системы не существует. Полной является бесконечная \(\tau_\infty\). Невозможность конечной системы доказывается цикломатическим инвариантом Θ: правила ограниченного порядка меняют его лишь с определённой кратностью, тогда как следующее тождество \(t_6^{(n+1)}\) эту кратность
Что важно запомнить
- Теорема 8.1: эквивалентные КС от фиксированных n переменных связаны преобразованием по
- Поэтому \(\tau_n\) — КПСТ при фиксированном n.
- \(\tau_\infty\) полна для всего класса КС, но бесконечна.
- \(\Theta(\Sigma,\alpha)=|E(\Sigma\mid\alpha)|-|V(\Sigma\mid\alpha)|+|c(\Sigma\mid\alpha)|\) — цикломатическое число проводящей сети.
- Теорема 8.2: в классе всех КС конечной полной системы тождеств
Полнота при фиксированном числе переменных
Обозначим \(\tau_n\) систему \(t_1\)–\(t_5\) вместе с \(t_{6}^{1},\ldots,t_{6}^{n}\). Теорема 8.1 утверждает: если две КС Σ′ и Σ″ от \(x_{1},\ldots,x_n\) эквивалентны, то существует цепочка эквивалентных преобразований Σ′⇒Σ″, использующая только тождества
Идея доказательства — привести обе схемы к каноническим КС, определяемым их одинаковым функционированием, а затем использовать обобщённые тождества. Отсюда \(\tau_n\) является конечной полной системой для фиксированного набора переменных.
Цикломатический инвариант
Для схемы Σ и набора α вводится
\(\Theta(\Sigma,\alpha)=|E(\Sigma\mid\alpha)|-|V(\Sigma\mid\alpha)|+|c(\Sigma\mid\alpha)|\),
то есть цикломатическое число проводящего графа. Затем суммируют \(\Theta(\Sigma)=\sum_{\alpha}\Theta(\Sigma,\alpha)\). Лемма 8.2 показывает: преобразования \(t_1\)–\(t_5\) сохраняют Θ, а преобразования по \(\tau_k\) при k<n меняют суммарный Θ на число, делящееся на
Почему КПСТ для всех КС невозможна
Предположим, что существует конечная полная система τ. В её тождествах встречается не более некоторого числа n переменных. Тогда полнота должна позволить вывести \(t_6^{(n+1)}\), сворачивающее цикл длины n+1 к полюсу. Для двух частей этого тождества значения Θ отличаются на 1. Но любой вывод правилами порядка не выше n должен менять Θ на число, делящееся на 2. Получается противоречие. Значит, для всего класса \(U^K\) конечной полной системы
Граница результата принципиальна: при каждом фиксированном n конечная полнота есть, единой конечной системы для всех n нет.
Пример простыми словами
Если заранее известно, что используются только \(x_{1},\ldots,x_n\), можно включить в \(\tau_n\) все нужные циклические правила до порядка n. Но при попытке сделать один конечный список для схем произвольной размерности всегда появляется следующий цикл \(t_6^{(n+1)}\), который этот список уже не выводит.
Частые ошибки
- Говорить, что у КС вообще нет полной системы тождеств. Полная система \(\tau_\infty\) существует. Не существует именно конечной полной системы для всего класса.
- Игнорировать фиксированное n. При фиксированном числе переменных \(\tau_n\) конечна и полна.
- Путать Θ с простым числом циклов исходной схемы. Θ суммирует цикломатические числа проводящих подграфов по входным наборам.
