离散数学教学大纲
第一部分大纲说明
一.课程的性质与任务
《离散数学》是现代数学的一个重要分支，也是计算机计算机科学与技术一级学科及其相关专业必修的基础理论的核心课程。它是学习后续专业课程不可缺少的数学工具。该课程结合计算机学科的特点，主要研究离散量结构及相互关系，其研究对象一般是有限个或可数个元素，因此《离散数学》充分描述了计算机学科离散性的特点。它是一门理论性较强，应用性较广的课程。
掌握集合论、数理逻辑、图论、整数、群、环、域、格、布尔代数以及语言与有限自动机等离散数学的基本概念和基本原理，为学习计算机专业各后续课程做好必要的知识准备。并通过这些知识的学习进一步提高学生的抽象思维和逻辑推理能力，为从事计算机相关的理论研究与应用提供必要的描述工具和理论基础。
二《离散数学》的特点
作为计算机科学与技术一级学科的一门课程，《离散数学》有与其他课程相同相似的地方，当然也有它自身的特点：
1、义与定理多。《离散数学》是建立在大量定义之上的逻辑推理学科，因此对概念的理解
是我们学习这门课程的核心。在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理与性质。
2、法性强。《离散数学》的许多证明题中，方法性是非常强的，如果知道题的证明方法，
很容易就可以证出来，反之则事倍功半。所以在学习该课程中要善于总结，勤于思考，这也是培养分析问题解决问题抽象思维能力的一个过程。
三与其他相关课程的关系
先修课程：高等数学（包括数学分析、线性代数）
后续课程：数据结构、数据库、编译原理等
四课程的主要内容与基本要求
本课程分为九部分：集合论基础、命题逻辑、谓词逻辑、图与网络、数论基础、群与环、多项式与有限域、格与布尔代数以及语言和有限自动机。
（一）集合论基础：在整个《离散数学》的知识体系中，集合论处于基础的地位，对于其所包
含知识的掌握程度，直接关系到是否能学好图论和抽象代数问题。本章主要讲述集合、关系和映射。
1. 掌握集合、子集、超集、空集、幂集、集合族的概念。懂得两个集合间相等和包含关系
的定义和性质，能够利用定义证明两个集合相等。熟悉常用的集合表示方法。
2. 掌握集合的基本运算：并、交、余、差、直乘积、对称差的定义以及集合运算满足的基
本算律，能够利用它们来证明更复杂的集合等式。
3. 掌握关系、二元关系、空关系、全域关系、相等关系、逆关系的概念以及关系的性质：
自反性、对称性、反对称性、传递性。会做关系的乘积。了解关系的闭包运算：自反闭包、对称闭包、传递闭包。
4. 掌握等价关系、等价类、商集的概念，了解等价关系和划分的内在联系。
5. 掌握部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最
大元、最小元、极大元、极小元、上确界、小确界的定义。能画出有限部分序集的Hasse 图，并根据图讨论部分序集的某些性质。
6. 掌握映射、映像、1-1映射等概念，会做映射的乘积。了解可数集合的概念，掌握可数
集合的判定方法。
7. 了解关系在数据库中的应用（数据的增、删、改）以及划分在计算机中的应用。
重点是使学生会用集合描述和解决问题，掌握二元关系，二元关系的性质及其证明方法（按定义证明法），对映射概念的深入理解；难点是证明集合相等，等价关系与部分序关系，1-1映射的证明和集合的可数性证明。
（二）数理逻辑：数理逻辑是用数学方法研究思维规律和推理过程的科学，由于它使用一套符号，简洁地表达出各种推理的逻辑关系，因此数理逻辑又称为符号逻辑。它和计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计等计算机理论研究与应用提供了必要的理论基础。本章需要学生掌握下列内容。
1. 掌握命题、逻辑联结词等概念，能够将命题符号化。
2. 掌握命题公式、解释、恒真公式、恒假公式等概念。能够判断一命题公式是恒真、恒假
还是可满足。
3. 掌握公式的等价、蕴涵等概念，熟记基本的等价式、蕴涵式，会证明更复杂的等价式、
蕴涵式。
4. 掌握联结词的功能完备集（全功能集）的概念，能够判别一个联结词集合是否为联结词
的功能完备集。
5. 掌握演绎方法，能够使用演绎方法进行有效推理。
6. 掌握析取范式、合取范式、极大项、极小项、主析取范式、主合取范式的概念和性质。
掌握求各种范式的方法，能够用等价演算法和真值表法求命题公式的主析取范式、主合取范式。了解一个命题公式的主合取范式与主析取范式的关系——如何根据一种主范式立即写出另一种主范式。
7. 了解命题逻辑在二值逻辑器件和语句逻辑中的应用。
重点是命题概念，等价公式与蕴涵公式，求主合取范式与主析取范式，联结词的变化与全功能集、演绎推理；难点是演绎推理和综合应用。
（三）谓词逻辑：谓词逻辑是在命题逻辑的基础上，对命题进行进一步的细分，分解出命题中的主语、谓语等，以便能处理句子的内部结构之间的逻辑关系，而非仅仅是句子之间的逻辑关系。为此，谓词逻辑将处理更为复杂的问题，而谓词逻辑本身的讨论也更为复杂。本章需要学生掌握下列内容。
1. 掌握谓词、全称量词、存在量词等概念，学会使用它们符号化一些命题并构成一些较复
杂的命题。
2. 掌握约束变量、自由变量的概念，能够正确使用改名规则。
3. 掌握谓词公式、解释的概念，能够求出一给定公式在某一解释下的真值。
4. 掌握恒真公式、恒假公式、可满足公式等概念，了解与命题逻辑判定问题可解不同的是：
谓词逻辑判定问题不可解，但谓词逻辑是半可判定的。
5. 掌握谓词公式的等价、蕴涵等概念，熟记基本的等价式、蕴涵式，会证明更复杂的等价
式、蕴涵式。
6. 掌握谓词演算的推理理论，能够正确使用推理规则进行有效推理，并能判断一推理过
程是否正确。
7. 掌握前束范式、Skolem范式等概念，能够将一谓词公式化成与之等价的前束范式，并
进一步化为Slolem范式。
8. 了解谓词逻辑计算机科学中的应用。
重点是谓词逻辑的基本概念及其符号化、谓词逻辑公式与解释、等价公式与蕴涵公式、前束范式与Skolem范式、能记住主要的等值式、掌握谓词演算中的推理方法；难点是谓词演算中的推理和综合应用。
数理逻辑的基本概念作为计算机科学的一种重要知识表示工具，要求通过这部分内容的学习能将所研究的对象及其相互关系形式化，并进行简单的逻辑推理。
（四）图与网络：图论是一门很有使用价值的学科，它在自然科学、社会科学等各个领域均有广泛的应用。特别是在计算机科学与技术学科中的数据结构、形式语言、分布式系统、计算机
图形学、操作系统等方面均有重要的应用。这种应用的多样性，使它受到了数学界与工程界的特别重视，对于这样一门广泛应用的学科，其包含的内容当然是浩瀚如海的。在本章主要介绍图论的基本知识、基本理论和一些特殊图形及其性质。本章需要学生掌握下列内容。
1. 掌握图、有限图、母图、子图、支撑子图、完全图、补图等概念，了解有限图中点的度
的性质，掌握图的矩阵表示：关联矩阵、邻接矩阵。
2. 掌握路、简单路、回路、连通图等概念。
3. 理解Dijkstra算法，并能够在已知权图中使用该算法求出任意两点间的最短路。
4. 掌握树、支撑树的概念以及图是树的几个等价命题。
5. 理解Kruskal算法，并能够应用它求已知加权连通图的最优树。了解求最优树的Prim算法，
会总结Sollin算法。
6. 掌握有向图、有向子图、有向路、简单有向路、有向回路等概念。
7. 掌握有向图的强连通性和有向图的根的概念，了解二者的关系。
8. 掌握有向树的概念以及有向树与树的转化定理。
9. 掌握Euler路、Euler图的概念，掌握有向图中和无向图中Euler图的充要条件，并能利
用判断某图是否为Euler图。了解从Euler路得出有向支撑树以及从有向支撑树得出
Euler路的方法。
10. 掌握Hamilton路、Hamilton回路、Hamilton图的概念以及Hamilton图的必要条件和若
干充分条件。
11. 了解流动推销员问题和求解Hamilton路的逼近算法。
12. 掌握平面图、平面图的对偶图、柏拉图体等概念，掌握平面图的库拉托夫斯基判定准则、
平面图的Euler公式以及平面图的性质。了解平面图的着色问题。
13. 掌握匹配、极大匹配、最大匹配、完全匹配、M-交错路、M-交回错路、M-增广路等概念。
会求一个图中的最大匹配，和判定一个匹配是否为最大匹配（完全匹配）。
14. 掌握二部图等概念，掌握判定一个二部图中存在完备匹配的充要条件以及在二部图G=(P1, L,
P2)中，寻找P1到P2的一个完备匹配的Hungarian算法。
15. 了解Konig无限性引理以及王浩定理。
重点是图的基本概念，图论的基本定理（握手定理）及其推论，结点的度，图的连通性与回路，图的矩阵表示，权图及其最短路求法，树的概念与性质，权图中最优树的求法，有向图与有向树，掌握Euler图与Hamilton图的概念及其判别方法，Euler公式和平面图的关于边与结点的数量关系不等式；难点是Euler图与Hamilton图的证明与判别方法，图着色，二部图与匹配。
（五）数论基础：数论是研究整数的学科，早在公元前1世纪左右，我国第一部数学名著《九
章算术》的第一章就开始讨论整数，介绍了展转相除法；公元4世纪，我国的《孙子算经》中更有闻名于世的中国剩余定理，也队整数进行了研究。而计算机只能处理有限数和有限个数，计算机的计算模型，硬件体系结构的设计与实现，代数编码，软件设计与实现，计算机通讯及密码学等，都广泛使用了整数理论，使得这门古老的学科又焕发了青春。本章介绍数论中一些最基本的事实，就是说，介绍整数的最基本性质。本章需要学生掌握下列内容。
1. 掌握整除、因数、倍数等概念，记住并会应用整除的性质。
2. 掌握最高公因数的概念，能够使用辗转相除法求两个数的最高公因数并表示为
它们的倍数和。会利用数的数码特征判别某些整除性。
3. 掌握互质的概念和质数的性质。掌握质数、合数的概念以及算术基本定理、欧几里得定
理。
4. 掌握合同的概念以及合同的基本性质。
5. 掌握剩余系、剩余类的概念。了解一次合同方程在什么条件下有解、什么条件下无解、
什么时候有唯一解（一个剩余类）、什么时候有多解（多个剩余类），并对有解的情况掌握求解方法。
6. 掌握秦九韶定理(及其推广)、合同方程组的一般解法。
7. 掌握简化剩余系、Euler函数、Euler函数的可乘性、欧拉定理、费尔马定理。
8. 掌握二次同余的概念、二次同余方程的判定和求解、勒让德符号、欧拉判别法则。
9.了解合同在计算机编码中的应用。
重点是掌握整数的整除性，任意二整数的最高公因数表示，互质，质因数分解，算术基本定理，一次合同及其性质，剩余类，中国剩余问题，Fermat-Euler定理，Euler函数；难点合同的概念以及合同的基本性质，简化剩余系，Euler函数，Euler函数的可乘性，欧拉定理，费尔马定理，二次同余方程的判定和求解，勒让德符号，欧拉判别法则。
（六）群与环：抽象代数学的研究对象是抽象的，它不是以某一具体对象为研究对象，而是以一大类具有某种共同性质的对象为研究对象，因此其研究成果适用于这一类对象中的每个对象，从而达到事半功倍的效果。群是具有一个二元代数运算的代数系统，环是具有两个代数运算的代数系统。本章需要学生掌握下列内容。
1. 掌握二元代数运算、代数系统的定义，能够判断一运算是否为二元代数运算，运算
是否满足交换律、结合律、分配律、幂等律、吸收律、消去律。
2. 掌握半群、群的定义以及群的性质，能够判断一代数系统是否为半群或群。
3. 掌握交换群的定义以及交换群中的三个指数律。
4. 掌握置换、轮换、不相杂轮换、对换等概念，会做置换的乘法，会将任意置换写成不相
杂轮换的乘积。了解置换的顺向圈表示。
5. 掌握奇置换、偶置换的概念，了解置换的定性数与置换的图型及奇偶性的关系。
6. 掌握n次对称群、n次交代群的概念，会写出其中的元素。
7. 掌握子群的定义以及子群的判别条件。掌握周期、循环群的定义和乘法群、加法群中周
期的性质以及循环群中一元素作为生成元的充要条件。
8. 掌握群中合同、右陪集的定义。了解子群在大群中的右陪集的一些性质。掌握正规子群
的概念以及一子群为大群的正规子群的充要条件。掌握并会正确应用Lagrange定理。
9. 掌握同态映射、同构映射、自同构映射的概念以及同态定理。会判断一个群与一乘法系
统间的映射是否为同态映射、同构映射或自同构映射。
10. 掌握同态核的概念，了解若σ是群G到G′上的同态映射，则其核N为一正规子群。
反过来，设N是G的一个正规子群，则有一个群G′以及一个G到G′上的同态映射σ，使N为σ的核。掌握并会正确应用联系同态与同构的基本定理。了解σ为群G到G′上的同态映射时，G中子群与G′中子群的关系。
11. 掌握环、交换环、含壹环、消去环的定义及其性质，会判断。
12. 掌握整区、体、域、子环、子体、子域等概念，以及环的子集作成子环的充要条件。
13. 掌握并会应用理想、主理想的定义，掌握环中合同关系、剩余类的定义以及环中合同关
系的性质。
14. 掌握环同态映射、同构映射、剩余环的定义，了解与群论中平行的环中的关于同态映射、
同构映射的一些定理。
15. 掌握单纯环与极大理想的定义，以及二者的关系，了解一个环是域的充要条件。
16. 了解群与环在计算机科学中的应用--计数问题、纠错码。
重点是二元代数运算及其性质，能够对某代数系统进行判断，半群与群的概念，群的性质，子群的性质与判别条件，循环群及其性质，元素的周期，合同，陪集，正规子群及其判定条件，正确应用Lagrange定理，群的同态与同构，同态核，环、交换环、含壹环、消去环的定义及其性质，会判断，掌握并会应用理想、主理想的定义，掌握环中合同关系、剩余类的定义以及环中合同关系的性质，环同态映射、同构映射、剩余环的定义，掌握单纯环与极大理想的定义，以及二者的关系；难点是群的同态同构，环的同态同构、剩余类环，一个环是域的充要条件。（七）多项式与有限域：多项式中许多概念、结果和方法是抽象代数中抽象概念的非常基本的模型和源泉。由于计算机科学和数字通讯技术的飞速发展有限域的理论得到了广泛和深入的应用。本章需要学生掌握下列内容。
1. 掌握域的特征的概念，了解若p为质数或等于0，则特征为p的任意域F包含R P为其最
小子域。
2. 掌握多项式相等、多项式的次数的概念，了解域F上х的多项式作成的环F[х]是一个
整区。掌握多项式整除的概念及其性质。掌握公因式、最高公因、真因式、互质、质式 等定义及相关定理。
3. 掌握多项式恒等、多项式的根、k 重根、重根等概念，了解余式定理及其推论。掌握多
项式有重根的充要条件。
4. 了解实数域上、复数域上、有理域上的质式问题。
5. 掌握本原多项式的概念、Eisenstein 定则以及求有理数多项式的有理根问题。会计算有
理根，会证明某多项式在有理域上不可约。了解代数数、超越数的概念。
6. 掌握有理域上和任意域上分圆多项式的定义，会利用公式хn -1 =
)(|x n d d ∏Φ计算分圆 多项式。
7. 了解有限域的元数和其子域的元数的关系，会构造元数为p n 的有限域。
8. 了解多项式编码方法及其实现（信息码多项式）。
重点是域的特征，多项式相等、多项式的次数的概念，多项式整除的概念及其性质。掌握公因式、最高公因、真因式、互质、质式等定义及相关定理。本原多项式的概念、Eisenstein 定则以及求有理数多项式的有理根问题。会计算有理根，会证明某多项式在有理域上不可约。有理域上和任意域上分圆多项式的定义，会利用公式хn -1 = )(|x n d d ∏Φ
计算分圆多项式，会构造
元数为p n 的有限域。难点是证明某多项式在有理域上不可约，构造元数为p n 的有限域。
（八）格与布尔代数：格是一种特殊的偏序集，也可以看作是有两个二元运算的代数系统，布尔代数是一种特殊的格。在保密学、开关理论、计算机理论和逻辑设计以及其他一些科学和工程领域中，都直接应用了格与布尔代数。本章需要学生掌握下列内容。
1. 掌握半序格、半序子格、代数格、代数子格的定义，了解半序格和代数格的定义是等价
的。
2. 掌握互相对偶的两个关系、互相对偶的两个格的定义，了解二者关系。掌握格中表达式、
对偶格中的对偶表达式、本格中的对偶表达式的定义，掌握并会应用对偶原理1及对偶 原理2。
3. 了解格的其它性质，如格的保序性、分配不等式、模不等式等。
4. 掌握并会应用格同态映射、格的自同态映射、格同构映射的定义。了解格的同态映射一
定是保序映射，同构映射的逆映射也是同构映射等结论。
5. 掌握有界格、有余格、分配格以及模格的定义以及相关的结论。了解一个格为模格的充
要条件。
6. 掌握布尔代数的定义及其16个性质，掌握并会应用Huntington 公理来判定一代数系统
是否为布尔代数。了解电路代数、集合代数、命题代数、开关代数。掌握并会应用布尔代数的子集是其子代数的充要条件。
7. 掌握可唯一表示布尔代数中元素的基底的定义及其性质。掌握极小元的定义及其性质。
掌握布尔代数的生成、极小项、多项式、多项范式、布尔代数中一组元素互相独立等概念，了解布尔代数中元素与多项范式的关系和极小项、基底、极小元间的关系。
8. 掌握布尔代数中同态、同构的概念及其相应结论。了解如果两个有限布尔代数的维数相
同，则这两个代数同构；任意n维布尔代数（B，·，+，ˉ，0，1）与开关代数（B n，·，+，ˉ，0n，1n）同构；Stone定理。
9. 掌握电路函数、布氏式的概念，了解任意一个电路函数，都可表为一个布氏式。掌握最
简多项式、极简多项式的概念。掌握两种得到组成极简多项式的极简项的方法：Quine 方法、Karnaugh图法，会应用这两种方法求极简项，对布尔代数进行化简。
10. 了解格与布尔代数在计算机科学中的应用。
重点是半序格、半序子格、代数格、代数子格的定义，格的其它性质，会应用格同态映射、格的自同态映射、格同构映射的定义，有界格、有余格、分配格以及模格的定义以及相关的结论，布尔代数的定义及其16个性质，会应用Huntington公理来判定一代数系统是否为布尔代数，掌握可唯一表示布尔代数中元素的基底的定义及其性质，布尔代数中同态、同构的概念及其相应结论。难点是布尔代数的生成、极小项、多项式、多项范式，布尔代数中同态、同构。
（九）语言与有限自动机：形式语言于自动机理论不仅对问题及其求解提供了良好的形式化描述工具，更在于通过适当的描述和解析而降低难度，成为本科生和研究生进行“计算思维”能力培养的重要内容。本章需要学生掌握下列内容。
1. 掌握语法结构、语言、演绎、演绎树的概念，能识别语法结构的分类，能写出一个语法的Backus-Naur form。
2.掌握带有输出的有限状态机的定义，能够使用状态图和状态表表示带有输出的有限状态机。
3.会求串联、kleene闭包，掌握没有输出的有限状态机（有限状态自动机）的概念，了解非确
定的有限状态机，知道能被一个非确定的有限状态自动机是别的语言也可以被一个确定的有限状态自动机识别。
4.掌握正则表达式和正则集合的概念，了解KLEENE定理。知道一个集合是由一个正则语法
产生的当且仅当它是正则集合。了解其他种类的有限状态机。
5.掌握Turing机的概念，知道Turing机如何识别一个符号串。
重点是语法结构、语言、演绎、演绎树的概念，掌握带有输出的有限状态机的定义，能够使用状态图和状态表表示带有输出的有限状态机，会求串联、kleene闭包，掌握没有输出的有限状态机（有限状态自动机）的概念，掌握正则表达式和正则集合的概念，掌握Turing机的概念，
知道Turing机如何识别一个符号串。难点是非确定的有限状态机，KLEENE定理，kleene闭包。
四.教学建议
离散数学是理论性较强的学科，学习离散数学的关键是准确掌握概念，勤于思考多与老师和同学沟通，多作练习。
五.教学要求的层次
各章教学的具体要求在后面列出的课程教学内容中给出，教学要求的层次为了解、理解和掌握。了解即能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。
第二部分教学媒体与教学过程建议
一、课程教学总学时数、学分数
课程教学总学时数为144学时，其中授课144学时，开设二学期。学分数为6学分。
二、文字教材与音像教材的配合
1.课程以文字教材为主，文字教材担负起形成整个课程体系系统性和完整性的任务，是学生
学习的主要媒体形式。因此教材要概念准确，条理清晰，深入浅出，便于自学。
1.幻灯教材作为文字教材的强化媒体，配合文字教材讲授课程的重点、难点以及解题的分析
方法与思路。
1.两者互相补充，互相配合。
三、学时的具体分配
教学内容授课学时
第一章集合论基础
§1.1集合的基本概念 2
§1.2 关系
1.2.1关系的基本概念及其性质 1
1.2.2等价关系 1
1.2.3部分序关系 1
§1.3映射
1.3.1集合的基数 1
1.3.2可数集合 1
1.3.3不可数集合 1
§1.4 集合在计算机科学中的应用 1
1.4.1关系在关系数据库中的应用
1.4.2关系代数与数据子语言
1.4.3等价关系在计算机中的应用
1.4.4序关系在项目管理中的应用
第二章命题逻辑
§2.1 命题以及逻辑联结词
2.1.1 命题 1
2.1.2 逻辑联结词 1
§2.2 命题公式
2.2.1 公式 1
2.2.2 解释 1
§2.3 命题公式的等价关系和蕴含关系
2.3.1 公式的等价 1
2.3.2 公式的蕴涵 1
2.3.3 演绎 1
2.3.4 公式蕴涵的证明方法 1
§2.4 范式
2.4.1 析取范式和合取范式 1
2.4.2 主析取范式和主合取范式 2
2.4.3 恒真恒假性的判定 1
§2.5 命题逻辑在二值逻辑器件和语句逻辑中的应用 1 第三章谓词逻辑
§3.1 谓词逻辑的基本概念
3.1.1 谓词和量词 1
3.1.2 改名规则 1
§3.2 谓词公式
3.2.1 公式 1
3.2.2 解释 1
§3.3 谓词公式的等价关系和蕴含关系
3.3.1 公式的等价和蕴涵 2
3.3.2 谓词演算的推理理论 2
§3.4 范式
3.4.1 前束范式 1
3.4.2 Skolem范式 1
§3.5 例 1 §3.6 谓词逻辑的应用 1
3.6.1谓词逻辑与数据子语言
3.6.2谓词逻辑与逻辑程序设计语言
第四章图与网络
§4.1 图
4.1.1 图的基本概念 2
4.1.2 权图Dijkstra算法 1
§4.2 树
4.2.1 树及其等价命题 2
4.2.2 最优树Kruskal算法 1
4.2.3 求最优树的其它算法 1 §4.3 有向图Euler路
4.3.1 有向图与有向树 2
4.3.2 Euler路Euler图 2
4.3.3 无向图无向图中的Euler路 1 §4.4 Hamilton图
4.4.1 Hamilton路Hamilton图的必要条件 1
4.4.2 Hamilton图的若干充分条件 2 §4.5 平面图
4.5.1 平面图判定库拉托夫斯基判定准则 1
4.5.2 平面图的Euler公式 1
4.5.3 平面图的对偶图柏拉图体 1
4.5.4 平面图的着色 1 §4.6 匹配二部图 1 §4.7 Konig无限性引理 1 §4.8 网络优化算法 1
4.8.1 图与网络的数据结构
4.8.2 单源最短路径问题具体算法及实现和比较
4.8.3 最大流问题具体算法及实现和比较
第五章数论基础
§5.1 整除性辗转相除
5.1.1 整除及其性质 2
5.1.2 辗转相除 1
5.1.3 利用数的数码特征判别某些整除性 1 §5.2 互质质因数分解
5.2.1 整数互质 1
5.2.2 质数与合数算术基本定理 1 §5.3 合同一次同余式
5.3.1 合同及其性质 2
5.3.2 剩余类一次同余式 2 §5.4 秦九韶定理Euler函数
5.4.1 一次同余式组秦九韶定理 2
5.4.2 一元高次同余式的化简 1
5.4.3 剩余系遍历Euler函数 1 §5.5 一元高次同余式二次剩余 1
5.5.1 一元高次同余式的解
5.5.2 二次同余式二次剩余
5.5.3 二次剩余的判定Legendre符号
§5.6 数论在计算机通信安全中的应用 1
5.6.1 密码系统
5.6.2 凯撒密码
5.6.3 V igenere密码
5.6.4 Hill加密算法
5.6.5 RSA公钥系统
第六章群与环
§6.1 代数系统 3 §6.2 群的定义
6.2.1 半群 1
6.2.2 群 1
6.2.3 群的性质 2
§6.3 置换群
6.3.1 置换的定义 1
6.3.2 置换的轮换表法 1
6.3.3 置换的顺向圈表示 1
6.3.4 置换的奇偶性 1
§6.4 子群及其陪集
6.4.1 子群的定义0.5
6.4.2 子群的判别条件 1.5
6.4.3 循环群 1.5
6.4.4 陪集 2
§6.5 同构及同态
6.5.1 同态映射 1
6.5.2 同构映射 1
6.5.3 同态核 2
§6.6 环
6.6.1 环的定义 1
6.6.2 环的性质 3
§6.7 环同态
6.7.1 理想 1
6.7.2 环中合同关系 1
6.7.3 环同态与同构 1.5
6.7.4 单纯环与极大理想 1.5
§6.8 群与环在计算机科学中的应用 1
6.8.1 计数问题
6.8.2 纠错码
第七章多项式有限域
§7.1 域的特征素域
7.1.1 域的特征 1
7.1.2 素域 2
§7.2 多项式的整除性 3
§7.3 多项式的根 2.5 §7.4 有理域上的多项式 2.5 §7.5 分圆多项式
7.5.1 复数域上的分圆多项式 1.5
7.5.2 任意域上的分圆多项式 1
§7.6 有限域 4
§7.7 多项式编码方法及其实现 1 第八章格与布尔代数
§8.1 引言0.5 §8.2 格的定义 1.5 §8.3 格的性质
8.3.1 对偶原理 1.5
8.3.2 格的其它性质 1
8.3.3 格的同态与同构 1.5
§8.4 几种特殊的格 3
8.4.1 有界格
8.4.2 有余格
8.4.3 分配格
8.4.4 模格
§8.5 布尔代数 4
8.5.1 布尔代数的定义及其性质
8.5.2 有限布尔代数的表示理论
8.5.3 布尔代数的同态与同构
§8.6 布尔表达式的化简问题 1 §8.7 格与布尔代数在计算机科学中的应用 1
8.7.1 开关电路函数
8.7.2 逻辑门
8.7.3 全加器的逻辑设计
第九章语言和有限状态机
§9.1 语言和语法 2
9.1.1 语法结构
9.1.2 语法结构的类型
9.1.3演绎树
9.1.4 Backus-Naur form
§9.2 带有输出的有限状态机 2 §9.3 没有输出的有限状态机 2 §9.4 语言识别 2
9.4.1 正则集合
9.4.2 KLEENE定理
9.4.3 其它几种类型的有限状态机
§9.5 Turing机 1
《离散数学》教学大纲 课程编码：11272016 课程名称：离散数学 英文名称：Discrete Mathematics 开课学期： 学时/学分：42/ 课程类型：专业基础课 开课专业：信息管理专业本科生 选用教材：《离散数学》清华大学出版社2004年3月第二版 主要参考书： 1、李大友主编：《离散数学》，清华大学出版社2003年版。 2、耿素云等著：《离散数学》，高等教育出版社1999年版。 一、课程性质、目的与任务 离散数学是全国高等学校信息管理专业开设的主干课程之一，是信息管理专业本科生必修的重要基础理论课程。本课既可为其他课程的学习提供理论基础，同时也使学生掌握一些基本数学理论。 通过本课程的学习，同学们应系统掌握离散数学的基本理论。透过现代数学的观点和内容，以开阔学生的眼界，启迪他们的思维。培养学生抽象概括问题的能力、逻辑推理能力、空间想象能力和动手能力。以及通过实践加深对理论的理解程度。 二、教学基本要求 1、全面掌握本学科的基本概念、基本理论和基本方法。 2、全面了解集合、关系、代数系统、图论等基本知识。 3、注重培养学生的思维能力，采用理论与实践相结合，理论讲述与案例分析相结合的方法进行教学，培养和提高学生分析问题和解决问题的能力，使学生完成本门课程的学习任务之后，能够自觉地对实践中存在的问题进行反思并提出解决办法。 三、各章节内容及学时分配 第一章集合论（4/2学时） 教学目的与要求 了解集合、集合的覆盖、笛卡儿积的概念。熟练掌握子集的概念和集合的运算。掌握集合的性质。
第一节集合的基本概念 第二节子集、集合的相等 第三节集合的运算及其性质 第四节笛卡儿积 第五节集合的覆盖与划分 考核要求 了解：集合、集合的覆盖、笛卡儿积的概念 理解：集合的性质 掌握：子集的概念和集合的运算 第二章二元关系（6/4学时） 教学目的与要求 了解关系的定义和基本类型。掌握关系的闭包和偏序关系。熟练掌握等价关系和关系的运算。 教学内容 第一节关系的定义及表示 第二节关系的运算 第三节关系的基本类型 第四节关系的闭包 第五节等价关系 第六节偏序关系 考核要求 了解：关系的定义和基本类型 理解：关系的闭包和偏序关系 掌握：等价关系和关系的运算 第三章函数（4/2学时） 教学目的与要求 了解集合的基数。掌握函数的基本概念。熟练掌握函数的复合、反函数。
实验1 1实验内容 （1）求任意一个命题公式的真值表。 （2）利用真值表求任意一个命题公式的主范式。 （3）利用真值表进行逻辑推理。 注：（2）和（3）可在（1）的基础上完成。 2实验目的 真值表是命题逻辑中的一个十分重要的概念，利用它几乎可以解决命题逻辑中的所有问题。例如，利用命题公式的真值表，可以判断命题公式的类型、求命题公式的主范式、判断两命题公式是否等价，还可以进行推理等。 本实验通过编写一个程序，让计算机给出命题公式的真值表，并在此基础上进行命题公式类型的判定、求命题公式的主范式等。目的是让学生更加深刻地理解真值表的概念，并掌握真值表的求解方法及其在解决命题逻辑中其他问题中的应用。 3算法的主要思想 利用计算机求命题公式真值表的关键是：①给出命题变元的每一组赋值；②计算命题公式在每一组赋值下的真值。 真值表中命题变元的取值具有如下规律：每列中0 和1 是交替出现的，且0 和1 连续出现的个数相同。n 个命题变元的每组赋值的生成算法可基于这种思想。 含有n个命题变元的命题公式的真值的计算采用的方法为“算符优先法”。 为了程序实现的方便，约定命题变元只用一个字母表示，非、合取、析取、蕴含和等价联结词分别用！、&、|、－、＋来表示。 算符之间的优先关系如表1-1所示： 表1-1算符优先级
优先算法，我们采用两个工作栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。算法的基本思想是： （1）首先设置操作数栈为空栈，符号“@”为运算符的栈底元素； （2）调用函数Divi（exp，myopnd）得到命题公式包含的命题变元序列myopnd （按字典序排列，同一个命题变元只出现一次）； （3）依次读入命题公式中的每个字符，若是命题变元则其对应的赋值进OPND 栈，若是运算符，则和OPTR栈的栈顶运算符比较后作相应操作，直至整个命题公式求值完毕。
《离散数学》课程考试大纲 课程名称：离散数学 教学时数：56 考试对象： A08、C08计算机 一、考试内容及要求 1．考试范围： 命题演算及其形式系统、谓词演算及其形式系统、集合及其运算、关系、函数、群论、格和布尔代数。 2．考试要求： （一）命题演算及其形式系统 掌握命题的概念掌握命题公式的概念；熟练掌握利用求任意命题公式的析取范式、主析取范式、合取范式和主合取范式的方法。 （二）谓词演算及其形式系统 掌握两种量词及其用法；掌握谓词公式的定义；掌握基本的谓词演算的等价式和蕴涵式。 （三）集合及其运算 掌握集合的概念及表示法；理解两个集合相等的定义和充分必要条件；掌握子集、真子集、空集、全集、幂集的定义；熟练掌握集合的五种基本运算：并、交、补、差及其满足的性质。 （四）关系 掌握笛卡儿积的概念；深刻理解关系的两个定义；深刻理解关系的五种性质：自反、对称、传递、反对称和反自反；能够判断任给的关系具有哪些性质；熟练掌握关系的三种特殊运算：复合运算、逆运算和闭包运算；掌握二种特殊的关系：等价关系、序关系。 （五）函数 掌握函数的概念；特殊函数类；函数的合成；了解逆函数。 （六）群论 掌握代数系统的定义和有关基本概念；熟练掌握群的定义和群的性质；掌握子群及其陪集概念和性质；掌握同态与同构的概念和性质；熟练掌握群同态和同构的证明方法。 （七）格与布尔代数 掌握格和代数格的基本概念；掌握格的基本性质；掌握几种特殊格的基本概念和性质；能够判断分配格和有余格；利用格的概念和性质证明一些基本定理；熟练掌握布尔代数的基本概念和有关性质。 二、考试形式 闭卷考试
三、试卷结构 第一篇集合论约占25％ 第二篇数理逻辑约占30％ 第三篇群论15％ 第四篇格和布尔代数 30% 题型比例： 判断题30分占30%，命题的符号化表示18分占18%，改错题12分占12%，证明和应用题40分占40%。 四、说明 试题由任课教师出A、B卷随机抽取。
《离散数学》课程教学大纲课程编号:02700013 课程名称：离散数学 英文名称：Discrete Mathematics 课程类型: 专业基础课 总学时：108 讲课学时：108 实验学时：0 学分：5 适用对象: 计算机科学与技术专业 先修课程：高等数学、线性代数等 一、课程简介 离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机科学的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且离散数学所提供的训练可以帮助学生提高抽象思维能力和逻辑推理能力，有益于学生严谨、完整、规范的科学态度的培养。为将来参与创新性的研究和开发工作打下坚实的基础。 二、课程性质、目的和任务 1.性质:本课程是为计算机专业本科开设的专业基础课。 2.目的:《离散数学》以研究离散量的结构和相互之间的关系为主要目标，在信息处理技术、计算机软硬件的设计等领域都有着广泛应用。 3.任务:通过这门课程的学习，要使学生掌握离散数学的基本概念和基本原理，以现代数学的方法，初步掌握处理离散结构所必须的一些基本数学工具和方法。同时，也要培养学生抽象思维、逻辑推理，符号演算和慎密概括的能力，从而使学生具有良好的专业理论素质，提高学生分析和解决实际问题的能力。 三、教学基本要求 通过本课程的学习，使学生了解和掌握关于离散量的基本概念及其相关理论，为后继课程的学习作必要的理论准备。基本要求：（1）学习数理逻辑最基本的内容，掌握命题逻辑及谓词逻辑的基本概念，掌握命题演算的方法，掌握命题推理及谓词推理的基本理论，并会用推理理论进行逻辑论证。（2）学习集合论的基本概念及性质，掌握集合运算及证明的基本理论和方法；学习二元关系的概念与性质，掌握等价关系和偏序关系，并使学生从更高层次理解函数。（3）学习代数系统的基本知识，掌握二元运算的定义和性质，了解代数系统的子代数和积代数、同态与同构等概念，掌握半群、幺半群、群、环、域和格、布尔代数等代数系统的定义及其性质。（4）学习图论的基本概念及其理论，主要掌握简单图和一些特殊图的性质，包括欧拉图和哈密尔顿图、二部图、平面图等。掌握树的基本概念及其相关运算。学会使用图论方法解决具体问题。
实验一命题逻辑公式化简 【实验目的】加深对五个基本联结词（否定、合取、析取、条件、双条件）的理解、掌握利用基本等价公式化简公式的方法。 【实验内容】用化简命题逻辑公式的方法设计一个表决开关电路。 实验用例：用化简命题逻辑公式的方法设计一个 5 人表决开关电路，要求 3 人以上（含 3 人）同意则表决通过（表决开关亮）。 【实验原理和方法】 （1）写出5人表决开关电路真值表，从真值表得出5 人表决开关电路的主合取公式（或主析取公式），将公式化简成尽可能含五个基本联结词最少的等价公式。 （2）上面公式中的每一个联结词是一个开关元件，将它们定义成 C 语言中的函数。 （3）输入5人表决值（0或1），调用上面定义的函数，将5人表决开关电路真值表的等价公式写成一个函数表达式。 （4）输出函数表达式的结果，如果是1，则表明表决通过，否则表决不通过。 参考代码： #include
总复习题 1. 设︱A ︱=5, ︱P(B)︱=512, ︱P(A ∩B)︱=8, 则︱A ⊕B ︱＝ , ︱A ∪B ︱＝ 。 2. 设p :选小王当班长，q ：选小李当班长，则选小王或小李中的一人当班长可符号化为____。 3. 命题公式根据赋值可分为________________、________________和______________三类。 4. 含N 个个命题变项的命题公式有______________组赋值，有_____________个真值。 5. ()A A B ∨∧=______________，()A A B ∧∨=__________________。 6. 设{|3,,14}A x x k k N k ==∈≤≤，则用列举法表示A =________________________。 7. 集合A ={1，2}的幂集P (A )与A 的笛卡尔积()P A A ?=____________________________ ____________________________________________________________________________。 8. 某无向图G 中，共有边15条，该图中共有5度顶点2个，4度顶点3个，剩下的均为2度顶 点，则该图中共有顶点 个。 9. 一个结点为n 的无向完全图，其边的数目为 。 10．已知
离散数学实验报告（实验ABC） 专业班级 学生姓名 学生学号 指导老师 完成时间
目录 第一章实验概述..................................... 错误!未定义书签。 实验目的....................................... 错误!未定义书签。 实验内容....................................... 错误!未定义书签。 实验环境....................................... 错误!未定义书签。第二章实验原理和实现过程........................... 错误!未定义书签。 实验原理....................................... 错误!未定义书签。 建立图的邻接矩阵，判断图是否连通 ............ 错误!未定义书签。 计算任意两个结点间的距离 ................... 错误!未定义书签。 对不连通的图输出其各个连通支 ................ 错误!未定义书签。 实验过程（算法描述）........................... 错误!未定义书签。 程序整体思路 ............................... 错误!未定义书签。 具体算法流程 ................................ 错误!未定义书签。第三章实验数据及结果分析........................... 错误!未定义书签。 建立图的邻接矩阵并判断图是否连通的功能测试及结果分析错误!未定义书签。 输入无向图的边 .............................. 错误!未定义书签。 建立图的连接矩阵 ............................ 错误!未定义书签。 其他功能的功能测试和结果分析................... 错误!未定义书签。 计算节点间的距离 ............................ 错误!未定义书签。 判断图的连通性 .............................. 错误!未定义书签。 输出图的连通支 .............................. 错误!未定义书签。 退出系统 .................................... 错误!未定义书签。第四章实验收获和心得体会........................... 错误!未定义书签。
《离散数学》 课程设计 学院计算机学院 学生姓名 学号 指导教师 评阅意见
提交日期 2011 年 11 月 25 日 引言 《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。 实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性） 一、前言引语：二元关系是离散数学中重要的内容。因为事物之间总是可以根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之
间存在的关系。 二、数学原理：自反、对称、传递关系 设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R 就是A×B的一个合于{()∈A×}的子集合 设R是集合A上的二元关系： 自反关系：对任意的x∈A,都满足<>∈R，则称R是自反的，或称R具有自反性，即R在A上是自反的?(?x)((x∈A)→(<>∈R))=1 对称关系：对任意的∈A，如果<>∈R，那么<>∈R，则称关系R是对称的，或称R具有对称性，即R在A上是对称的? (?x)(?y)((x∈A)∧(y∈A)∧(<>∈R)→(<>∈R))=1 传递关系：对任意的∈A，如果<>∈R且<>∈R，那么<>∈R，则称关系R是传递的，或称R具有传递性，即R在A上是传递的? (?x)(?y)(?z)[(x∈A)∧(y∈A)∧(z ∈A)∧((<>∈R)∧(<>∈R)→(<>∈R))]=1 三、实验原理：通过二元关系与关系矩阵的联系，可以引入N维数组，以数组的运算来实现二元关系的判断。 图示：
一、选择题： 1.下列句子是命题的是( )。 A. 你喜欢我吗? B. 这里的景色真美啊! C. 2x = 9。 D. 明年国庆节是晴天。 2.设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为( )。 ∧) A. ?P∧?Q B. ?(P Q C. ?(P?Q) D. ?(?P∨?Q) 3.下列语句不是 ．．命题的是( )。 A.黄金是非金属。 B.要是他不上场，我们就不会输。 C.他跑100米只用了10秒钟，你说他是不是运动健将呢? D.他跑100米只用了10秒钟，他是一个真正的运动健将。 4.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )。 A.P∨Q B.P∧?Q C.P→?Q D.P∨?Q 5.下列句子不是 ．．命题的是( )。 A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 6.在命题演算中，语句为真为假的一种性质称为( )。 A. 真值 B. 陈述句 C. 命题 D. 谓词 7.命题公式?(P∧Q)→R的成真指派是( )。 A. 000，001，110 B. 001，011，101，110，111 C. 全体指派 D. 无 8.下列命题中，不正确的是( )。 ∈?,{{?}}} A.{?}{ ∈?,{?}} B.{?}{ C.{?}?{?,{?}} D. ??{?,{?}} 9.命题公式P∧(Q∨? R)的成真指派是( )。 A.110，111，100 B.110，101，011 C.所有指派 D.无 ∨?( )。 10.设P,Q,R是命题公式,则P→R，Q→R，P Q A. P B. Q C. R D. ?R 11.下列是两个命题变元p，q的小项是( ) ∨C．?p q ∨∨ ∧D．?p p q A．p∧?p q ∧B．?p q 12.关于命题变元P和Q的大项M01表示( )。 ∨ C.P∨?Q D.P∧?Q ∧ B.?P Q A.?P Q 13.设P：明天天晴；q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为( ) ?p→?q C. ?p??q D. ?p→q A. p→?q B. 14.下列命题公式是永真式的是( ) (p→q)∨q D. (p∨p)∧(p→?p) ?(p→q)∧q C. A. (p∧?p)?q B.
《离散数学》期末复习大纲 一、数理逻辑 [复习知识点] 1、命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价?），复合命题 2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足）， 公式的基本等值式 3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式 4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法） 5、命题逻辑的推理理论 6、谓词、量词、个体词（一阶逻辑3要素）、个体域、变元（约束出现与自由出 现） 7、命题符号化、谓词公式赋值与解释，谓词公式的类型（永真、永假、可满足） 8、谓词公式的等值式（代换实例、消去量词、量词否定和量词辖域收与扩、量 词分配）和置换规则（置换规则、换名规则） 9、一阶逻辑前束范式（定义、求法） 本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、 公式类型的判定、命题逻辑的推理、谓词与量词、命题符号化、谓词公式赋值与 解释、求前束范式。 [复习要求] 1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方 法。 2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简 其它公式，公式在解释下的真值。 3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取） 范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。 4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公 式等价方法。 5、掌握命题逻辑的推理理论。 6、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑
联结词描述一个简单命题；掌握命题的符号化。 7、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定 解释下真值的方法；了解谓词公式的类型。 8、掌握求一阶逻辑前束范式的方法。 二、集合 [复习知识点] 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂 集 2、集合的交、并、差、补以及对称差等运算及有穷集的计数（文氏（Venn）图、包含排斥原理） 3、集合恒等式（幂等律、交换律、结合律、分配律、吸收律、矛盾律、德摩根 律等）及应用 本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明。 [复习要求] 1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。 2、掌握集合的表示法和集合的交、并、差、补、对称差等基本运算。 3、掌握集合运算基本规律，证明集合等式的方法。 三、二元关系 [复习知识点] 1、序偶、迪卡儿积，迪卡儿积的性质及运算。 2、二元关系（定义、空关系、全域关系、恒等关系）、关系表达式、关系矩阵与 关系图 3、关系的定义域、值域、限制、像、复合关系（右复合）与逆关系 4、关系的性质（自反性、反自反性、对称性、反对称性、传递性） 5、关系的闭包（自反闭包、对称闭包、传递闭包） 6、等价关系与等价类、商集、划分 7、偏序关系与哈斯图、极大/小元、最大/小元
“离散数学”课程教学大纲 课程英文名称：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. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨) ()(Q P Q P Q P ?∧?∨∧??Q) P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)() ()(R P Q P ∨∧∧?
①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q 7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥x 。 答案： 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??
《离散数学》实验报告 专业网络工程 班级 姓名 学号 授课教师 二 O 一六年十二月
目录 实验一联结词的运算 实验二根据矩阵的乘法求复合关系 实验三利用warshall算法求关系的传递闭包实验四图的可达矩阵实现
实验一联结词的运算 一．实验目的 通过上机实验操作，将命题连接词运算融入到C语言的程序编写中，一方面加强对命题连接词运算的理解，另一方面通过编程实现命题连接词运算，帮助学生复习和锻炼C语言知识，将理论知识与实际操作结合，让学生更加容易理解和记忆命题连接词运算。二．实验原理 (1) 非运算, 符号: ,当P=T时，P为F, 当P=F时，P为T 。 (2) 合取, 符号: ∧ , 当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。 (3) 析取, 符号: ∨ , 当且仅当P和Q的真值同为假，命题P∨Q的真值才为假；否则，P∨Q的真值为真。 (4) 异或, 符号: ▽ , 当且仅当P和Q的真值不同时，命题P▽Q的真值才为真；否则，P▽Q的真值为真。 (5) 蕴涵, 符号: →, 当且仅当P为T,Q为F时，命题P→Q的真值才为假；否则，P→Q 的真值为真。 (6) 等价, 符号: ?, 当且仅当P,Q的真值不同时，命题P?Q的真值才为假；否则，P→Q的真值为真。 三．实验内容 编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。四．算法程序 #include
《离散数学》课程教学大纲 课程代码：090132119 课程英文名称：Discrete Mathematics 课程总学时：48 讲课：48 实验：0 上机：0 适用专业：信息与计算科学 大纲编写（修订）时间：2017.11 一、大纲使用说明 （一）课程的地位及教学目标 本课程是信息与计算科学专业的一门专业基础课，通过本课程的学习，一方面，为计算机科学的专业课程，如数据结构、编译系统、操作系统、数据库、信息管理系统、人工智能、形式语言等提供必要的数学基础；另一方面，可以培养学生的逻辑思维能力，更好地实现素质教育的目的。 （二）知识、能力及技能方面的基本要求 通过本课程的学习，学生将达到以下要求： 1利用基本原理，解决实际问题的能力 2 利用数学手段研究计算机专业问题的能力 3 通过本课程的学习，使学生获得利用数学手段解决具体问题的技能。如利用数理逻辑理论进行逻辑推理的技能，利用集合论理论分析各类关系的技能，利用代数结构理论讨论各类代数系统及其关系的技能，利用图论分析最短路等技能。 （三）实施说明 1．教学方法：课堂讲授中要重点对基本概念、基本方法和解题思路的讲解；采用启发式教学，培养学生思考问题、分析问题和解决问题的能力；引导和鼓励学生通过实践和自学获取知识，培养学生的自学能力；增加讨论课，调动学生学习的主观能动性。讲课要联系实际并注重培养学生的创新能力。 2．教学手段：本课程属于理论基础课，在教学中主要以理论讲解为主，辅以适当的课堂练习，帮助同学更好的理解基本概念及基本方法，以确保在有限的学时内，全面、高质量地完成课程教学任务。 （四）对先修课的要求 本课程的教学必须在完成先修课程之后进行。本课程主要的先修课程有：高等代数1。 （五）对习题课、实践环节的要求 1．对重点、难点章节（如：稳定变应力下的疲劳强度计算、螺栓组强度计算、齿轮传动受力分析、轴系结构设计等）应安排习题课，例题的选择以培养学生消化和巩固所学知识，用以解决实际问题为目的。 2．课后作业要少而精，内容要多样化，作业题内容必须包括基本概念、基本理论及设计计算方面的内容，作业要能起到巩固理论，掌握计算方法和技巧，提高分析问题、解决问题能力，熟悉标准、规范等的作用，对作业中的重点、难点，课上应做必要的提示，并适当安排课内讲评作业。学生必须独立、按时完成课外习题和作业，作业的完成情况应作为评定课程成绩的一部分。 （六）课程考核方式 1．考核方式：考试 2．考核目标：在考核学生对离散数学的基本知识、基本方法的基础上，重点考核学生的分
一、选择题：（每题2’） 1、下列语句中不是命题的有（ ）。 A ．离散数学是计算机专业的一门必修课。 B ．鸡有三只脚。 C ．太阳系以外的星球上有生物 。 D ．你打算考硕士研究生吗? 2、命题公式A 与B 是等价的，是指（ ）。 A ． A 与B 有相同的原子变元 B ． A 与B 都是可满足的 C ． 当A 的真值为真时，B 的真值也为真 D ． A 与B 有相同的真值 3、所有使命题公式P∨(Q∧?R)为真的赋值为（ ）。 A ． 010，100，101，110，111 B ． 010，100，101，111 C ． 全体赋值 D ． 不存在 4、合式公式 (P∧Q)R 的主析取范式中含极小项的个数为（ ）。 A ．2 B ．3 C ．5 D ．0 5、一个公式在等价意义下，下面哪个写法是唯一的（ ）。 A ．析取范式 B ．合取范式 C ．主析取范式 D ．以上答案都不对 6、下述公式中是重言式的有（ ）。 A ．(P ∧Q) (P ∨Q) B ．(P Q) (( P Q)∧(Q P)) C ．(P Q)∧Q D ．P (P ∧Q) 7、命题公式 (P Q) ( Q ∨P) 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0 B ．1 C ．2 D ．3 8、若公式 (P∧Q)∨(P∧R) 的主析取范式为 m 001∨m 011∨m 110∨m 111 则它的主合取范式为（ ）。 A ．m 001∧m 011∧m 110∧m 111 B ．M 000∧M 010∧M 100∧M 101 C ．M 001∧M 011∧M 110∧M 111 D ．m 000∧m 010∧m 100∧m 101 9、下列公式中正确的等价式是（ ）。 A ．(x)A(x) ( x)A(x) B ．(x) (y)A(x, y) (y) (x) A(x, y) C ．(x)A(x) (x)A(x) D ．(x) (A(x) ∧B(x)) ( x) A(x) ∨(x) B(x) 10、下列等价关系正确的是（ ）。 A ．x ( P(x) ∨Q(x) ) x P(x) ∨x Q(x) B ．x ( P(x) ∨Q(x) ) x P(x) ∨x Q(x) C ．x ( P(x) Q ) x P(x) Q D ． x ( P(x) Q ) x P(x) Q 11、设个体域为整数集，下列真值为真的公式是（ ）。 A ．x y （x·y=1） B ．x y （x·y=0） C ． x y （x·y=y） D ．x y （x+y=2y ） 12、设S={,{1},{1,2}}，则有（ ）S 。 A ．{{1,2}} B ．{1,2 } C ．{1} D ．{2} 13、下列是真命题的有（ ）。 A ．{a}{{a}} B ．{{}}{,{}} C ．{,{}} D ．{}{,{}}
《离散数学》教学大纲 课程编号：CE3008 课程名称：离散数学英文名称：Discrete Mathematics 学分/学时：3.0/48 课程性质：必修 适用专业：网络工程、信息安全建议开设学期：3 先修课程：高等数学、线性代数开课单位：网络与信息安全学院 一、课程的教学目标与任务 离散数学是研究离散数量关系和离散结构数学模型的数学分支的统称，是网络工程、信息安全等计算机相关专业的专业平台基础课，也是学习专业课程必不可少的数学工具。本课程的数理逻辑是用符号化的方法研究推理的规律，集合论是现代数学的基础，代数结构、图论等知识在计算机相关的学科都有着广泛的应用。 通过本课程的学习，使学生掌握离散数学的基本概念和基本原理，掌握一些基本的能够描述离散对象的结构，了解这些离散结构的特性、离散结构之间的关系，理解离散结构在计算机问题求解中的意义与基本运用；进一步提高抽象思维和逻辑推理的能力，培养学生对简单问题进行合理数学建模的能力，使得学生能够在理论推导上有所提高，并且能够对计算机描述的世界进行基本建模；掌握一些基本的计数技巧，帮助学生掌握命题逻辑和谓词逻辑的概念、基本理论以及应用逻辑的理论建模，为进一步学习后续课程打下必要基础。 二、课程具体内容及基本要求 （一）数理逻辑（12学时） 具体内容提要： （1）命题逻辑基本概念 ●命题与联接词； ●命题公式及其赋值。 （2）命题逻辑等值演算 ●等值式； ●析取范式与合取范式； ●联接词的完备集。 （3）命题逻辑推理理论 ●推理的形式结构；
●自然推理系统P。 （4）一阶逻辑基本概念 ●一阶逻辑命题的符号化； ●一阶逻辑公式及其解释。 （5）一阶逻辑等值演算与推理理论 ●一阶逻辑等值式与置换规则； ●一阶逻辑的前束范式； ●一阶逻辑的推理理论。 1.基本要求 （1）对于命题逻辑：了解范式的应用和全功能联结词的应用；熟悉命题与联结词、命题公式及其赋值、命题公式的等值式模式、范式（析取范式和合取范式、主析取范式和主合取范式）、推理的形式结构和自然推理系统；掌握自然语言的形式描述、掌握利用真值表和等值演算的方法进行命题演算和范式表示、掌握用命题逻辑的推理规则进行证明的常用方法。 （2）对于一阶逻辑：了解一阶逻辑的前束范式和推理理论、了解一阶逻辑的应用；熟悉一阶逻辑的基本概念、一阶逻辑的合式公式；掌握一阶逻辑的命题符号化、一阶逻辑公式的解释及分类、掌握利用一阶逻辑的等值式和置换规则方法进行谓词演算。 2.重点、难点 重点：命题的符号化；命题公式的赋值与类型；等值式模式；析取范式与合取范式、极小项与极大项、主析取范式与主合取范式；求主析取(主合取)范式的方法；利用主析取(主合取)范式求公式的成真赋值、成假赋值、判断公式的类型、判断公式是否等值；推理的形式结构与推理规则；在自然推理系统中构造证明的直接证明法、附加前提证明法、归谬法；一阶逻辑命题的符号化；一阶逻辑公式、解释及判定其类型；一阶逻辑中重要的等值式；置换规则、换名规则、代替规则；前束范式；自然推理系统中的推理规则；在自然推理系统中构造推理的证明。 难点：“相容或”与“排斥或”；求主析取(主合取)范式；真值表法、等值演算法、主析取范式法等基本推理方法；直接证明法、附加前提证明法、归谬法等基本证明方法；一阶逻辑公式的解释；一阶逻辑的推理规则与证明。 3.作业及课外学习要求 选择与基本要求相关的典型习题布置为作业，阅读其他经典参考书中相关的内容。 （二）集合论（16学时）
第一部分数理逻辑 第一章命题逻辑 重点： ●熟练掌握联结词的定义； ●掌握数理逻辑中命题的翻译及命题公式的定义； ●熟记基本的等价公式和蕴涵公式； ●利用真值表技术和公式法求公式的主析取范式和主合取范式； ●熟练掌握应用基本推理方法完成命题逻辑推理： 1.直接证法 2.反证法 3.CP规则 难点： ●如何正确地掌握对语言的翻译； ●如何利用推理方法正确的完成命题推理。 第二章谓词逻辑 重点： ●谓词、量词、个体域的概念； ●谓词逻辑中带量词命题的符号化； ●熟记基本的谓词等价公式； ●求公式的前束范式； ●掌握谓词逻辑的推理规则以及能够熟练地完成一阶逻辑推理；难点： ●谓词逻辑中带量词命题的符号化； ●如何利用推理方法正确地完成一阶逻辑推理。
第二部分集合论 第三章集合与关系 重点： ●掌握集合的五种基本运算和集合相等的证明方法； ●幂集的概念以及和子集的关系； ●序偶和笛卡尔积的概念； ●关系定义及其和笛卡尔积之间的联系； ●关系的复合； ●关系的五种性质及其判断和证明； ●关系的闭包； ●等价关系定义、证明及其与等价类、集合的划分间的关系； ●偏序关系的定义和证明，哈斯图； ●偏序关系中的特殊元素； 难点： ●如何正确证明集合之间包含和相等关系； ●如何正确地理解和判断关系的性质； ●非常重要的关系性质的证明方法——按定义证明法； ●如何正确地掌握等价关系及相应的等价类与集合划分之间的关系； ●如何正确地理解和判断偏序关系中的八种特殊元素。 第四章函数
重点： ●能够判定某个二元关系是否是函数； ●几种特殊的函数：满射，单射，双射； 难点： ●如何正确地判断三种特殊函数。 第三部分代数结构 重点： ●理解代数结构的构成和研究方法； ●代数结构中运算的性质以及特殊元素； ●广群?半群?独异点?群； ●群的定义与性质； ●环与域的判断和证明； ●格的两种定义； ●特殊格：分配格、有界格、有补格、有补分配格； ●有补分配格与布尔代数之间的联系； 难点： ●循环群的判断和证明； ●如何正确理解由偏序关系定义的格与由代数系统定义格之间的关系 和区别； ●如何正确理解布尔代数的概念。 第四部分图论 重点： ●掌握图论的基本定理：握手定理及其推论的内容，并且能灵活地应用 （如已知边数和一些结点的度数，求另一些结点的度数等），在图论 中的很多证明都要用到握手定理及推论。 ●熟悉图的矩阵表示，在理解通路和回路相关概念的基础上，掌握可达
实验报告 （2013 / 2014 学年第一学期） 课程名称离散数学 实验名称利用真值表法求取主析取范式 以及主合取范式的实现 实验时间2013 年10 月23 日指导单位计算机学院、软件学院 指导教师 学生姓名班级学号 学院(系) 计算机、软件 专业软件工程 学院
实验报告 实验名称利用真值表法求取主析取范式 指导教师 以及主合取范式的实现 实验类型验证实验学时 4 实验时间2013.10.23 一、实验目的和要求 1、编程实现用真值表法求取含三个以内变量的合式公式的主析取范式和主合取范式。 2、要求： 1)从屏幕输入含三个以内变量的合式公式（其中联结词按照从高到底 的顺序出现） 2)规范列出所输合式公式的真值表 3)给出相应主析取和主合取范式
二、实验内容 1.可用字符数组a记录输入的合式公式（其中'&'代表与，'|'代表或，'~' 代表非，'>'代表单条件，'='代表双条件) 2.多重循环显示真值表（1表示T，0表示F，先1后0）并对公式进行相 应赋值得数组b 3.函数递归计算各种赋值情况下b的取值 4.联接词运算符定义
三、实验设计及代码 1、求取真值表 void truetable(){ /*求真值表函数*/ char s1[30],s2[30],s3[30],s4[30]; int n,i,j,k,m; printf("您要计算真值表！\n"); printf("***************** 输入要计算的表达式(A~Z,a~z) ****" "************ \n"); printf("(其中'&'代表与 '|'代表或 '~'代表非 '>'代表单条件 " "'='代表双条件)\n"); gets(s4); printf(" \n您输入要计算的表达式为：%s \n",s4); n=got(s1, s4); if(!n) {printf("输入有误！\n");return;} m = (int)pow(2,n); printf("计算真值表如下:\n"); for(j=0;j<(int)strlen(s1);j++){ printf("%c ",s1[j]); } printf(" %s\n",s4); for(j=0;j
相关主题
文本预览