DISCRTE STRUCTURES CSY1-QUANTIFIERS.pptx

quantifiers in discrete math for computer science students

1. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 1 QUANTIFIERS Discrete Structures 1 Lecture 3

2. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 2 Introduction Logic that deals with propositions is incapable of describing most of the statements in mathematics and computer science. For example p : n is an odd integer. The statement p is not a proposition because the truth or falsity of p depends on the value of n. Since most statements in mathematics and computer science use variables, we must extend the system of logic to include such mathematical statements.

3. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 3 Universe of Discourse Definition: Let P(x) be a statement involving the variable x and let D be a set. We call P a propositional function (with respect to D) if for each x in D, P(x) is a proposition. We call D the domain of discourse of P . A propositional function P , by itself, is neither true nor false. However, for each x in its domain of discourse, P(x) is a proposition and is, therefore, either true of false. P is also called a predicate .

4. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 4 The statement “x is greater than 3” has two parts. The first part, the variable x, is the subject of the statement. The second part—the predicate, “is greater than 3”—refers to a property that the subject of the statement can have. We can denote the statement “x is greater than 3” by P (x), where P denotes the predicate “is greater than 3” and x is the variable. The statement P (x) is also said to be the value of the propositional function P at x. Once a value has been assigned to the variable x, the statement P (x) becomes a proposition and has a truth value. Consider Examples 1 and 2.

5. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 5 EXAMPLE 1 Let P (x) denote the statement “x > 3.” What are the truth values of P (4) and P (2)? Solution: We obtain the statement P (4) by setting x = 4 in the statement “x > 3.” Hence, P (4), which is the statement “4 > 3,” is true. However, P (2), which is the statement “2 > 3,” is false

6. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 6 EXAMPLE 2 Let A(x) denote the statement “Computer x is under attack by an intruder.” Suppose that of the computers on campus, only CS2 and MATH1 are currently under attack by intruders. What are truth values of A(CS1), A(CS2), and A(MATH1)? Solution: We obtain the statement A(CS1) by setting x = CS1 in the statement “Computer x is under attack by an intruder.” Because CS1 is not on the list of computers currently under attack, we conclude that A(CS1) is false. Similarly, because CS2 and MATH1 are on the list of computers under attack, we know that A(CS2) and A(MATH1) are true.

7. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 7 Example 1 Let P(n) = n is an odd integer and D be the set of positive integers. Then P is a propositional function with domain of discourse D since for each n in D, P(n) is a proposition. For example, if n = 1, we obtain the proposition 1 is an odd integer (which is true) if n = 2, we obtain the proposition 2 is an odd integer (which is false)

8. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 8 Example 2 The following are propositional functions: n 2 + 2n is an odd integer (D = set of positive integers) x 2 – x – 6= 0 (D = set of real numbers) The student gets a GPA of 3.0 or better during the 2 nd semester SY 2023-2024 (D = set of students in CIT) The actress has won a FAMAS award. (D = set of actresses)

9. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 9 Quantifier - refers to quantities such as “some” or “all”. It tells for how many elements a given predicate is true. It is also used to express the quantities without giving an exact number. Ex. All, some, many, none, few etc. Example in sentence: Can I have some water? Jack has many friends.

10. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 10 Quantifiers Most of the statements in mathematics and computer science use terms such as “for every” and “for some.” For example, in mathematics we have the statements: For every triangle T, the sum of the angles of T is equal to 180 °. For some triangle S, the sum of two angles is less than 90°. Universal and Existential Quantifiers

11. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 11 Universal Quantifier Definition: Let P be a propositional function with domain of discourse D . The statement for every x, P(x) is said to be a universally quantified statement . The symbol  means “ for every .” Thus the statement above may be written  x, P(x). The symbol  is called a universal quantifier . The statement for every x, P(x) is true if P(x) is true for every x in D and false if P(x) is false for at least one x in D .

12. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 12 Existential Quantifier Definition: Let P be a propositional function with domain of discourse D . The statement for some x, P(x) is said to be an existentially quantified statement . The symbol  means “ for some .” Thus the statement above may be written  x, P(x). The symbol  is called an existential quantifier . The statement for some x, P(x) is true if P(x) is true for at least one x in D and false if P(x) is false for every x in D .

13. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 13 Binding Variables We call the variable x in the propositional function P(x) a free variable . (The idea is that x is “free” to roam over the domain of discourse). We call the variable x in the universally quantified statement x, P(x) or the existentially quantified statement x, P(x) a bound variable . (The idea is the x is “bound” by the quantifier  or .) We previously pointed out that a propositional function does not have a truth value. Quantifiers assign a truth value to the propositional function. In general, an unquantified statement is not a proposition and a quantified statement is a proposition.

14. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 14 Binding Variables The part of a logical expression to which a quantifier is applied is called the scope of this quantifier. In the statement x P(x,y), the variable x is bound by the existential quantification x, but the variable y is free because it is not bound by a quantifier and no value is assigned to it.

15. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 15 Binding Variables In the statement x (P(x)  Q(x))  y R(y), all variables are bound. The scope of the first quantifier, x, is the expression P(x)  Q(x) because x is applied only to P(x)  Q(x), and not to the rest of the statement. Similarly, the scope of the second quantifier, y is the expression R(y).

16. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 16 Remarks The symbol  may be read “for every,” “for all,” or “for any.” The symbol  may be read “for some,” “for at least one,” or “there exists.” Sometimes, to specify the domain of discourse D , we write a universally quantified statement as for every x in D , P(x) and we write an existentially quantified statement as for some x in D , P(x) .

17. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 17 Remarks The universally quantified statement for every x, P(x) is false if for at least one x in the domain of discourse, the proposition P(x) is false. A value x in the domain of discourse that makes P(x) false is called a counterexample to the statement for every x, P(x).

18. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 18 Table 1. Quantifiers Statement When True? When False? x P(x) x P(x) P(x) is true for every x. There is an x for which P(x) is true. There is an x for which P(x) is false. P(x) is false for every x.

19. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 19 Universal Quantifier EXAMPLE : Let P (x) be the statement “x + 1 > x.” What is the truth value of the quantification ∀xP (x), where the domain consists of all real numbers? Solution: Because P (x) is true for all real numbers x, the quantification ∀xP (x) is true.

20. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 20 Note that if the domain is empty, then ∀xP (x) is true for any propositional function P (x) because there are no elements x in the domain for which P (x) is false. Remember that the truth value of ∀xP (x) depends on the domain! Besides “for all” and “for every,” universal quantification can be expressed in many other ways, including “all of,” “for each,” “given any,” “for arbitrary,” “for each,” and “for any.” Remark: It is best to avoid using “for any x” because it is often ambiguous as to whether “any” means “every” or “some.” In some cases, “any” is unambiguous, such as when it is used in negatives, for example, “there is not any reason to avoid studying.” A statement ∀xP (x)is false, whereP (x)is a propositional function, if and only ifP (x)is not always true when x is in the domain. One way to show thatP (x)is not always true when x is in the domain is to find a counterexample to the statement ∀xP (x). Note that a single counterexample is all we need to establish that ∀xP (x)is false. Example 9 illustrates how counterexamples are used.

21. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 21 Example 2. Let Q(x) be the statement “x < 2.” What is the truth value of the quantification ∀xQ(x), where the domain consists of all real numbers? Solution: Q(x) is not true for every real number x, because, for instance, Q(3) is false. That is, x = 3 is a counterexample for the statement ∀xQ(x). Thus ∀xQ(x) is false.

22. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 22 Existential Quantifier The existential quantification of P (x) is the proposition “There exists an element x in the domain such that P (x).” We use the notation ∃xP (x) for the existential quantification of P (x). Here ∃ is called the existential quantifier. A domain must always be specified when a statement ∃xP (x) is used. Furthermore, the meaning of ∃xP (x) changes when the domain changes. Without specifying the domain, the statement ∃xP (x) has no meaning. Besides the phrase “there exists,” we can also express existential quantification in many other ways, such as by using the words “for some,” “for at least one,” or “there is.” The existential quantification ∃xP (x) is read as “There is an x such that P (x),” “There is at least one x such that P (x),” or “For some xP (x).”

23. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 23 Existenial Quantifier EXAMPLE1. Let P (x) denote the statement “x > 3.” What is the truth value of the quantification ∃xP (x), where the domain consists of all real numbers? Solution: Because “x > 3” is sometimes true—for instance, when x = 4—the existential quantification of P (x), which is ∃xP (x), is true. ▲ Observe that the statement ∃xP (x) is false if and only if there is no element x in the domain for which P (x) is true. That is, ∃xP (x) is false if and only if P (x) is false for every element of the domain.

24. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 24 Example 2. Let Q(x) denote the statement “x = x + 1.” What is the truth value of the quantification ∃xQ(x), where the domain consists of all real numbers? Solution: Because Q(x) is false for every real number x, the existential quantification of Q(x), which is ∃xQ(x), is false.

25. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 25 Exercise Let P(x) be the statement “x = x 2 .” If the universe of discourse consists of the integers, what are the truth values? P(0) P(1) P(2) P(-1) x P(x) x P(x)

26. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 26 Negating Quantified Statements x P(x)  x P(x) Example: Let P(x) be “x has taken a course in calculus.” The negation of this statement is “It is not the case that every student in the class has taken a course in calculus.” This is equivalent to “There is student in the class who has not taken a course in calculus.”

27. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 27 Negating Quantified Statements x P(x)  x P(x) “It is not the case that there is a student in this class who has taken a course in calculus.” This is equivalent to “Every student in this class has not taken calculus.”

28. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 28 Table 2. Negating Quantified Statements Negation Equivalent Statement When True? When False? x P(x) x P(x) x P(x) x P(x) For every x, P(x) is false. There is an x for which P(x) is false. There is an x for which P(x) is true. P(x) is true for every x.

29. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 29 Exercise Translate each of these statements into logical expressions using predicates, quantifiers, and logical connectives. (Let P(x)=“x is perfect” and F(x)=“x is your friend”) No one is perfect. Not everyone is perfect. All your friends are perfect. One of your friends is perfect. Everyone is your friend and is perfect. Not everybody is your friend or someone is not perfect.

30. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 30 Exercise Determine the truth value of each of these statements if the universe of discourse for all variables consists of all integers. n (n 2  0) n (n 2 = 2) n (n 2  n) n (n 2 < 0)

31. [email protected] Discrete Mathematics and Its Applications by Kenneth H. Rosen 31 Exercise Determine the truth value of each statement where the domain of discourse is the set of real numbers. xy (x 2 < y+1) xy (x 2 < y+1) x y (x 2 + y 2 = 13) xy (x 2 + y 2 = 13)