离散数学习题_离散数学习题答案

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

集合论

1.A={,1}，B={{a}}求A的幂集、A×B、A∪B、A+B。2.A={1,2,3,4,5}, R={(x,y)|x

4.A={a,b,c},R= IA ∪{(a,b),(b,a)}，求a和b关于R的等价类。

5.R是A上的等价关系，A/R={{1,2}，{3}},求A，R。6.请分别判断以下结论是否一定成立，如果一定成立请证明，否则请举出反例。

①如果A∪BC，则AC或者BC。②如果A×B=A×C且A，则B=C。

27.如果R是A上的等价关系，R,r(R)是否一定是A上的等价关系？证明或举例。

8.已知A∩CB∩C,A-CB-C,证明：AB。9.证明：AX(B∩C)=(AXB)∩(AXC)10.证明：P(A)∪P(B)P(A∪B)-111.证明：R[sym] iff R=R

-1212.证明：r(R)=R∪IA,S(R)=R∪R,t(R)=R∪R∪...13.证明：s(R∪S)=s(R)∪s(S)14.R是A上的关系，证明：如果R是对称的，则r(R)也是对称的。

15.I是整数集，R={(x,y)|x-y是3的倍数}，证明：R是I上的等价关系。

16.如果R是A上的等价关系，则A/R一定是A的划分。17.R是集合A上的自反关系，S是A上的自反和对称关系，证明t(R∪S)是A上的等价关系。18.I是正整数集合，R是I×I上的二元关系，R={,>|xv=yu},证明：R是等价关系。

19.f:AB，R是B上的等价关系，令S={|xA且yA且R}，证明：S是A上的等价关系。

20.R是集合A上的自反关系，S是A上的自反和对称关系，证明t(R∪S)是A上的等价关系。

21.P和Q都是集合A上的划分，请问P∪Q，P-Q是否是A上的划分，22.RAXA,R[irref]且R[tra],证明：r(R)是A上的偏序关系。

23.画出{1,2,3,4,6}上整除关系的哈斯图，求{2,3,6}的4种元素。

24.A={a,b,c,d,e,f,g},R={(a,c),(a,e),(b,d),(b,f),(d,e),(d,f)},S=tr(R),画出S的哈斯图并求{b,c,d,f}的极大元等8种元素。

25.f:A→B,g:B→C都是单（满）射，证明：复合映射gof一定是单（满）射。

26.f:A→B,g:B→C，gof是单射，请问f和g是否一定是单射？请证明或举出反例。27.R是实数集，f:R×RR×R,f()=,请问f是否为单射？是否为满射？分别证明或举反例。28.已知B∩C=,令f：P(B∪C)P(B)×P(C)，对XP(B∪C),令f(X)=(B∩X,C∩X),证明：f是双射。

代数系统

1.是模8加群，Z8={0,1,2,3,4,5,6,7},+8是模8加法，求出的单位元、每个元素的逆元、所有的生成元和所有的子群。

2.求的单位元，零元，每个元素的逆元，每个元素的阶，它是循环群吗？求出它所有的子群。

3.R是实数集，在R上定义运算*为x*y=x+y+xy,问：是代数系统吗？有单位元吗？每个元素都有逆元吗？ ***4.R是非零实数集合，是代数系统，对于R中元素*x,y，令xoy=2x+2y-2。请问中是否存在单位元、零元、哪些元素有逆元？运算o是否满足交换律和结合律。分别说明理由。

5.R是实数集，R上的6运算定义如下：对R中元素x,y，f1()=x+y；f2()=x-y；f3()=xy；f4()=x/y；f5()=max{x,y}；f6()=|x-y|。问：哪些满足交换律、结合律、有单位元、有零元？说明理由。

6.是一个群，证明：G是交换群当且仅当对任意G中222元素x,y,都有等式(xy)=xy成立。

7.证明：如果群G中每个元素的逆元素都是它自已，则G是交换群。

8.循环群一定是交换群。

9.证明：阶为素数的群一定是循环群。

-110.是一个群，uG,定义运算*：x*y=xouoy, 证明：是一个群。

11.整数集Z上定义运算*：对任意整数x和y,x*y=x+y-4,其中+，-为普通加减法。证明：是一个群。

12.证明：如果群G中至少有两个元素，则群中没有零元。13.S是G的子群，证明：{x|x是S的左陪集}是G的一个划分

14.是一个群,aG,n是a的阶(周期)，证明：k是的一个子群。

15.H，K都是群G的子群，请问H∩K,H∪K,H-K是否一定是G的子群？ 16.H，K是G的两个子群，aG, 试证：aHaK当且仅当HK。17.G={1,3,4,5,9},*是模11的乘法(即x*y=xy mod 11)，请问(G,*)是否构成群？

n18.是群，e是单位元，aG,a的阶为k,证明：a=e当且仅当 n是k的倍数。

19.S是G的子群，证明：{x|x是S的左陪集}是G的一个划分

20.G是群，证明：S={aG|xG(ax=xa)},则S是G的子群。21.是偶数阶群，则G中必存在2阶元素。22.证明：6个元素的群在同构意义下只有两个。

++23.R为实数集，R为正实数集，与是否同构？ 24.是有限群，证明：G不可能表示成两个真子群的并。25.图论

1.如何判断二部图？完全图、完全二部图的边数。2.如何求E回路？

3.Petersen图是否为E图或H图。

4.哪些完全图是H图？哪些完全图是E图？ 5.n为何值时轮图为H图？ 6.如何求最小生成树。

7.证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。8.证明：如果G是欧拉图，则其边图L(G)也是欧拉图。9.证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。10.G是平面图，G有m条边，n个顶点，证明：m3n-6。并由此证明K5不是平面图。

11.证明：有6个顶点的简单无向图G和它的补图中至少有一个三角形。

12.证明：在至少有两个顶点的无向树中，至少有2个一度顶点。

13.G是无向简单连通图，G有n个顶点，则G最少有几条边，最多有几条边？

14.证明：简单无向图G和它的补图中至少有一个是连通图。15.证明：无向图中奇度点（度数为奇数的点）有偶数个。16.证明：n个顶点的无向连通图至少有n-1条边。17.G是H图，V是G的顶点集，证明：对任意顶点集S，SV，都有ω（G-S）≤|S|。其中ω（G-S）表示G-S的分图数目。18.一棵无向树有3个3次点，1个顶点次数为2，其余顶点次数为1，问它有几个次数为1的顶点？写出求解过程。19.证明：每个简单平面图都包含一个次至多为5的顶点。20.连通平面图G有n个顶点，m条边和f个面，证明：n-m+f=2。21.如果图G的最大顶点次数≤ρ，证明：G是ρ+1可点着色的。

22.G是无向简单连通图，G有n个顶点，则G最少有几条边，最多有几条边？

23.如果一个简单图G和它的补图同构，则称G是自补图，求所有4个顶点自补图。

24.G是平面图，G有m条边，n个顶点，证明：m3n-6。如果G中无三角形，则m2n-4。数理逻辑

1.如果今天是星期一，则要进行英语或数理逻辑考试。

没有不犯错误的人。整数都是有理数。有的有理数不是整数。

不存在最大的整数。有且只有一个偶数是素数。2.求真值表及范式：P(┓QR)、(┓QR)(PR)3.推理：

p(qr)，┓s∨p，q ├ sr pr，qs，p∨q ├ r∨s p∨q，p┓r，st，┓sr，┓t ├ q p(┓(r∧s)┓q),p,┓s ├ ┓q 4.如果小王是理科学生，他一定会学好数学。如果小王不是文科学生，他一定是理科学生。小王没学好数学。所以小王是文科学生。

5.判断各公式在给定解释时的真假值，并且改变论域使该公式在新的解释下取值相反。论域：D={-2,3,6}, F(x):x≤3, G(x):x>5, R(x,y):x+y