第3章确定性推理方法

1、人工智能原理及应用人工智能原理及应用第第3章章 确定性推理方法确定性推理方法3.1 推理的基本概念推理的基本概念 已知事实已知事实（证据）（证据）已有知识已有知识新的事实新的事实（结论）（结论）3.1 推理的基本概念推理的基本概念由一般到个别由一般到个别l 大前提: BCl 小前提: ABl 三段论: AC3.1 推理的基本概念推理的基本概念由一般到个别由一般到个别l 大前提: 计算机学院的学生都会编程序l 小前提: 李强是一名计算机学院的学生l 结论: 李强会编程序3.1 推理的基本概念推理的基本概念由个别到一般由个别到一般l A的所有实例具有X属性 (完全归纳)l 结论: A具有X属性3.

2、1 推理的基本概念推理的基本概念由个别到一般由个别到一般l 检查某厂的所有产品均合格 (完全归纳)l 结论: 该厂的产品合格3.1 推理的基本概念推理的基本概念由个别到一般由个别到一般l A的部分实例具有X属性 (部分归纳)l 结论: A具有X属性3.1 推理的基本概念推理的基本概念由个别到一般由个别到一般l 抽查某厂的一部分产品合格 (部分归纳)l 结论: 该厂的产品合格3.1 推理的基本概念推理的基本概念由个别到一般由个别到一般l A具有X属性l B与A类似 (类比归纳)l 结论: B具有X属性3.1 推理的基本概念推理的基本概念由个别到一般由个别到一般l 软件工程专业的学生都会编程序l

3、计算机科学与技术与软件工程专业方向类似 (类比归纳)l 结论: 计算机科学与技术专业的学生都会编程序3.1 推理的基本概念推理的基本概念知识不完全的情况下的推理知识不完全的情况下的推理l ABl 没有证据证明Al 结论: B3.1 推理的基本概念推理的基本概念知识不完全的情况下的推理知识不完全的情况下的推理l 未满18岁不能进入营业性网吧l 不知道学生李强的真实年龄l 李强不能进入营业性网吧3.1 推理的基本概念推理的基本概念已知事实已知事实（证据）（证据）已有知识已有知识新的事实新的事实（结论）（结论）3.1 推理的基本概念推理的基本概念已知事实已知事实（证据）（证据）已有知识已有知识新的事

4、实新的事实（结论）（结论）3.1 推理的基本概念推理的基本概念已知事实已知事实（证据）（证据）已有知识已有知识新的事实新的事实（结论）（结论）3.1 推理的基本概念推理的基本概念Y3.1 推理的基本概念推理的基本概念3.1 推理的基本概念推理的基本概念事实事实: AB知识知识: ACD BEF目标目标: CFA?BABABCDEFCF目标匹配匹配F规则已知事实r1r2 3.1 推理的基本概念推理的基本概念事实事实: P(x,y)(Q(x)R(v,y)知识知识: P(u,v)(S(u)N(v)目标目标: S(x)N(y)Q(x)推理示例推理示例知识库知识库事实事实目标结论目标结论推理示例推理示例

5、g(x)4.5g(x)4.5 g(x)4.5A(x)g(x)4E(x)A(x) E(x) E(x) A(x)推理示例推理示例如何对事实进行如何对事实进行合理的归纳？合理的归纳？如何选择事实的如何选择事实的推理顺序？推理顺序？3.1 推理的基本概念推理的基本概念推理示例推理示例知识库知识库事实事实问题：请问谁是小偷？问题：请问谁是小偷？推理示例推理示例如何选择假设的如何选择假设的验证顺序？验证顺序？3.1 推理的基本概念推理的基本概念3.1 推理的基本概念推理的基本概念3.2 自然演绎推理自然演绎推理（1）双重否定律：）双重否定律： （2）交换律：）交换律： （3）结合律：）结合律： （4）分配

6、律：）分配律： （5）摩根定律：）摩根定律： PP )()(),()(PQQPPQQP)()(RQPRQP)()(RQPRQP)()()(RPQPRQP)()()(RPQPRQP(PQ)PQ(PQ)PQ3.2 自然演绎推理自然演绎推理（6）吸收律：）吸收律： （7）补余律）补余律: （8）连词化归律）连词化归律: （9）量词转换律）量词转换律: （10）量词分配律）量词分配律: PQPP)(PQPP)(FPPTPP,QPQP)()(PQQPQP)(PPxx ）（)()(PxPxQxPxQPx)()()(QxPxQPx)()()(PQ)(PQ) (QP)3.2 自然演绎推理自然演绎推理（1）化简

7、式：）化简式： （2）附加式：）附加式： （3）析取三段论：）析取三段论： （4）假言推理：）假言推理： （5）拒取式：）拒取式： QQPPQP,QPQQPP,QQPP,QQPP,PQPQ,3.2 自然演绎推理自然演绎推理（6）假言三段论：）假言三段论： （7）二难推理：）二难推理： （8）全称固化：）全称固化： 其中，其中，y是个体域中的任一是个体域中的任一个体，依此可消去谓词公式中的全称量词。个体，依此可消去谓词公式中的全称量词。（9）存在固化：）存在固化： 其中，其中，y是个体域中某一个是个体域中某一个可以使可以使 P(y)为真的个体，依此可消去谓词公式中的存在量词。为真的个体，依此可消

8、去谓词公式中的存在量词。RPRQQP,RRQRPQP,),()()(yPxPx,)()()(yPxPx3.3 谓词公式转换为子句集谓词公式转换为子句集3.3 谓词公式转换为子句集谓词公式转换为子句集消去连接词消去连接词“”和和“”把否定符号把否定符号“”移到每个谓词符号的前面移到每个谓词符号的前面变量标准化（使不同量词约束的变量有不同的名字）变量标准化（使不同量词约束的变量有不同的名字）引入引入Skolem函数消去存在量词函数消去存在量词化为前束形（使所有全称量词在公式最前面）化为前束形（使所有全称量词在公式最前面）化为化为Skolem标准形（子句的合取式）标准形（子句的合取式）略去全称量词略

9、去全称量词断开合取式得到子句集断开合取式得到子句集变量名标准化变量名标准化3.3 谓词公式转换为子句集谓词公式转换为子句集)()()()(),()()()()(xBxPxxQyxSyxQxPx)()()()(),()()()()(xBxPxxQyxSyxQxPx)()()()(),()()()()(xBxPxxQyxSyxQxPx)()()()(),()()()()(wBwPwxQyxSyxQxPx)()()()()(,()()()(wBwPwxQxfxSxQxPx)()()()(,()()()(wBwPxQxfxSxQxPwx)()()()(,()()(wBwPxQxfxSxPwx)()()

10、()(,()(wBwPxQxfxSxP)(,()(xfxSxP)(xQ)()(wBwP)(,()(xfxSxP( )Q y)()(wBwP3.4 消解原理消解原理C1: PQC2: PRC12: QR3.4 消解原理消解原理C1: P(x)Q(x)C2: P(a)R(y)C12: Q(a)R(y)3.5 归结反演归结反演(1)将已知前提表示为谓词将已知前提表示为谓词F(2)将待证明结果表示为谓词将待证明结果表示为谓词Q(3)将谓词公式将谓词公式FQ化为子句集化为子句集S(4)应用归结原理对应用归结原理对S中的子句进行归结，直至出现空子句，则证明中的子句进行归结，直至出现空子句，则证明Q为真为真推理示例推理示例知识库知识库事实事实问题：请问谁是天使，谁是魔鬼，谁是凡人？问题：请问谁是天使，谁是魔鬼，谁是凡人？3.5 归结反演归结反演案例研究案例研究: 故障推理故障推理(USB驱动安装错误驱动安装错误) (USB口损坏口损坏) (USB口无法使用口无法使用) (设置了静音设置了静音) (音频设备错误音频设备错误) (没有声音