第三章命题逻辑

第三章命题逻辑1、判断下列语句是否是命题,如果是命题,指出其真值：（1）2是无理数；(2)存在最大质数；（1）中国是一个人口众多的国家；（2）这座楼真高啊！（3）你喜欢“蓝色的多瑙河”吗？（4）请你关上门。（5）地球以外的星球上也有人。解（1）是命题，真值为1。（1）是命题，真值为0。（2）是命题，真值为1。（3）、（5）、（6）均不是命题。（6）是命题，真值是惟一的，迟早会被指出。说明要判断一个语句是否是命题，首先要判断它是否是陈述句，然后再判断它的真值是否是惟一的。本题中，（4）、（5）、（6）均不是陈述句，无法分辨其真假，故都不是命题。陈述句不一定是命题，这里的关键是：客观上有无真假可言，而不以主观能否判断为标准。2、将下列命题符号化，并确定其真值：（1）5不是偶数；（2）天气炎热但湿度较低；（3）2+3=5或者他游泳；（4）如果a和b是偶数，则a+b是偶数；（5）2+2=4，当且仅当3是奇数。解（1）设P：5是偶数。则（1）是：P，真值为1。（2）设P：天气炎热。Q：湿度较低。则（2）是：P∧Q。显然，只有在既炎热又湿度较低的情况下，P∧Q的真值为1，否则，其真值皆为0。（3）设P：2+3=5。Q：他游泳。则（3）是：P∨Q，真值为1。（4）设P：a和b是偶数。Q：a+b是偶数。则（4）是PQ，真值为1。（5）设P：2+2=4。Q：3是奇数。则（5）是：PQ，真值为1。3、设命题P，Q的真值为1，命题R，S的真值为0，试确定下面命题的真值：（1）G=（P∧Q∧R）∨（（P∨Q）∧（R∨S）；（2）G=（﹁（P∧Q）∨R）∨（（（﹁P∧Q）∨﹁R）∧S）；（3）G=（（P∧Q）∨R）∧（（QP）（R∨S））；（4）G=（P∨（Q（R∧P）））（Q∨S）。解（1）PQRSP∧Q∧RP∨QR∨S（（P∨Q）∧（R∨S）G110001011故（1）的真值为1。（2）PQRSP∧Q（﹁P∧Q）∨RG1100111故（2）的真值为1。（3）PQRSP∧Q（P∧Q）∨RQPR∨S（QP）（R∨SG1100110111故（3）的真值为1。PQRSPP∨（Q（R∧P））Q∨SG11001111故（4）的真值为1。4、在什么情况下，下面的命题是真的：“说戏院是寒冷的或者是人们常去的地方是不对的，并且说别墅是温暖的或者戏院是讨厌的也是假的。”解设P：戏院是寒冷是；Q：戏院是人们常去的地方；R：别墅是温暖的；S：戏院是讨厌的；于是，题设命题为G=（﹁（P∨Q））∧（﹁（R∨S）），且G的真值为1。由此可知，命题（﹁（P∨Q））与（﹁（R∨S））的真值同时为1，即命题（P∨Q）与（R∨S）的真值同时为0，亦即命题P，Q，R，S的真值同时为0。故当“戏院是温暖的，戏院不是人们常去的地方，别墅是寒冷的，戏院是不讨厌的”时，题设命题是真的。说明比较复杂的复合命题，命题之间往往会同时用多个联结及圆括号加以联结。在确定这种形式命题的真值过程中，必然会涉及到真值计算的次序。如果出现的联结词相同，又无括号时，按从左到右的次序运算；若遇有括号时，优先进行括号中的运算。总之，应按运算次序逐次求出真值的中间结果，直至完成全部计算。5、构造下列公式的真值表，并解释其结果。（1）（P∧（PQ））Q；（2）﹁（PQ）∧Q；（3）（P∨Q）（Q∨R）解（1）的真值表PQPQP∧（PQ）（P∧（PQ））Q00011011101101001111可见：（P∧（PQ））Q是恒真的。（2）的真值表PQPQ﹁（PQ）﹁（PQ）∧Q00011011100100010100可见：﹁（PQ）∧Q是恒假的。（3）的真值表PQRP∨QQ∨R（P∨Q）（Q∨R）000001010011100001010111111100101110111111111111可见：（P∨Q）（Q∨R）是可满足的。说明从从依照递归形式所给出的公式的定义中，可以看出：公式是一个符号串，设有真值，不是命题，是命题的抽象，仅当我们对其中的各个原子，用确定的真（1）或假（0）代入解释（赋值）时，才得到一个命题。并将公式在其所有解释下所取真值列成的一个表，称为其真值表。构造真值表的步骤如下：（1）找出给定公式G中所有的原子AAn,,1（n≥1），列出所有可能的解释（2n个）。（2）按照从低到高的顺序列出G的各层次，最后为G本身。（3）根据五个逻辑联结词的真值表，计算出各层次的真值，直至计算出G的真值。在本题的三个真值表中，我们还会看到有三种不同类型的最后结果。其中（1）的最后一列全为1（真），（2）的最后一列全为0（假），（3）的最后一列既有1又有0，我们将其分别称为恒真的，恒假的和可满足的。因此，构造公式G的真值表，是判断公式G的类型的一种方法当然，真值表还有其它的用途，而判断公式的类型也还有其它的方法。6、用真值表判断下列公式是恒真？恒假？可满足？（1）（P﹁P）﹁P；（2）﹁（PQ）∧Q；（3）（P∧﹁P）Q；（4）（（PQ）∧（QR））（PR）解（1）的真值表P﹁PP﹁P（P﹁P）﹁P01111001故公式（1）为恒真。（2）的真值表PQPQ﹁（PQ）﹁（PQ）∧Q00011011100100010100故公式（2）为恒假。（3）的真值表PQ﹁PP∧﹁P（P∧﹁P）Q00011011101100001000故公式（3）为可满足。（4）的真值表PQRPQQR（PQ）∧（QR）PR（（PQ）∧（QR））（PR）0000010100111001011101111111111111100111111101001010111000111111故公式（4）为恒真的。说明设G：公式I：G的所有解释当真值)(1GT≡1时，称G为恒真的。)(1GT≡0时，称G为恒假的。)(1GT=10时，称G为可满足的。由定义可知，恒真的和恒假的公式有些很好的特性，如：（1）G∨﹁G恒真；G∧﹁G恒假。（若G表示原子，亦然）；（2）G是恒真的﹁G是恒假的；（3）两个恒真的公式的析取、合取、蕴涵、等值均为恒真的。公式恒真性的判定，是数理逻辑的重要问题。虽然我们可以用真值表法来判定这一问题，但是这种方法，对于原子数较多的公式，相当繁复。利用求与G等价范式的方法，来解决判定问题在某些情况下会简单一些。7、证明下面的等价式：（1）（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）=R；（2）（P∧（Q∧S））∨（﹁P∧（Q∧S））=Q∧S；（3）P(QR)=(P∧Q)R;(4)﹁(PQ)=(P∧﹁Q)∨(﹁P∧Q)证(1)（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）=（﹁P∧（﹁Q∧R））∨（Q∨P）∧R）(分配律)=((﹁P∧﹁Q)∧R)∨（Q∨P）∧R)(结合律)=((﹁P∧﹁Q)∨（Q∨P）)∧R)(分配律)=(﹁(P∨Q)∨(P∨Q))∧R(德·摩根律)=1∧R(互补律)=R(同一律)(2)（P∧（Q∧S））∨（﹁P∧（Q∧S））=(（Q∧S）∧P)∨((Q∧S)∧﹁P)(交换律)=（Q∧S）∧(P∨﹁P)(分配律)=（Q∧S）∧1(互补律)=Q∧S(同一律)(3)P(QR)=﹁P∨(﹁Q∨R)(蕴涵律)=(﹁P∨﹁Q)∨R(结合律)=﹁(P∧Q)∨R(德·摩根律)=(P∧Q)R(蕴涵律)(4)﹁(PQ)=﹁((PQ)∧(QP)(等价律)=﹁((﹁P∨Q)∧(﹁Q∨P))(蕴涵律)=﹁(﹁P∨Q)∨﹁(﹁Q∨P)(德·摩根律)=(﹁(﹁P)∧﹁Q)∨(﹁(﹁Q)∧﹁P)(双重否定律)=(P∧﹁Q)∨(﹁P∧Q)(交换律)8、证明G∨（G∧H）=G（吸收律）证G∨（G∧H）=G∧1∨（G∧H）（同一律）=G∧（H∨﹁H）∨（G∧H）（互补律）=（G∧H）∨（G∧﹁H）∨（G∧H）(分配律)=（G∧H）∨（G∧H）∨（G∧﹁H）(交换律)=（G∧H）∨（G∧﹁H）（等幂律）=G∧（H∨﹁H）(分配律)=G∧1(互补律)=G(同一律)证毕.9、化简下列各式：（1）A∨（﹁A∨（B∧﹁B））；（2）（A∧B∧C）∨（﹁A∧B∧C）.解(1)A∨（﹁A∨（B∧﹁B））=A∨（﹁A∨0）(互补律)=A∨﹁A(同一律)=1(互补律)(2)(A∧B∧C)∨（﹁A∧B∧C）=(A∧(B∧C))∨（﹁A∧(B∧C)）(结合律)=(A∨﹁A)∧(B∧C)(分配律)=1∧(B∧C)(互补律)=B∧C(同一律)说明设有公式G，H，判定它们是否等价（即G=H），一般来说，常用下面的方法：1、真值表法分别瘵G，H的真值表列出，如果它们的真值表完全相同，则G与H等价，否则就不等。但是，当公式很繁杂，或所含符号很多时，真值表法的工作量太大。2、推演法依据基本等价式，在等价的意义下，对G进行推演，得到G=H的形式。3、主范式法分别求出G与H的主析（合）取范式，若他们相同，则G与H等价；若它们不同，则G与H不等价。4、范式法判断GH恒真时，则G与H等价。另外，需要指出的是，公式G的等价形式是不唯一的。10、试将下列公式化为析取范式和合取范式：（1）P∧（PQ）；（2）﹁（P∨Q）（P∧Q）（3）（（P∨Q）R）P；（4）（PQ）（﹁Q﹁P）.解(1)P∧（PQ）=P∧(﹁P∨Q)(蕴涵律)合取范式=(P∧﹁P)∨（P∧Q）(分配律)析取范式(2)﹁（P∨Q）（P∧Q）=(﹁（P∨Q）（P∧Q）)∧(（P∧Q）﹁（P∨Q）)(等值律)=(（P∨Q）∨（P∧Q）)∧(﹁（P∧Q）∨﹁（P∨Q）)(蕴涵律)=（P∨Q）∧(﹁P∨﹁Q)(分配律)合取范式=(﹁P∨P)∨(﹁P∨Q)∨(﹁Q∧P)∨(﹁Q∧Q)(分配律)析取范式(3)（（P∨Q）R）P=(﹁（P∨Q）∨R)P(蕴涵律)=﹁(﹁（P∨Q）∨R)∨P(蕴涵律)=(﹁﹁（P∨Q）∧﹁R)∨P(德·摩根律)=(（P∨Q）∧﹁R)∨P(双重否定律)=（P∨Q∨P）∧(﹁R∨P)(分配律)合取范式=(P∧﹁R)∨(Q∧﹁R)∨P(分配律)析取范式(4)（PQ）（﹁Q﹁P）=(﹁P∨Q)(﹁﹁Q∨﹁P)(蕴涵律)=(﹁P∨Q)(Q∨﹁P)(双重否定律)=((﹁P∨Q)(Q∨﹁P))∧((Q∨﹁P)(﹁P∨Q))(等值律)=(﹁(﹁P∨Q)∨(Q∨﹁P))∧((﹁Q∧﹁﹁P)∨(﹁P∨Q))(蕴涵律)=((﹁﹁P∧﹁Q)∨(Q∨﹁P))∧((﹁Q∧﹁﹁P)∨(﹁P∨Q))(德·摩根律)=((P∧﹁Q)∨(Q∨﹁P))∧((﹁Q∧P)∨(﹁P∨Q))(双重否定律)=(P∨Q∨﹁P)∧(﹁Q∨Q∨﹁P)∧(﹁Q∧﹁P∨Q)∧(P∨﹁P∨Q)合取范式=(P∧﹁Q)∨(Q∧﹁Q∧P)∨(P∧﹁Q∧P)∨(﹁P∨Q)(分配律)析取范式说明为得到任意一个公式G的范式(合取范式或析取范式)的步骤如下：（1）应用蕴涵律和等值律，删除G中的和，使G中只含有∨，∧，﹁。（2）应用双重否定律和(德·摩根律)，将G中所有﹁移至原子之前，使G中每个子句和短语中不含﹁或只有一个﹁。（3）反复使用分配律，当欲得到合取范式时，用∨分配律；当欲得到析取范式时，用∧分配律。另外，一个公式的合取范式和析取范式都是不唯一的，当然其真值是相等的。因此利用范式来判定两个公式是否等价，并不方便，但是，任意一个公式和主范式是唯一的，从而解决了等价公式的判定问题。11、模仿主析取范式概念，引进主合取范式概念，并证明：对任意公式存在唯一一个与其等价的主合取范式。解：首先介绍极大项的概念。定义设PPn,,1是n个原子，一个子句如果恰好包含所有这n个原子及其否定，且排列顺序与PPn,,1的顺序一致，则称此子句为关于PPn,,1的一个极大项。例如，对原子P，Q，R而言，P∨﹁Q∨R，﹁P∨﹁Q∨R，P∨Q∨R都是关于的P，Q，R的极大项。但是，P，﹁P∨Q不是P，Q，R的极大项。而﹁P∨Q是关于P，Q的极大项。显然，对于两个原子P，Q而言，其不同的解释有22个，如表3-4所