ECS 20 — Lecture 5 — Fall 2013 —10 Oct 2013
Phil Rogaway
Today: o First Order Logic o Sets
Adding quantifiers – First order logic All apples are bad
(x) (A(x) B(x)) // universe of discourse? Some apples are bad
(x) (A(x) B(x)) // universe of discourse? “BILLY has beat up every boy at the elementary school”
(x) ((Student(x) Boy(x) (xBILLY) HasBeatUp (BILLY, x)) // universe of discourse?
Universe of discourse = what quantifiers range over. Always important to know the universe of discourse; it’s implicit, or explicit, in any discussion of logical formulas involving quantifiers.
All lions are fierce (x) (L(x) F(x))
Some lions do not drink coffee ( x) (L(x) C(x))
Some fierce creatures do not drink coffee (x) (F(x) C(x))
“Nobody likes a sore loser”
universe of discourse = human beings (is this really unambiguous?) L(x,y) – predicate – true iff person x likes y (is this really unambiguous?) S(x) – person x is a sore loser
(x) (S(x) (y) L(y, x))
(Apparently, a sore loser doesn’t like even himself)
If anyone in the dorm has a friend who has the measles, then EVERYONE in the dorm will have to be quarantined.
Universe of discourse – people
D(x) – person x lives in some (unspecified but understood) dorm Q(x) – person x must be quarantined
F(x,y) – person x is friends with person y
M(x) – person x has the measles (oh no!)
(x)(D(x) (y)(F(x,y) M(y))) (x)(D(x) Q(x)) 1
3. T/F: universe of discourse:
Natural numbers {1,2,3, …}
There are always bigger numbers
There is a number that’s bigger than everything There is a number smaller than everything There’s always a smaller number
(x)(y) (x
(x)(y) (y>x z (z2 + 5z = y)) (x) (y) (y>x z (z2 + 5z = y)) (x) (y) (y>x z (z2 + 5z = y))
(A B) (A B) (A B)
(x) (y) (y>x z (z2 + 5z = y))m (x) (y) (y>x z (z2 + 5z = y)) (x) (y) (y>x z(z2 + 5z y))
Example: negligible functions
A function f: N R is negligible if it vanishes faster than the inverse of any polynomial:
(c>0) (N) (n N) f (n) nc shorthand for 3
(c) (N) (n) ( c>0 nN f (n) nc ) “eventually, you’re less than n-c for ANY c. Negate it: “there is a c s.t., infinitely often, you’re bigger than n-c”
Even grad students and researchers get confused about this!
= = = =
(c)(N)(n) ( c>0nNf(n)nc) (c)(N)(n) ( c>0nNf(n)nc) (c)(N)(n)( c>0nNf(n)nc) (c)(N)(n)( c>0nNf(n)nc) (c)(N)(n)( c>0nN f(n)nc)
Infinitely often, you are bigger than nc
Set Theory
predicate symbols: 2-ary function symbol:
Note “syntactic sugar” — write a A instead of (a,A). But that doesn’t change that is a 2-ary predicate.
“For any pair of sets, x and y, there a set x y that contains all of the elements of x and y”
(x)(y)(z) (u) (uz (ux) (u y)) Seems very spare, just \in.
What are other operators on sets, and how would we define them? A B: (another 2-ary predicate)
aA = (aA) AB = (xAxB) AB = (xBxA)
4