|
"
0
C
F
G
H
K
L
N
P
S
T
W
Z
А
Б
В
Г
Д
Е
Ж
З
И
Й
К
Л
М
Н
О
П
Р
С
Т
У
Ф
Х
Ц
Ч
Ш
Э
Ю
Я
ПОСТА КЛАССЗначение ПОСТА КЛАСС в математической энциклопедии: - замкнутый относительно операции суперпозиции класс функций алгебры логики (ф. а. л.). Э. Пост (Е, Post) установил, что таких классов в точности счетное множество, и дал их явное описание. Им же показано, что все они являются конечно порожденными, построена решетка по включению, образованная этими классами. Множество указанных классов исчерпывается списком С i, Ai, Dj, Lk, Ol, Sr, Pr, Класс C1 содержит все ф. а. л.; С 2 .состоит из всех ф. а. л. f(x1, . . ., х n).таких, что f(0,. . ., 0)=0; С 3- из всех ф. а. л. таких, что f(1, . . ., 1)=1; С 4 = С 2 Класс 09 состоит из всех ф. а. л., существенно зависящих не более чем от одного переменного; состоит из всех константных функций; Класс S6 состоит из всех ф. а. л. f(xl, . . ., xn)= Класс Р 6 состоит из всех ф. а. л. f(x1, х 2, . . .,xn)= = х гaх 2a...aх п и всех константных ф. а. л.; P5= Ф. а. л. удовлетворяет условию am, если любые m наборов, на к-рых она равна 0, имеют общую координату, равную нулю. Аналогично с заменой 0 на 1 вводится условие А m. Класс Ф. а. л. удовлетворяет условию Решетка по включению, образованная этими классами, изображена на рисунке. На нем классы изображены точками. Две точки соединены дугой, если нижележащая точка обозначает класс, непосредственно содержащийся в верхнем классе (т. е. между ними нет промежуточных классов). Лит.:[1] Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б., Функции алгебры логики и классы Поста, М., 1966. В. В. Кудрявцев. |
|
|
|
, где 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,. . .
С 3. Класс А 1 состоит из всех монотонных ф. а. л.;
. Класс D3 состоит из всех ф. а. л. 
; 
. Класс L1 состоит из всех ф. а. л. f(x1, х 2, . . ., х n) = х 1+х 2+. . .+xn+d(mod2),
.
и всех константных ф. а. л.; S3=
.
.
состоит из всех ф. а. л. со свойством а m;
состоит из всех ф. а. л. со свойством 
.
, если все наборы, на к-рых она равна нулю, имеют общую координату, равную нулю. Аналогично с заменой 0 на 1 вводится свойство 
. Класс 
состоит из всех ф. а. л. со свойством 
; 
состоит из всех ф. а. л. со свойством 
