Lecture 3: Boolean Algebra: CS-216: Digital Logic Design

Lecture 3: Boolean Algebra
CS-216: Digital Logic Design

September 7, 2015
Lecture Overview
• Boolean Algebra definitions
• Basic postulates of Boolean algebra
• Boolean expressions, simplification through
Boolean Algebra reduction, and their
corresponding logic diagrams
• Exercises
Boolean Algebra
• Boolean Algebra resembles ordinary Algebra
(very strong correspondence)
• Mathematical structure
– Elements
– Operators
– Postulates
• This mathematical structure is called a “Field”
Definitions
• Set of Elements B = { 0, 1 }
• Operators:
– Binary operators
• AND: Symbol for two elements a and b: a • b
• OR: Symbol for two elements a and b: a + b
– Unary operator
• NOT: Symbol for a generic element a: a’ or ā
• Postulates: Huntington Postulates (defined in
pairs to represent “duality”
Why Study Boolean Algebra
• To analyze and design a solution for a problem, you need to
define it first.
• Boolean algebra can be used to model and analyze a large
category of engineering problems: Propositional logic.
• Computers are basically logic operators. They store binary
information (1/0, or True/False), and can only perform logic
operations on this information. Other type of information
processing has to be derived from binary information.
• Example: “If I complete Digital Logic Design course and
don’t have excessive study load, then I will take Advanced
Digital Design with HDL course”.
Propositional Logic
Propositional Logic
• Statement: “If I complete Digital Logic Design course and don’t have
excessive study load, then I will take Advanced Digital Design with
HDL course”.
• Decompose:
– Proposition 1: Digital Logic Design course completion (true or false) –
Symbolize this with a.
– Proposition 2: Excessive study load (true or false) – Symbolize this with
b.
– Take “ADD with HDL” course (true or false) – symbolize this with q.
– Operators: binary operator AND (•), and unary operator NOT(’)
• Representation of the propositional logic statement:
q = a • b’
• Remember, maths is a language!!!
Steps in Solving Engineering Problems
• Problem Definition
• Modeling and Analysis
• Design and Implementation
• Realization
Engineering Problem
• Let’s arrange a party on Thursday
• Divide it into simpler binary “true” or “false” level propositions
– Homework due on Friday
• GS211 = a
• ET212 = b
• MT213 = c
• MT214 = d
• CS215 = e
• CS216 = f
– Classes on Thursday
• GS211 = u
• ET212 = v
• MT213 = w
• MT214 = x
• CS215 = y
• CS216 = z
– Party on Thursday = q
• Boolean expression representing party actually taking place on Thursday
q = (a + b + c + d + e + f)’ • (u + v + w + x + y + z)’
Engineering Problem (cont.)
• University rules changed, and only three courses offered in third semester: Homework
on Friday for GS211 = a, ET212 = b, MT213 = c. Classes on Thurdsay doesn’t matter,
because no matter what, classes will finish before the evening. Furthermore, you can
complete assignment for one subject, but not more after the party.
a b c q
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0
q = a’b’c’ + a’b’c + a’bc’ + ab’c’ (from sum of products method)
OR q = (a+b’+c’)(a’+b+c’)(a’+b’+c)(a’+b’+c’) (from product of sums method)
Simplification:
q = a’b’c’ + a’b’c + a’bc’ + ab’c’
= a’b’(c’ + c) + c’(a’b + ab’)
= a’b’ + c’((a+b’)(a’+b))’
= a’b’ + c’(aa’+ab+b’a’+b’b)’
= a’b’ + c’(ab + a’b’)’
= (a+b)’ + (c + (a’b’+ab))’
= ((a+b)(c+(a’b’+ab))’
= ((ac+bc)+(aa’b’+aab+a’bb’+abb))’
= ((ac+bc)+(ab+ab))’
= (ac+bc+ab)’
Simplification using K-Maps:
Implementation using Logic Gates:
Summary Engineering Problem Discussion
• Define the problem:
– Identifying all inputs and output(s).
– Simplify until the problem is represented by True/False propositions,
and the inputs and output(s) also take up True/False (or 1/0) values.
• Write down the truth table for the problem.
• Determine Boolean expression for the problem using the truth
table.
• Minimize the Boolean expression using Boolean Algebra
OR
Minimize using K-maps technique
• Implement using Logic gates
• Realize using discrete components, or CPLD/FPGA, or ASIC (for large
scale production)
Definitions
• Elements; B = { 0, 1 }
• Operators:
– Binary operators
• AND: Symbol for two elements a and b: a • b
• OR: Symbol for two elements a and b: a + b
– Unary operator
• NOT: Symbol for a generic element a: a’ or ā
• Postulates: Huntington Postulates (defined in pairs to
represent “duality”
NOTES:
(i) Paranthesis are used to define the order in which the operators are applied.
(ii) No subtraction or division operations defined in Boolean Algebra.
(iii) Just like Multiplication in ordinary Algebra, while writing Boolean expressions, •
is not written, i.e. ( a • b ) is written as (ab).
(iv) Operator precedence: Paranthesis, NOT, AND and OR.
Huntington’s Postulates
Postulate 1: Closure
∀ x, y ∈ B, ∃! z1 ∈ B, such that
a. x • y = z1
Similarly, ∀ x, y ∈ B, ∃! z2 ∈ B, such that
b. x + y = z2
NOTE: The postulates are written in pairs due to

the ‘principle of duality’.
Huntington’s Postulates (cont.)
Derived from Huntington’s Postulates:

Associative Law
∀ x, y, z ∈ B,
a. x ⋅ ( y ⋅ z ) = ( x ⋅ y ) ⋅ z
b. x + ( y + z ) = ( x + y ) + z
Postulate 2: Commutative Law

∀ x, y ∈ B,
a. x ⋅ y = y ⋅ x
b. x + y = y + x
Postulate 3: Identity elements

∀ x ∈ B,
a. x ⋅ 1 = x
b. x + 0 = x
Element 1 is the identity element for AND operation, and
element 0 is the identity element for OR operation.
Huntington’s Postulates
Postulate 4: Inverse or Complement

∀ x ∈ B, ∃ x’ ∈ B, such that
a. x • x’ = 0
b. x + x’ = 1
NOTE: Complement does not have a correspondence in

ordinary Algebra.
Postulate 5: Distributive Law

∀ x, y, z ∈ B,
a. x ⋅ (y + z) = (x ⋅ y) + (x ⋅ z)
b. x + (y ⋅ z) = (x + y) ⋅ (x + z)
NOTE: b. does not have correspondence in ordinary Algebra, i.e.

(+) is not distributive over (⋅).
Postulate 6
There exist at least two values x, y ∈ B, such that x ≠ y.
NOTE: Most of the time, when Boolean Algebra is mentioned, it

means “Two-valued Boolean Algebra”, in which set of elements B
= {0, 1}.
Principal of Duality
In any Boolean expression, if AND and OR
opertors are interchanged, and 0 and 1 are
interchanged, then the corresponding
expression is also true. This may be noted from
the postulates (written in pairs).
Postulates and Basic Theorems
The following postulates and basic theorems in Boolean
Algebra are often used to simplify Boolean Expressions.
Memorize them, and if that is not enough, derive the
theorems from the postulates.
Example Derivation
Theorem 1: x+x = x
Boolean Function
• Mapping from n-dimensional Boolean space
Bn to m-dimensional Boolean space Bm, where
n is the number of inputs, and m is the
number of outputs. Normally, m is 1.
• Algebraic expression consisting of binary
variables, the constants 0 and 1, and the logic
operation symbols.
• Example of a Boolean function: F1 = a+b’c
Truth Table
• For a Boolean function, a table presenting all
combinations that inputs could take, along
with corresponding value of the function. For
the Function F1 = a+b’c,
Canonical Forms
• Minterms (standard products) and Maxterms (standard sums)
• Used in converting a truth table into a Boolean expression
using “sum of products” or “product of sums”.
Example
For a Boolean function F1 = f(a,b,c) for which the
truth table has been given, find the Boolean
expression in Canonical forms.
F1 = Σ(4,5,6)
= ab’c’+ab’c+abc’
F1 = Π(0,1,2,3,7)
= (a+b+c)(a+b+c’)(a+b’+c)
(a+b’+c’)(a’+b’+c’)
Problem Session
Evaluate Boolean expression for F1 for the
following table, and simplify it.
F1 = a’b’c’+ab’c’+ab’c
+abc’+abc
F1 = (a+b+c’)(a+b’+c)(a+b’+c’)
Additional Gates
In addition to the three basic gates (or Boolean operations),
the following derived Boolean gates are commonly used.
Problem Session: Write the

truth tables for these gates.
Summary
• Definition of Boolean Algebra was covered in this
lecture. Boolean Algebra is used to formally
define a problem in mathematical terms, so that
it can be analyzed.
• Example of a problem in propositional logic was
considered, and a digital circuit was designed for
it using a formal methodology.
• Detailed steps for this methodology were
covered, which are required for analysis and
design of logic circuits for the propositional logic
problem.
Homework Assignment
1. Prove theorems 1 to 6 in the following table:
Consider this a free grade, since the solutions are provided in Morris
and Mano Book.
Homework Assignment
From the Morris/Mano text book, solve the following problems:
i. Simplify Boolean expressions given in 2.2(c), 2.2(f) using Boolean
theorems and postulates; Implement the derived expressions
using logic gate diagrams.
ii. 2.15; Draw logic gate diagram for T1 and T2.
iii. Write down Boolean expression for the following logic circuit, and
minimize the expressions for y1 and y2:

Lecture 3: Boolean Algebra: CS-216: Digital Logic Design

Uploaded by

Copyright:

Available Formats

Lecture 3: Boolean Algebra: CS-216: Digital Logic Design

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 3: Boolean Algebra: CS-216: Digital Logic Design

Uploaded by

Copyright:

Available Formats

What are the basic elements and operators of Boolean algebra?

What are the steps involved in solving engineering problems using Boolean algebra?

Lecture 3: Boolean Algebra

CS-216: Digital Logic Design

NOTE: The postulates are written in pairs due to

Derived from Huntington’s Postulates:

Postulate 2: Commutative Law

Postulate 3: Identity elements

Postulate 4: Inverse or Complement

NOTE: Complement does not have a correspondence in

Postulate 5: Distributive Law

NOTE: b. does not have correspondence in ordinary Algebra, i.e.

NOTE: Most of the time, when Boolean Algebra is mentioned, it

Problem Session: Write the

You might also like