CS 70 FALL 2006 — DISCUSSION #1D. GARMIRE, L. ORECCHIA & B. RUBINSTEIN1. Administrivia(1) Course Information• The first homework is due September 1stat 4pm in 283 Soda Hall, andis available at http://www-inst.eecs.berkeley.edu/~cs70/fa06• You are encouraged to work on the homework in groups of 3-4, butwrite up your submission on your own. Cite any external sources youuse.(2) Discussion Information• If you have a clash, it is OK to attend a section different to yourenrolled/wait-listed one. Just be sure to show up so that we can ‘as-sign’ you somewhere based on the roles taken in sections in the firstfew weeks.• Section notes like this one will be posted on the course website.• Feel free to contact the GSI’s via e-mail, or the class staff and studentsthrough the newsgroup, if you have a question.• Remember that 5% of your final grade comes from participation!2. Warm-up: Can You Spend Exactly Ten Coins?To help get the problem-solving juices flowing, attempt the following – no specialbackground math is required!Exercise 1. For your summer vacation you decide to visit the exotic land of Exac-tavia, where it is customary to pay shop-keepers the exact amount due with exactlyten coins. The currency of Exactavia consists of 1, 3 and 5 dollar coins. Assumethat you have at least ten of each type of coin.(i) Can you pay $24? If so, provide the coins you’d use; otherwise explain whyit is impossible.(ii) What if you are asked to pay $25?(iii) Can you generalize your procedure to paying amounts a, for 10 ≤ a ≤ 50?Which of these amounts can you pay? 3. Knights and Knaves: Fun with Propositional LogicKnights are always truthful while knaves are consistent liars. With this in mind,consider the following conversation between Alice and Bob.Date: August 30, 2006.The authors gratefully acknowledge Chris Crutchfield and Amir Kamil for the use of theirprevious notes, which form part of the basis for this handout.12 D. GARMIRE, L. ORECCHIA & B. RUBINSTEINAlice: “At least one of us is a knight.”Bob: “At least one of us is a knight.”How might we determine whether Alice is a knight or a knave? As we’re deal-ing with the truth of statements (i.e. that “Alice is a knight” and the same forBob), propositional logic should come to mind! Let’s begin by labeling the twopropositions we’re interested in:P = “Alice is a knight”Q = “Bob is a knight”Exercise 2. Using the propositional machinery discussed in class, determine ex-actly what can be deduced from the above facts/statements.(i) As a first step, write out the four distinct statements in terms of P and Qthat must be true. (hint: what if Alice is/is not a knight, what about Bob?).(ii) P must be either true or false, as must be Q. Also your four logical propo-sitions must be true. Using a truth table determine which truth assignmentsto P and Q are consistent with the truth of your four statements. From thisdeduce what can be said about the truth of P and Q. Using the same steps we can solve many variants of the knights and knavesproblem – this is generalization in problem solving.Exercise 3. Repeat the previous exercise after Alice says “At least one of us is aknight” and Bob says “We’re both of the same (knight/knave) type.”4. De Morgan’s Laws, Quantifiers and NegationAt the end of lecture #1’s notes the section ‘Quantifiers and Negation’ describeshow to push a negation passed a quantifier. In particular the following two lawsare justified intuitively.¬ (∀xP (x)) ≡ ∃x¬P (x)(4.1)¬ (∃xP (x)) ≡ ∀x¬P (x)(4.2)How might these “De Morgan’s Laws” be proven formally? In fact in our lastclass (class #2) we saw that for a universe of size 2 these laws translate to thefollowing binary cases.¬ (P ∧ Q) ≡ ¬P ∨ ¬Q(4.3)¬ (P ∨ Q) ≡ ¬P ∧ ¬Q(4.4)Following the argument given in lecture, we can appeal to common sense toconvince ourselves of the truth of these two equivalences. Say P is the proposition‘Mario is a plumber’ and Q represents the logical statement ‘Luigi wears green’.Consider Rule (4.4). Intuitively ¬ (P ∨ Q) is true if and only if Mario is not aplumber and Luigi is not wearing green. To prove the two (binary) De MorganCS 70 FALL 2006 — DISCUSSION #1 3Laws we can also formally test equivalence using truth tables. Let’s do so forpractice now.Exercise 4. Prove De Morgan’s Laws on two variables.(i) Prove Rule (4.3), by filling out the following table.P Q ¬P ¬Q P ∧ Q ¬ (P ∧ Q) ¬P ∨ ¬QT TT FF TF F(ii) Use this next table to prove Rule (4.4).P Q ¬P ¬Q P ∨ Q ¬ (P ∨ Q) ¬P ∧ ¬QT TT FF TF F Arguing that a universally (existentially) quantified statement is equivalent toa big possibly even infinite conjunction (disjunction), the common-sense argumentleads us to the general De Morgan’s Laws.Exercise 5. How might you ‘formally’ prove the two De Morgan’s Laws for uni-verses of arbitrary finite size?Next week we’ll learn about induction in lectures. One application of inductionis to formally proving the laws on countably in/finite universes. Extensions ofinduction are capable of proving the laws for uncountable universes.5. Quantifier PracticeConsider the false statement “For each x in R, x2≥ x” (consider 0 < x < 1).What is the negation of this statement? Is it “For each x in R, x2< x”? No,because this statement is still false (e.g. consider x > 1). So what is going wronghere?Let P (x) be the proposition “x2≥ x” with x taken from the universe of realnumbers R. Then our original statement is succinctly written as ∀x, P (x). Fromour previous discussion on De Morgan’s Laws and their generalization, we can applyRule (4.1) to get ¬∀x, P (x) ≡ ∃x, ¬P (x) or “There exists a real x for which x2< x.”We can chain together quantifiers in any manner we please: ∀x, ∃y, ∀z, P (x, y, z)and negate it using the same rules discussed above. By applying the rules insequence, we get that¬(∀x, ∃y, ∀z, P (x, y, z))∃x, ¬(∃y, ∀z, P (x, y, z))∃x, ∀y, ¬(∀z, P (x, y, z))∃x, ∀y, ∃z, ¬P (x, y, z)4 D. GARMIRE, L. ORECCHIA & B. RUBINSTEINThe ¬ “bubbles down”, flipping quantifiers as it goes. The following problemcomes from Question 14 in the Mathematics Subject GRE Sample Test:Exercise 6. Let R be the set of real numbers and let f and g be functions from Rto R. The negation of the statement“For each s in R, there exists an r in R such that if f(r) > 0, then g(s) > 0.”is which of
View Full Document
Unlocking...