離散數(shù)學(xué)期末考試題(共5頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一、單項選擇題2.設(shè)集合A=1，2，3，下列關(guān)系R中不是等價關(guān)系的是（ D ）A.R=<1,1>,<2,2>,<3,3>； B.R=<1,1>,<2,2>,<3,3>,<3,2>,<2,3>；C. R=<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>；D. R=<1,1>,<2,2>,&

2、lt;3,3>,<1,2 >.3在公式（）F（x，y）（ y）G（x，y）中變元x是（ B ）A自由變元；(前面無或量詞) B既是自由變元，又是約束變元；C約束變元；(前面有或量詞) D既不是自由變元，又不是約束變元.4設(shè)A=1，2，3，4，5，6，7，8，下列選項正確的是（C）A1A； B1，2，3A； C4，5A； DÆA.5.設(shè)論域為l，2，與公式等價的是( A )A.A(1)A(2)； B. A(1)A(2)； C.A(1)A(2)； D. A(2)A(1).6.一棵樹有5個3度結(jié)點，2個2度結(jié)點，其它的都是l度結(jié)點，那么這棵樹的結(jié)點數(shù)是( B )A.13；

3、 B.14 ； C.16 ； D.17 ./設(shè)一度結(jié)點數(shù)為n,則有：5×3+2×2+n=2(5+2+n)-1 解得：n=7, 所以這棵樹的結(jié)點數(shù)為：m=5+2+7=14.7設(shè)A是偶數(shù)集合，下列說法正確的是（A）A<A,+>是群；B<A,×>是群；C<A,÷>是群；D<A,+>, <A,×>,<A,÷>都不是群。8下列圖是歐拉圖的是（ D ）10.下面不滿足結(jié)合律的運算是( C )A.； B.； C.；D.二、填空題12.設(shè)fRR,f(x)=x+3,gRR,g(x)

4、=2x+1,則復(fù)合函數(shù) , /f(g(x)=f(2x+1)=(2x+1)+3=2x+4/=g(f(x)=g(x+3)=2(x+3)+1=2x+7/備注：fg=fg(x)=g(f(x)13設(shè)S是非空有限集，代數(shù)系統(tǒng)<P（S），>中，其中P（S）為集合S的冪集，則P（S）對運算的單位元是 ，零元是 S 。14設(shè)<A，>是格，其中A=1，2，3，4，6，8，12，24，為整除關(guān)系，則3的補元是 8 。 /（注：什么是格？ 即任意兩個元素有最小上界和最大下界的偏序）15.命題公式的成真指派為 00，01，11 ，成假指派為 10 。16.設(shè)A=<2,2>，<3

5、,4>,<3,5>，B=<1,3>，<2,5>,<3,4>，那么dom(AB)= 3 , ran(AB)= 2,3,4,5/關(guān)系R的定義域：domR=x|y(<x,y>R),即R中所有有序?qū)Φ牡谝辉貥?gòu)成的集合。 關(guān)系R的值域：ranR=y|x(<x,y>R),即R中所有有序?qū)Φ牡诙貥?gòu)成的集合。 關(guān)系R的域：fldR=domRranR17. 在根樹中，若每一個結(jié)點的出度 最多為（或）m,則稱這棵樹為m叉樹。如果每一個結(jié)點的出度 都為（或=）m或0，則稱這棵樹為完全m叉樹。如果這棵樹的葉 都在同一層 ，那么稱為正則

6、m叉樹。18<Zn, >是一個群，其中Zn=0,1,2,n-1，則在<Z6, >中，1的階是 6 ，4的階是 3 。 /單位元是e=019. n點完全圖記為Kn，那么當(dāng) n 4 時，Kn是平面圖，當(dāng) n 5 時，Kn是非平面圖。20. 若圖中存在 回路 ，它經(jīng)過圖中所有的結(jié)點恰好 一次 ，則稱該圖為漢密爾頓圖(哈密頓圖) 。 / 歐拉圖三、計算題21. 求命題公式的主析取范式。解： =22. 設(shè)A=1,2,3,4，給上的二元關(guān)系R=<1,2>,<2,1>,<2,3>,<3,4>，求R的傳遞閉包。解：由R=<1,2&g

7、t;,<2,1>,<2,3>,<3,4>，得， 從而， ，于是=<1,1>,<1,3>,<2,2>,<2,4>，=<1,2>,<1,4>,<2,1>,<2,3>，=<1,1>,<1,3>,<2,2>,<2,4>=，故=<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>，<2,3>，<2,4>，<3

8、,4>23.設(shè)A=1，2，3，4，6，8，12，24，R為A上的整除關(guān)系，試畫<A，R>的哈斯圖，并求A中的最大元、最小元、極大元、極小元。 解：<A，R>的哈斯圖如右圖所示： A中的最大元為24、最小元為1、極大元為24、極小元為1。24.求下圖所示格的所有5元子格。 解：所有5元子格如下：26.用矩陣的方法求右圖中結(jié)點v1，v3之間長度為2的路徑的數(shù)目。/教材P289、290 所以，圖中結(jié)點v1，v3之間長度為2的路徑的數(shù)目有3條。/備注：鄰接矩陣中所有元素之和等于邊數(shù)。通路（v1->v1,v2,v3,v4）與回路（v1->v1,v2->v2,v->v3）四、證明題27. 在整數(shù)集Z上定義：，證明：<Z，>是一個群。證明：（1）對于，有，所以運算是封閉的。（2）對于，有，即，故運算是可結(jié)合的。（3）是單位元，因為，.（4），由，可知 是的逆元。綜上所述，<Z，>是一個群。28. 設(shè)R為N×N上的二元關(guān)系，證明R為等價關(guān)系。證明：因為，所以，故R具有自反性。，若，則，即，故，所以R具有對稱性。，若，則，從而，故，所以R具有對稱性。綜上所述，R為等價關(guān)系。五、綜合應(yīng)用題29在謂詞邏輯中構(gòu)造下面推理的證明：每個在學(xué)校讀書的人都獲得知識。所以如果沒有人獲得知識就沒有人在學(xué)校讀書。（個體域：所