从命题逻辑到谓词逻辑.doc

从命题逻辑到谓词逻辑命题逻辑研究的基本元素是命题。命题是有真假意义的一句话，而对这句话的结构和成分是不考虑的。 因此，用这样简单的手段，很多思维过程不能在命题逻辑中表达出来。 例如，逻辑学中著名的三段论： 凡人必死 张三是人 张三必死 在命题逻辑中就无法表示这种推理过程。 因为，如果用P代表 “凡人必死”这个命题，Q代表 “张三是人”这个命题，R代表 “张三必死”这个命题，则按照三段论，R应该是P和Q的逻辑结果。但是，在命题逻辑中，R却不是P和Q的逻辑结果，因为公式 PQR 显然不是恒真的，解释P，Q，R就能弄假上面的公式。 发生这种情况的原因是：命题逻辑中描述出来的三段论，即PQR，使R成为一个与P，Q无关的独立命题。因此，取解释时，可将P，Q取真，R取假，从而弄假公式PQR。 但是，实际上命题R是和命题P，Q有关系的，只是这种关系在命题逻辑中无法表示。因此，对命题的成分、结构和命题间的共同特性等需要做进一步的分析，这正是谓词逻辑所要研究的问题。为了表示出这三个命题的内在关系，我们需要引进谓词的概念。在谓词演算中，可将命题分解为谓词与个体两部分。例如，在前面的例子“张三是人”中的“是人”是谓语，称为谓词，“张三”是主语，称为个体。 定义3.1.1 可以独立存在的物体称为个体。（它可以是抽象的，也可以是具体的。） 如人、学生、桌子、自然数等都可以做个体。在谓词演算中，个体通常在一个命题里表示思维对象。 定义3.1.2 设D是非空个体名称集合，定义在Dn上取值于1，0上的n元函数，称为n元命题函数或n元谓词。其中Dn表示集合D的n次笛卡尔乘积。 一般地，一元谓词描述个体的性质，二元或多元谓词描述两个或多个个体间的关系。0元谓词中无个体，理解为就是命题，这样，谓词逻辑包括命题逻辑。 下面我们举一个谓词的例子： 令G(x，y)： “x高于y”，于是，G(x，y)是一个二元谓词。将x代以个体 “张三”，y代以个体 “李四”，则G(张三，李四)就是命题： “张三高于李四”。随便将x，y代以确定的个体，由G(x，y)都能得到一个命题。但是，G(x，y)不是命题，而是一个命题函数即谓词。 于是，用谓词的概念可将三段论做如下的符号化： 令 H(x)表示 “x是人”， M(x)表示 “x必死”。 则三段论的三个命题表示如下： P： H(x)M(x) Q： H(张三) R： M(张三) 那么，在命题逻辑的基础上，仅仅引进谓词的概念是否就可以了呢?下面的例子说明，仅有谓词还是不够的。例如我们想得到 “命题”P的否定 “命题”，应该就是“命题”P。但是， P=(H(x)M(x) =(H(x)M(x) =H(x)M(x) 亦即，“命题”P的否定 “命题”是 “所有人都不死”。这和人们日常对命题 “所有人都必死”的否定的理解，相差得实在太远了。 其原因在于，命题P的确切意思应该是： “对任意x，如果x是人，则x必死”。 但是 H(x)M(x) 中并没有确切的表示出 “对任意x”这个意思，亦即H(x)M(x)不是一个命题。 因此，在谓词逻辑中除引进谓词外，还需要引进 “对任意x”这个语句，及其对偶的语句 “存在一个x”。 定义3.1.3 语句 “对任意x”称为全称量词，记以x； 语句 “存在一个x”称为存在量词，记以x。 这时，命题P就可确切地符号化如下： x(H(x)M(x) 命题P的否定命题为： P=(x(H(x)M(x) = x(H(x)M(x) 亦即 “有一个人是不死的”。这个命题确实是 “所有人都要死”的否定。 P=(H(x)M(x) =(H(x)M(x) =H(x)M(x) 应为H(x)M(x) P=(x(H(x)M(x) = x(H(x)M(x) 应为= x(H(x)M(x) - 解释 由于公式是由常量符号，变量符号，函数符号，谓词符号通过逻辑联结词和量词(当然还有括号)连结起来的抽象符号串，所以若不对它们(常量符号，变量符号，函数符号，谓词符号)给以具体解释，则公式是没有实在意思的。所谓给公式以解释，就是将公式中的常量符号指为常量，函数符号指为函数，谓词符号指为谓词。 定义3.2.4 谓词逻辑中公式G的一个解释I，是由非空区域D和对G中常量符号，函数符号，谓词符号以下列规则进行的一组指定组成： 1. 对每个常量符号，指定D中一个元素； 2. 对每个n元函数符号，指定一个函数，即指定Dn到D的一个映射； 3. 对每个n元谓词符号，指定一个谓词，即指定Dn到0，1的一个映射。 定义3.2.5 公式G称为可满足的，如果存在解释I，使G在I下取1值，简称I满足G。若I不满足G，则简称I弄假G。 定义3.2.6 公式G称为是恒假的(或不可满足的)，如果不存在解释I满足G；公式G称为恒真的，如果G的所有解释I都满足G。 定义3.3.1 公式G，H称为等价，记以G=H，如果公式GH是恒真的。 由定义显然可以看出：公式G，H等价的充要条件是：对G，H的任意解释I，G，H在I下的真值相同。 因为对任意公式G，H，在解释I下，G，H就是两个命题，所以命题逻辑中给出的10组基本等价式，在谓词逻辑中仍然成立。 定义3.3.2 设G，H是公式，称G蕴涵H，或H是G的逻辑结果，如果公式GH是恒真的，并记以GH。 显然，对任意两个公式G，H，G蕴涵H的充要条件是：对任意解释I，若I满足G，则I必满足H。 同样，命题逻辑中的14 组基本蕴涵式仍成立。 现在，我们再回到三段论上来。 令G1 =x(H(x)M(x) G2=H(a) H=M(a) 我们将证明：H是G1G2的逻辑结果。 因为，设I是G1 ，G2，H的一个解释(I指定a为张三)，且I满足G1 G2，即I满足 x(H(x)M(x)H(a) 所以，I满足M(a)。 由于集合D可以是无穷集合，而集合D的 “数目”也可能是无穷多个，因此，所谓公式的 “所有”解释，实际上是无法考虑的。这就使得谓词逻辑中公式的恒真，恒假性的判断变得异常困难。1936年Church和Turing分别独立地证明了：对于谓词逻辑，判定问题是不可解的 谓词演算的推理理论 利用命题公式间的各种等价和蕴涵关系，通过一些推理规则，从已知的命题公式推出另一些新的命题公式。这是命题演算中的推理。类似地，利用谓词公式间的各种等价和蕴涵关系，通过一些推理规则，从一些已知的谓词公式推出另一些新的谓词公式，这是谓词演算中的推理。在谓词演算中，要进行正确的推理，也必须构造一个结构严谨的形式证明，因此也要求给出一些相应的推理规则。下面我们就介绍这些规则，对于命题逻辑公式也可以应用相应的规则进行演算。 （1）前提引入规则：在证明的任何步骤上都可以引用前提。 （2）结论引入规则：在证明的任何步骤上所得到的结论都可以在其后的证明中引用。 （3）置换规则：在证明的任何步骤上，公式的子公式都可以用与之等价的其他公式置换。 （4）代入规则：在证明的任何步骤上，恒真公式中的任一原子都可以用一公式代入，得到的仍是恒真的公式。 （5）全称特定化规则（US）：xA(x) A(y) 这里的A(y)是将A(x)中的x处处代以y。要求y在A(x)中不约束出现。这里自由变量y也可以写成个体常量c，这时c为个体域中任意一个确定的个体。 这个规则的意思是说，如果个体域的所有元素都具有性质A，则个体域中的任一个元素具有性质A。 （6）存在特定化规则（ES）：xA(x) A 这里c是个体域中的某个确定的个体。这个规则是说，如果个体域中存在有性质A的元素，则个体域中必有某一元素c具有性质A。但是，如果xA(x)中有其它自由变量出现，且x是随其它自由变量的值而变，那么就不存在唯一的c使得A对自由变量的任意值都是成立的。这时，就不能应用存在特定化规则。 例如，x（x=y）中，x、y的论域是实数集合。若使用ES规则，则得c=y，即在实数集中有一实数c，等于任意实数y。结论显然不成立，这是因为A(x)：x=y中的x依赖于自由变量y，此时不能使用ES规则。另外，要注意的是，如果xP(x)和xQ(x)都真，则对于某个c和某个d，可以断定 P Q(d)必真，但不能断定P Q为真。 （7）全称一般化规则（UG）：A(x)yA(y) 这个规则是说，如果个体域中任意一个个体都具有性质A，则个体域中的全体个体都具有性质A。这里要求x必须为自由变量，并且y不出现在A(x)中。 （8）存在一般化规则（EG）：AyA(y) 这个规则是说，如果个体域中某一元素c具有性质A，则个体域中存在着具有性质A的元素。这里要求y不在A中出现。令G1 =x(H(x)M(x) G2=H(a) H=M(a) 我们将证明：H是G1G2的逻辑结果。 应为G1G2 - 引理1 设G是公式，其中自由变量有且仅有一个x，记以G(x)，H是不含变量x的公式，于是有： 1) x(G(x)H)=xG(x)H 1x(G(x)H)=xG(x)H 2) x(G(x)H)=xG(x)H 2x(G