逻辑2:命题逻辑,范式,归结

这节笔记接着上一篇命题逻辑和语义后承

如果阅读过程出现理解困难,请点上面链接看第一篇的名词.

重要概念:文字和子句

都是一些名词, 概念不难但是如果不记住这些词的话,后面内容可能难以阅读.

文字(Literal)

这里的文字是指一个原子公式atom,或它本身的否定,比如: $A$

而它的否定和肯定也有名词,如下:

肯定文字(positives Literal)

比如 $A$

否定文字(negatives Literal)

比如$\lnot A$

子句(Klausel, Disjunktionsterm, Disjunktionsglied)

kurzgesagt, in a nutshell, 简而言之就是文字的析取

Disjunktion von Literalen

比如$\alpha_1\lor\alpha_2 \lor\dots \lor \alpha_n$

K-子句(K-Klausel)

就是带有k个文字的子句

Unit-Klausel

Klausel, die aus einem Literal besteht
单文字子句

Monom(auch Konjunktionsterm)

文字的合取,中文译名不知道XD

范式(Normalformen)

否定范式(NNF:Negationsnormalform)

否定范式这个词是我根据日语(否定標準形)自己造的,不知道对不对

定义

• 一个式子$\alpha$
• 没有等价和蕴涵的符号
• 每个非运算符都直接和一个原子公式连接

例子

比如$(\lnot A \lor Y)\land (\lnot A \lor B)$这就是一个NNF,否定范式.

反例:

$\lnot\lnot A$和$\lnot(A\lor B)$就不是NNF. 前者一个非操纵符和另一个非操作符连接,后者接括号上了.

然而每个式子都存在一个等价的NNF
比如上面的反例,前者可以使用对合律, 后者可以使用德摩根定律把非操作符放到每个的前面.

合取范式(KNF, Konjunktive Normalform)

定义

设$\alpha1, \alpha2\dots\alpha_n$都是子句,那么$\alpha = \alpha1 \land \alpha2 \land \dots \land \alpha_n$为合取范式.

简而言之, 就是合取所有的子句. 先把所有原子析取,再合取.

同样,每个式子(Formel)都可以转化成为等价自身的KNF(通过双重否定,德摩根,分配率)

也存在一个问题就是程序处理这种转换可能会有2的n次方个子句,造成困难.

例子

比如$\alpha = {(A\lor B)\land (C\lor D)}$

析取范式(DNF, Disjunktive Normalform)

定义

和合取范式正好相反, 是对Monom的析取.同样的,每个式子也都可以转化为自身所等价的DNF.

归结/消解原理(Resolution)

为了方便理解,放上英文wiki的图:

本质上是取合取范式,利用上面提到的规则(见上一篇文章的语义后承的重要规则一节)对其进行化简. 如图中的a和非a就是所谓的互补对.

而两个子句中存在文字可以构成互补对的情况下,便可以化去,剩下的文字可以构建成一个新的子句.

如上图所示,横线之上两个子句中的文字a构成的互补对可以化去.在横线之下构成一个新的子句