离散数学命题公式与赋值

1.2命题(mìngtí)公式与赋值命题变项与合式公式公式的赋值真值表命题的分类(fēnlèi)重言式矛盾式可满足式第一页，共14页。1命题(mìngtí)变项与合式公式命题常项：真值确定(quèdìng)的简单命题.命题变项：真值不确定(quèdìng)的陈述句.命题(mìngtí)变项不是命题(mìngtí)！合式公式：将命题常项和命题变项用联结词和圆括号按一定的逻辑关系联接起来的符号串.注意:第二页，共14页。2定义合式公式(命题公式,公式)递归定义如下：(1)单个命题常项或变项p,q,r,…,pi,qi,ri,…,0,1是合式公式；(2)假设A是合式公式，那么(A)也是合式公式；(3)假设A,B是合式公式，那么(AB),(AB),(AB),(AB)也是合式公式；(4)只有有限次地应用(1)—(3)形成(xíngchéng)的符号串才是合式公式。说明:最外层括号可以省去.第三页，共14页。3合式公式的层次(céngcì)定义(1)假设(jiǎshè)A是单个的命题变项或常项,那么称A为0层公式.(2)称A是n+1(n≥0)层公式是指下面情况之一：(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).第四页，共14页。4又如：((pq)

r)s((p

q

r)s(pqr)合式公式的层次(céngcì)(续)例如(lìrú)公式pppq(pq)r((pq)r)(rs)0层1层2层3层4层4层5层第五页，共14页。5公式(gōngshì)的赋值定义给公式A中的命题变项p1,p2,…,pn指定一组真值称为对A的一个(yīɡè)赋值或解释。成真赋值:使公式为真的赋值.成假赋值:使公式为假的赋值.第六页，共14页。6说明(shuōmíng)：赋值=12…n之间不加标点符号，i=0或1.A中仅出现p1,p2,…,pn，给A赋值12…n是指p1=1,p2=2,…,pn=nA中仅出现p,q,r,…,给A赋值123…是指p=1,q=2,r=3…含n个变项的公式有？个赋值.——字典(zìdiǎn)顺序2n第七页，共14页。7真值表构造(gòuzào)真值表的步骤：1)找出公式中所含的全部命题变项，列出所有可能的赋值；2)按从低到高的顺序写出各层次；3)对应各赋值，计算公式各层次的值，直到最后算出公式的值。真值表:公式(gōngshì)A在所有赋值下的取值情况列成的表第八页，共14页。8例1.8求以下(yǐxià)公式的真值表.pq

00011011110110001111(1)A=(qp)qp

qp

(qp)q(qp)qp

第九页，共14页。9(2)B=(pq)q

pqppq(pq)(pq)q00011011

1111110000000000第十页，共14页。10(3)

C=(pq)rpqrpq

r

(pq)r

000001010111011100101110000000000111111111111111第十一页，共14页。11公式(gōngshì)的类型重言式是可满足式，但反之(fǎnzhī)不真.上例中A=(qp)qp，B=(pq)q，C=(pq)rA为重言式，B为矛盾式，C为可满足式定义设A为一个命题公式(1)假设A无成假赋值，那么称A为重言式(也称永真式)(2)假设A无成真赋值，那么称A为矛盾式(