PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 64 (78), 1998, 2–8

ON FREE BOOLEAN VECTORS

Žarko Mijajlović

Communicated by Mileva Prvanović

Abstract. Let f(x_{1}, x_{2},…, x_{n}) be a Boolean expression in n variables x_{1}, x_{2},…, x_{n}. A method for checking if the identity f(x_{1}, x_{2},…, x_{n}) = 1 is valid for all boolean values of x_{1}, x_{2},…, x_{n} is proposed, based on the parallel structure of a computer k-bit processor. We give a construction of n boolean vectors b_{1}, b_{2},…, b_{n} of the size 2^{n} with the following property:

If f(b_{1}, b_{2},…, b_{n}) = 1, then f(x_{1}, x_{2},…, x_{n}) is identically equal to one.

In this case, the necessary number of computing steps for checking the identity f(b_{1}, b_{2},…, b_{n}) = 1 is 2^{n−k}, to be compared with the number of 2^{n} computing steps in the usual table-checking procedure. The complete characterization of vectors b_{1}, b_{2},…, b_{n} is given.

It is usually neglected in the design and program implementation of algorithms that even standard computer processors are capable of performing certain parallel operations. Examples of this kind include logical operations which can be performed bitwise, i.e. by use of all register bits in one processor cycle. The aim of this paper is to present an algorithm for computing values of Boolean functions using parallel computing capability of a k-bit register processor. The mathematical background of this analysis are free finitely generated Boolean algebras.

1. Finite free Boolean algebras

Let us review first some facts, terminology and notation. The set of positive integers is denoted by N, while |X| denotes the cardinal number of a set X. Algebras will be denoted by bold capital letters (e.g. A), while their domains by ordinary capital letters (e.g. A). If F (x_{1}, x_{2},…, x_{n}) is an algebraic expression (term) over an algebraic language L, A an algebra of L and a_{1}, a_{2},…, a_{n} ∈ A, then F^{A}(a_{1}, a_{2},…, a_{n}) denotes the value of F in A for variables x_{1}, x_{2},…, x_{n} substituted with a_{1}, a_{2},…, a_{n}. If a set X ⊆ A generates A then we write A = ⟨X⟩. In the following we shall need the notion of a free algebra. Let M be an algebraic variety of algebras over a language L. An algebra A ∈ M is said to be free for M over a set of free generators X ⊆ A if for every B ∈ M and every map f: X → B there is a homomorphism h: A → B such that f ⊆ h. As it is well known (G. Birkhoff), every algebraic variety has a free algebra over the set X as a free set of generators for an arbitrary set X. As an illustration we prove the following theorem.

AMS Subject Classification (1991): 03G05, 06E30, 94C10

Theorem 1.1. Let M be an algebraic variety over an algebraic language L, and A ∈ M a free algebra over a finite free generator set X = {b_{1}, b_{2},…, b_{n}}, where b_{1}, b_{2},…, b_{n} are distinct. Further, let

u(x_{1}, x_{2},…, x_{n}) = v(x_{1}, x_{2},…, x_{n})

be an identity of L. If u^{A}(b_{1}, b_{2},…, b_{n}) = v^{A}(b_{1}, b_{2},…, b_{n}), then the identity u = v holds on all algebras of M.

Proof. Assume u^{A}(b_{1}, b_{2},…, b_{n}) = v^{A}(b_{1}, b_{2},…, b_{n}). Let B ∈ M be an arbitrary algebra and d_{1}, d_{2},…, d_{n} ∈ B. Further, let f: X → B be defined by f(b_{i}) = d_{i}, i = 1, 2,…, n. As A is free over X, there is a homomorphism h: A → B extending f. Then

u^{B}(d_{1}, d_{2},…, d_{n}) =u^{B}(hb_{1}, hb_{2},…, hb_{n}) = hu^{A}(b_{1}, b_{2},…, b_{n}) =
hv^{A}(b_{1}, b_{2},…, b_{n}) = v^{B}(hb_{1}, hb_{2},…, hb_{n}) =
v^{B}(d_{1}, d_{2},…, d_{n}).

As d_{1}, d_{2},…, d_{n} were arbitrarily selected it follows that u = v holds on B.♢

Let us consider free finitely generated Boolean algebras. By a Boolean algebra, shortly BA, we mean an algebraic structure B = (B, +, ·, ¯ , 0, 1,), where B is the domain of B, and +, ·, ¯ are usual Boolean operations. A two-element BA is denoted by 2, so its domain is 2 = {0, 1}. The fundamental representation theorem of finite BA’s states that every finite BA is isomorphic to 2^{n} for some n ∈ N. If B is generated by n elements b_{1}, b_{2},…, b_{n}, i.e., B = ⟨b_{1}, b_{2},…, b_{n}⟩ then |B| ≤ 2^{2^{n}}, so B is finite. From now on we shall discuss only finite BA’s. We shall call a basis of a BA B a minimal generating set of B. If the basis X is a free generating set of B then we shall call X a free basis, while the elements of X will be called free vectors. A free Boolean algebra generated by n free vectors will be denoted by Ω_{n}. First, we shall show that |B| = 2^{2^{n}} if and only if B is a free BA over a free generating n-element set. In the following we are going to use the following fact:

Theorem 1.2. (R. Sikorski) Let B be a BA and X ⊆ B. Then B is freely generated by X if and only if:

- B = ⟨X⟩.

- For any n ∈ N, b_{1}, b_{2},…, b_{n} ∈ X and α ∈ 2^{n}, b_{1}^{α_{1}}b_{2}^{α_{2}} ⋯ b_{n}^{α_{n}} ≠ 0. ♢

As usual, x^{1} = x and x^{0} = x̄. Here are examples of some free generating sets b_{1}, b_{2},…, b_{n}:

1^{0} The Lindenbaum algebra L_{P} of the propositional calculus with n propositional letters P = {p_{1}, p_{2},…, p_{n}}. If φ is a propositional formula over P and [φ] its equivalence class under the logical equivalence, then we may take b_{1} = [p_{1}], b_{2} = [p_{2}],…, b_{n} = [p_{n}].

2^{0} Let I = [0, 1]_{R} be the real interval. Then

b_{i} = {(x_{1}, x_{2},…, x_{n}) ∈ I^{n}: 0 ≤ x_{i} ≤ 1/2}, i = 1, 2,…, n

form a free basis of B = ⟨b_{1}, b_{2},…, b_{n}⟩ ⊆ P(I^{n}).

3^{0} Let A, B, C be circles in a Venn’s diagram, i.e., “circles in the general intersecting setting”. Then {A, B, C} is a free generating set of BA B = ⟨A, B, C⟩ ⊆ P(K), where K is a square to which belong A, B, C. According to the Theorem 1.1 every proof of a Boolean (and therefore set-theoretical) identity involving up to three variables using Venn’s diagrams is mathematically correct. Compare this to the sentence “They (Venn’s) diagrams are useful for verifying identities involving operations on sets, but should not be considered tools of rigorous mathematical proof” (cf. [2], p. 34).

4^{0} Let c_{i}, i = 0, 1,…, 2^{n} −1, be the binary expansion of the integer i with zeros padded to the left up to the length n. Let M be the matrix whose columns are vectors c_{i}, and let b_{i}, i = 1, 2,…, n, be binary vectors – rows of the matrix M. Then b_{1}, b_{2},…, are free vectors of Ω_{n}. In case n = 3, the matrix M looks like

M = [ \begin{matrix}0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{matrix} ]  (1.3)

thus, b_{1} = 00001111, b_{2} = 00110011, b_{3} = 01010101.

Theorem 1.4 Let B be a finitely generated BA. Then B is free if and only if it is isomorphic to 2^{2^{n}}.

Proof. Assume B = ⟨b_{1}, b_{2},…, b_{n}⟩ is freely generated by b_{1}, b_{2},…, b_{n}. If x∈B then x = Σ_{α∈Γ_{x}}b_{1}^{α_{1}}b_{2}^{α_{2}} ⋯ b_{n}^{α_{n}} for some Γ_{x} ⊆ 2^{n}. Let y = Σ_{α∈Γ_{y}}b_{1}^{α_{1}}b_{2}^{α_{2}} ⋯ b_{n}^{α_{n}}, Γ_{y} ⊆ 2^{n}. Assume that Γ_{x} ≠ Γ_{y}. Then Γ_{x}\Γ_{y} ≠ ∅, or Γ_{y}\Γ_{x} ≠ ∅, suppose Γ_{x}\Γ_{y} ≠ ∅. Let β ∈ Γ_{x}\Γ_{y}. Then by Sikorski’s condition b_{1}^{β_{1}}b_{2}^{β_{2}} ⋯ b_{n}^{β_{n}} ≠ 0 and b_{1}^{β_{1}}b_{2}^{β_{2}} ⋯ b_{n}^{β_{n}}Σ_{α∈Γ_{x}}b_{1}^{α_{1}}b_{2}^{α_{2}} ⋯ b_{n}^{α_{n}} = b_{1}^{β_{1}}b_{2}^{β_{2}} ⋯ b_{n}^{β_{n}} ≠ 0, so xb_{1}^{β_{1}}b_{2}^{β_{2}} ⋯ b_{n}^{β_{n}} ≠ 0. On the other hand, b_{1}^{β_{1}}b_{2}^{β_{2}} ⋯ b_{n}^{β_{n}}Σ_{α∈Γ_{y}}b_{1}^{α_{1}}b_{2}^{α_{2}} ⋯ b_{n}^{α_{n}} = 0, so yb_{1}^{β_{1}}b_{2}^{β_{2}} ⋯ b_{n}^{β_{n}} = 0. Hence, x ≠ y. Therefore, B has as many elements as there are subsets of 2^{n}, so |B| = 2^{2^{n}}.

Now assume that |B| = 2^{2^{n}}. By the above, Ω_{n} has 2^{2^{n}} elements, so by the representation theorem for finite Boolean algebras it follows B ≅ Ω_{n}. ♢

Theorem 1.5 Ω_{n+1} ≅ Ω_{n} × Ω_{n}.

Proof. By the previous theorem we have:

Ω_{n+1} ≅ 2^{2^{n+1}} ≅ 2^{2^{n}} × 2^{2^{n}} ≅ Ω_{n} × Ω_{n}. ♢

There is an easy procedure for constructing in the inductive way free vectors of Ω_{n} which can be used in a program implementation. Suppose that u_{1}, u_{2},…, u_{n−1} are free vectors of Ω_{n−1}. If this sequence is of length 1, then we take u_{1} = 01. Free vectors b_{1}, b_{2},…, b_{n} of Ω_{n} are obtained as follows. b_{1} = 00 … 011 … 1, i.e., b_{1} consists of two blocks, the first one is a block of zeros of size 2^{n−1}, while the second block is a sequence of ones also of size 2^{n−1}. Further, b_{2} = u_{1}ˆ u_{1}, b_{3} = u_{2}ˆ u_{2},… b_{n} = u_{n−1}ˆ u_{n−1}. Here uˆ v is a concatenation of words u and v.

For a real number x, let ⌈x⌉ denote the least integer greater than or equal to x.

Corollary 1.6 The Boolean algebra 2^{m} is generated by ⌈log_{2}(m)⌉ elements.

Proof. Let n = ⌈log_{2}(m)⌉. Then 2^{m} ≤ 2^{2^{n}}, so BA 2^{m} is a homomorphic image of BA 2^{2^{n}}, i.e., of Ω_{n}. A homomorphism h: Ω_{n} → 2^{m} is the projection, i.e. the mapping which cuts off the coordinates of vectors in 2^{2^{n}} (which are of length 2^{n}) to obtain vectors which are of length m. As Ω_{n} is generated by n vectors, say by b_{1}, b_{2},…, b_{n}, so is 2^{m}, since 2^{m} = ⟨hb_{1}, hb_{2},…, hb_{n}⟩. ♢

Example 1.7 Let us determine a generating subset of 2^{5} of size ⌈log_{2}(5)⌉ = 3. If in the matrix (1.3) the last three columns are deleted (the homomorphismprojection which “forgets” the three last coordinates), then we obtain vectors u_{1} = 00001, u_{2} = 00110, u_{3} = 01010, and 2^{5} = ⟨u_{1}, u_{2}, u_{3}⟩. As atoms of 2^{m} have exactly one bit equal to 1 in vector (binary) representation, by an obvious enumeration of atoms a_{i}, we have u_{1} = a_{5}, u_{2} = a_{3} + a_{4}, u_{3} = a_{2} + a_{4}.

Theorem 1.8 Suppose Ω_{n} = ⟨u_{1}, u_{2},…, u_{n}⟩. Then u_{1}, u_{2},…, u_{n} are free vectors of Ω_{n}.

Let {b_{1}, b_{2},…, b_{n}} be a free basis of Ω_{n}, and let the mapping f be defined by f(b_{i}) = u_{i}, i = 1, 2,… n. Then f extends to an endomorphism h: Ω_{n} → Ω_{n}. As u_{1}, u_{2},…, u_{n} generate Ω_{n}, h is onto. Since Ω_{n} is finite, h is also 1-1, therefore h is an automorphism. Hence u_{1} = hb_{1}, u_{2} = hb_{2},…, u_{n} = hb_{n} are free vectors of Ω_{n}.

♢

If u_{1}, u_{2},…, u_{m} ∈ Ω_{n} and m < n then ⟨u_{1}, u_{2},…, u_{m}⟩ is a proper Boolean subalgebra of Ω_{n} (since it has at most 2^{2^{m}} < 2^{2^{n}} elements), so, free vectors of Ω_{n} not only form a basis of Ω_{n} but also a generating set with the least possible number of elements. Thus it makes sense to introduce a “dimension” function d on a finite Boolean algebra B as dB = the least natural number k such that B has a basis with k elements. By the previous observation, we have dΩ_{n} = n. In fact we can compute d for every 2^{m}.

Theorem 1.9 d2^{m} = ⌈log_{2}(m)⌉.

Proof. By Corollary 1.6, Boolean algebra 2^{m} has a generating set having ⌈log_{2}(m)⌉ elements. If u_{1}, u_{2},…, u_{k} ∈ 2^{m} and k < ⌈log_{2}(m)⌉, then the subalgebra ⟨u_{1}, u_{2},…, u_{k}⟩ ⊆ 2^{m} has at most 2^{2^{k}} < 2^{m} elements so it is a proper subalgebra of 2^{m}. Thus 2^{m} does not have a generating subset with fewer elements than ⌈log_{2}(m)⌉.

♢

Since atoms of 2^{m} make a partition of 1, and under every non-zero element of 2^{m} there is an atom, it follows that the set of atoms A ⊆ 2^{m} is a basis of 2^{m} with the maximal number of elements. Hence, if S ⊆ 2^{m} is any basis of 2^{m}, then

⌈log_{2}(m)⌉ ≤ |S| ≤ m  (1.10)

Now, we shall describe all free base of Ω_{n}.

Theorem 1.11 Let b_{1}, b_{2},…, b_{n} be free vectors of Ω_{n} as defined in Example 4^{0}, b_{i} = (b_{i1}, b_{i2},…, b_{i2^{n}}), i = 1, 2,…, n. Let M = ||b_{ij}||_{n×2^{n}} be a matrix whose rows are formed by coordinates of vectors b_{i} (see the Example 4^{0}). Let p be any permutation of columns of matrix M, and let us denote the matrix so obtained by p ∗ M. Then

1. The rows of p ∗ M form a free basis of Ω_{n}.

2. Every free basis of Ω_{n} is obtained as row-vectors of p∗M for some permutation p.

Proof. To every column α of the matrix M corresponds an atom

a_{α} = b_{1}^{α_{1}}b_{2}^{α_{2}} ⋯ b_{n}^{α_{n}}

of Ω_{n}. Thus the permutation p permutes in fact atoms of Ω_{n}, so it defines an automorphism h_{p} of Ω_{n}. Then the rows of p∗M are images of free vectors b_{1}, b_{2},…, b_{n} under h_{p}, hence h_{p}b_{1}, h_{p}b_{2},…, h_{p}b_{n} also form a free basis of Ω_{n}.

Now, suppose that u_{1}, u_{2},…, u_{n} is any free basis of Ω_{n}. Let the mapping f be defined by f(b_{i}) = u_{i}, i = 1, 2,…, n. As u_{1}, u_{2},…, u_{n} generate Ω_{n}, f extends to an automorphism h of Ω_{n} (see the proof of Theorem 1.8). Therefore h permutes atoms of Ω_{n}, and h(b_{i}) = u_{i}, hence u_{i} are rows of the matrix p ∗ M, where p is the restriction of h to the set of atoms of Ω_{n}. ♢

By the above consideration, we see that the number of free basis of Ω_{n} is equal to |AutΩ_{n}| = (2^{n})!.

2. Computation of Boolean formulas by use of free vectors

Let f: Ω_{n} → 2 be a Boolean function. Representing f by its Boolean values, we may consider that f = F^{Ω_{n}}(b_{1}, b_{2},…, b_{n}), where F is a Boolean expression and b_{1}, b_{2},…, b_{n} form a free basis of Ω_{n}. Thus,

- If we want to check that f is identically equal to 1, it suffices to compute F^{Ω_{n}}(b_{1}, b_{2},…, b_{n}) and check if the Boolean values consist of the sequence of 1’s. Observe that in the computation, the expression F^{Ω_{n}}(b_{1}, b_{2},…, b_{n}) is evaluated only once. Also, we can obtain this fact by use of the Theorem 1.1.

- On the other hand, the sequence of binary values of F^{Ω_{n}}(b_{1}, b_{2},…, b_{n}) is exactly the sequence of values of the function f. If M = [b_{1}, b_{2},…, b_{n}] is the matrix whose rows are vectors b_{1}, b_{2},…, b_{n}, and α is the ith column of M (so 0 ≤ α ≤ 2^{n} − 1 if α is considered as a binary number), then the ith member of the sequence F^{Ω_{n}}(b_{1}, b_{2},…, b_{n}) is exactly f(α). Therefore, F^{Ω_{n}}(b_{1}, b_{2},…, b_{n}) represents f as a vector of the size 2^{n}. It should be observed that the DNF (disjunctive normal form) of F is read out from the binary representation of f immediately.

Now we shall consider an algorithm for fast checking whether f is identically equal to 1. Suppose that we have at our disposal a 2^{k}-bit processor (for example 2^{k} = 2^{5} = 32), and that we want to check whether f(x_{1}, x_{2},…, x_{n}) (for example n = 30) is identically equal to 1. According to the previous discussion, it suffices to see whether f(b_{1}, b_{2},…, b_{n}) = 1, where b_{1}, b_{2},…, b_{n} is a free basis of Ω_{n}. For the case 2^{n} ≤ 2^{k} one should put b_{1}, b_{2},…, b_{n} as binary sequences into 2^{k}-bit registers and compute f(b_{1}, b_{2},…, b_{n}). It means that in contemporary computer processors, due to the fact that logical operations are preformed bitwise, i.e. in parallel on the vectors of length 2^{k}, the evaluation of f can be done in the time interval of length t_{b} = λμ, where λ is the number of the nodes in the evaluation tree (the expression tree) of the corresponding Boolean expression F, and μ is the processor clock cycle which we may take to be about 5 · 10^{−9}sec. In the standard table-checking method this time interval would be of the length t_{s} = 2^{k}t_{b}, as it is performed on single bits, not on whole vectors. Thus, the proposed method speeds up the evaluation of f by 2^{k} times.

The algorithm works well on functions with small number of variables. Now, let us consider the case when the length of free vectors (i.e. when f have large number of arguments) is greater then the length of processor registers; this is the case when 2^{n} > 2^{k}. In this case each vector b_{i} should be divided simultaneously into blocks each of size 2^{k}. Observe that there are 2^{n−k} such blocks. Thus we may consider that b_{j} consists of blocks b_{i}^{j}, 1 ≤ i ≤ 2^{n−k}, each block having 2^{k} bits. Then, in order to to find out whether 0 appears in the binary expansion of f(b_{1}, b_{2},…, b_{n}), α = f(b_{i}^{1}, b_{i}^{2},…, b_{i}^{n}), 1 ≤ i ≤ 2^{n−k}, is computed and for each i it is checked whether 0 appears in the register containing the value α.

If 2^{r} processors are at our disposal, we may speed up the procedure by dividing the evaluation of f into 2^{r} parallel tasks, as the computation of f on a single block obviously does not depend on the values of f on other blocks. Then the necessary time of the whole computing process would take about t_{s}/2^{k+r}.

If for some reason the security of the computation is needed, as in cryptography, we can permute the bits of b_{i}, or the blocks b_{j}^{i} of the division of b_{i}. More precisely, the columns of the matrix M = [b_{1}, b_{2},…, b_{n}] are permuted (cf. Theorem 1.11), and then we apply f on the rows (blocks) of the matrix obtained in that manner.

Here is a real situation where the algorithm can be applied. Suppose that we have two Boolean expressions F (x_{1}, x_{2},…, x_{n}) and G(x_{1}, x_{2},…, x_{n}) that should define the same Boolean function f. Of course, we would like to know if F and G really define the same function, as f is intended to be firmware implemented on a certain chip. This problem may arise when G is obtained from F by some optimization process, so that F describes the intended function f of the chip, while G is the actual implementation of f on the chip. In order to show that the chip will work properly, it is necessary to show that F and G represent the same function f. There are algorithms that are used for this purpose, as the Quine’s BDP (binary decision procedure). In our approach we would take H = \overline{F △G}, where △ stands for the Boolean operation XOR (F △G = F̄G + fḠ). Then, check by the proposed procedure if H is identically equal to 1. If n ≤ 30, this can be done on a computer with one 32-bit processor in real time. But if parallel computers with processor fields, or if specialized chip (”logical chip”) with registers of appropriate size, say with 2^{24} bits, is designed, then the number of arguments of f can be raised up to 50.

3. Remark

In the search for zero in the sequence of binary values of F^{Ω_{n}}(b_{1}, b_{2},…, b_{n}), the reading of bits of a k-bit register for large k might be time consuming. In fact, this problem is equally hard to the computing problem of evaluating Lx, where L is an operator defined on the Boolean algebra B = 2^{k}, x ∈ B, which satisfies the following two axioms: x < 1 ⇒ Lx = 0, L1 = 1. If the dual operator M is defined by Mx = L̄x̄, then L and M behave as modal S5 necessity and possibility operators, respectively. In fact, finite structures (B, M, L) are characteristic algebras for S5 modal logic, i.e. modal propositional sentences true on such structures are exactly the theorems of S5 logic. There is a simple implementation of the operator M by a switching circuit by rows of AND gates described by the following recurrent formulas for x ∈ 2^{k}, k = 2^{m}, x = (x_{1}, x_{2},…, x_{n}):

x_{1}^{1} = x_{1}x_{2}, x_{2}^{1} = x_{3}x_{4},…  …  …, x_{2^{m−1}}^{1} = x_{2^{m}−1}x_{2^{m}}

x_{1}^{2} = x_{1}^{1}x_{2}^{1}, x_{2}^{2} = x_{3}^{1}x_{4}^{1},…, x_{2^{m−2}}^{2} = x_{2^{m−1}−1}^{1}x_{2^{m−1}}^{1}

⋮

x_{1}^{m} = x_{1}^{m−1}x_{2}^{m−1}.

Then Mx = x_{1}^{m}. Observe that the depth of this circuit is m = log_{2} k. In a similar way, a Boolean circuit for Lx can be constructed, but with OR gates. Therefore, the “logic processor” mentioned above should contain an extra bit e for each register. The bit e would carry out the status Mx of the register containing the value x. An extra property of such a device would be the capability of computing values of modal S5 formulas.

References

[1] P. M. Cohen, Universal Algebra, D. Reidel, Dordrecht, 1981.

[2] G.E. Hughes, M.J. Cresswell, An Introduction to Modal Logic, Methuen & Co, London, 1968.

[3] E. Mendelson, Boolean Algebra and Switching Circuits, Schaums’s Outline Series, McGraw Hil, New York, 1970.

[4] R. Sikorski, Boolean Algebras, Springer-Verlag, Berlin, 1969.

[5] R. Zacks, From Chips to Systems, Sybex, Berkely, 1981.

Matematički fakultet, Studentski trg 16, 11001 Beograd, p.p. 550, Yugoslavia (Received 01 04 1998; Revised 20 11 1998)