离散数学教学大纲(5篇)

人的记忆力会随着岁月的流逝而衰退，写作可以弥补记忆的不足，将曾经的人生经历和感悟记录下来，也便于保存一份美好的回忆。大家想知道怎么样才能写一篇比较优质的范文吗？以下是小编为大家收集的优秀范文，欢迎大家分享阅读。

离散数学教学大纲篇一

一、（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＝{，，，}＝rt(r)＝r＝{，，，，，，，，} i1i4232-

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

离散数学教学大纲篇二

武汉理工大学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 ，机械工业出版社，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分）集合相等证明 命题逻辑推理证明

离散数学教学大纲篇四

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

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

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

证明满射：函数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。这是最常见的题目中所使用的方法。

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

离散数学教学大纲篇五

复习提纲：

一、判断哪些是命题

*命题的表示（联结词），符号化命题(样题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叉数转换成二叉树