Modal
Logic
This course is an introduction
emphasizing major techniques,
and a small tour of modern
application areas for modal logic.
Schedule
-
Week
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
-
Week
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
-
Week
3 Translations and Extensions
We now turn our working analogy between modal operators
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
Fragment GF
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.
-
Week
4 Landscape of modal logics, frame correspondence
-
Week 5 Recapitulation,
and temporal logic
We first rehearsed earlier material, looking at evaluation games
for modal formulas, inductive decomposition of valid sequents,
and
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
article,
and the references therein, or look at this older monograph
with links to philosophy and linguistics.
-
Week 6 Modal Logics of Space
Guest speaker Darko Sarenac. See also this seminar
page
and
this Handbook page for
more material on modal logics
of topology and geometry.
-
Week 7 Epistemic
logics of knowledge and update
We have done the basics on Tuesday and update on Thursday.
See this text,
as well as the following papers (links to follow):
Update in Rotterdam,
One
is a Lonely Number.
-
Week 8 Dynamic
logics of action
Here is some material about propositional
dynamic logic.
And this is the key monograph
by three founding fathers.
-
Week 9 Games:
knowledge in action
You can look at the course homepage for Philosophy
298.
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.
-
Week 10 Student
presentations, two 2-hour sessions.
Presentations take 15 minutes, with 5 minutes discussion.
Tuesday June 1st, 11 AM - 1:15 PM, room
200-305
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, jj@stanford.edu
Govind Persad, The STIT Operator: a modal representation
of agency, gpersad@stanford.edu
Dan Auerbach, Dynamic Doxastic Logic as a Model for
Public Key Protocols, dan06@stanford.edu
Jonathan Lipps, Kripke's World: A Program that Tests
for Bisimulation, jon832@stanford.edu
Renee Trochet, Defaults in Update Semantics,
rtrochet@stanford.edu
Jonathan Frank, Epistemic Reasoning in Multi-Agent
Systems, jonfrank@stanford.edu
Kim Diana Ly, First-Order and Second-Order Aspects of
Branching-Time Semantics', kly@stanford.edu
Chris
Gearhart, An Analysis of Knowledge-Based TCP,
cmg33@stanford.edu
Brett Lockspeiser,Possible Worlds,
blocks@stanford.edu
Peter Lubell-Doughtree, Programming the Evaluation
Game, pld@stanford.edu
Tyler Greene, Plethoric Epistemology,
tylergreene@stanford.edu
Course materials
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
by
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
conference
sites. A nice source of illustrations for topics in the course
is the logic
animations
page of Jan Jaspars in Amsterdam.
Practical things
To be announced. You will
get weekly homework assignments
plus a final paper or presentation
assignment.
Homework
Week
1 This tests your understanding of (a) truth/expressive power
of modal formulas in models, and (b) the workings of bisimulation.
Week
2 Simple formal proofs, arguments about modal validity,
and some impressionistic exercises in
complexity analysis.
Week
3 Working with translations, and first-order fragments,
and understanding a few useful extended
modal languages.
Week
4 Substitution method for computing first-order frame
correspondents, and analyzing non-first-order
modal axioms.
Week
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
final one!
|