3确定性推理

15
3.2
命题逻辑
命题公式的缺点：
• 无法把所描述的客观事物的结构和逻辑特征反映出来 • 不能把不同事物的共同特征反映出来 P:“张三是李四的老师”；仅用字母P看不出张三和李四之 间的师生关系。 为了克服命题逻辑的局限性，引入了下面的谓词逻辑
16
3.3 谓词逻辑
3.3.1 谓词与个体
在谓词逻辑中，将原子命题分解为谓词与个体两部分。 个体是指可以独立存在的物体，可以是抽象的或具体的。 谓词则是用于刻画个体的性质、状态或个体间的关系的。 例如：“李白是诗人” 可表示为：poet(LiBai) poet称为谓词，用以刻画“是诗人”；LiBai称为个体
19
3.3 谓词逻辑
谓词的元数：谓词中包含的个体数目称为谓词的元数，例 如P(x)是一元谓词，P(x,y)是二元谓词，而P(x1,x2,…,xn )则 是n元谓词。 n 谓词的阶数：在谓词P(x1,x2,…,xn )中，若xi(i=1,2,…,n) 都是个体常量、变元或函数，则称它为一阶谓词。如果某 个xi本身又是一个一阶谓词，则称它为二阶谓词，依次类推。 谓词和函数的区别：谓词具有逻辑值“真”或“假”，而 函数则是某个个体到另一个个体（按数学上的概念是自变 量到因变量）之间的映射。
4
3.1 推理概述
3.1.2 推理的方法及其分类 1. 按照推理的逻辑基础分类 可分为演绎推理、归纳推理和默认推理。 （1）演绎推理 演绎推理是从已知的一般性知识出发，推理出 适合于某种个别情况的结论的过程。它是一种由 一般到个别的推理方法。
5
3.1 推理概述
（2）归纳推理 归纳推理是从大量特殊事例出发，归纳出一般性结论 的推理过程，是一种由个别到一般的推理方法。其基本思 想是：首先从已知事实中猜测出一个结论，然后对这个结 论的正确性加以证明确认，数学归纳法就是归纳推理的一 种典型例子。 归纳推理又可分为： 从特殊事例考察范围看：完全归纳推理、不完全归纳推理； 从使用的方法看：枚举归纳推理、类比归纳推理。
17
3.3 谓词逻辑
一个谓词可以与一个个体相关联，此种谓词称 作一元谓词，它刻画了个体的性质。一个谓词也可 以与多个个体相关联，此种谓词称为多元谓词，它 刻画了个体间的“关系”。
18
3.3 谓词逻辑
谓词的一般形式： P(x1,x2,…,xn ) 其中P是谓词，而x1,x2,…,xn 是个体。谓词通常用大写字母 P x 表示，个体通常用小写字母表示。 项：在谓词中，个体可以是常量，也可以是变量，还可 以是一个函数。例如，“小刘的哥哥是个工人”，可以表 示为worker(brother(Liu))，其中brother(Liu)是一个函数。 个体常数、变量和函数统称为项。 谓词的语义：由使用者根据需要人为地定义.
第三章 确定性推理
1
需要掌握的问题
应用归结原理求解下列问题： 应用归结原理求解下列问题： 任何兄弟都有同一个父亲， 任何兄弟都有同一个父亲，John和Peter 和 是兄弟， 的父亲是David，问 是兄弟，且John的父亲是 的父亲是 ， Peter的父亲是谁？ 的父亲是谁？ 的父亲是谁
2
按照推理过程所用知识的确定性，推理可分为确定性 推理和不确定性推理。 自然演绎推理和归结推理是经典的确定性推理，它们 以数理逻辑的有关理论、方法和技术为理论基础，是机械 化的、可在计算机上加以实现的推理方法。 本章在讨论有关推理的一般概念以及命题和谓词逻辑 的基础上，介绍自然演绎推理方法和基于一阶谓词逻辑的 归结推理方法。
28
3.3 谓词逻辑
谓词逻辑中还有如下一些推理规则： （1）P规则：在推理的任何步骤上都可引入前提。 （2）T规则：推理时，如果前面步骤中有一个或多个永真蕴含公式S，则可 把S引入推理过程中。 （3）CP规则：如果能从R和前提集合中推出S来，则可从前提集合推出 R→S来。 （4）反证法：P=>Q，当且仅当P∧～Q⇔F，即Q为P的逻辑结论，当且仅 当P∧～Q 是不可满足的。 推广之，可得如下定理。 定理3.1 Q为P1，P2，…，Pn的逻辑结论，当且仅当 (P1∧P2∧…∧Pn)∧～Q是不可满足的。
3.1.3 推理的控制策略 推理过程不仅依赖于所用的推理方法，同时也依赖于 推理的控制策略。控制策略包括推理方向、搜索策略、冲 突消解策略等；而推理方法则是指在推理控制策略确定之 后，在进行具体推理时所要采取的匹配方法或不确定性传 递算法等方法。 推理方向用来确定推理的驱动方式，即是数据（证据） 驱动或是目标驱动。所谓数据驱动即指推理过程从初始证 据开始直到目标结束，而目标驱动则是指推理过程从目标 开始进行反向推理，直到出现与初始证据相吻合的结果。 按照对推理方向的控制，推理可分为正向推理、反向 推理、混合推理及双向推理四种情况。
Dn={(x1,x2,…,xn)|x1,x2,…,xn ∈D}
（3）为每个n元谓词指派一个从Dn到{F,T}的映射； 则称这些指派为公式P在D上的一个解释。
24
3.3 谓词逻辑
例3.1 设个体域D={1,2}，求公式A=(∀x)(P(x)→Q(f(x),b))在 D上的某一个解释，并指出在此解释下公式A的真值。 详细的求解过程参见教材
3
3.1 推理概述
3.1.1 推理的基本概念
推理是指从已知事实出发，运用已掌握的知识，推导 出其中蕴含的事实性结论或归纳出某些新的结论的过程。 其中，推理所用的事实可分为两种情况，一种是与求解问 题有关的初始证据；另一种是推理过程中所得到的中间结 论，这些中间结论可以作为进一步推理的已知事实或证据。 人工智能系统的构成： 推理机－－－一些程序来完成的； 综合数据库－－－存放有用于推理的事实或证据； 知识库－－－存放有用于推理所必须的知识。
~P F F T T
14
3.2
命题逻辑
2.命题公式 定义3.3 以下面的递归形式给出命题公式的定义： • （1）原子命题是命题公式。 • （2）A是命题公式，则～A也是命题公式。 • （3）若A和B都是命题公式，则A∧B、A∨B、 A→B、A↔B •（4）只有按（1）—（3）所得的公式才是命题 公式。
25
3.3 谓词逻辑
2．谓词公式的永真性 定义3.7 如果谓词公式P，对个体域D上的任何一个解释都 取得真值T，则称P在D上是永真的；如果P在每个非空个体 域上均永真，则称P永真。 定义3.8 如果谓词公式P对于个体域D上的所有解释都取得 假值F，则称P在D上是永假的；如果P在每个非空个体域上 均永假，则称P永假。 谓词公式的永假性又称为不可满足性或不相容性。
3.3 谓词逻辑
3.3.4 谓词公式的等价性与永真蕴含 定义3.10 设P与Q是两个谓词公式，D是它们共同的个体域。若 对D上的任何一个解释，P与Q的取值都相同，则公式P和Q在域 D上是等价的。如果D是任意个体域，则称P和Q是等价的，记作 P⇔ Q。 常用的一些等价式参见教材 定义3.11 对于谓词公式P和Q，如果P→Q永真，则称P永真蕴含 Q，且称Q为P的逻辑结论，称P为Q的前提，记作P=>Q。 以后要用到的一些永真蕴含式参见教材
22
3.3 谓词逻辑
4. 量词辖域与约束变元 在一个公式中，如果有量词出现，位于量词后面 的单个谓词或者用括弧括起来的合式公式称为量词的 辖域。在辖域内与量词中同名的变元称为约束变元。
23
ቤተ መጻሕፍቲ ባይዱ
3.3 谓词逻辑
3.3.3 谓词公式的永真性和可满足性 1．谓词公式的解释 定义3.6 设D为谓词公式P的个体域，若对P中的个体常量、函数 和谓词按照如下规定赋值： （1）为每个个体常量指派D中的一个元素； （2）为每个n元函数指派一个从Dn到D的映射，其中
6
3.1 推理概述
（3）默认推理 默认推理又称缺省推理，是在知识不完全的情况下假 设某些条件已经具备所进行的推理。也就是说，在进行推 理时，如果对某些证据不能证明其不成立的情况下，先假 设它是成立的，并将它作为推理的依据进行推理，但在推 理过程中，当由于新知识的加入或由于所推出的中间结论 与已有知识发生矛盾时，就说明前面的有关证据的假设是 不正确，这时就要撤消原来的假设以及由此假设所推出的 所有结论，重新按新情况进行推理
13
3.2
命题逻辑
表3.1 命题逻辑真值表
3.2.2 命题公式
1. 连接词 P Q ～：称为“非”或“否定”。 P∨Q P∧Q P→Q P T Q T T T T T T F T F F F ∨：称为“析取”。 F T T F T F ∧：称为“合取”。 F F F F T T →：称为“条件”或者“蕴含”。 ↔：称为“双条件”。P ↔ Q表示“P当且仅当Q”。
20
3.3 谓词逻辑
3.3.2 谓词公式 1. 连接词 ～，∨，∧，→，↔ 2. 量词 为刻画谓词与个体间的关系，引入了两个量词：全称量词 （∀x）,和存在量词（∃x）。 3. 谓词演算公式 定义3.4 谓词演算中，由单个谓词构成的不含任何连接词的公式， 叫做原子谓词公式。
21
3.3 谓词逻辑
由原子公式的定义出发，可定义谓词演算的合式公式如下。 定义3.5 可按下述规则得到谓词演算的合式公式： （1） 原子谓词公式是合式公式。 （2） 若A是合式公式，则～A也是合式公式。 （3）若A和B都是合式公式，则A∧B、A∨B、A→B、A↔B也都 是合式公式。 （4）若A是合式公式，x是任一个体变元，则(∀x)A和(∃x)A也都 是合式公式。 （5）只有按（1）—（4）所得的公式才是合式公式。
10
3.1 推理概述
3.1.4 推理的冲突消解策略 推理过程中的冲突消解策略，就是确定如何从 多条匹配规则中选出一条规则作为启用规则，将 它用于当前的推理。 目前已有的多种冲突消解策略的基本思想都是 对匹配的知识或规则进行排序，以决定匹配规则 的优先级别，优先级高的规则将作为启用规则。 常用排序方法有如下几种:
29
3.3 谓词逻辑
3.3.5 置换与合一 1. 置换 置换的定义 定义3.12 置换是形如{t1/x1,t2/x2,…,tn/xn}的一个有限集。其 中xi是变量，ti是不同于xi的项（常量，变量，函数），且xi ≠xj（I≠j），i，j=1,2,…,n 。