离散数学模拟试卷
篇一：离散数学模拟题及答案
离散数学试题(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={<x,y>| x,y?N∧y=x}，S={<x,y>| x,y?N∧y=x+1}。求R、R*S、S*R、
R{1,2}、S[{1,2}]（10分）
解：R={<y,x>| x,y?N∧y=x}，R*S={<x,y>| x,y?N∧y=x+1}，S*R={<x,y>| x,y?N∧y=（x+1）}， 七、若f:A→B和g:B→C是双射，则（gf）=fg（10分）。
-1
-1-1
-1
2
2
2
2
-1
证明：因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数（gf）：C→A。同理可推fg：C→A是双射。 因为<x,y>∈fg?存在z（<x,z>∈g?<z,y>∈f）?存在z（<y,z>∈f?<z,x>∈g）?<y,x>∈gf?<x,y>∈（gf）,所以（gf）=fg。
R{1,2}={<1,1>,<2,4>}，S[{1,2}]={1,4}。
八、（15分）设<A，*>是半群，对A中任意元a和b，如a≠b必有a*b≠b*a，证明：
(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＝<V，E>，且|V|＝m，|E|＝n。试证：若n≥Cm?1＋2，则G是哈密尔顿图 2证明 若n≥Cm。 ?1＋2，则2n≥m－3m＋6 （1）
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?ST(3)(4),I (6)QP
(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的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超
过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、b∈Ai，I=1，2，…，n}，则R是A上的等价关系（15分）。 证明：?a∈A必有i使得a∈Ai，由定义知aRa，故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,y>∈f，<y,x>∈f。所以,f是满射。
对任意的x∈A，若存在y1,y2∈B，使得<y1,x>∈f且<y2,x>∈f,则有<x,y1>∈f且<x,y2>∈f。因为f是函数，则y1=y2。所以，f是单射。 因此f是双射。
八、设<G，*>是群，<A，*>和<B，*>是<G，*>的子群，证明：若A∪B＝G，则A＝G或B＝G（10分）。
证明 假设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是奇数
（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 ⑧ 8D: ⑨ {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?,,,22,,2,,3,4，求出它的自反闭包，对称闭包和传递闭包。
?1,2,4,8,12,24,?上的整除关系R?a1,a2
a1,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分）
? 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?T
2、r(R)
?,1,,22,2,3,42,23,34,4
s(R)?,,,2,2,,2,3,3,43,24,3
t(R)?,,,22,2,3,,4,,,2,2,2,4,,4
3、（1） R是
A上的偏序关系。
（2）极小元、最小元是1,极大元、 最大元是24。 四、
篇二：离散数学模拟试卷(中文)
目录
离散数学模拟题一 .............................................................................................................................. 1
离散数学模拟题二 .............................................................................................................................. 3
离散数学模拟题三 .............................................................................................................................. 7
离散数学模拟题四 .............................................................................................................................. 9
离散数学模拟题五 ............................................................................................................................ 12
离散数学模拟题六 ............................................................................................................................ 16
离散数学模拟题七 ............................................................................................................................ 18
离散数学模拟题八 ............................................................................................................................ 21
离散数学模拟题九 ............................................................................................................................ 24
离散数学模拟题十 ............................................................................................................................ 25
离散数学模拟题十一 ........................................................................................................................ 27
离散数学模拟题十二 ........................................................................................................................ 33
离散数学模拟题十三 ........................................................................................................................ 34
离散数学模拟题十四 ........................................................................................................................ 37
离散数学模拟题十五 ........................................................................................................................ 42
离散数学模拟题十六 ........................................................................................................................ 50
离散数学模拟题一
一、判断题（共12分，每小题1分）
() 1、（?p??q）?(p??q)不是重言式。
()2、在命题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。
() 3、命题函数是命题。
() 4、设A，B，C是Q的子集，则有A?(B?C)?（A?B）?（A?C）。
()5、设A、B为集合，若B≠Φ，则A-B包含于A。
() 6、若R为集合A上的非对称关系，则R亦然。
()7、存在一种建立在某个集合上的关系，它可以是对称的、反对称的、自反的、反自反和可传递的。
()8、设〈G，?〉是群，对于G中的任意元素a，b有：（a ? b）?1=b?1 ? a?1。
()9、在一个代数系统中，某个元素有多个左逆元，就不可能有右逆元。
()10、设是非连通平面图G的对偶图中的顶点数，边数和面数，则它们之间不满足欧拉公式；
()11、设无向图G具有割点，则G中一定不存在汉密尔顿回路；
()12、有向图G是单侧连通；
（G）
二、求出下列命题公式的主析取范式和主合取范式。（10分）
(P?(Q?R))?(?P?(?Q?R))
三、逻辑推证（10分）
（1）?（P?Q）?? (R?S)，((Q?P) ??R) ，?(R?P) ? P?Q
四、用谓词推理理论来论证下述推证（10分）
任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行 。 2
设M(x):x是人； Q(x)； x喜欢步行
S(x); x喜欢乘汽车 ； R(x)；x喜欢骑自行车
五、某班级有学生四十名，共有三门选修课可供选择，选修课课程名称分别为A、B、C，其中有15名学生选A课程，有10名学生选B课程，6名学生选C课程，而且其中有5名学生三门课程都选。问至少有多少学生三门选修课一门也没选？（10分）
六、设R是一个等价关系，设S?{?a,b?:对某一个c,有?a,c??R,且?c,b??R}，证明：S也是一个等价关系。（10分）
七、 已知有如图的偏序关系，并求出其子集A={b,c, d, e,}的极大元、极小元、最大元、最小元、上确界、下确界。（10分）
f g
八、设G={（a,b）︱a，b∈R，b≠0}，定义运算
（a，b）*(c,d)=(bc+a，bd)
求证：<G，*>是一个群。（10分）
九、求图中A到其余各顶点的最短路径，并写出它们的权。（10分）
6
E 1 F
十、设有一组数1，2，2，3，4，6，7，9，12，求相应的最优树。并写出W（T）。（8分）
离散数学模拟题二
一、判断题（共10分，每小题1分）
() 1、“谋事在人，成事在天。”这句话是命题；
()2、对任意的命题公式A,B,C, 若 A?C?B?C, 则A?B；
() 3、(x)（P(x)→Q(x)）(x)P(x)→(x)Q(x)；
() 4、对于任意集合A，B，A?B当且仅当A?B??；
()5、设x,y是集合A的两种不同划分，则x?y也是集合A的一种划分；
() 6、空集上的空关系，是对称的、反对称的、自反的、反自反和可传递的；
()7、若偏序集〈A，?〉，A中的所有元素都能排成a1? a2? a3? ??的形式，则偏序集〈A，?〉是一个全序集，并只存在一条反链
()8、设（S,*）是一个有单位元的半群，若对任意a∈S，a有左逆元u和右逆元v，则u=v；
()9、非连通平面图G的补图中的顶点数，边数和面数，它们之间不满足欧拉公式；
()10、设有无向图G1,G2，G1是G2的子图，则G1的最小生成树是G2最小生成树的子图。
二、选择题（共16分，每小题2分）
篇三：离散数学模拟试卷
《离散数学》模拟题
一、选择题
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
1．在命题演算中，语句为真为假的一种性质称为 （）
A）真值B）陈述句 C）命题D）谓词
2．下列语句中不是命题的只有 （ ） ．．
A）这个语句是假的。B）1+1=1.0
C）飞碟来自地球外的星球。 D）凡石头都可练成金。
3．下列句子是命题的是 （ ）
A）水开了吗? B）x>1.5
C）再过5000年，地球上就没水了。D）我正在说谎
4．下列语句中为命题的是 （ ）
A）这朵花是谁的？ B）这朵花真美丽啊！
C）这朵花是你的吗？D）这朵花是他的。
5．下列语句中不是命题的只有 （） ．
A）鸡毛也能飞上天？B）或重于泰山，或轻于鸿毛。
C）不经一事，不长一智。 D）牙好，胃口就好。
6．下列语句不是命题的是 （） ．．
A）黄金是非金属。
B）要是他不上场，我们就不会输。
C）他跑100米只用了10秒钟，你说他是不是运动健将呢?
D）他跑100米只用了10秒钟，他是一个真正的运动健将。
7．下列语句中是命题的只有 （）
A）1+1=10 B）x+y=10
C）sinx+siny<0D）x mod 3=2
8．下列是两个命题变元p，q的小项是（）
A）p∧┐p∧qB）┐p∨q C）┐p∧q D）┐p∨p∨q
9．关于命题变元P和Q的大项M01表示 ( )
A）┐P∧Q B）┐P∨Q C）P∨┐Q D）P∧┐Q
10．设P：明天天晴；q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为
()
A）p??q B） ?p??q C） ?p??q ? D） ?p?q
11．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）
A）p→┐qB）p∨┐q C）p∧q D）p∧┐q
12．设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是（ ）
A）┐p∧qB）┐p→q C）┐p→┐qD）p→┐q
13．若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为（ ）
A）P∨Q B）P∧┐Q C）P→┐Q D）P∨┐Q
14．下列命题公式中不是重言式的是 （ ） ．
A）p→(q→r) B）p→(q→p)
C）┐p→(┐p→┐p) D）(p→(q→r))(q→(p→r))
15．下列命题公式为重言式的是（ ）
A）p→ (p∨q)B）(p∨┐p)→qC）q∧┐qD）p→┐q
16．以下命题公式中，为永假式的是（ ）
A）p→(p∨q∨r)B）(p→┐p)→┐p
C）┐(q→q)∧p D）┐(q∨┐p)→(p∧┐p)
17．下列是命题公式p∧(q∨┐r)的成真指派的是（ ）
A）110，111，100 B）110，101，011 C）所有指派 D）无
18．设论域为整数集，下列谓词公式中真值为假的是 ( )
A）(?x)(?y)(x?y?0) B）(?x)(?y)(x?y?1)
C） (?y)(?x)(x?y?x)D） (?x)(?y)(?z)(x?y?z)
19．设个体域是正整数集，则下列公式中真值为真的公式是 （ ）
A）(?x)(?y)(x·y=0)B）(?x)(?y)(x·y=1)
C）(? x)(?y)(x·y=2)D）(?x)(?y)(?z)(x-y=z)
20．设论域为整数集，下列真值为真的公式是（ ）
A）(?x)(?y)(x?y?0) B）(?y)(?x)(x?y?0)
C）(?x)(?y)(x?y?0) D）?(?x)?(?y)(x?y?0)
21．设个体域是整数集，则下列命题的真值为真的是（）
A）yx(x·y=1)B）xy (x·y≠0)
C）xy (x·y=y2)D）yx(x·y=x2)
22．设B是不含变元x的公式，谓词公式(?x)(A(x)→B)等价于（ ）
A）(?x)A(x)→B B）(?x)A(x)→B
C）A(x)→B D）(?x)A(x)→(?x)B
23．下列等值式不正确的是（ ）
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)
24．下列等价式正确的是（ ）
A）┐(?x)A?(?x)┐AB）(?x)(?y)A?(?x)(?y)A
C）┐(?x)A?(?x)┐AD）(?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)
25．下列等价式不成立的是( ) ．．．
A）┐(?x)A(x)?(?x)┐A(x)
B）┐(?x)A(x)?(?x)┐A(x)
C）(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)
D）(?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x)
26．公式(?x)(?y)(P(x,z)→Q(y))S(x,y)中的(?x)的辖域是( )
A）(?y)(P(x,z)→Q(y))B）P(x,z)→Q(y)
C）P(x,z)D）S(x,z)
27．谓词公式(?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)
28．公式(?x)(?y)(P(x,y)∧Q(z))→R(x)中的x( )
A）只是约束变元B）只是自由变元
C）既是约束变元又是自由变元D）既非约束变元又非自由变元
29．在公式(?x)(?y)(P(x,y)?Q(z))?(?y)P(y,z)中变元y是（ ）
A）自由变元 B）约束变元
C）既是自由变元，又是约束变元 D）既不是自由变元，又不是约束变元
30．谓词公式(?x)(P(x,y))→(?z)Q(x,z)∧(?y)R(x,y)中变元x （ ）
A）是自由变元但不是约束变元B）既不是自由变元又不是约束变元
C）既是自由变元又是约束变元D）是约束变元但不是自由变元
31．令F(x):x是金属，G(y):y是液体，H(x,y):x可以溶解在y中，则命题“任何金属可以溶解在某种液体中”可符号化为 （ ）
A）(?x)(F(x)∧(?y)(G(y)∧H(x,y))) B）(?x)(?(x)F(x)→(G(y)→H(x,y)))
C）(?x)(F(x)→(?y)(G(y)∧H(x,y))) D）(?x)(F(x)→(?y)(G(y)→H(x,y))
32．在个体域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)
33．关于谓词公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y)，下面的描述中错误的是 （ ） ．．
A）（x）的辖域是（y）（P（x,y）∧Q(y,z)）B）z是该谓词公式的约束变元
C）（x）的辖域是P（x,y） D）x是该谓词公式的约束变元
34．设论域D={a,b}，与公式xA（x）等价的命题公式是（）
A）A（a）∧A（b） B）A（a）→A（b）
C）A（a）∨A（b） D）A（b）→A（a）
35．设M（x）：x是人；F（x）：x要吃饭。用谓词公式表达下述命题：所有的人都要吃饭，其中错误的表达式是（） ．．
A）(?x)(M(x)?F(x)) B）?(?x)(M(x)??F(x))
C）(?x)(M(x)?F(x)) D）(?x)(?M(x)?F(x))
36．下列公式是前束范式的是（）
A）(?x)(?y)(?F(z,x)?G(y))B）(?(?x)F(x)?(?y)G(y))?H(z)
C）(?x)F(x,y)?(?y)G(y) D）(?x)(F(x,y)?(?y)G(x,y))
37．下列是谓词演算中的合式公式的是（）
A）(?x)(p(x)??y) B）(?x)F(x)?G(x,y)
C）(?x)P(x,y)Q(y,z)D）(?x)?x?P(x,y)
38．下列式子正确的是 （ ）
A）（A－B）-C=A-（B∪C） B）A－（B∪C）=（A－B）∪C
C）~（A－B）=~（B－A） D）~（A∩B）?A
39．下列式子不正确的是（ ）
A）(A-B)-C=(A-C)-B B）(A-B)-C=A-(B∪C)
C）(A-B)-C=(A-C)-(B-C) D）A-(B∪C)=(A-B)∪ C
40．下列式子正确的是（ ）
A） ?∈?B）???C）{?}??D）{?}∈?
41．设A={?}，B=P(P(A))，以下正确的式子是（）
A）{?,{?}}∈B B）{{?,?}}∈B C）{{?},{{?}}}∈B
42．下列命题正确的是（ ） D）{?,{{?}}}∈B
A）{l，2}?{{1，2}，{l，2，3}，1} B）{1，2}?{1，{l，2}，{l，2，3}，2}
C）{1，2}?{{1}，{2}，{1，2}}D）{1，2}∈{1，2，{2}，{l，2，3}}
43．下列命题中，不正确的是（ ）
A）{φ}∈{φ,{φ}} B）{φ}∈{φ,{{φ}}}
C）{φ}?{φ,{φ}} D）φ?{φ,{ φ}}
44．设A={a,{a}}，则下列各式正确的是( )
A）{a}∈p(A)(A的幂集) B）{a}?p(A)
C）{{a}}?p(A)D）{a,{a}}?p(A)
45．设A={?}，B=P（P（A）），以下不正确的式子是 （ ） ．
A）{{? }，{{? }}，{? ，{? }}}包含于B B）{{{? }}}包含于B
C）{{? ，{? }}}包括于B D）{{? }，{{? ，{? }}}}包含于B
46．设φ为空集，P(x)是集合x的幂集，下列论断不正确的是() ．
A） φ∈P(φ), φ?P(φ) B）{φ}∈P（φ），{φ}?P（φ）
C） φ∈P（P（φ）），φ?P（P（φ）） D）{φ}∈P（P（φ））,{φ}?P（P（φ））
47．设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)
48．集合的以下运算律不成立的是 ( ) ．．．
A）A∩B=B∩AB）A∪B=B∪A
C）A?B=B?AD）A-B=B-A
49．设A={a,b,c}，则下列是集合A的划分的是（ ）
A）{{b,c},{c}}B）{{a,b},{a,c}} C）{{a,b},c}D）{{a},{b,c}}
50．设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，则对应于R的A的划分是（ ）
A）{{a},{b,c},{d}}B）{{a,b},{c},{d}}
C）{{a},{b},{c},{d}} D）{{a,b},{c,d}}
51．设R为实数集，函数f：R→R，f(x)=2x，则f是（）
A）满射函数 B）入射函数 C）双射函数D）非入射非满射
52．设N为自然数集(含0)，函数F：N→N×N，F(n)=<n,n+1>是（ ）
A）满射，不是入射 B）入射，不是满射
C）双射 D）不是入射，不是满射
53．设Z是整数集，E={?，-4，-2，0，2，4，?}，f：Z→E，f（x）=2x，则f （ ）
A）仅是满射B）仅是入射 C）是双射D）无逆函数
54．设N是自然数集，R是实数集，函数f：Ｎ→R，f(n)=lgn是 ()
A）入射 B）满射 C）双射 D）非以上三种的一般函数
55．设A=｛1，2，3｝，B=｛a,b｝，下列二元关系R为A到B的函数的是( )
A）R=｛<1,a>,<2,a>,<3,a>｝B）R=｛<1,a>,<2,b>｝
C）R=｛<1,a>,<1,b>,<2,a>,<3,a>｝ D）R=｛<1,b>,<2,a>,<3,b>,<1,a>｝
56．设集合X为人的全体，在X上定义关系R、S为R={<a，b|a，b∈X∧a是b的父亲}，S={<a，b>|a，b∈X∧a是b的母亲}，那么关系{<a，b>|a，b∈x∧ a是b的祖母}的表达式为 （ ）
A）R?SB）R-1?S C）S?RD）R?S-1
57．设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〉，〈4，2〉} B）{〈2，4〉，〈2，3〉，〈4，2〉}
C）{〈4，1〉，〈2，3〉，〈2，4〉}D）{〈2，2〉，〈3，1〉，〈4，4〉}
58．设A是正整数集，R={(x，y)|x，y∈A∧x+3y=12}，则R∩ ({2，3，4，6}×{2，3，4，6})= （ ）
A） O B）{<3，3>} /
C）{<3，3>，<6，2>} D）{<3，3>，<6，2>，<9，1>}
59．设集合X={0,1,2,3}，R是X上的二元关系，
R={<0,0&(转 载 于:wWw.cssYQ.COm 书 业 网:离散数学模拟试卷)gt;,<0,2>,<1,2>,<1,3>,<2,0>,<2,1>,<3,3,>}，则R的关系矩阵MR是（ ）
?1?1A）??0??0010??1?0100?? B）??1001???011??0010?011??C） 100??001??0?1??0??1001?010??D） 101??110??1?0??0??1110?011?? 001??010?
60．集合A={1，2，3}上的下列关系矩阵中符合等价关系条件的是（）
?101??101??110??100??B）?010? C）?011? D）?110? A）?010?????????????001???101???101???111??
61．设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S是（ ）
A）自反关系 B）反自反关系 C）对称关系D）传递关系
62．设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是（ ）
A）R∪IAB）R C）R∪{〈c,a〉}D）R∩IA
63．设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〉}
64．非空集合A上的二元关系R若是自反和对称的，则R是 ( )
A）偏序关系 B）等价关系 C）相容关系 D）拟序关系
65．设实数集R上的二元运算?为：x?y=x+y-2xy，则?不满足 ()
A）交换律 B）结合律C）有幂等元 D）有零元
66．设S是自然数集，则下列运算中不满足交换律的是 ( )
A）a*b=|a-b| B）a*b=ab
C）a*b=max{a,b} D）a*b=min{a,b}
67．在实数集合R上，下列定义的运算中是可结合的只有 ( )
A）a*b=a+2b B）a*b=a+b-2ab
C）a*b=a-b+2ab D）a*b=a-b-2ab
68．在实数集合R上，下列定义的运算中不可结合的是（） ．
A）a*b=a+b+2abB）a*b=a+b
C）a*b=a+b+ab D）a*b=a-b
69．在自然数集N上，下列定义的运算中不可结合的只有（）
A）a*b=min(a,b)B）a*b=a+b
C）a*b=GCD(a,b)(a,b的最大公约数) D）a*b=a(mod b)
70．设Z为整数集，A为集合，A的幂集为P(A)，+、-、/为数的加、减、除运算，∩为集
篇四：离散数学模拟试卷和答案
北京语言大学网络教育学院
《离散数学》模拟试卷一
注意：
1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。
4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 () 种不同的关系。 [A] 3
[B] 8
[C]9
[D]27
2、设A??1,2,3,5,8?,B??1,2,5,7?,则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个
8、一个连通图G具有以下何种条件时，能一笔画出：即从某结点出发，经过图中每边仅一次回到该结点（）。 [A] G没有奇数度结点 [B] G有1个奇数度结点
[C] G有2个奇数度结点 [D] G没有或有2个奇数度结点
9、设〈G,*〉是群，且|G|>1，则下列命题不成立的是（）。 [A] G中有幺元[B] G中么元是唯一的
[C] G中任一元素有逆元 [D] G中除了幺元外无其他幂等元
10、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）
[A] p→┐q [B] p∨┐q [C] p∧q [D] p∧┐q
11、设图G=<V,E>的结点集为V={v1,v2,v3},边集为E={<v1,v2>,<v1,v3>}.则G的割（点）集是（）。
[A]{v1} [B]{v2}[C]{v3} [D]{v2,v3}
12、下面4个推理定律中，不正确的为（）。
[A]A=>(A∨B)(附加律) [B](A∨B)∧┐A=>B (析取三段论) [C](A→B)∧A=>B (假言推理) [D](A→B)∧┐B=>A (拒取式)
13、在右图中过v1,v2的初级回路有多少条（ ）[A] 1 [B] 2 [C] 3[D] 4 14、若R,?,?是环，且R中乘法适合消去律，则R是（）。 [A]无零因子环 [C]整环
[B]除环
[D]域
15、无向图G中有16条边，且每个结点的度数均为2，则结点数是（）。 [A]8 [B]16 [C]4 [D]32
二、【判断题】(本大题共8小题，每小题3分，共24分)正确的填T，错误的填F，填在答题卷相应题号处。
16、???是空集。 （） 17、设S,T为任意集合，如果S—T=?，则S=T。
（）
18、在命题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。（） 19、关系的复合运算满足交换律。 （） 20、集合A上任一运算对A是封闭的。（） 21、
0,1,2,3,4?,max,min
是格。（）
22、强连通有向图一定是单向连通的。 （） 23、设都是命题公式，则(P??Q)?Q?P。 （） 三、【解答题】（本大题共3小题，24、25每小题10分，26小题11分，共31分）请将答案填写在答题卷相应题号处。
24、设集合A＝{a, b, c}，B={b, d, e}，求（1）B?A； （2）A?B； （3）A－B； （4）B?A． 25、设非空集合A，验证(P(A),?,?,~,?,A)是布尔代数
26、如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。
《离散数学》模拟试卷一 答案
一、【单项选择题】(本大题共15小题，每小题3分，共45分)
二、【判断题】(本大题共8小题，每小题3分，共24分) 三、【解答题】（本大题共3小题，24、25每小题10分，26小题11分，共31分） 24、设集合A＝{a, b, c}，B={b, d, e}，求（1）B?A； （2）A?B； （3）A－B； （4）B?A． 标准答案：（1）B?A={a, b, c}?{b, d, e}={ b }
（2）A?B={a, b, c}?{b, d, e}={a, b, c, d, e }
（3）A－B={a, b, c}－{b, d, e}={a, c}
（4）B?A= A?B－B?A={a, b, c, d, e }－{ b }={a, c, d, e }
复习范围或考核目标：考察集合的基本运算，包括交集，并集,见课件第一章第
二节,集合的运算。
25、设非空集合A，验证(P(A),?,?,~,?,A)是布尔代数
标准答案：证明 因为集合A非空，故P(A)至少有两个元素，显然?，?是P(A)上的二元运算. 由定理10 ，任给B,C,D?P(A), H1B?D=D?CC?D=D?C
H2B?(C?D)=(B?C)?(B?D) B?(C?D)=(B?C)?(B?D)
H3 P(A)存在?和A，?B?P(A), 有B??＝B， B?A＝B
H4，?B?P(A), B?A，存在A?~B，有
B?A?~B)= A B?(A?～B)=?
所以(P(A),?,?,~,?,A)是布尔代数.
复习范围或考核目标：考察布尔代数的基本概念，集合的运算，见课件代数系
统中布尔代数小节。
26、如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。
标准答案：令p：他是计算机系本科生
q：他是计算机系研究生 r：他学过DELPHI语言s:他学过C++语言t:他会编程序
前提：(p∨q)→(r∧s),(r∨s)→t结论：p→t
证①p P(附加前提) ②p∨q T①I ③(p∨q)→(r∧s)P(前提引入) ④r∧s T②③I ⑤r T④I ⑥r∨s T⑤I ⑦(r∨s)→t P(前提引入) ⑧t T⑤⑥I