1.  (30分)

　   請(qǐng)判斷下列各題的正確性。

   ⑴ 2A∩2B=2A∩B。

   ⑵ A/B=A當(dāng)且僅當(dāng)B=Æ。

   ⑶ (A´C)/(B´D)=(A/B)´(C/D)。

   ⑷ 設(shè)|A|=5，則A上恰有31個(gè)不同的等價(jià)關(guān)系。

   ⑸ 設(shè)R非空集合A上的關(guān)系，R是A上可傳遞的，當(dāng)且僅當(dāng)R○RÍR。

   ⑹ 若R1，R2均為非空集合A上的等價(jià)關(guān)系，那么R1○ R2也為A上的等價(jià)關(guān)系。

   ⑺ 設(shè)<P,≤>為半序集，ƹSÍP，若S有上界，則S必有上確界。

   ⑻ 設(shè)N為自然數(shù)集合，I為整數(shù)集合，´是算術(shù)乘法，則<N,´>與<I,´>同構(gòu)。

   ⑼ 設(shè)<G,*>是群，則G中至少有一個(gè)二階元素。

   ⑽ 設(shè)<R,Å,Ä>為整環(huán)，|R|=n，則<R,Å,Ä>是域。

   ⑾ 設(shè)<R,Å,Ä>為域，<R,Å,Ä>為<F,Å,Ä>的子環(huán)，則<R,Å,Ä>為整環(huán)。

   ⑿ 設(shè)<L,≤>為格，|L|=n，則<L,≤>為有界格。

   ⒀ 存在7個(gè)結(jié)點(diǎn)的自補(bǔ)圖。

   ⒁ 下圖為平面圖。

圖1  題1(14)

   ⒂ 下圖為哈密爾頓圖。

圖2  題1(15)圖

 2  (8分)

   設(shè)(G,*)為循環(huán)群，生成元為a，設(shè)(A,*)和(B,*)均為(G,*)的子群，而ai和aj分別為(A,*)和(B,*)的生成元。

   ① 證明(A∩B,*)是(G,*)的子群。

   ② 請(qǐng)問：(A∩B)是否為循環(huán)群。如果是，請(qǐng)給出其生成元。

 3  (10分)

   設(shè)(A,Å,Ä)是環(huán)，AA={f |f是A到A的函數(shù)}。定義AA上的運(yùn)算à和*如下，設(shè)f,gÎAA, 對(duì)于任意的xÎA。

   (fàg)(x)=f(x)Åg(x)；

   (f*g)(x)=f(x)Äg(x)；

   證明：(AA,à,*)是環(huán)。

 4  (6分)

   設(shè)A=<L1,≤1,*1,Å1>和B=<L2,≤2,*2,Å2>是兩個(gè)格，f是A到B的同態(tài)函數(shù)。證明A的同態(tài)象是B的子格。(注：A的同態(tài)象即：f(L1)={f(x)|xÎL1})。

 5  (8分)

   設(shè)G=（V,E）是簡(jiǎn)單的無向平面圖，證明G中至少有一個(gè)結(jié)點(diǎn)的度數(shù)小于等于5。

 6  (10分)

   設(shè)G是連通的無向圖，且有2k>0個(gè)奇結(jié)點(diǎn)，

   證明：G中存在各邊不重復(fù)的k條簡(jiǎn)單路P1，P2，…，Pk，使得

   E(G)=E(P1)∪E(P2)∪…∪E(Pk)。

 7  (8分)

   設(shè)個(gè)體域?yàn)檎麛?shù)集合，將下述語句分別表示成僅含有N(e)、P(e)、Q(e)、E(e1,e2)、L(e1,e2)、D(e1,e2)所組成的謂詞公式：其中各謂詞定義如下：

   N(e)：  e是自然數(shù)，

   P(e)：  e是素?cái)?shù)，

   Q(e)：  e是偶數(shù)，

   E(e1,e2)：e1=e2，

   L(e1,e2)：e1<e2，

   D(e1,e2)：e1|e2 (即e1整除e2)，

   ① 沒有最大的素?cái)?shù)；

   ② 并非所有的素?cái)?shù)都不是偶數(shù)。

 8  (8分)

   判斷下列邏輯關(guān)系是否成立。若成立，請(qǐng)用指派分析法給出證明。否則，請(qǐng)給出相應(yīng)的指派。

   ① $x(ØA(x)→B(x))→"xC(x)Þ"x(B(x)→C(x))；

   ② $x(A(x)→"yB(x,y))ÞØ"y$xB(x,y)→"xA(x)。

 9  (12分)

   構(gòu)造形式推理過程：

   ① ØR(ØPÚS), Q→ØS╞ P→(Q→R)；

   ② $x(A(x)→"yB(y))，"x(B(x)→$yC(y))╞ "xA(x)→$yC(y)。