Relative completeness

Authors Rade Doroslovački, Jovanka Pantović, Ratko Tošić, Gradimir Vojvodić

Publication date 20 January 2002

clones functional completeness multi-valued logic

Many-valued logic (03B50) Operations and polynomials in algebraic structures, primal algebras (08A40)

Let \(P_k\) denote the set of all maps \(E_k^n \longrightarrow E_k\), for all \(n \in N\), where \(E_k = \{1,\dots,k\}\). A clone on \(E_k\) is a subset of \(P_k\) which contains all the projections \(f(x_1,\dots,x_n) = x_i\), and which is closed w.r.t. superpositions. Given a clone \(C\), a subset \(F\) of \(P_k\) is \(C\)-complete if the clone generated by \(P \cup C\) is equal to \(P_k\). It is known that \(F\) is \(C\)-complete iff \(F\) contains at least one mapping outside \(M_i\), where \(M_i\) is an arbitrary maximal clone containing \(C\). Six special sets of relations, denoted \(R_1,\dots,R_6\), are known to be sufficient for characterization of maximal clones.NEWLINENEWLINENEWLINE\(C\)-completeness w.r.t. four specified clones \(C\) (which were found to be of particular interest) is considered. These clones are generated by minimum and complement, by two negations, by transpositions, and by two unary functions, respectively. In each case, maximal clones containing \(C\) are detected by investigating relationships between the elements of \(C\) and the sets \(R_1,\dots,R_6\).NEWLINENEWLINENEWLINEThe paper consists of an extensive list of statements (64 statements are listed on less than five pages) without proofs, related to the established relationships of the above type.NEWLINENEWLINEFor the entire collection see [Zbl 0977.00022].

Recommendations

Cited in

(13)

This page was built for publication: Relative completeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2763578)