Boolean Algebra





Boolean Algebra


Just like sets and logic, Boolean algebra is a modern concept. It is concerned with statements which are either true or false. It was George Boolen who developed this theory and its significance was realized when Claude Shanon introduced circuit algebra to deal with relay circuits in 1938. The digital computer which contains a large number of logic circuits in small space and works in switching them opened a wide field for this algebra and its recognition as significant part of modern mathematics.

 

Definition

 

A non-empty set B = (a, b, c …..) with two binary operations OR or JOIN denoted by +), AND or meet (denoted by \bullet) and a unary operation complement (denoted by’) is a Boolean Algebra if the elements satisfy the following axioms:

B.I. commutative law,

(i)a + b = b + a

(ii) a.b = b.a

 

B II. Distributive law,

(i)a.(b + c) =a.b + a.c

(ii) a+(b.c) = (a + b).(a + c)

 

B III. Existence of identity elements,

There exist elements, 0, \in B such that

a + 0 = a

a.1 =a

 

B IV. Existence of complements,

a + a’ = 1

a.a’ = 1

a.a’ = 0

we may note here that associative property has not been assumed in the above definition but will be derived from the above definition but will be derived from the above axioms. Also the distributive law (ii) is different from ordinary algebra applied to numbers and the reader is advised to familiarize himself fully with this property applied both was, the uniqueness of the identity elements and the complement shall be proved later on. There is great similarity among the set theory, logic and Boolean Algebra as shown below

Set theory Logic Boolean Algebra
Union \bigcup V +
Intersection \bigcap ^ \bullet
Complement \sim
Universal set S T 1
Null set \emptyset F 0
Implication Mapping p \to P’ + q
Equivalence One-one mapping p \leftrightarrow q[/latex] P’q’ + pq

 

 

Some properties

 

Now we shall prove some properties of Boolean algebra.

 

Theorem I : the two identity elements are unique.

Proof: suppose if possible there are two zero elements 0_1 \text{and} 0_2 in B. THEN

0_1 + 0_2 = 0_1

And 0_2 + 0_1 = 0_2  (B II)

But 0_1 + 0_2 = 0_2 + 1 (B I)

Hence 0_1 = 0_2

Similarly we can prove for the second identity 1.

 

Theorem II: a + a = a and a.a = a (indemptent laws)

 

Proof: a  = a + 0 = a+ (a. a’) (B IV)

= (a + a). (a +a’) (B II)

= (a + a).1

= a +a

Also a = a.1

= a.(a +a’)

= a.(a + a.a’

= a.a + 0 = a.a

 

Theorem III: form every element a \in B

A + 1 = 1, a.0 = 0.

 

Proof: 1 = a + a’

= a + (a’.1) = (a + 1).(a + a’)

= (a + 1).1 = a+ 1

Also

0 = a.a’ (B IV)

= a.(a’ + 0)  (B III)

= a.a’ + a.0   (B II)

= 0 + A.0  (B IV)

= a.0

 

Theorem IV: (Absorption laws)

A + (a.b) = a and a.(a + b) = a.

 

Proof:

a =  a.1

= a.(1 + b)

= (a.1) + (a.b) (B II)

= a + a.b

Also

a. (a + b) a.a + a.b

= a + a.b  (Th. II)

= a

 

\left( \begin{array}{c} a + x = a + y \\ a^{\prime} + x = a^{\prime} + y \end{array} \right)\Rightarrow x = y

 

And

\left( \begin{array}{c} a.x = a.y \\ a^{\prime}.x = a^{\prime}.y\end{array} \right)\Rightarrow x = y

 

Proof : we prove the first implication,

(a + x).(a’ + x) = a.a’ + x  (B II)

= 0 + x = x

(a + y).(a’ + y) = a.a’ + y

= 0 + y = y

\therefore (a + x).(a’ +x) = (a + y).(a’ + y)

\Rightarrow x = y

 

Similarly a.x + a’.x = (a + a’).x

= 1.x = x

 

And a.y + a’.y = (a + a’).y

= 1.y = y

Implying x = y

 

Theorem VI: addition and multiplication are associative,

i.e., a + (b + c) = (a + b) + c and a.(b.c) = (a.b).c

 

proof: Let a + (b + c) x, (a + b) + c = y.

Then a.x = a.{a+ (b + c)}

=a’    ( Th. IV)

 

And

a.y = a.{(a + b) + c}

= a.(a + b) + a.c

= a + a.c = a

 

Also x = a’.{a + (b + c)}

= a’.a + a’.(b + c)

= 0 + a’ .(b + c)

= a’.(b + c)

 

And

a’.y = a’.{(a + b) + c}

=a’. (a + b) + a’. c

= {a’.a + a’.b} + a’.c

= {0 + a’.b} + a’ .c

= a’. b + a’.c = a’.(b + c)

 

Hence a.x = a. y and a’.x = a’.y

\Rightarrow x = y   (Th. V)

Also let a.(b . c) = p and (a . b) . c = q

 

Then  a + p = a + a(a.(b.c)}   (B II)

= (a + a). (a + b.c)

= a.(a + b.c)

= a    (Th. IV)

 

Also a + q = a- {(a.c).c}

= (a + a.b).(a + c)   (B II)

= a.(+c)

= a . a + a.c

= x = a.c = c

 

a’ + p = a’ + {a, (b, c)}

= (a’ + a).(a’ + b.c)

= 1.(a’ +b .c) + a’ + b.c

= (a’ + b). (a’ + c)

= {1 .(a’ + b).(a’ + c)}

= {(a + a’). (a’ + b)}. (a’ + c)

= (a’ +a.b). (a’ +c)

= a’ + (a.b).c   (B II)

= a’ + q

 

Here a + p = a + q

And a’ + p = a’ + q

\Rightarrow p = q   (Th. V)

Note: some authors include associative law in the definition of Boolean Algebra.

 

Theorem VII. The complement of a \in B is uique.

 

Proof: let there are two complements a’ and a’’.

Then a + a’ = 1, a.a’ = 0

a + a’’ = 1, a.a’’ = 0

now a’ = 1.a’ = (a + a’’).a’

= a.a’ + a’’.a’

= 0 + a’’ . a’ = a.a’’ + a’’ .a’

=a’’.(a + a’) = a’’.1

= a’’

Here a’ is unique.

 

Theorem VIII (a’)’ = a

 

Proof : (a’)’ = a.a’ + (a’)’

= {a + (a’)’}. {a’ + (a’)’} …(B II)

= {a + (a’)’}.1

= {a + (a’)’}.{a + a’}

= a + (a’).a’ = a+ 0

=a

The theorem is direct result of B IV

 

Theorem IX: complements of identities

0’ = 1 and 1’ =0.

 

Proof: the proof follows from B III and B IV as

1 + 0 = 1 and 1.0 =0

 

Theorem X: de morgan’s law.

(a +b)’ = a’.b’

And (a.b)’ = a’ + b’

 

Proof:

(a’.b’).(a + b) = (a’.b’) . a + (a’.b’).b

= a’.(b’.a) + a’.(b’.b)  (Th. VI)

= a’.(a.b’) + a’.0

= (a’.a).b’ + 0 = 0.b’ + 0

= 0

Also (a’.b’) + (a + b) = (a’.b’ + a) + (a’ + b + b)

= (a + a’).(a + b’) + (a’ + b).(b’ + b)     (B II)

= 1.(a + b’) + (a’ + b).1

= (a + b’) + (b + a’)

= a + (b’ + b) + a’ = a  1 + a’

= a + a’ = 1

Hence a’.b’ is the complement of (a + b)

Also (a.b).(a’ + b’) = {(a.b).a’} + {(a.b).b’}

= {a’. (a.b)} + a. {(b.b’)}

= {(a’.a).b}  {a.0}

= 0.b + a.0 = 0 + 0 = 0

And  (a.b) + (a’ + b’) = (a’ + b’) + (a.b)

= {(a’ + b’) + a}.{(a’ + b’) + b}

= {a + (a’ + b’)}.{a’ + (a’ + (b’ + b)}

= {(a + a’) + b’}. {a’ + 1}

= (1 + b’). (a’ + 1) = 1.1 = 1

Hence a’ +b’ is the complement of a.b.

 

Duality

 

Any result that is obtained from the axioms of Boolean Algebra remains true if  + and \bullet are interchanged along with the interchange of 0 and 1 throughout the statement of the results.

 

Partial ordering

 

Just like inclusion of a set into another set as the case of subsets, we have the idea of partial ordering in Booleean algebra. Thus

a \leq b if a.b = a,a,b \in B

Or a + b = b

It can also be stated as

a \leq b if a.b’ =0

And a \leq if b^{\prime} \leq a^{\prime}

With the above notation we define as:

If ( B, + \bullet, … 0, 1) is a Boolean algebra, then (B, \leq) is a partially ordered set with greatest element 1 and least element 0. Moreover each pair {a, b} of elemtns has a least upper bound a + b and a greatest lower bound a \bullet b

 

Switching algebra

 

The knowledge of Boolean algebra received recognition mainly due to its application in electrical circuits C.E. Shanon in his paper in 1938 was the first to introduce circuit algebra as method of dealing algebraically with relay circuits. The emergence of digital computers brought this system into significance as a part of pure mathematics applied to electrical engineering.

With the symbols in the beginning of the chapter, we consider the system [0,1] +, \bullet]. The system is a Boolean with the composition tables.

 

Also 0’ 1 and 1’ = 0. In an electrical circuit if a switch is closed (or on) we denote it by 1 and when it is open (or off), it will be denoted by 0.

Switches in parallel are denoted by + and in series by \bullet. Thus

The above figure gives two switches in parallel and the truth table is as under:

x y x+ y
0

0

1

1

0

1

1

1

0

0

0

1

 

Hence we see that the current does not flow only in the case when both the switches are open.

Switches in series are denoted by \bullet. The figure of two switches in series is

The truth table is as under:

x y x+ y
0

0

1

1

0

1

1

1

0

0

0

1

 

In this case, the current flows in the case when both the switches are closed.

Some other circuits are below shown:

Draw figures to show the following equivalence of switches:

(i)x.y = y.x

(ii) x+ y = y + x

(iii) x + y .z = (x  + y). (x + z)

(iv) x.(y + z) = x.y + x.z

(v) x + x’ = 1 and x.x’ = 0

(vi) x + (y +z) = (x + y) + z

(vii) x.(y.z) = (x.y).z

 

In the above, we have studied cases where the switches are either open or closed independent of each other. Now we shall see same cases where x represents the closed switch and x’ the open in the same circuit.

 

The Two Switch Problem: we have to design a circuit such that the light of a bulb can be turned on or off by the change in state of any of the two switches in the circuit. The figure is shown below:

There are tow switches S_1 \text{and} S_2 different from ordinary switches as they have two way contacts. While x_1 state closes B and opens EF, x_1 closes EF and opens AB, similar is the case with S_2 so that the current flows in the state

f(x_1, x_2) = x_1x_2^{\prime} + x_2x_1^{\prime}

 

If the circuit is on with either x_1x_2^{\prime} \; or \; x_2x_1^{\prime} a change in any switch will make the circuit off. Again any change in the state of any of the switches will make the circuit on. We can write

f(x_1, x_2) = (x_1 + x_2) (x_1^{\prime} + x_2^{\prime} \\ = (x_1/x_2 = (x_2/x_1)

 

A three switch can be designed as

f(x_1, x_2, x_3) = x_1x_2^{\prime} x_3^{\prime} + x_1^{\prime} x_2 x_3^{\prime} + x_1^{\prime}x_2^{\prime}x_3 + x_1x_2x_3 \\ = x_1/x_2/x_3 \\ = (x_1/x_2)x_3^{\prime} + (x_1^{\prime}/x_2)x_3

 

A n switch circuit can similarly be designed.

 

Truth table

 

The truth of the above Boolean relations can also be shown with the help of a truth table. If a variable x is denoted by 1, x’ is denoted by 0. For + sometimes \bigcup \; or \; \vee, and similarly for \bigcap \; or \; \wedge are used. Thus to prove the relation a(a + b) = a, we form the table

a b a + b a.(a + b)
1

1

0

0

1

0

1

0

1

1

1

0

1

1

0

0

 

Duality: Another definition

 

In every (correct) formula of Boolean algebra, we can interchange addition and multiplication. However when an equality fulfills the laws of Boolean Algebra involves the ‘special’ elements 0 and 1, then the interchange of Boolean addition and multiplication in this equality must be followed by the interchange of elements 0 and 1. For instance the validity of

(A + B) (A + 1) + (A + B) (B + 0) = A + B

Results in

(AB + A0). (AB +B1) = AB



Related posts:

  1. Boolean Algebra Associated, Distributive, and Commutative Law are described below individually :...
  2. Introduction to Logic Function and Boolean Algebra The binary numbers are basic building block of all computer...
  3. Boolean Function Boolean Function: A Boolean function is an expression formed with...
  4. Distance Formula Basic Distance Formula. Distance formula to calculate distance between two...
  5. Partial Differentiation Defination of Partial Differentiation   If f is a function...