離散數學考試說明

2022-05-14 05:30:34 字數 4125 閱讀 8369

內容指要

一、 集合論

空集的性質,集合之間的並、交、差、補和對稱差運算

二、 數理邏輯

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得