離散數(shù)學(xué)綜合練習(xí)及答案

1、北京科技大學(xué)遠(yuǎn)程教育學(xué)院離散數(shù)學(xué)綜合練習(xí)(一)參考答案數(shù)理邏輯一、判斷下列句子是否是命題，若是命題判斷真值，并將其符號(hào)化。 1、今天天氣真好！ 解：不是命題。 2、王華和張民是同學(xué)。 解：是命題。真值視實(shí)際情況而定。p：王華和張民是同學(xué)。 3、我一邊吃飯，一邊看電視。 解：是命題。真值視實(shí)際情況而定。p：我吃飯。q：我看電視。pÙq 4、沒有不呼吸的人。 解：是命題。真值為1。M(x)：x是人。F(x)：x呼吸。"x(M(x)®F(x)二、求命題公式的真值表和成真賦值、成假賦值。 解： Ù0 0 001110 0 101110 1 001110 1 10

2、1111 0 001001 0 101111 1 010001 1 10111成真賦值：000，001，010，011，101，111；成假賦值100，110三、用真值表、等值演算兩種方法判別公式類型。 1、解： ®0 0 01010 0 11010 1 01100 1 11111 0 00011 0 10011 1 01101 1 1111可滿足式 2、解： A0 010110 110111 000111 11101永真式四、求命題公式的主析取范式和成真賦值、成假賦值。 解： 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 111111101 成真賦值

3、：000，001，010，011，100，101，111；成假賦值110五、解釋I如下：D是實(shí)數(shù)集，特定元素a=0；特定函數(shù)f(x，y)=x-y；特定謂詞F(x，y)：x<y。在解釋I下判別公式真、假。 1、解：真值為假 2、解：真值為真六、 1、求前束范式解： 2、證明：證明：七、寫出下面推理的證明，要求寫出前提、結(jié)論，并注明 推理規(guī)則。 （1）如果乙不參加籃球賽，那么甲就不參加籃球賽。若乙參加籃球賽，那么甲和丙就參加籃球賽。因此，如果甲參加籃球賽，則丙就參加籃球賽。解：p：甲參加籃球賽。q：乙參加籃球賽。r：丙參加籃球賽。前提： Øq® Øp ，q &#

4、174; (pÙr) ，結(jié)論：p ® r證明： Øq® Øp 前提引入 p®q 置換 q ® (pÙr) 前提引入 Øq Ú (pÙr) 置換 (Øq Ú p ) Ù(Øq Ú r) 置換 Øq Ú r 化簡(jiǎn) q ® r 置換 p ® r 假言三段論推理正確 （2）學(xué)會(huì)的成員都是專家。有些成員是青年人。所以，有些成員是青年專家。(個(gè)體域是人的集合)F(x)：x 是學(xué)會(huì)成員。G(x)：x 是專家。H

5、(x)：x 是青年人。前提："x( F(x)® G(x)，$x( F(x)Ù H(x)結(jié)論：$x( F(x)Ù H(x)Ù G(x)證明： $x( F(x)Ù H(x) 前提引入 F(c)Ù H(c) EI "x( F(x)® G(x) 前提引入 F(c)® G(c) UI F(c) 化簡(jiǎn) G(c) 假言推理 F(c)Ù H(c)Ù G(c) 合取 $x( F(x)Ù H(x)Ù G(x) EG推理正確離散數(shù)學(xué)綜合練習(xí)(二)參考答案集合、關(guān)系、函數(shù)一、判斷

6、題 1、對(duì)任意集合A，都有AÎA和AÍ A，不能同時(shí)成立。 （ F ） 2、R1、R2是A上的具有自反性的二元關(guān)系，R1R2也具有自反性。 （ F ） 3、A上恒等關(guān)系IA具有自反性、對(duì)稱性、反對(duì)稱性、傳遞性。 （ T ） 4、f：A®B，g：B®C，若fog是A®C的滿射，則f、g都是滿射。 （ F ） 5、A =1，2，3，4，f是從A到A的滿射，則也是從A到A的單射。 （ T ）二、填空題 1、(AB)AB = A 。 2、A有2個(gè)元素，B有3個(gè)元素，從A到B的二元關(guān)系有 26 個(gè)。 3、R是A上的二元關(guān)系，RoR1一定具有的性質(zhì)是 對(duì)稱

7、性 。 4、f(x)= lnx 是從 R+ 到 R 的函數(shù)。 5、f、g都是從A到A的雙射，(fog)1 = g1of1 。三、集合 1、A=a，b，c，c，a，b、B=a，b，c，b 求AB、AB、AB、AÅB解： 2、A=a，b，c，Ø 求A的冪集。解：P(A)=Ø，Ø，a，b，c，a，b，c，a，b，Ø，c，Ø，A 3、證明：A(BC) = (AB)(AC)解：四、二元關(guān)系（共30分） 1、Aa，b，c，b，R<a，b>，<b，a>，<b，c>，<c，d> 用關(guān)系矩陣求R4，寫出R

8、4的集合表示。 2、指出二元關(guān)系滿足哪種性質(zhì)，不滿足哪種性質(zhì)，說明理由。解：滿足反對(duì)稱性；不滿足自反性，反自反性，對(duì)稱性，傳遞性 3、A =1，2，3，4，5，6，S =1，2，3，4，5，6 畫出由S產(chǎn)生的等價(jià)關(guān)系的關(guān)系圖。解： 4、畫出偏序集的哈斯圖，并指出最大元、最小元、極大元、極小元。1，2，3，12整除關(guān)系解：最大元：無；最小元、極小元：1；極大元：7，8，9，10，11，12五、函數(shù) 1、確定以下各題中f是否是從A®B的函數(shù)，若是指出是否是單射、滿射、雙射， 如果不是說明理由。（1）A=1，2，3，4，5、B=5，6，7，8，9 f=<1，8>，<3，9

9、>，<4，10>，<2，6>，<5，9>解：f 是函數(shù)，由<3，9>，<5，9> f 不是單射，也不是滿射。（2）A=1，2，3，4，5、B=5，6，7，8，9 f=<1，7>，<2，6>，<4，8>，<1，9>，<5，10>解：由<1，7>，<1，9>，f 不是函數(shù)。（3）A、B都是實(shí)數(shù)集，f(x) = x3。解：f 是函數(shù)， f 是單射，也是滿射，f 是雙射。（4）A、B都是正整數(shù)集，解：f 是函數(shù)， f 是單射，不是滿射。2、，、都是的函數(shù)

10、。 ：， ：， 、中哪個(gè)有反函數(shù)？若有則求出反函數(shù)。求出復(fù)合函數(shù)、。解： 是雙射，有反函數(shù)，就是 自己。：，：，：，3、A、B都是有n個(gè)元素的集合，f：A®B的函數(shù)。 證明：f是單射 Û f是滿射。證明：Þ設(shè)f是單射，由于，所以 有n 個(gè)元素，又 ，而 也只有 n 個(gè)元素，所以 Ü 設(shè)f是滿射，若 f 不是單射，則 ，由于 中只有 n 個(gè)元素，所以 ，與 矛盾。離散數(shù)學(xué)綜合練習(xí)(三)參考答案代數(shù)系統(tǒng)一、判斷題1、0，±1，±2，±n對(duì)普通加法封閉。 （F）2、在非負(fù)整數(shù)集Z+上定義運(yùn)算·，x·y = mi

11、nx，y，1是運(yùn)算的幺元。（T）3、實(shí)數(shù)集與普通乘法構(gòu)成的代數(shù)系統(tǒng)中每個(gè)元素都有逆元素。 （F）4、在代數(shù)系統(tǒng)<Z，+，0>中，0是零元。 （F）5、非負(fù)整數(shù)集Z+與普通加法構(gòu)成的代數(shù)系統(tǒng)是群。 （F）6、M是n階可逆矩陣的集合，×是矩陣乘法，<M，×>是群。 （T）7、循環(huán)群的子群是循環(huán)群。 （T）8、代數(shù)系統(tǒng)<Z，+>是代數(shù)系統(tǒng)<R*，+>的子代數(shù)。 （F）二、填空題1、A =x | x = 3n ，nÎN，對(duì) 乘法 運(yùn)算封閉。2、<R*，+>構(gòu)成的代數(shù)系統(tǒng)是 半群 。3、在代數(shù)系統(tǒng)<Z，+，0

12、>中，0是 單位 元。4、F =f | f：A®A，o為函數(shù)的復(fù)合運(yùn)算，<F，o>的單位元是 恒等函數(shù) 。5、f、g都是從A到A的雙射，(fog)1 = g1of1 。6、在代數(shù)系統(tǒng)<S，*>中，元素a、b都有逆元，則(a1)1= a ，(a*b)1=b1*a1 。7、循環(huán)群有 生成 元，使循環(huán)群中元素都是該元素的方冪。8、V1=<S1，o>，V2=<S2，*>都有幺元，j是V1到V2的同態(tài)，則j把V1中的單 位元映射到 V2中的單位元 。三、解答題 1、Q是正有理數(shù)集，×是普通乘法，<Q+，×>是

13、否是半群、獨(dú)異點(diǎn)、群？解：普通乘法有結(jié)合律，單位元是 1 ，但 0 沒有逆元，<Q+，×>是獨(dú)異點(diǎn)。 2、實(shí)數(shù)集R上的運(yùn)算 * ，a*b=aba×b，是普通加法，×是普通乘法。 驗(yàn)證：<R，*>只能是獨(dú)異點(diǎn)。解： "a，b，cÎ R (a*b)*c = (aba×b) * c = (aba×b)c(aba×b)×c= abca×ba×cb×ca×b×ca*(b*c) = a* (bcb×c) = a+(bcb×c

14、)+a×(bcb×c)= abca×ba×cb×ca×b×c運(yùn)算 * 有結(jié)合律 由于運(yùn)算 * 有交換律，設(shè) e 是單位元。"a Î Ra*e = aea×e = a，(1+ a )×e = 0 ，e = 0設(shè) a1 是 * a 的逆元，a1 * a = a1 + a + a1 × a = 0(1+ a )a1 =a ，當(dāng) a ¹ 1時(shí)，a 有逆元。a = 1 無逆元，所以 <Q+，×>是獨(dú)異點(diǎn)。 3、實(shí)數(shù)集R上的運(yùn)算 * ，a*b=ab 2，是

15、普通加法，-是普通減法。 <R，*>是否是群？解： "a，b，c Î R，(a*b)*c = (ab2) * c = (ab2)c2 = abc4a*(b*c) = a * (cb2) = a(bc2)2 = abc4運(yùn)算 * 有結(jié)合律由于運(yùn)算 * 有交換律，設(shè) e 是單位元。"a Î Ra*e = ae2 = a，e2 = 0 ，e = 2設(shè) a1 是 * a 的逆元，a1 * a = a1 + a 2 = 2a1 = 4a 所以 <R，*> 是群。四、求8階循環(huán)群e，a，a2，a7的各階子群。解：一階子群e 二階子群e，a4

16、四階子群e，a2，a4，a6 八階子群e，a，a2，a7五、設(shè)代數(shù)系統(tǒng)A ，*有單位元，代數(shù)系統(tǒng)B ，無單位元。 證明：這兩個(gè)代數(shù)系統(tǒng)不同構(gòu)。證明：若A ，*，B ，同構(gòu)，則存在同構(gòu)映射j，又設(shè) e 是A ，*的單位元，則 j( e ) 是B ，中的單位元，與B ，無單位元矛盾。離散數(shù)學(xué)綜合練習(xí)(四)參考答案圖論一、判斷題 1、(2，2，5，2，1，3)可以構(gòu)成圖的度數(shù)序列。 （ F ） 2、n階無向完全圖的邊數(shù)為n(n1)。 （ F ） 3、生成子圖與母圖有相同的邊集。 （ F ） 4、最小生成樹是不唯一的。 （ T ） 5、有向完全圖是強(qiáng)連通圖。 （ T ）二、填空題 1、頂點(diǎn)和邊都不相同

17、的通路，稱為 初級(jí)通路 。 2、無向樹有m個(gè)樹枝，則頂點(diǎn)數(shù)為 m +1 。 3、無向圖頂點(diǎn)之間的連通關(guān)系具有自反性、 對(duì)稱 性、 傳遞 性， 是 等價(jià) 關(guān)系。 4、A是有向圖D的鄰接矩陣，若A3中的元素，則 頂點(diǎn)vi到vj 長(zhǎng)度為 3 的通路有 2 條 。 5、A是有向圖D的鄰接矩陣，Bk=A+A2+Ak中元素bij¹0，則頂點(diǎn)vi到 vj 可達(dá) 。三、解答題 1、在圖1中（1）求鄰接矩陣A；（2）計(jì)算A2、A3、A4；（3）求B4=A+A2+A3+A4；（4）v1到v2長(zhǎng)度為2、3的通路各有多少條？（5）v1到v2長(zhǎng)度小于等于4的通路有多少條？解：（1）（2），（3）B4=A+A2

18、+A3+A4（4）v1到v2長(zhǎng)度為2、3的通路分別有1、2條（5）v1到v2長(zhǎng)度小于等于4的通路有7條 2、有向圖的鄰接矩陣（1）畫出這個(gè)有向圖；（2）求；（3）中長(zhǎng)度為2的回路有多少條？（4）中到長(zhǎng)度小于等于2的通路有多少條？（5）中的元素說明什么？解：（1）畫出這個(gè)有向圖；（2）（3）中長(zhǎng)度為2的回路有2條（4）中到長(zhǎng)度小于等于2的通路有2條（5）中的元素說明到長(zhǎng)度等于2的通路有1條四、特殊圖 判別下列各圖是否是歐拉圖和哈密爾頓圖，說明理由。（3）（1）（2）解：(1) 只是哈密爾頓圖，aefbcghda 是哈密爾頓回路(2)(3)是歐拉圖，頂點(diǎn)度數(shù)都是偶數(shù)(2)(3)也是哈密爾頓圖 abcgdfea、abcdefghija 分別是哈密爾頓回路五、樹 1、求下列各