离散数学综合练习及答案

.. .

.

. 学习.资料. 科技大学远程教育学院

《离散数学》综合练习一参考答案

数理逻辑

一、判断下列句子是否是命题，若是命题判断真值，并将其符号化。

1、今天天气真好！

解：不是命题。

2、王华和民是同学。

解：是命题。真值视实际情况而定。p：王华和民是同学。

3、我一边吃饭，一边看电视。

解：是命题。真值视实际情况而定。p：我吃饭。q：我看电视。pq

4、没有不呼吸的人。

解：是命题。真值为1。Mx：x是人。Fx：x呼吸。xMxFx

二、求命题公式的真值表和成真赋值、成假赋值。

)(])[(rprqp

解：

p q r pq rqp)( rp )(])[(rprqp

0 0 0 0 1 1 1

0 0 1 0 1 1 1

0 1 0 0 1 1 1

0 1 1 0 1 1 1

1 0 0 0 1 0 0

1 0 1 0 1 1 1

1 1 0 1 0 0 0

1 1 1 0 1 1 1

成真赋值：000，001，010，011，101，111；成假赋值100，110

三、用真值表、等值演算两种方法判别公式类型。

1、rqqp])[( .. .

.

. 学习.资料. 解：

p q r pq qqp)( rqqp])[(

0 0 0 1 0 1

0 0 1 1 0 1

0 1 0 1 1 0

0 1 1 1 1 1

1 0 0 0 0 1

1 0 1 0 0 1

1 1 0 1 1 0

1 1 1 1 1 1

rqqprqqqprqqprqqprqqprqqp])[()]()[()()(])[(])[(

可满足式

2、))((pqpq

解：))((pqpqA

p q qp pqp)( ))((pqp A

0 0 1 0 1 1

0 1 1 0 1 1

1 0 0 0 1 1

1 1 1 1 0

1

1)()()())((qpqppqpqpqpq

永真式

四、求命题公式的主析取式和成真赋值、成假赋值。

)(rqp

解：

p q r )(rqp

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1 1

1

1

1

1

1

0

1

），，，，，，7543210()(rqp .. .

.

. 学习.资料. 成真赋值：000，001，010，011，100，101，111；成假赋值110

五、解释I如下：D是实数集，特定元素a=0；特定函数fx，y=xy；

特定谓词Fx，y：x

1、)])(([xyxfFyx，，

解：

)])[()])(([)]([)])(([xyxyxxyxyxxyxFyxxyxfFyx，，，

真值为假

2、)]()([)({zyfzxfFyxFzyx，，，，

解：

)]()()[()]}()([)({zyzxyxzyxzyfzxfFyxFzyx，，，，

真值为真

六、

1、求前束式)()(yxyGxxF，

解：

)]()([)()()()()()(ytGxFyxytyGxxFyxyGxxFyxyGxxF，，，，

2、证明：BxxABxAx)())((

证明：

BxxABxxABxAxBxAxBxAx)()()())(())((

七、写出下面推理的证明，要求写出前提、结论，并注明

推理规则。

（1）如果乙不参加篮球赛，那么甲就不参加篮球赛。若乙参加篮球赛，那么.. .

.

. 学习.资料. 甲和丙就参加篮球赛。因此，如果甲参加篮球赛，则丙就参加篮球赛。

解：

p：甲参加篮球赛。q：乙参加篮球赛。r：丙参加篮球赛。

前提： q p ，q  pr ，

结论：p  r

证明：① q p 前提引入

② pq ①置换

③ q  pr 前提引入

④ q  pr ③置换

⑤ q  p  q  r ④置换

⑥ q  r ⑤化简

⑦ q  r ⑥置换

⑧ p  r ②⑦假言三段论

推理正确

（2）学会的成员都是专家。有些成员是青年人。所以，有些成员是青年专家。个体域是人的集合

Fx：x 是学会成员。Gx：x 是专家。Hx：x 是青年人。

前提：x Fx Gx，x Fx Hx

结论：x Fx Hx Gx

证明：① x Fx Hx 前提引入

② Fc Hc ①EI

③ x Fx Gx 前提引入 .. .

.

. 学习.资料. ④ Fc Gc ③UI

⑤ Fc ②化简

⑥ Gc ⑤④假言推理

⑦ Fc Hc Gc ②⑥ 合取

⑧ x Fx Hx Gx ⑦EG

推理正确

《离散数学》综合练习二参考答案

集合、关系、函数

一、判断题

1、对任意集合A，都有AA和A A，不能同时成立。 （ F ）

2、R1、R2是A上的具有自反性的二元关系，R1－R2也具有自反性。 （ F ）

3、A上恒等关系IA具有自反性、对称性、反对称性、传递性。 （ T ）

4、f：AB，g：BC，若fog是AC的满射，则f、g都是满射。 （ F ）

5、A =｛1，2，3，4｝，f是从A到A的满射，则也是从A到A的单射。 （ T ）

二、填空题

1、A－B∪AB = A 。

2、A有2个元素，B有3个元素，从A到B的二元关系有 26 个。

3、R是A上的二元关系，RoR－1一定具有的性质是 对称性 。

4、fx= lnx 是从 R+ 到 R 的函数。

5、f、g都是从A到A的双射，(fog)－1 = g－1of－1 。

三、集合

1、A={{a，{b}}，c，{c}，{a，b}}、B={{a，b}，c，{b}}

求A∪B、A∩B、A－B、AB

解：

}}{},{}},{,{{}{}}{}},{,{{)()(}}{}},{,{{}},{,{}}{,},,{},,{},{,}},{,{{bcbabcbaABBABAcbaBAbacBAbcbabaccbaBA ..

.

.

. 学习.资料. 2、A={{a，{b}}，c，Ø} 求A的幂集。

解：PA={Ø，｛Ø｝，{{a，{b}}}，｛c｝，｛{a，{b}}，c｝，｛{a，{b}}，Ø｝，｛c，Ø｝}，A}

3、证明：A－B∪C = A－B∩A－C

解：)()()()(CABACABACBACBACBA

四、二元关系（共30分）

1、A＝{a，b，c，b}，R＝{，，，}

用关系矩阵求R4，写出R4的集合表示。

2、指出二元关系满足哪种性质，不满足哪种性质，说明理由。

解：满足反对称性；不满足自反性，反自反性，对称性，传递性

3、A =｛1，2，3，4，5，6｝，S =｛｛1，2｝，｛3｝，｛4，5，6｝｝

画出由S产生的等价关系的关系图。

解：

4、画出偏序集的哈斯图，并指出最大元、最小元、极大元、极小元。

｛1，2，3，…，12｝整除关系

解：

最大元：无；最小元、极小元：1；极大元：7，8，9，10，11，12

五、函数 .. .

.

. 学习.资料. 1、确定以下各题中f是否是从AB的函数，若是指出是否是单射、满射、双射，