测试题
——离散数学
一、选择题
1、G是一棵根树，则（）。
A、G一定是连通的
B、G一定是强连通的
C、G只有一个顶点的出度为0
D、G只有一个顶点的入度为1
2、下面哪个语句不是命题（）。
A、中国将成功举办2008年奥运会
B、一亿年前地球发生了大灾难
C、我说的不是真话
D、哈密顿图是连通的
3、设R是实数集合，在上定义二元运算*：a，b∈R，a*b=a+b-ab，则下面的论断中正确的是（）。
A、0是*的零元
B、1是*的幺元
C、0是*的幺元
D、*没有等幂元
4、下面说法中正确的是（）。
A、所有可数集合都是等势的
B、任何集合都有与其等势的真子集
C、有些无限集合没有可数子集
D、有理数集合是不可数集合
5、无向完全图K3的不同构的生成子图有（）个。
A. 6 C. 4 D. 3
6、下面哪一种图不一定是无向树
A、无回路的连通图
B、有n个顶点n-1条边的连通图
C、每对顶点间都有通路的图
D、连通但删去一条边则不连通的图
7、设集合A＝{{1,2,3},{4,5},{6,7,8}}，则下列各式为真的是( )。
A B.{{4,5}} A
C. {1,2,3} A
D.A
8、在有界格中，若一个元素有补元，则补元( )。 A 、必惟一 B 、不惟一 C 、不一定惟一 D 、可能惟一
9、设集合A={1,2,3,…,10}，下面定义的哪种运算关于集合A 是不封闭的（ ） A 、 x*y=max{x,y} B 、 x*y=min{x,y}
C 、 x*y=GCD(x,y)，即x,y 的最大公约数
D 、 x*y=LCM(x,y)，即x,y 的最小公倍数
10、集合X 中的关系R ，其矩阵是??
??
?
?????=111011101M ，则关于R 的论述中正确的是（ ）。 A 、R 是对称的 B 、R 是反对称的 C 、R 是反自反的 D 、R 中有7个元素 11. 下列各组数中，哪个可以构成无向图的度数列（ ）。 ，1，1，2，2 ，2，2，2，3 ，2，2，4，6 ，3，3，3
12. *是定义在Z 上的二元运算，y x xy y x Z y x -+=*∈?,,，则*的幺元和零元分别是（ ）。
A.不存在，0 ，1
，不存在 D.不存在，不存在 13. 设N N N f ,:→为自然数，且
?????=为偶数
若为奇数若x x
x x f 2
1)(
则})0({)0(f f 和分别是（ ）。
，0 ，{0} C.{0}，{0} D.{0}，0
14. 下列命题公式中是矛盾式的有（ ）。
A.p p p ?→?→)(
B.p p q ∧→?)(
C.)()(p q q p ?→→→?
D.r q p →∨)( 15. 下列各Hasse 图中，是格的有（ ）。
A. B.
C. D.
16． 下列命题公式中是永假式的有（ ）。
A.p p p ?→?→)(
B.p p q ∧→?)(
C.)()(p q q p →?→→?
D.r q p →∨)( 17. 设命题公式(P (Q P))，记作G ，则使G 的真值指派为0的P ，Q 的取值是( )。
A.(0,0)
B.(0,1)
C.(1,0)
D. (1,1) 18. 与命题公式P （Q R ）等值的公式是( )。
A.(P Q)R
B.(P Q)R
C.(P Q)R
D. P (Q R) 19. 命题公式(P Q)P 是( )。
A.永真式
B.永假式
C.可满足式
D.合取范式
20. 设命题公式)(),(P Q P H Q P G ?→→?→??，则G 与H 的关系是( ) 。 A.H Q → B.G H → C.G H ? D.H G ?
21．谓词公式)())()((x Q y yR x P x →?∨?中量词x 的辖域是( )。 A ))()((y yR x P x ?∨? B. P(x) C.)()(y yR x P ?∨ D.)(x Q
22．设个体域为整数集，下列公式中其值为1的是( )。
A.)0(=+??y x y x
B.)0(=+??y x x y
C.)0(=+??y x y x
D.)0(=+???y x y x
23．设L(x)：x 是演员，J(x)：x 是老师，A(x,y)：x 佩服y. 那么命题“所有演员都佩服某些老师”符号化为( )。 A.),()(y x A x xL →? B.)),()(()((y x A y J y x L x ∧?→?
C.)),()()((y x A y J x L y x ∧∧??
D.)),()()((y x A y J x L y x →∧??
24．在谓词演算中，P(a)是)(x xP ?的有效结论，根据是 ( )。 规则 规则 规则 规则
25. 在图G ＝
(v i )=2E B. deg(v i )=
E C.
∑∈=V
v E v 2)deg( D. ∑∈=
V
v E v )deg(
26. 设G 是有n 个结点的无向完全图，则图G 的边数为( )；设D 是有n 个结点的有向完全图，则图D 的边数为( )。
A. n(n －1)
B. n(n+1)
C. n(n －1)/2
D. n(n+1)/2
27. 仅有一个孤立结点的图称为( )。
A.零图
B.平凡图
C.补图
D.子图
28. 设G ＝
A.
(G)
29. 图G 与G 的结点和边分别存在一一对应关系，是G ≌G (同构)的( )。
A.充分条件
B.必要条件
C.充分必要条件
D.既非充分也非必要条件
30. 设},,,{d c b a V =，则与V 能构成强连通图的边集合是( )。
A.},,,,,,,,,{><><><><><=c d b c d b a b d a E
B.},,,,,,,,,{><><><><><=c d d b c b a b d a E
C.},,,,,,,,,{><><><><><=c d a d c b a b c a E
D.},,,,,,,,,{><><><><><=d c d b d a c a b a E
31. 相邻矩阵具有对称性的图一定是( )。
A.有向图
B.无向图
C.混合图
D.简单图
32. 无向图G 是欧拉图，当且仅当( )。
的所有结点的度数全为偶数 的所有结点的度数全为奇数 连通且所有结点的度数全为偶数 连通且所有结点的度数全为奇数 33. 设m E n V E V G ==>=<,,,为连通平面图且有r 个面，则r ＝( )。
A. m －n+2 －m －2 +m-2 +n+2
34. 设G 是由5个结点组成的完全图，则从G 中删去( )条边可以得到树。
35. 由5个结点可构成的根树中，其叉数m 最多为( )。
D. 4
36. 下图是( ) 。 A.完全图 B. 哈密顿图 C.欧拉图 D.平面图
37. 设集合A
＝
{1,2,3,…
,10},在集合A 上定义的运算，不是封闭的为( )。
A.a,b A, a b=lcm{a,b}(最小公倍数)
B.a,b A, a b=gcd{a,b}(最大公约数)
C.
a,b A, a b=max{a,b} D.a,b
A, a b=min{a,b}
38. 在自然数N 上定义的二元运算，满足结合律的是( )。
b=a －b B. a b=a+2b C. a b=max{a,b} D. a b=a －b
39. 下列代数系统(G,*)中，其中*是加法运算. ( )不是群。
为整数集合 为偶数集合
为有理数集合 为自然数集合 40. 设1
，
2
，
3
是三个置换，其中
1
＝(1 2)(2 3)(1 3),
2
=(2 4)(1 4),
3
=(1 3 2
4) 则
3
可以表成( )。
A. 2
1σ B.1
2
C.2
2σ D.
21
41. 下列图表示的偏序集中，是格的为( )。
A.
B.
C.
D.
42. 设)1,0,,,,(+?B 是布尔代数，b a B b a ≤∈?,,，则下式不成立的是( )。 A.0=b a B.1=+b a C.a b a =+ D.1=+b a 43. 布尔代数式)(c b c ab ab +++=( )。 A.b a + B.c b + C.c b + D.c b + 44. 设集合A ＝{1,2}，B={a,b,c},C={c,d}, 则A ×(B C)＝( )。
A.{
B.{<1,c>,<2,c>}
C.{
D.{<1,c>,
45. 设A ＝{0,a},B={1,a,3},则A B 的恒等关系是( )。
A. {<0,0><1,1>,<3,3>,
B.{<0,0>,<1,1>,<3,3>}
C.{<1,1>,
D. {<0,1>,<1,a>,
A.自反的
B.反自反的
C.反对称的
D.等价的
47. 设集合σ},,,{},,,,{3214321b b b B a a a a A ==是从A 到B 的函数， ,,{21><=b a σ
},,,,,341322><><>
A.双射
B.满射但不是单射
C.单射但不是满射
D.非单射也非满射 48.下列式子中正确的是（ ）。 A.
=0 B.
C.
{a,b} D.
{}
49.有向图的邻接矩阵中，行元素之和是对应结点的( )，列元素之和是对应结点的( ) 。 A.度数 B. 出度 C.最大度数 D.入度
50. 给定无向图如下所示，下面给出的顶点集子集中，不是点割集的是（ ）。
A.{b,d}
B.{d}
C.{e}
D.{f,h} 51． 谓词公式?xA(x)∧
?xA(x)的类型是（ ）。 A.永真式 B.矛盾式
C.非永真式的可满足式
D.不属于(A),(B),(C)任何类型 52. 谓词公式)(y yP ?取真值为1的充分必要条件是( )。 A.对任意y ，使P(y)都取真值1 B.存在一个y 0，使P(y 0)取真值1 C.存在某些y ，使P(y)都取真值1 D.存在y 0，使P(y 0)取真值0
53. 设G 是群，当G 有（ ）个元素时，不能肯定G 是交换群。
54．若集合A ＝{a,b,c},为空集合，则下列表示正确的是( )。
a f b
g
d e
A.{a} A
B.{a} A A D.A
55. 设A, B, C 都是集合，如果A C ＝B C ，则有( ) 。 ＝B B C.当A －C ＝B －C 时,有A=B D.当C=U 时, 有A B
56. 设S 1＝，S 2＝{}, S 3＝P({}), S 4＝P(
)，以下命题为假的是( )。
S 4
S 3， S 2 S 3
57.设G 是有6个元素的循环群，a 是生成元素，则G 的子集（ ）是子群。 A.{a} B.{a,e} C.{e,a 3
} D.{e,a, a 2
}
58.设集合A={a,b,c,d,e},半序关系R 的哈斯图如下，假设A 的子集B={c,d,e},则元素c 为B 的（ ）。
A.下界
B.最大下界
C.最小上界
D.以上答案都不对 59. 设G
x yP(x,y)Q(z,w)，下面三个命题为真的是( )。
是前束范式 不是前束范式 不是一阶公式 是永真式 60．对任意集合S ，S
＝S ，满足( )。
A.幂等律
B.零一律
C.同一律
D.互补律
61．设命题公式()R Q P G ∧→?:，则使公式G 取真值为1的P ，Q ，R 赋值分别是( )。 A. 0，0，0 B. 0，0，1 ，1，0 ，0，0
62．设a 是集合A 的元素，则以下正确的是( )。 A.{}a a ? B.{}A a ?
C.A
a?
D.{}A
a∈
63．设集合A{1，2，3，4}，B：{2，4，6，9}，那么集合A，B的对称差A⊕B＝( )。
A.{1，3}
B.{2，4，6}
C.{1，3，6，9}
D.{1，2，3，4，6，9}
64. 有向完全图D＝<Ｖ，Ｅ>，则图D的边数是( )。
A.｜Ｅ｜(｜E｜—1)／2
B.｜Ｖ｜(｜Ｖ｜一1)／2
C.｜Ｅ｜(｜Ｅ｜－１)
D.｜Ｖ｜(｜Ｖ｜－１)
65．设G是有n个结点，m条边的连通阻，必须删去G的( )条边，才能确定G的一棵生成树。
一n＋1
一m
＋n＋1
—m＋1
66. 设N为自然数集合，
A. xοy = x+y－2xy ο = x+y
C. xοy = x?y ο = |x|+|y|
67.已知图G的相邻矩阵为
?
?
?
?
?
?
?
?
?
?
?
?
1
1
1
1
1
1
，则G有（）。
个点，度为4 个点，度为6
个点，度为3 个点，度为6
68. 设集合A={1，2，3，……，10}，半序关系是A上的整除关系，则半序集（A ，）
上的元素10是集合A的（）。
A.最大元
B.最小元
C.极大元
D.极小元
二、填空题
1. 代数格（L，，）中的运算和满足的算律有_______、__________、__________。
2、A是含有3个元素的集合，在A上可以定义______个不同的等价关系。
3、R是实数集合，R中的关系g={
4、
5、当n是____________值时，无向完全图K n是欧拉图。
6、I是整数集合，代数系统
7、元素数目不超过________的格一定是链。
8、公式)
(
)
(Q
P
Q
P∧
?
∨
?的主合取范式为___________________________。
9、R
P
Q
P
Q∨
→
?,
,的有效结论是__________。
10、已知公式A(p，q，r)的主合取范式为M
0∧M
3
∧M
5
，它的主析取范式为(写成编码形
式)______________________。
11、设A={a,b}，B={0,1,2}，那么可定义________种不同的从A到B的单射。
12. 已知集合A={，1，2}，则A的幂集合 (A)=__________。
13、设
14、仅当n________时，K n为平面图。
15. p→q 的主合取范式是_________________________ 。
16. 语句“我在说谎”___________命题。（填“是”或“不是”）。
17. 设A={a,b,c,d}，R是定义在A上的关系，R={
18．一个树林G有三棵树，G的顶点数是20，则G的边数为_______________ 。
19．P(P(?))=________________________________________ 。
20．整数加法群
21．设有向图D ＝
?
???
????
???110010000100
0120，那么E ＝ 。 22. 语句“这句话是错的” 命题。（填“是”或“不是”）。
23．设命题公式G ＝P (Q R)，则使G 取真值为1的指派是 ， ，_________。 24. 已知命题公式为G ＝(P Q)R,则命题公式G 的析取范式是 。 25. 公式))(),()),()((x S z y zR y x Q x P x →?∨→?的自由变元是 , 约束变元是 。
26. 谓词逻辑公式)()(x xQ x xP ?→?的前束范式是 。
27. 设个体域D ＝{a,b},消去公式中的量词，则??∧?)()(x xQ x xP 。 28. 换名规则施于 变元，代入规则施于 变元。 29. 设图G ＝
＝
是G 的真子图，
若 ，则G 是G 的生成子图。
30. 在无向图中，结点间的连通关系具有 性， 性， 性，是 关系. 。
31. 无环有向图D 的关联矩阵M(D)中，第i 行值为1的元素个数为结点v i 的 ， 第j 列值为－1的元素个数为结点v j 的 .。
32. 设G 是完全二叉树，G 有15个结点，其中有8个是树叶，则G 有 条边，G 的总度数是 ，G 的分支点数是 ，G 中度数为3的结点数是 . 。 33. 连通有向图D 含有欧拉回路的充分必要条件是 。
34. 设G 是有n 个结点的简单图，若G 中每对结点的度数之和 ，则G 一定是哈密顿图. 。
35. 设G 是有n 个结点，m 条边的连通图，要确定G 的一颗生成树，必须删去G 的 条边. 。
36. 一个有向树T 称为根树，若 ，其中 ，称为树根，
称为树叶. 。
37. 在代数系统(N,+)中，其单位元是 ， 有逆元. 。
38. 设A 是非空集合，集合代数(P(A)，，)中，P(A)对运算的单位元是 ， P(A)对运算的单位元是 。 39. 把置换
???
?
??564132654321表成轮换的乘积是 ，表成对换的乘积是 。
40. 设G 是由6个元素构成的循环群，a 是G 的一个生成元素，则G 有 个子群，G 的生成元是 。
41. 非空集合L ，其上定义二元运算和，如果 是交换群，(L,)是 ，
而且 满足分配律，则L 对二元运算和构成环。
42. 设L 是一个集合，和是L 上两个二元运算，如果这两个二元运算满足 律， 律和 律，则(L,,)是格。
43. 在布尔代数中，有b a b a a ∨=∧∨)(成立. 则该式的对偶式 也一定成立。
44. 设R 1，R 2是集合A ＝{1,2,3,4}上的二元关系,其中 R 1＝{<1,1>,<1,2>,<2,4>}, R 2={<1,4>,<2,3>,<2,4>,<3,2>},则R 1R 2＝ 。 45. 设R ，S 都是集合A 上的等价关系，则对称闭包s(R
S)= 。
46. 图的通路中边的数目称为 . 结点不重复的通路是 通路. 边不重复的通路是 通路。
47. 将谓词公式),()()),()()((z x zS x xR z x Q x R x P x ?→?∧∨→?中的约束变元换名_____。
48. 写出下列集合的子集：B={} ;C=________。
49．设全集合E ＝{1,2,3,4,5},A={1,2,3},B={2,5},A B= ,~B= 。 ～A ～B= 。 50. 设A, B 代表集合，命题A B
的真值为 。
51. 设集合A ＝{a,b,c},B={a,b},那么P(A)－P(B)= ，P(B)－P(A)= 。
52．设A ＝{=,,,, }选择适当的符号填在各小题的横线上.（1）(1,2,3,4) N;
(2) Z Q Q ,2
。
53．关于格的命题P ：a ∧(b ∨c)，求P 的对偶命题P*=_______________。 54．计算Z6的所有理想__________________。 55．求)())((e R x Q P x ∨→?的真值______________。 56．判定公式(P Q
R
Q )(P
R
Q)的类型___________。
57. 将命题公式)(P R Q P →?∧?∧?化为只含和
的尽可能简单的等值式
_________。
58. 设n(A)=m,则A 上有___________个不同的自反关系。
59. 设集合A={a,b,c,d}，A 上的关系R={(a,a),(a,c),(b,d)} ，则关系R 2
=__________________。60. 设集合A 中有4个元素,则A 上的不同的等价关系的个数为__________个。 三、判断题
1. 空间中的平行六面体是平面图。（ ）
2、每个顶点的度都是偶数的无向图一定是欧拉图。（ ）
3、顶点数目相同，边数也相同的两个无向图一定同构。（ ）
4、函数的逆关系还是函数。（ ）
5、A ，B ，C 都是集合，如果A ∪B=A ∪C ，则B=C 。（ ）
6、设R 是环，A,B 是R 的两个理想，且B 包含于A,则A/B 是R/B 的理想，并且 R/B /(A/B) 同构于 R/A 。（ ） 7. q p ?∧的对偶是 q p ∨? 。（ ）
8. 设G 是有r 个面的连通平面图，顶点数和边数分别是n 和m ，则n-m+r=2 。（ ） 9. n 阶有向完全图有n （n-1）条边。（ ）
10. 在代数系统>*<,S 中，若z x y x *=*，则 z y = 。（ ） 11. 设无向图T 是树，则T 中一定没有简单回路。（ ） 12. 能够画在一张平面上的图是平面图。
13. 设>*<,S 是代数系统，B 是S 的非空子集，则>*<,B 是>*<,S 的子代数。（ ） 14. 循环群的子群仍然是循环群。（ ） 15. 格不一定是布尔代数。（ ）
16．1+101=110是命题 。（ ）
17．“全体立正是命题” 。（ ）
18．“明天是否开大会”是命题 。（ ）
19．“如果天气好，那么我去散步”是命题。（ ）
20. 判断(Z,)是否为格其中是数的小于或等于关系。（ ）
21．设 R 是实数集，“＋”为数的加法，“×”定义为b a b a =?. 试问R 对二元运算＋和×是否构成环。（ ）
22. 设集合A ＝{18的正整数因子}，为整除关系，说明
26. 已知S ＝{2,a,{3},4},R={{a},3,4,1},则{a}S 。（ ） 27. 整数集合Z 和普通的减法运算是封闭的。（ ）
28．在R 中定义二元运算：* ,a*b=a+b+ab,对于任意a,b 属于 R ，则
四、证明题
1. 设
2. 形式证明q s p r s r q p ?∧?→∨→,,
3. 证明：P (Q R)P Q R.
4．试证明：R S Q P S R Q P →?∧∨?∧→→)())((
5．试证明：Q R R Q Q P ???∧∨?∧?∧?)()( 6. 证明：)
()(x xB x xA ?→?))()((x B x A x →?
7．设G 是图，无回路，但若外加任意一条边于G 后，就形成一回路. 试证明G 必为树. 8. 设B 是任意集合，试验证(P(B),)是群. P(B)是集合B 的幂集，是集合的对称差运算， 9．给定代数系统(G,+,*), 二元运算见表一，表二.
表一 表二 + a b c D * a b c D A a b c D a a a a a B b a d C b a b c d C c D a B c a c d b D
d
C
b
A
d
a
d
b
c
证明(G,+,*)是域.
10. 证明如果非空集合A 上的二元关系R 和S 是偏序关系，则S R ?也是A 上的偏序关系． 11．试证A －(B －C)＝(A －B)(A C)
12．设非空集合A ，验证(A A P ,~,,,),(???)是布尔代数，
13. 试证明属于关系不满足传递性，即对于任意的集合A,B,C 若A ∈B 且B ∈C 不一定有 A ∈C
14．设 A,B 为两个集合，证明 A —B=A 当且仅当A ∩B= ?
15. 设R,S 都是非空集合A 上的二元关系，且他们是对称的，证明：RoS 具有对称性当且仅当 RoS=SoR.
16. 已知g ：A->B,f ：B->C
1） 已知fog 是单射的且g 是满射的，证明f 是单射的 2） 已知fog 是满射的且f 是单射的，证明g 是满射的 17．设A 是传递集，证明A+也是传递集。
18．设G 是n 阶无向简单图，其直径为d(G)=2, ο(G)=n-2，证明G 的边数m ≥2n-4 19．V=
五、计算题
1. 无向树T 有2个2度顶点，1个3度顶点，3个4度顶点，其他的都是树叶，问T 中有多少片树叶
2. 设公式()()x Q x P → ，其中P(x)：x>2，
Q(x)：x=0，F 是永假式，个体域是{1，2}，求公式A(x)的真值 3. 设集合X={1，2，3, 4}，X 中的关系为
F={<1，1>，<1，2>，<1，4>，<2，1>，<2，2>，<3，3>，<4，1>，<4，4>} 写出F 的关系矩阵及其关系图，F 有哪些性质
4. (1) n(n ≥1)阶无向完全图与有向完全图各有多少条边为什么 (2)完全二部图K m n ,中共有多少条边为什么
(3) 每个顶点的度都为k 的无向图称为k 正则图，问：n 阶k 正则图中共有多少条边为什么
5. 设集合L={a ，b}，在L 中规定 + 和·如下：
a+a=a ，a+b=b+a=b ，b+b=b a ·a=a ，a ·b=b ·a=a ，b ·b=b
问
7. 设集合M={1，2，3，4，5}， 和 是M 上的两个置换， =?
??
??
?1254354321， =
（1 4 5）（2 3），用轮换的形式写出 ，，
－1
i
－1
。
8. 对集合L ，规定对于x ，y ∈L ，x ≤y 当且仅当x 是y 的因子。问下面哪几个偏序集是格为什么
(1)L={1, 2, 3, 4, 6, 12} (2)L={1, 2 , 3, 48, 12, 14}
(3)L={1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 9． 在全总个体域中符号化下列命题。
（1）是金子总是要发光的。
（2）并非所有微笑的人都是高兴的。 （3）平面图的色数不超过4
10． 若无向图G 是欧拉图，G 中是否存在割边为什么 11. 设集合}6,5,4,3,2,1{=A ，R
是定义在
A
上的二元关系，
},
,|,{是素数b
a
A b a b a R ∈><=，写出R 的关系矩阵并求R 的对称闭包。 12. 设集合A={2，3，4，6，8，12，24}，R 为A 上的整除关系。 （1）画出半序集（A ，R ）的哈斯图；
（2）写出集合A 中的最大元、最小元、极大元、极小元；
（3）写出A 的子集B={2，3，6，12}的上界、下界、最小上界，最大下界。 13. 令X={1x ,2x ,…,m x },Y={1y ,2y ,…,n y }。问
⑴有多少个不同的由X 到Y 的关系 ⑵有多少个不同的由X 到Y 的函数
⑶当n,m 满足什么条件时，存在单射，且有多少个不同的单射 14．在全总个体域中符号化下列命题。
（1）在中国工作的人并非都是中国人。 （2）有的人在微笑但内心不高兴。 （3）每种金属都可以溶解在某种液体种。 15. 将下列命题符号化：
(1) 虽然交通堵塞，但是老王还是准时到达火车站； (2) 张力是三好学生或优秀共青团员
(3) 老李或小刁中有一个人去广州出差 16. 判定公式P Q 与P Q 是否等值. 17． 用等值演算法判定公式P
(Q R)P Q R 是永真式永假式
18．求公式)()(Q P R P ?∧→?的主合取范式和主析取范式.
19. 化简下式： (A B C)(A B C)
20． 设命题P,Q 的真值为0，命题R,S 的真值为1，求命题公式)()(S Q R P ∨?∧?的真值.
21． 将下列命题符号化：
（1）每个母亲都爱自己的孩子； (2) 所有的人都呼吸； (3) 有某些实数是有理数. 22．指出下列公式
),()),(),((y x xH z y L y x R y x ?∧∨??
中量词的每次出现辖域，并指出变元的每次出现是约束出现，还是自由出现，以及公式的约束变元，自由变元. 23．给定解释I ：
① D ＝{2,3};
② D 中特定元素a=2； ③ 函数为2)3(,3)2(==f f ④ 谓词F(x)为F(2)=0,F(3)=1 G(x,y)为G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1
L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0
求在解释I 下各公式的真值. (1) ),()(a x G x xF ∧?;
(2) ),(y x yL x ??；
24．讨论公式),(),(y x xF y y x yF x ??→??的类型.
25．将公式F )),()(()),()((z y zD y yC y x B x A x ?→?→→?化为前束范式. 26. 判定下面二图是否同构
27. 设G ＝(V,E)是一个无向图，},,...,,{821v v v V =
},,,,,,,,,,,,,{87434551133221><><><><><><><=v v v v v v v v v v v v v v E (1) 画出G 的图解；
(2) 指出与v 3邻接的结点，以及与v 3关联的边； (3) 指出与e 1关联的结点； (4) 该图是否有孤立结点和孤立边
(5) 求出各结点的度数，并判断是不是完全图 (6) G ＝
各是多少
28. 给定下列六个图(如图)，
G 1＝
G 4＝
(1) 哪些图是有向图哪些图是无向图 a
a a
a a a
b
e b e b
e b e b e b
e
(2) 哪些是简单图
(3) 哪些是强连通图哪些是单侧连通图哪些是弱连通图
29. 求图G 的点割集、割点、边割集和割边.
30. 已知有关人员a,b,c,d,e,f,g 的有关信息：
a ：说英语；
b ：说英语或西班牙语；
c ；说英语，意大利语和俄语；
d ：说日语和西班牙语
e ：说德语和意大利语；
f ：说法语、日语和俄语；
g ：说法语和德语.
试问上述7人中是否任意两人都能交谈(如果 必要，可由其余5人中组成的译员链帮助)
31. 在具有n 个结点的完全图K n 中，需要删去多少条边才能得到树. 32．画出具有下列条件的有 5个结点的图.
(1) 没有哈密顿回路，也不能适当指定各边的方向，使其具有欧拉回路； (2) 有哈密顿回路，但是不能适当指定各边的方向，使其具有欧拉回路； (3) 没有哈密顿回路，但是能适当指定各边的方向，使其具有欧拉回路； (4) 有哈密顿回路，也能适当指定各边的方向，使其具有欧拉回路.
33. 通常数的加法运算可看作正整数N ＋上的二元运算. 下列集合是N ＋的子集，加法运算在这些子集上封闭吗为什么
(1) }15{1的因子是n n S = (2) }15{2的倍数是n n S =
离散数学考试题(后附详细答案) 一、命题符号化（共6小题，每小题3分，共计18分） 1.用命题逻辑把下列命题符号化 a)假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS) b)我今天进城，除非下雨。 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→Q c)仅当你走，我将留下。 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不是有理数 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为： x(R(x) Q(x)) 或x(R(x) →Q(x)) b)对于所有非零实数x，总存在y使得xy=1。 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： x(R(x) E(x,0) →y(R(y) E(f(x,y),1)))) c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b. 设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为：F(f)a(A(a)→b(B(b) E(f(a),b) c(S(c) E(f(a),c) →E(a,b)))) 二、简答题（共6道题，共32分） 1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。 （5分） (P→(Q→R))(R→(Q→P))（PQR）(PQR) (（PQR）→(PQR)) ((PQR) →（PQR）). (（PQR）(PQR)) ((PQR) （PQR）) (PQR)(PQR) 这是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 （PQR（PQR（PQR（PQR（PQR（PQR 2.设个体域为{1,2,3}，求下列命题的真值（4分） a)xy(x+y=4) b)yx (x+y=4) a) T b) F 3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） x(F(x)→G(x))→(xF(x)→xG(x)) x(F(x)→G(x))→(yF(y)→zG(z)) x(F(x)→G(x))→yz(F(y)→G(z)) xyz((F(x)→G(x))→(F(y)→G(z))) 4.判断下面命题的真假，并说明原因。（每小题2分，共4分）
离散数学考试（试题及答案） 一、（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>}。
离散数学试题（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) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（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 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，，
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、下列哪些公式为永真蕴含式？( ) (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）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6） 44 一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，ο〉，Z是整数集，ο定义为xοxy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的 等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 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 满足：< 第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试 3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章 一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。 9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 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 的关系图为 《离散数学》模拟试题 一、 填空题（每小题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个 离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q 离散数学试题与答案试卷一 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 8．图的补图为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ?； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A B C ?；B．{Φ，3，4}；C．{4，Φ，3，3}；D．{3，4}。 A．{4，3}Φ 3、设A={1，2，3}，则A上的二元关系有（）个。 A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） Rο是自反的； A．若R，S 是自反的，则S Rο是反自反的； B．若R，S 是反自反的，则S Rο是对称的； C．若R，S 是对称的，则S Rο是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s t s p A R= ∧ =则P（A）/ R=（） < > ∈ s (| || |} {t ) , ( | , A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 离散数学考试试题(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 一、判断正误20% （每小题2分） 1、设A.B. C是任意三个集合。 （1）若A∈B且B?C，则A?C。（） （2）若A?B且B∈C，则A?C。（） （3）若A?B且B∈C，则A?C。（） （4）A) ( ) ( ) (C A B A C B ⊕ = ⊕。（） （5）(A–B)?C=(A?C)-(B?C)。（） 2、可能有某种关系，既不是自反的，也不是反自反的。（） ３、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（） ４、一个图是平面图，当且仅当它包含与Ｋ 3， 3 或Ｋ 5 在２度结点内同构的子图。（） ５、代数系统中一个元素的左逆元并一定等于该元素的右逆元。（） ６、群是每个元素都有逆元的半群。（） 二、8% 将谓词公式)) , ( ) ( ) ( ) (( )) , ( ) ( )( (z y Q z y P y y x Q x P x? ∧ ? → → ?化为前束析取范式与前束合取范式。 三、8% 设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{ 五、10% 证明：若图Ｇ是不连通的，则Ｇ的补图G 是连通的。 六、10% 证明：循环群的任何子群必定也是循环群。 七、12% 用ＣＰ规则证明： １．F A F E D D C B A →?→∨∧→∨,。 ２．?∨??∨?(()()())()()((x P x x Q x P x )()x Q x 。 八、10% 用推理规则证明下式： 前提: ))()()(()),()()(())()()(((y W y M y y W y M y x S x F x ?∧?→?→∧? 结论：?→?)()((x F x S ))(x 九、13% 若集合Ｘ＝｛（１，２），（３，４），（５，６），……｝ }|,,,{12212211y x y x y x y x R +=+>><><<= 1、证明R 是X 上的等价关系。 2、求出X 关于R 的商集。 一、 填空 20%（每小题2分） 《离散数学》试卷（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人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？离散数学模拟题(开卷)
《离散数学》及答案
离散数学试卷及答案一
离散数学模拟试卷和答案
离散数学(上)模拟题
离散数学作业答案
离散数学试卷及答案(2)
离散数学模拟试题及答案
离散数学模拟试卷和答案
离散数学课后答案
离散数学全部试卷
离散数学考试试题(A、B卷及答案)
离散数学试卷及答案(17)
离散数学期末试卷A卷及答案
相关主题
文本预览