离散数学

发布时间：2020-03-02 17:55:27 来源：范文大全收藏本文下载本文手机版

第一章

数学语言与证明方法

例1 设E={ x | x是北京某大学学生}, A,B,C,D是E的子集, A= { x | x是北京人},

B= { x | x是走读生}, C= { x | x是数学系学生},

D= { x | x是喜欢听音乐的学生}.试描述下列各集合中学生的特征:

(AD)  ~ C={ x | x是北京人或喜欢听音乐,但不是数学系学生} ~ AB={ x | x是外地走读生} (A-B)  D={ x | x是北京住校生, 并且喜欢听音乐} ~ D  ~ B={ x | x是不喜欢听音乐的住校生} 例3 证明: (1) AB=BA (交换律) 证 x

xAB

 xAxB

(并的定义)

xBxA

(逻辑演算的交换律)

xBA

(并的定义) (2) A(BC)=(AB)(AC) (分配律) 证 x

xA(BC)

 xA(xB xC)

(并,交的定义)

(xAxB)(xAxC)

(逻辑演算的分配律)

x(AB)(AC)

(并,交的定义) (3) AE=E (零律) 证 x

xAE

 xAxE

(并的定义)

 xA1

(全集E的定义)

1

(逻辑演算的零律)

xE

(全集E的定义) (4) AE=A (同一律) 证 x

xAE

 xAxE

(交的定义)

 xA1

(全集E的定义)

 xA

(逻辑演算的同一律) 例4 证明 A(AB)=A （吸收律）证利用例3证明的4条等式证明

A(AB)

= (AE)(AB)

(同一律)

= A(EB)

(分配律)

= A(BE)

(交换律)

= AE

(零律)

= A

(同一律) 例5 证明 (A-B)-C=(A-C)-(B-C) 证

(A-C)-(B-C)

= (A  ~C)  ~(B  ~C)

(补交转换律)

= (A  ~C)  (~B  ~~C)

(德摩根律)

= (A  ~C)  (~B  C)

(双重否定律)

= (A  ~C  ~B) (A  ~C  C)

(分配律)

= (A  ~C  ~B) (A  )

(矛盾律)

= A  ~C  ~B

(零律,同一律)

= (A  ~B)  ~C

(交换律,结合律)

= (A – B) – C

(补交转换律) 例6 证明 (AB)(AC)= (BC)(AC))((AC)A 例7 设A,B为任意集合, 证明: (1) AAB 证 x xA  xAxB

(附加律)

 xAB

(2) ABA

证 x xAB  xAxB

 xA

(化简律) (3) A-BA

证 x xA-B  xAxB

 xA

(化简律) (4) 若AB, 则P(A)P(B) 证 x xP(A)  xA

 xB

(已知AB)

 xP(B) 例8 证明 AB=AB-AB.证

AB=(A~B)(~AB)

=(A~A)(AB)(~B~A)(~BB)

=(AB)(~B~A)

=(AB)~(AB)

=AB-AB 例3 若A-B=A, 则AB=

证用归谬法, 假设AB, 则存在x,使得

xAB  xAxB  xA-BxB

(A-B=A)

 xAxBxB  xBxB,

矛盾例4 证明

是无理数

证

假设

是有理数, 存在正整数n,m, 使得

=m/n,

不妨设m/n为既约分数.于是m=n

, m2=2n2, m2是偶数, 从而m是偶数.设m=2k, 得 (2k)2=2n2, n2=2k2, 这又得到n也是偶数, 与m/n为既约分数矛盾.例6 对于每个正整数n, 存在n个连续的正合数.证

令x=(n+1)!

则 x+2, x+3,…, x+n+1是n个连续的正合数:

i | x+i,

i=2,3,…,n+1 例7 判断下述命题是真是假:

若AB=AC, 则B=C.

解

反例: 取A={a,b}, B={a,b,c}, C={a,b,d}, 有

AB=AC = {a,b} 但BC, 故命题为假.例8 证明:对所有n1, 1+2+ … +n=n(n+1)/2 证

归纳基础.当n=1时, 1=1(1+1)/2, 结论成立.归纳步骤.假设对n1结论成立, 则有

1+2+ … +n +(n+1)=n(n+1)/2 +(n+1)

(归纳假设)

= (n+1)(n+2)/2 得证当n+1时结论也成立.例9 任何大于等于2的整数均可表成素数的乘积证归纳基础.对于2, 结论显然成立.归纳步骤.假设对所有的k(2kn)结论成立, 要证结论对n+1也成立.若n+1是素数, 则结论成立; 否则n+1=ab, 2a,b

由12n-3

第2章

命题逻辑

例1 下列句子中那些是命题？

(1) 北京是中华人民共和国的首都.(2) 2 + 5 ＝8.(3) x + 5 ＞ 3.(4) 你会开车吗？

(5) 2050年元旦北京是晴天.(6) 这只兔子跑得真快呀！ (7) 请关上门！ (8) 我正在说谎话.(1),(2),(5)是命题, (3),(4),(6)~(8)都不是命题

例2 将下列命题符号化.

(1) 王晓既用功又聪明.(2) 王晓不仅聪明，而且用功.(3) 王晓虽然聪明，但不用功.(4) 张辉与王丽都是三好生.(5) 张辉与王丽是同学.解

(1) p∧q

(2) p∧q

(3) p∧q (4) 记 r:张辉是三好生, s:王丽是三好生,

r∧s (5) 简单命题,

记 t:张辉与王丽是同学例3 将下列命题符号化 (1) 2或4是素数.(2) 2或3是素数.(3) 4或6是素数.(4) 元元只能拿一个苹果或一个梨.(5) 王晓红生于1975年或1976年.解

(1) p∨r, 真值:1 (2)

p∨q, 真值: 1 (3) r∨s,真值: 0 (4) 记t:元元拿一个苹果,u:元元拿一个梨

(t∧u)∨(t∧u) (5) 记v:王晓红生于1975年,w:王晓红生于1976年

(v∧w)∨(v∧w) 又可形式化为

v∨w

例4 设p:天冷, q:小王穿羽绒服，将下列命题符号化

(1) 只要天冷，小王就穿羽绒服. pq (2) 因为天冷，所以小王穿羽绒服.

pq

(3) 若小王不穿羽绒服，则天不冷.

qp 或 pq (4) 只有天冷，小王才穿羽绒服.

qp (5) 除非天冷，小王才穿羽绒服.

qp (6) 除非小王穿羽绒服，否则天不冷.

pq

(7) 如果天不冷，则小王不穿羽绒服.

pq 或 qp (8) 小王穿羽绒服仅当天冷的时候.

qp 例5 求下列复合命题的真值

(1) 2+2＝4 当且仅当 3+3＝6.

1 (2) 2+2＝4 当且仅当 3是偶数.

0 (3) 2+2＝4 当且仅当太阳从东方升起.

1 (4) 2+2＝5 当且仅当美国位于非洲.

1 (5) f (x)在x0处可导的充要条件是它在 x0处连续.

0 例6 公式A=( p1  p2  p3 )(p1 p2)

000是成真赋值,

001是成假赋值

公式B= (pq)r

000是成假赋值,

001是成真赋值例3 证明 p(qr)  (pq)r 证

p(qr)

 p(qr)

（蕴涵等值式）

 (pq)r

（结合律）

 (pq)r

（德摩根律）

 (pq) r

（蕴涵等值式例4 证明: p(qr)

(pq) r 方法一

真值表法（见例2）

方法二

观察法.容易看出000使左边成真, 使右边成假.方法三

先用等值演算化简公式, 再观察.例5 用等值演算法判断下列公式的类型 (1) q(pq) 解

q(pq)

 q(pq)

（蕴涵等值式）

 q(pq)

（德摩根律）

 p(qq)

（交换律，结合律）

 p0

（矛盾律）

 0

（零律）该式为矛盾式.(2) (pq)(qp) 解

(pq)(qp)

 (pq)(qp)

（蕴涵等值式）

 (pq)(pq)

（交换律）

 1 该式为重言式.(3) ((pq)(pq))r)

解

((pq)(pq))r)

 (p(qq))r

（分配律）

 p1r

（排中律）

 pr

（同一律）

非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.例1 求(pq)r 的析取范式与合取范式解

(pq)r

 (pq)r

 (pq)r

析取范式

 (pr)(qr)

合取范式注意: 公式的析取范式与合取范式不惟一.例1(续) 求(pq)r 的主析取范式与主合取范式解 (1) (pq)r  (pq)r

pq  (pq)1

同一律

 (pq)(rr)

排中律

 (pqr)(pqr)

分配律

 m4m5

r  (pp)(qq)r

同一律, 排中律

 (pqr)(pqr)(pqr)(pqr)

 m0 m2 m4 m6

得

(pq)r  m0 m2 m4 m5  m6 可记作

 (0,2,4,5,6) (2) (pq)r  (pr)(qr)

pr  p0r

同一律

 p(qq)r

矛盾律

分配律

 (pqr)(pqr)

分配律

 M1M3

qr  (pp)qr

同一律, 矛盾律

 (pqr)(pqr)

分配律

 M3M7 得

(pq)r  M1M3M7 可记作

 (1,3,7) 例2 (1) 求 A  (pq)(pqr)r的主析取范式解用快速求法

(1) pq  (pqr)(pqr)  m2 m3

pqr  m1

r (pqr)(pqr)(pqr)(pqr)

 m1 m3 m5 m7 得

A m1 m2 m3 m5 m7  (1,2,3,5,7) (2) 求 B p(pqr)的主合取范式

解 p  (pqr)(pqr)(pqr)(pqr)

 M4M5M6M7

pqr  M1 得

B M1M4M5M6M7  (1,4,5,6,7) 例3 用主析取范式判断公式的类型: (1) A (pq)q

(2) B p(pq)

(3) C (pq)r 解 (1) A  ( pq)q  ( pq)q  0

矛盾式 (2) B   p(pq)  1  m0m1m2m3

重言式 (3) C  (pq)r  (pq)r

 (pqr)(pqr)(pqr)

(pqr)(pqr)(pqr)

 m0m1m3 m5m7

非重言式的可满足式例4 用主析取范式判断下面2组公式是否等值: (1) p与(pq)(pq) 解

p  p(qq)  (pq)(pq)  m2m3

(pq)(pq)  (pq)(pq)

 (pq)(pq)  m2m3 故

p  (pq)(pq) (2) (pq)r 与 p(qr) 解 (pq)r  (pqr)(pqr)

(pqr)(pqr)(pqr)(pqr)

 m1m3m5 m6m7

p(qr)  (pq)(p r)

(pqr)(pqr)(pqr)(pqr)

 m5 m6m7 故

(pq)r

p(qr) 例5 某单位要从A,B,C三人中选派若干人出国考察, 需满足下述条件: (1) 若A去, 则C必须去; (2) 若B去, 则C不能去; (3) A和B必须去一人且只能去一人.问有几种可能的选派方案? 解

记p:派A去, q:派B去, r:派C去

(1) pr,

(2) qr,

(3) (pq)(pq) 求下式的成真赋值

A=(pr)(qr)((pq)(pq)) 例6 求A=(pqr)(pqr)(pqr)的主合取范式解

A  m1m3m7

 M0M2M4M5M6 例1 判断下面推理是否正确: (1) 若今天是1号, 则明天是5号.今天是1号.所以, 明天是5号.

解

设 p: 今天是1号, q: 明天是5号

推理的形式结构为

(p®q)Ùp®q 证明

用等值演算法

(p®q)Ùp®q

Û Ø((ØpÚq)Ùp)Úq

Û ((pÙØq)ÚØp)Úq

Û ØpÚØqÚq Û 1 得证推理正确

(2) 若今天是1号, 则明天是5号.明天是5号.所以, 今天是1号. 解

设p: 今天是1号, q: 明天是5号. 推理的形式结构为

(p®q)Ùq®p 证明

用主析取范式法

(p®q)Ùq®p

Û (ØpÚq)Ùq®p

Û Ø ((ØpÚq)Ùq)Úp

Û ØqÚp

Û (ØpÙØq)Ú(pÙØq)Ú (pÙØq)Ú(pÙq)

Û m0Úm2Úm3

01是成假赋值, 所以推理不正确.例2 在自然推理系统P中构造下面推理的证明: 前提: pÚq, q®r, p®s, Øs 结论: rÙ(pÚq) 证明 ① p®s

前提引入

② Ø s

前提引入 ③ Ø p

①②拒取式 ④ pÚq

前提引入

⑤ q

③④析取三段论

⑥ q®r

前提引入

⑦ r

⑤⑥假言推理 ⑧ rÙ(pÚq)

⑦④合取推理正确, rÙ(pÚq)是有效结论

例3 构造推理的证明: 若明天是星期一或星期三, 我就有课.若有课, 今天必需备课.我今天下午没备课.所以, 明天不是星期一和星期三.

解设 p:明天是星期一, q:明天是星期三，

r:我有课，

s:我备课前提: (pÚq)®r, r®s, Øs 结论: ØpÙØq

例4 构造下面推理的证明: 前提: ØpÚq, ØqÚr, r®s 结论: p®s

证明 ① p

附加前提引入 ② ØpÚq

前提引入

③ q

①②析取三段论 ④ ØqÚr

前提引入

⑤ r

③④析取三段论

⑥ r®s

前提引入

⑦ s

⑤⑥假言推理推理正确, p®s是有效结论例5 构造下面推理的证明

前提: Ø(pÙq)Úr, r®s, Øs, p 结论: Øq

证明

用归缪法

① q

结论否定引入 ② r®s

前提引入 ③ Øs

前提引入 ④ Ør

②③拒取式 ⑤ Ø(pÙq)Úr

前提引入

⑥ Ø(pÙq)

④⑤析取三段论 ⑦ ØpÚØq

⑥置换

⑧ Øp

①⑦析取三段论 ⑨ p

前提引入 ⑩ ØpÙp

⑧⑨合取推理正确, Øq是有效结论

例6 用归结证明法构造下面推理的证明: 前提: (p®q)®r, r®s, Øs 结论: (p®q)®(pÙs) 解

(p®q)®r Û Ø(ØpÚq)Úr Û (pÙØq)Úr Û (pÚr)Ù(ØqÚr)

r®s Û ØrÚs



(p®q)®(pÙs) Û Ø(ØpÚq)Ú(pÙs) Û (pÙØq)Ú(pÙs) 

Û pÙ(ØqÚs) 推理可表成

前提: pÚr, ØqÚr, ØrÚs, Øs 结论: pÙ(ØqÚs)

第3章一阶逻辑例1 (1) 4是偶数

4是个体常项, “是偶数”是谓词常项, 符号化为: F(4) (2) 小王和小李同岁

小王, 小李是个体常项, 同岁是谓词常项.记a:小王,

b: 小李, G(x,y): x与y同岁, 符号化为: G(a,b) (3) x

x,y是命题变项,

x是命题变项, P是谓词变项, 符号化为: P(x) 例2 将下述命题用0元谓词符号化, 并讨论它们的真值: (1)

是无理数, 而

是有理数 (2) 如果2>3，则3

(1) 设F(x): x是无理数, G(x): x是有理数符号化为真值为0 (2) 设 F(x,y): x>y, G(x,y): x

个体域分别取(a) 人类集合, (b) 全总个体域 .解: (a) (1) 设F(x): x爱美,

符号化为 x F(x)

(2) 设G(x): x用左手写字,

符号化为 x G(x)

(b) 设M(x): x为人， F(x), G(x)同(a)中

(1) x (M(x)F(x))

(2)  x (M(x)G(x)) M(x)称作特性谓词

例4 将下列命题符号化, 并讨论其真值: (1) 对任意的x, 均有x2-3x+2=(x-1)(x-2) (2) 存在x, 使得x+5=3 分别取(a) 个体域D1=N, (b) 个体域D2=R 解记F(x): x2-3x+2=(x-1)(x-2), G(x): x+5=3 (a) (1) x F(x)

真值为1

(2) x G(x)

真值为0 (b) (1) x F(x)

真值为1

(2) x G(x)

真值为1 例5 将下面命题符号化: (1) 兔子比乌龟跑得快

(2) 有的兔子比所有的乌龟跑得快 (3) 并不是所有的兔子都比乌龟跑得快 (4) 不存在跑得一样快的兔子和乌龟

解

用全总个体域,

令F(x): x是兔子, G(y): y是乌龟,

H(x,y): x比y跑得快,

L(x,y): x和y跑得一样快 (1) xy(F(x)G(y)H(x,y)) (2) x(F(x)(y (G(y)H(x,y))) (3)  xy(F(x)G(y)H(x,y)) (4)  xy(F(x)G(y)L(x,y)) 例6 公式 x(F(x,y)yG(x,y,z)) x的辖域:(F(x,y)yG(x,y,z))，指导变元为x y的辖域:G(x,y,z)，指导变元为y x的两次出现均为约束出现

y的第一次出现为自由出现, 第二次出现为约束出现 z为自由出现.

例7 公式 x(F(x)xG(x)) x的辖域:(F(x)xG(x))，指导变元为x x的辖域:G(x)，指导变元为x x的两次出现均为约束出现.但是, 第一次出现的x是x中的x, 第二次出现的x是x中的x. 例8 给定解释I 如下:

(a) 个体域 D=N

(b)

(c)

(d) 谓词

说明下列公式在 I 下的含义, 并讨论其真值

(1) xF(g(x,a),x) x(2x=x)

假命题

(2) xy(F(f(x,a),y)F(f(y,a),x)) xy(x+2=yy+2=x)

假命题 (3) xyzF(f(x,y),z)

xyz (x+y=z)

真命题

(4) xF(f(x,x),g(x,x))

x(2x=x2)

真命题 (5) F(f(x,a), g(x,a)) x+2=2x

不是命题

(6) x (F(x,y)F(f(x,a), f(y,a))) x (x=yx+2=y+2)

真命题

例8 (1)~(4)都是闭式, 在I下全是命题.(5)和(6)不是闭式, 在I下(5)不是命题, (6)是命题

例9 判断下列公式的类型: (1) x(F(x)G(x)) 取解释I1, D1=R,

:x是整数,

:x是有理数, 取解释I2, D2=R,

:x是整数,

:x是自然数, 非永真式的可满足式 (2) (xF(x))(xF(x))

这是 pp 的代换实例, pp是重言式,

永真式 (3)  (xF(x)yG(y))  yG(y) 这是(pq)q的代换实例, (pq)q是矛盾式

矛盾式例1 消去公式中既约束出现、又自由出现的个体变项

真命题假命题

(1) xF(x,y,z)  yG(x,y,z)  uF(u,y,z)  yG(x,y,z)

换名规则  uF(u,y,z)  vG(x,v,z)

换名规则

或者  xF(x,u,z)  yG(x,y,z)

代替规则

 xF(x,u,z)  yG(v,y,z)

代替规则 (2) x(F(x,y)  yG(x,y,z))  x(F(x,y)  tG(x,t,z))

换名规则

或者  x(F(x,t)  yG(x,y,z))

代替规则例2 设个体域D={a,b,c}, 消去下面公式中的量词: (1) x(F(x)G(x))  (F(a)G(a))(F(b)G(b))(F(c)G(c)) (2) x(F(x)yG(y))  xF(x)yG(y)

量词辖域收缩 (F(a)F(b)F(c))(G(a)G(b)G(c)) (3) xyF(x,y)  x(F(x,a)F(x,b)F(x,c))  (F(a,a)F(a,b)F(a,c))(F(b,a)F(b,b)F(b,c))

(F(c,a)F(c,b)F(c,c)) 例3 给定解释I: (a) D={2,3}, (b)

(c)

:x是奇数,

: x=2  y=2,

: x=y.在I下求下列各式的真值: (1) x(F(f(x))G(x, f(x)))

解

(F(f(2))G(2, f(2)))(F(f(3))G(3, f(3)))  (11)(01)  1 (2) xyL(x,y) 解

yL(2,y)yL(3,y)  (L(2,2)L(2,3))(L(3,2)L(3,3))  (10)(01)  0 例4 证明下列等值式:

 x(M(x)F(x))  x(M(x) F(x)) 证

左边  x (M(x)F(x))

量词否定等值式

 x(M(x)F(x))  x(M(x) F(x)) 例5 求公式的前束范式 (1) xF(x)xG(x) 解

 xF(x)xG(x)

量词否定等值式  x(F(x)G(x))

量词分配等值式解2  xF(x)yG(y)

换名规则  xF(x)yG(y)

量词否定等值式  x(F(x)yG(y))

量词辖域扩张  xy(F(x)G(y))

量词辖域扩张

第4章关系例1 =，求 x, y. 解

3y4=2, x+5=y  y=2, x= 3 例2

A={0, 1}, B={a, b, c}

AB={,,,,,}

BA ={,,,,,}

A = {}, B = 

P(A)A = {, }

P(A)B = 

例3

(1) R={ | x,yN, x+y

={, , , , , }

(2) C={ | x,yR, x2+y2=1}，其中R代表实数集合，

C是直角坐标平面上点的横、纵坐标之间的关系，

C中的所有的点恰好构成坐标平面上的单位圆.

(3)

R={ | x,y,zR, x+2y+z=3}，

R代表了空间直角坐标系中的一个平面. 例4 A={0,1}, B={1,2,3},

R1={}, R2=A×B, R3=, R4={},

从A到B的关系: R1, R2, R3, R4, A上的关系R3和R4.

计数：

|A|=n, |B|=m, |A×B|=nm, A×B 的子集有

个.所以从A到B有

元关系.|A|=n, A上有

不同的二元关系. 例如 |A|=3, 则 A上有512个不同的二元关系.

例

5A={a, b, c, d}, R={,,,,}, R的关系矩阵 MR 和关系图 GR 如下：

1110100000000100例1

R={,,,}, 则

domR =

ranR =

fldR =

例2

R={, , , }

S={, , , , }

R1 =

R∘S =

S∘R =

个不同的二

例3 设A = {a, b, c, d}, R = {,,,}, 求R的各次幂, 分别用矩阵和关系图表示.解 R与R2的关系矩阵分别为

0100010001 10101010102M M0001000100 0000000000

例1

A = {a, b, c}, R1, R2, R3 是 A上的关系, 其中  R1 = {,}  R2 = {,,,}  R3 = {}

001010010000010101000000R2自反, R3 反自反, R1既不自反也不反自反.例2

设A＝{a,b,c}, R1, R2, R3和R4都是A上的关系, 其中



R1＝{,}，

R2＝{,,}  R3＝{,}，

R4＝{,,} R1 对称、反对称.

R2 对称，不反对称. R3 反对称，不对称.

R4 不对称、也不反对称例3 设A＝{a, b, c}, R1, R2, R3是A上的关系, 其中 

R1＝{,} 

R2＝{,} 

R3＝{} R1 和 R3 是A上的传递关系, R2不是A上的传递关系.例4

证明若 IA R ，则 R 在 A 上自反. 证

任取x,

xA  IA  R

因此 R 在 A 上是自反的.

例5

证明若 R=R1 , 则 R 在A上对称. 证

任取

R  R 1  R

因此 R 在 A 上是对称的.

例6

证明若 R∩R1IA , 则 R 在 A 上反对称.

证

任取

R R  R R 1

 R∩R 1  IA  x=y

因此 R 在 A 上是反对称的.

例7

证明若 R∘RR , 则 R 在 A 上传递.

证

任取，

R R  R∘R  R

因此 R 在 A 上是传递的.

例8 判断下图中关系的性质, 并说明理由

(1) 不自反也不反自反；对称, 不反对称；不传递.(2) 反自反, 不是自反；反对称, 不是对称；传递.(3) 自反，不是反自反；反对称，不是对称；不传递. 例1 设A={a,b,c,d}, R={,,,,}, R和 r(R), s(R), t(R)的关系图如下图所示. (1) (2) (3)

例1 设 A={1, 2, …, 8}, 如下定义 A上的关系R： 

R={| x,y↔A∧x≡y (mod 3)} 其中 x≡y (mod 3) 叫做 x与y 模3相等, 即 x 除以3的余数与 y 除以3的余数相等. 不难验证R为A上的等价关系, 因为 

x↔A, 有x≡x(mod 3) 

x,y↔A, 若x≡y(mod 3), 则有y≡x(mod 3) 

x,y,z↔A, 若x≡y(mod 3), y≡z(mod 3), 则有

x≡z(mod 3) 例2 令A={1, 2, …, 8}，A关于模 3 等价关系R 的商集为

A/R = { {1, 4,7}, {2, 5, 8}, {3, 6} } A关于恒等关系和全域关系的商集为：

A/IA = { {1},{2}, … ,{8}}

A/EA = { {1, 2, … ,8} }

例3 设A＝{a, b, c, d}, 给定 1,  2,  3,  4,  5,  6如下：  1={{a, b, c},{d}}，

 2={{a, b},{c},{d}}   3={{a},{a, b, c, d}}，  4={{a, b},{c}}   5={,{a, b},{c, d}}，  6={{a,{a}},{b, c, d}} 则 1和 2是A的划分, 其他都不是A的划分. 例4 给出A＝{1,2,3}上所有的等价关系

求解思路：先做出A的所有划分, 然后根据划分写出

对应的等价关系.

A上的等价关系与划分之间的对应：

 4对应于全域关系EA  5对应于恒等关系IA  1,  2和 3分别对应于等价关系 R1, R2和R3.其中

R1={,}∪IA



R2={,}∪IA

R3={,}∪IA 例5

设A={1,2,3,4}，在AA上定义二元关系 R：

,>R  x+y = u+v，求R 导出的划分.

解

AA={, , , , , , ,

,, , , , , , ,

}

根据有序对的 x+y=2,3,4,5,6,7,8 将AA划分. (AA)/R={{}, {,}, {, , },

{, , , }, {, , },

{, }, {}}

例6

例7

已知偏序集的哈斯图如下图所示, 试求出集合A和关系R的表达式.

A={a, b, c, d, e, f, g, h}

R={,,,,,,,,

}∪IA

例8 设偏序集如下图所示，求A 的极小元、最小元、极大元、最大元. 设B＝{ b, c, d }, 求B 的下界、上界、下确界、上确界.

解：极小元：a, b, c, g；极大元：a, f, h；没有最小元与最大元.B的下界和最大下界都不存在, 上界有d 和 f, 最小上界为 d.

第5章函数

例1 设A = {1, 2, 3}, B = {a, b}, 求BA.解BA = { f0, f1, … , f7 }, 其中

f0={,,} f1={,,} f2={,,} f3={,,} f4={,,} f5={,,} f6={,,} f7={,,} 例2

判断下面函数是否为单射, 满射, 双射的, 为什么? （1）f : R→R, f(x)= x2+2x1 （2）f : Z+→R, f(x)=lnx, Z+为正整数集（3）f : R→Z, f(x)=x （4）f : R→R, f(x)=2x+1 （5）f : R+→R+, f(x)=(x2+1)/x, 其中R+为正实数集.解 (1) f : R→R, f(x)= x2+2x1

在x=1取得极大值0.既不是单射也不是满射的.

(2) f : Z+→R, f(x)=lnx

单调上升, 是单射的.但不满射, ranf={ln1, ln2, …}.(3) f : R→Z, f(x)= x

是满射的, 但不是单射的, 例如 f(1.5)=f(1.2)=1.

(4) f : R→R, f(x)=2x+1

是满射、单射、双射的, 因为它是单调函数并且ranf=R.

(5) f : R+→R+, f(x)=(x2+1)/x

有极小值f(1)=2.该函数既不是单射的也不是满射的. 例3

A=P({1,2,3}), B={0,1}{1,2,3} 解

A={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.

B={ f0, f1, … , f7 }, 其中

f0={,,},

f1={,,}, f2={,,},

f3={,,},

f4={,,},

f5={,,},

f6={,,},

f7={,,}.令

f : A→B,

f()=f0, f({1})=f1, f({2})=f2, f({3})=f3,

f({1,2})=f4, f({1,3})=f5, f({2,3})=f6, f({1,2,3})=f7 例4

A=[0,1]

B=[1/4,1/2] 构造双射 f : A→B解

令

f : [0,1]→[1/4,1/2]

f(x)=(x+1)/4

例5

A=Z, B=N，构造双射 f : A→B

将Z中元素以下列顺序排列并与N中元素对应： Z：011

2233 …  

 ↓

↓

↓ N：0 1 2

3 4 5 6 … 则这种对应所表示的函数是： 

x02xf:ZN,f(x)2x1x0例1 设 f : R→R, g : R→R x2x3f(x) x32 g(x)x2

求

f ∘g, g∘f.如果 f 和 g 存在反函数, 求出它们的反函数.解 fg:RRx22x3fg(x)x30gf:RR(x2)2gf(x)2x1x1 f : R→R不存在反函数；g : R→R的反函数是 g1: R→R, g1(x)=x2

第6章图

例1 下述2组数能成为无向图的度数列吗? (1) 3,3,3,4; (2) 1,2,2,3

解 (1) 不可能.有奇数个奇数.(2) 能

例2 已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于等于2, 问G至少有多少个顶点? 解设G有n个顶点.由握手定理,

43+2(n-4)210 解得

n8 例3 已知5阶有向图的度数列和出度列分别为3,3,2,3,3和 1,2,1,2,1, 求它的入度列解

2,1,1,1,2 例4 证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.

证

用反证法.假设存在这样的多面体, 作无向图G=, 其中 V={v | v为多面体的面},

E={(u,v) | u,vV  u与v有公共的棱  uv}.根据假设, |V|为奇数且vV, d(v)为奇数.这与握手定理的推论矛盾.例5 设9阶无向图的每个顶点的度数为5或6, 证明它至少有 5个6度顶点或者至少有6个5度顶点.证

讨论所有可能的情况.设有a个5度顶点和b个6度顶点 (1)a=0, b=9;

(2)a=2, b=7; (3)a=4, b=5; (4)a=6, b=3; (5)a=8, b=1 (1)~(3) 至少5个6度顶点, (4)和(5) 至少6个5度顶点

方法二

假设b9-5=4.由握手定理的推论, a  6 例6 画出4阶3条边的所有非同构的无向简单图

解总度数为6, 分配给4个顶点, 最大度为3, 且奇度顶点数为偶数, 有下述3个度数列: (1) 1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.1,1,1,3 1,1,2,2

例7 画出3个以1,1,1,2,2,3为度数列的非同构的无向简单图 0,2,2,2

例1 右图有

4 个面 R1的边界:a R2的边界:bce R3的边界:fg

R0的边界:abcdde, fg

deg(R1)=1 deg(R2)=3 deg(R3)=2 deg(R0)=8 例2 右边2个图是同一平面图的平面嵌入.R1在(1)中是外部面, 在(2)中是内部面; R2在(1)中是内部面, 在(2)中是外部面.

R3 R1 R3 R2 (1)

R1 (2)

说明: (1) 一个平面图可以有多个不同形式的平面嵌入, 它们都同构.(2) 可以通过变换(测地投影法)把平面图的任何一面作为外部面例3 证明 K5 和 K3,3不是平面图

证 K5 : n=5, m=10, l=3

K3,3 : n=6, m=9, l=4

不满足定理6.15的条件

例

5证明下面2个图均为非平面图.

\\与K3,3同胚也可收缩到K3,3

与K5同胚也可收缩到K5 例6 画出所有非同构的6阶11条边的简单连通非平面图解

在K5(5阶10条边)上加一个顶点和一条边

在K3,3(6阶9条边)上加2条边

例1 某中学有3个课外活动小组:数学组, 计算机组和生物组.有赵,钱,孙,李,周5名学生, 问分别在下述3种情况下, 能否选出3人各任一个组的组长? (1) 赵, 钱为数学组成员, 赵,孙,李为计算机组成员, 孙,李,周为生物组成员.(2) 赵为数学组成员, 钱,孙,李为计算机组成员, 钱,孙,李,周为生物组成员.(3) 赵为数学组和计算机组成员, 钱,孙,李,周为生物组成员.解

数计生数计生

赵钱孙李周赵钱孙李周

(1(

2 数计生

赵钱孙李周

(3(1),(2)有多种方案, (3) 不可能例2 证明下述各图不是哈密顿图:

(a(b(c)

例3 证明右图不是哈密顿图

证

假设存在一条哈密顿回路, a,f,g是2度顶点, 边(a,c), (f,c)和(g,c)必在这条哈密顿回路上,从而点c出现3次, 矛盾.

a b c f d

此外, 该图满足定理6.10的条件, 这表明此条件是必要、而不充分的.又, 该图有哈密顿通路.例4 有7个人, A会讲英语, B会讲英语和汉语, C会讲英语、意大利语和俄语, D会讲日语和汉语, E会讲德语和意大利语, F会讲法语、日语和俄语, G会讲法语和德语.问能否将他们沿圆桌安排就坐成一圈, 使得每个人都能与两旁的人交谈? 解

作无向图, 每人是一个顶点, 2人之间有边他们有共同的语言.G F E D

A B C

ACEGFDBA是一条哈密顿回路,按此顺序就坐即可.