離散數學習題答案解析

..離散數學習題答案習題一及答案：〔P14-1514、將下列命題符號化：〔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解：列出公式的真值表,如下所示：001111011010100101110001由真值表可以看出公式有3個成真賦值,故公式是非重言式的可滿足式。20、求下列公式的成真賦值：〔4解：因為該公式是一個蘊含式,所以首先分析它的成假賦值,成假賦值的條件是：所以公式的成真賦值有：01,10,11。習題二及答案：〔P385、求下列公式的主析取范式,并求成真賦值：〔2解：原式,此即公式的主析取范式,所以成真賦值為011,111。*6、求下列公式的主合取范式,并求成假賦值：〔2解：原式,此即公式的主合取范式,所以成假賦值為100。7、求下列公式的主析取范式,再用主析取范式求主合取范式：〔1解：原式,此即主析取范式。主析取范式中沒出現的極小項為,,,所以主合取范式中含有三個極大項,,,故原式的主合取范式。9、用真值表法求下面公式的主析取范式：〔1解：公式的真值表如下：00010000011011010110101111111000101101010111001011110101由真值表可以看出成真賦值的情況有7種,此7種成真賦值所對應的極小項的析取即為主析取范式,故主析取范式習題三及答案：〔P52-5411、填充下面推理證明中沒有寫出的推理規(guī)則。前提：結論：s證明：①p前提引入②前提引入③q①②析取三段論④前提引入⑤r③④析取三段論⑥前提引入⑦s⑤⑥假言推理15、在自然推理系統P中用附加前提法證明下面推理：〔2前提：結論：證明：用附加前提證明法。①p附加前提引入②①附加③前提引入④②③假言推理⑤s④化簡⑥⑤附加⑦前提引入⑧u⑥⑦假言推理故推理正確。16、在自然推理系統P中用歸謬法證明下面推理：〔1前提：,,結論：證明：用歸謬法①p結論的否定引入②前提引入③①②假言推理④前提引入⑤③④析取三段論⑥前提引入⑦r⑥化簡⑧⑤⑦合取由于,所以推理正確。17、在自然推理系統P中構造下面推理的證明：只要A曾到過受害者房間并且11點以前沒離開,A就是謀殺嫌犯。A曾到過受害者房間。如果A在11點以前離開,看門人會看見他?？撮T人沒有看見他。所以,A是謀殺嫌犯。解：設p：A到過受害者房間,q：A在11點以前離開,r：A是謀殺嫌犯,s：看門人看見過A。則前提：,,,結論：證明：①前提引入②前提引入③①②拒取式④前提引入⑤③④合取引入⑥前提引入⑦⑤⑥假言推理習題四及答案：〔P65-675、在一階邏輯中將下列命題符號化：〔2有的火車比有的汽車快。解：設F<x>：x是火車,G<y>：y是汽車,H<x,y>：x比y快；則命題符號化的結果是：〔3不存在比所有火車都快的汽車。解：方法一：設F<x>：x是汽車,G<y>：y是火車,H<x,y>：x比y快；則命題符號化的結果是：或方法二：設F<x>：x是火車,G<y>：y是汽車,H<x,y>：x比y快；則命題符號化的結果是：或9、給定解釋I如下：<a>個體域為實數集合R。<b>特定元素。<c>函數。<d>謂詞。給出以下公式在I下的解釋,并指出它們的真值：〔2解：解釋是：,含義是：對于任意的實數x,y,若x-y=0則x<y。該公式在I解釋下的真值為假。14、證明下面公式既不是永真式也不是矛盾式：〔1解：取解釋如下：個體域為全總個體域,：x是兔子,：y是烏龜,：x比y跑得快,則該公式在解釋I下真值是1；取解釋如下：：x比y跑得慢,其它同上,則該公式在解釋下真值是0；故公式〔1既不是永真式也不是矛盾式。此題答案不唯一,只要證明公式既不是永真式也不是矛盾式的每個解釋合理即可。習題五及答案：〔P79-815、給定解釋I如下：<a>個體域D={3,4}<b><c>試求下列公式在I下的真值：<1>解：方法一：先消去存在量詞15、在自然推理系統中,構造下面推理的證明：〔3前提：,結論：證明：①前提引入②①置換③②UI規(guī)則④前提引入⑤④UI規(guī)則⑥③⑤析取三段論⑦⑥EG規(guī)則*22、在自然推理系統中,構造下面推理的證明：〔2凡大學生都是勤奮的。王曉山不勤奮。所以王曉山不是大學生。解：設F<x>：x為大學生,G<x>：x是勤奮的,c：王曉山則前提：,結論：證明：①前提引入②①UI規(guī)則③前提引入④②③拒取式25、在自然推理系統中,構造下面推理的證明：每個科學工作者都是刻苦鉆研的,每個刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。王大海是科學工作者,并且是聰明的。所以,王大海在他的事業(yè)中將獲得成功。〔個體域為人類集合解：設F<x>：x是科學工作者,G<x>：x是刻苦鉆研的,H<x>：x是聰明的,I<x>：x在他的事業(yè)中獲得成功,c：王大海則前提：,,結論：證明：①前提引入②①化簡③①化簡④前提引入⑤④UI規(guī)則⑥②⑤假言推理⑦③⑥合取引入⑧前提引入⑨⑧UI規(guī)則⑩⑦⑨假言推理習題六及答案〔P99-10028、化簡下述集合公式：〔3解：30、設A,B,C代表任意集合,試判斷下面命題的真假。如果為真,給出證明；如果為假,給出反例?！?解：該命題為假,,如果,則,否則,故為假。舉反例如下：則。〔8解：該命題為假,舉反例如下：如果B,C都是A的子集,則一定成立,但不一定成立,例如：,,,則,但。33、證明集合恒等式：〔1證明：習題七及答案：〔P132-13526設,R為A上的關系,R的關系圖如圖7.13所示：〔1求的集合表達式；〔2求r<R>,s<R>,t<R>的集合表達式。解：〔1由R的關系圖可得所以,,可得；〔2,41、設A={1,2,3,4},R為上的二元關系,,〔1證明R為等價關系；〔2求R導出的劃分。〔1只需證明R具有自反性、對稱性和傳遞性即可,證明過程如下：〔a任取,有,,所以R具有自反性；〔b任取,若,則有,,,所以R具有對稱性；〔c任取,若且,則有且,,,所以R具有傳遞性,綜合〔a〔b〔c可知：R為集合上的等價關系；〔2先求出集合的結果：再分別求集合各元素的等價類,結果如下：。等價關系R導出的劃分就是集合A關于R的商集,而集合A關于R的商集是由R的所有等價類作為元素構成的集合,所以等價關系R導出的劃分是：46、分別畫出下列各偏序集的哈斯圖,并找出A的極大元、極小元、最大元和最小元?！?解：哈斯圖如下：eeabcdfA的極大元為e、f,極小元為a、f；A的最大元和最小元都不存在。*22、給定,A上的關系,試〔1畫出R的關系圖；〔2說明R的性質。2解：1〔121●●●●3434〔2R的關系圖中每個頂點都沒有自環(huán),所以R是反自反的,不是自反的；R的關系圖中任意兩個頂點如果有邊的都是單向邊,故R是反對稱的,不是對稱的；R的關系圖中沒有發(fā)生頂點x到頂點y有邊、頂點y到頂點z有邊,但頂點x到頂點z沒有邊的情況,故R是傳遞的。*48、設為偏序集,在集合上定義關系T如下：證明T為上的偏序關系。證明：〔1自反性：〔2反對稱性：〔3傳遞性：綜合〔1〔2〔3知T具有自反性、反對稱性和傳遞性,故T為上的偏序關系。習題九及答案：〔P179-1808、〔1〔2。解：〔1〔211、〔3；解：〔3由*運算的定義可知：,16、習題十一及答案：〔P218-2191、圖11.11給出了6個偏序集的哈斯圖。判斷其中哪些是格。如果不是格,說明理由解：〔a、〔c、〔f是格；因為任意兩個元素構成的集合都有最小上界和最大下界；〔b不是格,因為{d,e}的最大下界不存在；〔d不是格,因為{b,c}的最小上界不存在；〔e不是格,因為{a,b}的最大下界不存在。2、下列各集合低于整除關系都構成偏序集,判斷哪些偏序集是格?！?L={1,2,3,4,5}；〔2L={1,2,3,6,12}；解：畫出哈斯圖即可判斷出：〔1不是格,〔2是格。4、設L是格,求以下公式的對偶式：〔2解：對偶式為：,參見P208頁定義11.2。6、設L為格,,且,證明。證明：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