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

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

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

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

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

5、題常元和命題變元。一個表示確定命題的標識符稱為命題常元或命題常項(Propositional constant)；沒有指定具體內(nèi)容的命題標識符稱為命題變元或命題變項(Propositional Variable)。命題變元的真值情況不確定，因而命題變元不是命題。只有給命題變元P一具體的命題取代時，P有了確定的真值，P才成為命題。習(xí)題1.1判斷以下語句是否為命題，假設(shè)是，指出其真值。外面下雨嗎？7能被2 整除。2*+34。2燕子北回，春天來了。1設(shè)P：雪是黑色的。Q：2+24。則1可表示為PQ，其真值為T。2設(shè)R：燕子北回。S：春天來了。則2可表示為R S，其真值為T。與前面的聯(lián)結(jié)詞一樣，條件聯(lián)

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

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

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

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

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

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

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

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

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

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

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

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

18、證明。2等值演算法定理代入規(guī)則在一個永真式中，任何一個原子命題變元出現(xiàn)的每一處用另一個公式代入，所得的公式仍為永真式。證明：因為永真式對于任何指派，其真值都是1，與每個命題變元指派的真假無關(guān)，所以，用一個命題公式代入到原子命題變元出現(xiàn)的每一處，所得到的命題公式的真值仍為1。例如，是永真式，將原子命題變元用代入后得到的式子仍為永真式。定理置換規(guī)則 設(shè)是命題公式的一個子公式，假設(shè)，如果將公式中的用來置換，則所得到的公式與公式等價，即。證明：因為，所以在相應(yīng)變元的任一種指派情況下，與的真值一樣，故以取代后，公式與公式在相應(yīng)的指派情況下真值也必一樣，因此。例如，利用置換，則。從定理可以看出，代入規(guī)則是

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

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

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

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

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

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

25、合取，仍是一個重言式。證明：設(shè)、為兩個重言式，則無論對與的分量作何種指派，總有，故，。定理一個重言式，對同一分量用任何合式公式置換，所得公式仍為一重言式。證明：因為重言式的真值與分量的指派無關(guān)，所以對同一分量用任何合式公式置換后，重言式的真值仍永為真。例如，為一重言式，用置換，所得新公式仍為重言式。對于矛盾式，也有類似于定理和定理1.5.2的結(jié)果。定理設(shè)、為兩個命題公式，當且僅當為重言式。證明：假設(shè)，則在、所含命題變元的任何指派下，與的真值都一樣，即恒為真。假設(shè)為重言式，由重言式的定義知，在對、所含命題變元的任何指派下，與都有一樣的真值，即。例證明為重言式。證明由例知，故依據(jù)定理1.5.3有為

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

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

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

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

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

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

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

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

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

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

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

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

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

39、言式。例判斷以下公式的類型。12解1 由定理可知，為矛盾式。2由定理可知，為重言式。命題公式的主析取*式和主合取*式由于一個命題公式的*式不唯一，這就使得*式的應(yīng)用受到了一定的限制，為了使任意命題公式化為唯一的標準形式，下面引入主*式的概念。1主析取*式定義 在含有n個命題變元的簡單合取式中，假設(shè)每個命題變元及其否認不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，則稱該簡單合取式為小項。例如，兩個命題變元和生成的4個小項為：，。三個命題變元，和生成的8個小項為：，。 一般說來，n個命題變元共有個小項。小項的二進制編碼為：命題變元按字母順序排列，命題變元與1對應(yīng)，命題變元的否認與0對應(yīng)，則得到小項的二

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

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

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

43、。2將真值表中的最后一列中的1的賦值所對應(yīng)的小項寫出。3將這些小項進展析取。例 利用真值表法求的主析取*式。解的真值表見表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等值演算法除了用真值表法來求一個命題公式的主析取*式外，還可以利用公式的等值演算方法來推導(dǎo)。具體的求解步驟如下：1求公式的析取*式；2除去中所有永假的析取項；3 假設(shè)的*個簡單合取式中不含有*個命題變元，也不含，則將展成形式。4將重復(fù)出現(xiàn)的命題變元、矛盾式及重復(fù)出現(xiàn)的小項都消去。5將小項按順序排列。例求的主析取*式。解例求的主析取*式。解2主合取*式定義在含有n個命題變元的簡單析取式中，假設(shè)每個命題變元及其否認形式不同時出現(xiàn)，但二者之一必出

45、現(xiàn)且僅出現(xiàn)一次，則稱該簡單析取式為大項。例如，兩個命題變元和生成的4個大項為：，。3個命題變元、和生成的8個大項為：，。 一般說來，n個命題變元共有個大項。大項的二進制編碼為：命題變元按字母順序排列，命題變元與0對應(yīng)，命題變元的否認與1對應(yīng)，則得到大項的二進制編碼，記為,其下標i是由二進制編碼轉(zhuǎn)化的十進制數(shù)。n個命題變元形成的個大項，分別記為：，。表1-20列出了兩個命題變元和生成的4個大項的真值表。表1-20 兩個命題變元和生成的4個大項的真值表二進制0 001110 110111 011011 11110十進制從這個真值表中可以看到，沒有兩個大項是等價的，且每個大項都只對應(yīng)著和的一組真值指

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

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

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

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

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

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

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