非归结定理证明

数学术语

非归结定理证明是不用归结原理而用自然演绎技术与探试策略等相结合的一种机器定理证明技术。

作用

不用归结原理而用自然演绎技术与探试策略等相结合的一种机器定理证明技术。

为了提高归结证明过程的效率，曾提出各种改进方案。另一条途径是在定理的机器证明中不用归结原理而用历史上早已形成的自然推理或称自然演绎技术，但在其中引入问题所需的特定探试策略。这就是1977年W.W.布莱塞提出的所谓非归结定理证明的基本思想。作为这种思想的具体体现，曾研制出一个运用探试策略的新的自然演绎系统IMPLY。R.S.鲍耶和 J.S.莫尔的数学归纳法机械定理证明系统也是成功地运用探试策略的一个重要例子。

重要例子

自然演绎系统由一组公理和一套推理规则组成，每条推理规则将若干恒真式映射为一个恒真式。如果存在一个恒真式系列，使得序列中每一恒真式或者是一公理，或者是一定理（即可从序列中位于其前的恒真式根据推理规则导出），则序列中最后一项恒真式称为在该推理系统中可导出（或可证明）。一阶逻辑的推理系统是完备的，也就是每一恒真式都可从该系统中导出。如果推理系统的公理和推理规则比较丰富，使得每一恒真式的导出过程都很自然，符合人的思维习惯，这样的推理系统称为自然推理系统或自然演绎系统。根据数理逻辑中著名的哥德尔定理，对于二阶逻辑不存在完备的演绎系统。采用不同的公理、推理规则，便可得到不同的自然演绎系统。著名的根岑系统便是20世纪30年代提出的典型的自然演绎系统。自然演绎系统的显著特点是在证题全过程中，始终维持前提和结论的明确界限。例如在下例的推理图式中，横线以上的H1、H2、H3是前提。

横线以下的C1，C2则是有待证明的结论。由H1，H2可推出C1（根据充分条件的假言推理原则），又根据H3和已推出的C1可推出C2。同样的例子如运用归结原理，其子句集可表示为

2 塡P∨Q

3 塡R∨-Q∨S

4 塡Q∨S

5 塡Q∨塡S

此时由于采用反证法，将结论的否定式并入子句集，不区分前提与结论，有关的推理信息便已丧失。自然演绎的优点是推理过程自然易懂，有利于发挥人机交互作用，便于引用探试策略。缺点是要用许多条复杂的推理规则。而运用归结原理，虽然推理过程不易控制，但只需要一条推理规则。因此，自然演绎与归结原理的优缺点是相比较而存在的，具有相对的意义，不能绝对化。

参考书目

W.W.Bledsoe，Non-resolutiontheoremProving，Artificial Intelligence, North-Holl and Publ.Co., Amsterdam,1977.

Zohor Manna,Mathematical Theory of computation, McGraw-Hill,New York,1974.

R.S.Boyer and J.S.Moore, A Computational Logic, Academic Press,New York,1979.

全国各地天气预报查询

上海市

市辖区

云南省

临沧市

云南省

丽江市

云南省