EE2000 Logic Circuit Design Boolean Algebra and Switching Function

2.0 Logic Gates

The term gate is used to describe a circuit that performs a basic logic operation.

2.0.1Inverter

Figure 2.1 Distinctive shape symbols with negation indicators.

Inverter Truth Table

InputOutput

------

Low (0)High (1)

High (1)Low (0)

Inverter Operation

2.0.2AND Gate

Inputs / Output
A / B / X=AB
0 / 0 / 0
0 / 1 / 0
1 / 0 / 0
1 / 1 / 1
Truth table for a 2-input AND gate.

2.0.3OR Gate

Inputs / Output
A / B / X
0 / 0 / 0
0 / 1 / 1
1 / 0 / 1
1 / 1 / 1
Truth table for a 2-input OR gate.

2.0.4NAND Gate

An NAND gates is a popular logic element because it can be used as a universal gate; that is, NAND Gates can be used to perform the AND, OR, and inverter operations, or any combination of these logic.

Inputs / Output
A / B / X
0 / 0 / 1
0 / 1 / 1
1 / 0 / 1
1 / 1 / 0
Truth table for a 2-input NAND gate.

2.0.5NOR Gate

The NOR Gate, like the NAND Gate, is a very useful logic element because it can also be used as a universal gate.

Inputs / Output
A / B / X
0 / 0 / 1
0 / 1 / 0
1 / 0 / 0
1 / 1 / 0

2.0.6The Exclusive-OR and Exclusive-NOR Gates

Exclusive-OR Gate /
Inputs / Output
A / B / X
0 / 0 / 0
0 / 1 / 1
1 / 0 / 1
1 / 1 / 0
Exclusive-NOR Gate /
Inputs / Output
A / B / X
0 / 0 / 1
0 / 1 / 0
1 / 0 / 0
1 / 1 / 1

2.1Boolean Algebra and Switching Function

2.1.1Boolean algebra

Def.:A set of elements S with at least two different elements and two binary operations (+) and ( ) satisfying the basic postulates.

P1.If x,y S, then(i)x + y = y + x

(ii)

note:this is also known as the Commutative law.

P2.If x,y,z S, then(i)x + (y + z) = (x + y) + z

(ii)

note:this is also known as the Associativelaw.

P3.If x,y,z S, then(i)

(ii)

note:this is also known as the Distributive law.

P4.The set S has 2 distinct identity elements, denoted as 0 and 1, so

that for elements in S, we have

(i)0 + x = x

(ii)

P5.For element in S there exists an element which is a complement to

it, so that

(i)

(ii)

P6.There exists at least two elements x,y S such that x y.

For Boolean algebrain which S = {0, 1}, the formulation is referred as switching function.

2.2Operator precedence ordering

( ) +

parentheseNOTANDOR

2.3Duality

If an expression is valid in Boolean algebra, the dual of the expressionis also valid.

Principle of duality - illustrated by the following identities

(1a)(1b)1 + x = 1

(2a)(2b)0 + x = x

(3a)(3b)x + x = x

(4a)(4b)

The expressions are interchangable by replacing " " by " + " and

" 0 " by " 1 ".

2.4Theorems

T1.Idempotent law

(1) x + x = x

(2)

T2Involution law

= x

T3Absorption law

(1)x + xy = x

(2)x(x + y) = x

T5Logical adjacency

T6DeMorgan's law

(1)

(2)

The first theorem stated that

The complement of a product is equal to the sum of the complement

The second theorem stated that

The complement of a sum is equal to the product of the complement

These theorems are illustrated by the following gate equivalencies and truth tables.

Boolean Expression and Truth Table of a Logic Circuit

To derive the Boolean expression of a given logic circuit, begin at the left-most inputs and work towards the final output, writing the expression for each gate. Consider the following circuit,

Decimal / Hexadecimal / Inputs / Output
A / B / C / D / A(B+CD)
0 / 0 / 0 / 0 / 0 / 0 / 0
1 / 1 / 0 / 0 / 0 / 1 / 0
2 / 2 / 0 / 0 / 1 / 0 / 0
3 / 3 / 0 / 0 / 1 / 1 / 0
4 / 4 / 0 / 1 / 0 / 0 / 0
5 / 5 / 0 / 1 / 0 / 1 / 0
6 / 6 / 0 / 1 / 1 / 0 / 0
7 / 7 / 0 / 1 / 1 / 1 / 0
8 / 8 / 1 / 0 / 0 / 0 / 0
9 / 9 / 1 / 0 / 0 / 1 / 0
10 / A / 1 / 0 / 1 / 0 / 0
11 / B / 1 / 0 / 1 / 1 / 1
12 / C / 1 / 1 / 0 / 0 / 1
13 / D / 1 / 1 / 0 / 1 / 1
14 / E / 1 / 1 / 1 / 0 / 1
15 / F / 1 / 1 / 1 / 1 / 1

Simplification using Boolean Algebra

The purpose of simplifying Boolean expressions is to use the fewest gates possible to implement a given expression.

e.g. simplify AB + A(B + C) + B(B + C)

AB + AB + AC + BB + BC

AB + AB + AC + B + BC (BB = B):

AB + AC + B + BC(AB + AB = AB)

AB + AC + B(B + BC = B)

B + AC(AB + B = B)


e.g. simplify

=

=

=

=

=

=

e.g. simplify

=

=

=

=

2.5Algebraic Forms of Switching Function

Switching functions (Boolean Algebra with S ={0,1}) are generally expressed with least number of literals (variables).

Sum of products (SOP)

Product of sums(POS)

Canonical Forms

For a switching function consists of n variables, the minterm and maxterm must include these n variables exactly one time.

minterm (product term):complemented = 0

uncomplemented = 1

e.g.

maxterm (sum term):complemented = 1

uncomplemented = 0

e.g.

Description for minterms and maxterms for 3 variables logic function

Minterms / Maxterms
x / y / z / Term / designation / term / designation
0 / 0 / 0 / / m0 / / M0
0 / 0 / 1 / / m1 / / M1
0 / 1 / 0 / / m2 / / M2
0 / 1 / 1 / / m3 / / M3
1 / 0 / 0 / / m4 / / M4
1 / 0 / 1 / / m5 / / M5
1 / 1 / 0 / / m6 / / M6
1 / 1 / 1 / / m7 / / M7

Sum of minterms representation:

Product of maxterms representation:

Conversion between canonical forms

By using the DeMorgan's theorem, it can be shown that to convert from one canonical form to another, interchange the symbols  and  and list those numbers missing from the original form.

e.g.

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 / 0
1 / 1 / 1 / 1

For minterm representation:

For maxterm representation:

2.6Synthesis of Logic Function

e.g.

Circuit:

1st level 2nd level

e.g.

Circuit:

1st level 2nd level

n levels – at least one input signal must pass through n gates before reaching

the output.

2.7Structure using one gate type

Using the above examples: ,

the function can be implemented using NAND gates.

,

the function can be implemented using NOR gates.

1