CPS102- Homework 2Due on September 29, 2006Questions may continue on the back. Please write clearly. What I cannot read, I will not grade. Typedhomework is preferable. A good compromise is to type the words and write the math by hand. Show allyour work in detail.The Duke Community Standard requires every undergraduate student to sign the statement below uponcompletion of each academic assignment. I am not allowed to accept your assignment unless you sign on theline below, if you intend to return this sheet, or you copy and sign the same statement on your own paper.I have adhered to the Duke Community Standard in completing this assignment.Signature:Important: A fundamental component of this course is about thinking formally and making clear arguments.Inaccurate, incomplete, or poorly phrased arguments will not receive full credit.1. The following axioms∀x (P (x) ∨ Q(x)) , ∃x ¬ Q(x) , ∀x (R(x) → ¬ P (x))entail the following formula φ:∃x ¬R(x) .Prove φ from the given axioms by resolution with refutation. Please take this directive seriously: no credit will be given forproofs of a different style (e.g., giving some intuitive argument, or using truth tables, or using resolution without refutation).Show all your substitutions and resolvents, and state which literals you are resolving away at each step.The following problem is number 24 on page 131 of the book (sixth edition). The one thereafter is a modification ofproblem 40 on the same page.2. Let A, B, and C be sets. Show that(A − B) − C = (A − C) − (B − C) .[Hints: Set difference is defined in the book. To solve this problem, show that each side of the equation is contained in theother (a “mutual inclusion” proof). To prove inclusion of set S in set T means to show that every x that is in S is also in T :∀x (x ∈ S → x ∈ T ) .To “show” means to give a clear, well-supported argument. ]3. The symmetric difference of A and B, denoted by A ⊕ B, is the set containing those elements in either A or B, but notin both A and B. In other words, an element in A ⊕ B is either in A but not in B, or in B but not in A:A ⊕ B = (A ∩ B) ∪ (A ∩ B) .Show that the symmetric difference is associative:A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C .Explain your reasoning carefully. [Hint: Either draw a Venn diagram for each side or go through blind formula manipulation.The second method is more straightforward but very boring and error prone, the first is more interesting. If you choose theCPS102 — Duke — September 21, 2006boring method, you get no credit if you make mistakes in the manipulation. If you use Venn diagrams, make sure that youexplain clearly how you use them, and how your drawings support your conclusion.]4. Let A be the set of prime numbers smaller than 10, and B the set of perfect squares less than 20. [Warning: 1 is notprime, and 0 is a perfect square.] Your answers below should be in the form of exact integers.(a) How many elements are in the power set of the Cartesian product of A and B?(b) How many elements are in the Cartesian product of the power sets of A and B?(c) How many elements are in the power set of the power set of B?5. A Venn diagram for n sets A1, . . . , Anis complete if it has a region of nonzero area for every component, that is, forevery set of the form L1∩ . . . ∩ Lnwhere Liis either Aior its complement, and ‘∩’ is set intersection. For instance, thecomponents for n = 2 are AB, AB, AB, and AB. Here are complete Venn diagrams for two and three sets, respectively:UBAA BCU(a) Make a reasonably large copy of the complete diagram for three sets A, B, C (figure on the right above), and labeleach of its eight components. For instance, the region that is in A and B but not in C is labeled A ∩ B ∩ C. You mayabbreviate this to ABC. Place the label in the interior of each component.(b) How many components does a complete Venn diagram for n sets have? Prove it.(c) Draw a complete Venn diagram for n = 4 sets and label all the components. Make a clean drawing. No credit forunintelligible drawings. This means that you probably need to make a few drafts on separate paper before you draw yourfinal solution. You get five extra-credit points if in your diagram (i) components are represented by connected regions,and (ii) no more than two boundaries cross each other at any point. For instance, the diagram for n = 3 below violatesrule (i) because component ABC is represented by two separate regions. This diagram also violates rule (ii) becausethree boundaries cross at one point.UBACABCABCThree boundariesintersect hereCPS102 — Duke — September 21,
View Full Document
Unlocking...