西安交通大学1999年研究生入学考试离散数学试题
130分请判断下列各题的正确性。⑴2∩22
ABA∩B
。
⑵ABA当且仅当B。⑶ACBDABCD。⑷设A5，则A上恰有31个不同的等价关系。⑸设R非空集合A上的关系，R是A上可传递的，当且仅当R○RR。⑹若R1，R2均为非空集合A上的等价关系，那么R1○R2也为A上的等价关系。⑺设P≤为半序集，SP，若S有上界，则S必有上确界。⑻设N为自然数集合，I为整数集合，是算术乘法，则N与I同构。⑼设G是群，则G中至少有一个二阶元素。⑽设R为整环，R
，则R是域。⑾设R为域，R为F的子环，则R为整环。⑿设L≤为格，L
，则L≤为有界格。⒀存在7个结点的自补图。⒁下图为平面图。
f图1⒂下图为哈密尔顿图。
题114
图228分
题115图
设G为循环群，生成元为a，设A和B均为G的子群，而a和a分别为A和B的生成元。①证明A∩B是G的子群。②请问：A∩B是否为循环群。如果是，请给出其生成元。310分设A是环，Aff是A到A的函数。定义A上的运算à和如下，设fgA对于任意的xA。fàgxfxgx；fgxfxgx；证明：Aà是环。
AAAA
i
j
f4
6分
设AL1≤111和BL2≤222是两个格，f是A到B的同态函数。证明A的同态象是B的子格。注：A的同态象即：fL1fxxL1。58分设G（VE）是简单的无向平面图，证明G中至少有一个结点的度数小于等于5。610分设G是连通的无向图，且有2k0个奇结点，证明：G中存在各边不重复的k条简单路P1，P2，…，Pk，使得EGEP1∪EP2∪…∪EPk。78分
设个体域为整数集合，将下述语句分别表示成仅含有Ne、Pe、Qe、Ee1e2、Le1e2、De1e2所组成的谓词公式：其中各谓词定义如下：Ne：Pe：Qe：e是自然数，e是素数，e是偶数，
Ee1e2：e1e2，Le1e2：e1e2，De1e2：e1e2即e1整除e2，①没有最大的素数；
f②并非所有的素数都不是偶数。88分判断下列逻辑关系是否成立。若成立，请用指派分析法给出证明。否则，请给出相应的指派。①xAx→Bx→