第三章-谓词逻辑与归结原理.pptVIP

人工智能 第三章 谓词逻辑与归结原理 概述 本章的内容与目标 智能体如何认识事物并且进行推理 用形式化的语言描述推理过程 机器证明的一般方法—归结原理 概述 语言 自然语言：人们在日常生活中所使用的语言文字 半形式化语言：自然语言加特定的符号，如数学语言(定义、定理等) 形式化语言：用精确的数学或机器可处理的公式定义的语言 。(逻辑学语言，弗雷格Frege ，1879) (p→q)∧(p→r)∧ ～ p∧ ～ r→ ～ p 怪物洞穴 人工智能的经典实验环境—怪物洞穴(wumpus世界) 洞穴有多个房间组成 某个房间中藏着一只怪物wumpus，它会吃掉进入这个房间的人，相邻房间中能够感觉到臭味 某些房间中有陷阱，进入房间会被陷阱吞噬，相邻房间中能够感觉到微风 游戏的主角是一个智能体，可以进入相邻的房间（对角线不可以） 智能体有且仅有一支箭，用这支箭可以射杀怪物 某个房间中有金子，游戏的目标是智能体找到金子 怪物洞穴 智能体行动的关键是要根据获得的信息推理，从而判断那个房间有怪物，那个房间有陷阱，那个房间是安全的 房间[4,2]和[2,3]有陷阱，房间[3,4]有怪物，房间[4,3]有金子 3.1 命题逻辑 3.1 命题逻辑 命题—能够判断真假的陈述句 陈述句 真值唯一， 可用二进制表示 用小写字母进行标识 例 1、北京是中国的首都。 2、长安大学位于钟楼附近。 3、 1+1=2 4、计算机系的学生必修C或JAVA。 5、坐着花生过黄河 5、x+1=2 6、吃饭了吗？ 7、南无阿弥陀佛 8、我正在说假话 3.1 命题逻辑 简单命题与复合命题 简单命题：（原子命题） 一个命题无法分解为更简单的子命题 复合命题： 由简单命题用联结词联结而成的命题 1、由若干简单命题组成； 2：由联结词联结 例： 1、北京是中国的首都。 2、长安大学位于钟楼附近。 3、计算机系的学生必修C或JAVA。 4、这家的报价单配置合理并且价格低廉。 5、“李四是犯罪嫌疑人” “李四有犯罪动机” 3.1 命题逻辑 合式公式： 单个常量或者变量的命题构成合式公式 联结词联结的合式公式的组合也是合式公式 合式公式的有限次组合称为命题公式 命题公式：有限次合式公式组合的形式化描述，本书中以大写字母标识。 3.1 命题逻辑 基本联结(连接)符号 ～ 非，否定, ﹁ ∧ 与，合取，AND的首字母 ∨ 或，析取，vel → 蕴含 式A： a →b表示，如果a为真，则b为真。 ? 等价 联结符号的优先级 ～ ∧ ∨ → ? 3.1 命题逻辑 将命题从语言表述转换为命题公式 step1、找出简单命题，并用符号表示 step2、分析简单命题间的逻辑关系，用联结符号进行描述 例 3.1 命题逻辑 例：怪物洞穴 如果房间[1,1]中有臭味，则房间[1,2]或[2,1]中有怪物 表示房间[i,j]中有臭味 表示房间[i,j]中有怪物 3.1 命题逻辑 练习：扫雷游戏 设Xi,j表示方格[i,j]中有一个地雷。 写出方格[1,1]周围恰好有2颗地雷的命题公式 3.1 命题逻辑 命题公式的赋值 对命题公式中的所有的命题变量各赋给一个值0，1。 真值表 3.1 命题逻辑 复合命题的真值 例： p: 周杰伦是一个流行歌手 q: 人工智能是计算机科学的一个分支 r: 牛在天上飞 求下列复合命题的真值 3.1 命题逻辑 命题公式的分类 重言式或永真式 tautology ， 设A为任一命题公式，若A在它的各种赋值下取值均为真，则称A是重言式 例：P∨~P 矛盾式或永假式 contradictory 设A为任一命题公式，若A在它的各种赋值下取值均为假，则称A是永假式。 例： P∧~P 3.1 命题逻辑 可满足式 satisfiable 设A为任一命题公式，如果存在一组取值使A为真，则A为可满足式。 即：对于命题公式A，若A不是矛盾式，则称A是可满足式。 例：P∧Q 非重言式的可满足式 既是可满足式，又不是重言式 3.1 命题逻辑 等值逻辑运算 = 逻辑等值，等号连接的命题公式等价，≡ 基本等值算式 P80 交换率: A ∧ B = B ∧ A； A ∨B = B ∨ A ； 结合率: (A ∧ B) ∧ C= A ∧(B ∧ C) ； (A ∨B) ∨ C= A ∨ (B ∨ C) ； *分配率: A ∨ (B ∧ C) = (A ∨ B) ∧(A ∨ C) ；