Special Coverings of Sets and Boolean Functions

Stepan Margaryan

doi:doi:10.11648/j.ajmcm.20251003.11

Research Article |

| Peer-Reviewed

Special Coverings of Sets and Boolean Functions

Stepan Margaryan^*

Published in American Journal of Mathematical and Computer Modelling (Volume 10, Issue 3)

Received: 13 June 2025 Accepted: 30 June 2025 Published: 23 July 2025

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

We will study some properties of Boolean functions based on newly introduced concepts called “Special Decomposition of a Set’’ and “Special Covering of a Set’’. The introduced concepts easily solve the question of how changes in clauses affect the resulting value of a function. They easily determine a clause as well as the literals that can be added to or removed from the clause so that the satisfiability of the function is preserved. The concept of generating a satisfiable function by another satisfiable function through admissible changes in the function's clauses is also introduced. If the generation of a function by another function is defined as a binary relation, then the set of satisfiable functions of n variables, represented in conjunctive normal form with m clauses is partitioned to equivalence classes. Moreover, we prove that any two satisfiable Boolean functions of n variables, represented in conjunctive normal form with m clauses, can be generated from each other in polynomial time.

Published in	American Journal of Mathematical and Computer Modelling (Volume 10, Issue 3)
DOI	10.11648/j.ajmcm.20251003.11
Page(s)	84-97
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2025. Published by Science Publishing Group

Keywords

Special Decomposition, Special Covering, Function Generation

1. Introduction

The subject of this article is Boolean functions represented in conjunctive normal form

[3, 7]

. We will study some properties of satisfiable functions

[1]

In generally the field of Boolean functions has long been widely investigated and well-studied

[2, 3, 6]

. Nevertheless, we obtain important and interesting results in this field using new introduced concepts of special decomposition and special covering of a set and based on them. These concepts are flexible and simple in use, so they enable us to study important problems concerning Boolean functions, including the satisfiability problem.

To create a special decomposition that will uniquely correspond to а Boolean function represented in conjunctive normal form, we treat the function as an ordered set of its clause.

We will show that any Boolean function in conjunctive normal form generates a special decomposition of the set of its clauses, and any special decomposition of a set generates a Boolean function. Moreover, we prove that these generations run in polynomial time

[9]

In addition, we prove that the Boolean function in conjunctive normal form is satisfiable if and only if there is a special covering for the set of clauses of this function.

One of the main goals of this article is to explore the possibilities of the concepts of special decomposition and special covering, using them in relation to satisfiable functions.

Typically, when transforming a Boolean function given in conjunctive normal form, it is not always obvious what impact a change in а clause may have on the satisfiability of the function. Furthermore, it is not always easy to find a clause and determine a literal that can be removed from or added to the clause, in order to preserve the satisfiability of the function.

We introduce the concept of admissible changes in the clauses, which allows us to add a literal to a clause, remove a literal from a clause, or swap negative and positive literals of the same variable of a satisfiable function, so that the resulting function remains satisfiable.

To study the results, we also introduce the concept of generation of а satisfiable function by another satisfiable function. Applying this concept to the function, as a result of any step, new satisfiable function is obtained. We also prove that the procedure for generation of a function by another function has a polynomial time complexity.

Further, defining the generation of a function by another function as a binary relation

[14, 16]

, we prove that the set of satisfiable functions of

n

variables represented in conjunctive normal form with

m

clauses, is partitioned into equivalence classes

[2, 3]

. All functions included in the same class have a common satisfiable assigning tuple.

Moreover, extending the rules of admissible changes, we prove an important result:

If two arbitrary Boolean functions of

n

variables represented in conjunctive normal form with

m

clauses, are both satisfiable, then either can be generated by the other using extended admissible changes in polynomial time

[8, 9, 11]

The terminology used in relation to set theory, Boolean functions, complexity theory and matrix theory is well known and is consistent with the terminology in corresponding monographs in the Bibliography. The newly introduced terms are not found in use by other authors and do not contradict to other terms.

2. Basic Concepts

We will deal with different nonempty sets. The elements of these sets will usually be denoted as

e_{1}

e_{2}

,.... etc. These sets are assumed to be ordered

[2, 14]

unless otherwise stated.

Let the nonempty set

S =

{

e_{1}

e_{2}

,...,

e_{m}

} be given. Let also for some natural number

n

(

M_{1}^{0}

M_{1}^{1}

),(

M_{2}^{0}

M_{2}^{1}

),...,(

M_{n}^{0}

M_{n}^{1}

)

n

arbitrary ordered pairs

[15, 16]

of arbitrary subsets of the set

S

It is important to note that the subsets and their pairs are numbered in no particular order.

We will use the notation

d_{n} S

for an arbitrarily ordered set of these ordered pairs:

d_{n} S

={(

M_{1}^{0}

M_{1}^{1}

),(

M_{2}^{0}

M_{2}^{1}

),...,(

M_{n}^{0}

M_{n}^{1}

)}.

The Boolean values

α_{i}

and

{\overset{̅}{α}}_{i}

, for

i

∈ {1,...,

n

}, will be used to denote superscripts of subsets:

{\overset{̅}{α}}_{i}

=0if

α_{i}

=1,and

{\overset{̅}{α}}_{i}

=1if

α_{i}

=0.

The tuple of superscripts (

α_{1}

,...,

α_{n}

) of subsets will also be called a Boolean tuple.

Definition 1.1. The set

d_{n} S

will be called a special decomposition of the set

S

, if

∀

i \in

{1,...,

n

}

{(M}_{i}^{0} \cap M_{i}^{1}

)=∅,(1)

∀

i \in

{1,...,

n

}(

M_{i}^{0} \neq \emptyset

M_{i}^{1} \neq

∅),(2)

⋃_{i = 1}^{n} (M_{i}^{0} \cup M_{i}^{1})

S

.(3)

Obviously, the same subsets of the set can form different special decompositions.

Definition 1.2. Let the set

d_{n} S

be a special decomposition of the set

S

For any Boolean tuple (

α_{1}

α_{2}

,...,

α_{n}

) the ordered set

c_{n} S

M_{1}^{α_{1}}

M_{2}^{α_{2}}

,...,

M_{n}^{α_{n}}

}

will be called a special covering for the set

S

under the decomposition

d_{n} S

, if

⋃_{i = 1}^{n} M_{i}^{α_{i}}

S

Note that the subsets

M_{i}^{0}

and

M_{i}^{1}

cannot simultaneously belong to the special covering.

Let

d_{n} S

= {(

M_{1}^{0}

M_{1}^{1}

),..., (

M_{n}^{0}

M_{n}^{1}

)}be an ordered set of arbitrary ordered pairs of subsets of the set

S

. For any 1 ≤

k

≤

n

, an ordered set obtained by permutating the components of arbitrary chosen ordered pairs

{(M}_{i_{1}}^{0}

M_{i_{1}}^{1})

,...,

(M_{i_{к}}^{0}

M_{i_{к}}^{1}

)

\in d_{n} S

will be called an

I

-transformation of the set

d_{n} S

. It will be denoted by

(i_{1}

i_{2}

,...,

i_{k}) I

(

d_{n} S

). Sometimes, if there is no need to mark the numbers of the ordered pairs, we will skip them and use the notation

I (d_{n} S)

I (d_{n} S)

{(M_{1}^{α_{1}}

M_{1}^{{\overset{̅}{α}}_{1}})

,...,(

M_{n}^{α_{n}}

M_{n}^{{\overset{̅}{α}}_{n}}

)}.

The ordered pairs of this decomposition are defined as:

(

M_{i}^{α_{i}}

M_{i}^{{\overset{̅}{α}}_{i}}

) = (

M_{i}^{0}

M_{i}^{1}

), if the components of the

i

-th pair are not displaced,

(

M_{i}^{α_{i}}

M_{i}^{{\overset{̅}{α}}_{i}}

) = (

M_{i}^{1}

M_{i}^{0}

), if the components of the

i

-th pair are displaced.

Lemma 1.3. If

d_{n} S

is an ordered set of ordered pairs of subsets of the set

S

then for any I-transformation I (

d_{n} S

), the following is true:

d_{n} S

is a special decomposition of the set

S

if and only if so is the ordered set

I (d_{n} S)

ii) If

d_{n} S

is a special decomposition of the set

S

, then there exists a special covering for the set

S

under the decomposition

d_{n} S

if and only if it exists under the decomposition

I

(

d_{n} S

Proof. i) During the transition from the set

d_{n} S

to the set

I (d_{n} S)

and vice versa, the contents of the subsets do not change. Only the orders of the components of some ordered pairs change. Therefore, the sets

d_{n} S

and

I (d_{n} S)

are either at the same time special decompositions of the set

S

, or at the same time they are not such decompositions.

At the other hand, if under the special decomposition

d_{n} S

the set

c_{n} S

= {

M_{1}^{α_{1}}

,...,

M_{n}^{α_{n}}}

(

α_{i} \in

{0, 1}) is a special covering for the set

S

, then it will also be a special covering for the set

S

under decomposition

I (d_{n} S)

and vice versa.

\nabla

In what follows, we will distinguish the subsets included in ordered pairs according to the order of their location in these pairs.

Let for some Boolean tuple (

α_{1}

,...,

α_{n}

d_{n} S

be a special decomposition:

d_{n} S

{(M_{1}^{α_{1}}

M_{1}^{{\overset{̅}{α}}_{1}})

,...,(

M_{n}^{α_{n}}

M_{n}^{{\overset{̅}{α}}_{n}}

)}.

The subsets

M_{1}^{α_{1}}

,...,

M_{n}^{α}

will be called the subsets of 0-domain,

The subsets

M_{1}^{{\overset{̅}{α}}_{1}}

,...,

M_{n}^{{\overset{̅}{α}}_{n}}

will be called the subsets of 1-domain.

If the components of an ordered pair (

M_{i}^{0}

M_{i}^{1}

) are permuted, then the subset

M_{i}^{1}

becomes a subset of the

0

-domain, and the subset

M_{i}^{0}

becomes a subset of the

1

-domain.

For technical convenience, for any

α \in

{0, 1}, we denote:

M^{α}

⋃_{i = 1}^{n} M_{i}^{α_{i}}

and

M^{\overset{̅}{α}}

⋃_{i = 1}^{n} M_{i}^{{\overset{̅}{α}}_{i}}

s M^{α}

= {

M_{1}^{α_{1}}

,...,

M_{n}^{α_{n}}

} and

s M^{\overset{̅}{α}}

= {

M_{1}^{{\overset{̅}{α}}_{1}}

,...,

M_{n}^{{\overset{̅}{α}}_{n}}

}. For any

α \in

{0, 1},

s M^{α}

will be called a set of

α

-components or

α

-domain of the decomposition

d_{n} S

(

i_{1}

,...,

i_{k}

M^{α}

is the set obtained by replacing the subsets

M_{1}^{α_{1}}

,...,

M_{n}^{α_{n}}

with the subsets

M_{1}^{{\overset{̅}{α}}_{1}}

,...,

M_{n}^{{\overset{̅}{α}}_{n}}

, respectively, in the set

s M^{α}

. (

i_{1}

,...,

i_{k}

)

s M^{α}

will be called a set of

α

-components of the ordered pairs included in the decomposition (

i_{1}

,...,

i_{k}

)

I (d_{n} S)

Definition 1.4. If the set of subsets of the

α

-domain is a special covering for the set

S

, then such a covering will be called a special

M^{α}

-covering or briefly

M^{α}

-covering for the set

S

Lemma 1.5. Let

d_{n} S

= (

M_{1}^{0}

M_{1}^{1}

),..., (

M_{n}^{0}

M_{n}^{1}

)} be a special decomposition of the set

S

Then, there exists a special covering for the set

S

under the special decomposition

d_{n} S

if and only if for some

α

∈ {0,1} there exists an

M^{α}

-covering for the set

S

under some special decomposition

I (d_{n} S)

Proof. Obviously, the procedure for forming the

α

-domain does not violate the Definition 1.2 of a special covering. Therefore, any

M^{α}

-covering is also a special covering for the set

S

If there exists a special covering for

S

containing subsets included in the

\overset{̅}{α}

-domain, then, obviously, by applying

I

-transformation with respect to ordered pairs containing these subsets, according to Lemma 1.3, we obtain an

M^{α}

-covering for the set

S

\nabla

3. Boolean Functions and Special Decompositions

Let for natural numbers

n

and

m

f

(

x_{1}

,...,

x_{n}

) be a Boolean function of

n

variables represented in conjunctive normal form (

CNF

) with

m

clauses.

We assume that the clauses of the function are numbered by the numbers 1,...,

m

in some natural order, and we will use the notation

c_{j}

for the

j

-th clause of the function. We will also use the notations

x_{i}^{0}

\overset{̅}{x_{i}}

and

x_{i}^{1}

x_{i}

for

i

∈ {1,...,

n

} for literals included in clauses.

For simplicity and technical convenience, we assume the following:

a) no variable and its negation are included in any clause simultaneously,

b) if the function contains

n

variables, then for any

i

∈ {1,...,

n

}, the literal

x_{i}^{α}

appears in some clauses for some

α

∈ {0,1}.

Obviously, this assumption does not limit the set of functions being considered.

We say that the clauses of the set {

c_{j_{1}}

,...,

c_{j_{k}}

} are satisfiable if there is a Boolean assignment tuple (

σ_{1}

,...,

σ_{n}

), such that any of these clauses takes the value 1 when the variables

x_{1}

,...,

x_{n}

are assigned the values

σ_{1}

,...,

σ_{n}

, respectively.

3.1. Special Decomposition of Clauses of a Boolean Function

Let

S

(

f

) = {

c_{1}

c_{2}

,...,

c_{m}

} be the set of clauses of some function

f

(

x_{1}

,...,

x_{n}

Based on the clauses of the function

f

(

x_{1}

,...,

x_{n}

), we form the subsets of the set

S

(

f

). For convenient these subsets will be denoted by capital letters corresponding to the function designation:

For any

i

∈ {1,...,

n

} and

α

∈ {0,1} we denote:

F_{i}^{0}

c_{j}

c_{j}

∈

S

(

f

)and

c_{j}

containstheliteral

{\overset{̅}{x}}_{i}

j

∈{1,...,

m

})}.

F_{i}^{1}

c_{j}

c_{j}

∈

S

(

f

)and

c_{j}

containstheliteral

x_{i}

j

∈{1,...,

m

})}.

Let’s form the following ordered set of ordered pairs of these subsets:

d_{n} S

(

f

)={(

F_{1}^{0}

F_{1}^{1}

),(

F_{2}^{0}

F_{2}^{1}

),...,(

F_{n}^{0}

F_{n}^{1}

)}.

We will say that the ordered set

d_{n} S

(

f

) is a decomposition of the set

S

(

f

) generated by the conjunctive normal form of the function

f

(

x_{1}

,...,

x_{n}

Lemma 2.2. For any function

f

(

x_{1}

,...,

x_{n}

), represented in conjunctive normal form, the set

d_{n} S

(

f

) is a special decomposition of the set

S

(

f

Proof. Taking into account that the functions under consideration satisfy conditions (a) and (b) set out in the previous paragraph, it is easy to verify that the conditions of the Definition 1.1 of the special decomposition, (1), (2) and (3) are satisfied.

\nabla

If there exists a special covering for the set

S (f)

under the special decomposition

d_{n} S (f),

then we will denote it by

c_{n} S (f)

= {

F_{1}^{α_{1}}

F_{2}^{α_{2}}

,...,

F_{n}^{α_{n}}}

Theorem 2.3. For any Boolean function

f

(

x_{1}

,...,

x_{n}

) represented in conjunctive normal form, the following is true:

There is a Boolean assigning tuple (

σ_{1}

,...,

σ_{n}

) such that f (

σ_{1}

,...,

σ_{n}

) = 1 if and only if there is a special covering for the set

S (f)

under the decomposition

d_{n} S (f)

Proof. Let for some tuple (

σ_{1}

,...,

σ_{n}

f

(

σ_{1}

,...,

σ_{n}

) =1. We prove, that then

⋃_{i = 1}^{n} F_{i}^{σ_{i}} = S (f)

, which will mean that the ordered set

c_{n} S (f)

= {

F_{1}^{σ_{1}}

F_{2}^{σ_{2}}

,...,

F_{n}^{σ_{n}}

} will be a special covering for the set

S (f)

under the decomposition

d_{n} S (f)

It is enough to show that each clause belongs to some subset included in the set

c_{n} S (f)

Suppose that there is a clause

c_{j}

∈

S

(

f

) that does not belong to any of the subset included in

c_{n} S (f)

. Then, none of the literals

x_{1}^{σ_{1}}

x_{2}^{σ_{2}}

,...,

x_{n}^{σ_{n}}

is included in the clause

c_{j}

. Therefore,

c_{j}

is the disjunction of some literals of the form

x_{i}^{{\overset{̅}{σ}}_{i}}

. Since

σ_{i}^{{\overset{̅}{σ}}_{i}} =

0 for any

i \in

{1,...,

n

}, then for given values of variables, the clause

c_{j}

will take the value 0, which contradicts the assumption that

f

(

σ_{1}

σ_{2}

,...,

σ_{n}

) = 1. So, each clause is included in some subset included in the set

c_{n} S (f)

Let for some tuple of superscripts (

α_{1}

α_{2}

,...,

α_{n}

), where

α_{i} \in \{0, 1\}

, the set

c_{n} S (f)

F_{1}^{α_{1}}

F_{2}^{α_{2}}

,...,

F_{n}^{α_{n}}

} is a special covering for the set

S (f)

under the decomposition

d_{n} S (f)

By definition, the subset

F_{i}^{α_{i}}

contains clauses that contain the literal

x_{i}^{α_{i}}

. If

x_{i}^{α_{i}}

= 1, then the value of all clauses included in the set

F_{i}^{α_{i}}

will be equal to 1,

That is, for any

i \in

{1,...,

n

} and

j \in

{1,...,

m

}, if (

x_{i}^{α_{i}}

= 1) & (

c_{j} \in F_{i}^{α_{i}}

) then (

c_{j}

= 1). It is easy to notice that if

σ_{1}

α_{1}

σ_{2}

α_{2}

,...,

σ_{n}

α_{n}

, then

f

(

σ_{1}

,...,

σ_{n}

) =1.

\nabla

3.2. Generation of the Boolean Function Based on a Special Decomposition

Let

S =

{

e_{1}

e_{2}

,...,

e_{m}

} be a nonempty set of

m

elements. Based on some special decomposition of the set

S

, we form a Boolean function, represented in conjunctive normal form. Suppose that

d_{n} S

= {

{{(M}_{1}^{0}, M}_{1}^{1})

,...,

(M_{n}^{0}, M_{n}^{1})

} is a mentioned decomposition.

To form this function, first, for any element

e_{j} \in S

, we form the set of literals, denoted by

l

(

e_{j}

), based on the positions of the subsets containing the element

e_{j}

. That is, for any

j

∈ {1,...,

n

} and

α \in \{0, 1\}

, if

e_{j}

∈

M_{i}^{α}

, then we form the literal

x_{i}^{α}

and add it to the formed set

l

(

e_{j}

). It is easy to see, that when forming the literals

x_{i}^{α}

, the number of variables will be

n

In fact, for any element

e_{i}

∈

S

we will have:

l

(

e_{j}

)={

x_{i}^{α}

e_{j}

∈

M_{i}^{α}

i

∈{1,...,

n

α \in \{0, 1\}

Let

c_{j}

be the clause formed by the literals of the set

l

(

e_{j}

). Obviously, the number of these clauses will be equal to

m

. Then, we form the function denoted by

h

(

x_{1}

,...,

x_{n}

) as follows:

h

(

x_{1}

,...,

x_{n}

⋀_{j = 1}^{m} c_{j}

We will say that the function

h

(

x_{1}

,...,

x_{n}

) is generated by the special decomposition

d_{n} S

Theorem 2.5. If the set

d_{n} S

= {

{{(M}_{1}^{0}, M}_{1}^{1})

,...,

(M_{n}^{0}, M_{n}^{1})

} is a special decomposition of a set

S

, and

h

(

x_{1}

,...,

x_{n}

) is the function generated by this decomposition, then:

There exists a special covering for the set

S

under the decomposition

d_{n} S

, if and only if there exists a Boolean assignment tuple (

σ_{1}

,...,

σ_{n}

) such that

h

(

σ_{1}

,...,

σ_{n}

) = 1.

Proof. The proof is similar to the proof of Theorem 2.3.

\nabla

Remark 2.6. In fact, we have established an important relationship between the Boolean satisfiability problem and the problem of finding a special covering for a set:

1. each Boolean function

f

(

x_{1}

,...,

x_{n}

) of

n

variables represented in conjunctive normal form with

m

clauses, generates a special decomposition

d_{n} S

(

f

) of the set

S

(

f

) of

m

elements.

2. each special decomposition of any set of

m

elements and containing

n

ordered pairs, generates a Boolean function of

n

variables in conjunctive normal form with

m

clauses.

In particular, using the Theorems 2.3 and 2.5, we can assert that any decidability result for any of these problems leads to the same result for the other

[1, 9, 11, 12]

4. Some Important Properties of Special Decompositions

We introduce some transformations in the special decomposition by changing the contents of subsets such that the conditions of the special decomposition are preserved.

We assume that the ordered set

d_{n} S

= {(

M_{1}^{0}

M_{1}^{1}

),..., (

M_{n}^{0}

M_{n}^{1}

)} is a special decomposition for a set

S

, and for some Boolean tuple (

α_{1}

,...,

α_{n}

), the ordered set

c_{n} S

= {

M_{1}^{α_{1}}

,...,

M_{n}^{α_{n}}

} is some special covering for the set

S

under this decomposition.

We will use the notation

M_{i}^{δ} \in

(

M_{i}^{0}

M_{i}^{1}

), meaning that

M_{i}^{δ}

M_{i}^{0}

M_{i}^{δ}

M_{i}^{1}

Definition 3.1. Let the ordered pairs (

M_{i}^{α}

M_{i}^{\overset{̅}{α}}

) and (

M_{j}^{β}

M_{j}^{\overset{̅}{β}}

) be included in the special decomposition

d_{n} S

and let

M_{i}^{δ} \in

(

M_{i}^{0}

M_{i}^{1}

) and

M_{j}^{γ} \in

(

M_{j}^{0}

M_{j}^{1}

i) We say that the changes in the contents of the subsets

M_{j}^{γ}

and

M_{i}^{δ}

are admissible under the tuple (

α_{1}

,...,

α_{n}

), if the changes are made in accordance with the following points:

a) for an element

e \in M_{i}^{δ}

, the subset

M_{i}^{δ}

is replaced with the set

M_{i}^{δ}

\ {

e

} in the ordered pair (

M_{i}^{0}

M_{i}^{1}

), if

M_{i}^{δ} \notin c_{n} S

and ((

M_{i}^{δ}

\ {

e

}) ∪

M_{i}^{\overset{̅}{δ}}

)

\neq \emptyset

b) for an element

e

∉ (

M_{i}^{0}

∪

M_{i}^{1}

), the subset

M_{i}^{δ}

is replaced with the set

M_{i}^{δ}

∪ {

e

} in the ordered pair (

M_{i}^{0}

M_{i}^{1}

c) if the subsets

M_{j}^{γ}

and

M_{i}^{δ}

are both included in

c_{n} S

, then for an element

e

such that

e

∈

M_{j}^{γ}

and

e

∉

M_{i}^{\overset{̅}{δ}}

, the subset

M_{j}^{γ}

is replaced with the set

M_{j}^{γ}

\ {

e

} and the subset

M_{i}^{δ}

is replaced with the set

M_{i}^{δ}

∪ {

e

} in the corresponding ordered pairs, respectively.

ii) We say that the ordered set, denoted by

d_{n} S G

, is generated by the decomposition

d_{n} S

as a result of admissible changes under the tuple (

α_{1}

,...,

α_{n}

), if these changes are made in the components of some ordered pairs of the decomposition

d_{n} S

, in accordance with points (i.1) - (i.3).

iii) We say that the ordered set, denoted by

c_{n} SG

is generated as a result of admissible changes under the tuple (

α_{1}

,...,

α_{n}

) in the special decomposition

d_{n} S

, if any subset included in it has the same superscript as the corresponding subset in the set

c_{n} S

If it does not lead to ambiguity, we will use the notation

c_{n} SG

for the ordered set which either coincides with the set

c_{n} S

or is generated by the sets

d_{n} S

and

c_{n} S

Theorem 3.2. Let for some Boolean tuple (

α_{1}

,...,

α_{n}

), the ordered set

c_{n} S

M_{1}^{α_{1}}

,...,

M_{n}^{α_{n}}

}

be a special covering for the set

S

under the special decomposition

d_{n} S

If the ordered sets

d_{n} S G

and

c_{n} SG

are generated as a result of admissible changes under the tuple (

α_{1}

,...,

α_{n}

) in the decomposition

d_{n} S

, then:

d_{n} S G

is also a special decomposition of the set

S

c_{n} SG

is a special covering for the set

S

under the decomposition

d_{n} S G

Proof. During the admissible changes, the conditions of Definition 1.1 are not violated.

\nabla

5. Admissible Changes in Clauses of Functions

Consider a Boolean function

f

(

x_{1}

,...,

x_{n}

) represented in conjunctive normal form with

m

clauses. Lemma 2.2 states that any Boolean function represented in

CNF

generates a special decomposition of the set

S

(

f

d_{n} S

(

f

)={(

F_{1}^{0}

F_{1}^{1}

),(

F_{2}^{0}

F_{2}^{1}

),...,(

F_{n}^{0}

F_{n}^{1}

)}.

Theorem 2.3 actually proves that the satisfiable assignment tuple defines the subsets that cover the set

S

(

f

), and vice versa, that is, for a Boolean tuple (

σ_{1}

,...,

σ_{n}

f

(

σ_{1}

,...,

σ_{n}

) = 1 if and only if the ordered set

c_{n} S (f)

= {

F_{1}^{σ_{1}}

F_{2}^{σ_{2}}

,...,

F_{n}^{σ_{n}}

} is a special covering for the set

S (f)

under the special decomposition

d_{n} S

(

f

Also, section 2.4 describes a procedure that, based on any special decomposition, generates a Boolean function in conjunctive normal form.

Definition 4.1. Let

f

(

x_{1}

,...,

x_{n}

) be a satisfiable Boolean function represented in conjunctive normal form.

We say that the function

h

(

x_{1}

,...,

x_{n}

) is generated by the function

f

(

x_{1}

,...,

x_{n}

) as a result of admissible changes under the assignment tuple (

σ_{1}

,...,

σ_{n}

), if the following conditions are met:

f

(

σ_{1}

,...,

σ_{n}

) = 1,

- the special decomposition

d_{n} S (f)

is generated by the function

f

(

x_{1}

,...,

x_{n}

- the special decomposition

d_{n} S (f) G

is generated by the special decomposition

d_{n} S (f)

as a result of admissible changes under the assignment tuple (

σ_{1}

,...,

σ_{n}

h

(

x_{1}

,...,

x_{n}

) is generated by the special decomposition

d_{n} S (f) G

Theorem 4.2. Let

f

(

x_{1}

,...,

x_{n}

) be a Boolean function represented in conjunctive normal form, and let for some assignment tuple (

σ_{1}

,...,

σ_{n}

f

(

σ_{1}

,...,

σ_{n}

) = 1.

If the function

h

(

x_{1}

,...,

x_{n}

) is generated by the function

f

(

x_{1}

,...,

x_{n}

) as a result of admissible changes under the assignment tuple (

σ_{1}

,...,

σ_{n}

), then

h

(

σ_{1}

,...,

σ_{n}

) = 1.

Proof. It is easy to see that under these conditions, according to Theorem 2.3, the ordered set

c_{n} S (f)

= {

F_{1}^{σ_{1}}

F_{2}^{σ_{2}}

,...,

F_{n}^{σ_{n}}

} is a special covering for the set

S (f)

under the special decomposition

d_{n} S (f)

Since the function

h

(

x_{1}

,...,

x_{n}

) is generated by the function

f

(

x_{1}

,...,

x_{n}

) by the admissible changes under the assignment tuple

σ_{1}

,...,

σ_{n}

), then:

- the special decomposition

d_{n} S (f)

generates the special decomposition

d_{n} S (f) G

as a result of admissible changes under the assignment tuple (

σ_{1}

,...,

σ_{n}

- the decomposition

d_{n} S (f) G

generates the function

h

(

x_{1}

,...,

x_{n}

According to Theorem 3.2, there is a special covering for the set

S (f)

under the special decomposition

d_{n} S (f) G

. But then, by Theorem 2.5, the function

h

(

x_{1}

,...,

x_{n}

) is satisfiable.

Obviously, during these changes in the decomposition

d_{n} S (f)

the special covering does not lose elements. So, the subsets with superscripts

σ_{1}

,...,

σ_{n}

, respectively, cover the set

S (f)

. Therefore,

h

(

σ_{1}

,...,

σ_{n}

) = 1.

\nabla

Let's explore the nature of the concept of function generation by a function in general.

For the function

f

(

x_{1}

,...,

x_{n}

) and for the satisfying assignment (

σ_{1}

,...,

σ_{n}

) we define the class of functions, denoted as

Gf

[

σ_{1}

,...,

σ_{n}

], as follows:

f

(

x_{1}

,...,

x_{n}

)

\in Gf

[

σ_{1}

,...,

σ_{n}

2) if the function

h

(

x_{1}

,...,

x_{n}

) is generated by the function included in the class

Gf

[

σ_{1}

,...,

σ_{n}

] as a result of admissible changes under the assignment tuple (

σ_{1}

,...,

σ_{n}

), then,

h

(

x_{1}

,...,

x_{n}

)

\in Gf

[

σ_{1}

,...,

σ_{n}

3) the class

Gf

[

σ_{1}

,...,

σ_{n}

] contains only functions satisfying conditions (1) and (2).

Theorem 4.3. Let

f

(

x_{1}

,...,

x_{n}

) and

h

(

x_{1}

,...,

x_{n}

) be Boolean functions of

n

variables represented in conjunctive normal form, each containing

m

clauses.

If there exists a Boolean satisfiable tuple (

σ_{1}

,...,

σ_{n}

) such that

f

(

σ_{1}

,...,

σ_{n}

) = 1 and

h

(

σ_{1}

,...,

σ_{n}

) = 1, then

h

(

x_{1}

,...,

x_{n}

)

\in Gf

(

σ_{1}

,...,

σ_{n}

) and

f

(

x_{1}

,...,

x_{n}

)

\in Gh

(

σ_{1}

,...,

σ_{n}

Proof. Let

S

(

f

) = {

c_{1}

,...,

c_{n}

} and

S

(

h

) = {

e_{1}

,...,

e_{n}

} be ordered sets of clauses of the functions

f

(

x_{1}

,...,

x_{n}

) and

h

(

x_{1}

,...,

x_{n}

), respectively. By Lemma 2.2 these functions generate special decompositions

d_{n} S

(

f

) and

d_{n} S

(

h

) of the sets

S

(

f

) and

S

(

h

), respectively:

d_{n} S

(

f

)={(

F_{1}^{0}

F_{1}^{1}

),(

F_{2}^{0}

F_{2}^{1}

),...,(

F_{n}^{0}

F_{n}^{1}

)},

d_{n} S

(

h

)={(

H_{1}^{0}

H_{1}^{1}

),(

H_{2}^{0}

H_{2}^{1}

),...,(

H_{n}^{0}

H_{n}^{1}

)}.

In addition, the following ordered sets

c_{n} S (f)

= {

F_{1}^{σ_{1}}

F_{2}^{σ_{2}}

,...,

F_{n}^{σ_{n}}

} and

c_{n} S (h)

= {

H_{1}^{σ_{1}}

H_{2}^{σ_{2}}

,...,

H_{n}^{σ_{n}}

} are special coverings for the sets

S

(

f

) and

S

(

h

), respectively.

Thus, we will proof that the special decompositions

d_{n} S

(

f

) and

d_{n} S

(

h

) are generated by each other as a result of admissible changes under the tuple of superscript (

σ_{1}

,...,

σ_{n}

Let for some

i \in

{1,...,

n

F_{i}^{σ_{i}}

c_{i_{1}}

,...,

c_{i_{p}}

}and

H_{i}^{σ_{i}}

e_{j_{1}}

,...,

e_{j_{q =}}

}.=

By the definition of these subsets,

x_{i}^{σ_{i}} \in c_{i_{k}}

forany

c_{i_{k}} \in

{

c_{i_{1}}

,...,

c_{i_{p}}

x_{i}^{σ_{i}} \in e_{j_{k}}

forany

e_{j_{k}} \in

{

e_{j_{1}}

,...,

e_{j_{q}}

Let’s describe a procedure for obtaining the subset

H_{i}^{σ_{i}}

instead the subset

F_{i}^{σ_{i}}

as a result of admissible changes in the decomposition

d_{n} S

(

f

The procedure consists of applying the points of Definition 3.1 to the subsets included in the decomposition

d_{n} S

(

f

We will assume that none of the subsets included in the set

c_{n} S (f)

is empty, otherwise we can add an element to this subset according to admissible changes. This does not affect the estimation of the complexity of the entire procedure.

a) We sequentially remove all elements from subsets not included in the set

c_{n} S (f)

. As a result, any ordered pair (

F_{i}^{0}

F_{i}^{1}

) will take the form

(

F_{i}^{0}

,∅),if

F_{i}^{0} \in c_{n} S (f)

or(∅,

F_{i}^{1}

),if

F_{i}^{1} \in c_{n} S (f)

We can do this applying the point (i.1) of the Definition 3.1. It is easy to see, that as a result of these operations some clauses of the function are change, so the function is changed. At the same time, the resulting function is satisfiable since all changes are made in accordance with the admissible changes under the same assignment tuple.

b) let’s consider the following cases for the clauses of the subsets

F_{i}^{σ_{i}}

c_{i_{1}}

,...,

c_{i_{p}}

}and

H_{i}^{σ_{i}}

e_{j_{1}}

,...,

e_{j_{q}}

Recall that our goal is to obtain the clauses of the set

H_{i}^{σ_{i}}

instead of the set

F_{i}^{σ_{i}}

in the decomposition

d_{n} S

(

f

) using the admissible changes.

1) suppose that

p

q

. In this case, we proceed as follows:

For any number

i_{k} \in

{

i_{1}

,...,

i_{p}

}, we compare the pairs of clauses

c_{i_{k}}

and

e_{i_{k}}

- if

c_{i_{k}}

and

e_{i_{k}}

are the same, we will assume that

e_{i_{k}} \in F_{i}^{σ_{i}}

and compare other pairs.

- if there is a literal, let it be

x_{s}^{α_{s}}

, such that

x_{s}^{α_{s}} \in e_{i_{k}}

and

x_{s}^{α_{s}} \notin c_{i_{k}}

, then we add

x_{s}^{α_{s}}

to the clause

c_{i_{k}}

. Recall that adding the literal

x_{s}^{α_{s}}

to the clause

c_{i_{k}}

means adding the clause

c_{i_{k}}

to the subset

F_{s}^{α_{s}}

, which is possible if

c_{i_{k}} \notin F_{s}^{{\overset{̅}{α}}_{s}}

(point (i.2), of the Definition 3.1).

To show that the clause

c_{i_{k}}

can be added to the subset

F_{s}^{α_{s}}

, we consider two cases:

F_{s}^{α_{s}} \in c_{n} S (f)

. In this case

F_{s}^{{\overset{̅}{α}}_{s}}

\emptyset

, therefore we can add

c_{i_{k}}

to the subset

F_{s}^{α_{s}}

which will mean that the literal

x_{s}^{α_{s}}

is added to the clause

c_{i_{k}}

F_{s}^{α_{s}} \notin c_{n} S (f)

. Then

F_{s}^{{\overset{̅}{α}}_{s}} \in c_{n} S (f)

and

F_{s}^{α_{s}}

\emptyset

. So, we will add

c_{i_{k}}

to the empty subset

F_{s}^{α_{s}}

. In this case, if

c_{i_{k}}

is included in

F_{s}^{{\overset{̅}{α}}_{s}}

, we can remove it in accordance to the point (i.3) of the Definition 3.1, since

c_{i_{k}}

is also included in another subset

F_{i}^{σ_{i}}

of the set

c_{n} S (f)

Thus, in case b.1) by means of admissible changes, we can add all clauses included in the subset

H_{i}^{σ_{i}}

to the subset

F_{i}^{σ_{i}}

2) if

p < q

, then we use the point (i.3) and add clauses to the subset

F_{i}^{σ_{i}}

such that the number of clauses in it will be equal to the number of clauses in the subset

H_{i}^{σ_{i}}

As a result, we will get the case b.1).

3) if

p > q

, then using the point (i.3), we move some clauses from the subset

F_{i}^{σ_{i}}

to other subsets such that the number of clauses in it will be equal to the number of clauses in the subset

H_{i}^{σ_{i}}

. As a result, we again get the case b.1).

c) after adding all the literals of the clause

e_{i_{k}}

to the clause

c_{i_{k}}

, we proceed to remove from the clause

c_{i_{k}}

literals that are not included in the clause

e_{i_{k}}

, as follows:

Let

x_{r}^{α_{r}} \in c_{i_{k}}

and

x_{r}^{α_{r}} \notin e_{i_{k}}

Removing

x_{r}^{α_{r}}

from

c_{i_{k}}

means removing

c_{i_{k}}

from the subset

F_{r}^{α_{r}}

. Note that we can do this using the point (i.3) of the Definition 3.1, since

c_{i_{k}}

is also included in the subset

F_{i}^{σ_{i}}

Repeating the procedure according to described points for all

i \in

{1,...,

n

}, we obtain the set

c_{n} S (h)

instead of the set

c_{n} S (f)

d) by applying the point (i.2) we do the following. For any subset

H_{i}^{{\overset{̅}{σ}}_{i}}

, which is not included in the special covering

c_{n} S (h)

, all clauses included in it are sequentially added to the subset

F_{i}^{{\overset{̅}{σ}}_{i}}

It is easy to see, that as a result, we obtain the special decomposition

d_{n} S

(

h

). Therefore, we can assert that first side of the theorem is valid, that is,

h

(

x_{1}

,...,

x_{n}

)

\in Gf

(

σ_{1}

,...,

σ_{n}

Similarly,

f

(

x_{1}

,...,

x_{n}

)

\in Gh

(

σ_{1}

,...,

σ_{n}

\nabla

Obviously, as a result of any step of the described procedure we obtain a new special decomposition of the set

S (f)

and a new special covering for the set

S (f)

under the obtained decomposition. Then, as a result of any step of the procedure, a satisfiable function is generated.

Applying the admissible changes to the subsets included in the special decomposition

d_{n} S

(

f

), actually means performing the following operations with the clauses of the function

f

- the clause

c_{j}

is removed from the subset

F_{i}^{α}

. This means the removing of the literal

x_{i}^{α}

from the clause

c_{j}

- the clause

c_{j}

is added to the subset

F_{i}^{α}

. This means adding the literal

x_{i}^{α}

to the clause

c_{j}

- the clause

c_{j}

is moved from the subset

F_{i}^{α}

, to the subset,

F_{j}^{δ}

. This means remove the literal

x_{i}^{α}

from the clause

c_{j}

and add the literal

x_{j}^{δ}

to the obtained clause.

Thus, adding a literal to a certain clause, removing a literal from the certain clause or changing a literal with another literal according to conditions of admissible changes, we obtain a satisfiable function.

Using the theorems 4.2 and 4.3, it is easy to proof the equivalence theorem.

First, let’s define a binary relation over the Boolean functions of

n

variables and represented in conjunctive normal form with

m

clauses. We will denote this relation by

G_{m}

[

σ_{1}

,...,

σ_{n}

] where (

σ_{1}

,...,

σ_{n}

) is a Boolean assignment tuple.

Suppose that

f

(

x_{1}

,...,

x_{n}

) and

h

(

x_{1}

,...,

x_{n}

) are Boolean function of

n

variables, both in conjunctive normal form with

m

clauses.

(

f

h

) will denote the ordered pair of these functions.

We say that (

f

h

)

\in G_{m}

[

σ_{1}

,...,

σ_{n}

], if the following conditions are satisfied:

f

(

σ_{1}

,...,

σ_{n}

) = 1,

- the function

h

(

x_{1}

,...,

x_{n}

) is generated by the function

f

(

x_{1}

,...,

x_{n}

) as a result of admissible changes under the satisfying assignment (

σ_{1}

,...,

σ_{n}

Theorem 4.4. For any Boolean assignment (

σ_{1}

,...,

σ_{n}

), the relation

G

[

σ_{1}

,...,

σ_{n}

] is an equivalence relation over the satisfiable Boolean functions of

n

variables represented in conjunctive normal form with

m

clauses.

Proof. Based on description of the relation

G

[

σ_{1}

,...,

σ_{n}

] and the definition of admissible changes, it is easy to prove that

G_{m}

[

σ_{1}

,...,

σ_{n}

] is a reflexive, symmetric and transitive relation

[2]

over the satisfiable Boolean functions. That is:

- if

f

(

σ_{1}

,...,

σ_{n}

) = 1, then (

f

f

)

\in G_{m}

[

σ_{1}

,...,

σ_{n}

- if (

f

h

)

\in G_{m}

[

σ_{1}

,...,

σ_{n}

] then (

h

f

)

\in G

[

σ_{1}

,...,

σ_{n}

- if (

f

g

)

\in G_{m}

[

σ_{1}

,...,

σ_{n}

] and (

g

h

)

\in G_{m}

[

σ_{1}

,...,

σ_{n}

] then (

f

h

)

\in G_{m}

[

σ_{1}

,...,

σ_{n}

\nabla

6. Complexity Estimations

In the previous sections we described the procedures that implement the proofs of theorems, so an important issue is to estimate the complexity of these procedures. They are as follows:

a) A procedure for generating a special decomposition of the set of clauses of the given Boolean function in conjunctive normal form.

b) A procedure for generating a Boolean function in conjunctive normal form based on a given special decomposition of a certain set.

c) A procedure for generating a satisfiable function from another satisfiable function by admissible changes under some satisfying assignment.

Data Representations.

Let

c_{1}

,...,

c_{m}

be the clauses of the function 𝑓(

x_{1}

,...,

x_{n}

). We will represent the function 𝑓(

x_{1}

,...,

x_{n}

) as an (

m ⨉ n

) matrix

[13]

, with elements 0, -1, 1. It will be denoted as (

f

)cnf.

The rows of the matrix will represent the clauses of the function, and the none-zero elements of the rows will represent the literals included in the clauses.

(

f

)cnf(

j

i

) = -1, if the negative literal

\overset{̅}{x_{i}}

is included in the clause

c_{j}

(

f

)cnf(

j

i

) = 0, if none of the literals

x_{i}

and

\overset{̅}{x_{i}}

is included in the clause

c_{j}

(

f

)cnf(

j

i

) = 1, if the positive literal

x_{i}

is included in the clause

c_{j}

Obviously, for any

j \in

{1,...,

m

}, the

j

-th row of the matrix (

f

)cnf is uniquely determined by the clause

c_{j}

of the function. Also, for any

j \in

{1,...,

m

}, the clause

c_{j}

of the function is uniquely determined by the

j

-th row of the corresponding matrix (

f

)cnf.

In addition, any Boolean function

f

(

x_{1}

,...,

x_{n}

) represented in conjunctive normal form is uniquely determined by the corresponding matrix (

f

)cnf,

It is easy to see, that an (

m ⨉ n

)-matrix with elements 0, -1, 1 only, represents a Boolean function if and only if it does not contain a row with only zeros and a column with only zeros.

Let

d_{n} S

be a special decomposition of the nonempty set

S

= {

e_{1}

,...,

e_{m}

d_{n} S

={(

M_{1}^{0}

M_{1}^{1}

),...,

{(M}_{n}^{0}

M_{n}^{1}

)}.

We will consider

S

as an ordered set

[2, 16]

. Obviously, it will not lead to any ambiguity.

Similar to the case of Boolean functions, it is technically convenient to represent the special decomposition of the set

S

using an ordered pair of (0,1)-matrices, each of size (

n ⨉ m

We will denote these matrices by

sM 0

and

sM 1

, respectively. They will be formed based on the decomposition

d_{n} S

as follows. For

i \in

{1,...,

n

} and

j \in

{1,...,

m

sM 0

(

i

j

\{\begin{matrix} 0, if e_{j} \notin M_{i}^{0} \\ 1, if e_{j} \in M_{i}^{0} \end{matrix} sM 1

(

i

j

\{\begin{matrix} 0, if e_{j} \notin M_{i}^{1} \\ 1, if e_{j} \in M_{i}^{1} \end{matrix}

We will say that the ordered pair (

sM 0

sM 1

) corresponds to the special decomposition

d_{n} S

On the other hand, the special decomposition

d_{n} S

is determined by the corresponding ordered pair of matrices (

sM 0

sM 1

). For any

i \in

{1,...,

n

M_{i}^{α}

e_{j} \in S

sM

i

j

)=1}and

M_{i}^{\overset{̅}{α}}

e_{j} \in S

sM 1

(

i

j

)=1},

Thus, any row of the matrices

sM

0 and

sM 1

corresponds to some subset included in the ordered pairs of a special decomposition. The ordered pair (

M_{i}^{0}

M_{i}^{1}

) of the decomposition

d_{n} S

will be determined by ordered pair of

i

-th rows of the matrices

sM 0

and

sM 1

We will say that the pair of (0,1)-matrices (

sM 0

sM 1

) is generated by the Boolean function 𝑓(

x_{1}

,...,

x_{n}

), if this pair corresponds to the special decomposition

d_{n} S

(

f

Recall that for any

i

∈ {1,...,

n

} the subsets

F_{i}^{0}

and

F_{i}^{1}

are composed as follows:

F_{i}^{0}

c_{j}

c_{j}

∈

S

(

f

)and

c_{j}

containstheliteral

{\overset{̅}{x}}_{i}

j

∈{1,...,

m

})},

F_{i}^{1}

c_{j}

c_{j}

∈

S

(

f

)and

c_{j}

containstheliteral

x_{i}

j

∈{1,...,

m

})}.

c_{j}

is a

j

-th clause of the function

f

(

x_{1}

,...,

x_{n}

According to Lemma 2.2, the ordered set of the ordered pairs of these subsets compose the special decomposition

d_{n} S

(

f

Let’s denote by ((

f

)

sM 0

, (

f

)

sM 1

) the pair of (0,1)-matrices, which is formed as follows:

(

f

)

sM 0

(

i

j

\{\begin{matrix} 0, if c_{j} \notin F_{i}^{0} \\ 1, if c_{j} \in F_{i}^{0} \end{matrix}

(

f

)

sM 1

(

i

j

\{\begin{matrix} 0, if c_{j} \notin F_{i}^{1} \\ 1, if c_{j} \in F_{i}^{1} \end{matrix}

We will say that the pair of (0,1)-matrices ((

f

)

sM 0

, (

f

)

sM 1

) corresponds to the special decomposition

d_{n} S

(

f

). On the other hand,

c_{j} \in F_{i}^{α}

if the literal

x_{i}^{α}

is included in the clause

c_{j}

. So,

(

f

)

sM 0

(

i

j

\{\begin{matrix} 0, if x_{i}^{0} \notin c_{j} \\ 1, if x_{i}^{0} \in c_{j} \end{matrix}

(

f

)

sM 1

(

i

j

\{\begin{matrix} 0, if x_{i} \notin c_{j} \\ 1, if x_{i} \in c_{j} \end{matrix}

In addition, we will use the following notation for any

i \in

{1,...,

n

(

f

)

M 0

(

i

)=((

f

)

sM 0

(

i

1

),...,(

f

)

sM 0

(

i

m

))

(

f

)

M 1

(

i

)=((

f

)

sM 1

(

i

1

),...,(

f

)

sM 1

(

i

m

)).

It is obvious, that the ordered pair ((

f

)

M 0

(

i

), (

f

)

M 1

(

i

)) is the ordered pair of

i

-th rows of the matrices (

f

)

sM 0

and (

f

)

sM 1

, respectively.

The Complexity of the Described Procedures

[1, 4, 5, 8]

Let we are given a special decomposition

d_{n} S

, and let (

sM 0

sM 1

) be a pair of (0,1)-matrices corresponding to this special decomposition.

Also, let we are given a Boolean function

f

(

x_{1}

,...,

x_{n}

) in conjunctive normal form, and let (

f

)cnf be the corresponding matrix with the elements 0, -1 and 1.

We often identify a special decomposition of a nonempty set of

m

elements containing

n

ordered pairs of subsets with the corresponding pair of (0,1)-matrices of the size (

n ⨉ m

We will also identify a Boolean function of

n

variables, in conjunctive normal form with

m

clauses, with the corresponding (

m ⨉ n

)-matrix with the elements 0, -1 and 1.

Definition 5.1. (i) The total number of 1s in the matrices

sM 0

and

sM 1

will be called the length of the input data of the special decomposition

d_{n} S

(ii) The total number of non-zero elements included in the matrix (

f

)cnf will be called the length of input data of the function

f

(

x_{1}

,...,

x_{n}

Definition 5.2. The following operations will be called elementary:

- assigning a value to a function variable or assigning a value to an array element,

- addition and subtraction of numbers,

- comparison of two numbers.

Proposition 5.3. If

f

(

x_{1}

,...,

x_{n}

) is a Boolean function represented in conjunctive normal form with

m

clauses, then the number of elementary operations required to obtain the pair of matrices ((

f

)

sM 0

, (

f

)

sM 1

) does not exceed the number

c ⨉ n ⨉ m

for some constant

c

Proof. We will form the matrices (

f

)

sM 0

and (

f

)

sM 1

based on the corresponding matrix (

f

)cnf and using the formulas described in the previous section.

For any

j \in

{1,...,

m

}, we sequentially consider all the elements of the

j

th row of the matrix (

f

)cnf and proceed as follows:

if (

f

)cnf(

j

i

) = -1, we assign 1 to the element (

f

)

sM 0

(

i

j

if (

f

)cnf(

j

i

) = 1, we assign 1 to the element (

f

)

sM 1

(

i

j

)

if (

f

)cnf(

j

i

) = 0, we assign 0 to the elements (

f

)

sM 0

(

i

j

) and (

f

)

sM 1

(

i

j

Recall that this corresponds to considering all the literals of any clause.

Obviously, all operations in the described procedure are elementary, and the number of these operations does not exceed the number

c ⨉

(

n ⨉ m

) for some constant

c

\nabla

Proposition 5.4. Let

S

= {

e_{1}

,...,

e_{m}

} be an ordered set, and

d_{n} S

{{(M}_{1}^{0}, M}_{1}^{1})

,...,

(M_{n}^{0}, M_{n}^{1})

be a special decomposition of the set

S

The number of elementary operations required to obtain the Boolean function generated by the special decomposition

d_{n} S

does not exceed the number

c ⨉ n ⨉ m

for some constant

c

Proof. Let

h

(

x_{1}

,...,

x_{n}

) denote the function that is generated by the decomposition

d_{n} S

We will form the matrix (

h

)cnf, which will correspond to the function

h

(

x_{1}

,...,

x_{n}

), based on the pair of matrices (

sM 0

sM \overset{̅}{1}

) corresponding to the special decomposition

d_{n} S

We will use the procedure described in the section 2.4. Recall that

sM 0

(

i

j

) = 1, if

e_{j}

∈

M_{i}^{0}

and

sM 1

(

i

j

) = 1, if

e_{j}

∈

M_{i}^{1}

For any

i

∈ {1,...,

n

}, we consider all elements of the

i

-th row of the matrix

sM 0

and all elements of the

i

-th row of the matrix

sM 1

, and do the following for any

j

∈ {1,...,

m

We assign (

h

)cnf(

j

i

) = -1 if

sM 0

(

i

j

) = 1,

We assign (

h

)cnf(

j

i

) = 1 if

sM 1

(

i

j

) = 1,

We assign (

h

)cnf(

j

i

) = 0 if

sM 0

(

i

j

) = 0 and

sM 1

(

i

j

) = 0.

Obviously, the resulting matrix (

h

)cnf(

j

i

) is formed correctly, and the number of required elementary operations does not exceed the number

c ⨉ n ⨉ m

for some constant

c

\nabla

The Propositions 5.3 and 5.4 prove the following:

Any Boolean function in conjunctive normal form generates a special decomposition in polynomial time, and any special decomposition of a set generates a Boolean function in conjunctive normal form in polynomial time.

Using Theorems 2.3 and 2.5, as well as Remark 2.6, one can state that any decidability procedure for the Boolean satisfiability problem leads to a decidability procedure for finding a special cover for a set, and vice versa.

[5]

The Complexity of the Generating Procedure

[1, 4, 5, 8, 10]

Theorem 5.5. Let the function

f

(

x_{1}

,...,

x_{n}

) be represented in CNF with

m

clauses, and let (

σ_{1}

,...,

σ_{n}

) be a Boolean assignment tuple such that

f

(

σ_{1}

,...,

σ_{n}

) = 1.

h

(

x_{1}

,...,

x_{n}

) is generated by the function

f

(

x_{1}

,...,

x_{n}

) as a result of admissible changes under the tuple (

σ_{1}

,...,

σ_{n}

), then the number of elementary operations to perform the generating procedure does not exceed the number

c ⨉ n ⨉ m

for some constant

c

Proof. According to Theorem 4.2,

h

(

σ_{1}

,...,

σ_{n}

) = 1.

In addition, the following conditions are satisfied by the Definition 4.1:

- the function

f

(

x_{1}

,...,

x_{n}

) generates the special decomposition

d_{n} S (f)

by Lemma 2.2,

- the special decomposition

d_{n} S (f)

generates the special decomposition

d_{n} S (f) G

as a result of admissible changes under the assignment tuple (

σ_{1}

,...,

σ_{n}

- the special decomposition

d_{n} S (f) G

generates the function

h

(

x_{1}

,...,

x_{n}

Thus, it is enough to estimate the number of required elementary operations for each of these procedures. According to Proposition 5.3, the number of elementary operations required to obtain the pair of (0,1)-matrices ((

f

)

sM 0

, (

f

)

sM 1

) generated by the function

f

(

x_{1}

,...,

x_{n}

) does not exceed the number

c ⨉ n ⨉ m

for some constant

c

According to Proposition 5.4, the number of elementary operations required to obtain the Boolean function generated by an ordered pair of (0,1)-matrices ((

f

)

sM 0

, (

f

)

sM 1

), does not exceed the number

c ⨉ n ⨉ m

for some constant

c

Thus, we need to estimate the number of elementary operations for generating the special decomposition

d_{n} S (f) G

based on the special decomposition

d_{n} S (f)

For convenience, here we will use

d_{n} S

(

h

) instead of the notation

d_{n} S (f) G

for the decomposition that generate the function

h

(

x_{1}

,...,

x_{n}

We will use the pairs of (0,1)-matrices ((

f

)

sM 0

, (

f

)

sM 1

) and ((

h

)

sM 0

, (

h

)

sM 1

) that correspond to the special decompositions

d_{n} S

(

f

) and

d_{n} S

(

h

), respectively.

Since the subsets

F_{i}^{σ_{i}}

and

H_{i}^{σ_{i}}

correspond to the rows (

f

)

M σ_{i}

(

i

) and (

h

)

M σ_{i}

(

i

), respectively, then the ordered sets

c_{n} S (f)

= {

F_{1}^{σ_{1}}

,...,

F_{n}^{σ_{n}}

} and

c_{n} S (h)

= {

H_{1}^{σ_{1}}

,...,

H_{n}^{σ_{n}}

}, correspond respectively to the following ordered sets of the rows:

{(

f

)

M σ_{1}

(

1

),...,(

f

)

M σ_{n}

(

n

)}and{(

h

)

M σ_{1}

(

1

),...,(

h

)

M σ_{n}

(

n

)},

Thus, we will estimate the maximum number of elementary operations required to generate the pair of (0,1)-matrices ((

h

)

sM 0

, (

h

)

sM 1

) based on the pair of (0,1)-matrices ((

f

)

sM 0

, (

f

)

sM 1

) using admissible changes under the tuple (

σ_{1}

,...,

σ_{n}

We will use the procedure similar to the procedure described in the Theorem 4.3.

Let’s note that we will consider the case when none of the rows included in the set

{(

f

)

M σ_{1}

(

1

),(

f

)

M σ_{2}

(

2

),...,(

f

)

M σ_{n}

(

n

)}

consist only of zeros, otherwise, we can assign 1 to any suitable element of this row in accordance with admissible changes. This does not affect the estimation of the complexity of the entire procedure. The procedure described in the Theorem 4.3 actually consists of the following points:

a) removal of all subsets that are not included in the special covering

c_{n} S (f)

This means sequentially assign zeros to all elements of the rows

(

f

)

M {\overset{̅}{σ}}_{1}

(

1

),(

f

)

M {\overset{̅}{σ}}_{2}

(

2

),...,(

f

)

M {\overset{̅}{σ}}_{n}

(

n

That is, the elements of any row not included in the set corresponding to the special covering

c_{n} S (f)

are assigned zero. Since the number of elements of any row does not exceed

m

, then the number of elementary operations for this point does not exceed the number (

n ⨉ m

b) for any

i \in

{1,...,

n

} we add all clauses included in the subset

H_{i}^{σ_{i}}

to the subset

F_{i}^{σ_{i}}

. That is, for any

i \in

{1,...,

n

}, we compare the elements of the rows

(

f

)

M σ_{i}

(

i

)={(

f

)

sM σ_{i}

(

i

1

),...,(

f

)

sM σ_{i}

(

i

m

)},

(

h

)

M σ_{i}

(

i

)={(

h

)

sM σ_{i}

(

i

1

),...,(

h

)

sM σ_{i}

(

i

m

)},

corresponding to the subsets

F_{i}^{σ_{i}}

and

H_{i}^{σ_{i}}

, respectively, and proceed as follows:

For any

j

∈ {1,...,

m

}, we assign (

f

)

sM σ_{i}

(

i

j

) = 1, if (

h

)

sM σ_{i}

(

i

j

) = 1. Obviously, the number of elementary operations for this point also does not exceed the number (

n ⨉ m

c) for any

i \in

{1,...,

n

}, all clauses included in the subset

F_{i}^{σ_{i}}

and not included in

H_{i}^{σ_{i}}

will be removed from the subset

F_{i}^{σ_{i}}

. That is, if for some

j

∈ {1,...,

m

(

f

)

sM σ_{i}

(

i

j

) = 1 and (

h

)

sM σ_{i}

(

i

j

) = 0, then we will assign (

f

)

sM σ_{i}

(

i

j

) = 0, which means removing the j-th clause from the subset

F_{i}^{σ_{i}}

It is easy to see (recall the arguments of the proof of Theorem 4.3), that the assignment operation (

f

)

sM σ_{i}

(

i

j

) = 0 corresponds to an admissible change, since for the same value of

j

and for another value of

i

, (

f

)

sM σ_{i}

(

i

j

) = 1. This also means that

c_{n} S (h)

will not lose an element.

Thus, by this point the procedure performs the following operations:

For any

i \in

{1,...,

n

}, it runs over the

i

-th row of the matrix (

h

)

sM σ_{i}

and considers the values of its elements

(

h

)

M σ_{i}

(

i

) = {(

h

)

sM σ_{i}

(

i

1

),..., (

h

)

sM σ_{i}

(

i

m

)}.

If for some

i \in

{1,...,

n

} and

j

∈ {1,...,

m

(

h

)

sM σ_{i}

(

i

j

) = 0 and (

f

)

sM σ_{i}

(

i

j

) = 1

then the element (

f

)

sM σ_{i}

(

i

j

) of the matrix (

f

)

sM σ_{i}

is assigned the value 0. It is easy to see that the described procedure requires no more than

c ⨉ n ⨉ m

elementary operations for some constant

c

d) for any pair of rows (

f

)

M {\overset{̅}{σ}}_{i}

(

i

) and (

h

)

M {\overset{̅}{σ}}_{i}

(

i

(

f

)

M {\overset{̅}{σ}}_{i}

(

i

)

\in

{(

f

)

M {\overset{̅}{σ}}_{1}

(

1

),(

f

)

M {\overset{̅}{σ}}_{2}

(

2

),...,(

f

)

M {\overset{̅}{σ}}_{n}

(

n

)},

(

h

)

M {\overset{̅}{σ}}_{i}

(

i

)

\in

{(

h

)

M {\overset{̅}{σ}}_{1}

(

1

),(

h

)

M {\overset{̅}{σ}}_{2}

(

2

),...,(

h

)

M {\overset{̅}{σ}}_{n}

(

n

)},

the elements of the row (

f

)

M {\overset{̅}{σ}}_{i}

(

i

) are assigned by the corresponding elements of the row (

h

)

M {\overset{̅}{σ}}_{i}

(

i

). So, the procedure for performing this point requires no more than (

n ⨉ m

) elementary operation. Thus, as a result of the procedures described in points a), b), c) and d) we obtain the pair of (0,1) matrices ((

h

)

sM 0

, (

h

)

sM 1

) based on the pair of (0,1)-matrices ((

f

)

sM 0

, (

f

)

sM 1

) using admissible changes under the assignment tuple (

σ_{1}

,...,

σ_{n}

Obviously, the number of all elementary operations for all described procedures does not exceed the number

c ⨉ n ⨉ m

for some constant

c

. ∇

Combining the results of the theorems 4.3 and 5.5, we can formulate the following:

Theorem 5.6. Let

f

(

x_{1}

,...,

x_{n}

) and

h

(

x_{1}

,...,

x_{n}

) be arbitrary Boolean functions, both represented in conjunctive normal form with

m

clauses. If there exists a Boolean assignment tuple (

σ_{1}

,...,

σ_{n}

) such that

f

(

σ_{1}

,...,

σ_{n}

) = 1 and

h

(

σ_{1}

,...,

σ_{n}

) = 1,

then the function

f

(

x_{1}

,...,

x_{n}

) generates the function

h

(

x_{1}

,...,

x_{n}

) as a result of admissible changes under the assignment tuple (

σ_{1}

,...,

σ_{n}

) in no more than

c ⨉

(

n ⨉ m

) elementary operations, for some constant

c

Proof. The proof follows directly from the Theorems 4.3 and 5.5. ∇.

7. Extension of Admissible Changes

In previous sections we studied admissible changes that are made only using elements from different subsets. We will extend this concept by adding a new operation to the operations defined in 3.1. The new operation will deal with ordered pairs of special decomposition.

Let’s consider the Boolean functions and the special decompositions generated by them.

Suppose that

f

(

x_{1}

,...,

x_{n}

) is a Boolean function in conjunctive normal form, and the set

d_{n} S

(

f

)={(

F_{1}^{0}

F_{1}^{1}

),...,(

F_{n}^{0}

F_{n}^{1}

)}

is a special decomposition of the set of clauses

S (f)

of this function.

Recall that (

i_{1}

,...,

i_{k}

)

I

(

d_{n} S

(

f

)) is a decomposition obtained as a result of permuting the components of the ordered pairs {(

F_{i_{1}}^{0}

F_{i_{1}}^{1}

),..., (

F_{i_{k}}^{0}

F_{i_{k}}^{1}

)} in the special decomposition

d_{n} S

(

f

According to Lemma 1.3, (

i_{1}

,...,

i_{k}

)

I

(

d_{n} S

(

f

)) is a special decomposition of the set

S

(

f

Theorem 6.1. If the function

h

(

x_{1}

,...,

x_{n}

) is generated by the special decomposition

(

i_{1}

,...,

i_{k}

)

I

(

d_{n} S

(

f

)), then

f

(

x_{1}

,...,

x_{n}

) is satisfiable if and only if

h

(

x_{1}

,...,

x_{n}

) is satisfiable.

Proof. Let

f

(

x_{1}

,...,

x_{n}

) be a satisfiable function, and let the set of ordered pairs

d_{n} S

(

f

)={(

F_{1}^{0}

F_{1}^{1}

),...,(

F_{n}^{0}

F_{n}^{1}

)}

be a special decomposition of the set

S (f)

. Then, according to Theorem 2.3, there is a special covering for the set

S (f)

under the special decomposition (

d_{n} S

(

f

)). Let it be the set

c_{n} S (f)

F_{1}^{α_{1}}

,...,

F_{n}^{α_{n}}

The special decomposition (

i_{1}

,...,

i_{k}

)

I

(

d_{n} S

(

f

)) is obtained by permuting components of the ordered pairs

{(

F_{i_{1}}^{0}

F_{i_{1}}^{1}

),...,(

F_{i_{k}}^{0}

F_{i_{k}}^{1}

)}

in the decomposition

d_{n} S

(

f

). So, by definition

(

i_{1}

,...,

i_{k}

)

I

(

d_{n} S

(

f

))={(

F_{1}^{σ_{1}}

F_{1}^{{\overset{̅}{σ}}_{1}}

),...,(

F_{n}^{σ_{n}}

F_{n}^{{\overset{̅}{σ}}_{n}}

)},

for

σ_{i} = \{\begin{matrix} 0, if i \notin {i_{1}, . . ., i_{k}} \\ 1, if i \in {i_{1}, . . ., i_{k}} \end{matrix}

But then, according to Lemma 1.3 there is a special covering for the set

S (f)

also under the special decomposition (

i_{1}

,...,

i_{k}

)

I

(

d_{n} S

(

f

)). Obviously, the following ordered set {

F_{1}^{δ_{1}}

,...,

F_{n}^{δ_{n}}

for

δ_{i} = \{\begin{matrix} α_{i}, i \notin {i_{1}, . . ., i_{k}} \\ {\overset{̅}{α}}_{i}, i \in \{i_{1}, . . ., i_{k}\} \end{matrix}

will be a special covering for the set

S (f)

under the special decomposition (

i_{1}

,...,

i_{k}

)

I

(

d_{n} S

(

f

)).

In addition, obviously,

h

(

δ_{1}

,...,

δ_{n}

) = 1. ∇

Let's now find out how the clauses of a new function

h

(

x_{1}

,...,

x_{n}

) differ from the clauses of the given function

f

(

x_{1}

,...,

x_{n}

) when permuting the components of some ordered pair, let it be (

F_{i}^{0}

F_{i}^{1}

), of the special decomposition

d_{n} S (f)

Suppose that

F_{i}^{0}

= {

c_{l_{1}}

,...,

c_{l_{p}}

} and

F_{i}^{1}

= {

c_{j_{1}}

,...,

c_{j_{q}}

}. By the definition of these subsets,

- the literal

{\overset{̅}{x}}_{i}

is included in all clauses of the set

c_{l_{1}}

,...,

c_{l_{p}}

- the literal

x_{i}

is included in all clauses of the set {

c_{j_{1}}

,...,

c_{j_{q}}

- the literals

{\overset{̅}{x}}_{i}

and

x_{i}

are not included in any other clauses.

When permuting the components of the ordered pair (

F_{i}^{0}

F_{i}^{1}

), we obtain the special decomposition (

i

)

I

(

d_{n} S

(

f

)), in which the

i

-th ordered pair has the form (

F_{i}^{1}

F_{i}^{0}

). The remaining ordered pairs coincide with the corresponding ordered pairs of

d_{n} S

(

f

(

i

)

I

(

d_{n} S

(

f

))={(

F_{1}^{0}

F_{1}^{1}

),...,(

F_{i}^{1}

F_{i}^{0}

),...,(

F_{n}^{0}

F_{n}^{1}

)}.

Let’s consider the procedure for generating the function

h

(

x_{1}

,...,

x_{n}

) in accordance with Section 2.4 based on the special decomposition (

i

)

I

(

d_{n} S

(

f

)).

Recall that, having a special decomposition of a set, for any element of this set we form a clause corresponding to this element, based on the positions of the subsets containing this element.

The ordered sets

d_{n} S

(

f

)) and (

i

)

I

(

d_{n} S

(

f

)) differ only in the

i

-th ordered pair. That is,

F_{i}^{0}

= {

c_{l_{1}}

,...,

c_{l_{p}}

} is located in the 1-domain,

F_{i}^{1}

= {

c_{j_{1}}

,...,

c_{j_{q}}

} is located in the

0

-domain, of the resulting decomposition.

Let’s denote the clauses of the function

h

(

x_{1}

,...,

x_{n}

) as

c_{1}^{'}

,...,

c_{m}^{'}

S

(

h

) = {

c_{1}^{'}

,...,

c_{m}^{'}

Since

h

(

x_{1}

,...,

x_{n}

) is generated by the decomposition (

i

)

I

(

d_{n} S

(

f

)), it is easy to see that:

- for any

c_{j_{r}}

∈ {

c_{j_{1}}

,...,

c_{j_{q}}

}, the corresponding new clause

c_{j_{r}}^{'}

will contain the literal

{\overset{̅}{x}}_{i}

- for any

c_{l_{r}}

∈ {

c_{l_{1}}

,...,

c_{l_{p}}

}, the corresponding new clause

c_{l_{r}}^{'}

will contain the literal

x_{i}

Denoting by

d_{n} S

(

h

) = {(

H_{1}^{0}

H_{1}^{1}

),..., (

H_{n}^{0}

H_{n}^{1}

)} the special decomposition (

i

)

I

(

d_{n} S

(

f

)), which generates the function

h

(

x_{1}

,...,

x_{n}

), according to the formation procedure we obtain:

- the literal

{\overset{̅}{x}}_{i}

is included in any of the clauses included in

H_{i}^{0}

- the literal

x_{i}

is included in any of the clauses included in

H_{i}^{1}

At the same time, the clauses of the function

h

(

x_{1}

,...,

x_{n}

), not included in the subsets

H_{i}^{0}

H_{i}^{1}

, coincide with the corresponding clauses of the function

f

(

x_{1}

,...,

x_{n}

Thus, the function

h

(

x_{1}

,...,

x_{n}

) is obtained by replacing the literal

{\overset{̅}{x}}_{i}

with the literal

x_{i}

and the literal

x_{i}

with the literal

{\overset{̅}{x}}_{i}

in all clauses of the function

f

(

x_{1}

,...,

x_{n}

) containing these literals.

Let’s now study the properties of extended changes in a special decomposition.

Consider a special decomposition of a set

S

d_{n} S

{{(M}_{1}^{0}, M}_{1}^{1})

,...,(

M_{n}^{0}

M_{n}^{1}

)}

such that for some Boolean tuple (

α_{1}

,...,

α_{n}

c_{n} S

= {

M_{1}^{α_{1}}

,...,

M_{n}^{α_{n}}

} is a special covering for

S

Definition 6.2. We say that the ordered set

d_{n} S G

is generated by the decomposition

d_{n} S

as a result of extended admissible changes if it is formed in accordance with the following steps:

- in addition to the admissible changes, a permutation procedure is also applied to some ordered pairs of the decomposition

d_{n} S

- if admissible changes are performed under some tuple of superscripts (

σ_{1}

,...,

σ_{n}

), and the permuting operation is applied to some

i

-th ordered pair of the decomposition under consideration, then admissible changes are continued under the tuple of superscripts (

σ_{1}

,...,

{\overset{̅}{σ}}_{i}

,...,

σ_{n}

It is easy to notice that adding a new operation to the operations of admissible changes actually means admitting

I

-thansformations in the special decomposition.

According to Lemma 1.3, this means that as a result of applying the new operation, the conditions of the special decomposition and special covering are preserved.

Definition 6.3. Let the function

f

(

x_{1}

,...,

x_{n}

) be represented in conjunctive normal form with

m

clauses. In addition, there is an assignment tuple (

σ_{1}

,...,

σ_{n}

) such that

f

(

σ_{1}

,...,

σ_{n}

) = 1.

We will say that the function

h

(

x_{1}

,...,

x_{n}

) is generated by the function

f

(

x_{1}

,...,

x_{n}

) as a result of extended admissible changes, if:

- the special decomposition

d_{n} S

(

h

) is generated as a result of extended admissible changes in the decomposition

d_{n} S

(

f

- the function

h

(

x_{1}

,...,

x_{n}

) is generated by the special decomposition

d_{n} S

(

h

Theorem 6.4. Let

f

(

x_{1}

,...,

x_{n}

) be a satisfiable Boolean function represented in conjunctive normal form with

m

clauses.

If the function

h

(

x_{1}

,...,

x_{n}

) is generated by the function

f

(

x_{1}

,...,

x_{n}

) as a result of extended admissible changes, then

h

(

x_{1}

,...,

x_{n}

) is a satisfiable function.

Proof. Let

d_{n} S

(

f

) be a special decomposition generated by the function

f

(

x_{1}

,...,

x_{n}

). Since

f

(

x_{1}

,...,

x_{n}

) is a satisfiable function, then there is some Boolean assignment tuple (

α_{1}

,...,

α_{n}

) such that

f

(

α_{1}

,...,

α_{n}

) = 1. At the same time, according to Theorem 2.3, the ordered set

c_{n} S (f)

F_{1}^{α_{1}}

,...,

F_{n}^{α_{n}}

}

is a special covering for the set

S

(

f

) under the decomposition

d_{n} S

(

f

We will show that as a result of applying any operation of extended admissible change, we obtain a special decomposition in which there will exist a special covering for the set

S

(

f

Let’s consider two cases:

a) the permuting operation is not applied during these changes.

In this case, according to Theorem 4.2, as a result of any operation we obtain a new special decomposition in which there exists a special covering for the set

S

(

f

In addition, the subsets included in the special covering have the same superscripts as in the original covering, (

α_{1}

,...,

α_{n}

). By Theorem 2.3, this means that as a result

h

(

α_{1}

,...,

α_{n}

)=1.

b) during the extended admissible changes, we apply the permutation procedure to the

i

-th ordered pair of the current decomposition. Let (

σ_{1}

,...,

σ_{i}

,...,

σ_{n}

) be the tuple of superscripts of the subsets make up the current special covering.

By definition, after the permutation, (

σ_{1}

,...,

{\overset{̅}{σ}}_{i}

,...,

σ_{n}

) will be the tuple of superscripts of the subsets in the special covering.

According to Theorem 2.3, this means that the function generated by this special decomposition takes the value 1 if the variables are assigned the values (

σ_{1}

,...,

{\overset{̅}{σ}}_{i}

,...,

σ_{n}

It is easy to see, that the final tuple of superscripts of the subset in the special covering will be a satisfying assignment for the function

h

(

x_{1}

,...,

x_{n}

). ∇

Theorem 6.5. Let

f

(

x_{1}

,...,

x_{n}

) and

h

(

x_{1}

,...,

x_{n}

) be arbitrary Boolean functions both represented in conjunctive normal form with

m

clauses. Let there also exist Boolean assignment tuples (

σ_{1}

,...,

σ_{n}

) and (

δ_{1}

,...,

δ_{n}

) such that

f

(

σ_{1}

,...,

σ_{n}

) = 1 and

h

(

δ_{1}

,...,

δ_{n}

) = 1.

Then, the function

h

(

x_{1}

,...,

x_{n}

) is generated by the function

f

(

x_{1}

,...,

x_{n}

), and the function

f

(

x_{1}

,...,

x_{n}

) is generated by the function

h

(

x_{1}

,...,

x_{n}

), as a result of extended admissible changes.

Proof. Let the ordered sets

d_{n} S

(

f

)={(

F_{1}^{0}

F_{1}^{1}

),...,(

F_{n}^{0}

F_{n}^{1}

)}and

d_{n} S

(

h

)={(

H_{1}^{0}

H_{1}^{1}

),...,(

H_{n}^{0}

H_{n}^{1}

)}

be special decompositions of the sets

S (f)

and

d_{n} S

(

h

), respectively.

The functions

f

(

x_{1}

,...,

x_{n}

) and

h

(

x_{1}

,...,

x_{n}

) are satisfiable, hence the ordered sets

c_{n} S (f)

F_{1}^{σ_{1}}

,...,

F_{n}^{σ_{n}}

}and

c_{n} S (h)

H_{1}^{δ_{1}}

,...,

H_{n}^{δ_{n}}

}

will be special coverings for the sets

S

(

f

) and

S

(

h

), respectively, under these decompositions.

We will prove that the function

h

(

x_{1}

,...,

x_{n}

) is generated by the function

f

(

x_{1}

,...,

x_{n}

) as a result of extended admissible changes.

Consider the tuples (

σ_{1}

,...,

σ_{n}

) and (

δ_{1}

,...,

δ_{n}

), which also are the tuples of superscripts of the subsets included in

c_{n} S (f)

and

c_{n} S (h)

, respectively.

We compare whether these tuples are the same.

- if (

σ_{1}

,...,

σ_{n}

) coincides with (

δ_{1}

,...,

δ_{n}

), then we use the procedure described in Theorem 4.3 to obtain the function

h

(

x_{1}

,...,

x_{n}

- if these tuples do not match, we compare their elements in pairs:

For any

i

∈ {1,...,

n

}, if

σ_{i} \neq δ_{i}

, we assign the value

δ_{i}

to the element

σ_{i}

It is easy to see that this operation is equivalent to the permutation of the components of the ordered pair (

F_{i}^{0}

F_{i}^{1}

), which is an admissible change. Therefore, we also permute the components of this ordered pair.

As a result of all these operations the special decomposition

d_{n} S

(

f

) turns out to another special decomposition. In addition, there exists a special covering under this decomposition such that (

δ_{1}

,...,

δ_{n}

) will be the tuple of superscripts of the subsets included in it.

On the other hand, the function generated by this special decomposition takes the value 1 if the variables are assigned the values (

δ_{1}

,...,

δ_{n}

Let’s denote this function by

g

(

x_{1}

,...,

x_{n}

). Since the function

g

(

x_{1}

,...,

x_{n}

) is generated by the function

f

(

x_{1}

,...,

x_{n}

), then using the Theorem 4.4, it is enough to proof that the function

h

(

x_{1}

,...,

x_{n}

) is generated by the function

g

(

x_{1}

,...,

x_{n}

Thus, we obtained that

δ_{1}

,...,

δ_{n}

) is a satisfying assigning tuple for the functions

g

(

x_{1}

,...,

x_{n}

)and

h

(

x_{1}

,...,

x_{n}

f

(

δ_{1}

,...,

δ_{n}

)=1and

h

(

δ_{1}

,...,

δ_{n}

)=1.

Obviously, the conditions of the Theorem 4.3 are satisfied for the functions

g

(

x_{1}

,...,

x_{n}

) and

h

(

x_{1}

,...,

x_{n}

Thus, the function

h

(

x_{1}

,...,

x_{n}

) is generated by the function

f

(

x_{1}

,...,

x_{n}

). Therefore, the function

h

(

x_{1}

,...,

x_{n}

) is also generated by the function

g

(

x_{1}

,...,

x_{n}

). In a similar way we prove that the function

f

(

x_{1}

,...,

x_{n}

) is generated by the function

h

(

x_{1}

,...,

x_{n}

). ∇

Theorem 6.6. Let

f

(

x_{1}

,...,

x_{n}

) and

h

(

x_{1}

,...,

x_{n}

) be arbitrary Boolean functions both represented in conjunctive normal form with

m

clauses. Let there also exist Boolean assignment tuples (

σ_{1}

,...,

σ_{n}

) and (

δ_{1}

,...,

δ_{n}

) such that

f

(

σ_{1}

,...,

σ_{n}

)=1and

h

(

δ_{1}

,...,

δ_{n}

)=1.

Then, the function

f

(

x_{1}

,...,

x_{n}

) generates the function

h

(

x_{1}

,...,

x_{n}

) as a result of extended admissible changes in no more than

c ⨉

(

n ⨉ m

) elementary operations, for some constant

c

Proof. Suppose that the pair of (0,1)-matrices ((

f

)

sM 0

, (

f

)

sM 1

) corresponds to the special decomposition

d_{n} S

(

f

). According to Proposition 5.3, the pair of matrices can be generated by the function

f

(

x_{1}

,...,

x_{n}

) in no more than

c ⨉

(

n ⨉ m

) elementary operations for some constant

c

We will use the procedure described during the proof of Theorem 6.5.

So, let

g

(

x_{1}

,...,

x_{n}

) be a function which takes the value 1 if the variables are assigned the values

δ_{1}

,...,

δ_{n}

. Recall that

g

(

x_{1}

,...,

x_{n}

) is the function generated by the ordered pair of matrices that is obtained as a result of permutation of some ordered pairs of rows included in the ordered pair of (0,1)-matrices ((

f

)

sM 0

, (

f

)

sM 1

Obviously, the maximum number of elementary operations required for permuting the components of an ordered pair of rows included in ((

f

)

sM 0

, (

f

)

sM 1

) does not exceed the number

c ⨉ m

for some constant

c

Hence, maximum number of elementary operations required for permuting the components of all needed ordered pairs does not exceed the number

c ⨉

(

n ⨉ m

Since

h

(

δ_{1}

,...,

δ_{n}

) = 1 and

g

(

δ_{1}

,...,

δ_{n}

) = 1, then according to Theorem 5.6, the function

g

(

x_{1}

,...,

x_{n}

) generates the function

h

(

x_{1}

,...,

x_{n}

) as a result of admissible changes under the assignment tuple (

σ_{1}

,...,

σ_{n}

) in no more than

c ⨉

(

n ⨉ m

) elementary operations, for some constant

c

. Combining these results, we can state:

Under the conditions of the theorem, the function

f

(

x_{1}

,...,

x_{n}

) generates the function

h

(

x_{1}

,...,

x_{n}

) as a result of extended admissible changes in no more than

c ⨉

(

n ⨉ m

) elementary operations, for some constant

c

. ∇

Thus, using the concept of admissible changes we can state the following:

- for any natural numbers

n

and

m

, the set of satisfiable functions of

n

variables, represented in conjunctive normal form with

m

clauses, is partitioned into equivalence classes,

- the functions included in the same class have a common satisfiable assigning tuple.

- for any function included in a certain class, as a result of applying any admissible operation on this function, another satisfiable function included in the same class is obtained.

- any function of any equivalency class can be generated by an arbitrary function of the same class in polynomial time.

Extending the rules of the admissible changes, we obtained an interesting result.

For any natural numbers

n

and

m

, all satisfiable functions of

n

variables, represented in conjunctive normal form with

m

clauses, are generated by each other in polynomial time, creating a chain of satisfiable functions in parallel.

Author Contributions

Stepan Margaryan is the sole author. The author read and approved the final manuscript.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach 2007.
[2]	Kenneth H. Rosen, Discrete Mathematics and its Applications, seventh edition, 2012.
[3]	Edward R. Scheinerman, Mathematics: A Discrete Introduction, Third Edition 2013.
[4]	Cook, S. A., The complexity of theorem - proving procedures. in Conference Record of. Third Annual ACM Symposium on Theory of Computing (1971), 151–158.
[5]	Karp, R. M., Reducibility among combinatorial problems. In Complexity of Computer, Computations, (1972), R. E. Miller and J. W. Thatcher, Eds., Plenum Press, 85–103.
[6]	Michael Sipser, Introduction to the Theory of Computation, third edition 2012.
[7]	Yves Crama, Peter L. Hammer, Boolean Functions. Theory, Algorithms, and Applications, 2011.
[8]	Peter G´acs Boston University and L´aszl´o Lov´asz Yale University, Complexity of Algorithms Lecture Notes, Spring 1999.
[9]	N. Creignou, S. Khanna, M. Sudan. Complexity Classifications of Boolean Constraint. Satisfaction Problems. Society for Industrial and Applied Mathematics, 2001.
[10]	Armin Biere, Marijn Heule, Hans van Maaren and Toby Walsh, Handbook of Satisfiability. IOS Press, 2008.
[11]	Evgeny Dantsin and Edward A. Hirsch, Worst-Case Upper Bounds, copyright 2008. SIAM J. Comput., vol 4, No. 1, March 1975.
[12]	Thomas J. Schaefer, The complexity of Satisfiability Problems. Department of Mathematics University of California, Berkeley, California 94720.
[13]	Fuzhen Zhang, Matrix Theory, Basic Results and Techniques, Second Edition, 2011.
[14]	Charles C. Pinter, A Book of Set Theory, 2014.
[15]	Thomas Jech, Set Theory, The Third Millennium Edition, 2003.
[16]	Luke Adams, Universal Totally Ordered Sets, May 11, 2018.

Cite This Article

Plain Text BibTeX RIS

APA Style

Margaryan, S. (2025). Special Coverings of Sets and Boolean Functions. American Journal of Mathematical and Computer Modelling, 10(3), 84-97. https://doi.org/10.11648/j.ajmcm.20251003.11

Copy | Download

ACS Style

Margaryan, S. Special Coverings of Sets and Boolean Functions. Am. J. Math. Comput. Model. 2025, 10(3), 84-97. doi: 10.11648/j.ajmcm.20251003.11

Copy | Download

AMA Style

Margaryan S. Special Coverings of Sets and Boolean Functions. Am J Math Comput Model. 2025;10(3):84-97. doi: 10.11648/j.ajmcm.20251003.11

Copy | Download

@article{10.11648/j.ajmcm.20251003.11,
  author = {Stepan Margaryan},
  title = {Special Coverings of Sets and Boolean Functions
},
  journal = {American Journal of Mathematical and Computer Modelling},
  volume = {10},
  number = {3},
  pages = {84-97},
  doi = {10.11648/j.ajmcm.20251003.11},
  url = {https://doi.org/10.11648/j.ajmcm.20251003.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajmcm.20251003.11},
  abstract = {We will study some properties of Boolean functions based on newly introduced concepts called “Special Decomposition of a Set’’ and “Special Covering of a Set’’. The introduced concepts easily solve the question of how changes in clauses affect the resulting value of a function. They easily determine a clause as well as the literals that can be added to or removed from the clause so that the satisfiability of the function is preserved. The concept of generating a satisfiable function by another satisfiable function through admissible changes in the function's clauses is also introduced. If the generation of a function by another function is defined as a binary relation, then the set of satisfiable functions of n variables, represented in conjunctive normal form with m clauses is partitioned to equivalence classes. Moreover, we prove that any two satisfiable Boolean functions of n variables, represented in conjunctive normal form with m clauses, can be generated from each other in polynomial time.},
 year = {2025}
}

Copy | Download

TY  - JOUR
T1  - Special Coverings of Sets and Boolean Functions

AU  - Stepan Margaryan
Y1  - 2025/07/23
PY  - 2025
N1  - https://doi.org/10.11648/j.ajmcm.20251003.11
DO  - 10.11648/j.ajmcm.20251003.11
T2  - American Journal of Mathematical and Computer Modelling
JF  - American Journal of Mathematical and Computer Modelling
JO  - American Journal of Mathematical and Computer Modelling
SP  - 84
EP  - 97
PB  - Science Publishing Group
SN  - 2578-8280
UR  - https://doi.org/10.11648/j.ajmcm.20251003.11
AB  - We will study some properties of Boolean functions based on newly introduced concepts called “Special Decomposition of a Set’’ and “Special Covering of a Set’’. The introduced concepts easily solve the question of how changes in clauses affect the resulting value of a function. They easily determine a clause as well as the literals that can be added to or removed from the clause so that the satisfiability of the function is preserved. The concept of generating a satisfiable function by another satisfiable function through admissible changes in the function's clauses is also introduced. If the generation of a function by another function is defined as a binary relation, then the set of satisfiable functions of n variables, represented in conjunctive normal form with m clauses is partitioned to equivalence classes. Moreover, we prove that any two satisfiable Boolean functions of n variables, represented in conjunctive normal form with m clauses, can be generated from each other in polynomial time.
VL  - 10
IS  - 3
ER  -

Copy | Download

Author Information

Stepan Margaryan

Mathematics Lecturer, Mkhitar Sebastatsi Educational Complex, Yerevan, Armenia

Contact Email

Download PDF

Submit an Article

Sections

Plain Text BibTeX RIS

APA Style

Margaryan, S. (2025). Special Coverings of Sets and Boolean Functions. American Journal of Mathematical and Computer Modelling, 10(3), 84-97. https://doi.org/10.11648/j.ajmcm.20251003.11

Copy | Download

ACS Style

Margaryan, S. Special Coverings of Sets and Boolean Functions. Am. J. Math. Comput. Model. 2025, 10(3), 84-97. doi: 10.11648/j.ajmcm.20251003.11

Copy | Download

AMA Style

Margaryan S. Special Coverings of Sets and Boolean Functions. Am J Math Comput Model. 2025;10(3):84-97. doi: 10.11648/j.ajmcm.20251003.11

Copy | Download

@article{10.11648/j.ajmcm.20251003.11,
  author = {Stepan Margaryan},
  title = {Special Coverings of Sets and Boolean Functions
},
  journal = {American Journal of Mathematical and Computer Modelling},
  volume = {10},
  number = {3},
  pages = {84-97},
  doi = {10.11648/j.ajmcm.20251003.11},
  url = {https://doi.org/10.11648/j.ajmcm.20251003.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajmcm.20251003.11},
  abstract = {We will study some properties of Boolean functions based on newly introduced concepts called “Special Decomposition of a Set’’ and “Special Covering of a Set’’. The introduced concepts easily solve the question of how changes in clauses affect the resulting value of a function. They easily determine a clause as well as the literals that can be added to or removed from the clause so that the satisfiability of the function is preserved. The concept of generating a satisfiable function by another satisfiable function through admissible changes in the function's clauses is also introduced. If the generation of a function by another function is defined as a binary relation, then the set of satisfiable functions of n variables, represented in conjunctive normal form with m clauses is partitioned to equivalence classes. Moreover, we prove that any two satisfiable Boolean functions of n variables, represented in conjunctive normal form with m clauses, can be generated from each other in polynomial time.},
 year = {2025}
}

Copy | Download

TY  - JOUR
T1  - Special Coverings of Sets and Boolean Functions

AU  - Stepan Margaryan
Y1  - 2025/07/23
PY  - 2025
N1  - https://doi.org/10.11648/j.ajmcm.20251003.11
DO  - 10.11648/j.ajmcm.20251003.11
T2  - American Journal of Mathematical and Computer Modelling
JF  - American Journal of Mathematical and Computer Modelling
JO  - American Journal of Mathematical and Computer Modelling
SP  - 84
EP  - 97
PB  - Science Publishing Group
SN  - 2578-8280
UR  - https://doi.org/10.11648/j.ajmcm.20251003.11
AB  - We will study some properties of Boolean functions based on newly introduced concepts called “Special Decomposition of a Set’’ and “Special Covering of a Set’’. The introduced concepts easily solve the question of how changes in clauses affect the resulting value of a function. They easily determine a clause as well as the literals that can be added to or removed from the clause so that the satisfiability of the function is preserved. The concept of generating a satisfiable function by another satisfiable function through admissible changes in the function's clauses is also introduced. If the generation of a function by another function is defined as a binary relation, then the set of satisfiable functions of n variables, represented in conjunctive normal form with m clauses is partitioned to equivalence classes. Moreover, we prove that any two satisfiable Boolean functions of n variables, represented in conjunctive normal form with m clauses, can be generated from each other in polynomial time.
VL  - 10
IS  - 3
ER  -

Copy | Download