12/04 Lesson Plan
Modal Logic

So far we talked about logical encodings of various kinds of assertions about the
world -- e.g., it's raining, all birds fly, etc.

But language is much richer than that.  In English we can talk about the way the
people THINK about the world.  We can talk about morality, the way the world SHOULD
be.  We can distinguish things that are NECESSARILY true from things that just HAPPEN
to be true.  Consider the following:

The capital of Peru is Lima.
Mary knows the capital of Peru is Lima.
John believes the capital of Peru is Caraz.
It is necessarily the case that Peru is a country, 
	but not that its capital is Lima.
Eventually, the capital of Peru will be Caraz.
Official documents in Peru are all written in Spanish.
By law, official documents in Peru must be written in Spanish.

The first sentence is the kind of simple assertion we've been talking about in this
class.  We might represent it by capital(peru,lima).
What about the other sentences?

KNOWLEDGE
BELIEF
NECESSITY
EVENTUALITY
just a regular generalization
OBLIGATION --- note is not the same as necessity!

Can assertions ABOUT other assertions be written in FOL?  Consider:

capital(peru,lima) & knows(Mary, capital(peru,lima))

THIS IS NOT WELL FORMED IN FOL.  KNOWS must be a new kind of operator, that relates
an individual and a SENTENCE.  It is a MODAL OPERATOR.

There are many modal operators we might want to use.  Some have a single argument, a
sentence, while others take a sentence and an additional argument:
K(agent, sentence)
B(agent, sentence)
N sentence
E sentence
O sentence

CLASS EXERCISE: IN PAIRS, COME UP WITH OTHER EXAMPLES OF MODAL OPERATORS.
Examples: 
desire -- John hopes that the capital of Peru is Caraz.
communication -- John wrote that the capital of Peru is Caraz.
attitude -- John is unhappy that the capital of Person is Lima.
+ complements of the operators above

How can we REASON with modal sentences?  We'll do this by understanding what
inferences each kind of modality supports.  For example, consider:

(i) knows(Mary, capital(peru,lima)) v knows(Mary, capital(peru,caraz))

(ii) knows(Mary, capital(peru,lima) v capital(peru,caraz))

Should (i) entail (ii)?  YES.  Should (ii) entail (i)?  NO.

Why do we reason that (i) should entail (ii)?  Here's my pattern of reasoning, where
I reason by the two cases of (i):

From 
	knows(Mary, capital(peru,lima)) 
I conclude
	knows(Mary, capital(peru,lima) v capital(peru,caraz))
From 
	knows(Mary, capital(peru,lima)) 
I also conclude
	knows(Mary, capital(peru,lima) v capital(peru,caraz))
So, in either case I can conclude knows(Mary, capital(peru,lima) v capital(peru,caraz)).

So, the only non-FOL step was going from
	knows(Mary, capital(peru,lima)) 
to
	knows(Mary, capital(peru,lima) v capital(peru,caraz))

What is the justification for this step?  Well, we should be able to do ordinary
logical reasoning INSIDE of Mary's head!  We can capture this kind of reasoning by
ADDING AXIOM SCHEMA to ordinary propositional or FOL.

From now on, let's just write K for "Mary knows".

Here is one way of writing the axioim schemas we need:

Necessitation:     K P        for all tautologies (valid sentences) in FOL P
Distribution:      K (P => Q) => (KP => KQ)

So, let L be capital(peru,lima) and C be capital(peru,caraz).  We want to prove that

K L => K( L v C )

Proof:
(i)   L => (L v C)  is a tautology in propositional logic
(ii)  K (L => (L v C))    instance of Necessitation
(iii) K (L => (L v C)) => (K L => K (L v C))  instance of Distribution
(iv)  K L => K (L v C)     by modus ponens from (ii) and (iii)

Let's review where we are:
- A MODAL LOGIC extends propositional or FOL with MODAL operators.
- Because it extends "ordinary" logic, EVERY MODAL logic is closed under ordinary
logical inference where we treat everything inside a modal operator as an indivisible
unit.  EXPLAIN THIS MORE.
- For any particular Modal operator, we can add ADDITIONAL axioms to allow
reasoning about the sentences INSIDE the operator.
- For KNOWLEDGE, we should at least have the axiom schemas NECESSITATION and
DISTRIBUTION.

Every MODAL OPERATOR has a complement, ~OPERATOR~
Possibly P   =def  ~ Necessarily ~P

When we don't want to specify WHICH modal operator we are using, we will use
SQUARE and DIAMOND:

DIAMOND P  =def  ~ SQUARE ~ P

CLASS EXERCISE: What is the complement of each of the following modal operators?
Knowledge:    (epistemic possibility)
	How do I express complete ignorance of P?
	(~K P) & (~K~P)
	same as
        DIAMOND ~P   &   DIAMOND P
Obligation:   (permission)
Eventuality:  (always)

*************************
Normal systems == modal logics with NECC and DIST.
Are ALL modalities normal?
Maybe not, consider DESIRE -- dentist example.

But the OTHER operators we will talk about all do seem to be normal.

DISTINCTION B and K.
	KP => P
	but NOT
	P => KP   (unless P is a tautology!)

NESTED MODAL OPERATORS.
Class exercise:  WHAT ARE PRINCIPLES FOR REASONING WITH NESTED B?