基于语义tableau的一阶逻辑自动定理证明.doc

基于语义tableau的一阶逻辑自动定理证明!""#$!!!计算机工程与应用基于语义!"#$%&’的一阶逻辑自动定理证明刘全孙吉贵"!苏州大学计算机科学与技术学院"苏州#"$%%&#’!%%"($#!吉林大学计算机科学与技术学院"长春)*+,-./01,2.-13415,6751682摘要自动推理作为自动定理证明的扩展是人工智能研究的基础工作"许多重要的人工智能系统都是以推理系统为其核心部分9其中的:,;.7,1方法"由于具有通用性%直观性及易于计算机实现等特点"至今成为重要的自动推理方法之一&在:,;.7,1方法基础上"讨论了一阶逻辑中的自动定理证明理论"提出使用模型存在定理证明其可靠性和完备性的方法&同时也给出了带等词:,;.7,1方法的证明过程&关键词语义:,;.7,1有效性完备性文章编号%""!&’((%&!!""#$!!&%%((*%!文献标识码)中图分类号<=">(’!)*&!%+,-%).%*/.)01234&5%+)26%*&2!17,&#$%&’!9:.+%.;)317;1’<’&26’2=13’1’!?24:-:1:******@AB@+C1:7DE8-7287,25<******@.***@GH"E@***@******@IJ2-K7D4-:H"******@1(M$%%&#(!******@..******@AB@+C1:7DE8-7287,25<******@.***@GH"N-.-2J2-K7D4-:H"BF,2G8F12M!O%"($(#5!.&7!>P1:@+,:7557518:-***@2IF-8F-47Q:724-***@2:@,1:@+,:75:******@D7+******@K-2G-4,;,4-******@******@A,D:-A-8-,.-2:7..-G7287ST,2H-+******@D:,2:4H4:7+******@A,D:-A-8-,.-2:7..-G7287D7G,D557518:-***@24H4:7+,******@D7C,D:S<***@5,H:,;.7,1+7:******@5F,4;78@+******@******@A:F7+,-257518:-***@24";78,147-:-412-K7D4,.,25-2:1-:-***@2-4:-8",257,4H:@;7-++72:75SU,******@2:,;.7,1:F7:******@D-******@A,1:@+,:75:******@D7+******@K-2G-2A-D4:****@D57D.***@G-8,D75-******@******@K-2G:******@1252744,25:F78@+:72744":F7+7:******@******@A:******@D7+******@K-2G14-2G:F7+***@-4:7287:******@D7+,D7CD7472:75S?2:F7+7,2:-+7":F-4C,******@I4CD@***@******@******@A:,;.7,1I-:F701,.-:HS?%***@A).+5%47+,2:-8:,;.7,1"******@1252744"8@+:72744基金项目!国家自然科学基金&编号%&%(W!%>%"&%XW!%%!$资助作者简介!刘全&%*+**$"男"博士"副教授"研究方向为智能信息处理"自动推理"地理信息系统’孙吉贵!%*+(*$"男"博士"教授"博士生导师"研究方向为人工智能"自动推理’"引言研究证明理论通常的方法有多种"不同的方法对于不同:,;.7,1的逻辑系统处理能力各有优劣"其中的归结法和语义法适合于自动推理"归结法与合取范式或子句的形式相联系"语义:,;.7,1法与析取范式或对偶子句的形式密切相关’归结法对于经典逻辑非常有效"但对于非经典逻辑却存在困难"对于不同的逻辑需构造不同的归结过程"因此本文讨论自动定理证明主要采用:,;.7,1"按照文献Y%Z的方法"研究语义:,;.7,1的证明过程’语义:,;.7,1由U7:F!M[$[$(\-2:-RR,!M[$$$引入的’<,;.7,1是按照某种规则在有向二叉树的每个节点上都标记有一个合式公式而构成’换句话说"通过引入相应的谓词公式"将二元关系的性质用逻辑公式表示出来"对于不同的逻辑系统"只是对公式构造集进行扩展’因此"这种方法有较强的通用性和直观性"并易于计算机实现自动推理’(:,;.7,1扩展规则:,;.7,1方法中":,;.7,1的扩展规则如下/规则M合取规则!!规则$!!!!"!!#!$"!"!!$"$!"!!%"$"!!"""!!规则!析取规则!"规则$"!!&!$"!!#"!!$""!!!%"!"""!"!规则(否定规则""!!"’("(’规则,全称规则!#规则$对于#$%&中的任意项’"有%!)($$$]()’^"!*($$"$]()’^规则#存在规则!%规则$对于新的参数$"有%"!)($$"$]()$^!*($$$]()$^((计算机工程与应用!""#$!!!"#$%&’(证明过程定义)令*!)!!+!"!!",为公式的有