離散數(shù)學(xué)模擬試卷二

1、離散數(shù)學(xué)模擬試卷二一、判斷選擇題（共20分，每小題2分）( ) 1. 在命題邏輯中，任何命題公式的主合取范式都是存在的，并且是唯一的；( ) 2. 設(shè)A上的恒等關(guān)系I，它既是A上的等價(jià)關(guān)系也是A上的偏序關(guān)系；( ) 3. 設(shè)G，*是群，對(duì)于G中的任意元素a，b有：（a × b）-1=b-1 × a-1；( ) 4. 連通圖G的任一邊一定為圖G的某一邊割集中的一條邊；( ) 5. 圖（a），（b），（c）兩兩同構(gòu)； （a） (b) (c)選擇題：6設(shè)有如下命題1) 如果地上有水，則天上下雨2) 如果天上下雨，則地上有水3) 如果地上沒(méi)有水，則天上不下雨4) 如果天上不下雨，則

2、地上沒(méi)有水哪些命題等價(jià)的（ ）A 1)與2)等價(jià) B 1)與3)等價(jià) C 1)與4)等價(jià) D 3)與4)等價(jià)7給定A=1、2、3上的關(guān)系R=<1, 1>, <2, 2>, <1, 3>, <3, 1>, <2, 3>則（ ）A R是自反的且傳遞B R不反自反且不對(duì)稱C R是反對(duì)稱且不對(duì)稱D R不自反且傳遞8下列敘述中錯(cuò)誤的是（ ）A 空集是任何一個(gè)集合的子集B 空集是任何一個(gè)群的子群C 每個(gè)集合都有子集合D 每個(gè)群都有子群9一個(gè)簡(jiǎn)單連通無(wú)向圖有n個(gè)結(jié)點(diǎn)，它的邊數(shù)至少有（ ）A 一條B n-1條C n條D n+1條10一個(gè)圖中，哪些分圖

3、的結(jié)點(diǎn)集合不是原圖的結(jié)點(diǎn)集的劃分（ ）A 強(qiáng)分圖B 單側(cè)分圖C 弱分圖D 連通子圖二、邏輯推證 PQR，RS，S =QP（8分） 三、求出下列命題公式的主析取范式。（6分）(P®(QÙR)Ù(ØP®(ØQÙR) 四、任何人如果他喜歡步行，他就不喜歡乘汽車，對(duì)于每個(gè)人或者喜歡乘汽車或者喜歡騎自行車，有的人不愛(ài)騎自行車，因而有的人愛(ài)步行。邏輯推證此結(jié)論的有效性。（10分） 設(shè)M(x): x是人； Q(x)； x喜歡步行S(x); x喜歡乘汽車 ； R(x)； x喜歡騎自行車五、設(shè)A=a,b,c,d，其上關(guān)系R=<b,b&g

4、t;，<b,c>，<c,a>，S=<b,a><c,d>,<d,a>，求 1）R·S 2)R的對(duì)稱閉包及傳遞閉包（10分）六、 已知有如圖的偏序關(guān)系，并求出其子集A=b,c, d, e,的極大元、極小元、最大元、最小元、上確界、下確界。（10分） f g e d c b a七、設(shè)G=（a,b）a，bR，b0，定義運(yùn)算（a，b）*(c,d)=(bc+a，bd)求證：<G，*>是一個(gè)群。（10分）八、某班級(jí)有學(xué)生四十名，共有三門選修課可供選擇，選修課課程名稱分別為A、B、C，其中有15名學(xué)生選A課程，有10名學(xué)生選B課程，6名學(xué)生選C課程，而且其中有5名學(xué)生三門課程都選。問(wèn)至少有多少學(xué)生三門選修課一門也沒(méi)選？（10分）九、證明下圖是否為漢密爾頓圖