离散数学例题整理

1、第一章定律证明:(1) AÈB=BÈA (交换律)证 "x xÎAÈB Þ xÎA 或 xÎB, 自然有 xÎB 或 xÎAÞ xÎBÈA得证 AÈBÍBÈA.同理可证 BÈAÍAÈB.(2) AÈ(BÇC)=(AÈB)Ç(AÈC) (分配律)证 "x xÎAÈ(BÇC) Þ xÎA或(xÎ

2、;B且 xÎC ) Þ(xÎA或xÎB)且(xÎA或xÎC) ÞxÎ(AÈB)Ç(AÈC) 得证 AÈ(BÇC)Í(AÈB)Ç(AÈC).类似可证 (AÈB)Ç(AÈC)ÍAÈ(BÇC).(3) AÈE=E (零律)证 根据并的定义, 有EÍAÈE.根据全集的定义, 又有AÈ EÍE.(4) AÇE=A (同

3、一律)证 根据交的定义, 有AÇEÍA.又, "x xÎA,根据全集E的定义, xÎE, 从而 xÎA且xÎE, Þ xÎAÇE得证 AÍAÇE. 例4 证明 AÈ(AÇB)=A （吸收律）证 利用例3证明的4条等式证明 AÈ(AÇB) = (AÇE)È(AÇB) (同一律) = AÇ(EÈB) (分配律) = AÇ(BÈE) (交换律) = AÇE (零律

4、) = 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 Ç

5、 C Ç B (零律,同一律) = (A Ç B) Ç C (交换律,结合律) = (A B) C (补交转换律)例6 证明 (AÈB)Å(AÈC)= (BÅC) - A证 (AÈB)Å(AÈC) =(AÈB) - (AÈC)È(AÈC) - (AÈB) =(AÈB)ÇAÇC)È(AÈC)ÇAÇB) = (BÇAÇC)È(CÇAÇ

6、;B) =(BÇC)È(CÇB)ÇA =(B-C)È(C-B)ÇA = (BÅC) - A例7 设A,B为任意集合, 证明: 若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

7、00;B)Ç(BÈA)Ç(BÈB) =(AÈB)Ç(BÈA) =(AÈB)Ç(AÇB) =AÈB-AÇB 直接法 若n是奇数, 则n2也是奇数.假设n是奇数, 则存在kÎN, n=2k+1. 于是 n2 = (2k+1)2 = 2(2k2+2k)+1得证n2是奇数.间接法 若n2是奇数, 则n也是奇数.只证:若n是偶数, 则n2也是偶数.假设n是偶数, 则存在kÎN, n=2k. 于是 n2 = (2k)2= 2(2k2)得证n2是偶数.归谬法 若A-B=

8、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, 矛盾构造性 对每正整数n, 存n个连的正合数.证 令x=(n+1)! +1考虑如下n个连续正整数：x+1, x+2, x+n ，对于i（i=1,2,3,n），x+i=(n+1)! +(1+i), 此式含有因

9、子1+i，而1+i不等于1也不等于x+i，因此x+i是合数。所以x+1, x+2, x+n 是n个连续的正合数。非构造性对每个正整数n, 存在大于n的素数.令x等于所有小于等于n的素数的乘积加1, 则 x不能被所有小于等于n的素数整除. 于是, x或者是素数, 或者能被大于n的素数整除.因此,存在大于n的素数.数学归：对所有n³1, 1+3+5+ +(2n-1)=n2 归纳基础. 当n=1时, 1=12, 结论成立.归纳步骤. 假设对n(n³1)结论成立, 则考虑n+1的情况有1+3+5+ +(2n-1)+(2n+1)=n2 +(2n+1) = (n+1)2得证当n+1时结

10、论也成立.第二数学归 任>=2的整数均可表成素数的乘积证 归纳基础. 对于2, 结论显然成立.归纳步骤. 假设对所有的k(2£k£n)结论成立, 要证结论对n+1也成立. 若n+1是素数, 则结论成立; 否则n+1=ab,2£a,b<n. 由归纳假设, a,b均可表成素数的乘积, 从而n+1也可表成素数的乘积. 得证结论对n+1成立.命题为假的证明举反例例11 证明下述命题不成立: 若AÇB=AÇC, 则B=C. 证明 反例: 取A=a,b, B=a,b,c, C=a,b,d, 有 AÇB=AÇC = a,b但

11、B¹C, 故命题不成立.第二章例3 证明 p®(q®r) Û (pÙq)®r证 p®(q®r) Û ØpÚ(ØqÚr) （蕴涵等值式） Û (ØpÚØq)Úr （结合律） Û Ø(pÙq)Úr （德摩根律） Û (pÙq) ®r （蕴涵等值式） (1) qÙØ(p®q) 解 qÙØ(p®q

12、) Û 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) （蕴

13、涵等值式） Û (ØpÚq)«(ØpÚq) （交换律） Û 1该式为重言式.Ø(p®q)ÚØr 的析取范式与合取范式解 Ø(p®q)ÚØr Û Ø(ØpÚq)ÚØr Û (pÙØq)ÚØr 析取范式 Û (pÚØr)Ù(ØqÚØr) 合取范式 Ø(p®

14、;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 

15、19; (Ø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

16、18; m4 Úm5 Ú m6可记作 Û S(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) 分配律

17、Û M1ÙM3 ØqÚØr Û (pÙØp)ÚØqÚØr 同一律, 矛盾律 Û (pÚØqÚØr)Ù(ØpÚØqÚØr) 分配律 Û M3ÙM7得 Ø(p®q)ÚØr Û M1ÙM3ÙM7可记作 Û P(1,3,7)快速求 A Û (ØpÙ

18、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Ù

19、;qÙr) Û m1Ú m3Ú m5Ú m7得 AÛ m1Ú m2Ú m3Ú m5Ú m7 Û S(1,2,3,5,7)(2) 求 BÛ ØpÙ(pÚqÚØr)的主合取范式解 Øp Û (ØpÚqÚr)Ù(ØpÚqÚØr)Ù(ØpÚØqÚr)Ù(ØpÚ

20、;ØqÚØr) Û M4ÙM5ÙM6ÙM7pÚqÚØr Û M1得BÛ M1ÙM4ÙM5ÙM6ÙM7 Û P(1,4,5,6,7)例3 用主析取范式判断公式的类型:(1) AÛ Ø(p®q)Ùq (3) CÛ (pÚq)®r A Û Ø(Ø pÚq)Ùq Û ( pÙØq)

21、17;q Û 0 矛盾式(2) BÛ p®(pÚq) B Û Ø pÚ(pÚq) Û 1 Û m0Úm1Úm2Úm3 重言式 (3) CÛ (pÚq)®r C Û Ø(pÚq)Úr Û (ØpÙØq)Úr Û (ØpÙØqÙr)Ú(ØpÙØqÙ

22、16;r)Ú(ØpÙØqÙr) Ú(ØpÙqÙr)Ú(pÙØqÙr)Ú(pÙqÙr) Û m0Úm1Úm3Ú m5Úm7 非重言式的可满足式用主析取范式判断下面2组公式是否等值:(1) p与(ØpÚq)®(pÙq)解 p Û pÙ(ØqÚq) Û (pÙØq)Ú(p&#

23、217;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)Ú

24、;(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Ù&

25、#216;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)求

26、下式的成真赋值 A=(p®r)Ù(q®Ør)Ù(pÙØq)Ú(ØpÙq)求A的主析取范式 A=(p®r)Ù(q®Ør)Ù(pÙØq)Ú(ØpÙq) Û (ØpÚr)Ù(ØqÚØr)Ù(pÙØq)Ú(ØpÙq) Û (ØpÙØq)&

27、#218;(ØpÙØr)Ú(rÙØq)Ú(rÙØr) Ù(pÙØq)Ú(ØpÙq) Û (ØpÙØq)Ù(pÙØq)Ú(ØpÙØr)Ù(pÙØq) Ú(rÙØq)Ù(pÙØq)Ú(ØpÙØq)Ù(&#

28、216;pÙq) Ú(ØpÙØr)Ù(ØpÙq)Ú(rÙØq)Ù(ØpÙq) Û (pÙØqÙr)Ú(ØpÙqÙØr)成真赋值:101,010结论: 方案1 派A与C去 方案2派B去A=(ØpÙØqÙr)Ú(ØpÙqÙr)Ú(pÙqÙr)的主合取范式解 A &

29、#219; m1Úm3Úm7 Û M0ÙM2ÙM4ÙM5ÙM6第二章判断若今天是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&

30、#218;ØqÚq Û 1得证推理正确判断若下午气温超过30度, 则小燕必去游泳，若她去游泳她就不去看电影了. 所以若小燕没去看电影, 下午气温必定超过了30度. m1解 设p: 下午气温超过30度, q: 小燕去游泳，r: 小燕去看电影. 推理的形式结构为 (p®q)Ù(q®Ø r) )®(Ø r®p)证明 主析取范式法(p®q)Ù(q®Ø r) )®(Ø r®p)ÛpÚ rÛm1Ú

31、m3Ú m4 Ú m5Ú m6 Ú m7主析取范式中缺少m0， m2，不是重言式，不正确。前提: 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)是有效结论构造推理的证明: 若明天是星期一或星期三, 我就有课. 若有课,

32、今天必需备课. 我今天下午没备课. 所以, 明天不是星期一和星期三. 解 设 p:明天是星期一, q:明天是星期三， r:我有课， s:我备课前提: (pÚq)®r, r®s, Øs结论: ØpÙØq 前提: (pÚq)®r, r®s, Øs结论: ØpÙØq 证明 r®s 前提引入 Øs 前提引入 Ør 拒取式 (pÚq)®r 前提引入 Ø(pÚq) 拒取式 ØpÙ

33、Ø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 前提引入

34、 Ør 拒取式 Ø(pÙq)Úr 前提引入 Ø(pÙq) 析取三段论 ØpÚØq 置换 Øp 析取三段论 p 前提引入 ØpÙp 合取推理正确, Øq是有效结论例6 前提: (p®q)®r, r®s, Øs结论: pÙØq归结证明法解 (p®q)®r Û Ø(ØpÚq)Úr Û (pÙØq)Úr &

35、#219; (pÚr)Ù(ØqÚr) r®s Û ØrÚs Ø(pÙØq) Û ØpÚq把推理的前提改写成前提: pÚr, ØqÚr, ØrÚs, Øs, ØpÚq(结论均为0, 不必写出)前提: pÚr, ØqÚr, ØrÚs, Øs , ØpÚq证明 pÚr 前提引入 Øp&

36、#218;q 前提引入 qÚr 归结 ØqÚr 前提引入 r 归结 ØrÚs 前提引入 s 归结 Øs 前提引入 0 合取第三章将下述命题用0元谓词符号化, 并讨论它们的真值:(1) 根2是无理数, 而根3是有理数(2) 如果2>3，则3<4解 (1) 设F(x): x是无理数, G(x): x是有理数符号化为真值为0(2) 设 F(x,y): x>y, G(x,y): x<y,符号化为 F(2,3)®G(3,4)真值为1例3 在一阶逻辑中将下面命题符号化: (1) 人都爱美; (2) 有人

37、用左手写字个体域分别取(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)例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)

38、(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

39、(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)

40、4;$xG(x)"x的辖域:(F(x)®$xG(x)， 指导变元为x$x的辖域:G(x)， 指导变元为xx的两次出现均为约束出现. 但是, 第一次出现的x是"x中的x, 第二次出现的x是$x中的x. 例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) 换名规则(2) "x(F(x,y) ® $yG(x,y,

41、z)Û "x(F(x,y) ® $tG(x,t,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&quo

42、t;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)例4 证明下列等值式:Ø $x(M(x)ÙF(x) Û "x(M(x)® ØF(x)证 左边 Û "x Ø(M(x)ÙF(x) 量词否定等值式Û "x(&#

43、216;M(x)ÚØF(x)Û "x(M(x)® ØF(x)例5 求公式的前束范式(1) "xF(x)ÙØ$xG(x)解1 Û "xF(x)Ù"xØG(x) 量词否定等值式Û "x(F(x)ÙØG(x) 量词分配等值式解2 Û "xF(x)ÙØ$yG(y) 换名规则Û "xF(x)Ù"yØG(y) 量词否定等值式Û &

44、quot;x(F(x)Ù"yØG(y) 量词辖域扩张Û "x"y(F(x)ÙØG(y) 量词辖域扩张第四章笛卡儿积A=0, 1, B=a, b, cA´B=<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c> B´A =<a,0>,<b,0>,<c,0>,<a,1>,<b,1>,<c,1> (1) R=<x,y> | x,y

45、ÎN, x+y<3 =<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0> (2) C=<x,y> | x,yÎR, x2+y2=1，其中R代表实数集合， C是直角坐标平面上点的横、纵坐标之间的关系， C中的所有的点恰好构成坐标平面上的单位圆. (3) R=<x,y,z> | x,y,zÎR, x+2y+z=3， R代表了空间直角坐标系中的一个平面. 例1 R=<a,b>,<c,d>,<a,d>,<d,d>, 则domR = a, c, a, d ranR =b, d, dfldR = a, c, a, d, b, d 例2 R=<1,2>, <2,3>, <1,4>, <2,2> S=<1,1>, <1,3>, <2,3>, <3,2>, <3,3>