离散数学复习纲要

华南农业大学 离散数学 期末考试2013试卷及答案

华南农业大学期末考试试卷（A 卷） 2013-2014学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 ①本试题分为试卷与答卷2部分。试卷有四大题，共6页。 ②所有解答必须写在答卷上，写在试卷上不得分。 一、选择题（本大题共 25 小题，每小题 2 分，共 50 分） 1、下面语句是简单命题的为_____。 A 、3不是偶数 B 、李平既聪明又用功 C 、李平学过英语或日语 D 、李平和张三是同学 2、设 p:他主修计算机科学, q:他是新生，r:他可以在宿舍使用电脑，下列命题“除非他不是新生，否则只有他主修计算机科学才可以在宿舍使用电脑。”可以符号化为______。 A 、r q p →?∧? B 、r q p ?→∧? C 、r q p →?∧ D 、r q p ∧→ 3、下列谓词公式不是命题公式P →Q 的代换实例的是______。 A 、)()(y G x F → B 、),(),(y x yG y x xF ?→? C 、))()((x G x F x →? D 、)()(x G x xF →? 4、设个体域为整数集，下列公式中其值为 1的是_____。 A 、)0(=+??y x y x B 、)0(=+??y x x y C 、)0(=+??y x y x D 、)0(=+???y x y x

2 5、下列哪个表达式错误_____。 A 、 B x xA B x A x ∧??∧?)())(( B 、B x xA B x A x ∨??∨?)())(( C 、B x xA B x A x →??→?)())(( D 、)())((x xA B x A B x ?→?→? 6、下述结论错误的是____。 A 、存在这样的关系，它可以既满足对称性，又满足反对称性 B 、存在这样的关系，它可以既不满足对称性，又不满足反对称性 C 、存在这样的关系，它可以既满足自反性，又满足反自反性 D 、存在这样的关系，它可以既不满足自反性，又不满足反自反性 7、集合A 上的关系R 为一个等价关系，当且仅当R 具有_____。 A 、自反性、对称性和传递性 B 、自反性、反对称性和传递性 C 、反自反性、对称性和传递性 D 、反自反性、反对称性和传递性 8、下列说法不正确的是：______。 A 、R 是自反的，则2R 一定是自反的 B 、R 是反自反的，则2R 一定是反自反的 C 、R 是对称的，则2R 一定是对称的 D 、R 是传递的，则2R 一定是传递 9、设R 和S 定义在P 上，P 是所有人的集合，=R {x P y x y x ∧∈><,|,是y 的父亲}，=S {x P y x y x ∧∈><,|,是y 的母亲}，则关系{y P y x y x ∧∈><,|,是的x 外祖父}的表达式是：______。 A 、11--R R B 、11--S R C 、11--S S D 、11--R S 10、右图描述的偏序集中，子集},,{f e b 的上界为_____。 A 、c b , B 、b a , C 、b D 、c b a ,, 11、以下整数序列，能成为一个简单图的顶点度数序列的是_____。 A 、1，2，2，3，4，5

离散数学_教学大纲

《离散数学》课程教学大纲课程编号:02700013 课程名称：离散数学 英文名称：Discrete Mathematics 课程类型: 专业基础课 总学时：108 讲课学时：108 实验学时：0 学分：5 适用对象: 计算机科学与技术专业 先修课程：高等数学、线性代数等 一、课程简介 离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机科学的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且离散数学所提供的训练可以帮助学生提高抽象思维能力和逻辑推理能力，有益于学生严谨、完整、规范的科学态度的培养。为将来参与创新性的研究和开发工作打下坚实的基础。 二、课程性质、目的和任务 1.性质:本课程是为计算机专业本科开设的专业基础课。 2.目的:《离散数学》以研究离散量的结构和相互之间的关系为主要目标，在信息处理技术、计算机软硬件的设计等领域都有着广泛应用。 3.任务:通过这门课程的学习，要使学生掌握离散数学的基本概念和基本原理，以现代数学的方法，初步掌握处理离散结构所必须的一些基本数学工具和方法。同时，也要培养学生抽象思维、逻辑推理，符号演算和慎密概括的能力，从而使学生具有良好的专业理论素质，提高学生分析和解决实际问题的能力。 三、教学基本要求 通过本课程的学习，使学生了解和掌握关于离散量的基本概念及其相关理论，为后继课程的学习作必要的理论准备。基本要求：（1）学习数理逻辑最基本的内容，掌握命题逻辑及谓词逻辑的基本概念，掌握命题演算的方法，掌握命题推理及谓词推理的基本理论，并会用推理理论进行逻辑论证。（2）学习集合论的基本概念及性质，掌握集合运算及证明的基本理论和方法；学习二元关系的概念与性质，掌握等价关系和偏序关系，并使学生从更高层次理解函数。（3）学习代数系统的基本知识，掌握二元运算的定义和性质，了解代数系统的子代数和积代数、同态与同构等概念，掌握半群、幺半群、群、环、域和格、布尔代数等代数系统的定义及其性质。（4）学习图论的基本概念及其理论，主要掌握简单图和一些特殊图的性质，包括欧拉图和哈密尔顿图、二部图、平面图等。掌握树的基本概念及其相关运算。学会使用图论方法解决具体问题。

离散数学考试大纲

《离散数学》课程考试大纲 课程名称：离散数学 教学时数：56 考试对象： A08、C08计算机 一、考试内容及要求 1．考试范围： 命题演算及其形式系统、谓词演算及其形式系统、集合及其运算、关系、函数、群论、格和布尔代数。 2．考试要求： （一）命题演算及其形式系统 掌握命题的概念掌握命题公式的概念；熟练掌握利用求任意命题公式的析取范式、主析取范式、合取范式和主合取范式的方法。 （二）谓词演算及其形式系统 掌握两种量词及其用法；掌握谓词公式的定义；掌握基本的谓词演算的等价式和蕴涵式。 （三）集合及其运算 掌握集合的概念及表示法；理解两个集合相等的定义和充分必要条件；掌握子集、真子集、空集、全集、幂集的定义；熟练掌握集合的五种基本运算：并、交、补、差及其满足的性质。 （四）关系 掌握笛卡儿积的概念；深刻理解关系的两个定义；深刻理解关系的五种性质：自反、对称、传递、反对称和反自反；能够判断任给的关系具有哪些性质；熟练掌握关系的三种特殊运算：复合运算、逆运算和闭包运算；掌握二种特殊的关系：等价关系、序关系。 （五）函数 掌握函数的概念；特殊函数类；函数的合成；了解逆函数。 （六）群论 掌握代数系统的定义和有关基本概念；熟练掌握群的定义和群的性质；掌握子群及其陪集概念和性质；掌握同态与同构的概念和性质；熟练掌握群同态和同构的证明方法。 （七）格与布尔代数 掌握格和代数格的基本概念；掌握格的基本性质；掌握几种特殊格的基本概念和性质；能够判断分配格和有余格；利用格的概念和性质证明一些基本定理；熟练掌握布尔代数的基本概念和有关性质。 二、考试形式 闭卷考试

三、试卷结构 第一篇集合论约占25％ 第二篇数理逻辑约占30％ 第三篇群论15％ 第四篇格和布尔代数 30% 题型比例： 判断题30分占30%，命题的符号化表示18分占18%，改错题12分占12%，证明和应用题40分占40%。 四、说明 试题由任课教师出A、B卷随机抽取。

中国石油大学大学《离散数学》期末复习题及答案

《离散数学》期末复习题 一、填空题（每空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是阿贝尔群的元素，则-(a+b+c)= 。 10、一个图的哈密尔顿路是。 11、不能再分解的命题称为，至少包含一个联结词的命题称 为。 12、命题是。 13、如果p表示王强是一名大学生，则┐p表示。 14、与一个个体相关联的谓词叫做。 15、量词分两种：和。 16、设A、B为集合，如果集合A的元素都是集合B的元素，则称A是B 的。 17、集合上的三种特殊元是、 及。 18、设A={a, b}，则ρ(A) 的四个元素分别 是：，，，。

19、代数系统是指由及其上的或 组成的系统。 20、设是代数系统，其中是*1,*2二元运算符，如果*1,*2都满 足、，并且*1和*2满足，则称是格。 21、集合A={a,b,c,d}，B={b }，则A \ B= 。 22、设A={1, 2}, 则∣A∣= 。 23、在有向图中，结点v的出度deg+(v)表示，入度deg-(v)表示 以。 24、一个图的欧拉回路是。 25、不含回路的连通图是。 26、不与任何结点相邻接的结点称为。 27、推理理论中的四个推理规则 是、、、。 二、判断题（每题2分，共20分） 1、空集是唯一的。 2、对任意的集合A，A包含A。 3、恒等关系不是对称的，也不是反对称的。 4、集合{1,2,3,3}和{1,2,2,3}是同一集合。 5、图G中，与顶点v关联的边数称为点v的度数，记作deg(v)。 6、在实数集上，普通加法和普通乘法不是可结合运算。 7、对于任何一命题公式，都存在与其等价的析取范式和合取范式。 8、设（A,*）是代数系统，a∈A，如果a*a＝a，则称a为（A，*）的等幂元。 9、设f：A→B，g：B→C。若f，g都是双射，则gf不是双射。 10、无向图的邻接矩阵是对称阵。 11、一个集合不可以是另一个集合的元素。 12、映射也可以称为函数，是一种特殊的二元关系。 13、群中每个元素的逆元都不是惟一的。

离散数学总复习

总复习题 1. 设︱A ︱=5, ︱P(B)︱=512, ︱P(A ∩B)︱=8, 则︱A ⊕B ︱＝ , ︱A ∪B ︱＝ 。 2. 设p :选小王当班长，q ：选小李当班长，则选小王或小李中的一人当班长可符号化为____。 3. 命题公式根据赋值可分为________________、________________和______________三类。 4. 含N 个个命题变项的命题公式有______________组赋值，有_____________个真值。 5. ()A A B ∨∧=______________，()A A B ∧∨=__________________。 6. 设{|3,,14}A x x k k N k ==∈≤≤，则用列举法表示A =________________________。 7. 集合A ={1，2}的幂集P (A )与A 的笛卡尔积()P A A ?=____________________________ ____________________________________________________________________________。 8. 某无向图G 中，共有边15条，该图中共有5度顶点2个，4度顶点3个，剩下的均为2度顶 点，则该图中共有顶点 个。 9. 一个结点为n 的无向完全图，其边的数目为 。 10．已知是一个群，则这个群的幺元是 ，这个群当中，逆元和自身相等的元素有 。 11. 已知关系R 1＝{,,,},R 2={,}，写出下列关系 R 2?R 1= ,R 13 = 。 12、设Φ是一个空集，则下列之一哪一个不成立（ ）。 ①、Φ∈Φ ②、Φ?Φ ③、Φ∈{Φ} ④、Φ?{Φ} 13、如果命题公式G=P ∧Q ，则下列之一哪一个成立（ ）。 ①、G=?(P →Q) ②、G=?(P →?Q) ③、G=?(?P →Q) ④、G=?(?P →?Q) 14、设X 、Y 是两个集合，|X|＝n ，|Y|＝m ，则从X 到Y 可产生（ ）个二元关系。 ①、m n ②、n m ③、n m ? ④、2 m n ? 15、若复合映射τσ?是满射，则 ( )。 ①、τ是满射 ②、σ 是满射 ③、τ是单射 ④、 σ是单射 16、若是一个群，则运算“*”一定满足（ ）。 ①、交换律 ②、消去律 ③、幂等律 ④、分配律 17、量词的约束范围称为量词的（ ）。 ①、定义域 ②、个体域 ③、辖域 ④、值域 18、下列公式中，（ ）是析取范式。

大学离散数学期末重点知识点总结(考试专用)

1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={|x,y 属于A ，y 盖住x}； 9.极小元：集合A 中没有比它更小的元素(若存在可能不唯一)； 极大元：集合A 中没有比它更大的元素(若存在可能不唯一)； 最小元：比集合A 中任何其他元素都小(若存在就一定唯一)； 最大元：比集合A 中任何其他元素都大(若存在就一定唯一)； 10.前提：B 是A 的子集 上界：A 中的某个元素比B 中任意元素都大，称这个元素是B 的上界(若存在，可能不唯一)； 下界：A 中的某个元素比B 中任意元素都小，称这个元素是B 的下界(若存在，可能不唯一)； 上确界：最小的上界(若存在就一定唯一)； 下确界：最大的下界(若存在就一定唯一)； 6.函数 1.若|X|=m,|Y|=n,则从X 到Y 有mn 2种不同的关系，有m n 种不同的函数； 2.在一个有n 个元素的集合上，可以有2n2种不同的关系，有nn 种不同的函数，有n!种不同的双射； 3.若|X|=m,|Y|=n ，且m<=n ，则从X 到Y 有A m n 种不同的单射； 4.单射：f:X-Y ，对任意1x ,2x 属于X,且1x ≠2x ，若f(1x )≠f(2x )； 满射：f:X-Y ，对值域中任意一个元素y 在前域中都有一个或多个元素对应； 双射：f:X-Y ，若f 既是单射又是满射，则f 是双射； 5.复合函数：f og=g(f(x)); 5.设函数f:A-B ，g:B-C ，那么 ①如果f,g 都是单射，则f og 也是单射； ②如果f,g 都是满射，则f og 也是满射； ③如果f,g 都是双射，则f og 也是双射； ④如果f og 是双射，则f 是单射，g 是满射； 7.代数系统 1.二元运算：集合A 上的二元运算就是2A 到A 的映射； 2. 集合A 上可定义的二元运算个数就是从A ×A 到A 上的映射的个数，即从从A ×A 到A 上函数的个数，若|A|=2,则集合A 上的二元运算的个数为2*22=42=16种； 3. 判断二元运算的性质方法： ①封闭性：运算表内只有所给元素； ②交换律：主对角线两边元素对称相等； ③幂等律：主对角线上每个元素与所在行列表头元素相同； ④有幺元：元素所对应的行和列的元素依次与运算表的行和列相同； ⑤有零元：元素所对应的行和列的元素都与该元素相同； 4.同态映射：,,满足f(a*b)=f(a)^f(b),则f 为由到的同态映射；若f 是双射，则称为同构； 8.群 广群的性质：封闭性； 半群的性质：封闭性，结合律； 含幺半群(独异点)：封闭性，结合律，有幺元； 群的性质：封闭性，结合律，有幺元，有逆元； 2.群没有零元； 3.阿贝尔群(交换群)：封闭性，结合律，有幺元，有逆元，交换律； 4.循环群中幺元不能是生成元； 5.任何一个循环群必定是阿贝尔群； 10.格与布尔代数 1.格：偏序集合A 中任意两个元素都有上、下确界； 2.格的基本性质： 1) 自反性a ≤a 对偶: a ≥a 2) 反对称性a ≤b ^ b ≥a => a=b 对偶:a ≥b ^ b ≤a => a=b 3) 传递性a ≤b ^ b ≤c => a ≤c 对偶:a ≥b ^ b ≥c => a ≥c 4) 最大下界描述之一a^b ≤a 对偶 avb ≥a A^b ≤b 对偶 avb ≥b 5）最大下界描述之二c ≤a,c ≤b => c ≤a^b 对偶c ≥a,c ≥b => c ≥avb 6) 结合律a^(b^c)=(a^b)^c 对偶 av(bvc)=(avb)vc 7) 等幂律a^a=a 对偶 ava=a 8) 吸收律a^(avb)=a 对偶 av(a^b)=a 9) a ≤b <=> a^b=a avb=b 10) a ≤c,b ≤d => a^b ≤c^d avb ≤cvd 11) 保序性b ≤c => a^b ≤a^c avb ≤avc 12） 分配不等式av(b^c)≤(avb)^(avc) 对偶 a^(bvc)≥(a^b)v(a^c) 13）模不等式a ≤c <=> av(b^c)≤(avb)^c 3.分配格：满足a^(bvc)=(a^b)v(a^c)和av(b^c)=(avb)^(avc)； 4.分配格的充要条件：该格没有任何子格与钻石格或五环格同构； 5.链格一定是分配格，分配格必定是模格； 6.全上界：集合A 中的某个元素a 大于等于该集合中的任何元素，则称a 为格的全上界，记为1；(若存在则唯一) 全下界：集合A 中的某个元素b 小于等于该集合中的任何元素，则称b 为格的全下界，记为0；(若存在则唯一) 7.有界格：有全上界和全下界的格称为有界格，即有0和1的格； 8.补元：在有界格内，如果a^b=0,avb=1，则a 和b 互为补元； 9.有补格：在有界格内，每个元素都至少有一个补元； 10.有补分配格(布尔格)：既是有补格，又是分配格； 布尔代数：一个有补分配格称为布尔代数； 11.图论 1.邻接：两点之间有边连接，则点与点邻接； 2.关联：两点之间有边连接，则这两点与边关联； 3.平凡图：只有一个孤立点构成的图； 4.简单图：不含平行边和环的图； 5.无向完全图：n 个节点任意两个节点之间都有边相连的简单无向图； 有向完全图:n 个节点任意两个节点之间都有边相连的简单有向图； 6.无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边； 7.r-正则图：每个节点度数均为r 的图； 8.握手定理：节点度数的总和等于边的两倍； 9.任何图中，度数为奇数的节点个数必定是偶数个； 10.任何有向图中，所有节点入度之和等于所有节点的出度之和； 11.每个节点的度数至少为2的图必定包含一条回路； 12.可达：对于图中的两个节点i v ,j v ，若存在连接i v 到j v 的路，则称i v 与j v 相互可达，也称i v 与j v 是连通的；在有向图中，若存在i v 到j v 的路，则称i v 到j v 可达； 13.强连通：有向图章任意两节点相互可达； 单向连通：图中两节点至少有一个方向可达； 弱连通：无向图的连通；(弱连通必定是单向连通) 14.点割集：删去图中的某些点后所得的子图不连通了，如果删去其他几个点后子图之间仍是连通的，则这些点组成的集合称为点割集； 割点：如果一个点构成点割集，即删去图中的一个点后所得子图是不连通的，则该点称为割点； 15.关联矩阵：M(G)，mij 是vi 与ej 关联的次数，节点为行，边为列； 无向图：点与边无关系关联数为0，有关系为1，有环为2； 有向图：点与边无关系关联数为0，有关系起点为1终点为-1， 关联矩阵的特点： 无向图： ①行：每个节点关联的边，即节点的度； ②列：每条边关联的节点； 有向图： ③所有的入度(1)=所有的出度(0); 16.邻接矩阵：A(G)，aij 是vi 邻接到vj 的边的数目，点为行，点为列； 17.可达矩阵：P(G)，至少存在一条回路的矩阵，点为行，点为列； P(G)=A(G)+2A (G)+3A (G)+4A (G) 可达矩阵的特点：表明图中任意两节点之间是否至少存在一条路，以及在任何节点上是否存在回路； A(G)中所有数的和：表示图中路径长度为1的通路条数； 2A (G)中所有数的和：表示图中路径长度为2的通路条数； 3A (G)中所有数的和：表示图中路径长度为3的通路条数； 4A (G)中所有数的和：表示图中路径长度为4的通路条数； P(G)中主对角线所有数的和：表示图中的回路条数； 18.布尔矩阵：B(G)，i v 到j v 有路为1，无路则为0，点为行，点为列； 19.代价矩阵：邻接矩阵元素为1的用权值表示，为0的用无穷大表示，节点自身到自身的权值为0； 20.生成树：只访问每个节点一次，经过的节点和边构成的子图； 21.构造生成树的两种方法：深度优先；广度优先； 深度优先： ①选定起始点0v ； ②选择一个与0v 邻接且未被访问过的节点1v ； ③从1v 出发按邻接方向继续访问，当遇到一个节点所有邻接点均已被访问时，回到该节点的前一个点，再寻求未被访问过的邻接点，直到所有节点都被访问过一次； 广度优先： ①选定起始点0v ； ②访问与0v 邻接的所有节点v1,v2,……,vk,这些作为第一层节点； ③在第一层节点中选定一个节点v1为起点； ④重复②③，直到所有节点都被访问过一次； 22.最小生成树：具有最小权值(T)的生成树； 23.构造最小生成树的三种方法： 克鲁斯卡尔方法；管梅谷算法；普利姆算法； （1）克鲁斯卡尔方法 ①将所有权值按从小到大排列； ②先画权值最小的边，然后去掉其边值；重新按小到大排序； ③再画权值最小的边，若最小的边有几条相同的，选择时要满足不能出现回路，然后去掉其边值；重新按小到大排序； ④重复③，直到所有节点都被访问过一次； （2）管梅谷算法(破圈法) ①在图中取一回路，去掉回路中最大权值的边得一子图； ②在子图中再取一回路，去掉回路中最大权值的边再得一子图； ③重复②，直到所有节点都被访问过一次； （3）普利姆算法 ①在图中任取一点为起点1v ，连接边值最小的邻接点v2； ②以邻接点v2为起点，找到v2邻接的最小边值，如果最小边值比v1邻接的所有边值都小(除已连接的边值)，直接连接，否则退回1v ，连接1v 现在的最小边值(除已连接的边值)； ③重复操作，直到所有节点都被访问过一次； 24.关键路径 例2 求PERT 图中各顶点的最早完成时间, 最晚完成时间, 缓冲时间及关键路径. 解：最早完成时间 TE(v1)=0 TE(v2)=max{0+1}=1 TE(v3)=max{0+2,1+0}=2 TE(v4)=max{0+3,2+2}=4 TE(v5)=max{1+3,4+4}=8 TE(v6)=max{2+4,8+1}=9 TE(v7)=max{1+4,2+4}=6 TE(v8)=max{9+1,6+6}=12 最晚完成时间 TL(v8)=12 TL(v7)=min{12-6}=6 TL(v6)=min{12-1}=11 TL(v5)=min{11-1}=10 TL(v4)=min{10-4}=6 TL(v3)=min{6-2,11-4,6-4}=2 TL(v2)=min{2-0,10-3,6-4}=2 TL(v1)=min{2-1,2-2,6-3}=0 缓冲时间 TS(v1)=0-0=0 TS(v2)=2-1=1 TS(v3)=2-2=0 TS(v4)=6-4=2 TS(v5=10-8=2 TS(v6)=11-9=2 TS(v7)=6-6=0 TS(v8)=12-12=0 关键路径: v1-v3-v7-v8 25.欧拉路：经过图中每条边一次且仅一次的通路； 欧拉回路：经过图中每条边一次且仅一次的回路； 欧拉图：具有欧拉回路的图； 单向欧拉路：经过有向图中每条边一次且仅一次的单向路； 欧拉单向回路：经过有向图中每条边一次且仅一次的单向回路； 26.（1）无向图中存在欧拉路的充要条件： ①连通图；②有0个或2个奇数度节点； （2）无向图中存在欧拉回路的充要条件： ①连通图；②所有节点度数均为偶数； （3）连通有向图含有单向欧拉路的充要条件： ①除两个节点外，每个节点入度=出度； ②这两个节点中，一个节点的入度比出度多1，另一个节点的入；度比出度少1； （4）连通有向图含有单向欧拉回路的充要条件： 图中每个节点的出度=入度； 27.哈密顿路：经过图中每个节点一次且仅一次的通路； 哈密顿回路：经过图中每个节点一次且仅一次的回路； 哈密顿图：具有哈密顿回路的图； 28.判定哈密顿图（没有充要条件） 必要条件： 任意去掉图中n 个节点及关联的边后，得到的分图数目小于等于n ； 充分条件： 图中每一对节点的度数之和都大于等于图中的总节点数； 29.哈密顿图的应用：安排圆桌会议； 方法：将每一个人看做一个节点，将每个人与和他能交流的人连接，找到一条经过每个节点一次且仅一次的回路(哈密顿图)，即可； 30.平面图：将图形的交叉边进行改造后，不会出现边的交叉，则是平面图； 31.面次：面的边界回路长度称为该面的次； 32.一个有限平面图，面的次数之和等于其边数的两倍； 33.欧拉定理：假设一个连通平面图有v 个节点，e 条边，r 个面，则 v-e+r=2； 34.判断是平面图的必要条件：(若不满足，就一定不是平面图) 设图G 是v 个节点，e 条边的简单连通平面图，若v>=3，则e<=3v-6； 35.同胚：对于两个图G1,G2，如果它们是同构的，或者通过反复插入和除去2度节点可以变成同构的图，则称G1，G2是同胚的； 36.判断G 是平面图的充要条件： 图G 不含同胚于K3.3或K5的子图； 37.二部图：①无向图的节点集合可以划分为两个子集V1，V2； ②图中每条边的一个端点在V1，另一个则在V2中； 完全二部图：二部图中V1的每个节点都与V2的每个节点邻接； 判定无向图G 为二部图的充要条件： 图中每条回路经过边的条数均为偶数； 38.树：具有n 个顶点n-1条边的无回路连通无向图； 39.节点的层数：从树根到该节点经过的边的条数； 40.树高：层数最大的顶点的层数； 41.二叉树： ①二叉树额基本结构状态有5种； ②二叉树内节点的度数只考虑出度，不考虑入度； ③二叉树内树叶的节点度数为0，而树内树叶节点度数为1； ④二叉树内节点的度数=边的总数(只算出度)；握手定理“节点数=边的两倍”是在同时计算入度和出度的时成立； ⑤二叉树内节点的总数=边的总数+1； ⑥位于二叉树第k 层上的节点，最多有12-k 个(k>=1)； ⑦深度为k 的二叉树的节点总数最多为k 2-1个，最少k 个(k>=1)； ⑧如果有0n 个叶子，n2个2度节点，则0n =n2+1； 42.二叉树的节点遍历方法： 先根顺序（DLR ）； 中根顺序（LDR ）； 后根顺序（LRD ）； 43.哈夫曼树：用哈夫曼算法构造的最优二叉树； 44.最优二叉树的构造方法： ①将给定的权值按从小到大排序； ②取两个最小值分支点的左右子树(左小右大)，去掉已选的这两个权值，并将这两个最小值加起来作为下一轮排序的权值； ③重复②，直达所有权值构造完毕； 45.哈夫曼编码：在最优二叉树上，按照左0右1的规则，用0和1代替所有边的权值； 每个节点的编码：从根到该节点经过的0和1组成的一排编码；

离散数学自学考试复习题

离散数学 复习题 1．设A 和B 都是命题，则A →B 的真值为假当且仅当 。 A. A 为假，B 为真 B. A 为假，B 为假 C. A 为真，B 为真 D. A 为真，B 为假 2．下列公式中为重言式的是 。 A. P →(P ∨Q ∨R) B. ┐(Q →P)∧P C. (P →Q)→(Q →┐P) D. (P ∧┐P)←→Q 3．设A ＝{a ，{a}}，P(A)表示A 的幂集，下面各式中错误的是 。 A. {a}∈P(A) B. {a}?P(A) C. {{a}}∈P(A) D. {{a}}?P(A) 4．设A ＝{1,2,3,4,5,6}上的关系为R ＝{|x>y}，则R -1具有 。 A. 对称性 B. 自反性 C. 反自反性、反对称性、传递性 D. 以上都不对 5．设R 是非空集合A 上的二元关系，则R 的对称闭包S(R)＝ 。 A. R ∪I A B. R ∪R C C. R-I A D. R ∩R C 6．映射的复合运算满足 。 A. 交换律 B. 结合律 C. 幂等律 D. 分配律 7．设R 、I 分别是实数集合和整数集合，-、×、/ 分别是普通的减法、乘法 和除法运算，则 是半群。 A. B. C. D. 8．在一个格中，对任意的a ，b ，c ∈A ，都有 。 A. a ∨(b ∧c)≤(a ∨b)∧(a ∨c) B. a ∧(b ∨c)≤(a ∧b)∨(a ∧c) C. a ∨(b ∧c)＝(a ∨b)∧(a ∨c) D. A 、B 、C 都正确 9．无向简单图G 中结点间的连通关系是 。 A. 偏序关系 B. 等价关系 C. 既是偏序关系又是等价关系 D. A 、B 、C 都错误 10.设G 是一个有v 个结点e 条边的连通简单平面图，若v ≥3，则 。 A. v ≤3e-6 B. e ≤3v-6 C. v ≤3e+6 D. e ≤3v+6 11．设P 和Q 是命题，P ，?P ∨Q ?Q 。 ( ) 12．设A 和B 是集合，A-B ＝A 当且仅当B ＝Φ。 ( ) 13．一个不是自反的关系，一定是反自反的。 ( ) 14．若A 和B 是任意两个集合，则A ×B ＝B ×A 。 ( ) 15．关系f ＝{|m,n ∈N,m+n ＜10}是函数，其中N 是自然数集合。 ( ) 16．集合B 是集合A 的真子集，则K[B]＜K[A]。 ( ) 17．整环一定是域。 ( ) 18．任何两个具有2n 个元素的有限布尔代数都是同构的。 ( ) 19．已知无向连通图G 中有n 个结点，m 条边，G 中无回路，则m ＝n-1。( ) 20.如果两个图的结点数相同、边数相等、度数相同的结点数目也相等，那么这两个图是同构的。 ( ) 21.设命题P 表示“我今天将去公园”，命题Q 表示“天下雨”，则命题“我今天去公园，除非下雨”可以符号化为 (1) 。

离散数学》双语课程教学大纲

离散数学》双语课程教学大纲 一、课程编号：040510 二、课程类型：必修 课程学时：理论教学 72学时 / 4.5学分。 适用专业：信息与计算科学专业。 先修课程：线性代数、概率论、高等数学等。 后续课程：编译原理、操作系统、数据结构、数据库等。 三、课程性质与任务 《离散数学》是信息与计算科学中基础理论的核心课程。该课程采用双语教学形式，教材是国外原版英语教材。通过本课程的学习，主要培养学生的抽象思维能力、严密的逻辑推理能力、阅读外文科技文献能力和专业英语写作能力。并为学生今后处理离散信息、离散建模、软件开发、计算机硬件系统设计、程序设计的时间和空间复杂度分析等提供理论指导基础，是学生从事信息科学的实际工作必备数学工具。 四、教学主要内容及学时分配

五、教学基本要求 了解离散数学所涵盖的内容及背景思想；理解离散数学组的数学思想和基本概念。掌握离散数学常用的基本方法、手段、技巧，并具备一定的分析论证能力和较强的利用离散数学解决实际问题能力。具体要求有： （1 ）理解子集、空集、全集、集合相等、幂集等基本概念；掌握集合的两种表示法。 （2）熟练掌握集合的交、并、差补运算；能通过文氏图理解与掌握集合的有关运算；了解包含排斥定理及其简单应用。 （3）熟练掌握集合运算的基本定律，并能熟练地应用这些定律证明集合恒等式。（4）掌握逻辑代数的基本理论和方法，理解命题﹑复合命题及真值表的概念，熟练掌握逻辑运算符‘非’﹑‘合取’ ﹑‘析取’﹑‘蕴涵’﹑及 ‘存在’﹑‘任意’等量词的定义及使用；理解条件语句的概念；理解等价。掌握一些常见的逻辑推理方法。

（5）熟练掌握乘法原理﹑加法原理﹑排列﹑组合﹑鸽笼原理及递归式，会用组合计数思想的方法计算简单的古典概率问题。 （6）理解序偶与笛卡尔积的概念；理解 n 元组与 n 个集合笛卡尔集的概念。 深刻理解关系的基本概念；掌握二元关系的关系矩阵与关系图。熟练掌握关系的自反性、对称性、反对称性和传递性四种性质并熟练掌握其求法。 深刻理解二元关系的自反闭包、对称闭包和传递闭包的概念并熟练掌握其求法。熟练掌握等价关系的判定与相关等价类的求法。了解关系的计算机表示﹑关系的运算﹑传递闭包及Warshall算法。 （7）理解映射、满射、单射、双射的概念并熟练掌握其判定方法；了解复合映射与逆映射的概念及求法。 （8）理解有向树，无向树，根数，标定树的定义及性质；掌握极小生成树算法； 了解生成树搜索法。 （9）理解无向图，哈密顿圈及哈密顿路，传输网络，匹配问题，图的着色的定义及性质；掌握欧拉环游及欧拉通路，最大流问题的定义﹑性质及算法。 掌握有关哈密顿图的一些必要和充分条件。 六、对学生课外作业的要求 本课程概念多、比较抽象、定理证明和应用有一定难度，为了学生进一步理解课堂教学内容，拟布置一定数量的课外习题为宜，教师批改作业本的 2/3, 并安排时间上习题课。各章节习题量分布如下： 七、教材及主要参考书

自考离散数学02324真题含答案(2009.4-2016.4年整理版)

全国2009年4月自学考试离散数学试题（附答案） 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 2．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟 C．如果1+2=3，那么雪是黑的D．如果1+2=5，那么雪是黑的 3．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q）D．?（? P∨? Q） 4．命题公式（P∧（P→Q））→Q是（） A．矛盾式B．蕴含式 C．重言式D．等价式 5．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无 6．在公式（x ?）F（x，y）→（?y）G（x，y）中变元x是（） A．自由变元B．约束变元 C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元 7．集合A={1，2，…，10}上的关系R={|x+y=10，x∈A，y∈A}，则R的性质是（） A．自反的B．对称的 C．传递的、对称的D．反自反的、传递的 8．若R和S是集合A上的两个关系，则下述结论正确的是（） A．若R和S是自反的，则R∩S是自反的 B．若R和S是对称的，则R S是对称的 C．若R和S是反对称的，则R S是反对称的 D．若R和S是传递的，则R∪S是传递的 9．R={<1，4>，<2，3>，<3，1>，<4，3>}，则下列不是 ．．t（R）中元素的是（） A．<1，1> B．<1，2> C．<1，3> D．<1，4>

《人工智能》课程教学大纲

人工智能》课程教学大纲 、课程基本信息 二、课程教学目标 《人工智能》是计算机科学与技术专业的一门专业拓展课，通过本课程的学习使本科生对人工智能的基本内容、基本原理和基本方法有一个比较初步的认识，掌握人工智能的基本概念、基本原理、知识的表示、推理机制和智能问题求解技术。启发学生开发软件的思路，培养学生对相关的智能问题的分析能力，提高学生开发应用软件的能力和水平。 三、教学学时分配

四、教学内容和教学要求 第一章人工智能概述（3 学时） （一）教学要求 1.掌握人工智能的基本概念； 2.理解人工智能的发展状况。 3.理解人工智能的基本技术； 4.了解人工智能的研究途径与方法； 5.了解人工智能的分支领域； （二）教学重点与难点教学重点：人工智能的基本技术。教学难点：三大学派的研究途径与方法。 （三）教学内容 第一节人工智能的基本概念 1.什么是人工智能 2.强人工智能与弱人工智能 3.脑智能和群智能 4.符号智能和计算智能 第二节人工智能发展概况 1.人工智能学科的产生

2.人工智能学科的发展 3.人工智能三大学派 第三节人工智能研究途径与方法 1.人工智能的研究目标 2.人工智能的研究方法 3.人工智能的研究内容 第四节人工智能基本技术 1.推理技术 2.搜索技术 3.知识库技术 4.归纳技术 5.联想技术第五节人工智能的应用 1.难题求解 2.机器定理证明 3.自动程序设计 4.模式识别 5.机器翻译 6.智能管控 7.智能决策 8.智能人机接口 第六节人工智能的影响 1.人工智能对人类的影响 2.人工智能对社会的影响 本章习题要点：对基本概念、技术、方法的理解。 第二章智能程序设计语言（5 学时）（一）教学要求 1．了解常见的几种人工智能程序设计语言；

离散数学复习题

一、选择题： 1.下列句子是命题的是( )。 A. 你喜欢我吗? B. 这里的景色真美啊! C. 2x = 9。 D. 明年国庆节是晴天。 2.设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为( )。 ∧) A. ?P∧?Q B. ?(P Q C. ?(P?Q) D. ?(?P∨?Q) 3.下列语句不是 ．．命题的是( )。 A.黄金是非金属。 B.要是他不上场，我们就不会输。 C.他跑100米只用了10秒钟，你说他是不是运动健将呢? D.他跑100米只用了10秒钟，他是一个真正的运动健将。 4.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )。 A.P∨Q B.P∧?Q C.P→?Q D.P∨?Q 5.下列句子不是 ．．命题的是( )。 A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 6.在命题演算中，语句为真为假的一种性质称为( )。 A. 真值 B. 陈述句 C. 命题 D. 谓词 7.命题公式?(P∧Q)→R的成真指派是( )。 A. 000，001，110 B. 001，011，101，110，111 C. 全体指派 D. 无 8.下列命题中，不正确的是( )。 ∈?,{{?}}} A.{?}{ ∈?,{?}} B.{?}{ C.{?}?{?,{?}} D. ??{?,{?}} 9.命题公式P∧(Q∨? R)的成真指派是( )。 A.110，111，100 B.110，101，011 C.所有指派 D.无 ∨?( )。 10.设P,Q,R是命题公式,则P→R，Q→R，P Q A. P B. Q C. R D. ?R 11.下列是两个命题变元p，q的小项是( ) ∨C．?p q ∨∨ ∧D．?p p q A．p∧?p q ∧B．?p q 12.关于命题变元P和Q的大项M01表示( )。 ∨ C.P∨?Q D.P∧?Q ∧ B.?P Q A.?P Q 13.设P：明天天晴；q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为( ) ?p→?q C. ?p??q D. ?p→q A. p→?q B. 14.下列命题公式是永真式的是( ) (p→q)∨q D. (p∨p)∧(p→?p) ?(p→q)∧q C. A. (p∧?p)?q B.