Home » BOOLEAN ALGEBRA » BOOLEAN ALGEBRA

BOOLEAN ALGEBRA

Long ago Aristotle constructed a complete system of formal logic and wrote six famous works on the subject, contributing greatly to the organization of man’s reasoning. For centuries afterward, mathematician kept on trying to solve these logic problems using conventional algebra but only George Boole could manipulate these symbols successfully to arrive at a solution with his own mathematical system of logic. Boole’s revolutionary paper “An Investigation of the laws of the though” was published in 1854 which led to the development of new system, the algebra of logic, “BOOLEAN ALGEBRA”. Boole’s work remained confined to paper only until 1938 when Claude E. Shannon wrote a paper titled ‘A Symbolic Analysis of Relay Switching Circuit’. In this paper he applied Boolean algebra to solve relay logic problems. As logic problems are binary decisions and Boolean algebra effectively deals with these binary values. Thus it is also called ‘Switching Algebra’.

DEFINITION OF BOOLEAN ALGEBRA

A Boolean Algebra is an algebra (set, operation, elements) consisting of a set B with ≥2 elements, together with three operations –the AND operation (Boolean Product), the OR operation (Boolean Sum), and the NOT operation (complement) –defined on the set. Let us consider the two-element Boolean algebra B2 = ({0, 1}; ., +,’ ;0, 1).The three operations . (AND), + (OR), ‘(NOT) are defined as follows:

TABLE ONE TABLE TWO TABLE THREE
. 0 1 + 0 1
0 0 0 0 0 1 0 1
1 0 1 1 1 1 1 0

Boolean algebra is a switching algebra that deals with binary variables and logic operations. The variables are designated by letters such as A, B, x, and y. The three basic logic operations are AND, OR, and NOT.A Boolean function can be expressed algebraically with binary variables, the logic operation symbols, parentheses, and equal sign. For a given value of the variables, the Boolean function can be either 1 or 0.The relationship between a function and its binary variables can be represented in a truth table. To represent a function in a truth table we need a list of 2n combinations of the n binary variables. A Boolean function can be transformed from an algebraic expression into a logic diagram of AND, OR, and NOT gates.

For example:- If F = X+Y’Z then its truth table and block diagram is shown below.

INPUT OUTPUT
X Y Z F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

THE PURPOSE OF BOOLEAN ALGEBRA

The purpose of Boolean algebra is to facilitate the analysis and design of digital circuits. It provides a conventional tool to:

  1. Express in algebraic form a truth table relationship between binary variables.
  2. Express in algebraic form the input-output relationship of logic diagrams.
  3. Find simpler circuit for the same function.

POSTULATES OF BOOLEAN ALGEBRA

Postulate1:-

A = 0 if and only if A is not equal to 1
A = 1 if and only if A is not equal to 0

Postulate2:-

X+0 = X
X.1 = X

Postulate3:- Commutative Law

X+Y = X+Y
X.Y = Y.X

Postulate4:- Associative Law

X+(Y+Z) = (X+Y)+Z
X.(Y.Z) = (X.Y).Z

Postulate5:- Distributive Law

X.(Y+Z) = X.Y+X.Z
X+Y.Z = (X+Y).(X+Z)

Postulate6:-

X+X’=1
X.X’=0

The postulates listed above are the basic axioms of the algebraic structure and need no proof.

COMPLEMENT OF A BOOLEAN FUNCTION

The complement of a Boolean function F is F’ and is obtained by interchange 0’s for 1’s and 1’s for 0’s in the truth table that defines the function.
F = XY’+X’Z

X Y Z F F’
0 0 0 0 1
0 0 1 1 0
0 1 0 0 1
0 1 1 1 0
1 0 0 1 0
1 0 1 1 0
1 1 0 0 1
1 1 1 0 1

Algebraically, the complement of a function may be derived through De Morgan’s Theorems whose generalized forms are as follows:

(A1+A2+A3+A4+……………+An)’ = A’1.A’2.A’3………..A’n
(A1.A2 .A3………………………An) = A’1+A’2+A’3+………+A’n

These theorems state that the complement of a function is obtained by interchanging the OR and the AND operators and complementing each literal. The method is illustrated below through an example.

Example1:- Find the complement of the function F = A’B’+AB?

Solution:- Applying De Morgan’s theorem as many times as necessary, the complement of the Boolean function is as obtained. Let F’ denotes the complement function of the function F.
F’
= (A’B’+AB)’
= (A’B’)’(AB)’
= [(A’)’+(B’)’](A’+B’)
= (A+B)(A’+B’)
This is the required result.

Let us take another example to have better understanding of the complementing operation.

Example2:- Find the complement of the function F = AB+(A’B’)(BC+B’C’)

Solution:- As in the above problem we have used De Morgan’s theorem repeatedly we also apply them here.
F = AB+(A’B’)(BC+B’C’)
F’ = [AB+(A’B’)(BC+B’C’)]
F’ = (AB)’[(A’B’)(BC+B’C’)]
F’ = (A’+B’)[(A’B’)’+(BC+B’C’)’]
F’ = (A’+B’)[(A+B)+(BC)’(B’C’)’]
F’ = (A’+B’)[(A+B)+(B’+C’)(B+C)]
F’ = (A’+B’)(A+B)+(A’+B’)(B’+C’)(B+C)
This is the required complement of the above Boolean function.

THEOREMS OF BOOLEAN ALGEBRA

There are six theorems or identities in the Boolean algebra which are listed below along with their proof by using above postulates. These identities or theorem can also be proved by means of truth tables. The theorems are as follows:

THEOREM 1 (IDEMPOTENT LAW)

X+X=X
X.X=X

Proof of the first Idempotent law by using postulates:

Left Hand Side
X+X = (X+X).1              [BY POSTULATE 2]
= (X+X).(X+X’)              [BY POSTULATE 6]
= X+XX’                         [BY POSTULATE 5]
= X+0                             [BY POSTULATE 6]
= X                                 [BY POSTULATE 2]

Hence, left hand side is equal to right hand side.

Proof of the first Idempotent law by means of truth table:

Truth table for the first law is written below.

INPUT VARIABLES L.H.S. R.H.S.
X X X+X X
0 0 0 0
1 1 1 1

Thus from the truth table we can see that left hand side and right hand side of the equation are same. Hence the equation is true.

Proof of the second idempotent law by using postulates:

Left Hand Side
X.X = X.X+0                                [BY POSTULATE 2]
= X.X+X.X’                                  [BY POSTULATE 6]
= X.(X+X’)                                   [BY POSTULATE 5]
= X.1                                           [BY POSTULATE 6]
= X                                               [BY POSTULATE 1]
Thus left hand side is equal to right hand side.

Proof of the Second Idempotent law by means of truth table:

Truth table for the second law is written below.

INPUT VARIABLES L.H.S. R.H.S.
X X X.X X
0 0 0 0
1 1 1 1

Since the left and right hand sides are equal thus second Idempotent law holds.

THEOREM 2:

X+1=1
X.0=0

Proof of the first part of second theorem by using postulates:

Left Hand Side
X+1 = (X+1).1                           [BY POSTULATE 2
= (X+1).(X+X’)                           [BY POSTULATE 6]
= X+X’.1                                    [BY POSTULATE 5]
= X+X’                                        [BY POSTULATE 2]
= 1                                              [BY POSTULATE 6]
Hence LHS is equal to RHS.

Proof of the second part of the second theorem:

Left Hand Side
X.0 = X.0+0                                [BY POSTULATE 2
= X.0+X.X’                                  [BY POSTULATE 6]
= X.(0+X’)                                   [BY POSTULATE 5]
= X.X’                                          [BY POSTULATE 2]
= 0                                               [BY POSTULATE 6]
Left hand side is equal right hand side.

THEOREM 3 (ABSORPTION LAW)

X+X.Y = X
X.(X+Y) = X

Proof of the first Absorption law by using postulates theorem:

Left Hand Side
X+X.Y = X.1+X.Y       [BY POSTULATE 2]
= X.(1+Y)                   [BY POSTULATE 5]
= X.1                          [BY THEOREM 2]
= X                             [BY POSTULATE 2]
Hence left and right sides of the Boolean equation are equal.

Proof by the method of perfect induction:

This theorem of Boolean algebra can also be proved by means of truth tables. In a truth table both side of the relation are checked to yield identical result for all possible combinations of the variables involved.

X Y X.Y X+X.Y
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1

 In the above truth table it is proved that both sides of the Boolean identity is same as the left and right side have same values for their corresponding positions.

Proof of the second theorem of the Absorption:

Left Hand Side
X.(X+Y) = X.(X+Y)+0          [BY POSTULATE 2]
= X.(X+Y)+XX’                    [BY POSTULATE 6]
= X.(X+Y+X’)                      [BY POSTULATE 5]
= X.(X+X’+Y)                      [BY POSTULATE 4]
= X.(1+Y)                            [BY POSTULATE 6]
=X.1                                    [BY THEOREM 2]
= X                                      [BY POSTULATE 2]

Proof of the Second law of Absorption by method of Truth Table:

X Y X+Y X.(X+Y)
0 0 0 0
0 1 1 0
1 0 1 1
1 1 1 1

The above table proves the second theorem of the Absorption law of Boolean identities.

THEOREM 4 (INVOLUTION LAW)

(X’)’ = X
This theorem is proved by the method of perfect induction below.

X X’ (X’)’
0 1 0
1 0 1

Note that theorem 4 has no dual since it deals with the NOT operator which is unary operator.

THEOREM 5

X.(X’+Y) = X.Y
X+X’Y = X+Y

Proof of the first part of the theorem five by using postulates and theorem:

Left Hand Side
X.(X’+Y) = X.X’+X.Y             [BY POSTULATE 5]
= 0+X.Y                                [BY POSTULATE 6]
= X.Y                                    [BY POSTULATE 2]

Since the left hand side and right hand side of the Boolean identity are same. Thus this Boolean identity holds.

Proof of the second part of the theorem five:

Left Hand Side
X+X’.Y = (X+X’).(X+Y)           [BY POSTULATE 5]
= 1.(X+Y)                               [BY POSTULATE 6]
= X+Y                                    [BY POSTULATE 2]
Here left and right sides are same thus this Boolean theorem also holds.

These theorems can also be proved by the method of induction as above theorems have been proved.

THEOREM 6 (DE MORGAN’S THEOREM)

(X+Y) = X’.Y’
(X.Y) = X’+Y’

This theorem is not discussed here in detail. This topic is coved in another page so to read about this topic goes to link given below.

DUAL OF A BOOLEAN FUNCTION

In Boolean algebra there is a precise duality between the operators AND and OR and the digits 0 and 1. This important property is known as the principle of duality in Boolean algebra. The dual of a Boolean function can be found by interchanging ‘+’ with ‘.’ and ‘0’ with ‘1’, some example are elaborated below.

Example 1:- Find the dual of the Boolean function F = A’+B’?

Solution:- Here the Boolean function is as F = A’+B’.

The dual of the function is found by interchanging only AND operator (+) and OR operators (.). Hence the dual of the Boolean function is as X = A’.B’ where X denotes the dual of the Boolean function.

Example 2:- Find the dual of the Boolean function F = (A’+B’).(A+C).(B+C’)?

Solution:- The Boolean function is F = (A’+B’).(A+C).(B+C’).
Now the dual of the function X = (A’.B’)+(A.C)+(B.C’) here X is the dual of the Boolean function.

Example 3:- Find the dual of the Boolean function F = (X’.Y.Z)+(X.Y’.Z)+(X.Y.Z’)+(X.Y.Z)?

Solution:- The Boolean function F = (X’.Y.Z)+(X.Y’.Z)+(X.Y.Z’)+(X.Y.Z).
The dual of the Boolean function F is given as:
X = (X’+Y+Z).(X+Y’+Z).(X+Y+Z’).(X+Y+Z) where X is used to denote dual of the function.

Example 4:- Find the dual of the Boolean function F = A+A.B+A’.C?

Solution:- The Boolean function is F = A+A.B+A’.C.
The dual is X = A.(A+B).(A’+C) where X is the dual of the Boolean function F.

MINIMIZATION OF A BOOLEAN FUNCTION

Minimization of a Boolean function can be achieved by two simple ways. These two methods are as:

  1. By using Boolean theorems and postulates.
  2. By using Map Simplification.

At first we will go through the first method. Let us take an example to understand the process.

Example 1:- Simplify the algebraic expression using Boolean algebra?

F = XY’Z+X’Y’Z+XYZ

Solution:- Here,
F = XY’Z+X’Y’Z+XYZ
F = XY’Z+XYZ+X’Y’Z          [BY POSTULATE 4]
F = XZ(Y’+Y)+X’Y’Z             [BY POSTULATE 5]
F = XZ(Y+Y’)+X’Y’Z             [BY POSTULATE 3]
F = XZ.1+X’Y’Z                     [BY POSTULATE 6]
F = XZ+X’Y’Z                        [BY POSTULATE 1]
F = Z(X+X’Y’)                        [BY POSTULATE 5]
F = Z(X+X’)(X+Y’)                [BY POSTULATE 5]
F = Z.1(X+Y’)                        [BY POSTULATE 6]
F = Z(X+Y’)                            [BY POSTULATE 1]
F = ZX+ZY’                            [BY POSTULATE 5]
F = XZ+Y’Z                            [BY POSTULATE 3]
This the minimized form of the Boolean function F.

Example 2:- Minimize the Boolean function F = X’Z’+Y’Z’+YZ’+XY?

Solution:- Here,
F = X’Z’+Y’Z’+YZ’+XY
F = X’Z’+Z’(Z’+Z)+XY          [BY POSTULATE 5]
F = X’Z’+Z’(Z+Z’)+XY          [BY POSTULATE 3]
F = X’Z’+Z’.1+XY                 [BY POSTULATE 6]
F = X’Z’+Z’+XY                     [BY POSTULATE 1]
F = X’Z’+Z’.1+XY                 [BY POSTULATE 1]
F = Z’(X’+1)+XY                   [BY POSTULATE 5]
F = Z’.1+XY                           [BY THEOREM 2]
F = Z’+XY                              [BY POSTULATE 1]
This is the required minimized result of the function.

Example 3:- Minimize the following algebraic expression F = A’B+ABC’+ABC?

Solution:- Since,
F = A’B+ABC’+ABC
F = A’B+AB(C+C’)                [BY POSTULATE 5]
F = A’B+AB.1                        [BY POSTULATE 6]
F = A’B+AB                           [BY POSTULATE 1]
F = B(A’+A)                           [BY POSTULATE 5]
F = B(A+A’)                           [BY POSTULATE 3]
F = B.1                                   [BY POSTULATE 6]
F = B                                      [BY POSTULATE 1]
Hence this is the required result of the Boolean function.

Related Posts

  • HALF ADDERHALF ADDER The most basic digital arithmetic circuit is the addition of two binary numbers. A combinational circuit that performs the addition of two bits is called a half adder. One that […] Posted in BOOLEAN ALGEBRA
  • FULL ADDERFULL ADDER A full adder is a combinational circuit that forms the arithmetic sum of three input bits. A full adder consists of three inputs and two outputs. Two of the input variables full adder, […] Posted in BOOLEAN ALGEBRA
  • 15’S AND 16’S COMPLEMENTS OF HEXADECIMAL NUMBERS15’S AND 16’S COMPLEMENTS OF HEXADECIMAL NUMBERS 15’S AND 16’S COMPLEMENTS OF HEXADECIMAL NUMBERSAs we find 1’s and 2’s complement of binary numbers or 7’s and 8’s complement of octal numbers in the same manner we can also find only 15’s […] Posted in NUMBER SYSTEM
  • 1’S AND 2’S COMPLEMENT OF BINARY NUMBER1’S AND 2’S COMPLEMENT OF BINARY NUMBER 1'S COMPLEMENT OF BINARY NUMBER OR UNSIGNED BINARY NUMBERS: There is a simple way to find the 1's complement of binary number or unsigned binary numbers. 1's complement of binary number […] Posted in NUMBER SYSTEM