Digital Logic Design Lecture 5 Agenda and Examples
Explore the agenda for Digital Logic Design Lecture 5 covering Boolean algebra, canonical forms, manipulations of Boolean formulas, equation complementation, expansion about a variable, and examples. Get ready for homework submissions and the upcoming midterm. Homework solutions are available on Canvas.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
ENEE244-02xx Digital Logic Design Lecture 5
Announcements Homework 1 solutions are on Canvas Homework 2 due on Thursday Coming up: First midterm on Sept. 30
Agenda Last time: Boolean Algebra axioms and theorems (3.1,3.2) Canonical Forms (3.5) This time: Finish up Canonical Forms (3.5) Manipulations of Boolean Formulas (3.6) Gates and Combinational Networks (3.7) Incomplete Boolean Functions and Don t Care Conditions (3.8 )
Canonical Forms (Review) X Y Z f 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0 ? ?,?,? = ?(1,3,4) ? ?,?,? = ?(0,2,5,6,7)
Canonical Forms Conversion Minterm to Maxterm: ? ?,?,? = ? 2,5,6,7 ? ?,?,? = ? 0,1,3,4 ? ?,?,? = ? 0,1,3,4 Maxterm to Minterm: ? ?,?,? = ? 1,2,3,5,7 ? ?,?,? = ? 0,4,6 ? ?,?,? = ? 0,4,6
Equation Complementation For every Boolean function ? there is an associated complementary function ? in which ? ?1, ,?? = 1 iff ? ?1, ,?? = 0. Example: ? = ??? + ? ? + ?? ? = ??? + ? ? + ??
Equation Complementation Use DeMorgan s Law to simplify: ? = ??? + ? ? + ?? = (???) [? ? + ?? ] = ? + ? + ? ? ? + ?? = ? + ? + ? [? + ? + ?? ] = ? + ? + ? [? + ? (? + ?) ]
Expansion about a Variable Rewrite a Boolean formula ?(?1, ,??) so that it has the structure: ? ?1, ,?? = ???1+ ???2OR ? ?1, ,?? = (??+ 1) ??+ 2
Expansion about a Variable Theorem 3.11 (a)? ?1, ,??, ,?? = ?? ? ?1, ,1, ,?? + ?? ?(?1, ,0, ,??) (b) ? ?1, ,??, ,?? = (??+? ?1, ,1, ,??)(??+ ? ?1, ,0, ,??)
Expansion about a Variable Examples: ? ?,?,?,? = ? ? + ?? + ? ? Expansion about ?: (??1+ ??2) ?? ?,1,?,? + ?? ?,0,?,? = ? ? + ? ? + ?(? + ??)
Shannons Reduction Theorems Used for obtaining simplified Boolean formula. Theorem 3.12 (a) ?? ? ?1, ,??, ,?? = ?? ?(?1, ,1, ,??) (b) ??+ ? ?1, ,??, ,?? = ??+ ?(?1, ,0, ,??) Theorem 3.13 (a)?? ? ?1, ,??, ,?? = ?? ?(?1, ,0, ,??) (b) ??+ ? ?1, ,??, ,?? = ??+ ?(?1, ,1, ,??)
Example of Equation Simplification ? ?,?,?,? = ? + ? ? + ? ?(? + ?)(? + ??) = ? + ? + ? ? + ? (? + ??) = ? + ? + ?? (? + ?) = ? + ? + ?? (? + ?) = ? + ? + ??
Digital Logic Gates AND OR NOT (Inverter) Buffer (Transfer) NAND NOR XOR X-NOR (Equivalence) ? ?,? = ?? ? ?,? = ? + ? ? ? = ? ? ? = ? ? ?,? = (??) = ? + ? ? ?,? = ? + ? = ? ? ? ?,? = ? ? + ? ? = ? ? ? ?,? = ?? + ? ?
Gates and Combinational Networks Synthesis Procedure Example: Truth table for parity function on three variables X Y Z f 0 0 0 0 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 1
Synthesis Procedure X Y Z f 0 0 0 0 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 1 Minterm Canonical Form: ? ?,?,? = ? ?? + ?? ? + ?? ? + xyz
Two-level Gate Network Minterm Canonical Form: ? ?,?,? = ? ?? + ?? ? + ?? ? + ??? ? ? ? ? ? ? ? ? ? ? ? ?
Incomplete Boolean Functions and Don t Care Conditions
Incomplete Boolean Functions and Don t Care Conditions n-variable incomplete Boolean function is represented by a truth table with n+1 columns and 2? rows. For those combinations of values in which a functional value is not to be specified, a symbol, - -, is entered. The complement of an incomplete Boolean function is also an incomplete Boolean function having the same unspecified rows of the truth table.
Describing Incomplete Boolean Functions X Y Z F 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 -- 1 0 0 0 1 0 1 -- 1 1 0 0 1 1 1 1 Minterm canonical formula: ? ?,?,? = ? 0,1,7 + ??(3,5)
Describing Incomplete Boolean Functions X Y Z F 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 -- 1 0 0 0 1 0 1 -- 1 1 0 0 1 1 1 1 Maxterm canonical formula: ? ?,?,? = ? 2,4,6 + ??(3,5)
Describing Incomplete Boolean Functions Manipulating Boolean equations derived from incomplete Boolean functions is a very difficult task. In the next chapter, there are procedures for obtaining minimal expressions that can handle the don t care conditions. Can leverage don t care conditions to get simplified expressions for functions (smaller gate networks).
{??,? ?} {??,??}
