Toán học - Chapter 12: Boolean algebra

Boolean AlgebraChapter 12Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.Chapter SummaryBoolean FunctionsRepresenting Boolean FunctionsLogic GatesMinimization of Circuits (not currently included in overheads)Claude Shannon (1916 - 2001)Boolean FunctionsSection 12.1Section SummaryIntroduction to Boolean AlgebraBoolean Expressions and Boolean FunctionsIdentities of Boolean AlgebraDualityThe Abstract Definition of a Boolean AlgebraIntroduction to Boolean Algebra Boolean Expressions and Boolean FunctionsDefinition: 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) Boolean Expressions and Boolean Functions (continued) Boolean Functions The example tells us that there are 16 different Boolean functions of degree two. We display these in Table 3. Identities of Boolean AlgebraEach identity can be proved using a table.All identities in Table 5, except for the first and the last two come in pairs. Each element of the pair is the dual of the other (obtained by switching Boolean sums and Boolean products and 0’s and 1’s.The Boolean identities correspond to the identities of propositional logic (Section 1.3) and the set identities (Section 2.2).Identities of Boolean AlgebraExample: Show that the distributive law x(y + x) = xy + xz is valid.Solution: We show that both sides of this identity always take the same value by constructing this table.Formal Definition of a Boolean Algebra x ∨ 0 = xx ∧ 1 = x  (x ∨ y ) ∨ z = x ∨ (y ∨ z) (x ∧ y ) ∧ z = x ∧ (y ∧ z) x ∨ y = y ∨ x x ∧ y = y ∧ x x ∨ (y ∧ z) = (x ∨ y) ∧ (y ∨ z) x ∧ (y ∨ z ) = (x ∧ y) ∨ (y ∧ z) identity laws complement lawsassociative lawscommutative lawsdistributive lawsThe set of propositional variables with the operators ∧ and ∨, elements T and F, and the negation operator ¬ is a Boolean algebra. Representing Boolean FunctionsSection 12.2Section SummarySum-of-Products ExpansionsFunctional CompletenessSum-of-Products Expansion The general principle is that each combination of values of the variables for which the function has the value 1 requires a term in the Boolean sum that is the Boolean product of the variables or their complements. Sum-of-Products Expansion (cont) Sum-of-Products Expansion (cont) Sum-of-Products Expansion (cont) Functional Completeness Logic GatesSection 12.3Section SummaryLogic GatesCombinations of GatesExamples of CircuitsLogic GatesWe construct circuits using gates, which take as input the values of two or more Boolean variables and produce one or more bits as output, and inverters, which take the value of a Boolean variable as input and produce the complement of this value as output.Combinations of Gates Combinations of Gates AddersLogic circuits can be used to add two positive integers from their binary expansions. The first step is to build a half adder that adds two bits, but which does not accept a carry from a previous addition.Since the circuit has more than one output, it is a multiple output circuit. Adders (continued)A full adder is used to compute the sum bit and the carry bit when two bits and a carry are added.Adders (continued)A half adder and multiple full adders can be used to produce the sum of n bit integers. Example: Here is a circuit to compute the sum of two three-bit integers.