离散数学 课件命题逻辑.ppt
第第2 2章章 命题逻辑命题逻辑1实例实例某单位要从某单位要从A,B,C三人中选派若干人出国考察三人中选派若干人出国考察,需满足下述条件需满足下述条件:(1)若若A去去,则则C必须去必须去;(2)若若B去去,则则C不能去不能去;(3)A和和B必须去一人且只能去一人必须去一人且只能去一人.问有几种可能的选派方案问有几种可能的选派方案?2请根据下面事实，找出凶手：请根据下面事实，找出凶手：1.清洁工或者秘书谋害了经理。清洁工或者秘书谋害了经理。2.如果清洁工谋害了经理，则谋害不会发生在午如果清洁工谋害了经理，则谋害不会发生在午夜前。夜前。3.如果秘书的证词是正确的，则谋害发生在午夜如果秘书的证词是正确的，则谋害发生在午夜前。前。4.如果秘书的证词不正确，则午夜时屋里灯光未如果秘书的证词不正确，则午夜时屋里灯光未灭。灭。5.如果清洁工富裕，则他不会谋害经理。如果清洁工富裕，则他不会谋害经理。6.经理有钱且清洁工不富裕。经理有钱且清洁工不富裕。7.午夜时屋里灯灭了。午夜时屋里灯灭了。实际推理题实际推理题：3第第2章章 命题逻辑命题逻辑2.1 命题逻辑基本概念命题逻辑基本概念 2.2 命题逻辑等值演算命题逻辑等值演算 2.3 范式范式2.4 命题逻辑推理理论命题逻辑推理理论 42.1 命题逻辑基本概念命题逻辑基本概念 2.1.1 命题与联结词命题与联结词命题与真值命题与真值(简单命题简单命题,复合命题复合命题)联结词联结词(,)2.2.2 命题公式及其分类命题公式及其分类命题公式及其赋值命题公式及其赋值真值表真值表命题公式的分类命题公式的分类 5命题及其真值命题及其真值命题命题:判断结果惟一的陈述句判断结果惟一的陈述句命题的真值命题的真值:判断的结果判断的结果,真或假真或假真命题真命题:真值为真的命题真值为真的命题假命题假命题:真值为假的命题真值为假的命题注意注意:感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是陈述句中的悖论以及判断结果不惟一确定的也不是命题命题 6例例1 1 下列句子中那些是命题？下列句子中那些是命题？(1)北京是中华人民共和国的首都北京是中华人民共和国的首都.(2)2+5 8.(3)x+5 3.(4)你会开车吗？你会开车吗？(5)2050年元旦北京是晴天年元旦北京是晴天.(6)这只兔子跑得真快呀！这只兔子跑得真快呀！(7)请关上门！请关上门！(8)我正在说谎话我正在说谎话.真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(1),(2),(5)是命题是命题,(3),(4),(6)(8)都不都不是命题是命题真值确定真值确定,但未但未知知实例实例7简单命题与复合命题简单命题与复合命题简单命题简单命题(原子命题原子命题):简单陈述句构成的命题简单陈述句构成的命题简单命题的符号化简单命题的符号化:用用p,q,r,pi,qi,ri(i1)表示表示 用用“1”表示真，用表示真，用“0”表示假表示假复合命题复合命题:由简单命题通过联结词联结而成的陈述句由简单命题通过联结词联结而成的陈述句 例如例如 如果明天天气好如果明天天气好,我们就出去郊游我们就出去郊游设设p:明天天气好明天天气好,q:我们出去郊游我们出去郊游,如果如果p,则则q 又如又如 张三一面喝茶一面看报张三一面喝茶一面看报设设p:张三喝茶张三喝茶,q:张三看报张三看报,p并且并且q8联结词与复合命题联结词与复合命题定定义义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为真为真9实例实例例例2 将下列命题符号化将下列命题符号化.(1)王晓既用功又聪明王晓既用功又聪明.(2)王晓不仅聪明，而且用功王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生张辉与王丽都是三好生.(5)张辉与王丽是同学张辉与王丽是同学.解解 记记 p:王晓用功王晓用功,q:王晓聪明王晓聪明(1)pq(2)pq(3)p q(4)记记 r:张辉是三好生张辉是三好生,s:王丽是三好生王丽是三好生,rs(5)简单命题简单命题,记记 t:张辉与王丽是同学张辉与王丽是同学10联结词与复合命题联结词与复合命题(续续)定定义义2.3 设设 p,q为为命命题题,复复合合命命题题“p或或q”称称作作p与与q的的析析取取式式,记作记作pq,称作称作析取联结词析取联结词,并规定并规定pq为假当且仅当为假当且仅当p与与q同时为假同时为假.例如例如 张三和李四至少有一人会英语张三和李四至少有一人会英语设设 p:张三会英语张三会英语,q:李四会英语李四会英语,符号化为符号化为pq相容或与排斥或相容或与排斥或例如例如 这件事由张三和李四中的一人去做这件事由张三和李四中的一人去做 设设 p:张三做这件事张三做这件事,q:李四做这件事李四做这件事 应符号化为应符号化为 (p q)(p q)11实例实例例例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(t u)(tu)(5)记记v:王晓红生于王晓红生于1975年年,w:王晓红生于王晓红生于1976年年(v w)(vw)又可形式化为又可形式化为 vw12联结词与复合命题联结词与复合命题(续续)定定义义2.4 设设 p,q为为二二命命题题,复复合合命命题题“如如果果p,则则q”称称作作p与与q的的蕴涵式蕴涵式,记作记作pq,并称并称p是蕴涵式的是蕴涵式的前件前件,q为蕴涵式的为蕴涵式的后件后件.称作称作蕴涵联结词蕴涵联结词,并规定并规定,pq为假当且仅当为假当且仅当 p为为真且真且q为假为假.例如例如 如果明天天气好如果明天天气好,我们就出去郊游我们就出去郊游 设设p:明天天气好明天天气好,q:我们出去郊游我们出去郊游,形式化为形式化为 pq13蕴涵联结词蕴涵联结词(续续)pq 的逻辑关系的逻辑关系:q为为p的必要条件的必要条件,p为为q的充分条件的充分条件“如果如果p,则则q”的多种表述方式：的多种表述方式：若若p,就就q 只要只要p,就就q 只有只有q 才才p 除非除非q,才才p 除非除非q,否则非否则非p当当p为假时，为假时，pq为真为真(不管不管q为真为真,还是为假还是为假)14实例实例例例4 设设p:天冷天冷,q:小王穿羽绒服，小王穿羽绒服，将下列命题符号化将下列命题符号化 (1)只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服.注意：注意：pq 与与 qp 等值（真值相同）等值（真值相同）pqpq qp 或或 pqpqqp qp pq 或或 qp15联结词与复合命题联结词与复合命题(续续)定定义义2.5 设设p,q为为命命题题,复复合合命命题题“p当当且且仅仅当当q”称称作作p与与q的的等价式等价式,记作记作pq,称作称作等价联结词等价联结词.并规定并规定pq为真当为真当且仅当且仅当 p与与q同时为真或同时为假同时为真或同时为假.pq 的逻辑关系的逻辑关系:p与与q互为充分必要条件互为充分必要条件例如例如 这件事张三能做好这件事张三能做好,且只有张三能做好且只有张三能做好 设设p:张三做这件事张三做这件事,q:这件事做好了这件事做好了 形式化为形式化为:pq16实例实例例例5 求下列复合命题的真值求下列复合命题的真值(1)2+24 当且仅当当且仅当 3+36.(2)2+24 当且仅当当且仅当 3是偶数是偶数.(3)2+24 当且仅当当且仅当 太阳从东方升起太阳从东方升起.(4)2+25 当且仅当当且仅当 美国位于非洲美国位于非洲.(5)f(x)在在x0处处可导的充要条件是它在可导的充要条件是它在 x0处连续处连续.1011017联结词与复合命题联结词与复合命题(续续)联结词优先级联结词优先级:(),:(),同级按从左到右的顺序进行同级按从左到右的顺序进行 p q p pq pq pq pq 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1基本复合命题的真值基本复合命题的真值18合式公式合式公式命题常命题常项项:简单命题简单命题 命题变项命题变项:真值可以变化的陈述句真值可以变化的陈述句定义定义2.6 合式公式合式公式(命题公式命题公式,公式公式)递归定义如下：递归定义如下：(1)单个命题常项或变项单个命题常项或变项是是合式公式合式公式,并称作并称作原子合式公式原子合式公式(2)若若A是合式公式是合式公式,则则(A)也是合式公式也是合式公式(3)若若A,B是合式公式是合式公式,则则(A B),(A B),(AB),(AB)也也 是合式公式是合式公式(4)只有有限次地应用只有有限次地应用(1)(3)形成的符号串才是合式公式形成的符号串才是合式公式说明说明:(1)元语言符号与对象语言符号元语言符号与对象语言符号 (2)在不影响运算顺序时在不影响运算顺序时,括号可以省去括号可以省去 例如例如 0,p,p q,(p q)(p r),p q r,(pq)r19合式公式的层次合式公式的层次定义定义2.7 (1)单个命题变项或命题常项是单个命题变项或命题常项是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)(d)A=BC,其中其中B,C的层次及的层次及n同同(b)(e)A=BC,其中其中B,C的层次及的层次及n同同(b)例如例如 p 0层层 p 1层层 pq 2层层 (pq)r 3层层 (p q)r)(r s)4层层20公式的赋值公式的赋值定义定义2.8 设设p1,p2,pn是出现在公式是出现在公式A中全部的命题变项中全部的命题变项,给给 p1,p2,pn指定一组真值指定一组真值,称为对称为对A的一个的一个赋值赋值或或解释解释.使公式为真的赋值称作使公式为真的赋值称作成真赋值成真赋值,使公式为假的赋值称作使公式为假的赋值称作成假赋值成假赋值说明说明:(1)赋值记作赋值记作=1 2 n,i=0或或1,诸诸 i之间不加标之间不加标点符号点符号(2)通常赋值与命题变项之间按下标或字母顺序对应通常赋值与命题变项之间按下标或字母顺序对应,即即当当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,21实例实例例例6 公式公式A=p1 p2 01是成真赋值是成真赋值,00是成假赋值是成假赋值 公式公式B=(p1 p2 p3)(p1 p2)000是成真赋值是成真赋值,001是成假赋值是成假赋值 公式公式C=(pq)r 000是成假赋值是成假赋值,001是成真赋值是成真赋值22真值表真值表例例7 给出公式的真值表给出公式的真值表(1)(qp)qp p q qp (qp)q (qp)qp 0 00 11 01 1 1011 0001 1111真值表真值表:命题公式在所有可能的赋值下的取值的列表命题公式在所有可能的赋值下的取值的列表含含n个变项的公式有个变项的公式有2n个赋值个赋值23实例实例(续续)(2)(p q)q p q p p q (p q)(p q)q0 00 11 01 1 110011010010000024实例实例(续续)(3)(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 1110101025命题公式的分类命题公式的分类重言式重言式(永真式永真式):无成假赋值的命题公式无成假赋值的命题公式矛盾式矛盾式(永假式永假式):无成真赋值的命题公式无成真赋值的命题公式可满足式可满足式:非矛盾式的命题公式非矛盾式的命题公式注意注意:重言式是可满足式，但反之不真重言式是可满足式，但反之不真.例如例如 上例中上例中(1)(qp)qp为重言式为重言式(2)(p q)q为矛盾式为矛盾式(3)(p q)r为非重言式的可满足式为非重言式的可满足式26
