西安交通大学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,≤>为半序集，Æ1Sí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)T"x(B(x)→C(x))；
② $x(A(x)→"yB(x,y))TØ"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)。