离散数学第1章命题公式与翻译 真值表与等价公式

1、Discrete Mathematics山东科技大学山东科技大学信息科学与工程学院信息科学与工程学院课程回顾课程回顾 命题：命题的定义、真值、分类及其表示。命题联结词： 否定、合取、析取、条件、双条件。PQPPQPQPQP QTT FTT TTTF FFT FFFT TFT TFFF TFF TT练习v判断是否命题？黄岛是个大城市。我们要努力学习。练习v只有具有确定真值的陈述句才是命题。只有具有确定真值的陈述句才是命题。v黄岛是个大城市。是命题，其真值为假。v 我们要努力学习。 祈使句，不是命题。 第一章 命题逻辑 第2讲 13 命题公式与翻译 14真值表与等价公式 要求：理解合式公式及两个合

2、式公式等价的定义，熟悉命题定律，会证明等价公式。重点：合式公式的定义，两个合式公式等价的定义，10个命题定律。难点：推证等价公式。13 命题公式与翻译命题公式与翻译一、合式公式 前面已经提到，不包含任何联结词的命题叫做原子命题，至少包含一个联结词的命题称作复合命题。 设P和Q是任意两个命题，则P， PQ，(PQ）(FQ），P (Q P)等都是复合命题。 若P和Q是命题变元，则上述各式均称作命题公式。P和Q称作命题公式的分量。说明：命题公式没有真值，仅当其中命题变元用确定的命题代入时，才得到一个命题。这个命题的真值，依赖于代换变元的那些命题的真值。并不是由命题变元，联结词和一些括号组成的字符串都

3、能成为命题公式。定义1-3.1 命题演算的合式公式(wff)，规定为： (1)单个命题变元本身是一个合式公式。 (2)如果A是合式公式，那么A是合式公式。 (3)如果A和B是合式公式，那么(AB)，(AB)， (AB）和(A B)都是合式公式。 (4)当且仅当能够有限次地应用(1)、(2)、(3)所得到 的包含命题变元，联结词和括号的符号串是合式公式。v 这个合式公式的定义，是以递归形式给出的，其中(1)称为基础，(2)(3)称为归纳，(4)称为界限。按照定义，下列公式都是合式公式： (PQ），(PQ)，(P(PQ)， (PQ）(QR) （S T) 而 (PQ）(Q)，(PQ，(PQ）Q）等都

4、不是合式公式。v目的：减少使用括号的数量目的：减少使用括号的数量v约定：命题公式外层的括号可以省略；约定：命题公式外层的括号可以省略；、。v范例：范例： PQRv等价于等价于 ： （PQ）R ）v等价于等价于 ： （PQ）Rv不等价于不等价于 ： P（QR）命题的翻译 v有了联结词的合式公式概念，我们可以把自然语言中的有些语句，翻译成数理逻辑中的符号形式。v把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，称为命题的符号化。v符号化应该注意下列事项： 确定给定句子是否为命题。 句子中联结词是否为命题联结词。 要正确地表示原子命题和适当选择命题联结词。(1)找出原子命题

5、(2)用大写字母代替命题(3)按题意用联结词自然语言的语句用自然语言的语句用形式化形式化主要注意以下几个方面：主要注意以下几个方面： 要准确确定原子命题，并将其形式化。要准确确定原子命题，并将其形式化。 要选用恰当的联结词，尤其要善于识别自然语要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要言中的联结词（有时它们被省略），否定词的位置要放准确。放准确。 必要必要时可以进行改述，即改变原来的叙述方式，时可以进行改述，即改变原来的叙述方式，但要保证表达意思一致但要保证表达意思一致。 需要的括号不能省略，而可以省略的括号，需要的括号不能省略，而可以省略的括号，在

6、需要提高公式可读性时亦可不省略。在需要提高公式可读性时亦可不省略。 要注意语句的形式化未必是唯一的。要注意语句的形式化未必是唯一的。 自然语言的语句用自然语言的语句用 形式化形式化解 若设 P：他聪明。 Q：他用功。 在自然语言中这个“既又”显然与“且”的意义一样，故本例可记为： PQ 。例题3 他既聪明又用功。例题解 这里“虽但”这个词不能用前述联结词表达，但其实际意义是：他聪明且不用功。若设 P：他聪明。 Q：他用功。 本例可表示为： PQ例题4 他虽聪明但不用功。从表中可看出原命题不能用前述五个联结词单独写出，但是如用命题和联结词组合，可以把本命题表达为：(P Q）。 解 P：上海到北京

7、的14次列车是下午五点半开。 Q：上海到北京的14次列车是下午六点开。 在本例中，汉语的“或”是不可兼或，而逻辑联结词是“可兼或”，因此不能直接对两命题析取。构造表如表1-3.1所示。PQ原命题P Q (P Q)TT F T FTF T F TFT T F TFF F T F表1-3.1例题2 上海到北京的14次列车是下午五点半或六点开。例题 解 这个命题的意义，亦可理解为：如果你不努力则你将失败。 若设 P：你努力。 Q：你失败。 本例可表示为： PQ例题5 除非你努力，否则你将失败。 解 这个命题的意义是： 张三可以做这件事，并且李四也可以做这件事。 若设P：张三可以做这事。 Q：李四可以

8、做这事。 本例可表示为： PQ例题6 张三或李四都可以做这件事。例题v解 找出各原子命题，并用命题符号表示： A：我们要做到身体好。 B：我们要做到学习好。 C：我们要做到工作好。 P：我们要为祖国四化建设而奋斗。 v 例题1 试以符号形式写出命题：我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。v故命题可形式化为：（A B C） P思考vA：我们要做到身体好。vA：我们要努力学习。 祈使句，不是命题。v 从上面的例子中可以看到，自然语言中的一些联结词，如：“与”“且”“或”“除非则”等等都各有其具体含义，因此需分别不同情况，根据实际含义，翻译成适当的逻辑联结词。v为了便于正确表达命题

9、间的相互关系，有时也常常采用列出“真值表”的方法，进一步分析各原命题，以此寻找逻辑联结词，使原来的命题能够正确地用形式符号予以表达。 小结 学习本节要深刻理解命题公式的定义，能够把用自然语言中的有些语句，翻译成数理逻辑中的符号形式。 合式公式：命题演算的合式公式(wff) 规定为： (1)单个命题变元本身是一个合式公式。 (2)如果A是合式公式，那么A是合式公式。 (3)如果A和B是合式公式，那么(AB)，(AB)，(AB）和(A B)都是合式公式。 (4)当且仅当能够有限次地应用(1)、(2)、(3)所得到的包含命题变元，联结词和括号的符号串是合式公式。 翻译 把自然语言中的有些语句，翻译成

10、数理逻辑中的符号形式。 优先次序 规定联结词运算的优先次序为：、14 真值表与等价公式真值表与等价公式 1.真值表 定义1-4.1 在命题公式中，对于分量（命题变元）指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。P Q P PQTTFTTFFF FTTTFFTT举例：构造PQ的真值表。解（见表 1-4.1 ）表 1-4.1例题例题2 给出给出(PQ）P的真值表。的真值表。解解 （见表（见表1-4.2） P Q PQP(PQ）PTTTFFTFFFFFTFTFFFFTF例题3 给出(PQ）（PQ）的真值表。解 PQPQPQPQ（PQ） （PQ）TT

11、 F F T F TTF F T F F FFT T F F F FFF T T F T T表1-4.3例题例题4 给出给出(PQ） （PQ）的真值表。）的真值表。解解PQPQ(PQ)PQPQ(PQ） （PQ）TT T F F F F TTF F T F T T TFT F T T F T TFF F T T T T T表表 1-4.4v 由表1-4.4 (表1-4.2)可以看出，有一类公式不论命题变元作何种指派，其真值永为真(假)，我们把这类公式记为T(F)。注意回顾PQPQ(PQ)PQPQ(PQ） （PQ）TT T F F F F TTF F T F T T TFT F T T F T T

12、FF F T T T T T表1-4.4回顾v 表 1-4.2v PQ PQP(PQ）PTT T F FTF F F FFT F T FFF F T Fv 重言式和矛盾式重言式和矛盾式这两类特殊的命题公式在今后的命题演算中极为有用。v 定义定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命题公式为重言式重言式或永真公式永真公式。定义定义1-5.2 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式矛盾式或永假公式永假公式。v 由表1-4.4 (表1-4.2)可以看出，有一类公式不论命题变元作何种指派，其真值永为真(假)，我们

13、把这类公式记为T(F)。v 在真值表中，命题公式真值的取值数目，决定于分量（命题变元）的个数。例如，由2个命题变元组成的命题公式共有四种可能的真值，由3个命题变元组成的命题公式共有八种真值。一般说来，n个命题变元组成的命题公式共有2n种真值情况。注意 从真值表中可以看到，有些命题公式在分量的不同指派下，其对应的真值与另一命题公式完全相同，如PQ与PQ的对应真值相同，如表1-4.5所示。 PQPQPQTT T TTF F FFT T TFF T T表1-4.5我们说我们说PQ和和PQ是等价的，是等价的，这在以后的推理中这在以后的推理中特别有用。特别有用。 同理(PQ)(PQ)与P Q对应的真值相

14、同，如表1-4.6所示。 表1-4.6 P Q P Q (PQ)(PQ)TT T TTF F FFT F FFF T T二、等价公式 1.定义 定义1-4.2 给定两个命题公式A和B，设P1，P2，Pn为所有出现于A和B中的原子变元，若给P1，P2，Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等。记作A B。v在这里，请注意和的区别与联系：v区别：是逻辑联结词，它出现在命题公式中； 不是逻辑联结词，它表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号。v2、等价公式的证明方法： 真值表法 由表1-4.7可知P Q与(PQ) (QP）真值相同，命题得证。例题

15、5 证明 P Q (PQ) (QP)证明 列出其值表 表 1-4.7PQP QQPP Q (PQ) (QP）TT T T T TTF F T F FFT T F F FFF T T T Tv2、等价公式的证明方法：（1）值表法（2）推导的证明方法命题定律推导的证明方法命题定律（表1-4.8列出的命题定律都可以用真值表予以验证） 表1-4.8对合律P P1幂等律PP P，PP P2结合律(PQ）R P（QR）(PQ）R P（QR）3交换律PQ QPPQ QP4分配律P（QR） （PQ）（PR）P（QR） （PQ）（PR）5吸收律P（PQ） PP（PQ） P6德摩根律(PQ) PQ(PQ) PQ7

16、同一律PF P，PT P8零律PT T，PF F9否定律PP T，PP F10PQ PQ例题6 验证吸收律 P（PQ） P P（PQ） P证明 列出真值表 表1-4.9PQPQ P（PQ）PQP（PQ）TT T T T TTF F T T TFT F F T FFF F F F F 由表1-4.9可知吸收律成立。v2、等价公式的证明方法：（1）值表法（2）推导的证明方法命题定律等价置换等价置换 在一个命题公式中，如果用公式置换命题的某个部分，一般地将会产生某种新的公式，新公式不一定与原公式等价，例如Q(P(PQ)中以(PQ)取代(PQ)，则Q(P(PQ) )就与原式不同。PQP(PQ)Q(P(

17、PQ)PQP(PQ)Q(P(PQ) )TT T T T T TTF T T T T TFT F F T T TFF F T F F T等价置换为了保证置换后的公式与原始公式是等价的，需对置换作出一些规定。 v等价置换v定义1-4.3 如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的子公式子公式。v证明 因为在相应变元的任一种指派情况下，X与Y的真值相同，故以Y取代X后，公式B与公式A在相应的指派情况下，其真值亦必相同，故A B。 口 v满足定理1-4.1条件的置换称为等价置换(等价代换)。v证明命题公式A和B等价的方法：将命题公式A的子公式不断做等价替换后得到新命题公式B

18、，则命题公式A和B等价v定理定理1-4.1 设设X是合式公式是合式公式A的子公式，若的子公式，若X Y，如果将如果将A中的中的X用用Y来置换，所得到公式来置换，所得到公式B与公式与公式A等价，即等价，即A B。 例题7 证明Q(P(PQ) QP PQPQP（PQ）QP（PQ）QPTT T T T TTF F T T TFT F F F FFF F F T T有了最基本的的命题公式的等价关系，再利用定理1-4.1，就可以推证一些更为复杂的命题等价公式。证明 设A：Q(P(PQ)， B：QP 因为 P(PQ) P 故 A B 对A B亦可用表1-4.10予以验证： 表 1-4.10吸收律 例题8 证明(PQ) (PQ) P (PQ) (PQ) (PQ)P) ( (PQ ) Q)