[理学]基于规则的演绎推理.ppt

4.3 基于规则的演绎推理 基本内容 1.基于规则的演绎推理的分类： 正向、反向和双向的演绎推理 2. F规则和B规则 基于规则的演绎推理把有关问题的知识和信息划分为规则与事实两种类型 规则：包含蕴含形式的表达式表示 事实：无蕴含式的表达式表示 画出相应的与/或图，然后通过规则进行演绎推理 第四章 基本的推理技术  4．3 基于规则的演绎推理 正向演绎推理 正向演绎推理对应于4．1中介绍的正向推理，它是从已知事实出发，反复尝试所有可利用的规则（F规则）进行演绎推理，直至得到某个目标公式的一个终止条件为止 正向演绎推理 （1）事实表达式及其与或图表示 正向演绎要求事实用不包含蕴含符号“→”的与/或形表示 表达式转化为标准的与/或形的步骤： ① 利用等价式P→Q与?P∨Q消去蕴含符“→” ② 把否定符号“?”移到每个谓词符号的前面 ③ 变量标准化，即重新命名变量，使不同量词约束变量有不同的名字 ④ 引入Skolem函数消去存在量词 ⑤ 将公式化为前束形 ⑥ 略去全称量词(默认事实表达式中尚存的变量是全称量词量化的变量) ⑦ 重新命名变量，使同一变量不出现在不同的主要合取式中 例如: (?x) (?y){Q(y,x)∧?[(R(y)∨P(y))∧S(x, y)]} 转化为标准的与/或形: Q(z,A)∧{[? R(y)∧? P(y)]∨? S(A，y)} 正向演绎推理 （1）事实表达式及其与或图表示 在与/或图中，结点表示事实表达式及其子表达式 根结点表示整个表达式，叶结点表示表达式中的单个文字 对于一个表示析取表达式（E1∨E2∨…En）的结点，用一个n连接符（图中的半圆弧）连接它的n个子表达式结点； 对于一个表示合取表达式（E1∧E2∧…En）的结点，则直接用单线连接符与它的n个子表达式结点相连 事实表达式:用n连接符（一个合取记号）来分解析取式 正向演绎推理 （1）事实表达式及其与或图表示 一重要性质：由变换表达式得到的一组子句则可从与或图中读出，每子句相当于与/或图的一个解图，每个子句是由叶结点组成的公式 从上上页可以读出上例表达式的三个子句： Q(z,A) ? S(A，y)∨? R(y) ? S(A，y)∨? P(y) 这三个子句正是原表达式化成的子句集?与/或图可看成是一组子句的一个简洁的表达形式 第四章 基本的推理技术  4．3 基于规则的演绎推理 正向演绎推理 （2）F规则的表示形式 基于规则的正向演绎推理中，通常要求F规则具有以下形式： L → W 具体要求如下： ① L是单文字，W是任意的与或形表达式 ② L和W中的所有变量都是全称量词量化的，默认的全称量词作用于整个蕴含式 ③ 各条规则的变量各不相同，而且规则中的变量与事实表达式中的变量也不相同 第四章 基本的推理技术  4．3 基于规则的演绎推理 正向演绎推理 （2）F规则的表示形式 将F规则的左部限制为单文字，是因为在进行演绎推理时，要用F规则作用于表示事实的与/或图，而该与/或图的叶结点都是单文字，这样就可用F规则的左部与叶结点进行匹配，大大简化了规则的应用过程 第四章 基本的推理技术  4．3 基于规则的演绎推理 正向演绎推理 （2）F规则的表示形式 变换成标准形式的步骤： ① 暂时消去蕴含符号“→” ② 把否定号“?”移到每个谓词的前面 ③ 引入Skolem函数消去存在量词 ④ 将公式化为前束形，并略去全称量词 ⑤ 恢复为蕴含式 正向演绎推理 （2）F规则的表示形式 变换成标准形式的例： 原公式(?x){[(?y)(?z)P(x,y,z)]→(?u)Q(x,u)} ① 消蕴含符 (?x){?[(?y)(?z)P(x,y,z)]∨(?u)Q(x,u)} ② 否定号移入 (?x){(?y)(?z)[?P(x,y,z)]∨(?u)Q(x,u)} ③ Skolem函数 (?x){(?y)[?P(x,y,f(x,y))]∨(?u)Q(x,u)} ④ 前束形/略全称量词 ?P(x,y,f(x,y))∨Q(x,u) ⑤ 恢复蕴含式 P(x,y,f(x,y))→Q(x,u) 第四章 基本的推理技术  4．3 基于规则的演绎推理 正向演绎推理 （3）目标公式的表示形式 在基于规则的正向演绎推理中，要求目标公式用子句表示，否则就要化成子句形式 第四章 基本的推理技术  4．3 基于规则的演绎推理