离散数学例题.doc

.第一章定律证明:(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 (交换律,结合律) = (A B) C (补交转换律)例6 证明 (AB)(AC)= (BC) - A证 (AB)(AC) =(AB) - (AC)(AC) - (AB) =(AB)AC)(AC)AB) = (BAC)(CAB) =(BC)(CB)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=(AB)(AB) =(AA)(AB)(BA)(BB) =(AB)(BA) =(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考虑如下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的素数.数学归：对所有n1, 1+3+5+ +(2n-1)=n2 归纳基础. 当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,b3，则3y, G(x,y): xy,符号化为 F(2,3)G(3,4)真值为1例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) $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)， 指导变元为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,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, cAB=, BA =, (1) R= | x,yN, x+y3 =, , , , , (2) C= | x,yR, x2+y2=1，其中R代表实数集合， C是直角坐标平面上点的横、纵坐标之间的关系， C中的所有的点恰好构成坐标平面上的单位圆. (3) R= | x,y,zR, x+2y+z=3， R代表了空间直角坐标系中的一个平面. 例1 R=, 则domR = a, c, a, d ranR =b, d, dfldR = a, c, a, d, b, d 例2 R=, , , S=, , , , R-1=, RS = , , SR =, , , 第六章已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于等于2, 问G至少有多少个顶点? 解 设G有n个顶点. 由握手定理, 43+2(n-4)210解得 n8证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.证 用反证法. 假设存在这样的多面体, 作无向图G=,其中 V=v | v为多面体的面, E=(u,v) | u,vV u与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;(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片树叶,2(2+x)=13+22+x解得x=3，故T有3片树叶.T的度数列为1, 1, 1, 2, 2, 3例2 画出所有6阶非同构的无向树解 5条边, 总度数等于10（同构性质：顶点数相等，边数相等，通过调整顶点顺序度数列相等）可能的度数列:(