Digital Circuits - Boolean Algebra
Boolean Algebra is an algebra, which deals with binary numbers & binary variables. Hence, it is also called as Binary Algebra or logical Algebra. A mathematician, named George Boole had developed this algebra in 1854. The variables used in this algebra are also called as Boolean variables.
The range of voltages corresponding to Logic ‘High’ is represented with ‘1’ and the range of voltages corresponding to logic ‘Low’ is represented with ‘0’.
Postulates and Basic Laws of Boolean Algebra
In this section, let us discuss about the Boolean postulates and basic laws that are used in Boolean algebra. These are useful in minimizing Boolean functions.
Boolean Postulates
Consider the binary numbers 0 and 1, Boolean variable (x) and its complement (x’). Either the Boolean variable or complement of it is known as literal. The four possible logical OR operations among these literals and binary numbers are shown below.
x + 0 = x
x + 1 = 1
x + x = x
x + x’ = 1
Similarly, the four possible logical AND operations among those literals and binary numbers are shown below.
x.1 = x
x.0 = 0
x.x = x
x.x’ = 0
These are the simple Boolean postulates. We can verify these postulates easily, by substituting the Boolean variable with ‘0’ or ‘1’.
Note− The complement of complement of any Boolean variable is equal to the variable itself. i.e., (x’)’=x.
Basic Laws of Boolean Algebra
Following are the three basic laws of Boolean Algebra.
Commutative Law
If any logical operation of two Boolean variables give the same result irrespective of the order of those two variables, then that logical operation is said to be Commutative. The logical OR & logical AND operations of two Boolean variables x & y are shown below
x + y = y + x
x.y = y.x
The symbol ‘+’ indicates logical OR operation. Similarly, the symbol ‘.’ indicates logical AND operation and it is optional to represent. Commutative law obeys for logical OR & logical AND operations.
Associative Law
If a logical operation of any two Boolean variables is performed first and then the same operation is performed with the remaining variable gives the same result, then that logical operation is said to be Associative. The logical OR & logical AND operations of three Boolean variables x, y & z are shown below.
x + (y + z) = (x + y) + z
x.(y.z) = (x.y).z
Associative law obeys for logical OR & logical AND operations.
Distributive Law
If any logical operation can be distributed to all the terms present in the Boolean function, then that logical operation is said to be Distributive. The distribution of logical OR & logical AND operations of three Boolean variables x, y & z are shown below.
x.(y + z) = x.y + x.z
x + (y.z) = (x+y).(x+z)
Distributive law obeys for logical OR and logical AND operations.
These are the Basic laws of Boolean algebra. We can verify these laws easily, by substituting the Boolean variables with ‘0’ or ‘1’.
Theorems of Boolean Algebra
The following two theorems are used in Boolean algebra.
Duality Theorem
This theorem states that the dual of the Boolean function is obtained by interchanging the logical AND operator with logical OR operator and zeros with ones. For every Boolean function, there will be a corresponding Dual function.
Let us make the Boolean equations (relations) that we discussed in the section of Boolean postulates and basic laws into two groups. The following table shows these two groups.
Group1 | Group2 |
x + 0 = x | x.1 = x |
x + 1 = 1 | x.0 = 0 |
x + x = x | x.x = x |
x + x’ = 1 | x.x’ = 0 |
x + y = y + x | x.y = y.x |
x + (y + z) = (x + y) + z | x.(y.z) = (x.y).z |
x.(y + z) = x.y + x.z | x + (y.z) = (x+y).(x+z) |
In each row, there are two Boolean equations and they are dual to each other. We can verify all these Boolean equations of Group1 and Group2 by using duality theorem.
DeMorgan’s Theorem
This theorem is useful in finding the complement of Boolean function. It states that the complement of logical OR of at least two Boolean variables is equal to the logical AND of each complemented variable.
DeMorgan’s theorem with 2 Boolean variables x and y can be represented as
(x + y)’ = x’.y’
The dual of the above Boolean function is
(x.y)’ = x’ + y’
Therefore, the complement of logical AND of two Boolean variables is equal to the logical OR of each complemented variable. Similarly, we can apply DeMorgan’s theorem for more than 2 Boolean variables also.
Simplification of Boolean Functions
Till now, we discussed the postulates, basic laws and theorems of Boolean algebra. Now, let us simplify some Boolean functions.
Example 1
Let us simplify the Boolean function, f=p’qr + pq’r + pqr’ + pqr
We can simplify this function in two methods.
Method 1
Given Boolean function, f=p’qr + pq’r + pqr’ +pqr.
Step 1 − In first and second terms r is common and in third and fourth terms pq is common. So, take the common terms by using Distributive law.
⇒ f= (p’q + pq’)r + pq(r’+r)
Step 2 − The terms present in first parenthesis can be simplified to Ex-OR operation. The terms present in second parenthesis can be simplified to ‘1’ using Boolean postulate
⇒ f=(p ⊕q)r+pq(1)
Step 3 − The first term can’t be simplified further. But, the second term can be simplified to pq using Boolean postulate.
⇒ f=(p ⊕q)r+pq
Therefore, the simplified Boolean function is f= (p⊕q)r + pq
Method 2
Given Boolean function, f=p’qr + pq’r + pqr’ +pqr.
Step 1 − Use the Boolean postulate, x + x = x. That means, the Logical OR operation with any Boolean variable ‘n’ times will be equal to the same variable. So, we can write the last term pqr two more times.
⇒ f= p’qr + pq’r + pqr’ + pqr + pqr + pqr
Step 2 − Use Distributive law for 1st and 4th terms, 2nd and 5th terms, 3rdand 6th terms.
⇒ f= qr(p’ + p) + pr(q’+q) + pq(r’+r)
Step 3 − Use Boolean postulate, x + x’ = 1 for simplifying the terms present in each parenthesis.
⇒ f= qr(1) + pr(1) + pq(1)
Step 4 − Use Boolean postulate, x.1 = x for simplifying the above three terms.
⇒ f = qr + pr + pq
⇒ f = pq + qr + pr
Therefore, the simplified Boolean function is f= pq + qr + pr.
So, we got two different Boolean functions after simplifying the given Boolean function in each method. Functionally, those two Boolean functions are same. So, based on the requirement, we can choose one of those two Boolean functions.
Example 2
Let us find the complement of the Boolean function, f=p’q + pq’.
The complement of Boolean function is f’=(p’q + pq’)’.
Step 1 − Use DeMorgan’s theorem, (x + y)’ = x’.y’.
⇒ f’= (p’q)’.(pq’)’
Step 2 − Use DeMorgan’s theorem, (x.y)’ = x’+y’
⇒ f’= {(p’)’+q’}.{p’+(q’)’}
Step3 − Use the Boolean postulate, (x’)’=x.
⇒ f’= {p+q’}.{p’+q}
⇒ f’= pp’+pq+p’q’+qq’
Step 4 − Use the Boolean postulate, xx’=0.
⇒ f= 0 + pq +p’q’ + 0
⇒ f= pq +p’q’
Therefore, the complement of Boolean function, p’q+pq’ is pq+p’q’.