《2005下离散数学A参考答案》由会员分享，可在线阅读，更多相关《2005下离散数学A参考答案（4页珍藏版）》请在金锄头文库上搜索。
1、 12005 下离散数学（A）参考答案 注：解答思路可能存在差异，描述方式也常常不唯一，下面仅仅给出典型的求解过程。 1. 设 E 为 a,b,c,d 这 4 个字母的全排列集合，A 为出现 ab 的排列集合，B 为出现 cd 的排列 集合。由容斥原理，不允许出现 ab 和 cd 的排列个数为： | E|-|AB|=4!-(3!+3!-2!)=10 2. （1）R 的关系矩阵是：0100101100001001（2）R 不是自反的，不是反自反的，不是对称的，不是反对称的，不是传递的； （3）r(R)=(0,0),(0,3),(1,1),(2,0),(2,1),(2,2),(2,3),(3,2)
2、,(3,3)； s(R)=(0,0),(0,2),(0,3),(1,2),(2,0),(2,1),(2,3),(3,0),(3,2)； t(R)=(0,0),(0,1),(0,2),(0,3),(2,0),(2,1),(2,2),(2,3),(3,0),(3,1),(3,2),(3,3)。 3. (1)对任意 xR,有3xx =0，即(x,x)S,所以 S 是自反的； (2)对任意 x,yR,设(x,y)S,则3yx 为整数，那么3xy 也为整数，即(y,x)S,所以 S 是对称的； (3)对任意 x,y,zR,设(x,y)S 且(y,z)S，则3yx ，3zy 为整数，那么3yx +3zy
3、=3zx 也为整数，即(x,z)S,所以 S 是可传递的； 由(1)(2)(3)知 S 是等价关系。 4. （1）可满足式 （2）可满足式 （3）可满足式 （4）矛盾式 （5）重言式 （6）重言式 5. （1）主析取范式：(PQ)(PQ) 主合取范式：(PQ)(PQ) （2）前束合取范式：xzu(P(x)Q(y)R(z)(P(x)Q(y)S(u) 6. 令 Q(x)：x 是有理数 R(x)：x 是实数 I(x)：x 是整数 则整个命题符号化为： x(Q(x)R(x), x(Q(x)I(x) |- x(R(x)I(x) 证明：(1) x(Q(x)I(x) P (2) Q(a)I(a) ES(1)
4、 (3) Q(a) I(2) (4) I(a) I(2) (5) x(Q(x)R(x) P (6) Q(a)R(a) US(5) (7) R(a) I(3)(6) 2(8) R(a)I(a) I(4)(7) (9) x(R(x)I(x) EG(8) 7. 要证明 Vh 与 V同构，需要证明如下几点： 1）同型：Vh 与 V同型？ 2）双射： 定义映射 f，并证明其为双射 定义映射 f：因为 h 是一个从 S 到 S的满射， S/h 的可允许划分，所以对于每一个xh S/h 必存在某个 xS，使得 x=h(x)，于是可以如下定义函数：f: S/h S ，使得 f(xh)=h(x)。 f 为满射：
5、对于任意 xS ，必存在 xS，使得 h(x) =x，从而存在xh S/h， ， 使得 f(xh)=h(x)，所以 f 是满射。 f 为单射：若 h(x)=h(y)，则 xhy，于是由h 的定义知xh=yh，所以 f 是单射 3）满足同态方程 由于 f(xh yh)=f(xoyh)=h(xoy)=h(x)*h(y) =f(xh)*f(yh). 所以，前述运算与双射函数满足同态方程。 综上， Vh 与 V同构。 8. （1）从以下几方面进行证明： 封闭性： a,bS, ab=a+b-a*bR 若 ab=1 即 a+b-a*b=1 (a-1)*(1-b)=0 a=1 或 b=1，矛盾，故 ab1
6、但 a bR，故 a bS 结合性:略. 单位元: 对于aS, 若 e 为单位元， 即需要满足 ae=a 即 a+e-a*e=a, e* （1-a） =0, 所 以 e=0（注意到 a1）. 即有 a0=a 又 0a=0+a-0*a=a,故 e=0 为单位元。 逆元: aS,若 ab=0 即 a+b-a*b=0,即 b=a/(a-1)S (注意到 a1) 即有 a（a/(a-1)）=0 又, （a/(a-1)）a = a/(a-1) +a- (a*a) /(a-1)=0 故 a/(a-1)为 a 之逆元. 综合上述几方面知是群. （2）构造出偏序集合的哈斯图如下图所示，显然可以判断，a，b P
7、(S)， 都有最大下界、最小上界，且 ab=ab, ab=ab，则为格。其导出的格代数为 . 39.（1）设 e,e分别为 G1,G2的单位元，显然，g(e)=h(e)=e,故 eG，从而 G. 由题设 GG1,要证明是的子群，需要证明对于 a,bG,a*b-1G. 而 a*b-1G1 是显然的，故只需要证明 g(a*b-1)=h(a*b-1), 即：g(a) o g(b-1)= h(a) o h(b-1),记为 (1)式. 而由 a,bG 知，g(a)=h(a) （记为（2）式） ，且 g(b)=h(b)（记为（3）式）. 而由 g(e)=h(e)即 g(b*b-1)=h(b*b-1)即 g
8、(b) o g(b-1)=h(b) o h(b-1)，结合（3）式得： g(b-1)=h(b-1). 于是，再结合（2）式知（1）式成立.即：g(a*b-1)=h(a*b-1). 所以，对于 a,bG,a*b-1G.即是的子群. （2）不是的正规子群，因为 要证明是的正规子群，需要证明对于 bG,aG1,有 a*b*a-1G. 需要证明g(a*b*a-1)=h(a*b*a-1), 即：g(a) o g(b)o g(a-1)= h(a) oh(b)o h(a-1)， 这里，显然仅有条件 g(b)=h(b)，不能保证上式成立. 10.（1）G 显然是连通图，当 n 为奇数时，每结点度数均为偶数，存
9、在欧拉回路，是欧拉图; 当 n 为偶数是，每个结点度数均为奇数，不存在欧拉回路，不是欧拉图. （2）当 n=5 时，G 不是平面图. （3）G 有（n=5）125 棵生成树，有 6 个不同构的四条边的生成子图. 11. 采用反证法. 假设 G 不是 Hamilton 图，则根据 Hamilton 图的判定定理，知至少存在两个结点的度数之和 小于 n，则该二结点所关联的边的数目 m1 小于 n，即 m1=C(n-1,2)矛盾. 所以，图 G 为 Hamilton 图. 12. （1）由于树 T 的每层的结点均仅仅与其上一层或下一层结点相邻，因此，可以将树 T 的第一、三、五层结点均置于集合 V1
10、 中，第二、四、六层结点均置于集合 V2 中, 显然，T 的任意边相关联的两结点分别在上述二集合中，且二集合内任意二结点间不相邻. 因此，树 T 是二部图. 按照（1） ，将 V1 种结点着色 r，V2 种结点着色 g. 这显然满足着色条件,因此，树 T 的色数 为 2. （2）对分支结点树 i 进行归纳. 41) 当 i=0，1 时，结论显然成立。 2) 设 i=k 时， t=(m-1)i+1 成立。 考虑 i=k+1 时，设 T 是具有 k+1 个分枝点，t 片叶的完全 m 分树。从 T 中找到一个具有m 片叶的分枝点 v，去掉 v 的 m 片叶，得到树 T。T仍是一个 m 分树，且具有 t-(m-1)片叶，k 个分枝点。由归纳假设，对于 T有： (t-(m-1) = (m-1) (i-1)+1 即 t=(m-1)i+1，亦即对于 i=k+1 时，结论仍成立。 由归纳原理，得证。 （3）T 的边数为结点数减 1，即：(i+t)-1=(t-1)/(m-1)+t)-1=m(t-1)/(m-1)=5(9-1)/(5-1)=10.
