一．填空R-1
1 R是集合X上的關(guān)系,若 ,則稱R是X上的等價關(guān)系.
2 R是集合X上的二元關(guān)系,則關(guān)系1/R={ | }.
3 T是一連通圖,若T滿足 ,則T構(gòu)成樹.
4 G是一個圖,若G可以 ,則稱G為二部圖.
5 已知謂詞公式 x F(x,y)yH(x,y),則 是自由變元.
6 已知謂詞公式 xF(x,y)yG(x,y,z),則 是約束變元.
7 圖G存在懸掛頂點,則至少刪去 條邊,圖變成兩個連通分支.
8 T是一棵樹,則T的樹葉最少有 片.
9 G是一個連通圖,若G有一個 ,則G為歐拉圖.
10 圖G存在懸掛頂點,則圖G的邊連通度λ（G）為 ( .
11．設(shè)p:小王走路,q:小王聽音樂,在命題邏輯中,命題“小王邊走路邊聽音樂”的符號化形式為___________________.
12.設(shè)F(x)：x是人,H(x,y)：x與y一樣高,在一階邏輯中,命題“人都不一樣高”的符號化形式為_________________.
13.命題公式r （ pq）的成真賦值為 _________________,對應(yīng)的極小項為 ,成假賦值為 對應(yīng)的極大項為 ,.
14．T是一棵具有n個頂點m條邊的樹,則n與m的關(guān)系是 .
15．G是一個圖,若G含有與 的子圖,則G一定是非平面圖.
二．用一階邏輯公式表示下列命題
1 集合A屬于集合B,
2 集合A等于集合B
3 集合X=空集
4．集合A上的二元關(guān)系R是自反的
5．集合A上的二元關(guān)系R是反自反的
6．集合A上的二元關(guān)系R是對稱的
7．集合A上的二元關(guān)系R是反對稱的
8．集合A上的二元關(guān)系R是傳遞的
三．按要求完成下列各題
1 A={x,y,z},R={,,,},S={,,,},求R◦S、S◦R及S的傳遞閉包t（R）.
2 已知集合E={1,2,{1,2}},S={1,{2}},求ES,ES,(E－S)(S－E) .求命題公式（pqr）的主析取范式和主合取范式.
3 A={1,2,{2}},求A×A,P（A）.
4 畫一棵帶權(quán)為2,2,3,3,4,5,8的最優(yōu)二元樹T,并計算它的權(quán)W（T）.
5 （1）在一棵有2個2度頂點,4個3度頂點,其余頂點都是樹葉的無向樹中,應(yīng)該有幾片樹葉?（2）畫出兩棵非同構(gòu)的滿足（1）中頂點度數(shù)的無向樹T1和T2.
6 一棵樹有5片樹葉,3個2度頂點,其余的頂點均為3度頂點,問T有幾個頂點?
7 A={1,2,3,5,7,14,15,35},R是A上的整除關(guān)系:Rx|y(x整除y),畫出R的哈斯圖,設(shè) B={2,5,7,14,35},求B關(guān)于R的極大元、極小元和最大元、最小元.
9 求出下列圖的所有點割集和邊割集.
10．已知一個有向圖G=,其中
V={v1,v2,v3 },
E={,,,,},
求D的鄰接矩陣A；（2）求頂點v1的入度、出度及次數(shù)（3）將G看成無向圖,寫出關(guān)聯(lián)矩陣.
11．用二元樹表示下面的表達(dá)式
((x－2y)*3z－7x)÷(4z-2y)2
12．求下列圖的最小生成樹
四．證明下列命題 (14分)
1 A,B,C是任意集合,證明(A-B)-C=(A-C)-(B-C)
2 A,B,C是任意集合,證明若A⊕B= A⊕C,則B=C
3 A,B是集合,若P(A)∩P(B)=P(A∩B),其中P(A)表示集合A的冪集.
4 p,q,r是任意命題,證明p→(q∨r) (p∧┑q) →r
5 p,q,r是任意命題,證明(p→q) ∧ (q→r) p→r
6 前提：(p∧q) → r ,┐r ∨s,┐s,p,
結(jié)論：┐q
7 設(shè)A={1,2,3,4},在A×A上定義二元關(guān)系R：,A×A,Rx+y=u+v,證明R為A×A上的等價關(guān)系.