Discrete Mathematics Predicates and Quantifiers

Page 1 of 6 Predicates Propositional logic is not enough to express the meaning of all statements in mathematics and natural language. Examples: Is “𝑥 > 1” True or False? Is “𝑥 is a great tennis player” True or False? Predicate Logic  Variables: 𝑥, 𝑦, 𝑧, etc.  Predicates: 𝑃(𝑥), 𝑄(𝑥), etc.  Quantifiers: Universal and Existential.  Connectives from propositional logic carry over to predicate logic. A predicate 𝑃(𝑥) is a declarative sentence whose truth value depends on one or more variables. 𝑃(𝑥) is also said to be the value of the propositional function 𝑃 at 𝑥. 𝑃(𝑥) becomes a proposition when a value of 𝑥 is assigned from the domain 𝑈. Examples (Propositional Functions): 1. Let 𝑃(𝑥) be “𝑥 ≥ 1.” Determine the truth value of a. 𝑃(2) b. 𝑃(−2) → 𝑃(1) 2. Let 𝑅(𝑥, 𝑦, 𝑧) be “𝑥 + 𝑦 = 𝑧.” Find these truth values: a. 𝑅(2, −1, 5) b. 𝑅(𝑥, 3, 𝑧) Page 2 of 6 Quantifiers We need quantifiers to express the meaning of English words including all and some:   “All students in this class are computer science majors” “There is a math major student in this class” The two most important quantifiers are:   Universal Quantifier, “For all,” symbol: ∀ Existential Quantifier, “There exists,” symbol: ∃ We write as in ∀𝑥 𝑃(𝑥) and ∃𝑥 𝑃(𝑥).  ∀𝑥 𝑃(𝑥) asserts 𝑃(𝑥) is true for every 𝑥 in the domain. If = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } , then ∀𝑥 𝑃(𝑥) = 𝑃(𝑥1 ) ∧ 𝑃(𝑥2 ) … ∧ 𝑃(𝑥𝑛 ).  ∃𝑥 𝑃(𝑥) asserts 𝑃(𝑥) is true for some 𝑥 in the domain. If = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } , then ∃𝑥 𝑃(𝑥) = 𝑃(𝑥1 ) ∨ 𝑃(𝑥2 ) … ∨ 𝑃(𝑥𝑛 ). Examples: 1. Let 𝑃(𝑥): “𝑥 > −𝑥” with the domain of all positive real numbers. Find the truth value of ∀𝑥 𝑃(𝑥). 2. Let 𝑃(𝑥): “𝑥 > −𝑥” with the domain of all real numbers. Find the truth value of ∀𝑥 𝑃(𝑥).  The truth value of ∃𝑥 𝑃(𝑥) and ∀𝑥 𝑃(𝑥) depends BOTH on the propositional function 𝑃(𝑥) and on the domain 𝑈. Quantifiers Statement When True? When False? ∀𝑥 𝑃(𝑥) 𝑃(𝑥) is true for every 𝑥. There is an x for which 𝑃(𝑥) is false. ∃𝑥 𝑃(𝑥) There is an x for which 𝑃(𝑥) is true. 𝑃(𝑥) is false for every 𝑥. Page 3 of 6 Example: Suppose the domain of the propositional function 𝑃(𝑥): 𝑥 2 ≤ 𝑥 consists of {1, 2, 3}. Write out each of the following propositions using conjunction or disjunction and determine its truth value. 1. ∀𝑥 𝑃(𝑥) 2. ∃𝑥 𝑃(𝑥) An element for which 𝑃(𝑥) is false is called a counterexample of ∀𝑥 𝑃(𝑥) Precedence of Quantifiers The quantifiers ∀ and ∃ have higher precedence than all the logical operators. Example: ∀𝑥 𝑃(𝑥) ∨ 𝑄(𝑥) means (∀𝑥 𝑃(𝑥)) ∨ 𝑄(𝑥). ∀𝑥 (𝑃(𝑥) ∨ 𝑄(𝑥)) means something different. Negating Quantifiers De Morgan laws for quantifiers (the rules for negating quantifiers) are: ¬∀𝑥 𝑃(𝑥) ≡ ∃𝑥¬𝑃(𝑥) ¬∃𝑥 𝑃(𝑥) ≡ ∀𝑥¬ 𝑃(𝑥) Example: Express each of these statements using quantifiers. Then form a negation of the statement, so that no negation is left of a quantifier. Next, express the negation in simple English. 1. “Some old dogs can learn new tricks.” Page 4 of 6 2. “Every bird can fly.” 3. ∀𝑥(𝑥 2 > 𝑥) Page 5 of 6 Translating from English into Logical Expressions Examples: Translate the statements into the logical symbols. Let 𝑥 be in set of all students in this class. 1. Someone in your class can speak Hindi. 2. Everyone in your class is friendly. 3. There is a student in your class who was not born in California. 𝐻(𝑥) = “ 𝑥 𝑠𝑝𝑒𝑎𝑘𝑠 𝐻𝑖𝑛𝑑𝑖”, 𝐹(𝑥) = “ 𝑥 𝑖𝑠 𝑓𝑟𝑖𝑒𝑛𝑑𝑙𝑦, ” 𝐶(𝑥) = “ 𝑥 𝑤𝑎𝑠 𝑏𝑜𝑟𝑛 𝑖𝑛 𝐶𝑎𝑙𝑖𝑓𝑜𝑟𝑛𝑖𝑎. ” Example: Translate the following sentence into predicate logic and give its negation: “Every student in this class has taken a course in Java.” Solution: First, decide on the domain U! Solution 1: If U is all students in this class, define a propositional function J(x) denoting “x has taken a course in Java” and translate as Solution 2: But if U is all people, also define a propositional function S(x) denoting “x is a student in this class” and translate as Page 6 of 6 Example: Translate the following sentence into predicate logic: “Some student in this class has taken a course in Java.” Solution: First, decide on the domain U! Solution 1: If U is all students in this class, translate as Solution 2: But if U is all people, then translate as