I've begun studying boolean algebra in mathematical logic, after studying a course on abstract algebra which ended with the definition of boolean lattices, so I'm familiar with some algebraic structures. But now that I've begun studying boolean algebra in mathematical logic, and I've come across the concept of a 'functionally complete' set. I understand it intuitively through digital circuits and combinational logic, and through algebraic manipulation too. But I was looking for a formal definition of a 'functionally complete' set for a notebook glossary. That's when I arrived at the concept of a 'clone'... and it's created a spectrum of questions that I haven't been able to find the answer of.
- Is a clone anything more than a magma whose set is a set of functions, and operation is the superposition operation?
- Does a clone require a 'basis' that it was generated from?
- What does it mean for the set of functions to be a projections? (is a projection just a generalization of a truth table)?
The Wikipedia article on clones explains this.
In contrast to that article, which defines general clones so that they are single-sorted and later defines abstract clones so that they are multisorted, I view clones as multisorted structures always: $$ {\mathbf C}= \langle C_0, C_1, C_2, \ldots; \{\textrm{comp}^m_k\;|\;m,k\geq 0\}, \{\pi_i^k\;|\;1\leq i\leq k\}\rangle. $$ Here $C_0, C_1, C_2, \ldots$ are sets. For a clone of operations on a set $A$, the set $C_n$ is a set of $n$-ary operations on $A$. (An $n$-ary operation on $A$ is a function $f\colon A^n\to A$.) For an abstract clone, each $C_n$ is just a set. I typically consider the $C_n$'s to be pairwise disjoint sets. Some people disallow the $0$-ary sort $C_0$.
The $(m+1)$-ary clone operation $\textrm{comp}^m_k$ is composition of one $m$-ary element with $m$ $k$-ary elements. For a clone of operations on a set $A$, this composition operation is defined so that $$ \textrm{comp}^m_k(f,g_1,\ldots,g_m) = f(g_1,\ldots,g_m). $$ The $0$-ary clone operation $\pi_i^k\in C_k$ is called the $k$-ary projection onto the $i$th variable. For a clone of operations on a set $A$, this projection is defined so that $ \pi_i^k(x_1,\ldots,x_k)=x_i. $ That is, $\pi_i^k\colon A^k\to A$ is the function $(a_1,\ldots,a_k)\mapsto a_i$ that accepts as input an element of $A^k$ and returns as output its $i$th coordinate.
The axioms for abstract clones are
These axioms generalize the axioms for monoids. Together, they allow one to prove a Cayley-type theorem stating that every abstract clone is isomorphic to a concrete clone of operations on some set.
Now I answer the questions:
It is awkward to think of superposition as a binary operation only, although it would be possible to develop clones this way if you also had operations for variable manipulation of clone elements. I would say instead that a clone is a multisorted set and superposition is a family of operations of different arities.
No.
A projection is not a generalization of a truth table.
A set $F$ of operations on a set $A$ is functionally complete if the clone on $A$ generated by $F$ is the clone of all operations on $A$. An algebra defined on a set $A$ is called functionally complete if its clone of polynomial operations is the clone of all operations on $A$. (The polynomial operations are those generated by the term operations and the constant operations on $A$.)
Example. The clone of the additive group of real numbers $\textrm{Clo}(\langle {\mathbb R}; +, -, 0\rangle)$ has sorts:
$C_0 = \{0\}$.
$C_1 = \{mx_1\;|\;m\in\mathbb Z\}$, $\pi_1^1 = x_1$
$C_2 = \{mx_1+nx_2\;|\;m,n\in\mathbb Z\}$, $\pi_1^2 = x_1$, $\pi_2^2 = x_2$
$C_3 = \{mx_1+nx_2+px_3\;|\;m,n,p\in\mathbb Z\}$, $\pi_1^3 = x_1$, $\pi_2^3 = x_2$, $\pi_3^3 = x_3$
ETC
Here $mx_1 = x_1+x_1+\cdots+x_1$ ($m$ $x_1$s).
Also, I am informally writing $x_i$ for $\pi_i^k$. This leaves me with a copy of $x_i$ in each $C_k$, $k\geq i$.
If $f(x_1,x_2)=x_1+x_2\in C_2$, then $\textrm{comp}^2_2(f,f,f) = f(f,f) = (x_1+x_2)+(x_1+x_2)=2x_1+2x_2\in C_2$.
Keeping $f=x_1+x_2\in C_2$, note that $\textrm{comp}^2_4(f,\pi_1^4,\pi_2^4) = f(\pi_1^4,\pi_2^4) = x_1+x_2 \in C_4$, and $\textrm{comp}^2_4(f,\pi_3^4,\pi_4^4) = f(\pi_3^4,\pi_4^4) = x_3+x_4 \in C_4$, Hence $\textrm{comp}^2_4(f,f(\pi_1^4,\pi_2^4), f(\pi_3^4,\pi_4^4))= (x_1+x_2)+(x_3+x_4) \in C_4$. This looks like $\textrm{comp}(f,f,f)$ again, but we need to watch out for superscripts and subscripts and projections.