离散数学-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,四、公式等价,PQ,PQ,14,四、公式等价,又如(P14 表1-4.6),P Q 与（P Q）（P Q）,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）中以（ P Q）取代（PQ），则Q（P （ P Q）就与原式不同。为了保证取代后的公式与原式等价（即真值相同），需要对置换作出一些规定。,17,五、公式置换,定义 1-4.3 如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的子公式。 定理 1-4.1 设X是合式公式A的子公式，若 X Y，如果将A中的X用Y来置换，所得到公式B与公式A等价，即A B。 证明 书P16 *满足定理1-4.1条件的置换称为等价置换（等价代换）,18,六、等值演算,虽然用真值法可以判断任何两个命题公式是否等值，但当命题变元较多时，工作量是很大的。可以先用真值表验证一组基本的又是重要的等价公式，以它们为基础进行公式之间的演算，来判断公式之间的是否等值。下面给出15组（共24个）重要的等值式，希望同学们牢牢记住它们。在下面公式中出现的P,Q,R仍然是元语言符号，它们代表任意的命题公式。P15 表1-4.8,19,六、等值演算,1. 双重否定律(对合律） P P 2. 幂等律 PP P PP P 3. 结合律 (PQ)R P(QR) (PQ)R P(QR) 4. 交换律 PQ QP PQ QP,20,六、等值演算,5.分配律 P(QR) (PQ)(PR) （对的分配律） P(QR) (PQ)(PR) （对的分配律） 6.吸收律 P(PQ) P P(PQ) P 7.德.摩根律 (PQ) PQ (PQ) PQ 8. 同一律 A0 A A1 A,21,六、等值演算,9.零律 P1 1 P0 0 10.否定律 PP 1 （排中律） PP 0 （矛盾律） 11.蕴涵等值式（补充） PQPQ 12. 等价等值式（补充） (P Q) (PQ)(QP),22,六、等值演算,13.假言易位 （补充） PQ QP 14.等价否定等值式（补充） P Q P Q 15.归谬论（补充） (PQ)(PQ) P,23,六、等值演算,在最基本的15组命题公式的等价关系的基础上，利用等价置换就可以推证一些更为复杂的命题等价公式。 例：命题公式(PQ)R中 ，可用PQ置换其中的PQ，由蕴涵等值式可知， PQ PQ， 所以有 (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)R P(QR) 证 方法一：真值表法，可自己证明。 方法二 ：设A=(PQ)R,B=P(QR) 先将A,B通过等值演算化成容易观察真值的情况，再进行判断。 A=(PQ)R (PQ)R （蕴涵等值式） (PQ)R （蕴涵等值式） (PQ)R （德摩根律） B=P(QR) P(QR) （蕴涵等值式） PQR （