ECS 20: Discrete Mathematics for Computer Science PS2.Problems UC Davis — Prof. 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.
A%9A
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.