西安交通大学1999年研究生入学考试 离散数学试题

1  (30分)

    请判断下列各题的正确性。

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

    ⑵ A\B=A当且仅当B=Æ。

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

    ⑷ 设|A|=5，则A上恰有31个不同的等价关系。

    ⑸ 设R非空集合A上的关系，R是A上可传递的，当且仅当R○RÍR。

    ⑹ 若R₁，R₂均为非空集合A上的等价关系，那么R₁○ R₂也为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ⁱ和a^j分别为(A,*)和(B,*)的生成元。

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

    ② 请问：(A∩B)是否为循环群。如果是，请给出其生成元。

  3  (10分)

    设(A,Å,Ä)是环，A^A={f |f是A到A的函数}。定义A^A上的运算à和*如下，设f,gÎA^A, 对于任意的xÎA。

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

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

    证明：(A^A,à,*)是环。

  4  (6分)

    设A=1,≤₁,*₁,Å₁>和B=2,≤₂,*₂,Å₂>是两个格，f是A到B的同态函数。证明A的同态象是B的子格。(注：A的同态象即：f(L₁)={f(x)|xÎL₁})。

  5  (8分)

    设G=（V,E）是简单的无向平面图，证明G中至少有一个结点的度数小于等于5。

  6  (10分)

    设G是连通的无向图，且有2k>0个奇结点，

    证明：G中存在各边不重复的k条简单路P₁，P₂，…，P_k，使得

    E(G)=E(P₁)∪E(P₂)∪…∪E(P_k)。

  7  (8分)

    设个体域为整数集合，将下述语句分别表示成仅含有N(e)、P(e)、Q(e)、E(e₁,e₂)、L(e₁,e₂)、D(e₁,e₂)所组成的谓词公式：其中各谓词定义如下：

    N(e)：  e是自然数，

    P(e)：  e是素数，

    Q(e)：  e是偶数，

    E(e₁,e₂)：e₁=e₂，

    L(e₁,e₂)：e₁2，

    D(e₁,e₂)：e₁|e₂ (即e₁整除e₂)，

    ① 没有最大的素数；

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

  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)。