離散數(shù)學(xué)期末考試題(和含解析1)

一.填空2．A,B,C示意三個齊集,文圖中陰影部分的齊集表達式為(B⊕C)-AAC4．公式的主合取范式為.5．若說明I的論域D僅包括一個元素,則在I下真值為1.6．設(shè)A={1,2,3,4},A上關(guān)系圖以下,則R^2={(1,1),(1,3),(2,2),(2,4)}.備注：7．設(shè)A={a,b,c,d},其上偏序關(guān)系R的哈斯圖以下,則R={(a,b),(a,c),(a,d),(b,d),(c,d)}U{(a,a),(b,b)(c,c)(d,d)}.備注：偏序滿足自反性,反對稱性,傳達性8．圖的補圖為.補圖:給定一個圖G,又G中全部結(jié)點和全部能使G成為完好圖的增添邊組成的圖,成為補圖.自補圖:一個圖假好像構(gòu)于它的補圖,則是自補圖9．設(shè)A={a,b,c,d},A上二元運算以下：*abcdaabcdbbcdaccdabddabc那么代數(shù)系統(tǒng)<A,*>的幺元是a,有逆元的元素為a,b,c,d,它們的逆元分別為a,b,c,d.//備注：二元運算為x*y=max{x,y},x,yA.10．以下圖所示的偏序分別,是格的為c.（注：什么是格？即任意任性兩個元素有最小上界和最大下界的偏序）二.選擇題1.以下是真命題的有（

C.D

）A．

;

B．

;C．

;

D

．

.以下聚分別相等的有（B.C）A．{4,3}

;B．{

,3,4};C

．{4,

,3,3};D

．

{3,4}.3.設(shè)

A={1,2,3},

則A上的二元關(guān)系有（

C）個.A．

23;

B

．32;

C

．

;D

．

.//備注：A的二元關(guān)系個數(shù)為：個.設(shè)R,S是齊集A上的關(guān)系,則以下說法正確的是（A）A．若

R,S

是自反的

,則

是自反的

;B．若

R,S

是反自反的

,則

是反自反的

;XC．若

R,S

是對稱的

,則

是對稱的

;XD．若

R,S

是傳達的

,則

是傳達的

.X//備注：設(shè)R={<3,3>,<6,2>},S={<2,3>},則={<6,3>},={<2,3>}設(shè)A={1,2,3,4},P（A）（A的冪集）上劃定二元系以下,則P（A）/R=（D）A．A;B．P(A);C．{{{1}},{{1,2}},{{1,2,3}},{{1,2,3,4}}};D．{{},{2},{2,3},{{2,3,4}},{A}}6.設(shè)A={,{1},{1,3},{1,2,3}}則A上包括關(guān)系“”的哈斯圖為C）例題：畫出以下各關(guān)系的哈斯圖1）P={1,2,3,4},<P,≤>的哈斯圖.2）A={2,3,6,12,24,36},<A,整除>的哈斯圖.3）A={1,2,3,5,6,10,15,30},<A,整除>的哈斯圖以下函數(shù)是雙射的為（A）//雙射既是單射又是滿射A．f:IE,f(x)=2x;B．f:NNN,f(n)=<n,n+1>;C．f:RI,f(x)=[x];//x的象D．f:IN,f(x)=|x|.（注：I—整數(shù)集,E—偶數(shù)集,N—天然數(shù)集,R—實數(shù)集）8.圖中從v1到v3長度為3的通路有（D）條.//備注：分別是v1->v1->v1->v3,v1->v4->v1->v3,v1->v3->v1->v3A．0;B．1;C．2;D．3.以下圖中既不是Eular（歐拉）圖,也不是Hamilton（哈密頓）圖的圖是（B）在一棵樹中有7片樹葉,3個3度結(jié)點,其他都是4度結(jié)點則該樹有（A）個4度結(jié)點.A．1;B．2;C．3;D．4.//備注：樹的極點數(shù)=邊數(shù)+17+3×3+4n=2（7+3+n-1）解得n=1三.證明題1.R是齊集X上的一個自反關(guān)系,求證：R是對稱和傳達的,當且僅當<a,b>和<a,c>在R中有<b,c>在R中.證：“”

若

由R對稱性知

,由

R傳達性得“”若

,

有

任意任性

,因

若因此

R是對稱的若

,

則

即R是傳達的2.f和g都是群<G1,★>到<G2,*>證明<C,★>是<G1,★>的一個子群

的同態(tài)映照.其中C=

.證：,有

,又★

★★

<C,

★>

是

<G1,

★>的子群

.3.G=<V,E>(|V|=v,|E|=e)

是每一個面起碼由

k（k

3）條邊圍成的連通平面圖圖長短平面圖.（11證：①設(shè)G有r個面,則

,則分）

,由此證明彼得森圖（,即.而故

Peterson

）即得

.

（8

分）②彼得森圖為

,這樣

不建立

,因此彼得森圖非平面圖為：四.邏輯推演用CP規(guī)矩證明下題①P（附帶前提）US①③P④US③⑤

T②④IUG⑤⑦CP五.籌算題1.設(shè)齊集

A={a,b,c,d}

上的關(guān)系

R={<a,b>,<b,a>,