tailieunhanh - Lecture Discrete mathematics and its applications (7/e) – Chapter 12: Boolean algebra

Lecture Discrete mathematics and its applications (7/e) – Chapter 12: Boolean algebra. This chapter presents the following content: Boolean functions, representing boolean functions, logic gates, minimization of circuits. | Boolean Algebra Chapter 12 Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Boolean Functions Representing Boolean Functions Logic Gates Minimization of Circuits (not currently included in overheads) Claude Shannon (1916 - 2001) Boolean Functions Section Section Summary Introduction to Boolean Algebra Boolean Expressions and Boolean Functions Identities of Boolean Algebra Duality The Abstract Definition of a Boolean Algebra Introduction to Boolean Algebra Boolean algebra has rules for working with elements from the set {0, 1} together with the operators + (Boolean sum), (Boolean product), and . These operators are defined by: Boolean sum: 1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0 Boolean product: 1 1 = 1, 1 0 = 0, 0 1 = 0, 0 0 = 0 complement: = 1, = 0 Example: Find the value of 1 0 + Solution : 1 0 + = 0 + = 0 + 0 = 0 Boolean Expressions and Boolean Functions Definition: Let B = {0, 1}. Then Bn = {(x1, x2, , xn) | xi ∈ B for 1 ≤ i ≤ n } is the set of all possible n-tuples of 0s and 1s. The variable x is called a Boolean variable if it assumes values only from B, that is, if its only possible values are 0 and 1. A function from Bn to B is called a Boolean function of degree n. Example: The function F(x, y) = x from the set of ordered pairs of Boolean variables to the set {0, 1} is a Boolean function of degree 2. Boolean Expressions and Boolean Functions (continued) Example: Find the values of the Boolean function represented by F(x, y, z) = xy + . Solution: We use a table with a row for each combination of values of x, y, and z to compute the values of F(x,y,z). Boolean Expressions and Boolean Functions (continued) Definition: Boolean functions F and G of n variables are equal if and only if F(b1, b2, , bn)= G(b1, b2, , bn) whenever b1, b2, , bn belong to B. Two different Boolean expressions that represent the same function are . | Boolean Algebra Chapter 12 Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Boolean Functions Representing Boolean Functions Logic Gates Minimization of Circuits (not currently included in overheads) Claude Shannon (1916 - 2001) Boolean Functions Section Section Summary Introduction to Boolean Algebra Boolean Expressions and Boolean Functions Identities of Boolean Algebra Duality The Abstract Definition of a Boolean Algebra Introduction to Boolean Algebra Boolean algebra has rules for working with elements from the set {0, 1} together with the operators + (Boolean sum), (Boolean product), and . These operators are defined by: Boolean sum: 1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0 Boolean product: 1 1 = 1, 1 0 = 0, 0 1 = 0, 0 0 = 0 complement: = 1, = 0 Example: Find the value of 1 0 + Solution : 1 0 + = 0 + = 0 + 0 = 0 Boolean Expressions and Boolean .