人工智能及应用_ch3_2.ppt

经典逻辑推理 自然演绎推理归结演绎推理 自然演绎推理 定义 设S是一个命题 谓词 公式集 从S推出G的一个演绎是一个公式的有限序列 G1 G2 Gk G其中Gj或者属于 或者是某些Gi i j 的逻辑结论 我们称公式G为演绎的逻辑结果或称由S演绎出G 例S PVQ Q R P M M 是一个公式集 如下的公式序列就是一个从S推出G的一个演绎 M P M P PVQ Q Q R R G 自然演绎推理 逻辑结论 定义3 17设S F1 F2 Fm 是公式集 G是公式 称G是S的逻辑结论 如果F1 F2 Fm蕴含G 结论 设S是公式集 G是一个公式 从S演绎出G的充要条件是G为S的逻辑结论 结论 设S是公式集 G和H是两个公式 如果从SU G 可演绎出H 则从S可演绎出G H 自然演绎推理 规则 通俗的解释演绎推理就是由一组已知事实出发 直接使用经典逻辑的推理规则推出结论的过程 推理规则 规则1 可以随便使用前提 规则2 可以随便使用前面演绎出的某些公式的逻辑结果 规则3 如需要演绎出公式G H 则可将G作为附加前提使用 演绎出H 自然演绎推理 示例 已知下列事实 A B A C B C D D Q求证Q为真 证 A A C C规则1 假言推理B C B C合取B C B C D D规则2 假言推理D D Q Q规则2 假言推理Q为真 自然演绎推理 示例 若厂方拒绝增加工资 则罢工不会停止 除非罢工超过一年且工厂经理辞职 问 如果厂方拒绝增加工资 而罢工刚刚开始 罢工能否停止 解 设P 厂方拒绝增加工资 Q 罢工停止 R 工厂经理辞职 S 罢工超过一年 自然演绎推理 示例 S 罢工没有超过一年 SV R 罢工没有超过一年或工厂经理没有辞职 S R P 厂方拒绝增加工资P S R P S R Q Q 自然演绎推理 示例 设已知如下事实 只要是需要编程的课 王程都喜欢 所有程序设计语言课都是需要编程的课C是一门程序设计语言课 求证 王程喜欢C这门课 自然演绎推理 示例 解 定义谓词 Prog x x是需要编程的课Like x y x喜欢yLang x x是一门程序设计语言课 把事实及待求解问题用谓词公式表示 Prog x Like Wang x x Lang x Prog x Lang C 自然演绎推理 示例 应用规则推理 Lang C Prog C 全称固化Lang C Lang C Prog C Prog C 假言推理Prog C Prog C Like Wang C Like Wang C 所以王程喜欢C语言这门课 归结演绎推理 归结演绎推理基本思路子句集海伯伦理论鲁宾逊归结原理归结反演 归结演绎推理的基本思路 人工智能中的问题求解几乎都可以转化为定理证明问题 定理证明的实质是从公式集S P1 P2 Pn 出发推出结论G 即需要验证如下蕴含式永真 P1 P2 Pn G 归结演绎推理的基本思路 蕴含式永真不容易验证 将其转化为不可满足性 即将验证 P1 P2 Pn G永真转化为验证 P1 P2 Pn G不可满足 下面我们证明 P G P G 蕴含式的定义 P G是假的当且仅当P是真的而G是假的 归结演绎推理的基本思路 归结演绎推理的基本思路 进一步要验证 P1 P2 Pn G不可满足只需要验证以上公式中的任意一个子式不可满足即可 定义3 17不包含任意文字的子句称为空子句 空子句是永假的 不可满足的 一般记为NIL或 子句集 定义3 18由子句和空子句组成的集合称为子句集 在谓词逻辑中 任何一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集 化子句集的步骤 Step1 消去连接词 和 反复使用如下等价式P Q PVQP Q P Q V P Q 即可消去连接词 和 例 x y P x y y Q x y R x y 由第一个等价式有 y Q x y R x y y Q x y VR x y 化子句集的步骤 所以 x y P x y y Q x y R x y x y P x y V y Q x y VR x y Step2 减少否定符号的辖域 反复使用德 摩根律 PVQ P Q P Q PV Q双重否定律 P P 化子句集的步骤 量词转换律 x P x P x P x P将每个否定符号移到仅靠谓词的位置 使否定符号只作用于一个谓词上 接上例 x y P x y V y Q x y R x y 化子句集的步骤 Step3 变元标准化 在一个量词的辖域内 把谓词公式中受该量词约束的变元全部用另外一个没有出现过的变元代替 使不同量词约束的变元的名称不同 接上例 x y P x y V z Q x z R x z 化子句集的步骤 Step4 化为前束范式 接上例 x y z P x y V Q x z R x z Step5 消去存在量词 接上例 x P x f x V Q x g x R x g x 化子句集的步骤 Step6 化Skolem标准形 接上例 x P x f x VQ x g x P x f x V R x g x Step7 消去全称量词 接上例 P x f x VQ x g x P x f x V R x g x 化子句集的步骤 Step8 消去合取词 接上例 P x f x VQ x g x P x f x V R x g x Step9 更换变元名称 得到谓词公式的标准子句集 P x f x VQ x g x P y f y V R y g y 子句集的性质 由于化子句集消去存在量词时引入Skolem函数 导致子句集与原谓词公式不等价 由定理3 3知 谓词公式与其相应的Skolem范式的不可满足性等价 子句集的性质 定理3 4设有谓词公式G 其标准子句集为S 则G为不可满足的充要条件是S为不可满足的 证明 设G是前束范式即G Q1x1 Q2x2 Qnxn M并假设首标中第一个存在量词是 Qrxr 将此量词消去后得到谓词公式G1G1 Q1x1 Q2x2 Qr 1xr 1 Qr 1xr 1 Qnxn M 子句集的性质 若能证明 G不可满足 G1不可满足同理可证 G1不可满足 G2不可满足重复此过程直到证明 Gm 1不可满足 Gm不可满足 子句集的性质 现证明 G不可满足 G1不可满足 先证明 反证 已知G不可满足 设G1可满足 则存在一个解释I 使G1在此解释下的真值为真 即对任意x1 x2 xr 1在I的设定下有 Qr 1xr 1 Qnxn M x1 x2 xr 1 f x1 x2 xr 1 xr 1 xn 为真 子句集的性质 即在I下有对任给的x1 x2 xr 1都有f x1 x2 xr 1 使得在I下有 x1 x2 xr 1 xr Qr 1xr 1 Qnxn M x1 x2 xr 1 xr xr 1 xn 的真值为真 即G的真值为真 G可满足 与已知矛盾 所以G1为不可满足的 海伯伦 Herbrand 理论 判定子句集不可满足 需要判定子句对任何非空个体域上的所有解释的真值都为假 海伯伦构造一个特殊的个体域H 只要验证子句在这个特殊的个体域上是不可满足的 即可证明子句是不可满足的 这个特殊的个体域称为海伯伦域 海伯伦 Herbrand 理论 定义3 19设S为论域D上的一个子句集 则按下述方法构造的域H 称为海伯伦域 简记为H域 令H0是S中所有个体常量的集合 若S中不包含个体常量 则可任取一常量a D并令H0 a 令Hi 1 Hi S中所有n元函数f x1 x2 xn xj j 1 2 n 是Hi中的元素 其中i 1 2 海伯伦域的示例 求S P a Q x VR f x 的H域 解 子句集中只有一个个体常量a 按定义3 19有H0 a H1 a f a a f a H2 a f a f f a a f a f f a H a f a f f a 海伯伦理论 基子句 如果用H域的元素代替子句中的变元 则所得到的子句称为基子句 基子句中的谓词称为基原子 子句中所有基原子构成的集合称为原子集 例如 基子句 Q a VR a Q f a VR f a 基原子 Q a R a Q f a R f a 原子集 Q a R a Q f a R f a H解释 定义3 20子句集S在H域上的解释IH满足如下条件 在解释IH下 常量映射到自身 S中的任意n元函数是Hn H的映射 其中Hn是一个由属于H的n个元素构成的集合 即函数的自变量x1 x2 xn H 并且有函数值f x1 x2 xn HS中的任意n元谓词是Hn T F 的映射 H解释的示例 求子句集S P x VQ x R f x 在H域上的解释 子句集S的H域和原子集分别为 H a f a f f a A P a Q a R a P f a Q f a R f a H解释的示例 对A中每个元素真值的一个具体设定 就是S的一个H解释 即有 IH1 P a Q a R a P f a Q f a R f a IH2 P a Q a R a P f a Q f a R f a IH3 P a Q a R a P f a Q f a R f a 子句集解释的对应关系 子句集对任意论域D上的任一解释I 若S在此解释下为真 那么是否有一个相应的H解释IH使得S在IH下的解释也为真 定理3 5设I是S在D域上的解释 则S存在着对应于I的H解释IH 使得若有S在解释I下为真 必有S在解释IH下也为真 鲁宾逊归结原理 基本思想 P1 P2 Pn G不可满足 通过化子句集S 空子句是不可满足的 通过归结运算找S中的空子句 鲁宾逊归结原理 命题逻辑归结原理谓词逻辑归结原理 命题逻辑归结原理 定义3 21设P是文字 则称P与 P为互补文字 定义3 22设C1和C2是子句集S中的任意两个子句 如果子句C1中的文字L1与C2中的文字L2互补 则从C1和C2中分别消去L1和L2 并将两个字句余下的部分析取构成一个新子句C12 称这一过程为归结 C12为C1和C2的归结式 C1和C2为C12的亲本子句 命题逻辑归结原理 例1 设C1 PVQVR C2 PVTC12 QVRVT例2 设C1 PVQ C2 Q C3 PC12 PC123 NIL L1 L2 归结的性质 定理3 6归结式C12是其亲本子句C1和C2的逻辑结论 证明 不妨设C1 LVC11 C2 LVC21则有C12 C11VC21LVC11 C11VL C11 L LVC21 L C21C1 C2 C11 L L C21 C1 C2 C11 L L C21 C11 C21 C11 C21 C11VC21 C12所以C1 C2 C12 归结的性质 推论1 设C1和C2是子句集S中的两个子句 C12是C1和C2的归结式 用C12代替C1和C2后构成新子句集S1 则由S1的不可满足性可以推出S的不可满足性 即 S1不可满足 S不可满足 归结的性质 推论2 设C1和C2是子句集S中的两个子句 C12是C1和C2的归结式 将C12添加到S中构成新子句集S2 则S2的不可满足性与S的不可满足性等价 即 S2不可满足 S不可满足 归结的性质 定理3 7子句集S是不可满足的 充要条件是存在一个从S到空子句的归结过程 命题逻辑的归结反演 已知F 证明G F G不可满足 定理3 4设有谓词公式G 其标准子句集为S 则G为不可满足的充要条件是S为不可满足的 子句集S不可满足 定理3 7子句集S是不可满足的 充要条件是存在一个从S到空子句的归结过程 S归结出空子句 命题逻辑的归结反演 应用归结原理证明定理的过程称为归结反演 已知F 证明G的归结反演过程如下 否定目标公式G 得 G 把 G并入到公式集F中 得 F G 把 F G 化子句集S 应用归结原理对S中的子句进行归结并将归结式并入S 反复进行 直到出现空子句 命题逻辑的归结反演 示例 设已知公式集为 P P Q R SVT R T 求证R 解 设R为假并加入已知公式集得 P P Q R SVT R T R 化子句集得子句集FF P PV QVR SVR TVR T R 命题逻辑的归结反演 示例 对子句集F归结 过程如下归结演绎树 PV QVR P QVR R Q TVQ T T NIL 谓词逻辑的归结 定义3 23设C1和C2是两个没有公共变元的子句 L1和L2分别是C1和C2中的文字 如果L1和 L2存在最一般合一 则称C12 C1 L1 C2 L2 为C1和C2的归结式 谓词逻辑的归结 例 C1 P a VR x C2 P y VQ b 求C12 解 取L1 P a L2 P y 最一般合一 a y C12 P a R x P a P a Q b P a R x Q b R x VQ b 谓词逻辑的归结 例 设C1 P x VP f a VQ x C2 P y VR b 求C12 解 对参加归结的子句 若其内部有可合一的文字 在归结前应先进行合一处理 本例中C1中含有可合一的文字 f a x 是最一般合一 则有C1 P f a VQ f a C12 R b VQ f a 子句的因子 设C是一个子句 其内部有可合一的文字 是最一般合一 则称C 为子句C的因子 谓词逻辑的归结原理 定义3 24设C1和C2是两个没有公共变元的子句C1和C2的二元归结式 C1和C2的因子C2 的二元归结式 C1的因子C1 和C2的二元归结式 C1的因子C1 和C2的因子C2 的二元归结式 以上四种归结式都是C1和C2的归结式 记为C12 谓词逻辑归结的性质 谓词逻辑归结的性质与命题逻辑相同 即定理3 6 推论1 推论2和定理3 7的结论都成立 归纳以上的结论有 C12是其亲本子句C1和C2的逻辑结论 用归结式取代它在子句集S中的亲本子句 所得到的子句集保持原子句的不可满足性 一阶谓词逻辑的归结原理也是完备的 谓词逻辑的归结反演 谓词逻辑归结反演与命题逻辑归结反演过程基本相同 否定目标公式G 得 G 把 G并入到公式集F中 得 F G 把 F G 化子句集S 应用归结原理对S中的子句进行归结并将归结式并入S 反复进行 直到出现空子句 两个亲本子句的最一般合一 谓词逻辑归结反演 示例 例 已知F x y A x y B y y C y D x y G x C x x y A x y B y 求证G是F的逻辑结论 谓词逻辑归结反演 示例 证明 否定G 得到 F G 将其化为子句集 G x C x x y A x y B y x C x x y A x y V B y x C x V x y A x y V B y x C x x y A x y B y x C x y z A y z B z C z A f z g z B g z 谓词逻辑归结反演 示例 F x y A x y B y y C y D x y x y A x y B y V y C y D x y x y A x y V B y V z C z D x z x y z A x y V B y V C z D x z A x y V B y VC h x y A u v V B v VD u h u v 谓词逻辑归结反演 示例 子句集 A x y V B y VC h x y A u v V B v VD u h u v C z A f z g z B g z 谓词逻辑归结反演 示例 归结过程 A x y V B y 1与3归结 取 h u v z B g z 4与6归结 取 f z x g z y NIL5与7归结 谓词逻辑归结反演 示例 归结反演树为 A x y V B y VC h x y C z A x y V B y h u v z A f z g z B g z f z x g z y B g z NIL 快乐学生 问题 例 快乐学生 问题 假设任何通过计算机考试并获奖的人都是快乐的 任何肯学习或幸运的人都可以通过所有考试 李不肯学习但他是幸运的 任何幸运的人都能获奖 求证 李是快乐的 快乐学生 问题 解 定义谓词Pass x y x通过考试y Win