Lesson 2

Theorem (Post's functional completeness theorem). A set of connectives \(\Omega \subset B^{*}\) is complete if and only if it is not entirely contained in any of the following so-called “pre-complete classes”:

1. functions preserving zero: \(\mathcal{S}_{0}=\{f \colon f(0,\dotsc,0)=0\} \ ;\)
2. functions preserving one: \(\mathcal{S}_{1}=\{f \colon f(1,\dotsc,1)=1\} \ ;\)
3. monotone functions: \(\mathcal{M}=\{f \colon x \le y \Rightarrow f(x) \le f(y)\} \ ;\)
4. linear functions: \(\mathcal{L}=\{f \colon \deg(f) \le 1\} \ ;\)
5. self-dual functions: \(\mathcal{D}=\{f \colon f(x_{1}, \dotsc, x_{n})=\neg f(\overline{x_1}, \dotsc, \overline{x_n})\} \ .\)