离散数学英文讲义：1-3 Predicates and Quantifiers.pptVIP

* Occurrences of variables that are not free are bound. Test your understanding: Which (if any) variables are free in ?x ?P(x) ??x ?P(x) ?yQ(x) ?xP(b) (NB, b is a constant) ?x(?y R(x,y)) * Occurrences of variables that are not free are bound. Check your understanding: Which (if any) variables are free in ?x ?P(x) [no free variables] ??x ?P(x) [no free variables] ?yQ(x) [x is free] ?xP(b) (NB, b is a constant) [no free var.] ?x(?y R(x,y)) [no free variables] * Negations ?x P(x) is the statement “Every student in the class has taken a course in calculus.” ??x P(x) ? ?x ? P(x) It is the statement “There is a student in the class has not taken a course in calculus.” * Negations ?x P(x) is the statement “There is a student in the class has taken a course in calculus.” ? ?x P(x) ? ? x ? P(x) It is the statement “Every student in the class has not taken a course in calculus.” * Negating Quantifiers ? ?x P(x) ? ? x ? P(x) When is Negation Ture? For every x, P(x) is false. When False? There is an x for which P(x) is true. ??x P(x) ? ?x ? P(x) When is Negation Ture? There is an x for which P(x) is false. When False? P(x) is true for every x. * * De Morgan’s laws ?(p(x1)? p(x2 ) … ? p(xn)) = ?p(x1 ) ? ? p(x2 )… ? ? p(xn) ?(p(x1) ? p(x2 ) … ? p(xn)) = ? p(x1 ) ? ? p(x2 )… ? ? p(xn) * Example 10 What are the negations of the statements “There is an honest politician” and “All Americans eats cheeseburgers?” Solution: Let H(x) denote “x is honest.” “There is an honest politician.” ?x H(x) ? ?x H(x) ? x ? H(x) Let C(x) denote “x eats cheeseburgers.” “All Americans eats cheeseburgers?” ?x C(x) ? ?x C(x) ?x ? C(x) * Example 11 Negations of the statements ?x ( x^2 x) and ?x ( x^2 = 2 ) ? ?x ( x^2 x) ? ?x ? ( x^2 x) ? ?x ( x^2 = x) ? ?x ( x^2 = 2 ) ? ?x ? ( x^2 = 2 ) ? ?x ( x^2 != 2 ) * Translation * Example 12 Express the statement “Every student in this class has studied calculus” using predicates and quanti