離散數(shù)學(xué)電子教材1及離散數(shù)學(xué)第二版答案(6-7章)

第1章命題邏輯邏輯是研究人的思維的科學(xué)，包括辯證邏輯和形式邏輯。辯證邏輯是研究反映客觀世界辯證發(fā)展過程的人類思維的形態(tài)的。形式邏輯是研究思維的形式結(jié)構(gòu)和規(guī)律的科學(xué)，它撇開具體的、個(gè)別的思維內(nèi)容，從形式結(jié)構(gòu)方面研究概念、判斷和推理及其正確聯(lián)系的規(guī)律。數(shù)理邏輯是用數(shù)學(xué)方法研究推理的形式結(jié)構(gòu)和推理的規(guī)律的數(shù)學(xué)學(xué)科。所謂的數(shù)學(xué)方法也就是用一套有嚴(yán)格定義的符號(hào)，即建立一套形式語言來研究。因此數(shù)理邏輯也稱為符號(hào)邏輯。數(shù)理邏輯的基礎(chǔ)部分是命題邏輯和謂詞邏輯。本章主要講述命題邏輯，謂詞邏輯將在第2章進(jìn)行討論。1.1命題及其表示1.1.1命題的基本概念數(shù)理邏輯研究的中心問題是推理（Inference)，而推理就必然包含前提和結(jié)論，前提和結(jié)論都是表達(dá)判斷的陳述句，因而表達(dá)判斷的陳述句就成為推理的基本要素。在數(shù)理邏輯中，將能夠判斷真假的陳述句稱為命題。因此命題就成為推理的基本單位。在命題邏輯中，對(duì)命題的組成部分不再進(jìn)一步細(xì)分。定義1.1.1能夠判斷真假的陳述句稱為命題（Proposition）。命題的判斷結(jié)果稱為命題的真值，常用T(True)（或1）表示真，F(xiàn)(False)（或0）表示假。真值為真的命題稱為真命題，真值為假的命題稱為假命題。從上述的定義可知，判定一個(gè)句子是否為命題要分為兩步：一是判定是否為陳述句，二是能否判定真假，二者缺一不可。例1.1.1判斷下列句子是否為命題北京是中國(guó)的首都。請(qǐng)勿吸煙！雪是黑的。明天開會(huì)嗎？x+y=5。我正在說謊。9+5≤12。1+101=110。今天天氣多好啊！別的星球上有生物。解在上述的十個(gè)句子中，（2）、（9）為祈使句，（4）為疑問句，（5）、（6）雖然是陳述句，但（5）沒有確定的真值，其真假隨x、y取值的不同而有改變，（6）是悖論(Paradox)（即由真能推出假，由假也能推出真），因而（2）、（4）、（5）、（6）、（9）均不是命題。（1）、（3）、（7）、（8）、（10）都是命題，其中（10）雖然現(xiàn)在無法判斷真假，但隨著科技的進(jìn)步是可以判定真假的。需要進(jìn)一步指出的是，命題的真假只要求它有就可以，而不要求立即給出。如例1.1.1的（8）1+101=110，它的真假意義通常和上下文有關(guān)，當(dāng)作為二進(jìn)制的加法時(shí)，它是真命題，否則為假命題。還有的命題的真假不能馬上給出，如例1.1.1的（10），但它確實(shí)有真假意義。1.1.2命題分類根據(jù)命題的結(jié)構(gòu)形式，命題分為原子命題和復(fù)合命題。定義1.1.2不能被分解為更簡(jiǎn)單的陳述語句的命題稱為原子命題(SimpleProposition)。由兩個(gè)或兩個(gè)以上原子命題組合而成的命題稱為復(fù)合命題(CompoundProposition)。例如，例1.1.1中的命題全部為原子命題，而命題“小王和小李都去公園。”是復(fù)合命題，是由“小王去公園?！迸c“小李去公園?！眱蓚€(gè)原子命題組成的。1.1.3命題標(biāo)識(shí)符定義1.1.3表示原子命題的符號(hào)稱為命題標(biāo)識(shí)符(Identifier)。通常用大寫字母A，B，C，…，P，Q，…等表示命題，如P：今天下雨。命題標(biāo)識(shí)符依據(jù)表示命題的情況，分為命題常元和命題變?cè)?。一個(gè)表示確定命題的標(biāo)識(shí)符稱為命題常元（或命題常項(xiàng)）(Propositionalconstant)；沒有指定具體內(nèi)容的命題標(biāo)識(shí)符稱為命題變?cè)ɑ蛎}變項(xiàng)）(PropositionalVariable)。命題變?cè)恼嬷登闆r不確定，因而命題變?cè)皇敲}。只有給命題變?cè)狿一具體的命題取代時(shí)，P有了確定的真值，P才成為命題。習(xí)題1.1判斷下列語句是否為命題，若是，指出其真值。外面下雨嗎？7能被2整除。2x+3<4。請(qǐng)關(guān)上門。小紅在教室里。指出下列命題是原子命題還是復(fù)合命題。小李一邊看書，一邊聽音樂。北京不是中國(guó)的首都。大雁北回，春天來了。不是東風(fēng)壓倒西風(fēng)，就是西風(fēng)壓倒東風(fēng)。張三與李四在吵架。1.2邏輯聯(lián)結(jié)詞本節(jié)主要介紹5種常用的邏輯聯(lián)結(jié)詞(LogicalConnectives)，分別是“非”（否定聯(lián)結(jié)詞）、“與”（合取聯(lián)結(jié)詞）、“或”（析取聯(lián)結(jié)詞）、“若…則…”（條件聯(lián)結(jié)詞）、“…當(dāng)且僅當(dāng)…”（雙條件聯(lián)結(jié)詞），通過這些聯(lián)結(jié)詞可以把多個(gè)原子命題復(fù)合成一個(gè)復(fù)合命題。下面分別給出各自的符號(hào)形式及真值情況。1.2.1否定聯(lián)結(jié)詞定義1.2.1設(shè)P為一命題，P的否定(Negation)是一個(gè)新的命題，記為（讀作非P）。規(guī)定若P為T，則為F；若P為F，則為T。的取值情況依賴于P的取值情況，真值情況見表1-1。表1-1P1001在自然語言中，常用“非”、“不”、“沒有”、“無”、“并非”等來表示否定。例1.2.1P：上海是中國(guó)的城市。：上海不是中國(guó)的城市。P是真命題，是假命題。Q：所有的海洋動(dòng)物都是哺乳動(dòng)物。：不是所有的海洋動(dòng)物都是哺乳動(dòng)物。Q為假命題，為真命題。1.2.2合取聯(lián)結(jié)詞定義1.2.2設(shè)P、Q為兩個(gè)命題，P和Q的合取(Conjunction)是一個(gè)復(fù)合命題，記為PQ（讀作P與Q），稱為P與Q的合取式。規(guī)定P與Q同時(shí)為T時(shí)，PQ為T，其余情況下，PQ均為F。聯(lián)結(jié)詞“”的定義見表1-2。表1-2聯(lián)結(jié)詞“”的定義PQPQ000010100111顯然P的真值永遠(yuǎn)是假，稱為矛盾式。在自然語言中，常用“既…又…”、“不但…而且…”、“雖然…但是…”、“一邊…一邊…”等表示合取。例1.2.2（1）今天下雨又刮風(fēng)。設(shè)P：今天下雨。Q：今天刮風(fēng)。則（1）可表示為PQ（2）貓吃魚且太陽從西方升起。設(shè)P：貓吃魚。Q：太陽從西方升起。則（2）可表示為PQ（3）張三雖然聰明但不用功。P：張三聰明。Q：張三用功。則（3）可表示為PQ需要注意的是，在自然語言中，命題（2）是沒有實(shí)際意義的，因?yàn)镻與Q兩個(gè)命題是互不相干的，但在數(shù)理邏輯中是允許的，數(shù)理邏輯中只關(guān)注復(fù)合命題的真值情況，并不關(guān)心原子命題之間是否存在著內(nèi)在聯(lián)系。析取聯(lián)結(jié)詞定義1.2.3設(shè)P、Q為兩個(gè)命題，P和Q的析取(Disjunction)是一個(gè)復(fù)合命題，記為PQ（讀作P或Q），稱為P與Q的析取式。規(guī)定當(dāng)且僅當(dāng)P與Q同時(shí)為F時(shí)，PQ為F，否則PQ均為T。析取聯(lián)結(jié)詞“”的定義見表1-3。表1-3聯(lián)結(jié)詞“”的定義PQPQ000011101111顯然的真值永遠(yuǎn)為真，稱為永真式。析取聯(lián)結(jié)詞“”與漢語中的“或”二者表達(dá)的意義不完全相同，漢語中的“或”可表達(dá)“排斥或”，也可以表達(dá)“可兼或”，而從析取聯(lián)結(jié)詞的定義可看出，“”允許P、Q同時(shí)為真，因而析取聯(lián)結(jié)詞“”是可兼或。對(duì)于“排斥或”將在1.6中論述。例1.2.3（1）小王愛打球或跑步。（2）他身高1.8m或1.85m。（1）為可兼或，（2）為排斥或。設(shè)P：小王愛打球。Q：小王愛跑步。則（1）可表示為PQ設(shè)P：他身高1.8米。Q：他身高1.85米。則（2）可表示為（PQ）（PQ）1.2.4條件聯(lián)結(jié)詞定義1.2.4設(shè)P、Q為兩個(gè)命題，P和Q的條件(Conditional)命題是一個(gè)復(fù)合命題，記為PQ（讀作若P則Q），其中P稱為條件的前件，Q稱為條件的后件。規(guī)定當(dāng)且僅當(dāng)前件P為T，后件Q為F時(shí)，PQ為F，否則PQ均為T。條件聯(lián)結(jié)詞“”的定義見表1-4。表1-4聯(lián)結(jié)詞“”的定義PQPQ001011100111在自然語言中，常會(huì)出現(xiàn)的語句如“只要P就Q”、“因?yàn)镻所以Q”、“P僅當(dāng)Q”、“只有Q才P”、“除非Q才P”等都可以表示為“PQ”的形式。例1.2.4（1）如果雪是黑色的，則太陽從西方升起。（2）僅當(dāng)天氣好，我才去公園。對(duì)于（1），設(shè)P：雪是黑色的。Q：太陽從西方升起。則（1）可表示為PQ（2）設(shè)R：天氣好。S：我去公園。則（2）可表示為SR1.2.5雙條件聯(lián)結(jié)詞定義1.2.5設(shè)P、Q為兩個(gè)命題，其復(fù)合命題PQ稱為雙條件(Biconditional)命題，PQ讀作P當(dāng)且僅當(dāng)Q。規(guī)定當(dāng)且僅當(dāng)P與Q真值相同時(shí)，PQ為T，否則PQ均為F。雙條件聯(lián)結(jié)詞“”的定義如表1-5所示。表1-5PQPQ001010100111例1.2.5（1）雪是黑色的當(dāng)且僅當(dāng)2+2>4。（2）燕子北回，春天來了。（1）設(shè)P：雪是黑色的。Q：2+2>4。則（1）可表示為PQ，其真值為T。（2）設(shè)R：燕子北回。S：春天來了。則（2）可表示為RS，其真值為T。與前面的聯(lián)結(jié)詞一樣，條件聯(lián)結(jié)詞和雙條件聯(lián)結(jié)詞連接的兩個(gè)命題之間可以沒有任何的因果聯(lián)系，只要能確定復(fù)合命題的真值即可。習(xí)題1.21．指出下列命題的真值：若2+2>4，則太陽從西方升起。若a，則aA。胎生動(dòng)物當(dāng)且僅當(dāng)是哺乳動(dòng)物。指南針永指北方，除非它旁邊有磁鐵。除非ABCD是平行四邊形,否則它的對(duì)邊不都平行。2．令P：天氣好。Q：我去公園。請(qǐng)將下列命題符號(hào)化。如果天氣好，我就去公園。只要天氣好，我就去公園。只有天氣好，我才去公園。我去公園，僅當(dāng)天氣好?；蛘咛鞖夂茫蛘呶胰ス珗@。天氣好，我去公園。1.3命題公式與翻譯1.3.1命題公式上一節(jié)介紹了5種常用的邏輯聯(lián)結(jié)詞，利用這些邏輯聯(lián)結(jié)詞可將具體的命題表示成符號(hào)化的形式。對(duì)于較為復(fù)雜的命題，需要由這5種邏輯聯(lián)結(jié)詞經(jīng)過各種相互組合以得到其符號(hào)化的形式，那么怎樣的組合形式才是正確的、符合邏輯的表示形式呢？定義1.3.1（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）稱為基礎(chǔ)，（2）、（3）稱為歸納，（4）稱為界限。由定義知,命題公式是沒有真假的，僅當(dāng)一個(gè)命題公式中的命題變?cè)毁x以確定的命題時(shí)，才得到一個(gè)命題。例如在公式中，把命題“雪是白色的。”賦給，把命題“2+2>4?！辟x給，則公式被解釋為假命題；但若的賦值不變，而把命題“2+2=4?！辟x給，則公式被解釋為真命題。定義中的符號(hào),不同于具體公式里的、、等符號(hào)，它可以用來表示任意的命題公式。例1.3.1，，等都是命題公式，而，，等都不是命題公式。為了減少命題公式中使用括號(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)可以省去。例1.3.2也可以寫成，也可寫成，也可寫成，而中的括號(hào)不能省去。定義1.3.2設(shè)是命題公式的一部分，且也是命題公式，則稱為的子公式。例如及都是公式的子公式；、及都是公式的子公式。1.3.2命題的符號(hào)化有了命題公式的概念之后，就可以把自然語言中的一些命題翻譯成命題邏輯中的符號(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é)詞，將原子命題分別連接起來，組成復(fù)合命題的符號(hào)化形式。把命題符號(hào)化，是不管具體內(nèi)容而突出思維形式的一種方法。注意在命題符號(hào)化時(shí)，要正確地分析和理解自然語言命題，不能僅憑文字的字面意思進(jìn)行翻譯。例1.3.3張三或李四都可以做這件事。設(shè)：張三可以做這件事。：李四可以做這件事。則命題符號(hào)化為：，而不是。例1.3.4（1）只有你走，我才留下。這個(gè)命題的意義也可以理解為：如果我留下了，那么你一定走了。設(shè)：你走。：我留下。則命題符號(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è)原子命題，“…與…是表兄弟?！北硎緝蓚€(gè)對(duì)象之間的關(guān)系?！皬埲潜硇值堋！奔啊袄钏氖潜硇值??！倍疾皇敲}。所以上述命題只能符號(hào)化為的形式。其中：張三與李四是表兄弟。例1.3.5將下列命題符號(hào)化。如果明天早上下雨或下雪，則我不去學(xué)校。如果明天早上不下雨且不下雪，則我去學(xué)校。如果明天早上不是雨夾雪，則我去學(xué)校。當(dāng)且僅當(dāng)明天早上不下雨且不下雪時(shí)，我才去學(xué)校。設(shè)：明天早上下雨。：明天早上下雪。：我去學(xué)校。符號(hào)化為：符號(hào)化為：符號(hào)化為：符號(hào)化為：例1.3.6將下列命題符號(hào)化。如果小王和小張都不去，則小李去。如果小王和小張不都去，則小李去。設(shè)：小王去。：小張去。：小李去。符號(hào)化為：符號(hào)化為：或例1.3.7將下列命題符號(hào)化。（1）說離散數(shù)學(xué)無用且枯燥無味是不對(duì)的。（2）若天不下雨，我就上街；否則在家。對(duì)于（1），設(shè)：離散數(shù)學(xué)是有用的。：離散數(shù)學(xué)是枯燥無味的。則命題符號(hào)化為：。對(duì)于（2），設(shè)：天下雨。：我上街。：我在家。則命題符號(hào)化為：。通過上述的例題可以看出，要正確地將自然語言中的聯(lián)結(jié)詞翻譯成恰當(dāng)?shù)倪壿嬄?lián)結(jié)詞，必須要正確地理解各原子命題之間的關(guān)系。習(xí)題1.31．判斷下列各式子是否是命題公式（1）（2） （3）（4）（5）（6）2．將下列命題符號(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)城，除非下雨。（7）如果太陽沒出來，則或者下雨或者陰天而且溫度下降。（8）指南針永指南北，除非它旁邊有磁鐵。（9）說邏輯枯燥無味和毫無價(jià)值是不對(duì)的。（10）人不犯我，我不犯人；人若犯我，我必犯人。1.4真值表與等價(jià)公式1.4.1真值表定義1.4.1設(shè)，，…，是出現(xiàn)在命題公式中的全部命題變?cè)?，給，，…，各指定一個(gè)真值，稱為對(duì)公式的一個(gè)賦值（或解釋或真值指派）。若指定的一組值使公式的真值為1，則這組值稱為公式的成真賦值。若指定的一組值使公式的真值為0，則這組值稱為公式的成假賦值。例如，對(duì)公式，賦值011（即令，則可得到公式的真值為1；若賦值000，則公式真值為0。因此，011為公式的一個(gè)成真賦值；000為公式的一個(gè)成假賦值。除了上述的兩種賦值外，公式的賦值還有000，001，…等。一般的結(jié)論是在含有n個(gè)命題變?cè)拿}公式中，共有種賦值。定義1.4.2將命題公式在所有賦值下的取值情況列成表，稱為公式的真值表(TruthTable)。構(gòu)造真值表的基本步驟：（1）找出公式中所有的命題變?cè)?，，…，，按二進(jìn)制從小到大的順序列出種賦值。（2）當(dāng)公式較為復(fù)雜時(shí)，按照運(yùn)算的順序列出各個(gè)子公式的真值。（3）計(jì)算整個(gè)命題公式的真值。例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.4.2等價(jià)公式定義1.4.3給定兩個(gè)命題公式，設(shè)，，…，是出現(xiàn)在命題公式中的全部命題變?cè)?，若給，，…，任一組賦值，公式和的真值都對(duì)應(yīng)相同，則稱公式與等價(jià)或邏輯相等(Equivalence)，記作。需要注意的是，“”不是邏輯聯(lián)結(jié)詞，因而“”不是命題公式，只是表示兩個(gè)命題公式之間的一種等價(jià)關(guān)系，即若，和沒有本質(zhì)上的區(qū)別，最多只是和具有不同的形式而已?！啊本哂腥缦碌男再|(zhì)：（1）自反性：。（2）對(duì)稱性：若，則。（3）傳遞性：若，，則。給定n個(gè)命題變?cè)鶕?jù)公式的形成規(guī)則，可以形成許多個(gè)形式各異的公式，但是有很多形式不同的公式具有相同的真值表。因此引入公式等價(jià)的概念，其目的就是將復(fù)雜的公式簡(jiǎn)化。下面介紹兩種證明公式等價(jià)的方法。1．真值表法由公式等價(jià)的定義可知，利用真值表可以判斷任何兩個(gè)公式是否等價(jià)。例1.4.2證明證明命題公式與的真值表見表1-9。由表1-9可知，在任意賦值下與兩者的真值均對(duì)應(yīng)相同。因此表1-9與的真值表001111011000100100111111例1.4.3判斷公式與二者是否等價(jià)。證明公式與的真值表見表1-10。表1-10與的真值表0011011010011111可見真值表中的最后兩列值不完全相同，因此公式與不等價(jià)。從理論上來講，利用真值表法可以判斷任何兩個(gè)命題公式是否等價(jià)，但是真值表法并不是一個(gè)非常好的方法，因?yàn)楫?dāng)公式中命題變?cè)^多時(shí)，其計(jì)算量較大，例如當(dāng)公式中有四個(gè)變?cè)獣r(shí)，需要列出=16種賦值情況，計(jì)算較為繁雜。因此，通常采用其他的證明方法。這種證明方法是先用真值表法驗(yàn)證出一些等價(jià)公式，再用這些等價(jià)公式來推導(dǎo)出新的等價(jià)公式，以此作為判斷兩個(gè)公式是否等價(jià)的基礎(chǔ)。下面給出12組常用的等價(jià)公式，它們是進(jìn)一步推理的基礎(chǔ)。牢記并熟練運(yùn)用這些公式是學(xué)好數(shù)理邏輯的關(guān)鍵之一。（1）雙重否定律：（2）結(jié)合律：，，（3）交換律：，，（4）分配律：，（5）冪等律：，（6）吸收律：，（7）德.摩根律：，（8）同一律：（9）零律：（10）否定律：（11）條件等價(jià)式：（12）雙條件等價(jià)式：上述12組公式均可以通過構(gòu)造真值表法來證明。2．等值演算法定理1.4.1（代入規(guī)則）在一個(gè)永真式中，任何一個(gè)原子命題變?cè)霈F(xiàn)的每一處用另一個(gè)公式代入，所得的公式仍為永真式。證明：因?yàn)橛勒媸綄?duì)于任何指派，其真值都是1，與每個(gè)命題變?cè)概傻恼婕贌o關(guān)，所以，用一個(gè)命題公式代入到原子命題變?cè)霈F(xiàn)的每一處，所得到的命題公式的真值仍為1。例如，是永真式，將原子命題變?cè)么牒蟮玫降氖阶尤詾橛勒媸?。定?.4.2（置換規(guī)則）設(shè)是命題公式的一個(gè)子公式，若，如果將公式中的用來置換，則所得到的公式與公式等價(jià)，即。證明：因?yàn)?，所以在相?yīng)變?cè)娜我环N指派情況下，與的真值相同，故以取代后，公式與公式在相應(yīng)的指派情況下真值也必相同，因此。例如，利用置換，則。從定理可以看出，代入規(guī)則是對(duì)原子命題變?cè)?，而置換規(guī)則可對(duì)命題公式進(jìn)行；代入必須處處代入，替換可以部分或全部替換；代入規(guī)則可以用來擴(kuò)大永真式的個(gè)數(shù)，替換規(guī)則可以增加等價(jià)式的個(gè)數(shù)。有了上述的12組等價(jià)公式及代入規(guī)則和置換規(guī)則后，就可以推演出更多的等價(jià)式。由已知等價(jià)式推出另外一些等價(jià)式的過程稱為等值演算(EquivalentCalculation)。例1.4.4證明下列公式等價(jià)。（1）（2）證明（1）（2）例1.4.5某件事情是甲、乙、丙、丁4人中某一個(gè)人干的。詢問4人后回答如下：（1）甲說是丙干的；（2）乙說我沒干；（3）丙說甲講的不符合事實(shí)；（4）丁說是甲干的。若其中3人說的是真話，一人說假話，問是誰干的？解設(shè)：這件事是甲干的。：這件事是乙干的。：這件事是丙干的。：這件事是丁干的。4個(gè)人所說的命題分別用、、、表示，則（1）、（2）、（3）、（4）分別符號(hào)化為：；；；則3人說真話，一人說假話的命題符號(hào)化為：其中同理所以，當(dāng)為真時(shí)，為真，即這件事是甲干的。本題也可以從題干直接找出相互矛盾的兩個(gè)命題作為解題的突破口。甲、丙兩人所說的話是相互矛盾的，必有一人說真話，一人說假話，而4個(gè)人中只有一人說假話，因此乙、丁兩人必說真話，由此可斷定這件事是甲干的。例1.4.6在某次球賽中，3位球迷甲、乙、丙對(duì)某球隊(duì)的比賽結(jié)果進(jìn)行猜測(cè)。甲說：該球隊(duì)不會(huì)得第一名，是第二名。乙說：該球隊(duì)不會(huì)得第二名，是第一名。丙說：該球隊(duì)不會(huì)得第二名，也不會(huì)是第三名。比賽結(jié)束后，結(jié)果證實(shí)甲、乙、丙3人中有一人猜的全對(duì)，有一人猜對(duì)一半，有一人猜的全錯(cuò)。試分析該球隊(duì)究竟是第幾名。解設(shè)：該球隊(duì)獲得第一名。：該球隊(duì)獲得第二名。：該球隊(duì)獲得第三名。則、、中必然有一個(gè)真命題，兩個(gè)假命題。設(shè)甲、乙、丙3人所說的命題分別用，，表示。則有，，。設(shè)甲、乙、丙的判斷全對(duì)分別用、、表示，甲、乙、丙的判斷對(duì)一半分別用、、表示，甲、乙、丙的判斷全錯(cuò)分別用、、表示。則有：。（由于該球隊(duì)不可能既是第一名又是第二名，所以）。。。。。。。。甲、乙、丙3人中有一人全對(duì)，有一人猜對(duì)一半，有一人全錯(cuò)的命題符號(hào)化為其中，。同理，，，（由于該球隊(duì)不可能既是第一名，又是第三名），。因此，若為真，只有為真。因而為真命題，為假命題。即該球隊(duì)獲得第二名。甲的判斷全對(duì)，乙的判斷全錯(cuò)，丙的判斷對(duì)一半。例1.4.7、、、4人進(jìn)行百米競(jìng)賽，觀眾甲、乙、丙對(duì)比賽的結(jié)果進(jìn)行預(yù)測(cè)。甲：第一，第二；乙：第二，第三；丙：第二，第四。比賽結(jié)束后發(fā)現(xiàn)甲、乙、丙每個(gè)人的預(yù)測(cè)結(jié)果都各對(duì)一半。試問實(shí)際名次如何（假如無并列者）？解設(shè)表示第名，表示第名，表示第名，表示第名，。則由題意有（1）（2）（3）因?yàn)檎婷}的合取仍為真命題，所以（1）（2）（4）（3）（4）因此，第二，第四，第一，第三。習(xí)題1.41．寫出下列公式的真值表。（1）（2）（3）（4）2．證明下列等價(jià)公式。（1）（2）（3）（4）3．甲、乙、丙、丁4人參加考試后，有人問他們誰的成績(jī)最好，甲說：不是我。乙說：是丁。丙說：是乙。丁說：不是我。已知4個(gè)人的回答只有一個(gè)人符合實(shí)際，問成績(jī)最好的是誰？4．3個(gè)球迷估計(jì)比賽結(jié)果，球迷甲說：大連實(shí)德第一，北京國(guó)安第二。球迷乙說：上海申花第二，長(zhǎng)春亞泰第四。球迷丙說：大連實(shí)德第二，長(zhǎng)春亞泰第四。結(jié)果3人估計(jì)的都不全對(duì)，但都對(duì)了一半，問4支球隊(duì)的名次（假設(shè)無并列次序）。5．如果，是否有？如果，是否有？如果，是否有？6．化簡(jiǎn)下列公式：（1）（2）（3）1.5命題公式的分類與蘊(yùn)含式1.5.1命題公式的分類從前述的真值表中可以看到，有的命題公式無論對(duì)命題歐變?cè)骱畏N賦值，其對(duì)應(yīng)的真值恒為或恒為，如例1.4.1的（2）、（3）；而有的公式對(duì)應(yīng)的真值則是有有，如例1.4.1的（1）。根據(jù)命題公式在不同賦值下的真值情況，可以對(duì)命題公式進(jìn)行分類。定義1.5.1設(shè)為一命題公式，對(duì)公式所有可能的賦值：（1）若的真值永為，則稱公式為重言式(Tautology)或永真式。（2）若的真值永為，則稱公式為矛盾式(Contradictory)或永假式。（3）若至少存在一種賦值使得的真值為，則稱公式為可滿足式(Satisfiable)。由定義可知，根據(jù)命題公式的真值情況，公式可分為兩大類，即矛盾式和可滿足式。重言式一定是可滿足式，但反之不成立。用真值表法可以判定公式的類型：若真值表的最后一列全為1，則公式為重言式；若最后一列全為0，則公式為矛盾式；若最后一列至少有一個(gè)1，則公式為可滿足式。在1.4的例1.4.1中，（1）為可滿足式，（2）為矛盾式，（3）為重言式。用真值表法判斷公式的類型方法簡(jiǎn)單，但當(dāng)變?cè)^多時(shí)，計(jì)算量大，在后面的章節(jié)中還要介紹其他的方法。1.5.2重言式與矛盾式的性質(zhì)定理1.5.1任何兩個(gè)重言式的析取或合取，仍是一個(gè)重言式。證明：設(shè)、為兩個(gè)重言式，則無論對(duì)與的分量作何種指派，總有，，故，。定理1.5.2一個(gè)重言式，對(duì)同一分量用任何合式公式置換，所得公式仍為一重言式。證明：因?yàn)橹匮允降恼嬷蹬c分量的指派無關(guān)，所以對(duì)同一分量用任何合式公式置換后，重言式的真值仍永為真。例如，為一重言式，用置換，所得新公式仍為重言式。對(duì)于矛盾式，也有類似于定理1.5.1和定理1.5.2的結(jié)果。定理1.5.3設(shè)、為兩個(gè)命題公式，當(dāng)且僅當(dāng)為重言式。證明：若，則在、所含命題變?cè)娜魏沃概上?，與的真值都相同，即恒為真。若為重言式，由重言式的定義知，在對(duì)、所含命題變?cè)娜魏沃概上拢c都有相同的真值，即。例1.5.1證明為重言式。證明由例1.4.2知，故依據(jù)定理1.5.3有為重言式。1.5.3蘊(yùn)含式下面討論的重言式。定義1.5.2設(shè)、為兩個(gè)命題公式，若為重言式，則稱“蘊(yùn)含(Implication)”，記作。注意“”與“”一樣，都不是邏輯聯(lián)結(jié)詞，因而也不是公式。是用來表示由條件能夠推導(dǎo)出結(jié)論，或稱為可以由邏輯推出。蘊(yùn)含關(guān)系具有如下的性質(zhì)：（1）自反性：對(duì)任意的公式，有。（2）反對(duì)稱性：對(duì)任意的公式、，若且，則有。（3）傳遞性：對(duì)任意的公式、、，若、，則有。由于不具有對(duì)稱性，即與不等價(jià)，因此，對(duì)于而言，稱為它的逆換式，稱為它的反換式，稱為它的逆反式。在上述的4個(gè)公式中，，。定理1.5.4的充分必要條件是且。證明：若，則為重言式，而，故均為重言式，即且。反之，若且，則均為重言式，于是為重言式，即為重言式，故。由定義1.5.2知，要證明，只需證明為重言式即可。因此，前面介紹的真值表法和等值演算法均可應(yīng)用。下面綜合介紹證明的各種方法。1．真值表法例1.5.2證明證明只需證明為重言式。真值表見表1-11。表1-11的真值表00010101100111112．等值演算法例1.5.3證明證明只需證明為重言式。即3．分析法分析法包括以下兩種形式：（1）假定前件為真，推出后件為真，則。（2）假定后件為假，推出前件為假，則。理由是：（1）若為真，則可能為真也可能為假，但由假設(shè)推出為真，所以否定了為真、為假的可能，只能是為真、也為真。所以為重言式，即。對(duì)于（2），若后件為假，則前件可能為真也可能為假。若為真，為假，則為假；若為假，為假，則為真。而由假設(shè)推知為假，因此否定了為真，為假的可能。所以為重言式，即。例1.5.4證明（1）（2）證明（1）假設(shè)前件為真，則為真，為真；由此有為假，為真。因此。（2）假設(shè)后件為假，若為真，則為假，有為假。若為假，則為真，有為假。綜上，若后件為假，無論為真還是假，前件均為假。因此。需要指出的是，在例1.5.4的（2）中，因?yàn)椴恢赖恼嬷登闆r，所以要分情況討論。例1.5.5分析下列論證的有效性。條件：香煙有利于健康；如果香煙有利于健康，那么醫(yī)生就會(huì)把香煙作為藥品開給病人。結(jié)論：醫(yī)生把香煙作為藥品開給病人。解設(shè)：香煙有利于健康。：醫(yī)生把香煙作為藥品開給病人。上述推理符號(hào)化為：。其證明同例1.5.4的（2下面給出的蘊(yùn)含式其正確性均可用上述的推理方法進(jìn)行證明。（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）習(xí)題1.51．判斷下列命題公式的類型。（1）。（2）。（3）。（4）。2．證明下列各蘊(yùn)含式。（1）（2）（3）（4）3．判斷下列命題的真假。（1）重言式的否定是矛盾式。（2）矛盾式的否定是重言式。（3）不是重言式就是矛盾式。（4）不是矛盾式就是重言式。（5）重言式必是可滿足式。（6）不是矛盾式就是可滿足式。（7）可滿足式未必是重言式。（8）不是可滿足式就是矛盾式。4．設(shè)P表示命題“8是偶數(shù)”，Q表示命題“糖果是甜的”。試以句子寫出：（1）。（2）的逆換式。（3）的反換式。（4）的逆反式。5．?dāng)⑹鱿铝懈鱾€(gè)命題的逆換式和逆反式，并以符號(hào)寫出。（1）如果下雨，我不去。（2）僅當(dāng)你走我將留下。（3）如果我不能獲得更多幫助，我不能完成這個(gè)任務(wù)。6．檢驗(yàn)下列論證的有效性。如果我學(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é)詞組1.6.1其它邏輯聯(lián)結(jié)詞前面介紹了5種常用的邏輯聯(lián)結(jié)詞，，，和，但是這5種聯(lián)結(jié)詞還不能很廣泛地直接用來表達(dá)命題間的聯(lián)系，為此，下面再介紹4種聯(lián)結(jié)詞。1．不可兼析取(排斥或/異或)(exclusiveor)（）定義1.6.1設(shè)、為兩個(gè)命題公式，復(fù)合命題稱為異或。規(guī)定的真值為，當(dāng)且僅當(dāng)與的真值不相同，否則的真值為。聯(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è)、為兩個(gè)命題公式，復(fù)合命題稱為和的“與非式”。當(dāng)且僅當(dāng)與的真值都為時(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è)、為兩個(gè)命題公式，復(fù)合命題稱為和的“或非式”。當(dāng)且僅當(dāng)與的真值都為時(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è)、為兩個(gè)命題公式，復(fù)合命題稱為和的“條件否定”。當(dāng)且僅當(dāng)?shù)恼嬷禐椋恼嬷禐闀r(shí)，的真值為，否則的真值為。聯(lián)結(jié)詞“”的定義見表1-15。表1-15聯(lián)結(jié)詞“”的定義000010101110從真值表中易見，。1.6.2最小功能完備聯(lián)結(jié)詞組到目前為止，共定義了9個(gè)聯(lián)結(jié)詞，但這些聯(lián)結(jié)詞在表達(dá)命題時(shí)并不是缺一不可，因?yàn)榘承┞?lián)結(jié)詞的公式可以用含有另外一些聯(lián)結(jié)詞的公式來進(jìn)行表示。如這說明“”可以轉(zhuǎn)化為“”，而“”可轉(zhuǎn)化為由“”與“”表示，而“”與“”又可以相互轉(zhuǎn)化。對(duì)于另外的4個(gè)聯(lián)結(jié)詞，由于，，，，這說明任意的一個(gè)命題公式最終都可以轉(zhuǎn)化為僅包含，或，的命題公式來等價(jià)地表示。定義1.6.5設(shè)是一個(gè)聯(lián)結(jié)詞的集合，若任意一個(gè)命題公式都可用中聯(lián)結(jié)詞構(gòu)成的公式來表示，則稱為功能完備聯(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é)詞組來表示命題。習(xí)題1.61．將下列命題公式轉(zhuǎn)化為僅含聯(lián)結(jié)詞的命題公式。（1）（2）（3）2．將下列命題公式用只含和的等價(jià)式表達(dá)，并要求盡可能簡(jiǎn)單。（1）（2）（3）3．證明不是最小功能完備連接詞組。4．證明是最小功能完備連接詞組。1.7對(duì)偶與范式1.7.1對(duì)偶式與對(duì)偶原理1．對(duì)偶式定義1.7.1在只含有邏輯聯(lián)結(jié)詞，，的命題公式中，若把與互換，與互換得到一個(gè)新的命題公式，則稱是的對(duì)偶式(DualisticFormula)，或稱與互為對(duì)偶式。顯然。例1.7.1寫出下列公式的對(duì)偶式。（1）（2）（3）解上述公式的對(duì)偶式為（1）（2）（3）例1.7.2求，的對(duì)偶式。解因?yàn)?，所以的?duì)偶式為。同理，的對(duì)偶式為。2．對(duì)偶原理(DualityPrinciple)一個(gè)僅含有邏輯聯(lián)結(jié)詞，，的命題公式和它的對(duì)偶式之間具有如下等值關(guān)系：定理1.7.1設(shè)公式為僅含有邏輯聯(lián)結(jié)詞，，及命題變?cè)?，，…，的命題公式，是的對(duì)偶式，則有：（1）（2）證明：由德.摩根定律，故同理例1.7.3設(shè)，證明證明因?yàn)?，所以，而所以定?.7.2（對(duì)偶原理）若公式，則。證明：設(shè)，，…，是出現(xiàn)在命題公式，中所有的命題變?cè)?，因?yàn)?，即，所以。由定?.7.1得，即為重言式故也為重言式即對(duì)偶定律表明，利用公式的對(duì)偶式可以擴(kuò)大等價(jià)式的數(shù)量，也可以簡(jiǎn)化證明。例如與這兩個(gè)等價(jià)公式的兩端互為對(duì)偶式，因而只需證明一個(gè)等價(jià)公式成立即可。1.7.2命題公式的范式從前面的討論可知,存在大量互不相同的命題公式，實(shí)際上互為等價(jià)，因此，有必要引入命題公式的標(biāo)準(zhǔn)形式，使得相互等價(jià)的命題公式具有相同的標(biāo)準(zhǔn)形式。這無疑對(duì)判別兩個(gè)命題公式是否等價(jià)以及判定命題公式的類型是一種好方法，同時(shí)對(duì)命題公式的簡(jiǎn)化和推證也是十分有益的。1．簡(jiǎn)單析取式與簡(jiǎn)單合取式定義1.7.2單個(gè)的命題變?cè)捌浞穸ㄐ问椒Q為文字。如，等。定義1.7.3僅由有限個(gè)文字組成的析取式稱為簡(jiǎn)單析取式。僅由有限個(gè)文字組成的合取式稱為簡(jiǎn)單合取式。例如，，，等都是簡(jiǎn)單析取式；，，，等都是簡(jiǎn)單合取式。一個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式。定理1.7.3簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變?cè)捌浞穸ㄐ问?。證明：設(shè)公式為簡(jiǎn)單析取式，含有命題變?cè)Ｈ敉瑫r(shí)含有及，顯然為重言式。若為重言式但不同時(shí)含有某個(gè)命題變?cè)捌浞穸ㄐ问?，不妨設(shè)，若真值均為0，而真值均為1，則的真值為0，這與為重言式矛盾。對(duì)于簡(jiǎn)單合取式也有類似的性質(zhì)。定理1.7.4簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變?cè)捌浞穸ㄐ问健ＷC明同定理1.7.3。2．析取范式與合取范式定義1.7.4由有限個(gè)簡(jiǎn)單合取式組成的析取式稱為析取范式（DisjunctiveNormalForm）。由有限個(gè)簡(jiǎn)單析取式組成的合取式稱為合取范式（ConjunctiveNormalForm）。析取范式與合取范式統(tǒng)稱為范式。例如，，等是析取范式。，等是合取范式。對(duì)于單獨(dú)的一個(gè)命題變?cè)蚱浞穸瓤梢钥闯墒俏鋈》妒剑挚煽闯墒呛先》妒?。?dāng)然既可以看成是簡(jiǎn)單析取式，又可以看成是簡(jiǎn)單合取式。至于，若把它看作為簡(jiǎn)單合取式的析取，則它是析取范式；若把它看成是文字的析取，則它是合取范式。同理，，等既是析取范式，又是合取范式。定理1.7.5（范式存在定理）任何一個(gè)命題公式都存在著與之等價(jià)的析取范式和合取范式。從析取范式和合取范式的定義可知，范式中不存在除了，，以外的其余邏輯聯(lián)結(jié)詞。下面給出求公式范式的步驟：（1）消去除，，以外公式中出現(xiàn)的所有邏輯聯(lián)結(jié)詞。（2）將否定聯(lián)結(jié)詞消去或內(nèi)移到各命題變?cè)?。如，；；。?）利用分配律、結(jié)合律將公式轉(zhuǎn)化為合取范式或析取范式。如，；。例1.7.4求的析取范式和合取范式。解（析取范式）（合取范式）例1.7.5求的析取范式。解上面所求的最后兩個(gè)等價(jià)的公式都是原公式的析取范式，所以命題公式的析取范式不唯一。例1.7.6求的合取范式。解上面所求的最后兩個(gè)等價(jià)的公式都是原公式的合取范式，所以命題公式的合取范式不唯一。3．范式的應(yīng)用利用范式判斷命題公式類型的問題稱為判定問題。定理1.7.6一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合取式都是矛盾式。一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式都是重言式。例1.7.7判斷下列公式的類型。（1）（2）解（1）由定理1.7.6可知，為矛盾式。（2）由定理1.7.6可知，為重言式。1.7.3命題公式的主析取范式和主合取范式由于一個(gè)命題公式的范式不唯一，這就使得范式的應(yīng)用受到了一定的限制，為了使任意命題公式化為唯一的標(biāo)準(zhǔn)形式，下面引入主范式的概念。1．主析取范式定義1.7.5在含有n個(gè)命題變?cè)暮?jiǎn)單合取式中，若每個(gè)命題變?cè)捌浞穸ú煌瑫r(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，則稱該簡(jiǎn)單合取式為小項(xiàng)。例如，兩個(gè)命題變?cè)蜕傻?個(gè)小項(xiàng)為：，，，。三個(gè)命題變?cè)蜕傻?個(gè)小項(xiàng)為：，，，，，，，。一般說來，n個(gè)命題變?cè)灿袀€(gè)小項(xiàng)。小項(xiàng)的二進(jìn)制編碼為：命題變?cè)醋帜疙樞蚺帕?，命題變?cè)c1對(duì)應(yīng)，命題變?cè)姆穸ㄅc0對(duì)應(yīng)，則得到小項(xiàng)的二進(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）全體小項(xiàng)的析取式為永真式。定義1.7.6由若干個(gè)不同的小項(xiàng)組成的析取式稱為主析取范式(ThePrincipalDisjunctiveNormalForm)。與公式等價(jià)的主析取范式稱為的主析取范式。定理1.7.7任意含個(gè)命題變?cè)姆怯兰偈矫}公式都存在著與之等價(jià)的主析取范式，并且其主析取范式是唯一的。證明：設(shè)是公式的析取范式，即。若的某個(gè)簡(jiǎn)單合取式中不含有命題變?cè)捌浞穸?，將展成形式，繼續(xù)這個(gè)過程，直到所有的簡(jiǎn)單合取式成為小項(xiàng)。然后消去重復(fù)的項(xiàng)及矛盾式后，得到公式的主析取范式。下證唯一性。若公式有兩個(gè)與之等價(jià)的主析取范式和，則。由于和是的不同的主析取范式，不妨設(shè)小項(xiàng)只出現(xiàn)在中而不在中，于是的二進(jìn)制表示為的成真賦值、的成假賦值，這與矛盾。因而公式的主析取范式是唯一的。一個(gè)命題公式的主析取范式可通過兩種方法求得，一是由公式的真值表得出，即真值表法；另一是由基本等價(jià)公式推出，即等值演算法。（1）真值表法定理1.7.8在真值表中，命題公式的真值為真的賦值所對(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）列出公式的真值表。（2）將真值表中的最后一列中的1的賦值所對(duì)應(yīng)的小項(xiàng)寫出。（3）將這些小項(xiàng)進(jìn)行析取。例1.7.8利用真值表法求的主析取范式。解的真值表見表1-17。表1-17的真值表001011101110從表1-17中可以看出，該公式在其真值表的00行、01行、10行處取真值1，所以。例1.7.9用真值表法求的主析取范式。解的真值表見表1-18。表1-18的真值表0000000101010000110110000101011101111111從表1-18中可以看出，該公式在其真值表的001行、011行、101行、110行和111行處取真值1，所以。例1.7.10設(shè)公式的真值表見表1-19，求公式的主析取范式。解由真值表可看出公式有3組成真賦值，分別出現(xiàn)在000行，100行和111行，所以公式的主析取范式為。表1-19公式的真值表00010010010001101001101011001111（2）等值演算法除了用真值表法來求一個(gè)命題公式的主析取范式外，還可以利用公式的等值演算方法來推導(dǎo)。具體的求解步驟如下：1）求公式的析取范式；2）除去中所有永假的析取項(xiàng)；3）若的某個(gè)簡(jiǎn)單合取式中不含有某個(gè)命題變?cè)膊缓?，則將展成形式。（4）將重復(fù)出現(xiàn)的命題變?cè)?、矛盾式及重?fù)出現(xiàn)的小項(xiàng)都消去。（5）將小項(xiàng)按順序排列。例1.7.11求的主析取范式。解例1.7.12求的主析取范式。解2．主合取范式定義1.7.7在含有n個(gè)命題變?cè)暮?jiǎn)單析取式中，若每個(gè)命題變?cè)捌浞穸ㄐ问讲煌瑫r(shí)出現(xiàn)，但二者之一必出現(xiàn)且僅出現(xiàn)一次，則稱該簡(jiǎn)單析取式為大項(xiàng)。例如，兩個(gè)命題變?cè)蜕傻?個(gè)大項(xiàng)為：，，，。3個(gè)命題變?cè)?、和生成?個(gè)大項(xiàng)為：，，，，，，，。一般說來，n個(gè)命題變?cè)灿袀€(gè)大項(xiàng)。大項(xiàng)的二進(jìn)制編碼為：命題變?cè)醋帜疙樞蚺帕?，命題變?cè)c0對(duì)應(yīng)，命題變?cè)姆穸ㄅc1對(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)制）000111011011101101111110（十進(jìn)制）從這個(gè)真值表中可以看到，沒有兩個(gè)大項(xiàng)是等價(jià)的，且每個(gè)大項(xiàng)都只對(duì)應(yīng)著和的一組真值指派使得該大項(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)的合取式必為永假式。定義1.7.8由若干個(gè)不同的大項(xiàng)組成的合取式稱為主合取范式(ThePrincipalConjunctiveNormalForm)。與公式等價(jià)的主合取范式稱為的主合取范式。定理1.7.9任意含個(gè)命題變?cè)姆怯勒媸矫}公式都存在著與之等價(jià)的主合取范式，并且其主合取范式是唯一的。與主析取范式的求解方法相類似，主合取范式同樣可通過真值表法或等值演算法求得。（1）真值表法定理1.7.10在真值表中，命題公式的真值為假的賦值所對(duì)應(yīng)的大項(xiàng)的合取即為命題公式的主合取范式。證明方法與定理1.7.8的證明相類似。利用真值表法求主合取范式的基本步驟為：（1）列出公式的真值表。（2）將真值表中的最后一列中的0的賦值所對(duì)應(yīng)的大項(xiàng)寫出。（3）將這些大項(xiàng)進(jìn)行合取。例1.7.13求的主合取范式。解的真值表見表1-21。表1-21的真值表0010011110001111從上表可看出，公式在00行，10行處取真值0，所以。（2）等值演算法具體的求解步驟如下：1）求公式的合取范式；2）除去中所有永真的合取項(xiàng)；3）若的某個(gè)簡(jiǎn)單析取式中不含有某個(gè)命題變?cè)?，也不含，則將展成形式。4）將重復(fù)出現(xiàn)的命題變?cè)?、永真式及重?fù)出現(xiàn)的大項(xiàng)都消去。5）將大項(xiàng)按順序排列。例1.7.14求的主合取范式。解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)的主合（析）取范式。如例1.7.14中的主合取范式為已求出，則主析取范式為，然后寫出相應(yīng)的小項(xiàng)即可。例1.7.15求的主析取范式與主合取范式。解4．主范式的應(yīng)用（1）命題公式等價(jià)性的判定由于每個(gè)命題公式都存在著與之等價(jià)的唯一的主析取范式和主合取范式，因此，如果兩個(gè)命題公式等價(jià)，則相應(yīng)的主范式也對(duì)應(yīng)相同。例1.7.16判斷與是否等價(jià)。解因?yàn)樗浴?2)命題公式類型的判定定理1.7.11設(shè)是含個(gè)命題變?cè)拿}公式，則1）為永真式當(dāng)且僅當(dāng)?shù)闹魑鋈》妒街泻腥總€(gè)小項(xiàng)。2）為矛盾式當(dāng)且僅當(dāng)?shù)闹骱先》妒街泻腥總€(gè)大項(xiàng)。3）若的主析取范式中至少含有一個(gè)小項(xiàng)，則是可滿足式。例1.7.17判斷下列命題公式的類型。1)2)解因此，命題公式1)為永真式。因此，命題公式2)為可滿足式。（3）解決實(shí)際問題例1.7.18張三說李四在說謊，李四說王五在說謊，王五說張三、李四都在說謊。請(qǐng)問3人中到底誰在說謊？解設(shè)：張三說真話（即沒有說謊）。：李四說真話。：王五說真話。則張三說李四在說謊可符號(hào)化為：。類似地，其余兩句話可符號(hào)化為：，。上述已知條件可表示為公式的真值表見表1-22。表1-22公式的真值表00000010010101101000101011001110則公式的主析取范式為，即張三在說謊，李四說真話，王五說謊話。例1.7.19某單位要從4位職工甲、乙、丙、丁中挑選兩位職工去外地旅游，由于工作需要，選派時(shí)要考慮下列要求：（1）甲、乙兩人中去且僅去1人。（2）乙和丁不能都去。（3）若丙去，則丁必須去。（4）若丁不去，則甲也不去。問該單位派誰去符合要求？解設(shè)：派甲去旅游。：派乙去旅游。：派丙去旅游。：派丁去旅游。則由已知條件可得命題公式：公式化成主析取范式為故選派方案有：（1）派甲、丙、丁去旅游。（2）派甲、丁去旅游。（3）派乙去旅游。由于單位要派兩位職工去旅游，因此只有方案（2）滿足要求，即派甲、丁去旅游。習(xí)題1.71．寫出下列公式的對(duì)偶式。（1）（2）（3）（4）2．（1）設(shè)，則。（2），則。3．求下列公式的析取范式與合取范式：（1）。（2）。（3）。（4）。4．寫出下列含有3個(gè)命題變?cè)拇箜?xiàng)或小項(xiàng)（腳標(biāo)是十進(jìn)制）。（1）（2）（3）（4）5．在對(duì)、、的真值指派110下，小項(xiàng)取值為，大項(xiàng)取值為。6．求下列命題公式的主析取范式和主合取范式：（1）。（2）。（3）7．判斷下列命題公式的類型：（1）。（2）。（3）。（4）。8．某科研所有三名青年高級(jí)工程師A、B和C。所里要選派他們中的1~2人出國(guó)進(jìn)修，由于所里工作的需要，選派時(shí)必須滿足以下條件：①若A去，則C也去。②若B去，則C不能去。③若C不去，則A或B去。問所里應(yīng)如何選派他們？9．試判斷下列各組命題是否等價(jià)：(1)與。(2)與。1.8推理理論推理是由一個(gè)或幾個(gè)命題推出另一個(gè)命題的思維形式。從結(jié)構(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)用的推理中，常常把本門學(xué)科的一些定律、定理和條件，作為假設(shè)前提，盡管這些前提在數(shù)理邏輯中并非永真，但在推理過程中，卻總是假設(shè)這些命題為真，并使用一些公認(rèn)的規(guī)則，得到另外的命題，形成結(jié)論，這種過程就是論證。定義1.8.1設(shè)和是兩個(gè)命題公式，當(dāng)且僅當(dāng)為一重言式，即，稱是的有效結(jié)論，或可由邏輯推出。這個(gè)定義可以推廣到有個(gè)前提的情況。設(shè)，，…，，是命題公式，當(dāng)且僅當(dāng)…，稱是一組前提，，…，的有效結(jié)論。注意，在形式邏輯中，并不關(guān)心結(jié)論是否真實(shí)，而只在乎由給定的前提，，…，能否推出結(jié)論來，只注意推理的形式是否正確。因此，有效結(jié)論并不一定是正確的，只有正確的前提經(jīng)過正確的推理得到的邏輯結(jié)論才是正確的。在證明有效結(jié)論時(shí)，可以用前面介紹的真值表法或證明蘊(yùn)含關(guān)系的方法來論證結(jié)論的有效性。論證的方法千變?nèi)f化，但基本上歸納起來只有3種方法，即真值表法、直接證法和間接證法。真值表法在此不再討論。1.8.1直接證法直接證法就是由一組命題，利用一些公認(rèn)的推理規(guī)則，根據(jù)已知的等價(jià)式或蘊(yùn)含式，推演出有效結(jié)論，即形式演繹法。直接證法必須遵循下列推理規(guī)則：規(guī)則：前提條件在推導(dǎo)過程中的任何時(shí)候都可以引入使用。規(guī)則：在推導(dǎo)過程中，所證明的結(jié)論、已知的等價(jià)或蘊(yùn)含公式都可以作為后續(xù)證明的前提，命題公式中的任何子公式都可以用與之等價(jià)的命題公式置換。現(xiàn)將常用的蘊(yùn)含式和等價(jià)式列入表1-23和表1-24中。表1-23常用的蘊(yùn)含式表1-24常用的等價(jià)式例1.8.1證明證明（1）（2）（3）（4）（5）（6）（7）（8）例1.8.2證明,,,證明（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）例1.8.3符號(hào)化下述命題并證明結(jié)論的有效性。前提：若是實(shí)數(shù)，則它不是有理數(shù)就是無理數(shù)。若不能表示成分?jǐn)?shù)，則它不是有理數(shù)。是實(shí)數(shù)且不能表示成分?jǐn)?shù)。結(jié)論：是無理數(shù)。證明設(shè)：是實(shí)數(shù)。：是有理數(shù)。：是無理數(shù)。：能表示成分?jǐn)?shù)。則本題即證：，，（1）（2）（3）（4）（5）（6）（7）（8）例1.8.4已知張三或李四的彩票中獎(jiǎng)，如果張三中獎(jiǎng)，你是會(huì)知道的；如果李四中獎(jiǎng)，王五也中獎(jiǎng)了；現(xiàn)在你不知道張三中獎(jiǎng)。試用邏輯推理來確定誰中獎(jiǎng)了？并寫出推理過程。解設(shè)：張三中獎(jiǎng)。：李四中獎(jiǎng)。：王五中獎(jiǎng)。：你知道張三中獎(jiǎng)。由題設(shè)得已知條件：，，，。則推理如下：（1）（2）（3）（4）（5）（6）（7）（8）（9）即李四和王五都中獎(jiǎng)了。1.8.2間接證法間接證法主要有兩種，一種稱之為規(guī)則，還有一種是常用的反證法（也叫歸謬法）。1．附加前提證明法（規(guī)則）由公式的等價(jià)性知……，所以要證明…，只需證明…即可，這種方法稱為規(guī)則。例1.8.5證明由，，能有效推出。證明（1）（附加前提）（2）（3）（4）（5）（6）（7）（8）例1.8.6“如果春暖花開，燕子就會(huì)飛回北方，如果燕子飛回北方，則冰雪融化，所以如果冰雪沒有融化，則沒有春暖花開”。證明這些語句構(gòu)成一個(gè)正確的推理。解設(shè)：春暖花開。：燕子飛回北方。：冰雪融化。則上述論斷轉(zhuǎn)化成要證明，。證（1）（附加前提）（2）（3）（4）（5）（6）例1.8.7“如果努力工作，或?qū)⑸钣淇?；如果生活愉快，那么將不努力工作；如果愉快，將不愉快。所以如果努力工作，將不愉快”。問這些語句是否構(gòu)成一個(gè)正確的推理？解設(shè)：努力工作。：將生活愉快。：將生活愉快。：將愉快。前提：，，結(jié)論：（1）（附加前提）（2）（3）（4）（5）（6）（7）（8）（9）因此，上述推理是正確的。2．歸謬法歸謬法（反證法）是經(jīng)常使用的一種間接證明方法，是將結(jié)論的否定形式作為附加前提與給定的前提條件一起推證來導(dǎo)出矛盾。它的基本原理是：當(dāng)且僅當(dāng)為矛盾式。這是因?yàn)楫?dāng)且僅當(dāng)為重言式，即永真，當(dāng)且僅當(dāng)永假。例1.8.8，，，證明（1）（附加前提）（2）（3）（4）（5）（6）（7）（8）（9）（10）（矛盾式）由（10）得出了矛盾，根據(jù)歸謬法說明原推理正確。例1.8.9，，證明（1）（附加前提）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（矛盾式）由（11）得出了矛盾，根據(jù)歸謬法說明原推理正確。習(xí)題1.81．證明。2．用間接證法證明3．如果2是偶數(shù)，則3是奇數(shù)；或者2是偶數(shù)或者2整除3。結(jié)果2不整除3，所以3是奇數(shù)。證明上述論斷正確。4．某公司若拒絕增加工資，則罷工不會(huì)停止，除非罷工超過一年并且公司經(jīng)理辭職。問：如果公司拒絕增加工資，而罷工又剛剛開始，罷工是否會(huì)停止？5．“如果下雨，春游就會(huì)改期；如果沒有球賽，春游就不會(huì)改期。結(jié)果沒有球賽，所以沒有下雨?！弊C明上述論斷正確。6．如果考試及格，那我高興。若我高興，那么我飯量增加。我的飯量沒增加，所以我考試沒有及格。試對(duì)上述論證構(gòu)造證明。7．證明RS是前提CD，C→R，D→S的有效結(jié)論。8．證明P∨Q,QR,PS,┐SR∧(Q∨P)。9．證明(A→BC)(B→┐A)(D→┐C)(A→┐D)。第六章代數(shù)系統(tǒng)6.1第129頁1．證明：任取，，因此，二元運(yùn)算*是可交換的；任取，因此，運(yùn)算*是可結(jié)合的。該運(yùn)算的么元是0，0的逆元是0，2的逆元是2，其余元素沒有逆元。2．證明：任取，由知，，*運(yùn)算不是可交換的。任取，由，知，，*運(yùn)算是可結(jié)合的。任取，，可知N中的所有元素都是等冪的。*運(yùn)算有右么元，任取，，知N中的所有元素都是右么元。*運(yùn)算沒有左么元。證明：采用反證法。假定為*運(yùn)算的左么元，取，由*的運(yùn)算公式知，由么元的性質(zhì)知，，得，這與相矛盾，因此，*運(yùn)算沒有左么元。3．解：=1\*GB3①任取因此對(duì)于任意的都有，即二元運(yùn)算*是可交換的。=2\*GB3②任取因此對(duì)于任意的，都有，即二元運(yùn)算*是可結(jié)合的。=3\*GB3③設(shè)幺元為，則，即幺元為1.=4\*GB3④對(duì)于所有的元素，都有，所以所有元素都是等冪的。4．解：設(shè)=1\*GB3①設(shè)是上的二元運(yùn)算，則是一個(gè)從的映射。求上有多少個(gè)二元運(yùn)算即相當(dāng)于求這樣的映射的個(gè)數(shù)。由于，映射的個(gè)數(shù)為，即上有個(gè)二元運(yùn)算。=2\*GB3②可交換即設(shè)集合，要求上可交換的二元運(yùn)算的個(gè)數(shù)，即相當(dāng)于求映射的個(gè)數(shù)，，其中：具體如下圖所示：此時(shí)映射的個(gè)數(shù)推廣到有個(gè)元素時(shí)，映射的個(gè)數(shù)=3\*GB3③單位元素即幺元，若存在必唯一。設(shè)集合，若幺元為1，則有此時(shí)的二元運(yùn)算的個(gè)數(shù)相當(dāng)于求映射的個(gè)數(shù)，其中：映射的個(gè)數(shù)為幺元為2，3，4時(shí)同理，因此集合上有個(gè)有單位元素的二元運(yùn)算。推廣到有個(gè)元素時(shí)，具有單位元素的二元運(yùn)算的個(gè)數(shù)為。5．解：任取=1\*GB3①對(duì)于任意的都有，故二元運(yùn)算*是可交換的。若，，此時(shí)故二元運(yùn)算*是不可結(jié)合的。不存在這樣使得任意的都有，因此，二元運(yùn)算*不含幺元。=2\*GB3②對(duì)于任意的都有，故二元運(yùn)算*是可交換的。故二元運(yùn)算*是不可結(jié)合的。不存在這樣使得任意的都有，因此，二元運(yùn)算*不含幺元。=3\*GB3③因此，二元運(yùn)算*是不可交換的。故二元運(yùn)算*是不可結(jié)合的。由于二元運(yùn)算*不是可交換的，所以不存在這樣使得任意的都有，因此，二元運(yùn)算*不含幺元。6．設(shè)是中的任意元素。由于二元運(yùn)算*是可結(jié)合的，故又對(duì)于任意的，若，則故即對(duì)于中的任意元素，都有，所以中的每一個(gè)元素都是等冪的。6.2第137頁4．證明：首先，U和V都只含有一個(gè)二元運(yùn)算，因此是同類型的；第二，的定義域是自然數(shù)集合，值域是，是V定義域的子集。第三，驗(yàn)證是否運(yùn)算的像等于像的運(yùn)算。任取，分情況討論：x和y都可以表示成，設(shè)，那么，x和y都不能表示成，那么也不能表示成,x可以表示成，y不能表示成，那么也不能表示成,x不可以表示成，y能表示成，那么也不能表示成,可知，無論x和y如何取值，都能夠保證。綜上所述，是U到V的同態(tài)映射。5．證明：設(shè)，首先，U和V都僅有一個(gè)二元運(yùn)算，因此U和V是同類型的；第二，U和V的定義域大小相同，具備構(gòu)成雙射函數(shù)的條件；第三，尋找特異元素，U中么元是a，右零元是c，三個(gè)元素都是等冪元；V中么元是3，右零元是1，三個(gè)元素都是等冪元。第四，在U和V的定義域之間構(gòu)造雙射函數(shù)，使得。把*運(yùn)算表中的元素都用f下的像點(diǎn)代替，得321321321222111調(diào)整表頭的順序?yàn)?，2，3，轉(zhuǎn)變?yōu)橄卤?23123111222123跟V中運(yùn)算表完全相同，因此代數(shù)系統(tǒng)和是同構(gòu)的。6.證明：(1)兩個(gè)代數(shù)系統(tǒng)都只存在一個(gè)二元運(yùn)算，故滿足同型。(2)構(gòu)造函數(shù)，使得fX=～X，顯然是雙射函數(shù)。(3)對(duì)于任意的ff故fX∩Y由(1),(2),(3)可知，兩代數(shù)系統(tǒng)是同構(gòu)的。7.解：當(dāng)時(shí)，零同態(tài)；當(dāng)時(shí)，恒等映射，自同態(tài)；當(dāng)時(shí)，；當(dāng)時(shí)，；當(dāng)時(shí)，；當(dāng)時(shí)，自同構(gòu)。8.證明：的個(gè)復(fù)數(shù)根可表示成：(1)與都含有一個(gè)二元運(yùn)算，故為同型的。(2)與定義域大小相同，具備構(gòu)成雙射函數(shù)的條件。(3)構(gòu)造雙射函數(shù)對(duì)于任意的，因此，。由(1),(2),(3)可知，同構(gòu)于。9．證明：(1)是代數(shù)系統(tǒng)到當(dāng)?shù)耐瑧B(tài)映射又是的子代數(shù)(2)對(duì)于，必存在，使得，由于為代數(shù)系統(tǒng)到當(dāng)?shù)耐瑧B(tài)映射，又是的子代數(shù)故對(duì)*運(yùn)算封閉，即對(duì)運(yùn)算滿足封閉性。由(1),(2),(3)可知,為的子代數(shù)。6.3第141頁1．解：解：首先，判斷是否是等價(jià)關(guān)系。任取，由于，因此，是自反的；任取，若，即（），則，，因此是對(duì)稱的；任取，若，則（），（），于是，，因此，可知是可傳遞的。因此，是等價(jià)關(guān)系。其次，判斷關(guān)于*是否滿足代換性質(zhì)。任取，若，即存在某個(gè)，滿足則于是由于，因此，，關(guān)于*是滿足代換性質(zhì)。綜上所述，是上的同余關(guān)系。2.解：（1）對(duì)于+運(yùn)算，在二元運(yùn)算下，任取，驗(yàn)證下式是否成立取，可知滿足，，但，即?？芍獙?duì)于運(yùn)算+，R不滿足代換性質(zhì)。（2）對(duì)于運(yùn)算，在二元運(yùn)算下，任取，若，，則必然滿足于是可得。由取值的任意性可知，對(duì)于運(yùn)算，R滿足代換性質(zhì)。3．證明：(1)對(duì)于，有由于對(duì)具有代換性質(zhì)，所以有由此可知：同理可知：因是等價(jià)關(guān)系，故是可傳遞的，所以有所以對(duì)具有代換性質(zhì)。(2)對(duì)具有代換性質(zhì)，但對(duì)不具有代換性質(zhì)，因4．設(shè)代數(shù)系統(tǒng)，為同余關(guān)系。(1)即證：為同余關(guān)系證明：為等價(jià)關(guān)系若對(duì)任意有,,…則，，…，，…為同余關(guān)系所以為同余關(guān)系。(2)為等價(jià)關(guān)系若對(duì)任意有,,…未必有，，…，，…因此，可能不滿足代換性質(zhì)所以未必是同余關(guān)系。5．（1）解：R不是上的同余關(guān)系，取則，但是，，因此，不滿足代換性質(zhì)。（2）,當(dāng)且僅當(dāng)解：R不是上的同余關(guān)系，取，則，，但，，R不滿足可傳遞性，不是等價(jià)關(guān)系。（3）解：R不是上的同余關(guān)系，取取則，但是，，因此，不滿足代換性質(zhì)。（4）解：R不是上的同余關(guān)系，取，則，但，即，R不滿足對(duì)稱性，不是等價(jià)關(guān)系。6.4第143頁1.解：（1）設(shè)其中，任取下面通過運(yùn)算表構(gòu)造*運(yùn)算（這里僅給出了一個(gè)運(yùn)算表，另一個(gè)照推）<0,0><0,1><0,2><1,0><1,1><1,2><0,0><0,0><0,0><0,0><1,0><1,0><1,0><0,1><0,0><0,1><0,2><1,0><1,1><1,2><0,2><0,0><0,2><0,1><1,0><1,2><1,1><1,0><1,0><1,0><1,0><0,0><0,0><0,0><1,1><1,0><1,1><1,2><0,0><0,1><0,2><1,2><1,0><1,2><1,1><0,0><0,2><0,1>（2）設(shè)其中，任取運(yùn)算表的構(gòu)造方法與上同。2.(1)證明：任取，和*可交換是可交換的。(2)任取和*可結(jié)合是可結(jié)合的。3.012345001234511234502234501334501244501235501234<0,0><0,1><0,2><1,0><1,1><1,2><0,0><0,0><0,0><0,0><1,0><1,0><1,0><0,1><0,0><0,1><0,2><1,0><1,1><1,2><0,2><0,0><0,2><0,1><1,0><1,2><1,1><1,0><1,0><1,0><1,0><0,0><0,0><0,0><1,1><1,0><1,1><1,2><0,0><0,1><0,2><1,2><1,0><1,2><1,1><0,0><0,2><0,1>證明：=1\*GB3①與都只有一個(gè)二元運(yùn)算，故為同型的。=2\*GB3②與定義域大小相同，具備構(gòu)成雙射函數(shù)的條件。=3\*GB3③構(gòu)造雙射函數(shù)由上圖可知，像的運(yùn)算=運(yùn)算的像所以與是同構(gòu)的。6.5第155頁1.（1）半群（2）半群（3）半群（4）獨(dú)異點(diǎn)，么元0（5）不是半群，取a=b=1,c=2，則不滿足結(jié)合律（6）不是半群，因?yàn)閨|不是二元運(yùn)算；（7）半群（8）獨(dú)異點(diǎn)，么元0（9）半群（10）獨(dú)異點(diǎn)，么元為恒等關(guān)系；（11）獨(dú)異點(diǎn)，么元為a2.（1）二元運(yùn)算表如下圖所示：GCD1234681224111111111212122222311313133412142444612326266812142848121234641212241234681224（2）,其中。（假定為叢X到X的雙射函數(shù)）解：X到X有6個(gè)雙射函數(shù)，分別用表示，設(shè)構(gòu)造運(yùn)算表如下：第七章圖論6.1第164頁1.畫出圖的圖示，指出其中哪些圖是簡(jiǎn)單圖。（1）不是簡(jiǎn)單圖。（2）不是簡(jiǎn)單圖。（3）是簡(jiǎn)單圖。2.寫出圖7-8的抽象數(shù)學(xué)定義。（1）解：，其中，，（2）解：，其中，，3.證明：在n階簡(jiǎn)單有向圖中，完全有向圖的邊數(shù)最多，其邊數(shù)為。證明：簡(jiǎn)單有向圖是沒有自環(huán)，沒有平行邊的有向圖，只要兩個(gè)不同的結(jié)點(diǎn)之間才能有邊。完全有向圖是每個(gè)結(jié)點(diǎn)的出度和入度都是n-1的簡(jiǎn)單有向圖，也就是每個(gè)結(jié)點(diǎn)都有到其他所有結(jié)點(diǎn)的邊，因此，完全有向圖的邊數(shù)最多。在完全有向圖中，所有結(jié)點(diǎn)的出度之和為n(n-1)，所有結(jié)點(diǎn)的入度之和為n(n-1)，設(shè)邊的個(gè)數(shù)為m，由握手定理可知，2m=n(n-1)+n(n-1)，即m=n(n-1)，得證。4.證明：3度正則圖必有偶數(shù)個(gè)結(jié)點(diǎn)。證明：設(shè)三度正則圖的結(jié)點(diǎn)個(gè)數(shù)為n，那么所有結(jié)點(diǎn)的度數(shù)之和為3n，由握手定理可知，邊的個(gè)數(shù)為3n/2=1.5n，由于邊的個(gè)數(shù)一定是整數(shù)，因此，n為偶數(shù)。得證。5.在一次集會(huì)中，相互認(rèn)識(shí)的人會(huì)彼此握手，試證明：與奇數(shù)個(gè)人握手的人數(shù)是偶數(shù)個(gè)。證明：設(shè)集會(huì)上的人一共有m個(gè)，可分為兩部分，一部分為與奇數(shù)個(gè)人握手的人，設(shè)為x個(gè)，另一部分為與偶數(shù)個(gè)人握手的人，為m-x個(gè)。由于握手是相互的，即一次握手，兩個(gè)人握手的次數(shù)都加1，一共加2，因此，集會(huì)上所有人的握手次數(shù)之和為偶數(shù)。與偶數(shù)個(gè)人握手的人，這些人的握手次數(shù)之和為（其中，都是偶數(shù)），為偶數(shù)。與奇數(shù)個(gè)人握手的人，這些人的握手次數(shù)之和為（其中，為基數(shù)），由于所有人的握手次數(shù)之和偶數(shù)，因此也要為偶數(shù)，即又因?yàn)榧?，因此x為偶數(shù)，即與奇數(shù)個(gè)人握手的人是偶數(shù)個(gè)，得證。6.證明：圖7-7中的兩個(gè)圖同構(gòu)。證明：首先，給這兩幅圖標(biāo)上對(duì)應(yīng)