Boolean Algebra

Boolean algebra is one of the most interesting and important algebraic structure which has significant applications in switching
circuits, logic and many branches of computer science and engineering.

Boolean algebra can be viewed as one of the special type of lattice.

A complemented distributive lattice with 0 and 1 is called Boolean algebra.
Generally Boolean algebra is denoted by (B, *, Å , ', 0, 1).

Example 1 :

( P(A), Ç , È , ', f, A) is a Boolean algebra. This is an important example of Boolean algebra [In fact the basic properties of
the (P (A), Ç , È , ' ) led to define the abstract concept of Boolean algebra]. Further, it can be proved that every finite Boolean
algebra must be isomorphic to (P (A), Ç , È , ' , f , A) for a suitably chosen finite set A. [refer [2]].

Example 2:

The structure ( Bⁿ = {0,1}ⁿ , *, Å , 1, 0 ) is a Boolean algebra, where Bⁿ is an n-fold Cartesian product of
{0,1} and the operations *, Å , are defined below.
We have Bⁿ = {( l₁, l ₂, … , l _n) / l _r = 0 or 1, 1 £ r £ n}
(i ₁, i ₂, … , i_n) * (j₁ , j₂, … , j_n) = (min (i ₁, j₁ ), min (i ₂, j₂), .., min (i _n, j_n) )
(i₁, i₂, … , i_n) Å (j₁, j₂,…, j_n) = (max ( i₁, j₁), max ( i₂, j₂), … , max ( i _n, j_n) )
(l ₁, l ₂, l ₃, … , l _n)' = (l ₁', l ₂', …. , l _n'),



1 = (1,1, …, 1) is the greatest element of Bⁿ.
0 = (0, 0,0, … ,0) is the least element of Bⁿ.
Since B is distributive, Bⁿ is distributive. From the definition of unary operation " ' ",

it is clear that Bⁿ is complemented. Further, it has 0 and 1. Thus, (Bⁿ, *, Å , ', 0,1) is a Boolean algebra.
For the case n = 3 we have,
B³ = {000, 100, 010, 001, 110, 101, 011, 111}.
The structure of the B³ is given in the following Hasse diagram.



The Boolean algebra (Bⁿ, *, Å , ', 0,1) plays an important role in the construction of switching circuits, electronic circuits and
other applications. Also it can be proved that every finite Boolean algebra is isomorphic to the above Boolean algebra
(Bⁿ, *, Å , ', 0,1), for some n. Thus, it is interesting to observe that number of elements in any finite Boolean algebra must be
always 2ⁿ, for some n.

Let (B, *, Å , ' , 0,1) be a Boolean algebra and S Í B. If S contains the elements 0 and 1 and is closed under the
operation *, Å and ' then (S, *, Å , ', 0,1) is called sub Boolean algebra.


Example 1:

Consider the Boolean algebra (P ({1,2,3}), Ç , È , ' ,f , {1,2,3})



Then (S = {f , {1}, {2,3}, {1,2,3}}, Ç , È , ', f , {1,2,3}) is also sub Boolean algebra.
Similarly, S = ({f ,{3},{1,2},{1,2,3}}, Ç , È , ', f , {1,2,3}) is also sub Boolean algebra.
But (S = ({f, {1}, {2,3}, {1,2,3}}, Ç , È ,' , f , {1,2,3})) is not a sub Boolean algebra.

[Find why it is not a sub Boolean algebra].


If we have two Boolean algebras (B₁, *₁, Å ₁, ', 0₁, 1₁) and (B₂, *₂, Å ₂, '', 0₂, 1₂) then we can get new Boolean algebra
by taking direct product of these two Boolean algebras. The direct product of these Boolean algebra is the Boolean algebra
(B₁ ´ B₂, *₃, Å ₃, ''', 0₃, 1₃); where for any two elements (a₁, b₁) and (a₂, b₂) Î B₁ ´ B₂,

(a₁,b₁) * (a₂,b₂) = (a₁ *₁ a₂, b₁ *₂ b₂)

(a₁,b₁)Å (a₂,b₂) = (a₁ Å ₁ a₂ , b₁ Å ₂ b₂)

(a₁,b₁) ''' = (a₁', b₁'')

0₃=(0₁,0₂) and 1₃=(1₁,1₂).

Let (B, *, Å , ', 0_B , 1_B) and (A, Ç , È, - , 0_A , 1_A) be two Boolean algebra. A mapping

f : B A is called a Boolean homomorphism if f preserves all the Boolean operations, that is,

f (a * b) = f (a) Ç f (b).
f (a Å b) = f (a) È f (b).

f (0_B) = 0_A.
f (1_B) = 1_A.


A bijective Boolean homomorphism is called Boolean isomorphism.


Exercise:

1. Prove that mapping f defined in the exercise 1 of the Section 3.3.3 is a Boolean isomorphism.
   
2. In every Boolean algebra, prove that (x * y)' = x' Å y' and (x Å y)' = x' * y', for all x, y.
   
3. In a Boolean algebra B, for all x, y Î B, prove that
   x £ y x * y = 0x' Å y = 1x * y = xx Å y = y.

1. 
   

fig ( i ) fig ( ii ) fig ( iii )

4. Show that in a Boolean algebra the following are equivalent for any a and b.
   ( i ) a' Ú b = 1
   ( ii ) a b' = 0.
   
5. The Boolean algebras (P (A₃), Ç , È, ', A₃, f) and D₃₀, where A₃ = {1,2,3} are (Boolean) isomorphic? Justify your
   answer.