东南大学计算机科学与工程学院周德宇dzhouseueducn.ppt

《东南大学计算机科学与工程学院周德宇dzhouseueducn.ppt》由会员分享，可在线阅读，更多相关《东南大学计算机科学与工程学院周德宇dzhouseueducn.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1东南大学计算机科学与工程学院周德宇dzhouseueducn Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望2朱朱 棣棣 朱高炽朱高炽 朱瞻基朱瞻基 朱祁镇朱祁镇 朱祁钰朱祁钰 朱见深朱见深 朱佑樘朱佑樘 朱厚照朱厚照 朱厚熜朱厚熜 朱载垕朱载垕 朱翊钧朱翊钧 朱常洛朱常洛 朱由校朱由校 朱由检朱由检 问题：从这些名字中你能告诉我什么？问题：从这些名字中你能告诉我什么？3序言一：什么是离散数学序言一：什么是离散数学q研究离散量的结构及相互关系的数学科学v离散结构

2、：集合、关系、图等 离散量是指分散开来的、不存在中间值的量 q研究对象:有限或可数个元素v自然数、整数，真假值，有限节点等q计算机技术的支撑科学：计算机只能处理离散的或离散化了的数量关系4序言二：与其他专业课关系序言二：与其他专业课关系数据结构基础数据结构基础离散结构离散结构数据库原理数据库原理软件工程软件工程操作系统操作系统编译原理编译原理人工智能人工智能可计算性理论可计算性理论5课程安排课程安排数理逻辑数理逻辑集合论集合论代数结构代数结构图论图论8周周4周周4周周8周周6课程安排课程安排数理逻辑数理逻辑集合论集合论代数结构代数结构图论图论7数理逻辑数理逻辑q逻辑学分类v辩证逻辑：是研究事物

3、发展的客观规律v形式逻辑：是研究思维的概念、判断和推理的问题v数理逻辑q数理逻辑v数学方法研究形式逻辑的一门科学v一般认为由莱布尼茨（Leibniz）率先提出v最基本组成部分：命题演算、谓词演算v应用：逻辑电路、自动控制、人工智能等8引语引语两栖动物数量的下降清楚地说明全球空气和水质的污染。在加州Yosemite国家公园对于两栖动物所进行的两次研究证实了我的结论。1915年公园中有7种两栖动物，每种的数量都很丰富。然而到了1992年在公园中只观察到4种两栖动物，并且每种动物的数量都显著下降。Yosemite公园两栖动物数量的下降曾被归因于始于1920年的在公园水域引入鲑鱼的行为（我们知道鲑鱼捕

4、食两栖动物的卵）。但鲑鱼的引入不会是但鲑鱼的引入不会是Yosemite两栖两栖动物数量下降的真正原因，因为它并不能解释全动物数量下降的真正原因，因为它并不能解释全球范围的数量下降。球范围的数量下降。9问题分析问题分析逻辑主线：全球空气和水质的污染导致了全球两栖动物数量的下降错误逻辑：鲑鱼不能解释全球两栖动物下降所以不能解释公园两栖动物数量下降。存在问题：1.在加洲国家公园对两栖动物进行的研究不能推理除全球范围的两栖动物的数量下降。只能推理除公园里的两栖动物下降。2.公园内两栖动物数量的下降并不能排除是由鲑鱼引入导致的，逻辑推理中不可以随意的将影响因素扩大化或缩小化。3.最大得逻辑错误，转化逻辑

5、主体，试图以全球两栖动物数量下降的事实证明鲑鱼不是yosemite公园里两栖动物下降得原因。两者间完全没有逻辑联系。10q主要内容（主要内容（8周的时间）周的时间）l命题逻辑基本概念命题逻辑基本概念l命题逻辑等值演算命题逻辑等值演算l命题逻辑推理理论命题逻辑推理理论l一阶逻辑基本概念一阶逻辑基本概念l一阶逻辑等值演算与推理一阶逻辑等值演算与推理第一部分第一部分 数理逻辑数理逻辑11第第1章命题逻辑基本概念章命题逻辑基本概念命题与联结词命题与联结词命题及其分类命题及其分类联结词与复合命题联结词与复合命题命题公式及其赋值命题公式及其赋值12学习要点学习要点1、命题的概念：定义、逻辑值、命题的概念：

6、定义、逻辑值、符号化表示符号化表示2、从简单命题到复合命题：、从简单命题到复合命题：逻辑联接词：运算方法、运算优先级逻辑联接词：运算方法、运算优先级3、从命题常量到命题变量，、从命题常量到命题变量，从复合命题到命题公式：从复合命题到命题公式：命题公式的真值描述：真值表命题公式的真值描述：真值表4、命题公式的分类：、命题公式的分类：永真公式、永假公式、可满足公式永真公式、永假公式、可满足公式 、一般公式、一般公式 131.1 命题命题与联接词与联接词q命题：具有唯一真值陈述句v唯一性：或真或假但不能两者都是的v命题所用符号：常用小写个英文字母q例子v十是整数v2100年人类将在月球生活vx=3v

7、现在是几点？v1+1=2v我现在说假话悖论！悖论！141.1 命题命题与联接词与联接词q判断下列语句是否为命题v明天下雨v加拿大是一个国家vx+y4注：v命题是陈述句，陈述句不一定是命题v命题有唯一真值，但真值可能受范围、时空、环境、判断标准、认识程度限制，一时无法确定151.1 命题与命题与联接词联接词q命题分类v简单命题：不能被分解成更简单的陈述句v复合命题：简单陈述句+连接词q例子v今天没有天晴v王华的成绩很好并且品德很好v小李是学数学或者计算机科学v如果天下雨，那么地下湿161.1 命题与命题与联接词联接词q否定联接词v符号,读作“非”，“否定”q定义：命题pvp的否定式：复合命题“p

8、的否定”（“非p”）v符号：p(符号称作否定联结词)vp为真当且仅当p为假q例子v今天没有天晴 p p：今天天晴ppTFFT171.1 命题与命题与联接词联接词q合取联接词v符号,读作“合取”q定义：命题p，qvp与q的合取式：复合命题“p并且q”v符号：pq(符号称作合取联结词)vpq为真当且仅当p和q同时为真q例子v王华的成绩很好并且品德很好 pqp：王华的成绩很好q：王华的品德很好p qpqF FFF TFT FFT TT181.1 命题与命题与联接词联接词q析取联接词v符号,读作“析取”q定义：命题p，qvp与q的析取式：复合命题“p或q”v符号：pq(符号称作合取联结词)vpq为假当

9、且仅当p和q同时为假q例子v小李是学数学或者计算机科学pqp：小李是学数学q：小李是学计算机科学p qpqF FFF TTT FTT TT191.1 命题与命题与联接词联接词析取联接词（相容或）“排斥或”q排斥或：v符号 q定义：命题p，qv符号：pqv等价于(pq)(pq)vpq为假当且仅当p和q同时为假或同时为真q例子：v小李在教室看书或在图书馆上网v小李在看书或者听音乐（析取）p qpqF FFF TTT FTT TF201.1 命题与命题与联接词联接词q蕴含联接词v符号,读作“如果则”、“蕴含”q定义：命题p，qvp与q的蕴涵式：复合命题“如果p，则q”v符号：pq(符号称作蕴涵联结词

10、)vpq为假当且仅当p为真，q为假q例子v如果天下雨，那么地下湿pqp：天下雨q：地下湿p qpqF FTF TTT FFT TT211.1 命题与命题与联接词联接词q更多关于蕴含联接词qpq：q是p的必要条件q其他：vpq的叙述方式：“只要p，就q”，“因为p，所以q”等v p为假，pq永远为真v 如果给我一个支点，我能把 地球撬起来 v区别于自然语言的“如果p,则q”p和q有内在联系p qpqF FTF TTT FFT TT221.1 命题与命题与联接词联接词q更多例子v如果天晴，则雪是白的 pqv如果不天晴，则雪是不是白的 pqv（对给定正整数a）只要a能被4整除，则a能被2整除 pq2

11、31.1 命题与命题与联接词联接词q给定命题pqv它的逆命题qpv它的反命题pqv它的逆反命题 qpq各种命题关系vpq qpvqp pq241.1 命题与命题与联接词联接词q等价式v符号,读作“当且仅当”q定义：命题p，qvp与q的等价式：复合命题“p当且仅当q”v符号：pq(符号称作等价联结词)vpq为假当且仅当p与q真值相同q例子v当且仅当x=2，才有x2=4 pqp：x=2q：x2=4p qpqF FTF TFT FFT TT251.1 命题与命题与联接词联接词q等价式v符号,读作“当且仅当”q定义：命题p，qvp与q的等价式：复合命题“p当且仅当q”v符号：pq(符号称作等价联结词)

12、vpq为假当且仅当p与q真值相同q例子v当且仅当x=2，才有x2=4 pqp：x=2q：x2=4p qpqF FTF TFT FFT TT261.1 命题与命题与联接词联接词q联接词的定义总结pqppqpqpqpqFFTFFTTFTTFTTFTFFFTFFTTFTTTT271.1 命题与命题与联接词联接词q联接词的优先级v、q括号最优先q同一优先级：从左到右q例子：求于命题pqr含义相同的命题v(p)q)rv(pq)rvp(qr)v(pqr)281.1 命题与命题与联接词联接词q例：vp：北京比天津人口多vq：224vr：乌鸦是白色的求下列命题真值v(pq)(pq)rv(qr)(pr)v(pr

13、)(pr)TTF291.1 命题与命题与联接词联接词q例子：符号化下面命题v小强虽然不聪明，但很用功v小李学过英语或者法语v小李正在教室看书或在图书馆上网v金无足赤，人无完人v得道多助，失道寡助pqpq(pq)(pq)pq(pq)(pq)301.1 命题与命题与联接词联接词q问题1：区别vx+y4v明天下雨311.1 命题与命题与联接词联接词q问题2：v得道多助，失道寡助(pq)(pq)321.1 命题与命题与联接词联接词q课堂练习：vp：2+3=5vq：大熊猫产在中国vr：太阳从西部升起求下列命题真值v(r(pq)(pr)FFFTTTFF331.2 命题公式命题公式及其赋值及其赋值q命题常项

14、：简单命题q命题变项：表示命题的变量v真值可以变化的陈述句v命题变项不是命题v命题变项用确定命题代入才能确定真值v命题所用符号：常用小写个英文字母命题变量不同于代数式的变量vx+y4的x，y不是命题变量34蕴含的几种表述蕴含的几种表述q如果如果p,则则qqP仅当仅当qq只有只有q才才pq除非除非q才才pq除非除非q否则非否则非p351.2 命题公式命题公式及其赋值及其赋值q合式公式（命题公式）的递归定义：1.单个命题常项或命题变项是合式公式（原子命题公式）2.A为合式公式，则A是合式公式3.A，B为合式公式,则（AB），（AB），AB），（AB）为合式公式4.有限次应用1-3形成的字符串为合式

15、公式q思考一下递归定义的好处思考一下递归定义的好处q子公式B：给定合式公式AvB是A的一部分vB是合式公式361.2 命题公式命题公式及其赋值及其赋值q符号说明v大写字母A，B表示合式公式q公式简写法则：v公式最外层括号可以省略v（A）的括号可以省略v根据运算符优先级省略括号 省略括号不能影响公式解释371.2 命题公式命题公式及其赋值及其赋值q合式公式的树状展开 (AB)(C)(DC)ABA B(C)(DC)(C)DCCDC381.2 命题公式命题公式及其赋值及其赋值q例子v(AB)Cv(pq)(qr)v(B)vpqr391.2 命题公式命题公式及其赋值及其赋值q公式层次v若公式A是单个的命

16、题变元，则称A为0层合式v称公式是n+1(n0)层公式是指下面情况之一a)AB，B是n层公式b)ABC，其中B，C分别为i层和j层公式，且nmax(i,j)c)ABC，其中B，C的层次及n同(b)d)ABC，其中B，C的层次及n同(b)e)ABC，其中B，C的层次及n同(b)v若公式的层次为k，则称A是k层公式q层次联接词数401.2 命题公式命题公式及其赋值及其赋值q例子：例子：p,q,r,s为命题变元为命题变元v(pq)r)sv(pq)(qr)v(pq r)s(p q r)435411.2 命题公式及其命题公式及其赋值赋值q命题公式的真值v命题变项的常量化：常项替换（解释）q例子：公式pq

17、rv真值为T的解释p:3是奇数；q:7是奇数；r:3乘7是奇数v真值为F的解释p:3是奇数；q:7是奇数；r:3乘7是偶数q赋值v命题变项赋真命题命题变项的真值为Tv命题变项赋假命题命题变项的真值为F421.2 命题公式及其命题公式及其赋值赋值q命题变项赋值vA中命题变项：p1,pnv对p1,pn赋值v：v(pi)=i，iT,Fv对A的真值递归定义v(B)=T iff v(B)=Fv(BC)=T iff v(B)=v(C)=Tv(BC)=F iff v(B)=v(C)=Fv(BC)=F iff v(B)=T，v(C)=Fv(BC)=T iff v(B)=v(C)v赋值（解释）简写：12,nvn

18、个变项的公式，共有2n个不同赋值431.2 命题公式及其命题公式及其赋值赋值q命题变项赋值v成真赋值：v(A)=Tv成假赋值：v(A)=Fq例子：公式(pq)rvFFF(p=F,q=F,r=F)vTFF?(pq)rFFF441.2 命题公式及其命题公式及其赋值赋值q真值表：A所有赋值列成表q真值表构造：v找出A中命题变项：p1,pnv列出2n个赋值（2进制加法形式）v从高到低写成公式各个层次v各个赋值：计算各层的真值451.2 命题公式及其命题公式及其赋值赋值q例(pq)p)p q pq(pq)p(pq)p)FFFFTFTTFTTFTTFTTTTF461.2 命题公式及其命题公式及其赋值赋值q

19、例例p(q r)pqrqrp(qr)FFFF FFFTF FFTFF FFTTT TTFFF TTFTF TTTFFTTTTT T471.2 命题公式及其命题公式及其赋值赋值q例(pq)(pqpq)p q p q pq pqpq公式公式FFTTTTTFTTFFFTTFFTFFTTTFFTTT481.2 命题公式及其命题公式及其赋值赋值q练习练习:v15页：页：19（3）（）（5）v15页：页：20（3）491.2 命题公式及其命题公式及其赋值赋值q命题公式分类：命题公式分类：Av重言式重言式(永真式永真式)：v(A)=T，对任意，对任意vv矛盾式矛盾式(永假式永假式)：v(A)=F，对任意，对

20、任意vv可满足式可满足式：v(A)=T，对某个，对某个vq关系关系v重言式是可满足式，反之不一定成立重言式是可满足式，反之不一定成立q真值判断发真值判断发v重言式：真值表最后一列全为重言式：真值表最后一列全为Tv矛盾式：真值表最后一列全为矛盾式：真值表最后一列全为Fv可满足式：真值表最后一列至少一个可满足式：真值表最后一列至少一个T501.2 命题公式及其命题公式及其赋值赋值q真值表有限性：给定真值表有限性：给定n个命题变项个命题变项v共有共有22n个真值表个真值表q例题：下列哪些具有相同真值？例题：下列哪些具有相同真值？a)pqb)qpc)(pq)d)(p q)p511.2 命题公式及其命题

21、公式及其赋值赋值q例题例题p qpqqp(pq)(pq)pFFTTTFFTTFTTTFFTFFTTTTTF521.2 命题公式及其命题公式及其赋值赋值q例题：下列哪些具有相同真值？例题：下列哪些具有相同真值？a)pqb)p(q r)c)(p q)(p r)p)531.2 命题公式及其命题公式及其赋值赋值q例题例题pqrpqp(qr)(pq)(pr)p)FFFT FT FFTT FT FTFT FT FTTT FT TFFF TF TFTF FF TTFTTTTTTT TT 54第一章第一章 习题课习题课q主要内容主要内容l命题、真值、简单命题与复合命题、命题符号化命题、真值、简单命题与复合命题

22、、命题符号化l联结词联结词,及复合命题符号化及复合命题符号化l命题公式及层次命题公式及层次l公式的类型公式的类型l真值表及应用真值表及应用q基本要求基本要求l深刻理解各联结词的逻辑关系深刻理解各联结词的逻辑关系,熟练地将命题符号化熟练地将命题符号化l会求复合命题的真值会求复合命题的真值l深刻理解合式公式及重言式、矛盾式、可满足式等深刻理解合式公式及重言式、矛盾式、可满足式等l熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型判断公式类型551.将下列命题符号化将下列命题符号化 (1)豆沙包是由面粉和红小豆做成的豆沙包是由

23、面粉和红小豆做成的.(2)苹果树和梨树都是落叶乔木苹果树和梨树都是落叶乔木.(3)王小红或李大明是物理组成员王小红或李大明是物理组成员.(4)王小红或李大明中的一人是物理组成员王小红或李大明中的一人是物理组成员.(5)由于交通阻塞，他迟到了由于交通阻塞，他迟到了.(6)如果交通不阻塞，他就不会迟到如果交通不阻塞，他就不会迟到.(7)他没迟到，所以交通没阻塞他没迟到，所以交通没阻塞.(8)除非交通阻塞，否则他不会迟到除非交通阻塞，否则他不会迟到.(9)他迟到当且仅当交通阻塞他迟到当且仅当交通阻塞.练习练习156提示：提示：分清复合命题与简单命题分清复合命题与简单命题分清相容或与排斥或分清相容或与

24、排斥或分清必要与充分条件及充分必要条件分清必要与充分条件及充分必要条件答案答案:(1)是简单命题是简单命题 (2)是合取式是合取式 (3)是析取式（相容或）是析取式（相容或）(4)是析取式（排斥或）是析取式（排斥或）设设 p:交通阻塞，交通阻塞，q:他迟到他迟到 (5)pq,(6)pq或或qp (7)qp 或或pq,(8)qp或或 pq (9)pq 或或 pq可见可见(5)与与(7)，(6)与与(8)相同（等值）相同（等值）练习练习1解答解答572.设设 p:2是素数是素数 q:北京比天津人口多北京比天津人口多 r:美国的首都是旧金山美国的首都是旧金山 求下面命题的真值求下面命题的真值 (1)

25、(p q)r (2)(q r)(pr)(3)(qr)(pr)(4)(qp)(pr)(rq)0练习练习2100583.用真值表判断下面公式的类型用真值表判断下面公式的类型 (1)p r(qp)(2)(pq)(qp)r (3)(pq)(pr)练习练习359练习练习3解答解答(1)p r(qp)矛盾式矛盾式p q rqp (qp)p r(qp)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 11001111 00110000 00000000 60练习练习3解答解答(2)(pq)(qp)r 永真式永真式11111111 11110011 11110011 0 0 0

26、0 0 10 1 00 1 11 0 01 0 11 1 01 1 1(pq)(qp)r qp pq p q r61练习练习3解答解答(3)(pq)(pr)非永真式的可非永真式的可满满足式足式p q rpq pr (pq)(pr)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 11110011 11110101 11111001 621.1 约定约定q在一个复杂的公式中，为了避免歧义需要引进许多的括号，但如果括号太多会使人眼花缭乱，如(p(qr)(pq)(rs)，共有6对括号，为了减少括号并不引起歧义，引进如下省略括号的约定：v公式最外层的括号可以省略。v规定联接词运算优先级别从高到低 v若同一个联结词连续多次出现且无括号，则按从左到右的顺序运算。q按照上述约定，(p(qr)(pq)(rs)省略了三对括号简化为 p(qr)(pq)(rs)。省略括号只是让公式书写简便，但并不能改变其复杂性。