1、命题逻辑命题逻辑ppt课件课件2 命题逻辑3第第2章章 命题逻辑命题逻辑 2.1 命题及其表示命题及其表示2.2 命题公式命题公式2.3 命题公式间的关系命题公式间的关系2.4 主范式与判定定理主范式与判定定理2.5 命题逻辑的推理理论命题逻辑的推理理论42.1 命题及其表示命题及其表示 n命题与真值命题与真值n原子命题原子命题n复合命题复合命题n命题常项命题常项n命题变项命题变项n联结词联结词 5命题与真值命题与真值 命题命题: 能判断真假的陈述句。这种陈述句的判断只有两种可能：一种是能判断真假的陈述句。这种陈述句的判断只有两种可能：一种是 正确的判断，一种是错误的判断。称判断为正确的命题的
2、真值（或正确的判断，一种是错误的判断。称判断为正确的命题的真值（或 值）为真，称判断为错误的命题的真值（或值）为假。值）为真，称判断为错误的命题的真值（或值）为假。 因此又可称因此又可称命题是具有唯一真值的陈述句命题是具有唯一真值的陈述句或或判断结果惟一的陈述句判断结果惟一的陈述句 命题的真值命题的真值: 判断的结果判断的结果真值的取值真值的取值: 真与假真与假 二者取一二者取一真命题真命题: 真值为真的命题真值为真的命题假命题假命题: 真值为假的命题真值为假的命题注意注意: 感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是命题陈述句
3、中的悖论以及判断结果不惟一确定的也不是命题 6 例例 下列句子中那些是命题？下列句子中那些是命题？ (1) 是无理数是无理数. (2) 2 + 5 8. (3) x + 5 3. (4) 你有铅笔吗？你有铅笔吗？ (5) 这只兔子跑得真快呀！这只兔子跑得真快呀！ (6) 请不要讲话！请不要讲话！ (7) 我正在说谎话我正在说谎话.真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(3)(7)都不是命题都不是命题 27理发师悖论理发师悖论 n某乡村有一位理发师，一天他宣布：某乡村有一位理发师，一天他宣布：只给不自己只给不自己理发的人理发理发的人理发。这里就产
4、生了问题：理发师给不。这里就产生了问题：理发师给不给自己理发？给自己理发？n如果他给自己理发，他就是自己理发的人，按照如果他给自己理发，他就是自己理发的人，按照他的原则，他不能给自己理发；他的原则，他不能给自己理发；n如果他不给自己理发，他就是不自己理发的人，如果他不给自己理发，他就是不自己理发的人，按照他的原则，他就应该给自己理发。按照他的原则，他就应该给自己理发。n这就产生了矛盾。这就产生了矛盾。 8命题的分类命题的分类 简单命题简单命题( (原子命题原子命题) )： 简单陈述句构成的命题简单陈述句构成的命题 复合命题复合命题： 由简单命题用联结词联结而成的命题由简单命题用联结词联结而成的
5、命题 9简单命题符号化简单命题符号化 2在本书中用小写英文字母在本书中用小写英文字母 p, q, r, , ,pi, ,qi, ,ri (i1）表示简单命题，将）表示简单命题，将表示命题的符号放在该命题的前面，称为命题符号化。表示命题的符号放在该命题的前面，称为命题符号化。 用用“1”表示真，用表示真，用“0”表示假表示假对简单命题而言，它的真值是确定的，因而又称为命题常项或命题常元。对简单命题而言，它的真值是确定的，因而又称为命题常项或命题常元。例如，令例如，令 p： 是有理数，则是有理数，则 p 的真值为的真值为 0 q：2 + 5 = 7，则，则 q 的真值为的真值为 1 见课本例见课本
6、例1.210联结词与复合命题联结词与复合命题 1.否定式与否定联结词否定式与否定联结词“ ” 定义定义2.12.1 设设p为任一命题，复合命题为任一命题，复合命题 “ “非非p”（或（或 “ “p的的否定否定”）称为）称为p的的否定式否定式，记作，记作 p，符号，符号 称作称作否定联否定联结词结词，并规定，并规定 p 为真当且仅当（即：等价）为真当且仅当（即：等价）p为假为假2.合取式与合取联结词合取式与合取联结词“” 定义定义 2.22.2设设p, ,q为两命题为两命题, ,复合命题复合命题“p并且并且q”(”(或或“p与与q”)”)称称 为为p与与q的的合取式合取式，记作，记作pq，称作称
7、作合取联结词合取联结词，并规，并规 定定 pq为真当且仅当为真当且仅当p与与q同时为真同时为真注意：描述合取式的灵活性与多样性注意：描述合取式的灵活性与多样性 分清简单命题与复合命题分清简单命题与复合命题 11 例例 将下列命题符号化将下列命题符号化. (1) 王晓既用功又聪明王晓既用功又聪明. (2) 王晓不仅聪明，而且用功王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功王晓虽然聪明，但不用功. (4) 王晓不是不聪明，而是不用功王晓不是不聪明，而是不用功. (5) 张辉与王丽都是三好学生张辉与王丽都是三好学生. (6) 张辉与王丽是同学张辉与王丽是同学. 解解 令令 p：王晓用功，
8、：王晓用功，q：王晓聪明，则：王晓聪明，则 (1) pq (2) pq (3) p q.12 例例 (续续) (4) ( p) q.令令 r : 张辉是三好学生，张辉是三好学生，s :王丽是三好学生王丽是三好学生 (5) rs. (6) 令令 t : 张辉与王丽是同学，张辉与王丽是同学，t 是简单命题是简单命题 .说明说明: (1)(4)说明描述合取式的灵活性与多样性说明描述合取式的灵活性与多样性. (5) 中中“与与”联结的是句子的主语成分，因而联结的是句子的主语成分，因而(5)中句子是简单命题中句子是简单命题.13联结词与复合命题联结词与复合命题( (续续) ) 定义2.32.3 设 p,
9、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.析取式与析取联结词析取式与析取联结词“”14解解 令令 p:2是
10、素数是素数, 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),
11、 又可又可符号化为符号化为 vw , 为什么为什么? （看（看vw 的值是多少？的值是多少？）15联结词与复合命题联结词与复合命题( (续续) ) 定义定义2.42.4 设设 p,q为二命题，复合命题为二命题，复合命题 “如果如果p,则则q” 称作称作p与与q的的蕴涵式蕴涵式，记作，记作pq，并称，并称p是蕴涵式是蕴涵式的的前件前件，q为蕴涵式的为蕴涵式的后件后件. 称作称作蕴涵联结词蕴涵联结词，并规定，并规定，pq为假当且仅当为假当且仅当 p 为真为真 q 为假为假.4.蕴涵式与蕴涵联结词蕴涵式与蕴涵联结词“”16pq 的逻辑关系：的逻辑关系：q为为p的必要条件的必要条件 或或p p为为q
12、q的充分条件的充分条件 （找（找关系时，要分清蕴涵式的关系时，要分清蕴涵式的前件前件与与后件，后件， 即找准充分条件或必要条件）即找准充分条件或必要条件）“如果如果 p，则，则 q ” 的不同表述法很多：的不同表述法很多： 若若 p，就，就 q（ p是是q的充分条件的充分条件 ） 只要只要 p，就，就 q （ p是是q的充分条件的充分条件 ） p 仅当仅当 q （ q是是p的必要条件的必要条件 ） 只有只有 q 才才 p （ q是是p的必要条件的必要条件 ） 除非除非 q, 才才 p 或或 除非除非 q, 否则非否则非 p，( (必须记住必须记住) )否则非否则非 可以理解为可以理解为 才才当
13、当 p 为假时，为假时，pq 为真为真常出现的错误：不分充分与必要条件常出现的错误：不分充分与必要条件见课本中注意的两点事项见课本中注意的两点事项联结词与复合命题联结词与复合命题( (续续) )17 例例 设设 p p: :天冷，天冷，q q: :小王穿羽绒服，小王穿羽绒服， 将下列命题符号化将下列命题符号化 (1) 只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服除非天冷
14、，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.注意：注意： pq 与与 q p 等值（真值相同）等值（真值相同） pqpqpqpqqp qpqpqp18联结词与复合命题联结词与复合命题( (续续) )定义定义2.52.5 设设p，q为二命题，复合命题为二命题，复合命题 “p当且仅当当且仅当q”称作称作p与与q的的等价式等价式，记作，记作pq，称作称作等价联结等价联结词词. pq为真当且仅当为真当且仅当p与与q同时为真或同时为
15、假同时为真或同时为假.说明说明: (1) pq 的逻辑关系的逻辑关系:p与与q互为充分必要条件互为充分必要条件 (2) pq为真当且仅当为真当且仅当p与与q同真或同假同真或同假5.等价式与等价联结词等价式与等价联结词“”19例例 求下列复合命题的真值求下列复合命题的真值 (1) 2 + 2 4 当且仅当当且仅当 3 + 3 6. (2) 2 + 2 4 当且仅当当且仅当 3 是偶数是偶数. (3) 2 + 2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起. (4) 2 + 2 4 当且仅当当且仅当 美国位于非洲美国位于非洲. (5) 函数函数 f (x) 在在x0 可导的充要条件是它在可
16、导的充要条件是它在 x0连续连续. 它们的真值分别为它们的真值分别为 1，0，1，0，0.20用联结词把各种各样的复合命题符号化用联结词把各种各样的复合命题符号化基本步骤：基本步骤：1：分析出各简单命题，将它们符号化；：分析出各简单命题，将它们符号化；2：使用合适的联结词，把简单命题逐个联：使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示。结起来，组成复合命题的符号化表示。注意析取联结词注意析取联结词的应用的应用21联结词与复合命题联结词与复合命题( (续续) )以上给出了以上给出了5个联结词：个联结词： , , , , ，组成，组成一个联结词集合一个联结词集合 , , ,
17、, ， 联结词的优先顺序为：联结词的优先顺序为： , , , , ; 1:1:如果出现的联结词同级，又无括号时，则按如果出现的联结词同级，又无括号时，则按从左到右的顺序运算从左到右的顺序运算; 2:2:若遇有括号时，应该先进行括号中的运算若遇有括号时，应该先进行括号中的运算. 注意注意: : 本书中使用的本书中使用的 括号全为圆括号（）括号全为圆括号（）. 222.2 命题公式命题公式命题变项与合式公式命题变项与合式公式公式的赋值公式的赋值真值表真值表命题的分类命题的分类 重言式重言式 矛盾式矛盾式 可满足式可满足式23命题变项与合式公式命题变项与合式公式 命题常项命题常项：简单命题：简单命题
18、 原子命题原子命题命题变项命题变项：真值不确定的陈述句：真值不确定的陈述句定义定义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)形成的符号串才是合式公式。形成的符号串才是合式公式。注注:
19、外层括号可以省去外层括号可以省去 问：命题公式是命题吗？问：命题公式是命题吗？不是，原因为：命题公式中可能含有命题变项。不是，原因为：命题公式中可能含有命题变项。24合式公式的层次合式公式的层次 定义定义 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的
20、层次及的层次及n同同(b)； (d) A=BC, 其中其中B,C的层次及的层次及n同同(b)； (e) A=BC, 其中其中B,C的层次及的层次及n同同(b). (3)若若A的最高层次为的最高层次为k.则则A是是k层公式。层公式。25合式公式的层次合式公式的层次 (续续) 例如例如 公式公式 p 0层层 p 1层层 pq 2层层 (pq)r 3层层 ( p q) r)( r s) 4层层26公式的赋值公式的赋值 定义定义2.8 给命题公式给命题公式A中的所有的命题变项中的所有的命题变项 p1, p2, , pn指定一组指定一组真值称为对真值称为对A的一个的一个赋值赋值或或 解释解释成真赋值成真
21、赋值: 使公式为真的赋值使公式为真的赋值成假赋值成假赋值: 使公式为假的赋值使公式为假的赋值说明说明： 赋值赋值 = 1 2 n之间不加标点符号，之间不加标点符号， i=0或或1. 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 含含n个变项的公式有个变项的公式有2n个赋值个赋值. 27真值表真值表 真值表真值表: 将命题将命题公式公式A在所有赋值之下取值的情况在所有赋值之下取值的情况列成表，成为列成表，成
22、为A的真值表的真值表 例例 给出公式的真值表给出公式的真值表 A= (qp) qp 的的真值表真值表 p q qp (qp) q (qp) qp 0 00 11 01 1 1011 0001 111128例例 B = ( p q) q 的的真值表真值表 p q p p q ( p q) ( p q) q0 00 11 01 1 1100110100100000实例实例29例例 C= (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 111010103
23、0公式的类型公式的类型 定义定义2.92.9 设设A为一个命题公式为一个命题公式 (1) 若若A在它的各种赋值下取值均为真，在它的各种赋值下取值均为真，则称则称A为为重言式重言式( (也也称称永真式永真式) ) (2) 若若A在它的各种赋值下取值均为假在它的各种赋值下取值均为假，则称，则称A为为矛盾式矛盾式( (也也称称永假式永假式) ) (3) 若若A至少存在一组赋值是成真赋值，则称至少存在一组赋值是成真赋值，则称A为为可满足式可满足式注意：重言式是可满足式，但反之不真注意：重言式是可满足式，但反之不真. .上例中上例中A为重言式，为重言式，B为矛盾式，为矛盾式，C为可满足式为可满足式 A=
24、 (qp) qp，B = ( p q) q，C= (p q)r31小结：小结：本节主要内容：本节主要内容：要理解所学的定义，利用所给的定义进行简单的判断和分析。要理解所学的定义，利用所给的定义进行简单的判断和分析。1：命题：命题 命题常项命题常项 命题变项命题变项 简单命题简单命题 复合命题的定义。复合命题的定义。2 2：联结词：联结词： , , , , 定义定义 取值情况，对应的语言词汇取值情况，对应的语言词汇表达。表达。3：命题公式：命题公式 层次层次 成真赋值成真赋值 成假赋值成假赋值 真值表的定义真值表的定义4：构造真值表的具体步骤，重言式：构造真值表的具体步骤，重言式 矛盾式矛盾式
25、可满足式可满足式 定定义义32上节知识复习上节知识复习n1:定义：命题定义：命题 真真(假假)命题命题 命题常命题常(变变)项项 n2:五个联结词定义及取值情况，对应的五个联结词定义及取值情况，对应的 语言表达语言表达n3:复合命题符号化的步骤复合命题符号化的步骤n4:命题公式命题公式 命题公式的层次定义及判断命题公式的层次定义及判断n5:成真赋值成真赋值 成假赋值成假赋值 重言式重言式 矛盾式矛盾式 可满足式定义可满足式定义n6:真值表定义及构造步骤真值表定义及构造步骤33随堂练习随堂练习1：写出命题、简单命题的定义。：写出命题、简单命题的定义。2：用符号定义五个联结词及其各自取值情况。：用
26、符号定义五个联结词及其各自取值情况。3：写出蕴涵式的定义，分析前件与后件的关系，：写出蕴涵式的定义，分析前件与后件的关系， 列出对应的语言表达形式。列出对应的语言表达形式。4：写出遇到析取联结词二义性时的判断方式及对应：写出遇到析取联结词二义性时的判断方式及对应 符号表示。符号表示。5：列出下面公式的真值表，说明各公式的层次：列出下面公式的真值表，说明各公式的层次 (pq)(pq) (qp) (p q)(p q)6：写出命题公式的定义：写出命题公式的定义34随堂练习随堂练习7：命题符号化：命题符号化：a:只有天冷只有天冷,小王才穿羽绒服小王才穿羽绒服.b:除非天冷除非天冷,小王才穿羽绒服小王才
27、穿羽绒服.c:除非小王穿羽绒服除非小王穿羽绒服,否则天不冷否则天不冷.d:如果天不冷如果天不冷,则小王不穿羽绒服则小王不穿羽绒服.e:小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.f:只有只有4是偶数，是偶数，3才能被才能被2整除。整除。g:选小王或小李中的一人当三好学生。选小王或小李中的一人当三好学生。h:小王现在在宿舍或在图书馆里。小王现在在宿舍或在图书馆里。352.3 命题公式间的关系命题公式间的关系 学习目标：学习目标：等值式等值式基本等值式基本等值式等值演算等值演算置换规则置换规则36等值式等值式 定义定义 设设A、B为两命题，若等价式为两命题，若等价式AB是重言式，是重言式
28、，则称则称A与与B等值的等值的，记作，记作AB，并称，并称AB是是等值式等值式说明说明：定义中符号：定义中符号“”不是联结词符，它只是当不是联结词符，它只是当A与与B等值时的一种记法。注意区分等值时的一种记法。注意区分“”、“=”和和“” 可以可以用真值表验证两个公式是否等值用真值表验证两个公式是否等值 等价关系具有自反性、对称性、传递性。等价关系具有自反性、对称性、传递性。请验证：请验证：p(qr) (p q) r p(qr) (pq) r 37 用真值表法的验证方式用真值表法的验证方式n 设设A、B为两命题，由定义判断为两命题，由定义判断A与与B是否是否等值，应判断等值，应判断AB是否为重
29、言式，若是否为重言式，若AB的真值表最后一列全为的真值表最后一列全为1，则，则AB为为重言式，因而重言式，因而AB，但最后一列全为，但最后一列全为1当当且仅当在各赋值之下，且仅当在各赋值之下，A与与B的真值相同。的真值相同。因而判断因而判断A与与B是否等值等价于判断是否等值等价于判断A、B的真值表是否相同。的真值表是否相同。38基本等值式基本等值式利用真值表法可以验证很多等值式：利用真值表法可以验证很多等值式：n下面下面24个重要的等值式，是学好数理逻辑个重要的等值式，是学好数理逻辑的关键基础，应当牢记！的关键基础，应当牢记！n在下面的公式中，在下面的公式中，A、B、C代表任意的代表任意的 命
30、题公式。命题公式。39基本等值式基本等值式 双重否定律双重否定律 : 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)40基本等值式基本等值式( (续续) )德德摩根律摩根律 : 10. (A B)AB 11. (A B)AB吸收律吸收律: 12.A (A B)A, 13. A (A B)A零律零律: 14. A 11, 15.A 00 同一律同一律:
31、 16.A 0A, 17. A 1A排中律排中律: 18.AA1矛盾律矛盾律: 19.AA041基本等值式基本等值式( (续续) )蕴涵等值式蕴涵等值式: 20. ABA B等价等值式等价等值式: 21.AB(AB) (BA)假言易位假言易位: 22. ABBA等价否定等值式等价否定等值式:23.ABAB归谬论归谬论: 24.(AB) (AB) A注意注意:A,B,C代表任意的命题公式代表任意的命题公式牢记这些等值式是继续学习的基础牢记这些等值式是继续学习的基础42等值演算与置换规则等值演算与置换规则 等值演算等值演算: 由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程
32、置换定理置换定理：设：设 (A)是含命题公式是含命题公式A的命题，的命题， 若若AB, 则则 (B)(A) 等值演算的基础：等值演算的基础： (1) 等值关系的性质：自反、对称、传递等值关系的性质：自反、对称、传递 (2) 基本的等值式基本的等值式 (3) 置换规则置换规则43应用举例应用举例证明两个公式等值证明两个公式等值 例例1证明证明 p(qr) (p q)r证证 p(qr) p ( q r) （蕴涵等值式）（蕴涵等值式） ( pq) r （结合律）（结合律） (p q) r （德摩根律）（德摩根律） (p q) r （蕴涵等值式）（蕴涵等值式） 说明说明: :也可以从右边开始演算（请做
33、一遍）也可以从右边开始演算（请做一遍） 因为每一步都用置换规则，故省略不写因为每一步都用置换规则，故省略不写 熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出 44应用举例应用举例证明两个公式不等值证明两个公式不等值例例2 证明证明: p(qr) (pq) r 用等值演算不能直接证明两个公式不等值用等值演算不能直接证明两个公式不等值,证明两证明两个公式不等值的基本思想是找到一个赋值使一个成个公式不等值的基本思想是找到一个赋值使一个成真真,另一个成假另一个成假. 方法一方法一 真值表法（自己证）真值表法（自己证） 方法二方法二 观察赋值法观察赋值法. 容易看出容易看出000, 010
34、等是左边的等是左边的成真赋值，是右边的成假赋值成真赋值，是右边的成假赋值. 方法三方法三 用等值演算先化简两个公式，再观察用等值演算先化简两个公式，再观察.45应用举例应用举例判断公式类型判断公式类型 例例3 3 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1) q(pq) 解解 q(pq) q( p q) （蕴涵等值式）（蕴涵等值式） q (pq) （德摩根律）（德摩根律） p (qq) （交换律，结合律）（交换律，结合律） p 0 （矛盾律）（矛盾律） 0 （零律）（零律）由最后一步可知，该式为矛盾式由最后一步可知，该式为矛盾式. 46 例例3 (续续)(2) (pq)(
35、 qp) 解解 (pq)( qp) ( p q)(qp) （蕴涵等值式）（蕴涵等值式） ( p q)( p q) （交换律）（交换律） 1由最后一步可知，该式为重言式由最后一步可知，该式为重言式.问：最后一步为什么等值于问：最后一步为什么等值于1？ 47例例3 (续续)(3) (p q) (pq) r) 解解 (p q) (pq) r) (p (qq) r （分配律）（分配律） p 1 r（排中律）排中律）p r （同一律）（同一律）这不是矛盾式，也不是重言式，而是非重言式这不是矛盾式，也不是重言式，而是非重言式的可满足式的可满足式. .如如101是它的成真赋值是它的成真赋值, ,000是它是
36、它的成假赋值的成假赋值. 总结：总结：A为矛盾式当且仅当为矛盾式当且仅当A0 A为重言式当且仅当为重言式当且仅当A1 说明：演算步骤不惟一说明：演算步骤不惟一, ,应尽量使演算短些应尽量使演算短些48本节小结n熟悉等值、等值演算的定义熟悉等值、等值演算的定义n会用真值表法判断等值会用真值表法判断等值n记熟会用记熟会用24个重要的等值式个重要的等值式49 2.4 主范式与判定为题主范式与判定为题 学习目标：学习目标：析取范式与合取范式析取范式与合取范式 主析取范式与主合取范式主析取范式与主合取范式 50析取范式与合取范式析取范式与合取范式 简单析取式简单析取式: :仅由有限个命题变项或其否定构成
37、的仅由有限个命题变项或其否定构成的析取式称为简单析取式。析取式称为简单析取式。如如 p, q, pq, p q r, 简单合取式简单合取式: :仅由有限个命题变项或其否定构成的仅由有限个命题变项或其否定构成的合取式称为简单合取式。合取式称为简单合取式。如如 p, q, pq, p q r, 由定义可知：由定义可知：1:一个简单析取式是重言式，当且仅当它同时含一个命题变一个简单析取式是重言式，当且仅当它同时含一个命题变项及其否定。项及其否定。2:一个简单合取式是矛盾式，当且仅当它同时含一个命题变一个简单合取式是矛盾式，当且仅当它同时含一个命题变项及其否定。项及其否定。51 析取范式与合取范式析取
38、范式与合取范式( (续续) )析取范式析取范式: :仅由有限个简单合取式组成的析取式称仅由有限个简单合取式组成的析取式称为析取范式。为析取范式。 A=A1 A2Ar, 其中其中A1,A2,Ar是是简单合取式。简单合取式。A A是析取范式。是析取范式。合取范式合取范式: :仅由有限个简单析取式组成的合取式称仅由有限个简单析取式组成的合取式称为合取范式。为合取范式。 A=A1 A2Ar , 其中其中A1,A2,Ar是是简单析取式。简单析取式。A A是合取范式。是合取范式。显然：任何析取范式的对偶式为合取范式，显然：任何析取范式的对偶式为合取范式， 任何合取范式的对偶式为析取范式，任何合取范式的对偶
39、式为析取范式， 52析取范式与合取范式析取范式与合取范式( (续续) )析取范式与合取范式有下列性质：析取范式与合取范式有下列性质：n1：一个析取范式是矛盾式，当且仅当它的一个析取范式是矛盾式，当且仅当它的每个简单合取式都是矛盾式。每个简单合取式都是矛盾式。n2：一个合取范式是重言式，当且仅当它的一个合取范式是重言式，当且仅当它的每个简单析取式都是重言。每个简单析取式都是重言。53析取范式与合取范式析取范式与合取范式( (续续) )范式范式: :析取范式与合取范式的总称析取范式与合取范式的总称 公式公式A的析取范式的析取范式: 与与A等值的析取范式等值的析取范式公式公式A的合取范式的合取范式:
40、 与与A等值的合取范式等值的合取范式说明：说明： 单个命题变项及其否定既是简单析取式，又是简单单个命题变项及其否定既是简单析取式，又是简单合取式合取式形如形如 pq r, p qr 的公式既是析取范式，的公式既是析取范式，又是合取范式又是合取范式 (为什么为什么?) 54 命题公式的范式命题公式的范式 定理定理 （范式存在定理范式存在定理）任何命题公式都存在着与之等值的任何命题公式都存在着与之等值的析取范式和合取范式析取范式和合取范式. .求公求公式式A的范式的步骤：的范式的步骤： (1) 由于由于 , , 是全功能集，因而若是全功能集，因而若A中含联结词中含联结词, , , , 等，可用基本
41、的等值式及置换规则将这些联结等，可用基本的等值式及置换规则将这些联结词消去。词消去。 (2) 否定联结词否定联结词 的内移或消去的内移或消去 (3) 使用分配律使用分配律 对对 分配（求析取范式）分配（求析取范式） 对对 分配（求合取范式）分配（求合取范式）公式的范式存在，但不惟一，这是它的局限性公式的范式存在，但不惟一，这是它的局限性 55求公式的范式举例求公式的范式举例 例例 求下列公式的析取范式与合取范式求下列公式的析取范式与合取范式(1) A=(pq)r解解 (pq)r ( pq)r （消去（消去） pqr （结合律）（结合律）这既是这既是A的析取范式（由的析取范式（由3个简单合取式组
42、成的析个简单合取式组成的析取式），又是取式），又是A的合取范式（由一个简单析取式的合取范式（由一个简单析取式组成的合取式）组成的合取式）56求公式的范式举例求公式的范式举例( (续续) )(2) B=(pq)r解解 (pq)r ( pq)r （消去第一个（消去第一个） ( pq) r （消去第二个（消去第二个） (p q) r （否定号内移（否定号内移德摩根律）德摩根律）这一步已为析取范式（两个简单合取式构成）这一步已为析取范式（两个简单合取式构成）继续：继续： (p q) r (p r) (q r) （ 对对 分配律）分配律）这一步得到合取范式（由两个简单析取式构成）这一步得到合取范式（由两
43、个简单析取式构成） 57 极小项极小项定义定义 在含在含n个命题变项的简单合取式中，若每个命题变项个命题变项的简单合取式中，若每个命题变项与其否定不同时存在，而两者之一必出现且仅出现一次，与其否定不同时存在，而两者之一必出现且仅出现一次，且第且第i（1 i n）个命题变项或其否定出现在从左起的第）个命题变项或其否定出现在从左起的第i位上（若命题变项无角标，则按字典顺序排序），称这位上（若命题变项无角标，则按字典顺序排序），称这样的简单合取式为样的简单合取式为极小项极小项.说明：说明：nn个命题变项产生个命题变项产生2n个极小项。个极小项。2n个极小项均互不等值个极小项均互不等值n用用mi表示第
44、表示第i个极小项，将个极小项，将mi里的命题变项看成里的命题变项看成1，命题，命题变项的否定看成变项的否定看成0，则每个极小项对应一个二进制数，则每个极小项对应一个二进制数，也对应一个十进制数。二进制数正是该极小项的成真赋也对应一个十进制数。二进制数正是该极小项的成真赋值，十进制数值，十进制数i是该极小项成真赋值的十进制表示也是该是该极小项成真赋值的十进制表示也是该极小项抽象表示法的角码极小项抽象表示法的角码. 58公式公式 成真成真赋值赋值名称名称 p q r p q r p q r p q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0
45、11 1 01 1 1m0m1m2m3m4m5m6m7极小项极小项 由由p, q, r三个命题变项形成的极小项三个命题变项形成的极小项59知识回顾知识回顾n1:定义：排斥或定义：排斥或 与非式与非式 或非式或非式 全功能集全功能集 冗余的（独立的）联结词冗余的（独立的）联结词n2:对偶式对偶式 对偶原理对偶原理 简单合取式简单合取式 简单析取式简单析取式 析取范式与合取范式析取范式与合取范式 极小项极小项n3:求公式求公式A的范式的步骤的范式的步骤60主析取范式主析取范式n定义：定义：主析取范式主析取范式: : 设命题公式设命题公式A A中含中含n n个命题变个命题变项，如果项，如果A A的析
46、取范式中的简单合取式全是极小项，的析取范式中的简单合取式全是极小项，则称该析取范式为则称该析取范式为A A的主析取范式的主析取范式例如，例如，n=3, 命题变项为命题变项为p, q, r时，时， ( pq r) ( p q r) m1 m3 是是主析取范式主析取范式 nA的主析取范式的主析取范式: 与与A等值的主析取范式等值的主析取范式61主析取范式主析取范式( (续续) )定理定理 2.5 任何命题公式的主析取范式都是存在的任何命题公式的主析取范式都是存在的, 并且是惟一并且是惟一的的. . 用等值演算法求给定命题公式的主析取范式的步骤：用等值演算法求给定命题公式的主析取范式的步骤： (1)
47、 先求先求A的析取范式的析取范式A。 (2)若若A的某简单合取式的某简单合取式B中不含命题变项中不含命题变项pi, 也不含否定也不含否定 pi ，则将则将B展成如下形式展成如下形式B B 1 B (pi pi) ( B pi ) (B pi) (3) 将重复出现的命题变项、矛盾式及重复出现的极小项都将重复出现的命题变项、矛盾式及重复出现的极小项都“消去消去”，如，如p p用用p取代，取代， pp用用0取代，取代， mi mi用用mi 取取代。代。 (4) 将将极小项按由小到大的顺序排序极小项按由小到大的顺序排序.并用并用 表示，如表示，如m1 m2 m5用用(1,2,5)表示。表示。62主析取
48、范式用途主析取范式用途n1：判断两命题公式是否等值：判断两命题公式是否等值由于任何命题公式的主析取范式都是唯一的，因而若由于任何命题公式的主析取范式都是唯一的，因而若AB，说明说明A与与B有相同的主析取范式。有相同的主析取范式。反之，若反之，若A与与B有相同的主析取范式，必有有相同的主析取范式，必有AB。n2：判断命题公式的类型：判断命题公式的类型设设A是含是含n个命题变项的命题公式，个命题变项的命题公式，A为重言式，当且仅当为重言式，当且仅当A的主析取范式中含全部的主析取范式中含全部2n个极小项。个极小项。A为矛盾式，当且仅为矛盾式，当且仅当当A的主析取范式中不含任何极小项。若的主析取范式中
49、不含任何极小项。若A的主析取范式中的主析取范式中至少含一个极小项，则至少含一个极小项，则A是可满足式。是可满足式。n3：求命题公式的成真和成假赋值。：求命题公式的成真和成假赋值。63极大项极大项定义定义 在含有在含有n个命题变项的简单析取式中，若每个命题个命题变项的简单析取式中，若每个命题变项与其否定不同时存在，而两者之一必出现且仅出变项与其否定不同时存在，而两者之一必出现且仅出现一次，且第现一次，且第i（1 i n）个命题变项或其否定出现在）个命题变项或其否定出现在从左起的第从左起的第i位上，称这样的简单析取式为位上，称这样的简单析取式为极大项极大项.说明：说明：nn个命题变项产生个命题变项
50、产生2n个极大项。个极大项。2n个极大项均互不等值个极大项均互不等值n用用Mi表示第表示第i个极大项，将个极大项，将Mi里的命题变项看成里的命题变项看成0，命题，命题变项的否定看成变项的否定看成1，则每个极大项对应一个二进制数，则每个极大项对应一个二进制数，也对应一个十进制数。二进制数正是该极大项的成假也对应一个十进制数。二进制数正是该极大项的成假赋值，十进制数赋值，十进制数i是该极大项成真赋值的十进制表示也是该极大项成真赋值的十进制表示也是该极大项抽象表示法的角码是该极大项抽象表示法的角码. 64由由p, q, r三个命题变项形成的极大项三个命题变项形成的极大项公式公式 成假成假赋值赋值名称
