谓词逻辑/一阶逻辑

使用了wiki内容和自己翻译了一部分英文和德文的教材,整理后作为笔记,公开出来给各位.德文可以无视.如果有错误非常希望各位能指出来!

语义和语法(Syntax und Semantik)

这一段很重要,否则后文无法理解

符号(Zeichenvorrat)

Individuenvariablen(个体变量): x,y,z或者带下标x1,x2…
Individuenkonstanten(个体常量): a,b,c或者带下标a1,a2…
Funktionssymbole(函数符号): f,g,h或者带下标
Prädikatssymbole(断言符号): P,Q,R或者带下标
Junktoren(逻辑符号):$\lor \land \lnot \dots$
Quantoren(量词): $\forall ,\exists$
Hilfszeichen: 偶尔也会有逗号之类的

项(Terme)

每个个体变量是一个项
每个个体常量是一个项
带有n个元(Stellig)的函数是一个项,而每个元也必须是项(元:可以类比参数,比如f(a,b,c)就有三个元)

注意:项是不能包含断言符号的.

公式(Prädikatenlogische Formeln)

通常用希腊字母表示

如果 t1,t2, … ,tn 为项并且P为n元断言符号,那么$P(t_1,t_2…t_n)$就是一个公式
如果$\alpha$为一个公式,那么$\lnot \alpha$是一个公式
二元运算符连接的公式$\alpha \lor \beta$是公式
如果$\alpha$是公式,$x$为自体变量,那么带有量词如$\forall x \alpha$是公式
等式: 如果$t1,t2$是项,那么$t1=t2$是公式.

例子

比如$\forall x (P(x)\lor S(x))$是公式
而$\forall f \forall x P(x,f(x))$不是公式

优先级(Bindungsregeln)

$\forall, \exists,\lnot$强于$\land$
$\land > \lor > \to > \leftrightarrow$

所以有$\forall x P(x) \lor Q(x)$, 解释为$(\forall x P(x)) \lor Q(x)$

作用域(辖域Wirkungsbereich)

一个变量可以和多个量词连接,如下:

$\forall x \exists y (P(x,y)\land \exists x (Q(x,x)\lor S(y)))$

但是这样:$P(x) \land \exists x(S(x))$后面的那个存在x就管不着P(x)了

还有这样:

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

这种情况”所有x”管不到Q那里

一些名词

一个变量在作用域内被称为约束变元(gebunden)
一个变量不在作用域内被称为自由变元(Feien Variablen????)
一个公式不存在自由变元,被称为闭式(geschlossene Formel),而这才是命题.

改名

(在这里我用B来表示这个解释函数)

约束变元:
- 在同一个作用域下的同名约束变元要改名,同步改.
- 不能和别的重名
自由变元:
- 整个公式里的同名的同步改名.
- 不能和别的重名
- $\exists xB(x) = \exists yG(y)$
- $\forall x B(x) = \forall y B(y)$

公式解释(Interpretation von Formeln)

(在这里我用B来表示这个解释函数)

规则与推导

$B(P(t_1,\dots,t_n))\leftrightarrow P(B(t_1),\dots,B(t_n))$
$B(\lnot \alpha) = w$ 那么 $B(\alpha) = f$
$B(\alpha \land \beta) = w$ 那么 $B(\alpha)=w,B(\beta) = w$, “或”同理

一些基本概念(Grundbegriffe)

与命题逻辑类似,设$\alpha$是一个谓词逻辑公式

erfüllbar可满足:一个解释存在$B(\alpha) = True$
falsifizierbar可证伪:一个解释存在$B(\alpha) = False$
widerspruchvoll矛盾:一个公式所有解释都$B(\alpha)=False$
tautologisch重言:对于所有解释$B(\alpha) = True$

所以有:如果$\alpha$是矛盾的,那么它不可满足,$\lnot \alpha$重言,并且不可证伪.

语义推论(Semantische Folgerung)

同样和命题逻辑类似:

Semantischer Folgerungsbegriff

设$\alpha,\beta$为谓词逻辑公式,那么存在$\alpha \models \beta$

$\alpha \models \beta$,那么$\alpha \land \lnot \beta$矛盾
$\alpha$矛盾,那么对于所有$\beta$存在$\alpha \models \beta$

演绎推论(Deduktionstheorem)

(没有详细写,见wiki)
设alpha和beta是谓词公式,M是一个如此的公式集合,那么存在:
$M \cup {\alpha } \models \beta \Longrightarrow M \models (\alpha \rightarrow \beta)$

逻辑等价(Logische Äquivalenz)

也类似于命题逻辑
设Alpha和Beta是谓词公式并且等价,写做:$\alpha \approx \beta$

这意味着$B(\alpha) = B(\beta)$.
和
$\alpha \models \beta, \beta \models \alpha$

转化规则(Umformungsregeln)

基本规则

这边的规则和命题逻辑那篇一样.但是我还是决定重写一遍.中文翻译见命题逻辑.
设$\alpha,\beta,\gamma$为PL1公式,那么存在以下规则:

Vererbung
- $\alpha \approx \beta \Longrightarrow \lnot \alpha \approx \lnot \beta$
- $\alpha \approx \beta \Longrightarrow \gamma \land \alpha \approx \gamma \land \beta,\quad \gamma \lor \alpha \approx \gamma \lor \beta$
- $\alpha \approx \beta \Longrightarrow \exists x \alpha \approx \exists x \beta , \quad \forall x \alpha \approx \forall x \beta$
Negation: $\lnot\lnot \alpha \approx \alpha$
Idempotenz:
- $\alpha \lor \alpha \approx \alpha$
- $\alpha \land \alpha \approx \alpha$
Neutrales Element:
- $(\alpha \land \lnot \alpha) \lor \beta \approx \beta$
- $(\alpha \lor \lnot \alpha) \land \beta \approx \beta$
Kontrad. /Tautol.
- $(\alpha \land \lnot \alpha) \land \beta \approx \alpha \land \lnot \alpha$
- $(\alpha \lor \lnot \alpha) \lor \beta \approx \alpha \lor \lnot \alpha$
Kommutativität
- $\alpha \lor \beta \approx \beta \lor \alpha$
- $\alpha \land \beta \approx \beta \land \alpha$
Assoziativität
- $(\alpha \lor \beta) \lor \gamma \approx \alpha \lor (\beta \lor \gamma)$
- $(\alpha \land \beta) \land \gamma \approx \alpha \land (\beta \land \gamma)$
Distributivität
- $(\alpha \land \beta) \lor \gamma \approx (\alpha \lor \gamma) \land (\beta \lor \gamma)$
- $(\alpha \lor \beta) \land \gamma \approx (\alpha \land \gamma) \lor (\beta \land \gamma)$
De morgan
- $\lnot(\alpha \land \beta) \approx \lnot \alpha \lor \lnot \beta$
- $\lnot (\alpha \lor \beta ) \approx \lnot \alpha \land \lnot \beta$
Absorption
- $\alpha \land (\alpha \lor \beta) \approx \alpha$
- $\alpha \lor (\alpha \land \beta) \approx \alpha$

带有量词的规则

Quantorenwechsel:$\lnot(\exists x \alpha) \approx \forall x (\lnot \alpha) \quad \lnot (\forall x \alpha) \approx \exists x (\lnot \alpha)$(量词转换)
Quantortausch: $\exists x \exists y \alpha \approx \exists y \exists x \alpha$ ($\forall,\exists$均适用)
Quantorenzusammenfassung: $\exists x \alpha \lor \exists x \beta \approx \exists x (\alpha \lor \beta)$($\forall,\exists$均适用)(量词分配)
Quantorelimination: 当x不是Alpha中自由变量(元)$\exists x \alpha \approx \alpha \quad \forall x \alpha \approx \alpha$
Quantifizierung:当x不是Beta中自由变量(元) $\exists x \alpha \land \beta \approx \exists x (\alpha \land \beta)$ ($\forall,\exists$均适用,替换全部的$\land,\lor$也适用)(量词扩张\收缩率)

范式(Normalformen)

否定范式(Negationsnormalform, NNF)

定义

这里定义什么的见命题逻辑部分

转换

$\lnot \lnot \alpha \Longrightarrow \alpha$(Negation)
$\lnot (\alpha \land \beta) \Longrightarrow \lnot \alpha \lor \lnot \beta$(de Morgan)
$\lnot (\exists y \alpha) \Longrightarrow \forall y\lnot \alpha$(Quantorenwechsel)

前束范式(Pränexe Normalform, PNF)

定义

如果它可以被写为量词在前，随后是被称为母体的无量词部分的字符串。(wikipedia)

简单的理解就是把所有量词提前,量词作用域覆盖了整个公式(不知道这样理解对不对)
比如:$\forall x \exists y \forall z (P(x,y) \lor H(y,z))$

因为有量词扩张/收缩率,并且可以改名,所有的经典逻辑公式都可以转换为等价的PNF

转换

举例,来自某大学讲义:

$\forall x \lnot P(x) \land \forall x (P(x) \lor R(x)) \land \forall x( Q(x)\land \exists y R(y))$

$\approx \forall x_1 \lnot P(x_1) \land \forall x_2 (P(x_2)\lor R(x_2)) \land \forall x (Q(x) \land \exists y R(y))$(改名)

$\approx x_q \lnot P(x_1) \land \forall x_2 (P(x_2) \lor R(x_2)) \land \forall x \exists y (Q(x) \land R(y))$

$\approx \forall x_1 \lnot P(x_1) \land \forall x_2 \forall x \exists y ((P(x_2) \lor R( x_2 )) \land (Q(x) \land R(y)))$

$\approx \forall x_1 \forall x_2 \forall x \exists y (\lnot P(x_1) \land (P(x_2) \lor R(x_2)) \land (Q(x) \land R(y)))$

斯科伦范式(Skolem Normalform, SKNF)

定义

若一个式子$\alpha$是斯科伦范式,那么$\alpha = \forall x_1 \dots \forall x_n \beta$,此处的beta没有量词.同时,此时Alpha的量词中不含存在量词

有点晦涩啊,看看wiki

一阶逻辑的公式是Skolem 范式的，如果它的前束范式只有全称量词。(wikipedia)

相较于命题逻辑:

定义:可满足等价(Erfüllbarkeits-Äquivalenz)

若两个谓词公式Alpha和beta可满足等价,写做$\alpha \approx _{sat} \beta$,意味着:当alpha可满足的时候beta也是可满足.