1、1,1.2 命題公式與賦值,命題變項(xiàng)與合式公式 公式的賦值 真值表 命題的分類 重言式 矛盾式 可滿足式,2,命題變項(xiàng)與合式公式,命題常項(xiàng)：真值確定的簡單命題. 命題變項(xiàng)：真值不確定的陳述句.,命題變項(xiàng)不是命題！,合式公式：將命題常項(xiàng)和命題變項(xiàng)用聯(lián)結(jié)詞和 圓括號(hào)按一定的邏輯關(guān)系聯(lián)接起來的符號(hào)串.,注意:,3,定義 合式公式(命題公式, 公式)遞歸定義如下： (1) 單個(gè)命題常項(xiàng)或變項(xiàng)p, q, r, , pi , qi , ri , , 0, 1是合式公式； (2) 若A是合式公式，則(A)也是合式公式； (3) 若A,B是合式公式，則(AB), (AB), (AB), (AB)也是合式公式；

2、 (4) 只有有限次地應(yīng)用(1)(3)形成的符號(hào)串才是合式公式。 說明: 最外層括號(hào)可以省去.,4,合式公式的層次,定義 (1) 若A是單個(gè)的命題變項(xiàng)或常項(xiàng), 則稱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),合式公式的層次 (續(xù)),例如

3、 公式 p p pq (pq)r (pq) r)(rs),0層,1層,2層,3層,4層,4層,5層,6,公式的賦值,定義 給公式A中的命題變項(xiàng) p1, p2, , pn 指定一組真值稱為對(duì)A的一個(gè)賦值或解釋。 成真賦值: 使公式為真的賦值. 成假賦值: 使公式為假的賦值.,7,說明： 賦值=12n之間不加標(biāo)點(diǎn)符號(hào)，i=0或1. A中僅出現(xiàn) p1, p2, , pn，給A賦值12n是 指 p1=1, p2=2, , pn=n A中僅出現(xiàn) p, q, r, , 給A賦值123是指 p=1, q=2 , r=3 含n個(gè)變項(xiàng)的公式有 ？ 個(gè)賦值., 字典順序,2n,8,真值表,構(gòu)造真值表的步驟： 1)

4、找出公式中所含的全部命題變項(xiàng)，列出所有可 能的賦值； 2)按從低到高的順序?qū)懗龈鲗哟危?3)對(duì)應(yīng)各賦值，計(jì)算公式各層次的值，直到最后 算出公式的值。,真值表:公式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為可滿足式,定義 設(shè)A為一個(gè)命題公式 (1)若A無成假賦值，則稱A為重言式