离散数学-21命题逻辑.ppt

《离散数学-21命题逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学-21命题逻辑.ppt（25页珍藏版）》请在三一办公上搜索。

1、课件,1,第2章 命题逻辑,课件,2,第2章 命题逻辑,2.1 命题逻辑基本概念 2.2 命题逻辑等值演算 2.3 范式2.4 命题逻辑推理理论,课件,3,2.1 命题逻辑基本概念,2.1.1 命题与联结词命题与真值(简单命题,复合命题)联结词(,)命题公式及其分类命题公式及其赋值真值表命题公式的分类,课件,4,命题及其真值,命题:判断结果惟一的陈述句命题的真值:判断的结果,真或假真命题:真值为真的命题假命题:真值为假的命题注意:感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是命题,课件,5,例1 下列句子中那些是命题？(1)北京是中华人民共和国的首都.(2)2+5

2、 8.(3)x+5 3.(4)你会开车吗？(5)2050年元旦北京是晴天.(6)这只兔子跑得真快呀！(7)请关上门！(8)我正在说谎话.,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(1),(2),(5)是命题,(3),(4),(6)(8)都不是命题,真值确定,但未知,实例,课件,6,简单命题与复合命题,简单命题(原子命题):简单陈述句构成的命题简单命题的符号化:用p,q,r,pi,qi,ri(i1)表示 用“1”表示真，用“0”表示假复合命题:由简单命题通过联结词联结而成的陈述句 例如 如果明天天气好,我们就出去郊游设p:明天天气好,q:我们出去郊游,如果p,则q 又如 张三一

3、面喝茶一面看报设p:张三喝茶,q:张三看报,p并且q,课件,7,联结词与复合命题,定义2.1 设p为命题,复合命题“非p”(或“p的否定”)称为p的否定式,记作p,符号称作否定联结词,并规定p为真当且仅当 p为假例如 p:2是合数,p:2不是合数,p为假,p为真定义2.2 设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式,记作pq,称作合取联结词,并规定 pq为真当且仅当 p与q同时为真例如 p:2是偶数,q:2是素数,pq:2是偶素数,p为真,q为真,pq为真,课件,8,实例,例2 将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然

4、聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.解,记 p:王晓用功,q:王晓聪明,(1)pq,(2)pq,(3)pq,(4)记 r:张辉是三好生,s:王丽是三好生,rs,(5)简单命题,记 t:张辉与王丽是同学,课件,9,联结词与复合命题(续),定义2.3 设 p,q为命题,复合命题“p或q”称作p与q的析取式,记作pq,称作析取联结词,并规定pq为假当且仅当p与q同时为假.例如 张三和李四至少有一人会英语设 p:张三会英语,q:李四会英语,符号化为pq相容或与排斥或例如 这件事由张三和李四中的一人去做 设 p:张三做这件事,q:李四做这件事 应符号化为(pq)(pq),

5、课件,10,实例,例3 将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.解,记 p:2是素数,q:3是素数,r:4是素数,s:6是素数,(1)pr,(2)pq,(3)rs,(4)记t:元元拿一个苹果,u:元元拿一个梨,真值:1,真值:1,真值:0,(tu)(tu),(5)记v:王晓红生于1975年,w:王晓红生于1976年,(vw)(vw),又可形式化为 vw,课件,11,联结词与复合命题(续),定义2.4 设 p,q为二命题,复合命题“如果p,则q”称作p与q的蕴涵式,记作pq,并称p是蕴涵

6、式的前件,q为蕴涵式的后件.称作蕴涵联结词,并规定,pq为假当且仅当 p为真且q为假.例如 如果明天天气好,我们就出去郊游 设p:明天天气好,q:我们出去郊游,形式化为 pq,课件,12,蕴涵联结词(续),pq 的逻辑关系:q为p的必要条件,p为q的充分条件“如果p,则q”的多种表述方式：若p,就q 只要p,就q p仅当q 只有q 才p 除非q,才p 除非q,否则非p当p为假时，pq为真(不管q为真,还是为假),课件,13,实例,例4 设p:天冷,q:小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷

7、，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.,注意：pq 与 qp 等值（真值相同）,pq,pq,qp 或 pq,pq,qp,qp,pq 或 qp,qp,课件,14,与“除非不把理论当作教条；否则就会束缚思想”不同义的是:,A.如果不把理论当作教条，就不会束缚思想B.如果把理论当作教条，就会束缚思想C.只有束缚思想，才会把理论当作教条。D.只有不把理论当作教条，才不会束缚思想。E.除非束缚思想，否则不会把理论当作教条。,课件,15,联结词与复合命题(续),定义2.5 设p,q为命题,

8、复合命题“p当且仅当q”称作p与q的等价式,记作pq,称作等价联结词.并规定pq为真当且仅当 p与q同时为真或同时为假.pq 的逻辑关系:p与q互为充分必要条件例如 这件事张三能做好,且只有张三能做好 设p:张三做这件事,q:这件事做好了 形式化为:pq,课件,16,实例,例5 求下列复合命题的真值(1)2+24 当且仅当 3+36.(2)2+24 当且仅当 3是偶数.(3)2+24 当且仅当 太阳从东方升起.(4)2+25 当且仅当 美国位于非洲.(5)f(x)在x0处可导的充要条件是它在 x0处连续.,1,0,1,1,0,课件,17,联结词与复合命题(续),联结词优先级:(),同级按从左到

9、右的顺序进行,课件,18,合式公式,命题常项:简单命题 命题变项:取值0(真)或1(假)的变元定义2.6 合式公式(命题公式,公式)递归定义如下：(1)单个命题常项或变项是合式公式,并称作原子合式公式(2)若A是合式公式,则(A)也是合式公式(3)若A,B是合式公式,则(AB),(AB),(AB),(AB)也 是合式公式(4)只有有限次地应用(1)(3)形成的符号串才是合式公式说明:(1)元语言符号与对象语言符号(2)在不影响运算顺序时,括号可以省去 例如 0,p,pq,(pq)(pr),pq r,(pq)r,课件,19,合式公式的层次,定义2.7(1)单个命题变项或命题常项是0层公式(2)称

10、A是n+1(n0)层公式是指下面情况之一：(a)A=B,B是n层公式(b)A=BC,其中B,C分别为i层和j层公式,且 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)例如 p 0层 p 1层 pq 2层(pq)r 3层(pq)r)(rs)4层,课件,20,公式的赋值,定义2.8 设p1,p2,pn是出现在公式A中全部的命题变项,给 p1,p2,pn指定一组真值,称为对A的一个赋值或解释.使公式为真的赋值称作成真赋值,使公式为假的赋值称作成假赋值说明:(1)赋值记作=12n,i=0或1,诸i

11、之间不加标点符号(2)通常赋值与命题变项之间按下标或字母顺序对应,即当A的全部命题变项为p1,p2,pn时,给A赋值12n是指p1=1,p2=2,pn=n;当A的全部命题变项为p,q,r,时,给A赋值123是指p=1,q=2,r=3,课件,21,实例,例6 公式A=(p1 p2 p3)(p1 p2)000是成真赋值,001是成假赋值 公式B=(pq)r 000是成假赋值,001是成真赋值,课件,22,真值表,例7 给出公式的真值表(1)(qp)qp,真值表:命题公式在所有可能的赋值下的取值的列表含n个变项的公式有2n个赋值,课件,23,实例(续),(2)(pq)q,课件,24,实例(续),(3)(pq)r,课件,25,命题公式的分类,重言式(永真式):无成假赋值的命题公式矛盾式(永假式):无成真赋值的命题公式可满足式:非矛盾式的命题公式注意:重言式是可满足式，但反之不真.例如 上例中(1)(qp)qp为重言式(2)(pq)q为矛盾式(3)(pq)r为非重言式的可满足式,