离散数学试卷及答案(25)

离散数学试卷（25）

166

一、填空题：（每空1分，本大题共15分）

1．给定命题公式A 、B ，若 ，则称A 和B 是逻辑相等的。

2．命题公式)(Q P →?的主析取范式为 ，主合取范式的编

码表示为 。

3．设E 为全集， ，称为A 的绝对补，记作～A ，

且～（～A ）= ，～E = ，～Φ= 。

4．设},,{c b a A =考虑下列子集

}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =，}},{},{{3c b a S =，}},,{{4c b a S = }}{},{},{{5c b a S =，}},{},{{6c a a S =

则A 的覆盖有 ，A 的划分有 。

5．设S 是非空有限集，代数系统＜ （S ），?，?＞中， （S ）对?的幺元为 ， 零元为 。 （S ）对?的幺元为 ，零元为 。

6．若>=

W(G-S) S 成立，其中W(G-S)是 。

二、单项选择题：（每小题1分，本大题共10分）

1．下面命题公式（ ）不是重言式。

A 、)(Q P Q ∨→；

B 、P Q P →∧)(；

C 、)()(Q P Q P ∨?∧?∧?；

D 、)()(Q P Q P ∨??→。

2．命题“没有不犯错误的人”符号化为（ ）。

设x x M ：

)(是人，x x P ：)(犯错误。 A 、))()((x P x M x ∧?； B 、)))()(((x P x M x ?→??；

C 、)))()(((x P x M x ∧??；

D 、)))()(((x P x M x ?∧??。

3．设}{Φ=A ，B = ( (A))，下列各式中哪个是错误的（ ）。

离散数学试卷（25）

167 A 、B ?Φ； B 、B ?Φ}{， C 、B ∈Φ}}{{； D 、?ΦΦ}}{,{ (A)。

4．对自然数集合N ，哪种运算不是可结合的，运算定义为任N b a ∈,（ ）。

A 、),min(b a b a =*；

B 、b a b a 2+=*；

C 、3++=*b a b a ；

D 、)3(mod ,b a b a =*。

5．设Z 为整数集，下面哪个序偶不够成偏序集（ ）。

A 、)(,小于关系：<>

<≤=

6．任意具有多个等幂元的半群，它（ ）。

A 、不能构成群；

B 、不一定能构成群；

C 、不能构成交换群；

D 、能构成交换群。

7．设≤><,A 是一个有界格，它也是有补格，只要满足（ ）。

A 、每个元素都有一个补元；

B 、每个元素都至少有一个补元；

C 、每个元素都无补元；

D 、每个元素都有多个补元。

8．设>=

。 A 、完全图； B 、树； C 、简单图； D 、多重图。

9．给定无向图>=

A 、},,,{4341><>

B 、},,,{6451><>

C 、},,,{8474><>

D 、},,,{3221><>

10．有n 个结点)3(≥n ，m 条边的连通简单图是平面图的必要条件（ ）。

A 、63-≥m n ；

B 、63-≤m n ；

C 、63-≥n m ；

D 、63-≤n m 。

离散数学试卷（25）

168 三、判断改正题：（每小题2分，本大题共20分）

1．设A ，B 为任意集合，不能B A B A ∈?且。 （ ）

2．设R 是集合A 上的关系，若21,R R 是对称的，则21R R 也是对称的。（ ）

3．群中可以有零元（对阶数大于1的群）。 （ ）

4．循环群一定是Abel 群。 （ ）

5．每一个链都是分配格。 （ ）

6．不可能有偶数个结点，奇数条边的欧拉图。 （ ）

7．图G 中的每条边都是割边，则G 必是树。 （ ）

9．公式)())()((y R x Q x P x ∧→?中x ?的辖域为)(x P 。 （ ）

10．公式),()(y x yQ x xP ?→?的前束范式为

)),()((y x Q x P y x →??。 （ ）

四、简答题（共20分）

1．用等值演算法求下面公式的主析取范式，并求其成真赋值。

R Q P →∨)(

2．集合}4,3,2,1{=A 上的关系

}4,4,3,4,4,3,1,3,3,3,2,2,3,1,1,1{><><><><><><><><=R ，写出关系矩阵R M ，画出关系图并讨论R 的性质。

3．有n 个药箱，若每两个药箱里有一种相同的药，而每种药恰好在两个药箱中，问共有多少种

药品？

4．一棵树T 中，有3个2度结点，一个3度结点，其余结点都是树叶。

（1）T 中有几个结点；

（2）画出具有上述度数的所有非同构的无向图。

离散数学试卷（25）

169

五、证明题：（35分）

1．符号化下列各题，并说明结论是否有效（用推理规则）。

凡15的倍数都是3的倍数，凡15的倍数都是5的倍数，所以有些5的倍数是3的倍数。 2．用推理规则证明：

C A F E F

D

E B D C B A →∧?∨?∧∨?→∧→,)(,)()(,)()(├ A

3．设函数B A f →：，C B g →：，若f g 是满射的，则g 是满射的。 4．当且仅当G 的一条边e 不包含在G 的闭迹中时，e 才是G 的割边。

5．设>∧∨<,,S 是一个分配格，S a ∈，令a x x f ∨=)(，对任意S a ∈，证明：f 是

>∧∨<,,S 到自身的格同态映射。

一、填空题

1．对于A ，B 中原子变元n P P P ,,,21 任意一组真值指派，A 和B 的真值相同。 2．110100,

M M M Q P ∧∧?∧ 。

3．集A 关于E 的补集E – A ；A ；Φ；E 。 4．54354321,,,,S S S S S S S S ，，；。 5．ΦΦ；；；S S 。 6．S G -≤；的连通分支数。

二、单项选择题

三、判断改正题

1．× 可能B A B A ∈?且，如}2}1{1{,

}{，，==B a A 。

离散数学试卷（25）

170 2．× 21R R ，是对称的，则21R R 不一定是对称的。

3．× 阶数大于1的群不可能有零元。

4．√。 5．√ 。

6．× 可以有偶数个结点、奇数条边的欧拉图。如图

7．× 连通图，若每条边都是割边，则G 必是树。

8．× ：P ?每一个自然数不都是偶数。

9．× x ?的辖域为)()(x Q x P →。

10．× ),()(y x yQ x xP ?→?的前束范式为)),()((y u Q x P y x →??。

四、简答题

1．解：原式

011

001101111000001)

()()()()()()()(m m m m m m R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P ∨∨∨∨∨?∧∧?∨∧?∧?∨∧?∧∨∧∧∨

?∧?∧?∨∧?∧??∨?∧??∨∨?? ∴ 使其成真赋值为：

??

???100R Q P ，

?????000R Q P ， ?????111R Q P ， ?????101R Q P ， ?????100R Q P ，??

???110R Q P 。 2．解： ??????

? ??=1100110100100101R M R 的关系图为 R 是自反、对称的。

3．解：用n 个结点表示n 个药箱，当两种药箱放一种相同药时，则对应的两点连一条边，则得

到一个无向完全图，因而所求药品数即为该图边数=)1(2

1-n n 。 4．解：（1）设该树树叶数为t ，则树T 的结点数为t ++13，又边数 = 结点数 － 1， ∑=倍边数2)deg(i

v ，∴ )113(213123-++=?+?+?t t

离散数学试卷（25）

171 即t t 269+=+ ，∵ 3=t ，∴ T 中7个结点。

（2）具有3个两度结点，一个3度结点，3片树叶的树（非同构的）共有以下三种：

五、证明题

1．解：设个体域为整数集，

的倍数是：y x y x D ),(。则命题符号化为： ))3()15((，，x D x D x →?，))5()15((，，x D x D x →?，），（15x xD ?

├ ))3()5((，，

x D x D x ∧? 证明：（1） ），（15x xD ? P

（2） ），（15c D ES （1）

（3） ))3()15((，，

x D x D x →? P （4）)3()15(，，

c D c D → US （3） （5）)3,(c D T （2）（4）I

（6）))5()15((，，

x D x D x →? P （7）)5()15(，，

c D c D → US （6） （8）)5,(c D T （2）（7）I

（9）)3,()5,(c D c D ∧ T （5）（8）I

（10）))3,()5,((x D x D x ∧? EG （9）

∴结论有效。

2．证明：（1）A P （附加前提）

（2）C A → P

（3）C T （1）（2）I

（4）)()(D C B A →∧→

P

离散数学试卷（25）

172 （5）D C → T （4）I

（6）D T （3）（5）I

（7）)()(F D E B ∨?∧∨? P

（8）)()(F D E B →∧→ T （7）E

（9）F D → T （8）I

（10）F T （6）（9）I

（11）B A → T （4）I

（12）B T （1）（11）I

（13）E B → T （8）I

（14）E T （12）（13）I

（15）F E ∧ T （10）（14）I

（16）)(F E ∧? P

（17）)()(F E F E ∧?∧∧ T （15）（16）I

∴结论有效。

3．证明：C A f g →：

，C c ∈?，∵f g 是满射，∴A a ∈?，使 c a f g a f g ==))(()( ，令 B a f b ∈=)(，则 c b g =)(，

∴C B g →：是满射。

4．证明：必要性：设e 为割边，若e 包含在G 的一个闭迹中，则从G 中删去e 仍连通，此与e 是

割边矛盾。

充分性：设),(v u e =，不包含G 的任一闭迹中。假设e 不为割边，则e G -仍连通，v

u ,间存在一条基本回路C ，于是e C +则为一条闭迹与已知矛盾，∴e 为割边。

5．证明： )()

()()()()(,,可结合∨∨=∨∨∨=∨∨=∨∈?y x f a y a x a y x y x f S y x ， )()()()()()()(分配律y x f a y a x a y x y x f ∧=∨∧∨=∨∧=∧，

离散数学试卷（25）

173 ∴ f 是>∧∨<，，

S 到自身的格同态映射。

本文来源：https://www.bwwdw.com/article/v1zq.html