高级数理逻辑第2讲.doc

高级数理逻辑是计算机科学和数学的一个重要分支，它研究如何用形式化的语言来表示和推理命题。在第二讲中，我们聚焦于命题逻辑及其形式系统，也被称为命题逻辑形式系统（FSPC）。这个系统是由一系列规则和符号构成，用于分析和验证命题的真值变化。 命题是逻辑推理的基础，它是一个可以被判断为真或假的陈述。原子命题是最基本的命题，不包含任何联结词。联结词如非（~）、与（∧）、或（∨）、蕴含（→）和等价（↔）则用来组合或连接不同的命题，形成更复杂的表达式。布尔代数，由布尔创立，将这些逻辑概念转化为代数运算，使得我们可以对命题进行数学分析。 真值表是研究命题逻辑的重要工具，它展示了命题的所有可能的真值组合以及这些组合如何影响复合命题的真值。例如，蕴含关系A→B的真值表表明，只有当A为真且B为假时，A→B才为假，其他情况下均为真。这包括A为假时，无论B为何值，A→B都为真。同理，A↔B表示A与B同时为真或同时为假，也就是A与B的真值相同。 命题变元是具有真值0或1的变量，它们代表可变的命题状态。赋值映射是将命题变元映射到真值集合{0,1}的函数。永真式（Tautology）是不论如何赋值，其结果始终为真的公式，比如A→A。矛盾式则是无论怎样赋值，结果始终为假的公式。两个公式等价意味着它们在所有可能的赋值下具有相同的真值，比如(A→(B→C))→((A→B)→(A→C))始终为真。 命题逻辑的主要特点是它从语义角度探讨命题的真值变化，通过真值表可以确定任何公式的全部可能真值情况。此外，永真式可以通过逻辑推理规则，如三段论，产生新的永真式。这里提出了一个寻找永真式最小集合的问题，答案是肯定的，这意味着存在一组基础的永真式，通过逻辑操作可以生成所有其他永真式。 形式系统FSPC，如Whitehead和Russell的《数学原理》中所介绍的，定义了一套严谨的符号集和规则，包括命题变元、联结词、括号等，以及对这些符号的处理规则，如逻辑推理规则。在这个系统中，可以推导和验证命题的有效性，进一步理解逻辑的结构和性质。 高级数理逻辑的第二讲主要涉及命题逻辑的形式化表示，包括命题、联结词、真值表、命题变元、赋值映射、永真式和矛盾式，以及形式系统FSPC的定义。这些概念和工具是理解和研究逻辑推理、证明以及计算机科学中的算法和数据结构的基础。