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