                                              Notes prepared by
                                                 Stanley Burris
                                                   July 3, 2001

1 Clones

As we have seen in II.5 of LMCS, different collections of connectives can have quite different expressive power. An obvious measure of the expressive power of a set of connectives is to take all formulas which can be built out of them, along with their associated truth-tables. However, if we are only interested in the expressive power up to truth-table equivalence, then it suffices just to take the set of truth-tables associated with the formulas. This leads to the notion of a clone.

DEFINITION 1 Given a set A let F(A) be the set of all constants from A and all finitary functions on A. A clone on A is a subset X of F(A) such that

i. X is closed under composition;

ii. X contains all projection functions;

iii. a constant c is in X implies that finitary functions with constant value c are in X;

iv. if a finitary function with constant value c is in X then the constant c is in X.

Each subset X of F(A) is contained in a smallest clone on A, which we will call Cl(X). For an algebra A, the clone generated by the fundamental operations is called the clone of A.

Thus, for example, we can now say that a set S of connectives with truth-tables X is adequate for the classical propositional calculus if Cl(X) = F({0, 1}).

A finite algebra A which has the property that its clone is all functions on A is called a primal algebra. In II.5.1 of LMCS we essentially pointed out that the two-element Boolean algebra is a primal algebra. One can easily show that the finite fields GF(p), p a prime, are primal. It is not known if one can test a finite algebra for primality in polynomial time.

DEFINITION 2 Given two sets of connectives S_{1}, S_{2} with associated sets of truth-tables X_{1}, X_{2} we will say that S_{1} and S_{2} are truth-table equivalent if Cl(X_{1}) = Cl(X_{2}).

Exercises

Problem 1 Show that the 3-element Post-algebra ({0, 1, 2}, ∧,′), where the operations are defined by i ∧ j = min(i, j), and 1′ = 2, 2′ = 0, and 0′ = 1, is primal.

Problem 2 Show a finite field GF(p^{n}) is primal iff n = 1.

1.1 Duality

We want to define the notion of dual functions for finitary functions on the set {0, 1}. So consider f : {0, 1}^{n} ⟶ {0, 1}. The dual Δf of f is the function obtained by interchanging 1 and 0 in the arguments and values of f, i.e.,

Δf(x_{0}, …, x_{n−1}) = ¬f(¬x_{0}, …, ¬x_{n−1}).

We say that a function is self-dual if it is equal to its dual.

Two connectives are said to be dual if their associated truth-tables are dual, and a connective is self-dual if it is its own dual.

For X a set of finitary functions on {0,1} we define ΔX to be the set of duals of members of X.

THEOREM 3 Cl(ΔX) = ΔCl(X).

Proof. It suffices to show that dual and composition commute. But this is easy:

(Δf)(Δg_{0}, …, Δg_{k−1})(x_{0}, …, x_{n−1})
= ¬f(¬(¬g_{0}(¬x_{0}, …, ¬x_{n−1})), …, ¬(¬g_{k−1}(¬x_{0}, …, x_{n−1})))
= ¬f(g_{0}(¬x_{0}, …, ¬x_{n−1}), …, g_{k−1}(¬x_{0}, …, ¬x_{n−1}))
= Δ [f(g_{0}, …, g_{k−1})] (x_{0}, …, x_{n−1}).

REMARK 4 • There are 2^{2^{n−1}} self-dual n-ary functions on {0,1} for n ≥ 2, i.e., \sqrt{#n-ary functions} are self-dual.

• The only self-dual binary functions are the projections and their negations.

• The Sheffer stroke and Schröder’s connective are dual.

• The connectives ∨ and ∧ are dual.

• The connective ¬ is self-dual.

1.2 Post’s classification of 2-valued logics

Emil Post classified all possible clones on {0,1}, and hence in a natural sense all possible 2-valued propositional logics. His work was first presented in 1920 as a companion piece to his Ph.D. Thesis,^{1} and it was finally published in the book Two-valued Iterative Systems of Mathematical Logic,^{2} Princeton, 1941. The classification of E. Post was presented in a more modern notation by R. Lyndon (see [3]).

Post’s classification of clones on {0, 1} consisted in giving a set of generating functions for each clone. One consequence of his classification is that each clone on {0, 1} is finitely generated. We will give a list of bases for the clones following Lyndon. (Clones come in dual pairs, and only one member of each such pair will be given.)

We will take as our building blocks the constants

0, 1;

the truth-tables of the standard connectives

¬, ∨, ∧, ⟹ , ⟺ ;

the function + defined by

\begin{matrix}x & y & x + y \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{matrix}

the function (x, y, z) defined by

(x, y, z) = x ∧ (y ∨ z);

the function [x, y, z] defined by

[x, y, z] = x ∧ (y ⟺ z); and the functions d_{n}(x_{0}, …, x_{n−1}), for n ≥ 3, defined by

1His thesis results appear in [4].

2In the preface of his book he says that truth-tables were originated by Keyser.

d_{n}(x_{0}, …, x_{n−1}) = ⋁_{0≤i≤n−1} x_{0} ∧ ⋯ ∧ x̂_{i} ∧ ⋯ ∧ x_{n−1},

where the notation x̂_{i} means that x_{i} is omitted.

Now we are ready to give a basis (up to duality) for each of the countably many clones on {0, 1}:

\begin{matrix}¬ & ¬, 0 & ∨ & ∨, 0 & ∨, 1 \\ ∨, 0, 1 & ∨, ∧ & ∨, ∧, 0 & ∨, ∧, 0, 1 & + \\ +, ¬ & ⟹ , ¬ & ⟹ , ∧ & x + y + z & x + y + z, ¬ \\ ⟹ & ⟹ , d_{n} & (x, y, z) & (x, y, z), 0 & [x, y, z] \\ [x, y, z], ∨ & (x, y, z), d_{n} & (x, y, z), d_{n}, 0 & [x, y, z], d_{n} & d_{3} \\ d_{3}, x + y + z & d_{3}, x + y + z, ¬ & Ø & 1 & 0,1 \end{matrix}

Post (1921/1941) suggested that n-valued logics be considered. However one cannot give such a nice classification even for the 3-valued iterative systems since there are continuum many. [See Janov & Mucnik ([2]1959); Hulanicki & Świerczkowski ([1] 1960).] Connectives in n-valued logic can again be thought of as components in circuits. In multi-valued logic one of the interests is to find good components for designing circuits.

Exercises

Problem 3 Determine which binary operations on {0,1} generate the same clone.

Problem 4 Determine which ternary operations generate the same clone on {0,1}.

References

[1] A. Hulanicki and S. Świerckowski, Number of algebras with a given set of elements. Bull. Acad. Polon., Sci. Sér. Sci. Math. Astronom. Phys. 8 (1960), 283-284.

[2] Ju.I. Janov and A.A. Muchnik, On the existence of k-valued closed classes that have no bases. (Russian) Dokl. Akad. Nauk SSSR 127 (1959), 44–46.

[3] R. Lyndon, Identities in two-valued calculi. Trans. Amer. Math. Soc. 71 (1951), 457–465.

[4] E. Post, Introduction to a general theory of elementary propositions of logic. Amer. J. Math. 43 (1921), 163-185.