離散數(shù)學(xué)習(xí)題答案(同名3671)

離散數(shù)學(xué)習(xí)題答案習(xí)題一及答案：（P14-15）14、將下列命題符號化：（5）李辛與李末是兄弟解：設(shè)p：李辛與李末是兄弟，則命題符號化的結(jié)果是p（6）王強(qiáng)與劉威都學(xué)過法語解：設(shè)p：王強(qiáng)學(xué)過法語；q：劉威學(xué)過法語；則命題符號化的結(jié)果是（9）只有天下大雨，他才乘班車上班解：設(shè)p：天下大雨；q：他乘班車上班；則命題符號化的結(jié)果是（11）下雪路滑，他遲到了解：設(shè)p：下雪；q：路滑；r：他遲到了；則命題符號化的結(jié)果是15、設(shè)p：2+3=5.q：大熊貓產(chǎn)在中國.r：太陽從西方升起.求下列復(fù)合命題的真值：（4）解：p=1，q=1，r=0，，19、用真值表判斷下列公式的類型：（2）解：列出公式的真值表，如下所示：001111011010100101110001由真值表可以看出公式有3個成真賦值，故公式是非重言式的可滿足式。20、求下列公式的成真賦值：（4）解：因?yàn)樵摴绞且粋€蘊(yùn)含式，所以首先分析它的成假賦值，成假賦值的條件是：所以公式的成真賦值有：01，10，11。習(xí)題二及答案：（P38）5、求下列公式的主析取范式，并求成真賦值：（2）解：原式，此即公式的主析取范式，所以成真賦值為011，111。6、求下列公式的主合取范式，并求成假賦值：（2）解：原式，此即公式的主合取范式，所以成假賦值為100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：（1）解：原式，此即主析取范式。主析取范式中沒出現(xiàn)的極小項(xiàng)為，，，所以主合取范式中含有三個極大項(xiàng)，，，故原式的主合取范式。9、用真值表法求下面公式的主析取范式：⑤③④合取引入⑥前提引入⑦⑤⑥假言推理習(xí)題四及答案：（P65-67）5、在一階邏輯中將下列命題符號化：（2）有的火車比有的汽車快。解：設(shè)F(x)：x是火車，G(y)：y是汽車，H(x,y)：x比y快；則命題符號化的結(jié)果是：（3）不存在比所有火車都快得汽車。解：設(shè)F(x)：x是汽車，G(y)：y是火車，H(x,y)：x比y快；則命題符號化的結(jié)果是：或9、給定解釋I如下：(a)個體域?yàn)閷?shí)數(shù)集合R。(b)特定元素。(c)函數(shù)。(d)謂詞。給出以下公式在I下的解釋，并指出它們的真值：（2）解：解釋是：，含義是：對于任意的實(shí)數(shù)x，y，若x-y=0則x<y。該公式在I解釋下的真值為假。14、證明下面公式既不是永真式也不是矛盾式：（1）解：取解釋如下：個體域?yàn)槿倐€體域，：x是兔子，：y是烏龜，：x比y跑得快，則該公式在解釋I下真值是1；取解釋如下：：x比y跑得慢，其它同上，則該公式在解釋下真值是0；故公式（1）既不是永真式也不是矛盾式。此題答案不唯一，只要證明公式既不是永真式也不是矛盾式的每個解釋合理即可。習(xí)題五及答案：（P80-81）15、在自然推理系統(tǒng)中，構(gòu)造下面推理的證明：（3）前提：，結(jié)論：證明：①前提引入②①置換③②UI規(guī)則④前提引入⑤④UI規(guī)則⑥③⑤析取三段論⑦⑥EG規(guī)則22、在自然推理系統(tǒng)中，構(gòu)造下面推理的證明：（2）凡大學(xué)生都是勤奮的。王曉山不勤奮。所以王曉山不是大學(xué)生。解：設(shè)F(x)：x為大學(xué)生，G(x)：x是勤奮的，c：王曉山則前提：，結(jié)論：證明：①前提引入②①UI規(guī)則③前提引入④②③拒取式25、在自然推理系統(tǒng)中，構(gòu)造下面推理的證明：每個科學(xué)工作者都是刻苦鉆研的，每個刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。王大海是科學(xué)工作者，并且是聰明的。所以，王大海在他的事業(yè)中將獲得成功。（個體域?yàn)槿祟惣希┙猓涸O(shè)F(x)：x是科學(xué)工作者，G(x)：x是刻苦鉆研的，H(x)：x是聰明的，I(x)：x在他的事業(yè)中獲得成功，c：王大海則前提：，，結(jié)論：證明：①前提引入②①化簡③①化簡④前提引入⑤④UI規(guī)則⑥②⑤假言推理⑦③⑥合取引入⑧前提引入⑨⑧UI規(guī)則⑩⑦⑨假言推理習(xí)題六及答案習(xí)題七及答案：（P132-135）*22、給定，A上的關(guān)系，試（1）畫出R的關(guān)系圖；（2）說明R的性質(zhì)。2解：1（1）21●●●●3434（2）R的關(guān)系圖中每個頂點(diǎn)都沒有自環(huán)，所以R是反自反的，不是自反的；R的關(guān)系圖中任意兩個頂點(diǎn)如果有邊的都是單向邊，故R是反對稱的，不是對稱的；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)系圖可得所以，，可得；（2），46、分別畫出下列各偏序集的哈斯圖，并找出A的極大元、極小元、最大元和最小元。（1）解：哈斯圖如下：eeabcdfA的極大元為e、f，極小元為a、f；A的最大元和最小元都不存在。48、設(shè)為偏序集，在集合上定義關(guān)系T如下：證明T為上的偏序關(guān)系。證明：（1）自反性：（2）反對稱性：（3）傳遞性：綜合（1）（2）（3）知T具有自反性、反對稱性和傳遞性，故T為上的偏序關(guān)系。習(xí)題九及答案：（P179-180）8、（1）（2）。解：（1）（2）11、（3）；解：（3）由*運(yùn)算的定義可知：，16、習(xí)題十一及答案：（P218-219）1、圖11.11給出了6個偏序集的哈斯圖。判斷其中哪些是格。如果不是格，說明理由解：（a）、（c）、（f）是格；因?yàn)槿我鈨蓚€元素構(gòu)成的集合都有最小上界和最大下界；（b）不是格，因?yàn)閧d,e}的最大下界不存在；（d）不是格，因?yàn)閧b,c}的最小上界不存在；（e）不是格，因?yàn)閧a,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是格，求以下公式的對偶式：（2）解：對偶式為：，參見P208頁定義11.2。9、針對圖11.11中的每個格，如果格中的元素存在補(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中每個格是否為分配格、有補(bǔ)格和布爾格，并說明理由。解：（a）圖：是一條鏈，所以是分配格，b和c都沒有補(bǔ)元，所以不是有補(bǔ)格，所以不是布爾格；（c）圖：a,f互為補(bǔ)元，c和d的補(bǔ)元都是b和e，b和e的補(bǔ)元都是c和d，所以任何元素皆有補(bǔ)元，是有補(bǔ)格；，所以對運(yùn)算不滿足分配律，所以不是分配格，