1、西安交通大學(xué) 1999 年入學(xué)離散數(shù)學(xué)試題1(30 分)請判斷下列各題的正確性。 2A2B=2AB。 AB=A 當(dāng)且僅當(dāng) B=。 (AC)(BD)=(AB)(CD)。 設(shè)|A|=5，則 A 上恰有 31 個不同的等價關(guān)系。 設(shè) R 非空集合 A 上的關(guān)系，R 是 A 上可傳遞的，當(dāng)且僅當(dāng) RRR。 若 R1，R2 均為非空集合 A 上的等價關(guān)系，那么 R1 R2 也為 A 上的等價關(guān)系。 設(shè)為半序集，SP，若 S 有上界，則 S 必有上確界。 設(shè) N 為自然數(shù)集合，I 為整數(shù)集合，是算術(shù)乘法，則與同構(gòu)。 設(shè)是群，則 G 中至少有一個二階元素。 設(shè)為整環(huán)，|R|=n，則是域。 設(shè)為域，為的子環(huán)，

2、則為整環(huán)。 設(shè)為格，|L|=n，則為有界格。 存在 7 個結(jié)點的自補(bǔ)圖。 下圖為平面圖。圖 1 題 1(14) 下圖為圖。圖 2 題 1(15)圖2 (8 分)設(shè)(G,*)為循環(huán)群，生成元為a，設(shè)(A,*)和(B,*)均為(G,*)的子群，而ai 和aj 分別為(A,*)和(B,*)的生成元。 證明(AB,*)是(G,*)的子群。 請問：(AB)是否為循環(huán)群。如果是，請給出其生成元。3 (10 分)設(shè)(A,)是環(huán)，AA=f |f 是 A 到 A 的函數(shù)。定義 AA 上的運(yùn)算 和*如下，設(shè) f,gAA, 對于任意的 xA。(fg)(x)=f(x)g(x)；(f*g)(x)=f(x)g(x)；證明

3、：(AA,*)是環(huán)。4 (6 分)設(shè) A=和 B=是兩個格，f 是 A 到 B 的同態(tài)函數(shù)。證明 A 的同態(tài)象是 B 的。(注：A 的同態(tài)象即：f(L1)=f(x)|xL1)。5 (8 分)設(shè) G=（V,E）是簡單的無向平面圖，證明 G 中至少有一個結(jié)點的度數(shù)小于等于 5。6 (10 分)設(shè) G 是連通的無向圖，且有 2k0 個奇結(jié)點，證明：G 中存在各邊不重復(fù)的 k 條簡單路 P1，P2，Pk，使得E(G)=E(P1)E(P2)E(Pk)。7 (8 分)設(shè)域為整數(shù)集合，將下述語句分別表示成僅含有 N(e)、P(e)、Q(e)、E(e1,e2)、L(e1,e2)、D(e1,e2)所組成的謂詞公式：其中各謂詞定義如下：N(e)： e 是自然數(shù)，P(e)： e 是素數(shù)，Q(e)： e 是偶數(shù)，E(e1,e2)：e1=e2，L(e1,e2)：e1e2，D(e1,e2)：e1|e2 (即 e1 整除 e2)， 沒有最大的素數(shù)； 并非所有的素數(shù)都不是偶數(shù)。8 (8 分)判斷下列邏輯關(guān)系是否成立。若成立，請用指派分析法給出證明。否則，請給出相應(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)造形式推