A new system of dynamic logic is introduced and motivated, witha novel approach to variable binding for incremental interpretation. Thesystem is shown to be equivalent to first order logic and complete.The new logic combines the dynamic binding idea from DynamicPredicate Logic with De Bruijn style variable free indexing. Quantifiersbind the next available variable register; the indexing mechanismguarantees that active registers are never overwritten by newquantifiers actions. Apart from its interest in its own right, theresulting system has (...) certain advantages over Dynamic Predicate Logic orDiscourse Representation Theory. It comes with a more well behaved(i.e., transitive) consequence relation, it gives a more explicitaccount of how anaphoric context grows as text gets processed, and ityields new insight into the dynamics of anaphoric linking in reasoning.Incremental dynamics also points to a new way of handling contextdynamically in Montague grammar. (shrink)

Dynamic First Order Logic results from interpreting quantification over a variable v as change of valuation over the v position, conjunction as sequential composition, disjunction as non-deterministic choice, and negation as test for continuation. We present a tableau style calculus for DFOL with explicit binding, prove its soundness and completeness, and point out its relevance for programming with DFOL, for automated program analysis including loop invariant detection, and for semantics of natural language. We also extend this (...) to an infinitary calculus for DFOL with iteration and connect up with other work in dynamic logic. (shrink)

Dynamic epistemic logic (DEL) is a multi-modal logic for reasoning about the change of knowledge in multi-agent systems. It extends epistemic logic by a modal operator for actions which announce logical formulas to other agents. In Hilbert-style proof calculi for DEL, modal action formulas are reduced to epistemic logic, whereas current sequent calculi for DEL are labelled systems which internalize the semantic accessibility relation of the modal operators, as well as the accessibility relation underlying the semantics of the (...) actions. We present a novel cut-free ordinary sequent calculus, called |$ \textbf{G4}_{P,A}[] $|⁠, for propositional DEL. In contrast to the known sequent calculi, our calculus does not internalize the accessibility relations, but—similar to Hilbert style proof calculi—action formulas are reduced to epistemic formulas. Since no ordinary sequent calculus for full S5 modal logic is known, the proof rules for the knowledge operator and the Boolean operators are those of an underlying S4 modal calculus. We show the soundness and completeness of |$ \textbf{G4}_{P,A}[] $| and prove also the admissibility of the cut-rule and of several other rules for introducing the action modality. (shrink)

We present a multi-conclusion natural deduction calculus characterizing the dynamic reasoning typical of Adaptive Logics. The resulting system AdaptiveND is sound and complete with respect to the propositional fragment of adaptive logics based on CLuN. This appears to be the first tree-format presentation of the standard linear dynamic proof system typical of Adaptive Logics. It offers the advantage of full transparency in the formulation of locally derivable rules, a connection between restricted inference-rules and their (...) adaptive counterpart, and the formulation of abnormalities as a subtype of well-formed formulas. These features of the proposed calculus allow us to clarify the relation between defeasible and multiple-conclusion approaches to classical recapture. (shrink)

Modern fundamental science tends to avoid the principle of physical causality and realism, replacing it with heuristically postulated and separated mathematical constructions that impose their own rules before being adjusted to measurement results. While it is officially accepted as the single possible kind of rigorous knowledge, we argue that another, explicitly extended kind of science can provide the causally complete picture of reality avoiding the glaring gaps, growing problems and persisting stagnation of the artificially reduced knowledge paradigm. The (...) logic of science development and especially its current state call for the urgently needed transition to the extended, causally complete kind of knowledge and related sustainable progress at superior creativity levels of self-aware, reason-based society. (shrink)

Current dynamic-epistemic logics model different types of information change in multi-agent scenarios. We generalize these logics to a probabilistic setting, obtaining a calculus for multi-agent update with three natural slots: prior probability on states, occurrence probabilities in the relevant process taking place, and observation probabilities of events. To match this update mechanism, we present a complete dynamic logic of information change with a probabilistic character. The completeness proof follows a compositional methodology that applies to (...) a much larger class of dynamic-probabilistic logics as well. Finally, we discuss how our basic update rule can be parameterized for different update policies, or learning methods. (shrink)

We define a tableau calculus for the logic of only knowing and knowing at most ON, which is an extension of Levesque's logic of only knowing O. The method is based on the possible-world semantics of the logic ON, and can be considered as an extension of known tableau calculi for modal logic K45. From the technical viewpoint, the main features of such an extension are the explicit representation of "unreachable" worlds in the tableau, and an additional branch closure (...) condition implementing the property that each world must be either reachable or unreachable. The calculus allows for establishing the computational complexity of reasoning about only knowing and knowing at most. Moreover, we prove that the method matches the worst-case complexity lower bound of the satisfiability problem for both ON and O. With respect to [22], in which the tableau calculus was originally presented, in this paper we both provide a formal proof of soundness and completeness of the calculus, and prove the complexity results for the logic ON. (shrink)

In this paper we study automated reasoning in the modal logic CPDLreg which is a combination of CPDL (Propositional Dynamic Logic with Converse) and REGc (Regular Grammar Logic with Converse). The logic CPDL is widely used in many areas, including program verification, theory of action and change, and knowledge representation. On the other hand, the logic REGc is applicable in reasoning about epistemic states and ontologies (via Description Logics). The modal logic CPDLreg can serve as (...) a technical foundation for reasoning about agency. Even very rich multi-agent logics can be embedded into CPDLreg via a suitable translation. Therefore, CPDLreg can serve as a test bed to implement and possibly verify new ideas without providing specific automated reasoning techniques for the logic in question. This process can to a large extent be automated. The idea of embedding various logics into CPDLreg is illustrated on a rather advanced logic TEAMLOGK designed to specify teamwork in multi-agent systems. Apart from defining informational and motivational attitudes of groups of agents, TEAMLOGK allows for grading agents' beliefs, goals and intentions. The current paper is a companion to our paper (Dunin-Kęplicz et al., 2010a). The main contribution are proofs of soundness and completeness of the tableau calculus for CPDLreg provided in (Dunin-Kęplicz et al., 2010a). (shrink)

Reasoning with the maximally consistent subsets of the premises is a well-known approach for handling contradictory information. In this paper we consider several variations of this kind of reasoning, for each one we introduce two complementary computational methods that are based on logical argumentation theory. The difference between the two approaches is in their ways of making consequences: one approach is of a declarative nature and is related to Dung-style semantics for abstract argumentation, while the other approach (...) has a more proof-theoretical flavor, extending Gentzen-style sequent calculi. The outcome of this work is a new perspective on reasoning with MCS, which shows a strong link between the latter and argumentation systems, and which can be generalized to some related formalisms. As a by-product of this we obtain soundness and completeness results for the dynamic proof systems with respect to several of Dung’s semantics. In a broader context, we believe that this work helps to better understand and evaluate the role of logic-based instantiations of argumentation frameworks. (shrink)

Current dynamic-epistemic logics model different types of information change in multi-agent scenarios. We generalize these logics to a probabilistic setting, obtaining a calculus for multi-agent update with three natural slots: prior probability on states, occurrence probabilities in the relevant process taking place, and observation probabilities of events. To match this update mechanism, we present a complete dynamic logic of information change with a probabilistic character. The completeness proof follows a compositional methodology that applies to (...) a much larger class of dynamic-probabilistic logics as well. Finally, we discuss how our basic update rule can be parameterized for different update policies, or learning methods. (shrink)

This paper presents a sound and complete proof system for the first order fragment of Discourse Representation Theory. Since the inferences that human language users draw from the verbal input they receive for the most transcend the capacities of such a system, it can be no more than a basis on which more powerful systems, which are capable of producing those inferences, may then be built. Nevertheless, even within the general setting of first order logic the structure of the (...) formulas of DRS-languages, i.e. of the Discourse Representation Structures suggest for the components of such a system inference rules that differ somewhat from those usually found in proof systems for the first order predicate calculus and which are, we believe, more in keeping with inference patterns that are actually employed in common sense reasoning.This is why we have decided to publish the present exercise, in spite of the fact that it is not one for which a great deal of originality could be claimed. In fact, it could be argued that the problem addressed in this paper was solved when Gödel first established the completeness of the system of Principia Mathematica for first order logic. For the DRS-languages we consider here are straightforwardly intertranslatable with standard formulations of the predicate calculus; in fact the translations are so straightforward that any sound and complete proof system for first order logic can be used as a sound and complete proof system for DRSs: simply translate the DRSs into formulas of predicate logic and then proceed as usual. As a matter of fact, this is how one has chosen to proceed in some implementations of DRT, which involve inferencing as well as semantic representation; an example is the Lex system developed jointly by IBM and the University of Tübingen ). (shrink)

Ibeling et al. (2023) axiomatize increasingly expressive languages of causation and probability, and Mossé et al. (2024) show that reasoning (specifically the satisfiability problem) in each causal language is as difficult, from a computational complexity perspective, as reasoning in its merely probabilistic or “correlational” counterpart. Introducing a summation operator to capture common devices that appear in applications—such as the do-calculus of Pearl (2009) for causal inference, which makes ample use of marginalization—van der Zander et al. (2023) partially (...) extend these earlier complexity results to causal and probabilistic languages with marginalization. We complete this extension, fully characterizing the complexity of probabilistic and causal reasoning with summation, demonstrating that these again remain equally difficult. Surprisingly, allowing free variables for random variable values results in a system that is undecidable, so long as the ranges of these random variables are unrestricted. We finally axiomatize these languages featuring marginalization (or more generally summation), resolving open questions posed by Ibeling et al. (2023). (shrink)

Standpoint logic is a recently proposed formalism in the context of knowledge integration, which advocates a multi-perspective approach permitting reasoning with a selection of diverse and possibly conflicting standpoints rather than forcing their unification. In this paper, we introduce nested sequent calculi for propositional standpoint logics---proof systems that manipulate trees whose nodes are multisets of formulae---and show how to automate standpoint reasoning by means of non-deterministic proof-search algorithms. To obtain worst-case complexity-optimal proof-search, we introduce a novel technique (...) in the context of nested sequents, referred to as "coloring," which consists of taking a formula as input, guessing a certain coloring of its subformulae, and then running proof-search in a nested sequent calculus on the colored input. Our technique lets us decide the validity of standpoint formulae in CoNP since proof-search only produces a partial proof relative to each permitted coloring of the input. We show how all partial proofs can be fused together to construct a complete proof when the input is valid, and how certain partial proofs can be transformed into a counter-model when the input is invalid. These "certificates" (i.e. proofs and counter-models) serve as explanations of the (in)validity of the input. (shrink)

Dynamic Topological Logic () is a combination of , under its topological interpretation, and the temporal logic interpreted over the natural numbers. is used to reason about properties of dynamical systems based on topological spaces. Semantics are given by dynamic topological models, which are tuples , where is a topological space, f a function on X and V a truth valuation assigning subsets of X to propositional variables. Our main result is that the set of valid formulas of (...) over spaces with continuous functions is recursively enumerable. We show this by defining alternative semantics for . Under standard semantics, is not complete for Kripke frames. However, we introduce the notion of a non-deterministic quasimodel, where the function f is replaced by a binary relation g assigning to each world multiple temporal successors. We place restrictions on the successors so that the logic remains unchanged; under these alternative semantics, becomes Kripke-complete. We then apply model-search techniques to enumerate the set of all valid formulas. (shrink)

We present a Hilbert style axiomatization and an equational theory for reasoning about actions and capabilities. We introduce two novel features in the language of propositional dynamic logic, converse as backwards modality and abstract processes specified by preconditions and effects, written as \({\varphi \Rightarrow \psi}\) and first explored in our recent paper (Hartonas, Log J IGPL Oxf Univ Press, 2012), where a Gentzen-style sequent calculus was introduced. The system has two very natural interpretations, one based on the (...) familiar relational semantics and the other based on type semantics, where action terms are interpreted as types of actions (sets of binary relations). We show that the proof systems do not distinguish between the two kinds of semantics, by completeness arguments. Converse as backwards modality together with action types allow us to produce a new purely equational axiomatization of Dynamic Algebras, where iteration is axiomatized independently of box and where the fixpoint and Segerberg induction axioms are derivable. The system also includes capabilities operators and our results provide then a finitary Hilbert-style axiomatization and a decidable system for reasoning about agent capabilities, missing in the KARO framework. (shrink)

This paper presents and illustrates a formal logic for the abduction of singular hypotheses. The logic has a semantics and a dynamic proof theory that is sound and complete with respect to the semantics. The logic presupposes that, with respect to a specific application, the set of explananda and the set of possible explanantia are disjoint . Where an explanandum can be explained by different explanantia, the logic allows only for the abduction of their disjunction.

We present a sound and complete tableau calculus for the class of regular grammar logics. Our tableau rules use a special feature called automaton-labelled formulae, which are similar to formulae of automaton propositional dynamic logic. Our calculus is cut-free and has the analytic superformula property so it gives a decision procedure. We show that the known EXPTIME upper bound for regular grammar logics can be obtained using our tableau calculus. We also give an effective Craig (...) interpolation lemma for regular grammar logics using our calculus. (shrink)

We treat the problem of reasoning with ambiguous propositions. Even though ambiguity is obviously problematic for reasoning, it is no less obvious that ambiguous propositions entail other propositions, and are entailed by other propositions. This article gives a formal analysis of the underlying mechanisms, both from an algebraic and a logical point of view. The main result can be summarized as follows: sound reasoning with ambiguity requires a distinction between equivalence on the one and congruence (...) on the other side: the fact that \ entails \ does not imply \ can be substituted for \ in all contexts preserving truth. Without this distinction, we will always run into paradoxical results. We present the sequent calculus \, which we conjecture implements sound and complete propositional reasoning with ambiguity, and provide it with a language-theoretic semantics, where letters represent unambiguous meanings and concatenation represents ambiguity. (shrink)

In the present article, we introduce a multi-type display calculus for dynamic epistemic logic, which we refer to as Dynamic Calculus. The display approach is suitable to modularly chart the space of dynamic epistemic logics on weaker-than-classical propositional base. The presence of types endows the language of the Dynamic Calculus with additional expressivity, allows for a smooth proof-theoretic treatment, and paves the way towards a general methodology for the design of proof systems (...) for the generality of dynamic logics, and certainly beyond dynamic epistemic logic. We prove that the Dynamic Calculus adequately captures Baltag–Moss–Solecki's dynamic epistemic logic, and enjoys Belnap-style cut elimination. (shrink)

Equational reasoning arises in many areas of mathematics and computer science. It is a cornerstone of algebraic reasoning and results essential in tasks of specification and verification in functional programming, where a program is mainly a set of equations. The usual manipulation of identities while conducting informal proofs obviates many intermediate steps that are neccesary while developing them using a formal system, such as the equationally complete Birkhoff calculus ${\mathcal{B}}$. This deductive system does not fit in (...) the common manner of doing mathematical proofs, and it is not compatible with the mechanisms of proof assistants. The aim of this work is to provide a deductive system ${\mathcal{B}}^{\textrm{GOAL}}$ for equality, equivalent to ${\mathcal{B}}$ but suitable for constructing equational proofs in a backward fashion. This feature makes it adequate for interactive proof-search in the approach of proof assistants. This will be achieved by turning ${\mathcal{B}}^{\textrm{GOAL}}$ into a transition system of formal tactics in the style of Edinburgh LCF, such transformation allows us to give a direct formal definition of backward proof in equational logic. (shrink)

In this dissertation we present proof systems for several modal logics. These proof systems are based on analytic (or semantic) tableaux. -/- Modal logics are logics for reasoning about possibility, knowledge, beliefs, preferences, and other modalities. Their semantics are almost always based on Saul Kripke’s possible world semantics. In Kripke semantics, models are represented by relational structures or, equivalently, labeled graphs. Syntactic formulas that express statements about knowledge and other modalities are evaluated in terms of such models. -/- This (...) dissertation focuses on modal logics with dynamic operators for public announcements, belief revision, preference upgrades, and so on. These operators are defined in terms of mathematical operations on Kripke models. Thus, for example, a belief revision operator in the syntax would correspond to a belief revision operation on models. -/- The ‘dynamic’ semantics of dynamic modal logics are a clever way of extending languages without compromising on intuitiveness. We present ‘dynamic’ tableau proof systems for these dynamic semantics, with the express aim to make them conceptually simple, easy to use, modular, and extensible. This we do by reflecting the semantics as closely as possible in the components of our tableau system. For instance, dynamic operations on Kripke models have counterpart dynamic relations between tableaux. -/- Soundness, completeness, and decidability are three of the most important properties that a proof system may have. A proof system is sound if and only if any formula for which a proof exists, is true in every model. A proof system is complete if and only if for any formula that is true in all models, a proof exists. A proof system is decidable if and only if any formula can be proved to be a theorem or not a theorem in a finite number of steps. All proof systems in this dissertation are sound, complete, and decidable. -/- Part of our strategy to create modular tableau systems is to delay concerns over decidability until after soundness and completeness have been established. Decidability is attained through the operations of folding and through operations on ‘tableau cascades’, which are graphs of tableaux. -/- Finally, we provide a proof-of-concept implementation of our dynamic tableau system for public announcement logic in the Clojure programming language. (shrink)

The fundamental relations in private law are claims and duties. These legal relations can be changed by agents with the appropriate legal powers. We use propositional dynamic logic and ideas about propositional control from the agency literature to formalize these changes in legal relations. Our models are sets of states with functions specifying atomic facts, agents’ abilities to change atomic facts, legal relations between agents concerning changing atomic facts and agents’ powers. We present a formal language that (...) allows us to describe models and changes of models caused by two kinds of actions: actions that change atomic facts and actions that change legal relations. Next, we present a sound and complete calculus for this language. The paper demonstrates that the perspective on actions borrowed from computer science can be used to shed interesting light on the dynamics of legal relations. (shrink)

This paper presents a calculus for mereotopological reasoning in which two-dimensional spatial regions are treated as primitive entities. A first order predicate language ℒ with a distinguished unary predicate c(x), function-symbols +, · and - and constants 0 and 1 is defined. An interpretation ℜ for ℒ is provided in which polygonal open subsets of the real plane serve as elements of the domain. Under this interpretation the predicate c(x) is read as 'region x is connected' and (...) the function-symbols and constants are given their meaning in terms of a Boolean algebra of polygons. We give an alternative interpretation ������ base on the real closed plane which turns out to be isomorphic to ℜ. A set of axioms and a rule of inference are introduced. We prove the soundness and completeness of the calculus with respect to the given interpretation. (shrink)

Qualitative description of the movement of objects can be very important when there are large quantity of data or incomplete information, such as in positioning technologies and movement of robots. We present a first step in the combination of fuzzy qualitative reasoning and quantitative data obtained by human interaction and external devices as GPS, in order to update and correct the qualitative information. We consider a Propositional Dynamic Logic which deals with qualitative velocity and enables us to (...) represent some reasoning tasks about qualitative properties. The use of logic provides a general framework which improves the capacity of reasoning. In this way, we can infer additional information by using axioms and the logic apparatus. In this paper we present sound and complete relational dual tableau that can be used for verification of validity of formulas of the logic in question. (shrink)

We consider substitutions in order sensitive situations, having in the back of our minds the case of dynamic predicate logic (DPL) with a stack semantics. We start from the semantic intuition that substitutions are move instructions on stacks: the syntactic operation [y/x] is matched by the instruction to move the value of the y-stack to the x-stack. We can describe these actions in the positive fragment of DPLE. Hence this fragment counts as a logic for DPL-substitutions. We give (...) a calculus for the fragment and prove soundness and completeness. (shrink)

Dynamic Topological Logic (DFH) is a multimodal system for reasoning about dynamical systems. It is defined semantically and, as such, most of the work done in the field has been model-theoretic. In particular, the problem of finding a complete axiomatization for the full language of DFH over the class of all dynamical systems has proven to be quite elusive. Here we propose to enrich the language to include a polyadic topological modality, originally introduced by Dawar and Otto (...) in a different context. We then provide a sound axiomatization for DFH over this extended language, and prove that it is complete. The polyadic modality is used in an essential way in our proof. (shrink)

This paper introduces a multi-agent dynamic epistemic logic for abstract argumentation. Its main motivation is to build a general framework for modelling the dynamics of a debate, which entails reasoning about goals, beliefs, as well as policies of communication and information update by the participants. After locating our proposal and introducing the relevant tools from abstract argumentation, we proceed to build a three-tiered logical approach. At the first level, we use the language of propositional logic to encode states (...) of a multi-agent debate. This language allows to specify which arguments any agent is aware of, as well as their subjective justification status. We then extend our language and semantics to that of epistemic logic, in order to model individuals’ beliefs about the state of the debate, which includes uncertainty about the information available to others. As a third step, we introduce a framework of dynamic epistemic logic and its semantics, which is essentially based on so-called event models with factual change. We provide completeness results for a number of systems and show how existing formalisms for argumentation dynamics and unquantified uncertainty can be reduced to their semantics. The resulting framework allows reasoning about subtle epistemic and argumentative updates—such as the effects of different levels of trust in a source—and more in general about the epistemic dimensions of strategic communication. (shrink)

We show the completeness of a Hilbert-style system LK defined by M. Valiev involving the knowledge operator K dedicated to the reasoning with incomplete information. The completeness proof uses a variant of Makinson's canonical model construction. Furthermore we prove that the theoremhood problem for LK is co-NP-complete, using techniques similar to those used to prove that the satisfiability problem for propositional S5 is NP-complete.

In this paper we introduce a formalism for single-agent decision making that is based on Dynamic Argumentation Frameworks. The formalism can be used to justify a choice, which is based on the current situation the agent is involved. Taking advantage of the inference mechanism of the argumentation formalism, it is possible to consider preference relations, and conflicts among the available alternatives for that reasoning. With this formalization, given a particular set of evidence, the justified conclusions supported by (...) warranted arguments will be used by the agent’s decision rules to determine which alternatives will be selected. We also present an algorithm that implements a choice function based on our formalization. Finally, we complete our presentation by introducing formal results that relate the proposed framework with approaches of classical decision theory. (shrink)

To reason about continuous processes in some areas of artificial intelligence and embedded systems one has to express real-time properties. For such purpose a real-time logic has to be considered. Various such logics have been proposed. Some of these formalisms interpret formulas over intervals of time. These are called interval logics. Zhou Chaochen and Michael Hansen have introduced one such first-order interval logic called Neighborhood Logic (NL) which has two expanding modalities ◊r and ◊l. They have shown the adequacy of (...) these modalities by deriving other unary and binary modalities from them; in particular, they show that chop can be expressed in terms of these modalities. The logic is subsequently expanded to get a Duration Calculus (called DC/nl) by expressing temporal variables as integrals of state variables. Liveness and fairness properties of a computing system can now be expressed in DC/nl by means of neighborhood (expanding) modalities. We take up an investigation of DC/nl in detail. We present a proof system for it. We further show that most of the results that hold in the original Duration Calculus continue to hold in our logic with some modifications. In this process we discuss soundness, completeness, and decidability results for DC/nl. Thus this paper establishes DC/nl as a useful formalism for specifying and verifying properties of real-time computing systems. (shrink)

With the inclusion of an e ective methodology, this article answers in detail a question that, for a quarter of a century, remained open despite intense study by various researchers. Is the formula XCB = e(x e(e(e(x y) e(z y)) z)) a single axiom for the classical equivalential calculus when the rules of inference consist of detachment (modus ponens) and substitution? Where the function e represents equivalence, this calculus can be axiomatized quite naturally with the formulas (...) (x x), e(e(x y) e(y x)), and e(e(x y) e(e(y z) e(x z))), which correspond to reexivity, symmetry, and transitivity, respectively. (We note that e(x x) is dependent on the other two axioms.) Heretofore, thirteen shortest single axioms for classical equivalence of length eleven had been discovered, and XCB was the only remaining formula of that length whose status was undetermined. To show that XCB is indeed such a single axiom, we focus on the rule of condensed detachment, a rule that captures detachment together with an appropriately general, but restricted, form of substitution. The proof we present in this paper consists of twenty- ve applications of condensed detachment, completing with the deduction of transitivity followed by a deduction of symmetry. We also discuss some factors that may explain in part why XCB resisted relinquishing its treasure for so long. Our approach relied on diverse strategies applied by the automated reasoning program OTTER. Thus ends the search for shortest single axioms for the equivalential calculus. (shrink)

The aim of this paper is to give new kinds of modal logics suitable for reasoning about regions in discrete spaces. We call them dynamic logics of the region-based theory of discrete spaces. These modal logics are linguistic restrictions of propositional dynamic logic with the global diamond E. Their formulas are equivalent to Boolean combinations of modal formulas like E(A ∧ ⟨α⟩ B) where A and B are Boolean terms and α is a relational term. Examining (...) what we can say about dynamic models when we use formulas to describe them, we successively address the axiomatization/completeness issue and the decidability/complexity issue of our dynamic logics of the region-based theory of discrete spaces. (shrink)

Some arguments use ‘generic’, or ‘typical’, objects. An explanation for this idea in terms of ‘almost all’ is suggested. The intuition of ‘almost all’ as ‘but for a few exceptions’ is rendered precise by means of ultrafilters. A logical system, with generalized quantifiers for ‘almost all’, is proposed as a basis for generic reasoning. This logic is monotonic, has a simple sound and complete deductive calculus, and is a conservative extension of classical first-order logic, with (...) which it shares several properties. For generic reasoning, generic individuals are introduced and internalized as generic constants, thereby producing conservative extensions where one can reason about generic objects as intended. A many-sorted version of this logic is introduced to handle distinct notions of ‘large’ subsets. Other possible applications for this logic are indicated. (shrink)

According to the standard definition, a first-order theory is categorical if all its models are isomorphic. The idea behind this definition obviously is that of capturing semantic notions in axiomatic terms: to be categorical is to be, in this respect, successful. Thus, for example, we may want to axiomatically delimit the concept of natural number, as it is given by the pre-theoretic semantic intuitions and reconstructed by the standard model. The well-known results state that this cannot be done within first-order (...) logic, but it can be done within second-order one. Now let us consider the following question: can we axiomatically capture the semantic concept of conjunction? Such question, to be sure, does not make sense within the standard framework: we cannot construe it as asking whether we can form a first-order (or, for that matter, whatever-order) theory with an extralogical binary propositional operator so that its only model (up to isomorphism) maps the operator on the intended binary truth-function. The obvious reason is that the framework of standard logic does not allow for extralogical constants of this type. But of course there is also a deeper reason: an existence of a constant with this semantics is presupposed by the very definition of the framework1. Hence the question about the axiomatic capturability of concunction, if we can make sense of it at all, cannot be asked within the framework of standard logic, we would have to go to a more abstract level. To be able to make sense of the question we would have to think about a propositional ‘proto-language’, with uninterpreted logical constants, and to try to search out axioms which would fix the denotations of the constants as the intended truth-functions. Can we do this? It might seem that the answer to this question is yielded by the completeness theorem for the standard propositional calculus: this theorem states that the axiomatic delimitation of the calculus and the semantic delimitation converge to the same result.. (shrink)

Graded epistemic logic is a logic for reasoning about uncertainties. Graded epistemic logic is interpreted on graded models. These models are generalizations of Kripke models. We obtain completeness of some graded epistemic logics. We further develop dynamic extensions of graded epistemic logics, along the framework of dynamic epistemic logic. We give an extension with public announcements, i.e., public events, and an extension with graded event models, a generalization also including nonpublic events. We present complete (...) axiomatizations for both logics. (shrink)

Probability plays an essential role in many branches of AI, where it is typically assumed that we have a complete probability distribution when addressing a problem. But this is unrealistic for problems of real-world complexity. Statistical investigation gives us knowledge of some probabilities, but we generally want to know many others that are not directly revealed by our data. For instance, we may know prob(P/Q) (the probability of P given Q) and prob(P/R), but what we really want is prob(P/Q&R), (...) and we may not have the data required to assess that directly. The probability calculus is of no help here. Given prob(P/Q) and prob(P/R), it is consistent with the probability calculus for prob(P/Q&R) to have any value between 0 and 1. Is there any way to make a reasonable estimate of the value of prob(P/Q&R)? A related problem occurs when probability practitioners adopt undefended assumptions of statistical independence simply on the basis of not seeing any connection between two propositions. This is common practice, but its justification has eluded probability theorists, and researchers are typically apologetic about making such assumptions. Is there any way to defend the practice? This paper shows that on a certain conception of probability — nomic probability — there are principles of “probable probabilities” that license inferences of the above sort. These are principles telling us that although certain inferences from probabilities to probabilities are not deductively valid, nevertheless the second-order probability of their yielding correct results is 1. This makes it defeasibly reasonable to make the inferences. Thus I argue that it is defeasibly reasonable to assume statistical independence when we have no information to the contrary. And I show that there is a function Y(r,s:a) such that if prob(P/Q) = r, prob(P/R) = s, and prob(P/U) = a (where U is our background knowledge) then it is defeasibly reasonable to expect that prob(P/Q&R) = Y(r,s:a).. (shrink)

Quasi-Boolean modal algebras are quasi-Boolean algebras with a modal operator satisfying the interaction axiom. Sequential quasi-Boolean modal logics and the relational semantics are introduced. Kripke-completeness for some quasi-Boolean modal logics is shown by the canonical model method. We show that every descriptive persistent quasi-Boolean modal logic is canonical. The finite model property of some quasi-Boolean modal logics is proved. A cut-free Gentzen sequent calculus for the minimal quasi-Boolean logic is developed and we show that it has the Craig (...) interpolation property. (shrink)

Non-determined game logic is the logic of two player board games where the game may end in a draw: unlike the case with determined games, a loss of one player does not necessarily constitute of a win of the other player. A calculus for non-determined game logic is given in [4] and shown to be complete. The calculus adds a new rule for the treatment of greatest fixpoints, and a new unfolding axiom for iterations of the (...) universal player. The technique of the completeness proof is inspired by the canonical model construction for propositional dynamic logic (PDL). In this paper, this is extended to the logic of determined games. It is proved that the calculus for nondetermined game logic, together with the axiom of determinacy, is complete for determined game logic. Next, it is shown that the axioms and rules of the new calculus can all be derived from the calculus proposed by Parikh in [5], for which the completeness was still open. This proves Parikh’s conjecture that his calculus is complete for determined games. (shrink)

Leibniz’s ‘new science of dynamics’ is typically taken to have been completed in the late monadological metaphysics. On this view, stemming from Martial Gueroult and continuing in the recent interpretations of Robert Adams and Pauline Phemister, Leibniz accomplished his dynamics in his later account of physical forces as merely phenomenal modifications of monadic, metaphysical forces. This paper argues, by contrast, that Leibniz considered the dynamics to be an unfinished project: this is evident in statements from throughout his mature period until (...) his final months. Two possible reasons for the non-completion of the dynamics are discussed. The first is that his encounter with the superior physics of Newton’s Principia caused Leibniz to continually defer his own contribution. I argue, however, in favour of a second reason: that there are philosophical difficulties inherent in the science of dynamics that prevented its completion. These difficulties are found in the relation of dynamics to metaphysics, and in the more fundamental split within dynamics, into the doctrine of primitive and derivative forces. Through three late exchanges with de Volder, Wolff and Des Bosses, I show that the relation of primitive and derivative forces remained an unsolved – although not in principle unsolvable – problem for Leibniz. (shrink)

Sound and complete axiomatizations are provided for a number of different logics involving modalities for the knowledge of multiple agents and operators for branching time, extending previous work of Halpern, van der Meyden and Vardi [to appear, SIAM Journal on Computing] for logics of knowledge and linear time. The paper considers the system constraints of synchrony, perfect recall and unique initial states, which give rise to interaction axioms. The language is based on the temporal logic CTL*, interpreted with (...) respect to a version of the bundle semantics. (shrink)

A first-order dynamic non-commutative logic, which has no structural rules and has some program operators, is introduced as a Gentzen-type sequent calculus. Decidability, cut-elimination and completeness theorems are shown for DN or its fragments. DN is intended to represent not only program-based, resource-sensitive, ordered, sequence-based, but also hierarchical reasoning.

We develop a vector space semantics for verb phrase ellipsis with anaphora using type-driven compositional distributional semantics based on the Lambek calculus with limited contraction of Jäger. Distributional semantics has a lot to say about the statistical collocation based meanings of content words, but provides little guidance on how to treat function words. Formal semantics on the other hand, has powerful mechanisms for dealing with relative pronouns, coordinators, and the like. Type-driven compositional distributional semantics brings (...) these two models together. We review previous compositional distributional models of relative pronouns, coordination and a restricted account of ellipsis in the DisCoCat framework of Coecke et al. :1079–1100, 2013). We show how DisCoCat cannot deal with general forms of ellipsis, which rely on copying of information, and develop a novel way of connecting typelogical grammar to distributional semantics by assigning vector interpretable lambda terms to derivations of LCC in the style of Muskens and Sadrzadeh Logical aspects of computational linguistics, Springer, Berlin, 2016). What follows is an account of ellipsis in which word meanings can be copied: the meaning of a sentence is now a program with non-linear access to individual word embeddings. We present the theoretical setting, work out examples, and demonstrate our results with a state of the art distributional model on an extended verb disambiguation dataset. (shrink)

The situation calculus is one of the most established formalisms for reasoning about action and change. In this paper we will review the basics of Reiter’s version of the situation calculus, show how knowledge and time have been addressed in this framework, and point to some of the weaknesses of the situation calculus with respect to time. We then present a modal version of the situation calculus where these problems can be overcome with (...) relative ease and without sacrificing the advantages of the original. (shrink)

ABSTRACT Two objects o1, o2 of an information system are said to be complementary with respect to attribute a if α(o1) = -α(o2), where α(o) is the set of values of attribute a assigned to o. They are said to be complementary with respect to a set of attributes A if they are complementary with respect to each attribute α ε A. A multi-modal logical language for reasoning about complementarity relations is presented, with modalities [A] (...) and ?A? parameterised by subsets of a given set ATTR of attributes. Two complete deduction system for the language are presented: a Rasiowa-Sikorski style system using signed formulae, and an equivalent sequent calculus system in Gentzen style complete for theories. (shrink)

We consider a simple modal logic whose nonmodal part has conjunction and disjunction as connectives and whose modalities come in adjoint pairs, but are not in general closure operators. Despite absence of negation and implication, and of axioms corresponding to the characteristic axioms of _T_, _S4_, and _S5_, such logics are useful, as shown in previous work by Baltag, Coecke, and the first author, for encoding and reasoning about information and misinformation in multiagent systems. For the propositional-only fragment of (...) such a dynamic epistemic logic, we present an algebraic semantics, using lattices with agent-indexed families of adjoint pairs of operators, and a cut-free sequent calculus. The calculus exploits operators on sequents, in the style of “nested” or “tree-sequent” calculi; cut-admissibility is shown by constructive syntactic methods. The applicability of the logic is illustrated by reasoning about the muddy children puzzle, for which the calculus is augmented with extra rules to express the facts of the muddy children scenario. (shrink)

All first-order Gödel logics G_V with globalization operator based on truth value sets V C [0,1] where 0 and 1 lie in the perfect kernel of V are axiomatized by Ciabattoni’s hypersequent calculus HGIF.

We present a completeness proof for Propositional Interval Temporal Logic with finite time which avoids certain difficulties of conventional methods. It is more gradated than previous efforts since we progressively reduce reasoning within the original logic to simpler reasoning in sublogics. Furthermore, our approach benefits from being less constructive since it is able to invoke certain theorems about regular languages over finite words without the need to explicitly describe the associated intricate proofs. A modified version of regular (...) expressions called Fusion Expressions is used as part of an intermediate logic called Fusion Logic. Both have the same expressiveness as PITL but are lower-level notations which play an important role in the hierarchical structure of the overall completeness proof. In particular, showing completeness for PITL is reduced to showing completeness for Fusion Logic. This in turn is shown to hold relative to completeness for conventional linear-time temporal logic with finite time. Logics based on regular languages over finite words and!-words offer a promising but elusive framework for formal specification and verification. A number of such logics and decision procedures have been proposed. In addition, various researchers have obtained complete axiom systems by embedding and expressing the decision procedures directly within the logics. The work described here contributes to this topic by showing how to exploit some interesting links between regular languages and interval-based temporal logics. (shrink)

Propositional dynamic logic (PDL) is one of the most successful variants of modal logic. To make it even more useful for applications, many extensions of PDL have been considered in the literature. A very natural and useful such extension is with negation of programs. Unfortunately, as long-known, reasoning with the resulting logic is undecidable. In this paper, we consider the extension of PDL with negation of atomic programs, only. We argue that this logic is still (...) useful, e.g. in the context of description logics, and prove that satisfiability is decidable and EXPTIME-complete using an approach based on Büchi tree automata. (shrink)

Richard Jeffrey developed the formula for probability kinematics with the intent that it would show that strong foundations are epistemologically unnecessary. But the reasons that support strong foundationalism are considerations of dynamics rather than kinematics. The strong foundationalist is concerned with the origin of epistemic force; showing how epistemic force is propagated therefore cannot undermine his position. The weakness of personalism is evident in the difficulty the personalist has in giving a principled answer to the question of when (...) the conditions for the application of the kinematic formula—the rigidity of the posteriors—are fulfilled, a problem made intractable by the personalist commitment to treating changes in intermediate probability as unexplained surds. Because the strong foundationalist admits changes in the intermediate probability of propositions only when there is some change in the foundations, he can avail himself of ananswer to the problem of the rigidity of the posteriors which the personalist cannot regard as complete. While probability kinematics does not make certain foundations unnecessary, the possession of certain foundations also does not make the probability kinematics formula superfluous. The formula allowsus to model the indirect routes by which the foundations influence various non-foundational propositions in the probability distribution. (shrink)

We introduce a family of tableau calculi for deontic action logics based on finite boolean algebras, these logics provide deontic operators which are applied to a finite number of actions ; furthermore, in these formalisms, actions can be combined by means of boolean operators, this provides an expressive algebra of actions. We define a tableau calculus for the basic logic and then we extend this calculus to cope with extant variations of this formalism; we prove the soundness (...) and completeness of these proof systems. In addition, we investigate the computational complexity of the satisfiability problem for DAL and its extensions; we show this problem is NP-complete when the number of actions considered is fixed, and it is \-Hard when the number of actions is taken as an extra parameter. The tableau systems introduced here can be implemented in PSPACE, this seems reasonable taking into consideration the computational complexity of the logics. (shrink)