人工智能三.ppt

第三章 归结推理方法 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 3.1.1命题 命题：能判断真假（不是既真又假）的陈述句。 简单陈述句描述事实、事物的状态、关系等性质。 例如：1．? 1+1=2 2．? 雪是黑色的。 3．? 北京是中国的首都。 4．? 到冥王星去渡假。 命题通常用字母p ,q ,a ,b 表示； 判断一个句子是否是命题，有先要看它是否是陈述句，而后看它的真值是否唯一。以上的例子都是陈述句，第4句的真值现在是假，随着人类科学的发展，有可能变成真，但不管怎样，真值是唯一的。因此，以上4个例子都是命题。 而例如： 1．? 快点走吧！ 2．? 到那去？ 3．? x+y10 等等句子，都不是命题。 3.1.2命题逻辑公式 定义： 原子命题：不能再分解的命题称为原子命题。 合式公式：原子命题是合式公式，连接词联结的合式公式的组合也是合 式公式（ 命题公式）。 常用的联结词： 合取式：p与q，记做p Λ q 析取式： p或q，记做p ∨ q 蕴含式： 如果p则q，记做p → q 等价式：p当且仅当q，记做p = q 否定：　　～p 、 ～最优先，其次为Λ、∨，再次为→， = 命题表示公式（1） 将陈述句转化成命题公式。 如：设“下雨”为p，“骑车上班”为q，， 1．“只要不下雨，我骑自行车上班”。～p 是 q的充分条件， 因而，可得命题公式： ～p → q 2．“只有不下雨，我才骑自行车上班”。～p 是 q的必要条件， 因而，可得命题公式：q → ～p 命题表示公式（2） 事件化为命题公式的步骤： （１）分析简单命题，将其符号化； （２）使用适当的联结词把简单命题连接起来。 例如： 1．? “如果我进城我就去看你，除非我很累。” 设：p，我进城，q，去看你，r，我很累。 则有命题公式：～r → (p → q)。 2．“应届高中生，得过数学或物理竞赛的一等 奖， 保送上北京大学。” 设：p，应届高中生，q，保送上北京大学上学， r，是得过数学一等奖。t，是得过物理一等奖。 则有命题公式公式：p ∧ ( r ∨t ) → q。 ２命题公式的解释 定义：设Ａ为一个命题公式，p1,p2,…,pn是出现在Ａ中的全部原　 　　　子命题，给原子命题各指定一个真值（０或者１），称 　　　为对Ａ的一个赋值或解释。 　　　若Ａ的值为真，则称为成真赋值。 　　　若Ａ的值为假，则称为成假赋值。 公式逻辑真值表 Ｐ　Ｑ　～Ｐ　Ｐ∨Ｑ　Ｐ∧Ｑ　Ｐ→Ｑ　Ｐ　Ｑ Ｔ　Ｔ　　Ｆ　　Ｔ　　　Ｔ　　　Ｔ　　　Ｔ Ｔ　Ｆ　　Ｆ　　Ｔ　　　Ｆ　　　Ｆ　　　Ｆ Ｆ　Ｔ　　Ｔ　　Ｔ　　　Ｆ　　　Ｔ　　　Ｆ Ｆ　Ｆ　　Ｔ　　Ｆ　　　Ｆ　　　Ｔ　　　Ｔ 命题逻辑基础 基本等值式 交换率：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 = p 等幂率： p= p∨p ， p= p Λp 等价等值式： p 　q = ( p → q )Λ(q → p ) 等价否定式： p 　 q = ~p ~q 命题逻辑基础 摩根率: ～ (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 ) Λ(p →~q )= ～ p 排中律： p∨～p = １ ； 　矛盾律： pΛ～p = ０ 零率：p∨１ = １ ； pΛ０ = ０ 范式：公式的标准型式。 定义：设A为一个公式 若A无成假赋值，则称A为重言式或永真式； 若A无成真赋值，则称A为矛盾式或永假式； 若A至少有一个成真赋值，则称A为可满足的； 简单合取式：有限个原子命题或其否定构成合取式。 简单析取式：有限个原子命题或其否定构成析取式。 析取范式：仅由有限个简单合取式组成的析取式。 合取范式：仅由有限个简单析取式组成的合取式。 范式的性质： 析取范式是矛盾式，当且仅当每个简单