《离散数学命题公式与赋值》由会员分享，可在线阅读，更多相关《离散数学命题公式与赋值（13页珍藏版）》请在金锄头文库上搜索。
1、1,1.2 命题公式与赋值,命题变项与合式公式 公式的赋值 真值表 命题的分类 重言式 矛盾式 可满足式,2,命题变项与合式公式,命题常项：真值确定的简单命题. 命题变项：真值不确定的陈述句.,命题变项不是命题！,合式公式：将命题常项和命题变项用联结词和 圆括号按一定的逻辑关系联接起来的符号串.,注意:,3,定义 合式公式(命题公式, 公式)递归定义如下： (1) 单个命题常项或变项p, q, r, , pi , qi , ri , , 0, 1是合式公式； (2) 若A是合式公式，则(A)也是合式公式； (3) 若A,B是合式公式，则(AB), (AB), (AB), (AB)也是合式公式；
2、 (4) 只有有限次地应用(1)(3)形成的符号串才是合式公式。 说明: 最外层括号可以省去.,4,合式公式的层次,定义 (1) 若A是单个的命题变项或常项, 则称A为0层公式. (2) 称A是n+1(n0)层公式是指下面情况之一： (a) A=B, B是n层公式； (b) A=BC, 其中B,C分别为i层和j层公式，且 n=max(i, j)； (c) A=BC, 其中B,C的层次及n同(b)； (d) A=BC, 其中B,C的层次及n同(b)； (e) A=BC, 其中B,C的层次及n同(b).,5,又如： (p q) r)s (p q r )s(p q r),合式公式的层次 (续),例如
3、 公式 p p pq (pq)r (pq) r)(rs),0层,1层,2层,3层,4层,4层,5层,6,公式的赋值,定义 给公式A中的命题变项 p1, p2, , pn 指定一组真值称为对A的一个赋值或解释。 成真赋值: 使公式为真的赋值. 成假赋值: 使公式为假的赋值.,7,说明： 赋值=12n之间不加标点符号，i=0或1. A中仅出现 p1, p2, , pn，给A赋值12n是 指 p1=1, p2=2, , pn=n A中仅出现 p, q, r, , 给A赋值123是指 p=1, q=2 , r=3 含n个变项的公式有 ？ 个赋值., 字典顺序,2n,8,真值表,构造真值表的步骤： 1)
4、找出公式中所含的全部命题变项，列出所有可 能的赋值； 2)按从低到高的顺序写出各层次； 3)对应各赋值，计算公式各层次的值，直到最后 算出公式的值。,真值表:公式A在所有赋值下的取值情况列成的表,9,例1.8 求下列公式的真值表.,0 0,0 1,1 0,1 1,1,1,0,1,1,0,0,0,1,1,1,1,(1) A= (qp) qp,qp,(qp) q,(qp)qp,10,(2) B = (pq) q,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,11,(3) C = (pq) r,0 0 0,0 0 1,0 1 0,1 1 1,0 1 1,1 0 0,1 0 1,1 1 0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,12,公式的类型,重言式是可满足式，但反之不真. 上例中 A= (qp)qp，B = (pq)q， C= (pq)r A为重言式，B为矛盾式，C为可满足式,定义 设A为一个命题公式 (1)若A无成假赋值，则称A为重言式(也称永真式) (2)若A无成真赋值，则称A为矛盾式(也称永假式) (3)若A不是矛盾式，则称A为可满足式。,注意:,13,作业: P35：6,
