Что такое базис замкнутого класса
Пусть A⊆P_k замкнут относительно суперпозиции. Множество B⊆A называется базисом A, если [B]=A и для каждого f∈B класс, порождённый B без функции f, уже не равен A. Второе условие означает неизбыточность. Оно существенно: без него сам класс A всегда был бы тривиальной порождающей системой.1
Теорема Янова
Для любого k≥3 существует замкнутый класс, не имеющий базиса. В доказательстве берут f₀=0 и функции f_i(x₁,…,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 возникают и классы вообще без базиса, и классы с бесконечным счётным базисом. Теоремы Янова и Мучника фиксируют эту качественную границу.