付费下载
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 金融科技公司数据分析师数据应用与分析能力绩效评定表
- 景区游客集中区域秩序维护指引方案
- 智能制造设备采购资金管理指引
- 电影制片财务管理与进度跟踪绩效表
- 关于新客户服务手册发放通知(6篇)
- 事业单位人事岗2026面试必练考题全真模拟试卷
- 小学英语教资面试结构化2026易错题题库及解析
- 游戏公司策划设计师用户反馈收集与体验优化绩效考核表
- 2026初中物理教资面试试讲历年真题题库及解析
- 2026小学数学教资面试结构化易错题题库及解析
- 蛋糕制作演讲课件
- 2026公安院校联考选拔考试(申论)历年参考题库含答案详解
- 2026年空气分离设备行业洞察报告及未来五至十年发展趋势报告
- 2027年普通内科副主任医师 副高职称面审答辩题库
- IT项目经理招聘笔试题及详细答案
- 7.1 珍视自由 课件(共18张)+内嵌视频
- 2025年甘肃(专升本)英语考试题库(含答案)
- 2026年麻醉、精神药物处方权培训考试试题(含答案)
- 2026年高考物理试题(山东卷)解析版
- 2026年煤矿水害防治培训课件(精讲版)
- 2026年6月英语四级真题(第3套)(附答案解析)
评论
0/150
提交评论