第一篇:本科离散数学复习题
离散数学复习题
一、填空题
1.集合A={,1},B={1,2},则2A2B=_________,2A2B=_________.A与B的笛卡尔积AB=_________.2.1000以内的所有正整数中,能被4和5同时整除的共有_____个,不能被6整除的共有_____个
3.设集合A={1,2,3},B={a,b,c},则AB共有_____个元素。A到B 的关系
(包括空关系)共有_____个,其中又有_____个是AB的函数, 有_____ 个是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)},则12=____________.12=____________.=_________.6=_________ 12=____________.21=____________.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上的整除关系, BA且 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.设
812=______________812=______________.911=______________911=______________.15.Z是整数集,函数 ƒ定义为:ZZ,且 ƒ(X)=|X|-2X,则函数ƒ的类型是_____(内射,满射,双射).16.设A={1,2,3,4,5},函数ƒ: AA, ƒ(x)=6-x, 则函数ƒ是一个_________射, 17.设函数ƒ: RR,则
f(x)x22,函数g: RR, g(x)x4
fg____,gf____.f1(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:AB,f(i)182i,iA,设H1,2,5,6,A,则f(H)______,设G4,8,10,16B,则f1(G)_____.19.含10条边的图的总度数是____________.20.含有8个顶点的完全图共有______条边.21.含6个结点,9条边的无向连通图,要得到此图的一棵生成树,必须删去__条边.22.不同构且有6个结点的树共有______个.23.简单图G=
((PQ)(QP))(PQ的真值为__________________.31.公式A含两个命题变元P,Q,其主析取范式为:
(PQ)(QP)),则它的主合取范式是______________.二、选择题
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,yA},则关 系 具有的性质是().A)自反的;B)对称的;C)传递的,对称的;D)反自反的,对称的;
3.设集合X={-1,1,2,3}与Y={1,2,3,4,5,9}, ƒ(x)=x2,是XY的一个函数,则下列 正确的是().A)ƒ是内射但不是满射;
B)ƒ是满射但不是内射;C)ƒ是双射;
D)ƒ既不是入射也不是满射;
4.设I为整数集合.A={x | x2<30,xI}, B={x | x为质数,x<20}, C={1,3,5}, 则(C-A)(B-A)=().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);中是永真式的公式有()个.A)0;B)1;C)2;D)3;
6.下面论断正确的是().A)有补格一定是分配格;B)有补格一定是有界格;C)任何一个格必有最大元;D)偏序集就是格;
7.下列命题中错误的是().A)若L为有限集,则格
B)在格
D)在有补分配格
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(PQ))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)|xA,yB且y=x2}, 1)写出的所有元素;
2)求出关系的定义域及值域;3)写出关系的关系矩阵M;4)判断关系是否为AB的一个函数? 2.设集合A={1,2,3,4},是A上的一个关系,的关系矩阵如下:
求:的自反闭包r(),对称闭包s(),传
递闭包t().4.设集合A={1,2,3,6,12,24,36,72},A上的整除关系={(a,b)|a,bA且a|b}.1)画出偏序集的次序图;2)A的子集B={6,24,36},求集合{x|xA,且x能整除B中的每一个整数},并求集合{x|xA,且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的邻接矩阵如下:
011000 110000100010110010010100000100
求图G的所有割点、割边.8.有向图G=
1)
2)3)4)5)
求G的邻接矩阵;求deg(V1);
从结点V2到V4长度为3的路有几条? 图中长度为2的回路有几条? 求d(V1 , V4)
9.求下面有权图的一棵最小生成树.并求出最小权数.10.求公式(P(QR))(R(QP))的主析取范式和主合取范式.11.掌握欧拉图、哈密顿图的判定.(教材P227页第16、17、18题)
五、证明题
1.证明: P(QR)Q(PR)2.证明:(Q(PP)(R(PP))R 3.用推理规则证明: 1)(PQ)R, SU, RS, UW, WPQ.2)证明:QS是前提,PQR, Q(RS), P的有效结论.4.试给出以下推理证明: 若这里举行足球赛,则交通就会很拥堵.若他们按时到了球场,则说明交通是畅通的.他们按时到达了.所以这里没有举行足球赛.5.设
9.证明:在(n,m)的树中,m = n-1 6
第二篇:离散数学复习题
离散数学复习题
• 设命题p,r的真值为1,命题q,s的真值为0,则(p→q)(﹁r→s)的真值
为。
• 只要4不是素数,3就是素数,用谓语表达式符号化为。
• D={},则幂集ρ(D)=
• A={a,{b}},B={},则A×B=
• 若集合A,B的元素个数分别为|A|=m,|B|=n,则A到B有种不同二元关系。• 设A={1,2,3,4},B={4,5,6,7},R={<1,4>,<1,6><2,4>,<3,5>,<3,6>}是由A
到B的二元关系,则domR=,ranR=
• I A是集合A上的恒等关系,A上的关系R具有性当且仅当IAR。• 二元关系R是等价关系,当且仅当的R是。
9.设K4是有4个点的无向完全图,则K4有条边。
10.无向图G是欧拉图当且仅当。
11.在任何无向图这,所有顶点的度数之和等于边数的倍。
12.设K5是有5个点的无向完全图,则K5有条边。
13.无向图G是欧拉图当且仅当。
计算题
• 求公式(PQ)→(QR)的主析取范式
• 集合A={a,b,c},R={,,,
闭包r(R),对称闭包s(R)和传递闭包t(R)(用矩阵运算),并画出各闭包的关系图。• 设图G
• 写出G的邻接矩阵
• 求各结点的初度,入度
• 求V3到V2长度是3的路的数目
• 设集合A={1,2,3,4,6,8,12},R是A上的整除关系,• 画出偏序图的哈斯图;
证明题
• 在自然推理系统p中构造下面推理的证明
前提:﹁r,﹁pr,(q)→p
结论:q→﹁
• 在自然系统p中构造下面推理的证明
前提:pq,p→r,q→s
结论:sr
第三篇:离散数学复习题
离散数学复习题
一、填空
1、命题中的否定联接词;蕴含联接词
2、一个命题公式,若在所有赋值下取值为真,则称此公式为式;若……假,则……..为 永假 式;若至少存在一组赋值,其命题为真,则…….为可满足式。
3、有限布尔代数只能有n4、R是定义在集合上的二元关系,若R满足性、性,则称R是A上的等价关系。
5、全序集(A,≤)必是,且是
6、n阶m条边无向图G是树,当且仅当G是连通点,且m=
7、若有向树G中,有一个顶点的入度为,则称G为根树。
8、有序对
(1)当x不等于y时,
(2)
9、关系的性质五。
10、图中顶点作为边的端点的称为此顶点的度数。
11、设X是格,并对交运算时可分配的,则且 格中的交运算对并运算是可分配的。
12、有向图按连通图分为三类连通图、连通图、连通图。
13、T 为一颗根树,若T的每个分支点则称T为r元正则树。
14、设A、B是集合,求A与B之间关系(属于、不属于、包含…)如果A={1},B={1,{1,2}},则A不属于B、A不包含B15、若R是定义在集合A上的一个二元关系,若R满足、性、可传递性则称R是偏序关系。
16、设集合A={1,2,3,4},A上二元关系R={<1,1><1,3><2,1><3,3><3,4><4,3>},则逆序关系R−1。
17、在有补分配格中,每个元素(的补元)都是的。
18、在无向图中,度数为奇数的顶点个数必为数。
19、若图中通路P中所有边互不相同,则称P为通路,若通路中所有顶点互不相同,则称P为 基本 通路。
二、简述题
1、偏序关系与格
2、设R是A爱上的二元关系,如果R是自反的,反对称的,传递的二元关系,则称R是A上的偏序关系或者半序关系;
2、等价关系与集合的划分
3、握手定理
4、对偶式与对偶原理
5、正规子群
6、什么是域,有限整环是不是域,为什么?
7、集合的基本运算公式(集代数公式)有哪些?
8、群论中的拉格朗日定理
9、主析取范式与主合取范式
10、鸽巢原理与计数原理
三、判断题
1、设A,B是集合,则A⨁=
2、偶数阶循环群有且只有一个2阶元素
3、设(G,∗)是n阶群,且有k阶子群,则k丨n4、有限格必是有界格
5、偶数阶群中比存在非幺元a,使得a∗a=e6、不存在含有奇数个面且每个面上有奇数条棱的多面体
7、设(A,∗)是独异点,B是A的子集,且(B,∗)是独异点,则(B,∗)一定是(A,∗)的子独异点8、3阶群同构意义下唯一
9、(N=(0),⊗)是一个群
10、素数阶群一定没有非平凡子群
四、计算题
1、求命题公式P∧(Q→R)主析取范式。
2、写出3次对称群(S3,∗)的运算表及所有正规子群。
3、在1,2,3…….100这100个自然数中,可以被2或3整除但不能被5整除的数有多少个?
4、设, A =3,P B=64,P A⋃B=256,求 B , A⋂B , A−B , A⊕B。
5、设A={a,b,c,d},R={(a,c),(c,b),(b,a),(a,d)},求R,r R ,s R ,t(R)的关系矩阵或关系图
6、命题公式 P∧Q ∨ −P ∧(−Q)的真值表
7、写出群(N13− 0,⨂13)各元素之阶数
8、集合A={1,2,3,6,8,12},求A 上的整除关系R并画出Hasse图
9、写出((a−4b)c−(7b+d))+(c+8a)的前缀式和后缀式
10、求(N6,⨂6)群的自同态
五、证明题
1、证明(N13− 0,⨂13)是循环群
2、证明不存在含有奇数个面且每个面上有奇数个棱的多面体
3、设(A,∗)是代数系统,R是(A,∗)上的同余关系,(A R,∗)是其商代数,设f是A到A/R的函数,对于A中任意元素a,都有f a = a R
证明:f是(A,∗)到(A R,∗)的同态映射
4、设T是完全k元树,若分枝点为i,树叶数为t,证明:i=(t−1)/(k−1)
5、证明偶数阶群必有二阶子群,且必有奇数个二阶子群
6、R是集合A上的等价关系,证明:对任意x,y属于A在此处键入公式。
(1)若xRy,则 x R= y R
(2)若(x,y)∉R,则 x R∩ x R=∅
7、证明下列说法是等价的(1)A≤B(2)A−B=∅(3)A∩B=A(4)A∪B=B8、证明逻辑等价式P↔Q⟺ P⋀Q ⋁(−P⋀−Q)
9、证明10阶群必有5阶子群
第四篇:离散数学复习题1
逻辑
1、给出的真值表
2、证明为永真式 谓词量词和推理
1、使用量词和谓词表达不存在这一事实
2、证明前提“在这个班上的某个学生没有读过书”和班上的每个学生都通过了第一门考试蕴含结论“通过考试的某个人没有读过书” 集合、函数、数列与求和
1、全集为,求集合A=的位串?它的补集的位串是什么?写出集合A=的所有子集,写出集合
2、从集合到集合能定义多少个函数?下面给出的函数其定义为:该函数是双射吗?是满射吗?该函数是否存在逆函数?如果存在请给出其逆函数。计数
1、计算机系统的美国用户有一个6~8个字符构成的密码,其中每个字符是一个大写字母或数字,且每个密码必须至少包含一个数字,问总共有多少个合适的密码?
2、在30天的一个月里,某棒球队一天至少打一场比赛,但最多打45场。证明一定有连续的若干天内这个球队恰好打了14场比赛
3、证明n个元素的集合中允许重复的r组合数等于
4、按照字典顺序生成整数1,2,3的所有排列(不允许重复),在362541后面按照字典顺序的下一个最大排列是什么?找出在1000100111后面的下一个最大的二进制串。关系
1、求下面给出关系R的自反闭包、对称闭包和传递闭包的0-1关系矩阵,其中
2、S是所有比特串的集合,关系定义为当s=t或者s和t的长度至少是3,且前3个比特相同时具有关系,例如0101,0011100101,但01010,0101101110。证明是S上的等价关系,由产生的S的等价类是那些集合?
3、偏序集({2,4,5,10,12,20,25},|)的那些元素是极大的,那些元素是极小的? 图与树
1、在下图所示的图中,从a 到d的长度为4的通路有几条?该图是否是Euler图,是否是Hamilton图,该图的度序列是什么?该图是否可平面,如果是请给出平面画图,该图的点色数和边色数等于多少?给出该图的一个生成树,2、求下面赋权图从a到z的最短距离是多少?最短路径是什么?(画图给出标号过程)
3、用哈夫曼编码方法来编码下列符号,这些符号具有下列频率:A:0.08,B:0.10,C:0.12,D:0.15,E:0.20,F:0.35,该编码方法编码一个字符的平均位数是多少?
4、下面树的高度是多少?那些节点是内部节点,那些节点是叶子节点,该树是否是3元正则树?分别给出该树节点的前序、中序、后序遍历的节点访问次序
第五篇:离散数学复习题(期末测试卷)
复习题
一、填空题(请将每空的正确答案写在答题纸相应位置处,答在试卷上不得分。每小题2分,共16分。)
1.谓词公式xy(P(x,y)Q(y,z))xR(x,y)中x的辖域是。
2.命题公式(pq)的成真赋值为。
3.在1和1000之间(包括1和1000在内)不能被4和5整除的数有个。
4.设R是定义在集合A{1,2,3,4}上的二元关系R{1,1,1,2,2,3,1,4},则R的对称闭包s(R)。
5.A{1,2,3,4},xymin{x,y},则代数系统A,中的零元是。
6.具有10个结点的无向完全图的边数=。
7.一次同余方程3x1(mod5)的最小正整数解是。
8.84与198的最大公约数是。
二、单项选择题(从下列各题四个备选答案中选出一个正确答案,并将其代号写在答题纸相应位置处。答案错选或未选者,该题不得分。每小题2分,共16分。)
1.设F(x): x是有理数,G(x):x能表示成分数。在一阶逻辑中,命题“没有不能表示成分数的有理数”可符号化为()。
A.x(F(x)G(x))B.x(F(x)G(x))
C.x(F(x)G(x))D.x(F(x)G(x))
2.设个体域是整数集,则下列命题的真值为真的是()。
A.yx(xy1)B.xy(xy0)
C.xy(xyy2)D.yx(xyx2)
3.集合A{1,2,,10}上的关系R{x,y|xy10,x,yA},则R的性质为()。
A、自反的B、传递的、对称的C、对称的D、反自反的、传递的4.对自然数集合N,下列定义的运算中()是不可结合的。
A.abab3B.aba2b
C.abab(mod 3)D.abmin{a,b}
5.下列各图中既是欧拉图,又是汉密尔顿图的是()。
A.B.C.D.
6.对于下列度数序列,可画成简单无向图的是()。
A.(1,1,1,2,3)B.(1,2,2,3,4,5)
C.(1,2,3,4,5,5)D.(2,3,3,4,5,6)
7.含有5个结点、3条边的不同构的简单图有()个。A.2B.3C.4D.5【】
8.5的模6逆等于()。
A.1B.
3C.4D.5
三、计算题(第1、2、3、4小题各7分,第5、6小题各8分共44分。)1.求命题公式(pq)(pr)的主析取范式和主合取范式。
2.设A,R为偏序集,其中A{1,2,3,4,6,9,24,54},R是A上的整除关系。(1)画出A,R的哈斯图;(2)求A中的极大元;(3)令B{4,6,9},求B的上确界和下确界。3.求下图1中带权无向图的最小生成树,并求出该最小生成树的权值。4.求解递推方程:an7an112an20,a04,a16。5.有向图D如图2所示,求:(1)D中v1到v3长度为3的通路有几条?(2)D中v1到v1长度为3的回路有几条?(3)D是哪类连通图?
v
4图1图
2v
36.在通讯中要传输字母a,b,c,d,e,f,g,它们出现的频率为:
a:30%,b:20%,c:15%,d:10%,e:10%,f:9%,g:6%,设计传输上述字母的最佳二元前缀码,画出最优树,并求传输100个按上述频率出现的字母所需二进制字个数。
四、证明题(每小题8分,共16分。)1.设R为自然数集N上的关系,定义N上的关系R如下:x,yRxy是偶数。(1)证明R为等价关系;(2)求商集N/R。2.设Z为整数集合,在Z上定义二元运算如下:证明:x,yZ,xyxy2,Z,是群。
五、符号化下列命题,并在自然推理系统P中论证结论的有效性(8分。)
若小张喜欢数学,则小李或小赵也喜欢数学。若小李喜欢数学,则他也喜欢物理。小张确实喜欢数学,可小李不喜欢物理。所以,小赵喜欢数学。
参考答案
一、填空题(请将每空的正确答案写在答题纸相应位置处,答在试卷上不得分。每小题2分,共16分。)
1.P(x,y)Q(y,z)2.10,11,003.600
4.{1,1,1,2,2,3,1,4,2,1,3,2,4,1}5.1 6.457.38.6
二、单项选择题(从下列各题四个备选答案中选出一个正确答案,并将其代号写在答题纸相应位置处。答案错选或未选者,该题不得分。每小题2分,共16分。)
1.C2.C3.C4.B5.C6.A7.C8.D
三、计算题(第1、2、3、4小题各7分,第5、6小题各8分共44分。)
1.解:主合取范式为:(5分)
(pq)(pr)(pq)(pr)
((pq)(rr))((pr)(qq))(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)M4M5M6
主析取范式为:(2分)
(pq)(pr)m0m1m2m3m7
(pqr)(pqr)(pqr)(pqr)(pqr)2.解:(1)A,R的哈斯图如下图所示。(3分)
429(2)A中的极大元是:24,54;(2分)
(3)B的上确界:无;B的下确界:1。(2分)3.解:所求该图的最小生成树如下图所示。(5分)
该最小生成树的权值之和
W(t)=2+1+1+2+3+4=13(2分)
4.解:其特征方程为:x27x120,其特征根是:x13,x24(2分)
通解为:anc13nc24n(2分)
代入初值得到:c1c24,3c14c26
解得:c110,c26(2分)
所以,原方程的解为:
an103n64n。(1分)
5.解:先求图D的邻接矩阵A及A2、A3。
11A
0
1110
220112,(1分)A1001
0001
122
541113,(2分)A1000
1102
233
232(2分)110
122
(1)D中v1到v3长度为3的通路有3条。(1分)(2)D中v1到v1长度为3的回路有5条。(1分)(3)D是强连通图。(1分)
6.解:按字母顺序,令pi为传输第i个字母的频率,i1,2,,7,则传输100个字母,各字母出现的频数为wi100pi,得
w130,w220,w315,w410,w510,w69,w76。将它们按照从小到大顺序排列,得691010152030。(2分)以wi为权求最优2叉树如下图所示。
6(4分)
传输的前缀码分别为:a01,b11,c001,d100,e101,f0001,g0000。传100个所需二进制数字个数为:
W(t)=15+30+60+100+40+20=265。(2分)
四、证明题(每小题8分,共16分。)1.(1)证明:
xN,因为xx2x,2xN且是偶数,于是x,xR,因此R在N上是自反的;(1分)
x,yN,若x,yR,则xy是偶数,即yx是偶数,于是y,xR, 因此R在N上是对称的;(1分)
x,y,zN,若x,yR且y,zR,则xy2k1yz2k2,k1,k2Z,于是xz(xy)(yz)2y2(k1k2y),进而x,zR,因此R在N上是传递的;(2分)
综上所述,R是N上的等价关系。(1分)
(2)N关于等价关系R的所有等价类为[0]R{0,2,4,6,}和[1]R{1,3,5,7,},则N/R{[0]R,[1]R}。(3分)
2.证明:显然,Z关于是封闭的。(1分)
对于任意x,y,zZ,由于
(xy)z(xy2)z(xy2)z2xyz4,而 x(yz)x(yz2)x(yz2)2xyz4,于是
(xy)zx(yz),即满足结合律。(2分)
(2分)xZ,因为x2x22x2x,因此2是Z关于的单位元。
xZ,由于4xZ且x(4x)x(4x)22(4x)x,于是
x关于存在逆元4x。(2分)所以,Z,是群。(1分)
五、符号化下列命题,并在自然推理系统P中论证结论的有效性(8分。)解:设简单命题
p:小张喜欢数学。q:小李喜欢数学。
r:小赵喜欢数学。s:小李喜欢物理。(2分)前提:p(qr),qs,p,s 结论:r
(或写为:推理形式为p(qr),qs,p,sr)(1分)证明:
(1)qs前提引入(2)s前提引入
(2)拒取式(2分)(3)q(1)
(4)p(qr)前提引入(5)p前提引入
(5)假言推理(2分)(6)qr(4)
(6)析取三段论(1分)(7)r(3)