離散數學習題答案

1、離散數學習題答案習題一及答案：（P14-15）14、將下列命題符號化：（5）李辛與李末是兄弟解：設p：李辛與李末是兄弟，則命題符號化的結果是p（6）王強與劉威都學過法語解：設p：王強學過法語；q：劉威學過法語；則命題符號化的結果是（9）只有天下大雨，他才乘班車上班解：設p：天下大雨；q：他乘班車上班；則命題符號化的結果是（11）下雪路滑，他遲到了解：設p：下雪；q：路滑；r：他遲到了；則命題符號化的結果是15、設p：2+3=5. q：大熊貓產在中國. r：太陽從西方升起.求下列復合命題的真值：（4）解：p=1，q=1，r=0，19、用真值表判斷下列公式的類型：（2）解：列出公式的真值表，如下所

2、示：001111011010100101110001由真值表可以看出公式有3個成真賦值，故公式是非重言式的可滿足式。20、求下列公式的成真賦值：（4）解：因為該公式是一個蘊含式，所以首先分析它的成假賦值，成假賦值的條件是：所以公式的成真賦值有：01，10，11。習題二及答案：（P38）5、求下列公式的主析取范式，并求成真賦值：（2）解：原式 ，此即公式的主析取范式，所以成真賦值為011，111。6、求下列公式的主合取范式，并求成假賦值：（2）解：原式，此即公式的主合取范式，所以成假賦值為100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：（1）解：原式 ，此即主析取范式。主析取范式

3、中沒出現的極小項為，所以主合取范式中含有三個極大項，故原式的主合取范式。9、用真值表法求下面公式的主析取范式：（1）解：公式的真值表如下：00010000011011010110101111111000101101010111001011110101由真值表可以看出成真賦值的情況有7種，此7種成真賦值所對應的極小項的析取即為主析取范式，故主析取范式習題三及答案：（P52-54）11、填充下面推理證明中沒有寫出的推理規(guī)則。前提：結論：s證明： p 前提引入 前提引入 q 析取三段論 前提引入 r 析取三段論 前提引入 s 假言推理15、在自然推理系統(tǒng)P中用附加前提法證明下面推理：（2）前提： 結

4、論：證明：用附加前提證明法。 p 附加前提引入 附加 前提引入 假言推理 s 化簡 附加 前提引入 u 假言推理故推理正確。16、在自然推理系統(tǒng)P中用歸謬法證明下面推理：（1）前提：， 結論：證明：用歸謬法 p 結論的否定引入 前提引入 假言推理 前提引入 析取三段論 前提引入 r 化簡 合取由于，所以推理正確。17、在自然推理系統(tǒng)P中構造下面推理的證明：只要A曾到過受害者房間并且11點以前沒離開，A就是謀殺嫌犯。A曾到過受害者房間。如果A在11點以前離開，看門人會看見他。看門人沒有看見他。所以，A是謀殺嫌犯。解：設p：A到過受害者房間，q：A在11點以前離開，r：A是謀殺嫌犯，s：看門人看見

5、過A。則前提：， 結論：證明： 前提引入 前提引入 拒取式 前提引入 合取引入 前提引入 假言推理習題四及答案：（P65-67）5、在一階邏輯中將下列命題符號化：（2）有的火車比有的汽車快。解：設F(x)：x是火車，G(y)：y是汽車，H(x,y)：x比y快；則命題符號化的結果是：（3）不存在比所有火車都快得汽車。解：設F(x)：x是汽車，G(y)：y是火車，H(x,y)：x比y快；則命題符號化的結果是：或9、給定解釋I如下：(a) 個體域為實數集合R。(b) 特定元素。(c) 函數。(d) 謂詞。給出以下公式在I下的解釋，并指出它們的真值：（2）解：解釋是：，含義是：對于任意的實數x，y，若

6、x-y=0則x<y。該公式在I解釋下的真值為假。14、證明下面公式既不是永真式也不是矛盾式：（1）解：取解釋如下：個體域為全總個體域，：x是兔子，：y是烏龜，：x比y跑得快，則該公式在解釋I下真值是1；取解釋如下：x比y跑得慢，其它同上，則該公式在解釋下真值是0；故公式（1）既不是永真式也不是矛盾式。此題答案不唯一，只要證明公式既不是永真式也不是矛盾式的每個解釋合理即可。習題五及答案：（P80-81）15、在自然推理系統(tǒng)中，構造下面推理的證明：（3）前提：， 結論：證明： 前提引入 置換 UI規(guī)則 前提引入 UI規(guī)則 析取三段論 EG規(guī)則22、在自然推理系統(tǒng)中，構造下面推理的證明：（2）

7、凡大學生都是勤奮的。王曉山不勤奮。所以王曉山不是大學生。解：設F(x)：x為大學生，G(x)：x是勤奮的，c：王曉山則前提：， 結論：證明： 前提引入 UI規(guī)則 前提引入 拒取式25、在自然推理系統(tǒng)中，構造下面推理的證明：每個科學工作者都是刻苦鉆研的，每個刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。王大海是科學工作者，并且是聰明的。所以，王大海在他的事業(yè)中將獲得成功。（個體域為人類集合）解：設F(x)：x是科學工作者，G(x)：x是刻苦鉆研的，H(x)：x是聰明的，I(x)：x在他的事業(yè)中獲得成功，c：王大海則前提：， 結論：證明： 前提引入 化簡 化簡 前提引入 UI規(guī)則 假言推理 合取引

8、入 前提引入 UI規(guī)則 假言推理習題六及答案習題七及答案：（P132-135）*22、給定，A上的關系，試（1）畫出R的關系圖；（2）說明R的性質。2解：1（1） 34 （2）R的關系圖中每個頂點都沒有自環(huán)，所以R是反自反的，不是自反的； R的關系圖中任意兩個頂點如果有邊的都是單向邊，故R是反對稱的，不是對稱的； R的關系圖中沒有發(fā)生頂點x到頂點y有邊、頂點y到頂點z有邊，但頂點x到頂點z沒有邊的情況，故R是傳遞的。26 設，R為A上的關系，R的關系圖如圖7.13所示：（1）求的集合表達式；（2）求r(R), s(R), t(R)的集合表達式。解：（1）由R的關系圖可得所以，可得；（2），46

9、、分別畫出下列各偏序集的哈斯圖，并找出A的極大元、極小元、最大元和最小元。（1）解：哈斯圖如下：eabcdfA的極大元為e、f，極小元為a、f；A的最大元和最小元都不存在。48、設為偏序集，在集合上定義關系T如下：證明T為上的偏序關系。證明：（1）自反性：（2）反對稱性：（3）傳遞性：綜合（1）（2）（3）知T具有自反性、反對稱性和傳遞性，故T為上的偏序關系。習題九及答案：（P179-180）8、（1）（2）。解：（1）（2）11、（3）；解：（3）由*運算的定義可知：，16、習題十一及答案：（P218-219）1、圖11.11給出了6個偏序集的哈斯圖。判斷其中哪些是格。如果不是格，說明理由解

10、：（a）、（c）、（f）是格；因為任意兩個元素構成的集合都有最小上界和最大下界；（b）不是格，因為d,e的最大下界不存在；（d）不是格，因為b,c的最小上界不存在；（e）不是格，因為a,b的最大下界不存在。2、下列各集合低于整除關系都構成偏序集，判斷哪些偏序集是格。（1）L=1，2，3，4，5；（2）L=1，2，3，6，12；解：畫出哈斯圖即可判斷出：（1）不是格，（2）是格。4、設L是格，求以下公式的對偶式：（2）解：對偶式為：，參見P208頁定義11.2。9、針對圖11.11中的每個格，如果格中的元素存在補元，則求出這些補元。解：（a）圖：a,d互為補元，其中a為全下界，d為全上界，b和c都沒有補元；（c）圖：a,f互為補元，其中a為全下界，f為全上界，c和d的補元都是b和e，b和e的補元都是c和d；（f）圖：a,f互為補元，其中a為全下界，f為全上界，b和e互為補元，c和d都沒有補元。10、說明圖11.11中每個格是否為分配格、有補格和布爾格，并說明理由。解：（a）圖：是一條鏈，所以是分配格，b和c都沒有補元，所以不是有補格，所以不是布爾格；（c）圖：a,f互為補元，c和d的補元都是b和e，b和e的補元都是c和d，所以任何元素皆有補元，是有補格； ，所以對運算不滿足分