We introduce a notion of bisimulation for graded modal logic. Using this notion, the model theory of graded modal logic can be developed in a uniform manner. We illustrate this by establishing the finite model property and proving invariance and definability results.

ABSTRACT We investigate a logic PFD, as introduced in [FA]. In our notation, this logic is enriched with operators P> r(r € [0,1]) where the intended meaning of P> r φ is “the probability of φ (at a given world) is strictly greater than r”. We also adopt the semantics of [FA]: a class of “F-restricted probabilistic kripkean models”. We give a completeness proof that essentially differs from that in [FA]: our “peremptory lemma” (a lemma in PFD rather than about (...) it) facilitates the construction of a canonical model for PFD considerably. We show that this construction can be carried out using only finitary means, and also give a filtration-technique for the intended models. We then define an alternative (in some sense more natural) semantics for the logic, and show some of its properties. Finally, we prove decidability of the logic. (shrink)

ABSTRACT Two models of the Aristotelian syllogistic in arithmetic of natural numbers are built as realizations of an old Leibniz idea. In the interpretation, called Scholastic, terms are replaced by integers greater than 1, and s.Ap is translated as “s is a divisor of p”, sIp as “g.c.d. > 1”. In the interpretation, called Leibnizian, terms are replaced by proper divisors of a special “Universe number” u < 1, and sAp is translated as “s is divisible by p”, sIp as (...) ‘l.c.m. < u”. Both interpretations are proved to be adequate to the Aristotelian syllogistic. They are extended to syllogistic including term negation and term conjunction as well. (shrink)

Some initial motivations for the Guarded Fragment still seem of interest in carrying its program further. First, we stress the equivalence between two perspectives: (a) satisfiability on standard models for guarded first-order formulas, and (b) satisfiability on general assignment models for arbitrary first-order formulas. In particular, we give a new straightforward reduction from the former notion to the latter. We also show how a perspective shift to general assignment models provides a new look at the fixed-point extension LFP(FO) of first-order (...) logic, making it decidable. Next, we relate guarded syntax to earlier quantifier restriction strategies for achieving effective axiomatizability in second-order logic – pointing at analogies with ‘persistent’ formulas, which are essentially in the Bounded Fragment of many-sorted first-order logic. Finally, we look at some further unexplored directions, including the systematic use of ‘quasi-models’ as a semantics by itself. (shrink)

Many of the formalisms used in Attribute Value grammar are notational variants of languages of propositional modal logic, and testing whether two Attribute Value Structures unify amounts to testing for modal satisfiability. In this paper we put this observation to work. We study the complexity of the satisfiability problem for nine modal languages which mirror different aspects of AVS description formalisms, including the ability to express re-entrancy, the ability to express generalisations, and the ability to express recursive constraints. Two main (...) techniques are used: either Kripke models with desirable properties are constructed, or modalities are used to simulate fragments of Propositional Dynamic Logic. Further possibilities for the application of modal logic in computational linguistics are noted. (shrink)

Adding certain cardinality quantifiers into first-order language will give substantially more expressive languages. Thus, many mathematical concepts beyond first-order logic can be handled. Since basic modal logic can be seen as the bisimular invariant fragment of first-order logic on the level of models, it has no ability to handle modally these mathematical concepts beyond first-order logic. By adding modalities regarding the cardinalities of successor states, we can, in principle, investigate modal logics of all cardinalities. Thus ways of exploring model-theoretic logics (...) can be transferred to modal logics. (shrink)

We introduce a notion of bisimulation for graded modal logic. Using this notion, the model theory of graded modal logic can be developed in a uniform manner. We illustrate this by establishing the finite model property and proving invariance and definability results.

We show that every modal logic (with arbitrary many modalities of arbitrary arity) can be seen as a multi-dimensional modal logic in the sense of Venema. This result shows that we can give every modal logic a uniform "concrete" semantics, as advocated by Henkin et al. This can also be obtained using the unravelling method described by de Rijke. The advantage of our construction is that the obtained class of frames is easily seen to be elementary and that the worlds (...) have a more uniform character. (shrink)

We give a condensed survey of recent research on generalized quantifiers in logic, linguistics and computer science, under the following headings: Logical definability and expressive power, Polyadic quantifiers and linguistic definability, Weak semantics and axiomatizability, Computational semantics, Quantifiers in dynamic settings, Quantifiers and modal logic, Proof theory of generalized quantifiers.

Adding certain cardinality quantifiers into first-order language will give substantially more expressive languages. Thus, many mathematical concepts beyond first-order logic can be handled. Since basic modal logic can be seen as the bisimular invariant fragment of first-order logic on the level of models, it has no ability to handle modally these mathematical concepts beyond first-order logic. By adding modalities regarding the cardinalities of successor states, we can, in principle, investigate modal logics of all cardinalities. Thus ways of exploring model-theoretic logics (...) can be transferred to modal logics. (shrink)

Modal logic with counting is obtained from basic modal logic by adding cardinality comparison formulas of the form $ \#\varphi \succsim \#\psi $, stating that the cardinality of successors satisfying $ \varphi $ is larger than or equal to the cardinality of successors satisfying $ \psi $. It is different from graded modal logic where basic modal logic is extended with formulas of the form $ \Diamond _{k}\varphi $ stating that there are at least $ k$-many different successors satisfying $ (...) \varphi $. In this paper, we investigate the axiomatization of ML(#) with respect to different frame classes, such as image-finite frames and arbitrary frames. Drawing inspiration from existing works, we employ a similar proof strategy that uses the characterization of binary relations on finite Boolean algebras capable of representing generalized probability measures or finite (respectively arbitrary) cardinality measures. Our main result shows that any formula not provable in the Hilbert system can be refuted within a finite (respectively arbitrary) cardinality measure Kripke frame with a finite domain. We then transform this finite (respectively arbitrary) cardinality measure Kripke frame into a Kripke frame in the corresponding class, refuting the unprovable formula. (shrink)