【正文】 為此，我們首先給出命題演算系統(tǒng)中最重要的一條定理，即演繹定理，通過(guò)演繹定理可將在某個(gè)前提S下的證明與P系統(tǒng)中的內(nèi)定理相聯(lián)系起來(lái)。C) // 分離規(guī)則: (3)和(6) 下面利用上述定義和定理來(lái)形式化地討論教材p42中給出的推理定律的正確性。(B174。C)) // 公理[A2] (6). (B174。A)174。C))174。C)) // 前提 (5). (B174。A) // 分離規(guī)則: (1)和(2) (4). (B174。(B174。C)}├(B174。【】證明：{A, B174。4. 易證，若A206。S，且S39。若S39。2. 易證：當(dāng)S = f時(shí)，f├A當(dāng)且僅當(dāng)├A，或者說(shuō)├A就是沒(méi)有前提的證明?！酢咀⒔狻繉?duì)于上述定義，我們需要注意以下幾點(diǎn)：1. S中的公式不一定是P中的公理或內(nèi)定理，也不一定是有限集合。 n)應(yīng)用分離規(guī)則(M)得到。S，或者 (3). Ai是由上述序列中Ai之前的某兩個(gè)公式Aj, Ak(1163。 i 163。4. 教材中所討論的推理是在某種前提下的推理，下面我們?cè)诿}演算系統(tǒng)P中來(lái)定義這種推理。2. 可使用分離規(guī)則和傳遞規(guī)則來(lái)構(gòu)造證明。建立形式系統(tǒng)的方法更符合計(jì)算機(jī)的思維方式，因?yàn)槌绦驈谋举|(zhì)來(lái)說(shuō)也是個(gè)形式系統(tǒng)，計(jì)算機(jī)將輸入變換到輸出也只是符號(hào)的改寫(xiě)，至于程序員所認(rèn)為的程序功能，是程序員賦予程序的解釋?zhuān)@種解釋計(jì)算機(jī)并不理解。A // 分離規(guī)則【注解】通過(guò)以上例子，我們可發(fā)現(xiàn)在構(gòu)造公式的證明中可使用如下方法：1. 可靈活地使用公理，公理中的每個(gè)符號(hào)代表的是無(wú)限多的公式，公理中某個(gè)符號(hào)的所有出現(xiàn)可用某個(gè)公式替換。216。216。(A174。216。216。A) // [1] (2). ├(216。A)174。216。A174。A) // (7). ├(216。216。216。A174。(216。216。A174。A))// [A2] (5). ├(216。216。A)174。216。216。A))174。216。A174。A) // 傳遞規(guī)則 (4). ├(216。216。A)174。A) // [A3] (3). ├(216。216。A)174。216。A174。216。216。(216。216。216。A[2]. ├A174。216。(A174。B) // [A3] (3). ├(216。A))174。B)174。(216。((216。B)【證明】 (1). ├(216。A)174。C) // 分離規(guī)則□ 以后稱(chēng)此定理的[2]為傳遞規(guī)則(Tr)。C) // 分離規(guī)則 (6). ├(A174。B)174。(A174。((A174。(B174。(B174。C)) // [A1] (2). ├(B174。(A174。對(duì)于[2]，證明如下： (1). ├(B174。C，則├A174。B，則├B [2]. 若├A174。A) // 公理[A1] (5). ├(A174。A)) // 分離規(guī)則(M)及(1)和(2) (4). ├(A174。A))174。A)) // 公理[A2] (3). ├((A174。A))174。((A174。A)174。A) // 公理[A1] (2). ├(A174。((B174。A) // 分離規(guī)則(M)及(1)和(2)【】設(shè)A是P中的公式，證明：├(A174。B)174。(A174。((A174。(B174。(B174。(A174。【】設(shè)A, B是P中的公式，證明：├(A174。 4. P的每個(gè)公理都是P中的內(nèi)定理。 i 163。Ai}。 2. 所謂的用兩個(gè)公式Aj, Ak應(yīng)用分離規(guī)則(M)得到，是指{Aj, Ak} = {Aj, Aj174。此時(shí)A1, A2, …, An稱(chēng)為An的一個(gè)證明，而An稱(chēng)為P的一個(gè)內(nèi)定理，記為├An。 j, k 163。 i 163。同樣分離規(guī)則也是一個(gè)模式。C)174。B)174。(((B174。(B174。C得到： (((B174。不是系統(tǒng)P的符號(hào)，只不過(guò)是為了使用方便而引入的符號(hào)。、218。(B174。B)代表((A174。(216。((216。B) (A217。B)代表((216。和171。這使得系統(tǒng)P比較簡(jiǎn)單，但也失去了使用另外三個(gè)聯(lián)結(jié)詞217。B)可得到B□ 【注解】關(guān)于以上定義，需要注意以下幾點(diǎn)： 1. 在系統(tǒng)P中只使用聯(lián)結(jié)詞216。(B174。(216。C)) [A3]. (((216。B)174。C))174。A)) [A2]. ((A174。 3. P的公理有如下三類(lèi)： [A1]. (A174。A)也是公式 [3]. 若A和B是公式，則(A174。、174。定理就是從公理出發(fā)，使用規(guī)則能夠構(gòu)造出有效證明的公式，形式系統(tǒng)就是研究能夠得到什么定理。當(dāng)然在構(gòu)造形式系統(tǒng)的時(shí)候，公理的選擇是一定的外在依據(jù)的。 一個(gè)形式系統(tǒng)包括符號(hào)表、公式、公理及規(guī)則，符號(hào)表定義形式系統(tǒng)所使用的所有符號(hào)，公式是符號(hào)表上字符串，公式定義哪些字符串是形式系統(tǒng)所研究的合法對(duì)象。前提本身的正確性要在賦予形式系統(tǒng)一定的解釋的基礎(chǔ)上才能確定，這種解釋可以說(shuō)是形式系統(tǒng)的語(yǔ)義。7. 命題演算系統(tǒng) 命題演算系統(tǒng)是研究利用命題邏輯公式進(jìn)行推理的形式系統(tǒng)。 關(guān)于極大項(xiàng)、主合取范式等有關(guān)內(nèi)容學(xué)生根據(jù)教材自學(xué)。q217。r)218。q217。r)218。216。r)218。p217。r)218。q217。(216。q217。p217。r)218。q217。p217。(p217。r)因此(p174。216。r)218。r)展開(kāi)為(p217。216。p217。r)218。q217。r)218。p217。r)218。r) q展開(kāi)為(p217。q217。p217。r)218。q217。(216。q217。p217。r)218。p217。r)，將其中每個(gè)簡(jiǎn)單合取式展開(kāi)為含有所有命題變?cè)臉O小項(xiàng)的析?。? (216。q218。r)的一個(gè)析取范式為(216。q)218。r)。(p217。q217。(p217。q217。(216。216。p217。216。p217。r)218。p217。r)218。216。r)218。r)的主析取范式為(p217。q)217。r)因此(216。p217。r)218。r)展開(kāi)為(p217。216。p217。r)218。p217。216。q217。(p217。q217。r)，我們將其中的每個(gè)簡(jiǎn)單合取式展開(kāi)為含有所有命題變?cè)臉O小項(xiàng)的析?。?p217。p)218。(q217。r)的一個(gè)析取范式是(p217。q)217。r)的主析取范式【解答】(1)(216。q)218。(p174。p174。 [3] 消除重復(fù)出現(xiàn)的命題變?cè)蛎}變?cè)姆穸?，矛盾式及重?fù)出現(xiàn)的極小項(xiàng)，并將每個(gè)極小項(xiàng)的命題變?cè)蚱浞穸ò聪聵?biāo)順序或字典順序排列。216。p)218。 [2] 如果該析取范式的某個(gè)簡(jiǎn)單合取式A中既不含某個(gè)命題變?cè)猵，也不含它的否定216。 【】任何命題公式存在唯一的主析取范式。q217。216。r對(duì)應(yīng)101，記為m5 p217。216。216。216。q217。r對(duì)應(yīng)010，記為m2 216。q217。r對(duì)應(yīng)001，記為m1 216。216。r對(duì)應(yīng)000，記為m0 216。q217。p217。q對(duì)應(yīng)10，記為m2 p217。q對(duì)應(yīng)01，記為m1 p217。q對(duì)應(yīng)00，記為m0 216。p217。若在極小項(xiàng)中，將命題變?cè)脑螌?duì)應(yīng)1，否定對(duì)應(yīng)0，則每個(gè)極小項(xiàng)唯一地對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)，該二進(jìn)制數(shù)的每一位正是使該極小項(xiàng)的真值為1的真值賦值。 極小項(xiàng)是特殊的簡(jiǎn)單合取式。 注意：一個(gè)命題公式的合取范式和析取范式不具有唯一性。(p217。p)218。(p217。r) 顯然(p174。p218。p)217。p218。r)219。q)218。(216。(p217。r)的合取范式： (p174。q)218。r)。(216。r)的合取范式為(p218。q)217。p)是矛盾式顯然(216。r) // (p217。p)218。(q217。(p217。(q217。216。r)218。p)218。(p217。p218。q)217。r) // 蘊(yùn)涵等值式 219。(216。p218。(216。(p174。p174。(p174。p174。(p217。r)的析取范式和合取范式 (2). 求(p174。q)217?！尽壳竺}公式的析取范式和合取范式 (1). 求(216。對(duì)217。對(duì)218。A和德摩爾根律將否定放到命題符號(hào)前。216。和218。使得公式中只含有聯(lián)結(jié)詞216。B)消除公式中的聯(lián)結(jié)詞174。(A218。A218。B)219。A218。B)219。【】（范式存在定理）任意命題公式都存在與之等值的析取范式與合取范式。【】一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合取式都是矛盾式。216。(216。r218。(q218。q), (p218。p218。q)217。216。(216。r217。(q217。q), (p217。p217。q)218。析取范式和合取范式統(tǒng)稱(chēng)為范式(normal form)。r)為三個(gè)文字的簡(jiǎn)單合取式【】一個(gè)簡(jiǎn)單析取式是永真式當(dāng)且僅當(dāng)它同時(shí)含一個(gè)命題符號(hào)及其否定，一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含一個(gè)命題符號(hào)及其否定。q217。(216。r)為三個(gè)文字的簡(jiǎn)單析取式 (3) p217。q218。(216。q等為文字，也是一個(gè)文字的簡(jiǎn)單析取式和簡(jiǎn)單合取式 (2) p218。僅由有限個(gè)文字構(gòu)成的合取式稱(chēng)為簡(jiǎn)單合取式。 □6. 命題公式的范式 【】將命題符號(hào)（代表命題變?cè)蛎}常量）或命題符號(hào)的否定統(tǒng)稱(chēng)為文字(literal)。}不是聯(lián)結(jié)詞的完全集。, 218?！酢尽縶174。A)218。B)219。(216。((216。B)219。, 218。A)218。B)219。(216。((216。B)219。, 217。(216。((216。B)219。A)174。B)219。和174。, 174。}都是聯(lián)結(jié)詞的完全集。}和{216。}, {216?！?【】{216。A2)的真值為1，所以A與A1等值，而按歸納假設(shè)有A1的真值為f1(t1, t2, …, tk)，即為f(x1, x2, …, xk, 0)。pk+1)174。即要證對(duì)命題變?cè)猵1, p2, …, pk, pk+1的一個(gè)真值賦值t1, t2, …, tk, tk+1時(shí)，A的真值是f(t1, t2, …, tk, tk+1)。(pk+1174。pk+1)174。的k元命題公式來(lái)表示，設(shè)它們分別可由A1和A2表示，且假定A1和A2中的k個(gè)命題變?cè)獮閜1, p2, …, pk。、218。設(shè)f(x1, x2, …, xk, xk+1)是一個(gè)k+1元真值函數(shù)，定義如下兩個(gè)k元真值函數(shù)： f1(x1, x2, …, xk) = f(x1, x2, …, xk, 0) f2(x1, x2, …, xk) = f(x1, x2, …, xk, 1)由歸納假設(shè)知f1和f2都可由只含216。p)來(lái)表示，因此定理成立。p和p218。(216。對(duì)真值函數(shù)的元數(shù)n進(jìn)行歸納證明。和174。 【證明】、217。, 174。, 217?，F(xiàn)在的問(wèn)題是，是否所有的真值函數(shù)都可使用常用的這5個(gè)真值聯(lián)結(jié)詞來(lái)表示呢？【】設(shè)W是聯(lián)結(jié)詞的一個(gè)集合，稱(chēng)W為聯(lián)結(jié)詞的一個(gè)完全集，如果任意真值函數(shù)f都可用僅含W中聯(lián)結(jié)詞的命題公式A來(lái)表示，即對(duì)A中命題變?cè)娜我庖粋€(gè)真值賦值t1, t2, …, tn，A在t1, t2, …, tn下的真值為f(t1, t2, …, tn)。1, 1174。1, 1174。0, 1174。0, 1174。{0, 1}是一個(gè)n元真值函數(shù)，則可如下定義一個(gè)n元真值聯(lián)結(jié)詞Nf : 對(duì)于n個(gè)命題變?cè)猵1, p2, …, pn，命題公式Nf(p1, p2, …, pn)在真值賦值函數(shù)t1, t2, …, tn下的真值為f(t1, t2, …, tn)。(1, 1) = 1 反過(guò)來(lái)，一個(gè)真值函數(shù)就可看成一個(gè)真值聯(lián)結(jié)詞。(0, 1) = 0, f171。(1, 1) = 1 f171。(0, 1) = 1, f174。(1, 1) = 1 f174。(0, 1) = 1, f218。(1, 1) = 1 f218。(0, 1) = 0, f217。則都是二元真值函數(shù)： f217。、174。(1) = 0而聯(lián)結(jié)詞217。實(shí)際上一個(gè)一元真值函數(shù)：f216。{0, 1}就稱(chēng)為一個(gè)n元真值函數(shù)。An) 【證明】對(duì)n實(shí)施數(shù)學(xué)歸納法，[2]得到?！?18。(216。 (216?！?17。(A1217。(216。A2)217。A1)217。An) 219。A2218。r) // 蘊(yùn)涵等值式(4)(6)留作練習(xí) □【】德摩爾根律的推廣： (1). 216。q)218。的交換律和結(jié)合律 219。p218。q)218。 (216。r) // 218。p)218。p)218。r) // 蘊(yùn)涵等值式 219。p)218。r)) 219。r)) // 蘊(yùn)涵等值式(5). (p174。r)217。r)) // 分配律與交換律 219。(216。p218。r) // 德摩爾根律 219。216。 ((216。q)218。 (216。q)174。q)174。r) // 德摩爾根律，反向運(yùn)用 219。(p217。的結(jié)合律 219。q)218。p218。r)) // 蘊(yùn)涵等值式 219。(216。 (216。(q174。 (216。(q174。r) // 217。q217。r // 德摩爾根律 219。(216。r // [12]：蘊(yùn)涵等值式 219。p218。 (216。q)174。 ((216。q)174?？梢钥吹缴鲜龅戎凳街饕顷P(guān)于蘊(yùn)涵的等值式，[12]將蘊(yùn)涵化成只出現(xiàn)與、或、非的公式，再來(lái)驗(yàn)證它們的相等。的兩邊在任何真值賦值下都有相同的真值，從而完成上述等值式的驗(yàn)證。(p174。 ((p174。(q217。(p174。 ((p174。(q218。(q174。 ((p174。q)174。(q174。 ((p174。q)174。q)174。r)) 219。r)(2). (p174。q217。r) 219?！尽框?yàn)證下列等值式(1). ((p174。B)) 219。A，這與第二個(gè)吸收律公式(A217。B)) 219。A218。A217。216。(216。B))的對(duì)偶公式是(216。 A，其中(A218。(A217。 (Bop)216。 216。 216。則：(Aop)216。 216。 B當(dāng)且僅當(dāng)216。A) 219。 (Bop)216。 B則(Aop)216。 216。) [2]. (Aop)216。 216。A)216。 216。【】設(shè)公式A是任意的限制性公式，有： [1]. (216。 (A216。 r)顯然有(Aop)216。 (216。(((216。 r), (A216。 (216。(((216。 r) (2). A216。(216。(((216。r)), (Aop)216。q)218。r))，則： (1). Aop = 216。q)217。例如： 【，續(xù)】設(shè)公式A = 216。)op表示對(duì)A做一次對(duì)偶操作得到Aop，然后再求Aop的內(nèi)否式，得到的公式與先求A的內(nèi)否式，然后再做對(duì)偶操作得到的公式完全一樣，用代數(shù)學(xué)的術(shù)語(yǔ)來(lái)說(shuō)，就是這兩種操作可交換。 186。 A表示對(duì)A