CS206 Lecture 21

Modal Logic
Home Page

Title Page

Contents
G. Sivakumar
Computer Science Department

JJ II IIT Bombay

siva@[Link]
J I [Link]

Page 1 of 17
Thu, Mar 13, 2003

Go Back

Full Screen
Plan for Lecture 21
Close
• Modal Logic
Quit
• Possible World Semantics
 Modal Logic
• FOL is a big improvement over PL in terms of expressive power
Home Page
• But, there are many arguments that cannot be expressed in FOL.

Title Page
• Many facts in real world are dynamic and their truth is a relative notion.
Contents Consider the following.

• Either it rains or it does not rain.

JJ II

• It may rain today.

J I
• It rains sometimes.

Page 2 of 17
• It always ooded after every rains.

Go Back
•I believe that I may be wrong.

•I believe that Ram knows that I know that he did it.

Full Screen

The rst statement is true absolutely in all situations, at all places and at
Close all times. The truth value of the rest depends on the place, time and the

judgment of the person who uttered it.

Quit
 Bindi Puzzle
A mother wishes to test her three daughters. She arranges them
Home Page
in a circle so that they can see and hear each other and tells them

that she will put a white or black bindi on each of their foreheads
Title Page
but that at least one bindi will be white. In fact all three bindis are

Contents
white. She then repeatedly asks them, Do you know the color of

your bindi? What do they answer?

JJ II

J I

Page 3 of 17

Go Back

Full Screen

Close

Quit
 Sum and Product Puzzle
Two numbers m and n are chosen such that 2 ≤ m, n ≤ 99. Mr.
Home Page
S is told their sum and Mr. P is told their product. The following

dialogue ensues:
Title Page

• Mr. P: I don't know the numbers.

Contents
• Mr. S: I knew you didn't know. I don't know either.

JJ II
• Mr. P: Now I know the numbers.

• Mr S: Now I know them too.

J I
So, do you know the numbers now?

Page 4 of 17

Go Back

Full Screen

Close

Quit
 Another Example
Consider an island starting initially with n male rabbits and n female rab-
Home Page
bits. Assume the following things can happen any time.

Title Page •2 males can ght with each other and one dies.

•A male and a female can produce one of the following litters

Contents

 1 male and 2 female

JJ II
 1 male and 1 female
J I
 2 females
• An (old?) couple (1 male and 1 female) commit suicide together.
Page 5 of 17

Can translate above easily into some problem on vlaues of variables in a

Go Back program (but that takes away the fun?)

Full Screen

Close

Quit
 Possible Scenarios (Worlds)
Home Page

Title Page

Contents

JJ II

J I

Page 6 of 17

Go Back

Full Screen

Close

Quit
 Some Theorems
How can we state and prove/refute the following?
Home Page
• There will always be at least as many females as males.

Title Page
• Whenever there is at least one male left, it is possible for the entire

species to become extinct.

Contents

• So long as at least one male and one female survive, it is possible that
JJ II the number of males will become a prime number and the number of

females will be twice this.

J I
• ...
Page 7 of 17
Which ones are

Go Back • Necessary Truths?

Full Screen
• Possible Truths?

Close

Quit
 MODAL LOGIC
Modal logics have been developed precisely to express these kinds of state-
Home Page
ments. Modal logic once a subject of philosophy, has now become a branch

of mathematical logic. Nowadays computer scientists use modal logic to

Title Page
reason about knowledge, time, beliefs and proof theory. The simplicity,

Contents
elegance and power of modal logic can be best seen in its application in

reasoning about proofs, where it throws light on Gödel's theorems.

JJ II Modal logic is an extension of propositional logic by introducing modalities

on propositions: instead of a proposition being merely just true or false,

J I
it may in addition be necessarily true or possibly true. This investigation

was largely conned to the domain of philosophical logic. However in

Page 8 of 17
the 1950s Kripke gave precise mathematical meanings to the notions of

Go Back
modality in terms of possible world models and brought it in the domain

of mathematics. Besides having precise syntax and semantics, the logic

Full Screen was shown to have several applications by appropriately interpreting the

modalities.
Close

Quit
 Modalities
The two modalities necessity and and its dual possibility can qualify for-
Home Page
mulae with several useful interpretations:
Logic  (G) ♦ (F)
Title Page
Modal Necessary Possible

Epemistic Knowledge Belief

Contents

Deontic Obligation Permitted

JJ II Proof Theory Provable Consistent

Temporal Always Sometimes

J I

Page 9 of 17

Go Back

Full Screen

Close

Quit
 Can we do all this in
Home Page First-order logic?
It is possible to do some modal logic in FOL by means of interpretations.
Title Page
For example, by using the natural numbers to represent the time points

Contents and using predicates to assert their truth values at dierent time points.

However, the modalities let us get down directly to the issues of temporal
JJ II properties, instead of rst having to dene the properties of time points

using the axiomatization of natural numbers.

J I
Hence the modalities let us concentrate on the issues at hand, and we need

to only dene the properties of the modalities.

Page 10 of 17

Go Back

Full Screen

Close

Quit
 Duality
Home Page
φ ↔ ¬♦¬φ
Title Page

♦φ ↔ ¬¬φ
Contents

Example:
JJ II
• It sometimes rains.

J I • It is not the case that it is always dry.

Page 11 of 17
♦Rain ↔ ¬¬Rain
Go Back

Full Screen

Close

Quit
 Examples of Modalities in Use
•I believe `2 + 2 = 4' is true: B(2 + 2 = 4).
Home Page
• It always rains and sometimes oods here: Rain ∧ ♦f lood.
Title Page
• The formula φ is neither provable nor refutable: ¬(φ) ∧ ¬¬φ.
Contents • It is possible that he knows that φ is true: ♦Kφ.

JJ II

J I

Page 12 of 17

Go Back

Full Screen

Close

Quit
 Possible Worlds semantics
In philosophical logic, the notion of absolute truth of a proposition was
Home Page
replaced by the notion of truth with respect to the world where it was

uttered. It envisaged a set of worlds related to each other. A proposition

Title Page
was necessarily true in a world if it was true in every world related to that

Contents
world, and possibly true in it if it was true in at least one world related to

it.
JJ II

J I

Page 13 of 17

Go Back

Full Screen

Close

Quit
 The syntax
The language of propositional modal logic consists of logical and nonlogical
Home Page
symbols. The nonlogical symbols are a set of propositions which assert facts

about the world.

The Alphabet
Title Page

Contents • The truth constants: true ( T ), false ( F );

JJ II
• The usual propositional connectives: conjunction (∧), disjunction (∨),
implication (→), if and only (↔), negation (¬);
J I
• And the modal operators: necessarily () and possibly (♦).
Page 14 of 17

Go Back

Full Screen

Close

Quit
 Well formed formulae
The set of ws is given by applying the following rules any number of times:
Home Page
1. Every proposition is a ws

Title Page
2. If φ and ψ are ws then so are the following.

Contents • φ∧ψ
• φ∨ψ
JJ II
•φ→ψ
J I • ¬φ
• φ
Page 15 of 17
• ♦φ
Go Back

Full Screen

Close

Quit
 Truth of formulae
Every formula must be either true or false in any given situation ( model ).
Home Page
Moreover the truth value is meaningfully assigned: for example, if both φ
and ψ are assigned T , then (φ∧ψ) will also be assigned T . Using possible
Title Page
world as our basic model, truth value can be assigned to every formula of

Contents
modal logic.

A possible world model consist of a set worlds, a binary (accessibility)

JJ II relation between the worlds, and truth assignments to the propositions in

every world. The formula ∀φ is true in a world w, if and only if φ is true

J I
in all worlds related to w. Whereas its dual formula ∃φ is true in a world

w, if and only if φ is true in some (at least one) world related to w.

Page 16 of 17

Go Back

Full Screen

Close

Quit
 Example of a Model
w1 w2

Home Page
p - q
#
6
Title Page
w3 ? ? "!

Contents p, q

JJ II

J I
There are three possible worlds:w1 , w2 andw3. Proposition p is true in w1
and w3. Proposition q is true in w2 and w3. The accessibility relation R
Page 17 of 17
is:

Go Back R(w1, w2), R(w1, w3), R(w2, w2), R(w2, w3), R(w3, w2).
Then the following modal formulae are true in the given world:
Full Screen
w1 q, q, ♦p, ♦¬p.
Close w2 q, ♦p, ♦¬p.
w3 q, ¬p, ♦q.
Quit