离散试卷及答案 离散数学试题(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的整数倍
证明 设a1，a2，…，am?1为任取的m＋1个整数，用m去除它们所得余数只能是0，1，…，m－1，由抽屉原理可知，
a1，a2，…，am?1这m＋1个整数中至少存在两个数as和at，它们被m除所得余数相同，因此as和at的差是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={
解：R={
第 1 页 共 12 页
-1
-1-1
-1
2
2
2
2
-1
离散试卷及答案
证明：因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数（gf）：C→A。同理可推fg：C→A是双射。 因为
R{1,2}={<1,1>,<2,4>}，S[{1,2}]={1,4}。
八、（15分）设
(1)对A中每个元a，有a*a＝a。 (2)对A中任意元a和b，有a*b*a＝a。 (3)对A中任意元a、b和c，有a*b*c＝a*c。 证明 由题意可知，若a*b＝b*a，则必有a＝b。 (1)由(a*a)*a＝a*(a*a)，所以a*a＝a。
(2)由a*(a*b*a)＝(a*a)*(b*a)＝a*b*(a*a)＝(a*b*a)*a，所以有a*b*a＝a。
(3)由(a*c)*(a*b*c)＝(a*c*a)*(b*c)＝a*(b*c)＝(a*b)*c＝(a*b)*(c*a*c)＝(a*b*c)*(a*c)，所以有a*b*c＝a*c。
2九、给定简单无向图G＝
2
-1
-1-1
-1-1
-1
-1
-1
-1
-1-1
若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝
w?V?d(w)＜m＋(m－2)(m－3)＋m＝m－3m＋6，与（1）矛
2
盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m，所以G是哈密尔顿图。
离散数学试题(B卷及答案）
一、证明题（10分）
1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T
证明 左端?((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律) ? ((P∨Q)∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律) ? ((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R)) (等幂律) ?T (代入) 2)?x(P(x)?Q(x))∧?xP(x)??x(P(x)∧Q(x))
证明 ?x(P(x)?Q(x))∧?xP(x)??x((P(x)?Q(x)∧P(x))??x((?P(x)∨Q(x)∧P(x))??x(P(x)∧Q(x))??xP(x)∧?xQ(x)??x(P(x)∧Q(x))
二、求命题公式(?P?Q)?(P∨?Q) 的主析取范式和主合取范式（10分）
解：(?P?Q)?(P∨?Q)??(?P?Q)∨(P∨?Q)??(P∨Q)∨(P∨?Q)?(?P∧?Q)∨(P∨?Q) ?(?P∨P∨?Q)∧(?Q∨P∨?Q)?(P∨?Q)?M1?m0∨m2∨m3 三、推理证明题（10分） 1)(P?(Q?S))∧(?R∨P)∧Q?R?S
证明：（1）R 附加前提 (2)?R∨P P (3)P T(1)(2),I (4)P?(Q?S) P (5)Q?S T(3)(4),I (6)Q P
(7)S T(5)(6),I
(8)R?S CP
2) ?x(P(x)∨Q(x))，?x?P(x)??x Q(x)
证明：(1)?x?P(x) P (2)?P(c) T(1),US (3)?x(P(x)∨Q(x)) P (4)P(c)∨Q(c) T(3),US (5)Q(c) T(2)(4),I (6)?x Q(x) T(5),EG
四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超
第 2 页 共 12 页
离散试卷及答案
过1/8（10分）。
证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。
五、已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) （10分）
证明：∵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）
六、?={A1，A2，…，An}是集合A的一个划分，定义R={
?a,b∈A，若aRb ，则a,b∈Ai，即b,a∈Ai，所以bRa，故R对称。
?a,b,c∈A，若aRb 且bRc，则a,b∈Ai及b,c∈Aj。因为i≠j时Ai∩Aj=?，故i=j，即a,b,c∈Ai，所以aRc，故R传递。 总之R是A上的等价关系。
七、若f:A→B是双射，则f:B→A是双射（15分）。
证明: 对任意的x∈A，因为f是从A到B的函数，故存在y∈B，使
对任意的x∈A，若存在y1,y2∈B，使得
八、设
证明 假设A≠G且B≠G，则存在a?A，a?B，且存在b?B，b?A（否则对任意的a?A，a?B，从而A?B，即A∪B＝B，得B＝G，矛盾。）
对于元素a*b?G，若a*b?A，因A是子群，a?A，从而a * (a*b)＝b ?A，所以矛盾，故a*b?A。同理可证a*b?B，综合有a*b?A∪B＝G。
综上所述，假设不成立，得证A＝G或B＝G。
九、若无向图G是不连通的，证明G的补图G是连通的（10分）。
证明 设无向图G是不连通的，其k个连通分支为G1、G2、…、Gk。任取结点u、v∈G，若u和v不在图G的同一个连通分支中，则[u，v]不是图G的边，因而[u，v]是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支Gi（1≤i≤k）中，在不同于Gi的另一连通分支上取一结点w，则[u，w]和[w，v]都不是图G的边，，因而[u，w]和[w，v]都是G的边。综上可知，不管那种情况，u和v都是可达的。由u和v的任意性可知，G是连通的。
-1
-1
-1
-1
-1
-1
-1
-1
-1
一、 选择题.(每小题2分，总计30) 1. 给定语句如下： （1）15是素数（质数） （2）10能被2整除，3是偶数。
（3）你下午有会吗？若无会，请到我这儿来！ （4）2x+3>0.
（5）只有4是偶数，3才能被2整除。 (6)明年5月1日是晴天。
以上6个语句中，是简单命题的为（A）,是复合命题的为（B）,是真命题的为（C）,是假命题的是（D）,真值待定的命题是（E） A: ①(1)(3)(4)(6) ②(1)(4)(6) ③(1)（6） B: ①(2)(4) ②(2)(4)(6) ③(2)(5) C: ①(1)(2)(5)(6) ②无真命题 ③（5） D: ①(1)(2) ②无假命题 ③(1)(2)(4)(5) E: ①(4)(6) ②（6） ③ 无真值待定的命题 2. 将下列语句符号化：
（1）4是偶数或是奇数。（A）设p：4是偶数，q：4是奇数
第 3 页 共 12 页
离散试卷及答案
（2）只有王荣努力学习，她才能取得好成绩。（B）设p：王荣努力学习，q：王荣取得好成绩 （3）每列火车都比某些汽车快。（C）设F(x):x是火车，G(y):y是汽车，H(x,y):x比y快。 A: ① p∨q ② p∧q ③ p→q B: ① p→q ② q→p ③ p∧q
C: ①?x ?y ((F(x) ∧G(y)) → (H(x,y))②?x (F(x) →?y(G(y)∧H(x,y)))③?x (F(x) ∧?y(G(y)∧H(x,y))) 3. 设S={1,2,3},下图给出了S上的5个关系,则它们只具有以下性质:R1是（A）,R2是(B),R3是(C)。
A B C:①自反的，对称的，传递的 ②反自反的，对称的 ③自反的
④??
反对称的 ⑤对称的 ⑥自反的，对称的，反对称的，传递的
4. 设S={Ф，{1}，{1，2}}，则有
（1）（A）?S （2） (B) ?S
（3） P(S)有（C）个元数。 （4）（D）既是S的元素，又是S的子集 A: ① {1,2} ② 1 B: ③{{1,2}} ④{1} C: ⑤ 3 ⑥ 6 ⑦ 7 ⑧ 8 D: ⑨ {1} ⑩Ф
二、证明（本大题共2小题，第1小题10分，第2小题10分，总计20分） 1、用等值演算算法证明等值式 (p∧q)∨(p∧?q)?p 2、构造下面命题推理的证明
如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。
三、计算（本大题共4小题，第1小题5分，第2小题10分，第3小题15分， 总计30分） 1、设P?x,y?为x整除y，Q?x?为x?2，个体域为?1，2?，求公式： ??x???y??P?x,y??Q?x??的真值。
2、设集合3、设A?A??1,2,3,4?,A上的关系 R??1,1,1,2,2,1,2,3,3,4?，求出它的自反闭包，对称闭包和传递闭包。
?1,2,4,8,12,24,?上的整除关系R??a1,a2a1,a2?A,a1整除a2?，R是否为A上的偏序关系？若是，则：
1、画出R的哈斯图；（10分）
2、求它的极小元，最大元，极大元，最大元。（5分） 四、用推导法求公式答案： 一、 选择题
1. A:③ B: ③ C:③ D:① E:② 2.A:① B: ② C:② 3.A:③ B: ④ C:⑥ 4.A:① B: ③ C:⑧ D:⑩ 二、证明题
1. 证明 左边?（(p∧q)∨p）∧（(p∧q)∨?q)） （分配律） ? p∧（(p∧q)∨?q)） (吸收律) ? p∧（(p∨?q) ∧ (q∨?q)） （分配律） ? p∧（(p∨?q)∧1） （排中律）
??p?q??p?的主析取范式和主合取范式。（本大题10分）
第 4 页 共 12 页
离散试卷及答案
? p∧ (p∨?q) （同一律） ? p （吸收律） 2.解：p：今天是星期三。 q：我有一次英语测验。 r：我有一次数学测验。 s：数学老师有事。
前提：p?(q∨r) , s??r , p∧s 结论：q
证明：①p∧s 前提引入
②p ①化简 ③p?(q∨r) 前提引入 ④q∨r ②③假言推理 ⑤s ①化简 ⑥s??r 前提引入 ⑦?r ⑤⑥假言推理 ⑧q ④⑦析取三段论 推理正确。
三、计算
??x???y??P?x,y??Q?x??1. ???y???P?1,y??Q?1????P?2,y??Q?2????
??P?1,1??Q?1????P?2,1??Q?2??????P?1,2??Q?1????P?2,2??Q?2???
P?1,1??1,P?1,2??1,P?2,1??0,P?2,2??1,Q?1??1,Q?2??0????1?1???0?0?????1?1???1?0???1该公式的真值是1，真命题。
??x???y??P?x,y??Q?x?????x???P?x,1??Q?x????P?x,2??Q?x??????P?1,1??Q?1????P?1,2??Q?1??????P?2,1??Q?2????P?2,2??Q?2???或者
???T?T???T?T?????F?F???T?F????T?T???T?F??T?T?T2、r(R)??1,1,1,2,2,1,2,3,3,4,2,2,3,3,4,4?
s(R)??1,1,1,2,2,1,2,3,3,4,3,2,4,3?
t(R)??1,1,1,2,2,1,2,3,3,4,1,3,2,2,2,4,1,4?
3、（1） R是
A上的偏序关系。
（2）极小元、最小元是1,极大元、 最大元是24。 四、
第 5 页 共 12 页
离散数学期末考试试题(有几套带答案)
