离散数学复习题
一、选择题：
1.下列句子是命题的是( )。
A. 你喜欢我吗?
B. 这里的景色真美啊!
C. 2x = 9。
D. 明年国庆节是晴天。
2.设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为( )。
∧)
A. ?P∧?Q
B. ?(P Q
C. ?(P?Q)
D. ?(?P∨?Q)
3.下列语句不是
．．命题的是( )。
A.黄金是非金属。
B.要是他不上场，我们就不会输。
C.他跑100米只用了10秒钟，你说他是不是运动健将呢?
D.他跑100米只用了10秒钟，他是一个真正的运动健将。
4.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )。
A.P∨Q
B.P∧?Q
C.P→?Q
D.P∨?Q
5.下列句子不是
．．命题的是( )。
A. 做人真难啊!
B. 后天是阴天。
C. 2是偶数。
D. 地球是方的。
6.在命题演算中，语句为真为假的一种性质称为( )。
A. 真值
B. 陈述句
C. 命题
D. 谓词
7.命题公式?(P∧Q)→R的成真指派是( )。
A. 000，001，110
B. 001，011，101，110，111
C. 全体指派
D. 无
8.下列命题中，不正确的是( )。
∈?,{{?}}}
A.{?}{
∈?,{?}} B.{?}{
C.{?}?{?,{?}}
D. ??{?,{?}}
9.命题公式P∧(Q∨? R)的成真指派是( )。
A.110，111，100
B.110，101，011
C.所有指派
D.无
∨?( )。
10.设P,Q,R是命题公式,则P→R，Q→R，P Q
A. P
B. Q
C. R
D. ?R
11.下列是两个命题变元p，q的小项是( )
∨C．?p q
∨∨
∧D．?p p q
A．p∧?p q
∧B．?p q
12.关于命题变元P和Q的大项M01表示( )。
∨ C.P∨?Q D.P∧?Q
∧ B.?P Q
A.?P Q
13.设P：明天天晴；q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为( )
?p→?q C. ?p??q D. ?p→q
A. p→?q
B.
14.下列命题公式是永真式的是( )
(p→q)∨q D. (p∨p)∧(p→?p)
?(p→q)∧q C.
A. (p∧?p)?q
B.
15.数理逻辑是采用()研究抽象思维规律的一门科学。
A.数学方法
B.逻辑方法
C.实践方法
D.抽象方法
16.下列式子正确的是()
A. p→q ? q→p
B. p→q ??p∨q
C. p→q ??q∨p
D. p→q ??q∨?p
17.下列含有命题p，q，r的公式中，是主析取范式的是()
A. (p∧q∧r)∨(?p∧q)
B. (p∨q∨r)∧(?p∧q)
(p∧q∧r)∨(?p∧?q∧r)
C. (p∨q∨r)∧(?p∨?q∨r)
D.
18.下列命题公式为重言式的是( )
∨B．q∧?q C．(p∨?p)→q D．p→?q
A．p→ (p q)
19.设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是( )
∧B．?p→q C．?p→?q D．p→?q
A．?p q
20.设论域为{a, b}，与公式(?x)A(x)等价的是( )。
A. A(a)∨A(b)
B. A(a)∧A(b)
C. A(a)
D. A(b)→A(a)
21.设论域为{l，2}，与公式(?x)A(x)等价的是( )。
A. A(1)∨A(2)
B. A(1)∧A(2)
C. A(1)
D. A(2)→ A(1)
22.设M(x)：x是人；F(x)：x要吃饭。用谓词公式表达下述命题：所有的人都要吃饭，其中错
误的表达式是( )。
A. M (x)∨F (x)
B. M (x)∧F (x)
C. (?x)( M (x)→F (x))
(?x)( M (x)∧F (x))
D.
23.在论域D={a,b}中与公式(?x)A(x)等价的不含存在量词的公式是( )。
A. A(a)∧A(b)
B. A(a)∨A(b)
C. A(a)→A(b)
D. A(b)→A(a)
24.设论域为整数集，下列真值为真的公式是( )。
A．(?x)(?y)(x – y = 0) B．(?y)(?x)(x – y = 0)
C．(?x)(?y)(x – y = 0) D．?(?x)?(?y)(x – y = 0)
25.设R(x)：x是实数；S(x,y)：x小于y。用谓词表达下述命题：不存在最小的实数。其中错
误的表达式是：( )。
A. (?x)(R(x)→(?y)(R(y)∧S(y, x)))
B. ?(?x)(R(x)→(?y)(R(y)∧S(x, y)))
C. (?x)(R(x)∧(?y)(?R(y)∨?S(x, y)))
D. (?x)(R(x)→(?y)(R(y)→S(y, x)))
26.设A(x): x是鸟，B(x): x会飞，命题“有的鸟不会飞”符号化为( )。
A. ?(?x)(A(x)∧B(x))
B. ?(?x)(A(x)∧B(x))
?(?x)(A(x)→B(x))
C. ?(?x)(A(x)→B(x))
D.
27.下列哪个式子不是谓词演算的合式公式( )
∧
A. (?x)(A(x,2)B(y))
∧ B. (?x)(A(x)B(x,y))
C. ((?x)(∧?y))→(A(x,y)B(x,y))∧
D. (?x)(A(x)→B(y)) 28. 设个体域为整数集,则下列公式中值为真的是( )。
A. (?y)(?x)(x·y =2)
B. (?x)(?y)(x·y=2)
C. (?x)(x·y =x)
D. (?x)(?y)(x+y=2y) 29. 下列等值式不正确的是( )
A ．?(?x)A ?(?x)?A
B ．(?x)(B →A(x))?B →(?x)A(x)
C ．(?x)(A(x)B(x))∧?(?x)A(x)(∧?x)B(x)
D ．(?x)(?y)(A(x)→B(y))?(?x)A(x)→(?y)B(y)
30. 谓词公式(?x)P(x,y)(∧?x)(Q(x,z)→(?x)(?y)R(x,y,z)中量词?x 的辖域是( )
A ．(?x)Q(x,z)→(?x)(?y)R(x,y,z))
B ．Q(x,z)→(?y)R(x,y,z)
C ．Q(x,z)→(?x)(?y)R(x,y,z)
D ．Q(x,z)
31. 利用谓词的约束变元改名规则和自由变元代入规则，可将如下公式：
(?x)(p(x, y)→(?z)Q(x, z))∧(?y)R(x, y)改写成( ) A. (?z)(p(z, y)→(?y)Q(z, y))∧(?s)R(z, s) B. (?z)(p(z, y)→(?s)Q(x,s))∧(?y)R(z, y) C. (?x)(p(x, m)→(?y)Q(x, y))∧(?m)R(m, m) D. (?x)(p(y, y)→(?y)Q(x, y))∧(?s)R(y, s)
32. 对于公式(?x)(?y)P(x ，y)Q(x ∨，z)(∧?x)P(x ，y)，下列说法正确的是( )
A.x 是自由变元
B.x 是约束变元
C.(?x)的辖域是P(x ，y)Q(x ∨，z)
D.(?x)的辖域是P(x ，y) 33. 下列关系矩阵所对应的关系具有反对称性的是( )。
A ．
B ．
C ．
D ．
??????????001110101??????????101110001????
?
?????001100100????
?
?????00101010134. 设集合A ={a , b , c }，集合B ={a , b , c , d }，则│A ×B │等于( )。
A. 7
B. 12
C. 81
D. 64 35. 集合{1, 2, 3}上共有( )个不同的等价关系。
A. 8
B. 7
C. 6
D. 5
36. 设A ={1，2，3，4，5}，A 上二元关系R ={<1,2>, <3,4>, <2,2>}，S ={<2,4>, <3,1>, <4,2>}，则
S -1?R -1的运算结果是( )。
A ．{<4,1>，<2,3>，<2,4>}
B ．{<2,4>，<2,3>，<4,2>}
C ．{<4,1>，<2,3>，<4,2>}
D ．{<2,2>，<3,1>，<4,4>} 37. 集合的以下运算律不成立．．．
的是( )。 A. A ∩B =B ∩A B. A ∪B =B ∪A C. A ⊕B =B ⊕A D. A - B =B - A 38. 设有A ={a,b,c }上的关系R ={
A. 自反性
B. 反对称性
C. 传递性
D. 以上答案都正确
39. 设X ={a , b , c },I X 是X 上恒等关系，要使I X {∪，，
系，R 应取( )。
A. {
B.{
C. {
D.{，
。
A.自反性
B.对称性
C.传递性
D.反自反性
41. 设A ={a ,b ,c }，A 上二元关系R ={, , }，则关系R 的对称
闭包s (R )是( )。 A. R ∪I A B. R C. R ∪{
A.3个
B.6个
C.8个
D.9个
43. 设A ={1，2，3，4 }，A 上二元关系R ={<1,2>, <3,4>, <2,2>}，S ={<2,4>, <3,1>, <4,2>}，则S ?R -1
的运算结果是( )。
A ．{<4,1>, <2,3>, <4,2>}
B ．{<2,3>, <3,2>, <4,1>, <4,2>}
C ．{<4,1>, <2,3>, <2,4>}
D ．{<1,1>, <2,2>, <3,3>, <4,4>} 44. 设A={a,b,c}，则下列是集合A 的划分的是( )。
A.{{b,c},{c}}
B.{{a,b},{a,c}}
C.{{a,b},c}
D.{{a},{b,c}}
45. 设集合A ={a, b, c }上的关系如下，具有传递性的是( )。
A.R ={
B.R ={
C.R ={
D.R ={
46. 集合{1, 2, 3, 4}上的偏序关系如下列四个关系图所示，其中属于全序关系的是( )。
47. 下列式子正确的是( )
A. ?∈?
B. ???
C.{?}??
D.{?}∈? 48. 设A={a,b,c},则A×A 中的元素有( )。
A.3个
B.6个
C.8个
D.9个
49. 设A={a,b,c,d}，A 上的等价关系R={
分是( )
A ．{{a},{b,c},{d}}
B ．{{a,b},{c},{d}}
C ．{{a},{b},{c},{d}}
D ．{{a,b},{c,d}}
50. 设X ，Y ，Z 是集合，一是集合相对补运算，下列等式不正确的是( )
A ．(X-Y)-Z=X-(Y ∩Z)
B ．(X-Y)-Z=(X-Z)-Y
C ．(X-Y)-Z =(X-Z)-(Y-Z)
D ．(X-Y)-Z=X-(Y Z)∪
C
B
A
图1
51. 设A={a,{a}}，p(A)为A 的幂集，则下列各式正确的是( )。
A.{a}p(A)∈
B.{a}?p(A)
C.{{a}}?p(A)
D.{a,{a}}?p(A)
52. 设A ∩B=B,则有( )
A. A B=∪ A
B. A – B = ?
C. A B=B ∪
D. A ? B 53. 设R 为实数集，函数f ：R →R ，f(x)=2x ，则f 是( )
A ．满射函数
B ．入射函数
C ．双射函数
D ．非入射非满射
54. 设A ={1, 2, 3}，B ={a , b }，下列二元关系R 为A 到B 的函数的是( )。
A. R ={<1, a >, <2, a >, <3, a >}
B. R ={<1, a >, <1, b >, <2, a >, <3, a >}
C. R ={<1, a >, <2, b >}
D. R ={<1, b >, <2, a >, <3, b >, <1, a >} 55. 设N 为自然数集(含0)，函数f ：N →N ×N , f (n )=
A.满射，不是入射
B.入射，不是满射
C.双射
D.不是入射，不是满射 56. 设A ={a ,b ,c },则A →A 的双射共有( )。
A.3个
B.6个
C.8个
D.9个 57. 设N 是自然数集，R 是实数集，函数f ：Ｎ→R ，f (n)=lg n 是( )。
A.入射
B.满射
C.双射
D.非以上三种的一般函数
58. 设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 >} 59. 如右图2的最大入度是( )。
A. 0
B. 1
C. 2
D. 3 60. 设有一个无向连通图，共有6个结点、且每个结点的度均为2，则它的边数为( )。 A. 5
B. 6
C. 7
D. 8
61. 下列可一笔画成的图形是( )。
A B C D 62. 设图G ′=
A. V ′≠V 但E ′=E
B. V ′=V
C. E ′=E
D. E ′≠E 且V ′≠V 63. 在有3个结点的图中，度为奇数的结点个数为( )。
A. 0
B. 1
C. 1或3
D. 0或2
图2
64. 下列图是欧拉图的是( )。
A B C D 65. 给定n 个结点的一个图，它还是一个树的下列说法中，( )是不对．．
的。 A.无回路的连通图
B.无回路但若增加一条新边就会变成回路
C.所有结点的度数≥2
D.连通且e =v -1，其中e 是边数，v 是结点数
66. 下列各有向图是强连通图的是( )。
A B C D 67. 在有n 个结点的连通图中，其边数( )。
A ．最多有n -1条
B ．至少有n -1条
C ．最多有n 条
D ．至少有n 条
68. 下列是．
树的是( )。
69. 70. 71. A ． B ． C ． D ．
72. 设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点
数是( )。
A ．3
B ．4
C ．5
D ．6
73. 无向图G 中有16条边，且每个结点的度数均为2，则结点数是( )
A.8
B.16
C.4
D.32
b d f
74.下列各图不是欧拉图的是( )
A B C D
75.设有向图G有5个结点，4条边，且有一条有向路经过每个结点一次，则图G满足的最大
连通性是( )。
A.不连通
B.弱连通
C.单侧连通
D.强连通
76.下列各图是平面图的是( )
A B C D
77.下列各图是无向完全图的是()
A B C D
78.设G是具有n个结点的无向简单图，若在G中存在一条汉密尔顿路，则G中每一对结点
的度数之和与n-1的关系为()
A．大于B．大于等于C．等于D．小于
79.设连通平面图G，共有n个结点，e条边，r个面，则欧拉证明成立的公式是()
A．e-n+r 2 B．n+r-e= 2 C．n-r+e 2 D．n-e-r=2
80.设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点
数是()
A．3 B．4 C．5 D．6
二、简答题、计算题：
1.试构造命题公式(P→ (Q∧R)) →?P的真值表。
2.试把原子命题表示为P, Q, R等，然后用符号译出下列各句子。a)或者你没有给我写信，或
者它在途中丢失了。b)如果张三和李四都不去，他就去。c)我们不能既划船又跑步。d)如果你来了，那么他唱不唱歌将看你是否伴奏而定。
3.求下列各复合命题的真值表: a) (P∨Q)?(Q∨P)；b) (P→(Q→R))→((P→Q)→ (P→R))。
4.化简以下各式：a) ((A→B)?(?B→?A))∧C；b) A∨(?A∨(B∧?B))。
c) (A∧B∧C)∨(?A∧B∧C)。
5.用真值表法求?(P→Q)?(P→?Q)的主析取范式。
6.用等值演算法求?(P→Q)?(P→?Q)的主合取范式。
7.求(P→Q)→R的主析取范式。
8.利用真值表判断公式((?P∨Q)∧(Q→R)) →? (P∧?R)是否为重言式。
9.分别用真值表法与等值演算法判断这两个公式是否等价：?(A?B)，(A∧?B)∨(?A∧B)。
10.利用谓词符号化句子：“并不是所有的大学生都是共产党员”。
11.求公式?((?x)F(x,y)→(?y)G(x,y))∨(?x)H(x)的前束范式。
12.给定个体域D={a,b},F(a,b)=1,F(a,b)=0,F(b,a)=0,F(b,b)=1,试求(?x)(?y)F(x,y)的真值。
13.用谓词逻辑将命题符号化：有些运动员只钦佩某些教练。
14.如果论域是集合{a,b,c}，试消去给定公式中的量词：(?y)(?x)(x+y=0)。
15.确定下列集合的幂集：a) {a, {a}}；b) {{1, {2,3}}}；c) {?, a, {b}}；d) ?(?)；e) ?(?(?))。
16.设A={0,1}, B={1,2}, 确定下列集合：a) A×{1}×B；b) (B×A)2。
17.对{0, 1, 2, 3, 4, 5, 6}上的二元关系R={ 18.设集合A={a, b, c, d}，A上的关系R={ 法求出R的自反闭包、对称闭包和传递闭包。 19.设集合为{3, 5, 15}，{1, 2, 3, 6, 12}，{3, 9, 27, 54}，偏序关系为整除，画出这些集合的偏序 关系图，并指出哪些是全序关系。 20.在偏序集 16, 24, 32, 36}的极大元，极小元，最大元，最小元，上确界和下确界。 21.设A={1,2,3,4}，给定A上二元关系R={<1,2>, <1,3>, <2,3>,<3,4>}，求r(R), s(R)。 22.若集合A={{1,{2,3}}, {2}}的幂集为P(A)，集合B={{?,2},{2}}的幂集为P(B)，求P(A)∩P(B)。 23.对于集合A，设|A|=3，共有多少种不同的划分?试举例说明。 24.设有集合A={a,b,c,d}，B={2,3,4}，C={x,y,z}。A到B的关系ρ1 = {< a,2>, B到C的关系ρ2 = {<2,x>,<3,y>,<4,x>,<4,z>}，设ρ3=ρ2-1?ρ1-1，求ρ3。 25.设A＝{2, 4, 8, 16, 24, 32, 36, 40, 48}，R为A上整除关系，试画 26.设集合A={1,2,3}上的二元关系R={<1,2>,<2,3>,<3,1>}求关系R的关系图，并判断R的性 质(自反性、反自反性、对称性、反对称性、传递性)。 27.设集合P={x1, x2, x3, x4, x5}上的偏序关系如右图所示，找出P中的最 大元素，最小元素，极大元素，极小元素。找出子集{x2, x3, x4}，{x3, x4, x5}和{x1, x2, x3}的上界、下界、上确界、下确界。 x1 x2x3 x4x5 28.设A、B是两个集合，|A|=2, |B|=3。由A→B能生成多少个不同的函数?由B→A能生成多 少个不同的函数? 29.假设有一台计算机，它有一条加法指令，可计算3个数之和。如果要求9个数x1, x2,…, x9之 和，问至少要执行几次加法指令? 30.确定n取怎样的值，完全图K n定有一条欧拉回路。请说明理由。 31.试画出结点数为4的: (1)强连通图；(2)单向连通图；(3)弱连通图；(4)非连通图。 32.一棵树有5个结点度数为2，2个结点度数为3，1个结点度数为4，问它有几个叶子结点， 并给出求解过程。 33.一棵4叉树有2个4度结点，3个3度结点，其余结点是叶子，求该树的叶子数。 34.给定的一个有权图G= 35.给定一组权值，利用哈夫曼算法构造一棵最优二叉树。 1.用真值表法证明：?(A?B) ? (A∧?B)∨(?A∧B)。 2.用真值表法证明：﹁A∧(A∨B)∧(B→C)?C 3.用等值演算法证明(P→Q)→(Q∨R)?P∨Q∨R。 4.用推理方法证明： 前提：P∨Q，P→R，Q→S 结论：R∨S。 5.在个体域D={a1,a2,…，a n}中证明等价式：(?x)(A(x)→B(x))? (?x)A(x)→(? x)B(x) 6.设A，B，C是三个命题，构造下列推理证明： 前提：A∨B，B→C，﹁A 结论：C 7.证明(P∨﹁P)→((Q∧﹁Q)∧R)是矛盾式。 8.证明(?x)(P(x)→Q(x)) ? (?x)P(x)→(?x)Q(x) 9.利用推理规则证明 (?x)(M(x)→D(x)),(?x)(S(x)∧M(x))(?x)(D(x)∧S(x)) ? 10.设关系R与关系S均为集合A上的自反、对称且可传递的关系，证明：R∩S也是A上的 自反、对称且可传递的关系。 11.设{A1, A2, ... , A k}是集合A的一个划分，我们定义A上的一个二元关系R，使 当a和b在这个划分的同一块中，证明：R是自反的、对称的、可传递的。 12.设R1，R2为集合A中的两个等价关系，且R1?R2=R2?R1，试证R1?R2也是A上的等价关系。 13.设R是A上的自反和传递关系，如下定义A上的关系T，使得?x, y∈A， 14.证明：若X×X=Y×Y，则X=Y。 15.对于不含0的自然数集合N。证明N上的整除关系‘|’是一个偏序关系。 16.设R是集合X上的二元关系，证明R是X上传递关系当且仅当R?R?R。 17.设R是A上的一个自反关系，证明：R是一个等价关系，当且仅当若 则 18.R是集合A上自反和传递的关系，试证明：R?R=R。 19.设一个简单图G有21个结点，191条边。证明：G是连通的。 20.证明：在完全m叉树中，边的总数等于(n t-1)m/(m-1)，式中n t是树叶数。 21.证明：一个图是强连通的，当且仅当图中有一个回路，它至少包含每个结点一次。 22.设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3。 23.设图G有n个结点，2n条边，且存在度数为3的结点。证明：G中至少有一个结点度数≥5。 24.设T是非平凡的无向树，T中度数最大的顶点有2个，它们的度数为k(k≥2),证明T中至 少有2k-2片树叶。 25.设具有n个结点的无向树G= 1.某科研所有六名青年高级工程师A，B，C，D，E，F。所里要选派他们中的4人出国进修， 由于所里工作的需要，选派时必须满足以下条件： ①若A去，则B不去或C也去； ②若C和D都去，则E也一定去； ③若D没去或者E去了，则F一定去。 问所里应如何选派他们? 2.构造下面推理的证明。 只要A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。A曾到过受害者房间。如果在11点以前离开，看门人会看见他。看门人没有看见他。所以A犯了谋杀罪。 3.构造下面推理的证明：如果他是计算机专业学生，他必修离散数学。如果他不是工商管理 专业学生，他必是计算机专业的学生。他没修离散数学。所以他是工商管理专业的学生。 4.对下面推理进行符号化，并作证明。会操作计算机的人都认识26个英文字母。文盲都不认 识26个英文字母。有的文盲是很聪明的。所以有的很聪明的人不会操作计算机。(个体域：所有人的集合) 5.符号化下面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的。 6.右图是一幢房子的平面图形，前门进入一个客厅，由客 厅通向4个房间。如果要求每扇门只能进出一次，现在 你由前门进去，能否通过所有的门走遍所有的房间和客 厅，然后从后门走出，并说明理由。 7.设有a,b,c,d,e,f,g等七个人，已知a会讲英语；b会讲英 语、汉语；c会讲英、俄语；d会讲日、汉语；e会讲德 语、俄语；f会讲法语、日语；g会讲法语、德语。试用 图论方法安排园桌座位，使每人都能与其身边的人交谈。 8.某发电厂a要向b,c,d,e四个地点送电，已知发电厂可以和b,c,d直接架接电线，地点e可 以和b与d直接架设电线，其他由于地理原因无法直接架设电线，在a,b,c,d和e之间架设电线时不能有回路存在，否则会造成浪费。请找出所有电线架设方案，使从a可向b，c，d，e供电。 9.设有一群人，人数为6，试证明：在这6人中，一定存在其中有3人是互相认识的或者是 互相不认识的。 10.对右图，利用克鲁斯卡尔算法构造它的一棵最小生成树。 并给出构造过程。 离散数学试题（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 ＝{，，，，，，，， 离散数学考试（试题及答案） 一、（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分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分） 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D (7) R∨S 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明（1）?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍 证明设 1 a，2a，…，1+m a为任取的m＋1个整数，用m去除它们所得余数 只能是0，1，…，m－1，由抽屉原理可知， 1 a，2a，…，1+m a这m＋1个整 数中至少存在两个数 s a和t a，它们被m除所得余数相同，因此s a和t a的差是m的整数倍。 五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分）证明∵x∈ A-（B∪C）? x∈ A∧x?（B∪C）? x∈ A∧（x?B∧x?C）?（x∈ A∧x?B）∧（x∈ A∧x?C）? x∈（A-B）∧x∈（A-C）? x∈（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C） 六、已知R、S是N上的关系，其定义如下：R={ 试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 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、下面偏序集( )能构成格。 离散数学期末试题及答 案 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 离散数学模拟试题Ⅰ 一、单项选择题(本大题共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 ,则有向图 >= 离散数学考试题(后附详细答案) 一、命题符号化（共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分） 《离散数学》期末考试题(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.整环不一定是域. ( ) 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 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个 离散数学考试试题（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?{ 离散数学试题(Ｂ卷答案１） 一、证明题(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={ 《离散数学》模拟试题 一、 填空题（每小题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 →∧?=)( 填空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) 离散数学试题(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 离散数学考试试题(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 离散数学期末考试试卷(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分）(完整版)离散数学试卷及答案
离散数学模拟题一套及答案
离散数学期末考试试题(有几套带答案)
离散数学试题与答案
离散数学期末试题及答案完整版
离散数学模拟试题讲解
离散数学考试题详细答案
【浙江工商大学】《离散数学》期末考试题(B)
离散数学模拟试卷和答案
离散数学考试试题(A卷及答案)
离散数学期末试卷及答案
离散数学期末考试试题及答案
离散数学模拟试题及答案
离散数学试卷及答案
离散数学期末考试试题及答案
离散数学考试试题(A、B卷及答案)
离散数学期末考试试卷(A卷)
- 最新离散数学期末练习题 (带答案)
- 离散数学期末复习试题及答案(一)
- 离散数学期末考试题(附答案和含解析1)
- 离散数学期末复习试题及答案
- 离散数学期末复习题
- 淮海工学院 离散数学期末复习题答案
- 《离散数学》期末复习题答案_80011521535014977
- 离散数学本科期末复习题
- 离散数学期末考试题(附答案和含解析3)
- 离散数学期末考试题
- 离散数学期末练习题-(带标准答案)
- 离散数学期末试题
- 离散数学期末复习题
- 《离散数学》期末复习题答案
- 离散数学期末考试题答案
- 中国石油大学大学《离散数学》期末复习题及答案
- 离散数学期末练习题-(带答案)
- 【浙江工商大学】《离散数学》期末考试题(A)
- 最新离散数学期末练习题-(带答案)
- 离散数学期末复习试题及答案(六)