离散数学.pdf

### 离散数学知识点概览 #### 一、数理逻辑 数理逻辑是离散数学中的一个重要分支，主要研究逻辑推理的形式化系统。它包括了命题逻辑和一阶逻辑两大部分。 ##### 1.1 命题逻辑 **命题逻辑**是基于简单命题及其组合的研究，通过逻辑联结词将这些简单命题连接起来形成更复杂的命题。 - **命题符号化** - **简单命题**：是指一个简单的陈述句，可以直接判断真假。 - **复合命题**：由简单命题通过逻辑联结词（否定词┑、合取词∧、析取词∨、蕴含词→、等值词↔）组合而成。 - **条件命题**（P→Q）：如果P为真，则Q也必须为真。 - **双条件命题**（P↔Q）：P和Q同时为真或同时为假。 - **合式公式** - 定义了一个形式语言的基本元素（∑）和构建规则，确保所形成的公式是有意义的。 - 合式公式的构成： - **命题常元或命题变元**本身就是一个合式公式。 - 如果A和B都是合式公式，则通过逻辑联结词构建的新公式也是合式公式。 - 合式公式只能通过有限次使用这些规则构建出来。 - **代入和替换** - 替换可以在公式中的某些特定位置进行，不必对所有出现的子公式进行替换。 - **永真公式** - **解释**：对于含有n个命题变元的合式公式A，对A的所有命题变元赋予一个真值，称为对A的一个解释。 - 根据不同解释下公式的真值，可以将合式公式分为三类： - **永真式**：在所有可能的解释下都为真的公式。 - **永假式**：在所有可能的解释下都为假的公式。 - **可满足式**：至少存在一个解释使得公式为真的公式。 - **逻辑恒等式** - **范式** - **文字**：可以是命题变元或者命题变元的否定。 - **合取范式**与**析取范式**是命题逻辑中常用的表达方式。 - **合取范式**：基本和的合取。 - **析取范式**：基本积的析取。 - 主合取范式和主析取范式则是特殊的合取范式和析取范式，它们包含了所有的文字组合。 - **推理理论** - 推理规则：如附加规则、化简规则、MP规则等。 - **证明方法**：包括前件假证明法、后件真证明法、直接证明法、间接证明法等。 - 公理系统的组成部分： - **初始符号**：未经定义而直接使用的符号。 - **形成规则**：确定哪些符号串是合式公式。 - **公理集**：未经证明而认为是恒真的命题。 - **推理规则**：如何从已知的合式公式推导出新的合式公式。 - **联结词的全功能集** - **全功能集**：能够表示所有可能的命题逻辑运算的一组联结词。 - **极小全功能集**：如果去掉任何一个联结词就不再是全功能集，那么这个集合就是极小全功能集。 ##### 1.2 一阶逻辑 **一阶逻辑**进一步扩展了命题逻辑的概念，引入了个体、谓词、量词等概念，从而能够表达更加复杂的逻辑关系。 - **命题符号化** - 在一阶逻辑中，个体、个体词、函数符号、谓词符号等都是基本的构成元素。 - **个体**：指的是所讨论的对象。 - **个体词**：用来表示个体的符号，包括个体常元和个体变元。 - **函数符号**：表示个体之间的函数关系。 - **谓词符号**：表示个体的属性或个体之间的关系。 - **量词**：包括全称量词∀和存在量词∃，用于限定谓词的应用范围。 - **合式公式** - 在一阶逻辑中，构建合式公式的规则更加复杂，包括项的定义、谓词的应用以及量词的使用等。 - **项**：可以是个体常元、个体变元或由函数符号与项组成的复合结构。 通过以上概述可以看出，数理逻辑不仅涵盖了命题逻辑的基础概念和方法，还深入探讨了一阶逻辑中更为复杂的逻辑结构和推理机制。这些理论为后续学习计算机科学、数学以及其他相关领域的知识提供了坚实的逻辑基础。