In the previous blog, we learned about the Digital Circuit and Logic Gates. This time we will learn about Boolean Algebra, Gates and their truth tables, DeMorgan’s Theorem, and Compliment of a function.
Let’s Get Started!
Gates and their Truth table
What is Boolean Algebra in Computer?
Boolean Algebra is algebra of two sets; Set A and Set B, with either of three operands AND operation, OR operation and NOT operation.
Boolean functions use multiple binary variables, logic operation symbols, parenthesis, and equal sign. The boolean function can be 0 or 1 depending on the given values. For example: F = x + y’z
Boolean Algebra Truth Table
The relationship between the binary variable and function is represented in the Truth Table of the function. To represent a function in truth table we need to make a list of 2n combinations of n binary variables.
A boolean function can be transformed into a logic diagram from the algebraic expression. Let us see an example of a truth table and its logic diagram of the function, F = x + y’z below:
Sometimes boolean expressions are not in their simplified state. It can be manipulated to bring it to its simplified state. To see this, lets consider an another expression, F(A, B, C) = A’BC + A’BC’ + ABC’ + AB’C’ + A’B’C’ + ABC.
F = A'BC + A'BC' + ABC' + AB'C' + A'B'C' + ABC = A'BC + A'BC' +ABC' + AB'C' + A'BC' + A'B'C' + ABC = A'B(C + C') + (A + A')(B + B')C' + ABC (where, x+x'=1 is a basic identity of boolean algebra) = A'B + C' + ABC
So, you see… you can manipulate any boolean expression to obtain a simple expression that will require fewer gates. But you must also keep in mind that expressions are manipulated according to Boolean algebra rules. The table below will help you with the basic identities of Boolean algebra.
DeMorgan’s Theorem – Boolean Algebra
DeMorgan’s Theorem is very important in dealing with NAND and NOR gates. According to this theorem NOR gate performs (x + y +z)’ = x’y’z’.
Similarly NAND gate performs (xyz)’= (x’ +y’+z’).
In the above figure, you can see that there can be two graphic symbols for NOR and NAND gate. NOR and NAND gates can also be used to implement any Boolean function, including basic logic gates such as AND, OR, and NOT. Therefore, NAND Gates and NOR Gates are also called Universal Gates.
Now let’s see how boolean function manipulation can be used to simplify the digital circuit. For this let’s consider a boolean function, we’ll also see the corresponding digital circuit along with simplification.
The complement of a Function – Boolean Algebra
As we all know, a boolean function returns either 0 or 1. So, if a function F returns 1 as its result, then its function F’ will return 0 as its complement. The Complement of a function can be derived with the help of DeMorgan’s Theorem.
The general form of DeMorgan’s theorem :
(x1 + x2 + x3 + ... + xn )' = x1' + x2' + x3' + ... + xn' (x1x2x3...xn)' = x1' + x2' + x3' + ... xn'
To understand this, let us take an example;
F = AB + C'D' + B'D F' = (A' + B')(C + D)(B + D')
Note: The complement of a function can be obtained by interchanging AND with OR operations and vice-versa and complementing each individual variables.
If you are interested in illustrations and graphics than you must check our blogs on Adobe Illustrator.
My enthusiasm for hardware and software knowledge has brought me toward this blogging profession. I am a BCA student studing at BIT Mesra.