离散数学.docx
- 文档编号:83491
- 上传时间:2023-04-28
- 格式:DOCX
- 页数:38
- 大小:486.04KB
离散数学.docx
《离散数学.docx》由会员分享,可在线阅读,更多相关《离散数学.docx(38页珍藏版)》请在冰点文库上搜索。
离散数学
第一章数学语言与证明方法
例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(交换律)
证xxAB
xAxB(并的定义)
xBxA(逻辑演算的交换律)
xBA(并的定义)
(2)A(BC)=(AB)(AC)(分配律)
证xxA(BC)
xA(xBxC)(并,交的定义)
(xAxB)(xAxC)(逻辑演算的分配律)
x(AB)(AC)(并,交的定义)
(3)AE=E(零律)
证xxAE
xAxE(并的定义)
xA1(全集E的定义)
1(逻辑演算的零律)
xE(全集E的定义)
(4)AE=A(同一律)
证xxAE
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)(~BC)(双重否定律)
=(A~C~B)(A~CC)(分配律)
=(A~C~B)(A)(矛盾律)
=A~C~B(零律,同一律)
=(A~B)~C(交换律,结合律)
=(A–B)–C(补交转换律)
例6证明(AB)(AC)=(BC)-A
证(AB)(AC)
=((AB)-(AC))((AC)-(AB))
=((AB)~A~C)((AC)~A~B)
=(B~A~C)(C~A~B)
=((B~C)(C~B))~A
=((B-C)(C-B))~A
=(BC)-A
例7设A,B为任意集合,证明:
(1)AAB
证xxAxAxB(附加律)
xAB
(2)ABA
证xxABxAxB
xA(化简律)
(3)A-BA
证xxA-BxAxB
xA(化简律)
(4)若AB,则P(A)P(B)
证xxP(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,使得
xABxAxBxA-BxB(A-B=A)
xAxBxBxBxB,矛盾
例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 也可表成素数的乘积.得证结论对n+1成立。 例10可用4分和5分邮票组成n分邮资,n12. 证归纳基础.12=34,13=24+5,14=25+4,15=35, 得证对n=12,13,14,15时结论成立. 归纳步骤.设n15,假设对12,13,…,n结论成立, 由12n-3 成,再加一张4分邮票即可得到n+1分邮资,得证结论对n+1 也成立. 第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)只要天冷,小王就穿羽绒服.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.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=(p1p2p3)(p1p2) 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) m0m2m4m6分配律 得(pq)rm0m2m4m5m6 可记作(0,2,4,5,6) (2)(pq)r(pr)(qr) prp0r同一律 p(qq)r矛盾律 (pqr)(pqr)分配律 M1M3 qr(pp)qr同一律,矛盾律 (pqr)(pqr)分配律 M3M7 得(pq)rM1M3M7 可记作(1,3,7) 例2 (1)求A(pq)(pqr)r的主析取范式 解用快速求法 (1)pq(pqr)(pqr)m2m3 pqrm1 r(pqr)(pqr)(pqr)(pqr) m1m3m5m7 得Am1m2m3m5m7(1,2,3,5,7) (2)求Bp(pqr)的主合取范式 解p(pqr)(pqr)(pqr)(pqr) M4M5M6M7 pqrM1 得BM1M4M5M6M7(1,4,5,6,7) 例3用主析取范式判断公式的类型: (1)A(pq)q (2)Bp(pq)(3)C(pq)r 解 (1)A(pq)q(pq)q0矛盾式 (2)Bp(pq)1m0m1m2m3重言式 (3)C(pq)r(pq)r (pqr)(pqr)(pqr) (pqr)(pqr)(pqr) m0m1m3m5m7非重言式的可满足式 例4用主析取范式判断下面2组公式是否等值: (1)p与(pq)(pq) 解pp(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) m1m3m5m6m7 p(qr)(pq)(pr) (pqr)(pqr)(pqr)(pqr) m5m6m7 故(pq)rp(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)的主合取范式 解Am1m3m7 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 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 符号化为F(2,3)G(3,4) 真值为1 例3在一阶逻辑中将下面命题符号化: (1) 人都爱美; (2)有人用左手写字 个体域分别取(a)人类集合,(b)全总个体域. 解: (a) (1)设F(x): x爱美,符号化为xF(x) (2)设G(x): x用左手写字,符号化为xG(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)xF(x)真值为1 (2)xG(x)真值为0 (b) (1)xF(x)真值为1 (2)xG(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=2y=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))量词分配等值式 解2xF(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=yy=2,x=3 例2A={0,1},B={a,b,c} AB={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>} A={},B= P(A)A={<,>,<{},>} P(A)B= 例3 (1)R={
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学