Logic with quantifiers

1 .Logic with quantifiers aka First-Order Logic Predicate Logic Quantificational Logic 2/6/12 1 Harry Lewis/CS20/CSCI E-120/with thanks to Albert R. Meyer

2 .Predicates A predicate is a proposition with variables For example: P(x,y ) := “ x+y =0” (For today, universe is Z = all integers) P(-4,3) is 2/6/12 2 Harry Lewis/CS20/CSCI E-120/with thanks to Albert R. Meyer

3 .Predicates A predicate is a proposition with variables For example: P(x,y ) := “ x+y =0” P(-4,3) is False P(5,-5) is 2/6/12 3 Harry Lewis/CS20/CSCI E-120/with thanks to Albert R. Meyer

4 .Predicates A predicate is a proposition with variables For example: P(x,y ) := “ x+y =0” P(-4,3) is False P(5,-5) is True P(6,-6)⋀¬P(1,2) is 2/6/12 4 Harry Lewis/CS20/CSCI E-120/with thanks to Albert R. Meyer

5 .Predicates A predicate is a proposition with variables For example: P(x,y ) := “ x+y =0” P(-4,3) is False P(5,-5) is True P(6,-6)⋀¬P(1,2) is True 2/6/12 5 Harry Lewis/CS20/CSCI E-120/with thanks to Albert R. Meyer

6 .Quantifiers ∀ x Q(x ) := “for all x , Q(x )” That is, Q(x ) holds for each and every value of x ∃ x Q (x ) := “for some x , Q(x )” That is, Q(x ) holds for at least one value of x Let Q(x ) := “x-7=0” ∀ x Q(x ) is false but ∃ x Q (x ) is true Let R(x,y ) := “x≥0 ⋀ x+y =0” Then ∀ y∃x ( R(x,y ) ⋁ R(y,x )) is …? ∀ y ∃ x ( (x≥0 ⋀ x+y =0) ⋁ (y≥0 ⋀ y+x =0)): True! 2/6/12 6 Harry Lewis/CS20/CSCI E-120/with thanks to Albert R. Meyer

7 .Quantifiers ∀ is AND-like and ∃ is OR-like If the universe is {Alice, Bob, Carol} then ∀ x Q (x ) is the same as Q(Alice ) ⋀ Q(Bob ) ⋀ Q(Carol ) ∃ x Q (x ) is the same as Q(Alice ) ⋁ Q(Bob ) ⋁ Q(Carol ) In general the universe is infinite … 2/6/12 7 Harry Lewis/CS20/CSCI E-120/with thanks to Albert R. Meyer

8 .Rhetoric and Quantifiers Let Loves(x,y ) := “ x loves y ” “Everybody loves Oprah”: ∀ x Loves (x , Oprah) What does “Everybody loves somebody” mean? ∀ x∃y Loves (x,y )? ∃ y∀x Loves (x,y )? “All that glitters is not gold” ∀ x ( Glitters(x ) ⇒ ￢Gold(x )) ? ￢∀x ( Glitters(x ) ⇒ Gold(x )) ? 2/6/12 8 Harry Lewis/CS20/CSCI E-120/with thanks to Albert R. Meyer

9 .Negation and Quantifiers ￢∀x P (x ) ≡ ∃ x ￢ P(x ) ￢∃x P (x ) ≡ ∀ x ￢ P(x ) So negation signs can be pushed in to the predicates but the quantifiers flip ￢∀x ( Glitters(x ) ⇒ Gold(x )) ⤳ ∃ x ￢(Glitters(x ) ⇒ Gold(x )) ⤳ ∃ x ￢(￢Glitters(x ) ∨ Gold(x )) rewriting “⇒” ⤳ ∃ x ( Glitters(x ) ⋀ ￢Gold(x )) by DeMorgan and double negation “There is something that glitters and is not gold” 2/6/12 9 Harry Lewis/CS20/CSCI E-120/with thanks to Albert R. Meyer

10 .Renaming Variables ∃ x ( P(x ) ⋀ Q(x )) implies ∃ x P (x ) ⋀ ∃ x Q (x ) But not vice versa! P(x ) := “ x won South Carolina” Q(x ) := “ x won Florida” ∃ x P (x ) ⋀ ∃ x Q (x ) (“somebody won SC and somebody won FL”) but ￢∃x ( P(x ) ⋀ Q(x )) Clearer but not different to write ∃ x P (x ) ⋀ ∃ y Q (y ) 2/6/12 Harry Lewis/CS20/CSCI E-120/with thanks to Albert R. Meyer 10

11 .Moving Quantifiers By renaming variables you can move quantifiers outward (∃ x)P(x ) ⋀ (∃ x)Q(x ) is equivalent to (∃ x)P(x ) ⋀ (∃ y)Q(y ) which is equivalent to (∃ x)(∃y ) ( P(x ) ⋀ Q(y )) w hich is very different from (∃ x)(P(x ) ⋀ Q(x )) 2/6/12 Harry Lewis/CS20/CSCI E-120/with thanks to Albert R. Meyer 11

12 .Models A model is an interpretation of the predicates in which the statement is true (∃ x)P(x ) ⋀ (∃ x ) Q(x ) ⋀ ¬(∃ x)(P(x ) ⋀ Q(x )) Is there a model? Yes – P(x ) := “ x is even” and Q(x ) := “ x is odd” 2/6/12 12 Harry Lewis/CS20/CSCI E-120/with thanks to Albert R. Meyer

13 .Models A formula is satisfiable iff it has a model A formula is valid if its negation is unsatisfiable , that is, it is true under any interpretation of the predicates (∃ x)(P(x ) ⋀ Q(x )) ⇒ ((∃ x)P(x ) ⋀ (∃ x)Q(x )) 2/6/12 13 Harry Lewis/CS20/CSCI E-120/with thanks to Albert R. Meyer