人的记忆力会随着岁月的流逝而衰退,写作可以弥补记忆的不足,将曾经的人生经历和感悟记录下来,也便于保存一份美好的回忆。大家想知道怎么样才能写一篇比较优质的范文吗?以下是小编为大家收集的优秀范文,欢迎大家分享阅读。
离散数学教学大纲篇一
一、(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
离散数学教学大纲篇二
武汉理工大学2024年博士入学考试《离散数学》考试大纲
一、考试要求共济
要求考生系统地掌握离散数学的基本概念、基本定理和方法,具有较强的逻辑思维和抽象思维能力,能够灵活运用所学的内容和方法解决实际问题。考
二、考试内容济
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.离散数学,胡新启,武汉大学出版社,2024年。
2.离散数学,尹宝林、何自强、许光汉、檀凤琴等,高等教育出版社,1998年。
3.离散数学及其应用,kenneth ,机械工业出版社,2024年。
离散数学教学大纲篇三
第一部分 简单命题符号化,求主析取范式,判断公式类型(重言式,矛盾式,可满足式)量词消去规则。命题逻辑推理规则
带全称量词和存在量词的命题逻辑推理的构造和证明 第二部分
集合基本运算,文氏图 有序对的基本知识,笛卡儿积,特征函数
函数的性质(单射,满射,双射)
集合的基本概念(交集,并集,幂集,定义域,值域)
给出关系图,画出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叉数转换成二叉树