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

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

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

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

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

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