西安交通大学1999年研究生入学考试离散数学试题 1(30分) 请判断下列各题的正确性 (1)24∩2=2。 (2)A\B=A当且仅当B=E。 (3)(A'C)\BD)=(A\B)(C\D)。 (4)设A|=5,则A上恰有31个不同的等价关系。 (5)设R非空集合A上的关系,R是A上可传递的,当且仅当RORR (6)若R,R2均为非空集合A上的等价关系,那么ROR2也为A上的等价关系 (7)设为半序集,ESP,若S有上界,则S必有上确界。 8)设N为自然数集合,I为整数集合,是算术乘法,则与同构 (9)设是群,则G中至少有一个二阶元素 00设为整环,|R|=n,则是域 D设为域,为的子环,则为整环 0D设为格,|L|=n,则为有界格。 03存在7个结点的自补图。 040下图为平面图。 囗“p 图1题1(14) 5下图为哈密尔顿图
西安交通大学 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 上的等价关系。 ⑺ 设为半序集，ƹSÍP，若 S 有上界，则 S 必有上确界。 ⑻ 设 N 为自然数集合，I 为整数集合，´是算术乘法，则与同构。 ⑼ 设是群，则 G 中至少有一个二阶元素。 ⑽ 设为整环，|R|=n，则是域。 ⑾ 设为域，为的子环，则为整环。 ⑿ 设为格，|L|=n，则为有界格。 ⒀ 存在 7 个结点的自补图。 ⒁ 下图为平面图。 图 1 题 1(14) ⒂ 下图为哈密尔顿图
图2题1(15)图 2(8分) 设(G,*)为循环群,生成元为a,设(A,*)和(B,*)均为(G,*)的子群,而a和a3分别 为(A,*)和(B,*)的生成元 ①证明(A∩B,*)是(G,*)的子群 ②请问:(A∩B)是否为循环群。如果是,请给出其生成元。 3(10分) (A,A,A)是环,A={ff是A到A的函数}。定义A上的运算a和*如下,设f,g 对于任意的xA (fag)(x)=f(x)Ag(x) (f*g)(x)=f(x)Ag(x) 证明:(A,a,*)是环 4(6分) 设A=L1,≤1,*,A>和B=是两个格,f是A到B的同态函数。证明A的 同态象是B的子格。(注:A的同态象即:f(L)={f(x)|xiL} 5(8分) 设G=(V,E)是简单的无向平面图,证明G中至少有一个结点的度数小于等于5 6(10分) 设G是连通的无向图,且有2k>0个奇结点 证明:G中存在各边不重复的k条简单路P1,P2,…,P,使得
图 2 题 1(15)图 2 (8 分) 设(G,*)为循环群，生成元为 a，设(A,*)和(B,*)均为(G,*)的子群，而 a i 和 a j 分别 为(A,*)和(B,*)的生成元。 ① 证明(A∩B,*)是(G,*)的子群。 ② 请问：(A∩B)是否为循环群。如果是，请给出其生成元。 3 (10 分) 设(A,Å,Ä)是环，A A ={f |f 是 A 到 A 的函数}。定义 A A 上的运算 à 和*如下，设 f,gÎAA , 对于任意的 xÎA。 (fàg)(x)=f(x)Åg(x)； (f*g)(x)=f(x)Äg(x)； 证明：(AA ,à,*)是环。 4 (6 分) 设 A=和 B=是两个格，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(P)UE(P2)U.UE(Ps) 7(8分) 设个体域为整数集合,将下述语句分别表示成仅含有N(e)、P(e)、Q(e)、E(e,e2)、 L(e1,e2)、D(e1,e2)所组成的谓词公式:其中各谓词定义如下 N(e):e是自然数 P(e):e是素数, e是偶数, E(en, e2): e=e L(e,e2):e1< D(e1,e2):ele2(即e整除e) ①没有最大的素数: ②并非所有的素数都不是偶数 8(8分) 判断下列逻辑关系是否成立。若成立,请用指派分析法给出证明。否则,请给出相 应的指派 ①$x(0A(x)→B(x))→"xC(x)b"x(B(x)→C(x)): ②$x(A(x)→"yB(x,y))b"ysxB(x,y)→"xA(x)。 9(12分) 构造形式推理过程 ①R(OPUS),Q→Bs卜P→(Q→R) ②$x(A(x)→"yB(y)),"x(B(x)→SyC(y)"xA(x)→$yC(y)
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)