离散数学复习题全.docx
- 文档编号:16249107
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:13
- 大小:47.58KB
离散数学复习题全.docx
《离散数学复习题全.docx》由会员分享,可在线阅读,更多相关《离散数学复习题全.docx(13页珍藏版)》请在冰点文库上搜索。
离散数学复习题全
)
全(离散数学复习题.
离散数学复习资料一、填空
命题“对于任意给定的正实数,都存在比它大1.
则命题的:
x为实数,的实数”令F(x)y?
y):
xxL(。
逻辑谓词公式为
米500米冠军,王大力是设王大力是1002.:
qp:
100冠军,在命题逻辑中,命题“王大力不但是米冠军”的符号化形式米冠军,而且是500为。
命题“存在一个人不但是100米冠军,而且是500米冠军”的符号化形式为____。
3.选择合适的论域和谓词表达集合A=“直角坐标系中,单位元(不包括单位圆周)的点集”则A=。
4.设P(x):
x是素数,E(x):
x是偶数,O(x):
x是奇数N(x,y):
x可以整数y。
则谓词的自然语言是对于任意)))?
xN(yyyxx?
(P()?
?
(O()
一个素数都存在一个奇数使该素数都能被整
除。
5.设个体域是,谓词公式写成不)xPx()(?
xb}{a,(?
)Px?
?
)(2
。
含量词的形式是
式前束范的6.谓词))u,y,))(?
x?
y?
z(P(x,z)?
P(y,z?
?
uQ(x。
为
式题公7.合取范式命的主)))?
R(Q?
(?
QA?
P?
(?
P?
。
,其编码表示为为
记A的绝对补,,称为8.设E为全集,
,,~E=作~A,且~(~A)=
。
=~?
B
A-B=,A?
,9.设则4},{13,,B?
{23,4},C,A={2?
5,6},C=。
=A,×,子集虑下列考10.设}c,ab,A?
{}},b?
S{{a,},{bc1,}}a,cbS?
{{a},{a,},{2,,,}},Sc?
{{a},{c{{a},{b,}}c?
S{{a},{b},{}}a?
SS,,?
{{abc}}6534。
的划分有A则的覆盖有,A,设11.
}Zx?
2?
{x1x?
12,x被整除,?
M,,则}Z?
3整除,x被?
xN?
{1?
x12,x?
?
NM
。
?
?
MN设12.3,A={<1,2>,<24>,<3,>},
,B={<1,3>,<2,4>,<4,2>},则=B?
A3
。
=BA?
系元关6},A上二A={113.,2,3,4,5,的;TT=,则用列举法}|x?
y是素数T?
{?
x,y?
性质。
关系图为,T具有
,则14.的哈斯图为偏序集?
?
RA?
。
=R?
上的二元运算为普,定义设A15.n}2x?
n?
NA?
{x|中运算通乘法、除法和加法,则代数系统运算具*关于
有封闭性。
16.A,B,C表示三个集合,文图中阴影部分的集合表达式为。
A
B
设图G=
V{,,,41324
1100?
?
?
?
1011的出度,,则的入度=?
?
?
?
Avv)g(dev?
?
1140011?
?
?
?
0010?
?
,从到的长度为2的路径有=?
vv)g(ved442条。
)的简单连通平面图的边数为(结点数18.n3n?
与n。
的关系为m<=3n-6m,则m数函N自然数集上的19.设f,g是。
,则?
xf?
g)?
2x()?
N?
x?
f(x)?
x1,g(x的同余类组成3设I是整数集合,Z是由模20.3如义+下:
同余类集,在Z上定的33>;,+ ][j]? i[(? [i33+3。 是否构成群 为上的二元运算*γ,δ},21.集合S={α,β δβγα* αδαβγ βαβγδ γβγγγ δαδγδ 那么,代数系统 。 元是 运算如下: 设<{a,b,c},*>为代数系统,*22. cb*a caab a bbc ccc c 。 则它的幺元为;零元为 R={,<,c}A上二元关系23.设A={a,b,Ra,b>,, = 324.设>}>,<3A={<1,2>,<2,4 ,=B={<1,3>,<2,4>,<4,2>},则BA? =。 B? A 不是等价25.设集合X={1,2,3},下列关系中 的。 A={<1,1>,<2,2>,<3,3>} B={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>} C={<1,1>,<2,2>,<3,3>,<1,4>} >,<1{<1,1>,<2 D= 2, 6 2>,<2,1>,<1,3>,<3,1>,<3,3>,<2,3>,<3,2>} 设;,则26.r(R)=,? ? 2,4? RX}? 3,3? ? {1,2,3,4},? {? 1,2。 t(R)=s(R)=; 的边数G阶完全图,则27.设G是n。 m= 的哈斯,其上偏序关系Rb设A={a,,c,d}28. 图如右图所示: 则。 R= 。 的边数为29.n阶完全图Kn )的简单连通平面图的边数为(30.结点数n3n? 。 m,则m与n的关系为 。 31.图的补图为 长度到vv32.有向图中从21为2的通路有条。 G为9阶无向图,每个结点度数不是33.设5就7 度结点。 个5中至少有是6,则Gn-1的度数d(v)=。 34.n阶完全图结点v 二、证明 1.不构造真值表证明蕴涵式 Q? ? R? ? P)))? (R? (R? (P((Q? P? ? P))2.证明FA? E? F? ? ? B? CD,D? A3.证明(P∧Q)∨(P∧? Q)? P 4.证明R)? ? ? QQ? R))? (PP((? 5.证明)x? xQ(? ? xP(x)? ? x(P(x)? Q(x))6.证明)xxQ(xxP()? ? P(x)? Q(x))? ? ? x(7.用推理规则证明下式: 前提: )(xx)Qx)P(),(? ))Q((P(x)? (x))? R(x,(? x? (? (x)Px)? x结论: ))y? R(y)(P(x))((? x? 8.设论域D={a,b,c},求证: 。 ? xA(x)? ? xB(x)? ? x(A(x)? B(x))9.设是复合函数,如果满射,则也是满射。 gf? gg? f10.假定,且是一个满射,g是个fg? ? : ? : fABgBC入射,则f是满射。 8 11.用反证法证明。 R? )? S? ? R)(Q? SQ(P? )? (P12.设是一个群,设I={x|x=2n,n∈I},E证明是的一个子群。 E 三、按要求解答 1.将谓词公式化为前束析取)y)R((Q(y))? ? y? xx((? )P()? (y)范式与前束合取范式。 2.用推理规则论证: 如果今天是星期六,我们就要到颐和园或圆明园玩,如果颐和园游人太多,我们就不去颐和园玩。 今天是星期六,颐和园游人太多,所以,我们去圆明园玩。 3.符号化语句: “有些人喜欢所有的花,但是人们不喜欢杂草,那么花不是杂草”。 并推证其结论。 4.用推理规则论证: 或者逻辑难学,或者有少数学生不喜欢它;如果数学容易学,那么逻辑并不难学。 因此,如果许多学生喜欢逻辑,那么数学并不难学。 9 5.设有下列情况,用推理规则论证结论是否有效? (a)或者天晴,或者下雨。 (b)如果天晴,我去看电影。 (c)如果我去看电影,我就不看书。 结论: 如果我在看书则天在下雨。 6.符号化语句: “有些病人相信所有的医生,但是病人都不相信骗子,所以医生都不是骗子”。 并推证其结论。 7.给定3个命题: P: 北京比天津人口多;Q: 2大于1;R: 15是素数。 求复合命题: )P? ? R? (QR)? (的真值。 8.将化为与其等价的前束范)))xR(zQ(z)? x? (? yP(,y))? (? ? x(式。 9.把公式转化为前束范式? ? ? ? ? ? ? ? x? ? xxx? QP10.求的主合取范式。 )Q(? P? )(Q? P? 11.求(A? B? C)? (? A? (? B? ? C))的主析取范式与主合取范式。 10 PQR的主析取范式与主合取范式。 ()∨? 12.求13.设命题A,A的真值为1,A,A真值为0,4312求命题 的真值。 )A(A? ? (A? ? A)))? ? (A? (A4123121求集合14.的并与交。 ? ? (n? 1,2,3,? )Ax? 0? x? ? ? nn? ? 15.设X={1,2,3,4,5},X上的关系R={<1,1>,<1, 2>,<2,4>,<3,5>,<4,2>},求R的传递闭包t(R)。 16.设集合上的关系}b,c,d,X? {a。 求的传递闭包。 ? ? ? c? ? b,c? c? R? ? ab? ? b,a)Rt(R17.在实数平面上,画出关系,并判定关系的特殊性? ? 0? ? 2y? 0? x? yR? ? x,y? x? ? 2质。 设,R是X上的二元关系,R={ 上整”,设S={1,2,3,4,6,8,12,24}“为S? 除关系,问: (1)偏序集的哈斯图如何? (2) ? ? ? S偏序集 (1)画出R的关系图。 (2)写出R的关系11 矩阵。 (3)说明R的性质 19.A={a,b,c,d},R={,,, 20.的极小元、最小元、极大元、最大元是什 }S? {么? 21.集合上的偏序关系为整除关}3624,6,12,,A? {2,3系。 设,,试画出哈斯图,并求}632,126,},C? {? B{A,B,C的最大元素、极大元素、下界、上确界。 22.对于实数集合R,在下表所列的二元远算是否具有左边一列中的性质,请在相应位上填写“Y”或“N”。 MaxMin+ 可结合性可交换性存在 12 幺存零元*如下表,23.设B4={e,a,b,ab},运算 * aeabbaeeabbeaaabbaeabbbeaababb Klein是一个群(称作四元群)。 *> (24.设S=R-{-1}R为实数集),ab? aba? ? ? b中解()说明2)在是否构成群;1(? ? S? S方程。 7? ? 2x? 3设25.是,RX上的二元关系,,X1={,,234}},11{R=? ,? ? ? ,1,4,? 34? ,2,3,? 33? ,3,1,? 13,? ? ,? ? ,? ? ? 2,1? ,? 24,的关系矩阵。 说的关系图。 写出画出 (1)RR13 R是否是自反、反自反、对称、传递的。 明是负整数集合,定义二个双射函数,26.设Igf、? ? ? },<-3,3>,? ? ,? ? 2,2? x? ? ? {? ? 1ff: I? I,1x? ? ,? ? N? g: ,1,0? ? 2,1? <3,2>,? }gIx? ? x1? {? ? ,并说明其是否是双射函数。 求fg表示平面上,180o,300o}M={0o,60o,120o,240o27.设 定义一个二元几何图形顺时针旋转的六种位置,图形旋转有a*b=,对M中任一元素a,b运算*。 时即为0o(a+b)的角度,并规定当旋转到360o *0o60o120o180o240o300o 300o0o0o60o120o180o240o0o60o60o120o300o180o240o 60o120o120o180o0o240o300o 120o180o180o240o60o300o0o 180o300o0o60o120o240o240o60o180o120o240o300o300o0o 28.求图中的一棵最小生成树。 14 v0010? ? 1? ? v0101? ? 2? A? ? v1011? ? 3? ? 29.已知某有向图的邻接矩阵如下: v0010? ? 4试求: 到的长度为4的有向路径的条数。 vv3130.下图所示带权图中最优投递路线并求出投递路线长度(邮局在D点)。 求图的可达矩阵,并判断图的连通31.性。 32.有向图G如图所示,试求: (1)求G的邻接234(3)v到v。 A (2)求出A、A和A长度矩阵41为1、2、3和4的路径有多少? (4)求出可达矩阵P。 15 3V画一个有一条汉密尔顿回路的图。 画一个有33.有一条欧拉回路,但有一条汉密尔顿回路的图。 画一个一条欧拉回路和一条汉密尔顿回路的图。 有一条欧拉回路,但没下面两图是否同构,若是给出点集间的同构34. 映射。 43度结点、个2个2度结点、335.已知某树有。 (无其它度数点)4度结点,问有几个叶子点个 图给出的赋权图表示五个城市36.vv,v,,vv,12345及对应两城镇间公路的长度。 16 试给出一个最优化的设计 方案使得各城市间能够有公路连通。 17中的幺元是,α的逆5
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 复习题