離散數(shù)學 習題解答

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

2、用，使（1）中命題變成了“宇宙間的一切事物都是鳥并且都會飛翔。”這顯然改變了原命題的意義。3° （2）與（4）中兩種符號化公式是等值的，請讀者正確的使用量詞否定等值式，證明（2），（4）中兩公式各為等值的。2.2 (1)d (a),(b),(c)中均符號化為其中此命題在中均為真命題。（2） 在中均符號化為其中，此命題在（a）中為假命題，在(b)(c)中均為真命題。（3）在中均符號化為其中此命題在中均為假命題，在(c)中為真命題。分析 1°命題的真值與個體域有關(guān)。2° 有的命題在不同個體域中，符號化的形式不同，考慮命題“人都呼吸”。在個體域為人類集合時，應符號化為這

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

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

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

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

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

8、，前者可能在某些解釋下，真值不確定，而后者對于任何解釋真值都確定，即不是真就是假。當然非閉式也可以是邏輯有效式（如），也可能為矛盾式（如，也可能不存在其值不確定的解釋。210 （1） （消去量詞等值式） （德·摩根律） （消去量詞等值式）（2） （消去量詞等值式） （德·摩根律） （消去量詞等值式）211 （1） 令為人。長著綠色頭發(fā)。本命題直接符號化為而 （量詞否定等值式） （德·摩根律） （蘊含等值式）最后一步得到的公式滿足要求（使用全稱量詞），將它翻譯成自然語言，即為“所有的人都不長綠色頭發(fā)”?？梢姷谩皼]有人長著綠色頭發(fā)?！迸c“所有人都不長綠色頭發(fā)?！笔峭?/p>

9、命題的兩種不同的敘述方法。（2）令是北京人去過香山。命題直接符號化為而 （雙重否定律） （理詞否定等值式） （德·摩根律） （蘊含等值式）最后得到的公式滿足要求（只含全稱量詞），將它翻譯成自然語言，即為“并不是北京人都去過香山?！笨梢姡坝械谋本┤藳]過過香山。”與“并不是北京人都去過香山?！笔峭幻}不同的敘述方法。2.12 （1） （2） （量詞轄域收縮擴張等值式）（3） 分析 在有窮個體域內(nèi)消去量詞時，應將量詞的轄域盡量縮小，例如，在（2）中，首先將量詞轄域縮小了（因為中不含x，所以，可以縮?。７駝t，演算是相當麻煩的。見下面的演算：顯然這個演算比原來的演算麻煩多了。2.13 在

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

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

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