离散数学期末练习题 (带答案)
离散数学复习注意事项：
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 Q x
??→ B. ()(()
x P x
C. ()(()())
Q x
??∧())
x P x Q x
??→ D. ()(()
x P x
5.设()
L x y：x大于等于y；命题“所有整数
f x:x的绝对值，(,)
P x:x是整数，()
的绝对值大于等于0”可符号化为（）。
A. (()((),0))
?→
x P x L f x
?∧B. (()((),0))
x P x L f x
C. ()((),0)
?→
xP x L f x
?∧ D. ()((),0)
xP x L f x
6.设()
F x:x是人，()
G x:x犯错误，命题“没有不犯错误的人”符号化为（）。
A．(()())
??→?
x F x G x
?∧B．(()())
x F x G x
C．(()())
??∧?
x F x G x
??∧D．(()())
x F x G x
7.下列命题公式不是永真式的是（）。
A. ()
p q p
→→
→→ B. ()
p q p
C. ()
→∨
p q p
p q p
?∨→ D. ()
8．设()
R x:x为有理数；()
Q x:x为实数。命题“任何有理数都是实数”的符号化为（）
A ．()(()())x R x Q x ?∧
B ．()(()())?∧x R x Q x
C ．()(()())?→x R x Q x
D ．(()())x R x Q x ?→ 9.设个体域{,}D a b =，与公式()xA x ?等价的命题公式是( )
A ．()()A a A b ∧
B ．()()A a A b →
C ．()()A a A b ∨
D ．()()A b A a →
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. 设个体域{,}D a b =，与公式()xA x ?等价的命题公式是( ) A ．()()A a A b ∧ B ．()()A a A b → C ．()()A a A b ∨ D ．()()A b A a → 12.设X ={,{},{,}}a a ??，则下列陈述正确的是（ ）。
A.a X ∈
B.{,}a X ?? C .{{,}}a X ??
D.{}X ?∈
13.有向图D 是连通图，当且仅当（ ）。 A. 图D 中至少有一条通路
B. 图D 中有通过每个顶点至少一次的通路
C. 图D 的连通分支数为一
D . 图D 中有通过每个顶点至少一次的回路 14.设A={a,b,c}，则下列是集合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 ．M-N 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 ．{b,c }是点割集 C ．{b,d }是点割集 D ．{c }是割点
d
28.格L 是分配格的充要条件是L 不含与下面哪一个选项同构的子格（ ）。 A ．链
B ．钻石格
C ．五角格
D . 五角格与钻石格
29.下列图是欧拉图的是（ D ）。
30.给定一个有n 个结点的无向树，下列陈述不正确的是（ ）。 A ．所有结点的度数≥2
B ．无回路但若增加一条新边就会变成回路
C ．连通且1e 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. 设{,{},{,{}}}A a a a a =则其幂集()P A 的元素总个数为（ ）。 A. 3 B. 4 C . 8
D. 16
34. 在实数集合R 上，下列定义的运算中不可结合的是（ ）。 A. 2a 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个结点，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.二部图
K是（）。
3,3
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．设集合A={a,b, c}上的关系如下，具有传递性的是（ ）。 A ． R={
D ． R={
参考答案：（若有问题，可以到1#402或打电话问）
一、选择题
AAAAB DACAA CCDBD BCDBC ABBDC CBDDA ACCDD BBBDB CCCBB ADCCD
二、填空题
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 ??→∧?约束变元为 x,y ，自由变元
为 x,z 。
5．公式(()())(,)x P x yR y Q x z ?∨?→约束变元为__x,y _，自由变元为_x,z _ 。 6．设{,,{,}}A a b a b =，{,}B a b =，则B A -=?，A B ⊕= {{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 ⊕= {{a,b},c} 。
10.一棵无向树的顶点数n 与边数m 的关系是 m=n-1 。6阶无向连通图至多有 6 棵不同构的生成树。
11．设()1f x x =-，2()g x x =，则复合函数()()f g x =2(1)x -,()()g f x =21x -。 12. ,n Z <⊕>是一个群，其中{0,1,2,
,1}n Z n =-，()mod x y x y n ⊕=+，则当n =6
时，在6,Z <⊕>中，2的阶为___3___, 3的阶为_ 2 。
13．设是格，其中A={1, 3,4，6，8，12，24}，≤为整除关系，则1的补元是___24 __，3的补元是_8_。
14．设A=｛<1，3>，<3，5>，<4，4>｝，B=｛<1,3>,<4,5>,<5,5>｝,那么dom()
A B ={1,3,4,5} ran ()A B = {3,5} 。 15. 设A ={l,2,3,4},A 上的二元关系R ={<1,2>,<2,3>,<3,2>}，S ={
则R S = {<1,3>,<3,3>} ,1()R S -= {<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 = {<1,1>,<3,5>} ， 11S R --= {<1,1>,<5,3>} 。 17． 设A ={2, 4, 6}，A 上的二元运算*定义为：a *b =max {a ,b }，则在独异点
中，单位元是 2 ，零元是 6 。
18．一棵无向树的顶点数n 与边数m 关系是 m= n-1 。设G 是具有8个顶点的
树，则G 中增加___21 _条边才能把G 变成完全图。
19．设复合函数g f 是从A 到C 的函数，如果g f 是满射，那么__ g ___必是满
射，如果g f 是单射，那么_f _必是单射。
20．设是格，其中A ={1, 3, 5, 9, 45}，≤为整除关系，则1的补元是___45___，3的补元是_ 5 _。
21．给出A ={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 ，传递闭包()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→R,f(x)=x+3,g ∶R→R,g(x)=2x+1,则复合函数(f g)()x = 2x+4 ,
(g f )(x)= 2x+7 。
29.给定集合A={1,2,3,4,5}，在集合A 上定义两种关系：R={<1,2>,<3,4>,<2,2>},
S={<4,2>,<2,5>,<3,1>,<1,3>，则R S = {<1,5>,<3,2>,<2,5>} 。 30．设A={0，1，2，3，6}，{,|,(mod3)}R x y x y A x y x y =<>∈∧≠∧≡则
domR= {0， 3，6}_ ，ranR=_{0， 3，6} ，
31． 设6,Z <⊕>为模6加群，其中6{0,1,2,3,4,5}Z =，则2-3= 0 ，4-2= 4 。 32．一个结点为n 的无向完全图，其边的数目为n(n-1)/2 ，顶点的度为 n-1 。 33. 已知n 阶无向简单图G 有m 条边，则G 的补图G 中有 m- n(n-1)/2 条边。 参考答案：
1．_10_，00，01，11 2. 00 10 11， 01_ 3. _00 01 11, 10 4. _x ,y ，x ,z __ 5. _x ,y ，x ,z __
6.?,, {{a,b}}
7.{1,2,2,1}<><>，{1,2,2,1,1,1,2,2}<><><><> 8. 结合律 ， 单位元 9,, {{a,b}，c} 10.n-1, 6 11. 2(1)x -,,21x -
12. 3 , 2 13. _24__,_8__ 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. m= n-1, _21 19. _g , _f_ 20. 45 , _5_
21. {1,1,2,2}<><>,{{1},{2}} 22. A R
I , 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(n-1)/2, n-1 33. m- n(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*4+x=2*（2+1+3+x-1） 得x=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 ，g f ；
（2）,,f g h 哪些函数有反函数？如果有，求出这些反函数。 解：（1）22()(())(4)(4)2814g f x f g x f x x x x ==+=+-=++ 22()(())(2)2f g x g f x g x x ==-=+ （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)=R ∪I A ={
s(R)=R ∪R -1={
9.设{1,2,3,4,6,9,24,54}A =，≤为整除关系。 （1）画出偏序集
（3）求子集B=｛3, 6, 9｝的上确界与下确界。 解：（1）哈斯图
（2）A 中的极大元为 24，54；极小元为1；最大元：无；最小元：1 （3）求子集B=｛3, 6, 9｝的上确界为54，下确界为3。 10.设有向图D 如图所示，用邻接矩阵完成以下计算。 （1）1v 到4v 长度小于或等于4的通路数； （2）1v 到自身长度小于或等于4的回路数； （3）求出D 的可达矩阵，并说明D 的连通性。
有向图的邻接矩阵为
1210001000010010A ?????
?=??
????，212
31000100100001A ??
????=??
?
???
3
1243001000010
010A ?????
?=??
????，41
264000100100
001A ??????=??
?
?
??
（1）v 1到v 4长度小于或等于4的通路数为
4
()14
1
01348i i a
==+++=∑
1
4
24
9 54
（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)=R ∪I A
s(R)=R ∪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 的关系图为
（2）R 的关系矩阵 1010001
001
1
0100
00010
1
01
?????
??????????? 由关系图可以看出R 是等价关系。等价类为：
[1][3][6]{1,3,6},[2]{2,5},[4]{4}=====
或写为：A/R={{1,3,6},{2,5},{4}}
2. 设{1,3,(1,4,2,2,3,1,3,3),4,1}R =<>><><><<>是A ={1,2,3,4}上的二元关系。
（1）画出R 的关系图； （2）写出R 的关系矩阵； （3）讨论R 的性质。 解：（1）R 的关系图
（2）R 的关系矩阵 0
0110
10010001
00
?????
???????
（3）R 非自反、非反自传、对称、非反对称 、非传递的 （4）R 不是函数，不满足函数单值性的要求。 3．设A={1,2,3,4,5,6,7,8,9,10}，R 是A 上的二元关系， R={|x,y ∈A ∧x+y=10} 说明R 具有哪些性质。
解：R={<1,9>,<2,8> ,<3,7> ,<4,6> ,<5,5> ,<9,1>,<8,2> ,<7,3> ,<6,4> }
4
1
2
3
6
5
4
易知 R 既不是自反也不是反自反的 R 是对称的
R 不是反对称的 R 不是传递的。
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 ?∨ 前提引入
f
c
1
v 2
v 3
v
（2）()()F x H x ∨ （1）?- （3）()x H x ?? 前提引入 （4）()H x ? （3）?-
（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 的双射函数的集合, 是函数的复合运算。 证明：,F <>是群。
证明：由于集合A 是非空的，A I F ∈，,因此F 非空 。
(1) ,f g F ∈,因为f 和g 都是A 到A 的双射函数，故f g 也是A 到A 的双射函
数，从而集合F 关于运算 是封闭的。
(2) ,,f g h F ∈,由函数复合运算的结合律有()()f g h f g h =，故运算 是可结
合的。
(3) A 上的恒等函数A I 也是A 到A 的双射函数即A I F ∈,且f F ∈有A A I f f I =,
故A I 是,F <>中的幺元。
(4) f F ∈,因为f 是双射函数，故其逆函数是存在的，也是A 到A 的双射函数，
且有11A f f f f I --==,因此1f -是f 的逆元 由此上知,F <>是群
3．设代数系统6,V Z =<⊕>，6{0,1,2,3,4,5}Z =，⊕为模6加法。证明：6Z 关于⊕运算构成群。
证明：集合6Z 显然非空。
(1) 6,a b Z ?∈,6a b Z ⊕∈,从而集合6Z ⊕关于运算是封闭的。 (2) 6,,a b c Z ?∈,有()()a b c a b c ⊕⊕=⊕⊕，故运算⊕ 是可结合的。 (3) 6a Z ?∈, 0a a ⊕=,故0是6,Z <⊕>中的幺元。
(4) 6a Z ?∈,因为(6)0a a ⊕-=,因此6a -是a 的逆元 由此上知6,Z <⊕>是群
4．设A 是集合，P(A)是A 的幂集合，⊕是对称差运算， 证明
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）对于任意的a ∈R ， 都有aRa ， （2）若aRb, aRc, 则有bRc ， 证明：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.用一阶逻辑推理证明
每个喜欢步行的人都不喜欢骑自行车，每个人或喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以，有的人不喜欢步行（个体域为人类集合） 解: 令():F x x 喜欢步行, ():G x x 喜欢骑自行车, ():H x x 喜欢乘汽车 前提：(()())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）?-
（5）()F x （2）（4）析取三段论
（6）(()())x F x G x ?→? 前提引入 （7）()()F x G x →? （6）?-
（8）()G x ? （5）（7）假言推理 （9）()G x ?? （8）?+
5．今有于,,,,,a b c d e f 7个人，已知下列事实： a 会讲英语；
b 会讲英语和汉语；
c 会讲英语、意大利语和俄语；
d 会讲日语和汉语；
e 会讲德国和意大利语；
f 会讲法语、日语和俄语；
g 会讲法语和德语。 试问这七个人应如何排座位，才能使每个人都能和他身边的人交谈？ 解：用结点表示人，用边表
示连接的两个人能讲同一种语言，构造出图G 如下：
g
在G 中存在着一条哈密顿回路如下，根据这条回路安排座位，就能够使每个人都能和他身边的人交谈。
6． 一次学术会议的理事会共有20个人参加，他们之间有的互相认识但有的互相不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人？根据是什么？
7.设有7个城市1v ，2v ，……7v ，任意两个城市之间直接通信线路及通信线路预算造价如带权图所示，试给出一个设计方案，使得各城市间能够通信，而且总造价最低。写出求解过程，并计算出最低总造价。
解：带权图中边表示通信路，边上的数字表示修建该通信线路所需费用，于是求
解此题便成为求权图中的最小生成树问题。 按避圈算法，对图中各边的权值按由小到大的顺序排序，
112233444555=<=<=<==<==
日b g
5
4
v 2
v 4
5
v
取12(,)v v T ∈,45(,)v v T ∈，34(,)v v T ∈，04(,)v v T ∈
02(,)v v T
∈，
16(,)v v T ∈
则求解最小生成树如下图所示： 图中最小生成树的权为:
12(,)w v v +45(,)w v v +34(,)w v v +04(,)w v v +02(,)w v v +16(,)w v v =1+1+2+2+3+5=14
离散数学期末试题
离散数学考试试题（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 的面数为( ).
(完整word版)离散数学期末练习题带答案
离散数学复习注意事项： 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 Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（）
离散数学习题三 含答案
离散数学习题三 11、填充下面推理证明中没有写出的推理规则。 前提：p s r r q q ,,,p →∨?∨? 结论：s 证明：① p 前提引入 ②q ∨?p 前提引入 ③ q （①②析取三段论） ④r q ∨? 前提引入 ⑤ r （③④析取三段论） ⑥s r → 前提引入 ⑦ s （⑤⑥假言推理） 12、填充下面推理证明中没有写出的推理规则。 前提：s)(r q r),(q p →→→→ 结论：s q)(p →∧ 证明：①q)(p ∧ （附加前提） ② p （①化简规则） ③ q （①化简规则） ④r)(q p →→ 前提引入 ⑤r q → （②④假言推理） ⑥ r （③⑤假言推理） ⑦s)(r q →→ 前提引入 ⑧s)(r → （③⑦假言推理） ⑨ s （⑥⑧假言推理） 13、前提：s r ,q p q,q)p (→∨∧→? 结论1：r 结论2：s 结论3：s ∨r （1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。 （2）证明从此前提出发，推任何结论的推理都是正确的。 证明：（1）①r s))r (q)(p q)q)p (((→→∨∨∨∧→? 1r s))r (q)p (q)q)p ((?∨?∧∨?∧?∨?∨∨??
②s ∨ → ∨ → ? ((→ ∨ ∧ s)) p( q) r( q) q) (p ∧ ? ? ∨ ∨ ∧ ? ? ? ∨ ∨ ? q) r( q) ∨ s 1 p s)) p ( q) ((? ③s) ∨ ∨ → ∨ ?r → → ∧ (p q) s)) ((∨ ( r( q) q) p( ? ∧ ∨ ∧ ? ? ? ?r ∨ ∨ ? ∨ ∨ r( q) ∨ s 1 p s)) ((? p q) ( q) 即结论1，结论2，结论3的推理都是正确的。 （2）s) ∨ ∧ ∧ ∧ → (→ ? r( p( (p q) q) q) ∧ ? ∨ ? ∧ ? ∨ ∧ ∧ ∧ ? ? ? ∨ ? ∨ ∧ ∧ (∨ (p q) p( q) ( s) r s) q r p ( q) q) ( q) (p ∨ ? ∧ 0? ? ∨ ∧ s) (p r ( q) 即推任何结论的推理都是正确的。 14、在自然推理系统P中构造下面推理的证明： （1）前提：q → p， → (q r) p, r→ 结论：s 证明：①r) →前提引入 p→ (q ②p 前提引入 ③r) (q→①②假言推理 ④q 前提引入 ⑤r③④假言推理 r→⑤附加律 ⑥s 15、在自然推理系统P中用附加前提法证明下面的推理： 前提：q → ， →s p→ (q p, r) s→ 结论：r 证明： ①s 附加前提引入 ②p s前提引入 → ③p①②假言推理 ④r) →前提引入 p→ (q ⑤r q→③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 即根据附加前提证明法，推理正确。
离散数学期末试题及答案完整版
离散数学期末试题及答 案 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、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统
二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
中国石油大学大学《离散数学》期末复习题及答案
《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群
16、设A、B为集合，如果集合A的元素都是集合B的元素，则称A是B 的。 17、集合上的三种特殊元是、 及。 18、设A={a, b}，则ρ(A) 的四个元素分别 是：，，，。 19、代数系统是指由及其上的或 组成的系统。 20、设
离散数学期末试卷A卷及答案
《离散数学》试卷（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. 写出命题公式 ﹁（P →（P ∨ Q)）的真值表。 答案： 2.证明 答案: 3. 证明以下蕴涵关系成立： 答案： ４. 写出下列式子的主析取范式: 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P)(Q P)P (Q)(Q Q)P (P)Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?
5． 构造下列推理的论证:p ∨q, ｐ→?r ， s →t, ?s →ｒ， ?t ? ｑ 答案: ①s →ｔ 前提 ②t 前提 ③ｓ ①②拒取式I12 ④s →ｒ 前提 ⑤ｒ ③④假言推理I １１ ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论Ｉ10 6. 用反证法证明:ｐ→(?(r ∧s ）→?q ）, p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨
７. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F （ x )：ｘ是鱼 Ｗ（ x )：x 生活在水中 ))((W(x)F(x)x →? 8． 请将下列命题符号化: 存在着不是有理数的实数。 答案: 令 Q ( ｘ ):x 是有理数 R （ x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令Ｍ(ｘ)：x 是人 Ｃ（x):x 是聪明的 则上述命题符号化为 １０. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥ｘ。 答案: 令P(x):x 是正实数 Ｓ（ｘ,y): x+y ≥x １１． 请将下列命题符号化： 每个人都要参加一些课外活动。 答案: 令P(x ）:x 是人 Q （ｙ）: y 是课外活动 S(ｘ,ｙ）:ｘ参加y ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→??
离散数学期末测验试题(有几套带答案1)
离散数学期末测验试题（有几套带答案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｝，Ｓ={
离散数学期末试卷及答案
一．判断题（共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?{
离散数学复习题及答案
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P)Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?
5. 构造下列推理的论证：p ∨q, p →?r, s →t, ?s →r, ?t ? q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →(?(r ∧s)→?q), p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??))(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨
7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥x 。 答案： 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： 令P(x):x 是人 Q(y): y 是课外活动 S(x,y):x 参加y )))()((())()((x C x M x x C x M x →??∧∧?)),()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→??
最新离散数学期末考试试题配答案
精品文档院术师范学广东技模拟试题 科目：离散数学 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（，
《离散数学》练习题和参考答案
《离散数学》练习题和参考答案 一、选择或填空（数理逻辑部分） 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))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) 北京是中华人民共和国的首都。 (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） P Q→ ?（2）Q P? →（3）Q P? ?（4）Q P→ ? 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∧?Q)化简为（），公式 Q→(P∨(P∧Q))可化简为（）。答：?P ，Q→P 14、谓词公式?x(P(x)∨?yR(y))→Q(x)中量词?x的辖域是（）。答：P(x)∨?yR(y) 15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。
离散数学期末考试试题及答案
离散数学试题(Ｂ卷答案１） 一、证明题(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={
《离散数学》试习题及答案
欢迎共阅 一、填空题 1设集合A,B ，其中A ＝{1,2,3},B={1,2},则A-B ＝____________________; ?(A)-?(B)＝__________________________. 2.设有限集合A,|A|=n,则|?(A×A)|=__________________________. 3.设集合A={a ,b },B={1,2},则从A 到B 的所有映射是_______________________________________,其中双射的是__________________________. 4.6设A 、7.设R 8.9.设集合 R 1?R 2 R 1210.11设A ∩13.14.设一阶逻辑公式G=?xP(x)??xQ(x)，则G 的前束范式是_______________________________. 16.设谓词的定义域为{a ,b },将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________. 17.设集合A ＝{1,2,3,4}，A 上的二元关系R ＝{(1,1),(1,2),(2,3)},S ＝{(1,3),(2,3),(3,2)}。则R ?S ＝_____________________________________________________, R 2＝______________________________________________________. 二、选择题
离散数学图论部分经典试题及答案
离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝
图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( ) ． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f