一类扩展的动态描述逻辑

作为描述逻辑的扩展,动态描述逻辑为语义Web服务的建模和推理提供了一种有效途径.在将语义Web服务建模为动作之后,动态描述逻辑从动作执行结果的角度提供了丰富的推理机制,但对于动作的执行过程却不能加以处理.借鉴Pratt关于命题动态逻辑的相关研究,一方面,对动态描述逻辑中动作的语义重新进行定义,将每个动作解释为由关于可能世界的序列组成的集合;另一方面,在动态描述逻辑中引入动作过程断言,用来对动作的执行过程加以刻画.在此基础上提出一类扩展的动态描述逻辑EDDL(X),其中的X表示从ALC(attributive language with complements)到SHOIN(D)等具有不同描述能力的描述逻辑.以X为描述逻辑ALCQO(attributive language with complements,qualified number restrictions and nominals)的情况为例,给出了EDDL(ALCQO)的表判定算法,并证明了算法的可终止性、可靠性和完备性.EDDL(X)可以从动作执行过程和动作执行结果两个方面对动作进行全面的刻画和推理,为语义Web服务的建模和推理提供了进一步的逻辑支持.     

模糊面向对象数据模型的描述逻辑表示与推理

通过分析描述逻辑与面向对象数据模型之间的关系,研究了基于描述逻辑的模糊面向对象数据(fuzzy object-oriented data,简称FOOD)模型的表示与推理.首先,进一步研究了FOOD模型,提出了FOOD模型的形式化定义和语义定义,以便更好地在FOOD模型与模糊描述逻辑之间建立对应关系;然后,针对FOOD模型的特点和推理需求,介绍了模糊描述逻辑f-ALCIQ.在此基础上,研究了基于f-ALCIQ的FOOD模型的表示与推理,包括:实现了从FOOD模型到f-ALCIQ知识库在结构层和实例层上的转化,即实现了从FOOD模型到f-ALCIQ TBox的转化,以及从FOOD模型相应的数据库实例到f-ALCIQ ABox的转化;进而,基于转化得到的f-ALCIQ知识库,研究了如何利用f-ALCIQ的推理机制对FOOD模型的推理问题(一致性、包含性和冗余性等)进行推理;最后,设计并实现了基于f-ALCIQ的模糊描述逻辑推理机(FRsQ推理机),实现了对FOOD模型和f-ALCIQ模糊概念知识的自动推理.     

Combining and automating classical and non-classical logics in classical higher-order logics

Numerous classical and non-classical logics can be elegantly embedded in Church??s simple type theory, also known as classical higher-order logic. Examples include propositional and quantified multimodal logics, intuitionistic logics, logics for security, and logics for spatial reasoning. Furthermore, simple type theory is sufficiently expressive to model combinations of embedded logics and it has a well understood semantics. Off-the-shelf reasoning systems for simple type theory exist that can be uniformly employed for reasoning within and about embedded logics and logics combinations. In this article we focus on combinations of (quantified) epistemic and doxastic logics and study their application for modeling and automating the reasoning of rational agents. We present illustrating example problems and report on experiments with off-the-shelf higher-order automated theorem provers.     

The Calculus of Relations as a Foundation for Mathematics

A variable-free, equational logic $\mathcal{L}^\timesA variable-free, equational logic based on the calculus of relations (a theory of binary relations developed by De Morgan, Peirce, and Schr?der during the period 1864–1895) is shown to provide an adequate framework for the development of all of mathematics. The expressive and deductive powers of are equivalent to those of a system of first-order logic with just three variables. Therefore, three-variable first-order logic also provides an adequate framework for mathematics. Finally, it is shown that a variant of may be viewed as a subsystem of sentential logic. Hence, there are subsystems of sentential logic that are adequate to the task of formalizing mathematics. This paper is an expanded version of a talk given by the author at the Special Session on Automated Reasoning in Mathematics and Logic, held March 8–10, 2002, at the Georgia Institute of Technology, during the Joint Southeastern Section MAA/Southeast Regional AMS Meeting. The session was organized by Johan G. F. Belinfante.     

A connection between the Cantor–Bendixson derivative and the well-founded semantics of finite logic programs

Results of Schlipf (J Comput Syst Sci 51:64?C86, 1995) and Fitting (Theor Comput Sci 278:25?C51, 2001) show that the well-founded semantics of a finite predicate logic program can be quite complex. In this paper, we show that there is a close connection between the construction of the perfect kernel of a $\Pi^0_1$ class via the iteration of the Cantor?CBendixson derivative through the ordinals and the construction of the well-founded semantics for finite predicate logic programs via Van Gelder??s alternating fixpoint construction. This connection allows us to transfer known complexity results for the perfect kernel of $\Pi^0_1$ classes to give new complexity results for various questions about the well-founded semantics ${\mathit{wfs}}(P)$ of a finite predicate logic program P.     

Multi-Agent Dynamic Logics with Informational Test

This paper investigates a family of logics for reasoning about the dynamic activities and informational attitudes of agents, namely the agents' beliefs and knowledge. The logics are based on a new formalisation and semantics of the test operator of propositional dynamic logic and a representation of actions which distinguishes abstract actions from concrete actions. The new test operator, called informational test, can be used to formalise the beliefs and knowledge of particular agents as dynamic modalities. This approach is consistent with the formalisation of the agents' beliefs and knowledge as K(D)45 and S5 modalities. Properties concerning informativeness, truthfulness and preservation of beliefs are proved for a derivative of the informational test operator. It is shown that common belief and common knowledge can be expressed in the considered logics. This means, the logics are more expressive than propositional dynamic logic with an extra modality for belief or knowledge. The logics remain decidable and belong to 2EXPTIME. Versions of the considered logics express natural additional properties of beliefs or knowledge and interaction of beliefs or knowledge with actions. It is shown that a simulation of PDL can be constructed in one of these extensions.     

Fermat,Euler, Wilson - Three Case Studies in Number Theory

We report on computer assisted proofs of three theorems from Number Theory, viz. Fermat’s Little Theorem, Euler’s generalization of Fermat’s statement and Wilson’s Theorem. Common to the formal proofs is that permutation of certain number lists has to be proved, which causes the main effort in the development. We give a short survey of the Open image in new window   system used in this experiment and illustrate the proofs before presenting them formally. We also discuss alternative solutions, report on the required effort and conclude with some experiences gained from this experiment.     

基于动态描述逻辑DDL的动作理论

基于一阶谓词逻辑或高阶逻辑的动作理论与采用命题语言的动作理论之间存在一个关于描述和推理能力的鸿沟;作为描述逻辑的动态扩展,动态描述逻辑DDL为基于描述逻辑的动作刻画和推理提供了一种途径.系统地研究了基于DDL的动作表示和推理问题.首先,在应用描述逻辑对静态领域知识进行刻画的基础上,引入带参数的原子动作定义式和带参数的复...     

An Efficient Approach to Solving Random k-sat Problems

Proving that a propositional formula is contradictory or unsatisfiable is a fundamental task in automated reasoning. This task is coNP-complete. Efficient algorithms are therefore needed when formulae are hard to solve. Random sat formulae provide a test-bed for algorithms because experiments that have become widely popular show clearly that these formulae are consistently difficult for any known algorithm. Moreover, the experiments show a critical value of the ratio of the number of clauses to the number of variables around which the formulae are the hardest on average. This critical value also corresponds to a ‘phase transition’ from solvability to unsolvability. The question of whether the formulae located around or above this critical value can efficiently be proved unsatisfiable on average (or even for a.e. formula) remains up to now one of the most challenging questions bearing on the design of new and more efficient algorithms. New insights into this question could indirectly benefit the solving of formulae coming from real-world problems, through a better understanding of some of the causes of problem hardness. In this paper we present a solving heuristic that we have developed, devoted essentially to proving the unsatisfiability of random sat formulae and inspired by recent work in statistical physics. Results of experiments with this heuristic and its evaluation in two recent sat competitions have shown a substantial jump in the efficiency of solving hard, unsatisfiable random sat formulae.     

Axiomatizing the Skew Boolean Propositional Calculus

The skew Boolean propositional calculus () is a generalization of the classical propositional calculus that arises naturally in the study of certain well-known deductive systems. In this article, we consider a candidate presentation of and prove it constitutes a Hilbert-style axiomatization. The problem reduces to establishing that the logic presented by the candidate axiomatization is algebraizable in the sense of Blok and Pigozzi. In turn, this process is equivalent to verifying four particular formulas are derivable from the candidate presentation. Automated deduction methods played a central role in proving these four theorems. In particular, our approach relied heavily on the method of proof sketches.