基础概念

符号

$\rightarrow$ 或者 $\Rightarrow$：实质蕴含，如果…那么…（连接两个子句，是命题逻辑连接词）
$\models$ : 语句蕴含、逻辑蕴含、逻辑推论，连接两个语句
如果$\beta$语句在所有$\alpha$语句为真的世界中都为真，则$\alpha$蕴含$\beta$
等价定义（$\alpha 、\beta$是两个语句）
$\alpha \models \beta$
$\alpha \Rightarrow \beta$是有效的(valid)
$\alpha \land \neg \beta$是不可满足的(unsatisfiable)
$M(KB) \subseteq M(\alpha)$
- 一个知识库$KB$是可满足的当且仅当这个知识库的模型$M(KB)$是非空集合。即，一个知识库$KB$是不可满足的当且仅当这个知识库的模型$M(KB)$是空集。
区分$\Rightarrow$和$\models$
1. $\Rightarrow$(Entailment)，逻辑上的概念，刻画两组sentence之间的关系
  - 语句P$\Rightarrow$Q只有当$P=true，Q=false$时为$False$，其余为$True$
  - $P \Rightarrow Q$等价于$\neg P∨Q$
    命题逻辑不要求P和Q之间存在相关性或因果关系。不要有P为真则Q为真的错觉
    例如，语句“5是奇数蕴含北京是中国的首都”是命题逻辑的真语句
    前提为假的任意蕴含都为真
2. $\models$（Implication）命题之间的一种运算子，使用真值表刻画其语义。
  - 逻辑蕴含关系类似于算术：语句$x=0$蕴含了语句$xy=0$
  - $α \models β$当且仅当在使$α$为真的每个模型中，$β$也为真。
  - $α \models β$ 当且仅当 $M(α) ⊆ M(β)$
    例如$M(x=0)$与$M(xy=0)$,$x=0$的指派是$xy=0$的指派的子集（$xy=0$多了关于$y$的指派）
  - $P \Rightarrow Q$为假，除非P在m中为真且Q在m中为假
  - 对任意语句$α$和$β$，$α \models β$ 当且仅当语句α$\Rightarrow$β是有效的
  - 对任意语句$α$和$β$，$α \models β$ 当且仅当语句$α∧ \neg β$是不可满足的
$\vdash$ : 推出
$\alpha \vdash \beta$表示$\beta$是由$\alpha$形式可推演的
形式可推演关系是$\alpha$(作为前提的公式\命题\句子)和$\beta$(作为结论的公式\命题\句子)之间的关系，可以读作推出
$\vdash$不是形式语言中的符号，$\alpha \vdash \beta$不是形式语言中的公式
$\alpha \vdash \beta$是关于$\beta$是由$\alpha$的命题

逻辑推论$\models$和形式推演$\vdash$区别：
前者属于语义、后者属于语法

可靠性(soundness)和完备性(completeness)

对于一个算法来说，如果永远不会返回一个错误的结果，那么这个算法就是可靠的(sound)
对于任意输入，这个算法总能返回的结果总能覆盖所有正确的解，那么这个算法就是完备的(complete)

换言之，如果假设算法要得到正确的结果，可靠性即避免假阳性（False Positive）结果，完备性则避免了假阴性（False Negative）

两个问题：

它的推理都是有效的吗？或者说，当前提为真时，它推理得到的结论都是真的吗？
用它能得到所有的有效推理吗？

第一个问题叫可靠性问题：从$Γ⊢A$，能否得到$Γ⊨A$？
第二个叫完全性问题：从$Γ⊨A$，能否得到$Γ⊢A$？

$Γ$表示命题集（可以是空集）
$Γ⊢A$，表示从$Γ$推出$A$
$Γ⊨A$，表示如果$Γ$中的每个命题都真，则$A$真

推理的可靠和完备

可靠的推理算法只生成被蕴含的语句
完备的推理算法生成所有被蕴含的语句

举例：

设计规则，在一堆木棍和2根针组成的堆里寻找针。

如果根据规则能找出1根针，那么这个规则就是可靠但不完备的
因为给出的答案没有错，但是并没有覆盖所有正确的解（不会把假的说成真的，但真的可能不完全）
如果答案中包含2根针但是同时包含有木棍，这个规则就是完备但不可靠的
因为给出的答案覆盖了所有正确解，但是也包含了错误解（把真的都说完全，但还包含了假的）
如果答案中仅包含2根针，那么这个规则就是可靠并完备的

命题逻辑系统

由语法和语义两部分组成
一旦定义了语法和语义，整个逻辑系统也就构建好了

语法:一些规则的集合
- 一旦这些规则被从现实世界中剥离出来，它们就有了一定程度的独立性，不信赖于具体的含义
- 例如，”我　吃　饭”，和 “饭　吃　我”都符合主谓宾结构，后者不正确是因为表达的意思不正确，是语义层面，而不是语法层面
推理和推理的有效性 (此部分还需核实)

什么是推理
$\varphi_1,\varphi_2,…,\varphi_n \vdash \psi$就叫一次推理(sequent).其中$\varphi_i$叫做前提(premise),$\psi$叫做结论(conclusion).
例如，下面这个形式就叫一次推理
$p, ¬¬(q ∧ r) \vdash ¬¬ p ∧ r$

语义:语言所表达的含义,句子的含义

在命题逻辑中的“句子结构”，例如: $\phi \wedge \psi$

定义公式取值的集合：${T, F}$,$T$代表真，$F$代表假

有了取值集合，我们就可以定义自己的“句子”了：

$T ∧ F$

$T ∨ T$

$T → F$

$…$

句子的含义是一个集合，在命题逻辑里，“句子含义”的集合定义为句子的真假，即${T,F}$
真值表

将句子与句子的含义映射起来，即将 $T ∧ F$ 等句子与 $T, F$映射起来
有了真值表，我们才知道 $T ∧ F$ 意味着什么，$ F → T $意味着什么

逻辑 logic in general

1.知识库KB的完备性、可靠性

一个知识库KB就是句子构成的集合

模型（Model）

即一个真值指派，使这个句子为真
对语句$\alpha$中的每个文字都给予一个真或假的指派，最终这个句子为真，这个指派就叫model
$M(\alpha)$是$\alpha$的所有Model的集合

蕴含 entailment

$KB \models \alpha$：KB蕴含句子$\alpha$
形式化定义：$KB \models \alpha$当且仅当在使$\alpha$为真的每个model模型中，$\beta$也为真
即：在所有$KB$语句为真的世界中，语句$\alpha$都为真
记为：$M(KB) \subseteq M(\alpha)$

注意：这里的蕴含是两个句子之间的关系

例如
$KB$：“张三走了”、“李四走了”
$\alpha$：“张三或者李四走了”（这里的或者是两边都可以为真，和现实世界不一样）

等价定义（$\alpha 、\beta$是两个语句）
$\alpha \models \beta$
$\alpha \Rightarrow \beta$是有效的(valid)
$\alpha \land \neg \beta$是不可满足的(unsatisfiable)
$M(KB) \subseteq M(\alpha)$ (定义式)

使用推理算法i从KB中导出语句$α$ 或语句$α$通过推理算法i从KB导出记为: $KB \vdash_i \alpha$
Soundness(可靠性)：对于推理过程i从KB推理出的每条语句$α$,都有$KB \models α$,则i是可靠的或真值保持的
Completeness(完备性)：对于KB蕴涵的每条语句$α$,推理过程i都能从KB推理出$α$,则i是完备的

命题逻辑：一种简单逻辑

语法

原子语句：即原子命题，单个命题词组成，每个命题词代表一个真或假的命题
复合句：简单语句和逻辑连接词构造而成
文字：原子命题或原子命题的否定
互补文字：一个文字是另一文字的否定
子句：文字的析取式。单个文字可以被视为只有一个文字的析取式，也叫单元子句
归并：去除文字的多余副本

5种常用逻辑连接词：

非 $\neg$，否定式(negation)
与 $∧$，合取式(conjunction)
或 $∨$，析取式(disconjunction)
蕴含 $⇒$或$→$或$⊃$，蕴含式.也称为规则或if-then语句(implication)
当且仅当$⇔$(英文：If and only if, 或者：iff)，双向蕴含式(biconditional)

语义

定义了用于判定特定模型中的语句真值的规则。在命题逻辑里面，命题词的真值只有两个——$true$或$false$

模型：即一个句子为真的，每个文字的真值指派
对语句$\alpha$中的每个文字都给予一个真或假的指派，最终这个句子为真，这个指派就叫model
$M(\alpha)$是$\alpha$的所有Model的集合

$“x=2,y=2”$ is a model of $x^2 +y^2 <=16$
$“x=3,y=3”$ is not a model of $x^2 +y^2 <=16$
$“P=T,Q=T”$ is a model of $P ∧ Q$
$“P=T,Q=F”$ is not a model of $P ∧ Q$

考虑一个具有四个命题A、B、C、D的词表，对于下列语句分别有多少个模型？

$B∨C$ ,($2^4-1* 2^2=12$)总共$2^4$个，减去让$B∨C$为假的4个（$B、C$同时为假，$A、D$的取值有四个）
$\neg A∨\neg B∨\neg C∨\neg D$ ,($2^4-1=15$)

命题逻辑定理的证明

逻辑推理：用蕴含推导出结论
模型检验：通过枚举所有可能的模型model来检验$KB$为真的情况下$α$都为真，即$M(KB) \subseteq M(\alpha)$
有效性：当一个语句在所有的模型(model)中它都为真时，称这个语句是有效的。（有效语句也叫重言式——必定为真）例如$\neg P∨P$为有效的
对任意语句$α$和$β$，$\alpha \models \beta$ 当且仅当语句$\alpha \Rightarrow \beta$是有效的
可满足性：如果一个语句在某些模型中为真，则可满足
对任意语句$α$和$β$，$\alpha \models \beta$ 当且仅当语句$\alpha \land \neg \beta$是不可满足的

SAT问题：命题逻辑语句的可满足性判定。是第一个被证明为NP完全的问题。（如CSP，就是询问在某个赋值下约束是否满足的）

单调性：逻辑蕴含语句集会随着添加到知识库的信息的增长而增长
对任意语句α和β，如果$KB \models \alpha$ ，那么$KB \land \beta \models \alpha$

推导和证明

推导规则：

假言推理规则（Modus Ponens，拉丁文）
$\frac{\alpha \Rightarrow \beta, \alpha}{\beta}$
消去合取词
$\frac{\alpha \land \beta}{\alpha}$
逻辑等价
逻辑等价：如果两个语句在同样的模型集合$M$中为真，则二者逻辑等价
$\left. \begin{aligned} M(\alpha) \subseteq M(\beta) \\ M(\beta) \subseteq M(\alpha) \end{aligned} \right\}M(\alpha)=M(\beta)$
$\alpha \equiv \beta$ 当且仅当 $\alpha \models \beta$ and $\beta \models \alpha$
$\alpha \Leftrightarrow \beta \equiv (\alpha \Rightarrow \beta) \land (\beta \Rightarrow \alpha)$
$\frac{\alpha \Leftrightarrow \beta}{(\alpha \Rightarrow \beta) \land (\beta \Rightarrow \alpha)}$
`
$\frac{(\alpha \Rightarrow \beta) \land (\beta \Rightarrow \alpha)}{\alpha \Leftrightarrow \beta}$

任意搜索算法来找出证明序列，只需定义如下证明问题：

初始状态：初始$KB$
行动：行动集合由应用于语句的所有推理规则组成
结果：将推理规则得到的新的语句实例加入$KB$
目标：要证明的语句状态
（这叫搜索证明，是模型枚举的一个替代方法）

归结证明（只针对文字的析取式：子句）

单元归结
若每个$l$都是一个文字，而且$l_i$和$m$是互补文字，则有：
$\frac{l1 \vee… \vee l_k,m}{l1 \vee…\vee l_{i-1} \vee l_{i+1} \vee ,…, \vee l_k}$

全归结
$l_i$和$m_j$是互补文字：
$\frac{l_1 \vee… \vee l_k, m_1 \vee … \vee m_n}{l_1 \vee…\vee l_{i-1} \vee l_{i+1} \vee ,…, \vee l_k \vee m_1 \vee … \vee m_{j-1} \vee m_{j+1} \vee … \vee m_n}$

归结规则的可靠性证明：
已知$l_1∨…∨l_k$和$m_1∨…∨m_n$这两个子句为真
如果$l_i$为真，由于$l_i$和$m_j$是互补文字，知$m_j$为假，则$m_1 \vee … \vee m_{j-1} \vee m_{j+1} \vee … \vee m_n$必为真
如果$l_i$为假，则$l_1 \vee … \vee l_{i-1} \vee l_{i+1} \vee … \vee l_k$必为真
因此，结论必定成立

归结选取两个子句并生成一个新的子句，该子句包含除了两个互补文字以外的原始子句中的所有文字。
归结规则中每个文字只能出现一次。例如，$（A∨B）$和$（A∨\neg B）$归结得$(A∨A)$，简化为$A$。

范式
合取范式CNF：子句的合取式
最外层是合取，且子句只能包含与、或、非(非只能用做文字的一部分，即只能直接在文字前出现)
基于逻辑等价规则: 双重否定律、德·摩根定律和分配律，所有命题公式都可以转换成 CNF 的等价公式。
析取范式DNF：子句的析取式

归结算法-如何证明蕴含 $\models$ (归结演绎推理)

归结演绎推理是一种基于逻辑“反证法”的机械化定理证明方法。
其基本思想是把永真性的证明转化为不可满足性的证明。
即要证明 $P→Q$永真，只要能够证明$P∧\neg Q$为不可满足即可
对于知识库$KB$而言，为了 证明$KB \models α$ ,只需要证明${KB,\neg α}$(或$KB∧\neg α$)是不可满足的。

步骤：

将$KB∧\neg α$转化成CNF
对结果子句运用归结规则，对含有互补文字的子句进行归结产生新的子句
- 如果该新的子句没有出现过就将其加入子句集中
- 如果含有多个互补文字，需要一次性进行
  - 归结$(\neg B、A∨B,C∨B)$归结得$(A,C)$而不是$(A,C∨B)$
持续上面两步，直到：
- 没有可以添加的新语句，此时，KB不蕴含$\alpha$
- 两个子句归结出空子句，则$KB \models α$

horn子句和限定子句

限定子句：受限形式的一种子句,它是指恰好只含一个正文字的析取式。
例如：$(A∨B∨\neg C)$不是限定子句，而$(A∨ \neg B∨ \neg C)$是限定子句。
每个限定子句可写为蕴含式

Horn子句：至多只有一个正文字的析取式。
如：$(A∨ \neg B∨ \neg C)$和$(\neg A∨ \neg B∨ \neg C)$都是horn子句。
Horn子句在归结下是封闭的:如果对两个Horn子句进行归结,结果依然是Horn子句。

目标子句：没有正文字的析取式。如：$(\neg A∨ \neg B∨ \neg C)$就是目标子句。
horn子句=限定子句+目标子句

命题逻辑的前向链接和反向链接

前向链接

从知识库中的已知事实(正文字)开始。如果蕴涵的所有前提已知，那么把它的结论加到已知事实集。持续这一过程，直到询问q被添加或者直到无法进行更进一步的推理。前向链接的运行时间是线性的。

前向链接是数据驱动推理的实例——即推理是从已知数据开始的。
对于Horn $KB$，前向链接是

可靠的：每个推理本质上是分离规则的一个应用
完备的：每个被蕴涵的原子语句都将得以生成

反向链接

反向链接算法正如它的名字，从查询开始进行推理。如果查询q已知为真,那么无需进行任何操作。否则,寻找知识库中那些以q为结论的蕴含式。如果其中某个蕴含式的所有前提都能证明为真(通过反向链接),则q为真。与前向链接一样,有效实现的时间复杂度是线性的。
反向链接是一种目标制导的推理形式。

参考资料

yyl424525, 人工智能一种现代方法第7章逻辑Agent（命题逻辑）

高级人工智能笔记-知识1

knowledge 1