第1章命题逻辑

1、第第1章章 命题逻辑命题逻辑 2021-8-8 第第1章章 命题逻辑命题逻辑 1.1 命命 题及联结词题及联结词 1.2 命题公式与真值表命题公式与真值表 1.3 逻辑恒等式与永真逻辑恒等式与永真蕴涵式蕴涵式 1.4 命题范式命题范式 1.5 命题演算推理方法命题演算推理方法 第第1章章 命题逻辑命题逻辑 2021-8-8 1.1 命命 题与联结词题与联结词 1.1.1 命题的基本概念命题的基本概念 定义定义1.1 能判断真假的陈述句称为命题能判断真假的陈述句称为命题。 一个命题的真或假称为命题的真值，分别用一个命题的真或假称为命题的真值，分别用T(或或1)与与F(或或0)表表 示。真值为真的

2、命题称为真命题，真值为假的命题称为假命示。真值为真的命题称为真命题，真值为假的命题称为假命 题。题。 判断一个句子是否为命题应分为两步：首先判断它是否判断一个句子是否为命题应分为两步：首先判断它是否 为陈述句，其次判断它能否确定真假。注意，为陈述句，其次判断它能否确定真假。注意，一个陈述句能否 判断真假，和我们是否知道它的真假是两回事。 第第1章章 命题逻辑命题逻辑 2021-8-8 例例 1 判断下列句子哪些是命题？判断下列句子哪些是命题？ (1) (1)雪是黑的。雪是黑的。 (2)(2)天气多好呀！天气多好呀！ (3)(3)别的星球上有生物。别的星球上有生物。 (4)1(4)1101101

3、110110。 (5)(5)你上网了吗？你上网了吗？ (6)(6)全体立正！全体立正！ (7)(7)x xy y5 5。 (8)(8)人有五指。人有五指。 (9)(9)现在是现在是6 6点钟。点钟。 (10)(10)我正在说谎。我正在说谎。 解解: :在上述在上述1010个句子中，个句子中，(2)(2)是感叹句，是感叹句，(5)(5)是疑问句，是疑问句，(6)(6)是祈使句，因此是祈使句，因此 它们都不是命题。它们都不是命题。(7)(7)和和(10)(10)虽然都是陈述句，但因为虽然都是陈述句，但因为(7)(7)没有确定的真值，而没有确定的真值，而 (10)(10)是悖论是悖论( (即由真能推

4、出假，也能由假推出真即由真能推出假，也能由假推出真) )，因而它们也不是命题。，因而它们也不是命题。(1)(1)、 (3)(3)、(8)(8)、(9)(9)都是命题，其中，都是命题，其中，(3)(3)虽然目前无法判断，但就其本质而言是可虽然目前无法判断，但就其本质而言是可 以判断真假的，因此我们说它是命题；以判断真假的，因此我们说它是命题；(8)(8)的真值因人而异；的真值因人而异；(9)(9)的真值因地而的真值因地而 异。异。(4)(4)这个句子所表达的内容在十进制范围中真值为假，而在二进制范围中真这个句子所表达的内容在十进制范围中真值为假，而在二进制范围中真 值为真，因此其真值由上下文而定

5、。值为真，因此其真值由上下文而定。 第第1章章 命题逻辑命题逻辑 2021-8-8 1.1.2 命题分类与命题标识符命题分类与命题标识符 定义定义1.2 不能再分解为其他命题的命题称为原子命题。由原不能再分解为其他命题的命题称为原子命题。由原 子命题和命题联结词构成的命题称为复合命题。子命题和命题联结词构成的命题称为复合命题。 例如，例例如，例1中的命题都是原子命题，而命题中的命题都是原子命题，而命题“张三和李四都是张三和李四都是 大学生大学生”是复合命题，因为它由是复合命题，因为它由“张三是大学生张三是大学生”和和“李四是李四是 大学生大学生”两个原子命题组成。两个原子命题组成。 表示原子命

6、题的符号称为命题标识符。表示原子命题的符号称为命题标识符。 例例2 P：雪是黑的。：雪是黑的。 定义定义1.3 一个命题标识符如表示真值确定的命题，则称其为个命题标识符如表示真值确定的命题，则称其为 命题常元，如果命题标识符表示真值不确定的陈述句，则称其命题常元，如果命题标识符表示真值不确定的陈述句，则称其 为命题变元。为命题变元。 第第1章章 命题逻辑命题逻辑 2021-8-8 1.1.3命题联结词命题联结词 通过命题联结词可以把原子命题复合成一个复合命题，命题通过命题联结词可以把原子命题复合成一个复合命题，命题 逻辑中常用的联结词有以下五种：逻辑中常用的联结词有以下五种：“非非”、“且且”

7、、“或或”、 “如果如果，则，则”、“当且仅当当且仅当”，下面给出它们的确切含，下面给出它们的确切含 义和符号表示。义和符号表示。 1.1.否定词否定词 定义定义1.4 1.4 复合命题复合命题“非非P P”称为命题称为命题P P的否定，记作的否定，记作 P P，读，读 作非作非P P。 P P为真当且仅当为真当且仅当P P为假。为假。 例例3 3 设设P P：离散数学是计算机专业的核心课程，：离散数学是计算机专业的核心课程，则则 P P表示离表示离 散数学不是计算机专业的核心课程。散数学不是计算机专业的核心课程。 第第1章章 命题逻辑命题逻辑 2021-8-8 2.2.合取词合取词 定义定义

8、1.5 1.5 复合命题复合命题“P且且Q”称为称为P与与Q的合取式，记作的合取式，记作 PQ，读作，读作P且且Q。PQ为真当且仅当为真当且仅当P与与Q都为真。都为真。 例例4 4设设P：今天上机，：今天上机，Q：今天下雨，则：今天下雨，则PQ表示今天上机表示今天上机 且今天下雨。且今天下雨。 PP 01 10 表11 PQP Q 000 010 100 111 表12 第第1章章 命题逻辑命题逻辑 2021-8-8 3. 析取词析取词 定义定义1.6 复合命题复合命题“P或或Q”称为称为P与与Q的析取式，记作的析取式，记作PQ， 读作读作P或或Q。PQ为假当且仅当为假当且仅当P和和Q都为假。

9、都为假。 由于自然语言中的由于自然语言中的“或或”具有多义性，包括具有多义性，包括“可兼或可兼或”、 “排斥或排斥或”和和“表示近似的或表示近似的或”，因此需要指出命题逻辑中的，因此需要指出命题逻辑中的 “或或”是指哪一种。先看下表给出的例子。是指哪一种。先看下表给出的例子。 或的含义或的含义例子例子说明说明 联结词联结词 可兼或可兼或ab0 0即即a0 0或或b0 0或或ab0 0 两者至少有一个发生，不排斥两两者至少有一个发生，不排斥两 者都发生的情况者都发生的情况 排斥或排斥或小张在教室上课或参加长跑比赛小张在教室上课或参加长跑比赛非此即彼，不可兼得非此即彼，不可兼得 非联结词非联结词表

10、示近似数的或表示近似数的或去主楼需去主楼需6 6分钟或分钟或8 8分钟分钟表示近似数表示近似数 第第1章章 命题逻辑命题逻辑 2021-8-8 表表1 3 PQ真值表真值表 P QP Q 0 0 0 1 1 0 1 1 0 1 1 1 第第1章章 命题逻辑命题逻辑 2021-8-8 命题逻辑中的析取词命题逻辑中的析取词表示的是可兼或，即允许表示的是可兼或，即允许PQ中的中的 P和和Q同时为真。同时为真。 例例5 (1)李强是李强是100米或米或400米赛跑冠军。米赛跑冠军。 (2)今天晚上我在家看电视或去剧场看戏。今天晚上我在家看电视或去剧场看戏。 解解 (1)中的中的“或或”是可兼或，可以用

11、联结词是可兼或，可以用联结词表示。设表示。设P： 李强是李强是100米赛冠军，米赛冠军，Q：李强是：李强是400米赛冠军，则米赛冠军，则(1)表示为表示为 PQ。 (2)中的中的“或或”是排斥或，不能用联结词是排斥或，不能用联结词直接表示。若设直接表示。若设P： 今天晚上我在家看电视，今天晚上我在家看电视，Q：今天晚上我去剧场看戏，则：今天晚上我去剧场看戏，则(2)可可 以表示为以表示为( PQ)(P Q)，也可用后面介绍的异或联结词表，也可用后面介绍的异或联结词表 示为示为P Q。 第第1章章 命题逻辑命题逻辑 2021-8-8 4.蕴涵联结词蕴涵联结词 定义定义1.7 复合命题复合命题“如

12、果如果P，则，则Q”称为称为P与与Q的蕴含式，记作的蕴含式，记作 PQ，读作如果，读作如果P则则Q。其中。其中P称为前件，称为前件，Q称为后件。称为后件。PQ为为 假当且仅当假当且仅当P为真而为真而Q为假。为假。 在自然语言中，在自然语言中，“如果如果”与与“则则”之间常有因果联系，否则之间常有因果联系，否则 没有意义，但对条件命题没有意义，但对条件命题PQ来说，只要来说，只要P和和Q能够确定真值，能够确定真值， PQ即成为命题。在条件命题中，若前提为假时，条件命题的即成为命题。在条件命题中，若前提为假时，条件命题的 真值为真，称为善意的推断。前件假而整个句子为真的例子，在真值为真，称为善意的

13、推断。前件假而整个句子为真的例子，在 自然语言中也是常见的，如：自然语言中也是常见的，如：假如给我一根合适的杠杆，我可以假如给我一根合适的杠杆，我可以 把地球撬起来。把地球撬起来。 第第1章章 命题逻辑命题逻辑 2021-8-8 表表1 4 PQ真值表真值表 P QP Q 0 0 0 1 1 0 1 1 1 1 0 1 第第1章章 命题逻辑命题逻辑 2021-8-8 条件式条件式PQ表示的基本逻辑关系是：表示的基本逻辑关系是：Q是是P的必要的必要 条件或条件或P是是Q的充分条件。复合命题的充分条件。复合命题“只要只要P，就，就Q”、 “因为因为P，所以，所以Q”、“除非除非Q，才，才P”、“除

14、非除非Q，否则，否则 非非P”、“P仅当仅当Q”、“只有只有Q，才，才P”等均可符号化为等均可符号化为 PQ的形式。的形式。 例例6 (1)只要不下雨，我就骑自行车上班。只要不下雨，我就骑自行车上班。 (2)只有不下雨，我才骑自行车上班。只有不下雨，我才骑自行车上班。 解解 设设P：天下雨，：天下雨，Q：我骑自行车上班。则：我骑自行车上班。则(1)表示表示 为为 PQ；(2)表示为表示为QP。 第第1章章 命题逻辑命题逻辑 2021-8-8 5.等价联接词等价联接词 定义定义1.8 复合命题复合命题“P当且仅当当且仅当Q”称为称为P和和Q的等价式，记的等价式，记 作作PQ，读作，读作P当且仅当

15、当且仅当Q。PQ为真当且仅当为真当且仅当P与与Q的真值的真值 相同。相同。 例例7 (1)两个三角形全等当且仅当它们的三组对应边相等。两个三角形全等当且仅当它们的三组对应边相等。 (2)224当且仅当雪是黑的。当且仅当雪是黑的。 解解 (1)设设P：两个三角形全等，：两个三角形全等，Q：两个三角形的三组对：两个三角形的三组对 应边相等，则应边相等，则(1)表示为表示为PQ。 (2)设设P：224，Q：雪是黑的，则：雪是黑的，则(2)表示为表示为PQ。 第第1章章 命题逻辑命题逻辑 2021-8-8 P QP Q 0 0 0 1 1 0 1 1 1 0 0 1 表表1 5 PQ真值表真值表 第第

16、1章章 命题逻辑命题逻辑 2021-8-8 rprp3 rprq2 rqpqp1 :r 422:q :p ：求下列复合命题的真值求下列复合命题的真值 乌鸦是白色的乌鸦是白色的 北京比天津人口多北京比天津人口多令令例例 从而算得从而算得的真值分别为的真值分别为解：由已知解：由已知, 0 , 1 , 1,rqp . 11 的真值为的真值为 . 12 的真值为的真值为 . 03 的真值为的真值为 对个命题联结词的运算对个命题联结词的运算 优先次序优先次序规定为规定为 、 、 、 、 第第1章章 命题逻辑命题逻辑 2021-8-8 上节我们介绍了个命题联结词上节我们介绍了个命题联结词, 反复利用这些命

17、题联结词反复利用这些命题联结词 可以产生更复杂的命题。如符号串可以产生更复杂的命题。如符号串 p(qr) (pq)(rs) 1.2.1 命题公式命题公式 命题常元命题常元 ：简单命题、简单命题、 原子命题原子命题 命题变元命题变元： 是一个真值可以变化的陈述句是一个真值可以变化的陈述句。 说明：说明：当这些符号串中的字母都表示确定的命题时当这些符号串中的字母都表示确定的命题时, 上面上面 的符号串就表示更复杂的命题的符号串就表示更复杂的命题; 若这些字母不表示确定的命题若这些字母不表示确定的命题 时时, 上面的符号串就是我们下面所称的上面的符号串就是我们下面所称的命题公式命题公式。 但并不是但

18、并不是随随 意产生的符号串都能称为命题公式意产生的符号串都能称为命题公式, 必须遵循一定的规则。必须遵循一定的规则。 命题常元和命题变元都可以用命题常元和命题变元都可以用p,q,r,来表示。来表示。 1.2 命题公式与真值表命题公式与真值表 第第1章章 命题逻辑命题逻辑 2021-8-8 定义定义1.8 (1)(1)单个单个命题变元命题变元是命题公式。是命题公式。 (2)(2)如果如果A是命题公式，那么是命题公式，那么 A也是命题公式。也是命题公式。 (3)(3)如果如果A、B是命题公式，那么是命题公式，那么(AB)、(AB)、(AB)和和 (AB)是命题公式。是命题公式。 (4)(4)经过有

19、限次地使用经过有限次地使用(1)、(2)、(3)所组成的有意义的符号串所组成的有意义的符号串 都是命题公式。都是命题公式。 第第1章章 命题逻辑命题逻辑 2021-8-8 例例1 (PQ)，(P(PQ)，(PQ)(QR)(PR) 都是命题公式。而都是命题公式。而 PQ，(PQ)(Q)，(PQ都不是都不是 命题公式。命题公式。 为了减少命题公式中的括号数量，我们规定：为了减少命题公式中的括号数量，我们规定：联结词的联结词的 优先次序依次为：优先次序依次为： 、；规定具有相同优先规定具有相同优先 级的联结词，按出现的先后次序进行计算；级的联结词，按出现的先后次序进行计算；最外层的括号可最外层的括号

20、可 以省去。以省去。 定义定义1.10 设设B是命题公式是命题公式A的一部分，且的一部分，且B也是命题公式，也是命题公式， 则称则称B是是A的子公式。的子公式。 例如，例如，PQ和和QR都是都是(PQ)(QR)(PR)的子的子 公式。公式。 第第1章章 命题逻辑命题逻辑 2021-8-8 1.2.2真值表真值表 定义定义1. 9设设A是一个命题公式，是一个命题公式，p1、p2、pn为出现在为出现在A 中的所有命题变元。给中的所有命题变元。给p1、p2、pn指定一组真值，称为对指定一组真值，称为对 A的一个赋值。若指定的一组值使的一个赋值。若指定的一组值使A为真，称这组值为为真，称这组值为A的一

21、的一 个成真赋值，若使个成真赋值，若使A为假，称这组值为为假，称这组值为A的一个成假赋值。的一个成假赋值。 若若A有有n个不同的命题变元，则有个不同的命题变元，则有2n组不同的赋值。组不同的赋值。 定义定义1.10 设设A是含有是含有n个命题变元的命题公式，将命题公个命题变元的命题公式，将命题公 式式A在所有赋值之下取值的情况汇列成表，称为在所有赋值之下取值的情况汇列成表，称为A的真值表。的真值表。 第第1章章 命题逻辑命题逻辑 2021-8-8 为列出一个公式的真值表，我们约定：为列出一个公式的真值表，我们约定：命题变元按字典命题变元按字典 或序数排列；或序数排列；对公式的每个解释，以二进制

22、从小到大列出；对公式的每个解释，以二进制从小到大列出； 当公式较复杂时，可先列出子公式的真值，最后列出所给公当公式较复杂时，可先列出子公式的真值，最后列出所给公 式的真值。式的真值。 例例3 求下列命题公式的真值表，并求其成真赋值和成假赋求下列命题公式的真值表，并求其成真赋值和成假赋 值。值。 (1)(PQ)( PQ)。 (2) (PQ)Q。 (3)(PQ) R。 第第1章章 命题逻辑命题逻辑 2021-8-8 第第1章章 命题逻辑命题逻辑 2021-8-8 1.3 公式分类与等价式公式分类与等价式 1.3.1 公式分类公式分类 定义定义1.13 设设A是一个命题公式，对是一个命题公式，对A所

23、有可能的解释：所有可能的解释： (1)若若A都为真，称都为真，称A为永真式或重言式。为永真式或重言式。 (2)若若A都为假，称都为假，称A为永假式或矛盾式。为永假式或矛盾式。 (3)若至少存在一个解释使得若至少存在一个解释使得A为真，称为真，称A为可满足式。为可满足式。 公式类型的判定方法：真值表法、公式法和求主范式法。公式类型的判定方法：真值表法、公式法和求主范式法。 例例1 从上一节真值表可知，命题公式从上一节真值表可知，命题公式(PQ)( PQ)为为 重言式，重言式， (PQ)Q为矛盾式，为矛盾式，PQ) R为可满足式。为可满足式。 第第1章章 命题逻辑命题逻辑 2021-8-8 偶偶然

24、然式式非非永永真真式式的的可可满满足足式式 永永真真式式 可可满满足足式式 永永假假式式 命命题题公公式式 第第1章章 命题逻辑命题逻辑 2021-8-8 1.3.2 逻辑恒等式逻辑恒等式(等价式、等值式等价式、等值式) 定义定义1.14 设设A和和B是两个命题公式，如是两个命题公式，如A和和B在任意解释在任意解释 下，其真值相同，称下，其真值相同，称A与与B是等价的或逻辑相等，记作是等价的或逻辑相等，记作AB。 例例2 证明证明PQ(PQ)(QP)。 证明证明 命题公式命题公式PQ和和(PQ)(QP)的真值表如下表的真值表如下表 所示：所示： 由上表可知，由上表可知，PQ与与(PQ)(QP)

25、在任意解释下真值在任意解释下真值 相同，所以相同，所以PQ(PQ)(QP)。 第第1章章 命题逻辑命题逻辑 2021-8-8 定理定理1.1 对命题公式对命题公式A和和B，AB当且仅当当且仅当AB是重言式。是重言式。 证明证明 若若AB是重言式，则在任一解释下，是重言式，则在任一解释下，AB的真值都为的真值都为 真。依真。依AB的定义知，当的定义知，当AB为真时，为真时，A和和B有相同的真值。于有相同的真值。于 是，在任一解释下，是，在任一解释下，A和和B都有相同的真值，从而有都有相同的真值，从而有AB。 反过来，若反过来，若AB，则在任一解释下，则在任一解释下A和和B都有相同的真值，都有相同

26、的真值， 依依AB的定义知，此时的定义知，此时AB为真，从而为真，从而AB是重言式。是重言式。 第第1章章 命题逻辑命题逻辑 2021-8-8 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，AAA (6)吸收律吸收律 A(AB)A，A(AB)A (7)德德摩根律摩根律 (AB)A B， (AB)A B 第第1章章

27、 命题逻辑命题逻辑 2021-8-8 (8)同一律同一律 A0A，A1A (9)零律零律 A11，A00 (10)互补律互补律 A A1，A A0 (11)蕴涵等价式蕴涵等价式 (AB)AB (12)等价表达式等价表达式 (AB)(AB)(BA)(AB)( A B) (13)逆反律逆反律 (AB)BA (14)归谬律归谬律 (AB)(AB)A (15)输出律输出律 (AB)CA(BC) 第第1章章 命题逻辑命题逻辑 2021-8-8 表表 1.2 - 1 逻逻 辑辑 恒恒 等等 式式 1.3.4 代入规则和替换规则代入规则和替换规则 定理定理1.2(代入规则代入规则)在一个永真式在一个永真式A

28、中，任何一个原子命题中，任何一个原子命题 变元变元R出现的每一处用另一个公式代入，所得公式出现的每一处用另一个公式代入，所得公式B仍为永真式。仍为永真式。 证明证明 因为永真式对任何解释，其真值都是真，与每个命因为永真式对任何解释，其真值都是真，与每个命 题变元指派的真假无关，所以，用一个命题公式代入到原子命题变元指派的真假无关，所以，用一个命题公式代入到原子命 题变元出现的每一处，所得命题公式的真值仍为真。题变元出现的每一处，所得命题公式的真值仍为真。 例例3 证明证明(PQ) (PQ)为永真式。为永真式。互补律互补律 证明证明 因为因为R R为永真式，由代入规则可知，将为永真式，由代入规则

29、可知，将R用用 (PQ)代入得到的式子仍为永真式，所以代入得到的式子仍为永真式，所以(PQ) (PQ)为为 永真式。永真式。 第第1章章 命题逻辑命题逻辑 2021-8-8 定理定理1.3 (替换规则替换规则)设设A1是公式是公式A的子公式，若的子公式，若 A1B1，并且将，并且将A中的中的A1用用B1替换，得到公式替换，得到公式B，则，则 AB。 证明证明 因为因为A1 B1 ，即对于它们的命题变元的任意，即对于它们的命题变元的任意 一组赋值，一组赋值， A1与与B1的真值相同。所以，将的真值相同。所以，将A中的中的A1用用B1 替换后，替换后，A与与B在对其命题变元的任意赋值下，它们的真在

30、对其命题变元的任意赋值下，它们的真 值也相同，故值也相同，故AB。 第第1章章 命题逻辑命题逻辑 2021-8-8 1.3.5证明命题公式等价证明命题公式等价(等值等值)的方法的方法 通常有通常有真值表法、公式法真值表法、公式法和求主范式法。和求主范式法。 例例4 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)( P Q) (P Q)(Q P) ( PQ)( QP) (PQ)(QP)(PQ) 第第1章章 命题逻辑命题逻辑 2021-8-8 例例5

31、 某件事是甲、乙、丙、丁某件事是甲、乙、丙、丁4人中某一个人干的，询人中某一个人干的，询 问问4人后回答如下：人后回答如下：(1)甲说是丙干的；甲说是丙干的；(2)乙说我没干；乙说我没干；(3) 丙说甲讲的不符合事实；丙说甲讲的不符合事实；(4)丁说是甲干的。若其中丁说是甲干的。若其中3人说人说 的是对的、的是对的、1人说的不对，问是谁干的？人说的不对，问是谁干的？ 解解 设设A：这件事是甲干的，：这件事是甲干的，B：这件事是乙干的，：这件事是乙干的，C： 这件事是丙干的，这件事是丙干的，D：这件事是丁干的。：这件事是丁干的。 4人所说命题分别用人所说命题分别用Q、R、S、M表示，则表示，则(

32、1)、(2)、 (3)、(4)分别符号化为：分别符号化为： QA BC D； RB；SC； MA B C D 第第1章章 命题逻辑命题逻辑 2021-8-8 3人对、人对、1人错的命题人错的命题P符号化为：符号化为： P( QRSM)(Q RSM) (QR SM)(QRS M) 而而( QRSM)A B C D，其它三项，其它三项0，所，所 以以P为真时，为真时，A B C D为真，所以这件事是甲干的。为真，所以这件事是甲干的。 第第1章章 命题逻辑命题逻辑 2021-8-8 例例6 A、B、C、D四人进行百米竞赛，观众甲、乙、丙预四人进行百米竞赛，观众甲、乙、丙预 报比赛的名次为甲：报比赛的

33、名次为甲：C第一、第一、B第二；乙：第二；乙：C第二、第二、D第三；丙：第三；丙： A第二、第二、D第四。比赛结束后发现甲、乙、丙每人报告的情况第四。比赛结束后发现甲、乙、丙每人报告的情况 都是各对一半，试问实际名次如何都是各对一半，试问实际名次如何(假如无并列者假如无并列者)？ 解解 设设Ai表示表示A第第i名，名，Bi表示表示B第第i名，名，Ci表示表示C第第i名，名，Di表表 示示D第第i名，则依据题意有：名，则依据题意有： (C1 B2)( C1B2)T (1) (C2 D3)( C2D3)T (2) (A2 D4)( A2D4)T (3) 第第1章章 命题逻辑命题逻辑 2021-8-

34、8 因为真命题的合取仍为真命题，所以因为真命题的合取仍为真命题，所以 (1)(2)(C1 B2C2 D3)(C1 B2 C2D3) ( C1B2C2 D3)( C1B2 C2D3) (C1 B2 C2D3)( C1B2 C2D3)T (4) (3)(4)(A2 D4C1 B2 C2D3) ( A2D4C1 B2 C2D3) (A2 D4C1 B2 C2D3) ( A2D4 C1B2 C2D3) A2 D4C1 B2 C2D3T 所以，所以，A第二、第二、B第四、第四、C第一、第一、D第三。第三。 第第1章章 命题逻辑命题逻辑 2021-8-8 1.4对偶式与蕴涵式对偶式与蕴涵式 1.4.1对偶

35、式对偶式 定义定义1.15 在给定的仅使用联结词在给定的仅使用联结词 、和和的命题公式的命题公式A中，中， 若把若把1和和0互换、互换、和和互换得到一个命题公式互换得到一个命题公式A*，则称，则称A*是是A 的对偶式，或说的对偶式，或说A和和A*互为对偶式。互为对偶式。 例例1 (PQ)R的对偶式为的对偶式为(PQ)R，P0的对偶式为的对偶式为 P1。 定理定理1.4 设设A和和A*互为对偶式，互为对偶式，P1、Pn是出现在是出现在A和和A* 中的所有原子命题变元，则：中的所有原子命题变元，则： (1) A(P1，Pn)A*( P1， Pn)。 (2)A( P1， Pn)A*(P1，Pn)。

36、第第1章章 命题逻辑命题逻辑 2021-8-8 证明证明 由德由德摩根律得：摩根律得：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中的所有原子命题变元。中的所有原子命题变元。 若若AB，即，即A(P1，Pn)B(P1，Pn)，则，则 A(P1，Pn)B(P1，Pn) 由定理由定理1.4得得A*( P1， Pn)B*( P1， Pn)，再由代，再由代 入规则得入规则得A*(P1，Pn)B*(P1，

37、Pn)。 第第1章章 命题逻辑命题逻辑 2021-8-8 例例2 设设A(P，Q，R) P( QR)，证明，证明A*( P， Q， R)P(Q R)。 证明证明 A*( P， Q， R) A(P，Q，R) ( P( QR) P(Q R) 第第1章章 命题逻辑命题逻辑 2021-8-8 1.4.2蕴涵式蕴涵式 定义定义1.16 设设A和和B为命题公式，若为命题公式，若AB是永真式，则称是永真式，则称A 蕴含蕴含B，记作，记作AB，称，称AB为永真蕴含式或永真条件式。为永真蕴含式或永真条件式。 定理定理1.6 AB的充要条件是的充要条件是AB且且BA 证明证明 若若AB，则，则AB为永真式，而为永

38、真式，而 AB(AB)(BA)，故，故AB和和BA皆为真，即皆为真，即AB且且 BA。 反之，若反之，若AB且且BA，则，则AB和和BA为永真式，于是为永真式，于是 (AB)(BA)永真，即永真，即AB永真式，所以永真式，所以AB成立。成立。 第第1章章 命题逻辑命题逻辑 2021-8-8 下面给出常用的下面给出常用的14组永真蕴涵式，它们的正确性可用后组永真蕴涵式，它们的正确性可用后 面介绍的真值表法、分析法和公式法来证明。面介绍的真值表法、分析法和公式法来证明。 (1)化简式化简式 PQP，PQQ (2)附加式附加式 PPQ (3)附加式变形附加式变形 PPQ (4)附加式变形附加式变形

39、QPQ (5)化简式变形化简式变形 (PQ)P (6)化简式变形化简式变形 (PQ)Q (7)假言推理假言推理 P(PQ)Q (8)拒取式拒取式 Q(PQ)P 第第1章章 命题逻辑命题逻辑 2021-8-8 (9)析取三段论析取三段论 P(PQ)Q (10)条件条件(前提前提)三段论三段论 (PQ)(QR)PR (11)双条件三段论双条件三段论 (PQ)(QR)PR (12)合取构造二难合取构造二难 (PQ)(RS)(PR)QS (13)析取构造二难析取构造二难 (PQ)(RS)(PR)QS (14)前件附加前件附加 PQ(PR)(QR) PQ(PR)(QR)(例例1-30,1-31) 除了上

40、述蕴含式外，等价式也可作为永真蕴含式，即若除了上述蕴含式外，等价式也可作为永真蕴含式，即若 有有AB，则有，则有AB和和BA。 第第1章章 命题逻辑命题逻辑 2021-8-8 1.4.3蕴涵式的证明方法蕴涵式的证明方法 1.真值表法真值表法 例例3 Q(PQ)P(拒取式拒取式) 证明证明 命题公式的真值表如下表所示：命题公式的真值表如下表所示： 由上表可知，当由上表可知，当( Q(PQ)为真时，为真时， P为真，所以为真，所以 Q(PQ)P。 第第1章章 命题逻辑命题逻辑 2021-8-8 2.分析法分析法 形式形式1：若若A为真推出后件为真推出后件B也真，则也真，则AB。形式。形式2：若：若

41、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)(QR)R。 第第1章章 命题逻

42、辑命题逻辑 2021-8-8 3.定义法定义法 例例5 证明证明P(PQ)Q 证明证明 因为因为(P(PQ)Q (P( PQ)Q (P P)(PQ)Q (PQ)Q (PQ)Q ( P Q)Q P( QQ) P1 1 所以所以P(PQ)Q。 第第1章章 命题逻辑命题逻辑 2021-8-8 证(PQ)(QR)(RS) (P Q)(Q R)(RS) PS 证明 (PQ)(QR)(RS) PS 4.公式法公式法 第第1章章 命题逻辑命题逻辑 2021-8-8 1.4.1简单合取式与简单析取式简单合取式与简单析取式 定义定义1.14 在一公式中，仅由命题变元及否定构成的合取式在一公式中，仅由命题变元及否

43、定构成的合取式 称为简单合取式；仅由命题变元及否定构成的析取式称为简单称为简单合取式；仅由命题变元及否定构成的析取式称为简单 析取式。析取式。 例如，例如，P、 P、 PQ、P Q P都是简单合取式，而都是简单合取式，而P、 P、PQ都是简单析取式。都是简单析取式。 定理定理1.7 简单合取式为永假式当且仅当它同时含有某个命题简单合取式为永假式当且仅当它同时含有某个命题 变元及其否定。变元及其否定。 1.4 命题范式命题范式 第第1章章 命题逻辑命题逻辑 2021-8-8 证明证明 设设A为简单合取式，其包含的所有命题变元为为简单合取式，其包含的所有命题变元为p1、 p2、pn。 若若A为永假

44、式，但不同时含有某个命题变元及其否定，则为永假式，但不同时含有某个命题变元及其否定，则 不妨设不妨设Ap1p2pi pi 1 pn，于是当，于是当p1、 p2、pi的真值都是真，而的真值都是真，而pi 1、 、pn的真值都是假时，的真值都是假时，A 的真值为真，与的真值为真，与A为永假式矛盾。为永假式矛盾。 反之，若反之，若A同时含有某个命题变元及其否定，显然有同时含有某个命题变元及其否定，显然有A为永为永 假式。假式。 定理定理1.8 简单析取式为永真式当且仅当它同时含有某个命简单析取式为永真式当且仅当它同时含有某个命 题变元及其否定。题变元及其否定。 第第1章章 命题逻辑命题逻辑 2021

45、-8-8 1.4.2 析取范式与合取范式析取范式与合取范式 定义定义1.15 若干个简单合取式的析取称为析取范式；若干若干个简单合取式的析取称为析取范式；若干 个简单析取式的合取称为合取范式。个简单析取式的合取称为合取范式。 定义定义1.21 与公式与公式A等价的析取范式称为公式等价的析取范式称为公式A的析取范的析取范 式，与公式式，与公式A等价的合取范式称为公式等价的合取范式称为公式A的合取范式。的合取范式。 定理定理1.4 对任意命题公式，都存在与其等价的析取范式对任意命题公式，都存在与其等价的析取范式 和合取范式。和合取范式。 第第1章章 命题逻辑命题逻辑 2021-8-8 下面给出求公

46、式的范式的步骤：下面给出求公式的范式的步骤： (1)使用基本等价式消去除使用基本等价式消去除 、以外公式中出现的以外公式中出现的 所有联结词；所有联结词； (2)消去消去； (3)使使 出现在命题变元之前；出现在命题变元之前； (4)用结合律、分配律等将公式化为所需范式。用结合律、分配律等将公式化为所需范式。 第第1章章 命题逻辑命题逻辑 2021-8-8 例例1 求求 (PQ)(PQ)的析取范式。的析取范式。 解解 (PQ)(PQ) ( (PQ)(PQ)(PQ) (PQ) ( P QPQ)(PQ)( P Q) ( P QPQ)(P P) (P Q)(Q P)(Q Q) (P Q)( PQ)

47、第第1章章 命题逻辑命题逻辑 2021-8-8 例例2 求求 (PQ)(PQ)的合取范式。的合取范式。 解解 (PQ)(PQ) (PQ)(PQ)( (PQ) (PQ) (PQ)(PQ)( P Q)( P Q) (PQP)(PQQ)( P P Q) ( Q P Q) (PQ)( P Q) 第第1章章 命题逻辑命题逻辑 2021-8-8 1.4*公式主范式公式主范式 1.4*.1主析取范式主析取范式 1.极小项的概念及性质极小项的概念及性质 定义定义1.16 在含有在含有n个命题变元的简单合取式中，若每个命个命题变元的简单合取式中，若每个命 题变元与其否定不同时存在，而两者之一出现一次且仅出现一题

48、变元与其否定不同时存在，而两者之一出现一次且仅出现一 次，称该简单合取式为极小项。次，称该简单合取式为极小项。 例如，例如，2个命题变元个命题变元P和和Q产生产生4个小项：个小项： P Q、 PQ、 P Q、PQ。3个命题变元个命题变元P、Q和和R产生产生8个小项：个小项： P Q R、 P QR、 PQ R、 PQR、 P Q R、P QR、PQ R、PQR。 第第1章章 命题逻辑命题逻辑 2021-8-8 表表2.4 p,q,r2.4 p,q,r形成的极小项与极大项形成的极小项与极大项 极极大大项项极极小小项项 77 66 55 44 33 22 11 00 111111 110110 1

49、01101 100100 011011 010010 001001 000000 Mrqpmrqp Mrqpmrqp Mrqpmrqp Mrqpmrqp Mrqpmrqp Mrqpmrqp Mrqpmrqp Mrqpmrqp 名称名称成假赋值成假赋值公式公式名称名称成真赋值成真赋值公式公式 第第1章章 命题逻辑命题逻辑 2021-8-8 n个命题变元共形成个命题变元共形成2n个极小项。个极小项。 极小项的二进制编码：约定命题变元按字典顺序排列，命极小项的二进制编码：约定命题变元按字典顺序排列，命 题变元与题变元与1对应，命题变元的否定与对应，命题变元的否定与0对应，则得到极小项的二对应，则得到

50、极小项的二 进制编码，记为进制编码，记为mi，其下标，其下标i是由二进制转化的十进制数。是由二进制转化的十进制数。n个个 命题变元形成的命题变元形成的2n个小项，分别记为：个小项，分别记为：m0，m1， ， 。 两个命题变元两个命题变元P和和Q的极小项真值表如下表所示：的极小项真值表如下表所示： 1 n 2 m 第第1章章 命题逻辑命题逻辑 2021-8-8 由真值表可得极小项具有如下的性质：由真值表可得极小项具有如下的性质： (1)各极小项的真值表都是不同的。各极小项的真值表都是不同的。 (2)每个极小项只有当赋值与其对应的二进制编码相同时，每个极小项只有当赋值与其对应的二进制编码相同时，

51、其真值为真，且其真值其真值为真，且其真值1位于主对角线上。位于主对角线上。 (3)任两不同极小项的合取式是永假式。任两不同极小项的合取式是永假式。 (4)所有极小项的析取式为永真式。所有极小项的析取式为永真式。 2.主析取范式定义与存在定理主析取范式定义与存在定理 定义定义1.17 由若干个不同的极小项组成的析取式称为主析由若干个不同的极小项组成的析取式称为主析 取范式；与取范式；与A等价的主析取范式称为等价的主析取范式称为A的主析取范式。的主析取范式。 定理定理1.5 任意含任意含n个命题变元的命题公式个命题变元的命题公式A都存在与其等都存在与其等 价的主析取范式，并且是惟一的。价的主析取范

52、式，并且是惟一的。 第第1章章 命题逻辑命题逻辑 2021-8-8 证明证明 设设A 是是A的析取范式，即的析取范式，即AA 。若。若A 的某个简单合的某个简单合 取式取式Ai中不含命题变元中不含命题变元P及其否定及其否定 P，将，将Ai展成形式展成形式 AiAiTAi(P P)(AiP)(Ai P)，继续这个过程，继续这个过程， 直到所有的简单合取式成为极小项。然后，消去重复的项及矛直到所有的简单合取式成为极小项。然后，消去重复的项及矛 盾式之后，得到盾式之后，得到A的主析取范式。的主析取范式。 下面证明其惟一性。下面证明其惟一性。 若若A有两个与之等价的主析取范式有两个与之等价的主析取范式

53、B和和C，则，则BC。由。由B和和 C是是A的不同的主析取范式，不妨设极小项的不同的主析取范式，不妨设极小项mi只出现在只出现在B中而不中而不 在在C中，于是中，于是i的二进制为的二进制为B的成真赋值，的成真赋值，C的成假赋值，与的成假赋值，与 BC矛盾。因而矛盾。因而A的主析取范式是惟一的。的主析取范式是惟一的。 第第1章章 命题逻辑命题逻辑 2021-8-8 3.求主析取范式的方法求主析取范式的方法 1)真值表法真值表法 定理定理1.13 在真值表中，命题公式在真值表中，命题公式A的真值为的真值为1的赋值所对应的的赋值所对应的 极小项的析取即为此公式极小项的析取即为此公式A的主析取范式。的

54、主析取范式。 证明证明 设设A真值为真值为T的赋值所对应的极小项为的赋值所对应的极小项为m1、mk，令，令 Bm1m2mk。下证。下证AB。 若若A为真，则其赋值所对应的极小项一定是为真，则其赋值所对应的极小项一定是m1、mk中的中的 某一项，不妨设为某一项，不妨设为mi，因为，因为mi为真，而为真，而m1、mi 1、 、mi 1、 、 mk都为假，故都为假，故B也为真。也为真。 若若A为假，则其赋值所对应的小项一定不是为假，则其赋值所对应的小项一定不是m1、mk中的中的 某一项，此时某一项，此时m1、m2、mk都为假，故都为假，故B也为真。也为真。 因此，因此，AB。 第第1章章 命题逻辑命

55、题逻辑 2021-8-8 例例1 用真值表法求用真值表法求 (PQ)(PQ)的主析取范式。的主析取范式。 解解 (PQ)(PQ)的真值表如下表所示：的真值表如下表所示： 从上表知，该公式仅在其真值表的从上表知，该公式仅在其真值表的00行和行和10行处取真值行处取真值1，所，所 以以 (PQ)(PQ)m0m2。 第第1章章 命题逻辑命题逻辑 2021-8-8 例例2 用真值表法求用真值表法求(PQ)R的主析取范式。的主析取范式。 解解 (PQ)R的真值表如下表所示：的真值表如下表所示： 从上表知，该公式仅在其真值表的从上表知，该公式仅在其真值表的001、011、101、110、 111处取真值处

56、取真值1，所以，所以(PQ)Rm1m3m5m6m7。 第第1章章 命题逻辑命题逻辑 2021-8-8 2)公式法公式法 求主析取范式的步骤如下：求主析取范式的步骤如下： (1)求求A的析取范式的析取范式A ； (2)若若A 的某简单合取式的某简单合取式B中不含某个命题变元中不含某个命题变元P或其否定或其否定 P，则将，则将B展成形式展成形式 BB1B(P P)(BP)(B P) (3)将重复出现的命题变元、矛盾式及重复出现的极小项都将重复出现的命题变元、矛盾式及重复出现的极小项都 消去；消去； (4)将极小项按顺序排列。将极小项按顺序排列。 第第1章章 命题逻辑命题逻辑 2021-8-8 例例

57、3 用公式法求用公式法求(PQ)Q的主析取范式。的主析取范式。 解解 (PQ)Q ( PQ)Q ( PQ)Q ( PQ)(P P)Q) ( PQ)(PQ)( PQ) ( PQ)(PQ) m1m3。 第第1章章 命题逻辑命题逻辑 2021-8-8 例例4 用公式法求用公式法求(PQ)R)P的主析取范式。的主析取范式。 解解 (PQ)R)P ( (PQ)R)P(PQ) R)P (P R)(Q R)P(Q R)P (P P)Q R)(P(Q Q) (PQ R)( PQ R)(PQ)(P Q) (PQ R)( PQ R)(PQ(R R) (P Q(R R) (PQ R)( PQ R)(PQR) (PQ

58、 R)(P QR)(P Q R) (PQ R)( PQ R)(PQR) (P QR)(P Q R) m2m4m5m6m7。 第第1章章 命题逻辑命题逻辑 2021-8-8 1.7.2主合取范式主合取范式 1.极大项的概念及性质极大项的概念及性质 定义定义1.16在含有在含有n个命题变元的简单析取式中，若每个命个命题变元的简单析取式中，若每个命 题变元与其否定不同时存在，而两者之一出现一次且仅出现题变元与其否定不同时存在，而两者之一出现一次且仅出现 一次，称该简单析取式为极大项。一次，称该简单析取式为极大项。 极大项的二进制编码：约定命题变元按字典顺序排列，极大项的二进制编码：约定命题变元按字典

59、顺序排列， 命题变元与命题变元与0对应，命题变元的否定与对应，命题变元的否定与1对应，则得到极大项对应，则得到极大项 的二进制编码，记为的二进制编码，记为Mi，其下标，其下标i是由二进制转化的十进制。是由二进制转化的十进制。n 个命题变元形成的个命题变元形成的2n个极大项，分别记为：个极大项，分别记为：M0，M1，。，。 第第1章章 命题逻辑命题逻辑 2021-8-8 两个命题变元两个命题变元P和和Q的极大项真值表如下表所示：的极大项真值表如下表所示： 由真值表可得大项具有如下的性质：由真值表可得大项具有如下的性质： (1)各极大项的真值表都是不同的；各极大项的真值表都是不同的； (2)每个极

60、大项只有当赋值与其对应的二进制编码相同时，每个极大项只有当赋值与其对应的二进制编码相同时， 其真值为假，且其真值其真值为假，且其真值0位于主对角线上；位于主对角线上； (3)任两不同极大项的析取式是永真式；任两不同极大项的析取式是永真式； (4)所有极大项的合取式为永假式。所有极大项的合取式为永假式。 第第1章章 命题逻辑命题逻辑 2021-8-8 2.主合取范式定义与存在定理主合取范式定义与存在定理 定义定义1.17 由若干个不同的极大项组成的合取式称为主合取由若干个不同的极大项组成的合取式称为主合取 范式；与范式；与A等价的主合取范式称为等价的主合取范式称为A的主合取范式。的主合取范式。