Зарегистрироваться

Поста класс

Категории Математическая кибернетика | Под редакцией сообщества: Математика

Поста класс – замкнутый относительно операции суперпозиции класс функций алгебры логики (ф. а. л.). Э. Пост (E. Post) установил, что таких классов в точности счетное множество, и дал их явное описание. Им же показано, что все они являются конечно порожденными, построена решетка по включению, образованная этими классами. Множество указанных классов исчерпывается списком Ci, Ai, Dj, Lk, Ol, Sr, Pr, Fμs, Fs, где i=1,2,3,4; j=1,2,3; k=1, …, 5; l=1, …, 9; r=1,3,5,6; s=1, …, 8; μ=2,3, … .

Класс C1 содержит все ф. а. л.; C2 состоит из всех ф. а. л. ƒ(x₁, …, xn) таких, что ƒ(0, …, 0)=0; C3 "--- из всех ф. а. л. ƒ(x₁, …, xn)  таких, что ƒ(1, …, 1)=1; C₄=C2 C₃. Класс A₁ состоит из всех монотонных ф. а. л.; A₂= C2 A₁; A₃=C₂ A₁; A₄= A₂ A₃. Класс D₃ состоит из всех ф. а. л. ;  D₁=C₄ D₃; D₂= A₁ D₃. Класс L₁ состоит из всех ф. а. л.  ƒ(x₁, x₂ …, xn)  = x₁ + x₂ + … + xn + d(mod2), ; L2=C2L₁ ; L₃=C₃L₁ ; L₄=L2L₃; L₅=D₃L₁; .

Класс O₉ состоит из всех ф. а. л., существенно зависящих не более чем от одного переменного; O₈=A₁O₉; O₄=D3O9; O5=C2O9; O6=C3O9; O1=O5O6; O7 состоит из всех константных функций: O2=O5O7; O3=O6O7.

Класс S6 состоит из всех ф. а. л. ƒ(x1, …, xn)=x1 ѵ x2 ѵ … ѵ xn и всех константных ф. а. л. S3=C2S6; S5=C3S6; S1=S3S5.

Класс P6 состоит из всех ф. а. л. ƒ(x1, …, xn)= x1&x2& … & xn и всех константных ф. а. л.; P5=C2P6; P3=C3P6; P1=P5P3.

Ф. а. л. удовлетворяет условию aμ, если любые μ наборов, на которых она равна 0, имеют общую координату, равную нулю. Аналогично с заменой 0 на 1 вводится условие Aμ.

Класс F4μ состоит из всех ф. а. л. со свойством aμ; F1μ=C4F4μ; F3μ=A1F4μ; F2μ=F1μF3μ; F8μ состоит из всех ф. а. л. со свойством Aμ; F5μ=C4F8μ; F7μ=A3F8μ; F6μ=F5μF7μ.

Ф. а. л. удовлетворяет условию a∞, если все наборы, на которых она равна нулю, имеют общую координату, равную нулю. Аналогично с заменой 0 на 1 вводится свойство A∞. Класс F4 состоит из всех ф. а. л. со свойством a; F1=C4F4; F3=A1F4; F2=F1 F3; F8 состоит из всех ф. а. л. со свойством A∞; F5∞=C4F8; F7=A3F8; F6=F5F7.

Решетка по включению, образованная этими классами, изображена на рисунке. На нем классы изображены точками. Две точки соединены дугой, если нижележащая точка обозначает класс, непосредственно содержащийся в верхнем классе (т. е. между ними нет промежуточных классов).

Рекомендуемая литература

Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б., Функции алгебры логики и классы Поста, М., 1966.

Эта статья еще не написана, но вы можете сделать это.