离散数学第一章PPT课件

1、1.1 命题与联结词命题与联结词 1.2 命题公式、翻译、真值表命题公式、翻译、真值表1.4 对偶式与蕴涵式对偶式与蕴涵式1.3 公式分类与等价式公式分类与等价式1.5 联结词的扩充与全功能联结词组联结词的扩充与全功能联结词组1.6 公式标准型公式标准型范式范式1.8 命题逻辑的推理规则命题逻辑的推理规则1.7 公式主范式公式主范式1.1 命题与联结词命题与联结词 1.1.1 命题的基本概念命题的基本概念1.1.2 命题分类与命题标识符命题分类与命题标识符1.1.3 命题联结词命题联结词1.1.1 命题的基本概念命题的基本概念 注意：判断一个句子是否为命题应分为两步：首注意：判断一个句子是否为

2、命题应分为两步：首先判断它是否为陈述句，其次判断它能否确定真假。先判断它是否为陈述句，其次判断它能否确定真假。注意，一个陈述句能否判断真假，和我们是否知道注意，一个陈述句能否判断真假，和我们是否知道它的真假是两回事。它的真假是两回事。 定义定义1.1 能判断真假的陈述句称为命题。一能判断真假的陈述句称为命题。一个命题的真或假称为命题的真值，分别用个命题的真或假称为命题的真值，分别用T(或或1)与与F(或或0)表示。真值为真的命题称为真表示。真值为真的命题称为真命题，真值为假的命题称为假命题。命题，真值为假的命题称为假命题。 例 1 判断下列句子哪些是命题？ (1)雪是黑的。 (2)天气多好呀！

3、 (3)别的星球上有生物。 (4)1101110。 (5)你上网了吗？ (6)全体立正！ (7)xy5。 (8)人有五指。 (9)现在是6点钟。 (10)我正在说谎。命题命题感叹句，不是命题感叹句，不是命题命题（目前无法判断）命题（目前无法判断）命题（由上下文而定）命题（由上下文而定）疑问句，不是命题疑问句，不是命题祈使句，不是命题祈使句，不是命题陈述句，但没有确定的真值，不是命题陈述句，但没有确定的真值，不是命题命题（因人而异）命题（因人而异）命题（因地而异）命题（因地而异）悖论，不是命题悖论，不是命题 定义定义1.2 不能再分解为其他命题的命题称为原子不能再分解为其他命题的命题称为原子命题

4、。由原子命题和命题联结词构成的命题称为复合命题。由原子命题和命题联结词构成的命题称为复合命题。命题。 1.1.2 命题分类与命题标识符 定义定义1.3 一个命题标识符如表示真值确定的命题，一个命题标识符如表示真值确定的命题，则称其为命题常元，如果命题标识符表示真值不确定则称其为命题常元，如果命题标识符表示真值不确定的陈述句，则称其为命题变元。的陈述句，则称其为命题变元。 表示原子命题的符号称为命题标识符。例2 P：雪是黑的。 例如，例1中的命题都是原子命题，而命题“张三和李四都是大学生”是复合命题，因为它由“张三是大学生”和“李四是大学生”两个原子命题组成。1.1.3 命题联结词 通过命题联结

5、词可以把原子命题复合成一个复合命题，命题逻辑中常用的联结词有以下五种：“非”、“且”、“或”、“如果，则”、“当且仅当”，下面给出它们的确切含义和符号表示。1.否定词(negation connective ) 定义定义1.4 复合命题复合命题“非非P”称为命题称为命题P的否定，记作的否定，记作 P，读作非，读作非P。 P为真当且仅当为真当且仅当P为假。为假。 例3 设 P：离散数学是计算机专业的核心课程， 则 P:离散数学不是计算机专业的核心课程。2.合取词(conjunction connective ) 定义定义1.5 复合命题复合命题“P且且Q”称为称为P与与Q的合取式，记作的合取式，

6、记作PQ，读作，读作P且且Q。PQ为真当且仅当为真当且仅当P与与Q都为真。都为真。 例4 设P：今天上机，Q：今天下雨，则PQ表示今天上机且今天下雨。3.3.析取词析取词( (disjunction connective ) 定义定义1.6 复合命题复合命题“P或或Q”称为称为P与与Q的析取式，的析取式，记作记作PQ，读作，读作P或或Q。PQ为假当且仅当为假当且仅当P和和Q都为都为假。假。 由于自然语言中的“或”具有多义性，包括“可兼或”、“排斥或”和“表示近似的或”，因此需要指出命题逻辑中的“或”是指哪一种。先看下表给出的例子。 或的含义例子说明联结词可兼或ab0即a0或b0或ab0两者至少

7、有一个发生，不排斥两者都发生的情况排斥或小张在教室上课或参加长跑比赛非此即彼，不可兼得非联结词表示近似数的或去主楼需6分钟或8分钟表示近似数 注：命题逻辑中的析取词注：命题逻辑中的析取词表示的是可表示的是可兼或，即允许兼或，即允许PQPQ中的中的P P和和Q Q同时为真。同时为真。 例5(1)李强是100米或400米赛跑冠军。 (2)今天晚上我在家看电视或去剧场看戏。 解（1）可兼或。设P：李强是100米赛冠军，Q：李强是400米赛冠军，则(1)表示为PQ。 （2）排斥或。若设P：今天晚上我在家看电视，Q：今天晚上我去剧场看戏，则(2)可以表示为(PQ)(PQ)，也可用后面介绍的异或联结词表示

8、为PQ。4.条件词条件词(conditional connective ) 定义定义1.7 复合命题复合命题“如果如果P，则，则Q”称为称为P与与Q的条的条件式，记作件式，记作PQ，读作如果，读作如果P则则Q。其中。其中P称为前件称为前件(Premise)，Q称为后件称为后件(Consequence)。PQ为假当为假当且仅当且仅当P为真而为真而Q为假。为假。 在自然语言中，“如果”与“则”之间常有因果联系，否则没有意义，但对条件命题PQ来说，只要P和Q能够确定真值，PQ即成为命题。在条件命题中，若前提为假时，条件命题的真值为真，称为善意的推断。前件假而整个句子为真的例子，在自然语言中也是常见的

9、，如：假如给我一根合适的杠杆，我可以把地球撬起来。 条件式PQ表示的基本逻辑关系是：Q是P的必要条件或P是Q的充分条件。复合命题“只要P，就Q”、“因为P，所以Q”、“除非除非Q Q，才，才P P”、“除非除非Q Q，否则，否则非非P P”、“P P仅当仅当Q Q”、“只有只有Q Q，才，才P P”等均可符号化为PQ的形式。 例6 (1)只要不下雨，我就骑自行车上班。 (2)只有不下雨，我才骑自行车上班。 解 设P：天下雨，Q：我骑自行车上班。则(1)可符号化为PQ；(2)表示为QP。5.双条件词双条件词(biconditional connective ) 定义定义1.8 复合命题复合命题“

10、P当且仅当当且仅当Q”称为称为P和和Q的双条的双条件复合命题，记作件复合命题，记作PQ，读作，读作P当且仅当当且仅当Q。PQ为为真当且仅当真当且仅当P与与Q的真值相同。的真值相同。 例7 (1)两个三角形全等当且仅当它们的三组对应边相等。 (2) 224当且仅当雪是黑的。 解解(1)(1)设设P P：两个三角形全等，：两个三角形全等，Q Q：两个三角形的：两个三角形的三组对应边相等，则三组对应边相等，则(1)(1)可符号化为可符号化为P PQ Q。 (2)(2)设设P P：2 22 24 4，Q Q：雪是黑的，则：雪是黑的，则(2)(2)可符号可符号化为化为P PQ Q。 命题符号化命题符号化

11、的目的在于用五个联结词将日常语言中的命题转化为数理逻辑中的形式命题，其关键在于对自然语言中语句之间的逻辑关系以及命题联结词的含义要有正确的理解，使用适当的联结词：（1）确定语句是否是一个命题；（2）找出句中连词，用适当的命题联结词表示。 Assignments（作业） 第30页: 3（偶数小题）1.2命题公式、翻译与真值表命题公式、翻译与真值表1.2.1 命题公式命题公式1.2.2 命题的符号化命题的符号化1.2.3 真值表真值表1.2.1 命题公式（命题公式（ logical expression ） 定义定义1.9 (1)单个命题变元是命题公式。单个命题变元是命题公式。 (2)如果如果A是

12、命题公式，那么是命题公式，那么 A也是命题公式。也是命题公式。 (3)如果如果A、B是命题公式，那么是命题公式，那么(AB)、(AB)、(AB)和和(AB)是命题公式。是命题公式。 (4)经过有限次地使用经过有限次地使用(1)、(2)、(3)所组成的有意所组成的有意义的符号串都是命题公式。义的符号串都是命题公式。 例1: 1、 (PQ)， 2、(P(PQ)， 3、(PQ)(QR)(PR) 都是命题公式。而PQ，(PQ)(Q)，(PQ都不是命题公式。注：注： 1、 一个命题公式一般无真假。只有对其所有的变元指派以确定的命题（即真值）后，它才有真值； 2、 命题公式无限多； 为了减少命题公式中的括

13、号数量，我们规定：联结词的优先次序( Precedence of logical connectives )依次为：、；规定具有相同优先级的联结词，按出现的先后次序进行计算，其括号可以省去；最外层的括号可以省去。 定义定义1.10 设设B是命题公式是命题公式A的一部分，且的一部分，且B也是命题公式，则称也是命题公式，则称B是是A的子公式。的子公式。 例如，PQ和QR都是(PQ)(QR)(PR)的子公式。1.2.2 命题的符号化命题的符号化 把一个用文字叙述的命题相应的写成把一个用文字叙述的命题相应的写成由命题标识符、联结词和圆括号表示的由命题标识符、联结词和圆括号表示的命题公式称为命题的符号化

14、或翻译。命题公式称为命题的符号化或翻译。 把命题符号化，是不管具体内容而把命题符号化，是不管具体内容而突出思维形式的一种方法。突出思维形式的一种方法。 例2 将下列命题符号化。 (1)小王现在在宿舍或在图书馆。 (2)李明既聪明又用功。 (3) 是有理数的话， 也是有理数。 (4)张三与李四是表兄弟。 (5)除非你努力，否则你将失败。 (6)除非天气好，我才骑自行车上班。 (7)小王晚上要回家，除非天下大雨。 (8)只有睡觉才能恢复疲劳。 (9)只要我还有口气，我就要战斗。 (10)A中没有元素，A就是空集。 (11)如果我上街，我就去书店看看，除非我很累。222(1)该命题符号化为(PQ)或

15、(PQ)(PQ)，其中，P：小王现在在宿舍，Q：小王现在在图书馆。(2)符号化为PQ，其中，P：李明聪明，Q：李明用功。(3)符号化为PQ，其中，P： 是有理数，Q： 是有理数。(4)只能将其符号化为P的形式，因为“张三是表兄弟”，“李四是表兄弟”都不是命题。(5)符号化为PQ，其中，P：你努力，Q：你失败。(6)符号化为PQ，其中，P：我骑自行车上班，Q：天气好。(7)符号化为QP，其中，P：小王晚上要回家，Q：天下大雨。(8)符号化为QP，其中，P：睡觉，Q：恢复疲劳。(9)符号化为PQ，其中，P：我还有口气，Q：我就要战斗。(10)符号化为PQ，其中，P：A中没有元素，Q：A就是空集。(

16、11)符号化为(RP)Q，其中，P：我上街，Q：我去书店看看，R：我很累。2221.2.3 真值表真值表 定义定义1.11 设设A是一个命题公式，是一个命题公式，p1、p2、pn为出现在为出现在A中的所有命题变元。给中的所有命题变元。给p1、p2、pn指定一组真值，称为对指定一组真值，称为对A的一的一个赋值个赋值( Assignment )。若指定的一组值使。若指定的一组值使A为为真，称这组值为真，称这组值为A的一个成真赋值，若使的一个成真赋值，若使A为为假，称这组值为假，称这组值为A的一个成假赋值。的一个成假赋值。 若A有n个不同的命题变元，则有2n组不同的赋值。 定义定义1.12 设设A是

17、含有是含有n个命题变元的命题个命题变元的命题公式，将命题公式公式，将命题公式A在所有赋值之下取值的情在所有赋值之下取值的情况汇列成表，称为况汇列成表，称为A的真值表的真值表( truth table )。 为列出一个公式的真值表，我们约定：命题变元按字典序排列；对公式的每个解释，以二进制从小到大列出；当公式较复杂时，可先列出子公式的真值，最后列出所给公式的真值。 例3 求下列命题公式的真值表，并求其成真赋值和成假赋值。 (1)(PQ)(PQ)。 (2)(PQ)Q。 (3)(PQ)R。(1)(PQ)(PQ)。 P QPQPQ(PQ)(PQ)1101110111110 00 11 01 1P QP

18、Q(P Q)(PQ)Q1101001000000 00 11 01 1(2)(PQ)Q。P Q RPQR(PQ)R1111001110101010101000100 0 00 0 10 1 00 1 10 01 0 11 011 1 1(3)(PQ)R。 AssignmentsAssignments（作业）（作业） 第30页: 41.3 公式分类与等价式公式分类与等价式 1.3.1 公式分类公式分类1.3.2 等价公式（等值演算）等价公式（等值演算）1.3.3 基本等价式基本等价式-命题定律命题定律1.3.4 代入规则和替换规则代入规则和替换规则1.3.5 证明命题公式等价的方法证明命题公式等

19、价的方法 定义定义1.13 设设A是一个命题公式，对是一个命题公式，对A所有可能的解释：所有可能的解释： (1)若若A都为真，称都为真，称A为永真式或重言式。为永真式或重言式。 (2)若若A都为假，称都为假，称A为永假式或矛盾式。为永假式或矛盾式。 (3)若至少存在一个解释使得若至少存在一个解释使得A为真，称为真，称A为可满足式。为可满足式。1.3.1 公式分类公式分类 例1 从上一节真值表可知，命题公式(PQ)(PQ)为重言式，(PQ)Q为矛盾式，PQ)R为可满足式。注：注： 1、 永真式必为可满足式，反之则不然；永真式的否定是永假式，反之亦然； 2、 决定一个公式是否是一个永真式、永假式或

20、可满足式有三种方法：真值表法（适用于变元少而简单的公式）、求主范式法和公式（等价替换）法； 定义定义1.14 设设A和和B是两个命题公式，如是两个命题公式，如A和和B在任在任意解释下，其真值相同，称意解释下，其真值相同，称A与与B是等价的或逻辑相是等价的或逻辑相等等(Logically equivalent)，记作，记作AB。1.3.2 等价公式（等值演算）等价公式（等值演算） 表示的是两个命题公式之间的一种逻辑关系，它具有如下三个性质： （1）自反性：A A。 （2）对称性：若A B，则B A。 （3）传递性：若A B 且 B C，则A C。 例例2 证明PQ(PQ)(QP)。P QPQQP

21、PQ(PQ)(QP)1101101110010 00 11 01 11001证明：证明： 命题公式PQ和(PQ)(QP)的真值表如下表所示： 由上表可知，PQ与(PQ)(QP)在任意解释下真值相同，所以PQ(PQ)(QP)。 定理定理1.1 对命题公式对命题公式A和和B，A B当且仅当当且仅当A B是重言式。是重言式。 证明证明 若若A AB B是重言式，则在任一解释下，是重言式，则在任一解释下，A AB B的真值都的真值都为真。依为真。依A AB B的定义知，当的定义知，当A AB B为真时，为真时，A A和和B B有相同的真值。有相同的真值。于是，在任一解释下，于是，在任一解释下，A A和

22、和B B都有相同的真值，从而有都有相同的真值，从而有A AB B。 反过来，若反过来，若A AB B，则在任一解释下，则在任一解释下A A和和B B都有相同的真值，都有相同的真值，依依A AB B的定义知，此时的定义知，此时A AB B为真，从而为真，从而A AB B是重言式。是重言式。1.3.3 基本等价式基本等价式(1)双重否定律双重否定律 AA(2)结合律结合律 (AB)CA(BC) (AB)CA(BC) (AB)CA(BC)(3)交换律交换律 ABBA，ABBA，ABBA(4)分配律分配律 A(BC)(AB)(AC) A(BC)(AB)(AC)(5)等幂律等幂律(恒等律恒等律) AAA

23、，AAA(6) 吸收律吸收律 A(AB)A，A(AB)A(7)德德摩根律摩根律 (AB)A B， (AB)A B(8)同一律同一律 AFA，ATA(9)零律零律 ATT，AFF(10)补余律补余律 A AT，A AF(11)条件转化律条件转化律 (AB)ABBA(12)双条件转化律双条件转化律 (AB)(AB)(BA)(AB)( A B) 定理定理1.2(代入规则代入规则)在一个永真式在一个永真式A中，任何一个中，任何一个原子命题变元原子命题变元R出现的每一处用另一个公式代入，出现的每一处用另一个公式代入，所得公式所得公式B仍为永真式。仍为永真式。1.3.4 代入规则和替换规则代入规则和替换规

24、则 证明 因为永真式对任何解释，其真值都是真，与每个命题变元指派的真假无关，所以，用一个命题公式代入到原子命题变元出现的每一处，所得命题公式的真值仍为真。 例3 证明(PQ)(PQ)为永真式。 证明 因为RR为永真式，由代入规则可知，将R用(PQ)代入得到的式子仍为永真式，所以(PQ)(PQ)为永真式。 定理定理1.3 (替换规则替换规则)设设A1是公式是公式A的子公式，若的子公式，若A1B1，并且将，并且将A中的中的A1用用B1替换，得到公式替换，得到公式B，则则AB。 证明 因为A1B1，即对于它们的命题变元的任意一组赋值，A1与B1的真值相同。所以，将A中的A1用B1替换后，A与B在对其

25、命题变元的任意赋值下，它们的真值也相同，故AB。 1.3.5 证明命题公式等价的方法证明命题公式等价的方法 常用的方法有三种：真值表法真值表法，公式法公式法和求主范式求主范式法法。其中公式法基于基本等价式、代入规则和替换规则。例4 证明 (1)P(QR)Q(PR) (2)(PQ)(PQ)(PQ)证明:(1)P(QR)P(QR) P(QR)Q(PR)Q(PR)Q(PR)(2)(PQ)(PQ) (PQ)(PQ)(PQ)(QP) (PQ)(QP)(PQ)(QP) (PQ) 例5 某件事是甲、乙、丙、丁4人中某一个人干的，询问4人后回答如下：(1)甲说是丙干的；(2)乙说我没干；(3)丙说甲讲的不符合

26、事实；(4)丁说是甲干的。若其中3人说的是对的、1人说的不对，问是谁干的？ 解 设A：这件事是甲干的，B：这件事是乙干的，C：这件事是丙干的，D：这件事是丁干的。 4人所说命题分别用Q、R、S、M表示，则(1)、(2)、(3)、(4)分别符号化为： QABCD RB SCMABCD P(QRSM)(QRSM) (QRSM)(QRSM) 而(QRSM)ABCD，其它三项F，所以P为真时，ABCD为真，所以这件事是甲干的。3人对、1人错的命题P符号化为： 例6 A、B、C、D四人进行百米竞赛，观众甲、乙、丙预报比赛的名次为甲：C第一、B第二；乙：C第二、D第三；丙：A第二、D第四。比赛结束后发现甲

27、、乙、丙每人报告的情况都是各对一半，试问实际名次如何(假如无并列者)？ 解 设Ai表示A第i名，Bi表示B第i名，Ci表示C第i名，Di表示D第i名，则依据题意有： (C1B2)(C1B2)T (1) (C2D3)(C2D3)T (2) (A2D4)(A2D4)T (3) 因为真命题的合取仍为真命题，所以(1)(2) (C1B2C2D3)(C1B2C2D3)(C1B2C2D3)(C1B2C2D3)(C1B2C2D3)(C1B2C2D3)T (4)(3)(4) (A2D4C1B2C2D3)(A2D4C1B2C2D3)(A2D4C1B2C2D3)(A2D4C1B2C2D3)A2D4C1B2C2D3

28、T所以，A第二、B第四、C第一、D第三。Assignments（作业）（作业） 第30页: 5（2）、（4）、（6） 6（2）、（4）、（6）1.4 对偶式与蕴涵式对偶式与蕴涵式1.4.1 对偶式对偶式1.4.2 蕴涵式蕴涵式1.4.3 蕴涵式的证明方法蕴涵式的证明方法1.4.1对偶式对偶式( Dual ) 例例1 (PQ)R的对偶式为的对偶式为(PQ)R，PF的的对偶式为对偶式为PT。 定义定义1.15 在给定的仅使用联结词在给定的仅使用联结词 、和和的命题公式的命题公式A中，若把中，若把T和和F互换、互换、和和互换得到一个命题公式互换得到一个命题公式A*，则称，则称A*是是A的的对偶式，或

29、说对偶式，或说A和和A*互为对偶式。互为对偶式。 证明证明 由德由德摩根律得：摩根律得： 定理定理1.4 设设A和和A*互为对偶式，互为对偶式，P1、Pn是出现是出现在在A和和A*中的所有原子命题变元，则：中的所有原子命题变元，则： (1) A(P1，Pn)A*( P1， Pn)。 (2)A( P1， Pn)A*(P1，Pn)。PQ( P Q) PQ( P Q) 故故 A(P1，Pn)A*( P1， Pn) 同理同理A( P1， Pn)A*(P1，Pn) 定理定理1.5(对偶定律对偶定律) 若若AB，则，则A*B*。 证明证明 设设P1、Pn是出现在是出现在A和和B中的所有原子中的所有原子命题

30、变元。命题变元。 A A* *(P(P1 1，P Pn n) )B B* *(P(P1 1，P Pn n) ) A A* *( ( P P1 1， P Pn n) )B B* *( ( P P1 1， P Pn n) ) 若若A AB B，即，即A(PA(P1 1，P Pn n) ) B(PB(P1 1,P,Pn n) )，则，则 A(P1，Pn)B(P1，Pn)由定理由定理1.4得得再由代入规则得再由代入规则得 证明 A*(P，Q，R) 例2 设A(P，Q，R)P(QR)，证明A*(P，Q，R)P(QR)。A(P，Q，R) (P(QR) P(QR)1.4.2 蕴涵式蕴涵式 定理定理1.6 A

31、B的充要条件是的充要条件是AB且且BA 定义定义1.16 设设A和和B为命题公式，若为命题公式，若AB是是永真式，则称永真式，则称A蕴含蕴含B，记作，记作AB，称，称AB为蕴含式或永真条件式。为蕴含式或永真条件式。 证明 若AB，则AB为永真式，而AB(AB)(BA)，故AB和BA皆为真，即AB且BA。 反之，若AB且BA，则AB和BA为永真式，于是(AB)(BA)永真，即AB永真式，所以AB成立。 (1)化简式 PQP，PQQ 下面给出常用的14组蕴涵公式，它们的正确性可用后面介绍的真值表法、分析法和公式法来证明。(8)拒取式 Q(PQ)P(7)假言推论 P(PQ)Q(6)化简式变形 (PQ

32、)Q (5)化简式变形 (PQ)P (4)附加式变形 QPQ(3)附加式变形 PPQ (2)附加式 PPQ 除了上述蕴含式外，等价式也可作为蕴含式，即若有AB，则有AB和BA。 (9)析取三段论 P(PQ)Q(14)前件附加 PQ(PR)(QR) PQ(PR)(QR) (13)析取构造二难 (PQ)(RS)(PR)QS (12)合取构造二难 (PQ)(RS)(PR)QS(11)双条件三段论 (PQ)(QR)PR(10)条件三段论 (PQ)(QR)PR 由上表可知，当(Q(PQ)为真时，P为真，所以Q(PQ)P。 1.4.3 蕴涵式的证明方法蕴涵式的证明方法1.真值表法例3 Q(PQ)P证明 命

33、题公式的真值表如下表所示：P QPQQ (PQ)P1101100011000 00 11 01 12.分析法 形式形式1：若：若A为真推出后件为真推出后件B也真，则也真，则AB。 形式形式2：若：若B为假推出前件为假推出前件A也假，则也假，则AB。 例4 证明(1)Q(PQ)P (2)(PQ)(PR)(QR)R (1)若Q(PQ)为真，则Q与(PQ)都为真，有Q为假、(PQ)为真，于是P为真，故Q(PQ)P。 (2)若R为假，当P和Q有一个为真时，有PR与QR有一个为假，此时(PQ)(PR)(QR)为假；当P和Q都为假时，有PQ为假，因此也有(PQ)(PR)(QR)为假。故(PQ)(PR)(Q

34、R)R。证明3.3.公式法公式法 例5 证明P(PQ)Q所以P(PQ)Q。 证证明明因为(P(PQ)Q (P(PQ)Q(PP)(PQ)Q(PQ)Q(PQ)Q(PQ)QP(QQ)PTT1.5 联结词的扩充与全功能联结词的扩充与全功能联结词组联结词组1.5.1 联结词的扩充联结词的扩充1.5.2 与非、或非、异或的性质与非、或非、异或的性质1.5.3 全功能联结词组全功能联结词组1.5.1 联结词的扩充联结词的扩充 定义定义1.17 设设P、Q为两个命题，则：为两个命题，则： (1)复合命题复合命题“P与与Q的否定的否定”称为称为P与与Q的合取非的合取非(与非与非)，记为，记为P Q。即。即P Q

35、(PQ)。 (2)复合命题复合命题“P或或Q的否定的否定”称为称为P与与Q的析取非的析取非(或非或非)，记为，记为P Q。即。即P Q(PQ)。 (3)复合命题复合命题“如果如果P则则Q的否定的否定”称为称为P与与Q的条的条件非件非(条件否定条件否定)，记为，记为 。即。即(PQ)。 (4)复合命题复合命题“P、Q之中恰有一个成立之中恰有一个成立”称为称为P与与Q的异或的异或 (双条件非、不可兼析取双条件非、不可兼析取)，记为，记为P Q。 1.5.2 与非、或非、异或的性质与非、或非、异或的性质1.“与非”的性质(1)PQQP(2)PP(PP)P(3)(PQ)(PQ)(PQ)PQ (4)(P

36、P)(QQ)PQ (PQ)PQ2.“或非”的性质(1)PQQP(2)PP(PP)P(3)(PQ)(PQ)(PQ)PQ(4)(PP)(QQ)PQPQ3.“异或”的性质(1)PQQP(2)(PQ)RP(QR)(3)P(QR)(PQ)(PR)(4)PQ(PQ)(PQ)(5)PPF，FPP，TPP(6)PQ(PQ) 例1 设P、Q、R为命题公式。如果PQR，则PRQ，QRP，且PQR为矛盾式。如果PQR，则证明PRPPQFQQQRQPQFPP所以，PQRRRF1.5.3 全功能联结词组全功能联结词组 定义定义1.18 设设G是一个联结词的集合，若任意一个是一个联结词的集合，若任意一个命题公式都可用命题

37、公式都可用G中联结词构成的的公式来表示，则中联结词构成的的公式来表示，则称称G为全功能联结词组。如在为全功能联结词组。如在G中去掉任何一个联结中去掉任何一个联结词，就不再具有这种特性，就称其为最小全功能联结词，就不再具有这种特性，就称其为最小全功能联结词组。词组。 例2 证明是最小全功能联结词组。PPP证明PQ(PP)(QQ)PQ(PQ)(PQ)所以，是最小全功能联结词组。 PQP(QQ)PQ(P(QQ)(Q(PP)1.6 公式标准型公式标准型范式范式1.6.1 简单合取式与简单析取式简单合取式与简单析取式1.6.2 析取范式与合取范式析取范式与合取范式1.6.3 范式的应用范式的应用 例如，

38、P、P、PQ、PQP都是简单合取式，而P、P、PQ都是简单析取式。1.6.1 简单合取式与简单析取式简单合取式与简单析取式 定义定义1.19 在一公式中，仅由命题变元及否在一公式中，仅由命题变元及否定构成的合取式称为简单合取式；仅由命题变定构成的合取式称为简单合取式；仅由命题变元及否定构成的析取式称为简单析取式。元及否定构成的析取式称为简单析取式。 定理定理1.7 简单合取式为永假式当且仅当它简单合取式为永假式当且仅当它同时含有某个命题变元及其否定。同时含有某个命题变元及其否定。 定理定理1.8 简单析取式为永真式当且仅当简单析取式为永真式当且仅当它同时含有某个命题变元及其否定。它同时含有某个

39、命题变元及其否定。 设A为简单合取式，其包含的所有命题变元为p1、p2、pn。 若A为永假式，但不同时含有某个命题变元及其否定，则不妨设Ap1pipi1pn，于是当p1、p2、pi的真值都是真，而pi1、pn的真值都是假时，A的真值为真，与A为永假式矛盾。 反之，若A同时含有某个命题变元及其否定，显然有A为永假式。 定理1.17的证明1.6.2 析取范式与合取范式析取范式与合取范式 定义定义1.20 若干个简单合取式的析取称为析若干个简单合取式的析取称为析取范式；若干个简单析取式的合取称为合取范取范式；若干个简单析取式的合取称为合取范式。式。 定义定义1.21 与公式与公式A等价的析取范式称为

40、公等价的析取范式称为公式式A的析取范式，与公式的析取范式，与公式A等价的合取范式称等价的合取范式称为公式为公式A的合取范式。的合取范式。 定理定理1.9 对任意命题公式，都存在与其等对任意命题公式，都存在与其等价的析取范式和合取范式。价的析取范式和合取范式。 (1)使用命题定律消去除、以外公式中出现的所有联结词； (2)消去； (3)使出现在命题变元之前； (4)用结合律、分配律等将公式化为所需范式。下面给出求公式的范式的步骤：(PQ)(PQ)例1 求(PQ)(PQ)的析取范式。解(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQPQ)(PQ)(PQ)(PQPQ)(PP)(PQ)(QP)(

41、QQ)(PQ)(PQ)例2 求(PQ)(PQ)的合取范式。解(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQP)(PQQ)(PPQ)(QPQ)1.6.3 范式的应用范式的应用 定理定理1.10 公式公式A为矛盾式当且仅当为矛盾式当且仅当A的析的析取范式的每个简单合取式至少同时含有一个命取范式的每个简单合取式至少同时含有一个命题变元及其否定。题变元及其否定。 定理定理1.11 公式公式A为永真式当且仅当为永真式当且仅当A的合的合取范式的每个简单析取式至少同时含有一个命取范式的每个简单析取式至少同时含有一个命题变元及其否定。题变元及其否定。 (2)(PQ)Q

42、例3 判断下列公式的类型： (1)P(QR)(PR) (2)(PQ)Q解由定理1.11可知，P(QR)(PR)是永真式。(1)P(QR)(PR) P(QR)(PR)PQR(PR) (PQRP)(PQRR)(PQ)Q PQQ 由定理1.10可知，(PQ)Q为矛盾式。1.7 公式主范式公式主范式1.7.1 主析取范式主析取范式1.7.2 主合取范式主合取范式1.7.3 主范式的应用主范式的应用PQ，PQ，PQ，PQ。1.7.1 主析取范式主析取范式 定义定义1.22在含有在含有n个命题变元的简单合取个命题变元的简单合取式中，若每个命题变元与其否定不同时存在，式中，若每个命题变元与其否定不同时存在，

43、而两者之一出现一次且仅出现一次，称该简单而两者之一出现一次且仅出现一次，称该简单合取式为小项。合取式为小项。1.小项的概念及性质 PQR，PQR，PQR PQR，PQR，PQR PQR，PQR。例如2个命题变元P和Q产生4个小项：3个命题变元P、Q和R产生8个小项： 小项的二进制编码：约定命题变元按字典顺序排列，命题变元与1对应，命题变元的否定与0对应，则得到小项的二进制编码，记为mi，其下标i是由二进制转化的十进制数。n个命题变元形成的2n个小项，分别记为：m0，m1，。 n个命题变元共形成 个小项。两个命题变元P和Q的小项真值表如下表所示：m(二进制)m00m01m10m11P QPQPQ

44、PQPQ0 00 11 01 11000010000100001m(十进制)m0m1m2m3？2n由真值表可得小项具有如下的性质：(1)各小项的真值表都是不同的。 (2)每个小项只有当赋值与其对应的二进制编码相同时，其真值为真，且其真值1位于主对角线上。(3)任两不同小项的合取式是永假式。(4)所有小项的析取式为永真式。 定义1.23 由若干个不同的小项组成的析取式称为主析取范式；与A等价的主析取范式称为A的主析取范式。2.主析取范式定义与存在定理 定理1.12 任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式，并且是惟一的。 证明 设A是A的析取范式，即AA。若A的某个简单合取

45、式Ai中不含命题变元P及其否定P，将Ai展成形式AiAiTAi(PP)(AiP)(AiP)，继续这个过程，直到所有的简单合取式成为小项。然后，消去重复的项及矛盾式之后，得到A的主析取范式。 下面证明其惟一性。 若A有两个与之等价的主析取范式B和C，则BC。由B和C是A的不同的主析取范式，不妨设小项mi只出现在B中而不在C中，于是i的二进制为B的成真赋值，C的成假赋值，与BC矛盾。因而A的主析取范式是惟一的。 定理1.13 在真值表中，命题公式A的真值为T的赋值所对应的小项的析取即为此公式A的主析取范式。 3.求主析取范式的方法1)1)真值表法真值表法 则其赋值所对应的小项一定不是m1、mk中的

46、某一项，此时m1、m2、mk都为假，故B也为假。 证明设A真值为T的赋值所对应的小项为m1、mk令Bm1m2mk。下证AB。 若A为真， 若A为假， 则其赋值所对应的小项一定是m1、mk中的某一项，不妨设为mi，因为mi为真，而m1、mi1、mi1、mk都为假，故B也为真。 因此，AB。 例1 用真值表法求(PQ)(PQ)的主析取范式。 解 (PQ)(PQ)的真值表如下表所示： 从上表知，该公式仅在其真值表的00行和10行处取真值1，所以(PQ)(PQ)m0m2。 P QPQ(PQ)PQ(PQ)(PQ)0111100011010 00 11 01 11010 例2 用真值表法求(PQ)R的主析

47、取范式。 所以， (PQ)Rm1m3m5m6m7。 解 (PQ)R的真值表如下表所示：P Q R(PQ)(PQ)R从左表知，该公式仅在其真值表的001、011、101、110、111处取真值100000011010101110 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 2)2)公式法公式法 (4)将小项按顺序排列。 求主析取范式的步骤如下： (1)求A的析取范式A； (2)若A的某简单合取式B中不含某个命题变元P或其否定P，则将B展成形式 BB1B(PP)(BP)(BP) (3)将重复出现的命题变元、矛盾式及重复出现的小项都消去；(PQ)Q 例3 用公式法求

48、(PQ)Q的主析取范式。 解 (PQ)Q (PQ)Q (PQ)(PP)Q) (PQ)(PQ)(PQ) m1m3。 (PQ)(PQ)例4 用公式法求(PQ)R)P的主析取范式。 解 (PQ)R)P(PP)QR)(P(QQ) (PQ)R)P(PQ)R)P (PR)(QR)P(QR)P (PQR)(PQR)(PQ)(PQ) (PQR)(PQR)(PQR) (PQR)(PQR)(PQR) m2m4m5m6m7。 (PQR)(PQR)(PQR) (PQR)(PQR) (PQR)(PQR)(PQ(RR) (PQ(RR) PQ，PQ，PQ，PQ。1.7.2 主合取范式主合取范式 定义定义1.24 在含有在含

49、有n个命题变元的简单析取个命题变元的简单析取式中，若每个命题变元与其否定不同时存在，式中，若每个命题变元与其否定不同时存在，而两者之一出现一次且仅出现一次，称该简单而两者之一出现一次且仅出现一次，称该简单析取式为大项。析取式为大项。1.大项的概念及性质 PQR， PQR， PQR PQR， PQR， PQRPQR， P QR。 例如2个命题变元P和Q产生4个大项：3个命题变元P、Q和R产生8个大项： 大项的二进制编码：约定命题变元按字典顺序排列，命题变元与0对应，命题变元的否定与0对应，则得到大项的二进制编码，记为Mi，其下标i是由二进制转化的十进制数。n个命题变元形成的2n个大项，分别记为：

50、M0，M1，。 n个命题变元共形成 个大项。两个命题变元P和Q的大项真值表如下表所示：M(二进制)M00M01M10M11P QPQPQPQPQ0 00 11 01 10111101111011110M(十进制)M0M1M2M3？2n由真值表可得大项具有如下的性质：(1)各大项的真值表都是不同的。 (2)每个大项只有当赋值与其对应的二进制编码相同时，其真值为假，且其真值0位于主对角线上。(3)任两不同大项的析取式是永真式。(4)所有大项的合取式为永假式。 定义1.25 由若干个不同的大项组成的合取式称为主合取范式；与A等价的主合取范式称为A的主合取范式。2.主合取范式定义与存在定理 定理1.1

51、4 任意含n个命题变元的非永真命题公式A都存在与其等价的主合取范式，并且是惟一的。 定理1.15 在真值表中，命题公式A的真值为F的赋值所对应的大项的合取即为此公式A的主合取范式。 3.求主合取范式的方法1)1)真值表法真值表法 例5 用真值表法求(PQ)Q的主合取范式。 解 (PQ)Q的真值表如下表所示： 从上表知，该公式仅在其真值表的00行和10行处取真值0，所以(PQ)Q M0M2。 P QPQ ( PQ) Q110101010 00 11 01 1 2)2)公式法公式法 (4)将大项按顺序排列。 求主合取范式的步骤如下： (1)求A的合取范式A； (2)若A的某简单析取式B中不含某个命

52、题变元P或其否定P，则将B展成形式 BB0B(PP)(BP)(BP) (3)将重复出现的命题变元、永真式及重复出现的大项都消去；P(QR) 例6 用公式法求(PQ)(PR)的主合取范式。 解 (PQ)(PR)(PQ)(PR) (PQ)(PQ)(PQR)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)M0M1M2M3M7。 定理1.17 设A是含有n个命题变元的命题公式，且A的主析取范式中含k个小项m1、m2、mk，则A的主析取范式中必含有其余的2nk个小项，记为 ，且 A 4.主析取范式与主合取范式之间的关系 定理1.16 小项mi与大项Mi满足miMi，Mimi。 证

53、明 由小项和大项的定义及对偶性即得。 例7 求(PQ)(PR)的主析取范式和主合取范式。M1M3M4M5 证明 (PQ)(PR) (PQ)(PR)(PR)(PQ) (PQ)(PR)(PR)(PQ) (PQ)(PR)(PR)(PQ) (PQ)(PR)(PQR)(PQR)(PQR)(P QR) m0m2m6m7 1.7.3 主范式的应用主范式的应用 定理定理1.18 设设A是含是含n个命题变元的命题公个命题变元的命题公式，则：式，则： (1)A为永真式当且仅当为永真式当且仅当A的主析取范式含的主析取范式含有全部有全部2n个小项。个小项。 (2)A为矛盾式当且仅当为矛盾式当且仅当A的主合取范式含的主

54、合取范式含有全部有全部2n个大项。个大项。 (3)若若A的主析取范式至少含有一个小项，的主析取范式至少含有一个小项，则则A是可满足式。是可满足式。 1.判定命题公式的类型例8 判断下列命题公式的类型： (1)(PQ)(QR)(PR) (2)(PQ)P)Q (3)(PQ)Q证明 (1) (PQ)(QR)(PR)(PQR)(PQR) (PQR)(PQR)(PQ) (PQ)(PR)(PR) (PQR)(PQR)(PQR) (PQR)(PQR)(PQR) (PQR)(PQR)(PQR) (PQR)(PQR)(PQR) M0M1M2M3M4M5M6M7 (2)(PQ)P)Q(PQ)(PQ)(PQ)(PQ

55、)(PQ)(PQ)P)Q (PQ)PQ(PQ)PQ (PQ)(P(QQ)(PP)Q) m0m1m2m3 (3) (PQ)Q因此，(1)为永假式，(2)为永真式，(3)为可满足式。 (PQ)(PQ)(PQ) (PQ)Q(PQ)Q (PQ)(PP)Q) (PQ)(PQ)m1m3 2.判断两个命题公式是否等价例9 判断(PQ)(PR)与P(QR)是否等价。P(QR) 证明 因为(PQ)(PR) (PQ)(PR) (PQ(RR)(P(QQ)R) (PQR)(PQR)(PQR)(PQR) M4M5M6 P(QR)(PQ)(PR)所以，(PQ)(PR)P(QR)M4M5M6 3.求命题公式的成真赋值和成假

56、赋值 由于小项对应的是成真赋值，大项对应的是成假赋值，所以可以根据命题公式的主范式求其成真赋值和成假赋值。 例如，由P(QR)M4M5M6可知，P(QR)的成假赋值为：100、101、110，成真赋值为：000、001、010、011、111。1.8 命题逻辑的推理理命题逻辑的推理理1.8.1 推理规则推理规则1.8.2 推理定律推理定律1.8.3 判断有效结论的常用方法判断有效结论的常用方法1.8.1 推理规则推理规则 (1)P规则：在推导过程中，在任何地方都规则：在推导过程中，在任何地方都可引用前提。可引用前提。 (2)T规则：在推导过程中，前面导出的有规则：在推导过程中，前面导出的有效结

57、论都可作为后续推导的前提。效结论都可作为后续推导的前提。 定义定义1.261.26 若A1A2AnB为重言式，则称A1，A2，An推结论B的推理正确，B是A1，A2，An的有效结论，记为A1，A2，An B或A1，A2，AnB。 (6)分离规则：如果已知命题公式分离规则：如果已知命题公式AB和和A，则有命题公式则有命题公式B。 (5)置换规则：在推理过程中，命题公式置换规则：在推理过程中，命题公式中的任何部分公式都可以用与之等值的命题中的任何部分公式都可以用与之等值的命题公式来置换。公式来置换。 (4)代入规则：在推理过程中，对重言式中的代入规则：在推理过程中，对重言式中的命题变元可使用代入规则。命题变元可使用代入规则。 (3)CP规则：要证规则：要证A1，An AB，只，只需证明需证明A1，A2，An，A B。 (6)QPQ (3) (PQ) Q (4)PPQ (5) PPQ (7) P(PQ)Q (8)P(PQ)Q 1.8.2 推理定律推理定律 (1)PQP (2)