离散数学期末练习题-(带答案)
离散数学复习注意事项：
1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容
系统复习一遍。
2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。
3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。
离散数学综合练习题
一、选择题
1．下列句子中，（）是命题。
A．2是常数。 B．这朵花多好看呀！
C．请把门关上！D．下午有会吗？
2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了”
可符号化为（）。
A. p q r
∨→
∧→ B. p q r
C. p q r
∨?
∧∧ D. p q r
3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。
A.p q
∧
∧? B.p q
C.p q
→?
∨? D. p q
4．设()
Q x:x会飞，命题“有的鸟不会飞”可符号P x:x是鸟，()
化为（）。
A. ()(()())
Q x
??∧())
x P x
??→ B. ()(()
x P x Q x
C. ()(()())
Q x
??∧())
x P x
??→ D. ()(()
x P x Q x
5.设()
f x:x的绝对值，(,)
L x y：x大于等于y；命P x:x是整数，()
题“所有整数的绝对值大于等于0”可符号化为（）。
A. (()((),0))
?→
x P x L f x
x P x L f x
?∧B. (()((),0))
C. ()((),0)
xP x L f x
?→
?∧ D. ()((),0)
xP x L f x
6.设()
G x:x犯错误，命题“没有不犯错误的人”符
F x:x是人，()
号化为（）。
A．(()())
??→?
x F x G x
x F x G x
?∧B．(()()) C．(()())
??∧?
x F x G x
x F x G x
??∧D．(()())
7.下列命题公式不是永真式的是（）。
A. ()
→→
p q p
p q p
→→ B. ()
C. ()
→∨
p q p
p q p
?∨→ D. ()
8．设()
Q x为实数。命题“任何有理数都是实数”
R x为有理数；()
的符号化为（）
A．()(()())
x R x Q x
?∧
x R x Q x
?∧B．()(()())
C．()(()())
?→
x R x Q x
?→
x R x Q x D．(()())
9.设个体域{,}
=，与公式()
D a b
?等价的命题公式是( )
xA x
A．()()
→
A a A b
A a A b
∧B．()()
C．()()
→
A b A a
A a A b
∨D．()()
10.下列等价式不正确的是（）。
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 x xP x xQ x
D．(())()
?∧??∧
x P x Q xP x Q
11. 设个体域{,}
xA x
?等价的命题公式是( )
=，与公式()
D a b
A．()()
A a A b
→
A a A b
∧B．()()
C．()()
→
A b A a
A a A b
∨D．()()
12.设{,{},{,}}
??，则下列陈述正确的是（）。
a a
A.a X
∈ B.{,}
??
a X
C.{{,}}
?∈
?? D.{}X
a X
13.有向图D是连通图，当且仅当（）。
A. 图D中至少有一条通路
B. 图D中有通过每个顶点至少一次的通路
C. 图D的连通分支数为一
D. 图D中有通过每个顶点至少一次的回路
14.设{}，则下列是集合A的划分的是( )
A.{{,},{}}b c c B . {{},{,}}a b c C.{{,},{,}}a b a c D. {{,},}a b c 15.下列谓词公式中是前束范式的是（ ）。
A ．()()()xF x x G x ?∧??
B ．()()xF x yG y ?∨?
C ．(()(,))x P x yQ x y ?→?
D ．(()(,))x y P x Q x y ??→ 16.设12{|()0},{|()0}M
x f x N x f x ====，则方程12()()0f x f x ?=的解为
（ ）。
A ．M∩N
B ．M∪ N
C ．M N C ．
17.设,G A =<*>是群，则下列陈述不正确的是（ ）。
A. 11()a a --=
B. n m n m a a a += C . 111()ab a b ---= D. 11()n n a ba a b a --=
18.在整数集合Z 上，下列定义的运算满足结合律的是（ ）。
A. 1a b b *=+
B. 1a b a *=-
C. 1a b ab *=- D . 1a b a b *=++
19. 设简单图G 所有结点的度数之和为50，则G 的边数为（ ）。
( ) A. 50 B . 25 C. 10 D. 5
20.设简单无向图G 是一个有5个顶点的4－正则图，则G 有（ ）条边。
A. 4
B. 5 C . 10 D. 20
21.设集合{1,2,3,4}A =,A 上的等价关系{1,1,3,2,2,3,R =<><><> 4,4}A I <>U ，则对应于R 的划分是（ ）。
A . {{1},{2,3},{4}} B. {{1,3},{2,4}} C. {{1,3},{2},{4}} D. {{1},{2},{3},{4}}
22.设集合{1,2,3,4}A =,A 上的等价关系{1,3,3,1,2,4,R =<><><> 4,2}A I <>U ，则对应于R 的划分是（ ）。
A. {{1},{2,3},{4}} B . {{1,3},{2,4}} C. {{1,3},{2},{4}} D. {{1},{2},{3},{4}} 23.设,G A =<*>是群，则下列陈述不正确的是（ ）。
A. 11()a a --=
B . 111()ab a b ---=
C. n m n m a a a +=
D. 11()n n a ba a b a --=
24.{1,2,,10}A =L ，下列定义的运算关于集合A 是不封闭的是（ ）。
A. max{,}x y x y *=，即,x y 的较大数
B. min{,}x y x y *=，即,x y 的较小数
C. gcd{,}x y x y *=，即,x y 的最大公约数 D . {,}x
y lcm x y *=，即,x y 的最小公倍数
25. 设{1,2,3},{,,,},{1,,2,,3,}X Y a b c d f a b c ===<><><>，则f 是
( )。
A ．从X 到Y 的双射
B ．从X 到Y 的满射，但不是单射
C ．从X 到Y 的单射，但不是满射
D ．从X 到Y 的二元关系，但不是从X 到Y 的映射
26.设简单无向图G 是一个有6个顶点的5－正则图，则G 有( )条边。
A. 5
B. 6 C . 15 D. 30
27.图G 如下图所示，以下说法正确的是( )。
A ．a 是割点
B ．{}是点割集
C ．{}是点割集
D ．{c }是割点
28.格L 是分配格的充要条件是L 不含与下面哪一个选项同构的子格（ ）。
A ．链
B ．钻石格
C ．五角格
D . 五角格与钻石格 29.下列图是欧拉图的是（ D ）。
30.给定一个有n 个结点的无向树，下列陈述不正确的是（ ）。
A ．所有结点的度数≥2
d
b c
B．无回路但若增加一条新边就会变成回路
C．连通且1
=-，其中e是边数，v是结点数
e v
D．无回路的连通图
31. 设A有5个元素，则其幂集()
P A的元素总个数为（）。
A. 32
B.25
C. 50
D. 5
32．若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是（）。
A. (1,2,2,3,4,5)
B. (1,2,3,4,5,5)
C. (1,1,1,2,3)
D. (2,3,3,4,5,6)
33. 设{,{},{,{}}}
=则其幂集()
P A的元素总个数为（）。
A a a a a
A. 3
B. 4
C. 8
D. 16
34. 在实数集合R上，下列定义的运算中不可结合的是（）。
A. 2
*=++
a b a b ab
B. a b a b
*=+
C. a b a b ab
*=++
D. a b a b
*=-
35. 无向图G是欧拉图，当且仅当（）。
A. G的所有结点的度数全为偶数
B. G中所有结点的度数全为奇数
C. G连通且所有结点度数全为奇数
D. G连通且所有结点度数全为偶数
36.下列不一定
．．．是树的是（）
A. 无回路的连通图D
B. 有n个结点，1条边的连通图
C. 每对结点之间都有通路的图
D. 连通但删去一条边则不连通的图
37. 设简单图G所有结点的度数之和为48，则G的边数为
( )
A. 48
B. 24
C. 16
D. 12
38．下面既是哈密顿图又是欧拉图的图形是（ B ）。
39.下列必为欧拉图的是（ ）
A.有回路的连通图
B.不可以一笔画的图
C.有1个奇数度结点的连通图 D .无奇数度结点的连通图 40.二部图 3,3K 是（ ）。
A.欧拉图 B . 哈密顿图 C.平面图 D. 完全图 41．下列所示的哈斯图所对应的偏序集中能构成格的是（ C ）。
A. B.
C. D.
42.设简单无向图G 是一个有6个顶点的3－正则图，则G 有( )条边。
A. 3
B. 6 C . 9 D. 18 43．下列式子为矛盾式的是（ ）。
A ．()p p q ∨∧
B ．p p ∨?
C ．p p ∧?
D ． ()p q p q ?∨??∧?
44.设集合{,,}A a b c =，A 上的关系{,,,,,}R a a a c c a =<><><>，则R 是（ ）
A ．自反的
B ．对称的
C ．传递的
D ．反对称的
45．设12,R R 是集合{,,,}A a b c d =上的两个关系，其中
1{,,,,R a a b b =<><>
,,,}b c d d <><>，
2{,,,,,,,,,}R a a b b c b b c d d =<><><><><>，则2R 是1R 的（ ）闭包。
A ．自反
B ．对称
C ．传递
D ．自反、对称且传递闭包 46. 下列公式是前束范式的是（ ）。
A ．()()((,)())x y F z x G y ???∨
B ．(()()()())()x F x y G y H z ??∨?∧
C ．()(,)()()x F x y y G y ?→?
D ．()((,)()(,))x F x y y G x y ?→? 47. 设R 为实数集，函数:f R R →，2()25f x x x =-++，则f 是（ ）。
A ．单射而非满射
B ．满射而非单射
C ．双射
D ．既不是单射，也不是满射 48．下列各图中既是欧拉图，又是汉密尔顿图的是（ C ）。
A ．
B ．
C ．
D ．
49．下列四个格，是分配格的是（ C ）。
50．设集合{, c}上的关系如下，具有传递性的是（ ）。
A ． {<>,<>,<>,<>}
B ． {<>,<>}
C ． {<>,<>,<>,<>}
D ． {<>}
参考答案：（若有问题，可以到1#402或打电话问）
一、选择题
二、填空题 1．命题公式()p q ?→的成真指派为 10 ，成假指派为_00，01，11。 2. 命题公式()p q p ∨→的成真指派为00 10 11，成假指派为_01。 3．命题公式()p p q →∧的成真指派为00 01 11 , 成假指派为_ 10。 4．公式()()(()(,))()(,)x y P y Q x z y R x y ??→∧?约束变元为 ，自由变元为 。
5．公式(()())(,)x P x yR y Q x z ?∨?→约束变元为，自由变元为 。 6．设{,,{,}}A a b a b =，{,}B a b =，则B A -=?，A B ⊕= {{}} 。 7．设{1,2,3}A =，A 上的关系{1,2,2,1}R =<><>，则对称闭包
()s R =
{<1,2>,<2,1>} ，传递闭包()t R = {<1,2>,<2,1>,<1,1>,<2,2>}。
8.设*是集合S 上的二元运算，若运算*满足结合律_，并且存在单位元_，则称,*S <>为独异点。
9． 设{,,{,}}A a b a b =，{,,}B a b c =，则A A ⊕=?，A B ⊕= {{}} 。 10.一棵无向树的顶点数n 与边数m 的关系是 1 。6阶无向连通图至多有 6 棵不同构的生成树。
11．设()1f x x =-，2()g x x =，则复合函数()()f g x o =2(1)x -,()()g f x o
=21x -。
12. ,n
Z <⊕>是一个群，其中{0,1,2,,1}n Z n =-L ，()mod x y x y n ⊕=+，则当n =6时，在6
,Z <⊕>中，2的阶为3, 3的阶为_ 2 。 13．设是格，其中{1, 3,4，6，8，12，24}，≤为整除关系，则1的补元是24 ，3的补元是_8_。 14．设｛<1，3>，<3，5>，<4，4>｝，｛<1,3>,<4,5>,<5,5>｝,
那么dom()A B U ={1,3,4,5} ()A B I {3,5} 。
15. 设{l,2,3,4}上的二元关系{<1,2>,<2,3>,<3,2>}，{
则R S o = {<1,3>,<3,3>} ,1()R S -=o {<3,1>,<3,3>} 。
16．设={<1,2>,<3,4>,<3,5>}R 和={<2,1>,<3,3>,<5,5>}S 是集合={1,2,3,4,5}
A
上的两个关系，则R S o = {<1,1>,<3,5>} ， 11S R --o = {<1,1>,<5,3>} 。
17． 设{2, 4, 6}，A 上的二元运算*定义为：a *{}，则在独异点中，单位元是 2 ，零元是 6 。
18．一棵无向树的顶点数n 与边数m 关系是 1 。设G 是具有8
个顶点的树，则G 中增加21 _条边才能把G 变成完全图。 19．设复合函数ο是从A 到C 的函数，如果ο是满射，那么 必是
满射，如果ο是单射，那么 _必是单射。
20．设是格，其中{1, 3, 5, 9, 45}，≤为整除关系，则1的补元是45，3的补元是_ 5 _。
21．给出{l ，2}上的一个等价关系_{<1,1>,<2,2>}_，并给出其对应的划分_{{1},{2}}。
22．设{,,,}A a b c d =，A 上的二元关系{,,,,,}R a b a d b b =<><><>，则R 的自反闭包()r R =A R I U ，传递闭包()t R = R
23．命题公式()p q p ?∨→的成真赋值为 01 10 11 ，成假赋值为 00 。
24．公式()()p q p q ?∧?∨∧的成真赋值是 00,11 。成假赋值 01 10 25．公式()()p q p q ?∧∨∧的成真赋值是 01 11 。成假赋值 00 10
26．公式()()p q p q ∨?∧?∨的成假赋值是 01 10 。成假赋值 00 11
27．设个体域是实数集，命题)3(x x x <-?的真值为 1 ；命
题2(10)x x ?+=的真值为 0 。
28.设f∶R→(x)3∶R→(x)=21,则复合函数(f g)()x =o 24 ,
(g f )(x)=o 27 。
29.给定集合{1,2,3,4,5}，在集合A 上定义两种关系：
{<1,2>,<3,4>,<2,2>},
{<4,2>,<2,5>,<3,1>,<1,3>，则R S =o {<1,5>,<3,2>,<2,5>} 。
30．设{0，1，2，3，6}，{,|,(mod3)}
R x y x y A x y x y
=<>∈∧≠∧≡则 {0， 3，6}_ ，{0， 3，6}，
31．设
6,
Z
<⊕>为模6加群，其中6{0,1,2,3,4,5}
Z=，则2-3= 0 ，4-2= 4 。
32．一个结点为n的无向完全图，其边的数目为n(1)/2 ，顶点的度为 1 。
33. 已知n阶无向简单图G有m条边，则G的补图G中有 n(1)/2条边。
参考答案：
1．_10_，00，01，11
2. 00 10 11， 01_
3. _00 01 11, 10
4.，
5.，
,, {{}}
{1,2,2,1}
<><>，{1,2,2,1,1,1,2,2}
<><><><>
8. 结合律，单位元
9,, {{}，c}
101, 6
11.2
(1)
x-,,21
x-
12. 3 , 2
13. _248
14. {1,3,4,5}，_{3}
15. {<1,3>,<3,3>},{<3,1>,<3,3>}
16. {1,1,3,5}
<><>，{1,1,5,3}
<><>
17. 2 , 6
18. 1, _21
19.,
20. 45 , _5_
21. {1,1,2,2}
<><>,{{1},{2}}
22. A R I U , R 23. 01 10 11，00
24. 00，11 ,01，10 25. 01，11 ,00，10 26. 01 10 , 00 11 27. 1 , 0
28. 24x +,27x +
29. {<1,5>,<3,2>,<2,5>}
30. {0， 3，6}, {0， 3，6} 31. 0 , 4 32. n(1)/2, 1 33. n(1)/2
三、计算题（仅给出部分题目的解题思路，未给出答案自己完成） 1. 已知命题公式()()p q p r ?→→∧ （1）构造真值表
（2）求出公式的主析取范式
（2）()()p q p r ?→→∧
0157
()()()()
p q r p q r p q r p q r m m m m ??∧?∧?∨∧∧?∨∧?∧∨∧∧?∨∨∨
2.已知命题公式()()p q p r ∨→?∨
（1）构造真值表；
（2）用等值演算法求公式的主析取范式。
（2）主析取范式
012
()()()()()()(()())(()r)
(()()(r)(r)p q p r p q p r p q p r p q r r p q q p q r p q r p q p q m m m ∨→?∨??∨∨?∨??∧?∨?∧???∧?∧?∨∨?∧?∨∧???∧?∧?∨?∧?∧∨?∧?∧?∨?∧∧??∨∨ 3．求公式(())()p r p q p →∨∧→ 的主合取范式及主析取范式。 4．构造命题公式(p ?∧)r ∨()p q →的真值表。
5. 一棵（无向）树有2结点的度为2， 1个结点的度为3，3个结点的度为4, 其余都是叶结点，问该树有几个叶结点？ 解：在一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。
根据这两点，可知树中各结点的度数总和=2*（树中点数-1），设树叶有x 个，
于是，2*2+3+3*42*（2+1+31） 得9。
6.一棵无向树T 有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T 有几个顶点？ 提示：类似上题求解。
7.设2:,()2f R R f x x →=-，:,()4g R R g x x →=+,3:,()1h R R h x x →=-， 其中R 表示实数集。
（1）求函数f g o ，g f o ；
（2）,,f g h 哪些函数有反函数？如果有，求出这些反函数。 解：（1）22()(())(4)(4)2814g f x f g x f x x x x =
=+=+-=++o
22()(())(2)2f g x g f x g x x ==-=+o
（2）g 和h 有反函数，11:,()4g R R g x x --→=-；
11:,()h R R h x --→=
8.设A ＝{a ，b ，c}，R 是A 上的二元关系，且R ＝{，}，
求r(R)、s(R)和t(R)。 解：r(R)∪{<>,<>,<>,<>,<>}
s(R)∪1
={<>,<>}
t(R)= R∪R 2∪R 3
={，，，} 9.设{1,2,3,4,6,9,24,54}A =，≤为整除关系。
（1）画出偏序集
（3）求子集｛3, 6, 9｝的上确界与下确界。 解：（1）哈斯图
（2）A 中的极大元为 24，54；极小元为1；最大元：无；最小
元：1
（3）求子集｛3, 6, 9｝的上确界为54，下确界为3。 10.设有向图D 如图所示，用邻接矩阵完成以下计算。
（1）1v 到4v 长度小于或等于4的通路数；
1
9
（2）1v 到自身长度小于或等于4的回路数； （3）求出D 的可达矩阵，并说明D 的连通性。
有向图的邻接矩阵为
1210001000010010A ?????
?=??
????，21
231000100100001A ??
????=??
?
?
?? 31243001000010
010A ?????
?=??
????，41
264000100100
001A ??????=??
?
?
??
（1）v 1到v 4长度小于或等于4的通路数为
4
()14
1
01348i i a
==+++=∑
（2）v 1到自身长度小于或等于4的回路数为
4
()11
1
11114i i a
==+++=∑
（3）11110
111()00110011P D ?????
?=??
??
??
由可达矩阵可知D 是单向连通的。
11．设{0,1,2}A =，给出幂集合()P A 对称差运算的运算表。 12．设6{0,1,2,3,4,5}Z =，给出模6加运算的运算的运算表。 参看教材P167例9.4 与9.5
14. 设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)∪
s(R)∪1
t(R)= {<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>,（2,2>,<5,5>} 15.下图为一连通赋权图，计算该图的最小生成树和权值。
四、简答题 1.设集合}654321{，，，，，A =上的关系{(1,1,1,3,1,6,2,2,R =><><><>
2,5,3,1,3,3,3,6,4,4,5,2,5,5,6,1,6,3),6,6}
<><><><><><><><><<>（1）画出R 的关系图，并写出R 的关系矩阵；
（2）R 是否为等价关系？若是，写出R 的所有等价类。
解：（1）R 的关系图为
1
2 3 6
5 4
（2）R的关系矩阵
10100 01001 10100 00010 01001????????????????
由关系图可以看出R是等价关系。等价类为：
[1][3][6]{1,3,6},[2]{2,5},[4]{4}
=====
或写为：{{1,3,6},{2,5},{4}}
2. 设{1,3,(1,4,2,2,3,1,3,3),4,1}
R=<>><><><<>是{1,2,3,4}上的二元关系。
（1）画出R的关系图；
（2）写出R的关系矩阵；
（3）讨论R的性质。
解：（1）R的关系图
（2）R的关系矩阵
0011 0100 1000 1000????????????
（3）R非自反、非反自传、对称、非反对称、非传递的
（4）R不是函数，不满足函数单值性的要求。
3．设{1,2,3,4,5,6,7,8,9,10}，R是A上的二元关系，
{∈A ∧10} 说明R具有哪些性质。
解：{<1,9>,<2,8> ,<3,7> ,<4,6> ,<5,5> ,<9,1>,<8,2> ,<7,
3> ,<6,4> }
易知 R既不是自反也不是反自反的
R是对称的
R不是反对称的
R不是传递的。
4
4．判断下图是否为二部图？若是，找出它的互补结点子集。它
5.判断下图G 是否是二部图？若是，找出它的互补结点子集。它是否为哈密顿图？若是，找出一条哈密顿回路。
6.设{1,3,5,9,45}A
=，≤为A 上的整除关系。
（1）,A <≤>（2）,A <≤>是否为格？说明理由；
解：（1）,A <
≤>是偏序集。哈斯图为：
（2）,A <≤>是格。因为偏序集中的任意两个元素均有上、下确界。
四、证明题
1．用一阶逻辑的推理理论证明：
前提：(()())x F x G x ?→?，(()())x F x H x ?∨， ()x H x ?? 结论： ()x G x ?? 证明：（1）(()())x F x H x ?∨ 前提引入 （2）()()F x H x ∨ （1）?- （3）()x H x ?? 前提引入 （4）()H x ? （3）?-
f
c
1
v 2
v 3
v
（5）()F x （2）（4）析取三段论 ………（4分）
（6）(()())x F x G x ?→? 前提引入 （7）()()F x G x →? （6）?-
（8）()G x ? （5）（7）假言推理
（9）()G x ?? （8）?+ ………（3分）
2．设A 是非空集合,F 是所有从A 到A 的双射函数的集合, o 是函数的复合运算。
证明：,F <>o 是群。
证明：由于集合A 是非空的，A I F ∈，,因此F 非空 。
(1) ,f g F ∈,因为f 和g 都是A 到A 的双射函数，故f g o 也是A 到
A 的双射函数，从而集合F 关于运算 是封闭的。
(2) ,,f g h F ∈,由函数复合运算的结合律有()()f g h f g h o o o o =，
故运算o 是可结合的。
(3) A 上的恒等函数A I 也是A 到A 的双射函数即A
I F ∈,且
f F ∈有A A I f f I =o o , 故A I 是,F <>o 中的幺元。
(4) f F ∈,因为f 是双射函数，故其逆函数是存在的，也是A
到A 的双射函数，且有11A
f f f f I o o --==,因此1
f -是f 的逆元
由此上知,F <>o 是群
3．设代数系统6,V Z =<⊕>，6{0,1,2,3,4,5}Z =，⊕为模6加法。证明：6Z 关于⊕运算构成群。 证明：集合6
Z 显然非空。
(1) 6
,a b Z ?∈,6
a b Z ⊕∈,从而集合6
Z ⊕关于运算是封闭的。
(2) 6
,,a b c Z ?∈,有()()a b c a b c ⊕⊕=⊕⊕，故运算⊕ 是可结合的。
(3) 6a Z ?∈, 0a a ⊕=,故0是6,Z <⊕>中的幺元。 (4) 6
a Z ?∈,因为(6)0a a ⊕-=,因此6a -是a 的逆元 由此上知6,Z <⊕>是群
4．设A 是集合，P(A)是A 的幂集合，⊕是对称差运算， 证明 ⊕>构成群。 提示：参考2、3证明题完成。 5．设{,|,A x y x y =<>为正整数}，在A 上定义二元关系R 如下： ,,x y R u v <><>当且仅当x y u v -=-。 证明：R 是一个等价关系。 证明： 任取,x y <> ,,,x y A x y x y x y R x y <>∈?-=-?<><> 所以R 自反的。 任取,,,x y u v <><> ,,,,x y R u v x y u v u v x y u v R x y <><>?-=-?-=-?<><> 所以R 是对称的。 任取,,,,,x y u v s t <><><> ,,,,x y R u v u v R s t x y u v u v s t <><>∧<><>?-=-∧-=- ,,x y s t x y R s t ?-=-?<><> 所以R 是传递的。 因此，R 是等价关系。 6.设R 是A 上的关系，如果R 满足以下两条件： （1）对于任意的∈， 都有， （2）若, , 则有， 证明：R 是等价关系 证明： 任取,,a b c R ∈ （1）由已知条件（1）得 ,a a R <>∈,,所以R 是自反的。 （2）由已知条件（1）、（2）得 ,,,a b R a a R b a R <>∈∧<>∈?<>∈ 所以R 是对称的。 （3）由已知条件（1）、（2）得 ,,,,a b R b c R b a R c b R <>∈∧<>∈?<>∈∧<>∈ ,,,b c R b a R c a R <>∈∧<>∈?<>∈ 所以R 是传递的。 五、应用题（仅给出第7题的参考答案,未给出参考答案的自己完成） 1. 构造下列推理的证明。 如果今天是星期一，则要进行英语或离散数学考试。如果英语老师有会，则不考英语。今天是星期一，英语老师有会，所以进行离散数学考试。 2. 构造下列推理的证明。 小王是理科学生，则他的数学成绩很好。如果小王不是文科学生，则他一定是理科学生。小王的数学成绩不好, 所以小王是文科学生。 3．如果甲是冠军，则乙或丙将得亚军；如果乙得亚军，则甲不能得冠军；如果丁得亚军，丙不能得亚军；事实是甲已得冠军。因此丁不能得亚军。 参照作业：P54 17,18 4.用一阶逻辑推理证明 每个喜欢步行的人都不喜欢骑自行车，每个人或喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以，有的人不喜欢步行（个体域为人类集合） 解: 令(): H x x喜欢乘 F x x喜欢步行, (): G x x喜欢骑自行车, (): 汽车 前提：(()()) x H x ?? x F x G x ?∨，() x F x H x ?→?，(()()) 结论：() ?? x G x 证明：（1）(()()) ?∨前提引入 x F x H x （2）()() ∨（1）?- F x H x （3）() x H x ??前提引入 （4）() ?（3）?- H x （5）() F x（2）（4）析取三段论 （6）(()()) ?→?前提引入 x F x G x （7）()() F x G x →?（6）?- （8）() ?（5）（7）假言推理 G x （9）() ??（8）?+ G x 5．今有于,,,,, a b c d e f7个人，已知下列事实：a会讲英语；b会讲英语和汉语； c会讲英语、意大利语和俄语；d会讲日语和汉语；e会讲德国和意大利语；f会讲法语、日语和俄语；g 离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 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的补元( ). 5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ). 离散数学期末试题及答 案 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的补元( ). 《离散数学》期末考试题(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 是欧拉图. 二、单选题(每小题3分，共15分) 1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数，则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”. 1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( ) 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={ 《离散数学》试卷（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人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 离散数学期末测验试题（有几套带答案1) ————————————————————————————————作者: ————————————————————————————————日期: ? 离散数学试题(A卷及答案） 一、证明题（10分） １)(?P∧(?Q∧Ｒ)）∨(Q∧R）∨(P∧R）?Ｒ 证明：左端?(?P∧?Q∧R)∨（(Q∨Ｐ)∧R)?（(?P∧?Q)∧R))∨((Ｑ∨Ｐ)∧R） ?(?(P∨Q）∧R)∨((Q∨P)∧Ｒ)?(?(P∨Q)∨(Ｑ∨Ｐ))∧R ?(?(P∨Q)∨(Ｐ∨Ｑ))∧R?T∧R(置换）?R 2）?x(Ａ（ｘ)→B(x)）??xＡ(x）→?xB(x) 证明:?x(A(x)→Ｂ(x））??x（?A（x)∨B(x))??x?A(x)∨?xB(x)???xA（x)∨?xB(x)??xA(x)→?xＢ(ｘ） 二、求命题公式(P∨(Q∧Ｒ))→(Ｐ∧Q∧R）的主析取范式和主合取范式(１０分) 证明:(P∨（Ｑ∧Ｒ））→(P∧Q∧R)??(P∨(Ｑ∧Ｒ）)∨（P∧Q∧R)) ?（?P∧（?Q∨?R)）∨(Ｐ∧Q∧Ｒ） ?(?P∧?Ｑ)∨(?P∧?R)）∨(Ｐ∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Ｑ∧?R）∨(?Ｐ∧Q∧?R)）∨(?P∧?Q∧?R)）∨(Ｐ∧Ｑ∧R) ?m0∨ｍ1∨m2∨ｍ７ ?Ｍ3∨M4∨M5∨M6 三、推理证明题(10分) 1）Ｃ∨D， (C∨D)→?E, ?Ｅ→(A∧?B), (A∧?B)→(R ∨S)?R∨S 证明:(1) (C∨D）→?E (２) ?E→（A∧?Ｂ) ?? (3）（C∨D）→（A∧?Ｂ) （４) （Ａ∧?B)→(R∨Ｓ) ?? (5) （C∨D）→（R∨Ｓ) ? (6) C∨Ｄ?? (7) R∨S 2) ?x(P(ｘ)→Q(ｙ）∧R(x)），?xP(x)?Q(y）∧?x（P(x)∧R(x)) 证明（1)?xP(ｘ) (2）P(a) （3)?ｘ(P(x)→Q(y）∧R(x)) (4）P（a)→Q(y)∧R(a) (５)Q(y)∧Ｒ(a) (6)Q(y) （７)R(a） (8)P(a) (9)P(ａ)∧R(a) （10)?x(Ｐ(x)∧R(ｘ)) (11)Q（ｙ)∧?x(P（x）∧R(x)） 五、已知Ａ、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) （１5分) 证明∵x∈A-（Ｂ∪C)?x∈A∧x?（Ｂ∪C)?x∈A∧(x?Ｂ∧ｘ?C）?(x∈A∧x?B)∧（x∈A∧x?C）?x∈（Ａ-B)∧ｘ∈(A－C）?x∈(A－B）∩（A-Ｃ)∴A-(B∪Ｃ）=（A-B)∩(A-C） 六、已知R、S是N上的关系，其定义如下：Ｒ=｛＜x，ｙ>| x，y∈N∧y=x2｝，Ｓ={ 离散数学试题(B卷答案1） 一、证明题（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 P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4)， I (6) C∨D P (7) R∨S T(5)，I 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P 一．判断题（共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?{ 精品文档院术师范学广东技模拟试题 科目：离散数学 120 分钟考试时间: 考试形式：闭卷 姓名：学号：系别、班级： 2分，共10分）一．填空题（每小题__________。?x?y?P(x)∨Q(y) 1. 谓词公式的前束范式是 __)xxQ(?xP(x)????????____，，2. 设全集A?_{4,5}B =__则A∩ {2}__,,?E?1,2,3,4,55,A?21,,32,B_____ __ {1,3,4,5}??BA????b,c}} __________，则3. 设__ ， b?,c,b,a,A?Ba???B(A)?)(_____Φ_______。???)(AB()?4. 在代数系统（N，+）中，其单位元是0，仅有_1___ 有逆元。 ne条边，则G有___e+2-n____个面。5．如果连通平面图G有个顶点，二．选择题（每小题2分，共10分） P?(Q?R)等价的公式是（1. 与命题公式） （A）（B）（C）（D）R?P?Q)()?R)R?(QPP?(Q?R?Q)(P??????b?b,?a,aA??a,b,cR?,不具备关系( 2. 设集合上的二元关系,A)性质 （A）(A)传递性(B)反对称性(C)对称性(D)自反性 G??V,E?中,结点总度数与边数的关系是3. 在图( ) ??E?Edeg(v)deg(v)?2deg(v)?Evdeg()?2E(A)(C)(B) (D) iiiiVv?Vv?4. 设D是有n个结点的有向完全图,则图D的边数为( ) n(n?1)n(n?1)n(n?1)/2n(n?1)/2(A)(B)(D)(C) 5. 无向图G是欧拉图,当且仅当( ) (A)G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数 精品文档． 精品文档 (C)G连通且所有结点的度数都是偶数(D) G连通且G的所有结点度数都是奇数。 三．计算题（共43分） p?q?r的主合取范式与主析取范式。（1. 求命题公式6分） 解：主合取方式：p∧q∨r?(p∨q∨r)∧(p∨?q∨r)∧(?p∨q∨r)= ∏0.2.4 主析取范式：p∧q∨r?(p∧q∧r) ∨(p∧q∧?r)∨(?p∧q∧r) ∨(?p∧?q∧r) ∨(p∧?q∧r)=∑1.3.5.6.7 1000????0111?????Md,A?a,b,c,的上的二元关集2. 设合系R关系矩阵为求 ??R0000????1000??)tR(),(RsRr()(),(),(rRsRtR),的关系图。R的关系矩阵，并画出分）10（， 《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 北京工业大学经管学院期末试卷 《离散数学》（A） 学号姓名：成绩 一、单项选择题（每题2分，共18分） 1．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不．滑”可符号化为（D）A．P→Q B．P∨Q C．P∧Q D．P∧Q p→q，蕴涵式，表示假设、条件、“如果，就”。 “→”与此题无关 2. 关于命题变元P和Q的极大项M1表示( C )。书P1520，此题换作p、q更容易理解 A.┐P∧Q B.┐P∨Q p∨┐q 01 1 M1 ∨┐Q∧┐Q 3.设R（x）：x是实数；S（）：x小于y。用谓词表达下述命题：不存在最小的实数。其中错误的表达式是：（D） 4.在论域{}中与公式（x?）A（x）等价的不含存在量词的公式是（B） A.)b( )a( A∨ A A )a( A∧ B. )b( C. )b( )b( A→ A A )a( A→ D. )a( 5．下列命题公式为重言式的是（C） A．Q→（P∧Q）B．P→（P∧Q） C．（P∧Q）→P D．（P∨Q）→Q 牢记→真假条件，作为选择题可直接代入0、1，使选项出现1→0，排除。熟练的可直接看出C不存在1→0的情况 6. 设｛1，2，3｝，｛｝，下列二元关系R为A到B的函数的是( A ) A. ｛<1>,<2>,<3>｝ B. ｛<1>,<2>｝ C. ｛<1>,<1>,<2>,<3>｝ D. ｛<1>,<2>,<3>,<1>｝ 7.偏序关系具有性质（D）背 A.自反、对称、传递 B.自反、反对称 C.反自反、对称、传递 D.自反、反对称、传递 8.设R 为实数集合，映射:,R R σ→2 ()21,x x x σ=-+-则σ 是( D ). (A) 单射而非满射 (B) 满射而非单射 (C) 双射 (D) 既不是单射也不是满射. 书P96.设函数f ：A→B （1）若，则f 是满射的【即值域为B 的全集，在本题中为R ，该二次函数有最高点，不满足】 （2）若对于任何的x 12∈A , x 1≠x 2,都有f(x 1)≠f(x 2)，则称f 是单射的【即真正一一对应，甚至不存在一个y 对应多个x 。显然，本题为二次函数，不满足】 （3）若f 既是满射的，又是单射的，则称f 是双射的【本题中两个都不满足，既不是单射也不是满射】 二、填空题（每空2分，共22分） １.设Q 为有理数集，笛卡尔集×Q ，*是S 上的二元运算，? 离散数学-期末考试卷-A卷 东莞理工学院城市学院（本科）试卷（A卷） 2013-2014学年第一学期 开课单位：计算机与信息科学系，考试形式：闭卷，允许带入场 科目：离散数学，班级：软工本2012-1、2、3 姓名：学号： 题序一二三四总分 得分 A评 卷人 一、单项选择题（每小题2分，共20分） 在每小题列出的四个备选项中只有一个是符合题目要求的，错选、多选或未选均无分。 1. 下述不是命题的是( ) A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 2. 命题公式P→(P∨Q∨R)是( ) A. 永假的 B. 永真的 C. 可满足的 D. 析取范式 3. 命题公式﹁B→﹁A等价于( ) A. ﹁A∨﹁ B B. ﹁(A∨B) C. ﹁A∧﹁ B D. A→B 4．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）A．?P∧Q B．P∧?Q C．P→?Q D．P∨?Q 5．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（）A．?x(A(x))∧B(x) B．??x( A(x)→?B(x) ) C．??x( A(x)∧B(X)) D．??x( A(x)∧?B(x) ) 6. 设有A={a,b,c}上的关系R={ 7. 设A={1,2,3,4,5,6},B={a,b,c,d,e}，以下哪一个关系是从A到B的满射函数( ) A. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>} B. f={<1,e>,<2,d>,<3,c>,<4,b>,<5,a>,<6,e>} C. f={<1,a>,<2,b>,<3,c>,<4,a>,<5,b>,<6,c>} D. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>,<1,b>} 8．设简单图G所有结点的度数之和为10，则G一定有（） A．3条边B．4条边C．5条边 D．6条边 9．下列不．一定是树的是（） A．每对结点之间都有通路的图 B．有n个结点，n-1条边的连通图 C．无回路的连通图D．连通但删去一条边则不连通的图 10．下列各图中既是欧拉图，又是哈密顿图的是（） 《离散数学》复习题 一、单项选择题（每小题2分，共20分） 1、下列命题中是命题的是（ ） A 、 7>+y x B 、雪是黑色的 C 、严禁吸烟 D 、我正在说谎 2下列命题联结词集合中,哪个不是极小全功能集( )。 A 、{,}刭 B 、{,}刳 C 、{}- D 、{,}佼 3、下列公式中哪个不是简单析取式（ ）。 A 、p B 、p q ∨ C 、()p q ?∨ D 、p q ?∨? 4、设个体域{,}A c d =，公式()()x P x x S x ?∧?在A 中消去量词后应为（ ） A ()()P x S x ∧ B (()())(()( P c P d S c S d ∧∧∨ C ()()P c S d ∧ D ()() () (P c P d S c S d ∧ ∧∨ 5、下列是命题公式p ∧(q ∨┓r)的成真指派的是( ) A.110，111，100 B.110，101，011 C.所有指派 D.无 6、下列命题中（ ）是正确的。 A. 若图G 有n 个顶点，则G 的各顶点的度和为2n; B. 无向树中任意两点之间均相互可达； C. 若有向图G 是弱连通的，则它必定也是单向连通； D. 若无向带权图G 是连通的，则其最小生成树存在且唯一。 7、正整数集合Z +的以下四个划分中，划分块最多的是（ ） A ．1π={{x }︱x ∈Z + } B ．2π= {Z + } C. 3π={12,S S },1S 为素数集，21S Z S + =- D ．3π={12,S S ,3S },i S 为Z +中元素除以3的余数 8、给定下列各图： ⑴G 1= 广东技术师范学院 模拟试题 科 目：离散数学 考试形式：闭卷 考试时间: 120 分钟 系别、班级： 姓名： 学号： 一．填空题（每小题2分，共10分） 1. 谓词公式)()(x xQ x xP ?→?的前束范式是__ ?x ?y?P(x)∨Q(y) __________。 2. 设全集{}{}{},5,2,3,2,1,5,4,3,2,1===B A E 则A ∩B =__{2}__，=A _{4,5}____， =B A __ {1,3,4,5} _____ 3. 设{}{}b a B c b a A ,,,,==，则=-)()(B A ρρ__ {{c},{a,c},{b,c},{a,b,c}} __________， =-)()(A B ρρ_____Φ_______。 4. 在代数系统（N ，+）中，其单位元是0，仅有 _1___ 有逆元。 5．如果连通平面图G 有n 个顶点，e 条边，则G 有___e+2-n ____个面。 二．选择题（每小题2分，共10分） 1. 与命题公式)(R Q P →→等价的公式是（ ） （A ）R Q P →∨)( （B ）R Q P →∧)( （C ）)(R Q P ∧→ （D ）)(R Q P ∨→ 2. 设集合{}c b a A ,,=,A 上的二元关系{}><><=b b a a R ,,,不具备关系( )性质 （A ） (A)传递性 (B)反对称性 (C)对称性 (D)自反性 3. 在图>= 安徽大学2006-2007学年第1学期 《离散数学》期末考试试卷（A卷） （时间120分钟） 开课院（系、部）姓名学号. 一、选择题（每小题2分，共20分）1．下列语句中，哪个是真命题（）A、 4 2= + x； B、我们要努力学习； C、如果ab为奇数，那么a是奇数，或b是偶数； D、如果时间流逝不止，你就可以长生不老。 2．下列命题公式中，永真式的是（） A、P Q P→ →) (； B、P P Q∧ → ?) (； C、Q P P? ? ∧) (； D、) (Q P P∨ →。3．在谓词逻辑中，令) (x F表示x是火车；) (y G表示y是汽车；) , (y x L表示x比y快。 命题“并不是所有的火车比所有的汽车快”的符号表示中哪些是正确的（） I.)),()()((y x L y G x F y x →∧??? II.)),()()((y x L y G x F y x ?∧∧?? III. )),()()((y x L y G x F y x ?→∧?? A 、仅I ； B 、仅III ； C 、I 和II ； D 、都不对。 4．下列结论正确的是：（ ） A 、若C A B A =，则 C B =； B 、若B A B A ?，则B A =； C 、若C A B A =，则C B =； D 、若B A ?且D C ?，则D B C A ?。 5．设φ=1A ，}{2φ=A ，})({3φρ=A ，)(4φρ=A ，以下命题为假的是（ ） A 、42A A ∈； B 、31A A ?； C 、24A A ?； D 、34A A ∈。 6．设R 是集合},,,{d c b a A =上的二元关系， },,,,,,,,,,,{><><><><><><=b d d b a c c a a d d a R 。下列哪些命题为真（ ） I.R R ?是对称的 II. R R ?是自反的 III. R R ?不是传递的 A 、仅I ； B 、仅II ； C 、I 和II ； D 、全真。 一、填空 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 (B ⊕C)-A 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 )()(R S P R S P ∨?∨?∧∨∨? 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 1 。 6．设A={1，2，3，4}，A 上关系图如下，则 R^2= {(1,1),(1,3),(2,2),(2,4)} 。 //备注： ?????? ? ??=0000100001010010 R ?????? ? ? ?=00000000101001012 R 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图如下，则R= {(a,b),(a,c), (a,d), (b,d), (c,d)} U {(a,a),(b,b)(c,c)(d,d)} 。 //备注：偏序满足自反性，反对称性，传递性 8．图的补图为 。 //补图:给定一个图G ,又G 中所有结点和所有能使G 成为完全图的添加边组成的图,成为补图. 自补图:一个图如果同构于它的补图,则是自补图 9．设A={a ，b ，c ，d} ，A 上二元运算如下： * a b c d a b c d a b c d b c d a c d a b d a b c 那么代数系统的幺元是 a ，有逆元的元素为 a,b,c,d ，它们的逆元分别为 a,b,c,d 。 //备注：二元运算为x*y=max{x,y}，x,y ∈A 。 10．下图所示的偏序集中，是格的为 c 。 //（注：什么是格？即任意两个元素有最小上界 和最大 下界的偏序） 二、选择题 1、下列是真命题的有（ C 、D ） A ． }}{{}{a a ?； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ．}}{{}{Φ∈Φ。 2、下列集合中相等的有（ B 、C ） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 A C离散数学期末试题
离散数学期末试题及答案
离散数学期末试题及答案完整版
【浙江工商大学】《离散数学》期末考试题(B)
离散数学期末考试试题及答案
离散数学期末试卷A卷及答案
离散数学期末测验试题(有几套带答案1)
离散数学期末考试试题及答案
离散数学期末试卷及答案
最新离散数学期末考试试题配答案
《离散数学》期末考试试题
离散数学期末试卷
离散数学-期末考试卷-A卷
离散数学期末考试题
离散数学期末考试试题(配答案)
大学《离散数学》期末考试试卷及答案-(1)
离散数学期末考试题(附答案和含解析)
相关文档
- 离散数学期末考试题
- 离散数学期末考试题(有几套带答案)
- 【浙江工商大学】《离散数学》期末考试题(B)
- 离散数学期末考试试题(配答案)
- 离散数学期末考试试题(配答案)
- 离散数学期末考试题及答案
- 最新离散数学期末考试试题(配答案)
- 离散数学期末测试卷I及答案
- 《离散数学》期末考试试题
- 离散数学期末考试试题与答案
- 离散数学》期末考试题(A)
- 《离散数学》期末试题及答案
- 离散数学期末试题及答案完整版
- 离散数学期末考试题(附答案和含解析3)
- 离散数学期末考试题
- 离散数学期末试卷(3套附答案)
- 离散数学期末考试试题(有几套带答案)
- 离散数学期末试卷A卷汇总
- 离散数学期末考试试题及答案
- 离散数学期末考试试题及答案