离散数学11教学课件

离散数学11集合论基础图论基础命题逻辑初步谓词逻辑初步代数系统简介目录CONTENTS01集合论基础集合是具有某种特定性质的事物的总体，事物称为集合的元素。集合的概念常用大写字母表示集合，如A、B、C等；用花括号{}括起来的元素列表表示集合，如{1,2,3}；用描述法表示集合，如{x|x是自然数，且x<10}。集合的表示法集合及其表示法集合间关系与运算集合间关系包括相等关系、包含关系、真包含关系等。如A=B表示集合A与B相等；A⊆B表示集合A包含于集合B；A⊂B表示集合A真包含于集合B。集合运算包括并集、交集、差集、补集等。如A∪B表示集合A与B的并集；A∩B表示集合A与B的交集；A-B表示集合A与B的差集；A'表示集合A的补集。幂集对于任意集合A，以A为元素构成的所有子集（包括空集和A本身）所组成的集合称为A的幂集，记作P(A)。例如，对于集合{1,2}，其幂集为{{},{1},{2},{1,2}}。笛卡尔积设A和B为任意两个集合，则所有有序对(a,b)的集合，其中a属于A且b属于B，称为A与B的笛卡尔积，记作A×B。例如，对于集合A={1,2}和B={a,b}，其笛卡尔积为{(1,a),(1,b),(2,a),(2,b)}。幂集与笛卡尔积02图论基础图的定义无向图与有向图顶点的度连通性图的基本概念与性质由顶点集和边集构成的数据结构，表示对象及其之间的关系。与顶点相关联的边的数目，对于有向图分为入度和出度。根据边的方向性分类，无向图中的边没有方向，有向图中的边有方向。任意两个顶点之间都存在路径，则称图是连通的。表示顶点间关系的矩阵，元素值为1表示存在边，为0表示不存在边。邻接矩阵表示顶点和边之间关系的矩阵，元素值为1表示顶点与边相关联，为0表示不相关联。关联矩阵表示任意两顶点间是否存在路径的矩阵，通过邻接矩阵的幂运算求得。可达性矩阵图的矩阵表示法树的性质及应用连通且无环的无向图称为树。具有n个顶点的树有n-1条边，且任意两顶点间存在唯一路径。连通图的极小连通子图，包含图中的所有顶点且边数最少。带权连通图中权值和最小的生成树，常用算法有Prim算法和Kruskal算法。树的定义树的性质生成树最小生成树03命题逻辑初步命题01具有明确真假的陈述句，例如“今天是晴天”或“2+2=5”。联结词02用来连接两个或多个命题的词，如“且（∧）”、“或（∨）”、“非（¬）”、“如果...则...（→）”等。复合命题03由联结词连接的命题构成的命题，例如“(今天是晴天∧温度高于30℃)”。命题与联结词123列出命题中所有可能真值组合及其对应结果的表格。通过真值表可以判断复合命题的真假。真值表通过一系列等值式（如德摩根律、吸收律等）将命题化简或转换为其他形式的过程。等值演算在命题逻辑中，两个命题如果对所有可能的真值组合都有相同的真值，则称这两个命题是等值的。等值式真值表与等值演算析取范式（CNF）与析取范式（DNF）将命题转换为由析取或合取连接的简单命题的形式。CNF是合取范式，DNF是析取范式。推理规则在命题逻辑中，用于从已知命题推导出新命题的规则，如假言推理、拒取式、析取三段论等。重言式与矛盾式重言式是在所有可能真值组合下都为真的命题；矛盾式是在所有可能真值组合下都为假的命题。范式与推理规则04谓词逻辑初步谓词用于描述对象性质或对象间关系的词，通常表示为P(x)、Q(x,y)等。谓词可以带有一个或多个参数，用于表示不同的对象。量词用于限定谓词作用范围的词，包括全称量词“∀”和存在量词“∃”。全称量词表示对论域中所有对象都成立，存在量词表示对论域中至少一个对象成立。谓词与量词谓词公式的解释与分类谓词公式中的每个谓词和量词都需要赋予具体的含义，即解释。解释可以是具体的数学结构、物理现象等。解释根据谓词公式中量词的种类和位置，可以将谓词公式分为四类：全称命题、存在命题、特称命题和混合命题。分类VS在谓词逻辑中，推理规则用于从已知的前提推导出新的结论。常见的推理规则有假言推理、拒取式推理、析取三段论等。推理步骤使用推理规则进行推理时，需要遵循一定的步骤。首先，列出已知的前提；其次，根据推理规则选择合适的推导方式；最后，得出新的结论。推理规则谓词逻辑的推理规则05代数系统简介封闭性结合律交换律分配律二元运算及其性质指二元运算满足结合律，即改变运算元素的组合方式不改变运算结果。指二元运算满足交换律，即改变运算元素的顺序不改变运算结果。指二元运算满足分配律，即一个元素与一组元素的运算结果等于该元素与这组元素中每个元素进行运算后再求和（或求积）。指运算结果仍在代数系统中，即对于任意两个元素，经过二元运算后得到的结果也属于该系统。等价关系在代数系统中，若两个元素经过一系列二元运算后得到的结果相等，则称这两个元素等价。同态与同构若两个代数系统之间存在一个保持运算的映射，则称这两个代数系统同态；若该映射为双射，则称这两个代数系统同构。代数系统由非空集合和定义在该集合上的若干个二元运算所组成的系统。代数系统基本概念群由非空集合和定义在该集合上的一个二元运算所组成的代数系统，满足封闭性、结合律、存在单位元和存在逆元。域是一种特殊的环，其中非零元素对乘法也构成群，即满足乘法交换律和乘法逆元存在性。格由非空集合和定义在该集合上的两个二元运算（通常称为交和并）所组成