“离散数学”课程教学大纲
课程英文名称:Discrete Methemetics
课程编号:05141201 课程类型:专业核心课
总学时:64 学分:4
使用对象:信息与系统工程学院计算机专业(民、汉本)
选修课程:高等数学、线形代数、C语言
使用教材及参考书
教材:《离散数学》,耿素云、屈婉玲编著,高等教育出版社,2004年1月,面向21世纪教材。
参考书:《离散数学》,左孝凌,刘永才编著,上海科学技术出版社,1988年2月
—课程性质、目的和任务
离散数学是计算机科学的理论基础,对于培养学生的逻辑思维和分析问题、解决问题的能力起着重要作用。通过离散数学的教学,不仅能为学生的专业课学习及将来从事的软、硬件开发和应用研究打下坚实的基础,同时也能培养他们抽象思维和严格逻辑推理能力。二、教学基本要求
离散数学是现代数学的一个重要分支,是计算机科学中基础理论的核心课程。它以研究离散量的结构和相互之间的关系为主要目标,其研究对象一般是有限个或可数个元素,因此它充分描述了计算机科学离散性的特点。
本课程包括数理逻辑、集合论、代数结构,图论等四个内容。考虑到教学时数,要求学生掌握只选数理逻辑、集合论、图论等内容。
三、教学内容及要求
第一部分:数理逻辑
第一章命题逻辑基本概念
1.分清简单命题(既原子命题)与复合命题。
2.深刻理解5种常用联结词的涵义,并能准确地应用它们将基本复合命题及复合命题符号化。
3.分清“相容或”与“排斥或”。
4.深刻理解命题公式的赋值、成真赋值、成假赋值,从而准确地判断出公式的类型。
第二章命题逻辑等值演算
1.深刻理解等值式的定义,知道公式之间的等值关系具有自反性、对称性、传递性。2.牢记基本等值式的名称及它们的内容。
3.熟练地应用基本等值式及置换规则进行等值演算。
4.了解文字、简单析取式、简单合取式、析取范式,合取范式等概念。
5.深刻理解极小项、极大项的定义,名称、下角标与成真赋值的关系,主析取范式与主合取范式。
6.熟练掌握求主析取(主合取)范式的方法。
7.会用主析取范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值。
8.会将任何命题公式等值地化成某联结词完备集中的公式。
第三章命题逻辑的推理理论
1.理解并记住推理形式结构的以下两种形式.
(1)(A1∧A2∧…∧A k) →B
(2)前提:A1A2...A k结论:B
2.熟练掌握判断推理是否正确的不同方法,如真值表法、等值演算法、主析取范式法等。3.牢记P系统中各条推理规则的内容及名称。
4.熟练掌握在P系统中构造证明的直接证明法、附加前提证明法、归谬法。
5.会将日常生活中、社会活动中、科学领域中的某些推理形式化,即写出符号化形式的前提、结论,并能判断推理是否正确,对于正确的推理能在P系统中给出证明。
第四章:一阶逻辑基本概念
1.准确地将给定命题符号化:分清在4.1节中给出(1)一(7)或更多种的符号化形式,特别注意两个基本公式中量词与联结词的搭配情况,其实(5)、(6)、(7)等都是两个基本公式(3)与
(4)的应用。
2.深刻理解永真式、矛盾式、可满足式的概念及其判别方法:准确写出公式的真值表。3.深刻理解闭式的概念及闭式的性质(闭式在任何解释下都是命题)。
4.对于给定的解释会判断给定公式是否成为命题,对是命题的能判断出是真命题,还是假命题。
第五章一阶逻辑等值演算与推理
1.深刻理解并牢记一阶逻辑中的重要的等值式,并能准确而熟练地应用他们
2.熟练又正确地使用置换规则、换名规则、代替规则
3.准确地求出给定公式的前束范式
4.深刻理解自然推理系统F的定义,牢记F中的各条推理规则,特别是要正确使用UI、UG、EG、EI 4条推理规则,使用中应注意以下几点:
(1)一定对前束范式才能使用UI、UG、EG、EI规则.对不是前束范式的公式要使用它们,一定先求出公式的前束范式;
(2)记住UI、UG、EG、EI各自使用的条件;
(3)在同一个推理的证明中,如果既要使用UI规则,又要使用EI规则,一定先使用EI规则,
后使用UI规则,而且UI规则使用的个体常项一定是EI规则中使用过的。
(4)对A(c)不能使用UG规则,其中c为特定的个体常项。
5.对于给定的推理,要求正确地给出它的证明。
第二部分:集合论
第六章:集合代数
1.熟练掌握集合的两种表示法。
2.能够判别元素是否属于给定的集合。
3.能够判别两个集合之间是否存在包含、相等、真包含等关系。
4.熟练掌握集合的基本运算(幂集运算,普通运算和广义运算)并能化简集合表达式。5.掌握有穷集合的计数方法。
6.掌握证明集合等式或者包含关系的基本方法。
第七章:二元关系
1.理解有序对、二元关系、集合A到B的关系、集合A上的关系(包含空关系、全域关系、小于等于关系、整除关系、包含关系等)的定义,掌握笛卡儿积的运算和性质。
2.熟练掌握关系表达式、关系矩阵、关系图的表示法。
3.熟练掌握关系的定义域、值域、逆、右复合、限制、像、幂的计算方法。
4.熟练计算集合A上关系R的自反闭包、对称闭包和传递闭包。
5.能够证明含有上述关系运算的集合恒等式或者包含式。
6.熟练掌握判断关系五种性质的方法,并能对关系的自反、对称、反对称、传递性给出证
明。
7.熟练掌握等价关系、等价类、商集、划分的概念,以及等价关系与划分的对应性质。8.熟练掌握偏序关系、偏序集、哈斯图、偏序集中的特定元素等概念。
9.能够利用上述关系模型处理简单的实际问题。
第八章:函数
1.掌握函数的基本概念,会判断给定集合是否为函数、是否为从A到B的函数
2.熟练计算函数的值、像、完全原像。
3.会判断和证明函数的单射、满射、双射的性质。
4.给定集合A和B,会构造从A到B的双射函数。
5.会计算复合函数、双射函数的反函数。
第四部分:图论
第十四章:图的基本概念
1.理解与图的定义有关的诸多概念,以及它们之间的相互关系
2.深刻理解握手定理及其推论的内容,并能熟练地应用它们
3.深刻理解图同构,简单图,完全图,正则图,子图,补图,二部图等概念及其它们的性质和相互关系,并能熟练地应用这些性质和关系。
4.深刻理解通路与回路的定义,相互关系及其分类,掌握通路与回路的各种不同的表示方法。
5.理解无向图的连通性,连通分支等概念。
6.深刻理解无向图的点连通度、边连通度等概念及其之间的关系,并能熟练地求出给定的较为简单的图的点连通度与边连通度。
7.理解有向图连通性的概念及其分类,掌握判断有向连通图类型的方法。
8.熟练掌握用有向图的邻接矩阵及各次幂求图中通路与回路数的方法。
9.会求有向图的可达矩阵。
第十五章:欧拉图与哈密尔顿图
1.深刻理解欧拉图与半欧拉图的定义及判别定理,对于给定的图(无向的或有向的),应用定理15.5准确地判断出它是否为欧拉图。
2.会用Fleury算法求出欧拉图中的欧拉回路。
3.深刻理解哈密顿图及半哈密顿图的定义。
4.会用破坏哈密顿图应满足的某些必要条件(如定理15.6)的方法判断某些图不是哈密顿图。5.会用满足哈密顿图的充分条件(如定理15.7)的方法判断某些图是哈密顿图。
6.严格地分清哈密顿图的必要条件和充分条件,千万不能将必要条件当充分条件,同样地,也不能将充分条件当成必要条件。
7.对于完全带权图K4和K5能准确地求出最短的哈密顿回路。
第十六章:树
1.深刻理解无向树的定义,熟练掌握无向树的主要性质,并能灵活应用它们。
2.熟练地求解无向树,准确地画出阶数n较小的所有非同构的无向树。
3.深刻理解基本回路,基本回路系统,基本割集,基本割集系统,并对给定的生成树能准确地求出它们。
4.熟练地应用Kruskal算法求最小生成树。
5.理解根树及其分类等概念。
6.会画出阶数n较小(如1≤n≤5)所有非同构的根树。
7.熟练掌握Huffman算法,并用它求最佳前缀码。
8.掌握波兰符号法及逆波兰符号法的算法。
第十七章:平面图及图的着色
1.深刻理解平面图的基本概念,并能灵活应用它们。
2.熟练应用欧拉(Euler)公式
3.深刻理解平面图的判断基本定理。
4熟练地应用平面图的对偶图基本转换方法及对图中顶点的着色。
5理解地图的着色与平面图的着色及边着色等概念。
四、教学重点与难点
第一部分数理逻辑
第一章命题逻辑基本概念
教学重点:①简单命题(既原子命题)与复合命题②5种常用联结词,复合命题的符号化③“相容或”与“排斥或”④命题公式的赋值、成真赋值、成假赋值。
教学难点:“相容或”与“排斥或”的区别。
第二章命题逻辑等值演算
教学重点:①等值式的定义②基本等值式及置换规则进行等值演算③文字、简单析取式、简单合取式、析取范式,合取范式④极小项、极大项的定义,名称、下角标与成真赋值的关系,主析取范式与主合取范式⑤求主析取(主合取)范式的方法⑥主析取范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值⑦将任何命题公式等值地化成某联结词完备集中的公式。
教学难点:求主析取(主合取)范式
第三章命题逻辑的推理理论
教学重点:①推理的不同方法,如真值表法、等值演算法、主析取范式法等。②各条推理规则的内容及名称。③在P系统中构造证明的直接证明法、附加前提证明法、归谬法。
教学难点:①基本推理方法:等值演算法、主析取范式法等。②基本证明方法:直接证明法、附加前提证明法、归谬法。
第四章一阶逻辑基本概念
教学重点:①一阶逻辑公式,永真式、矛盾式、可满足式的概念及其判别方法。②闭式的概念及闭式的性质。③给定的解释会判断给定公式的类型
教学难点:给定的解释会判断给定公式的类型
第五章一阶逻辑等值演算与推理
教学重点:①一阶逻辑中的重要的等值式。②置换规则、换名规则、代替规则。③求出给定公式的前束范式。④自然推理系统F中的各条推理规则。⑤对于给定的推理,要求正确地给出它的证明。
教学难点:自然推理系统F中的各条推理规则;求正确地给出它的证明。
第二部分集合论
第六章集合代数
教学重点:①集合的两种表示法。②集合之间的包含、相等、真包含等关系。③集合的基本运算(幂集运算,普通运算和广义运算)。④有穷集合的计数方法。⑤证明集合等式或者包含关系的基本方法。
教学难点:有穷集合的计数方法;证明集合等式或者包含关系的基本方法。
第七章二元关系
教学重点:①有序对、二元关系、集合A到B的关系、集合A上的关系(包含空关系、全域关系、小于等于关系、整除关系、包含关系等)的定义掌握笛卡儿积的运算和性质。②关系表达式、关系矩阵、关系图的表示法。③关系的定义域、值域、逆、右复合、限制、像、幂的计算方法。④集合A上关系R的自反闭包、对称闭包和传递闭包。⑤关系运算的集合恒
等式或者包含式。⑥判断关系五种性质的方法,并能对关系的自反、对称、反对称、传递性给出证明。⑦等价关系、等价类、商集、划分的概念,以及等价关系与划分的对应性质。⑧偏序关系、偏序集、哈斯图、偏序集中的特定元素等概念。
教学难点:关系的闭包运算;等价关系、等价类;偏序关系、偏序集、哈斯图。
第八章函数
教学重点:①函数的概念,会判断给定集合是否为函数、是否为从A到B的函数。②计算函数的值、像、完全原像以及B A。③单射、满射、双射的性质、构造从A到B的双射函数。
④复合函数、双射函数的反函数。
教学难点:复合函数、双射函数的反函数。
第四部分:图论
第十四章图的基本概念
教学重点:①图的定义。②握手定理。③同构,简单图,完全图,正则图,子图,补图,二部图等概念及其它们的性质和相互关系。④通路与回路的定义,相互关系及其分类,掌握通路与回路的各种不同的表示方法。⑤无向图的连通性,连通分支等概念。⑥无向图的点连通度、边连通度等概念及其之间的关系。⑦用有向图的邻接矩阵及各次幂求图中通路与回路数的方法。⑧有向图的关联矩阵、距离矩阵、可达矩阵。
教学难点:无向图的连通性,连通分支;无向图的点连通度、边连通度。
第十五章欧拉图与哈密尔顿图
教学重点:①欧拉图与半欧拉图的定义及判别定理②哈密顿图及半哈密顿图的定义③分清哈密顿图的必要条件和充分条件④对于完全带权图K4和K5能准确地求出最短的哈密顿回路教学难点:欧拉图与半欧拉图的判别定理;哈密顿图及半哈密顿图的判别定理
第十六章树
教学重点:①无向树的定义及性质。②画出阶数n较小的所有非同构的无向树。③基本回路,基本回路系统,基本割集,基本割集系统。④Kruskal算法求最小生成树。⑤根树及其分类,阶数n较小(如1≤n≤5)所有非同构的根树。⑤Huffman算法,并用它求最佳前缀码。
⑥波兰符号法及逆波兰符号法的算法。⑦波兰符号法及逆波兰符号法的算法。
教学难点:n阶树的所有非同构的无向树;Kruskal算法求最小生成树;Huffman算法,并用它求最佳前缀码。
第十七章平面图及图的着色
教学重点:①平面图的基本概念。②欧拉(Euler)公式。③平面图的判断。④平面图的对偶图。
⑤图中顶点的着色。
教学难点:欧拉(Euler)公式的应用及地图的着色。
五、学时分配
六、考核方式
考试,闭卷,期末试卷占70%(80%),平时成绩占30%(20引。
第一章命题逻辑的基本概念 一、判断下列语句是否是命题,若是命题是复合命题则请将其符号化 (1)中国有四大发明。 (2)2是有理数。 (3)“请进!” (4)刘红和魏新是同学。 (5)a+b (6)你去图书馆吗? (7)如果买不到飞机票,我哪儿也不去。 (8)侈而惰者贫,而力而俭者富。(韩非:《韩非子?显学》) (9)火星上有生命。 (10)这朵玫瑰花多美丽啊! 二、将下列命题符号化,其中p:2<1,q:3<2 (1)只要2<1,就有3<2。 (2)如果2<1,则3≥2。 (3)只有2<1,才有3≥2。 (4)除非2<1,才有3≥2。 (5)除非2<1,否则3≥2。 (6)2<1仅当3<2。 三、将下列命题符号化 (1)小丽只能从筐里拿一个苹果或一个梨。 (2)王栋生于1992年或1993年。 - 1 -
四、设p、q的真值为0;r、s的真值为1,求下列各命题公式的真值。(1)p∨(q∧r) (2)(p?r)∧(﹁q∨s) (3)(?p∧?q∧r)?(p∧q∧﹁r) (4)(?r∧s)→(p∧?q) 五.判断下面一段论述是否为真:“π是无理数。并且,如果3是无理数,则2也是无理数。另外6能被2整除,6才能被4整除。” 六、用真值表判断下列公式的类型: (1) p∧(p→q)∧(p→?q) (2) (p∧r) ?(?p∧?q) (2)((p→q) ∧(q→r)) →(p→r) - 2 -
第二章命题逻辑等值演算 一、用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 二、用等值演算法证明下面等值式 (1)(p→q)∧(p→r)?(p→(q∧r)) (2)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) - 3 -
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求2010年12月19日前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮,以便教师评分。 一、填空题 1.命题公式()P Q P →∨的真值是 1 . 2.设P :他生病了,Q :他出差了.R :我同意他不参加学习. 则命题“如果他生病或出差了,我就同意他不参加学习”符号化的结果为 (PQ)R . 3.含有三个命题变项P ,Q ,R 的命题公式PQ 的主析取范式是 (PQR) (PQR) . 4.设P(x):x 是人,Q(x):x 去上课,则命题“有人去上课.” 可符号化为 (x)(P(x) →Q(x)) . 5.设个体域D ={a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) . 6.设个体域D ={1, 2, 3},A(x)为“x 大于3”,则谓词公式(x)A(x) 的真值为 . 7.谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 . 8.谓词命题公式(x)(P(x) Q(x) R(x ,y))中的约束变元为 X . 三、公式翻译题 1.请将语句“今天是天晴”翻译成命题公式. 1.解:设P :今天是天晴; 则 P . 2.请将语句“小王去旅游,小李也去旅游.”翻译成命题公式. 解:设P :小王去旅游,Q :小李去旅游, 则 PQ . 3.请将语句“如果明天天下雪,那么我就去滑雪”翻译成命题公式. 解:设P:明天天下雪 。 Q:我去滑雪 则 P Q . 4.请将语句“他去旅游,仅当他有时间.”翻译成命题公式. 7.解:设 P :他去旅游,Q :他有时间, 则 P Q . 5.请将语句 “有人不去工作”翻译成谓词公式. 11.解:设P(x):x 是人,Q(x):x 去工作,
2006-2007学年第2学期 2005级《离散数学2》期末考试试题(A卷) 考试时间:2007年6月班级_______________________ 学号_____________________ 姓名_____________________ 请将答案写在答题纸上,写明题号,不必抄题,字迹工整、清晰; 请在答题纸和试题纸上都写上你的班级,学号和姓名,交卷时请将试题纸、答题纸和草纸一并交上来。 一.综合体(30分,每题3分) 1. 求( 1 3 5 ) (2 5 4 ) (3 4 ) 2. 只有两个生成元的循环群一定是有限循环群吗?并说明理由。 3. 有限循环群中是否一定存在周期与群的元数相等的元素? 4. 下面哪个是域GF( 16)的真子域 (A)GF (6) ;(B)GF ⑷;(C)GF(8);(D)GF(16) 5. 有限布尔代数的元素个数必定是如下哪个形式? (A)2n;(B)n 2 ;(C)2 n;(D)4n. 6. 下列代数系统(S, *)中,哪个是群? (A) S={0,1,3,5},* 是模7的乘法;(B) S是有理数集合,*运算是普通乘法; (C) S是整数集合,*是普通乘法;(D) S={1,3,4,9},* 是模11的乘法。 7. 设A={0,1,2,3,4},运算为模5加法,请给出A的所有子群。 8. n元恒等置换是奇置换还是偶置换?对换呢? 9?请给出一个有余,但不是分配格的例子。 10.设R是模12的整数环,R={0,1,2,…,11},下面哪一个是极大理想: (A) 6R; (B)2R; (C)4R; (D)8R 二.计算题(25分,每题5分) 1. 计算分圆多项式①24(X). 2. 设(Z,+)为整数加法群,(C*,??)为非零复数的乘法群,令 f: n -i n ,是Z到C*中的同态映射,请求出f的同态核。 3. 在R上求出x+2除2X5+4X3+3X2+1所得的商式和余式。 4. 设G是3次对称群,H是由I和(13)作成的子群,求H得所有右陪集。 5. 设A={0,1,2,3,4,5}, 运算为模6加法,请给出A中所有元素的周期。 三.(10分)证明或者反驳:f(x)=3x 5+5X2+1 四.(10分)设(G, *)是群,(A, *)和(B,*)是它的两个子群,C={a*b|a € A, b€ B}.证明:若*满足交换律,则(C, *)也是(G,*)的子群。 五.(10分)设Z是整数集合,X={(a,b)|a,b € Z},定义X上的二元运算①和。 如下:对任意(ab) ,(a 2,b2)€ X,有: (a1b"e (a2,b2)= (a+a?,b1+b2), (a1bJ O (a2,b2)= (ax a2,b 1X b),其中,+,x分别是整数加法与乘法。 证明:(X,?,O)是环,如果此环有零因子请给出它们
离散数学试题(A 卷答案) 一、(10分) (1)证明(P →Q )∧(Q →R )?(P →R ) (2)求(P ∨Q )→R 的主析取范式与主合取范式,并写出其相应的成真赋值和成假赋值。 解:(1)因为((P →Q )∧(Q →R ))→(P →R ) ??((?P ∨Q )∧(?Q ∨R ))∨(?P ∨R ) ?(P ∧?Q )∨(Q ∧?R )∨?P ∨R ?(P ∧?Q )∨((Q ∨?P ∨R )∧(?R ∨?P ∨R )) ?(P ∧?Q )∨(Q ∨?P ∨R ) ?(P ∨Q ∨?P ∨R )∧(?Q ∨Q ∨?P ∨R ) ?T 所以,(P →Q )∧(Q →R )?(P →R )。 (2)(P ∨Q )→R ??(P ∨Q )∨R ?(?P ∧?Q )∨R ?(?P ∨(Q ∧?Q )∨R )∧((P ∧?P )∨?Q ∨R ) ?(?P ∨Q ∨R )∧(?P ∨?Q ∨R )∧(P ∨?Q ∨R )∧(?P ∨?Q ∨R ) ?2M ∧4M ∧6M ?0m ∨1m ∨3m ∨5m 所以,其相应的成真赋值为000、001、011、101、111:成假赋值为:010、100、110。 二、(10分)分别找出使公式?x (P (x )→?y (Q (y )∧R (x ,y )))为真的解释和为假的解释。 解:设论域为{1,2}。 若P (1)=P (2)=T ,Q (1)=Q (2)=F ,R (1,1)=R (1,2)=R (2,1)=R (2,2)=F ,则 ?x (P (x )→?y (Q (y )∧R (x ,y ))) ??x (P (x )→((Q (1)∧R (x ,1))∨(Q (2)∧R (x ,2)))) ?(P (1)→((Q (1)∧R (1,1))∨(Q (2)∧R (1,2))))∧(P (2)→((Q (1)∧R (2,1))∨(Q (2)∧R (2,2)))) ?(T →((F ∧F)∨(F ∧F)))∧(T →((F ∧F)∨(F ∧F))) ?(T →F)∧(T →F) ?F 若P (1)=P (2)=T ,Q (1)=Q (2)=T ,R (1,1)=R (1,2)=R (2,1)=R (2,2)=T ,则 ?x (P (x )→?y (Q (y )∧R (x ,y ))) ??x (P (x )→((Q (1)∧R (x ,1))∨(Q (2)∧R (x ,2)))) ?(P (1)→((Q (1)∧R (1,1))∨(Q (2)∧R (1,2))))∧(P (2)→((Q (1)∧R (2,1))∨(Q (2)∧R (2,2)))) ?(T →((T ∧T)∨(T ∧T)))∧(T →((T ∧T)∨(T ∧T))) ?(T →T)∧(T →T) ?T
一、请给出一个集合A,并给出A上既具有对称性,又具有反对称性的关系。(10分)解:A={1,2} R={(1,1),(2,2)} 二、请给出一个集合A,并给出A上既不具有对称性,又不具有反对称性的关系。(10分)集合A={1,2,3} A上关系{<1,2>,<2,1>,<1,3>},既不具有对称性,又不具有反对称性 三、设A={1,2},请给出A上的所有关系。(10分) 答:A上的所有关系: 空关系,{<1,1>,<1,2>,<2,1>,<2,2>} {<1,1>} {<1,2>} {<2,1>} {<2,2>} {<1,1>,<1,2>} {<1,1>,<2,1>} {<1,1>,<2,2>} {<1,2>,<2,1>} {<1,2>,<2,2>} {<2,1>,<2,2>} {<1,1>,<1,2>,<2,1>} {<1,1>,<1,2>,<2,2>}
{<1,2>,<2,1>,<2,2>} {<1,1>,<2,1>,<2,2>} 四、设A={1,2,3},问A 上一共有多少个不同的关系。(10分) 设A={1,2,3},A 上一共有2^(3^2)=2^9=512个不同的关系。 五、证明: 命题公式G 是恒真的当且仅当在等价于它的合取范式中,每个子句均至少包含一个原子及其否定。(10分) 证明:设公式G 的合取范式为:G ’=G1∧G2∧…∧Gn 若公式G 恒真,则G ’恒真,即子句Gi ;i=1,2,…n 恒真 为其充要条件。 Gi 恒真则其必然有一个原子和它的否定同时出现在Gi 中,也就是说无论一个解释I 使这个原子为1或0 ,Gi 都取1值。 若不然,假设Gi 恒真,但每个原子和其否定都不同时出现在Gi 中。则可以给定一个解释I ,使带否定号的原子为1,不带否定号的原子为0,那么Gi 在解释I 下的取值为0。这与Gi 恒真矛盾。 因此,公式G 是恒真的当且仅当在等价于它的合取范式中,每个子句均至少包含一个原子及其否定。 六、若G=(P ,L)是有限图,设P(G),L(G)的元数分别为m ,n 。证明:n ≤2m C ,其中2m C 表 示m 中取2的组合数。(10分) 证明:如果G=(P,L)为完全图,即对于任意的两点u 、v (u ≠v ),都有一条边uv ,则此时对于元数为m 的P(G),L(G)的元数取值最大为C m 2。因此,若G=(P,L)为一有限图,设P(G)的元数为m ,则有L(G)
本科高等数学离散数学试题及答案 一、填空题 1设集合A,B,其中A={1,2,3}, B= {1,2}, 则A - B=____________________; ρ(A) - ρ(B)=__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G=?(P→Q)∧R,则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树,G有7个点,其中4个叶点,则G的总度数为__________,分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B=_________________________; A?B=_________________________;A-B=_____________________ . 7. 设R是集合A上的等价关系,则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G=?(P→(Q∧R)),则使公式G为真的解释有__________________________,_____________________________, __________________________. 9. 设集合A={1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B,|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合,其中R是实数集,A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A={2, 3, 4, 5, 6},R是A上的整除,则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x),则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树,则G中增加_________条边才能把G变成完全图。
离散数学 作业要求: (1)禁止用附件提交作业。附件提交的作业计0分。 (2)作业按题号顺序作答,乱序、不写题号等视情况扣分。 (3)选择题直接提交答案,不要抄题。 (4)卷面整洁,文字、符号以及图等要清晰可辨。 一、单选题(每题2分,共15小题) 1.集合}}}{{},{,{c b a A =,则下列不属于A 的子集的是( ) A.}}{{a B.}}{{b C.}}}{{{c D.}}{,{b a 2.设全集{1,2,...,9,10}U =的子集为A={偶数},B={奇数},则下列选项正确的是( ) A.A B =? B.A B =? C.A B U = D. 以上答案都不对 3.已知集合}4,3,2,1{=A , },,{c b a B =, }8,6,4,2,1{=C ,定义A 到B 的关系c)}(4,b),(3,a),(2,a),{(1,1=ρ,B 到C 的关系(c,1)}(b,6),{(a,4),2=ρ,则下列属于21ρρ的是( ) A.)8,1( B.)4,1( C.)6,2( D.)1,3( 4.集合}3,2,1{=A 上的关系)}3,1(),1,2(),2,1{(=R ,则R 具有( )
A.对称性 B.自反性 C.可传递性 D.以上说法都不对 5.集合{1,2,3}A =上的下列关系,是由A 到A 的函数的是( ) A.{(1,3),(2,3),(3,1)}f = B.{(1,2),(3,1)}g = C.{(1,1),(2,1),(3,2),(1,3)}h = D.{(1,3),(2,1),(2,2)}I = 6.集合},,{},3,2,1{c b a B A ==,则A 到B 的映射中,是单射的是( ) A.}b)b)(3,a)(2,(1,{ B.}b)b)(3,a)(1,(1,{ C.}c)b)(3,a)(2,(1,{ D.}b)b)(3,b)(2,(1,{ 7. 下面各集合都是N 的子集,( )集合在普通加法运算下是封闭的。 A.}16|{整除的幂可以被x x B.}5|{互质与x x C.}30|{的因子是x x D.}30|{ 离散数学作业布置 第1次作业(P15) 1.16 设p、q的真值为0;r、s的真值为1,求下列各命题公式的真值。 解:(1)p∨(q∧r)=0∨(0∧1)=0 (2)(p?r)∧(﹁q∨s)=(0?1)∧(1∨1)=0∧1 =0 (3)(﹁p∧﹁q∧r)?(p∧q∧﹁r)=(1∧1∧1)? (0∧0∧0)=0 (4)(r∧s)→(p∧q)=(0∧1)→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真:“π是无理数。并且,如果3是无理数,则2 也是无理数。另外只有6能被2整除,6才能被4整除。” 解:p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为:p∧(q→r)∧(t→s)的真值为1,所以这一段的论述为真。 1.19 用真值表判断下列公式的类型: (4)(p→q) →(﹁q→﹁p) (5)(p∧r) ? (﹁p∧﹁q) (6)((p→q) ∧(q→r)) →(p→r) 解:(4) p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式,最后一列全为1 (5)公式类型为可满足式(方法如上例),最后一列至少有一个1 (6)公式类型为永真式(方法如上例,最后一列全为1)。 第2次作业(P38) 2.3 用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解:(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)(p→(p∨q))∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?¬(p∨q) ∨ (p∧r) ? (¬p∧¬q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111 一、填空题 1设集合A,B,其中A={1,2,3}, B= {1,2}, 则A - B=__{3}__________________; ρ(A) - ρ(B)=___________________{3},{1,3},{2,3},{123}______ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = _____2^(n^2)_____________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G=?(P→Q)∧R,则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树,G有7个点,其中4个叶点,则G的总度数为__________,分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B=_________________________; A?B=_________________________;A-B=_____________________ . 7. 设R是集合A上的等价关系,则R所具有的关系的三个特性是__自反,对称,传递 ____________________, ________________________, _______________________________. 8. 设命题公式G=?(P→(Q∧R)),则使公式G为真的解释有__________________________,_____________________________, __________________________. 9. 设集合A={1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R2= {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B,|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合,其中R是实数集,A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A={2, 3, 4, 5, 6},R是A上的整除,则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x),则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树,则G中增加_________条边才能把G变成完全图。 16. 设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除,写成与之对应的命题公 离散数学 一、逻辑和证明 1.1命题逻辑 命题:是一个可以判断真假的陈述句。 联接词:∧、∨、→、?、?。记住“p仅当q”意思是“如果p,则q”,即p→。记住“q除非p”意思是“?p→q”。会考察条件语句翻译成汉语。 系统规范说明的一致性是指系统没有可能会导致矛盾的需求,即若pq无论取何值都无法让复合语句为真,则该系统规范说明是不一致的。 1.3命题等价式 逻辑等价:在所有可能情况下都有相同的真值的两个复合命题,可以用真值表或者构造新的逻辑等价式。 谓词+量词变成一个更详细的命题,量词要说明论域,否则没有意义,如果有约束条件就直接放在量词后面,如?x>0P(x)。 当论域中的元素可以一一列举,那么?xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。同理,?xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。 两个语句是逻辑等价的,如果不论他们谓词是什么,也不论他们的论域是什么,他们总有相同的真值,如?x(P(x)∧Q(x))和(?xP(x))∧(?xQ(x))。 量词表达式的否定:??xP(x) ??x?P(x),??xP(x) ??x?P(x)。 1.5量词嵌套 我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译,注意论域。嵌套量词的否定就是连续使用德摩根定律,将否定词移入所有量词里。 1.6推理规则 一个论证是有效的,如果它的所有前提为真且蕴含着结论为真。但有效论证 二、集合、函数、序列、与矩阵 2.1集合 ∈说的是元素与集合的关系,?说的是集合与集合的关系。常见数集有N={0,1,2,3...},Z整数集,Z+正整数集,Q有理数集,R实数集,R+正实数集,C复数集。 A和B相等当仅当?x(x∈A?x∈B);A是B的子集当仅当?x(x∈A→x∈B);A是B的真子集当仅当?x(x∈A→x∈B)∧?x(x?A∧x∈B)。 幂集:集合元素的所有可能组合,肯定有?何它自身。如?的幂集就是{?},而{?}的幂集是{?,{?}}。 考虑A→B的函数关系,定义域、陪域(实值函数、整数值函数)、值域、像集(定义域的一个子集在值域的元素集合)。 一对一或者单射:B可能有多余的元素,但不重复指向。 映上或者满射:B中没有多余的元素,但可能重复指向。 一一对应或者双射:符合上述两种情况的函数关系。 反函数:如果是一一对应的就有反函数,否则没有。 合成函数:fοg(a)=f(g(a)),一般来说交换律不成立。 2.4序列 无限集分为:一组是和自然数集合有相同基数,另一组是没有相同基数。前者是可数的,后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。 如果A和B是可数的,则A∪B也是可数的。 命题逻辑的基本概念 一、单项选择题 1.下列语句中不是命题的有( ). A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗D.我要努力学习。 2. 下列语句是真命题为( ). A. 1+2=5当且仅当2是偶数 B. 如果1+2=3,则2是奇数 C. 如果1+2=5,则2是奇数 D. 你上网了吗 3. 设命题公式)(r q p ∧→?,则使公式取真值为1的p ,q ,r 赋值分别是 ( ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式q q p →∨ )(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q :我有时间. 命题“我将去市里,仅当我有时间时”符号化为为( ) q p q p q p p q ?∨??→→)D ()C ()B ()A (6.设P :我听课,Q :我看小说. “我不能一边听课,一边看小说”的符号为( ) A. Q P ?→ ; B. Q P →?; C. P Q ?∧? ; D. )(Q P ∧? 二、判断下列语句是否是命题,若是命题是复合命题则请将其符号化 (1)中国有四大发明。 (2)2是有理数。 (3)“请进!” (4)刘红和魏新是同学。 (5)a+b (6)如果买不到飞机票,我哪儿也不去。 (8)侈而惰者贫,而力而俭者富。(韩非:《韩非子显学》) (9)火星上有生命。 (10)这朵玫瑰花多美丽啊! 二、将下列命题符号化,其中p:2<1,q:3<2 (1)只要2<1,就有3<2。 (2)如果2<1,则32。 (3)只有2<1,才有32。 (4)除非2<1,才有32。 (5)除非2<1,否则32。 离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次,容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握.本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业. 要求:学生提交作业有以下三种方式可供选择: 1. 可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅. 2. 在线提交word文档 3. 自备答题纸,将答题过程手工书写,并拍照上传. 一、填空题 1.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是15 . 2.设给定图G(如右由图所示),则图G的点割集是 { f },{ e,c} . 3.设G是一个图,结点集合为V,边集合为E,则 G的结点度数之和等于边数的两倍. 4.无向图G存在欧拉回路,当且仅当G连通且不含奇数度结 点. 5.设G= 8.结点数v与边数e满足e=v - 1 关系的无向连通图就是树. 9.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去条边后使之变成树. 10.设正则5叉树的树叶数为17,则分支数为i = 4 . 二、判断说明题(判断下列各题,并说明理由.) 1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路. 答:错误。应叙述为:“如果图G是无向连通图,且其结点度数均为偶数,则图G存在一条欧拉回路。” 2.如下图所示的图G存在一条欧拉回路. 答:错误。因为图中存在奇数度结点,所以不存在欧拉回路。 3.如下图所示的图G不是欧拉图而是汉密尔顿图. 离散数学作业 软件0943 张凌晨38 李成16 1.设S={1,2,3,4},定义S上的二元运算*如下: x*y=(xy) mod 5任意x,y属于S 求运算*的运算表. 解(xy) mod 5表示xy除以5的余数,所以运算表如下: 2.设*为Z+上的二元运算,任意x,y属于Z+, x*y=min(x,y),即x和y之中的较小数. (1)求4*6,7*3. (2)*在Z+上是否满足交换律、结合律和幂等律? (3)求*运算的单位元、零元及Z+中所有可逆元素的逆元. 解 (1)由题得:4*6=min(4,6)=4; 7*3=min(7,3)=3. (2)由题分析知: *运算是取x和y之中的较小数,即x和y调换位置不影响结果,所以*在Z+上满足交换律. *运算满足结合律,因为任意x,y属于Z+,有 (x*y)*z=min(x,y)*z=min(min(x,y),z) x*(y*z)=x*min(y,z)=min(x,min(y,z)) 无论x,y,z三数中哪个较小,*运算的最终结果都是较小的那个,所以满足结合律. *运算满足幂等律,因为在Z+上任意 x*x=min(x,x)=x (3)在Z+中最小的数字是1 任意x属于Z+,有 x*1=1=1*x 所以1是*运算的零元,*运算没有单位元,也没有可逆元素的逆元。 3.令S={a,b},S 上有四个二元运算:*,&,@和#,分别由下表确定. (1)这四个运算中哪些运算满足交换律、结合律、幂等律? (2)求每个运算的单位元、零元及所有可逆元素的逆元. 解 (1)*,&和@满足交换律;*,@和#满足结合律;#满足幂等律。 (2)*运算没有单位元和可逆元素,a 是零元;&运算的单位元为a ,没有零元,每个元素都是自己的逆元;@运算和#运算没有单位元, 零元和可逆元素. 离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题 目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识 点,重点复习,争取尽快掌握。本次形考书面作业是第一次作业,大家要认真及时地 完成集合论部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答 过程,要求本学期第11周末前完成并上交任课教师(不收电子稿)。并在03任务界 面下方点击“保存”和“交卷”按钮,完成并上交任课教师。 一、填空题 1.设集合{1,2,3},{1,2} ==,则P(A)- A B P(B )={{3},{1,3},{2,3},{1,2,3}},A? B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} . 2.设集合A有10个元素,那么A的幂集合P(A)的元素个数为 1024 . 3.设集合A={0, 1, 2, 3},B={2, 3, 4, 5},R是A到B的二元关系, 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>} . 4.设集合A={1, 2, 3, 4 },B={6, 8, 12},A到B的二元关系 R=} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R-1={<6,3>,<8,4>} 5.设集合A={a, b, c, d},A上的二元关系R={, , , 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={离散数学作业(2)
太原理工大学离散数学试题
离散数学知识点整理
离散数学作业
2018国家开放大学离散数学本形考任务答案
离散数学作业
离散数学作业答案完整版
大学离散数学期末重点知识点总结(考试专用)