知识推理

Posted on

逻辑的一般原理

基于知识的Agent通过对知识的内部表示进行操作而推理，其核心部件是知识库KB，知识库作为语句的集合，用知识表示语言表达，用以表示关于世界的某些断言，某些语句直接给定，我们尊称其为公理；

Agent如何维护其知识库？

  • Tell：告诉知识库Agent感知的内容；
  • Ask：询问知识库应该采取什么行动，这个过程可能包括大量的推理；
  • Tell:告诉知识库Agent选择的行动后并执行；

如果Agent感知到的可用信息正确，那么Agent得出的结论也一定是正确的，这就是逻辑推理的本质；

语法

  1. 命题：具有确切真值的陈述句；

    • 原子命题：不能继续分解的命题；
      • 常值命题：不是真就是假的命题；
      • 变量命题：没有具体内容的原子命题；
    • 复合命题：可以继续分解的命题，由简单命题用括号和联结词组成；
      • 简单命题是变量命题时，可看作其函数；

  2. 联结词：五种常用的联结词如下：

    • 否定式:非P，$\neg P$
    • 合取式：P且Q，$P\wedge Q$
    • 析取式：P或Q，$P\vee Q$​
    • 蕴含：规则语句，若P则Q,$P\Rightarrow Q$
    • 等价：P当且仅当Q，$P \Leftrightarrow Q$​

  3. 命题公式：我们递归地定义公式WFF

    • 命题变元$P$本身就是公式
    • $\neg P, P\wedge Q,P\vee Q,P\Rightarrow Q, P \Leftrightarrow Q $都是公式；
    • 仅通过有限步使用上述两规则进行命题的联结得到的才是公式

    对于含有$n$个命题变元$P_1,P_2,…,P_n$的公式$G$,记为$G(P_1,P_2,…,P_n)$;

语义

  1. 模型/解释：可能的模型就是对命题$\alpha$的真值所有可能赋值，用$M(\alpha)$​表示；

    对公式$G(P_1,P_2,…,P_n)$,指定$(P_1,P_2,…,P_n)$的一组真值，这组真值称为$G$的解释；

  2. 语义：每个命题在每个模型内的真值，命题的真值必须通过指定模型确定；

  3. 真值表：联结词的运算规则，用如下表来概括

    image-20240614234959767

  4. 逻辑推理：用蕴含关系推导出结论；

    • 可靠性：只导出蕴含句的推理算法称为可靠的；
    • 完备的：若推理算法可以生成任意蕴含句；

  5. 模型检验：枚举可能的模型检验KB为真时命题$\alpha$为真,即检验$M(KB)\subseteq M(\alpha)$​

定理证明

  1. 逻辑等价：命题$\alpha,\beta$ 在同样的模型集合中为真，记为$\alpha \equiv \beta$
  2. 有效性（永真性）：若命题在任何模型都是真的；
  3. 可满足性：若命题在某些模型中为真；
  4. 永假性：若命题在任何模型都是假的；

永真蕴含式

  • 化 简 式 $P \land Q \Rightarrow P$, $P \land Q \Rightarrow Q$​
  • 附加式$ P \Rightarrow P \vee Q$, $ Q \Rightarrow P \vee Q$
  • 析取三段论$﹁P, P∨Q ⇒Q$
  • 假言推理 $P, P→Q ⇒Q$
  • 拒取式$ ¬Q, P→Q ⇒¬P$​
  • 假言三段论 $P→Q, Q→R ⇒P→R$​
  • 二难推理$ P∨Q, P→R, Q→R ⇒R $
  • 全称固化$ (∀x)P(x) ⇒P(y)$
  • 存在固化$ (∃x)P(x) ⇒P(y)$​

置换和推理

  1. 谓词：带有参数的命题；

    • 谓词公式的解释：设D是谓词公式P的非空个体域，若对P中的常量，函数和谓词按如下规定赋值:

      1. 为每个个体常量指派D中的一个元素；

      2. 为每个n元函数指派一个从Dn到D的一个映射，其中
        $$
        Dn = {(x_1, x_2, · · · , x_n)|x_1, x_2, · · · , x_n ∈ D}
        $$

      3. 为每个n元谓词指派一个从$D^n$到{0,1}的映射，则称这些指派为P在D上的一个解释

    • 谓词公式的永真性：如果谓词公式P对非空个体域D上的任一解释都取得真值T，则称P在D上是永真的；如果P在任何非空个体域上都是永真的，则称P是永真。

    • 谓词公式的可满足性：对于谓词公式P，如果至少存在D上的一个解释，使公式P在此解释下的真值为T，则称公式P在D上是可满足的。

    • 谓词公式的永假性：如果谓词公式P对非空个体域D上的任一解释都取真值F，则称P在D上是永假的；如果P在任何非空个体域上均是永假的，则称P永假。

    • 谓词公式的等价性：设P与Q是D上的两个谓词公式，若对D上的任意解释，P与Q都有相同的真值，则称P与Q在D上是等价的。如果D是任意非空个体域，则称P与Q是等价的，记作P⇔Q。

  2. ​ 在不同谓词公式中，往往会出现谓词名相同但其个体不同的情况，此时推理过程是不能直接进行匹配的，需要先进行置换； W (a) 和W(x)→Q(x)

    对谓词W (a)与W (x)谓词名相同，但个体不同，不能直接进行推理。

    ​ 要使用假言推理，首先需要找到项a对变元x的置换，使W (a)与W (x)一致。这种寻找项对变元的置换，使谓词一致的过程叫做合一的过程。

  3. 置换是形如 ${t_1 /x_1 ,t_2 /x_2 ,…,t_n /x_n }$

    的有限集合。其中，$t_1 ,t_2 ,…,t_n $是项；$x_1 ,x_2 ,…,x_n $是互不相同的变元；$t_i /x_i$ 表示用$t_i $替换$x_i$ 。要求：$t_i $与$x_i$ 不能相同，$x_i $不能循环地出现在另一个$t_i$ 中。

    通常，置换是用希腊字母$θ、σ、α、λ$等来表示的

  4. 设$θ={t_1 /x_1 ,t_2 /x_2 ,…,t_n /x_n }$是一个置换，$F$是一个谓词公式，把公式$F$中出现的所有$x_i$ 换成$t_i (i=1,2,…,n)$，得到一个新的公式$G$，称$G$为$F$在置换$θ $下的例示，记作$G=Fθ$

归结(消解)演绎推理背景

归结演绎推理是一种基于鲁宾逊(Robinson)归结原理的机器推理技术。鲁宾逊归结原理亦称消解原理, 鲁宾逊于1965年在海伯伦(Herbrand)理论的基础上提出一种基于逻辑的”反证法”

在人工智能中, 几乎所有的问题都可转化为一个定理证明问题。定理证明的实质, 就是对 前提P、结论Q, 证明 P→Q 永真。

要证明P→Q永真, 就要证明P→Q在任何一个非空的个体域上都是永真的。这是非常困难, 甚至是不可实现的。

人们发现可采用反证法的思想, 把关于永真性的证明转化为关于不可满足性的证明。

即要证明P→Q永真, 只要能够证明P∧﹁Q是不可满足的就可。

因 ： ﹁ (P→Q) ⇔ ﹁ (﹁ P∨Q) ⇔ P∧﹁ Q

这方面最有成效的工作就是鲁宾逊归结原理。它使定理证明的机械化成为现实。