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

1、1计算机科学与工程学院计算机科学与工程学院周德宇周德宇2朱朱 棣棣 朱高炽朱高炽 朱瞻基朱瞻基 朱祁镇朱祁镇 朱祁钰朱祁钰 朱见深朱见深 朱佑樘朱佑樘 朱厚照朱厚照 朱厚熜朱厚熜 朱载垕朱载垕 朱翊钧朱翊钧 朱常洛朱常洛 朱由校朱由校 朱由检朱由检 问题：从这些名字中你能告诉我什么？问题：从这些名字中你能告诉我什么？3q研究离散量的结构及相互关系的数学科学v离散结构：集合、关系、图等 离散量是指分散开来的、不存在中间值的量 q研究对象:有限或可数个元素v自然数、整数，真假值，有限节点等q计算机技术的支撑科学：计算机只能处理离散的或离散化了的数量关系4数据结构基础数据结构基础离散结构离散结构数据

2、库原理数据库原理软件工程软件工程操作系统操作系统编译原理编译原理人工智能人工智能可计算性理论可计算性理论5数理逻辑数理逻辑集合论集合论代数结构代数结构图论图论8周周4周周4周周8周周6数理逻辑数理逻辑集合论集合论代数结构代数结构图论图论7数理逻辑数理逻辑q逻辑学分类v辩证逻辑：是研究事物发展的客观规律v形式逻辑：是研究思维的概念、判断和推理的问题v数理逻辑q数理逻辑v数学方法研究形式逻辑的一门科学v一般认为由莱布尼茨（leibniz）率先提出v最基本组成部分：命题演算、谓词演算v应用：逻辑电路、自动控制、人工智能等8引语引语两栖动物数量的下降清楚地说明全球空气和水质的污染。在加州yosemit

3、e国家公园对于两栖动物所进行的两次研究证实了我的结论。1915年公园中有7种两栖动物，每种的数量都很丰富。然而到了1992年在公园中只观察到4种两栖动物，并且每种动物的数量都显著下降。yosemite公园两栖动物数量的下降曾被归因于始于1920年的在公园水域引入鲑鱼的行为（我们知道鲑鱼捕食两栖动物的卵）。但鲑鱼的引入不会是但鲑鱼的引入不会是yosemite两栖两栖动物数量下降的真正原因，因为它并不能解释全动物数量下降的真正原因，因为它并不能解释全球范围的数量下降。球范围的数量下降。9问题分析问题分析逻辑主线：全球空气和水质的污染导致了全球两栖动物数量的下降错误逻辑：鲑鱼不能解释全球两栖动物下降

4、所以不能解释公园两栖动物数量下降。存在问题：1. 在加洲国家公园对两栖动物进行的研究不能推理除全球范围的两栖动物的数量下降。只能推理除公园里的两栖动物下降。2. 公园内两栖动物数量的下降并不能排除是由鲑鱼引入导致的，逻辑推理中不可以随意的将影响因素扩大化或缩小化。3. 最大得逻辑错误，转化逻辑主体，试图以全球两栖动物数量下降的事实证明鲑鱼不是yosemite公园里两栖动物下降得原因。两者间完全没有逻辑联系。10q主要内容（主要内容（8周的时间）周的时间）l 命题逻辑基本概念命题逻辑基本概念l 命题逻辑等值演算命题逻辑等值演算l 命题逻辑推理理论命题逻辑推理理论l 一阶逻辑基本概念一阶逻辑基本概

5、念l 一阶逻辑等值演算与推理一阶逻辑等值演算与推理第一部分第一部分 数理逻辑数理逻辑11第第1章命题逻辑基本概念章命题逻辑基本概念命题与联结词命题与联结词命题及其分类命题及其分类联结词与复合命题联结词与复合命题命题公式及其赋值命题公式及其赋值12学习要点学习要点1、命题的概念：定义、逻辑值、命题的概念：定义、逻辑值、 符号化表示符号化表示2、从简单命题到复合命题：、从简单命题到复合命题： 逻辑联接词：运算方法、运算优先级逻辑联接词：运算方法、运算优先级3、从命题常量到命题变量，、从命题常量到命题变量， 从复合命题到命题公式：从复合命题到命题公式： 命题公式的真值描述：真值表命题公式的真值描述：

6、真值表4、命题公式的分类：、命题公式的分类： 永真公式、永假公式、可满足公式永真公式、永假公式、可满足公式 、一般公式、一般公式 131.1 与联接词与联接词q命题：具有唯一真值陈述句v唯一性：或真或假但不能两者都是的v命题所用符号：常用小写个英文字母q例子v十是整数v2100年人类将在月球生活vx=3v现在是几点？v1+1=2v我现在说假话悖论！悖论！141.1 与联接词与联接词q判断下列语句是否为命题v明天下雨v加拿大是一个国家vx+y4注：v命题是陈述句，陈述句不一定是命题v命题有唯一真值，但真值可能受范围、时空、环境、判断标准、认识程度限制，一时无法确定151.1 命题与命题与q命题分

7、类v简单命题：不能被分解成更简单的陈述句v复合命题：简单陈述句+连接词q例子v今天没有天晴v王华的成绩很好并且品德很好v小李是学数学或者计算机科学v如果天下雨，那么地下湿161.1 命题与命题与q否定联接词v符号,读作“非”，“否定”q定义：命题pvp的否定式：复合命题“p的否定”（“非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王华的成绩很好

8、并且品德很好 pq p：王华的成绩很好 q：王华的品德很好p qpqf fff tft fft tt181.1 命题与命题与q析取联接词v符号,读作“析取”q定义：命题p，qvp与q的析取式：复合命题“p或q”v符号：pq(符号称作合取联结词)vpq为假当且仅当p和q同时为假q例子v小李是学数学或者计算机科学pq p：小李是学数学 q：小李是学计算机科学p qpqf fff ttt ftt tt191.1 命题与命题与析取联接词（相容或） “排斥或”q排斥或：v符号 q定义：命题p，qv符号：pqv等价于(pq)(pq)vpq为假当且仅当p和q同时为假或同时为真q例子：v小李在教室看书或在图书

9、馆上网v小李在看书或者听音乐 （析取）p qpqf fff ttt ftt tf201.1 命题与命题与q蕴含联接词v符号,读作“如果则”、“蕴含”q定义：命题p，qvp与q的蕴涵式：复合命题“如果p，则q”v符号：pq(符号称作蕴涵联结词)vpq为假当且仅当p为真，q为假q例子v如果天下雨，那么地下湿pq p：天下雨 q：地下湿p qpqf ftf ttt fft tt211.1 命题与命题与q更多关于蕴含联接词qpq：q是p的必要条件q其他：vpq的叙述方式：“只要p，就q”，“因为p，所以q”等v p为假，pq永远为真v 如果给我一个支点，我能把 地球撬起来 v区别于自然语言的“如果p,

10、则q” p和q有内在联系p qpqf ftf ttt fft tt221.1 命题与命题与q更多例子v如果天晴，则雪是白的 pqv如果不天晴，则雪是不是白的 pqv（对给定正整数a）只要a能被4整除，则a能被2整除 pq231.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 pq p：x=2 q： x2=4

11、p qpqf ftf tft fft tt251.1 命题与命题与q等价式v符号,读作“当且仅当”q定义：命题p，qvp与q的等价式：复合命题“p当且仅当q”v符号：pq(符号称作等价联结词)vpq为假当且仅当p与q真值相同q例子v当且仅当x=2，才有x2=4 pq p：x=2 q： x2=4p qpqf ftf tft fft tt261.1 命题与命题与q联接词的定义总结pqppqpqpqpqfftffttfttfttftffftffttftttt271.1 命题与命题与q联接词的优先级v、q括号最优先q同一优先级：从左到右q例子：求于命题pqr含义相同的命题v(p)q)rv(pq)rvp

12、(qr)v(pqr)281.1 命题与命题与q例：vp：北京比天津人口多vq：224vr：乌鸦是白色的求下列命题真值v(pq)(pq)rv(qr)(pr)v(pr)(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：太

13、阳从西部升起求下列命题真值v(r(pq)(pr)ffftttff331.2 命题公式命题公式及其赋值及其赋值q命题常项：简单命题q命题变项：表示命题的变量v真值可以变化的陈述句v命题变项不是命题v命题变项用确定命题代入才能确定真值v命题所用符号：常用小写个英文字母命题变量不同于代数式的变量vx+y4的x，y不是命题变量34蕴含的几种表述蕴含的几种表述q如果如果p, 则则qqp仅当仅当qq只有只有q才才pq除非除非q才才pq除非除非q否则非否则非pqp 351.2 命题公式命题公式及其赋值及其赋值q 合式公式（命题公式）的递归定义：1. 单个命题常项或命题变项是合式公式（原子命题公式）2. a为

14、合式公式，则a是合式公式3. a，b为合式公式,则（ab），（ ab）， ab）， （ ab）为合式公式4. 有限次应用1-3形成的字符串为合式公式q 思考一下递归定义的好处思考一下递归定义的好处q 子公式b：给定合式公式av b是a的一部分v b是合式公式361.2 命题公式命题公式及其赋值及其赋值q 符号说明v 大写字母a，b表示合式公式q 公式简写法则：v 公式最外层括号可以省略v （ a）的括号可以省略v 根据运算符优先级省略括号 省略括号不能影响公式解释371.2 命题公式命题公式及其赋值及其赋值q 合式公式的树状展开 (ab)(c)(dc)aba b(c)(dc)(c)dccdc3

15、81.2 命题公式命题公式及其赋值及其赋值q 例子v (ab)cv (pq)(qr)v (b)v pqr391.2 命题公式命题公式及其赋值及其赋值q 公式层次v 若公式a是单个的命题变元，则称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为命题变

16、元v (pq)r)sv (pq)(qr)v (pqr)s (pqr)435411.2 命题公式及其命题公式及其赋值赋值q 命题公式的真值v 命题变项的常量化：常项替换（解释）q 例子：公式pqrv 真值为t的解释 p:3是奇数；q:7是奇数；r:3乘7是奇数v 真值为f的解释 p:3是奇数；q:7是奇数；r:3乘7是偶数q 赋值v 命题变项赋真命题命题变项的真值为tv 命题变项赋假命题命题变项的真值为f421.2 命题公式及其命题公式及其赋值赋值q 命题变项赋值v a中命题变项：p1,pnv 对p1,pn赋值v：v(pi)=i，it,fv 对a的真值递归定义 v(b)=t iff v(b)=f

17、 v(bc)=t iff v(b)=v(c)=t v(bc)=f iff v(b)=v(c)=f v(bc)=f iff v(b)=t，v(c)=f v(bc)=t iff v(b)=v(c)v 赋值（解释）简写：12,nv n个变项的公式，共有2n个不同赋值431.2 命题公式及其命题公式及其赋值赋值q 命题变项赋值v 成真赋值：v(a)=tv 成假赋值：v(a)=fq 例子：公式(pq)rv fff(p=f,q=f,r=f)v tff?(pq)rfff441.2 命题公式及其命题公式及其赋值赋值q 真值表：a所有赋值列成表q 真值表构造：v 找出a中命题变项：p1,pnv 列出2n个赋值（

18、2进制加法形式）v 从高到低写成公式各个层次v 各个赋值：计算各层的真值451.2 命题公式及其命题公式及其赋值赋值q 例(pq)p)p q pq(pq)p(pq)p)fffftfttfttfttfttttf461.2 命题公式及其命题公式及其赋值赋值q 例p(qr)pqrqrp(qr)ffff ffftf fftff ffttt ttfff ttftf tttffttttt t471.2 命题公式及其命题公式及其赋值赋值q 例(pq)(pqpq)p q p q pqpqpq公式公式fftttttfttfffttfftfftttffttt481.2 命题公式及其命题公式及其赋值赋值q 练习:v

19、 15页：19（3）（5）v 15页：20（3）491.2 命题公式及其命题公式及其赋值赋值q 命题公式分类：av 重言式(永真式)：v(a)=t，对任意vv 矛盾式(永假式)：v(a)=f，对任意vv 可满足式：v(a)=t，对某个vq 关系v 重言式是可满足式，反之不一定成立q 真值判断发v 重言式：真值表最后一列全为tv 矛盾式：真值表最后一列全为fv 可满足式：真值表最后一列至少一个t501.2 命题公式及其命题公式及其赋值赋值q 真值表有限性：给定n个命题变项v 共有22n个真值表q 例题：下列哪些具有相同真值？a) pqb)qpc) (pq)d)(pq)p511.2 命题公式及其命

20、题公式及其赋值赋值q 例题p qpqqp(pq)(pq)pfftttffttftttfftfftttttf521.2 命题公式及其命题公式及其赋值赋值q 例题：下列哪些具有相同真值？a) pqb)p(qr)c) (pq)(pr)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命题、真值、简单命题与复合命题、命题符号化命题、真值、简单命题与复合命题、命题符号化l联结词联结词 ,

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

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

23、容或与排斥或分清相容或与排斥或分清必要与充分条件及充分必要条件分清必要与充分条件及充分必要条件答案答案: (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 : 美国的首都是旧金山美国的首都是旧金山 求下面命题的