高中数学 第一章 常用逻辑用语 1.1 命题及其关系 命题逻辑素材 新人教A版选修21.doc

命题逻辑命题逻辑以逻辑运算符结合原子命题来构成代表“命题”的公式，以及允许某些公式建构成“定理”的一套形式“证明规则”。（相对于谓词逻辑，它是量化的并且它的原子公式是谓词函数；和模态逻辑，它可以是非真值泛函的。）目录1简介2文法3演算4推理规则1简介演算是用来证明有效的公式（就是说它的定理）和论证（argument）的逻辑系统。它是公理或公理模式的集合（它可以为空或是可数无限集合），和推导有效的推理的推理规则。形式文法（或语法）递归定义语言的表达式和合式公式（well-formed formula 经常缩写为wff）。此外给出定义真值和求值（或释义）的语义。它允许我们确定哪个 wff 是有效的（也就是定理）。在命题演算中语言由命题变量（或者叫占位符（placeholder）和句子/判决算子（或者叫连结词）。wff 是任何原子公式或在句子操作符之上建造的公式。在下文中我们描述一种标准命题演算。很多不同的公式系统存在，它们都或多或少等价但在下列方面不同：它们的语言（就是说哪些操作符和变量是语言的一部分）； 它们有哪些（如果有的话）公理； 采用了哪些推理规则。2文法语言的构成：字母表的大写字母，表示命题变量。它们是原子公式。惯例上，使用拉丁字母（a,b,c）或希腊字母（，），但是不能混合使用。表示连结词（connective)（或逻辑算子）的符号： ¬；、?。（我们可以使用更少的算子（和相应的符号），因为一些算子是简写形式 例如，p q 等价于 ¬ p q）。左右圆括号： （，）。合式公式（wff）的集合右如下规则递归的定义：基础： 字母表的字母（通常是大写的，如a、b、 等）是 wff。归纳条款 i: 如果 是 wff，则 ¬ 是 wff。归纳条款 如果 和 是 wff，则 （ ）、（ ）、（ ） 和 （ ） 是 wff。闭包条款： 其他东西都不是 wff。重复的应用这三个公式允许生成复杂的 wff。例如：通过规则 1，a 是 wff。通过规则 2，¬ a 是 wff。通过规则 1，b 是 wff。通过规则 3，（¬ a b) 是 wff。3演算为了简单化，我们使用自然演绎系统，它没有公理；或者等价的说，它有空的公理集合。使用我们的演算的推导将用编号后的行的列表，在每行之上有一个单一的 wff 和一个理由（justification）的形式展示出来。任何前提（premise）都在上部，并带有 p 作为它们的断定。结论将在最后一行。推导将被看作完备的，条件是所有行都是通过正确的应用一个规则而从前面的行得出的。（作为一种对比的方式，参见证明树）。公理我们的公理集合是空集。4推理规则我们的命题演算有十个推理（inference）规则。这些规则允许我们从给定的一组假定为真的公式中推导出其他为真的公式。前八个简单的陈述我们可以从其他 wff 推论出（infer）特定的 wff。但是最后两个规则使用了假言(hypothetical）推理，这意味着在规则的前提中我们可以临时的假定一个（未证明的）假设（hypothesis）作为推导出的公式集合的一部分，来查看我们是否能推导出一个特定的其他公式。因为前八个规则不是这样而通常被描述为非假言规则，而最后两个就叫做假言规则。双重否定除去从 wff ¬ ¬ ，我们可以推出 。合取介入从任何 wff 和任何 wff ，我们可以推出 （ ）。合取除去从任何 wff （ ），我们可以推出 和 。析取介入从任何 wff ，我们可以推出 （ ） 和 （ ），这里的 是任何 wff。析取除去从 （ ）、（ ） 和 （ ） 形式的wff，我们可以推出 。双条件介入从 （ ） 和 （ ） 形式的 wff，我们可以推出 （ ）。双条件除去从 wff （ ），我们可以推出 （ ） 和 （ ）。肯定前件从 和 （ ） 形式的 wff，我们可以推出 。条件证明如果在假定假设 的时候可以推导出 ，我们可以推出 （ ）。反证证明如果在假定假设 的时候可以推导出 和 ¬ ，我们可以推出 ¬ 。规则的可靠性和完备性这组规则的关键特性是它们是可靠的和完备的。非形式的，这意味着规则是正确的并且不再需要其他规则。这些要求可以如下这样正式的提出。我们定义真值指派为把命题变量映射到真或假的函数。非形式的，这种真值指派可以被理解为对事件的可能状态（或可能性世界）的描述，在这里特定的陈述是真而其他为假。公式的语义因而可以被形式化，通过对它们把那些事件状态认定为真的定义。我们通过如下规则定义这种真值 a 在什么时候满足特定 wff:a 满足命题变量p当且仅当a(p) = 真a 满足 ¬ 当且仅当a 不满足 a 满足 （ ）当且仅当a 满足 与 二者a 满足 （ ）当且仅当a 满足 和 中至少一个a 满足 （ ） 当且仅当没有 a 满足 但不满足 的事例a 满足 （ ）当且仅当a 满足 与 二者，或则不满足它们中的任何一个通过这个定义，我们现在可以形式化公式 被特定公式集合 s 蕴涵的意义。非形式的，就是在使给定公式集合 s 成立的所有可能情况下公式 也成立。这导引出了下面的形式化定义： 我们说 wff 的集合 s 语义蕴涵（蕴涵：entail 或 imply）特定的 wff ，条件是满足在 s 中的公式的所有真值指派也满足 。最后我们定义语法蕴涵， 被 s 语法蕴涵，当且仅当我们可以在有限步骤内使用我们提出的上