你的位置：首页 > IT圈 > 离散数学习题整合

离散数学习题整合

IT圈 admin 2024-02-25 61浏览 0评论

2024年2月25日发(作者：宰丽文)

CHOI复习§1.2

命题判断（每空1分，共4分）1.1-1.3 P32-

A小李和小王是同班同学

B小猪不是鲜花

C 3-2n<0 D若2+2=4,则太阳从

西方升起。

上述语句中，—是简单命题，—不是命题，—是符合命题且真值为假，_是符合命题且真值为真。（参考答案：ACDB）

命题符号化（每空2分，共4分）习题1.5（7）（3） P32-

P：天下人雨，q：他乘公共汽车去上班，命题“除非天下大雨，否则他不乘公共汽车去上班”可符号化为—o

（参考答案：q-p必要条件为后件）

r：天很冷，s：老李来了，命题“虽然天很冷，老李还是来了”可符号化为_,（参考答案rAs）

五个真值表（每空2分，共4分）习题1.6（2）（4） P32-

设P的真值为0, r的真值为1, q、s都是命题，则命题公式（3

o r）人Jq v s）的真值为 _______ ,命题公式->

3 v （q Cr人「p〉））t Cr v「s）的真值为 ______ 。（参考答案：0,1）

用符号p、q填空。（每空1分，共4分）朕本概念

设p： x>0 （其中x是整数），q：太阳从西方升起，则_是命题，_是命题变项，是命题常项，_不是命题。（参考答案：q，p, q, p）

命题符号化，相容或与排斥或

设r：现在小李在图书馆，s：现在小李在学生宿舍，则“现在小李在图书馆或学生宿舍”

可符号化为—。（参考答案：B）

A rVs B （rA-'sJV （"YAs）

§ 1.2命题公式及分类

C rAs D （rA-'s）或（~YAS）

已知：A是含三个命题变项的命题公式，且A（001）=0, A（100）=l,则A是 ______

o （D）

A矛盾是

B可满足式

C重言式

D非重言式的可满足式

§ 1.3等值演算

用等值演算法证明等值式：（p/q）f中〜（q-r）.（演算的每一步都要写依据）

§ 1.4范式

（每项1分，共4分）已知命题公式A（p,q）的真值表

01、

11, 00、

10）

A(p,q)

求A的永主析取范式、主合取范式、成真赋值和成假赋值。（参考答案：miVm3, M0AM2,

7. （2分）命题公式B（p,qj）=（「p/r7「q）的主析取范式是 ___ 。（参考答案：C）

A m2 B M6 C mi D M5 E

命题公式B（pzq,r）=（-pV-qVr）W主析取范式是 ____ 。（参考答案：A）

A moVmiVm2Vm3Vm4Vm5Vm7 B IVk C mi D Mi

§1.5全功能集（2分）

_____ 不是联结词全功能集。（参考答案：D）

A{t}

A{l,}

§ 1.6组合电路

B{- -*}

B{V,A} C{V}

C{- V} D{A,V}

D{A}

_____ 是联结词全功能集。（参考答案：A）

（习题1.16）有一盏灯由三个开关控制，要求按任何一个开关都能使灯由黒变亮或由亮变黑,

试设计这样的一个电路。

（解题基本步骤：状态设置、设计真值表、写主析取范式、化简、绘制电路.答案不唯一）

§ 1.7推理理论

（习题1.19（1））用直接证明法或归谬法证明下面的推理.

前提：■'（pA^q）,「qVr, ~T.结论：~p-

证明：...

（习题1.19⑶）用直附加前提法证明卞面的推理.

前提：P~*q.结论：P-*（pAq）.

证明：...

（例题1.28）公安人员审查一件盗窃案，已知事实如下：

（1）

李或王盗窃了录音机；

（2）

若李盗窃了录音机，则作案时间不能发生在午夜前;

（3）

若王的证词正确，则午夜时屋里灯光未灭；

（4）

若王的证词不正确，则作案时间发生在午夜前：

（5）

午夜时屋里灯光灭了.

试问盗窃录音机的是李还是王，并证明你的结论。参考答案：王盗窃了录音机.

设p：李盗窃了录音机；

q：王盗窃了录音机；

r：作案时间发生在午夜前；

s：王的证词正确；

t：午夜时屋里灯光灭了.

前提：pVq, pf~T, s-*t,飞~*「，飞.结论：q.

证明：...

CH02复习题

§2.1

例

2.1 （3）

1将命题“若李一的成绩比王二高，王二的成绩比吴三高，那么李一的成绩比吴三高”用0

元谓词符号化。

解：设H(x,y)： x的成绩比y高，a：李一，b：王二，c:吴三

则命题可符号化为H(a,b)A H(b,c) H(a,c)

§2.1

例

2.4 (4)

2在一阶逻辑中将命题“素数不全是奇数”符号化。

解：设F(x)： x是素数，G(x)： x是奇数

则命题可符号化为x(F(x)AG(x))

或

x(F(x)G(x))

(每空1分，共4分)

给定解释I，对一阶逻辑合式公式中每个 _______ 出现的 __________ 指定 __________ 中的一

个元素，称作在 __________ 下的赋值。(自由个体变项个体域解释I)

§2.2

4下面的一阶逻辑合式公式 _______ 不是闭式。(D

有自由出现)

A x(F(x)G(X)) B y(F(x,y)G(x)) C xF(x)yG(y) D xF(x,y)yG(y) §2.2

5下面各种叙述， _______ 不正确。(C

例2.8 (5))也町改造成正误判断题

A在给定的解释和赋值卞，任何一阶逻辑合式公式都是命题VP45-

B闭公式的真值与赋值无关，只需要给定解释

C非闭式的公式的真值只与赋值有关

D可满足式可能是逻辑有效式

§2.3

在四个合式公式

A 2 B 3

(尸(x)T(G(y)/〃(尤

y)))

、Vx(尸(x)T3y(G(y)人〃(x, y)))、

C 1 D 0

V4(F3"(X))、「丑(尸323)中共有 ____________________ 个是前束范式。(参考答案：A)

(*参考答案:B)

已知

F (x)亠>王丫(必3

人F(x)), Gi (x)二Vxr

(MCY) A 尸3),

G： (x)二V->F(AF)),

G3(X)*XW3T「F3),则在

G：(x)、G,x)和

Gs(x)中，有 ________________ 个是

F(x)的前束范式。

A 0 B 3 C 2 D 1

例

2.11 (3)

8求公式xF(x)G(x)的前束范式。

解：xF(x)G(x)

xF(x)xG(x)(蕴涵等值式)

xF(x)xG(x)(量词否定等值式)

xF(x)G(x))(量词分配等值式) 解法

xF(x)yG(y)(换名规则)

x(F(x)yG(y))(量词扩

TH2.2(2)③)

xyF(x)G(y))(量词扩

TH2.2⑵④)

2： xF(x)G(x)

解法

3： xF(x/)G(x)F(y)G(x))

§ 2.4

例

2.17

设个体域D={a,b}t消去公式x(F(x) AyG(y))中的量词。

离散CH03复习题

判断(1分/每小题)

若集合

A={1, {1,2}, 3},则

若集合

B={2, {a, b}},则{a, b}B (X)

单选(2分/每小题)

下面的集合算式 ______ 不正确。(VA=.-.C)

A A-(BUC)=A-B) U (A-C) B A_B=A A

〜B

A |{, {c}, {{a, b}}, B}| B2

C A二A D ABA-B=

C3 D8

(X)

已知

B={{a, b}, c},则|

P(A) | = _____ . ( VP(A)={, {c}, {{a, b}}, B}, A A)

填空(2分/每小题)

若

|P(A)| =12

8,则

|A|= ______ .(V|P(A)|=27/A7)

设

A={lz33}>

贝'J|A|= _____ . VA={1,3}»

・・・2)

计算(8分/每小题)

某班有48个学生，第一次作业优秀7人，第二次作业优秀6人，两次作业都没得优秀的

41人，求两次作业都得优秀的人数。(求解过程参见[例3.12],参考答案：6)

解：用A、B分别表示第一次和第二次作业优秀的人数集合，E为某班全体学生的集合

则：|E|=48, |A|=7, |B|=6,

|〜AC

〜B|=41

〜AC

〜B| = |E卜(|A| + |B|)+|ADB|

|ADB| = 41-48+(7+6)

己知

A二{{a, b}, c, d}, B={c, d},计算

ADB、AUB、A-B、AB。(P74-3.13(l))

画图

画(AC

〜B) U (C-B)的文氏图。(3.15 (3))

证明：(AC〜B) U

(C-B) = (AUC)

一

证：左式二(AC〜B) = U (CH〜B )

(AUC) Cl

〜B =

(AUC)-B

(3.27 /差交运算转换)

(3.8/分配律)

(3.27 /差交运算转换)

离散CH04复习J

判断（1分/每小题）

§4.1

1. A是任意集合，则AXA的任何子集称作A上的二元关系，

若集合

B={2, {a, b}},则{a, b}B （X）

（V）

单选（2分/每小题）

§4.1

3. A是任意集合，{〈x, x>|xA}称作 ________ 关系。（•・•恒等关系蕴含其是A上的・・・B）

A空

设

A={a, b, c}»

B恒等

C全域

D A上的

R={, , < b, b>, , , },则 _________________ 是

R的关系矩阵。（参见P80-,参考答案：（A）

BCD

设S={1,2,3,4}, R是S上的关系，其关系矩阵是，R的关系图中有_个环。

A 1 B 3 C 6 D 7

填空（2分/每小题）

§4.1

6. A、B

是任意两个集合，若

|A|=m, |B|=n,贝lJ|P（AXB）|= ______

。

§4.5

8. R是集合A上的等价关系，如果有序对R,则记作 _________。（a〜b）

若R是集合A上的偏序关系，则可将此偏序关系简记作;有序对,可记作 _______

o（ab）

（）

设A是任意集合，|A|=n,则A上有 ___________ 个不同的二元关系。（,|AXA|=n2）

计算（8分/每小题）

§4.2

10.

己知关系

R={<2,{2}>, <{2},{2,{2}}>},求

RR、R{2}、R[{2}].（同例

4.7

理解定义

4.9）

解：RR={<2, {2,{2}}>}

R⑵={<2,{2}>}限制

R[{2}] = ran （R{2}） = ran{<2,{2}>} = {{2}}

像集

11.

已知人*,

b, c, d}, Ri

和

是

上的关系，且

Rx={, , },

R2={, , , }。求

R2R1。

解：V Ri R2 , R2Ri

Ri R2 ,・°・R2Ri

故

R2Ri={,

证明题

综合：§ 1等值公式和等值运算+ § 3集合运算+ §

4关系性质的定义

12.设集合A上的两个关系Ri和R2都是对称的，证明RLAR2仍是对称的。

证明：参见主教材P87-

13.试证任何集合A的幕集P（A）上的包含关系R是偏序关系

证明：

xP(A),都有xx- R・・・R是自反的

R A xHy

xy A xHy

(包含关系的定义)/.R是反对称的

x、t、yP(A), ®RAR

(集合包含关系的定义)

则xtAty

(关系R的定义)

(集合运算律)

(关系R的定义)...R是传递的

14.己知R的关系图如下图所示，画R的自反闭包「(R)、对称闭包s (R)、传递闭包t(R)・

15.画<{1234567,8}, R整除〉的哈斯图。

16.判断函数f： N-N,是否是满射、单射、双射，为什么?

解：作f的对应关系图如右，由图可知

1无原像，故f非满射，也非双射。

但f是单射。

离散CH05

选择一个最合适的答案

•下图中的边亠租边序列『：eo ei e2 e3 e4e5称为 ________________ 。(A)

D复杂通路

2•卞面有向图中的顶点序列Vo Vi V2 V3 V4 V2 V5称为 _____________

o (C)

A路径

B初级通路

C简单通路

D复杂通路

3. ______

能构成图的度数序列。(C)

A (3, 3, 2, 1) B (2, 3, 2) C (1)

D (3, 3, 3)

填空：

设G (V,E)是n阶有向简单图，若u,胆V,都有 ____________________________ ,则称G是n

阶有向完全图。(<—v>eE A eE)

5. G (V,E)是n阶有向完全图，通常记为 __________

(K,,)

在下面的有向图中，从V2到V2的长度为2的初级回路是 ___________________ °

v2e4v1e1v2

7•在下面的无向图中，顶点 _____ 是割点，边 ______ 是桥。(琏)(e3)

8•设G是有向图或无向图，称p (G)是图G的 __________________

(连通分支个数) 简答(6分/每小题)

§5.2

下面三个无向图，它们之间哪些同构，哪些不同构。若不同构，为什么？若同构，请建立顶点之间的双射。

答：图Gi与图G2不同构，因为图$与G2存在度不相同的顶点。…2分同理G2G3. ...2分

...2

Gi G3・

分

4°^^0B

建立顶点之间的如下对应关系f:

3-C, 4-* f是双射，并且

两图的边也一一对应。

10•无向图的（点）着色：P132-例5.5

•图强连通，图单向连通，图弱连通，图非连通。

R 0

必

参考答案：D2、6 . D4、DJ

12•应用题

P133-[例

5.6]

离散CH06

选择一个最合适的答案

1. __________________________________

下面三种说法，其中不正确的有个。（C还有必要条件）

①

Hall定理是二部图G（V“ V.E）存在完备匹配的充要条件

② 无论是有向图还是无向图，都有判断其是否存在欧拉通路和欧拉回路的充要条件

③ 目前只有判断哈密顿图的充分条件

A 0 B 3 C 1 D 2

2. _______________________________

下面（A）

四种说法，其中正确的有 _____________ 个。

②存在是欧拉图不是哈密顿图的无向图

①存在既是欧拉图又是哈密顿图的无向图

③存在不是欧拉图却是哈密顿图的无向图

④ 存在既不是欧拉图又不是哈密顿图的无向图

D 1

填空

§6.1

3.用GM ,

Q表示二部图G, | X|=n, | V2|=m,记号表示图G为 _________________________

（完全二部图）

§6.4

4・若图G画在平面上使得除顶点处外没有 ____________ 出现，则称G为平面图。（边交叉）

5•卞面的平面图共有 _______ 个面，其中无限面Ro的次数deg （Ro）=

(3, 8)

平而图6-1

_____ o (9)

非连通平而图6-2

应用题：

7. P151-习题6.5

（二部图的应用）

8. P151-习题6.15

（哈密顿图的应用）

9. P152-习题6.18

（欧拉通路或欧拉回路的应用）

10. *P152-习题6.23

（平面图在作色中的应用）

离散CH07复习J

§7.1

1. P165- I 12设n阶连通无向图G（V,Q有m条边，G的生成树有 ____________ 条边，余树有

条边。（n-1, m-n+l）

2. P167-例7.5 （2）画出4个顶点非同构无向树。（2种）

3. P173-习题7.16 （3）画出4个顶点非同构的根树（4种）

下面三条叙述中有 _____ 条正确。（B）

①一阶零图是一棵树 ②只有一片树叶的树在同构意义下只有1种

③ 树中每条边都是桥 ④在树中任意两个不相邻顶点卩U加一条边会形成唯一 -条初级回路

AO B3 C2 D1

计算题

5. （6分）一棵树有2个4度顶点，3个3度顶点，其余都是树叶，则该树有 ________ 片树叶。

（9

＜与P171-习题7.1同类型〉）

解：设该树有x片树叶、n个节点、m条边

贝IJ

度数之和=4X2 + 3X3 + lXx

二

17+x

二

2 + 3 + x = 5+x

二

n~l

（树）=4+x

17+x = 2m

（握手定理）二

2 （4+x） x = 9

6. P171-最小生成树-习题7.8 （b）

7. P173-最佳二元前缀码-习题7. 17

离散CH09

§9.1

1曾是非零实数集，1是L上普通乘法的幺元，蔦对普通乘法，a的逆元是 °

(a-1

或

1/a)

2 n阶单位矩阵是n阶矩阵 ________ 的幺元。(乘法)

3在集合A的幕集P(A)±, _________

是U运算的幺元Cl运算的零元。(0)

_____ 是门运算的幺元U运算的零元。(A)

4 _____

正确。(D)

A减法是自然数集N上的二元运算

C加法是非零实数集R•上的二元运算

5 _____

错误。(C)

A 0是加法的幕等元

C单位矩阵E是矩阵加法的幕等元

B除法是整数集上的二元运算

D㊉是任意集合A的幕集P(A)上的二元运算

B 1是乘法的幕等元

D 0是幕集P(S)上㊉运算的幕等元

6二{0,1}, X表示空串， _________是回文语言， _______ 是镜像语言…(A, D)

A (0n10r |n N} = {l,010, 00100,-}

C {(01)n|n N} = {X,01,0101, -}

B {(TT |n N} = { X , 01, 0011,-}

D {01, 10}

2024年2月25日发(作者：宰丽文)

CHOI复习§1.2

命题判断（每空1分，共4分）1.1-1.3 P32-

A小李和小王是同班同学

B小猪不是鲜花

C 3-2n<0 D若2+2=4,则太阳从

西方升起。

上述语句中，—是简单命题，—不是命题，—是符合命题且真值为假，_是符合命题且真值为真。（参考答案：ACDB）

命题符号化（每空2分，共4分）习题1.5（7）（3） P32-

P：天下人雨，q：他乘公共汽车去上班，命题“除非天下大雨，否则他不乘公共汽车去上班”可符号化为—o

（参考答案：q-p必要条件为后件）

r：天很冷，s：老李来了，命题“虽然天很冷，老李还是来了”可符号化为_,（参考答案rAs）

五个真值表（每空2分，共4分）习题1.6（2）（4） P32-

设P的真值为0, r的真值为1, q、s都是命题，则命题公式（3

o r）人Jq v s）的真值为 _______ ,命题公式->

3 v （q Cr人「p〉））t Cr v「s）的真值为 ______ 。（参考答案：0,1）

用符号p、q填空。（每空1分，共4分）朕本概念

设p： x>0 （其中x是整数），q：太阳从西方升起，则_是命题，_是命题变项，是命题常项，_不是命题。（参考答案：q，p, q, p）

命题符号化，相容或与排斥或

设r：现在小李在图书馆，s：现在小李在学生宿舍，则“现在小李在图书馆或学生宿舍”

可符号化为—。（参考答案：B）

A rVs B （rA-'sJV （"YAs）

§ 1.2命题公式及分类

C rAs D （rA-'s）或（~YAS）

已知：A是含三个命题变项的命题公式，且A（001）=0, A（100）=l,则A是 ______

o （D）

A矛盾是

B可满足式

C重言式

D非重言式的可满足式

§ 1.3等值演算

用等值演算法证明等值式：（p/q）f中〜（q-r）.（演算的每一步都要写依据）

§ 1.4范式

（每项1分，共4分）已知命题公式A（p,q）的真值表

01、

11, 00、

10）

A(p,q)

求A的永主析取范式、主合取范式、成真赋值和成假赋值。（参考答案：miVm3, M0AM2,

7. （2分）命题公式B（p,qj）=（「p/r7「q）的主析取范式是 ___ 。（参考答案：C）

A m2 B M6 C mi D M5 E

命题公式B（pzq,r）=（-pV-qVr）W主析取范式是 ____ 。（参考答案：A）

A moVmiVm2Vm3Vm4Vm5Vm7 B IVk C mi D Mi

§1.5全功能集（2分）

_____ 不是联结词全功能集。（参考答案：D）

A{t}

A{l,}

§ 1.6组合电路

B{- -*}

B{V,A} C{V}

C{- V} D{A,V}

D{A}

_____ 是联结词全功能集。（参考答案：A）

（习题1.16）有一盏灯由三个开关控制，要求按任何一个开关都能使灯由黒变亮或由亮变黑,

试设计这样的一个电路。

（解题基本步骤：状态设置、设计真值表、写主析取范式、化简、绘制电路.答案不唯一）

§ 1.7推理理论

（习题1.19（1））用直接证明法或归谬法证明下面的推理.

前提：■'（pA^q）,「qVr, ~T.结论：~p-

证明：...

（习题1.19⑶）用直附加前提法证明卞面的推理.

前提：P~*q.结论：P-*（pAq）.

证明：...

（例题1.28）公安人员审查一件盗窃案，已知事实如下：

（1）

李或王盗窃了录音机；

（2）

若李盗窃了录音机，则作案时间不能发生在午夜前;

（3）

若王的证词正确，则午夜时屋里灯光未灭；

（4）

若王的证词不正确，则作案时间发生在午夜前：

（5）

午夜时屋里灯光灭了.

试问盗窃录音机的是李还是王，并证明你的结论。参考答案：王盗窃了录音机.

设p：李盗窃了录音机；

q：王盗窃了录音机；

r：作案时间发生在午夜前；

s：王的证词正确；

t：午夜时屋里灯光灭了.

前提：pVq, pf~T, s-*t,飞~*「，飞.结论：q.

证明：...

CH02复习题

§2.1

例

2.1 （3）

1将命题“若李一的成绩比王二高，王二的成绩比吴三高，那么李一的成绩比吴三高”用0

元谓词符号化。

解：设H(x,y)： x的成绩比y高，a：李一，b：王二，c:吴三

则命题可符号化为H(a,b)A H(b,c) H(a,c)

§2.1

例

2.4 (4)

2在一阶逻辑中将命题“素数不全是奇数”符号化。

解：设F(x)： x是素数，G(x)： x是奇数

则命题可符号化为x(F(x)AG(x))

或

x(F(x)G(x))

(每空1分，共4分)

给定解释I，对一阶逻辑合式公式中每个 _______ 出现的 __________ 指定 __________ 中的一

个元素，称作在 __________ 下的赋值。(自由个体变项个体域解释I)

§2.2

4下面的一阶逻辑合式公式 _______ 不是闭式。(D

有自由出现)

A x(F(x)G(X)) B y(F(x,y)G(x)) C xF(x)yG(y) D xF(x,y)yG(y) §2.2

5下面各种叙述， _______ 不正确。(C

例2.8 (5))也町改造成正误判断题

A在给定的解释和赋值卞，任何一阶逻辑合式公式都是命题VP45-

B闭公式的真值与赋值无关，只需要给定解释

C非闭式的公式的真值只与赋值有关

D可满足式可能是逻辑有效式

§2.3

在四个合式公式

A 2 B 3

(尸(x)T(G(y)/〃(尤

y)))

、Vx(尸(x)T3y(G(y)人〃(x, y)))、

C 1 D 0

V4(F3"(X))、「丑(尸323)中共有 ____________________ 个是前束范式。(参考答案：A)

(*参考答案:B)

已知

F (x)亠>王丫(必3

人F(x)), Gi (x)二Vxr

(MCY) A 尸3),

G： (x)二V->F(AF)),

G3(X)*XW3T「F3),则在

G：(x)、G,x)和

Gs(x)中，有 ________________ 个是

F(x)的前束范式。

A 0 B 3 C 2 D 1

例

2.11 (3)

8求公式xF(x)G(x)的前束范式。

解：xF(x)G(x)

xF(x)xG(x)(蕴涵等值式)

xF(x)xG(x)(量词否定等值式)

xF(x)G(x))(量词分配等值式) 解法

xF(x)yG(y)(换名规则)

x(F(x)yG(y))(量词扩

TH2.2(2)③)

xyF(x)G(y))(量词扩

TH2.2⑵④)

2： xF(x)G(x)

解法

3： xF(x/)G(x)F(y)G(x))

§ 2.4

例

2.17

设个体域D={a,b}t消去公式x(F(x) AyG(y))中的量词。

离散CH03复习题

判断(1分/每小题)

若集合

A={1, {1,2}, 3},则

若集合

B={2, {a, b}},则{a, b}B (X)

单选(2分/每小题)

下面的集合算式 ______ 不正确。(VA=.-.C)

A A-(BUC)=A-B) U (A-C) B A_B=A A

〜B

A |{, {c}, {{a, b}}, B}| B2

C A二A D ABA-B=

C3 D8

(X)

已知

B={{a, b}, c},则|

P(A) | = _____ . ( VP(A)={, {c}, {{a, b}}, B}, A A)

填空(2分/每小题)

若

|P(A)| =12

8,则

|A|= ______ .(V|P(A)|=27/A7)

设

A={lz33}>

贝'J|A|= _____ . VA={1,3}»

・・・2)

计算(8分/每小题)

某班有48个学生，第一次作业优秀7人，第二次作业优秀6人，两次作业都没得优秀的

41人，求两次作业都得优秀的人数。(求解过程参见[例3.12],参考答案：6)

解：用A、B分别表示第一次和第二次作业优秀的人数集合，E为某班全体学生的集合

则：|E|=48, |A|=7, |B|=6,

|〜AC

〜B|=41

〜AC

〜B| = |E卜(|A| + |B|)+|ADB|

|ADB| = 41-48+(7+6)

己知

A二{{a, b}, c, d}, B={c, d},计算

ADB、AUB、A-B、AB。(P74-3.13(l))

画图

画(AC

〜B) U (C-B)的文氏图。(3.15 (3))

证明：(AC〜B) U

(C-B) = (AUC)

一

证：左式二(AC〜B) = U (CH〜B )

(AUC) Cl

〜B =

(AUC)-B

(3.27 /差交运算转换)

(3.8/分配律)

(3.27 /差交运算转换)

离散CH04复习J

判断（1分/每小题）

§4.1

1. A是任意集合，则AXA的任何子集称作A上的二元关系，

若集合

B={2, {a, b}},则{a, b}B （X）

（V）

单选（2分/每小题）

§4.1

3. A是任意集合，{〈x, x>|xA}称作 ________ 关系。（•・•恒等关系蕴含其是A上的・・・B）

A空

设

A={a, b, c}»

B恒等

C全域

D A上的

R={, , < b, b>, , , },则 _________________ 是

R的关系矩阵。（参见P80-,参考答案：（A）

BCD

设S={1,2,3,4}, R是S上的关系，其关系矩阵是，R的关系图中有_个环。

A 1 B 3 C 6 D 7

填空（2分/每小题）

§4.1

6. A、B

是任意两个集合，若

|A|=m, |B|=n,贝lJ|P（AXB）|= ______

。

§4.5

8. R是集合A上的等价关系，如果有序对R,则记作 _________。（a〜b）

若R是集合A上的偏序关系，则可将此偏序关系简记作;有序对,可记作 _______

o（ab）

（）

设A是任意集合，|A|=n,则A上有 ___________ 个不同的二元关系。（,|AXA|=n2）

计算（8分/每小题）

§4.2

10.

己知关系

R={<2,{2}>, <{2},{2,{2}}>},求

RR、R{2}、R[{2}].（同例

4.7

理解定义

4.9）

解：RR={<2, {2,{2}}>}

R⑵={<2,{2}>}限制

R[{2}] = ran （R{2}） = ran{<2,{2}>} = {{2}}

像集

11.

已知人*,

b, c, d}, Ri

和

是

上的关系，且

Rx={, , },

R2={, , , }。求

R2R1。

解：V Ri R2 , R2Ri

Ri R2 ,・°・R2Ri

故

R2Ri={,

证明题

综合：§ 1等值公式和等值运算+ § 3集合运算+ §

4关系性质的定义

12.设集合A上的两个关系Ri和R2都是对称的，证明RLAR2仍是对称的。

证明：参见主教材P87-

13.试证任何集合A的幕集P（A）上的包含关系R是偏序关系

证明：

xP(A),都有xx- R・・・R是自反的

R A xHy

xy A xHy

(包含关系的定义)/.R是反对称的

x、t、yP(A), ®RAR

(集合包含关系的定义)

则xtAty

(关系R的定义)

(集合运算律)

(关系R的定义)...R是传递的

14.己知R的关系图如下图所示，画R的自反闭包「(R)、对称闭包s (R)、传递闭包t(R)・

15.画<{1234567,8}, R整除〉的哈斯图。

16.判断函数f： N-N,是否是满射、单射、双射，为什么?

解：作f的对应关系图如右，由图可知

1无原像，故f非满射，也非双射。

但f是单射。

离散CH05

选择一个最合适的答案

•下图中的边亠租边序列『：eo ei e2 e3 e4e5称为 ________________ 。(A)

D复杂通路

2•卞面有向图中的顶点序列Vo Vi V2 V3 V4 V2 V5称为 _____________

o (C)

A路径

B初级通路

C简单通路

D复杂通路

3. ______

能构成图的度数序列。(C)

A (3, 3, 2, 1) B (2, 3, 2) C (1)

D (3, 3, 3)

填空：

设G (V,E)是n阶有向简单图，若u,胆V,都有 ____________________________ ,则称G是n

阶有向完全图。(<—v>eE A eE)

5. G (V,E)是n阶有向完全图，通常记为 __________

(K,,)

在下面的有向图中，从V2到V2的长度为2的初级回路是 ___________________ °

v2e4v1e1v2

7•在下面的无向图中，顶点 _____ 是割点，边 ______ 是桥。(琏)(e3)

8•设G是有向图或无向图，称p (G)是图G的 __________________

(连通分支个数) 简答(6分/每小题)

§5.2

下面三个无向图，它们之间哪些同构，哪些不同构。若不同构，为什么？若同构，请建立顶点之间的双射。

答：图Gi与图G2不同构，因为图$与G2存在度不相同的顶点。…2分同理G2G3. ...2分

...2

Gi G3・

分

4°^^0B

建立顶点之间的如下对应关系f:

3-C, 4-* f是双射，并且

两图的边也一一对应。

10•无向图的（点）着色：P132-例5.5

•图强连通，图单向连通，图弱连通，图非连通。

R 0

必

参考答案：D2、6 . D4、DJ

12•应用题

P133-[例

5.6]

离散CH06

选择一个最合适的答案

1. __________________________________

下面三种说法，其中不正确的有个。（C还有必要条件）

①

Hall定理是二部图G（V“ V.E）存在完备匹配的充要条件

② 无论是有向图还是无向图，都有判断其是否存在欧拉通路和欧拉回路的充要条件

③ 目前只有判断哈密顿图的充分条件

A 0 B 3 C 1 D 2

2. _______________________________

下面（A）

四种说法，其中正确的有 _____________ 个。

②存在是欧拉图不是哈密顿图的无向图

①存在既是欧拉图又是哈密顿图的无向图

③存在不是欧拉图却是哈密顿图的无向图

④ 存在既不是欧拉图又不是哈密顿图的无向图

D 1

填空

§6.1

3.用GM ,

Q表示二部图G, | X|=n, | V2|=m,记号表示图G为 _________________________

（完全二部图）

§6.4

4・若图G画在平面上使得除顶点处外没有 ____________ 出现，则称G为平面图。（边交叉）

5•卞面的平面图共有 _______ 个面，其中无限面Ro的次数deg （Ro）=

(3, 8)

平而图6-1

_____ o (9)

非连通平而图6-2

应用题：

7. P151-习题6.5

（二部图的应用）

8. P151-习题6.15

（哈密顿图的应用）

9. P152-习题6.18

（欧拉通路或欧拉回路的应用）

10. *P152-习题6.23

（平面图在作色中的应用）

离散CH07复习J

§7.1

1. P165- I 12设n阶连通无向图G（V,Q有m条边，G的生成树有 ____________ 条边，余树有

条边。（n-1, m-n+l）

2. P167-例7.5 （2）画出4个顶点非同构无向树。（2种）

3. P173-习题7.16 （3）画出4个顶点非同构的根树（4种）

下面三条叙述中有 _____ 条正确。（B）

①一阶零图是一棵树 ②只有一片树叶的树在同构意义下只有1种

③ 树中每条边都是桥 ④在树中任意两个不相邻顶点卩U加一条边会形成唯一 -条初级回路

AO B3 C2 D1

计算题

5. （6分）一棵树有2个4度顶点，3个3度顶点，其余都是树叶，则该树有 ________ 片树叶。

（9

＜与P171-习题7.1同类型〉）

解：设该树有x片树叶、n个节点、m条边

贝IJ

度数之和=4X2 + 3X3 + lXx

二

17+x

二

2 + 3 + x = 5+x

二

n~l

（树）=4+x

17+x = 2m

（握手定理）二

2 （4+x） x = 9

6. P171-最小生成树-习题7.8 （b）

7. P173-最佳二元前缀码-习题7. 17

离散CH09

§9.1

1曾是非零实数集，1是L上普通乘法的幺元，蔦对普通乘法，a的逆元是 °

(a-1

或

1/a)

2 n阶单位矩阵是n阶矩阵 ________ 的幺元。(乘法)

3在集合A的幕集P(A)±, _________

是U运算的幺元Cl运算的零元。(0)

_____ 是门运算的幺元U运算的零元。(A)

4 _____

正确。(D)

A减法是自然数集N上的二元运算

C加法是非零实数集R•上的二元运算

5 _____

错误。(C)

A 0是加法的幕等元

C单位矩阵E是矩阵加法的幕等元

B除法是整数集上的二元运算

D㊉是任意集合A的幕集P(A)上的二元运算

B 1是乘法的幕等元

D 0是幕集P(S)上㊉运算的幕等元

6二{0,1}, X表示空串， _________是回文语言， _______ 是镜像语言…(A, D)

A (0n10r |n N} = {l,010, 00100,-}

C {(01)n|n N} = {X,01,0101, -}

B {(TT |n N} = { X , 01, 0011,-}

D {01, 10}