重大2015年離散數(shù)學(xué) ( 第3次作業(yè) )

1、第3次作業(yè)次作業(yè)一、判斷題（本大題共一、判斷題（本大題共2020分，共分，共1010小題，每小題小題，每小題2分）分）1.一個(gè)關(guān)系可以：既滿足對稱性，同時(shí)也滿足反對稱性（）2.連通圖的最小生成樹不一定是唯一的。（）3.bcaaaacabb是前綴碼。（）4.歐拉定理的具體內(nèi)容是：若一個(gè)連通圖存在0個(gè)或2個(gè)奇數(shù)度結(jié)點(diǎn)，則該圖中存在歐拉路。（）5.任何合式公式的主析取范式都是唯一的（如果存在的話）（）。6.設(shè)集合A=abc，A上的二元關(guān)系R=

2、，則R是等價(jià)關(guān)系。（）7.一個(gè)群可以有多個(gè)等冪元。（）8.不存在既有歐拉回路又有漢密爾頓回路的圖。（）9.為重言式。（）10.設(shè)是一個(gè)代數(shù)系統(tǒng)，且集合A中元素的個(gè)數(shù)大于1。如果該代數(shù)系統(tǒng)中存在幺元e和零元，則e。（）二、單項(xiàng)選擇題（本大題共二、單項(xiàng)選擇題（本大題共3030分，共分，共1010小題，每小題小題，每小題3分）分）1.以下關(guān)系中是等價(jià)關(guān)系的是（）A.房間之間的相鄰關(guān)系B.三角形的相似關(guān)系C.朋友關(guān)系D.函數(shù)之間的合成關(guān)系2.設(shè)

3、G是連通平面圖，G中有6個(gè)頂點(diǎn)8條邊，則G的面的數(shù)目是（）A.2個(gè)面B.3個(gè)面C.4個(gè)面D.5個(gè)面3.設(shè)無向圖G的邊數(shù)為m，結(jié)點(diǎn)數(shù)為n，則G是樹等價(jià)于（）A.G連通且m=n1B.G連通且n=m1C.G連通且m=2nD.每對結(jié)點(diǎn)之間至少有一條通路4.以下復(fù)合命題可以使用合取符號聯(lián)結(jié)的是（）A.我一邊散步一邊打電話。B.我打開門，走了進(jìn)來。C.我和小劉是同事。D.如果11=2，當(dāng)且僅當(dāng)桌子有4條腿。5.下面哪一個(gè)圖是樹（）？A.C.D.10

4、.設(shè)PQR是命題公式，則()。?A.PB.QC.RD.三、分析題（本大題共三、分析題（本大題共8分，共分，共1小題，每小題小題，每小題8分）分）等值演算法求公式（p→q）→（p→q）的主合取范式四、計(jì)算題（本大題共四、計(jì)算題（本大題共8分，共分，共1小題，每小題小題，每小題8分）分）設(shè)S=1234612，D為S上的整除關(guān)系，（1）試寫出該關(guān)系并畫出哈斯圖；（2）設(shè)子集B=236，試求B的最大元、最小元、極大元和極小元；（3）試求B的上界

5、、上確界、下界和下確界。五、作圖題（本大題共五、作圖題（本大題共6分，共分，共1小題，每小題小題，每小題6分）分）試畫出結(jié)點(diǎn)數(shù)為3的（1）強(qiáng)連通圖（2）單向連通圖（3）弱連通圖（4）非連通圖六、證明題（本大題共六、證明題（本大題共8分，共分，共1小題，每小題小題，每小題8分）分）構(gòu)造下面推理的證明。只要A曾到過受害者房間并且11點(diǎn)以前沒離開，A就犯了謀殺罪。A曾到過受害者房間。如果在11點(diǎn)以前離開，看門人會看見他。看門人沒有看見他。所以