下载文档原格式
离散数学部分概念和公式总结命题：称能判断真假的陈述句为命题。
命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。
命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。
给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。
若指定的一组值使A的值为真，则称成真赋值。
真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。
将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。
命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。
（2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。
（3）若A至少存在一组赋值是成真赋值，则A是可满足式。
主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。
主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。
命题的等值式：设A、B为两命题公式，若等价式A↔B是重言式，则称A与B是等值的，记作A<=>B。
约束变元和自由变元：在合式公式∀x A和∃x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。
一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A↔B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。
前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。
集合的基本运算：并、交、差、相对补和对称差运算。
笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。
二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。
《离散数学》教学大纲（专科）《离散数学》教学大纲（专科）说明一．课程的性质本课程是为计算机科学与技术专业专科开设的专业基础课。
离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程，是学习专业理论不可少的数学工具。
离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个和可数个元素，充分描述了计算机科学离散性的特点。
在计算机科学中，离散数学与数据结构、操作系统、逻辑设计、算法分析、编译原理、人工智能、系统结构等课程联系紧密。
学习离散数学不仅为后续课程作必要的理论准备，而且其课程内容中所提供的一些把科学理论应用于实践的范例，可以培养学生逐步增强如何实施“科学理论---技术---生产力”转化的观念和方法，提高学生在知识经济时代中的适应能力。
同时本课程在培养学生的创新能力，提高学生的科研素质方面都有着重要作用。
二．课程的教学目的和要求在计算机科学教学中，离散数学主要是为专业服务的基础理论课，是一门概念较多、理论性较强，应用性较广的课程。
本课程主要教授数理逻辑、集合论、代数系统、图论方面的基础知识，是计算机科学与技术教学中一些后续课程学习的基础和工具。
通过本课程的学习，要使学生掌握离散数学的基本概念和基本原理，以现代数学的观点和方法，初步掌握处理离散结构所必须的描述工具和方法。
同时，也要培养学生抽象思维、慎密概括、逻辑推理的能力，从而使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力。
三．课程的主要教学内容1.集合论：集合的基本概念，集合的运算，包含排斥原理。
2.二元关系：集合的笛卡尔乘积，关系的定义，关系的表示法，特殊关系，复合关系和逆关系，关系的闭包运算。
3. 函数：函数的定义，特殊函数，复合函数和逆函数。
4. 代数结构：代数系统，特殊运算和特殊元素；同构概念，半群、群；子群，循环群，置换群；陪集和拉格朗日定理。
环、域；格与布尔代数。
5．图论：图的基本概念，通路、回路及图的连通性，赋权图的最短通路，图与矩阵表示、欧拉图与哈密顿图、平面图与二部图、无向树，有向树及其应用。
离散数学知识点整理离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、物理学等领域都有着广泛的应用。
以下是对离散数学中一些重要知识点的整理。
一、集合论集合是离散数学中最基本的概念之一。
集合是由一些确定的、互不相同的对象组成的整体。
集合的表示方法有列举法、描述法等。
列举法就是将集合中的元素一一列举出来，比如{1, 2, 3}；描述法是通过描述元素所具有的性质来表示集合，例如{x ｜ x 是大于 0 小于 5 的整数}。
集合之间的关系包括子集、真子集、相等。
如果集合 A 的所有元素都属于集合 B，那么 A 是 B 的子集；如果 A 是 B 的子集，且 B 中存在元素不属于 A，那么 A 是 B 的真子集；如果两个集合的元素完全相同，那么它们相等。
集合的运算有并集、交集、差集等。
并集是将两个集合中的所有元素合并在一起组成的新集合；交集是两个集合中共同拥有的元素组成的集合；差集是从一个集合中去掉另一个集合中的元素所得到的集合。
二、关系关系是集合中元素之间的某种联系。
比如在一个班级中，同学之间的“同桌关系”就是一种关系。
关系可以用矩阵和图来表示。
矩阵表示中，若元素之间存在关系则对应的位置为1，否则为0；图表示中，用点表示元素，用线表示关系。
关系的性质包括自反性、对称性、反对称性和传递性。
自反性是指每个元素都与自身有关系；对称性是指如果 a 与 b 有关系，那么 b 与 a 也有关系；反对称性是指如果 a 与 b 有关系且 b 与 a 有关系，那么 a ＝b；传递性是指如果 a 与 b 有关系，b 与 c 有关系，那么 a 与 c 有关系。
关系的运算有复合关系和逆关系。
复合关系是将两个关系组合起来得到新的关系；逆关系是将原关系中的元素顺序颠倒得到的关系。
三、函数函数是一种特殊的关系，对于定义域中的每个元素，在值域中都有唯一的元素与之对应。
函数的类型有单射、满射和双射。
单射是指不同的定义域元素对应不同的值域元素；满射是指值域中的每个元素都有定义域中的元素与之对应；双射是既是单射又是满射。
《离散数学》期末复习大纲一、数理逻辑[复习知识点]1、命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价↔），复合命题2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），公式的基本等值式3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）5、命题逻辑的推理理论6、谓词、量词、个体词（一阶逻辑3要素）、个体域、变元（约束出现与自由出现）7、命题符号化、谓词公式赋值与解释，谓词公式的类型（永真、永假、可满足）8、谓词公式的等值式（代换实例、消去量词、量词否定和量词辖域收与扩、量词分配）和置换规则（置换规则、换名规则）9、一阶逻辑前束范式（定义、求法）本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理、谓词与量词、命题符号化、谓词公式赋值与解释、求前束范式。
[复习要求]1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。
2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。
3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。
4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。
5、掌握命题逻辑的推理理论。
6、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；掌握命题的符号化。
7、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。
8、掌握求一阶逻辑前束范式的方法。
二、集合[复习知识点]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补以及对称差等运算及有穷集的计数（文氏（Venn）图、包含排斥原理）3、集合恒等式（幂等律、交换律、结合律、分配律、吸收律、矛盾律、德摩根律等）及应用本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明。
《离散数学》教学大纲前言离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。
是研究计算机科学的基本数学工具，离散数学是以离散量作为其研究对象，在离散数学中非常重视“能行性”问题的研究，要解决一个问题，首先要证明此问题解的存在性，同时要找出得到此问题解的步骤来，而且其步骤必须是有限的、有规则的。
这就构成了离散数学的特征。
在计算机科学中，离散数学与数据结构、操作系统、逻辑设计、算法分析、编译原理、人工智能、系统结构等课程联系紧密。
教学目的要求和内容离散数学是计算机类专业基础理论的核心课，它根据计算机科学的特点，主要研究离散对象之间的数据结构和相互关系。
它的预修课程是线性代数。
离散数学涉及的数学领域非常广，同时与计算机科学和相关学科关系非常密切，是很多计算机有关课程的基础，如：高级语言、数据结构、编译原理、操作系统、可计算性理论、人工智能、形式语言与自动机、信息管理与检索以及开关理论等，离散数学也是研究自动控制、管理科学、电子工程等的重要工具。
教学目的通过本课程的学习，为计算机各专业理论的讲授做好必要的准备知识，使得学生了解离散结构之间的关系和基于这些离散结构的算法，掌握基本的计数技巧，能够对一些简单的算法给出定量的分析，培养学生的抽象思维和严密的概括能力，强化思维的推理，能够在理论推导上有所提高，并且能够对计算机描述的世界进行基本建模，并为提高专业理论水平打下扎实的基础。
学生应该按照本大纲的具体要求，掌握基本的离散对象结构和特性，以及离散结构之间的关系和算法，能够对一些简单的算法给出定量的分析，并有较强的逻辑推理能力，了解机器证明的基本技术。
本课程以课堂讲授为主，计90学时，含有习题课讲解。
采取考试与小项目结合，并结合作业情况。
使用教材与参考书目1．邱学绍等编，离散数学，机械工业出版社，2005年9月。
2．耿素云，屈婉玲编著，离散数学（修订版），高等教育出版社，2004年1月。
3．Bernard Kolman, Robert C. Busby and Sharon Cutler Ross, Discrete Mathematical Structure, Prentice Hall, 2001.4．Richard Johnsonbaugh著，石纯一等译，人民邮电出版社，2003年9月。
离散数学关系的运算离散数学是研究离散结构和离散对象的数学分支。
其中，关系是离散数学中一个重要的概念。
关系的运算是指对不同关系进行操作，从而得到新的关系。
在离散数学中，常见的关系运算包括并集、交集、差集、补集和复合运算。
1. 并集：对于两个关系R和S，它们的并集R∪S是包含了两个关系的所有元素的集合。
即R∪S={x | x∈R 或 x∈S}。
并集运算可以合并两个关系中的元素，得到新的关系。
2. 交集：对于两个关系R和S，它们的交集R∩S是同时属于R和S的元素的集合。
即R∩S={x | x∈R 且 x∈S}。
交集运算可以得到两个关系中共同拥有的元素。
3. 差集：对于两个关系R和S，它们的差集R-S是属于R但不属于S的元素的集合。
即R-S={x | x∈R 且 xS}。
差集运算可以得到在R中存在但不在S 中的元素。
4. 补集：对于一个关系R，它的补集R'是所有不属于R的元素的集合。
即R'={x | x不属于R}。
补集运算可以得到关系R的补集。
5. 复合运算：对于两个关系R和S，它们的复合运算RS是通过将R的元素的后继者与S的元素的后继者进行连接得到的新关系。
即RS={(a,c) | 对于某个b∈B, (a,b)∈R 且 (b,c)∈S}。
复合运算可以通过连接两个关系的元素来构建新的关系。
这些关系运算在离散数学中具有重要的应用，常用于描述集合、图、逻辑等离散结构之间的关系。
对于每种关系运算，都有相应的运算规则和性质。
熟练掌握关系运算可以帮助我们更好地理解和分析离散结构中的关系。
第一章命题逻辑1.1 命题及其表示方法1.2 联结词1.3 命题公式与翻译1.4 真值表与等价公式1.5 重言式与蕴含式1.6 其它联结词1.7 对偶与范式1.8 推理理论1.1 命题及其表示方法命题：具有确定真值的陈述句命题的类型（原子命题和复合命题）命题的表示（一个命题标识符（比如P）表示确定的命题）重点：如何判断语句是否为命题。
1.2 联结词否定⌝合取∧析取∨条件→双条件↔重点：五种联结词的含义、真值表1.3 命题公式与翻译命题公式符号化：所谓命题的符号化就是把一个用文字叙述的句子相应地写成由命题标识符、联结词和括号表示的合式公式。
命题符号化的重要性命题符号化是很重要的，一定要掌握好，在命题推理中最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。
重点：命题的符号化符号化应该注意下列事项:①确定给定句子是否为命题。
②句子中连词是否为命题联结词。
③要正确地表示原子命题和适当选择命题联结词。
1.4 真值表与等价公式真值表的构造方法(1) 找出公式中所含的全体命题变元P1, P2, …, Pn, (若无下角标就按字典顺序排列), 列出2n个赋值. 赋值从00…0开始, 然后按二进制加法依次写出各赋值, 直到11…1为止.(2) 按从低到高的顺序写出公式的各个层次.(3) 对应各个赋值计算出各层次的真值, 直到最后计算出公式的真值.等价关系的含义等价式的判别方法•真值表法•等价演算法基本等价式（必须掌握）(1)对合律（双重否定）：⌝⌝P⇔P(2)幂等律：P∧P⇔P，P∨P⇔P(3)结合律：(P∧Q)∧R⇔P∧(Q∧R)，(P∨Q)∨R⇔P∨(Q∨R)(4)交换律：P∧Q⇔Q∧P，P∨Q⇔Q∨P(5)分配律：P∧(Q∨R)⇔(P∧Q)∨(P∧R)，P∨(Q∧R)⇔(P∨Q)∧(P∨R)(6)德·摩根律：⌝ (P∧Q) ⌝⇔P∨⌝Q，⌝ (P∨Q) ⌝⇔P∧⌝Q(7)吸收律：P∧(P∨Q)⇔P，P∨(P∧Q)⇔P(8)同一律：P∧T⇔P，P∨F⇔P(9)零律：P∧F⇔F，P∨T⇔T(10)否定律：P∧⌝P⇔F，P∨⌝P⇔T(11) 条件式转化律：P→Q⌝⇔P∨Q，P→Q⌝⇔Q→⌝P(12) 双条件式转化律：P↔Q ⇔(P→Q)∧(Q→P) ⇔(P∧Q)∨(⌝P∧⌝Q)⌝ (P↔Q) ⇔P⌝↔Q ⌝⇔P↔Q(13) 输出律(CP规则)：P→(Q→R) ⇔(P∧Q)→R重点：等价式的证明、基本等价式1.5 重言式与蕴含式重言式或永真公式定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为真，则称该命题公式为重言式或永真公式。
