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

PAGEPAGE4第1章命題邏輯邏輯是研究人的思維的科學，包括辯證邏輯和形式邏輯。辯證邏輯是研究反映客觀世界辯證發(fā)展過程的人類思維的形態(tài)的。形式邏輯是研究思維的形式結(jié)構(gòu)和規(guī)律的科學，它撇開具體的、個別的思維內(nèi)容，從形式結(jié)構(gòu)方面研究概念、判斷和推理及其正確聯(lián)系的規(guī)律。數(shù)理邏輯是用數(shù)學方法研究推理的形式結(jié)構(gòu)和推理的規(guī)律的數(shù)學學科。所謂的數(shù)學方法也就是用一套有嚴格定義的符號，即建立一套形式語言來研究。因此數(shù)理邏輯也稱為符號邏輯。數(shù)理邏輯的基礎(chǔ)部分是命題邏輯和謂詞邏輯。本章主要講述命題邏輯，謂詞邏輯將在第2章進行討論。1.1命題及其表示1.數(shù)理邏輯研究的中心問題是推理（Inference)，而推理就必然包含前提和結(jié)論，前提和結(jié)論都是表達判斷的陳述句，因而表達判斷的陳述句就成為推理的基本要素。在數(shù)理邏輯中，將能夠判斷真假的陳述句稱為命題。因此命題就成為推理的基本單位。在命題邏輯中，對命題的組成部分不再進一步細分。定義1.1.1能夠判斷真假的陳述句稱為命題（Proposition）。命題的判斷結(jié)果稱為命題的真值，常用T(True)（或1）表示真，F(xiàn)(F從上述的定義可知，判定一個句子是否為命題要分為兩步：一是判定是否為陳述句，二是能否判定真假，二者缺一不可。例1.1.1判斷下列句子是否為命題北京是中國的首都。請勿吸煙！雪是黑的。明天開會嗎？x+y=5。我正在說謊。9+5≤12。1+101=110。今天天氣多好?。e的星球上有生物。解在上述的十個句子中，（2）、（9）為祈使句，（4）為疑問句，（5）、（6）雖然是陳述句，但（5）沒有確定的真值，其真假隨x、y取值的不同而有改變，（6）是悖論(Paradox)（即由真能推出假，由假也能推出真），因而（2）、（4）、（5）、（6）、（9）均不是命題。（1）、（3）、（7）、（8）、（10）都是命題，其中（10）雖然現(xiàn)在無法判斷真假，但隨著科技的進步是可以判定真假的。需要進一步指出的是，命題的真假只要求它有就可以，而不要求立即給出。如例1.1.1的（8）1+101=110，它的真假意義通常和上下文有關(guān)，當作為二進制的加法時，它是真命題，否則為假命題。還有的命題的真假不能馬上給出，如例1.1.1的（10），但它確實有真假意義。1.1根據(jù)命題的結(jié)構(gòu)形式，命題分為原子命題和復合命題。定義1.1.2不能被分解為更簡單的陳述語句的命題稱為原子命題(SimpleProposition)。由兩個或兩個以上原子命題組合而成的命題稱為復合命題(CompoundProposition例如，例1.1.1中的命題全部為原子命題，而命題“小王和小李都去公園?！笔菑秃厦}，是由“小王去公園?！迸c“小李去公園?！眱蓚€原子命題組成的。1.定義1.1.3表示原子命題的符號稱為命題標識符(Identifier通常用大寫字母A，B，C，…，P，Q，…等表示命題，如P：今天下雨。命題標識符依據(jù)表示命題的情況，分為命題常元和命題變元。一個表示確定命題的標識符稱為命題常元（或命題常項）(Propositionalconstant)；沒有指定具體內(nèi)容的命題標識符稱為命題變元（或命題變項）(PropositionalVariable)。命題變元的真值情況不確定，因而命題變元不是命題。只有給命題變元P一具體的命題取代時，P有了確定的真值，P才成為命題。習題1.1判斷下列語句是否為命題，若是，指出其真值。外面下雨嗎？7能被2整除。2x+3<4。請關(guān)上門。小紅在教室里。指出下列命題是原子命題還是復合命題。小李一邊看書，一邊聽音樂。北京不是中國的首都。大雁北回，春天來了。不是東風壓倒西風，就是西風壓倒東風。張三與李四在吵架。1.2邏輯聯(lián)結(jié)詞本節(jié)主要介紹5種常用的邏輯聯(lián)結(jié)詞(LogicalConnectives)，分別是“非”（否定聯(lián)結(jié)詞）、“與”（合取聯(lián)結(jié)詞）、“或”（析取聯(lián)結(jié)詞）、“若…則…”（條件聯(lián)結(jié)詞）、“…當且僅當…”（雙條件聯(lián)結(jié)詞），通過這些聯(lián)結(jié)詞可以把多個原子命題復合成一個復合命題。下面分別給出各自的符號形式及真值情況。1.2.1定義1.2.1設(shè)P為一命題，P的否定(Negation)是一個新的命題，記為（讀作非P）。規(guī)定若P為T，則為F；若P為F，則為T。的取值情況依賴于P的取值情況，真值情況見表1-1。表1-1P1001在自然語言中，常用“非”、“不”、“沒有”、“無”、“并非”等來表示否定。習題1.21．指出下列命題的真值：若2+2>4，則太陽從西方升起。若a，則aA。胎生動物當且僅當是哺乳動物。指南針永指北方，除非它旁邊有磁鐵。除非ABCD是平行四邊形,否則它的對邊不都平行。2．令P：天氣好。Q：我去公園。請將下列命題符號化。如果天氣好，我就去公園。只要天氣好，我就去公園。只有天氣好，我才去公園。我去公園，僅當天氣好。或者天氣好，或者我去公園。天氣好，我去公園。1.3命題公式與翻譯1.上一節(jié)介紹了5種常用的邏輯聯(lián)結(jié)詞，利用這些邏輯聯(lián)結(jié)詞可將具體的命題表示成符號化的形式。對于較為復雜的命題，需要由這5種邏輯聯(lián)結(jié)詞經(jīng)過各種相互組合以得到其符號化的形式，那么怎樣的組合形式才是正確的、符合邏輯的表示形式呢？定義1.（2）如果是命題公式，那么也是命題公式。（3）如果、是命題公式，那么(∧),（∨),(→)和()也是命題公式。（4）當且僅當能夠有限次地應用（1）、（2）、（3）所得到的包含命題變元、聯(lián)結(jié)詞和括號的符號串是命題公式（又稱為合式公式，或簡稱為公式）。上述定義是以遞歸的形式給出的，其中（1）稱為基礎(chǔ)，（2）、（3）稱為歸納，（4）稱為界限。由定義知,命題公式是沒有真假的，僅當一個命題公式中的命題變元被賦以確定的命題時，才得到一個命題。例如在公式中，把命題“雪是白色的?！辟x給，把命題“2+2>4?！辟x給，則公式被解釋為假命題；但若的賦值不變，而把命題“2+2=4?！辟x給，則公式被解釋為真命題。定義中的符號,不同于具體公式里的、、等符號，它可以用來表示任意的命題公式。例1.3.1，，等都是命題公式，而，，等都不是命題公式。為了減少命題公式中使用括號的數(shù)量，規(guī)定：（1）邏輯聯(lián)結(jié)詞的優(yōu)先級別由高到低依次為、∧、∨、→、。（2）具有相同級別的聯(lián)結(jié)詞，按出現(xiàn)的先后次序進行計算，括號可以省略。（3）命題公式的最外層括號可以省去。例1.3.2也可以寫成，也可寫成，也可寫成，而中的括號不能省去。定義1.3.2設(shè)是命題公式的一部分，且也是命題公式，則稱為的子公式。例如及都是公式的子公式；、及都是公式的子公式。1.有了命題公式的概念之后，就可以把自然語言中的一些命題翻譯成命題邏輯中的符號化形式。把一個文字描述的命題相應地寫成由命題標識符、邏輯聯(lián)結(jié)詞和圓括號表示的命題形式稱為命題的符號化或翻譯。命題符號化的一般步驟：（1）明確給定命題的含義；（2）找出命題中的各原子命題，分別符號化。（3）使用合適的邏輯聯(lián)結(jié)詞，將原子命題分別連接起來，組成復合命題的符號化形式。把命題符號化，是不管具體內(nèi)容而突出思維形式的一種方法。注意在命題符號化時，要正確地分析和理解自然語言命題，不能僅憑文字的字面意思進行翻譯。例1.3.3張三或李四都可以做這件事。設(shè)：張三可以做這件事。：李四可以做這件事。則命題符號化為：，而不是。例1.3.4（1）只有你走，我才留下。這個命題的意義也可以理解為：如果我留下了，那么你一定走了。設(shè)：你走。：我留下。則命題符號化為：。與原命題類似的命題如：僅當你走我才留下。我留下僅當你走。當我留下你得走。注意：在一般的命題表述中，“僅當”是必要條件，譯成條件命題時其后的命題是后件，而“當”是充分條件，譯成條件命題時其后的命題是前件。（2）僅當天不下雨且我有時間，我才上街。設(shè)：天下雨。：我有時間。：我上街。命題符號化為：。（3）你將失敗，除非你努力。這個命題的意義可以理解為：如果你不努力，那么你將失敗。設(shè)：你努力。：你失敗。則命題符號化為：。含有“除非”的命題，“非…”是充分條件，譯成條件命題時，“非…”是條件的前件。（4）中沒有元素，就是空集。設(shè)：中有元素。：是空集。則命題符號化為：（5）張三與李四是表兄弟。此命題是一個原子命題，“…與…是表兄弟?！北硎緝蓚€對象之間的關(guān)系?！皬埲潜硇值堋！奔啊袄钏氖潜硇值堋！倍疾皇敲}。所以上述命題只能符號化為的形式。其中：張三與李四是表兄弟。例1.3.如果明天早上下雨或下雪，則我不去學校。如果明天早上不下雨且不下雪，則我去學校。如果明天早上不是雨夾雪，則我去學校。當且僅當明天早上不下雨且不下雪時，我才去學校。設(shè)：明天早上下雨。：明天早上下雪。：我去學校。符號化為：符號化為：符號化為：符號化為：例1.3.如果小王和小張都不去，則小李去。如果小王和小張不都去，則小李去。設(shè)：小王去。：小張去。：小李去。符號化為：符號化為：或例1.3（1）說離散數(shù)學無用且枯燥無味是不對的。（2）若天不下雨，我就上街；否則在家。對于（1），設(shè)：離散數(shù)學是有用的。：離散數(shù)學是枯燥無味的。則命題符號化為：。對于（2），設(shè)：天下雨。：我上街。：我在家。則命題符號化為：。通過上述的例題可以看出，要正確地將自然語言中的聯(lián)結(jié)詞翻譯成恰當?shù)倪壿嬄?lián)結(jié)詞，必須要正確地理解各原子命題之間的關(guān)系。習題1.31．判斷下列各式子是否是命題公式（1）（2） （3）（4）（5）（6）2．將下列命題符號化（句中括號內(nèi)提示的是相應的原子命題的符號表示）（1）我去新華書店，僅當我有時間。（2）我們不能既劃船又跑步。（3）只要努力學習，成績就會好的。（4）或者你沒有給我寫信，或者它在路上丟了。（5）如果上午不下雨，我就去看電影，否則我就在家里讀書或看報紙。（6）我今天進城，除非下雨。（7）如果太陽沒出來，則或者下雨或者陰天而且溫度下降。（8）指南針永指南北，除非它旁邊有磁鐵。（9）說邏輯枯燥無味和毫無價值是不對的。（10）人不犯我，我不犯人；人若犯我，我必犯人。1.4真值表與等價公式1.定義1.4.1設(shè)，，…，是出現(xiàn)在命題公式中的全部命題變元，給，，…，各指定一個真值，稱為對公式的一個賦值（或解釋或真值指派）。若指定的一組值使公式的真值為1，則這組值稱為公式的成真賦值。若指定的一組值使公式的真值為0，則這組值稱為公式的成假賦值。例如，對公式，賦值011（即令，則可得到公式的真值為1；若賦值000，則公式真值為0。因此，011為公式的一個成真賦值；000為公式的一個成假賦值。除了上述的兩種賦值外，公式的賦值還有000，001，…等。一般的結(jié)論是在含有n個命題變元的命題公式中，共有種賦值。定義1.4.2將命題公式在所有賦值下的取值情況列成表，稱為公式的真值表(TruthTable)構(gòu)造真值表的基本步驟：（1）找出公式中所有的命題變元，，…，，按二進制從小到大的順序列出種賦值。（2）當公式較為復雜時，按照運算的順序列出各個子公式的真值。（3）計算整個命題公式的真值。例1.4.1寫出下列公式的真值表，并求其成真賦值和成假賦值。（1）（2）（3）解（1）的真值表見表1-6。表1-6的真值表0011011110001101成真賦值為00，01，11，成假賦值為10。（2）的真值表見表1-7。表1-7的真值表00100011001001011100無成真賦值，成假賦值為00，01，10，11。（3）的真值表見表1-8。表1-8的真值表000111010111100111111001成真賦值為00，01，10，11，無成假賦值。1.定義1.4.3給定兩個命題公式，設(shè)，，…，是出現(xiàn)在命題公式中的全部命題變元，若給，，…，任一組賦值，公式和的真值都對應相同，則稱公式與等價或邏輯相等(Equivalence)，記作。需要注意的是，“”不是邏輯聯(lián)結(jié)詞，因而“”不是命題公式，只是表示兩個命題公式之間的一種等價關(guān)系，即若，和沒有本質(zhì)上的區(qū)別，最多只是和具有不同的形式而已?！啊本哂腥缦碌男再|(zhì)：（1）自反性：。（2）對稱性：若，則。（3）傳遞性：若，，則。給定n個命題變元，根據(jù)公式的形成規(guī)則，可以形成許多個形式各異的公式，但是有很多形式不同的公式具有相同的真值表。因此引入公式等價的概念，其目的就是將復雜的公式簡化。下面介紹兩種證明公式等價的方法。1．真值表法由公式等價的定義可知，利用真值表可以判斷任何兩個公式是否等價。例1.4.證明命題公式與的真值表見表1-9。由表1-9可知，在任意賦值下與兩者的真值均對應相同。因此表1-9與的真值表001111011000100100111111例1.4.3判斷公式證明公式與的真值表見表1-10。表1-10與的真值表0011011010011111可見真值表中的最后兩列值不完全相同，因此公式與不等價。從理論上來講，利用真值表法可以判斷任何兩個命題公式是否等價，但是真值表法并不是一個非常好的方法，因為當公式中命題變元較多時，其計算量較大，例如當公式中有四個變元時，需要列出=16種賦值情況，計算較為繁雜。因此，通常采用其他的證明方法。這種證明方法是先用真值表法驗證出一些等價公式，再用這些等價公式來推導出新的等價公式，以此作為判斷兩個公式是否等價的基礎(chǔ)。下面給出12組常用的等價公式，它們是進一步推理的基礎(chǔ)。牢記并熟練運用這些公式是學好數(shù)理邏輯的關(guān)鍵之一。（1）雙重否定律：（2）結(jié)合律：，，（3）交換律：，，（4）分配律：，（5）冪等律：，（6）吸收律：，（7）德.摩根律：，（8）同一律：（9）零律：（10）否定律：（11）條件等價式：（12）雙條件等價式：上述12組公式均可以通過構(gòu)造真值表法來證明。2．等值演算法定理1.4.1（代入規(guī)則）在一個永真式中，任何一個原子命題變元出現(xiàn)的每一處用另一個公式代入，所得的公式仍為永真式。證明：因為永真式對于任何指派，其真值都是1，與每個命題變元指派的真假無關(guān)，所以，用一個命題公式代入到原子命題變元出現(xiàn)的每一處，所得到的命題公式的真值仍為1。例如，是永真式，將原子命題變元用代入后得到的式子仍為永真式。定理1.4.2（置換規(guī)則）設(shè)是命題公式的一個子公式，若，如果將公式中的用來置換，則所得到的公式與公式等價，即。證明：因為，所以在相應變元的任一種指派情況下，與的真值相同，故以取代后，公式與公式在相應的指派情況下真值也必相同，因此。例如，利用置換，則。從定理可以看出，代入規(guī)則是對原子命題變元而言，而置換規(guī)則可對命題公式進行；代入必須處處代入，替換可以部分或全部替換；代入規(guī)則可以用來擴大永真式的個數(shù)，替換規(guī)則可以增加等價式的個數(shù)。有了上述的12組等價公式及代入規(guī)則和置換規(guī)則后，就可以推演出更多的等價式。由已知等價式推出另外一些等價式的過程稱為等值演算(EquivalentCalculation)。例1.4.4證明下列公式等價。（1）（2）證明（1）（2）例1.4.5解設(shè)：這件事是甲干的。：這件事是乙干的。：這件事是丙干的。：這件事是丁干的。4個人所說的命題分別用、、、表示，則（1）、（2）、（3）、（4）分別符號化為：；；；則3人說真話，一人說假話的命題符號化為：其中同理所以，當為真時，為真，即這件事是甲干的。本題也可以從題干直接找出相互矛盾的兩個命題作為解題的突破口。甲、丙兩人所說的話是相互矛盾的，必有一人說真話，一人說假話，而4個人中只有一人說假話，因此乙、丁兩人必說真話，由此可斷定這件事是甲干的。例1.4.6在某次球賽中，3位球迷甲、乙、丙解設(shè)：該球隊獲得第一名。：該球隊獲得第二名。：該球隊獲得第三名。則、、中必然有一個真命題，兩個假命題。設(shè)甲、乙、丙3人所說的命題分別用，，表示。則有，，。設(shè)甲、乙、丙的判斷全對分別用、、表示，甲、乙、丙的判斷對一半分別用、、表示，甲、乙、丙的判斷全錯分別用、、表示。則有：。（由于該球隊不可能既是第一名又是第二名，所以）。。。。。。。。甲、乙、丙3人中有一人全對，有一人猜對一半，有一人全錯的命題符號化為其中，。同理，，，（由于該球隊不可能既是第一名，又是第三名），。因此，若為真，只有為真。因而為真命題，為假命題。即該球隊獲得第二名。甲的判斷全對，乙的判斷全錯，丙的判斷對一半。例1.4.7、、、4人進行百米競賽，觀眾甲、乙、丙對比賽的結(jié)果進行預測。甲：第一，第二；乙：第二，第三；丙：第二，第四。比賽結(jié)束后發(fā)現(xiàn)甲、乙、丙每個人的預測結(jié)果都各對一半。試問實際名次如何（假如無并列者）？解設(shè)表示第名，表示第名，表示第名，表示第名，。則由題意有（1）（2）（3）因為真命題的合取仍為真命題，所以（1）（2）（4）（3）（4）因此，第二，第四，第一，第三。習題1.41．寫出下列公式的真值表。（1）（2）（3）（4）2．證明下列等價公式。（1）（2）（3）（4）3．甲、乙、丙、丁4人參加考試后，有人問他們誰的成績最好，甲說：不是我。乙說：是丁。丙說：是乙。丁說：不是我。已知4個人的回答只有一個人符合實際，問成績最好的是誰？4．3個球迷估計比賽結(jié)果，球迷甲說：大連實德第一，北京國安第二。球迷乙說：上海申花第二，長春亞泰第四。球迷丙說：大連實德第二，長春亞泰第四。結(jié)果3人估計的都不全對，但都對了一半，問4支球隊的名次（假設(shè)無并列次序）。5．如果，是否有？如果，是否有？如果，是否有？6．化簡下列公式：（1）（2）（3）1.5命題公式的分類與蘊含式1.5.從前述的真值表中可以看到，有的命題公式無論對命題歐變元作何種賦值，其對應的真值恒為或恒為，如例1.4.1的（2）、（3）；而有的公式對應的真值則是有有，如例1.4.1的（1）。根據(jù)命題公式在不同賦值下的真值情況，可以對命題公式進行分類。定義1.5.1設(shè)為一命題公式，對公式所有可能的賦值：（1）若的真值永為，則稱公式為重言式(Tautology)或永真式。（2）若的真值永為，則稱公式為矛盾式(Contradictory)或永假式。（3）若至少存在一種賦值使得的真值為，則稱公式為可滿足式(Satisfiable)。由定義可知，根據(jù)命題公式的真值情況，公式可分為兩大類，即矛盾式和可滿足式。重言式一定是可滿足式，但反之不成立。用真值表法可以判定公式的類型：若真值表的最后一列全為1，則公式為重言式；若最后一列全為0，則公式為矛盾式；若最后一列至少有一個1，則公式為可滿足式。在1.4的例1.4.1中，（1）為可滿足式，（2）為矛盾式，（3）為重言式。用真值表法判斷公式的類型方法簡單，但當變元較多時，計算量大，1.5.2重言式與矛盾式的性質(zhì)定理1.5.1證明：設(shè)、為兩個重言式，則無論對與的分量作何種指派，總有，，故，。定理1.5.2一個重言式，證明：因為重言式的真值與分量的指派無關(guān)，所以對同一分量用任何合式公式置換后，重言式的真值仍永為真。例如，為一重言式，用置換，所得新公式仍為重言式。對于矛盾式，也有類似于定理1.5.1和定理1.定理1.5.3設(shè)、為兩個命題公式，當且僅當為重言式。證明：若，則在、所含命題變元的任何指派下，與的真值都相同，即恒為真。若為重言式，由重言式的定義知，在對、所含命題變元的任何指派下，與都有相同的真值，即。例1.5.1證明由例1.4.2知，故依據(jù)定理1.5.3有為重言式。1.5下面討論的重言式。定義1.5.2設(shè)、為兩個命題公式，若為重言式，則稱“蘊含(Implication)”，記作。注意“”與“”一樣，都不是邏輯聯(lián)結(jié)詞，因而也不是公式。是用來表示由條件能夠推導出結(jié)論，或稱為可以由邏輯推出。蘊含關(guān)系具有如下的性質(zhì)：（1）自反性：對任意的公式，有。（2）反對稱性：對任意的公式、，若且，則有。（3）傳遞性：對任意的公式、、，若、，則有。由于不具有對稱性，即與不等價，因此，對于而言，稱為它的逆換式，稱為它的反換式，稱為它的逆反式。在上述的4個公式中，，。定理1.5.4的充分必要條件是且。證明：若，則為重言式，而，故均為重言式，即且。反之，若且，則均為重言式，于是為重言式，即為重言式，故。由定義1.5.2知，要證明，只需證明為重言式即可。下面綜合介紹證明的各種方法。1．真值表法例1.5.證明只需證明為重言式。真值表見表1-11。表1-11的真值表00010101100111112．等值演算法例1.5.3證明只需證明為重言式。即3．分析法分析法包括以下兩種形式：（1）假定前件為真，推出后件為真，則。（2）假定后件為假，推出前件為假，則。理由是：（1）若為真，則可能為真也可能為假，但由假設(shè)推出為真，所以否定了為真、為假的可能，只能是為真、也為真。所以為重言式，即。對于（2），若后件為假，則前件可能為真也可能為假。若為真，為假，則為假；若為假，為假，則為真。而由假設(shè)推知為假，因此否定了為真，為假的可能。所以為重言式，即。例1.5.（2）證明（1）假設(shè)前件為真，則為真，為真；由此有為假，為真。因此。（2）假設(shè)后件為假，若為真，則為假，有為假。若為假，則為真，有為假。綜上，若后件為假，無論為真還是假，前件均為假。因此。需要指出的是，在例1.5.4的（2）中，因為不知道的真值情況，所以要分情況討論。例1.5.5分析下列論證的有效性。條件：香煙有利于健康；如果香煙有利于健康，那么醫(yī)生就會把香煙作為藥品開給病人。結(jié)論：醫(yī)生把香煙作為藥品開給病人。解設(shè)：香煙有利于健康。：醫(yī)生把香煙作為藥品開給病人。上述推理符號化為：。其證明同例1.5.4的下面給出的蘊含式其正確性均可用上述的推理方法進行證明。（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）習題1.51．判斷下列命題公式的類型。（1）。（2）。（3）。（4）。2．證明下列各蘊含式。（1）（2）（3）（4）3．判斷下列命題的真假。（1）重言式的否定是矛盾式。（2）矛盾式的否定是重言式。（3）不是重言式就是矛盾式。（4）不是矛盾式就是重言式。（5）重言式必是可滿足式。（6）不是矛盾式就是可滿足式。（7）可滿足式未必是重言式。（8）不是可滿足式就是矛盾式。4．設(shè)P表示命題“8是偶數(shù)”，Q表示命題“糖果是甜的”。試以句子寫出：（1）。（2）的逆換式。（3）的反換式。（4）的逆反式。5．敘述下列各個命題的逆換式和逆反式，并以符號寫出。（1）如果下雨，我不去。（2）僅當你走我將留下。（3）如果我不能獲得更多幫助，我不能完成這個任務。6．檢驗下列論證的有效性。如果我學習，那么我數(shù)學不會不及格。如果我不熱衷于玩撲克，那么我將學習。但我數(shù)學不及格。因此，我熱衷于玩撲克。7．用符號寫出下列各式并且驗證論證的有效性。如果6是偶數(shù)，則7被2除不盡?；?不是素數(shù)，或7被2除盡。但5是素數(shù)。所以6是奇數(shù)。8．證明，Q邏輯蘊含P。1.6其它邏輯聯(lián)結(jié)詞和最小功能完備聯(lián)結(jié)詞組1.6.前面介紹了5種常用的邏輯聯(lián)結(jié)詞，，，和，但是這5種聯(lián)結(jié)詞還不能很廣泛地直接用來表達命題間的聯(lián)系，為此，下面再介紹4種聯(lián)結(jié)詞。1．不可兼析取(排斥或/異或)(exclusiveor)（）定義1.6.1設(shè)、為兩個命題公式，復合命題稱為異或。規(guī)定的真值為，當且僅當與的真值不相同，否則的真值為。聯(lián)結(jié)詞“”的定義見表1-12。表1-12聯(lián)結(jié)詞“”的定義000011101110從真值表中易見，。利用真值表法，易證“”具有如下性質(zhì)：（1）（2）（）（3）（4）（5）；；（6）若，則，，且為一矛盾式。2．與非聯(lián)結(jié)詞(Nand)()定義1.6.2設(shè)、為兩個命題公式，復合命題稱為和的“與非式”。當且僅當與的真值都為時，的真值為，否則的真值為。聯(lián)結(jié)詞“”的定義見表1-13。表1-13聯(lián)結(jié)詞“”的定義001011101110從真值表中易見，。聯(lián)結(jié)詞“”具有如下性質(zhì)：（1）（2）（3）3．或非聯(lián)結(jié)詞(Nor)（）定義1.6.3設(shè)、為兩個命題公式，復合命題稱為和的“或非式”。當且僅當與的真值都為時，的真值為，否則的真值為。聯(lián)結(jié)詞“”的定義見表1-14。表1-14聯(lián)結(jié)詞“”的定義001010100110從真值表中易見，。聯(lián)結(jié)詞“”具有如下性質(zhì)：（1）（2）（3）4．條件否定聯(lián)結(jié)詞(Non-conditional)（）定義1.6.4設(shè)、為兩個命題公式，復合命題稱為和的“條件否定”。當且僅當?shù)恼嬷禐椋恼嬷禐闀r，的真值為，否則的真值為。聯(lián)結(jié)詞“”的定義見表1-15。表1-15聯(lián)結(jié)詞“”的定義000010101110從真值表中易見，。1.6.到目前為止，共定義了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)化為僅包含，或，的命題公式來等價地表示。定義1.6.5設(shè)是一個聯(lián)結(jié)詞的集合，若任意一個命題公式都可用中聯(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é)詞組來表示命題。習題1.61．將下列命題公式轉(zhuǎn)化為僅含聯(lián)結(jié)詞的命題公式。（1）（2）（3）2．將下列命題公式用只含和的等價式表達，并要求盡可能簡單。（1）（2）（3）3．證明不是最小功能完備連接詞組。4．證明是最小功能完備連接詞組。1.7對偶與范式1.71．對偶式定義1.7.1在只含有邏輯聯(lián)結(jié)詞，，的命題公式中，若把與互換，與互換得到一個新的命題公式，則稱是的對偶式(DualisticFormula)，或稱與互為對偶式。顯然。例1.7.1寫出下列公式的對偶式。（1）（2）（3）解上述公式的對偶式為（1）（2）（3）例1.7.2求解因為，所以的對偶式為。同理，的對偶式為。2．對偶原理(DualityPrinciple)一個僅含有邏輯聯(lián)結(jié)詞，，的命題公式和它的對偶式之間具有如下等值關(guān)系：定理1.7.1設(shè)公式為僅含有邏輯聯(lián)結(jié)詞，，及命題變元，，…，的命題公式，是的對偶式，則有：（1）（2）證明：由德.摩根定律，故同理例1.7.3證明因為，所以，而所以定理1.7.2（對偶原理）若公式，則。證明：設(shè)，，…，是出現(xiàn)在命題公式，中所有的命題變元，因為，即，所以。由定理1.7即為重言式故也為重言式即對偶定律表明，利用公式的對偶式可以擴大等價式的數(shù)量，也可以簡化證明。例如與這兩個等價公式的兩端互為對偶式，因而只需證明一個等價公式成立即可。1.7.2從前面的討論可知,存在大量互不相同的命題公式，實際上互為等價，因此，有必要引入命題公式的標準形式，使得相互等價的命題公式具有相同的標準形式。這無疑對判別兩個命題公式是否等價以及判定命題公式的類型是一種好方法，同時對命題公式的簡化和推證也是十分有益的。1．簡單析取式與簡單合取式定義1.7.2單個的命題變元及其否定形式稱為文字。如，等。定義1.例如，，，等都是簡單析取式；，，，等都是簡單合取式。一個文字既是簡單析取式，又是簡單合取式。定理1.7.3證明：設(shè)公式為簡單析取式，含有命題變元。若同時含有及，顯然為重言式。若為重言式但不同時含有某個命題變元及其否定形式，不妨設(shè)，若真值均為0，而真值均為1，則的真值為0，這與為重言式矛盾。對于簡單合取式也有類似的性質(zhì)。定理1.7.4證明同定理1.2．析取范式與合取范式定義1.7.4由有限個簡單合取式組成的析取式稱為析取范式（DisjunctiveNormalForm）。由有限個簡單析取式組成的合取式稱為合取范式（ConjunctiveNormalForm）例如，，等是析取范式。，等是合取范式。對于單獨的一個命題變元或其否定既可以看成是析取范式，又可看成是合取范式。當然既可以看成是簡單析取式，又可以看成是簡單合取式。至于，若把它看作為簡單合取式的析取，則它是析取范式；若把它看成是文字的析取，則它是合取范式。同理，，等既是析取范式，又是合取范式。定理1.從析取范式和合取范式的定義可知，范式中不存在除了，，以外的其余邏輯聯(lián)結(jié)詞。下面給出求公式范式的步驟：（1）消去除，，以外公式中出現(xiàn)的所有邏輯聯(lián)結(jié)詞。（2）將否定聯(lián)結(jié)詞消去或內(nèi)移到各命題變元之前。如，；；。（3）利用分配律、結(jié)合律將公式轉(zhuǎn)化為合取范式或析取范式。如，；。例1.7.解（析取范式）（合取范式）例1.7.解上面所求的最后兩個等價的公式都是原公式的析取范式，所以命題公式的析取范式不唯一。例1.7.解上面所求的最后兩個等價的公式都是原公式的合取范式，所以命題公式的合取范式不唯一。3．范式的應用利用范式判斷命題公式類型的問題稱為判定問題。定理1.例1.7（1）（2）解（1）由定理1.7.6可知，（2）由定理1.7.6可知，1.7.3命題公式的主析取范式和主合取范式由于一個命題公式的范式不唯一，這就使得范式的應用受到了一定的限制，為了使任意命題公式化為唯一的標準形式，下面引入主范式的概念。1．主析取范式定義1.7.5在含有n個命題變元的簡單合取式中，若每個命題變元及其否定不同時出現(xiàn)，而二者之一例如，兩個命題變元和生成的4個小項為：，，，。三個命題變元，和生成的8個小項為：，，，，，，，。一般說來，n個命題變元共有個小項。小項的二進制編碼為：命題變元按字母順序排列，命題變元與1對應，命題變元的否定與0對應，則得到小項的二進制編碼，記為m,其下標是由二進制編碼轉(zhuǎn)化的十進制數(shù)。n個命題變元形成的個小項，分別記為：，，…，。表1-16列出了兩個命題變元和生成的4個小項的真值表。表1-16兩個命題變元和生成的4個小項的真值表（二進制）001000010100100010110001（十進制）從這個真值表中可以看到，沒有兩個小項是等價的，且每個小項都只對應著和的一組真值指派使得該小項的真值為1。這個結(jié)論可以推廣到3個及3個以上變元的情況。由真值表可得到小項具有如下性質(zhì)：（1）各小項的真值表都不相同。（2）每個小項當其真值指派與對應的二進制編碼相同時，其真值為真，在其余種指派情況下，其真值均為假。（3）任意兩個小項的合取式是矛盾式。例如=（4）全體小項的析取式為永真式。定義1.7.6由若干個不同的小項組成的析取式稱為主析取范式DisjunctiveNormalForm)。與公式等價的主析取范式稱為的主析取范式。定理1.7.7任意含個命題變元的非永假式命題公式都存在著與之等價的主析取范式，并且其主析取范式是唯一的證明：設(shè)是公式的析取范式，即。若的某個簡單合取式中不含有命題變元及其否定，將展成形式，繼續(xù)這個過程，直到所有的簡單合取式成為小項。然后消去重復的項及矛盾式后，得到公式的主析取范式。下證唯一性。若公式有兩個與之等價的主析取范式和，則。由于和是的不同的主析取范式，不妨設(shè)小項只出現(xiàn)在中而不在中，于是的二進制表示為的成真賦值、的成假賦值，這與矛盾。因而公式的主析取范式是唯一的。一個命題公式的主析取范式可通過兩種方法求得，一是由公式的真值表得出，即真值表法；另一是由基本等價公式推出，即等值演算法。（1）真值表法定理1.7.8在真值表中，命題公式的真值為真的賦值所對應的小項的析取即為命題公式的主析取范式。 證明：設(shè)命題公式的真值為真的賦值所對應的小項為，，…，。令=…。下證，即證與在相應指派下具有相同的真值。首先，對為真的某一指派，其對應的小項為，則因為為，而，，…，，，…，均為，所以=…為真。其次，對為假的某一指派，則其賦值所對應的小項一定不是，，…，中的某一項，即，，…，均為假，所以=…為假。綜上，。利用真值表法求主析取范式的基本步驟為：（1）列出公式的真值表。（2）將真值表中的最后一列中的1的賦值所對應的小項寫出。（3）將這些小項進行析取。例1.7.解的真值表見表1-17。表1-17的真值表001011101110從表1-17中可以看出，該公式在其真值表的00行、01行、10行處取真值1，所以。例1.7.解的真值表見表1-18。表1-18的真值表0000000101010000110110000101011101111111從表1-18中可以看出，該公式在其真值表的001行、011行、101行、110行和111行處取真值1，所以。例1.7.10設(shè)公式的真值表見解由真值表可看出公式有3組成真賦值，分別出現(xiàn)在000行，100行和111行，所以公式的主析取范式為。表1-19公式的真值表00010010010001101001101011001111（2）等值演算法除了用真值表法來求一個命題公式的主析取范式外，還可以利用公式的等值演算方法來推導。具體的求解步驟如下：1）求公式的析取范式；2）除去中所有永假的析取項；3）若的某個簡單合取式中不含有某個命題變元，也不含，則將展成形式。（4）將重復出現(xiàn)的命題變元、矛盾式及重復出現(xiàn)的小項都消去。（5）將小項按順序排列。例1.7.11解例1.7.12解2．主合取范式定義1.7.7在含有n例如，兩個命題變元和生成的4個大項為：，，，。3個命題變元、和生成的8個大項為：，，，，，，，。一般說來，n個命題變元共有個大項。大項的二進制編碼為：命題變元按字母順序排列，命題變元與0對應，命題變元的否定與1對應，則得到大項的二進制編碼，記為,其下標i是由二進制編碼轉(zhuǎn)化的十進制數(shù)。n個命題變元形成的個大項，分別記為：，，…，。表1-20列出了兩個命題變元和生成的4個大項的真值表。表1-20兩個命題變元和生成的4個大項的真值表（二進制）000111011011101101111110（十進制）從這個真值表中可以看到，沒有兩個大項是等價的，且每個大項都只對應著和的一組真值指派使得該大項的真值為0。這個結(jié)論可以推廣到3個及3個以上變元的情況。由真值表可得到大項具有如下性質(zhì)：1）各大項的真值表都不相同。2）每個大項當其真值指派與對應的二進制編碼相同時，其真值為假，在其余種指派情況下，其真值均為真。3）任意兩個不同大項的析取式是永真式。例如=4）全體大項的合取式必為永假式。定義1.7.8由若干個不同的大項組成的合取式稱為主合取范式ConjunctiveNormalForm)。與公式等價的主合取范式稱為的主合取范式。定理1.7.9任意含個命題變元的非永真式命題公式都存在著與之等價的主合取范式，并且其主合取范式是唯一的與主析取范式的求解方法相類似，主合取范式同樣可通過真值表法或等值演算法求得。（1）真值表法定理1.7.10在真值表中，命題公式的真值為假的賦值所對應的大項的合取即為命題公式的主合取范式。證明方法與定理1.7.8利用真值表法求主合取范式的基本步驟為：（1）列出公式的真值表。（2）將真值表中的最后一列中的0的賦值所對應的大項寫出。（3）將這些大項進行合取。例1.7.13解的真值表見表1-21。表1-21的真值表0010011110001111從上表可看出，公式在00行，10行處取真值0，所以。（2）等值演算法具體的求解步驟如下：1）求公式的合取范式；2）除去中所有永真的合取項；3）若的某個簡單析取式中不含有某個命題變元，也不含，則將展成形式。4）將重復出現(xiàn)的命題變元、永真式及重復出現(xiàn)的大項都消去。5）將大項按順序排列。例1.7.14解3．主析取范式和主合取范式關(guān)系設(shè)為命題公式的主析取范式中所有小項的足標集合，為命題公式的主合取范式中所有大項的足標集合，則有或。故已知命題公式的主析取范式，可求得其主合取范式；反之亦然。事實上，注意到小項與大項滿足，。（例：，）。在含有個命題變元的命題公式中，如果的主析取范式中含有個小項，，則的主析取范式中必含個小項，且所以則的主合取范式中含有個大項，且的主合取范式為。因此，根據(jù)公式的主析（合）取范式可以寫出相應的主合（析）取范式。如例1.7.14中的主合取范式為已求出，則主析取范式為例1.7.15解4．主范式的應用（1）命題公式等價性的判定由于每個命題公式都存在著與之等價的唯一的主析取范式和主合取范式，因此，如果兩個命題公式等價，則相應的主范式也對應相同。例1.7.16判斷解因為所以。(2)命題公式類型的判定定理1.7.11設(shè)是含個命題變元的命題公式，則1）為永真式當且僅當?shù)闹魑鋈》妒街泻腥總€小項。2）為矛盾式當且僅當?shù)闹骱先》妒街泻腥總€大項。3）若的主析取范式中至少含有一個小項，則是可滿足式。例1.1)2)解因此，命題公式1)為永真式。因此，命題公式2)為可滿足式。（3）解決實際問題例1.7.1解設(shè)：張三說真話（即沒有說謊）。：李四說真話。：王五說真話。則張三說李四在說謊可符號化為：。類似地，其余兩句話可符號化為：，。上述已知條件可表示為公式的真值表見表1-22。表1-22公式的真值表00000010010101101000101011001110則公式的主析取范式為，即張三在說謊，李四說真話，王五說謊話。例1.7.19某單位要從4位職工甲、（1）甲、乙兩人中去且僅去1人。（2）乙和丁不能都去。（3）若丙去，則丁必須去。（4）若丁不去，則甲也不去。問該單位派誰去符合要求？解設(shè)：派甲去旅游。：派乙去旅游。：派丙去旅游。：派丁去旅游。則由已知條件可得命題公式：公式化成主析取范式為故選派方案有：（1）派甲、丙、丁去旅游。（2）派甲、丁去旅游。（3）派乙去旅游。由于單位要派兩位職工去旅游，因此只有方案（2）滿足要求，即派甲、丁去旅游。習題1.71．寫出下列公式的對偶式。（1）（2）（3）（4）2．（1）設(shè)，則。（2），則。3．求下列公式的析取范式與合取范式：（1）。（2）。（3）。（4）。4．寫出下列含有3個命題變元的大項或小項（腳標是十進制）。（1）（2）（3）（4）5．在對、、的真值指派110下，小項取值為，大項取值為。6．求下列命題公式的主析取范式和主合取范式：（1）。（2）。（3）7．判斷下列命題公式的類型：（1）。（2）。（3）。（4）。8．某科研所有三名青年高級工程師A、B和C。所里要選派他們中的1~2人出國進修，由于所里工作的需要，選派時必須滿足以下條件：①若A去，則C也去。②若B去，則C不能去。③若C不去，則A或B去。問所里應如何選派他們？9．試判斷下列各組命題是否等價：(1)與。(2)與。1.8推理理論推理是由一個或幾個命題推出另一個命題的思維形式。從結(jié)構(gòu)上說，推理由前提、結(jié)論和規(guī)則3個部分組成。前提與結(jié)論有蘊含關(guān)系的推理，或者結(jié)論是從前提中必然推出的推理稱為必然性推理，如演繹推理；前提和結(jié)論沒有蘊含關(guān)系的推理，或者前提與結(jié)論之間并沒有必然聯(lián)系而僅僅是一種或然性聯(lián)系的推理稱為或然性推理，如簡單枚舉歸納推理。推理：“金能導電，銀能導電，銅能導電。金、銀、銅都是金屬。所以金屬都能導電?！边@種從偶然現(xiàn)象概括出一般規(guī)律的推理就是一種簡單枚舉歸納推理。命題邏輯中的推理是演繹推理。在實際應用的推理中，常常把本門學科的一些定律、定理和條件，作為假設(shè)前提，盡管這些前提在數(shù)理邏輯中并非永真，但在推理過程中，卻總是假設(shè)這些命題為真，并使用一些公認的規(guī)則，得到另外的命題，形成結(jié)論，這種過程就是論證。定義1.8.1設(shè)和是兩個命題公式，當且僅當為一重言式，即，稱是的有效結(jié)論，或可由邏輯推出。這個定義可以推廣到有個前提的情況。設(shè)，，…，，是命題公式，當且僅當…，稱是一組前提，，…，的有效結(jié)論。注意，在形式邏輯中，并不關(guān)心結(jié)論是否真實，而只在乎由給定的前提，，…，能否推出結(jié)論來，只注意推理的形式是否正確。因此，有效結(jié)論并不一定是正確的，只有正確的前提經(jīng)過正確的推理得到的邏輯結(jié)論才是正確的。在證明有效結(jié)論時，可以用前面介紹的真值表法或證明蘊含關(guān)系的方法來論證結(jié)論的有效性。論證的方法千變?nèi)f化，但基本上歸納起來只有3種方法，即真值表法、直接證法和間接證法。真值表法在此不再討論。1.直接證法就是由一組命題，利用一些公認的推理規(guī)則，根據(jù)已知的等價式或蘊含式，推演出有效結(jié)論，即形式演繹法。直接證法必須遵循下列推理規(guī)則：規(guī)則：前提條件在推導過程中的任何時候都可以引入使用。規(guī)則：在推導過程中，所證明的結(jié)論、已知的等價或蘊含公式都可以作為后續(xù)證明的前提，命題公式中的任何子公式都可以用與之等價的命題公式置換?，F(xiàn)將常用的蘊含式和等價式列入表1-23和表1-24中。表1-23常用的蘊含式表1-24常用的等價式例1.8.證明（1）（2）（3）（4）（5）（6）（7）（8）例1.8.2證明,,,證明（1）（2）（3）（4）