1、注：考試期間試卷不允許拆開考試期間試卷不允許拆開本試卷共６頁第0頁第1學期學期《離散數(shù)學離散數(shù)學》試卷試卷A（試卷共（試卷共6頁，答題時間頁，答題時間120120分鐘）分鐘）題號一二三四總分統(tǒng)分人復核人得分一、選擇題（每小題一、選擇題（每小題2分，共分，共2020分。請將答案分。請將答案填在下面的表格內）填在下面的表格內）1、從集合分類的角度看命題公式可分為()A.永真式、矛盾式B.永真式、可滿足式、矛盾式C.可滿足式、矛盾式D.永真式

2、、可滿足式2、設B不含有x，等值于()))((BxAx??A.B.C.D.BxxA??)())((BxAx??BxxA??)())((BxAx??3、設STM是集合，下列結論正確的是（）A如果S∪T=S∪M，則T=MB如果ST=Φ，則S=TCDSSS??)(~TSTS???4、設R是集合A上的偏序關系，則R不一定是()A.自反的B.對稱的C.反對稱的D.傳遞的5設R為實數(shù)集，定義R上4個二元運算，不滿足結合律的是（）。A.f1(xy)=

3、xyB.f2(xy)=xyC.f3(xy)=xyD.f4(xy)=maxxy得分閱卷人題號12345678910答案注：考試期間試卷不允許拆開考試期間試卷不允許拆開本試卷共6頁第2頁4、已知n階無向簡單圖G有m條邊，則G的補圖有條邊。5、一個有向圖是強連通強連通的充分必要條件是。7、已知n階無向圖G中有m條邊，各頂點的度數(shù)均為3。又已知2n3=m，則m=.8、在下圖中從A點開始，用普里姆算法構造最小生成樹，加入生成樹的第三條邊是（）。A

4、BCDE12345678三、計算題（每題三、計算題（每題9分，共分，共3636分）分）1、已知命題公式，)()(pqqp?????(1)構造真值表。(2)求主析取范式(要求通過等值演算推出)。2、R1=R2=求：(1)（２）(３)求21RR?11?R12RR?３、設為一個偏序集，其中，A=1，2，3，4，6，9，12，24R是A上的整除關系。（1）畫R出的哈斯圖；（2）求A的極大元和極小元；（3）求B=46的上確界和下確界。４、畫一棵帶