內容指要
一、 集合論
空集的性質，集合之間的並、交、差、補和對稱差運算
二、 數理邏輯
1、 命題的概念；
2、 5種基本的聯結詞（乛，∧，∨，→，）的含義；
3、 全稱量詞(x)，存在量詞(x)的含義；
4、 如何求給定命題公式的主析取、主合取正規化及其成真的賦值；
5、 如何使用p規則，t規則，cp規則對命題邏輯推理的證明；
三、 關係
1、 關係的概念；
2、 關係的三種表示方法：集合，矩陣，關係圖；
3、 關係的五種性質：
1） r是a上自反的(x)(x∈a→∈r)
2） r是a上反自反的(x)(x∈a→r)
3） r是a上對稱的(x)(y)(((x∈a)∧(y∈a)∧(∈r))→(∈r))
4） r是a上反對稱的(x)(y)(((x∈a)∧(y∈a)∧(∈r)∧(∈r))→(x=y))
5） r是a上傳遞的(x)(y)(z)(((x∈a)∧(y∈a)∧(z∈a)∧(∈r)∧(∈r))→(∈r))
4、 等價關係的概念；偏序關係的概念，如何畫哈斯圖，如何確定最小元、最大元、極大元和極小元
5、 如何求自反閉包，對稱閉包；
6、 能通過集合，矩陣，關係圖來判斷關係具有的性質；
7、 掌握關係性質的證明
8、 函式的概念，函式的分類（單射、雙射、滿射），如何判斷是那一類函式；
四、 圖論
1、 完全圖的概念；
2、 簡單通路，基本通路，簡單迴路，基本回路的概念；
3、 尤拉圖的概念及判斷方法；
4、 平面圖的概念，如何計算面的次數；
5、 樹的概念與性質；如何求帶權圖的最小生成樹；
五、 代數系統
1、 代數系統的概念；如何判定是否為一個代數系統；
2、 二元基本運算律與特異元素的定義，如何判斷代數系統中運算滿足什麼運算律，如何找一個代數系統中的零元、么元；
3、 半群、群、子群、迴圈群、元素週期的概念；如何判斷一個代數系統的型別，如何判斷是否為子群。
4、 格的概念，如何判定一個代數系統是否為格；
5、 布林代數的概念；
各部分佔分比率
試卷結構
《離散數學》期末考試樣卷
一、 選擇題（共20分，每題2分）
1．設a，b為任意集合，下面命題中不恆為真的是( )
a．∈}
c．a－{}＝ad．a－b＝ba＝b＝
2．下列語句中為命題的是（ ）
a．這朵花是誰的？ b．這朵花真美麗啊！
c．這朵花是你的嗎？ d．這朵花是他的。
3．設論域d=，與公式等價的命題公式是（ ）
a．a（a）∧a（b） b．a（a）→a（b）
c．a（a）∨a（b） d．a（b）→a（a）
4．設集合s＝，則s上不同的二元關係有( )
a．8個 b．16個 c．256個 d．512個
5．設r為實數集，函式f：r→r，f(x)=2x，則f是（ ）
a．滿射函式b．單射函式
c．雙射函式d．非單射非滿射
6．下列各圖是無向完全圖的是（ ）
7．結點數為奇數且所有結點的度數也為奇數的連通圖必定是（ ）
a．尤拉圖 b．哈密爾頓圖
c．非平面圖 d．不存在的
8．平面圖(如下)的三個面的次數分別是（ ）
a．11，3，4 b．11，3，5
c．12，3，6 d．10，4，3
9．設r為實數集，對於任意a，b∈r，a*b＝a＋b＋ab，則下述結論中正確的是( )
a．不構成代數系統
b．構成半群，但不構成含么半群
c．構成含么半群，但不構成群
d．構成群
10．下列整數集對於整除關係都構成偏序集，而能構成格的是（ ）
a． b．
c． d．
二、 填空題（共20分，每題2分）
1．公式┐pq的成真賦值有個．
2．設個體域為d=,f(x):x3,g(x):x>5.則在此解釋下公式(x)(f(x)∧g(x))的真值為______.
3．設a＝，b＝，則a∩b
4．設a＝ 1，2，3，4 ，則劃分b＝，}對應的a上的等價關係r
5．設r為a上的關係，則r的自反閉包r(r)= ，對稱閉包s(r)= 。
6．若一條路中，所有邊均不相同，則此路稱作若一條路中所有的結點均不相同，則稱此路為
7．一個且的無向圖稱為樹。
8．代數系統，其中a為命題公式集合，。為析取運算，則中零元素是____，么元是____。
9．設a,bg，則（a-1）-1ab）-1
10．一個格稱為布林代數，如果它是______格和______格.
三、應用題（共30分，每題10分）
1．求命題公式(pq)(q∨p)的主析取正規化，並求成真賦值。
2．設a=，r是a冪集上的包含關係。
（1） 畫出偏序集的哈斯圖；
（2） 設b=,,}，求b極大元、極小元、最大元、最小元。
3．用克魯斯克爾演算法求以下賦權圖的最小生成樹（畫出其生成過程）。
四、證明題（共30分，每題10分）
1．構造下列推理的證明。
前提： (a∨b)(p∨q)，p，(ba)∨p a
結論：a
2．已知r和s是非空集合a上的等價關係，試證：
（1） r∩s是a上的等價關係；
（2） 對。
3．設是一個群.c=,證明是的一個子群.
《離散數學》期末考試樣卷
試題答案及評分參考
一、選擇題（共30分，每題2分）
二、填空題（共20分，每題2分）
1．22．假（0，f）
3．4．
5．,6．簡單通路，基本通路
7．連通，不含迴路
8．1，0
9．a, b-1*a-1
10．有補，分配
三、應用題（共30分，每題10分）
1．解：(pq)(q∨p)(p∨q)(q∨p)(p∨q)∨(q∨p)
(p∧q)∨q∨pq∨p((p∨p)∧q)∨(p∧q)∨(p∧q)
(p∧q)∨(p∧q)∨(p∧q)∨(p∧q) m0∨m2∨m37分
成真賦值為：00、10、113分
2．解： （1）
6分（2）
最大元：無；
最小元：無；
級大元：,
級小元：,{c4分
3．解： 每步驟2分
四、證明題（共20分，每題10分）
1．證明：
(1)(a∨b)(p∨qp
(2)(p∨q)(a∨bt(1)，e
(3)pp
(4)a∨bt(2)(3)，i
(5)(ba)∨pp
(6)bat(3)(5)，i
(7)a∨bt(6)，e
(8)(a∨b)∧(a∨bt(4)(7)，i
(9)a∧(b∨bt(8)，e
(10)at(9)，e
2．證明：
（1）1）自反性：x∈a，因為r和s是自反關係，所以∈r、∈s，因而∈r∩s，故r∩s是自反的2分
2）對稱性：x、y∈a，若∈r∩s，則∈r、∈s，因為r和s是對稱關係，所以因∈r、∈s，因而∈r∩s，故r∩s是對稱的。 2分
3）傳遞性：x、y、z∈a，若∈r∩s且∈r∩s，則∈r、∈s且∈r、∈s，因為r和s是傳遞的，所以因∈r、∈s，因而∈r∩s，故r∩s是傳遞的。
即r∩s是等價關係2分
（2）因為x∈[a]r∩s∈r∩s∈r∧∈s x∈[a]r∧x∈[a]s x∈[a]r∩[a]s
所以[a]r∩s=[a]r∩[a]s4分
3證明：
1）非空性
因為群中單位元素e滿足e*x=x*e=x所以e∈c,c非空. 3分
2）封閉性
設a∈c, b∈c,則對任意 x∈g有a*x=x*a,b*x=x*b.於是,根據乘法結合律
(a*b)*x=a*(b*x)=a*(x*b)=(a*x)*b=(x*a)*b=x*(a*b)
所以a*b∈c3分
3）可逆性
設a∈c,則對任意x∈g,有
a*x=x*a
在上式兩端左乘a-1,右乘a-1得