6.042J/18.062J 6. Size of Sets, Mapping Lemma

1 lec 3W.1 Albert R Meyer, February 17, 2010 Predicate Logic Quantifiers ∀,∃Mathematics for Computer Science MIT 6.042J/18.062J lec 3W.2 Albert R Meyer, February 17, 2010 Predicates Propositions with variables Example: [x + 2 = y] P(x,y) ::= lec 3W.3 Albert R Meyer, February 17, 2010 Predicates x = 1 and y = 3: x = 1 and y = 4: P(1,4) is false NOT(P(1,4)) is true [x + 2 = y] P(x,y) ::= P(1,3) is true lec 3W.4 Albert R Meyer, February 17, 2010 Quantifiers For ALL x There EXISTS some y ∀x ∃y lec 3W.5 Albert R Meyer, February 17, 2010 ∀ is like AND ∀s. P(s) Let s range over 6.042 staff P(s) ::= [s is Pumped about 6.042] same as P(Stav) AND P(Rich) AND P(Megumi) AND…AND P(Oscar) lec 3W.6 Albert R Meyer, February 17, 2010 ∃ is like OR ∃t. B(t) Let t range over 6.042 staff B(t) ::= [t took 6.042 Before] same as B(Stav) OR B(Rich) OR B(Megumi) OR…OR B(Oscar) 2 lec 3W.7 Albert R Meyer, February 17, 2010 Q(y) ::= ∃x. x < y Q(3) is T ([x<3] is T for x=1) Q(1) is T ([x<1] is T for x=0) Q(0) is F ([x<0] is not T for any x in N) Existential Quantifier Let x, y range over N lec 3W.8 Albert R Meyer, February 17, 2010 R(y) ::= ∀x. x < y R(1) is F ([x<1] is F for x=5) R(8) is F ([x<8] is F for x=12) R(10100) is F ([x<10100] is F for x=10100) Universal Quantifier x, y range over N lec 3W.9 Albert R Meyer, February 17, 2010 For every virus, I have a defense: against MYDOOM, use Defender against ILOVEYOU, use Norton against BABLAS, use Zonealarm… ∀∃ is expensive! virus attack, I: ∀∃ lec 3W.10 Albert R Meyer, February 17, 2010 I have one defense good against every attack. Example: d is MITviruscan, protects against all viruses virus attack, II:∃∀ That’s what we want! lec 3W.15 Albert R Meyer, February 17, 2010 x, y range over Domain of Discourse ints < 0 F reals < 0 T T Domain G is: N G ::= ∀x∃y. x < y Alternating Quantifiers lec 3W.16 Albert R Meyer, February 17, 2010 F F Reverse the Quantifiers Z- ::= ∃y∀x. x < y Domain N H is: ≤ T F -3 lec 3W.38 Albert R Meyer, February 17, 2010 Team Problems Problems 1 & 2 MIT OpenCourseWare http://ocw.mit.edu 6.042J /18.062J Mathematics for Computer Science Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.