离散数学习历年真题

“ ” 若<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 即R是传递的。 若<a,b> R，<b,c> R 则 <b,a> R b,c 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

2e2e

2 v e r v e

k。而 v e r 2故k即

得

e

k(v 2)

k 2。（8分）

②彼得森图为k 5,e 15,v 10，这样

e

k(v 2)

k 2不成立，

所以彼得森图非平面图。（3分）

二、 逻辑推演 16% 1、 证明：

①A ②A B

③A B C D ④C D ⑤D ⑥D E ⑦D E F ⑧F ⑨A F 2、证明

P（附加前提） T①I P T②③I T④I T⑤I P T⑥⑦I CP