2017大学离散数学自测题及参考答案
《离散数学》自测题
姓名: 班级：学号：
一、判断题（共6小题，每小题1分，共6分）
1. ( )设A、B为任意的2个集合，则A×B=B×A 。
2. ( )若R和S均为反对称关系，则R∪S也为反对称关系
3. ( )关系R是自反的iff I A ?R。
4. ( )设p、q为任意的命题公式，则p→ q=?p∨q 。
5. ( )没有平行边的图就是简单图。
6. ( )设函数f(n)表示n位二进制数中不含连续连个1的个数，则当n>2时，有f(n)=f(n-1)+f(n-2)。
二、单选题（共15小题，每小题2分，共30分）
1.集合A={a,b}与集合B={1,2}的笛卡儿乘积为。
A.{(a,1),(b,2)}
B. {(a,2),(b,1)}
C. {(1,a),(1,b),(2,a),(2,b)}
D. {(a,1),(b,1),(a,2),(b,2)}
2.设}4,3,2,1{
=
A，则A的划分有。
A．
B．}}
4{
},
3,2
{{
C．}}
3{
},
4,2{
},
1
{{ D. }}
4,2{
},
3,2,1
{{
3.对于实数集上的“<”关系，下列说法正确的是。
A. 它是一个偏序关系。
B.它是一个等价关系。
C. 它是反自反、反对称、传递的。
D.它是反自反、对称、传递的。
4.设A={1,2,3}，A上二元关系R的关系图如右，R具有的性质是。
A.自反性
B.对称性
C.传递性
D.反自反性
5.现有2面无差别红旗和3面无差别黄旗，则把这5面旗悬挂在一根旗杆
上，可以组成（）中不同的标志。
A. 5
B. 6
C. 10
D. 20
6.下列各项图中不是简单图的是（）。
A. B．C．D．
7.下列语句中，不是命题的有。
A.5能被2整除。
B.太阳系以外的星球上有生物。
C.现在开会吗？
D.小李在宿舍里。
8.下列命题中真值为0的有。
A. 1+1=2并且3+3=6;
B. 若1+1=2, 则3+3≠6;
C. 1+1=2, 当且仅当3+3=6;
D. 1+1≠2或者3+3=6;
9.若p：他去；q：我去；则“只有他不去，我才去。”，可符号化为。
A. ?p→q
B. q→?p
C. ? q → p
D. ?q→?p
10.图G有12条边，且G中有6个结点度数为3，其余结点度数均小于3，则图G至少
有多少个顶点。
A. 9
B. 8
C. 7
D.10
11.设G为简单无向图，其点集为V，边集为E，且|V|=5，|E|=4, 则其邻接矩阵中有
个1。
A. 4
B.5
C.8
D.10
12.下列的数列能作为无向简单图的顶点度数数列的是。
A. 2,3,3,4, 5
B. 1,2,2,3, 3
C. 1,1,1,2,3
D. 0,1,2,3,4
13.设命题公式G：()
?→→,则使公式G取真值为0的p，q，r赋值分别是。
p q r
A. 1,0,0
B.0,1,0
C. 1,1,0
D. 0,0,1
14.前提条件,
→?的有效结论是。
p q q
A. p
B. q
C. ?p
D. 以上均不是
15.下列各图中不是二部图的（）
A.B．C．D．
三、填空题（共6小题，每小题3分，共18分）
1.设有集合A={{1},2}，则P(A)= 。
2.若p=0,q=1,r=1则命题公式((p∨q)∧(p→r))?(q→r)真值为。
3.n阶无向完全图K n中，共有条边。
4.设p：天气恶劣；q：航班被取消。命题“除非天气恶劣，否则航班不会被取消。”可
符号化为。
5.设二元关系R={
6.设A={1,2,3}，A上的关系R={<1,1>, <2,2>, <2,3>},则R的关系矩阵为：
四、（6分）现有一刑事案件，有4名的犯罪嫌疑人甲、乙、丙、丁，经侦查已知以
下事实：
1.这件事若是甲参与了，则乙或者丙的其中一人也参与了。
2.丙和丁不可能同时参与了这件事。
3.仅当甲不参与此事件时，丁才可能参与此事。
4.这件事有且仅有两人参与。
设命题P：甲参与这件事。Q：乙参与这件事。R：丙参与这件事。S：丁参与这件事。试把1、2、3描述的事实，进行命题符号化，并根据陈述事实，写出这四个人是否参与此事的所有的组合情况。
五、（6分）利用真值表求命题公式(p→r )∧(q→r)的主析取范式和主合取范式。
六、（6分）计算机系1班中共有55名学生，每一名学生至少选修C++，Java，VB
三种语言中的一种，其中选修C++的学生共有30名，选修Java的学生共有32名，选修VB的学生共有15名，且同时选修C++和Java的学生共有12名，同时选修C++和VB的学生共有8名，同时选修Java和VB的共有7名，则
1．同时选修三门课程的人数是多少？
2．只选修了两门课程的人数是多少？
七、（6分）在命题逻辑中证明下述推理：“如果小王是理科学生，则他的数学成绩
很好。如果小王不是文科学生，则他一定是理科学生。小王的数学成绩不好。所以，小王是文科学生。”
八、（6分）设A＝{a, b, c, d，e}上的偏序关系R＝{(a,b),(a, c),(b, d),(a, d),(a, e),(c, e)}
∪I A
(1) 画出其哈斯图。
(2) 找出A的最大元、最小元、极大元和极小元。
九、 （5分）证明逻辑等价式：
(p →r )∧(q →r ) ＝ (p ∨q )→r
十、 （5分）设S ={{a , b },{c },{d , e }}是集合A ={a , b , c , d , e }上的一个划分，试写出由S 确
定的A 上的等价关系R 。
十一、 （6分）给定如下无向图G ，回答以下问题： （1）给出该无向图G 的邻接矩阵A 。
（2）该无向图G 是欧拉图吗，为什么？若是欧拉图，给出一条欧拉回路。 （3）G 中长度为2的通路共有多少条？长度为3的回路共有多少条？
《离散数学》自测题参考答案
一、判断题
1. ?
2. ?
3. √
4. √
5. ?
6. ? 二、单选题
1.D
2.C
3.C
4.D
5.C
6.A
7.C
8.B
9. B 10.A 11.C 12.C 13.B 14.C 15.C 三、填空题
1. {?，{{1}}，{2}，{{1}，2}}
2. 1
3. n(n-1)/2
4. ?p →?q
5. {
6.??
??
?
?????000110001 四、命题符号化
1. P →((Q ∧?R)∨(?Q ∧R))
2. ?(R ∧S)
3. S ??P
可能参与这件事的组合情况是：甲和丙、甲和乙、乙和丁。
4
3
v 5
五、
(p →r )∧(q →r)=m 0∨m 1∨m 3∨m ∨5∨m 7(主析取范式)
=M 2∧M 4∧M 6(主合取范式)
六、设：A 为选修C++的学生集合； B 为选修Java 的学生集合； C 为选修VB 的学生集
合；（1分）
则：|A |=30 |B|=32 |C|=15 |A ∩B |=12 |A∩C |=8 |B ∩C |=7
则：|A ∪B ∪C |=|A|+|B|+|C|-|A∩B |-|A∩C |-|B ∩C |+|
A∩B ∩C |=55 所以同时选修三门课程的人数：|A∩B ∩C |=55-（30+32+15-12-7-8）= 5 只选修了两门课程学生人数为： （|
A∩B |+|A∩C |+|B ∩C |）-3|A∩B ∩C |
=（12+8+7）-15=12
七、
解：设p: 小王是理科学生, q: 小王的数学成绩很好，r: 小王是文科学生 则有，前提： p →q ， ?r →p ，?q 结论：r (1) p →q 前提引入 (2) ?q 前提引入 (3) ?p (1)和(2)拒取规则 (4) ?r →p 前提引入 (5) r (1)和(2)拒取规则 八、
（1）哈斯图： （2）A 极大元为d 和九、
方法1：写出真值表：
方法二：(p →r ) ∧ (q →r)= (?p ∨r ) ∧ (?q ∨r) 蕴涵等值式
=(?p ∧?q) ∨r 分配律 =? (p ∨q) ∨r 德摩根律 =(p ∧q )→r 蕴涵等值式
十、R={a , b }2 ? {c }2 ? {d , e }2
={(a,a), (a,b), (b,a), (b,b)} ? {(c,c)} ?{(d,d), (d,e), (e,d), (e,e)} ={(a,a), (a,b), (b,a), (b,b), (c,c), (d,d), (d,e), (e,d), (e,e)} 十一、 (1) 邻接矩阵：
A=
(2) 是欧拉图。因为各个结点的度数均为偶数。
欧拉回路为：v 1v 2v 3v 4v 2v 5v 4v
1 (3)
23
212122141316,2
12122
131416212122A A ????
? ?
? ?
? ?== ? ?
? ?
? ??
???
v 1 v 2 v 3 v 4
v 5
G中长度为2的通路共有44条, 长度为3的回路有18条.
离散数学作业答案
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作，
山东大学离散数学题库及答案
《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 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、判断下列语句就是不就是命题。若就是,给出命题的真值。( ) (1) 北京就是中华人民共与国的首都。 (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)均有可能
华南理工离散数学作业题2017版
华南理工大学网络教育学院 2014–2015学年度第一学期 《离散数学》作业 （解答必须手写体上传，否则酌情扣分） 1．设命题公式为?Q∧（P→Q）→?P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。 解：（1）真值表如下： P Q ?Q P →Q ?Q∧（P→Q）?P ?Q∧（P→Q）→?P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 （2）?Q∧（P→Q）→?P??(?Q∧(?P∨ Q)) ∨? P ?( Q∨? (?P∨ Q)) ∨? P ?? ( ?P∨ Q) ∨ (Q∨?P) ?1（析取范式） ?(?P∧? Q) ∨ (?P∧ Q) ∨ (P∧? Q) ∨（P∧ Q）（主析取范式） （3）该公式为重言式 2．用直接证法证明 前提：P∨Q，P→R，Q→S 结论：S∨R 解：（1）?S P (2)Q →S P (3) ? Q (1)(2) (4)P∨ Q P
(5)P (3)(4) (6) P → R P (7)R (5)(6) (8)?S→ R （1）（7） 即SVR得证 3．在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。 令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 解：前题：?x (F (x) →?G(x)), ?x (G (x) ∨H (x)) ? x ?H (x) 结论:? x ?F (x) 证：（1）? x ?F (x) p (2) ?H (x) ES(1) (3) ?x (G (x) ∨H (x))P (4)G(c) vH(c)US(3) (5)G(c) T(2,4)I (6)?x (F (x) →?G(x)), p (7)F (c) →?G(c) US(6) (8) ?F (c) T(5,7)I (9)( ? x) ?F (x) EG(8) 4．用直接证法证明： 前提：（?x）（C（x）→W（x）∧R（x）），（?x）（C（x）∧Q（x）） 结论：（?x）（Q（x）∧R（x））。 证： （1）（?x）（C（x）∧Q（x））P (2) C (c) ∧Q（c）ES(1) (3)（?x）（C（x）→W（x）∧R（x））P
离散数学模拟题一套及答案
离散数学考试（试题及答案） 一、（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>}。
(完整版)离散数学作业答案一
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外) 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1 .命题公式P (Q P)的真值是T或1 ______ . 2?设P:他生病了，Q:他出差了. R:我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P V Q)-R 3. ____________________________________________________________ 含有三个命题变项P，Q，R的命题公式P Q的主析取范式是__________________ _(P Q R) (P Q R)_ 4. 设P(x): x是人，Q(x): x去上课，则命题“有人去上课.” 可符号化为— x(P(x) Q(x))_ 5. 设个体域D = {a, b},那么谓词公式xA(x) yB(y)消去量词后的等值式为 (A(a) A(b)) (B(a) B(b))_ 6 .设个体域D = {1,2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x)的真值为F 或0 ________________ . 7.谓词命题公式(x)((A(x) B(x)) C(y))中的自由变元为 ________ . 8 .谓词命题公式(x)(P(x) Q(x) R(x，y))中的约束变元为x _______ . 三、公式翻译题 1 .请将语句“今天是天晴”翻译成命题公式
《离散数学》题库及答案
《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( A ) (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）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式x((A(x)B(y，x))z C(y，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式x A和x A中，称x为指导变元，A为量词的辖域。在x A和x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( )
(1)北京是中华人民共和国的首都。(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→ ? P? ?（4）Q P? →（3）Q 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 (反证法：假若存在，则（x- 1）*y=0 对所有的x都成立，显然这个与前提条件相矛盾) （2）F （同理）（3）F （同理）（4）T（对任一整数x存在整数y满足条件y=2x 很明显是正确的）
离散数学模拟试题讲解
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 ,则有向图 >= 第二章命题逻辑 §2.2 主要解题方法 2.2.1 证明命题公式恒真或恒假 主要有如下方法： 方法一.真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每 一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。 真值表法比较烦琐，但只要认真仔细，不会出错。 例2.2.1 说明G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。 解：该公式的真值表如下： 表2.2.1 由于表2.2.1中对应公式G所在列的每一取值全为1，故 G恒真。 方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例2.2.2 说明G= ((P→R) ∨? R)→ (? (Q→P) ∧ P)是恒真、恒假还是可满足。 解：由(P→R) ∨? R=?P∨ R∨? R=1，以及 ? (Q→P) ∧ P= ?（?Q∨ P）∧ P = Q∧? P∧ P=0 知，((P→R) ∨? R)→ (? (Q→P) ∧ P)=0，故G恒假。 方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。 方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G 本科高等数学离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________. 9. 设集合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 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。 浙江农林大学暨阳学院 2016 - 2017 学年第 二 学期考试卷答案 课程名称： 离散数学 课程类别： 必修 考试方式： 闭卷 适用专业： 计算机151-152 注意事项：1、本试卷满分100分。 2、考试时间 120分钟。 一、单项选择题（在每小题的四个备选答案中，选出一个正确答案， 并将正确答案的选项填在题后的括号内。每小题2分，共8分） 1. 公式q p p ?→?→)(的类型是 ( C ) A. 重言式 B. 矛盾式 C. 非重言式的可满足式 D. 以上均不对 2. |A |=n , |B |=m , 且m , n >0, 则|B A |= ( D ) A.m 2 B. 2n C. n m D. m n 3. 集合的广义并}},{},,,{},,,{{d a d c a c b a ?= ( B ) A.},,{c b a B.},,,{d c b a C.},,{d c a D.}{a 4. f ：R→R, f (x )=-x 2+2x -1，则f 是 ( D ) A. 单射 B. 满射 C. 双射 D. 以上均不对 系（部） ： 专业班级： 姓名： 学号： 装 订 线 内 不 要 答 题 二、填空题（每小题3分，共36分） 1. 令p:吴颖用功, q:吴颖聪明，吴颖既用功又聪明符号化为__q p ∧_____ 2. 如果2 <1,则23≥的真值为___1___ 3. (q →p ) ∧q →p 的成真赋值为 ___00,01,10,11_ __ 4. (p →?q)→r ? 13567m m m m m ∨∨∨∨的成假赋值为__000,010,100_ 5. 设A 有3个命题变项, 且已知A= m 2∨m 4∨m 5∨m 6，A 的主合取范式为 ___7310M M M M A ∧∧∧= 6. 设D 为人类集合，G(x)：x 用左手写字，则一阶逻辑中命题有人用左手写字符号 化为__)(x xG ?__ _ 7. 给定解释 I 如下： (a) 个体域 D=R (b) 0a = (c) (,),(,)f x y x y g x y x y =+=? (d) (,):F x y x y = 则公式?xF (g (x ,y ),a ) 在I 下的解释为__)0(=??y x x _____ 8. R = {<1,2>, <2,3>, <1,4>, <2,2>}，S = {<1,1>, <1,3>, <2,3>, <3,2>, <3,3>}， 则S ?R = __{1,2,1,4,3,3,3,2}<><><><>__ 9. 设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}, 则R ?{2} = ___}4,2,2,2{><><___ 10. 设R 为A 上的关系, 则有R 的对称闭包s(R)=__ 1-?R R ____ 11. 设G= 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 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个 作业参考答案——10-特殊图 1.(a)(c)(d)是欧拉图，(a)(b)(c)(d)(e)可以一笔画，(a)(b)(c)(d)(e)(f)(g)是 哈密顿图。 2.根据给定条件建立一个无向图G= 数至少为2，而V2中的每个结点度数至多为2，从而它满足t条件t=1，因此存在从V1到V2的匹配，故可分配。 5.此平面图具有五个面，如下图所示。 a b c d e f g r1r2 r3 r4 r5 ?r1，边界为abca，D(r1)=3; ?r2，边界为acga，D(r2)=3; ?r3，边界为cegc，D(r3)=3; ?r4，边界为cdec，D(r4)=3; ?r5，边界为abcdefega，D(r5)=8;无限面 6.设该连通简单平面图的面数为r，由欧拉公式可得，6?12+r=2，所以 r=8，其8个面分别设为r1,r2,r3,r4,r5,r6,r7,r8。因是简单图，故每个面至少由3条边围成。只要有一个面是由多于3条边所围成的，那就有所有面的次数之和 8∑ i=1 D(r i)>3×8=24。但是，已知所有面的次数之和等于边数的两倍，即2×12=24。因此每个面只能由3条边围成。 2 《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群 19、代数系统是指由及其上的或 组成的系统。 20、设 2017年4月高等教育自学考试《离散数学(二)》试题 课程代码：06094 一、单项选择题(本大题共20小题，每小题2分，共40分) 1．下面给出的句子中不构成命题的是 A ．不要作弊 B ．3+2=9 C ．7是质数 D ．我是男生 2．能使命题P Q →为真的条件是 A ．P 真 B ．Q 假 C ．Q 真 D ．P 真Q 假 3．用P 表示“选张三任班长”，Q 表示“选李四任班长”。则命题“选张三或李四中的 一人任班长”可符号为 A ．P Q ∨ B ．P Q ∧ C ．P Q ?∨ D ．()()P Q P Q ??∧∨∧ 4．P(3,x,y,z)谓词的元数是 A ． 1 B ．4 C ．3 D ．0 5．在公式()X P x ?中，称P 为量词的 A ．论域 B ．辖域 C ．值域 D ．0定义域 6．设谓词F(x)表示x 是实数；Q(x)表示x 能被2整除。则命题“存在能被2整除的实数” 可符号化为 A ．(()())X F x Q x ?∧ B ．(()())X F x Q x ?→ C ．(()())X F x Q x ?→ D ． (()())X F x Q x ?∧ 7．由存在指定规则可得到P(c)结论的公式是 A ．()X P x ? B ．()X P x ? C ．()X P x ?? D ．()X P x ?? 8．下面描述中错误的是 A ．P 是合式公式，则 P ?是合式公式 B ．()X P x ?中x 是约束出现的变元 C ．()X P y ?∧是合式公式 D ．()()X X P x P x ????? 9．只有两个元素的集合其幂集元素个数共有 A ．2 B ．7 C ．8 D ．16 10．设集合M=｛1，2｝，P={2，3}。则有 A ．M P ={2} B ．M P ⊕ =｛1，3｝ C ．M P -={3} D ．M P =｛1，2，3｝ 11．下面给出的集合中，不是{a,b}到{1,2,3}的二元关系的是 A ． {a,2} B ． {(a,2)} C ． {} D ．空集 12．设A={1，2}，B={3，4}，M={(1，3)，(2,4)}是A 到B 的一个二元关系，则M 的关系矩阵第二 《离散数学》模拟试题 一、 填空题（每小题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 →∧?=)( 第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试 3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章 《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 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、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (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吉林大学离散数学课后习题答案
大学本科高等数学《离散数学》试题及答案
离散数学试卷答案2017.6月
离散数学模拟试卷和答案
慕课 离散数学 电子科技大学 课后习题十 答案
中国石油大学大学《离散数学》期末复习题及答案
2017年4月高等教育自学考试《离散数学(二)》试题06094
离散数学模拟试题及答案
离散数学作业答案
山东大学离散数学题库及答案
- 离散数学考试试题A、B卷及答案
- 离散数学期末考试题答案
- 南昌大学_离散数学_期末试卷(最新)
- 《离散数学》复习题及答案
- 中国石油大学大学《离散数学》期末复习题及答案
- 中国石油大学大学《离散数学》期末复习题及答案
- 离散数学试题及答案
- 大学离散数学复习试题
- 大学离散数学复习试题 (1)
- 大学离散数学试题集(非常完全试题)
- 大学离散数学题库答案
- 大学《离散数学》期末考试试卷及答案-(1)
- 北京交通大学离散数学期末考试题-05-06-1-B-公选-试卷
- 大学离散数学复习试题
- 大学离散数学试题集(完整试题)
- 大学离散数学试题集(非常完整试题)
- 大学离散数学试题集非常完整试题
- 中国石油大学大学《离散数学》期末复习题及答案
- 离散数学试题及复习资料
- 大学《离散数学》期末考试试卷及答案-(1)