Computations in fragments of intuitionistic propositional logic

This article is a report on research in progress into the structure of finite diagrams of intuitionistic propositional logic with the aid of automated reasoning systems for larger calculations. Afragment of a propositional logic is the set of formulae built up from a finite number of propositional variables by means of a number of connectives of the logic, among which possibly non-standard ones like ¬¬ or which are studied here. Thediagram of that fragment is the set of equivalence classes of its formulae partially ordered by the derivability relation. N.G. de Bruijn's concept of exact model has been used to construct subdiagrams of the [p, q, , , ¬]-fragment.     

Fast decision procedure for propositional Dummett logic based on a multiple premise tableau calculus

We present a procedure to decide propositional Dummett logic. Such a procedure relies on a tableau calculus with a multiple premise rule and optimizations. The resulting implementation outperforms the state of the art graph-based procedure.     

Condensed detachment is complete for relevance logic: A computer-aided proof

The condensed detachment ruleD is a combination of modus ponens with a minimal amount of substitution. EarlierD has been shown to be complete for intuitionistic and classical implicational logic but incomplete forBCK andBCI logic. We show thatD is complete for the relevance logic. One of the main steps is the proof of the formula ((a a) a) a found in interaction with our resolution theorem prover. Various strategies of generating consequences of the axioms and choosing best ones for the next iteration were tried until the proof was found.     

Substitutions into propositional tautologies

We prove that there is a polynomial time substitution (y₁,…,yn):=g(x₁,…,xk) with k?n such that whenever the substitution instance A(g(x₁,…,xk)) of a 3DNF formula A(y₁,…,yn) has a short resolution proof it follows that A(y₁,…,yn) is a tautology. The qualification “short” depends on the parameters k and n.     

Sequent calculi and decidability for intuitionistic hybrid logic

In this paper we study the proof theory of the first constructive version of hybrid logic called Intuitionistic Hybrid Logic (IHL) in order to prove its decidability. In this perspective we propose a sequent-style natural deduction system and then the first sequent calculus for this logic. We prove its main properties like soundness, completeness and also the cut-elimination property. Finally we provide, from our calculus, the first decision procedure for IHL and then prove its decidability.     

A decision procedure for combinations of propositional temporal logic and other specialized theories

We present a decision procedure for formulae of discrete linear time propositional temporal logic whose propositional part may include assertions in a specialized theory. The combined decision procedure may be viewed as an extension of known decision procedures for quantifier-free theories to theories including temporal logic connectives. A combined decision procedure given by Pratt restricted to linear time temporal logic, runs in polynomial space relative to an oracle for the underlying theory. Our procedure differs from this one in that it can handle assertions containing arbitrary mixtures of global variables, whose values cannot change with time, and state variables, whose values can change with time. This new procedure can also handle assertions containing functions and predicates whose interpretations do not change with time. However, it requires the computation of least and greatest fixed points and has a worse asymptotic running time than that of Pratt. This new procedure has been implemented and seems efficient enough to be practical on simple formulae, although an upper bound derived for the worst case running time is triple exponential in the length of the formula. The techniques used appear to apply to logics other than temporal logic which have decision procedures based on tableaux. Most of this work was done while the author was at SRI International, Menlo Park, California, and at the University of Illinois, Urbana, Illinois, U.S.A. This work was partially supported by the National Science Foundation under grants MCS 81-09831 and MCS 83-07755.     

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.     

Accelerating tableaux proofs using compact representations

In this article a modified form of tableau calculus, calledTableau Graph Calculus, is presented for overcoming the well-known inefficiencies of the traditional tableau calculus to a large extent. This calculus is based on a compact representation of analytic tableaux by using graph structures calledtableau graphs. These graphs are obtained from the input formula in linear time and incorporate most of the rule applications of normal tableau calculus during the conversion process. The size of this representation is linear with respect to the length of the input formula and the graph closely resembles the proof tree of tableau calculi thus retaining the naturalness of the proof procedure. As a result of this preprocessing step, tableau graph calculus has only a single rule which is repeatedly applied to obtain a proof. Many optimizations for the applications of this rule, to effectively prune the search space, are presented as well. Brief details of an implemented prover called FAUST, embedded within the higher-order theorem prover called HOL, are also given. Applications of FAUST within a hardware verification context are also sketched.This work has been partly financed by german national grant under the project Automated System Design, SFB No. 358.     

Set theory in first-order logic: Clauses for Gödel's axioms

In this paper we present a set of clauses for set theory, thus developing a foundation for the expression of most theorems of mathematics in a form acceptable to a resolution-based automated theoren prover. Because Gödel's formulation of set theory permits presentation in a finite number of first-orde formulas, we employ it rather than that of Zermelo-Fraenkel. We illustrate the expressive power of thi formulation by providing statements of some well-known open questions in number theory, and give some intuition about how the axioms are used by including some sample proofs. A small set of challeng problems is also given.     

The HOL logic extended with quantification over type variables

The HOL system is an LCF-style mechanized proof assistant for conducting proofs in higher-order logic. This paper discusses a proposal to extend the primitive basis of the logic underlying the HOL system with a very simple form of quantification over types. It is shown how certain practical problems with using the definitional mechanisms of HOL would be solved by the additional expressive power gained by making this extension.     

Proof strategies in linear logic

Linear logic, introduced by J.-Y. Girard, is a refinement of classical logic providing means for controlling the allocation of resources. It has aroused considerable interest from both proof theorists and computer scientists. In this paper we investigate methods for automated theorem proving in propositional linear logic. Both the bottom-up (tableaux) and top-down (resolution) proof strategies are analyzed. Various modifications of sequent rules and efficient search strategies are presented along with the experiments performed with the implemented theorem provers.     

A new reduction rule for the connection graph proof procedure

A new reduction rule is introduced for the connection graph proof procedure proposed by Kowalski in 1975. The new rule considers sets of values which clause variables may take. Application of the rule often leads to massive removals of links. A proof system in which the new rule is included has successfully been implemented in PROLOG. The performance of this system is compared to other resolution based proof systems. Also, the new rule is related to order-sorted logic.     

Intuitionistic hybrid logic: Introduction and survey

Intuitionistic hybrid logic is hybrid modal logic over an intuitionistic logic basis instead of a classical logical basis. In this short paper we introduce intuitionistic hybrid logic and we give a survey of work in the area.     

Filter-based resolution principle for lattice-valued propositional logic LP(X)

As one of most powerful approaches in automated reasoning, resolution principle has been introduced to non-classical logics, such as many-valued logic. However, most of the existing works are limited to the chain-type truth-value fields. Lattice-valued logic is a kind of important non-classical logic, which can be applied to describe and handle incomparability by the incomparable elements in its truth-value field. In this paper, a filter-based resolution principle for the lattice-valued propositional logic LP(X) based on lattice implication algebra is presented, where filter of the truth-value field being a lattice implication algebra is taken as the criterion for measuring the satisfiability of a lattice-valued logical formula. The notions and properties of lattice implication algebra, filter of lattice implication algebra, and the lattice-valued propositional logic LP(X) are given firstly. The definitions and structures of two kinds of lattice-valued logical formulae, i.e., the simple generalized clauses and complex generalized clauses, are presented then. Finally, the filter-based resolution principle is given and after that the soundness theorem and weak completeness theorems for the presented approach are proved.     

Some properties of fuzzy reasoning in propositional fuzzy logic systems

In order to analyze the logical foundation of fuzzy reasoning, this paper first introduces the concept of generalized roots of theories in ?ukasiewicz propositional fuzzy logic ?uk, Gödel propositional fuzzy logic Göd, Product propositional fuzzy logic Π, and nilpotent minimum logic NM (the R₀-propositional fuzzy logic L^∗). Next, it is proved that all consequences of a theory Γ, named D(Γ), are completely determined by its generalized root whenever Γ has a generalized root. Moreover, it is proved that every finite theory Γ has a generalized root, which can be expressed by a specific formula. Finally, we demonstrate the existence of a non-fuzzy version of Fuzzy Modus Ponens (FMP) in ?uk, Göd, Π and NM (L^∗), and we provide its numerical version as a new algorithm for solving FMP.     

A model for failure mode and effects analysis based on intuitionistic fuzzy approach

Failure mode and effects analysis (FMEA) is one of the most powerful methods in the field of risk management and has been widely used for improving process reliability in manufacturing and service sector. High applicability of FMEA has contributed to its applications in many research domains and practical fields pertaining risk assessment and system safety enhancement. However, the method has also been criticized by experts due to several weaknesses and limitations. The current study proposed a novel model for failure mode and effects analysis based on intuitionistic fuzzy approach. This approach offers some advantages over earlier models as it accounts for degrees of uncertainty in relationships among various criteria or options, specifically when relations cannot be expressed in definite numbers. The proposed model provides a tool to evaluate the failure modes, while dealing with vague concepts and insufficient data. The proposed model was tested in a case study examining the failure modes for quality of internet banking services.     

Reference and perspective in intuitionistic logics

What an intuitionist may refer to with respect to a given epistemic state depends not only on that epistemic state itself but on whether it is viewed concurrently from within, in the hindsight of some later state, or ideally from a standpoint “beyond” all epistemic states (though the latter perspective is no longer strictly intuitionistic). Each of these three perspectives has a different—and, in the last two cases, a novel—logic and semantics. This paper explains these logics and their semantics and provides soundness and completeness proofs. It provides, moreover, a critique of some common versions of Kripke semantics for intuitionistic logic and suggests ways of modifying them to take account of the perspective-relativity of reference.     

■ukasiewicz命题逻辑系统中有限命题集的约简理论

在n值■ukasiewicz命题逻辑中提出了命题集Γ的约简理论,引入由命题集Γ所诱导的形式背景的概念,从Γ及其子集的关系出发给出了n值命题逻辑中有限命题集Γ约简的判定定理以及求Γ约简的方法。说明了无穷值■ukasiewicz命题逻辑中命题集Γ的约简可转化为n值情形。