离散数学-1-4真值表与等价公式.ppt

1,第一章命题逻辑,1-4真值表与等价公式,2,一、公式的层次,公式的层次（补充）定义：(1)若公式A是单个的命题变元，则称A为0层公式。(2)称A是n+1(n0)层公式是指下面情况之一：AB，B是n层公式；ABC，其中B，C分别为i层和j层公式，且nmax(i，j)；ABC，其中B，C的层次及n同(b)；ABC，其中B，C的层次及n同(b)；ABC，其中B，C的层次及n同(b)；(3)若公式A的层次为k，则称A是k层公式。易知，(PQ)R，(PQ)(RS)P)分别为3层和4层公式。,3,二、命题公式分量指派,公式就代表命题，但代表的命题是真还是假呢？在命题公式中，由于有命题符号的出现，因而真值是不确定的。当将公式中出现的全部命题符号都解释成具体的命题之后，公式就成了真值确定的命题了。例如，在公式(PQ)R中:若将P解释成：2是素数，Q解释成：3是偶数，R解释成：是无理数，则P与R被解释成真命题，Q被解释成假命题了，此时公式(PQ)R被解释成：若2是素数或3是偶数，则是无理数。这是一个真命题。,4,二、命题公式分量指派,若P，Q的解释不变，R被解释为：是有理数，则(PQ)R被解释成：若2是素数或3是偶数，则是有理数。这是个假命题。其实，将命题符号P解释成真命题，相当于指定P的真值为1，解释成假命题，相当于指定P的真值为0。在本课中，对含n个命题变项的公式A的指派（赋值）情况做如下规定：1若A中出现的命题符号为P1,P2,Pn，给定A的指派（赋值）1,2,n是指P11，P22,，Pnn。,5,二、命题公式分量指派,2若A中出现的命题符号为P，Q，R.,给定A的指派（赋值）1,2,n是指P1，Q2,，最后一个字母赋值n。上述i取值为0或1，i1,2,n。例如，在公式(P1P2P3)(P1P2)中000(P10，P20，P30)，110(P11，P21，P30)都是成真赋值而001(P10，P20，P31)011(P10，P21，P31)都是成假赋值。在(PQ)R中，011(P0，Q1，R1)为成真赋值，100(P1，Q0，R0)为成假赋值。,6,二、命题公式分量指派,不难看出，含n(n1)个命题变元的公式共有2n个不同的指派（赋值）。下面的问题是，指定P，Q，R的真值为何值时，(PQ)R的真值为1；指定P，Q，R的真值为何值时，(PQ)R的真值为0。为看清命题公式在各种指派下的取值情况，通常构造下面的“真值表”。,7,三、真值表,定义1-4.1在命题公式中，对于各分量指派真值的各种可能组合，就确定了这个命题公式的各种真种情况，把它汇列成表，就是命题公式的真值表。真值表的构造步骤：(1)找出公式中所含的全体命题变项P1,P2,Pn(若无下角标就按字典顺序排列)，列出2n个赋值。本课规定，赋值从000开始，然后按二进制加法依次写出各赋值，直到111为止。,8,三、真值表,(2)按从低到高的顺序写出公式的各个层次。(3)对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。例求下列公式的真值表，并求成真赋值和成假赋值。(1)(PQ)R(2)(PP)(QQ)(3)(PQ)QR,9,三、真值表,解:公式(1)是含3个命题变项的3层合式公式。它的真值表如表1所示。表1(PQ)R的真值表从表1可知，公式(1)的成假赋值为011，其余7个赋值都是成真赋值。,10,三、真值表,公式(2)是含2个命题变项的3层合式公式，它的真值表如表2所示。表2(PP)(QQ)的真值表从表2可以看出，该公式的4个赋值全是成真赋值，即无成假赋值。,11,三、真值表,公式(3)是含3个命题变项的4层合式公式。它的真值表如表3所示。表3(PQ)QR的真值表它的真值表如表3所示。不难看出，该公式的8个赋值全是成假赋值，它无成真赋值。,12,三、真值表,注意：表1表3都是按构造真值表的步骤一步一步地构造出来的，这样构造真值表不易出错。如果构造的思路比较清楚，有些层次可以省略。有一类公式，不论其命题变元做何种指派，其真值永为真（假），就把这类公式记为T（F）。关于n个命题变元P1,P2,Pn,可以构造多少个真值表呢?,n个命题变元共产生2n个不同指派,在每个指派下,公式的值只有0和1两个值。于是n个命题变元的真值表共有种不同情况。,13,四、公式等价,根据真值表，有些命题公式在分量的不同指派下，其对应的真值与另一命题公式对应的真值完全相同，如表（P141-4.5)：,PQ,PQ,14,四、公式等价,又如(P14表1-4.6),PQ与（PQ）（PQ）,15,四、公式等价,定义1-4.2给定两个公式A和B，设P1，P2，Pn为所有出现于A和B中的原子变元，若给P1，P2，Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等，记作AB。例5：证明PQ（PQ）（QP）书P15，列出真值表证明注意：定义中给出的符号不是联结词，它是用来说明A与B等值的一种记法，因而是元语言符号。此记号在下文中频繁出现，千万不要将它与混为一谈，同时也要注意它与一般等号=的区别。,16,五、公式置换,在一命题公式中，如果用公式置换命题的某个部分，一般地会产生某种新的公式，例如Q（P（PQ）中以（PQ）取代（PQ），则Q（P（PQ）就与原式不同。为了保证取代后的公式与原式等价（即真值相同），需要对置换作出一些规定。,17,五、公式置换,定义1-4.3如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的子公式。定理1-4.1设X是合式公式A的子公式，若XY，如果将A中的X用Y来置换，所得到公式B与公式A等价，即AB。证明书P16*满足定理1-4.1条件的置换称为等价置换（等价代换）,18,六、等值演算,虽然用真值法可以判断任何两个命题公式是否等值，但当命题变元较多时，工作量是很大的。可以先用真值表验证一组基本的又是重要的等价公式，以它们为基础进行公式之间的演算，来判断公式之间的是否等值。下面给出15组（共24个）重要的等值式，希望同学们牢牢记住它们。在下面公式中出现的P,Q,R仍然是元语言符号，它们代表任意的命题公式。P15表1-4.8,19,六、等值演算,1.双重否定律(对合律）PP2.幂等律PPPPPP3.结合律(PQ)RP(QR)(PQ)RP(QR)4.交换律PQQPPQQP,20,六、等值演算,5.分配律P(QR)(PQ)(PR)（对的分配律）P(QR)(PQ)(PR)（对的分配律）6.吸收律P(PQ)PP(PQ)P7.德.摩根律(PQ)PQ(PQ)PQ8.同一律A0AA1A,21,六、等值演算,9.零律P11P0010.否定律PP1（排中律）PP0（矛盾律）11.蕴涵等值式（补充）PQPQ12.等价等值式（补充）(PQ)(PQ)(QP),22,六、等值演算,13.假言易位（补充）PQQP14.等价否定等值式（补充）PQPQ15.归谬论（补充）(PQ)(PQ)P,23,六、等值演算,在最基本的15组命题公式的等价关系的基础上，利用等价置换就可以推证一些更为复杂的命题等价公式。例：命题公式(PQ)R中，可用PQ置换其中的PQ，由蕴涵等值式可知，PQPQ，所以有(PQ)R(PQ)R在这里，使用了等价置换规则。如果再一次地用蕴涵等值式及等价置换规则，又会得到(PQ)R(PQ)R,24,六、等值演算,如果再用德摩根律及置换规则，又会得到(PQ)R(PQ)R再用分配律及置换规则，又会得到(PQ)R(PR)(QR)将以上过程连在一起，可得到(PQ)R(PQ)R(PQ)R(PQ)R(PR)(QR)*上述演算中得到的5个公式彼此之间都是等值的，在演算的每一步都用到了等价置换规则上述用等值式及等价置换规则进行推演的过程称为等值演算，这是数理逻辑的主要内容。,25,六、等值演算,例:证明(PQ)R(PR)(QR)证：可以从左边开始演算，也可以从右边开始演算。现在从左边开始演算。(PQ)R(PQ)R(蕴含等值式）(PQ)R（德摩根律）(PR)(QR)（分配律）(PR)(QR)（蕴含等值式）练习：从右边开始演算？,26,六、等值演算,例2.4证明：(PQ)RP(QR)证方法一：真值表法，可自己证明。方法二：设A=(PQ)R,B=P(QR)先将A,B通过等值演算化成容易观察真值的情况，再进行判断。A=(PQ)R(PQ)R（蕴涵等值式）(PQ)R（蕴涵等值式）(PQ)R（德摩根律）B=P(QR)P(QR)（蕴涵等值式）PQR（结合律）容易观察到，000，010是A的成假赋值，而它们是B的成真赋值,27,本节小结,公式层次命题公式分量指派真值表公式等价公式置换等值演算,28,课后作业,复习课本例题P18（7）a)、c)、e)、f)、h)(使用等值演算方法证明）补充:（使用等值演算方法或真值表证明）(PQ)(PQ)P(PQ)R(PR)(QR)P(QR)(PR)Q,