谓词逻辑

主讲教师

李 辉

谓词的概念和表示

命题逻辑以原子命题为基本单位, 研究复合命题之间的逻辑关系和推理关系. 但是, 有些推理关系用命题逻辑难以确切表达.

典型的例子是苏格拉底三段论:

  1. 所有的人都是会死的,

  2. 苏格拉底是人,

  3. 所以苏格拉底是会死的.

显然, 结论是前提合理的结果, 即推理是正确的.

将三段论推理符号化, 得到:

  • \(p\): 所有的人都是会死的

  • \(q\): 苏格拉底是人

  • \(r\): 苏格拉底是会死的

前提: \(p\), \(q\), 结论: \(r\). 需证明\({p, q}{\vDash}r\)是有效的.

注意:各命题的逻辑关系不是体现在原子命题之间, 而是体现在构成原子命题内部的组成部分之间, 即体现在命题结构的更深层次上.

\(p\)是对所有人情况的判断, 其中也包括\(q\). \(q\)和\(r\)都是关于苏格拉底一个人的判断. 这些逻辑关系在命题表达时被淹没了.

在研究某些推理时, 有必要对原子命题作进一步分析, 分解出其中的各个成分: 个体, 谓词和量词等.

研究它们的形式结构、逻辑关系和推理规则, 这些正是谓词逻辑(一阶逻辑)的研究内容.

个体词和谓词

定义: 表示主体或客体成分的词称为个体(词). 个体可以是具体的或是抽象的.

例: 天安门, 熊猫, 思想, 2等都是个体.

个体常元: 表示具体的、确定的个体的词. 用小写字母\(a, b, c, {\cdots}\)等表示.

个体变元: 表示不确定的个体的词. 用小写字母\(x, y, z, {\cdots}\)等表示.

在命题中所出现的每个个体都是个体常元.

  • 我是人民教师.

  • 小明喜欢猫.

定义: 表示一个个体性质或多个个体之间关系的词称为谓词.

表示一个个体性质的谓词称为一元谓词, 表示\(n\)个个体之间关系的谓词称为\(n\)元谓词.

  • “我是人民教师” 表示一个个体性质.

  • “周三和周五之间有周四”表示多个个体之间关系.

谓词也有常元和变元之分.

谓词常元: 表示具体性质或具体关系的谓词

谓词变元: 表示抽象或泛指的性质或关系的谓词

谓词一般用大写英文字母\(P, Q, R{\cdots}\)等来表示.

定义: 一个原子命题用一个谓词\(P\)和\(n\)个有序的个体常元\(a_{1}, a_{2}, {\cdots}, a_{n}\)表示成\(P(a_{1}, a_{2}, {\cdots}, a_{n})\), 称它为该原子命题的谓词形式.

 

在谓词逻辑里, 如何符号化一个原子命题呢？

2是偶数, 可以符号化为\(P(a)\), 其中\(P:{\cdots}\)是偶数, \(a:2\).

小王喜欢小花猫, 可以符号化为: \(F(a, b)\), 其中\(F\): \({\cdots}\)喜欢\({\cdots}\), \(a\): 小王, \(b\): 小花猫.

上海位于北京和广州之间, 可以符号化为: \(G(a, b, c)\), 其中\(G\): \({\cdots}\)位于\({\cdots}\)和\({\cdots}\)之间, \(a\): 上海, \(b\): 北京, \(c\): 广州.

张三是大学生, 李四是大学生.

(命题逻辑中符号化) \(p\): 张三是大学生, \(q\): 李四是大学生.

(谓词逻辑中符号化) \(S(a)\): 张三是大学生, \(S(b)\): 李四是大学生. 其中\(S\): \({\cdots}\)是大学生, \(a\): 张三, \(b\): 李四.

在命题逻辑符号化的结果中, \(p\)和\(q\)没有任何联系. 而在谓词逻辑符号化的结果中, \(S(a)\)和\(S(b)\)反映出了两者同是大学生.

一个给定的谓词, 可以与不同的个体常元构成不同的命题.

张三是大学生, 李四是大学生.

这是两个不同的命题, 但它们有一个共同的表现形式, 即\(S(x)\), \(x\)是个体变元. 当\(x\)取\(a\)或\(b\)时就分别表示上述两个命题.

在这里\(S(x)\)只是某些具体命题的共性抽象, 本身不代表任何命题.

定义: 一个由谓词\(P\)和\(n\)(\(n{\geq}1\))个个体变元\(x_{1}, x_{2}, {\cdots}, x_{n}\)组成的符号串\(P(x_{1}, x_{2}, {\cdots}, x_{n}\))称为\(n\)元谓词.

\(n=1\), 一元谓词, 例: \(P(x):x\)喜欢动物.

\(n=2\), 二元谓词, 例: \(Q(x, y):x\)和\(y\)是同学.

\(n=3\), 三元谓词, 例: \(R(x, y, z):x+y=z\).

有时将原子命题的谓词形式称为0元谓词, \(P(a), F(a, b), G(a, b, c)\)等都是0元谓词.

由于命题逻辑中的命题均可表示成0元谓词, 所以可以将命题看作是特殊的谓词.

个体域和量词

\(n\)元谓词本身不是命题, 只有其中的所有个体变元用特定的个体取代, 有确定的值后, 才成为一个命题. 个体变元可用哪些特定个体取代, 可在什么范围内取值, 对其真值有很大的影响.

个体变元取值的范围称为个体域或论域.

\(P(x, y):x^{2}+y^{2}=0\)

设\(x\)和\(y\)的个体域均为全体正数, 则对\(x, y\)的任何取值, \(P(x, y)\)均为假;

设\(x\)和\(y\)的个体域均为全体实数, 则除\(P(0, 0)\)是一个真命题之外, 其余情形均是假命题.

\(S(x)\): \(x\)是化工大学学生

若\(x\)的个体域为化工大学全体师生, 则\(x\)的取值为某个学生时, \(S(x)\)为真命题, 其余取值\(S(x)\)为假命题.

若\(x\)的个体域为化工大学全体学生, 则\(x\)任一取值\(S(x)\)均为真命题.

在命题中除了个体词和谓词外, 有时还会出现一些表示数量的词, 这些词称为量词.

在谓词逻辑中, 量词被分为三种:

  1. 全称量词: 表示“所有”, “一切”和“任意的”等数量的词, 用符号\(\forall\)表示

  2. 存在量词: 表示“存在一些”, “有一个”和“至少有一个”等数量的词, 用符号\(\exists\)表示

  3. 存在唯一量词: 表示“存在着唯一的”和“恰有一个”等数量的词, 用符号\({\exists}!\)表示

量词\({\forall}\), \({\exists}\)和\({\exists}!\)不能单独使用.

还需引入一个个体变元(如\(x\))作为量词的指导变元置于量词之后, 形成\({\forall}x\), \({\exists}x\)和\({\exists}!x\)的形式, 分别表示“对于所有的\(x\)”, “存在至少一个\(x\)”和“恰有一个\(x\)”之意.

可以放到\(n\)元谓词之前作为其组成部分, 对个体变元在个体域中的取值作进一步的约束.

\({\forall}xP(x)\)表示个体域中的所有个体均满足P(x);

\({\exists}xQ(x)\)表示个体域中至少有一个个体满足Q(x);

\({\exists}!xR(x)\)表示个体域中恰有一个个体满足R(x).

将下列命题符号化, 要求分析出量词, 个体词和谓词.

  1. 所有的大学生都会说英语.

  2. 有一些大学生会说英语.

解:

(1)命题符号化为\({\forall}xE(x)\). 其中, \(x\)的个体域为全体大学生, \(E(x)\): \(x\)会说英语.

(2)命题符号化为\({\exists}xE(x)\). 其中, \(x\)的个体域为全体大学生, \(E(x)\): \(x\)会说英语.

  1. 凡自然数都是整数.

  2. 有些老虎是白色的.

  3. 存在着唯一的偶素数.

解:

(3)命题符号化为\({\forall}xI(x)\). 其中, \(x\)的个体域为自然数集合, \(I(x)\): \(x\)是整数.

(4)命题符号化为\({\exists}xW(x)\). 其中, \(x\)的个体域为所有的老虎, \(W(x)\): \(x\)是白色的.

(5)命题符号化为\({\exists}!xR(x)\). 其中, \(x\)的个体域为偶数集合, \(R(x)\): \(x\)是素数.

定义: 一个命题函数中所有个体的论域合在一起构成的论域, 称为命题函数的全总论域.

教师的年龄比学生大.

其中, \(P(x, y):x\)的年龄比\(y\)大, \(x\)的个体域为全体教师的集合, \(y\)的个体域为全体学生的集合. 全总论域:教师和学生集合.

一般约定, 当一个命题没有指明其个体的个体域时, 可把全总论域作为其个体域.

对每个个体变元的真正取值范围, 可使用一个谓词来加以限制, 称之为特性谓词.

同样的例子, 使用特定谓词可表达如下：

  1. 所有的大学生都会说英语. \({\forall}x(S(x){\rightarrow}E(x))\), \(S(x):x\)是大学生, \(E(x):x\)会说英语.

  2. 有一些大学生会说英语. \({\exists}x(S(x){\wedge}E(x))\), \(S(x):x\)是大学生, \(E(x):x\)会说英语.

  3. 凡自然数都是整数. \({\forall}x(N(x){\rightarrow}I(x))\), \(N(x):x\)是自然数, \(I(x):x\)是整数.

  4. 有些老虎是白色的. \({\exists}x(M(x){\wedge}W(x))\), \(M(x):x\)是老虎, \(W(x):x\)是白色的.

  5. 存在着唯一的偶素数. \({\exists}!x(Q(x){\wedge}R(x))\), \(Q(x):x\)是偶数, \(R(x):x\)是素数.

给\(n\)元谓词加上量词, 称为\(n\)元谓词的量化.

在含有量词和特性谓词的谓词公式中, 量词与相应特性谓词的搭配是:全称量词后应跟一个条件式, 特性谓词作为前件; 存在量词后应跟一个合取式，特性谓词作为一合取项. 即:

  • “所有\(A\)都是\(B\)”形式的命题表示为\({\forall}x(A(x){\rightarrow}B(x))\)

  • “有一些\(A\)是\(B\)”形式的命题表示为\({\exists}x(A(x){\wedge}B(x))\)

已知\(L(x):x+3>7\), 设个体域分别为:

(1)\(\{-3, -2, -1, 0, 1, 2\}\) (2)\(\{-5, 0, 3, 5, 6\}\) (3)\(\{10, 15, 24, 30\}\)

考察命题\({\forall}xL(x)\)及\({\exists}xL(x)\)的真值.

解: 当个体域为(1)时, 命题\({\forall}xL(x)\)为\(F\), \({\exists}xL(x)\)为\(F\); 为(2)时, 命题\({\forall}xL(x)\)为\(F\), \({\exists}xL(x)\)为\(T\); 为(3)时, 命题\({\forall}xL(x)\)为\(T\), \({\exists}xL(x)\)为\(T\).

谓词公式

\(P\)是\(n\)元谓词, \(x_{1}, x_{2}, {\cdots}, x_{n}\)是个体变元或个体常元, 则\(P(x_{1}, x_{2}, {\cdots}, x_{n})\)称为原子谓词公式.

特别地, 当\(n=0\)时, 原子谓词公式\(P(x_{1}, x_{2}, {\cdots}, x_{n})\)就是命题常元或命题变元\(P\), 因此命题常元和命题变元也是原子谓词公式.

复合谓词公式由量词和联结词将原子谓词公式联结组成.

谓词公式递归定义如下:

  1. 原子谓词公式是谓词公式;

  2. 如果\(A\)是谓词公式, 则\({\lnot}A\)也是谓词公式;

  3. 如果\(A, B\)是谓词公式, 则\(A{\wedge}B, A{\vee}B, A{\rightarrow}B\)和\(A{\leftrightarrow}B\)也是谓词公式;

  4. 如果\(A\)是谓词公式, \(x\)是个体变元, 则\({\forall}xA\)和\({\exists}xA\)也是谓词公式;

  5. 有限次使用规则(1)-(4)所得到的由原子谓词公式, 逻辑联结词, 量词和圆括号组成的符号串才是谓词公式.

例: \[{\forall}x((R(x){\rightarrow}P(x)){\wedge}S(x))\] \[{\forall}x(P(x, y){\rightarrow}{\exists}yQ(y))\] \[{\exists}x{\exists}y(D(y){\vee}E(x, y)){\rightarrow}{\forall}xC(x)\] \[P(x, y, z)\] \[P(a, 2){\wedge}Q(x)\] \[{\exists}yL(x, y){\rightarrow}R(x)\] 等都是谓词公式.

命题符号化

把一个用自然语言描述的命题表示成谓词公式的形式, 称为谓词逻辑中命题的符号化(命题的翻译).

设个体域为实数集合, 试将下列命题符号化.

  1. 任一实数或者是有理数, 或者是无理数.

  2. 对于每个实数\(x\)都存在一个实数\(y\), 使\(x+y=0\).

解:

  1. 令\(U(x)\): \(x\)是有理数, \(V(x)\): \(x\)是无理数. 命题符号化为: \({\forall}x(U(x){\vee}V(x))\).

  2. 令\(E(x, y)\): \(x+y=0\). 命题符号化为: \({\forall}x{\exists}yE(x, y)({\forall}x{\exists}y(x+y=0))\).

谓词逻辑中命题翻译一般经过以下几个步骤:

  1. 找出命题中各原子命题和联结词.

  2. 分解出每个原子命题的个体, 谓词和量词.

  3. 确定每个个体的个体域, 若在全总论域中讨论给出相应的特性谓词.

  4. 按照谓词公式的表示规则将命题翻译出来.

试将下列命题符号化:

  1. 每列(量词)火车(个体)都比(谓词一部分)某些(量词)汽车快(谓词另一部分).

解: \(F(x)\): \(x\)是火车, \(G(y)\): \(y\)是汽车, \(H(x, y)\): \(x\)比\(y\)快.

符号化: \({\forall}x(F(x){\rightarrow}{\exists}y(G(y){\wedge}H(x, y)).\)

  1. 某些汽车比所有火车快.

解: \(F(x)\): \(x\)是火车, \(G(y)\): \(y\)是汽车, \(H(x, y)\): \(x\)比\(y\)快.

符号化: \({\exists}y(G(y){\wedge}{\forall}x(F(x){\rightarrow}H(y, x))\)

  1. 不存在比一切数都大的数.

解: \(F(x)\): \(x\)是数, \(G(x, y)\): \(x\)比\(y\)大.

符号化: \({\lnot}{\exists}x(F(x){\wedge}{\forall}y(F(y){\rightarrow}G(x, y))\)

  1. 有种液体可以溶解所有金属.

解: \(F(x)\): \(x\)是液体, \(G(y)\): \(y\)是金属, \(H(x, y)\): \(x\)可以溶解\(y\).

符号化: \({\exists}x(F(x){\wedge}{\forall}y(G(y){\rightarrow}H(x, y))\).

变元的约束

给定谓词公式\(A\), 其中形如\({\forall}xP(x)\)或\({\exists}xP(x)\)的部分, 称为谓词公式\(A\)的\(x\)约束部分, \(P(x)\)称为相应量词\({\forall}\)或\({\exists}\)的辖域.

\(x\)在谓词公式\(A\)的\(x\)约束部分任何出现都称为\(x\)的约束出现, 并称\(x\)为约束变元.

在谓词公式中当\(x\)的出现不是约束出现时, 称\(x\)的出现是自由出现, 称自由出现的变元为自由变元.

指出下列谓词公式中各量词的辖域和变元约束的情况.

  1. \({\exists}x(P(x){\wedge}Q(x))\)

解:\({\exists}x\)的辖域是\(P(x){\wedge}Q(x), x\)是约束变元.

  1. \({\forall}x(P(x){\rightarrow}{\exists}yQ(x, y, z)){\wedge}R(x)\)

解: \({\forall}x\)的辖域是\(P(x){\rightarrow}{\exists}yQ(x, y, z)\), \({\exists}y\)的辖域是\(Q(x, y, z)\), \(x\)和\(y\)是约束变元. \(z\)是自由变元, \(R(x)\)中的\(x\)是自由变元.

在整个谓词公式中, \(x\)即是约束出现又是自由出现, \(y\)为约束出现, \(z\)为自由出现.

  1. \({\exists}x{\forall}y(P(x, y){\rightarrow}(Q(x){\wedge}R(y)))\)

解: \({\exists}x\)的辖域是\({\forall}y(P(x, y){\rightarrow}(Q(x){\wedge}R(y)))\), \({\forall}y\)的辖域是\(P(x, y){\rightarrow}(Q(x){\wedge}R(y))\), \(x\)和\(y\)是约束变元.

在整个谓词公式中, \(x\)和\(y\)为约束出现.

  1. \({\forall}x(P(x, y){\wedge}Q(y)){\rightarrow}{\exists}yR(x, y)\)

解: \({\forall}x\)的辖域为\(P(x, y){\wedge}Q(y)\), \(x\)是约束变元, \(y\)是自由变元. \({\exists}y的辖域是R(x, y)\), \(x\)是自由变元, \(y\)是约束变元.

在整个谓词公式中, \(x\)和\(y\)为既是自由出现又是约束出现.

  1. \({\forall}xP(y, z){\rightarrow}{\exists}yQ(y)\)

解: \({\forall}x\)的辖域是\(P(y, z)\), \(y\)和\(z\)是自由变元. \({\exists}y\)的辖域是\(Q(y), y\)是约束变元.

在整个谓词公式中, \(z\)为自由出现, \(y\)是自由出现也是约束出现.

在一个谓词公式中, 个体变元即可作为自由变元, 又可作为约束变元, 也可同时作为自由变元和约束变元出现.

一个变元在一个谓词公式中可能既约束出现又自由出现, 为避免由此引起的混乱, 可对约束变元进行换名, 使每个个体变元在一个谓词公式中只以一种形式出现, 或是自由出现或是约束出现.

一个约束变元在谓词公式中所使用的名称符号是不重要的, 所以变元使用符号的更改并不改变谓词公式的含义.

  • \({\forall}xP(x)\)与\({\forall}yP(y)\)具有相同的意义

  • \({\exists}xQ(x)\)与\({\exists}yQ(y)\)具有相同的意义

约束变元的换名规则:

  1. 对于约束变元的换名, 其换名范围是量词辖域中的某个约束出现的个体变元, 谓词公式中的其他部分不变.

  2. 换名时要换成在辖域中未曾出现的符号, 最好是谓词公式中未出现过的符号.

对谓词公式: \[({\forall}x(P(x){\rightarrow}(R(x){\vee}Q(x))){\wedge}{\exists}xR(x)){\rightarrow}{\exists}zS(x, z)\] 的约束变元换名.

可换名为: \[({\forall}y(P(y){\rightarrow}(R(y){\vee}Q(y))){\wedge}{\exists}wR(w)){\rightarrow}{\exists}zS(x, z)\]

对以下谓词公式换名: \[{\forall}x(P(x){\rightarrow}R(x, y)){\wedge}Q(x, y)\] 可换名为:\[{\forall}z(P(\boxed{z}){\rightarrow}R(\boxed{z}, y)){\wedge}Q(x, y)\] 但不能换成: \[{\forall}y(P(y){\rightarrow}R(y, y)){\wedge}Q(x, y)\] \[{\forall}z(P(z){\rightarrow}R(x, y)){\wedge}Q(x, y)\]

对于谓词公式中的自由变元, 也允许换名, 称之为自由变元代入.

自由变元的代入规则:

  1. 对于谓词公式中的自由变元可以代入, 且代入时需对该自由变元的所有出现同时进行代入.

  2. 用来代入的可以是个体常元和个体变元, 代入时所选用的符号应是原谓词公式中没有出现的.

对于谓词公式 \[({\forall}x(R(x, y){\vee}S(x)){\rightarrow}Q(x)){\wedge}{\exists}zP(x, y, z)\] 可将自由变元\(x\)代入自由变元\(w\), 得到谓词公式: \[({\forall}x(R(x, y){\vee}S(x)){\rightarrow}Q(w)){\wedge}{\exists}zP(w, y, z)\]

但不能代入为: \[({\forall}x(R(x, y){\vee}S(x)){\rightarrow}Q(w)){\wedge}{\exists}zP(x, y, z)\] 因为违背代入规则(1).

或代入为:\[({\forall}x(R(x, y){\vee}S(x)){\rightarrow}Q(y)){\wedge}{\exists}zP(y, y, z)\] 因为违背代入规则(2).

量词对变元的约束, 与量词出现的次序有关, 量词出现的次序一般不可随意更改.

  • \({\forall}x{\exists}y(x+y=0)\) 表示”对于任意的实数\(x\), 均存在实数\(y\), 使得\(x+y=0\)“, 这是一个真命题.

  • \({\exists}y{\forall}x(x+y=0)\) 表示”存在实数\(y\), 使对于任意的实数\(x\)均有\(x+y=0\)“, 这是一个假命题.

它们具有不同的意义.

谓词公式的解释

一个谓词公式仅仅由一些抽象符号组成. 只有在对其进行解释后才有真正的意义, 对其赋值后才有真值.

例如: \(S(x){\wedge}{\exists}xQ(x)\)本身是没有任何意义的.

解释包括: 定义个体域, 说明谓词符号和运算符号的具体含义等, 是抽象符号与个体域上的具体性质、关系、运算间的映射, 常用\(I\)表示.

同样的谓词公式, 在不同的解释下所具有的意义是不同的.

当给定谓词公式的一种解释后, 对公式中的个体变元用其个体域中确定的个体代入, 命题变元用确定的命题代入, 称为对谓词公式的赋值.

一个谓词公式一经赋值, 就成为具有确定真值的命题.

给定以下解释\(I\), 试讨论\(S(x), {\exists}xS(x), S(x){\wedge}{\exists}xS(x)\)的真值.

  1. \(I_1\): 个体域\(D_{1}=\{3, 4\}\), \(S(x)\)表示\(x\)是素数.

  2. \(I_2\): 个体域\(D_{2}=\{3, 4\}\), \(S(x)\)表示\(x\)是偶数.

  3. \(I_3\): 个体域\(D_{3}=\{3, 5\}\), \(S(x)\)表示\(x\)是素数.

  4. \(I_4\): 个体域\(D_{4}=\{3, 5\}\), \(S(x)\)表示\(x\)是偶数.

\(S(x)\), \({\exists}xS(x)\), \(S(x){\wedge}{\exists}xS(x)\)的真值表:

  \[ \begin{array}{ccccc} 解释 & x & S(x) & {\exists}xS(x) & S(x){\wedge}{\exists}xS(x) \\ I_1 & 3 & T & T & T \\ I_1 & 4 & F & T & F \\ I_2 & 3 & F & T & F \\ I_2 & 4 & T & T & T \\ I_3 & 3 & T & T & T \\ I_3 & 5 & T & T & T \\ I_4 & 3 & F & F & F \\ I_4 & 5 & F & F & F \\ \end{array} \]

给定谓词公式\(A\)的解释\(I\), \(x_{1}, x_{2}, {\cdots}, x_{n}\)是\(A\)中出现的个体变元,

如果\(x_{1}, x_{2}, {\cdots}, x_{n}\)赋值为\(t_{1}, t_{2}, {\cdots}, t_{n}\)时\(A\)为真, 则称\(A\)在\(t_{1}, t_{2}, {\cdots}, t_{n}\)处为真;

当\(x_{1}, x_{2}, {\cdots}, x_{n}\)在解释\(I\)中的每个赋值\(A\)均为真, 则称\(A\)在解释\(I\)下为真.

  • 给定解释\(I\): 个体域\(D=\{3, 4, 5\}\), \(S(x)\): \(x\)大于2, \(T(x)\): \(x\)小于6, 则\(S(x){\wedge}T(x)\): 在\(x=3\), \(x=4\), \(x=5\)均为真, 所以\(S(x){\wedge}T(x)\)在解释\(I\)下为真.

  • 给定解释\(I\): 个体域\(D=\{-5, -4, 1, 2\}\) \(Q(x)\): \(x\)大于3, 则: \(Q(x)\)在\(-5, -4, 1, 2\)处均为假. \(Q(x)\)在解释\(I\)下为假.

  • 给定解释\(I\): 个体域\(D_x=\{1, 2, 3\}, D_y=\{1, 4, 5\}\), \(Q(x, y)\): \(x<y\), 则: \(Q(x, y)\)在{1, 1}, {2, 1}, {3, 1}处为假, 其余为真.

若谓词公式\(A\)在每一解释\(I\)下均为真, 则称\(A\)为永真式.

若谓词公式\(A\)在每一解释\(I\)下均为假, 则称\(A\)为永假式; 否则称\(A\)为可满足式.

 

\(P(x){\vee}{\lnot}P(x)\)是永真式, \(Q(x){\wedge}{\lnot}Q(x)\)是永假式, \(P(x){\vee}{\exists}xQ(x)\)是可满足式.

谓词公式: \[({\forall}xF(x){\rightarrow}G(x)){\rightarrow}({\forall}xF(x){\rightarrow}{\forall}xG(x))\]是否为永真式？

 

解: 设个体域\(D\)={2, 4, 6, 8}; \(F(x):x\)能被2整除; \(G(x):x\)能被4整除.

则\({\forall}xF(x)\)的真值为\(T\), \({\forall}xG(x)\)的真值为\(F\), 故 \({\forall}xF(x){\rightarrow}{\forall}xG(x)\)的真值为\(F\).

G(4)的真值为\(T\), 因此有\({\forall}xF(x){\rightarrow}G(4)\)的真值为\(T\).

故\(({\forall}xF(x){\rightarrow}G(4)){\rightarrow}({\forall}xF(x){\rightarrow}{\forall}xG(x))\)的真值为\(F\).

于是, \(({\forall}xF(x){\rightarrow}G(x)){\rightarrow}({\forall}xF(x){\rightarrow}{\forall}xG(x))\)不是永真式.

谓词公式\({\forall}xA(x){\rightarrow}A(y)\)是否为永真式？

任意给定个体域\(D\), 假定在该解释下\({\forall}xA(x)\)为真, 则对于任意\(d{\in}D\), 均有\(A(d)\)为真, 因此\(A(y)\)为真.

故\({\forall}xA(x){\rightarrow}A(y)\)为永真式.

 

谓词公式\({\forall}x(P(x){\rightarrow}Q(x))\)是否为可满足式？

定义解释\(I\): 个体域\(D\)上为整数集, \(P(x):x\)是整数, \(Q(x):x\)是有理数.

在解释\(I\)下, \({\forall}x(P(x){\rightarrow}Q(x))\)为真, 所以\({\forall}x(P(x){\rightarrow}Q(x))\)是可满足式.

等价式和永真蕴含式

设\(A\)和\(B\)是谓词公式, 若\(A{\leftrightarrow}B\)为永真式, 则称\(A\)和\(B\)是等价(值)的, 记为\(A{\Leftrightarrow}B\).

\(A{\Leftrightarrow}B\)表明在任意的解释和赋值下, \(A\)与\(B\)都具有相同的值.

  • \({\forall}x{\lnot}{\lnot}P(x){\Leftrightarrow}{\forall}xP(x).\)

设\(A\)和\(B\)是谓词公式, 若\(A{\rightarrow}B\)为永真式, 则称\(A\)永真蕴含\(B\), 记为\(A{\Rightarrow}B.\)

\(A{\Rightarrow}B\)表明在任意的解释下, 一切使\(A\)为真的赋值均使\(B\)为真.

  • \({\exists}xP(x){\Rightarrow}{\exists}x{\lnot}{\lnot}P(x).\)
  1. 命题演算中永真式的推广

由于谓词演算中允许使用命题常元和命题变元, 因而谓词公式中仍可含有命题公式, 其中永真的命题公式在谓词演算中仍然是永真式.

在命题演算的永真式中, 若将其中的同一命题变元改为同一谓词公式时, 不会影响其永真性, 即可得到谓词演算中的永真式.

命题演算的等价式: \[{\lnot}(A{\vee}B){\Leftrightarrow}({\lnot}A{\wedge}{\lnot}B)\] 若用\({\forall}xP(x)\)代替\(A\), \({\exists}xQ(x)\)代替\(B\), 就得到谓词演算的等价式: \[{\lnot}({\forall}xP(x){\vee}{\exists}xQ(x)){\Leftrightarrow}({\lnot}{\forall}xP(x){\wedge}{\lnot}{\exists}xQ(x))\]

在这种意义下, 命题演算中的等价式和永真蕴含式在谓词演算中都是成立的.

 

\[{\forall}xP(x, y){\vee}{\exists}xQ(x){\Leftrightarrow}{\exists}xQ(x){\vee}{\forall}xP(x, y)\] \[{\forall}x(P(x){\rightarrow}Q(x)){\Leftrightarrow}{\forall}x({\lnot}P(x){\vee}Q(x))\] \[{\forall}xP(x){\wedge}({\forall}xP(x){\rightarrow}{\exists}xQ(x)){\Rightarrow}{\exists}xQ(x)\]

  1. 量词的转换律

\[{\lnot}{\forall}x{\lnot}A(x){\Leftrightarrow}{\exists}xA(x)\] \[{\lnot}{\exists}x{\lnot}A(x){\Leftrightarrow}{\forall}xA(x)\] \[{\lnot}{\forall}xA(x){\Leftrightarrow}{\exists}x{\lnot}A(x)\] \[{\lnot}{\exists}xA(x){\Leftrightarrow}{\forall}x{\lnot}A(x)\]

  1. 量词辖域的扩张与收缩律

设\(B\)是不含个体变元\(x\)的谓词公式, 则:

\[{\forall}x(A(x){\vee}B){\Leftrightarrow}{\forall}xA(x){\vee}B\] \[{\forall}x(A(x){\wedge}B){\Leftrightarrow}{\forall}xA(x){\wedge}B\] \[{\exists}x(A(x){\vee}B){\Leftrightarrow}{\exists}xA(x){\vee}B\] \[{\exists}x(A(x){\wedge}B){\Leftrightarrow}{\exists}xA(x){\wedge}B\]

  1. 量词的分配律

\[{\forall}x(A(x){\wedge}B(x)){\Leftrightarrow}{\forall}xA(x){\wedge}{\forall}xB(x)\] \[{\exists}x(A(x){\vee}B(x)){\Leftrightarrow}{\exists}xA(x){\vee}{\exists}xB(x)\]

  1. 量词的消去

在某一解释\(I\)下, 若个体域为有限集, 如\(D=\{a_{1}, a_{2}, {\cdots}, a_{n}\}\), 则由量词的定义可得: \[{\forall}xA(x){\Leftrightarrow}A(a_{1}){\wedge}A(a_{2}){\wedge}{\cdots}{\wedge}A(a_{n})\] \[{\exists}xA(x){\Leftrightarrow}A(a_{1}){\vee}A(a_{2}){\vee}{\cdots}{\vee}A(a_{n})\] 其中, \(A(a_{i})(i=1, 2, {\cdots}, n)\)为用\(a_{i}\)代入公式\(A(x)\)中自由出现的\(x\)得到的公式.

  1. 含有量词的永真蕴含式

\[{\forall}xA(x){\vee}{\forall}xB(x){\Rightarrow}{\forall}x(A(x){\vee}B(x))\] \[{\exists}x(A(x){\wedge}B(x)){\Rightarrow}{\exists}xA(x){\wedge}{\exists}xB(x)\] \[{\forall}x(A(x){\rightarrow}B(x)){\Rightarrow}{\forall}xA(x){\rightarrow}{\forall}xB(x)\] \[{\exists}xA(x){\rightarrow}{\forall}xB(x){\Rightarrow}{\forall}x(A(x){\rightarrow}B(x))\] 这些永真蕴含式的逆均不成立.

  1. 多个量词的使用

\[{\forall}x{\forall}yA(x, y){\Leftrightarrow}{\forall}y{\forall}xA(x, y), \, \, {\exists}x{\exists}yA(x, y){\Leftrightarrow}{\exists}y{\exists}xA(x, y)\] \[{\forall}x{\forall}yA(x, y){\Rightarrow}{\exists}y{\forall}xA(x, y), \, \, {\forall}y{\forall}xA(x, y){\Rightarrow}{\exists}x{\forall}yA(x, y)\] \[{\exists}y{\forall}xA(x, y){\Rightarrow}{\forall}x{\exists}yA(x, y), \, \, {\exists}x{\forall}yA(x, y){\Rightarrow}{\forall}y{\exists}xA(x, y)\] \[{\forall}x{\exists}yA(x, y){\Rightarrow}{\exists}y{\exists}xA(x, y), \, \, {\forall}y{\exists}xA(x, y){\Rightarrow}{\exists}x{\exists}yA(x, y)\]

量词次序不同, 其意义是不一样的, 不可随意交换.

 

例: \(G(x, y):x+y>2\), 个体域为实数集合.

命题\({\forall}x{\exists}yG(x, y)\): 对任意实数\(x\), 都存在实数\(y\), 有\(x+y>2\).

命题\({\exists}y{\forall}xG(x, y)\): 存在实数\(y\), 使对任意实数\(x\), 有\(x+y>2\).

\(A(x, y)\): \(x\)和\(y\)同姓, \(x\)的个体域为甲村人集合, \(y\)的个体域为乙村人集合.

\({\forall}x{\forall}yA(x, y)\): 甲村与乙村所有人都同姓

\({\forall}y{\forall}xA(x, y)\): 乙村与甲村所有人都同姓

可见:\[{\forall}x{\forall}yA(x, y){\Leftrightarrow}{\forall}y{\forall}xA(x, y)\]

\({\exists}x{\exists}yA(x, y)\): 甲村与乙村有同姓的人

\({\exists}y{\exists}xA(x, y)\): 乙村与甲村有同姓的人

可见:\[{\exists}x{\exists}yA(x, y){\Leftrightarrow}{\exists}y{\exists}xA(x, y)\]

\({\forall}x{\exists}yA(x, y)\): 对于甲村的每一个人, 乙村都有跟他同姓的

\({\exists}y{\forall}xA(x, y)\): 乙村有一个人, 甲村所有人都跟他同姓

\({\forall}y{\exists}xA(x, y)\): 对于乙村的每一个人, 甲村都有跟他同姓的

\({\exists}x{\forall}yA(x, y)\): 甲村有一个人, 乙村所有人都跟他同姓

定理(置换规则): 设\(A\)为含有子公式\(A_{1}\)的公式, 用公式\(B_{1}\)置换公式\(A\)中的\(A_{1}\)得到公式\(B\), 若\(A_{1}{\Leftrightarrow}B_{1}\), 则\(A{\Leftrightarrow}B\).

由于\(A_{1}\)和\(B_{1}\)等价, 因而用\(B_{1}\)替换\(A_{1}\)不会改变\(A\)的真值, 因此\(A\)与\(B\)等价.

定理(换名规则): 设\(x\)是辖域内的约束变元, \(y\)是在辖域内未曾出现的个体变元, 则有: \[{\forall}xA(x){\Leftrightarrow}{\forall}yA(y)\] \[{\exists}xA(x){\Leftrightarrow}{\exists}yA(y)\] 定理(代入规则): 设\(A\)为谓词公式, 将\(A\)中某自由变元的所有出现, 替换为\(A\)中未曾出现的某个体变元, 而\(A\)的其余部分不变, 得谓词公式\(B\), 则\(A{\Leftrightarrow}B\).

若个体域\(D=\{a, b\}\), 求\({\forall}x{\exists}y(A(x){\rightarrow}B(y))\)的真值.

已知: \[ \begin{array}{cccc} A(a)&A(b)&B(a)&B(b)\\ T&F&T&T\\ \end{array} \]  

\({\forall}x{\exists} y(A(x){\rightarrow}B(y))\)

\[{\Leftrightarrow}{\forall}x((A(x){\rightarrow}B(a)){\vee}(A(x){\rightarrow}B(b)))\] \[{\Leftrightarrow}((A(a){\rightarrow}B(a)){\vee}(A(a){\rightarrow}B(b))){\wedge}((A(b){\rightarrow}B(a)){\vee}(A(b){\rightarrow}B(b)))\] \[{\Leftrightarrow}((T{\rightarrow}T){\vee}(T{\rightarrow}T)){\wedge}((F{\rightarrow}T){\vee}(F{\rightarrow}T))\] \[{\Leftrightarrow}T\] 当个体域中的元素较多或有无限多元素时, 这种方法就变得不实际了.

求证: \[{\forall}x(A(x){\rightarrow}B){\Leftrightarrow}{\exists}xA(x){\rightarrow}B.\]

证明: \[{\forall}x(A(x){\rightarrow}B)\] \[{\Leftrightarrow}{\forall}x({\lnot}A(x){\vee}B)\] \[{\Leftrightarrow}{\forall}x{\lnot}A(x){\vee}B\] \[{\Leftrightarrow}{\lnot}{\exists}xA(x){\vee}B\] \[{\Leftrightarrow}{\exists}xA(x){\rightarrow}B\]

求证: 对于任意的\(A(x)\)和\(B(x)\), 有 \[{\exists}x(A(x){\rightarrow}B(x)){\Leftrightarrow}{\forall}xA(x){\rightarrow}{\exists}xB(x).\] 证明:\[{\exists}x(A(x){\rightarrow}B(x))\] \[{\Leftrightarrow}{\exists}x({\lnot}A(x){\vee}B(x))\] \[{\Leftrightarrow}{\exists}x{\lnot}A(x){\vee}{\exists}xB(x)\] \[{\Leftrightarrow}{\lnot}{\forall}xA(x){\vee}{\exists}xB(x)\] \[{\Leftrightarrow}{\forall}xA(x){\rightarrow}{\exists}xB(x)\]

求证: \[{\forall}xP(x){\wedge}{\exists}xQ(x){\Leftrightarrow}{\forall}x{\exists}y(P(x){\wedge}Q(y)).\] 证明:\[{\forall}xP(x){\wedge}{\exists}xQ(x)\] \[{\Leftrightarrow}{\forall}xP(x){\wedge}{\exists}yQ(y)\] \[{\Leftrightarrow}{\forall}x(P(x){\wedge}{\exists}yQ(y))\] \[{\Leftrightarrow}{\forall}x{\exists}y(P(x){\wedge}Q(y))\]

求证: 对于任意的\(A(x)\)和\(B(x)\), 有 \[{\exists}xA(x){\rightarrow}{\forall}xB(x){\Rightarrow}{\forall}x(A(x){\rightarrow}B(x))\] 证明:\[{\exists}xA(x){\rightarrow}{\forall}xB(x)\] \[{\Leftrightarrow}{\lnot}{\exists}xA(x){\vee}{\forall}xB(x)\] \[{\Leftrightarrow}{\forall}x{\lnot}A(x){\vee}{\forall}xB(x)\] \[{\Rightarrow}{\forall}x({\lnot}A(x){\vee}B(x))\] \[{\Leftrightarrow}{\forall}x(A(x){\rightarrow}B(x))\] 故\[{\exists}xA(x){\rightarrow}{\forall}xB(x){\Rightarrow}{\forall}x(A(x){\rightarrow}B(x))\]

前束范式

一个谓词公式, 如果它的所有量词均出现在公式的最前端, 而它们的作用域延伸到整个谓词公式的尾端, 则称该谓词公式为前束范式.

前束范式具有以下形式: \[Q_{1}x_{1}Q_{2}x_{2}{\cdots}Q_kx_kB\] 其中, 每个\(Q_{i}{\in}{{\forall}, {\exists}}(1{\le}i{\le}k)\), \(B\)为不含量词的谓词公式.

如果谓词公式\(A\)中无量词, \(A\)也被看作是前束范式. 如: \({\lnot}A(x){\vee}B(x)\).

例: \[{\forall}x{\exists}y{\exists}z({\lnot}P(x){\rightarrow}(Q(y){\rightarrow}R(z, y)))\] \[{\forall}x{\forall}y(S(x, w){\vee}T(y))\] \[U(x, y)\] 是前束范式.

而 \[{\forall}xF(x, y){\rightarrow}{\exists}yG(y)\] \[{\forall}x{\exists}zC(x, z){\wedge}V(z)\] 都不是前束范式.

定理(前束范式存在定理): 任何谓词公式均存在与其等价的前束范式.

化谓词公式为前束范式的步骤是:

  1. 将否定联结词向谓词公式内推入, 使之直接位于原子谓词公式之前.

  2. 利用换名规则和代入规则使所有约束变元符号均不相同, 自由变元与约束变元的符号也不相同.

  3. 利用等价式将量词逐个移至谓词公式之前.

化谓词公式 \({\forall}xP(x){\rightarrow}{\exists}xQ(x)\)为前束范式.

(方法1) \[{\forall}xP(x){\rightarrow}{\exists}xQ(x)\] \[{\Leftrightarrow}{\lnot}{\forall}xP(x){\vee}{\exists}xQ(x)\] \[{\Leftrightarrow}{\exists}x{\lnot}P(x){\vee}{\exists}xQ(x)\] \[{\Leftrightarrow}{\exists}x({\lnot}P(x){\vee}Q(x))\]

(方法2) \[{\forall}xP(x){\rightarrow}{\exists}xQ(x)\] \[{\Leftrightarrow}{\forall}xP(x){\rightarrow}{\exists}yQ(y)\] \[{\Leftrightarrow}\lnot{\forall}xP(x){\vee}{\exists}yQ(y)\] \[{\Leftrightarrow}{\exists}x({\lnot}P(x)){\vee}{\exists}yQ(y)\] \[{\Leftrightarrow}{\exists}x({\lnot}P(x){\vee}{\exists}yQ(y))\] \[{\Leftrightarrow}{\exists}x{\exists}y({\lnot}P(x){\vee}Q(y))\] \[{\Leftrightarrow}{\exists}x{\exists}y(P(x){\rightarrow}Q(y))\]

可见, 谓词公式的前束范式并不唯一

化谓词公式 \({\lnot}({\forall}xP(x, y){\wedge}{\forall}xQ(x, z)){\rightarrow}{\exists}yR(y, x)\)为前束范式.

解:\[{\lnot}({\forall}xP(x, y){\wedge}{\forall}xQ(x, z)){\rightarrow}{\exists}yR(y, x)\] \[{\Leftrightarrow}({\lnot}{\forall}xP(x, y){\vee}{\lnot}{\forall}xQ(x, z)){\rightarrow}{\exists}yR(y, x)\] \[{\Leftrightarrow}({\exists}x{\lnot}P(x, y){\vee}{\exists}x{\lnot}Q(x, z)){\rightarrow}{\exists}yR(y, x)\] \[{\Leftrightarrow}{\exists}x({\lnot}P(x, y){\vee}{\lnot}Q(x, z)){\rightarrow}{\exists}yR(y, x)\] \[{\Leftrightarrow}{\exists}u({\lnot}P(u, y){\vee}{\lnot}Q(u, z)){\rightarrow}{\exists}vR(v, x)\] \[{\Leftrightarrow}{\exists}u(\lnot({\lnot}P(u, y){\vee}{\lnot}Q(u, z)){\lor}{\exists}vR(v, x))\] \[{\Leftrightarrow}{\exists}u{\exists}v(\lnot({\lnot}P(u, y){\vee}{\lnot}Q(u, z)){\lor}R(v, x))\] \[{\Leftrightarrow}{\exists}u{\exists}v(({\lnot}P(u, y){\vee}{\lnot}Q(u, z)){\rightarrow}R(v, x))\]

一个前束范式, 若其不含量词的部分为析取范式, 称为前束析取范式; 若其不含量词的部分为合取范式, 称为前束合取范式.

  • \({\forall}x{\exists}y(P(x, y){\wedge}Q(x))\)是前束合取范式

  • \({\forall}x{\exists}y{\exists}z((R(x, y, z){\wedge}S(x)){\vee}Q(x))\)是前束析取范式

定理:任何谓词公式均可化为与其等价的前束析取范式或前束合取范式.

转化为前束析取范式或前束合取范式的步骤:

  1. 将谓词公式中的联结词全部转化为\({\lnot}\), \({\wedge}\)和\({\vee}\).

  2. 将公式化为前束范式.

  3. 利用分配律将公式进一步化为前束析取范式或前束合取范式.

求\({\exists}xA(x){\rightarrow}{\exists}yB(y)\)的前束析取范式与前束合取范式.

解:\[{\exists}xA(x){\rightarrow}{\exists}yB(y)\] \[{\Leftrightarrow}{\lnot}{\exists}xA(x){\vee}{\exists}yB(y)\] \[{\Leftrightarrow}{\forall}x{\lnot}A(x){\vee}{\exists}yB(y)\] \[{\Leftrightarrow}{\forall}x({\lnot}A(x){\vee}{\exists}yB(y))\] \[{\Leftrightarrow}{\forall}x{\exists}y({\lnot}A(x){\vee}B(y))\]

求\({\forall}x(F(x){\vee}H(y)){\rightarrow}{\forall}yG(x, y)\) 的前束析取范式与前束合取范式.

解: \[{\forall}x(F(x){\vee}H(y)){\rightarrow}{\forall}yG(x, y)\] \[{\Leftrightarrow}{\lnot}{\forall}x(F(x){\vee}H(y)){\vee}{\forall}yG(x, y)\] \[{\Leftrightarrow}{\exists}x{\lnot}(F(x){\vee}H(y)){\vee}{\forall}yG(x, y)\] \[{\Leftrightarrow}{\exists}v{\lnot}(F(v){\vee}H(y)){\vee}{\forall}wG(x, w)\] \[{\Leftrightarrow}{\exists}v({\lnot}(F(v){\vee}H(y)){\vee}{\forall}wG(x, w))\] \[{\Leftrightarrow}{\exists}v{\forall}w({\lnot}(F(v){\vee}H(y)){\vee}G(x, w))\] \[{\Leftrightarrow}{\exists}v{\forall}w(({\lnot}F(v){\wedge}{\lnot}H(y)){\vee}G(x, w))\]

前束析取范式: \({\exists}v{\forall}w(({\lnot}F(v){\wedge}{\lnot}H(y)){\vee}G(x, w))\)

前束合取范式: \({\exists}v{\forall}w({\lnot}F(v){\vee}G(x, w)){\wedge}({\lnot}H(y){\vee}G(x, w))\)

求\({\forall}x{\exists}y(P(x, y){\wedge}Q(x)){\wedge}{\forall}x({\exists}zR(z, x){\rightarrow}S(w))\)的前束析取范式.

解:\[{\forall}x{\exists}y(P(x, y){\wedge}Q(x)){\wedge}{\forall}x({\exists}zR(z, x){\rightarrow}S(w))\] \[{\Leftrightarrow}{\forall}x{\exists}y(P(x, y){\wedge}Q(x)){\wedge}{\forall}x({\lnot}{\exists}zR(z, x){\vee}S(w))\] \[{\Leftrightarrow}{\forall}x{\exists}y(P(x, y){\wedge}Q(x)){\wedge}{\forall}x({\forall}z{\lnot}R(z, x){\vee}S(w))\] \[{\Leftrightarrow}{\forall}x({\exists}y(P(x, y){\wedge}Q(x)){\wedge}{\forall}z({\lnot}R(z, x){\vee}S(w)))\]

\[{\Leftrightarrow}{\forall}x{\exists}y((P(x, y){\wedge}Q(x)){\wedge}{\forall}z({\lnot}R(z, x){\vee}S(w)))\] \[{\Leftrightarrow}{\forall}x{\exists}y{\forall}z((P(x, y){\wedge}Q(x)){\wedge}({\lnot}R(z, x){\vee}S(w)))\] \[{\Leftrightarrow}{\forall}x{\exists}y{\forall}z((P(x, y){\wedge}Q(x){\wedge}{\lnot}R(z, x)){\vee}(P(x, y){\wedge}Q(x){\wedge}S(w)))\]

例: 求\({\forall}x({\exists}y(A(x, y){\wedge}B(x)){\rightarrow}{\exists}zC(y, z))\)的前束合取范式.

解:\({\forall}x({\exists}y(A(x, y){\wedge}B(x)){\rightarrow}{\exists}zC(y, z))\) \[{\Leftrightarrow}{\forall}x({\lnot}{\exists}y(A(x, y){\wedge}B(x)){\vee}{\exists}zC(y, z))\] \[{\Leftrightarrow}{\forall}x({\forall}y({\lnot}A(x, y){\vee}{\lnot}B(x)){\vee}{\exists}zC(y, z))\] \[{\Leftrightarrow}{\forall}x({\forall}\boxed{w}({\lnot}A(x, \boxed{w}){\vee}{\lnot}B(x)){\vee}{\exists}zC(y, z))\] \[{\Leftrightarrow}{\forall}x{\forall}w{\exists}z({\lnot}A(x, w){\vee}{\lnot}B(x){\vee}C(y, z))\]

谓词逻辑推理

推理规则

对谓词公式\(A(x)\)来说, 在量词\({\forall}y\)或\({\exists}y\)的辖域内, 如果没有\(x\)的自由变元, 则称\(A(x)\)对于变元\(y\)是自由的.

由定义可知, 若\(y\)不是\(A(x)\)的约束变元, 则\(A(x)\)对于\(y\)一定是自由的.

  1. \(A(x)={\forall}yP(y){\vee}Q(x, y)\)

  2. \(A(x)={\forall}yP(y){\rightarrow}(Q(x){\wedge}Q(y))\)

  3. \(A(x)={\forall}yP(\boxed{x}, y){\rightarrow}Q(x, y)\)

  4. \(A(x)={\forall}y(P(y){\vee}Q(\boxed{x}, y))\)

  5. \(A(x)={\forall}y(P(y){\vee}{\forall}xQ(x, y))\)

(1), (2)和(5)对\(y\)是自由的, (3)和(4)对\(y\)不是自由的.

全称量词具体化规则

又称存在量词消去规则, 简称US (Universal Specification)规则.

\[ \frac{\forall xA(x)}{\therefore A(y)}\, \, or\, \, \frac{\forall xA(x)}{\therefore A(c)} \]

其中\(c\)为个体域中任意个体常元.

这里要求\(A(x)\)对\(y\)是自由的.

\(y\)或\(c\)是取代了\(A(x)\)中所有自由出现的\(x\).

使用这两个规则时需注意该规则成立的条件, 否则会导致推理错误.

设个体域为实数集合, \(L(x, y)\)表示\(x<y\), 则\({\exists}x{\exists}yL(x, y)\)解释为“对任一实数\(x\), 都存在实数\(y\), 使得\(x<y\)”, 这是一个真命题.

如果进行以下推理:

  1. \({\forall}x{\exists}yL(x, y)\qquad\)前提引入

  2. \({\exists}yL(y, y)\qquad\) US规则(1)

所得结果表示“存在着实数\(y\), 使\(y<y\)”, 显然这是不正确的推理结果.

原因是\({\exists}yL(x, y)\)对y不是自由的.

全称量词泛化规则

又称全称量词引入规则, 简称UG (Universal Generalization)规则. \[ \frac{A(x)}{\therefore {\forall}yA(y)} \]

要求前提\(A(x)\)对于\(x\)的任意取值都成立, \(A(x)\)对\(y\)是自由的, 且取代\(x\)的个体变元\(y\)不能在\(A(x)\)中约束出现.

注意该规则的使用条件, 以免出现推理错误.

设个体域为实数集合, \(L(x, y)\)表示\(x<y\), 进行以下推理:

  1. \({\forall}x{\exists}yL(x, y)\qquad\) 前提引入

  2. \({\exists}yL(z, y)\qquad\qquad\) US规则

  3. \({\forall}y{\exists}yL(y, y)\qquad\) UG规则(2)

得出“对于任意的实数\(y\), 存在着实数\(y\), 使\(y<y\)”, 结论显然是错误的.

原因是用在\({\exists}yL(z, y)\)中约束出现的y取代了z.

存在量词具体化规则

又称存在量词消去规则, 简称ES (Existential Specification)规则.

\[ \frac{\exists xA(x)}{\therefore A(y)}\, \, or\, \, \frac{\exists xA(x)}{\therefore A(c)} \]

其中\(c\)为特定的个体常元, 且使用不曾在\(A(x)\)中出现过的个体常元\(c\)或个体变元\(y\)取代\(x\).

当\(A(x)\)中存在其它自由变元时不宜使用此规则, 否则可能导致错误的推理.

设个体域为实数集合, \(L(x, y)\)表示\(x<y\), 如果进行以下推演:

  1. \({\forall}x{\exists}yL(x, y)\qquad\)前提引入

  2. \({\exists}yL(z, y)\qquad\,\,\,\) US规则(1)

  3. \(L(z, c)\qquad\qquad\) ES规则(2)

得到“任一实数\(z\)均满足\(z<c\)”, 显然这是错误的结论.

原因是\({\exists}yL(z, y)\)中存在自由变元z, 不宜使用ES规则.

存在量词泛化规则

又称存在量词引入规则, 简称EG (Existential Generalization)规则.

\[ \frac{A(c)}{\therefore {\exists}yA(y)}\, \, or\, \, \frac{A(x)}{\therefore {\exists}yA(y)} \]

其中\(c\)为特定的个体常元, \(A(x)\)对\(y\)是自由的, 取代\(c\)的个体变元\(y\)不曾在\(A(x)\)中出现, 且\(y\)不能是\(A(x)\)中的个体变元.

应用该规则时应注意这些条件, 否则可能产生推理错误.

设个体域为实数集合, \(L(x, y)\)表示\(x<y\), 如果进行以下推理:

  1. \({\exists}xL(x, 0)\qquad\qquad\)前提引入

  2. \({\exists}x{\exists}xL(x, x)\qquad\) EG规则(1)

得出结论为“存在实数\(x\), 使\(x<x\)”, 显然是不正确的.

原因是x已在\({\exists}xL(x, 0)\)中出现, 此时不能用\(x\)取代0.

构造推理证明的序列时, 在应用量词的引入和消去规则时, 需注意从序列整体上考虑个体变元与个体常元符号选取.

特别是在应用EG和ES规则时, 要避免选择已在序列前面的公式中出现的符号进行取代, 否则可能产生推理错误.

\(x, y\)的个体域为实数集, \(F(x)\)表示\(x\)是正数, \(G(x)\)表示\(x\)是负数, 进行以下的推理:

  1. \({\exists}xF(x)\qquad\) 前提引入

  2. \(F(c)\qquad\qquad\) ES规则(1)

  3. \({\exists}yG(y)\qquad\) 前提引入

  4. \(G(c)\qquad\qquad\) ES规则(3)

  5. \(F(c){\wedge}G(c)\qquad\) T规则(2)(4)

  6. \({\exists}x(F(x){\wedge}G(x))\qquad\) EG规则(5)

结论是“存在实数\(x\), 它既是正数又是负数”, 显然是错误的.

原因是在第(2)步引入个体常元\(c\)后, 在第(4)步应用ES规则时又引入相同的个体常元, 结果推出了错误的结论.

设个体域为正实数集, \(F(x):x＞0\),

\(G(x):x＞2\), 进行以下推理:

  1. \({\forall}xF(x)\qquad\) 前提引入

  2. \({\exists}yG(y)\qquad\) 前提引入

  3. \(F(c)\qquad\) US规则(1)

  4. \(G(c)\qquad\) ES规则(2)

  5. \(F(c){\wedge}G(c)\qquad\) T规则(2)

推理过程正确吗?

重新推理:

  1. \({\forall}xF(x)\qquad\) 前提引入

  2. \({\exists}yG(y)\qquad\) 前提引入

  3. \(G(c)\qquad\) ES规则(1)

  4. \(F(c)\qquad\) US规则(2)

  5. \(F(c){\wedge}G(c)\qquad\) T规则(2)

这个是正确的.

注意：量词的消去是先\(\exists\)后\(\forall\).

推理应用

谓词逻辑的推理方法与命题逻辑的推理方法类似, 利用已知的基本等价式、基本蕴含式、\(P\)规则、\(T\)规则和\(CP\)规则, 以及有关量词的引入和消去规则进行推理.

推理方法也分直接证法和间接证法.

推理证明: \[{\forall}x(A(x){\vee}B(x)), {\exists}x(A(x){\rightarrow}C(x)){\vDash}{\exists}x(B(x){\vee}C(x))\]

证明:

  1. \({\exists}x(A(x){\rightarrow}C(x))\qquad\) P

  2. \(A(c){\rightarrow}C(c)\qquad\) ES(1)

  3. \({\forall}x(A(x){\vee}B(x))\qquad\) P

  4. \(A(c){\vee}B(c)\qquad\) US(3)

  5. \({\lnot}B(c){\rightarrow}A(c)\qquad\) T(4)

  6. \({\lnot}B(c){\rightarrow}C(c)\qquad\) T(2)(5)

  7. \(B(c){\vee}C(c)\qquad\) T(6)

  8. \({\exists}x(B(x){\vee}C(x))\qquad\) EG(7)

凡是大熊猫都产在中国四川省, 欢欢是只大熊猫, 所以欢欢产在中国四川省.

设\(F(x)\): \(x\)是大熊猫; \(G(x)\): \(x\)产在中国四川省 \(c\): 欢欢.

前提: \({\forall}x(F(x){\rightarrow}G(x))\); \(F(c)\),

结论: \(G(c)\)

  1. \({\forall}x(F(x){\rightarrow}G(x))\qquad\) P

  2. \(F(c){\rightarrow}G(c)\qquad\) US(1)

  3. \(F(c)\qquad\qquad\) P

  4. \(G(c))\qquad\) T(2)(3)

推理证明: \[{\forall}x(P(x){\vee}Q(x)), {\lnot}{\forall}xP(x){\vDash}{\exists}xQ(x).\]

将\({\lnot}{\exists}xQ(x)\)作为附加前提. 证明如下:

  1. \({\lnot}{\forall}xP(x)\qquad\) P

  2. \({\exists}x{\lnot}P(x)\qquad\) T(1)

  3. \({\lnot}P(a)\qquad\, \, \, \, \, \,\) ES(2)

  4. \({\lnot}{\exists}xQ(x)\qquad\) P(附加前提)

  5. \({\forall}x{\lnot}Q(x)\qquad\) T(4)

  6. \({\lnot}Q(a)\, \, \, \, \, \qquad\) US(5)

  1. \({\lnot}P(a){\wedge}{\lnot}Q(a)\qquad\) T(3)(6)

  2. \({\lnot}(P(a){\vee}Q(a))\qquad\) T(7)

  3. \({\forall}x(P(x){\vee}Q(x))\qquad\) P

  4. \(P(a){\vee}Q(a)\qquad\, \, \, \, \, \, \, \, \,\) US(9)

  5. \((P(a){\vee}Q(a)){\wedge}{\lnot}(P(a){\vee}Q(a))\quad\) \(\qquad\qquad\qquad\qquad\qquad\) T(8)(10)

(11)是一个矛盾式, 所以 \[{\forall}x(P(x){\vee}Q(x)), {\lnot}{\forall}xP(x){\vDash}{\exists}xQ(x).\]

推理证明 \[{\forall}x(H(x){\rightarrow}M(x)){\vDash} {\forall}x{\forall}y(H(y){\wedge}N(x, y)){\rightarrow}{\exists}y(M(y){\wedge}N(t, y))\]

将\({\forall}x{\forall}y(H(y){\wedge}N(x, y))\)作为附加前提, 证明序列如下:

  1. \({\forall}x{\forall}y(H(y){\wedge}N(x, y))\) P(附加前提)

  2. \({\forall}y(H(y){\wedge}N(t, y))\qquad\) US(1)

  3. \(H(b){\wedge}N(t, b)\qquad\qquad\) US(2)

  1. \({\forall}x(H(x){\rightarrow}M(x))\, \,\) P

  2. \(H(b){\rightarrow}M(b)\qquad\) US(4)

  3. \(H(b)\qquad\qquad\qquad\) T(3)

  4. \(M(b)\qquad\qquad\qquad\) T(5)(6)

  5. \(N(t, b)\qquad\qquad\qquad\) T(3)

  6. \(M(b){\wedge}N(t, b)\qquad\) T(7)(8)

  7. \({\exists}y(M(y){\wedge}N(t, y)\) EG(9)

  8. \({\forall}x{\forall}y(H(y){\wedge}N(x, y)){\rightarrow}{\exists}y(M(y){\wedge}N(t, y))\qquad\qquad\) CP(1)(10)

推理证明苏格拉底的三段论: 所有的人都是会死的, 苏格拉底是人, 所以苏格拉底是会死的.

证明: 设\(F(x)\): \(x\)是人, \(G(x)\): \(x\)是会死的, \(c\): 苏格拉底.

前提: \({\forall}x(F(x){\rightarrow}G(x)), F(c)\)

结论: \(G(c)\)

证明序列如下:

  1. \({\forall}x(F(x){\rightarrow}G(x))\qquad\) P

  2. \(F(c){\rightarrow}G(c)\qquad\quad\quad\) US(1)

  3. \(F(c)\qquad\qquad\qquad\quad\, \, \,\) P

  4. \(G(c)\qquad\qquad\qquad\quad\, \, \,\) T(2)(3)