Characterization of clones of boolean operations by identities
In [4] the authors characterized all clones of Boolean operations (Boolean clones) by functional terms. In this paper we consider a Galois connection between operations and equations and characterize all Boolean clones by using of identities. For each Boolean clone we obtain a set of equations wi...
Gespeichert in:
| Datum: | 2007 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2007
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/157376 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Characterization of clones of boolean operations by identities / R. Butkote, K. Denecke // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 2. — С. 70–90. — Бібліогр.: 6 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-157376 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1573762019-06-21T01:30:26Z Characterization of clones of boolean operations by identities Butkote, R. Denecke, K. In [4] the authors characterized all clones of Boolean operations (Boolean clones) by functional terms. In this paper we consider a Galois connection between operations and equations and characterize all Boolean clones by using of identities. For each Boolean clone we obtain a set of equations with the property that an operation f belongs to this clone if and only if it satisfies these equations. 2007 Article Characterization of clones of boolean operations by identities / R. Butkote, K. Denecke // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 2. — С. 70–90. — Бібліогр.: 6 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 03B05, 03C05, 08B05. http://dspace.nbuv.gov.ua/handle/123456789/157376 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
In [4] the authors characterized all clones of Boolean operations (Boolean clones) by functional terms. In this paper
we consider a Galois connection between operations and equations
and characterize all Boolean clones by using of identities. For each
Boolean clone we obtain a set of equations with the property that
an operation f belongs to this clone if and only if it satisfies these
equations. |
| format |
Article |
| author |
Butkote, R. Denecke, K. |
| spellingShingle |
Butkote, R. Denecke, K. Characterization of clones of boolean operations by identities Algebra and Discrete Mathematics |
| author_facet |
Butkote, R. Denecke, K. |
| author_sort |
Butkote, R. |
| title |
Characterization of clones of boolean operations by identities |
| title_short |
Characterization of clones of boolean operations by identities |
| title_full |
Characterization of clones of boolean operations by identities |
| title_fullStr |
Characterization of clones of boolean operations by identities |
| title_full_unstemmed |
Characterization of clones of boolean operations by identities |
| title_sort |
characterization of clones of boolean operations by identities |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2007 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/157376 |
| citation_txt |
Characterization of clones of boolean operations by identities / R. Butkote, K. Denecke // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 2. — С. 70–90. — Бібліогр.: 6 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT butkoter characterizationofclonesofbooleanoperationsbyidentities AT deneckek characterizationofclonesofbooleanoperationsbyidentities |
| first_indexed |
2025-07-14T09:48:56Z |
| last_indexed |
2025-07-14T09:48:56Z |
| _version_ |
1837615323010826240 |
| fulltext |
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 2. (2007). pp. 70 – 90
c© Journal “Algebra and Discrete Mathematics”
Characterization of clones of boolean operations
by identities
Runglawan Butkote and Klaus Denecke
Communicated by V. I. Sushansky
Dedicated to V.I. Sushchansky on the occasion of his 60th birthday
Abstract. In [4] the authors characterized all clones of Boo-
lean operations (Boolean clones) by functional terms. In this paper
we consider a Galois connection between operations and equations
and characterize all Boolean clones by using of identities. For each
Boolean clone we obtain a set of equations with the property that
an operation f belongs to this clone if and only if it satisfies these
equations.
1. Preliminaries
Let A be the two-element set A = {0, 1}. An n-ary Boolean opera-
tion is a map fA : An → A. We denote by O
(n)
A the set of all n-
ary operations defined on A. Let OA :=
⋃
n≥1
O
(n)
A be the set of all
operations defined on A. On the set OA we may define the follow-
ing composition operations Sn,A
m : O
(n)
A ×
(
O
(m)
A
)n
→ O
(m)
A by setting
Sn,A
m (fA, gA
1 , . . . , gA
n ) := fA(gA
1 , . . . , gA
n ), where fA(gA
1 , . . . , gA
n ) ∈ O
(m)
A
is defined by
fA(gA
1 , . . . , gA
n )(a1, . . . , am) := fA(gA
1 (a1, . . . , am), . . . , gA
n (a1, . . . , am))
for all m-tuples (a1, . . . , am) ∈ Am.
2000 Mathematics Subject Classification: 03B05, 03C05, 08B05.
Key words and phrases: Clone of Boolean operations, identity, Galois connec-
tion.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.R. Butkote, K. Denecke 71
Further, we consider projections en,A
i : An → A, 1 ≤ i ≤ n, defined
by en,A
i (a1, . . . , an) := ai, as nullary operations.
A clone of Boolean operations, for short a Boolean clone, is a class of
Boolean operations that contains all projections and is closed under all
composition operations Sn,A
m , m, n ≥ 1, m, n ∈ N. All clones of Boolean
operations form a lattice, where the lattice operation meet is the intersec-
tion. The second lattice operation applied to clones is defined to be the
smallest clone that contains the union of both clones. Since any clone can
be regarded as a multi-based algebra, all Boolean clones form a complete
lattice which is the lattice of all subclones of the clone O{0,1}, originally
described in [5], (see also [6]).
Boolean clones can be characterized by relations in the form PolAρ.
Here PolAρ is the set of all operations fA defined on A preserving the
h-ary relation ρ in the sense that from
(a11, . . . , a1h) ∈ ρ, . . . , (an1, . . . , anh) ∈ ρ
it follows (fA((a11, . . . , an1), . . . , f
A(a1h, . . . , anh)) ∈ ρ. It is easy to see
that all sets of operations which have the form PolAρ are clones. Con-
versely, each clone can be presented in this way by relations.
In this paper we characterize all Boolean clones by equations. This
was also done in [4], but in our paper we will use the equational theory
of Universal Algebra for a description of clones by equations.
If fA ∈ O
(n)
A , then one can consider the algebra A = (A;∧,∨,⇒
,⇔,⊕,¬,0A,1A, fA) of type τ = (2, 2, 2, 2, 2, 1, 0, 0, n). To define the
language over this algebra, we use the following notation,
K is the operation symbol corresponding to the conjunction ∧,
D is the operation symbol corresponding to the disjuction ∨,
I is the operation symbol corresponding to the implication ⇒,
E is the operation symbol corresponding to the equivalence ⇔,
M is the operation symbol corresponding to the addition modulo 2,
N is the operation symbol corresponding to the negation ¬,
0 is the operation symbol corresponding to the constant 0,
1 is the operation symbol corresponding to the constant 1,
F is the operation symbol corresponding to the operation fA.
If fA ∈ O
(n)
A , then the dual operation (fA)d can be defined by
(fA)d(a1, . . . , an) := ¬fA(¬a1, . . . ,¬an) for all (a1, . . . , an) ∈ An.
Let fA ∈ O
(n)
A and i ∈ {1, . . . , n}. We say that the i − th variable of
fA is essential (or fA depends essentially on the i − th variable) if there
are n-tuples
a = (a1, . . . , ai−1, b, ai+1, . . . , an), a′ = (a1, . . . , ai−1, c, ai+1, . . . , an)
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.72 Boolean Clones and Identities
such that b 6= c and fA(a) 6= fA(a′). Otherwise the i − th variable is
called fictitious (or non-essential).
We denote by Alg(τ) the class of all algebras of type τ . Terms of type
τ over a set X of variables are defined as follows,
(i) xi ∈ X is a term of type τ and 0,1 are terms of type τ ,
(ii) if t1, . . . , tn are terms of type τ and if F is the n−ary operation
symbol, then t = F (t1, . . . , tn) is a term of type τ , if t1, t2 are
terms, then t1Kt2, t1Dt2, t1It2, t1Et2, t1Mt2, Nt1 are terms of
type τ .
We denote the set of all terms of type τ by Wτ (X). If Xm =
{x1, . . . , xm} is a finite set of variables, then by (i) and (ii) the set Wτ (Xm)
of m−ary terms is defined.
For every term t ∈ Wτ (Xm) and for every algebra A = (A;∧,∨,⇒
,⇔,⊕,¬,0A,1A, fA) we define an operation tA ∈ O
(m)
A , called term op-
eration, inductively by the following steps,
(i) if t = xi ∈ Xm, then xA
i = em,A
i (the m−ary projection on the i-th
input, 1 ≤ i ≤ m),
(ii) if t1, t2 are terms of type τ , then (t1Kt2)
A = tA1 ∧tA2 , (t1Dt2)
A = tA1 ∨
tA2 , (t1It2)
A = tA1 ⇒ tA2 , (t1Et2)
A = tA1 ⇔ tA2 , (t1Mt2)
A = tA1 ⊕ tA2 ,
(Nt1)
A = ¬tA1 and 0A = 0, 1A = 1,
(iii) if t = F (t1, . . . , tn) and tA1 , . . . , tAn are the term operations which are
induced by t1, . . . , tn, then tA = fA(tA1 , . . . , tAn ). Here fA(tA1 , . . . , tAn )
is the operation defined by
fA(tA1 , . . . , tAn )(a1, . . . , an) = fA(tA1 (a1, . . . , an), . . . , tA(a1, . . . , an)).
Since later on we will replace only the symbol F by n−ary elements
of a clone instead of the correct notations t1Kt2, t1Dt2, t1It2, t1Et2,
t1Mt2, Nt1 we will use t1 ∧ t2, t1 ∨ t2, t1 ⇒ t2, t1 ⇔ t2, t1 ⊕ t2, ¬t1.
A pair s ≈ t of terms from Wτ (X) is called an identity in the algebra
A if sA = tA, i.e. if the induced term operations are equal. In this case
we write A |= s ≈ t.
Let IdBA be the set of all identities satisfied in A. For the class
K ⊆ Alg(τ) we denote by IdBK the set of all identities satisfied by each
algebra A from K. If Σ is a set of equations s ≈ t consisting of terms from
Wτ (X), then we denote the class of all algebras satisfying each equation
from Σ as identity by ModBΣ.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.R. Butkote, K. Denecke 73
Then we get a Galois connection (IdB, ModB), i.e. the following
properties are satisfied:
Σ1 ⊆ Σ2 ⇒ ModBΣ2 ⊆ ModBΣ1,
C1 ⊆ C2 ⇒ IdBC2 ⊆ IdBC1,
Σ ⊆ IdBModBΣ,
K ⊆ ModBIdBC.
2. A Galois Connection between Operations and Equa-
tions
Let fA ∈ O
(n)
A be an n-ary operation and let
A = (A;∧,∨,⇒,⇔,⊕,¬,0A,1A, fA)
be an algebra of type τ = (2, 2, 2, 2, 2, 1, 0, 0, n). Let s, t ∈ Wτ (X) be
terms of type τ . Then s ≈ t is satisfied as identity in A, and we write
A |= s ≈ t if sA = tA. Then we define
Definition 2.1. Let s ≈ t be an equation consisting of terms s, t of type
τ , i.e. s ≈ t ∈ Wτ (X)2. Then by
fA ⊢ s ≈ t ⇔ A = (A;∧,∨,⇒,⇔,⊕,¬,0A,1A, fA) |= s ≈ t
we define a binary relation ⊢ between O(n)(A) and Wτ (X). If fA ⊢ s ≈ t
holds, then we say that the operation fA satisfies the equation s ≈ t.
For C ⊆ O(n)(A) we define
C ⊢ fA ⇔ ∀fA ∈ C (fA ⊢ s ≈ t)
and for Σ ⊆ Wτ (X)2 we set
C ⊢ Σ ⇔ ∀s ≈ t ∈ Σ (C ⊢ s ≈ t).
Let C ⊆ O
(n)
A , A = {0, 1}, and let Σ ⊆ Wτ (X)2. Then we define
two operations FBMod : P(O
(n)
A ) → P(Wτ (X)2) ( where P denotes the
formation of the power set) and IdB : P(Wτ (X)2) → P(O
(n)
A ) by
FBModΣ =
{
fA | fA ∈ O
(n)
A and ∀s ≈ t ∈ Σ (fA ⊢ s ≈ t)
}
,
IdBC =
{
s ≈ t | s, t ∈ Wτ (X) and ∀fA ∈ C (fA ⊢ s ≈ t)
}
.
Then the pair (FBMod, IdB) is a Galois connection, i.e. we have
Σ1 ⊆ Σ2 ⇒ FBModΣ2 ⊆ FBModΣ1,
C1 ⊆ C2 ⇒ IdBC2 ⊆ IdBC1,
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.74 Boolean Clones and Identities
Σ ⊆ IdBFBModΣ,
C ⊆ FBModIdBC.
Further, we get two closure operators IdBFBMod and FBModIdB on
P
(
Wn(X)2
)
and on P
(
O
(n)
A ), respectively.
Our main question is whether each clone of Boolean operations has
the form FBModΣ for a set Σ of equations. We are especially interested
to find one-element sets Σ.
3. The Lattice of all Boolean Clones
The set of all clones of Boolean operations, originally described by E. Post
([5], [6]) forms a lattice. These clones and lattice are often called Post’s
classes and the lattice is denoted as Post’s lattice. Post’s lattice is count-
ably infinite, complete, algebraic, atomic and dually atomic. It is also
known that every clone in the lattice is finitely generated. Post’s classes
can be described as follows and the following Hasse diagram illustrates
the lattice of all Boolean clones.
C1 := O{0,1}.
C3 := Pol{0}, and dually C2 := Pol{1}.
C4 := C2 ∩ C3.
A1 := Pol ≤, where ≤:= {(00), (01), (11)}, (monotone Boolean func-
tions).
A3 := A1 ∩ C3, and dually A2 := A1 ∩ C2.
A4 := A1 ∩ C4.
D3 := PolN , where N := {(01), (10)}, (self-dual Boolean functions).
D1 := D3 ∩ C4.
D2 := D3 ∩ A1.
L1 := PolρG
, where ρG :=
{
(x, y, z, u) ∈ {0, 1}4 | x + y = z + u
}
,
(linear Boolean functions).
L3 := L1 ∩ C3, dually L2 := L1 ∩ C2.
L4 := L1 ∩ C4.
L5 := L1 ∩ D3.
Fµ
8 := PolDµ, where Dµ := {0, 1}µ \ {(1, . . . , 1}, for µ ≥ 2, and dually
Fµ
4 := PolD
′
µ with D
′
µ := {0, 1}µ \ {(0, . . . , 0}.
Fµ
7 := Fµ
8 ∩ A1, and dually Fµ
3 := Fµ
4 ∩ A1.
Fµ
6 := Fµ
8 ∩ A4, and dually Fµ
2 := Fµ
4 ∩ A4.
Fµ
5 := Fµ
8 ∩ C4, and dually Fµ
1 := Fµ
4 ∩ C4.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.R. Butkote, K. Denecke 75
F∞
8 :
∞
⋂
µ=2
PolDµ, and dually F∞
4 :
∞
⋂
µ=2
PolD
′
µ.
F∞
7 := F∞
8 ∩ A1, and dually F∞
3 .
F∞
6 := F∞
8 ∩ A4, and dually F∞
2 .
F∞
5 := F∞
8 ∩ C4, and dually F∞
1 .
P1 := 〈{et}〉, and dually S1 := 〈{vel}〉
P3 := 〈{et,0}〉, and dually S1 := 〈{vel,1}〉
P5 := 〈{et,1}〉, and dually S5 := 〈{vel,0}〉
P6 := 〈{et,0,1}〉, and dually S6 := 〈{vel,0,1}〉.
O9 :=
〈{
e1
1,0,1, non
}〉
= 〈{non,0}〉.
O8 :=
〈{
e1
1,0,1
}〉
.
O6 :=
〈{
e1
1,0
}〉
, and dually O5 :=
〈{
e1
1,1
}〉
.
O4 :=
〈{
e1
1, non
}〉
= 〈{non}〉.
O1 :=
〈{
e1
1
}〉
.
Note that 0,1 are the unary constant functions with values 0 and
1, respectively, e1
1 is the identity, and vel, et and non are ∨, ∧ and ¬,
respectively.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.
r
r
r r
r
rr
r
r
r
r
r
r
r
r
r
r
r
r
r r
r
r
r
r
r r
r
r
r
r
r
r
r
r
r
r r
r
rr
r
r
r
r
r
r
r
r
r
r
r
r
r
F2
8
F
3
8
F∞
8
F2
5
F3
5
F∞
5
F∞
7
F3
7
F2
7
F
2
6
F3
6
F∞
6
P3
P1
P6
P5
L5
L1
D2
D1
D3
A4
A1
C4
C1
C3
A3
L3L2
L4
O9
O1
O6O5
O8
O4
C2
A2
S5
S6
S1
S3
F∞1
F3
1
F2
1
F2
4
F
3
4
F∞
4 F∞
3
F3
3
F2
3
F∞
2
F3
2
F2
2
Figure 1: Post’s Lattice of all Boolean Clones
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.76 Boolean Clones and Identities
4. Identities for Clones of Boolean Operations
There are several methods to characterize clones of Boolean operations.
In [4] the authors characterized all clones of Boolean operations by so-
called functional terms. Using the langauge of Universal Algebra for each
clone of Boolean operations we obtain a set of characterizing identities
satisfied in the algebra A = ({0, 1} ;∧,∨,⇒,⇔,⊕,¬,0A,1A, fA). The
results are given in the following table. Our notation goes partly back to
E. L. Post [6].
Clones Identities
C1 1 ≈ 1
C3 ¬F (0) ≈ 1
C2 F (1) ≈ 1
C4 ¬F (0) ∧ F (1) ≈ 1
A1 F (x) → F (x ∨ y) ≈ 1
A3 ¬F (0) ∧ (¬F (x ∨ F (x ∨ y)) ≈ 1
A2 F (1) ∧ (¬F (x) ∨ F (x ∨ y)) ≈ 1
A4 ¬F (0) ∧ F (1) ∧ (¬F (x) ∨ F (x ∨ y)) ≈ 1
D3 F (x) ⊕ F (x) ≈ 1
D1 ¬F (0) ∧ (F (x) ⊕ F (x)) ≈ 1
D2 (F (x) ⊕ F (x̄)) ∧ (¬F (x) ∨ F (x ∨ y)) ≈ 1
L1 1 ⊕ F (0) ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y) ≈ 1
L3 1 ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y) ≈ 1
L2 F (1) ∧ (1 ⊕ F (0) ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y) ≈ 1
L4 F (1) ∧ (1 ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y)) ≈ 1
L5 (F (1) ⊕ F (0) ∧ (1 ⊕ F (0) ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y))
≈ 1
P6 F (x) ∧ F (y) ≈ F (x ∧ y)
P3 ¬F (0) ∧ (F (x) ∧ F (y) ⇔ F (x ∧ y)) ≈ 1
P5 F (1) ∧ (F (x) ∧ F (y) ⇔ F (x ∧ y)) ≈ 1
P1 ¬F (0) ∧ F (1) ∧ (F (x) ∧ F (y) ⇔ F (x ∧ y)) ≈ 1
S6 (F (x) ∨ F (y)) ≈ F (x ∨ y)
S5 ¬F (0) ∧ ((F (x) ∨ F (y)) ⇔ F (x ∨ y)) ≈ 1
S3 F (1) ∧ ((F (x) ∨ F (y)) ⇔ F (x ∨ y)) ≈ 1
S1 ¬F (0) ∧ F (1) ∧ ((F (x) ∨ F (y)) ⇔ F (x ∨ y)) ≈ 1
Fµ
8
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1 ∧ y) ≈ 1
Fµ
4
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1 ∨ y) ≈ 1
F∞
8
∞
∧
µ=2
(
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1 ∧ y)) ≈ 1
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.R. Butkote, K. Denecke 77
Clones Identities
F∞
4
∞
∧
µ=2
(
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1 ∨ y)) ≈ 1
Fµ
5 F (1) ∧ (
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1 ∧ y)) ≈ 1
Fµ
1 ¬F (0) ∧ (
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1 ∨ y)) ≈ 1
F∞
5 F (1) ∧ (
∞
∧
µ=2
(
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1 ∧ y))) ≈ 1
F∞
1 ¬F (0) ∧ (
∞
∧
µ=2
(
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1 ∨ y))) ≈ 1
F 2
7 F (x) ⇒ ¬F (x̄) ∧ F (x ∨ y) ≈ 1
Fµ
7
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1)) ∧ F (x1 ∨ x2) ≈ 1
F 2
3 ¬F (x) ⇒ F (x̄) ∧ ¬F (x ∧ y) ≈ 1
Fµ
3
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1) ∧ ¬F (x1 ∧ x2)
≈ 1
F∞
7
∞
∧
µ=2
(
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1)) ∧ F (x1 ∨ x2))
≈ 1
F∞
3
∞
∧
µ=2
(
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1) ∧ ¬F (x1 ∧ x2))
≈ 1
F 2
6 F (1) ∧ (F (x) ⇒ ¬F (x) ∧ F (x ∨ y)) ≈ 1
Fµ
6 F (1) ∧ (
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1)∧
F (x1 ∨ x2)))) ≈ 1
F 2
2 ¬F (0) ∧ ¬F (x) ⇒ F (x) ∧ ¬F (x ∧ y)) ≈ 1
Fµ
2 ¬F (0) ∧ (
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1)∧
¬F (x1 ∧ x2)) ≈ 1
F∞
6 F (1) ∧ (
∞
∧
µ=2
(
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1)
∧F (x1 ∨ x2))) ≈ 1
F∞
2 ¬F (0) ∧ (
∞
∧
µ=2
(
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1)∧
¬F (x1 ∧ x2))) ≈ 1
O9 ((F (x ⇔ F (y)) ⇒ (F (x ⇔ F (x ∧ y)))∧
(1 ⊕ f(0) ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y)) ≈ 1
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.78 Boolean Clones and Identities
Clones Identities
O4 (F (0) ⊕ F (1)) ∧ ((F (x) ⇔ F (y)) ⇒ (F (x)
⇔ F (x ∧ y)))∧
(1 ⊕ f(0) ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y)) ≈ 1
O8 (F (x) ⇒ F (x ∨ y)) ∧ (1 ⊕ f(0) ⊕ F (x) ⊕ F (y)
⊕F (x ⊕ y)) ≈ 1
O6 (F (x) ⇒ F (x ∨ y)) ∧ (1 ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y))
≈ 1
O5 F (1) ∧ (F (x) ⇒ F (x ∨ y)) ∧ (1 ⊕ f(0) ⊕ F (x) ⊕ F (y)
⊕F (x ⊕ y)) ≈ 1
O1 F (1) ∧ (F (x) ⇒ F (x ∨ y)) ∧ (1 ⊕ F (x) ⊕ F (y)
⊕F (x ⊕ y)) ≈ 1
The main result is that every clone of Boolean operations can be
characterized by a set of identities. We will give a complete proof of
this result. We denote the n-tuples (0, . . . , 0) and (1, . . . , 1) by 0 and 1,
respectively. The proof can be shortened using the following observations.
Lemma 4.1. Let Σ = {s ≈ t}, then FBModΣ ∩ C2 = FBMod{F (1)
∧ s ≈ t}.
Proof. Let fA ∈ FBMod{s ≈ t}∩C2, then fA ⊢ s ≈ t and fA(1, . . . , 1) =
1. Now we get sA = tA and then F (1)A∧sA = tA. Therefore [F (1)∧s]A =
tA. Thus fA ∈ FBMod{F (1) ∧ s ≈ t}. Let fA ∈ FBMod{F (1) ∧ s ≈ t},
then [F (1) ∧ s]A = tA. Further F (1)A ∧ sA = tA. Therefore fA(1) = 1
and sA = tA. Hence fA ∈ C2 and fA ∈ FBMod{s ≈ t}.
The following lemma can be proved in a similar way.
Lemma 4.2. Let Σ = {s ≈ t}, then FBModΣ ∩ C3 = FBMod{¬F (0) ∧
s ≈ t}.
Lemma 4.1 and Lemma 4.2 are needed only for the special case when
Σ = {s ≈ 1}. Then both follow from the the next lemma.
Lemma 4.3. Let Σ1 = {s ≈ 1} and Σ2 = {t ≈ 1}, then FBModΣ1 ∩
FBModΣ2 = FBMod{s ∧ t ≈ 1}.
Proof. Let fA ∈ FBModΣ1∩FBModΣ2, then fA ⊢ s ≈ 1 and fA ⊢ t ≈ 1.
Further we get sA ≡ 1 and tA ≡ 1. Therefore from sA ∧ tA = [s∧ t]A ≡ 1
implies fA ⊢ s ∧ t ≈ 1. Hence fA ∈ FBMod{s ∧ t ≈ 1}.
Let fA ∈ FBMod{s ∧ t ≈ 1}, then fA ⊢ s ∧ t ≈ 1. Therefore
[s ∧ t]A ≡ 1. Then from sA ∧ tA ≡ 1 we get sA ≡ 1 and tA ≡ 1. Now we
have fA ⊢ s ≈ 1 and fA ⊢ t ≈ 1. Thus fA ∈ FBModΣ1∩FBModΣ2.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.R. Butkote, K. Denecke 79
Let F d be a new n-ary operation symbol. Let
L = {K, D, E, M, N, 0, 1, F, F d}.
Instead of these symbols we use L = {∧,∨,⇔,⊕,¬, 0, 1, F, F d}. Let τ
′
be the type which uses only operation symbols from L.
Definition 4.4. Let Wτ
′ (Xm) be the set of all m-ary terms of type τ
′
.
Now for each t ∈ Wτ
′ (Xm) we define the dual term td inductively by the
following steps,
(i) if t = xi ∈ Xm, then xd
i = xi, 1 ≤ i ≤ m,
(ii) if t1, . . . , tn ∈ Wτ
′ (Xm) and td1, . . . , t
d
n are dual terms of t1, . . . , tn,
respectively, then (t1 ∧ t2)
d = td1 ∨ td2, (t1 ∨ t2)
d = td1 ∧ td2, (t1 ⇔
t2)
d = td1 ⊕ td2, (¬t1)
d = td1 and F (t1, . . . , tn) = F d(td1, . . . , t
d
n).
This gives the set Wτ
′ (Xm)d ⊆ Wτ
′ (Xm). For a subset M ⊆ Wτ
′ (Xm)
we define Md := {td | t ∈ M} and for the algebra A = (A; MA, fA) we
define Ad = (A; (Md)A, (fd)A).
Lemma 4.5. For each t ∈ Wτ
′ (Xm) we get (td)A = (tA)d.
Proof. If t = xi ∈ Xm, then (tA)d = (xA
i )d = (em,A
i )d = em,A
i = xA
i =
(td)A. If td1, . . . , t
d
n are dual terms of t1, . . . , tn, respectivly and (td1)
A =
(tA1 )d, . . . , (tdn)A = (tAn )d, then ((t1∧ t2)
d)A = (td1∨ td2)
A = (td1)
A∨ (td2)
A =
(tA1 )d∨(tA2 )d = (tA1 ∧tA2 )d = ((t1∧t2)
A)d. For t1∨t2, t1 ⇔ t2, t1⊕t2,¬t1 the
corresponding equations can be proved similarly. If t = F (t1, . . . , tn), we
get ((F (t1, . . . , tn))d)A = (F d(td1, . . . , t
d
n))A = (F d)A((td1)
A, . . . , (tdn))A =
(FA)d((tA1 )d, . . . , (tAn )d) = (FA(tA1 , . . . , tAn ))d = (F (t1, . . . , tn)A)d.
Lemma 4.6. Let LA = {∧,∨,⇔,⊕,¬,0,1, fA, (fA)d} and let s, t be
terms using only operation symbols from LA. Let L
′A
⊆ LA be a subset,
then
A = ({0, 1}; L
′A
, fA) |= s ≈ t ⇐⇒ Ad = ({0, 1}; (L
′d
)A, (fA)d) |= sd ≈ td.
Proof. Let ϕ : {0, 1} → {0, 1} be given by ϕ(0) = 1 and ϕ(1) = 0, i.e.
ϕ = ¬ is the negation. Let fA
i ∈ L
′
. Since
ϕ((fA
i )d(x1, . . . , xn)) = ¬(fA
i )d(x1, . . . , xn) =
¬(¬fA
i (¬x1, . . . ,¬xn)) = fA
i (¬x1, . . . ,¬xn) =
fA
i (ϕ(x1), . . . , ϕ(xn))
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.80 Boolean Clones and Identities
and
ϕ((fA)d(x1, . . . , xn)) = ¬(fA)d(a1, . . . , an) =
¬(¬fA(¬x1, . . . ,¬xn)) = fA(¬x1, . . . ,¬xn) =
fA(ϕ(x1), . . . , ϕ(xn)),
ϕ has the properties of an isomorphism exchanging each operation by the
dual one. Since A ⊢ s ≈ t, then Ad ⊢ sd ≈ td and vice versa.
Corollary 4.7. (FBMod{s ≈ t})d = FBMod{sd ≈ td}.
Proof. Let (fA)d ∈ (FBMod{s ≈ t})d, then fA ∈ FBMod{s ≈ t}. From
Lemma 4.4 we get (fA)d ⊢ sd ≈ td. Therefore (fA)d ∈ FBMod{sd ≈ td},
i.e. (FBMod{s ≈ t})d ⊆ FBMod{sd ≈ td}.
Let fA ∈ FBMod{sd ≈ td}, then A = ({0, 1}; KA, fA) |= sd ≈
td. From Lemma 4.4 we get Ad = ({0, 1}; K
′A
, (fA)d) |= (sd)d ≈
(td)d = s ≈ t. Further (fA)d ∈ FBMod{s ≈ t}. Therefore ((fA)d)d ∈
(FBMod{s ≈ t})d. Hence fA ∈ (FBMod{s ≈ t})d, i.e. FBMod{sd ≈
td} ⊆ (FBMod{s ≈ t})d.
Proposition 4.8.
C1 = FBMod{1 ≈ 1},
C3 = FBMod{¬F (0) ≈ 1},
C2 = FBMod{F (1) ≈ 1},
C4 = FBMod{¬F (0) ∧ F (1) ≈ 1}.
Proof. Obviously, for C1, the equation 1 ≈ 1 is satisfied by all Boolean
operations fA since F does not occur in our equation. Since C3 = C1∩C3,
C2 = C1 ∩C2 and C4 = C3 ∩C2, then one can apply Lemma 4.1, Lemma
4.2 and Lemma 4.3, respectively.
We set x = (x1, . . . , xn). If xi ≤ yi for all 1 ≤ i ≤ n, where ≤ denotes
the usual order on the set {0, 1}, then we write x � y.
Proposition 4.9.
A1 = FBMod{F (x) ⇒ F (x ∨ y) ≈ 1},
A3 = FBMod{¬F (0) ∧ (¬F (x) ∨ F (x ∨ y)) ≈ 1},
A2 = FBMod{F (1) ∧ (¬F (x) ∨ F (x ∨ y)) ≈ 1},
A4 = FBMod{¬F (0) ∧ F (1) ∧ (¬F (x) ∨ F (x ∨ y)) ≈ 1}.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.R. Butkote, K. Denecke 81
Proof. Let fA ∈ A1 and let Σ = {F (x) ⇒ F (x ∨ y) ≈ 1}, then fA(x) ≤
fA(y) for every x � y. Assume fA(x) = 0, then (fA(x) ⇒ fA(x)∨ y)) =
(0 ⇒ fA(x)∨y)) = 1. Assume fA(x) = 1, then fA(x∨y) = 1 since fA is
monotone and x � x ∨ y. Moreover (fA(x) ⇒ fA(x ∨ y)) = 1. Therefore
fA ⊢ Σ.
Let fA ∈ FBModΣ, then (fA(x) ⇒ fA(x ∨ y)) = 1. Let x � y and
assume that fA(x) > fA(y), then fA(x) > fA(x ∨ y) since fA(x ∨ y) =
fA(y). Therefore fA(x) = 1 and fA(x ∨ y) = 0. Hence (fA(x) ⇒
fA(x ∨ y)) = 0 6= 1, a contradiction. Thus fA(x) ≤ fA(y). Therefore
fA ∈ A1.
Since A3 = A1 ∩ C3, A2 = A1 ∩ C2 and A4 = A2 ∩ C3, then we can
apply Lemma 4.1, Lemma 4.2 and Lemma 4.3, respectively.
For x = (x1, . . . , xn) we write x = (¬x1, . . . ,¬xn).
Proposition 4.10.
D3 = FBMod{F (x) ⊕ F (x) ≈ 1},
D1 = FBMod{¬F (0) ∧ (F (x) ⊕ F (x)) ≈ 1},
D2 = FBMod{(F (x) ⊕ F (x)) ∧ (¬F (x) ∨ F (x ∨ y)) ≈ 1}.
Proof. Let fA ∈ D3 and let Σ = {F (x) ⊕ F (x) ≈ 1}, then fA(x) =
fA(x1, . . . , xn) = ¬fA(¬x1, . . . ,¬xn) = ¬fA(x). Assume fA(x) = 0,
then ¬fA(x) = 0, i.e. fA(x) = 1. Therefore fA(x)⊕ fA(x) = 1. Assume
fA(x) = 1, then ¬fA(x) = 1, i.e. fA(x) = 0. Then fA(x) ⊕ fA(x) = 1.
Therefore fA ⊢ Σ.
Let fA ∈ FBModΣ, then fA(x) ⊕ fA(x) = 1 for every x ∈ {0, 1}n.
Assume fA(x) = 0, then 1 = fA(x) ⊕ fA(x) = 0 ⊕ fA(x). Therefore
fA(x) = 1, i.e. ¬fA(x) = 0. Hence fA(x) = ¬fA(x). Assume fA(x) = 1,
then 1 = fA(x) ⊕ fA(x) = 1 ⊕ fA(x). Now we get fA(x) = 0, i..e.
¬fA(x) = 1. Hence fA(x) = ¬fA(x). Therefore fA ∈ D3.
Since D1 = D3 ∩ C4 = D3 ∩ C3 and D2 = D3 ∩ A1, then the proof
can be given using Lemma 4.1 and Lemma 4.3, respectively.
Instead of x ∧ y we will also write xy.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.82 Boolean Clones and Identities
Proposition 4.11.
L1 = FBMod{1 ⊕ F (0) ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y) ≈ 1},
L3 = FBMod{1 ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y) ≈ 1},
L2 = FBMod{F (1) ∧ (1 ⊕ F (0) ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y) ≈ 1},
L4 = FBMod{F (1) ∧ (1 ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y) ≈ 1},
L5 = FBMod{(F (1) ⊕ F (0)) ∧ (1 ⊕ F (0) ⊕ F (x) ⊕ F (y) ⊕
F (x ⊕ y)) ≈ 1}.
Proof. Let fA ∈ L1 and let Σ = {1⊕F (0)⊕F (x)⊕F (y)⊕F (x⊕y) ≈ 1},
then there are a0, a1, . . . , an ∈ {0, 1} such that fA(x) = fA(x1, . . . , xn) =
a0 ⊕ a1x1⊕, . . . ⊕ anxn. If ai = 0, then aixi ⊕ aiyi = 0 ⊕ 0 = 0 =
0∧ (xi ⊕ yi) = ai ∧ (xi ⊕ yi). If ai = 1, then aixi ⊕ aiyi = (1xi)⊕ (1yi) =
xi⊕yi = 1∧(xi⊕yi) = ai∧(xi⊕yi). Therefore (aixi)⊕(aiyi) = ai(xi⊕yi).
Then 1 ⊕ fA(0) ⊕ fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y) = 1 ⊕ (a0 ⊕ a1x1 ⊕ . . . ⊕
anxn)⊕(a0⊕a1y1⊕. . .⊕anyn)⊕(a0⊕a1(x1⊕yn)⊕. . .⊕an(xn⊕yn)) = 1.
Therefore fA ⊢ Σ.
Let fA ∈ FBModΣ, then 1⊕ fA(0)⊕ fA(x)⊕ fA(y)⊕ fA(x⊕ y) = 1.
Assume that fA is essentially depending on n variables. If n = 0, then
fA is constant. Now we have that fA is linear. Suppose n ≥ 1. Let
α = (a1, . . . , an), β = (¬a1, a2, . . . , an) and e1 = (1, 0, . . . , 0). Since
fA ⊢ Σ, then 1 = 1⊕ fA(0)⊕ fA(α)⊕ fA(β)⊕ fA(α⊕ β) = 1⊕ fA(0)⊕
fA(α) ⊕ fA(β) ⊕ fA(e1). Therefore fA(α) = fA(β) iff fA(0) = fA(e1).
Since a1 is an essential variable, then there exist x2, . . . , xn ∈ {0, 1}n
such that fA(a1, x2, . . . , xn) 6= fA(¬a1, x2, . . . , xn). Therefore fA(0) 6=
fA(e1). Hence fA(α) 6= fA(β) for any a2, . . . , an ∈ {0, 1}n. Thus
fA(a1, . . . , an) = a1 ⊕ fA(0, a2, . . . , an). Applying the same argument
to the remaining variable we get fA(a1, . . . , an) = a1 ⊕ a2 ⊕ . . . ⊕ an ⊕
fA(0, . . . , 0). Therefore fA ∈ L1.
For the proof of the equations for L3 = L1 ∩ C3, L2 = L1 ∩ C2,
L4 = L1 ∩ C4, and L5 = L1 ∩ D3, we can apply Lemma 4.1, Lemma 4.2
and Lemma 4.3.
Proposition 4.12.
P6 = FBMod{F (x) ∧ F (y) ≈ F (x ∧ y)},
P3 = FBMod{¬F (0) ∧ (F (x) ∧ F (y) ⇔ F (x) ∧ F (y)) ≈ 1},
P5 = FBMod{F (1) ∧ (F (x) ∧ F (y) ⇔ F (x) ∧ F (y)) ≈ 1},
P1 = FBMod{¬F (0) ∧ F (1) ∧ (F (x) ∧ F (y)) ⇔ F (x) ∧ F (y)) ≈ 1}.
Proof. Let fA ∈ P6 and let Σ = {F (x)∧F (y) ≈ F (x∧ y)}. If fA is con-
stant, then fA ⊢ Σ. If fA ∈ P6/ {0,1}, then fA(x) = fA(x1, . . . , xn) =
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.R. Butkote, K. Denecke 83
x1 ∧ . . .∧ xn. Assume fA(x∧ y) = 0, then (x1 ∧ y1)∧ . . .∧ (xn ∧ yn) = 0.
Then there exists xi ∧ yi = 0 for some i ∈ {1, . . . , n}. Therefore from
xi = 0∨yi = 0 it follows fA(x)∧fA(y) = (x1∧. . .∧xn)∧(y1∧. . .∧yn) = 0.
Thus fA(x) ∧ fA(y) = fA(x ∧ y). Assume fA(x ∧ y) = 1, now we get
(x1 ∧ y1) ∧ . . . ∧ (xn ∧ yn) = 1. Then xi = yi = 1 for all i ∈ {1, . . . , n}.
Therefore fA(x) = x1 ∧ . . .∧ xn = 1 and fA(y) = y1 ∧ . . .∧ yn = 1. Thus
(fA(x) ∧ fA(y)) = fA(x ∧ y). Therefore fA ⊢ Σ.
Let fA ∈ FBModΣ, then fA(x) ∧ fA(y) = fA(x ∧ y). Assume fA is
not constant. Let x � y, then xi ∧ yi = xi for all i ∈ {1, . . . , n}. Now we
have fA(x∧y) = fA(x). Therefore fA(x)∧fA(y) = fA(x). If fA(x) = 1,
then fA(y) = 1. Therefore fA(x) ≤ fA(y). Hence fA is monotone.
Let B =
{
x ∈ {0, 1}n | fA(x) = 1 ∧ ∀ y (y ≺ x ⇒ fA(y) = 0)
}
. We
will show that |B| = 1. Assume that |B| > 1. We have a, b ∈ B, a 6= b,
and then fA(a) = 1 and fA(b) = 1. Since a 6= b, a ⊀ b and b ⊀ a, then
there exist i, j ∈ {1, . . . , n} and i 6= j such that ai > bi and bj > aj .
Then ai ∧ bi = bi < ai and aj ∧ bj = aj . Consider k ∈ {1, . . . , n}
such that k 6= i, j. If ak = bk, then ak ∧ bk = ak. If ak 6= bk, then
ak ∧ bk = 0 ≤ ak. Therefore a ∧ b ≺ a. Further fA(a ∧ b) = 0. Therefore
fA(a) ∧ fA(b) 6= fA(a ∧ b), a contradiction. Therefore |B| ≤ 1.
Assume |B| = φ, then there is no x ∈ {0, 1}n such that fA(x) = 1 or
if there is an x such that fA(x) = 1, then there is a y with y ≺ x and
fA(y) = 1.
If there is no x ∈ {0, 1}n such that fA(x) = 1, then fA(x) = 0 for all
x ∈ {0, 1}n. Therefore fA is constant 0, a contradiction.
If there is an x such that fA(x) = 1, then there is a y with y ≺ x and
fA(y) = 1. Assume y = 0, then fA(0) = 1. Therefore fA is constant 1,
a contradiction.
Assume y 6= 0, now we have fA(y) = 1 and since |B| = φ, then
there exists z1 with z1 ≺ y and fA(z1) = 1. If z1 = 0, then fA(0) = 1.
Therefore fA is constant 1, a contradiction. If z1 6= 0, then there exists
z2 with z2 ≺ z1 and fA(z2) = 1 otherwise z2 ∈ B. Applying the same
argument then we get the chain zk ≺ zk−1 ≺, . . . ,≺ z1 ≺ y for some
k. Since this chain is finite, then zk = 0. Therefore fA is constant 1, a
contradiction. Therefore |B| 6= φ. Hence |B| = 1.
Hence fA is monotone and has the property |B| = 1. Since fA is
not constant 0, then fA(1) = 1. Therefore B = {1}. Hence fA(x) = 0
for all x 6= 1. Therefore fA(x) = fA(x1, . . . , xn) = x1 ∧ . . . ∧ xn. Since
P3 = P6∩C3, P5 = P6∩C2 and P1 = P6∩C4, then one can apply Lemma
4.1, Lemma 4.2 and Lemma 4.3.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.84 Boolean Clones and Identities
Proposition 4.13.
S6 = FBMod{F (x) ∨ F (y) ≈ F (x ∨ y)},
S5 = FBMod{¬F (0) ∧ ((F (x) ∨ F (y)) ⇔ F (x ∨ y))) ≈ 1},
S3 = FBMod{F (1) ∧ ((F (x) ∨ F (y)) ⇔ F (x ∨ y))) ≈ 1},
S1 = FBMod{¬F (0) ∧ F (1) ∧ ((F (x) ∨ F (y)) ⇔ F (x ∨ y))) ≈ 1}.
Proof. Since S6 = (P6)
d, then by Corollary 4.5 S6 = FBMod{F (x) ∨
F (y) ≈ F (x ∨ y)}.
Since S5 = S6 ∩ C3, S3 = S6 ∩ C2 and S1 = S6 ∩ C4, one can apply
lemmas 4.1, 4.2 and 4.3.
Let xi be the n-tuple xi = (xi1 , . . . , xin).
Proposition 4.14. For each µ ≥ 2,
Fµ
8 = FBMod{
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1 ∧ y) ≈ 1},
Fµ
5 = FBMod{F (1) ∧ (
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1 ∧ y)) ≈ 1},
Fµ
7 = FBMod{
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1) ∧ F (x1 ∨ x2) ≈ 1},
Fµ
6 = FBMod{F (1) ∧ (
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1) ∧
F (x1 ∨ x2)) ≈ 1}.
Proof. Let fA ∈ Fµ
8 and let Σ = {
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1∧y) ≈
1}, then for any α1, . . . , αµ ∈ {0, 1}n : if fA(α1) = · · · = fA(αµ) = 1,
then α1 ∧ . . . ∧ αµ 6= (0, . . . , 0). Assume fA(α1) = · · · = fA(αµ−1) =
1, and let β = α1 ∧ . . . ∧ αµ−1 ∧ αµ, then β ∧ (α1 ∧ . . . ∧ αµ−1) =
α1 ∧ . . . ∧ αµ−1∧αµ∧(α1∧. . .∧αµ−1) = (0, . . . , 0). Therefore by the con-
trapositive of the implication which defines the elements from Fµ
8 we get
fA(β) = 0. Then fA(α1)∧. . .∧fA(αµ−1) ⇒ ¬fA(α1 ∧ . . . ∧ αµ−1∧αµ) =
1. If there exists αi such that fA(αi) = 0 for some i ∈ {1, . . . , µ − 1},
then fA(α1)∧. . .∧fA(αµ−1) ⇒ ¬fA(α1 ∧ . . . ∧ αµ−1∧αµ) = 1. Therefore
fA ⊢ Σ.
Let fA ∈ FBModΣ, then
µ−1
∧
i=1
fA(xi) ⇒ ¬fA(x1 ∧ . . . ∧ xµ−1 ∧ xµ) =
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.R. Butkote, K. Denecke 85
1. Assume fA(0) 6= 0, i.e. fA(0) = 1. Since
µ−1
∧
i=1
fA(0) = 1 and
¬fA(0 ∧ . . . ∧ 0 ∧ 0) = ¬fA(0) = ¬1 = 0, then
µ−1
∧
i=1
fA(0) ⇒
¬fA(0 ∧ . . . ∧ 0 ∧ 0) = 0, a contradiction. Therefore fA(0) = 0.
Let α1, . . . , αµ ∈ {0, 1}n such that fA(α1) = . . . = fA(αµ) = 1.
Because of (fA(α1)∧. . .∧fA(αµ−1)) ⇒ ¬fA(α1 ∧ . . . αµ−1∧x) = 1 for all
x ∈ {0, 1}n we have ¬fA(α1 ∧ . . . αµ−1 ∧ αµ) = 1, i.e fA(α1 ∧ . . . αµ−1 ∧
αµ) = 0. Assume (α1 ∧ . . .∧αµ−1)∧αµ = 0, then α1 ∧ . . . ∧ αµ−1 ∧αµ =
αµ. Therefore fA(αµ) = fA(α1 ∧ . . . αµ−1 ∧ αµ) = 0, a contradiction.
Hence (α1 ∧ . . . αµ−1) ∧ αµ 6= 0. Therefore fA ∈ Fµ
8 .
Since Fµ
5 = Fµ
8 ∩ C4, Fµ
7 = Fµ
8 ∩ A1, Fµ
6 = Fµ
8 ∩ A4, one can apply
Lemma 4.3.
Proposition 4.15. For each µ ≥ 2,
Fµ
4 = FBMod{
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1 ∨ y) ≈ 1},
Fµ
1 = FBMod{¬F (0) ∧ (
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1 ∨ y)) ≈ 1},
Fµ
3 = FBMod{
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1) ∧ ¬F (x1 ∧ x2) ≈ 1},
Fµ
2 = FBMod{¬F (0) ∧ (
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1) ∧
¬F (x1 ∧ x2)) ≈ 1}.
Proof. Let fA ∈ Fµ
4 and let σ = {
µ−1
∧
i=1
¬F (xi) ⇒ ¬F (x1 ∨ . . . ∨ xµ−1 ∨
y) ≈ 1}, then for any α1, . . . , αµ ∈ {0, 1}n : if fA(α1) = · · · = fA(αµ) =
0, then α1 ∨ . . . ∨ αµ 6= (1, . . . , 1). If fA(α1) = . . . = fA(αµ−1) = 0,
we get ¬fA(αi) = 1 for all i ∈ {0, 1}n. Let β = α1 ∨ . . . ∨ αµ−1 ∨
αµ, then β ∨ (α1 ∨ . . . ∨ αµ−1) = (α1 ∨ . . . ∨ αµ−1 ∨ αµ) ∨ (α1 ∨ . . . ∨
αµ−1) = (1, . . . , 1) ∨ αµ = (1, . . . , 1). Then by the contrapositive of the
implication which defines the elements from Fµ
4 we get fA(β) = 1, i.e.
we have fA(β) = fA(α1 ∨ . . . ∨ αµ−1 ∨ αµ) = 1. Then ¬fA(α1) ∨ . . . ∨
¬fA(αµ−1) ⇒ fA(α1 ∨ . . . ∨ αµ−1 ∨ αµ) = 1. If there exists αi such
that fA(αi) = 1 for some i ∈ {1, . . . , µ − 1}, then ¬fA(αi) = 0. Thus
¬fA(α1) ∧ . . . ∧ ¬fA(αµ−1) ⇒ fA(α1 ∨ . . . ∨ αµ−1 ∨ αµ) = 1. Therefore
fA ⊢ Σ.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.86 Boolean Clones and Identities
Let fA ∈ FBModΣ, then
µ−1
∧
i=1
¬fA(xi) ⇒ fA(x1 ∨ . . . ∨ xµ−1 ∨ xµ) =
1. Assume fA(1) 6= 1, i.e. fA(1) = 0, then
µ−1
∧
i=1
¬fA(1) ⇒ fA(1 ∨ . . . ∨ 1∨
1) = 0, a contradiction. Therefore fA(1) = 1.
Let α1, . . . , αµ ∈ {0, 1}n such that fA(α1) = . . . = fA(αµ) = 0. Then
¬fA(αi) = 1 for all i ∈ {1, . . . , µ}. Therefore ¬fA(α1)∧ . . .∧¬fA(αµ−1)
⇒ fA(α1 ∨ . . . αµ−1 ∨ x) = 1 for all x ∈ {0, 1}n. This gives
fA(α1 ∨ . . . αµ−1 ∨ αµ) = 1.
Assume (α1 ∨ . . . ∨ αµ−1) ∨ αµ = 1, then α1 ∨ . . . ∨ αµ−1) ∨ αµ = αµ.
Therefore fA(αµ) = fA(α1 ∨ . . . αµ−1)∨αµ) = 1, a contradiction. Hence
(α1 ∨ . . . ∨ αµ−1) ∨ αµ 6= 1. Therefore fA ∈ Fµ
4 .
Since Fµ
1 = Fµ
4 ∩ C4, Fµ
3 = Fµ
4 ∩ A1, and Fµ
2 = Fµ
4 ∩ A4, one can
apply Lemma 4.3.
Proposition 4.16. O9 = FBMod{((F (x) ⇔ F (y)) ⇒ (F (x ⇔ F (x ∧
y))) ∧ (1 ⊕ F (0) ⊕ F (y) ⊕ F (x ⊕ y)) ≈ 1}.
Proof. Let fA ∈ O9 and let Σ = {((F (x) ⇔ F (y)) ⇒ (F (x ⇔ F (x∧y)))∧
(1 ⊕ F (0) ⊕ F (y) ⊕ F (x ⊕ y)) ≈ 1}. If fA is the constant, then fA ⊢ Σ.
If fA is the identity mapping, then ((fA(x) ⇔ fA(y)) ⇒ (fA(x) ⇔
fA(x ∧ y)) = ((x ⇔ y) ⇒ (x ⇔ (x ∧ y))) = ((x ⇔ y) ⇒ (x ⇔ (x ∧ y)))
and this is a tautology. Since 1 ⊕ fA(0) ⊕ fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y) =
1 ⊕ 0 ⊕ x ⊕ y ⊕ (x ⊕ y) = 1, then ((fA(x) ⇔ fA(y)) ⇒ (fA(x) ⇔
fA(x ∧ y)) ∧ (1 ⊕ fA(0) ⊕ fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y)) = 1. If fA is the
negation, then ((fA(x) ⇔ fA(y)) ⇒ (fA(x) ⇔ fA(x∧ y))∧ (1⊕ fA(0)⊕
fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y)) = ((y ⇔ x) ⇒ (y ⇔ ¬(x ∧ y))) ∧ (1 ⊕ 1 ⊕
y ⊕ x⊕¬(x⊕ y)) = ((y ⇔ x) ⇒ (y ⇔ (y ∨ x)))∧ (y ⊕ x⊕¬(x⊕ y)) = 1.
Therefore fA ⊢ Σ.
Let fA ∈ FBModΣ, then ((fA(x) ⇔ fA(y)) ⇒ (fA(x) ⇔ fA(x ∧
y)) ∧ (1 ⊕ fA(0) ⊕ fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y)) = 1. Then 1 ⊕ fA(0) ⊕
fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y) = 1. Therefore fA is linear.
Next we will show that fA depends essentially on at most one vari-
able. If fA does not depend on any varaiable, then fA is the constant
0 or 1. Then fA ∈ O9. If fA is essentially depending on one vari-
able, then fA ∈ {x,¬x}. Then fA ∈ O9. Assume fA depends es-
sentially on more than one variable, i.e. fA has at least two essen-
tial variables. Let x1, x2 be essential variables of fA, then fA(x) =
fA(x1, . . . , xn) = x1 ⊕x2 ⊕ fA(0, 0, x3, . . . , xn). Let α = (0, 1, x3, . . . , xn)
and β = (1, 0, x3, . . . , xn), then fA(α) = 0 ⊕ 1 ⊕ fA(0, 0, x3, . . . , xn) =
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.R. Butkote, K. Denecke 87
1 ⊕ 0 ⊕ fA(0, 0, x3, . . . , xn) = fA(β). Therefore fA(α) = fA(β). Since
fA ⊢ Σ, then (fA(α) ⇔ fA(β)) ⇒ (fA(α) ⇔ fA(α ∧ β)) = 1. Therefore
fA(α) = fA(α∧β). Since fA(α∧β) = fA(0∧1, 1∧0, x3∧x3, . . . , xn∧xn) =
fA(0, 0, x3, . . . , xn) = ¬fA(α), then fA(α) 6= fA(α∧β) = ¬fA(α), a con-
tradiction. Therefore fA depends essentially on one variable.
Proposition 4.17. O4 = FBMod{(F (0) ⊕ F (1)) ∧ ((F (x) ⇔ F (y)) ⇒
(F (x) ⇔ F (x ∧ y))) ∧ (1 ⊕ F (0) ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y)) ≈ 1}.
Proof. Let fA ∈ O4 and let Σ = {(F (0) ⊕ F (1)) ∧ ((F (x) ⇔ F (y)) ⇒
(F (x) ⇔ F (x ∧ y))) ∧ (1 ⊕ F (0) ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y)) ≈ 1}, then
fA ⊢ ((F (x) ⇔ F (y)) ⇒ (F (x ⇔ F (x ∧ y))) ∧ (1 ⊕ F (0) ⊕ F (x) ⊕
F (y) ⊕ F (x ⊕ y)) ≈ 1}. Since fA is the identity or the negation, then
fA(0) ⊕ fA(1) = 1. Further (fA(0) ⊕ fA(1)) ∧ ((fA(x) ⇔ fA(y)) ⇒
(fA(x) ⇔ fA(x ∧ y))) ∧ (1 ⊕ fA(0) ⊕ fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y)) = 1.
Therefore fA ⊢ Σ.
Let fA ∈ FBModΣ, then (fA(0) ⊕ fA(1)) ∧ ((fA(x) ⇔ fA(y)) ⇒
(fA(x ⇔ fA(x ∧ y))) ∧ (1 ⊕ fA(0) ⊕ F (x) ⊕ fA(y) ⊕ fA(x ⊕ y)) = 1.
Now we get fA(0) ⊕ fA(1) = 1 and ((fA(x) ⇔ fA(y)) ⇒ (fA(x) ⇔
fA(x ∧ y))) ∧ (1 ⊕ fA(0) ⊕ fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y)) = 1. Then
fA ∈ O9. Since fA(0) ⊕ fA(1) = 1, then fA ∈ {x,¬x}.
Proposition 4.18. O8 = FBMod{(F (x) ⇒ F (x) ∨ y)) ∧ (1 ⊕ F (0) ⊕
F (x) ⊕ F (y) ⊕ F (x ⊕ y)) ≈ 1}.
Proof. Let fA ∈ O8 and let Σ = {(F (x) ⇒ F (x)∨y))∧(1⊕F (0)⊕F (x)⊕
F (y) ⊕ F (x ⊕ y)) ≈ 1}. Since O8 ⊆ A1 and O8 ⊆ L1 , then fA(x) ⇒
fA(x∨ y) = 1 and 1⊕ fA(0)⊕ fA(x)⊕ fA(y)⊕ fA(x⊕ y) = 1. Therefore
(fA(x) ⇒ fA(x ∨ y)) ∧ (1 ⊕ fA(0) ⊕ fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y)) = 1.
Hence fA ⊢ Σ.
Let fA ∈ FBModΣ, then (fA(x) ⇒ fA(x∨y))∧ (1⊕fA(0)⊕fA(x)⊕
fA(y) ⊕ fA(x ⊕ y)) = 1. Therefore fA(x) ⇒ fA(x ∨ y) = 1 and 1 ⊕
fA(0) ⊕ fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y) = 1. Hence fA ∈ A1 and fA ∈ L1.
Thus fA ∈ {0,1, x}.
Proposition 4.19. O6 = FBMod{(F (x) ⇒ F (x ∨ y)) ∧ (1 ⊕ F (x) ⊕
F (y) ⊕ F (x ⊕ y)) ≈ 1}.
Proof. Let fA ∈ O6 and let Σ = {(F (x) ⇒ F (x ∨ y)) ∧ (1 ⊕ F (x) ⊕
F (y) ⊕ F (x ⊕ y)) ≈ 1}. If fA is the constant, then fA ⊢ Σ. If fA
is the identity, then fA(x) ⇒ fA(x ∨ y) = x ⇒ (x ∨ y) = 1 and 1 ⊕
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.88 Boolean Clones and Identities
fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y) = 1 ⊕ x ⊕ y ⊕ (x ⊕ y) = 1. Then (fA(x) ⇒
fA(x ∨ y)) ∧ (1 ⊕ fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y)) = 1. Therefore fA ⊢ Σ.
Let fA ∈ FBModΣ, then (fA(x) ⇒ fA(x∨y))∧ (1⊕fA(x)⊕fA(y)⊕
fA(x ⊕ y)) = 1. Thus fA(x) ⇒ fA(x ∨ y) = 1 and 1 ⊕ fA(x) ⊕ fA(y) ⊕
fA(x ⊕ y) = 1. Therefore fA ∈ A1 and fA ∈ L3. Hence fA ∈ O6.
Proposition 4.20. O5 = FBMod{F (1)∧(F (x) ⇒ F (x∨y))∧(1⊕F (0)⊕
F (x) ⊕ F (y) ⊕ F (x ⊕ y)) ≈ 1}.
Proof. Let fA ∈ O5 and let Σ = {F (1) ∧ (F (x) ⇒ F (x ∨ y)) ∧ (1 ⊕
F (0) ⊕ F (x) ⊕ F (y) ⊕ F (x ⊕ y)) ≈ 1}. If fA is the constant 1, then
fA ⊢ Σ. If fA is the identity, then fA(1) = 1 and (fA(x) ⇒ fA(x∨ y))∧
(1 ⊕ fA(0) ⊕ fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y)) = 1. Then fA(1) ∧ (fA(x) ⇒
fA(x ∨ y)) ∧ (1 ⊕ fA(0) ⊕ fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y)) = 1 ∧ 1 ∧ 1 = 1.
Therefore fA ⊢ Σ.
Let fA ∈ FBModΣ, then fA(1)∧ (fA(x) ⇒ fA(x∨y))∧ (1⊕fA(0)⊕
fA(x)⊕fA(y)⊕fA(x⊕y)) = 1. ThenfA(1) = 1, fA(x) ⇒ fA(x∨y) = 1
and 1 ⊕ fA(0) ⊕ fA(x) ⊕ fA(y) ⊕ fA(x ⊕ y) = 1. Therefore fA ∈ C2,
fA ∈ A1 and fA ∈ L3. Hence fA ∈ O6
Proposition 4.21. O1 = FBMod{F (1) ∧ (F (x) ⇒ F (x ∨ y)) ∧ (1 ⊕
F (x) ⊕ F (y) ⊕ F (x ⊕ y)) ≈ 1}.
Proof. Let fA ∈ O1 and let {F (1)∧(F (x) ⇒ F (x∨y))∧(1⊕F (x)⊕F (y)⊕
F (x⊕ y)) ≈ 1}, then fA(1) = 1 and (fA(x) ⇒ fA(x∨ y))∧ (1⊕ fA(x)⊕
fA(y)⊕fA(x⊕y)) = 1. Then fA(1)∧(fA(x) ⇒ fA(x∨y))∧(1⊕fA(x)⊕
fA(y) ⊕ fA(x ⊕ y)) = 1. Therefore fA ⊢ Σ. Let fA ∈ FBModΣ, then
fA(1)∧(fA(x) ⇒ fA(x∨y))∧(1⊕fA(x)⊕fA(y)⊕fA(x⊕y)) = 1. Then
fA(1) = 1 and fA(x) ⇒ fA(x∨y))∧(1⊕fA(x)⊕fA(y)⊕fA(x⊕y)) = 1.
Therefore fA ∈ C2 and fA ∈ O6. Assume fA(0) 6= 0, i.e. fA(0) = 1,
then 1⊕fA(0)⊕fA(1)⊕fA(0⊕1) = 0, a contradiction. Then fA(0) = 0.
Therefore fA ∈ O1.
Proposition 4.22.
F∞
8 =FBMod{
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1 ∧ y)) ≈ 1 | µ ≥ 2},
F∞
5 =FBMod{F (1) ∧ (
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1 ∧ y)) ≈ 1
| µ ≥ 2},
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.R. Butkote, K. Denecke 89
F∞
7 =FBMod{
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1) ∧ F (x1 ∨ x2) ≈ 1
| µ ≥ 2},
F∞
6 =FBMod{F (1) ∧ (
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1)
∧ F (x1 ∨ x2)) ≈ 1 | µ ≥ 2}.
Proof. Let fA ∈ F∞
8 and let Σ = {
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1 ∧
y)) ≈ 1 | µ ≥ 2}. Since
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1 ∧ y)) ≈ 1 is
satisfied by any operation from Fµ
8 for all µ ≥ 2 and fA ∈ F∞
8 =
⋂
µ≥2
Fµ
8 ,
then fA ⊢
µ−1
∧
i=1
F (xi) ⇒ ¬F (x1 ∧ . . . ∧ xµ−1 ∧ y)) ≈ 1 for all µ ≥ 2.
Therefore fA ⊢ Σ.
Let fA ∈ FBModΣ, then
µ−1
∧
i=1
fA(xi) ⇒ ¬fA(x1 ∧ . . . ∧ xµ−1∧y)) = 1
for all µ ≥ 2. Therefore fA ∈ Fµ
8 for all µ ≥ 2. Hence fA ∈
⋂
µ≥2
Fµ
8 = F∞
8 .
Since F∞
5 = F∞
8 ∩ A4, F∞
7 = F∞
8 ∩ A1, and F∞
6 = F∞
8 ∩ A4, then one
can apply Lemma 4.3.
Proposition 4.23.
F∞
4 = FBMod{
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1 ∨ y)
≈ 1 | µ ≥ 2},
F∞
1 = FBMod{¬F (0) ∧ (
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1 ∨
y)) ≈ 1 | µ ≥ 2},
F∞
3 = FBMod{
µ−1
∧
i=1
¬F (xi) ⇒ ¬F (x1 ∨ . . . ∨ xµ−1) ∧ ¬F (x1
∧x2) ≈ 1 | µ ≥ 2},
F∞
2 = FBMod{¬F (0) ∧ (
µ−1
∧
i=1
¬F (xi) ⇒ F (x1 ∨ . . . ∨ xµ−1) ∧
¬F (x1 ∧ x2)) ≈ 1 | µ ≥ 2}.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.90 Boolean Clones and Identities
The proof is similar to the proof of Proposition 4.22.
References
[1] K. Denecke and S. L. Wismath, Hyperidentities and Clones, Gordon and Breach
Science Publishers, 2000.
[2] K. Denecke and S. L.Wismath, Universal Algebra and Applications in Theoretical
Computer Science, Chapman and Hall/CRC, 2002.
[3] O. Ekins, S. Foldes, P. L. Hammer, L. Hellerstein, Equational Theories of Boolean
Functions, RUTCOR Research Report, RRR 6-98, February 1998.
[4] S. Foldes and G. R. Pogosyan, Post Class Characterized by Functional Terms,
RRR-RUTCOR Research Report, Rutgers University Center for Operation Re-
search, 2000.
[5] E. L. Post, Introduction to a General Theory of Elementary propositions, Amer.
J. Math. 43(1921).
[6] E. L. Post, The two-valued iterative systems of mathematical logic, Ann. Math.
Studies 5, Princeton Univ. Press, 1941.
Contact information
R. Butkote University of Potsdam, Institute of Math-
ematics, 14415 Potsdam, Germany, Am
Neuen Palais 10
E-Mail: unique1st@hotmail.com
URL: www.users.math.uni-potsdam.de
K. Denecke University of Potsdam, Institute of Math-
ematics, 14415 Potsdam, Germany, Am
Neuen Palais 10
E-Mail: kdenecke@rz.uni-potsdam.de
URL: www.users.math.uni-potsdam.de
|