Module 8.1 Propositional Function and Quantification PDF

Ateneo de Davao University No portion of this module is permitted to be uploaded to other resource sharing platforms. Module 8.1 Propositional Function, Quantification, and Negation of Quantified Statements Propositional Function A propositional function or predicate is a complete declar...

Ateneo de Davao University No portion of this module is permitted to be uploaded to other resource sharing platforms. Module 8.1 Propositional Function, Quantification, and Negation of Quantified Statements Propositional Function A propositional function or predicate is a complete declarative sentence P(x) that makes a statement about the variable x. The variable x is called the argument of P(x). If x is assigned a particular value, then P(x) becomes a proposition with a definite truth value. Example: Let P(x) denote the statement “x > 3”. What are the truth values of P(4) and P(2)? Solutions: P(4) : “4 > 3.” This proposition has the truth value T. P(2): “2 > 3.” This has truth value of F. Universal and Existential Quantification When all variables in a propositional function are assigned values, the resulting statement has a truth value. There is another method to change propositional functions into propositions called quantification which may be universal or existential. The universal quantification of P(x) is the proposition “P(x) is true for ALL values of x in the domain of discourse.” The notation ∀ 𝑥𝑃(𝑥), read as “For all x, P(x)” or “For every x, P(x),” denotes the universal quantification of P(x). The domain of discourse specifies the possible values of the variable. Examples: 1. Express the statement “Every student in this class has studied calculus” as a universal quantification. 2. Let P(x) be “x + 1 > x.” What is the truth value of ∀ 𝑥𝑃(𝑥), where the domain of discourse is the set ℝ? 3. Let Q(x) be “x < 2.” What is the truth value of ∀ 𝑥𝑄(𝑥), where the domain of discourse is the set ℚ? Solutions: 1. Let P(x) denote the statement “x has studied calculus.” The given statement can now be expressed as ∀ 𝑥𝑃(𝑥), where the domain of discourse consists of the students in class. 2. ∀ 𝑥𝑃(𝑥): “For all x, x + 1 > x.” Since a real number x will always be smaller than x + 1, ∀ 𝑥𝑃(𝑥) has the truth value of T. 3. ∀ 𝑥𝑄(𝑥): “For all x, x < 2.” Since x < 2 is not true when x = 3, ∀ 𝑥𝑄(𝑥) has the truth value of F. The existential quantification of P(x) is the proposition “There exist an element x in the domain of discourse such that P(x) is true.” The notion ∃ 𝑥𝑃(𝑥) is read as “There is an x such that P(x)” or “For some x, P(x).” These denote the existential quantification of P(x). Examples: 1. Let P(x) be “x + 1 > x.” What is the truth value of ∃ 𝑥𝑃(𝑥), where the domain of discourse is the set ℝ? 2. Let Q(x) be “x < 2.” What is the truth value of ∃ 𝑥𝑄(𝑥), where the domain of discourse is the set ℚ? Ateneo de Davao University No portion of this module is permitted to be uploaded to other resource sharing platforms. Solutions: 1. ∃ 𝑥𝑃(𝑥): “There is an x such that x + 1 > x.” Since x + 1 > x when x = 1, ∃ 𝑥𝑃(𝑥) has the truth value of T. 2. ∃ 𝑥𝑄(𝑥): “There is an x such that x < 2.” Since x < 2 when x = 0, ∃ 𝑥𝑄(𝑥) has the truth value of T. Negation of Quantified Statements Statement Negation All X are Y. Some X are not Y. No X are Y. Some X are Y. Some X are not Y. All X are Y. Some X are Y. No X are Y. Exercises: I. Use quantifiers to express the following statements. 1. Every student needs a course in mathematics. 2. There is a student in this class who owns a dual SIM smartphone. 3. Every student in this class has been in every building on campus. 4. There is a student in this class who has been in every floor of at least one building on campus. II. Let Q(x, y) denote the statement “x is the capital of y.” What are the truth values of Q(Paris, France), Q(Sydney, Australia), and Q(Japan, Tokyo)? III. Let P(x, y) denote “x + y = 0.” What are the truth values of ∃𝑦 ∀𝑥𝑃(𝑥, 𝑦) and ∀𝑥 ∃𝑦 𝑃(𝑥, 𝑦)? III. Write the negation of each of the following statements. 1. Some airports are open. 2. All movies are worth the price of admission. 3. No odd numbers are divisible by 2. Answer Key I. 1. Let 𝑃(𝑥) denote the statement “x needs a course in mathematics”; ∀ 𝑥𝑃(𝑥), where the domain of discourse consists of students. 2. Let 𝑄(𝑥) denote the statement “x is a student who owns a dual SIM smartphone”; ∃ 𝑥𝑄(𝑥), where the domain of discourse consists of students in this class. 3. Let 𝑅(𝑥) denote the statement “x has been in every building on campus; ∀ 𝑥𝑅(𝑥), where the domain of discourse consists of students in this class. 4. Let 𝑆(𝑥) denote the statement “x has been un every floor of at least one building on campus; ∃ 𝑥𝑆(𝑥), where the domain of discourse consists of students in this class. II. T, F, F III. F, T IV. 1. No airports are open. 2. Some movies are not worth the price of admission. 3. Some odd numbers are divisible by 2.