1、精選優(yōu)質文檔-傾情為你奉上一、填空2A，B，C表示三個集合，文圖中陰影部分的集合表達式為 (BC)-A A C C4公式的主合取范式為 。5若解釋I的論域D僅包含一個元素，則 在I下真值為 1 。6設A=1，2，3，4，A上關系圖如下，則 R2= (1,1),(1,3),(2,2),(2,4) 。 /備注： 7設A=a，b，c，d，其上偏序關系R的哈斯圖如下，則R= (a,b),(a,c), (a,d), (b,d), (c,d) U (a,a),(b,b)(c,c)(d,d) 。 /備注：偏序滿足自反性，反對稱性，傳遞性8圖的補圖為 。 /補圖:給定一個圖G,又G中所有結點和所有能使G成為的

2、添加邊組成的圖,成為補圖. 自補圖:一個圖如果同構于它的補圖,則是自補圖 9設A=a，b，c，d ，A上二元運算如下：*a b c dabcda b c db c d ac d a bd a b c 那么代數(shù)系統(tǒng)<A，*>的幺元是 a ，有逆元的元素為 a,b,c,d ，它們的逆元分別為 a,b,c,d 。 /備注：二元運算為x*y=maxx,y，x,yA。10下圖所示的偏序集中，是格的為 c 。 /（注：什么是格？即任意兩個元素有最小上界 和最大下界的偏序）二、選擇題1、下列是真命題的有（C、D）A ； B；C ； D。2、下列集合中相等的有（ B、C ） A4，3；B，3，4；

3、C4，3，3；D 3，4。3、設A=1，2，3，則A上的二元關系有（ C ）個。 A 23 ； B 32 ； C ； D 。 /備注：A的二元關系個數(shù)為：個。4、設R，S是集合A上的關系，則下列說法正確的是（ A ） A若R，S 是自反的， 則是自反的； B若R，S 是反自反的， 則是反自反的； X C若R，S 是對稱的， 則是對稱的； X D若R，S 是傳遞的， 則是傳遞的。 X /備注：設R=<3,3>,<6,2>,S=<2,3>, 則=<6,3> , =<2,3>5、設A=1，2，3，4，P（A）（A的冪集）上規(guī)定二元系如下，則

4、P（A）/ R=（ D ） AA ； BP(A) ； C1，1，2，1，2，3，1，2，3，4； D，2，2，3，2，3，4，A6、設A=，1，1，3，1，2，3則A上包含關系“”的哈斯圖為（ C ） /例題：畫出下列各關系的哈斯圖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,整除>的哈斯圖 7、下列函數(shù)是雙射的為（ A ） /雙射既是單射又是滿射Af : IE , f (x) = 2x ； Bf : NNN, f (n) = <n , n+1&

5、gt; ；Cf : RI , f (x) = x ；/x的象 Df :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->v3A0； B1； C2； D3。9、下圖中既不是Eular（歐拉）圖，也不是Hamilton（哈密頓）圖的圖是（ B ）10、在一棵樹中有7片樹葉，3個3度結點，其余都是4度結點則該樹有（ A ）個4度結點。A1；B2；C3；D4

6、。/備注：樹的頂點數(shù)=邊數(shù)+1 7+3×3+4n=2（7+3+n-1） 解得n=1三、證明題1、R是集合X上的一個自反關系，求證：R是對稱和傳遞的，當且僅當< a, b>和<a , c>在R中有<b , c>在R中。證：“” 若由R對稱性知，由R傳遞性得 “” 若，有 任意 ，因若 所以R是對稱的若， 則 即R是傳遞的2、f和g都是群<G1 ,>到< G2, *>的同態(tài)映射。證明<C , >是<G1, >的一個子群。其中C= 證：，有 ，又 < C , > 是 < G1 , >

7、的子群。3、G=<V, E> (|V| = v，|E|=e ) 是每一個面至少由k（k3）條邊圍成的連通平面圖，則 ， 由此證明彼得森圖（Peterson）圖是非平面圖。（11分）證：設G有r個面，則，即 。而 故即得 。（8分）彼得森圖為，這樣不成立， 所以彼得森圖非平面圖為： 四、邏輯推演1、用CP規(guī)則證明下題 P（附加前提） US P US TI UG CP五、計算題1、設集合A=a，b，c，d上的關系R=<a , b > ,< b , a > ,< b, c > , < c , d >用矩陣運算求出R的傳遞閉包t (R)。解： ， ， ， t (R)=<a , a> , <a , b> , < a , c> ,