第一套题
一、填空题
1设集合A,B，其中A＝{1,2,3}, B= {1,2},
则A - B＝____________________;
ρ(A) - ρ(B)＝_________________ .
答案：{3};
{{3},{1,3},{2,3},{1,2,3}}.
2. 设有限集合A, |A| = n,
则|ρ(A×A)| = ____________.
答案：2
2n.
3. 已知命题公式G＝?(P→Q)∧R，
则G的主析取范式是____________.
答案：(P∧?Q∧R).
4. 设A、B为两个集合, A= {1,2,4}, B = {3,4},
则从A?B＝_____;
A?B＝_____;
A－B＝_____.
5. 设R是集合A上的等价关系，
则R所具有的关系的三个特性是______, ________, ________.
6. 设集合A＝{1,2,3,4}, A上的关系
R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)},
则R1?R2=________；
R2?R1 =________；
R12=___________.
7. 设有限集A, B，|A| = m, |B| = n,
则| |ρ(A?B)| = ___________.
8.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，
则R以集合形式(列举法)记为______________.
9. 设G 是具有8个顶点的树，
则G 中增加_________条边才能把G 变成完全图。
10. 设谓词的定义域为{a , b },将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是_____________.
11. 设集合A ＝{1, 2, 3, 4}，A 上的二元关系
R ＝{(1,1),(1,2),(2,3)},
S ＝{(1,3),(2,3),(3,2)}。
则R ?S ＝_____________,
R 2＝_________________.
12、使命题公式P → (P →Q)成假的赋值是 。
13、n 个顶点的无向完全图的边数一定是 。
14、设N (x )：x 是自然数，Z (y )；y 是整数，
则命题“一切自然数都是整数，
而有的整数不是自然数”符号化为 。
15、命题公式A 含3个命题变元P ，Q ，R ，
其成真赋值为000，010，100，110，
A 的主析取范式为 。
16、若G 为连通的平面图，有a 个顶点，b 个面，
则G 的边数是 。
17、连通无向图G 有6个顶点10条边，要得到G 的一棵生成树，必须删去 条边。
18、若集合A 上的二元关系R 的关系矩阵主对角线上元素全是1，则关系R 具有 性质。
19、无向完全图K 3的不同构的生成子图的个数为 。
20、已知有向图G 的邻接矩阵为???????? ??0111110101110001000
111010，则G 的边数是 。
21、P({a, {b, c}}) = _____________________
22、设个体域为整数域，命题?x ?y(x - y = 1)的真值为 。
23、设p: 小李努力学习，q: 小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为 ________________。
24、若G 为连通的平面图，有n 个顶点，k 个面，则G 的边数为 。
25、设A ＝{1,2},B={x,y}, 则A ×B= 。
26、集合},{b a A =的幂集=)(A ρ 。
27、设)(x F 表示“x 会飞”，论述域为{鸟}，则命题“一切鸟都会飞”可译
为：。
28、若集合A上的二元关系R的关系矩阵主对角线上元素全是1，则关系R具有性质。
29、公式R
∨)
(的对偶公式为。
P→
Q
30、连通无向图G有9个顶点14条边，要得到G的一棵生成树，必须删去条
边。
二、选择题
1设集合A={2,{a},3,4}，B = {{a},3,4,1}，E为全集，
则下列命题正确的是( )。
(A){2}∈A (B){a}?A (C)??{{a}}?B?E (D){{a},1,3,4}?B.
2设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，
则R不具备( ).
(A)自反性(B)传递性(C)对称性(D)反对称性
3 设半序集(A,≤)关系≤的哈斯图如下所示，若A的子集
B = {2,3,4,5},则元素6为B的( )。
(D)以上答案都不对
4下列语句中，( )是命题。
(A)请把门关上(B)地球外的星球上也有人
(C)x + 5 > 6 (D)下午有会吗？
5.
的是( ).
(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).
6设命题公式G＝?(P→Q)，H＝P→(Q→?P)，
则G与H的关系是( )。
(A)G?H (B)H?G
(C)G＝H (D)以上都不是.
7 设A, B为集合，当( )时A－B＝B.
(A)A＝B (B)A?B (C)B?A (D)A＝B＝?.
8 设集合A = {1,2,3,4}, A上的关系R＝{(1,1),(2,3),(2,4),(3,4)},
则R具有( )。
(A)自反性(B)传递性(C)对称性(D)以上答案都不对
9下列关于集合的表示中正确的为( )。
（A){a}∈{a,b,c} (B){a}?{a,b,c}
(C)?∈{a,b,c} (D){a,b}∈{a,b,c}
10命题?xG(x)取真值1的充分必要条件是( ).
(A)对任意x，G(x)都取真值1.
(B)(B)有一个x0，使G(x0)取真值1.
(C)有某些x，使G(x0)取真值1.
(D)以上答案都不对.
11. 设G是连通平面图，有5个顶点，6个面，则G的边数是( ).
(A) 9条 (B) 5条 (C) 6条 (D) 11条.
12. 设G 是5个顶点的完全图，则从G 中删去( )条边可以得到树.
(A)6 (B)5 (C)10 (D)4.
13. 设图G 的相邻矩阵为???????
?????????0110110101
110110*********，则G 的顶点数与边数分别为( ). (A)4, 5 (B)5, 6 (C)4, 10 (D)5, 8.
第二套
1、下列数列中哪个可以成为无向树的度序列？( )
A 、 1,1,1,1,2；
B 、 1,1,1,3,3；
C 、 1,1,1,2,2,3；
D 、 1,1,3,3,4
2、下列命题错误的是( )
A 、? ? ?
B 、? ∈ ?
C 、? ? {?}
D 、? ∈ {?}
3、判断下列为双射函数的是( )
A 、f ：N →N ，f (x ) = x 2 ＋ 1
B 、f ：Z →Z ， f (x ) = x mod 3
C 、f ：N →N ， 为偶数
若为奇数若x x x f ???=01)( D 、f ：R →R ，f (x ) = x 3
4、公式（p ? q ）∧┐p 的成真赋值是（）
A 、00
B 、 01
C 、 10
D 、 11
5、公式?x(F(x) → (F(x) ∨ G(x)))是（）；
A ． 永真式
B 、永假式
C 、非永真式的可满足式
D 、不能确定
6、A = {1, 2, 3, 4, 5, 6, 7}，R 是A 上的模3等价关系，则A / R = ()
A 、{{1, 2, 3}, {4, 5}, {6, 7}}
B 、{{1, 4, 7}, {2, 5}, {3, 6}}
C 、{{1, 4, 7}, {1, 5}, {1, 7}}
D 、{{1, 4, 7}, {2, 5}, {0, 3, 6}}
第三套题
1、选择题：
① 命题公式)∨(→P P Q ?是( )。
(A) 矛盾式 (B) 重言式
(C) 非永真的可满足式 (D) 以上都不对
② 设个体域为全体自然数集合，下列公式中真值为T 是( )。
(A) )(??0=+y x y x (B) )(??0=+y x y x
(C) )(??0=+y x y x (D) )(?y ?0=+y x x
③谓词公式),(∨)),(?→),(?(?y x A y x yR y x xQ P x ∧(x)，以下陈述错误的是（ ）
。 (A) ?x 的辖域是),(),()(y x yR y x xQ x P ?→?∧
(B) ?x 的辖域是Q (x ,y )
(C) R (x ,y )中的x 是自由出现
(D)此公式等值于 ),(∨)),(?→),(?∧)((?y x A y z yR y x xQ z P z
④ 设A ,B ,C 为任意集合,下列表达正确的是()。
(A) ??? (B) A －B ＝? ? A ＝B
(C)A ?B ＝A ?C ? B ＝C (D) A ?B ＝A ? A ?B=A
⑤ 设A ＝{1,2},B={a,d,c},C={c,d}, 则(B －C)×A= ( )。
(A){<1,a>,<2,a>} (B){
(C){
⑦设N 是自然数集合，则下列四个陈述不对是( )。
(A) ≤是N 上的偏序关系 (B) =不是N 上的等价关系
(C) ≥是N 上的偏序关系 (D) ≤是N 上的线序关系
⑩下面四个图中，哪个是欧拉图( )。
2、求下图中的最小生成树，其权为多少？
3、将下列句子所表示的复合命题用符号形式写出
（1）这个内容有趣，并且习题很难。
（2）如果这个内容有趣，习题也不难，那么这门课程也让人喜欢。 其中A ：这个内容有趣。B ：这个习题很难。
C ：这门课程让人喜欢。
4、设2)(,:2+=→x x f R R f ， 4)(,:-=→x x g R R g
求（1）g f ?，（2）f g ?
5、设1R 和2R 是集合}4,3,2,1{=A 为上的关系，其中
}3,3,1,3,1,2{},2,4,1,2,2,2{21><><><=><><><=R R
求1R 的值域)(1R S ，1~R ，.21R R
6、求)()(Q P R Q P ?∨∧∨∨的主合取范式.
7、设R A },4,3,2,1{=为A 上的关系，},1,4,2,3,2,2{><><><=R
求),(R r )(R s 。
8、下面给出了有向图的邻接矩阵A ，求出432,,A A A 及可达性矩阵P 。
0101001001000110A ??????=??????
. 9、偏序集R A ,的哈斯图如右： 求（1）A 的极大元素和极小元素， （2）A 的子集B = {2,3,4,5}的上界和下界， 并指出该子集的上确界和下确界，如果它们存在. 10、已知T 是图G 的生成树，
e e
a d a
c g
f h f
b b
G T
1）指出T 的弦及每条弦对应的基本回路和对应T 的基本回路系统
2）指出T 的所有树枝及每条树枝对应的基本割集和对应T 的基本割集系统.
三、判断下述推理是否正确。（本题满分10分）
一个侦探调查了某珠宝店的钻石项链盗窃案后，根据以下事实：
①营业员A或B盗窃了钻石项链。
②若A作案，则作案时间不在营业时间。
③若B提供的证词正确，则货柜未上锁。
④若B提供的证词不正确，则作案发生在营业时间。
⑤货柜上了锁。推断B盗窃了钻石项链。
（其中P：营业员A盗窃了钻石项链。
Q：营业员B盗窃了钻石项链。
R：作案发生在营业时间。
S：B提供的证词正确。
T：货柜上了锁。）
提示：问题转化为：判断Q
→
?
?
?
∨,
→
,
,
→
,
S
R
T
T
S
Q
P
R
P?
第四套题
一、在真命题后的括号内标上T，在假命题后的括号内标上F
ρ。（）
1、`集合}
{{
)
(b
a
A=
b
a
},
a
{b
,
A=的幂集}}
,
{
{
},
2、
K不是平面图. （）5
3、有向树的结点数n和边数m满足关系：1
m. （）
+
=n
4、设A为任意的公式，B为重言式，则B
A∨的类型为重言式. （）
5、如果论述域是整数，则)1
x。（）
(=
?x
6、设1
N
x
f，是单射的。（）→x
N
f
(
)
=
,
2
:+
7、无向图T是树，则T是有简单回路。（）
8、设}3,2,1{
2,1{
},
3,2{
1
=
{{
C，
},
3,2{
A，}}
B，}}
},
=
2,1
=
{{
则B和C都是A的覆盖. （）
二、填空题
1、若G为连通的平面图，有n个顶点，k个面，则G的边为。
2、设A＝{1,2},B={x,y},则AB=。
ρ。
3、集合}
)
(A
A=的=
,
{b
a
4、设)
(x
F表示“x会飞”，论述域为{鸟}，则命题“一切鸟都会飞”可译为：。
5、若集合A上的二元关系R的关系矩阵主对角线上元素全是1，
则关系R具有性质。
6、公式R
∨)
(的对偶公式为。
P→
Q
7、连通无向图G有9个顶点14条边，要得到G的一棵生成树，必须删去条边。
三、简答题
1、画出无向图G 的生成树
e a d c
f h
b
G
2、将R Q P ∨→)(化成仅用┓，∧的等价表达式。
3、下面给出了图G ，其顶点集},,,,{E D C B A V =，试判断图G 的子图中哪些是生成子图 ，由边集导出的子图 ，由结点集导出的子图？
B
A C
E D 图G
B
A C A C
D E D
1G 2G
B B
A C A C
E D D
3G 4G
4、下面给出一个赋权图，用最邻近算法确定一条起始于a 点的哈密尔顿回路。其长度为多少？
a
5 6
3 5
b 2 c
6 3
3 4
d 2 e
5、设},4,3,2,1{=A R 和S 是A 上的二元关系，
}3,3,4,2,3,1{},1,4,2,3,4,2{><><><=><><><=S R ，
求S 的定义域)(S D ，R ~， RS
6、偏序集R A ,的哈斯图如右： a b
d c
e f
求（1）A 的最大元素和最小元素，
（2）A 的子集{c ，e ，f}的上界和下界.
7、求R Q P P A ∨∧→=))((的主合取范式和主析取范式
8、设R 是}4,3,2,1{=A 上的二元关系，R 的关系矩阵为 ?????
???????=001000010010
0101R M ， 试求出（1）)(R r M ，（2）)(R sr M
四、证明下面的结论（要求写出每一步的依据）
（1）前提为：S R R P Q P ?→→??∨?,,，结论为：Q S ?→
（2）前提：)()),()((x xF x G x F x ?→?， 结论：)(x xG ?
五、计算题。
（1）求出下图的邻接矩阵A ，
（2）求出T A ，T AA ，分析T AA 中第（1，4）个元素和第（4，4）个元素的意义.
υ3
（3）求赋权图中的最小生成树,T 并计算出T 的权).(T W
a
5
5
12 b 8 c 14
11 10
9 8
d 9 e
第四套题
1. 设集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R为整除关系。
(1)画出半序集(A,R)的哈斯图；
(2)写出A的子集B = {3,6,9,12}的上界，下界，最小上界，最大下界；
(3)写出A的最大元，最小元，极大元，极小元。
2.设集合A＝{1, 2, 3, 4}，A上的关系R＝{(x,y) | x, y∈A 且x ≥ y}, 求
(1)画出R的关系图；（2）写出R的关系矩阵.
3. 设集合A＝{1, 2, 4, 6, 8, 12}，R为A上整除关系。
（1）画出半序集(A,R)的哈斯图；
（2）写出A的最大元，最小元，极大元，极小元；
（3）写出A的子集B = {4, 6, 8, 12}的上界，下界，最小上界，最大下界.
4. 设命题公式G = ?(P→Q)∨(Q∧(?P→R)), 求G的主析取范式。
5. 设R是集合A = {a, b, c, d}. R是A上的二元关系,
R = {(a,b), (b,a), (b,c), (c,d)},
（1）求出r(R), s(R), t(R)；
（2）画出r(R), s(R), t(R)的关系图.
6. 通过求主析取范式判断下列命题公式是否等价：
(1) G = (P∧Q)∨(?P∧Q∧R)
(2) H = (P∨(Q∧R))∧(Q∨(?P∧R))
7. 设R和S是集合A＝{a, b, c, d}上的关系，其中
R＝{(a, a),(a, c),(b, c),(c, d)},
S＝{(a, b),(b, c),(b, d),(d, d)}.
(1) 试写出R和S的关系矩阵；
(2) 计算R?S, R∪S, R－1, S－1?R－1.
第五套题
1. 证明：{P→Q, R→S, P∨R}蕴涵Q∨S。
2. 证明：{?A∨B, ?C→?B, C→D}蕴涵A→D。
3、设A = ?1, 2, 3, 4?，A 上二元关系R 定义为：R ={<1, 2>, <2, 1>, <2, 3>, <3, 4>} 求：
(1) R 的自反闭包
(2) R 的对称闭包
(3) R 的传递闭包
4、有向图D 如右图所示，求：
(1) v 4到v 3 长度为1, 2的不同路径的条数。
(2) v 3到v 3 长度为4的不同回路的条数。
(3) D 的可达矩阵
5、已知公式：p→(q→r)，求其主析取范式与主合取范式。
6、构造下面推理的证明。
前提：?x(F(x) → (G(x)∧R(x)))，?xF(x)，
结论：?x(F(x) ∧ R(x))。
7构造命题公式))(()(P Q P Q P ∨∧→→的真值表，并判断该公式的类型．
8、求谓词公式)(∨))(→(?4R x Q P x 的真值．
其中P ：4>3，Q(x )：x >1，R (x )：x ≤2，个体域D ={0,4}．
R(4)∨Q(x))→x(P ??R(4)∨Q(4)))→(P ∧Q(0))
→((P ?0?0∨1)→(1∧0)→(1
9、判断下列推理是否正确(先将前提和结论的各命题符号化，然后进行判断，必须构造证明过程)
如果本周是这学期第十九周,则要进行英语或离散数学考试.
如果英语老师去外地开会,则不考英语.
本周是第十九周,英语老师外地有会.所以要进行离散数学考试.
P ：本周是第十九周,
Q ：进行英语考试,
R ：进行离散数学考试,
S ：英语老师外地开会
前提:P →(Q ∨R), S →?Q,P,S 结论:R
10、 设A={a,b,c,d}，A 上的二元关系R={
②求R 的对称闭包s(R)
11、 偏序集
①试写出A 和R 的集合表达式；
②求A 的子集B={b,c,d}的极大元,最大元和上界。
12、 设R 和S 是集合A ＝{1,2,3}上的二元关系， R ＝{<1,2>,<3,1>} S={<1,2>,<2,1>,<3,3>}
求R ?S ，R －S,写出合成关系矩阵M R ?S ．
13、设1R 和2R 是A 上的关系且21R R ?，证明)()(21R r R r ?
14、设1R 和2R 是A 上的关系，证明)()()(2121R r R r R R r =
离散数学试题（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卷)
相关主题
文本预览