PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 98(112) (2015), 85–89 DOI:10.2298/PIM1512085M

DISJUNCTION OF BOOLEAN EQUATIONS

Ulfeta Marovac

Abstract. We give a formula for all the solutions of a disjunction of Boolean equations.

1. Introduction

Since Boole, systems of equations over a Boolean algebra have been extensively studied. Some results on solving systems of Boolean equations were summarized in Rudeanu’s books [5, 6]. The problem of solving the generalized systems of Boolean equations (systems which are built using conjunctions and disjunctions of Boolean equations and Boolean inequations) still stays open for further discussion. Banković has given all the solutions related to: Boolean inequations [1], systems of a Boolean equation and a Boolean inequation [2], and systems of two Boolean inequations [3]. Marovac in [7] has considered systems of k Boolean inequation and described all their solutions. In this paper, we deal with the problem of solving the disjunction of k Boolean equations.

Let (B, ∩, ∪,′, 0, 1) be a Boolean algebra and n be a natural number.

Definition 1.1. Let x ∈ B. Then

x^{1} = x, x^{0} = x′.

If X = (x_{1}, …, x_{n}) ∈ B^{n} and A = (a_{1}, …, a_{n}) ∈ {0, 1}^{n} then

X^{A} = x_{1}^{a_{1}} ∩ ⋯∩ x_{n}^{a_{n}} .

In the sequel, ∩ will be omitted.

Definition 1.2. [5, Definition 1.13] The Boolean functions of n variables (BFn) over the Boolean algebra (B, ∪, ·,′, 0, 1) are determined by the following rules:

(0) For every a ∈ B, constant function f_{a} : B^{n} → B defined by

f_{a}(x_{1}, …, x_{n}) = a (∀x_{1}, …, x_{n} ∈ B)

2010 Mathematics Subject Classification: Primary 06E30.

Key words and phrases: Boolean algebra, generalized system of Boolean equations, disjunction of Boolean equations, general solution.

Partially supported by the Ministry of Education, Science and Technological Development, Republic of Serbia, Project III-44007.

Communicated by Žarko Mijajlović.

is a BFn.

(1) For every i = 1, 2, …, n, the projection function ε_{i} : B^{n} → B defined by

ε_{i}(x_{1}, …, x_{n}) = x_{i} (∀x_{1}, …, x_{n} ∈ B)

is a BFn.

(2) If f, g : B^{n} → B are BFn, then the functions f ∪g, fg, f′: B^{n} → B defined by

(f ∪ g)(x_{1}, …, x_{n}) = f(x_{1}, …, x_{n}) ∪ g(x_{1}, …, x_{n}) (∀x_{1}, …, x_{n} ∈ B),
(fg)(x_{1}, …, x_{n}) = f(x_{1}, …, x_{n}) · g(x_{1}, …, x_{n}) (∀x_{1}, …, x_{n} ∈ B),
f′(x_{1}, …, x_{n}) = (f(x_{1}, …, x_{n}))′ (∀x_{1}, …, x_{n} ∈ B)

are BFn.

(3) Any BFn is obtained by applying the rules (0), (1) and (2) a finite number of times.

Theorem 1.1. [5, Corollary 1.1] The function f : B^{n} → B is Boolean if and only if it can be written in the canonical disjunctive form

f(X) = ⋃_{A} f(A)X^{A}.

2. Generalized systems of Boolean equations

When we generally refer to a system of equations of any kind, we refer to equations that are linked by logical conjunction. The idea of generalized system of equations is to link the equations by any logical operation, not merely by conjunction.

Definition 2.1. [6, Definition 5.1] The generalized systems of Boolean equations (GSBE’s for short) over a Boolean algebra are defined recursively as follows:

(i) every Boolean equation f(X) = 0 is a GSBE;

(ii) the negation, logical conjunction and logical disjunction of any GSBE’s is a GSBE;

(iii) every GSBE is obtained by applying rules (i) and (ii) finitely many times.

The problem of solving GSBE’s reduces to a particular case of it.

Definition 2.2. [6, Definition 5.3] An elementary GSBE is either a Boolean equation f(X) = 0 or a system of the form

f_{1}(X) ≠ 0 ∧ ⋯∧ f_{k}(X) ≠ 0

or of the form

g(X) = 0 ∧ f_{1}(X) ≠ 0 ∧ ⋯∧ f_{k}(X) ≠ 0.

If k = 1 we shall call them an atomic GSBE. An atomic GSBE of the form f(X) ≠ 0 will be called a Boolean inequation.

Proposition 2.1. [6, Proposion 5.1] Every GSBE is equivalent to a logical disjunction of elementary GSBE’s, possibly a single elementary GSBE.

Theorem 2.1. [6, Theorem 5.1] The set of solutions of any GSBE is the union of the sets of solutions of several elementary GSBE’s.

3. Boolean equations

To solve a Boolean equation f(X) = 0 means to determine all X ∈ B^{n} such that f(X) = 0 holds, i.e., to determine the set S = {X ∈ B^{n} | f(X) = 0}.

Theorem 3.1. [5, Theorem 2.3] Let f : B^{n} → B be a Boolean function. The equation f(X) = 0 has a solution if and only if ∏ _{A} f(A) = 0.

Let T = (t_{1}, …, t_{n}). The following definition comes from Prešić [4]. Prešić’s definition refers to an arbitrary equation. It can be also found in [6, Definition 1.2]. Here it is applied to Boolean equations.

Definition 3.1. Let f, F_{1}, …, F_{n} : B^{n} → B be Boolean functions and F =

(F_{1}, …, F_{n}). The formula X = F (T), or in scalar form x_{i} = F_{i}(t_{1}, …, t_{n}) (i = 1, …, n), expresses the general solution of the Boolean equation f(X) = 0 if and only if, for every X ∈ B^{n}

f(X) = 0 ⇔ (∃T)X = F (T).

Lemma 3.1. [5, Lemma 2.2] Suppose that the equation ax ∪ bx′ = 0 has a solution (ab = 0). Then

(3.1)  ax ∪ bx′ = 0 ⇔ (∃t)(x = a′t ∪ bt′)
ax ∪ bx′ = 0 ⇔ b ⩽ x ⩽ a′

for all x ∈ B.

4. Disjunction of k Boolean equations

Here we describe all the solutions of a system of Boolean equations connected by logical disjunction

(4.1)  f_{1}(X) = 0 ∨ f_{2}(X) = 0 ∨ ⋯∨ f_{k}(X) = 0.

The solution set of this system is the union of the solutions of the Boolean equations in it. If an equation has no solution, it will be eliminated from the system. In the sequel, we shall consider the system of Boolean equations of the form (4.1), where each equation has a solution.

Let k = 2. Then, system (4.1) can be written as f(X) = 0 ∨ g(X) = 0.

Theorem 4.1. Let f, g : B^{n} → B be Boolean functions. Then

f(X) = 0 ∨ g(X) = 0 ⇔ (∃T)(∃s)((s = 0 ∨ s = 1) ∧ (X = s′Φ(T) ∪ sΨ(T))

where Φ(T) and Ψ(T) express the general solutions of equations f(X) = 0 and g(X) = 0, respectively.

Proof. Let (∃T)(∃s)((s = 0 ∨ s = 1) ∧ (X = s′Φ(T) ∪ sΨ(T)). If s = 1, then

the formula X = s′Φ(T)∪sΨ(T) gives X = Ψ(T). Since Ψ(T) expresses the general solution of the equation g(X) = 0, then g(X) = 0. Therefore, f(X) = 0∨g(X) = 0. Similarly, if s = 0 then X = Φ(T). Since Φ(T) expresses the general solution of the equation f(X) = 0, then f(X) = 0. Therefore, f(X) = 0 ∨ g(X) = 0. Let f(X) = 0 ∨ g(X) = 0. If f(X) = 0, then there is T such that X = Φ(T), because X = Φ(T) determines the general solution of f(X) = 0. Therefore X = s′Φ(T) ∪ sΨ(T) for s = 0. Similarly, if g(X) = 0, then there is T such that X = Ψ(T), because X = Ψ(T) determines the general solution of g(X) = 0. Therefore X = s′Φ(T) ∪ sΨ(T) for s = 1. □

Example 4.1. Let a, b, c, d ∈ B. Solve the system

ax ∪ bx′ = 0 ∨ cx ∪ dx′ = 0.

According to (3.1) we can take Φ(t) = a′t ∪ bt′ and Ψ(t) = c′t ∪ dt′ . Using Theorem 4.1 we get

(4.2) ax ∪ bx′ = 0 ∨ cx ∪ dx′ = 0

⇔ (∃t)(∃s)((s = 0 ∨ s = 1) ∧ (x = s′(a′t ∪ bt′) ∪ s(c′t ∪ dt′)).

Example 4.2. Let B = {0, 1, m, l, k, m′, l′, k′}. Solve the system

m′x′ = 0 ∨ m′x = 0.

In accordance with Example 4.1 we have a = 0, b = m′, c = m′, d = 0. Then

m′x′ = 0 ∨ m′x = 0 ⇔ (∃t)(∃s)((s = 0 ∨ s = 1) ∧ (x = s′t ∪ m′st′∪ mst)).

Since t ∈ {0, 1, m, l, k, m′, l′, k′} and s ∈ {0, 1} we get x ∈ {m′, 1, 0, m}.

Theorem 4.2. Let f_{1}, …, f_{k} : B^{n} → B be Boolean functions. Then

f_{1}(X) = 0 ∨ ⋯∨ f_{k}(X) = 0 ⇔

(∃T)(∃s_{1}) ⋯ (∃s_{k−1} )((s_{i} = 0 ∨ s_{i} = 1) ∧ ⋯∧ (s_{k−1} = 0 ∨ s_{k−1} = 1)∧
X = s′_{1}Φ_{1}(T) ∪ ⋯∪ s_{1} ⋯ s_{k−2} s′_{k−1} Φ_{k−1} (T) ∪ s_{1} ⋯ s_{k−1} Φ_{k}(T))

where for every i ∈ {1, …, k}, Φ_{i}(T) expresses the general solution of the equation f_{i}(X) = 0.

Proof. Let

(4.3) (∃T)(∃s_{1}) ⋯ (∃s_{k−1} )((s_{1} = 0 ∨ s_{1} = 1) ∧ ... ∧ (s_{k−1} = 0 ∨ s_{k−1} = 1)∧

X = s′_{1}Φ_{1}(T) ∪ ⋯∪ s_{1} ⋯ s_{k−2} s′_{k−1} Φ_{k−1} (T) ∪ s_{1} ⋯ s_{k−1} Φ_{k}(T)).

Let s_{i} be the number of the sequence s_{1}, …, s_{k−1} such that s_{i} = 0 and i = 1 or s_{1} = 1 , …, s_{i−1} = 1. Then formula (4.3) gives X = Φ_{i}(T). Thus f_{i}(X) = 0. Therefore, f_{1}(X) = 0 ∨ ⋯∨ f_{k}(X) = 0. If s_{i} = 1 for each i ∈ {1, …, k − 1}, formula(4.3) gives X = Φ_{k}(T). Thus f_{k}(X) = 0. Therefore, f_{1}(X) = 0 ∨ ⋯∨ f_{k}(X) = 0. Let f_{1}(X) = 0 ∨ ⋯∨ f_{k}(X) = 0. Then f_{j} (X) = 0 for some j ∈ {1, …, k}. Then there is T such that X = Φ_{j} (T). Thus, X can be presented by formula (4.3), where: a) if j < k then s_{1} = 1, …, s_{j−1} = 1 and s_{j} = 0,

b) if j = k then s_{i} = 1 for each i ∈ {1 …k − 1}. □

Acknowledgement. The author is grateful to professor Dragić Banković for having suggested her to write this article.

References

1. D. Banković, Boolean inequations, Discrete Math. 307 (2007), 750–755.

2. , Boolean equations and Boolean inequations, J. Mult.-Val. Log. Soft Comput. 16 (2010), 189–196.

3. D. Banković, U. Marovac, System of two Boolean inequations, J. Mult.-Val. Log. Soft Comput. 24 (2015), 521–528.

4. S. Prešić, Ein Satz über reproduktive Lösungen, Publ. Inst. Math., Nouv. Sér. 14(28) (1973) 133–136.

5. S. Rudeanu, Boolean Functions and Equations, North-Holland, Amsterdam, 1974.

6. , Lattice Functions and Equations, Springer, Berlin, 2001.

7. U. Marovac, Systems of k Boolean inequations, J. Mult.-Val. Log. Soft Comput. 25 (2015), D401-MVLSC.

Department of Mathematics (Received 19 03 2015) State University of Novi Pazar Novi Pazar Serbia

    umarovac@np.ac.rs