命题演算与联结词：从主合取范式到主析取范式

本文档是哈工大数理逻辑课程的课件，主要讲解了命题演算的形式化系统，特别是关于联结词的扩充与归约。内容包括命题的定义、命题公式、逻辑联结词的含义、赋值计算模式、命题公式的分类、范式（主合取范式和主析取范式）以及如何从弄假指派和弄真指派构建这些范式。此外，还介绍了命题演算形式系统PC和ND的基本结构与定理，并简要提到了一阶谓词演算的相关概念。 在命题演算中，主合取范式（MCM）和主析取范式（MDN）是极为重要的概念。主合取范式是由所有使原公式为假的最小子句合取而成，而主析取范式则是由所有使原公式为真的最大子句析取而成。例如，命题1.6.3指出，通过公式的主合取范式可以直接写出公式的弄假指派。如果已知所有弄假指派，可以构建出公式的主合取范式，因为每个弄假指派对应于主合取范式中的一个合取项。同样，命题1.6.5说明了如何通过主析取范式来表示所有弄真指派。 定理1.6.2阐述了一个关键的逻辑等价性：n元命题公式的全体可以被划分为2^n个等价类，每个类内的公式逻辑等价，并且每个类都有一个共同的主合取范式或主析取范式。这意味着，对于所有具有相同真值表的公式，它们都可以用同一个主合取范式或主析取范式来表示。 联结词的扩充与归约是指在给定的命题联结词集合上增加新的联结词或者通过已有联结词表达新的逻辑功能。例如，一元命题联结词∆1到∆4展示了四种基本的逻辑操作，包括恒真（∆1和∆4）、逻辑非（∆3）和逻辑与（∆2）。通过这些基本联结词，可以构造出更复杂的逻辑表达式，实现对命题的多样化处理。 此外，文中还提及了一阶谓词演算，这是比命题演算更为强大的逻辑系统，允许使用量词（全称量词和存在量词）来表述更复杂的逻辑关系，如关系和函数。一阶逻辑的语义和推理规则在此基础上进一步扩展，使得逻辑推理能够应用于更为复杂的数学和哲学问题。 这篇课件深入浅出地讲解了逻辑系统的基础，对理解逻辑推理和证明的方法具有重要作用，是学习数理逻辑的良好教材。