离散数学综合练习及答案

科技大学远程教育学院

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

数理逻辑

一、判断下列句子是否是命题，若是命题判断真值，并将其符号化。 1、今天天气真好！ 解：不是命题。 2、王华和民是同学。

解：是命题。真值视实际情况而定。p：王华和民是同学。 3、我一边吃饭，一边看电视。

解：是命题。真值视实际情况而定。p：我吃饭。q：我看电视。pq 4、没有不呼吸的人。

解：是命题。真值为1。Mx：x是人。Fx：x呼吸。xMxFx 二、求命题公式的真值表和成真赋值、成假赋值。 [(pq)r](pr)

解：

p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 pq (pq)r pr [(pq)r](pr) 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 成真赋值：000，001，010，011，101，111；成假赋值100，110 三、用真值表、等值演算两种方法判别公式类型。 1、[(pq)q]r

. 学习.资料.

.. . .

解：

p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 pq 1 1 1 1 0 0 1 1 (pq)q 0 0 1 1 0 0 1 1 [(pq)q]r 1 1 0 1 1 1 0 1 [(pq)q]r[(pq)q]r(pq)qr

(pq)qr[(pq)(qq)]r[(pq)q]r可满足式

2、q((pq)p) 解：Aq((pq)p)

p q 0 0 0 1 1 0 1 1 pq 1 1 0 1 (pq)p 0 0 0 1 ((pq)p) 1 1 1 0 A 1 1 1 1 q((pq)p)q(pq)p(pq)(pq)1

永真式

四、求命题公式的主析取式和成真赋值、成假赋值。 p(qr) 解：

p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 p(qr) 1 1 1 1 1 1 0 1 p(qr)(0， 1，2，3，4，5，7） . 学习.资料.

.. . .

成真赋值：000，001，010，011，100，101，111；成假赋值110 五、解释I如下：D是实数集，特定元素a=0；特定函数fx，y=xy；

特定谓词Fx，y：xxy[F(f(x，y)，x)]xy[F(xy，x)]xy[((xy)x)]

xy[(xy)x)]真值为假

2、xyz{F(x，y)F[f(x，z)，f(y，z)] 解：

xyz{F(x，y)F[f(x，z)，f(y，z)]}xyz[(xy)(xz)(yz)]

真值为真 六、

1、求前束式xF(x)yG(x，y) 解：

xF(x)yG(x，y)xF(x)yG(x，y)xF(x)yG(t，y)

xy[F(x)G(t，y)] 2、证明：x(A(x)B)xA(x)B 证明：

x(A(x)B)x(A(x)B)xA(x)BxA(x)B

xA(x)B七、写出下面推理的证明，要求写出前提、结论，并注明 推理规则。

（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，不能同时成立。 2、R1、R2是A上的具有自反性的二元关系，R1－R2也具有自反性。 3、A上恒等关系IA具有自反性、对称性、反对称性、传递性。 4、f：AB，g：BC，若fog是AC的满射，则f、g都是满射。 5、A =｛1，2，3，4｝，f是从A到A的满射，则也是从A到A的单射。

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

AB{{a,{b}},c,{c},{a,b},{a,b},c,{b}}AB{c,{a,b}}AB{{a,{b}},{c}}AB(AB)(BA)

{{a,{b}},{c}}{b}{{a,{b}},{c},{b}} F ） F ） T ） F ） T ）

. 学习.资料.

一、判断题 （ （ （ （ （二、填空题 三、集合 解： .. . .

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

解：A(BC)A(BC)ABCABAC(AB)(AC)

四、二元关系（共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的函数，若是指出是否是单射、满射、双射， 如果不是说明理由。 （1）A=｛1，2，3，4，5｝、B=｛5，6，7，8，9｝ f=｛1，8，3，9，4，10，2，6，5，9｝

解：f 是函数，由3，9，5，9 f 不是单射，也不是满射。

（2）A=｛1，2，3，4，5｝、B=｛5，6，7，8，9｝ f=｛1，7，2，6，4，8，1，9，5，10｝ 解：由1，7，1，9，f 不是函数。 （3）A、B都是实数集，fx = x3。

解：f 是函数， f 是单射，也是满射，f 是双射。 （4）A、B都是正整数集，f(x)x11

x1x1解：f 是函数， f 是单射，不是满射。

2、Aa，b，c，d，g、h都是AA的函数。

g：ab，ba，cd，dc h：ab，bc，cb，dc

g、h中哪个有反函数？若有则求出反函数。求出复合函数gg(x)、hg(x)。 解：g 是双射，有反函数，就是 g 自己。g1：ab，ba，cd，dc

gg(x)：aa，bb，cc，dd hg(x)：aa，bd，ca，dd

3、A、B都是有n个元素的集合，f：AB的函数。 证明：f是单射  f是满射。

证明：设f是单射，由于x1x2A，f(x1)f(x2)，所以ranf 有n 个元素， 又 ranfB，而 B 也只有 n 个元素，所以 ranfB

 设f是满射，若 f 不是单射，则 x1x2A，f(x1)f(x2)， 由于 A 中只有 n 个元素，所以 ranfB，与 ranfB 矛盾。

《离散数学》综合练习三参

代数系统

一、判断题

1、｛0，1，2，…，n｝对普通加法封闭。 （F）

. 学习.资料.

.. . .

2、在非负整数集Z+上定义运算·，x·y = min｛x，y｝，1是运算的幺元。（T） 3、实数集与普通乘法构成的代数系统中每个元素都有逆元素。 （F） 4、在代数系统Z，+，0中，0是零元。 （F） 5、非负整数集Z+与普通加法构成的代数系统是群。 （F） 6、M是n阶可逆矩阵的集合，×是矩阵乘法，M，×是群。 （T） 7、循环群的子群是循环群。 （T） 8、代数系统Z，+是代数系统R*，+的子代数。 （F） 二、填空题

1、A =｛x | x = 3n ，nN｝，对 乘法 运算封闭。 2、R*，+构成的代数系统是 半群 。 3、在代数系统Z，+，0中，0是 单位 元。

4、F =｛f | f：AA｝，o为函数的复合运算，F，o的单位元是 恒等函数 。 5、f、g都是从A到A的双射，(fog)－1 = g－1of－1 。

6、在代数系统S，*中，元素a、b都有逆元，则a－1－1= a ，a*b－1=b－1*a－1 。 7、循环群有 生成 元，使循环群中元素都是该元素的方幂。

8、V1=S1，o，V2=S2，*都有幺元，是V1到V2的同态，则把V1中的单 位元映射到 V2中的单位元 。 三、解答题

1、Q＋是正有理数集，×是普通乘法，Q+，×是否是半群、独异点、群？

解：普通乘法有结合律，单位元是 1 ，但 0 没有逆元，Q+，×是独异点。

2、实数集R上的运算 * ，a*b=a＋b＋a×b，＋是普通加法，×是普通乘法。 验证：R，*只能是独异点。

解： a，b，c R

. 学习.资料.

.. . .

a*b*c = a＋b＋a×b * c = a＋b＋a×b＋c＋a＋b＋a×b×c = a＋b＋c＋a×b＋a×c＋b×c＋a×b×c

a*b*c = a* b＋c＋b×c = a+b＋c＋b×c+a×b＋c＋b×c = a＋b＋c＋a×b＋a×c＋b×c＋a×b×c 运算 * 有结合律

由于运算 * 有交换律，设 e 是单位元。a  R a*e = a＋e＋a×e = a，1+ a ×e = 0 ，e = 0

设 a－1 是 * a 的逆元，a－1 * a = a－1 + a + a－1 × a = 0 1+ a a－1 =－a ，当 a  －1时，a 有逆元。 a = －1 无逆元，所以 Q+，×是独异点。

3、实数集R上的运算 * ，a*b=a＋b －2，＋是普通加法，是普通减法。 R，*是否是群？

解： a，b，c  R，

a*b*c = a＋b－2 * c = a＋b－2＋c－2 = a＋b＋c－4 a*b*c = a * c＋b－2 = a＋b＋c－2－2 = a＋b＋c－4 运算 * 有结合律

由于运算 * 有交换律，设 e 是单位元。a  R a*e = a＋e－2 = a，e－2 = 0 ，e = 2

设 a－1 是 * a 的逆元，a－1 * a = a－1 + a －2 = 2 a－1 = 4－a

所以 R，* 是群。

四、求8阶循环群｛e，a，a2，…，a7｝的各阶子群。 解：一阶子群｛e｝

. 学习.资料.

.. . .

二阶子群｛e，a4｝ 四阶子群｛e，a2，a4，a6｝ 八阶子群｛e，a，a2，…，a7｝

五、设代数系统〈A ，*〉有单位元，代数系统〈B ，〉无单位元。 证明：这两个代数系统不同构。

证明：若〈A ，*〉，〈B ，〉同构，则存在同构映射，又设 e 是〈A ，*〉 的单位元，则  e  是〈B ，〉中的单位元，与〈B ，〉无单位元矛盾。

《离散数学》综合练习四参

图论

一、判断题

1、2，2，5，2，1，3可以构成图的度数序列。 （ F ） 2、n阶无向完全图的边数为nn－1。 （ F ） 3、生成子图与母图有相同的边集。 （ F ） 4、最小生成树是不唯一的。 （ T ） 5、有向完全图是强连通图。 （ T ） 二、填空题

1、顶点和边都不相同的通路，称为 初级通路 。 2、无向树有m个树枝，则顶点数为 m +1 。

3、无向图顶点之间的连通关系具有自反性、 对称 性、 传递 性， 是 等价 关系。

(3) 4、A是有向图D的邻接矩阵，若A3中的元素aij2，则

顶点vi到vj 长度为 3 的通路有 2 条 。

. 学习.资料.

.. . .

5、A是有向图D的邻接矩阵，Bk=A+A2+…+Ak中元素bij0，则顶点vi到 vj 可达 。 三、解答题 1、在图1中

（1）求邻接矩阵A； （2）计算A2、A3、A4； （3）求B4=A+A2+A3+A4；

（4）v1到v2长度为2、3的通路各有多少条？ （5）v1到v2长度小于等于4的通路有多少条？ 解：

0101

（1）A0

011





0101

100



0

01110212（2）A2020101223000111，

A0212，A400110201000747（3）B4=A+A2+A3+A407470747 0434 323413323 122 . 学习.资料.

.. . .

（4）v1到v2长度为2、3的通路分别有1、2条 （5）v1到v2长度小于等于4的通路有7条

0100 2、有向图G的邻接矩阵A0011

1101

1000

（1）画出这个有向图； （2）求A2；

（3）G中长度为2的回路有多少条？

（4）G中v2到v1长度小于等于2的通路有多少条？

（5）A2中的元素a(2)31说明什么？

解：（1）画出这个有向图；

（2）

01000100011A2AA0011011010101101110121111100010000100

（3）G中长度为2的回路有2条

（4）G中v2到v1长度小于等于2的通路有2条

（5）A2中的元素a(2)31说明v3到v1长度等于2的通路有1条

四、特殊图

判别下列各图是否是欧拉图和哈密尔顿图，说明理由。

. 学习.资料.

.. . .

（1） （2） （3） 解：

1 只是哈密尔顿图，aefbcghda 是哈密尔顿回路 23是欧拉图，顶点度数都是偶数

23也是哈密尔顿图 abcgdfea、abcdefghija 分别是哈密尔顿回路 五、树

1、求下列各图的最小生成树。

解：

w = 1+1+2+3 = 7 w = 1+2+4+4 = 11

. 学习.资料.

.. . .

2、求下列带权的最优二叉树，并求权数。 （1）3，4，5，6，7，8，9 （2）1，2，4，6，9，12

解：（1）3，4，5，6，7，8，9 3，4，5，6，7，8，9

5，6，7，7，8，9

7，7，8，9，11

8，9，11，14

11，14，17

17，25

42W =7+11+14+25+42=119

. 学习.资料.

.. . .

（2）1，2，4，6，9，12

（2）1，2，4，6，9，12 1，2，4，6，9，12 3，4，6，9，12 6，7，9，12 9，12，13 13，21 34 W =3+7+13+21+34=78

. 学习.资料.