离散数学(本)阶段练习一

最新国家开放大学电大《离散数学》形考任务1试题及答案最新国家开放大学电大《离散数学》形考任务1试题及答.形考任务1（集合论部分概念及性质）单项选择.题目.若集合A＝.a, {a}, {1, 2}}, 则下列表述正确的是（）.选择一项:A.{a, {a}}.B..C.{1, 2..D.{a..题目.设函数f: N→N, f(n)=n+1, 下列表述正确的是.）.选择一项: A.f是满射.B.f存在反函.C.f是单射函.D.f是双射.题目.设集合A={1, 2, 3, 4, 5}, 偏序关系是A上的整除关系, 则偏序集<A, >上的元素5是集合A的.）.选择一项:A.极小.B.极大.C.最大.D.最小.题目.设A={a, b}, B={1, 2}, C={4, 5}, 从A到B的函数f={<a,1>.<b, 2>}, 从B到C的函数g={<1, 5>.<2, 4>}, 则下列表述正确的是.）.选择一项:A.g..={<a, 5>.<b, 4>.B.g..={<5, .>.<4, .>.C.f°.={<5, .>.<4, .>.D.f°.={<a, 5>.<b, 4>.题目.集合A={1.2.3.4}上的关系R={<x, y>|x=y且x.yA}, 则R的性质为.）.选择一项:A.传递.B.不是对称.C.反自.D.不是自反.题目.设集合..{1..}, 则P(A...).选择一项:A.{{1}.{a}.{1..}.B.{{1}.{a}.C.{,{1}.{a}.D.{,{1}.{a}.{1..}.题目.若集合A={1, 2}, B={1, 2, {1, 2}},则下列表述正确的是.).选择一项:A.AB, 且A.B.AB, 且A.C.BA, 且A.D.AB, 且A.题目.设集合A={1.2.3}, B={3.4.5}, C={5.6.7},则A∪B–.=.).选择一项:A.{1.2.3.4.B.{4.5.6.7.C.{2.3.4.5.D.{1.2.3.5.题目.设集合..{1.2.3.4.5}上的偏序关系的哈斯图如右图所示, 若A的子集..{3.4.5}, 则元素3为B的.）.选择一项:A.最小上.B.下.C.最大下.D.最小.题目1.如果R1和R2是A上的自反关系, 则R1∪R2, R1∩R2, R1-R2中自反关系有.）个.选择一项:A..B..C..D..以下资料为赠送资料:《滴水之中见精神》主题班会教案活动目的: 教育学生懂得“水”这一宝贵资源对于我们来说是极为珍贵的, 每个人都要保护它, 做到节约每一滴水, 造福子孙万代。

离散数学1-6章练习题及答案离散数学练习题第⼀章⼀?填空1?公式(p q) ( p q)的成真赋值为01; 102?设p, r为真命题，q, s为假命题，则复合命题(p q) ( r s)的真值为03?公式(p q)与(p q) ( p q)共同的成真赋值为01 ；104?设A为任意的公式，B为重⾔式，则A B的类型为重⾔式5. 设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。

⼆.将下列命题符合化1. ■ 7不是⽆理数是不对的。

解：(p)，其中p：. 7是⽆理数；或p,其中p: . 7是⽆理数。

2?⼩刘既不怕吃苦，⼜很爱钻研。

解：p q,其中p:⼩刘怕吃苦，q :⼩刘很爱钻研3?只有不怕困难，才能战胜困难。

解：q p，其中p:怕困难，q:战胜困难或p q，其中p:怕困难，q:战胜困难4?只要别⼈有困难，⽼王就帮助别⼈，除⾮困难解决了。

解：r (p q)，其中p:别⼈有困难，q:⽼王帮助别⼈，r:困难解决了或：(r p) q，其中p：别⼈有困难，q:⽼王帮助别⼈，r:困难解决了5?整数n是整数当且仅当n能被2整除。

解：p q，其中p:整数n是偶数，q:整数n能被2整除三、求复合命题的真值P：2能整除5, q：旧⾦⼭是美国的⾸都，r：在中国⼀年分四季1. ((p q) r) (r (p q))2?((q p) (r p)) (( p q) r解：p, q为假命题，r为真命题1. (( p q) r) (r (p q))的真值为02. (( q p) (r p)) (( p q) r 的真值为1四、判断推理是否正确设y 2x为实数，推理如下：若y在x=0可导，则y在x=0连续。

y在x=0连续，所以y在x=0可导。

解：y 2x，x为实数，令p: y在x =0可导，q: y在x=0连续。

P为假命题，q为真命题，推理符号化为：(p q) q p，由p, q得真值可知，推理的真值为0,所以推理不正确。

离散数学-习题集《离散数学》习题集第⼀部分判断题⼀、第⼀章—集合1、（）已知集合A的元素个数为10，则集合A的幂集的基=102。

2、（）已知两个集合A、B，若A中的元素都是B中的元素，则记为A∈B。

2、（）已知集合A的元素个数为n，则集合A的幂集P（A）的元素个数为n2。

3、( ) 已知两个集合A={Ф，{Ф}}，B={Ф}，则A∩B={Ф}。

4、（）已知两个集合A={Ф，{Ф}}，B={Ф}，则A∩B=Ф。

5、（）已知两个集合A、B，若A中的元素都是B中的元素，则记为A∈B。

6、（）已知集合A的元素个数为n，则集合A的幂集P（A）的元素个数为n2。

7、（）已知集合A的元素个数为n，则A×A的幂集的元素个数为n2。

8、（）已知两个集合A、B，则A-B是由属于B但不属于A的元素构成的集合。

⼆、第⼆章—⼆元关系1、（）若R是A上的⼆元关系，I A是A上的恒等关系，则当且仅当I A∈R时，R是A上的⾃反关系。

2、（√）若R是集合A上的⼆元关系，且当（a，b）∈R且（a，c）∈R时，就有（b，c）∈R，则R是A 上的可传递关系。

3、（）设A是集合，A1、A2、．．．A n都是A的⾮空⼦集，令S={A1，A2，．．．,A n}，则如果S是集合A的⼀个划分，那么S⼀定是集合A的⼀个完全覆盖；反之亦然。

5、（）R是⾮空集合A上的等价⼆元关系，则A关于R的商集A/R是集合A的⼀个划分，但不是A的⼀个完全覆盖。

6、（）已知集合A有4元素，易知集合A共有24个互不相同的⼦集合，所以在集合A上⼀共可定义24个互不相同的⼆元关系。

7、（）若R1和R2都是集合A上的可传递⼆元关系，则R1∪R2也是A上的传递关系。

8、（）设R是有限的⾮空集合A上的偏序关系，则A必有极⼤（⼩）元和最⼤（⼩）元。

9、（）若R1和R2都是集合A上的相容关系，则R1∩R2也是A上的相容关系。

10、（）若R1和R2都是集合A的可传递⼆元关系，则R1∩R2也是A上的传递关系。

5、下列命题公式为重言式的是（ D ），为矛盾式的是（ C ）
A、(P→Q)⋀Q⋀R
B、(P→P)→Q
C、(Q⋁R)⋀R
D、((P→Q)⋀(Q→R))→(P→R)
6、命题公式 (P→Q) 的主合取范式中含有（ D ）个极大项， 主析取范式中含有（ B ）个极小项 A、0 B、1 C、2 D、3
7、下列式子不正确的是（ D ） A、∃xA(x) ⇔ ∀xA(x) B、∃x(A→B(x)) ⇔ A→∃xB(x) C、∀xA(x) ⇔ ∃xA(x) D、∀x(A(x)→B) ⇔ ∀xA(x)→B
以下方案任选一：①A不去,B不去,C去；②A不去,B去,C不去； ③A去,B不去,C去
9、证明下列谓词公式为永真式
(xF( x) yG( y)) (yG( y) xF( x))
证明：题中的谓词公式为 (P Q) (Q P) 的代换实例
(P Q) (Q P) (P Q) (Q P) (P Q) (P Q) 1 (A A 1)
(P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) m001 m000 m011 m111 m0 m1 m3 m（7 主析取范式） M2 M4 M5 M（6 主合取范式） (P Q R) (P Q R) (P Q R) (P Q R)
命题“并不是所有汽车都比火车跑得慢”可符号化为（ C ）
命题“说汽车都比火车快是不对的”可符号化为（ C ） A、∃x(F(x)∧∀y(G(y)→H(x,y))) B、∃x∃y(F(x)∧G(y)→H(x,y)) C、∀x∀y(F(x)∧G(y)→H(x,y)) D、∀x(F(x)∧∃y(G(y)→H(x,y)))

离散数学练习题(含答案)离散数学试题第一部分选择题1.下列命题变元p，q的小项是(C)。

A。

p∧┐p∧qB。

┐p∨qC。

┐p∧qD。

┐p∨p∨q2.命题“虽然今天下雪了，但是路不滑”可符号化为(D)。

A。

p→┐qB。

p∨┐qC。

p∧qD。

p∧┐q3.只有语句“1+1=10”是命题(A)。

A。

1+1=10B。

x+y=10___<0D。

x mod 3=24.下列等值式不正确的是(C)。

A。

┐(x)A(x)┐AB。

(x)(B→A(x))B→(x)A(x)C。

(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)D。

(x)(y)(A(x)→B(y))(x)A(x)→(y)B(y) 5.量词x的辖域是“Q(x,z)→(x)(y)R(x,y,z)”(C)。

A。

(x)Q(x,z)→(x)(y)R(x,y,z))B。

Q(x,z)→(y)R(x,y,z)C。

Q(x,z)→(x)(y)R(x,y,z)D。

Q(x,z)6.设A={a,b,c,d}，A上的等价关系R={。

}∪IA则对应于R的A的划分是(D)。

A。

{{a},{b,c},{d}}B。

{{a,b},{c},{d}}C。

{{a},{b},{c},{d}}D。

{{a,b},{c,d}}7.设A={Ø}，B=P(P(A))，以下正确的式子是(A)。

A。

{Ø,{Ø}}∈BB。

{{Ø,Ø}}∈BC。

{{Ø},{{Ø}}}∈BD。

{Ø,{{Ø}}}∈B8.集合相对补运算中，不正确的等式是(A)。

A。

(X-Y)-Z=X-(Y∩Z)B。

(X-Y)-Z=(X-Z)-YC。

(X-Y)-Z=(X-Z)-(Y-Z)D。

(X-Y)-Z=X-(Y∪Z)9.在自然数集N上，不可结合的定义的运算是(D)。

A。

a*b=min(a,b)B。

a*b=a+bC。

a*b=GCD(a,b) (a,b的最大公约数)D。

离散数学第一部分测试题 一、 填空题1．当p,q,r 分别取1，0，1时，(p→q) (p→r)的真值为 假，或02．设P ：他富有，Q ：他幸福，“他既不富有也不幸福” 的符号化为 ┐ P ∧┐ Q3．“所有的人都长着黑头发”用谓词表达式符号化为 M(x):x 为人，F(x): x 长着黑头发， x(M(x)→F(x))4．如果6大于4，则4大于5用谓词表达式符号化为 G(x,y): x ﹥y ,G(6,4) →G(4,5)二、 选择题1.2x+3<4（ C ）A.是命题也是复合命题B.是命题但不是复合命题C.不是命题D.以上都不对2. 下列语句是命题的有（ D ）A. 什么时候开会呀？B. 请快开门！C. x+y>10。

D. 苹果树和梨树都是落叶乔木。

3.设p 表示命题“天下大雨”，q 表示命题“他乘公共汽车上班”，r 表示命题“他骑自行车上班”。

则命题“如果天不下大雨，他乘公共汽车上班或者骑自行车上班。

”符号化为（ B ）A ．(⌝p ∧q) →rB ．⌝p →(q ∨r )C ．⌝p ∧(q →r )D ．p →(q ∧r )三、 计算题1．求(p ∨q) →r 的主析取范式解 本公式含有三个命题变项，所以极小项均含有三个文字。

75310)()()()()()()()()()()())()(()()()()()(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 r q p r q p r q p r q q p p r r q p rq p rq p rq p ∨∨∨∨⇔∧∧∨∧⌝∧∨∧∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝⇔∧∧∨∧⌝∧∨∧∧⌝∨∧⌝∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝⇔∧∨⌝∧∨⌝∨∨⌝∧⌝∧⌝⇔∨⌝∧⌝⇔∨∨⌝⇔→∨2．求公式的主合取范式：()()R Q Q P ∧→∨证明：()()()()P Q Q R P Q Q R ∨→∧⇔⌝∨∨∧()()P Q Q R ⇔⌝∧⌝∨∧()()()()()P Q Q P P Q R ⇔⌝∧⌝∨∧⌝∨∧∧()()()()()()R Q P P R R Q P ∧∧∨⌝∨∨⌝∧⌝∧⌝⇔()()()()R Q P R Q P R Q P R Q P ∧∧∨∧∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝⇔四、 证明题1.用等演算法证明下面等值式。

4.求与公式((x1x2)x3)x4等价的主析取范式 或主合取范式。
((x1x2)x3)x4 (( x1 x2) x3) x4 ( ( x1 x2) x3) x4 ( x1 x2 x4) （ x3 x4） (x1 x2 x3 x4) (x1 x2 x3 x4) （x1 x2 x3 x4） (x1 x2 x3 x4) (x1 x2 x3 x4) (x1 x2 x3 x4)
P P T(1)(2);I P T(3)(4);I
T(9)(10);I T(11);E
6. 将前提和结论符号化，并证明相应的结论是有效的。
前提：若我学习，则考试不会失败； 若我不踢球，那我将学习； 我考试失败了。
结论：我踢了球。
设：P: 我学习 Q:我考试失败 R:我踢球 则：PQ , RP, Q R
(1) PQ (2) Q (3) P (4) RP (5) R
P T(1);E P T(2)(3);I T(4);E P T(5)(6);I T(7);E
(PQ)R,RS,S PQ
(1) S (2) RS (3) R (4) (PQ)R (5) (PQ) (6) PQ
P P T(1)(2);I P T(3)(4);I T(5);E
P(QR),QS,(LM) S,Q P QL
(x1 x2 x3 x4) (x1 x2 x3 x4) （x1 x2 x3 x4） (x1 x2 x3 x4) (x1 x2 x3 x4)
5. 证明结论是前提的有效结论 (课后练习P46 T27)
PQ,PR,QS SR
(1) PQ (2) PQ (3) QS (4) PS (5) S P (6) PR (7) S R (8) SR
第一章离散数学练习参考答案离散数学第一章离散数学课后习题答案离散数学答案离散数学左孝凌答案离散数学及其应用答案离散数学第五版答案离散数学答案屈婉玲离散数学课后答案离散数学贾振华答案

1-5 题：× × × ×√6-10 题：× ×√√√11-15题：× ×√ ×√16-17题：√ ×二、单项选择题1 A C2 C3 C 4. B 5 A6 B7 B8 C9 B 10 B11 D 12 A 13 C 14 C三、填空题1 ┐Q→P 或┐P→Q，Q→P2 A B=｛{a,b}, {a},{b},{c}｝，A B=｛｛c｝｝，A B-=｛{a,b}｝，A B⊕=｛{a,b},{a},{b}｝。

3．{}ΦΦ=Φ，{,{}}ΦΦ-Φ={Φ,{ Φ}}，ΦΦ={Φ}。

{,{}}{}ΦΦ-Φ={{Φ}}，{}4．A={1,2,3,……,12}，R是A上的整除关系，子集B={2,4,6}。

则B的最大元是：无，最小元是：2，极大元是：4，6，极小元是：2，上界是：12，下界是：2，上确界是：12，下确界是：2。

5. g g g6 R, T7. 略8．极大元：{a,b}, {b,c}，最大元：无，上界：{a,b,c}，下确界：Φ。

( )1．设A ，B ，C 为任意的命题公式，若A C B C ∨⇔∨,则A B ⇔。

( )2．公式P Q ∧是合取范式，不是析取范式。

( )3．公式()()P Q P Q ⌝∨∧→与公式()P Q R →∧等价。

( )4．()(()())()()()()x A x B x x A x x B x ∀∨⇔∀∨∀。

( )5．谓词公式()()((,)(,))x y P x y Q y z ∀∀∨中，x,y 是约束变元，z 是自由变元。

( )6．对谓词公式()(()(,))(,)x P y Q x y R x y ∀→∧中的自由变元进行代入后得到公式()(()(,))(,)x P z Q x z R x y ∀→∧。

( )7．对谓词公式()(()(,))(,)x P x Q x y R x y ∀→∧中的约束变元进行换名后得到公式()(()(,))(,)y P y Q y y R x y ∀→∧。

离散数学本试题及答案一、单项选择题（每题2分，共20分）1. 在集合{1,2,3,4}中，元素3的补集是（）。

A. {1,2,4}B. {1,2,3,4}C. {1,2,3}D. {2,4}答案：A2. 命题“若x>0，则x>1”的逆否命题是（）。

A. 若x≤1，则x≤0B. 若x≤1，则x<0C. 若x>1，则x>0D. 若x≤0，则x≤1答案：A3. 函数f(x)=x^2在区间[0,1]上是（）。

A. 增函数B. 减函数C. 常数函数D. 非单调函数答案：A4. 逻辑运算符“与”的符号是（）。

A. ∧B. ∨C. →D. ¬答案：A5. 集合A={1,2,3}，B={2,3,4}，则A∩B=（）。

A. {1,2,3}B. {2,3}C. {1,2,4}D. {1,3,4}答案：B6. 命题“若x>0，则x>1”的否定是（）。

A. 若x≤0，则x≤1B. 若x≤0，则x>1C. 若x>0，则x≤1D. 若x≤0，则x≤1答案：C7. 函数f(x)=x^2在区间[-1,1]上是（）。

A. 增函数B. 减函数C. 常数函数D. 非单调函数答案：D8. 逻辑运算符“或”的符号是（）。

A. ∧B. ∨C. →D. ¬答案：B9. 集合A={1,2,3}，B={2,3,4}，则A∪B=（）。

A. {1,2,3}B. {2,3}C. {1,2,4}D. {1,2,3,4}答案：D10. 命题“若x>0，则x>1”的逆命题是（）。

A. 若x≤1，则x≤0B. 若x>1，则x>0C. 若x>1，则x>0D. 若x≤0，则x≤1答案：B二、填空题（每题3分，共30分）11. 集合{1,2,3}的子集个数为______。

答案：812. 命题“若x>0，则x>1”的逆命题是“若x>1，则x>0”，其真假性为______。

可编辑修改精选全文完整版离散数学习题答案习题一：P121.判断下列句子哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？(1)中国有四大发明。

(2)5是无理数。

(3)3是素数或4是素数。

(4)x2+3<5，其中x是任意实数。

(5)你去图书馆吗？(6)2与3都是偶数。

(7)刘红与魏新是同学。

(8)这朵玫瑰花多美丽呀！(9)吸烟请到吸烟室去！(10)圆的面积等于半径的平方乘π。

(11)只有6是偶数，3才能是2的倍数。

(12)8是偶数的充分必要条件是8能被3整除。

(13)2025年元旦下大雪。

1、2、3、6、7、10、11、12、13是命题。

在上面的命题中，1、2、7、10、13是简单命题；1、2、10是真命题；7的真值现在还不知道。

2.将上题中是简单命题的命题符号化。

(1)p：中国有四大发明。

(2)q：5是无理数。

(7)r：刘红与魏新是同学。

(10)s：圆的面积等于半径的平方乘π。

(1)t：2025年元旦下大雪。

3.写出下列各命题的否定式，并将原命题及其否定式都符号化，最后指出各否定式的真值。

“5是有理数”的否定式是“5不是有理数”。

解：原命题可符号化为：p：5是有理数。

其否定式为：非p。

非p的真值为1。

4.将下列命题符号化，并指出真值。

(1)2与5都是素数。

(2)不但π是无理数，而且自然对数的底e也是无理数。

(3)虽然2是最小的素数，但2不是最小的自然数。

(4)3是偶素数。

(5)4既不是素数，也不是偶数。

a：2是素数。

b：5是素数。

c：π是无理数。

d：e是无理数。

f：2是最小的素数。

g：2是最小的自然数。

h：3是偶数。

i：3是素数。

j：4是素数。

k：4是偶数。

解：（1）到（5）的符号化形式分别为a∧b，c∧d，f∧非g，h∧i，非j∧非k。

这五个复合命题的真值分别为1，1，1，0，0。

5.将下列命题符号化，并指出真值。

a：2是偶数。

b：3是偶数。

c：4是偶数。

国家开放大学最新《离散数学（本）》形考任务（1-4 ）试题及答案解析形考任务1（正确答案解析附题冃之后）单项选择题题冃1正确获得5.00分中的5.00分未标记标记题目题干设A={1, 2, 3, 4, 5, 6, 7, 8}, R是A上的整除关系，B={2, 4, 6},则集合B的最大元、最小元、上界、下界依次为（）■选择一项：A.无、2、无、2B.8、2、8、2C.8、1、6、1D.6、2、6、2反馈你的回答正确正确答案是：无、2、无、2题目2正确获得5.00分中的5.00分未标记标记题目题干设集合A={1,2,3,4}上的二元关系R={<l z 1>, <2, 2>, <2, 3>, <4, 4>}. S={<1, 1>, <2,2>, <2, 3>, <3,2>, <4,4>},则S 是日的（）闭包.选择一项：A.自反和传递B.传递C.自反D.对称反馈你的回答正确正确答案是：对称题目3正确获得5.00分中的5.00分未标记标记题冃题干若集合A的元素个数为10,则其暴集的元素个数为( ).选择一项：A.1024B. 1C.100D.10反馈你的回答正确正确答案是：1024题目4正确获得5.00分中的5.00分未标记标记题目题干设集合A = {1, 2, 3, 4, 5}上的偏序关系的哈斯图如图所示，若A的子集B = {3, 4, 5},则元素3为B的( )・选择一项：A.最大下界B.下界C.最小元D.最小上界反馈你的回答正确正确答案是：最小上界题目5正确获得5.00分中的5.00分未标记标记题冃题干设集合A=(1, 2, 3), B={3, 4, 5}, C={5, 6, 7), WJ AUB~C=( ).选择一项：A.(4, 5, 6, 7)B.{1, 2, 3, 5)C.(2, 3, 4, 5)D.{1, 2, 3, 4}反馈你的回答正确正确答案是：{1,2, 3, 4}题目6正确获得5.00分中的5.00分未标记标记题目题干设集合A={1, 2, 3, 4, 5},偏序关系是A上的整除关系，则偏序夷<A, > 上的元素5是集合A的( )・选择一项jA.极大元B.最大元C.最小元D.极小元反馈你的回答正确正确答案是：极大元题目7正确获得5.00分中的5.00分未标记标记题冃题干设集合A ={1,2, 3}上的函数分别为：f = {<l,2>, <2,1>, <3,3>},g = {<1, 3>, <2,2>, <3, 2>),h = {<l,3>, <2,1>, <3,1>},则h=( ).选择一项：A.g%B.g°fC.何D.f°g反馈你的回答正确正确答案是：f°g题冃8正确获得5.00分中的5.00分未标记标记题冃题干设集合A={2,4,6,8}, B={1,3,5,7} , A 到 B 的关系R={<x, y>| y = x+l),则R=( )•选择一项：A.{<2, 2>, <3, 3>, <4, 6>}B.(<2,1>, <4, 3>, <6, 5>}C.(<2, 3>, <4, 5>, <6, 7>)D.{<2,1>, <3, 2>, <4, 3>}反馈你的回答正确正确答案是：{<2, 3>, <4, 5>, <6, 7>}题冃9正确获得5.00分中的5.00分未标记标记题目题干集合A=(1, 2, 3, 4}上的关系R={<x, y>|x=y且x, yA},则R的性质为( ).选择一项：A.反自反B.不是对称的C.传递的D.不是自反的反馈你的回答正确正确答案是：传递的题目10正确获得5.00分中的5.00分未标记标记题冃题干集合A=(1, 2, 3, 4, 5, 6, 7, 8}上的关系R={<x, y>|x+y=10 且x, yA},则R 的性质选择一项：A.传递且对称的B.反自反且传递的C.自反的D.对称的反馈你的回答正确正确答案是：对称的未标记标记题冃信息文本判断题题目11正确获得5.00分中的5.00分未标记标记题日题干空集的幕集是空集.（）选择一项：对错反馈正确的答案是“错”。

离散数学练习题（一）一、填空 20% （每小题2分）1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E +正偶数） 则 =⋃B A 。

2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。

3．设P ，Q 的真值为0，R ，S 的真值为1，则)()))(((S R P R Q P ⌝∨→⌝∧→∨⌝的真值= 。

4．公式P R S R P ⌝∨∧∨∧)()(的主合取范式为 。

5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ∀→∃ 在I 下真值为 。

6．设A={1，2，3，4}，A 上关系图为则 R 2 = 。

7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则 R= 。

8．图的补图为 。

9．设A={a ，b ，c ，d} ，A 上二元运算如下：那么代数系统<A ，*>的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。

二、选择 20% （每小题 2分）1、下列是真命题的有（ ） A ． }}{{}{a a ⊆；B ．}}{,{}}{{ΦΦ∈Φ；C ． }},{{ΦΦ∈Φ；D ． }}{{}{Φ∈Φ。

2、下列集合中相等的有（ ）A ．{4，3}Φ⋃；B ．{Φ，3，4}；C ．{4，Φ，3，3}；D ． {3，4}。

3、设A={1，2，3}，则A 上的二元关系有（ ）个。

A ． 23；B ． 32 ；C ． 332⨯； D ． 223⨯。

4、设R ，S 是集合A 上的关系，则下列说法正确的是（ ） A ．若R ，S 是自反的， 则S R 是自反的； B ．若R ，S 是反自反的， 则S R 是反自反的； C ．若R ，S 是对称的， 则S R 是对称的； D ．若R ，S 是传递的， 则S R 是传递的。

5、设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系如下|}||(|)(,|,{t s A p t s t s R =∧∈><=则P （A ）/ R=（ ）A ．A ；B ．P(A) ；C ．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D ．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}}6、设A={Φ，{1}，{1，3}，{1，2，3}}则A 上包含关系“⊆”的哈斯图为（ ）7、下列函数是双射的为（ ）A ．f : I →E , f (x) = 2x ；B ．f : N →N ⨯N, f (n) = <n , n+1> ；C ．f : R →I , f (x) = [x] ；D ．f :I →N, f (x) = | x | 。

离散数学习题一二参考答案----a3039d74-7162-11ec-90d9-7cb59b590d7d离散数学习题一二参考答案离散数学练习1的参考答案第一节集合的基数1.证明两个可数集的并是可数的。

证明：设a，b是两可数集，a={a1,a2,a3,,an,}，b={b1,b2,b3,,bn,}⎧ab→n⎧f:⎧ai2i-1，f是一一对应关系，所以|a∪b|=|n|=ℵ0。

⎧b2jj⎧2．证明有限可数集的并是可数集证明：设A1，A2和a3ak是有限可数集，AI=（Ai1，AI2，ai3，ain，），I=1，2，3，Kk⎧k⎧a=ai→n，f是一一对应关系，所以|a|=|ai|=|n|=ℵ0。

f:⎧i=1i=1⎧aijj（k-1）+i⎧3.证明可数个可数集的并是可数集。

证明：设A1，A2和a3ak为无限可数集，AI=（Ai1，AI2，ai3，ain，），I=1,2,3，∞⎧a=ai→n⎧⎧i=1f:⎧，1⎧aij(i+j-1)(i+j-2)+i⎧2⎧所以f是一对一的对应，所以|a |=|a |=|n |=ℵ. 我∞04.证明整系数多项式所构成的集合是可数集。

证明了具有整系数的n次多项式之和可以写成an={a0xn+a1xn-1++an-1x+an|ai∈z}那么整系数为a=an的多项式集；由于xk的系数ak是整数，那么所有xk的系数的全体所构成的集合是可数集，由习题2“有限个可数集的并是可数集”可得an是可数集，再又习题4“可数个可数集的并是可数集”得出整系数多项式所构成的集合a=an也是可数集。

5.证明不存在等于其真子集的有限集证明：设集合a是有限集，则|a|=n，若b是a的真子集，则|b|≤|a|=n，a-b≠φ，即|a-b|=|a|-|ab|＞0；又a=（a-b）∪b，（a-b）b=φ，所以，，就是|a|＞|b|，即得结论。

6.证明正有理数集是可数的，从而证明有理数集是可数的。

m证明：因为q+={|m,n∈n}，是正分数集，n∞ n+让AI={|n∈ n} ，I=1,2,3,4,m}，AI是可数集，q=AIII=1由可数集性质4“可数个可数集的并仍然是可数集”，所以正有理数集合是可数集。

第1次作业一、单项选择题（本大题共30分，共15小题，每小题2分）1.A.4B.5C.6D.32.在完全m叉树中，若树叶数为t，分枝点数为i，则有（）A.（m-1）i<t-1B.(m-1)i>t-12C.(m-1)i=t-1D.（m-1）i <t -13.命题a）：如果天下雨，我不去。

写出命题a）的逆换式______________A.如果我不去，天下雨。

B.如果我去，天下雨。

C.如果天下雨，我去。

D.如果天不下雨，我去。

4. 设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点, 问该图有多少个顶点（）A.B.C.42D.65. 假设A={a,b,c,d}, 考虑子集S={{a,b},{b,c},{d}} ，则下列选项正确的是( )。

A.S 是A 的覆盖B.S是A的划分C.S既不是划分也不是覆盖D.以上选项都不正确6. 没有不犯错误的人。

M(x): x为人。

F(x): x犯错误。

则命题可表示为( )。

A.(? x)(M(x) —F(x)B.(? x)(M(x) ? F(x)C.(? x) (M(x) ? F(x))D.(? x)(M(x) —F(x)7. 命题逻辑演绎的CP规则为()A.在推演过程中可随便使用前提B.在推演过程中可随便使用前面演绎出的某些公式的逻辑结果C.如果要演绎出的公式为B—C形式，那么将B作为前提，演绎出CD.设？ (A)是含公式A的命题公式，B<=>A则可以用B替换？ (A)中的A8. 设G是有6个结点的完全图，从G中删去()条边，则得到树。

A.6B.9C.159. 设A B两个集合，当（）时A-B=B10A.A=BB.A? BC.B? AD.A=B=?10. 设U={1，2，3，4，5} ，A={2，4} ，B={4，3，5} ，C={2，5，3} ，确定集合（A-C）-B = （）。

A.{1,4}B.{2,3,4,5}C.{4}D.11.下图的最小生成树的权为（）A.40B.44C.48D.5212.对偶式为P T Q表达式是_______________A.P A QB.P J QC.P V QD.i Q13. 下列语句是命题，并且真值为0 的是()A. 雪式白的。

离散数学练习题Chapter 1 集合、映射与运算1. 下列集合运算的结果中与其余三个不同的是（）.（A ）{}ΦΦ（B ）{}{}ΦΦ（C ）{}{}{}Φ-ΦΦ, （D ）{}{}{}{}Φ-ΦΦ, 2. 设A 为⾮空集合,则下列各式中正确的是（）.（A ）)(A P A ? （B ）)(A P A ? （C ）{})(A P A ∈（D ）{})(A P A ? 3. ( )是错误的.（A ）{}{}{}a a ∈（B ）{}{}{}a a a ,∈（C ）{}{}{}a a a ,? （D ）{}{}{}a a ? 4. 设{}{}a a A ,=,下列各式中错误的是（）.（A ）{}()A P a ∈（B ）{}()A P a ? （C ）{}{}()A P a ∈（D ）{}{}()A P a ? 5. 设{})(,A P B A =Φ=,则A B -是（）. （A ）Φ（B ）{}Φ（C ）{}{}Φ（D ）{}{}ΦΦ, 6. 对任⼀集合A ,能成⽴的是（）.（A ）)(A P A ∈（B ）{})(A P A ∈（C ）Φ-∈A A （D ）Φ⊕∈A A 7. 证明a) A C B A C A B -=--)()()( b) )()()(C B C A C B A ---=-- c) ()()()C A B A C B A -=-- 8. 下列等式说明集合A,B 有何关系? a) A B A =b) A B A =c)A B A =-d) A B B A =e) A B B A -=-9. 判断题.（1）设2N ,3N 分别为2,3的倍数集,则{}N N 3,2是N 的划分. （）（2）若{}A B B A -, 是B A 的⼀个划分,则Φ=-B A . （）（3）若Φ==B A B B A ,,则Φ=A . （）（4）若A B B A ?=?,则B A =. （）（5）设B A ,为任意集合,则有()()()B P A P B A P = （）（6）若Φ=-B A ,则B A =.（）10. 求1000~1中能被8,6,5之⼀整除的整数个数.11. 在校运会中,某班有10⼈,12⼈,8⼈分别参加了长跑,短跑和跳远,其中有6⼈三项全参加.已知该班共40⼈,问该班⾄少有多少⼈没有参加任何项⽬？12. 设}}{{5,2,1,4,3,2,1==B A ,求)()(B P A P ⊕.参考答案： 1-6：CDDBCA7. a) ()()()右左===A C B A C A B b)右=()()()()()()()C B A C C A B C A C B C A C B C A ====左c)左=()()()()()C A B A C B A C B A C B A ===-=右 8. a)A B ?, b)B A ?, c)Φ=B A , d)⽆, e)B A = 9.×√√××× 10. 20051000=, 16661000=,12581000=, 33651000=?,25851000=?,41241000=,81201000=??200+166+125-33-25-41+8=40011.40-(10+12+8-6-6-6+6)=2212.16Chapter 2 关系1. 设S R ,是集合A 上的等价关系,则是等价关系. （）（A ）R A A -? （B ）2R （C ）S R - （D ）()S R r -2. 设A 为某⼀⾮空集合,)(A P 为A 的幂集,在)()(A P A P ?上定义函数:f ()=21,S S f ()2121,S S S S ,)(,21A P S S ∈?,则f 是 .（）（A ）单射但不是满射（B ）满射但不是单射（C ）双射（D ）既⾮单射⼜⾮满射3. 集合A 上的关系21,R R 具有下列哪个性质,使21R R 也具有同样的性质？（）（A ）⾃反（B ）反⾃反（C ）对称（D ）传递4. 设4=A ,则A 上有个等价关系. （）（A ）11 （B ）14 （C ）15 （D ）175. 若A 上的函数f 满⾜A I f=2,则f 是双射. （） 6. 若A 上的函数f 满⾜A I f =3,则f 是双射. （） 7. 若集合A 上的关系21,R R 都是⾃反的,则21R R 也是⾃反的.（）8. 设n A =,则A 上有个关系,有个⾃反关系,有个函数,有个双射.9. 设集合{}c b a S ,,=,求S 上所有满⾜b a f =)(且f f=2的函数10. 已知(){}1,,,=-∈=i j I j i j i R ,求R 的三种闭包. 11. 设n A =,则A 上有多少商集的基数为2的等价关系？ 12. 设{}4,3,2,1=A ,在)(A P 上规定关系R 如下：(){}T S A P T S T S R =∈=),(,,,证明R 是)(A P 上的等价关系,并写出商集R A P /)(.13. +I 上的关系R 定义如下：21Rn n 当且仅当21/n n 能表⽰成m2的样⼦, m 是任⼀整数.（1）证明R 是⼀等价关系；（2）R 下的等价类是什么？参考答案：1 B2 D3 A4 C 5√ 6√ 7√ 8. ()!,,2,222n n n nnn -9.()()(){},,,,,,1b c b b b a f =()()(){}c c b b b a f ,,,,,2=10. (){}r R i j i j I j i or j i (),,,1=∈-==(){}s R i j i j I j i (),,,1=∈-=(){}t R i j i j I j i (),,,=∈>11.12)(211121-=++--n n n n n C C C 12. R 满⾜⾃反、对称、传递性,所以是等价关系；(){}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{4,3,2,1,4,3,2,4,3,1,4,2,1,3,2,1 ,4,3,4,2,3,2,4,1,3,1,2,1,4,3,2,1,/Φ=R A P13. （1）02/=n n ,所以⾃反;m m n n n n -=?=2/ 2/1221,所以对称；lm l m n n n n n n +=?==2/2/,2/313221, 所以传递,所以R 是等价关系（2）[]{}++∈-=I n n R I 12 /RChapter3 命题逻辑单项选择:1. 下列哪个语句是命题？（）（A ）⼈可以长⽣不⽼. （B ）真没劲！（C ）本命题为假. （D ）你吃过了吗？2. 下列语句中哪个是真命题？（）（A ）我在说假话. （B ）如果1+2=3,那么雪是⿊的.（C ）严禁吸烟！（D ）如果疑问句是命题,那么地球将停⽌转动. 3. 下⾯哪个公式不是永真式？（）（A ）()Q P Q ∨→（B ）()P Q P →∧（C ）()()Q P Q P ∨?∧?∧? （D ）()()Q P Q P ∨??→ 4. 下⾯哪个公式是永真式？（）（A ）R Q P ∨→（B ）()()R P Q P →∧∨（C ）()()R Q Q P ∨?∨（D ）()()Q P Q P ∨??→ 5. 是错误的. （）（A ）()P P Q P ∨∧= （B ）()()P Q R P Q R→→=∧→（C ）()()()P Q R Q P R Q →∧→=∨→（D ）()()P Q Q R P R →∧→=→填空题：1. 公式()()()R P Q Q P ∧?→??→可化简为 .2. 公式()()R P Q P P →∨→?∨可化简为 .3. 公式Q P ∨的仅⽤→和?表⽰的逻辑等值式为 .4. 公式Q P ∧的仅⽤→和?表⽰的逻辑等值式为 .计算或证明:1. 求下列公式类型：（1） )()(P Q Q P ?→?→→（2）)()(Q P Q p ∨?→? （北师⼤2000年考研试题）2. 给出真值表：(a) )()(Q P Q P ∧→∨ (b) )(R Q P ∨?→3. 形式证明：()()()E B S A B C F E C B A →??∧→?→?→∧→,,4. 形式证明：()()D C B A →∧→,E B →,F D →,()F E ∧?,C A → ? A ?.5. ⽤推理规则说明()C A C B B A ∧∧?→,,能否同时为真.6. 在某次研讨会的中间休息时间,3名与会者根据王教授的⼝⾳猜测他是哪⾥⼈：甲说王教授不是苏州⼈,是上海⼈；⼄说王教授不是上海⼈,是苏州⼈；丙说王教授既不是上海⼈,也不是杭州⼈.听完3⼈的判断后,王教授笑着说,3⼈中有⼀⼈说得全对,有⼀⼈说对了⼀半,另⼀⼈说得全不对.试⽤真值表⽅法判断王教授到底是哪⾥⼈？7. 公安⼈员审查⼀件盗窃案.已知的事实如下： (1) 甲或⼄盗窃了名画；(2) 若是甲盗窃了名画,则作案时间不可能在午夜前； (3) 若⼄的证词正确,则午夜时屋⾥灯光未灭； (4) 若⼄的证词不正确,则作案时间在午夜前； (5) 午夜时屋⾥灯光灭了,将各命题符号化,推断是谁盗窃了名画,并⽤形式⽅法证明推理的有效性.8. 将下⾯推理符号化并形式证明推理的有效性：如果甲努⼒⼯作,那么⼄或丙感到愉快；如果⼄愉快,那么甲不努⼒⼯作；如果丁愉快,那么丙不愉快；所以,如果甲努⼒⼯作,那么丁不愉快.参考答案：选择1-5: A D C D D 填空：1.()()()P Q Q P R R R 1→??→?∧=∧=；2. ()()R P Q P P →∨→?∨=()()R P Q P P →∨?∧∨()P P R P P R ()1=∨→=∨?∨= 3. P Q P Q ∨=?→4. P Q P Q P Q ()()∧=??∨?=?→?.计算证明：1．解（1）)()(P Q Q P ?→?→→=)()(P Q Q P ?∨→∨? =)()(P Q Q P ?∨∨?∧=)()(P Q Q P Q P ?∨∨?∧?∨∨=1 永真式(2) 若P 和 Q 都为真, 命题为假; 若P 和 Q 都为假, 命题为真, 因此为中性式. 3．证（1） B P(附加) （2） ()S A B ?∧→ P（3） S A ?∧ T （1）,（2）I （4） A T （3）I （5） ()C B A ∧→ P （6） C B ∧ T （4）,（5）I （7） C T （6）I （8） ()C F E ?→?→ P（9） ()F E ?→? T （7）,（8）I （10） ()F E ?∨?? T （9）E （11） F E ∧ T （10）E （12） E T （11）I（13） E B →CP 4．证(1) A P(附加) (2) ()()D C B A →∧→ P(3) B A → T(2)I (4) B T(1),(3)I (5) E B → P(6) E T(4),(5)I (7) C A → P(8) C T(1),(7)I (9) D C → T(2)I (9) DT(8),(9)I(10) F D → P(11) F T(9),(10)I (12) F E ∧ T(6),(11)I (13) ()F E ∧?P(14) ()()F E F E ∧?∧∧ T(12),(13)I 5．解（1）C A ∧ P（2）A T （1）I （3）B A → P（4）B T （2）,（3）I （5）C T （1）I（6）C B ∧ T （4）,（5）I （7）()C B ∧? P（8）()()C B C B ∧∧∧? T （6）,（7）I 所以不能同时为真. 6.解甲⼄丙是杭州⼈是苏州⼈是上海⼈01∧ 01∧ 01∧ 00∧ 11∧ 11∧ 11∧ 00∧ 10∧所以是上海⼈.7．解设：:P 甲盗窃了名画；:Q ⼄盗窃了名画；:R 作案时间在午夜前；:S ⼄的证词正确；:T 午夜时灯光灭了. T R S T S R P Q P , , , ,→??→?→∨证（1）TP（2）T S ?→ P（3）S ?T （1）,（2）I （4）R S →? P （5）R T （3）,（4）I（6）R P ?→P（7）P ?T （5）,（6）I （8）Q P ∨P（9）Q T （7）,（8）I 所以是⼄盗窃了名画.8．解设P ：甲努⼒⼯作；Q ：⼄感到愉快；R ：丙感到愉快；S ：丁感到愉快.S P R S P Q R Q P ?→??→?→∨→ , ,证：（1）PP(附加)（2）R Q P ∨→ P （3）R Q ∨ T （1）,（2）I（4）P Q ?→P（5）Q ?T （1）,（4）I （6）R T （3）,（5）I （7）R S ?→ P（8）S ?T （6）,（7）I（9）S P ?→CPChapter 5 群单项选择:1. 下列集合中, 对普通加法和普通乘法都封闭. （）（A ）{}1,0 （B ）{}2,1 （C ）{}N n n ∈2 （D ）{}N n n∈22. 在⾃然数集N 上,下⾯哪种运算是可结合的？（）（A ）b a - （B ）),max(b a （C ）b a 2+ （D ）b a -3. 有理数集Q 关于下列哪个运算能构成代数系统？（）（A ）ba b a =*（B ）()1ln 22++=*b a b a（C ）()b a b a +=*sin （D ）ab b a b a -+=*4. 下列代数系统,哪个是独异点？（）（A ）()22,,b a b a R +=（B ）()333,,b a b a R +=**（C ）()max ,I （D ）()表⽰最⼤公约数GCD GCD I ,,+.5. 下列各个N 的⼦集,哪个关于加法封闭？（）（A ）{}整除的某次幂能被6x x （B ）{}互质与5x x（C ）{}的因⼦是30x x（D ）{}N n x x n∈=,26. 下列运算中,哪种运算关于整数集I 不能构成半群？（）（A ）()b a b a ,max =* （B ）b b a =* （C ）ab b a 2=* （D ）b a b a -=*7. 运算*定义为： b a b a ?=*,则代数系统()*,R 是（）（A ）半群（B ）独异点（C ）群（D ）交换群 8. 设{}1,0=S ,则代数系统()?,S 是（）（A ）半群（B ）独异点（C ）群（D ）交换群 9. 具有多个幂等元的半群,它（）（A ）不能构成群（B ）不⼀定能构成群（C ）必能构成群（D ）能构成交换群10. 设实数集R 上的运算*定义为：x y x =*,则()*,R （）（A ）不是代数系统（B ）是半群,但不是独异点（C ）是独异点,但不是群（D ）是群.11. 运算*定义为:ab b a b a -+=*,则代数系统()*,Q 的单位元是（）（A ）a （B ）不存在（C ）1 （D ）012. 代数系统()*,R 中*表⽰普通乘法,下列映射中是R R →的⼀个⼦集的同态. （A ）2x x →（B ）x x 2→（C ）xx 2→（D ）x x -→是⾮题1. 设),(*S 是代数系统,S B ?,则()*,B 是),(*S 的⼦代数系统. （）2. 设),(*S 是代数系统,S a ∈,若a 的左、右逆元均存在,则必相等.（）3. 若代数系统的右零元存在,则必唯⼀. （）4. 若()()**,,,B A 都是群()*,G 的⼦群,则()*?,B A 也是()*,G 的⼦群.（）5. 设),(*S 是半群,若l θ是左零元,则对l x S x θ*∈?,仍是左零元.（）6. 设),(*S 为可交换独异点,{}x x x S x x T =*∈=,,则T 也是独异点.（） 7. 设),(*G 为独异点,若对,,e a a G a =*∈?有其中e 是单位元,则),(*G 是交换群.（）8. 除了单位元以外,⼀个群没有其他幂等元. （） 9. 设{}I n m G n m ∈=,23,则()?,G 是群. （）计算与证明1．设{}0-=*R R ,在R R ?*上定义运算*如下: ()()()d bc ac d c b a +=*,,,,()()R R d c b a ?∈?*,,,,证明: ()*?*,R R 构成群. 2. 设()*,G 是群,若对任意G x ∈,有x x=-1,则()*,G 是交换群.3. 设()*,A 是⼀个半群,且满⾜以下条件：A b a b a a b b a ∈?=?*=*,,,证明：（1）A a ∈?,有a a a =*；（2）A b a ∈?,,有a a b a =**；（3）A c b a ∈?,,,有c a c b a *=**.4. 设u 是群()*,G 中取定的元素,在G 中定义运算b u a b a **=-1: ,其中1-u 为u 在群()*,G 中的逆元.证明：() ,G 也是⼀个群.5. 设()*,G 是交换群,()()**,,,B A 是它的⼦群,{}B b A a b a ABC ∈∈*==,,证明：()*,C 也是()*,G 的⼦群.6. 设()*,1H ,()*,2H 是群()*,G 的两个互不包含的⼦群.证明:G 中存在元素既不属于1H ⼜不属于2H .参考答案CBDBADABABDA FFFTTTTTT1．证 (1) 运算*在R R ?*上封闭,所以()*?*,R R 构成代数系统； (2) ()()()()),(,),(,,f e d bc ac f e d c b a *+=**()()f de bce ace f e d bc ace ++=++=,)(,,()()()()f de ce b a f e d c b a +*=**,,),(),(,()f de bce ace ++=,,所以满⾜结合律；(3)单位元()0,1=e ； (4) ()??-=-a b a b a ,1,1综上所述, ()*?*,R R 构成群.2．证 ()()x y x y y x y x *=*=*=*---111,即*可交换.3．证（1）由结合律,()()a a a a a a a a a *=?**=**；（2）()()()()a b a a a a b a a a b a a b a a a b a a **=?***=***=***=***；（3）)()(c a c b a ****c b a c a c b a **=****=)()()()()(c b a c a c b a c a ****=****=, ? c a c b a *=**.4. 证由*的封闭性可以得到的封闭性,结合律显然,关于的⼳元为u ,a 关于的逆元为u a u **-1,其中1-a 为a 关于*的逆元.5. 证（1）C d c b a ∈**?,,即 B d b A c a ∈∈,,,,因为()()**,,,B A 是群,B d b A c a ∈*∈*, ,⽽*可交换, ()()()()()()C d b c a d b c a d c b a d c ∈***=***=***=***∴b a , 即*在C 中封闭;（2）C e e e ∈*= 所以C 有单位元;（3）()C b a a b b a ∈*=*=*-----11111,所以C 中的元素可逆; （4）*在C 中显然满⾜结合律 . 综上所述,()*,C 构成()*,G 的⼦群.6. 证因为1H ,2H 互不包含,所以1H a ∈?但2H a ?,2H b ∈?但1H b ?,若1H b a ∈*,则11)(H b a a b ∈**=-,⽭盾,故1H b a ?*；同理,2H b a ?*,所以21H H b a ?*.chap6,7 图论补充练习1. 在任何图中必有偶数个的结点. （ B ）（A ）度数为偶数（B ）度数为奇数（C ）⼊度为偶数（D ）出度为偶数2. 下列序列中,哪⼀个可构成简单⽆向图的结点度数序列？（ B ）（A ）()3,2,2,1,1 （B ）()2,2,2,1,1 （C ）()3,3,3,1,0 （D ）()5,4,4,3,23. 设()m n ,图G 中有k N 个k 度结点,其余均为1+k 度结点,则k N 为（ C ）（A ）2n（B ）()1+k n （C ）()m k n 21-+ （D ）()m k n -+1 4. 附图不是 .（ C ）（A ）欧拉图（B ）哈密尔顿图（C ）⼆部图（D ）完全图1．证明：有k 个连通分⽀的简单⽆向图⾄多有)1)((21+--k n k n 条边．证设分⽀i G 是()i i m n ,图,k i ,,1 =,则()121-≤i i i n n m ,()11--≤≤k n n i ,∑==ki in n 1, ()()()()()k n k n n k n n n m m ki i k i k i i i i -+-=-+-≤-≤=∴∑∑∑===1211121121 1112. 设G 是边数30假设()n i v i ,,1,5deg =≥，由握⼿定理，()∑≥=n v m i 5deg 2，所以652363-?≤-≤m n m ,于是30≥m ,与已知条件⽭盾,于是结论成⽴. 3. 设G 是简单平⾯图,证明G 中⾄少有⼀个结点的度数⼩于等于5.证不妨设G 连通，否则考察G 的⼀个连通分⽀．设G 有n 个结点，m 条边，k 个⾯．若2≤m ，因为G 是简单图，结论成⽴；若3≥m ，()3≥∴i F d ，m k k m 32,32≤≥；假设()n i v d i ,,1,6 =≥，则n m 62≥，n m 3≥，由欧拉公式，032312=+-≤+-=m m m k m n ，⽭盾．4. 设G 为阶数11≥n 的简单⽆向图,且G 和G 均连通.证明：G 或G ⾄少有⼀个不是平⾯图.证 (反证)假设()1,m n G 和()2,m n G 都是平⾯图，⽽11≥n ，所以632,1-≤n m ,⽽()12121-=+n n m m ，所以()126121-≤-n n n ，或024132≤+-n n , 所以，1127313 <+≤n ，与条件⽭盾．所以G 和G ⾄少有⼀个不是平⾯图．5. 设G 为阶数7证假设G 和G 都不是平⾯图，由Kuratowsky 定理,G 和G 必含有与5K 或3,3K同胚的⼦图，即⾄少有9条边，于是G 和G 的边数之和()1812 1≥-n n ，7 ≥?n ,与7。