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

从命题逻辑到谓词逻辑

命题逻辑研究的基本元素是命题。命题是有真假意义的一句话，而对这句话的结构和成分是不考虑的。 因此，用这样简单的手段，很多思维过程不能在命题逻辑中表达出来。

例如，逻辑学中著名的三段论：

凡人必死

张三是人

张三必死

在命题逻辑中就无法表示这种推理过程。

因为，如果用P代表 “凡人必死”这个命题，Q代表 “张三是人”这个命题，R代表 “张三必死”这个命题，则按照三段论，R应该是P和Q的逻辑结果。但是，在命题逻辑中，R却不是P和Q的逻辑结果，因为公式

P∧Q→R
显然不是恒真的，解释{P，Q，¬R}就能弄假上面的公式。
发生这种情况的原因是：命题逻辑中描述出来的三段论，即PÙQ®R，使R成为一个与P，Q无关的独立命题。因此，取解释时，可将P，Q取真，R取假，从而弄假公式P∧Q→R。 但是，实际上命题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”，于是，Gx，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，如果公式G↔H是恒真的。

由定义显然可以看出：公式G，H等价的充要条件是：对G，H的任意解释I，G，H在I下的真值相同。

因为对任意公式G，H，在解释I下，G，H就是两个命题，所以命题逻辑中给出的10组基本等价式，在谓词逻辑中仍然成立。

定义3.3.2 设G，H是公式，称G蕴涵H，或H是G的逻辑结果，如果公式G→H是恒真的，并记以G⇒H。

显然，对任意两个公式G，H，G蕴涵H的充要条件是：对任意解释I，若I满足G，则I必满足H。

同样，命题逻辑中的14 组基本蕴涵式仍成立。

现在，我们再回到三段论上来。

令G1 =∀x(H(x)→M(x))

G2=H(a)

H=M(a)

我们将证明：H是G1∨G2的逻辑结果。

因为，设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）：A©⇒∃yA(y)

这个规则是说，如果个体域中某一元素c具有性质A，则个体域中存在着具有性质A的元素。这里要求y不在A©中出现。

令G1 =∀x(H(x)→M(x))

G2=H(a)

H=M(a)

我们将证明：H是G1∨G2的逻辑结果。 应为G1∧G2
------------------------------------------------------

引理1 设G是公式，其中自由变量有且仅有一个x，记以G(x)，H是不含变量x的公式，于是有：
1) ∀x(G(x)∨H)=∀xG(x)∨H
1’∃x(G(x)∨H)=∃xG(x)∨H
2) ∀x(G(x)∧H)=∀xG(x)∧H
2’∃x(G(x)∧H)=∃xG(x)∧H
3) ¬(∀xG(x))=∃x(¬G(x))
4) ¬(∃xG(x))=∀x(¬G(x))

引理2 设G，H是两个公式，其中自由变量有且只有一个x，分别记以G(x)，H(x)，于是有：
1) ∀xG(x)∧∀xH(x)=∀x(G(x)∧H(x))
2) ∃xG(x)∨∃xH(x)=∃x(G(x)∨H(x))
3)∀xG(x)∨∀xH(x)=∀x∀y(G(x)∨H(y))
4)∃xG(x)∧∃xH(x)=∃x∃y(G(x) ∧H(y))