第4 讲 归结原理(不讲).ppt

1、1、人工智能原理第4课的归纳原理，星期日归化洞交通大学信息工程学院，2，归纳原理，4.1介绍4.2第1逻辑4.3节4.4赫布兰定理4.5替换和集成4.6归纳原则4.7归纳方法的完整性4.8归纳策略，3，4.1介绍，自动整理证明历史4色定理3种方法定理证明是一种智力行为。反映了人类逻辑推理的能力。使用推理来实现里维尼斯的梦想：livinis imia gined a universal formal calculus which could express reasoning in any subject，And an algorithmic procedure which coocoedure

2、.5，1930年，赫布兰定理。反判问题。一阶逻辑的判定问题。在一阶逻辑中，有什么方法可以判断哪些命题是定理吗？(没有任何公式可以从公理和推理规则中推导出来的方法。)维修逻辑的基本问题。1936年证明了基本问题是无法解决的。在一阶逻辑中，如果定理是正确的，机械方法可以在有限的阶段内证明它。一阶谓词逻辑的表达能力很强，所有可计算函数都可以用一阶谓词来表达。6，历史，纳威，肖，西蒙1956年，Shaw logic theory machine。数学定理证明程序(logic theorist) mimic human REE，7，王浩1958年，IBM704计算机，3-5分钟，在数学原理中证明了所有关

3、于命题运算的220个定理。1959年，8.4分钟，证明了数学原理中的全部(350多个)定理。罗素：“我希望怀缇海和我浪费了十年，在证明这个定理之前，就知道有这种可能性。”1983年获得了第一届自动整理证明里程碑奖。8，4色整理，1852年，21岁大学生提出的数学问题：任何地图最多可以用4种颜色上色，以便区分两个相邻的国家或地区。9，4色定理，1976年7月，美国的Appel(K . Appel)等共同解决了124年来的难题4色定理。他们利用3台大型计算机花费1200小时的CPU时间，人为地修改了500多处中间结果。四色定理的成功证明了计算机界轰动一时。伊利诺伊数学杂志第21卷中的检查表(460

4、p)，10，3种方法，归并方法判定方法，11 1960年，M.Davis和H.Putnam的改进：Davis非本质技术：基于枚举的替代。1960年，D.Prawitz亲自寻找替换，避免了组合爆炸。思想深刻，效果不理想。1965年，J.A.Robinson提出了归纳原理One-literal Rule的扩展。12，提高效率1965: WOS，G.A. Robinson，Curson，支持集摘要1967:矿渣，含义摘要；1970:Loveland，Luckham，线性归结；1971年：看，锁归结为。1978年：刘玉玲书画，锁定语义摘要；1979年：王相浩，刘玉玲徐华，概括总结；13，human s

5、imulation，1956年，Newell，Shaw，Simon The logic theory machine 1966年，MIT的L启发式1972年R . Boyer1977年，bled SOE:non-resolution theorem proving，14，判定方法，在小范围内找到了有效的判定方法。早期作业：A.Tarski的初等代数和初等几何的方法。王浩：命题逻辑的有效判定方法。吴文俊：吴法(1977)。，15，吴法，平面几何定理几何问题-代数问题1959年，Geometry Theorem Proving Machine，几何定理线性图形大部分高中考试问题运行时间与高中生解决

6、问题的时间相似。“国际Herbrand自动推理杰出成果奖”o的工作证明了几何定理在不太成功的领域中是最成功的领域之一。在很少的领域，我们可以把整理机器归于一个人的工作。几何定理就是这样的领域(中国)，16，4.2第一逻辑，基本概念适当公式的解释前束范式和提取范式逻辑结论，17，1。基本概念，定义(述词):D为非空的物件名称集合，Dn中的定义Dn代表集合D的第n个直角积。例如：Man(x) Greater(x，y)，18，1。函数，函数(函数)是映射。f: D D D D d范例：变数father (x)，19是项目。f是n元函数符号，t1，T2，如果TN是项目，则f(t1，T2，TN)也是项目。所有项目都是通过应用上述规则创建的。谓词不能是条目。21，2。适当的公式(wf