ECS 20: Discrete Mathematics for Computer Science Handout M
UC Davis — Phillip Rogaway October 30, 2008
Midterm
Dear students,
Relax. Read each problem. Write down each answer. Neatly. What could be simpler?
The exam has five pages not including this one—23 questions (but many of them are
very short, and indeed the first 10 are true/false). While I may count some questions
more than others, no question will count more than twice another question.
Your Name:
On page you got
1
2
3
4
5
Σ
ECS 20 Handout M: Midterm 1
For the following true/false questions, guess if you can’t figure out the answer: your grade
for these will be a function of the number of correct answers you give. Mark the correct
answer by putting an X through the correct box. No justification is required. Note:
students often do not take True/False questions seriously enough. You must consider
each question carefully if you are to accurately decide its validity.
1. The logical connectives {∧,∨} are logically complete. True False
2. If a Boolean formula is tautological then it is satisfiable. True False
3. If φ is Boolean formula then either φ or ¬φ is tautological. True False
4. Any Boolean formula can be realized (that is, equivalently written) using just NAND
gates. True False
5. If A and B are finite sets then |A ∪B| = |A|+ |B|. True False
6. If A, B, C are sets, x ∈ A⊕B ⊕ C iff x is in exactly one of A, B, and C.
True False
7. An infinite language is one that contains at least one string of infinite length.
True False
8.
⋃
i∈N {1
i} = 1∗ (where the right-hand side is interpreted as a language). (Recall that
N = {0, 1, 2, . . .} is the set of natural numbers and 10 = ε.) True False
9. Let T be the relation on pairs of people defined by saying that x T y iff x is at least as
tall as y. Then T is an equivalence relation. True False
10. In PS #1 you were asked to show that there exist irrational a and b such that ab is
rational. The distributed solution I gave out showed this to be the case for a = b =
√
2.
True False
2 ECS 20 Handout mt: Midterm
For the remaining problems you will be providing short answers. Make sure your writing
is succinct and legible.
11. Convert the following formula into an equivalent one without negations. The logical
connectives your formula may use are {∧,∨}. The relation symbols your formula
may use are {<,≤, , =, 6=,≥, >}. As always, be careful.
¬ (∀c)(∃N)(∀n)((c > 0 ∧N > 0 ∧ n ≥ N) → f(n) ≤ n−c)
12. Write a disjunctive normal form (DNF) formula whose truth table is given
below. Let your formula be the or of four terms where each term is the and of
three variables or their complements:
A B C φ(A, B, C)
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0
13. Using only and, or, and not gates, draw a circuit realizing the functionality of an
xor (exclusive or) gate.
ECS 20 Handout M: Midterm 3
14. Capture the logical content of the following sentence in a Boolean formula: Nobody
likes Mark except his roommates, who actually do like him. You may use any logical
connectives you know. Make your formula as succinct as possible. Use predicate
symbols L(x, y) (person x likes person y), R(x, y) (persons x and y are roommates),
and the constant symbol Mark. The universe of discourse is people.
15. Suppose that A, B, A′, and B′ are sets. Give a simple counter-example to the claim:
A×B = A′ ×B′ =⇒ A = A′ ∧ B = B′.
16. Let L = {x : x ∈ {a, b, c}∗ and x contains at least one a and at least one b}. Write,
in lexicographic order, the first five strings of L. (Recall that the lexicographic
ordering of a language L is: all the length-0 strings in L; then, in alphabetical
order, all the length-1 strings in L; then, in alphabetical order, all the length-2
strings in L; and so on.)
17. Finish this statement of DeMorgan’s law for sets: (A ∩B)c =
18. Write a shortest regular expression for the language L = {an : n is odd}.
4 ECS 20 Handout mt: Midterm
19. Draw a DFA for L = {a1 . . . an : each ai is a bit and ai = 1 for all odd i}. Assume
that the empty string ε is in L. Make your DFA have the minimum number of
states you can.
20. Let P ⊆ A×B and Q ⊆ B×C be a relation. Formally define P ◦Q, the composition
of P and Q.
P ◦Q is the relation P ◦Q ⊆ ×
defined by:
21. For a, b ∈ R define a E b if a− b ∈ Z. What’s the smallest positive number in [π]?
(Here π = 3.14159 · · · is the usual constant that goes by this name.)
ECS 20 Handout M: Midterm 5
22. Let Tn be the minimum number of moves to solve the n-ring tower of Hanoi problem.
In class we showed that, for n ≥ 1,
Tn ≤ 2Tn−1 + 1 (1)
(while T0 = 0). Repeating the proof given in class, establish this equation. Please
do not “solve” the equation (that is, write it in a “closed-form” way); your job is to
justify it. Write your proof in clear, grammatical English.
23. We showed in class that five shuffles is inadequate to mix a deck a 52 cards. In a
clearly written paragraph, recount the line of reasoning for our proof.