離散數(shù)學習題答案(同名3671)

離散數(shù)學習題答案習題一及答案：（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）解：列出公式的真值表，如下所示：001111011010100101110001由真值表可以看出公式有3個成真賦值，故公式是非重言式的可滿足式。20、求下列公式的成真賦值：（4）解：因為該公式是一個蘊含式，所以首先分析它的成假賦值，成假賦值的條件是：所以公式的成真賦值有：01，10，11。習題二及答案：（P38）5、求下列公式的主析取范式，并求成真賦值：（2）解：原式，此即公式的主析取范式，所以成真賦值為011，111。6、求下列公式的主合取范式，并求成假賦值：（2）解：原式，此即公式的主合取范式，所以成假賦值為100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：（1）解：原式，此即主析取范式。主析取范式中沒出現(xiàn)的極小項為，，，所以主合取范式中含有三個極大項，，，故原式的主合取范式。9、用真值表法求下面公式的主析取范式：⑤③④合取引入⑥前提引入⑦⑤⑥假言推理習題四及答案：（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)個體域為實數(shù)集合R。(b)特定元素。(c)函數(shù)。(d)謂詞。給出以下公式在I下的解釋，并指出它們的真值：（2）解：解釋是：，含義是：對于任意的實數(shù)x，y，若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）凡大學生都是勤奮的。王曉山不勤奮。所以王曉山不是大學生。解：設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ī)則⑥②⑤假言推理⑦③⑥合取引入⑧前提引入⑨⑧UI規(guī)則⑩⑦⑨假言推理習題六及答案習題七及答案：（P132-135）*22、給定，A上的關系，試（1）畫出R的關系圖；（2）說明R的性質。2解：1（1）21●●●●3434（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、分別畫出下列各偏序集的哈斯圖，并找出A的極大元、極小元、最大元和最小元。（1）解：哈斯圖如下：eeabcdfA的極大元為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個偏序集的哈斯圖。判斷其中哪些是格。如果不是格，說明理由解：（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，所以任何元素皆有補元，是有補格；，所以對運算不滿足分配律，所以不是分配格，