Toán học - Chapter 1 - Part II: Predicate logic

The Foundations: Logic and ProofsChapter 1, Part II: Predicate LogicWith Question/Answer AnimationsCopyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.SummaryPredicate Logic (First-Order Logic (FOL), Predicate Calculus)The Language of QuantifiersLogical EquivalencesNested QuantifiersTranslation from Predicate Logic to EnglishTranslation from English to Predicate LogicPredicates and QuantifiersSection 1.4Section SummaryPredicates VariablesQuantifiersUniversal QuantifierExistential QuantifierNegating QuantifiersDe Morgan’s Laws for QuantifiersTranslating English to LogicLogic Programming (optional)Propositional Logic Not EnoughIf we have: “All men are mortal.”“Socrates is a man.”Does it follow that “Socrates is mortal?”Can’t be represented in propositional logic. Need a language that talks about objects, their properties, and their relations. Later we’ll see how to draw inferences. Introducing Predicate LogicPredicate logic uses the following new features:Variables: x, y, zPredicates: P(x), M(x)Quantifiers (to be covered in a few slides):Propositional functions are a generalization of propositions. They contain variables and a predicate, e.g., P(x)Variables can be replaced by elements from their domain.Propositional FunctionsPropositional functions become propositions (and have truth values) when their variables are each replaced by a value from the domain (or bound by a quantifier, as we will see later).The statement P(x) is said to be the value of the propositional function P at x. For example, let P(x) denote “x > 0” and the domain be the integers. Then:P(-3) is false.P(0) is false.P(3) is true. Often the domain is denoted by U. So in this example U is the integers.Examples of Propositional FunctionsLet “x + y = z” be denoted by R(x, y, z) and U (for all three variables) be the integers. Find these truth values: R(2,-1,5)Solution: FR(3,4,7)Solution: TR(x, 3, z)Solution: Not a PropositionNow let “x - y = z” be denoted by Q(x, y, z), with U as the integers. Find these truth values:Q(2,-1,3) Solution: TQ(3,4,7) Solution: F Q(x, 3, z) Solution: Not a PropositionCompound ExpressionsConnectives from propositional logic carry over to predicate logic. If P(x) denotes “x > 0,” find these truth values:P(3) ∨ P(-1) Solution: TP(3) ∧ P(-1) Solution: FP(3) → P(-1) Solution: FP(3) → ¬P(-1) Solution: TExpressions with variables are not propositions and therefore do not have truth values. For example,P(3) ∧ P(y) P(x) → P(y) When used with quantifiers (to be introduced next), these expressions (propositional functions) become propositions.QuantifiersWe need quantifiers to express the meaning of English words including all and some:“All men are Mortal.”“Some cats do not have fur.”The two most important quantifiers are:Universal Quantifier, “For all,” symbol: Existential Quantifier, “There exists,” symbol: We write as in x P(x) and x P(x).x P(x) asserts P(x) is true for every x in the domain.x P(x) asserts P(x) is true for some x in the domain.The quantifiers are said to bind the variable x in these expressions. Charles Peirce (1839-1914)Universal Quantifierx P(x) is read as “For all x, P(x)” or “For every x, P(x)”Examples: If P(x) denotes “x > 0” and U is the integers, then x P(x) is false.If P(x) denotes “x > 0” and U is the positive integers, then x P(x) is true.If P(x) denotes “x is even” and U is the integers, then  x P(x) is false.Existential Quantifierx P(x) is read as “For some x, P(x)”, or as “There is an x such that P(x),” or “For at least one x, P(x).” Examples: If P(x) denotes “x > 0” and U is the integers, then x P(x) is true. It is also true if U is the positive integers.If P(x) denotes “x 0,” then !x P(x) is false.The uniqueness quantifier is not really needed as the restriction that there is a unique x such that P(x) can be expressed as: x (P(x) ∧y (P(y) → y =x))Thinking about QuantifiersWhen the domain of discourse is finite, we can think of quantification as looping through the elements of the domain.To evaluate x P(x) loop through all x in the domain. If at every step P(x) is true, then x P(x) is true. If at a step P(x) is false, then x P(x) is false and the loop terminates. To evaluate x P(x) loop through all x in the domain. If at some step, P(x) is true, then x P(x) is true and the loop terminates. If the loop ends without finding an x for which P(x) is true, then x P(x) is false.Even if the domains are infinite, we can still think of the quantifiers this fashion, but the loops will not terminate in some cases.Properties of QuantifiersThe truth value of x P(x) and  x P(x) depend on both the propositional function P(x) and on the domain U. Examples:If U is the positive integers and P(x) is the statement “x 2”, then both x P(x) and  x P(x) are true. But if P(x) is the statement “x 0)∧ (y > 0)→ (x + y > 0)) where the domain of both variables consists of all integersTranslating English into Logical Expressions ExampleExample: Use quantifiers to express the statement “There is a woman who has taken a flight on every airline in the world.”Solution:Let P(w,f) be “w has taken f ” and Q(f,a) be “f is a flight on a .” The domain of w is all women, the domain of f is all flights, and the domain of a is all airlines.Then the statement can be expressed as: w a f (P(w,f ) ∧ Q(f,a))Calculus in Logic (optional)Example: Use quantifiers to express the definition of the limit of a real-valued function f(x) of a real variable x at a point a in its domain.Solution: Recall the definition of the statement is “For every real number ε > 0, there exists a real number δ > 0 such that |f(x) – L| 0, such that for every real number δ > 0, there exists a real number x such that 0 < | x – a | < δ and |f(x) – L | ≥ ε .Some Questions about Quantifiers (optional)Can you switch the order of quantifiers? Is this a valid equivalence? Solution: Yes! The left and the right side will always have the same truth value. The order in which x and y are picked does not matter.Is this a valid equivalence? Solution: No! The left and the right side may have different truth values for some propositional functions for P. Try “x + y = 0” for P(x,y) with U being the integers. The order in which the values of x and y are picked does matter.Can you distribute quantifiers over logical connectives? Is this a valid equivalence? Solution: Yes! The left and the right side will always have the same truth value no matter what propositional functions are denoted by P(x) and Q(x).Is this a valid equivalence? Solution: No! The left and the right side may have different truth values. Pick “x is a fish” for P(x) and “x has scales” for Q(x) with the domain of discourse being all animals. Then the left side is false, because there are some fish that do not have scales. But the right side is true since not all animals are fish.