On renaming a set of clauses as a Horn set

Let S = {C₁, …, C_m} be a set of clauses in the propositional calculus and let n denote the number of variables appearing these clauses. We present and O(mn) time algorithm to test whether S can be renamed as a Horn set.     

leanTAP: Lean tableau-based deduction

prove ((E, F), A, B, C, D) : - !, prove (E, [F A], B, C, D).prove ((E; F), A, B, C, D) : - !, prove (E, A, B, C, D), prove (F, A, B, C, D).prove (all(H, I), A, B, C, D) : - !, + length (C, D), copy_term ((H, I, C), (G, F, C)), append (A, [all (H, I)], E), prove(F, E, B, [G C], D).prove (A,_, [C D] ,_, _) :-((A= – (B); – (A) = B)) -> (unify(B, C); prove (A, [], D,_,_)).prove (A, [E F], B, C, D): - prove (E, F, [AB], C,D).implements a first-order theorem prover based on free-variable semantic tableaux. It is complete, sound, and efficient.     

利用派生谓词和偏好处理OSP 问题的目标效益依赖

在过渡规划问题(over-subscribed planning,简称 OSP)研究中,如果目标之间不是相互独立的,那么目标坚定效益依赖比单个目标效益更能提高规划解的质量.但是,已有的描述模型不符合标准规划描述语言(planning domain descrion language,简称PDDL)的语法规范,不能在一般的OSP规划系统上进行推广,提出了用派生谓词规则和目标偏好描述效益依赖的方法,这二者均为ＰDDL语言的基本要素.实质上,将已有的GAI模型转化为派生谓词规则和目标偏好,其中派生谓词规则显式描述目标子集的存在条件,偏好机制用来表示目标子集的效益,二者缺一不可.该转换算法既可以保持在描述依赖关系时GAI模型的易用性和直观性上,又可以扩展一般的OSP规划系统处理目标效益依赖的能力.从理论上可以证明该算法在转化过程中的语义不变性,子啊基准领域的实验结果表明其可行性和规划解质量的改善能力.提出符合PDDL语言规范的目标效益依赖关系的描述形式,克服了已有模型不通用的缺点.     

集合论等式型定理机器证明系统的研究与开发

集合论定理机器证明,至今在国内外尚无相关研究。虽然集合论在数学领域中所处的基础地位显得在这一领域实现机械化极其重要,但是多年来尚无进展。到目前为止,还没有发现能产生可读证明的系统。通过对人工智能搜索算法的研究,提出了集合论等式型定理证明的机械化方法。实现的系统能自动生成定理的可读证明以及相关的说明。     

Mechanical verification of strategies

This paper presents a method of representing planning domains in the Boyer-Moore logic so that we can prove mechanically whether a strategy solves a problem. Current approaches require explicit frame axioms and state constraints to be included as part of a domain specification and use a programming language for expressing strategies. These make it difficult to specify domains and verify plans efficiently. Our method avoids explicit frame axioms, since domains are specified by programming an interpreter for sequences of actions in the Boyer-Moore logic. Strategies are represented as planners, Lisp programs that take an initial state and other arguments as input and return a sequence of actions that, when executed in the given initial state, will bring about a goal state. Mechanical verification of a strategy is accomplished by proving that the corresponding planner solves all instances of the given problem. We illustrate our approach by verifying strategies in some variations of the blocks world.The work described here was supported in part by NSF Grant MIP-9017499.     

TMPR: A tree-structured modified problem reduction proof procedure and its extension to three-valued logic

This paper deals with automated deduction for classical and partial logics, especially for the three-valued logic L3, which has been introduced, for example, in the study of natural language semantics. Based on ideas from a Plaisted's Gentzen style system for classical two-valued logic, we present a new tree-structured proof procedure (TMPR) together with a new completeness proof using proof transformation techniques and some improvements including the generation and use of lemmata. TMPR extends SLD-resolution with a Prolog-style backward chaining to full first-order logic by a controlled use of case analysis. This is done without having to extend negative goals needed, for example, for model elimination. A classification of TMPR, model elimination and related calculi in a common tableau framework is given. Thereafter, we present our extension of the TMPR proof procedure to L3 and show its soundness and completeness. As a side result, a TMPR proof system for the four-valued logic L4 is given. Finally, the restriction of TMPR to L3-Horn clauses is considered, and, additionally, an idea for similarly extending model elimination and related systems to L3 (and L4) is illustrated.This work is supported by the KI-Verbund NRW, founded by the Ministry for Science and Research of North Rhine Westphalia and by the Deutsche Forschungs Gemeinschaft in the scope of the research topic Deduktion, and is an extended version of a talk held at the German-Japanese Workshop on Logic and Natural Language (23–25 October 1990, in Kyoto, Japan).     

Higher-Order and Modal Logic as a Framework for Explanation-Based Generalization

Certain tasks, such as formal program development and theorem proving, fundamentally rely upon the manipulation of higher-order objects such as functions and predicates. Computing tools intended to assist in performing these tasks are at present inadequate in both the amount of knowledge they contain (i.e., the level of support they provide) and in their ability to learn (i.e., their capacity to enhance that support over time). The application of a relevant machine learning technique—explanation-based generalization (EBG)—has thus far been limited to first-order problem representations. We extend EBG to generalize higher-order values, thereby enabling its application to higher-order problem encodings.Logic programming provides a uniform framework in which all aspects of explanation-based generalization and learning may be defined and carried out. First-order Horn logics (e.g., Prolog) are not, however, well suited to higher-order applications. Instead, we employ Prolog, a higher-order logic programming language, as our basic framework for realizing higher-order EBG. In order to capture the distinction between domain theory and training instance upon which EBG relies, we extend Prolog with the necessity operator of modal logic. We develop a meta-interpreter realizing EBG for the extended language, Prolog, and provide examples of higher-order EBG.     

边缘计算: 万物互联时代新型计算模型

从智能手机、智能手表等小型终端智能设备,到智能家居、智能网联车等大型应用,再到智慧生活、智慧农业等,人工智能已经逐渐步入人们的生活,改变传统的生活方式. 各种各样的智能设备会产生海量的数据,传统的云计算模式已无法适应新的环境. 边缘计算在靠近数据源的边缘侧实现对数据的处理,可以有效降低数据传输时延,减轻网络传输带宽压力,提高数据隐私安全等. 在边缘计算架构上搭建人工智能模型,进行模型的训练和推理,实现边缘的智能化,对于当前社会至关重要. 由此产生的新的跨学科领域——边缘智能（edge intelligence,EI）,开始引起了广泛的关注. 全面调研了边缘智能相关研究：首先,介绍了边缘计算、人工智能的基础知识,并引出了边缘智能产生的背景、动机及挑战. 其次,分别从边缘智能所要解决的问题、边缘智能模型研究以及边缘智能算法优化3个角度对边缘智能相关技术研究展开讨论. 然后,介绍边缘智能中典型的安全问题. 最后,从智慧工业、智慧生活及智慧农业3个层面阐述其应用,并展望了边缘智能未来的发展方向和前景.

     

一阶逻辑知识库的检测

本文提出的方法是以Loveland的MESON一阶逻辑定理证明过程为基础,用于一阶逻辑规则知识库的冗余性和不一致性的检测.知识库的规则可包含非真、或及if-and-only-if规则.系统以交互形式从正、反向推理研究知识库规则增加时的变化.     

多媒体智能：当多媒体遇到人工智能

过去10年中涌现出大量新兴的多媒体应用和服务,带来了很多可以用于多媒体前沿研究的多媒体数据。多媒体研究在图像/视频内容分析、多媒体搜索和推荐、流媒体服务和多媒体内容分发等方向均取得了重要进展。与此同时,由于在深度学习领域所取得的重大突破,人工智能(artificial intelligence,AI)在20世纪50年代被正式视为一门学科之后,迎来了一次“新”的发展浪潮。因此,一个问题就自然而然地出现了：当多媒体遇到人工智能时会带来什么？为了回答这个问题,本文通过研究多媒体和人工智能之间的相互影响引入了多媒体智能的概念。从两个方面探讨多媒体与人工智能之间的相互影响：一是多媒体促使人工智能向着更具可解释性的方向发展;二是人工智能反过来为多媒体研究注入了新的思维方式。这两个方面形成了一个良性循环,多媒体和人工智能在其中不断促进彼此发展。本文对相关研究及进展进行了讨论,并围绕值得进一步探索的研究方向分享见解。希望可以对多媒体智能的未来发展带来新的研究思路。     

基于MK的实数公理系统相容性和范畴性的Coq形式化

数学定理机器证明是人工智能基础理论的深刻体现. 实数理论是数学分析的基础, 实数公理系统是建立实数理论的重要方法. Morse-Kelley公理化集合论(MK)作为现代数学的基础, 也为实数构建提供了严谨的数学框架和工具. 本文使用定理证明器Coq, 基于MK对实数公理系统进行了深入探索. 在优化了MK形式化代码的基础上, 形式化构建了完整的实数公理系统, 并通过形式化Landau《分析基础》中的实数模型, 证明其相对于MK相容, 此外, 还形式化证明了实数公理系统所有模型在同构意义下是唯一的, 验证了实数公理系统的范畴性. 本文全部定理无例外地给出Coq的机器证明代码, 所有形式化过程已被Coq验证, 并在计算机上运行通过, 充分体现了基于Coq的数学定理机器证明具有可读性、交互性和智能性的特点, 其证明过程规范、严谨、可靠. 该系统可方便地应用于拓扑学和代数学理论的形式化构建. 谨以此文庆祝我国著名控制系统专家秦化淑研究员九十华诞!     

SGARP中符号计算模块的实现及其应用

可持续发展的几何自动推理平台(sustainable geometry automated reasoning platform, SGARP)支持用户按需添加或修改几何定理机器证明所涉及的几何对象、谓词、定理和规则,以发展多种多样基于规则的机器自动推理或人机交互推理方法.为进一步提高SGARP的推理能力和扩展其适用范围,提出一种在SGARP中实现符号计算功能的快捷方法,并成功添加了质点法和解析法推理模块.质点法可证明希尔伯特交点类几何命题,解析法能用于辅助证明各种类型有一定难度的几何定理,如著名的Thebault定理.对这两种方法用基于Web的机器证明测试用的几何问题库(thousands of geometric problems for geometric theorem provers, TGTP)中180道几何题进行评估,均在合理时间内给出令人满意的可读机器证明,表明升级后的SGARP能更好地满足用户学习与发展几何机器推理的需求.     

An overview of automated reasoning and related fields

This article provides an overview of automated reasoning and of the various fields for which it is relevant. It takes the form of a collection of articles, each covering some field and each written by an expert in that field. A field is introduced, its elements reviewed, the current state of the art given, the basic problems discussed, and the various goals listed. Although individually the goals of each field present a wide spectrum, collectively the fields share the interest of automating the process known as reasoning.     

状态空间的启发式搜索方法研究

对人工智能中用于状态空间问题求解的启发式搜索方法－A算法和A^*算法进行了详细分析，并指出了影响搜索算法启发能力的主要因素和提高搜索效率的措施。