《离散数学》模拟题（补）
一．单项选择题
1．下面四组数能构成无向图的度数列的有( )。
A、 2,3,4,5,6,7；
B、 1,2,2,3,4；
C、 2,1,1,1,2；
D、 3,3,5,6,0。
2．图的邻接矩阵为( )。
A、；
B、；
C、；
D、。
3.设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件下X与（）集合相等。
A、X=S2或S5 ；
B、X=S4或S5；
C、X=S1，S2或S4；
D、X与S1，…，S5中任何集合都不等。
4．下列图中是欧拉图的有( )。
5.下述命题公式中，是重言式的为（）。
A、；
B、；
C、；
D、。
6.的主析取范式中含极小项的个数为（）。
A 、2； B、 3； C、5； D、0
??
?
?
?
?
?
?
?
1
1
1
1
1
1
1
??
?
?
?
?
?
?
?
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
??
?
?
?
?
?
?
?
1
1
1
1
1
1
1
??
?
?
?
?
?
?
?
1
1
1
1
1
1
1
3
1
S
X
S
X?
?且
)
(
)
(q
p
q
p∨
→
∧))
(
))
((
)
(p
q
q
p
q
p→
∧
→
?
?
q
q
p∧
→
?)
(q
p
p?
?
∧)
(
r
q
p
wff→
∧
?)
(
7.给定推理
① P ② US ① ③ P ④ ES ③ ⑤ T ②④I ⑥ UG ⑤
推理过程中错在（ ）。
A 、①->②;
B 、②->③;
C 、③->④;
D 、④->⑤
8.设S 1={1，2，…，8，9}，S 2={2，4，6，8}，S 3={1，3，5，7，9}，S 4={3，4，5}， S 5={3，5}，在条件
下X 与（ ）集合相等。
A 、X=S 2或S 5 ；
B 、X=S 4或S 5；
C 、X=S 1，S 2或S 4；
D 、X 与S 1，…，S 5中任何集合都不等。 9.设R 和S 是P 上的关系，P 是所有人的集合，
，
则表示关系 （ ）
。
A 、；
B 、
；
C 、 ；
D 、
。
10.下面函数（ ）是单射而非满射。
A 、
； B 、
；
C 、
；
D 、。
))()((x G x F x →?)()(y G y F →)(x xF ?)(y F )(y G )(x xG ?)())()((x xG x G x F x ??→?∴3
1S X S X ??且},|,{的父亲是y x P y x y x R ∧∈><=},|,{的母亲是y x P y x y x S ∧∈><=R S 1-},|,{的丈夫是y x P y x y x ∧∈><},|,{的孙子或孙女是y x P y x y x ∧∈><Φ},|,{的祖父或祖母是y x P y x y x ∧∈><12)(,:2-+-=→x x x f R R f x x f R Z f ln )(,:=→+的最大整数表示不大于x x x x f Z R f ][],[)(,
:=→12)(,:+=→x x f R R f
11.其中R 为实数集，Z 为整数集，R +，Z +
分别表示正实数与正整数集。
1、 设S={1，2，3}，R 为S 上的关系，其关系图为
则R 具有（ ）的性质。
A 、自反、对称、传递；
B 、什么性质也没有；
C 、反自反、反对称、传递；
D 、自反、对称、反对称、传递。 12.设，则有（ ）。 A 、{{1,2}} ；B 、{1,2 } ； C 、{1} ； D 、{2} 。 13.设A={1 ,2 ,3 }，则A 上有（ ）个二元关系。
A 、23
； B 、32
； C 、； D 、
二．填空题
1.任何(n,m) 图G = (V,E) , 边与顶点数的关系是 。
2.当n 为 时,非平凡无向完全图Kn 是欧拉图。
3.已知一棵无向树T 有三个3顶点,一个2度顶点,其余的都是1度顶点, 则T 中有 个1度顶点。
阶完全图Kn 的点色数X(KN)= 。
5.设集合A={1，2，3，4，5，6，7，8，9，10}，定义A 上的二元关系“≤”为 x ≤ y = x|y , 则= 。
6.设
，定义A 上的二元运算为普通乘法、除法和加法，则代数系统
8.设
1. 设G 为具有n 个结点的简单图，且
则G 是连通图。
2. 设G 是（n,m ）简单二部图，则
。 }}2,1{},1{,{Φ=S S ?3
222
3
2y x ∨},2|{N n x x A n
∈==G a ∈)2)(1(21
-->
n n m 42
n m ≤
3.证明：在6个结点12条边的连通平面简单图中，每个面的面度都是3。
4.对代数系统
（2）每个元素的逆元是唯一的。
5.证明任一环的同态象也是一环。
四.中国邮递员问题
求带权图G中的最优投递路线。邮局在v1点。
五.应用题
某年级共有9门选修课程，期末考试前必
须提前将这9门课程考完，每人每天只在
下午考一门课，若以课程表示结点，有一
人同时选两门课程，则这两点间有边（其
图如右），问至少需几天？
参考答案：
一、单项选择题
题目 1 2 3 4 5 6 7 8 9 答案 B C B B C C C C A 题目10 11 12 13
答案 A B D D
二．填空题
.奇数 （x,y ） 6.乘法
7.群 8.
三．证明题
1、反证法：若G 不连通，不妨设G 可分成两个连通分支G 1、G 2，假设G 1和G 2的顶点数分别为n 1和n 2，显然。
与假设矛盾。所以G 连通。 2、设G=（V ，E ），
对完全二部图有
当
时，完全二部图的边数m 有最大值。 故对任意简单二部图有
。 3、证：n=6,m=12 欧拉公式n-m+f=2知 f=2-n+m=2-6-12=8 由图论基本定理知：
，而，所以必有，
即每个面用3条边围成。 4.证明：
（1）设，b 是a 的右逆元，c 是b 的右逆元，由于，
所以b 是a 的左逆元。
（2）设元素a 有两个逆元b 、c ，那么
a 的逆元是唯一的。 5.证明:
设是一环,且是关于同态映射f 的同态象。 ∑∈=V
v m
v d 2)(},,{12e a a a a G n
n ==-， n n n =+2111112121-≤-≤∴≥≥n n n n n n 2)
2)(1(2)2)(1(2)1(2)1(212211--=-+-≤-+-≤
∴n n n n n n n n n m n
n n n Y n X Y X V =+==?=2121,,,则4)2()(2
2112
1
1121n n n n n n n n n n n m +
--=+-=-=?=21n
n =
),(m n 42n ),(m n 42
n m ≤
242)deg(=?=∑m F 3)deg(≥i
F 3)deg(=i
F A c b a ∈,,b e b b a b ==*)*(*a b e a b c b a b c b a b c b e **)*()*(*)*(*)*(**=====c c e c a b c a b e b b =====**)*()*(**>?+<,,A >?⊕<,,)(A f
由是Abel 群，易证也是Abel 群。
是半群，易证也是半群。
现只需证：对是可分配的。
于是
同理可证
因此也是环。
四．中国邮递员问题
解：图中有4个奇数结点，
（1） 求
任两结点的最短路
再找两条道路使得它们没有相同的起点和终点，且长度总和最短：
（2） 在原图中复制出
，设图G ‘
，则图G ‘
中
每个结点度数均为偶数的图G ‘
存在欧拉回路，欧拉回路C 权长
为43。
五.应用题
解：即为最少考试天数。 用Welch-Powell 方法对G 着色：
第一种颜色的点 ，剩余点
第二种颜色的点 ，剩余点
第三种颜色的点
>+<,A >⊕<,)(A f >?<,A >?<,)(A f ?⊕3
,2,1,)(:,,),(,,321321==∈?i b a f a a a A f b b b i i 使得则必有相应的)
()())()(())()(()()())()(())(())(()())()(()()(3121312131213121321321321321b b b b a f a f a f a f a a f a a f a a a a f a a a f a a f a f a f a f a f b b b ?⊕?=?⊕?=?⊕?=?+?=+?=+?=⊕?=⊕?)
()()(1312132b b b b b b b ?⊕?=?⊕>?⊕<,,)(A f 5
)(, 3)( ,5)( ,3)(5321====v d v d v d v d 5
321,,,v v v v 5736562532457133212211535232513221 , , , , ,4)( , 3)( ,2)( ,4)(, 5)( ,3)(v v v p v v v p v v p v v v p v v v p v v p v v d v v d v v d v v d v v d v v d ============
, ,3245713v v p v v v p ==4
3 ,p p 1
57123.5726542371v v v v v v v v v v v v v v v v C =)(G χ6
85421739v v v v v v v v v 6419v v v v 8
5273v v v v v 573v v v 8
2v v 8
2v v
所以≤3 任
构成一圈，所以≥3
故=3
所以三天下午即可考完全部九门课程。
)(G χ9
32v v v )(G χ)(G χ
离散数学考试（试题及答案） 一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。 解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T 故有三种派法：B∧D，A∧C，A∧D。 二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为： (()∧())，()(()∧())
下面给出证明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。 证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪I A＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>， <5，2>，<1，2>，<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝R i＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。
一、填空 1、 设p ：天气热，q ：他去游泳，则命题“如果天气热，则 他就去游泳”可符号化为 2、 设A={2，3，4，5，6}上的二元关系 }|,{是质数x y x y x R ∨<><=，则R= （列举法）。R 的关系矩阵M R = 。 3、设A={1，2，3}，则A 上既是对称的又是反对称的关系R= 。 4、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 5、 设A 为任意的命题公式，B 为重言式，则B A ∨的类型为 ； 二、选择 1、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为 则R 具有（ ）性质。 A ．自反性、对称性、传递性； B ．反自反性、 反对称性；
C ．反自反性、反对称性、传递性； D ．自反性 。 2、在如下各图中（ ）欧拉图。 3. 设{}1,2,3A =，则A 上的二元关系有几个？（ ） A. 32 . B. 23 . C. 332? . D. 323?. 4．下列哪个命题是真命题？（ ） A ．我正在说谎. B. 若011=+，则雪是黑色的. C. 9518+>. D.存在最大的质数. 5. 下面四组数能构成无向简单图的度数列的有（ ）。 A 、（2，2，2，2，2）； B 、（1，1，2，2，3）； C 、（1，1，2，2，2）； D 、（0，1，3，3，3）。 三、计算 1、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。 2. 利用主析取范式，求公式R Q Q P ∧∧→?)(的类型。 3. 设A={1，2}，A 上所有函数的集合记为A A ,试给出A A 四、证明 1. 若无向图G 为欧拉图，证明G 中无桥.
1 离散数学模拟试题Ⅰ 一、单项选择题(本大题共15小题,每题1分,共15分)在每小题列出的四个备选项中只有一个就是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分 1.设 }16{2<=x x x A 是整数且,下面哪个命题为假( A )。 A 、A ?}4,2,1,0{; B 、A ?---}1,2,3{; C 、A ?Φ; D 、A x x x ?<}4{是整数且。 2.设}}{,{,ΦΦ=Φ=B A ,则B －A 就是( C )。 A 、}}{{Φ; B 、}{Φ; C 、}}{,{ΦΦ; D 、Φ。 3.右图描述的偏序集中,子集},,{f e b 的上界为 ( B )。 A 、b,c; B 、a,b; C 、b; D 、a,b,c 。 4.设f 与g 都就是X 上的双射函数,则1)(-g f ο为( C )。 A 、11--g f ο; B 、1)(-f g ο; C 、11--f g ο; D 、1-f g ο。 5.下面集合( B )关于减法运算就是封闭的。 A 、N ; B 、}2{I x x ∈; C 、}12{I x x ∈+; D 、}{是质数x x 。 6.具有如下定义的代数系统>*<,G ,( D )不构成群。 A 、G={1,10},*就是模11乘 ; B 、G={1,3,4,5,9},*就是模11乘 ; C 、G=Q(有理数集),*就是普通加法; D 、G=Q(有理数集),*就是普通乘法。 7.设 },32{I n m G n m ∈?=,*为普通乘法。则代数系统>*<,G 的幺元为( B )。 f
2 A 、不存在 ; B 、0032?=e ; C 、32?=e ; D 、1132--?=e 。 8.下面集合( C )关于整除关系构成格。 A 、{2,3,6,12,24,36} ; B 、{1,2,3,4,6,8,12} ; C 、{1,2,3,5,6,15,30} ; D 、{3,6,9,12}。 9.设},,,,,{f e d c b a V =, },,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ,则有向图 >= 《离散数学》模拟题（补） 一．单项选择题 1．下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7； B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。 2．图的邻接矩阵为( )。 A、； B、； C、； D、。 3.设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件下X与（）集合相等。 A、X=S2或S5 ； B、X=S4或S5； C、X=S1，S2或S4； D、X与S1，…，S5中任何集合都不等。 4．下列图中是欧拉图的有( )。 5.下述命题公式中，是重言式的为（）。 A、； B、； C、； D、。 6.的主析取范式中含极小项的个数为（）。 A 、2； B、 3； C、5； D、0 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 3 1 S X S X? ?且 ) ( ) (q p q p∨ → ∧)) ( )) (( ) (p q q p q p→ ∧ → ? ? q q p∧ → ?) (q p p? ? ∧) ( r q p wff→ ∧ ?) ( 7.给定推理 ① P ② US ① ③ P ④ ES ③ ⑤ T ②④I ⑥ UG ⑤ 推理过程中错在（ ）。 A 、①->②; B 、②->③; C 、③->④; D 、④->⑤ 8.设S 1={1，2，…，8，9}，S 2={2，4，6，8}，S 3={1，3，5，7，9}，S 4={3，4，5}， S 5={3，5}，在条件 下X 与（ ）集合相等。 A 、X=S 2或S 5 ； B 、X=S 4或S 5； C 、X=S 1，S 2或S 4； D 、X 与S 1，…，S 5中任何集合都不等。 9.设R 和S 是P 上的关系，P 是所有人的集合， ， 则表示关系 （ ） 。 A 、； B 、 ； C 、 ； D 、 。 10.下面函数（ ）是单射而非满射。 A 、 ； B 、 ； C 、 ； D 、。 ))()((x G x F x →?)()(y G y F →)(x xF ?)(y F )(y G )(x xG ?)())()((x xG x G x F x ??→?∴3 1S X S X ??且},|,{的父亲是y x P y x y x R ∧∈><=},|,{的母亲是y x P y x y x S ∧∈><=R S 1-},|,{的丈夫是y x P y x y x ∧∈><},|,{的孙子或孙女是y x P y x y x ∧∈><Φ},|,{的祖父或祖母是y x P y x y x ∧∈><12)(,:2-+-=→x x x f R R f x x f R Z f ln )(,:=→+的最大整数表示不大于x x x x f Z R f ][],[)(, :=→12)(,:+=→x x f R R f 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个 离散数学（上）模拟题 1、命题符号化（共6小题，每小题3分，共计18分） 1. 用命题逻辑把下列命题符号化 a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 b) 我今天进城，除非下雨。 c) 仅当你走，我将留下。 2. 用谓词逻辑把下列命题符号化 a) 有些实数不是有理数 b) 对于所有非零实数x，总存在y使得xy=1。 c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得 f(a)=b. 2、简答题（共6道题，共32分） 1. 求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范 式，并写出所有成真赋值。（5分） 2. 设个体域为{1,2,3}，求下列命题的真值（4分） a) xy(x+y=4) b) yx (x+y=4) 3. 求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） 4. 判断下面命题的真假，并说明原因。（每小题2分，共4分） a) （AB）－C=(A-B) (A-C) b) 若f是从集合A到集合B的入射函数，则|A|≤|B| 5. 设A是有穷集，|A|=5，问（每小题2分，共4分） a) A上有多少种不同的等价关系？ b) 从A到A的不同双射函数有多少个？ 6. 设有偏序集 下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即 可）(6分) 3、证明题（共3小题，共计40分） 1. 使用构造性证明，证明下面推理的有效性。（每小题5分，共10 分） a) A→(B∧C),(E→F)→C, B→(A∧S)B→E b) x(P(x)→Q(x)), x(Q(x)∨R(x))，xR(x) xP(x) 2. 设R1是A上的等价关系，R2是B上的等价关系，A≠且B≠，关系R 满足：< 《离散数学》模拟试题 一、 填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A 得幂集合p （A ）=_____ _。 2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B = {a , d , e }, 则A ∪B =___ ___， A ∩ B =____ __，A －B =___ ___，～A ∩～B =____ ____。 3. 设A ，B 是两个集合，其中A = {1, 2, 3}, B = {1, 2}，则A －B =____ ___， ρ（A ）－ρ（B ）=_____ _ _。 4. 已知命题公式，则G 的析取范式为 。 5. 设P ：2＋2＝4，Q ：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为 。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A 、B 是两个集合，A ＝{1,3,4}，B ＝{1,2}，则A －B 为（ ）. A. {1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（ ）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X ＝{x , y }，则ρ（X ）＝（ ）。 A. {{x },{y }} B. {φ,{x },{y }} C. {φ,{x },{y },{x , y }} D. {{x },{y },{x , y }} 4. 设集合 A ＝{1,2,3}，A 上的关系 R ＝ {(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R 不具备（ ）. 三、计算题（共50分） R Q P G →∧?=)( 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个 离散数学考试试题(A卷及答案） 一、证明题（10分） 1) (P∧Q∧A C)∧(A P∨Q∨C ) (A∧(P Q ))C。P<->Q=(p->Q)合取（Q->p） 证明: (P∧Q∧A C)∧(A P∨Q∨C) (P ∨Q ∨A∨C)∧(A∨P∨Q∨C) ((P ∨Q ∨A)∧(A∨P∨Q))∨C反用分配律 ((P∧Q∧A)∨(A ∧P ∧Q))∨C ( A∧((P∧Q)∨(P ∧Q)))∨C再反用分配律 GAGGAGAGGAFFFFAFAF ( A∧(P Q))∨C (A∧(P Q ))C 2) (P Q)P Q。 证明：(P Q)((P∧Q))(P ∨Q))P Q。 二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(Q R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。 主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由析取范式经等值演算法算得。 GAGGAGAGGAFFFFAFAF 证明： 公式法：因为(P(Q ∨R))∧(P∨(Q R)) (P∨Q∨R)∧(P∨(Q ∧R )∨(Q ∧R)) (P∨Q ∨R)∧(((P∨Q)∧(P ∨R ))∨(Q ∧R ))分配律 (P∨Q∨R)∧(P∨Q ∨Q)∧(P∨Q ∨R)∧(P∨R ∨Q)∧(P∨R ∨R) (P∨Q ∨R)∧(P∨Q ∨R )∧(P ∨Q∨R) M∧5M∧6M使（非P析取Q析取R）为0 4 GAGGAGAGGAFFFFAFAF 所赋真值，即100，二进制为4 GAGGAGAGGAFFFFAFAF 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 《离散数学》课程试题(A)卷 课程代码： 080800111 本试卷适用理学系数学与应用数学专业和信息与计算科学专业 （时量：120分钟；总分为100分） 注 意： 1、所有答案和解答均应写在答题纸上，答在试卷上不记分 2、答案必须写明题目序号，并按题号顺序答题 3、请保持行距，保持卷面整洁 一、填空题：（每题3分，本大题共24分） 1．设}4,}3{,,2{a A =，}1,4,3,}{{a B =，请在下列每对集合中填入适当的符号：?∈, 。 （1）}{a B , (2) }}3{,4,{a A 。 2．设}1,0{=A ，N 为自然数集，???=是偶数。，是奇数， ，x x x f 10)( 若A A f →： ，则f 是 射的，若A N f →： ，则f 是 射的。 3．设图G = < V ，E >中有7个结点，各结点的次数分别为2，4，4，6，5，5，2， 则G 中有 条边，根据 。 4．两个重言式的析取是 ，一个重言式和一个矛盾式的合取是 。 5．在一阶逻辑中将命题：凡对顶角都相等，符号化为_____________________。 6.集合A 有n 个元素，则A 上共有_____________________个既是对称又是反对称的的关系。 7. 连通简单无向图有17条边。则该图至少有_____________________个结点。 8. 某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没得优，那么两次考试都得优的学生的人数是_____________________。 二、单项选择题：（每小题3分，本大题共30分） 1．设}16{2<=x x x A 是整数且，下面哪个命题为假（ ） 。 A 、A ?}4,2,1,0{ ； B 、A ?---}1,2,3{ ； C 、A ?Φ ； D 、A x x x ?<}4{是整数且。 2．设}}{,{,ΦΦ=Φ=B A ，则B －A 是（ ）。 A 、}}{{Φ ； B 、}{Φ ； C 、}}{,{ΦΦ ； D 、Φ。 一、填空 1．不能再分解的命题称为____________，至少包含一个联结词的命题称为____________。2．一个命题公式A(P, Q, R)为真的所有真值指派是000, 001, 010, 100，则其主析取范式是__________________，其主合取范式是_________________。 3．设A={a,b,c}，B={b,c,d,e}，C={b,c}，则( A ?B ) ⊕C＝____________。 4．幂集P(P(?)) ＝________________。 5．设A为任意集合，请填入适当运算符，使式子A________A=?；A________A’=?成立。6．设A={0，1，2，3，6}，R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod 3)}，则D(R)=____________，R(R)=____________。 7．称集合S是给定非空集合A的覆盖：若S={S1，S2，…，S n}，其中S i?A，S i≠?，i=1，2，…，n，且______ _____；进一步若_____ _______，则S是集合A的划分。8．两个重言式的析取是____ ____式，一个重言式和一个永假式的合取式是式。9．公式┐(P∨Q) ←→(P∧Q)的主析取范式是。 10. 已知Π={{a}{b,c}}是A={a,b,c}的一个划分，由Π决定的A上的一个等价关系 是。 二、证明及求解 1．求命题公式（P→Q）→（Q∨P）的主析取范式。 2．推理证明题 1）?P∨Q，?Q∨R，R→S?P→S。 2) (?x)(P(x)→Q(y)∧R(x))，(?x)P(x)?Q(y)∧(?x)(P(x)∧R(x)) x)}，S={〈x,y〉|x,y∈A∧（x=y+2）}。3．设A={0，1，2，3}，R={〈x,y〉|x,y∈A∧(y=x+1∨y= 2 试求R S R。 4．证明：R是传递的?R*R?R。 5．设R是A上的二元关系，S={ 华南理工大学网络教育学院 2016–2017学年度第一学期期末考试 《 离散数学 》试卷（模拟卷） （客观题电脑给分，主观题依过程给分） 教学中心： 专业层次： 学 号： 姓 名： 座号： 注意事项：1. 本试卷共 三 大题，满分100分，考试时间90分钟，闭卷； 2. 考前请将以上各项信息填写清楚； 3. 所有答案必须做在答题纸上,做在试卷、草稿纸上无效； 4．考试结束，试卷、答题纸、草稿纸一并交回。 一、单项选择题（本大题30分，每小题6分） 1．设，P ：他聪明；Q ：他用功。在命题逻辑中，命题： “他既聪明又用功。” 可符号化为：( ) A ．P ∧ Q B ．P → Q C ．P ∨ ?Q D ．P ∧?Q 【答案：A 】 2．下列式子( )是永真式 A ．Q →（P ∧ Q ） B ．P →（P ∧ Q ） C ．（P ∧ Q ）→ P D ．（P ∨Q ）→ Q 【答案：C 】 3．设S （x ）：x 是运动员，J （y ）：y 是教练员，L （x ，y ）：x 钦佩y 。命题“所有运动员都钦佩一些教练员”的符号化公式是( ) A ．?x （S （x ）∧ ? y （J （y ）∧ L （x ，y ））） B ．?x ?y （S （x ）→（J （y ）→ L （x ，y ））） C ．?x （S （x ）→ ?y （J （y ）∧ L （x ，y ））） D ．?y ?x （S （x ）→（J （y ）∧ L （x ，y ））） 【答案：C 】 4．下列命题是真的是( ) A ．如果A ? B 及B ∈C,则A ? C B ．如果A ?B 及B ∈C,则A ∈C C ．如果A ∈B 及B ?C,则A ?C D ．如果A ∈B 及B ?C,则A ∈C 【答案：D 】 5．设G 是n 有个结点，m 条边的简单有向图。若G 是连通的，则m 的下界是（ ） A ．n B ．1n - C ．()1n n - D ．()1 12 n n - 【答案：B 】 二、 判断题（本大题20分，每小题4分） 1. 设A ，B 是命题公式，则蕴涵等值式为A →B ??A ∧B 。 （ × ） 2、?x ?yA(x,y)? ?y ?xA(x,y) 。 （ × ） 模 拟 试 题 1 一．将下面命题写成符号表达式。(3,4题要使用句后给定的谓词。) 1.如果小张去，则小王与小李都不去，否则小王与小李不都去。 2.我们不能既划船又跑步。 3.有些运动员是大学生。(L(x)：x 是运动员；,S(x)：x 是大学生。) 4.每个运动员都钦佩一些教练。( L(x):x 是运动员，A(x,y):x 钦佩y ，J(x):x 是教练。) 二．写出命题公式 (Q →?P)→Q 的主合取范式。（要求有解题过程） 三．令集合A={1,{1}}, B={1}, P(A)表示A 的幂集 1.判断下面命题的真值。并说明原因，否则不给分。 (1) B ∈A, (2) P(B) ?P(A) (3) {Φ}?P(A) (4) {1}∈P(B) 2.分别计算: (1) A ×P(B) (2) A ⊕B (3) P(A)－P(B) 四．用谓词逻辑推理证明下面推理的有效性。 ?x(A(x)∧(B(x)→?C(x))), ?x(A(x) → (C(x) ∨?D(x))), ?x(A(x) →D(x)) ? ?x(A(x) ∧? B(x)) 五．令Ａ＝{1,2,3,4 }，给出Ａ中关系R 1,R 2,R 3, R 4如下： R 3={<1,2>,<2,2>,<1,3>,<2,4>,<1,1>,<1,4>, <3,3>,<4,4>} R 4={<2,2>,<3,2>,<4,1>,<2,1>,<1,4>,<2,3>,<2,4>,<1,2>,<3,3>,<3,4>, <4,2>,<4,4>,<4,3>,<1,1>} 1．求复合关系~R 4oR 2c 。 2．分别画出R 1、R 3、R 4关系的有向图。 3．分别指出上面各个关系是否具有自反性、反自反性、对称性、反对称性、传递性。 4．上述四个关系中，哪些是等价关系？哪些是偏序关系？哪些是从Ａ到Ａ的函数？如果是等价关系，请写出该等价关系的各个等价类。 如果是函数，请指出该函数的类型。 六．设I 是整数集合，在I 上定义二元运算 * 如下：对于任何a,b ∈I a *b=a+ b ＋4 求证 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 一、选择题（每小题只有一个正确答案，每题2分，共30分） 1、令A（x）:x是实数，B（x）:x是有理数，则命题：并非所有有理数都是实数。符号化为：（） A、x┐(A(x)∧B(x)) B、┐x(B(x)→A(x)) C、┐x(A(x)∧B(x)) D、┐x(B(x)∧┐A(x)) 2、设A={{1，2，3}，{4，5}，{6，7，8}}，则下列选项正确的是（） A、1∈A， B、φ∈A C、{1，2，3} A， D、{{4，5}} A 3、设A、B为集合，A-B=φ，则有（） A、B=φ B、B≠φ C、A B D、B A 4、一个连通有向图，如果它的每个结点的出度均等于入度，那么它有一条（）。 A、基本回路 B、欧拉回路 C、欧拉通路 D、简单回路 5、一棵树有2个结点度数为2，2个结点度数为3，3个结点度数为4，则它的树叶数为（） A、8 B、9 C、10 D、12 6、G是连通平面图，有5个顶点、6个面，则G的边数为（） A、6 B、5 C、11 D、9 7、设A={1，2，3}，B={1，2，3，4，5}，C={2，3}，则（A∪B）+C=（） A、{1，2} B、{2，3} C、{1，4，5} D、{1，2，3} 8、下列命题中为假的是（） A、{a，{b}}{{a，{b}}} B、φP(∪{φ,{φ}}) C、{a}XaX D、X∪Y=YX=φ 9、设解释T为：个体域为D={—2，3，6}，谓词A(x)：x 6，B(x)：x>5，则根据解释，公式x(A(x)∨B(x))的真值为（） A、0 B、1 C、没有确定真值 10、一个教室公用一个电源，如果想接34盏灯，则至少需要4个插线孔的接线板（）个。 A、10 B、11 C、12 D、34 11、下列说法错误的是（） A、n个结点m条边的有向树和无向树均满足：m=n－1. B、树都是二部图。 C、有向树都是单侧连通的 D、有桥的图不是欧拉图 一、 填空 1．不能再分解的命题称为，至少包含一个联结词的命题称为。 2．一个命题公式A(P , Q, R)为真的所有真值指派是000, 001, 010, 100，则其主析取范式是，其主合取范式是。 3．设 {}，{}，{}，则( A ? B ) ⊕C ＝ 。 4．幂集 P(P(?)) ＝ 。 5．设A 为任意集合，请填入适当运算符，使式子?；’=?成立。 6．设{0，1，2，3，6}，{〈〉≠y ∧(∈A)∧y≡x( 3)}，则D(R)，R(R)。 7．称集合S 是给定非空集合A 的覆盖：若{S 1，S 2，…，}，其中?，≠?，1，2，…，n ，且 ；进一步若 ，则S 是集合A 的划分。 8．两个重言式的析取是 式，一个重言式和一个永假式的合取式是 式。 9．公式 ┐(P ∨Q) ←→(P ∧Q)的主析取范式是 。 10. 已知Π={{a}{}}是{}的一个划分，由Π决定的A 上的一个等价关系是 。 二、 证明及求解 1．求命题公式（P →Q ）→（Q ∨P ）的主析取范式。 2．推理证明题 1）?P ∨Q ，?Q ∨R ，R →S ?P →S 。 2) (?x)(P(x)→Q(y)∧R(x))，(?x)P(x)?Q(y)∧(?x)(P(x)∧R(x)) 3．设{0，1，2，3}，{〈〉∈A ∧(1∨2x )}，{〈〉∈A ∧（2）}。试求οο。 4．证明：R 是传递的?R *R ?R 。 5．设R 是A 上的二元关系，{ 专科《离散数学模拟》试题（一） 姓名______________ 学号______________ 成绩______________ 一、填空（每小题5分，共25分） 1．设}41,,3|{≤≤∈==K N k k x x A ，则用列举法表示A =_____________________。 2．设}2,{φ=A ，则A 的幂集=A 2________________________。 3．设)}1,2(),2,4(),3,1{(=ρ是A 到B 的关系，则ρ的逆关系=ρ~_______________。 4．下图G 的邻接矩阵 A =__________________________ 5．设}},3,2{,3,2{φ=A ，则=-}}3,2{{A ____________________________。 二、选择题（将正确答案的编号填入相应题目后面的括号中，每小题5分，共20分） 1．设集合}3,2,1{=A ，A 上的关系)}1,1(),1,2(),1,3(),3,2{(=ρ，则ρ是（ ）。 A ．自反的 B ．反对称的 C ．可传递的 2．设有函数Z Z Z f →?:（Z 表示非负整数集），定义为y x y x f +=),(，则f 是（ ）。 A ．满射 B ．内射 C ．双射 3．设}4,3,2,1{=A ，则A 的分划有（ ）。 A ．}}3{},4,2{),1{( B ．}}4{},3,2{{ C ．}}4{},3,2,1{{ 4．设简单图G 所有结点的度之和为12，则G 一定有（ ）。 A ．3条边 B ．4条边 C ．6条边 4 v 3v 2 v 1 v 目录 离散数学模拟题一 (1) 离散数学模拟题二 (3) 离散数学模拟题三 (7) 离散数学模拟题四 (9) 离散数学模拟题五 (12) 离散数学模拟题六 (16) 离散数学模拟题七 (18) 离散数学模拟题八 (21) 离散数学模拟题九 (24) 离散数学模拟题十 (25) 离散数学模拟题十一 (27) 离散数学模拟题十二 (33) 离散数学模拟题十三 (34) 离散数学模拟题十四 (37) 离散数学模拟题十五 (42) 离散数学模拟题十六 (50) 离散数学模拟题一 一、判断题（共12分，每小题1分） ( ) 1、（?p∨?q）→(p→?q)不是重言式。 ( )2、在命题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。 ( ) 3、命题函数是命题。 ( ) 4、设A，B，C是Q的子集，则有A?(B⊕C)≠（A?B）⊕（A?C）。 ( )5、设A、B为集合，若B≠Φ，则A-B包含于A。 ( ) 6、若R为集合A上的非对称关系，则R2亦然。 ( )7、存在一种建立在某个集合上的关系，它可以是对称的、反对称的、自反的、反自反和可传递的。 ( )8、设〈G，*〉是群，对于G中的任意元素a，b有：（a ? b）-1=b-1 ? a-1。 ( )9、在一个代数系统中，某个元素有多个左逆元，就不可能有右逆元。 ( )10、设是非连通平面图G的对偶图中的顶点数，边数和面数，则它们之间不满足欧拉公式； ( )11、设无向图G具有割点，则G中一定不存在汉密尔顿回路； ( )12、有向图G是单侧连通； （G） 二、求出下列命题公式的主析取范式和主合取范式。（10分） (P→(Q∧R))∧(?P→(?Q∧R)) 三、逻辑推证（10分） （1）?（P→Q）→? (R∨S)，((Q→P) ∨?R) ，?(R→P) ? P→Q 四、用谓词推理理论来论证下述推证（10分） 任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行。离散数学模拟题(开卷)
离散数学模拟试卷和答案
离散数学(上)模拟题
离散数学模拟试题及答案
离散数学模拟试卷和答案
离散数学考试试题(A、B卷及答案)
离散数学期末试卷A卷及答案
离散数学模拟卷(简单)
离散数学模拟题及答案
离散数学试题2018模拟1+答案
离散数学模拟题1
离散数学期末试卷及答案
离散数学模拟试题1
离散数学模拟题及答案
专科离散数学模拟试题(一)
离散数学模拟试卷(中文)
相关主题
文本预览