This work aims to make tense logic a more robust tool for ontologists, philosophers, knowledge engineers and programmers by outlining a fusion of tense logic and ontology of time. In order to make tense logic better understandable, the central formal primitives of standard tense logic are derived as theorems from an informal and intuitive ontology of time. In order to make formulation of temporal propositions easier, temporal operators that were introduced (...) by Georg Henrik von Wright are developed, and mapped to the ontology of time. (shrink)

We explain two ways of revising a tense logic like kripke's (1963) modal logic by adding predicate modifiers. first we show that modifiers allow us to render valid some mixing formulas--conditionals reversing the order of a quantifier and an operator--within a complete bivalent system. then we show how modifiers enable a tense logic to give analyses close to the surface form for sentences with temporal qualifications of singular terms, e.g., 'toby was fatter then (...) than william is today'. (shrink)

The paper introduces a first-order theory in the language of predicate tense logic which contains a single simple axiom. It is shewn that this theory enables times to be referred to and sentences involving ‘now’ and ‘then’ to be formalised. The paper then compares this way of increasing the expressive capacity of predicate tense logic with other mechanisms, and indicates how to generalise the results to other modal and tense systems.

The paper presents the revised analysis of a formal language having greater expressive capabilities than a first-order predicate language. This new, first-order temporal language can express propositions involving tenses, dates, or quantification over temporal entities. The discussion includes a description of the first-order predicate language and the notion of bound and free variables. The notions of a deduction, a theorem of logic, and a consistent set of formulas are introduced, and the deduction theorem (...) and a form of the compactness theorem are stated and proved. Detailed comparison shows that the new, first-order temporal language differs from the traditional one in allowing quantification over intervals and the admission of interval constants. (shrink)

Based on the results of [11] this paper delivers uniform algorithms for deciding whether a finitely axiomatizable tense logic has the finite model property, is complete with respect to Kripke semantics, is strongly complete with respect to Kripke semantics, is d-persistent, is r-persistent.It is also proved that a tense logic is strongly complete iff the corresponding variety of bimodal algebras is complex, and that a tense logic is d-persistent iff it is complete and its (...) Kripke frames form a first order definable class. From this we obtain many natural non-d-persistent tense logics whose corresponding varieties of bimodal algebras are complex. (shrink)

The author's motivation for constructing the calculi of this paper\nis so that time and tense can be "discussed together in the same\nlanguage" (p. 282). Two types of enriched propositional caluli for\ntense logic are considered, both containing ordinary propositional\nvariables for which any proposition may be substituted. One type\nalso contains "clock-propositional" variables, a,b,c, etc., for\nwhich only clock-propositional variables may be substituted and that\ncorrespond to instants or moments in the semantics. The other type\nalso contains "history-propositional" variables, u,v,w, etc., for\nwhich only history-propositional (...) variables may be substituted and\nthat correspond to maximally linearly ordered subsets of instants.\nThis second type is for tense logics in which time is not linear\nand where at any moment there may exist alternative future courses\nof events. Quantifiers are included in both types but only for clock-\nand history-propositional variables. However, these quantifiers are\ngiven an essentially substitutional interpretation. In addition,\nbesides each clock-propositional variable being true at exactly one\ninstant, the semantics requires that for each instant there be at\nleast one clock-propositional variable true at that instant, which\nin effect amounts to having each instant of the model "denoted" in\nthe formalism by some clock-propositional variable. Thus it is not\nsurprising that quantification over clock-propositional variables\nturns out to have a "well behaved first-order semantics" (p. 284).\n{One axiom relating history- with clock-propositions seems to need\nrevision: CKTauTbuAUabUba. Since the clock-propositional variables\nmight be true at the same instant the consequent should include an\nalternative, namely, LCab.} Besides the standard truth-functional\nand tense operators G,H,F,P, the author includes L for "it is\nalways the case that". The model-theoretic earlier-than relation\nordering instants and the semantic truth-at (an instant) relation\nare formalized by Uab and Taα (for a wff α) which\nare defined respectively as LCbPa (whenever the clock-proposition\nb is the case the clock-proposition a was the case) and LCaα\n(α is the case whenever the clock-proposition a is the case).\nBecause the future tense operators are definable in terms of U\nand T and the latter are definable in terms of L and P, the\ndual of H, the author notes that his completeness proofs can be\nrestricted to L and H as primitive and with the future tense\noperators used for other interpretations, especially Prior, A.'s\nindeterminist "it will be the case that", where time is not linear.\nThe author concludes with some rather technical observations showing\nthat "in ordinary tense logics the instants are nonstandard elements\nof the models. This provides", according to the author, "a semantic\npressure to build the instants into tense logic, so that they will\nappear as standard elements in the models" (p. 283). (shrink)

We take the well-known intuitionistic modal logic of Fischer Servi with semantics in bi-relational Kripke frames, and give the natural extension to topological Kripke frames. Fischer Servi’s two interaction conditions relating the intuitionistic pre-order with the modal accessibility relation generalize to the requirement that the relation and its inverse be lower semi-continuous with respect to the topology. We then investigate the notion of topological bisimulation relations between topological Kripke frames, as introduced by Aiello and van Benthem, and show (...) that their topology-preserving conditions are equivalent to the properties that the inverse relation and the relation are lower semi-continuous with respect to the topologies on the two models. The first main result is that this notion of topological bisimulation yields semantic preservation w.r.t. topological Kripke models for both intuitionistic tense logics, and for their classical companion multi-modal logics in the setting of the Gödel translation. After giving canonical topological Kripke models for the Hilbert-style axiomatizations of the Fischer Servi logic and its classical companion logic, we use the canonical model in a second main result to characterize a Hennessy–Milner class of topological models between any pair of which there is a maximal topological bisimulation that preserve the intuitionistic semantics. (shrink)

We provide a simple translation of the satisfiability problem for regular grammar logics with converse into GF2, which is the intersection of the guarded fragment and the 2-variable fragment of first-order logic. The translation is theoretically interesting because it translates modal logics with certain frame conditions into first-order logic, without explicitly expressing the frame conditions. It is practically relevant because it makes it possible to use a decision procedure for the guarded fragment in (...) class='Hi'>order to decide regular grammar logics with converse. The class of regular grammar logics includes numerous logics from various application domains. A consequence of the translation is that the general satisfiability problem for every regular grammar logics with converse is in EXPTIME. This extends a previous result of the first author for grammar logics without converse. Other logics that can be translated into GF2 include nominal tense logics and intuitionistic logic. In our view, the results in this paper show that the natural first-order fragment corresponding to regular grammar logics is simply GF2 without extra machinery such as fixed-point operators. (shrink)

We provide a simple translation of the satisfiability problem for regular grammar logics with converse into GF2, which is the intersection of the guarded fragment and the 2-variable fragment of first-order logic. The translation is theoretically interesting because it translates modal logics with certain frame conditions into first-order logic, without explicitly expressing the frame conditions. It is practically relevant because it makes it possible to use a decision procedure for the guarded fragment in (...) class='Hi'>order to decide regular grammar logics with converse. The class of regular grammar logics includes numerous logics from various application domains. A consequence of the translation is that the general satisfiability problem for every regular grammar logics with converse is in EXPTIME. This extends a previous result of the first author for grammar logics without converse. Other logics that can be translated into GF2 include nominal tense logics and intuitionistic logic. In our view, the results in this paper show that the natural first-order fragment corresponding to regular grammar logics is simply GF2 without extra machinery such as fixed-point operators. (shrink)

We provide a version of first-order hybrid tense logic with predicate abstracts and definite descriptions as the only non-rigid terms. It is formalised by means of a tableau calculus working on sat-formulas. A particular theory of DD exploited here is essentially based on the approach of Russell, but with descriptions treated as genuine terms. However, the reductionist aspect of the Russellian approach is retained in several ways. Moreover, a special form of tense definite descriptions is (...) formally developed. A constructive proof of the interpolation theorem for this calculus is given, which is an extension of the result provided by Blackburn and Marx. (shrink)

The last chapter examines the tense system used by ordinarily competent speakers of English to discuss past, present, and future events, actual and possible events, and various combinations of these. I present a systematic method for translating English sentences containing certain compound verb tenses and embedded tense constructions into a logical language using tense operators. Finally I show how the usual semantics for these operators reflects the truth conditions of the original English sentences. I argue, however, that (...) a tense logical semantics reflecting the use of tense in English will contain a partially ordered tense structure rather than one that is linearly ordered or branching. ;The third chapter discusses logic of 'unless'. I show that many of the previously puzzling features of this word can be understood by considering the tenses of the verbs in the sentences joined by 'unless'. In a number of cases it turns out that 'unless' should not be interpreted as a truth-functional connective at all, but is best understood as an intensional, tense connective. ;In the second chapter I discuss Quine's doctrine of eternal sentences. I take Quine's position to be that all the information important for logic and science presented in tensed English sentences can also be presented by eternal sentences which use timeless verbs and data and clock times. I argue that in so far as logic and science are concerned with an analysis of the reasons for human action, and with the explanation and prediction of specific events, eternal sentences lose indexical information that is necessary to accomplish these tasks. ;The first chapter investigates what may be called the standard view of propositions. On this view propositions are abstract objects that are timelessly true , and serve both as the meanings of sentences and as the objects of propositional attitudes. Although this view was widely held by a previous generation of logicians and is found in many textbooks today, there are serious difficulties in the view. I show that many of these difficulties stem from the claim that propositions are timelessly true . The standard view has been revised in two general ways. The first sort of revision allows propositions to be sometimes true and sometimes false. This position is consistent with the development of tense logic as one of the intensional logics. The second sort of revision replaces the notion of timeless propositions with that of eternal sentences which always have the same truth value. On this view tense logic is not worth serious philosophic attention since its basic notion, that of truth at a time, can be eliminated in favor of eternal truth. ;The first part of the project examines two major sources of criticism of tense logic: the view that logic is concerned with timeless propositions, and Quine's doctrine of eternal sentences. The second part of the project discusses several problems in logical theory that the use of tense logic can clarify or resolve, and that alternative theories are unable to present accurately, much less to elucidate. ;In the past few years there has been increasing interest in the logic of indexicals, including the temporal indexical 'now', and in the relationship between tense and modality. Although modern tense logic has reached a high level of technical sophistication, often specifically in response to this interest, many philosophers remain skeptical about the value of tense logic as a philosophic tool. This thesis addresses that skepticism and argues that it is unjustified. (shrink)

The forward convergence constraint is important to time analysis. Without it, given two future moments to the same point, the time branches. This is unacceptable if one assumes that time is linear. Nevertheless, one may wish to consider time-branching in order to discuss future possibilities. One can have both a linear order for the time and branching through the combination of the tense logic semantics with those of an alethic logic which allows the evaluation of (...) the timelines of other possible worlds. In this paper, I give the semantics and the tableaux systems for some alethic-tense logics. I review one in which worlds differ on their time orders, another in which they agree on the time order, a pair of conditional tense logics ), and the first-order version of MT. A brief philosophical discussion arises from every system. (shrink)

I consider the first-order modal logic which counts as valid those sentences which are true on every interpretation of the non-logical constants. Based on the assumptions that it is necessary what individuals there are and that it is necessary which propositions are necessary, Timothy Williamson has tentatively suggested an argument for the claim that this logic is determined by a possible world structure consisting of an infinite set of individuals and an infinite set of worlds. He (...) notes that only the cardinalities of these sets matters, and that not all pairs of infinite sets determine the same logic. I use so-called two-cardinal theorems from model theory to investigate the space of logics and consequence relations determined by pairs of infinite sets, and show how to eliminate the assumption that worlds are individuals from Williamson’s argument. (shrink)

In this dissertation, we construct a consistent, complete quotational logic G$\sb1$. We first develop a semantics, and then show the undecidability of circular quotation and anaphorism . Next, a complete axiom system is presented, and completeness theorems are shown for G$\sb1$. We show that definable truth exists in G$\sb1$. ;Later, we replace equality in G$\sb1$ with an equivalence relation. An axiom system and completeness theorems are provided for this equality-free version of G$\sb1$, which is useful in program verification. (...) ;Interpolation and definability are discussed in intensional and extensional contexts. We show that G$\sb1$ contains the complete first order theory of arithmetic by implicit definitional extension. ;The last chapter deals with representability and fixed points. Derived induction schemata are produced, and G$\sb1$ is shown to be a recursion theory. We give an example of how G$\sb1$ may be used to solve domain equations of Scott. (shrink)

In this paper the language of first-order modal logic is enriched with an operator @ ('actually') such that, in any model, the evaluation of a formula @A at a possible world depends on the evaluation of A at the actual world. The models have world-variable domains. All the logics that are discussed extend the classical predicate calculus, with or without identity, and conform to the philosophical principle known as serious actualism. The basic logic relies on the (...) system K, whereas others correspond to various properties that the actual world may have. All the logics are axiomatized. (shrink)

In recent years combinations of tense and modality have moved intothe focus of logical research. From a philosophical point of view, logical systems combining tense and modality are of interest because these logics have a wide field of application in original philosophical issues, for example in the theory of causation, of action, etc. But until now only methods yielding completeness results for propositional languages have been developed. In view of philosophical applications, analogous results with respect to languages of (...) predicate logic are desirable, and in this paper I present two such results. The main developments in this area can be split into two directions, differing in the question whether the ordering of time is world-independent or not. Semantically, this difference appears in the discussion whether T x W-frames or Kamp-frames (resp. Ockham-frames) provide a suitable semantics for combinations of tense and modality. Here, two calculi are presented, the first adequate with respect to Kamp-semantics, the second to T x Wsemantics. (Both calculi contain an appropriate version of Gabbay's irreflexivity rule.) Furthermore, the proposed constructions of canonical frames simplify some of those which have hitherto been discussed. (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)

Well-written undergraduate-level introduction begins with symbolic logic and set theory, followed by presentation of statement calculus and predicate calculus. First-order theories are discussed in some detail, with special emphasis on number theory. After a discussion of truth and models, the completeness theorem is proved. "...an excellent text."—Mathematical Reviews. Exercises. Bibliography.

This paper is an attempt to develop the many-valued first-order fuzzy logic. The set of its truth, values is supposed to be either a finite chain or the interval 0, 1 of reals. These are special cases of a residuated lattice L, , , , , 1, 0. It has been previously proved that the fuzzy propositional logic based on the same sets of truth values is semantically complete. In this paper the syntax and semantics of (...) the first-order fuzzy logic is developed. Except for the basic connectives and quantifiers, its language may contain also additional n-ary connectives and quantifiers. Many propositions analogous to those in the classical logic are proved. The notion of the fuzzy theory in the first-order fuzzy logic is introduced and its canonical model is constructed. Finally, the extensions of Gödel's completeness theorems are proved which confirm that the first-order fuzzy logic is also semantically complete. (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.

First-order Gödel logics are a family of finite- or infinite-valued logics where the sets of truth values V are closed subsets of [0,1] containing both 0 and 1. Different such sets V in general determine different Gödel logics GV (sets of those formulas which evaluate to 1 in every interpretation into V). It is shown that GV is axiomatizable iff V is finite, V is uncountable with 0 isolated in V, or every neighborhood of 0 in V is (...) uncountable. Complete axiomatizations for each of these cases are given. The r.e. prenex, negation-free, and existential fragments of all first-order Gödel logics are also characterized. (shrink)

When philosophers and linguists theorize about the nature of conditionals, they tend to make a number of assumptions about the linguistic structure of these sentences. For example, they almost invariably assume that conditionals have “antecedents” and “consequents” and that these have the structure of independent clauses. With a few exceptions, they assume that conditionals are categorized according to whether they are in the “indicative” or the “subjunctive” “mood”. However, rarely do they formulate criteria for identifying these moods, or for distinguishing (...) between indicative and subjunctive conditionals.Through an analysis of the coordinated verb tense structures of the clauses of English conditionals, I challenge these and other related assumptions and show that the one relatively well-developed attempt to provide criteria for distinguishing between indicative and subjunctive conditionals---that of Gibbard (1980)---fails in its task. I then offer an alternative account of the linguistic structure of conditional constructions. To represent their structure I use first-order predicate logic with added devices to indicate deictic and anaphoric reference. (shrink)

Higher‐order metaphysicians take facts to be higher‐order beings, i.e., entities in the range of irreducibly higher‐order quantifiers. In this paper, I investigate the impact of this conception of facts on the debate about the reality of tense. I identify two major repercussions. The first concerns the logical space of tense realism: on a higher‐order conception of facts, a prominent version of tense realism, dynamic absolutism, turns out to conflict with the laws of (...) (higher‐order tense) logic. The second concerns our understanding of the positions occupying this logical space: on a higher‐order conception of facts, an attractive interpretation of the central tense realist notion of ‘facts constituting reality’ becomes unavailable. I discuss these results in the context of the more general project of higher‐order metaphysics and the (meta)metaphysics of time, drawing out their implications for the nature of the disputes both between realists and anti‐realists about tense and between different tense realist factions. (shrink)

In this research I will focus on a basis for a formal model based on an alternative kind of logic invented by Hans Götzsche: Occurrence Logic (Occ Log), which is not based on truth values and truth functionality. Also, I have taken into account tense logic developed and elaborated by A. N. Prior. In this article I will provide a conceptual and logical foundation for formal Occurrence Logic based on symbolic logic and will illustrate (...) the most important relations between symbolic logic and Occurrence Logic. There will be a special need to focus on arguments based on symbolic occurrence logic. The interrelationships and dependencies between symbolic logic and Occ Log could be conducive to an approach that can express and analyse ‘the occurrences of the world’s descriptions based on various logical principles at different moments’. Symbolic Occ Log checks the occurrence conditioning and the priority of occurrences by employing occurrence values. I shall conclude that the desired approach could gradually support me in providing a truth-functional independent first-order predicate calculus that could work on semantic analysis of different propositions within world descriptions. (shrink)

Prior investigated a tense logic with an operator for ‘historical necessity’, where a proposition is necessary at a time iff it is true at that time in all worlds ‘accessible’ from that time. Axiomatisations of this logic all seem to require non-standard axioms or rules. The present paper presents an axiomatisation of a first-order version of Prior’s logic by using a predicate which enables any time to be picked out by an individual in the (...) domain of interpretation. (shrink)

This somewhat unusual introductory logic text has been clearly designed to bring the student into contact with the mathematical aspects and problems of logical systems as quickly and naturally as possible, at the expense of "fundamental" discussions of logical theory, language and philosophy. In the introductory chapter, the student is introduced to elementary logical technique via Gentzen-type rules of inference, given the requisite set-theoretical background, given a preliminary orientation with respect to the concept of an axiomatic theory, and then (...) shown the full first-order language of the basic predicate calculus. The following chapter develops an axiomatic version of first-order logic with identity, and exhibits proofs of the deduction theorem, completeness theorem, and various applications of equivalence and replacement theorems and other materials to formal number theory. Finally, in what is undoubtably the most valuable part of the book, a good treatment of first-order mathematical theories is given in the third chapter. This includes an extensive discussion of Tarski's semantical theory of truth and a detailed version of Henkin's completeness theorem. Sections on decidability and Gödel's theorem complete this fine introduction to basic mathematical logic. There are numerous exercises throughout the book.—H. P. K. (shrink)

We generalize two well-known model-theoretic characterization theorems from propositional modal logic to first-order modal logic. We first study FML-definable frames and give a version of the Goldblatt–Thomason theorem for this logic. The advantage of this result, compared with the original Goldblatt–Thomason theorem, is that it does not need the condition of ultrafilter reflection and uses only closure under bounded morphic images, generated subframes and disjoint unions. We then investigate Lindström type theorems for first- (...) class='Hi'>order modal logic. We show that FML has the maximal expressive power among the logics extending FML which satisfy compactness, bisimulation invariance and the Tarski union property. (shrink)

This paper provides finitary jointly necessary and sufficient acceptance and rejection conditions for the logical constants of a first order quantificational language. By introducing the notion of making an assignment as a distinct object level practice—something you do with a sentence—(as opposed to a meta-level semantic notion) and combining this with the practice of (hypothetical and categorical) acceptance and rejection and the practice of making suppositions one gains a structure that is sufficiently rich to fully characterize the class (...) of classical first order theories. The analysis thus provides a way of characterizing classical first order quantification by expressivist means. (shrink)

This is a companion paper to Braüner where a natural deduction system for propositional hybrid logic is given. In the present paper we generalize the system to the first-order case. Our natural deduction system for first-order hybrid logic can be extended with additional inference rules corresponding to conditions on the accessibility relations and the quantifier domains expressed by so-called geometric theories. We prove soundness and completeness and we prove a normalisation theorem. Moreover, we give (...) an axiom system first-order hybrid logic. (shrink)

The volume includes the proceedings from the conference FOL75 -- 75 Years of First-Order Logic held at Humboldt University, Berlin, September 18 - 21, 2003 on the occasion of the anniversary of the publication of Hilbert's and Ackermann's Grundzuge der theoretischen Logik. The papers provide analyses of the historical conditions of the shaping of FOL, discuss several modern rivals to it, and show the importance of FOL for interdisciplinary research. While there is no doubt that the celebrated (...) book marks a most important step in the development of logic, the volume in hand proves the actuality of the question "Which logic is the right logic." The volume contains articles by: H. Andreka, J. X. Madarasz, I. Nemeti, A. Avron, K. Brunnler, A. Guglielmi, G. Englebretsen, W. Ewald, P. Hajek, J. Hintikka, W. Hodges, M. Kracht, R. Lanzet, H. Ben-Yami, C. Toke, S. P. Odintsov, H. Wansing, J. A. Robinson, M. Rossberg, M. Thielscher, D. E. Willard, andJ. Wole 'nski. (shrink)

Within a weak system \ of intuitionistic analysis one may prove, using the Weak Fan Theorem as an additional axiom, a completeness theorem for intuitionistic first-order predicate logic relative to validity in generalized Beth models as well as a completeness theorem for classical first-order predicate logic relative to validity in intuitionistic structures. Conversely, each of these theorems implies over \ the Weak Fan Theorem.

In this paper, we introduce a new fragment of the first-order temporal language, called the monodic fragment, in which all formulas beginning with a temporal operator have at most one free variable. We show that the satisfiability problem for monodic formulas in various linear time structures can be reduced to the satisfiability problem for a certain fragment of classical first-order logic. This reduction is then used to single out a number of decidable fragments of (...) class='Hi'>first-order temporal logics and of two-sorted first-order logics in which one sort is intended for temporal reasoning. Besides standard first-order time structures, we consider also those that have only finite first-order domains, and extend the results mentioned above to temporal logics of finite domains. We prove decidability in three different ways: using decidability of monadic second-order logic over the intended flows of time, by an explicit analysis of structures with natural numbers time, and by a composition method that builds a model from pieces in finitely many steps. (shrink)

We introduce a homotopy-theoretic interpretation of intuitionistic first-order logic based on ideas from Homotopy Type Theory. We provide a categorical formulation of this interpretation using the framework of Grothendieck fibrations. We then use this formulation to prove the central property of this interpretation, namely homotopy invariance. To do this, we use the result from [8] that any Grothendieck fibration of the kind being considered can automatically be upgraded to a two-dimensional fibration, after which the invariance property is (...) reduced to an abstract theorem concerning pseudonatural transformations of morphisms into two-dimensional fibrations. (shrink)

Logic has sometimes been seen as an alternative to metaphysics and to speculation. In this paper it is argued that a different story should be told when it comes to temporal logic and tense-logic in particular. A. N. Prior’s first formulation of tense logic was mainly established in order to qualify the discussion of certain metaphysical and conceptual problems. Although temporal logic has now been developed in various abstract and rather technical (...) ways, it may still serve as a great help for anyone who wants to clarify the discussion of important existential questions like the nature of time, determinism, future contingency or freedom of choice. (shrink)

It has been shown recently that monodic first-order temporal logic without functional symbols but with equality is incomplete, i.e., the set of the valid formulae of this logic is not recursively enumerable. In this paper we show that an even simpler fragment consisting of monodic monadic two-variable formulae is not recursively enumerable.

We present an axiomatisation for the first-order temporal logic with connectives Until and Since over the class of all linear flows of time. Completeness of the axiom system is proved.We also add a few axioms to find a sound and complete axiomatisation for the first order temporal logic of Until and Since over rational numbers time.

In this paper a first-order version of hybrid logic is presented. The language is obtained by adding nominals, satisfaction operators and the down-arrow binder to classical first-order modal logic. The satisfaction operators are applied to both formulas and terms. Moreover adding the universal modality is discussed. This first-order hybrid language is interpreted over varying domains and a sound and complete, fully internalized tableau system for this logic is given.

A sentence of first-order logic is satisfiable if it is true in some structure, and finitely satisfiable if it is true in some finite structure. The question arises as to whether there exists an algorithm for determining whether a given formula of first-order logic is satisfiable, or indeed finitely satisfiable. This question was answered negatively in 1936 by Church and Turing (for satisfiability) and in 1950 by Trakhtenbrot (for finite satisfiability).In contrast, the satisfiability and (...) finite satisfiability problems are algorithmically solvable for restricted subsets---or, as we say, fragments---of first-order logic, a fact which is today of considerable interest in Computer Science. This book provides an up-to-date survey of the principal axes of research, charting the limits of decision in first-order logic and exploring the trade-off between expressive power and complexity of reasoning. Divided into three parts, the book considers for which fragments of first-order logic there is an effective method for determining satisfiability or finite satisfiability. Furthermore, if these problems are decidable for some fragment, what is their computational complexity? Part I focusses on fragments defined by restricting the set of available formulas. Topics covered include the Aristotelian syllogistic and its relatives, the two-variable fragment, the guarded fragment, the quantifier-prefix fragments and the fluted fragment. Part II investigates logics with counting quantifiers. Starting with De Morgan's numerical generalization of the Aristotelian syllogistic, we proceed to the two-variable fragment with counting quantifiers and its guarded subfragment, explaining the applications of the latter to the problem of query answering in structured data. Part III concerns logics characterized by semantic constraints, limiting the available interpretations of certain predicates. Taking propositional modal logic and graded modal logic as our cue, we return to the satisfiability problem for two-variable first-order logic and its relatives, but this time with certain distinguished binary predicates constrained to be interpreted as equivalence relations or transitive relations. The work finishes, slightly breaching the bounds of first-order logic proper, with a chapter on logics interpreted over trees. (shrink)

Many authors have noted that there are types of English modal sentences cannot be formalized in the language of basic first-order modal logic. Some widely discussed examples include “There could have been things other than there actually are” and “Everyone who is actually rich could have been poor.” In response to this lack of expressive power, many authors have discussed extensions of first-order modal logic with two-dimensional operators. But claims about the relative expressive power (...) of these extensions are often justified only by example rather than by rigorous proof. In this paper, we provide proofs of many of these claims and present a more complete picture of the expressive landscape for such languages. (shrink)

The first-order temporal logics with □ and ○ of time structures isomorphic to ω (discrete linear time) and trees of ω-segments (linear time with branching gaps) and some of its fragments are compared: the first is not recursively axiomatizable. For the second, a cut-free complete sequent calculus is given, and from this, a resolution system is derived by the method of Maslov.

One is often said to be reasoning well when they are reasoning logically. Many attempts to say what logical reasoning is have been proposed, but one commonly proposed system is first-order classical logic. This Element will examine the basics of first-order classical logic and discuss some surrounding philosophical issues. The first half of the Element develops a language for the system, as well as a proof theory and model theory. The authors provide theorems (...) about the system they developed, such as unique readability and the Lindenbaum lemma. They also discuss the meta-theory for the system, and provide several results there, including proving soundness and completeness theorems. The second half of the Element compares first-order classical logic to other systems: classical higher order logic, intuitionistic logic, and several paraconsistent logics which reject the law of ex falso quodlibet. (shrink)