数理逻辑12.ppt
《数理逻辑12.ppt》由会员分享,可在线阅读,更多相关《数理逻辑12.ppt(624页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 数理逻辑Mathematical Logic 自我介绍v杨磊v生物数学教研室v外语学馆411v手机:15244775691vQQ:4064534562v运筹学v最优化方法v网络生物医学资源v生物信息学软件3v数理逻辑:离散数学的分支v离散数学:计算机科学的核心基础课程,它以离散量为研究对象。v数学分析:(微积分)以连续函数为主要研究对象,属于连续型数学。4v计算机软件和硬件都属于离散结构,必然大量使用离散数学,只能处理离散的或离散化了的数量关系v(0,1)v离散数学在计算机领域有着广泛的应用v数据结构v操作系统v编译原理v人工智能v程序设计5离散数学数理逻辑集合论图论代数结构组合数学6数理逻
2、辑 Mathematical Logic v数理:Mathematical 数学理论v逻辑:Logic7什么是逻辑v逻辑通常指人们思考问题,从某些已知条件出发推出合理的结论的规律。v逻辑学:一门研究思维形式及思维规律的科学。v逻辑学主要研究对象:推理形式。8逻辑学现代逻辑古典逻辑传统逻辑数理逻辑9什么是数理逻辑v字面含义:数学理论的逻辑。v广义理解:用数学方法研究演绎规律的学科。v狭义理解:用数学方法研究数学中演绎规律的学科。v研究对象:推理过程的正确性标准。10什么是数理逻辑v更深入的理解:就是采用数学的方法来研究思维形式的逻辑结构及其规律的一门科学。v所谓数学的方法就是用一套符号(即人工符
3、号语言)的方法。11数理逻辑与传统逻辑的区别v1.使用一整套符号语言,从而简化了推理形式。v2.借助人工符号语言,使整个推理形式化。v3.具有系统性。12数理逻辑的历史v数理逻辑的创始人:莱布尼兹 贡献:把数学引入形式逻辑;v布尔 贡献:1847年实现了命题演算;v弗雷格v贡献:1879年建立了第一个谓词演算系统;13v皮尔斯 贡献:在著作中引入了逻辑符号。现代数理逻辑最基本的理论基础逐步形成,成为一门独立的学科14课程教材vKenneth H.Rosen著的Discrete Mathematics and Its Applicationsv离散数学领域的经典教材,全世界几乎所有知名的院校都曾
4、使用.v离散数学 左孝凌 刘永才 上海科学技术文献出版社。v国内经典著作中内容最全的一本。1516学习本课程的目的v很多专业课的先修课 离散数学后继课程有:数据结构、人工智能、数据库、操作系统、计算机网络等。v培养学生抽象的思维和逻辑推理能力和创新能力v离散数学可以帮助学生提高数学素质,提高创造力v专业核心课程,考研、计算机等级考试、程序员考试的考试科目17学习本课程的方法v课程特点 内容杂,概念多,定理多,很抽象,给学习带来一定难度v学习方法 强调:逻辑性、抽象性 注重:概念、方法与应用18本课程主要内容v第一章 逻辑、集合和函数v命题逻辑、谓词逻辑、逻辑等价v集合、集合运算v函数、函数增长
5、19v第二章 算法、整数和矩阵v算法、搜索算法v整数和除法(素数、最大公约数、最小公倍数、模运算等)、整数和算法v矩阵v第三章 数学推理v证明方法、数学归纳法、递归算法等v第四章 关系v关系及其性质、n元关系及应用、关系的表示20第一章 逻辑、集合和函数Chapter 1 Logic、set and function21命题逻辑Propositional Logic22命题(Proposition)vDefinition:A declarative sentence that is either true or false,but not bothv定义:命题是一个或真或假的陈述句,但不能既真
6、又假vNote:陈述句 或者真 或者假23命题满足的条件v(1)命题的语句形式:陈述句v(2)非命题语句:疑问句、命令句、感叹句、非命题陈述句(悖论语句)v(3)命题所表述的内容可决定是真还是假,不能不真又不假,也不能又真又假。24命题的真值v命题具有两种可能的取值(又称真值),为真或为假,并且只能取其一。v命题真值(Truth Values)的表示:v 真:T、1;假:F、0v因为命题只有两种取值,所以这样的命题逻辑称为二值逻辑。25命题语句真值确定的几点说明:v1、时间性v2、区域性v3、标准性v注意:注意:严格地说,含有可变时间、地点、人物的语句不是命题,除非假定了一个确定的时间、地点、
7、人物。26Example(1)The sun is bigger than earth.(太阳比地球大)-Proposition (TRUE)(2)The integer 9 is prime.(整数9是素数)-Proposition (FALSE)(3)This statement is false.(这个陈述是错误的)-Not a proposition27(4)Please open the book.(请打开课本)-Not a proposition(5)What time is it?(现在几点了?)-Not a proposition(6)x+1=2.-Not a proposit
8、ion28下列句子中那些是命题v(1)2 是无理数.v(2)2+5 8.v(3)x+5 3.v(4)你有铅笔吗?v(5)这只兔子跑得真快呀!v(6)请不要讲话!v(7)我正在说谎话.v(3)(7)not a proposition29命题表示法命题常用字母表示。习惯上用来表示命题的字母是p、q、r、s 30命题的分类v简单命题v复合命题31简单命题 简单命题又称原子命题,由最简单的陈述句构成的命题(该句不能再分解成更简单的句子)。例:2是个素数32复合命题复合命题又称分子命题,由若干个原子命题构成的命题。例:ab、bc、ac,是由三个原子命题构成的复合命题。33逻辑运算的概念 命题可以通过逻辑
9、联结词(逻辑运算)构成新的命题-复合命题.复合命题的真值依赖于其中简单命题的真值 逻辑运算符也称为联结词 体现了复合命题中各个原子命题之间的运算关系34逻辑运算符vNegation (NOT)否定vConjunction (AND)合取vDisjunction (OR)析取vExclusive or (XOR)异或vImplication (if then)蕴涵35否定 Negation(NOT)v定义:令p为一命题,则语句“不是p所说的情形。”是另一个命题,称为p的否定。v用p:not p,表示,读作:“非p”v例:p:Today is Tuesday.今天是星期二 p:Today is n
10、ot Tuesday今天不是星期二 不能说今天是星期一、星期三等36v例:找出命题“昨天张三看球赛了”的否定vp:昨天张三看球赛了。vp:并非昨天张三看球赛了。vp:昨天张三没有看球赛。37命题之否定的真值表ppTFFT38合取 Conjunction(AND)v定义:令p和q为命题,用pq表示的命题“p而且q”是这样的一个命题:当p和q均为真时它成真,否则为假。命题pq称为p和q的合取。39vp:小王能唱歌 q:小王能跳舞v合取为:vpq:小王能歌善舞vTrue if and only if both p and q are true.v当且仅当p和q都为真时,pq 才为真40命题合取的真值
11、表pqpqTTTTFFFTFFFF41析取 Disjunction(OR)v定义:令p和q为命题,用pq表示的命题“p或q”是这样的一个命题:它的真值在p和q均为假时为假,否则成真。命题pq称为p和q的析取。v同或 异或42析取的真值表pqpqTTTTFTFTTFFF43v析取中包含两种情况:v同或:两个命题之一成真或两者均成真时,析取成真v异或:两个命题之一成真,析取成真;两者均成真时或两者均假时,析取成假44异或Exclusive or(XOR)v定义:令p和q为命题,p和q的异或,用 表示.vTrue if and only if exactly one of p and q is tr
12、ue.v(当p和q中恰有一个成真时它成真,否则它为假)vp:米卢在西安 q:米卢在北京。v :米卢在西安或者米卢在北京。45v异或表示两个命题不可能同时都成立。v 命题“第一节课上数学或者上英语。”可以解释为:“第一节课上数学而没有上英语或者第一节课上英语而没有上数学。46异或真值表pqTTFTFTFTTFFF47蕴含Implicationv令p和q为命题,蕴含pq是这样一个命题:在p成真而q为假时它为假,否则成真。其中p称为假设(前项、前提),q称为结论(或后果)48v例:如果缺少水分,植物就会死亡vp:缺少水分vq:植物会死亡vpq:如果缺少水分,植物就会死亡v缺少水分是前提条件vFals
13、e if and only if p is true and q is false.v当且仅当p为真且q为假时,pq为假49蕴含真值表pqpqTTTTFFFTTFFT50蕴含术语v“如果p,那么q”v“p是q的充分条件”v“p蕴含q”“q如果p”v“如果p,q”“q每当p”v“p仅当q”“q是p的必要条件”51vv例:令:P:天气好。Q:我去公园。v1.如果天气好,我就去公园。(充分)v2.只要天气好,我就去公园。(充分)v3.仅当天气好,我才去公园。(必要)v4.只有天气好,我才去公园。(必要)v命题1、2 写成:PQ v命题3、4 写成:QP52逆蕴含Converse of an Impl
14、icationv定义:命题qp称为pq的逆蕴含vFor example:Implication:蕴含If it is raining now,then there are clouds outside.如果现在在下雨,那么外面有很多乌云Converse:逆蕴含If there are clouds outside,then it is raining now.如果外面有很多乌云,那么现在在下雨53逆否命题Contrapositive of an Implication v定义(倒置命题):pq的逆否命题是命题qpvFor exampleImplication:蕴含If it is rainin
15、g now,then there are clouds outside.如果现在在下雨,那么外面有乌云Contrapositive:逆否If there are not clouds outside,then it is not raining now.如果外面没有乌云,那么现在没下雨vNote:pq 等价于q p54双蕴含Biconditionalv定义:令p和q为命题,双蕴含 是这样一个命题:其真值只有在p和q有同样真值时为真,否则为假。v双蕴含恰在pq和qp均为真时为真。55双蕴含术语v“p当且仅当q”v“p是q的充分必要条件”v“如果p,那么q;反之亦然。”56双蕴含真值表pqTTTT
16、FFFTFFFT57Precedence of Logical Operators逻辑运算符的优先级vPrecedence:v优先级优先级:vFor example:pqr means(pq)r,not p(qr)pqr means(pq)r58v命题是一个或真或假的陈述句,但不能既真又假vNote:陈述句 或者真 或者假v真:T、1;假:F、0v简单命题v复合命题v逻辑运算符v否定:令p为一命题,则语句“不是p所说的情形。”是另一个命题,称为p的否定vp:not p,表示,读作:“非p”59v合取:当p和q均为真时它成真,否则为假。命题pq称为p和q的合取v析取:p和q均为假时为假,否则成真
17、。命题pq称为p和q的析取v异或:当p和q中恰有一个成真时它成真,否则它为假v蕴含:在p成真而q为假时它为假,否则成真。其中p称为假设(前项、前提),q称为结论(或后果)60v逆蕴含:命题qp称为pq的逆蕴含v逆否命题:pq的逆否命题是命题qpv双蕴含:恰在pq和qp均为真时为真v优先级:61练习题vp:气温在零度以下vq:正在下雪(1)气温在零度以下且正在下雪 pq(2)气温在零度以下但不在下雪 pq62(3)气温不在零度以下,也不在下雪 pq(4)如果气温在零度以下,那么就在下雪 pq(5)气温在零度以下是下雪的充分必要条件 pq63v侦探调查了罪案的四位证人。从证人的话侦探得出的结论是:
18、如果男管家说的是真话,厨师说的也是真话;厨师和园丁说的不可能都是真话;园丁和杂役不可能都说慌;如果杂役说的是真话,那么厨师说的就是假话。vg:管家说的是真话;c:厨师说的是真话;vy:园丁说的是真话;z:杂役说的是真话;gc (cy)yz zc64命题的符号化v目的:把自然语言的句子翻译成由命题变量和逻辑联结词组成的表达式。v1.首先要明确给定命题的含义。v2.对于复合命题,找联结词,用联结词断句,分解出各个原子命题。v3.设原子命题符号,并用逻辑联结词联结原子命题符号,构成给定命题的符号表达式。65v说离散数学无用且枯燥无味是不对的。P:离散数学是有用的。Q:离散数学是枯燥无味的。该命题可写
19、成:(PQ)66v人不犯我,我不犯人;人若犯我,我必犯人。P:人犯我 Q:我犯人。该命题可写成:(PQ)(PQ)或写成:PQ67v除非你已满16周岁,否则只要你身高不足4英尺就不能玩过山车vp:你能玩过山车。vr:你身高不足4英尺。vs:你已满16周岁。v(sr)p68必要条件和充分条件v只有 p才 q 必要条件vqpv只要 p 就 q 充分条件vpq69ExamplevYou can access the Internet from campus only if you are a computer science major or you are not a freshman(只有你主修计
20、算机科学或不是新生,才可以从校园内访问因特网)a:you can access the Internet from campus(你可以从校内网访问因特网)c:you are a computer science major(你主修计算机科学)f:you are a freshman(你是个新生)a(cf)70vp:你的车速超过每小时65英里vq:你接到一张超速罚单v1)你的车速没有超过每小时65英里vpv2)你的车速超过每小时65英里,但没接到超速罚单v pq71v3)你的车速若超过每小时65英里,将接到一张超速罚单vpqv4)你的车速不超过每小时65英里,就不会接到超速罚单vpqv5)你车
21、速超过每小时65英里足以接到超速罚单vpq72v6)你接到一张超速罚单,但你的车速没超过每小时65英里vqpv7)只要你接到一张超速罚单,你的车速就超过每小时65英里vqp73将下列命题符号化将下列命题符号化(1)王晓既用功又聪明.(2)王晓不仅聪明,而且用功.(3)王晓虽然聪明,但不用功.令 p:王晓用功,q:王晓聪明 (1)pq (2)pq (3)qp74(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.令 r:张辉是三好学生,s:王丽是三好学生(4)rs.(5)令 t:张辉与王丽是同学,t 是简单命题.75将下列命题符号化将下列命题符号化v(1)2或4是素数.v(2)2或3是素数.v(
22、3)4或6是素数.vp:2是素数,q:3是素数,r:4是素数,s:6是素数vpr vpqvrs76v小元元只能拿一个苹果或一个梨vp:小元元拿一个苹果,q:小元元拿一个梨v王晓红生于1975年或1976vp:王晓红生于1975年,q:王晓红生于1976年77例例 设 p:天冷,q:小王穿羽绒服 将下列命题符号化 (1)只要天冷,小王就穿羽绒服.(2)因为天冷,所以小王穿羽绒服.(3)若小王不穿羽绒服,则天不冷.(4)只有天冷,小王才穿羽绒服.(5)除非天冷,小王才穿羽绒服.(6)除非小王穿羽绒服,否则天不冷.pqpqpqpqqp qp78例例 求下列复合命题的真值 (1)2+2 4 当且仅当
23、3+3 6.(2)2+2 4 当且仅当 3 是偶数.(3)2+2 4 当且仅当 太阳从东方升起.(4)2+2 4 当且仅当 美国位于非洲.(5)2+2 4 当且仅当3不是奇数.(6)两圆面积相等当且仅当它们的半径相等.它们的真值分别为 1,0,1,0,1,179布尔检索v定义:运用布尔逻辑运算符对检索词进行逻辑组配,表达两个概念之间的逻辑关系的检索。v与(AND)v或(OR)v非(NOT)80v与(AND):用于匹配包含两个检索项的记录v目的:提高查准率v或(OR):用于匹配两个检索项之一或两项均匹配的记录v目的:提高查全率v非(NOT):用于排除某个特定的检索项v目的:提高查准率818283
24、逻辑运算和位运算v计算机用字位表示信息,每个字位有两个可能的值,即0或1。v字位、字节、英文字母、汉字v1byte=8bitsv一个英文字母一个字节,一个汉字两个字节;84vBit意为位或比特,是计算机运算的基础;vByte意为“字节”,是计算机文件大小的基本计算单位;v1字节=8位,1KB=1024字节,MG=1024KB,v1GB=1024MB,1TB=1024GB;85字位运算对应于逻辑联结词vAND:vOR:vXOR:v信息一般用位串来表示,也就是0和1的序列表示。v对位串的运算即可用来处理信息。86字位运算符的真值表xyxyxyx y0000001101101011111087v在长
25、度相同的两个位串上定义按位运算(每个字位分别运算):vBitwise(按位)ORvBitwise(按位)ANDvBitwise(按位)XOR88求位串01 1011 0110和位串11 0001 1101的按位OR、按位AND和按位XOR。01 1011 011011 0001 110111 1011 1111 按位OR01 0001 0100 按位AND10 1010 1011 按位XOR89模糊逻辑v定义:命题的真值是介于0和1之间的数。v1为真值的命题为真v0为真值的命题为假v“张三是幸福的”真值为0.8;v“李四是幸福的”真值为0.4;v命题的否定:1减去该命题的真值。v“张三不幸福”
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数理逻辑 12
限制150内