Exercises 119- Find all truth values for which the following combinatorial circuit gives a value of
T. Interpret this combinatorial circuit in terms of mechanizing majority rule for three
parties. (Hint: If current is interpreted as a "yes" vote and no current as a "no" vote,
then you should be able to see from a truth table when at least two of the three votes
are in favor of the measure.)
x
y
x - Prove that a combinatorial network for
(x A y A z) V (-x A y A z) V (x A --y A z) V (x A y A -z)
can be simplified to a combinatorial network representing(x A y) V (x A z) V (y A z)(Hint: Replace (x A y A z) with (x A y A Z) V (x A y A z) as often as needed.)- A half-adder circuit was given in the text. It adds two 1-bit numbers and produces two
1-bit outputs, a sum and a carry. To add two n-bit numbers, it is tempting to try to use
n half-adders in parallel, one for each position, but this does not work. Consider the
following base-2 addition:
carries 1 1 1 1 0
1 1 0 1 02
+ 1 0 1 1 12(^1 1 0 0 0 12)
For example, the fourth digit of the sum, the third position from the right, is the sum of
a 1 plus a 0, plus 1 carried from the position to the right of it. So, to compute that one
position, one needs a circuit that computes the sum of three 1-digit binary numbers,
the two digits and a carry. It should output the sum (the 1's position of the sum) and a
carry (the 2's position of the sum). Such a circuit is called afull-adder
(a) Draw a full-adder circuit.
(b) Draw a circuit, with one half-adder and three full-adders, for adding two 4-digit
binary numbers.
(c) Draw a circuit that implements the multiplication table (for one-digit numbers).
- (a) The conjunction of n formulas P1, P2, ... , Pn is defined to be the formula
(... ((Pl A P2) A P3) A ...) A Pn. For n = 0, there is a special case: The conjunc-
tion of zero formulas is defined to be T. For n = 1, that conjunction simplifies to
Pi. Let 'p be the conjunction of P1, P2 .... pn. Prove that for any interpretation
I, l('p) = T if and only if I(pi) = T for each i such that 1 < i < n. (Hint: Use
induction.)