离散数学 第一章 命题逻辑 PPT

1、离散数学离散数学胡海涛 软件工程教研主楼E707 电话：61772578 第一章第一章 命题逻辑命题逻辑1.1 命题与联结词1.2 命题公式与翻译1.3 真值表与等价公式1.4 对偶原理与蕴含式1.5 联结词的扩充与功能完全组1.6 范式1.7 命题逻辑的推理理论l命题的概念、判定l命题的表示l命题的真值l五个联结词的定义及真值表l所谓命题命题，是指具有真假意义的陈述句。也就是说能够确定或能够分辨其真假的陈述句，且真或假二者必居其一，也只能居其一。l简言之，命题就是非真即假的陈述句。l判断下列语句是否为命题？（1）离散数学好学吗？（2）我真开心！（3）禁止吸烟！（4）我是学生。（5）6不是自然

2、数。（6）火星上有生物。（7）现在是八点钟。（8）2012年奥林匹克运动会将在英国举行。（9）如果天气好，那么我去散步。（10）本命题为假。l在上面的例子中，（1）、（2）、（3）不是陈述句，因而不是命题。（4）、（5）、（6）、（7）、（8）、（9）是命题。其中（4）的真假意义要根据具体的“我”而定；（7）要根据“现在”具体的时间而定；（5）是假命题；（6）在目前可能无法判定真假，但从事物的本质而言，它本身是有明确真假意义的，只不过我们现在还不知道，所以我们承认这也是一个命题；（8）是真命题；（9）由两句话组成，有明确的真假意义，因而是命题；（10）无法确定它的真假，当“本命题”假时，它便真

3、，当“本命题”真时它便假，这种断言叫悖论。l一些不能分解为更简单的陈述句的命题，称为原子命题。如上面的（4）、（5）、（6）、（7）、（8）都是原子命题。反之，称为复合命题，即由联结词，标点符号和原子命题复合而成的命题。如上面的（9）为复合命题。联结词的概念将在下一小节给出。l一个命题的真或假称为命题的真值真值，简称值，真用T T或1表示；假用F F或0表示。由于命题只有真、假二个真值，所以命题逻辑也称二值逻辑。l一个原子命题，一般用大写字母或带下标的大写字母，如P，Q，R，或Pi，Qi，Ri，等表示，把表示原子命题的符号，称为命题标识符，简称命题符。例如 P：北京是中国的首都。其中“:”是表

4、示的意思。l一个命题标识符P，如果表示一个确定的命题，则称P为原子命题常元，简称命题常元；若P只表示任意命题的位置标志，或表示不确定的命题，或以原子命题为值的变元P，就称P为原子命题变元，简称命题变元。l命题变元是以命题的真值为值的变元。显然，命题变元不是命题。将一个命题变元P用一个特定命题去代替，才能确定它的真值，这时也称为对P进行指派或对P进行解释。否定合取析取条件双条件合取非析取非条件非双条件非基本联结词扩充联结词1.1.2 联结词l(1) (1) 否定联结词否定联结词设P是一个命题，由联结词和命题P构成 P，称为命题P 的否定式复合命题。P读做“非P”。联结词 是自然语言中的“非”、“

5、不”和“没有”等的逻辑抽象。否定联结词是一个一元运算。如；P：离散数学是计算机及相关专业的基础课。P：离散数学不是计算机及相关专业的基础课。l(2) (2) 合取联结词合取联结词令P和Q是两个命题，由联结词把P，Q连接成PQ ，称为P和Q的合取式复合命题，PQ读做“P与Q”，或“P合取Q”。联结词是自然语言中的“和”，“与”，“并且”，“既又”等的逻辑抽象。合取联结词是一个二元运算。例如：P：今天下雨。Q：明天下雨。PQ：今天与明天都下雨。l(3) (3) 析取联结词析取联结词设P和Q是两个命题，由联结词把P，Q连接成PQ，称为P和Q的析取式复合命题，PQ读做“P或Q”，或“P析取Q”。析取联

6、结词是自然语言中的“或”的逻辑抽象。但它与自然语言中的“或”的意义并不完全相同，自然语言中的“或”既可以表示“排斥或”，也可以表示“可兼或”。例如：P：今天晚上我在家里看电视或去剧场看戏。Q：他可能是100米或200米赛跑的冠军。l命题P中的“或”是“排斥或”，命题Q中的“或”是“可兼或”，而析取联结词表示的是“可兼或”。关于“排斥或”，我们会在1.5节给出它的定义。析取联结词是一个二元运算。l(4) (4) 条件联结词条件联结词l设P和Q是两个命题，由联结词把P，Q连接成PQ，称PQ为P和Q的条件式复合命题，把P和Q分别称为PQ的前件和后件，或者前提和结论。PQ读做“若P，则Q”或“P条件Q

7、”。l联结词是自然语言中“如果，则”，“若，才能”等的逻辑抽象。条件联结词是一个二元运算。l在自然语言中，前件为假，不管结论真假，整个语句的意义，往往无法判断。但在命题逻辑中，当P为F F时，无论Q为T T还是为F F，都规定PQ为T T，这称为“善意推定”。例如：lP：雪是黑的。Q：太阳从西方升起。lR：336。lPQ：如果雪是黑的，那么太阳从西方升起。lPR：如果雪是黑的，那么336。lP为假命题，Q为假命题，R为真命题，而PQ和PR都是真命题。l(5) (5) 双条件联结词双条件联结词l令P和Q是两个命题，由联结词 把P，Q连接成P Q，称P Q为P和Q的双条件式复合命题，P Q读做“P

8、当且仅当Q”。l双条件联结词也可以用符号来表示。l双条件联结词 是自然语言中的“充分必要条件”、“当且仅当”等的逻辑抽象。双条件联结词是一个二元运算。例如：P：两个三角形全等。lQ：两个三角形的三组对应边相等。lP Q：两个三角形全等，当且仅当这两个三角形的三组对应边相等。l关于这五个联结词的定义，可以通过如表1-1的真值表给出，关于真值表的定义，我们将在1.3节详细说明。l表1-1 五个联结词的真值表PQPPQ PQ PQP QTTFTTTTTFFFTFFFTTFTTFFFTFFTTl需要注意：l 复合命题的真值只取决于构成它们的各原子命题的真值，而与它们的内容、含义无关，与联结词所连接的两

9、原子命题之间是否有关系也无关。l ，和具有对称性，而 ，没有。l 联结词都有从已知命题得到新的命题的作用，从这个意义上讲，它们具有操作或运算的意义。因此，可以把它们看作是一种运算或是一种函数。l 关于和 有的数学书或逻辑学的书籍中有其他的说法，如称为蕴含，称 为等价等，本书中将避免使用这种称呼，因为在后面的章节我们将另外定义“蕴含”和“等价”这两个概念。l命题公式l命题的翻译l联结词、原子命题变元、圆括号“(”、“)”，可进行有限次地连接，得到许多字符串，那些有意义的字符串，称为命题逻辑中的合式公式， 简称命题公式或公式。l定义定义1.11.1 单个的命题常元和命题变元，统称为原子命题公式，简

10、称原子公式。l下面，我们使用递归来定义命题逻辑中的合式公式（wff）。l定义定义1.2 1.2 命题逻辑中的合式公式是由下列规则形成的字符串：l 原子命题公式和真值T T、F F都是一个合式公式。l 若A是合式公式，则 (A)是合式公式。l 若A和B是合式公式，则(AB)、(AB)、(AB)和(A B)都是合式公式。l 经过有限次地使用、所得到的包含原子命题公式、联结词和圆括号的字符串都是合式公式。l例例1.1 1.1 (P)Q，(P(QR)都是合式公式，而(PQ)(Q)，(P，( PQ)(R)都不是合式公式。l为方便计，对于圆括号的使用和联结词的优先级做如下约定：l 公式最外层的圆括号可省略

11、，如把(P (QR)写成P(QR)。l 只作用于邻接后的原子命题变元，如把(P)Q写成 PQ。l 联结词的优先级从高到低依次为 ，。l定义定义1.31.3 如果A1是公式A的一部分，且A1是一个公式，称A1是A的子公式。l例例1.21.2 设公式A为(PQ)(QR)，则PQ，QR都是A的子公式。l需要注意的是，命题公式是没有真假值的，仅当在一个公式中命题变元用确定的命题代入时，才得到一个命题。这个命题的真值，依赖于代换变元的那些命题的真值。此外，并不是由命题变元，连接词和一些括号组成的字符串都能构成命题公式，如例1.1中的(PQ)(Q)和(P，( PQ) (R)就都不是命题公式。l有了合式公式

12、的概念，我们可以把自然语言中的有些语句，翻译成数理逻辑中的符号形式。把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，称为翻译，也称符号化。l例例1.3 1.3 张明正在睡觉或游泳。l解：设P：张明正在睡觉。Q：张明正在游泳。本例的“或”是“不可兼或”，而析取联结词是“可兼或”，因此不能直接对两命题析取。构造表1-2如下：l从表中可以看出原命题不能用上节的五个联结词单独写出，但是如用命题和联结词组合，可以把本命题表示为：(P Q)。P Q 原命题P Q(P Q)PQPQ (PQ)(PQ)TTFTFFFFT FTFTTFTF TTFTFTTF FFTFFFFl1.5节给

13、出其他联结词的定义后，本例也可以直接用异或联结词给出。l另外本例也可这样理解：张明正在睡觉而不在游泳或张明正在游泳而不在睡觉。因而可符号化为：(PQ) (PQ)，由表1-2可以看出，它与(P Q)的真值相同。l例例1.41.4 符号化下列命题：l 他既聪明又用功。 他虽聪明但不用功。l 除非你努力，否则你将失败。l 除非天气好，我才骑自行车上班。l 小王晚上要回家，除非下大雨。l 只有睡觉才能恢复疲劳。l 只要我还有口气，我就要战斗。l A中没有元素，A就是空集。l 张明或者李强都可以做这件事。l 张明和李强都做这件事了。l解：设P：他聪明。Q：他用功。本例可以表示为PQ。l设P：他聪明。Q：

14、他用功。本例可以表示为PQ。l设P：你努力。Q：你将失败。本例可以表示为PQ。l设P：天气好。Q：我骑自行车上班。本例可以表示为PQ或QP。l设P：小王晚上要回家。Q：下大雨。本例可以表示为QP。l解：设P：睡觉。Q：恢复疲劳。本例可以表示为QP。一般地，对于“只有P才Q”这样的语句，P是Q的必要条件，或Q是P的充分条件。l设P：我还有口气。Q：我要战斗。本例可以表示为PQ。一般地，对于“只要P就Q”这样的语句，P是Q的充分条件，或Q是P的必要条件。l设P：A中没有元素。Q：A是空集。本例可以表示为P Q。l设P：张明可以做这件事。Q：李强可以做这件事。本例可以表示为PQ。l设P：张明做了这件

15、事。Q：李强做了这件事。本例可以表示为PQ。l例例1.51.5 公式(PQ) R，其中P：李强是体育爱好者，Q：李强是文艺爱好者，R：李强是文体爱好者，试用自然语言把它叙述出来。l解：如果李强是体育爱好者而不是文艺爱好者，那么他不是文体爱好者。l符号化应该注意下列事项：l 首先确定给定句子是否为命题。l 句子中的连词是否为命题联结词。l 正确地表示原子命题和适当选择命题联结词。l为了便于正确表达命题间的相互关系，有时也采用列出“真值表”的方法，进一步分析各原子命题，以此寻找合适的逻辑联结词，使原来的命题能够正确地用形式化符号予以表达，如例1.3中。下节我们将详细讨论真值表。l真值表l公式分类l

16、等价公式l代入规则和替换规则l定义定义1.41.4 对于命题公式A中每个命题变元P，任给一个指派或解释，得到一种真值的组合，称为A的一个真值指派，或称为A的一种解释。若A的指派为T T，称该指派为A的成真指派或说A的解释为真。类似地可以定义A的成假指派（或称A的解释为假）。l定义定义1.51.5 设A为一命题公式，对其中出现的命题变元做所有可能的每一组真值指派，连同公式A的相应的真值汇列成表，称为A的真值表。l为了能更规范、更方便地构造真值表，特做如下约定：l 命题变元按字典顺序排列。l 对公式的每个解释，以二进制数从小到大或者从大到小顺序列出。l 若公式复杂，可先列出各子公式的真值(若有括号

17、，则应从里层向外层展开)，最后列出所给公式的真值。l例例1.61.6 求(PQ) ( PQ)的真值表。l解： l 表1-3PQPQPPQ(PQ) (PQ)111011100001011111001111l例例1.71.7 求(PQ)R的真值表l解：l 表1-4PQRPQR(PQ)R111100110111101000100010011100010111001100000111l在真值表中，命题公式真值的取值数目，决定于分量的个数。例如，例1.6中由2个命题变元组成的命题公式共有4种可能的真值，例1.7中由3个命题变元组成的命题公式共有8种可能的真值。不难证明，n个命题变元组成的命题公式共有2n

18、种真值情况。l定义定义1.61.6 设A为一个命题公式，对A做所有可能的解释，若这些解释使得A皆为真，则称A为永真式；若这些解释使得A皆为假，则称A为永假式；若至少存在一种解释使得A为真，则称A为可满足式。l永真式也称重言式，常用T T表示；永假式也称矛盾式，常用F F表示。l由定义可知，重言式必是可满足式，反之未必成立。l判定给定公式是否为永真式，永假式或可满足式的问题，称为给定公式的判定问题。l在命题逻辑中，由于任何一个命题公式的解释数目总是有限的，所以命题逻辑的判定问题是可解的。其判定方法有真值表法和公式推演法。用真值表法求解如例1.6就是一个永真式，例1.7是一个可满足式。下面再给出一

19、个利用真值表法判定公式类型的例子。l例例1.81.8 用真值表判定公式 (PQ)P是永真式、永假式还是可满足式。l解：l 表1-5l由真值表可以看出，公式 (PQ)P是永假式。PQPPQ (PQ)(PQ)P110100100100011100001010l由真值表可以看出，有些命题公式在分量的不同指派下，其对应的真值与另一个命题公式完全相同，如例1.6中的(PQ)和 ( PQ)。像这样的两个公式，我们称它们是等价的。l定义定义1.71.7 设A和B是两个命题公式，如果A、B在其任意解释下，其真值都是相同的，则称A和B是等价的，或逻辑相等，记作AB，读作A等价B，称AB为等价式。l显然，若公式A

20、和B的真值表是相同的，则A和B等价。因此，验证两公式是否等价，只需做出它们的真值表即可。l例例1.91.9 P Q (PQ)(QP)l解：l 表1-6l由表1-6可以看出，P Q与(PQ)(QP) 的真值表是相同的，因此这两个公式是等价的。PQP QPQ QP (PQ)(QP)111111100010010100001111l请读者自己验证下列等价式：lP P， PPP， (PP)QQ， PPQQ。l由此可见，两公式等价，不一定是含相同的命题变元。l在这里，请读者注意和的区别与联系。l区别： 是逻辑联结词，属于目标语言中的符号，它出现在命题公式中，不是逻辑联结词，属于元语言中的符号，表示两个命

21、题公式之间的一种充分必要(记为iff)关系，它不属于这两个公式的任何一个公式中的符号。l定理定理1.1 1.1 AB当且仅当A B是永真式。l证明：若AB，则A、B有相同的真值，即A B永为T T。反之，若A B为永真式，即A B永为T T，故A、B的真值相同，则AB。l等价式有下列性质：l 自反性，即对任意公式A，有AA。l 对称性，即对任意公式A和B，若AB，则BA。l 传递性，即对任意公式A、B和C，若AB、BC，则AC。l在判定公式是否等价时，有一些简单而又常用的等价式，称为基本等价式或称命题定律。l(1) 对合律：AA。l(2) 交换律：ABBA，ABBA，A B B A。l(3)

22、结合律：(AB)CA(BC)，(AB)CA(BC)，l(AB)CA(BC)。l(4) 分配律：A(BC)(AB)(AC)，lA(BC)(AB) (AC)。l(5) 德摩根律：(AB) AB，(AB) AB。l(6) 等幂律：AAA，AAA。l(7) 同一律：AT TA，AF FA。l(8) 零 律：AF FF F，AT TT T。l(9) 吸收律：A(AB) A，A(AB)A。l(10) 互补律：AAF F，(矛盾律)lAAT T。(排中律)l(11) 条件式转化律：AB AB，AB B A。l(12) 双条件式转化律：A B (AB)(BA)(AB)(AB)，lAB (AB)。l(13) 输

23、出律：(AB)CA(BC)。l(14) 归谬律：(AB)(A B) A。l由已知的等价式可以推演出更多的等价式，称这一过程为等价演算，等价演算是逻辑代数或布尔代数的重要组成部分。关于布尔代数我们将在第三篇代数结构中详细讨论。l在定义复合公式时，通过使用逻辑联结词可以从已知公式形成新的公式，从这个意义上可把逻辑联结词看成运算。除逻辑联结词外，还有两个规则：代入规则和替换规则。它们也有从已知公式得到新的公式的作用。下面分别介绍。l(1) 代入规则l定理定理1.21.2 在一个永真式A中，任何一个原子命题变元R出现的每一处， 用另一个公式代入，所得公式B仍是永真式。本定理称为代入规则。l证明：因为永

24、真式对任意指派，其值都为真，与所给的某个命题变元指派的真值是真还是假无关，因此，用一个命题公式代入到原子命题变元R出现的每一处后，所得命题公式的真值仍为真，证毕。l例例1.10 1.10 求证：(PQ)(PQ)为永真式。l证明：由命题定律可知，RRT T，即RR为永真式。用公式(PQ)代入公式RR中的命题变元R，则得(PQ)(PQ)。根据代入规则可知，给定公式是永真式。l注意，若仅仅将(PQ)代入到一个析取项R，得到(PQ)R，显然它不是永真式，因为这不符合代入规则所要求的处处代入。l(2) 替换规则l定理定理1.31.3 设A1是合式公式A的子公式，若A1B1，将A中的A1用B1 替换，得到

25、公式B，则AB。本定理称为替换规则。l证明：因为A1B1，即对于它们的命题变元做任何真值的指派，A1与B1的真值相同，故以B1替换A1后，公式B与A在对其命题变元做相应的任何真值指派时，它们的真值亦相同，因此，AB成立。l例例1.111.11 求证 Q(P(PQ) QP。l证明：因为QP QP，又由吸收律知，P(PQ) P，根据替换规则可得，Q(P(PQ) QP。l满足定理1.3条件的替换，称为等价替换。l利用命题定律和定理1.3，可以推演出一些更为复杂的等价式。l例例1.12 1.12 证明 P(QR)Q(PR) R(Q P)。l证明：P(QR) P(QR)两次替换 Q(PR)结合、交换、结

26、合Q(PR)两次替换l类似可证明P(QR) R(Q P)。l从定理及上述例题可看到，代入和替换有两点区别： 代入是对原子命题变元而言的，而替换通常是可对命题公式实行。l 代入必须是处处代入，替换则可部分替换，亦可全部替换。l对偶原理l蕴含式l从上节可以看到很多命题定律都是成对出现的，其不同的只是和互换。我们把这样的公式称为具有对偶规律。下面先给出对偶式的定义。l定义定义1.81.8 在给定的命题公式A中，若把和互换，F F和T T互换而得到另一个命题公式A*，则称A*为A的对偶式。l显然，A也是A*的对偶式。可见，A与A*互为对偶式。l例例1.13 1.13 写出下列表达式的对偶式l（1）(P

27、Q)Rl（2）(PQ)T Tl（3）(PQ) (P(QS)l解：这些表达式的对偶式分别是：l（1）(PQ)Rl（2）(PQ) F Fl（3）(PQ)(P(QS)l定理定理1.4(1.4(对偶定理对偶定理) ) 设A和A*互为对偶式，P1，P2，Pn是出现A和A* 中的原子命题变元，则l A(P1，P2，Pn)A*(P1，P2，Pn)l A(P1，P2，Pn) A*(P1，P2，Pn)l证明：由德摩根律lPQ(PQ)，PQ(PQ)l故 A(P1，P2，Pn)A*(P1，P2，Pn)l同理lA(P1，P2，Pn) A*(P1，P2，Pn)l表明，公式A的否定等价于其命题变元否定的对偶式；表明，命题

28、变元否定的公式等价于对偶式之否定。l例例1.141.14 设A(P，Q，R)= P(QR)，试证明：A*(P，Q，R)P(QR)。l证明：A*(P，Q，R) A(P，Q，R) (P(QR) P(QR)。l定理定理1.51.5 设A和B为两个命题公式，若AB则A*B*。l证明：令P1，P2，Pn是A和B中所有的命题变元。因为A(P1，P2，Pn)B(P1，P2，Pn)，所以A(P1，P2，Pn) B(P1，P2，Pn)，根据定理1.4可知A(P1，P2，Pn)A*(P1，P2，Pn)，B(P1，P2，Pn)B*(P1，P2，Pn)。于是A*(P1，P2，Pn)B*(P1，P2，Pn)，利用代入规

29、则，得A*(P1，P2，Pn) B*(P1，P2，Pn)，证毕。l例例1.151.15 试证明l (PQ)(PQ)PQl (PQ)(PQ)PQl证明：因为 (PQ)(PQ) (PQ)(PQ)(PPQ)(QPQ) T T(PQ)PQl故得证。l在证明中，可知(PQ)(PQ)是(PQ)(PQ)的对偶式，PQ是PQ的对偶式，根据定理1.5得证。l有了等价式、代入规则、替换规则和对偶定理，便可能得到更多的永真式，证明更多的等价式，使化简命题公式更为方便。l定义定义1.91.9 设A和B是两个命题公式，若AB是永真式，则称A蕴含B，记作AB，称AB为蕴含式或永真条件式。l因为AB不是对称的，即AB与BA

30、不等价，对AB来说，BA称作它的逆换式；AB称作它的反换式；BA称作它的逆反式，它们之间的关系如表1-7所示。l从表1-7可以看出：l(AB)( BA)，(BA)( AB)。l这两个式子在推理中会经常用到。l符号和的区别与联系类似于和的关系。区别：是逻辑联结词，属于对象语言中的符号，是公式中的符号；而不是联结词，属于元语言中的符号，表示两个公式之间的关系，不是公式中符号。联系：AB成立，其充要条件AB是永真式。l蕴含式有下列性质：l 自反性，即对任意公式A，有AA。l 传递性，即对任意公式A、B和C，若AB，BC，则AC。l 对任意公式A、B和C，若AB，AC，则A(BC)。l 对任意公式A、

31、B和C，若AC，BC，则ABC。l这些性质的正确性，请读者自己验证。l 表1-7ABABBA BAAB111111100011011100001111l定理定理1.61.6 设A和B是两命题公式，AB的充要条件是AB且BA。l证明：若AB，则A B为永真式，因为A B (AB)(BA)，故AB为T T且BA为T T，即AB，BA成立。反之，若AB且BA，则AB为T T且BA为T T，因此A B为T T，A B是永真式，即AB。l这个定理也可以作为两个公式等价的定义。l蕴含式证明方法，除真值表外，还有两种方法：l前件真推导后件真方法l设公式的前件为真，若能推导出后件也为真，则条件式是永真式，故蕴

32、含式成立。l欲证AB，即证AB是永真式。对于AB，除在A取真和B取假时，AB为假外，余下AB皆为真。所以，若AB的前件A为真，可推出B亦为真，则AB是永真式，即AB。l后件假推导前件假方法l设条件式后件为假，若能推导出前件也为假，则条件式是永真式，即蕴含式成立。l因为若由AB的后件B取假，可推出A取假，即推证了：B A。又因ABB A，故AB成立。l例例1.161.16 求证 Q(PQ) P。l证明：前件真推导后件真方法：设Q(PQ)为T T，则Q，(PQ)皆为T T，于是Q为F F，PQ为T T，则必须P为F F，故P为T T。l后件假推导前件假方法：假定P为F F，若Q为F F，则PQ为F

33、 F，Q(PQ)为F F；若Q为T T，则Q为F F，Q(PQ)为F F，故Q(PQ) P。l下面给出常用的蕴含式，称为基本蕴含式，它们的正确性可用真值表法或上述的前件真推导后件真和后件假推导前件假方法来证明。l(1) ABA化简式l(2) ABB化简式l(3)AAB附加式l(4)AAB附加式变形l(5)BAB附加式变形l(6)(AB)A化简式变形l(7)(AB) B化简式变形l(8)A(AB)B假言推论l(9)B(AB) A拒取式l(10)A(AB)B析取三段论l(11)(AB)(BC)AC 条件三段论l(12)(AB)(B C)AC 双条件三段论l(13)(AB)(CD)(AC) BD合取

34、构造二难l(14)(AB)(CD)(AC) BD析取构造二难l特别当B = D时，有l(AB)(CB)(AC) B 二难推论l(AB)(CB)(AC) B 二难推论l(15)AB (AC)(BC) 前后件附加lAB (AC)(BC)l(16)A，BAB 合取引入l此外，由定理1.6可知，每个命题定律均可看成基本蕴含式，并且一个命题定律对应两个基本蕴含式。l其他联结词l联结词的功能完全组l定义定义1.101.10 设P和Q是任意两个原子命题，l 由合取非联结词 把P和Q连接成PQ，称它为P和Q的合取非式复合命题，读作“P合取非Q”。PQ的真值由命题P和Q的真值确定：当且仅当P和 Q均为T T时，

35、PQ为F F，否则PQ为T T。“合取非”又常称为“与非”。l 由析取非联结词 把P和Q连接成PQ，称它为P和Q的析取非式复合命题，读作“P析取非Q”。PQ的真值由命题P和Q的真值确定：当且仅当P和Q均为F F时，PQ为T T，否则PQ为F F。“析取非”又常称为“或非”。l 由条件非联结词 把P和Q连接成PQ，称它为P和Q的条件非式复合命题，读作“P条件非Q”。PQ的真值由P和Q的真值确定：当且仅当P为T T而Q为F F时，PQ为T T；否则PQ为F F。有时也把条件非联结词记为“ ”。l 由双条件非联结词 把P和Q连接成P Q，称它为P和Q的双条件非式复合命题，读作“P双条件非Q”。PQ的

36、真值由P和 Q的真值确定：当且仅当P和Q的真值不同时， PQ为T T，否则PQ为F F。“双条件非”又常称为“异或”，也常用符号“”或“ ”表示。cl上面4个联结词构成的复合命题，其真值表如下：l 表1-8l由表可知， PQ (PQ)l PQ (PQ) P Q (PQ)l PQ (P Q)l这4个联结词的取名也正缘于此。P QPQ PQ P Q P Q1 11 00 10 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0l令P、Q和R是原子命题变元，关于与非、或非和异或有如下性质：l 与非的性质l(a) PQQPl(b) PP Pl(c) (PQ)(PQ)PQl(d) (PP

37、)(QQ)PQl 或非的性质l(a) PQQPl(b) PP Pl(c) (PQ)(PQ)PQl(d) (PP)(QQ)PQl从上述的性质可知，联结词 、和可分别用联结词 或者 取代。读者可以自行验证， 和 都不满足结合律。l 异或的性质l(a) PQ QPl(b) P (QR)(PQ)Rl(c) P(QR)(PQ)(PR)l(d) PPF F，F FPP，T T P Pl(e) 若PQR，则QRP，PPQ，且PQRF F。l以上所有性质，用真值表或命题定律都是不难证明的，请读者自己完成。l至此，已有了九个联结词，是否还需要定义其他联结词呢？事实上，两个命题变元P和Q，恰可构成 个不等价的命题

38、公式，如下表所示：l表1-9P QFTPQPQPQPQ1 11 00 10 000001111110010100011010110000111所用的联结词序号12345678l从列表可知：l第1、2列分别表示永真T T和永假F F；l第3、4列分别表示命题变元P和Q；l第5、6列分别表示命题变元的否定：P和Q；P QPQPQPQP QP QP QQPQ P1 11 00 10 011100001101101001001011011010010所用的联结词 序号910111213141516l第7列表示“合取”命题：PQ；l第8列表示“合取非”命题：PQ；l第9列表示“析取”命题：PQ；l第10

39、列表示“析取非”命题：PQ；l第11、15列分别表示条件命题：PQ和QP；l第12、16列分别表示条件非命题：PQ和QP；l第13列表示双条件命题：P Q；l第14列表示双条件非命题：P Q；l由上述分析，除常量T T和F F及命题变元本身外，命题联结词一共九个就足够了。l虽然我们定义了九个联结词，但这些联结词并非都是必要的，因为包含某些联结词的公式可以用另外一些联结词的公式等价代换。现在考虑联结词的功能完全组，对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换。这是因为：P Q (PQ)，P Q (PQ)lPQ (PQ)，PQ (P Q)l可见，扩充的4个联结词 ， 和 能由原有5

40、个联结词分别替代。l又由命题定律：lP Q(PQ)(QP)lPQ PQlPQ (PQ)lPQ (PQ)l可知，原有5个联结词 ，和 又能由联结词组，或，取代。那么，究竟最少用几个联结词？也就是说，用最少的几个联结词就能等价表示所有的命题公式。这便是所要定义的联结词功能完全组。l定义定义1.111.11 称G为联结词功能完全组，如果G满足下列两条件：由G中联结词构成的公式能等价表示任意命题公式；G 中的任一联结词不能用其余的联结词等价表示。l可以证明任意的命题公式都可由仅包含，或，的命题公式等价代换。所需注意的是上述联结词组，和，不能再归为，或，。l因为从合式公式定义可以看出包含二元联结词的命题

41、公式不能用仅包含一元联结词的命题公式等价代换，同时如有lP(PQ) )l的形式，则对该等价式右边所出现的变元，都指派其真值为T T，由于和的各次复合结果，其真值必为T T，而该式的左边的真值为F F，产生矛盾，说明“”是不能由“”或“”的复合所替代，故联结词功能完全组应为，或，但为了表示方便，仍经常使用联结词组，。l当然，也都是联结词功能完全组；而， 不是联结词功能完全组。l例例1.171.17 试将公式(P(QR)(PQ)用仅含联结词 和的公式等价表示。l解： (P(QR)(PQ) (P(QR)(PQ)(P(PQ)(Q(PQ)(R(PQ)(PQ)(PQ)(RPQ)(PQ)(PQ)l析取范式与

42、合取范式l主析取范式与主合取范式l定义定义1.12 1.12 命题变元和命题变元的否定，称为文字。如果一个文字恰为另一个文字的否定，则称它们为一对相反文字。l例如，P和 P都是文字，并且是一对相反文字， P不是文字。P和 Q都是文字，但不是一对相反文字。l定义定义1.131.13 设L1，L2，Lk都是文字，称L1L2Lk为简单析取式，并称Li为析取项；称L1L2Lk为简单合取式，称Li为合取项，其中1ik。l例如，公式P，Q，PQ和PQP等都是简单合取式，而P，Q和P为相应的简单合取式的合取项；公式P，Q，PQ，PQP等都是简单析取式，而P，Q和 P为相应简单析取式的析取项。l注意，一个命题

43、变元或其否定既可以是简单合取式，也可是简单析取式，如例中P，Q等。l定理定理1.71.7 简单合取式为永假式的充要条件是：它至少含有相反文字出现。l证明：充分性：因为对于任何命题变元P，P和 P这对相反文字的合取，即PP为F F，所以，若PP在简单合取式中出现，根据定义1.13，它必是永假式F F。l必要性：假设某个简单合取式为永假式F F，但该简单合取式中不同时包含任何相反的文字。对这简单合取式中的各命题变元指派真值为T T，而各带否定的命题变元指派真值为F F，则使简单合取式取真值T T，这与原假设矛盾，定理得证。l定理定理1.81.8 简单析取式为永真式的充要条件是：它至少含有相反文字出

44、现。l定理1.8的证明与定理1.7类似，请读者自己完成。l定义定义1.141.14 设A1，A2，Am为简单合取式，称A1A2Am为析取范式，其中1m。l定义定义1.151.15 设B1，B2，Bn为简单析取式，称B1B2Bn为合取范式，其中1n。l例如，公式(PQ)(PQ)(PQQ)是析取范式；公式P(PQ)为合取范式，而PQ既是析取范式又是合取范式。l定理定理1.91.9 对于任何一命题公式，都存在与其等价的析取范式和合取范式。l求范式算法：l 使用命题定律，消去公式中除 、 和 以外公式中出现的所有联结词；l 使用(P)P和德摩根律，将公式中出现的联结词 都移到命题变元之前；l 利用结合

45、律、分配律等将公式化成析取范式或合取范式。l例例1.181.18 求(P(QR)S的析取范式和合取范式。l解：l(P(QR)Sl(P(QR)SlP(QR)SlP(QR)S（析取范式）l(PQS)(PRS) （合取范式）l利用析取范式和合取范式可对公式进行判定。l定理定理1.101.10 公式A为永假式的充要条件是A 的析取范式中每个简单合取式至少包含一对相反文字。l证明：充分性：因为任何命题变元P，PP为F F，并且对任何命题变元Q，（PP）QF F。所以，在每个简单合取式中，由于至少包含一对相反文字，故A的析取范式中的每个简单合取式均为F F，所以A为永假式。l必要性：（反证法）假设公式A的

46、析取范式为永假式，但存在某个简单合取式不同时包含一对相反文字，则该简单合取式不能为永假式，从而导致A的析取范式不是永假式。这与假设矛盾，证毕。l定理定理1.111.11 公式A为永真式的充要条件是A 的合取范式中每个简单析取式至少包含一对相反文字。l定理1.11的证明与定理1.10类似，请读者自己完成。l例例1.191.19 判定下面公式为何种公式：l P(QR)(PR)l (PQ)Pl解： P(Q R)(PR) l P(QR)(PR)l (PQRP)(PQRR)l由于第一个简单析取式中包含P和P，第二个简单析取式中包含R和R，由定理1.11可知，为永真式。l(PQ)P l(PQ)Pl(PQ)

47、P析取范式l(PP)(Q)P)合取范式l中的两个范式，均不满足定理1.10和定理1.11，故既不是永假式，也不是永真式，它是可满足式。l由例1.19可知，利用范式判定公式，必要时需给出公式的两种范式方能做出正确结论，这显然很麻烦，有其他的方法加以改进，见下节“公式的主范式”。l范式不惟一，这只需要给出一个例子便能说明之。l例例1.201.20 求(PQ)P的析取范式和合取范式。l解l(PQ)Pl (PQ)Pl(PQ)P 析取范式l P 析取范式l(PQ)Pl(PQ)Pl(PP)(QP) 合取范式l P(QP) 合取范式l P 合取范式l由于范式的不惟一性，对用范式判定公式间的等价关系带来不便，

48、这也要求范式有待进一步改进。为此我们给出主范式的概念。l范式基本解决了公式的判定问题。但由于范式的不惟一性，对识别公式间是否等价带来不便和困难，而公式的主范式解决了这个问题。下面分别讨论公式的主析取范式和主合取范式。l定义定义1.161.16 在含有n个命题变元的简单合取式中， 若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现一次，则称该简单合取式为小项，或布尔积。l例如，两个命题变元P和Q，其构成的小项有PQ，PQ，PQ和PQ；而三个命题变元P、Q和R，其构成的小项有PQR，PQR，PQR，PQR，PQR ，PQR，PQR，PQR。l可以证明，n个命题变元共形成2n个小项。l为简

49、化小项的书写和表示，特编码如下：l如果将命题变元按字典序排列，并且把命题变元与1对应，命题变元的否定与0对应，则可对2n个小项依二进制数编码，记为mi，其下标i是由二进制数转化的十进制数。用这种编码所求得2n个小项的真值表，可明显地反映出小项的性质。l表1-10和表1-11分别给出了2个命题变元P和Q，3个命题变元P、Q和R的小项真值表。l表1-10 两个命题变元P和Q的小项真值表m(二) m00 m01 m10 m 11P QPQ PQ PQ PQ0 0 1 0 0 00 1 0 1 0 01 0 0 0 1 01 1 0 0 0 1m(+) m0 m1 m2 m3l(PQ)Pl(PQ)Pl

50、(PP)(QP) 合取范式l P(QP) 合取范式l P 合取范式l由于范式的不惟一性，对用范式判定公式间的等价关系带来不便，这也要求范式有待进一步改进。为此我们给出主范式的概念。l表1-11 三个命题变元P、Q和R的小项真值表m(二)m000m001m010m011m100m101m110m111P Q RPQRPQRPQRPQRPQRPQRPQRPQR0 0 0100000000 0 1010000000 1 0001000000 1 1000100001 0 0000010001 0 1000001001 1 0000000101 1 100000001m(+)m0m1m2m3m4m5m

51、6m7l从表1-10，表1-11可看出，小项有如下性质：l(a) 没有两个小项是等价的，即是说各小项的真值表都是不同的；l(b) 任意两个不同的小项的合取式是永假的：mimjF F，ij。l(c) 所有小项之析取为永真： miT T。l(d) 每个小项只有一个成真指派，且其真值1位于主对角线上。这表明每个小项与其成真指派之间建立了一一对应关系。l定义定义1.171.17 在给定公式的析取范式中，若其简单合取式都是小项， 则称该范式为主析取范式。l定理定理1.121.12 任意含n个命题变元的非永假命题公式A 都存在与其等价的主析取范式。l证明：首先求出A的所有小项，再列出各小项和A的真值表，对

52、A的每个解释为真且取真值为1的小项，这些小项的析取范式，即A的主析取范式，显然与A等价。l主析取范式求法有两种：真值表法和公式化归法。定理1.12的证明已给出了用真值表求主析取范式的方法，而公式化归法给出如下：l(a) 把给定公式化成析取范式；l(b) 删除析取范式中所有为永假的简单合取式；l(c) 用等幂律把简单合取式中重复出现的同一命题变元化简为一次出现，如PPP。l(d) 用同一律补进简单合取式中未出现的所有命题变元，如Q未出现，则PP(QQ)，并用分配律展开，将相同的简单合取式的多次出现化为一次出现， 这样即可得到给定公式的主析取范式。l例例1.211.21 求(PQ)Q的主析取范式。

53、l解：用公式化归法求解：l(PQ)Q(PQ)Ql (PQ)(QQ)l (PQ)(Q(PP)l (PQ)(PQ)(PQ)l (PQ)(PQ) m3m1l 用真值表法求解：l由真值表可求出l(PQ)Q( PQ)(PQ) m11m01 m3m1 P QPQ PQ PQ PQ (PQ)Q1 11 00 10 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0l由真值表可求出(PQ)Q( PQ)(PQ) m11m01 m3m1l定理定理1.131.13 任意含n个命题变元的非永假命题公式，其主析取范式是惟一的。l证明：（反证法）假设一含n个命题变元的非永假命题公式A有两个

54、不同的主析取范式A1和A2。显然A1 A2。由于A1和A2是不同的主析取范式，故至少存在一个小项，如mi，只出现在A1和A2之一中，不妨令mi在A1中而不在A2中。取mi的成真指派S，于是在S下A1为真，而在S下A2为假，这与已知A1 A2矛盾，证毕。l定义定义1.181.18 在n个命题变元的简单析取式中，若每个命题变元与其否定不同时存在，而二者之一必出现一次且仅出现一次，则称该简单析取式为大项，或布尔和。l例如，由两个命题变元P和Q，构成大项有PQ，PQ，PQ，PQ；三个命题变元P，Q和R，构成PQR，PQR，PQR，PQR，PQR，PQR，PQR，PQR。l能够证明，n个命题变元共有2n

55、个大项。l大项编码如下：l如果将n个命题变元排序，并且把命题变元与对应，命题变元的否定与对应，则可对2n个大项按二进制数编码，记为Mi，其下标i是由二进制数化成的十进制数。用这种编码所求的2n个大项的真值表，能直接反映出大项的性质。l表1-12给出了2个命题变元P和构成所有大项的真值表。l表1-12M(二)M00M01M10M11P QPQPQPQPQ0 00 11 01 10111101111011110M(+)M0M1M2M3l类似可给出个命题变元P、Q和R的所有大项的真值表，留给读者完成。l从表1-11可看出大项的性质：l(a)没有两个大项是等价的。l(b)任何两个不同大项之析取是永真的

56、，即MiMjT T，ij。l(c) 所有大项之合取为永假，即 MiF F。l(d) 每个大项只有一个解释为假，且其真值0位于主对角线上。这表明每个大项与其成假指派建立了一一对应关系。l定义定义1.191.19 在给定公式的合取范式中，若其所有简单析取式都是大项， 称该范式为主合取范式。l定理定理1.141.14 任意含有n个命题变元的非永真命题公式A，都存在与其等价的主合取范式。l定理定理1.151.15 任意含n个命题变元的非永真命题公式A，其主合取范式是惟一的。l上述两个定理的证明，类似于定理1.12和定理1.13，请读者自己完成。l主合取范式的求法也有两种，类似于主析取范式的求法。l由于

57、主范式是由小项或大项构成，从小项和大项的定义，可知两者有下列关系：lmiMi Mimil因此，主析取范式和主合取范式有着“互补”关系，即由给定公式的主析取范式可以求出其主合取范式。l设命题公式A中含有n个命题变元，且A的主析取范式中含有k个小项 ， ， 。则 A的主析取范式中必含有2n-k个小项，不妨含为 ， ， ，即 A 。于是1im2imkim1jm2jmknjm-21jm2jmknjm-2lA A ( )l l l由此可知，从A的主析取范式求其主合取范式的步骤为：l(a)求出A的主析取范式中没有包含的小项。l(b) 求出与(a)中小项的下标相同的大项。l(c) 做(b)中大项之合取，即为

58、A的主合取范式。l例如，(PQ)Qm1m3，则(PQ)QM0M2。l利用主范式可以求解判定问题或者证明等价式成立。1jm2jmknjm-21jm2jmknjm-21jM2jMknjM-2l1.1.判定问题判定问题l根据主范式的定义和定理，也可以判定含n个命题变元的公式，其关键是先求出给定公式的主范式，其次按下列条件判定之：l(a) 若A，或A可化为与其等价的、含2n个小项的主析取范式，则A为永真式。l(b) 若A，或A可化为与其等价的、含2n个大项的主合取范式，则A为永假式。l(c) 若A不与或者等价，且又不含2n个小项或者大项，则A为可满足的。l例例1.221.22 判定下列公式为何类公式：

59、l(1) (PQ)Ql(2) (PQ)(PQ)l解：用公式化归法，可得l(1) (PQ)Q M0M2 m1m3l可见，其主范式中，大、小项数目均不到4，故(PQ)Q为可满足式。l(2) (PQ)(PQ) (PQ)(PQ)T T，故(PQ)(PQ)为永真式。l2.2.证明等价式成立证明等价式成立l由于任一公式的主范式是惟一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的。l例例1.23 1.23 求证(PQ)(PR)P(QR)l证明：利用求主合取范式来证明等价性。l(PQ)(PR)l (PQ)(PR)l (PQ)(PR)l ( (PQ)(RR) )(P(QQ)R)l(PQR)

60、(PQR)(PQR)(PQR)lM4M5M4M6 M4M5M6lP(QR) P(QR) (PQ)(PR)l M4M5M6l由于两公式具有相同的主合取范式，故两公式等价。l推理的基本概念l推理常用方法l推理也称论证，它是指由已知命题得到新的命题的思维过程，其中已知命题称为推理的前提或假设，推得的新命题称为推理的结论或逻辑推论。l定义定义1.201.20 设A和C是两个命题公式，当且仅当AC为T T时，即AC，称C是A的有效结论，或C可由A逻辑地推出。l这个定义可以推广到有n个前提的情况。l如果H1，H2，Hn，C是命题公式，当且仅当lH1 H2 Hn C（1.1）l此时称C是一组前提H1，H2，