离散数学及应用（第3版）课件第三章 谓词逻辑

第三章谓词逻辑《离散数学及应用》第三章谓词逻辑苏格拉底三段论：凡是人都是要死的。苏格拉底是人。所以苏格拉底是要死的。p∧q

r重言式？正确的推理？2第三章谓词逻辑为了克服命题逻辑的局限性，引入了谓词和量词对原子命题和命题间的相互关系做进一步的剖析，从而产生了谓词逻辑。谓词逻辑亦称一阶逻辑，它同命题逻辑一样，是数理逻辑中最基础的内容。原子命题是命题逻辑中最基本的组成单元，不能对它再作进一步的分解，但同时也无法反映出某些原子命题的共同特征和相互关系。3第三章谓词逻辑§3.1谓词与量词§3.2谓词公式及分类§3.3自然语句形式化§3.4谓词逻辑的等值演算§3.5前束范式§3.6谓词逻辑的推理4谓词与量词个体词（individual）是一个命题里表示思维对象的词，表示独立存在的具体或抽象的客体具体的、确定的个体词称为个体常项，一般用

a,b,c

表示抽象的、不确定的个体词称为个体变项，一般用

x,y,z

表示个体变项的取值范围称作个体域或论域（domainofthediscourse）宇宙间一切事物组成的个体域称作全总个体域（universaldomainofindividuals）5谓词与量词表示个体词性质或相互之间关系的词称作谓词（predicate）。6谓词与量词如果命题里只有一个个体词，这时表示该个体词性质或属性的词便称为谓词。这是一元（目）谓词，以

P(x),Q(x),…表示。例Human(Socrates)Mortal(Socrates)7谓词与量词如果在命题里的个体词多于一个，那么表示这几个个体词间的关系的词称作谓词。这是多元（目）谓词，有

n

个个体的谓词

P(x1,…,xn)称

n元（目）谓词，以

P(x,y),Q(x,y),R(x,y,z),…表示。例

Greater(x,y)Equal(x,y)Friend(俞伯牙,钟子期)8谓词与量词准确地讲，谓词

P(x),Q(x,y),…是命题形式而不是命题因为既没有指定谓词符号

P,Q

的含义，而且个体词

x,y

也是个体变项而不代表某个具体的事物，从而无法确定P(x),Q(x,y)

的真值。仅当赋予谓词确定含义，并且个体词取定为个体常项时，命题形式才化为命题。9谓词与量词世界上有黑天鹅。世界上所有天鹅都是黑色的。Black(swan)？10谓词与量词用来表示个体数量的词是量词（quantification），给谓词加上量词称作谓词的量化可看作是对个体词所加的限制、约束的词，但不是对数量一个、二个、三个…的具体描述，而是讨论两个最通用的数量限制词：11谓词与量词全称量词(universalquantification)

“

”读作“所有的x”、“任意x”或“一切x”含意相当于自然语言中的“任意的”、“所有的”、“一切的”、“每一个”、“凡”等(

x)P(x)意指对论域

D

中的所有个体都具有性质

P命题

(

x)P(x)

当且仅当对论域中的所有

x

来说，P(x)

均为真时方为真。

12谓词与量词例假设个体x的论域是全总个体域“一切事物都是运动的”可以形式描述为：(

x)(x是运动的)若以

P(x)

表示“x是运动的”，则可写作(

x)(P(x))，或简写成(

x)P(x)或

xP(x)例

凡是人都是要死的。D={所有人}

xMortal(x)13谓词与量词存在量词(existentialquantification)

“

”读作“存在x”含意相当于自然语言中的“某个”、“存在”、“有的”、“至少有一个”、“有些”等(

x)P(x)意指对论域

D

中至少有一个个体具有性质

P

14谓词与量词例假设个体x的论域是全总个体域“有的事物是水果”可以形式描述为：(

x)(x是水果)若以

Q(x)

表示“x是水果”，则可写作(

x)(Q(x))，或简写成(

x)Q(x)或

xQ(x)15谓词与量词注意：指定了论域且赋予谓词确定含义时，(

x)P(x)和(

x)P(x)都是命题。“x”不是随意可变的了类似于16

第三章谓词逻辑§3.1谓词与量词§3.2谓词公式及分类§3.3自然语句形式化§3.4谓词逻辑的等值演算§3.5前束范式§3.6谓词逻辑的推理17谓词公式及分类谓词逻辑中的谓词公式(wellformedformula，简记为wff)递归地定义为：(1)命题常项、命题变项和原子谓词公式（不含联结词的谓词）是谓词公式；(2)如果

A

是谓词公式，则

~A

也是谓词公式；(3)如果

A

和

B

是谓词公式，则由逻辑联结词联结

A

和

B

的符号串也是谓词公式，(4)若

A

是谓词公式，且

A

中无

x

及

x出现，则

(

x)A(x),

(

x)A(x)

也是谓词公式；(5)只有有限次地应用(1)-(4)构成的符号串才是谓词公式。谓词公式也称为合式公式，简称公式。18谓词公式及分类例

p,

P(x,y)∧Q(x),

x(F(x)

G(x)),

x(A(x)

yF(x,y))

x(

x(F(x))

19谓词公式及分类类似于命题逻辑中对命题公式进行的真值指派，可以对谓词逻辑公式赋予不同的解释：

20谓词公式及分类谓词公式的一个解释（interpretation）由下面4部分组成：(1)非空的论域

D；(2)D

中一部分特定元素；(3)D

上一些特定的函数；(4)D

上一些特定的谓词。21F(x)

G(x+y,2)

D

谓词公式及分类解释规定了相应的个体常项、个体变项、函数符号及谓词符号的具体意义，以及个体变项的取值范围如果两个解释的四个组成部分中至少有一部分不同，则这两个解释是不同的一个公式可以用不同的解释给定含义，一个解释可以对多个不同的公式22谓词公式及分类例

谓词公式

(

x)P(f(x),2)解释1：论域

D

是正整数集合2是一个特定的整数函数

f(x)=4x谓词

P(x,y)表示

x<y那么在解释1下该命题是假命题。23谓词公式及分类例

谓词公式

(

x)P(f(x),2)解释2：论域

D

为实数集2是一个特定的实数函数

f(x)=x2谓词

P(x,y)

表示

x=y那么在解释2下该命题是真命题。24谓词公式及分类类似于命题逻辑，也可以对谓词逻辑公式进行分类：设

A

为一个谓词公式，若

A

在任何解释下真值均为真，则称

A

为普遍有效的公式或逻辑有效式（logicallyvalidformula）例(

x)(P(x)∨

P(x))(

x)P(x)

P(y)25谓词公式及分类设

A

为一个谓词公式，若

A

在任何解释下真值均为假，则称

A

为不可满足的（unsatisfiable）公式或矛盾式例(

x)(P(x)∧

P(x))(

x)P(x)∧(

y)

P(y)26谓词公式及分类设

A

为一个谓词公式，若至少存在一个解释使

A

为真，则称

A

为可满足的（satisfiable）公式逻辑有效式一定是可满足式；反之不然27谓词公式及分类在命题逻辑中，一个公式是否是重言式是很容易验证的而对于谓词逻辑的判定问题：定理（丘奇-图灵（Church-Turing）定理）

对任一谓词公式而言，没有一个可行的方法判明它是否是普遍有效的。即谓词逻辑是不可判定的(undecidabilityoffirst-orderlogic)。但是谓词逻辑的某些子类是可判定的28谓词公式及分类设命题公式

A0

含命题变项

p1,p2,…,pn，用

n

个谓词公式

A1,A2,…,An

分别处处代换

p1,p2,…,pn

，所得公式

A

称为

A0

的代换实例。例P(y)

Q(z)，(

x)P(x)

(

x)Q(x)都是命题公式

p

q的代换实例。29谓词公式及分类定理

命题公式中的重言式的代换实例都是逻辑有效式，在谓词公式中可仍称为重言式；命题公式中的矛盾式的代换实例都是矛盾式。例(1)

xP(x)

(

x

yQ(x,y)

xP(x))

p

(q

p)(2)

xP(x)

(

xP(x)∨

yG(y)) p

(p∨q)30谓词公式及分类设

A为谓词公式，B为

A

中的一个连续的符号串，且

B

为谓词公式，则称

B

为

A

的子公式（subformula）31谓词公式及分类设

A为谓词公式，(

x)P(x)或

(

x)P(x)为公式

A

的子公式紧跟在

、

之后的

x

称为量词的指导变项或作用变项，P(x)称为相应量词的作用域或辖域（scope）在辖域中

x

的一切出现均称为约束出现，受指导变项所约束所有约束出现的变项称为约束变项（boundedvariable）在

A

中除了约束变项外出现的变项均称为自由变项（freevariable），不受指导变项的约束32谓词公式及分类

x

(

P(x,z)

y

Q(x,

y))∧

xR(x,y)33第三章谓词逻辑§3.1谓词与量词§3.2谓词公式及分类§3.3自然语句形式化§3.4谓词逻辑的等值演算§3.5前束范式§3.6谓词逻辑的推理34自然语句形式化基本方法是：1.

首先要将问题分解成一些原子命题和逻辑联结符2.

之后分解出各个原子命题的个体词、谓词和量词3.

按照合式公式的表示规则翻译出自然语句35自然语句形式化

xOdd(x)

xEven(x)

x

(Even(x)∨Odd(x))

x(Even(x)∧Odd(x))

x(Even(x)∧Prime(x))

x(Prime(x)(Equal(x,2)∨Odd(x)))36论域：正整数集Greater(x,y)表示“x>y”Equal(x,y)表示“x=y”自然语句形式化

x

y(Greater(y,x)∧Prime(y))

x

y(Equal(x,y+2)∧Prime(x)∧Prime(y))

x

y

z

((Equal(z,x+y)∧Odd(x)∧Odd(y))

Even(z))3738所有的素数都是正奇数

x(Prime(x)Odd(x))而不是

x(Prime(x)∧Odd(x))一般地讲，"所有的A是B”、“是A的都是B”、“一切A都是B的。”这类语句的形式描述只能使用“

”而不能使用“∧”自然语句形式化39没有正偶数是素数

x(Prime(x)∧Even(x))其他“等价的”写法

x(Even(x)

Prime(x))

x

(Prime(x)

Even(x))一般地讲，“有的A是B。”这类语句的形式描述只能使用“∧”而不能使用“

”。自然语句形式化40有一个偶的正奇数

x(Even(x)∧Odd(x))有一个正偶数，也有一个正奇数

xEven(x)∧

xOdd(x)

或

x

y(Even(x)∧Odd(y))这二者是不“等价”的！自然语句形式化41所有正整数都是正偶数或者正奇数

x(Odd(x)∨Even(x))所有正整数都是正偶数，或者所有正整数都是正奇数

xOdd(x)∨

x

Even(x)这二者是不“等价”的！自然语句形式化42对于任一个正整数而言，都存在比它大的正整数

x

yGreater(y,x)

y

x

Greater(y,x)存在一个正整数，大于任何正整数这二者是不“等价”的！

X自然语句形式化自然语句形式化对于任一个正奇数而言，都存在比它大的正偶数

x(Odd(x)y(Even(y)∧Greater(y,x)))43自然语句形式化存在某个正奇数，它小于所有正偶数

x(Odd(x)∧

y

(Even(y)Greater(y,x)))4445存在唯一的偶素数“存在且唯一”

x(P(x)∧

y(P(y)Equal(x,y)))

x((Prime(x)∧Even(x))∧

y(Prime(y)∧Even(y)Equal(x,y)))自然语句形式化自然语句形式化金子一定闪光，但闪光的不一定是金子G(x)：x

是金子L(x)：x

会闪光原语句可表示成(

x)(G(x)

L(x))∧(

x)(L(x)∧~G(x))4647天下乌鸦一般黑F(x)：x是乌鸦G(x,

y)：x

与

y

一般黑

原语句可表示成(

x)(

y)(F(x)∧F(y)

G(x,

y))或者~(

x)(

y)(F(x)∧F(y)∧~G(x,

y))自然语句形式化第三章谓词逻辑§3.1谓词、量词与自然语句形式化§3.2谓词公式及分类§3.3自然语句形式化§3.4谓词逻辑的等值演算§3.5前束范式§3.6谓词逻辑的推理48谓词逻辑的等值演算天下乌鸦一般黑F(x)：x是乌鸦G(x,

y)：x

与

y

一般黑

原语句可表示成(

x)(

y)(F(x)∧F(y)

G(x,

y))或者~(

x)(

y)(F(x)∧F(y)∧~G(x,

y))49谓词逻辑的等值演算设

A,B

是两个谓词公式，若

A

B是普遍有效的公式，则称

A

与

B

等值，记作

A

B

。类似于命题逻辑，两个谓词公式

A,B

等值当且仅当在任何解释下，A和

B

的真值都相同。谓词逻辑的等值演算仍是以基本等值式为基础，应用等值演算规则，逐步推演50谓词逻辑的等值演算谓词逻辑中的基本等值式主要分两类：其一是从命题公式移植来的等值式，即命题逻辑中基本等值式的代换实例如(

x)F(x)

(

y)G(y)

(

x)F(x)∨(

y)G(y)另一类是谓词逻辑所特有的等值式，与量词有关

51谓词逻辑的等值演算（消去量词等值式）设论域

D={a1,a2,…,am}

是有限集合，则有(

x)A(x)

A(a1)∧A(a2)∧…∧A(am)(

x)A(x)

A(a1)∨A(a2)∨…∨A(am)52谓词逻辑的等值演算例设论域

D={a,b,c}

，消去下面公式中的量词： (1)

x(F(x)

G(x))

(F(a)

G(a))∧(F(b)

G(b))∧(F(c)

G(c))

(2)

x

yF(x,y)

x(F(x,a)∧F(x,b)∧F(x,c))

(F(a,a)∧F(a,b)∧F(a,c))

∨(F(b,a)∧F(b,b)∧F(b,c)) ∨(F(c,a)∧F(c,b)∧F(c,c))53谓词逻辑的等值演算（量词否定等值式/德·摩根律）设

A(x)

是含

x

自由出现的公式，则

(

x)A(x)

(

x)

A(x)

(

x)A(x)

(

x)

A(x)54

当

D={a1,a2,…,am}时

xA(x)

A(a1)∧A(a2)∧…∧A(am)，

xA(x)

A(a1)∨A(a2)∨…∨A(am)

~

xA(x)

~(A(a1)∧A(a2)∧…∧A(am))

~A(a1)∨~A(a2)∨…∨~A(am)

x

A(x)55谓词逻辑的等值演算（量词辖域收缩与扩张等值式）设

A(x)是含

x

自由出现的公式，谓词公式

B

中不含

x

的出现，则有

x(A(x)∨B)

xA(x)∨B

x(A(x)∧B)

xA(x)∧B

x(A(x)∨B)

xA(x)∨B

x(A(x)∧B)

xA(x)∧B56（量词分配等值式）设

A(x),B(x)是含

x

自由出现的谓词公式，则有

x(A(x)∧B(x))

xA(x)∧xB(x)

x(A(x)∨B(x))

xA(x)∨xB(x)注意：

对∨不满足分配律，

对∧不满足分配律

当

D={a1,a2,…,am}时

xA(x)

A(a1)∧A(a2)∧…∧A(am),

xA(x)

A(a1)∨A(a2)∨…∨A(am)

谓词逻辑的等值演算谓词逻辑的等值演算设

A(x,y)

是含

x,y

自由出现的谓词公式，则有

x

yA(x,y)y

xA(x,y)

x

yA(x,y)y

xA(x,y)这组等值式表明相同量词与排列的次序无关，但是对于不同量词，不能随意更换次序，即

(

x)(

y)A(x,y)与

(

y)(

x)A(x,y)不等值57谓词逻辑的等值演算谓词逻辑包括以下三条等值演算规则：置换规则设

(A)

是含谓词公式

A

的公式，

(B)

是用谓词公式

B

取代

(A)

中的

A

（不一定是每一处）之后得到的谓词公式，若

A

B，则

(A)

(B)

。代替规则换名规则58谓词逻辑的等值演算

x

(

P(x,z)

y

Q(x,

y))∧

xR(x,y)59

谓词逻辑的等值演算

x

(

P(x,z)

y

Q(x,

y))∧

xR(x,y)同一个个体变项符号既有约束出现又有自由出现，容易引起概念上的混淆。为避免这种情况，引入了下面的代替规则和换名规则，使得同一个个体变项符号在一个公式中只呈现一种形式，要么为约束出现，要么为自由出现同时使不同的量词所约束的个体变项不同名，便于计算机处理60谓词逻辑的等值演算（代替规则）将谓词公式

A

中某个自由出现的个体变项的所有自由出现改成

A

中未曾出现的某个个体变项符号，其余部分不变，记所得谓词公式为

A

，则

A

A

61谓词逻辑的等值演算（换名规则）将谓词公式

A

中某量词的指导变项及其在辖域内的所有约束出现改成该量词辖域内未曾出现的某个个体变项符号，其余部分不变，记所得谓词公式为

A

，则A

A

62谓词逻辑的等值演算换名规则

xφ(x,x1,

x2,

…,

xn)

y

φ(y,x1,

x2,

…,

xn)

xφ(x,x1,

x2,

…,

xn)

y

φ(y,x1,

x2,

…,

xn)其中

y

{x1,

x2,

…,

xn}6364谓词逻辑的等值演算

x

(

P(x,y)

yQ(x,z))∧

xR(x,y)

u

(

P(u,y)

yQ(u,z))∧

xR(x,y)

x(

P(x,y)

yQ(x,z))∧

v

R(v,y)

谓词逻辑的等值演算例将公式

(

x)F(x,y,z)

(

y)G(x,y,z)

化为与之等值的公式，使其没有既是约束出现又是自由出现的个体变项符号解(

x)F(x,y,z)

(

y)G(x,y,z)

(

u)F(u,y,z)

(

y)G(x,y,z)

（换名规则）

(

u)F(u,y,z)

(

v)G(x,v,z)

（换名规则）或者(

x)F(x,y,z)

(

y)G(x,y,z)

(

x)F(x,u,z)

(

y)G(x,y,z)

（代替规则）

(

x)F(x,

u,

z)

(

y)G(v,

y,

z)

（代替规则）65

谓词逻辑的等值演算

代替规则换名规则使用对象任一谓词公式改名对象自由变项指导变项及其在辖域内的所有约束出现改名方式对公式中出现的所有同名的自由变项进行改名对指导变项及其量词辖域中所出现的约束变项处处进行改名改名限制公式中未曾出现的某个个体变项符号新的变项符号应是该量词辖域内未曾出现的改名结果与原公式等值6667谓词逻辑的等值演算例证明等值式

x(P(x)Q(x))xP(x)xQ(x)证明

x(P(x)Q(x))

x(P(x)∨Q(x))

x

P(x)∨

xQ(x)

xP(x)∨

xQ(x)

xP(x)xQ(x)谓词逻辑的等值演算天下乌鸦一般黑F(x)：x是乌鸦G(x,

y)：x

与

y

一般黑

原语句可表示成(

x)(

y)(F(x)∧F(y)

G(x,

y))或者~(

x)(

y)(F(x)∧F(y)∧~G(x,

y))6869谓词逻辑的等值演算

(

x)(

y)(F(x)∧F(y)∧

G(x,y))

(

x)

(

y)(F(x)∧F(y)∧

G(x,y))

(

x)(

y)

(F(x)∧F(y)∧

G(x,y))

(

x)(

y)(

(F(x)∧F(y))∨G(x,y))

(

x)(

y)(F(x)∧F(y)

G(x,y))谓词逻辑的等值演算证明

x(P(x)

Q(x))是假命题的方法——由~(

x(P(x)

Q(x)))

(

x)(P(x)∧

Q(x)))则只需要找到论域D

中一个个体x0使得P(x0)同时Q(x0)为假这个过程称作反驳（disproof）x0

称作反例（counterexample）70第三章谓词逻辑§3.1谓词、量词与自然语句形式化§3.2谓词公式及分类§3.3自然语句形式化§3.4谓词逻辑的等值演算§3.5前束范式§3.6谓词逻辑的推理71前束范式设

A为一谓词公式，如果满足(1)所有量词都位于该公式的最左边；

(2)所有量词前都不含否定词；

(3)量词的辖域都延伸到整个公式的末端，

则称

A为前束范式（prenexformalform）72前束范式前束范式的一般形式为：Q1

x1

Q2

x2

Qn

xn

M(x1,x2,

,xn)其中

Qi(1

i

n)为

或

Q1

x1

Q2

x2

Qn

xn称为前束M

为不含量词的公式，称作公式的基式或母式73前束范式

xP(x)∨

xQ(x)

x

y

~(P(x)

Q(y))

x

yR(x,y)R(x,y)~

xR(x,y)

x(P(x)

Q(x))∨R(z)74

前束范式化前束范式的基本方法：步骤1.

消去谓词公式中的联结词

，

；步骤2.

将谓词公式中的否定词

右移步骤3.

将谓词公式中的量词左移（使用量词分配等值式、量词辖域收缩与扩张等值式），必要时将变项改名7576前束范式例求

((

x)(

y)P(a,x,y)

(

x)(

(

y)Q(y,b)

R(x)))

的前束范式解步骤1.消去联结词

((

x)(

y)P(a,x,y)

(

x)(

(

y)Q(y,b)

R(x)))

(

(

x)(

y)P(a,x,y)∨(

x)(

(

y)Q(y,b)∨R(x)))步骤2.

否定连接词右移

(

(

x)(

y)P(a,x,y)∨(

x)(

(

y)Q(y,b)∨R(x)))

(

x)(

y)P(a,x,y)∧

(

x)((

y)Q(y,b)∨R(x))

(

x)(

y)P(a,x,y)∧(

x)((

y)

Q(y,b)∧

R(x))

77前束范式步骤3.量词左移

(

x)(

y)P(a,x,y)∧(

x)((

y)

Q(y,b)∧

R(x))

(

x)((

y)P(a,x,y)∧(

y)

Q(y,b)∧

R(x))

(

x)((

y)(

z)((P(a,x,y)∧

Q(z,b))∧

R(x))

(

x)(

y)(

z)(P(a,x,y)∧

Q(z,b)∧

R(x))

(

x)(

y)(

z)M(a,b,x,y,z)

前束范式

注

((

x)(

y)P(a,x,y)

(

x)(

(

y)Q(y,b)

R(x)))

(

x)(

y)(

z)(P(a,x,y)∧

Q(z,b)∧

R(x))

(

x)(

z)(

y)(P(a,x,y)∧

Q(z,b)∧

R(x))

(

x)(

y)(

z)(P(a,x,y)∧

Q(z,b)∧

R(x)∧T)78任一不含量词的普遍有效的公式等值的前束范式不唯一前束范式定理（前束范式存在定理）

任一谓词公式都存在与之等值的前束范式，但其前束范式并不唯一。79第三章谓词逻辑§3.1谓词、量词与自然语句形式化§3.2谓词公式及分类§3.3自然语句形式化§3.4谓词逻辑的等值演算§3.5前束范式§3.6谓词逻辑的推理80谓词逻辑的推理从前提

H1,H2,…,Hn出发推出结论

C

的推理形式结构，依然采用如下的蕴涵式形式：(H1∧H2∧…∧Hn)

C若上式为逻辑有效式，则称推理正确，称

C为前提

H1,H2,…,Hn的逻辑结论或有效结论81谓词逻辑的推理由于在谓词逻辑中不能使用真值表法，又不存在判别

A

B是否普遍有效的一般方法，从而使用基本推理公式及推理规则是谓词逻辑的基本推理演算方法82谓词逻辑的推理（基本推理公式）以下蕴含式都是普遍有效公式(

x)P(x)∨(

x)Q(x)

(

x)(P(x)∨Q(x))(

x)(P(x)∧Q(x))

(

x)P(x)∧(

x)Q(x)(

x)(P(x)

Q(x))

((

x)P(x)

(

x)Q(x))(

x)(P(x)

Q(x))

((

x)P(x)

(

x)Q(x))(

x)(

y)P(x,y)

(

x)(

y)P(x,y)(

x)(

y)P(x,y)

(

y)(

x)P(x,y)(

x)(

y)P(x,y)

(

x)(

y)P(x,y)83谓词逻辑的推理而所使用的推理规则除命题逻辑的推理演算中用到的几条基本推理规则外，还包括四条有关量词的消去和引入规则：全称推广规则/全称量词引入规则(UG)全称举例规则/全称量词消去规则(US)存在推广规则/存在量词引入规则(EG)

存在举例规则/存在量词消去规则(ES)84谓词逻辑的推理全称量词消去规则：

x

P(x)

P(y)或

x

P(x)

P(a)

其中y是论域中一个体

意指如果所有的x

D都具有性质P，那么D中任一个体y必具有性质P该规则使用的条件是：(1)第一式中，取代x的y应为任意的不在P(x)中约束出现的个体变项(2)第二式中，a为任意个体常项(3)用y或a去取代P(x)

中自由出现的x

时，必须在x自由出现的一切地方进行取代85谓词逻辑的推理分析下述推理的正确性(1)(

x)(

y)G(x,y)

（前提引入）(2)(

y)G(y,y)

（全称量词消去）假定论域是整数集，谓词G(x,y)表示“x>y”违反条件(1)，用约束变项

y取代

x86谓词逻辑的推理全称量词引入规则：P(y)

(

x)P(x)，其中

y

是论域中任一个体。意指如果任一个个体

y

D

都具有性质

P，那么D

中所有个体

x

都具有性质

P。该规则使用的条件是：(1)无论

P(y)

中自由出现的个体变项

y

取何值，P(y)应该均为真。(2)取代自由出现的

y

的

x

不能在

P(y)

中约束出现。87谓词逻辑的推理分析下述推理的正确性(1)(

x)G(x,y)（对任意给定的y都成立）(2)(

x)(

x)G(x,x)

（全称量词引入）论域是整数集，谓词G(x,y)表示“x>y”结论(2)明显不正确违反条件(2)，用约束变项

x取代

y88谓词逻辑的推理存在量词引入规则：P(a)

(

x)P(x)，其中

a

是论域中一个体常项。意指如果有个体常项

a

具有性质

P

，那么

(

x)P(x)

必真。该规则使用的条件是：(1)a是特定的个体常项(2)取代

a

的

x

不在

P(a)

中出现过89谓词逻辑的推理存在量词消去规则：(

x)P(x)

P(a)，其中

a

是论域中的一个个体常项。意指如果论域

D

中存在某个体具有性质

P，那么必有特定个体

a

具有该性质

P。该规则使用的条件是：(1)a

是使

P

为真的特定的个体常项(2)a

不在

P(x)

中出现(3)P(x)中没有其它自由出现的个体变项(4)a

是在推导中未曾使用过的90谓词逻辑的推理分析下述推理的正确性(1)(

x)Q(x)

（前提引入）(2)(

x)

Q(x)

（前提引入）(3)Q(a)

（对(1)的存在量词消去）(4)

Q(a)

（对(2)的存在量词消去）(5)Q(a)∧

Q(a)

（(3)(4)合取）(6)(

x)(Q(x)∧

Q(x))

（存在量词引入）论域是整数集，谓词

Q(x)

表示“x是偶数”结论(6)明显不正确违反条件(4)，使用了在推导中曾使用过的

a91谓词逻辑的推理分析下述推理的正确性(1)(

x)(

y)G(x,y) （前提引入）(2)(

y)G(x,y)

（全称量词消去）(3)G(x,a)

（存在量词消去）(4)(

x)G(x,a)

（全称量词引入）(5)(

y)(

x)G(x,y)

（存在量词引入）假定论域是整数集，G(x,y)表示“x>y”结论(5)不正确违反条件(3)，(

y)的辖域G(x,y)中存在自由变项

x从语义上解释，G(x,a)成立时个体a是依赖于x

的，不是对所有的

x

对同一个

a

都有G(x,a)

成立92谓词逻辑的推理使用推理规则的推理演算过程是：步骤1.首先将以自然语句表示的推理问题形式化，转换为谓词公式步骤2.若不能直接使用基本的推理公式则消去量词步骤3.在无量词下使用规则和公式进行推理步骤4.最后再引入量词，得到相应结论93谓词逻辑的推理特别注意如下两点： (1)在既需要消去存在量词又需要消去全称量词时，一般要先使用存在量词消去规则，再使用全称量词消去规则。 (2)使用US，UG，ES，EG规则时，量词的辖域都必须延伸到整个公式的末端。

换言之，在含有多个量词的谓词推理中，使用消去规则应该按照从左到右的顺序，而引入规则的使用应该按照从右到左的顺序。94谓词逻辑的推理例

分析下述推理的正确性。(1)(

x)(P(x)

Q(x))

（前提引入）(2)(

x)P(x)

（前提引入）(3)P(c)

Q(c)

（对(1)的全称量词消去）(4)P(c)

（对(2)的存在量词消去）(5)Q(c)

（(3)(4)假言推理）(6)(

x)Q(x)

（存在量词引入）解由前提“(

x)(P(x)

Q(x))”和“(

x)P(x)”得到结论“(

x)Q(x)”是一个正确推理，整个推理过程从表面上看也是正确的但是步骤(4)违反了存在量词消去规则的使用条件(4)从语义上讲，步骤(3)中的c可以为任意个体常项，不见得使P为真，因此步骤(4)不一定成立只要调换步骤(3)和步骤(4)就得到了正确的推理过程95谓词逻辑的推理构造下述推理的证明：前提：(

x)(G(x)∨H(x))，(

x)~G(x)

结论：(

x)H(x)证明(1)(

x)(G(x)∨H(x)) （前提引入）(2)G(a)∨H(a)

（全称量词消去）(3)(

x)~G(x)

（前提引入）(4)~G(a)

（全称量词消去）(5)H(a)

（(2)(4)析取三段论）(6)(

x)H(x)

（存在量词引入）96谓词逻辑的推理构造下述各推理的证明：前提：(

x)P(x)

(

x)Q(x)

结论：(

x)(P(x)

Q(x))证明(1)(

x)P(x)

(

x)Q(x)

（前提引入）(2)(

x)(

y)(P(x)

Q(y))

（(1)置换）(3)(

y)(P(z)

Q(y))

（全称量词消去）(4)P(z)

Q(z)

（全称量词消去）(5)(

x)(P(x)

Q(x))

（全称量词引入）97谓词逻辑的推理例

在谓词逻辑中构造下面推理的证明所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。解P(x)表示“x是人”Q(x)表示“x会死”则得到如下推理