離散數(shù)學(xué)習(xí)題答案(共13頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上離散數(shù)學(xué)習(xí)題答案習(xí)題一及答案：（P14-15）14、將下列命題符號(hào)化：（5）李辛與李末是兄弟解：設(shè)p：李辛與李末是兄弟，則命題符號(hào)化的結(jié)果是p（6）王強(qiáng)與劉威都學(xué)過法語解：設(shè)p：王強(qiáng)學(xué)過法語；q：劉威學(xué)過法語；則命題符號(hào)化的結(jié)果是（9）只有天下大雨，他才乘班車上班解：設(shè)p：天下大雨；q：他乘班車上班；則命題符號(hào)化的結(jié)果是（11）下雪路滑，他遲到了解：設(shè)p：下雪；q：路滑；r：他遲到了；則命題符號(hào)化的結(jié)果是15、設(shè)p：2+3=5. q：大熊貓產(chǎn)在中國. r：太陽從西方升起.求下列復(fù)合命題的真值：（4）解：p=1，q=1，r=0，19、用真值表判斷下列公式的類型：（2）解

2、：列出公式的真值表，如下所示：001111011010100101110001由真值表可以看出公式有3個(gè)成真賦值，故公式是非重言式的可滿足式。20、求下列公式的成真賦值：（4）解：因?yàn)樵摴绞且粋€(gè)蘊(yùn)含式，所以首先分析它的成假賦值，成假賦值的條件是：所以公式的成真賦值有：01，10，11。習(xí)題二及答案：（P38）5、求下列公式的主析取范式，并求成真賦值：（2）解：原式 ，此即公式的主析取范式，所以成真賦值為011，111。6、求下列公式的主合取范式，并求成假賦值：（2）解：原式，此即公式的主合取范式，所以成假賦值為100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：（1）解：原式 ，

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

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

5、是謀殺嫌犯，s：看門人看見過A。則前提：， 結(jié)論：證明： 前提引入 前提引入 拒取式 前提引入 合取引入 前提引入 假言推理習(xí)題四及答案：（P65-67）5、在一階邏輯中將下列命題符號(hào)化：（2）有的火車比有的汽車快。解：設(shè)F(x)：x是火車，G(y)：y是汽車，H(x,y)：x比y快；則命題符號(hào)化的結(jié)果是：（3）不存在比所有火車都快得汽車。解：設(shè)F(x)：x是汽車，G(y)：y是火車，H(x,y)：x比y快；則命題符號(hào)化的結(jié)果是：或9、給定解釋I如下：(a) 個(gè)體域?yàn)閷?shí)數(shù)集合R。(b) 特定元素。(c) 函數(shù)。(d) 謂詞。給出以下公式在I下的解釋，并指出它們的真值：（2）解：解釋是：，含義是

6、：對(duì)于任意的實(shí)數(shù)x，y，若x-y=0則x<y。該公式在I解釋下的真值為假。14、證明下面公式既不是永真式也不是矛盾式：（1）解：取解釋如下：個(gè)體域?yàn)槿倐€(gè)體域，：x是兔子，：y是烏龜，：x比y跑得快，則該公式在解釋I下真值是1；取解釋如下：x比y跑得慢，其它同上，則該公式在解釋下真值是0；故公式（1）既不是永真式也不是矛盾式。此題答案不唯一，只要證明公式既不是永真式也不是矛盾式的每個(gè)解釋合理即可。習(xí)題五及答案：（P80-81）15、在自然推理系統(tǒng)中，構(gòu)造下面推理的證明：（3）前提：， 結(jié)論：證明： 前提引入 置換 UI規(guī)則 前提引入 UI規(guī)則 析取三段論 EG規(guī)則22、在自然推理系統(tǒng)中，

7、構(gòu)造下面推理的證明：（2）凡大學(xué)生都是勤奮的。王曉山不勤奮。所以王曉山不是大學(xué)生。解：設(shè)F(x)：x為大學(xué)生，G(x)：x是勤奮的，c：王曉山則前提：， 結(jié)論：證明： 前提引入 UI規(guī)則 前提引入 拒取式25、在自然推理系統(tǒng)中，構(gòu)造下面推理的證明：每個(gè)科學(xué)工作者都是刻苦鉆研的，每個(gè)刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。王大海是科學(xué)工作者，并且是聰明的。所以，王大海在他的事業(yè)中將獲得成功。（個(gè)體域?yàn)槿祟惣希┙猓涸O(shè)F(x)：x是科學(xué)工作者，G(x)：x是刻苦鉆研的，H(x)：x是聰明的，I(x)：x在他的事業(yè)中獲得成功，c：王大海則前提：， 結(jié)論：證明： 前提引入 化簡 化簡 前提引入

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

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

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