8.2. BOOLEAN FUNCTIONS, APPLICATIONS 1238.2. Boolean Functions, Applications8.2.1. Introduction. A Boolean function is a function from Zn2to Z2. For instance, consider the exclusive-or function, defined by thefollowing table:x1x2x1Y x21 1 01 0 10 1 10 0 0The exclusive-or function can interpreted as a function Z22→ Z2that assigns (1, 1) 7→ 0, (1, 0) 7→ 1, (0, 1) 7→ 1, (0, 0) 7→ 0. It can alsobe written as a Boolean expression in the following way:x1Y x2= (x1∧ ¯x2) ∨ (¯x1∧ x2)Every Boolean function can be writtenas a Boolean expression aswe are going to see next.8.2.2. Disjunctive Normal Form. We startwith a definition.A minterm in the symbols x1, x2. . . , xnis a Boolean expression of theform y1∧ y2∧ ··· ∧ yn, where each yiis either xior ¯xi.Given any Boolean function f :Zn2→ Z2that is not identicallyzero, it can berepresentedf(x1, . . . , xn) = m1∨ m2∨ ··· ∨ mk,where m1, m2, . . . , mkare all the minterms mi= y1∧y2∧···∧ynsuchthat f(a1, a2, . . . , an) = 1, where yj= xjif aj= 1 and yj= ¯xjif aj= 0.That representation is called disjunctive normal formof the Booleanfunction f.Example: Wehave seen that the exclusive-or can be representedx1Y x2= (x1∧ ¯x2) ∨ ( ¯x1∧ x2). This provides a way to implement theexclusive-or with a combinatorial circuit as shown in figure 8.4.8.2.3. Conjunctive Normal Form. A maxterm in the symbolsx1, x2. . . , xnis a Boolean expression of the form y1∨y2∨···∨yn, whereeach yiis either xior ¯xi.8.2. BOOLEAN FUNCTIONS, APPLICATIONS 124x1x2x2x1Figure 8.4. Exclusive-Or.Given any Boolean function f : Zn2→ Z2that is not identicallyone, it can be representedf(x1, . . . , xn) = M1∧ M2∧ ··· ∧ Mk,where M1, M2, . . . , Mkare all the maxterms Mi= y1∨ y2∨ ··· ∨ ynsuch that f(a1, a2, . . . , an) = 0, where yj= xjif aj= 0 and yj= ¯xjifaj= 1. That representation is called conjunctive normal form of theBoolean function f.Example: The conjunctive normal form of the exclusive-or isx1Y x2= (x1∨ x2) ∧ (¯x1∨ ¯x2) .8.2.4. Functionally Complete Sets of Gates. We have seenhow to design combinatorialcircuits using AND, OR and NOT gates.Here we will see how to do the same with other kinds of gates. In thefollowing gates will be considered as functions from Zn2into Z2intendedto serve as building blocks of arbitrary boolean functions.A set of gates {g1, g2, . . . , gk} is said to be functionally completeif for any integer n and any function f : Zn2→ Z2it is possible toconstruct a combinatorial circuit that computes f using only the gatesg1, g2, . . . , gk. Example: The result about the existence of a disjunctivenormal form for any Boolean function proves that the set of gates{AND,OR, NOT} is functionally complete. Next we show other setsof gates that are also functionally complete.1.The set of gates {AND, NOT} is functionally complete. Proof:Since we already know that {AND, OR, NOT} is functionallycomplete, all we need to do is to show that we can computex ∨ y using only AND and NOT gates.In fact:x ∨ y = ¯x ∧ ¯y ,hence the combinatorialcircuit of figure 8.5 computes x ∨ y.8.2. BOOLEAN FUNCTIONS, APPLICATIONS 125x1 x2x2x1Figure 8.5. OR with AND and NOT.2. The set of gates {OR, NOT} is functionally complete. Theproof is similar:x ∧ y =¯x ∨ ¯y ,hence the combinatorialcircuit of figure 8.6 computes x ∨y.x1x1 x2x2Figure 8.6. AND with OR and NOT.3. The gate NAND, denoted ↑ and defined asx1↑ x2=(0 if x1= 1 and x2= 11 otherwise,is functionally complete.x1x1 x2x2Figure 8.7. NAND gate.Proof: Note that x ↑ y = x ∧ y. Hence ¯x = x ∧ x = x ↑ x,so theNOT gate can be implemented with a NAND gate. Alsothe OR gate can be implemented with NAND gates: x ∨ y =¯x ∧ ¯y = (x ↑ x) ↑ (y ↑ y). Since the set {OR, NOT} is func-tionally complete and each of its elements can be implementedwith NAND gates, the NAND gate is functionally complete.8.2.5. Minimization of Combinatorial Circuits. Here we ad-dress the problems of finding a combinatorial circuit that computes agiven Boolean function with the minimum number of gates. The ideais to simplify the corresponding Boolean expressionby using algebraic8.2. BOOLEAN FUNCTIONS, APPLICATIONS 126x yxxxyFigure 8.8. NOT and OR functions implemented withNAND gates.properties such as (E ∧ a) ∨ (E ∧ ¯a) = E and E ∨ (E ∧ a) = E, whereEis any Boolean expression. For simplicity in the following we willrepresent a ∧ b as ab, so for instance the expressions above will looklike this: Ea ∨ E¯a = E and E ∨ Ea = E.Example: Let F (x, y, z) the Boolean function defined by the follow-ing table:x y z f(x,y,z)1 1 1 11 1 0 11 0 1 01 0 0 10 1 1 00 1 0 00 0 1 00 0 0 0Its disjunctive normal form is f(x, y, z) = xyz ∨ xy¯z ∨ x¯y¯z. Thisfunction can be implemented with the combinatorial circuit of figure8.9.zyx.f(x,y,z)Figure 8.9. A circuit that computes f(x, y, z) = xyz ∨xy¯z ∨ x¯y¯z.8.2. BOOLEAN FUNCTIONS, APPLICATIONS 127But we can do better if we simplify the expression in the followingway:f(x, y, z) =xyz }| {xyz ∨ xy¯z ∨x¯y¯z= xy ∨ x¯y¯z= x(y ∨ ¯y¯z)= x(y ∨ ¯y)(y ∨ ¯z)= x(y ∨ ¯z) ,which corresponds to the circuit of figure 8.10.f(x,y,z).yxzFigure 8.10. A simpler circuit that computesf(x,y, z) = xyz ∨ xy¯z ∨ x¯y¯z.8.2.6. Multi-Output CombinatorialCircuits. Example: Half-Adder. A half-adder is a combinatorial circuit with two inputs x andy and two outputs s and c, where s represents the sum of x and y andc is the carry bit. Its table is as follows:x y s c1 1 0 11 0 1 00 1 1 00 0 0 0So the sum is s = x Y y (exclusive-or) and the carry bit is c = x ∧y.Figure 8.11 shows a half-adder circuit.yscxFigure 8.11. Half-adder