第3章 确定性推理方法

人工智能原理及应用第3章确定性推理方法PrinciplesandApplicationsofArtificialIntelligence知识表示：将知识以某种模式存储到计算机中。智能：知识能力+思维能力（运用知识求解问题）推理：计算机的逻辑思维第3章确定性推理方法3.1 推理的基本概念

3.2 自然演绎推理

3.3 谓词公式转换为子句集3.4消解原理

3.5 归结反演

3.1推理的基本概念

推理

已知事实（证据）已有知识新的事实（结论）3.1推理的基本概念推理方式演绎推理(deductivereasoning)

由一般到个别大前提:BC小前提:AB

三段论:AC3.1推理的基本概念推理方式演绎推理(deductivereasoning)

由一般到个别大前提:计算机学院的学生都会编程序小前提:李强是一名计算机学院的学生结论:李强会编程序3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)

由个别到一般

A的所有实例具有X属性(完全归纳)结论:A具有X属性3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)

由个别到一般检查某厂的所有产品均合格(完全归纳)结论:该厂的产品合格3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)

由个别到一般

A的部分实例具有X属性(部分归纳)结论:A具有X属性3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)

由个别到一般抽查某厂的一部分产品合格(部分归纳)结论:该厂的产品合格3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)

由个别到一般

A具有X属性

B与A类似(类比归纳)结论:B具有X属性3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)

由个别到一般软件工程专业的学生都会编程序计算机科学与技术与软件工程专业方向类似(类比归纳)结论:计算机科学与技术专业的学生都会编程序3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)缺省推理(defaultreasoning)

知识不完全的情况下的推理

AB没有证据证明A结论:B3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)缺省推理(defaultreasoning)

知识不完全的情况下的推理未满18岁不能进入营业性网吧不知道学生李强的真实年龄李强不能进入营业性网吧3.1推理的基本概念推理方式确定性推理:证据和知识都是确定的——结论也是确定的不确定性推理:证据和知识不都是确定——结论也是不确定的

已知事实（证据）已有知识新的事实（结论）3.1推理的基本概念推理方式单调推理:从证据不断接近结论非单调推理:可能推翻已有的结论

已知事实（证据）已有知识新的事实（结论）3.1推理的基本概念推理方式启发式推理:推理过程中运用了启发式知识非启发式推理

已知事实（证据）已有知识新的事实（结论）3.1推理的基本概念推理的方向正向推理:从已知事实出发，逐步尝试推导出结论，或证明问题无解Y3.1推理的基本概念推理系统的基本要素知识库数据库推理机3.1推理的基本概念正向推理事实:AB知识:ACD

BEF目标:CF3.1推理的基本概念正向推理事实:P(x,y)(Q(x)R(v,y))知识:P(u,v)(S(u)N(v))目标:S(x)N(y)Q(x)推理示例知识库平均绩点超过4.5分的学生，授予一等奖学金评为优秀研究生的学生，平均绩点不能少于4分事实10名学生中，3人绩点超过4.5，其余绩点均低于4目标结论评为优秀研究生的学生都获得了一等奖学金获得了一等奖学金的学生都被评为优秀研究生推理示例g(x)>4.5g(x)<4g(x)>4.5∨g(x)<4g(x)>4.5A(x)g(x)<4E(x)A(x)E(x)E(x)A(x)推理示例如何对事实进行合理的归纳？如何选择事实的推理顺序？3.1推理的基本概念推理的方向正向推理:从已知事实出发，逐步尝试推导出结论，或证明问题无解逆向推理:从假设目标出发，逐步尝试找出其证据，或证明问题无解推理示例知识库4个嫌疑犯中有一个是小偷，且4人中只有一个说假话事实A说“我不是小偷”B说“C是小偷”C说“D是小偷”D说“C说谎”问题：请问谁是小偷？推理示例如何选择假设的验证顺序？3.1推理的基本概念推理的方向正向推理:从已知事实出发，逐步尝试推导出结论，或证明问题无解逆向推理:从假设目标出发，逐步尝试找出其证据，或证明问题无解混合推理3.1推理的基本概念冲突：已知事实可与知识库中的多条知识匹配冲突消解按针对性排序按事实新鲜性排序按匹配度排序按条件个数排序3.2自然演绎推理命题公式及其等价式（1）双重否定律：

（2）交换律：

（3）结合律：

（4）分配律：

（5）摩根定律：

~(P∨Q)~P∧~Q~(P∧Q)~P∨~Q3.2自然演绎推理命题公式及其等价式（6）吸收律：

（7）补余律:（8）连词化归律:

（9）量词转换律:

（10）量词分配律:P<->Q)(P∧Q)∨(~Q∧~P)3.2自然演绎推理永真蕴含式

（1）化简式：

（2）附加式：

（3）析取三段论：

（4）假言推理：

（5）拒取式：

3.2自然演绎推理永真蕴含式

（6）假言三段论：

（7）二难推理：

（8）全称固化：

其中，y是个体域中的任一个体，依此可消去谓词公式中的全称量词。（9）存在固化：

其中，y是个体域中某一个可以使

P(y)为真的个体，依此可消去谓词公式中的存在量词。3.3谓词公式转换为子句集文字:原子公式或其否定子句:文字的析取式谓词:子句的合取式3.3谓词公式转换为子句集文字:原子公式或其否定子句:文字的析取式谓词:子句的合取式消去连接词“→”和“↔”把否定符号“～”移到每个谓词符号的前面变量标准化（使不同量词约束的变量有不同的名字）引入Skolem函数消去存在量词化为前束形（使所有全称量词在公式最前面）化为Skolem标准形（子句的合取式）略去全称量词断开合取式得到子句集变量名标准化3.3谓词公式转换为子句集3.4消解原理消解原理(RobinsonTheorem)命题逻辑中的归结原理:如果C1和C2为真，则C12为真推论1:C1,C2S,则S{C1|C12,C2|C12}不可满足S不可满足推论2:C1,C2S,则S{C12}不可满足S不可满足C1:PQC2:PRC12:QR3.4消解原理消解原理(RobinsonTheorem)谓词逻辑中的归结原理:如果C1和C2为真，则C12为真推论1:C1,C2S,则S{C1|C12,C2|C12}不可满足S不可满足推论2:C1,C2S,则S{C12}不可满足S不可满足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为真推理示例知识库天使只说真话不说假话魔鬼只说假话不说真话凡人有时候说真话有时候说假话事实A,B,C三人分别是天使、魔鬼和凡人A说“我不是天使”。B说“我不是魔鬼”。C说“我不是凡人”问题：请问谁是天使，谁是魔鬼，谁是凡人？3.5归结反演归结反演:可能产生大量不必要的归结式控制策略删除无用子句限制子句的归结范围案例研究:故障推理(USB驱动安装错误)∨(USB口损坏)(USB口无法使用)(设置了静音)∨(音频设备错误)(没有声音)(音频设备被禁用)∨(声卡驱动安装错误)∨(病毒程序破坏了音频服务)∨(声卡硬件损坏)∨(扬声器硬件损坏)(音频设备错误)人工智能推理领域学术刊物重要国际期刊InternationalJournalofApproximateReasoning,Elsevier(/international-journal-of-approximate-reasoning/)IF:1.729JournalofAutomatedReasoning,Springer(/journal/10817)IF:0.567人工智能推理领域学术刊物重要国际会议InternationalJointConferenceonAutomatedReasoning(IJCAR),/InternationalConferenceonCase-BasedReasoning,/InternationalConferenceonPrinciplesofKnowledgeRepresentationandReasoning,

作业用确定性推理技术求解以下问题一宗盗窃案有的5个嫌疑犯，他们当中只有3个人说的是真话。A说“D是小偷”;B