第二章谓词逻辑法.ppt

2 4谓词逻辑法Predicatelogicmethod 内容提要Outline 逻辑 logic 命题propostion谓词演算predicatecalculus谓词公式predicateformula谓词公式的性质thenatureforpredicateformula一阶谓词逻辑知识表示方法 Method 一阶谓词逻辑表示法的特点 Characteristic 置换与合一 substitutionandunification 1逻辑 logic 1逻辑 logic 命题逻辑与谓词逻辑命题逻辑与谓词逻辑是最先用于人工智能的两种逻辑 对于知识的形式化表示 特别是定理的证明发挥了重要作用虽然命题逻辑能够把客观世界的各种事实表示为逻辑命题 但是它具有较大的局限性 命题逻辑只能进行命题间关系的推理 无法解决与命题结构和成分有关的推理问题 不适合表示比较复杂的问题 谓词逻辑是在命题逻辑的基础上发展而来的 命题逻辑可以看作是谓词逻辑的一种特殊形式 2命题 Proposition 命题命题是具有真假意义的语句命题代表人们进行思维时的一种判断 若命题的意义为真 称它的真值为 真 记作 T 若命题的意义为假 称它的真值为 假 记作 F 例如 西安是陕西省省会 10大于6 是真值为 T 的命题 月亮是方的 煤炭是白的 是真值为 F 的命题一个命题不能同时即为真又为假 但可以在一定条件下为真 在另一种条件下为假 例如 1 1 10 在二进制情况下为真 十进制情况下为假 2命题 Proposition 命题没有真假意义的语句 如感叹句 疑问句等 不是命题 通常用大写英文字母表示一个命题 例如 P 西安是座古老的城市命题逻辑的局限性 客观事物的结构及逻辑特征 不同事物间的共同特征 2命题 Proposition 命题逻辑的局限性 命题这种表示方法无法把它所描述的客观事物的结构及逻辑特征反映出来 也不能把不同事物间的共同特征表述出来例如 用字母P表示 小张是老张的儿子 这一命题 则无法表述出老张与小张是父子关系又如 张三是学生 李四是学生 这两个命题 用命题逻辑表示时 无法把两者的共同特征 都是学生 形式的表示出来可否用Student 张三 Student 李四 表示上述命题 谓词逻辑 3谓词演算predicatecalculus 3 1语法和符号syntaxandnotation3 2连词conjunctions3 3量词quantifiers 谓词 谓词在谓词逻辑中 命题是用形如P x1 x2 xn 的谓词来表述的 一个谓词可分为谓词名与个体两个部分个体 是命题的主语 表示独立存在的事物或某个抽象的概念 x1 x2 xn 是个体 一般用小写字母表示个体可以是个体常量 变元或函数谓词名 表示个体的性质 状态或个体之间的关系 P 是谓词名 一般用大写字母表示称P是一个n元谓词 谓词 谓词对于命题 张三是学生 用谓词可以表示为 Student 张三 其中 Student是谓词名 张三 是个体 Student刻画了 张三 是个学生这一特征 在谓词中 个体可以是常量 也可以是变元 还可以是一个函数 例如 对于命题 x 10 可以表示为more x 10 其中x是变元 又如 命题 小张的父亲是老师 可以表示为Teacher father Zhang 其中 father Zhang 是一个函数 当谓词中的变元都用特定的个体取代时 谓词就具有一个确定的真值 T 或 F 谓词 谓词在n元谓词P x1 x2 xn 中 若每个个体均为常量 变元或函数 则称它为一阶谓词 如果某个个体本身又是一个一阶谓词 则称它为二阶谓词 如此类推 个体变元的取值范围称为个体域 个体域可以是有限的 也可以是无限的 例如用I x 表示 x是整数 则个体域为所有整数 是无限的 谓词与函数不同 谓词的真值是 T 或 F 而函数的值是个体域中的一个个体 无真值可言 3 1 1谓词逻辑的基本组成部分 谓词演算谓词逻辑语言的语法和语义基本符号 谓词符号 变量符号 函数符号 常量符号 括号和逗号原子公式 原子公式由若干谓词符号和项组成谓词符号规定定义域内的一个相应关系常量符号是最简单的项 表示论域内的物体或实体变量符号也是项 不明确涉及是哪一个实体函数符号表示论域内的函数 是从论域内的一个实体到另外一个实体的映射例如 原子公式Married father LI mother LI 表示 李 LI 的父亲和他的母亲结婚 3 1 2原子公式 atomicformulas 谓词公式原子谓词公式 是由谓词符号和若干项组成的谓词演算 若t1 t2 tn是项 P是谓词 则称P t1 t2 tn 为原子谓词公式 分子谓词公式 可以用连词把原子谓词公式组成复合谓词公式 并把它叫做分子谓词公式 3 1 2原子公式 atomicformulas 只有当其对应的语句在定义域内为真时 才具有值T 真 而当其对应的语句在定义域内为假时 该原子公式才具有值F 假 老张是一个教师 一元谓词Teacher Zhang 机器人在1号房间中 INRoom Robot r1 Smith作为一个工程师为IBM工作 三元谓词Works Smith IBM engineer 2020 3 20 15 原子公式举例 Inroom Robot R1 谓词符号 常量符号 Married father L1 x 谓词符号 函数符号 常量符号 常量符号 变量符号 用括号和逗号隔开 以表示论域内的关系 2020 3 20 16 Inroom Robot R1 谓词符号 常量符号 Married father L1 x 谓词符号 谓词符号 常量符号 首字母大写的形式来表示 常量符号 常量符号 2020 3 20 17 Married father L1 x 函数符号 变量符号 小写字母的形式来表示 变量符号 函数符号 3 2连词 conjunctions 连词和量词连词合取 符号 表示所连结的两个命题之间具有 与 的关系 析取 符号 表示所连结的两个命题之间具有 或 的关系蕴涵 符号 表示 若 则 的语义 P Q读作 如果P 则Q 其中 P称为条件的前件 Q称为条件的后件 非 符号 表示对其后面的命题的否定双条件 符号 表示 当且仅当 的语义 P Q读作 P当且仅当Q 连词的优先级 机器人不在2号房间 Inroom robot r2 李明打篮球或踢足球 Plays Liming basketball Plays Liming football 我喜欢音乐和绘画 Like I music Like I painting 如果刘华跑得最快 那么他取得冠军 RUNS Liuhua faster WINS Liuhua champion 3 2连词 conjunctions 3 3量词 quantifier 连词和量词量词全称量词 符号 意思是 所有的 任一个 x读作 对一切x 或 对每一x 或 对任一x 命题 x P x 为真 当且仅当对论域中的所有x 都有P x 为真命题 x P x 为假 当且仅当至少存在论域中的一个x 使得P x 为假 例 x ROBOT x COLOR x GRAY 3 3量词 quantifier 连词和量词量词存在量词 符号 意思是 至少有 存在 x读作 存在一个x 或 对某些x 或 至少有一x 命题 x P x 为真 当且仅当至少存在论域中的一个x 使得P x 为真命题 x P x 为假 当且仅当对论域中的所有x 都有P x 为假 例如 x INROOM x r1 1号房间内有个物体 全称量词和存在量词举例 x y F x y 表示对于个体域中的任何个体x都存在个体y x与y是朋友 x y F x y 表示在个体域中存在个体x 与个体域中的任何个体y都是朋友 x y F x y 表示在个体域中存在个体x与个体y x与y是朋友 x y F x y 表示对于个体域中的任何两个个体x和y x与y都是朋友 注意点 全称量词和存在量词出现的次序将影响命题的意思 例如 x y Employee x Manager y x 每个雇员都有一个经理 y x Employee x Manager y x 有一个人是所有雇员的经理 4谓词公式predicateformula 4 4量词的辖域位于量词后面的单个谓词或者用括弧括起来的谓词公式 4 5约束变元与自由变元 辖域内与量词中同名的变元称为约束变元 不同名的变元称为自由变元 例子 x P x y Q x y R x y P x y Q x y x 的辖域 辖域内的变元x是受 x 约束的变元 R x y 中的x是自由变元 公式中的所有y都是自由变元 4谓词公式 谓词公式合适公式 WFF Well formedFormulas 通常把合适公式叫做谓词公式 递归定义如下 1 原子谓词公式是合适公式 2 若A为合适公式 则 A也是一个合适公式 3 若A B是合适公式 则A B A B A B A B也都是合适公式 4 若A是合适公式 x为A中的自由变元 则 x A和 x A都是合适公式 5 只有按上述规则 1 至 4 求得的那些公式 才是合适公式 4谓词公式 谓词公式用谓词公式表示知识时 需要首先定义谓词 然后再用连接词把有关的谓词连接起来 形成一个谓词公式表达一个完整的意义 例1 设有下列知识 刘欢比他父亲出名 高扬是计算机系的一名学生 但他不喜欢编程 任何整数或者为正或者为负 为了用谓词公式表示上述知识 首先需要定义谓词 Famous x y x比y出名Computer x x是计算机系的Like x y x喜欢y 4谓词公式 I x 表示 x是整数 P x 表示 x是正数 N x 表示 x是负数 此时可用谓词公式把上述知识表示为 刘欢比他父亲出名 Famous Liuhuan father Liuhuan 高扬是计算机系的一名学生 但他不喜欢编程 Computer Gaoyang Like Gaoyang Programing 任何整数或者为正或者为负 x I x P x N x 4谓词公式 谓词公式例2 用谓词逻辑描述右图中的房子的概念个体 A B谓词 Support x y 表示x被y支撑着Wedge x 表示x是楔形块Brick y 表示y是长方块其中x y是个体变元 它们的个体域 A B 房子的概念可以表示成一组合式谓词公式的合取式 Support A B Wedge A Brick B 5谓词公式的性质thenatureofpredicateformula 1 谓词公式的解释谓词公式在个体域上的解释 个体域中的实体对谓词演算表达式的每个常量 变量 谓词和函数符号的指派 Friends george x Friends george susie TFriends george kate F 对于每一个解释 谓词公式都可求出一个真值 T或F 5thenatureofpredicateformula 2 谓词公式的永真性 可满足性 不可满足性 定义3对于谓词公式P 如果至少存在一个解释使得P在此解释下的真值为T 则称P是可满足的 否则 则称P是不可满足的 定义2如果谓词公式P对个体域D上的任何一个解释都取得真值F 则称P在D上是永假的 如果P在每个非空个体域上均永假 则称P永假 定义1如果谓词公式P对个体域D上的任何一个解释都取得真值T 则称P在D上是永真的 如果P在每个非空个体域上均永真 则称P永真 5thenatureofpredicateformula 3 谓词公式的等价性 定义4设P与Q是两个谓词公式 D是它们共同的个体域 若对D上的任何一个解释 P与Q都有相同的真值 则称公式P和Q在D上是等价的 如果D是任意个体域 则称P和Q是等价的 记为PQ 5 3谓词公式的等价性Equivalence 1 否定之否定 P 等价于P 2 P Q等价于 P Q 3 狄 摩根定律 P Q 等价于 P Q P Q 等价于 P Q 4 分配律P Q R 等价于 P Q P R P Q R 等价于 P Q P R 5 交换律P Q等价于Q PP Q等价于Q P 5 3谓词公式的等价性Equivalence 6 结合律 P Q R等价于P Q R P Q R等价于P Q R 7 逆否律P Q等价于 Q P 8 x P x 等价于 x P x x P x 等价于 x P x 9 x P x Q x 等价于 x P x x Q x x P x Q x 等价于 x P x x Q x 10 x P x 等价于 y P y x P x 等价于 y P y 5thenatureofpredicateformula 4 谓词公式的永真蕴含 定义5对于谓词公式P与Q 如果P Q永真 则称公式P永真蕴含Q 且称Q为P的逻辑结论 称P为Q的前提 记为PQ 6一阶谓词逻辑知识表示方法 method 谓词公式表示知识的步骤 1 定义谓词及个体 2 变元赋值 3 用连接词连接各个谓词 形成合适公式 ForeverysetX thereisasety suchthatthecardinalityofyisgreaterthanthecardinalityofX 2020 3 20 36 例 用谓词逻辑表示下列知识 武汉是一个美丽的城市 但她不是一个沿海城市 如果马亮是男孩 张红是女孩 则马亮比张红长得高 解 按照知识表示步骤 用谓词公式表示上述知识 第一步 定义谓词如下 BCity x x是一个美丽的城市HCity x x是一个沿海城市Boy x x是男孩Girl x x是女孩High x y x比y长得高 谓词逻辑表示知识的举例 2020 3 20 37 这里涉及的个体有 武汉 wuhan 马亮 mal 张红 zhangh 第二步将这些个体代入谓词中 得到BCity wuhan HCity wuhan Boy mal Girl zhangh High mal zhangh 第三步根据语义 用逻辑连接符将它们连接起来 就得到了表示上述知识的谓词公司 BCity wuhan HCity wuhan Boy mal Girl zhangh High mal zhangh 2020 3 20 38 解 首先定义谓词如下 Student x x是学生Uniform x y x穿yN x x是自然数I x 是整数L x x大于零按照第二步和第三步的要求 上述知识可以用谓词公式分别表示为 x Student x Uniform x color x N x L x I x 例用谓词逻辑表示下列知识 所有学生都穿彩色制服 自然数都是大于零的整数 7 1置换substitution 置换置换 Substitution 置换的定义 置换是用变元 常量 函数来替换变元 使该变元不在公式中出现 置换是形如 t1 x1 t2 x2 tn xn 的有限集合 t1 t2 tn是项x1 x2 xn是互不相同的变元ti xi表示用ti项替换变元xi 不允许ti和xi相同 也不允许变元xi循环地出现在另一个tj中 7 1置换substitution 置换置换 Substitution 例如 a x f b y w z 是一个置换 g y x f x y 不是一个置换 g a x f x y 不是一个置换 7 1置换substitution 置换置换 Substitution 例 表达式P x f y B 的置换为s1 z x w y s2 A y s3 q z x A y s4 c x A y 用Es表示一个表达式E用置换s所得到的表达式的置换 于是 P x f y B 的4个置换如下 P x f y B s1 P z f w B P x f y B s2 P x f A B P x f y B s3 P q z f A B P x f y B s4 P c f A B 7 1置换substitution 置换置换 Substitution 置换是可结合的用s1s2表示两个置换s1和s2的合成 L表示一个表达式 则有 Ls1 s2 L s1s2 即用s1和s2相继作用于表达式L是与用s1s2作用于L一样的进一步推广 s1s2 s3 s1 s2s3 一般说来 置换是不可交换的 即s1s2 s2s1 7 2合一 unification 置换与合一合一 Unification 合一的定义 寻找项对变量的置换 以使两表达式一致 如果一个置换s作用于表达式集合 Ei 的每个元素 用 Ei s表示置换例的集 称表达式 Ei 是可合一的 如果存在一个置换s使得 E1s E2s E3s 那么 称此s为 Ei 的合一者 unifier 因为s的作用是使集合 Ei 成为单一形式 7 2合一 unification 置换与合一合一 Unification 例如 设有公式集E P x y f y P a g x z 则下式是它的一个合一 s a x g a y f g a z 7 2合一 unification 置换与合一最通用合一如果s是 Ei 的任一合一者 又存在某个s 使得 Ei s Ei gs 成立 则称g为 Ei 的最通用 最一般 的合一者 记为mgu 例如 设有公式集E P x f y B P x f B B 的最一般合一是 g B y 谓词逻辑法 主要优点自然 一阶谓词逻辑是一种接近于自然语言的形式语言系统 谓词逻辑表示法接近于人们对问题的直观理解明确 有一种标准的知识解释方法 因此用这种方法表示的知识明确 易于理解精确 谓词逻辑的真值只有 真 与 假 其表示 推理都是精确的灵活 知识和处理知识的程序是分开的 无须考虑处理知识的细节模块化 知识之间相对独立 这种模块性使得添加 删除 修改知识比较容易进行 谓词逻辑法 主要缺点知识表示能力差 只能表示确定性知识 而不能表示非确定性知识 过程性知识和启发式知识知识库管理困难 缺乏知识的组织原则 知识库管理比较困难存在组合爆炸 由于难以表示启发式知识 因此只能盲目地使用推理规则 这样当系统知识量较大时 容易发生组合爆炸系统效率低 它把推理演算与知识含义截然分开 抛弃了表达内容中所含有的语义信息 往往使推理过程冗长 降低了系统效率 2020 3 20 48 1 定义谓词及个体 确定每个谓词及个体的确切含义 2 根据所要表达的事物或概念 为每个谓词中的变元赋以特定的值 3 根据所要表达的知识的语义 用适当的连接符将各个谓词连接起来形成谓词公式 复习 简述谓词逻辑表示步骤 2020 3 20 49 练习 任何人都会死的 定义谓词 D x x会死的 M x x是人谓词表示 x M x D x 2020 3 20 50 练习 每个人都有一个父亲定义谓词 PERSON x 表示x是人HASFATHER x y 表示x有父亲y谓词表示 x y PERSON x HASFATHER x y 2020 3 20 51 所有的教师都有自己的学生定义谓词 TEACHER x 表示x是教师STUDENT y 表示y是学生TEACHES x y 表示x是y的老师谓词表示 x y TEACHER x TEACHES x y STUDENT y 练习 作业 1设有下列语句 请用相应的谓词公式把它们表示出来 1 有的人喜欢梅花 有的人喜欢菊花 有的人既喜欢梅花又喜欢菊花 2 喜欢玩篮球的人必喜欢玩排球 3 要想出国留学 必须通过外语考试 2针对猴子和香蕉问题 定义必要的谓词 写出问题的初始状态和目标状态 Answer 11 Like x y x喜欢yMeihua 梅花 Juhua 菊花 x Like x Meihua y Like y Juhua z Like z Meihuan Like z Juhuan 2 Likeplay x y x喜欢玩y x Likeplay x 篮球 Likeplay x 排球 3 Want x y x想要y Pass x y x通过y x Pass x Flanguage Want x Goaboard Answer 21 Monkey Box banana A B C2 Site x y Hang x y On x y Holds y w 3 初始状态Site Monkey A Hang Banana B Site Box C On Monkey Box