Homework 2 Logical Equivalences and Boolean Algebra

1. Logical Equivalences (20 points)
Prove the following assertions using equivalances. You can use commutativity and associativity an
arbitrary number of times in a single line of the proof.
(a) [8 Points] p ! (q ! r) ≡ q ! (p ! r).
(b) [12 Points] ((p ! q) ^ (r ! :q)) ! (r ! :p) ≡ T:
2. Boolean Algebra (10 points)
Prove that X0 + ((X + Y ) • X)0 = X0 using the axioms and theorems of boolean algebra.
3. X · Y (20 points)
In this question, you will construct a circuit that takes a pair of two-bit integers (x1x0)2 and (y1y0)2
and computes the four output bits for their integer product.
For example, if (x1x0)2 = (10)2 and (y1y0)2 = (11)2 then we’re doing the following computation:
1 0
× 1 1
1 0
+ 1 0 0
0 1 1 0
(a) [8 Points] Give sum-of-products forms for the two output bits of the product, (a1a0)2, of (x1x0)2
and (y0)2. Do the same for (x1x0)2 and (y1)2 yielding (b1b0)2. These are the bits produced as
part of applying the usual elementary school method for multiplying numbers.
Drawn out, this looks like:
x1 x0
× y1 y0
a1 a0
b1 b0 0
1(b) [12 Points] Use the minimized sum-of-products forms for one-bit adders given in class, together
with the results of the above two products, to produce sum-of-products forms for the output
bits z3; z2; z1; z0. Some of the inputs you give to the one-bit adders may be constants. Use
Boolean algebra to minimize the resulting sum-of-products form as a sum-of-products using only
x1; x0; y1; y0.
Drawn out, this looks like:
a1 a0
+ b1 b0 0
z3 z2 z1 z0
4. Counting Courses with Combinational Logic (20 points)
In lecture 4, we considered a combinational logic example about days of class.
(a) [5 Points] Write c1 in the product of sum form.
(b) [6 Points] Simplify the sum of product forms of c0; c2 using boolean algebra axioms and theorems.
Make sure to cite which axioms and theorems you are using when simplifying.
(c) [9 Points] Simplify the sum of product forms of c1 using boolean algebra axioms and theorems.
5. Hats, 311, and Bunnies (20 points)
It is often useful to assert that something exists and is unique. For instance,
There exists a unique course at UW with the course number CSE 311.
(a) [4 Points] Let the domain of discourse be all vases. Let B be a constant representing “the painted
vase in Shayan’s office.” Translate “If there is a vase that is painted, then it is the painted vase in
Shayan’s office.” into first-order logic. Don’t forget to define predicates.
Hint: Remember that a “constant” is a particular object in the domain. For example, “0” and “1”
are constants in the domain of natural numbers.
(b) [4 Points] Let the domain of discourse be all university courses. Now, use an idea similar to part
(a) to translate the sentence about the CSE 311 course number into first-order logic. Don’t forget
to define predicates.
For the remaining parts, we define the following predicates:
• Let R(x) be “x is a rabbit.”
• Let H(x) be “x hops.”
2For these parts, let the domain be mammals. Translate each of the following into English.
(c) [3 Points] 9x(R(x) ^ H(x))
(d) [3 Points] 8x(R(x) ! H(x))
(e) [3 Points] 8x(R(x) ^ H(x))
(f) [3 Points] 9x(R(x) ! H(x))
6. Domain of discourse (10 points)
(a) [5 Points] Give examples of predicates P and Q and a domain of discourse so that the two
statements
8x(P (x) _ Q(x)) and (8xP (x)) _ (8xQ(x))
are not equivalent.
(b) [5 Points] Give an example where they are equivalent.
(c) [0 Points]Mini extra credit: Say that a logical connective p ⊗ q is non-trivial if it sometimes
evaluates to false and sometimes evaluates to true. Is there any such connective p ⊗ q such that
9x(P (x) ⊗ Q(x)) and 9xP (x) ⊗ 9xQ(x) are logically equivalent for every domain and choice of
predicates? Explain.
7. Extra credit: Comparison circuit (-NoValue- points)
In this problem, you will design a circuit with a minimal number of gates that takes a pair of four-bit
integers (x3x2x1x0)2 and (y3y2y1y0)2 and returns a single bit indicating whether x3x2x1x0 < y3y2y1y0.
See the following table for some examples.
x3x2x1x0 y3y2y1y0 x3x2x1x0 < y3y2y1y0
0101 1011 1
1100 0111 0
1101 1101 0
Design such a circuit using at most 10 AND, OR, and XOR gates. You can use an arbitrary number of
NOT gates, and a single gate can have multiple inputs. (Extra credit points start at 10 gates, but if you
can use fewer, you will get even more points.)
3