离散数学讲义第二章命题逻辑.ppt

1、第二章命题逻辑数理逻辑是用数学方法研究思维规律的学科。所谓数学方法是指：使用一套数学符号系统来描述和处理思维的形式和规律。因此，数理逻辑也被称为符号逻辑。本章介绍了数理逻辑最基本的内容命题逻辑。首先，介绍了命题和命题公式的概念。然后，在此基础上，研究了命题公式之间的等价关系和蕴涵关系，给出了推导命题的推理规则。主要内容如下：2.1命题的概念和表示2.2逻辑合取2.3命题演算的适当公式2.4等价和蕴涵2.5对偶和范式2.6命题演算的推理理论，例1判断下列陈述是否为命题。(1)空气是人类生存所必需的。(2)请关门。南京是中国的首都。你吃过了吗？(5)x=3 .啊，多美啊！明年的春节将是一个阳光明媚

2、的日子。解释性声明(1)、(3)、(5)和(7)是声明，而声明(1)、(3)和(7)是命题。真值用来描述一个命题是真还是假。它们分别用“1”和“0”表示，命题用大写的拉丁字母A、B、C、P、Q或带有下列标记的大写字母表示。如果下列陈述是命题。p:在地球之外的行星上也有人类；小王是我的好朋友；解P和Q是命题，原子命题是由简单句子构成的命题。复合命题：由一个或几个由连词连接的原子命题组成的命题。李明是一个好学生。李明既是三好学生又是足球运动员。明天将是晴天。d:张萍不是在钓鱼，就是在睡觉。如果明天天气晴朗，我们将举行运动会。解A和C是原子命题，解D和E是复合命题，2.2逻辑合取，1。2.2.1如果

3、P是一个命题，那么P的否定就是一个复合命题，它被称为P的无命题，并被标为“P”(发音为“非P”)。让我们举个例子：上海是一座城市；问：每个自然数都是偶数。上海不是一个城市；问：不是每个自然数都是偶数。当命题p为真时，命题p为假；当命题p为假时，命题p为真。2连词的定义2.2.2假设P和Q是两个命题，那么P和Q的连词就是一个复合命题，叫做“P Q”。我们去电影院吧。问：房间里有十张桌子。问的意思是“我们去看电影，房间里有十张桌子。”当且仅当命题p和Q都为真时，P Q为真。3.析取的定义2.2.3假设P和Q是两个命题，那么P和Q的析取是一个复合命题，标记为PQ(发音为P或Q)。他可能是100米赛跑

4、的冠军；问：他可能是400米赛跑的冠军。命题PQ表明他可能是100米或400米赛跑的冠军。当且仅当P和Q中至少一个为真时，PQ为真。4.“定义2.2.4假设P和Q是两个命题，那么它们的条件命题是一个复合命题，它被记录为“PQ”(发音为“如果P，那么Q”)。如果我得到这本小说，那么我将在今晚读完它象征。谢玲P:我得到了这本小说；问：我今晚读完了。所以上述命题可以表示为PQ。如果p:雪是黑色的；问：太阳从西方升起；太阳从东方升起。那么PQ和PR所代表的两个命题都是正确的。当P为真，Q为假时，PQ为假，否则PQ为真。5等价定义2.2.5如果P和Q是两个命题，那么它们的等价命题就是复合命题，这种复合命

5、题被称为等价复合命题，并被标为“P Q”。当P和Q的真值相同时，PQ为真，否则为假。非仓库工人不允许进入。订单p:有人是仓库工人；问：有人可以进入仓库。上述命题可以表示为p q。黄山比喜马拉雅山高，如果且仅当3是素数，p:黄山比喜马拉雅山高；问：3是质数。这个例子可以被符号化为PQ。从汉语的语义角度看，P和Q之间没有联系，但就连词的定义而言，PQ的真值是假的，因为P和Q的真值是真的。对于以上五个连词，应该注意到复合命题的真值只取决于构成它的每个原子命题的真值，而与这些原子命题的内容和意义无关。命题符号化许多日常句子可以用连词来符号化。基本步骤如下：(1)将原子命题从句子中分离出来，并进行符号化

6、；(2)用适当的命题连词将原子命题一个接一个地联系起来，形成复合命题的符号表征。下列命题以符号形式表达。如果明天早上下雨或下雪，我就不去上学了。如果明天早上不下雨或不下雪，那么我就去上学。如果明天早上不是雨夹雪，那我就去上学。只有明天早上不下雨不下雪的时候，我才会去上学。解释p:明天早上会下雨；问：明天早上会下雪；我去学校。(1)(PQ)R；(2)(P Q)R；(3)(PQ)R (4)R(P Q)，例13象征下列命题(1)派小王或小李出差；(2)我们不能划船和跑步；(3)如果你来，他是否唱歌将取决于你是否陪他；(4)如果李明是体育爱好者，但不是文学爱好者，那么李明不是体育爱好者；如果早上不下雨

7、，我就去看电影，否则我就在家看书。解决方案(1)订单P:派小王出差；问：派小李出差。命题被符号化为PQ。让我们划船；问：我们跑步。那么这个命题可以表示为(PQ)。(3)订餐员：你来了；他唱歌；你陪着。那么这个命题可以表示为P (Q R)。(4)让李明成为一名体育爱好者；问：李明是一个文艺爱好者。那么这个命题可以表达为(P Q)(P Q)，(5)让P:早上下雨；问：我去看电影了；我在家学习。那么这个命题可以表示为。练习2-2 1。确定下列哪个陈述是命题，如果它们是命题，指出它们的真实值。(1)只有孩子喜欢哭。(2)X6=y3)银是白色的。(4)起来，我的朋友。(假)，(不)，(真)，(不)，2象

8、征下列命题(1)我看到的既不是小张也不是老李。谢玲P:我看到的是小张；问：我看到的是老李。这个命题可以表示为PQ。如果他晚上完成作业，没有别的事情可做，他就会看电视或听音乐。他晚上完成了作业；问：他晚上还有别的事情；他看电视。他听音乐。那么命题可以表示为(PQ)(RS)，2.3命题演算的适当公式1。命题公式1的概念。命题常数是表示一个确定命题的大写字母。命题论证没有具体内容的命题符号。当一个命题没有内容时，它的真正价值就无法确定。一旦一个特定的命题被取代，它的真正价值就被确定了。命题公式命题公式(或简称公式)是由0，1，命题参数和命题连词按照一定的规则产生的符号串。定义2.3.1(命题公式的递

9、归定义。(1) 0，1是命题公式；(2)命题论证是命题公式；(3)如果甲是命题公式，那么甲就是命题公式；(4)如果A和B是命题公式，(AB)、(AB)、(A B)和(AB)也是命题公式；通过在有限时间内使用上述(1)和(4)产生的符号串是命题公式。示例1确定以下符号字符串是否是命题公式。P(QPR)；(2)(PQ)(QR)，解(1)不是命题公式。(2)它是一个命题公式。4.在例定义2.3.2中，假设A和B是两个命题公式。如果A中的一些命题变元被命题公式所取代，B就可以得到，并且这种取代满足：(1)它是被取代的命题变元；(2)如果一个命题变元要被替换，则A中所有出现的命题变元都应该被替换。(3)

10、如果代换必须同时独立进行，则称B为A的代换实例。例2假设A=P(Q P)，并判断以下命题公式是否为A的代换实例：B=SR (Q (SR) C=SR (Q P)，并求解B。C不是。2.真值赋予命题公式来表示一个命题，但只有当公式中的每一个命题参数都被一个确定的命题所取代时，命题公式才具有确定的真值并成为一个命题。定义2.3.3设A(P1、P2、Pn)是一个命题公式，P1、P2、Pn都是出现在其中的命题论据。给P1、P2、Pn赋值就叫做给P1、P2、Pn的公式A赋值。列出了P1、P2、Pn的2n个真值赋值下命题公式A的真值，这样的表称为A的真值表.例3给出了公式F=(PQ)(QR) (PR)的真值

11、表。求解公式f的真值表如下：3 .公式类型的定义2.3.5如果命题公式f中包含的命题自变量的任何一组真值被赋值，则公式f的真值总是真的，那么公式f被称为重言式(或永恒真值公式)，通常表示为“1”。相反，如果f的真值对于f中包含的命题自变量的任何一组真值赋值总是假的，那么公式f被称为矛盾公式(或永久假公式)，它通常被表示为“0”。如果至少分配了一组真值来使公式f的真值为真，那么f被称为可满足公式。例4构造下列命题公式的真值表，并判断它们是什么类型的公式(1)(p q)(p q)；(2)(QP)(PQ)；(3)(PQ)(QR)(PR).从上面可以看出，F1是同义反复，F2是矛盾。2.4等效和隐含，

12、1。命题公式等价关系的定义2.4.1假设A和B是两个命题公式，P1，p2，pn都是出现在A和B中的命题参数，如果A和B的真值对于分配给P1，p2，pn的任何一组真值都是相同的，那么公式A和B是等价的，表示为A和B，A B是等价的。注意：(1)符号“”和“”的区别和联系。(2)可以证明等价关系满足：自反性：对于任何公式A，都有一个a A。对称性：对于任何公式a，b，如果是AB，那么是BA。可转让性：对于任何公式a，b，c，如果ab，BC，然后AC。(3)当A是同义反复时，A1；当A是矛盾的，A0。定理2.4.1当且仅当一个公式总是正确的。2.假设P、Q和R是命题参数，下表列出了24个基本等价公式

13、：3.区分等价公式有两种方法：真值表法、命题演算法1、真值表法，例1:用真值表法证明E10: (PQ) PQ，并求解它：A=(PQ)。0，例2用真值表法证明E11:PQPQ，并使A=PQ，B=PQ构造A，B和AB的真值表如下：因为公式AB标记的所有列都是1，AB。例3使用真值表方法判断PQPQ是否为真，并使A=PQ，B=PQ构造A、B和AB的真值。(1)替代规则的同义反复的替代实例仍然是同义反复。2命题演算方法，例如，F=(PQ) (QP)是一个同义反复。如果用公式AB代替命题变元P得到公式F1=(AB)Q) (Q(AB)，F1仍然是同义反复。注意：因为甲乙是同义反复，当且仅当甲乙是同义反复。

14、因此，如果在等价公式中出现任何命题论证的每一个地方都用同一个命题公式代替，那么仍然可以得到等价公式。(2)代换规则是C是命题公式A的一部分(即C是公式A中的一系列符号)，而C本身也是命题公式，那么C就叫做公式A的子公式，例如，让公式A=(PQ)(PQ)(RS)。PQ，PQ，(PQ)(RS)都是a的子公式，但p，p和q不是a的子公式，替换规则是c是公式a，CD的子公式。如果公式a中的子公式c被公式d代替，得到的公式是b，然后是AB。(3)等价演算等价演算是指利用一些已知的等价公式，根据等价关系的代换规则、代换规则和可转移性，推导出其他等价公式的过程。根据替换规则，上述基本等价公式不仅对任何命题变量p，q和r有效，而且当p，q和r分别是命题公式时也有效。例2证明了命题公式的等价关系：(pq)(rq)(pr)q；为了证明(PQ)(RQ)(PQ)(RQ)E11(P(R)Q E3(分布律)(PR)Q E10(德摩根定律)(PR) Q E11 so (PQ)(RQ)(PR)Q，例3证明了下列命题公式的等价关系(p q) (p证明(PQ)(P(PQ)(PQ)(P(P)Q)E2(结合律)，(PQ)(PQ) E7(等幂律)，(P Q)(PQ)(E1(交换律)，3.命题公式蕴涵关系的定义2.4.2假设A和B是两个公式。如果公式AB是同义反复，即AB1，那么公