合式公式-Basic-上海交通大学

合式公式Basic上海交通大学一、合式公式的定义与基本规则合式公式，又称为良构公式，是逻辑学中用于表示命题的一种形式化语言。在合式公式中，我们使用符号、运算符和括号等元素来构建逻辑表达式，以表达命题之间的逻辑关系。为了确保公式的正确性和可读性，合式公式需要遵循一系列基本规则。1.基本符号：合式公式的基本符号包括命题变元（如p、q、r等）、逻辑常量（如真值常量T、F）、逻辑运算符（如非运算¬、合取运算∧、析取运算∨、蕴涵运算→、等价运算↔等）以及括号。2.命题变元：命题变元代表一个具体的命题，如“今天下雨”可以表示为p。命题变元必须以小写字母开头，后可跟数字、下标等。3.逻辑常量：逻辑常量包括真值常量T（表示真）和F（表示假）。4.逻辑运算符：逻辑运算符用于连接命题变元和逻辑常量，形成更复杂的逻辑表达式。常见的逻辑运算符包括：（1）非运算（¬）：表示命题的否定，如¬p表示“今天不下雨”。（2）合取运算（∧）：表示命题之间的逻辑与关系，如p∧q表示“今天下雨且今天晴天”。（3）析取运算（∨）：表示命题之间的逻辑或关系，如p∨q表示“今天下雨或今天晴天”。（4）蕴涵运算（→）：表示命题之间的逻辑蕴涵关系，如p→q表示“如果今天下雨，那么今天晴天”。（5）等价运算（↔）：表示命题之间的逻辑等价关系，如p↔q表示“今天下雨当且仅当今天晴天”。5.括号：括号用于改变运算符的优先级，确保公式的正确性。如（p∧q）→r表示“如果今天下雨且今天晴天，那么明天会下雨”。二、合式公式的构造方法1.单个命题变元或逻辑常量是合式公式。2.如果A是合式公式，那么¬A也是合式公式。3.如果A和B是合式公式，那么（A∧B）、（A∨B）、（A→B）、（A↔B）也是合式公式。三、合式公式的性质1.合式公式的真值：合式公式的真值取决于其构成命题的真值。我们可以通过真值表来展示合式公式在所有可能的命题组合下的真值。2.合式公式的类型：根据逻辑运算符的不同，合式公式可以分为原子公式、复合公式和分子公式。原子公式是只包含命题变元或逻辑常量的公式，复合公式是由逻辑运算符连接的公式，分子公式是包含括号的复合公式。3.合式公式的长度：合式公式的长度是指公式中符号的数量，包括命题变元、逻辑常量、逻辑运算符和括号。合式公式的长度与其复杂度有关，长度越长，公式越复杂。4.合式公式的深度：合式公式的深度是指公式中括号的最大嵌套层数。深度越大的公式，其逻辑结构越复杂。四、合式公式的等价变换1.双重否定律：¬(¬A)等价于A。2.交换律：A∧B等价于B∧A，A∨B等价于B∨A。3.结合律：A∧(B∧C)等价于(A∧B)∧C，A∨(B∨C)等价于(A∨B)∨C。4.分配律：A∧(B∨C)等价于(A∧B)∨(A∧C)，A∨(B∧C)等价于(A∨B)∧(A∨C)。5.吸收律：A∧(A∨B)等价于A，A∨(A∧B)等价于A。6.德摩根定律：¬(A∧B)等价于¬A∨¬B，¬(A∨B)等价于¬A∧¬B。通过应用等价变换规则，我们可以将复杂的合式公式简化为更易理解和推理的形式。在后续章节中，我们将进一步探讨合式公式的推理方法，包括命题逻辑中的推理规则和证明方法。五、合式公式的推理方法1.假言推理（ModusPonens）：如果已知A→B（A蕴涵B）和A（A为真），则可以推出B（B为真）。2.否定后件推理（ModusTollens）：如果已知A→B（A蕴涵B）和¬B（B为假），则可以推出¬A（A为假）。3.析取三段论（DisjunctiveSyllogism）：如果已知A∨B（A或B）和¬A（A为假），则可以推出B（B为真）；同理，如果已知A∨B和¬B，则可以推出A。4.合取引入（ConjunctionIntroduction）：如果已知A和B，则可以推出A∧B。5.合取消除（ConjunctionElimination）：如果已知A∧B，则可以推出A和B。6.析取引入（DisjunctionIntroduction）：如果已知A，则可以推出A∨B；同理，如果已知B，则可以推出A∨B。7.析取消除（DisjunctionElimination）：如果已知A∨B和(A→C)∧(B→C)，则可以推出C。通过这些推理规则，我们可以从已知的前提中推导出新的结论。在实际应用中，这些规则通常与真值表和等价变换结合使用，以证明某个结论的有效性或推导出新的命题。六、合式公