國防科技大學2003年離散數學考研試題
來源：
時間：2007-06-06 14:41:48
國防科技大學2003年離散數學考研試題
考生注意：答案必須寫在統一配發的答題紙上！
一、（每小題10分，共20分）
設 A = {a, b, c, d}，A 上的二元關系 R1和 R2定義如下：
R1 = {<a, b>, <b, c>, <c, d>, <d, a>}
R2= IA∪{<a, b>,<b, a>,<c, d>,<d, c>}
i) 試分別指出R1和R2所具有的性質（即 是否具有自反性，反自反性，對稱性，反對稱性和傳遞性這五種性質）。
ii) 試求出R12，R22，R1•R2， R1 和 R2 。
二、（15分）
設函數ƒ : X→Y 且 g : X→Y ，若令
A = {a∈X | g (ƒ(a))=a} 且 B = {b∈Y |ƒ(g (b))=b}
則 ƒ[A]= B。
三、（20分）
設 A 為有限集且ƒ:A→A , 證明：
a) 若有自然數 n≥1 使 ƒ n =IA ，則ƒ為雙射；
b) 若ƒ為雙射，則有自然數 n≥1 使 ƒ n =IA 。
四、（15分）
求合式公式（P∨Q）∧（P→R）∧（Q→R）<==>R 的主合取范式和主析取范式。
五、（15分）
試判斷下列合式公式是否為永真式，并證明你的結論：
(Ax)(P(x)∨Q(x))→(Ax)P(x)∨(Ey)Q(y)，其中P和Q均為一元謂詞。
六、（每小題10分，共30分）
用自然推理系統證明：
i) ﹁A∧﹁B ┣ ﹁(﹁A→B )
ii) ﹁(﹁A→B ) ┣ ﹁A∧﹁B
iii) (Ex)(﹁A(x)) ┣ ﹁(Ax)A(x)
七、（15分）
試求葉的權分別為 2，3，3，4，5，6，8 的最優葉加權二叉樹及其葉加權路徑長度。
八、（20分）
設n階簡單無向圖G的邊數 m >(1/2) (n-1)(n-2)，則G為連通的。
結束
特別聲明：①凡本網注明稿件來源為"原創"的，轉載必須注明"稿件來源：育路網"，違者將依法追究責任；
②部分稿件來源于網絡，如有侵權，請聯系我們溝通解決。
閱讀全文
招生服務平臺始創于1999年
打開微信掃一掃，關注育路教育官方微信
