离散数学-1-4真值表与等价公式.ppt
《离散数学-1-4真值表与等价公式.ppt》由会员分享,可在线阅读,更多相关《离散数学-1-4真值表与等价公式.ppt(28页珍藏版)》请在三一文库上搜索。
1、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,二、命题公式分量指派,公式就代表命题,但代表的命题是真还是假呢? 在命题公式中,由于
2、有命题符号的出现,因而真值是不确定的。当将公式中出现的全部命题符号都解释成具体的命题之后,公式就成了真值确定的命题了。 例如,在公式(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个命
3、题变项的公式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,
4、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个赋值。本课规定,赋值从
5、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)的真
6、值表 从表2可以看出,该公式的4个赋值全是成真赋值,即无成假赋值。,11,三、真值表,公式(3)是含3个命题变项的4层合式公式。它的真值表如表3所示。 表3 (PQ)QR的真值表 它的真值表如表3所示。不难看出,该公式的8个赋值全是成假赋值,它无成真赋值。,12,三、真值表,注意:表1表3都是按构造真值表的步骤一步一步地构造出来的,这样构造真值表不易出错。如果构造的思路比较清楚,有些层次可以省略。 有一类公式,不论其命题变元做何种指派,其真值永为真(假),就把这类公式记为T(F)。 关于n个命题变元P1,P2,Pn,可以构造多少个真值表呢?,n个命题变元共产生2n个不同指派,在每个指派下,公式
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 真值 等价 公式
链接地址:https://www.31doc.com/p-2252399.html