离散数学模拟试题Ⅰ
一、单项选择题（本大题共 15 小题，每题 1 分，共 15 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分
2
1．设
A
{ x
x 是整数且 x
16}
，下面哪个命题为假（ A ）。
A 、{0,1,2,4} A ；
B 、{ 3, 2, 1}
A ；
C 、
A ；
D
、
{ x x 是整数且
x 4}
A
。
2．设
A
, B { ,{
}}
，则B －A 是（
C ）。
A 、{{
}}；
B 、{ }；
C 、{ ,{ }}；
D 、 。
a
3．右图描述的偏序集中，子集
{ b , e , f }
的上界为 （
B
）。
c
A 、 b ，c ；
B 、a ，b ；
C 、b ；
D 、a ，b ，c 。
4．设 f 和 g 都是 X 上的双射函数，则
( f g)
1
为（C ）。
f
d
A 、 f 1 g 1 ；
B 、 (g f ) 1 ；
C 、 g 1 f 1 ；
D 、 g f 1 。
5．下面集合（
B ）关于减法运算是封闭的。
A 、 N ；
B 、 { 2x x I } ；
C 、 { 2x 1 x I } ；
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．设
G
{ 2 m 3n m , n
I }
，* 为普通乘法。则代数系统
G ,
的幺元为（ B ）。
A、不存在； B 、e2030； C 、 e 2 3 ； D 、e 2 1 3 1。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．设 V{ a , b , c , d , e , f } ，
E { a , b , b , c , c , a , a , d , d , e , f , e} ，则有向图
G V ,E
是（C）。
A、强连通的； B 、单向连通的； C 、弱连通的； D 、不连通的。10．下面那一个图是欧拉图（A）。
11．在任何图中必定有偶数个（C）。
A、度数为偶数的结点；
B、入度为奇数的结点；
C、度数为奇数的结点；
D、出度为奇数的结点。
12．含有 3 个命题变元的具有不同真值的命题公式的个数为（C）。
A、23；
B、32；
C、223；
D、232。
13．下列集合中哪个是最小联结词集（ A ）。
A、{ , }；
B、{, }；
C、{ , }；
D、{,,}。
14．下面哪个命题公式是重言式（ B ）。
A、(P Q) (Q R)；
B、(P Q)P；
C、( P Q)(P Q)；
D、(P Q)P。
15．在谓词演算中，下列各式哪个是正确的（ A ）。
A、 x yA( x, y)y xA( x, y) ； B 、x yA( x, y)y xA(x, y) ；
C、 x yA( x, y)y xA(x, y) ； D 、A(a)xA(x) 。
二、多项选择题（本大题共 5 小题，每题 2 分，共 10 分）在每小题列出的五个备选项中有二个至五个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。
1、设 A＝{1,2,3}，则右图所示A上的关系具有（2）4)5)）。
1
1).自反性2).反自反性3).对称性
4).反对称性5). 传递性
23 2、下列语句是命题的有（ 1 ）3)）。
1).明年中秋节的晚上是晴天；2).x y 0 ；
3).xy 0
当且仅当 x 和 y 都大于 0； 4). 我正在说谎。
3 A B
为二合式公式，且A B ，则（1） 2)3)4)5)
）。
、，
1).A B为重言式；2).A*B*；3). A B ；
4).A*B*；5).A B 为重言式。
4、右图所示的图一定不是（1） 2)3)5)）。
1).平面图2). 二部图3). 欧拉图
4).哈密而顿图5). 树
5、设 R 和 S 是集合 A 上的任意关系，下列命题不成立（2）3)4)）。
1).若 R和 S 是自反的，则 R S 也是自反的。
2).若 R 和 S 是反自反的，则 R S 也是反自反的。
3).若 R和 S 是对称的，则 R S 也是对称的。
4).若 R和 S 是传递的，则 R S 也是传递的
三、填空题（本大题共 5 小题，每题 2 分，共 10 分）
1、 P：你努力， Q：你失败。“除非你努力，否则你将失败”的翻译为（1）～P→Q或～ Q→ P；“虽然你努力了，但还是失败了”的翻译为（2）P∧Q。
2、设 A={2，3，4，5，6} 上的二元关系R{x, y| x y x是质数 }
，则
R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3
,5>,<3,6>,<4,5>,
1 1 1 11
1 1 1 11
0 0 0 11
1 1 1 11
0 0 0 00
<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>}
（枚举法）。
R的关系矩阵M R=
3、设代数系统
*a b c 则幺元是（1）a；是否有幂等性a a b c
（2）F。b b b c
c c c b
4、设 A={1，2，3} ，则 A 上既不是对称的又不是反对称的关系
R= {<1,2>,<1,3>,<2,1>}；A上既是对称的又是反对称的关系
R= {<1,1>,<2,2>,<3,3>}。
5、 n 个结点的无向完全图K n的边数为
（1）n(n－1)/2，欧拉图的充要条件是
图中无奇度结点且连通。
四、演算题（本大题共 5 小题，每题 7 分，共 35 分）
1、设 A={1，2} ， A 上所有函数的集合记为 A A, 是函数的复合运算，试给出 A A上运算的运算表，并指出 A A中是否有幺元，哪些元素有逆元。
解：
幺元为，、有逆元
2、设 E( x1 , x2 , x3 ) ( x1x) ( x2x)( x x3 ) 是布尔代数{ 0,1}, , ,上
231
的一个布尔表达式，试写出其主析取范式和主合取范式。
解：函数表为：
x1x2x3E( x1 , x2 , x3 )
0000
0011
0101
0111
1001
1011
1101
1110
主析取范式：
E(x1,x2,x3) (x1x2x3) (x1x2x3) (x1x2x3) (x1x2 x3) (x1x2 x3) (x1x2x3)
主合取范式：
E( x1 , x2 , x3 ) ( x1x 2 x3)( x1x 2x 3 )
3、如右图所示的赋权图表示某七个城市 v 1
, v 2
, , v
7
及预先算出它们之间的一些直接通信线路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。
解： 用克鲁斯克尔（ Kruskal ）算法求产生的最优树。算法为：
w(v , v
7
)
1
选 e
v v
7
1
1 1
w(v
7 , v
2
)
4
选 e
v
7 v
2
2
w(v 7 , v 3 ) 9
选 e 3
v 7 v 3
w(v 3 , v 4 ) 3
选 e v 3 v 4
w(v 4
, v 5 )
17
选 e v 4 v 5
w(v 1
, v 6 )
23
选 e
v 1v 6
结果如图：
树权 C(T)=23+1+4+9+3+17=57（万元）即为总造价。
4、已知有如右图的偏序关系，求出其子集
A={b,c,d,e} 的
极大元、极小元、最大元、最小元、最小上界和最大下界。
解：极大元： e
极小元： b,d
f
g
e
c
d
b
a
最大元： e
最小元：无
最小上界： e
最大下界： a
5、设 A { a , b , c} ，A上的关系{ a , a , a , b , b , c , c , b} ，求出
r ( ) , s( ) 和 t () 。
解：r (
){a, a,a, b,b,c,c, b,b,b,c, c } s(){a, a,a, b,b, c,c,b,b, a} ，
2
{ a, a , a, b , a, c , b, b , c, c }，
32{ a, a , a,b , a, c , a,b , b,c , c, b }
，t ()2{a, a,a,b ,a,c ,b, b, c, c, b, c , c,b }
五、证明题（本大题共 3 小题，每题 10 分，共 30 分）
1、证明： (P (Q S)) ∧(R∨P)∧Q R S
证：（ 1）R附加前提
（2） R∨P P
（3）P T(1)(2)，I
（4）P (Q S) P
（5）Q S T(3)(4)，I
（6）Q P
（7）S T(5)(6)，I
（8）R S CP
2、如果集合 A 上的关系 R 和 S 是自反的、对称的和传递的，
证明： R S 是 A 上的等价关系。
证明：（1） a A , R , S自反，a, a R , a,a S ,
a, a R S ,R S自反。
（ 2）a, b A
，若a, b R
S
，则a, b R , a, b
S,
由 R，S对
称，所以，b, a R ,b, a S ,b, a R S
，所以 R S 对称。
（3） a,b, c A ，若a, b R S , b,c R S , 则a,b R , a,b S , b, c R , b, c S , 由R，S传递性知，a, c R , a, c S , 从而
a, c R S,
所以，R S传递。
综上所述， R S 是A上的等价关系。
3、若无向图 G中只有两个奇数度结点，则这两个结点一定连通。
证：由题设，在无向图G中只有两个奇数度结点，
因此，在这两个奇数度结点之间作一条边，则在该图中所有的结点的度数
都是偶数，由欧拉图的充要条件，在图中必然存在一条欧拉回路，将此边从欧
拉回路中删除，在这两个奇数度结点间还存在一条欧拉道路，所以，这两个结
点一定连通。
离散数学模拟试题Ⅱ
一、单项选择题（本大题共15 小题，每题 1 分，共 15 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1、设S{,{1}, {1,2}}
，则2S有（D）个元素。
A.3；B．6；C．7；D．8。
2、设S{ 1, 2, 3}
，定义S S上的等价关系
R {a, b ,c, d | a, b S S, c, dS S, a d b c} 则由R产生的 S S上一个划分共有（ B ）个分块。
A．4； B．5； C．6； D ．9。
解释：
=
=，=，=
=
3、设S { 1, 2, 3 }
，S 上关系 R的关系图如右图所示，则R具有（ D ）性质。
A．自反性、对称性、传递性；B ．反自反性、反对称性；C．反自反性、反对称性、传递性； D ．自反性。
4、设,
为普通加法和乘法，则（ A ）
S,,
是域。
A．S { x | x a b 3 , a, b Q}B．S { x | x 2n , a, b Z}
C．S { x | x 2n 1, n Z}D．S { x | x Z x 0}= N。
5、下面偏序集（B）能构成格。
6、在如图所示的有向图中，从V1到 V4长度为 3 的道路有
（ B ）条。
A．1；B．2；C．3；D．4。
7、在如下各图中（ B ）是欧拉图。
8、“人总是要死的”谓词公式表示为（C）。（论域为全总个体域）M(x)：x 是人； Mortal(x)：x是要死的。
A.M ( x)Mortal (x) ；
B.M ( x) Mortal ( x)
C.x(M (x)Mortal (x)) ；
D.x(M ( x)Mortal ( x))
9、公式A x(P( x)Q (x))
的解释I为：个体域D={2}，P(x)：x>3, Q(x)：x=4则 A 的真值为（A）。
A. 1 ；
B. 0；
C.可满足式；
D.无法判定。
10、下列等价关系正确的是（ B ）。
A.x( P(x) Q( x))xP( x)xQ( x) ；
B.x( P(x) Q (x))xP(x)xQ(x) ；
C.x( P(x)Q )xP( x)Q ；
D.x( P( x)Q )xP( x)Q 。
11、下列推理步骤错在（B）。
①x(F ( x)G (x))P
② F ( y)G ( y)US①
③xF ( x)P
④ F ( y)ES③
⑤ G ( y)T②④ I
⑥xG( x)EG⑤
A. ②；
B.④；
C.⑤；
D.⑥
12、下列命题公式为重言式的是（A）。
A．p→ (p ∨ q)B．(p∨┐ p)→q C．q∧┐ q D．p→┐ q
13、下列语句中是真命题的是（ C ）。
A ．我正在说谎B．严禁吸烟
C ．如果 1+2=5，那么雪是黑的D．如果1+2=3，那么雪是黑的
14、设 p：我很累， q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是（D）。
A．┐ p∧q B．┐ p→q C．┐ p→┐ q D．p→┐ q
15、 A={1，2， 3} ，A 上二元关系 S={<1， 1>，<1， 2>，<3，2>，<3，3>} ，
S是（D）。
A．自反关系； B ．反自反关系； C ．称关系； D ．关系；
二、多（本大共 5 小，每 2 分，共 10 分）在每小列出的五个中有二个至五个
是符合目要求的，将其代填写在后的括号内。、多、少或未均无分。
1、下面在集合和学中正确的公式有 (1)2 ）4）)。
1) P ∧～P R∧Q； 2) R QP～P；3)2A U2B2AUB；
4) A ⊕B=A⊕ C B=C；
2、有如下命
A)如果地上有水，天上下雨
B)如果天上下雨，地上有水
C)如果地上没有水，天上不下雨
D)如果天上不下雨，地上没有水
哪些命等价的（2）4））。
1）. A) 与 B)等价；2）. A)与D)等价；3). A)与C)等价；
4）. B)与C)等价
3、 G={0,1,2, ? ,n} ，n∈N，定模n加法，即x y=(x+y) modn，代数
系(G，)(1)2 ）) 。
1).是循群2).是交群3).是半群但不是群4).是无限群
4、 G是一个 35 群， a∈ G， a 的周期不可能是（1）2）3）4））。
1).12).23).34).45).5
5、下列哈斯中，是格的有（3） 4））。
1). 2). 3). 4). 5).
三、填空题（本大题共 5 小题，每题 2 分，共 10 分） 1．设
A
{ 2 , a , {3} , 4} ， B
{{ a} , 3 , 4 , 1}
，请在下列每对集合中填入适当的符
号： { a}
∈ B , (2)
{ a , 4 , { 3}}A 。
0 ， 是奇数，
f ( x)
， 是偶数。
2．设
A { 0 ,1}
，N 为自然数集，
1 x
若
f ：A
A
，则
f
是 双
射的；若
f ：N
A
，则
f
是 （2） 满 射的。
3．设图 G = < V ，E >中有 7 个结点，各结点的次数分别为
2，4，4，6，5，5，
2 ，则 G 中有（1） 14
条边，根据 （2）
。
4．两个重言式的析取是 （1）重言式 ，一个重言式和一个矛盾式的合是 （2）
矛盾式
。
5．设个体域为自然数集，命题“不存在最大自然数”符号化为
。
四、演算题（本大题共 5 小题，每题 7 分，共 35 分 ）
1、设集合 A ＝ {a ，b ，c} ，A 上的关系
计算
解：
R1R2{ a, a , a, b , b, b , c, c}
R1R2{ a, a , a, b , a, c , b, a , b, c , b, b , c, c}
R11{ a, a , b, a , b, b , c, a , c, b , c, c}
r (R1 ) R1t( R1 )R1
s(R1 ) { a, a , a,b , a, c , c, a , b, a , b, c , c, b b, b , c, c}
2、有向图 G如右图所示，试求：
(1)求 G的邻接矩阵 A。
(2)求出可达矩阵 P。
(3)所有强分图。
解 (1) 求G的邻接矩阵为：
0 1 01
0 0 11
A
0 1 01
0 1 00
(2)可达矩阵为
0 1 1 1
0 1 1 1
P
0 1 1 1
。
0 1 1 1
0 1 1 1
0 0 0 0 (3) 因为 P P
T
0 1 1 1 ∧ 1 1 1 1 ＝ 0 1 1 1 1 1 1 1
0 1 1 1
1 1 1 1
1 0 0 0 0 1 1 1 0 1 1 1
0 1 1 1
，
所以 { v 1 } ， { v 2 ， v 3 ， v 4 } 构成 G 的强分图。
3、右图给出的赋权图表示五个城市
v 1 ， v 2 ， v 3 ， v 4 ， v 5 及
对应两城镇间公路的长度。 试给出一个最优化的设计方案使得各城市间能够有公路连通。
解：此问题的最优设计方案即要求该图的最小生成树，
由破圈法或避圈法得最小生成树为：
其权数为 1+1+3+4 = 9 。
4、已知有如图的偏序关系，并求出其子集 A={b,c,d,e} 的极大
f
g
元、极小元、最大元、最小元、最小上界和最大下界。
e
解：极大元： e
c d
极小元： b,d
b
a
最大元： e
最小元：无
最小上界： e
最大下界： a
5、已知 G {1，2 ，3 ，4 ，5 ，6} ，7模7乘法。明G，7是否构成群？是否循群？若是，生成元是什么？
解：因 G于7 是封的，同足合律， 1 是幺元， 3 和 5，2 和 4，6
和 6 互逆元，所以G，7构成群。
是循群，生成元是（ 3）。
五、证明题（本大题共 3 小题，每题10 分，共 30 分）
1、x(P(x) ∨Q(x)) ，x P(x)x Q(x)
明：
(1)x P(x)P
(2)P(c)T(1)，US
(3)x(P(x) ∨ Q(x)) P
(4)P(c)∨ Q(c)T(3)，US
(5)Q(c)T(2)(4)，I
(6) x Q(x)T(5)，EG
2、={A ，A ，?， A } 是集合 A 的一个划分，定 R={
12n i
2，?， n} ， R 是 A 上的等价关系。
明教材
3、
证明：
[ 幺 ]a R ，
0 * a 0 a 0 a a , a * 0 a 0 a 0
即 0 * a a * 0 a0为幺元
[ 闭 ]a, b R
，由于 +，·在 R封闭。所以
a *
b a b a b R即*在 R上封闭。[ 结 ]a, b,
c R
( a * b) * c (a b a b c a b a * (b* c) a b 所以( a * b) * c
a b) * c a
b a b
c (a
a c
b
c a b c
c a b a c b c a b c
a * (
b * c)
b a b) c
因此，〈R，* 〉是含幺半群。
离散数学模拟试题Ⅲ
一、单项选择题（本大题共 15 小题，每题 1 分，共 15 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、
多选或未选均无分
1．下列命题公式是永真式的是（ B ）。
A．（ P∧～ P）? Q B．（～（P→Q）∧ Q）→ Q
C．（ P→ Q）∨ Q D．（P∨P）∧（P→～P）
2．命题公式 A 不存在主合取范式，则A是（C）
A．矛盾式 B ．可满足式C．永真式 D ．都不对
3．谓词公式（ x）P（X）→（x）P（X）是（ D）
A．可满足式 B ．矛盾式C．无法判别 D ．永真式
4．公式（x）（y）（ P（ x,y ）∧ Q（z））→ R（ x）中的 x （C）A．仅是约束变元B．仅是自由变元
C．既是约束变元又是自由变元 D ．既不是约束变元也不是自由变元
5．设 A、B、C 是集合，下列四个命题中， ( D) 在任何情况下都是正确的。
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
6．下面的表达哪个不正确（ A）
A． {a} {{a}} B．{a} ∈{{a}}C．{a} {a ，{a}}D． {a} ∈{a ， {a}} 7．若集合 A 中共有 n 个元素，那么 A 上不同二元关系的个数为（ B）A． B ． C ． D ．都不对
8．下列判断正确的是（C）
A．若 R，S 是自反的，则 R-S 是自反的
B．若 R，S 是对称的，则 R○S 是对称的
C．若 R，S 是传递的，则 R∩ S 是传递的
D．若 R，S 是传递的，则 R ∪S 是传递的
9．设 R，S 是非空集合上的等价关系，则R∪S 是（ C）A．一定具有自反性，但不一定保持对称性
B．一定具有对称性，但不一定保持自反性
C．一定具有自反性和对称性
D．是等价关系
10．在A． 55 个元素的集合上可以定义的单射数目为
B．10C．60D．120
（D）
11．设函数的是（A． |X|=| Y|f ：X→ Y；X，Y
B）
B ．|X| ﹥|Y|
是有限集合， f
C．|X|﹤|Y|
是单射，那么下列关系一定不成立
D ．X∈Y
12．平面非连通图G， n-m+f的值为（C）
A． 2B．ω（ G）C．ω（G）+1 D ．3
13．若一棵树 G（n，n-1 ）只有两个叶节点，则（ B ）不正确
A．不包含点度大于等于 3 的枝点 B ．节点总度数大于等于4
C．最少包含 2 个节点D．节点总度数=2+2（n-2 ）14．设 10 阶简单连通图有32 条边，则最少要去掉（D）条边才能使其成为平面图
A． 10 B ．12 C ．32 D ．8
15. 下列代数系统 < S ， *>中，哪个是群？（D）
A. S
{0,1,3,5} ，*是模7加法 B.S
Q
（有理数集合），* 是一般乘法
离散数学考试（试题及答案） 一、（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．下面四组数能构成无向图的度数列的有( )。 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
离散数学试题(A卷及答案） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分） 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D
(7) R∨S 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明（1）?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍 证明设 1 a，2a，…，1+m a为任取的m＋1个整数，用m去除它们所得余数 只能是0，1，…，m－1，由抽屉原理可知， 1 a，2a，…，1+m a这m＋1个整 数中至少存在两个数 s a和t a，它们被m除所得余数相同，因此s a和t a的差是m的整数倍。 五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分）证明∵x∈ A-（B∪C）? x∈ A∧x?（B∪C）? x∈ A∧（x?B∧x?C）?（x∈ A∧x?B）∧（x∈ A∧x?C）? x∈（A-B）∧x∈（A-C）? x∈（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C） 六、已知R、S是N上的关系，其定义如下：R={
一、填空 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.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 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 离散数学模拟试题Ⅰ 一、单项选择题(本大题共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.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 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 一．将下面命题写成符号表达式。(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 求证 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 一、 填空 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 1v 三、问答题（每小题6分，共42分） 1．下图G 是否二部图？若是，找出它的互补结点子集. 2．设有命题公式)(Q P P F →?∨=，问F 3．判断下图是否欧拉图，若是，找出一个欧拉回路. 4．设1ρ和2ρ是集合A 上的偏序关系，问1ρ－ 5．判断下述命题公式的等值关系是否成立 P Q P Q P Q ∨??→∧→)(( 6．将下一命题符号化.分析到个体词、谓词和量词，使用全总个体域. “有些大学生不钦佩任何运动员” v 2v 1v 5 3v 5v 《离散数学》课程试题(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 、Φ。 《离散数学》模拟试题3 一、填空题（每小题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. 已知命题公式R Q P G→ ∧ ? =) (，则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分） 1. （6分）设全集E＝N，有下列子集：A＝{1，2，8，10}，B＝{n|n2<50 ，n∈N}，C＝ {n|n可以被3整除，且n<20 ，n∈N}，D＝{n|2i，i<6且i、n∈N}，求下列集合：（1）A∪(C∩D) （2）A∩(B∪(C∩D)) （3）B－(A∩C) （4）(～A∩B) ∪D 2. （6分）设集合A＝{a, b, c}，A上二元关系R1，R2，R3分别为：R1＝A×A， R2 ＝{(a，a)，(b，b)}，R3 ＝{(a，a)}，试分别用 定义和矩阵运算求R1·R2 ， 2 2 R，R 1 ·R2 ·R3 ， (R1·R2 ·R3 )－1 。 3.（6分）化简等价式（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）. 4.(8分) 设集合A＝{1,2,3}，R为A上的二元关系，且 M R＝ 写出R的关系表达式，画出R的关系图并说明R的性质. 5. （10分）设公式G的真值表如下. 试叙述如何根据真值表求G的 主析取范式和主合取范式，并 写出G的主析取范式和主合取范式. 1 0 0 1 1 0 1 0 0 华南理工大学网络教育学院 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) 。 （ × ） 《离散数学》模拟试题 一、 填空题（每小题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 →∧?=)( 一、选择题（每小题只有一个正确答案，每题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、有桥的图不是欧拉图 《离散数学》期末考试考点及模拟题答案 一、考试题型及分值 各种题型所占的比例： 填空题10%，判断题10%，选择题20%，其它题型60% 新出试卷按照如下各种题型所占的比例： 填空题20%，判断题15%，选择题30%，其它题型35% 二、考点 1．命题逻辑 熟练掌握命题及其表示; 掌握常用联结词(?、∧、∨、→、 )的使用; 熟练掌握命题公式的符号化; 熟练掌握使用真值表判别命题等价的方法; 掌握使用等价公式判别命题等价的方法; 掌握重言式与蕴含式的概念及其判别方法;了解其他联结词的使用;了解对偶的概念; 掌握求命题范式的方法; 熟练掌握命题演算推理的基本理论。 2．谓词逻辑 熟练掌握谓词的概念及其表示; 熟练掌握量词的使用; 掌握使用谓词公式翻译命题的方法; 掌握变元的约束; 掌握谓词演算中等价式与蕴含式的判别;了解前束范式的求法; 熟练掌握谓词演算推理的基本理论。 3．集合与关系 熟练掌握集合的概念和表示法; 掌握集合的基本运算; 掌握序偶与笛卡尔积的概念; 熟练掌握关系及其表示; 掌握关系的基本性质;了解复合关系和逆关系的概念; 掌握关系的闭包运算; 了解集合的划分和覆盖; 掌握等价关系与等价类的概念; 了解相容关系的概念; 掌握各种序关系的概念。 4．函数 熟练掌握函数的概念; 掌握逆函数和复合函数的概念;了解基数的概念; 了解可数集与不可数集; 了解基数的比较。 5．代数结构 掌握代数系统的概念; 掌握n元运算及其性质; 掌握半群、群与子群的概念; 了解阿贝尔群和循环群的概念; 了解陪集与拉格朗日定理; 了解同构与同态的概念; 了解环与域的概念。 6．图论 离散数学模拟试题1 一、单项选择题（本大题共8小题，每小题2分，共16分） 1.p:a是2的倍数，q:a是4的倍数。命题“除非a是2的倍数，否则a不是4的倍数。”符号化为（）； A．p→q B．q→p C．p→?q D．?p→q 2.设解释Ⅰ如下: 个体域D＝{a,b}，F(a,a)= F(b,b)=0,F(a,b)=F(b,a)=1,在解释Ⅰ下,下列公式中真值为1的是（）； A. ?x?yF(x,y) B. ?x?yF(x,y) C. ?x?yF(x,y) D.??x?yF(x,y) 3.设G为n阶m条边的无向简单连通图，下列命题为假的是 A.G一定有生成树 B.m一定大于等于n C.G不含平行边和环 D.G的最大度?（G）≤n-1 4.设G为完全图K5，下面命题中为假的是（） A. G为欧拉图 B.G为哈密尔顿图 C. G为平面图 D.G为正则图 5.对于任意集合X,Y,Z,则 A. X∩Y=X∩Z?Y=Z B. X∪Y=X∪Z?Y=Z C. X－Y=X－Z?Y=Z D. X⊕Y=X⊕Z?Y=Z 6.下面等式中唯一的恒等式是 A.A∪B∪C－(A∪B)=C B. A⊕A=A C. A－(B×C)=(A－B)×( A－C ) D.A×(B－C)=(A×B)－(A×C) 7.设R为实数集,定义*运算如下:a*b=∣a+b-ab∣, 则*运算满足 A.结合律 B.交换律 C.有幺元 D.冥等律 8.在有补格L中, 求补 A. 是L中的一元运算 B.一定有唯一的补元 C.不一定是L中的一元运算 D.可能没有补元. 二、填空题（本大题共8小题，每空3分，共24分）请在每小题的空格中填上正确答案。错填、不填均无分。 1.含n个命题变项的重言式的主合取范式为. 2.设个体域为整数集合Z，命题?x?y(xy=1)的真值为. 3.任何一棵非平凡树至少有片树叶. 4.已知n阶无向简单图G有m条边, 则G的补图G有条边. 5.设R={〈{1},1〉,〈1,{1}〉, 〈2,{3}〉, 〈{3},{2}〉},则 domR⊕ranR= . 6.设A={1,2}, B={1,2,3},则从A到B的不同函数有个. 7.如果无向连通图G有n个顶点m条边，并且m≥n，则G中必含有. 8.设B为布尔代数,a,b,c∈B，则（a∧b）∧(a∨c)∨a的化简式. 三、简答题（本大题共8小题，每小题5分，共40分） 1.设p：2＋2＝4，q：3＋3＝7，r：4＋4＝8，求下列各复合命题的真值： (1)(p∧q)?r (2)(p?r)?(q?r) (3)(p∨┐q)→(q→r) (4) ┐q→(p?r) (5) (p∨q)→(┐p∧┐q∧r) 2.求公式?x (┐?yF(x,y) →?zG(x,z))的前束范式. 3.已知无向图G有12条边，1度顶点有2个，2度、3度、5度顶点各1个，其余顶点的度数均为4，求4度顶点的个数. 4.已知连通的平面图G的阶数n=6,边数m=8,面数r=4.求G的对偶图G*的阶数n*,边数m*,面数r*. 5.设A={{a,{b}},c,{c },{a,b}},B={{a,b},{b}},计算 (1)A∩B (2)A⊕B (3)P(B) 目录 离散数学模拟题一 (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分） 任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行。离散数学模拟试卷和答案
离散数学模拟题1
离散数学期末试题及答案完整版
离散数学模拟题及答案
专科离散数学模拟试题
离散数学模拟卷(简单)
离散数学第五版--模拟试题--及答案
离散数学试题2018模拟1+答案
离散数学模拟试题及答案
离散数学模拟试题1
《2013离散数学课程 》模拟题答案
离散数学模拟试题1
离散数学模拟试卷(中文)
相关主题
文本预览