Digital Logic Design I

Boolean Algebra and Logic

Gate

Mathematical Toolkit for Binary Logic

1
Postulates of a mathematical system
Forms the basic assumptions from which it is possible to deduce rule,
theorems and properties of the system
The most common postulates to form various algebraic structures are
❖ Closure
❖ Associative law
❖ Commutative law
❖ Identity element
❖ Distributive law

February 13, 2023

2
 Algebras
◼ What is an algebra?
❑ Mathematical system consisting of
❑ Set of elements
❑ Set of operators
❑ Axioms or postulates
◼ Why is it important?
❑ Defines rules of “calculations” or doing some operations
◼ Example: arithmetic on natural numbers
❑ Set of elements: N = {1,2,3,4,…}
❑ Operator: +, –, *
❑ Axioms: associativity, distributivity, closure, identity elements,
inverse etc.
◼ Note: operators with two inputs are called binary
❑ Does not mean they are restricted to binary numbers!
❑ Operator(s) with one input are called unary

February 13, 2023

3
 BASIC DEFINITIONS
◼ A set is collection of having the same property.
❑ S: set, x and y: element or event
❑ For example: S = {1, 2, 3, 4} or S = {a,b,c}, where c = a*b
❑ If x = 2, then xS.
❑ If y = 5, then y S.
◼ A binary operator defines on a set S of elements is a
rule that assigns, to each pair of elements from S, a
unique element from S.
❑ For example: given a set S, consider a*b = c and * is a binary
operator.
❑ If (a, b) through * get c and a, b, cS, then * is a binary
operator of S.
❑ On the other hand, if * is not a binary operator of S and a, bS,
then c  S.

4
 BASIC DEFINITIONS
◼ The most common postulates used to formulate various
algebraic structures are as follows:
1. Closure: a set S is closed with respect to a binary operator if, for
every pair of elements of S, the binary operator specifies a rule for
obtaining a unique element of S.
❑ For example, natural numbers N={1,2,3,...} is closed w.r.t. the binary
operator + by the rule of arithmetic addition, since, for any a, bN, there
is a unique cN such that
❑ a+b = c
❑ But operator – is not closed for N, because 2-3 = -1 and 2, 3 N, but (-1)N.
2. Associative law: a binary operator * on a set S is said to be
associative whenever
❑ (x * y) * z = x * (y * z) for all x, y, zS
❑ (x+y)+z = x+(y+z)
3. Commutative law: a binary operator * on a set S is said to be
commutative whenever
❑ x * y = y * x for all x, yS
❑ x+y = y+x
February 13, 2023
5
 BASIC DEFINITIONS
4. Identity element: a set S is said to have an identity element with
respect to a binary operation * on S if there exists an element eS
with the property that
❑ e * x = x * e = x for every xS
❑ 0+x = x+0 =x for every xI . I = {…, -3, -2, -1, 0, 1, 2, 3, …}.
❑ 1*x = x*1 =x for every xI. I = {…, -3, -2, -1, 0, 1, 2, 3, …}.
5. Inverse: a set having the identity element e with respect to the
binary operator to have an inverse whenever, for every xS, there
exists an element yS such that
❑ x*y=e
❑ The operator + over I, with e = 0, the inverse of an element a is (-a), since
a+(-a) = 0.
6. Distributive law: if * and ．are two binary operators on a set S, * is
said to be distributive over . whenever
❑ x * (y．z) = (x * y)．(x * z)

February 13, 2023

6
 George Boole
◼ Father of Boolean algebra
◼ He came up with a type of linguistic algebra, the three
most basic operations of which were (and still are) AND,
OR and NOT. It was these three functions that formed
the basis of his premise, and were the only operations
necessary to perform comparisons or basic mathematical
functions.
◼ Boole’s system (detailed in his 'An Investigation of the
Laws of Thought, on Which Are Founded the
Mathematical Theories of Logic and Probabilities', 1854)
was based on a binary approach, processing only two
objects - the yes-no, true-false, on-off, zero-one
approach.
George Boole (1815 - 1864)
◼ Surprisingly, given his standing in the academic
community, Boole's idea was either criticized or
completely ignored by the majority of his peers.
◼ Eventually, one bright student, Claude Shannon (1916-
2001), picked up the idea and ran with it

7
 Axiomatic Definition of Boolean Algebra
◼ We need to define algebra for binary values
❑ Developed by George Boole in 1854
◼ Huntington postulates for Boolean algebra (1904):
◼ B = {0, 1} and two binary operations, + and ．, x, y
and z are three binary variables of set B
❑ 1(a) Closure with respect to operator + or x+0 =
x, where x is element of B
❑ (b) Closure with respect to operator dot · x.1=x
❑ 2(a) 0 is Identity element for operator + : x+0 = 0
+x = x
❑ (b) 1 is Identity element for operator dot . : x . 1
= 1.x = x 8
 Axiomatic Definition of Boolean Algebra

❑3 (a) Commutative with respect to + : x+y = y+x,

(b) Commutative with respect to dot · : x.y = y.x
❑ 4(a) . is distributive over +: x·(y+z) = (x·y)+(x·z)
❑ (b) + is distributive over dot . : x+(y·z) = (x+y)·(x+z)
5. Complement for every element x is x’ with
x+x’=1, x·x’=0
❑ 6. There are at least two elements x,yB such that
xy

9
Difference between Boolean algebra and ordinary algebras (real
numbers) for arithmetic operation
Properties Boolean algebras Ordinary algebras
Set B is a set with only two A set of real numbers,
elements, B(0,1) have infinite elements
Variables/literals Defined by symbol like Defined by symbol like
x, y, z etc a, b, x, y, z etc
Associative law Hold for both operators Not hold
Distributive law of + over x+(y.z) = (x+y)(x +z) Not valid
.
Additive or multiplicative Not available , so no Available so subtraction
inverse subtraction or division or division possible
possible

Complement operation Valid Not valid

February 13, 2023

10
◼Our purpose is application of
Boolean Algebra to logic
circuits

February 13, 2023

11
 Boolean Algebra
◼ Terminology:
❑ Literal: A variable or its complement
❑ Product term: literals connected by •
❑ Sum term: literals connected by +

12
 Postulates of Two-Valued Boolean
Algebra
◼ B = {0, 1} and two binary operations, + and．
◼ The rules of operations: AND、OR and NOT.
AND
x y c=x．y OR NOT
0 0 0 x y c=x+y x x'
0 1 0 0 0 0 0 1
1 0 0 0 1 1 1 0
1 1 1 1 0 1
1 1 1
1. Closure (+ and‧) , operation on elements result another
element c belong to the Boolean set B.
2. The identity elements
(1) +: 0
(2) ．: 1
13
 Postulates of Two-Valued Boolean Algebra
3. The commutative laws x+y = y+x or x.y = y.x, The
distributive laws, x·(y+z) = (x·y)+(x·z) or x+(y.z) = x.y + x.z
x y z y+z x．(y+z) x．y x．z (x．y)+(x．z)

0 0 0 0 0 0 0 0

0 0 1 1 0 0 0 0

0 1 0 1 0 0 0 0

0 1 1 1 0 0 0 0

1 0 0 0 0 0 0 0

1 0 1 1 1 0 1 1

1 1 0 1 1 1 0 1

1 1 1 1 1 1 1 1
14
 Postulates of Two-Valued Boolean Algebra

5. Complement
❑ x+x'=1 → 0+0'=0+1=1; 1+1'=1+0=1
❑ x．x'=0 → 0．0'=0．1=0; 1．1'=1．0=0
6. Has two distinct elements 1 and 0, with 0 ≠ 1

◼ Note
❑ A set of two elements
❑ + : OR operation; ．: AND operation
❑ A complement operator: NOT operation
❑ Binary logic is a two-valued Boolean algebra

15
 Duality
◼ The principle of duality is an important concept.
This says that if an expression is valid in Boolean
algebra, the dual of that expression is also valid.

◼ To form the dual of an expression,

◼ replace all + operators with . operators,
◼ all . operators with + operators,
◼ all ones with zeros,
◼ all zeros with ones.

16
 Duality

◼ Form the dual of the expression given below

a + (b.c) = (a + b).(a + c)
◼ Following the replacement rules (replace + by .
and . by +)…
a.(b + c) = a.b + a.c is dual of first expression
◼ Take care not to alter the location of the
parentheses if they are present.

17
Basic Theorems

18
 Boolean Theorems
◼ Huntington’s postulates define some rules
Post. 1:
closure
Post. 2:
(a) x+0=x, (b) x·1=x
Post. 3:
(a) x+y=y+x, (b) x·y=y·x
Post. 4:
(a) x(y+z) = xy+xz,
(b) x+yz = (x+y)(x+z)
◼ Need more rules to modify Post. 5: (a) x+x’=1, (b) x·x’=0
algebraic expressions
❑ Theorems that are derived from postulates
◼ What is a theorem?
❑ A formula or statement that is derived from
postulates (or other proven theorems)
◼ Basic theorems of Boolean algebra
❑ Theorem 1 (a): x + x = x (b): x · x = x
❑ Looks straightforward, but needs to be proven !

February 13, 2023

19
 Proof of x+x=x
◼ We can only use Huntington postulates:
Huntington postulates:
Post. 2: (a) x+0=x, (b) x·1=x
Post. 3: (a) x+y=y+x, (b) x·y=y·x
Post. 4: (a) x(y+z) = xy+xz,
(b) x+yz = (x+y)(x+z)
Post. 5: (a) x+x’=1, (b) x·x’=0
◼ Show that x+x=x.
x+x = (x+x)·1 by 2(b)
= (x+x)(x+x’) by 5(a)
= x+xx’ by 4(b)
= x+0 by 5(b)
=x by 2(a)
hence proved.
◼ We can now use Theorem 1(a) in future proofs

February 13, 2023

20
 Proof of x·x=x
◼ Similar to previous Huntington postulates:
proof
Post. 2: (a) x+0=x, (b) x·1=x
Post. 3: (a) x+y=y+x, (b) x·y=y·x
Post. 4: (a) x(y+z) = xy+xz,
(b) x+yz = (x+y)(x+z)
Post. 5: (a) x+x’=1, (b) x·x’=0
Th. 1: (a) x+x=x

◼ Show that x·x = x.

x·x = xx+0 by 2(a)
= xx+xx’ by 5(b)
= x(x+x’) by 4(a)
= x·1 by 5(a)
=x by 2(b)

February 13, 2023

21
 Proof of x+1=1
◼ Theorem 2(a): x + 1 = 1 Huntington postulates:
x + 1 = 1．(x + 1) by 2(b) Post. 2: (a) x+0=x, (b) x·1=x
=(x + x')(x + 1) 5(a) Post. 3: (a) x+y=y+x, (b) x·y=y·x
= x + x' 1 4(b) Post. 4: (a) x(y+z) = xy+xz,
(b) x+yz = (x+y)(x+z)
= x + x' 2(b) Post. 5: (a) x+x’=1, (b) x·x’=0
=1 5(a) Th. 1: (a) x+x=x
◼ Theorem 2(b): x．0 = 0 by duality
◼ Theorem 3: (x')' = x
❑ Postulate 5 defines the complement of x, x + x' = 1 and x x' =
0
❑ The complement of x' is x is also (x')'

February 13, 2023

22
 Absorption Property (Covering)
Huntington postulates:
• Absorption identity is an identity
linking a pair of binary operations Post. 2: (a) x+0=x, (b) x·1=x
• Two binary operations, ¤ and ⁂, Post. 3: (a) x+y=y+x, (b) x·y=y·x
are said to be connected by Post. 4: (a) x(y+z) = xy+xz,
the absorption law (b) x+yz = (x+y)(x+z)
• if: a ¤ (a ⁂ b) = a ⁂ (a ¤ b) = a Post. 5: (a) x+x’=1, (b) x·x’=0
Th. 1: (a) x+x=x

◼ Theorem 6(a): x + x . y = x
❑ x + xy = x．1 + xy by 2(b) Proof by truth table
= x (1 + y) 4(a) x y xy x+xy x.(x+y)
= x (y + 1) 3(a)
= x．1 Th 2(a) 0 0 0 0 0
=x 2(b) 0 1 0 0 0
1 0 0 1 1
Theorem 6(b): x . (x + y) = x = x + xy
by duality 1 1 1 1 1
February 13, 2023
23
 DeMorgan’s Theorem
◼ Theorem 5(a): (x + y)’ = x’.y’
◼ Theorem 5(b): (x.y)’ = x’ + y’
◼ By means of truth table

x y x’ y’ x+y (x+y)’ x’y’ xy x’+y' (xy)’

0 0 1 1 0 1 1 0 1 1

0 1 1 0 1 0 0 0 1 1

1 0 0 1 1 0 0 0 1 1

1 1 0 0 1 0 0 1 0 0

February 13, 2023

24
 Consensus Theorem
1. X.y + x’.z + y.z = x.y + x’.z, here yz redundant term
2. (x+y)•(x’+z)•(y+z) = (x+y)•(x’+z) -- (dual)
◼ Proof:
xy + x’z + yz = xy + x’z + (x+x’)yz
= xy + x’z + xyz + x’yz
= (xy + xyz) + (x’z + x’zy)
= xy (z+1) + x’z (y+1) = xy + x’z
◼ (2 true by duality). It helps to eliminate redundant term

February 13, 2023

25
 Operator Precedence
◼ The operator precedence for evaluating
Boolean Expression is
❑ Parentheses
❑ NOT
❑ AND
❑ OR
◼ Examples
❑ x y' + z
❑ (x y + z)'

February 13, 2023

26
 Boolean Functions
◼ A Boolean function
❑Binary variables
❑ Binary operators OR and AND
❑ Unary operator NOT
❑ Parentheses
◼ Examples
❑ F1= x .y .z'
❑ F2 = x + y'z
❑ F3 = x' y' z + x' y z + x y'
❑ F4 = x y' + x' z
❑ F5 = xy’ + x’y = sum bit of half adder

February 13, 2023

27
 Boolean Functions
 The truth table of 2n entries
 F1 = xyz’, x + y'z, F3 = x' y' z + x' y z + x y‘ , F4 = x y' + x' z
x y z F1 F2 F3 F4
0 0 0 0 0 0 0
0 0 1 0 1 1 1
0 1 0 0 0 0 0
0 1 1 0 0 1 1
1 0 0 0 1 1 1
1 0 1 0 1 1 1
1 1 0 1 1 0 0
1 1 1 0 1 0 0
◼ Two Boolean expressions may be same
❑ F3 = F4
February 13, 2023
28
 Boolean Functions
◼ Implementation with logic gates
❑ F4 is more economical

F2 = x + y'z

F3 = x' y' z + x' y z + x y'

F4 = x y' + x' z

February 13, 2023

29
 Algebraic Manipulation
◼ To minimize Boolean expressions
❑ Literal: a primed or unprimed variable (an input to a gate)
❑ Term: an implementation with a gate
❑ The minimization of the number of literals and the number of
terms → a circuit with less components/equipment
It is a hard problem (no specific rules to follow)
❑
◼ Example 2.1
1. x(x'+y) = xx' + xy = 0+xy = xy
2. x+x'y = (x+x')(x+y) = 1. (x+y) = x+y
3. (x+y)(x+y') = x.x+xy+xy'+yy' = x(1+y+y') = x
4. xy + x'z + yz.1 = xy + x'z + yz(x+x') = xy + x'z + yzx + yzx' =
xy(1+z) + x'z(1+y) = xy +x'z
5. (x+y)(x'+z)(y+z) = (x+y)(x'+z), by duality from function 4.
(consensus theorem with duality)

February 13, 2023

30
 Complement of a Function
◼ An interchange of 0's for 1's and 1's for 0's in the value
of F = (A + B +C)
❑ By DeMorgan's theorem
❑ F’ = (A+B+C)' = (A+X)' let B+C = X
= A‘.X' by theorem 5(a) (DeMorgan's)
= A'(B+C)' substitute B+C = X
= A‘.(B'C') by theorem 5(a) (DeMorgan's)
= A'B'C' by theorem 4(b) (associative)
◼ Generalizations: a function is obtained by interchanging
AND and OR operators and complementing each literal.
❑ (A+B+C+D+ ... +F)' = A'B'C'D'... F'
❑ (ABCD ... F)' = A'+ B'+C'+D' ... +F'

February 13, 2023

31
 Examples
◼ Example 2.2

◼ F1 = x’.y.z’ + x’y’z, it is sum of product form (SOP)

❑ F1' = (x'yz' + x'y'z)' = (x'yz')' .(x'y'z)' = (x+y'+z) .
(x+y+z') (product of sum (POS)
❑ F2' = [x(y'z'+yz)]' = x' + (y'z'+yz)' = x' + (y'z')' (yz)‘
= x' + (y+z) (y'+z')
= x' + yz‘+y'z

February 13, 2023

32
 Examples
◼ Example 2.3: a simpler procedure

❑ Take the dual of the function

❑ Complement each literal
1. F1 = x'yz' + x'y'z.
The dual of F1 is (x'+y+z'). (x'+y'+z).
Complement each literal: (x+y'+z)(x+y+z') = F1‘

2. F2 = x.(y' z' + yz).

The dual of F2 is x+(y'+z') (y+z).
Complement each literal: x'+(y+z)(y' +z') = F2'

February 13, 2023

33
 2.6 Canonical and Standard Forms
Minterms and Maxterms
◼ A minterm (standard product): an AND term consists of
all literals in their normal form or in their complement
form.
❑ For example, two binary variables x and y,
❑ X.y, x.y', x'y, x'y'
❑ It is also called a standard product.
❑ n variables can be combined to form 2n minterms.

◼ A maxterm (standard sums): an OR term It is also

called a standard sum.
❑ 2n maxterms for n variables
❑ Foe example (x + y), (y+x’) maxterm of two variables

February 13, 2023

34
 Minterms and Maxterms
 Each maxterm is the complement of its corresponding
minterm, and vice versa.
 Mj = mj’ or mj = Mj’ say j = 1, M1 = m1’ =(x’y’z)’ = (x+y+z’)

February 13, 2023

35
Minterms and Maxterms
◼ An Boolean function can be expressed by
❑ A truth table
❑ Sum of minterms (SOP)
❑ Product of Maxterms (POS)
❑ For SOP fom consider those minterms which give 1 value in the
function

February 13, 2023

36
Minterms and Maxterms
◼

February 13, 2023

37
 F1 = (x + y+z)(x+y’+z)(x + y’+z’) (x’ + y’ +z)

February 13, 2023

38
 Minterms and Maxterms

➢ Any Boolean function can be expressed as

➢A sum of minterms (“sum” meaning the
ORing of terms).
➢ A product of maxterms (“product” meaning
the ANDing of terms).
➢ Both Boolean functions are said to be in
Canonical form.
➢ Both forms have maximum number of literals

February 13, 2023

39
Sum of Minterms
◼ Sum of minterms: there are 2n minterms and 22n
combinations of function with n Boolean variables.
◼ A+A’ = 1, BC’ = BC’.1 = BC’(A+A’) = BC’A + BC’A’
◼ A.1 = A(B+B’) = AB + AB’ = AB.1+AB’.1 = AB(C+C’) +
AB’(C+C’) = ABC + ABC’ + AB’C + AB’C’
◼ Example 2.4: express F = A+BC' as a sum of minterms.
❑ F = A+B'C = A (B+B') + B'C = AB +AB' + B'C = AB(C+C') +
AB'(C+C') + (A+A')B'C = ABC+ABC'+AB'C+AB'C'+A'B'C
❑ F = A'B'C +AB'C' +AB'C+ABC'+ ABC = m1 + m4 +m5 + m6 + m7
❑ F(A, B, C) = S(1, 4, 5, 6, 7) in canonical form
❑ or, built the truth table first

February 13, 2023

40
 Product of Maxterms
◼ Product of maxterms: using distributive law to expand.
◼ Do maxterm representation
❑ x + yz = (x + y)(x + z) = (x+y+zz')(x+z+yy') =
❑ (x+y+z)(x+y+z')(x+y'+z)(x+z+y)=
❑ (x+y+z)(x+y+z’)(x+y’+z) =M0.M1.M2 = π(0,1,2)

◼ Example 2.5: express F = xy + x'z as a product of maxterms.

❑ F = xy + x'z = (xy + x')(xy +z) = (x+x')(y+x')(x+z)(y+z) =

(x'+y)(x+z)(y+z)
❑ x'+y = x' + y + zz' = (x'+y+z)(x'+y+z')
❑ F = (x+y+z)(x+y'+z)(x'+y+z)(x'+y+z') = M0M2M4M5
❑ F(x, y, z) = P(0, 2, 4, 5)

February 13, 2023

41
 Conversion between Canonical Forms
◼ The complement of a function expressed as the sum of minterms equals the sum
of minterms missing from the original function.
❑ F(A, B, C) = Σ(1, 4, 5, 6, 7) =
❑ Thus, F'(A, B, C) = Σ(0, 2, 3) = m0 + m2 + m3
❑ By DeMorgan's theorem
❑ F’’(A,B,C) = (m0 + m2 + m3)’ =(m0’)(m2’)(m3)’
❑ = (A’.B’.C’)’(A’.B.C’)’(A’.B.C.)’ = (A+B+C)(A + B’ +C)(A+B’ + C’)
❑ = M0.M2.M3 =
F(A, B, C) = P(0, 2, 3)
F'(A, B, C) =P (1, 4, 5, 6, 7)
❑ mj' = Mj
❑ Sum of minterms = product of maxterms
❑ Interchange the symbols S and P and list those numbers missing from the
original form
❑ S of 1's

❑ P of 0's
February 13, 2023
42
◼ Example
❑ F = xy + xz
❑ F(x, y, z) = S(1, 3, 6, 7)
❑ F(x, y, z) = P (0, 2, 4, 6)

February 13, 2023

43
Standard Forms

◼ Canonical forms are very seldom the ones with

the least number of literals.

◼ Standard forms: the terms that form the

function may obtain one, two, or any number of literals.
❑ Sum of products: F1 = y' + xy+ x'yz'
❑ Product of sums: F2 = x(y'+z)(x'+y+z')
❑ F3 = A'B'CD+ABC'D'

February 13, 2023

44
Conversion of standard form to Minterms/maxterm form

◼ Example 2.4: express F = A+BC' as a sum of minterms.

❑ F = A+B'C = A (B+B') + B'C = AB +AB' + B'C = AB(C+C') +
AB'(C+C') + (A+A')B'C = ABC+ABC'+AB'C+AB'C'+A'B'C
❑ F = A'B'C +AB'C' +AB'C+ABC'+ ABC = m1 + m4 +m5 + m6 + m7
❑ F(A, B, C) = S(1, 4, 5, 6, 7)

❑ Example: Express the following in SOP and POS form

❑ F(A,B,C,D) = B’D + A’D + BD

❑ F = ABC + A’B’C
❑ Two level of implementation

February 13, 2023

45
 Implementation of standard form
◼ Two-level implementation

F1 = y' + xy+ x'yz' F2 = x(y'+z)(x'+y+z')

◼ Multi-level implementation

February 13, 2023

46
 2.7 Other Logic Operations (
◼ 2n rows in the truth table of n binary variables. (n=2)
n
◼ 22
functions for n binary variables.
◼ 16 functions of two binary variables.

◼ All the new symbols except for the exclusive-OR

symbol are not in common use by digital designers.
February 13, 2023
47
Boolean Expressions

February 13, 2023

48
Digital Logic Gates

◼ Boolean expression: AND, OR and NOT operations

◼ Constructing gates of other logic operations

❑ The feasibility and economy;
❑ The possibility of extending gate's inputs;
❑ The basic properties of the binary operations (commutative and
associative);
❑ The ability of the gate to implement Boolean functions.

February 13, 2023

49
 Standard Gates
◼ Consider the 16 functions in Table 2.8 (slide 47)
❑ Two are equal to a constant (F0 and F15).
❑ Four are repeated twice (F4, F5, F10 and F11).
❑ Inhibition (F2) and implication (F13) are not commutative or
associative.
❑ The other eight: complement (F12), transfer (F3), AND (F1), OR
(F7), NAND (F14), NOR (F8), XOR (F6), and equivalence (XNOR)
(F9) are used as standard gates.
❑ Complement: inverter.
❑ Transfer: buffer (increasing drive strength).
❑ Equivalence: XNOR.

February 13, 2023

50
Summary of Logic Gates

February 13, 2023 Figure 2.5 Digital logic gates

51
 Summary of Logic Gates

February 13, 2023

Figure 2.5 Digital logic gates
52
 Multiple Inputs Gates
◼ Extension of two inputs gate to multiple inputs gate
❑ A two inputs gate can be extended to multiple inputs.
❑ If its binary operation is commutative and associative.

❑ AND and OR are commutative and associative.

❑ So multi-inputs AND or OR gates can be formed from
two inputs AND or OR gates
❑ OR gate

▪ x+y = y+x
▪ (x+y)+z = x+(y+z) = x+y+z
❑ AND gate

▪ xy = yx
▪ (x y)z = x(y z) = x y z
February 13, 2023
53
Multiple Inputs
❑ NAND and NOR are commutative but not associative → they
are not extendable to multiinputs.

Figure 2.6 Demonstrating the nonassociativity of the NOR operator;

(x ↓ y) ↓ z ≠ x ↓(y ↓ z)
February 13, 2023
54
Multiple Inputs
❑ Multiple NOR = a complement of OR gate, Multiple NAND = a
complement of AND.
❑ The cascaded NAND operations = sum of products.
❑ The cascaded NOR operations = product of sums.

Figure 2.7 Multiple-input and cascated NOR and NAND gates

February 13, 2023
55
Multiple Inputs XOR/XNOR
❑ The XOR and XNOR gates are commutative and associative.
❑ Multiple-input XOR gates are uncommon?
❑ XOR is an odd function: it is equal to 1 if the inputs variables
have an odd number of 1's.

February 13, 2023 Figure 3-input XOR gate

56
Multiple Inputs XOR/XNOR
❑ The XOR and XNOR gates are commutative and associative.
❑ Multiple-input XOR gates are uncommon for hardware point
❑ These gates are constructed from other gates/basic gates?
❑ XOR is an odd function: its output is equal to 1 if the inputs variables
have an odd number of 1's.

February 13, 2023 Figure 3-input XOR gate

57
ODD Function and their implementation

❑ XOR is an odd function: its output is equal to 1 if the inputs variables

have an odd number of 1's.

February 13, 2023 Figure 3-input XOR gate

58
ODD Function and their implementation

❑ XOR is an odd function:

❑ A Odd function can be implemented by XOR gate

February 13, 2023 Figure 3-input/four input XOR gate

59
Positive and Negative Logic
◼ Positive and Negative Logic
❑ Two signal values <=> two logic
values
❑ Positive logic: H=1; L=0
❑ Negative logic: H=0; L=1
◼ Consider a TTL gate
❑ A positive logic AND gate
❑ A negative logic OR gate
❑ The positive logic is used in this
book (Morris Mano)

Figure 2.9 Signal assignment and logic polarity

February 13, 2023
60
Positive and Negative Logic

February 13, 2023 Figure 2.10 Demonstration of positive and negative logic 61
 2.9 Integrated Circuits
Level of Integration
◼ An IC (a chip)
◼ Examples:
❑ Small-scale Integration (SSI): < 10 gates
❑ Medium-scale Integration (MSI): 10 ~ 100 gates
❑ Large-scale Integration (LSI): 100 ~ xk gates
❑ Very Large-scale Integration (VLSI): > xk gates
◼ VLSI
❑ Small size (compact size)
❑ Low cost
❑ Low power consumption
❑ High reliability
❑ High speed

February 13, 2023

62
 Digital Logic Families
◼ Digital logic families: circuit technology
❑ TTL: transistor-transistor logic (dying?)
❑ ECL: emitter-coupled logic (high speed, high power
consumption)
❑ MOS: metal-oxide semiconductor (NMOS, high density)
❑ CMOS: complementary MOS (low power)
❑ BiCMOS: high speed, high density

February 13, 2023

63
 Digital Logic Families
◼ The characteristics of digital logic families
❑ Fan-out: the number of standard loads that the output of a
typical gate can drive.
❑ Power dissipation.
❑ Propagation delay: the average transition delay time for the
signal to propagate from input to output.
❑ Noise margin: the minimum of external noise voltage that
caused an undesirable change in the circuit output.

February 13, 2023

64
CAD
◼ CAD – Computer-Aided Design
❑ Millions of transistors
❑ Computer-based representation and aid
❑ Automatic the design process
❑ Design entry
❑ Schematic capture
❑ HDL – Hardware Description Language
▪ Verilog, VHDL
❑ Simulation
❑ Physical realization
❑ ASIC, FPGA, PLD

February 13, 2023

65
 Chip Design
◼ Why is it better to have more gates on a single chip?
❑ Easier to build systems
❑ Lower power consumption
❑ Higher clock frequencies

◼ What are the drawbacks of large circuits?

❑ Complex to design
❑ Chips have design constraints
❑ Hard to test

◼ Need tools to help develop integrated circuits

❑ Computer Aided Design (CAD) tools
❑ Automate tedious steps of design process
❑ Hardware description language (HDL) describe circuits
February 13, 2023
66
❑ VHDL (see the lab) is one such system
 Thanks to

February 13, 2023 67

February 13, 2023
68