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