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)

Participants maneuvered a rat image through a circular region on the computer screen to find a hidden target platform, blending aspects of two well-known spatial tasks. Like the Morris water maze task, participants first experienced a series of learning trials before having to navigate to the hidden target platform from different locations and orientations. Like the dot-location task, they determined the location of a position within a two-dimensional circular region. This procedure provided a way to examine how the number of (...) surrounding cues (1, 2, or 3) affects the memory for spatial location in navigation. Memory performance was better when there were more cues and when targets were close to cues, consistent with the idea that cues bolster fine-grain memory, especially in proximal regions. Early and late measures of bias in memory reflected biases in a direction toward the nearest cue, implicating a cue-based category structure of the navigational space. Collectively, results suggest cue-based spatial memory representations that have been inferred from the dot-location task generalize to a navigation task within a simple, computer-based environment, as demonstrated by the good fits of the spatial model developed for the dot-location task (Fitting, Wedell, & Allen, 2005, 2007). (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.

As used by professional logicians today, is the name of their chosen subject singular or plural, "logic" or "logics"? This is a special case of a more general question. For instance, an algebraist might write a book entitled "Algebra", which is about algebras. Though many mathematicians are not aware of it, logic today most decidedly has its plural aspect. Indeed, it always did. Classical logic, which mathematicians often tend to identify with the entirety of logic, was in place roughly by (...) the beginning of the twentieth century. Since then a wide range of so-called non-classical logics have been developed. But indeed, before the creation of classical logic, there were multiple versions of logic, some of them more-or-less formalized. The current growing interest in medieval and ancient European and Asian logics has brought much of this back to modern awareness. Perhaps a later volume in this series will look at the history from a contemporary viewpoint. But that is not our task here. This is the second volume in a series called Landscapes in Logic. The intention of the series is to present reports illustrating the interplay between contemporary work in logic and mainstream mathematics. Of course this is both vague and overly ambitious, and must result in heterogeneous collections. The first volume in the series, Contemporary Logic and Computing, appeared in 2020. The contents divided plausibly into topics from contemporary logic, and from contemporary computing. The present volume is more diverse, and includes articles about both classical and non-classical logics, sometimes from the semantic side and sometimes from the proof-theoretic side. Some articles are primarily technical, often algebraic, while others are more philosophical in nature. Many fit into multiple categories. This multiplicity should not be seen as a defect. The papers here do not just explore logics house by house, but say something about their general neighborhoods as well. (shrink)

Generalized databases will be examined, in which attributes can be sets of attributes, or sets of sets of attributes, and other higher type constructs. A precise semantics will be developed for such databases, based on a higher type modal/intensional logic.

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)

We give a basic introduction to modal logic. This includes possible world semantics, axiom systems, and quantification. Ideas and formal machinery are discussed, but all proofs are omitted. Recommendations are given for those who want more.

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)

The logic S4LP combines the modal logic S4 with the justification logic LP, both axiomatically and semantically. We introduce a simple restriction on the behavior of constants in S4LP, having no effect on the LP sublogic. Under this restriction some powerful derived rules are established. Then these are used to show completeness relative to a semantics having what we call the local realizability property: at each world and for each formula true at that world there is a realization also true (...) at that world, where a realization is the result of replacing all modal operators with explicit justification terms. This is a part of a project to understand the deeper aspects of Artemov’s Realization Theorem. (shrink)

We present a logic programming language, which we call Proflog, with an operational semantics based on tableaus, and a denotational semantics based on supervaluations. We show the two agree. Negation is well-behaved, and semantic non-computability issues do not arise. This is accomplished essentially by dropping a domain closure requirement. The cost is that intuitions developed through the use of classical logic may need modification, though the system is still classical at a level once removed. Implementation problems are discussed very briefly (...) — the thrust of the paper is primarily theoretical. (shrink)

There is an error in the completeness proof for the {λ, =} part of FOIL-K. The error occurs in Section 4, in the text following the proof of Corollary 4.7, and concerns the definition of the interpretation I on relation symbols. Before this point in the paper, for each object variable v an equivalence class v has been defined, and for each intension variable f a function f has been defined. Then the following definition is given for a relation symbol (...) P : v1, v2, . . . , f1, f2, . . . ∈ I(P )(Γ) just in case there are w1, w2, . . . in d(Γ) with wi ∈ vi such that P (w1, w2, . . . , f1, f2, . . .) ∈ Γ. It was pointed out by Torben Brauner that we could have f1 and g1 being the same function, but also have P (w1, w2, . . . , f1, f2, . . .) ∈ Γ without having P (w1, w2, . . . , g1, f2, . . .) ∈ Γ. Our solution is to modify the definition of the model, rather artificially, so that if f and g are the same function, then f and g are syntactically the same intension variable. This is done as follows. First, arbitrarily choose some object variable w, and its corresponding equivalence class w. For each intension variable f we define a disambiguation world ˆ. (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.

We investigate the relationship between three-valued Kripke/Kleene semantics and stratified semantics for stratifiable logic programs. We first show these are compatible, in the sense that if the three-valued semantics assigns a classical truth value, the stratified approach will assign the same value. Next, the familiar fixed point semantics for pure Horn clause programs gives both smallest and biggest fixed points fundamental roles. We show how to extend this idea to the family of stratifiable logic programs, producing a semantics we call (...) weak stratified. Finally, we show weak stratified semantics coincides exactly with the three-valued approach on stratifiable programs, though the three-valued version is generally applicable, and does not require stratification assumptions. (shrink)

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)

This is a largely expository paper in which the following simple idea is pursued. Take the truth value of a formula to be the set of agents that accept the formula as true. This means we work with an arbitrary Boolean algebra as the truth value space. When this is properly formalized, complete modal tableau systems exist, and there are natural versions of bisimulations that behave well from an algebraic point of view. There remain significant problems concerning the proper formalization, (...) in this context, of natural language statements, particularly those involving negative knowledge and common knowledge. A case study is presented which brings these problems to the fore. None of the basic material presented here is new to this paper—all has appeared in several papers over many years, by the present author and by others. Much of the development in the literature is more general than here—we have confined things to the Boolean case for simplicity and clarity. Most proofs are omitted, but several of the examples are new. The main virtue of the present paper is its coherent presentation of a systematic point of view—identify the truth value of a formula with the set of those who say the formula is true. (shrink)

Preface of Festschrift on the occasion of Professor Rohit Parikh's 60th birthday.

A generalization of conventional Horn clause logic programming is proposed in which the space of truth values is a pseudo-Boolean or Heyting algebra, whose members may be thought of as evidences for propositions. A minimal model and an operational semantics is presented, and their equivalence is proved, thus generalizing the classic work of Van Emden and Kowalski.

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)

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)

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.

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.

This paper continues my work of [9], which showed there was a broad family of many valued logics that have a strict/tolerant counterpart. Here we consider a generalization of weak Kleene three valued logic, instead of the strong version that was background for that earlier work. We explain the intuition behind that generalization, then determine a subclass of strict/tolerant structures in which a generalization of weak Kleene logic produces the same results that the strong Kleene generalization did. This paper provides (...) much background, but is not self-contained. Some results from [9] are called on, and are not reproved here. [9] Melvin C. Fitting. “A Family of Strict/Tolerant Logics”. In: Journal of Philosophical Logic. Online. Print publication forthcoming. (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)

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.

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)

Consider those many-valued logic models in which the truth values are a lattice that supplies interpretations for the logical connectives of conjunction and disjunction, and which has a De Morgan involution supplying an interpretation for negation. Assume that the set of designated truth values is a prime filter in the lattice. Each of these structures determines a simple many-valued logic. We show that there is a single Smullyan-style signed tableau system appropriate for all of the logics these structures determine. Differences (...) between the logics are confined entirely to tableau branch closure rules. Completeness, soundness, and interpolation can be proved in a uniform way for all cases. Since branch closure rules have a limited number of variations, in fact all the semantic structures determine just four different logics, all well-known ones. Asymmetric logics such as strict/tolerant, ST, also share all the same tableau rules, but differ in what constitutes an initial tableau. It is also possible to capture the notion of antivalidity using the same set of tableau rules. Thus a simple set of tableau rules serves as a unifying and classifying device for a natural and simple family of many-valued logics. (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)

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.

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)