离散数学教学研究论文范文第1篇
关键词:离散数学;实验;课程安排
“离散数学”作为计算机专业很重要的一门基础课,对于后续课程,如数据结构,数据库原理,编译等课程起到直接的影响,同时对培养学生的逻辑思维能力,抽象思维能力,探讨前沿领域都起着非常重要的作用。根据我校离散数学教学的多年教学,我们在“离散数学”教学的环节中增加了实践环节,考虑课时安排问题,基本都是以课后作业的形式安排,但是在考核中增加分值,以调动学生的积极性。
1“离散数学”实验内容的设计
“离散数学”课程按传统的教学,共分四个部分,数理逻辑,集合论,代数系统,图论。我们共计按两个学期开设课程,每个学期54学时。在第一学期讲授前两部分,第二学期讲授后两部分。根据实际情况,我们设计了如下的实践题目,见表1和表2。
根据学时,我们的实验大部分都安排在业余时间进行。教师利用QQ群等工具进行答疑辅导,我们感觉到学生如果发现老师和他们一样能够使用现代的网络工具,那么他们和老师之间的距离无形中被缩小了。
在实验题目的安排上我们力求精炼,体现课程的难点,增加学生理解的最大化。在实验的组织上,我们采用分组进行,组长负责制,采用小组软件工程的要求,填写实验日志。在实验的指导上,教师利用投影分析流程,训练流程图的使用。在编程语言上我们不加要求,学生可以使用C,C++,Java等。事实表明,由于我们学校在前一学期学习了C语言,所以大多数同学使用C,也有个别同学使用了自学的GUI语言,比如JBuilder等。在实验组的形式上,学生可以给自己的组自由命名,有的组居然命名为“微软第二小组”。通过这个命名,学生的集体意识明显增强了。
对于实验的梯度问题,很多同学的分析能力和解决问题的能力很弱,针对这种情况,我们采取了互相帮助的原则,如果哪个同学对于该组的题目内容无法讲解清楚,无法说明每个人所做的工作,那么一票否决制。这样,即使那些不会编程的同学,也通过这个过程熟悉了如何提出和解决问题。
2实验效果的反馈与评价
在最开始进行实验活动的时候,很多同学不理解,也无法按时完成任务,但是我们对那些完成任务的同学给予及时的鼓励,给予加分奖励,不知不觉中,他们也接受了“自己也应该去完成这样的任务,也应该能够完成任务”的思想,思想一旦启动了,行动就顺理成章的进行了。因此我们感觉,必须让学生从思想上意识到问题的重要性。
通过实验后,学生普遍的感受都是收获很大,无论是在题目的和语言编程上,还是在团队的战斗过程中。在实验后,他们增加了战胜下一个题目的信心,增加了彼此的了解,彼此的信任,取长补短。在2005级同学的实验数据如图1。
我们的评价指标主要包括如下几个方面(1)问题分析透彻,分析报告完整。(2)程序编写的思路清晰,代码编写的规范(3)小组的讨论记录,见图2。
优秀人数的比例大约占到总人数的3-25%之间,良好在40-50%之间。我们从来不吝啬赞美之辞,使得广大同学的积极性非常高涨。
3存在的问题和解决的思路
经过几年的实践,我们发现了如下几个问题:
(1) 学生水平参差不齐,选择计算机专业学习就是要把它放到一定的高度上,有兴趣的同学经常看课外书,经常问老师问题,思考能力明显增强,但是还有很多同学,选择计算机学习后又后悔了,以为计算机就是打打字,使用应用软件那么简单。针对这种情况,我们从职业化和就业的高度教育同学,告诫他们既选择之,就要奋斗之。鼓励而不是消极的讽刺。
(2) 语言基础不够扎实。在学习语言的时候,要对于基本的如数组,结构体,文件等内容有较为熟练的使用。我们的大多数同学都需要翻阅上个学期学习的语言教材,有很多同学甚至都看不懂上个学期学习的内容了。针对这种情况我们专门组织了学习比较好的同学做几次辅导讲座,一方面使讲座同学系统的整理一下,又使其他同学温习了相关知识,向学习好的同学看齐,差距是前进的动力。同时我们和负责语言教学的老师进行沟通,适当加强某些环节课程的教学。
总之,通过几年的实践教学,我们感觉到学生们通过自己的努力,在教师的辅导下,获得了学习的乐趣,增长了学习的动力,提高了学习的自主性。
离散数学教学研究论文范文第2篇
graph theory.
考试题型:计算题;简答题;证明题;构造图形(构造满足一定条件的图,如:
6个顶点,11条边且无Hamiltonian circuit)。题目共计6题,无选择题和填空题。
考试难度:基本与期中考试相同,有一定数量的题直接来自于习题,最后一题较
难(构造图形)。
复习要点:基本概念及定义:
rooted tree; binary tree; labeled tree; positional tree; tree
searching; undirected tree; weighted graph; minimal spanning tree;(undirected) graph; degree; Euler path and Euler circuit; Hamiltonian path and Hamiltonian circuit; matching function; coloring graph; chromatic number; chromatic polynomial; planar graph;
基本内容:
tree searching; the prefix (Polish form) and infix form of the
algebraic expression; minimal spanning tree; the sufficient-necessary condition for a graph G to have Euler circuit (or path); coloring graph; chromatic number; chromatic polynomial; construct a graph (directed or undirected) subject to some given conditions.
不要求的内容:
Computer representation of binary positional tree; searching general tree; algorithms.
复习中如遇困难请联系:钱建国13178272231,jgqian@jingxian.xmu.edu.cn徐伟13599513903
陈美润13799279303
离散数学教学研究论文范文第3篇
一、选择题:本题共5小题,每小题3分,共15分,在每小题给出的四个选项中,只有一项是符合题目要求的。
1. 命题公式(PQ)Q为 ()
(A) 矛盾式 (B) 可满足式(C) 重言式 (D) 合取范式
2.设P表示“天下大雨”, Q表示“他在室内运动”,则命题“除非天下大雨,否则他不在室内运动”符号化为()。
(A). PQ; (B).PQ;(C).PQ; (D).PQ.
3.设集合A={{1,2,3}, {4,5}, {6,7,8}},则下式为真的是()
(A) 1A(B) {1,2, 3}A
(C) {{4,5}}A(D) A
4. 设A={1,2},B={a,b,c},C={c,d}, 则A×(BC)= ()
(A) {<1,c>,<2,c>}(B) {,<2,c>}(C) {,}(D) {<1,c>,}
5. 设G如右图:那么G不是().(A)哈密顿图;(B)完全图;
(C)欧拉图;(D) 平面图.二、填空题:本大题共5小题,每小题4分,共20
6. 设集合A={,{a}},则A的幂集P(A7. 设集合A={1,2,3,4 }, B={6,8,12}, A到B的关系R={x,yy2x,xA,yB},
那么R1=-
8. 在“同学,老乡,亲戚,朋友”四个关系中_______是等价关系.9. 写出一个不含“”的逻辑联结词的完备集.
10.设X={a,b,c},R是X上的二元关系,其关系矩阵为
101,那么R的关系图为 MR=100100
三、证明题(共30分)
11. (10分)已知A、B、C是三个集合,证明A∩(B∪C)=(A∩B)∪(A∩C)
12. (10分)构造证明:(P(QS))∧(R∨P)∧QRS
(0,1)13.(10分)证明与[0,1),[0,1)与[0,1]等势。
四、解答题(共35分)
14.(7分)构造三阶幻方(以1为首项的9个连续自然数正好布满一个33方阵,且方阵中的每一行, 每一列及主、副对角线上的各数之和都相等.)
15.(8分) 求命题公式(PQ)(PQ)的真值表.16.(10分)设R1是A1={1,2}到A2=(a,b,c)的二元关系,R2是A2到A3={,}的二元关系,R1= {<1,a>,<1,b>,<2,c>}, R2={,}
毕节学院《离散数学 》课程试卷第 1 页 共 4 页
求R1R2的集合表达式.
17.(10分)某项工作需要派A、B、C和D 4个人中的2个人去完成,按下面3个条件,有几种派法?如何派?
三个条件:(1)若A去,则C和D中要去1个人;(2)B和C不能都去;
(3)若C去,则D留下。
一、单项选择题(每小题3分,共15分)
1.B2.C3. C4.A5.B
二、填空题(每小题4分,共20分)
6. {,{},{{a}},{,{a}}}
7.{<6,3>,<8,4> }8. 老乡
9.{,}或{,} 或 {}或 {}
10. 见第10题答案图.
11.证明:∵x A∩(B∪C) x A∧x(B∪C) ··························································· 2分
x A∧(xB∨xC) ······························································································· 3分
( x A∧xB)∨(x A∧xC) ··········································································· 5分
x(A∩B)∨x A∩C ······························································································ 7分
x(A∩B)∪(A∩C) ····························································································· 9分
∴A∩(B∪C)=(A∩B)∪(A∩C) ·················································································· 10分
12.证明:(1)R附加前提
(2)R∨PP ········································································································ 2分
(3)PT(1)(2),I ······················································································ 3分
(4)P(QS)P ······································································································· 4分
(5)QST(3)(4),I ······················································································ 5分
(6)QP ······································································································· 6分
(7)ST(5)(6),I ······················································································ 8分
(8)RSCP ··································································································· 10分
13. 证明:a) 设A{,,,
c第10题答案图 11
231,},作f:(0,1)[0,1)如下: ································· 2分 n
1f()0211,xAn2 ························································································ 5分 f()nn1f(x)x,x(0,1)A
b) 设A,,,11
231,},作f:[0,1)[0,1]如下: ····················································· 7分 n
毕节学院《离散数学 》课程试卷第 2 页 共 4 页
f(0)0111························································································ 10分 ,n1,A ·f()n1nn
f(x)x,x[0,1)A
14.
8
9 5 1 2 7 6
填对每个格得1分。
15.
表中最后一列的数中,每对1个数得2分.
11016.MR1,(2分)001
MR201(4分) 0100
010101(6分) 0000110 MR1R2001
R1R2{1,}(10分)
17. 解设A:A去工作;B:B去工作;C:C去工作;D:D去工作。则根据题意应有:ACD,(B∧C),CD必须同时成立。 ······························································································ 2分 因此(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∧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 ··································································································································· 8分
毕节学院《离散数学 》课程试卷第 3 页 共 4 页
故有三种派法:B∧D,A∧C,A∧D。 ······································································· 10分
离散数学教学研究论文范文第4篇
1. 设A={1,2,3,4},A上二元关系
R={(a,b)|a=b+2},
S={(x,y)|y=x+1 or y=
x2} 求RS,SR,SRS,S2,S
3,SRc。
RS={(3,2),(4,3),(4,1)} SR={(2,1),(3,2)} SRS={(2,2),(3,3),(3,1)} S2={(1,1),(1,3),(2,2),(2,4),(3,2),(4,1),(4,3)} S3={(1,2),(1,4),(2,1),(2,2),(2,3),(3,1),(3,3),(4,2),(4,4)} SRc={(1,4),(2,3),(4,4)}
2.A={a,b,c,d,e,f,g,h},给定A上关系R的
关系图如下:
图3-14 求最小正整数m,n,m
R1=R16
这是因为R15是8个顶点以及8个自回路,相 当于左图的点各走了5圈,左图的点各走了3圈, R16就成了原来的R.
3.证明:
(1)(InA)IA(a,a)I2nA,aA,(a,a)IA,...,(a,a)IA, (b,b)InA,bA,(b,b)IA.
22
(2)IARRIAR(a,b)R,a,bA,(a,a)IA,(b,b)IA,(a,b)IAR,(a,b)RIA,即RI
AR,RRIA;(a,b)IAR,若(a,b)R,则(a,b)IAR,矛盾,得IARR;同理,RIAR. 事实上,当|A|有限时,R与IA复合,相当于矩阵与 单位矩阵相乘,不会变化。
(3)(RIn2nA)IARR...Rn1(RIA)IAR;设(RIk2A)IARR...Rk
(RIk1(I2A)...RkARR)(RIA)(RR2...Rk1)(I2ARR...Rk)IR2...RkRk1AR
4.判断下列等式是否成立(R,R1,R2均是A到B的 二元关系)
(1)(Rccc1R2)R1R2对,(a,b)(Rc1R2)(b,a)R1R2(b,a)R
1or(b,a)R2(a,b)Rc1or(a,b)Rc2(a,b)Rcc1R2
(2)(Rcc1R2)R1Rc2对(a,b)(Rc1R2)(b,a)R1R2(b,a)R
1and(b,a)R2(a,b)Rcc1and(a,b)R2(a,b)Rcc1R2
23
(3)(R1R2)R1R2对cccc(a,b)(R1R2)(R1R2)c(b,a)R1R2(b,a)R1,(b,a)R2
(a,b)Rc1,(a,b)Rc2(a,b)Rcccc1R2R1R2(4)(AB)cAB否,例:A{1,2},B{3,4},AB{(1,3),(2,3),(1,4),(2,4)}
(AB)c{(3,1),(3,2),(4,1),(4,2)}(5)c否,c
与的定义域,值域对换了一下.(6)(R)c(Rc)对,(a,b)(R)c(b,a)R(b,a)R(a,b)Rc(a,b)Rc(7)(Rcc1R2)R2Rc1否,R2的定义域不一定与R1的值域相同(8)如果Rcc1R2,则R1R2对,(a,b)Rc1,(b,a)R1R2, (a,b)Rc2.(9)如果R1Rcc2,则R1R2对,(a,b)Rc1,(b,a)R1R2,(a,b)Rc2,
R1R2,(c,d)R2,(c,d)R1,(d,c)Rc2,而(d,c)Rc1..
24
(10)R1R2R2R1否,R
2的定义域不一定与R1的值域相同.
5. 设R1,R2是集合A上的二元关系,如果R2R1,
其中r,s,t分别是自反闭包,对称闭包,传递闭包的 记号。试证明: (1)r(R2)r(R1)R2R1,IAIA, R2IAR1IA
(2)s(R2)s(R1)R2Rcc1,R2R1
Rcc2R2R1R1
(3)t(R2)t(R1)R222R1(R2)1(R1)1(即R2R2R1R1)(a,b)R(a,b)(R2R1(R1)1b)R22)1(a,2,cA,(a,c),(c,b)R2R1,(a,b)R21,(a,b)(R1)1(a,b)t(R2),k,使(a,b)(R2)k(R1)kt(R1).
6. 设R1,R2,R3,R4分别是A到B,B到C,B到C, C到D的二元关系,证明
(1)R1(R2R3)R1R2R1R3(x,y)R1(R2R3)z,(x,z)R1,(z,y)R2or(z,y)R3z,(x,z)R1,(z,y)R2or(x,z)R
1,(z,y)R3(x,y)R1R2or(x,y)R1R3(x,y)R1R2R1R3
25
(2)R1(R2R3)R1R2R1R3(x,y)R1(R2R3)z,(x,z)R1,(z,y)R2and(z,y)R3z,(x,z)R
1,(z,y)R2and(x,z)R1,(z,y)R3(x,y)R1R2and(x,y)R1R3(x,y)R1R2R1R3(3)(4)类(1)(2)证明。
7. 设R是A上的二元关系,证明对任意自然数m,n,
(1)RmRnRmn(2)(Rm)nRmn
由归
(1)1)n1,Rm1RmR2)假定RmRnRmn{(a,b)|cA,(a,c)Rm,(c,b)Rn}n1RmR{(a,b)|cA,(a,c)Rm,(c,b)Rn1}其中,Rn1{(c,b)|dA,(c,d)Rn,(d,b)R}RmRn1{(a,b)|c,dA,(a,c)Rm,(c,d)Rn,(d,b)R}{(a,b)|dA,(a,d)Rmn,(d,b)R}RmnRR(mn)1Rm(n1)
(2)1)n1,RmRm2)假定(Rm)nRmn(Rm)n1(Rm)nRmRmnRm
由(1)RmnmRm(n1)8. 设R是A上的二元关系,|A|=n,证明存在 自然数s,t,使RsRt,且0st2n2,其中定义
R0{(a,a)|aA}。
26
0(ai,aj)R证:R(rij)nn,rij1(ai,aj)R至多有2n2个不同的Rk(kN)出现,
0k2n2,由鸽洞原理,(2n21)个Rk中必存在s,t,0st2n2,RsRt.
9. R1,R2是A上的二元关系,判别下列命题正确与否
(1)如果R1,R2自反,则R1R2也自反。
对,aA,(a,a)R1,(a,a)R2,(a,a)R
1R2
(2)如果R1,R2反自反,则R1R2也反自反。
否,若(a,b)R1,(b,a)R2,(a,a)R1R2
(3)如果R1,R2对称,则R1R2也对称。
否,例:A{1,2,3},
R1{(1,2),(2,1)},R2{(2,3),(3,2)},(1,2)R
1,(2,3)R2,(1,3)R1R2,而(3,1)R1R2
(4)如果R1,R2反对称,则R1R2也反对称。
否,例:A{1,2,3},
R1{(1,2),(3,2)},R2{(2,3),(2,1)},(1,2)R,3)R,
1,(22,(1,3)R1R2(3,2)R1,(2,1)R2,(3,1)R1R2
(5)如果R1,R2传递,则R1R2也传递。
否,例:A{1,2,3,4},R1{(1,1),(2,3)},R2{(1,2),(3,3)},
(1,1)R1,(1,2)R2,(1,2)R1R2,
(2,3)R1,(3,3)R2,(2,3)R1R2,但(1,3)R1R2
10.设A={a,b,c},以下分别给出一个P(A)上的二元 关系,确定它们哪些是自反的,反自反的,对称的, 反对称的,传递的。
27 P(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} (1) x是y的一个真子集
R1{(x,y)|xy,x,yP(A)}
反自反,不对称,反对称,传递 (2) x与y不相交
R2{(x,y)|xy,x,yP(A)}
不自反,也不反自反(),对称,不传递 (3)xyA
R3{(x,y)|xyA,x,yP(A)}
不自反,也不反自反{a,b,c}{a,b,c}A, 对称,不传递。
11. 设R是A上二元关系,证明R是传递的当且仅当
R2R。
任(a,b)∈R2,C,(a,c)(c,b)∈R ,由R传递(a,b)∈R , 即R2 R; 若(a,b)∈R, (b,c)∈R , 即(a,c)∈R2 R , 所以R传递。
12. R是A上反对称的二元关系,问t(R)总是反对称 的吗?
010111否, 例: R001,t(R)111
100111
13.设R是A上的一个自反关系,证明当且仅当 (a,b)和(a,c)属于R推出(b,c)属于R时,R是一个等价 关系。
若(a,b)∈R,又自反(a,a)∈R, 推出(b,a)∈R, 所以对称;
若(a,b)(b,c)∈R , 由对称(b,a)(b,c)∈R , 推出(a,c)∈R ,所以传递。若R等价, (a,b)(a,c)∈R , 由对称性(b,a)(a,c)∈R , 由传递性 ,(b,c)∈R。
14. 设R是A上的一个对称和传递的关系,证明如果对A中的每个a,在A中存在b,使得(a,b)∈R,则R是一个等价关系。 aA,bA,(a,b)R,由对称性,(b,a)R,又由传递性,(a,a)R.
15. 设R是A上的一个传递和自反的关系,设T是 A上的一个二元关系,使得当且仅当(a,b)和(b,a)同时 属于R时,(a,b)∈T,证明T是一个等价关系。 a (a,a) ∈R, (a,a) ∈R => (a,a) ∈T 若(a,a) ∈T, (a,b)(b,a) ∈R , 即(b,a)(a,b) ∈R
28
=>(b,a)∈T 若(a,b)(b,c) ∈T, (a,b)(b,a)(b,c)(c,b) ∈R
=> (a,c) ∈R, (c,a) ∈R
=>(a,c) ∈T
16. 设R是A上一个二元关系,设
S={(a,b)|对某个C,(a,c)∈R且(c,b)∈R}
证明如果R是等价关系,则S也是等价关系。
a, (a,a) ∈R, (a,a) ∈R
=> (a,a) ∈S 若(a,b) ∈S , 存在c, (a,c)(c,b) ∈R 由R对称, (b,c)(c,a) ∈R , 所以(b,a) ∈S 若 (a,b)(b,c) ∈S
存在d,e
(a,d)(d,b)(b,e)(e,c) ∈R
由R传递(a,b)(b,c) ∈R 所以(a,c) ∈S
17. 设R是A上的二元关系,对所有的xi,xj,xk∈A, 如果xiRxj∧xjRxkxkRxi,则称R为循环关系,
试证明当且仅当R是等价关系时,R才是自反的和循环的。(其中aRb表示(a,b)∈R)。
R等价, 当然自反,如果xiRxj且xjRxk则由传递性, xiRxk, 由对称性xkRxi,
R是自反, 循环的;
若(a,b) ∈R, 由R自反 a, (a,a) ∈R, 又(a,b) ∈R, 由循环(b,a) ∈R,对称,
若(a,b)(b,c)∈R,由循环(c,a) ∈R, 由对称(a,c) ∈R, 传递。
18.设R1,R2是A上二元关系,证明 (1)r(R1R2)r(R1)r(R2)(2)s(R1R2)s(R1)s(R2) (3)t(R1R2)t(R1)t(R2)(1)r(R1R2)(R1R2)IAR1IAR2R1(IAIA)R2(R1IA)(IAR2)(R1IA)(R2IA)r(R1)r(R2)(2)s(Rc1R2)(R1R2)(R1R2)Rcc1R2R1R2
(Rcc1R1)(R2R2)s(R1)s(R2)(3)(R1R2)2{(a,b)|c,(a,c)R1orR2,(c,b)R1orR2}R221R2R1R2R2R1 29 R2221R2(R1R2)用归纳法可证RnRnn12(R1R2)
n,可得t(R1)t(R2)t(R1R2)
19. 设A={a,b,c,d},A上二元关系
R={(a,b),(b,a),(b,c),(c,d)}
(1) 用矩阵算法和作图法求r(R),s(R),t(R)。 (2)用Warshall算法求t(R)。
110001001111 r(R) =1110101011110011 s(R)= 0101 t(R)=0001000100100000
010010011101010i10110i211100001100010001
0000j20000j1,20000i3111111111111110i311111i41111j20001000100010000j20000j1,2,30000
20. 讨论正实数集上二元关系R的几何意义。 (1)R是自反的 (2)R是对称的 (3)R是传递的
(提示:以第一象限的点讨论)
(1)第一象限角平分线
(2)关于对角平分线对称的点对集合
(3)若有P1(x1,y1)、 P2(x2,y2), 若x2=y1,
必有第三个点P3(x1,y2)
离散数学教学研究论文范文第5篇
第一章 集合
1.分别用穷举法,描述法写出下列集合 (1) 偶数集合
(2)36的正因子集合 (3)自然数中3的倍数 (4)大于1的正奇数
(1) E={,-6,-4,-2,0,2,4,6,}
={2 i | i I }
(2) D= { 1, 2, 3, 4, 6, } = {x>o | x|36 }
(3) N3= { 3, 6, 9, ```} = { 3n | nN }
(4) Ad= {3, 5, 7, 9, ```} = { 2n+1 | nN }
2.确定下列结论正确与否 (1)φφ
× (2)φ{φ}√ (3)φφ√ (4)φ{φ}√ (5)φ{a}× (6)φ{a}√
(7){a,b}{a,b,c,{a,b,c}}×(8){a,b}{a,b,c,{a,b,c}}√(9){a,b}{a,b,{{a,b}}}× (10){a,b}{a,b,{{a,b}}}√
3.写出下列集合的幂集 (1){{a}}
{φ, {{ a }}}
( 2 ) φ
{φ} (3){φ,{φ}}
{φ, {φ}, {{φ}}, {φ,{φ}} } (4){φ,a,{a,b}}
{φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }},
{a, {a b }}, {φ,a,{ a, b }} } (5)P(P(φ))
{φ, {φ}, {{φ}}, {φ,{φ}} }
4.对任意集合A,B,C,确定下列结论的正确与否 (1)若AB,且BC,则AC√ (2)若AB,且BC,则AC× (3)若AB,且BC,则AC× (4)若AB,且BC,则AC ×
5.对任意集合A,B,C,证明
(1)A(BC)(AB)(AC) 左差A(BC)差A(BC)D.MA(BC)
分配(AB)(AC)右(2)A(BC)(AB)(AC)1)左差A(BC)(1)的结论(AB)(AC) 差(AB)(AC)右
2)左差A(BC)D.MA(BC)分配(AB)(AC)差(AB)(AC)右(3)A(BC)(AB)(AC)左差A(BC)D.MA(BC) 幂等(AA)(BC)
结合,交换(AB)(AC)右(4)(AB)BAB 左差(AB)B对称差((AB)B)((AB)B)
分配,结合((AB)(BB))(A(B)B))
2 互补((AB)U)(A)
零一
(AB)(AB)右(5)(AB)CA(BC) 左差(AB)C结合A(BC)
D.MA(BC)差A(BC)(6)(AB)C(AC)B左差(AB)C结合A(BC)交换A(CB)结合(AC)B
差(AC)B右(7)(AB)C(AC)(BC)右(5)A(C(BC))差A(C(BC)) 分配A((CB)(CC))互补A((CB)U)
零一A(CB)交换A(BC)(5)(AB)C左
6.问在什么条件下,集合A,B,C满足下列等式
(1)A(BC)(AB)C左(AB)(AC)右若要右左,须CA(BC),
CA时等式成立
(2)ABA左右是显然的,AABAB,AB,
AB时等式成立
(3)ABBABB,BB,B,代入原式得A,
AB时等式成立
(4)ABBAABBA,只能AB,AB, BA,BA,AB时等式成立
(5)ABAB,若B,bB,
当bA,bABA矛盾;当bA,bABA矛盾
(6)ABAB右左是显然的,ABAB,AAB,ABBAB,BAABAB时等式成立
(7)(AB)(AC)A左(AB)(AC)A(BC)A(BC)A(BC)A
ABC时等式成立
(8)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC)
A(BC),AB,AC时等式成立
(9)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC)
A(BC)时等式成立
(10)(AB)(AC)((AB)(AC))((AB)(AC))(AB)(AC)(AB)(AC)
由(6)知,(AB)(AC),ABAC,ABAC时等式成立
(11)A(BA)BA(BA)(AB)(AA)(AB)U(AB)B
AB时等式成立
7.设A={a,b,{a,b},},求下列各式(1)φ∩{φ}=φ (2){φ}∩{φ}={φ} (3){φ,{φ}}-φ={φ,{φ}} (4){φ,{φ}}-{φ}= {{φ}} (5){φ,{φ}}-{{φ}}={φ} (6)A-{a,b}={{a,b}, φ} (7)A-φ = A (8)A-{φ}={a,b,{a,b}} (9)φ-A=φ (10){φ}-A=φ
8.在下列条件下,一定有B=C吗? (1) ABAC
否,例:A={1,2,3},B={4},C={3,4}, ABAC{1,2,3,4},而BC。
(2)ABAC
否,例:A={1,2,3},B={2,3},C={2,3,4} ABAC{2,3},而BC。
(3)ABAC
对,若BC,不妨,aB,aC,若aA,aAB,aAB,aAB,aAC,aAC,aAC; 若aA,aAB,aAB,aAB,aAC,aAC,aAC矛盾(4)ABAC且ABAC
bB,若bA,bABAC,bC,若bA,bABAC,bC,
BC,同理,CB,BC
9. (1) (AB)(BC)AB
证:a左,a(BC),aB,aB;a(AB),而aB,aA,aAB
(2)若A(BC)且B(AC),则B。
若B,aB(AC)(AC),aA(BC),aC,aB即aB,矛盾
10.化简
((ABC)(AB))((A(BC))A)(AB)A(AB)A
(AA)(BA)(BA)BA11. 设A={2,3,4},B={1,2},C={4,5,6},求 (1)AB{1, 3, 4} (2)ABC{1,3,5,6} (3)(AB)(BC){2,3,5,6}
12. 设A={1,2,3,4},B={1,2,5},求
(1) P(A)P(B){φ,{1},{2},{1,2}}
(2) P(A)P(B)
{φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}, {1,2,3,},{1,2,4,},{1,3,4,},{2,3,4},{1,2,3,4,},{5},{1,5}, {2,5},{1,2} }
(3)P(A)P(B)
{ {3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},
{2,3,4},{1,2,3,4} }
(4)P(A)P(B)
离散数学教学研究论文范文第6篇
第一章 命题逻辑
p38 习题一
1、2(1)(3)、3(1)(4)、4(2)(3)、6(2)、7(4)(6)、8(1)(3)(5) 补充题:将PQ化成与之等价的并仅含联结词的公式。
第二章 谓词逻辑
P70 习题二
2(2)(4)、3(1)(3)、4(3)(4)、10(4) 补充题:
1. 谓词符号化:
1) 所有的鱼都生活在水中。 2) 没有大于2的偶素数。 3) 并不是每个人都聪明。
2. 设个体域D={a,b},将一阶公式(x)(F(x)→(y)G(y))中的量词消除
3. 设个体域为整数集,令P(x,y):x+y=1;Q(x,y):xy>0,试求解下列命题的真假。
1) (x) (y)P(x,y).
2) (x) (y)Q(x,y).
4. 求前束范式:
1) (x)F(x)(x)R(x).
2) ((x)P(x)∨(y)Q(y))(x)R(x). 5. 证明:
前提:(x)(A(x) B(x)∧C(x)),(x)(A(x)∧D(x)) 结论:(x)(C(x)∧D(x))
6. 所有的整数均为有理数并且为实数,存在是整数又是奇数的数,因而存在是奇数又是实数的数。
写出上面推理的证明。(用谓词逻辑,写出用谓词表示的前提、结论和证明过程)
第三章 集合、关系与映射 P133 习题三:
7、
9、
11、17 补充题
1. AB,A∈B能否同时成立,说明原因
求集合A={a,{a}}的幂集
2. 证明:若BC,则P(B) P(C) 3. 如果A∪B=A∪C,是否有B=C?
如果A⊕B=A⊕C,是否有B=C?
4. 试求1到10000之间不能被4,5或6整除的整数个数. 5. 列出所有从A={a,b,c}到B={s}的关系,并指出集合A上的恒等关系和从A到B的全域关系. 5. 给出A上的关系及其关系图和矩阵表示.{|0≤x-y<3} A={0,1,2,3,4}
6. 已知S={a,b}. R ={〈x,y〉|x,y∈A∧xy∧A为集合族ρ(S)}.试写出关系R. 7. 已知: A={a,b,c}, R={〈a,b〉,〈a,c〉,〈b,c〉}该关系具有什么性质?
(自反,反自反,对称,反对称,传递性) 8.设A={a,b,c},R={〈a,b〉,〈a,c〉} 计算:r(R),sr(R),tr(R),str(R). 9. 设A是含有4个元素的集合,试求:
(1)在A上可以定义多少种对称关系?
(2)在A上可以定义多少种既是自反的,又是对称的关系?
(3)在A上可以定义多少种既不是自反的,也不是反自反的二元关系?
10. 设集合A={0,1,2,3,4}. R={|x+y=4,x,y∈A} ,S={|y-x=1,x,y∈A}.
试求:R◦S,R◦R,(R◦S)◦R,R◦(S◦R). 11. 证明:R是A上的传递关系R◦RR. 12. A={1,2,3,4,5},R={|x,y∈A∧x-y可被2整除},试问R是否是A上的等价关系?如果是,求出R的各等价类. 13. A={1,2,3,4,5},A上的划分∏={{1,2},{3,4},{5}},给出由∏所诱导出的A上的等价关系R的集合表达式. 14. 试给出一个单射但非满射的函数.(对某一集合而言) 15. 设f:N→N×N,f(n)=,则:
(1)说明f是否为单射和满射,并说明理由.
(2) f的反函数是否存在?并说明理由.
(3)求ranf.
16. 已知如果从无限集合A到集合B存在单射f,则B也是无限集合。
设X是无限集合,集合Y≠φ,证明:X与Y的笛卡儿积X×Y是无限集合。
第六章 代数结构
P247 习题六:4(1)(3)、
6、
16、21 补充题:
1. 以下集合和运算是否构成代数系统?如果构成,说明该系统是否满足结合律、交换律?求出该运算的幺元、零元和所有可逆元素的逆元. 1) P(B)关于对称差运算⊕,其中P(B)为幂集.
2) A={a,b,c},*运算如下表所示:
2. 设集合A={a,b},那么(1)在A上可以定义多少不同的二元运算?(2)在A上可以定义多少不同的具有交换律的二元运算?
3. 设A={1,2},B是A上的等价关系的集合. 1) 列出B的元素.
2) 给出代数系统V=的运算表. 3) 求出V的幺元、零元和所有可逆元素的逆元. 4) 说明V是否为半群、独异点和群?
4. 设A={a,b,c},构造A上的二元运算*,使得a*b=c,c*b=b,且*运算满足幂等律、交换律. 1) 给出关于*运算的一个运算表.
其中表中?位置可以是a、b、c。 2) *运算是否满足结合律,为什么? 5. 设是一个代数系统。
*是R上的一个二元运算,使得对于R(实数集合)中的任意元素a,b都有a*b=a+b+a·b(·和+为数集上的乘法和加法).
证明:: 是独异点. 6. 如果是半群,且*是可交换的.
证明:如果S中有元素a,b,使得a*a=a和b*b=b,则(a*b)*(a*b)=a*b.
7. 设是一个群,则a,b,c∈S。
试证明: 群G中具有消去律,即成立: 如果a·b=a·c ,b·a=c·a 那么b=c. 8. 设是群,a∈G .
现定义一种新的二元运算⊙:x⊙y=x*a*y,x,y∈G .
证明:也是群 .
9. 试写出模6加法群的每个子群及其相应的左陪集. 的运算表如下所示:
10. 设A={1,2,5,10,11,22,55,110}. 1) A关于整除关系是否构成偏序集?
2) 如果构成偏序集合,画出其对应的哈斯图. 3) 如果构成偏序集,该偏序集合构成哪种格? (分配格、有界格、有补格、布尔格). 第七题
图论
P295 习题七:
2、
9、10 补充题:
1. 是否存在7阶无向简单图G,其度序列为
1、
3、
3、
4、
6、
6、7.给出相应证明. 2. 求下图的补图
3. 1)试画一个具有5个顶点的自补图
2) 是否存在具有6个顶点的自补图,试说明理由。
4. 设图G为n(n>2且为奇数)阶无向简单图,证明:G与G的补图中奇度顶点个数相等. 5. 无向图G中只有2个奇度顶点u和v,u与v是否一定连通.给出说明或证明。 6. 图G如下图所示:
1) 写出上图的一个生成子图.(不唯一) 2) δ(G),κ(G),λ(G).
3) 说明:δ(G)=min{ d(v) | vV } ;κ(G)=min{ |V’| |V’是图G的点割集} ; λ(G)=min{ |E’| |E’是图G的边割集} 7. 在什么条件下无向完全图Kn为欧拉图?
8. 证明:有割边的图不是欧拉图. 9. 证明:有割边的图不是哈密尔顿图. 10. 树T有2个4度顶点,3个3度顶点,其余顶点全为树叶,问T有几片树叶? 11. 给出全部互不同构的4阶简单无向图的平面图形。