东北师范大学离散数学期末试卷10年

一．每个小题2分，共20分。

1．C        2．B          3．B        4．D       5．(PQ) H   

6．{A}      7．10         8．125       9．11，4

二．每个空2分，共10分。

1.     2. √     3. √      4.      5. 

三．每题10分，共50分。

1．（PQ）R

（PQR）（PQR）（PQR）（PQR）（PQR）

1,3,4,5,70,2,6(PQR)(PQR)(PQR) 

（主析取范式和主合取范式各占5分）

2．(x)P(y,x)(y)Q(y)(x)P(y,x)(y)Q(y)(x)P(y,x)(y)Q(y) 

(x)P(s,x)(y)Q(y) 

(x)(y)(P(s,x)Q(y))

（前两步骤各3分，后两步骤各2分）

3．解：(1) 2*（-5）=2-5+2×2×（-5）= -23

(2) 运算可结合，可交换。因为(a*b)*c=a*(b*c) , a*b=b*a

(3) 单位元为0。 (4) 零元为  -0.5 

每小题各2.5分。

4．R={<1,1>,<2,2>,<3,3>,<1,2>,<2,3>,<2,1>,<3,2>,<,1,3>,<3,1>,<4,4>,<5,5>}

有步骤的，按步骤给分。共10分。

5．解：5个1度结点。6分

两个图各2分

四．选做两题，每题10分，共20分。

1.证明：左边=(A∪ )∩(A∪B)   （同一率）  （5分）

=A∪(∩B)  （分配率）        （2分）

=A∪      （零率）           （2分）

=A=右边   （同一率）          （1分）

或用逻辑推演法证明

2. 证明：反证法：假设每个结点的度数>4，即deg(vi)≥5，因为2e=

即v≤2e/5，由于平面图(|v|≥3) 有e≤3v-6，把v≤2e/5代入后得到e≤6e/5-6，即有e≥30，与边数小于30矛盾。

每句2分。

3.证明：因为f1 , f2是两代数系统之间的同态

   所以 f1(ab)= f1(a)*f2(b) ,    f2(ab)= f2(a)*f2(b)

又因为 是可交换半群，所以*运算可交换，由g(a)= f1(a)*f2(a) 

      g(ab)=f1(ab)*f2(ab)=f1(a)*f2(b)*f2(a)*f2(b)=f1(a)*f2(a)*f1(b)*f2(b)=g(a)*g(b)

因此，g是一个由到的同态，得证。

每句2分。

4. 证明：显然HG。运算*在H中显然满足结合性。（2分）

对于任意的x,yH，以及任意的aG，

因为 (x*y)*a=x*y*a=x*a*y=a*x*y=a*(x*y)

所以，x*y H，这说明*关于H是封闭的。     （3分）

因为e*a=a*e，所以e H。                   （2分）

对于任意的x H，由于x*a=a*x， 

所以  x-1*(x*a)*x-1=x-1*(a*x)*x-1

即得   a*x-1=x-1*a

这就表明x-1H。                           （3分）

综上所述，是的子群。