**Unformatted text preview:**

3.1 Predicates and Quantified Statements IPredicate calculus is the symbolic analysis of predicates and quantified statements.Consider the sentence“Rick Grimes was a sheriff’s deputy.”“Rick Grimes” is the subject and the phrase “was a sheriff’s deputy” is the predicate. If welet P stand for “was a sheriff’s deputy,” then we call P a predicate symbol. Thus, wewould say P (Rick Grimes) gives us the above sentence.DefinitionA is a sentence that contains a finite number of variables and becomesa statement when specific values are substituted for variables.The of a predicate variable is the set of all values that may besubstituted in place of the variable.Finding the Truth Values of a PredicateExample 1Let P (♥) be the predicate ♥2= 9 with domain the set Z of all integers. Indicate which ofthe following are true, and which are false.1. P (1)2. P (−3)3. P (7)DefinitionIf P (x) is a predicate and x has domain D, the of P (x) is the set ofall elements of D that make P (x) true when they are substituted for x.The truth set of P (x) is denoted {x ∈ D|P (x)}Example 2Find the truth set for the predicate given in Example 1. How would this answer change ifthe domain changed to Q? R? Will this always be the case?1One way to obtain statements from predicates is to add . Quantifiers arewords that refer to quantities. Examples include:• •The Universal Quantifier: ∀We call the symbol denoting “for all” the . How do weuse this in the English language? Consider the example:“All natural numbers are strictly positive.”We can equivalently say this as,“∀ x ∈ N, x > 0”Notice that the domain of the predicate variable is generally indicated between ∀ and thevariable name. The domain for this statement is N.There are multiple ways that ∀ can be translated. They include, but are not limited to:•••••DefinitionLet Q(x) be a predicate and D be the domain of x.A is a statement of the form∀x ∈ D, Q(x).When is a universal statement true? False?A value for x for which Q(x) is false is called a .2Example 3Determine whether the following universal statement is true or false.∀x ∈ D,1x≤ x1. D = {2, 4, 5}2. D = Z+, the set of all positive integers.3. D = ZThe method we used to prove that Example 3.1 is a true universal statement is called.Can you think of pros and cons of using this method?The Existential Quantifier: ∃We call the symbol denoting “there exists,” the .How do we use this in the English language? Consider the example:“There is at least one girl in this class”We can equivalently say this as,“∃ x ∈ {students in Math 2534} such that x is a girl.”Notice that the domain of the predicate variable is generally indicated between ∃ and thevariable name. Here we get that our domain is “students in Math 2534.”Consider the statement: “There are some girls in this class.” How would you translate this?There are multiple ways that ∃ can be translated. They include, but are not limited to:••••••3DefinitionLet Q(x) be a predicate and D be the domain of x.An is a statement of the form∃x ∈ D such that Q(x).When is an existential statement true? False?Example 4Determine whether the following existential statement is true or false.∃x ∈ D, x2+ 1 = 2x1. D = {2, 4, 5}2. D = Z−, the set of all negative integers.3. D = ZExample 5Rewrite the following formal statements informally.1. ∀x ∈ Q,1x∈ Q2. ∃x ∈ C such that x2= −13. ∀x ∈ R, ∃y ∈ R such that x + y = 1Example 6Rewrite the following informal statements, formally.1. Some people have tattoos.2. No student likes having tests on Friday.Universal Conditional StatementsA is one of the form∀x, if P (x), then Q(x).Example 71. Rewrite the statement∀x ∈ R, if x − 2 > 0, then x2> 0informally.2. Rewrite the statementWhenever any girl scout sells cookies outside Kroger, she makes a small fortune.formally.5Equivalent Forms of Universal and Existential StatementsNote that∀x ∈ U, if P (x), then Q(x) ≡ ∀x ∈ D, Q(x),where we narrow U to the domain D, where D is the domain consisting of all values of thevariable x that make P (x) true.For example,[∀x ∈ R, if x ∈ Z, then x ∈ Q] ≡ [∀x ∈ Z, x ∈ Q].Example 8Rewrite the following statement in two forms:(a) ∀x, if , then and(b) ∀ x, .All zombies are dead.Similarly, we can rewrite existential statements. Note that[∃x such that P (x) and Q(x)] ≡ [∃x ∈ D such that Q(x)],where D is the set of all x for which P (x) is true.Example 9Rewrite the following statement in two forms:(a) ∃x such that ∧ .(b) ∃ x such that .There is a telenovela that is funny and realistic.6Implicit Quantificationquantification occurs when a statement is missing the keywords to indicateuniversal or existential quantification. For example, considerThe sum of even integers is even.Let us rewrite this explicitly.DefinitionLet P (x) and Q(x) be predicates and suppose the common domain of x is D.• The notation means that every element in the truth setof P (x) is in the truth set of Q(x). That is,∀x, P (x) → Q(x)• The notation means that P (x) and Q(x) haveidentical truth sets, or, equivalently,∀x, P (x) ↔ Q(x).Example 10Which of the following are true for domain D = R?1. x > 2 =⇒ x > 12. x > 2 =⇒ x2> 43. x2> 4 =⇒ x > 24. x2> 4 ⇐⇒ |x| >

View Full Document