人工智能3-1.ppt

人工智能原理人工智能原理第第3 3章章 逻辑逻辑逻辑逻辑 系系统统统统与推理与推理 （上）（上） 1本章内容本章内容3.1 逻辑 系统回顾 3.2 逻辑 智能体推理策略 3.3 消解法推理的理论基础 3.4 消解法与消解策略 3.5 模态逻辑 3.6 三值逻辑 3.7 模糊逻辑 参考文献第3章 逻辑系统与推理2第第1 1部分部分 经经典典逻辑逻辑 系系统统逻辑逻辑 系系统统 推理策略推理策略第3章 逻辑系统与推理3经经经经典数理典数理逻辑逻辑逻辑逻辑• AI研究内容之一是推理，即研究怎样 使 计算机获得自动推理的能力 • 数理逻辑 用数学 方法研究各种推理中的 逻辑问题 ，以推理本身作为研 究对象 • AI要使用逻辑 推理，就必然涉及数理逻 辑 / 数理逻辑 的经典部分—经典的命题 逻辑 和一阶谓词逻辑 ，同时作为人工 智能的知识表示方法和推理方法而存在 ；因此数理逻辑 是人工智能的一个基础第3章 逻辑系统与推理4逻辑逻辑逻辑逻辑 智能体智能体• 基于知识的智能体的核心部件是知识库 ，当这 些知识以逻辑 形式表示并进 行相 应的推理时，就是逻辑 智能体 • 知识表示：命题逻辑 、一阶谓词逻辑 • 推理(一阶谓词逻辑 )—主要有3类推理算法 ：前向链接和演绎系统、反向链接和逻辑 程序设计(3.2节)、归结反演和定理证明系 统(3.3和3.4节) • 采用命题和谓词 演算进行推理的系统( 如演绎系统)是一种典型的逻辑 智能体第3章 逻辑系统与推理53.1 逻辑系统回顾3.1.1 命题与 公式 3.1.2 谓词 3.1.3 一阶语 言及其项 3.1.4 逻辑 系统的语法与语义 3.1.5 语法和语义 之间关 系第3章 逻辑系统与推理63.1.1 3.1.1 命命题题题题与公式与公式• 命题：描述客观世界的可区分真假的陈 述句, 即一个判断（经典二值逻辑 ：非 真即假） • 是命题的例子： • 2+2=4 / 二月份有30天 / 2002年哈尔滨有 地震 / 人类能够证明数论中所有论断非真 即假（有待时间） • 不是命题的例子： • 张三比李四聪明 / 公共汽车内非常拥挤（ 各人认识不同）第3章 逻辑系统与推理7命命题变题变题变题变 量与真量与真值值值值• 命题变 量（变元）：一个命题用符号表 示，称为 命题符号 • 当命题符号代表任一个命题时 ，即为命 题变 量 • 真值 ：真或假 – 一个命题或命题变 量具 有真值 • 真值连 接词（5个）：否定/合取/析取/ 蕴涵/等价第3章 逻辑系统与推理8简单简单简单简单 命命题题题题与复合命与复合命题题题题• 真值 函数：真值联结词 可以视为 一元 或二元映射(真值 函数)，￢是从{T,F}到 {T,F}，其余是{T,F}2到{T,F}的映射 / 其函 数定义由真值 表确定 • 简单 命题：一个被视为 整体的、具有真 或假的命题是简单 命题 • 复合命题：使用联结词将简单 命题联 结起来的命题是复合命题第3章 逻辑系统与推理9命命题语题语题语题语 言与原子公式言与原子公式• 命题逻辑 ：研究复合命题之间的推导 关系 • 命题语 言：是命题逻辑 使用的形式语言 ，是符号的集合,用Lp表示 / 包括：命题 符号、连接词、左右括号 • 原子公式：命题语 言中的一个表达式是 原子公式，当且仅当它 是一个命题符号 / 原子公式也称为 文字(包括正文字和负 文字)第3章 逻辑系统与推理10命命题逻辑题逻辑题逻辑题逻辑 的合式公式的合式公式• 合式公式(well-formed formula)，简称 公 式，记作wff：一个表达式是一个公式， 当且仅当它 能通过有限次地使用下述步 骤生成： (1)原子公式是公式； (2)如果A是公式，则(￢A)是公式； (3)如果A、B均为公式，则A*B是公式，其中* 表示∧∨→≡中的任意一个 • 公式的形成规则 • 命题逻辑 的主要研究对象是公式第3章 逻辑系统与推理11命命题逻辑题逻辑题逻辑题逻辑 的特点的特点• 命题逻辑 ：使用陈述性、上下文无关、无歧 义性、合成性的形式语言 • 陈述性—使用符号描述(语句形式)显式地表 示知识 • 相对于过程性—将需要的知识直接编写为 程序 代码 • 上下文无关—其含义不因环境而改变 • 无歧义性—含义唯一 • 合成性—语句的含义是其各部分含义的一个 函数(也是一种唯一性)第3章 逻辑系统与推理123.1.2 3.1.2 谓词谓词谓词谓词• 从命题到一阶谓词 ：命题内 部逻辑结 构的分解 ￿ 对判断的分解，把判断中 的具体内容抽出，称为个 体；剩下的判 断即为谓词 • 谓词 可看作是从个 体域或个体域的笛卡 儿乘积到真值 集合{T/F}的映射 • 典型的推理例子：(1)凡人皆有死；(2)苏 格拉底是人；(3)苏格拉底有死。

三段 论式）M(x)￿D(x), M(s)├ D(s)第3章 逻辑系统与推理13论论论论域与个体域与个体• 论域和个体：在一阶逻辑 中，被研究对 象构成的非空集称为论 域；论域中的每 个元素称为个 体 • 论域例子：前面例子中的论域是“人” / 所有 的有理数都是实数：其论域为有理数 • 一阶逻辑还研 究个体之间的关系（或个体 的性质）及作用于个体的函数 • 论域/个体/个体间关系/作用于个体函数 这 4个成分构成了一阶逻辑 的结构第3章 逻辑系统与推理14谓词谓词谓词谓词• 谓词 （关系）：一阶形式语言中用于指 称论 域中个体的性质或者个体之间关 系 的形式符号（大写字母表示） • 给定了论域，就确定了谓词的真假值 • 一元谓词：个体的性质；二元谓词(多元谓 词)：个体的关系 • 个体的位置—空位，具体化—构成意义完 整的语句 • 空位的数目—谓词的元数→几元谓词第3章 逻辑系统与推理15变变变变量与量量与量词词词词• 变量(变元)：表示论域内的任意一个个 体 / 常量(常元)，表示确定的个体 • 量词与变 量：量词用来表示谓词 的判断特 性 • 全称量词￿：对所有的x ￿x P(x) • 存在量词￿：存在x ￿x P(x) • 约束变量：￿、￿中x的变量，量词所管辖 的公式如P(x)称为 量词辖 域 • 自由变量：不在量词辖 域内的变量为自由 变量第3章 逻辑系统与推 理16约约约约束束变变变变量和自由量和自由变变变变量量• 区别 ：自由变量可代入常量，约束变量不 行，因为￿a P(a)无意义 ；约束变量可改 名，自由变量不行 • 带有全称变量￿x的命题表示为一阶公式时 ，其表示形式为 ￿x(P(x)→…)，带有存在变 量￿x的命题则表示形式为￿x(P(x)∧…) • 例子：所有有理数都是实数 ￿x(P(x)→R(x)) ，有些人身高超过2米￿x(M(x)∧G(x)) • 上述使用方式不可改变，否则造成逻辑错 误第3章 逻辑系统与推 理17函数函数• 函数：表示个体之间的运算，可作用于 一个或数个个 体（用小写字母） • 给定一个或若干个体（对象），产生一个 新的个体（对象）/ 函数的元数 • 例子：x的父亲 father(张三) • 两数之和仍是一个数 add(e1, e2)第3章 逻辑系统与推 理18函数与函数与谓词谓词谓词谓词 的区的区别别别别• 谓词 和函数的区别 ：谓词 代表语句， 结果是关系（具有真假值）；函数代表 关系运算，结果是一个新个体 • 例子：谓词 SUM(e1, e2, e3) 说明e1、 e2、e3之间的关系是e1与e2的和是e3 ， • 函数add(e1, e2)说明e1与e2相加的结果 仍是一个数第3章 逻辑系统与推 理193.1.3 3.1.3 一一阶语阶语阶语阶语 言言(1)(1)• 一阶语 言L：是一阶逻辑 使用的形式语言 ，可以和任何结构 （论域）没有联系，也 可以与某个结构 有联系 • 与结构没 有联系的一阶语言由8类符号组 成： (1)无限序列的个体符号（个体常量） (2)无限序列的谓词符号，有确定的元数n≥1 有一个特殊的谓词符号称为 相等符号（等式 ），记为=。

L可含或不含=，如果含有，即 称为含=的一阶逻辑第3章 逻辑系统与推 理20一一阶语阶语阶语阶语 言言(2)(2)(3)无限序列的函数符号，有确定的元数m≥1 (4)无限序列的自由变量：用u/v/w等表示自由 变量 (5)无限序列的约束变量：用x/y/z等表示约束 变量 (6)联结词 ：￢∧∨→≡ (7)量词： ￿、￿ (8)标点：左右括号、逗号 ( ) , • 一阶逻辑 ：描述对象和关系的陈述性、 合成性的形式语言第3章 逻辑系统与推 理21一一阶语阶语阶语阶语 言的言的项项项项和公式和公式• L的项：一阶语 言中的一个符号是项t， 当且仅当它 能通过有限次使用下述步骤 生成： (1)个体常量、自由变量是项； (2)如果t1…tn是项，且f是n元函数，则f(t1…tn)是 项 • L的原子公式：一阶语 言中的一个表达 式是一个原子公式，当且仅当它 有如下 2种形式：(1)F(t1…tn)，F是n元谓词 ，t1…tn是项； (2)=(t1,t2)或t1=t2， t1、t2是项第3章 逻辑系统与推 理22一一阶语阶语阶语阶语 言的公式言的公式(1)(1)• L的公式：一阶语 言中的一个表达式是 一个公式，当且仅当它 能通过有限次使 用下述步骤生成： (1)原子公式是公式； (2)如果A是公式，则(￢A)是公式； (3)如果A、B均为公式，则A*B是公式，其中* 表示∧∨→≡中的任意一个 (4)如果A(u)是公式，且x不在A(u)中出现，则 ￿x A(x)、￿x A(x)都是公式第3章 逻辑系统与推 理23一一阶语阶语阶语阶语 言的公式言的公式(2)(2)• 一阶谓词 公式的例子 • 数学命题的表示：5只被1和5整除 • 设Q(x,y)表示x被y整除，N(x)表示x是自然 数 ￿ ￿x(Q(5,x)→N(5)∨N(1)) • 自然语言语句的表示：他不能在所有时刻 欺骗所有人 • 设F(x)表示“x是人”/G(x)“x是一个时刻 ”/H(x,y)“他能在y时刻欺骗x” ￿ ¬ ￿x ￿y (F(x)∧G(y) → H(x,y)) 或者 ￿x￿y(¬H(x,y)∧F(x)∧G(y)) 第3章 逻辑系统与推 理243.1.4 3.1.4 逻辑逻辑逻辑逻辑 系系统统统统• 逻辑 系统(亦称形式系统Formal System) 由5个部分组成： • 符号表—非空集合￿，即逻辑(形式)语言— 如一阶语言 • ￿上全体符号的集合￿*的子集—项和变量 • ￿*的子集—公式 | 公式和项的交集为空 • 公式FORMULA上的子集—公理AXIOM • 公式上的n元关系集合—推理规则RULE • ￿、项TERM、FORMULA称为 FS的组成 部分 / AXIOM、RULE称为 FS的推演部分第3章 逻辑系统与推 理25语语语语法和形式推演法和形式推演• 逻辑 系统除符号表以外的部分构成了逻 辑系统的语法 • 形式推演：定义了公式之间的形式可推演 性关系，它涉及公式的语法结构 ，其正确 性能够机械地证明 • 用记号├ 表示形式可推演关系，读作“推出” • 用￿├ A表示A是由￿形式可推演的（或形式 可证明的），其中￿是前提，A是结论第3章 逻辑系统与推 理26推演推演规则举规则举规则举规则举 例例• 形式推演由形式推演规则 定义，举例如 下： • 自反A├ A (Ref) • 传递if ￿├ ￿ ‘├ A then ￿├ A (￿) • ￢消去(反证律) if ￿ , ￢A├ B & ￿ , ￢A├￢B then ￿├ A( ￢–) • 公式变换A→B ￿ ￿A￿B第3章 逻辑系统与推 理27形式可推演性形式可推演性• 形式可推演性：在命题/一阶逻辑 系统中 ，A是由￿可形式推演的(或形式可证明 的)，记为 ￿├A，当且仅当 ￿├A能通过 有限次应用相应逻辑 的形式推演规则 生 成 • 即￿├A成立，当且仅当存在有限序列使得 ￿1├A1，￿2├A2，…，￿n├An 中的每一项 均由某个形式推导规则 生。