在日常学习、工作或生活中，大家总少不了接触作文或者范文吧，通过文章可以把我们那些零零散散的思想，聚集在一块。相信许多人会觉得范文很难写？下面我给大家整理了一些优秀范文，希望能够帮助到大家，我们一起来看一看吧。

谓词逻辑推理篇一

由于谓词逻辑与命题逻辑不同，有量词、变量和函数，所以在生成子句集之前要对逻辑公式做处理，具体的说就是要将其转化为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不可满足

谓词逻辑推理篇二

习题二

(参考答案)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

③⑦假言推理

⑤⑧析取三段论

⑨附加规则

⑩置换规则

谓词逻辑推理篇三

谓词逻辑习题

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规则

谓词逻辑推理篇四

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式。

共五组