3.7. References 65
(a)A 1-bitadd1module just has inputa 0. Write propositional formulas for its
outputscandp 0.
(b)Explain how to build an.nC1/-bit parallel half-adder from an.nC1/-bitadd1
module by writing a propositional formula for the half-adder output,oi, using only
the variablesai,pi, andb.
We can build a double-sizeadd1module with2.nC1/inputs using two single-
sizeadd1modules 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 sizeadd1module 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.)
Exam Problems
Problem 3.7.
There are exactly two truth environments (assignments) for the variablesM;N;P;Q;R;S
that satisfy the following formula:
.„PORƒ‚Q/...
clause (1)AND.„QORƒ‚R/...
clause (2)AND.„RORƒ‚S/...
clause (3)AND.„SORƒ‚P/...
clause (4)ANDMAND N
(a)This claim could be proved by truth-table. How many rows would the truth
table have?
(b)Instead of a truth-table, prove this claim with an argument by cases according
to the truth value ofP.