Post class

A class of functions of the algebra of logic (Boolean functions, cf. Boolean function) that is closed with respect to the operation of superposition. E. Post has established that the set of such classes is enumerable and has given an explicit description of them. He has also shown that all of them are finitely generated, and he has constructed the lattice with respect to inclusion formed by these classes. The set of the above-mentioned classes is exhausted by the list $ C _ {i} $, $ A _ {i} $, $ D _ {j} $, $ L _ {k} $, $ O _ {l} $, $ S _ {r} $, $ P _ {r} $, $ F _ {s} ^ { \mu } $, $ F _ {s} ^ { \infty } $, where $ i = 1 , 2 , 3 , 4 $; $ j = 1 , 2 , 3 $; $ k = 1 \dots 5 $; $ l = 1 \dots 9 $; $ r = 1 , 3 , 5 , 6 $; $ s = 1 \dots 8 $; $ \mu = 2 , 3 , . . . $.

The class $ C _ {1} $ contains all functions of the algebra of logic; $ C _ {2} $ consists of all functions of the algebra of logic $ f ( x _ {1} \dots x _ {n} ) $ such that $ f ( 0 \dots 0 ) = 0 $; $ C _ {3} $ consists of all functions of the algebra of logic such that $ f ( 1 \dots 1 ) = 1 $; $ C _ {4} = C _ {2} \cap C _ {3} $. The class $ A _ {1} $ consists of all monotone functions of the algebra of logic (cf. Monotone Boolean function); $ A _ {2} = C _ {2} \cap A _ {1} $; $ A _ {3} = C _ {3} \cap A _ {1} $; $ A _ {4} = A _ {2} \cap A _ {3} $. The class $ D _ {3} $ consists of all functions of the algebra of logic such that $ f ( x _ {1} \dots x _ {n} ) = \overline{f}\; ( \overline{x}\; _ {1} \dots \overline{x}\; _ {n} ) $; $ D _ {1} = C _ {4} \cap D _ {3} $; $ D _ {2} = A _ {1} \cap D _ {3} $. The class $ L _ {1} $ consists of all functions of the algebra of logic such that $ f ( x _ {1} \dots x _ {n} ) = x _ {1} + \dots + x _ {n} + d $ $ ( \mathop{\rm mod} 2 ) $, $ d \in \{ 0 , 1 \} $; $ L _ {2} = C _ {2} \cap L _ {1} $; $ L _ {3} = C _ {3} \cap L _ {1} $; $ L _ {4} = L _ {2} \cap L _ {3} $; $ L _ {5} = D _ {3} \cap L _ {1} $.

The class $ O _ {9} $ consists of all functions of the algebra of logic that are essentially dependent on not more than one variable; $ O _ {8} = A _ {1} \cap O _ {9} $; $ O _ {4} = D _ {3} \cap O _ {9} $; $ O _ {5} = C _ {2} \cap O _ {9} $; $ O _ {6} = C _ {3} \cap O _ {9} $; $ O _ {1} = O _ {5} \cap O _ {6} $; $ O _ {7} $ consists of all constant functions; $ O _ {2} = O _ {5} \cap O _ {7} $; $ O _ {3} = O _ {6} \cap O _ {7} $.

The class $ S _ {6} $ consists of all functions of the algebra of logic such that $ f ( x _ {1} \dots x _ {n} ) = x _ {1} \lor \dots \lor x _ {n} $ and all constant functions of the algebra of logic; $ S _ {3} = C _ {2} \cap S _ {6} $; $ S _ {5} = C _ {3} \cap S _ {6} $; $ S _ {1} = S _ {3} \cap S _ {5} $.

The class $ P _ {6} $ consists of all functions of the algebra of logic such that $ f ( x _ {1} \dots x _ {n} ) = x _ {1} \& \dots \& x _ {n} $ and all constant functions of the algebra of logic; $ P _ {5} = C _ {2} \cap P _ {6} $; $ P _ {3} = C _ {3} \cap P _ {6} $; $ P _ {1} = P _ {5} \cap P _ {3} $.

A function of the algebra of logic satisfies the condition $ a ^ \mu $ if $ \mu $- tuples on which it is equal to $ 0 $ have a common coordinate equal to zero. In a similar way, by replacing $ 0 $ by $ 1 $, one can introduce the condition $ A ^ \mu $.

The class $ F _ {4} ^ \mu $ consists of all functions of the algebra of logic with the property $ a ^ \mu $; $ F _ {1} ^ { \mu } = C _ {4} \cap F _ {4} ^ { \mu } $; $ F _ {3} ^ { \mu } = A _ {1} \cap F _ {4} ^ { \mu } $; $ F _ {2} ^ { \mu } = F _ {1} ^ { \mu } \cap F _ {3} ^ { \mu } $; $ F _ {8} ^ { \mu } $ consists of all functions of the algebra of logic with the property $ A ^ \mu $; $ F _ {5} ^ { \mu } = C _ {4} \cap F _ {8} ^ { \mu } $; $ F _ {7} ^ { \mu } = A _ {3} \cap F _ {8} ^ { \mu } $; $ F _ {6} ^ { \mu } = F _ {5} ^ { \mu } \cap F _ {7} ^ { \mu } $.

A function of the algebra of logic satisfies the condition $ a ^ \infty $ if all tuples on which it is equal to zero have a common coordinate equal to zero. Similarly, by replacing $ 0 $ by $ 1 $, one can introduce the property $ A ^ \infty $. The class $ F _ {4} ^ { \infty } $ consists of all functions of the algebra of logic with the property $ a ^ \infty $; $ F _ {1} ^ { \infty } = C _ {4} \cap F _ {4} ^ { \infty } $; $ F _ {3} ^ { \infty } = A _ {1} \cap F _ {4} ^ { \infty } $; $ F _ {2} ^ { \infty } = F _ {1} ^ { \infty } \cap F _ {3} ^ { \infty } $; $ F _ {8} ^ { \infty } $ consists of all functions of the algebra of logic with the property $ A ^ \infty $; $ F _ {5} ^ { \infty } = C _ {4} \cap F _ {8} ^ { \infty } $; $ F _ {7} ^ { \infty } = A _ {3} \cap F _ {8} ^ { \infty } $; $ F _ {6} ^ { \infty } = F _ {5} ^ { \infty } \cap F _ {7} ^ { \infty } $.

The lattice, with respect to inclusion, generated by these classes is shown in the figure. The classes are represented by points. Two points are connected by an arc if the underlying point represents a class immediately contained in the upper class (i.e. there are no intermediate classes between them).

Figure: p074010a

References

[1]	S.V. Yablonskii, G.P. Gavrilov, V.B. Kudryavtsev, "Functions of the algebra of logic and Post classes" , Moscow (1966) (In Russian) Zbl 0171.27701