Algebraic Method for Combinational Logic, Physics tutorial


A logic circuit can be defined in the form of Boolean expression which, in turn, can be simplified using Boolean laws. A Boolean expression can also be transformed in the equivalent logic circuit. Whenever the logic circuit is explicitly stated by its truth table to give a fixed, invariant relationship between input and output, circuit is known as combinational circuit. The combinational circuit doesn't have memory. It always operates in accordance with its truth table in spite of of any previous input that may have been given to circuit. Boolean expression can be simplified in either of the two forms - (i) Sum of Product (SOP), and (ii) Product of Sum (POS). Object of simplification is to minimize number of variables or occurrences of the variable in expression. This signifies minimizing operation symbols and therefore the number of gates to be utilized in circuit. Several times, we get more than one simplified form of the expression, each being equivalent in number of gates and variables to be used. In final analysis, we shall utilize Minimum Sum of Product (MSP) form which is written without brackets. Consider reduced expression A (B + C) that is written in MSP form AB + AC. While reduced expression needs one AND gate and one OR gate, MSP expression needs one AND gates and one OR gate. Therefore in this situation MSP expression is not simplest. Fundamental rule is that expression should be (i) reduced as much as possible, and (ii) written without brackets. For simplification of Boolean expression, Boolean operations must be performed in given order:

i) Inversion of single variables.

ii) All operations with brackets.

iii) AND operations before OR operations.

iv) OR operations.

v) If the expression is with bar, then before inverting, carry out all operations.

E.g.: Find MSP expression for

Y = (A‾ + B‾)C‾ + AB‾

= (A‾ + B‾)C‾ + (A‾ + B‾) Using De Morgan's theorem Theorem

= (A‾ + B‾)(C‾ 1) Taking (A‾ + B‾) common

= (A‾ + B‾).1

= (A‾ + B‾)

= MSP expression

Getting the Truth Table from Boolean Expression:

Simple method of getting the truth table from Boolean expression is to substitute values of variables in each possible combination of values in expression. Carry out all logic operations and get result for each combination. For instance,

Y = AB + A (B + C) + B (B + C)

In this expression, say, A = 1, B = 0, and C = 0, then

Y = 1 . 0 + 1 . (0 + 0) + 0 (0 + 0)

= 0 + 1 . 0 + 0 . 0

= 0 + 0 + 0

= 0

Likewise, determine Y for all combinations of values for A, B, and C.

617_Truth table for expression.jpg

Getting Boolean Expression from a Truth Table:

Consider truth table

923_Boolean Expression from a Truth Table.jpg

Note, that entries 5, 7, and 8 give the logic 1 to operation whereas all other entries provide logic 0. To get Boolean expression, write product term for each entry that give a logic 1, and then assemble operations by connecting all products with logic

Entry 5: Y = 1 for A = 1, B = 0, C = 0

= AB‾C‾

As output of AND gate will be 1 only if all inputs are 1. Likewise

Entry 7: Y = 1 for A = 1, B = 1, C = 0 = ABC‾

Entry 8: Y = 1 for A = 1, B = 1, C = 1 = ABC

Now join all three products with OR logic. Therefore Y = AB‾C‾ + ABC‾ + ABC (Sum of Product), that can be simplified as

Y = AB‾C‾ + AB(C‾ + C)

= AB‾C‾ + AB

= A(B‾C‾ + B)

= A(B + C‾)

= AB + AC‾

Exclusive- OR (XOR) Gate:

XOR gate gives the high output (i.e. 1) when the odd number of inputs is high. Two-input exclusive - OR gate has its output 1 if one of two inputs is 1 and other is 0, and if both inputs are same then output is 0.

542_Truth table for XOR gate.jpg

Its Boolean expression is t is Y = A‾B + AB‾. This expression is in MSP form as it can't be simplified further. Therefore Y is output of OR gate inputs to which are A‾B and AB‾, which in turn are outputs of two AND gates. The XOR operation is expressed by ⊕.

1554_XOR gate.jpg

Exclusive -NOR (XNOR) Gate:

1599_XNOR gate.jpg

Exclusive-NOR gate has its output 1 if both inputs are same, and if both inputs are different then output is 0. Truth table of XNOR gate is:

1387_Truth table for XNOR gate.jpg

Its Boolean expression is:

Y = A‾B‾ + AB

Addition of Two One Bit Binary Numbers (Half Adder):

This application has two outputs, one for sum and another for carry. Thus, we have to get two Boolean expressions for two outputs.

Truth table for half adder

678_Truth table for half adder.jpg

Expression for carry is

Carry = AB that is, it is the output of an AND gate.

The expression for sum is

Sum = A‾B + AB‾

It is the output of XOR gate. These two circuits are connected together as shown. This circuit is known as half adder and its symbol is given below:

915_Half adder circuit and symbol.jpg

Addition of Three One Bit Binary Numbers (Full Adder):

Full adder can add three single-bit binary numbers. Binary addition three single-bit binary numbers is as follows:

Right hand bits of the additions represent sum and left hand bits represent the carry.

The eight possible combinations of three single-bit binary numbers can be presented in form of truth table


To design logic circuit for full adder, Boolean expressions have to be written and simplified in MSP form for both sum and carry, that are as follows:

Sum = A‾B‾C + A‾BC‾ + AB‾C‾ + ABC ABC + ABC + ABC + ABC

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

= A‾(B ⊕ C) + A[(B ⊕ C)‾]

= A‾X + AX‾ where X = B ⊕C

= A⊕ B ⊕C

= MSP expression.

This is the output of a 3-input XOR gate.

Carry = A‾BC + AB‾C + ABC‾ + ABC

= BC(A‾ + A) + AB‾C + ABC‾ BC(A + A) + ABC + ABC

= BC + AB‾C + ABC‾

= C(B + AB‾) + ABC‾

= C(B + A) + ABC‾

= BC + AC + ABC‾

= BC + A(C + BC‾)

= BC + A(C + B)

= BC + AC + AB = MSP expression

589_Truth table for full adder.jpg

A computer or digital circuit can add only two binary numbers at a time. If the digital circuit has to add more than two binary numbers, the circuit will add first two binary numbers and to sum of these two numbers it will add third binary number, and so on. But while adding two bits a carry is liable to appear.

Thus if two binary numbers to be added are having more than one bit, then after addition of first bits of numbers addition of second bits will also need addition of any carry that appears from addition of first bits. Therefore addition of first bits can be performed by half adder that has two inputs, but addition of second bits need a 3- input adder that is realized by full adder. There are eight entries to truth table of a full adder, half of which are satisfied by truth table of half adder ignoring carry bit (as addition of first bits of two numbers don't have a carry to be added).

Designing Circuits Using NAND Gates Only:

Quite often it is needed that only NAND gates must be utilized in designing digital circuits. NAND gate being universal can be utilized to realize AND, OR and NOT gates. Thus, wherever these gates are appearing, equivalent NAND circuit is utilized. The realization of AND, OR and NOT gates from NAND gates.

1450_Designing Circuits Using NAND Gates.jpg


Expand your confidence, grow study skills and improve your grades.



