Для контактных схем при фиксированном числе n переменных конечная система τ_n полна: любые две эквивалентные КС от x₁,…,x_n преобразуются друг в друга по τ_n. Следовательно, для каждого фиксированного n существует конечная полная система
Но для класса всех контактных схем, где n не ограничено, конечной полной системы не существует. Полной является бесконечная \(\tau_{\infty}\). Невозможность конечной системы доказывается цикломатическим инвариантом Θ: правила ограниченного порядка меняют его лишь с определённой кратностью, тогда как следующее тождество \(t_6^{(n+1)}\) эту кратность
Что важно запомнить
- Теорема 8.1: эквивалентные КС от фиксированных n переменных связаны преобразованием по
- Поэтому τ_n — КПСТ при фиксированном n.
- \(\tau_{\infty}\) полна для всего класса КС, но бесконечна.
- \(\Theta(\Sigma,\alpha)=|E(\Sigma\mid\alpha)|-|V(\Sigma\mid\alpha)|+|c(\Sigma\mid\alpha)|\) — цикломатическое число проводящей сети.
- Теорема 8.2: в классе всех КС конечной полной системы тождеств
Полнота при фиксированном числе переменных
Обозначим τ_n систему \(t_1\)–\(t_5\) вместе с t₆^(1),…,t₆^(n). Теорема 8.1 утверждает: если две КС Σ′ и Σ″ от x₁,…,x_n эквивалентны, то существует цепочка эквивалентных преобразований Σ′⇒Σ″, использующая только тождества
Идея доказательства — привести обе схемы к каноническим КС, определяемым их одинаковым функционированием, а затем использовать обобщённые тождества. Отсюда τ_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\) сохраняют Θ, а преобразования по τ_k при k<n меняют суммарный Θ на число, делящееся на
Почему КПСТ для всех КС невозможна
Предположим, что существует конечная полная система τ. В её тождествах встречается не более некоторого числа n переменных. Тогда полнота должна позволить вывести \(t_6^{(n+1)}\), сворачивающее цикл длины n+1 к полюсу. Для двух частей этого тождества значения Θ отличаются на 1. Но любой вывод правилами порядка не выше n должен менять Θ на число, делящееся на 2. Получается противоречие. Значит, для всего класса U^K конечной полной системы
Граница результата принципиальна: при каждом фиксированном n конечная полнота есть, единой конечной системы для всех n нет.
Пример простыми словами
Если заранее известно, что используются только x₁,…,x_n, можно включить в τ_n все нужные циклические правила до порядка n. Но при попытке сделать один конечный список для схем произвольной размерности всегда появляется следующий цикл \(t_6^{(n+1)}\), который этот список уже не выводит.
Частые ошибки
- Говорить, что у КС вообще нет полной системы тождеств. Полная система \(\tau_{\infty}\) существует. Не существует именно конечной полной системы для всего класса.
- Игнорировать фиксированное n. При фиксированном числе переменных τ_n конечна и полна.
- Путать Θ с простым числом циклов исходной схемы. Θ суммирует цикломатические числа проводящих подграфов по входным наборам.
