The Refined Extension Principle for Semantics of Dynamic Logic Programming

Over recent years, various semantics have been proposed for dealing with updates in the setting of logic programs. The availability of different semantics naturally raises the question of which are most adequate to model updates. A systematic approach to face this question is to identify general principles against which such semantics could be evaluated. In this paper we motivate and introduce a new such principle the refined extension principle. Such principle is complied with by the stable model semantics for (single) logic programs. It turns out that none of the existing semantics for logic program updates, even though generalisations of the stable model semantics, comply with this principle. For this reason, we define a refinement of the dynamic stable model semantics for Dynamic Logic Programs that complies with the principle.     

Constructive Logic with Strong Negation is a Substructural Logic. II

The goal of this two-part series of papers is to show that constructive logic with strong negation N is definitionally equivalent to a certain axiomatic extension NFL _ew of the substructural logic FL _ew . The main result of Part I of this series [41] shows that the equivalent variety semantics of N (namely, the variety of Nelson algebras) and the equivalent variety semantics of NFL _ew (namely, a certain variety of FL _ew -algebras) are term equivalent. In this paper, the term equivalence result of Part I [41] is lifted to the setting of deductive systems to establish the definitional equivalence of the logics N and NFL _ew . It follows from the definitional equivalence of these systems that constructive logic with strong negation is a substructural logic. Presented by Heinrich Wansing     

On The Computational Consequences of Independence in Propositional Logic

Sandu and Pietarinen [Partiality and Games: Propositional Logic. Logic J. IGPL 9 (2001) 101] study independence friendly propositional logics. That is, traditional propositional logic extended by means of syntax that allow connectives to be independent of each other, although the one may be subordinate to the other. Sandu and Pietarinen observe that the IF propositional logics have exotic properties, like functional completeness for three-valued functions. In this paper we focus on one of their IF propositional logics and study its properties, by means of notions from computational complexity. This approach enables us to compare propositional logic before and after the IF make-over. We observe that all but one of the best-known decision problems experience a complexity jump, provided that the complexity classes at hand are not equal. Our results concern every discipline that incorporates some notion of independence such as computer science, natural language semantics, and game theory. A corollary of one of our theorems illustrates this claim with respect to the latter discipline.     

Constructive Logic with Strong Negation is a Substructural Logic. I

The goal of this two-part series of papers is to show that constructive logic with strong negation N is definitionally equivalent to a certain axiomatic extension NFL _ew of the substructural logic FL _ew . In this paper, it is shown that the equivalent variety semantics of N (namely, the variety of Nelson algebras) and the equivalent variety semantics of NFL _ew (namely, a certain variety of FL _ew -algebras) are term equivalent. This answers a longstanding question of Nelson [30]. Extensive use is made of the automated theorem-prover Prover9 in order to establish the result. The main result of this paper is exploited in Part II of this series [40] to show that the deductive systems N and NFL _ew are definitionally equivalent, and hence that constructive logic with strong negation is a substructural logic over FL _ew . Presented by Heinrich Wansing     

Inexact Knowledge with Introspection

Standard Kripke models are inadequate to model situations of inexact knowledge with introspection, since positive and negative introspection force the relation of epistemic indiscernibility to be transitive and euclidean. Correlatively, Williamson’s margin for error semantics for inexact knowledge invalidates axioms 4 and 5. We present a new semantics for modal logic which is shown to be complete for K45, without constraining the accessibility relation to be transitive or euclidean. The semantics corresponds to a system of modular knowledge, in which iterated modalities and simple modalities are not on a par. We show how the semantics helps to solve Williamson’s luminosity paradox, and argue that it corresponds to an integrated model of perceptual and introspective knowledge that is psychologically more plausible than the one defended by Williamson. We formulate a generalized version of the semantics, called token semantics, in which modalities are iteration-sensitive up to degree n and insensitive beyond n. The multi-agent version of the semantics yields a resource-sensitive logic with implications for the representation of common knowledge in situations of bounded rationality.     

A Lewisian Semantics for S2

This paper sets out a semantics for C.I. Lewis's logic S2 based on the ontology of his 1923 paper ‘Facts, Systems, and the Unity of the World’. In that article, worlds are taken to be maximal consistent systems. A system, moreover, is a collection of facts that is closed under logical entailment and conjunction. In this paper, instead of defining systems in terms of logical entailment, I use certain ideas in Lewis's epistemology and philosophy of logic to define a class of models in which systems are taken to be primitive elements but bear certain relations to one another. I prove soundness and completeness for S2 over this class of models and argue that this semantics makes sense of at least a substantial fragment of Lewis's logical theory.     

Alternative semantics for quantified first degree relevant logic

A system FDQ of first degree entailment with quantification, extending classical quantification logic Q by an entailment connective, is axiomatised, and the choice of axioms defended and also, from another viewpoint, criticised. The system proves to be the equivalent to the first degree part of the quantified entailmental system EQ studied by Anderson and Belnap; accordingly the semantics furnished are alternative to those provided for the first degree of EQ by Belnap. A worlds semantics for FDQ is presented, and the soundness and completeness of FDQ proved, the main work of the paper going into the proof of completeness. The adequacy result is applied to yield, as well as the usual corollaries, weak relevance of FDQ and the fact that FDQ is the common first degree of a wide variety of (constant domain) quantified relevant logics. Finally much unfinished business at the first degree is discussed.     

Neighborhoods for Entailment

This paper presents a neighborhood semantics for logics of entailment. It begins with a minimal system Min that expresses the most fundamental assumptions about the entailment relation, and continues by examining various extensions that reflect further assumptions that might be made about entailment. This leads first to the logic B that is the basic relevant logic, and then to more powerful systems. All of these logics are proved to be sound and strongly complete. With B the neighborhood semantics meets the Routley–Meyer relational semantics for relevant logic; these connections are examined. The minimal and basic entailment logics are shown to have the finite model property, and hence to be decidable.     

On an Intuitionistic Modal Logic

In this paper we consider an intuitionistic variant of the modal logic S4 (which we call IS4). The novelty of this paper is that we place particular importance on the natural deduction formulation of IS4— our formulation has several important metatheoretic properties. In addition, we study models of IS4— not in the framework of Kirpke semantics, but in the more general framework of category theory. This allows not only a more abstract definition of a whole class of models but also a means of modelling proofs as well as provability.     

Negation in the Context of Gaggle Theory

We study an application of gaggle theory to unary negative modal operators. First we treat negation as impossibility and get a minimal logic system Ki that has a perp semantics. Dunn's kite of different negations can be dealt with in the extensions of this basic logic K_i. Next we treat negation as “unnecessity” and use a characteristic semantics for different negations in a kite which is dual to Dunn's original one. K_u is the minimal logic that has a characteristic semantics. We also show that Shramko's falsification logic FL can be incorporated into some extension of this basic logic K_u. Finally, we unite the two basic logics K_i and K_u together to get a negative modal logic K_-, which is dual to the positive modal logic K₊ in [7]. Shramko has suggested an extension of Dunn's kite and also a dual version in [12]. He also suggested combining them into a “united” kite. We give a united semantics for this united kite of negations.     

A weak intuitionistic propositional logic with purely constructive implication

We introduce subsystems WLJ and SI of the intuitionistic propositional logic LJ, by weakening the intuitionistic implication. These systems are justifiable by purely constructive semantics. Then the intuitionistic implication with full strength is definable in the second order versions of these systems. We give a relationship between SI and a weak modal system WM. In Appendix the Kripke-type model theory for WM is given.This work was partially supported by NSF Grant DCR85-13417     

A second-order relevance logic with modality

In this paper a system, RPF, of second-order relevance logic with S5 necessity is presented which contains a defined, notion of identity for propositions. A complete semantics is provided. It is shown that RPF allows for more than one necessary proposition. RPF contains primitive syntactic counterparts of the following semantic notions: (1) the reflexive, symmetrical, transitive binary alternativeness relation for S5 necessity, (2) the ternary Routley-Meyer alternativeness relation for implication, and (3) the Routley-Meyer notion of a prime intensional theory, as well as defined syntactic counterparts, of the semantic notions of a possible world and the Routley-Meyer ^* operator.     

A Sequent Formulation of Conditional Logic Based on Belief Change Operations

Peter Gärdenfors has developed a semantics for conditional logic, based on the operations of expansion and revision applied to states of information. The account amounts to a formalisation of the Ramsey test for conditionals. A conditional A > B is declared accepted in a state of information K if B is accepted in the state of information which is the result of revising K with respect to A. While Gärdenfors's account takes the truth-functional part of the logic as given, the present paper proposes a semantics entirely based on epistemic states and operations on these states. The semantics is accompanied by a syntactic treatment of conditional logic which is formally similar to Gentzen's sequent formulation of natural deduction rules. Three of David Lewis's systems of conditional logic are represented. The formulations are attractive by virtue of their transparency and simplicity.     

Logic for dialogue games

The purpose of this paper is to work toward an explicit logic and semantics for a game theoretically inspired theory of action. The purpose of the logic is to explicate the conceptual machinery implicit in the dialogue-game model of rational discourse developed in Carlson (1983).A variety of ideas and techniques of modal and philosophical logic are used to define a model structure that generalizes the game theoretical notion of a game in extensive form (von Neumann and Morgenstern, 1944). Relative to this model structure, semantic characterizations are given to the action-theoretic notions oftime, possibility, belief, preference, ability, intention, action, andrationality. The unification of these characterizations under the game-theoretical paradigm leads to insights about the logical interdependences between these concepts.The resulting theory of rational interaction is applied to the explication of rational dialogue. The main benefit of the enterprise for a theory of rational dialogue is that concepts and results of game theory become accessible to the explication of dialogue. In particular, the task of proving the logical coherence of a discourse is reduced to the task of showing the rationality of strategy choices made in an associated dialogue game.     

Non-Adjunctive Inference and Classical Modalities

The article focuses on representing different forms of non-adjunctive inference as sub-Kripkean systems of classical modal logic, where the inference from □A and □B to □A∧B fails. In particular we prove a completeness result showing that the modal system that Schotch and Jennings derive from a form of non-adjunctive inference in (Schotch and Jennings, 1980) is a classical system strictly stronger than EMN and weaker than K (following the notation for classical modalities presented in Chellas, 1980). The unified semantical characterization in terms of neighborhoods permits comparisons between different forms of non-adjunctive inference. For example, we show that the non-adjunctive logic proposed in (Schotch and Jennings, 1980) is not adequate in general for representing the logic of high probability operators. An alternative interpretation of the forcing relation of Schotch and Jennings is derived from the proposed unified semantics and utilized in order to propose a more fine-grained measure of epistemic coherence than the one presented in (Schotch and Jennings, 1980). Finally we propose a syntactic translation of the purely implicative part of Jaśkowski's system D₂ into a classical system preserving all the theorems (and non-theorems) explicilty mentioned in (Jaśkowski, 1969). The translation method can be used in order to develop epistemic semantics for a larger class of non-adjunctive (discursive) logics than the ones historically investigated by Jaśkowski.     

An Illocutionary Logical Explanation of the Surprise Execution

This paper further develops the system of illocutionary logic presented in ‘Propositional logic of supposition and assertion’ (Notre Dame Journal of Formal Logic 1997, 38, 325-349) to accommodate an ‘I believe that’ operator and resolve Moore's Paradox. This resolution is accomplished by providing both a truth-conditional and a commitment-based semantics. An important feature of the logical system is that the correctness of some arguments depends on who it is that makes the argument. The paper then shows that the logical system can be expanded to resolve the surprise execution paradox puzzle. The prisoner's argument showing that he can't be executed by surprise is correct but his beliefs are incoherent. The judge's beliefs (and our beliefs) about this situation are not incoherent.     

Two-Valued Logics of Intentionality: Temporality,Truth, Modality,and Identity

The essay introduces a non-Diodorean, non-Kantian temporal modal semantics based on part-whole, rather than class, theory. Formalizing Edmund Husserl’s theory of inner time consciousness, §3 uses his protention and retention concepts to define a relation of self-awareness on intentional events. §4 introduces a syntax and two-valued semantics for modal first-order predicate object-languages, defines semantic assignments for variables and predicates, and truth for formulae in terms of the axiomatic version of Edmund Husserl’s dependence ontology (viz. the Calculus [CU] of Urelements) introduced by The Ontology of Intentionality I & II. It then uses the §3 results to define the modalities of truth, and §5 extends the semantics to identity claims. §6 defines and contrasts synthetic a priori truths to analytic a priori truths, and §7 compares Brentano School noetic semantic and Leibnizian possible-world semantic perspectives on modality. The essay argues that the modal logics it defines semantically are two-valued, first-order versions of the type of language which Husserl viewed as the language of any ontology of experience (i.e. of any science), and conceived as the logic of intentionality.     

The Logic of the Ontological Square

The Ontological Square is a categorial scheme that combines two metaphysical distinctions: that between types (or universals) and tokens (or particulars) on the one hand, and that between characters (or features) and their substrates (or bearers) on the other hand. The resulting four-fold classification of things comprises particular substrates, called substances, universal substrates, called kinds, particular characters, called modes or moments, and universal characters, called attributes. Things are joined together in facts by primitive ontological ties or nexus. This article describes a logic that is meant to capture the basic intuitions behind the Ontological Square. Given a minimal correspondence between atomic logical form and ontological structure, the commitment to nexus as a distinct ontological category entails a rehabilitation of copulae as ties of predication. Thus, the Logic of the Ontological Square is a copula calculus rather than a predicate calculus; its soundness and completeness can be established with respect to a model akin to a so-called first-order semantics for standard second-order logic. Presented by Hannes Leitgeb     

Combinatory Logic and the Semantics of Substructural Logics

The results of this paper extend some of the intimate relations that are known to obtain between combinatory logic and certain substructural logics to establish a general characterization theorem that applies to a very broad family of such logics. In particular, I demonstrate that, for every combinator X, if LX is the logic that results by adding the set of types assigned to X (in an appropriate type assignment system, TAS) as axioms to the basic positive relevant logic B∘T, then LX is sound and complete with respect to the class of frames in the Routley-Meyer relational semantics for relevant and substructural logics that meet a first-order condition that corresponds in a very direct way to the structure of the combinator X itself. Presented by Rob Goldblatt     

Algebraic Semantics for Deductive Systems

The notion of an algebraic semantics of a deductive system was proposed in [3], and a preliminary study was begun. The focus of [3] was the definition and investigation of algebraizable deductive systems, i.e., the deductive systems that possess an equivalent algebraic semantics. The present paper explores the more general property of possessing an algebraic semantics. While a deductive system can have at most one equivalent algebraic semantics, it may have numerous different algebraic semantics. All of these give rise to an algebraic completeness theorem for the deductive system, but their algebraic properties, unlike those of equivalent algebraic semantics, need not reflect the metalogical properties of the deductive system. Many deductive systems that don't have an equivalent algebraic semantics do possess an algebraic semantics; examples of these phenomena are provided. It is shown that all extensions of a deductive system that possesses an algebraic semantics themselves possess an algebraic semantics. Necessary conditions for the existence of an algebraic semantics are given, and an example of a protoalgebraic deductive system that does not have an algebraic semantics is provided. The mono-unary deductive systems possessing an algebraic semantics are characterized. Finally, weak conditions on a deductive system are formulated that guarantee the existence of an algebraic semantics. These conditions are used to show that various classes of non-algebraizable deductive systems of modal logic, relevance logic and linear logic do possess an algebraic semantics.