离散数学试题及解答

第二章习题一

1、指出下列公式∀x∃y(F(x,y)∧G(y,z)) ∨∃xH(x,y,z)中的指导变元，量词的辖域，各个体

变项的自由出现和约束出现。

解：全称量词的指导变元为x，第一个存在量词的指导变元为y，第2个存在量词的指

导变元为x。

在∀x∃y(F(x,y) ∧G(y,z))中约束变元为x与y，自由变元为z。

在∃xH(x,y,z)中的约束变元为x，自由变元为y,z。

2、给定解释I如下：

(a)个体域为实数集R；

(b)特定元素a=0；

(c)函数f(x,y)=x-y，x与y为实数。

(d)谓词F(x,y)为x=y，G(x,y)为x

给出下列公式在解释I下的真值。

(1) ∀x ∀y(F(f(x,y),a) →G(x,y))

(2) ∀x ∀y(G(f(x,y),a) →F(x,y))

(1) ∀x ∀y(F(f(x,y),a) →G(x,y))

解：原式=∀x ∀y(F(x-y,0) → G(x,y))

=∀x∀y(x-y=0 → x

当x-y=0为1时，x

故此式的值为0。

(1) ∀x ∀y(G(f(x,y),a) →F(x,y))

=∀x ∀y(G(x-y,0) →F(x,y))

=∀x ∀y((x-y<0) →x=y)

当x-y<0即x

故此式的值为0。

3、给定解释I如下：

(a)个体域D=自然数N；

(b)特定元素a=2；

(c)函数f(x,y)=x+y，g(x,y)=x*y；

(d)谓词F(x,y)为x=y；

给出下列各式在I下的解释，并讨论它们的真值：

(1) ∀x∀y(F(f(x,a),y) →F(f(y,a),x))

(2) ∃x(F(f(x,x),g(x,x)))

(1) ∀x∀y(F(f(x,a),y) →F(f(y,a),x))

=∀x∀y(F(f(x,2),y) →F(f(y,2),x))

=∀x∀y(F(x+2,y) →F(y+2,x))

=∀x∀y((x+2=y) →(y+2=x))

应用离散数学 图论

§5.2 图的连通性

习题5.2

1．证明或否定：

（1）简单图G

中有从点u

到点v

的两条不同的通路，则G

中有基本回路。

（2）简单图G

中有从点u

到点v

的两条不同的基本通路，则G

中有基本回路。

解：（1）简单图G

中有从点u

到点v

的两条不同的通道，则G

中有回路。

（2）简单图G

中有从点u

到点v

的两条不同的路，则G

中有回路。

解 （1）不一定：如下图，点1与点3之间有两条通道：（1、2、3）和（1、2、1、2、3），

但图中没有回路。

（2）一定：设两条路分别为),,,,,(

211vxxxuL

m

和),,,,,(

212vyyyuL

n

。若对

mi1

，nj1

有

jiyx

，则),,,,,,,,,,(

12121uyyyyvxxxu

nnm

是一条回路。否

则假设

lkyx

且是离u

最近的一对（即对ki1

，lj1

，不存在

jiyx

），则

),,,,,,,,,(

12121vyyyxxxu

lk

是一条回路。

2．设G

是简单图，)(G

≥2

，证明G

中存在长度大于或等于1)(G

的基本回路。

证：以图G中一点v

1出发，与之相邻的点设为v

2，由于)(G

≥2

，则v

2至少还有一个邻

接点，设为v

3，若v

3与v

1邻接，则形成长度为1)(G

的基本回路，则若v

3不与v

1邻接，

则至少还有一个邻接点，设为v

4，若v

4与v

1或v

2邻接，则形成长度为大于或等于1)(G

的

基本回路，若v

4与v

1和v

2都不邻接，至少还有一个邻接点，设为v

5，…，依次类推，一定可

以到达最后一个顶点v

i，由于)(G

≥2

，则除了v

i-1外，一定会与前面的某个顶点邻接，就

会形成长度为大于或等于1)(G

的基本回路。

3．证明：若连通图G

不是完全图，则G

中存在三个点wvu，，

，使Evu)(，

，Ewv)(，

，

Ewu)(，

。

证明：用反证法，假设图G中任意的三个点都有Evu)(，

，Ewv)(，

，(u，w)∈E

, 应用离散数学 图论

国开电大《离散数学》形考任务一

参考答案

单项选择题

试题1

若集合A的元素个数为10

,

则其幕集的元素个数为().

选择一

项：

A.

l

B.100

C.1024

D.10

正确答案是：1024

试题2

集合A={l,2, 3, 4, 5, 6, 7, 8}上的关系R={ I x+y=lO且x,yA}, 则R

的性质为().

选择一

项：

A反自反且传递的

B对称的

C自反的

D传递且对称的

正确答案是：对称的

试题3

设集合A={l,2, 3}, 8={3, 4, S}, C={S, 6, 7}, 则AUB -C =(

). 一、公式翻译题（每小题

4分，共

16分）

1.将语句 “

我会英语， 并且会德语．

“翻译成命题公式．

答： 设P: 我会头语Q: 我会德语

则命题公式为P/\Q

2.将语句 “

如果今天是周三， 则昨天是周二． “翻译成命题

公式．

答： 设P: 今天是周三Q: 昨天是周二

则命题公式为： PQ

3.将语句"C3次列车每天上午9点发车或者10点发车”

翻

译成命题公式．

答： 设

P:

C3次列车每天卜午9点发车

Q: C3次列车每天上午10点发车

则命题公式为: -, C

P仁 Q)

4.将语句 “

小王是个学生， 小李是个职员， 而小张是个军人．

“翻译成命题公式． 答： 设： P: 小王是个学生Q: 小李是个职

员R: 小张是个军人

则命题公式为： p /\Q/\R

二

、计算题（每小题12 分， 共 84 分）

1.设集合A={{a},a, b), B

={a, {b)}, 试计算

(1)AnB;(2)AU 8;(3)A-(AnB)

答：

CI)炉B=

{

a}

(

2)Au B=

{ {a},a,b{

b}}

(3)A-(AnB)={ {

a },

a,

b }-{a}={

a,b}

2设集合

A={2,3, 6, 12, 24, 36

}, B为A的子集，其中

B={6,12

}, R是A上

的整除关系，试

Cl)写出

R的关系表达式；

(2)画出关系

R的哈斯图；

(3)求出

B的最大元、极大元、最小上界．

离散数学尹宝林版第7章作业答案

第七章习题答案2. 试问下列关系中哪个能构成函数：

(1){< x1, x2 > | x1, x2∈N, x1 + x2 <10}

(2){< x, y > | x, y∈R, y = x2}

(3){< x, y > | x, y∈R, y2 = x}

解只有(2)满⾜单值性，能构成函数。6. 设X = {0, 1, 2}，求出X X中的如下函数：

(1)f2(x) = f (x)

(2)f2(x) = x

(3)f3(x) = x

解(1) 任取y∈ran( f )，则有x∈X使得f (x) = y，因⽽f (y) = f2(x) = f (x) = y

若ran( f ) = {0}，则f1 = {< 0, 0 >,< 1, 0 >,< 2, 0 >}。

若ran( f ) = {1}，则f2 = {< 0, 1 >,< 1, 1 >,< 2, 1 >}。

若ran( f ) = {2}，则f3 = {< 0, 2 >,< 1, 2 >,< 2, 2 >}。

若ran( f ) = {0, 1}，则有两个函数f4 = {< 0, 0 >,< 1, 1 >,< 2, 0 >}和

f5 = {< 0, 0 >,< 1, 1 >,< 2, 1 >}。

若ran( f ) = {0, 2}，则有两个函数f6 = {< 0, 0 >,< 1, 0 >,< 2, 2 >}和

f7 = {< 0, 0 >,< 1, 2 >,< 2, 2 >}。

若ran( f ) = {1, 2}，则有两个函数f8 = {< 0, 1 >,< 1, 1 >,< 2, 2 >}和

f9 = {< 0, 2 >,< 1, 1 >,< 2, 2 >}。

若ran( f ) = {0, 1, 2}，则f10必为I X 。所以，共有10个函数满⾜条件。(2) 若f (x) = y≠x，则f (y) = f2(x) = x。集合

{ x | x∈X∧ f (x) ≠x }的元素个数为偶数，可为0或2。若它为0，则f1必为I X 。若它为2，则有三个函数