CS 202, Spring 2007 Midterm 1: 20 Feb 2007 Page 1/8 1 Name: ______________________________________ E-mail ID: [email protected] Pledge: _______________________________________________________________________ _____________________________________________________________________________ _____________________________________________________________________________ Signature: _____________________________________________________________________ This test is closed book, closed notes, and closed neighbor. There are 50 minutes for this exam and 100 points on the test; don’t spend too long on any one question! The 14 short answer questions require only a sentence or two for full credit (some can receive full credit with just a single word); the three long answer questions have their own page, and obviously require more. The reference sheet is on page 2. All work must be on these exam pages. Good luck! Page 3 (short answer) _____ / 25 Page 4 (short answer) _____ / 25 Page 5 (short answer) _____ / 20 Page 6 (long answer) _____ / 10 Page 7 (long answer) _____ / 10 Page 8 (long answer) _____ / 10 Total _____ / 100CS 202, Spring 2007 Midterm 1: 20 Feb 2007 Page 2/8 2 CS 202 Exam 1 Reference Sheet Set and logical identities Sets (Epp, page 272) Name Boolean logic (Epp page 14) AUAAA==∅∩∪ Identity laws pppp≡∨≡∧FT ∅=∅=∩∪AUUA Domination laws FFTT≡∧≡∨pp AAAAAA==∩∪ Idempotent laws pppppp≡∧≡∨ ()AA = Complemen-tation law pp≡¬¬)( ABBAABBA∩∩∪∪== Commutative laws pqqppqqp∧≡∧∨≡∨ CBACBACBACBA∩∩∩∩∪∪∪∪)()()()(== Associative laws )()()()(rqprqprqprqp∧∧≡∧∧∨∨≡∨∨ )()()()()()(CABACBACABACBA∪∩∪∩∪∩∪∩∪∩== Distributive laws )()()()()()(rpqprqprpqprqp∧∨∧≡∨∧∨∧∨≡∧∨ BABABABA∪∩∩∪== DeMorgan’s laws qpqpqpqp¬∧¬≡∨¬¬∨¬≡∧¬)()( ABAAABAA==)()(∪∩∩∪ Absorption laws pqpppqpp≡∨∧≡∧∨)()( ∅==AAUAA∩∪ Complement laws FT=¬∧=¬∨pppp Rules of inference (Epp, p. 40) Rule of Inference Tautology Name qpp∨∴ )( qpp∨→ Generali-zation pqp∴∧ pqp→∧)( Speciali-zation qpqp∧∴ ())()()( qpqp ∧→∧ Conjunction qqpp∴→ []qqpp →→∧ )( Modus ponens pqpq¬∴→¬ []pqpq ¬→→∧¬ )( Modus tollens rprqqp→∴→→ [])()()( rprqqp →→→∧→ Transitivity qpqp∴¬∨ []qpqp →¬∧∨ )( Elimination rqrpqp∨∴∨¬∨ [])()()( rqrpqp ∨→∨¬∧∨ ResolutionCS 202, Spring 2007 Midterm 1: 20 Feb 2007 Page 3/8 3 Part I: Short answer (5 points each) Each of these questions is answerable in 10 words or less. Do not go over about 20 words!!!! 1. How are logic gates implemented in hardware, such as in a computer? 2. What is a trivial proof and a vacuous proof? If you mix them up, you’ll still get credit on this problem 3. Give two applications of Prolog, the programming language that uses predicate logic. Solving sudoku doesn’t count. 4. What is the halting problem? 5. Why was the halting problem’s proof so important when it came out (and still so today)? ___ / 25CS 202, Spring 2007 Midterm 1: 20 Feb 2007 Page 4/8 4 6. Explain modus tollens in English. 7. Why does this statement not show what is intended? How should it be written? ∃x student(x) → redhair(x) (it’s attempting to say that there is a student who has red hair). Let the domain of x be all people. 8. What is the difference between a constructive existence proof and a non-constructive existence proof? 9. List a real-world application of the Fibonacci sequence. 10. What is the difference between countably infinite and uncountably infinite? Give an example of each. ___ / 25CS 202, Spring 2007 Midterm 1: 20 Feb 2007 Page 5/8 5 11. What does Professor Bloomfield think of photo printers? 12. What are the two ways to turn a propositional function into a proposition? 13. Were you at the review session? You’ll get full credit for this, regardless of your answer, as long as you answer it honestly (this is for our curiosity – and because the question that was here had to be removed). 14. What is an indirect proof? You can explain this one symbolically, if you would prefer. ___ / 20CS 202, Spring 2007 Midterm 1: 20 Feb 2007 Page 6/8 6 Part II: Long answer (10 points each) These questions have a lot of space to allow you to work through them – you don’t need to fill all the space, as long as you answer it correctly. 15. Draw the circuit for a half-adder. You are only allowed to use OR, AND, and NOT gates. Recall that a half-adder will have two results: the carry out is the AND of the inputs, and the sum is the XOR of the inputs. ___ / 10CS 202, Spring 2007 Midterm 1: 20 Feb 2007 Page 7/8 7 16. Prove, by mathematical induction, that 2)1(1−=∑=nnini. If it’s easier, you can prove an alternative form of the same thing: 2)1(21−=+++nnn⋯ . You must clearly label your inductive hypothesis! ___ / 10CS 202, Spring 2007 Midterm 1: 20 Feb 2007 Page 8/8 8 17. Prove, through Boolean logical equivalences, that ( )p q p q¬ ⊕ ≡ ↔. Note that the logical equivalences are listed on page 2 of this exam. ___ /