COSC 221 Discrete Structures Week 2 Predicate Logic 2025 PDF

COSC 221 Introduction to Discrete Structures Week 2 - Predicate Logic 1/13/2025 Okanagan College 1 Predicates A predicate is a proposition defined with variables. The truth value of the predicate depends on the variables. Think a predicate is a boolean...

COSC 221 Introduction to Discrete Structures Week 2 - Predicate Logic 1/13/2025 Okanagan College 1 Predicates A predicate is a proposition defined with variables. The truth value of the predicate depends on the variables. Think a predicate is a boolean function. For example: 𝑃(𝑥): “𝑥 has 31 days.” where 𝑥 is a month. Then 𝑃(January) is true, while 𝑃(February) is false. 𝑃(𝑎, 𝑏): “𝑎 > 𝑏” where 𝑎 and 𝑏 are numerical values. Then 𝑃(5,1) is true, while 𝑃(9, 9) is false. *Here we only use single letters to represent predicates, but in other textbooks you may also see words. E.g., CAT(x): x is a cat 1/13/2025 Okanagan College 2 Domain of Interpretation The domain of interpretation (or simply, domain) refers to the set of objects and values, the variables can take from. It provides the concrete meaning to symbols and terms used in the formal system. For the predicate 𝑃(𝑥): “𝑥 has 31 days.”, the domain of 𝑥 can be the set of months. It doesn’t make sense to use, for example, the world of animals to be the domain. *Domains are important but can sometimes be assumed from the context. Winter 2024 Okanagan College Quantifiers Universal Quantifier (∀) The universal quantifier means “for all”, “any”, “every”, etc. Existential Quantifier (∃) The existential quantifier means “there is”, “there are”, “some”, “at least one”, etc. The symbols quantify some variables, and apply to predicates. For example: ∀𝑥𝑃(𝑥): “For every 𝑥, 𝑃 𝑥 is true.” ∃𝑦𝑃(𝑦): “There exists some 𝑦, such that 𝑃(𝑦) is true.” 1/13/2025 Okanagan College 4 Expansion with Quantifiers If the domain is finite, for example {𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛 }, then ∀𝑥𝑃(𝑥) is the same as 𝑃 𝑥1 ∧ 𝑃(𝑥2 ) ∧ ⋯ ∧ 𝑃(𝑥𝑛 ), and ∃𝑥𝑃(𝑥) is the same as 𝑃 𝑥1 ∨ 𝑃(𝑥2 ) ∨ ⋯ ∨ 𝑃(𝑥𝑛 ). Winter 2024 Okanagan College Examples What are the truth values? 1. 𝑃(𝑥): “𝑥 is yellow” (domain is all flowers) ∀𝑥𝑃(𝑥) is false; ∃𝑥𝑃(𝑥) is true; 2. 𝑃(𝑥): “𝑥 is a plant” (domain is all flowers) ∀𝑥𝑃(𝑥) is true; ∃𝑥𝑃(𝑥) is true; 3. 𝑃(𝑥): 𝑥 > 5 (domain is all integers) ∀𝑥𝑃(𝑥) is false; ∃𝑥𝑃(𝑥) is true; 1/13/2025 Okanagan College 6 Comparing the Quantifiers Can you find one interpretation of 𝑃(𝑥) in which ∀𝑥𝑃(𝑥) is true while ∃𝑥𝑃(𝑥) is false? - Not possible Can you find one interpretation of 𝑃(𝑥) in which ∃𝑥𝑃(𝑥) is true while ∀𝑥𝑃(𝑥) is false? - Example 1 and 3 in the previous slide 1/13/2025 Okanagan College 7 Negation of Quantified Predicates By De Morgan’s Law, ¬ ∀𝑥𝑃 𝑥 ≡ ∃𝑥¬𝑃(𝑥) and ¬ ∃𝑥𝑃 𝑥 ≡ ∀𝑥¬𝑃(𝑥) Intuitive interpretations: The negation of “all apples are sweet” is the same as “some apples are not sweet”. The negation of “some apples are sweet” is the same as “all apples are not sweet” 1/13/2025 Okanagan College 8 Question Which one is the negation of “Everybody loves somebody sometime.” Everybody hates somebody sometime Somebody loves everybody all the time Everybody hates everybody all the time Somebody hates everybody all the time 1/13/2025 Okanagan College 9 Question What is the negation of the following statements? Some pictures are old or faded. All pictures are neither old nor faded. All people are tall and thin. Some people are not tall or not thin. 1/13/2025 Okanagan College 10 Predicates with Multiple Variables Predicates involving properties of single variables are known as unary predicates. Binary, ternary and n-ary predicates are also possible. 𝑄(𝑥, 𝑦) is a binary predicate. The expression ∀𝑥∃𝑦𝑄(𝑥, 𝑦) reads as “for every 𝑥 there exists a 𝑦 such that 𝑄(𝑥, 𝑦).” - The domain may be different for each variable 1/13/2025 Okanagan College 11 Predicates with Multiple Variables Are ∀𝑥∀𝑦𝑃(𝑥, 𝑦) the same as ∀𝑦∀𝑥𝑃(𝑥, 𝑦)? - Yes. (∀𝑥∀𝑦 can be written as ∀𝑥, 𝑦) Are ∃𝑥∃𝑦𝑃(𝑥, 𝑦) the same as ∃𝑦∃𝑥𝑃(𝑥, 𝑦)? - Yes. (∃𝑥∃𝑦 can be written as ∃𝑥, 𝑦) Are ∀𝑥∃𝑦𝑃(𝑥, 𝑦) the same as ∃𝑦∀𝑥𝑃(𝑥, 𝑦)? - No. 1/13/2025 Okanagan College 12 Scope of a Variable Brackets and parentheses may be used to identify the scope of the variable. ∀𝑥 ∃𝑦 𝑃 𝑥, 𝑦 ∨ 𝑄 𝑥, 𝑦 →𝑅 𝑥 Scope of ∃𝑦 is 𝑃 𝑥, 𝑦 ∨ 𝑄(𝑥, 𝑦), while the scope of ∀𝑥 is the entire expression in parentheses following it. ∀𝑥(𝑃 𝑥, 𝑦 → ∃𝑦𝑄(𝑥, 𝑦)) Variable 𝑦 in 𝑃(𝑥, 𝑦) is not within the scope of a 𝑦 quantifier, hence 𝑦 is called a free variable. Such expressions might not have a truth value at all. 1/13/2025 Okanagan College 13 Exercise What is the truth value of the expression ∃𝑥 𝐴 𝑥 ∧ ∀𝑦 𝐵 𝑥, 𝑦 → 𝐶 𝑦 where 𝐴(𝑥) interprets as 𝑥 > 0, 𝐵 𝑥, 𝑦 interprets as 𝑥 > 𝑦, 𝐶 𝑦 interprets as 𝑦 ≤ 0, the domain of both 𝑥 and 𝑦 is all integers True, 𝑥 = 1 is a positive integer and any integer 𝑦 < 1 must be the case that 𝑦 ≤ 0. 1/13/2025 Okanagan College 14 Translating Verbal Statements 𝑃(𝑥): 𝑥 is an apple 𝑄(𝑥): 𝑥 is sweet “All apples are sweet” can be translated to “for anything, if it is an apple, then it is sweet”. ∀𝑥 𝑃 𝑥 → 𝑄 𝑥 “Some apples are sweet” can be translated to “There exists something that is an apple and is sweet” ∃𝑥 𝑃 𝑥 ∧ 𝑄 𝑥 Almost always, ∃ goes with ∧ while ∀ goes with →. It doesn’t make sense to have ∃𝑥 𝑃 𝑥 → 𝑄 𝑥. Why? 1/13/2025 Okanagan College 15 “Only” The word “only” can be tricky depending on its presence in the statement. Usually we can try to convert “only” to “if- then” (recall that the clause following only is the conclusion of an implication): X loves only Y ≡ If X loves anything, then that thing is Y. Only X loves Y ≡ If anything loves Y, then it is X. X only loves Y ≡ If X does anything to Y, then it is love. 1/13/2025 Okanagan College 16 Translation Exercises 𝑆(𝑥): 𝑥 is a student; 𝐼(𝑥): 𝑥 is intelligent; 𝑀(𝑥): 𝑥 likes music Write wffs that express the following statements: All students are intelligent. ∀𝑥 𝑆 𝑥 → 𝐼 𝑥 Some intelligent students like music. ∃𝑥 𝐼 𝑥 ∧ 𝑆 𝑥 ∧ 𝑀 𝑥 Everyone who likes music is a stupid student. ∀𝑥 𝑀 𝑥 → ¬𝐼 𝑥 ∧ 𝑆 𝑥 Only intelligent students like music. ∀𝑥 𝑀 𝑥 → 𝐼 𝑥 ∧ 𝑆 𝑥 1/13/2025 Okanagan College 17 Translation Exercises Using the following predicates: 𝐶(𝑥): 𝑥 is a computer 𝑃(𝑥): 𝑥 is a program 𝑅(𝑥, 𝑦): 𝑥 runs 𝑦 Write the following statements in formal logic: All computers run all programs. Some computers run all programs. Only computers run programs. 1/13/2025 Okanagan College 18 Translation Exercises “All computers run all programs.” ≡ “For any 𝑥, if it is a computer, then for any 𝑦, if it is a program, then 𝑥 (the computer) runs 𝑦 (the program).” ∀𝑥 𝐶 𝑥 → ∀𝑦 𝑃 𝑦 → 𝑅 𝑥, 𝑦 “Some computers run all programs.” ≡ “There is some 𝑥 that is a computer and for anything 𝑦, if that 𝑦 is a program, then 𝑥 (the computer) runs 𝑦 (the program).” ∃𝑥 𝐶 𝑥 ∧ ∀𝑦 𝑃 𝑦 → 𝑅 𝑥, 𝑦 “Only computers run programs.” ≡ “For any two things, if one is a program and the other runs it, then the other is a computer.” ∀𝑥, 𝑦 𝑃 𝑦 ∧ 𝑅 𝑥, 𝑦 → 𝐶 𝑥 1/13/2025 Okanagan College 19 Question What is the negation of the following? Some students eat only pizza. Rewrite the statement to “for some students, if they eat anything, then that something is pizza.” The negation is “all students eat something that is not pizza” Only students eat pizza. Rewrite the statement to “for any two things, if the second thing is pizza and the first thing eats it, then the first thing is a student.” The negation is “there exists non-student who eats pizza” 1/13/2025 Okanagan College 20 Validity of Predicate Arguments Recall that an argument is valid means the implication is a tautology (always true regardless the truth value of all the variables). For predicate arguments, they are valid when the implication is always true regardless of the interpretation of the predicates. It is possible to check the validity of a propositional argument, but maybe impossible for a quantified predicate argument. 1/13/2025 Okanagan College 21 Validity Examples ∀𝑥𝑃 𝑥 → ∃𝑥𝑃(𝑥) is valid. ∃𝑥𝑃 𝑥 → ∀𝑥𝑃(𝑥) is invalid. ∀𝑥 𝑃 𝑥 → 𝑄 𝑥 ∧ ∃𝑥𝑃 𝑥 → ∃𝑥𝑄 𝑥 is valid. 1/13/2025 Okanagan College 22 Proofs in Predicate Logic Four new rules to strip off quantifiers and reinstall quantifiers. The rest are the same as in propositional logic. From Can Derive Name / Abbreviation ∀𝑥𝑃(𝑥) 𝑃(𝑎) where 𝑎 is a Universal Instantiation variable or constant (ui) symbol ∃𝑥𝑃(𝑥) 𝑃(𝑎) where 𝑎 is a Existential Instantiation constant symbol not (ei) previously used in a proof sequence 𝑃(𝑥) where 𝑥 ∀𝑥𝑃(𝑥) Universal Generalization is an arbitrary (ui) variable 𝑃(𝑥) or 𝑃(𝑎) ∃𝑥𝑃(𝑥) Existential Generalization (eg) 1/13/2025 Okanagan College 23 Example Prove: ∀𝑥 𝑃 𝑥 → 𝑄 𝑥 ∧ ∃𝑥𝑃 𝑥 → ∃𝑥𝑄 𝑥 1. ∀𝑥 𝑃 𝑥 → 𝑄 𝑥 hyp 2. ∃𝑥𝑃 𝑥 hyp 3. 𝑃(𝑎) 2 ei 4. 𝑃 𝑎 → 𝑄 𝑎 1 ui 5. 𝑄(𝑎) 3,4 mp 6. ∃𝑥𝑄 𝑥 5 eg 1/13/2025 Okanagan College 24 Instantiation Existential instantiation: Whenever possible, perform existential instantiation first. We have no power to choose what instance to use, we get what we get. By convention, use letters like 𝑎, 𝑏, 𝑐, etc. to indicate that they are certain instances. Universal instantiation: We have the power to choose arbitrary instance/value of the variable. Either choose existing instances like 𝑎, 𝑏, 𝑐 if we want to use the statement on the certain instances or keep it arbitrary, and use letters like 𝑥, 𝑦, 𝑧 1/13/2025 Okanagan College 25 Example Prove: ∀𝑥 𝑃 𝑥 → 𝑄 𝑥 ∧ ∀𝑥𝑃 𝑥 → ∀𝑥𝑄(𝑥) 1. ∀𝑥 𝑃 𝑥 → 𝑄 𝑥 hyp 2. ∀𝑥𝑃 𝑥 hyp 3. 𝑃 𝑥 → 𝑄 𝑥 1 ui 4. 𝑃 𝑥 2 ui 5. 𝑄 𝑥 3,4 mp 6. ∀𝑥𝑄(𝑥) 5 ug 1/13/2025 Okanagan College 26 Instantiation and Generalization of Nested Quantifiers For nested quantifiers, for example ∀𝑥∃𝑦𝑃(𝑥, 𝑦), remember it is actually ∀𝑥 ∃𝑦𝑃 𝑥, 𝑦. We need to instantiate the outer quantifier first. Consider this example: 𝑃(𝑥, 𝑦) interprets as “𝑦 is 𝑥’s mom”. ∀𝑥∃𝑦𝑃(𝑥, 𝑦) is true but ∀𝑥𝑃(𝑥, 𝑎) is not true. 1/13/2025 Okanagan College 27 Proving Verbal Arguments Example 1 “Every computer only runs programs. Some computers run something. Therefore, there is program” Use the following predicates, rewrite the argument: 𝐶(𝑥): 𝑥 is a computer 𝑃(𝑥): 𝑥 is a program 𝑅(𝑥, 𝑦): 𝑥 runs 𝑦 1/13/2025 Okanagan College 28 Proving Verbal Arguments Example 1 ∀𝑥∀𝑦 𝐶 𝑥 ∧ 𝑅 𝑥, 𝑦 → 𝑃 𝑦 ∧ ∃𝑥∃𝑦 𝐶 𝑥 ∧ 𝑅 𝑥, 𝑦 → ∃𝑥𝑃 𝑥 1. ∀𝑥∀𝑦 𝐶 𝑥 ∧ 𝑅 𝑥, 𝑦 → 𝑃 𝑦 hyp 2. ∃𝑥∃𝑦 𝐶 𝑥 ∧ 𝑅 𝑥, 𝑦 hyp 3. ∃𝑦 𝐶 𝑎 ∧ 𝑅 𝑎, 𝑦 2 ei 4. 𝐶 𝑎 ∧ 𝑅 𝑎, 𝑏 3 ei 5. ∀𝑦 𝐶 𝑎 ∧ 𝑅 𝑎, 𝑦 → 𝑃 𝑦 1 ui 6. 𝐶 𝑎 ∧ 𝑅 𝑎, 𝑏 → 𝑃 𝑏 5 ui 7. 𝑃 𝑏 3,5 mp 8. ∃𝑥𝑃 𝑥 7 eg 1/13/2025 Okanagan College 29 Proving Verbal Arguments Example 2 “Every computer runs every program. HP ProBook is a computer. However, there is an image, and HP ProBook does run that image. Therefore, something is not a program.” Use the following predicates, rewrite the argument: 𝐶(𝑥): 𝑥 is a computer 𝑃(𝑥): 𝑥 is a program 𝑅(𝑥, 𝑦): 𝑥 runs 𝑦 𝐼(𝑥): 𝑥 is an image ℎ: a constant, HP ProBook Although not said explicitly, all the predicates have their own variable domains. What possibly are they? 1/13/2025 Okanagan College 30 Proving Verbal Arguments ∀𝑥∀𝑦 𝐶 𝑥 ∧ 𝑃 𝑦 → 𝑅 𝑥, 𝑦 ∧ 𝐶 ℎ ∧ ∃𝑥 𝐼 𝑥 ∧ ¬ 𝑅 ℎ, 𝑥 → ∃𝑥 ¬𝑃 𝑥 1. ∀𝑥∀𝑦 𝐶 𝑥 ∧ 𝑃 𝑦 → 𝑅 𝑥, 𝑦 hyp 2. 𝐶 ℎ hyp 3. ∃𝑥 𝐼 𝑥 ∧ ¬ 𝑅 ℎ, 𝑥 hyp 4. 𝐼 𝑎 ∧ ¬ 𝑅 ℎ, 𝑎 3 ei 5. ∀𝑦 𝐶 ℎ ∧ 𝑃 𝑦 → 𝑅 ℎ, 𝑦 1 ui 6. 𝐶 ℎ ∧ 𝑃 𝑎 → 𝑅 ℎ, 𝑎 5 ui 7. ¬ 𝑅 ℎ, 𝑎 4 simp 8. ¬ 𝐶 ℎ ∧ 𝑃 𝑎 6,7 mt 9. ¬𝐶 ℎ ∨ ¬𝑃(𝑎) 8 dm 10. ¬𝑃(𝑎) 2,9 ds 11. ∃𝑥 ¬𝑃 𝑥 10 eg 1/13/2025 Okanagan College 31 Implicit Quantification Consider the statement: “If an integer is divisible by 4, then it is divisible by 2” What it really means is “for all integer, if it is divisible by 4, then it is divisible by 2” Another statement: “The number 9 is a product of two positive integers that are not 1 and are not 9” It means “there exists two positive integers 𝑥 and 𝑦, such that they are not 1 and not 9 and 𝑥𝑦 = 9”. 1/13/2025 Okanagan College 32 Implicit Hypotheses Consider the argument: “The sum of two odd integers is even.” We can rewrite it as “For any two integers 𝑥 and 𝑦, if 𝑥 is odd and 𝑦 is odd, then 𝑥 + 𝑦 is even.” To prove it is valid, we need additional hypotheses: ∀𝑥(“𝑥 is an odd number” ∃𝑘(𝑥 = 2𝑘 + 1)) ∀𝑥(“𝑥 is an even number” ∃𝑘(𝑥 = 2𝑘)) and other definitions for addition, multiplication, etc. 1/13/2025 Okanagan College 33