《Discrete Mathematics II教学-华南理工》Lecture 5 Lattices and Boolean Algebra.pptVIP

Boolean Functions and Expressions Definition: Let B = {0, 1}. The variable x is called a Boolean variable if it assumes values only from B. A function from Bn, the set {(x1, x2, …, xn) |xi?B, 1 ? i ? n}, to B is called a Boolean function of degree n. Boolean functions can be represented using expressions made up from the variables and Boolean operations. Boolean Operations The complement is denoted by a bar (on the slides, we will use a minus sign). It is defined by 0’ = 1 and 1’ = 0. The Boolean sum, denoted by + or by OR, has the following values: 1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0 The Boolean product, denoted by ? or by AND, has the following values: 1 ? 1 = 1, 1 ? 0 = 0, 0 ? 1 = 0, 0 ? 0 = 0 Boolean Functions and Expressions The Boolean expressions in the variables x1, x2, …, xn are defined recursively as follows: 0, 1, x1, x2, …, xn are Boolean expressions. If E1 and E2 are Boolean expressions, then (E1’),  (E1E2), and (E1 + E2) are Boolean expressions. Each Boolean expression represents a Boolean function. The values of this function are obtained by substituting 0 and 1 for the variables in the expression. Boolean Functions and Expressions For example, we can create Boolean expression in the variables x, y, and z using the “building blocks”0, 1, x, y, and z, and the construction rules: Since x and y are Boolean expressions, so is xy. Since z is a Boolean expression, so is z’. Since xy and (z’) are expressions, so is xy + z’. … and so on… Simplification using Boolean Algebra A simplified Boolean expression uses the fewest gates possible to implement a given expression. Example Using Boolean algebra techniques, simplify this expression: AB + A(B + C) + B(B + C) Simplification Solution for simplification of: AB + A(B + C) + B(B + C) Step 1: Apply the distributive law to the second and third terms in the expression, as follows: AB + AB + AC + BB + BC Step 2: Apply rule