上海應用技術學院2008—2009學年第一學期
《 離散數學 》期末試卷（a）
課程**: b204216學分: 4 考試時間: 100 分鐘
課程序號: 3404
班級學號姓名
我已閱讀了有關的考試規定和紀律要求，願意在考試中遵守《考場規則》，如有違反將願接受相應的處理。
試卷共 6 頁，請先檢視試卷有無缺頁，然後答題。
一．選擇題(10 x 2 =20)
1. 下列命題中命題（ ）為假。
a. 「如果2是偶數，則乙個公式的主析取正規化唯一。」
b. 「如果2是偶數，則乙個公式的析取正規化唯一。」
c. 「如果2是奇數，則乙個公式的析取正規化唯一
d. 「如果2是奇數，則乙個公式的主析取正規化唯一。」
2. 命題公式的成真賦值為（ ）。
a. 001b. 110
c. 100d. 010
3. 集合a=，b=,則|a∩b|=（ ）。
a. 7 b. 8 c. 4d. 3
4. .若個體域為，下列公式中值為真的是（ ）。
a. xy(x+y=
c. xy(x+y=0) d. xy(x+y=0)
5. 設集合 s=,,},集合( )是s中所有元素的交集。
a.cd.
6. 若ab且bc則
a. a∩c =b b. a∪b= a
c. a∩c =a d. a∪c =b
7. 在自然數集合n上，下列運算中（ ）滿足結合律。
a. a * b = | a-bb. a * b = a+2b
c. a * b = max( a,b ) d. a * b = a b
8. 以下關係中（ ）不具有傳遞性。
b. s=
c. s=
d. s=
9. 以下命題中（ ）是假命題。
a.「群滿足結合律」
b.「群中只有乙個么元」
c.「群中無零元」
d.「群滿**換律」
10設無向圖中有6條邊，有乙個3度頂點和乙個5度頂點，其餘頂點度為2，則該圖的頂點數是（ ）。
a．3 b．4
c．5 d．6
二．填空題(2 x 10 = 20)
1. 設a=，ra×a，r=，則r的自反閉包r(r對稱閉包t(r
2. a=，則獨異點，它的么元為 ，-1的逆元為 。
3. 設f(x)表示「x是奇數」，h(x)表示「x是偶數」，g(x) 表示「x是整數」，用謂詞公式表示命題「所有整數要麼是奇數要麼是偶數
4. 有向圖中任意兩點間均相互可達 ，此圖為連通圖。若任二頂點間至少從乙個頂點到另乙個頂點是可達的，則稱此圖為連通圖
5．設a=,b=,則a與b的笛卡爾積a╳b
6．設命題p：天下雨，q：我進城，r：我有空。用自然語言寫出下列命題。
（┐p→q）∧（r→q
7．具有n個元素的集合a的子集個數是
三．設a=，它的乙個劃分π=，，}。 （10）
1．寫出對應的等價關係r；（3）
2．畫出r的關係圖；（3）
3．寫出a中元素關於r的等價類。（4）
四．寫出命題公式( p →( p ∧ q )) ∨ r的真值表，並按真值表寫出主析取正規化和主合取正規化。（10）
五．有帶權圖g如下(12)
1．寫出圖g的鄰接矩陣（3）
2．求最小生成樹和樹權t（w）。（寫出每一步生成過程）（7）
3．找出圖中的「割點」（2）
六．給定權 1，4， 6 ， 7， 8，11，22，36，構造一棵最優二元樹，並計算該二元樹的權（寫出構造的過程）。（10）
七．設有集合z4 =，+4 為定義在z4 上的模4加法（兩數相加後除以4的餘數）（10）
1．構造< z4 ，+4 >的運算表；（4）
2．證明< z4 ，+4 >是乙個群；（6）
八．構造推理證明(8)
前提：p∨q , p→﹁r , s→t , ﹁s→r,﹁t
結論：q
上海應用技術學院2008—2009學年第一學期
《離散數學 》期末考試（a）試卷標準答案
一． 選擇題（20）
baddc ccadb
二． 填空題（20）
1. 2. 1，-1
3. 4. 強， 單向
5. 6. 若天不下雨並且我有空，那麼我進城。
7. 2n
三． （10分）
(1)r=
(2)圖略
(3)[1]=[3]= , [2]=, [4]=
四 （10分）
主析取正規化 m0 ∨m1 ∨m2∨m3 ∨m5∨m6 ∨m7
主合取正規化 m0
五． 有帶權圖g如下(12分) 最小生成樹如下：
w(t)=11+15+16+18+21=81
a(g)=
六． 給定權 1，4， 6 ， 7， 8，11，22，36，構造一棵最優二元樹，並計算二叉樹的權（寫出構造的過程）。（10分）
權=(1+4)*5+6*4+(7+8+11)*3+(36+22)*2 = 243
七．設有集合z4 =，+4 為定義在z4 上的模4加法（兩數相加後除4的餘數）（10分） 證明略
八、（8分）證明略
離散期末總結
數理邏輯部分以判定推理為主 包括對給定合式公式屬性的判定及熟練使用 條規則進行有效推理。這一部分佔20分。代數系統部分 掌握代數系統的基本概念，包括子代數，代數系統的同態 同構，積代數和商代數的求法等，特殊代數系統掌握群相關的內容，如何求子群等。這部分佔20分。圖論部分掌握圖的基本概念，圖的矩陣表示...
離散數學試卷
全國2004年7月高等教育自學考試 課程 02324 一 單項選擇題 在每小題的四個備選答案中，選出乙個正確答案，並將正確答案的序號填在題幹的括號內。每小題1分，共14分 1.下列語句不是命題的是 a.是非金屬。b.要是他不上場，我們就不會輸。c.他跑100公尺只用了10秒鐘，你說他是不是運動健將呢...
離散數學試卷 答案
一 判斷下列命題對錯 每小題前標記 或 總20分 1.集合的交運算關於對稱差運算滿足分配律。2.對於集合a，aa a。3.集合的差運算滿足結合律。4.集合a上的關係都是自反的。5.若r,s都是a上的自反關係，則復合關係rs也是自反關係。6.若,都是a上的等價關係，則復合關係也是等價關係。7.合取正規...