离散数学试卷及答案(25)
一、填空题：（每空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))，下列各式中哪个是错误的（ ）。 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 。 三、判断改正题：（每小题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）画出具有上述度数的所有非同构的无向图。 五、证明题：（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 。 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 即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 （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 ∧=∨∧∨=∨∧=∧， ∴ f 是>∧∨<，， S 到自身的格同态映射。