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

《离散数学-耿素云PPT第5版.ppt》由会员分享，可在线阅读，更多相关《离散数学-耿素云PPT第5版.ppt（33页珍藏版）》请在三一办公上搜索。

1、1,离散数学,2,主要内容,数理逻辑集合论图论组合分析初步代数系统简介形式语言和自动机初步,3,教材与教学参考书,教材：耿素云、屈婉玲、张立昂，离散数学（第五版），清华大学出版社,2013.教学参考书：屈婉玲、耿素云、张立昂，离散数学题解（第五版），清华大学出版社，2013.,4,数理逻辑部分,第1章 命题逻辑第2章 一阶逻辑,5,第1章 命题逻辑,1.1 命题符号化及联结词1.2 命题公式及分类1.3 等值演算1.4 范式1.5 联结词全功能集1.6 组合电路1.7 推理理论,6,1.1 命题符号化及联结词,命题与真值原子命题复合命题命题常项命题变项联结词,7,命题与真值,命题:判断结果惟一

2、的陈述句命题的真值:判断的结果真值的取值:真与假真命题:真值为真的命题假命题:真值为假的命题注意:感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是命题,8,例 下列句子中那些是命题？(1)是无理数.(2)2+5 8.(3)x+5 3.(4)你有铅笔吗？(5)这只兔子跑得真快呀！(6)请不要讲话！(7)我正在说谎话.,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(3)(7)都不是命题,9,命题的分类,简单命题(原子命题)：简单陈述句构成的命题 复合命题：由简单命题与联结词按一定规则复合 而成的命题,10,简单命题符号化,用小写英文字母 p,q,r,pi,

3、qi,ri(i1）表示简单命题用“1”表示真，用“0”表示假例如，令 p：是有理数，则 p 的真值为 0 q：2+5=7，则 q 的真值为 1,11,联结词与复合命题,1.否定式与否定联结词“”定义 设p为命题，复合命题“非p”(或“p的否定”)称 为p的否定式，记作p.符号称作否定联结词，并规 定p 为真当且仅当p为假.2.合取式与合取联结词“”定义 设p,q为二命题,复合命题“p并且q”(或“p与q”)称 为p与q的合取式，记作pq.称作合取联结词，并规 定 pq为真当且仅当p与q同时为真注意：描述合取式的灵活性与多样性 分清简单命题与复合命题,12,例 将下列命题符号化.(1)王晓既用功

4、又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.解 令 p：王晓用功，q：王晓聪明，则(1)pq(2)pq(3)pq.,13,例(续),令 r:张辉是三好学生，s:王丽是三好学生(4)rs.(5)令 t:张辉与王丽是同学，t 是简单命题.,说明:(1)(4)说明描述合取式的灵活性与多样性.(5)中“与”联结的是两个名词，整个句子是一个简单命题.,14,联结词与复合命题(续),定义 设 p,q为二命题，复合命题“p或q”称作p与q 的析取式，记作pq.称作析取联结词，并规定pq为假当且仅当p与q同时为假.,例 将下列命题符号

5、化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.(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)符号化为(tu)(tu).令v:王晓红生于1975年,w:王晓红生于1976年,则(5)既可符号化为(vw)(vw),又可符号化为 vw.,16,联结词与复合命题(续),定义 设 p,q

6、为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件.称作蕴涵联结词，并规定，pq为假当且仅当 p 为真 q 为假.,4.蕴涵式与蕴涵联结词“”,17,pq 的逻辑关系：q 为 p 的必要条件“如果 p，则 q”的不同表述法很多：若 p，就 q 只要 p，就 q p 仅当 q 只有 q 才 p 除非 q,才 p 或 除非 q,否则非 p.当 p 为假时，pq 为真常出现的错误：不分充分与必要条件,联结词与复合命题(续),18,例 设 p:天冷，q:小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(

7、3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.,注意：pq 与 qp 等值（真值相同）,pq,pq,pq,pq,qp,qp,qp,qp,19,联结词与复合命题(续),定义 设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq.称作等价联结词.并规定pq为真当且仅当p与q同时为真或同时为假.说明:(1)pq 的逻辑关系:p与q互为充分必要条件(2)pq为真当且仅当p与q同真或同假,5.等价式与等价联结词“”,20,例 求下列

8、复合命题的真值(1)2+2 4 当且仅当 3+3 6.(2)2+2 4 当且仅当 3 是偶数.(3)2+2 4 当且仅当 太阳从东方升起.(4)2+2 4 当且仅当 美国位于非洲.(5)函数 f(x)在x0 可导的充要条件是它在 x0连续.,1,1,0,0,0,例,21,联结词与复合命题(续),以上给出了5个联结词：,，组成一个联结词集合,，联结词的优先顺序为：,;如果出现的联结词同级，又无括号时，则按从左到右的顺序运算;若遇有括号时，应该先进行括号中的运算.注意:本书中使用的 括号全为园括号.,22,1.2 命题公式及分类,命题变项与合式公式公式的赋值真值表命题的分类 重言式 矛盾式 可满足

9、式真值函数,23,命题变项与合式公式,命题常项：简单命题命题变项：真值不确定的陈述句定义 合式公式(命题公式,公式)递归定义如下：(1)单个命题常项或变项 p,q,r,pi,qi,ri,0,1 是合式公式(2)若A是合式公式，则(A)也是合式公式(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式(4)只有有限次地应用(1)(3)形成的符号串才是合式公式说明:外层括号可以省去,24,合式公式的层次,定义(1)若公式A是单个的命题变项,则称A为0层公式.(2)称A是n+1(n0)层公式是指下面情况之一：(a)A=B,B是n层公式；(b)A=BC,其中B,C分别为i层和j

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

11、3是指p=1,q=2,r=3 含n个变项的公式有2n个赋值.,27,真值表,真值表:公式A在所有赋值下的取值情况列成的表 例 给出公式的真值表 A=(qp)qp 的真值表,28,例 B=(pq)q 的真值表,实例,29,例 C=(pq)r 的真值表,30,公式的类型,定义 设A为一个命题公式(1)若A无成假赋值，则称A为重言式(也称永真式)(2)若A无成真赋值，则称A为矛盾式(也称永假式)(3)若A不是矛盾式，则称A为可满足式注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式 A=(qp)qp，B=(pq)q，C=(pq)r,31,真值函數,问题：含n个命题变项的所

12、有公式共产生多少个互不相同的真值表？定义 称定义域为000,001,111，值域为0,1的函数是n元真值函数，定义域中的元素是长为n的0,1串.常用F:0,1n0,1 表示F是n元真值函数.共有 个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个命题变项的公式的真值表都可以在下表中找到.例如：pq,pq,(pq)(pq)q)等都对应表中的,33,2元真值函数对应的真值表,