人的记忆力会随着岁月的流逝而衰退，写作可以弥补记忆的不足，将曾经的人生经历和感悟记录下来，也便于保存一份美好的回忆。大家想知道怎么样才能写一篇比较优质的范文吗？以下是小编为大家收集的优秀范文，欢迎大家分享阅读。
离散数学教学大纲篇一
一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？ 1)((pq)∧q)((q∨r)∧q)2)((qp)∨p)∧(p∨r)3)((p∨q)r)((p∧q)∨r)解：1)永真式；2）永假式；3)可满足式。
二、（8分）个体域为{1，2}，求xy（x+y=4）的真值。
解：xy（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∧10
三、（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×cb×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中的运算“”为ab=a*u-1*b，对任意a,b∈g，求证：
也是个群。
证明：1）a,b∈g，ab=a*u-1*b∈g，运算是封闭的。2）a,b,c∈g，（ab）c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a（bc），运算是可结合的。3）a∈g，设e为的单位元，则ae=a*u-1*e=a，得e=u，存在单位元。
4）a∈g，ax=a*u-1*x=e，x=u*a-1*u，则xa=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)(pr)的主合取范式。
解：(p∧q)(pr)（(p∧q)(pr)）∧（(pr)(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∧（xb∨xc）
（x a∧xb）∨（x a∧xc） 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＝{，，
，
，，，
，
，} i1i
4232-1六、(15分)设a、b、c、d是集合，f是a到b的双射，g是c到d的双射，令h：a×cb×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，bh，则有a*bh。
证明： 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 ∵hg且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叉数转换成二叉树
