试卷二十四试题与答案一、填空题：（每空1分，本大题共15分）1．设}4,}3{,,2{a A =，}1,4,3,}{{a B =，请在下列每对集合中填入适当的符号：⊆∈,。
（1）}{a B , (2) }}3{,4,{a A 。
2．设}1,0{=A ，N 为自然数集，⎩⎨⎧=是偶数。
，是奇数，，x x x f 10)(若A A f →：，则f 是 射的，若A N f →：，则f 是 射的。
3．设图G = < V ，E >中有7个结点，各结点的次数分别为2，4，4，6，5，5，2，则G 中有 条边，根据 。
4．两个重言式的析取是 ，一个重言式和一个矛盾式的合取是 。
5．设个体域为自然数集，命题“不存在最大自然数”符号化为 。
6．设S 为非空有限集，代数系统>⋃<,2S 中幺元为 ，零元为 。
7．设P 、Q 为两个命题，其De-Morden 律可表示为 。
8．当8=G 时，群>*<,G 只能有 阶非平凡子群，不能有阶子群，平凡子群为 。
二、单项选择题：（每小题1分，本大题共15分）1．设}16{2<=x x x A 是整数且，下面哪个命题为假（ ）。
A 、A ⊆}4,2,1,0{；B 、A ⊆---}1,2,3{；C 、A ⊆Φ；D 、A x x x ⊆<}4{是整数且。
2．设}}{,{,ΦΦ=Φ=B A ，则B －A 是（ ）。
A 、}}{{Φ；B 、}{Φ；C 、}}{,{ΦΦ；D 、Φ。
3．下图描述的偏序集中，子集},,{f e b 的上界为 （ ）。
A 、c b ,；B 、b a ,；C 、b ；D 、c b a ,,。
4．设f 和g 都是X 上的双射函数，则1)(-g f ο为（ ）。
A 、11--g f ο；B 、1)(-f g ο；C 、11--f g ο；D 、1-f g ο。
5．下面集合（ ）关于减法运算是封闭的。
A 、N ；B 、；C 、}12{I x x ∈+； D 、}{是质数x x 。
6．具有如下定义的代数系统>*<,G ，（ ）不构成群。
A 、}10,1{=G ，*是模11乘 ；B 、}9,5,4,3,1{=G ，*是模11乘 ；C 、Q G =（有理数集），*是普通加法 ；D 、Q G =（有理数集），*是普通乘法。
7．设},32{I n m G n m ∈⨯=，*为普通乘法。
则代数系统>*<,G 的幺元为（ ）。
A 、不存在 ；B 、0032⨯=e ；C 、32⨯=e ；D 、1132--⨯=e 。
8．下面集合（ ）关于整除关系构成格。
A 、{2，3，6，12，24，36} ；B 、{1，2，3，4，6，8，12} ；C 、{1，2，3，5，6，15，30} ；D 、{3，6，9，12}。
9．设},,,,,{f e d c b a V =，},,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ，则有向图>=<E V G ,是（ ）。
A 、强连通的 ；B 、单侧连通的 ；C 、弱连通的 ；D 、不连通的。
10．下面那一个图可一笔画出（ ）。
11．在任何图中必定有偶数个（ ）。
} 2 { I x xA 、度数为偶数的结点 ；B 、入度为奇数的结点 ；C 、度数为奇数的结点 ；D 、出度为奇数的结点 。
12．含有3个命题变元的具有不同真值的命题公式的个数为（ ）。
A 、32；B 、23；C 、322；D 、232。
13．下列集合中哪个是最小联结词集（ ）。
A 、},{→⌝；B 、},{↔⌝；C 、},{↔→；D 、},,{∨∧⌝。
14．下面哪个命题公式是重言式（ ）。
A 、)()(R Q Q P →∧→；B 、P Q P →∧)(；C 、)()(Q P Q P ⌝∧⌝∧∨⌝；D 、P Q P ∧∨⌝)(。
15．在谓词演算中，下列各式哪个是正确的（ ）。
A 、),(),(y x xA y y x yA x ∃∃⇔∃∃；B 、),(),(y x xA y y x yA x ∀∀⇔∃∃；C 、),(),(y x xA y y x yA x ∃∀⇐∀∃；D 、)()(x xA a A ∀⇒。
三、判断改正题：（每小题2分，本大题共20分） 1．设}2,1{=A ，}{a B =，则 B A BA ⋃=⋃222。
（其中A 2为（A ）） ( )2．设}1,0{=A ，}2,1{=B ，则 }2,0,1,1,0,1,2,1,0,1,1,0{2><><><><=⨯B A 。
（ ）3．集合A 上的恒等关系是一个双射函数。
（ ） 4．设Q 为有理数集，Q 上运算 * 定义为),max(b a b a =*，则>*<，Q 是半群。
（ ）5．阶数为偶数的有限群中，周期为2的元素的个数一定为偶数。
（ ）6．在完全二元树中，若有t 片叶子，则边的总数12-=t e 。
（ ）7．能一笔画出的图不一定是欧拉图。
（ ）8．设P ，Q 是两个命题，当且仅当P ，Q 的真值均为T 时，Q P ↔的值为T 。
（ ）9．命题公式Q Q P P →→∧))((是重言式。
（ ）10．设，是研究生：x x P )(，曾读过大学：x x Q )( 命题“所有的研究生都读过大学”符号化为：))()((x Q x P x ∧∀。
（ ）四、简答题：（25分）1．设},,{c b a A =，A 上的关系 },,,,,,,{><><><><=b c c b b a a a ρ，求出)()(,)(ρρρt s r 和。
2．集合}36,24,12,6,3,2{=A 上的偏序关系为整除关系。
设}12,6{=B ，}6,3,2{=C ，试画出的哈斯图，并求A ，B ，C 的最大元素、极大元素、下界、上确界。
3．图给出的赋权图表示五个城市54321v v v v v ，，，，及对应两城镇间公路的长度。
试给出一个最优化的设计方案使得各城市间能够有公路连通。
4．已知}654321{，，，，，=G ，7⨯为模7乘法。
试说明>⨯<7，G 是否构成群是否为循环群若是，生成元是什么5．给定命题公式)())((W S R Q P ∨⌝∨∧⌝∧，试给出相应的二元树。
五、证明题：（25分）1．如果集合A 上的关系R 和S 是反自反的、对称的和传递的，证明：S R ⋂是A 上的等价关系。
2．用推理规则证明)()(a G a P ∧⌝是))()((,)(,))()((,)))()(()((x G x S x a S a R a Q x R x Q x P x ↔∀∧⌝∧→∀的有效结论。
3．若有n 个人，每个人都恰有三个朋友，则n 必为偶数。
4．设G 是（11，m ）图，证明G 或其补图G 是非平面图。
答案一、填空题1．（1）∈， （2）⊆。
2．双射 ， 满射。
3．14 ，E v V v i i 2)deg(=∑∈。
4．重言式 ，矛盾式 。
5．)(x y y x >∃∀， 6．Φ，S 。
7．Q P Q P Q P Q P ⌝∧⌝⇔∨⌝⌝∨⌝⇔∧⌝)()(，；P Q P P P Q P P ⇔∧∨⇔∨∧)(,)( 。
8．2，4； 3，5，6，7；>*<>*<,,},{G e 。
二、单项选择题 题号1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 A C B C B D B C C A C C A B A1．× B A B A 222⋃⊇⋃ 。
2．× 3．√ 。
4．√ 。
5．× 阶数为偶数的有限群中周期为2 的元素个数一定为奇数。
6．× 完全二叉树中，边数)1(2-=t e 。
7．√ 。
8．× 当且仅当P ，Q 的真值相同时，Q P ↔的真值为T 。
9．√ 。
10．× ))()((x Q x P x →∀。
四、简答案题1．解},,,,,,,,,,,{)(><><><><><><=c c b b b c c b b a a a r ρ，},,,,,,,,,{)(><><><><><=a b b c c b b a a a s ρ，},,,,,,,,,{2><><><><><==c c b b c a b a a a ρρρο，},,,,,,,,,,,{23><><><><><><==b c c b b a c a b a a a ρρρο，},,,,,,,,,,,,,{)(2><><><><><><><=⋃=∴b c c b c c b b c a b a a a t ρρρ。
2．解：的哈斯图为集合 最大元 极大元 下界 上确界A 无 24，36 无 无 B12 12 6，2，3 12 C 6 6 无 6由破圈法或避圈法得最小生成树为：其权数为1+1+3+4 = 9 。
4．解：>⨯<7，G 既构成群，又构成循环群，其生成元为3，5。
因为：7⨯的运算表为：1 2 3 4 5 6 11 2 3 4 5 6 22 4 6 13 5 33 6 2 5 14 44 15 26 3 55 3 16 4 2 6 6 5 4 3 2 11）由运算表知，7⨯封闭；2）7⨯可结合（可自证明）3）1为幺元；4）111=-，421=-，531=-，241=-，351=-，661=-，综上所述，>⨯<7，G 构成群。
由331=，232=，633=，434=，535=，136=。
所以，3为其生成元，3的逆元5也为其生成元。
故>⨯<7，G 为循环群。
5．解：命题公式对应的二元树见右图。
五、证明题1．证明：（1）,,,,,,S a a R a a S R A a >∈<>∈<∈∀∴自反，Θ S R S R a a ⋂⋂>∈<∴∴,,自反。
（2）A b a ∈∀,，若S R b a ⋂>∈<,，则,,,,S b a R b a >∈<>∈<由R ，S 对称， 所以，,,,,S a b R a b >∈<>∈<S R a b ⋂>∈<∴,，所以 S R ⋂对称。