離散數(shù)學(xué) 習(xí)題解答

1、第2章 習(xí)題解答2.1 本題沒(méi)有給出個(gè)體域,因而使用全總個(gè)體域. (1) 令是鳥 會(huì)飛翔.命題符號(hào)化為.(2)令為人.愛(ài)吃糖命題符號(hào)化為或者(3)令為人. 愛(ài)看小說(shuō).命題符號(hào)化為.(4) 為人. 愛(ài)看電視.命題符號(hào)化為.分析 1°如果沒(méi)指出要求什么樣的個(gè)體域，就使用全總個(gè)休域，使用全總個(gè)體域時(shí)，往往要使用特性謂詞。（1）-（4）中的都是特性謂詞。2° 初學(xué)者經(jīng)常犯的錯(cuò)誤是，將類似于（1）中的命題符號(hào)化為即用合取聯(lián)結(jié)詞取代蘊(yùn)含聯(lián)結(jié)詞，這是萬(wàn)萬(wàn)不可的。將（1）中命題敘述得更透徹些，是說(shuō)“對(duì)于宇宙間的一切事物百言，如果它是鳥，則它會(huì)飛翔?！币蚨?hào)化應(yīng)該使用聯(lián)結(jié)詞而不能使用。若使

2、用，使（1）中命題變成了“宇宙間的一切事物都是鳥并且都會(huì)飛翔。”這顯然改變了原命題的意義。3° （2）與（4）中兩種符號(hào)化公式是等值的，請(qǐng)讀者正確的使用量詞否定等值式，證明（2），（4）中兩公式各為等值的。2.2 (1)d (a),(b),(c)中均符號(hào)化為其中此命題在中均為真命題。（2） 在中均符號(hào)化為其中，此命題在（a）中為假命題，在(b)(c)中均為真命題。（3）在中均符號(hào)化為其中此命題在中均為假命題，在(c)中為真命題。分析 1°命題的真值與個(gè)體域有關(guān)。2° 有的命題在不同個(gè)體域中，符號(hào)化的形式不同，考慮命題“人都呼吸”。在個(gè)體域?yàn)槿祟惣蠒r(shí)，應(yīng)符號(hào)化為這

3、里，呼吸，沒(méi)有引入特性謂詞。在個(gè)體域?yàn)槿倐€(gè)體域時(shí)，應(yīng)符號(hào)化為這里，為人，且為特性謂詞。呼吸。23 因題目中未給出個(gè)體域，因而應(yīng)采用全總個(gè)體域。（1） 令：是大學(xué)生，是文科生，是理科生，命題符號(hào)化為（2）令是人，是化，喜歡，命題符 號(hào)化為（3）令是人，犯錯(cuò)誤，命題符號(hào)化為或另一種等值的形式為（4）令在北京工作，是北京人，命題符號(hào)化為或（5）令是金屬，是液體，溶解在y中，命題符號(hào)化為（6）令與y是對(duì)頂角，與y相等，命題符號(hào)化為分析 （2），（5），（6）中要使用2無(wú)謂詞，用它們來(lái)描述事物之間的關(guān)系。2.4 （1）對(duì)所有的x，存在著y，使得，在中為真命題，在中為假命題。（2）存在著對(duì)所有的y，都有

4、，在中為真命題，在中為假命題。（3）對(duì)所有x，存在著y，使得，在中均為假命題，而在中為真命題。（4）存在著x，對(duì)所有的y，都有，在中都是假命題。（5）對(duì)所有的x，存在著y，使得在中都是真命題。（6）存在x，對(duì)所有的y，都有，在中為真命題，在中為假命題。（7）對(duì)于所有的x和y，存在著z，使得，在中為真命題，在中為假命題。2.5 （1）取解釋為：個(gè)體域（實(shí)數(shù)集合），為有理數(shù)，能表示成分?jǐn)?shù)，在下，的含義為“對(duì)于敘何實(shí)數(shù)x而言，若x為有理數(shù)，則x能表示成分?jǐn)?shù)”，簡(jiǎn)言之為“有理數(shù)都能表示成分?jǐn)?shù)?！痹诖颂N(yùn)含式中，當(dāng)前件為真時(shí)，后件也為真，不會(huì)出現(xiàn)前件為真，后件為假的情況，所以在下，為真命題。在在下，的含義

5、為“對(duì)于任何實(shí)數(shù)x,x既為有理數(shù)，又能表示成分?jǐn)?shù)?！比。瑒t顯然為假，所以，在下，為假命題.(2) 取解釋為:個(gè)體域D=N(自然數(shù)集合), 為奇數(shù), 為偶數(shù),在下,的含義為“存在自然數(shù)x,x發(fā)既為奇數(shù)，又為偶數(shù)?！比?，則為假，于是為真，這表明為真命題。分析 本題說(shuō)明這里，表示A與B不等值，以后遇到，含義相同。在一階邏輯中，將命題符號(hào)化時(shí)，當(dāng)引入特性謂詞（如題中的之后，全稱量詞后往往使用聯(lián)結(jié)詞而不使用，而存在量詞后往往使用，而不使用，如果用錯(cuò)了，會(huì)將真命題變成假命題，或者將假命題變成真命題。26 在解釋R下各式分別化為（1）（2）（3）（4）易知，在解釋R下，（1），（2）為假；，（3）（4）為真

6、。27 給定解釋為：個(gè)體域D=N（自然數(shù)集合），為奇數(shù)，為偶數(shù)。（1）在解釋下，公式被解釋為“如果所有的自然數(shù)不是奇數(shù)就是偶數(shù)，則所有自然數(shù)全為奇數(shù)，或所有自然數(shù)全為偶數(shù)。”因?yàn)樘N(yùn)含式的前件為真，后件為假，所以真值為假。（2）在下，公式解釋為“如果存在著自然數(shù)為奇數(shù)，并且存在著自然為偶數(shù)，則存在著自然數(shù)既是奇數(shù)，又是偶數(shù)?！庇捎谔N(yùn)含式的前件為真，后件為假，后以真值為假。分析 本題說(shuō)明全稱量詞對(duì)析取不滿足分配律，存在量詞對(duì)合取不滿足分配律。2.8 令在A中，無(wú)自由出現(xiàn)的個(gè)體變項(xiàng)，所以A為閉式。給定解釋：個(gè)體域D=N（整數(shù)集合），為正數(shù)，為負(fù)數(shù)，在下，A的含義為“對(duì)于任意的整數(shù)x和y，如果x為正整

7、數(shù)，y為負(fù)整數(shù)，則?！边@是真命題。設(shè)解釋：個(gè)體域D=R（R整數(shù)集合），為有理數(shù)，為無(wú)理數(shù)，在下，A的含義為“對(duì)于任意的實(shí)數(shù)x和y，如果x為有理數(shù)，y為元理數(shù)，則?！边@是假命題。分析 閉式在任何解釋下不是真就是假，不可能給出解釋I, 使得閉式在I下真值不確定，這一點(diǎn)是閉式的一個(gè)重要特征。而非封閉的公式就沒(méi)有這個(gè)特征。2.9 取和，則和都是非土產(chǎn)的公式，在中，x, y都是自由出現(xiàn)的，在中，y是自出現(xiàn)的。取解釋I為，個(gè)體域D=N（N為自然數(shù)集合），為。在I下，為為假，所以在I下，真值不確定，即在I下的真值也是命題。在I下，為當(dāng)時(shí)，它為真；時(shí)為假，在I下的真值也不確定。分析 非閉式與 閉式的顯著區(qū)別是

8、，前者可能在某些解釋下，真值不確定，而后者對(duì)于任何解釋真值都確定，即不是真就是假。當(dāng)然非閉式也可以是邏輯有效式（如），也可能為矛盾式（如，也可能不存在其值不確定的解釋。210 （1） （消去量詞等值式） （德·摩根律） （消去量詞等值式）（2） （消去量詞等值式） （德·摩根律） （消去量詞等值式）211 （1） 令為人。長(zhǎng)著綠色頭發(fā)。本命題直接符號(hào)化為而 （量詞否定等值式） （德·摩根律） （蘊(yùn)含等值式）最后一步得到的公式滿足要求（使用全稱量詞），將它翻譯成自然語(yǔ)言，即為“所有的人都不長(zhǎng)綠色頭發(fā)”。可見(jiàn)得“沒(méi)有人長(zhǎng)著綠色頭發(fā)。”與“所有人都不長(zhǎng)綠色頭發(fā)。”是同一

9、命題的兩種不同的敘述方法。（2）令是北京人去過(guò)香山。命題直接符號(hào)化為而 （雙重否定律） （理詞否定等值式） （德·摩根律） （蘊(yùn)含等值式）最后得到的公式滿足要求（只含全稱量詞），將它翻譯成自然語(yǔ)言，即為“并不是北京人都去過(guò)香山?！笨梢?jiàn)，“有的北京人沒(méi)過(guò)過(guò)香山?！迸c“并不是北京人都去過(guò)香山?！笔峭幻}不同的敘述方法。2.12 （1） （2） （量詞轄域收縮擴(kuò)張等值式）（3） 分析 在有窮個(gè)體域內(nèi)消去量詞時(shí)，應(yīng)將量詞的轄域盡量縮小，例如，在（2）中，首先將量詞轄域縮小了（因?yàn)橹胁缓瑇，所以，可以縮?。?。否則，演算是相當(dāng)麻煩的。見(jiàn)下面的演算：顯然這個(gè)演算比原來(lái)的演算麻煩多了。2.13 在

10、I下（1）所以，在下為假。（2）所以，此公式在I下也是假命題。（3） （量詞分配等值式）所以，此公式在I下為真214 （1） （量詞否定等值式） （約束變項(xiàng)換名規(guī)則） （量詞轄域收縮擴(kuò)張等值式）（2）在以上演算中分別使用了德·摩根律、量詞否定等值式、約束變項(xiàng)換名規(guī)則等。分析 公式的前束范式是不唯一的。（1）中最后兩步都是前束范式，其實(shí)也是（1）中公式的前束范式。215 （1）（2）在以上演算中分別使用了自由變項(xiàng)換名規(guī)則和量詞轄域收縮擴(kuò)張等值式。2.16 （1）錯(cuò)。使用UI，UG，EI，EG規(guī)則應(yīng)對(duì)前束范式，而中公式下不是前束范式，所以，不能使用UI規(guī)則。（2）。中公式為，這時(shí)，因而使

11、用UI規(guī)則時(shí)，應(yīng)得（或），故應(yīng)有而不可能為（3）錯(cuò)。應(yīng)對(duì)使用EG規(guī)則，其中c為特定的使A為真的個(gè)體常項(xiàng)，而不能為個(gè)體變項(xiàng)。（4）錯(cuò)。中公式含個(gè)體變項(xiàng)x，不能使用EG規(guī)則。（5）錯(cuò)。公式含兩個(gè)個(gè)體常項(xiàng)，不能使用EG規(guī)則。（6）錯(cuò)。對(duì)使用EI規(guī)則得，此c應(yīng)使為真，此c不一定使為真。分析 由于的錯(cuò)誤，可能由真前提，推出假結(jié)論。反例如下：設(shè)個(gè)體域?yàn)樽匀粩?shù)集合為偶數(shù)，為素?cái)?shù)，能被3整除，能被4整數(shù)，顯然此時(shí)，與均為真，但為假。其實(shí)在（6）中，應(yīng)為，它是真命題，而為假命題。對(duì)使用EI規(guī)則，得才為真。所以，對(duì)兩個(gè)公式使用EI規(guī)則使用同一個(gè)個(gè)體常項(xiàng)是會(huì)犯錯(cuò)誤的。2.17 （1）證明 前提引入 前提引入 假言推

12、理 EI 附加 UI 假言推理 EG （2）證明： 前提引入 EI 前提引入 UI 假言推理 化簡(jiǎn) 合取 EG 218 令是大熊獵。 產(chǎn)在中國(guó)。歡歡前提：結(jié)論：證明： 前提引入 前提引入 UI 假言推理219令為有理數(shù)。 為實(shí)數(shù)。為整數(shù)。前提：結(jié)論：證明： 前提引入 前提引入 假言推理 EI 附加 UI 假言推理 EG （2）證明： 前提引入 EI 前提引入 UI 化簡(jiǎn) 假言推理 化簡(jiǎn) 與合取 EG分析 在以上證明中，不能如下進(jìn)行。 前提引入 前提引入 UI EI至此，可能犯了錯(cuò)誤，在中取則為真，但為假，就是說(shuō)，由UI規(guī)則得到的c不一定滿足EI規(guī)則，但反之為真，這一點(diǎn)務(wù)必注意。2.20 答案 A：； B：分析 （7）式為非閉式，在個(gè)體域?yàn)檎麛?shù)集Z時(shí)，的真值不能確定，當(dāng)時(shí)為真，當(dāng)時(shí)為假，所以，它不是命題，其余各式都是命題。（5）雖然不是閉式，但它為真。221 答案 A：； B：， C：； D：分析 注意約束變項(xiàng)和自由變項(xiàng)改名規(guī)則的使用。供選答案中，（1）的前束范式只有一個(gè)，就是。而的前束范式有3個(gè)，當(dāng)然它們都是等值的。（3）的前束范式有2個(gè)，就是和。注意，在（3）式中，的轄域?yàn)?，這就決定了它們的前束范式為， （將自由出現(xiàn)的y改名為z）但由于所以，也是（3）的前束范式。222 答案 A：。分析