离散数学及其应用课件第2章谓词逻辑

离散数学及其应用1第2章谓词逻辑2.1谓词逻辑的基本概念2.2谓词合式公式2.3谓词公式的解释和分类2.4谓词演算的关系式2.5前束范式2.6谓词演算的推理22.1谓词逻辑的基本概念2.1.1个体词和谓词定义2.1.1个体词是指可以独立存在的客体，可以是一个具体的事物或抽象的概念，是原子命题所描述的对象。

谓词是用来说明个体的性质或个体间的关系。例如，小王是个大学生

3大于23谓词个体词个体词个体词谓词谓词

形如“b是A”类型的命题可表达为A(b)；表示多个个体间关系的命题，可表达为B(a，b)，或P(a，b，c)定义2.1.2

和一个个体相联系的谓词称为一元谓词，和二个个体相联系的谓词称为二元谓词，和n个个体相联系的谓词称为n元谓词。

个体常元

表示具体的或特定的个体，如a，b，c，

等；个体变元

表示抽象的或泛指的个体，如x，y，z，

等。

谓词常项

表示具体性质或关系的谓词，R(a)表示a是人；

谓词变项

表示抽象或泛指的谓词

，如：P(a)表示a具有P性质。4谓词表达式和命题函数定义2.1.3

一个原子命题可以用一个谓词常项P和几个个体常元，如a，b，c，

，表示成P(a，b，c，

)的形式。称P(a，b，c，

)为原子命题或命题的谓词表达式。

一个谓词常项P和几个个体变元如x，y，z，

表示成P(x，y，z，

)的形式，称为命题函数，其中的个体变元可以代表任意一个个体。注意：命题的谓词表达式是有真值的，命题函数的真值是不确定的。5例题写出下列命题的谓词表达式。

1.小王和小李是大学生。解：设A(x)：x是大学生。a：小王，b：小李。

A(a)

A(b)2.

北京是中国的首都。解：设F(x，y)：x是y的首都。a：北京，b：中国。F(a，b)3.如果你来，他就走。解：设P(x)：x来。Q(x)：x走。a：你，b：他。

P(a)

Q(b)6例题（续）4.如果3

2，2

1，则3

1。解：设B(x，y)：x

y。a：3，b：2，c：1。则

：

B(a，b)

B(b，c)

B(a，c)武汉位于北京和广州之间。解：设Q(x，y，z)：y位于x和z之间。a：北京，b：广州，c：武汉。Q(a，c，b)7个体域定义2.1.4命题函数中，个体变元的取值范围称为个体域或论述域。

个体域可以是有限的，也可以是无限的。把宇宙中一切事物作为对象的的集合称为全总个体域。通常，没有特别说明时，个体变元的论述域是指全总个体域。如：A(x)表示：x是大学生。个体域：华工计科1班学生，则A(x)是永真式。个体域：华工附中1班学生，则A(x)是永假式。个体域：xx公司员工，其中有些是大学生，有些不是大学生，则对有些人，A(x)为真，对有些人，A(x)为假。8例题给出执行语句“If

P(x)then

x：=1”以后x的值，其中P(x)为语句“x

1”，且执行到该语句时x的值如下：1)x=02)x=13)x=2解1)若x=0，P(x)为语句“0

1”，真值为0，不执行赋值语句“x：=1”，所以x=0。2)若x=1，P(x)为语句“1

1”，真值为0，不执行赋值语句“x：=1”，所以x=1。3)若x=2，P(x)为语句“2

1”，真值为1，执行赋值语句“x：=1”，所以x=1。92.1.2量词定义2.1.5表示个体常元或个体变元之间数量关系的词称为量词。量词有两种：全称量词

符号：

x表示对个体域“所有的x”，“每一个x”，“一切x”等。存在量词

符号：

x表示个体域中“存在这样的x”，“某个x”，“至少有一个x”或“有一些x”等。

xF(x)表示个体域中所有个体都有性质F

xF(x)表示个体域中存在个体有性质F10例题假设F(x)表示x选修离散数学，x的个体域是这个班的同学，将下面的两个命题符号化。这个班的所有学生都选修离散数学这个班有些学生选修离散数学解

当个体域是这个班的同学时：

xF(x)

xF(x)若个体域是全总个体域时，要引入一个新的谓词表示个体的取值范围。称这个表示个体范围的谓词为特性谓词。11例题假设F(x)表示x选修离散数学，将下面的两个命题符号化。这个班的所有学生都选修离散数学这个班有些学生选修离散数学解

（没有特别说明时个体域是全总个体域）设特性谓词S(x)：表示x是这个班的同学，

x(S(x)

F(x))

x(S(x)

F(x))注意：在使用全称量词时，

特性谓词和表示个体性质的谓词构成条件关系式；

在使用存在量词时，特性谓词和表示个体性质的谓词构成合取关系式。12例题在个体域分别为：(a):自然数集合，(b):实数集合时，将下列命题符号化，并给出它们的真值。对于任意的x，均有x2−3x+2=(x−1)(x−2);存在x，使得x+5=2。解

假设F(x)：x2−3x+2=(x−1)(x−2)，G(x)：x+5=2。(a)个体域为自然数集合。符号化为：

xF(x)，真值为1。符号化为：

xG(x)，真值为0。(b)个体域为实数集合。符号化为：

xF(x)，真值为1。符号化为：

xG(x)，真值为1。13例题用谓词逻辑将下列命题符号化。所有的偶数均能被2整除。解

设A(x)：x是偶数，B(x)：x能被2整除。

x(A(x)

B(x))这个班有些学生有电脑。解设A(x)：x是这个班的学生，B(x)：x有电脑。

x(A(x)

B(x))。14例题（续）没有不犯错误的人。解设A(x)：x是人，B(x)：x犯错误。

x(A(x)

B(x))。尽管有人聪明，但未必一切人都聪明。解设A(x)：x是人，B(x)：x聪明。

x(A(x)

B(x))

x(A(x)

B(x))15例题（续）5.有些人喜欢某些体育运动。解

设A(x)：x是人，B(y)：y是体育运动，

C(x，y)：x喜欢y。

x(A(x)

y(B(y)

C(x，y)))。6.并非所有的工作都可以由一些机器人来完成。解设A(x)：x是工作，B(x，y)：x可以由y来完成，

R(x)：x是机器人。

x(A(x)

y(R(y)

B(x，y)))。16量词当论述域中的元素个数有限时，例如，论述域为n个元素的集合{a1，a2，a3，

an}时，有

x

A(x)

A(a1)

A(a2)

A(a3)

A(an)

x

A(x)

A(a1)

A(a2)

A(a3)

A(an)17例题若P(x)是语句“x2>10”，论述域为不超过4的正整数，

xP(x)和

x

P(x)的真值是什么？

解

由于论述域为{1，2，3，4}，命题

xP(x)为

x

P(x)

P(1)

P(2)

P(3)

P(4)而P(1)即“12>10”为假，所以

x

P(x)为假。命题

xP(x)为

x

P(x)

P(1)

P(2)

P(3)

P(4)而P(4)即“42>10”为真，所以

x

P(x)为真。18例题设P(x，y)表示“x+y>10”，论述域为实数，

x

yP(x，y)和

y

xP(x，y)的真值是什么？

解

x

yP(x，y)表示命题：“对每一个实数x，都存在实数y，使得x+y>10成立”，这是个真命题，真值为1。

y

xP(x，y)表示命题：“存在实数y，对每一个实数x，都有x+y>10成立”，这是个假命题，真值为0。注意：除非所有量词都是全称量词或存在量词，否则，多个量词同时出现时，不能随意颠倒量词的顺序，颠倒后会改变原命题的含义。192.2谓词演算公式一个谓词P和n个个体变元，如x1，x2，x3，

xn，表示成P(x1，x2，x3，

xn)的形式，称为n元原子谓词公式，简称n元谓词公式。如果谓词公式中没有个体变元，即n=0时称为0元谓词公式。0元谓词公式就是原子命题。20谓词演算公式定义2.2.1谓词演算的合式公式，简称谓词演算公式，定义如下：每一个原子谓词公式都是谓词演算公式。如果A是谓词公式，则(

A)是谓词公式。如果A和B都是谓词公式，则(A

B),(A

B),(A

B),(A

B)都是谓词公式。如果A是谓词公式，x是其中的任一变元，则

xA和

xA都是谓词公式。当且仅当有限次地应用上面的步骤得到的符号串才是谓词公式。21量词的辖域及变元的约束定义2.2.2谓词公式

xA和

xA中出现在量词

和

后面的变元x称为量词的指导变元。每个量词后面的最小的谓词子公式，称为该量词的辖域。在量词的辖域中，x的所有出现都称为约束出现。约束出现的变元称为约束变元。除约束变元以外的其它变元的出现称为自由出现。自由出现的变元称为自由变元。22例题说明以下谓词公式中各量词的辖域及变元的约束情况。(1)

x(P(x)

Q(x))；(2)

x(P(x)

yQ(x，y))；(3)

x

y(P(x，y)

Q(y，z))

x

R(x，y)解(1)

x的辖域是P(x)

Q(x)，x为约束变元。(2)

x的辖域是P(x)

yQ(x，y)，

y的辖域是Q(x，y)，x，y为约束变元。(3)

x的辖域是

y(P(x，y)

Q(y，z))，

y的辖域是P(x，y)

Q(y，z)，

x的辖域是R(x，y)。在

x

y(P(x，y)

Q(y，z))中，x，y为约束变元，z为自由变元。在

x

R(x，y)中，x为约束变元，y为自由变元。23约束变元换名和自由变元代入对谓词公式中约束出现的变元更改符号名称，称为约束变元换名。约束变元换名规则：将量词中的指导变元以及该量词辖域中该变元的所有出现更改为辖域中没有出现的变元名称，公式的其余部分不变。对谓词公式中自由出现的变元更改符号名称，称为自由变元代入。自由变元代入规则：对某自由出现的个体变元的每一处都代入与原公式中所有变元的名称不相同的变元。24例题对下列谓词公式中的变元更名，使每一变元只呈现一种出现形式。(1)

x(P(x)

Q(x，y))

R(x，y)；(2)

x(P(x，y)

Q(y，z))

x

R(x，y)

yS(y)解(1)利用约束变元换名规则，将

x(P(x)

Q(x，y))中的约束变元x换成z，得公式为：

z(P(z)

Q(z，y))

R(x，y)；或利用自由变元代入规则，将R(x，y)中的x用z代入，得公式为：

x(P(x)

Q(x，y))

R(z，y)。(2)利用约束变元换名规则，将

x

R(x，y)中的约束变元x换成u，利用自由变元代入规则，将自由出现的三处y用t代入，得公式为：

x(P(x，t)

Q(t，z))

uR(u，t)

yS(y)。25闭式定义2.2.3任一谓词公式A，若A中没有自由出现的个体变元，称A是封闭的谓词公式，简称闭式。例判断下列谓词公式是否是闭式？

x(P(x)

Q(x))；

x

y(P(x，y)

Q(y，z))

yS(y)解1.是闭式，因为无自由出现的变元；2.不是闭式，有自由出现的变元z。262.3谓词公式的解释和分类2.3.1谓词公式的解释定义2.3.1谓词逻辑中公式A的一个解释（或赋值）I由如下四部分组成：非空的个体域集合D；A中的每个常元符号，指定D中的某个特定的元素；A中的每个n元函数符号，指定Dn到D的某个特定的函数；A中的每个n元谓词符号，指定Dn到{0,1}的某个特定的谓词；27例题给定解释I如下：个体域为自然数集合N；a=0；N中特定的函数f(x,y)=x+y，g(x,y)=xy；N中特定的谓词F(x,y)：x=y。在解释I下，求下列公式的真值。

xF(g(x,y),z);

xF(g(x,a),x)

F(x,y);

x

y

zF(f(x,y),z);28例题（续）解(1)

xF(g(x,y),z)

x(xy=z)，不是命题，真值不确定。（2）

xF(g(x,a),x)

F(x,y)

x(xa=x)

(x=y)

x(0=x)

(x=y)

1，因为蕴含式前件为假。（3）

x

y

zF(f(x,y),z)

x

y

z(x+y=z)

1。定理2.3.1

封闭的谓词公式在任何解释下都变成命题。证明略。不是闭式的谓词公式在某些解释下也可能变成命题，如公式(2)292.3.2谓词公式的分类定义2.3.2设A是一个谓词公式，如A在任何解释下的真值恒为真，则称A为永真式(或逻辑有效式)；如A在任何解释下的真值恒为假，则称该谓词公式为永假式(或矛盾式)；如果至少存在一个解释使A的真值为真，则称A为可满足式。30例题判定公式

x

yA(x，y)

y

xA(x，y)的类型。解

设个体域为自然数集合，令A(x，y)表示xy=y。

y

xA(x，y)在该解释下的真值为1，而此时

x

yA(x，y)的真值也为1。因而在此解释下

x

yA(x，y)

y

xA(x，y)的真值为1。再设个体域为自然数集合，A(x，y)表示x

y。

y

xA(x，y)在该解释下的真值为1，而此时

x

yA(x，y)的真值为0。因而在此解释下

x

yA(x，y)

y

xA(x，y)的真值为0。因此公式

x

yA(x，y)

y

xA(x，y)不是永真式，是可满足式。31命题公式的代换实例定义2.3.3

设A0是含命题变元p1，p2，p3，

pn的命题公式，A1,A2,…An是n个谓词公式，用Ai(1

in)处处代替A0中的pi，所得公式A称为A0的代换实例。如F(x)

G(y)，

xF(x)

xF(x)都是p

q的代换实例。定理2.3.2

命题公式中永真式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。证明略。32例题判断下列公式是永真式还是矛盾式。

xF(x)

xF(x);

xF(x)

(

yG(y)

xF(x));F(x,y)

(G(x,y)

F(x,y));解1.

xF(x)

xF(x)为永真式。2.因为p

(q

p)

1，而

xF(x)

(

yG(y)

xF(x))是p

(q

p)的代换实例，所以

xF(x)

(

yG(y)

xF(x))是永真式。3.因为p

(q

p)

(

q

p)

p

q

p

0，而F(x,y)

(G(x,y)

F(x,y))是p

(q

p)的代换实例，所以F(x,y)

(G(x,y)

F(x,y))是矛盾式。332.4谓词演算的关系式定义2.4.1设A和B是任意两个谓词公式，如果A

B是永真式，则称谓词公式A和B等价，记为A

B。谓词逻辑的等价式有：命题逻辑中的等价式的代换实例是谓词逻辑中的等价式谓词逻辑中特有的等价式34谓词逻辑的等价式（1）定理2.4.1（量词否定转换律）设A(x)是任意谓词公式，则有(1)

xA(x)

x

A(x)(2)

xA(x)

x

A(x)证明

（1）

xA(x)为真

xA(x)为假

a使A(a)为假

a使

A(a)为真

x

A(x)为真，所以

xA(x)

x

A(x)。(2)

x

A(x)为假

a使

A(a)为假

a使A(a)为真

xA(x)为真

xA(x)为假，所以

xA(x)

x

A(x)。35谓词逻辑的等价式（2）定理2.4.2（量词辖域扩张和收缩律）设A(x)是包含x为自由变元的公式，B是不包含x的公式，则有365.xA(x)

B

x(A(x)

B)6.xA(x)

B

x(A(x)

B)7.B

xA(x)

x(B

A(x))8.B

xA(x)

x(B

A(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)

B证明：谓词逻辑的等价式（3）定理2.4.3（量词分配律）设A(x)，B(x)是包含自由变元x的公式，则有(1)

xA(x)

xB(x)

x(A(x)

B(x))(2)

xA(x)

xB(x)

x(A(x)

B(x))证明

（1）设I为任意解释。如果

xA(x)

xB(x)在I下为真，则

xA(x)和

xB(x)都为真，于是对于任意一个个体a都有A(a)

B(a)为真，所以

x(A(x)

B(x))为真，因此

xA(x)

xB(x)

x(A(x)

B(x))。如果

x(A(x)

B(x))在I下为真，则对于任意一个个体a都有A(a)和B(a)为真，从而

xA(x)和

xB(x)都为真，于是

xA(x)

xB(x))为真，因此

x(A(x)

B(x))

xA(x)

xB(x)。故

xA(x)

xB(x)

x(A(x)

B(x))。37谓词逻辑的等价式（4）定理2.4.4设A(x,y)是包含自由变元x,y的二元谓词公式，则有：(1)

x

yA(x,y)

y

xA(x,y)(2)

x

yA(x,y)

y

xA(x,y)38例题证明下面的等价式成立。

x(A(x)

B(x))

xA(x)

x

B(x)；

xA(x)

B(x)

y(A(y)

B(x))证明

39谓词逻辑的蕴含式定义2.4.2设A和B是任意两个谓词公式，如果A

B是永真式，则称谓词公式A蕴含B，记为A

B，称A

B为蕴含式。定理2.4.5设A(x)，B(x)是包含自由变元x的公式，则有(1)

xA(x)

xB(x)

x(A(x)

B(x))(2)

x(A(x)

B(x))

xA(x)

x

B(x)(3)

x(A(x)

B(x))

xA(x)

xB(x)(4)

x(A(x)

B(x))

xA(x)

x

B(x)40谓词逻辑的蕴含式定理2.4.5证明。证明

（1）若

x(A(x)

B(x))为假，则存在个体a使A(a)

B(a)为假，于是A(a)和B(a)都为假，因而

xA(x)和

xB(x)都为假，从而

xA(x)

xB(x)为假。所以

xA(x)

xB(x)

x(A(x)

B(x))。（3）利用推理的CP规则，

x(A(x)

B(x))

xA(x)

x((A(x)

B(x))

A(x))

x((

A(x)

B(x))

A(x))

x(B(x)

A(x))

xB(x)

xA(x)

xB(x)，所以

x(A(x)

B(x))

xA(x)

xB(x)。41例题证明下面的蕴含式成立。

xA(x)

xB(x)

x(A(x)

B(x))解

xA(x)

xB(x)

xA(x)

xB(x)

x

A(x)

xB(x)

x(

A(x)

B(x))

x(A(x)

B(x))42谓词逻辑的蕴含式定理2.4.6设A(x,y)是包含自由变元x,y的二元谓词公式，则有：

x

yA(x,y)

xA(x,x)

xA(x,x)

x

yA(x,y)

x

yA(x,y)

y

xA(x,y)

y

xA(x,y)

x

yA(x,y)证明

(1)设I为任意解释，如果

xA(x,x)在解释I下为假，则存在一个个体a,使得A(a,a)为假，于是

yA(a,y)为假，因而有

x

yA(x,y)为假，所以

x

yA(x,y)

xA(x,x)。43

y

xA(x,y)

x

yA(x,y)

x

yA(x,y)

y

x

A(x,y)

x

yA(x,y)

y

xA(x,y)

y

xA(x,y)

x

yA(x,y)前束范式定义2.5.1一个谓词公式A，若具有形式Q1x1Q2x2

QnxnM，其中每个Qi(1

i

n)为

或

，M为不含量词的谓词公式，则称谓词公式A为前束范式。Q1x1Q2x2

Qnxn称为首标，M称为母式。例如，

x

y(A(x，y)

B(x，y))，

x

y(A(x，y，z)

C(x，y))等都是前束范式，而

xA(x)

xB(x)，

xA(x)

xB(x，y)等都不是前束范式。44前束范式定理2.5.1任一谓词公式都存在着与之等价的前束范式。证明

设A为任意一个谓词公式，将公式化成只含3个联结词

、

、

的形式。利用

(

P)

P、De

Mogen律及量词转换律等将公式中的所有

符号移到原子公式的前面。如果需要的话，将约束变元换名。利用量词辖域收缩及扩张律、量词分配律等，将所有量词提到公式的最前面。按照以上步骤，可得到谓词公式A的前束范式。由于每一步变换都保持着等价的关系，所以得到的前束范式与原公式是等价的。45例题求下列谓词公式的前束范式。

xA(x)

xB(x)解

xA(x)

xB(x)

xA(x)

xB(x)(置换规则)

x

A(x)

xB(x)(定理2.4.1)

x(

A(x)

B(x))(定理2.4.3)或者

xA(x)

xB(x)

xA(x)

xB(x)(置换规则)

x

A(x)

xB(x)(定理2.4.1)

x

A(x)

yB(y)(换名规则)

x

y(

A(x)

B(y))(定理2.4.2)462.6谓词演算的推理谓词逻辑的推理形式：若(A1

A2

An)

B是永真式，则称由前提A1，A2，

，An可推出结论B，可表示为(A1

A2

An)

B。在命题逻辑的推理中使用的等价关系、蕴涵关系和推理规则在谓词逻辑的推理中同样适用，另外还有谓词演算特有的关于量词的规则。47全称量词消去规则(UI)：

xA(x)

A(y)或

xA(x)

A(c)成立的条件：

x是A(x)中自由出现的个体变元；

y是任意的不在A(x)中约束出现的个体变元；例如若A(x)

yF(x,y)，则

xA(x)

x

yF(x,y)，利用UI规则：

xA(x)

A(y)，于是

x

yF(x,y)

yF(y,y)，这个蕴含式是不成立，原因是使用UI规则时违背了条件②。48存在量词消去规则(EI)

xA(x)

A(c)成立的条件：c是个体域中使A成立的特定的个体常元；c不曾在A(x)中出现过；A(x)中除x外还有其他自由出现的个体变元时，不能用此规则。注意这里的c是使A成立的特定的个体常元，不要和公式中或推理证明过程中前面步骤的其它常元和变元名称相同。例如在实数集上F(x,y)：x>y，若A(x)

F(x,c)，c是实数集上的一个常数，则

xA(x)为真，例用EI规则，消去量词，用c取代x，得F(c,c)，这是假命题。原因是违背了条件(2)。49全称量词引入规则(UG)A(y)

xA(x)成立的条件：y是A(y)中自由出现的个体变元，y取个体域中的任何值，A都为真；取代y的x不能在A(x)中约束出现。例如在实数集上F(x,y)：x>y，若A(y)

xF(x,y)，则对任意的y，A(y)为真，用UG规则，用x取代y，得

x

xF(x,x)，显然这是假命题。原因是违背了条件(2)。50存在量词引入规则(EG)A(c)

xA(x)成立的条件：c是特定的个体常元；取代c的x不能在A(c)中出现过。例如在实数集上F(x,y)：x>y，若A(2)

xF(x,2)，则A(2)为真，例用EG规则，用x取代2，得

xF(x,x)，显然这是假命题。原因是违背了条件(2)。512.6.2推理问题的证明例2.6.1证明

x(P(x)

Q(x))是

x(P(x)

Q(x))

y(R(y)

S(y))，

y(R(y)

S(y))的结论。

证明：

y(R(y)

S(y))前提引入

y

(R(y)

S(y))(1)量词否定转换律

y(

R(y)

S(y))(2)德摩根律

y(R(y)

S(y))(3)

置换规则

x(P(x)

Q(x))

y(R(y)

S(y))前提引入

x(P(x)

Q(x))(4)，(5)拒取式

x(

P(x)

Q(x))(6)量词否定转换律、德摩根律

x(P(x)

Q(x))(7)置换规则52例题2.6.2例2.6.2证明苏格拉底三段论“所有的人都是要死的。苏格拉底是人。所以苏格拉底是要死的。”证明

设：M(x)：x是人；P(x)：x是要死的；a：苏格拉底。

前提符号化为：

x(M(x)

P(x))，M(a)。结论符号化为：P(a)。

证明

：(1)

x(M(x)

P(x))前提引入(2)M(a)

P(a)(1)UI(3)M(a)前提引入(4)P(a)(2)(3)假言推理53例题2.6.3例2.6.3证明“每个大学生都是聪明的,每个勤奋又聪明的大学生在学业中都会取得成功,有些大学生是勤奋的,所以有些大学生在学业中会取得成功.”是正确的推理。证明

设P(x)：x是大学生，Q(x)：x是聪明的，R(x)：x是勤奋的，S(x)：x在学业中都会取得成功。则前提为：

x(P(x)

Q(x))，

x(P(x)

R(x)

Q(x)

S(x))，

x(P(x)

R(x))，结论是：

x(P(x)

S(x))54例题2.6.3（续）

x(P(x)

R(x))前提引入P(c)

R(c)(1)EIP(c)(2)化简

x(P(x)

Q(x))前提引入P(c)

Q(c)(4)UIQ(c)(3)(5)假言推理R(c)(2)化简P(c)

Q(c)

R(c)(3)(6)(7)合取引入

x(P(x)

R(x)

Q(x)

S(x))前提引入P(c)

Q(c)

R(c)

S(c)(9)UIS(c)(8)(10)假言推理P(c)

S(c)(3)(11)合取引入

x(P(x)

S(x))(12)EG55例题2.6.4例2.6.4说明下面推理的错误，并指出错误的原因。

xP(x)

x

Q(x)前提引入

xP(x)(1)化简P(c)(2)EI

x

Q(x)(1)化简Q(c)(4)EIP(c)

Q(c)(3)(5)合取

x(P(x)

Q(x))(5)EG解

错误在第(5)步用EI规则时，用c取代x，c在前面步骤已用于特指使P为真的个体，在这里不一定能使Q为真。56例题2.6.4（续）正确的推理步骤是：

xP(x)

x

Q(x)前提引入

xP(x)(1)化简P(c)(2)EI