Bilattices, introduced by M. Ginsberg, constitute an elegant family of multiple-valued logics. Those meeting certain natural conditions have provided the basis for the semantics of a family of logic programming languages. Now we consider further restrictions on bilattices, to narrow things down to logic programming languages that can, at least in principle, be implemented. Appropriate bilattice background information is presented, so the paper is relatively self-contained.

The variety of semantical approaches that have been invented for logic programs is quite broad, drawing on classical and many-valued logic, lattice theory, game theory, and topology. One source of this richness is the inherent non-monotonicity of its negation, something that does not have close parallels with the machinery of other programming paradigms. Nonetheless, much of the work on logic programming semantics seems to exist side by side with similar work done for imperative and functional programming, with relatively minimal contact (...) between communities. In this paper we summarize one variety of approaches to the semantics of logic programs: that based on fixpoint theory. We do not attempt to cover much beyond this single area, which is already remarkably fruitful. We hope readers will see parallels with, and the divergences from the better known fixpoint treatments developed for other programming methodologies. (shrink)

Kleene’s well-known strong three-valued logic is shown to be one of a family of logics with similar mathematical properties. These logics are produced by an intuitively natural construction. The resulting logics have direct relationships with bilattices. In addition they possess mathematical features that lend themselves well to semantical constructions based on fixpoint procedures, as in logic programming.

A well-known problem with Hintikka-style logics of knowledge is that of logical omniscience. One knows too much. This breaks down into two subproblems: one knows all tautologies, and one’s knowledge is closed under consequence. A way of addressing the second of these is to move from knowledge simpliciter, to knowledge for a reason. Then, as consequences become ‘further away’ from one’s basic knowledge, reasons for them become more complex, thus providing a kind of resource measurement. One kind of reason is (...) a formal proof. Sergei Artemov has introduced a logic of explicit proofs, LP. I present a semantics for this, based on the idea that it is a logic of knowledge with explicit reasons. A number of fundamental facts about LP can be established using this semantics. But it is equally important to realize that it provides a natural logic of more general applicability than its original provenance, arithmetic provability. (shrink)

Classical first-order logic can be extended in two different ways to serve as a foundation for mathematics: introduce higher orders, type theory, or introduce sets. As it happens, both approaches have natural analogs for quantified modal logics, both approaches date from the 1960’s, one is not very well-known, and the other is well-known as something else. I will present the basic semantic ideas of both higher order intensional logic, and intensional set theory. Before doing so, I’ll quickly sketch some necessary (...) background material from quantified modal logic. Except for standard material concerning propositional modal logics, the paper is essentially self-contained. (shrink)

The family of all stable models for a logic program has a surprisingly simple overall structure, once two naturally occurring orderings are made explicit. In a so-called knowledge ordering based on degree of definedness, every logic program P has a smallest stable model, sk P — it is the well-founded model. There is also a dual largest stable model, S k P, which has not been considered before. There is another ordering based on degree of truth. Taking the meet and (...) the join, in the truth ordering, of the two extreme stable models sk P and S.. (shrink)

We present non-clausal resolution systems for propositional modal logics whose Kripke models do not involve symmetry, and for first order versions whose Kripke models do not involve constant domains. We give systems for K, T , K4 and S4; other logics are also possible. Our systems do not require preliminary reduction to a normal form and, in the first order case, intermingle resolution steps with Skolemization steps.

Kripke’s work on modal logic has been immensely influential. It hardly needs remarking that this is not his only work. Here we address his pioneering applications of fixpoint constructions to the theory of truth, and related work by others. In his fundamental paper on this he explicitly described a modal version, applying a fixpoint construction world by world within a modal frame. This can certainly be carried out, and doubtless has been somewhere. Others have suggested a variety of other extensions (...) such as using the unit interval as the underlying space of truth values, or using a four valued logic instead of three, or various combinations of these. When many similar formal constructions have been proposed, one naturally asks what is the common core. Is there some setting in which things can be proved once and for all, with the various specific proposals seen as applications of this common core. In fact this is the case, with bilattices providing the desired structure. Much of such a development has already appeared in some form or other. It is the purpose of this article to bring everything together, and also add a few things. We present general results that, more or less, have everything currently in the fixpoint literature as special cases. Fortunately this does not make things more complicated, since the underlying proofs are essentially the same as they have always been. It is just that they are being carried out in generality rather than in specificity. (shrink)

Among non-monotonic systems of reasoning, non-monotonic modal logics, and autoepistemic logic in particular, have had considerable success. The presence of explicit modal operators allows flexibility in the embedding of other approaches. Also several theoretical results of interest have been established concerning these logics. In this paper we introduce non-monotonic modal logics based on many-valued logics, rather than on classical logic. This extends earlier work of ours on many-valued modal logics. Intended applications are to situations involving several reasoners, not just one (...) as in the standard development. (shrink)

One can add the machinery of relation symbols and terms to a propositional modal logic without adding quantifiers. Ordinarily this is no extension beyond the propositional. But if terms are allowed to be non-rigid, a scoping mechanism (usually written using lambda abstraction) must also be introduced to avoid ambiguity. Since quantifiers are not present, this is not really a first-order logic, but it is not exactly propositional either. For propositional logics such as K, T and D, adding such machinery produces (...) a decidable logic, but adding it to S5 produces an undecidable one. Further, if an equality symbol is in the language, and interpreted by the equality relation, logics from K4 to S5 yield undecidable versions. (Thus transitivity is the villain here.) The proof of undecidability consists in showing that classical first-order logic can be embedded. (shrink)

A sequent calculus of a new sort is extracted from the Prolog program leanTAP. This calculus is sound and complete, even though it lacks almost all structural rules. Thinking of leanTAP as a sequent calculus provides a new perspective on it and, in some ways, makes it easier to understand. It is also easier to verify correctness and completeness of the Prolog implementation. In addition, it suggests extensions to other logics, some of which are considered here.

Justification logics are logics of knowledge in which explicit reasons are formally represented. Standard logics of knowledge have justification logic analogs. Connecting justification logics and logics of knowledge are Realization Theorems. In this paper we give a new, constructive proof of the Realization Theorem connecting S5 and its justification analog, JS5. This proof is, I believe, the simplest in the literature.

£ The existence of a model for a logic program is generally established by lattice-theoretic arguments. We present three examples to show that metric methods can often be used instead, generally in a direct, straightforward way. One example is a game program, which is not stratified or locally stratified, but which has a unique supported model whose existence is easily established using metric methods. The second example is a program without a unique supported model, but having a part that is (...) ‘well-behaved.’ The third example is a program in which one part depends on another, illustrating how modularity might be treated metrically. Finally we use ideas from this third example to prove a general result from [3]. The intention in presenting these examples and the theorem is to stimulate interest in.. (shrink)

An interpolation theorem holds for many standard modal logics, but first order $S5$ is a prominent example of a logic for which it fails. In this paper it is shown that a first order $S5$ interpolation theorem can be proved provided the logic is extended to contain propositional quantifiers. A proper statement of the result involves some subtleties, but this is the essence of it.

First we have individual variables, as usual in first-order logics. (We do not have individual constants, but this is a minor point.) The propositional logic LP has justification constants, but in FOLP these are generalized to allow individual variables as arguments. Thus we have as justification constants c, c(x), c(x, y), . . . . Similarly LP has justification variables, but in FOLP these can be parametrized with individual variables p, p(x), p(x, y), . . . . To keep terminology (...) in line with past papers, we will still refer to things as justification constants and justification variables, even though they have structure to them. As in LP, justification terms are built up from justification constants and justification variables using ·, +, ! as usual. In addition there is a new constructor, genx, introduced by Artemov, and there is one further new constructor, exsx, introduced in this paper. If t is a justification term and x is an individual variable, genxt and exsxt are justification terms. An individual variable x is free in a justification term unless it is bound by genx or exsx. More specifically, the free variables of p(x, y, . . .) and of c(x, y, . . .) are {x, y, . . .}, the free variables of s · t and of s + t are the free variables of s together with the free variables of t, the free variables of !s are the free variables of s, and the free variables of genxt and of exsxt are the free variables of t except for x. Formulas are built up from atomic formulas, including ⊥, in the way standard in first-order logic, together with the additional formation rule: t:X is a formula provided t is a justification term, X is a formula, and all free variables of X occur in t. We assume ⊃, ⊥, and ∀ are basic, with other connectives and quantifier defined. The axiomatization used here is a combination of an LP axiomatization and a standard axiomatization of first-order logic, together with a version of the Barcan formula, and one additional axiom that corresponds to the converse Barcan formula.. (shrink)

Suppose there are several experts, with some dominating others (expert A dominates expert B if B says something is true whenever A says it is). Suppose, further, that each of the experts has his or her own view of what is possible — in other words each of the experts has their own Kripke model in mind (subject, of course, to the dominance relation that may hold between experts). How will they assign truth values to sentences in a common modal (...) language, and on what sentences will they agree? This problem can be reformulated as one about many-valued Kripke models, allowing many-valued accessibility relations. This is a natural generalization of conventional Kripke models that has only recently been looked at. The equivalence between the many-valued version and the multiple expert one will be formally established. Finally we will axiomatize many-valued modal logics, and sketch a proof of completeness. (shrink)

In a forthcoming paper, Walter Carnielli and Abilio Rodrigues propose a Basic Logic of Evidence whose natural deduction rules are thought of as preserving evidence instead of truth. BLE turns out to be equivalent to Nelson’s paraconsistent logic N4, resulting from adding strong negation to Intuitionistic logic without Intuitionistic negation. The Carnielli/Rodrigues understanding of evidence is informal. Here we provide a formal alternative, using justification logic. First we introduce a modal logic, KX4, in which \ can be read as asserting (...) there is implicit evidence for X, where we understand evidence to permit contradictions. We show BLE embeds into KX4 in the same way that Intuitionistic logic embeds into S4. Then we formulate a new justification logic, JX4, in which the implicit evidence motivating KX4 is made explicit. KX4 embeds into JX4 via a realization theorem. Thus BLE has both implicit and explicit possibly contradictory evidence interpretations in a formal sense. (shrink)

First-order modal logic, in the usual formulations, is not suf- ficiently expressive, and as a consequence problems like Frege’s morning star/evening star puzzle arise. The introduction of predicate abstraction machinery provides a natural extension in which such difficulties can be addressed. But this machinery can also be thought of as part of a move to a full higher-order modal logic. In this paper we present a sketch of just such a higher-order modal logic: its formal semantics, and a proof procedure (...) using tableaus. Naturally the tableau rules are not complete, but they are with respect to a Henkinization of the “true” semantics. We demonstrate the use of the tableau rules by proving one of the theorems involved in G¨ odel’s ontological argument, one of the rare instances in the literature where higher-order modal constructs have appeared. A fuller treatment of the material presented here is in preparation. (shrink)

Modal logic is an enormous subject, and so any discussion of it must limit itself according to some set of principles. Modal logic is of interest to mathematicians, philosophers, linguists and computer scientists, for somewhat different reasons. Typically a philosopher may be interested in capturing some aspect of necessary truth, while a mathematician may be interested in characterizing a class of models having special structural features. For a computer scientist there is another criterion that is not as relevant for the (...) other disciplines: a logic should be ‘well-behaved.’ This is, admittedly, a vague notion, but some things are clear enough. A logic that can be axiomatized is better than one that can’t be; a logic with a simple axiomatization is better yet; and a logic with a reasonably implementable proof procedure is best of all. My current interests are largely centered in computer science, and so I will only discuss well-behaved modal logics. My talk is organized into three sections, depending on the expressiveness of the modal logics considered: propositional; first-order with rigid designators; first-order with non-rigid designators. Even limited as I have said, the subject is a big one, and this talk can be no more than an outline. For a general discussion of propositional modal logic see [2]; for this and first-order modal logic see [9], [10] and [8]; for tableau systems in modal logic see [6]. (shrink)

Most automated theorem provers have been built around some version of resolution [4]. But resolution is an inherently Classical logic technique. Attempts to extend the method to other logics have tended to obscure its simplicity. In this paper we present a resolution style theorem prover for Intuitionistic logic that, we believe, retains many of the attractive features of Classical resolution. It is, of course, more complicated, but the complications can be given intuitive motivation. We note that a small change in (...) the system as presented here causes it to collapse back to a Classical resolution system. We present the system in some detail for the propositional case, including soundness and completeness proofs. For the first order version we are sketchier. (shrink)

Strict/tolerant logic, ST, evaluates the premises and the consequences of its consequence relation differently, with the premises held to stricter standards while consequences are treated more tolerantly. More specifically, ST is a three-valued logic with left sides of sequents understood as if in Kleene’s Strong Three Valued Logic, and right sides as if in Priest’s Logic of Paradox. Surprisingly, this hybrid validates the same sequents that classical logic does. A version of this result has been extended to meta, metameta, … (...) consequence levels in Barrio et al.. In my earlier paper Fitting I showed that the original ideas behind ST are, in fact, much more general than first appeared, and an infinite family of many valued logics have Strict/Tolerant counterparts. This family includes both Kleene’s and Priest’s logic individually, as well as first degree entailment. For instance, for both the Kleene and the Priest logic, the corresponding strict/tolerant logic is six-valued, but with differing sets of strictly and tolerantly designated truth values. The present paper extends that generalization in two directions. We examine a reverse notion, of Tolerant/Strict logics, which exist for the same structures that were investigated in Fitting. And we show that the generalization extends through the meta, metameta, … consequence levels for the same infinite family of many valued logics. Finally we close with remarks on the status of cut and related rules, which can actually be rather nuanced. Throughout, the aim is not the philosophical applications of the Strict/Tolerant idea, but the determination of how general a phenomenon it is. (shrink)

Herbrand’s theorem is a central fact about classical logic, [9, 10]. It provides a constructive method for associating, with each first-order formula X, a sequence of formulas X1, X2, X3, . . . , so that X has a first-order proof if and only if some Xi is a tautology. Herbrand’s theorem serves as a constructive alternative to..

We continue a series of papers on a family of many-valued modal logics, a family whose Kripke semantics involves many-valued accessibility relations. Earlier papers in the series presented a motivation in terms of a multiple-expert semantics. They also proved completeness of sequent calculus formulations for the logics, formulations using a cut rule in an essential way. In this paper a novel cut-free tableau formulation is presented, and its completeness is proved.

One approach to the paradoxes of self-referential languages is to allow some sentences to lack a truth value (or to have more than one). Then assigning truth values where possible becomes a fixpoint construction and, following Kripke, this is usually carried out over a partially ordered family of three-valued truth-value assignments. Some years ago Matt Ginsberg introduced the notion of bilattice, with applications to artificial intelligence in mind. Bilattices generalize the structure Kripke used in a very natural way, while making (...) the mathematical machinery simpler and more perspicuous. In addition, work such as that of Yablo fits naturally into the bilattice setting. What I do here is present the general background of bilattices, discuss why they are natural, and show how fixpoint approaches to truth in languages that allow self-reference can be applied. This is not new work, but rather is a summary of research I have done over many years. (shrink)

In the tech report Artemov and Yavorskaya [4] an elegant formulation of the first-order logic of proofs was given, FOLP. This logic plays a fundamental role in providing an arithmetic semantics for first-order intuitionistic logic, as was shown. In particular, the tech report proved an arithmetic completeness theorem, and a realization theorem for FOLP. In this paper we provide a possible-world semantics for FOLP, based on the propositional semantics of Fitting [5]. We also give an Mkrtychev semantics. Motivation and intuition (...) for FOLP can be found in Artemov and Yavorskaya [4], and are not fully discussed here.This paper is dedicated to Sergei Artemov, an honored colleague and friend, who has made wonderful things for the rest of us to play with. (shrink)

Two things are done in this paper. First, a modal logic in which one can quantify over both objects and concepts is presented; a semantics and a tableau system are given. It is a natural modal logic, extending standard versions, and capable of addressing several well-known philosophical difficulties successfully. Second, this modal logic is used to introduce a rather different way of looking at relational databases. The idea is to treat records as possible worlds, record entries as objects, and attributes (...) as concepts, in the modal sense. This makes possible an intuitively satisfactory relational database theory. It can be extended, by the introduction of higher types, to deal with multiple-valued attributes and more complex things, though this is further than we take it here. (shrink)

First - order modal logic is very much under current development, with many different semantics proposed. The use of rigid objects goes back to Saul Kripke. More recently, several semantics based on counterparts have been examined, in a development that goes back to David Lewis. There is yet another line of research, using intensional objects, that traces back to Richard Montague. I have been involved with this line of development for some time. In the present paper, I briefly sketch several (...) of the approaches to first - order modal logic. Then I present one that I call FOIL in the Montague tradition that, I believe, is both expressive and natural. I briefly discuss in what sense it can be made to encompass the other approaches. Finally, I provide tableau rules to go with the FOIL semantics. (shrink)

LP can be seen as a logic of knowledge with justifications. See [S. Artemov, The logic of justification, The Review of Symbolic Logic 1 477–513] for a recent comprehensive survey of justification logics generally. Artemov’s Realization Theorem says justifications can be extracted from validities in the more conventional Hintikka-style logic of knowledge S4, in which they are not explicitly present. Justifications, however, are far from unique. There are many ways of realizing each theorem of S4 in the logic LP. If (...) the machinery of justifications is to be applied to artificial intelligence, or better yet, to everyday reasoning, we will need to work with whatever justifications we may have at hand—one version may not be interchangeable with another, even though they realize the same S4 formula. In this paper we begin the process of providing tools for reasoning about justifications directly. The tools are somewhat complex, but in retrospect this should not be surprising. Among other things, we provide machinery for combining two realizations of the same formula, and for replacing subformulas by equivalent subformulas. The results are algorithmic in nature—semantics for LP plays no role. We apply our results to provide a new algorithmic proof of Artemov’s Realization Theorem itself. This paper is a much extended version of [M.C. Fitting, Realizations and LP, in: S. Artemov, A. Nerode , Logical Foundations of Computer Science—New York ’07, in: Lecture Notes in Computer Science, vol. 4514, Springer-Verlag, 2007, pp. 212–223]. (shrink)

Bilattices, due to M. Ginsberg, are a family of truth value spaces that allow elegantly for missing or conflicting information. The simplest example is Belnap’s four-valued logic, based on classical two-valued logic. Among other examples are those based on finite many-valued logics, and on probabilistic valued logic. A fixed point semantics is developed for logic programming, allowing any bilattice as the space of truth values. The mathematics is little more complex than in the classical two-valued setting, but the result provides (...) a natural semantics for distributed logic programs, including those involving confidence factors. The classical two-valued and the Kripke/Kleene three-valued semantics become special cases, since the logics involved are natural sublogics of Belnap’s logic, the logic given by the simplest bilattice. (shrink)

Nested sequent systems for modal logics are a relatively recent development, within the general area known as deep reasoning. The idea of deep reasoning is to create systems within which one operates at lower levels in formulas than just those involving the main connective or operator. Prefixed tableaus go back to 1972, and are modal tableau systems with extra machinery to represent accessibility in a purely syntactic way. We show that modal nested sequents and prefixed modal tableaus are notational variants (...) of each other, roughly in the same way that tableaus and Gentzen sequent calculi are notational variants. This immediately gives rise to new modal nested sequent systems which may be of independent interest. We discuss some of these, including those for some justification logics that include standard modal operators. (shrink)

A new semantics is presented for the logic of proofs (LP), [1, 2], based on the intuition that it is a logic of explicit knowledge. This semantics is used to give new proofs of several basic results concerning LP. In particular, the realization of S4 into LP is established in a way that carefully examines and explicates the role of the + operator. Finally connections are made with the conventional approach, via soundness and completeness results.

Many powerful logics exist today for reasoning about multi-agent systems, but in most of these it is hard to reason about an infinite or indeterminate number of agents. Also the naming schemes used in the logics often lack expressiveness to name agents in an intuitive way.To obtain a more expressive language for multi-agent reasoning and a better naming scheme for agents, we introduce a family of logics called term-modal logics. A main feature of our logics is the use of modal (...) operators indexed by the terms of the logics. Thus, one can quantify over variables occurring in modal operators. In term-modal logics agents can be represented by terms, and knowledge of agents is expressed with formulas within the scope of modal operators. (shrink)

A propositional logic of explicit proofs, LP, was introduced in [S. Artemov, Explicit provability and constructive semantics, The Bulletin for Symbolic Logic 7 1–36], completing a project begun long ago by Gödel, [K. Gödel, Vortrag bei Zilsel, translated as Lecture at Zilsel’s in: S. Feferman , Kurt Gödel Collected Works III, 1938, pp. 62–113]. In fact, LP can be looked at in a more general way, as a logic of explicit evidence, and there have been several papers along these lines. (...) A major result about LP is the Realization Theorem, that says any theorem of S4 can be converted into a theorem of LP by some replacement of necessitation symbols with explicit proof terms. Thus the necessitation operator of S4 can be seen as a kind of implicit existential quantifier: there exists a proof term such that…. In this paper, quantification over evidence is introduced into LP, and it is shown that the connection between S4 necessitation and the existential quantifier becomes an explicit one. The extension of LP with quantifiers is called QLP. A semantics and an axiom system for QLP are given, soundness and completeness are established, and several results are proved relating QLP to LP and to S4. (shrink)

We introduce a subclass of Kripke's fixed points in which falsehood is the preferred truth value. In all of these the truthteller evaluates to false, while the liar evaluates to undefined (or overdefined). The mathematical structure of this family of fixed points is investigated and is shown to have many nice features. It is noted that a similar class of fixed points, preferring truth, can also be studied. The notion of intrinsic is shown to relativize to these two subclasses. The (...) mathematical ideas presented here originated in investigations of so-called stable models in the semantics of logic programming. (shrink)

Several justification logics have been created, starting with the logic LP, [1]. These can be thought of as explicit versions of modal logics, or of logics of knowledge or belief, in which the unanalyzed necessity (knowledge, belief) operator has been replaced with a family of explicit justification terms. We begin by sketching the basics of justification logics and their relations with modal logics. Then we move to new material. Modal logics come in various strengths. For their corresponding justification logics, differing (...) strength is reflected in different vocabularies. What we show here is that for justification logics corresponding to modal logics extending T, various familiar extensions are actually conservative with respect to each other. Our method of proof is very simple, and general enough to handle several justification logics not directly corresponding to distinct modal logics. Our methods do not, however, allow us to prove comparable results for justification logics corresponding to modal logics that do not extend T. That is, we are able to handle explicit logics of knowledge, but not explicit logics of belief. This remains open. (shrink)

This is a thorough treatment of first-order modal logic. The book covers such issues as quantification, equality (including a treatment of Frege's morning star/evening star puzzle), the notion of existence, non-rigid constants and function symbols, predicate abstraction, the distinction between nonexistence and nondesignation, and definite descriptions, borrowing from both Fregean and Russellian paradigms.

This book describes computability theory and provides an extensive treatment of data structures and program correctness. It makes accessible some of the author's work on generalized recursion theory, particularly the material on the logic programming language PROLOG, which is currently of great interest. Fitting considers the relation of PROLOG logic programming to the LISP type of language.