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

《离散数学-21命题逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学-21命题逻辑.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2 2章章 命题逻辑命题逻辑1第第2章章 命题逻辑命题逻辑2.1 命题逻辑基本概念命题逻辑基本概念 2.2 命题逻辑等值演算命题逻辑等值演算 2.3 范式范式2.4 命题逻辑推理理论命题逻辑推理理论 2 命题逻辑基本概念命题逻辑基本概念 2.1.1 命题与联结词命题与联结词命题与真值命题与真值(简单命题简单命题,复合命题复合命题)联结词联结词(,)命题公式及其分类命题公式及其分类命题公式及其赋值命题公式及其赋值真值表真值表命题公式的分类命题公式的分类 3命题及其真值命题及其真值命题命题:判断结果惟一的陈述句判断结果惟一的陈述句命题的真值命题的真值:判断的结果判断的结果,真或假真或假真命题真

2、命题:真值为真的命题真值为真的命题假命题假命题:真值为假的命题真值为假的命题注意注意:感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是陈述句中的悖论以及判断结果不惟一确定的也不是命题命题 4例例1 1 下列句子中那些是命题？下列句子中那些是命题？(1)北京是中华人民共和国的首都北京是中华人民共和国的首都.(2)2+5 8.(3)x+5 3.(4)你会开车吗？你会开车吗？(5)2050年元旦北京是晴天年元旦北京是晴天.(6)这只兔子跑得真快呀！这只兔子跑得真快呀！(7)请关上门！请关上门！(8)我正在说谎话我正在说谎话.真命题真命题假命

3、题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(1),(2),(5)是命题是命题,(3),(4),(6)(8)都不都不是命题是命题真值确定真值确定,但未但未知知实例实例5简单命题与复合命题简单命题与复合命题简单命题简单命题(原子命题原子命题):简单陈述句构成的命题简单陈述句构成的命题简单命题的符号化简单命题的符号化:用用p,q,r,pi,qi,ri(i1)表示表示 用用“1”表示真，用表示真，用“0”表示假表示假复合命题复合命题:由简单命题通过联结词联结而成的陈述句由简单命题通过联结词联结而成的陈述句 例如例如 如果明天天气好如果明天天气好,我们就出去郊游我们就出去郊

4、游设设p:明天天气好明天天气好,q:我们出去郊游我们出去郊游,如果如果p,则则q 又如又如 张三一面喝茶一面看报张三一面喝茶一面看报设设p:张三喝茶张三喝茶,q:张三看报张三看报,p并且并且q6联结词与复合命题联结词与复合命题 设设p为命题为命题,复合命题复合命题“非非p”(或或“p的否定的否定”)称为称为p的的否定式否定式,记作记作 p,符号符号 称作称作否定联结词否定联结词,并规定并规定 p为真当且仅当为真当且仅当 p为假为假例如例如 p:2是合数是合数,p:2不是合数不是合数,p为假为假,p为真为真 设设p,q为二命题为二命题,复合命题复合命题“p并且并且q”(或或“p与与q”)称称为为

5、p与与q的的合取式合取式,记作记作pq,称作称作合取联结词合取联结词,并规定并规定 pq为真当且仅当为真当且仅当 p与与q同时为真同时为真例如例如 p:2是偶数是偶数,q:2是素数是素数,pq:2是偶素数是偶素数,p为真为真,q为真为真,pq为真为真7实例实例例例2 将下列命题符号化将下列命题符号化.(1)王晓既用功又聪明王晓既用功又聪明.(2)王晓不仅聪明，而且用功王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生张辉与王丽都是三好生.(5)张辉与王丽是同学张辉与王丽是同学.解解 记记 p:王晓用功王晓用功,q:王晓聪明王晓聪明(1)pq(

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

7、一人去做这件事由张三和李四中的一人去做 设设 p:张三做这件事张三做这件事,q:李四做这件事李四做这件事 应符号化为应符号化为 (p q)(pq)9实例实例例例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:元元拿一个梨元元拿一个梨真值真

8、值:1真值真值:1真值真值:0(t u)(tu)(5)记记v:王晓红生于王晓红生于1975年年,w:王晓红生于王晓红生于1976年年(v w)(vw)又可形式化为又可形式化为 vw10联结词与复合命题联结词与复合命题(续续)设设 p,q为二命题为二命题,复合命题复合命题“如果如果p,则则q”称作称作p与与q的的蕴涵式蕴涵式,记作记作pq,并称并称p是蕴涵式的是蕴涵式的前件前件,q为蕴涵式的为蕴涵式的后件后件.称作称作蕴涵联结词蕴涵联结词,并规定并规定,pq为假当且仅当为假当且仅当 p为为真且真且q为假为假.例如例如 如果明天天气好如果明天天气好,我们就出去郊游我们就出去郊游 设设p:明天天气好

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

10、，所以小王穿羽绒服因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.注意：注意：pq 与与 qp 等值（真值相同）等值（真值相同）pqpq qp 或或 pqpqqp qp pq 或或 qpqp13与与“除非不把理论当作教条；否除非不把理论当作教条；否则就会束缚思

11、想则就会束缚思想”不同义的是不同义的是:A.如果不把理论当作教条，就不会束缚思想B.如果把理论当作教条，就会束缚思想C.只有束缚思想，才会把理论当作教条。D.只有不把理论当作教条，才不会束缚思想。E.除非束缚思想，否则不会把理论当作教条。14联结词与复合命题联结词与复合命题(续续)设设p,q为命题为命题,复合命题复合命题“p当且仅当当且仅当q”称作称作p与与q的的等价式等价式,记作记作pq,称作称作等价联结词等价联结词.并规定并规定pq为真当为真当且仅当且仅当 p与与q同时为真或同时为假同时为真或同时为假.pq 的逻辑关系的逻辑关系:p与与q互为充分必要条件互为充分必要条件例如例如 这件事张三

12、能做好这件事张三能做好,且只有张三能做好且只有张三能做好 设设p:张三做这件事张三做这件事,q:这件事做好了这件事做好了 形式化为形式化为:pq15实例实例例例5 求下列复合命题的真值求下列复合命题的真值(1)2+24 当且仅当当且仅当 3+36.(2)2+24 当且仅当当且仅当 3是偶数是偶数.(3)2+24 当且仅当当且仅当 太阳从东方升起太阳从东方升起.(4)2+25 当且仅当当且仅当 美国位于非洲美国位于非洲.(5)f(x)在在x0处处可导的充要条件是它在可导的充要条件是它在 x0处连续处连续.1011016联结词与复合命题联结词与复合命题(续续)联结词优先级联结词优先级:(),:()

13、,同级按从左到右的顺序进行同级按从左到右的顺序进行 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基本复合命题的真值基本复合命题的真值17合式公式合式公式命题常命题常项项:简单命题简单命题 命题变项命题变项:取值取值0(真真)或或1(假假)的变元的变元 合式公式合式公式(命题公式命题公式,公式公式)递归定义如下：递归定义如下：(1)单个命题常项或变项单个命题常项或变项是是合式公式合式公式,并称作并称作原子合式公式原子合式公式(2)若若A是合式公式是合式公式,则则(A)也是合式公式也是合式公式(3

14、)若若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)r18合式公式的层次合式公式的层次定义定义2.7 (1)单个命题变项或命题常项是单个命题变项或命题常项是0层公式层公式(2)称称A是是n+1(n0)层公式是指下面情况之一：层公式是指下面情况之

15、一：(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层层19公式的赋值公式的赋值定义定义2.8 设设p1,p2,pn是出现在公式是出现在公式A中全部的命题变项中全部的命题变项,给给 p1,p2,pn指定一组真值指定一组真值,称为对称为对A的一个的一

16、个赋值赋值或或解释解释.使公式为真的赋值称作使公式为真的赋值称作成真赋值成真赋值,使公式为假的赋值称作使公式为假的赋值称作成假赋值成假赋值说明说明:(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,20实例实例例例6 公式公式

17、A=(p1 p2 p3)(p1 p2)000是成真赋值是成真赋值,001是成假赋值是成假赋值 公式公式B=(pq)r 000是成假赋值是成假赋值,001是成真赋值是成真赋值21真值表真值表例例7 给出公式的真值表给出公式的真值表(1)(qp)qp p q qp (qp)q (qp)qp 0 00 11 01 1 1011 0001 1111真值表真值表:命题公式在所有可能的赋值下的取值的列表命题公式在所有可能的赋值下的取值的列表含含n个变项的公式有个变项的公式有2n个赋值个赋值22实例实例(续续)(2)(p q)q p q p p q (p q)(p q)q0 00 11 01 1 11001

18、1010010000023实例实例(续续)(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 1110101024命题公式的分类命题公式的分类重言式重言式(永真式永真式):无成假赋值的命题公式无成假赋值的命题公式矛盾式矛盾式(永假式永假式):无成真赋值的命题公式无成真赋值的命题公式可满足式可满足式:非矛盾式的命题公式非矛盾式的命题公式注意注意:重言式是可满足式，但反之不真重言式是可满足式，但反之不真.例如例如 上例中上例中(1)(qp)qp为重言式为重言式(2)(p q)q为矛盾式为矛盾式(3)(p q)r为非重言式的可满足式为非重言式的可满足式25