第一篇：离散数学
第一章
数学语言与证明方法
例1 设E={ x | x是北京某大学学生}, A,B,C,D是E的子集, A= { x | x是北京人}，B= { x | x是走读生}, C= { x | x是数学系学生}，D= { x | x是喜欢听音乐的学生}.试描述下列各集合中学生的特征:
(AD) ~ C={ x | x是北京人或喜欢听音乐,但不是数学系学生} ~ AB={ x | x是外地走读生}(A-B) D={ x | x是北京住校生, 并且喜欢听音乐} ~ D ~ B={ x | x是不喜欢听音乐的住校生} 例3 证明:(1)AB=BA(交换律)证 x
xAB
xAxB
(并的定义)
xBxA
(逻辑演算的交换律)
xBA
(并的定义)(2)A(BC)=(AB)(AC)(分配律)证 x
xA(BC)
xA(xB xC)
(并,交的定义)
(xAxB)(xAxC)
(逻辑演算的分配律)
x(AB)(AC)
(并,交的定义)(3)AE=E(零律)证 x
xAE
xAxE
(并的定义)
xA1
(全集E的定义)
1
(逻辑演算的零律)
xE
(全集E的定义)(4)AE=A(同一律)证 x
xAE
xAxE
(交的定义)
xA1
(全集E的定义)
xA
(逻辑演算的同一律)例4 证明 A(AB)=A（吸收律）证 利用例3证明的4条等式证明
A(AB)
=(AE)(AB)
(同一律)
= A(EB)
(分配律)
= A(BE)
(交换律)
= AE
(零律)
= 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 证明(AB)(AC)=(BC)(AC))((AC)A 例7 设A,B为任意集合, 证明:(1)AAB 证 x xA xAxB
(附加律)
xAB
(2)ABA
证 x xAB xAxB
xA
(化简律)(3)A-BA
证 x xA-B xAxB
xA
(化简律)(4)若AB, 则P(A)P(B)证 x xP(A) xA
xB
(已知AB)
xP(B)例8 证明 AB=AB-AB.证
AB=(A~B)(~AB)
=(A~A)(AB)(~B~A)(~BB)
=(AB)(~B~A)
=(AB)~(AB)
=AB-AB 例3 若A-B=A, 则AB=
证 用归谬法, 假设AB, 则存在x,使得
xAB xAxB xA-BxB
(A-B=A)
xAxBxB xBxB，矛盾 例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 判断下述命题是真是假:
若AB=AC, 则B=C.解
反例: 取A={a,b}, B={a,b,c}, C={a,b,d}, 有
AB=AC = {a,b} 但BC, 故命题为假.例8 证明:对所有n1, 1+2+ … +n=n(n+1)/2 证
归纳基础.当n=1时, 1=1(1+1)/2, 结论成立.归纳步骤.假设对n1结论成立, 则有
1+2+ … +n +(n+1)=n(n+1)/2 +(n+1)
(归纳假设)
=(n+1)(n+2)/2 得证当n+1时结论也成立.例9 任何大于等于2的整数均可表成素数的乘积 证 归纳基础.对于2, 结论显然成立.归纳步骤.假设对所有的k(2kn)结论成立, 要证结论 对n+1也成立.若n+1是素数, 则结论成立;否则n+1=ab, 2a,b 命题逻辑 例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)只要天冷，小王就穿羽绒服.pq(2)因为天冷，所以小王穿羽绒服.pq (3)若小王不穿羽绒服，则天不冷.qp 或 pq(4)只有天冷，小王才穿羽绒服.qp(5)除非天冷，小王才穿羽绒服.qp(6)除非小王穿羽绒服，否则天不冷.pq (7)如果天不冷，则小王不穿羽绒服.pq 或 qp(8)小王穿羽绒服仅当天冷的时候.qp 例5 求下列复合命题的真值 (1)2+2＝4 当且仅当 3+3＝6.(2)2+2＝4 当且仅当 3是偶数.0(3)2+2＝4 当且仅当 太阳从东方升起.(4)2+2＝5 当且仅当 美国位于非洲.(5)f(x)在x0处可导的充要条件是它在 x0处连续.0 例6 公式A=( p1 p2 p3)(p1 p2) 000是成真赋值，001是成假赋值 公式B=(pq)r 000是成假赋值，001是成真赋值 例3 证明 p(qr)(pq)r 证 p(qr) p(qr) （蕴涵等值式） (pq)r （结合律） (pq)r （德摩根律） (pq)r （蕴涵等值式 例4 证明: p(qr) (pq)r 方法一 真值表法（见例2） 方法二 观察法.容易看出000使左边成真, 使右边成假.方法三 先用等值演算化简公式, 再观察.例5 用等值演算法判断下列公式的类型(1)q(pq)解 q(pq) q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律）该式为矛盾式.(2)(pq)(qp)解 (pq)(qp) (pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1 该式为重言式.(3)((pq)(pq))r) 解 ((pq)(pq))r) (p(qq))r （分配律） p1r （排中律） pr （同一律） 非重言式的可满足式.如101是它的成真赋值,000是它的 成假赋值.例1 求(pq)r 的析取范式与合取范式 解 (pq)r (pq)r (pq)r 析取范式 (pr)(qr) 合取范式 注意: 公式的析取范式与合取范式不惟一.例1(续)求(pq)r 的主析取范式与主合取范式 解(1)(pq)r (pq)r pq (pq)1 同一律 (pq)(rr) 排中律 (pqr)(pqr) 分配律 m4m5 r (pp)(qq)r 同一律, 排中律 (pqr)(pqr)(pqr)(pqr) m0 m2 m4 m6 得 (pq)r m0 m2 m4 m5 m6 可记作 (0,2,4,5,6)(2)(pq)r (pr)(qr) pr p0r 同一律 p(qq)r 矛盾律 分配律 (pqr)(pqr) 分配律 M1M3 qr (pp)qr 同一律, 矛盾律 (pqr)(pqr) 分配律 M3M7 得 (pq)r M1M3M7 可记作 (1,3,7)例2(1)求 A (pq)(pqr)r的主析取范式 解 用快速求法 (1)pq (pqr)(pqr) m2 m3 pqr m1 r (pqr)(pqr)(pqr)(pqr) m1 m3 m5 m7 得 A m1 m2 m3 m5 m7 (1,2,3,5,7)(2)求 B p(pqr)的主合取范式 解 p (pqr)(pqr)(pqr)(pqr) M4M5M6M7 pqr M1 得 B M1M4M5M6M7 (1,4,5,6,7)例3 用主析取范式判断公式的类型:(1)A (pq)q (2)B p(pq) (3)C(pq)r 解(1)A ( pq)q (pq)q 0 矛盾式(2)B p(pq) 1 m0m1m2m3 重言式(3)C (pq)r (pq)r (pqr)(pqr)(pqr) (pqr)(pqr)(pqr) m0m1m3 m5m7 非重言式的可满足式 例4 用主析取范式判断下面2组公式是否等值:(1)p与(pq)(pq)解 p p(qq)(pq)(pq) m2m3 (pq)(pq) (pq)(pq) (pq)(pq) m2m3 故 p (pq)(pq)(2)(pq)r 与 p(qr)解(pq)r (pqr)(pqr) (pqr)(pqr)(pqr)(pqr) m1m3m5 m6m7 p(qr)(pq)(p r) (pqr)(pqr)(pqr)(pqr) m5 m6m7 故 (pq)r p(qr)例5 某单位要从A,B,C三人中选派若干人出国考察, 需满 足下述条件:(1)若A去, 则C必须去;(2)若B去, 则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案? 解 记p:派A去, q:派B去, r:派C去 (1)pr，(2)qr，(3)(pq)(pq)求下式的成真赋值 A=(pr)(qr)((pq)(pq))例6 求A=(pqr)(pqr)(pqr)的主合取范式 解 A m1m3m7 M0M2M4M5M6 例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< y x,y是命题变项, < 是谓词常项, 符号化为: L(x,y)(4)x具有某种性质P x是命题变项, P是谓词变项, 符号化为: P(x)例2 将下述命题用0元谓词符号化, 并讨论它们的真值:(1) 是无理数, 而 是有理数(2)如果2>3，则3<4 解 (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)xy(F(x)G(y)H(x,y))(2)x(F(x)(y(G(y)H(x,y)))(3) xy(F(x)G(y)H(x,y))(4) xy(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)xy(F(f(x,a),y)F(f(y,a),x))xy(x+2=yy+2=x) 假命题(3)xyzF(f(x,y),z) xyz(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=yx+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)) 这是 pp 的代换实例, pp是重言式，永真式(3)(xF(x)yG(y)) yG(y)这是(pq)q的代换实例, (pq)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)xyF(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)))(11)(01) 1(2)xyL(x,y)解 yL(2,y)yL(3,y)(L(2,2)L(2,3))(L(3,2)L(3,3))(10)(01) 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)xG(x) 量词否定等值式 x(F(x)G(x)) 量词分配等值式 解2 xF(x)yG(y) 换名规则 xF(x)yG(y) 量词否定等值式 x(F(x)yG(y)) 量词辖域扩张 xy(F(x)G(y)) 量词辖域扩张 第4章 关系 例1 <2,x+5>=<3y4,y>，求 x, y.解 3y4=2, x+5=y y=2, x= 3 例2 A={0, 1}, B={a, b, c} AB={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>} BA ={ A = {}, B = P(A)A = {<,>, <{},>} P(A)B = 例3 (1)R={ ={<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>} (2)C={ R={ |A|=n, |B|=m, |A×B|=nm, A×B 的子集有 个.所以从A到B有 元关系.|A|=n, A上有 不同的二元关系.例如 |A|=3, 则 A上有512个不同的二元关系.例 5A={a, b, c, d}, R={ 1110100000000100例1 R={ domR = ranR = fldR = 例2 R={<1,2>, <2,3>, <1,4>, <2,2>} S={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>} R1 = R∘S = S∘R = 个不同的二 例3 设A = {a, b, c, d}, R = { 0100010001 10101010102M M0001000100 0000000000 例1 A = {a, b, c}, R1, R2, R3 是 A上的关系, 其中 R1 = { 001010010000010101000000R2自反, R3 反自反, R1既不自反也不反自反.例2 设A＝{a,b,c}, R1, R2, R3和R4都是A上的关系, 其中 R1＝{ R1＝{ R2＝{ R3＝{ 证明若 IA R，则 R 在 A 上自反.证 任取x，xA 因此 R 在 A 上是自反的.例5 证明若 R=R1 , 则 R 在A上对称.证 任取 因此 R 在 A 上是对称的.例6 证明若 R∩R1IA , 则 R 在 A 上反对称.证 任取 因此 R 在 A 上是反对称的.例7 证明若 R∘RR , 则 R 在 A 上传递.证 任取 因此 R 在 A 上是传递的.例8 判断下图中关系的性质, 并说明理由 (1)不自反也不反自反；对称, 不反对称；不传递.(2)反自反, 不是自反；反对称, 不是对称；传递.(3)自反，不是反自反；反对称，不是对称；不传递.例1 设A={a,b,c,d}, R={ 例1 设 A={1, 2, …, 8}, 如下定义 A上的关系R： R={ 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={<2,3>,<3,2>}∪IA R2={<1,3>,<3,1>}∪IA R3={<1,2>,<2,1>}∪IA 例5 设A={1,2,3,4}，在AA上定义二元关系 R： < AA={<1,1>, <1,2>, <1,3>, <1,4>, <2,1>, <2,2>, <2,3>，<2,4>,<3,1>, <3,2>, <3,3>, <3,4>, <4,1>, <4,2>, <4,3>，<4,4>} 根据有序对 例6 <{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }, R整除> 例7 已知偏序集 R={ 例8 设偏序集 例1 设A = {1, 2, 3}, B = {a, b}, 求BA.解BA = { f0, f1, … , f7 }, 其中 f0={<1,a>,<2,a>,<3,a>} f1={<1,a>,<2,a>,<3,b>} f2={<1,a>,<2,b>,<3,a>} f3={<1,a>,<2,b>,<3,b>} f4={<1,b>,<2,a>,<3,a>} f5={<1,b>,<2,a>,<3,b>} f6={<1,b>,<2,b>,<3,a>} f7={<1,b>,<2,b>,<3,b>} 例2 判断下面函数是否为单射, 满射, 双射的, 为什么?（1）f : R→R, f(x)= x2+2x1（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+2x1 在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={<1,0>,<2,0>,<3,0>}，f1={<1,0>,<2,0>,<3,1>}, f2={<1,0>,<2,1>,<3,0>}，f3={<1,0>,<2,1>,<3,1>}，f4={<1,1>,<2,0>,<3,0>}，f5={<1,1>,<2,0>,<3,1>}，f6={<1,1>,<2,1>,<3,0>}，f7={<1,1>,<2,1>,<3,1>}.令 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：011 2233 … ↓ ↓ ↓ ↓ ↓ ↓ ↓ N：0 1 2 4 5 6 … 则这种对应所表示的函数是： x02xf:ZN,f(x)2x1x0例1 设 f : R→R, g : R→R x2x3f(x) x32 g(x)x2 求 f ∘g, g∘f.如果 f 和 g 存在反函数, 求出它们的反函数.解 fg:RRx22x3fg(x)x30gf:RR(x2)2gf(x)2x1x1 f : R→R不存在反函数；g : R→R的反函数是 g1: R→R, g1(x)=x2 第6章 图 例1 下述2组数能成为无向图的度数列吗?(1)3,3,3,4;(2)1,2,2,3 解(1)不可能.有奇数个奇数.(2)能 例2 已知图G有10条边, 4个3度顶点, 其余顶点的度数均小 于等于2, 问G至少有多少个顶点? 解 设G有n个顶点.由握手定理，43+2(n-4)210 解得 n8 例3 已知5阶有向图的度数列和出度列分别为3,3,2,3,3和 1,2,1,2,1, 求它的入度列 解 2,1,1,1,2 例4 证明不存在具有奇数个面且每个面都具有奇数条棱的 多面体.证 用反证法.假设存在这样的多面体, 作无向图G= 讨论所有可能的情况.设有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度顶点 方法二 假设b<5, 则a>9-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 右图有 个面 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) R2 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(数 计 生 赵 钱 孙 李 周 (3(1),(2)有多种方案,(3)不可能 例2 证明下述各图不是哈密顿图: (a(b(c) (c)中存在哈密顿通路 例3 证明右图不是哈密顿图 证 假设存在一条哈密顿回路, a,f,g是2度顶点, 边(a,c),(f,c)和(g,c)必在这条哈密顿回路上,从而点c出现3次, 矛盾.a b c f d e g 此外, 该图满足定理6.10的条件, 这表明此条件是必要、而不充分的.又, 该图有哈密顿通路.例4 有7个人, A会讲英语, B会讲英语和汉语, C会讲英语、意大利语和俄语, D会讲日语和汉语, E会讲德语和意大利语, F会讲法语、日语和俄语, G会讲法语和德语.问能否将他们沿圆桌安排就坐成一圈, 使得每个人都能与两旁的人交谈? 解 作无向图, 每人是一个顶点, 2人之间有边他们有共同的语言.G F E D A B C ACEGFDBA是一条哈密顿回路,按此顺序就坐即可. 离散数学试题（A卷答案） 一、（10分） （1）证明(PQ)∧(QR)(PR)（2）求(P∨Q)R的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。解：（1）因为((PQ)∧(QR))(PR)((P∨Q)∧(Q∨R))∨(P∨R)(P∧Q)∨(Q∧R)∨P∨R (P∧Q)∨((Q∨P∨R)∧(R∨P∨R))(P∧Q)∨(Q∨P∨R)(P∨Q∨P∨R)∧(Q∨Q∨P∨R)T 所以，(PQ)∧(QR)(PR)。 （2）(P∨Q)R(P∨Q)∨R(P∧Q)∨R (P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)M2∧M4∧M6 m0∨m1∨m3∨m5 所以，其相应的成真赋值为000、001、011、101、111：成假赋值为：010、100、110。 二、（10分）分别找出使公式x(P(x)y(Q(y)∧R(x，y)))为真的解释和为假的解释。 解：设论域为{1，2}。 若P(1)＝P(2)＝T，Q(1)＝Q(2)＝F，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝F，则 x(P(x)y(Q(y)∧R(x，y)))x(P(x)((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))(P(1)((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))(T((F∧F)∨(F∧F)))∧(T((F∧F)∨(F∧F)))(TF)∧(TF)F 若P(1)＝P(2)＝T，Q(1)＝Q(2)＝T，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝T，则 x(P(x)y(Q(y)∧R(x，y)))x(P(x)((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))(P(1)((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))(T((T∧T)∨(T∧T)))∧(T((T∧T)∨(T∧T)))(TT)∧(TT)T 三、（10分） 在谓词逻辑中构造下面推理的证明：每个喜欢步行的人都不喜欢做汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。 解 论域：所有人的集合。A(x)：x喜欢步行；B(x)：x喜欢坐汽车；C(x)：x喜欢骑自行车；则推理化形式为： x(A(x)B(x))，x(B(x)∨C(x))，xC(x)xA(x)下面给出证明：(1)xC(x) P(2)xC(x) T(1)，E(3)C(c) T(2)，ES(4)x(B(x)∨C(x)) P(5)B(c)∨C(c) T(4)，US(6)B(c) T(3)(5)，I(7)x(A(x)B(x)) P(8)A(c)B(c) T(7)，US(9)A(c) T(6)(8)，I(10)xA(x) T(9)，EG 四、（10分） 下列论断是否正确？为什么？(1)若A∪B＝A∪C，则B＝C。(2)若A∩B＝A∩C，则B＝C。(3)若AB＝AC，则B＝C。 解(1)不一定。例如，令A＝{1}，B＝{1，2}，C＝{2}，则A∪B＝A∪C，但B＝C不成立。(2)不一定。例如，令A＝{1}，B＝{1，2}，C＝{1，3}，则A∩B＝A∩C，但B＝C不成立。(3)成立。因为若AB＝AC，对任意的x∈B，当x∈A时，有x∈A∩BxABxAC＝(A∪C)－(A∩C)x∈A∩Cx∈C，所以BC；当xA时，有xA∩B，而x∈Bx∈A∪B，所以x∈A∪B－A∩B＝ABx∈AC，但x A，于是x∈C，所以BC。 同理可证，C B。 因此，当AB＝AC时，必有B＝C。 五、（10分）若R是集合A上的自反和传递关系，则对任意的正整数n，R＝R。 证明 当n＝1时，结论显然成立。设n＝k时，Rk＝R。当n＝k＋1时，Rk+1＝Rk*R＝R*R。下面由R是自反和传递的推导出R*R＝R即可。 由传递性得R*RR。另一方面，对任意的 由数学归纳法知，对任意的正整数n，Rn＝R。 n 六、（15分）设函数f：R×RR×R，f定义为：f( (1)证明f是单射。(2)证明f是满射。(3)求逆函数f。 (4)求复合函数f－1f和ff。 证明(1)对任意的x，y，x1，y1∈R，若f( (2)对任意的 1，y＝ uw2，则f( uw2＋ uw2，uw2－>＝ uw2－1(3)f( xyxy2xy(xy)2(4)ff( 七、（15分）设X＝{1，2，3，4}，R是X上的二元关系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)画出R的关系图。(2)写出R的关系矩阵。 (3)说明R是否是自反、反自反、对称、传递的。解(1)R的关系图如图所示：(2)R的关系矩阵为： 10M(R)111011101100 00(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的； 经过计算可得 102M(R)111011101100M(R)，所以R是传递的。00 八、（10分）若 对于任意的a、b∈H，有a*b＝a*(b)∈H，即a*b∈H。又因为H是G非空子集，所以*在H上满足结合律。综上可知， 九、（10分）给定二部图G＝ 证明 设|V1|＝m1，则|V2|＝m－m1，于是n≤m1(m－m1)＝m1m－m22 2－ 1－1 －1 m12。因为(m2m1)20，即4mm1m1，所以n≤m2/4。离散数学试题（B卷答案） 一、（20分）用公式法判断下列公式的类型：(1)(P∨Q)(PQ)(2)(PQ)(P∧(Q∨R))解：（1）因为(P∨Q)(PQ)(P∨Q)∨(P∧Q)∨(P∧Q) (P∧Q)∨(P∧Q)∨(P∧Q)m1∨m2∨m3 M0 所以，公式(P∨Q)(PQ)为可满足式。 （2）因为(PQ)(P∧(Q∨R))((P∨Q))∨(P∧Q∧R)) (P∨Q)∨(P∧Q∧R)) (P∨Q∨P)∧(P∨Q∨Q)∧(P∨Q∨R)(P∨Q)∧(P∨Q∨R) (P∨Q∨(R∧R))∧(P∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)M0∧M1 m2∨m3∨m4∨m5∨m6∨m7 所以，公式(PQ)(P∧(Q∨R))为可满足式。 二、（15分）在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。 Q(x)：x是勤奋的；x是科学家；C(x)：解：论域：所有人的集合。H(x)：x是身体健康的；S(x)：x是事业获得成功的人；F(x)：x是事业半途而废的人；则推理化形式为： x(S(x)Q(x))，x(Q(x)∧H(x)C(x))，x(S(x)∧H(x)) x(C(x)∨F(x))下面给出证明： (1)x(S(x)∧H(x)) P(2)S(a)∧H(a) T(1)，ES(3)x(S(x)Q(x)) P(4)S(a)Q(a) T(1)，US(5)S(a) T(2)，I(6)Q(a) T(4)(5)，I(7)H(a) T(2)，I(8)Q(a)∧H(a) T(6)(7)，I(9)x(Q(x)∧H(x)C(x)) P(10)Q(a)∧H(a)C(a) T(9)，Us(11)C(a) T(8)(10)，I(12)xC(x) T(11)，EG(13)x(C(x)∨F(x)) T(12)，I 三、（10分）设A＝{，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)B。解 P(A)＝{，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}} P(B)－{0}＝{，{0}，{{0}}，{0，{0}}－{0}＝{，{0}，{{0}}，{0，{0}} P(B)B＝{，{0}，{{0}}，{0，{0}}{0，{0}}＝{，0，{{0}}，{0，{0}} 四、（15分）设R和S是集合A上的任意关系，判断下列命题是否成立？(1)若R和S是自反的，则R*S也是自反的。(2)若R和S是反自反的，则R*S也是反自反的。(3)若R和S是对称的，则R*S也是对称的。(4)若R和S是传递的，则R*S也是传递的。(5)若R和S是自反的，则R∩S是自反的。(6)若R和S是传递的，则R∪S是传递的。 解 (1)成立。对任意的a∈A，因为R和S是自反的，则 (2)不成立。例如，令A＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，则R和S是反自反的，但R*S＝{<1，1>}不是反自反的。 (3)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，则R和S是对称的，但R*S＝{<1，3>，<3，2>}不是对称的。 (4)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，3>，<1，3>}，S＝{<2，3>，<3，1>，<2，1>}，则R和S是传递的，但R*S＝{<1，3>，<1，1>，<2，1>}不是传递的。 (5)成立。对任意的a∈A，因为R和S是自反的，则 五、（15分）令X＝{x1，x2，…，xm}，Y＝{y1，y2，…，yn}。问(1)有多少个不同的由X到Y的函数？ (2)当n、m满足什么条件时，存在单射，且有多少个不同的单射？(3)当n、m满足什么条件时，存在双射，且有多少个不同的双射？ 解 (1)由于对X中每个元素可以取Y中任一元素与其对应，每个元素有n种取法，所以不同的函数共n个。 (2)显然当|m|≤|n|时，存在单射。由于在Y中任选m个元素的任一全排列都形成X到Y的不同的单射，故不同的单射有Cnm!＝n(n－1)(n―m―1)个。 (3)显然当|m|＝|n|时，才存在双射。此时Y中元素的任一不同的全排列都形成X到Y的不同的双射，mm故不同的双射有m!个。 六、（5分）集合X上有m个元素，集合Y上有n个元素，问X到Y的二元关系总共有多少个？ 解 X到Y的不同的二元关系对应X×Y的不同的子集，而X×Y的不同的子集共有个2mn，所以X到Y的二元关系总共有2mn个。 七、（10分）若 证明 设e是群 若x∈G也是a*x＝b的解，则x＝e*x＝(a*a)*x＝a*(a*x)＝a*b＝x。所以，x＝a*b是a*x － 1－1 －1 －1＝b的惟一解。 八、（10分）给定连通简单平面图G＝ 由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是d(f)＝2|E|＝24。若存在f∈ fFF，使得d(f)＞3，则3|F|＜2|E|＝24，于是|F|＜8，与|F|＝8矛盾。故对任意f∈F，d(f)＝3。 学习体会 专业：计算机 姓名：范文芳 学号： 成绩： 院校： 离散数学是计算机科学与技术专业的基础核心课程。通过本课程的学习，使学生具有现代数学的观点和方法，并初步掌握处理离散结构所必须的描述工具和方法。同时，也要培养学生抽象思维和慎密概括的能力，使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力，为学生以后学习计算机基础理论与专业课程打下良好的基础。 学习离散数学有两项最基本的任务：其一是通过学习离散数学，使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理，掌握计算机中常用的科学论证方法，为后续课程的学习奠定一个良好的数学基础；其二是在离散数学的学习过程中，培训自学能力、抽象思维能力和逻辑推理能力，以提高专业理论水平。因此学习离散数学对于计算机、通信等专业后续课程的学习和今后从事计算机科学等工作是至关重要的。但是由于离散数学的离散性、知识的分散性和处理问题的特殊性，使部分学生在刚刚接触离散数学时，对其中的一些概念和处理问题的方法往往感到困惑，特别是在做证明题时感到无从下手，找不到正确的解题思路。因此，对离散数学的学习方法给予适当的指导和对学习过程中遇到的一些问题分析是十分必要的。 一、认知离散数学 离散数学是计算机科学基础理论的核心课程之一，是计算机及应用、通信等专业的一门重要的基础课。它以研究量的结构和相互关系为主要目标，其研究对象一般是有限个或可数个元素，充分体现了计算机科学离散性的特点。学习离散数学的目的是为学习计算机、通信等专业各后续课程做好必要的知识准备，进一步提高抽象思维和逻辑推理的能力，为计算机的应用提供必要的描述工具和理论 基础。 1．定义和定理多 离散数学是建立在大量定义、定理之上的逻辑推理学科，因此对概念的理解是学习这门课程的核心。在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理和性质。在考试中有一部分内容是考查学生对定义和定理的识记、理解和运用，因此要真正理解离散数学中所给出的每个基本概念的真正的含义。比如，命题的定义、五个基本联结词、公式的主析取范式和主合取范式、三个推理规则以及反证法；集合的五种运算的定义；关系的定义和关系的四个性质；函数（映射）和几种特殊函数（映射）的定义；图、完全图、简单图、子图、补图的定义；图中简单路、基本路的定义以及两个图同构的定义；树与最小生成树的定义。掌握和理解这些概念对于学好离散数学是至关重要的。2.方法性强 在离散数学的学习过程中，一定要注重和掌握离散数学处理问题的方法，在做题时，找到一个合适的解题思路和方法是极为重要的。如果知道了一道题用怎样的方法去做或证明，就能很容易地做或证出来。反之，则事倍功半。在离散数学中，虽然各种各样的题种类繁多，但每类题的解法均有规律可循。所以在听课和平时的复习中，要善于总结和归纳具有规律性的内容。在平时的讲课和复习中，老师会总结各类解题思路和方法。作为学生，首先应该熟悉并且会用这些方法，同时，还要勤于思考，对于一道题，进可能地多探讨几种解法。3.抽象性强 离散数学的特点是知识点集中，对抽象思维能力的要求较高。由于这些定义的抽象性，使初学者往往不能在脑海中直接建立起它们与现实世界中客观事物的联系。不管是哪本离散数学教材，都会在每一章中首先列出若干个定义和定理，接着就是这些定义和定理的直接应用，如果没有较好的抽象思维能力，学习离散数学确实具有一定的困难。因此，在离散数学的学习中，要注重抽象思维能力、逻辑推理能力的培养和训练，这种能力的培养对今后从事各种工作都是极其重要的。 在学习离散数学中所遇到的这些困难，可以通过多学、多看、认真分析讲课 中所给出的典型例题的解题过程，再加上多练，从而逐步得到解决。在此特别强调一点：深入地理解和掌握离散数学的基本概念、基本定理和结论，是学好离散数学的重要前提之一。所以，同学们要准确、全面、完整地记忆和理解所有这些基本定义和定理。4.内在联系性 离散数学的三大体系虽然来自于不同的学科，但是这三大体系前后贯通，形成一个有机的整体。通过认真的分析可寻找出三大部分之间知识的内在联系性和规律性。如：集合论、函数、关系和图论，其解题思路和证明方法均有相同或相似之处。 二、认知解题规范 一般来说，离散数学的考试要求分为：了解、理解和掌握。了解是能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。为了考核学生对这三部分的理解和掌握的程度，试题类型一般可分为：判断题、填空题、选择题、计算题和证明题。判断题、填空题、选择题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算；计算题主要考核学生的基本运用技能和速度，要求写出完整的计算过程和步骤；证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出严格的推理和论证过程。 学习离散数学的最大困难是它的抽象性和逻辑推理的严密性。在离散数学中，假设让你解一道题或证明一个命题，你应首先读懂题意，然后寻找解题或证明的思路和方法，当你相信已找到了解题或证明的思路和方法，你必须把它严格地写出来。一个写得很好的解题过程或证明是一系列的陈述，其中每一条陈述都是前面的陈述经过简单的推理而得到的。仔细地写解题过程或证明是很重要的，既能让读者理解它，又能保证解题过程或证明准确无误。一个好的解题过程或证明应该是条理清楚、论据充分、表述简洁的。针对这一要求，在讲课中老师会提供大量的典型例题供同学们参考和学习。 通过离散数学的学习和训练，能使同学们学会在离散数学中处理问题的一般性的规律和方法，一旦掌握了离散数学中这种处理问题的思想方法，学习和掌握离散数学的知识就不再是一件难事了。复习离散数学的整个过程可大致分为三个 阶段。 第一阶段，大量进行知识储备的阶段。 离散数学是建立在大量定义上面的逻辑推理学科。因而对概念的理解是我们学习这门学科的核心。由于这些定义非常抽象，初学者往往不能在脑海中建立起它们与现实世界中客观事物的联系。对于跨专业自学的朋友来说更是如此。这是离散数学学习中的第一个困难。因此，对于第一遍复习，我们提出一个最为重要的要求，即准确、全面、完整地记忆所有的定义和定理。具体做法可以是：在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记，直到能够全部正确地默写出来为止。无须强求一定要理解，记住并能准确复述 各定义定理是此阶段的最高要求。也不需做太多的题（甚至不做课后习题也是可以的，把例题看懂就行），重心要放在对定义和定理的记忆上。请牢记，这是为未来的向广度和深度扩张作必要的准备。 这一过程视各人情况不同耗时约在一到两个月内。第二阶段，深入学习，并大量做课后习题的阶段。 这是最漫长的一个阶段，耗时也很难估计，一般来说，若能熟练解出某一章75%以上的课后习题，可以考虑结束该章。 解离散数学的题，方法非常重要，如果拿到一道题，立即能够看出它所属的类型及关联的知识点，就不难选用正确的方法将其解决，反之则事倍功半。例如在命题逻辑部分，无非是这么几种题目：将自然语言表述的命题符号化，等价命题的相互转化（包括化为主合取范式与主析取范式），以给出的若干命题为前提进行推理和证明。相应的对策也马上就可以提出来。以推理题为例，主要是利用P、T规则，加上蕴涵和等价公式表，由给定的前提出发进行推演，或根据题目特点采用真值表法、CP规则和反证法。由此可见，在平常复习中，要善于总结和归纳，仔细体会题目类型和此类题目的解题套路。如此多作练习，则即使遇到比较陌生的题也可以较快地领悟其本质，从而轻松解出。 “熟读唐诗三百首，不会做诗也会吟。”要是拿到一本习题集，从头到尾做过，甚至背会的话。那么，在考场上就会发现绝大多数题见过或似曾相识。这时，要取得较好的成绩也就不是太难的事情了。这一情况具有普遍性，对许多院校的考试都适用。 第三阶段，进行真题模拟训练，提高整体水平和综合能力的阶段。 这一阶段从第二阶段结束一直持续到考试。 除了我们使用的课本外，应尽可能地弄到报考院校的专业课历年试题。因为每个单位对该科目的侧重点毕竟有不同，从历年试题中可以获取许多有用的信息。这些历年试题此时就有了巨大的作用。 第三章部分课后习题参考答案 14.在自然推理系统P中构造下面推理的证明：(2)前提：pq,(qr),r 结论：p(4)前提：qp,qs,st,tr 结论：pq 证明：（2） ①(qr)前提引入 ②qr ①置换 ③qr ②蕴含等值式 ④r 前提引入 ⑤q ③④拒取式 ⑥pq 前提引入 ⑦￢p ⑤⑥拒取式 证明（4）： ①tr 前提引入 ②t ①化简律 ③qs 前提引入 ④st 前提引入 ⑤qt ③④等价三段论 ⑥（qt）(tq)⑤ 置换 ⑦（qt）⑥化简 ⑧q ②⑥ 假言推理 ⑨qp 前提引入 ⑩p ⑧⑨假言推理(11)pq ⑧⑩合取 15在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p(qr),sp,q 结论：sr 证明 ①s 附加前提引入 ②sp 前提引入 ③p ①②假言推理 ④p(qr)前提引入 ⑤qr ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 16在自然推理系统P中用归谬法证明下面各推理： (1)前提：pq,rq,rs 结论：p 证明： ①p 结论的否定引入 ②p﹁q 前提引入 ③﹁q ①②假言推理 ④￢rq 前提引入 ⑤￢r ④化简律 ⑥r￢s 前提引入 ⑦r ⑥化简律 ⑧r﹁r ⑤⑦ 合取 由于最后一步r﹁r 是矛盾式,所以推理正确. 集合论 1.A={,1}，B={{a}}求A的幂集、A×B、A∪B、A+B。2.A={1,2,3,4,5}, R={(x,y)|x 4.A={a,b,c},R= IA ∪{(a,b),(b,a)}，求a和b关于R的等价类。 5.R是A上的等价关系，A/R={{1,2}，{3}},求A，R。6.请分别判断以下结论是否一定成立，如果一定成立请证明，否则请举出反例。 ①如果A∪BC，则AC或者BC。②如果A×B=A×C且A，则B=C。 27.如果R是A上的等价关系，R,r(R)是否一定是A上的等价关系？证明或举例。 8.已知A∩CB∩C,A-CB-C,证明：AB。9.证明：AX(B∩C)=(AXB)∩(AXC)10.证明：P(A)∪P(B)P(A∪B)-111.证明：R[sym] iff R=R -1212.证明：r(R)=R∪IA,S(R)=R∪R,t(R)=R∪R∪...13.证明：s(R∪S)=s(R)∪s(S)14.R是A上的关系，证明：如果R是对称的，则r(R)也是对称的。 15.I是整数集，R={(x,y)|x-y是3的倍数}，证明：R是I上的等价关系。 16.如果R是A上的等价关系，则A/R一定是A的划分。17.R是集合A上的自反关系，S是A上的自反和对称关系，证明t(R∪S)是A上的等价关系。18.I是正整数集合，R是I×I上的二元关系，R={< 19.f:AB，R是B上的等价关系，令S={ 20.R是集合A上的自反关系，S是A上的自反和对称关系，证明t(R∪S)是A上的等价关系。 21.P和Q都是集合A上的划分，请问P∪Q，P-Q是否是A上的划分，22.RAXA,R[irref]且R[tra],证明：r(R)是A上的偏序关系。 23.画出{1,2,3,4,6}上整除关系的哈斯图，求{2,3,6}的4种元素。 24.A={a,b,c,d,e,f,g},R={(a,c),(a,e),(b,d),(b,f),(d,e),(d,f)},S=tr(R),画出S的哈斯图并求{b,c,d,f}的极大元等8种元素。 25.f:A→B,g:B→C都是单（满）射，证明：复合映射gof一定是单（满）射。 26.f:A→B,g:B→C，gof是单射，请问f和g是否一定是单射？请证明或举出反例。27.R是实数集，f:R×RR×R,f( 代数系统 1. 2.求 3.R是实数集，在R上定义运算*为x*y=x+y+xy,问： 5.R是实数集，R上的6运算定义如下：对R中元素x,y，f1( 6. 7.证明：如果群G中每个元素的逆元素都是它自已，则G是交换群。 8.循环群一定是交换群。 9.证明：阶为素数的群一定是循环群。 -110. 11.整数集Z上定义运算*：对任意整数x和y,x*y=x+y-4,其中+，-为普通加减法。证明： 12.证明：如果群G中至少有两个元素，则群中没有零元。13.S是G的子群，证明：{x|x是S的左陪集}是G的一个划分 14. 15.H，K都是群G的子群，请问H∩K,H∪K,H-K是否一定是G的子群？ 16.H，K是G的两个子群，aG, 试证：aHaK当且仅当HK。17.G={1,3,4,5,9},*是模11的乘法(即x*y=xy mod 11)，请问(G,*)是否构成群？ n18. 19.S是G的子群，证明：{x|x是S的左陪集}是G的一个划分 20.G是群，证明：S={aG|xG(ax=xa)},则S是G的子群。21. ++23.R为实数集，R为正实数集， 1.如何判断二部图？完全图、完全二部图的边数。2.如何求E回路？ 3.Petersen图是否为E图或H图。 4.哪些完全图是H图？哪些完全图是E图？ 5.n为何值时轮图为H图？ 6.如何求最小生成树。 7.证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。8.证明：如果G是欧拉图，则其边图L(G)也是欧拉图。9.证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。10.G是平面图，G有m条边，n个顶点，证明：m3n-6。并由此证明K5不是平面图。 11.证明：有6个顶点的简单无向图G和它的补图中至少有一个三角形。 12.证明：在至少有两个顶点的无向树中，至少有2个一度顶点。 13.G是无向简单连通图，G有n个顶点，则G最少有几条边，最多有几条边？ 14.证明：简单无向图G和它的补图中至少有一个是连通图。15.证明：无向图中奇度点（度数为奇数的点）有偶数个。16.证明：n个顶点的无向连通图至少有n-1条边。17.G是H图，V是G的顶点集，证明：对任意顶点集S，SV，都有ω（G-S）≤|S|。其中ω（G-S）表示G-S的分图数目。18.一棵无向树有3个3次点，1个顶点次数为2，其余顶点次数为1，问它有几个次数为1的顶点？写出求解过程。19.证明：每个简单平面图都包含一个次至多为5的顶点。20.连通平面图G有n个顶点，m条边和f个面，证明：n-m+f=2。21.如果图G的最大顶点次数≤ρ，证明：G是ρ+1可点着色的。 22.G是无向简单连通图，G有n个顶点，则G最少有几条边，最多有几条边？ 23.如果一个简单图G和它的补图同构，则称G是自补图，求所有4个顶点自补图。 24.G是平面图，G有m条边，n个顶点，证明：m3n-6。如果G中无三角形，则m2n-4。数理逻辑 1.如果今天是星期一，则要进行英语或数理逻辑考试。 没有不犯错误的人。整数都是有理数。有的有理数不是整数。 不存在最大的整数。有且只有一个偶数是素数。2.求真值表及范式：P(┓QR)、(┓QR)(PR)3.推理： p(qr)，┓s∨p，q ├ sr pr，qs，p∨q ├ r∨s p∨q，p┓r，st，┓sr，┓t ├ q p(┓(r∧s)┓q),p,┓s ├ ┓q 4.如果小王是理科学生，他一定会学好数学。如果小王不是文科学生，他一定是理科学生。小王没学好数学。所以小王是文科学生。 5.判断各公式在给定解释时的真假值，并且改变论域使该公式在新的解释下取值相反。论域：D={-2,3,6}, F(x):x≤3, G(x):x>5, R(x,y):x+y<4 ①x(F(x)∨G(x))②yyR(x,y)第二篇：离散数学
第三篇：离散数学自学
第四篇：离散数学第三章
第五篇：离散数学习题
点击咨询 