本科离散数学复习题_离散数学考试复习题

本科离散数学复习题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学考试复习题”。

离散数学复习题

一、填空题

1.集合A={,1}，B={1,2}，则2A2B=_________，2A2B=_________.A与B的笛卡尔积AB=_________.2.1000以内的所有正整数中，能被4和5同时整除的共有_____个，不能被6整除的共有_____个

3.设集合A={1,2,3}，B={a,b,c}，则AB共有_____个元素。A到B 的关系

(包括空关系)共有_____个，其中又有_____个是AB的函数, 有_____ 个是A B的内射, 有_____ 个是A B的双射。

4.设A={1,2,3,4,5,6,7,8}.则由B15 表示的A的子集是____________.A的一个子集{2,3,5,7}可表示为____________ 5.集合A={1,2,3,4}，上的两个关系 1={(1,2),(1,3),(2,1)(2,2),(4,1)}，2={(1,3),(3,1)}，则12=____________.12=____________.=_________.6=_________ 12=____________.21=____________.116.集合 A={1,2,3} 上的关系 ={(1,1),(1,2),(1,3),(3,3)} 具有的性质是 _____.7.集合 A={1,2,3,4} 上具有自反性的关系有_____个，具有对称性的关系有_____个，8.设集合A={a,b,c,d}，则A共有_____中不同的分划，A上共有_____个不同的等价关系。若其中的一个分划则与之对应的等价关系是________________.A={{a},{b,c},{d}}，若A上的等价关系：{(a,a),(b,b),(c,c),(d,d),(a,c),(c,a),(b,d),(d,b}.则由导出的A的分划是____________.9.设是集合A={1,2,3,4,5,6,7,8,9,10}上的关于模3同余关系，则[2]=______________________.10.A={1,2,3,4,5,6,7,8,9,10,11,12,24}, 是集合A上的整除关系, BA且 B={2,4,6},则B的最大元是______.最小元是______.上界是______.下界是 ______.最小上界是______.最大下界是______.A的最大元是______.最小元是 ______.A11.在格2,中，集合 A={1,2,3,4,5,6},2A的两元素{1,2}{2,3,5}______.{1,2}与{2,3,5}上界有 ______个.{1,2}{2,3,5}是______.{2,3,4}与{2,4,5}共有______个不同的下界.{1,2,4,6}的补元是________.13.设为任意的格,a,b,c,dL, 若ab且bc,则ac=______________.bc=______________.ac=______________.ab=______________.14.自然数集上的整除关系是一个格, 则在格 N,.中

812=______________812=______________.911=______________911=______________.15.Z是整数集,函数 ƒ定义为:ZZ,且 ƒ(X)=|X|-2X,则函数ƒ的类型是_____(内射,满射,双射).16.设A={1,2,3,4,5},函数ƒ: AA, ƒ(x)=6-x, 则函数ƒ是一个_________射, 17.设函数ƒ: RR,则

f(x)x22，函数g: RR, g(x)x4

fg____,gf____.f1(x)_________.18.设集合A={1,2,3,4,5,6,7,8,9,10},B={2,4,6,8,10,12,14,16,18,20}，函数f:AB,f(i)182i,iA,设H1,2,5,6,A,则f(H)______，设G4,8,10,16B,则f1(G)_____.19.含10条边的图的总度数是____________.20.含有8个顶点的完全图共有______条边.21.含6个结点,9条边的无向连通图,要得到此图的一棵生成树,必须删去__条边.22.不同构且有6个结点的树共有______个.23.简单图G=共有10个结点,其中6个结点的度数为3，其余4个结点的 度数都为2, 则该图共有____条边.该图的补图共有____条边.24.简单图G共有9个结点,且图G与它的补图同构，则该图共有____条边.25.一棵树有2个2度分支点, 1个3度分支点, 3个4度分支点, 则此树共有____片树叶.26.若完全图Kn既是欧拉图又是哈密尔顿，则n满足的条件是__________ 2 27.命题P:“小王学过高等数学”.Q:“小王学过离散数学”.则符合命题“小王学过 高等数学但没有学过离散数学”可表示为___________.命题(PQ)表示的 复合命题含义是:__________________________________________________.28.公式((PQ)(QP))P可化简为___________________________.29.将公式P(QP)化成与之等价的且只含和的公式，则此公式为: __________________.30.令P,Q的赋值分别为1,0.则公式

（(PQ)(QP)）（PQ的真值为__________________.31.公式A含两个命题变元P,Q，其主析取范式为：

(PQ)(QP)），则它的主合取范式是______________.二、选择题

1.设集合A={a，{a}}，则下列错误的是().A){a}2A;B){a}2A;C){{a}}2A； D){{a}}2A;

2.集合A={1,2,3,4,5,6,7,8,9,10}, A上的关系={(x,y)|x+y=10，x,yA},则关 系 具有的性质是().A)自反的;B)对称的;C)传递的,对称的;D)反自反的,对称的;

3.设集合X={-1,1,2,3}与Y={1,2,3,4,5,9}, ƒ(x)=x2,是XY的一个函数,则下列 正确的是().A)ƒ是内射但不是满射;

B)ƒ是满射但不是内射;C)ƒ是双射;

D)ƒ既不是入射也不是满射;

4.设I为整数集合.A={x | x2

C){1,3,5,7};

D){1,2,3,5,7};5.在下面的三个命题公式

1)(PQ)(PQ);2)(PQ)(PQ);3)(PQ)(QP);中是永真式的公式有()个.A)0;B)1;C)2;D)3;

6.下面论断正确的是().A)有补格一定是分配格;B)有补格一定是有界格;C)任何一个格必有最大元;D)偏序集就是格;

7.下列命题中错误的是().A)若L为有限集,则格必定是有限格;

B)在格中,a,bL,必有a(ab)=a;C)格是有补格当且仅当有元素存在补元;

D)在有补分配格中,a,bL, 必有ab=ab;

8.一个含n个结点,连通且有圈的简单图,至少有()条边.A)

n;B)n+1;C)n+2;D)2n-1;

三、判断题

1.设A={}, B=22, 则: {}B且{}B.A

()

()2.集合A={a,b,c}上的关系={(a,b),(a,c)}是不可传递的.3.平面上直线间的“平行关系”是等价关系.()4.人群中的“朋友关系”是偏序

()5.若ƒg是满射,则ƒ必是满射.()6.若ƒ, g都是入射,则gƒ也是入射.()7.在有限分配格中,一个元素若有补元,则补元一定是唯一的.()8.K4有10个生成子图.()9.三个(4,2)无向简单图中,至少有两个同构.()10.凡陈述句都是命题.()11.命题公式(P(PQ))Q是矛盾式.()12.命题“如果1+2=3，那么雪是黑的”是真命题.。

13.判定偏序集是否为格.（教材P150页图7-

3、P174页图7-12）

四、解答题

1.设集合A={1,2,4,5},B={1,2,3,5,16,25}，A到B的关系={(x,y)|xA,yB且y=x2}, 1)写出的所有元素;

2)求出关系的定义域及值域;3)写出关系的关系矩阵M;4)判断关系是否为AB的一个函数? 2.设集合A={1,2,3,4},是A上的一个关系,的关系矩阵如下:

求:的自反闭包r(),对称闭包s(),传

递闭包t().4.设集合A={1,2,3,6,12,24,36,72},A上的整除关系={(a,b)|a,bA且a|b}.1)画出偏序集的次序图;2)A的子集B={6,24,36},求集合{x|xA,且x能整除B中的每一个整数},并求集合{x|xA,且x能被B中的每一个整数整除}.3)判定偏序集是否为格?说明理由.5.偏序集的次序图 如下:

1)求B1={b,c,e}的最小元,最大元.2)求B2={b,c,d,e}的上界,最小上界,下界,最大下界.3)求A的最小元,最大元.4)偏序集是否为格?为什么?

6.格的次序图如下:

1)求出A中所有元素的补元.2)判定格是否为有补格?为什么? 3)判定格是否为分配格?为什么?

7.无向简单图G的邻接矩阵如下：

011000 110000100010110010010100000100

求图G的所有割点、割边.8.有向图G=如下:

1)

2)3)4)5)

求G的邻接矩阵;求deg(V1);

从结点V2到V4长度为3的路有几条? 图中长度为2的回路有几条? 求d(V1 , V4)

9.求下面有权图的一棵最小生成树.并求出最小权数.10.求公式(P(QR))(R(QP))的主析取范式和主合取范式.11.掌握欧拉图、哈密顿图的判定.(教材P227页第16、17、18题)

五、证明题

1.证明： P(QR)Q(PR)2.证明：（Q(PP)(R(PP))R 3.用推理规则证明: 1)(PQ)R, SU, RS, UW, WPQ.2)证明:QS是前提,PQR, Q(RS), P的有效结论.4.试给出以下推理证明: 若这里举行足球赛，则交通就会很拥堵.若他们按时到了球场，则说明交通是畅通的.他们按时到达了.所以这里没有举行足球赛.5.设是一个格,a,b,c,dL, 若ab且cd.求证:acbd.6.设是一个格,a,b,c, L.证明：（ab）(bc)(ac)(ab)(bc)(ac).7.设N是自然数集,定义N上的二元关系={(x,y)|xN,yN,x+y是偶数} 证明是一个等价关系.8.证明：自然数集N上的“整除关系”是一个偏序

9.证明：在（n,m）的树中，m = n-1 6

离散数学复习题

离散数学复习题一、填空1、命题中的否定联接词；蕴含联接词2、一个命题公式，若在所有赋值下取值为真，则称此公式为式；若……假，则……..为 永假 式；若至少存在一组赋值，其命题为真，则......

离散数学复习题

离散数学复习题• 设命题p，r的真值为1，命题q，s的真值为0，则（p→q）(﹁r→s)的真值为。• 只要4不是素数，3就是素数，用谓语表达式符号化为。• D=｛｝，则幂集ρ(D)=• A={a,{b}}，B=｛｝，则A×B=•......

离散数学复习题1

逻辑1、给出的真值表2、证明为永真式 谓词量词和推理1、使用量词和谓词表达不存在这一事实2、证明前提“在这个班上的某个学生没有读过书”和班上的每个学生都通过了第一门......

离散数学函数复习题答案

第6章 函数一、选择题（每题3分）1、设A{a,b,c},B{1,2,3}，则下列关系中能构成A到B函数的是（ C ）A、f1{a,1,a,2,a,3}B、f2{a,1,b,1,b,2}C、f4{a,1,b,1,c,1}D、f1{a,1,a,2,b,2,c,3}2......

离散数学复习题(期末测试卷)

复习题一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）1．谓词公式xy(P(x,y)Q(y,z))xR(x,y)中x的辖域是。2．命题公式　(　pq)的成真赋......