On the role of logical connectives for primality and functional completeness of algebras of logics (Q2269795): Difference between revisions

It is well known that every \(n\)-ary function over the alphabet \(\{0,1\}\) can be expressed as a Boolean term function, i.e. as a function constructed by means of the operations (or logical connectives) conjunction, disjunction, negation, 0 and 1. In particular, this can be done in a normal conjunctive form, i.e. as a conjunction of elementary disjunctions. This is important for applications, for example in the design of switching circuits and synthesis of automata. More generally, the problem of expressibility of functions by means of suitable term functions turned out to be one of the key problems in all sciences where function systems appear. From the point of view of applications the most important sets of Boolean functions called complete (or primal) are those having the potential to generate all Boolean functions. In the present paper the authors focus on the problem which (natural) functions are sufficient to be added to a logical connective of implication (satisfying certain natural conditions) in order to obtain a complete class of functions. This approach, based on clone theory, also clarifies what is the role of different types of logical connectives in connection with the completeness problem. It is well known that the reduct of a two-element classical logic containing the connective of implication and a constant unary function \(c_{0}\) with value 0 is primal. This result is extended to finite algebras. If \(A\) is a finite universe with \(| A| >1\), and 0 and 1 are two distinct fixed elements of \(A\), let \(f:A^{2}\rightarrow A\) be a function which satisfies for all \(x\in A\), \[ f(0,x)=f(x,1)=f(x,x)=1,\quad f(1,x)=x \] . Denote by \(\mathcal{O}\) the set of (finitary) operations on \(A\). For \(m,n\geq 1\), the composition of an \(n\)-ary \(f\in \mathcal{O}\) with \(m\)-ary \(q_{1},\dots,q_{n}\in \mathcal{O}\) is the \(m\)-ary \(h\in \mathcal{O}\) defined for all \(a\in A^{m}\) by setting \(h(a)=f(q_{1}(a),\dots,q_{n}(a))\). A clone on \(A\) is a composition-closed subset \(C\) of \(\mathcal{O}\) containing all \(n\)-ary projections \(e_{i}^{n}\) (defined by \(e_{i}^{n}(a_{1},\dots,a_{n})=a_{i}\) for all \(a_{1},\dots,a_{n}\in A)\) for all \(1\leq i\leq n\). The clones on \(A\) ordered by set inclusion (as subsets of \(\mathcal{O}\)) form a complete lattice \(L\) in which the meet of any \(C\subseteq L\) is the set-theoretical intersection on \(C\). Denote by \(c_{0}\) and \(c_{1}\) the constant unary functions on \(A\) with value 0 or 1. The question that the authors address here is: if \(X\) is a set of operations on \(A\) such that \(f,c_{0}\in X\), when is the algebra \((A,X)\) primal or, equivalently, when is \(X\) complete? The answer to this question is given by Theorem 1 in terms of three types of maximal clones. This theorem shows that \(\langle c_{0},f\rangle\) (where \(f\) satisfies the condition from above) need not be primal. A lot of algebras connected with logic have other operations besides \(c_{0}\) and \(f\). To improve Theorem 1, the authors consider two additional operations, weak conjunction (\(x\odot 1=x=1\odot x\)) and dual strict negation (\(\neg 1=0\), \(\neg x=1\) otherwise) as well as another natural property of \(f\) (\(f(x,y)=f(y,x)=1\) implies \(x=y\)). This way, we have Theorem 2 which characterizes the algebra \((A,f,\neg,\odot)\) as functionally complete (i.e. \((A,X\cup \{c_{a}\}_{a\in A})\) is primal, where \(c_{a}\) denotes the constant unary operation with value \(a\)).