CS 202, Spring 2005 Midterm 1: 24 Feb 2005 Page 1/8 Name: ______________________________________ E-mail ID: [email protected] Pledge: _______________________________________________________________________ _____________________________________________________________________________ _____________________________________________________________________________ Signature: _____________________________________________________________________ There are 75 minutes for this exam and 100 points on the test; don’t spend too long on any one question! The 12 short answer questions require only a sentence or two for full credit; the three long answer questions have their own page, and obviously require more. The questions are organized by topic, so the long answer questions are scattered throughout the exam (questions 5, 14, and 15). The long answer questions are worth about half of the test score; the short answer questions are all worth 4 points each, and constitute the other half. The reference sheet is on page 2. All work must be on these exam pages. Good luck! Part I: Logic _____ / 33 Part II: Structures _____ / 16 Part III: Proofs _____ / 51 Total _____ / 100CS 202, Spring 2005 Midterm 1: 24 Feb 2005 Page 2/8 CS 202 Exam 1 Reference Sheet Set and logical identities Sets (Rosen, p. 89) Name Boolean logic (Rosen, p. 24) AUAAA==∅IU Identity laws pppp≡∨≡∧FT ∅=∅=IUAUUA Domination laws FFTT≡∧≡∨pp AAAAAA==IU Idempotent laws pppppp≡∧≡∨ ()AA = Complemen-tation law pp≡¬¬ )( ABBAABBAIIUU== Commutative laws pqqppqqp∧≡∧∨≡∨ CBACBACBACBAIIIIUUUU)()()()(== Associative laws )()()()(rqprqprqprqp∧∧≡∧∧∨∨≡∨∨ )()()()()()(CABACBACABACBAUIUIUIUIUI== Distributive laws )()()()()()(rpqprqprpqprqp∧∨∧≡∨∧∨∧∨≡∧∨ BABABABAUIIU== DeMorgan’s laws qpqpqpqp¬∧¬≡∨¬¬∨¬≡∧¬)()( ABAAABAA==)()(UIIU Absorption laws pqpppqpp≡∨∧≡∧∨)()( ∅==AAUAAIU Complement laws FT=¬∧=¬∨pppp Rules of inference (Rosen, p. 58) Rule of Inference Tautology Name qpp∨∴ )(qpp ∨→ Addition pqp∴∧ pqp →∧ )( Simplifi-cation qpqp∧∴ ())()()( qpqp ∧→∧ Conjunction qqpp∴→ []qqpp →→∧ )( Modus ponens pqpq¬∴→¬ []pqpq ¬→→∧¬ )( Modus tollens rprqqp→∴→→ [])()()( rprqqp →→→∧→ Hypothetical syllogism qpqp∴¬∨ []qpqp →¬∧∨ )( Disjunctive syllogism rqrpqp∨∴∨¬∨ [])()()( rqrpqp ∨→∨¬∧∨ ResolutionCS 202, Spring 2005 Midterm 1: 24 Feb 2005 Page 3/8 Part I: Logic Question 1 (4 points): What is the converse of p→q? Question 2 (4 points): Given the Boolean proposition p↔q, write an equivalent compound proposition using only the operators ¬, ∧, and ∨. Question 3 (4 points): State the negation of the following quantified statement: ())()( yQxPyx ¬∧∃∀ Question 4 (4 points): What are the two ways to convert a propositional function into a proposition?CS 202, Spring 2005 Midterm 1: 24 Feb 2005 Page 4/8 Question 5 (17 points): Prove that )()())(( qpqpqpp ∧≡∨¬∧∧∧ using logical equivalences. You must clearly label each step of the logical equivalence.CS 202, Spring 2005 Midterm 1: 24 Feb 2005 Page 5/8 Part II: Structures (sets and functions) Question 6 (4 points): What is the difference between a subset and a proper subset? Question 7 (4 points): Why must a function f be 1-to-1 and onto if the function f is invertible (i.e. you can find an inverse function of f)? Question 8 (4 points): What is the cardinality of a power set of a set of n elements? Question 9 (4 points): Let 25)( += xxf and 32)( += xxg . What is ))(( xgf o ?CS 202, Spring 2005 Midterm 1: 24 Feb 2005 Page 6/8 Part III: Proofs Question 10 (4 points): What two properties must be shown for a uniqueness proof? Question 11 (4 points): Write an existential generalization of the quantified statement )(xxP∃ . If you introduce new variables, etc., clearly describe what they represent. Question 12 (4 points): What is the difference between a vacuous proof and a trivial proof? Question 13 (4 points): What movie did Professor Bloomfield show a preview of during class?CS 202, Spring 2005 Midterm 1: 24 Feb 2005 Page 7/8 Question 14 (15 points): For this question, you will have to prove that if m is an even integer, then m+7 is an odd integer. You need to prove it two different ways: by direct proof, indirect proof, or proof by contradiction. Each proof method is worth the same amount. Proof method 1 (circle one): Direct proof Indirect proof Proof by contradiction Proof method 2 (circle one): Direct proof Indirect proof Proof by contradictionCS 202, Spring 2005 Midterm 1: 24 Feb 2005 Page 8/8 Question 15 (20 points): Consider the following statements. 1. If Dominic goes to the racetrack, then Helen will be mad. 2. If Ralph plays cards all night, then Carmela will be mad. 3. If either Helen or Carmela gets mad, then Veronica (their attorney) will be notified. 4. Veronica has not heard from either of these two clients. From these, can we conclude the following? • Dominic didn’t make it to the racetrack and Ralph didn’t play cards all night. Write each of these statements in symbolic form. Clearly label what your Boolean variables represent! Then establish the validity of the conclusion. You must clearly label which rule of inference is used for each