Predicate Logic PDF

Predicate Logic By the time that you notice this notice, you will notice that this notice is not worth noticing 1/60  Predicate Logic In English, the predicate is the part...

Predicate Logic By the time that you notice this notice, you will notice that this notice is not worth noticing 1/60  Predicate Logic In English, the predicate is the part of the sentence that tells you something about the subject. Eg “x is greater than 3” x - subject “is greater than 3” - predicate In logic a predicate is a boolean valued function applied to one or more variables. P(x) → {true,false} x – subject P – predicate We have already encountered this when describing set definitions “S = the set of objects x belonging to a Domain/Universe U where x satisfies the condition” S = { x | x  U  x satisfies the condition } 2/60 S = { x | x  U  P(x) }  Predicate Logic Example “Steve is a student at QUB” Question: What is the subject in this statement? Two different predicates possible: Let P(x) be “x is a student at QUB” Let Q(x,y) be “x is a student at y” When specific values are assigned, a predicate becomes a proposition (Propositional Logic Section i.e. Boolean statements). 3/60  Predicate Logic Example When specific values are assigned, a predicate becomes a proposition. Let P(x,y,z) be “x is a student at y in z” Let Q(x,z) be “x passes exam in z” P(“Steve”, “QUB”, 2024) ∧ ¬ Q(“Steve”, 2024) ⇒ ¬P(“Steve”, “QUB”, 2025) What does this statement say in English? 4/60  Guess Who Let G(x) = “x has glasses” Let L(x) = “x has long hair” Let M(x) = “x has a moustache” Let B(x) = “x has a beard” Let F(x) = “x has facial hair” F(x) ⇒ B(x) v M(x) F(x) ⋀ L(x) ⋀ G(x) 5/60  Universe of Discourse The domain or universe of discourse for a predicate variable is the set of values which can be assigned to that variable. If P(x) is a predicate and x has domain D, the truth set of P(x) is the set of all elements t in D such that P(t) is true, ie { t | t ∈ D  P(t) is true} Example D = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } Let P(x) = “x is even” / P(x) = x mod 2 = 0 The truth set is { 2, 4, 6, 8, 10 } 6/60  Quantification Remember. Assigning specific values to the variables turns a predicate into a proposition. P(x) = x mod 2 = 0 P(8) = true P(17) = false Another way is to add a quantifier like “All” or “Some” which indicates the number of values for which the predicate is true. 7/60  Quantifiers For All Domain of x: QUBstudents ∀ Let P(x) = “has lectures on Thursday and Friday” ∀𝑥 𝜖 QUBstudents  𝑥 𝜖 𝑐𝑠𝑐1026 ⇒ 𝑃(𝑥) Everyone in csc1026 has lectures on Thurs & Fri There Exists ∃ Let Q(x) = “gets the train to come to university” ∃𝑥 𝜖 QUBstudents  𝑥 𝜖 𝑐𝑠𝑐1026 ∧ 𝑄(𝑥) 8/60 Some people in csc1026 get the train to come to university  Quantifiers For All Domain of x: csc1026 ∀ Let P(x) = “has lectures on Thursday and Friday” ∀𝑥 𝜖 csc1026  𝑃(𝑥) Everyone in csc1026 has lectures on Thurs & Fri There Exists ∃ Let Q(x) = “gets the train to come to university” ∃𝑥 𝜖 csc1026  𝑄(𝑥) 9/60 Some people in csc1026 get the train to come to university  Predicate Logic Summary So Far A predicate is a true or false statement that tells you something about / a property of one or more variables Assigning specific values to the variables turns a predicate into a proposition All the rules of propositional logic already encountered also apply to predicates Quantifiers are another way to turn predicates into propositions by saying something about the number of possible values would make a predicate true Basic introduction to ∀ (for all) and ∃ (there exists) 10/60  Quantification ∀x D  P(x) Ways to read it: For all possible values of x (in the Domain D), P(x) is true For every x, P(x) For every x, P(x) is true For all x, P(x) 11/60  Quantification ∃xD  P(x) Ways to read it: For at least one possible value of x (in the Domain D), P(x) is true There is some x, P(x) There is some x (in D) where P(x) is true There exists an x, P(x) 12/60  Guess Who (Advanced) What happens if each person picks 2 cards instead of one? How does this change the type of questions you need to ask? Does anything else change? 13/60  Guess Who (Advanced) “Do both your people have…” “Do all your people have…” ∀xCP(x) “Do either of your people have…” “Do any etc etc” ∃xCP(x) The Domain of x in this context is the set of chosen cards C 14/60  Negation of Quantifiers ∀xD  P(x) For all possible values of x (in the Domain D), P(x) is true For all x, P(x) What does ¬( ∀xDP(x) ) mean? How would you express it in English? Is it equivalent to ∀xD¬P(x) ? No 15/60  Negation of Quantifiers ¬( ∀xD  P(x) ) The negation of “For all”, requires you to find a counterexample. i.e. At least one value in the domain for which the predicate is not true Example Let P(x) be: x < 15 (Domain of x: D = { 1,…,20 }) Can you say: ∀xDP(x) ? P(1) = true, P(2) = true, P(11) = true etc. But P(15) = false (there are more, but you only need one) 16/60  Negation of Quantifiers ¬( ∀xD  P(x) ) So NOT ( ForAll x, P(x) is true) is the same as: There is at least one value of x for which P(x) is false ¬( ∀xDP(x) ) = ∃xD¬P(x) 17/60  Negation of Quantifiers ¬( ∃xD  P(x) ) Same for “There exists” ∃xDP(x) There is some x (in D) where P(x) is true There exists an x, P(x) The opposite is: There is no x (in D) where P(x) is true There does not exist an x, P(x) For all x, P(x) is false ∀xD¬P(x) 18/60  Negation of Quantifiers De Morgans Laws for Quantifiers ¬( ∀xDP(x) ) = ∃xD¬P(x) ¬( ∃xDP(x) ) = ∀xD¬P(x) Basic Rule: Flip the quantifier, and negate the predicate The Domain does not change 19/60  Numerical Predicates Let P(𝑥) be 𝑥 ≥ 0 Suppose the Domain of x is N, the set of Natural Numbers… Can we say ∀xP(x) Yes What if the Domain of x was changed to Z, the set of Integers No ∃x¬P(x) e.g. -7 20/60  Interpreting Predicates ∃𝑡(𝑡 > 3) ∧ (𝑡 3 > 27) Can you express this predicate in English? Can you prove it? Note: to prove ∃, you really only need provide one example 21/60  Interpreting Predicates What about this English statement. Can you express it in logic? “There is an integer whose square is twice itself”. ∃𝑥𝑥 2 = (𝑥 ∗ 2) What is that integer? 22/60  Interpreting Predicates A note on ∀ and ∃ If D = { 1, 2, 3 } then ∀𝑥𝐷𝑃 𝑥 is the same as: 𝑃 1 ∧ 𝑃(2) ∧ 𝑃(3) And ∃𝑥𝐷𝑃 𝑥 is the same as: 𝑃 1 ∨ 𝑃(2) ∨ 𝑃(3) 23/60  Exercises The Domain is Z, the set of Integers Let: N(x) : x is a non-negative integer E(x) : x is even O(x) : x is odd P(x) : x is a prime number Express the following in logical notation: ❖ There exists an even integer o ∃𝑥 𝐸(𝑥) ❖ Every integer is even or odd o ∀𝑥 𝐸(𝑥) ∨ 𝑂(𝑥) ❖ All prime integers are non-negative o ∀𝑥 𝑃 𝑥 ⇒ 𝑁(𝑥) 24/60  Exercises The Domain is Z, the set of Integers N.B. There may be Let: more than one N(x) : x is a non-negative integer E(x) : x is even way to express the O(x) : x is odd P(x) : x is a prime number same thing in Express the following in logical notation: logical notation ❖ The only even prime is 2 o ∀𝑥 𝐸 𝑥 ∧ 𝑃 𝑥 ⇒ 𝑥 = 2 ❖ Not all integers are odd o ∃𝑥 ¬𝑂(𝑥) ❖ Not all primes are odd o ∃𝑥 𝑃 𝑥 ∧ ¬𝑂(𝑥) ❖ If an integer is not odd, then it must be even o ∀𝑥 ¬𝑂 𝑥 ⇒ 𝐸(𝑥) 25/60  Clarification from earlier Let P(x) = “has lectures on Thursday and Friday Let Q(x) = “gets the train to come to university” ∀𝑥𝐷𝑥 𝜖 𝑐𝑠𝑐1026 ⇒ 𝑃 𝑥 ✓ Everyone in csc1026 has lectures on Thurs & Fri ∃𝑥𝐷𝑥 𝜖 𝑐𝑠𝑐1026 ⇒ 𝑄(𝑥) X ∃𝑥𝐷𝑥 𝜖 𝑐𝑠𝑐1026 ∧ 𝑄(𝑥) ✓ Some people in csc1026 get the train to come to university 26/60  Why? Easy mistake to make but ∃𝑥𝐷𝑃 𝑥 ⇒ 𝑄 𝑥 doesn’t say what we might think it does. ∃𝑥𝐷 𝑤𝑜𝑚𝑎𝑛 𝑥 ⇒ 𝑡𝑎𝑙𝑙(𝑥) Remember A B AB We want to say “There exists a tall woman” T T T But T F F We could also be saying: F T T “There exists something that is not a woman, that is tall” F F T Much weaker statement than was intended. ∃𝑥𝐷𝑤𝑜𝑚𝑎𝑛 𝑥 ∧ 𝑡𝑎𝑙𝑙(𝑥) 27/60  Combining Quantifiers What if a predicate involves more than just one variable? How would you interpret a predicate involving more than one quantifier? E.g. Let A = {2, 6, 14} and B = {6, 8, 11} What does this predicate say?: ∃𝑥𝐴 ∃𝑦𝐵 𝑥 = 𝑦 Is it true? What about this one? ∀𝑥𝐴 ∃𝑦𝐵 𝑥 < 𝑦 Is it true? 28/60  The Lovers Relationship Let L(a,b) be “a loves b” (also b is loved by a) How would you interpret the following predicates into English? ∀𝑥𝐷 ∃𝑦𝐷 𝐿 𝑦, 𝑥 Everyone is loved by someone ∀𝑥𝐷 ∃𝑦𝐷 𝐿 𝑥, 𝑦 Everyone loves someone ∃𝑥𝐷 ∀𝑦𝐷 𝐿 𝑥, 𝑦 Someone loves everyone ∃𝑥𝐷 ∀𝑦𝐷 𝐿 𝑦, 𝑥 Someone is loved by everyone ∃𝑥𝐷 𝐿 𝑥, 𝑥 Someone loves them self ∀𝑥𝐷 𝐿 𝑥, 𝑥 Everyone loves themselves ∃𝑥𝐷 ∃𝑦𝐷 𝐿 𝑥, 𝑦 Someone loves someone ∃𝑥𝐷 ∃𝑦𝐷 𝐿 𝑦, 𝑥 Someone is loved by someone ∀𝑥𝐷 ∀𝑦𝐷 𝐿 𝑥, 𝑦 Everyone loves everyone ∀𝑥𝐷 ∀𝑦𝐷 𝐿 𝑦, 𝑥 Everyone is loved by everyone 29/60  Exercise Express these statements in logic, then negate the statements “Some drivers do not obey the speed limit” “All dogs have fleas” ∃𝑥𝑑𝑟𝑖𝑣𝑒𝑟𝑠 ¬𝑜𝑏𝑒𝑦𝐿𝑖𝑚𝑖𝑡(𝑥) Negated ∀𝑥𝑑𝑟𝑖𝑣𝑒𝑟𝑠 𝑜𝑏𝑒𝑦𝐿𝑖𝑚𝑖𝑡(𝑥) ∀𝑥𝑑𝑜𝑔𝑠 𝑓𝑙𝑒𝑎𝑠 𝑥 Negated ∃𝑥𝑑𝑜𝑔𝑠 ¬𝑓𝑙𝑒𝑎𝑠(𝑥) There are other ways to say the same things in logic, but the negations could be different 30/60  Negation of Multiple Quantifiers Basic rule for negation of quantified predicates (De Morgan): Flip the quantifier and negate the predicate This extends to multiple predicates Example ¬∃𝑥𝐷∀𝑦𝐷∀𝑧𝐷𝑃(𝑥, 𝑦, 𝑧) = ∀𝑥𝐷 ¬∀𝑦𝐷 ∀𝑧𝐷 𝑃 𝑥, 𝑦, 𝑧 = ∀𝑥𝐷 ∃𝑦𝐷 ¬∀𝑧𝐷 𝑃(𝑥, 𝑦, 𝑧) = ∀𝑥𝐷 ∃𝑦𝐷 ∃𝑧𝐷 ¬𝑃(𝑥, 𝑦, 𝑧) 31/60  Sets vs Sequences So far when we want to group objects together we have used mainly used sets Remember: A set is an unordered collection of objects called ‘members’ of the set Order doesn’t matter {15, 41, 89} = {41, 89, 15 } A set doesn’t record multiple occurrences of an element Sometimes the concept of order is useful when describing a problem For this we need another type of collection which we have seen before A sequence [15, 41, 89] ≠ [41, 89, 15] 32/60  Ordered? An ordered list is not the same thing as a sorted list [15, 41, 89] ≠ [41, 89, 15] but they are both ordered For Example In the first sequence: S = [15, 41, 89] This number which refers to 15 is the first term S(1) = 15 the values 41 is the second term S(2) = 41 position is called 89 is the third term S(3) = 89 the index Whereas in the second sequence: T = [41, 89, 15] 41 is the first term T(1) = 41 89 is the second term T(2) = 89 33/60 15 is the third term T(3) = 15  Length of a Sequence A sequence could be finite This means we know how many terms there are and can specify the index of the first and last terms (as well as all those in between However a sequence could also be infinite E.g. S = [2, 4, 6, 8, …] We don’t know how many terms there are We also don’t know anything for sure about the terms beyond the first 4 (though its often safe to make an educated guess with numerical patterns) 34/60  Predicates over Sequences We can use predicates to say things about properties of a sequence. For a sequence of finite length we limit the domain to the number of terms in the sequence. For Example Given the sequence S=[4, 13, 72, 89, 51] What does the following predicate say? ∃𝑖 ∈ {1, … , 5} ∙ 𝑆(𝑖) = 89 89 is in the sequence. It doesn’t tell us where exactly, just that there is at least one index where it 35/60 does.  Sorted A sequence is an ordered list of objects Remember, ordered is not the same as sorted. But how would you express a predicate over a sequence of 5 terms which stated that it was arranged in ascending order? ∀𝑖 ∈ {1, … , 4} ∙ 𝑆(𝑖) < 𝑆(𝑖 + 1) Note the domain of 𝑖 is limited to the first 4 terms because of the use of S(𝑖 + 1) This works for the sequence S=[4, 17, 28, 32, 90] What about S=[5, 21, 21, 52, 52] ? ∀𝑖 ∈ {1, … , 4} ∙ 𝑆(𝑖) ≤ 𝑆(𝑖 + 1) 36/60  Sorted Can you define a predicate which states that a sequence is sorted in either ascending or descending order? Does the following predicate work for a 5 term sequence? e.g. [3, 12, 16, 72, 90] or [205, 180, 72, 17, 10] ∀𝑖 ∈ {1, … , 4} ∙ (𝑆 𝑖 ≤ 𝑆 𝑖 + 1 ) ∨ (𝑆(𝑖) ≥ 𝑆(𝑖 + 1)) ? Does it work for all 5 term sequences? Why not? Give an example sequence which satisfies this predicate, but not the condition we wanted to express [6, 2, 91, 34, 62] How would you fix the predicate? 37/60 (∀𝑖 ∈ {1, … , 4} ∙ 𝑆(𝑖) ≤ 𝑆(𝑖 + 1)) ∨ (∀𝑗 ∈ {1, … , 4} ∙ 𝑆(𝑗) ≥ 𝑆(𝑗 + 1))  Index vs Value ∃𝑖 ∈ 1, … , 5 ∙ ∀𝑗 ∈ {1, … , 5} ∙ 𝑆(𝑖) ≥ 𝑆(𝑗) Important to remember the difference between 𝑖 the index and 𝑆(𝑖) the value in the sequence at that index. Given the sequence S = [14, 5, 71, 22, 7 ] Ask yourself what the predicate says in English There is an index i, and the value at that index is greater than or equal to every other value at every other index Ask yourself what is the value of 𝑖? 3 (not 71 as that would be S(i) ) 38/60  Predicates Over Infinite Sequences If a sequence is infinite we don’t know the last index or the definite values of any terms beyond those we are told about However if we see the values appear to follow a pattern, we can often make a conjecture about what subsequent values may be. Eg What might the next 3 values of this sequence be? S=[2,4,6,8,10…] What about the 50th value? 39/60  Predicates Over Infinite Sequences If we can see a pattern which holds we could define a rule in predicate form which would help us derive potential subsequent values in the sequence. S=[3,5,7,9…] ∀𝑖 ∈ ℕ ∖ {0} ∙ 𝑆(𝑖) = 2 ∗ 𝑖 + 1 This works, and allows us to predict later terms S=[3,5,7,9,11,13…] However we could define a different rule. For example, one which listed “odd numbers without a one in them” Then the sequence would be S=[3,5,7,9,23,25…] 40/60  Fibonacci The Fibonacci sequence is a famous sequence in mathematics 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … What pattern can you see? Can you define a predicate rule which would give this sequence? ∀𝑖 ∈ ℕ ∖ {0} ∙ 𝑆(𝑖) = 𝑆(𝑖 − 2) + 𝑆 𝑖 − 1 Strong enough? 𝑆 1 = 1 ∧ 𝑆 2 = 1 ∧ ∀𝑖 ∈ ℕ ∖ {0, 1, 2} ∙ 𝑆(𝑖) = 𝑆(𝑖 − 2) + 𝑆(𝑖 − 1) 41/60  Look Familiar? Note that, particularly for finite sequences, there is a strong parallel between ∀𝑖 and the concept of for loops over arrays ∀𝑖 ∈ {1, … , 5} ∙ 𝑆(𝑖) = 2 ∗ 𝑖 Defines the sequence: S=[2, 4, 6, 8, 10] Similarly: int[] S = new int; for(int i=0;i