This course is an introduction
emphasizing major techniques,
and a small tour of modern
application areas for modal logic.
1 Basic Language and Expressive Power
This week introduces the
basic modal language, and its
evaluation in possible worlds models. This is a paradigm
for studying the diverse modal languages used in practice.
Expressive power is measured by the modern technique
of bisimulation invariance, also found in computer science.
We can think of bisimulation in terms of playing games,
a topic that will return in this course.
basic language and semantics
bisimulation and expressive power
2 Axiomatization and Complexity
Here we look at the Balance
found in any logical system.
Expressive power comes at a price in terms of complexity
for the basic tasks a logical system is used for, These are
semantical evaluation/model checking, valid reasoning/
SAT-testing, and model comparison for language equiva-
lence/structural similarity. This involves a brief excursion
into computational complexity, a whole topic by itself.
valid reasoning and axiomatics
complexity of logical tasks
We now turn our working analogy between modal operators
3 Translations and Extensions
and quantifiers into a systematic translation. This puts the
basic modal language inside a spectrum of much stronger
extended modal languages, with the decidable Guarded
of first-order logic near the top. The next
workshop on all matters
guarded is this summer. in Nancy
We have also looked at how extended modal languages
fare when we consider all our earlier topics: model checking,
bisimulation, minimal logic, complexity, and ST translation.
Finally, we have explored the border line with undecidability,
noting the non (pairwise-)guarded quantification needed to
express the 'grid structure' of the undecidable Tiling Problem.
4 Landscape of modal logics, frame correspondence
We first rehearsed earlier material, looking at evaluation games
Week 5 Recapitulation,
and temporal logic
for modal formulas, inductive decomposition of valid sequents,
some further examples of computing frame correspondence.
On Thursday, we looked at tense logic, with the basic language
as proposed by Prior, expressive power on frames (first-order
properties of linear orders, Dedekind completeness of the reals),
and then the Until/Since extension, explaining Kamp's Theorem
on expressive completeness for this language w.r.t. the full
first-order language over the reals and related linear orders.
Finally, we looked at modal-temporal models of branching time,
which seemed an appropriate setting for the day's closing event,
viz. the SSP Forum lecture "Is
the Future Unreal?" by John Perry.
Further material on temporal logic: see e.g., this survey
and the references therein, or look at this older monograph
with links to philosophy and linguistics.
Guest speaker Darko Sarenac. See also this seminar
Week 6 Modal Logics of Space
this Handbook page for
more material on modal logics
of topology and geometry.
We have done the basics on Tuesday and update on Thursday.
Week 7 Epistemic
logics of knowledge and update
See this text,
as well as the following papers (links to follow):
Update in Rotterdam,
is a Lonely Number.
Here is some material about propositional
Week 8 Dynamic
logics of action
And this is the key monograph
by three founding fathers.
You can look at the course homepage for Philosophy
Week 9 Games:
knowledge in action
On Tuesday, we did some basic modal structures in games:
action modalities, reasonign about strategies in dynamic logic,
Zermelo's Theorem and fixed-point definition for coloring algorithm,
epistemic-dynamic logic of games with imperfect information.
Thursday: special topic, modal
deconstruction of first-order logic.
Presentations take 15 minutes, with 5 minutes discussion.
Week 10 Student
presentations, two 2-hour sessions.
Tuesday June 1st, 11 AM - 1:15 PM, room
Thursday June 3d, 10 AM - 12:15 PM, room 160-326
Titles, and emails ifor people who want to request the paper:
Josh Snyder, Vagueness, Common Knowledge &
Public Announcements, firstname.lastname@example.org
Govind Persad, The STIT Operator: a modal representation
of agency, email@example.com
Dan Auerbach, Dynamic Doxastic Logic as a Model for
Public Key Protocols, firstname.lastname@example.org
Jonathan Lipps, Kripke's World: A Program that Tests
for Bisimulation, email@example.com
Renee Trochet, Defaults in Update Semantics,
Jonathan Frank, Epistemic Reasoning in Multi-Agent
Kim Diana Ly, First-Order and Second-Order Aspects of
Branching-Time Semantics', firstname.lastname@example.org
Gearhart, An Analysis of Knowledge-Based TCP,
Brett Lockspeiser,Possible Worlds,
Peter Lubell-Doughtree, Programming the Evaluation
Tyler Greene, Plethoric Epistemology,
The book "Manual of Intensional
Logic" provides general philosophical
background. It can be obtained
at CSLI's Publications Office.
But the self-
image of modal logicians
is shifting, and the course now takes a more
modern view of what makes
modal logic tick as a family of 'fine-structure
formalisms' striking a nice
balance between reasonable expressive
power and often decidable
computational complexity. See the recent
state-of-the-art new Textbook
Blackburn, de Rijke, and Venema,
or the new Handbook
of Modal Logic, under construction right now.
The following paper in the
volume "Companion to Philosophical Logic"
is a lightning
survey of this course. You may also want to look at some
sites. A nice source of illustrations for topics in the course
is the logic
page of Jan Jaspars in Amsterdam.
To be announced. You will
get weekly homework assignments
plus a final paper or presentation
1 This tests your understanding of (a) truth/expressive power
of modal formulas in models, and (b) the workings of bisimulation.
2 Simple formal proofs, arguments about modal validity,
and some impressionistic exercises in
3 Working with translations, and first-order fragments,
and understanding a few useful extended
4 Substitution method for computing first-order frame
correspondents, and analyzing non-first-order
5 Varia from the survey, and some temporal logic.
Week 6: you got spatial logic homework
from our guest speaker.
Weeks 7, 8, 9: combined
homework on epistemic logic,
dynamic logic & a bit of games: the