離散數(shù)學試題及解答

離散數(shù)學2m*n一、選擇題（ 2*10）1令 P：今天下雨了， Q：我沒帶傘，則命題“雖然今天下雨了，但是我沒帶傘”可符號化為（）。（A）PQ（B）PQ（C）PQ（D）PQ2下列命題公式為永真蘊含式的是（）。（A）Q（ PQ）（ B） P（ PQ）（C）（PQ） P（ D）（PQ） Q3、命題“存在一些人是大學生”的否定是(A) ，而命題“所有的人都是要死的”的否定是（）。（A）所有人都不是大學生，有些人不會死（B）所有人不都是大學生，所有人都不會死（C）存在一些人不是大學生，有些人不會死（D）所有人都不是大學生，所有人都不會死4、永真式的否定是（）。（A）永真式（ B）永假式（ C）可滿足式（ D）以上均有可能5、以下選項中正確的是（）。（A）0= ?（B）0?（C）0?（D）0?6、以下哪個不是集合A 上的等價關(guān)系的性質(zhì)？（）（A）自反性（B）有限性（ C）對稱性（ D）傳遞性7、集合 A=1,2,10 上的關(guān)系 R=<x,y>|x+y=10,x,yA ，則 R 的性質(zhì)為（）。（A）自反的（B）對稱的（C）傳遞的，對稱的（D）傳遞的8設(shè) D=<V, E>為有向圖， V=a, b, c, d, e, f, E=<a, b>, <b, c>, <a,d>, <d, e>, <f, e>是（）。（A）強連通圖（B）單向連通圖（C）弱連通圖（D）不連通圖9、具有 6 個頂點， 12 條邊的連通簡單平面圖中，每個面都是由（）條邊圍成？（A）2（B）4（C）3（D）510連通圖 G是一棵樹，當且僅當G中（）。（A）有些邊不是割邊（B）每條邊都是割邊（C）無割邊集（D）每條邊都不是割邊二、填空題（ 2*10）1、命題“ 2 是偶數(shù)或 -3 是負數(shù)”的否定是 _。2、設(shè)全體域 D 是正整數(shù)集合，則命題xy(xy=y) 的真值是 _。3、令 R(x):x是實數(shù)， Q(x):x是有理數(shù)。則命題“并非每個實數(shù)都是有理數(shù)”的符號化表示為 _。4、公式 (PQ)(PQ)化簡為 _。5、設(shè)A B=A C， A B=A C，則 B_C。6、設(shè) A=2,4,6 ，A 上的二元運算 * 定義為： a*b=maxa,b ，則在獨異點 <A,*> 中，單位元是 _，零元是 _。7、任一有向圖中，度數(shù)為奇數(shù)的結(jié)點有_(奇數(shù) / 偶數(shù) ) 個。8如下無向圖割點是 _，割邊是 _。三、（10分）設(shè) A、B 和 C是三個集合，則 A B(BA。)。四、（15 分）某項工作需要派A、 B、 C和 D 4 個人中的 2 個人去完成，按下面3 個條件，有幾種派法？如何派？(1) 若 A 去，則 C和 D中要去 1 個人；(2)B 和 C不能都去；(3) 若 C去，則 D留下五、（ 15 分）設(shè) A=1,2,3,寫出下列圖示關(guān)系的關(guān)系矩陣，并討論它們的性質(zhì)：AAABCBCBC六、（ 20 分）畫一個圖使它分別滿足：（ 1）有歐拉回路和哈密爾頓回路；（ 2）有歐拉回路，但無條哈密爾頓回路；（ 3）無歐拉回路，但有哈密爾頓回路；（ 4）既無歐拉回路，又無哈密爾頓回路。答案：一、選擇題：1、D2、C3、A4、B5、D6、B7、B8、C9、C10、B二、填空：1、 2 不是偶數(shù)且 -3 不是負數(shù)2、 F3、x(R(x)Q(x)4、P5、等于6、2，67、偶數(shù)8、 d， e5三、證明：ABx( x A x B) x( x B xA)x( xA x B) x( x BxA)x( x A xB) x( xBx A)x( x AxB) x( x A x B)(xx A x Bxx A x B(xx A x Bxx B()()()( x A)(BA)。四、解設(shè) A：A 去工作； B： B 去工作； C： C 去工作； D：D 去工作。則根據(jù)題意應(yīng)有：ACD，(BC， CD必須同時成立。因此)(AC D(B CCD)()(ACD(CD(BC(CD()(ACD(CD(BC(BDC(C()D)(ABC) (ABD) (AC) (ACD)( CDBC) ( CDBD) ( CDC) ( CDCD)(CDBC) (CDBD) (CDC) (CD C D)FF(AC) FF( CDB) FF(CDB) F(CD) F(AC(BCD(CDB(CD)(A C) (BC D) (CD)T故有三種派法： B D， A C， A D。五、000（ 1）R=<2,1>,<3,1>,<2,3>MR=101 ; 它是反自反的、 反對稱的、傳遞的；100011（ 2） R=<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>MR=101; 它是反自反110的、對稱的；011（ 3）R=<1,2>,<2,1>,<1,3>,<3,3>M =1 0 0; 它既不是自反的、反自反的、R001也不是對稱的、反對稱的、傳遞的。六、