上節討論了簡單命題(原子命題)和復合命題以及它們的符號化方式簡單命題是命題邏輯中最基本的研究單位,其真值是確定的,又叫做命題常項或命題常元,命題常項相當于高中的常數。初等物理中還有變量,對應地這兒有命題變項。取值1(真)或0(假)的變元叫做命題變項或命題變元可以用命題變項表示真值可以變化的陳述句.命題變項不是命題,命題變項與命題常項的關系就像初等物理中變量與常量的關系今后也用p,q,r,…表示命題變項這樣來,P,q,r,…既可以表示命題常項,又可以表示命題變項,一般可以由上下文確定。
將命題變項用連結詞和圓括弧按一定的邏輯關系連結上去的符號串稱為合式公式,當使用連結詞集{┓,A,V,→,}時,合式公式定義如下.
定義1.6(1)單個命題變項和命題常項是合式公式,并稱為原子命題公式.
若A是合式公式,則(┓A)是合式公式若A,B是合式公式,則(A∧B),(AVB),(A→B),(AB)是合式公式有限次地應用(1)~(3)產生的符號串是合式公式
合式公式稱作為命題公式或命題方式,簡稱為公式.
設A為合式公式,B為A中一部份,若B也是合式公式,則稱B為A的子公式.
對于定義1.6,要做以下說明:
定義1.6給出的合式公式的定義方法稱為歸納定義或遞歸定義方法,下文中還將多次出現這些定義形式定義中引進了A,B等符號,用它們表示任意的合式公式,也稱元語言符號.而某個具體的公式,如p,P∧q,(P∧q)→r等合稱對象語言符號.所謂對象語言是指拿來描述研究對象的語言，而元語言是指拿來描述對象語言的語言,這兩種語言是不同層次的語言.做一個不完全恰當的類比，中國人學日語,常用漢語描述日語,法語是對象語言,而漢語就成了元語言。為便捷起見,(┓A),(A∧B)等公式單獨出現時,內層括弧可以省去,寫成┓A,A∧B等，另外,公式中不影響運算順序的括弧也可以省去,如公式(pVq)V(┓r)可以寫成pVgV┓r
由定義可知,(p→q)∧(qr),(P∧q)∧┓r,p∧(q∧┓r)等都是合式公式，而pq->r,p->(r->q等不是合式公式。
下邊給出公式層次的定義
定義1.7(1)若公式A是單個的命題變項,則稱A為0層公式
稱是n+1(n≥0)層公式是指下邊情況之一：A=┓B,B是n層公式A=BAC,其中B,C分別為i層和j層公式,且n=max(i,j)A=BVC,其中B,C的層次及n同(b)A=B→C,其中B,C的層次及n同(b)A=BC,其中B,C的層次及n同(b)若公式A的層次為k.則稱A是k層公式
比如,(┓p∧q)→r,((p→┓q))∧((rVs)┓p)分別為3層和4層公式
在命題公式中.因為有命題變項的出現,因此真值是不確定的,用命題常項替換公式中的命題變項叫做解釋.當將公式中出現的全部命題變項都解釋成具體的命題常項以后,公式就成了真值確定的命題.諸如,在公式(pVq)→r中,若將p解釋成:2是質數,q解釋成:3是奇數,r解釋成:√2是無理數,則公式(pVq)→r被解釋成:若2是質數或3是奇數,則2是無理數.這是一個真命題.若p,q的解釋不變,r被解釋為:2是有理數,則(pVq)→r被解釋成:若2是質數或3是奇數,則√2是有理數.這是一個假命題,還可以給出這個公式各類不同的解釋,其結果不是得到真命題就是得到假命題.雖然,將命題變項p解釋成真命題,相當于指定p的真值為1,解釋成假命題,相當于指定p的真值為0
定義1.8設p1,P2,…,Pn是出現在公式A中的全部命題變項,給p1,P2,…,Pn各指定一個真值,稱為對A的一個形參或解釋.若指定的一組值使A為1,則稱這組值為A的成真形參;若使A為0,則稱這組值為A的成假形參
在本書中,對含n個命題變項的公式A的形參采用下列記法
1.若A中出現的命題變項為p1,P2,…,Pn。,A的形參α1α2…αn,是指p1=α1,p2=α2,…,pn=αn
2.若A中出現的命題變項(按字母次序)為p,q,r,…,A的形參α1α2…αn是指p=α1,q=α2,…,最后字母形參αn其中αi,為0或1,i=1,2,...,n
比如,在公式(┓P1∧┓P2∧p3)V(P1∧P2)中,000(P1=0,P2=0,P3=0),110(P1=1,P1=1,P3=0)都是成真形參,而001(P1=0,P2=0,P3=1),011(P1=0,P2=1,p3=1)都是成假形參.在(pA┓q)→r中,011(p=0,q=1,r=1)為成真形參,100(p=1,q=0,r=0)為成假形參.
不難看出,含n(n≥1)個命題變項的公式共有2"個不同的形參
定義1.9將命題公式A在所有形參下取值情況列成表,亦稱A的真值表
構造真值表的具體步驟如下
找出公式中所含的全體命題變項P1,P2,...,pn(若無下角標就按字母次序排列),列舉2n個形參.形參從00…0開始,之后按二補碼乘法依次寫出每位形參,直至11…1為止按從低到高的次序寫出公式的各個層次對應各個斌值估算出各層次的真值,直至最后估算出公式的真值
假如兩個公式A與B的真值表對所有形參最后一列都相同,即最后結果都相同,則稱這兩個真值表相同,而不考慮構造真值表的中間過程
例1.8寫出下述公式的真值表,并求它們的成真形參和成假形參:
(┓p∧q)-->┓r(p^┓q)(q^┓q)┓(p->p)^q^r
解：公式（1）是含3個命題變項的3層合式公式。它的真值表如表1.2所示：
從表1.2可知公式(1)的成假形參為011,其余7個形參都是成真形參
公式(2)是含2個命題變項的3層合式公式,它的真值表如表1.3所示.從表1.3看出該公式的4個形參全是成真形參,即無成假形參。
公式（3）是含3個命題變項的4層合式公式，它的真值表如表1.4所示。不難看出初中物理的所有公式及其變式，該公式的8個形參全是成假形參初中物理的所有公式及其變式，無成真形參。
表1.2~表1.4都是按構造真值表的步驟一步一步地構造下來的,這樣構造真值表不易出錯.假如構造的思路比較淸楚,有些層次可以省略
依據公式在各類形參下的取值情況,可按下列定義將命題公式進行分類
定義1.10設A為任一命題公式
若A在它的各類形參下取值均為真,則稱A是重言式或永真式若A在它的各類形參下取值均為假,則稱A是矛盾式或永假式若A不是矛盾式A是可滿足式
從定義不難看出以下幾點
A是可滿足式的等價定義是:A起碼存在一個成真形參重言式一定是可滿足式,但反之不真.若公式A是可滿足式,且它起碼存在一個成假形參則稱A為非重言式的可滿足式真值表可拿來判別公式的類型若真值表最后一列全為1,則公式為重言式若真值表最后一列全為0,則公式為矛盾式若真值表最后一列中起碼有一個1,則公式為可滿足式
從表1.2~表1.4可知,例1.8中,公式(1)(┓p^g)→┓r為非重言式的可滿足式,公式(2)(p^┓p)(q^┓q)為重言式,而公式(3)┓(P->q)^q^r為矛盾式
從以上的討論可知,真值表不但能確切地給出公式的成真形參和成假形參,并且能判別公式的類型
給定n個命題變項,按合式公式的產生規則,自然可以產生無窮多種方式各異的公式,如今要問:那些公式的真值表是否也有無窮多種不同的情況呢?答案是否定的.n個命題變項共形成2“個不同的形參,而任何公式在每種形參下只能取兩個值,0或1,于是含n個命題變項的公式的真值表只有2種不同的情況,因此必有無窮多個公式具有相同的真值表
例1.9下述各公式均含兩個命題變項p與q,它們中什么具有相同的真值表?
(p→q)Pq┓(p^┓q)(p->q)^(q->p)┓qvp
解構造過程略去不寫,表1.5給出了5個公式的真值表,從表中可看出,(1),(3)具有相同的真值表,(2),(4)具有相同的真值表
設公式A,B中共富含命題變項P1,P2,...,pn而A或B不全含這種命題變項,例如A中不含pi,pi+1,...,pn,i>=2,稱這種命題變項為A的啞元,A的取值與啞元無關,因此在討論A與B是有相同的真值表時,可將A,B都看成含P1,P2,…,Pn的命題公式
例1.10下述公式中,什么具有相同的真值表
(1)p->q
(2)┓qvr
(3)(┓pvq)^((p^r)->p)
(4)(q->r)^(p->p)
解本例中給出的4個公式,總共有3個命題變項P,q和r,r是公式(1)的啞元,P是公式(2)的啞元,討論它們是否有相同的真值表時,均按3個命題變項寫出它們的真值表.表1.6列舉4個公式的真值表,中間過程省略了.從表中看出,(1)與(3)有相同的真值表,(2)與(4)有相同的真值表.