CSCI 2011: Predicate Logic - University of Minnesota

1 CSCI 2011: Predicate LogicChris KauffmanLast Updated:Wed Jun 20 23:12:43 CDT 20181 LogisticsReading: Rosen Now: Ch - Next: Ch - A01 due tonight A02 posted tomorrow, due next TueGoals Finish up Propositional Logic Predicate Logic (First-order Logic )2 What one can t do in Propositional Logic Propositional Logic is simple and neat but has major limits Example: The following ideas cannot be expressed andmanipulated in propositional integers that can be written 2 n for some integer n arecalled can be written as 2 is therefore Even. Point of trouble: (1) is a general statement while (2) is a specific case of (1) which allows (3) as a conclusion Propositions in their current form have no notion of general or specific So we need a bigger, badder, logic3 First Order Logic Source: 800poundproductions The old Logic could blow up one planet at a time; that failed.

2 The First Order blows up whole sets of planets at a sgottawork better, right?4 Predicate LogicAddsthe following to Propositional LogicPredicates / Propositional FunctionsRather than propositions which are true/false, usePredicates, Propositional Functions which are true / falseLogicNotation Defined to be is positive. true but rigid: 2alwayspositivePredicateP(x)xis positive. Don t know yet, need xPredicateP(2)2 is positive. TruePredicateP(-7)-7 is positive. FalseQuantifiersNew notation that makes a statement about All objects in a set orthe Existence of objects in a set. Used to introduce variables 8xP(x):For Allx,xis positive (Everyxis positive) 9xE(x):There Existsxsuch thatxis is always over somedomainsuch as integers5 Aside: Functions in First-Order Logic Proper 1st order Logic includes functions on objects such as +(x,y):x+y(arithmetic sum) f(s):size of set s Allows statements about functional relationships betweenobjects such as8x9y(x=y+1)For all x, there exists a y such x equals y+1.

3 Not coveredin our text or class: we are just dipping our toesin the water of first order Logic Would be covered in deep dive Mathematical Logic coursesuch as MATH 5165/5166 Higher-order Logic allows quantifiers over functions which getseven more crazy6 predicates Asserts true / false about a specific object DefineE(x):x is even(don t knowxyet) E(2): true,E(3): false,E(10100101): false E(apple):wait, what? predicates usually have an intendeddomain, which should behonored, the kind of object expected Used in combination with Logical ConnectivesSymbolsEnglishTruthinessE(2)^ E(4)2 is even AND 4 is eventrueE(2)^E(7)2 is even AND 7 is evenfalse:(E(9)_E(7))NOT the case that 7 OR 9 is even trueE(x)!

4 E(y)IF x is even THEN y is evenunknown7 Exercise:Use some predicates DefineE(x):x is even(don t knowxyet) DefineS(x,y): the sum of x and y is 5 Fill in the blanksin the table below Truthiness can be: True / False / UnknownSymbolsEnglishTruthinessE(2)!E(4) S(2,4)The sum of 4 and 1 is 5 OR 3 is evenx is even:E(5)The sum of x and 1 is 5 OR 7 is NOT evenIF the sum of x an y is 5 THEN the sumof y and z is NOT 58 Answers:Use some predicates DefineE(x):x is even(don t knowxyet) DefineS(x,y): the sum of x and y is 5 Fill in the blanksin the table below Truthiness can be: True / False / UnknownSymbolsEnglishTruthinessE(2)!E(4) IF 2 is even THEN 4 is eventrueS(2,4)The sum of 2 and 4 is 5falseS(4,1)_E(3)The sum of 4 and 1 is 5 OR 3 is eventrueE(x)x is evenunknown:E(5)5 is NOT eventrueS(x,1)_:E(7)The sum of x and 1 is 5 OR 7 is NOT even trueS(x,y)!

5 :S(y,z)IF the sum of x an y is 5 THEN the sum unknownof y and z is NOT 59 Quantifiers and Variables Quantifiers allow statements about all objects in a particularuniverse(mathematical set) Introduce avariableto represent object instances as in8x(some statements about x) Variables without quantifiers are unbound and consideredsyntactically incorrect Quantifiers have very high operator precedence and mayrequire parentheses:8xA(x)_B(x)bad syntax, reads:(8xA(x))_B(x)8x(A(x)_B(x))kosherEx ample DefineC(x): x is a comedian,F(x): x is funny Assume quantifying over the universe of people 8x(C(x)!F(x)):FOR ALL people, IF person x is a comedian, THEN person xis :To and From English in Predicate Logic 8x: universal quantifier, For 9x: existential quantifier, There DefineC(x): x is a comedian,F(x): x is funny Assume quantifying over the universe of peopleSymbols to English 8x(C(x)^F(x)) 9x(C(x)!)

6 F(X))English to Symbols Among people, there existsa person who is a comedianand is funny. For all people, if a person isnot funny, that person is nota :To and From English in Predicate Logic 8x: universal quantifier, For 9x: existential quantifier, There DefineC(x): x is a comedian,F(x): x is funny Assume quantifying over the universe of peopleSymbols to English 8x(C(x)^F(x)) All people are comediansand are funny. 9x(C(x)!F(x)) There exists a personthat, if that person is acomedian, they are to Symbols Among people, there existsa person who is a comedianand is funny. 9x(C(x)^F(x)) For all people, if a person isnot funny, that person is nota comedian.

7 8x(:F(x)!:C(x))12 Logical Equivalence in Predicate Logic In Propositional Logic , two statements equivalent ( ) if theyhad the same truth values for any truth assignment; couldconstruct a table of these Predicate Logic is similar: two statements are equivalent ifthey have the same truth values but must account for AnyPredicate definition:P(x)might bex is oddorx is > 0 Anyuniverse/set over quantifiers including a universe ofinfinite objects Result:can t use truth tables anymore Need a formalproofof equivalence13 Proof that8x(P(x)^Q(x)) (8xP(x))^(8xQ(x)) Makes intuitive sense but need a more formal description toqualify as a proof RecallA Bis identical toA$Bbeing a tautology ShowingA$B (A!)

8 B)^(B!A)gets us thereA:8x(P(x)^Q(x))B:(8xP(x))^(8xQ(x))A !BAssumeAtrue:8x(P(x)^Q(x))(Implication: don t care if it s false) That means for any specific valuev, bothP(v)andQ(v)are true. SinceP(v)is true for all elements,have8xP(x) SinceQ(v)is true for allelements, have8xQ(x) Then have desired resultB:(8xP(x))^(8xQ(x))B!AAssumeBtrue: (8xP(x))^(8xQ(x)) Means that any specific valuev,P(v)is true AND means that any specificvaluev,Q(v)is true So for anyv,P(v)^Q(v)true Means that this statement is trueforallspecific values Have desired result:A:8x(P(x)^Q(x))SinceA$Bis a tautology, property holds 14 First Example of a Proper Proof Symbols helped determine the structure of the proof Gave some insight into the plan of attack ShowAandBare true/false at the same time Used the fact thatA$B (A!

9 B)^(B!A) Allows showing two smaller things are true, very commonproof structureBy relieving the brain of all unnecessary work, a good nota-tion sets it free to concentrate on more advanced problems,and in effect mental power Alfred North Whitehead, (1911) Ultimately part of the proof wasnot in symbolsbut wasbased on reasoning outside of the notationThe difficulty that attends mathematical symbolism is theaccompanying tendency to take the symbol as exhaustivelydescriptive of reality. Charles Nordmann (1922)15 Exercise:What about the or? These two statements are NOT logically equivalentA:8x(P(x)_Q(x)) B:(8xP(x))_(8xQ(x)) To see why not, find a counter example as follows Pick a universe of discourse (like the integers) Define predicatesP()andQ()such that one of the above istrue while the other is false Will need to find two predicates where one or the other orboth are true about all :What about the or?

10 These two statements are NOT logically equivalentA:8x(P(x)_Q(x)) B:(8xP(x))_(8xQ(x)) Pick a universe of discourse (like the integers) I pick the Integers, as inFor all integers, .. Define predicatesP()andQ() P(x): x is even Q(x): x is odd A:8x(P(x)_Q(x)):For all x where x is an integers, x is evenOR x is B:(8xP(x))_(8xQ(x)):All integers are even OR all integersare by counter example. 17 Good Practice Showed equivalences for the Universal Quantifier8withConjunction/Disjunction Good practice to do the same for the Existential Quantifier9:And?A:9x(P(x)^Q(x))? ?B:(9xP(x))^(9xQ(x))Or?C:9x(P(x)_Q(x))? ?D:(9xP(x))_(9xQ(x))This is the kind of thing that might come up on Quantified ExpressionsNegationEquivalent English:9P(x) 8x:P(x)For all x, P(x) is false.