离散数学考试大纲

时间:2019-05-15 01:39:04下载本文作者:会员上传
简介:写写帮文库小编为你整理了多篇相关的《离散数学考试大纲》,但愿对你工作学习有帮助,当然你在写写帮文库还可以找到更多《离散数学考试大纲》。

第一篇:离散数学考试大纲

武汉理工大学2011年博士入学考试《离散数学》考试大纲

一、考试要求共济

要求考生系统地掌握离散数学的基本概念、基本定理和方法,具有较强的逻辑思维和抽象思维能力,能够灵活运用所学的内容和方法解决实际问题。考

二、考试内容济

1、数理逻辑济

1)命题和联结词,谓词与量词,合适公式,赋值,解释与指派,范式共

2)命题形式化,等价式与对偶式,蕴含式,推理与证明

3)证明方法3

4)数学归纳法

2、集合论院

1)集合代数,笛卡尔乘积,关系与函数,关系的性质与运算

2)等价关系,划分共济

3)偏序关系与偏序集,格辅导

3、计数336260 37

1)排列与组合,容斥原理,鸽巢原理共

2)离散概率正门

3)函数的增长与递推关系院

4、图论 共济网

1)欧拉图与哈密顿图,平面图与对偶图,二部图与匹配,图的着色021-

2)树,树的遍历,最小生成树正门

3)最短路经,最大流量

5、形式语言与自动机 院

1)语言与文法,正则表达式与正则集

2)有限状态自动机,自动机与正则语言

6、代数系统

1)二元运算,群与半群,积群与商群,同态与同构

2)群与编码

3)格与布尔代数,环与域

三、试卷结构

1、考试时间为3小时,满分100分。

2、题目类型:计算题、简答题和证明题。

参考书

1.离散数学,胡新启,武汉大学出版社,2007年。

2.离散数学,尹宝林、何自强、许光汉、檀凤琴等,高等教育出版社,1998年。

3.离散数学及其应用,Kenneth H.Rosen,机械工业出版社,2002年。

第二篇:离散数学考试范围

第一部分 简单命题符号化,求主析取范式,判断公式类型(重言式,矛盾式,可满足式)量词消去规则。命题逻辑推理规则

带全称量词和存在量词的命题逻辑推理的构造和证明 第二部分

集合基本运算,文氏图 有序对的基本知识,笛卡儿积,特征函数

函数的性质(单射,满射,双射)

集合的基本概念(交集,并集,幂集,定义域,值域)

给出关系图,画出r(R),s(R),t(R)等价关系及等价划分 集合相等证明

从A到B的函数的性质

关系的性质(自反,对称,传递)偏序关系和哈斯图

A卷

1、选择10题(2*10=20分)

2、填空8题(1*15=15分)

3、综合题(6题,39分)(1)前束范式

(2)偏序关系和哈斯图(3)文氏图(4)关系的闭包

(5)用真值表判断公式的成真赋值(6)量词消去

4、证明题(3题,共26分)自然推理系统证明(第三章)集合相等证明

命题逻辑推理证明(第五章)B卷

1、填空10题(2*10=20分)

2、选择10题(1*10=10分)

3、综合题(6题,44分)(1)主析取范式判断公式类型(2)量词消去,求公式真值(3)集合计算(4)量词消去(5)前束范式

(6)偏序关系和哈斯图

4、推理填空题(8分)

5、证明题(18分)集合相等证明 命题逻辑推理证明

第三篇:上海海事大学离散数学考试提纲

复习提纲:

一、判断哪些是命题

*命题的表示(联结词),符号化命题(样题2)*真值表(用来证明)

*等价式的证明(用已知的等价式推导)(样题3)蕴涵的证明(样题4)对偶式(化对偶式)

*写出主析(合)取范式(真值表,公式推导)(样题5)*命题的推理(真值表,直接,间接)(样体6)

二、*谓词公式的翻译(存在,全称)(p60习题2,批p61例题,批p62习题1)约束变元及其换名(p63例题1)等价式和蕴涵式(转换,扩展和收缩,分配,多量词)(p66-p70)前束范式(p73例题)*推理 p76-p77

三、*集合的表示

*集合的运算(。。幂集)*包含排斥

序偶(同集合)

关系(定义域,值域,特殊的关系,*关系的表示,特别是矩阵)*关系的性质(5大性质,)

复合关系和逆关系 p114例题1,p115例题5,p118例题4 关系的闭包运算(三个)p121例题1,p124例题4 集合的划分和覆盖(能判断哪些是划分和覆盖)

*等价关系(判定,要会用等价关系对集合划分即写出等价类)p131,132例题, *序关系(判定,哈斯图,链反链)p140,141例题, *求极大(小),最大(小),上(下)界,上(下)确界 p146习题6

四、*判定是否函数,满,入,双

*逆函数、复合函数(判定原函数是满,入,双复合后是否满,入,双)判定二个集合是否等势(构造双射函数)有限集,无限集(可数,不可数)

自然数 实数集

可列

五、*代数运算的表示(包括运算表)p189例题

*判断代数系统的运算性质:封闭,可交换,可结合,可分配,吸收率,等幂性 *代数系统的幺元和零元(唯一性证明),逆元 p184 半群的判断,独异点的判断

*群与子群的判断,群的性质证明 交换群的性质,循环群的性质 *定理5-7.1,意义,性质

任何一个群不是4阶循环群就是Klein群

*同构同态的判断(满,单一,)p214例题,同余 环,域判断,同态象

六、*格、子格的定义

*并,交运算的定义及其性质 p233例题 p241例题 p242习题 格的同态与同构

*分配格的性质,p244例2,3 ,有补格的性质,补元素 p252习题1 布尔代数,布尔表达式及其范式

七、图简单性质(点边数目关系),图的同构判断,生成子图,补图 路,回路,通路,连通,点割集(割点),边割集(割边)及其性质

有向图的单侧连通(分图),强连通(分图),弱连通(分图)p287习题8 *图的矩阵(邻接,可达性,完全关联)p290例题1, *欧拉图的判定,H图的判定,p306,p310,样体21平面图的判定(K3,3 K5)p317习题5 对偶图和着色 p318,p319 p321习题 *树的等价定义和证明

*最小生成树 p327习题6 *根树p327习题2,叉树,m叉数转换成二叉树

第四篇:离散数学考试题型之定理应用题

下面我们就列出常用的几种应用:

证明等价关系:即要证明关系有自反、对称、传递的性质。

证明偏序关系:即要证明关系有自反、反对、传递的性质(特殊关系的证明就列出来两种,要证明剩下的几种只需要结合定义来进行)。

证明满射:函数f:X®Y,即要证明对于任意的yÎY,都有xÎX,使得f(x)=y。

证明入射:函数f:X®Y,即要证明对于任意的x1,x2ÎX,且x1≠x2,则f(x1)≠f(x2);或者对于任意的f(x1)=f(x2),则有x1=x2。

证证明集合等势:即明两个集合中存在双射。有三种情况:第一,证明两个具体的集合等势,用构造法,或者直接构造一个双射,或者构造两个集合相互间的入射。

第二,已知某个集合的基数,如果为א,就设它和R之间存在双射f,然后通过f的性质推出另外的双射,因此等势;如果为א0,则设和N之间存在双射。第三,已知两个集合等势,然后再证明另外的两个集合等势,这时,先设已知的两个集合存在双射,然后根据剩下题设条件证明要证的两个集合存在双射。

证明群:即要证明代数系统封闭、可结合、有幺元和逆元(同样,这一部分可以作为证明题的概念更多,要结合定义把它们全部理解透彻)。

证明子群:虽然子群的证明定理有两个,但如果考证明子群的话,通常是考第二个定理,即设是群,S是G的非空子集,如果对于S中的任意元素a和b有a*b-1ÎS,则是的子群。对于有限子群的相关证明,则可以考虑第一个定理。

证明正规子群:若是一个子群,H是G的一个子集,即要证明对于任意的aÎG,有aH=Ha,或者对于任意的hÎH,有a-1 *h*aÎH。这是最常见的题目中所使用的方法。

证明格和子格:子格没有条件,因此和证明格一样,证明集合中任意两个元素的最大元和最小元都在集合中。

第五篇:离散数学考试试题(A卷及答案)

离散数学考试试题(A卷及答案)

一、(10分)判断下列公式的类型(永真式、永假式、可满足式)? 1)((PQ)∧Q)((Q∨R)∧Q)2)((QP)∨P)∧(P∨R)3)((P∨Q)R)((P∧Q)∨R)解:1)永真式;2)永假式;3)可满足式。

二、(8分)个体域为{1,2},求xy(x+y=4)的真值。

解:xy(x+y=4)x((x+1=4)∨(x+2=4))

((1+1=4)∨(1+2=4))∧((2+1=4)∨(2+1=4))(0∨0)∧(0∨1)1∧10

三、(8分)已知集合A和B且|A|=n,|B|=m,求A到B的二元关系数是多少?A到B的函数数是多少?

解:因为|P(A×B)|=2|A×B|=2|A||B|=2mn,所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn,所以A到B的函数mn个。

四、(10分)已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>},求r(R)、s(R)和t(R)。

解:r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>} t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}

五、(10分)75个儿童到公园游乐场,他们在那里可以骑旋转木马,坐滑行铁道,乘宇宙飞船,已知其中20人这三种东西都乘过,其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元,公园游乐场总共收入70元,求有多少儿童没有乘坐过其中任何一种。

解 设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合,|A∩B∩C|=20,|A∩B|+|A∩C|+|B∩C|-2|A∩B∩C|=55,|A|+|B|+|C|=70/0.5=140。

由容斥原理,得

|A∪B∪C|=|A|+|B|+|C|―|A∩B|―|A∩C|―|B∩C|+|A∩B∩C| 所以

|A∩B∩C|=75-|A∪B∪C|=75-(|A|+|B|+|C|)+(|A∩B|+|A∩C|+|B∩C|-2|A∩B∩C|)+|A∩B∩C|=75-140+55+20=10 没有乘坐过其中任何一种的儿童共10人。

六、(12分)已知R和S是非空集合A上的等价关系,试证:1)R∩S是A上的等价关系;2)对a∈A,[a]R∩S=[a]R∩[a]S。

解:x∈A,因为R和S是自反关系,所以∈R、∈S,因而∈R∩S,故R∩S是自反的。

x、y∈A,若∈R∩S,则∈R、∈S,因为R和S是对称关系,所以因∈R、∈S,因而∈R∩S,故R∩S是对称的。x、y、z∈A,若∈R∩S且∈R∩S,则∈R、∈S且∈R、∈S,因为R和S是传递的,所以因∈R、∈S,因而∈R∩S,故R∩S是传递的。

总之R∩S是等价关系。

2)因为x∈[a]R∩S∈R∩S∈R∧∈S x∈[a]R∧x∈[a]S x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

七(10分)设A、B、C、D是集合,f是A到B的双射,g是C到D的双射,令h:A×CB×D且∈A×C,h()=。证明h是双射。

证明:1)先证h是满射。

∈B×D,则b∈B,d∈D,因为f是A到B的双射,g是C到D的双射,所以存在a∈A,c∈C,使得f(a)=b,f(c)=d,亦即存在∈A×C,使得h()=,所以h是满射。

2)再证h是单射。

∈A×C,若h()=h(),则,所以f(a1)=f(a2),g(c1)=g(c2),因为f是A到B的双射,g是C到D的双射,所以a1=a2,c1=c2,所以,所以h是单射。综合1)和2),h是双射。

八、(12分)是个群,u∈G,定义G中的运算“”为ab=a*u-1*b,对任意a,b∈G,求证:也是个群。

证明:1)a,b∈G,ab=a*u-1*b∈G,运算是封闭的。

2)a,b,c∈G,(ab)c=(a*u-1*b)*u-1*c=a*u-1*(b*u-1*c)=a(bc),运算是可结合的。3)a∈G,设E为的单位元,则aE=a*u-1*E=a,得E=u,存在单位元。

4)a∈G,ax=a*u-1*x=E,x=u*a-1*u,则xa=u*a-1*u*u-1*a=u=E,每个元素都有逆元。所以也是个群。

九、(10分)已知:D=,V={1,2,3,4,5},E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>},求D的邻接距阵A和可达距阵P。

解:D的邻接距阵A和可达距阵P如下:

A= 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0

0 0 1 0 0

P= 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1

十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。

解:最优二叉树为

权=148

离散数学考试试题(B卷及答案)

一、(10分)求命题公式(P∧Q)(PR)的主合取范式。

解:(P∧Q)(PR)((P∧Q)(PR))∧((PR)(P∧Q))((P∧Q)∨(P∧R))∧((P∨R)∨(P∨Q))(P∧Q)∨(P∧R)(P∨R)∧(Q∨P)∧(Q∨R)

(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)M1∧M3∧M4∧M5

二、(8分)叙述并证明苏格拉底三段论

解:所有人都是要死的,苏格拉底是人,所以苏格拉底是要死的。符号化:F(x):x是一个人。G(x):x要死的。A:苏格拉底。命题符号化为x(F(x)G(x)),F(a)G(a)证明:

(1)x(F(x)G(x))P(2)F(a)G(a)T(1),US(3)F(a)P(4)G(a)T(2)(3),I

三、(8分)已知A、B、C是三个集合,证明A∩(B∪C)=(A∩B)∪(A∩C)证明:∵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)

四、(10分)已知R和S是非空集合A上的等价关系,试证:1)R∩S是A上的等价关系;2)对a∈A,[a]R∩S=[a]R∩[a]S。

解:x∈A,因为R和S是自反关系,所以∈R、∈S,因而∈R∩S,故R∩S是自反的。

x、y∈A,若∈R∩S,则∈R、∈S,因为R和S是对称关系,所以因∈R、∈S,因而∈R∩S,故R∩S是对称的。

x、y、z∈A,若∈R∩S且∈R∩S,则∈R、∈S且∈R、∈S,因为R和S是传递的,所以因∈R、∈S,因而∈R∩S,故R∩S是传递的。

总之R∩S是等价关系。

2)因为x∈[a]R∩S∈R∩S

∈R∧∈S x∈[a]R∧x∈[a]S x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

五、(10分)设A={a,b,c,d},R是A上的二元关系,且R={},求r(R)、s(R)和t(R)。

解 r(R)=R∪IA={} s(R)=R∪R={} R={} R={} R={}=R

t(R)=R={} i1i

4232-

1六、(15分)设A、B、C、D是集合,f是A到B的双射,g是C到D的双射,令h:A×CB×D且∈A×C,h()=。证明h是双射。

证明:1)先证h是满射。

∈B×D,则b∈B,d∈D,因为f是A到B的双射,g是C到D的双射,所以存在a∈A,c∈C,使得f(a)=b,f(c)=d,亦即存在∈A×C,使得h()=,所以h是满射。

2)再证h是单射。

∈A×C,若h()=h(),则,所以f(a1)=f(a2),g(c1)=g(c2),因为f是A到B的双射,g是C到D的双射,所以a1=a2,c1=c2,所以,所以h是单射。

综合1)和2),h是双射。

七、(12分)设是群,H是G的非空子集,证明的子群的充要条件是若a,bH,则有a*bH。

证明: a,b∈H有b∈H,所以a*b∈H。a∈H,则e=a*a∈H-1-

1-1-1a=e*a∈H ∵a,b∈H及b∈H,∴a*b=a*(b)∈H ∵HG且H≠,∴*在H上满足结合律 ∴的子群。

八、(10分)设G=是简单的无向平面图,证明G至少有一个结点的度数小于等于5。

解:设G的每个结点的度数都大于等于6,则2|E|=d(v)≥6|V|,即|E|≥3|V|,与简单无向平面图-

1-1

-1-1-1的|E|≤3|V|-6矛盾,所以G至少有一个结点的度数小于等于5。九.G=,A={a,b,c},*的运算表为:(写过程,7分)

(1)G是否为阿贝尔群?

(2)找出G的单位元;(3)找出G的幂等元(4)求b的逆元和c的逆元 解:(1)(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b)(b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c)所以G是阿贝尔群

(2)因为a*a=a a*b=b*a=b a*c=c*a=c 所以G的单位元是a(3)因为a*a=a 所以G的幂等元是a(4)因为b*c=c*b=a,所以b的逆元是c且c的逆元是b

十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。

解:最优二叉树为

权=148 5

下载离散数学考试大纲word格式文档
下载离散数学考试大纲.doc
将本文档下载到自己电脑,方便修改和收藏,请勿使用迅雷等下载。
点此处下载文档

文档为doc格式


声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:645879355@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。

相关范文推荐

    小学数学考试大纲

    2018年安徽省中小学新任教师公开招聘统一笔试 小学数学学科考试大纲 一、考试性质 安徽省中小学新任教师公开招聘考试为全省统一组织的公开性选拔考试,是落实“省考、县管、......

    高等数学考试大纲

    高等数学考试大纲 2013年6月1.函数 极限与连续 函数的概念及表示法 函数的有界性、单调性、周期性和奇偶性 复合函数、反函数、分段函数和隐函数 基本初等函数的概念及性质......

    高等数学考试大纲

    演讲稿 工作总结 调研报告 讲话稿 事迹材料 心得体会 策划方案 高等数学考试大纲 2011年山东省专升本高等数学(公共课)考试要求 总要求:考生应了解或理解“高等数学”中函数、......

    江西省数学考试大纲小学部

    江西省数学考试大纲(仅供参考) (小学部) 第一部分学科专业基础 一、函数的极限和连续 (一)考试内容 函数及其性质;初等函数;数列的极限和函数的极限;极限的性质;无穷小量和无穷大量;两......

    云南省高等数学考试大纲

    云南省普通类“专升本”《高等数学》考试大纲 一、 函数、极限、连续 1. 理解函数概念,会求函数的定义域,了解分段函数。 2. 了解反函数和复合函数概念。 3. 熟念基本初等函数的......

    2018高考数学考试大纲

    Ⅰ.考核目标与要求一、知识要求 知识是指《普通高中数学课程标准(实验)》(以下简称《课程标准》)中所规定的必修课程、选修课程系列2和系列4中的数学概念、性质、法则、公式......

    离散数学考试试题(A、B卷及答案)test2

    离散数学考试试题(A卷及答案)一、证明题(10分)1) (P∧Q∧AC)∧(AP∨Q∨C) (A∧(PQ))C。PQ=(p->Q)合取(Q->p) 证明: (P∧Q∧AC)∧(AP∨Q∨C)(P∨Q∨A∨C)∧(A∨P∨Q∨C)((P∨Q∨A)......

    离散数学考试试题(A、B卷及答案)test7(5篇)

    离散数学考试试题(A卷及答案) 一、(10分)证明(A∨B)(P∨Q),P,(BA)∨PA。 证明:(A∨B)(P∨Q)P (P∨Q)(A∨B) T,E P P A∨B T,I (BA)∨PP (6)BA T,I (7......