人工智能——归结推理

思考题

问题:设 A,B,C 三人中有人从不说真话,也有人从不说假话。某人向这三人分别提出同一个问题:谁是说谎者?A 答:“ B 和 C 都是说谎者”;B 答:“ A 和 C 都是说谎者”;C答:“ A 和 B 中至少有一个是说谎者”。求谁是老实人,谁是说谎者?

答案:C 是老实人,A、B 是说谎者。

归结演绎推理

  • 鲁滨逊归结原理把永真性的证明转化为关于不可满足性的证明
  • 反证法P ⇒ Q ,当且仅当 P∧~QF ,即 Q 为 P 的逻辑结论,当且仅当 P∧~Q 是不可满足的。
  • 海伯伦(Herbrand)定理为自动定理证明奠定了理论基础
  • 鲁滨逊(Robinson)提出的归结原理使机器定理证明成为现实

谓词公式的范式

前束型范式

在这里插入图片描述

Skolem范式(斯克林范式)

在这里插入图片描述

谓词公式 G 化为 Skolem 标准型的步骤

在这里插入图片描述

在这里插入图片描述

子句与子句集

在这里插入图片描述

谓词公式分别化成子句集

在这里插入图片描述

归结推理方法

在这里插入图片描述

命题逻辑中的归结原理

在这里插入图片描述

归结原理

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

谓词逻辑的归结原理

在这里插入图片描述

归结原理

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

利用归结原理进行定理证明

应用归结原理进行定理证明的步骤如下:

  • 设要被证明的定理可用谓词公式表示为如下的形式:A1∧A2∧…∧An ⇒ B
    1. 首先否定结论 B ,并将否定后的公式~B 与前提公式集组成如下形式的谓词公式: G= A1∧A2∧…∧An∧~B
    2. 求谓词公式 G的子句集 S
    3. 应用归结原理证明子句集 S 的不可满足性,从而证明谓词公式G的不可满足性。这就说明对结论 B 的否定是错误的,推断出定理的成立。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

“ 快乐学生 ” 问题

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

利用归结原理进行定理证明

在这里插入图片描述
在这里插入图片描述

应用归结原理进行问题求解

问题求解步骤:

  1. 把已知前提条件用谓词公式表示出来,并化成相应的子句集,设该子句集的名字为人工智能——归结推理
  2. 把待求解的问题也用谓词公式表示出来然后将其否定并与一谓词ANSWER构成析取式。谓词 ANSWER 是一个专为求解问题而设置的谓词,其变量必须与问题公式的变量完全一致。
  3. 把问题公式与谓词 ANSWER 构成的析取式化为子句集,并把该子句集与 S1 合并构成子句集 S
  4. 对子句集 S 应用谓词归结原理进行归结,在归结的过程中,通过合一置换,改变ANSWER中的变元。
  5. 如果得到归结式 ANSWER,则问题的答案即在 ANSWER 谓词中。

在这里插入图片描述

归结原理的特点

在这里插入图片描述

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
乘风的头像乘风管理团队
上一篇 2023年3月4日 下午4:27
下一篇 2023年3月4日 下午4:28

相关推荐