态映射，证明C★是G1★的一个子群。其中Cxx∈G1且fxgx３、GVE8分
Vv，Ee是每一个面至少由k（k≥3）条边围成的连通平面
图，则
e≤
kv2k2，由此证明彼得森图（Peterso
）图是非平面图。（11分）
四、逻辑推演16
用CP规则证明下题（每小题8分）1、A∨B→C∧DD∨E→FA→F2、xPx→QxxPx→xQx
五、计算18
1、设集合Aa，b，c，d上的关系Rabbabccd用矩阵运算求出R的传递闭包tR。（9分）
2、如下图所示的赋权图表示某七个城市v1v2Lv7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（９分）
试卷一答案：一、填空20（每小题2分）1、0，1，2，3，4，6；2、BCA；3、1；4、P∨S∨R∧P∨S∨R；5、1；6、11132224；7、abacadbdcdUIA；8、
9、a；abcd；adcd；10、c
f二、选择20（每小题2分）题目答案1CD2B、C3C4A5D6C7A8D9B10A
三、证明261、证：“”
abc∈X
若abac∈R由
R
对称性知
baca∈R，由R传递性得bc∈R
“”若ab∈R，ac∈R有
bc∈R
任意
ab∈X，因
aa∈R若ab∈R∴ba∈R所以R是对称的。
若ab∈R，bc∈R即R是传递的。2、证则ba∈R∧bc∈R∴ac∈R
ab∈C
1
，
有
fagafbgb
1
，
又
fb1f
bgb1g1b∴fb1f
1
bg1bgb1
∴fa★b1faf
bgagb1ga★b1
∴a★b1∈C
3、证：
∴C★是G1★的子群。
①设G有r个面，则
2e∑dFi≥rk
i1
r
，即
r≤
2ek。而ver2故
2ver≤ve
2ek即得
e≤
kv2k2。分）（8e≤kv2k2不成立，
②彼得森图为k5e15v10，这样
所以彼得森图非平面图。分）（3
二、逻辑推演161、证明：
f①A②A∨B③A∨B→C∧D④C∧D⑤D⑥D∨E⑦D∨E→F⑧F⑨A→F2、证明①xPx②Pc③xPx→Qx④Pc→Qc⑤Qc⑥xQx⑦xPx→xQx
P（附加前提）T①IPT②③IT④IT⑤IPT⑥⑦ICP
P（附加前提）US①PUS③T②④IUG⑤CP
三、计算181、解：
01MR00
1000r