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.

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)

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.

Two families of many-valued modal logics are investigated. Semantically, one family is characterized using Kripke models that allow formulas to take values in a finite many-valued logic, at each possible world. The second family generalizes this to allow the accessibility relation between worlds also to be many-valued. Gentzen sequent calculi are given for both versions, and soundness and completeness are established.

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)

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)

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)

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)

Kleene’s strong three-valued logic extends naturally to a four-valued logic proposed by Belnap. We introduce a guard connective into Belnap’s logic and consider a few of its properties. Then we show that by using it four-valued analogs of Kleene’s weak three-valued logic, and the asymmetric logic of Lisp are also available. We propose an extension of these ideas to the family of distributive bilattices. Finally we show that for bilinear bilattices the extensions do not produce any new equivalences.

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)

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)

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 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)

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)

is used to give a formalization of Artemov’s knowledge based reasoning approach to game theory, (KBR), [ 4 , 5 ]. Epistemic states of players are represented explicitly and reasoned about formally. We give a detailed analysis of the Centipede game using both proof theoretic and semantic machinery. This helps make the case that PDL + E can be a useful basis for the logical investigation of game theory.

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)

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.

While Kripke's original paper on the theory of truth used a three-valued logic, we believe a four-valued version is more natural. Its use allows for possible inconsistencies in information about the world, yet contains Kripke's development within it. Moreover, using a four-valued logic makes it possible to work with complete lattices rather than complete semi-lattices, and thus the mathematics is somewhat simplified. But more strikingly, the four-valued version has a wide, natural generalization to the family of interlaced bilattices. Thus, with (...) little more work, the theory is extended to a broad class of settings. Indeed, a result like Theorem 6.2 would not even be possible to state without the interlaced bilattice machinery. We hope the notion of interlaced bilattice will make apparent further such connections. (shrink)

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)

This is an expository paper in which the basic ideas of a family of Justification Logics are presented. Justification Logics evolved from a logic called LP, introduced by Sergei Artemov [1, 3], which formed the central part of a project to provide an arithmetic semantics for propositional intuitionistic logic. The project was successful, but there was a considerable bonus: LP came to be understood as a logic of knowledge with explicit justifications and, as such, was capable of addressing in a (...) natural way long-standing problems of logical omniscience. Since then, LP has become one member of a family of related logics, all logics of knowledge with explicit knowledge terms. In this paper the original problem of intuitionistic foundations is discussed only briefly. We concentrate entirely on issues of reasoning about knowledge. (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)

There is an obvious difference between what a term designates and what it means. At least it is obvious that there is a difference. In some way, meaning determines designation, but is not synonymous with it. After all, “the morning star” and “the evening star” both designate the planet Venus, but don't have the same meaning. Intensional logic attempts to study both designation and meaning and investigate the relationships between them.

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)

Hybrid logics internalize their own semantics. Members of the newer family of justification logics internalize their own proof methodology. It is an appealing goal to combine these two ideas into a single system, and in this paper we make a start. We present a hybrid/justification version of the modal logic T. We give a semantics, a proof theory, and prove a completeness theorem. In addition, we prove a Realization Theorem, something that plays a central role for justification logics generally. Since (...) justification logics are newer and less well-known than hybrid logics, we sketch their background, and give pointers to their range of applicability. We conclude with suggestions for future research. Indeed, the main goal of this paper is to encourage others to continue the investigation begun here. (shrink)

£ 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.

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)

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.

A modal accessibility relation is just a transition relation, and so can be represented by a {0, 1} valued transition matrix. Starting from this observation, I first show that the machinery of matrices, over Boolean algebras more general than the two-valued one, is appropriate for investigating multi-modal semantics. Then I show that bisimulations have a rather elegant theory, when expressed in terms of transformations on Boolean vector spaces. The resulting theory is a curious hybrid, fitting between conventional modal semantics and (...) conventional linear algebra. I don’t know where the investigations begun here will ultimately wind up, but in the meantime the approach has a kind of curious charm that others may find appealing. (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)

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)

First-order modal logics, as traditionally formulated, are not expressive enough. It is this that is behind the difficulties in formulating a good analog of Herbrand’s Theorem, as well as the well-known problems with equality, non-rigid designators, definite descriptions, and nondesignating terms. We show how all these problems disappear when modal language is made more expressive in a simple, natural way. We present a semantic tableaux system for the enhanced logic, and (very) briefly discuss implementation issues.

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..

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)

odel-L¨ ob computability logic. In order to make things relatively self-contained, I sketch the essential ideas of GL, and discuss the significance of its fixpoint theorem. Then I give the algorithm embodied in the program in a little more detail. It should be emphasized that nothing new is presented here — all the theory and methodology are due to others. The main interest is, in a sense, psychological. The approach taken here has been declared in the literature, more than once, (...) to be of theoretical interest only, being too unwieldly in practice. Experimentation shows this is not so provided formulas are not too complicated. A copy of the program can be obtained by ftp from venus.gc.cuny.edu. It is in the subdirectory “/pub/fitting,” under the name “glfixpt.pro.” Log on as “anonymous” and use your full e-mail address as password. If there are difficulties with ftp, send e-mail to the author at mlflc@cunyvm.cuny.edu. The Prolog code is standard, and should run under any implementation, though minor modifications may be necessary for some systems. These modifications are described in the last section, and also in the program itself. (shrink)