离散数学：谓词逻辑

发表于 2020-03-09 更新于 2023-10-11 分类于 math Waline：阅读次数：

谓词逻辑

谓词

Definition

在原子命题中，可以独立存在的客体（句子中的主语、宾语等），成为个体词。而用以刻画客体的心智或者客体之间关系即为谓词。

个体词

Definition

个体词可分为两种，个体常量和个体变量，均在个体域内取值。

表示具体或特定的个体词成为个体常量。一般用带或不带下标的小写英文字母$a,b,c,\cdots,a_1,b_1,c_1,\cdots$等表示

表示抽象或泛指的个体词成为个体变量。一般用带或不带下标的小写英文字母$x,y,z,\cdots,x_1,y_1,z_1,\cdots$等表示

个体词的取值范围称为取值域(或论域)，常用D表示

宇宙间的所有个体域聚集在一起所构成的个体域成为全总个体域。若如特别说明，均使用全总个体域

n元谓词

Definition

设D为非空的个体域，定义在$D^n$（表示n个个体都在个体域D上取值）上取值于｛0，1｝上的n元函数，成为n元命题函数或者n元谓词，记为$P(x_1,x_3,\cdots,x_n)$。其中，个体变量$x_1,x_3,\cdots,x_n \in D$

表示具体性质或关系的谓词成为谓词常量。

表示抽象或泛指的形式或关系的谓词成为谓词变量。

谓词均使用大写英文字母$P,Q,R,\cdots,F,G,G,\cdots$

TIPS

谓词中个体词的顺序是十分重要的，不能随意变更。$F(b,c)\neq F(c,b)$
一元谓词用以描述某一个个体的某种特性，而n元谓词($n\ge2$)则用以描述n个个体之间的关系
谓词$P(x_1,x_2,\cdots,x_n)$包含了个体变量，因而本身并不是命题，只有用谓词常量取代P，用个体常量取代$x_1,x_2,\cdots,x_n$后才会成为命题
一般将没有任何个体变量的谓词成为0元谓词，如$F(a),G(a,b),H(a_1,a_2,\cdots,a_n)$等。当F,G,H为谓词常量时，0元谓词就成为了命题。此时，命题逻辑中的所有命题都可以表示成0元谓词

量词

Definition

全称量词($\forall x$):所有的x；任意的x；一切的x；每一个x；...

存在量词($\exists x$):有些x；至少有一个x；某一些x；存在x；...

其中的x成为作用变量。一般将量词加到其谓词之前，记为$(\forall x)F(x),(\exists x) F(x)$。此时，F(x)成为全称量词和存在量词的辖域。

谓词逻辑符号化的两条规则

统一个体域为全总个体域，而对每一个句子中个体变量的变化范围用一元特性谓词刻画之。这种特性谓词在加入到命题函数中时必定遵循如下原则：

对于全称谓词($ x$),刻画其为个体域的特性谓词作为蕴含式之前件加入

对于存在谓词($ x$),刻划其对应个体域的特性谓词作为合取式只合取项加入

### 量词真值确定

特别的，当个体域$D= \{x_0,x_1,\cdots,x_n \}$是有限集合时，$(\forall x)G(x)$和$(\exists x)G(x)$的真值可以用与之等价的命题公式来进行表示。 \[ (\forall x)G(x)=G(x_0)\wedge G(x_1) \wedge\cdots\wedge G(x_n)\\ (\exists x)G(x)=G(x_0)\vee G(x_1)\vee\cdots\vee G(x_n) \]

谓词合式公式

四类符号

在基于谓词的形式化中，我们将使用如下四种符号：

常量符号：指所属个体域D中的某个元素，用带或不带下标的小写英文字母$a,b,c,\cdots,a_1,b_1,c_1,\cdots$来表示

变量符号：指所属个体域D中的任意元素，用带或不带下标的小写英文字母$x,y,z,\cdots,x_1,y_1,z_1,\cdots$来表示

函数符号：n元函数符号$f(x_1,x_2,\cdots,x_n)$可以是所属个体域集合$D^n \rightarrow D$的任意一个函数，用带或不带下标的小写英文字母$f,g,h,\cdots,f_1,g_1,h_1,\cdots$来表示

谓词符号：n元谓词符号$P(x_1,x_2,\cdots,x_n)$可以是所属个体域$D^n \rightarrow \{0,1 \}$的任意一个谓词，用带或不带下标的大写英文字母$P,Q,R,\cdots,P_1,Q_1,R_1,\cdots$来表示

项

Definition

谓词逻辑中的项(Term),被递归地定义为：

任意的常量符号或任意的变量符号是项；

若$f(x_1,x_2,\cdots,x_n)$是n元函数符号，$t_1,t_2,\cdots,t_n$是项，则$f(t_1,t_1,\cdots,t_n)$是项；

仅由有限次使用以上两个规则产生的符号串才是项。

合式公式

Definition

若$P(x_1,x_2,\cdots,x_n)$是n元谓词，$t_1,t_2,\cdots,t_n$是项，则$P(t_1,t_1,\cdots,t_n)$为原子谓词公式，简称原子公式。

Definition

满足下列条件的表达式，成为合式公式(well-formed formulae/wff)，简称公式。

原子公式是合适公式；

若G，H是合式公式，则$(\neg G),(\neg H),(G \vee H),(G \wedge H),(G \rightarrow H),(G \leftrightarrow H)$也是合式公式

若G是合式公式，x是个体变量，则$(\forall x)G,(\exists x)G$也是合式公式

由有限次使用以上三个规则产生的表达式才是合式公式

tips

公式的最外层括号可以省略；

量词后面括号省略方式为：一个量词的辖域仅出现一个原子公式，则此辖域的外层括号可省略，否则不能省略；

一个个体词只能接受一个量词的约束，否则是没有意义的。

自由变元与约束变元

Definition

给定一个合式公式G，若变元在使用变元的量词的辖域之内，则成为变元x的出现为约束出现，此时的变元x称为约束变元。若x的出现不是约束出现，则称它为自由出现，此时的变元x成为自由变元。

规则1：约束变元的改名规则

将量词中的变元以及该量词辖域中此变量之所有约束出现都用新的个体变元替换；

新的变元一定有别于改名辖域的所有其他变量。

规则2：自由变元的代入规则

将变元中出现改自由变元的每一处都用新的个体变元替换；

新的变元不允许在原公式以任何约束形式出现。也可用个体常量代入。

闭式

Definition

设G是任意一个公式，若G中无自由出现的个体变元，则称G为封闭的合式公式，简称闭式。

白话：所有个体都有量词约束

闭式是一个命题

公式的解释与分类

公式的解释

Definition

谓词逻辑中公式G的每一个解释I由如下四部分组成：

非空的个体域D；

G中的每一个常量符号，指定D中的特定的元素；

G中的每个n元函数符号，指定$D^n$到D中某个特定的函数；

G中的每个n元谓词符号，指定$D^n$到{0,1}中的某个特定的谓词。

规定：公式中无自由变元，或将自由变元看成变量符号。

公式的分类

Definition

如果公式G在它的所有解释下都取值为真，则称G为有效公式。

如果公式G在它的所有解释下都为假，则称G为矛盾公式

如果至少有一种解释使得公式G取值为真，则称G为可满足公式

谓词公式的可判定性

谓词逻辑是不可判定的；

只含有一元谓词变项的公式是可判定的

如下形式的公式： \[ (\forall x_1)(\forall x_2)\cdots(\forall x_n)P(x_1,x_2,\cdots,x_n),\\ (\exists x_1)(\exists x_2)\cdots(\exists x_n)P(x_1,x_2,\cdots,x_n) \] 若P中无量词和其他自由变元时，也是可以判定的；

个体域有穷时的谓词公式是可判定。

公式的等价关系

等价

Definition

如果公式$G\leftrightarrow H$是有效公式，则公式G，H成为等价的，记为G=H。

Definition

设$G(P_1,P_2,\cdots,P_n)$是命题演算中的命题公式，$P_1,P_1,\cdots,P_n$是出现在G中的命题变元，当用任意的谓词公式$G_i(1\le i \le n)$分别代入$P_i$后，得到的新谓词公式$G(G_1,G_2,\cdots,G_n)$称为原公式的代入实例。

Theorem

永真公式的任意一个代入实例必为有效公式

tip

命题盐酸中的基本等价公式$E_1——E_24$在谓词演算中仍然成立

Theorem

假设G(x),H(x)是只含有自由变元的公式，S是不含x的公式，则在总全个体域中，有

公式名称

$E_{25}:(\exists x)G(x)=(\exists y)G(y)$
$E_{26}:(\forall x)G(x)=(\forall y)G(y)$ 改名规则

$E_{27}:\neg(\exists x)G(x)=(\forall x)\neg G(x)$
$E_{28}:\neg (\forall x)G(x)=(\exists x)\neg G(x)$ 量词转换率
量词否定等价式

$E_{29}:(\forall x)(G(x)\vee S)=(\forall x)G(x)\vee S$
$E_{30}:(\forall x)(G(x)\wedge S)=(\forall x)G(x)\wedge S$
$E_{31}:(\exists x)(G(x)\vee S)=(\exists x)G(x)\vee S$
$E_{32}:(\exists x)(G(x)\wedge S)=(\exists x)G(x)\wedge S$ 量词辖域的扩张与收缩率

$E_{33}:(\forall x)(G(x)\wedge H(x))=(\forall x) G(x)\wedge (\forall x)H(x)$
$E_{34}:(\exists x)(G(x)\vee H(x))=(\exists x)G(x)\vee(\exists x)H(x)$ 量词分配率

$E_{35}:(\forall x)G(X)\vee(\forall x)H(x)=(\forall x)(\forall y)(G(x)\vee G(y))$
$E_{36}:(\exists x)G(x)\wedge(\exists x)H(x)=(\exists x)(\exists y)(G(x)\wedge H(y))$

$E_{37}:(\forall x)(\forall y)G(x,y)=(\forall y)(\forall x)G(x,y)$
$E_{38}:(\exists x)(\exists y)G(x,y)=(\exists y)(\exists x)G(x,y)$

公式	名称
\(E_{25}:(\exists x)G(x)=(\exists y)G(y)\) \(E_{26}:(\forall x)G(x)=(\forall y)G(y)\)	改名规则
\(E_{27}:\neg(\exists x)G(x)=(\forall x)\neg G(x)\) \(E_{28}:\neg (\forall x)G(x)=(\exists x)\neg G(x)\)	量词转换率量词否定等价式
\(E_{29}:(\forall x)(G(x)\vee S)=(\forall x)G(x)\vee S\) \(E_{30}:(\forall x)(G(x)\wedge S)=(\forall x)G(x)\wedge S\) \(E_{31}:(\exists x)(G(x)\vee S)=(\exists x)G(x)\vee S\) \(E_{32}:(\exists x)(G(x)\wedge S)=(\exists x)G(x)\wedge S\)	量词辖域的扩张与收缩率
\(E_{33}:(\forall x)(G(x)\wedge H(x))=(\forall x) G(x)\wedge (\forall x)H(x)\) \(E_{34}:(\exists x)(G(x)\vee H(x))=(\exists x)G(x)\vee(\exists x)H(x)\)	量词分配率
\(E_{35}:(\forall x)G(X)\vee(\forall x)H(x)=(\forall x)(\forall y)(G(x)\vee G(y))\) \(E_{36}:(\exists x)G(x)\wedge(\exists x)H(x)=(\exists x)(\exists y)(G(x)\wedge H(y))\)
\(E_{37}:(\forall x)(\forall y)G(x,y)=(\forall y)(\forall x)G(x,y)\) \(E_{38}:(\exists x)(\exists y)G(x,y)=(\exists y)(\exists x)G(x,y)\)

前束范式

Definition

称公式G是一个前束范式，如果G中的一切量词都位于该公式的最前端（不含否定词）且这些量词的辖域都延伸到公式的末端。其标注形式如下： \[ (Q_1x_1)(Q_2x_2)\cdots(Q_nx_n)M(x_1,x_2,\cdots,x_n) \] 其中$Q_i$为量词$\forall 或\exists(i=1,\cdots,n)$,M称作公式G的母式（基式），M中不再有量词。

求解步骤

消去公式中的联结词$"\rightarrow","\leftrightarrow"$（如果有的话）；
反复运用量词转换率，德摩根律和双重否定率，直到将多有的$\neg$都内移到原子谓词公式的前端；（量词转换率）
使用谓词的等价公式将所有的量词提到公式的最前端并保证其辖域直到公式的末端。（改名规则）（量词分配率）（量词辖域的扩张与收缩率）

推理形式和推理规则

推理形式

Definition

设$G_1,G_2,\cdots, G_n,H$是公式，称H是$G_1,G_2,\cdots,G_n$的逻辑结果(或称$G_1,G_2,\cdots,G_n$共同蕴含H)当且仅当对任意解释I，若I同时满足$G_1,G_2,\cdots,G_n$，则I满足H，记为$G_1,G_2,\cdots,G_n\Rightarrow H$，此时称为$G_1,G_2,\cdots,G_n\Rightarrow H$是有效的，否则称为无效的。$G_1,G_2,\cdots,G_n$称为一组前提(premise),有时候集合$\Gamma$来表示，记为$\Gamma = \{G_1,G_2,\cdots,G_n \}$,H称为结论(conclusion),又称H是前提集合$\Gamma$的逻辑结果，记为$\Gamma \Rightarrow H$。

Theorem

设$G_!,G_2,\cdots,G_n,H$是公式，公式H是前提集合$\Gamma = \{G_1,G_2,\cdots,G_n \}$的逻辑结果当且仅当$G_1\wedge G_2 \wedge\cdots\wedge G_n\rightarrow H$为有效公式。

命题验算中的基本蕴含公式$I_1-I_{11}$在谓词验算中仍然成立

推理规律

Theorem

假设G(x),H(x)是只包含自由变元x的公式，则在全总个体域中，有

$I_{12}:(\forall x)G(x)\Rightarrow (\exists x)G(x)$

$I_{13}:(\forall x)G(x)\vee (\forall x)H(x)\Rightarrow(\forall x)(G(x)\vee H(x))$

$I_{14}:(\exists x)(G(x)\wedge H(x))\Rightarrow (\exists x)G(x)\wedge (\exists x)H(x)$

$I_{15}:(G(x)\rightarrow H(x))\Rightarrow (\forall x)G(x)\rightarrow(\forall x)H(x)$

$I_{16}:(\forall x)(G(x)\rightarrow H(x))\Rightarrow (\exists x)G(x)\rightarrow(\exists x)H(x)$

$I_{17}:(\exists x)(\forall y)G(x,y)\Rightarrow(\forall x)(\exists y)G(x,y)$

$I_{18}:(\forall x)(\forall y)G(x,y)\Rightarrow(\exists y)(\exists x)G(x,y)$

$I_{19}:(\forall y)(\forall x)G(x,y)\Rightarrow(\exists x)(\forall y)G(x,y)$

$I_{20}:(\exists y)(\forall x)G(x,y)\Rightarrow(\forall x)(\forall y)G(x,y)$

$I_{21}:(\forall x)(\exists y)G(x,y)\Rightarrow(\exists y)(\exists x)G(x,y)$

$I_{22}:(\forall y)(\exists x)G(x,y)\Rightarrow(\exists x)(\exists y)G(x,y)$

全称特指规则

US(全称特指规则)：

$(\forall x)G(x)\Rightarrow G(y)$,y不在G(x)中约束出现

或$(\forall x)G(x)\Rightarrow G(c)$,c为任意个体常量

存在特指规则

ES(存在特指规则)：

$(\exists x)G(x)\Rightarrow G(c)$,c为使得G(c)为真的特定的个体常量。当G(x)中还有除x以外的自由变元，则必须用关于这些变元的函数符号来取代c。

全称推广规则

UG(全称推广规则)：$G(x)\Rightarrow (\forall x)G(x)$,G(y)中无变元想

存在推广规则

EG(存在推广规则)：

$G(c)\Rightarrow (\exists x)G(x)$,c为特定个体变量

或：$G(y)\Rightarrow(\exists x)G(x)$,G(y)中无变元x

综合推理方法

假定推导过程都是在相同的个体域内进行（通常是全总个体域）。

综合推理方法

推导过程中可以引用命题验算中的规则P和规则T；

如果结论是以条件形式或析取形式给出，则可使用规则CP；

若需消去量词，可以引用规则US和规则ES；

当所有结论为定量时，可引用规则UG和规则EG引入量词；

证明时可采用如命题验算中的直接证明方法或间接证明方法；

在推导过程中，对消去量词的公式或公式中不含量词的子公式，可以引用命题验算中的基本等价公式和基本蕴含公式；

在推导过程中，对含有量词的公式可以引用谓词中的基本等价公式和基本蕴含公式。

难点总结

在推导过程中，如既需要使用规则US又要使用规则ES消去量词，而且选用的个体是同一个符号，则必须先使用规则ES，在使用规则US。然后再使用命题验算中的推理规则，最后使用规则UG或规则EG引入量词，得到所求结论。

如一个变量用规则ES消去量词，对该变量在添加量词是，则只能使用规则EG；如使用规则US消去量词，对该变量在添加量词时，则可使用规则EG和规则UG。

在用规则US和规则ES消去量词时，此量词必须位于整个公式的最前端，且辖域为其后的整个公式。

在添加量词$(\forall x)$和$(\exists)$时，所选用的x不能再公式G(y)或G(c)中出现、