ch4 谓词逻辑的基本概念¶

【命题逻辑存在的问题】

问题出在 “凡” 字
没有表达出个体和总体之间的内在联系和数量关系

【谓词逻辑和命题逻辑的关系】

谓词逻辑是命题逻辑的推广，命题逻辑是谓词逻辑的特殊情形。

1. 谓词和个体词¶

【谓词逻辑】区分主语、谓语，引入变元，引入谓词、量词。

可将谓词逻辑理解为【命题逻辑 + {个体词、谓词、量词、函数}】。

谓词逻辑的三要素：个体词，谓词和量词，函数。

【个体词（主词）】指所研究对象中可以独立存在的具体的或抽象的客体。在一个命题中，个体词通常是表示思维对象的词，又称主词。

【个体常项与个体变项】将表示具体或特定客体的个体词称作个体常项，用小写字母 \(a,b,c..\) 表示；将表示抽象或泛指的个体词称为个体变项，用小写字母 \(x,y,z..\) 表示；并称个体变项的取值范围为个体域或论域，以 \(D\) 表示。约定有一个特殊的个体域，它由世间一切事物组成，称之为总论域。

【谓词】用来刻画个体词的性质或多个个体词间关系的词，用 \(P(x),Q(x,y)\) 表示，谓词又可看作是由给定的个体域到集合 \(\{T,F\}\) 上的一个映射。

【谓词常项与谓词变项】表示具体性质或关系的谓词称作谓词常项；表示抽象或泛指的性质或关系的谓词称作谓词变项。谓词常项与谓词变项都用大写字母 \(P,Q,R..\) 表示，可根据上下文区分。

【一元谓词与多元谓词】在一个命题中，如果个体词只有一个，这时表示该个体词性质或属性的词便是一元谓词；如果一个命题中的个体词多于一个，则表示这几个个体词间关系的词便是多元谓词。一般的，用 \(P(a)\) 表示个体常项 \(a\) 具有性质 \(P\)，用 \(P(x)\) 表示个体变项 \(x\) 具有性质 \(P\)。

【零元谓词】将不带个体变项的谓词称为零元谓词，当此时的零元谓词又为谓词常项时，零元谓词即化为命题。因此，命题逻辑中的命题均可以表示成零元谓词，或认为一个命题是没有个体变项的零元谓词。

2. 函数和量词¶

【函数】在谓词逻辑中可引入函数，它是某一个体域到另一个体域的映射。谓词逻辑中的函数一般不单独使用，而是嵌入在谓词中。约定函数符号用小写字母表示。

【量词】表示个体常项或变项之间数量关系的词称为量词。量词是对个体词所加的限制或约束的词，量词分为全称量词和存在量词两种。量词的优先级高于逻辑联结词。

【全称量词】命题 \((\forall x)P(x)\) 当且仅当对论域中的所有 \(x\)，\(P(X)\) 均为真时方为真。而 \((\forall x)P(x) = F\) 成立，当且仅当至少存在一个 \(x_0\in D\)，使 \(P(x_0) = F\)。

【存在量词】命题 \((\exists x)P(x)\) 当且仅当至少存在一个 \(x_0\in D\)，\(P(X_0)\)为真时即为真。而 \((\exists x)P(x) = F\) 成立，当且仅当对论域中的所有 \(x\)，均有 \(P(x) = F\)。

【约束变元与自由变元】量词所约束的范围称为量词的辖域，在公式 \((\forall x)A\) 和 \((\exists x)A\) 中，\(A\) 为相应量词的辖域，在 \((\forall x)\) 和 \((\exists x)\) 的辖域中，\(x\) 的所有出现都称为约束出现。所有约束出现的变元称为约束变元。\(A\) 中不是约束出现的其它变元均称为自由变元。一个谓词公式如果无自由变元，它就表示一个命题。

3. 合式公式¶

【一阶谓词逻辑】限定量词仅作用于个体变项，不允许量词作用于命题变项和谓词变项。

【合式公式定义】

命题常项、命题变项和原子谓词公式（不含联结词的谓词公式）是合式公式。
若 \(A\) 是合式公式，则 \((\lnot A)\) 也是合式公式。
若 \(A,B\) 是合式公式，而无变元 \(x\) 在 \(A,B\) 的一个中是约束的而在另一个中是自由的，则 \((A\land B)\)、\((A\lor B)\)、\((A\to B)\)，\((A\leftrightarrow B)\) 也是合式公式。
若 \(A\) 是合式公式，则 \((\forall x)A\)、\((\exists x)A\) 也是合式公式。
只有有限次地应用 \(1\sim 4\) 构成的符号串才是合式公式。

4. 自然语句的形式化¶

利用计算机进行推理的基础工作。
在分析的基础上，将问题分解成一些合适的为此表示，即先做一些谓词（函数）设定；然后使用量词、联结词将设定的谓词构成合式公式。

形式化：所有的有理数都是实数

解：设 \(P(x)\)：\(x\) 是有理数，\(Q(x)\)：\(x\) 是实数，则形式化描述为 \((\forall x)(P(x)\to Q(x))\)

形式化：有的实数是有理数

解：假设同上，则形式化描述为 \((\exists x)(Q(x)\land P(x))\)

形式化：没有无理数是有理数

解：设 \(A(x)\)：\(x\) 是无理数，\(B(x)\)：\(x\) 是有理数，则形式化描述为 \(\lnot (\exists x)(A(x) \land B(x))\)，也可以形式化为 \((\forall x) (A(x) \to \lnot B(x))\) 或 \((\forall x) (B(x) \to \lnot A(x))\)

在谓词演算中，命题的符号表达式与论域有关系。当论域扩大时，需要添加用来表示客体特性的谓词，称此谓词为特性谓词。特性谓词往往就是给定命题中量词后面的那个名词。如果前面是全称量词，特性谓词后面是蕴含联结词；如果前面是存在量词，特性谓词后面是合取联结词。

形式化：每个自然数都是整数。

如果论域是自然数集合 \(N\)，令 \(I(x)\)：\(x\) 是整数，则命题的表达式为 \(\forall x\ I(x)\)。

如果论域扩大为全总个体域时，需要添加谓词 \(N(x)\)：\(x\) 是自然数，用于表明 \(x\) 的特性，于是命题的符号表达式为 \(\forall x\ (N(x) \to I(x))\)。

在不同个体域内，同一个命题的符号化形式可能不同，也可能相同。
同一个命题，在不同个体域中的真值也可能不同。

关于唯一性的一般描述：常用办法是，先表示存在一个，同时如果还能找到另一个的话，则它们一定相等。一般描述可以表述为：\((\exists x)(P(x)\land (\forall y)(P(y)\to E(x, y)))\)，其中 \(E(x,y)\) 表示 \(x = y\)。

5. 有限域下公式的表示法¶

将论域限定为有限集，不失一般性，用 \(\{1,2,...,k\}\) 来表示，这时全称量词和存在量词可化为如下公式：

\((\forall x)P(x) = P(1)\land P(2)\land .. \land P(k)\)
\((\exists x)P(x) = P(1)\lor P(2)\lor .. \lor P(k)\)

这种情况下可以说，全称量词是合取词的推广，存在量词是析取词的推广。一般而言（在无限域下），谓词逻辑的公式不能转换为命题逻辑的公式。

普遍有效公式：设 \(A\) 是一个谓词公式，若 \(A\) 在任何解释下真值均为真，则称 \(A\) 为普遍有效的公式。
不可满足公式：设 \(A\) 是一个谓词公式，若 \(A\) 在任何解释下真值均为假，则称 \(A\) 为不可满足的公式。
可满足公式：设 \(A\) 是一个谓词公式，若至少存在一个解释使 \(A\) 为真，则称 \(A\) 为可满足的公式。普遍有效公式一定是可满足公式。

有限域上公式普遍有效性的几个结论：

公式的可满足性和普遍有效性依赖于个体域中个体的个数。
如果公式在某个含 \(k\) 个元素的 \(k\) 个体域上普遍有效（可满足），则在任一 \(k\) 个体域上也普遍有效（可满足）。
如果某公式在 \(k\) 个体域上普遍有效，则在 \(k-1\) 个体域上也普遍有效。
如果某公式在 \(k\) 个体域上可满足，则在 \(k+1\) 个体域上也可满足。

谓词逻辑判定的几个结论：

一阶谓词逻辑是不可判定的。一阶谓词逻辑的某些子类是可判定的，包括
- 仅含一元谓词变项的公式是可判定的
- \((\forall x_1)(\forall x_2)..(\forall x_n)P(x_1, x_2,.. x_n)\) 和 \((\exists x_1)(\exists x_2)..(\exists x_n)P(x_1, x_2,.. x_n)\) 型公式若 \(P\) 中无量词和其它自由变项也是可判定的。
- 个体域有穷时的谓词公式是可判定的。
一阶谓词逻辑的普遍有效性是半可判定的。如果公式本身是普遍有效（或不可满足）的，则存在有限的判定算法，否则不存在有限的判定算法。