西安交通大學1999年離散數學考研試題

1.  (30分)

　   請判斷下列各題的正確性。

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

   ⑵ A/B=A當且僅當B=Æ。

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

   ⑷ 設|A|=5，則A上恰有31個不同的等價關系。

   ⑸ 設R非空集合A上的關系，R是A上可傳遞的，當且僅當R○RÍR。

   ⑹ 若R1，R2均為非空集合A上的等價關系，那么R1○ R2也為A上的等價關系。

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

   ⑻ 設N為自然數集合，I為整數集合，´是算術乘法，則<N,´>與<I,´>同構。

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

   ⑽ 設<R,Å,Ä>為整環，|R|=n，則<R,Å,Ä>是域。

   ⑾ 設<R,Å,Ä>為域，<R,Å,Ä>為<F,Å,Ä>的子環，則<R,Å,Ä>為整環。

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

   ⒀ 存在7個結點的自補圖。

   ⒁ 下圖為平面圖。

圖1  題1(14)

   ⒂ 下圖為哈密爾頓圖。

圖2  題1(15)圖

 2  (8分)

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

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

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

 3  (10分)

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

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

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

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

 4  (6分)

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

 5  (8分)

   設G=（V,E）是簡單的無向平面圖，證明G中至少有一個結點的度數小于等于5。

 6  (10分)

   設G是連通的無向圖，且有2k>0個奇結點，

   證明：G中存在各邊不重復的k條簡單路P1，P2，…，Pk，使得

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

 7  (8分)

   設個體域為整數集合，將下述語句分別表示成僅含有N(e)、P(e)、Q(e)、E(e1,e2)、L(e1,e2)、D(e1,e2)所組成的謂詞公式：其中各謂詞定義如下：

   N(e)：  e是自然數，

   P(e)：  e是素數，

   Q(e)：  e是偶數，

   E(e1,e2)：e1=e2，

   L(e1,e2)：e1<e2，

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

   ① 沒有最大的素數；

   ② 并非所有的素數都不是偶數。

 8  (8分)

   判斷下列邏輯關系是否成立。若成立，請用指派分析法給出證明。否則，請給出相應的指派。

   ① $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分)

   構造形式推理過程：

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

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