高等数学-第十七章数理逻辑

第十七章数理逻辑

第十七章数理逻辑17.1

命题与联结词

17.2

公式的相等与蕴涵

17.3

谓词与量词2.1命题以及逻辑联结词

2.1.1命题

所谓命题是指一句有真假意义的话。例如：上海是中国最大的城市 今天是星期二 所有素数都是奇数 1+1=2命题用大写英文字母P，Q，…，P1，P2，…，表示。

如果一个命题是真的，就说它的真值是1；

如果一个命题是假的，就说它的真值是0。

也用“1”代表一个抽象的真命题，用“0”代表一个抽象的假命题。

定义2.1.1设P是一个命题，命题“P是不对的”称为P的否定，记以

P，读作非P。

P是真的当且仅当P是假的。例如：

P：吉大是中国最大的大学。

P：吉大不是中国最大的大学。定义2.1.2设P，Q是两个命题，命题“P或者Q”称为P，Q的析取，记以P

Q，读作P或Q。规定P

Q是真的当且仅当P，Q中至少有一个是真的。例如：

P：今天下雨，Q：今天刮风， P

Q：今天下雨或者刮风。定义2.1.3设P，Q是两个命题，命题“P并且Q”称为P，Q的合取，记以P

Q，读作P且Q。规定P

Q是真的当且仅当P和Q都是真的。例如，P：2

2=5，Q：雪是黑的，

P

Q：2

2=5并且雪是黑的。

定义2.1.4设P，Q是两个命题，命题“如果P，则Q”称为P蕴涵Q，记以P

Q。规定，P

Q是假的当且仅当P是真的而Q是假的。例如，P：f(x)是可微的，Q：f(x)是连续的，

P

Q：若f(x)是可微的，则f(x)是连续的。由定义知，如果P是假命题，则不管Q是什么命题，命题“如果P，则Q”在命题逻辑中都被认为是真命题。例如，P：2

2=5，Q：雪是黑的，

于是，命题“如果2

2=5，则雪是黑的”是真命题。定义2.1.5设P，Q是两个命题，命题“P当且仅当Q”称为P等价Q，记以P

Q。规定，P

Q是真的当且仅当P，Q或者都是真的，或者都是假的。例如， P：a2+b2=a2，

Q：b=0，

P

Q：a2+b2=a2当且仅当b=0。例2.1.1

如果你走路时看书，那么你会成为近视眼。令P：你走路；Q：你看书；R：你会成为近视眼。于是，上述语句可表示为（P

Q）

R。

例2.1.2

除非他以书面或口头的方式正式通知我，否则我不参加明天的会议。

令P：他书面通知我；Q：他口头通知我；R：我参加明天的会议。

于是，上述语句可表示为(P

Q)

R。

例2.1.3

设P，Q，R的意义如下：

P：苹果是甜的；Q：苹果是红的；

R：我买苹果。

试用日常语言复述下述复合命题：

(1)(P

Q)

R (2)(

P

Q)

R解：(1)如果苹果甜且红，那么我买。(2)我没买苹果，因为苹果不甜也不红。2.2命题公式

§2.2.1公式我们用大写的英文字母P，Q，R，…等代表一个抽象的命题，或称为命题符号。定义2.2.1命题符号称为原子。例如，Q，S，…等都是原子。定义2.2.2

命题公式命题逻辑中的公式，是如下定义的一个符号串： (1) 原子是公式；

(2) 0、1是公式；

(3) 若G，H是公式，则(

G)，(G

H)， (G

H)，(G

H)，(G

H)是公式； (4) 所有公式都是有限次使用(1)，(2)，(3)

得到的符号串。规定：公式(

G)的括号可以省略，写成

G。整个公式的最外层括号可以省略。五种逻辑联结词的优先级按如下次序递增：

，

，

，

，

例如，我们写符号串

P

Q

R

Q

S

R

就意味着是如下公式： ((P

(Q

R))

(Q

((

S)

R)))§2.2.2解释

定义2.2.3设G是命题公式，A1,…,An是出现在G中的所有原子。指定A1,…,An的一组真值，则这组真值称为G的一个解释。设G是公式，I是G的一个解释，显然，G在I下有真值，通常记为TI(G)。

例

G=P

Q，设解释I，I’如下：

I： I’：

则TI(G)=1，TI’(G)=0PQ

11

PQ

10

定义2.2.4公式G在其所有可能的解释下所取真值的表，称为G的真值表。显然，有n个不同原子的公式，共有2n个解释。

例：G=(P

Q)

R，其真值表如下：

PQRG00010011010101111001101111001111

若公式G中出现的所有原子为A1，…，An，有时我们用{m1，…，mn}表示G的一个解释I，其中

例如，上例公式G的真值表中第二个解释就可以记为{

P，

Q，R}定义2.2.5公式G称为恒真的(或有效的)，如果G在它的所有解释下都是真的；

公式G称为恒假的(或不可满足的)，如果G在它的所有解释下都是假的；公式G称为可满足的，如果它不是恒假的。考虑G1=

(P→Q)→P，G2=(P→Q)P，G3=P

P。从真值表可以看出G1对所有解释具有“真”值，公式G3对所有解释具有“假”值，而G2具有“真”和“假”值。PQG1PQG2PG30010000001101110101100111111G是恒真的当且仅当

G是恒假的。G是可满足的当且仅当至少有一个解释I，使G在I下为真。若G是恒真的，则G是可满足的；反之不对。如果公式G在解释I下是真的，则称I满足G；

如果G在解释I下是假的，则称I弄假G。在逻辑研究和计算机推理以及决策判断中，人们对于所研究的命题，最关心的莫过于“真”、“假”问题，所以恒真公式在数理逻辑研究中占有特殊且重要的地位。判定问题能否给出一个可行方法，对任意的公式，判定其是否是恒真公式。因为一个命题公式的解释的数目是有穷的，所以命题逻辑的判定问题是可解的(可判定的，可计算的)，亦即，命题公式的恒真，恒假性是可判定的。§2.3 命题公式的等价关系

和蕴涵关系

§2.3.1公式的等价定义2.3.1公式G，H说是等价的，记以G=H，如果G，H在其任意解释I下，其真值相同。显然，公式G，H等价的充要条件是公式G

H是恒真的。基本等价式1) (G

H)=(G

H)

(H

G)；2) (G

H)=(

G

H)；3) G

G=G，G

G=G； (等幂律)4)

G

H=H

G，G

H=H

G； (交换律)5)

G

(H

S)=(G

H)

S，

G

(H

S)=(G

H)

S； (结合律)基本等价式6) G

(G

H)=G，G

(G

H)=G； (吸收律)7)

G

(H

S)=(G

H)

(G

S)，

G

(H

S)=(G

H)

(G

S)； (分配律)8)

G

0=G，G

1=G； (同一律)9)

G

0=0，G

1=1； (零一律)10)

(G

H)=

G

H，

(G

H)=

G

H。 (摩根律)从上述众多的等价公式可以看出，每一个命题公式的表达式是不唯一的，这种不唯一性使得人们在进行逻辑推理时可以有千变万化的方式，即对于一个公式G，可根据如上等价公式，在等价的意义下，对其进行推演，从而得到G的各种等价形式。经验表明，自觉的使用逻辑规律和不自觉的使用是完全不一样的，熟悉这些规律可以使我们的思维正确而敏锐。定义2.3.2完备集设Q是逻辑运算符号集合，若所有逻辑运算都能由Q中元素表示出来，而Q的任意真子集无此性质，则称Q是一个完备集。可以证明，{

，

}，{

，

}都是完备集。

定义2.3.3与非式设P，Q是两个命题，命题“P与Q的否定”称为P与Q的与非式，记作P

Q。“”称作与非联结词。P

Q为真当且仅当P，Q不同时为真。由定义可知：

P

Q=

(P

Q)。

定义2.3.4或非式设P，Q是两个命题，命题“P或Q的否定”称为P与Q的或非式，记作P

Q，

称作或非联结词。P

Q为真当且仅当P，Q同时为假。由定义可知：

P

Q=

(P

Q){

}是完备集下面我们来说明{

}是完备集。

P=P

PP

Q=(P

P)

(Q

Q)P

Q=(P

Q)

(P

Q)读者可以自己证明{

}也是完备集。

§2.3.2公式的蕴涵

逻辑的一个重要功能是研究推理。固然，依靠等价关系可以进行推理。但是，进行推理时，不必一定要依靠等价关系，只需是蕴涵关系就可以了。例如，若三角形等腰，则两底角相等，

这个三角形等腰，

所以，这个三角形两底角相等。又如，若行列式两行成比例，则行列式值为0，

这个行列式两行成比例，

所以，这个行列式值为0。上面两个例子的推理关系涵义不同，但依据的推理规则相同，推理形式为：

若P则Q，P，所以Q。

推理的正确性与命题P，Q涵义无关，只决定于逻辑形式，命题逻辑中用公式表示命题，命题间演绎推理关系，反映为公式间逻辑蕴涵关系。定义2.3.5蕴涵设G，H是两个公式。称H是G的逻辑结果(或称G蕴涵H)，当且仅当对G，H的任意解释I，如果I满足G，则I也满足H，记作G

H。注意：符号“”和“=”一样，它们都不是逻辑联结词，因此，G=H，G

H也都不是公式。

是一种部分序关系。公式G蕴涵公式H的充要条件是：公式G

H是恒真的。例如：(P

Q)

P，(P

Q)

Q定义2.3.6设G1,…,Gn，H是公式。称H是G1,…,Gn的逻辑结果(或称G1,…,Gn共同蕴涵H)，当且仅当公式G1

…

Gn蕴涵H。显然，公式H是G1,…,Gn的逻辑结果的充要条件是：公式((G1

…

Gn)

H)是恒真的。例如，P，P

Q共同蕴涵Q。

定理2.3.1如果H1，…，Hm，P共同蕴涵公式Q，则H1，…，Hm共同蕴涵公式P

Q。例如，因为公式P

Q，Q

R，P共同蕴涵R，所以P

Q，Q

R共同蕴涵P

R。

定理2.3.1证明：因为(H1

…

Hm

P)

Q，所以公式(H1

…

Hm

P)

Q是恒真的。利用下面的基本等价公式：

P1

(P2

P3)=(P1

P2)

P3于是，(H1

…

Hm

P)

Q=(H1

…

Hm)

(P

Q)。故(H1

…

Hm)

(P

Q)是恒真的。所以H1，…，Hm共同蕴涵P

Q。§2.3.3演绎

定义2.3.7设S是一个命题公式的集合(前提集合)。从S推出公式G的一个演绎是公式的一个有限序列：

G1,G2,…,Gk

其中，Gi或者属于S，或者是某些

Gj(j<i)的逻辑结果。

并且

Gk就是G。我们称公式G为此演绎的逻辑结果，或称从S演绎出G。

有时也记为S

G。

例设S={P

Q，Q

R，P

M，

M}则下面的公式序列:

M，P

M，

P，P

Q，Q，Q

R，R

就是从S推出R的一个演绎。引理设G，H1，H2是公式。如果G蕴涵H1，G蕴涵H2，则G蕴涵H1

H2。证明：任取G，H1，H2的一个解释I。

若I满足G，由假设知，I满足

H1，I满足H2，故I满足

H1

H2。由I的任意性，所以G

(H1

H2)。

定理2.3.2设S是公式集合，G是一个公式。于是，从S演绎出G的充要条件是G是S的逻辑结果。证明：必要性，设从S演绎出G，令

G1，…，Gk

是这个演绎。对任意Gi(i=1，…，k)，往证Gi

是S的逻辑结果。对i用归纳法:(1)当i=1时，因G1

S，显然,G1

…

G1

是恒真公式，故S

G1

，即

G1

是S的逻辑结果。

(2)设i<n时，命题成立。(3)当i=n时，若Gn

S，则S

Gn，归纳法完成。若Gn是某些Gj(j<n)的逻辑结果，不妨设

(Gj1

…

Gjh)

Gn

(1)

其中j1，…，jh都小于n。

由归纳假设知，S

Gjm，m=1，…，h。由引理知：S

(Gji

…

Gjh)(2)

根据(1)，(2)式及蕴涵关系的传递性，得

S

Gn

即Gn是S的逻辑结果，归纳完成。

充分性，若G是S的逻辑结果，由演绎的定义知，G是如下演绎：

G1，…，Gk，G的逻辑结果，其中

G1

，…，Gk

是S中所有公式。

定理2.3.3设S是前提公式集合，G，H是两个公式。如果从S∪{G}可演绎出H，则从S可演绎出G

H。证明：因为从S∪{G}可演绎出H，由定理2.3.2知，H是S∪{G}的逻辑结果。亦即

(G1

…

Gk

G)

H

其中G1，…，Gk

是S中所有公式。

由定理2.3.1知：

(G1

…

Gk)

(G

H)

即G

H是S的逻辑结果，再由定理2.3.2知，从S可演绎出G

H。

基本蕴涵式

P

Q

PP

Q

QP

P

QQ

P

Q

P

(P

Q)Q

(P

Q)

(P

Q)

P基本蕴涵式

(P

Q)

QP，Q

P

Q

P，P

Q

QP，P

Q

Q

Q，P

Q

PP

Q，Q

R

P

RP

Q，P

R，Q

R

R§2.3.4公式蕴涵的证明方法真值表法；证G

H是恒真公式；利用一些基本等价式及蕴涵式进行推导；任取解释I，若I满足G，往证I满足H；反证法，设结论假，往证前提假。§2.3.4公式蕴涵的证明方法若给出前提集合S={G1，…，Gk}，公式G，证明S

G有如下两种方法：

1.G1

…

Gk

G

2.形式演绎法形式演绎法根据一些基本等价式和基本蕴涵式，从S出发，演绎出G，在演绎过程中遵循以下三条规则：规则1.可随便使用前提。(根据演绎定义)规则2.可随便使用前面演绎出的某些公式的逻辑结果。(根据演绎的定义)规则3.

如果需要演绎出的公式是P

Q的形式，则我们可将P做为附加前提使用，而力图去演绎出Q。(根据定理2.3.3)。

例2.3.1证明{(P

Q)，(P

R)，(Q

S)}

S

R

P

Q 规则1

P

Q 规则2，根据1 Q

S 规则1

P

S 规则2，根据2，3

S

P 规则2，根据4 P

R 规则1

S

R 规则2，根据5，6 S

R 规则2，根据7。

例2.3.2证明{P

(Q

S)，

R

P，Q}

R

S

R

P 规则1 R 规则3 P 规则2，根据1，2 P

(Q

S) 规则1 Q

S 规则2，根据3，4 Q 规则1 S 规则2，根据5，6 R

S 规则3，根据2，7例2.3.3若厂方拒绝增加工资，则罢工不会停止，除非罢工超过一年并且工厂经理辞职。问：如果厂方拒绝增加工资，而罢工又刚刚开始，罢工是否能停止?令 P：厂方拒绝增加工资；

Q：罢工停止；

R：工厂经理辞职；

S：

罢工超过一年。

于是， G1：(P

(R

S))

Q G2：P G3：

S H：

Q我们要证明：H是{G1，G2，G3}的逻辑结果。1.

S 规则12.

S

R 规则2，根据13.

(R

S) 规则2，根据24.

P 规则15.

P

(R

S) 规则2，根据3，46.(P

(R

S))

Q 规则17.

Q 规则2，根据5，6亦即，罢工不会停止。第三节谓词逻辑§3.1 谓词逻辑的基本概念§3.2 谓词公式§3.3 谓词公式的等价关系和蕴含关系

§3.4 范式

§3.5 例

§3.6 谓词逻辑的应用§3.1谓词逻辑的基本概念§3.1.1谓词和量词例如，逻辑学中著名的三段论：

凡人必死

张三是人

张三必死

在命题逻辑中就无法表示这种推理过程。§3.1.1谓词和量词因为，如果用P代表“凡人必死”这个命题，Q代表“张三是人”这个命题，R代表“张三必死”这个命题，则按照三段论，R应该是P和Q的逻辑结果。但是，在命题逻辑中，R却不是P和Q的逻辑结果，因为公式

P

Q

R

显然不是恒真的，解释{P，Q，

R}就能弄假上面的公式。

§3.1.1谓词和量词定义3.1.1

可以独立存在的物体称为个体。（它可以是抽象的，也可以是具体的。）如人、学生、桌子、自然数等都可以做个体。在谓词演算中，个体通常在一个命题里表示思维对象。§3.1.1谓词和量词定义3.1.2

设D是非空个体名称集合，定义在Dn上取值于{1，0}上的n元函数，称为n元命题函数或n元谓词。其中Dn表示集合D的n次笛卡尔乘积。一般地，一元谓词描述个体的性质，二元或多元谓词描述两个或多个个体间的关系。0元谓词中无个体，理解为就是命题，这样，谓词逻辑包括命题逻辑。§3.1.1谓词和量词下面我们举一个谓词的例子：

令G(x，y)：“x高于y”，于是，G(x，y)是一个二元谓词。将x代以个体“张三”，y代以个体“李四”，则G(张三，李四)就是命题：“张三高于李四”。随便将x，y代以确定的个体，由G(x，y)都能得到一个命题。但是，G(x，y)不是命题，而是一个命题函数即谓词。§3.1.1谓词和量词于是，用谓词的概念可将三段论做如下的符号化：令

H(x)表示“x是人”，

M(x)表示“x必死”。则三段论的三个命题表示如下：

P：H(x)

M(x)

Q：H(张三)

R：M(张三)§3.1.1谓词和量词例如我们想得到“命题”P的否定“命题”，应该就是“命题”

P。但是，

P=

(H(x)

M(x))

=

(

H(x)

M(x))

=H(x)

M(x)亦即，“命题”P的否定“命题”是“所有人都不死”。这和人们日常对命题“所有人都必死”的否定的理解，相差得实在太远了。

§3.1.1谓词和量词其原因在于，命题P的确切意思应该是：“对任意x，如果x是人，则x必死”。但是

H(x)

M(x)

中并没有确切的表示出“对任意x”这个意思，亦即H(x)

M(x)不是一个命题。因此，在谓词逻辑中除引进谓词外，还需要引进“对任意x”这个语句，及其对偶的语句“存在一个x”。

§3.1.1谓词和量词定义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))

亦即“有一个人是不死的”。这个命题确实是“所有人都要死”的否定。

§3.1.1谓词和量词三段论的三个命题，在谓词逻辑中是如下这样表示的：

P：

x(H(x)

M(x))

Q：H(张三)

R：M(张三)以后可以证明：在谓词逻辑中，R是P和Q的逻辑结果。

§3.1.1谓词和量词设G(x)是一元谓词，任取x0

D，则G(x0)是一个命题。于是

xG(x)是这样一个命题“对任意x

D，都有G(x)”。故对命题

xG(x)的真值做如下规定：

xG(x)取1值

对任意x

D，G(x)都取1值；

xG(x)取0值

有一个x0

D，使G(x0)取0值。§3.1.1谓词和量词

xG(x)是命题“存在一个x0

D，使得G(x0)成立”。对命题

xG(x)的真值规定如下：

xG(x)取1值

有一个x0

D，使G(x0)取1值；

xG(x)取0值

对所有x

D，G(x)都取0值。

§3.1.1谓词和量词当D={x0

，x1，…}是可数集合时，

xG(x)等价于G(x1)

G(x2)

…

xG(x)等价于G(x1)

G(x2)

…§3.1.1谓词和量词对于一个谓词，如果其中每一个变量都在一个量词作用之下。则它就不再是命题函数，而是一个命题了。但是，这种命题和命题逻辑中的命题毕竟有所不同。因为终归这种命题里还有变量，当然这种变量和命题函数中的变量还有区别。使用量词时应注意以下几个问题：

1.量词的论域，即D中都有那些元素；

2.在多重量词时，应注意量词的顺序；

3.量词的作用域。§3.1.2改名规则

定义3.1.4

在一个由谓词，量词，逻辑联结词，括号组成的有意义的符号串(实际是指下一节将严格定义的公式)中，变量的出现说是约束的，当且仅当它出现在使用这个变量的量词范围之内；变量的出现说是自由的，当且仅当这个出现不是约束的。例如，

x(P(x，y)

Q(x，z))

R(x)。从左向右算起，变量x的第一，第二次出现是约束的，第三次出现是自由的；变量y，z的出现是自由的。

§3.1.2改名规则

定义3.1.5

变量说是约束的，如果至少一个它的出现是约束的；变量说是自由的，如果至少一个它的出现是自由的。由定义可以看出一个变量可以既是约束变量又是自由变量。例如，上例中的x既是约束变量，又是自由变量；y，z只是自由变量。

§3.1.2改名规则

显然，

xG(x)与

yG(y)的真值一样，

xG(x)与

yG(y)的真值一样，亦即，谓词逻辑中的命题的真值，与命题中的约束变量的记法无关。这就引出了谓词逻辑中的改名规则。

§3.1.2改名规则

在由谓词，量词，逻辑联结词，括号组成的有意义的符号串(实际是下节定义的公式)中，我们可将其中出现的约束变量改为另一个约束变量，这种改名必须在量词作用区域内各处以及该量词符号中实行，并且改成的新约束变量要有别于改名区域中的所有其它变量。显然改名规则不改变原符号串的真值。

例:对于

x(P(x，y)

Q(x，z))，可改名为

u(P(u，y)

Q(u，z))。但下面的改名都是不对的：

a.

u(P(u，y)

Q(x，z))

b.

x(P(u，y)

Q(u，z))

c.

u(P(x，y)

Q(x，z))

d.

y(P(y，y)

Q(y，z))

e.

z(P(z，y)

Q(z，z))§3.2谓词公式

§3.2.1公式

在形式化中，我们将使用如下四种符号：1.

常量符号：用小写英文字母a，b，c，…表示，当个体名称集合D给出时，它可以是D中某个元素。2.

变量符号：用小写英文字母x，y，z，…表示，当个体名称集合D给出时，D中任意元素可代入变量符号。§3.2.1公式

3.

函数符号：用小写英文字母f，g，…表示，当个体名称集合D给出时，n元函数符号f(x1，…，xn)可以是Dn到D的任意一个映射。4.

谓词符号：用大写英文字母P，Q，R，…表示，当个体名称集合D给出时，n元谓词符号P(x1，…，xn)可以是Dn上的任意一个谓词。

定义3.2.1项谓词逻辑中的项，被递归定义为：1)

常量符号是项；2)

变量符号是项；3)

若f(x1,…,xn)是n元函数符号，t1,…,tn

是项，则f(t1,…,tn)是项；4)

所有项都是有限次使用1)，2)，3)生成

的符号串。

定义3.2.2若P(x1,…,xn)是n元谓词符号，t1,…,tn是项，则P(t1,…,tn)是原子。

定义3.2.3公式

谓词逻辑中的公式，被递归定义如下：1)

原子是公式；2)

若G，H是公式，则(

G)，(G

H)，(G

H)，

(G

H)，(G

H)是公式；3)

若G是公式，x是G中的自由变量，则

xG，

xG是公式；4)

所有公式都是有限次使用1)～3)生成的符号

串。

§3.2.2解释

定义3.2.4

谓词逻辑中公式G的一个解释I，是由非空区域D和对G中常量符号，函数符号，谓词符号以下列规则进行的一组指定组成：1.

对每个常量符号，指定D中一个元素；2.

对每个n元函数符号，指定一个函数，即指

定Dn到D的一个映射；3.

对每个n元谓词符号，指定一个谓词，即指

定Dn到{0，1}的一个映射。

§3.2.2解释

今后我们对讨论的公式做如下规定：公式中无自由变量，或将自由变量看做常量。

例:给出如下两个公式：

1)G=

x(P(f(x))

Q(x，f(a)))

2)H=

x(P(x)

Q(x，a))给出如下的解释I：

D={2，3}

a

2

f(2)f(3)

32

P(2)P(3)Q(2,2)Q(2,3)Q(3,2)Q(3,3)

011101例:TI(G) =TI((P(f(2))

Q(2，f(2)))

(P(f(3))

Q(3，f(2))))

=TI((P(3)

Q(2，3))

(P(2)

Q(3，3)))

=(1

1)

(0

0)

=1TI(H) =TI(P(2)

Q(2，2)

P(3)

Q(3，2))

=0

1

1

0

=0定义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谓词公式的等价关系和蕴含关系

§3.3.1公式的等价和蕴涵

定义3.3.1

公式G，H称为等价，记以G=H，如果公式G

H是恒真的。由定义显然可以看出：公式G，H等价的充要条件是：对G，H的任意解释I，G，H在I下的真值相同。因为对任意公式G，H，在解释I下，G，H就是两个命题，所以命题逻辑中给出的基本等价式，在谓词逻辑中仍然成立。

§3.3.1公式的等价和蕴涵

定义3.3.2

设G，H是公式，称G蕴涵H，或H是G的逻辑结果，如果公式G

H是恒真的，并记以G

H。显然，对任意两个公式G，H，G蕴涵H的充要条件是：对任意解释I，若I满足G，则I必满足H。同样，命题逻辑中的基本蕴涵式仍成立。

§3.3.1公式的等价和蕴涵

令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)。否则，令M(a)在I下为假，而H(a)在I下为真，于是H(a)

M(a)在I下为假，故

x(H(x)

M(x))在I下为假，矛盾!

故M(a)在I下为真命题，而I指定a为“张三”，故M(张三)为真命题。§3.3.1公式的等价和蕴涵

由于谓词逻辑中的恒真(恒假)公式，要求所有解释I都满足(弄假)该公式。而解释I依赖于一个非空集合D。由于集合D可以是无穷集合，而集合D的“数目”也可能是无穷多个，因此，所谓公式的“所有”解释，实际上是无法考虑的。这就使得谓词逻辑中公式的恒真，恒假性的判断变得异常困难。1936年Church和Turing分别独立地证明了：对于谓词逻辑，判定问题是不可解的。

设G(x)是一元谓词符号，若公式

xG(x)是恒真公式，则这件事实可被叙述为如下的一个真命题：对任意一元谓词G(x)，命题

xG(x)都是真的。但是，如果想把这个命题加以否定，则在谓词逻辑中是办不到的。因为：1)这个命题的否定，应该是如下命题：有一个一元谓词G(x)，使得命题

xG(x)是假的。2)公式

xG(x)的否定是公式

(

xG(x))。而后一个公式表示的命题是：公式

xG(x)是恒假的，亦即，对任意一元谓词G(x)，命题

xG(x)都是假的。

1)和2)所表示出的事实相差得太远了。发生这件事的原因是：用“公式

xG(x)是恒真的”来表达命题“对任意一元谓词G(x)，命题

xG(x)都是真的”是不确切的。确切地，后一个命题，应该用“公式

G(

xG(x))是恒真的”来表达。

这个公式中，不仅有关于个体变量x的量词，而且有关于谓词变量(即谓词符号，亦即原子)的量词。由这样的公式组成的系统就称为高阶逻辑。高阶逻辑中，不仅判定问题不可解，甚至连一个完备的公理系统都没有。§3.3.2谓词演算的推理理论前提引入规则：在证明的任何步骤上都可以引用前提。结论引入规则：在证明的任何步骤上所得到的结论都可以在其后的证明中引用。置换规则：在证明的任何步骤上，公式的子公式都可以用与之等价的其他公式置换。代入规则：在证明的任何步骤上，恒真公式中的任一原子都可以用一公式代入，得到的仍是恒真的公式。全称特定化规则(US)：

xA(x)

A(y)

这里的A(y)是将A(x)中的x处代以y。要求y在A(x)中不约束出现。这里自由变量y也可以写成个体常量c，这时c为个体域中任意一个确定的个体。

这个规则的意思是说，如果个体域的所有元素都具有性质A，则个体域中的任一个元素具有性质A。

存在特定化规则(ES)：

xA(x)

A(c)

存在特定化规则(ES)：

xA(x)

A(c)

这里c是个体域中的某个确定的个体。这个规则是说，如果个体域中存在有性质A的元素，则个体域中必有某一元素c具有性质A。

但是，如果

xA(x)中有其它自由变量出现，且x是随其它自由变量的值而变，那么就不存在唯一的c使得A(c)对自由变量的任意值都是成立的。这时，就不能应用存在特定化规则。

例如，

x(x=y)中，x、y的论域是实数集合。若使用ES规则，则得c=y，即在实数集中有一实数c，等于任意实数y。结论显然不成立，这是因为A(x)：x=y中的x依赖于自由变量y，此时不能使用ES规则。另外，要注意的是，如果

xP(x)和

xQ(x)都真，则对于某个c和某个d，可以断定

P(c)

Q(d)必真，但不能断定P(c)

Q(c)为真。

全称一般化规则(UG)：A(x)

yA(y)

这个规则是说，如果个体域中任意一个个体都具有性质A，则个体域中的全体个体都具有性质A。这里要求x必须为自由变量，并且y不出现在A(x)中。存在一般化规则(EG)：A(c)

yA(y)

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

证明： （1）

x(P(x)

Q(x))

前提 （2）P(c)

Q(c) (1)；US

（3）P(c)

前提 （4）Q(c) (2),(3)

例3.3.1

证明:

x(P(x)

Q(x))

P(c)

Q(c)证明：用反证法，假设

xQ(x)成立。

x

P(x)

前提

P(y) (1)；US

xQ(x)

假设

x

Q(x) (3)

Q(y) (4)；US

P(y)

Q(y) (2)，(5)

例3.3.2证明：

x(P(x)

Q(x)),

x

P(x)

xQ(x)

(P(y)

Q(y)) (6)

x(P(x)

Q(x))

前提

P(y)

Q(y) (8),US (P(y)

Q(y))

(P(y)

Q(y)) (7),(9)

因为(P(y)

Q(y))

(P(y)

Q(y))是恒假公式，所以

x(P(x)

Q(x))，

x

P(x)

xQ(x)。

（1）

x(F(x)

G(x))

前提（2）F(c)

G(c) （1），ES（3）F(c) （2）（4）

y(H(y)

I(y))

前提（5）H(c)

I(c) （4）（6）H(c) （5）（7）F(c)

H(c)

（3）,（6）（8）

x(F(x)

H(x))

（7），EG。

例3.3.3指出下面推理中的错误。

§3.4范式定义3.4.1

谓词逻辑中公式G称为前束范式，如果G有如下形状：

Q1x1…QnxnM

其中

Qixi或者是

xi，或者是

xi，i=1，…，n，M是不含量词的公式，Q1x1…Qnxn称为首标，M称为母式。例如，

x

y

z(P(x，y)

Q(x，z))

x

y

zP(x，y，z)§3.4.1前束范式

设G是公式，其中自由变量有且仅有一个x，记以G(x)，H是不含变量x的公式，于是有：1)

x(G(x)

H)=

xG(x)

H1’)

x(G(x)

H)=

xG(x)

H2)

x(G(x)

H)=

xG(x)

H2’)

x(G(x)

H)=

xG(x)

H3)

(

xG(x))=

x(

G(x))4)

(

xG(x))=

x(

G(x))引理1

1)

设I是G(x)和H的一个解释。若

x(G(x)

H)在I下取1值，则在I下，对任意x

D，G(x)

H都是真命题。若H是真命题，则

xG(x)

H是真命题；若H是假命题，则必然是对每个x

D，G(x)都是真命题，故

xG(x)取1值。所以

xG(x)

H在I下取1值。若

x(G(x)

H)在I下取0值，则必有一个x0

D，使G(x0)

H在I下取0值。故G(x0)为假命题，并且H为假命题。所以

xG(x)取0值。从而

xG(x)

H在I下取0值。

证明：

（1）‘的证明设I是G(x)和H的一个解释。若

x(G(x)

H)在I下取1值，则在I下，存在x0

D，G(x0)

H是真命题。若H是真命题，则

xG(x)

H是真命题；若H是假命题，则必然有G(x0)是真命题，故

xG(x)取1值。所以

xG(x)

H在I下取1值。若

x(G(x)

H)在I下取0值，则在I下对任意的x

D，使G(x)

H在I下取0值。故G(x)和H都为假命题，所以

xG(x)

H在I下取0值。（3）的证明若I满足

(

xG(x))，则I弄假

xG(x)。则必有某一个x0

D，G(x0)

是假命题，于是

G(x0)

是真命题，即

x(

G(x))在I下是真命题，故I满足

x(

G(x))若I弄假

(

xG(x))，则I满足

xG(x)。即对任意的x

D，有G(x)是真命题。也就是对任意的x

D，

G(x)是假命题，于是

x(

G(x))是假命题，故I弄假

x(

G(x))。若I满足

(

xG(x))，则I弄假

xG(x)。故对任意x

D，G(x)都是假命题，从而

G(x)都是真命题，故I满足

x(

G(x))若I弄假

(

xG(x))，则I满足

xG(x)。故有x0

D，使得G(x0)是真命题。从而

G(x0)是假命题，故I弄假

x(

G(x))。证明：

设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))引理2设I是G(x)和H(x)的一个解释。若

xG(x)

xH(x)在I下取1值，则在解释I下，对任意x

D，G(x)、H(x)都是真命题，所以G(x)

H(x)是真命题，即对任意x

D，G(x)

H(x)是真命题，所以

x(G(x)

H(x))在I下取1值。若

xG(x)

xH(x)在I下取0值，则

xG(x)为假，或

xH(x)为假，若

xG(x)为假，必有一个x0

D，使G(x0)在I下取0值，所以G(x0)

H(x0)为假命题，所以

x(G(x)

H(x))在I下取0值。若

xH(x)为假，同理可证。1)证明：

xG(x)

xH(x)

=

xG(x)

yH(y)

改名规则=

x(G(x)

yH(y))

引理1

=

x

y(G(x)

H(y))

引理13)证明：

对任意公式G，都存在与其等价的前束范式。

证明：通过如下算法，可将公式G化成等价的前束范式。1.

使用基本等价

(K

H)=(K

H)

(H

K)

(K

H)=

K

H

可将公式G中的

和

删除。定理3.4.12.

使用

(

H)=H，摩根律，引理1，可将公式中所有否定号

放在原子之前。3.

如果必要的话，则将约束变量改名。4.

使用引理1，2将所有量词都提到公式的最左边。于是，将公式G在等价意义下化成了一个前束范式。

x

y(

z(P(x,z)

P(y,z))

uQ(x,y,u))=

x

y(

(

z(P(x,z)

P(y,z)))

uQ(x,y,u))=

x

y(

z(

P(x,z)

P(y,z))

uQ(x,y,u))=

x

y

z(

P(x,z)

P(y,z)

uQ(x,y,u))=

x

y

z

u(

P(x,z)

P(y,z)

Q(x,y,u))例3.4.1定义3.4.2

设G是一个公式，Q1x1…QnxnM是与G等价的前束范式，其中M为合取范式形式。若Qr是存在量词，并且它左边没有全称量词，则取异于出现在M中所有常量符号的常量符号c，并用c代替M中所有的xr，然后在首标中删除Qrxr。§3.4.2Skolem范式

若Qs1,…,Qsm是所有出现在Qrxr左边的全称量词(m

1，1

s1<s2<…<sm<r)，则取异于出现在M中所有函数符号的m元函数符号f(xs1,…,xsm)，用f(xs1,…,xsm)