離散數(shù)學(xué)樣卷參考答案

1、一、單項(xiàng)選擇題 ( 每題2分, )1. 公式的所有成真賦值為_(kāi)D_.A. 00, 10, 11 B. 10, 11, 01 C. 00, 01, 11 D. 00, 01, 102. 設(shè)，則集合A上有_A_個(gè)不同的二元關(guān)系.A. B. C. D. 3. 設(shè)A1,2,3，是A上的關(guān)系, 則R滿足的性質(zhì)是_B_.A. 反自反性 B. 對(duì)稱性 C. 反對(duì)稱性 D. 傳遞性4. 下列集合中對(duì)所給二元運(yùn)算封閉的是 D .A. 1,-1關(guān)于普通的加法運(yùn)算 B. 1,-1關(guān)于普通的減法運(yùn)算C. 1,0關(guān)于普通的加法運(yùn)算 D. 1,0關(guān)于普通的乘法運(yùn)算5. 階無(wú)向樹(shù)是 C .A. 哈密頓圖 B. 歐拉圖 C.

2、 二部圖 D. 不連通圖二、判斷題（每小題 2 分，共10分）1. 設(shè)A, B都是含命題變項(xiàng),的公式, 若是矛盾式, 則A一定是矛盾式. （ ）2. 是聯(lián)結(jié)詞完備集. （ ）3. 設(shè)R是非空集合A上的關(guān)系，則R的對(duì)稱閉包. （ × ）4. 任何無(wú)向圖中, 奇度點(diǎn)的個(gè)數(shù)一定是偶數(shù). （ ）5. 簡(jiǎn)單通路必是初級(jí)通路. （ × ） 得 分評(píng)卷人三、填空題（每空 2 分，共20 分）1. 公式的類型是 永真式 .2. 的前束范式為 .3. 計(jì)算的冪集 .4. 已知, 求x和y. 5 設(shè)A = 1, 2, 3， 則A上的小于等于關(guān)系 6. 設(shè)A = a, b, c, d，則的關(guān)系矩

3、陣 . 7. 設(shè)A = 1, 2, 3， 給出A的一個(gè)劃分 1, 2, 3等 .8. 設(shè)A = a, b, c, d, e， A上的偏序關(guān)系, 則A的極大元是 a, b, d, e .9. 對(duì)于普通數(shù)的加法運(yùn)算, 加法運(yùn)算的冪等元是 0 .10. 設(shè)圖G是階-正則圖, 則G的邊數(shù) .四、計(jì)算證明題（每小題 10 分，共 60 分）1. 求的主析取范式和主合取范式. 解: 2. 在自然推理系統(tǒng)中構(gòu)造下面推理的證明:每個(gè)喜歡步行的人都不喜歡騎自行車(chē). 每個(gè)人或者喜歡騎自行車(chē)或者喜歡乘汽車(chē).有的人不喜歡乘汽車(chē). 所以, 有的人不喜歡步行. (個(gè)體域?yàn)槿祟惣?設(shè)F(x): x喜歡步行，G(x): x

4、喜歡騎自行車(chē)，H(x): x喜歡乘汽車(chē).解：前提: , , 結(jié)論: 證: 前提引入 EI 前提引入 UI 析取三段論 前提引入 UI 拒取 EG3. 設(shè)F, G是任意的關(guān)系, 證明: 證: 任取, 4. 證明: 大于等于關(guān)系是整數(shù)集合Z上的偏序關(guān)系. 證: 自反. 對(duì)Z, 反對(duì)稱. 對(duì)Z, 傳遞. 對(duì)Z, 5. 設(shè)G = a+bia, bZ, i為虛數(shù)單位. 證明: G關(guān)于復(fù)數(shù)加法構(gòu)成群. 證: (1) 復(fù)數(shù)加法可結(jié)合. i, i, iG,iii= iii=i(2) 單位元0. (3) 對(duì)iG，(i )= i.6. 有向圖的鄰接矩陣為, 求：(1) 中從到的長(zhǎng)度為1,2,3,4的通路數(shù). (2) 中從到的長(zhǎng)度為1,2,3,4的回路數(shù).(3) 中長(zhǎng)度為2的回路數(shù).(4) 中長(zhǎng)度為4的通路數(shù). 解: , (1) 中從到的長(zhǎng)度為1,2,3,4的通路分別有0,0,0,0條. (2) 中從到的長(zhǎng)度為1,2,3