Kudryavtsev V.B., Rosenberg I.G. Structural Theory of Automata, Semigroups, and Universal Algebra

Подождите немного. Документ загружается.

Completeness of automaton mappings 93

3.2 Results on completeness with respect to congruences

In this subsection we discuss completeness with respect to the congruence relations deter-

mined in the preceding subsection.

By the deﬁnition of σ

, σ

-completeness coincides with “classical” completeness. There-

fore we can refer to Section 2.3.

By the deﬁnition of σ

-completeness, we immediately get the following results.

3.4 Theorem

(1) Any non-empty subalgebra of F is a σ

-algebra.

(2) Any non-empty subset of F is σ

-complete.

(3) ∅ is the only σ

-maximal subalgebra.

(4) The σ

-completeness of a ﬁnite subset of F is decidable.

By the deﬁnition of σ

-completeness, a set M is complete if and only if, for any n ∈ N,it

contains at least one n-ary function. From an arbitrary m-ary function F , for any m



<mand

any m



>m, we can obtain an m



-ary function by identiﬁcation of inputs (i.e. by application

of operation ∆ sometimes) and an m



-ary function by application of ∇ sometimes. Thus M

is σ

-complete if and only if M contains at least one function. Therefore M is σ

-complete

iﬀ M is σ

-complete. Thus we get the following statements from Theorem 3.4.

3.5 Theorem

(1) Any non-empty subalgebra of F is a σ

-algebra.

(2) Any non-empty subset of F is σ

-complete.

(3) ∅ is the only σ

-maximal subalgebra.

(4) The σ

-completeness of a ﬁnite subset of F is decidable.

We now discuss σ

-completeness where t ∈ N. We start with a deﬁnition which extends

-equivalence to sets.

3.6 Deﬁnition Let t ∈ N.WesaythattwosetsM and M



are σ

-equivalent if and only if,

for any two functions F ∈ M and F



∈ M



, there are functions G ∈ M



and G



∈ M such

that (F, G) ∈ σ

and (F



) ∈ σ

First we show that we can restrict ourselves to the algebra F



, i.e., we do not have to take

into consideration the feedback operation.

3.7 Theorem For any set M ⊂Fand any t ∈ N, [M] and M are σ

-equivalent.

Proof Let F



∈M.SinceM



= M is a subset of [M ], we obtain F



∈ [M ]. Choosing



= F



,wegetG



∈ [M]and(G



) ∈ σ

, which proves that G



satisﬁes the requirements

of Deﬁnition 3.6.

94 J. Dassow

In order to show the other statement we prove that, for any t ∈ N and any sequential

function F , the function

= F ◦ (F ◦ (...(F



 

t−1 times

◦F ) ...))

is σ

-equivalent to ↑ F . Using this construction instead of the feedback operation we obtain

for any F ∈ [M] the corresponding G ∈M .

Let t =1. SinceF depends in a delayed fashion on its ﬁrst variable, F and ↑ F are

-equivalent. Thus the statement holds for t =1.

Let t ≥ 2. Obviously we have ↑ F = F ◦↑F since we use the same input for the ﬁrst

variable. If we also take into consideration that F depends in a delayed fashion on its ﬁrst

variable we obtain that F and F

are σ

-equivalent.

Choosing G = F

, we satisfy the requirements of Deﬁnition 3.6. 2

3.8 Theorem For any t ∈ N, there is a mapping τ

: F→P

such that M ⊂Fis σ

complete if and only if τ

(M)={τ

(F ) | F ∈ M} generates τ

(F).

Proof Obviously, it is suﬃcient to study the behaviour of the sequential functions at the

ﬁrst t moments. Thus it is suﬃcient to consider words of length at most t. Further, the value

F (q

,...,q

)whereq

is a preﬁx of p

for 1 ≤ i ≤ n is determined by the corresponding

preﬁx of F (p

,...,p

). Thus it is suﬃcient to consider only F (p

,...,p

)where,for

1 ≤ i ≤ n, p

is a word of length t.

Now we interpret a word p = x

...x

of length t over {0, 1} as a binary representation

of a natural number ϕ(p) ∈{0, 1,...,2

− 1}.ThenwithF ∈F

we can associate the

function τ

(F ) ∈ P

where

(F )(z

,...,z

)=ϕ(F(ϕ

−1

),ϕ

−1

),...,ϕ

−1

)).

For a set M ∈F,weset

(M)={τ

(F ) | F ∈ M}.

It is easy to see that, for any functions F and G,

α(τ

(F )) = τ

(α(F )) for α ∈{ζ,η,∆, ∇}, (3.1)

(F ) ◦ τ

(G)=τ

(F ◦ G). (3.2)

Thus

(M)=τ

(M).

The statement now follows. 2

By Theorem 3.8 we have reduced σ

-completeness to the generation of the special set τ

(F)

of functions over a set of 2

elements by such functions. We note that τ

(F)isnotP

.We

consider a unary function F .ThenF (x

...x

)=y

...y

implies F (x



...x



...y



), i.e., the value τ

(F ) cannot be chosen arbitrarily on ϕ(x



...x



Obviously, for any t ∈ N, {F

(non)

(et)

(vel)

(id;1)

} is a ﬁnite σ

-complete set. From the

general statements of universal algebra, we obtain the following criterion.

Completeness of automaton mappings 95

3.9 Theorem Let t ∈ N. M ⊆Fis σ

-complete if and only if M is not contained in any

-maximal subalgebra of F.

Without proof we give the following statement.

3.10 Theorem For any t ∈ N, there is a ﬁnite number of σ

-maximal subalgebras.

It is well-known that the maximal subalgebras of P

, k ≥ 2, can be described by relations.

Since the σ

-completeness corresponds to the generation of a subset of P

one can expect

that the σ

-maximal subalgebras can be described by relations, too. Therefore we recall this

concept.

Let t ∈ N.LetR be a k-ary relation on {0, 1}

. We say that the n-ary sequential

function F preserves the relation R if, for any words p

∈{0, 1}

,1≤ i ≤ k,1≤ j ≤ n,

,...p

) ∈ R for 1 ≤ j ≤ n implies

(F (p

,...,p

),F(p

,...,p

),...,F(p

,...,p

)) ∈ R.

(This requirement can be interpreted as follows: Consider the words p

as elements of a

(k, n)-matrix. If the columns of the matrix belong to R, then the vector formed by the values

obtained by applying F to the rows belongs to R, too.) For a given relation R,letM (R)be

the set of all sequential functions preserving R.

In [3], for any t ∈ N and any σ

-maximal subalgebra M , Buevic has given a relation R such

that M = M(R). Since we can check whether or not a function preserves a given relation,

the result by Buevic and Theorem 3.9 lead to an algorithm to decide the σ

-completeness of

a given ﬁnite set.

This decidability is stated in the following theorem. However, since the complete proof

of the Buevic result is very long (more than 100 pages) and cannot be given here, we give an

alternative proof of the decidability of σ

-completeness, especially, because this method can

be used in many other cases, too.

3.11 Theorem For any t ∈ N,theσ

-completeness of a ﬁnite subset of F is decidable.

Proof For any set N ⊆ P

,let

U(N)={f | f = α(h ◦ h



),f∈ P

,h∈ N, h



∈ N ∪{id},

α is a composition of ζ,η,∆, ∇}.

Using the empty composition for α and h



= id, we reproduce h.ThusN ⊆ U(N). For any

N, U(N) ⊆ P

, and thus U(N )containsatmostk

elements. Moreover, if N is ﬁnite, then

U(N) can algorithmically be determined.

Further we set

H = {τ

(non)

),τ

(et)

),τ

(vel)

),τ

)}.

Note that H = τ

(F).

We consider the following algorithm which takes an arbitrary ﬁnite set M ⊂Fas input:

96 J. Dassow

:= ∅;

= U(τ

(M));

A: if N

= N

then goto B ;

:= N

;

:= U(N

);

goto A;

B: if H ⊂ N

then Output: “M is σ

-complete.” ;

Output: “M is not σ

-complete.”

The algorithm produces the sequence

= U(τ

(M),M

= U (U(τ

(M))),M

= U(U(U (τ

(M))),M

= U(U(U (U(τ

(M)))),...

Since M

⊆ M

i+1

⊆ P

for i ≥ 1, there is a j, j ≥ 1 such that M

= M

j+1

.Thusthe

condition in row A is satisﬁed after some steps and we continue with row B.

Moreover, for i ≥ 1, M

⊆ τ

(M) is valid and hence

= τ

(M) ∩P

If the condition in row B is satisﬁed, then

(F)=H⊆M

⊆τ

(M) ⊆ τ

(F)

for some j, j ≥ 1, which implies τ

(M)=τ

(F). By Theorem 3.8, M is σ

-complete. On

the other hand, if H is not a subset of τ

(M) ∩ P

,thenM cannot be complete. 2

4 Kleene-completeness

In the preceding section we considered equivalence relations which are important from the

algebraic point of view. Now we consider an equivalence relation which is based on the fact

that automata or sequential functions can be used as acceptors for languages.

4.1 Deﬁnition AsetL of words over X is called regular if and only if L can be obtained

from ∅ and {x},wherex ∈ X, by iterated application of union, product and Kleene-closure.

As an example, we mention that, for 1 ∈ X, X

∗

{1}{1} is regular.

Now we introduce a notion of acceptance of a language by a sequential function.

4.2 Deﬁnition Let F : X

∗

→ Y

∗

be a sequential function and ∅⊂Y



⊂ Y . Then the

language T (F, Y



) accepted by F and Y



is deﬁned as the set of all words p such that F(p)=



y with y ∈ Y



Intuitively, we accept a word p of length t if taking p as input the output at the moment

t is an element of Y



4.3 Example We consider the function F of Example 2.2. Then the output 1 is produced at

the moment t if and only if the input at the moments t −1andt was 1. Therefore T(F, {1})

is the set of all words ending with two 1’s or formally

T (F, {1})={0, 1}

∗

{1}{1}.

Completeness of automaton mappings 97

Usually, in automata and language theory we use the notion of acceptance of languages

by states, i.e. a word w is accepted by an automaton A =(X, Z, z

,T,δ) (without output),

where T is a subset of Z,ifδ

∗

,w) ∈ T . Obviously, if—in addition—one deﬁnes the output

function γ : Z × X →{0, 1} by γ(z, x) = 1 if and only if δ(z, x) ∈ T (and γ(z,x)=0

otherwise), then the automaton and its sequential function accept the same set by state set

T and output set {1}.

The concepts of regular languages and languages accepted by a sequential function are

connected by the famous theorem of Kleene.

4.4 Theorem AsetL ⊂ X

is regular if and only if there are a sequential function F :

→ Y

andasetY



, ∅⊂Y



⊂ Y , such that T (F,Y



)=L.

We omit a proof of Kleene’s Theorem. It is given in any textbook on the basics of

theoretical computer science using acceptance by states and can be transformed easily to

output acceptance.

4.5 Deﬁnition Two sequential functions F : X

→ Y

and G : X

→ Z

are Kleene-

equivalent (written as (F, G) ∈ σ

) if and only if there are sets Y



and Z



with ∅⊂Y



⊂ Y

and ∅⊂Z



⊂ Z such that T (F, Y



)=T (G, Z



We omit the easy proof of the following lemma.

4.6 Lemma σ

is an equivalence relation on F.

Assume that F and G are Kleene-equivalent sequential functions of F.ThenT (F, Y )=

T (G, Y



). Since ∅⊂Y ⊂{0, 1} and ∅⊂Y



⊂{0, 1}, either of the sets Y and Y



has to be

{0} or {1}.

Let us assume that Y = Y



= {1}. Then, for any t ∈ N, the functions ϕ

and ϕ

have

to coincide, since they have to give 1 if and only if the input belongs to their accepted sets

(which are equal). Thus F = G.

If we assume that Y = {0} and {Y



} = {1},then

,...,x

) = 0 if and only if ϕ

,...,x

)=1

for i ∈ N.Thuswehave

= (non) ◦ ϕ

for i ∈ N

and

F = F

(non)

◦G.

The other cases can be handled analogously. Thus we get the following assertion.

4.7 Lemma Let F ∈F

and G ∈F

. (F, G) ∈ σ

if and only if F = G or F = F

(non)

◦G

(and G = F

(non)

◦ F ).

We now give an example of a σ

-algebra.

4.8 Example Let i ∈{0, 1}.Weset

= {F | F ((i,i,...,i)) = i}.

98 J. Dassow

Obviously, F ∈ M

if and only if ϕ

∈ T

. It is easy to prove that M

is a subalgebra of F.

We now show that M

is a σ

-algebra; the proof for M

can be given analogously.

Let R be a regular set over {0, 1}

and let R be accepted by the sequential functions F and

G by {0} and {1}, respectively. If (0, 0,...,0) ∈ R,thenF ∈ M

since F ((0, 0,...,0)) ∈{0}.

If (0, 0,...,0) /∈ R,thenG((0, 0,...,0)) /∈{1}, i.e., G ∈ M

. Inbothcaseswehavea

sequential function in M

which accepts R. Hence M

is a σ

-algebra.

First we determine all σ

-algebras.

4.9 Theorem If M is a σ

-algebra of F,thenM = M

or M = M

or M = F.

Proof We only give an outline of the proof; for a complete proof we refer to [5, 9, 11].

Step 1. We consider the regular set {(0, 1)}∪({0, 1}

)

{(0, 1)} which is accepted by the

sequential functions F

(f)

and F

(non)

◦ F

(f)

= F

(non◦f )

and {1} and {0}, respectively, where

f(0, 1) = 1 and f(x, y)=0for(x, y) =(0, 1).

It is easy to see that f and non ◦ f are not monotone. Thus any σ

-algebra M contains a

sequential function F

(h)

where h/∈ Mon.

By analogous arguments one can prove that any σ

-algebra contain sequential functions

)

,1≤ i ≤ 5, where h

/∈ Sd, h

/∈ Lin, h

/∈ Q

, h

/∈ Q

and h

/∈ T

∩ T

, respectively.

By Theorem 2.14 (2),

M ⊇{F

(f)

| f ∈ T

} (4.1)

for some i ∈{0, 1}.

The regular set {0, 1}

∗

{0}{0, 1} is accepted by the functions F

(id;1)

and F

(non;0)

and

{0, 1}

∗

{1}{0, 1} is accepted by the functions F

(id;0)

and F

(non;1)

. Thus we get eight possi-

bilities depending on the i from (4.1) and the function used to accept {0, 1}

∗

{0}{0, 1} and

{0, 1}

∗

{1}{0, 1}. A detailed discussion of these cases leads to

M ⊇{F

(f)

| f ∈ T

}∪{F

(id;i)

(non;i)

} (4.2)

for some i ∈{0, 1}.

Step 2. We prove that, for i ∈{0, 1},

=[{F

(f)

| f ∈ T

}∪{F

(non;i)

}].

If we combine this relation with (4.2), then we get M ⊇ M

for some i ∈{0, 1}.

Step 3. We prove that M

and M

are maximal subalgebras of F. This implies M = M

or M = M

or M = F. 2

4.10 Theorem There is no algorithm which decides the σ

-completeness of a ﬁnite set.

Proof Assume that there is an algorithm to decide the σ

-completeness for a ﬁnite set M.

We show that this implies that there exists an algorithm to decide the completeness of a

ﬁnite set which contradicts Theorem 2.13.

Completeness of automaton mappings 99

Let M be a ﬁnite set. First we decide whether M is σ

-complete. If the answer is “no”,

then M is not complete (because any complete set is σ

-complete). If M is σ

-complete,

then one of the following three cases occurs:

[M]=M

or [M]=M

or [M]=F.

Let i ∈{0, 1}. Obviously, [M]=M

holds if and only if all elements of M belong to

. In order to check whether or not a sequential function F belongs to M

we have only

to test whether the output of F at the ﬁrst moment is i if the input at the ﬁrst moment is

thetupleconsistingofi’s only. If the answer is “yes” for any function of M,then[M]=M

Now we check whether [M]=M

or [M]=M

. If the answer is “yes”, for some

i ∈{0, 1},thenM is not complete. If the answer is no in both cases, then [M]=F has to

hold. Therefore M is complete. 2

4.11 Theorem

(1) M ⊂Fis σ

-complete if and only if M is not contained in any σ

-maximal subalgebra.

(2) The cardinality of the set of σ

-maximal subalgebras of F is the cardinality of the set

of real numbers.

(3) There is a countable set N of σ

-maximal subalgebras of F such that M ⊂Fis complete

if and only if M is not contained in any algebra of N.

Proof (1) Since any σ

-algebra is ﬁnitely generated, the statement follows from known

facts of universal algebra.

(2) Any maximal subalgebra of F which is diﬀerent from M

and M

is σ

-maximal

too. By Theorem 2.11, the statement follows.

(3) can be proved analogously to the proof of Theorem 2.12. 2

We now discuss some special cases by restricting to special regular sets, i.e., we do not

require that any regular language be accepted; we only ask for acceptance of some special

classes of regular languages.

First, we take into consideration only regular languages contained in ({0, 1}

)

,where

n ∈ N is a natural number.

Let n ≥ 2. Obviously, if M ⊆Fis a σ

-algebra, then, for any regular set R ⊆ ({0, 1}

)

there is a sequential function in M which accepts R.

We now prove the converse statement. For a regular set R ⊆ ({0, 1}

)

, we deﬁne the ex-

tension R(n) as follows: Let x

=(x

,...,x

)fori ≥ 1. Then the word x

...x

∈

({0, 1}

)

belongs to R(n) if and only if (x

)(x

) ...(x

) ∈ R, i.e., a word

belongs to R(n) if the word obtained by a restriction to the ﬁrst two components of any letter

belongs to R.

Let R(n) be an extension of R ⊆ ({0, 1}

)

,andletF be a sequential function of F

which accepts R(n)byY . Then the function F



which is obtained from F by identiﬁcation

of the the last n − 1 inputs, belongs to F

and accepts R by Y .

Analogously, we deﬁne the extension R(n)ofaregularsetR ⊆{0, 1}

.Moreover,for

any R ⊆{0, 1}

, there is a function G ∈F

such that G



obtained from G by identiﬁcation

of all inputs accepts R.

100 J. Dassow

Now assume that, M ⊆Fis a subalgebra of F such that, for any regular set R ⊆

({0, 1}

)

, there is a sequential function in M which accepts R. Then, for any regular set

R(n) which is an extension of a regular set R ⊆{0, 1}

∪ ({0, 1}

)

, there is a sequential

function in M which accepts R(n). Thus by the above construction, for any regular set

R ⊆{0, 1}

∪ ({0, 1}

)

, M contains a function F accepting R. Since we used only regular

sets from {0, 1}

∪ ({0, 1}

)

in the proof of Theorem 4.9, we can prove that M is a σ

algebra.

Therefore, for n ≥ 2, a subset M of F is σ

-complete if and only if, for any regular

set R ⊆ ({0, 1}

)

,[M ] contains a sequential function which accepts R.Thuswehavethe

following statement.

For n ≥ 2, there is no algorithm which decides for a ﬁnite set M ⊆Fwhether or

not, for any regular set R ⊆ ({0, 1}

)

, [M] contains a sequential function which

accepts R.

Now let n = 1, i.e., we consider only languages which are contained in {0, 1}

. Obviously,

in order to accept such languages we can restrict ourselves to unary sequential functions,

i.e., to elements of F

. Moreover, using the operation we can generate only functions which

depend essentially on at most one variable. Hence we here consider the semigroup F

instead

of F. We mention the following two results.

There is no ﬁnite set M such that, for any regular set R ⊆{0, 1}

, [M] contains

a sequential function accepting R.

This can be seen very easily. Assume that such a ﬁnite set M exists. Then we consider

the set M ∪{F

(non)

} which is ﬁnite, too, and generates F

. This contradicts the fact that

there is no ﬁnite system of generators for F

[15].

The set of subsemigroups of F

, which for any regular set R ⊆{0, 1}

contain a

sequential function accepting R, has the cardinality of the set of real numbers.

Let M = M

∩F

. Obviously, M is a subsemigroup of F

and,foranyregularset

R ⊆{0, 1}

, M contains a sequential function accepting R. For any t ∈ N,letF

be the

sequential function of F

with

,...,x



non(x

)ifi<t,

non(x

)ifi ≥ t.

For any set I ⊆ N,weset

=[M ∪{F

| t ∈ I}].

By deﬁnition, M

is a subsemigroup of F

and, for any regular set R ⊆{0, 1}

, M

contains

a sequential function accepting R. We show that s/∈ I, I ⊂ N and s = 1 implies F

/∈ M

Assume the contrary. Then

= G

◦ G

r−1

◦···◦G

for some functions G

,1≤ j ≤ r,withG

∈ M or G

= F

for some t ∈ I.IfG

∈ M holds

for 1 ≤ j ≤ r,thenG

∈ M

for 1 ≤ j ≤ r and thus F

∈ M

in contrast to its construction.

Let G

/∈ M , i.e., G

= F

for some t ∈ I.Let

G = G

k−1

◦ G

k−2

◦···◦G

and H = G

◦G

r−1

◦···◦G

k+1

Completeness of automaton mappings 101

Then we get

,...,x

⎧

⎪

⎨

⎪

⎩

(non(ϕ

)), non(ϕ

)),...,non(ϕ

))) if i<t,

(non(ϕ

)),...,non(ϕ

)),

non(ϕ

,...,x

)),...,non(ϕ

,...,x

))) if i ≥ t.

It is easy to see that the behaviour given on the right side of the last equation does not describe

the behaviour of F

(e.g., if s>tthen F

changes its function after the s-th moment, whereas

this does not hold for the functions given at the right hand side). This contradiction proves

that F

/∈ M

Let I

and I

be two subsets of N not containing 1. Then I

= I

implies M

= M

Therefore we have at least as many sets M containing a sequential function accepting R for

any regular set R ⊆{0, 1}

as we have subsets of N \{1}. Hence the statement follows.

We mention that the results under the restriction to regular sets contained in {0, 1}

strongly diﬀer from those for arbitrary regular sets (or regular sets contained in ({0, 1}

)

with n ≥ 2), for instance we have an inﬁnite set of subalgebras accepting all regular sets over

{0, 1} in contrast to only three σ

-algebras, or any σ

-algebra is ﬁnitely generated whereas

there is no ﬁnitely generated subsemigroup accepting all regular sets of {0, 1}

We now restrict ourselves to strongly deﬁnite languages, i.e., to languages of the form

({0, 1}

)

∗

U({0, 1}

)

∪



i∈Z

({0, 1}

)

with n ≥ 1,r≥ 0,U⊆{0, 1}

,Z⊆{1, 2,...,r}.

(for information on deﬁnite languages we refer to [12].) We note that a strongly deﬁnite

language of the above form is accepted by a sequential function F by Y = {y} where

,...,x

⎧

⎪

⎨

⎪

⎩

y if j ≤ r, j ∈ Z,

non(y)ifj ≤ r, j/∈ Z,

f(x

j−r

)ifj>r.

This means that the regular set is accepted by a sequential function which corresponds to a

Boolean function with delay r (and some ﬁxed outputs at the moments before the delay is

eﬀective). Such sequential functions can be described as (f ; r; a

,...,a

), where r is the

delay and a

is the output at the j-th moment, 1 ≤ j ≤ r.

Thus it is also natural to consider only such sequential functions. Therefore we have to

change the operation of substitution (or superposition) to synchronized substitution, i.e., for

any n-ary function F =(f ; r; a

...,a

)andn functions G

=(g

; s; b

,...,b

)with

arity m, we deﬁne F ◦ (G

,...,G

)by

F ◦ (G

,...,G

)(p

,...,p

)=F (G

,...p

),G

,...,p

),...,G

,...,p

)).

Let F

be the corresponding algebra, and let M be the closure of a set M with respect

to F

. Then we have the following result.

There is an algorithm which decides for a ﬁnite set M ⊂F

whether or not, for

any strongly deﬁnite language R, there is a function in M which accepts R.

102 J. Dassow

We omit the proof and refer to [6, 9].

However, we mention that there is a diﬀerence between our concepts and those of [14]

besides our restriction to a special equivalence relation. We have to generate all functions for

all delays whereas in [14] one only requires that any function can be generated with a certain

delay.

If we consider the special case of a function without delay or, equivalently, languages of

the form

({0, 1}

)

∗

U with n ≥ 1andU ⊆{0, 1}

, (4.3)

we have to consider P

. As above we can prove that T

, T

and P

are the only subalgebras

such that, for any regular set R of the form (4.3), the subalgebra contains a function accepting

R. Hence, by Theorem 2.14, we can decide for a ﬁnite set M ⊆ P

whether or not, for any

regular set R of the form (4.3), M contains a function accepting R. For corresponding

results for P

, k ≥ 3, we refer to [7].

Let us turn back to the consideration of equivalence relations and completeness with

respect to them.

We give some variations of Kleene-equivalence which can be described as shown in Lem-

ma 4.7 by using F

(non)

in the beginning or in the beginning and the end instead of using it

only in the end.

4.12 Deﬁnition

(1) F ∈F

and G ∈F

are called negation-equivalent (written as (F, G) ∈ σ

)ifand

only if F = G or

F (p

,...,p

)=G(F

(non)

),F

(non)

),...,F

(non)

)).

(2) F ∈F

and G ∈F

are called dual (written as (F, G) ∈ σ

) if and only if F = G or

F (p

,...,p

)=F

(non)

(G(F

(non)

),F

(non)

),...,F

(non)

))).

The duality is a well-known notion for Boolean functions (the Boolean functions which

are dual to itself form the maximal subalgebra Sd of P

Let us consider σ

-andσ

-completeness.

4.13 Theorem

(1) M ⊂Fis σ

-complete if and only if M is complete.

(2) M ⊂Fis σ

-complete if and only if M is complete.

Proof (1) With a set M ⊆Fwe associate the sets



=[M] ∩{F

(f)

| f ∈ P

} and M



= {f | f ∈ P

(f)

∈ M}.

First we note that any equivalence class contains at most two elements. If F

(f)

is an

element of an equivalence class with respect to σ

, then the other element is F

(g)

where g is

the Boolean function with

g(y

,...,y

)=f(non(y

), non(y

),...,non(y

)).