Что такое базис замкнутого класса
Пусть \(A\subseteq P_k\) замкнут относительно суперпозиции. Множество B⊆A называется базисом A, если [B]=A и для каждого f∈B класс, порождённый B без функции f, уже не равен A. Второе условие означает неизбыточность. Оно существенно: без него сам класс A всегда был бы тривиальной порождающей системой.1
Теорема Янова
Для любого k≥3 существует замкнутый класс, не имеющий базиса. В доказательстве берут f₀=0 и функции \(f_i(x_{1},\ldots,x_i)\), равные 1 только на наборе (2,…,2), и рассматривают A=[{f₀,f₁,f₂,…}]. При вложении одной нетривиальной \(f_j\) в другую \(f_i\) результат обнуляется, поэтому структура суперпозиций очень ограничена.1
Если предположить существование базиса и взять его функцию \(f_n\) наименьшей арности, возникают два случая. При наличии в базисе \(f_m\) с m>n функция \(f_n\) получается из \(f_m\) отождествлением переменных, что нарушает неизбыточность. Если же \(f_n\) — единственный базисный элемент, функции больших арностей из него не получаются, что нарушает полноту базиса. Следовательно, базиса нет.1
Теорема Мучника
Для любого k≥3 существует замкнутый класс со счётным базисом. Рассматриваются функции \(f_i\), i≥2, которые равны 1 ровно на наборах, где одна координата равна 1, а все остальные — 2. Для A=[{f₂,f₃,…}] система B={f₂,f₃,…} порождает A. Доказательство показывает, что ни одну \(f_n\) нельзя выразить через остальные функции B без \(f_n\). Значит, B неизбыточен и является счётным базисом.1
Значение результатов
В булевой логике структура замкнутых классов существенно более регулярна. Уже при k≥3 возникают и классы вообще без базиса, и классы с бесконечным счётным базисом. Теоремы Янова и Мучника фиксируют эту качественную границу.