Математическая энциклопедия - поста класс

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

Класс C1 содержит все ф. а. л.; С 2 .состоит из всех ф. а. л. f(x1, . . ., х n).таких, что f(0,. . ., 0)=0; С 3из всех ф. а. л. таких, что f(1, . . ., 1)=1; С 4 = С 2С 3. Класс А 1 состоит из всех монотонных ф. а. л.;

. Класс D3 состоит из всех ф. а. л. ; . Класс L1 состоит из всех ф. а. л. f(x1, х 2, . . ., х n) = х 1+х 2+. . .+xn+d(mod2),

Класс 09 состоит из всех ф. а. л., существенно зависящих не более чем от одного переменного;

состоит из всех константных функций;

.

Класс S6 состоит из всех ф. а. л. f(xl, . . ., xn)= и всех константных ф. а. л.; S3=.

Класс Р 6 состоит из всех ф. а. л. f(x1, х 2, . . .,xn)= = х гaх 2a...aх п и всех константных ф. а. л.; P5⁼.

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

Класс состоит из всех ф. а. л. со свойством а ^m;

состоит из всех ф. а. л. со свойством .

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

Решетка по включению, образованная этими классами, изображена на рисунке. На нем классы изображены точками.

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

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

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985