Predicates and Quantifiers PDF

statements that assert that a certain a telephone system: “If the directory database is opened, property proposition given in holds forasserts...

statements that assert that a certain a telephone system: “If the directory database is opened, property proposition given in holds forasserts the text that all objects that each ofof the a certain type nine 3 × 3 blocks of a 9 × 9 Sudoku puzzle contains ev- then the monitor is put in a closed state, if the system is statements that assert the existence of an object with a particular property. not in its initial state.” This specification is hard to under- ery number. are often found in mathematical assertions, in computer programs, and in system specifications. These statements are neither true nor false when the values of the variables are not specified. In 1.4 Predicates Predicates this and Quantifiers section, we will discuss the ways that propositions can be produced from such statements. Introduction The statement “x is greater than 3” has two parts. The first part, the variable x, is the subject Predicate is ofStatements Propositional involving the statement.logic, The second studied variables, part—the in Sections such predicate, 1.1–1.3, as “iscannot greateradequately than 3”—refers to atheproperty express meaningthatof all the subject statements of the in statement mathematics It can be denoted by propositional function P(x). can have. and We can in natural denote the language. statement For example,“x is greater suppose than that 3”weby know P that (x), This propositional P“xdenotes wherefunction > 3,” “x evaluates “Every computer = the predicate connected + yeither to“is greater to the than“x or F 3”+ 3,”T university once ax= andynetwork z,”isvariable. is the value has beenTheassigned functioning statement properly.” P (x) is to variable x, inalso said tocase which be the thevalue of the propositional statement P(x) becomes function P at x. Once a value has been assigned a proposition. toand the variable x, the statement P (x) becomes a proposition and has a truth value. Consider Examples 1 and 2. “computer x is under attack by an intruder,” EXAMPLE 1 Let P (x) denote the statement “x > 3.” What are the truth values of P (4) and P (2)? and Solution: We obtain the statement P (4) by setting x = 4 in the statement “x > 3.” Hence, “computer P (4), which x is functioning is the statement “4 > 3,” is true. properly,” However, P (2), which is the statement “2 > 3,” ▲ is false. are often found in mathematical assertions, in computer programs, and in system speci These statements are neither true nor false when the values of the variables are not spe this section, we will discuss the ways that propositions can be produced from such sta The statement “x is greater than 3” has two parts. The first part, the variable x, is th of the statement. The second part—the predicate, “is greater than 3”—refers to a prop  has a truth value. EXAMPLE 3 Let Q(x, y) denote the statement “x = y + 3.” What are the truth values of the propositions Q(1, 2) and Q(3, 0)? Solution: To obtain Q(1, 2), set x = 1 and y = 2 in the statement Q(x, y). Hence, Q(1, 2) is the statement “1 = 2 + 3,” which is false. The statement Q(3, 0) is the proposition “3 = 0 + 3,” ▲ which is true.  Solution: Because MATH1 is not connected to the CAMPUS1 network, we see that A(MATH1, CAMPUS1) is false. However, because MATH1 is connected to the CAMPUS2 network, we ▲ see that A(MATH1, CAMPUS2) is true. Similarly, we can let R(x, y, z) denote the statement `‘x + y = z.” When values are assigned to the variables x, y, and z, this statement has a truth value. EXAMPLE 5 What are the truth values of the propositions R(1, 2, 3) and R(0, 0, 1)? Solution: The proposition R(1, 2, 3) is obtained by setting x = 1, y = 2, and z = 3 in the statement R(x, y, z). We see that R(1, 2, 3) is the statement “1 + 2 = 3,” which is true. Also note that R(0, 0, 1), which is the statement “0 + 0 = 1,” is false. ▲ In general, a statement involving the n variables x1 , x2 ,... , xn can be denoted by P (x1 , x2 ,... , xn ). A statement of the form P (x1 , x2 ,... , xn ) is the value of the propositional function P at the n-tuple (x1 , x2 ,... , xn ), and P is also called an n-place predicate or a n-ary predicate. Propositional functions occur in computer programs, as Example 6 demonstrates. EXAMPLE 6 Consider the statement  A statement of the form P(x1 , x2 ,... , xn ) is the value of the propositional function P at the n-tuple (x1 , x2 ,... , xn ), and P is also called an n-place predicate or a n-ary predicate. Propositional functions occur in computer programs, as Example 6 demonstrates. EXAMPLE 6 Consider the statement if x > 0 then x := x + 1. When this statement is encountered in a program, the value of the variable x at that point in the execution of the program is inserted into P(x), which is “x > 0.” If P(x) is true for this value of x, the assignment statement x := x + 1 is executed, so the value of x is increased by 1. If P(x) is false for this value of x, the assignment statement is not executed, so the value of x is ▲ not changed. PRECONDITIONS AND POSTCONDITIONS Predicates are also used to establish the correctness of computer programs, that is, to show that computer programs always produce the  b) Q(Detroit, Michigan) c) Q(Massachusetts, Boston) d) Q(New York, New York) 4. State the value of x after the statement if P (x) then x := 1 Exercise: 11. is executed, where P (x) is the statement “x > 1,” if the value of x when this statement is reached is a) x = 0. b) x = 1. c) x = 2. 12. 5. Let P (x) be the statement “x spends more than five hours every weekday in class,” where the domain for x consists of all students. Express each of these quantifications in English. a) ∃xP (x) b) ∀xP (x) 13. c) ∃x ¬P (x) d) ∀x ¬P (x) 6. Let N (x) be the statement “x has visited North Dakota,” where the domain consists of the students in your school. Express each of these quantifications in English. 14.  THE UNIVERSAL QUANTIFIER Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), often just referred to as the domain. Such a statement is expressed Quantifier: Another way using universal to turn quantification. a propositional The universal quantification of P (x)function into isathe for a particular domain proposition isproposition via quantification. that asserts that P (x) is true for all values of x in this domain. Note that the domain specifies the possible values of the variable x. The meaning of the universal quantification ❖ Predicateofcalculus P (x) changes iswhenthe areatheofdomain. we change logic Thethat domaindeals must alwayswithbe specified when a universal quantifier is used; without it, the universal quantification of a statement is not defined. predicates and quantifiers. DEFINITION 1 The universal quantification of P (x) is the statement “P (x) for all values of x in the domain.” The notation ∀xP (x) denotes the universal quantification of P (x). Here ∀ is called the universal quantifier. We read ∀xP (x) as “for all xP (x)” or “for every xP (x).” An element for which P (x) is false is called a counterexample of ∀xP (x). The meaning of the universal quantifier is summarized in the first row of Table 1. We  at least one value of x in the domain. DEFINITION 2 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. 1.4 Predicates and Quantifiers 41 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 ∃xP (x) has no meaning. TABLE 1 statement Quantifiers. Besides the phrase “there exists,” we can also express existential quantification in many other Statement ways, such When as True? by using the words “for some,” “for at least When one,” or “there is.” The existential False? quantification ∃xP (x) is read as ∀xP (x) P (x) is true for every x. There is an x for which P (x) is false. “There is an x such that P (x),” ∃xP (x) Thereis is “There an x one at least for xwhich P (x) such that is true. P (x),” P (x) is false for every x. or XAMPLE 8 Let P (x) be the“For statement “x + 1 > x.” What is the truth value of the quantification ∀xP (x), some xP (x).”  The meaning of the existential quantifier is summarized in the second row of Table 1. We illustrate the use of the existential quantifier in Examples 14–16. EXAMPLE 14 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 quan- tification 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. We illustrate this observation in Example 15. EXAMPLE 15 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. ▲ Remember that the truth value of ∃xP (x) depends on the domain! Remark: Generally, an implicit assumption is made that all domains of discourse for quantifiers are nonempty. If the domain is empty, then ∃xQ(x) is false whenever Q(x) is a propositional  the domain. We illustrate this observation in Example 15. EXAMPLE 15 LetQ(x)denotethestatement“x = x + 1.”Whatisthetruthvalueofthequantification∃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. ▲ Remember that the truth value of ∃xP(x) depends on the domain! Remark: Generally, an implicit assumption is made that all domains of discourse for quantifiers are nonempty. If the domain is empty, then ∃xQ(x) is false whenever Q(x) is a propositional function because when the domain is empty, there can be no element x in the domain for which Q(x) is true. When all elements in the domain can be listed—say, x1, x2 ,... , xn— the existential quan- tification ∃xP(x) is the same as the disjunction  there is a student in your class who has this animal as a pet. 1 11. Let P (x) be the statement “x = x 2.” If the domain con- Exercise: he sists of the integers, what are these truth values? a) P (0) b) P (1) c) P (2) d) P (−1) e) ∃xP (x) f ) ∀xP (x) 12. Let Q(x) be the statement “x + 1 > 2x.” If the domain rs consists of all integers, what are these truth values? ts a) Q(0) b) Q(−1) c) Q(1) in d) ∃xQ(x) e) ∀xQ(x) f ) ∃x¬Q(x) g) ∀x¬Q(x) 13. Determine the truth value of each of these statements if the domain consists of all integers. ,” a) ∀n(n + 1 > n) b) ∃n(2n = 3n) ol. c) ∃n(n = −n) d) ∀n(3n ≤ 4n)