离散数学复习提纲(代数系统)

WORD格式

专业资料整理

《离散数学》期末复习大纲

一、 数理逻辑

[复习知识点]

1、命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价 ?），复合命题

2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），

公式的基本等值式

3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式

4、公式类型的判别方法（真值表法、等值演算法、主析取 /合取范式法）

5、命题逻辑的推理理论

6、谓词、量词、个体词（一阶逻辑 3要素）、个体域、变元（约束出现与自由出

现）

7、命题符号化、谓词公式赋值与解释，谓词公式的类型（永真、永假、可满足）

8、谓词公式的等值式（代换实例、消去量词、量词否定和量词辖域收与扩、量

词分配）和置换规则（置换规则、换名规则）

9、一阶逻辑前束范式（定义、求法）

本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、

公式类型的判定、命题逻辑的推理、谓词与量词、命题符号化、谓词公式赋值与

解释、求前束范式。

[复习要求]

1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方

法。

2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简

其它公式，公式在解释下的真值。

3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）

范式的概念；掌握用基本等值式或真值表将公式化为主析取 （合取）范式的方法。

4、掌握利用真值表、等值演算法和主析取 /合取范式的唯一性判别公式类型和公

式等价方法。

5、掌握命题逻辑的推理理论。

6、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑

1 WORD格式

专业资料整理

联结词描述一个简单命题；掌握命题的符号化。

7、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定

解释下真值的方法；了解谓词公式的类型。

。

-可编辑修改- 总结 离散数学知识点

第二章 命题逻辑

1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假；

2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积；

3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反；

4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假；

5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写；

6.真值表中值为1的项为极小项，值为0的项为极大项；

7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取；

8.永真式没有主合取范式，永假式没有主析取范式；

9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假)

10.命题逻辑的推理演算方法：P规则，T规则

①真值表法；②直接证法；③归谬法；④附加前提法；

第三章 谓词逻辑

1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质；

多元谓词：谓词有n个个体，多元谓词描述个体之间的关系；

2.全称量词用蕴含→，存在量词用合取^; 。

-可编辑修改- 3.既有存在又有全称量词时，先消存在量词，再消全称量词；

第四章 集合

1.N，表示自然数集，1,2,3……，不包括0；

2.基：集合A中不同元素的个数，|A|；

3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)；

4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2；

5.集合的分划：(等价关系)

①每一个分划都是由集合A的几个子集构成的集合；

②这几个子集相交为空，相并为全(A)；

6.集合的分划与覆盖的比较：

分划：每个元素均应出现且仅出现一次在子集中；

覆盖：只要求每个元素都出现，没有要求只出现一次；

高三离散数学知识点汇总

离散数学是计算机科学、信息技术以及其他相关领域中的重要基础学科，是高中阶段的数学课程之一。下面将对高三离散数学的主要知识点进行汇总，以帮助学生更好地复习和掌握这门学科。

一、命题逻辑

命题逻辑是离散数学的基础，它研究命题的逻辑关系及其合成。以下是命题逻辑中常见的知识点：

1. 命题与命题的合取（与）、析取（或）、非（非）运算；

2. 命题的真值表与真值；

3. 命题的等价、蕴含、互斥等逻辑关系；

4. 命题的可满足性与有效性。

二、集合与关系

集合论是离散数学中的另一重要组成部分，它研究集合及其间的关系。以下是集合与关系中的主要知识点：

1. 集合的表示方式与基本操作，如并集、交集、差集和补集；

2. 笛卡尔积与关系的定义； 3. 关系的性质，如自反性、对称性、传递性等；

4. 等价关系与偏序关系的概念与判断；

5. 关系的闭包与传递闭包。

三、图论

图论是离散数学中的重要分支，它研究图及其相关的性质与算法。以下是图论中的常见知识点：

1. 图的基本概念与表示方式，如顶点、边、度、路径等；

2. 树与森林的定义与性质，包括最小生成树与最短路径树等；

3. 图的连通性与强连通性的判定；

4. 图的着色与平面图的概念；

5. 图的网络流与匹配等问题。

四、代数系统

代数系统是离散数学的重要组成部分，它研究运算规则及其相应的结构。以下是代数系统中的主要知识点：

1. 半群、幺半群、群的概念与性质；

2. 环、域的定义与性质； 3. 线性方程组与矩阵的基本运算；

4. 同余与剩余类的概念与应用。

五、概率与统计

概率与统计是离散数学的重要应用领域，它研究随机事件及其规律性。以下是概率与统计中的常见知识点：

1. 随机事件的基本概念与性质；

2. 概率的计算方法，包括古典概型、几何概型、条件概率等；

3. 随机变量与概率分布的概念与应用；

4. 抽样与统计推断，包括参数估计与假设检验等。

离散数学知识点整理

离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、数理逻辑等领域都有着广泛的应用。下面就来对离散数学的一些重要知识点进行整理。

一、集合论

集合是离散数学中最基本的概念之一。集合是由一些确定的、彼此不同的对象所组成的整体。

集合的表示方法有列举法和描述法。列举法就是将集合中的元素一一列举出来，用花括号括起来。描述法是通过描述元素所具有的性质来确定集合。

集合之间的关系包括子集、真子集、相等。如果集合 A 的所有元素都属于集合 B，那么 A 是 B 的子集；如果 A 是 B 的子集且 A 不等于 B，那么 A 是 B 的真子集；如果集合 A 和集合 B 的元素完全相同，那么 A

和 B 相等。

集合的运算有并集、交集、差集和补集。并集是将两个集合中的所有元素合并在一起组成的新集合；交集是两个集合中共同的元素组成的新集合；差集是从一个集合中去掉另一个集合中的元素所得到的新集合；补集是在给定的全集 U 中，去掉集合 A 中的元素所得到的新集合。 二、关系

关系是集合论中的一个重要概念，它描述了两个集合元素之间的某种联系。

关系可以用关系矩阵和关系图来表示。关系矩阵是一个二维矩阵，用于表示两个有限集合之间的关系；关系图则是用顶点和边来表示关系。

关系的性质包括自反性、反自反性、对称性、反对称性和传递性。自反性是指集合中的每个元素都与自身有关系；反自反性则是集合中的每个元素都与自身没有关系；对称性是如果 a 与 b 有关系，那么 b

与 a 也有关系；反对称性是如果 a 与 b 有关系且 b 与 a 有关系，那么 a

等于 b；传递性是如果 a 与 b 有关系，b 与 c 有关系，那么 a 与 c 有关系。

等价关系是一种具有自反性、对称性和传递性的关系，它可以将集合划分为等价类。偏序关系是一种具有自反性、反对称性和传递性的关系，它可以引出偏序集的概念。

三、函数

函数是一种特殊的关系，它对于定义域中的每个元素，在值域中都有唯一的元素与之对应。