离散数学-习题课

第3/次习题课

习题课 单老师

例1 图11.3.8给定加权连通图，其中V={v1,v2,v3,v4,v5,v6}，E={[v1,v2],[v1,v5],

[v2,v3],[v2,v6],[v2,v5],[v3,v4],[v3,v6],[v4,v5],[v4,v6],[v5,v6]}和W={3,1,2,1,3,2,3,4,1,2}。

解 令x0=v1，按G.Dantzig算法可得到下面的结点和边序列：

v1,v5,v6,v2,v4,v3

[v1,v5], [v5,v6], [v1,v2], [v6,v4], [v2,v3]

所求生成树如图11.3.9所示。

前面讨论的树，都是无向图中的树，即无向树；下面将简单地介绍有向图中的树即有向树。

定义11.3.6 如果一个有向图的基础图是一棵树，则该有向图称为有向树。其图形表示法常采用倒置树表示之，且为方便计，有时略去边之方向。

例2 图11.2.2中(a)的一个最大匹配是{[v1,v2],[v3,v9],[v5,v6],[v7,v8]}；(b)的一个完全匹配是{[v1,v2],[v3,v4],[v5,v6],[v7,v8]}。

例题 3 设A为简单图G的邻接矩阵，则Al中的i行j列元素alij等于G中联结vi到vj的长度为l的链(或路)的数目。

证明 对l施行归纳证明之。

当l=1时，Al=A1=A，定理显然为真。

假设当l=k时定理成立，考察l=k+1的情形。由于

Ak+1=Ak·A

即有

1kija=nrrjkiraa1 (1)

根据归纳假设和邻接矩阵的定义可知，kira是联结vi到vr长度为k的链（或路）的数目，arj是联结vr到vj长度为1的链（或路）的数目（实际上这是从vr到vj的一条边（或弧）。因此，(1)式右 图11.3.8 图11.3.9 端的每项表示由vi经过一条长度为k的链（或路）到vr，再由vr经过一条边（或弧）到vj的总长度为k+1的链（或路）的数目。对r求和，即得1kija，它是所有从vi到vj长度为k+1的链（或路）的数目。故定理得证。

1 第一章 命题演算基础

1.1 判断下列语句是否为命题，若是请翻译为符号公式；若不是说明由。

（1）请给我一支笔！

（2）火星上有生物。

（3）8YX

（4）只有努力工作，方能把事情做好。

（5）如果嫦娥是虚构的，而圣诞老人也是虚构的，那么许多孩子受骗了。

解

（1）不为命题，因为它不是陈述句。

（2）是命题，用命题变元P表示该命题。

（3）不为命题，虽为陈述句，但不能判断其真假性。

（4）是命题。设P表示努力工作，Q表示把事情做好，则原句翻译为命题公式PQ。

（5）是命题。设P表示嫦娥是虚构的，Q表示圣诞老人也是虚构的，R表示许多孩子受骗了，则原句翻译为RQP)(。

1.2 试判定下列公式的永真性和可满足性。

（1）))(()(RQPQP

解

（1）当TP时，

原式=))(()(RQTQT

=))((RQFQ

=FQ

=Q

当Q=T时，上式=F；当FQ时，上式=T，因此公式存在成真解释),,(),,(FTRQP，存在成假解释),,(),,(TTRQP，故公式可满足，但非永真。

（2）))(()(PRQQP

解

当TP时

原式=))(()(TRQQT

2 =))((FRQQ

=)((RQQ

当Q=T时

上式=)(RTT

=RF

=F

当Q=F时

上式=)(RFF

=RT

=R

=R

当TR时，上式=T，因此公式存在成真解释),,(),,(TFTRQP，存在成假解释),,(),,(TTRQP，故公式可满足，但非永真。

（3）))(()(PRQQP

解

当TP时

原式=))(()(TRQQT

精品文档

. 1-1，1-2

（1） 解：

a) 是命题，真值为T。

b) 不是命题。

c) 是命题，真值要根据具体情况确定。

d) 不是命题。

e) 是命题，真值为T。

f) 是命题，真值为T。

g) 是命题，真值为F。

h) 不是命题。

i) 不是命题。

（2） 解：

原子命题：我爱北京天安门。

复合命题：如果不是练健美操，我就出外旅游拉。

（3） 解：

a) (┓P ∧R)→Q

b) Q→R

c) ┓P

d) P→┓Q

（4） 解：

a)设Q:我将去参加舞会。R:我有时间。P:天下雨。

Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。

b)设R:我在看电视。Q:我在吃苹果。

R∧Q:我在看电视边吃苹果。

c) 设Q:一个数是奇数。R:一个数不能被2除。

（Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。

(5) 解：

a) 设P：王强身体很好。Q：王强成绩很好。P∧Q

b) 设P：小李看书。Q：小李听音乐。P∧Q

c) 设P：气候很好。Q：气候很热。P∨Q 精品文档

. d) 设P： a和b是偶数。Q：a+b是偶数。P→Q

e) 设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。PQ

f) 设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R

(6) 解：

a) P:天气炎热。Q:正在下雨。 P∧Q

b) P:天气炎热。R:湿度较低。 P∧R

c) R:天正在下雨。S:湿度很高。 R∨S

d) A:刘英上山。B:李进上山。 A∧B

e) M:老王是革新者。N:小李是革新者。 M∨N

f) L:你看电影。M:我看电影。 ┓L→┓M

g) P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R

h) P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q

1-3

（1）解：

a) 不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式）

..

Word资料. 习题1.1

1、 用列举法给出下列集合：

a) 小于5的非负整数的集合；

b) 10到20之间的素数的集合；

c) 不超过65的12之正整数倍数的集合。

2、 用命题法给出下列集合：

a) 不超过100的自然数的集合；

b) Ev和Od；

c) 10的整倍数的集合。

3、 用归纳定义法给出下列集合：

a) 允许有前0的十进制无符号整数的集合；

b) 不允许有前0的十进制无符号整数的集合；

c) 允许有前0和后0的有有限小数部分的十进制无符号实数的集合；

d) 不允许有前0的十进制无符号偶数的集合；

e) Ev和Od；

f) 集合{0，1，4，9，16，25，…}。

4、 确定下列集合中哪些是相等的：

A={x|x为偶数且x2为奇数}

B={x|有y∈I使x=2y}

C={1，2，3}

D={0，2，-2，5，-3，4，-4}

E={2x|x∈I}

F={3，3，2，1，2}

G={x|有x∈I且x3-6x2-7x-6=0}

5、 确定下列关系中哪些是正确的，并简单说明理由。

a) 

b) 

c) {}

d) {}

e) {a, b}{a, b, c,{a, b, c}}

f) {a, b}{a, b, c,{a, b, c}}

g) {a, b}{a, b,{a, b}}

h) {a, b}{a, b,{a, b}}

6、 设A、B和C为集合。证明或用反例推翻以下的各个命题：

a) 若AB且BC，则AC。

b) 若AB且BC，则AC。

c) 若AB且BC，则AC。

d) 若AB且BC，则AC。

7、 若A、B为集合，则AB与AB能同时成立吗？请证明你的结论。

8、 列举出下列集合中每个集合的所有子集：

a) {1，2，3}

b) {1，{2，3}}

c) {{1，{2，3}}}