西安交通大学15年7月课程考试《离散数学》作业考核试题

解: 一般地, R1∘R2≠ R1∘R2.

反例: R1={(1,3), (3,1)} 对称! R2={(3,2), (2,3)} 对称! R1∘R2 ={(1,2)} 不对称!

证明: 不妨记

A={a1, a2, a3, …,an, …} B={b1, b2, b3, …, bm} 作映射 φ: A→A∪B

φ(ai)=bi (i=1,…,m)

φ(ai)=ai-m (i=m+1,m+2,…) 则可以说明φ为A→A∪B的双射， 故结论得证。

证明：因为G不连通，则G可以分为若干连通子图: G1=（V1，E1），--- ，Gn=（Vn，En）

根据G的补图的构造过程知V1中每个顶点与其它顶点集V2，--- ，Vn中顶点有边相连。 这样， 在G的补图中，有

 分别属于两个顶点子集Vi与Vj中的任意两个顶点之间有边直接相连，  属于同一个顶点子集Vi的任意两个顶点借助顶点子集Vj的任意一个顶点连通。

所以，根据连通的定义知：G的补图一定连通 。

证明：设 T=(V,E)是一棵树，若T中最多只有一片树叶，则有 ∑d(v) ≥1+2(|V|-1)=2|E|+1,

这与结论 ∑ d(v) =2|E| 矛盾! 矛盾说明 T 不止一片树叶。

解: A×B={({a},{b}), ({a},a), (a, {b}), (a, a), (b, {b}), (b, a)} AB=(A-B) ∪(B-A)={{a}, b, {b}}

P(A)={Ø, {a}, a, b, {{a}, a}, {{a},b}, {a,b}, A}.

证明: (1) a,b HK,就有a,b H, a,b K， 因为H, K是群G的子群，

所以，a*b-1H，a*b-1K，因此a*b-1 HK。故 HK是G的子群。 (2) 对于a HK,  gG, 就有a H，aK。 因为H，K是群G的正规子群，所以 g*a*g-1H, g*a*g-1K,

从而有g*a*g-1HK， 故HK是G的正规子群。

解：

（2）因为n个顶点的无向完全图有n(n-1)/2个边，所以自互补图各有n(n-1)/4个边，因此，n=4k或4k+1。

解：格? ✔ 分配格? ✔? 有补格? ✘

布尔格 ✘

解: (p∧q)((q→r)p) = (p∧q)((q∨r)p)

= (p∧q)(((q∨r) ∧p) ∨((q∨r) ∧p)) = (p∧q)((q∧p)∨(r∧p) ∨(q∧r) ∧p)) = p∨q∨ (q∧p)∨(r∧p) ∨(q∧r∧p) = p∨q∨ (q∧r∧p)

= (p∧q∧r) ∨ (p∧q∧r) ∨ (p∧q∧r) ∨ (p∧q∧r) ∨ (p∧q∧r) ∨ (p∧q∧r) ∨ (p∧q∧r) =∑(0,1,2,3,4,5,6) =∏(7)= p∨q∨r

证明:

(1) pp∨q 公理B (2) pp∨p 代入 (3) (pr) ((qr) ((p∨q) r)) 公理D (4) (pp) ((pp) ((p∨p) p)) 代入 (5) p  p 公理C

(6) (pp) ((p∨p) p) (4)(5)分离 (7) (p∨p) p (5)(6)分离 (8) (pq) ((qp) (pq)) 公理A (9) (p(p∨p)) (((p∨p)p) (p(p∨p))) 代入

(10) ((p∨p)p) (p(p∨p)) (2)(9)分离 (11) (p(p∨p)) (7)(10)分离