育路教育網(wǎng)，權(quán)威招生服務(wù)平臺(tái)

國防科技大學(xué)2003年離散數(shù)學(xué)考研試題

來源：時(shí)間：2007-06-06 14:41:48

國防科技大學(xué)2003年離散數(shù)學(xué)考研試題

考生注意：答案必須寫在統(tǒng)一配發(fā)的答題紙上！

一、（每小題10分，共20分）
設(shè) A = {a, b, c, d}，A 上的二元關(guān)系 R1和 R2定義如下：
R1 = {<a, b>, <b, c>, <c, d>, <d, a>}
R2= IA∪{<a, b>,<b, a>,<c, d>,<d, c>}
i) 試分別指出R1和R2所具有的性質(zhì)（即是否具有自反性，反自反性，對稱性，反對稱性和傳遞性這五種性質(zhì)）。
ii) 試求出R12，R22，R1•R2， R1 和 R2 。

二、（15分）
設(shè)函數(shù)ƒ : X→Y 且 g : X→Y ，若令
A = {a∈X | g (ƒ(a))=a} 且 B = {b∈Y |ƒ(g (b))=b}
則 ƒ[A]= B。

三、（20分）
設(shè) A 為有限集且ƒ:A→A , 證明：
a) 若有自然數(shù) n≥1 使 ƒ n =IA ，則ƒ為雙射；
b) 若ƒ為雙射，則有自然數(shù) n≥1 使 ƒ n =IA 。

四、（15分）
求合式公式（P∨Q）∧（P→R）∧（Q→R）<==>R 的主合取范式和主析取范式。

五、（15分）
試判斷下列合式公式是否為永真式，并證明你的結(jié)論：
(Ax)(P(x)∨Q(x))→(Ax)P(x)∨(Ey)Q(y)，其中P和Q均為一元謂詞。

六、（每小題10分，共30分）
用自然推理系統(tǒng)證明：
i) ﹁A∧﹁B ┣ ﹁(﹁A→B )
ii) ﹁(﹁A→B ) ┣ ﹁A∧﹁B
iii) (Ex)(﹁A(x)) ┣ ﹁(Ax)A(x)

七、（15分）
試求葉的權(quán)分別為 2，3，3，4，5，6，8 的最優(yōu)葉加權(quán)二叉樹及其葉加權(quán)路徑長度。

八、（20分）
設(shè)n階簡單無向圖G的邊數(shù) m >(1/2) (n-1)(n-2)，則G為連通的。

結(jié)束

特別聲明：①凡本網(wǎng)注明稿件來源為"原創(chuàng)"的，轉(zhuǎn)載必須注明"稿件來源：育路網(wǎng)"，違者將依法追究責(zé)任；

②部分稿件來源于網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系我們溝通解決。