第四章 推理技术.ppt

第四章 推理技术 本章讨论 消解原理 规则演绎系统 产生式系统 不确定性推理 非单调推理 逻辑 经典逻辑 命题逻辑 谓词逻辑：知识表示和机器推理的基本方法之一 非经典逻辑 归结原理 也叫消解原理 一种主要基于谓词逻辑的知识表示方法 命题例 命题：能判断真假（不是既真又假）的陈述句。 简单陈述句描述事实、事物的状态、关系等性质。 例如：1．? 1+1=2 2．? 雪是黑色的。 3．? 北京是中国的首都。 4．? 到冥王星去渡假。 而例如：1．? 快点走吧！ 2．? 到那去？ 3．? x+y10 简单命题（原子命题） 陈述句不能分成更简单的句子 复合命题 简单命题+连接词 合适公式 单个常量或变量的命题 命题逻辑基础 基本等值式24个 交换率：p∨q = q∨p ； p∧q = q ∧p 结合率： (p∨q)∨r= p∨(q∨r); (p ∧q)∧r= p ∧(q∧r) 分配率： p∨(q∧r)=(p∨q)∧(p∨r) ； p∧(q∨r)=(p∧q)∨(p∧r) 基本等值式 摩根率: ～ (p∨q) = ～ p ∧～ q ； ～ (p∧q) = ～ p ∨ ～ q 吸收率: p∨(p∧q ) =p ； p∧(p∨q )=p 同一律: p∨0 = p ； p∧1 = p 蕴含等值式:p→q=～p∨q 假言易位式: p→q=～p→～q 给出事件命题公式的基本步骤 分析简单命题，使其符号化 连接词 其他概念 赋值 成真赋值 成假赋值 永真式：重言式 永假式：矛盾式 可满足式：至少有一个成真赋值 命题表示公式 将陈述句转化成命题公式。 如：设“下雨”为p，“骑车上班”为q，， 1．“只要不下雨，我骑自行车上班”。～p 是 q的充分条件， 因而，可得命题公式： ～p→q 2．“只有不下雨，我才骑自行车上班”。～p 是 q的必要条件， 因而，可得命题公式：q→～p 例如： 1．? “如果我进城我就去看你，除非我很累。” 设：p，我进城；q，去看你；r，我很累。 则有命题公式：～r → (p → q)。 2．“应届高中生，得过数学或物理竞赛的一等 奖， 保送上北京大学。” 设：p，应届高中生；q，保送上北京大学上学； r，是得过数学一等奖；t，是得过物理一等奖。 则有命题公式公式：p∧( r∨t )→q。 命题逻辑的归结法 基本单元：简单命题（陈述句） 例： 命题： A1、A2、A3 和 B 求证： A1∧A2∧A3成立，则B成立， 即：A1∧A2∧A3→B 反证法：证明A1∧A2∧A3∧～B 是矛盾式（永假式） 基础 如果E1∨E2为真，～E2∨E3为真 则E1∨E3为真 建立子句集 合取范式：命题、命题或的与，如： P∧(P∨Q)∧(～P∨Q) 子句集S：合取范式形式下的子命题(元素)的集合。例： 命题公式：P∧(P∨Q)∧(～P∨Q) 子句集 S：S={P,P∨Q,～P∨Q} 命题逻辑的归结法 归结过程 将命题写成合取范式 求出子句集 对子句集使用归结推理规则 归结式作为新子句参加归结 归结式为空子句□ ，S是不可满足的（矛盾），原命题成立。 □（证明完毕） 谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。 谓词归结原理基础 一阶逻辑 基本概念 个体词：表示主语的词 谓词：刻画个体性质或个体之间关系的词 量词：表示数量的词 小王是个工程师。 8是个自然数。 我去买花。 小丽和小华是朋友。 其中，“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词，而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系，最后一个谓词“是朋友”表示两个个体词之间的关系。 一阶逻辑 公式及其解释 个体常量：a,b,c 个体变量：x,y,z 谓词符号：P,Q,R 量词符号： ? ,? 例如：（1）所有的人都是要死的。 （2）有的人活到一百岁以上。 在个体域D为人类集合时，可符号化为： （1）?xP(x)，其中P(x)表示x是要死的。 （2）?xQ(x), 其中Q(x)表示x活到一百岁以上。 在个体域D是全总个体域时， 引入特殊谓词R(x)表示x是人，可符号化为： （1）?x（R(x)→P(x)）, 其中，R(x)表示x是人；P(x)表示x是要死的。