------------
PAGE 1
------------
March 22, 2017
1
Digital Logic Design I Boolean Algebra and Logic Gate
Fernaz Narin Nur
------------
PAGE 2
------------
March 22, 2017
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”
ƒÞ Example: arithmetic on natural numbers
ƒá Set of elements: N = { 1,2,3,4,…}
ƒá Operator: , – , *
ƒá Axioms: associativity, distributivity, closure, identity elements, 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
------------
PAGE 3
------------
March 22, 2017
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}
ƒá 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 .
------------
PAGE 4
------------
March 22, 2017
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
------------
PAGE 5
------------
March 22, 2017
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 D are two binary operators on a set S, * is said to be distributive over . whenever
ƒá x * ( y D z ) = ( x * y ) D ( x * z )
------------
PAGE 6
------------
March 22, 2017
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.
ƒÞ 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
George Boole ( 1815 - 1864)
------------
PAGE 7
------------
March 22, 2017
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 D
ƒá Closure with respect to operator and operator ·
ƒá Identity element 0 for operator and 1 for operator ·
ƒá Commutativity with respect to and ·
x y = y x, x · y = y · x
ƒá Distributivity of · over , and over ·
x · ( y z) = ( x · y) ( x · z) and x ( y · z) = ( x y) · ( x z)
„X Complement for every element x is x’ with x x’= 1 , x · x’= 0
ƒá There are at least two elements x, y „¡ B such that x „j y
------------
PAGE 8
------------
March 22, 2017
8
Boolean Algebra
ƒÞ Terminology:
ƒá Literal: A variable or its complement
ƒá Product term: literals connected by •
ƒá Sum term: literals connected by
------------
PAGE 9
------------
March 22, 2017
9
Postulates of Two- Valued Boolean Algebra
ƒÞ B = { 0, 1} and two binary operations, and D
ƒÞ The rules of operations: AND A OR and NOT.
1. Closure ( and ¡E )
2. The identity elements
( 1) : 0
( 2) D : 1
x
y
x D y
0
0
0
0
1
0
1
0
0
1
1
1
x
y
x y
0
0
0
0
1
1
1
0
1
1
1
1
x
x '
0
1
1
0
AND
OR
NOT
------------
PAGE 10
------------
March 22, 2017
10
Postulates of Two- Valued Boolean Algebra
3. The commutative laws
4. The distributive laws
x
y
z
y z
x D ( y z)
x D y
x D z
( x D y) ( x D 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
------------
PAGE 11
------------
March 22, 2017
11
Postulates of Two- Valued Boolean Algebra
5. Complement
ƒá x x'= 1 ¨ 0 0'= 0 1= 1; 1 1'= 1 0= 1
ƒá x D x'= 0 ¨ 0 D 0'= 0 D 1= 0; 1 D 1'= 1 D 0= 0
6. Has two distinct elements 1 and 0, with 0 ‚ 1
ƒÞ Note
ƒá A set of two elements
ƒá : OR operation; D : AND operation
ƒá A complement operator: NOT operation
ƒá Binary logic is a two- valued Boolean algebra
------------
PAGE 12
------------
March 22, 2017
12
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, and all zeros with ones.
ƒÞ Form the dual of the expression
a ( bc) = ( a b)( a c)
ƒÞ Following the replacement rules…
a( b c) = ab ac
ƒÞ Take care not to alter the location of the parentheses if they are present.
------------
PAGE 13
------------
March 22, 2017
13
Basic Theorems
------------
PAGE 14
------------
March 22, 2017
14
Boolean Theorems
ƒÞ Huntington’s postulates define some rules
ƒÞ Need more rules to modify
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 !
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)
Post. 5: ( a) x x’= 1 , ( b) x · x’= 0
------------
PAGE 15
------------
March 22, 2017
15
Proof of x x= x
ƒÞ We can only use Huntington postulates:
ƒÞ 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)
Q. E. D.
ƒÞ We can now use Theorem 1( a) in future proofs
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
------------
PAGE 16
------------
March 22, 2017
16
Proof of x · x= x
ƒÞ Similar to previous proof
ƒÞ 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)
Q. E. D.
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
Th. 1 : ( a) x x= x
------------
PAGE 17
------------
March 22, 2017 17
Proof of x 1 = 1
ƒÞ Theorem 2( a): x 1 = 1
x 1 = 1 D ( x 1) by 2( b)
=( x x' )( x 1) 5( a)
= x x' 1 4( b)
= x x' 2( b)
= 1 5( a)
ƒÞ Theorem 2( b): x D 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' ) ' 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 Th. 1 : ( a) x x= x
------------
PAGE 18
------------
March 22, 2017
18
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
------------
PAGE 19
------------
March 22, 2017
19
Operator Precedence
ƒÞ The operator precedence for evaluating Boolean Expression is
ƒá Parentheses
ƒá NOT
ƒá AND
ƒá OR
ƒÞ Examples
ƒá x y' z
ƒá ( x y z ) '
------------
PAGE 20
------------
March 22, 2017
20
Boolean Functions
ƒÞ A Boolean function
ƒá Binary variables
ƒá Binary operators OR and AND
ƒá Unary operator NOT
ƒá Parentheses
ƒÞ Examples
ƒá F 1 = x y z'
ƒá F 2 = x y'z
ƒá F 3 = x' y' z x' y z x y'
ƒá F 4 = x y' x' z
------------
PAGE 21
------------
March 22, 2017
21
Boolean Functions
„Z The truth table of 2 n entries
ƒÞ Two Boolean expressions may specify the same function
ƒá F 3 = F 4
x
y
z
F 1
F 2
F 3
F 4
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
------------
PAGE 22
------------
March 22, 2017
22
Boolean Functions
ƒÞ Implementation with logic gates
ƒá F 4 is more economical F 4 = x y' x' z
F 3 = x' y' z x' y z x y'
F 2 = x y'z
------------
PAGE 23
------------
March 22, 2017
23
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 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 xy xy' yy' = x ( 1 y y' ) = x
4. xy x'z yz = 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)
------------
PAGE 24
------------
March 22, 2017 24
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,
ƒá xy, xy', x'y, x'y'
ƒá It is also called a standard product.
ƒá n variables con be combined to form 2 n minterms.
ƒÞ A maxterm ( standard sums): an OR term
ƒá It is also call a standard sum.
ƒá 2 n maxterms.
------------
PAGE 25
------------
March 22, 2017
25
Minterms and Maxterms
„Z Each maxterm is the complement of its corresponding minterm , and vice versa.
------------
PAGE 26
------------
March 22, 2017 26
Minterms and Maxterms
ƒÞ An Boolean function can be expressed by
ƒá A truth table
ƒá Sum of minterms
ƒá f 1 = x'y'z xy'z' xyz = m 1 m 4 m 7 ( Minterms)
ƒá f 2 = x'yz xy'z xyz' xyz = m 3 m 5 m 6 m 7 ( Minterms)
------------
PAGE 27
------------
March 22, 2017
27
Minterms and Maxterms
ƒÞ The complement of a Boolean function
ƒá The minterms that produce a 0
ƒá f 1 ' = m 0 m 2 m 3 m 5 m 6 = x'y'z' x'yz' x'yz xy'z xyz'
ƒá f 1 = ( f 1 ' ) ' = ( x y z )( x y' z ) ( x y' z' ) ( x' y z' )( x' y' z ) = M 0 M 2 M 3 M 5 M 6
ƒá f 2 = ( x y z )( x y z' )( x y' z )( x' y z ) = M 0 M 1 M 2 M 4
ƒÞ 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.
------------
PAGE 28
------------
March 22, 2017 28
Sum of Minterms
ƒÞ Sum of minterms: there are 2 n minterms and 2 2n combinations of function with n Boolean variables.
ƒÞ 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 = m 1 m 4 m 5 m 6 m 7
ƒá F( A , B , C ) = S ( 1, 4, 5, 6, 7)
ƒá or, built the truth table first
------------
PAGE 29
------------
March 22, 2017
29
Product of Maxterms
ƒÞ Product of maxterms: using distributive law to expand.
ƒá x yz = ( x y )( x z) = ( x y zz' )( x z yy' ) = ( x y z )( x y z' )( x y' z )
ƒÞ 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' ) = M 0 M 2 M 4 M 5
ƒá F ( x, y, z ) = P ( 0, 2, 4, 5)
------------
PAGE 30
------------
March 22, 2017 30
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 ) = S ( 1, 4, 5, 6, 7)
ƒá Thus, F' ( A , B , C ) = S ( 0, 2, 3)
ƒá By DeMorgan's theorem
F ( A , B , C ) = P ( 0, 2, 3)
F' ( A , B , C ) = P ( 1, 4, 5, 6, 7)
ƒá m j ' = M j
ƒá 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
------------
PAGE 31
------------
March 22, 2017
31
ƒÞ Example
ƒá F = xy x „S z
ƒá F ( x , y , z ) = S ( 1, 3, 6, 7)
ƒá F ( x , y , z ) = P ( 0, 2, 4, 6)
------------
PAGE 32
------------
March 22, 2017 32
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: F 1 = y' xy x'yz'
ƒá Product of sums: F 2 = x ( y' z )( x' y z' )
ƒá F 3 = A'B'CD ABC'D'
------------
PAGE 33
------------
March 22, 2017
33
Implementation
ƒÞ Two- level implementation
ƒÞ Multi- level implementation F 1 = y' xy x'yz' F 2 = x ( y' z )( x' y z' )
------------
PAGE 34
------------
March 22, 2017
34 Figure 2.5 Digital logic gates
Summary of Logic Gates
------------
PAGE 35
------------
March 22, 2017
35 Figure 2.5 Digital logic gates Summary of Logic Gates
------------
PAGE 36
------------
March 22, 2017
36 Multiple Inputs
ƒÞ Extension to multiple inputs
ƒá A gate can be extended to multiple inputs.
ƒá If its binary operation is commutative and associative.
ƒá AND and OR are commutative and associative.
ƒá OR
„X x y = y x
„X ( x y ) z = x ( y z ) = x y z
ƒá AND
„X xy = yx
„X ( x y ) z = x ( y z ) = x y z
------------
PAGE 37
------------
March 22, 2017
37 Multiple Inputs
ƒá NAND and NOR are commutative but not associative ¨ they are not extendable.
Figure 2.6 Demonstrating the nonassociativity of the NOR operator; ( x « y ) « z ‚ x «( y « z )
------------
PAGE 38
------------
March 22, 2017 38 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
------------
PAGE 39
------------
March 22, 2017 39
Multiple Inputs
ƒá 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. Figure 2.8 3- input XOR gate
------------
PAGE 40
------------
March 22, 2017 40 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 Figure 2.9 Signal assignment and logic polarity
------------
PAGE 41
------------
March 22, 2017
41 Figure 2.10 Demonstration of positive and negative logic Positive and Negative Logic
------------
PAGE 42
------------
March 22, 2017 42 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
------------
PAGE 43
------------
March 22, 2017
43 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
------------
PAGE 44
------------
March 22, 2017 44 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.
Back to top of page