离散数学课程总结
离散数学是现代数学的一个重要分支,是计算科学专业的专业主干课之一，课程结合计算科学的特点研究离散对象及相互关系，对提高学生的抽象思维与逻辑推理能力有重要作用.它以研究离散量的结构和相互间的关系为主要目标,在计算科学中的数据结构、操作系统等有广泛的应用。
课程内容：
第一部分：数理逻辑数理逻辑是研究推理的数学分支，推理有一些列的陈述句组成。在数理逻辑中，主要学习了命题逻辑的基本概念、命题逻辑的等值演算、命题逻辑的推理理论、一阶逻辑基本概念、一阶逻辑等值演算与推理。
1、在命题逻辑的基本概念中学习了命题与联结词、命题与联结词、命题及其分类、联结词与复合命题、命题公式及其赋值。
2、在命题逻辑的等值演算中主要学习了等值式与基本的等值式、等值演算与置换规则、析取范式与合取范式，主析取范式与主合取范式、联结词完备集可满足性问题与消解法。
3、在命题逻辑的推理理论中主要学习了推理的形式结构、推理的正确与错误、推理形式结构、判断推理正确的方法、推理定律；自然推理系统P、形式系统的定义与分类、自然推理系统P，在P 中构造证明：直接证明法、附加前提证明法、归谬法
4、在一阶逻辑基本概念中主要学习了一阶逻辑命题符号化、个体词、谓词、量词、一阶逻辑命题符号化、一阶逻辑公式及其解释、一阶语言、合式公式、合式公式的解释、永真式、矛盾式、可满足式。
5、在一阶逻辑等值演算与推理中主要学习了一阶逻辑等值式与基本等值式、置换规则、换名规则、代替规则、前束范式、自然推理系统NL 及其推理规则、数理逻辑应用。
第二部分：集合论在集合论中，主要学习了集合代数、二元关系、函数。
1、在集合代数中，学习了集合的基本概念：属于、包含、幂集、空集、文氏图等；集合的基本运算：并、交、补、差等；集合恒等式：集合运算的算律、恒等式的证明方法。
2、在二元关系中学习了有序对与笛卡儿积、二元关系的定义与表示法、关系的运算、关系的性质、关系的闭包、等价关系与划分、偏序关系。
3、在函数中学习了函数的定义与性质、函数运算。
第三部分图的基本概念及其矩阵表示
1.掌握有关图的基本概念。
2.掌握通路和回路的概念。
3.掌握图的矩阵表示法（邻接矩阵、关联矩阵）。重点：图的概念及其矩阵表示。难点：通路与回路。
4. 理解图的连通性，掌握连通性的判别方法，对简单有向图会判断强连通、单向连通还是弱连通。能熟练地求图的点割集、边割集，割点、割边。
5. 理解欧拉图、欧拉通路、欧拉回路的概念，知道哈密顿图的概念及哈密顿图与欧拉图的区别，掌握相关的重要结论，会判断一个图是否是欧拉图或哈密顿图。
6.理解二分图的概念,会求最大匹配. 重点：点割集、边割集及欧拉图。
《离散数学》的特点是：
1、知识点集中，概念和定理多：《离散数学》是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。不管哪本离散数学教材，都会在每一章节列出若干定义和定理，接着就是这些定义定理的直接应用。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。
2、方法性强：离散数学的特点是抽象思维能力的要求较高。通过对它的学习，能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。
《离散数学》的证明题多，不同的题型会需要不同的证明方法（如直接证明法、反证法、归纳法、构造性证明法），同一个题也可能有几种方法。但是《离散数学》证明题的方法性是很强的，如果知道一道题用什么方法讲明，则很容易可以证出来，否则就会事倍功半。
离散数学是一门计算机专业的基础课程，也是比较难学的一门课程。这门课程里有太多的概念需要记忆。学理工科最重要的就是理解。只有真正理解了概念的内在涵义，才能真正掌握这个概念。理解了概念的内在涵义，就为学好这门课程打好了坚实的基础。在理解概念的基础上，再形成适合于离散数学本身的思维模式。学习物理，要用物理思维模式；学习高等数学，要用高数的思维模式；学习线性代数，也要用线性代数式思维模式。所以学习任何一门课程，都要有适合于该课程的思维模式。当然离散数学也不例外，它也有自己独特的思考问题的方式。只有找到了，并理解了这种思维方式，才能为后继学习作好铺垫。最后最重要的就是要找到解决问题的方法。学习任何一门课程，都是为了解决实际问题。离散数学也是如此。有了对概念的理解，有了正确的思考问题的方式，在解决问题的时候就不会走弯路了，也就是说基本的解决问题的方法也就自然而然地掌握了。
浅论离散数学的实际应用 摘要： 离散数学是现代数学的重要分支，是研究离散量的结构及相互关系的学科，它在计算机理论研究及软、硬件开发的各个领域都有着广泛的应用。作为一门重要的专业基础课，对于我们电子专业的同学来说，学习离散数学史有其重要现实意义：它不仅能为我们的专业课学习打下基础，也为我们今后将要从事的软、硬件开发和应用研究打下坚实的基础，同时也有助于培养我们的抽象思维、严格的逻辑推理和创新能力。离散数学的应用非常广泛，本文主要研究其在我们所学的重要课程中的应用：数字电路中的门电路设计、软件技术基础中的一些技术以及解决现实生活中的一些问题的应用。 关键字：离散数学、电路设计、软件技术、应用 1.什么是离散数学 1.1简介 离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。1.2离散数学的内容 离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域，它通常研究的领域包括：数理逻辑、集合论、代数结构、关系论、函数论、图论、组合学、数论等。 2.离散数学在门电路设计中的应用 2.1 逻辑门的概念 逻辑门是集成电路中的基本组件。简单的逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种信号的高低电平在通过它们之后产生高电平或者低电平的信号。高、低电平可以分别代表逻辑上的“真”与“假”
离散数学期末复习 一、选择题 1、下列各选项错误的是 A、??? B、??? C、?∈{?} D、??{?} 2、命题公式(p∧q)→p是 A、矛盾式 B、重言式 C、可满足式 D、等值式 3、如果是R是A上的偏序关系，R-1是R的逆关系，则R∪R-1是 A、等价关系 B、偏序关系 C、全序关系 D、都不是 4、下列句子中那个是假命题？ A、是无理数. B、2 + 5＝8.
C、x+ 5＞3 D、请不要讲话！ 5、下列各选项错误的是？ A、??? B、??{?} C、?∈{?} D、{?}?? 6、命题公式p→（p∨q∨r）是？ A、重言式 B、矛盾式 C、可满足式 D、等值式 7、函数f : N→N, f(x)=x+5,函数f是 A、单射 B、满射 C、双射 D、都不是 8、设D=
D、不连通的 9、关系R1和R2具有反自反性，下面运算后，不能保持自反性的是 A、R1?R2 B、R1-1 C、R1?R2 D、R1-R2 10、连通平面图G有4个结点，3个面，则G有（）条边。 A、7 B、6 C、5 D、4 二、填空题 1、将下面命题符号化。设p:天冷，q:小王穿羽绒服。只要天冷，小王就穿羽绒服.符号化为 2、将下面命题符号化，设p:天冷，q:小王穿羽绒服。因为天冷，所以小王穿羽绒服.符号化为 3、将下面命题符号化，设p:天冷，q:小王穿羽绒服。若小王不穿羽绒服，则天不冷.符号化为 4、将下面命题符号化，设p:天冷，q:小王穿羽绒服。只有天冷，小王才穿羽绒服.符号化为
离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。
离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).
数学小论文范文 随着课程改革的不断深入，新课程理念与课堂教学实践正在逐步融合，逐步改变了以教师、课堂或课本为中心的局面，促进了学生 创新意识与实践能力的发展，学生的学习产生了实质性的变化。那么，在课堂教学中如何使学生主动探索在课堂上显现呢?下面结合本 人的教学实践，谈几点体会及做法。 一给学生提供可探索的材料和可探索的学习内容 二给学生提供良好的学习背景和可探究的学习情境 在课堂教学中，教师应结合教学内容为学生的学习，创设良好的学习背景和可探究的学习情境，让学生在数学知识的广阔背景中更 好地建构知识的意义，并感受数学与生活实际的密切联系，体会数 学的价值，让学生的数学学习活动真正变为学生自己探究的创新过程。如，在教学“百分数的意义”时，可为学生创设这样的学习背景：“有甲乙丙三位工人师傅，甲每加工25个零件，有23个及格，乙加工20个零件，有19个及格，丙加工50个零件，有47个及格。如果有一批零件要其中一位师傅加工，你会选择谁?”通过探究，使 学生认识到这个现实问题实际上可转化成“求谁的合格率高”这一 数学问题。又如，教学“分数的基本性质”时，我有意识地给学生 提供以下的可探究学习情境：上课开始，我拿着一捆36本课外书， 从容地走进课堂。同学们在猜想：这节课老师让我们看课外书了。 于是我指着这捆课外书说：“这36本课外书，我要分给你们三个小组，要求让第一组分得这捆书的三分之一，第二小组分得这捆书的 六分之二，第三小组分得这捆书的九分之三，请同学们说一说，这 样分法合理不合理，谁分得多?谁分得少?结果分完没有?”这样问题 的创设，调动了学生思维的积极性，探究活动立即在课堂上显现， 有的按照自己的思路去画线段图，有的一会儿测量，有的一会儿皱 眉思索，兴趣盎然，学生会心地笑了，一样多。这时，学生又产生 困惑，为什么会一样多呢?最后经过引导探究，得出“分数的基本性质”。
《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???.
2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？
《离散数学》期末考试题(B) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为 ( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二、单选题(每小题3分，共15分) 1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数，则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”. 1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( )
离散数学论文 —浅谈离散数学的学习及其在计算机中的应用一、对离散数学学习的认识 通过这一学期的学习，我对这门课程有一些初步的了解，现在的心情和当初也很不相同。在听过老师讲解以后，我觉得第一部分的数理逻辑自己都能很好的掌握。后面的开始深入一些，对于好多以前没有接触过的名词定义不能马上理解，但是只要跟着老师的思维走，上课认真听讲，课后看一下书本就能懂。有了这些认知，我觉得这门课的难点在于课程比较枯燥，好多理论的知识需要我们去理解。前五章主要是认识逻辑语言符号，了解了数理逻辑的特点，并做一些简单的逻辑推理和运算。第二部分讲的是集合论。在这一部分中进一步认识、运用数理逻辑语言，熟练强化练习，深入理解。这一章的难度相较于前几章要繁琐些，有很多的符号转换，运算，运算过程很复杂。对于计算能力不强的我来说，这一章或许是最吃力的，即使知道原理也需要通过大量的练习强化巩固，而这其中用到的还有线性代数里面的矩阵。在第三部分的代数结构中主要学习了代数系统、群与环，其中二元运算和代数系统有点难度，较以往学习非常吃力！第五部分的图论可以归结为本书的重点之一，“图”“树及其应用”又是其中的重中之重。它的用途非常广泛，并且应用于我们整个日常生活中。比如：一个计算机芯片需要多少层才能使得同一层的路线互不相交？一位流动推销员要以怎样的顺序到达每一个城市才能使得旅行时间最短？这些问题以及其他一些实际问题都涉及“图论”。 这里所说的图并不是几何学中的图形，而是客观世界中某些具体事物间
联系的一个数学抽象，用顶点代表事物，用边表示各式物间的二元关系，如果所讨论的事物之间有某种二元关系，我们就把相应的顶点练成一条边。这种由顶点及连接这些顶点的边所组成的图就是图论中所研究的图。 树是指没有回路的连通图。它是连通图中最简单的一类图，许多问题对一般连通图未能解决或者没有简单的方法，而对于树，则已圆满解决，且方法较为简单。而且在许多不同领域中有着广泛的应用。例如家谱图就是其中之一。如果将每个人用一个顶点来表示，并且在父子之间连一条边，便得到一个树状图。 通过对图论的初步理解和认识，我深深地认识到，图论的概念虽然有其直观、通俗的方面，但是这许多日常生活用语被引入图论后就都有了其严格、确切的含义。我们既要学会通过术语的通俗含义更快、更好地理解图论概念，又要注意保持术语起码的严格。 本以为枯燥乏味的离散数学竟然会是贴近生活是我意想不到的，这些历史难题等等，都让我对它产生了一定的兴趣，虽然不可否认的是，对我来说它确实是一门很难很深奥很抽象的课程，但是仍然不减我对图论产生的兴趣，或许这也就是我选择这门课程最大的收获吧。 二、离散数学在计算机中的应用 离散数学是现代数学的重要分支，是研究离散量的结构及相互关系的学科，它在计算机理论研究及软、硬件开发的各个领域都有着广泛的应用。作为一门重要的专业基础课，对于我们计算机专业的同学来说，学习离散数学史有其重要现实意义：它不仅能为我们的专业课学习打下基础，也为我们今后将要从事的软、硬件开发和应用研究打下坚实的基础，同时也有助于培
安徽大学20 09 — 20 10 学年第 1 学期 《离散数学（上）》考试试卷（A 卷） （时间120分钟） 院/系 专业 姓名 学号 题 号 一 二 三 四 五 总分 得 分 一、单选题（每小题2分，共20分） 1. 设A={a,b,c}，A 上二元关系R={〈a,a 〉，〈b,b 〉,〈a,c 〉}，则关系R 的对称闭包S(R)是( ) A.R ∪I A B.R C.R ∪{〈c,a 〉} D.R ∩I A 2. 设X={a,b,c},I x 是X 上恒等关系，要使I x ∪{〈a,b 〉，〈b,c 〉，〈c,a 〉，〈b,a 〉}∪R 为X 上的等 价关系，R 应取( ) A. ｛〈c,a 〉，〈a,c 〉｝ B.{〈c,b 〉，〈b,a 〉} C. {〈c,a 〉，〈b,a 〉} D.{〈a,c 〉，〈c,b 〉} 3. 下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 4. 设解释R 如下：论域D 为实数集，a=0, f(x,y)=x-y, A(x,y):x 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={ 离散数学试题(B卷答案1） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D， (C∨D)→?E，?E→(A∧?B)， (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4)， I (6) C∨D P (7) R∨S T(5)，I 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P 《离散数学》课程总结论文 专业：11级计科系计本三班姓名：学号：1104013045 一．课程小结 从学离散数学这门课程开始，到现在学期末也已经有了一个学期的认识。以下是对离散数学这门课程的总结： 第一部分：数理逻辑 1.首先我们学习了命题逻辑的基本概念。其实这一部分的内容在高中时已经讲过。其次.命题公式及其赋值，这一小结主要讲的是什么是合式公式以及命题的解释和成真赋值、成假赋值等。 2.命题逻辑等值演算。在这一章节中主要介绍了一些重要的等值公式，例如德摩根律和蕴含等值式等，然后介绍的就是什么是析取范式与析取范式，又进一步的引出主析取范式与主合取范式的概念。另外一个知识点为连接词的完备集。 3.命题逻辑的推理形式。就是如何去证明推理的正确性。这需要我们记住一些重要的推理定律。然后是自然推理系统。推理的一些构造证明的方法有附加前提证明法和归谬法等等。 4.一阶逻辑基本概念。主要说的是一阶逻辑命题的符号化和一阶逻辑公式及其解释。 5.一阶逻辑等值演算与推理，这节知道量词如何消去和一些基本的量词等值式就可以了。 第二部分：集合论 1.集合代数。这一章节中首先讲的是集合的基本概念和运算等等，其中大部分的知识我们高中的时候都已经接触过了。其中要知道什么是绝对补集，对称差集和绝对补集就可以了。 2.二元关系。要知道二元关系首先要知道什么是有序对和笛卡尔集，这是二元关系的基础。然后要清楚二元关系的表示方法有三种，即集合表达式、关系矩阵和关系图。知道了二元关系，紧接着就是关系的运算和性质。关系的性质有自反性、反自反性、对称性、反对称性和传递性。还有就是关系的闭包，其中包括自反闭包、对称闭包和传递闭包。最后一点就是偏序关系和等价关系，还需要知道哈斯图并且会画哈斯图。 第三部分：代数结构 1.代数系统。首先要能够判断一个运算是否为一个集合上的二元运算。在二院运算的基础上，要知道和能够判断单位元、零元和逆元。2群与环。在这一小节中首先要会判断一个代数系统是否为群。在也是这一章节的核心内容。如果一个代数系统，其二元运算时可结合的，又含有单位元，并且集合中的每个元素都有逆元，则此代数系统叫做群。 第四部分：图论 1.图的基本概念。其实在这一章节中，内容多数为一些基本概念。这就需要我们熟练的去掌握。只有清楚了概念才能够做题，比如说什么是有向图、零图、无向图和空图等等。另外图的矩阵表示在这一章节是尤为重要的。其中包括无向图的关联矩阵、有向图的关联矩阵、有向图的邻接矩阵和可达矩阵等。 2.欧拉图与哈 1. 计算：2400 mod 319、2340 mod 11。 2. 设整数a 和b 不全为0，且a 和b 互素。请证明：ab 和a+b 互素。 3. 设n!的标准素因数分解式是 k k p p p εεεΛ2121 请证明： ∑∞=???? ? ?????=1s s i p n i ε，i=1,2,…,k 4. 300！末尾0的个数是？。 5. 解同余方程组：x≡3(mod 8)，x≡11(mod 20)，x≡1(mod 15)。 6. 求p →(p ∧(q →p))的主析取范式和主合取范式。（真值表法和等值演算法） 7. 求谓词公式?x ?y(P(x,y)?Q(x,y))→?x ?yR(x,y)的前束范式。 8. 证明下面的推理： “每个科研工作者都是努力工作的。每个努力工作而又聪明的人都取得事业的成功。某个人是科研工作者并且聪明。所以，某人事业取得成功。” 9. 设R={(1,2),(1,4),(3,3),(4,1)}是集合A={1,2,3,4}上的关系。 （1） R 是自反的吗？是对称的吗？是传递的吗？ （2） R 的自反对称闭包存在吗？ （3） R 的自反传递闭包存在吗？ （4） R 的对称传递闭包存在吗？ （5） R 的自反对称传递闭包存在吗？ （6） R 的反自反闭包存在吗？ （7） R 的反对称闭包存在吗？ 10. 设A={x|x ∈N ，且x|54}，R={(x,y)|x,y ∈A ，且x|y }。 （1） 列出集合A 和R 中的元素； （2） 给出R 的矩阵表示； （3） 证明(A,R)是偏序集，画出哈斯图； （4） 指出(A,R)中的最大元、最小元、极大元、极小元。 11. 设X={(x,y) | x 和y 是不为零的实数}，E 是X 上的关系： 《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 分类号图论密级公开UDC081202编号 计算机科学与技术学院 离散数学及其应用结课论文 图划分方法及其在社会网络分析和佩奇网站排名的应用 李英儒涂超杨凯航张蔚樊哲 指导教师张爱华教授 华中科技大学计算机科学与技术学院 班级计算机科学2013创新实验班 学科专业名称计算机科学与技术 学科名称离散数学及其应用论文提交日期2014年11月学院名称计算机科学与技术学院 学校名称华中科技大学 Typeset by Ying-Ru Li using L A T E X2εat November20,2014 With package CASthesis v0.2of CT E https://www.doczj.com/doc/9e202190.html, The Methods of Graph Partition and Its Applications in Social Network Analysis and PageRank Ying-Ru Li Chao Tu Kai-Hang Yang Wei Zhang Zhe Fan Supervisor: Prof.Ai-Hua Zhang Computer Science and Technology School of Computer Science and Technology Huazhong University of Science and Technology November,2014 Essay about Discrete Mathematics and Its Applications of ACM Class of Computer Science,2013 in Computer Science and Technology 安徽大学2006-2007学年第1学期 《离散数学》期末考试试卷（A卷） （时间120分钟） 开课院（系、部）姓名学号. 一、选择题（每小题2分，共20分）1．下列语句中，哪个是真命题（）A、 4 2= + x； B、我们要努力学习； C、如果ab为奇数，那么a是奇数，或b是偶数； D、如果时间流逝不止，你就可以长生不老。 2．下列命题公式中，永真式的是（） A、P Q P→ →) (； B、P P Q∧ → ?) (； C、Q P P? ? ∧) (； D、) (Q P P∨ →。3．在谓词逻辑中，令) (x F表示x是火车；) (y G表示y是汽车；) , (y x L表示x比y快。 命题“并不是所有的火车比所有的汽车快”的符号表示中哪些是正确的（） I.)),()()((y x L y G x F y x →∧??? II.)),()()((y x L y G x F y x ?∧∧?? III. )),()()((y x L y G x F y x ?→∧?? A 、仅I ； B 、仅III ； C 、I 和II ； D 、都不对。 4．下列结论正确的是：（ ） A 、若C A B A =，则 C B =； B 、若B A B A ?，则B A =； C 、若C A B A =，则C B =； D 、若B A ?且D C ?，则D B C A ?。 5．设φ=1A ，}{2φ=A ，})({3φρ=A ，)(4φρ=A ，以下命题为假的是（ ） A 、42A A ∈； B 、31A A ?； C 、24A A ?； D 、34A A ∈。 6．设R 是集合},,,{d c b a A =上的二元关系， },,,,,,,,,,,{><><><><><><=b d d b a c c a a d d a R 。下列哪些命题为真（ ） I.R R ?是对称的 II. R R ?是自反的 III. R R ?不是传递的 A 、仅I ； B 、仅II ； C 、I 和II ； D 、全真。 v1.0 可编辑可修改 离散数学知识要点总结 第1章命题逻辑 1、会判断一个语句是否为命题（如P31-习题题） 练习：判断下列语句是否为命题。 (1).3+8=13； (2).离散数学是计算机系的一门必修课； (3).太阳系以外的星球上有生物； (4).你打算考硕士研究生吗 (5).9+5≤12 ； (6). 天上有三个月亮。 (7).x+5 > 6； (8).一定要努力学习！(9).2是素数； (10).x+5 > 6； (11).我正在说谎； (12).x=13. (13).这朵花多好看呀！ (14).7能被2整除. (15).我用的计算机CPU主频是 1G吗 (16).蓝色和黄色可以调成绿 色； (17). 雪是黑色的. (18). 明天会下雨吗； (19).我能进来吗 (20).这个男孩真勇敢呀！ (21).蓝色和黄色可以调成绿 色； (22).x≤3； (23)地球饶着太阳转. (24)青年人多么朝气蓬发呀！ (25).5能被2整除. (26).嫦娥一号太棒了！ (27).台湾是中国的一部分； (29) 你下午有会吗若无会，请 到我这儿来！ (30).请不要讲话！ (31) 5是奇数； (32). 3 2> + x 2、注意五个命题联结词的使用，会将命题进行符号化（如，，题的题型）或在判断体现逻辑联结词的逻辑有关系等。练习：将以下命题符号化 (1)如果你不去逛街，那么我也不去逛街。 (2)小李边吃饭边看电视。 (3)林芳学过英语或日语。 (4)张辉与王丽都是三好生. (5)小王住在101室或102室。 (6).2+2≠4当且仅当王红没努力学习离散数学。 (7)4或6是素数. (8).王晓聪明，但是他不用功. (9)如果今天是1号，则明天是5号。(10).小潘不能既跳舞又唱歌。 (11)如果你来了，他就唱歌而且陪你跳舞。 (12).或者雪是黑色的，或者太阳从东方升起。 (13).王晓既用功又聪明。 (14)2 + 2 ≠ 4 当且仅当美国位于非洲。 (15)小李学过英语或法语。 (16）如果石头会说话，那么月亮上就会出现海洋。(17）.如果天气寒冷，小梅就不去游泳。 （18）小红喜欢看书和画画。 离散数学-期末考试卷-A卷 东莞理工学院城市学院（本科）试卷（A卷） 2013-2014学年第一学期 开课单位：计算机与信息科学系，考试形式：闭卷，允许带入场 科目：离散数学，班级：软工本2012-1、2、3 姓名：学号： 题序一二三四总分 得分 A评 卷人 一、单项选择题（每小题2分，共20分） 在每小题列出的四个备选项中只有一个是符合题目要求的，错选、多选或未选均无分。 1. 下述不是命题的是( ) A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 2. 命题公式P→(P∨Q∨R)是( ) A. 永假的 B. 永真的 C. 可满足的 D. 析取范式 3. 命题公式﹁B→﹁A等价于( ) A. ﹁A∨﹁ B B. ﹁(A∨B) C. ﹁A∧﹁ B D. A→B 4．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）A．?P∧Q B．P∧?Q C．P→?Q D．P∨?Q 5．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（）A．?x(A(x))∧B(x) B．??x( A(x)→?B(x) ) C．??x( A(x)∧B(X)) D．??x( A(x)∧?B(x) ) 6. 设有A={a,b,c}上的关系R={ 7. 设A={1,2,3,4,5,6},B={a,b,c,d,e}，以下哪一个关系是从A到B的满射函数( ) A. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>} B. f={<1,e>,<2,d>,<3,c>,<4,b>,<5,a>,<6,e>} C. f={<1,a>,<2,b>,<3,c>,<4,a>,<5,b>,<6,c>} D. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>,<1,b>} 8．设简单图G所有结点的度数之和为10，则G一定有（） A．3条边B．4条边C．5条边 D．6条边 9．下列不．一定是树的是（） A．每对结点之间都有通路的图 B．有n个结点，n-1条边的连通图 C．无回路的连通图D．连通但删去一条边则不连通的图 10．下列各图中既是欧拉图，又是哈密顿图的是（） SHEN YANG NORMAL UNIVERSITY “离散数学”论文 课题名称：离散数学在计算机中的应用 学校：沈阳师范大学 姓名: 郑珊珊 学号： 08304019 院系：数学与系统科学学院 专业：数学与应用数学 班级： 08级3班 日期： 2010年11月28日 离散数学在计算机中的应用 离散数学是工科类计算机专业必修的基础课。它在科学研究、工程技术、国民经济等诸多领域都有广泛应用，所以说离散数学的重要性是不言而喻的。特别是离散数学对计算机中的程序的设计起着至关重要的作用。 离散数学中的集合论、数理逻辑、关系、图论、代数系统在计算机中有着广泛的应用。具体如下： 集合论：集合论被应用在计算机科学研究的各个方面。集合是构造离散结构的基础，离散结构是计算机的基本结构。从集合构造而来的离散结构包括：计数时广泛使用的组合、表示对象之间相互关联的关系、图形、以及用户模拟计算机的有限状态机等。集合论在人工智能领域、逻辑学及程序设计语言等方面都有着重要的应用。同时，集合论在新一代智能计算机的发展具有重要的应用。计算机智能利用模糊集合理论，把人类的语言和思维过程提炼成数学模型，使人类语言数量化、形式化，并通过对模糊逻辑、模糊控制、模糊识别、模糊聚类分析、模糊决策等方面的分析，使计算机能够模拟人脑的高级智能。 数理逻辑：数理逻辑在计算机科学的计算理论、算法、程序设计、人工智能、计算机硬件系统等方面发挥着重要而广泛的应用。从计算机程序设计语言方面来说，语言的理论基础是形式语言、自动机与形式语义学。而形式语言、自动机和形式语义学所采用的主要研究思想和方法来源与数理逻辑和代数。程序设计语言中的许多机制和方法，如子程序调用中的参数代换、赋值等都出自数理逻辑的方法。此外，在语言的语义研究中，四种语义方法最终可归结为代数和逻辑方法。而且，程序的语义及其正确性的理论基础仍然是数理逻辑或进一步的模型论。不仅如此，数理逻辑在计算机体系结构的研究中起着主导的作用，像容错计算机系统、Transputer计算机、阵列式向量计算机、可变结构的计算机系统结构及其计算机模型等都直接或间接与逻辑及代数密不可分。如容错计算机的重要基础之一是多值逻辑，Transputer计算机理论基础是CSP理论，阵列式向量计算机必须以向量运算为基础，可变结构的计算机系统结构及其计算机模型主要采用逻辑与代数的方法。 关系：数据库是多元关系的一种很重要的应用。通常情况下，我们会使用文件方式将信息保存在计算机上，但是当信息的规模越来越庞大的时候，这种单纯使用文件系统保存信息的方式就会存在很多问题：比如信息的一致性和完整性问题，以及在大量的文件中查找具有某些特征信息的问题，信息的并发访问和安全性问题。这些问题导致了数据库德产生和高速发展。数据库系统能够将大量的数据信息有序的组织起来，并提供相应的查询和访问策略以及安全性措施。数据库系统的应用领域覆盖了我们生活中的方方面面。比如银行和证券交易所得事务处理，所有公司和单位都需要的财务和工资管理以及学校里的学籍管理系统、人事管理系统、题库系统等。近几年来，数据库在决策支持系统、空间数据库、多媒体数据库、移动数据库、信息检索和分布式信息检索等领域发挥着越来越重要的作用。除此之外，关系理论在计算机科学的通讯网络、项目调度以及集合划分和计算机语义等方面具有重要的作用。 图论：图论是研究点线构成的图形问题的一门学科，它的起源很早，但它的发展在初期是比较缓慢的，根本原因在于图的分析计算量非常大，仅靠人工不但耗时耗力，而且也容易出错。直到20世纪50年代之后，随着计算机技术的高速发展，利用计算机的强大处理能力，图论的研究也达到了空前活跃的程度，同时，离散数学期末考试试题及答案
离散数学期末考试试题及答案
《离散数学》课程总结论文
离散数学本科期末复习题
《离散数学》期末考试试题
离散数学课程论文
大学《离散数学》期末考试试卷及答案-(1)
离散数学--期末复习
离散数学-期末考试卷-A卷
离散数学在计算机中的应用
相关主题
文本预览