Introduction to Logic Basics

 Hardware consists of a few simple building blocks

 These are called logic gates
 AND, OR, NOT, …

 NAND, NOR, XOR, …

 Logic gates are built using transistors

 NOT gate can be implemented by a single transistor
 AND gate requires 3 transistors
 Transistors are the fundamental devices
 Pentium consists of 3 million transistors
 Compaq Alpha consists of 9 million transistors
 Now we can build chips with more than 100 million
transistors
 Basic Concepts
 Simple gates
 AND
 OR
 NOT
 Functionality can be
expressed by a truth table
 A truth table lists output for
each possible input
combination
 Precedence
 NOT > AND > OR
 F=AB+AB
= (A (B)) + ((A) B)
 Basic Concepts (cont.)
 Additional useful gates
 NAND
 NOR
 XOR
 NAND = AND + NOT
 NOR = OR + NOT
 XOR implements
exclusive-OR function
 NAND and NOR gates
require only 2 transistors
 AND and OR need 3
transistors!
 Basic Concepts (cont.)
 Proving NAND gate is universal
 Basic Concepts (cont.)
 Proving NOR gate is universal
Logic Chips (cont.)
 Logic Chips (cont.)
 Integration levels
 SSI (small scale integration)
 Introduced in late 1960s

 1-10 gates (previous examples)

 MSI (medium scale integration)

 Introduced in late 1960s

 10-100 gates

 LSI (large scale integration)

 Introduced in early 1970s

 100-10,000 gates

 VLSI (very large scale integration)

 Introduced in late 1970s

 More than 10,000 gates

 Logic Functions
3-input majority function  Logical expression form
A B C F F=AB+BC+AC

0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
 Logical Equivalence
 All three circuits implement F = A B function
 Logical Equivalence (cont.)
 Proving logical equivalence of two circuits
 Derive the logical expression for the output of each
circuit
 Show that these two expressions are equivalent
 Two ways:

 You can use the truth table method

 For every combination of inputs, if both expressions

yield the same output, they are equivalent

 Good for logical expressions with small number of

variables
 You can also use algebraic manipulation
 Need Boolean identities
 Logical Equivalence (cont.)
 Derivation of logical expression from a circuit
 Trace from the input to output
 Write down intermediate logical expressions along the path
 Logical Equivalence (cont.)
 Proving logical equivalence: Truth table method

A B F1 = A B F3 = (A + B) (A + B) (A +
B)
0 0 0 0
0 1 0 0
1 0 0 0
1 1 1 1
 Deriving Logical Expressions
 Derivation of logical expressions from truth tables
 sum-of-products (SOP) form
 product-of-sums (POS) form
 SOP form
 Write an AND term for each input combination that
produces a 1 output
 Write the variable if its value is 1; complement

otherwise
 OR the AND terms to get the final expression
 POS form
 Dual of the SOP form
 Deriving Logical Expressions (cont.)
 3-input majority function  SOP logical expression
A B C F  Four product terms
 Because there are 4 rows
0 0 0 0 with a 1 output
0 0 1 0
0 1 0 0
0 1 1 1 F=ABC+ABC+
1 0 0 0 ABC+ABC
1 0 1 1
1 1 0 1
1 1 1 1
 Deriving Logical Expressions (cont.)
 3-input majority function  POS logical expression
A B C F  Four sum terms
 Because there are 4 rows
0 0 0 0 with a 0 output
0 0 1 0
0 1 0 0
0 1 1 1 F = (A + B + C) (A + B + C)
1 0 0 0 (A + B + C) (A + B + C)
1 0 1 1
1 1 0 1
1 1 1 1
 Logical Expression Simplification
 Two basic methods
 Algebraic manipulation
 Use Boolean laws to simplify the expression

 Difficult to use
 Don’t know if you have the simplified form
 Karnaugh map (K-map) method
 Graphical method

 Easy to use

 Can be used to simplify logical expressions with a few

variables
 Algebraic Manipulation
 Majority function example
Added extra
ABC+ABC+ABC+ABC =
ABC+ABC+ABC+ABC+ABC+ABC

 We can now simplify this expression as

BC+AC+AB

 A difficult method to use for complex expressions

Karnaugh Map Method

Note the order

Karnaugh Map Method (cont.)
Simplification examples
Karnaugh Map Method (cont.)
First and last columns/rows are adjacent
Karnaugh Map Method (cont.)
Minimal expression depends on groupings
Karnaugh Map Method (cont.)
No redundant groupings
 Implementation Using NAND Gates
 Using NAND gates
 Get an equivalent expression

AB+CD=AB+CD
 Using de Morgan’s law

AB+CD=AB.CD
 Can be generalized
 Majority function

A B + B C + AC = A B . BC . AC
Idea: NAND Gates: Sum-of-Products, NOR Gates: Product-of-Sums
 Implementation Using NAND Gates
(cont.)
 Majority function
  Sampai Ketemu Mgg Depan……

 Minggu Depan Harap Masuk Semua……

 Akan Ada Quiz-1

 (Tdk ada susulan, hanya ada Tugas Pengganti, yg

akan diumumkan Mgg depannya….)