Class Notes (837,550)
Canada (510,314)
Lecture

continuation of Boolean algebra

23 Pages
100 Views
Unlock Document

Department
Computer Engineering
Course
COMPENG 2DI4
Professor
Xudong Zhu
Semester
Fall

Description
SLIDES FOR CHAPTER 3 BOOLEAN ALGEBRA This Objectives the book includes: Study Guide 3.1 Multiplying Out and Factoring Expressions 3.2 Exclusive-OR and Equivalence Operations 3.3 The Consensus Theorem 3.5 Proving the Validity of an Equationng Expressions Programmed Exercises Problems Click the mouse to move to the next page. Use the ESC key to exit this chapter. Distributive Laws Given an expression in product-of-sums form, the corresponding sum-of-products expression can be obtained by multiplying out, using the two distributive laws: X(Y + Z) = XY + XZ (3-1) (X + Y)(X + Z) = X + YZ (3-2) In addition, the following theorem is very useful for factoring and multiplying out: (X + Y)(X′ + Z) = XZ + X′Y (3-3) In the following example, if we were to multiply out by brute force, we would generate 162 terms, and 158 of these terms would then have to be eliminated to simplify the expression. Instead, we will use the distributive laws to simplify the process. Example (3-4), p. 63 The same theorems that are useful for multiplying out expressions are useful for factoring. By repeatedly applying (3-1), (3-2), and (3-3), any expression can be converted to a product-of-sums form. Exclusive-OR and Equivalence Operations The exclusive-OR operation ( ) is defined as follows: The equivalence operation ( ) is defined by: We will use the following symbol for an exclusive-OR gate: Section 3.2, p. 64 The following theorems apply to exclusive OR: Controlled inverter We will use the following symbol for an equivalence gate: Section 3.2, p. 65 The equivalence gate is also called an exclusive-NOR gate. Example 1: By (3-6) and (3-17), F = [(A′B)C + (A′B)′C′ ] + [B′(AC′) + B(AC′)′ ] = A′BC + (A + B′)C′ + AB′C′ + B(A′ + C) = B(A′C + A′ + C) + C′(A + B′ + AB′) = B(A′ + C) + C′(A + B′) Example 2: = (A′B′ + AB)C′ + (A′B′ + AB) ′C (by (3-6)) = (A′B′ + AB)C′ + (A′B + AB′)C (by (3-19)) = A′B′C′ + ABC′ + A′BC + AB′C Section 3.2 (p. 66) The Consensus Theorem The consensus theorem can be stated as follows: XY + X'Z + YZ = XY + X'Z (3-20) Dual Form: (X + Y)(X’ + Z)(Y + Z) = (X + Y)(X’ +(3-21) Section 3.2 (p. 66-67) Consensus Theorem Proof XY + X'Z + Y= (XY + XYZ) + (X'Z + X'YZ) = XY(1 + Z) + X'Z(1 + Y) = XY + X'Z Section 3.3 (p. 67) Basic methods for simplifying functions 1. Combining terms. Use the theorem XY + XY′ = X to combine two terms. For example, abc′d′ + abcd′ = abd′ [X = abd′, Y = c] (3-24) 2. Eliminating terms. Use the theorem X + XY = X to eliminate redundant terms if possible; then try to apply the consensus theorem (XY + X′Z + YZ = XY + X′Z) to eliminate any consensus terms. For example, a′b + a′bc = a′b [X = a′b] a′bc′ + bcd + a′bd = a′bc′ + bc[X = c, Y = bd, Z = a′b] (3-24) Section 3.4 (p. 68-69) 3. Eliminating literals. Use the theorem X + X’Y = X + Y to eliminate redundant literals. Simple factoring may be necessary before the theorem is applied. A′B + A′B′C′D′ + ABCD′ = A′(B + B′C′D′) + ABCD′ = A′(B + C′D′) + ABCD′ = B(A′ + ACD′) + A′C′D′ = B(A′ + CD′) + A′C′D′ = A′B + BCD′ + A′C′D′ (3-26) 4. Adding redundant terms. Redundant terms can be introduced in several ways such as adding xx′, multiplying by (x + x′), adding yz to xy + x′z, or adding x
More Less

Related notes for COMPENG 2DI4

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit