Theorem Prover for Intuitionistic Logic Based on the Inverse Method

The first-order intuitionistic logic is a formal theory from the family of constructive logics. In intuitionistic logic, it is possible to extract a particular example x = a and a proof of a formula P(a) from a proof of a formula ?xP(x). Owing to this feature, intuitionistic logic has many applications in mathematics and computer science. Many modern proof assistants include automated tactics for the first-order intuitionistic logic, which simplify the task of solving challenging problems, such as formal verification of software, hardware, and protocols. In this paper, a new theorem prover (called WhaleProver) for full first-order intuitionistic logic is presented. Testing on the ILTP benchmarking library has shown that WhaleProver performance is comparable with the state-of-the-art intuitionistic provers. Our prover has solved more than 800 problems from the ILTP version 1.1.2. Some of them are intractable for other provers. WhaleProver is based on the inverse method proposed by S.Yu. Maslov. We introduce an intuitionistic inverse method calculus which is, in turn, a special kind of sequent calculus. It is also described how to adopt for this calculus several existing proof search strategies proposed for different logical calculi by S.Yu. Maslov, V.P. Orevkov, A.A. Voronkov, and others. In addition, a new proof search strategy is proposed that allows one to avoid redundant inferences. The paper includes results of experiments with WhaleProver on the ILTP library. We believe that Whale- Prover can be used as a test bench for different inference procedures and strategies, as well as for educational purposes.     

Axioms for classical, intuitionistic, and paraconsistent hybrid logic

In this paper we give axiom systems for classical and intuitionistic hybrid logic. Our axiom systems can be extended with additional rules corresponding to conditions on the accessibility relation expressed by so-called geometric theories. In the classical case other axiomatisations than ours can be found in the literature but in the intuitionistic case no axiomatisations have been published. We consider plain intuitionistic hybrid logic as well as a hybridized version of the constructive and paraconsistent logic N4.     

Complexity of some problems in positive and related calculi

A problem of recognizing important properties of propositional calculi is considered, and complexity bounds for some decidable properties are found. For a given logical system L, a property P of logical calculi is called decidable over L if there is an algorithm which for any finite set Ax of new axiom schemes decides whether the calculus L+Ax has the property P or not. In Maksimova and Voronkov (Bull. Symbol. Logic 6 (2000) 118) the complexity of tabularity, pretabularity, and interpolation problems over the intuitionistic logic (Int) and over modal logic S4 was studied.In the present paper, positive and positively axiomatizable calculi are investigated. We prove NP-completeness of tabularity, DP-hardness of pretabularity and PSPACE-completeness of interpolation and projective Beth's property over the positive fragment Int⁺ of the intuitionistic logic. Some complexity bounds for properties of propositional calculi over the intuitionistic or the minimal logic are found.     

Proof-Search in Intuitionistic Logic with Equality, or Back to Simultaneous Rigid E-Unification

We characterize provability in intuitionistic logic with equality in terms of a constraint calculus. This characterization uncovers close connections between provability in intuitionistic logic with equality and solutions to simultaneous rigid E-unification. We show that the problem of existence of a sequent proof with a given skeleton is polynomial-time equivalent to simultaneous rigid E-unifiability. This gives us a proof procedure for intuitionistic logic with equality modulo simultaneous rigid E-unification. We also show that simultaneous rigid E-unifiability is polynomial-time reducible to intuitionistic logic with equality. Thus, any proof procedure for intuitionistic logic with equality can be considered as a procedure for simultaneous rigid E-unifiability. In turn, any procedure for simultaneous rigid E-unifiability gives a procedure for establishing provability in intuitionistic logic with equality.     

Proof Search in Intuitionistic Logic with Equality, or Back to Simultaneous Rigid E-Unification

We characterize provability in intuitionistic logic with equality in terms of a constraint calculus. This characterization uncovers close connections between provability in intuitionistic logic with equality and solutions to simultaneous rigid E-unification. We show that the problem of existence of a sequent proof with a given skeleton is polynomial-time equivalent to simultaneous rigid E-unifiability. This gives us a proof procedure for intuitionistic logic with equality modulo simultaneous rigid E-unification. We also show that simultaneous rigid E-unifiability is polynomial-time reducible to intuitionistic logic with equality. Thus, any proof procedure for intuitionistic logic with equality can be considered as a procedure for simultaneous rigid E-unifiability. In turn, any procedure for simultaneous rigid E-unifiability gives a procedure for establishing provability in intuitionistic logic with equality.     

Uniform provability realization of intuitionistic logic, modality and λ-terms

The intended meaning of intuitionistic logic is explained by the Brouwer-Heyting-Kolmogorov (BHK) provability semantics which informally defines intuitionistic truth as provability and specifies the intuitionistic connectives via operations on proofs. The problem of finding an adequate formalization of the provability semantics and establishing the completeness of the intuitionistic logic Int was first raised by Gödel in 1933. This question turned out to be a part of the more general problem of the intended realization for Gödel's modal logic of provability S4 which was open since 1933. In this tutorial talk we present a provability realization of Int and S4 that solves both of these problems. We describe the logic of explicit provability (LP) with the atoms “t is a proof of F” and establish that every theorem of S4 admits a reading in LP as the statement about operations on proofs. Moreover, both S4 and Int are shown to be complete with respect to this realization. In addition, LP subsumes the λ-calculus, modal λ-calculus, combinatory logic and provides a uniform provability realization of modality and λ-terms.     

Focusing and polarization in linear,intuitionistic, and classical logics

A focused proof system provides a normal form to cut-free proofs in which the application of invertible and non-invertible inference rules is structured. Within linear logic, the focused proof system of Andreoli provides an elegant and comprehensive normal form for cut-free proofs. Within intuitionistic and classical logics, there are various different proof systems in the literature that exhibit focusing behavior. These focused proof systems have been applied to both the proof search and the proof normalization approaches to computation. We present a new, focused proof system for intuitionistic logic, called LJF, and show how other intuitionistic proof systems can be mapped into the new system by inserting logical connectives that prematurely stop focusing. We also use LJF to design a focused proof system LKF for classical logic. Our approach to the design and analysis of these systems is based on the completeness of focusing in linear logic and on the notion of polarity that appears in Girard’s LC and LU proof systems.     

广义优势多粒度直觉模糊粗糙集及规则获取

优势关系粗糙集模型是研究序信息系统中数据挖掘的主要方法。为了丰富现有优势关系粗糙集模型,使其更加有效地应用于实际问题,本文首先在直觉模糊决策信息系统中利用三角模和三角余模定义了3种优势关系,得到了3种优势类;其次构造了广义优势关系多粒度直觉模糊粗糙集模型,讨论了该模型的主要性质;随后给出如何从直觉模糊决策信息系统中获取逻辑连接词为“或”的决策规则;最后通过实例说明该模型在处理直觉模糊决策序关系信息系统时是有效的。     

语言真值直觉模糊命题逻辑系统的推理规则

提出了一种基于语言真值直觉模糊代数的直觉模糊命题逻辑系统。基于语言真值格蕴涵代数生成语言真值直觉模糊代数,可同时处理具有可比性或不可比性信息。该方法可以同时处理不确定性问题的正面证据和反面证据。研究了语言真值直觉模糊命题逻辑系统LP(S)的性质,得到了其公理及推理规则,也获得了LP(S)中的证明与定理。实例说明,该方法在处理同时具有可比性和不可比性的直觉模糊决策问题中更灵活、更有效。     

直觉线性μ-演算

线性mu-演算(μTL)是线性时序逻辑(LTL)的不动点扩展.LTL是一个便于规范和论证反应式系统的方法.μTL作为比LTL表达能力更强的逻辑,用LTL表示的性质度可由μTL表示.类似于LTL的直觉线性时序逻辑(ILTL),提出一种基于直觉解释的μTL,称为直觉μTL(IμTL).确立了IμTL和ILTL的关系,比较了它们之间的表达能力.讨论了使用IμTL与安全性质和活性描述的关系以及描述"假设-保证"规范的问题.     

直觉模糊逻辑算子研究’

模糊逻辑算子是模糊信息融合、模糊推理及模糊决策的重要工具。针对作为模糊逻辑算子重要扩展的直觉模糊逻辑算子,首先引入了直觉模糊集在特殊格上的等价定义。其次,验证了直觉模糊t-模与s-模的若干重要性质。在此基础上,对两种常用的蕴涵算子：直觉模糊孓蕴涵与直觉模糊R-蕴涵所具有的新性质进行讨论和证明,从而便于直觉模糊逻辑算子的进一步应用。     

Optimization techniques for propositional intuitionistic logic and their implementation

This paper presents some techniques which bound the proof search space in propositional intuitionistic logic. These techniques are justified by Kripke semantics and are the backbone of a tableau based theorem prover (PITP) implemented in C++. PITP and some known theorem provers are compared using the formulas of ILTP benchmark library. It turns out that PITP is, at the moment, the propositional prover that solves most formulas of the library.     

六元语言值直觉模糊的金融决策推理方法

为了处理金融决策中的不确定性信息,采用直觉格值的方法来表达语言值。基于语言真值直觉格值系统,改进了一个个人金融决策辅助系统模型。该系统的推理方法是将直觉模糊逻辑近似推理方法进行扩展,通过使用相似度的方法来处理模糊问题,实现了一种较为理想的不确定性推理方法。最后给出了一个实例,结果表明所提出的方法可以灵活有效地处理金融决策问题。     

A linear ordering on the class of Trapezoidal intuitionistic fuzzy numbers

Fuzzy numbers and intuitionistic fuzzy numbers are introduced in the literature to model problems involving incomplete and imprecise information in expert and intelligent systems. Ranking of TrIFNs plays an important role in an information system (Decision Making) with imprecise and inadequate information and the complete ranking on the class of trapezoidal intuitionistic fuzzy number is an open problem worldwide. Researchers from all over the world have been working in ranking of intuitionistic fuzzy numbers since 1985, but till date there is no common methodology that ranks any two arbitrary intuitionistic fuzzy numbers due to the partial ordering of TraIFNs. Different algorithms are available in the literature for solving intuitionistic fuzzy decision (or information system) problem, but each and every algorithm failed to give better result in some places due to the ranking procedure of TrIFNs. Intuitionistic fuzzy decision algorithm works better when it have a complete ranking procedure that ranks arbitrary intuitionistic fuzzy numbers. In this paper a linear (total) ordering on the class of trapezoidal intuitionistic fuzzy numbers using axiomatic set of eight different scores is introduced. The main idea of this paper is to classify and study the properties of eight different sub classes of the set of TrIFNs. Further new total order relations are defined on each of the subclasses of TrIFNs and they are extended to a complete ranking procedure on the set of TrIFNs. Finally the significance of the proposed method over existing methods is studied by illustrative examples.     

Computable Kripke Models and Intermediate Logics

We introduce effectiveness considerations into model theory of intuitionistic logic. We investigate effectiveness of completeness (by Kripke) results for intermediate logics such as intuitionistic logic, classical logic, constant domain logic, directed frames logic, and Dummett's logic.     

直觉模糊逻辑的(α,β)-准锁语义归结方法*

为了提高直觉模糊命题逻辑的(α,β)-归结效率,将准锁语义归结策略应用于(α,β)-归结原理,得到直觉模糊命题逻辑的(α,β)-准锁语义归结方法,证明方法的可靠性与完备性.给出直觉模糊命题逻辑系统的(α,β)-准锁语义归结和(α,β)-准锁语义归结演绎的概念.讨论直觉模糊命题逻辑系统中的(α,β)-准锁语义归结式和锁子句的合并规则.最后,给出直觉模糊命题逻辑系统的基于(α,β)-准锁语义归结的自动推理算法步骤,并通过实例说明算法的有效性.     

直觉模糊集的模糊蕴含式运算方法

与经典模糊集相比,直觉模糊集具有更强的表达能力和灵活性.针对直觉模糊集的模糊推理,将经典的模糊集的模糊蕴含式拓展到直觉模糊集中,提出基于扩展二值逻辑的直觉模糊集下各种模糊蕴含式运算方法,通过实例验证直觉模糊集模糊蕴含式运算方法的有效性和正确性.     

On goal-directed provability in classical logic

One of the key features of logic programming is the notion of goal-directed provability. In intuitionistic logic, the notion of uniform proof has been used as a proof-theoretic characterization of this property. Whilst the connections between intuitionistic logic and computation are well known, there is no reason per se why a similar notion cannot be given in classical logic. In this paper we show that there are two notions of goal-directed proof in classical logic, both of which are suitably weaker than that for intuitionistic logic. We show the completeness of this class of proofs for certain fragments, which thus form logic programming languages. As there are more possible variations on the notion of goal-directed provability in classical logic, there is a greater diversity of classical logic programming languages than intuitionistic ones. In particular, we show how logic programs may contain disjunctions in this setting. This provides a proof-theoretic basis for disjunctive logic programs, as well as characterising the “disjunctive” nature of answer substitutions for such programs in terms of the provability properties of the classical connectives Λ and Λ.     

基于IFTL的不确定时间推理方法

针对现有时序逻辑对复杂不确定时间信息描述和推理方面的局限性,定义了直觉模糊不确定时间区间与时间间隔,构造了未知时刻的直觉模糊时序逻辑(IFTL)预测模型,提出了基于IFTL的不确定时间推理方法,较好地解决了时间推理精度不高的问题。同时,定义了直觉模糊集间的重叠度,并提出了基于此的知识模型及时间网络的一致性检验方法。最后通过典型实例验证了所提出的时间推理方法的有效性和优越性。     

Constructive logics Part I: A tutorial on proof systems and typed λ-calculi

The purpose of this paper is to give an exposition of material dealing with constructive logics, typed λ-calculi, and linear logic. The emergence in the past ten years of a coherent field of research often named “logic and computation” has had two major (and related) effects: firstly, it has rocked vigorously the world of mathematical logic; secondly, it has created a new computer science discipline, which spans a range of subjects from what is traditionally called the theory of computation, to programming language design. Remarkably, this new body of work relies heavily on some “old” concepts found in mathematical logic, like natural deduction, sequent calculus, and λ-calculus (but often viewed in a different light), and also on some newer concepts. Thus, it may be quite a challenge to become initiated to this new body of work (but the situation is improving, and there are now some excellent texts on this subject matter). This paper attempts to provide a coherent and hopefully “gentle” initiation to this new body of work. We have attempted to cover the basic material on natural deduction, sequent calculus, and typed λ-calculus, but also to provide an introduction to Girard's linear logic, one of the most exciting developments in logic these past six years. The first part of these notes gives an exposition of the background material (with some exceptions, such as “contraction-free” systems for intuitionistic propositional logic and the Girard translation of classical logic into intuitionistic logic, which is new). The second part is devoted to more current topics such as linear logic, proof nets, the geometry of interaction, and unified systems of logic (LU).