离散数学试卷答案

《离散数学》期末考试试卷评分标准

每空3分共21分

1） A 3，5； B 6； C 2。 2）A GF∪S ；B S-M∪RG 3）1 4）0

一. （10分 每题5分）

1）x(F(x)yG(x,y))xy(F(x)G(x,y)) 2）xF(x)yG(x,y)xF(x)yG(z,y)

x(F(x)yG(z,y))xy(F(x)G(z,y))

二. （10分 每题2分）

1. p∧q 。 其中，p:小王聪明，q:小王用功。

2. q→p。 其中，p:天下大雨，q:他乘公共汽车上班。 3. ﹁p→﹁q。其中，p:经一事，q:长一智。

4.x(M(x)F(x))。 其中,M(x):x是人, F(x):x吃饭。 5. x(M(x)G(x))。 其中,M(x):x是人, M(x):x吸烟。 四. 成真赋值：010，100，101，110，111 ……4’

成假赋值：000，001，011 ……4’

非重言可满足式。 …. ..2’ 五. 解：符号化：p：甲盗窃了录音机。q：乙盗窃了录音机。

r：作案时间发生在午夜前。s：乙的证词正确。t：午夜时屋里灯光

没灭。

前提：p→r ，s→t ,，s→r ， t， p∨q。 结论：p或q

（1）s→t 前提引入 （2） t 前提引入 （3）s （1）（2）拒取式 （4）s→r 前提引入 （5）r （3）（4）假言推理 （6）p→r 前提引入 （7）p （5）（6）拒取式 （8）p∨q 前提引入 （9）q （7）（8）析取三段论

A卷答案 第 1 页 共 2 页

结论：乙盗窃了录音机。

六．解：彼得森图中有长度为奇数的圈，故不是二部图 ； …… 3’ 又彼得森图每个顶点度数都是3,故不是欧拉图 。 …… 3’ 七．6个。

八．每图3分

－ 九．-**+abc+de-f*gh……5’ ……5’ * －

* + * f

c d e + g h

a b

十．(5分)

（¬p→q）→(q→¬p) ¬(p∨q)∨(¬q∨¬p) ¬p∧¬q∨¬q∨¬p ¬p∨¬q ¬(p∨p) 是可满足式。 十一．（5分）证明：

设有k片树叶。由握手定理知：2m≥k+2(n-k), m=n-1,得k≥2。

A卷答案 第 2 页 共 2 页