Ch4-谓词逻辑的基本概念谓词和个体词函数和量词谓词逻辑合式公式自然语句的形式化谓词变元多次量化和公式表示法公式的普遍有效性和判定问题Ch5-谓词逻辑的等值和推理演算谓词逻辑的等值谓词逻辑的范式谓词逻辑的基本的推理公式谓词逻辑的推理演算谓词逻辑的归结证明

Ch4-谓词逻辑的基本概念

Q: 能否用命题逻辑刻画以下推理：
$p$ ；
$q$ ；
$r$ 。
$(p\wedge q) \to r$ . 需要再引用符号，来表示一个个体是否具有某个性质。

谓词和个体词

Definition（谓词） $\{T,F\}$ $P,Q,\cdots$ 表示。

$P(x),Q(x),\cdots$ 表示。
$P(x,y),Q(x,y),R(x,y,z)$ 表示。

Example：
例如 “3 是有理数”，其中“是有理数”是谓词，表示了 3 的关系；
“5 大于 3”，其中“大于”是谓词，表示了 5,3 之间的关系。

Definition（个体词）：是一个命题里面表示思维对象的词。若指定了，称为个体常量；若没有指定，则称为个体变项。

Definition（谓词变项） $n$ $P(x_1,\cdots,x_n)$ $n$ $P$ $P$ 表示任一谓词时，称为谓词变项。

Definition（个体域/论域） 将个体变项的变化范围称为 个体域 或者论域。e.g. 自然数集，实数集。命题正确与否，也取决于论域。

$P(x)$ $P,x$ $P(x)$ $x$ $x$ $P(x)$ 取值为 T. 谓词逻辑是命题逻辑的推广。可以认为一个命题是一个零元谓词。

函数和量词

Definition（函数）：是某个体域到另外一个体域的映射，约定用小写字母表示。

Example $\mathrm{MARRIED}(father(张三),mother(张三))$ ，表示张三的父亲和母亲是否结婚。

$\forall ,\exists$ 作用于个体变元，不允许作用于命题变项和谓词变项。表示为：

\begin{matrix} (\forall x) (x 是 运 动 的) \\ (x) (x 是 运 动 的) \\ \forall x (P (x)) \\ \exists x (x 是 动 物) \end{matrix}

$\forall x (P(x))$ $x_0 \in D$ $P(x_0)=T$ .
$\forall x(P(x))$ $x_0 \in D$ $P(x_0)=F$ .
$(\exists x) P(x) \wedge Q(x)$ .
$(\forall x) P(x)=(\forall y) P(y)$ $x,y$ 无关。

Definition（辖域）：是量词所约束的范围。

$(\exists x)((\forall y) P(x,y))$ $P(x,y)$ $\forall y$ 的辖域。

谓词逻辑合式公式

符号约定：

$p,q,r,\cdots$ 表示命题变项；
$x,y,z,\cdots$ 表示个体；
$P,Q,R,\cdots$ 表示谓词变项；
$f,g,\cdots$ 表示函数。

Definition（谓词逻辑的合式公式）：合式公式的定义：

命题常项、命题变项和原子谓词公式（不含联结词的谓词）都是合式公式；
$A$ $\neg A$ 也是合式公式；
$A,B$ $x$ $A$ $B$ $(A\wedge /\vee B)$ $(A \to /\leftrightarrow B)$ 也是合式公式；

$(\forall x) F(x)\wedge G(x)$ $G(x)\to (\forall x)F(x)$ .

$A$ $x$ $A$ $A$ $(\forall x)(A),(\exists x)(A)$ 也是合式公式。

$(\exists x)((\forall x) P(x))$ $(\forall x) P(y)$ .

简单理解，就是能不能给出一个解释，使得合式公式合理。

自然语句的形式化

所有的……都是……

(\forall x) (P (x) \to Q (x))

$(\forall x)(P(x)\wedge Q(x))$ $(\forall x)(P(x))\wedge (\forall x)(Q(x))$ .
当真值取真时，真值和论域无关？
$\{1,2,3\}$ $\{1,2,\pi\}$ $\{\mathrm i\}$ ，则成立。

有的……是……

(\exists x) (P (x) \land Q (x))

$P:是有理数$ $Q:是无理数$ $(\exists x)(P (x) \to Q(x))$ . 假设我们找到一个数既不是有理数，也不是无理数，那么这个是对的。

没有……是……

\neg (\exists x) (P (x) \land Q (x))

(\forall x) (P (x) \to \neg Q (x))

有的……不是……

(\exists x) (A (x) \land \neg B (x))

\neg (\forall x) (A (x) \to B (x))

至少有一偶数是素数和至少有一偶数并且至少有一素数 第一个命题等价于“有的……是……”，第二个命题等价于：

(\exists x) P (x) \land (\exists x) Q (x)

积木世界的形式描述

$ON$ $CLEAR$ 表示是否其上有积木块，则：

(\forall x) (C L E A R (x) \to \neg (\exists y) (O N (y, x)))

自然数集的形式化描述

论域是自然数集，来形式化语句：

（1）对每个数，有且仅有一个相继后元（2）没有这样的数，0 是其相继后元（3）对除 0 而外的数，有且仅有一个相继前元（可将这三句话作为建立自然数集合的公理）

引入：

$E(x,y)$ $x=y$ ；
$f(x)$ $x$ 的相继后元；
$g(x)$ $x$ 的相继前元。

那么可以这样表示：

(\forall x) (\exists y) (E (y, f (x)) \land (\forall z) (E (z, f (x)) \to E (y, z)))

$y$ $x$ $z$ $y=z$ .

\neg (\exists x) E (0, f (x))

$0$ .

(\forall x) (\neg E (x, 0) \underset{在 说 有 且 仅 有 一 个 相 继 前 元}{\underset{⏟}{\to (\exists y) (E (y, g (x)) \land (\forall z) (E (z, g (x)) \to E (y, z))}}))

谓词变元多次量化和公式表示法

\begin{array}{l} (\forall x) (\forall y) P (x, y) = (\forall x) ((\forall y) P (x, y)) \\ (\forall x) (\exists y) P (x, y) = (\forall x) ((\exists y) P (x, y)) \\ (\exists x) (\forall y) P (x, y) = (\exists x) ((\forall y) P (x, y)) \\ (\exists x) (\exists y) P (x, y) = (\exists x) ((\exists y) P (x, y)) \end{array}

$(\exists x)(\exists y) P(x,y)=(\exists y)(\exists x) P(x,y),(\forall x)(\forall y) P(x,y)=(\forall y)(\forall x) P(x,y)$

$\{1,2,\cdots,k\}$ ，我们可以枚举：

\begin{array}{l} (\forall x) P (x) = P (1) \land P (2) \land \dots \land P (k) \\ (\exists x) P (x) = P (1) \lor P (2) \lor \dots \lor P (k) \end{array}

$\forall$ $\wedge$ $\exists$ $\vee$ 的推广。

$\{1,2\}$ 上多次量化公式：

(\exists x) (\forall y) P (x, y) = (\forall y) P (1, y) \lor (\forall y) P (2, y) = (P (1, 1) \land P (1, 2)) \lor (P (2, 1) \land P (2, 2))

公式的普遍有效性和判定问题

和命题公式类似，也有三类：

如何理解一个解释，就是将个体变元以具体的事物代之。

$I$ 下真值都为真，便称作 普遍有效的。
$I$ 下真值为真，便称作 可满足的。
$I$ 下真值均为假，便称作 不可满足的。

有限域 上一个公式的可满足性和普遍有效性依赖于个体域个体的个数且仅依赖于个体域个体的数目

$k$ $k$ $k$ 个体域上也普遍有效 (或可满足)；
$k$ $k-1$ 个体域上也普遍有效；
$k$ $k+1$ 个体域上也可满足。

谓词逻辑的判定问题，指的是任一公式的普遍有效性。若说谓词逻辑是可判定的，就要给出一个能行方法，使得对任一谓词公式都能判断其是否普遍有效。

谓词逻辑是不可判定的；
- 对任一谓词公式而言，没有能行的方法判明它是否是普遍有效的
- 并不排除谓词公式有子类是可判定的
- 判定问题的困难在于个体域是个无穷集以及对谓词设定的任意性
个体域有穷的时候，可以遍历每一个个体，因此是可判定的。
只含一元谓词变元的公式是可判定的。

Ch5-谓词逻辑的等值和推理演算

谓词逻辑的等值

$A,B$ $A,B$ $A,B$ 等值。

Theorems 由命题公式移植来的等值式 （命题公式中，直接以谓词公式代入命题变项）

$\neg \neg P(x)= P(x)$
$\neg \neg(\forall x) P(x)=(\forall x) P(x)$
$P(x) \rightarrow Q(x)=\neg P(x) \vee Q(x)$
$(\forall x) P(x) \rightarrow(\exists x) Q(x)=\neg(\forall x) P(x) \vee(\exists x) Q(x)$
$(P(x) \wedge Q(x)) \vee R(x)=(P(x) \vee R(x)) \wedge(Q(x) \vee R(x))$
$((\forall x) P(x) \wedge Q(y)) \vee(\exists z) R(z)=((\forall x) P(x) \vee(\exists z) R(z)) \wedge(Q(y) \vee(\exists z) R(z))$

Theorems 否定型等值式（摩根律）

\begin{array}{l} \neg (\forall x) P (x) = (\exists x) \neg P (x) & (\forall x) P (x) = \neg (\exists x) (\neg P (x)) \\ \neg (\exists x) P (x) = (\forall x) \neg P (x) & (\exists x) P (x) = \neg (\forall x) (\neg P (x)) \end{array}

$x$ $x$ 不成立。

Examples

$A(x)$ $x$ $B(x)$ $x$ 是猫。

$\neg (\forall x)(A(x)\to B(x))$ .
$(\exists x) \neg(\neg A(x)\vee B(x))=(\exists x)(A(x)\wedge \neg B(x))$ .

$F(x)$ $x$ $G(x,y)$ $x,y$ 一般黑。

$(\forall x)(F(x)\wedge (\forall y)(F(y)\to G(x,y)))$ .
$(\forall x)(\forall y) F(x)\wedge F(y)\to G(x,y)$ .
$\neg (\exists x)(\exists y)(F(x)\wedge F(y)\wedge \neg G(x,y))$ .
$(\forall x)(\forall y)\neg(F(x)\wedge F(y)\wedge \neg G(x,y))=(\forall x)(\forall y)(\neg(F(x)\wedge F(y))\vee G(x,y))=(\forall x)(\forall y) F(x)\wedge F(y)\to G(x,y)$

Theorems 量词对合取、析取的分配律 $q$ $x$ ，则：

\begin{array}{l} (\forall x) (P (x) \lor q) = (\forall x) P (x) \lor q \\ (\exists x) (P (x) \lor q) = (\exists x) P (x) \lor q \\ (\forall x) (P (x) \land q) = (\forall x) P (x) \land q \\ (\exists x) (P (x) \land q) = (\exists x) P (x) \land q \end{array}

\begin{array}{l} (\forall x) (P (x) \land Q (x)) = (\forall x) P (x) \land (\forall x) Q (x) \\ (\exists x) (P (x) \lor Q (x)) = (\exists x) P (x) \lor (\exists x) Q (x) \end{array}

$\forall$ $\vee$ $\exists$ $\wedge$ 的分配率一般不成立。

Problem $(\forall x)(P(x)\vee Q(x))\not=(\forall x)P(x)\vee(\forall x)Q(x)$ .

Proof $\{1,2\}$ $P(1)=1,P(2)=0,Q(1)=0,Q(2)=1$ ，则不成立。

Problem $(\forall x)P(x)\vee(\forall x)Q(x) \Rightarrow (\forall x)(P(x)\vee Q(x))$ .

Proof $(\forall x)P(x)$ $(\forall x)Q(x)$ 成立。

Problem $(\exists x)(P(x)\wedge Q(x))\not=(\exists x)P(x)\wedge (\exists x)Q(x)$ . 和上面举例相同。

Problem $(\exists x)(P(x)\wedge Q(x))\Rightarrow(\exists x)P(x)\wedge (\exists x)Q(x)$ ,

Proof $P(a)\wedge Q(a)$ $P(a),Q(a)$ $(\exists x)P(x)$ $(\exists x)Q(x)$ 均成立。

$\boldsymbol{\to}$ 的分配律

\begin{array}{l} (\forall x) (P (x) \to q) = (\exists x) P (x) \to q \\ (\exists x) (P (x) \to q) = (\forall x) P (x) \to q \\ (\forall x) (p \to Q (x)) = p \to (\forall x) Q (x) \\ (\exists x) (p \to Q (x)) = p \to (\exists x) Q (x) \end{array}

Proof（1.）

(\forall x) (\neg P (x) \lor q) = (\forall x) (\neg P (x)) \lor q = \neg (\exists x) P (x) \lor q = (\exists x) P (x) \to q

$(\exists x)P(x)$ $q$ $(\forall x)(P(x)\to q)$ 。

Theorems 变元易名后的分配律

\begin{matrix} (\forall x) (\forall y) (P (x) \lor Q (y)) = (\forall x) P (x) \lor (\forall x) Q (x) \\ (\exists x) (\exists y) (P (x) \land Q (y)) = (\exists x) P (x) \land (\exists x) Q (x) \\ (\forall x) (\forall y) (P (x) \land Q (y)) = (\forall x) P (x) \land (\forall x) Q (x) \\ (\exists x) (\exists y) (P (x) \lor Q (y)) = (\exists x) P (x) \lor (\exists x) Q (x) \end{matrix}

Proof（1.） $(\forall x)P(x)\vee (\forall y)Q(y)$ $q$ ，则：

(\forall x) (P (x) \lor (\forall y) Q (y))

因此：

(\forall x) (\forall y) (P (x) \lor Q (y))

谓词逻辑的范式

Definition 前束范式 $A$ $A$ 的一般形式为：

(Q_{1} x_{1}) \dots (Q_{n} x_{n}) M (x_{1}, \dots, x_{n})

$Q_i$ $M$ $A$ $M$ 中不再有量词。

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

$\exists$ 前束范式 $\exists$ $(\exists x_1)\cdots (\exists x_i)(\forall x_{i+1})\cdots (\forall x_n) M(x_1,\cdots,x_n)$ $M(x_1,\cdots,x_n)$ 不含量词和自由个体变元。

$A$ $\exists$ $A$ 普遍有效 $\exists$ 范式是 普遍有效 的。

Problem $(\exists x)(\forall y)(\exists u)P(x,y,u)$ $\exists$ 前束范式（P 中无量词）。

Solution $(\forall y)$ $(\exists y)$ $S$ $z$ $S(x,z)$ ，建立公式

(\exists x) (((\exists y) (\exists u) P (x, y, u) \land \neg S (x, y)) \lor (\forall z) S (x, z))

$\exists$ 前束范式仅在普遍有效的意义下与原公式等值，

(\forall y) (F (y) \to G (y)) \to ((\forall y) F (y) \to (\forall z) G (z))

Problem $(\forall x)(P(x)\leftrightarrow (\exists y)Q(x,y))$ 的前束范式。

Solution：

\begin{aligned} (\forall x) (P (x) \leftrightarrow (\exists y) Q (x, y)) \\ = & (\forall x) ((P (x) \to (\exists y) Q (x, y)) \land ((\exists y) Q (x, y) \to P (x))) \\ = & (\forall x) (\exists y) (\forall z) ((P (x) \to Q (x, y)) \land (Q (x, z) \to P (x))) \end{aligned}

Definition Skolem 标准型 仅仅保留全称量词的前束形。

$A$ $A$ 是 不可满足 的当且仅当其 Skolem 标准型是 不可满足 的。

$\exists x$ $P$ $x$ $a$ $\exists x$ $(\forall y)\cdots (\forall z)$ $P$ $x$ $y,\cdots,z$ $f(y,\cdots,z)$ 代入。

Example $(\exists x)(\forall y)(\forall z)(\exists u)(\forall v)(\exists w)P(x,y,z,u,v,w)$ 的 Skolem 标准型.

$x$ $a$ .
$u$ $y,z$ $f(y,z)$ .
$w$ $y,z,v$ $g(y,z,v)$ .

$(\forall y)(\forall z)(\forall v)P(a,y,z,f(y,z),v,g(y,z,w))$ .

$\forall \varepsilon>0,\exists \delta>0,\forall |x-x_0|<\delta,|f(x)-f(x_0)|<\varepsilon$ .
$\delta$ $x_0,\varepsilon$ 的一个函数。

谓词逻辑的基本的推理公式

\begin{matrix} (\forall x) P (x) \lor (\forall x) Q (x) \Rightarrow (\forall x) (P (x) \lor Q (x)) \\ (\exists x) (P (x) \land Q (x)) \Rightarrow (\exists x) P (x) \land (\exists x) Q (x) \end{matrix}

Proof：前面推导过。

\begin{matrix} (\forall x) (P (x) \to Q (x)) \Rightarrow (\forall x) P (x) \to (\forall x) Q (x) \\ (\forall x) (P (x) \to Q (x)) \Rightarrow (\exists x) P (x) \to (\exists x) Q (x) \end{matrix}

Proof $(\forall x)P(x)$ $(\exists x)P(x)$ $(\forall x)(P(x)\to Q(x))$ $(\forall x)Q(x)$ $(\exists x)Q(x)$ 成立。

\begin{matrix} (\forall x) (P (x) \leftrightarrow Q (x)) \Rightarrow (\forall x) P (x) \leftrightarrow (\forall x) Q (x) \\ (\forall x) (P (x) \leftrightarrow Q (x)) \Rightarrow (\exists x) P (x) \leftrightarrow (\exists x) Q (x) \end{matrix}

Proof：和上面证明方法一样，证明双向。

(\forall x) (P (x) \to Q (x)) \land (\forall x) (Q (x) \to R (x)) \Rightarrow (\forall x) (P (x) \to R (x))

Proof：

\begin{aligned} (\forall x) (P (x) \to Q (x)) \land (\forall x) (Q (x) \to R (x)) \\ \Rightarrow & (\forall x) ((P (x) \to Q (x)) \land (Q (x) \to R (x))) \\ \Rightarrow & (\forall x) (P (x) \to R (x)) \end{aligned}

(\forall x) (P (x) \to Q (x)) \land P (a) \Rightarrow Q (a)

\begin{matrix} (\forall x) (\forall y) P (x, y) \Rightarrow (\exists x) (\forall y) P (x, y) \\ (\exists x) (\forall y) P (x, y) \Rightarrow (\forall y) (\exists x) P (x, y) \end{matrix}

Proof：解释性的说明：

$P(x,y)$ $x,y$ $x_0$ $P(x_0,y)$ 成立。
$I$ $(\exists x)(\forall y)P(x,y)=T$ $x_0\in D$ $y\in D$ $P(x_0,y)=T$ $y\in D$ $x$ $x_0$ $P(x,y)=T$ .

谓词逻辑的推理演算

前提引入规则；
结论引用规则；（中间结论可以作为后续推理的前提）
代入规则；（代入重言式的命题变项）
置换规则；（用等值公式置换）
$A\to B$ $A$ $B$ .
$A_1\Rightarrow A_2 \to B$ $A_1\wedge A_2 \Rightarrow B$ 是等价的。

谓词逻辑的推理规则

全称量词消去规则 $(\forall x)P(x)\Rightarrow P(y)$ $y$ $P(x)$ $y$ $P(x)$ 中不能出现，不能使用重复的符号。
全称量词引入规则 $P(y)\Rightarrow (\forall x)P(x)$ $y$ 是论域中任意个体。
存在量词消去规则 $(\exists x)P(x)\Rightarrow P(c)$ $c$ $(\exists x)P(x)$ 中没有自由个体出现。
存在量词引入规则 $P(c)\Rightarrow (\exists x)P(x)$ $c$ $x$ $P(c)$ 里。

$(\forall x)(\exists y)P(x,y)\Rightarrow (\exists y)P(x,y)\Rightarrow P(x,a)$ .
$(\forall x)P(x,a)$ $a$ 都成立。

需要分析好变量之间的依赖关系。

Example：分析下述推理的正确性

$(\forall x)(\exists y)(x>y)$ . 前提;
$(\exists y)(z>y)$ $y$ $z$ 相关;
$z>b$ $b$ $z$ .
$(\forall z)(z>b)$ $b$ $z$ ）

Problem：有的病人喜欢所有的医生：

(\exists x) (P (x) \land (\forall y) (D (y) \to L (x, y)))

没有病人喜欢庸医：

(\forall x) (P (x) \to (\forall y) (Q (y) \to \neg L (x, y)))

推出，没有医生是庸医：

(\forall x) (D (x) \to \neg Q (x))

Solution.

$(\exists x)(P(x) \wedge (\forall y)( D(y)\to L(x,y)))$
$P(c)\wedge (\forall y)(D(y)\to L(c,y))$ .
$(\forall x)(P(x)\to (\forall y) (Q(y)\to \neg L(x,y)))$
$P(c)\to (\forall y) (Q(y)\to \neg L(c,y))$
$P(c)$ 2. 推出
$(\forall y)(D(y)\to L(c,y))$ 2. 推出
$D(y)\to L(c,y)$ 6. 消去
$(\forall y)(Q(y) \to \neg L(c,y))$ . 5. 4. 分离
$Q(y)\to \neg L(c,y)$ . 8. 消去
$L(c,y)\to \neg Q(y)$ . 9. 置换。
$D(y)\to \neg Q(y)$ . 三段论
$(\forall y )(D(y)\to \neg Q(y))$ $y$ 为论域中任何一个个体）

谓词逻辑的归结证明

$A\wedge \neg B=G$ $G$ .
建立子句集。
归结出矛盾。

$(\forall x)(P(x)\to Q(x)) \wedge (\forall x)(P(x)\to Q(x))=(\forall x)(P(x)\to R(x))$ .

$G=(\forall x)(P(x)\to Q(x)) \wedge (\forall x)(P(x)\to Q(x))\wedge \neg (\forall x)(P(x)\to R(x))$

$(\forall x)(P(x)\to Q(x))$ $\{\neg P(x)\vee Q(x)\}$ .
$(\forall x)(Q(x)\to R(x))$ $\{\neg Q(x)\vee R(x)\}$ .
$\neg (\forall x)(P(x)\to R(x))=(\exists x)\neg (\neg P(x)\vee R(x))=(\exists x)(P(x)\wedge \neg R(x))$ .
$\{P(a),\neg R(a)\}$ .

$G$ $\{\neg P(x)\vee Q(x),\neg Q(x)\vee R(x),P(a),\neg R(a)\}$ .

$\neg P(x)\vee Q(x), P(a)$ $Q(a)$ .
$\neg Q(x)\wedge R(x),Q(a)$ $R(a)$ .
$R(a), \neg R(a)$ 矛盾。

$A_1=(\exists x)(P(x) \wedge (\forall y)( D(y)\to L(x,y)))$ .
$A_2=(\forall x)(P(x)\to (\forall y) (Q(y)\to \neg L(x,y)))$ .
$B=(\forall x)(D(x)\to \neg Q(x))$ .

$A_1 \wedge A_2 \Rightarrow B$ $G=A_1\wedge A_2\wedge \neg B$ .

建立子句集：

\begin{matrix} {P (a), \neg D (y) \lor L (a, y)} \\ {\neg P (x) \lor \neg Q (y) \lor \neg L (x, y)} \\ D (b), Q (b) \end{matrix}