Chapter 3 Logical Formulas58
(a)A 1-bit add1 module just has inputa 0. Write propositional formulas for its
outputscandp 0.
(b)Explain how to build annC 1 -bit parallel half-adder from annC 1 -bit add1
module by writing a propositional formula for the half-adder output,oi, using only
the variablesai,pi, andb.
We can build a double-size add1 module with2.nC1/inputs using two single-
size add1 modules withnC 1 inputs. Suppose the inputs of the double-size module
area2nC 1 ;:::;a 1 ;a 0 and the outputs arec;p2nC 1 ;:::;p 1 ;p 0. The setup is illus-
trated in Figure 3.1.
Namely, the first single size add1 module handles the firstnC 1 inputs. The in-
puts to this module are the low-ordernC 1 input bitsan;:::;a 1 ;a 0 , and its outputs
will serve as the firstnC 1 outputspn;:::;p 1 ;p 0 of the double-size module. Let
c.1/be the remaining carry output from this module.
The inputs to the second single-size module are the higher-ordernC 1 input bits
a2nC 1 ;:::;anC 2 ;anC 1. Call its firstnC 1 outputsrn;:::;r 1 ;r 0 and letc.2/be its
carry.
(c)Write a formula for the carry,c, in terms ofc.1/andc.2/.(d)Complete the specification of the double-size module by writing propositional
formulas for the remaining outputs,pi, fornC 1 i2nC 1. The formula for
pishould only involve the variablesai,ri .nC1/, andc.1/.
(e)Parallel half-adders are exponentially faster than ripple-carry half-adders. Con-
firm this by determining the largest number of propositional operations required to
compute any one output bit of ann-bit add module. (You may assumenis a power
of 2.)
Problems for Section 3.3
Class Problems
Problem 3.7. (a)Verify by truth table that
.P IMPLIES Q/ OR.Q IMPLIES P/is valid.
(b)LetPandQbe propositional formulas. Describe a single formula,R, using
AND’s,OR’s, andNOT’s such thatRis valid iffPandQare equivalent.