离散数学的练习课件.ppt

1、目录,第1章 集合 习题参考答案 第2章 关系与映射 习题参考答案 第3章 命题逻辑 习题参考答案 第4章 一阶逻辑 习题参考答案 第5章 群与环 习题参考答案 第6章 格与布尔代数 习题参考答案 第7章 图论 习题参考答案,第一章集合,(一) 填空题,1.已知集合A ，则A的幂集合=_. 2.设全集E=a,b,c,d,e,A=a,b,c,B=a,d,e,则 , AB=_, A-B=_,AB=_. 3.设A,B是两个集合,其中A=1,2,3,B=1,2, 则A-B=_, 4. 设A= ,B= , 则A-B=_, B- A=_,A=_,B=_. 5.由集合运算的吸收律, =_, =_,核对本页答

2、案,（二）计算题,1.设集合A 判定下列各命题是否正确，并说明理由. (1) ; （2） ; (3) a (4) . 2.设全集 ，有下列子集： ,B= , C= , D= . 求下列集合 (1) ;(2) A ; ; (4) . .,核对本页答案,（二）计算题,3.设集合A ，Ba,b,c,试求： AB1 ;(2) ; (3) ; (4) .,核对本页答案,（三）证明题,四 . 设A，B，C为三个任意集合，试证明： 1. 2. 3. 4. 5. 6. 7. 8. 9.,.,核对本页答案,第二章关系与映射,（一）填空题,1.设集合Aa, b, c, d,A上的关系R(a, a),(a, c),

3、(b, d),则关系 _. 2.设集合A1,2,3,4,R为A上的一个二元关系，R(1,1),(1,2),(1,4),(2,1),(2,3),(3,2),(3,3), (3,4),(4,1),(4,3),(4,4),则R的关系矩阵 _, R的关系图为_.,核对本页答案,（一）填空题,3.设 4.设集合A=1,2,3, 则,核对本页答案,（一）填空题,5.设集合Aa, b，B1,2,则A到B的所有映射是_,其中双射是_. 6.设集合Aa, b, c, d,A上的二元关系R(a, a), (a, c), (b, a), (c, c), (c, d), (d, c),则的关系矩阵 _, 的关系图_.

4、,核对本页答案,7.设集合A1,2,3,A上的二元关系R的关系图如图2-9所示，则关系R具有的性质是_. 8. 设集合A0,1,2,3,4,5,A上的关系R=(0,0), (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3), (4,4), (4,5), (5,4), (5,5),则R在A上构成的等价类是_.,（一）填空题,核对本页答案,9.设集合Aa, b, c, d, e,A上的半序关系R的哈斯图2-10所示，则A的极大元为_,极小元为_.,（一）填空题,核对本页答案,（二）证明题,1.设 是集合A，B上的二元关系，求证

5、： (1) (2) (3) (4) 若 2.设R为集合A上的二元关系，求证： 3.设R是集合A上的关系，如果R是自反的和传递的，证明： .,核对以上答案,核对此题答案,（二）证明题,4.设集合A，B，C， A,B上的二元关系， 是B，C上的二元关系，求证： (1) (2) 5. 设R是集合A上的二元关系，则 (1) R是对称的，当且仅当 ； (2)R是传递的，当且仅当 ；,核对本页答案,6. 设 集合A上的二元关系，若 ，求证： (1) ; (2) ; (3) . 7.设映射 是双射，则,（二）证明题,核对本页答案,（三）计算题,1.设集合Aa，b，c,A上的二元 关系 分别为： ，试分别用定

6、义和矩阵运算求： 2.设集合A1，2，3, 是A上的二元关系，分别为 ， （1）试分别写出 的关系矩阵； （2）分别画出 的关系图； （3）判定 各具有关系的哪几种性质（自反性、对称性、反对称性、传递性）？,核对本页答案,3.设集合Aa，b，c,R是集合A上的关系， ，求 ， 并分别画出它们的关系图. 4.设集合Aa，b，c，d, A上的二元关系R的关系图如图 2-13所示。试求 ，并画出它们的关系图。,（三）计算题,核对此题答案,核对此题答案,5.设R是集合A1，2，3，4，5，6上的关系， (1)验证R是等价关系； (2)画出R的关系图； (3)写出A关于R的等价类. 6.设集合A1，2，

7、3，12, R为整除关系， （1）画出半序集(A,R)的哈斯图； （2）写出集合A的最大元，最小元，极大元和极小元； （3）写出A的子集B3,6,9,12的上界，下界，最小上界和最大上界.,（三）计算题,核对此题答案,核对此题答案,7. 设 是实数集合R上的三个映射， 其中 ，对 ， 试求复合映射 和 ，并指出这些映射中哪些是双 射？,（三）计算题,核对本页答案,第三 章 命题逻辑,(一) 填空题 1. 已知命题公式G=(P(QR),则所有的使G取真值为1的解释是 . 2. 已知命题公式G=(PQ)R,则 G的主析取范式是 .,核对以上答案,(二)计算题 1.设命题逻辑公式G=(R (PQ)

8、S,写出G的析取范式与合取范式. 2.求命题公式G的住析取范式,其中G= (PQ R) (PQ) (QR),核对此题答案,核对此题答案,(三)证明题 1.证明(方法不限): ( (P (Q) (Q R) =Q (P R) 2.利用蕴涵定义证明: (P Q)(R Q) R P,核对本页答案,3.判断公式 G=（PQ）(QR) P)R是恒真的. 4.利用形式演绎法证明: AB,B C,CD 蕴涵 AD.,核对本题答案,核对本题答案,5.利用推演法证明: (P Q) ( P ( PQ) = P Q 6.利用将公式化为范式的方法,证明:G=H. 其中 G=(AB) (AB), H= ( AB) (BA

9、).,核对本题答案,核对本题答案,第四章 一阶逻辑,(一) 填空题 设一阶逻辑公式,则G的前束范式 . 设D:a,b,将表达式 中的量词消除后,与之等价的命题公式是.,核对本页答案,(二) 证明题 1.利用一阶逻辑的基本等价式,证明: 2. 试用解释的方法,证明:,核对本题答案,核对本题答案,(三) 计算题 1.将下面的命题符号化: 某些人对某些食物过敏; 对于任一个正整数,总存在一个更大的正整数. (i)设D:正整数集合; (ii)设D:非空个体名称集合.,核对本页答案,2.设P(x):x是人; F(x,y):x是y的父亲; M(x,y):x是y的母亲. 试用谓词公式表示:x是y的外祖父.

10、3.设一阶逻辑公式: 把G化成前束范式.,核对本页答案,第五章 群与环,(一)填空题 1. 设G是由12个元素构成的循环群,a是G的 一个生成元素,则G有个子群.G的生成 元素集合是. 2. 把置换,核对本页答案,写成轮换的乘积是,写成对换的乘积 是. 3. 设集合M=1,2,3,G是M上的置换群, H=I,(1,3)是G的子群,则H的右陪集为 . 4. 设循环群G有6个元素,a是生成元素,则G 的全部子群是.,核对本页答案,(二)计算题 1. 设G是由M=1,2,3,4上的偶置换在置换 的乘法下做的群,写出G的所有元素及所有元数4的子群.,核对本页答案,核对本页答案,核对本页答案,第六章 格

11、与布尔代数,（一）填空题 设L是一个集合， ， 是L中两个二元运算。如果这两个二元运算满足_律，_律和_律，则(L, , )称为是一个格。 设格中表达式E=（a b)(c d)，则E的对偶表达式 _。 设(L, , ，0, 1 )是有界格，a是L中的一个元素，如果存在元素b，使得_，_，则b称为a的余元素。 设(L, , ，0, 1 )是布尔代数，a,b,c是集合B中任意元素，则(a b)+(a c )+(a c) +(a )=_。,核对本页答案,（二）证明题 设（L, )是一个分配格，a,b,cL 证明： (a b)ca (bc) 设（L, )是分配格，x,y是格中任意元素，如果对格中某个元

12、素a，有 ax=ay, a x=a y 则 x=y。 设(B, ,+, - ,0,1)是布尔代数， a,b,cB，证明： (a+b) =( b)+(a )。 设(B, ,+, - ,0,1)是布尔代数， a,b,cB ，证明：如果ca，则有 (a b)+c=a (b+c)。,核对以上答案,核对以上答案,（三）计算题 设(B, ,+, - ,0,1)是布尔代数，a,b,cB，化简 abc+ab +bc+ bc+ . 设(B, ,+, - ,0,1)是布尔代数， a,b,cB，化简 (a )+c) (a+b) c.,核对本页答案,第七章 图论,（一）填空题 设G是完全二叉树，G有15个点，其中有8

13、个叶点，则G有_条边，G的总度数是_，G的分枝点数是_，G中度数为3的顶点数是_ 。 无孤立点的有限有向图有欧拉路的充要条件是_ 。 设图G的相邻矩阵为 则G的顶点数为_ ，边数为_ 。,核对本页答案,对图7-21二叉树的点 先根遍历的次序是_，中根遍历的次序是_。,D,C,B,A,H,G,F,M,J,图7-21,L,K,I,E,N,核对本页答案,（二）证明题 一株恰有两个度为1的树必是一条路。 设G=(P,A)是有向图，其中含有向路（ e1, en） ，其中fin(en)=init(e1)。试证明G不是有向树。 （三）计算题 1. 写出图7-23所示图的关联矩阵和相邻矩阵。,v1,v4,v3

14、,v2,l6,l5,l4,l3,l2,l1,l8,l7,图7-23,核对以上答案,核对此题答案,设P=a,b,c,d,e,f，画出图G=(P,L)。 其中 (1) L1 =ab,ac,af,be,bf,cd,cf,de,df,ef; (2) L2 =ab,ac,ad,ae,af,bc,cd,de,ef,fb. 并问(1), (2)中的图是否同构？ 3. 根据如下的相邻矩阵，画出它所对应的图G。,核对此题答案,核对此题答案,4. 求图7-24琐碎权图中从u到v的最短路。,图7-24,5. 分别用三种不同的遍历方式写出对图7-25中二叉树点的访问次序。,I,H,G,F,E,D,C,A,B,M,L,

15、K,J,图7-25,核对本页答案,已知一棵二叉树在中根遍历下 各点的次序是：BFDGACIJHKE。在后根遍历下的次序是：FGDBJIKHECA。试找出这样的一棵二叉树，并问这样的二叉树是否唯一。 求图7-26中权图的最优支撑树。,2,1,2,8,7,3,3,3,3,4,4,5,5,5,5,6,6,6,7,图7-26,核对此题答案,核对此题答案,8. 判断7-27中各图是否是欧拉图。,(b),图7-27,核对本页答案,判断图7-28中各图是否试哈密顿图， 若是找出一条哈密顿路；否则说明原因。,（d）,（c）,（b）,（a）,图7-28,核对本页答案,参考答案,第一章 集合,（一）填空题 1.

16、2. 3. 4. 5.,继续答题,继续答题,继续答题,继续答题,继续答题,第一章 集合,6. 等幂，零一，同一，互补. 7. ； 8. 9. 10.,继续答题,继续答题,继续答题,继续答题,继续答题,第一章 集合,（二）计算题 1.(1),(3),(4)正确, (2)不正确； 2.(1) A; (2) 3; (3) B;(4)2,4,8,9,16,32; 3.略.,继续答题,继续答题,继续答题,第一章 集合,（三）证明题 1. 反复利用 2.两边分别证明等于 3.从左边证明等于右边. 4,5,6,7,8利用定义证明. 9.证 因为 ，所以 ， 于 是，原等式左边,继续答题,第二章 关系与映射,

17、（一）填空题 1. 2.,继续答题,继续答题,第二章 关系与映射,3. 4. 5. 6.,继续答题,继续答题,继续答题,继续答题,第二章 关系与映射,7.自反性、反对称性、传递性. 8. 9. （二）证明题 1.用定义证明.参考教材P40定理4中已经证明的小题.,继续答题,继续答题,继续答题,继续答题,第二章 关系与映射,2，3, 用定义证明. 4，5, 用定义证明. 6. 证 （1）因为 ，所以 ，即 （2）因为 ，而 ，所以 ，由定义， 是包含 的最小对称关系， 是对称的，所以 （3） 同（2）. 7. 按定义证明.,继续答题,继续答题,继续答题,继续答题,第二章 关系与映射,（三）计算题

18、 1. 2. （1） （2） （3）,继续答题,继续答题,第二章 关系与映射,图8-3,继续答题,第二章 关系与映射,3. 它们的关系图如图84所示.,图 8-4,继续答题,第二章 关系与映射,4. 它们的关系图如图85所示.,图85,继续答题,5.（1）因为R具有自反性、对称性和传递性，所以R是等价关系. （2） R的关系图如图8-6所示. （3）.A的关于R的等价类是,第二章 关系与映射,继续答题,6.（1）半序集的哈斯图如图8-7所示. （2） 无最大元，最小元是1，极大元是8，12，9，10，7，11，极小元是1； （3）无上界，下界是1，3，无最小上界，最大下界是3.,第二章 关系与

19、映射,图 8-7,继续答题,7. （完）,第二章 关系与映射,继续答题,第三章 命题逻辑,（一） 填空题 1.1,0,0,1,0,1，1,1,0. 2.（PQ R）（P Q R） （P Q R）.,继续答题,继续答题,第三章 命题逻辑,（二）计算题 1.G的析取范式为 （RP）（RQ）（RS） S P） （ S Q）S 合取范式（ R S ） （P Q S）,继续答题,第三章 命题逻辑,2.（PQ R）（PQR）（PQ R）（P Q R） （三）证明题 1.略. 2.设（PQ）（R Q）R为1，则有R为1，且R Q为1，故Q为其1；又PQ为1，故P为1。,继续答题,继续答题,继续答题,第三章

20、命题逻辑,3. G（P Q）（Q R）P）R （P Q）（Q R） P R （Q P）（Q R） Q Q PR.,继续答题,第三章 命题逻辑,4. （1）AB 规则P （2）AB 规则Q，根据（1） （3）A 规则D （4）B 规则Q1，根据（2），（3） （5）BC 规则P （6）BC 规则Q，根据（5） （7）C 规则Q，根据（4），（6） （8）CD 规则P （9）D 规则Q，根据（1），（8） （10）A D 规则D，根据（3），（9）,继续答题,第三章 命题逻辑,5.（PQ）（P （ P Q） （PQ）（P （ P Q） （PQ）（P Q） （P Q）（P Q） P （Q（P Q）

21、P Q,继续答题,第三章 命题逻辑,6. G（AB）（AB） （AB）（A B） A （ B B） A H（AB）（BA） （A B）（ B A） A （B B ） A,继续答题,第四章 一阶逻辑,(一)填空题 (二)证明题,继续答题,继续答题,第四章 一阶逻辑,继续答题,继续答题,第四章 一阶逻辑,继续答题,第四章 一阶逻辑,继续答题,第四章 一阶逻辑,(三)计算题,继续答题,第四章 一阶逻辑,继续答题,继续答题,第五章 群与环,(一)填空题,继续答题,继续答题,继续答题,继续答题,第五章 群与环,(三)计算题,继续答题,第五章 群与环,继续答题,第五章 群与环,继续答题,继续答题,第五章 群与环,继续答题,第五章 群与环,继续答题,第六章 格与布尔代数,（一）填空题 1.交换律，结合律和吸收律； 2. =(ab) (cd) 3.a+b=1, ab=0, 4. a。,继续答题,继续答题,继续答题,继续答题,（二）证明题 1.提示：由分配律(a b)c=(ac) (bc)，再由aca知(ac) (bc) a (bc)。 2.提示：x=x (xa)=(x x)(x a)= x(a y) =(xa) (xy)=(ay) (xy)=(a x)y =(a )y=y。,第六章 格与布尔代数,继续答题,继续答题,3.提示：由德摩根律 ，然后对等式左端使用分