命题逻辑课件

命题逻辑命题逻辑ppt课件课件命题逻辑ppt课件命题逻辑ppt课件命题逻辑ppt课件命题逻辑课件命题逻辑课件命题逻辑课件命题逻辑课件 例例下列句子中那些是命题？下列句子中那些是命题？(1)是无理数是无理数.(2)2+58.(3)x+53.(4)你有铅笔吗？你有铅笔吗？(5)这只兔子跑得真快呀！这只兔子跑得真快呀！(6)请不要讲话！请不要讲话！(7)我正在说谎话我正在说谎话.真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(3)(7)都不是命题都不是命题 6例下列句子理发师悖论理发师悖论n某乡村有一位理发师，一天他宣布：某乡村有一位理发师，一天他宣布：只给不自己只给不自己理发的人理发理发的人理发。这里就产生了问题：理发师给不。这里就产生了问题：理发师给不给自己理发？给自己理发？n如果他给自己理发，他就是自己理发的人，按照如果他给自己理发，他就是自己理发的人，按照他的原则，他不能给自己理发；他的原则，他不能给自己理发；n如果他不给自己理发，他就是不自己理发的人，如果他不给自己理发，他就是不自己理发的人，按照他的原则，他就应该给自己理发。按照他的原则，他就应该给自己理发。n这就产生了矛盾。这就产生了矛盾。7理发师悖论某乡村有一位理发师，一天他宣布：只给不自己理发的命题的分类命题的分类 简单命题简单命题(原子命题原子命题)：简单陈述句构成的命题简单陈述句构成的命题 复合命题复合命题：由简单命题用联结词联结而成的命题由简单命题用联结词联结而成的命题8命题的分类简单命题(原子命题)：8简单命题符号化简单命题符号化 在本书中用小写英文字母在本书中用小写英文字母 p,q,r,pi,qi,ri(i1）表示简单命题，将表）表示简单命题，将表示命题的符号放在该命题的前面，称为命题符号化。示命题的符号放在该命题的前面，称为命题符号化。用用“1”表示真，用表示真，用“0”表示假表示假对简单命题而言，它的真值是确定的，因而又称为命题常项或命题常元。对简单命题而言，它的真值是确定的，因而又称为命题常项或命题常元。例如，令例如，令 p：是有理数，则是有理数，则 p 的真值为的真值为 0 q：2+5=7，则，则 q 的真值为的真值为 1 见课本例见课本例1.29简单命题符号化在本书中用小写英文字母p,q,r,联结词与复合命题联结词与复合命题 1.否定式与否定联结词否定式与否定联结词“”定定义义2.12.1设设p为为任任一一命命题题，复复合合命命题题 “非非p”（或或 “p的的否否定定”）称称为为p的的否否定定式式，记记作作 p，符符号号 称称作作否否定定联联结结词词，并规定，并规定 p为真当且仅当（即：等价）为真当且仅当（即：等价）p为假为假2.合取式与合取联结词合取式与合取联结词“”定定义义2.22.2设设p,q为为两两命命题题,复复合合命命题题“p并并且且q”(”(或或“p与与q”)”)称称 为为p与与q的的合取式合取式，记作，记作pq，称作称作合取联结词合取联结词，并规，并规 定定 pq为真当且仅当为真当且仅当p与与q同时为真同时为真注意：描述合取式的灵活性与多样性注意：描述合取式的灵活性与多样性 分清简单命题与复合命题分清简单命题与复合命题 10联结词与复合命题1.否定式与否定联结词“”10 例例将下列命题符号化将下列命题符号化.(1)王晓既用功又聪明王晓既用功又聪明.(2)王晓不仅聪明，而且用功王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功王晓虽然聪明，但不用功.(4)王晓不是不聪明，而是不用功王晓不是不聪明，而是不用功.(5)张辉与王丽都是三好学生张辉与王丽都是三好学生.(6)张辉与王丽是同学张辉与王丽是同学.解解令令p：王晓用功，：王晓用功，q：王晓聪明，则：王晓聪明，则(1)pq(2)pq(3)p q.11例将下列命题符号化.例例(续续)(4)(p)q.令令r:张辉是三好学生，张辉是三好学生，s:王丽是三好学生王丽是三好学生(5)rs.(6)令令t:张辉与王丽是同学，张辉与王丽是同学，t 是简单命题是简单命题.说明说明:(1)(4)说明描述合取式的灵活性与多样性说明描述合取式的灵活性与多样性.(5)中中“与与”联结的是句子的主语成分，因而联结的是句子的主语成分，因而(5)中句子是简单命题中句子是简单命题.12例(续)(4)(p)q.说联结词与复合命题联结词与复合命题(续续)定义2.32.3 设 p,q为二命题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词，并规定 pq为假当且仅当p与q同时为假.即:pq为真当且仅当p与q至少有一个为真。此处定义的析取式pq表示的是一种相容性或，即允许p与q同时为真注意区分自然言语中“或”的二义性。见课本描述。例例将下列命题符号化将下列命题符号化(1)2或或4是素数是素数.(2)2或或3是素数是素数.(3)4或或6是素数是素数.(4)小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨.(5)王晓红生于王晓红生于1975年或年或1976年年.3.析取式与析取联结词析取式与析取联结词“”13联结词与复合命题(续)定义2.3设p,q为二命题，复解解令令 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:王晓红生于王晓红生于1976年年,则则 (5)既可符号化为既可符号化为 (v w)(vw),又可又可符号化为符号化为 vw,为什么为什么?（看（看vw的的值是多少？是多少？）14解令p:2是素数,q:3是素数,r:4是素数,s:联结词与复合命题联结词与复合命题(续续)定定义义2.42.4设设p,q为为二二命命题题，复复合合命命题题“如如果果p,则则q”称称作作p与与q的的蕴蕴涵涵式式，记记作作pq，并并称称p是是蕴蕴涵涵式式的的前前件件，q为为蕴蕴涵涵式式的的后后件件.称称作作蕴蕴涵涵联联结结词词，并规定，并规定，pq为假当且仅当为假当且仅当p 为真为真q 为假为假.4.蕴涵式与蕴涵联结词蕴涵式与蕴涵联结词“”15联结词与复合命题(续)定义2.4设p,q为二命题，pq 的逻辑关系：的逻辑关系：q为为p的必要条件的必要条件 或或p p为为q q的充分条件的充分条件 （找（找关系时，要分清蕴涵式的关系时，要分清蕴涵式的前件前件与与后件，后件，即找准充分条件或必要条件）即找准充分条件或必要条件）“如果如果 p，则，则 q”的不同表述法很多：的不同表述法很多：若若 p，就，就 q（p是是q的充分条件的充分条件）只要只要 p，就，就 q（p是是q的充分条件的充分条件）p 仅当仅当 q（q是是p的必要条件的必要条件）只有只有 q 才才 p（q是是p的必要条件的必要条件）除非除非 q,才才 p 或或 除非除非 q,否则非否则非 p，(必须记住必须记住)否则非否则非 可以理解为可以理解为 才才当当 p 为假时，为假时，pq 为真为真常出现的错误：不分充分与必要条件常出现的错误：不分充分与必要条件见课本中注意的两点事项见课本中注意的两点事项联结词与复合命题联结词与复合命题(续续)16pq的逻辑关系：q为p的必要条件或p为q的充分条件联结 例例 设设p p:天冷，天冷，q q:小王穿羽绒服，小王穿羽绒服，将下列命题符号化将下列命题符号化 (1)只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.注意：注意：pq 与与 q p 等值（真值相同）等值（真值相同）pqpqpqpqqp qpqpqp17例设p:天冷，q:小王穿联结词与复合命题联结词与复合命题(续续)定定义义2.52.5设设p，q为为二二命命题题，复复合合命命题题“p当当且且仅仅当当q”称称作作p与与q的的等等价价式式，记记作作pq，称称作作等等价价联联结结词词.pq为真当且仅当为真当且仅当p与与q同时为真或同时为假同时为真或同时为假.说明说明:(1)pq 的逻辑关系的逻辑关系:p与与q互为充分必要条件互为充分必要条件(2)pq为真当且仅当为真当且仅当p与与q同真或同假同真或同假5.等价式与等价联结词等价式与等价联结词“”18联结词与复合命题(续)定义2.5设p，q为二命题，复合命题例例求下列复合命题的真值求下列复合命题的真值(1)2+24当且仅当当且仅当3+36.(2)2+24当且仅当当且仅当3是偶数是偶数.(3)2+24当且仅当当且仅当太阳从东方升起太阳从东方升起.(4)2+24当且仅当当且仅当美国位于非洲美国位于非洲.(5)函数函数 f(x)在在x0可导的充要条件是它在可导的充要条件是它在x0连续连续.它们的真值分别为它们的真值分别为 1，0，1，0，0.19例求下列复合命题的真值19用联结词把各种各样的复合命题符号化用联结词把各种各样的复合命题符号化基本步骤：基本步骤：1：分析出各简单命题，将它们符号化；：分析出各简单命题，将它们符号化；2：使用合适的联结词，把简单命题逐个联：使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示。结起来，组成复合命题的符号化表示。注意析取联结词注意析取联结词 的应用的应用20用联结词把各种各样的复合命题符号化基本步骤：20联结词与复合命题联结词与复合命题(续续)以上给出了以上给出了5个联结词：个联结词：,，组成，组成一个联结词集合一个联结词集合,，联结词的优先顺序为：联结词的优先顺序为：,;1:1:如果出现的联结词同级，又无括号时，则按如果出现的联结词同级，又无括号时，则按从左到右的顺序运算从左到右的顺序运算;2:2:若遇有括号时，应该先进行括号中的运算若遇有括号时，应该先进行括号中的运算.注意注意:本书中使用的本书中使用的括号全为圆括号（）括号全为圆括号（）.21联结词与复合命题(续)以上给出了5个联结词：,2.2命题公式命题公式命题变项与合式公式命题变项与合式公式公式的赋值公式的赋值真值表真值表命题的分类命题的分类重言式重言式矛盾式矛盾式可满足式可满足式222.2命题公式22命题变项与合式公式命题变项与合式公式 命题常项命题常项：简单命题：简单命题 原子命题原子命题命题变项命题变项：真值不确定的陈述句：真值不确定的陈述句定义定义2.6合式公式合式公式(命题公式命题公式,公式公式)递归定义如下：递归定义如下：(1)单个命题常项或变项单个命题常项或变项p,q,r,pi,qi,ri,0,1 是是合式公式；合式公式；(2)若若A是合式公式，则是合式公式，则(A)也是合式公式；也是合式公式；(3)若若A,B是是合合式式公公式式，则则(A B),(A B),(AB),(AB)也是合式公式；也是合式公式；(4)只有有限次地应用只有有限次地应用(1)(3)形成的符号串才是合式公式。形成的符号串才是合式公式。注注:外层括号可以省去外层括号可以省去问：命：命题公式是命公式是命题吗？不是，原因不是，原因为：命：命题公式中可能含有命公式中可能含有命题变项。23命题变项与合式公式命题常项：简单命题原子命题23合式公式的层次合式公式的层次 定义定义2.72.7(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)；(d)A=BC,其中其中B,C的层次及的层次及n同同(b)；(e)A=BC,其中其中B,C的层次及的层次及n同同(b).(3)若若A的最高层次为的最高层次为k.则则A是是k层公式。层公式。24合式公式的层次定义2.724合式公式的层次合式公式的层次(续续)例如例如公式公式 p 0层层 p1层层 pq2层层(pq)r3层层 (p q)r)(r s)4层层25合式公式的层次(续)例如公式25公式的赋值公式的赋值 定义定义2.8给给命命题题公公式式A中中的的所所有有的的命命题题变变项项p1,p2,pn指指定定一一组组真值称为对真值称为对A的一个的一个赋值赋值或或解释解释成真赋值成真赋值:使公式为真的赋值使公式为真的赋值成假赋值成假赋值:使公式为假的赋值使公式为假的赋值说明说明：赋值赋值=1 2 n之间不加标点符号，之间不加标点符号，i=0或或1.A中仅出现中仅出现p1,p2,pn，给，给A赋值赋值 1 2 n是是指指p1=1,p2=2,pn=nA中仅出现中仅出现p,q,r,给给A赋值赋值 1 2 3是指是指p=1,q=2,r=3含含n个变项的公式有个变项的公式有2n个赋值个赋值.26公式的赋值定义2.826真值表真值表 真值表真值表:将命题将命题公式公式A在所有赋值之下取值的情况在所有赋值之下取值的情况列成表，成为列成表，成为A的真的真值表表 例例给出公式的真值表给出公式的真值表 A=(qp)qp 的的真值表真值表 p q qp(qp)q(qp)qp 00011011 1011 0001 111127真值表真值表:将命题公式A在所有赋值之下取值的情况列成例例B=(p q)q 的的真值表真值表 p q p p q(p q)(p q)q00011011 1100110100100000实例实例28例B=(pq)q的真值表p例例C=(p q)r 的的真值表真值表 p q r p q r(p q)r 000001010011100101110111 00111111 10101010 1110101029例C=(pq)r的真值表pq公式的类型公式的类型 定义定义2.92.9 设设A为一个命题公式为一个命题公式(1)若若A在在它它的的各各种种赋值下下取取值均均为真真，则则称称A为为重重言言式式(也也称称永真式永真式)(2)若若A在在它它的的各各种种赋值下下取取值均均为假假，则则称称A为为矛矛盾盾式式(也也称称永假式永假式)(3)若若A至少存在一组赋值是成真赋值，则称至少存在一组赋值是成真赋值，则称A为为可满足式可满足式注意：重言式是可满足式，但反之不真注意：重言式是可满足式，但反之不真.上例中上例中A为重言式，为重言式，B为矛盾式，为矛盾式，C为可满足式为可满足式 A=(qp)qp，B=(p q)q，C=(p q)r30公式的类型定义2.9设A为一个命题公式30小结：小结：本节主要内容：本节主要内容：要理解所学的定义，利用所给的定义进行简单的判断和分析。要理解所学的定义，利用所给的定义进行简单的判断和分析。1：命题：命题 命题常项命题常项 命题变项命题变项 简单命题简单命题 复合命题的定义。复合命题的定义。2 2：联结词：联结词：,定义定义取值情况，对应的语言词汇取值情况，对应的语言词汇表达。表达。3：命题公式：命题公式层次层次成真赋值成真赋值成假赋值成假赋值真值表的定义真值表的定义4：构造真值表的具体步骤，重言式：构造真值表的具体步骤，重言式矛盾式矛盾式可满足式可满足式定定义义31小结：本节主要内容：31上节知识复习上节知识复习n1:定义：命题定义：命题 真真(假假)命题命题 命题常命题常(变变)项项 n2:五个联结词定义及取值情况，对应的五个联结词定义及取值情况，对应的 语言表达语言表达n3:复合命题符号化的步骤复合命题符号化的步骤n4:命题公式命题公式 命题公式的层次定义及判断命题公式的层次定义及判断n5:成真赋值成真赋值 成假赋值成假赋值 重言式重言式 矛盾式矛盾式 可满足式定义可满足式定义n6:真值表定义及构造步骤真值表定义及构造步骤32上节知识复习1:定义：命题真(假)命题命题常(变)项3随堂练习随堂练习1：写出命题、简单命题的定义。：写出命题、简单命题的定义。2：用符号定义五个联结词及其各自取值情况。：用符号定义五个联结词及其各自取值情况。3：写出蕴涵式的定义，分析前件与后件的关系，：写出蕴涵式的定义，分析前件与后件的关系，列出对应的语言表达形式。列出对应的语言表达形式。4：写出遇到析取联结词二义性时的判断方式及对应：写出遇到析取联结词二义性时的判断方式及对应 符号表示。符号表示。5：列出下面公式的真值表，说明各公式的层次：列出下面公式的真值表，说明各公式的层次 (pq)(pq)(qp)(p q)(p q)6：写出命题公式的定义：写出命题公式的定义33随堂练习1：写出命题、简单命题的定义。33随堂练习随堂练习7：命题符号化：命题符号化：a:只有天冷只有天冷,小王才穿羽绒服小王才穿羽绒服.b:除非天冷除非天冷,小王才穿羽绒服小王才穿羽绒服.c:除非小王穿羽绒服除非小王穿羽绒服,否则天不冷否则天不冷.d:如果天不冷如果天不冷,则小王不穿羽绒服则小王不穿羽绒服.e:小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.f:只有只有4是偶数，是偶数，3才能被才能被2整除。整除。g:选小王或小李中的一人当三好学生。选小王或小李中的一人当三好学生。h:小王现在在宿舍或在图书馆里。小王现在在宿舍或在图书馆里。34随堂练习7：命题符号化：342.3命题公式间的关系命题公式间的关系 学习目标：学习目标：等值式等值式基本等值式基本等值式等值演算等值演算置换规则置换规则352.3命题公式间的关系学习目标：35等值式等值式 定义定义设设A、B为两命题，若等价式为两命题，若等价式AB是重言式，是重言式，则称则称A与与B等值的等值的，记作，记作AB，并称，并称AB是是等值式等值式说明说明：定义中符号：定义中符号“”不是联结词符，它只是当不是联结词符，它只是当A与与B等值时的一种记法。注意区分等值时的一种记法。注意区分“”、“=”和和“”可以可以用真值表验证两个公式是否等值用真值表验证两个公式是否等值等价关系具有自反性、对称性、传递性。等价关系具有自反性、对称性、传递性。请验证：请验证：p(qr)(p q)r p(qr)(pq)r36等值式定义设A、B为两命题，若等价式AB是重言式，则称用真值表法的验证方式用真值表法的验证方式n 设设A、B为两命题，由定义判断为两命题，由定义判断A与与B是否是否等值，应判断等值，应判断AB是否为重言式，若是否为重言式，若AB的真值表最后一列全为的真值表最后一列全为1，则，则AB为重言式，为重言式，因而因而AB，但最后一列全为，但最后一列全为1当且仅当在各当且仅当在各赋值之下，赋值之下，A与与B的真值相同。因而判断的真值相同。因而判断A与与B是否等值等价于判断是否等值等价于判断A、B的真值表是的真值表是否相同。否相同。37用真值表法的验证方式设A、B为两命题，由定义判断A与B是基本等值式基本等值式利用真值表法可以验证很多等值式：利用真值表法可以验证很多等值式：n下面下面24个重要的等值式，是学好数理逻辑个重要的等值式，是学好数理逻辑的关键基础，应当牢记！的关键基础，应当牢记！n在下面的公式中，在下面的公式中，A、B、C代表任意的代表任意的 命题公式。命题公式。38基本等值式利用真值表法可以验证很多等值式：38基本等值式基本等值式 双重否定律双重否定律:1.AA等幂律等幂律：2.A AA,3.A AA交换律交换律:4.A BB A,5.A BB A结合律结合律:6.(A B)CA(B C)7.(A B)CA(B C)分配律分配律:8.A(B C)(A B)(A C)9.A(B C)(A B)(A C)39基本等值式双重否定律:1.AA39基本等值式基本等值式(续续)德德摩根律摩根律 :10.(A B)AB11.(A B)AB吸收律吸收律:12.A(A B)A,13.A(A B)A零律零律:14.A 11,15.A 00同一律同一律:16.A 0A,17.A 1A排中律排中律:18.AA1矛盾律矛盾律:19.AA040基本等值式(续)德摩根律:10.(AB)A基本等值式基本等值式(续续)蕴涵等值式蕴涵等值式:20.ABA B等价等值式等价等值式:21.AB(AB)(BA)假言易位假言易位:22.ABBA等价否定等值式等价否定等值式:23.ABAB归谬论归谬论:24.(AB)(AB)A注意注意:A,B,C代表任意的命题公式代表任意的命题公式牢记这些等值式是继续学习的基础牢记这些等值式是继续学习的基础41基本等值式(续)蕴涵等值式:20.AB等值演算与置换规则等值演算与置换规则 等值演算等值演算:由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程置换定理置换定理：设：设(A)是含命题公式是含命题公式A的命题，的命题，若若AB,则则(B)(A)等值演算的基础：等值演算的基础：(1)等值关系的性质：自反、对称、传递等值关系的性质：自反、对称、传递(2)基本的等值式基本的等值式(3)置换规则置换规则42等值演算与置换规则等值演算:42应用举例应用举例证明两个公式等值证明两个公式等值 例例1证明证明p(qr)(p q)r证证p(qr)p(q r)（蕴涵等值式）（蕴涵等值式）(pq)r（结合律）（结合律）(p q)r（德摩根律）（德摩根律）(p q)r（蕴涵等值式）（蕴涵等值式）说明说明:也可以从右边开始演算（请做一遍）也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故省略不写因为每一步都用置换规则，故省略不写 熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出 43应用举例证明两个公式等值例1证明p(qr)应用举例应用举例证明两个公式不等值证明两个公式不等值例例2证明证明:p(qr)(pq)r用等值演算不能直接证明两个公式不等值用等值演算不能直接证明两个公式不等值,证明两证明两个公式不等值的基本思想是找到一个赋值使一个成个公式不等值的基本思想是找到一个赋值使一个成真真,另一个成假另一个成假.方法一方法一真值表法（自己证）真值表法（自己证）方法二方法二观察赋值法观察赋值法.容易看出容易看出000,010等是左边的等是左边的成真赋值，是右边的成假赋值成真赋值，是右边的成假赋值.方法三方法三用等值演算先化简两个公式，再观察用等值演算先化简两个公式，再观察.44应用举例证明两个公式不等值例2证明:p(qr)应用举例应用举例判断公式类型判断公式类型 例例3 3用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1)q(pq)解解 q(pq)q(p q)（蕴涵等值式）（蕴涵等值式）q(pq)（德摩根律）（德摩根律）p(qq)（交换律，结合律）（交换律，结合律）p 0（矛盾律）（矛盾律）0（零律）（零律）由最后一步可知，该式为矛盾式由最后一步可知，该式为矛盾式.45应用举例判断公式类型例3用等值演算法判断下列公式的类例例3(续续)(2)(pq)(qp)解解(pq)(qp)(p q)(qp)（蕴涵等值式）（蕴涵等值式）(p q)(p q)（交换律）（交换律）1由最后一步可知，该式为重言式由最后一步可知，该式为重言式.问：最后一步为什么等值于问：最后一步为什么等值于1？46例3(续)(2)(pq)(qp)例例3(续续)(3)(p q)(pq)r)解解(p q)(pq)r)(p(qq)r（分配律）（分配律）p 1 r（排中律）排中律）p r（同一律）（同一律）这这不不是是矛矛盾盾式式，也也不不是是重重言言式式，而而是是非非重重言言式式的的可可满满足足式式.如如101是是它它的的成成真真赋赋值值,000是是它它的成假赋值的成假赋值.总结：总结：A为矛盾式当且仅当为矛盾式当且仅当A0 A为重言式当且仅当为重言式当且仅当A1 说明：演算步骤不惟一说明：演算步骤不惟一,应尽量使演算短些应尽量使演算短些47例3(续)(3)(pq)(pq)r)本节小结n熟悉等值、等值演算的定义熟悉等值、等值演算的定义n会用真值表法判断等值会用真值表法判断等值n记熟会用记熟会用24个重要的等值式个重要的等值式48本节小结熟悉等值、等值演算的定义482.4主范式与判定为题主范式与判定为题 学习目标：学习目标：析取范式与合取范式析取范式与合取范式 主析取范式与主合取范式主析取范式与主合取范式 492.4主范式与判定为题学习目标：49析取范式与合取范式析取范式与合取范式 简简单单析析取取式式:仅仅由由有有限限个个命命题题变变项项或或其其否否定定构构成成的的析取式称为简单析取式。析取式称为简单析取式。如如p,q,pq,p q r,简简单单合合取取式式:仅仅由由有有限限个个命命题题变变项项或或其其否否定定构构成成的的合取式称为简单合取式。合取式称为简单合取式。如如p,q,pq,p q r,由定由定义可知：可知：1:一一个个简单析析取取式式是是重重言言式式，当当且且仅当当它它同同时含含一一个个命命题变项及其否定。及其否定。2:一一个个简单合合取取式式是是矛矛盾盾式式，当当且且仅当当它它同同时含含一一个个命命题变项及其否定。及其否定。50析取范式与合取范式简单析取式:仅由有限个命题变项或其否定构 析取范式与合取范式析取范式与合取范式(续续)析析取取范范式式:仅仅由由有有限限个个简简单单合合取取式式组组成成的的析析取取式式称称为为析析取取范范式式。A=A1 A2Ar,其其中中A1,A2,Ar是是简单合取式。简单合取式。A A是析取范式。是析取范式。合合取取范范式式:仅仅由由有有限限个个简简单单析析取取式式组组成成的的合合取取式式称称为为合合取取范范式式。A=A1 A2Ar,其其中中A1,A2,Ar是是简单析取式。简单析取式。A A是合取范式。是合取范式。显然：任何析取范式的对偶式为合取范式，显然：任何析取范式的对偶式为合取范式，任何合取范式的对偶式为析取范式，任何合取范式的对偶式为析取范式，51析取范式与合取范式(续)析取范式:仅由有限个简单合取式组成析取范式与合取范式析取范式与合取范式(续续)析取范式与合取范式有下列性质：析取范式与合取范式有下列性质：n1：一个析取范式是矛盾式，当且一个析取范式是矛盾式，当且仅当它的当它的每个每个简单合取式都是矛盾式。合取式都是矛盾式。n2：一个合取范式是重言式，当且一个合取范式是重言式，当且仅当它的当它的每个每个简单析取式都是重言。析取式都是重言。52析取范式与合取范式(续)析取范式与合取范式有下列性质：52析取范式与合取范式析取范式与合取范式(续续)范式范式:析取范式与合取范式的总称析取范式与合取范式的总称公式公式A的析取范式的析取范式:与与A等值的析取范式等值的析取范式公式公式A的合取范式的合取范式:与与A等值的合取范式等值的合取范式说明：说明：单单个个命命题题变变项项及及其其否否定定既既是是简简单单析析取取式式，又又是是简简单单合取式合取式形如形如 pq r,p qr 的公式既是析取范式，的公式既是析取范式，又是合取范式又是合取范式 (为什么为什么?)53析取范式与合取范式(续)范式:析取范式与合取范式的总称53 命题公式的范式命题公式的范式 定定理理（范范式式存存在在定定理理）任任何何命命题题公公式式都都存存在在着着与与之之等等值值的的析取范式和合取范式析取范式和合取范式.求公求公式式A的范式的步骤：的范式的步骤：(1)由由于于,是是全全功功能能集集，因因而而若若A中中含含联联结结词词,等等，可可用用基基本本的的等等值值式式及及置置换换规规则则将将这这些些联联结结词词消去。消去。(2)否定联结词否定联结词 的内移或消去的内移或消去(3)使用分配律使用分配律 对对 分配（求析取范式）分配（求析取范式）对对 分配（求合取范式）分配（求合取范式）公式的范式存在，但不惟一，这是它的局限性公式的范式存在，但不惟一，这是它的局限性54命题公式的范式定理（范式存在定理）任何命题公式都存在求公式的范式举例求公式的范式举例 例例求下列公式的析取范式与合取范式求下列公式的析取范式与合取范式(1)A=(pq)r解解 (pq)r(pq)r（消去（消去）pqr（结合律）（结合律）这既是这既是A的析取范式（由的析取范式（由3个简单合取式组成的析个简单合取式组成的析取式），又是取式），又是A的合取范式（由一个简单析取式的合取范式（由一个简单析取式组成的合取式）组成的合取式）55求公式的范式举例例求下列公式的析取范式与合取范式55求公式的范式举例求公式的范式举例(续续)(2)B=(pq)r解解 (pq)r (pq)r（消去第一个（消去第一个）(pq)r（消去第二个（消去第二个）(p q)r（否定号内移（否定号内移德摩根律）德摩根律）这一步已为析取范式（两个简单合取式构成）这一步已为析取范式（两个简单合取式构成）继续：继续：(p q)r(p r)(q r)（对对 分配律）分配律）这一步得到合取范式（由两个简单析取式构成）这一步得到合取范式（由两个简单析取式构成）56求公式的范式举例(续)(2)B=(pq)r56 极小项极小项定定义义在在含含n个个命命题题变变项项的的简简单单合合取取式式中中，若若每每个个命命题题变变项项与与其其否否定定不不同同时时存存在在，而而两两者者之之一一必必出出现现且且仅仅出出现现一一次次，且且第第i（1 i n）个个命命题题变变项项或或其其否否定定出出现现在在从从左左起起的的第第i位位上上（若若命命题题变变项项无无角角标标，则则按按字字典典顺顺序序排排序序），称称这这样的简单合取式为样的简单合取式为极小项极小项.说明：说明：nn个命题变项产生个命题变项产生2n个极小项。个极小项。2n个极小项均互不等值个极小项均互不等值n用用mi表示第表示第i个极小项，将个极小项，将mi里的命里的命题变项看成看成1，命，命题变项的否定看成的否定看成0，则每个极小每个极小项对应一个二一个二进制数，也制数，也对应一个十一个十进制数。二制数。二进制数正是制数正是该极小极小项的成真的成真赋值，十十进制数制数i是该极小项成真赋值的十进制表示也是该极小是该极小项成真赋值的十进制表示也是该极小项抽象表示法的角码项抽象表示法的角码.57极小项定义在含n个命题变项的简单合取式中，若每个命题变公式公式 成真成真赋值赋值名称名称 p qr p q r p qr p q rp q rp q rp qrp q r000001010011100101110111m0m1m2m3m4m5m6m7极小项极小项 由由p,q,r三个命题变项形成的极小项三个命题变项形成的极小项58公式成真名称pqr000m0极小项由知识回顾知识回顾n1:定义：排斥或定义：排斥或 与非式与非式 或非式或非式 全功能集全功能集 冗余的（独立的）联结词冗余的（独立的）联结词n2:对偶式对偶式 对偶原理对偶原理 简单合取式简单合取式 简单析取式简单析取式 析取范式与合取范式析取范式与合取范式 极小项极小项n3:求公式求公式A的范式的步骤的范式的步骤59知识回顾1:定义：排斥或与非式或非式全功能集冗余的（主析取范式主析取范式n定义：定义：主析取范式主析取范式:设命题公式设命题公式A A中含中含n n个命题变个命题变项，如果项，如果A A的析取范式中的简单合取式全是极小项，的析取范式中的简单合取式全是极小项，则称该析取范式为则称该析取范式为A A的主析取范式的主析取范式例如，例如，n=3,命题变项为命题变项为p,q,r时，时，(pq r)(p q r)m1 m3是是主析取范式主析取范式nA的主析取范式的主析取范式:与与A等值的主析取范式等值的主析取范式60主析取范式定义：主析取范式:设命题公式A中含n个命题变项，主析取范式主析取范式(续续)定定理理2.5任任何何命命题题公公式式的的主主析析取取范范式式都都是是存存在在的的,并并且且是是惟惟一一的的.用等值演算法求给定命题公式的主析取范式的步骤：用等值演算法求给定命题公式的主析取范式的步骤：(1)先求先求A的析取范式的析取范式A。(2)若若A的某简单合取式的某简单合取式B中不含命题变项中不含命题变项pi,也不含否定也不含否定 pi，则将将B展成如下形式展成如下形式BB 1B(pi pi)(B pi)(B pi)(3)将重复出现的命题变项、矛盾式及重复出现的极小项都将重复出现的命题变项、矛盾式及重复出现的极小项都“消去消去”，如，如p p用用p取代，取代，pp用用0取代，取代，mi mi用用mi 取代。取代。(4)将将极小项按由小到大的顺序排序极小项按由小到大的顺序排序.并用并用 表示，如表示，如m1 m2 m5用用(1,2,5)表示。表示。61主析取范式(续)定理2.5任何命题公式的主析取范式都是存主析取范式用途主析取范式用途n1：判断两命题公式是否等值：判断两命题公式是否等值由于任何命题公式的主析取范式都是唯一的，因而若由于任何命题公式的主析取范式都是唯一的，因而若AB，说明明A与与B有相同的主析取范式。有相同的主析取范式。反之，若反之，若A与与B有相同的主析取范式，必有有相同的主析取范式，必有AB。n2：判断命题公式的类型：判断命题公式的类型设设A是含是含n个命题变项的命题公式，个命题变项的命题公式，A为重言式，当且仅当为重言式，当且仅当A的主析取范式中含全部的主析取范式中含全部2n个极小项。个极小项。A为矛盾式，当且仅为矛盾式，当且仅当当A的主析取范式中不含任何极小项。若的主析取范式中不含任何极小项。若A的主析取范式中的主析取范式中至少含一个极小项，则至少含一个极小项，则A是可满足式。是可满足式。n3：求命题公式的成真和成假赋值。：求命题公式的成真和成假赋值。62主析取范式用途1：判断两命题公式是否等值62极大项极大项定定义义在在含含有有n个个命命题题变变项项的的简简单单析析取取式式中中，若若每每个个命命题题变变项项与与其其否否定定不不同同时时存存在在，而而两两者者之之一一必必出出现现且且仅仅出出现现一一次次，且且第第i（1 i n）个个命命题题变变项项或或其其否否定定出出现现在在从从左起的第左起的第i位上，称这样的简单析取式为位上，称这样的简单析取式为极大项极大项.说明：说明：nn个命题变项产生个命题变项产生2n个极大项。个极大项。2n个极大项均互不等值个极大项均互不等值n用用Mi表示第表示第i个极大项，将个极大项，将Mi里的命里的命题变项看成看成0，命，命题变项的否定看成的否定看成1，则每个极大每个极大项对应一个二一个二进制数，制数，也也对应一个十一个十进制数。二制数。二进制数正是制数正是该极大极大项的成假的成假赋值，十，十进制数制数i是该极大项成真赋值的十进制表示也是该极大项成真赋值的十进制表示也是该极大项抽象表示法的角码是该极大项抽象表示法的角码.63极大项定义在含有n个命题变项的简单析取式中，若每个命题变项由由p,q,r三个命题变项形成的极大项三个命题变项形成的极大项公式公式 成假成假赋值赋值名称名称 p q r p qr p q r p qr p q r p qr p q r p qr 000001010011100101110111M0M1M2M3M4M5M6M7 极大项极大项 64由p,q,r三个命题变项形成的极大项公式成假名称p知识回顾知识回顾n掌握对偶式定义掌握对偶式定义 对偶原理对偶原理 定理定理1.2n简单合取式、简单析取式、析取范式、合取范式、简单合取式、简单析取式、析取范式、合取范式、主析取范式、主合取范式定义主析取范式、主合取范式定义 n主析取范式、主合取范式的求法、表示意义、与主析取范式、主合取范式的求法、表示意义、与真值表之间的转化方式真值表之间的转化方式n极小项、极大项定义、二进制的成真赋值（成假极小项、极大项定义、二进制的成真赋值（成假赋值）与对应的十进制角标关系赋值）与对应的十进制角标关系65知识回顾掌握对偶式定义对偶原理定理1.265极小项与极大项极小项与极大项注意：注意：nmi(Mi)称为极小项称为极小项(极大项极大项)的名称的名称.mi与与Mi的关系的关系:mi Mi,Mi mi（结合定理合定理1.2理解）理解）n记忆理解极小理解极小项与极大与极大项的定的定义、取、取值、用法、用法时，重点，重点记忆一个，另一个利用上述关系式推一个，另一个利用上述关系式推导即可即可66极小项与极大项注意：66极小项与极大项极小项与极大项(续续)由由p,q两个命题变项形成的极小项与极大项两个命题变项形成的极小项与极大项 公式公式 成真赋值成真赋值名称名称 公式公式 成假赋成假赋值值名称名称 p q p q p q p q00011011m0m1m2m3 p qp q p q p q 00011011 M0M1M2M3 极小项极小项 极大项极大项 67极小项与极大项(续)由p,q两个命题变项形成的极小项与极大主合取范式主合取范式n定义：定义：主合取范式主合取范式:设命题公式设命题公式A A中含中含n n个命题变项，如果个命题变项，如果A A的合取范式中的简单的合取范式中的简单析取式全是极大项，则称该合取范式为析取式全是极大项，则称该合取范式为A A的主合取范式的主合取范式例如，例如，n=3,命题变项为命题变项为p,q,r时，时，(p qr)(p qr)M1 M5是是主合取范式主合取范式A的主合取范式的主合取范式:与与A等值的主合取范式等值的主合取范式68主合取范式定义：主合取范式:设命题公式A中含n个命题变项，主合取范式（续）主合取范式（续）n任意命题公式的主合取范式一定存在，且是唯任意命题公式的主合取范式一定存在，且是唯一的。一的。n求一命题公式求一命题公式A的主合取范式与求主析取范式的主合取范式与求主析取范式的步骤非常相似，也是先求出合取范式的步骤非常相似，也是先求出合取范式A。若。若A的某简单析取式的某简单析取式B中不含命题变项中不含命题变项pi,，也不也不含否定含否定 pi，则将将B展成如下形式展成如下形式：BB 0B(pi pi)(B pi)(B pi)69主合取范式（续）任意命题公式的主合取范式一定存在，且是唯一的主合取范式主合取范式(续续)n由由A的主析取范式求主合取范式的步骤为：的主析取范式求主合取范式的步骤为：(1):求出求出A的主析取范式中没包含的极小项的主析取范式中没包含的极小项 (2):求出与求出与(1)中极小项角码相同的极大项中极小项角码相同的极大项(3):由以上极大项构成的合取式为由以上极大项构成的合取式为A的主合取的主合取式。式。70主合取范式(续)由A的主析取范式求主合取范式的步骤为：70求公式的主范式求公式的主范式例例求公式求公式A=(pq)r的主析取范式与主合的主析取范式与主合 取范式取范式.(1)求主析取范式求主析取范式(pq)r(p q)r,（析取范式）（析取范式）(p q)(p q)(r r)(p qr)(p q r)m6 m7,71求公式的主范式例求公式A=(pq)r的主析取范式与求公式的主范式求公式的主范式(续续)r(p p)(q q)r(pq r)(p q r)(pq r)(p q r)m1 m3 m5 m7,代入代入并排序，得并排序，得(pq)rm1 m3 m5 m6 m7（主析取范式）主析取范式）72求公式的主范式(续)r72求公式的主范式求公式的主范式(续续)(2)求求A的主合取范式的主合取范式(pq)r(p r)(q r),（合取范式）（合取范式）p rp(qq)r(p q r)(pq r)M0 M2,73求公式的主范式(续)(2)求A的主合取范式73求公式的主范式求公式的主范式(续续)q r(pp)q r(p q r)(p q r)M0 M4,代入代入并排序，得并排序，得(pq)rM0 M2 M4（主合取范式）（主合取范式）74求公式的主范式(续)qr74主范式的用途主范式的用途与真值表相同与真值表相同(1)求公式的成真赋值和成假赋值求公式的成真赋值和成假赋值例如例如(pq)rm1 m3 m5 m6 m7，其成真赋值为其成真赋值为001,011,101,110,111，其余的赋值其余的赋值 000,010,100为为成假赋值成假赋值.类似地，由主合取范式也可立即求出成类似地，由主合取范式也可立即求出成 假赋值和成真赋值假赋值和成真赋值.75主范式的用途与真值表相同(1)求公式的成真赋值和成主范式的用途主范式的用途(续续)(2)判断公式的类型判断公式的类型设设A含含n个命题变项，则个命题变项，则A为重言式为重言式A的主析取范式含的主析取范式含2n个极小项个极小项A的主合取范式为的主合取范式为1.A为矛盾式为矛盾式A的主析取范式为的主析取范式为0A的主合析取范式含的主合析取范式含2n个极大项个极大项A为非重言式的可满足式为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项的主合取范式中至少含一个且不含全部极大项 76主范式的用途(续)(2)判断公式的类型76主范式的用途主范式的用途(续续)例例用主析取范式判断下述两个公式是否等值：用主析取范式判断下述两个公式是否等值：p(qr)与与(p q)r p(qr)与与(pq)r解解 p(qr)=m0 m1 m2 m3 m4 m5 m7(p q)r=m0 m1 m2 m3 m4 m5 m7(pq)r=m1 m3 m4 m5 m7显见，显见，中的两公式等值，而中的两公式等值，而的不等值的不等值.(3)判断两个公式是否等值判断两个公式是否等值说说明明：由由公公式式A的的主主析析取取范范式式确确定定它它的的主主合合取取范范式式，反反之之亦亦然然.用公式用公式A的真值表求的真值表求A的主范式的主范式.77主范式的用途(续)例用主析取范式判断下述两个公式是否等值：主范式的用途主范式的用途(续续)例例某公司要从赵、钱、孙、李、周五名新毕某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习业的大学生中选派一些人出国学习.选派必须选派必须满足以下条件：满足以下条件：(1)(1)若赵去，钱也去；若赵去，钱也去；(2)(2)李、周两人中至少有一人去；李、周两人中至少有一人去；(3)(3)钱、孙两人中有一人去且仅去一人；钱、孙两人中有一人去且仅去一人；(4)(4)孙、李两人同去或同不去；孙、李两人同去或同不去；(5)(5)若周去，则赵、钱也去若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出试用主析取范式法分析该公司如何选派他们出国？国？78主范式的用途(续)例某公司要从赵、钱、孙、李、周五名新例例(续续)解此类问题的步骤为：解此类问题的步骤为：将简单命题符号化将简单命题符号化写出各复合命题写出各复合命题写出由写出由中复合命题组成的合取式中复合命题组成的合取式 求求中所得公式的主析取范式中所得公式的主析取范式 79例(续)解此类问题的步骤为：79例例(续续)解解设设p：派赵去，：派赵去，q：派钱去，：派钱去，r：派孙去，：派孙去，s：派李去，：派李去，u：派周去：派周去.(1)(pq)(2)(s u)(3)(qr)(q r)(4)(r s)(rs)(5)(u(p q)(1)(5)构成的合取式为构成的合取式为A=(pq)(s u)(qr)(q r)(r s)(rs)(u(p q)80例(续)解设p：派赵去，q：派钱去，r：派孙去，80例例(续续)A(pq r su)(p qrs u)结论：由结论：由可知，可知，A的成真赋值为的成真赋值为00110与与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）周去（孙、李不去）.A的演算过程如下的演算过程如下:A(p q)(qr)(q r)(s u)(u(p q)(r s)(rs)（交换律（交换律)B1=(p q)(qr)(q r)(p qr)(pq r)(qr)（分分配配律）律）81例(续)A(pqrsu)例例(续续)B2=(s u)(u(p q)(su)(p q s)(p q u)（分配律）（分配律）B1 B2(p qr su)(pq r su)(qr su)(p qr s)(p qr u)再令再令B3=(r s)(rs)得得 AB1 B2 B3(pq r su)(p qrs u)注意：在以上演算中多次用矛盾律注意：在以上演算中多次用矛盾律要求：自己演算一遍要求：自己演算一遍 82例(续)B2=(su)(u(pq)822.5 命题逻辑的推理理论命题逻辑的推理理论 本节目标：本节目标：推理的形式结构推理的形式结构判断推理是否正确的方法判断推理是否正确的方法推理定律与推理规则推理定律与推理规则构造证明法构造证明法832.5命题逻辑的推理理论本节目标：83推理的形式结构推理的形式结构问题的引入问题的引入推理举例推理举例:(1)正项级数收敛当且仅当部分和上有界正项级数收敛当且仅当部分和上有界.(2)若若A C B D，则，则A B且且C D.推理推理:从前提推出结论的思维过程从前提推出结论的思维过程前提前提是指已知的命题公式，是指已知的命题公式，结论结论是从前提出发应用推理规则推出的命题公式是从前提出发应用推理规则推出的命题公式上面上面(1)是正确的推理，而是正确的推理，而(2)是错误的推理是错误的推理.证明证明:描述推理正确或错误的过程描述推理正确或错误的过程.84推理的形式结构问题的引入推理举例:84推理的形式结构推理的形式结构定定义义：若若(A1 A2 Ak)B为为重重言言式式,则则称称A1,A2,Ak推推出出结结论论B的的推推理理正正确确,B是是A1,A2,Ak的的逻逻辑辑结结论论或或有有效效结结论论。称称(A1 A2 Ak)B为为由由前前提提A1,A2,Ak推出结论推出结论B的推理的形式结构。的推理的形式结构。用用AB表示表示AB是重言式。是重言式。若由前提若由前提A1,A2,Ak 推出结论推出结论B的的推理正确，则记推理正确，则记作：作：A1 A2 AkB.85推理的形式结构定义：若(A1A2Ak)B判断推理是否正确的方法判断推理是否正确的方法由定义可知：判断推理是否正确的方法就是判断重由定义可知：判断推理是否正确的方法就是判断重言蕴涵式的方法：言蕴涵式的方法：真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法构造证明法构造证明法 说明：当命题变项比较少时，用前说明：当命题变项比较少时，用前3 3个方法比较方个方法比较方便便,此时采用此时采用形式结构形式结构“A1 A2 AkB”.而在构而在构造证明时，造证明时，采用采用“前提前提:A1,A2,Ak,结论结论:B”.86判断推理是否正确的方法由定义可知：判断推理是否正确的方法就是 实例实例例例判断下面推理是否正确判断下面推理是否正确(1)若今天是若今天是1号，则明天是号，则明天是5号号.今天是今天是1号号.所所以明天是以明天是5号号.解解设设p：今天是：今天是1号，号，q：明天是：明天是5号号.证明的形式结构为证明的形式结构为:(pq)pq证明（用等值演算法）证明（用等值演算法）(pq)pq(p q)p)q pq q1得证推理正确得证推理正确87实例例判断下面推理是否正确87实例实例(续续)(2)若今天是若今天是1号，则明天是号，则明天是5号号.明天是明天是5号号.所以今天是所以今天是1号号.解解设设p：今天是：今天是1号，号，q：明天是：明天是5号号.证明的形式结构为证明的形式结构为:(pq)qp证明（用主析取范式法）证明（用主析取范式法）(pq)qp(p q)qp(p q)q)p q p(pq)(pq)(pq)(p q)m0 m2 m3结果不含结果不含m1,故故01是成假赋值，所以推理不正确是成假赋值，