离散数学测试题答案
测试题
——离散数学
一、选择题
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 )=2?E ? 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) B.?(G)?n C. ?(G)>n D. ?(G)?n 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. 21σ B.?1?2 C.2 2σ D.?2?1 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.{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 ? f ? b ? ? ? ?g c ? ?h 图 d e 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 ＝ 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 1?R 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的正整数因子}，?为整除关系，说明 25．如果S ?T ＝S ?M ，则T ＝M 。（ ） 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,+,*), 二元运算见表一，表二. 表一 表二 证明(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 问 6. 设多重集A={{?}，{?，1}，{1，1，?}}， B={{?，1}，{1}}.计算A Y B ，A I B ，A-B 7. 设集合M={1，2，3，4，5}，? 和? 是M 上的两个置换，? =? ?? ???1254354321，? =（1 4 5）（2 3），用轮换的形式写出? ?，??，?－1 ? －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＝ G2＝ G3＝ G4＝ 试问： (1) 哪些图是有向图？哪些图是无向图？ (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 = (3) }246{2 3n n n S 整除， 整除= 34. 212121r r r r r r -+=*；运算*是否有单位元和幂等元？若有单位元的话，哪些元素有逆 元？ 35. )1,0,,,,(+?B 是布尔代数，B c b a ∈?,,，化简c b a bc a bc c ab abc ++++. 36. 设143)(,122)(223++=++=x x x Q x x x P 是定义在Z 5(＝{0,1,2,3,4})上的多项式(即系数是Z 5的元素的多项式)，试计算P(x)+Q(x)，P(x)Q(x). 37. 回答下列代数系统是环吗？是交换环吗？ (1) (Z m ,＋，*),其中Z m ＝{0,1,2,…,m －1}，＋和*是模m 加法和乘法. (2) (M n (R)，＋，?), 其中M n (R)是n 阶实矩阵全体，＋，?分别是矩阵的加法和乘法. 38. 设集合A ＝{a,b},R 是P(A)上的包含关系，写出R 的表达式和关系矩阵. 39. 设A ＝{1,2,3},用列举法给出A 上的恒等关系I A ，全关系E A ，A 上的小于关系 },,{y x A y x y x L A <∧∈><= 及其逆关系和关系矩阵. 40. 设A ＝{1,2,3,4}, R 是A 上的二元关系，其关系矩阵为 ? ? ??? ???? ???=0001100000011001 R M 试求 (1) R 的关系表达式； (2) Dom(R)和Ran(R)； (3) R ?R 中有多少个有序对 (4) R －1 的关系图中有多少条自回路? 41. 设集合},,,,{d c b a A =判定下列关系，哪些是自反的，对称的，反对称的，传递的？ }, ,,,{},,,,,,{},,{}, ,,,,,{},,,,{54321><><=><><><=><=><><><=><><=d b c a R c c b b a a R d c R a d c b a a R a b a a R 42. 设A ＝{1,2,3,4,5,6},定义A 上的二元关系 R ＝{<1,1>,<1,4>,<2,2>,<2,3>,<2,6>,<3,2>,<3,3>,<3,6>, <4,1>,<4,4>,<5,5>,<6,2>,<6,3>,<6,6>} (1) 判定R 是否为等价关系？ (2) 若是等价关系，写出A 的关于R 的等价类. 43. 设集合A ＝{a,b,c,d},定义R ＝{ f （?3）=1，f （1）=5，f （5）= ?3．a ：5． 个体域D=（?3，1，5）． 45．化简))(()))(((A B B A C B A --??-? 46．设集合 A={a,b},B={1,2,3},C={d},求(A ×B)×C ，A ×B ×C ，B ×A. 47．用列举法表示以下集合： (1) }7{2≤∧∈=x N x x A ； (2) }33{<-∧∈=x N x x A ; (3) }0)1({2≤+∧∈=x R x x A 48. 列出下列集合的各元子集，并求幂集 （1）A={a,b,c} (2) A={1,{2,3}} (3)A={?,{ ? } } 49. A={a,b,c},B={1,2},令a1=P(A),a2=A->B, 构造一个a1到a2的双射函数，再构造一个 a2到a1的双射函数 50. 由f:A->B 导出A 上的等价关系定义为： R={ f1(n)=n f2(n)= 1 n 为奇数 f3(n)=0 n 为偶数 f3(n)=j,n=3k+j,j=0,1,2,k ∈N f4(n)=j,n=6k+j,j=0,1,…,5,k ∈N Rk 为fk 导出的N 上的等价关系,k=1,2,3,4 1) 求商集N/Rk k=1,2,3,4 2) 求H={10k|k ∈N }在f1,f2,f3,f4 下的象！ 51．对图给出的二叉树分别进行先根遍历、中根遍历和后根遍历。 更多课程资料请到大学课程网学习 测 试 题 答 案 ——离散数学 一、选择题 1. A 2. C 3. C 4. A. 5. D 6. C 7. D 8. C 9. D 10. D 12. D 13. B 14. B 15. B ,A ,D 二、填空题 1. 交换律、结合律、吸收律 2. 5 3. 不是 4. 不存在 5. 奇数 6. 1, -1 7. 3 8. )()(Q P Q P ∨∧?∨? 9. R 10. m1∨m2∨m4∨m6∨m7 11. 6 12、?(A)={?，{?}，{1}，{2}，{?，1}，{?，2}，{1，2}，A} 13、= 14、奇数 15. q p ∨? 16. 不是 17、{ 23. (1,0,0,) (1,0,1) (1,1,1) 24. P ??Q ?R 25. y,x x,z 26. ))()((x Q x P x ∨?? 27. ))()(()()(b Q a Q b P a P ∨∧∧ 28. 约束 自由 29. E E V V E E V V ?'='?'?',;或 30. 自反性 对称性 传递性 等价. 31. 出度 入度 32. 14 28 7 6 33. D 中每个结点的入度＝出度. 34. 大于或等于n 35. m+1－n 36. 若有向图T 恰有一个结点的入度为0，其余结点入度为1 入度为0的结点 入度为1的结点. 37. 0 仅有单位元0. 38. ? A. 39. (1 2 3)(5 6) (1 3)(1 2)(5 6)(不唯一) 40. 4 a ，a 5 41. (L,?) 半群 二元运算?对运算? 42. 交换律 结合律 吸收律 43. b a b a a ∧=∨∧)( 44. {<1,4>,<1,3>} 45. R ?S 46. 通路出度 初级 简单. 47. ),()()),()()((w x wS v vR z u Q u R u P u ?→?∧∨→? 48. ?，{?} ? 离散数学试题（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 ＝{，，，，，，，， 离散数学试题(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={ 一、填空 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 的关系图为 试卷二试题与参考答案 一、填空 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、下面偏序集( )能构成格。 离散数学考试题(后附详细答案) 一、命题符号化（共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分） 一、单项选择题(本大题共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 离散数学期末试题及答 案 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的补元( ). 离散数学考试试题（A卷及答案） 一、（10分）证明?(A∨B)→?(P∨Q)，P，(B→A)∨?P A。 证明：(1)?(A∨B)→?(P∨Q) P (2)(P∨Q)→(A∨B) T(1)，E (3)P P (4)A∨B T(2)(3)，I (5)(B→A)∨?P P (6)B→A T(3)(5)，I (7)A∨?B T(6)，E (8)(A∨B)∧(A∨?B) T(4)(7)，I (9)A∧(B∨?B) T(8)，E (10)A T(9)，E 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 解符号化命题，设A：甲参加了比赛；B：乙参加了比赛；C：丙参加了比赛；D：丁参加了比赛。 依题意有， (1)甲和乙只有一人参加，符号化为A⊕B?(?A∧B)∨(A∧?B)； (2)丙参加，丁必参加，符号化为C→D； (3)乙或丁至多参加一人，符号化为?(B∧D)； (4)丁不参加，甲也不会参加，符号化为?D→?A。 所以原命题为：(A⊕B)∧(C→D)∧(?(B∧D))∧(?D→?A) ?((?A∧B)∨(A∧?B))∧(?C∨D)∧(?B∨?D)∧(D∨?A) ?((?A∧B∧?C)∨(A∧?B∧?C)∨(?A∧B∧D)∨(A∧?B∧D))∧((?B∧D)∨(?B∧?A)∨(?D∧?A)) ?(A∧?B∧?C∧D)∨(A∧?B∧D)∨(?A∧B∧?C∧?D)?T 但依据题意条件，有且仅有两人参加竞赛，故?A∧B∧?C∧?D为F。所以只有：(A∧?B∧?C∧D)∨(A∧?B∧D)?T，即甲、丁参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误？为什么？给出正确的推理形式。 (1)?x(P(x)→Q(x)) P (2)P(y)→Q(y) T(1)，US (3)?xP(x) P (4)P(y) T(3)，ES (5)Q(y) T(2)(4)，I (6)?xQ(x) T(5)，EG 解 (4)中ES错，因为对存在量词限制的变元x引用ES规则，只能将x换成某个个体常元c，而不能将其改为自由变元。所以应将(4)中P(y)改为P(c)，c为个体常元。 正确的推理过程为： (1)?xP(x) P (2)P(c) T(1)，ES (3)?x(P(x)→Q(x)) P (4)P(c)→Q(c) T(3)，US (5)Q(c) T(2)(4)，I (6)?xQ(x) T(5)，EG 四、（10分）设A＝{a，b，c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性。 解设R＝{ 一．判断题（共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?{ 离散数学考试试题(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 填空10% （每小题 2 分） 1、若P，Q，为二命题，P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数，都存在比它大的实数” 令F（x）：x 为实数，L（x, y） : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP（x） xQ（x）的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为 换名规则。 5、设x 是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y 是自由的，则被称为存 在量词消去规则，记为ES。 选择25% （每小题分） 1、下列语句是命题的有（）。 A、明年中秋节的晚上是晴天； C、xy 0 当且仅当x 和y 都大于0； D 、我正在说谎。 2、下列各命题中真值为真的命题有（）。 A、2+2=4当且仅当3是奇数； B、2+2=4当且仅当 3 不是奇数； C、2+2≠4 当且仅当3是奇数； D、2+2≠4当且仅当 3 不是奇数； 3、下列符号串是合式公式的有（） A、P Q ； B、P P Q； C、( P Q) (P Q)； D、(P Q) 。 4、下列等价式成立的有（ ）。 A、P QQ P ； B、P(P R) R； C、P (P Q) Q； D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ，且A1 A2 A n B 则 （ ）。 A、称A1 A2 A n 为 B 的前 件； B 、称 B 为A1,A2 A n 的有效结论 C 、 x(M (x) Mortal (x)) ； D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为：个体域 D={2} ，P(x) ：x>3, Q(x) ：x=4则 A 的 真 值为（ ） 。 A 、 1； B 、 0； C 、 可满足式； D 、无法判定。 9、 下列等价关系正确的是（ ）。 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 。 10 、 下列推理步骤错在（ ）。 ① 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 、⑥ 逻辑判断 30% 1、 用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ，B 为二合式公式，且 B ，则（ ）。 7、 A 、 A C 、 A B 为重言式； B 、 B ； E 、 A B 为重言式。 人总是要死的”谓词公式表示为（ ）。 论域为全总个体域） M （x ） ： x 是人； Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ； B M (x) Mortal (x) 离散数学期末考试试卷(A卷) 一、判断题：（每题2分，共10分） （1） （1） （2）对任意的命题公式, 若, 则 （0） （3）设是集合上的等价关系, 是由诱导的上的等价关系，则。（1） （4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。 （0） （5）设是上的关系，分别表示的对称和传递闭包，则 （0） 二、填空题：（每题2分，共10分） (１) 空集的幂集的幂集为（）。 (２) 写出的对偶式（）。 （３）设是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（），同学小王所在 的等价类为（）。 （４）设是上的关系，则满足下列性质的哪几条：自反的，对称的，传递的，反自反的，反对称的。 （） (5)写出命题公式的两种等价公式( ）。 三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题（４）（５）（６）。（12分） （１）（１）仅当今晚有时间，我去看电影。 （２）（２）假如上午不下雨，我去看电影，否则就在家里读书。 （3）你能通你能通过考试，除非你不复习。 （４）（４）并非发光的都是金子。 （５）（５）有些男同志，既是教练员，又是国家选手。 （６）（６）有一个数比任何数都大。 四、设，给定上的两个关系和分别是 （１）（１）写出 和 的关系矩阵。（２）求 及 （1２分） 五、求 的主析取范式和主合取范式。（１０分） 六、设 是 到 的关系， 是 到 的关系，证明： （8分） 七、设 是一个等价关系，设 对某一个 ,有 ，证明： 也是一个等价关系。（10分） 八、（1０分）用命题推理理论来论证 下述推证是否有效？ 甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获 胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。 九、（１０分） 用谓词推理理论来论证下述推证。 任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑 自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行 (论 域是人)。 十、(8分) 利用命题公式求解下列问题。 甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好， 甲说：“不是我，”乙说：“是丁，”丙说：“是乙，” 丁说：“不是我。” 四人的回答只有一人符合实际，问若只有一人成绩最 好，是谁？ 离散数学期末考试试卷答案(A 卷) 一、判断题：（每题2分，共10分） （1）}}{{}{x x x -∈ （ ∨） (2) 对任意的命题公式C B A ,,, 若 C B C A ∧?∧, 则B A ? ( ? ) （3）设R 是集合A 上的等价关系, L 是由 R A 诱导的A 上的等价关系，则L R =。 ( ∨ ) （4） 任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等 价。 （ ? ） （5）设R 是A 上的关系，)(),(R t R s 分别表示R 的对称和传递闭包，则 )()(R st R ts ? （ ? ） 二、填空题：（每题2分，共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是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。 一、填空 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 = 。 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为 则 R= 。 8．图的补图为 。 9．设A={a ，b ，c ，d} ，A 上二元运算如下： 那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。 10．下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ? ； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 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 p R= t s ∈ =则P（A）/ R=（） < > ∧ A ) (| || |} ( , {t , | s A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（） 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 离散数学练习题 1、图中度为零的结点称为孤立结点。 A. 正确 B. 错误 正确：【A】 2、域是整环。 A. 正确 B. 错误 正确：【A】 3、有限格都是有界格。 A. 正确 B. 错误 正确：【A】 4、连通且不含圈的图称为树。 A. 正确 B. 错误 正确：【A】 5、“如果1+1≠3，则2+2≠4”是真命题。 A. 正确 B. 错误 正确：【B】 6、无向图G为欧拉图，则G是连通的。 A. 正确 B. 错误 正确：【A】 7、若A和B都是谓词公式，则(A∧B)、(A∨B)、(A→B)、(A<->B)都是谓词公式。 A. 正确 B. 错误 8、设A, B, C是命题公式，则AVBV﹁C 也是命题公式。 A. 正确 B. 错误 正确：【A】 9、设〈L，≤〉是格，则格的交∧和并∨运算满足等幂律。 A. 正确 B. 错误 正确：【A】 10、“x+3>1。”是命题。 A. 正确 B. 错误 正确：【B】 11、半群满足交换律。 A. 正确 B. 错误 正确：【B】 12、在任何图中，奇数度的结点数必是偶数。 A. 正确 B. 错误 正确：【A】 13、在格〈L，∨，∧〉中，如果交运算对并运算是可分配的，则并运算对交运算也是可分配的。 A. 正确 B. 错误 正确：【A】 14、完全图Kn没有割集，它的连通性能是最好的。 A. 正确 B. 错误 15、对任意集合A，都有??A。 A. 正确 B. 错误 正确：【A】 17、强连通图一定是单向连通图。 A. 正确 B. 错误 正确：【A】 18、代数系统〈G，°〉为群的条件是存在零元素。 A. 正确 B. 错误 正确：【B】 19、对应日常生活中的“任意的”，“所有的”，“一切的”等词，用符号“任意”表示。 A. 正确 B. 错误 正确：【A】 20、如果a是集合A中的元素，则称a属于A，记作a?A。 A. 正确 B. 错误 正确：【B】 21、A,B是集合,P（A），P（B）为其幂集,且,则P(A)∩P(B)为（） A. B. C. D. 正确：【B】 22、设M={x|f1(x)=0},N={x|f2(x)=0}，则方程f1(x)?f2(x)=0的解 《离散数学》试卷（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卷及答案)
离散数学期末试卷及答案
离散数学考试试题(A、B卷及答案)
离散数学试卷及答案
离散数学期末考试试卷(A卷)
《离散数学》练习题和参考答案
离散数学试卷及答案(1)
离散数学练习题
离散数学期末试卷A卷及答案