PS2.ProblemsECS 20: Discrete Mathematics for Computer Science
UC Davis September 28, 2021
Problem Set 2 – Due Tuesday, October 5, at 5pm
1. How many reasonable paths are there from the Start to the Finish? By a “reasonable path” I mean
that you walk from one vertex (darkened circle) to the next, with the (Euclidean) distance to the
finish decreasing with each edge (line segment) that you take.
�����
����
2. What is a necessary and sufficient number of riffle shuffles to transform the sequence of cards
π0 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) to the sequence of cards π = (3, 6, 1, 0, 8, 2, 4, 5, 9, 7).
3. Consider the Boolean formula T (a, b, c) that returns True when exactly two of its three inputs are
true.
(a) Express the formula T as the disjunctions of terms, each term being the conjunction of variables
or their complements. A formula of this sort is said to be in disjunctive normal form, or DNF.
(b) Express the formula T as the conjunction of clauses, each clause being the disjunction of
variables or their complements. A formula of this sort is said to be in conjunctive normal form, or
CNF.
(c) We argued in class that every Boolean formula can written in DNF. Can every Boolean formula
be written in CNF, too? Why or why not.
(d) Exhibit a Boolean formula B(x1, . . . , xn) whose shortest DNF representation would seem to
be much longer than the length of B(x1, . . . , xn). Explain why you suspect your formula has this
property. You needn’t prove it.
4. Three students, A, B, and C, are suspected of cheating on an examination. When they are ques-
tioned by OSSJA, they assert:
A: “B copied and C is innocent”
B: “If A is guilty then so is C”
C: “I am innocent”
Now answer the following questions:
(a) If A spoke the truth and B lied, who is innocent and who copied?
(b) If everyone is innocent, who told the truth and who lied?
(c) If C lied and B told the truth, who is guilty?
5. Prove that {→,¬} is logically complete.
6. Consider the parity function: Fn(x1, . . . , xn) = ⊕ni=1 xi where each xi ∈ B. Prove that, for every
n ≥ 2, there is no way to compute Fn using only AND and OR gates, and the constants 0 and 1.