離散數(shù)學(xué)電子教材

1、-PAGE . z.第1章 命題邏輯邏輯是研究人的思維的科學(xué)，包括辯證邏輯和形式邏輯。辯證邏輯是研究反映客觀世界辯證開展過程的人類思維的形態(tài)的。形式邏輯是研究思維的形式構(gòu)造和規(guī)律的科學(xué)，它撇開具體的、個(gè)別的思維內(nèi)容，從形式構(gòu)造方面研究概念、判斷和推理及其正確聯(lián)系的規(guī)律。數(shù)理邏輯是用數(shù)學(xué)方法研究推理的形式構(gòu)造和推理的規(guī)律的數(shù)學(xué)學(xué)科。所謂的數(shù)學(xué)方法也就是用一套有嚴(yán)格定義的符號(hào)，即建立一套形式語(yǔ)言來(lái)研究。因此數(shù)理邏輯也稱為符號(hào)邏輯。數(shù)理邏輯的根底局部是命題邏輯和謂詞邏輯。本章主要講述命題邏輯，謂詞邏輯將在第2章進(jìn)展討論。1.1命題及其表示1.1.1命題的根本概念數(shù)理邏輯研究的中心問題是推理Infer

2、ence)，而推理就必然包含前提和結(jié)論，前提和結(jié)論都是表達(dá)判斷的陳述句，因而表達(dá)判斷的陳述句就成為推理的根本要素。在數(shù)理邏輯中，將能夠判斷真假的陳述句稱為命題。因此命題就成為推理的根本單位。在命題邏輯中，對(duì)命題的組成局部不再進(jìn)一步細(xì)分。定義1.1.1能夠判斷真假的陳述句稱為命題Proposition。命題的判斷結(jié)果稱為命題的真值，常用 T(True)或1表示真，F(xiàn)(False)或0表示假。真值為真的命題稱為真命題，真值為假的命題稱為假命題。從上述的定義可知，判定一個(gè)句子是否為命題要分為兩步：一是判定是否為陳述句，二是能否判定真假，二者缺一不可。判斷以下句子是否為命題是中國(guó)的首都。請(qǐng)勿吸煙！雪是

3、黑的。明天開會(huì)嗎？*+y=5。我正在說謊。9+512。1+101=110。今天天氣多好啊！別的星球上有生物。解 在上述的十個(gè)句子中，2、9為祈使句，4為疑問句，5、6雖然是陳述句，但5沒有確定的真值，其真假隨*、y取值的不同而有改變，6是悖論(Parado*)即由真能推出假，由假也能推出真，因而2、4、5、6、9均不是命題。1、3、7、8、10都是命題，其中10雖然現(xiàn)在無(wú)法判斷真假，但隨著科技的進(jìn)步是可以判定真假的。需要進(jìn)一步指出的是，命題的真假只要求它有就可以，而不要求立即給出。如例 的81+101=110，它的真假意義通常和上下文有關(guān)，當(dāng)作為二進(jìn)制的加法時(shí)，它是真命題，否則為假命題。還有的

4、命題的真假不能馬上給出，如例1.1.1 的10，但它確實(shí)有真假意義。命題分類根據(jù)命題的構(gòu)造形式，命題分為原子命題和復(fù)合命題。定義不能被分解為更簡(jiǎn)單的陳述語(yǔ)句的命題稱為原子命題(Simple Proposition )。由兩個(gè)或兩個(gè)以上原子命題組合而成的命題稱為復(fù)合命題(pound Proposition )。例如，例中的命題全部為原子命題，而命題小王和小李都去公園。是復(fù)合命題，是由小王去公園。與小李去公園。兩個(gè)原子命題組成的。命題標(biāo)識(shí)符定義表示原子命題的符號(hào)稱為命題標(biāo)識(shí)符(Identifier)。通常用大寫字母A，B，C，P，Q，等表示命題，如P：今天下雨。命題標(biāo)識(shí)符依據(jù)表示命題的情況，分為命

5、題常元和命題變?cè)Ｒ粋€(gè)表示確定命題的標(biāo)識(shí)符稱為命題常元或命題常項(xiàng)(Propositional constant)；沒有指定具體內(nèi)容的命題標(biāo)識(shí)符稱為命題變?cè)蛎}變項(xiàng)(Propositional Variable)。命題變?cè)恼嬷登闆r不確定，因而命題變?cè)皇敲}。只有給命題變?cè)狿一具體的命題取代時(shí)，P有了確定的真值，P才成為命題。習(xí)題1.1判斷以下語(yǔ)句是否為命題，假設(shè)是，指出其真值。外面下雨嗎？7能被2 整除。2*+34。2燕子北回，春天來(lái)了。1設(shè)P：雪是黑色的。Q：2+24。則1可表示為PQ，其真值為T。2設(shè)R：燕子北回。S：春天來(lái)了。則2可表示為R S，其真值為T。與前面的聯(lián)結(jié)詞一樣，條件聯(lián)

6、結(jié)詞和雙條件聯(lián)結(jié)詞連接的兩個(gè)命題之間可以沒有任何的因果聯(lián)系，只要能確定復(fù)合命題的真值即可。習(xí)題1.21指出以下命題的真值：假設(shè)2+24，則太陽(yáng)從西方升起。假設(shè)a，則aA。 胎生動(dòng)物當(dāng)且僅當(dāng)是哺乳動(dòng)物。 指南針永指北方，除非它旁邊有磁鐵。除非ABCD 是平行四邊形,否則它的對(duì)邊不都平行。2令P：天氣好。Q：我去公園。請(qǐng)將以下命題符號(hào)化。如果天氣好，我就去公園。只要天氣好，我就去公園。只有天氣好，我才去公園。我去公園，僅當(dāng)天氣好。 或者天氣好，或者我去公園。天氣好，我去公園。1.3命題公式與翻譯命題公式上一節(jié)介紹了5種常用的邏輯聯(lián)結(jié)詞，利用這些邏輯聯(lián)結(jié)詞可將具體的命題表示成符號(hào)化的形式。對(duì)于較為復(fù)

7、雜的命題，需要由這5種邏輯聯(lián)結(jié)詞經(jīng)過各種相互組合以得到其符號(hào)化的形式，則怎樣的組合形式才是正確的、符合邏輯的表示形式呢？定義1單個(gè)的命題變?cè)敲}公式。2如果是命題公式，則也是命題公式。3如果、是命題公式，則(),), ()和()也是命題公式。 4當(dāng)且僅當(dāng)能夠有限次地應(yīng)用1、2、3所得到的包含命題變?cè)?、?lián)結(jié)詞和括號(hào)的符號(hào)串是命題公式又稱為合式公式，或簡(jiǎn)稱為公式。上述定義是以遞歸的形式給出的，其中1稱為根底，2、3稱為歸納，4稱為界限。由定義知,命題公式是沒有真假的，僅當(dāng)一個(gè)命題公式中的命題變?cè)毁x以確定的命題時(shí)，才得到一個(gè)命題。例如在公式中，把命題雪是白色的。賦給，把命題2+24。賦給，則公式

8、被解釋為假命題；但假設(shè)的賦值不變，而把命題2+2=4。賦給，則公式被解釋為真命題。定義中的符號(hào),不同于具體公式里的、等符號(hào)，它可以用來(lái)表示任意的命題公式。例，等都是命題公式，而，等都不是命題公式。為了減少命題公式中使用括號(hào)的數(shù)量，規(guī)定：1邏輯聯(lián)結(jié)詞的優(yōu)先級(jí)別由高到低依次為、。2具有一樣級(jí)別的聯(lián)結(jié)詞，按出現(xiàn)的先后次序進(jìn)展計(jì)算，括號(hào)可以省略。3命題公式的最外層括號(hào)可以省去。也可以寫成，也可寫成，也可寫成，而中的括號(hào)不能省去。定義 設(shè)是命題公式的一局部，且也是命題公式，則稱為的子公式。例如及都是公式的子公式；、及都是公式的子公式。 命題的符號(hào)化 有了命題公式的概念之后，就可以把自然語(yǔ)言中的一些命題翻

9、譯成命題邏輯中的符號(hào)化形式。把一個(gè)文字描述的命題相應(yīng)地寫成由命題標(biāo)識(shí)符、邏輯聯(lián)結(jié)詞和圓括號(hào)表示的命題形式稱為命題的符號(hào)化或翻譯。命題符號(hào)化的一般步驟：1明確給定命題的含義；2找出命題中的各原子命題，分別符號(hào)化。3使用適宜的邏輯聯(lián)結(jié)詞，將原子命題分別連接起來(lái)，組成復(fù)合命題的符號(hào)化形式。把命題符號(hào)化，是不管具體內(nèi)容而突出思維形式的一種方法。注意在命題符號(hào)化時(shí)，要正確地分析和理解自然語(yǔ)言命題，不能僅憑文字的字面意思進(jìn)展翻譯。 *三或李四都可以做這件事。設(shè)：*三可以做這件事。：李四可以做這件事。則命題符號(hào)化為：，而不是。 1只有你走，我才留下。這個(gè)命題的意義也可以理解為：如果我留下了，則你一定走了。設(shè)

10、：你走。：我留下。則命題符號(hào)化為：。與原命題類似的命題如：僅當(dāng)你走我才留下。我留下僅當(dāng)你走。當(dāng)我留下你得走。注意：在一般的命題表述中，僅當(dāng)是必要條件，譯成條件命題時(shí)其后的命題是后件，而當(dāng)是充分條件，譯成條件命題時(shí)其后的命題是前件。2僅當(dāng)天不下雨且我有時(shí)間，我才上街。設(shè)：天下雨。：我有時(shí)間。：我上街。命題符號(hào)化為：。3你將失敗，除非你努力。這個(gè)命題的意義可以理解為：如果你不努力，則你將失敗。設(shè)：你努力。：你失敗。則命題符號(hào)化為：。含有除非的命題，非是充分條件，譯成條件命題時(shí)，非是條件的前件。4中沒有元素，就是空集。設(shè)：中有元素。：是空集。則命題符號(hào)化為：5*三與李四是表兄弟。此命題是一個(gè)原子命題

11、，與是表兄弟。表示兩個(gè)對(duì)象之間的關(guān)系。*三是表兄弟。及李四是表兄弟。都不是命題。所以上述命題只能符號(hào)化為的形式。其中：*三與李四是表兄弟。例 將以下命題符號(hào)化。如果明天早上下雨或下雪，則我不去學(xué)校。如果明天早上不下雨且不下雪，則我去學(xué)校。如果明天早上不是雨夾雪，則我去學(xué)校。當(dāng)且僅當(dāng)明天早上不下雨且不下雪時(shí)，我才去學(xué)校。設(shè)：明天早上下雨。：明天早上下雪。：我去學(xué)校。符號(hào)化為：符號(hào)化為：符號(hào)化為：符號(hào)化為：例將以下命題符號(hào)化。如果小王和小*都不去，則小李去。如果小王和小*不都去，則小李去。設(shè)：小王去。：小*去。：小李去。符號(hào)化為：符號(hào)化為：或例 將以下命題符號(hào)化。1說離散數(shù)學(xué)無(wú)用且枯燥無(wú)味是不對(duì)的

12、。2假設(shè)天不下雨，我就上街；否則在家。對(duì)于1，設(shè)：離散數(shù)學(xué)是有用的。：離散數(shù)學(xué)是枯燥無(wú)味的。則命題符號(hào)化為：。對(duì)于2，設(shè)：天下雨。：我上街。：我在家。則命題符號(hào)化為：。通過上述的例題可以看出，要正確地將自然語(yǔ)言中的聯(lián)結(jié)詞翻譯成恰當(dāng)?shù)倪壿嬄?lián)結(jié)詞，必須要正確地理解各原子命題之間的關(guān)系。習(xí)題1.31判斷以下各式子是否是命題公式1234562將以下命題符號(hào)化句中括號(hào)內(nèi)提示的是相應(yīng)的原子命題的符號(hào)表示1我去新華書店，僅當(dāng)我有時(shí)間。2我們不能既劃船又跑步。3只要努力學(xué)習(xí)，成績(jī)就會(huì)好的。4或者你沒有給我寫信，或者它在路上丟了。5如果上午不下雨，我就去看電影，否則我就在家里讀書或看報(bào)紙。6我今天進(jìn)城，除非下雨

13、。7如果太陽(yáng)沒出來(lái)，則或者下雨或者陰天而且溫度下降。8指南針永指南北，除非它旁邊有磁鐵。9說邏輯枯燥無(wú)味和毫無(wú)價(jià)值是不對(duì)的。10人不犯我，我不犯人；人假設(shè)犯我，我必犯人。1.4真值表與等價(jià)公式真值表定義 設(shè)，是出現(xiàn)在命題公式中的全部命題變?cè)?，給，各指定一個(gè)真值，稱為對(duì)公式的一個(gè)賦值或解釋或真值指派。假設(shè)指定的一組值使公式的真值為1，則這組值稱為公式的成真賦值。假設(shè)指定的一組值使公式的真值為0，則這組值稱為公式的成假賦值。例如，對(duì)公式，賦值011即令，則可得到公式的真值為1；假設(shè)賦值000，則公式真值為0。因此，011為公式的一個(gè)成真賦值；000為公式的一個(gè)成假賦值。除了上述的兩種賦值外，公式的

14、賦值還有000，001，等。一般的結(jié)論是在含有n個(gè)命題變?cè)拿}公式中，共有種賦值。定義 將命題公式在所有賦值下的取值情況列成表，稱為公式的真值表(Truth Table)。構(gòu)造真值表的根本步驟：1找出公式中所有的命題變?cè)?，按二進(jìn)制從小到大的順序列出種賦值。2當(dāng)公式較為復(fù)雜時(shí)，按照運(yùn)算的順序列出各個(gè)子公式的真值。3計(jì)算整個(gè)命題公式的真值。 寫出以下公式的真值表，并求其成真賦值和成假賦值。123解1的真值表見表1-6。表1-6的真值表0011011110001101成真賦值為00，01，11，成假賦值為10。2的真值表見表1-7。表1-7的真值表00100011001001011100無(wú)成真賦值

15、，成假賦值為00，01，10，11。3的真值表見表1-8。表1-8的真值表000111010111100111111001成真賦值為00，01，10，11，無(wú)成假賦值。 等價(jià)公式定義 給定兩個(gè)命題公式，設(shè)，是出現(xiàn)在命題公式中的全部命題變?cè)僭O(shè)給，任一組賦值，公式和的真值都對(duì)應(yīng)一樣，則稱公式與等價(jià)或邏輯相等(Equivalence)，記作。需要注意的是，不是邏輯聯(lián)結(jié)詞，因而不是命題公式，只是表示兩個(gè)命題公式之間的一種等價(jià)關(guān)系，即假設(shè)，和沒有本質(zhì)上的區(qū)別，最多只是和具有不同的形式而已。具有如下的性質(zhì)：1自反性：。2對(duì)稱性：假設(shè)，則。3傳遞性：假設(shè)，則。給定n個(gè)命題變?cè)鶕?jù)公式的形成規(guī)則，可以形

16、成許多個(gè)形式各異的公式，但是有很多形式不同的公式具有一樣的真值表。因此引入公式等價(jià)的概念，其目的就是將復(fù)雜的公式簡(jiǎn)化。下面介紹兩種證明公式等價(jià)的方法。1真值表法由公式等價(jià)的定義可知，利用真值表可以判斷任何兩個(gè)公式是否等價(jià)。例 證明證明命題公式與的真值表見表1-9。由表1-9可知，在任意賦值下與兩者的真值均對(duì)應(yīng)一樣。因此表1-9與的真值表001111011000100100111111例 判斷公式與二者是否等價(jià)。證明公式與的真值表見表1-10。表1-10與的真值表0011011010011111可見真值表中的最后兩列值不完全一樣，因此公式與不等價(jià)。從理論上來(lái)講，利用真值表法可以判斷任何兩個(gè)命題公

17、式是否等價(jià)，但是真值表法并不是一個(gè)非常好的方法，因?yàn)楫?dāng)公式中命題變?cè)^多時(shí)，其計(jì)算量較大，例如當(dāng)公式中有四個(gè)變?cè)獣r(shí)，需要列出=16種賦值情況，計(jì)算較為繁雜。因此，通常采用其他的證明方法。這種證明方法是先用真值表法驗(yàn)證出一些等價(jià)公式，再用這些等價(jià)公式來(lái)推導(dǎo)出新的等價(jià)公式，以此作為判斷兩個(gè)公式是否等價(jià)的根底。下面給出12組常用的等價(jià)公式，它們是進(jìn)一步推理的根底。牢記并熟練運(yùn)用這些公式是學(xué)好數(shù)理邏輯的關(guān)鍵之一。1雙重否認(rèn)律：2結(jié)合律：，3交換律：，4分配律：，5冪等律：，6吸收律：，7德.摩根律：，8同一律：9零律：10否認(rèn)律：11條件等價(jià)式：12雙條件等價(jià)式：上述12組公式均可以通過構(gòu)造真值表法來(lái)

18、證明。2等值演算法定理代入規(guī)則在一個(gè)永真式中，任何一個(gè)原子命題變?cè)霈F(xiàn)的每一處用另一個(gè)公式代入，所得的公式仍為永真式。證明：因?yàn)橛勒媸綄?duì)于任何指派，其真值都是1，與每個(gè)命題變?cè)概傻恼婕贌o(wú)關(guān)，所以，用一個(gè)命題公式代入到原子命題變?cè)霈F(xiàn)的每一處，所得到的命題公式的真值仍為1。例如，是永真式，將原子命題變?cè)么牒蟮玫降氖阶尤詾橛勒媸健６ɡ碇脫Q規(guī)則 設(shè)是命題公式的一個(gè)子公式，假設(shè)，如果將公式中的用來(lái)置換，則所得到的公式與公式等價(jià)，即。證明：因?yàn)?，所以在相?yīng)變?cè)娜我环N指派情況下，與的真值一樣，故以取代后，公式與公式在相應(yīng)的指派情況下真值也必一樣，因此。例如，利用置換，則。從定理可以看出，代入規(guī)則是

19、對(duì)原子命題變?cè)?，而置換規(guī)則可對(duì)命題公式進(jìn)展；代入必須處處代入，替換可以局部或全部替換；代入規(guī)則可以用來(lái)擴(kuò)大永真式的個(gè)數(shù)，替換規(guī)則可以增加等價(jià)式的個(gè)數(shù)。有了上述的12組等價(jià)公式及代入規(guī)則和置換規(guī)則后，就可以推演出更多的等價(jià)式。由等價(jià)式推出另外一些等價(jià)式的過程稱為等值演算(Equivalent Calculation)。 證明以下公式等價(jià)。12證明12例*件事情是甲、乙、丙、丁4人中*一個(gè)人干的。詢問4人后答復(fù)如下：1甲說是丙干的；2乙說我沒干；3丙說甲講的不符合事實(shí)；4丁說是甲干的。假設(shè)其中3人說的是真話，一人說假話，問是誰(shuí)干的？解設(shè)：這件事是甲干的。：這件事是乙干的。：這件事是丙干的。：這

20、件事是丁干的。4個(gè)人所說的命題分別用、表示，則1、2、3、4分別符號(hào)化為：；則3人說真話，一人說假話的命題符號(hào)化為：其中同理所以，當(dāng)為真時(shí)，為真，即這件事是甲干的。此題也可以從題干直接找出相互矛盾的兩個(gè)命題作為解題的突破口。甲、丙兩人所說的話是相互矛盾的，必有一人說真話，一人說假話，而4個(gè)人中只有一人說假話，因此乙、丁兩人必說真話，由此可斷定這件事是甲干的。例在*次球賽中，3位球迷甲、乙、丙對(duì)*球隊(duì)的比賽結(jié)果進(jìn)展猜想。甲說：該球隊(duì)不會(huì)得第一名，是第二名。乙說：該球隊(duì)不會(huì)得第二名，是第一名。丙說：該球隊(duì)不會(huì)得第二名，也不會(huì)是第三名。比賽完畢后，結(jié)果證實(shí)甲、乙、丙3人中有一人猜的全對(duì)，有一人猜對(duì)一

21、半，有一人猜的全錯(cuò)。試分析該球隊(duì)終究是第幾名。解設(shè)：該球隊(duì)獲得第一名。：該球隊(duì)獲得第二名。：該球隊(duì)獲得第三名。則、中必然有一個(gè)真命題，兩個(gè)假命題。設(shè)甲、乙、丙3人所說的命題分別用，表示。則有，。設(shè)甲、乙、丙的判斷全對(duì)分別用、表示，甲、乙、丙的判斷對(duì)一半分別用、表示，甲、乙、丙的判斷全錯(cuò)分別用、表示。則有：。由于該球隊(duì)不可能既是第一名又是第二名，所以。甲、乙、丙3人中有一人全對(duì)，有一人猜對(duì)一半，有一人全錯(cuò)的命題符號(hào)化為其中，。同理，由于該球隊(duì)不可能既是第一名，又是第三名，。因此，假設(shè)為真，只有為真。因而為真命題，為假命題。即該球隊(duì)獲得第二名。甲的判斷全對(duì)，乙的判斷全錯(cuò)，丙的判斷對(duì)一半。例、 4人

22、進(jìn)展百米競(jìng)賽，觀眾甲、乙、丙比照賽的結(jié)果進(jìn)展預(yù)測(cè)。甲：第一，第二；乙：第二，第三；丙：第二，第四。比賽完畢后發(fā)現(xiàn)甲、乙、丙每個(gè)人的預(yù)測(cè)結(jié)果都各對(duì)一半。試問實(shí)際名次如何假設(shè)無(wú)并列者？解設(shè)表示第名，表示第名，表示第名，表示第名，。則由題意有 1 2 3因?yàn)檎婷}的合取仍為真命題，所以12 434因此，第二，第四，第一，第三。習(xí)題1.41寫出以下公式的真值表。12342證明以下等價(jià)公式。12343甲、乙、丙、丁4人參加考試后，有人問他們誰(shuí)的成績(jī)最好，甲說：不是我。乙說：是丁。丙說：是乙。丁說：不是我。4個(gè)人的答復(fù)只有一個(gè)人符合實(shí)際，問成績(jī)最好的是誰(shuí)？ 43個(gè)球迷估計(jì)比賽結(jié)果，球迷甲說：*實(shí)德第一，國(guó)

23、安第二。球迷乙說：*申花第二，*亞泰第四。球迷丙說：*實(shí)德第二，*亞泰第四。結(jié)果3人估計(jì)的都不全對(duì)，但都對(duì)了一半，問4支球隊(duì)的名次假設(shè)無(wú)并列次序。5如果，是否有？如果，是否有？如果，是否有？6化簡(jiǎn)以下公式：12 31.5 命題公式的分類與蘊(yùn)含式 命題公式的分類從前述的真值表中可以看到，有的命題公式無(wú)論對(duì)命題歐變?cè)骱畏N賦值，其對(duì)應(yīng)的真值恒為或恒為，如例的2、3；而有的公式對(duì)應(yīng)的真值則是有有，如例1.4.1的1。根據(jù)命題公式在不同賦值下的真值情況，可以對(duì)命題公式進(jìn)展分類。定義 設(shè)為一命題公式，對(duì)公式所有可能的賦值：1假設(shè)的真值永為，則稱公式為重言式(Tautology)或永真式。2假設(shè)的真值永為

24、，則稱公式為矛盾式(Contradictory)或永假式。3假設(shè)至少存在一種賦值使得的真值為，則稱公式為可滿足式(Satisfiable)。由定義可知，根據(jù)命題公式的真值情況，公式可分為兩大類，即矛盾式和可滿足式。重言式一定是可滿足式，但反之不成立。用真值表法可以判定公式的類型：假設(shè)真值表的最后一列全為1，則公式為重言式；假設(shè)最后一列全為0，則公式為矛盾式；假設(shè)最后一列至少有一個(gè)1，則公式為可滿足式。在1.4的例中，1為可滿足式，2為矛盾式，3為重言式。用真值表法判斷公式的類型方法簡(jiǎn)單，但當(dāng)變?cè)^多時(shí)，計(jì)算量大，在后面的章節(jié)中還要介紹其他的方法。重言式與矛盾式的性質(zhì)定理 任何兩個(gè)重言式的析取或

25、合取，仍是一個(gè)重言式。證明：設(shè)、為兩個(gè)重言式，則無(wú)論對(duì)與的分量作何種指派，總有，故，。定理一個(gè)重言式，對(duì)同一分量用任何合式公式置換，所得公式仍為一重言式。證明：因?yàn)橹匮允降恼嬷蹬c分量的指派無(wú)關(guān)，所以對(duì)同一分量用任何合式公式置換后，重言式的真值仍永為真。例如，為一重言式，用置換，所得新公式仍為重言式。對(duì)于矛盾式，也有類似于定理和定理1.5.2的結(jié)果。定理設(shè)、為兩個(gè)命題公式，當(dāng)且僅當(dāng)為重言式。證明：假設(shè)，則在、所含命題變?cè)娜魏沃概上?，與的真值都一樣，即恒為真。假設(shè)為重言式，由重言式的定義知，在對(duì)、所含命題變?cè)娜魏沃概上?，與都有一樣的真值，即。例證明為重言式。證明由例知，故依據(jù)定理1.5.3有為

26、重言式。蘊(yùn)含式下面討論的重言式。定義 設(shè)、為兩個(gè)命題公式，假設(shè)為重言式，則稱蘊(yùn)含( Implication)，記作。注意與一樣，都不是邏輯聯(lián)結(jié)詞，因而也不是公式。是用來(lái)表示由條件能夠推導(dǎo)出結(jié)論，或稱為可以由邏輯推出。蘊(yùn)含關(guān)系具有如下的性質(zhì)：1自反性：對(duì)任意的公式，有。2反對(duì)稱性：對(duì)任意的公式、，假設(shè)且，則有。3傳遞性：對(duì)任意的公式、，假設(shè)、，則有。由于不具有對(duì)稱性，即與不等價(jià)，因此，對(duì)于而言，稱為它的逆換式，稱為它的反換式，稱為它的逆反式。在上述的4個(gè)公式中，。定理的充分必要條件是且。證明：假設(shè)，則為重言式，而，故均為重言式，即且。反之，假設(shè)且，則均為重言式，于是為重言式，即為重言式，故。由定

27、義知，要證明，只需證明為重言式即可。因此，前面介紹的真值表法和等值演算法均可應(yīng)用。下面綜合介紹證明的各種方法。1真值表法例 證明證明只需證明為重言式。真值表見表1-11。表1-11的真值表00010101100111112等值演算法例 證明證明只需證明為重言式。即3分析法分析法包括以下兩種形式：1假定前件為真，推出后件為真，則。2假定后件為假，推出前件為假，則。理由是：1假設(shè)為真，則可能為真也可能為假，但由假設(shè)推出為真，所以否認(rèn)了為真、為假的可能，只能是為真、也為真。所以為重言式，即。對(duì)于2，假設(shè)后件為假，則前件可能為真也可能為假。假設(shè)為真，為假，則為假；假設(shè)為假，為假，則為真。而由假設(shè)推知為

28、假，因此否認(rèn)了為真，為假的可能。所以為重言式，即。例證明12證明1假設(shè)前件為真，則為真，為真；由此有為假，為真。因此。2假設(shè)后件為假，假設(shè)為真，則為假，有為假。假設(shè)為假，則為真，有為假。綜上，假設(shè)后件為假，無(wú)論為真還是假，前件均為假。因此。需要指出的是，在例的2中，因?yàn)椴恢赖恼嬷登闆r，所以要分情況討論。例1.5.5 分析以下論證的有效性。 條件：香煙有利于安康； 如果香煙有利于安康，則醫(yī)生就會(huì)把香煙作為藥品開給病人。結(jié)論：醫(yī)生把香煙作為藥品開給病人。解設(shè)：香煙有利于安康。：醫(yī)生把香煙作為藥品開給病人。上述推理符號(hào)化為：。其證明同例的2。因此上述論證是有效的。下面給出的蘊(yùn)含式其正確性均可用上述

29、的推理方法進(jìn)展證明。1234567891011121314習(xí)題1.51判斷以下命題公式的類型。1。2。3。4。2證明以下各蘊(yùn)含式。12343判斷以下命題的真假。1重言式的否認(rèn)是矛盾式。2矛盾式的否認(rèn)是重言式。3不是重言式就是矛盾式。4不是矛盾式就是重言式。5重言式必是可滿足式。6不是矛盾式就是可滿足式。7可滿足式未必是重言式。8不是可滿足式就是矛盾式。4設(shè)P表示命題8是偶數(shù)，Q表示命題糖果是甜的。試以句子寫出：1。2的逆換式。3的反換式。4的逆反式。5表達(dá)以下各個(gè)命題的逆換式和逆反式，并以符號(hào)寫出。1如果下雨，我不去。2僅當(dāng)你走我將留下。3如果我不能獲得更多幫助，我不能完成這個(gè)任務(wù)。6檢驗(yàn)以下

30、論證的有效性。如果我學(xué)習(xí)，則我數(shù)學(xué)不會(huì)不及格。如果我不熱衷于玩撲克，則我將學(xué)習(xí)。但我數(shù)學(xué)不及格。因此，我熱衷于玩撲克。7用符號(hào)寫出以下各式并且驗(yàn)證論證的有效性。如果6是偶數(shù)，則7被2除不盡?；? 不是素?cái)?shù)，或7被2除盡。但5是素?cái)?shù)。所以6是奇數(shù)。8證明，Q邏輯蘊(yùn)含P。1.6 其它邏輯聯(lián)結(jié)詞和最小功能完備聯(lián)結(jié)詞組其它邏輯聯(lián)結(jié)詞 前面介紹了5種常用的邏輯聯(lián)結(jié)詞，和，但是這5種聯(lián)結(jié)詞還不能很廣泛地直接用來(lái)表達(dá)命題間的聯(lián)系，為此，下面再介紹4種聯(lián)結(jié)詞。1不可兼析取(排斥或/異或)(e*clusive or)定義設(shè)、為兩個(gè)命題公式，復(fù)合命題稱為異或。規(guī)定的真值為，當(dāng)且僅當(dāng)與的真值不一樣，否則的真值為。聯(lián)

31、結(jié)詞的定義見表1-12。表1-12 聯(lián)結(jié)詞的定義000011101110從真值表中易見，。利用真值表法，易證具有如下性質(zhì)：12345；6假設(shè)，則，且為一矛盾式。2與非聯(lián)結(jié)詞(Nand)( ) 定義 設(shè)、為兩個(gè)命題公式，復(fù)合命題稱為和的與非式。當(dāng)且僅當(dāng)與的真值都為時(shí)，的真值為，否則的真值為。聯(lián)結(jié)詞的定義見表1-13。表1-13 聯(lián)結(jié)詞的定義001011101110從真值表中易見，。聯(lián)結(jié)詞具有如下性質(zhì)：1233或非聯(lián)結(jié)詞(Nor)定義 設(shè)、為兩個(gè)命題公式，復(fù)合命題稱為和的或非式。當(dāng)且僅當(dāng)與的真值都為時(shí)，的真值為，否則的真值為。聯(lián)結(jié)詞的定義見表1-14。表1-14 聯(lián)結(jié)詞的定義00101010011

32、0從真值表中易見，。聯(lián)結(jié)詞具有如下性質(zhì)：1234條件否認(rèn)聯(lián)結(jié)詞(Non-conditional)定義 設(shè)、為兩個(gè)命題公式，復(fù)合命題稱為和的條件否認(rèn)。當(dāng)且僅當(dāng)?shù)恼嬷禐椋恼嬷禐闀r(shí)，的真值為，否則的真值為。聯(lián)結(jié)詞的定義見表1-15。表1-15 聯(lián)結(jié)詞的定義000010101110從真值表中易見，。 最小功能完備聯(lián)結(jié)詞組到目前為止，共定義了9個(gè)聯(lián)結(jié)詞，但這些聯(lián)結(jié)詞在表達(dá)命題時(shí)并不是缺一不可，因?yàn)榘?些聯(lián)結(jié)詞的公式可以用含有另外一些聯(lián)結(jié)詞的公式來(lái)進(jìn)展表示。如這說明可以轉(zhuǎn)化為，而可轉(zhuǎn)化為由與表示，而與又可以相互轉(zhuǎn)化。對(duì)于另外的4個(gè)聯(lián)結(jié)詞，由于，這說明任意的一個(gè)命題公式最終都可以轉(zhuǎn)化為僅包含，或，的命題

33、公式來(lái)等價(jià)地表示。定義 設(shè)是一個(gè)聯(lián)結(jié)詞的集合，假設(shè)任意一個(gè)命題公式都可用中聯(lián)結(jié)詞構(gòu)成的公式來(lái)表示，則稱為功能完備聯(lián)結(jié)詞組。如果在中去掉任何一個(gè)聯(lián)結(jié)詞后都不再具有這種性質(zhì)，則稱為最小功能完備聯(lián)結(jié)詞組，簡(jiǎn)稱為最小聯(lián)結(jié)詞組。可以證明，等都是功能完備聯(lián)結(jié)詞組，而，及，均為最小功能完備聯(lián)結(jié)詞組。由聯(lián)結(jié)詞及的性質(zhì)知，聯(lián)結(jié)詞、和可分別用 或表示，所以及也是最小功能完備聯(lián)結(jié)詞組。通常為了命題表示的簡(jiǎn)潔清楚，常用包含，的聯(lián)結(jié)詞組來(lái)表示命題。習(xí)題1.61將以下命題公式轉(zhuǎn)化為僅含聯(lián)結(jié)詞的命題公式。1232將以下命題公式用只含和的等價(jià)式表達(dá)，并要求盡可能簡(jiǎn)單。1233證明不是最小功能完備連接詞組。4證明是最小功能完備

34、連接詞組。1.7 對(duì)偶與*式對(duì)偶式與對(duì)偶原理 1對(duì)偶式定義 在只含有邏輯聯(lián)結(jié)詞，的命題公式中，假設(shè)把與互換，與互換得到一個(gè)新的命題公式，則稱是的對(duì)偶式(Dualistic Formula)，或稱與互為對(duì)偶式。顯然。例1.7.1 寫出以下公式的對(duì)偶式。123解上述公式的對(duì)偶式為123例 求，的對(duì)偶式。解因?yàn)?，所以的?duì)偶式為。同理，的對(duì)偶式為。2對(duì)偶原理(Duality Principle) 一個(gè)僅含有邏輯聯(lián)結(jié)詞，的命題公式和它的對(duì)偶式之間具有如下等值關(guān)系：定理設(shè)公式為僅含有邏輯聯(lián)結(jié)詞，及命題變?cè)拿}公式，是的對(duì)偶式，則有：12證明：由德.摩根定律，故同理例 設(shè)，證明證明因?yàn)椋?，而所以定?/p>

35、對(duì)偶原理假設(shè)公式，則。證明：設(shè)，是出現(xiàn)在命題公式，中所有的命題變?cè)?，因?yàn)椋?，所以。由定理得，即為重言式故也為重言式即?duì)偶定律說明，利用公式的對(duì)偶式可以擴(kuò)大等價(jià)式的數(shù)量，也可以簡(jiǎn)化證明。例如與這兩個(gè)等價(jià)公式的兩端互為對(duì)偶式，因而只需證明一個(gè)等價(jià)公式成立即可。命題公式的*式從前面的討論可知,存在大量互不一樣的命題公式，實(shí)際上互為等價(jià)，因此，有必要引入命題公式的標(biāo)準(zhǔn)形式，使得相互等價(jià)的命題公式具有一樣的標(biāo)準(zhǔn)形式。這無(wú)疑對(duì)判別兩個(gè)命題公式是否等價(jià)以及判定命題公式的類型是一種好方法，同時(shí)對(duì)命題公式的簡(jiǎn)化和推證也是十分有益的。1簡(jiǎn)單析取式與簡(jiǎn)單合取式定義 單個(gè)的命題變?cè)捌浞裾J(rèn)形式稱為文字。如，等。定義

36、 僅由有限個(gè)文字組成的析取式稱為簡(jiǎn)單析取式。僅由有限個(gè)文字組成的合取式稱為簡(jiǎn)單合取式。例如，等都是簡(jiǎn)單析取式；，等都是簡(jiǎn)單合取式。一個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式。定理簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含有*個(gè)命題變?cè)捌浞裾J(rèn)形式。證明：設(shè)公式為簡(jiǎn)單析取式，含有命題變?cè)?。假設(shè)同時(shí)含有及，顯然為重言式。假設(shè)為重言式但不同時(shí)含有*個(gè)命題變?cè)捌浞裾J(rèn)形式，不妨設(shè)，假設(shè)真值均為0，而真值均為1，則的真值為0，這與為重言式矛盾。對(duì)于簡(jiǎn)單合取式也有類似的性質(zhì)。定理簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含有*個(gè)命題變?cè)捌浞裾J(rèn)形式。證明同定理。2析取*式與合取*式定義由有限個(gè)簡(jiǎn)單合取式組成的析取式稱為析取*式

37、Disjunctive Normal Form。由有限個(gè)簡(jiǎn)單析取式組成的合取式稱為合取*式Conjunctive Normal Form。析取*式與合取*式統(tǒng)稱為*式。例如，等是析取*式。，等是合取*式。對(duì)于單獨(dú)的一個(gè)命題變?cè)蚱浞裾J(rèn)既可以看成是析取*式，又可看成是合取*式。當(dāng)然既可以看成是簡(jiǎn)單析取式，又可以看成是簡(jiǎn)單合取式。至于，假設(shè)把它看作為簡(jiǎn)單合取式的析取，則它是析取*式；假設(shè)把它看成是文字的析取，則它是合取*式。同理，等既是析取*式，又是合取*式。定理*式存在定理任何一個(gè)命題公式都存在著與之等價(jià)的析取*式和合取*式。從析取*式和合取*式的定義可知，*式中不存在除了，以外的其余邏輯聯(lián)結(jié)詞

38、。下面給出求公式*式的步驟：1消去除，以外公式中出現(xiàn)的所有邏輯聯(lián)結(jié)詞。2將否認(rèn)聯(lián)結(jié)詞消去或內(nèi)移到各命題變?cè)啊Ｈ?，；?利用分配律、結(jié)合律將公式轉(zhuǎn)化為合取*式或析取*式。如，；。例 求的析取*式和合取*式。解析取*式 合取*式例 求的析取*式。解上面所求的最后兩個(gè)等價(jià)的公式都是原公式的析取*式，所以命題公式的析取*式不唯一。例 求的合取*式。解上面所求的最后兩個(gè)等價(jià)的公式都是原公式的合取*式，所以命題公式的合取*式不唯一。3*式的應(yīng)用利用*式判斷命題公式類型的問題稱為判定問題。定理 一個(gè)析取*式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合取式都是矛盾式。一個(gè)合取*式是重言式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式都是重

39、言式。例判斷以下公式的類型。12解1 由定理可知，為矛盾式。2由定理可知，為重言式。命題公式的主析取*式和主合取*式由于一個(gè)命題公式的*式不唯一，這就使得*式的應(yīng)用受到了一定的限制，為了使任意命題公式化為唯一的標(biāo)準(zhǔn)形式，下面引入主*式的概念。1主析取*式定義 在含有n個(gè)命題變?cè)暮?jiǎn)單合取式中，假設(shè)每個(gè)命題變?cè)捌浞裾J(rèn)不同時(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，則稱該簡(jiǎn)單合取式為小項(xiàng)。例如，兩個(gè)命題變?cè)蜕傻?個(gè)小項(xiàng)為：，。三個(gè)命題變?cè)蜕傻?個(gè)小項(xiàng)為：，。 一般說來(lái)，n個(gè)命題變?cè)灿袀€(gè)小項(xiàng)。小項(xiàng)的二進(jìn)制編碼為：命題變?cè)醋帜疙樞蚺帕?，命題變?cè)c1對(duì)應(yīng)，命題變?cè)姆裾J(rèn)與0對(duì)應(yīng)，則得到小項(xiàng)的二

40、進(jìn)制編碼，記為m,其下標(biāo)是由二進(jìn)制編碼轉(zhuǎn)化的十進(jìn)制數(shù)。n個(gè)命題變?cè)纬傻膫€(gè)小項(xiàng)，分別記為：，。表1-16列出了兩個(gè)命題變?cè)蜕傻?個(gè)小項(xiàng)的真值表。表1-16 兩個(gè)命題變?cè)蜕傻?個(gè)小項(xiàng)的真值表二進(jìn)制001000010100100010110001十進(jìn)制從這個(gè)真值表中可以看到，沒有兩個(gè)小項(xiàng)是等價(jià)的，且每個(gè)小項(xiàng)都只對(duì)應(yīng)著和的一組真值指派使得該小項(xiàng)的真值為1。這個(gè)結(jié)論可以推廣到3個(gè)及3個(gè)以上變?cè)那闆r。由真值表可得到小項(xiàng)具有如下性質(zhì)：1各小項(xiàng)的真值表都不一樣。2每個(gè)小項(xiàng)當(dāng)其真值指派與對(duì)應(yīng)的二進(jìn)制編碼一樣時(shí)，其真值為真，在其余種指派情況下，其真值均為假。3任意兩個(gè)小項(xiàng)的合取式是矛盾式。例如=4全體

41、小項(xiàng)的析取式為永真式。定義由假設(shè)干個(gè)不同的小項(xiàng)組成的析取式稱為主析取*式(The PrincipalDisjunctive Normal Form )。與公式等價(jià)的主析取*式稱為的主析取*式。定理任意含個(gè)命題變?cè)姆怯兰偈矫}公式都存在著與之等價(jià)的主析取*式，并且其主析取*式是唯一的。證明：設(shè)是公式的析取*式，即。假設(shè)的*個(gè)簡(jiǎn)單合取式中不含有命題變?cè)捌浞裾J(rèn)，將展成形式，繼續(xù)這個(gè)過程，直到所有的簡(jiǎn)單合取式成為小項(xiàng)。然后消去重復(fù)的項(xiàng)及矛盾式后，得到公式的主析取*式。下證唯一性。假設(shè)公式有兩個(gè)與之等價(jià)的主析取*式和，則。由于和是的不同的主析取*式，不妨設(shè)小項(xiàng)只出現(xiàn)在中而不在中，于是的二進(jìn)制表示為的

42、成真賦值、的成假賦值，這與矛盾。因而公式的主析取*式是唯一的。一個(gè)命題公式的主析取*式可通過兩種方法求得，一是由公式的真值表得出，即真值表法；另一是由根本等價(jià)公式推出，即等值演算法。1真值表法定理 在真值表中，命題公式的真值為真的賦值所對(duì)應(yīng)的小項(xiàng)的析取即為命題公式的主析取*式。證明：設(shè)命題公式的真值為真的賦值所對(duì)應(yīng)的小項(xiàng)為，。令=。下證，即證與在相應(yīng)指派下具有一樣的真值。首先，對(duì)為真的*一指派，其對(duì)應(yīng)的小項(xiàng)為，則因?yàn)闉?，而，均為，所?為真。其次，對(duì)為假的*一指派，則其賦值所對(duì)應(yīng)的小項(xiàng)一定不是，中的*一項(xiàng)，即，均為假，所以=為假。綜上，。利用真值表法求主析取*式的根本步驟為：1列出公式的真值表

43、。2將真值表中的最后一列中的1的賦值所對(duì)應(yīng)的小項(xiàng)寫出。3將這些小項(xiàng)進(jìn)展析取。例 利用真值表法求的主析取*式。解的真值表見表1-17。表1-17的真值表001011101110從表1-17中可以看出，該公式在其真值表的00行、01行、10行處取真值1，所以。例用真值表法求的主析取*式。解的真值表見表1-18。表1-18的真值表0000000101010000110110000101011101111111從表1-18中可以看出，該公式在其真值表的001行、011行、101行、110行和111行處取真值1，所以。例 設(shè)公式的真值表見表1-19，求公式的主析取*式。解由真值表可看出公式有3組成真賦值

44、，分別出現(xiàn)在000行，100行和111行，所以公式的主析取*式為。表1-19 公式的真值表000100100100011010011010110011112等值演算法除了用真值表法來(lái)求一個(gè)命題公式的主析取*式外，還可以利用公式的等值演算方法來(lái)推導(dǎo)。具體的求解步驟如下：1求公式的析取*式；2除去中所有永假的析取項(xiàng)；3 假設(shè)的*個(gè)簡(jiǎn)單合取式中不含有*個(gè)命題變?cè)?，也不含，則將展成形式。4將重復(fù)出現(xiàn)的命題變?cè)⒚苁郊爸貜?fù)出現(xiàn)的小項(xiàng)都消去。5將小項(xiàng)按順序排列。例求的主析取*式。解例求的主析取*式。解2主合取*式定義在含有n個(gè)命題變?cè)暮?jiǎn)單析取式中，假設(shè)每個(gè)命題變?cè)捌浞裾J(rèn)形式不同時(shí)出現(xiàn)，但二者之一必出

45、現(xiàn)且僅出現(xiàn)一次，則稱該簡(jiǎn)單析取式為大項(xiàng)。例如，兩個(gè)命題變?cè)蜕傻?個(gè)大項(xiàng)為：，。3個(gè)命題變?cè)?、和生成?個(gè)大項(xiàng)為：，。 一般說來(lái)，n個(gè)命題變?cè)灿袀€(gè)大項(xiàng)。大項(xiàng)的二進(jìn)制編碼為：命題變?cè)醋帜疙樞蚺帕?，命題變?cè)c0對(duì)應(yīng)，命題變?cè)姆裾J(rèn)與1對(duì)應(yīng)，則得到大項(xiàng)的二進(jìn)制編碼，記為,其下標(biāo)i是由二進(jìn)制編碼轉(zhuǎn)化的十進(jìn)制數(shù)。n個(gè)命題變?cè)纬傻膫€(gè)大項(xiàng)，分別記為：，。表1-20列出了兩個(gè)命題變?cè)蜕傻?個(gè)大項(xiàng)的真值表。表1-20 兩個(gè)命題變?cè)蜕傻?個(gè)大項(xiàng)的真值表二進(jìn)制0 001110 110111 011011 11110十進(jìn)制從這個(gè)真值表中可以看到，沒有兩個(gè)大項(xiàng)是等價(jià)的，且每個(gè)大項(xiàng)都只對(duì)應(yīng)著和的一組真值指

46、派使得該大項(xiàng)的真值為0。這個(gè)結(jié)論可以推廣到3個(gè)及3個(gè)以上變?cè)那闆r。由真值表可得到大項(xiàng)具有如下性質(zhì)：1各大項(xiàng)的真值表都不一樣。2每個(gè)大項(xiàng)當(dāng)其真值指派與對(duì)應(yīng)的二進(jìn)制編碼一樣時(shí)，其真值為假，在其余種指派情況下，其真值均為真。3任意兩個(gè)不同大項(xiàng)的析取式是永真式。例如=4全體大項(xiàng)的合取式必為永假式。定義由假設(shè)干個(gè)不同的大項(xiàng)組成的合取式稱為主合取*式(The PrincipalConjunctive Normal Form)。與公式等價(jià)的主合取*式稱為的主合取*式。定理任意含個(gè)命題變?cè)姆怯勒媸矫}公式都存在著與之等價(jià)的主合取*式，并且其主合取*式是唯一的。與主析取*式的求解方法相類似，主合取*式同樣可

47、通過真值表法或等值演算法求得。1真值表法定理在真值表中，命題公式的真值為假的賦值所對(duì)應(yīng)的大項(xiàng)的合取即為命題公式的主合取*式。證明方法與定理的證明相類似。利用真值表法求主合取*式的根本步驟為：1列出公式的真值表。2將真值表中的最后一列中的0的賦值所對(duì)應(yīng)的大項(xiàng)寫出。3將這些大項(xiàng)進(jìn)展合取。例求的主合取*式。解的真值表見表1-21。表1-21的真值表0010011110001111從上表可看出，公式在00行，10行處取真值0，所以。2等值演算法 具體的求解步驟如下：1求公式的合取*式；2除去中所有永真的合取項(xiàng)；3 假設(shè)的*個(gè)簡(jiǎn)單析取式中不含有*個(gè)命題變?cè)?，也不含，則將展成形式。4將重復(fù)出現(xiàn)的命題變?cè)?/p>

48、永真式及重復(fù)出現(xiàn)的大項(xiàng)都消去。5將大項(xiàng)按順序排列。例求的主合取*式。解3主析取*式和主合取*式關(guān)系設(shè)為命題公式的主析取*式中所有小項(xiàng)的足標(biāo)集合，為命題公式的主合取*式中所有大項(xiàng)的足標(biāo)集合，則有或。故命題公式的主析取*式，可求得其主合取*式；反之亦然。事實(shí)上，注意到小項(xiàng)與大項(xiàng)滿足，。例：，。在含有個(gè)命題變?cè)拿}公式中，如果的主析取*式中含有個(gè)小項(xiàng)，則的主析取*式中必含個(gè)小項(xiàng)，且所以則的主合取*式中含有個(gè)大項(xiàng)，且的主合取*式為。因此，根據(jù)公式的主析合取*式可以寫出相應(yīng)的主合析取*式。如例 中的主合取*式為已求出，則主析取*式為，然后寫出相應(yīng)的小項(xiàng)即可。 例求的主析取*式與主合取*式。解4主*式的

49、應(yīng)用1命題公式等價(jià)性的判定由于每個(gè)命題公式都存在著與之等價(jià)的唯一的主析取*式和主合取*式，因此，如果兩個(gè)命題公式等價(jià)，則相應(yīng)的主*式也對(duì)應(yīng)一樣。例判斷與是否等價(jià)。解因?yàn)樗浴? 2) 命題公式類型的判定定理設(shè)是含個(gè)命題變?cè)拿}公式，則1為永真式當(dāng)且僅當(dāng)?shù)闹魑鋈?式中含有全部個(gè)小項(xiàng)。2為矛盾式當(dāng)且僅當(dāng)?shù)闹骱先?式中含有全部個(gè)大項(xiàng)。3假設(shè)的主析取*式中至少含有一個(gè)小項(xiàng)，則是可滿足式。例 判斷以下命題公式的類型。1) 2) 解因此，命題公式1)為永真式。因此，命題公式2)為可滿足式。3 解決實(shí)際問題例 *三說李四在說謊，李四說王五在說謊，王五說*三、李四都在說謊。請(qǐng)問3人中到底誰(shuí)在說謊？解設(shè)：*三

50、說真話即沒有說謊。：李四說真話。：王五說真話。則*三說李四在說謊可符號(hào)化為：。類似地，其余兩句話可符號(hào)化為：，。上述條件可表示為公式的真值表見表1-22。表1-22 公式的真值表00000010010101101000101011001110則公式的主析取*式為，即*三在說謊，李四說真話，王五說謊話。例 *單位要從4位職工甲、乙、丙、丁中挑選兩位職工去外地旅游，由于工作需要，選派時(shí)要考慮以下要求：1甲、乙兩人中去且僅去1人。 2乙和丁不能都去。3假設(shè)丙去，則丁必須去。4假設(shè)丁不去，則甲也不去。問該單位派誰(shuí)去符合要求？解設(shè)：派甲去旅游。：派乙去旅游。：派丙去旅游。：派丁去旅游。則由條件可得命題公

51、式：公式化成主析取*式為應(yīng)選派方案有：1派甲、丙、丁去旅游。2派甲、丁去旅游。3派乙去旅游。由于單位要派兩位職工去旅游，因此只有方案2滿足要求，即派甲、丁去旅游。習(xí)題1.71寫出以下公式的對(duì)偶式。123421設(shè)，則。2，則。3求以下公式的析取*式與合取*式：1。2。3。4。4寫出以下含有3個(gè)命題變?cè)拇箜?xiàng)或小項(xiàng)腳標(biāo)是十進(jìn)制。1 2 3 45在對(duì)、的真值指派110下，小項(xiàng)取值為，大項(xiàng)取值為。6求以下命題公式的主析取*式和主合取*式：1。2。37判斷以下命題公式的類型：1。2。3。4。8*科研所有三名青年高級(jí)工程師A、B和C。所里要選派他們中的12人出國(guó)進(jìn)修，由于所里工作的需要，選派時(shí)必須滿足以下

52、條件：假設(shè)A去，則C也去。假設(shè)B去，則C不能去。假設(shè)C不去，則A或B去。問所里應(yīng)如何選派他們？9試判斷以下各組命題是否等價(jià)：(1)與。(2) 與。1.8 推理理論推理是由一個(gè)或幾個(gè)命題推出另一個(gè)命題的思維形式。從構(gòu)造上說，推理由前提、結(jié)論和規(guī)則3個(gè)局部組成。前提與結(jié)論有蘊(yùn)含關(guān)系的推理，或者結(jié)論是從前提中必然推出的推理稱為必然性推理，如演繹推理；前提和結(jié)論沒有蘊(yùn)含關(guān)系的推理，或者前提與結(jié)論之間并沒有必然聯(lián)系而僅僅是一種或然性聯(lián)系的推理稱為或然性推理，如簡(jiǎn)單枚舉歸納推理。推理：金能導(dǎo)電，銀能導(dǎo)電，銅能導(dǎo)電。金、銀、銅都是金屬。所以金屬都能導(dǎo)電。這種從偶然現(xiàn)象概括出一般規(guī)律的推理就是一種簡(jiǎn)單枚舉歸納推理。命題邏輯中的推理是演繹推理。在實(shí)際應(yīng)用的推理中，