命题逻辑与合式公式：从永真式到范式

"这篇文档主要讨论了离散数学中的数理逻辑概念，特别是关于命题逻辑、合式公式、永真公式以及范式的内容。" 在数理逻辑中，命题逻辑是基础，它涉及到如何用符号表示和操作逻辑命题。简单命题是直接陈述的事实，而复合命题是由简单命题通过否定词┑、合取词∧（与）、析取词∨（或）、蕴含词→（蕴含）和等值词↔（等价）连接而成的。例如，P→Q 表示条件命题“如果P，则Q”，而P↔Q表示双条件命题“P当且仅当Q”。 合式公式是命题逻辑中的一个重要概念，它定义了一组规则来构建有效的命题表达式。合式公式可以通过递归地应用基础规则（如命题常元或变元、否定、合取、析取等）来构建。代入和替换允许我们在合式公式中修改特定子公式，但需注意只替换某些特定的出现，而不是全部。 永真公式是指在所有可能的解释下都为真的合式公式。解释是为合式公式中的每个命题变元赋予真值（0或1）的过程，一个合式公式如果在所有解释下都为真，那么它就是一个永真式。逻辑恒等式和永真蕴含式是永真公式的特殊情况，前者是无论怎样赋值都为真的公式，后者表示不论P的真值如何，Q总是为真的。 范式是将合式公式转换为特定形式的过程，有助于简化逻辑推理。例如，前束范式是量词只出现在公式开头的特殊形式，便于分析量词的作用范围。Skolem范式则进一步处理存在量词，确保不存在未定义的函数。 推理理论探讨了如何根据一系列推理规则从已知的前提中推出新结论。这些规则包括附加规则、化简规则、模态逻辑中的三段论等。证明方法包括直接证明、间接证明、反证法等，这些方法用于展示一个命题的正确性或错误性。 公理系统是逻辑推理的基础，通常包括初始的假设（公理）、推导规则以及证明的准则。这些组件一起构成了证明一个命题有效性的框架。 这个文档深入介绍了离散数学中的命题逻辑和相关的逻辑概念，这些知识对于理解计算机科学中的算法和数据结构，以及形式验证等领域至关重要。