命题逻辑课件.ppt

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

1、命题逻辑命题逻辑ppt课件课件 例例下列句子中那些是命题？下列句子中那些是命题？(1)是无理数是无理数.(2)2+58.(3)x+53.(4)你有铅笔吗？你有铅笔吗？(5)这只兔子跑得真快呀！这只兔子跑得真快呀！(6)请不要讲话！请不要讲话！(7)我正在说谎话我正在说谎话.真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(3)(7)都不是命题都不是命题 6理发师悖论理发师悖论 n某乡村有一位理发师，一天他宣布：某乡村有一位理发师，一天他宣布：只给不自己只给不自己理发的人理发理发的人理发。这里就产生了问题：理发师给不。这里就产生了问题：理发师给不给自己理发

2、？给自己理发？n如果他给自己理发，他就是自己理发的人，按照如果他给自己理发，他就是自己理发的人，按照他的原则，他不能给自己理发；他的原则，他不能给自己理发；n如果他不给自己理发，他就是不自己理发的人，如果他不给自己理发，他就是不自己理发的人，按照他的原则，他就应该给自己理发。按照他的原则，他就应该给自己理发。n这就产生了矛盾。这就产生了矛盾。7命题的分类命题的分类 简单命题简单命题(原子命题原子命题)：简单陈述句构成的命题简单陈述句构成的命题 复合命题复合命题：由简单命题用联结词联结而成的命题由简单命题用联结词联结而成的命题8简单命题符号化简单命题符号化 在本书中用小写英文字母在本书中用小写英

3、文字母 p,q,r,pi,qi,ri(i1）表示简单命题，将表）表示简单命题，将表示命题的符号放在该命题的前面，称为命题符号化。示命题的符号放在该命题的前面，称为命题符号化。用用“1”表示真，用表示真，用“0”表示假表示假对简单命题而言，它的真值是确定的，因而又称为命题常项或命题常元。对简单命题而言，它的真值是确定的，因而又称为命题常项或命题常元。例如，令例如，令 p：是有理数，则是有理数，则 p 的真值为的真值为 0 q：2+5=7，则，则 q 的真值为的真值为 1 见课本例见课本例1.29联结词与复合命题联结词与复合命题 1.否定式与否定联结词否定式与否定联结词“”定定义义2.12.1设设

4、p为为任任一一命命题题，复复合合命命题题 “非非p”（或或 “p的的否否定定”）称称为为p的的否否定定式式，记记作作 p，符符号号 称称作作否否定定联联结结词词，并规定，并规定 p为真当且仅当（即：等价）为真当且仅当（即：等价）p为假为假2.合取式与合取联结词合取式与合取联结词“”定定义义2.22.2设设p,q为为两两命命题题,复复合合命命题题“p并并且且q”(”(或或“p与与q”)”)称称 为为p与与q的的合取式合取式，记作，记作pq，称作称作合取联结词合取联结词，并规，并规 定定 pq为真当且仅当为真当且仅当p与与q同时为真同时为真注意：描述合取式的灵活性与多样性注意：描述合取式的灵活性与

5、多样性 分清简单命题与复合命题分清简单命题与复合命题 10 例例将下列命题符号化将下列命题符号化.(1)王晓既用功又聪明王晓既用功又聪明.(2)王晓不仅聪明，而且用功王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功王晓虽然聪明，但不用功.(4)王晓不是不聪明，而是不用功王晓不是不聪明，而是不用功.(5)张辉与王丽都是三好学生张辉与王丽都是三好学生.(6)张辉与王丽是同学张辉与王丽是同学.解解令令p：王晓用功，：王晓用功，q：王晓聪明，则：王晓聪明，则(1)pq(2)pq(3)p q.11 例例(续续)(4)(p)q.令令r:张辉是三好学生，张辉是三好学生，s:王丽是三好学生王丽是三好学生(

6、5)rs.(6)令令t:张辉与王丽是同学，张辉与王丽是同学，t 是简单命题是简单命题.说明说明:(1)(4)说明描述合取式的灵活性与多样性说明描述合取式的灵活性与多样性.(5)中中“与与”联结的是句子的主语成分，因而联结的是句子的主语成分，因而(5)中句子是简单命题中句子是简单命题.12联结词与复合命题联结词与复合命题(续续)定义2.32.3 设 p,q为二命题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词，并规定 pq为假当且仅当p与q同时为假.即:pq为真当且仅当p与q至少有一个为真。此处定义的析取式pq表示的是一种相容性或，即允许p与q同时为真注意区分自然言语中“或”的

7、二义性。见课本描述。例例将下列命题符号化将下列命题符号化(1)2或或4是素数是素数.(2)2或或3是素数是素数.(3)4或或6是素数是素数.(4)小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨.(5)王晓红生于王晓红生于1975年或年或1976年年.3.析取式与析取联结词析取式与析取联结词“”13解解令令 p:2是素数是素数,q:3是素数是素数,r:4是素数是素数,s:6是素数是素数,则则 (1),(2),(3)均为相容或均为相容或.分别符号化为分别符号化为:pr,pq,rs,它们的真值分别为它们的真值分别为 1,1,0.而而 (4),(5)为排斥或为排斥或.令令 t:小元元拿一个苹

8、果，小元元拿一个苹果，u:小元元拿一个梨，小元元拿一个梨，则则 (4)符号化为符号化为 (t u)(tu).令令v:王晓红生于王晓红生于1975年年,w:王晓红生于王晓红生于1976年年,则则 (5)既可符号化为既可符号化为 (v w)(vw),又可又可符号化为符号化为 vw,为什么为什么?（看（看vw的的值值是多少？是多少？）14联结词与复合命题联结词与复合命题(续续)定定义义2.42.4设设p,q为为二二命命题题，复复合合命命题题“如如果果p,则则q”称称作作p与与q的的蕴蕴涵涵式式，记记作作pq，并并称称p是是蕴蕴涵涵式式的的前前件件，q为为蕴蕴涵涵式式的的后后件件.称称作作蕴蕴涵涵联联

9、结结词词，并规定，并规定，pq为假当且仅当为假当且仅当p 为真为真q 为假为假.4.蕴涵式与蕴涵联结词蕴涵式与蕴涵联结词“”15pq 的逻辑关系：的逻辑关系：q为为p的必要条件的必要条件 或或p p为为q q的充分条件的充分条件 （找（找关系时，要分清蕴涵式的关系时，要分清蕴涵式的前件前件与与后件，后件，即找准充分条件或必要条件）即找准充分条件或必要条件）“如果如果 p，则，则 q”的不同表述法很多：的不同表述法很多：若若 p，就，就 q（p是是q的充分条件的充分条件）只要只要 p，就，就 q（p是是q的充分条件的充分条件）p 仅当仅当 q（q是是p的必要条件的必要条件）只有只有 q 才才 p

10、（q是是p的必要条件的必要条件）除非除非 q,才才 p 或或 除非除非 q,否则非否则非 p，(必须记住必须记住)否则非否则非 可以理解为可以理解为 才才当当 p 为假时，为假时，pq 为真为真常出现的错误：不分充分与必要条件常出现的错误：不分充分与必要条件见课本中注意的两点事项见课本中注意的两点事项联结词与复合命题联结词与复合命题(续续)16 例例 设设p p:天冷，天冷，q q:小王穿羽绒服，小王穿羽绒服，将下列命题符号化将下列命题符号化 (1)只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷若小

11、王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.注意：注意：pq 与与 q p 等值（真值相同）等值（真值相同）pqpqpqpqqp qpqpqp17联结词与复合命题联结词与复合命题(续续)定定义义2.52.5设设p，q为为二二命命题题，复复合合命命题题“p当当且且仅仅当当q”称称作作p与与q的的等等价价式式，记记作作pq

12、，称称作作等等价价联联结结词词.pq为真当且仅当为真当且仅当p与与q同时为真或同时为假同时为真或同时为假.说明说明:(1)pq 的逻辑关系的逻辑关系:p与与q互为充分必要条件互为充分必要条件(2)pq为真当且仅当为真当且仅当p与与q同真或同假同真或同假5.等价式与等价联结词等价式与等价联结词“”18例例求下列复合命题的真值求下列复合命题的真值(1)2+24当且仅当当且仅当3+36.(2)2+24当且仅当当且仅当3是偶数是偶数.(3)2+24当且仅当当且仅当太阳从东方升起太阳从东方升起.(4)2+24当且仅当当且仅当美国位于非洲美国位于非洲.(5)函数函数 f(x)在在x0可导的充要条件是它在可

13、导的充要条件是它在x0连续连续.它们的真值分别为它们的真值分别为 1，0，1，0，0.19用联结词把各种各样的复合命题符号化用联结词把各种各样的复合命题符号化基本步骤：基本步骤：1：分析出各简单命题，将它们符号化；：分析出各简单命题，将它们符号化；2：使用合适的联结词，把简单命题逐个联：使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示。结起来，组成复合命题的符号化表示。注意析取联结词注意析取联结词 的应用的应用20联结词与复合命题联结词与复合命题(续续)以上给出了以上给出了5个联结词：个联结词：,，组成，组成一个联结词集合一个联结词集合,，联结词的优先顺序为：联结词的优先顺序

14、为：,;1:1:如果出现的联结词同级，又无括号时，则按如果出现的联结词同级，又无括号时，则按从左到右的顺序运算从左到右的顺序运算;2:2:若遇有括号时，应该先进行括号中的运算若遇有括号时，应该先进行括号中的运算.注意注意:本书中使用的本书中使用的括号全为圆括号（）括号全为圆括号（）.212.2命题公式命题公式命题变项与合式公式命题变项与合式公式公式的赋值公式的赋值真值表真值表命题的分类命题的分类重言式重言式矛盾式矛盾式可满足式可满足式22命题变项与合式公式命题变项与合式公式 命题常项命题常项：简单命题：简单命题 原子命题原子命题命题变项命题变项：真值不确定的陈述句：真值不确定的陈述句定义定义2

15、.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)形成的符号串才是合式公式。形成的符号串才是合式公式。注注:外层括号可以省去外层括号可以省去问问：命：命题题公式是命公式是命题吗题吗？不是，原因不是，原因为为：命：命题题公式中可能含有

16、命公式中可能含有命题变项题变项。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的

17、最高层次为的最高层次为k.则则A是是k层公式。层公式。24合式公式的层次合式公式的层次(续续)例如例如公式公式 p 0层层 p1层层 pq2层层(pq)r3层层 (p q)r)(r s)4层层25公式的赋值公式的赋值 定义定义2.8给给命命题题公公式式A中中的的所所有有的的命命题题变变项项p1,p2,pn指指定定一一组组真值称为对真值称为对A的一个的一个赋值赋值或或解释解释成真赋值成真赋值:使公式为真的赋值使公式为真的赋值成假赋值成假赋值:使公式为假的赋值使公式为假的赋值说明说明：赋值赋值=1 2 n之间不加标点符号，之间不加标点符号，i=0或或1.A中仅出现中仅出现p1,p2,pn，给，给A

18、赋值赋值 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真值表真值表 真值表真值表:将命题将命题公式公式A在所有赋值之下取值的情况在所有赋值之下取值的情况列成表，成为列成表，成为A的真的真值值表表 例例给出公式的真值表给出公式的真值表 A=(qp)qp 的的真值表真值表 p q qp(qp)q(qp)qp 00011011 1011 0001 111127例例B=(p q)q 的的真值表真值表 p q p p q(p q)(p q)q00011011 1

19、100110100100000实例实例28例例C=(p q)r 的的真值表真值表 p q r p q r(p q)r 000001010011100101110111 00111111 10101010 1110101029公式的类型公式的类型 定义定义2.92.9 设设A为一个命题公式为一个命题公式(1)若若A在在它它的的各各种种赋赋值值下下取取值值均均为为真真，则则称称A为为重重言言式式(也也称称永真式永真式)(2)若若A在在它它的的各各种种赋赋值值下下取取值值均均为为假假，则则称称A为为矛矛盾盾式式(也也称称永假式永假式)(3)若若A至少存在一组赋值是成真赋值，则称至少存在一组赋值是成真

20、赋值，则称A为为可满足式可满足式注意：重言式是可满足式，但反之不真注意：重言式是可满足式，但反之不真.上例中上例中A为重言式，为重言式，B为矛盾式，为矛盾式，C为可满足式为可满足式 A=(qp)qp，B=(p q)q，C=(p q)r30小结：小结：本节主要内容：本节主要内容：要理解所学的定义，利用所给的定义进行简单的判断和分析。要理解所学的定义，利用所给的定义进行简单的判断和分析。1：命题：命题 命题常项命题常项 命题变项命题变项 简单命题简单命题 复合命题的定义。复合命题的定义。2 2：联结词：联结词：,定义定义取值情况，对应的语言词汇取值情况，对应的语言词汇表达。表达。3：命题公式：命题

21、公式层次层次成真赋值成真赋值成假赋值成假赋值真值表的定义真值表的定义4：构造真值表的具体步骤，重言式：构造真值表的具体步骤，重言式矛盾式矛盾式可满足式可满足式定定义义31上节知识复习上节知识复习n1:定义：命题定义：命题 真真(假假)命题命题 命题常命题常(变变)项项 n2:五个联结词定义及取值情况，对应的五个联结词定义及取值情况，对应的 语言表达语言表达n3:复合命题符号化的步骤复合命题符号化的步骤n4:命题公式命题公式 命题公式的层次定义及判断命题公式的层次定义及判断n5:成真赋值成真赋值 成假赋值成假赋值 重言式重言式 矛盾式矛盾式 可满足式定义可满足式定义n6:真值表定义及构造步骤真值

22、表定义及构造步骤32随堂练习随堂练习1：写出命题、简单命题的定义。：写出命题、简单命题的定义。2：用符号定义五个联结词及其各自取值情况。：用符号定义五个联结词及其各自取值情况。3：写出蕴涵式的定义，分析前件与后件的关系，：写出蕴涵式的定义，分析前件与后件的关系，列出对应的语言表达形式。列出对应的语言表达形式。4：写出遇到析取联结词二义性时的判断方式及对应：写出遇到析取联结词二义性时的判断方式及对应 符号表示。符号表示。5：列出下面公式的真值表，说明各公式的层次：列出下面公式的真值表，说明各公式的层次 (pq)(pq)(qp)(p q)(p q)6：写出命题公式的定义：写出命题公式的定义33随堂

23、练习随堂练习7：命题符号化：命题符号化：a:只有天冷只有天冷,小王才穿羽绒服小王才穿羽绒服.b:除非天冷除非天冷,小王才穿羽绒服小王才穿羽绒服.c:除非小王穿羽绒服除非小王穿羽绒服,否则天不冷否则天不冷.d:如果天不冷如果天不冷,则小王不穿羽绒服则小王不穿羽绒服.e:小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.f:只有只有4是偶数，是偶数，3才能被才能被2整除。整除。g:选小王或小李中的一人当三好学生。选小王或小李中的一人当三好学生。h:小王现在在宿舍或在图书馆里。小王现在在宿舍或在图书馆里。342.3命题公式间的关系命题公式间的关系 学习目标：学习目标：等值式等值式基本等值式基本等

24、值式等值演算等值演算置换规则置换规则35等值式等值式 定义定义设设A、B为两命题，若等价式为两命题，若等价式AB是重言式，是重言式，则称则称A与与B等值的等值的，记作，记作AB，并称，并称AB是是等值式等值式说明说明：定义中符号：定义中符号“”不是联结词符，它只是当不是联结词符，它只是当A与与B等值时的一种记法。注意区分等值时的一种记法。注意区分“”、“=”和和“”可以可以用真值表验证两个公式是否等值用真值表验证两个公式是否等值等价关系具有自反性、对称性、传递性。等价关系具有自反性、对称性、传递性。请验证：请验证：p(qr)(p q)r p(qr)(pq)r36 用真值表法的验证方式用真值表法

25、的验证方式n 设设A、B为两命题，由定义判断为两命题，由定义判断A与与B是否是否等值，应判断等值，应判断AB是否为重言式，若是否为重言式，若AB的真值表最后一列全为的真值表最后一列全为1，则，则AB为重言式，为重言式，因而因而AB，但最后一列全为，但最后一列全为1当且仅当在各当且仅当在各赋值之下，赋值之下，A与与B的真值相同。因而判断的真值相同。因而判断A与与B是否等值等价于判断是否等值等价于判断A、B的真值表是的真值表是否相同。否相同。37基本等值式基本等值式利用真值表法可以验证很多等值式：利用真值表法可以验证很多等值式：n下面下面24个重要的等值式，是学好数理逻辑个重要的等值式，是学好数理

26、逻辑的关键基础，应当牢记！的关键基础，应当牢记！n在下面的公式中，在下面的公式中，A、B、C代表任意的代表任意的 命题公式。命题公式。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基本等值式基本等值式(续续)德德摩根律摩根律 :10.(A B)AB11.(A B)AB吸收律吸收律:12.A(A B)A,13.A(A B)A零律零律:14.A

27、 11,15.A 00同一律同一律:16.A 0A,17.A 1A排中律排中律:18.AA1矛盾律矛盾律:19.AA040基本等值式基本等值式(续续)蕴涵等值式蕴涵等值式:20.ABA B等价等值式等价等值式:21.AB(AB)(BA)假言易位假言易位:22.ABBA等价否定等值式等价否定等值式:23.ABAB归谬论归谬论:24.(AB)(AB)A注意注意:A,B,C代表任意的命题公式代表任意的命题公式牢记这些等值式是继续学习的基础牢记这些等值式是继续学习的基础41等值演算与置换规则等值演算与置换规则 等值演算等值演算:由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程置

28、换定理置换定理：设：设(A)是含命题公式是含命题公式A的命题，的命题，若若AB,则则(B)(A)等值演算的基础：等值演算的基础：(1)等值关系的性质：自反、对称、传递等值关系的性质：自反、对称、传递(2)基本的等值式基本的等值式(3)置换规则置换规则42应用举例应用举例证明两个公式等值证明两个公式等值 例例1证明证明p(qr)(p q)r证证p(qr)p(q r)（蕴涵等值式）（蕴涵等值式）(pq)r（结合律）（结合律）(p q)r（德摩根律）（德摩根律）(p q)r（蕴涵等值式）（蕴涵等值式）说明说明:也可以从右边开始演算（请做一遍）也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故

29、省略不写因为每一步都用置换规则，故省略不写 熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出 43应用举例应用举例证明两个公式不等值证明两个公式不等值例例2证明证明:p(qr)(pq)r用等值演算不能直接证明两个公式不等值用等值演算不能直接证明两个公式不等值,证明两证明两个公式不等值的基本思想是找到一个赋值使一个成个公式不等值的基本思想是找到一个赋值使一个成真真,另一个成假另一个成假.方法一方法一真值表法（自己证）真值表法（自己证）方法二方法二观察赋值法观察赋值法.容易看出容易看出000,010等是左边的等是左边的成真赋值，是右边的成假赋值成真赋值，是右边的成假赋值.方法三方法三用

30、等值演算先化简两个公式，再观察用等值演算先化简两个公式，再观察.44应用举例应用举例判断公式类型判断公式类型 例例3 3用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1)q(pq)解解 q(pq)q(p q)（蕴涵等值式）（蕴涵等值式）q(pq)（德摩根律）（德摩根律）p(qq)（交换律，结合律）（交换律，结合律）p 0（矛盾律）（矛盾律）0（零律）（零律）由最后一步可知，该式为矛盾式由最后一步可知，该式为矛盾式.45例例3(续续)(2)(pq)(qp)解解(pq)(qp)(p q)(qp)（蕴涵等值式）（蕴涵等值式）(p q)(p q)（交换律）（交换律）1由最后一步可知，该

31、式为重言式由最后一步可知，该式为重言式.问：最后一步为什么等值于问：最后一步为什么等值于1？46例例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本节

32、小结n熟悉等值、等值演算的定义熟悉等值、等值演算的定义n会用真值表法判断等值会用真值表法判断等值n记熟会用记熟会用24个重要的等值式个重要的等值式482.4主范式与判定为题主范式与判定为题 学习目标：学习目标：析取范式与合取范式析取范式与合取范式 主析取范式与主合取范式主析取范式与主合取范式 49析取范式与合取范式析取范式与合取范式 简简单单析析取取式式:仅仅由由有有限限个个命命题题变变项项或或其其否否定定构构成成的的析取式称为简单析取式。析取式称为简单析取式。如如p,q,pq,p q r,简简单单合合取取式式:仅仅由由有有限限个个命命题题变变项项或或其其否否定定构构成成的的合取式称为简单合取

33、式。合取式称为简单合取式。如如p,q,pq,p q r,由定由定义义可知：可知：1:一一个个简简单单析析取取式式是是重重言言式式，当当且且仅仅当当它它同同时时含含一一个个命命题题变变项项及其否定。及其否定。2:一一个个简简单单合合取取式式是是矛矛盾盾式式，当当且且仅仅当当它它同同时时含含一一个个命命题题变变项项及其否定。及其否定。50 析取范式与合取范式析取范式与合取范式(续续)析析取取范范式式:仅仅由由有有限限个个简简单单合合取取式式组组成成的的析析取取式式称称为为析析取取范范式式。A=A1 A2Ar,其其中中A1,A2,Ar是是简单合取式。简单合取式。A A是析取范式。是析取范式。合合取取

34、范范式式:仅仅由由有有限限个个简简单单析析取取式式组组成成的的合合取取式式称称为为合合取取范范式式。A=A1 A2Ar,其其中中A1,A2,Ar是是简单析取式。简单析取式。A A是合取范式。是合取范式。显然：任何析取范式的对偶式为合取范式，显然：任何析取范式的对偶式为合取范式，任何合取范式的对偶式为析取范式，任何合取范式的对偶式为析取范式，51析取范式与合取范式析取范式与合取范式(续续)析取范式与合取范式有下列性质：析取范式与合取范式有下列性质：n1：一个析取范式是矛盾式，当且一个析取范式是矛盾式，当且仅仅当它的当它的每个每个简单简单合取式都是矛盾式。合取式都是矛盾式。n2：一个合取范式是重言

35、式，当且一个合取范式是重言式，当且仅仅当它的当它的每个每个简单简单析取式都是重言。析取式都是重言。52析取范式与合取范式析取范式与合取范式(续续)范式范式:析取范式与合取范式的总称析取范式与合取范式的总称公式公式A的析取范式的析取范式:与与A等值的析取范式等值的析取范式公式公式A的合取范式的合取范式:与与A等值的合取范式等值的合取范式说明：说明：单单个个命命题题变变项项及及其其否否定定既既是是简简单单析析取取式式，又又是是简简单单合取式合取式形如形如 pq r,p qr 的公式既是析取范式，的公式既是析取范式，又是合取范式又是合取范式 (为什么为什么?)53 命题公式的范式命题公式的范式 定定

36、理理（范范式式存存在在定定理理）任任何何命命题题公公式式都都存存在在着着与与之之等等值值的的析取范式和合取范式析取范式和合取范式.求公求公式式A的范式的步骤：的范式的步骤：(1)由由于于,是是全全功功能能集集，因因而而若若A中中含含联联结结词词,等等，可可用用基基本本的的等等值值式式及及置置换换规规则则将将这这些些联联结结词词消去。消去。(2)否定联结词否定联结词 的内移或消去的内移或消去(3)使用分配律使用分配律 对对 分配（求析取范式）分配（求析取范式）对对 分配（求合取范式）分配（求合取范式）公式的范式存在，但不惟一，这是它的局限性公式的范式存在，但不惟一，这是它的局限性 54求公式的范

37、式举例求公式的范式举例 例例求下列公式的析取范式与合取范式求下列公式的析取范式与合取范式(1)A=(pq)r解解 (pq)r(pq)r（消去（消去）pqr（结合律）（结合律）这既是这既是A的析取范式（由的析取范式（由3个简单合取式组成的析个简单合取式组成的析取式），又是取式），又是A的合取范式（由一个简单析取式的合取范式（由一个简单析取式组成的合取式）组成的合取式）55求公式的范式举例求公式的范式举例(续续)(2)B=(pq)r解解 (pq)r (pq)r（消去第一个（消去第一个）(pq)r（消去第二个（消去第二个）(p q)r（否定号内移（否定号内移德摩根律）德摩根律）这一步已为析取范式（两

38、个简单合取式构成）这一步已为析取范式（两个简单合取式构成）继续：继续：(p q)r(p r)(q r)（对对 分配律）分配律）这一步得到合取范式（由两个简单析取式构成）这一步得到合取范式（由两个简单析取式构成）56 极小项极小项定定义义在在含含n个个命命题题变变项项的的简简单单合合取取式式中中，若若每每个个命命题题变变项项与与其其否否定定不不同同时时存存在在，而而两两者者之之一一必必出出现现且且仅仅出出现现一一次次，且且第第i（1 i n）个个命命题题变变项项或或其其否否定定出出现现在在从从左左起起的的第第i位位上上（若若命命题题变变项项无无角角标标，则则按按字字典典顺顺序序排排序序），称称这

39、这样的简单合取式为样的简单合取式为极小项极小项.说明：说明：nn个命题变项产生个命题变项产生2n个极小项。个极小项。2n个极小项均互不等值个极小项均互不等值n用用mi表示第表示第i个极小项，将个极小项，将mi里的命里的命题变项题变项看成看成1，命，命题题变项变项的否定看成的否定看成0，则则每个极小每个极小项对应项对应一个二一个二进进制数，也制数，也对应对应一个十一个十进进制数。二制数。二进进制数正是制数正是该该极小极小项项的成真的成真赋值赋值，十十进进制数制数i是该极小项成真赋值的十进制表示也是该极小是该极小项成真赋值的十进制表示也是该极小项抽象表示法的角码项抽象表示法的角码.57公式公式 成

40、真成真赋值赋值名称名称 p qr p q r p qr p q rp q rp q rp qrp q r000001010011100101110111m0m1m2m3m4m5m6m7极小项极小项 由由p,q,r三个命题变项形成的极小项三个命题变项形成的极小项58知识回顾知识回顾n1:定义：排斥或定义：排斥或 与非式与非式 或非式或非式 全功能集全功能集 冗余的（独立的）联结词冗余的（独立的）联结词n2:对偶式对偶式 对偶原理对偶原理 简单合取式简单合取式 简单析取式简单析取式 析取范式与合取范式析取范式与合取范式 极小项极小项n3:求公式求公式A的范式的步骤的范式的步骤59主析取范式主析取范

41、式n定义：定义：主析取范式主析取范式:设命题公式设命题公式A A中含中含n n个命题变个命题变项，如果项，如果A A的析取范式中的简单合取式全是极小项，的析取范式中的简单合取式全是极小项，则称该析取范式为则称该析取范式为A A的主析取范式的主析取范式例如，例如，n=3,命题变项为命题变项为p,q,r时，时，(pq r)(p q r)m1 m3是是主析取范式主析取范式nA的主析取范式的主析取范式:与与A等值的主析取范式等值的主析取范式60主析取范式主析取范式(续续)定定理理2.5任任何何命命题题公公式式的的主主析析取取范范式式都都是是存存在在的的,并并且且是是惟惟一一的的.用等值演算法求给定命题

42、公式的主析取范式的步骤：用等值演算法求给定命题公式的主析取范式的步骤：(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 m

43、5用用(1,2,5)表示。表示。61主析取范式用途主析取范式用途n1：判断两命题公式是否等值：判断两命题公式是否等值由于任何命题公式的主析取范式都是唯一的，因而若由于任何命题公式的主析取范式都是唯一的，因而若AB，说说明明A与与B有相同的主析取范式。有相同的主析取范式。反之，若反之，若A与与B有相同的主析取范式，必有有相同的主析取范式，必有AB。n2：判断命题公式的类型：判断命题公式的类型设设A是含是含n个命题变项的命题公式，个命题变项的命题公式，A为重言式，当且仅当为重言式，当且仅当A的主析取范式中含全部的主析取范式中含全部2n个极小项。个极小项。A为矛盾式，当且仅为矛盾式，当且仅当当A的主

44、析取范式中不含任何极小项。若的主析取范式中不含任何极小项。若A的主析取范式中的主析取范式中至少含一个极小项，则至少含一个极小项，则A是可满足式。是可满足式。n3：求命题公式的成真和成假赋值。：求命题公式的成真和成假赋值。62极大项极大项定定义义在在含含有有n个个命命题题变变项项的的简简单单析析取取式式中中，若若每每个个命命题题变变项项与与其其否否定定不不同同时时存存在在，而而两两者者之之一一必必出出现现且且仅仅出出现现一一次次，且且第第i（1 i n）个个命命题题变变项项或或其其否否定定出出现现在在从从左起的第左起的第i位上，称这样的简单析取式为位上，称这样的简单析取式为极大项极大项.说明：说

45、明：nn个命题变项产生个命题变项产生2n个极大项。个极大项。2n个极大项均互不等值个极大项均互不等值n用用Mi表示第表示第i个极大项，将个极大项，将Mi里的命里的命题变项题变项看成看成0，命，命题题变项变项的否定看成的否定看成1，则则每个极大每个极大项对应项对应一个二一个二进进制数，制数，也也对应对应一个十一个十进进制数。二制数。二进进制数正是制数正是该该极大极大项项的成假的成假赋值赋值，十，十进进制数制数i是该极大项成真赋值的十进制表示也是该极大项成真赋值的十进制表示也是该极大项抽象表示法的角码是该极大项抽象表示法的角码.63由由p,q,r三个命题变项形成的极大项三个命题变项形成的极大项公式

46、公式 成假成假赋值赋值名称名称 p q r p qr p q r p qr p q r p qr p q r p qr 000001010011100101110111M0M1M2M3M4M5M6M7 极大项极大项 64知识回顾知识回顾n掌握对偶式定义掌握对偶式定义 对偶原理对偶原理 定理定理1.2n简单合取式、简单析取式、析取范式、合取范式、简单合取式、简单析取式、析取范式、合取范式、主析取范式、主合取范式定义主析取范式、主合取范式定义 n主析取范式、主合取范式的求法、表示意义、与主析取范式、主合取范式的求法、表示意义、与真值表之间的转化方式真值表之间的转化方式n极小项、极大项定义、二进制的

47、成真赋值（成假极小项、极大项定义、二进制的成真赋值（成假赋值）与对应的十进制角标关系赋值）与对应的十进制角标关系65极小项与极大项极小项与极大项注意：注意：nmi(Mi)称为极小项称为极小项(极大项极大项)的名称的名称.mi与与Mi的关系的关系:mi Mi,Mi mi（结结合定理合定理1.2理解）理解）n记忆记忆理解极小理解极小项项与极大与极大项项的定的定义义、取、取值值、用法、用法时时，重点，重点记忆记忆一个，另一个利用上述关系式推一个，另一个利用上述关系式推导导即可即可66极小项与极大项极小项与极大项(续续)由由p,q两个命题变项形成的极小项与极大项两个命题变项形成的极小项与极大项 公式公

48、式 成真赋值成真赋值名称名称 公式公式 成假赋成假赋值值名称名称 p q p q p q p q00011011m0m1m2m3 p qp q p q p q 00011011 M0M1M2M3 极小项极小项 极大项极大项 67主合取范式主合取范式n定义：定义：主合取范式主合取范式:设命题公式设命题公式A A中含中含n n个命题变项，如果个命题变项，如果A A的合取范式中的简单的合取范式中的简单析取式全是极大项，则称该合取范式为析取式全是极大项，则称该合取范式为A A的主合取范式的主合取范式例如，例如，n=3,命题变项为命题变项为p,q,r时，时，(p qr)(p qr)M1 M5是是主合取范

49、式主合取范式A的主合取范式的主合取范式:与与A等值的主合取范式等值的主合取范式68主合取范式（续）主合取范式（续）n任意命题公式的主合取范式一定存在，且是唯任意命题公式的主合取范式一定存在，且是唯一的。一的。n求一命题公式求一命题公式A的主合取范式与求主析取范式的主合取范式与求主析取范式的步骤非常相似，也是先求出合取范式的步骤非常相似，也是先求出合取范式A。若。若A的某简单析取式的某简单析取式B中不含命题变项中不含命题变项pi,，也不也不含否定含否定 pi，则则将将B展成如下形式展成如下形式：BB 0B(pi pi)(B pi)(B pi)69主合取范式主合取范式(续续)n由由A的主析取范式求

50、主合取范式的步骤为：的主析取范式求主合取范式的步骤为：(1):求出求出A的主析取范式中没包含的极小项的主析取范式中没包含的极小项 (2):求出与求出与(1)中极小项角码相同的极大项中极小项角码相同的极大项(3):由以上极大项构成的合取式为由以上极大项构成的合取式为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求公式的主范式求公式的主范式(续续)r(p p