离散数学
二、选择 20% （每小题 2分）
三、证明 26%
1、 证：
“ ” a,b,c X 若<a,b>,<a,c> R由
R
对称性知
<b,a>,<c,a R，由R传递性得 <b,c> R
“ ” 若<a,b> R，<a,c> R有 <b,c> R 任意 a,b X，因
<a,a> R若<a,b> R <b,a> R 所以R是对称的。
<a,c> R 若<a,b> R，<b,c> R 则 <b,a> R b,c R
即R是传递的。 2、 证
a,b C
，有
f(a) g(a),f(b) g(b)
，又
f(b 1) f 1(b),g(b 1) g 1(b) f(b 1) f 1(b) g 1(b) g(b 1)
f(a★b 1) f(a)*f 1(b) g(a)*g(b 1) g(a★b 1)
a★b 1 C < C , ★> 是 < G1 , ★>的子群。
3、 证：
r
①设G有r个面，则
2e d(Fi) rk
i 1
，即
r
2e
k。而 v e r 2故
2 v e r v e
2ek(v 2)
e
k即得 k 2。（8分）
e
k(v 2)
k 2不成立，
②彼得森图为k 5,e 15,v 10，这样
所以彼得森图非平面图。（3分）
二、 逻辑推演 16% 1、 证明：