Second-Order Formulas in Action

Yuri Movsisyan

Department of Mathematics and Mechanics, Yerevan State University, Yerevan, Armenia.

DOI: 10.4236/am.2024.159039                

Abstract

This survey article illustrates many important current trends and perspectives for the field and their applications, of interest to researchers in modern algebra, mathematical logic and discrete mathematics. It covers a number of directions, including completeness theorem and compactness theorem for hyperidentities; the characterizations of the Boolean algebra of n-ary Boolean functions and the bounded distributive lattice of n-ary monotone Boolean functions; the functional representations of finitely-generated free algebras of various varieties of lattices via generalized Boolean functions, etc.

Keywords

Boolean Algebra, Boolean Function, Distributive Lattice, Monotone Boolean Function, De Morgan Algebra, De Morgan Function, Boole-De Morgan Algebra, Quasi-De Morgan Function, Hyperidentity, Coidentity

1. Hyperidentitis and Coidentities

By definition, a Boolean algebra is a complemented bounded distributive lattice. In the nineteenth century, George Boole’s [1] attempt to formalize propositional logic led to the concept of Boolean algebra. Historically, lattice theory started with Boolean algebras which have played a fundamental role in the development of the lattice theory.

Boolean functions, i.e. $\left\{0,1\right\}$ -valued functions of a finite number on $\left\{0,1\right\}$ -valued variables, are among the most fundamental objects that have been investigated in pure and applied mathematics, especially in discrete mathematics, algebra, mathematical logic and computer science. The Boolean algebra of Boolean functions of n variables is a free Boolean algebra on n free generators. The bounded lattice of monotone Boolean functions of n variables is a free bounded distributive lattice on n free generators (R. Dedekind [2]). These are the first Boolean structures in both mathematics and applied mathematics, and they are used extensively in discrete mathematics.

Algebra and model theory study the connections between formal languages and their interpretations in models and algebras. The simplest and most widespread formal language is the first-order language (A. Church [3], A. I. Mal’tsev [4]-[7], G. Grätzer [8], C. Chang with H. Keisler [9], S. Burris with H. P. Sankappanavar [10], B. I. Plotkin [11]). The founders of the first-order language (logic) are Löwenheim, Skolem, Gödel, Łoś, Tarski, Mal’tsev and Birkhoff.

However, there exist very commonly encountered, classical algebraic structures that are not axiomatizable by the first-order formulae (logic). For example, rings, associative rings, commutative rings, associative-commutative rings, fields, or fields of fixed characteristics are axiomatized by first-order formulae, but their multiplicative groupoids, multiplicative semigroups and multiplicative groups are not, because these classes of groupoids, semigroups and groups are not closed under elementary equivalence (A. I. Mal’tsev, S. Kogalovskii [12], G. Sabbagh [13]). The situation is analogous for near-fields (M. Hall [14]), Grätzer algebras (G-fields) [15]-[18], topological rings and topological fields (L. S. Pontryagin [19]). However, if some class $\mathcal{K}$ of lattices is axiomatized by the first-order formulae, then the class of its multiplicative semigroups is also axiomatized by the first-order formulae [20].

Characterizations of such semigroups and groups are the most important problems in modern algebra, logic and topology. L. Fuchs ([21], p. 324) called the characterization of multiplicative groups of fields a big problem.

This is why it is necessary to widen the formal language to allow to express phenomena that the first-order logic can not capture.

An important extension of the first-order logic (language) is the second-order logic (language), described in detail in [3] [5] [6] [9] (also see [22]). The second-order formulae consist of the same logical symbols of $\&,\vee ,\neg ,\to ,\exists ,\forall$ of individual and functional (predicate) variables, which are used in the first-order formulae. The difference is that in the second-order formulae, the quantifiers $\forall ,\exists$ can be applied not only to individual variables, but also to functional (or to predicate) variables. Investigations of the second-order formulae (logic) go back to L. Henkin, A. I. Mal’tsev, A. Church, S. Kleene, A. Tarski. Many important mathematical concepts can be written in the second-order language. Consequently, investigation of the theories of the second-order languages (logic) is one of the central problems of algebra and mathematical logic (Mal’tsev [5]). For a compactness theorem for quasi-universal second-order formulae see [5] [22].

Starting with the 1960’s the following second-order formulae were studied in various domains of algebra and its applications (see [5] [18] [20] [23]-[63])

$\forall X_1,\cdots ,X_m\forall x_1,\cdots ,x_n\left(w_1=w_2\right),$ (1.1)

$\forall X_1,\cdots ,X_k\exists X_{k+1},\cdots ,X_m\forall x_1,\cdots ,x_n\left(w_1=w_2\right),$ (1.2)

$\exists x_1,\cdots ,x_n\forall X_1,\cdots ,X_m\left(w_1=w_2\right),$ (1.3)

$\exists X_1,\cdots ,X_k\forall X_{k+1},\cdots ,X_m\forall x_1,\cdots ,x_n\left(w_1=w_2\right),$ (1.4)

$\forall X_1,\cdots ,X_k\exists X_{k+1},\cdots ,X_t\forall X_{t+1},\cdots ,X_m\forall x_1,\cdots ,x_n\left(w_1=w_2\right),$ (1.5)

where $w_1,w_2$ are words (hyperterms) in the functional variables $X_1,\cdots ,X_m$ and the individual (object) variables $x_1,\cdots ,x_n$ . The first formula is called hyperidentity or $\forall (\forall )$ -identity (see [20] [27] [34] [35] [39] [40] [43] [50] [54] [64]-[69], and also [70]); the second (third, fourth, fifth) formula is called an $\forall \exists (\forall )$ -identity ($(\exists )\forall$ -identity, $\exists \forall (\forall )$ -identity, $\forall \exists \forall (\forall )$ -identity). Sometimes the $\forall \exists (\forall )$ -identity is called a generalized identity [27] [71], the $(\exists )\forall$ -identity is called a coidentity [30] [39] (also see [70]) and $\exists \forall (\forall )$ -identity is called a hybrid identity [32] [50]. The satisfiability of these second-order formulae in an algebra $\mathfrak{A}=\left(Q;\Sigma \right)$ is understood by functional quantifiers $\left(\forall X_i\right)$ and $\left(\exists X_j\right)$ , meaning: “for every value $X_i=A\in \Sigma$ of the corresponding arity” and “there exists a value $X_j=A\in \Sigma$ of the corresponding arity”. It is assumed that such a replacement is possible, that is

$\left\{\left|X_1\right|,\cdots ,\left|X_m\right|\right\}\subseteq \left\{\left|A\right||A\in \Sigma \right\}=T_{\mathfrak{A}}=T_{\left(\Sigma \right)},$

where $\left|S\right|$ is the arity of S, and $T_{\mathfrak{A}}$ is called the arithmetic type of $\mathfrak{A}$ . A T-algebra is an algebra with arithmetic type T. We say that a hyperidentity (coidentity) is called a T-hyperidentity (T-coidentity), if the set of arities of all functional variables accuring in it is contained in T.

Hyperidentities and coidentities are usually presented without quantifiers: ${\omega }_1={\omega }_2$ . The coidentity ${\omega }_1={\omega }_2$ is said to be satisfied in the algebra $\left(Q;\Sigma \right)$ , if there exist values for object variables $x_1,\cdots ,x_n$ from Q, such that the equality ${\omega }_1={\omega }_2$ holds when every functional variable in it is replaced by any operation of the corresponding arity from Σ (a possibility of such replacement is supposed, too). In addition, the object variables in the notation of the coidentity ${\omega }_1={\omega }_2$ are replaced by corresponding fixed values from Q.

Coidentities can be defined as second-order formulas of the following form, as well:

$\forall X_1,\cdots ,X_m\left(w_1=w_2\right).$

Example 1.1. In any multioperator Ω-group the following coidentity is valid:

$X\left(\underset{n}{\underbrace{0,\cdots ,0}}\right)=0,$

for all $n\in T_{\left(\Omega \right)}$ , where all object variables are replaced by the zero element of the Ω-group [70] [72] [73].

Theorem 1.1 (J. von Neumann). Let $L\left(+,\cdot \right)$ be a modular lattice and $a,b,c\in L$ . The sublattice of L, generated by the elements $a,b,c$ , is distributive iff the following coidentity of left distributivity

$X\left(a,Y\left(b,c\right)\right)=Y\left(X\left(a,b\right),X\left(a,c\right)\right)$

holds in $L\left(+,\cdot \right)$ .

Second-order formulae with analogous predicative quantifiers in models and algebraic systems are also often used in mathematical logic. For example, finiteness, the axiom of well-ordering, the continuum hypothesis, the property of being countable and others can be formulated within the second-order logic. Every algebra can be embedded into an algebra of functions whose identities are equivalent to hyperidentities or $\forall \exists (\forall )$ -identities (A. Cayley, P. M. Cohn, unpublished).

The above semantics is different from the standard definition of the semantics of second-order formulas (logics) ([3] [5] [6]). Studying logic via semantics is a well-established and very active branch of mathematical logic with many applications in computer science and elsewhere.

A variety (or equational class) is a class of algebras (all of the same similarity type or signature, or Ω-algebras) closed under the formation of products, subalgebras and homomorphic images. Equivalently, a variety is a class of algebras defined by a set of equations (identities). A hypervariety is a class of algebras (all of the same arithmetic type or the same signature) defined by a set of hyperidentities.

Note that even in the classical algebras (groups, semigroups, quasigroups, rings, etc) the characterization of varieties in which every finitely generated algebra is finite is an open problem (see S. Adian [74] [75], E. Zel’manov [76]-[79]).

A variety of algebras is called Burnside variety (W. Burnside) [80] if its any finitely generated algebra is finite.

In 1902, Burnside proposed the following problem: Is a finitely generated group satisfying an identity of the form $x^n=1$ necessarily finite? The answer in yes for $n=1,2,3,4$ and 6. The case $n\le 2$ is trivial, the case $n=3$ was settled by Burnside [81], the case $n=4$ by Sanov [82] and the case $n=6$ by M. Hall [14]. The original problem finally received a negative answer by Novikov and Adian in 1968 [83] (see also [74] [84]).

The numbers m and n in hyperidentity (1.1) are called the functional and object rank, respectively. A hyperidentity is said to be nontrivial if its functional rank is >1, and it is called trivial otherwise ($m=1$ ). A hyperidentity is called n-ary, if its functional variables are n-ary. For $n=1,2,3$ the n-ary hyperidentity is called unary, binary, ternary. A formula (hyperidentity, coidentity, ...) is called a formula (hyperidentity, coidentity, ...) of algebra $\mathfrak{A}$ , if it is satisfied in algebra $\mathfrak{A}$ . Let V be a variety or another class of algebras. A hyperidentity (coidentity, ...) $w_1=w_2$ is called a hyperidentity (coidentity, ...) of V if it is a hyperidentity (coidentity, ...) for any algebra $\mathfrak{A}\in V$ .

The concept of hyperidentity is present in many well known notions. For example, an algebra $\mathfrak{A}=\left(Q;\Sigma \right)$ is said to be Abelian (A.G.Kurosh [85]) or entropic (medial) if the following nontrivial hyperidentity

$X\left(Y\left(x_{11},\cdots ,x_{1n}\right),\cdots ,Y\left(x_{m1},\cdots ,x_{mn}\right)\right)=Y\left(X\left(x_{11},\cdots ,x_{m1}\right),\cdots ,X\left(x_{1n},\cdots ,x_{mn}\right)\right)$

is valid for all $m,n\in T_{\mathfrak{A}}$ . An algebra $\mathfrak{A}=\left(Q;\Sigma \right)$ is said to be idempotent if any its operation is idempotent, i.e. if the following hyperidentity of idempotency

$X\left(\underset{n}{\underbrace{x,\cdots ,x}}\right)=x$

is valid for all $n\in T_{\mathfrak{A}}$ .

A mode is an idempotent and entropic algebra (studied in monographs [86] [87]). A distributive bisemilattice (multisemilattice) [88] is a binary algebra with semilattice operations satisfying the following (nontrivial) hyperidentity of distributivity

$X\left(x,Y\left(y,z\right)\right)=Y\left(X\left(x,y\right),X\left(x,z\right)\right).$

A doppelsemigroup (see [89]-[97]) is an algebra with two binary operations satisfying the following non-trivial hyperidentity of associativity

$X\left(x,Y\left(y,z\right)\right)=Y\left(X\left(x,y\right),z\right).$

Binary algebras satisfying the hyperidentity of associativity

$X\left(x,Y\left(y,z\right)\right)=Y\left(X\left(x,y\right),z\right)$

we call hyperassociative algebras. These algebras under the name of Γ-Semigroups, Γ-Semirings (or gamma-Semigroups, gamma-Semirings) also were considered by various authors [98]-[112].

Example 1.2. Let A and B be non empty sets, Σ be the set of all mappings from B to A and Q be the set of all mappings from A to B. Then we can consider every element $\alpha \in \Sigma$ as a binary operation on Q:

$\alpha \left(a,b\right)=a\cdot \alpha \cdot b,$

where $a,b\in Q$ and $a\cdot \alpha \cdot b$ is the usual superposition of mappings. So we obtain a binary algebra $\left(Q;\Sigma \right)$ , which is hyperassociative.

The investigation of hyperidentities (coidentities) is a relatively new, actively developing field of pure and applied algebra. The concept of hyperidentity offers a high-level approach to algebraic questions, leading to new results, applications and problems. In particular, the investigation of hyperidentities is useful from the point of view of new technologies too, via optimization problems of block diagrams [40]. For applications of hyperidentities in discrete mathematics and topology see [62] [113]-[116]. For characterization of Sheffer functions and primal algebras via hyperidentities see (K. Denecke, R. Pöschel [113] [114]).

Hyperidentities are also “identities” of algebras in the category of bihomomorphisms ($\phi ,\tilde{\psi }$ ), where

$\phi A\left(x_1,\cdots ,x_n\right)=\left(\tilde{\psi }A\right)\left(\phi x_1,\cdots ,\phi x_n\right),$

which were studied in the monograph [39]. Thus, we obtain the categorical definition of hyperidentities. More about the application of such morphisms in the cryptography can be found in [117]. For the categorical definition of $\forall \exists (\forall )$ -identities and Birkhoff style theorem for $\forall \exists (\forall )$ -identities see [29] (Belousov’s problem).

Hyperidentities for binary algebras with quasigroup operations were first considered by V. D. Belousov [27] (as a special case of $\forall \exists (\forall )$ -identities which earlier is considered by R. Schauffler ([23] [24]) in coding theory) and then J. Aczel [118], about the classification of associative and distributive hyperidentities in binary algebras with quasigroup operations. Currently, more general results about these and other classifications of hyperidentities may be found in [20] [39] and [40]. Observe that in algebras with quasigroup operations many $\forall \exists \forall (\forall )$ -identities are equivalent to hyperidentities (see [20]). Coidentities for algebras were first considered in [30] [39].

The multiplicative groups of fields have been characterized in [119] via hyperidentities. On the base of these results the concept of binary G-spaces is developed in topology [115]. The hyperidentities of varieties of lattices, modular lattices, distributive lattices, Boolean algebras, De Morgan algebras and weakly idempotent lattices have been characterized in the works [63] [120]-[122].

Theorem 1.2. The variety of lattices satisfies the following hyperidentities:

$X\left(x,x\right)=x,$ (1.6)

$X\left(x,y\right)=X\left(y,x\right),$ (1.7)

$X\left(x,X\left(y,z\right)\right)=X\left(X\left(x,y\right),z\right),$ (1.8)

$X\left(Y\left(X\left(x,y\right),z\right),Y\left(y,z\right)\right)=Y\left(X\left(x,y\right),z\right).$ (1.9)

And conversely, every hyperidentity of the variety of lattices is a consequence of the hyperidentities: (1.6)-(1.9) (see [63]).

Theorem 1.3. The variety of modular lattices satisfies the following hyperidentities: (1.6)-(1.9) and

$X\left(Y\left(x,X\left(y,z\right)\right),Y\left(y,z\right)\right)=Y\left(X\left(x,Y\left(y,z\right)\right),X\left(y,z\right)\right).$ (1.10)

And conversely, every hyperidentity of the variety of modular lattices is a consequence of the hyperidentities: (1.6)-(1.10) (see [63]).

Theorem 1.4. The variety of distributive lattices satisfies the following hyperidentities: (1.6)-(1.8) and

$X\left(x,Y\left(y,z\right)\right)=Y\left(X\left(x,y\right),X\left(x,z\right)\right).$ (1.11)

And conversely, every hyperidentity of the variety of distributive lattices is a consequence of the hyperidentities: (1.6)-(1.8), (1.11) (see [63]).

Theorem 1.5. The variety of Boolean algebras satisfies the following hyperidentities: (1.6)-(1.8), (1.11) and

$F\left(F\left(x\right)\right)=x,$ (1.12)

$X\left(F\left(x\right),y\right)=X\left(F\left(X\left(x,y\right)\right),y\right),$ (1.13)

$F\left(X\left(F\left(X\left(x,y\right)\right),F\left(X\left(x,F\left(y\right)\right)\right)\right)\right)=x.$ (1.14)

And conversely, every hyperidentity of the variety of Boolean algebras is a consequence of the hyperidentities: (1.6)-(1.8), (1.11)-(1.14).

All hyperidentities of the variety of Boolean algebras are consequences of one of its hyperidentities, i.e. the hyperequational theory of the variety of Boolean algebras is one-based (see [63]).

Theorem 1.6. The variety of De Morgan algebras satisfies the following hyperidentities: (1.6)-(1.8), (1.11), (1.12) and

$F\left(x\right)=G\left(x\right),$ (1.15)

$F\left(Y\left(F\left(X\left(x,y\right)\right),z\right)\right)=X\left(F\left(Y\left(F\left(x\right),z\right)\right),F\left(Y\left(F\left(y\right),z\right)\right)\right),$ (1.16)

$X\left(F\left(X\left(x,y\right)\right),F\left(x\right)\right)=F\left(x\right),$ (1.17)

$X\left(x,X\left(y,z\right)\right)=X\left(Y\left(x,Y\left(y,z\right)\right),F\left(Y\left(F\left(x\right),Y\left(F\left(y\right),F\left(z\right)\right)\right)\right)\right),$ (1.18)

$\begin{array}{l}X\left(F\left(X\left(Y\left(x,e\right),Y\left(x,Y\left(y,e\right)\right)\right)\right),F\left(X\left(Y\left(z,e\right),Y\left(z,Y\left(t,e\right)\right)\right)\right)\right)\\ =X(F\left(X\left(Y\left(x,Y\left(z,e\right)\right)\right),Y\left(x,Y\left(y,Y\left(z,Y\left(u,e\right)\right)\right)\right)\right),\\ F\left(X\left(F\left(Y\left(F\left(Y\left(x,Y\left(y,e\right)\right)\right),F\left(Y\left(z,Y\left(t,e\right)\right)\right)\right),e\right)\right)\right)).\end{array}$ (1.19)

And conversely, every hyperidentity of the variety of De Morgan algebras is a consequence of the hyperidentities: (1.6)-(1.8), (1.11), (1.12), (1.15)-(1.19).

The hyperequational theory of the variety of De Morgan algebras is not one-based (see [63]).

A hyperidentity ${\omega }_1={\omega }_2$ is called termal or t-hyperidentity of the algebra $\mathfrak{A}$ if it is valid in the term algebra $ℱ\left(\mathfrak{A}\right)$ . Let V be a variety. A hyperidentity ${\omega }_1={\omega }_2$ is called a termal hyperidentity of V if it is a termal hyperidentity for any algebra $\mathfrak{A}\in V$ . Termal hyperidentities for varieties were first considered by W. Taylor ([34]) (as a special case of Mal’tsev conditions for varieties) for characterization of classes of varieties which are closed under formation of equivalent varieties, products of varieties, reducts of varieties and subvarieties. Since the operations of an algebra are included in the set of term operations (clone) of the algebra, the concept of termal hyperidentity of a variety is stronger than the concept of hyperidentity. In particular, the variety of rings (even commutative rings) does not have termal hyperidentities except $w=w$ , but has hyperidentities.

Termal hyperidentities of varieties of groups and semigroups have been characterized by G. Bergman [35] (also see [36]). Termal hyperidentities of the variety of lattices and of the variety of semilattices were studied by R. Padmanabhan and P. Penner ([37] [44] [123]).

Hyperidentities and coidentities in algebras as an individual direction of investigations, were first presented in the monographs [20] [39] (see also [124]-[126]).

2. Bihomomorphisms of T-Algebras

Let $\mathfrak{A}=\left(A;\Sigma \right)$ be a T-algebra and ${\mathfrak{A}}^{\prime }=\left(A^{\prime };{\Sigma }^{\prime }\right)$ be a T’-algebra, where $T\subseteq T^{\prime }$ . The pair $\left(\phi ,\tilde{\psi }\right)$ of maps $\phi :A\to A^{\prime }$ and $\tilde{\psi }:\Sigma \to {\Sigma }^{\prime }$ is called a bihomomorphism from T-algebra $\mathfrak{A}$ into T’-algebra ${\mathfrak{A}}^{\prime }$ and is denoted by $\left(\phi ,\tilde{\psi }\right):\mathfrak{A}\Rightarrow {\mathfrak{A}}^{\prime }$ or $\left(\phi ,\tilde{\psi }\right):\mathfrak{A}\rightrightarrows {\mathfrak{A}}^{\prime }$ , if the map $\tilde{\psi }$ preserves the arity of operations, i.e., $\left|\tilde{\psi }f\right|=\left|f\right|$ for any operation $f\in \Sigma$ , and the equality

$\phi f\left(x_1,\cdots ,x_n\right)=\left[\tilde{\psi }f\right]\left(\phi x_1,\cdots ,\phi x_n\right)$

holds for all n-ary operations $f\in \Sigma$ and for all $x_1,\cdots ,x_n\in A$ .

Now we define the concepts of subalgebra, congruence relation and quotient algebra for T-algebras.

An algebra ${\mathfrak{A}}^{\prime }=\left(A^{\prime };{\Sigma }^{\prime }\right)$ is called a subalgebra of the algebra $\mathfrak{A}=\left(A;\Sigma \right)$ if $A^{\prime }\subseteq A$ and every operation from ${\Sigma }^{\prime }$ is the restriction of some operation from Σ (to the subset $A^{\prime }$ ). For example, the additive semigroup of all natural numbers is a subalgebra of the ring of integers, every Abelian group is a subalgebra of some ring, and, a fortiori, every groupoid is a subalgebra of some ring. Every semi-lattice is a subalgebra of some distributive lattice and every distributive lattice is a subalgebra of some Boolean algebra, and so on. When we wish to specify the arithmetic type of subalgebras, we call them T-subalgebras.

An intermediate notion here is that of a subsystem. Let $\mathfrak{A}=\left(A;\Sigma \right)$ be an arbitrary T-algebra, and let $A^{\prime }\subseteq A$ , ${\Sigma }^{\prime }\subseteq \text{Σ}$ , where $A^{\prime }\ne \varnothing$ and ${\Sigma }^{\prime }\ne \varnothing$ . A pair ${\mathfrak{A}}^{\prime }=\left(A^{\prime };{\Sigma }^{\prime }\right)$ is called a subsystem of the T-algebra $\mathfrak{A}$ if $A^{\prime }$ is closed with respect to all the operations of ${\Sigma }^{\prime }$ . Subsystems of the form $\left(A^{\prime };\Sigma \right)$ are called principal.

A class of T-algebras is called hereditary if it contains all the T-subalgebras of any T-algebra from itself.

Let $\mathfrak{A}=\left(A;\Sigma \right)$ be a T-algebra and r and $\tilde{t}$ be equivalence relations defined respectively on the sets A and Σ. The pair $q=\left(r,\tilde{t}\right)$ is called a congruence relation (or simply congruence) of the T-algebra $\mathfrak{A}$ if the following two conditions hold:

1) $\tilde{t}$ preserves the arity of the operations, i.e., $f\tilde{t}g$ implies $\left|f\right|=\left|g\right|$ , for any two operations $f,g\in \Sigma$ ;

2) the relations r and $\tilde{t}$ are compatible in the following sense:

$x_{i}r{y}_i,i=1,\cdots ,n,f\tilde{t}g\Rightarrow f\left(x_1,\cdots ,x_n\right)rg\left(y_1,\cdots ,y_n\right),$

for any elements $x_i,y_i\in A$ and any n-ary operations $f,g\in \Sigma$ .

The class of all congruences $\left(r,\tilde{t}\right)$ of an T-algebra $\mathfrak{A}$ is a lattice and denoted by $Con\left(\mathfrak{A}\right)$ .

If r is a congruence relation of $\mathfrak{A}=\left(A;\Sigma \right)$ considered as an Ω-algebra for some type Ω, then $\left(r,\tilde{0}\right)$ is obviously a congruence of $\mathfrak{A}$ considered as a T-algebra and vice versa, where $\tilde{0}$ is the identity relation of Σ, i.e., $\tilde{0}=\left\{\left(f,f\right)|f\in \Sigma \right\}$ .

If $q=\left(r,\tilde{t}\right)$ is a congruence of a T-algebra $\mathfrak{A}=\left(A;\Sigma \right)$ then every element ${\left[f\right]}_{\tilde{t}}$ of the quotient set $\Sigma /\tilde{t}$ defines an operation on the quotient set $Q/r$ in the following way:

${\left[f\right]}_{\tilde{t}}\left({\left[x_1\right]}_r,\cdots ,{\left[x_n\right]}_r\right)={\left[f\left(x_1,\cdots ,x_n\right)\right]}_r,$

where $f\in \Sigma$ , $\left|f\right|=n$ , $x_1,\cdots ,x_n\in A$ .

The definition of a congruence implies that the operation ${\left[f\right]}_{\tilde{t}}$ is well defined. As a result we shall obtain a quotient algebra of the T-algebra $\mathfrak{A}$ modulo the congruence $q=\left(r,\tilde{t}\right)$ , denoted by $\mathfrak{A}/q$ .

A congruence $q=\left(r,\tilde{t}\right)$ of a T-algebra $\mathfrak{A}=\langle Q;\Sigma \rangle$ is said to be nuclear if different elements of $\Sigma /\tilde{t}$ define different operations on $Q/r$ , that is

$A\tilde{t}B\iff A\left(x_1,\cdots ,x_n\right)rB\left(x_1,\cdots ,x_n\right),\forall x_1,\cdots ,x_n\in Q,$

where $A,B\in \Sigma$ , $\left|A\right|=\left|B\right|=n\in T$ .

For a congruence $q=\left(r,\tilde{t}\right)$ of a T-algebra $\mathfrak{A}=\left(A;\Sigma \right)$ the natural bihomomorphism $\left({\pi }_q,{\tilde{\pi }}_q\right):\mathfrak{A}\rightrightarrows \mathfrak{A}/q$ is defined by ${\pi }_q\left(a\right)={\left[a\right]}_r$ ,$a\in A$ ,${\tilde{\pi }}_q\left(f\right)={\left[f\right]}_{\tilde{t}}$ ,$f\in \Sigma$ .

3. Biautomorphisms of T-Algebras

A bihomomorphism $\left(\phi ,\tilde{\psi }\right)$ is called a biepimorphism (bimonomorphism, biisomorphism) if the maps $\phi$ and $\tilde{\psi }$ are surjective (injective, bijective). A bihomomorphism $\left(\phi ,\tilde{\psi }\right)$ is called a semiepimorphism, (semimonomorphism, semiisomorphism) if the map $\phi$ is surjective (injective, bijective). A bihomomorphism (biisomorphism) of a T-algebra into itself is called a biendomorphism, (biautomorphism). Any semimonomorphism $\left(\phi ,\tilde{\psi }\right)$ of T-algebras is a bimonomorphism:

$\begin{array}{l}\tilde{\psi }f=\tilde{\psi }g\to \tilde{\psi }f\left(\phi x_1,\cdots ,\phi x_n\right)=\tilde{\psi }g\left(\phi x_1,\cdots ,\phi x_n\right)\to \\ \phi f\left(x_1,\cdots ,x_n\right)=\phi g\left(x_1,\cdots ,x_n\right)\to f\left(x_1,\cdots ,x_n\right)=g\left(x_1,\cdots ,x_n\right)\to f=g,\end{array}$

where $\left|f\right|=\left|g\right|=n$ . We denote $\mathfrak{A}\simeq {\mathfrak{A}}^{\prime }$ (or $\mathfrak{A}\cong {\mathfrak{A}}^{\prime }$ ) for biisomorphic T-algebras $\mathfrak{A}$ and ${\mathfrak{A}}^{\prime }$ , i.e. if there exists a biisomorphism $\left(\phi ,\tilde{\psi }\right):\mathfrak{A}\Rightarrow {\mathfrak{A}}^{\prime }$ .

A congruence $q=\left(r,\tilde{t}\right)$ of a T-algebra $\mathfrak{A}=\langle Q;\Sigma \rangle$ is said to be fully invariant if it preserves any biendomorphism $\left(\phi ,\tilde{\psi }\right)$ of this algebra, that is,

$xry\to \phi \left(x\right)r\phi \left(y\right)$

and

$A\tilde{t}B\to \tilde{\psi }\left(A\right) \tilde{t} \tilde{\psi }\left(B\right),$

where $x,y\in Q$ and $A,B\in \Sigma$ .

A T-algebra ${\mathfrak{A}}^{\prime }$ is called a bihomomorphic image of the T-algebra $\mathfrak{A}$ if there exists a biepimorphism $\left(\phi ,\tilde{\psi }\right):\mathfrak{A}\rightrightarrows {\mathfrak{A}}^{\prime }$ . A class of T-algebras is said to be bihomomorphically closed if along with each T-algebra it contains every bihomomorphic image of that algebra under any bihomomorphism.

The pair $\left(\epsilon ,\tilde{\epsilon }\right)$ of identical maps $\epsilon :A\to A$ and $\tilde{\epsilon }:\Sigma \to \Sigma$ is an biautomorphism of T-algebra $\left(A;\Sigma \right)$ .

The set of all biendomorphisms (biautomorphisms) of the same T-algebra forms a semigroup with identity (group) under the componentwise multiplication of pairs:

$\left({\phi }_1,{\tilde{\psi }}_1\right)\cdot \left({\phi }_2,{\tilde{\psi }}_2\right)=\left({\phi }_1{\phi }_2,{\tilde{\psi }}_1{\tilde{\psi }}_2\right).$

We will denote the group of all biautomorphisms $\left(\phi ,\tilde{\psi }\right)$ of the same T-algebra $\mathfrak{A}$ by $Aut\mathfrak{A}$ . The biautomorphisms of the form $\left(\phi ,\tilde{\epsilon }\right)$ , where $\tilde{\epsilon }$ is the identical mapping, are ordinary automorphisms and form a group denoted by $Au{t}^{(\circ )}\mathfrak{A}$ . Obviously $Au{t}^{(\circ )}\mathfrak{A}⊴Aut\mathfrak{A}$ , i.e., $Au{t}^{(\circ )}\mathfrak{A}$ is an invariant subgroup of the group $Aut\mathfrak{A}$ .

Theorem 3.1 ([39]). For any group G there exists a binary algebra $\mathfrak{A}$ with the hyperidentity of associativity

$X\left(x,Y\left(y,z\right)\right)=Y\left(X\left(x,y\right),z\right)$

such that $G\simeq Aut\mathfrak{A}$ and $Au{t}^{(\circ )}\mathfrak{A}$ is singletone.

Theorem 3.2 ([39]). For any group G there exists a binary algebra $\mathfrak{A}$ with the hyperidentity of distributivity

$X\left(x,Y\left(y,z\right)\right)=Y\left(X\left(x,y\right),X\left(x,z\right)\right)$

such that $G\simeq Au{t}^{(\circ )}\mathfrak{A}$ and $HolG(\cdot )\simeq Aut\mathfrak{A}$ .

Below we will formulate a more general result.

Theorem 3.3. Let G be an arbitrary group with an invariant subgroup H. Then there exists an algebra $\mathfrak{A}$ such that $G\simeq Aut\mathfrak{A}$ and $H\simeq Au{t}^{(\circ )}\mathfrak{A}$ , where the last isomorphism is induced by the first isomorphism.

Let $\mathfrak{A}=\left(A;\Sigma \right)$ and ${\mathfrak{A}}^{\prime }=\left(A^{\prime };{\Sigma }^{\prime }\right)$ be T-algebras. With each bihomomorphism $\left(\phi ,\tilde{\psi }\right):\mathfrak{A}\Rightarrow {\mathfrak{A}}^{\prime }$ two congruencies are associated, called the kernel and the weak kernel of that bihomomorphism and denoted by $Ker\left(\phi ,\tilde{\psi }\right)$ and $WKer\left(\phi ,\tilde{\psi }\right)$ respectively. They are defined as follows:

$WKer\left(\phi ,\tilde{\psi }\right)=\left(Ker\phi ,Ker\tilde{\psi }\right),$

$Ker\left(\phi ,\tilde{\psi }\right)=\left(Ker\phi ,\tilde{t}\right),$

where

$f\tilde{t}g\iff {\tilde{\psi }f|}_{\phi \left(A\right)}={\tilde{\psi }g|}_{\phi \left(A\right)},f,g\in \text{Σ}.$

Clearly $Ker\tilde{\psi }\subseteq \tilde{t}$ and if $\phi$ is a surjection then $Ker\tilde{\psi }=\tilde{t}$ .

But in general $WKer\left(\phi ,\tilde{\psi }\right)\ne Ker\left(\phi ,\tilde{\psi }\right)$ . For example, let $\left(\phi ,\tilde{\epsilon }\right)$ be an endomorphism of a non-zero ring, where $\phi$ is the zero map and $\tilde{\epsilon }$ is the identical. Then $WKer\left(\phi ,\tilde{\psi }\right)\ne Ker\left(\phi ,\tilde{\psi }\right)$ .

In general we have $WKer\left(\phi ,\tilde{\psi }\right)\le Ker\left(\phi ,\tilde{\psi }\right)$ , where the partial order between two congruencies is defined in the natural way:

$\left(r_1,{\tilde{t}}_1\right)\le \left(r_2,{\tilde{t}}_2\right)\iff r_1\subseteq r_2,{\tilde{t}}_1\subseteq {\tilde{t}}_2.$

The class of all congruencies of the same T-algebra forms a complete algebraic lattice with respect to this partial order “≤”.

4. Superproducts and Filtered Products of T-Algebras

Now we define the concepts of direct and subdirect products for T-algebras.

Let ${\mathfrak{A}}_i=\left(A_i;{\Sigma }_i\right),i\in I$ be T-algebras of the same arithmetic type. We form the Cartesian product $\widehat{A}={\displaystyle {\prod }_{i\in I}{A}_i}$ . In addition we form the Cartesian product ${\displaystyle {\prod }_{i\in I}{\Sigma }_i}$ and define the subset $\widehat{\Sigma }\subseteq {\displaystyle {\prod }_{i\in I}{\Sigma }_i}$ as the set of all possible functions $F:I\to {\displaystyle {\cup }_{i\in I}{\Sigma }_i}$ satisfying the following two conditions:

1) $F\left(i\right)\in {\Sigma }_i$ for all $i\in I$ ;

2) $\left|F\left(i\right)\right|=\left|F\left(j\right)\right|$ for all $i,j\in I$ ,

that is, for fixed F the arity of an operation $F\left(i\right)\in {\Sigma }_i$ does not depend on $i\in I$ .

The set $\widehat{\Sigma }$ can be identified with the set of all possible systems $F={\left(F_i\right)}_{i\in I}$ of operations of the same arity, with one taken from each set ${\Sigma }_i$ . We write $\widehat{\Sigma }={\displaystyle {\prod }_{i\in I}{\Sigma }_i}$ . If $F\in \widehat{\Sigma }$ and $\left|F\left(i\right)\right|=n$ , then F defines an n-ary operation on the set $\widehat{A}={\displaystyle {\prod }_{i\in I}{A}_i}$ defined componentwise:

$F\left(f_1,\cdots ,f_n\right)\left(i\right)=F\left(i\right)\left(f_1\left(i\right),\cdots ,f_n\left(i\right)\right),i\in I,$

where $f_1,\cdots ,f_n\in \widehat{A}$ .

As result we obtain a T-algebra $\widehat{\mathfrak{A}}=\left(\widehat{A};\widehat{\Sigma }\right)$ , which is called the (direct) product of the T-algebras ${\mathfrak{A}}_i,i\in I$ , or their direct T-product and is written $\widehat{\mathfrak{A}}={\displaystyle {\prod }_{i\in I}{\mathfrak{A}}_i}$ .

The direct product of T-algebras ${\mathfrak{A}}_i,i\in I$ is also called their superproduct. The superproduct of two T-algebras $\mathfrak{A}$ and $\mathfrak{B}$ is denoted by $\mathfrak{A}⊳⊲\mathfrak{B}$ . For example, the superproduct $L_1⊳⊲L_2$ of the two lattices $\left(L_1;{\wedge }_1,{\vee }_1\right)$ and $\left(L_1;{\wedge }_1,{\vee }_1\right)$ is an algebra $\left(L_1\times L_2;\wedge ,\vee ,\cdot ,+\right)$ with four binary operations:

$\begin{array}{ll}\wedge =\left({\wedge }_1,{\vee }_2\right),\hfill & \vee =\left({\vee }_1,{\wedge }_2\right),\hfill \\ \cdot =\left({\wedge }_1,{\wedge }_2\right),\hfill & +=\left({\vee }_1,{\vee }_2\right),\hfill \end{array}$

which operate component-wise.

The semisubalgebra (reduct) of direct product is called a semidirect product.

The projection maps

${\pi }_j:{\displaystyle \prod }_{i\in I}{A}_i\to A_j\text{and}{\tilde{\pi }}_j:\widehat{\Sigma }\to {\Sigma }_j$

for each $j\in I$ are defined by

${\pi }_j\left(f\right)=f\left(j\right)\text{and}{\tilde{\pi }}_j\left(F\right)=F\left(j\right).$

These maps give surjective bihomomorphisms

$\left({\pi }_j,{\tilde{\pi }}_j\right):{\displaystyle \prod }_{i\in I}{\mathfrak{A}}_i\rightrightarrows {\mathfrak{A}}_j.$

Definition 4.1. A T-algebra $\mathfrak{A}$ is called a subdirect product of the T-algebras ${\mathfrak{A}}_i,i\in I$ , if $\mathfrak{A}$ is a subalgebra of the direct product ${\displaystyle {\prod }_{i\in I}{\mathfrak{A}}_i}$ and the projection maps ${\pi }_i$ and ${\tilde{\pi }}_i$ are surjective for all $i\in I$ .

Definition 4.2. A T-algebra $\mathfrak{A}=\left(A;\Sigma \right)$ is called subdirectly irreducible if $\left|A\right|>1$ and the (componentwise) intersection of all nonzero congruencies of $\mathfrak{A}$ is nonzero.

If r is a congruence of an algebra $\mathfrak{A}$ considered as an Ω-algebra, then $\left(r,\tilde{0}\right)$ is a congruence of $\mathfrak{A}$ considered as a T-algebra. Further, if $\left(r,\tilde{t}\right)$ is a congruence of an algebra $\mathfrak{A}$ considered as a T-algebra, then $\left(r,\tilde{0}\right)$ is also a congruence of $\mathfrak{A}$ considered as a T-algebra, i.e., r is a congruence of an algebra $\mathfrak{A}$ considered as an Ω-algebra. From these facts we conclude that an algebra $\mathfrak{A}$ is subdirectly irreducible as an Ω-algebra if and only if it is subdirectly irreducible as a T-algebra.

Theorem 4.1 (see Birkhoff’s subdirect representation theorem [127]). Every T-algebra $\mathfrak{A}$ can be represented as a subdirect product of subdirectly irreducible T-algebras, which are bihomomorphic images of $\mathfrak{A}$ . Every finite algebra can be subdirectly embedded into a product of finitely many finite subdirectly irreducible algebras.

A class of T-algebras is said to be multiplicatively closed if it contains the direct product of any family of T-algebras from this class.

Let ${\mathfrak{A}}_i=\langle Q_i;{\Sigma }_i\rangle$ , $i\in I$ , be T-algebras of the same arithmetic type, and let $\mathcal{D}$ be a filter¹ I [6]. on I. We introduce the relation ${\equiv }_{\mathcal{D}}$ defined on ${\displaystyle \prod }_{i\in I}{Q}_i$ and the relation ${~}_{\mathcal{D}}$ defined on $\underset{i\in I}{{\displaystyle \tilde{\prod }}}{\Sigma }_i$ by setting

$f{\equiv }_{\mathcal{D}}g\iff \left\{\alpha \in I|f\left(\alpha \right)=g\left(\alpha \right)\right\}\in \mathcal{D},$

where $f,g\in {\displaystyle \prod }_{i\in I}{Q}_i$ , and

$F{~}_{\mathcal{D}}G\iff \left\{\alpha \in I|F\left(\alpha \right)=G\left(\alpha \right)\right\}\in \mathcal{D},$

where $F,G\in \underset{i\in I}{{\displaystyle \tilde{\prod }}}{\Sigma }_i$, $\left|F\right|=\left|G\right|$ .

According to the definition of a filter the relations ${\equiv }_{\mathcal{D}}$ and ${~}_{\mathcal{D}}$ will be equivalence relations. In addition, it is easy to prove that the pair of equivalence relations $\left({\equiv }_{\mathcal{D}},{~}_{\mathcal{D}}\right)$ is a congruence of the product of the T-algebras ${\mathfrak{A}}_i=\langle Q_i;{\Sigma }_i\rangle$ , $i\in I$ . The corresponding quotient algebra is denoted by ${\displaystyle \prod }_{i\in I}{\mathfrak{A}}_i/\mathcal{D}$ and is called the filtered product (with respect to the filter $\mathcal{D}$ ) of the T-algebras ${\mathfrak{A}}_i=\langle Q_i;{\Sigma }_i\rangle$ , $i\in I$ . A filtered product of T-algebras with respect to an ultrafilter is called an ultraproduct of T-algebras.

Moreover, the congruence $\left({\equiv }_{\mathcal{D}},{~}_{\mathcal{D}}\right)$ is nuclear. Indeed, for any $f_1,\cdots ,f_n\in {\displaystyle \prod }_{i\in I}{Q}_i$ we have

$\begin{array}{l}F{~}_{\mathcal{D}}G\iff \left\{\alpha \in I|F\left(\alpha \right)=G\left(\alpha \right)\right\}\in \mathcal{D}\\ \iff \left\{\alpha \in I|F\left(\alpha \right)\left(f_1\left(\alpha \right),\cdots ,f_n\left(\alpha \right)\right)=G\left(\alpha \right)\left(f_1\left(\alpha \right),\cdots ,f_n\left(\alpha \right)\right)\right\}\in \mathcal{D}\\ \iff \left\{\alpha \in I|F\left(f_1,\cdots ,f_n\right)\left(\alpha \right)=G\left(f_1,\cdots ,f_n\right)\left(\alpha \right)\right\}\in \mathcal{D}\\ \iff F\left(f_1,\cdots ,f_n\right)\left(\alpha \right){\equiv }_{\mathcal{D}}G\left(f_1,\cdots ,f_n\right)\left(\alpha \right).\end{array}$

As a product of T-algebras the superproduct of two non-zero rings (lattices), where $T=\left\{2\right\}$ , is an algebra with four binary operations, and does not a ring (lattice). However it follows from the following Proposition that an ultraproduct of a finite number of finite rings (lattices), as an ultraproduct of T-algebras, is a ring (lattice).

Proposition 4.1. Let ${\mathfrak{A}}_0,\cdots ,{\mathfrak{A}}_{n-1}$ be pairwise nonisomorphic finite T-algebras with finite sets of operations, and let ${\mathfrak{A}}_i$ , $i\in I$ , be a non-empty family of T-algebras, each of which is one of the algebras ${\mathfrak{A}}_0,\cdots ,{\mathfrak{A}}_{n-1}$ . If $\mathcal{D}$ is an ultrafilter on I, then there exists a number j, $0\le j<n$ , such that we have the isomorphism:

${\displaystyle \prod }_{i\in I}{\mathfrak{A}}_i/\mathcal{D}\simeq {\mathfrak{A}}_j.$

Proof. We define the sets

$I_j=\left\{i\in I|{\mathfrak{A}}_i={\mathfrak{A}}_j\right\},0\le j<n,$

and notice that $I_0,\cdots ,I_{n-1}$ are pairwise disjoint and $I=I_0\cup I_1\cup \cdots \cup I_{n-1}$ . Since the filter $\mathcal{D}$ is maximal and $I\in \mathcal{D}$ , there exists a unique $j\in \left\{0,\cdots ,n-1\right\}$ such that $I_j\in \mathcal{D}$ . Since the congruences $\left({\equiv }_{\mathcal{D}},{~}_{\mathcal{D}}\right)$ are nuclear, we have

${\displaystyle \prod }_{i\in I}{\mathfrak{A}}_i/\mathcal{D}\simeq {\displaystyle \prod }_{i\in I}{\mathfrak{A}}_i/ℰ,$

where $ℰ=\left\{X\cap I_j|X\in \mathcal{D}\right\}$ is an ultrafilter on $I_j$ .

For $a\in Q_j$ we define $f_a\in {\displaystyle \prod }_{i\in I_j}{Q}_i$ with the property $f_a\left(i\right)=a$ for all $i\in I_j$ . For $X\in {\Sigma }_j$ we define $F_X\in \underset{i\in I_j}{{\displaystyle \tilde{\prod }}}{\Sigma }_i$ with the property $F_X\left(i\right)=X$ for all $i\in I_j$ . If $a\ne b$ and $a,b\in Q_j$ , then

$\left\{i\in I_j|f_a\left(i\right)=f_b\left(i\right)\right\}=\varnothing \notin ℰ.$

Hence $f_a{\cancel{\equiv }}_{ℰ}{f}_b$ and the map $\alpha :a\to {\left[f_a\right]}_{ℰ}$ , where ${\left[f_a\right]}_{ℰ}$ is an equivalence class modulo ${\equiv }_{ℰ}$ , will be an injection. In an analogous way we show that the map $\tilde{\alpha }:X\to {\left[F_X\right]}_{ℰ}$ , where ${\left[F_X\right]}_{ℰ}$ is an equivalence class modulo ${~}_{ℰ}$ , is an injection. Moreover, starting from the equality $f_{X\left(a_1,\cdots ,a_n\right)}=F_X\left(f_{a_1},\cdots ,f_{a_n}\right)$ , we verify that, for the pair $\left(\alpha ,\tilde{\alpha }\right):{\mathfrak{A}}_j\Rightarrow {\displaystyle \prod }_{i\in I_j}{\mathfrak{A}}_i/ℰ$ ,

$\begin{array}{c}\alpha X\left(a_1,\cdots ,a_n\right)={\left[f_{X\left(a_1,\cdots ,a_n\right)}\right]}_{ℰ}={\left[F_X\left(f_{a_1},\cdots ,f_{a_n}\right)\right]}_{ℰ}\\ ={\left[F_X\right]}_{ℰ}\left({\left[f_{a_1}\right]}_{ℰ},\cdots ,{\left[f_{a_n}\right]}_{ℰ}\right)=\left[\tilde{\alpha }\left(X\right)\right]\left(\alpha a_1,\cdots ,\alpha a_n\right).\end{array}$

It remains to verify that $\alpha$ and $\tilde{\alpha }$ are surjective.

Let $f\in {\displaystyle \prod }_{i\in I_j}{Q}_i$ and $F\in {\displaystyle \prod }_{i\in I_j}{\Sigma }_i$ . Then, for each $a\in Q_j$ and $A\in {\Sigma }_j$ we define:

$I_{j,a}=\left\{i\in I_j|f\left(i\right)=a\right\},$

and

$I_{j,A}=\left\{i\in I_j|F\left(i\right)=A\right\}.$

Since the $I_{j,a}$ are pairwise disjoint and $\cup \left(I_{j,a}|a\in Q_j\right)=I_j$ , we conclude that there exists exactly one $a\in Q_j$ such that $I_{j,a}\in ℰ$ . Now

$\left\{i\in I_j|f\left(i\right)=f_a\left(i\right)\right\}=I_{j,a}\in ℰ,$

hence, $f{\equiv }_{ℰ}{f}_a$ and $\alpha$ is onto. The similar proof is valid for $\tilde{\alpha }$ . Therefore,

${\displaystyle \prod }_{i\in I_j}\mathfrak{A}/ℰ\simeq \mathfrak{A}.$ □

A set of T-hyperidentities is said to be satisfiable if there exists a non-trivial T-algebra in which every T-hyperidentity of this set is true. The compactness theorem for first-order languages extends to hyperidentities using ultraproducts of T-algebras.

Theorem 4.2 (The Godel-Mal’tsev type compactness theorem for hyperidentities). If every finite part of an infinite set of T-hyperidentities is satisfiable, then the whole set of T-hyperidentities is also satisfiable.

5. The Hypervariety of T-Algebras

Let $\mathfrak{L}$ be a system of T-hyperidentities. Denote by ${\mathfrak{M}}_{\mathfrak{L}}^T$ the class of all T-algebras each of which satisfies all T-hyperidentities from $\mathfrak{L}$ . The class of T-algebras $\mathfrak{N}$ is called a hypervariety of T-algebras if there exists a system of T-hyperidentities $\mathfrak{L}$ such that

$\mathfrak{N}={\mathfrak{M}}_{\mathfrak{L}}^T.$

In this case the class of T-algebras $\mathfrak{N}$ is called the hypervariety of T-algebras defined by the system of T-hyperidentities $\mathfrak{L}$ . Similarly, a variety of Ω-algebras is called a hypervariety of Ω-algebras if it is defined by $T_{\Omega }$ -hyperidentities [40], where $T_{\Omega }=\left\{\left|f\right||f\in \Omega \right\}$ .

A T-hyperidentity ${\omega }_1={\omega }_2$ is called a consequence of $\mathfrak{L}$ if for every T-algebra $\mathfrak{A}$ ,

$\mathfrak{A}\models \mathfrak{L}\Rightarrow \mathfrak{A}\models \left({\omega }_1={\omega }_2\right)$

(the notation $\mathfrak{A}\models \mathfrak{L}$ means satisfiability of all hyperidentities of $\mathfrak{L}$ in the algebra $\mathfrak{A}$ ). The set ${\mathfrak{L}}^{\prime }$ of T-hyperidentities is called a consequence of $\mathfrak{L}$ and denoted by $\mathfrak{L}\Rightarrow {\mathfrak{L}}^{\prime }$ if every hyperidentity of ${\mathfrak{L}}^{\prime }$ is a consequence of $\mathfrak{L}$ .

Every T-hyperidentity is a T’-hyperidentity for every set of positive integers $T^{\prime }\supseteq T$ . It is obvious that if ${\omega }_1={\omega }_2$ is a consequence of $\mathfrak{L}$ in the meaning of T-hyperidentities, then ${\omega }_1={\omega }_2$ is a consequence of $\mathfrak{L}$ in the meaning of T’-hyperidentities, for $T^{\prime }\supseteq T$ .

Let us define the concept of formal consequence of $\mathfrak{L}$ .

(i) Any T-hyperidentity of the form $w=w$ and any hyperidentity from $\mathfrak{L}$ are formal consequences of $\mathfrak{L}$ ;

(ii) If T-hyperidentity $w_1=w_2$ is a formal consequence of $\mathfrak{L}$ , then the hyperidentity $w_2=w_1$ is a formal consequence of $\mathfrak{L}$ as well;

(iii) If T-hyperidentities $w_1=w_2$ and $w_2=w_3$ are formal consequences of $\mathfrak{L}$ , then the hyperidentity is also formal consequence of $\mathfrak{L}$ ;

(iv) If T-hyperidentity $u_i=v_i$ is a formal consequence of $\mathfrak{L}$ for $i=1,\cdots ,n$ , then for any n-ary functional variable Y (where $n\in T$ ) the T-hyperidentity

$Y\left(u_1,\cdots ,u_n\right)=Y\left(v_1,\cdots ,v_n\right)$

is a formal consequence of $\mathfrak{L}$ as well;

(v) If T-hyperidentity $w_1=w_2$ is a formal consequence of $\mathfrak{L}$ , then T-hyperidentity ${w^{\prime }}_1={w^{\prime }}_2$ is also a formal consequence of $\mathfrak{L}$ , where ${w^{\prime }}_1$ and ${w^{\prime }}_2$ are obtained from $w_1$ and $w_2$ , respectively, by replacement of all occurrences of the functional variable X (the object variable x) by any functional variable Z with the same arity (respectively by any T-hyperterm $\omega$ ).

A T-hyperidentity ${\omega }_1={\omega }_2$ is a formal consequence of a system of T-hyperidentities $\mathfrak{L}$ , if it is a formal consequence of $\mathfrak{L}$ according to (i)-(v).

Theorem 5.1 (completeness for hyperidentities). The T-hyperidentity ${\omega }_1={\omega }_2$ is a consequence of the system of T-hyperidentities $\mathfrak{L}$ iff it is a formal consequence of $\mathfrak{L}$ ([39] p. 169, [20] p. 43).

Theorem 5.2. A class of T-algebras is a hypervariety of T-algebras if and only if it is hereditary, homomorphicaly and multiplicatively closed.

6. Varieties of Boolean Algebras and Distributive Lattices

Let us start from the definitions of Boolean algebras.

Definition 6.1. An algebra $\left(Q;\left\{+,\cdot ,\text{'},0,1\right\}\right)$ with two binary, one unary and two nullary operations is called a Boolean algebra if $\left(Q;\left\{+,\cdot ,0,1\right\}\right)$ is a bounded distributive lattice with least element 0 and greatest element 1 and the algebra $\left(Q;\left\{+,\cdot ,\text{'},0,1\right\}\right)$ satisfies the following identities:

$x+x^{\prime }=1,$

$x\cdot x^{\prime }=0.$

For a lattice $\left(L;\left\{+,\cdot \right\}\right)$ its partial order ≤ is defined in the following way:

$x\le y\iff x+y=y,x,y\in L.$

For the definition and existence of free algebras $F_V\left(X\right)$ of the given variety V with the set of free generators X also see [8] [10] [11] [36] [72] [128]-[133]. If V is the variety of Boolean algebras then the free algebra $F_V\left(X\right)$ is called the free Boolean algebra with the set of free generators X. For the variety V of distributive lattices (bounded distributive lattices) the free algebra $F_V\left(X\right)$ is called the free distributive lattice (free bounded distributive lattice) with the set of free generators X. The problem of determining the cardinality of free distributive lattices goes back to R.Dedekind [2] (for a modern survey of the field, see [134]).

Definition 6.2. A Boolean algebra (distributive lattice) $ℱ$ is called a free Boolean algebra (free distributive lattice with the system of free generators $X\subseteq ℱ$ if the algebra $ℱ$ is generated by the subset $X\subseteq ℱ$ and for every Boolean algebra (distributive lattice) $\mathfrak{S}$ and for every mapping $\mu :X\to \mathfrak{S}$ there exists a unique homomorphism: $\nu :ℱ\to \mathfrak{S}$ with ${\nu |}_X=\mu$ .

Let $B=\left\{0,1\right\}$ . Define the operations $+,\cdot ,\text{'}$ on B in the following way: $0+0=0$ , $0+1=1+0=1+1=1$ , $0\cdot 1=0\cdot 0=1\cdot 0=0$ , $1\cdot 1=1$ , $0^{\prime }=1$ , $1^{\prime }=0$ . We get the two-element Boolean algebra $B=\left(B;\left\{+,\cdot ,\text{'},0,1\right\}\right)$ .

The two-element Boolean algebra is the only subdirectly irreducible Boolean algebra up to isomorphism, the two-element lattice is the only subdirectly irreducible distributive lattice up to isomorphism, the two-element semilattice is the only subdirectly irreducible semilattice up to isomorphism [72] [130] [131].

For a set X denote the set of all its subsets by $2^X$ or . If we consider subsets of a given set X then for a subset $s\subseteq X$ we denote $s^{\prime }=X\backslash s$ .

A function $f:B^n\to B$ is called a Boolean function of n variables, where $B^n$ is the set of all n-element sequences of B. The following result is well known.

Theorem 6.1 ([135]). For every Boolean function $f:B^n\to B$ there exists a unique set $S\subseteq 2^{\left\{1,\cdots ,n\right\}}$ such that

$f\left(x_1,\cdots ,x_n\right)={\displaystyle \sum }_{s\in S}\left({\displaystyle \prod }_{i\in s}{x}_i\cdot {\displaystyle \prod }_{i\in \overline{s}}{x^{\prime }}_i\right),$

where the operations on the right hand side are the operations of Boolean algebra $B$ .

Note that those terms are called disjunctive normal forms for Boolean functions.

For $u=\left(u_1,\cdots ,u_n\right),v=\left(v_1,\cdots ,v_n\right)\in B^n$ we define: $u\le v$ iff $u_i\le v_i$ for all $i=\overline{1,n}$ . Here and afterwards $n\ge 1$ is a positive integer.

Definition 6.3. A Boolean function $f:B^n\to B$ is called monotone if

$x\le y\Rightarrow f\left(x\right)\le f\left(y\right),$

where $x,y\in B^n$ .

If $u=\left(u_1,\cdots ,u_n\right),v=\left(v_1,\cdots ,v_n\right)\in B^n$ then we will say $u\underset{\_}{\prec }v$ if there exists k ($1\le k\le n$ ) such that $u_i=v_i$ for all $i\ne k$ and $u_k=0$ ,$v_k=1$ . A Boolean function $f:B^n\to B$ is monotone iff

$x\underset{\_}{\prec }y\Rightarrow f\left(x\right)\le f\left(y\right),$

where $x,y\in B^n$ .

Denote the set of all monotone Boolean functions of n variables by ${ℳ}_n$ .

We can define $f+g$ and $f\cdot g$ for any two Boolean functions of n variables by the standard way. It is obvious that if f and g are monotone Boolean functions, then $f+g$ and $f\cdot g$ are monotone, too. Thus, we get the Boolean algebra of Boolean functions of n variables, and the algebra ${\mathfrak{L}}_n={ℳ}_n\left(+,\cdot \right)$ which obviously is a bounded distributive lattice. Also let $m_n=\left|{ℳ}_n\right|$ be the number of monotone Boolean functions of n variables. (Note that the numbers $m_n$ are called Dedekind’s numbers.) For instance, $m_1=3$ , $m_2=6$ , $m_3=20$ , $m_4=168$ , $m_5=7581$ , $m_6=7828354$ ([134]).

It is commonly known that the free Boolean algebra on n free generators is isomorphic to the Boolean algebra of Boolean functions of n variables ([2] [11] [130] [136]). The free bounded distributive lattice on n free generators is isomorphic to the bounded lattice of monotone Boolean functions of n variables ([2] [11] [130] [136]). Let us present the last result in detailed.

Now let $S\subseteq 2^{\left\{1,\cdots ,n\right\}}$ be an antichain (or Sperner set [2]) with respect to the order $\subseteq$ . It means that S consists of subsets of $\left\{1,\cdots ,n\right\}$ , none of which is contained in any other subset from S. Note that the empty set is also considered an antichain. For an antichain $S\subseteq 2^{\left\{1,\cdots ,n\right\}}$ define the following monotone Boolean function:

$f_S\left(x_1,\cdots ,x_n\right)={\displaystyle \sum }_{s\in S}{\displaystyle \prod }_{i\in s}{x}_i.$ (6.1)

For $S=\varnothing$ we set $f_{\varnothing }=0$ , and for $S=\{\varnothing \}$ we set $f_{\{\varnothing \}}=1$ . Notice that $f_S$ does not depend on the order of the elements in the set S. It is easy to see that if $S_1\ne S_2$ are two antichains, then $f_{S_1}\ne f_{S_2}$ . To see this without loss of generality suppose that there exists $s\in S_1$ such that $s\notin S_2$ . We can also suppose that there does not exist $s^{\prime }\in S_2$ with $s^{\prime }\subseteq s$ . Otherwise, we would take $s^{\prime }$ instead of s (in that case $s^{\prime }\notin S_1$ , because $S_1$ is an antichain). Take the following values of the variables:

$x_i=\{\begin{array}{l}1,\text{if}i\in s,\hfill \\ 0,\text{if}i\notin s.\hfill \end{array}$

For that values of variables we have: $f_{S_1}=1$ and $f_{S_2}=0$ .

The form (6.1) is uniquely determined by the antichain $S\subseteq 2^{\left\{1,\cdots ,n\right\}}$ . And conversely, every monotone Boolean function is obtained in that way.

Proposition 6.1. For every monotone Boolean function f of n variables, there exists a unique antichain $S\subseteq 2^{\left\{1,\cdots ,n\right\}}$ such that $f=f_S$ .

Proof. For $a=\left(a_1,\cdots ,a_n\right)\in B^n$ let $s_a=\left\{i:a_i=1\right\}$ . Consider the set $A=\left\{s_a:a\in B^n,f\left(a\right)=1\right\}$ . Let S be the subset of A, consisting exactly of all minimal sets in A. Then $S\subseteq 2^{\left\{1,\cdots ,n\right\}}$ is an antichain. Notice that $f\left(a_1,\cdots ,a_n\right)=1$ iff for some $s\in S$ we have $a_i=1$ for all $i\in s$ . The same is valid for $f_S$ . Therefore, $f\left(a_1,\cdots ,a_n\right)=f_S\left(a_1,\cdots ,a_n\right)$ for all $\left(a_1,\cdots ,a_n\right)\in B^n$ , and so $f=f_S$ . The uniqueness follows from the argument stated above. □

Define the Boolean functions:

${\delta }_n^i=x_i,i=\overline{1,n}.$

Theorem 6.2 (Functional representation theorem for free bounded distributive lattices (R.Dedekind [2])). The algebra ${\mathfrak{L}}_n$ is a free bounded distributive lattice with the system of free generators: $\Delta =\left\{{\delta }_n^1,\cdots ,{\delta }_n^n\right\}$ . Hence, every n-generated free bounded distributive lattice is isomorphic to the distributive lattice ${\mathfrak{L}}_n$ .

Proof. Let $\mathfrak{L}$ be any bounded distributive lattice and $\phi :\text{Δ}\to \mathfrak{L}$ be a mapping. We show that there exists a unique homomorphism $\psi :{\mathfrak{L}}_n\to \mathfrak{L}$ such that ${\psi |}_{\text{Δ}}=\phi$ . For any $f\in {\mathfrak{L}}_n$ there exists a unique antichain S such that

$f\left(x_1,\cdots ,x_n\right)=f_S\left(x_1,\cdots ,x_n\right)={\displaystyle \sum }_{s\in S}{\displaystyle \prod }_{i\in s}{x}_i.$

Take

$\psi \left(f\right)={\displaystyle \sum }_{s\in S}{\displaystyle \prod }_{i\in s}\phi \left({\delta }_i\right).$

Obviously $\phi \left(f\right)=\psi \left(f\right)$ for $f\in \text{Δ}$ and $\psi$ is a homomorphism. The uniqueness of $\psi$ is also obvious. □

Corollary 6.1. Every finitely generated free bounded distributive lattice is finite.

Corollary 6.2. Every finitely generated bounded distributive lattice is finite, i.e. the variety of bounded distributive lattices is a Burnside variety.

Theorem 6.3. (Functional representation theorem for free Boolean algebras (R.Dedekind [2])) The algebra ${\mathfrak{B}}_n$ of Boolean function of n variables is a free Boolean algebra with the system of free generators: $\Delta =\left\{{\delta }_n^1,\cdots ,{\delta }_n^n\right\}$ . Hence, every n-generated free Boolean algebra is isomorphic to the Boolean algebra ${\mathfrak{B}}_n$ .

Corollary 6.3. Every finitely generated free Boolean algebra is finite.

Corollary 6.4. Every finitely generated Boolean algebra is finite, i.e. the variety of Boolean algebras is a Burnside variety.

7. Bool-De Morgan Algebras

Definition 7.1. An algebra $\left(Q;\left\{+,\cdot {,}^{-},0,1\right\}\right)$ with two binary, one unary and two nullary operations is called a De Morgan algebra if $\left(Q;\left\{+,\cdot ,0,1\right\}\right)$ is a bounded distributive lattice with least element 0 and greatest element 1 and the algebra $\left(Q;\left\{+,\cdot {,}^{-}\right\}\right)$ satisfies the following identities:

$\overline{x+y}=\overline{x}\cdot \overline{y},$

$\overline{\overline{x}}=x,$

where $\overline{\overline{x}}=\overline{\left(\overline{x}\right)}$ ([136]-[148]).

Definition 7.2. An algebra $\left(Q;\left\{+,\cdot ,\text{'},0,1\right\}\right)$ with two binary, two unary and two nullary operations is called a Boole-De Morgan algebra if $\left(Q;\left\{+,\cdot {,}^{-},0,1\right\}\right)$ is a De Morgan algebra and $\left(Q;\left\{+,\cdot ,\text{'},0,1\right\}\right)$ is a Boolean algebra and the two unary operations commute, i.e., ${\left(\overline{x}\right)}^{\prime }=\overline{\left(x^{\prime }\right)}$ . So, Boole-De Morgan algebras form a variety.

This concept is introduced in [149] [150] under the name of Boolean bisemigroup. It is easy to note that the last condition ${\left(\overline{x}\right)}^{\prime }=\overline{\left(x^{\prime }\right)}$ of the definition follows from the other conditions:

$\overline{\left(x^{\prime }\right)}+\overline{x}=\overline{x^{\prime }\cdot x}=1,\overline{\left(x^{\prime }\right)}\cdot \overline{x}=\overline{x^{\prime }+x}=0,$

and

$\overline{\left(x^{\prime }\right)}={\left(\overline{x}\right)}^{\prime }$

in the Boolean algebra $\left(Q;\left\{+,\cdot ,\text{'},0,1\right\}\right)$ .

Let us consider some natural examples of Boole-De Morgan algebras. First note that every Boolean algebra can be considered as a Boole-De Morgan algebra with two equal unary operations. In particular if $B=\left(B;\left\{+,\cdot ,\text{'},0,1\right\}\right)$ is the two-element Boolean algebra and $\overline{x}=x^{\prime }$ (i.e., the unary operations ${}^{-}$ and $\text{'}$ are equal) then the algebra $\left(B;\left\{+,\cdot {,}^{-},\text{'},0,1\right\}\right)$ is a Boole-De Morgan algebra and we will denote it by $B{M}_2$ .

Now we define a Boole-De Morgan algebra on the four-element set $D=\left\{0,a,b,1\right\}$ which will be used in the proof of the main theorem of the next Section. Defining $0+x=x+0=x$ , $0\cdot x=x\cdot 0=0$ and $1\cdot x=x\cdot 1=x$ , $1+x=x+1=1$ and $x+x=x$ ,$x\cdot x=x$ for all $x\in D$ , and $a+b=b+a=1$ , $a\cdot b=b\cdot a=0$ , $\overline{0}=1$ , $\overline{1}=0$ , $\overline{a}=a$ , $\overline{b}=b$ , $1^{\prime }=0$ , $0^{\prime }=1$ , $a^{\prime }=b$ , $b^{\prime }=a$ we get the Boole-De Morgan algebra $B{M}_4=\left(D;\left\{+,\cdot {,}^{-},\text{'},0,1\right\}\right)$ .

For a Boolean algebra $\mathfrak{B}=\left(Q;\left\{+,\cdot ,\text{'},0,1\right\}\right)$ consider the direct product $\mathfrak{B}\times \mathfrak{B}$ . Defining one more unary operation ${}^{-}$ on the set $Q\times Q$ by $\overline{\left(x,y\right)}=\left(y^{\prime },x^{\prime }\right)$ we get the Boole-De Morgan algebra $\left(Q\times Q;\left\{+,\cdot ,\text{'}{,}^{-},\left(0,0\right),\left(1,1\right)\right\}\right)$ .

The set $\mathcal{T}\left(\mathfrak{A}\right)$ of binary term operations of the nontrivial lattice $\mathfrak{A}$ is a Boole-De Morgan algebra (of order 4) where the operations are defined below. For any two binary terms $f\left(x,y\right)$ and $g\left(x,y\right)$ the binary operations are defined as the following binary superpositions:

$\left(f+g\right)\left(x,y\right)=f\left(x,g\left(x,y\right)\right),\left(f\cdot g\right)\left(x,y\right)=f\left(g\left(x,y\right),y\right).$

The nullary operations are the terms y and x. The unary operations are the commutation and dualization. The commutation is defined by $\overline{f}\left(x,y\right)=f\left(y,x\right)$ and for a binary term $f\left(x,y\right)$ to get its dual term $f^{\prime }\left(x,y\right)$ we shall change all variables x by y and vice versa, and also change all operations + by ∙ and vice versa. So we obtain the Boole-De Morgan algebra $\mathcal{T}\left(\mathfrak{A}\right)$ : $\overline{x+y}=x+y$ , $\overline{x\cdot y}=x\cdot y$ , $\overline{x}=y$ , $\overline{y}=x$ , ${\left(x+y\right)}^{\prime }=x\cdot y$ , ${\left(x\cdot y\right)}^{\prime }=x+y$ , $x^{\prime }=y$ , $y^{\prime }=x$ . Note, that every lattice identity of the Boole-De Morgan algebra $\mathcal{T}\left(\mathfrak{A}\right)$ is equivalent to certain hyperidentity. For applications of mentioned binary superpositions see [18] [20] [27] [115] [119] [151]-[158].

Let $\mathfrak{B}=\left(Q;\left\{+,\cdot ,\text{'},0,1\right\}\right)$ be a Boolean algebra. Denote its dual Boolean algebra by ${\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}$ , i.e., ${\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}=\left(Q;\left\{\cdot ,+,\text{'},1,0\right\}\right)$ . Consider the direct product $\mathfrak{B}\times {\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}=\left(Q\times Q;\left\{\vee ,\wedge ,\text{'},\left(0,1\right),\left(1,0\right)\right\}\right)$ where $\left(x_1,y_1\right)\vee \left(x_2,y_2\right)=\left(x_1+x_2,y_1\cdot y_2\right)$ , $\left(x_1,y_1\right)\wedge \left(x_2,y_2\right)=\left(x_1\cdot x_2,y_1+y_2\right)$ , ${\left(x_1,y_1\right)}^{\prime }=\left({x^{\prime }}_1,{y^{\prime }}_1\right)$ for any $x_1,x_2,y_1,y_2\in Q$ . Defining one more unary operation ${}^{-}$ on the set $Q\times Q$ by $\overline{\left(x,y\right)}=\left(y,x\right)$ we get the Boole-De Morgan algebra $\mathfrak{B}\times {\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}$ . Every Boole-De Morgan algebra $\mathfrak{B}$ is an embedding into $\mathfrak{B}\times {\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}$ . We define an embedding of the Boole-De Morgan algebra $\mathfrak{B}$ into Boole-De Morgan algebra $\mathfrak{B}\times {\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}$ by the following rule:

$x\to \left(x,\overline{x}\right).$

Now we formulate a Stone-type representation theorem for Boole-De Morgan algebras.

Let $2^I$ be the Boolean algebra of all subsets of the set I.

Theorem 7.1 ([149] [150]). Every Boole-De Morgan algebra $\mathfrak{A}$ is isomorphic to a subalgebra of the Boole-De Morgan algebra $\mathfrak{B}\times {\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}$ for some Boolean algebra $\mathfrak{B}=2^I$ .

For a Boole-De Morgan algebra $\left(Q;\left\{+,\cdot {,}^{-},\text{'},0,1\right\}\right)$ we define one more unary operation ${}^{\text{*}}$ by the following way: $x^{\text{*}}={\left(\overline{x}\right)}^{\prime }=\overline{\left(x^{\prime }\right)}$. It is easy to see that ${\left(x+y\right)}^{\text{*}}=x^{\text{*}}+y^{\text{*}}$ , ${\left(x\cdot y\right)}^{\text{*}}=x^{\text{*}}\cdot y^{\text{*}}$ , $\overline{x^{\text{*}}}={\left(\overline{x}\right)}^{\text{*}}$, ${\left(x^{\text{*}}\right)}^{\prime }={\left(x^{\prime }\right)}^{\text{*}}$ . Thus the mapping $x\to x^{\text{*}}$ is an automorphism of the Boole-De Morgan algebra $\left(Q;\left\{+,\cdot {,}^{-},\text{'},0,1\right\}\right)$ . Also it is easy to see that $x^{\text{*}}=x$ if and only if $x^{\prime }=\overline{x}$ .

8. Quasi-De Morgan Functions

Recall that $D=\left\{0,a,b,1\right\}$ and $B=\left\{0,1\right\}$ . Let us construct a one-to-one correspondence between the sets D and $B\times B$ as follows:

$0\leftrightarrow \left(0,0\right),a\leftrightarrow \left(1,0\right),b\leftrightarrow \left(0,1\right),1\leftrightarrow \left(1,1\right).$

We define the operations $+,\cdot {,}^{-},\text{'}$ on the set $B\times B$ as follows:

$\overline{\left(u,v\right)}=\left(v^{\prime },u^{\prime }\right),{\left(u,v\right)}^{\prime }=\left(u^{\prime },v^{\prime }\right),$

$\left(u_1,v_1\right)+\left(u_2,v_2\right)=\left(u_1+u_2,v_1+v_2\right),\left(u_1,v_1\right)\cdot \left(u_2,v_2\right)=\left(u_1\cdot u_2,v_1\cdot v_2\right)$

(here the operations on the right hand side are the operations of the Boole-De Morgan algebra $B{M}_2$ ). We get the Boole-De Morgan algebra $\left(B\times B;\left\{+,\cdot {,}^{-},\text{'},0,1\right\}\right)=B\times B$ , which is isomorphic to the algebra $B{M}_4$ (the one-to-one correspondence described above is an isomorphism). However, if the ordered pair $\left(y,z\right)\in B\times B$ corresponds to $x\in D$ then we will write $x=\left(y,z\right)$ (this causes no confusion).

For $x\in D$ let

$x^{\text{*}}=\{\begin{array}{l}x,\text{if}x=0,1,\hfill \\ a,\text{if}x=b,\hfill \\ b,\text{if}x=a.\hfill \end{array}$

The unary operation ${}^{\text{*}}$ can also be defined on $B\times B$ taking into account the isomorphism described above. In result we get ${\left(u,v\right)}^{\text{*}}=\left(v,u\right)=\left(v^{\text{*}},u^{\text{*}}\right)$ , $u,v\in B$ . It is clear that $x^{\text{*}}={\left(\overline{x}\right)}^{\prime }=\overline{x^{\prime }}$ (which agrees with the notation from the previous section).

Now we can introduce the following two concepts of quasi-De Morgan and De Morgan functions.

Definition 8.1. A function $f:D^n\to D$ is called a quasi-De Morgan function if the following conditions hold:

(1) if $x_i\in \left\{0,1\right\},i=1,\cdots ,n$ , then $f\left(x_1,\cdots ,x_n\right)\in \left\{0,1\right\}$ ,

(2) if $x_i\in D,i=1,\cdots ,n$ , then $f\left(x_1^{\text{*}},\cdots ,x_n^{\text{*}}\right)={\left(f\left(x_1,\cdots ,x_n\right)\right)}^{\text{*}}$ ,

In terms of clone theory, Condition (1) means that the function f preserves the unary relation $\left\{0,1\right\}\subseteq D$ , and Condition (2) means that f preserves the binary relation $\left\{\left(0,0\right),\left(a,b\right),\left(b,a\right),\left(1,1\right)\right\}\subseteq D^2$ , which is the graph of the automorphism $x\mapsto x^{\text{*}}$ .

For $c=\left(c_1,\cdots ,c_n\right),d=\left(d_1,\cdots ,d_n\right)\in D^n$ we say that d is a permitted modification of c if for some $k\left(1\le k\le n\right)$ we have $d_i=c_i$ for all $1\le i\le n$ , $i\ne k$ , and

$d_k=\{\begin{array}{l}a,\text{if}{c}_k=0,\hfill \\ 1,\text{if}{c}_k=b.\hfill \end{array}$

Definition 8.2. A quasi-De Morgan function $f:D^n\to D$ is called a De Morgan function if it satisfies the following condition:

(3) if $x,y\in D^n$ with $f\left(x\right)\ne b$ and y is a permitted modification of x then $f\left(y\right)\in \left\{f\left(x\right),a\right\}$ .

In terms of clone theory the Condition (3) means that f preserves the order relation $\rho =\left\{\left(b,b\right),\left(b,0\right),\left(b,1\right),\left(b,a\right),\left(0,0\right),\left(0,a\right),\left(1,1\right),\left(1,a\right),\left(a,a\right)\right\}\subseteq D^2$ .

Notice that Condition (1) is a consequence of Condition (2), however it is more convenient to write it as a separate condition.

Note that it follows from Condition (1) that every quasi-De Morgan function is an extension of some Boolean function. Notice that the constant functions $f=1$ and $f=0$ are quasi-De Morgan functions, but the constant functions $f=a$ and $f=b$ are not. This means that 0 and 1 are the only constant quasi-De Morgan functions. Further examples of quasi-De Morgan functions are $f\left(x\right)=x$ , $g\left(x\right)=\overline{x}$ , $h\left(x,y\right)=x\cdot y$ , $q\left(x,y\right)=x+y$ , $p\left(x\right)=x^{\prime }$ , where the operations on the right hand side are the operations of the Boole-De Morgan algebra $B{M}_4$ . Also note that the function p is an example of quasi-De Morgan function which is not a De Morgan function.

Below, for $x_i\in D$ we denote by $\left(y_i,z_i\right)$ the pair from $B\times B$ which corresponds to $x_i$ , i.e., $x_i=\left(y_i,z_i\right)$ .

Theorem 8.1. A function $f:D^n\to D$ is a quasi-De Morgan function if and only if there exists a Boolean function $\phi :B^{2n}\to B$ such that

$f\left(x_1,\cdots ,x_n\right)=\left(\phi \left(y_1,\cdots ,y_n,{z^{\prime }}_1,\cdots ,{z^{\prime }}_n\right),\phi \left(z_1,\cdots ,z_n,{y^{\prime }}_1,\cdots ,{y^{\prime }}_n\right)\right),$ (8.1)

for all $x_1,\cdots ,x_n\in D$ .

For a quasi-De Morgan function $f:D^n\to D$ there exists a unique Boolean function $\phi :B^{2n}\to B$ which satisfies (8.1). To emphasize that $\phi$ is the unique Boolean function corresponding to f, we denote it by ${\phi }_f$ .

Corollary 8.1. There are exactly $2^{4^n}$ quasi-De Morgan functions of n variables.

Denote the set of all quasi-De Morgan functions of n variables by $ℬ{ℳ}_n$ . For the functions $f,g:D^n\to D$ define $f+g$ , $f\cdot g$ , $\overline{f}$ and $f^{\prime }$ by the standard way, i.e., $\left(f+g\right)\left(x\right)=f\left(x\right)+g\left(x\right)$ , $\left(f\cdot g\right)\left(x\right)=f\left(x\right)\cdot g\left(x\right)$ , $\overline{f}\left(x\right)=\overline{f\left(x\right)}$ , $f^{\prime }\left(x\right)={\left(f\left(x\right)\right)}^{\prime }$ , $x\in D^n$ , where the operations on the right hand side are the operations of the Boole-De Morgan algebra $B{M}_4$ .

Theorem 8.2. The set $ℬ{ℳ}_n$ is closed under operations $+,\cdot {,}^{-},\text{'}$ , i.e., if $f,g\in ℬ{ℳ}_n$ , then $f+g,f\cdot g,\overline{f},f^{\prime }\in ℬ{ℳ}_n$ .

Thus, we get an algebra: $\mathfrak{B}{\mathfrak{M}}_n=\left(ℬ{ℳ}_n,\left\{+,\cdot {,}^{-},\text{'},0,1\right\}\right)$ (here 0 and 1 are the constant quasi-De Morgan functions), which obviously is a Boole-De Morgan algebra.

For a set $S\subseteq 2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ define the function $f_S:D^n\to D$ by the following way:

$f_S\left(x_1,\cdots ,x_n\right)={\displaystyle \sum }_{\left(s_1,s_2\right)\in S}\left({\displaystyle \prod }_{i\in s_1}{x}_i\cdot {\displaystyle \prod }_{i\in {\overline{s}}_1}{x^{\prime }}_i\cdot {\displaystyle \prod }_{i\in s_2}{\overline{x}}_i\cdot {\displaystyle \prod }_{i\in {\overline{s}}_2}{x}_i^{\text{*}}\right),$(8.2)

where the operations on the right hand side are the operations of $B{M}_4$ (cf. [120] [121]).

Notice that $f_S$ does not depend on the order of the elements in the set S.

Also we set $f_{\varnothing }=0$ and $f_{\left\{\left(\varnothing ,\varnothing \right)\right\}}=1$ .

Let us consider the projection functions

${\delta }_n^i\left(x_1,\cdots ,x_n\right)=x_i,i=1,\cdots ,n,$

as functions $D^n\to D$ . Obviously, ${\delta }_n^i$ is a quasi-De Morgan function for each i. According to (8.2), for any set $S\subseteq 2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ we have:

$f_S={\displaystyle \sum }_{\left(s_1,s_2\right)\in S}\left({\displaystyle \prod }_{i\in s_1}{\delta }_n^i\cdot {\displaystyle \prod }_{i\in {\overline{s}}_1}{\left({\delta }_n^i\right)}^{\prime }\cdot {\displaystyle \prod }_{i\in s_2}\overline{{\delta }_n^i}\cdot {\displaystyle \prod }_{i\in {\overline{s}}_2}{\left({\delta }_n^i\right)}^{\text{*}}\right).$

Hence, $f_S\in ℬ{ℳ}_n$ , i.e., $f_S$ is a quasi-De Morgan function for any set $S\subseteq 2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ .

For $s=\left(s_1,s_2\right)\in 2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ let $s^{\prime }=s_1\cup \left\{n+i:i\in s_2\right\}\in 2^{\left\{1,\cdots ,2n\right\}}$ , and for $S\subseteq 2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ let $S^{\prime }=\left\{s^{\prime }:s\in S\right\}\subseteq 2^{\left\{1,\cdots ,2n\right\}}$ . In this way we give a one-to-one correspondence between the sets and .

Now, for any quasi-De Morgan function $f\in ℬ{ℳ}_n$ from Theorem 1 we conclude that there exists a set $S^{\prime }\subseteq 2^{\left\{1,\cdots ,2n\right\}}$ such that:

$\begin{array}{l}f\left(x_1,\cdots ,x_n\right)=\left({\phi }_f\left(y_1,\cdots ,y_n,{z^{\prime }}_1,\cdots ,{z^{\prime }}_n\right),{\phi }_f\left(z_1,\cdots ,z_n,{y^{\prime }}_1,\cdots ,{y^{\prime }}_n\right)\right)\\ =({\displaystyle \sum }_{s^{\prime }\in S^{\prime }}\left({\displaystyle \prod }_{\begin{array}{c}i\in s^{\prime }\\ 1\le i\le n\end{array}}{y}_i\cdot {\displaystyle \prod }_{\begin{array}{c}i\in \overline{s^{\prime }}\\ 1\le i\le n\end{array}}{y^{\prime }}_i\cdot {\displaystyle \prod }_{\begin{array}{c}i\in s^{\prime }\\ n+1\le i\le 2n\end{array}}{z^{\prime }}_{i-n}\cdot {\displaystyle \prod }_{\begin{array}{c}i\in \overline{s^{\prime }}\\ n+1\le i\le 2n\end{array}}{z}_{i-n}\right),\\ {\displaystyle \sum }_{s^{\prime }\in S^{\prime }}\left({\displaystyle \prod }_{\begin{array}{c}i\in s^{\prime }\\ 1\le i\le n\end{array}}{z}_i\cdot {\displaystyle \prod }_{\begin{array}{c}i\in \overline{s^{\prime }}\\ 1\le i\le n\end{array}}{z^{\prime }}_i\cdot {\displaystyle \prod }_{\begin{array}{c}i\in s^{\prime }\\ n+1\le i\le 2n\end{array}}{y^{\prime }}_{i-n}\cdot {\displaystyle \prod }_{\begin{array}{c}i\in \overline{s^{\prime }}\\ n+1\le i\le 2n\end{array}}{y}_{i-n}\right))\\ ={\displaystyle \sum }_{s^{\prime }\in S^{\prime }}\left({\displaystyle \prod }_{\begin{array}{c}i\in s^{\prime }\\ 1\le i\le n\end{array}}\left(y_i,z_i\right)\cdot {\displaystyle \prod }_{\begin{array}{c}i\in \overline{s^{\prime }}\\ 1\le i\le n\end{array}}{\left(y_i,z_i\right)}^{\prime }\cdot {\displaystyle \prod }_{\begin{array}{c}i\in s^{\prime }\\ n+1\le i\le 2n\end{array}}\overline{\left(y_{i-n},z_{i-n}\right)}\cdot {\displaystyle \prod }_{\begin{array}{c}i\in \overline{s^{\prime }}\\ n+1\le i\le 2n\end{array}}{\left(y_{i-n},z_{i-n}\right)}^{\text{*}}\right)\\ ={\displaystyle \sum }_{\left(s_1,s_2\right)\in S}\left({\displaystyle \prod }_{i\in s_1}{x}_i\cdot {\displaystyle \prod }_{i\in {\overline{s}}_1}{x}_i\cdot {\displaystyle \prod }_{i\in s_2}{\overline{x}}_i\cdot {\displaystyle \prod }_{i\in {\overline{s}}_2}{x}_i^{\text{*}}\right)=f_S\left(x_1,\cdots ,x_n\right),\end{array}$

where S is the subset of $2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ corresponding to $S^{\prime }$ .

Moreover, the number of all quasi-De Morgan functions of n variables is the same as the number of all subsets of $2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ . Hence, we get the following result.

Theorem 8.3. For any quasi-De Morgan function f of n variables there exists a unique set $S\subseteq 2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ such that $f=f_S$ .

In particular, $f_{S_1}\ne f_{S_2}$ if $S_1\ne S_2$ .

Thus every quasi-De Morgan function can be uniquely presented in the form (8.2). This form is called the disjunctive normal form (or briefly—DNF) of quasi-De Morgan function f. Notice that from Theorems 1 and 3 we get an algorithm which, given a quasi-De Morgan function, gives its disjunctive normal form. We can also prove that every quasi-De Morgan function can be uniquely presented in conjunctive normal form (CNF), i.e., in the following form:

${\displaystyle \prod }_{\left(s_1,s_2\right)\in S}\left({\displaystyle \sum }_{i\in s_1}{x}_i+{\displaystyle \sum }_{i\in {\overline{s}}_1}{x^{\prime }}_i+{\displaystyle \sum }_{i\in s_2}{\overline{x}}_i+{\displaystyle \sum }_{i\in {\overline{s}}_2}{x}_i^{\text{*}}\right).$

Below we will use the concept of essential variable (and essential dependence) of quasi-De Morgan functions. The definitions are the same as in case of Boolean functions and so we do not give them here.

Using arguments similar to those given above we can prove the following theorem.

Theorem 8.4. For a quasi-De Morgan function f the corresponding Boolean function ${\phi }_f$ does not essentially depend on the last n variables if and only if f can be represented as a term function with functional symbols $+,\cdot ,\text{'}$ , i.e., f is a term function of the Boolean algebra $\left(D;\left\{+,\cdot ,\text{'},0,1\right\}\right)$ .

Theorem 8.5. (Functional representation theorem for free Boole-De Morgan algebras). The algebra $\mathfrak{B}{\mathfrak{M}}_n$ is a free Boole-De Morgan algebra with the system of free generators $\Delta =\left\{{\delta }_n^1,\cdots ,{\delta }_n^n\right\}$ . Hence every free n-generated Boole-De Morgan algebra is isomorphic to the Boole-De Morgan algebra $\mathfrak{B}{\mathfrak{M}}_n$ .

Corollary 8.2. Every finitely generated free Boole-De Morgan algebra is finite.

Corollary 8.3. Every finitely generated Boole-De Morgan algebra is finite, i.e. the variety of Bool-De Morgan algebras is a Burnside variety.

Problem 8.1. Prove the Post style functional completeness theorem for quasi-De Morgan functions (see [63] [159]-[161]).

Now let us formulate the following characterization of quasi-De Morgan functions.

Theorem 8.6. Quasi-De Morgan functions are precisely the term functions of the Boole-De Morgan algebra $B{M}_4$ , i.e., the set of all quasi-De Morgan functions is the clone of term functions of the Boole-De Morgan algebra $B{M}_4$ .

9. De Morgan Algebras

Apart from mathematical logic ([65] [144] [162]-[169]) and algebra, De Morgan algebras (and De Morgan bisemilattices) have applications in multi-valued simulations of digital circuits too ([139] [140]).

For example, the standard fuzzy algebra $F=\left(\left[0,1\right];\max \left(x,y\right),\min \left(x,y\right),1-x,0,1\right)$ is a De Morgan algebra.

Note that in any De Morgan algebra $\left(Q;\left\{+,\cdot {,}^{-},0,1\right\}\right)$ : $\overline{0}=1$ , $\overline{1}=0$ and:

$x\le y\iff \overline{y}\le \overline{x},x,y\in Q.$

A characterization of De Morgan algebras can be found in [138] [140].

Let $\mathfrak{B}=\left(Q;\left\{+,\cdot ,0,1\right\}\right)$ be a bounded distributive lattice. Denote its dual bounded distributive lattice by ${\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}$ , i.e., ${\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}=\left(Q;\left\{\cdot ,+,1,0\right\}\right)$ . Consider the direct product $\mathfrak{B}\times {\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}=\left(Q\times Q;\left\{\vee ,\wedge ,\left(0,1\right),\left(1,0\right)\right\}\right)$ where $\left(x_1,y_1\right)\vee \left(x_2,y_2\right)=\left(x_1+x_2,y_1\cdot y_2\right)$ , $\left(x_1,y_1\right)\wedge \left(x_2,y_2\right)=\left(x_1\cdot x_2,y_1+y_2\right)$ , for any $x_1,x_2,y_1,y_2\in Q$ . Defining one more operation ${}^{-}$ on the set $Q\times Q$ by $\overline{\left(x,y\right)}=\left(y,x\right)$ , we convert the bounded distributive lattice $\mathfrak{B}\times {\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}$ into the De Morgan algebra $\mathfrak{B}\times {\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}$ . Every De Morgan algebra $\mathfrak{B}$ is an embedding into $\mathfrak{B}\times {\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}$ . We define an embedding of the De Morgan algebra $\mathfrak{B}$ into De Morgan algebra $\mathfrak{B}\times {\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}$ by the following rule:

$x\to \left(x,\overline{x}\right).$

Now we formulate a Stone-type representation theorem for De Morgan algebras.

Let $2^I$ be the bounded distributive lattice of all subsets of set I.

Theorem 9.1. ([149] [150]). Every De Morgan algebra $\mathfrak{A}$ is isomorphic to a subalgebra of the De Morgan algebra $\mathfrak{B}\times {\mathfrak{B}}^{\mathfrak{o}\mathfrak{p}}$ for some bounded distributive lattice $\mathfrak{B}=2^I$ .

Let us consider the following De Morgan algebras: $2=\left(\left\{0,1\right\};\left\{+,\cdot {,}^{-},0,1\right\}\right)$ , $3=\left(\left\{0,a,1\right\};\left\{+,\cdot {,}^{-},0,1\right\}\right)$ , where $\overline{a}=a$ , and $4=\left(\left\{0,a,b,1\right\};\left\{+,\cdot ,,0,1\right\}\right)$ , where $\overline{a}=a$ , $\overline{b}=b$ , $a+b=1$ , $a\cdot b=0$ .

Let us remind the following result.

Theorem 9.2. ([143]). Every non-trivial subdirectly irreducible De Morgan algebra is isomorphic to one of the following algebras: 2, 3, 4, where 2 is the unique non-trivial subdirectly irreducible Boolean algebra.

10. Free De Morgan Algebras and De Morgan Functions

If V is the variety of De Morgan algebras then the free algebra $F_V\left(X\right)$ is called free De Morgan algebra with the set of free generators X. Thus, De Morgan algebra $ℱ=F\left(\left\{+,\cdot {,}^{-},0,1\right\}\right)$ is called a free De Morgan algebra with the system of free generators $X\subseteq F$ if the algebra $ℱ$ is generated by the subset $X\subseteq F$ and for every De Morgan algebra $\mathfrak{S}=S\left(\left\{+,\cdot {,}^{-},0,1\right\}\right)$ and for every mapping $\mu :X\to S$ there exists a unique homomorphism: $\nu :ℱ\to \mathfrak{S}$ with ${\nu |}_X=\mu$ .

Denote $D=B\times B=\left\{\left(0,0\right),\left(1,0\right),\left(0,1\right),\left(1,1\right)\right\}=\left\{0,a,b,1\right\}$ , where $0=\left(0,0\right)$ , $a=\left(1,0\right)$ , $b=\left(0,1\right)$ , $1=\left(1,1\right)$ . Defining $0+x=x$ , $1\cdot x=x$ , $x\in D$ , $a+b=1$ , $ab=0$ , $\overline{0}=1$ , $\overline{1}=0$ , $\overline{a}=a$ , $\overline{b}=b$ we get the De Morgan algebra $4=D\left(+,\cdot {,}^{-},0,1\right)$ . Notice that $\overline{\left(u,v\right)}=\left(\overline{v},\overline{u}\right)$ , $\left(u_1,v_1\right)+\left(u_2,v_2\right)=\left(u_1+u_2,v_1+v_2\right)$ and $\left(u_1,v_1\right)\cdot \left(u_2,v_2\right)=\left(u_1\cdot u_2,v_1\cdot v_2\right)$ (here the operations on the right hand side are the operations of the De Morgan algebra 2). For $x\in D$ let

$x^{\text{*}}=\{\begin{array}{l}x,\text{if}x=0,1,\hfill \\ a,\text{if}x=b,\hfill \\ b,\text{if}x=a.\hfill \end{array}$

Also for $c=\left(c_1,\cdots ,c_n\right),d=\left(d_1,\cdots ,d_n\right)\in D^n$ we say that d is a permitted modification of c if for some $k\left(1\le k\le n\right)$ we have $d_i=c_i$ for all $1\le i\le n$ , $i\ne k$ and

$d_k=\{\begin{array}{l}a,\text{if}{c}_k=0,\hfill \\ 1,\text{if}{c}_k=b.\hfill \end{array}$

Definition 10.1. A function $f:D^n\to D$ is called a De Morgan function of n variables if the following conditions hold:

(1) if $x_i\in \left\{0,1\right\},i=\overline{1,n}$, then $f\left(x_1,\cdots ,x_n\right)\in \left\{0,1\right\}$ ,

(2) if $x_i\in D,i=\overline{1,n}$ then $f\left(x_1^{\text{*}},\cdots ,x_n^{\text{*}}\right)={\left(f\left(x_1,\cdots ,x_n\right)\right)}^{\text{*}}$ ,

(3) if $x\in D^n$ with $f\left(x\right)\ne b$ and y is a permitted modification of x then $f\left(y\right)\in \left\{f\left(x\right),a\right\}$ .

Note that it follows from the first condition that every De Morgan function is an extension of some Boolean function. And notice that the constant functions $f=1$ and $f=0$ are De Morgan functions, but the constant functions $f=a$ and $f=b$ are not. This means that 0 and 1 are only constant De Morgan functions. Other examples of De Morgan functions are $f\left(x\right)=x$ , $g\left(x\right)=\overline{x}$ , $h\left(x,y\right)=x\cdot y$ , $q\left(x,y\right)=x+y$ , where the operations on the right hand side are the operations of the De Morgan algebra 4.

As Boolean functions, De Morgan functions can be given by tables. Also note that there exists an algorithm which for a given table of a function $f:D^n\to D$ determines whether f is a De Morgan function.

Below, for $x_i\in D$ by $\left(y_i,z_i\right)$ we mean the couple from $B\times B$ which is equal to $x_i$ . But often we will consider $B=\left\{0,1\right\}$ as a subset of D (when it can cause no confusion).

The equivalency of the following two definitions follows from the Theorem 1.

For any quasi-De Morgan function $f:D^n\to D$ there exists a unique Boolean function $\phi :B^{2n}\to B$ which satisfies (8.1) and denoted by ${\phi }_f$ (see previous Chapter).

Theorem 10.1. The function $f:D^n\to D$ is a De Morgan function iff it is a quasi-De Morgan function and ${\phi }_f$ is a monotone Boolean function.

Corollary 10.1. There are $m_{2n}$ De Morgan functions of n variables, where $m_k$ is the number of monotone Boolean functions of k variables.

Denote the set of all of n-variable De Morgan functions by ${\mathcal{D}}_n$ . For the functions $f,g:D^n\to D$ define $f+g$ , $f\cdot g$ and $\overline{f}$ by the standard way, i.e. $\left(f+g\right)\left(x\right)=f\left(x\right)+g\left(x\right)$ , $\left(f\cdot g\right)\left(x\right)=f\left(x\right)\cdot g\left(x\right)$ , $\overline{f}\left(x\right)=\overline{f\left(x\right)}$ , $x\in D^n$ , where the operations on the right hand side are the operations of De Morgan algebra 4. Notice that ${\mathcal{D}}_n$ is closed under those operations, i.e. if $f,g\in {\mathcal{D}}_n$ , then $f+g,f\cdot g,\overline{f}\in {\mathcal{D}}_n$ . We can verify it straightforwardly, using the definition of De Morgan function.

Thus, we get the algebra: ${\mathfrak{D}}_n={\mathcal{D}}_n\left(+,\cdot {,}^{-},0,1\right)$ , which obviously is a De Morgan algebra.

Let $a=\left(a_1,a_2\right),b=\left(b_1,b_2\right)\in 2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ . We say that $a\subseteq b$ , if $a_1\subseteq b_1$ and $a_2\subseteq b_2$ . In this way, we get a partially ordered set $2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}(\subseteq )$ . For the antichain, $S\subseteq 2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ , define the function, $f_S:D^n\to D$ , by the following way:

$f_S\left(x_1,\cdots ,x_n\right)={\displaystyle \sum }_{s=\left(s_1,s_2\right)\in S}\left({\displaystyle \prod }_{i\in s_1}{x}_i\cdot {\displaystyle \prod }_{i\in s_2}{\overline{x}}_i\right).$(10.1)

Notice that $f_S$ does not depend on the order of the elements in the set S ([120]).

Note that we set $f_{\varnothing }=0$ and $f_{\left\{\left(\varnothing ,\varnothing \right)\right\}}=1$ .

Let us consider the functions

${\delta }_n^i=x_i,i=\overline{1,n},$

as functions $D^n\to D$ . Obviously, ${\delta }_n^i$ is a De Morgan function. And according to (10.1), for any antichain $S\subseteq 2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ we have:

$f_S={\displaystyle \sum }_{s=\left(s_1,s_2\right)\in S}\left({\displaystyle \prod }_{i\in s_1}{\delta }_n^i\cdot {\displaystyle \prod }_{i\in s_2}\overline{{\delta }_n^i}\right).$

Hence, $f_S\in {\mathcal{D}}_n$ , i.e. $f_S$ is a De Morgan function for any antichain $S\subseteq 2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ .

For $s=\left(s_1,s_2\right)\in 2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ let $s^{\prime }=s_1\cup \left\{n+i:i\in s_2\right\}\in 2^{\left\{1,\cdots ,2n\right\}}$ , and for $S\subseteq 2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ let $S^{\prime }=\left\{s^{\prime }:s\in S\right\}\subseteq 2^{\left\{1,\cdots ,2n\right\}}$ . In this way we give a bijective mapping from the set of all antichains of $2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}(\subseteq )$ to the set of all antichains of $2^{\left\{1,\cdots ,2n\right\}}(\subseteq )$ . And so the number of all antichains of the partially ordered set $2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}(\subseteq )$ is $m_{2n}$ .

Now, for any De Morgan function $f\in {\mathcal{D}}_n$ from Proposition 1 we conclude that there exists an antichain $S^{\prime }\subseteq 2^{\left\{1,\cdots ,2n\right\}}$ such that:

$f\left(x_1,\cdots ,x_n\right)=\left({\phi }_f\left(y_1,\cdots ,y_n,{\overline{z}}_1,\cdots ,{\overline{z}}_n\right),{\phi }_f\left(z_1,\cdots ,z_n,{\overline{y}}_1,\cdots ,{\overline{y}}_n\right)\right)$

where S is the antichain of $2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}(\subseteq )$ , corresponding to $S^{\prime }$ .

Moreover, the number of all De Morgan functions of n variables is the same as the number of all antichains of $2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}(\subseteq )$ . Hence, we get the following result.

Theorem 10.2. For any De Morgan function f of n variables there exists a unique antichain $S\subseteq 2^{\left\{1,\cdots ,n\right\}}\times 2^{\left\{1,\cdots ,n\right\}}$ such that $f=f_S$ .

In particular, $f_{S_1}\ne f_{S_2}$ if $S_1\ne S_2$ .

Thus every nonconstant De Morgan function can be uniquely presented in the form (10.1). This form is called the canonical form (or disjunctive normal form (or briefly—DNF)) of De Morgan function f. Notice that from the proofs of Theorem 2 and Proposition 1 we get an algorithm which, for a De Morgan function, gives its disjunctive normal form. From this we conclude that every nonconstant De Morgan function can be uniquely presented in conjunctive normal form (CNF), i.e. in the following form:

${\displaystyle \prod }_{\left(s_1,s_2\right)\in S}\left({\displaystyle \sum }_{i\in s_1}{x}_i+{\displaystyle \sum }_{i\in s_2}{\overline{x}}_i\right).$

For a De Morgan function CNF is unique (we can prove this analogously to DNF).

Theorem 10.3 (Functional representation theorem for free De Morgan algebras). The algebra ${\mathfrak{D}}_n$ is a free De Morgan algebra with the system of free generators: $\Delta =\left\{{\delta }_n^1,\cdots ,{\delta }_n^n\right\}$ . Hence, every free n-generated De Morgan algebra is isomorphic to the De Morgan algebra ${\mathfrak{D}}_n$ .

Corollary 10.2. Every finitely generated free De Morgan algebra is finite.

Corollary 10.3. Every finitely generated De Morgan algebra is finite, i.e. the variety of De Morgan algebras is a Burnside variety.

A similar result is valid for the finitely generated free algebras with two binary operations of the hypervariety defined by the system of hyperidentities of the variety of Boolean algebras ( distributive lattices, De Morgan algebras) ([120]-[122]).

Problem 10.1. Develop the De Morgan analogue of the theory of Boolean functions.

The idea of De Morgan functions is also applicable in quantum computation and the theory of quantum computers.

Acknowledgements

The author was partially supported by the State Committee of Science of the Republic of Armenia, grants: 10-3/1-41, 21T-1A213.

NOTES

¹A filter on a non-empty set I is a non-empty set $\mathcal{D}$ of subsets of I satisfying the requirements: a) the intersection of any two subsets from $\mathcal{D}$ belongs to $\mathcal{D}$ ; b) all the supersets of any subset belonging to $\mathcal{D}$ also belong to $\mathcal{D}$ ; c) the empty set $\varnothing$ does not belong to $\mathcal{D}$ . A maximal filter on I, that is, a filter on I that does not lie in any other filter on I, is usually called an ultrafilter on I.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Boole, G. (1853) The Laws of Thought. Dover.
[2]	Dedekind, R. (1897) Über Zerlegungen von Zahlen Durch Ihre Grössten Gemeinsamen Theiler. In: Dedekind, R., ED., Fest-Schrift der Herzoglichen Technischen Hochschule Carolo-Wilhelmina, Vieweg+Teubner Verlag, 1-40. https://doi.org/10.1007/978-3-663-07224-9_1
[3]	Church, A. (1956) Introduction to Mathematical Logic. Vol. 1. Princeton University Press.
[4]	Mal’tsev, A.I. (1963) On the General Theory of Algebraic Systems. AMS American Mathematical Society Translations, 27, 125-142.
[5]	Mal’tsev, A.I. (1963) Some Questions of the Theory of Classes of Models. Proceedings of the IVth All-Union Mathematical Congress, 1, 169-198. (In Russian)
[6]	Mal’tsev, A.I. (1973) Algebraic Systems. Springer-Verlag.
[7]	Mal’tsev, A.I. and Mal’tsev, I.A. (2012) Iterative Post algebras. Nauka. (In Russian)
[8]	Grätzer, G. (1979) Universal Algebra. 2nd Edition, Springer-Verlag.
[9]	Chang, C.C. and Keisler, H.J. (1973) Model Theory. Studies in Logic and the Foundations of Mathematics. Vol. 73, Nort-Holland Publishing Co., American Elsevier Publishing Co. Inc.
[10]	Burris, S. and Sankappanavar, H.P. (1981) A Course in Universal Algebra. Springer-Verlag.
[11]	Plotkin, B.I. (1994) Universal Algebra, Algebraic Logic, and Databases. Kluwer Academic Publisher.
[12]	Kogalovskii, S.R. (1961) On Multiplicative Semigroups of Rings. Proceedings of the USSR Academy of Sciences, 140, 1005-1007. (In Russian)
[13]	Sabbagh, G. (1969) How Not to Characterize the Multiplicative Groups of Fields. Journal of the London Mathematical Society, 2, 369-370. https://doi.org/10.1112/jlms/s2-1.1.369
[14]	Hall Jr., M. (1959) The Theory of Groups. Chelsea.
[15]	Grätzer, G. (1964) A Theorem on Doubly Transitive Permutation Groups with Application to Universal Algebras. Fundamenta Mathematicae, 53, 25-41. https://doi.org/10.4064/fm-53-1-25-41
[16]	Ganter, B. and Werner, H. (1975) Equational Classes of Steiner Systems. Algebra Universalis, 5, 125-140. https://doi.org/10.1007/bf02485242
[17]	Belousov, V.D. (1966) Gratzer Algebra and S-Systems of Quasigroups. Mat. Issledovaniya Akad. Nauk Moldavii, Kishinev, 1, 55-81. (In Russian)
[18]	Movsisyan, Y.M. (2017) Hyperidentities and Related Concepts I. Armenian Journal of Mathematics, 2, 146-222.
[19]	Pontryagin, L.S. (1973) Continuous Groups. Nauka. (In Russian)
[20]	Movsisyan, Y.M. (1990) Hyperidentities and Hypervarieties in Algebras. Yerevan State University Press.
[21]	Fuchs, L. (1973) Infinite Abelian Groups, Volume II. Academic Press.
[22]	Kargapolov, M.I. and Merzlyakov, Y.I. (1977) Foundation of Group Theory. Nauka.
[23]	Schauffler, R. (1956) Uber die Bildung von Codewörtern. Archiv der elektrischen Übertragung, 10, 303-314.
[24]	Schauffler, R. (1957) Die Assoziativität im Ganzen, besonders bei Quasigruppen. Mathematische Zeitschrift, 67, 428-435. https://doi.org/10.1007/bf01258874
[25]	Sade, A. (1960) Théorie des systèmes demosiens de groupoï des. Pacific Journal of Mathematics, 10, 625-660. https://doi.org/10.2140/pjm.1960.10.625
[26]	Sade, A. (1961) Groupoides en relation associative et semigroupes mutuellements associatifs. Annales de la Société scientifique de Bruxelles, 1, 52-57.
[27]	Belousov, V.D. (1965) Systems of Quasigroups with Generalized Identities. Russian Mathematical Surveys, 20, 75-143. https://doi.org/10.1070/rm1965v020n01abeh004140
[28]	Denes, J., and Keedwell, A.D. (1974) Lattin Squares and Their Applications. Akademiai Kiado. (Also Academic Press and English Universities Press).
[29]	Movsisyan, Y.M. (1974) Biprimitive Classes of Algebras of Second Degree. Matematicheskie Issledovaniya, 9, 70-84. (in Russian)
[30]	Movsisyan, Y.M. (1983) Coidentities in algebras. Doklady Akademii Nauk Armyanskoi SSR, 77, 51-54.
[31]	Movsisyan, Y.M. and Davidov, S.S. (2018) Algebras That Are Nearly Quasigroups. LENAND. (In Russian)
[32]	Belousov, V.D. and Movsisyan, Y.M. (1974) On the Rank of Generalized Identities. Izv. Acad. Nauk. Armenii, Ser. Mat., 9, 135-142.
[33]	Čupona, G. (1959-1961) Za finitarnite operazii. Godishen zbornik univerzitetot Skopje, Prirod-no-Matematichki Fakultet, 1, 7-49.
[34]	Taylor, W. (1981) Hyperidentities and hypervarieties. Aequationes Mathematicae, 23, 30-49. https://doi.org/10.1007/bf02188010
[35]	Bergman, G.M. (1981) Hyperidentities of Groups and Semigroups. Aequationes Mathematicae, 23, 50-65. https://doi.org/10.1007/bf02188011
[36]	Bergman, G.M. (2015) An Invitation on General Algebra and Universal Constructions. 2nd Edition, Springer.
[37]	Padmanabhan, R. and Penner, P. (1982) Bases of Hyperidentities of Lattices and Semilattices. Comptes Rendus Math. Acad. Sci. Canada, 4, 9-14.
[38]	Skornyakov, L.A. (1985) Stochastic Algebra, Soviet Math. Izvestiya VUZ. Matematika, 29, 1-12.
[39]	Movsisyan, Y.M. (1986) Introduction to the Theory of Algebras with Hyperidentities. Yerevan State University Press. (In Russian)
[40]	Movsisyan, Y.M. (2001) Hyperidentities and Hypervarieties. Scientiae Mathematicae Japonicae, 54, 595-640.
[41]	Movsisyan, Y. (2022) Hyperidentities and Related Concepts, II. Armenian Journal of Mathematics, 10, 1-85. https://doi.org/10.52737/18291163-2018.10.4-1-85
[42]	Movsisyan, Y.M. (2018) On Functional Equations and Distributive Second-Order Formulae with Specialized Quantifiers. Algebra and Discrete Mathematics, 25, 269-285.
[43]	Smith, J.D.H. (2010) On Groups of Hypersubstitutions. Algebra universalis, 64, 39-48. https://doi.org/10.1007/s00012-010-0087-y
[44]	Padmanabhan, R. and Penner, P. (1992) Binary Hyperidentities of Lattices. Aequationes Mathematicae, 44, 154-167. https://doi.org/10.1007/bf01830976
[45]	Słomiński, J. (1993) On the Satisfiabilities and Varieties for Abstract Algebras Induced by the Cones and Functor Dynamics. Demonstratio Mathematica, 26, 11-22. https://doi.org/10.1515/dema-1993-0103
[46]	Movsisyan, Y.M. (1993) On a Theorem of Schauffler. Mathematical Notes, 53, 172-179. https://doi.org/10.1007/bf01208322
[47]	Movsisyan, Y.M., Romanowska, A.B. and Smith, J.D.H. (2004) Hyperidentities and Ginsberg-Fitting Type Theorems. Eighteenth Midwest Conference on Combinatorics, Cryptography, and Computing, Rochester, 28-30 October 2004, 15.
[48]	Movsisyan, Y.M., Romanowska, A.B. and Smith, J.D.H. (2006) Superproducts, Hyperidentities, and Algebraic Structures of Logic Programming. The Journal of Combinatorial Mathematics and Combinatorial Computing, 58, 101-111.
[49]	Krapež, A. (1980) Generalized Associativity on Groupoids. Publications de l’Institut Mathématique (Beograd), 28, 105-112.
[50]	Schweigert, D. (1993) Hyperidentities. In: Rosenberg, I.G. and Sabidussi, G., Eds., Algebras and Orders, Springer Netherlands, 405-506. https://doi.org/10.1007/978-94-017-0697-1_10
[51]	Mal’tsev, I.A. and Schveigert, D. (1989) Hyperidentitäten von AZ-algebren. Fachbereich Mathematik, Universität Kaiserslautern.
[52]	Mando, M. (1990) Regular-Identities of Length Four in Algebras. Ph.D. Thesis,.Yerevan State University.
[53]	Paseman, G. (2014) On Two Problems from “Hyperidentities and Clones”. https://arxiv.org/abc/1408.2784
[54]	Denecke, K. and Wismath, S.L. (2000) Hyperidentities and Clones. Gordon and Breach Science Publishers.
[55]	Graczynska, E. (2014) Algebra of M-Solid Quasivarieties. Siatras International Bookshop.
[56]	Graczynska, E. (2007) On the Problem on M-Hyperquasivarieties. https://arxiv.org/abc/math/0609600
[57]	Ušan, J. (1975) Globally Associative Systems of N-Ary Quasigroups. Publications de l’Institut Mathematique (Beograd), 19, 155-165.
[58]	Usan, J. (2001) Description of Super Associative Algebras with N-Quasigroup Operations. Mathematica Moravica, 2001, 129-157. https://doi.org/10.5937/matmor0105129u
[59]	Usan, J. (2006) (n, m)-Groups in the Light of the Neutral Operations Survey Article. Mathematica Moravica, 2006, 107-147. https://doi.org/10.5937/matmor0610147u
[60]	Ušan, J. and Žižović, M. (1975) N-Ary Analogy of Schauffler Theorem. Publications de l’Institut Mathematique (Beograd), 19, 167-172.
[61]	Žarkov, D. (1977) A Remark on Globally Associative Systems of N-Quasigroups over . Publications de l’Institut Mathematique (Beograd), 21, 207-211.
[62]	Belyavskaya, G.B. (1974) S-Systems of Quasigroups. Mat. Issledovaniya Acad. Nauk Moldavii, Kishinev, 9, 10-18.
[63]	Movsisyan, Y. (2022) Hyperidentities: Boolean and De Morgan Structures. World Scientific. https://doi.org/10.1142/12796
[64]	Koppitz, J. and Denecke, K. (2006) M-Solid Varieties of Algebras. Springer.
[65]	DeMorgan, A. (1847) Formal Logic. Taylor and Walton.
[66]	Denecke, K. (1998) Hyperequational Theory. Mathematica Japonica, 47, 333-356.
[67]	Denecke, K. and Koppitz, J. (1994) Hyperassociative Varieties of Semigroups. Semigroup Forum, 49, 41-48. https://doi.org/10.1007/bf02573469
[68]	Denecke, K., Lau, D., Pöschel, R. and Schweigert, D. (1991) Hyperidentities, Hyperequational Classes, and Clone Congruences. Contribution to General Algebr, Verlag Hölder-Pichler-Tempsky, 97-118.
[69]	Graczyńska, E. and Schweigert, D. (1990) Hypervarieties of a Given Type. Algebra Universalis, 27, 305-318. https://doi.org/10.1007/bf01190711
[70]	Skornyakov, L.A. (1991) General Algebra, Vol. 2. Nauka. (In Russian)
[71]	Belousov, V.D. (1961) Globally Associative Systems of Quasigroups. Matematicheskii Sbornik, 55, 221-236.
[72]	Kurosh, A.G. (1963) Lectures on General Algebra. Chelsea.
[73]	Plotkin, B.I. (1966) Automorphisms Groups of Algebraic Systems. Nauka. (In Russian)
[74]	Adian, S.I. (1979) The Burnside Problem and Identities in Groups. Springer.
[75]	Adian, S.I. (2011) The Burnside Problem and Related Topics. Russian Mathematical Surveys, 65, 805-855. https://doi.org/10.1070/rm2010v065n05abeh004702
[76]	Zel’manov, E.I. (1990) The Solution of the Restricted Burnside Problem for Groups of Odd Exponent. Math. USSR Izv, 54, 42-59.
[77]	Zel’manov, E.I. (1991) The Solution of the Restricted Burnside Problem for 2-Groups. Matematicheskii Sbornik, 182, 568-592.
[78]	Zelmanov, E.I. (1993) On Additional Laws in the Burnside Problem on Periodic Groups. International Journal of Algebra and Computation, 3, 583-600. https://doi.org/10.1142/s0218196793000330
[79]	Zelmanov, E. (2007) Some Open Problems in the Theory of Infinite Dimensional Algebras. Journal of the Korean Mathematical Society, 44, 1185-1195. https://doi.org/10.4134/jkms.2007.44.5.1185
[80]	Movsisyan, Y.M. (2016) On Burnside Varieties. VII International Joint Conference of the Georgian Mathematical Union & Georgian Mechanical Union (Dedicated to 125th Birthday Anniversary of Academician N. Muskhelishvili), Batumi, 5-9 September 2016, 172.
[81]	Burnside, W. (1902) On an Unsettled Question in the Theory of Discountinuous Groups. The Quarterly Journal of Pure and Applied Mathematics, 33, 230-238.
[82]	Sanov, I.N. (1940) Solution of Burnside’s Problem for Exponent 4. Scientific Notices of Leningrad State University, 10, 166-170. (In Russian)
[83]	Novikov, P.S. and Adian, S.I. (1968) Infinite Periodic Groups. Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya, 32, 212-244, 251-524, 709-731.
[84]	Lysenok, I.G. (1992) The Infinitude of Burnside Groups of Period 2k for . Russian Mathematical Surveys, 47, 229-230. https://doi.org/10.1070/rm1992v047n02abeh000888
[85]	Kurosh, A.G. (1974) General Algebra. Nauka. (In Russian)
[86]	Romanowska, A.B. and Smith, J.D.H. (1985) Modal Theory. Helderman-Verlag.
[87]	Romanowska, A.B. and Smith, J.D.H. (2002) Modes. World Scientific.
[88]	Knoebel, A. and Romanowska, A. (1991) Distributive Multisemilattices. Instytut Matematyczny Polskiej Akademi Nauk.
[89]	Aguiar, M. and Livernet, M. (2007) The Associative Operad and the Weak Order on the Symmetric Groups. Journal of Homotopy and Related Structures, 2, 57-84.
[90]	Loday, J. and Ronco, M.O. (2002) Order Structure on the Algebra of Permutations and of Planar Binary Trees. Journal of Algebraic Combinatorics, 15, 253-270. https://doi.org/10.1023/a:1015064508594
[91]	Richter, B. (1997) Dialgebren, Doppelalgebren und ihre Homologie, Diplomarbeit, Universitat Bonn. http://www.math.uni-hamburg.de/home/richter/publications.html
[92]	Zhuchok, Y.V. (2016) The Endomorphism Monoid of a Free Trioid of Rank 1. Algebra universalis, 76, 355-366. https://doi.org/10.1007/s00012-016-0392-1
[93]	Zhuchok, A.V. and Demko, M. (2016) Free n-Dinilpotent Doppelsemigroups. Algebra and Discrete Mathematics, 22, 304-316.
[94]	Zhuchok, A.V. and Knauer, K. (2018) Abelian doppelsemigroups. Algebra and Discrete Mathematics, 26, 290-304.
[95]	Zhuchok, A.V. (2018) Structure of Free Strong Doppelsemigroups. Communications in Algebra, 46, 3262-3279. https://doi.org/10.1080/00927872.2017.1407422
[96]	Zhuchok, A.V. (2018) Relatively Free Doppelsemigroups. Potsdam University Press.
[97]	Zhuchok, A.V., Zhuchok, Y.V. and Koppitz, J. (2019) Free Rectangular Doppelsemigroups. Journal of Algebra and Its Applications, 19, Article ID: 2050205. https://doi.org/10.1142/s0219498820502059
[98]	Barnes, W. (1966) On the γ-Rings of Nobusawa. Pacific Journal of Mathematics, 18, 411-422. https://doi.org/10.2140/pjm.1966.18.411
[99]	Hedayati, H. and Shum, K.P. (2011) An Introduction to γ-Semirings. International Journal of Algebra, 5, 709-726.
[100]	Luh, J. (1969) On the Theory of Simple γ-Rings. Michigan Mathematical Journal, 16, 65-75. https://doi.org/10.1307/mmj/1029000167
[101]	Nobusawa, N. (1964) On a Generalization of the Ring Theory. Osaka Journal of Mathematics, 1, 81-89.
[102]	Muralikrishna Rau, M. (1995) Г-Semirings-I. Southeast Asian Bull. Math., 19, 49-54.
[103]	Sardar, S.K., Gupta, S. and Shum, K.P. (2013) γ-Semigroups with Unites and Morita Equivalence for Monoids. European Journal of Pure and Applied Mathematics, 6, 1-10.
[104]	Sardar, S.K., Saha, B.C. and Shum, K.P. (2010) h-Prime and h-Semiprime Ideals in Semirings and γ-Semirings. International Journal of Algebra, 4, 209-220.
[105]	Sen, M.K. and Saha, N.K. (1986) On γ-Semigroup—I. Bulletin of the Calcutta Mathematical Society, 78, 180-186.
[106]	Seth, A. (1990) γ‐Group Congruences on Regular γ‐Semigroups. International Journal of Mathematics and Mathematical Sciences, 15, 103-106. https://doi.org/10.1155/s0161171292000115
[107]	Muralikrishna Rau, M. (1997) Г-Semirings—II. Southeast Asian Bull. Math., 21, 281-287.
[108]	Kehayopulu, N. (2011) On Regular Duo Po-γ-Semigroups. Mathematica Slovaca, 61, 871-884. https://doi.org/10.2478/s12175-011-0054-x
[109]	Koreshkov, N.A. (2014) Associative N-Tuple Algebras. Mathematical Notes, 96, 38-49. https://doi.org/10.1134/s0001434614070049
[110]	Жучок, А.В. (2020) Free Rectangular n-Tuple Semigroups. Chebyshevskii Sbornik, 20, 261-271. https://doi.org/10.22405/2226-8383-2019-20-3-261-271
[111]	Zhuchok, A.V. and Koppitz, J. (2019) Free Products of N-Tuple Semigroups. Ukrainian Mathematical Journal, 70, 1710-1726. https://doi.org/10.1007/s11253-019-01601-2
[112]	Zhuchok, A.V. (2018) Free n-Tuple Semigroups. Mathematical Notes, 103, 737-744. https://doi.org/10.1134/s0001434618050061
[113]	Denecke, K. and Pöschel, R. (1988) A Characterization of Sheffer Functions by Hyperidentities. Semigroup Forum, 37, 351-362. https://doi.org/10.1007/bf02573146
[114]	Denecke, K. and Pöschel, R. (1988) The Characterization of Primal Algebras by Hyperidentities. In: Dorninger, D., Ed., Contributions to General Algebra 6, Hölder-Pichler-Tempsky, 67-87.
[115]	Gevorkyan, P.S. (2014) On Binary G-Spaces. Mathematical Notes, 96, 600-602. https://doi.org/10.1134/s0001434614090351
[116]	Melkonian, V. (2011) Circuit Integration through Lattice Hyperterms. Discrete Mathematics, Algorithms and Applications, 03, 101-119. https://doi.org/10.1142/s179383091100105x
[117]	Anosov, A.D. (2007) On Homomorphisms of Many-Sorted Algebraic Systems in Connection with Cryptographic Applications. Discrete Mathematics and Applications, 17, 331-347. https://doi.org/10.1515/dma.2007.028
[118]	Aczél, J. (1971) Proof of a Theorem on Distributive Type Hyperidentities. Algebra Universalis, 1, 1-6. https://doi.org/10.1007/bf02944948
[119]	Movsisyan, Y.M. (1990) The Multiplicative GROUP of a field and Hyperidentities. Mathematics of the USSR-Izvestiya, 35, 377-391. https://doi.org/10.1070/im1990v035n02abeh000708
[120]	Movsisyan, Y.M. (1993) Hyperidentities of Boolean Algebras. Russian Academy of Sciences. Izvestiya Mathematics, 40, 607-622. https://doi.org/10.1070/im1993v040n03abeh002179
[121]	Movsisyan, Y.M. (1996) Algebras with Hyperidentities of the Variety of Boolean Algebras. Izvestiya: Mathematics, 60, 1219-1260. https://doi.org/10.1070/im1996v060n06abeh000098
[122]	Movsisyan, Y.M. (1996) Superidentities in the Variety of Lattices. Mathematical Notes, 59, 686-688. https://doi.org/10.1007/bf02307222
[123]	Penner, P. (1984) Hyperidentities of Semilattices. Houston Journal of Mathematics, 10, 81-108.
[124]	Movsisyan, Y.M. (2011) Bilattices and Hyperidentities. Proceedings of the Steklov Institute of Mathematics, 274, 174-192. https://doi.org/10.1134/s0081543811060113
[125]	Movsisyan, Y.M. (2008) Interlaced, Modular, Distributive and Boolean Bilattices. Armenian Journal of Mathematics, 1, 7-13.
[126]	Movsisyan, Y.M. (2022) Boole-De Morgan Bilattices. Journal of Multiple-Valued Logic and Soft Computing, 38, 137-152.
[127]	Birkhoff, G. (1944) Subdirect Unions in Universal Algebra. Bulletin of the American Mathematical Society, 50, 764-768. https://doi.org/10.1090/s0002-9904-1944-08235-9
[128]	Birkhoff, G. (1935) On the Structure of Abstract Algebras. Mathematical Proceedings of the Cambridge Philosophical Society, 31, 433-454. https://doi.org/10.1017/s0305004100013463
[129]	Cohn, P.M. (1965) Universal Algebra. Harper & Row Publishers.
[130]	Grätzer, G. (2011) Lattice Theory: Foundation. Springer.
[131]	McKenzie, R.N., McNulty, G.F. and Taylor, W.T. (1987) Algebras, Lattices, Varieties, Volume I. AMS Bookstore.
[132]	Pinus, A.G. (2005) Foundations of Universal Algebra. Novosibirsk State Technical University. (In Russian)
[133]	Smith, J.D.H. and Romanowska, A.B. (1999) Post‐Modern Algebra. Wiley. https://doi.org/10.1002/9781118032589
[134]	Korshunov, A.D. (2003) Monotone Boolean Functions. Russian Mathematical Surveys, 58, 929-1001. https://doi.org/10.1070/rm2003v058n05abeh000667
[135]	Crama, Y. and Hammer, P.L. (2011) Boolean Functions: Theory, Algorithms, and Applications. Cambridge University Press. https://doi.org/10.1017/cbo9780511852008
[136]	Birkhoff, G. (1979) Lattice Theory. 3rd Edition, American Mathematical Society.
[137]	Balbes, R. and Dwinger, P. (1974) Distributive Lattices. University of Missouri Press.
[138]	Bialynicki-Birula, A. and Rasiowa, H. (1957) On the Representation of Quasi-Boolean Algebras. Bulletin L’Académie Polonaise des Science, Série des Sciences Mathématiques, Astronomiques et Physiques, 5, 259-261.
[139]	Brzozowski, J.A. (2000) De Morgan Bisemilattices. The 30th IEEE International Sym-pozium on Multiple-Valued Logic, Portland, May 2000, 23-25.
[140]	Brzozowski, J.A. (2001) A Characterization of de Morgan Algebras. International Journal of Algebra and Computation, 11, 525-527. https://doi.org/10.1142/s0218196701000681
[141]	Brzozowski, J.A. and Seger, C.J.H. (1995) Asynchronous Circuits. Springer-Verlag.
[142]	Ésik, Z. (1998) A Cayley Theorem for Ternary Algebras. International Journal of Algebra and Computation, 8, 311-316. https://doi.org/10.1142/s0218196798000156
[143]	Kalman, J.A. (1958) Lattices with Involution. Transactions of the American Mathematical Society, 87, 485-491. https://doi.org/10.1090/s0002-9947-1958-0095135-x
[144]	Markov, A.A. (1950) Constructive Logic. Uspekhi Matematicheskikh Nauk, 5, 187-188. (In Russian)
[145]	Moisil, G.C. (1935) Recherches sur l’algebre de la logique. Annales scientifiques de l’uni-versite de Jassy, 22, 1-117.
[146]	Rasiowa, H. (1974) An Algebraic Approach to Non-Classical Logics. Nort-Holland Publisher.
[147]	Sankappanavar, H.P. (1980) A Characterization of Principal Congruences of De Morgan Algebras and Its ApplicationsStudies in Logic and the Foundations of Mathematics, 99, 341-349. https://doi.org/10.1016/s0049-237x(09)70493-8
[148]	Sankappanavar, H.P. (2018) Implication Zroupoids: An Abstraction from De Morgan Algebras. Emil Artin International Conference dedicated to the 120th Anniversary of Emil Artin, Yerevan, 27 May-2 June 2018, 119-120.
[149]	Movsisyan, Y.M. (2005) Boolean Bisemigroups, Bigroups and Local Bigroups. Computer Science and Information Technologies, Proceedings of the Conference, Yerevan, 19-20 September 2005, 97-104.
[150]	Movsisyan, Y.M. (2005) On the Representations of De Morgan Algebras. In: Ehrenfeucht, A., Grzegorczyk, A., Mycielski, J., Ryll-Nardzewski, C., Eds., Trends in Logic III, Studia Logica, Warsaw, 23-25 September 2005. https://mimuw.edu.pl/~mrr/
[151]	Belyavskaya, G.B. and Cheban, A.M. (1972) S-Systems of Arbitrary Index I. Mat Issledovaniya Akad. Nauk Moldavii, Kishinev, 7, 23-43.
[152]	Belyavskaya, G.B. and Cheban, A.M. (1972) S-Systems of Arbitrary Index II. Mat Issledovaniya Akad. Nauk Moldavii, Kishinev, 7, 3-13.
[153]	Bloom, S.L., Ésik, Z. and Manes, E.G. (1990) A Cayley Theorem for Boolean Algebras. The American Mathematical Monthly, 97, 831-833. https://doi.org/10.1080/00029890.1990.11995668
[154]	Movsisyan, Y.M. (2009) Binary Representations of Algebras with at Most Two Binary Operations: A Cayley Theorem for Distributive Lattices. International Journal of Algebra and Computation, 19, 97-106. https://doi.org/10.1142/s0218196709004993
[155]	Padmanabhan, R. and Penner, P. (1998) Lattice Ordered Polynomial Algebras. Order, 15, 75-86. https://doi.org/10.1023/a:1006036222760
[156]	Przytycki, J.H. (2015) Knots and Distributive Homology: From Arc Colorings to Yang-Baxter Homology. In: Kauffman, L.H. and Manturov, V.O., Eds., New Ideas in Low Dimensional Topology, World Scientific, 413-488. https://doi.org/10.1142/9789814630627_0011
[157]	Stein, S.K. (1957) On the Foundations of Quasigroups. Transactions of the American Mathematical Society, 85, 228-256. https://doi.org/10.1090/s0002-9947-1957-0094404-6
[158]	Urbanik, K. (1964) On Algebraic Operations in Idempotent Algebras. Colloquium Mathematicum, 13, 129-157. https://doi.org/10.4064/cm-13-2-129-157
[159]	Lau, D. (2006) Functional Algebras on Finite Sets, a Basic Course on Many-Valued Logic and Clone Theory. Springer-Verlag.
[160]	Post, E.L. (1921) Introduction to a General Theory of Elementary Propositions. American Journal of Mathematics, 43, 163-185. https://doi.org/10.2307/2370324
[161]	Post, E. (1941) The Two-Valued Iterative Systems of Mathematical Logic. Princeton University Press.
[162]	Arieli, O. and Avron, A. (1998) The Value of the Four Values. Artificial Intelligence, 102, 97-141. https://doi.org/10.1016/s0004-3702(98)00032-0
[163]	Belnap, N.D. (1977) A Useful Four-Valued Logic. In: Epstein, G. and Dunn, J.M., Eds., Modern Uses of Multiple-Valued Logic, Springer Netherlands, 5-37. https://doi.org/10.1007/978-94-010-1161-7_2
[164]	Bou, F. and Rivieccio, U. (2010) The Logic of Distributive Bilattices. Logic Journal of IGPL, 19, 183-216. https://doi.org/10.1093/jigpal/jzq041
[165]	Gehrke, M., Walker, C. and Walker, E. (1997) A Mathematical Setting for Fuzzy Logics. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 5, 223-238. https://doi.org/10.1142/s021848859700021x
[166]	Gehrke, M., Walker, C. and Walker, E. (2000) Some Comments on Fuzzy Normal Forms. Ninth IEEE International Conference on Fuzzy Systems. FUZZ—IEEE 2000 (Cat. No.00CH37063), San Antonio, 7-10 May 2000, 593-598. https://doi.org/10.1109/fuzzy.2000.839060
[167]	Kondo, M. (2002) On the Structure of Weak Interlaced Bilattice. Proceedings 32nd IEEE International Symposium on Multiple-Valued Logic, Boston, 15-18 May 2002, 23-26. https://doi.org/10.1109/ismvl.2002.1011065
[168]	Mobasher, B., Pigozzi, D. and Slutzki, G. (1997) Multi-Valued Logic Programming Semantics an Algebraic Approach. Theoretical Computer Science, 171, 77-109. https://doi.org/10.1016/s0304-3975(96)00126-0
[169]	Mobasher, B., Pigozzi, D., Slutzki, G. and Voutsadakis, G. (2000) A Duality Theory for Bilattices. Algebra Universalis, 43, 109-125. https://doi.org/10.1007/s000120050149