3 1 Predicates and Quanti ed Statements I Predicate calculus is the symbolic analysis of predicates and quanti ed statements Consider the sentence Rick Grimes was a sheri s deputy Rick Grimes is the subject and the phrase was a sheri s deputy is the predicate If we let P stand for was a sheri s deputy then we call P a predicate symbol Thus we would say P Rick Grimes gives us the above sentence De nition A a statement when speci c values are substituted for variables is a sentence that contains a nite number of variables and becomes The substituted in place of the variable of a predicate variable is the set of all values that may be Finding the Truth Values of a Predicate Example 1 Let P be the predicate 2 9 with domain the set Z of all integers Indicate which of the following are true and which are false 1 P 1 2 P 3 3 P 7 De nition Example 2 If P x is a predicate and x has domain D the all elements of D that make P x true when they are substituted for x of P x is the set of The truth set of P x is denoted x D P x Find the truth set for the predicate given in Example 1 How would this answer change if the domain changed to Q R Will this always be the case 1 One way to obtain statements from predicates is to add words that refer to quantities Examples include Quanti ers are The Universal Quanti er We call the symbol use this in the English language Consider the example denoting for all the How do we 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 the variable name The domain for this statement is N There are multiple ways that can be translated They include but are not limited to De nition Let 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 2 Example 3 Determine whether the following universal statement is true or false x D x 1 x 2 D Z the set of all positive integers 1 D 2 4 5 3 D Z The 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 Quanti er 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 the variable 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 3 De nition Let 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 4 Determine whether the following existential statement is true or false x D x2 1 2x 1 D 2 4 5 2 D Z the set of all negative integers 3 D Z Example 5 1 x Q 1 x Q Rewrite the following formal statements informally 2 x C such that x2 1 3 x R y R such that x y 1 Example 6 Rewrite the following informal statements formally 1 Some people have tattoos 2 No student likes having tests on Friday Universal Conditional Statements A is one of the form x if P x then Q x x R if x 2 0 then x2 0 Example 7 1 Rewrite the statement informally 2 Rewrite the statement formally Whenever any girl scout sells cookies outside Kroger she makes a small fortune 5 Equivalent Forms of Universal and Existential Statements 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 the variable x that make P x true x R if x Z then x Q x Z x Q Note that For example Example 8 Rewrite the following statement in two forms a x if b then and 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 9 Rewrite the following statement in two forms a x such that b x such that There is a telenovela that is funny and realistic 6 Implicit Quanti cation quanti cation occurs when a statement is missing the keywords to indicate universal or existential quanti cation For example consider Let us rewrite this explicitly The sum of even integers is even De nition Let 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 set of P x is in the truth set of Q x That is The notation means that P x and Q x have identical truth sets or equivalently x P x Q x x P x Q x Example 10 Which of the following are true for domain D R 1 x 2 x 1 2 x 2 x2 4 3 x2 4 x 2 4 x2 4 x 2 7