离散数学例题整理
说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。
. . 第一章 定律证明: (1) AB=BA (交换律) 证 x xAB xA 或 xB, 自然有 xB 或 xA xBA 得证 ABBA. 同理可证 BAAB. (2) A(BC)=(AB)(AC) (分配律) 证 x xA(BC) xA或(xB且 xC ) (xA或xB)且(xA或xC) x(AB)(AC) 得证 A(BC)(AB)(AC). 类似可证 (AB)(AC)A(BC). (3) AE=E (零律) 证 根据并的定义, 有EAE. 根据全集的定义, 又有A EE. (4) AE=A (同一律) 证 根据交的定义, 有AEA. 又, x xA, 根据全集E的定义, xE, 从而 xA且xE, xAE 得证 AAE. 例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 (交换律,结合律) 1 / 13 . . = (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为任意集合, 证明: 若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 直接法若n是奇数, 则n2也是奇数. 假设n是奇数, 则存在kN, n=2k+1. 于是 n2 = (2k+1)2 = 2(2k2+2k)+1 得证n2是奇数. 间接法 若n2是奇数, 则n也是奇数. 只证:若n是偶数, 则n2也是偶数. 假设n是偶数, 则存在kN, n=2k. 于是 n2 = (2k)2= 2(2k2) 得证n2是偶数. 归谬法若A-B=A, 则AB= 证 用归谬法, 假设AB, 则存在x,使得 xAB xA且xB xA-B且xB (A-B=A) (xA且xB)且xB xB且xB, 矛盾 构造性对每正整数n, 存n个连的正合数. 证 令x=(n+1)! +1 2 / 13 . . 考虑如下n个连续正整数：x+1, x+2,…, x+n ， 对于i（i=1,2,3,…,n），x+i=(n+1)! +(1+i), 此式含有因子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的素数. 2数学归：对所有n1, 1+3+5+ … +(2n-1)=n 归纳基础. 当n=1时, 1=12, 结论成立. 归纳步骤. 假设对n(n1)结论成立, 则考虑n+1的情况有 1+3+5+ … +(2n-1)+(2n+1)=n2 +(2n+1) = (n+1)2 得证当n+1时结论也成立. 第二数学归任>=2的整数均可表成素数的乘积 证 归纳基础. 对于2, 结论显然成立. 归纳步骤. 假设对所有的k(2kn)结论成立, 要证结论 对n+1也成立. 若n+1是素数, 则结论成立; 否则n+1=ab, 2a,b<n. 由归纳假设, a,b均可表成素数的乘积, 从而n+1 也可表成素数的乘积. 得证结论对n+1成立. 命题为假的证明——举反例 例11 证明下述命题不成立: 若AB=AC, 则B=C. 证明 反例: 取A={a,b}, B={a,b,c}, C={a,b,d}, 有 AB=AC = {a,b} 但BC, 故命题不成立. 第二章 例3 证明 p(qr) (pq)r 证 p(qr) p(qr) （蕴涵等值式） (pq)r （结合律） (pq)r （德摩根律） (pq) r （蕴涵等值式） (1) q(pq) 3 / 13 . . 解 q(pq) q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律） 该式为矛盾式. (2) (pq)(qp) 解 (pq)(qp) (pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1 该式为重言式. (pq)r 的析取式与合取式 解 (pq)r (pq)r (pq)r析取式 (pr)(qr) 合取式 (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)rm0m2m4 m5 m6 可记作 (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) 4 / 13 . . 快速求 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 (3) C (pq)r A(pq)q ( pq)q 0 矛盾式 (2) Bp(pq) Bp(pq) 1 m0m1m2m3 重言式 (3) C (pq)r C (pq)r (pq)r (pqr)(pqr)(pqr) (pqr)(pqr)(pqr) m0m1m3m5m7 非重言式的可满足式 用主析取式判断下面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) m1m3m5m6m7 p(qr) (pq)(pr) (pqr)(pqr)(pqr)(pqr) m5m6m7 故 (pq)r 不等于p(qr) 例5 某单位要从A,B,C三人中选派若干人出国考察, 需满 足下述条件: (1) 若A去, 则C必须去; (2) 若B去, 则C不能去; (3) A和B必须去一人且只能去一人. 5 / 13 . . 问有几种可能的选派方案? 解 记p:派A去, q:派B去, r:派C去 (1) pr, (2) qr, (3) (pq)(pq) 求下式的成真赋值 A=(pr)(qr)((pq)(pq)) 求A的主析取式 A=(pr)(qr)((pq)(pq)) (pr)(qr)((pq)(pq)) ((pq)(pr)(rq)(rr)) ((pq)(pq)) ((pq)(pq))((pr)(pq)) ((rq)(pq))((pq)(pq)) ((pr)(pq))((rq)(pq)) (pqr)(pqr) 成真赋值:101,010 结论: 方案1 派A与C去方案2派B去 A=(pqr)(pqr)(pqr)的主合取式 解A m1m3m7 M0M2M4M5M6 第二章 判断若今天是1号, 则明天是5号. 今天是1号. 所以, 明天是5号. 解 设 p: 今天是1号, q: 明天是5号 推理的形式结构为 (pq)pq 证明 用等值演算法 (pq)pq((pq)p)q ((ppq)p)q qq 1 得证推理正确 判断若下午气温超过30度, 则小燕必去游泳，若她去游泳她就不去看电影了. 所以若小燕没去看电影, 下午气温必定超过了30度. m1 解 设p: 下午气温超过30度, q: 小燕去游泳，r: 小燕去看电影. 推理的形式结构为 ((pq)qr)rp) 证明 主析取式法 ((pq)qr)rp) p r m1m3m4m5m6 m7 主析取式中缺少m0， m2，不是重言式，不正确。 6 / 13 . . 前提:pq, qr, ps, s结论: rpq 直接证明法 证明①ps 前提引入 ②s 前提引入 ③p ①②拒取式 ④pq 前提引入 ⑤q ③④析取三段论 ⑥qr 前提引入 ⑦r ⑤⑥假言推理 ⑧rpq⑦④合取 推理正确rpq是有效结论 构造推理的证明: 若明天是星期一或星期三, 我就有 课. 若有课, 今天必需备课. 我今天下午没备课. 所以, 明天 不是星期一和星期三. 解 设 p:明天是星期一, q:明天是星期三， r:我有课， s:我备课 前提: (pq)r, rs, s 结论: pq 前提: (pq)r, rs, s 结论: pq 证明 ①rs前提引入 ②s前提引入 ③r ①②拒取式 ④ (pq)r前提引入 ⑤(pq) ③④拒取式 ⑥pq ⑤置换 结论有效, 即明天不是星期一和星期三 例4前提: pq, qr, rs结论: ps 证明①p 附加前提引入 ②pq 前提引入 ③q ①②析取三段论 ④qr 前提引入 ⑤r ③④析取三段论 ⑥rs 前提引入 ⑦s ⑤⑥假言推理 推理正确ps是有效结论 例5前提: (pq)r, rs, s, p结论: q 证明 用归缪法 ①q 结论否定引入 ②rs 前提引入 7 / 13 . . ③s前提引入 ④r ②③拒取式 ⑤(pq)r前提引入 ⑥(pq) ④⑤析取三段论 ⑦pq ⑥置换 ⑧p ①⑦析取三段论 ⑨p前提引入 ⑩pp ⑧⑨合取 推理正确q是有效结论 例6前提: pqr, rs, s结论: pq 归结证明法 解pqr pqr pqr pr)qr rsrs pqpq 把推理的前提改写成 前提prqrrss,pq (结论均为0, 不必写出) 前提prqrrss ,pq 证明①pr 前提引入 ②pq 前提引入 ③qr ①②归结 ④qr 前提引入 ⑤r ③④归结 ⑥rs前提引入 ⑦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 8 / 13 . . 例3 在一阶逻辑中将下面命题符号化: (1) 人都爱美; (2) 有人用左手写字 个体域分别取(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)(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. 9 / 13 . . 例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,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) 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)) 例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) 解1 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)) 量词辖域扩 第四章 笛卡儿积 A={0, 1}, B={a, b, c} AB={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>} BA ={<a,0>,<b,0>,<c,0>,<a,1>,<b,1>,<c,1>} (1) R={<x,y> | x,yN, x+y<3} ={<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>} (2) C={<x,y> | x,yR, x2+y2=1}，其中R代表实数集合， 10 / 13 . . C是直角坐标平面上点的横、纵坐标之间的关系， C中的所有的点恰好构成坐标平面上的单位圆. (3) R={<x,y,z> | x,y,zR, x+2y+z=3}， R代表了空间直角坐标系中的一个平面. 例1 R={<a,{b}>,<c,d>,<{a},{d}>,<d,{d}>}, 则 domR ={ a, c, {a}, d } ranR ={{b}, d, {d}} fldR = { a, c, {a}, d, {b}, {d}} 例2R={<1,2>, <2,3>, <1,4>, <2,2>} S={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>} R1={<2,1>,<3,2>,<4,1>,<2,2>} R∘S = {<1,3>, <2,2>, <2,3> } S∘R ={<1,2>, <1,4>, <3,2>, <3,3>} 第六章 已知图G有10条边, 4个3度顶点, 其余顶点的度数均小 于等于2, 问G至少有多少个顶点? 解 设G有n个顶点. 由握手定理, 43+2(n-4)210 解得 n8 证明不存在具有奇数个面且每个面都具有奇数条棱的多面体. 证 用反证法. 假设存在这样的多面体, 作无向图G=<V,E>, 其中 V={v | v为多面体的面}, E={(u,v) | u,vVu与v有公共的棱 uv}. 根据假设, |V|为奇数且vV, d(v)为奇数. 这与握手定理的推论矛盾. 设9阶无向图的每个顶点的度数为5或6, 证明它至少有5个6度顶点或者至少有6个5度顶点. 证 讨论所有可能的情况. 设有a个5度顶点和b个6度顶点 (1)a=0, b=9; (2)a=2, b=7; 11 / 13 . . (3)a=4, b=5; (4)a=6, b=3; (5)a=8, b=1 (1)~(3) 至少5个6度顶点, (4)和(5) 至少6个5度顶点 子图 (1),(2),(3)是(1)的子图, (2),(3)是真子图, (1)是母图. (1),(3)是(1)的生成子图. (2)是{d,e,f }的导出子图, 也是{e5, e6, e7}导出子图. (3)是{e1, e3, e5, e7}的导出子图 画出4阶3条边的所有非同构的无向简单图 解 总度数为6, 分配给4个顶点, 最大度为3, 且奇度顶点数 为偶数, 有下述3个度数列: (1) 1,1,1,3;(2)1,1,2,2;(3)0,2,2,2. 画出3个以1,1,1,2,2,3为度数列的非同构的无向简单图 (1) v1到v4,v4到v1长为3的通路各有多少条? (2) v1到自身长为1,2,3,4的回路各有多少条? (3) 长为4的通路共有多少条?其中有多少条回路? (4) 长度小于等于4的回路共有多少条? (5) 写出D的可达矩阵, 并问D是强连通的吗? 解v1到v4长为3的通路有3条, v4到v1长为3的通路有0条 v1到自身长为1,2,3,4的回路各有1条 长为4的通路共有16条, 其中有3条回路 长度小于等于4的回路共有 8条 例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶 点全是树叶. 试求树叶数, 并画出满足要求的非同构的无 向树. 解 设有x片树叶, 12 / 13 . . 2(2+x)=13+22+x 解得x=3，故T有3片树叶. T的度数列为1, 1, 1, 2, 2, 3 例2 画出所有6阶非同构的无向树 解 5条边, 总度数等于10（同构性质：顶点数相等，边数相等，通过调整顶点顺序度数列相等） 可能的度数列: (1) 1,1,1,1,1,5 (2) 1,1,1,1,2,4 (3) 1,1,1,1,3,3 (4) 1,1,1,2,2,3 (5) 1,1,2,2,2,2 例1 求以1,3,4,5,6为权的最优2元树, 并计算它的权 解 例4 右图表示算式 ((b+(c+d))a)((ef)(g+h)(ij)) 波兰符号法 b + cdaef + ghij 逆波兰符号法 bcd + + aefgh + ij 13 / 13 本文来源：https://www.wddqw.com/doc/2be8d5ae6b0203d8ce2f0066f5335a8102d26667.html