【文章內(nèi)容簡介】 沒有園括號，(p 217。 q 217。 r)不是公式，實際上，每個命題聯(lián)結符都會對應一對園括號。顯然(pq174。r)、(q174。(r217。p)等都不是公式。 【】設R是某個性質，如果有： [1]. 對于所有的原子項p，都滿足性質R；[2]. 如果對任意的公式A和B都滿足性質R，就有(216。A)、(A217。B)、(A218。B)、(A174。B)和(A171。B)也滿足性質R。 那么，所有的公式A就都滿足性質R。 □ 該定理的證明類似數(shù)學歸納法的證明。 【】命題公式A的復雜程度deg(A)定義為： [1]. 如果A是原子項，則deg(A) = 0； [2]. deg(216。A) = deg(A) + 1。 [3]. deg(A * B) = max(deg(A), deg(B)) + 1，其中*代表217。、218。、174。、171。之一。 □ 。只不過我們在這里給出的是遞歸定義。使用歸納法，我們可證明下面定理：【】deg(A)小于等于命題公式A中的命題聯(lián)結符號的數(shù)目。 【證明】根據(jù)命題公式A的結構進行歸納證明： 1. 歸納基：如果A是原子項，(A) = 0，顯然定理成立。 2. 歸納步：假設定理對于命題公式A和B成立（歸納假設），記命題公式A中的命題聯(lián)結符號數(shù)為Sym(A)，即有deg(A) 163。 Sym(A)和deg(B) 163。 Sym(B)。那么由于deg(216。A) = deg(A) + 1，而Sym(216。A) = Sym(A) + 1，所以定理對于216。A也成立。同樣由于deg(A * B) = max(deg(A), deg(B)) + 1，而Sym(A * B) = Sym(A) + Sym(B) + 1，因而有deg(A * B)163。 Sym(A * B)，從而定理對所有的命題公式都成立。 □ 【】任意命題邏輯公式A中出現(xiàn)相等數(shù)目的左右園括號，實際上，左右園括號的個數(shù)都等于A中的命題聯(lián)結符號數(shù)。 □ 【】任意命題邏輯公式A具有下列6種形式之一，且只具有其中一種形式： [1]. A為原子項； [2]. (216。A) [3]. (A217。B) [4]. (A218。B) [5]. (A174。B) [6]. (A171。B) □ ： 1. 任意命題公式必然具有上述6中形式之一； 2. 這6中形式都互不相同； 3. 如果(216。A)與(216。A1)相同，則必有A與A1相同； 4. 如果(A * B)與(A1 * B1)相同，則必有A與A1相同，且B與B1相同。實際上每個命題公式的最左邊都是左園括號，如果從第二個符號不是左園括號，那么這個公式只有一個命題聯(lián)結符。否則找與第二個左園括號配對的右園括號，從而將命題公式劃分為這樣的形式：((…) * (…))，如果原來的命題公式為根的話，那么左右兩邊的兩個命題公式分別為它的左右子樹了，而且對這兩個公式可作類似的分析，最后到原子項。 在后面，為了書寫方便起見，我們省略最外邊的括號，并規(guī)定各個命題聯(lián)結符的優(yōu)先級別為216。大于217。，217。大于218。，218。大于174。，174。大于171。，從而可省略命題公式中一些不必要的園括號，：p 218。 q 174。 216。p 171。 q 217。 r。不過在后面我們書寫公式的原則是盡量簡便，但又能讓讀者容易理解。而有關命題公式的性質的討論。 上面討論的命題公式的語法結構，下面討論命題公式的賦值?！尽?對命題公式的一次真值賦值t是從所有命題變量所組成的集合到集合{0, 1}的函數(shù)。實際上，對于某個命題公式A來說，我們只關心t在A中的命題變量上的值。這里我們假定存在一個所有命題變量所組成的集合U，或者說我們所有命題公式中的變量都取之于集合U，我們記命題公式A中的所有命題變量所組成的集合為Var(A)。設有一個真值賦值t : U174。{0, 1}，而對于命題公式A的真值賦值來說，我們只關心t在Var(A)上的值?！尽繉τ诿}公式A = ((p 218。 q) 174。 ((216。p) 171。 (q 217。 r)))，有： Var(A) = {p, q, r}這里不妨假定U = Var(A)，真值賦值就是一個函數(shù)t : {p, q, r}174。{0, 1}，例如可令： t(p) = 0, t(q) = 1, t(r) = 0【】命題公式A在真值賦值t : U174。{0, 1}下的真值t(A)遞歸定義如下： [1]. 如果命題公式A是一個命題常量p，則如果p為真，t(A) = 1，否則t(A) = 0； [2]. 如果命題公式A是一個命題變量p，則t(A) = t(p) [3]. 若t(A) = 0則t(216。A) = 1，否則t(216。A) = 0。 [4]. 若t(A) = t(B) = 1，則t(A217。B) = 1，否則t(A217。B) = 0。 [5]. 若t(A) = t(B) = 0，則t(A218。B) = 0，否則t(A218。B) = 1。 [6]. 若t(A) = 0或者t(B) = 1，則t(A174。B) = 1，否則t(A174。B) = 0。 [7]. 若t(A) = t(B)，則t(A171。B) = 1，否則t(A171。B) = 0?！?，續(xù)】對于命題公式A = ((p 218。 q) 174。 ((216。p) 171。 (q 217。 r)))，及真值賦值函數(shù)t： t(p) = 0, t(q) = 1, t(r) = 0有： 1. t(p) = 0, t(q) = 1。 2. t(p 218。 q) = 1。 // [5] 4. t(216。p) = 1。 // [3] 5. t(r) = 0。 6. t(q 217。 r) = 0。 // [4] 7. t((216。p) 171。 (q 217。 r)) = 0。 // [7] 8. t((p 218。 q) 174。 ((216。p) 171。 (q 217。 r))) = 0。 // [6] 因此命題公式A在上述真值賦值下的真值t(A)是0。 不難看出。，對于命題公式的真值，可根據(jù)該命題公式的生成步驟來得到。命題公式的真值只與命題公式中所出現(xiàn)的命題變量的真值賦值有關，如果命題公式中含有n個命題變量，則對這些命題變量的真值賦值共有2n種不同情況，可通過一個表，列出在這所有情況下命題公式的真值，這種表稱為該命題公式的真值表，例如上述命題公式A的真值表為：pqr(p218。q)(216。p)(q217。r)((216。p)171。(q217。r))((p218。q)174。 ((216。p)171。(q217。r)))0000100100101001010110000111111110010011101100111101001111110100【】如果命題公式A在任意的真值賦值函數(shù)t : U174。{0, 1}下的真值t(A)都為1,則稱命題公式A為永真式(tautology)（或稱重言式）；如果命題共A在任意的真值賦值函數(shù)下的真值都為0，則稱A為矛盾式(contradiction)；如果A不是矛盾式，則稱為可滿足式。 【】根據(jù)命題公式A = ((p 218。 q) 174。 ((216。p) 171。 (q 217。 r)))的真值表，我們知該命題公式是可滿足式，但不是永真式。而公式B = ((p174。(q218。p))218。r)是永真式，其真值表為：pqr(q218。p)(p174。(q218。p))((p174。(q218。p))218。r)000011001011010111011111100111101111110111111111而公式(((216。(p174。q))217。q)217。r)（教材14頁簡寫為216。(p174。q)217。q217。r）是矛盾式，其真值表為：pqr(p174。q)(216。(p174。q))((216。(p174。q))217。q)(((216。(p174。q))217。q)217。r)00010000011000010100001110001000100101010011010001111000【】我們使用符號S來表示一組命題公式所構成的集合。定義S在真值賦值函數(shù)t : U174。{0, 1}下的真值t(S)為：t(S) = 1當且僅當對S中任意公式A有t(A) = 1，否則定義t(S) = 0(注意只要S中存在某個公式A使得t(A) = 0，就有t(S) = 0)。說S是可滿足的，如果存在某個真值賦值函數(shù)t使得t(S) = 1，這時稱t滿足S。 【】設S是一組命題公式的集合，說命題公式A是以S為前提的永真式，如果滿足對任意滿足S的真值賦值函數(shù)t都有t(A) = 1，這時我們記為S╞A。 ，如果S為空集，則f╞A表示A為永真式，因為對于空集S來說，顯然任意的真值賦值函數(shù)t都滿足它（因為S中沒有命題公式），從而f╞A意味著對任意的真值賦值函數(shù)t都有t(A) = 1，即A為永真式。4. 等值演算 【】當S = {A1, A2, …, An}時，我們也記S╞A為A1, A2, …, An╞A。如果有A╞B且B╞A，則稱命題公式A與B等值，記為A219。B。 實際上公式A與B等值記為A╞╡B會更準確些，但教材采用了符號A219。B，為了不會過于混淆，我們也使用這種記號。實際上，A219。B就意味著對任意的真值賦值函數(shù)t有t(A) = 1當且僅當t(B) = 1，也就是說對任意的t有t(A) = t(B)。，即有下述定理： 【】A219。B當且僅當A171。B是永真式。 □ 使用真值表，不難證明下面的定理： 【】設A, B, C是任意的命題公式，有： [1]. 雙重否定律： A219。 (216。(216。A)) [2]. 等冪律： A219。(A218。A) A219。(A217。A) [3]. 交換律： (A218。B) 219。 (B218。A) (A217。B) 219。 (B217。A) [4]. 結合律： ((A218。B)218。B) 219。 (A218。(B218。B)) ((A217。B)217。B) 219。 (A217。(B217。B)) [5]. 分配律： (A218。(B217。C)) 219。 ((A218。B)217。(A218。C)) (A217。(B218。C)) 219。 ((A217。B)218。(A217。C)) [6]. 德摩根律： (216。(A218。B)) 219。 ((216。A)217。(216。B)) (216。(A217。B)) 219。 ((216。A)218。(216。B)) [7]. 吸收律： (A218。(A217。B)) 219。 A (A217。(A218。B)) 219。A [8]. 零律： (A218。1) 219。1 (A217。0) 219。 0 [9]. 同一律： (A218。 0) 219。A (A217。1) 219。 A [10]. 排中律： (A218。(216。A)) 219。 1 [11]. 矛盾律： (A217。(216。A)) 219。 0 [12]. 蘊涵等值式： (A174。B) 219。 ((216。A)218。B) [13]. 等價等值式： (A171。B) 219。 ((A174。B)217。(B174。A)) [14]. 假言易位： (A174。B) 219。 ((216。B)174。(216。A)) [15]. 等價否定等值式： (A171。B) 219。 ((216。A)171。(216。B)) [16]. 歸謬論： ((A174。B)217。(A174。(216。B))) 219。 (216。A) □ 要注意的是，上述定理中的0代表真值為0的任意命題常量，而1代表真值為1的任意命題常量。 由于命題聯(lián)結符號217。和218。都滿足結合律，因此我們可有如下的簡寫： A1217。A2217?！?17。An A1218。A2218?！?18。An 根據(jù)以上簡寫，：【】[1]. A1, A2, …, An╞A當且僅當f╞((A1217。A2217?！?17。An)174。A)。 [2]. A1, A2, …, An╞A當且僅當f╞((A1174。(A2174。(…(An174。A)…))。 □【】設有A219。A39。和B219。B39。，則有： [1]. (216。A)219。(216。A39。) [2]. (A217。B)219。(A39。217。B39。) [3]. (A218。B)219。(A39。218。B39。) [4]. (A174。B)219。(A39。174。B39。) [5]. (A171。B)219。(A39。171。B39。) □ ，不難證明下面的置換規(guī)則： 【】設有B219。C，而A39。是命題公式A通過使用C替換A中出現(xiàn)的某些B（不需要是替換所有的B）而得到的命題公式，則有A219。A39?！咀C明】對命題公式A的結構進行歸納。首先如果B = A，則有C = A39。，從而有A219。A39。 歸納基：如果A是命題變量和命題常量，那么必有B = A，因此定理成立。 歸納步：，命題公式A必為如下5種形式之一：216。A1, A1217。A2, A1218。A2, A1174。A2, A1171。A2。設A的形式為216。A1，如果B = A則定理成立，否則必有B出現(xiàn)A1中，將A1中的B用C替換后得到的為A139。，按歸納假設有A1 = A139。， = 216。A139。定理成立。若A的形式為A1 * A2，則如果B = A則定理成立，否則必有B出現(xiàn)在A1或A2中，或同時出現(xiàn)在這兩者中。設將A1中的B用C替換后得到的為A139。，而將A2中的B用C替換后得到的為A239。，按歸納假設有A1219。A139。和A2 219。A239。，*A2219。A1*A2，即定理成立。 □ 【】如果命題公式A中只出現(xiàn)命題變量、命題常量、命題聯(lián)結符號216。、217。和218。則稱為限制性（命題）公式。定義：[1]. 對于限制性公式A，將其中的命題聯(lián)結符號217。換成218。，命題聯(lián)結符號218。換成217。得到的公式稱為A的對偶公式(dual formula)，記為Aop。[2]. 對于限制性公式A，將其中出現(xiàn)的所有原子項（命題變量或命題常量）p換成216。p得到的公式稱為A的內(nèi)否式，記為A216。 【】設公式A = 216。((p218。q)217。(216。r))，則： (1). A的對偶式Aop = 216。((p217。q)218。(216。r)) (2). A的內(nèi)否式A216。 = 216。(((216