一、 判斷下列命題對錯（每小題前標記√或×）（總20分）
（√）1.集合的交運算關於對稱差運算滿足分配律。
（×）2.對於集合a，aa=a。
（×）3.集合的差運算滿足結合律。
（×）4.集合a上的關係都是自反的。
（√）5.若r,s都是a上的自反關係，則復合關係rs也是自反關係。
（×）6.若, 都是a上的等價關係，則復合關係也是等價關係。
（×）7.合取正規化都不是析取正規化。
（×）8.命題的主析取正規化不是唯一的。
（√）9.無向圖的總度數是偶數。
（√）10.無迴路的無向連通圖稱為樹。
二、 填空題題目（每空3分，總30分）
1. 設集合a的階數|a|=3，則冪集|p(a)|=___8___。
2. 設a是全集e的子集，則ae=__a-e__。
3. 若集合a=，r是a上模為3的同餘關係，則等價類=___，商集a/r=__，，}__。
4. 偏序關係是指滿足自反、反對稱、傳遞的二元關係。
5. 命題pq的主合取正規化是。
6. 有向連通圖是尤拉圖的充分必要條件是圖中每個頂點的入度和出度相等。
7. 設賦權圖的頂點集是v=，令t=，已知指標dt(b)=6，dt(c)=8，dt(d)=8，dt(e)=7，dt(z)= ，則a到b的最短路長是__6___。
8. 命題邏輯中，吸收律是指如下兩個等價式：_ p (pq) p__和_p (pq) p__。
三、（10分）設集合a=，r是a上的整除關係，證明r是a上的偏序關係並畫出r的哈斯圖。
證明：r是a上的整除關係，即當a,ba，a能整除b時，(a,b) r。
易知a能整除a，得(a,a) r，即r是自反的二元關係；
易知(b,a) r，即r是反對稱的二元關係；
當ca，c能整除a時，c也能整除b，即若(c,a) r，(a,b) r時，有(c,b) r，即r是傳遞的二元關係。
故r是a上的偏序關係。
四、（10分）證明下列推理：
pr,pq,qs, spr
解：1 qs p
2 sp
3 qt①②
4 q p
5 p t④
6 pt③⑤
7 prp
8 rt⑥⑦
9 pr t⑥⑧
五、（10分）求(pq) r的主析取正規化和主合取正規化。
解：先列出(pq) r的真值表：
由表可知，(pq) r
(pq) r
所以(pq) r的主析取正規化為：
(qr) ( qr) ( qr) ( qr) ( qr) ( qr)
(pq) r的主合取正規化為：
(qr) ( qr)
六、（10分）某單位有五個不同職位：b1,b2,b3,b4,b5，有四個申請者：a1,a2,a3,a4，他們想申請的職位分別是：
a1(b2,b5)，a2(b1,b3)，a3(b1,b4)，a4(b3,b4)，如何安排他們的申請，才能使無職位的人最少？（要求利用匈牙利演算法計算，初始對集取為m=）
解：(b3)(b4)( )
(a2a4) (a4)
(1)由於a4是唯一的不是m中的端點，把a4標記為()。
(2)將a4的鄰接點b3和b4標記(a4)。
(3)從b3出發，把a2標記(b3)，從b4出發，把a3標記(b4)。
(4)從a2出發，把b1標記為(a2)，因為b1已不是m中邊的端點，說明已找到一條長通路a4b3a2b1。再用增長通路中不屬於m的邊代替屬於m的邊，於是可得匹配m』=如下圖，由於中僅有4個頂點，所以m』是最大匹配。
七、（10分）證明下列永真蘊含式：
pq證明：
(p) (p)
1由此可見(p) 是永真式，即pq。證畢。
離散數學試卷
全國2004年7月高等教育自學考試 課程 02324 一 單項選擇題 在每小題的四個備選答案中，選出乙個正確答案，並將正確答案的序號填在題幹的括號內。每小題1分，共14分 1.下列語句不是命題的是 a.是非金屬。b.要是他不上場，我們就不會輸。c.他跑100公尺只用了10秒鐘，你說他是不是運動健將呢...
《離散數學》試卷 AB 知識點
湖南人文科技學院2014 2015學年第1學期信工系 計科 網工 軟工專業2013級離散數學課程期末考試試卷 ab 知識點第一章 1.命題的判斷 p1例1.1 p28例1.28 2.命題符號化 p35習題5 3.復合命題的真值 p6例1.9 p35習題6 p242題一 1 4.用等值演演算法或真值表...
20062019學年第二學期離散數學試卷B標準答案
浙江工商大學2006 2007學年第二學期 離散數學 考試b卷標準答案 一 單項選擇題 2 10 20分 1 d 2 c 3 c 4 c 5 c 6 a 7 a 8 b 9 b 10 b 二 填空題 2 5 10分 1 24 2 3 0 4 5 14三 簡答題 每小題5分,共20分 1 解3 所以是...