离散数学

??(?P?Q) ?P??Q 7. 答案：

解：此题答案不唯一 （1）R = {,} （2）S={,} 8. 答案：

解：该矩阵不对称，所以G是有向图，如右图。d-(V2)=1，d+(V2)=2 9. 答案：

解：此题答案不唯一 （1）R = {,,} （2）S={,,} 10. 答案：

解：RA={<1,1><1,3><1,4>,<1,12>,<1,24>,<3,3>,<3,12>,<3,24>,

<4,4>,<4,12>,<4,24>,<12,12>,<12,24>,<24,24>}

11. 答案：

解：1）交换律：a*b=a+b-ab=b+a-ba=b*a所以满足交换律

2）结合律：(a*b)*c=(a+b-ab)*c= a+b-ab+c-(a+b-ab)c

= a+b+c -ab -ac-bc+abc =a+b+c-ac -ab -bc +abc

a*(b*c)=a*(b+c-bc)=a+ b+c-bc-a(b+c-bc) 所以(a*b)*c= a*(b*c)

所以满足结合律。

12. 答案：

解：RA={<1,1><1,2><1,5>,<1,10>,<1,20>,<2,2>,<2,10>,

<2,20>,<5,5>,<5,10>,<5,20>,<10,10>,<10,20>,<20,20>}

13. 答案：

解：1）交换律：a*b=a+b-3=b+a-3=b*a所以满足交换律

2）结合律：(a*b)*c= (a+b-3)+c –3 = a+b+c-6

a*(b*c)=a+(b+c-3)-3=a+b+c-6 所以(a*b)*c= a*(b*c) 所以*满足结合律。

三、证明题 1. 答案：

证明：(1) A?B (2) A

P

P(附加前提) T(1),(2)I

(3)B

(4) ?(BC) P (5) ?B??C T(4)E (6) ?B T(6)I (7)B??B(矛盾) T(3),(6)I 2. 答案：

证明：a)自反性：对任意a?A，因为?A,?S，

所以?R?S，即R?S具有自反性。

b)对称性：对任意a,b?A，如果有?R?S，则?R且?S。

因为R,S是等价关系，所以具有对称性， 所以?R且?S。

所以?R?S，即R?S具有对称性。

c)传递性：对任意a,b,c?A，若有,?R?S 则,?R且,?S

则因为R,S是等价关系，所以具有传递性， 所以?R且?S

所以?R?S，即R?S具有传递性。

所以R?S是A上的等价关系。

3. 答案：

证明：显然?是G上的二元运算（即满足封闭性），要证G是群，需证结合律成立，同时有幺元，每个元素有逆元。

（1）?a,b,c?G，有(a?b)?c?(a*x*b)*x*c?a*x*(b*x*c)?a?(b?c) 所以运算是可结合的。

（2）x?1是?G,??的幺元。事实上，?a?G，有

a?x?1?a*x*x?1?a；x?1?a?x?1*x*a?a

（3）?a?G，x?1*a?1*x?1是a在?G,??中的逆元。事实上，

a?(x?1*a?1*x?1)?a*x*x?1*a?1*x?1?x?1 (x?1*a?1*x?1)?a?x?1*a?1*x?1*x*a?x?1 由以上证明，?G,??是群。 4. 答案：

证明：(1)D P（附加前提） (2) ?DA P (3)A

T(1)(2)I

(4) A?(B?C) P

(5) (B?C) T(3)(4)I (6) B P

(7)C T(5)(6)I (8) D?C

CP

5. 答案：

证明：因为有向图中，

每条有向边必对应一个入度和一个出度，

所以，结点入度之和等于边数，出度之和也等于边数，

因此，所有有入度之和等于出度之和。

6. 答案：

证明： (1) ?AB

(2) A?B

P P T(3)E T(4)E T(5)E T(2)(6)I

T(1)E

(3) C??B (4) ?C?B (5) ?B?C

(6) B??C (7) A??C

7. 答案：

证明：a)自反性：对任意a?A，因为?A,?S，

所以?R?S，即R?S具有自反性。

b)对称性：对任意a,b?A，如果有?R?S，则?R并且?S。

因为R,S是相容关系，所以具有对称性， 所以?R并且?S。

所以?R?S，即R?S具有对称性。

所以R?S是A上的相容关系。

8. 答案：

证明：设G’中有m’条边，则m+m’ = 11*(11-1)/2 = 55。

若G,G’均为平面图，则m<=3*11-6=27，m’<=3*11-6=27 则m+m’<=27+27=54与上矛盾， 所以G或G’是非平面图。

9. 答案：

证明：a)自反性：对任意a?A，f(a)=f(a)，所以aRa，即R是自反的。

b)对称性：对任意a，b?A，若aRb，即f(a)=f(b)，

即f(b)=f(a)，故bRa，即R是对称的。

c)传递性：对任意a，b，c?A，若aRb，bRc，即f(a)=f(b)，f(b)=f(c)

即f(a)=f(b) =f(c)，故aRc，即R是传递的。

所以R是A上的等价关系。

10. 答案：

证明：

由运算表可知*运算满足封闭性；

由运算表可知a为幺元，每个元素有逆元是其本身； 所以为群 11. 答案：

证明：由欧拉公式v-e+r=2知：6-12+r=2解得r=8。

又每个面至少由三条边围成，所以2*12>=3r得r<=8。 因此每个面恰由三条边围成。