Поста класс

- замкнутый относительно операции суперпозиции класс функций алгебры логики (ф. а. л.). Э. Пост (Е, Post) установил, что таких классов в точности счетное множество, и дал их явное описание. Им же показано, что все они являются конечно порожденными, построена решетка по включению, образованная этими классами. Множество указанных классов исчерпывается списком С i, Ai, Dj, Lk, Ol, Sr, Pr, [img: http://localhost:8080/file/041735-74.jpg], где 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 [img: http://localhost:8080/file/041735-75.jpg] С 3. Класс А 1 состоит из всех монотонных ф. а. л.; [img: http://localhost:8080/file/041735-76.jpg]. Класс D3 состоит из всех ф. а. л. [img: http://localhost:8080/file/041735-77.jpg]; [img: http://localhost:8080/file/041735-78.jpg]. Класс L1 состоит из всех ф. а. л. f(x1, х 2,..., х n) = х 1+х 2+...+xn+d(mod2), [img: http://localhost:8080/file/041735-79.jpg] Класс 09 состоит из всех ф. а. л., существенно зависящих не более чем от одного переменного; [img: http://localhost:8080/file/041735-80.jpg] [img: http://localhost:8080/file/041735-81.jpg] состоит из всех константных функций; [img: http://localhost:8080/file/041735-82.jpg] [img: http://localhost:8080/file/041735-83.jpg]. Класс S6 состоит из всех ф. а. л. f(xl,..., xn)= [img: http://localhost:8080/file/041735-84.jpg] и всех константных ф. а. л.; S3= [img: http://localhost:8080/file/041735-85.jpg]. Класс Р 6 состоит из всех ф. а. л. f(x1, х 2,...,xn)= = х гaх 2a...aх п и всех константных ф. а. л.; P5= [img: http://localhost:8080/file/041735-86.jpg]. Ф. а. л. удовлетворяет условию am, если любые m наборов, на к-рых она равна 0, имеют общую координату, равную нулю. Аналогично с заменой 0 на 1 вводится условие А m. Класс [img: http://localhost:8080/file/041735-87.jpg] состоит из всех ф. а. л. со свойством а m; [img: http://localhost:8080/file/041735-88.jpg] состоит из всех ф. а. л. со свойством [img: http://localhost:8080/file/041735-89.jpg] [img: http://localhost:8080/file/041735-90.jpg]. Ф. а. л. удовлетворяет условию [img: http://localhost:8080/file/041735-91.jpg], если все наборы, на к-рых она равна нулю, имеют общую координату, равную нулю. Аналогично с заменой 0 на 1 вводится свойство [img: http://localhost:8080/file/041735-92.jpg]. Класс [img: http://localhost:8080/file/041735-93.jpg] состоит из всех ф. а. л. со свойством [img: http://localhost:8080/file/041735-94.jpg]; [img: http://localhost:8080/file/041735-95.jpg] состоит из всех ф. а. л. со свойством [img: http://localhost:8080/file/041735-96.jpg] [img: http://localhost:8080/file/041735-97.jpg] Решетка по включению, образованная этими классами, изображена на рисунке. На нем классы изображены точками. [img: http://localhost:8080/file/041735-98.jpg] Две точки соединены дугой, если нижележащая точка обозначает класс, непосредственно содержащийся в верхнем классе (т. е. между ними нет промежуточных классов).