ECS 20: Discrete Mathematics for Computer Science Handout M
UC Davis —
Dear students,
October 30, 2008
Midterm
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 1
2
3
4
5
Σ
you got
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
2. If a Boolean formula is tautological then it is satisfiable. True
3. If φ is Boolean formula then either φ or ¬φ is tautological. True
4. Any Boolean formula can be realized (that is, equivalently written) using just NAND
False False False
gates. True 5. If A and B are finite sets then |A ∪ B| = |A| + |B|. True
False 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 {1i} = 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 = True False
√
2.
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 {<, ≤, , =, ̸=, ≥, >}. 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) 000 0 001 1 010 1 011 0 100 1 101 0 110 1 111 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 19.
ECS 20 Handout mt: Midterm
DrawaDFAforL={a1…an : eachai isabitandai =1foralloddi}. 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:
Fora,b∈RdefineaEbifa−b∈Z. What’sthesmallestpositivenumberin[π]? (Here π = 3.14159 · · · is the usual constant that goes by this name.)
21.
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.