《本科离散数学复习题(8页).doc》由会员分享，可在线阅读，更多相关《本科离散数学复习题(8页).doc（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-本科离散数学复习题-第 8 页离散数学复习题一、 填空题。1. 集合A=,1，B=1,2，则=_（，），（，1），（1，）_.*A与B的笛卡尔积AB=_（，1），（，2），（1,1），（1,2）_.2. 设集合A=1,2,3，B=a,b,c,d，则AB共有_12_个元素。A到B的关系(包括空关系)共有_212_个，其中又有_43_个是AB的函数, 有_4_ 个是A B的内射, 有_4_ 个是A B的双射。若#A=m,#B=n,A*B有mn个元素，A到B的关系共有2mn个，A到B的函数有nm个，有P（从上到下是m，n）个A到B的内射，有n！个A到B的双射。（课本75页）3. 设A= a1, a
2、2, a3, a4, a5, a6, a7, a8.则由B15 表示的A的子集是_a5,a6,a7,a8_. A的一个子集 a2, a4, a5, 可表示为_B88_P8 B15=B00001111=a5,a6,a7,a8,a2,a4,a5=B01011000=B884. 若1,2,4,7A=1,2,4,7,8,10,11 且 1,2,4,7A=1,7,则A=_1,7,8,10,11_5. 集合A上的两个关系 1=(1,2),(1,3),(2,1)(2,2),(4,1),2=(1,3),(3,1)，则12=_(1,3)_.12.=(1,2),(1,3),(2,1),(2,2),(3,1),(4
3、,1)12=_(1,1),(2,3),(4,3)_.21=_(3,2)_.1c=_.*P436. 集合 A=1,2,3 上的关系 =(1,1),(1,2),(1,3),(3,3) 具有的性质是_传递性_.P52 自反性：apb 对称性：任何apb必有bpa反对称：每个apb和bpa必有a=b传递性：每当apb和bpc必有apc7. 集合 A=1,2,3,4 上具有自反性的关系有_15_个，具有对称性的关系有_44_个.N个元素集合上有2(n*(n+1)/2)个关系是对称的、有2n*3(n(n+1)/2)个关系是反对称的、有3(n(n-1)/2)个关系是非对称的、有2n(n-1)个关系是反自反、
4、有2(n(n-1)/2)个关系是既不自反也不反自反、有2(n2)-2*2(n(n-1)个关系是自反和对称的8. 集合A=a,b,c,d，则A共有_15_中不同的分划。A上共有_11_个不同的等价关系。若其中的一个分划A=a,b,c,d，则与之对应的等价关系是_（a,a）,(b,b),(b,c),(c,b),(c,c),(d,d)_.*P19&P56集合A上的关系p,如果它是自反、对称且可传递的，则称p为A上的等价关系。如P57例一含有n个元素的集合的划分数记为Bn,显然B1=1, B2=2,对一般的n有递推公式 Bn+1=C(n,0)B0+C(n,1)B1+.+C(n,n)Bn,9. 设是集合
5、A=1,2,3,4,5,6,7,8,9,10上的关于模3同余关系，则2=_2,5,8_.P58 用RESm（i）表示用m除i所得的余数，如果RESm（i1）=RESm（i2），则我们说i1和i2“模m相等”或“模m同余”，写成i1=（三条横线的等于）i2（mod m）10. A=1,2,3,4,5,6,7,8,9,10,11,12, 是集合A上的整除关系, BA且B=2,4,6,则B的最大元是_无1_. 上界是_无是_2,1无2_.A的最大元是_无1无_.下界是_1无1_.*P194 最大下界记为glb，最小上界记为lub11.集合 A=1,2,3,4,5,6,在格中,1,22,3,5是_无_
6、.上界是 _无_.1,22,3,5是_1_.2,3,4与2,4,5共有_无_个不同的下界.1,2,4,6的补元是_3_.P207 设是一个含有元素1和0的格，对于L中的一个元素l，如果有元素l非使得lVl非=1，l（最大下界的符号）l非=0，则称l非是l的补12.设为任意的格,a,b,c,dL, 若ab且bc,则ac=_c_.bc=_bc=_ab=_b_.13. Z是整数集,函数 定义为:ZZ,且 (X)=|X|-2X,则函数的类型是_双射_(内射,满射,双射).P75 当ai/=aj时，f(ai)/=f(aj)(也就是当f(ai)=f(aj)时，有ai=aj)，则称f为由A到B的内射 若f(
7、A)=B,则称f为由A到B的满射 若f既是内射又是满射，则称f为A到B的双射14. 设A=1,2,3,4,5,函数: AA, (X)=6-X, 则函数是一个_双_射.15. 含10条边的图的总度数是_20_.每条边贡献两个度数，所以10条边贡献20个度数16. 含有8个顶点的完全图共有_28_条边.P233 具有n个节点和m条边的图称为（n，m）图，在一个完全的（n，m）图中，m=C（上2下n）=n（n-1）/217. 含6个结点,9条边的无向连通图,要得到此图的一棵生成树,必须删去_4_条边.P267 在（n，m）树中，m=n-1，须删去的总数为9-（6-1）=418. 画不同构且有6个结点
8、的树共有_6_个.画树时，n=6，所以m=n-1=5，所以度数为10，分为：（1） 111115（2） 111124（3） 111133（4） 111223（5） 11222219. 简单图G=共有10个结点,其中6个结点的度数为3，其余4个结点的度数都为2, 则该图共有_13_条边. 该图的补图共有_32_条边.度数和为边数的两倍，补图的边即为完全图的边（m=C（上2下n）=n（n-1）/2）减去该图的边20. 一棵树有2个2度分支点, 1个3度分支点, 3个4度分支点, 则此树共有_7_ 片树叶.21. 命题P:小王学过高等数学. Q:小王学过离散数学. 则符合命题小王学过高等数学但没有学
9、过离散数学可表示为_pQ(PQ)表示的复合命题含义是:_小王没学过高等数学和离散数学。_.22. 公式(PQ)(QP)P可化简为_PQ_.23. 将公式P(QP)化成与之等价的且只含和的公式,则此公式为: _(PQ)V(PQ)V(pQ)V(PQ)_. （(PQ)(QP) ）（PQ）的真值为_1_.二、 选择题。1. 设集合A=a，a，则下列错误的是( C ).A)a(A);B)a(A);C)a(A);D)a(A);2.集合A=1,2,3,4,5,6,7,8,9,10, A上的关系=(x,y)|x+y=10，x,yA,则关系具有的性质是( D ).A)自反的;B)对称的;C)传递的,对称的;D)
10、反自反的,对称的;3.设集合X=-1,1,2,3与Y=1,2,3,4,5,9, (x)=x2,是XY的一个函数,则下列正确的是( A ).A) 是入射但不是满射; B) 是满射但不是入射;C) 是双射;D) 既不是入射也不是满射;4.设I为整数集合. A=x | x230，xI, B=x | x为质数，x20, C=1,3,5, 则(C-A)(B-A)=( B ).A)1,2,3,5;B); C)1,3,5,7;D)1,2,3,5,7;5.在下面的三个命题公式1) (PQ)(PQ);2) (PQ)(PQ);3) (PQ)(QP);中是永真式的公式有( C )个. A)0;B)1; C) 2;D
11、)3;6. 下面论断正确的是( B ).A) 有补格一定是分配格;B)有补格一定是有界格;C) 任何一个格必有最大元;D)偏序集就是格;7. 下列命题中错误的是( B ).A)若L为有限集,则格必定是有限格;B)在格中,a,bL,必有a(ab)=a;C)格是有补格当且仅当有元素存在补元;D)在有补分配格中,a,bL, 必有=;8. 一个含n个结点,连通且有圈的简单图,至少有( A )条边.A) n;B) n+1;C) n+2;D) 2n-1;三、 判断题。1. 设A=, B=(A), 则: B且B.( F )2. 若A-BB,则BA.( F )3. 集合A=a,b,c上的关系=(a,b),(a
12、,c)是不可传递的.( T )4. 平面上直线间的平行关系是等价关系. （T）5. 若A到B关系和g都具有自反性,则g必也具有自反性.( T)6. 若g是满射,则必是满射.（内射看前，满射看后）( )7. 若, g都是入射,则g也是入射.( )8. 在有限分配格中,一个元素若有补元,则补元一定是唯一的.( )9. K4有10个生成子图.（）( )10. 三个(4,2)无向简单图中,至少有两个同构.( )11. 凡陈述句都是命题.( )12. 命题公式(P(PQ)Q是矛盾式.( )13. 命题如果1+2=3，那么雪是黑的是真命题.。（）14. 判定偏序集是否为格.（教材P150页图7-3、P17
13、4页图7-12）四、 解答题。1. 设集合A=1,2,4,5,B=1,2,3,5,16,25, A到B的关系=(x,y)|xA,yB且y=x2,1) 写出的所有元素;2) =(x,y)|(1,1),(4,16),(5,25)3) 求出关系的定义域及值域; 定义域为1,4,5,值域为1，16，253) 写出关系的关系矩阵M;1235162511000002000000400001050000014) 判断关系是否为AB的一个函数,为什么?不是！A中的2并没有像2. 设集合A=1,2,3,4,是A上的一个关系,的关系矩阵如下:M=求:的自反闭包r(),对称闭包s(),传递闭包t().自反闭包r(p
14、)=(1,1),(2,2),(3,3),(4,4),(1,4),(2,3),(3,1),(4,3)对称闭包s(p)=(1,1),(1,4),(4,1),(2,2),(2,3),(3,2),(3,1),(1,3),(4,3),(3,4),(4,4)3.设集合A=1,2,3,6,12,24,36,72,A上的整除关系=(a,b)|a,bA且a|b. 画出偏序集的哈斯图; 对于A的子集B=6,24,36,求集合x|xA,且x能整除B中的每一个整 数,并求集合x|xA,且x能被B中的每一个整数整除. 判定偏序集是否为格?说明理由.4. 偏序集的哈斯图如下:1)求B1=b,c,e的最小元e,最大元a.2
15、) 求B2=b,c,d,e的上界a,最小上界a,下界e,最大下界.e3) 求A的最小元无,最大元.a4) 偏序集是否为格?为什么?不是没有最小下界5. 格, A=1,2,3,4,5,6,求: 2,3与1,2,4的最小上界, 1，2，3，42,4与4,5,6的最大下界.（4） 求(A)的最大元（1，2，3，4，5，6）,最小元.空集 求1,2,5,6的补元.3，46. 格的哈斯图如下:1) 求出A中所有元素的补元.2) 判定格是否为有补格?为什么?3) 判定格是否为分配格?为什么?7. 有向图G=如下:1) 求G的邻接矩阵;2) 求deg(V1);3) 从结点V2到V4长度为3的路有几条?4)
16、图中长度为3的回路有几条?5) 求d(V1 , V4).（1）AV1V2V3V4V11110V20110V31001V40101(2)出度为3，入度为2（3）A3为2 (4)8. 求下面有权图的一棵最小生成树.9. 求公式(P(QR)(R(QP)的主析取范式和主合取范式.10. 掌握欧拉图、哈密顿图的判定.(教材P227页第16、17、18题)五、 证明题。1. 证明： P(QR)Q(PR)要证明：P(QR)Q(PR)只需要证明P(QR) Q(PR)为重言式即可PQRQRP(QR)PRQ(PR)P(QR) Q(PR)000111110011111101001111011111111001101
17、1101111111100000111111111结论得证 2. 证明： （Q (PP)(R(PP) RQ要证明（Q (PP)(R(PP) RQ成立，只需要证明（Q (PP)(R(PP) （RQ）为重言式PQRPPPQ (PPR(PP（Q (PP)(R(PP)RQ(PP)(R(PP) （RQ）000101111100110100010101001111011100011110000111111010010001110000111111100001113 用推理规则证明:1) (PQ)R, SU, RS, UW, WPQ.2) 证明:QS是前提,PQR, Q(RS), P的有叙结论.（1）1W前提2UW前提3U1，24SU前提5S3，46RS前提7R5，68(PQ)R前提9(PQ)7，810PQ的摩根定理结论得证（2）1P前提2Q前提3PQR前提4R1，2，35Q(RS)前提6S2，4，5结论得证3. 试给出以下推理证明:一个科室选定出差的人.如果李去,则王必须去.张和王不能同时去.结果是:如果张去,则李不能去.4. 设是一个格,a,b,c,dL, 若ab且cd.求证:acbd.5. 设是一个格,a,b,c,dL. 证明： （ab）(cd) ( ac) (bd).6. 设N是自然数集,定义N上的二元关系=(x,y)|xN,yN,x+y是偶数 证明是一个等价关系; 求关系的等价类.