ECEN 248: INTRODUCTION TO

DIGITAL SYSTEMS DESIGN

Week 2
Dr. Srinivas Shakkottai
Dept. of Electrical and Computer Engineering
Boolean Algebra
Boolean Algebra

 A Boolean algebra is defined with:

 A set of elements S
 A set of operators

 A number of unproved axioms or postulates

 A set is a collection of objects

 S={0,1}
 S={1,2,3,4}

 We will focus on a two-valued Boolean algebra.

Boolean Algebra (cont.)

 A binary operator:
 Defined on a set S of elements
 A rule that assigns to each pair of elements from S a
unique element from S
 Example a·b=c

 aS and bS it must hold that a·bS

 A set S is closed with respect to a binary operator

if for every two elements of S, the binary
operator specifies a unique element of S
Definition of Boolean Algebra

 Boolean algebra is an algebraic structure,

defined by a set of elements S and two binary
operators, +, and ·, with the following postulates:
1. The structure is closed with respect to + and ·
2. Element 0 is an identity element for +
Element 1 is an identify element for ·
◼ x+0=0+x=x
◼ x · 1=1 · x=x
Definition of Boolean Algebra (cont.)

3. The structure is commutative with respect to + and · :

◼a+b=b+a
◼a·b=b·a

4. The operator · is distributive over +

The operation + is distributive over ·
◼a·(b+c)=(a·b)+(a·c)
◼a+(b·c)=(a+b)·(a+c )
Definition of Boolean Algebra (cont.)

5. For every element aS there exists an element a’S

such that
◼ a+ a’=1
◼ a · a’=0
6. There exist at least two elements a,bS such that a≠b
 Associative Law

 Note that the postulates do not include the

associative law
 a + (b + c) = (a + b) + c
 a · (b · c) = (a · b) · c

 However, the associative law holds and can be

derived from the postulates
 Comparison with ordinary algebra

 The distributive law of + over · is not valid for

regular algebra
◼ a+(b·c)=(a+b)·(a+c)
 Boolean algebra does not have additive or
multiplicative inverses; therefore there are no
subtraction or division operations
 Postulate 5 ( a+ a’=1, a · a’=0) is not available in
ordinary algebra
 Two-valued Boolean Algebra

 Is defined on a set of two elements B={0,1}, with

the rules for two operators + and · as shown
below:

x·y x+y
 Two-valued Boolean Algebra (cont.)

 It can be easily shown that postulates 1-6 are

valid for the set S={0,1} and two operators +
and ·
 For postulate 5 we use the following complement
operator:
x’
 Two-valued Boolean Algebra (cont.)

 The validity can be checked by means of truth

tables.
 In truth tables, both sides of the relation are checked
to have identical results for all possible combinations
of variables
 Ex, for the distributive law:
 a·(b+c)=(a·b)+(a·c)
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.
 Follows from the structure of the posulates
Duality

 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.
DeMorgan’s Theorem

 A key theorem in simplifying Boolean algebra

expression is DeMorgan’s Theorem. It states:
(a + b)’ = a’b’ (ab)’ = a’ + b’

 Complement the expression

a(b + z(x + a’)) and simplify.

(a(b+z(x + a’)))’ = a’ + (b + z(x + a’))’

= a’ + b’(z(x + a’))’
= a’ + b’(z’ + (x + a’)’)
= a’ + b’(z’ + x’a’’)
= a’ + b’(z’ + x’a)
Postulates and Basic Theorems
 Theorem 1(a)

 This theorem states:

x+x= x
 Proof:
 Theorem 1(b)

 This theorem states:

x · x= x
 Proof:
 Theorem 2(a)

 This theorem states:

x +1= 1
 Proof:
 Theorem 2(b)

 This theorem states:

x · 0= 0
 Proof (hint - use the duality property):
 Consensus Properties

 This theorem states:

x y + x’z= xy + yz + x’z

 The dual is also valid.

CIRCUIT REPRESENTATIONS
 Overview

 Expressing Boolean functions

 Relationships between algebraic equations, symbols,
and truth tables
 Simplification of Boolean expressions
 Minterms and Maxterms
 AND-OR representations
 Product of sums
 Sum of products
 Boolean Functions

 Boolean algebra deals with binary variables and

logic operations.
 Function results in binary 0 or 1
x y z F
0 0 0 0
0 0 1 0 x
0 1 0 0 y
0 1 1 0 F = x(y+z’)
z y+z’
1 0 0 1 z’
1 0 1 0
1 1 0 1
1 1 1 1 F = x(y+z’)
Boolean Functions

x y z xy yz G
0 0 0 0 0 0
0 0 1 0 0 0 x xy
0 1 0 0 0 0 y
0 1 1 0 1 1 G = xy +yz
1 0 0 0 0 0 z
yz
1 0 1 0 0 0
1 1 0 1 0 1 We will learn how to transition between equation,
1 1 1 1 1 1 symbols, and truth table.
 Representation Conversion

 Need to transition between boolean expression,

truth table, and circuit (symbols).

Circuit Boolean
Expression

Truth
Table
Truth Table to Expression

 Converting a truth table to an expression

 Each row with output of 1 becomes a product term
 Sum product terms together.
x y z G Any Boolean Expression can be
0 0 0 0 represented in sum of products form!
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
xyz + xyz’ + x’yz
Equivalent Representations of
Circuits
 All three formats are equivalent
 Number of 1’s in truth table output column equals AND terms for
Sum-of-Products (SOP)
x y z G
0 0 0 0
0 0 1 0 x x
x
0 1 0 0 G
x
0 1 1 1 x
x
1 0 0 0 x
1 0 1 0 x
x
1 1 0 1
1 1 1 1

x y z
G = xyz + xyz’ + x’yz
 Reducing Boolean Expressions
 Is this the smallest possible implementation of this
expression? No! G = xyz + xyz’ + x’yz
 Use Boolean Algebra rules to reduce complexity
while preserving functionality.
 Step 1: Use Theorem 1 (a + a = a)
 So xyz + xyz’ + x’yz = xyz + xyz + xyz’ + x’yz

 Step 2: Use distributive rule a(b + c) = ab + ac

 So xyz + xyz + xyz’ + x’yz = xy(z + z’) + yz(x + x’)
 Step 3: Use Postulate 3 (a + a’ = 1)
 So xy(z + z’) + yz(x + x’) = xy · 1 + yz · 1
 Step 4: Use Postulate 2 (a · 1 = a)
 So xy · 1 + yz · 1 = xy + yz = xyz + xyz’ + x’yz
 Reduced Hardware
Implementation
 Reduced equation requires less hardware!
 Same function implemented!
x y z G
0 0 0 0
0 0 1 0 x x
0 1 0 0 G
0 1 1 1
1 0 0 0
1 0 1 0 x
x
1 1 0 1
1 1 1 1

x y z
G = xyz + xyz’ + x’yz = xy + yz
 Minterms and Maxterms

 Each variable in a Boolean expression is a literal

 Boolean variables can appear in normal (x) or complement form (x’)
 Each AND combination of terms is a minterm
 Each OR combination of terms is a maxterm
For example: For example:
Minterms Maxterms

x y z Minterm x y z Maxterm
0 0 0 x’y’z’ m0 0 0 0 x+y+z M0
0 0 1 x’y’z m1 0 0 1 x+y+z’ M1
… …
1 0 0 xy’z’ m4 1 0 0 x’+y+z M4
… …
1 1 1 xyz m7 1 1 1 x’+y’+z’ M7
Representing Functions with Minterms

 Minterm number same as row position in truth table

(starting from top from 0)
 Shorthand way to represent functions
x y z G
0 0 0 0 G = xyz + xyz’ + x’yz
0 0 1 0
0 1 0 0
0 1 1 1
G = m7 + m6 + m3 = Σ(3, 6, 7)
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
 Complementing Functions

 Minterm number same as row position in truth table

(starting from top from 0)
 Shorthand way to represent functions
x y z G G’
0 0 0 0 1 G = xyz + xyz’ + x’yz
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0 G’ = (xyz + xyz’ + x’yz)’ =
1 0 0 0 1
1 0 1 0 1
1 1 0 1 0 Can we find a simpler representation?
1 1 1 1 0
 Complementing Functions
 Step 1: assign temporary names
 b+ c→ z G = a + b+ c
 (a + z)’ = G’ G’ = (a + b + c)’
 Step 2: Use DeMorgans’ Law
 (a + z)’ = a’ · z’
 Step 3: Resubstitute (b+c) for z
 a’ · z’ = a’ · (b + c)’
 Step 4: Use DeMorgans’ Law G = a + b+ c
 a’ · (b + c)’ = a’ · (b’ · c’) G’ = a’ · b’ · c’ = a’b’c’
 Step 5: Associative rule
 a’ · (b’ · c’) = a’ · b’ · c’
Conversion Between Canonical Forms
 Easy to convert between minterm and maxterm
representations
 For maxterm representation, select rows with 0’s
x y z G
0 0 0 0 G = xyz + xyz’ + x’yz
0 0 1 0
0 1 0 0
0 1 1 1 G = m7 + m6 + m3 = Σ(3, 6, 7)
1 0 0 0
1 0 1 0
1 1 0 1 G = M0M1M2M4M5 = Π(0,1,2,4,5)
1 1 1 1

G = (x+y+z)(x+y+z’)(x+y’+z)(x’+y+z)(x’+y+z’)
Representation of Circuits

 All logic expressions can be represented in 2-level format

 Circuits can be reduced to minimal 2-level representation
 Sum of products representation most common in industry.
Venn Diagrams
Venn Diagram: A+B
Venn Diagram: A.B
Containment
Venn Diagram: A’B
Venn Diagram: A+B’
Venn Diagram: (A+B’)’ = A’.B
Venn Diagram: A’+B’ =?
Venn Diagram: A’+B’ = (AB)’
Venn Diagram: 3 Variables
Summary

 Truth table, circuit, and boolean expression

formats are equivalent
 Easy to translate truth table to SOP and POS
representation
 Boolean algebra rules can be used to reduce
circuit size while maintaining function
 Venn Diagrams can be used to represent Boolean
expressions.
 All logic functions can be made from AND, OR,
and NOT
Codes
 Binary Coded Decimal
Digit BCD Digit BCD
Code Code
0 0000 5 0101
1 0001 6 0110
2 0010 7 0111
3 0011 8 1000
4 0100 9 1001

 Binary coded decimal (BCD) represents each decimal

digit with four bits
 Ex· 0011 0010 1001 = 32910
3 2 9

 This is NOT the same as 0011001010012

 Why do this? Because people think in decimal.
Putting It All
Together

° BCD not very efficient.

° Used in early
computers (40s, 50s).
° Used to encode
numbers for seven-
segment displays.
° Easier to read?
Gray Code
Digit Binary Gray
Code
0 0000 0000  Gray code is not a number
1 0001 0001 system.
2 0010 0011  It is an alternate way to represent four
3 0011 0010 bit data
4 0100 0110  Only one bit changes from
5 0101 0111
6 0110 0101
one decimal digit to the next
7 0111 0100  Useful for reducing errors in
8 1000 1100 communication.
9 1001 1101
10 1010 1111  Can be scaled to larger
11 1011 1110 numbers.
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000
 ASCII Code
 American Standard Code for Information
Interchange
 ASCII is a 7-bit code, frequently used with an 8th bit
for error detection.
Character ASCII (bin) ASCII (hex) Decimal Octal
A 1000001 41 65 101
B 1000010 42 66 102
C 1000011 43 67 103
…
Z
a
…
1
‘
ASCII Codes and Data Transmission

° ASCII Codes
° A – Z (26 codes), a – z (26 codes)
° 0-9 (10 codes), others (@#$%^&*…·)