逻辑函数的双逻辑综合与优化

针对传统布尔逻辑在电路面积优化中存在的不足,提出了一种用传统布尔逻辑和Reed-Muller(RM)逻辑相结合的双逻辑优化算法.通过将原逻辑函数的乘积项转化为不相交乘积项,并利用不相交乘积项的位操作,将逻辑函数的覆盖分成2个部分,使之分别适合布尔逻辑综合和RM逻辑综合;同时提出了适合双逻辑函数的逻辑功能验证方法.双逻辑优化算法用C语言编程实现并用MCNC标准电路进行测试.实验结果表明,与单一的布尔逻辑综合结果相比,在绝大多数情况下文中算法可使电路面积获得进一步优化.     

超协调限制逻辑

本文给出了一阶超协调限制逻辑ＬＰｓ的定义，并证明了它与悖论逻辑（ＬＰ与ＬＰｍ）和限制逻辑（ＣＩＲＣ）的关系，ＬＰ作为一种非单调超协调逻辑具有非单逻辑和超协调逻辑的优点，而用能解决非单调逻辑和超协调逻辑存在的问题，它可作为在不完全与不协调知识下常识推理的形式化，因此它的知识表示中具有广泛的应用。     

概率逻辑、不确定逻辑和模糊逻辑之比较

通过一个实例分析比较了概率逻辑、主观概率逻辑、不确定逻辑和模糊逻辑的思想方法。提出了自己的观点：基于数据统计的概率逻辑是最科学的。不确定逻辑比主观概率逻辑更科学。当具有不确定性的原子命题具有独立性时,不确定逻辑和模糊逻辑的观点是一致的。而对于处理带有不确定性的相关性命题,不确定逻辑比模糊逻辑更科学。但是模糊逻辑在建立推理理论方面见长。     

一个二阶的context逻辑

本文为Ｂｕｖａｃ的ｃｏｎｔｅｘｔ逻辑定义了一个二阶扩充ＳＯＱＬＣ，它能为许多常识现象提供更简单自然的描述。     

基于泛逻辑的分形与混沌逻辑初探

人们对自然的看法正经历着一个根本性的改变,即转向多重性、暂时性和复杂性,混沌学与分形论则是研究此类非线性自然系统的新兴科学。本文分析了分形与混沌的基本特征及其与泛逻辑的相互关系,讨论了建立分形与混沌逻辑的必要性和可能性,并给出了分形逻辑的研究纲要和混沌逻辑的实现途径。文章指出:<1>.分形与混沌逻辑的产生既是人类对自然规律认识深入的必然产物,也是深入认识自然的客观需要;<2>.泛逻辑学原理为建立具体的逻辑体系提供了理论框架与生成规则,这使得建立分形与混沌逻辑成为可能;<3>.分形与混沌逻辑在复杂系统的研究中将扮演重要的角色,并在其应用中逐渐自我完善。     

线性逻辑和逻辑式程序设计

所谓的逻辑式程序设计它涉及两个逻辑层次：外部逻辑和内部逻辑，前者描述对象之间的逻辑关系，而后者涉及目标求解遵循的逻辑法则。如PROLOG，它的外部逻辑是古典逻辑，而其计算遵循的，我们将证明可以使用线性逻辑中的记法加以刻画。本文从从证明论角度出发，研究PROLOG目标求解成功或失败的公理性，并说明对任一给定的程序P，可定义一个线性理论LT（P），关于该理论，PROLOG目标求解是正确且完备的。     

人工智能中概率逻辑的研究

概率论是在不完备的、不确定的数据中进行推理的,它是度量不确定性的重要手段。在人工智能中,研究者结合概率和逻辑各自的优点,进行概率逻辑的研究。本文介绍了传统概率逻辑的三大派别,阐述了二值逻辑概率和三值逻辑概率的发展;最后介绍了泛逻辑,通过对概率逻辑和泛逻辑学的研究,将概率逻辑纳入泛逻辑学的框架内。     

人工智能中概率逻辑的研究

概率论是在不完备的、不确定的数据中进行推理的,它是度量不确定性的重要手段。在人工智能中,研究者结合概率和逻辑各自的优点,进行概率逻辑的研究。本文介绍了传统概率逻辑的三大派别,阐述了二值逻辑概率和三值逻辑概率的发展;最后介绍了泛逻辑,通过对概率逻辑和泛逻辑学的研究,将概率逻辑纳入泛逻辑学的框架内。     

基于四值语义的缺省逻辑

基于公式变换,给出一组缺省理论的变换方法,将命题语言L中的缺省理论变换到对应的命题语言L^-＋中,保证了所得到的缺省理论的所有扩张均不平凡,并通过一种弱变换可同时保证缺省扩张的存在性．为缺省理论定义了各种四值模型,使得缺省逻辑具有非单调超协调推理能力,并证明了L^-＋中的缺省扩张与L中缺省理论的四值模型之间具有一一对应关系．四值模型描述了公式变换的语义,基于四值语义的缺省推理通过缺省理论的变换技术能在标准的缺省逻辑中实现．     

Automated Inference of Finite Unsatisfiability

We present Infinox, an automated tool for analyzing first-order logic problems, aimed at showing finite unsatisfiability, i.e., the absence of models with finite domains. Finite satisfiability is not a decidable problem (only semi-decidable), which means that such a tool can never be complete. Nonetheless, our hope is that Infinox be a useful complement to finite model finders in practice. Infinox uses several different proof techniques for showing infinity of a set, each of which requires the identification of a function or a relation with particular properties. Infinox enumerates candidates to such functions and relations, and subsequently uses an automated theorem prover as a sub-procedure to try to prove the resulting proof obligations. We have evaluated Infinox on the relevant problems from the TPTP benchmark suite, and we are able to automatically show finite unsatisfiability for over 25% of these problems.     

Representing model theory in a type-theoretical logical framework

In a broad sense, logic is the field of formal languages for knowledge and truth that have a formal semantics. It tends to be difficult to give a narrower definition because very different kinds of logics exist. One of the most fundamental contrasts is between the different methods of assigning semantics. Here two classes can be distinguished: model theoretical semantics based on a foundation of mathematics such as set theory, and proof theoretical semantics based on an inference system possibly formulated within a type theory.Logical frameworks have been developed to cope with the variety of available logics unifying the underlying ontological notions and providing a meta-theory to reason abstractly about logics. While these have been very successful, they have so far focused on either model or proof theoretical semantics. We contribute to a unified framework by showing how the type/proof theoretical Edinburgh Logical Framework (LF) can be applied to the representation of model theoretical logics.We give a comprehensive formal representation of first-order logic, covering both its proof and its model theoretical semantics as well as its soundness in LF. For the model theory, we have to represent the mathematical foundation itself in LF, and we provide two solutions for that. Firstly, we give a meta-language that is strong enough to represent the model theory while being simple enough to be treated as a fragment of untyped set theory. Secondly, we represent Zermelo-Fraenkel set theory and show how it subsumes our meta-language. Specific models are represented as LF morphisms.All representations are given in and mechanically verified by the Twelf implementation of LF. Moreover, we use the Twelf module system to treat all connectives and quantifiers independently. Thus, individual connectives are available for reuse when representing other logics, and we obtain the first version of a feature library from which logics can be pieced together.Our results and methods are not restricted to first-order logic and scale to a wide variety of logical systems, thus demonstrating the feasibility of comprehensively formalizing large scale representation theorems in a logical framework.     

Deforestation, program transformation, and cut-elimination

The problem of proving that two programs, in any reasonable programming language, are equivalent is well-known to be undecidable. In a formal programming system, in which the rules for equivalence are finitely presented, the problem of provable equivalence is semi-decidable. Despite this improved situation there is a significant lack of generally accepted automated techniques for systematically searching for a proof (or disproof) of program equivalence. Techniques for searching for proofs of equivalence often stumble on the formulation of induction and, of course, coinduction (when it is present) which are often formulated in such a manner as to require inspired guesses.There are, however, well-known program transformation techniques which do address these issues. Of particular interest to this paper are the deforestation techniques introduced by Phil Wadler and the fold/unfold program transformation techniques introduced by Burstall and Darlington. These techniques are shadows of an underlying cut-elimination procedure and, as such, should be more generally recognized as proof techniques.In this paper we show that these techniques apply to languages which have both inductive and coinductive datatypes. The relationship between these program transformation techniques and cut-elimination requires a transformation from initial and final “algebra” proof rules into “circular” proof rules as introduced by Santocanale (and used implicitly in the model checking community). This transformation is only possible in certain proof systems. Here we show that it can be applied to cartesian closed categories with datatypes: closedness is an essential requirement. The cut-elimination theorems and attendant program transformation techniques presented here rely heavily on this alternate presentation of induction and coinduction.     

Hilbert's Twenty-Fourth Problem

For almost a century, a treasure lay hidden in a library in Germany, hidden until a remarkable discovery was made. Indeed, for most of the twentieth century, all of science thought that Hilbert had posed twenty-three problems, and no others. In the mid-1990s, however, as a result of a thorough reading of Hilbert's files, a twenty-fourth problem was found (in a notebook, in file Cod. ms. D. Hilbert 600:3), a problem that might have a profound effect on research. This newly discovered problem focuses on the finding of simpler proofs and criteria for measuring simplicity. A proof may be simpler than previously known in one or more ways that include length, size (measured in terms of the total symbol count), and term structure. A simpler proof not only is more appealing aesthetically (and has fascinated masters of logic including C. A. Meredith, A. Prior, and I. Thomas) but is relevant to practical applications such as circuit design and program synthesis. This article presents Hilbert's twenty-fourth problem, discusses its relation to certain studies in automated reasoning, and offers researchers with varying interests the challenge of addressing this newly discovered problem. In particular, we include open questions to be attacked, questions that (in different ways and with diverse proof refinements as the focus) may prove of substantial interest to mathematicians, to logicians, and (perhaps in a slightly different manner) to those researchers primarily concerned with automated reasoning.     

The Strategy of Cramming

Offered in this article is a new strategy, cramming, that can serve well in an attempt to answer an open question or in an attempt to find a shorter proof. Indeed, when the question can be answered by proving a conjunction, cramming can provide substantial assistance. The basis of the strategy rests with forcing so many steps of a subproof into the remainder of the proof that the desired answer is obtained. As for reduction in proof length, the literature shows that proof shortening (proof abridgment) was indeed of interest to some of the masters of logic, masters that include C. A. Meredith, A. Prior, and I. Thomas. The problem of proof shortening (as well as other aspects of simplification) is also central to the recent discovery by R. Thiele of Hilbert's twenty-fourth problem. Although that problem was not included in his 1900 Paris lecture (because he had not yet sufficiently formulated it), Hilbert stressed at various times in his life the importance of finding simpler proofs. Because a sharp reduction in proof length (of constructive proofs) is correlated with a significant reduction in the complexity of the object being constructed, the cramming strategy is relevant to circuit design and program synthesis. The most impressive success with the use of the cramming strategy concerns an abridgment of the Meredith–Prior abridging of the ukasiewicz proof for his shortest single axiom for the implicational fragment of two-valued sentential (or classical propositional) calculus. In the context of answering open questions, the most satisfying examples to date concern the study of the right-group calculus and the study of the modal logic C5. Various challenges are offered here.     

Comparing verification systems: interactive consistency in ACL2

Achieving interactive consistency among processors in the presence of faults is an important problem in fault tolerant computing, first cleanly formulated by L. Lamport, R. Pease, and M. Shostak (1980; 1982) and solved in selected cases with their Oral Messages (OM) algorithm. Several machine supported verifications of this algorithm have been presented, including a particularly elegant formulation and proof by John Rushby using EHDM and PVS (S. Owre et al., 1992, 1995; J. Rushby, 1992). Rushby proposes interactive consistency as a benchmark problem for specification and verification systems. We present a formalization of the OM algorithm in the ACL2 logic and compare our formalization and proof to his. We draw some conclusions concerning the range of desirable features for verification systems. In particular, while higher order functions, strong typing, lambda abstraction, and full quantification have some value they come with a cost; moreover, many uses of such features can be easily translated into simpler logical constructs, which facilitate more automated proof discovery. We offer a cautionary note about comparing systems with respect to a small set of problems in a limited domain     

Soundness and Completeness Proofs by Coinductive Methods

We show how codatatypes can be employed to produce compact, high-level proofs of key results in logic: the soundness and completeness of proof systems for variations of first-order logic. For the classical completeness result, we first establish an abstract property of possibly infinite derivation trees. The abstract proof can be instantiated for a wide range of Gentzen and tableau systems for various flavors of first-order logic. Soundness becomes interesting as soon as one allows infinite proofs of first-order formulas. This forms the subject of several cyclic proof systems for first-order logic augmented with inductive predicate definitions studied in the literature. All the discussed results are formalized using Isabelle/HOL’s recently introduced support for codatatypes and corecursion. The development illustrates some unique features of Isabelle/HOL’s new coinductive specification language such as nesting through non-free types and mixed recursion–corecursion.     

The ILTP Problem Library for Intuitionistic Logic

The Intuitionistic Logic Theorem Proving (ILTP) library provides a platform for testing and benchmarking automated theorem proving (ATP) systems for intuitionistic propositional and first-order logic. It includes about 2,800 problems in a standardized syntax from 24 problem domains. For each problem an intuitionistic status and difficulty rating were obtained by running comprehensive tests of currently available intuitionistic ATP systems on all problems in the library. Thus, for the first time, the testing and evaluation of ATP systems for intuitionistic logic have been put on a firm basis.     

Integrating predicate transition nets with first order temporal logic in the specification and verification of concurrent systems

This paper presents some results of integrating predicate transition nets with first order temporal logic in the specification and verification of concurrent systems. The intention of this research is to use predicate transition nets as a specification method and to use first order temporal logic as a verification method so that their strengths — the easy comprehension of predicate transition nets and the reasoning power of first order temporal logic can be combined. In this paper, a theoretical relationship between the computation models of these two formalisms is presented; an algorithm for systematically translating a predicate transition net into a corresponding temporal logic system is outlined; and a special temporal refutation proof technique is proposed and illustrated in verifying various concurrent properties of the predicate transition net specification of the five dining philosophers problem.     

A Framework for Proof Systems

Linear logic can be used as a meta-logic to specify a range of object-level proof systems. In particular, we show that by providing different polarizations within a focused proof system for linear logic, one can account for natural deduction (normal and non-normal), sequent proofs (with and without cut), and tableaux proofs. Armed with just a few, simple variations to the linear logic encodings, more proof systems can be accommodated, including proof system using generalized elimination and generalized introduction rules. In general, most of these proof systems are developed for both classical and intuitionistic logics. By using simple results about linear logic, we can also give simple and modular proofs of the soundness and relative completeness of all the proof systems we consider.