离散数学及其应用7e chapter1p_第1页
离散数学及其应用7e chapter1p_第2页
离散数学及其应用7e chapter1p_第3页
离散数学及其应用7e chapter1p_第4页
离散数学及其应用7e chapter1p_第5页
免费预览已结束,剩余52页可下载查看

付费下载

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、The Foundations: Logic and ProofsChapter 1, Part II: Predicate LogicWith Question/Answer AnimationsSummaryPredicate Logic (First-Order Logic (FOL), Predicate Calculus)The Language of QuantifiersLogical EquivalencesNested QuantifiersTranslation from Predicate Logic to EnglishTranslation from English

2、to Predicate LogicPredicates and QuantifiersSection 1.4Section SummaryPredicates VariablesQuantifiersUniversal QuantifierExistential QuantifierNegating QuantifiersDe Morgans Laws for QuantifiersTranslating English to LogicLogic Programming (optional)Propositional Logic Not EnoughIf we have: “All men

3、 are mortal.”“Socrates is a man.”Does it follow that “Socrates is mortal?”Cant be represented in propositional logic. Need a language that talks about objects, their properties, and their relations. Later well see how to draw inferences. Introducing Predicate LogicPredicate logic uses the following

4、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 FunctionsPropositiona

5、l functions e 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

6、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

7、: 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

8、 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 quantifie

9、rs (to be introduced next), these expressions (propositional functions) e 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,

10、” 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)Univer

11、sal Quantifierx 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.Existe

12、ntial Quantifierx 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 unique

13、ness 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)

14、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

15、 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

16、function P(x) and on the domain U. Examples:If U is the positive integers and P(x) is the statement “x 2”, then x P(x) is true, but x P(x) is false. If U is the negative 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)

17、 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 flig

18、ht 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 re

19、al 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| whenever 0 |x a| 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

20、 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,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论