命题逻辑的公理系统-进一步的讨论1

1、仅供个人参考不得用于商业用途关于形式化的讨论第2、3章证明了每一命题形式都可以通过等值变换成各种范式用真 值表方法和范式，回答了命题逻辑中很多有重要意义的问题，如：判定任 一给定的命题形式是不是重言式 （常真的）、矛盾式（常假的）；一命题形式 是不是另一些命题形式的逻辑后承；两个任给的命题形式是否等值以及如 何判定一个推理形式是否正确，等等。但是，真值表方法有它的局限性， 它没有把所有的重言式作为一个整体来研究，而逻辑中其它更复杂的部分 也不能用真值表方法来处理。公理方法是研究命题逻辑的另外一种方法， 通公理方法建立命题逻辑的形式系统一一命题演算。公理系统从一些公理出发，应用逻辑规则，推导一系

2、列定理，这样形成的演绎 体系称为公理系统。欧氏几何就是一个著名的古典公理系统。公理系统首先包括一组特别挑选出来的命题称为公理，也叫作初始命 题。公理是不加证明而接受作为系统的出发点的。系统中其余的命题都从 公理出发经证明推导出来，称为定理。公理的选择必须满足某些一般的条 件，如公理必须明确地规定所包含的概念的意义，并且容易理解；一组公 理要能充分地刻划所研究对象的恃征；是协调的（不会导致矛盾的），等等,在现代公理系统中，选作公理的命题其真实性不一定是最明显的。公理系统包括一组不加定义的概念，称为基本概念或初始概念。其余 的概念由基本概念定义，称为派生概念。基本概念的意义由公理明确地陈 述和规定

3、。现代公理系统和古典公理系统的一个重大差别是， 对于现代公理系统， 可以有多种不同的概念都使得公理为真， 或者说可以对系统作不同的解释。 例如，等价关系理论就是现代公理系统的一个例子。仅供个人参考不得用于商业用途例 等价关系理论建立在下面三个公理的基础上( xRy 读作“ x 等价 于 y ”或“ x 与 y 等价”)。(E1) 对所有 x， xRx；(E2) 对所有x和y，如果xRy,则yRx;(E3) 对所有x, y和z,如果xRy并且yRz,则xRz。令A是一非空集合，R是A中的一个二元关系。二元组v A, R称为 一个结构。我们称 R是A中的一个等价关系，v A, R是一个等价结构如

4、果公理 (E1)-(E3) 被满足的话。 (E1)-(E3) 不是关于某一个特定的等价结构 的公理，其中的R可以作不同的解释。例如，以 S表示命题形式的集合， 把R解释为命题形式之间的等值关系“=”以自然数集合N为论域，把R 解释为自然数的相等关系“=”以整数集合Z为论域，把aRb解释为a-b 能被5整除(记为“ R5)，那么v S, =,v N,=,v Z, R5都是等 价结构。 形式系统 形式系统是完全形式化的公理系统。对公理系统的研究,可以采取两 种不同的观点：一种是把公理、定理等等看作是语句,另种足把公理理 解为由语句所表达的意义。前者是对公理系统的语法研究；后者是对公理 系统的语义研

5、究。形式系统是公理系统的语法部分,使用人工语言,用专 门的符号表示概念,把公理和定理都变换成一些符号公式,对这些具体对 象进行研究。形式系统和通常的公理系统的另一个不同之点是,普通公理 系统不把从公理推导定理 (证明定理 )所用的逻辑规律 (推理规则 )包括系 统在本身之中,对于哪些证明方法是可以使用的没有明确的规定。而在形 式系统中对此有明确的规定。一个形式系统包括三个组成部分。 第一部分是语言 (形式语言),通常 仅供个人参考不得用于商业用途是一种人工语言。语言的选择应当尽可能使得语句的结构能反映它们的意 义。建立一个语言首先是确定它的符号 （初始符号）。初始符号相当于普通 拼音文字中的字

6、母，也称为字母表。当对符号加以解释时，其中某些符号 就是公理系统的初始概念。符号的数目一般是无穷的，可以由有穷个初始 符号进行构造。符号的有穷序列 （有穷长的符号串 ） 称为表达式。某一表达式中符号的 数目（包括重复数）称为该表达式的长度。一个表达式 （ 不算单个符号自身 ） 也可能在另一表达式中出现。例如，“好读书”和“好读书不好读书”是汉语中的两个表达式，前一表达式在 后一表达式中出现两次。表达式中有一部分被专门区别开来。在有的形式 语言中，这样被区分开来的表达式包括两类，一类称为项，一类称为合式 公式。一个语言的符号和公式确定时，语言得到确定。建立一个语言就是确 定它的符号和形成规则。语

7、言是纯语法的对象。形式系统的第二个组成部分是它的公理。公理是从系统公式中挑选出 来作为推导系统中其余定理的出发点的部分公式。形式系统的第三个组成部分是推理规则，也称变形规则。推理规则用 于从公理得出定理。每一条推理规则都规定：在一定条件下，从若干称为 前提的公式能推出一个称为结论的公式。当一个推理的前提是公理或者是 已经应用推理规则从公理得出的结论，那么应用一个推理规则得出的结论 称为定理。一个形式系统的定理可以定义为：（1）一个形式系统的公理是它的定理；（2）如果所有的前提都是定理，那么应用它的一个推理规则得出的结仅供个人参考不得用于商业用途论是它的定理。并且只有根据（1）和（2）这两条能确

8、定它是定理的公式才是 系统的定理。对于一个形式系统的定理可以更清晰地描述如下：设So是系统的公理的集合，根据（1） So是能够确定为定理的公式集合。设Si是只以So中的公式作前提应用推理规则得出的结论集合，根据（2）S i是能够确定为定理的公式集合。设S2是只以Si中的公式作前提应用推理规则得出的结论集合，根据（2）S 2是能够确定为定理的公式集合。用同样的方法构造集合S3 ,S4,.令S:是以So, S, S2 中的公式作前提应用推理规则得出的结论 集合，根据（2）S ：是定理集合。用同样的方法继续构造下去，直到根据（2）再也不能得到新的定理为止。这样得到了一个形式系统的全部定理.上述方式的

9、定义称为广义归纳定义。一个归纳定义通过给出一组规则 （法则），由这些规则确定某一类对象组成的一个集合。这些规则中的第一 条规定某些对象属于该集合，其余各条都规定如果某些对象属于该集合， 那么另外的一个怎样的对象属于该集合。形式语言的（合式）公式的形成规则是一个关于合式公式的归纳定义。归纳定义具有这样的特点：要证明归纳定义所确定的某一类对象中的 每一个都有某个性质，只需证明满足定义中陈述的规则的对象都有该性质。 例如，要证明一个形式系统的每一定理都有性质P,只需要证明满足对定理的定义规则的公式都有性质P。即只需要证明：（1）形式系统的每一公理都有性质P;（2）如果一个推理规则的所有前提都有性质P

10、,结论也有性质P（推理规则保持性质P）。用这个方法所作的证明称为对于定理的归纳证明。（1）称为基始，（2仅供个人参考不得用于商业用途）称为归纳步骤。（2）中的假设：推理规则的所有前提都有性质P,称为归 纳假设。类似地，要证明每一个合式公式都有某个性质，只需对合式公式 作归纳证明。归纳证明是一个很重要应用很广的证明方法。一个形式系统由语言 （ 包括初始符号和形成规则 ） 、公理和推理规则这 样三部分组成。系统中的其它对象：合式公式 （ 或者还有项 ） 和定理都是在 系统内逐步生成的。公式由符号和形成规则生成，定理由公理和推理规则 生成。每一公式和定理都有一个生成序列，一个公式的生成序列是由有穷

11、个公式组成的，其中每一个或者是由公式形成规则直接确定为公式的，或 者从前面的公式根据形成规则形成的，最后一个是由这序列生成的公式。 公式是有穷长的符号序列，所以总能在有穷步内生成，生成序列的长度是 有穷的。定理是由公理和推理规则生成，每一推理规则的前提的数目是有 穷的。定理的生成序列称为证明，其长度也是有穷的。一个证明是一有穷长的公式序列，其中每一个公式或者是一个公理， 或者是以序列中在前的公式作前提的一个推理规则的结论。如果一个公式 A 是一个证明 P 的最后的公式，就说 P 是 A 的一个证明，并说 A 是一个定 理。一形式系统的一个公式是系统中的定理当且仅当存在它的一个证明。 每一定理都

12、有一个证明：对定理作归纳证明，一个公理自身是它的一个证 明，所以每一公理是有证明的。如果一个定理是以某些定理作前提的推理 规则的结论，根据归纳假设，这些作前提的定理都是有证明的。这样把这 些证明放在一起构成一个公式序列，把那个公式（ 定理 ） 放在这序列的最后，就得到这个公式 （ 定理 ） 的一个证明。反过来，如果一个公式是有证明 的，它是一个证明的最后的公式，根据定理和证明的定义，它就是个定 理。在一个形式系统中，对于下列各点：仅供个人参考不得用于商业用途（1）任一符号是不是一初始符号；(2) 任一有穷长的符号序列是不是合式的；(3) 任一公式是不是一个公理；(4) 任一公式是不是以给定的公

13、式作前提的某个推理规则的结论；(5) 任一有穷长的公式序列是不是一个证明，也就是说，序列中的每 一公式是不是一个公理，或者是不是以序列中在前的公式作前提的推理规 则的一个结论。都要求有一个机械的方法，能在有穷步内进行判定。在形式系统中， 上述各点都是能够判定的。一般不能机械地判定任一公式是不是一个定理。要求判定一个公式是 不是定理，需要给出它的一个证明，确定它是定理，或者证明它不是定理 即它是没有证明的，所有的证明都不是它的证明。存在机械的方法判定一 个公式是不是定理的系统 ( 理论 ) ，称为是可判定的。内容丰富的系统一般 是不可判定的。 语法和语义 形式系统是把普通公理系统形式化的结果。普

14、通的公理系统都是有解 释的理论，其中的公理、定理等等都是有意义的。一个形式系统是一个公理系统的语法部分。在把一个公理系统形式化 时，用特定的符号表示公理系统中的概念，用符号公式表示公理系统中的 命题， 而把公理系统的内容抽象。 在形式系统中， 处理的只是符号、 公式、 公式的符号组合的变换等等，完全不涉及内容和意义。推理实际上就是对 公式(符号组合 )所作的变形或符号变换。从给定的前提能不能得出某个结 论，实际上就是根据变形 (推理) 规则，从给定的公式经过符号变换能不能 仅供个人参考不得用于商业用途得出(变成) 某个公式。这种语法研究的优点是，符号、公式等等都是具体 的对象， 是完全确定的，

15、 不会引起不同理解， 不会造成歧义并且容易掌握， 能更精确地处理。而意义是抽象的，往往比较难于理解和掌握，不同的人 在理解上很容易不一致。语法研究包括可证明性、协调性等重要概念和问 题。在把一个有内容的理论形式化，建立一个形式系统时，在选择形式系 统的语言时，应尽可能使得系统的语句(公式)的结构能反映它们的意义。 经解释后某些符号就成为概念，公式成为有意义的句子。对形式系统的解 释，关于表达式的意义、表达式与它们所反映的对象之间的关系的研究， 属于语义的研究。语义研究包括真假、可满足性、意义等等概念和问题。 由语义研究建立的理论成为语义理论或者语义学.关于公理系统P合式公式的定义是一个归纳定义

16、。因此，要证明所有的公式都有某个 性质，可以对公式作归纳证明。这个证明方法称为施归纳于公式的结构， 具体地说，要证明所有公式有某个性质，只要证明以下三点：(1)所有原子公式都有这个性质；(2)对任何A,如果A有这个性质，则 - A有这个性质；(3)对任何A和B,如果A和B有这个性质，则(A、B)有这性质。P的公理和推理规则P的公理凡是有下列形式的 P的公式都是P的公理：(A1)卜 A (B A)(A2)卜(A (B C) (A B) (A C)(A3)卜(- B) ( B) A)仅供个人参考不得用于商业用途(A2)称为蕴涵词分配律，即蕴涵词对蕴涵词自身是可分配的.(A3)称为反证律，它反映通常

17、的反证法，相当于：假设 A是假的(即 假设-A)，就引出一个矛盾，即得出 B并且非B(-A蕴涵B, - A蕴涵-B),那么就可以肯定A。P的定理我们也可以用另一种方式，即用归纳定义来定义P的定理：(1)P的每一公理是P的定理；(2)如果分离规则的前提 A1, A2是定理，B是应用分离规则从 A1和 A2得出的结论，则B是定理。要证明P的所有定理有性质P，需要证明：(1)每一公理有性质P;(2)如果A1, A2有性质P，B是应用分离规则从 A1, A2得出的结论， 则B有性质P.定理P中有1卜A，A (同一律)2卜(BT C)T (AT B)T (AT C)3卜(AT B)T (BT C)T (

18、AT C)(蕴涵词传递律)4卜(AT (BT C)T (BT (AT C)证明仅供个人参考不得用于商业用途导出规则下面引进若干规则，称为导出的推理规则，简称导出规则。这些规则 从P中的公理、定理和分离规则导出。导出规则具有与分离规则同样的性 质：如果一个规则的前提是定理，那么应用规则得出的结论也是定理。应 用导出规则可以简化证明。导出规则1从卜A,可推出卜B A导出规则2从卜A (BT C)，可推出卜(AT B)T (AT C)导出规则3从卜-M- B和卜-A B,可推出卜A导出规则4从卜A B和卜B C可推出卜AC导出规则5从卜A （BT C），可推出卜B （AT C）定理P中有5卜心（AT B）T B）6卜-AA （ 双重否定律）7卜A - - A8卜（-A B厂（BA）9卜（一A，B）（一B A）10卜（AB），（-B- A）11卜（A B），（BA）12卜（ATB）T （AT B）TA）（归谬律）证明演绎定理我们将证明一个重要的语法定理一演绎定理。