第一篇：谓词逻辑

习题二

(参考答案)2.1 在谓词逻辑中将下面命题符号化，（1）高斯是数学家，但不是文学家。

P(x):x是数学家.s(x):x是文学家.a:高斯 P(a)s(a)（2）如果小张比小李高，小李比小赵高，则小张比小赵高。

P(x,y):x比y高.a:小张.b:小李.c:小赵

(p(a,b)p(b,c))p(a,c)（3）鱼都会在水里游。

P(x)::x是鱼

R(x)x都会在水里游.x(P(x) R(x))（4）情商比智商更重要。

P(x,y):x比y更重要.a:情商.b:智商 P(a,b)（5）并不是所有的人都爱看电影。

P(x):x是人.G(x):爱看电影.x(p(x) G(x))或

x(p(x) G(x))（6）有的人爱吃醋，并且没有不爱美的人。

P(x):x是人.G(x):x爱吃醋.R(x):x爱美.x(P(x)G(x))x(P(x) R(x))2.2 利用二元谓词将下面命题符号化。（1）每列火车都比某些汽车快。

P(x,y):x比y快.M(x):x是火车.G(y):y是汽车 x(M(x)y(G(y)P(x,y))（2）某些汽车比所有火车慢。

P(x,y):x比y慢.M(x):x是汽车.G(y):y是火车 x(M(x)y(G(y)P(x,y)))2.3 在谓词逻辑中将下面命题符号化，要求使用全称量词与存在量词两种方法。（1）有的江西人没去过庐山。P(x):x是江西人.M(x):x去过庐山.x(P(x) M(x))或

x(P(x) M(x))（2）没有人不爱自己的祖国。

P(x):x是人.M(x):x爱自己的祖国 x(P(x) M(x))或

x(P(x) M(x))（3）并非每个清华大学的学生都是优等生。

P(x):x是清华大学的学生.M(x):x是优等生 x(P(x) M(x))

或

x(P(x) M(x))（4）没有不努力的大学生。

M(x):x是大学生

P(x):x是努力的.x(M(x) P(x)).或

x(M(x) P(x))2.4 指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元。如果有同名而引起混淆的情况，要求使用换名规则或代替规则改写。

（1）x(P(x)yQ(y))；

x的辖域为P(x)yQ(y).其中：x是约束出现 y的辖域为Q(y).其中：y是约束出现

（2）x(F(x) H(x,y)) H(x)；

x的辖域为F(x) H(x,y).其中：x是约束出现.y是自由出现 而原式中 H(x)中x是自由出现 更改后的为：x(F(x) H(x,y))H(z)（3）x(P(x)xQ(x,z)yR(x, y))Q(x, y)；

x的辖域为P(x)xQ(x,z)yR(x, y).其中：z是自由出现.x ,y是约束出现.x的辖域为Q(x,z).其中：x是约束出现.z是自由出现 y的辖域为R(x, y).其中：y是约束出现.x是自由出现 Q(x, y)中x、y是自由出现

更改后的为：x(p(x)u Q(u,z)yR(v, y))Q(s, t)（4）P(x)(yx(P(x)B(x,y))P(x))；

y与x的辖域为(P(x)B(x,y)).其中：x、y是约束出现 更改后的为：P(u)(yx(P(x)B(x,y)) P(u)2.5 设个体域D={1,2,3}，消去下列各公式中的量词。（1）xP(x)yQ(y)；(P(1) P(2) P(3))(Q(1) Q(2) Q(3))（2）xP(x)yQ(y)；(P(1) P(2) P(3))(Q(1) Q(2) Q(3))（3）xy P(x,y)。(P(1,1) P(1,2) P(1,3))(P(2,1) P(2,2) P(2,3))(P(3,1) P(3,2) P(3,3))2.6 设一元谓词F(x):x3,G(x):x5,R(x);x7，解释I为：个体域D={0,2,6 }，在I下求下列各式的真值。

（1）x(F(x)G(x));(F(0)G(0))(F(2)G(2))(F(6)G(6))F（2）x(R(x)F(x))G(5);((R(0) F(0))(R(2) F(2))(R(6) F(6)))G(5)F（3）x(F(x)G(x))。

(F(0)G(0))(F(2)G(2))(F(6)G(6))T 2.7 取个体域为整数集，给定下列各公式，判定命题的真值。（1）xy(xy1)

假（2）x(xyx);

不是命题

（3）xyz(xyz)；

真（4）xyz(x + y = z)；

真（5）yx(xy2)；

真（6）xy(xy2y)。

假 2.8 求下列各式的前束范式：（1）(xP(x)yP(y))； xy(P(x)p(y))（2）(xP(x)yzQ(y,z))； xyz(p(x) Q(y,z))（3）(xF(x)yG(y))(F(u)zH(z))； xyz((F(x)G(y))(F(u)H(z)))（4）xF(y,x)yG(y)； xy(F(u,x)G(y))

（5）x(F(x,y)yG(x,y))。xy(F(x,u) G(y))

2.9 构造下列推理的证明：

（1）前提：x(F(x) H(x))， H(y)

结论：x(F(x))

证明：①x[F(x)H(x)]

前提引入

②F(y)H(y)

①UI

③H(y)

前提引入

④F(y)

②③拒取式

⑤x[F(x)]

④UG（2）前提：x(F(x)G(x)H(x))，x(F(x)R(x))

结论：x(F(x)R(x)G(x))

证明：①x(F(x)R(x))

前提引入

②F(c) R(c)

①EI

③F(c)

②化简规则

④x(F(x)G(x)H(x))

前提引入 ⑤F(c) G(c)H(c)

④UI

⑥G(c)H(c)

③⑤假言推理

⑦G(c)

⑥化简规则

⑧F(y)R(y) G(y)

②⑦合取规则

⑨x[F(x)R(x) G(x)]

⑧EG（3）前提：x(F(x)H(x))，x(G(x)H(x))结论：G(y)F(y)

证明：①x(F(x)H(x))

前提引入

②x(F(x)H(x))

①置换规则 ③x(H(x)F(x))

②置换规则 ④H(y)F(y)

③UI ⑤x(G(x)H(x))

前提引入 ⑥G(y)H(y)

⑤UI ⑦G(y)F(y)

④⑥假言三段论

（4）前提：x(W(x)B(x))，x(B(x)R(x))，x(R(x))结论：x(W(x))证明：①xR(x)

前提引入

②R(c)

①EI ③x(B(x)R(x))

前提引入 ④B(c)R(c)

③UI ⑤B(c)

②④析取三段论 ⑥x(W(x)B(x))

前提引入 ⑦W(c)B(c)

⑥UI ⑧ W(c)

⑤⑦拒取式 ⑨x(W(x))

⑧EG 2.10 在谓词逻辑中，构造下面推理的证明。个体域是人的集合。

（1）每个科学工作者都是勤奋的，每个既勤奋又聪明的人在他的事业中都将获得成功，刘涛是科学工作者并且是聪明的，所以刘涛在他的事业中将获得成功。

F(x):x是科学工作者

G(x):x是勤奋的人

H(x):x是聪明的人

R(x):x在他的事业中都将获得成功

a: 刘涛

前提：x(F(x)G(x))x((G(x)H(x))R(x))

F(a)H(a)结论：R(a)证明：①x(F(x)G(x))

前提引入

②F(a)G(a)

①UI

③F(a)H(a)

前提引入

④F(a)

③化简规则

⑤G(a)

②④假言推理

⑥H(a)

③化简规则

⑦G(a)H(a)

⑤⑥合取规则

⑧x((G(x)H(x))R(x))

前提引入

⑨(G(a) H(a))R(a)

⑧UI

⑩R(a)

⑧⑨假言推理

（2）每个学术会的成员都是工人并且是专家，有些成员是青年人，所以有的成员是青年专家

F(x):x是学术会的成员

G(x):x是工人

H(x):x是专家 R(x):x是青年人

前提：x(F(x)(G(x)H(x)))

x(F(x)R(x))结论：x(F(x)H(x)R(x))证明：①x(F(x)R(x))

前提引入

②F(c)R(c)

①EI ③F(c)

②化简规则

④x(F(x)(G(x)H(x)))

前提引入

⑤F(c)(G(c)H(c))

④UI

⑥G(c)H(c)

③⑤假言推理

⑦H(c)

⑥化简规则

⑧F(c) R(c)H(c)

②⑦合取规则

⑨x(F(x)H(x)R(x))

⑧EG（3）每一个大学生不是文科生就是理科生；有的大学生是优等生；小张不是文科生但他是优等生。因此，如果小张是大学生，他就是理科生。

P(x):x是大学生

G(x):x是文科生

H(x):x是理科生

R(x):x是优等生

a:是小张

前提：x(P(x)(G(x)H(x)))

结论：P(a)H(a)证明：①x(P(x) R(x))

②P(a) R(a)

③P(a)

④G(a) R(a)

⑤G(a)

⑥x(P(x)(G(x)H(x)))

⑦P(a)(G(a)H(a))

⑧G(a)H(a)

⑨H(a)

⑩H(a)P(a)

⑾P(a)H(a)

x(P(x) R(x))

G(a) R(a)

前提引入

①EI ②化简规则

前提引入

④化简规则

前提引入

⑥UI

③⑦假言推理

⑤⑧析取三段论

⑨附加规则

⑩置换规则

第二篇：第2章谓词逻辑习题及答案

谓词逻辑习题

1.将下列命题用谓词符号化。（1）小王学过英语和法语。（3）3不是偶数。

（2）2大于3仅当2大于4。（4）2或3是质数。

（5）除非李键是东北人，否则他一定怕冷。解：

(1)令P(x)：x学过英语，Q(x)：x学过法语，c：小王，命题符号化为P(c)Q(c)(2)令P(x,y)：x大于y, 命题符号化为P(2,4)P(2,3)(3)令P(x)：x是偶数，命题符号化为P(3)(4)令P(x)：x是质数，命题符号化为P(2)P(3)

(5)令P(x)：x是北方人；Q(x)：x怕冷；c：李键；命题符号化为Q(c)P(x)

b，c}，消去下列各式的量词。2.设个体域D{a，（1）xy(P(x)Q(y))（3）xP(x)yQ(y)

（2）xy(P(x)Q(y))（4）x(P(x，y)yQ(y))

解：

(1)中A(x)y(P(x)Q(y))，显然A(x)对y是自由的，故可使用UE规则，得到

A(y)y(P(y)Q(y))，因此xy(P(x)Q(y))y(P(y)Q(y))，再用ES规则，y(P(y)Q(y))P(z)Q(z)，zD，所以xy(P(x)Q(y))P(z)Q(z)

（2）中A(x)y(P(x)Q(y))，它对y不是自由的，故不能用UI规则，然而，对

A(x)中约束变元y改名z，得到z(P(x)Q(z))，这时用UI规则，可得：

xy(P(x)Q(y))

xz(P(x)Q(z))

z(P(x)Q(z))（3）略（4）略，2，3}。求下列各式3.设谓词P(x，y)表示“x等于y”，个体变元x和y的个体域都是D{1（1）xP(x，3)

的真值。，y)（2）yP(1y)（4）xyP(x，y)（6）yxP(x，y)

（3）xyP(x，y)（5）xyP(x，解：

(2)当x3时可使式子成立，所以为Ture。

(3)当y1时就不成立，所以为False。

(4)任意的x,y使得xy，显然有xy的情况出现，所以为False。

(4)存在x,y使得xy，显然当x1,y1时是一种情况，所以为Ture。

(5)存在x，任意的y使得xy成立，显然不成立，所以为False。

(6)任意的y，存在x，使得xy成立，显然不成立，所以为False。

4.令谓词P(x)表示“x说德语”，Q(x)表示“x了解计算机语言C++”，个体域为杭电全体学生的集合。用P(x)、Q(x)、量词和逻辑联接词符号化下列语句。

（1）杭电有个学生既会说德语又了解C++。（2）杭电有个学生会说德语，但不了解C++。（3）杭电所有学生或会说德语，或了解C++。（4）杭电没有学生会说德语或了解C++。

假设个体域为全总个体域，谓词M(x)表示“x是杭电学生”。用P(x)、Q(x)、M(x)、量词和逻辑联接词再次符号化上面的4条语句。解：（ⅰ）个体域为杭电全体学生的集合时：

（1）x(P(x)Q(x))（2）x(P(x)Q(x))（3）x(P(x)Q(x))（4）x(P(x)Q(x))

（ⅱ）假设个体域为全总个体域，谓词M(x)表示“x是杭电学生”时：

（1）x(M(x)P(x)Q(x))（2）x(M(x)P(x)Q(x))（3）x(M(x)(P(x)Q(x)))（4）x(M(x)(P(x)Q(x)))

5.令谓词P(x，y)表示“x爱y”，其中x和y的个体域都是全世界所有人的集合。用P(x，y)、量词和逻辑联接词符号化下列语句。

（1）每个人都爱王平。

（2）每个人都爱某个人。（4）没有人爱所有的人。（6）有个人人都不爱的人。（8）成龙爱的人恰有两个。

（3）有个人人都爱的人。

（5）有个张键不爱的人。

（7）恰有一个人人都爱的人。

（9）每个人都爱自己。

（10）有人除自己以外谁都不爱。

解：a：王平b：张键

c：张龙

(1)xP(x,a）

(2)xyP(x,y)(3)yxP(x,y)

(4)xyP(x,y)(5)xP(b，x)

(6)xyP(x,y)(7)x(yP(y,x)z((P(,z))zx))

(8)xy(xyP(c,x)P(c)z(P(c，z)(zxzy)))(9)xP(x,x)

(10)xy(P(x,y)xy)§2.2 谓词公式及其解释

习题2.2 1.指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。

（1）x(P(x)Q(x，y))（2）xP(x，y)yQ(x，y)

（3）xy(P(x，y)Q(y，z))xR(x，y，z)

解：（1）x是指导变元，x的辖域是P(x)Q(x,y)，对于x的辖域而言，x是约束变元，y是自由变元。

（2）x,y都为指导变元，x的辖域是P(x，y)yQ(x，y)，y的辖域是Q(x，y)；对于x的辖域而言，x,y都为约束变元，对于y的辖域而言，x是自由变元，y是约束变元。

（3）x,y为指导变元，x的辖域是y(P(x，y)Q(y，z))xR(x，y，z)，y的辖域是(P(x，y)Q(y，z))xR(x，y，z)，x的辖域是R(x，y，z)；对于x的辖域而言，x,y为约束变元，z为自由变元，对于y的辖域而言，z为自由变元，y为约束变元，x即为约束变元也为自由变元，对于x的辖域而言，x为约束变元，y,z是自由变元。在整个公式中，x,y即为约束变元又为自由变元，z为自由变元。

2.判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。（1）x(P(x)Q(x))(xP(x)yQ(y))（2）x(P(x)Q(x))(xP(x)yQ(y))（3）(xP(x)yQ(y))yQ(y)（4）x(P(y)Q(x))(P(y)xQ(x))（5）x(P(x)Q(x))(P(x)xQ(x))（6）(P(x)(yQ(x，y)P(x)))（7）P(x，y)(Q(x，y)P(x，y))

解：（1）易知公式是(pq)(pq)的代换实例，而

(pq)(pq)(pq)(pq)1 是永真式，所以公式是永真式。

（2）易知公式是(pq)(pq)的代换实例，而

(pq)(pq)(pq)(pq)1 是永真式，所以公式是永真式。

（3）易知公式是(pq)q的代换实例，而

(pq)q(pq)qpqq0 是永假式，所以公式是永假式。

（4）易知公式是(pq)(pq)的代换实例，而

(pq)(pq)(pq)(pq)1 是永真式，所以公式是永真式。

（5）易知公式是(pq)(pq)的代换实例，而

(pq)(pq)(pq)(pq)1 是永真式，所以公式是永真式。

（6）易知公式是(p(qp))的代换实例，而

(p(qp))(p(qp))pqp0 是永假式，所以公式是永假式。

（7）易知公式是pqp的代换实例，而

pqp(pq)p(pq)p 是可满足式，所以公式是可满足式。§2.3 谓词公式的等价演算与范式

习题2.3 1.将下列命题符号化，要求用两种不同的等价形式。（1）没有小于负数的正数。

（2）相等的两个角未必都是对顶角。

解：（1）P(x)：x为负数，Q(x)：x是正数，R(x,y)：x小于y，命题可符号化为：xy(R(P(x),Q(y)))或xy(R(P(x),Q(y)))

（2）略

2.设P(x)、Q(x)和R(x，y)都是谓词，证明下列各等价式（1）x(P(x)Q(x))x(P(x)Q(x))（2）x(P(x)Q(x))x(P(x)Q(x))

（3）xy(P(x)Q(y)R(x，y))xy(P(x)Q(y)R(x，y))（4）xy(P(x)Q(y)R(x，y))xy(P(x)Q(y)R(x，y))证明：（1）左边＝x(P(x)Q(x))

＝x(P(x)Q(x))＝x(P(x)Q(x))＝右边

（2）左边 ＝x(P(x)Q(x))

＝x(P(x)Q(x))

＝x(P(x)Q(x))＝右边

（3）左边＝xy(P(x)Q(y)R(x,y))

＝xy((P(x)Q(y))R(x,y))

＝xy(P(x)Q(y)R(x，y))＝右边

（4）左边＝xy(P(x)Q(y)R(x,y)

＝xy(P(x)Q(y))R(x,y)

＝xy(P(x)Q(y)R(x，y))＝右边

3.求下列谓词公式的前束析取范式和前束合取范式。（1）xP(x)yQ(x，y)

（2）x(P(x，y)yQ(x，y，z))（3）xyP(x，y)(zQ(z)R(x))

（4）x(P(x)Q(x，y))(y(R(y)zS(y，z))

解：（1）原式xyP(x)Q(z,y)xy(P(x)Q(z,y))

前束析取范式

xy(P(x)Q(z,y))

前束合取范式

（2）原式xt(P(x,y)Q(x,t,z)xt(P(x,y)Q(x,t,z)前束析取范式

xt(P(x,y)Q(x,t,z)

前束合取范式（3）原式xyz(P(x,y)(Q(z)R(t))

xyz(P(x,y)Q(z)R(t))

前束析取范式

xyz(P(x,y)Q(z)R(t))

前束合取范式（4）原式x(P(x)Q(x，y))(t(R(t)zS(t，z))

xtz((P(x)Q(x,y))(R(t)S(t,z)))

xtz((P(x)Q(x,y))(R(t)S(t,z)))

xtz((P(x)Q(x,y)R(t))(P(x)Q(x,y)S(t,z)))

xtz((P(x)(R(t)S(t,z))(Q(x,y)R(t)S(t,z)

§2.4 谓词公式的推理演算

习题2.4 1.证明：x(A(x)B(x))x(A(x)B(x))

证明：（1）左边x(A(x)B(x))x(A(x)B(x))

x(A(x)B(x))＝x(A(x)B(x))2.指出下面演绎推理中的错误，并给出正确的推导过程。（1）①xP(x)Q(x)

②P(y)Q(y)

P规则 US规则：① P规则 US规则：① P规则 ES规则：① P规则 UG规则：① P规则 EG规则：① P规则 EG规则：①（2）①x(P(x)Q(x))

②P(a)Q(b)

（3）①P(x)xQ(x)

②P(a)Q(a)（4）①P(a)G(a)

②x(P(x)G(x))

（5）①P(a)G(b)

②x(P(x)G(x))

（6）①P(y)Q(y)

②x(P(c)Q(x))

解：（1）②错，使用US,UG,ES,EG规则应对前束范式，而①中公式不是前束范式，所以不能用US规则。

A(x)P(x)Q(x)，(2)②错，①中公式为xA(x)，这时，因而使用US规则时，应得A(a)(或A(y)),故应有P(a)Q(a)，而不能为P(a)Q(b)。

3.用演绎法证明下列推理式

xP(x)y((P(y)Q(y))R(y))，xP(x)xR(x)

证明：① xP(x)前提引入

② P(a)ES①

③ xP(x)y((P(y)Q(y))R(y))

前提引入

④ y((P(y)Q(y))R(y))T①③

⑤(P(a)Q(a))R(a)US④

⑥ P(a)Q(a)

T②

⑦ R(a)T⑤⑥

⑧ xR(x)EG⑦

4.将下列命题符号化，并用演绎推理法证明其结论是有效的。（1）有理数、无理数都是实数；虚数不是实数。因此，虚数既不是有理数，也不是无理数。（个体域取全总个体域）（2）所有的舞蹈者都很有风度；万英是个学生并且是个舞蹈者。因此，有些学生很有风度。（个体域取人类全体组成的集合）（3）每个喜欢步行的人都不喜欢骑自行车；每个人或者喜欢骑自行车或者喜欢乘汽车；有的人不喜欢乘汽车。所以有的人不喜欢步行。（个体域取人类全体组成的集合）（4）每个旅客或者坐头等舱或者坐经济舱；每个旅客当且仅当他富裕时坐头等舱；有些旅客富裕但并非所有的旅客都富裕。因此有些旅客坐经济舱。（个体域取全体旅客组成的集合）

解：(2)证明：设P(x)：x 是个舞蹈者； Q(x)：x很有风度； S(x)：x是个学生； a：王华

上述句子符号化为：

前提：x(P(x)Q(x))、S(a)P(a)结论：x(S(x)Q(x))

（1）S(a)P(a)P（2）x(P(x)Q(x))P（3）P(a)Q(a)（4）P(a)（5）Q(a).（6）S(a)（7）S(a)Q(a)（8）x(S(x)Q(x)

]（3）命题符号化为：F(x)：x喜欢步行,G(x)：x喜欢骑自行车，H(x)：x喜欢坐汽车。

US（2）T（1）I T（3）（4）I T（1）I T（5）（6）I EG（7）

前提：x(F(x)G(x))，x(G(x)H(x))，x(H(x))

结论：x(F(x)).证明：(1)x(H(x))P(2)H(c)ES(1)(3)x(G(x)H(x))

P(4)G(c)H(c)US(3)(5)G(c)T(2)(4)I(6)x(F(x)G(x))

P(7)F(c)G(c)US(6)(8)F(c)T(5)(7)I(9)x(F(x))

EG(8)

（4）命题符号化为：F(x)：x坐头等舱, G(x)：x坐经济舱，H(x)：x富裕。

前提：x(F(x)G(x))，x(F(x)H(x))，x(H(x))，x(H(x))

结论：x(G(x)).证明：(1)x(H(x))P(2)H(c)ES(1)(3)x(F(x)H(x))

P(4)F(c)H(c)US(3)(5)F(c)T(2)(4)I(6)x(F(x)G(x))

P

(7)F(c)G(c)US(6)(8)G(c)T(5)(7)I(9)x(G(x))

EG(8)

5.令谓词P(x)、Q(x)、R(x)和S(x)分别表示“x是婴儿”，表示“x的行为符合逻辑”、“x能管理鳄鱼”和“x被人轻视”，个体域为所有人的集合。用P(x)、Q(x)、R(x)、S(x)、量词和逻辑联接词符号化下列语句。

（1）婴儿行为不合逻辑。（2）能管理鳄鱼的人不被人轻视。（3）行为不合逻辑的人被人轻视。

（4）婴儿不能管理鳄鱼。

请问，能从（1）、（2）和（3）推出（4）吗？若不能，请写出（1）、（2）和（3）的一个有效结论，并用演绎推理法证明之。解：（1）x(P(x)Q(x))

（2）x(R(x)S(x))

（3）x(Q(x)S(x))

（4）x(P(x)R(x))能从（1）（2）（3）推出（4）。

证明：（1）

P(x)

（2）

x(P(x)Q(x))

（3）

Q(x))

（4）

x(Q(x)S(x))

（5）

S(x)

（6）

x(R(x)S(x))

（7）

R(x)

（8）

x(P(x)R(x))

前提假设

前提引入

T 规则：(1)，(2)

P规则

T 规则：(3)，(4)P规则 拒取式 UG规则

第三篇：人工智能原理教案02章归结推理方法2.3谓词逻辑归结法基础

2.3 谓词逻辑归结法基础

由于谓词逻辑与命题逻辑不同，有量词、变量和函数，所以在生成子句集之前要对逻辑公式做处理，具体的说就是要将其转化为Skolem标准形，然后在子句集的基础上再进行归结，虽然基本的归结的基本方法都相同，但是其过程较之命题公式的归结过程要复杂得多。

本节针对谓词逻辑归结法介绍了Skolem标准形、子句集等一些必要的概念和定理。

2．3．1 Skolem 标准形 Skolem标准形的定义：

前束范式中消去所有的存在量词，则称这种形式的谓词公式为Skolem标准形，任何一个谓词公式都可以化为与之对应的Skolem标准形。但是，Skolem标准形不唯一。

前束范式：A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。

Skolem标准形的转化过程为，依据约束变量换名规则，首先把公式变型为前束范式，然后依照量词消去原则消去或者略去所有量词。具体步骤如下：

将谓词公式G转换成为前束范式

前束范式的形式为：

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)

即： 把所有的量词都提到前面去。

注意：由于所有的量词的辖域都延伸到公式的末端，即，最左边量词将约束表达式中的所有同名变量。所以将量词提到公式最前端时存在约束变量换名问题。要严守规则。

约束变量换名规则：

(Qx)M（x）（Qy）M（y）

(Qx)M（x,z）（Qy）M（y,z）

量词否定等值式：

～(x)M（x）（y）～ M（y）

～(x)M（x）（y）～ M（y）

量词分配等值式：

(x)(P（x）∧Q（x）)(x)P（x）∧(x)Q（x）

(x)(P（x）∨ Q（x）)(x)P（x）∨(x)Q（x）

消去量词等值式：设个体域为有穷集合（a1, a2, …an）

(x)P（x）P（a1）∧ P（a2）∧ …∧ P（an）

(x)P（x）P（a1）∨ P（a2）∨ … ∨ P（an）

量词辖域收缩与扩张等值式：

(x)(P（x）∨ Q)(x)P（x）∨ Q

(x)(P（x）∧ Q)(x)P（x）∧ Q

(x)(P（x）→ Q)(x)P（x）→ Q

(x)(Q → P（x）)Q →(x)P（x）

(x)(P（x）∨ Q)(x)P（x）∨ Q

(x)(P（x）∧ Q)(x)P（x）∧ Q

(x)(P（x）→ Q)(x)P（x）→ Q

(x)(Q → P（x）)Q →(x)P（x）消去量词

量词消去原则：

1)消去存在量词“"，即，将该量词约束的变量用任意常量（a, b等）、或全称变量的函数(f(x), g(y)等)代替。如果存在量词左边没有任何全称量词，则只将其改写成为常量；如果是左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数。

2)略去全程量词”“，简单地省略掉该量词。

Skolem 定理：

谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。

注意：公式G的SKOLEM标准形同G并不等值。例题2-2

将下式化为Skolem标准形：

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

＝(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)P(a, x, y)∧(y)(～Q(y, b)∧～R(x)))

＝(x)((y)P(a, x, y)∧(z)(～Q(z, b)∧～R(x)))

=(x)(y)(z)(P(a, x, y)∧～Q(z, b)∧～R(x))

由此得到前述范式

第五步，消去”“（存在量词），略去”“全称量词

消去(y)，因为它左边只有(”x)，所以使用x的函数f(x)代替之，这样得到：

(x)(z)(P(a, x, f(x))∧～Q(z, b)∧～R(x))

消去(z)，同理使用g(x)代替之，这样得到：

(x)(P(a, x, f(x))∧～Q(g(x), b)∧～R(x))

则，略去全称变量，原式的Skolem标准形为：

P(a, x, f(x))∧～Q(g(x), b)∧～R(x)2.3.2子句集

文字：不含任何连接词的谓词公式。

子句：一些文字的析取（谓词的和）。

子句集：所有子句的集合

对于任一个公式G，都可以通过Skolem标准形，标准化建立起一个子句集与之相对应。因为子句不过是一些文字的析取，是一种比较简单的形式，所以对G的讨论就用对子句集S的讨论来代替，以便容易处理。

子句集S可由下面的步骤求取：

1.谓词公式G转换成前束范式

2.消去前束范式中的存在变量，略去其中的任意变量，生成SKOLEM标准形

3.将SKOLEM标准形中的各个子句提出，表示为集合形式

教师提示：为了简单起见，子句集生成可以理解为是用“，”取代SKOLEM标准形中的“Λ”，并表示为集合形式。

注意：SKOLEM标准形必须满足合取范式的条件。即，在生成子句集之前逻辑表达式必须是各“谓词表达式”或“谓词或表达式”的与。定理

谓词表达式G是不可满足的当且仅当 其子句集S是不可满足的

公式G与其子句集S并不等值，但它们在不可满足的意义下是一致的。因此如果要证明A1∧A2∧A3→B，只需证明G＝ A1∧A2∧A3∧～B的子句集是不可满足的，这也正是引入子句集的目的。

注意：公式G和子句集S虽然不等值，但是它们的之间一般逻辑关系可以简单的说明为：G真不一定S真，而S真必有G真，即，S G。在生成SKOLEM标准形时将存在量词用常量或其他变量的函数代替，使得变量讨论的论域发生了变化，即论域变小了。所以G不能保证S真。定理的推广

对于形如G = G1Λ G2Λ G3Λ …Λ Gn 的谓词公式，G的子句集的求取过程可以分解成几个部分单独处理。如果Gi的子句集为Si，则

有 S' = S1 ∪ S2 ∪ S3 ∪ …∪ Sn，虽然G的子句集不为S'，但是可以证明：

SG 与S1 ∪ S2 ∪ S3 ∪ …∪Sn在不可满足的意义上是一致的。

即SG 不可满足 S1 ∪ S2 ∪S3 ∪ …∪ Sn不可满足

第四篇：人工智能原理教案02章 归结推理方法2.3 谓词逻辑归结法基础

2.3 谓词逻辑归结法基础

由于谓词逻辑与命题逻辑不同，有量词、变量和函数，所以在生成子句集之前要对逻辑公式做处理，具体的说就是要将其转化为Skolem标准形，然后在子句集的基础上再进行归结，虽然基本的归结的基本方法都相同，但是其过程较之命题公式的归结过程要复杂得多。

本节针对谓词逻辑归结法介绍了Skolem标准形、子句集等一些必要的概念和定理。

2．3．1 Skolem 标准形

Skolem标准形的定义：

前束范式中消去所有的存在量词，则称这种形式的谓词公式为Skolem标准形，任何一个谓词公式都可以化为与之对应的Skolem标准形。但是，Skolem标准形不唯一。

前束范式：A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。

Skolem标准形的转化过程为，依据约束变量换名规则，首先把公式变型为前束范式，然后依照量词消去原则消去或者略去所有量词。具体步骤如下：

将谓词公式G转换成为前束范式

前束范式的形式为：

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)

即： 把所有的量词都提到前面去。

注意：由于所有的量词的辖域都延伸到公式的末端，即，最左边量词将约束表达式中的所有同名变量。所以将量词提到公式最前端时存在约束变量换名问题。要严守规则。

约束变量换名规则：

(Qx)M（x）

(Qx)M（x,z）

（Qy）M（y）

（Qy）M（y,z）

量词否定等值式：

～(x)M（x）

～(x)M（x）

量词分配等值式：

(x)(P（x）∧Q（x）)

(x)(P（x）∨ Q（x）)

(x)P（x）∧(x)Q（x）(x)P（x）∨(x)Q（x）

（y）～ M（y）

（y）～ M（y）

消去量词等值式：设个体域为有穷集合（a1, a2, …an）

(x)P（x）

(x)P（x）

P（a1）∧ P（a2）∧ …∧ P（an）P（a1）∨ P（a2）∨ … ∨ P（an）

量词辖域收缩与扩张等值式：

(x)(P（x）∨ Q)

(x)(P（x）∧ Q)

(x)(P（x）→ Q)

(x)(Q → P（x）)

(x)P（x）∨ Q(x)P（x）∧ Q(x)P（x）→ Q Q →(x)P（x）

(x)(P（x）∨ Q)

(x)(P（x）∧ Q)

(x)(P（x）→ Q)

(x)(Q → P（x）)

消去量词

量词消去原则：

(x)P（x）∨ Q(x)P（x）∧ Q(x)P（x）→ Q Q →(x)P（x）

1)消去存在量词“"，即，将该量词约束的变量用任意常量（a, b等）、或全称变量的函数(f(x), g(y)等)代替。如果存在量词左边没有任何全称量词，则只将其改写成为常量；如果是左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数。

2)略去全程量词”“，简单地省略掉该量词。

Skolem 定理：

谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。

注意：公式G的SKOLEM标准形同G并不等值。例题2-2

将下式化为Skolem标准形：

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

＝(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)P(a, x, y)∧(y)(～Q(y, b)∧～R(x)))

＝(x)((y)P(a, x, y)∧(z)(～Q(z, b)∧～R(x)))

=(x)(y)(z)(P(a, x, y)∧～Q(z, b)∧～R(x))

由此得到前述范式

第五步，消去”“（存在量词），略去”“全称量词

消去(y)，因为它左边只有(”x)，所以使用x的函数f(x)代替之，这样得到：

(x)(z)(P(a, x, f(x))∧～Q(z, b)∧～R(x))

消去(z)，同理使用g(x)代替之，这样得到：

(x)(P(a, x, f(x))∧～Q(g(x), b)∧～R(x))

则，略去全称变量，原式的Skolem标准形为：

P(a, x, f(x))∧～Q(g(x), b)∧～R(x)

2.3.2子句集

文字：不含任何连接词的谓词公式。

子句：一些文字的析取（谓词的和）。

子句集：所有子句的集合

对于任一个公式G，都可以通过Skolem标准形，标准化建立起一个子句集与之相对应。因为子句不过是一些文字的析取，是一种比较简单的形式，所以对G的讨论就用对子句集S的讨论来代替，以便容易处理。

子句集S可由下面的步骤求取：

1.谓词公式G转换成前束范式

2.消去前束范式中的存在变量，略去其中的任意变量，生成SKOLEM标准形

3.将SKOLEM标准形中的各个子句提出，表示为集合形式

教师提示：为了简单起见，子句集生成可以理解为是用“，”取代SKOLEM标准形中的“Λ”，并表示为集合形式。

注意：SKOLEM标准形必须满足合取范式的条件。即，在生成子句集之前逻辑表达式必须是各“谓词表达式”或“谓词或表达式”的与。

定理

谓词表达式G是不可满足的当且仅当 其子句集S是不可满足的

公式G与其子句集S并不等值，但它们在不可满足的意义下是一致的。因此如果要证明A1∧A2∧A3→B，只需证明G＝ A1∧A2∧A3∧～B的子句集是不可满足的，这也正是引入子句集的目的。

注意：公式G和子句集S虽然不等值，但是它们的之间一般逻辑关系可以简单的说明为：G真不一定S真，而S真必有G真，即，S G。在生成SKOLEM标准形时将存在量词用常量或其他变量的函数代替，使得变量讨论的论域发生了变化，即论域变小了。所以G不能保证S真。

定理的推广

对于形如G = G1Λ G2Λ G3Λ …Λ Gn 的谓词公式，G的子句集的求取过程可以分解成几个部分单独处理。如果Gi的子句集为Si，则

有 S' = S1 ∪ S2 ∪ S3 ∪ …∪ Sn，虽然G的子句集不为S'，但是可以证明：

SG 与S1 ∪ S2 ∪ S3 ∪ …∪Sn在不可满足的意义上是一致的。

即SG 不可满足

由上面的定理，我们对SG的讨论，可以用较为简单的S1 ∪ S2 ∪ S3 ∪ …∪ Sn来代替。为方便起见，也称S1 ∪ S2 ∪ S3 ∪ …∪ Sn为G的子句形，即：

S1 ∪ S2 ∪S3 ∪ …∪ Sn不可满足

SG＝S1 ∪ S2 ∪ S3 ∪ …∪ Sn。根据以上定理可对一个谓词表达式分而治之，化整为零，大大减少了计算复杂度。

例2－3

对所有的x,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？

用一阶逻辑表示这个问题，并建立子句集。

解：

这里我们首先引入谓词：

P(x, y)表示x是y的父亲

Q(x, y)表示x是y的祖父

ANS(x)表示问题的解答

于是有：

对于第一个条件，“如果y是x的父亲，z又是y的父亲，则z是x的祖父”，一阶逻辑表达式如下：

A1：(x)(y)(z)(P(x, y)∧P(y, z)→Q(x, z))

则把A1化为合取范式，进而化为Skolem标准形，表示如下：

S A1：～P(x ,y)∨～P(y, z)∨Q(x, z)

对于第二个条件：“每个人都有父亲”，一阶逻辑表达式如下：

A2：(y)(x)P(x, y)

化为Skolem标准形，表示如下：

S A2：P(f(y), x)

结论：某个人是它的祖父

B：(x)(y)Q(x, y)

否定后得到子句：

S～B：～Q(x, y)∨ANS(x)

则得到的相应的子句集为：{ S A1，S A2，S～B }

解毕。

第五篇：逻辑,

第三章复习

对当关系性质

1.矛盾关系：不可同真，不可同假。

2.反对关系：不可同真，可以同假。

3.下反对关系：不可同假，可以同真。

4.差等关系：上真下真，下假上假。

命题变形推理

换质法：两变两不变

1.变：变质、谓项变成矛盾概念；

2.不变：主、谓项位置不变、量不变。

换位法：一变一不变

1.变：主、谓项位置变。

2.不变：质不变。

3.前提中不周延的项在结论中不得周延。

三段论

1.三段论规则

2.三段论的格式

3.周延性。

4.三段论有效性的检验

5.省略三段论的检验

6.三段论证明

例：一组三段论包括两个有效三段论，它们的大前提和结论都不同真不同假。请列出所有符合上述条件的有效三段论形式（以组为单位，两个三段论为一组），并写出推导过程。

证明：

1.结论与大前提都是矛盾关系。为AO或EI。

2.结论为AO，结论为A的是第一格AAA式。

结论为O的，大前提一定是MOP，小前提是MAS，第一格AAA式与第三格OAO。

3.结论是EI，结论为I的，其大前提为MIP或PIM,小前提为MAS。

结论为E的，大前提为PEM或MEP，小前提为SAM。符合条件的有： 第一格EAE式与第三格IAI式；第一格EAE式与与第四格IAI式；第二格EAE式与第三格IAI式；第二格EAE式与第四格IAI式。

共五组