离散数学-耿素云PPT第5版.ppt

《离散数学-耿素云PPT第5版.ppt》由会员分享，可在线阅读，更多相关《离散数学-耿素云PPT第5版.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1离散数学离散数学2主要内容主要内容n数理逻辑数理逻辑n集合论集合论n图论图论n组合分析初步组合分析初步n代数系统简介代数系统简介n形式语言和自动机初步形式语言和自动机初步3教材与教学参考书教材与教学参考书n教材：教材：耿素云、屈婉玲、张立昂，离散数学（第五版）耿素云、屈婉玲、张立昂，离散数学（第五版），清华大学出版社，清华大学出版社,2013.n教学参考书：教学参考书：屈婉玲、耿素云、张立昂，离散数学题解（第屈婉玲、耿素云、张立昂，离散数学题解（第五版），清华大学出版社，五版），清华大学出版社，2013.4数理逻辑部分数理逻辑部分n第第1章章 命题逻辑命题逻辑n第第2章章 一阶逻辑一阶逻辑5

2、第第1章章 命题逻辑命题逻辑 1.1 命题符号化及联结词命题符号化及联结词1.2 命题公式及分类命题公式及分类1.3 等值演算等值演算1.4 范式范式1.5 联结词全功能集联结词全功能集1.6 组合电路组合电路1.7 推理理论推理理论61.1 命题符号化及联结词命题符号化及联结词 n命题与真值命题与真值n原子命题原子命题n复合命题复合命题n命题常项命题常项n命题变项命题变项n联结词联结词 7命题与真值命题与真值 命题命题:判断结果惟一的陈述句判断结果惟一的陈述句命题的真值命题的真值:判断的结果判断的结果真值的取值真值的取值:真与假真与假真命题真命题:真值为真的命题真值为真的命题假命题假命题:真

3、值为假的命题真值为假的命题注意注意:感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是陈述句中的悖论以及判断结果不惟一确定的也不是命题命题 8 例例 下列句子中那些是命题？下列句子中那些是命题？(1)是无理数是无理数.(2)2+5 8.(3)x+5 3.(4)你有铅笔吗？你有铅笔吗？(5)这只兔子跑得真快呀！这只兔子跑得真快呀！(6)请不要讲话！请不要讲话！(7)我正在说谎话我正在说谎话.真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(3)(7)都不是命题都不是命题9命题的分类命题的分类 简单命

4、题简单命题(原子命题原子命题)：简单陈述句构成的命题简单陈述句构成的命题 复合命题复合命题：由简单命题与联结词按一定规则复合由简单命题与联结词按一定规则复合 而成的命题而成的命题 10简单命题符号化简单命题符号化 用小写英文字母用小写英文字母 p,q,r,pi,qi,ri(i1）表示）表示简单命题简单命题用用“1”表示真，用表示真，用“0”表示假表示假例如，令例如，令 p：是有理数，则是有理数，则 p 的真值为的真值为 0 q：2+5=7，则，则 q 的真值为的真值为 1 11联结词与复合命题联结词与复合命题 1.否定式与否定联结词否定式与否定联结词“”定义定义 设设p为命题，复合命题为命题，

5、复合命题 “非非p”(或或 “p的否定的否定”)称称 为为p的的否定式否定式，记作，记作 p.符号符号 称作称作否定联结词否定联结词，并规，并规 定定 p 为真当且仅当为真当且仅当p为假为假.2.合取式与合取联结词合取式与合取联结词“”定义定义 设设p,q为二命题为二命题,复合命题复合命题“p并且并且q”(或或“p与与q”)称称 为为p与与q的的合取式合取式，记作，记作pq.称作称作合取联结词合取联结词，并规，并规 定定 pq为真当且仅当为真当且仅当p与与q同时为真同时为真注意：描述合取式的灵活性与多样性注意：描述合取式的灵活性与多样性 分清简单命题与复合命题分清简单命题与复合命题 12 例例

6、 将下列命题符号化将下列命题符号化.(1)王晓既用功又聪明王晓既用功又聪明.(2)王晓不仅聪明，而且用功王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生张辉与王丽都是三好生.(5)张辉与王丽是同学张辉与王丽是同学.解解 令令 p：王晓用功，：王晓用功，q：王晓聪明，则：王晓聪明，则 (1)pq (2)pq (3)p q.13 例例(续续)令令 r:张辉是三好学生，张辉是三好学生，s:王丽是三好学生王丽是三好学生 (4)rs.(5)令令 t:张辉与王丽是同学，张辉与王丽是同学，t 是简单命题是简单命题.说明说明:(1)(4)说明描述合取式的灵

7、活性与多样性说明描述合取式的灵活性与多样性.(5)中中“与与”联联结结的的是是两两个个名名词词，整整个个句句子子是是一个简单命题一个简单命题.14联结词与复合命题联结词与复合命题(续续)定定义义 设设 p,qp,q为为二二命命题题，复复合合命命题题“p p或或q q”称称作作p p与与q q 的的析析取取式式，记记作作p pq q.称称作作析析取取联联结结词词，并并规规定定p pq q为为假当且假当且仅仅当当p p与与q q同同时为时为假假.例例 将下列命题符号化将下列命题符号化 (1)2或或4是素数是素数.(2)2或或3是素数是素数.(3)4或或6是素数是素数.(4)小元元只能拿一个苹果或一

8、个梨小元元只能拿一个苹果或一个梨.(5)王晓红生于王晓红生于1975年或年或1976年年.3.析取式与析取联结词析取式与析取联结词“”15解解 令令 p:2是素数是素数,q:3是素数是素数,r:4是素数是素数,s:6是素数是素数,则则 (1),(2),(3)均为均为相容或相容或.分别符号化为分别符号化为:pr,pq,rs,它们的真值分别为它们的真值分别为 1,1,0.(4),(5)为为排斥或排斥或.令令 t:小元元拿一个苹果，小元元拿一个苹果，u:小元元拿一个梨，小元元拿一个梨，则则 (4)符号化为符号化为 (t u)(tu).令令v:王晓红生于王晓红生于1975年年,w:王晓红生于王晓红生于

9、1976年年,则则 (5)既可符号化为既可符号化为 (v w)(vw),又可又可符号化为符号化为 vw.16联结词与复合命题联结词与复合命题(续续)定定义义 设设 p,qp,q为为二二命命题题，复复合合命命题题 “如如果果p,p,则则q q”称称作作p p与与q q的的蕴蕴涵涵式式，记记作作p pq q，并并称称p p是是蕴蕴涵涵式式的的前前件件，q q为为蕴蕴涵涵式式的的后后件件.称称作作蕴蕴涵涵联联结结词词，并并规规定，定，p pq q为为假当且假当且仅仅当当 p p 为为真真 q q 为为假假.4.蕴涵式与蕴涵联结词蕴涵式与蕴涵联结词“”17pq 的逻辑关系：的逻辑关系：q 为为 p 的

10、必要条件的必要条件“如果如果 p，则，则 q”的不同表述法很多：的不同表述法很多：若若 p，就，就 q 只要只要 p，就，就 q p 仅当仅当 q 只有只有 q 才才 p 除非除非 q,才才 p 或或 除非除非 q,否则非否则非 p.当当 p 为假时，为假时，pq 为真为真常出现的错误：不分充分与必要条件常出现的错误：不分充分与必要条件联结词与复合命题联结词与复合命题(续续)18 例例 设设 p p:天冷，天冷，q q:小王穿羽绒服，小王穿羽绒服，将下列命题符号化将下列命题符号化 (1)只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服

11、.(3)若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.注意：注意：pq 与与 qp 等值（真值相同）等值（真值相同）pqpqpqpqqp qpqpqp19联结词与复合命题联结词与复合命题(续续)定定义义 设设p，q为为二二命命题题，复复合合命命题题“p当当且且仅仅当当q”称称作作p与与q的的

12、等等价价式式，记记作作pq.称称作作等等价价联联结结词词.并并规规定定pq为为真真当当且且仅仅当当p与与q同同时时为为真真或或同同时时为为假假.说明说明:(1)pq 的逻辑关系的逻辑关系:p与与q互为充分必要条件互为充分必要条件 (2)pq为真当且仅当为真当且仅当p与与q同真或同假同真或同假5.等价式与等价联结词等价式与等价联结词“”20例例 求下列复合命题的真值求下列复合命题的真值 (1)2+2 4 当且仅当当且仅当 3+3 6.(2)2+2 4 当且仅当当且仅当 3 是偶数是偶数.(3)2+2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起.(4)2+2 4 当且仅当当且仅当 美国位于

13、非洲美国位于非洲.(5)函数函数 f(x)在在x0 可导的充要条件是它在可导的充要条件是它在 x0连续连续.11000例例21联结词与复合命题联结词与复合命题(续续)以上给出了以上给出了5个联结词：个联结词：,，组成，组成一个联结词集合一个联结词集合,，联结词的优先顺序为：联结词的优先顺序为：,;如果出如果出现的联结词同级，又无括号时，则按从左到右现的联结词同级，又无括号时，则按从左到右的顺序运算的顺序运算;若遇有括号时，应该先进行括号若遇有括号时，应该先进行括号中的运算中的运算.注意注意:本书中使用的本书中使用的 括号全为园括号括号全为园括号.221.2 命题公式及分类命题公式及分类命题变项

14、与合式公式命题变项与合式公式公式的赋值公式的赋值真值表真值表命题的分类命题的分类 重言式重言式 矛盾式矛盾式 可满足式可满足式n真值函数真值函数23命题变项与合式公式命题变项与合式公式 命题常项命题常项：简单命题：简单命题命题变项命题变项：真值不确定的陈述句：真值不确定的陈述句定义定义 合式公式合式公式(命题公式命题公式,公式公式)递归定义如下：递归定义如下：(1)单个命题常项或变项单个命题常项或变项 p,q,r,pi,qi,ri,0,1 是是合式公式合式公式(2)若若A是合式公式，则是合式公式，则(A)也是合式公式也是合式公式(3)若若 A,B是是 合合 式式 公公 式式，则则(A B),(

15、A B),(AB),(AB)也是合式公式也是合式公式(4)只只有有有有限限次次地地应应用用(1)(3)形形成成的的符符号号串串才才是是合合式公式式公式说明说明:外层括号可以省去外层括号可以省去 24合式公式的层次合式公式的层次 定义定义(1)若公式若公式A是单个的命题变项是单个的命题变项,则称则称A为为0层公式层公式.(2)称称A是是n+1(n0)层公式是指下面情况之一：层公式是指下面情况之一：(a)A=B,B是是n层公式；层公式；(b)A=B C,其中其中B,C分别为分别为i层和层和j层公式，且层公式，且 n=max(i,j)；(c)A=B C,其中其中B,C的层次及的层次及n同同(b)；(

16、d)A=BC,其中其中B,C的层次及的层次及n同同(b)；(e)A=BC,其中其中B,C的层次及的层次及n同同(b).25合式公式的层次合式公式的层次(续续)例如例如 公式公式 p 0层层 p 1层层 pq 2层层 (pq)r 3层层 (p q)r)(r s)4层层26公式的赋值公式的赋值 定义定义 给公式给公式A中的命题变项中的命题变项 p1,p2,pn指定指定一组真值称为对一组真值称为对A的一个的一个赋值赋值或或解释解释成真赋值成真赋值:使公式为真的赋值使公式为真的赋值成假赋值成假赋值:使公式为假的赋值使公式为假的赋值说明说明：赋赋值值=1 2 n之之间间不不加加标标点点符符号号，i=0或

17、或1.A中中仅仅出出现现 p1,p2,pn，给给A赋赋值值 1 2 n是是指指 p1=1,p2=2,pn=n A中仅出现中仅出现 p,q,r,给给A赋值赋值 1 2 3是指是指p=1,q=2,r=3 含含n个变项的公式有个变项的公式有2n个赋值个赋值.27真值表真值表 真值表真值表:公式公式A在所有赋值下的取值情况列成的表在所有赋值下的取值情况列成的表 例例 给出公式的真值表给出公式的真值表 A=(qp)qp 的的真值表真值表 p q qp (qp)q (qp)qp 0 00 11 01 1 1011 0001 111128例例 B=(p q)q 的的真值表真值表 p q p p q (p q

18、)(p q)q0 00 11 01 1 1100110100100000实例实例29例例 C=(p q)r 的的真值表真值表 p q r p q r (p q)r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 0011111 1 1010101 0 1110101030公式的类型公式的类型 定义定义 设设A为一个命题公式为一个命题公式 (1)若若A无成假赋值，则称无成假赋值，则称A为为重言式重言式(也称也称永真式永真式)(2)若若A无成真赋值，则称无成真赋值，则称A为为矛盾式矛盾式(也称也称永假式永假式)(3)若若A不是矛盾式，则称不是矛盾式，则称A为为可

19、满足式可满足式注意：重言式是可满足式，但反之不真注意：重言式是可满足式，但反之不真.上例中上例中A为重言式，为重言式，B为矛盾式，为矛盾式，C为可满足式为可满足式 A=(qp)qp，B=(p q)q，C=(p q)r31真值函數真值函數 问题：含问题：含n个命题变项的所有公式共产生多少个互个命题变项的所有公式共产生多少个互不相同的真值表？不相同的真值表？定义定义 称定义域为称定义域为000,001,111，值域，值域为为0,1的函数是的函数是n元真值函数元真值函数，定义域中的元素是，定义域中的元素是长为长为n的的0,1串串.常用常用F:0,1n0,1 表示表示F是是n元真值元真值函数函数.共有

20、共有 个个n元真值函数元真值函数.例如例如 F:0,120,1，且，且F(00)=F(01)=F(11)=0，F(01)=1，则，则F为一个确定的为一个确定的2元真值函数元真值函数.32命题公式与真值函数命题公式与真值函数 对于任何一个含对于任何一个含n个命题变项的命题公式个命题变项的命题公式A，都存在，都存在惟一的一个惟一的一个n元真值函数元真值函数F为为A的真值表的真值表.等值的公式对应的真值函数相同等值的公式对应的真值函数相同.下表给出所有下表给出所有2元真值函数对应的真值表元真值函数对应的真值表,每一个含每一个含2 2个命题变项的公式的真值表都可以在下表中找到个命题变项的公式的真值表都可以在下表中找到.例如：例如：pq,p q,(p q)(pq)q)等等都对应都对应表中的表中的332元真值函数对应的真值表元真值函数对应的真值表p q0 00 10 11 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 p q0 00 10 11 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1