离散数学习题及答案.docx
- 文档编号:15862552
- 上传时间:2023-07-08
- 格式:DOCX
- 页数:18
- 大小:26KB
离散数学习题及答案.docx
《离散数学习题及答案.docx》由会员分享,可在线阅读,更多相关《离散数学习题及答案.docx(18页珍藏版)》请在冰点文库上搜索。
离散数学习题及答案
离散数学习题及答案
【篇一:
《离散数学》题库及答案】
>一、选择或填空
(数理逻辑部分)
1、下列哪些公式为永真蕴含式?
()
(1)?
q=q→p
(2)?
q=p→q(3)p=p→q(4)?
p?
(p?
q)=?
p答:
(1),(4)
2、下列公式中哪些是永真式?
()
(1)(┐p?
q)→(q→?
r)
(2)p→(q→q)(3)(p?
q)→p(4)p→(p?
q)答:
(2),(3),(4)
3、设有下列公式,请问哪几个是永真蕴涵式?
()
(1)p=p?
q
(2)p?
q=p(3)p?
q=p?
q
(4)p?
(p→q)=q(5)?
(p→q)=p(6)?
p?
(p?
q)=?
p
答:
(2),(3),(4),(5),(6)
4、公式?
x((a(x)?
b(y,x))?
?
zc(y,z))?
d(x)中,自由变元是(),约束变元是()。
答:
x,y,x,z
5、判断下列语句是不是命题。
若是,给出命题的真值。
()
(1)北京是中华人民共和国的首都。
(2)陕西师大是一座工厂。
(3)你喜欢唱歌吗?
(4)若7+8>18,则三角形有4条边。
(5)前进!
(6)给我一杯水吧!
答:
(1)是,t
(2)是,f(3)不是
(4)是,t(5)不是(6)不是
6、命题“存在一些人是大学生”的否定是(),而命题“所有的人都是要死的”的否定是()。
答:
所有人都不是大学生,有些人不会死
7、设p:
我生病,q:
我去学校,则下列命题可符号化为()。
(1)只有在生病时,我才不去学校
(2)若我生病,则我不去学校
(3)当且仅当我生病时,我才不去学校(4)若我不生病,则我一定去学校答:
(1)?
q?
p
(2)p?
?
q(3)p?
?
q(4)?
p?
q
8、设个体域为整数集,则下列公式的意义是()。
(1)?
x?
y(x+y=0)
(2)?
y?
x(x+y=0)
答:
(1)对任一整数x存在整数y满足x+y=0
(2)存在整数y对任一整数x满足x+y=0
9、设全体域d是正整数集合,确定下列命题的真值:
(1)?
x?
y(xy=y)()
(2)?
x?
y(x+y=y)()
(3)?
x?
y(x+y=x)()(4)?
x?
y(y=2x)()
答:
(1)f
(2)f(3)f(4)t
10、设谓词p(x):
x是奇数,q(x):
x是偶数,谓词公式?
x(p(x)?
q(x))在哪个个体域中为真?
()
(1)自然数
(2)实数(3)复数(4)
(1)--(3)均成立答:
(1)
11、命题“2是偶数或-3是负数”的否定是()。
答:
2不是偶数且-3不是负数。
12、永真式的否定是()
(1)永真式
(2)永假式(3)可满足式(4)
(1)--(3)均有可能答:
(2)
13、公式(?
p?
q)?
(?
p?
为()。
答:
?
p,q?
p?
q)化简为(),公式q?
(p?
(p?
q))可化简
14、谓词公式?
x(p(x)?
?
yr(y))?
q(x)中量词?
x的辖域是()。
答:
p(x)?
?
yr(y)
15、令r(x):
x是实数,q(x):
x是有理数。
则命题“并非每个实数都是有理
数”的符号化表示为()。
答:
?
?
x(r(x)?
q(x))
(集合论部分)
16、设a={a,{a}},下列命题错误的是()。
(1){a}?
p(a)
(2){a}?
p(a)(3){{a}}?
p(a)(4){{a}}?
p(a)答:
(2)
17、在0()?
之间写上正确的符号。
(1)=
(2)?
(3)?
(4)?
答:
(4)
18、若集合s的基数|s|=5,则s的幂集的基数|p(s)|=()。
答:
32
19、设p={x|(x+1)2?
4且x?
r},q={x|5?
x2+16且x?
r},则下列命题哪个正确()
(1)q?
p
(2)q?
p(3)p?
q(4)p=q
答:
(3)
20、下列各集合中,哪几个分别相等()。
(1)a1={a,b}
(2)a2={b,a}(3)a3={a,b,a}(4)a4={a,b,c}
(5)a5={x|(x-a)(x-b)(x-c)=0}(6)a6={x|x2-(a+b)x+ab=0}答:
a1=a2=a3=a6,a4=a5
答:
(4)
22、判断下列命题哪个为真?
()
(1)a-b=b-a=a=b
(2)空集是任何集合的真子集
(3)空集只是非空集合的子集(4)若a的一个元素属于b,则a=b答:
(1)
23、判断下列命题哪几个为正确?
()
答:
(2),(4)
24、判断下列命题哪几个正确?
()
25、设a∩b=a∩c,a∩b=a∩c,则b()c。
答:
=(等于)
26、判断下列命题哪几个正确?
()
(1)若a∪b=a∪c,则b=c
(2){a,b}={b,a}
(3)p(a∩b)?
p(a)∩p(b)(p(s)表示s的幂集)
(4)若a为非空集,则a?
a∪a成立。
答:
(2)
27、A,B,C是三个集合,则下列哪几个推理正确:
(1)a?
b,b?
c=a?
c
(2)a?
b,b?
c=a∈b(3)a∈b,b∈c=a∈c答:
(1)
(二元关系部分)
28、设A={1,2,3,4,5,6},b={1,2,3},从A到b的关系R={〈x,y〉|x=y2},求
(1)r
(2)r-1。
答:
(1)r={1,1,4,2}
(2)r?
1={1,1,2,4}
29、举出集合a上的既是等价关系又是偏序关系的一个例子。
()答:
a上的恒等关系
30、集合a上的等价关系的三个性质是什么?
()
答:
自反性、对称性和传递性
31、集合a上的偏序关系的三个性质是什么?
()
答:
自反性、反对称性和传递性
32、设s={1,2,3,4},A上的关系R={〈1,2〉,〈2,1〉,〈2,3〉,〈3,4〉}求
(1)r?
r
(2)r-1。
答:
r?
r={〈1,1〉,〈1,3〉,〈2,2〉,〈2,4〉}
r={〈2,1〉,〈1,2〉,〈3,2〉,〈4,3〉}-1
33、设A={1,2,3,4,5,6},R是a上的整除关系,求r={()}。
答:
r={1,1,2,2,3,3,4,4,5,5,6,6,1,2,1,3,1,4,
1,5,1,6,2,4,2,6,3,6}
34、设A={1,2,3,4,5,6},b={1,2,3},从A到b的关系R={〈x,y〉|x=2y},求
(1)r
(2)r-1。
答:
(1)r={1,1,4,2,6,3}
(2)r?
1={1,1,2,4,(36}
35、设A={1,2,3,4,5,6},b={1,2,3},从A到b的关系R={〈x,y〉|x=y2},
求r和r-1的关系矩阵。
?
1?
0?
0答:
r的关系矩阵=?
?
0?
?
0
?
?
00001000?
0?
?
1?
0?
0r?
1的关系矩阵=?
?
0?
?
?
?
00?
0?
?
0000000100000?
?
0?
0?
?
36、集合a={1,2,…,10}上的关系r={x,y|x+y=10,x,y?
a},则r的性质为()。
(1)自反的
(2)对称的(3)传递的,对称的(4)传递的答:
(2)
(代数结构部分)
37、设a={2,4,6},a上的二元运算*定义为:
a*b=max{a,b},则在独异点a,*中,单位元是(),零元是()。
答:
2,6
38、设a={3,6,9},a上的二元运算*定义为:
a*b=min{a,b},则在独异点
【篇二:
离散数学练习题及答案】
的表示方法有两种:
法。
请把“奇整数集合”表示出
,k?
z}来{}。
1、列举;描述;{x|x?
2k?
1
2、无向连通图g含有欧拉回路的充分必要条件是
2*、连通有向图d含
有欧拉回路的充分必要条件是d中每个结点的入度=出度.
3、设r是集合a上的等价关系,则r所具有的关系的三个特性是自反性、对称性、传递性.
4、有限图g是树的一个等价定义是:
.
5、设n(x):
x是自然数,z(y);y是整数,则命题“自然数都是整数,而有的整数不是自然
数”符号化为?
x(n(x)?
z(x))?
?
x(z(x)?
?
n(x))
6、在有向图的邻接矩阵中,第i行元素之和,第j列元素之和分别为
结点v的出度和结点v的入度.
7、设a,b为任意命题公式,c为重言式,若a?
c?
b?
c,那么命题a?
b是
重言式的真值是1.
8、命题公式?
(p?
q)的主析取范式为
9、设图g=v,e和g?
=v?
e?
若g?
是g的真子图,若
,则g?
是g的生成子图.v?
?
v或e?
?
e;v?
?
v,e?
?
e
10、在平面图g?
?
v,e?
中,则
11、设a?
{a,b},?
deg(r)=,其中r(i=1,2,…,r)是g的面.iiri?
1b?
{1,2},则从a到b的所有映射是11、?
1={(a,1),(b,1)};?
2={(a,2),(b,2)};?
3={(a,1),(b,2)};?
4={(a,
2),(b,1)}
12、表达式?
x?
yl(x,y)中谓词的定义域是{a,b,c},将其中的量词消除,写成与之等价
的命题公式为
12、(l(a,a)?
l(a,b)?
l(a,c))?
(l(b,a)?
l(b,b)?
l(b,c))?
(l(c,a)?
l(c,b)?
l(c,c))
12*、设个体域d={a,b},公式?
x(g(x)?
?
yh(x,y))消去量词化为
13、含有三个命题变项p,q,r的命题公式p?
q的主析取范式是14、设r,s都是集合a上的等价关系,则对称闭包s(r?
s)=15、设g是连通平面图,v,e,r分别表示g的结点数,边数和面数,则v,e和r满足的关系式
是v?
r?
e?
?
16、设g是n个结点的简单图,若g,则g一定是哈密顿图.
17、一个有向树t称为根树,若
称为树叶.若有向图t恰有一个结点的入度为0,其余结点入度为1;入度为0的结点;出度为0的结点.
18、图的通路中边的数目称为结点不重复的通路是通路.边不重复的
通路是通路.通路长度;初级;简单.
19、设a和b为有限集,|a|=m,|b|=n,则有个从a到b的关系,有个从a到b的函数,其中当m?
n时有个入射,当m=n时,有个双射。
19、2m*nm,nm,cn?
m!
m!
2a?
{n|n?
n}(是/不是)可数的。
是20、集合
21、设l?
?
1,2,3,4,12?
上的整除关系
?
?
a1,a2a1,a2?
l,a1整除a2?
?
在l上定义两个二元运算?
和?
:
对任意a,b?
l,a?
b?
glb(a,b),a?
b?
lub(a,b)。
请填空(在横线上填是或不是):
①是②是③是④不是
①代数系统?
l,?
?
?
格。
②代数系统?
l,?
?
?
有界格。
③代数系统?
l,?
?
?
有补格。
④代数系统?
l,?
?
?
分配格。
二、单项选择题(选择一个正确答案的代号,填入括号中)
1、设命题公式g=?
(p?
q),h=p?
(q?
?
p),则g与h的关系是(a)。
a.g?
hb.h?
gc.g=hd.以上都不是
2、下列命题公式等值的是(c)
(a)?
p?
?
q,p?
q
(c)q?
(p?
q),?
q?
p?
q(b)a?
(a?
b),?
a?
(a?
b)(d)?
a?
(a?
b),b
3、设v={a,b,c,d},与v能构成强连通图的边集e=(a)
(a){a,b,a,c,d,a,b,d,c,d}(b){a,d,b,a,b,c,b,d,d,c}
(c){a,c,b,a,b,c,d,a,d,c}(d){a,d,b,a,b,d,c,d,d,c}
4、设l(x):
x是演员,j(x):
x是老师,a(x,y):
x佩服y.那么命题“所有演员都佩服某些老
师”符号化为(b)
(a)?
xl(x)?
a(x,y)(b)?
x(l(x)?
?
y(j(y)?
a(x,y)))(c)?
x?
y(l(x)?
j(y)?
a(x,y))(d)?
x?
y(l(x)?
j(y)?
a(x,y))
5、在由3个元素组成的集合上,可以有(d)种不同的关系。
(a)3(b)8(c)9(d)512
6、设s1=?
s2={?
},s3=p({?
}),s4=p(?
)则命题为假的是(a).
(a)s2?
s4(b)s1?
s3(c)s2?
s4(d)s4?
s3
7、设g是连通平面图,有v个结点,e条边,r个面,则r=(a).
(a)e-v+2(b)v+e-2(c)e-v-2(d)e+v+2
8、下列命题正确的是(a)。
a.?
?
{?
}=?
b.?
?
{?
}=?
c.{a}?
{a,b,c}d.?
?
{a,b,c}
9、设a,b,c都是集合,如果a?
c=b?
c,则有(c)
(a)a=b(b)a?
b(c)当a-c=b-c时,有a=b(d)当c=u时,有a?
b
10、设(b,?
?
,0,1)是布尔代数,?
a,b?
b,a?
b,则下式不成立的是(d)(a)ab?
0(b)a?
b?
1(c)a?
b?
a(d)a?
b?
1
11、下面给出的一阶逻辑等价式中,(a)是错的。
a.?
x(a(x)?
b(x))=?
xa(x)?
?
xb(x)
b.a?
?
xb(x)=?
x(a?
b(x))
c.?
x(a(x)?
b(x))=?
xa(x)?
?
xb(x)
d.?
?
xa(x)=?
x(?
a(x))
三、多重选择题(每道小题都可能有一个以上的正确选项,须选出所有的正确选项,不答不得分,多选、少选或选错都将按比例扣分。
)
1、命题公式(p∧(p→q))→q是_____式。
(1)重言
(2)矛盾(3)可满足(4)非永真的可满足
2、给定解释i=(d,ic)=(整数集,{f(x,y):
f(x,y)=x-y;g(x,y):
g(x,y)=x+y;
p(x,y):
xy}),下列公式中_____在解释i下为真。
(1)p(f(x,y),g(x,y))
(2)?
x?
yp(f(x,y),g(x,y))
(3)?
x?
y(p(x,y)→p(f(x,y),x))(4)?
x?
yp(f(x,y),g(x,y))
3、A是集合,a=10,则p(a)=_____。
(1)100
(2)99(3)2048(4)1024(5)512
4、集合A={x|x是整数,x230},B={x|x是质数,x20},c={1,3,5},则
①(a?
b)?
c=_____;
②(b?
a)?
c=_____;
③(c?
a)?
(b?
a)=_____;
④(b?
c)?
a=_____。
(1){1,2,3,5}
(2)?
(3){0}(4){1,3,5,7,11,13,17,19}
(5){1,3,5,7}(6){7,11,13,17,19}
5、设a、b、c是集合,下列四个命题中,_____在任何情况下都是正确的。
(1)若a?
b且b∈c,则a∈c
(2)若a?
b且b∈c,则a?
c
(3)若a∈b且b?
c,则a?
c(4)若a∈b且b?
c,则a∈c
6、设集合A={a,b,c,d,e,f,g},A的一个划分?
={{a,b},{c,d,e},{f,g}},则?
所对应的等价关系有_____个二元组。
(1)14
(2)15(3)16(4)17(5)8(6)49(7)512
7、s={1,2,3,4,5,6,7,8,9,10,11,12},≤是s上的整除关系。
s的子集B=
{2,4,6},则在s,≤中,B的最大元是_____;B的最小元是_____;B的上确界是_____;B的下确界是_____。
(1)不存在的
(2)36(3)24(4)12(5)6(6)1(7)2
8、设有有限布尔代数(b,+,*,’,0,1),则b=_____能成立。
(1)1
(2)2(3)3(4)4(5)5(6)8(7)9
9、g={0,1,2,?
n},n∈n,定义?
为模n加法,即x?
y=(x+y)modn,则
代数系统(g,?
)_____。
(1)是半群但不是群
(2)是无限群(3)是循环群(4)是变换群
(5)是交换群
10、仅有一个结点的图称为(),当然也是()
(1)零图
(2)平凡图(3)补图(4)子图
1.1、3。
2.4。
3.4。
4.1;4;2;2。
5.4。
7.1;7;4;7。
8.2、4、6。
9.3、5。
10.2;1。
四、化简解答题
1、
(1)设图g(如第1题图),作图g的嵌入图,说明图g是平面图.
第1题图1、
(1)
图g的嵌入图,如第12题答案图.故图g为平面图(4分)第12题答案图
(2)在具有n个顶点的完全图kn中删去多少条边才能得到树?
解:
n个顶点的完全图kn中共有6.4。
n?
(n?
1)条边,n个顶点的树应有n?
1条边,于是,删2
n?
(n?
1)(n?
1)?
(n?
2)?
(n?
1)?
去的边有:
。
22
2、判别谓词公式?
x?
yf(x,y)?
?
y?
xf(x,y)的类型.
2、设i为任意一个解释,d为i的个体域.若在解释i下,该公式的前件为0,无论?
y?
xf(x,y)如何取值,?
x?
yf(x,y)?
?
y?
xf(x,y)为1;
若在解释i下,该公式的前件为1,则?
x0?
d,使得?
yf(x,y)为1,它蕴含着?
y?
?
d,f(x0,y?
)为1?
?
xf(x,y?
)为1,由y?
的任意性,必有?
y?
xf(x,y)为1,于是?
x?
yf(x,y)?
?
y?
xf(x,y)为1.
所以,?
x?
yf(x,y)?
?
y?
xf(x,y)是永真式.
3、化简集合表达式:
((a?
b?
c)?
(a?
c))-((c?
(c-b)-a)
3、((a?
b?
c)?
(a?
c))-((c?
(c-b)?
~a)
=(a?
c)-(c?
~a)(两次用吸收律)
=((a?
c)?
(~c?
a)
=(a?
~c)?
(c?
~c)?
a?
(a?
c)
=(a?
~c)?
?
?
a=a
4、判断下列哪些运算结果是对的?
哪些是错的?
请将错误的运算结果更正过来.
(1)?
?
{?
}?
?
(2)?
?
{?
}?
?
(3){?
}?
{?
{?
}}?
{?
}(4){?
{?
}}?
{?
}?
{?
{?
}}
(5)(a?
b)?
b?
a(6)(a?
b)?
b?
a
(7)a?
a?
a(8)(a?
b)?
a?
?
4、
(1)对.
(2)错.应为{?
}.(3)对.(4)错.应为{{?
}}
(5)错.应为a?
b(6)错.应为a?
b(或a?
~b或a-ab)
(7)错.应为?
,即a?
a?
a?
a?
a?
a?
?
(8)对.
5、将命题公式?
p?
q?
(?
r?
p)化为只含?
和?
的尽可能简单的等值式.5、?
p?
q?
(?
r?
p)
?
?
(p?
?
q)?
(r?
p)(优先级有误)
?
?
(p?
?
q)?
?
(?
p?
?
r)不惟一.
(1)v1e5v5e7v2e2v3
(2)v5e6v2e2v3e3v4e8v2e7v5v25
4(3)v2e7v5e6v2(4)v1e1v2e2v3e3v4e8v2e6v5
e
v4
6、
(1)初级通路;
(2)简单回路;(3)初级回路;(4)简单通路.e3
vev7、试问n取何值时,无向完全图kn,存在一条欧拉回路?
6、设图g如右图.已知通路
7、由于kn有n个结点,并且每个结点的度数均为n-1,于是,当n为奇数时,kn的每个结点的度数都是偶数,所以存在一条欧拉回路.
8、已知(l,*,?
)是格,且二元运算*和?
满足分配律,?
a,b,c?
l,化简表达式((a*b)?
(a*c))*((a*b)?
(b*c))
解答:
((a*b)?
(a*c))*((a*b)?
(b*c))
=(a*b)?
((a*c)*(b*c))(分配律)
=(a*b)?
((a*b)*c)(幂等律)
=a*b(吸收律)
9、化简(?
p?
(?
q?
r))?
(q?
r)?
(p?
r)。
9、(?
p?
(?
q?
r))?
(q?
r)?
(p?
r)=(?
p?
?
q?
q?
p)?
r=
=(?
p?
q?
p)?
r=r
10、试将一阶逻辑公式?
x?
?
yp?
x,y?
?
?
?
?
yq?
y?
?
r?
x?
?
?
化成前束范式。
解:
【篇三:
离散数学课后习题答案一】
txt>习题1.1
1.下列哪些语句是命题,在是命题的语句中,哪些是真命题,哪些是假命题,哪些命题的真值现在还不知道?
(1)中国有四大发明。
(2)你喜欢计算机吗?
(4)请回答这个问题!
(6)x?
7?
10。
(3)地球上海洋的面积比陆地的面积大。
(5)2?
3?
6。
(7)园的面积等于半径的平方乘以圆周率。
(8)只有6是偶数,3才能是2的倍数。
(9)若x?
y,则x?
z?
y?
z。
(11)2020年元旦下大雪。
解
(10)外星人是不存在的。
(12)如果1?
1?
3,则血就不是红的。
是真命题的有:
(1)、(3)、(7)、(9)、(12);是假命题的有:
(5)、(8);是命题
但真值现在不知道的有:
(10)、(11);不是命题的有:
(2)、(4)、(6)。
2.令p、q为如下简单命题:
p:
气温在零度以下。
q:
正在下雪。
用p、q和逻辑联接词符号化下列复合命题。
(1)气温在零度以下且正在下雪。
(2)气温在零度以下,但不在下雪。
(3)气温不在零度以下,也不在下雪。
(4)也许在下雪,也许气温在零度以下,也许既下雪气温又在零度以下。
(5)若气温在零度以下,那一定在下雪。
(6)也许气温在零度以下,也许在下雪,但如果气温在零度以上就不下雪。
(7)气温在零度以下是下雪的充分必要条件。
解
(1)p?
q;
(2)p?
?
q;(3)?
p?
?
q;(4)p?
q;(5)p?
q;(6)(p?
q)?
(?
p?
?
q);(7)p?
q。
3.令原子命题p:
你的车速超过每小时120公里,q:
你接到一张超速罚款单,用p、q和逻辑联接词符号化下列复合命题。
(1)你的车速没有超过每小时120公里。
(2)你的车速超过了每小时120公里,但没接到超速罚款单。
(3)你的车速若超过了每小时120公里,将接到一张超速罚款单。
(4)你的车速不超过每小时120公里,就不会接到超速罚款单。
(5)你接到一张超速罚款单,但你的车速没超过每小时120公里。
(6)只要你接到一张超速罚款单,你的车速就肯定超过了每小时120公里。
解
(1)?
p;
(2)p?
?
q;(3)p?
q;(4)?
p?
?
q;(5)q?
?
p;(6)q?
p。
4.判断下列各蕴涵式是真是假。
(2)若1?
1?
2,则2?
2?
5。
f(4)若1?
1?
3,则2?
2?
5。
t(6)若猪会飞,那么2?
2?
5。
t(8)若1?
1?
2,猪就会飞。
f
(1)若1?
1?
2,则2?
2?
4。
t(3)若1?
1?
3,则2?
2?
4。
t(5)若猪会飞,那么2?
2?
4。
t(7)若1?
1?
3,猪就会飞。
t
解
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 习题 答案