Boolean algebra for logic gates

Boolean algebra is the mathematics which is used to create and simplify any complex logical (digital) circuits using logic gates. We can analyze a digital circuit and reduce the complexity of Boolean expression by using laws of Boolean. In Boolean algebra there can be only two values of any variable i.e. true and false or 1 and 0 like logic gates. There are three operations in Boolean algebra which are addition (OR), multiplication (AND) and complement (NOT). Let’s see an example to understand Boolean algebra by creating a logic circuit using logic gates according to Boolean expression.

Example: – X = A.B + C’

In this expression A, B and C are the input and X is output. Here “.” Sign is AND operation, “+” sign is OR operation and “ C’ ” is complement (NOT) of C. This expression means A and B are inputs of an AND gate and its output is one input of an OR gate, second input of this OR gate is complement of C.

Truth table of this circuit: –

Table of Contents

Boolean algebra for AND gate

It is multiplication of two binary digits. It is represented by dot (“.”) sign.

Important Rule: –

A.1 = A

If one input of an AND gate is one then output will be whatever it is present on other input.

A.0 = 0

If one input of an AND gate is 0 then output will be always 0.

Boolean algebra for OR gate

This is addition of binary digits. It is represented by “+” sign mark.

Important Rule: –

A+1 = 1

If one input of OR gate is 1 then output will be always 1.

A+0 = A

If one input of an OR gate is 0 then output will be whatever it is present on other input.

Boolean algebra for NOT gate

It just inverts the input. If input is 1 then output will 0 and if input is 0 then output will 1. It is represented by (’).

Important rule: –

(A’)’ = A

Input will be inverted in NOT operation. If we invert an input twice then we will get the same output which we have given to input.

All Boolean algebra rules at a sight

A+0 = A
A+1 = 1
A+A = A
A+A’ = 1
A.1 = A
A.0 = 0
A.A = A
(A +BC) = (A+B)(A+C)
(A+AB) = A
A(A+B) = (1+AB)
A+A’B = A+B
(A+B)(A+B’) = A
AB+A’C = (A+C)(A’+B)

The Boolean expression also follows the additive, distributive and commutative laws.

Additive, A+B = B+A

Distributive, A(B+C) = AB+AC

Commutative, A.B = B.A

De Morgan’s theorem

De Morgan’s deals with NOR and NAND gate

This theorem says that if two separate terms is inverted or NOR’ed together then it is equals to the two terms inverted and AND’ed.

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

If two inputs X and Y are NAND’ed together then it is equals to inverted X and Y are OR’ed.

For example: – (X.Y)’ = (X’ + Y’)

Boolean expression from truth table

There are two ways to obtain Boolean expression from a truth table.

Sum of products (SOP): –

In this method of forming expression consider ‘0’ as complement (X’) and ‘1’ as X. Now mark all 1 output in the truth table. Write down the conditions of input in the form of multiplication for every high output and sum it.

Example:-

A = XY’Z’ + XYZ’ + XYZ

It also can be represented as, F(X,Y,Z) = Σ(4,6,7)

Here 4, 6 and 7 represents that it is the place where high outputs are occurred.

Now, this expression which we obtained with the help of truth table is called canonical form of expression because all variables are present in every terms of expression. We can simplify this expression using “laws of Boolean algebra” which we have discussed.

A = XY’Z’ + XY(Z’+Z)

A = XY’Z’ + XY (Rule No. 4)

A = X(Y +Y’Z’)

A = X(Y + Z’) (Rule No. 11)

A = XY + XZ’

This is the minimal form of that canonical expression. With the help of this expression, now we can design a logical circuit easily.

Product of sum (POS): –

In this method, consider ‘1’ as complement. Mark all 0’s in truth table. Write down the input condition in the form of addition for every low output and multiply it.

Example:-

D = (A+B+C).(A+B’+C).(A+B’+C’)

It also can represented as F(A,B,C) = π(0,2,3)

Now, let’s simplify this expression.

D = (A+BB’+C).(A+B’+C’)

D = (A+C).(A+B’+C’)

According to rule number 8,

(A+B)(A+C) = A +BC

So, D=A+(B’+C’)C

D=A+B’C+C’C

D=A+B’C

D=(A+B’)(A+C)

Now, let’s design a circuit using this expression which follows the truth table above.

We have seen that how to convert a truth table into a Boolean expression and simplify them. Now, we will see how can we convert a minimal expression into canonical expression and make a truth table.

SOP (minimal to canonical form): –

If we multiply any number by 1, its value doesn’t change. Same thing we can apply here. Let’s see how,

Given, Y = A’ + BC

In this expression, there are three inputs variables – A,B and C. In the first term B and C, and in the second term A is not present. So, we will multiply (B+B’)(C+C’) in the first term and (A+A’) in second term.

Y = A’.1.1 + 1.B.C

Y = A’(B+B’)(C+C’) + (A+A’)BC

Y = (A’B + AB’)(C+C’) + ABC + A’BC

Y = A’BC+ A’BC’ + AB’C + AB’C’ + ABC + A’BC

Here A’BC came twice, so we will write it only once

Y = A’BC+ A’BC’ + AB’C + AB’C’ + ABC

At these five input conditions, output is high.

POS (minimal to canonical form):-

POS form is in the form product of all input’s addition at which low output occurs. So, if any input variable is missing in the addition in minimal expression we can add 0 ( means that input multiplied with complement of that input). For an example,

Given, X = (A+B’)(A+C)

In the expression given above, there are three input variables – A, B and C. In the first term variable C is missing and in the second term variable B is missing. So, we will add CC’ in the first term and BB’ in second term.

X = (A+B’+CC’)(A+BB’+C)

X = (A+B’+C) (A+B’+C’) (A+B+C) (A+B’+C)

X = (A+B’+C) (A+B’+C’) (A+B+C)

At these three input conditions, output is low.