Критерий Поста

Пять классов Поста T₀, T₁, S. M, L. Их замкнутость. Критерий Поста: множество полно, если оно не содержится ни в одном из классов Поста. Примеры.

Рассмотрим некоторые классы булевых функций:

• класс функций T₀, сохраняющих константу 0, т.е. функций, удовлетворящих условию f(0,...,0) = 0;

• аналогичный класс функций T₁, сохраняющих константу 1, т.е. удовлетворящих условию f(1,...,1) = 1;

• класс S самодвойственных функций, т.е. функций, удовлетворяющих условию ∀α f(α) = = f(α) (здесь α — n-мерный булев вектор, отрицание которого выполняется покомпонентно);

• класс M функций, монотонных относительно естественного порядка полукольца B_n, т.е. функций, удовлетворяющих условию α ≤ β ⇒ f(α) ≤ f(β);

• класс L линейных функций — функций, представимых полиномом Жегалкина первой степени (попросту говоря суммой по модулю 2 литералов, в число которых может входить ко станта 0).

Выделенные классы называют классами Поста. Они интересны тем, что каждый определяется свойством, сохраняющимся при конструировании формул. Точнее говоря, если функции f, g₁, ..., g_k принадлежат одному из указанных классов, то и их композиция f(g₁,g₂,...,g_k) принадлежит этому же классу. Это означает, что каждый из названных классов есть замкну- тое множество. Отметим также, что классы Поста замкнуты относительно операций введения или удаления фиктивных аргументов.

Рассмотрение классов Поста приводит к следующему необходимому условию полноты рассматриваемого базиса: базис, целиком попадающий в один из классов Поста, не может быть полным. Действительно, если базис включен в один из классов Поста, то замыкание базиса также оказывается в этом классе. Но ни один из классов Поста не совпадает со всем множе- ством булевых функций. Следовательно, замыкание базиса не будет совпадать с множеством всех булевых функций. Менее очевидным является то, что это условие и достаточно.

Теорема 1.5 (критерий Поста). Множество F полно тогда и только тогда, когда оно не является подмножеством никакого из классов Поста.

◀Доказательство достаточности критерия состоит в построении из заданных функций формул, представляющих функции стандартного базиса. Отметим, что в стандартном базисе одна из бинарных операций выражается через отрицание и другую бинарную операцию, например

x + y = xy .

Поэтому достаточно построить формулы, определяющие отрицание и умножение.

Пусть F не является подмножеством ни одного из классов Поста. Для каждой функции f ∈ F рассмотрим формулу g(x) = f(x, x, . . . , x). Поскольку F не содержится в T₀ и в T₁, в F, во-первых, есть непостоянные функции, а во-вторых есть хотя бы одна функция f₁, для которой g₁(0) = 1, и есть хотя бы одна функция f₂, для которой g₂(1) = 0. Это возможно, если одна из функций g₁(x) и g₂(x) есть отрицание, либо обе функции постоянны и представляют константы 0 и 1. Рассмотрим оба случая.

Пусть функции g₁(x) и g₂(x) являются константы 0 и 1. Тогда для любой функции f ∈ F формула f(α₁,α₂,...,α_i−1,x,α_i+1,...,α_n), в которой αj — константы, есть формула над F. Выберем функцию f, не являющуюся монотонной. Тогда существуют два булевых вектора p и q, удовлетворяющие условиям p < q и f(p) = 1, f(q) = 0. Векторы p и q можно соединить цепочкой p = p₀, p₁, . . . , p_k = q непосредственно предшествующих друг другу векторов (соседних). В этой цепочке найдется два соседних вектора p_j−1 и p_j, которые отличаются только одной компонентой с некоторым номером i и на которых f(p_j−1) = 1, f(p_j) = 0. Пусть α_j, j≠ i, одинаковые компоненты этих векторов. Тогда формула f(α₁, α₂, . . . , α_i−1, x, α_i+1, . . . , α_т) представляет собой операцию отрицания.

Предположим, например, что функция g₁(x) является отрицанием. Тогда мы можем составлять формулы вида f(x ⊕ σ¹,...,x ⊕ σ1), где x ⊕ σ есть переменная x при σ = 0 и ее отрицание при σ = 1. Выберем функцию f ∈ F, не являющуюся самодвойственной. Тогда можно указать такой булев вектор p ∈ B^т, что f(p) ̸= f(p), откуда f(p) = f(p). Пусть σ₁, ..., σ_n — компоненты вектора p. Рассмотрим функцию g(x) = f(x ⊕ σ¹, . . . , x ⊕ σ₁), определяемую выбранной несамодвойственной функцией f и вектором p. Так как 0 ⊕ σ_i = σ_i, 1 ⊕ σ_i = σ_i, то g(0) = f(p) = f(p) = g(x). Следовательно, функция g(x) является константой. Пусть, например, g(x) = 1. Тогда g(x) = 0 — другая константа.

Итак, мы показали, что множество F, не являющееся подмножеством классов T₀, T₁, S, M, позволяет получить в виде формул отрицание и обе константы. Для построения формулы для произведения выберем функцию f ∈ F, не являющуюся линейной. Составляя формулы вида f(X₁,X₂,...,X_n), где X_i — это либо переменная x, либо переменная y, мы получим функции двух аргументов. Покажем, что среди таких функций есть нелинейные. В полиноме Жегалкина, представляющем функцию f, выберем нелинейное (степени два или выше) слагаемое наименьшей степени. Пусть это слагаемое имеет вид x_i1 x_i2 . . . x_ik . В формуле f(X₁, X₂, . . . , X_n) положим X_i1 = x, X_ij = y, j = 2, k, а для остальных переменных, не вошедших в выбран- ное слагаемое выберем значение 0. Тогда выбранное слагаемое преобразуется в xy, остальные нелинейные слагаемые обнулятся, и мы получим функцию вида g(x, y) = xy ⊕ αx ⊕ βy ⊕ γ.

Так как

g(x, y) = xy ⊕ αx ⊕ βy ⊕ γ = (x ⊕ β)(y ⊕ α) ⊕ αβ ⊕ γ = (x ⊕ β)(y ⊕ α) ⊕ γ′,

заключаем, что g(x⊕β,y⊕α)⊕γ′ = xy. Но x⊕σ — это переменная x при σ = 0 и ее отрицание x при σ = 1. Поэтому, если g(x,y) принадлежит замыканию F, то и функция g(x ⊕ β, y ⊕ α) ⊕ γ′ = xy, т.е. конъюнкция, принадлежит замыканию F .

Итак, мы показали, что если множество F не является подмножеством никакого класса Поста, то формулами над F можно представить отрицание и конъюнкцию, а значит, и дизъюнкцию. В этом случае, согласно теореме 1.3, множество F полное.