Exercises: Normative Reasoning and Deontic Logics
Table of Contents
- General Info
- Session 1: Introducing Modal Logic and some Reminders on Set Theory
- Session 2
- Session 3: Von Wright 1951
- Session 4: Distribution and Scopes
- Session: Conditional Obligations
- Sessions: Horty and his Default Model for Conditional Obligations with Priorities; McNamara and the Supererogatory (Fri)
back to the main course page
General Info
Change Log
- Session 1 added
Course
Course: | Normative Reasoning and Deontic Logics |
Organised by: | Christian Straßer, GA 3/39, 0234/3224721 |
Speaking hours: | Wednesdays from 10:00–12:00 |
When: | every Thursday from 12:00 to 14:00, , Summer term 2015 |
Where: | GABF 04 / 609 |
More information on the course can be found here.
Notation
A note on the way we use the formal language:
Modal operators bind stronger than the classical connectives \(\wedge, \vee, \neg, \rightarrow\). In view of this we can write \(\Box A \wedge \Diamond B\) instead of \((\Box A) \wedge \Diamond B\).
Session 1: Introducing Modal Logic and some Reminders on Set Theory
To be discussed at
.Let \(M = \langle W, R, v\rangle\) be an arbitrary Kripke-model as defined on slide 3.
Task 1: Kripke Models
- Discussed at .
Show: $$M,w \models \Box(A \wedge B) \mbox{ implies } M,w \models \Box A \wedge \Box B$$
Recall the following:
- \(M, w \models \Box A\) iff for all \(w' \in W\) for which \((w, w') \in R\), \(M,w' \models A\).
- \(M, w \models A \wedge B\) iff \(M,w \models A\) and \(M,w \models B\).
The proof goes as follows:
- We suppose that \(M,w \models \Box(A \wedge B)\) for some Kripke-model \(M = \langle W, R, v\rangle\) where \(w \in W\).
- By 1, this means that for all \(w' \in W\) for which \((w,w') \in R\), \(M,w' \models A \wedge B\).
- By 2, this means that for all \(w' \in W\) for which \((w,w') \in R\), \(M, w' \models A\) and \(M,w' \models B\).
- By 1, this means that \(M,w \models \Box A\) and \(M,w \models \Box B\).
- By 2, this means that \(M,w \models \Box A \wedge \Box B\).
Here's an alternative proof:
- We suppose that \(M,w \models \Box(A \wedge B)\) for some Kripke-model \(M = \langle W, R, v\rangle\) where \(w \in W\).
- If there are no accessible worlds from \(w\) then \(M,w \models \Box A\) and \(M,w \models \Box B\) by 1. By 2, \(M,w \models \Box A \wedge \Box B\).
- If there are accessible worlds from \(w\) choose an arbitrary \(w' \in W\) for which \((w,w') \in R\).
- By 1, \(M,w' \models A \wedge B\).
- By 2, \(M,w' \models A\) and \(M,w' \models B\).
- Since \(w'\) is an arbitrary accessible world from \(w\), by 1, \(M,w \models \Box A\) and \(M,w \models \Box B\).
- By 2, \(M,w \models \Box A \wedge \Box B\).
Task 2: Kripke Models
- Discussed at .
Show: $$M,w \models \Box A \mbox{ and } M,w \models \Box B \mbox{ implies } M,w \models \Box(A \wedge B)$$
Recall items 1 and 2 in the solution of Task 1. The proof goes as follows:
- We suppose \(M \models \Box A\) and \(M \models \Box B\) for some Kripke-model \(M = \langle W, R, v \rangle\) where \(w \in W\).
- By 1, for all \(w' \in W\) for which \((w,w') \in R\), \(M,w' \models A\) and \(M,w' \models B\).
- By 2, for all \(w' \in W\) for which \((w,w') \in R\), \(M,w' \models A \wedge B\).
- By 1, \(M,w \models \Box(A \wedge B)\).
Task 3: Kripke Models
- Discussed at .
Do you think the following holds: $$M, w \models \Diamond (A \vee B) \mbox{ implies } M,w \models \neg \Box (\neg A \wedge \neg B)$$
Give a reason.
We first suppose that \(\Diamond\) is characterised by:
- \(M,w \models \Diamond A\) iff there is a world \(w' \in W\) for which \((w,w')\in R\) and \(M,w' \models A\).
Recall also:
- \(M,w \models \neg A\) iff \(M,w \not\models A\)
- \(M, w \models A \vee B\) iff \(M,w \models A\) or \(M,w \models B\)
- \(M,w \models A \wedge B\) iff \(M,w \models A\) and \(M,w \models B\)
The proof goes as follows:
- Suppose \(M,w \models \Diamond(A \vee B)\) where \(M = \langle W, R, v\rangle\) is some Kripke-model and \(w \in W\).
- By 1, there is a \(w' \in W\) for which \((w, w') \in R\) and \(M,w' \models A \vee B\).
- By 3, \(M,w' \models A\) or \(M,w' \models B\).
- By 2, \(M,w' \not\models \neg A\) or \(M,w' \not\models \neg B\).
- By 4, \(M,w' \not\models \neg A \wedge \neg B\).
- By 1, \(M,w \not\models \Box(\neg A \wedge \neg B)\).
Now suppose \(\Diamond\) is defined by \(\neg\Box\neg\).
Note that the following are equivalent:
- \(M,w \models \Diamond A\)
- \(M,w \models \neg \Box \neg A\)
- \(M,w \not\models \Box \neg A\)
- not(for all \(w' \in W\) for which \((w, w') \in R\), \(M,w' \models \neg A\))
- not(for all \(w' \in W\) for which \((w, w') \in R\), \(M,w' \not\models A\))
- there is a \(w' \in W\) for which \((w, w') \in R\) and \(M,w'\models A\)
This means that \(M,w \models \Diamond A\) iff there is a \(w' \in W\) for which \((w, w') \in R\) and \(M,w'\models A\) — just as in 1. So the proof of our statement is the same in case \(\Diamond\) is defined by \(\neg \Box \neg\).
Task 4: Epistemic Logic
- Discussed at .
In a branch of epistemic logic \(\Box\) models 'I know'. Epistemic introspection says that when an agent knows \(A\) then the agent knows that she knows \(A\).
- How would you express introspection formally?
- Does introspection hold in arbitrary Kripkean models? Give a reason.
- By \(\Box A \supset \Box \Box A\).
- No. The following model \(M\) is a counter-model for \(A = p\) (i.e., \(M \not \models \Box p \supset \Box \Box p\)): \(M = \langle \{w_1, w_2, w_3\}, R, v\rangle\) where \(R = \{(w_1, w_2), (w_2, w_3)\}\) and \(v(w_1) = \{p\} = v(w_2)\) while \(v(w_3) = \emptyset\). Clearly, \(M,w_1 \models \Box p\) while \(M,w_1 \not\models \Box\Box p\) since \(M,w_3 \not\models p\).
In the class we also discussed that a requirement on the accessibility relation of Kripke-models that makes sure that epistemic introspection holds is: \(R\) is reflexive (\(R\) is reflexive iff for all \(w \in W\), \((w,w) \in R\)).
Task 5: Deontic Logic
- Discussed at .
A principle in deontic logic says that obligations should imply permissions.
- How would you express this principle formally where the \(\Box\) is written \({\sf O}\) while the diamond is written \({\sf P}\).
- Are there Kripkean models that do not validate this principle? Give a reason.
- \({\sf O}A \supset {\sf P}A\)
- Yes. Take \(M = \langle \{w\}, R, v\rangle\) where \(R = \emptyset\) and \(v\) may be arbitrary (e.g., \(v(w) = \emptyset\)) and let \(A = p\) (where \(p\) is some propositional atom). We have
- \(M \models {\sf O}A\) since \(M,w \models {\sf O} A\) (note, \(w\) is the only world in \(M\)) since there are no accessible worlds from \(w\).
- But \(M \not\models {\sf P}A\) since there is no accessible world from \(w\) in which \(A\) holds (\(M,w \not\models {\sf P} A\)).
The restriction on the accessibility relation that ensures \({\sf O} A \supset {\sf P} A\) is called seriality. It goes as follows: \(R \subseteq W \times W\) is serial iff for all \(w \in W\) there is a \(w' \in W\) such that \((w,w') \in R\) (note that it may be that \(w = w'\)).
Caution: seriality is different from reflexivity, while reflexivity implies seriality, this does not hold the other way around.
Task 6: Set Theory
- Discussed at .
- \(\{1,3,5,6\} \cap \{1,4,6\} = \mbox{?}\)
- \(\{1,3,5,6\} \cup \{1,4,6\} = \mbox{?}\)
- \(\{1,4,6\} \subseteq \{1,3,5,6\}\mbox{?}\)
- Let \(A = \{1,3\}\) and \(B = \{2,3\}\). Write down all elements of \(A \times B\).
- \(\{1,3,5,6\} \cap \{1,4,6\} = \{1.6\}\)
- \(\{1,3,5,6\} \cup \{1,4,6\} = \{1,3,4,5,6\}\)
- \(\{1,4,6\} \not\subseteq \{1,3,5,6\}\) since \(4\) is in the former but not in the latter set.
- \(A \times B = \{(1,2), (1,3), (3,2), (3,3)\}\)
#+end_{solution}
Task 7: Naive Set Theory and Self-reference (for the courageous)
- Discussed at .
According to contemporary mathematical orthodoxy we do not refer allow for sets such as the following:
Let \(R\) be the set of all sets \(X\) that are not element of themselves (\(X \notin X\)).
The reason is that that the following question leads to paradox: Does \(R\) contain itself?
Demonstrate the paradox.
- We can write \(R = \{ X \mid X \notin X\}\).
- Suppose \(R \in R\). Then \(R \notin R\) by the definition of \(R\). Contradiction.
- Suppose \(R \notin R\). Then \(R \in R\) by the definition of \(R\). Contradiction.
Note: This paradox is well-known as the Russell-Paradox since it goes back to Betrand Russell (1901). (However, it was also discovered at a similar time by Ernst Zermelo.) In contemporary set theory (which goes back to the work of Zermelo and Fraenkel: it's called Zermelo-Fraenkel set theory) sets like \(R\) are not allowed.
Session 2
To be discussed on
.Task 1
- Discussed at .
Let \(M = \langle \{w_1, w_2, w_3 \}, R, v\rangle\) be a Kripke-model where
- \(R = \{ (w_1, w_1), (w_1, w_2), (w_2, w_3), (w_3, w_2), (w_3, w_3) \}\)
- \(v(w_1) = \{p\}\), \(v(w_2) = \{p\}, v(w_3) = \{q\}\)
Does the following hold? Give reasons.
- \(M \models \Diamond p\)
- \(M \models \Box p\)
- \(M \models \Box(p \vee q)\)
- \(M \models \neg q \supset \Diamond \Diamond q\)
- This does not hold since \(M,w_2 \not\models \Diamond p\).
- This does not hold since \(M,w_2 \not\models \Box p\).
- This holds since \(M,w_i \models \Box(p\vee q)\) for all \(i \in \{1,2,3\}\).
- This holds since \(M,w_i \models \neg q \supset \Diamond \Diamond q\) for all \(i \in \{1,2,3\}\).
Task 2
- Discussed at .
Does the following hold in all Kripke-models: $$\Diamond p \supset \Box \Diamond p$$
Give a reason. If your answer is negative, give a counter-model (a model \(M\) for which \(M \not \models \Diamond p \supset \Box \Diamond p\)). In that case, also indicate what requirement we need for the accessibility relation so that every model that fulfils the respective requirement also models the formula in question.
No, it doesn't hold in all Kripke-models. Take \(M = \langle \{w_1, w_2\}, R, v\rangle\) where
- \(R = \{(w_1, w_2)\}\) and \(v(w_i) = \{p\}\) where \(i \in \{1,2\}\).
Note that \(M,w_1 \models \Diamond p\) but \(M,w_1 \not\models \Box\Diamond p\) since \(M,w_2 \not\models \Diamond p\).
Task 3
- Discussed at .
Given any Kripke-model \(M = \langle W, R, v\rangle\). Show that $$M \models A$$ implies $$M \models \Box A$$ where \(M \models A\) is defined by \(M,w \models A\) for all \(w \in W\).
- Suppose \(M\models A\).
- Hence, \(M,w \models A\) for all \(w \in W\).
- Now let \(w \in W\) arbitrary. Then \(M,w \models \Box A\) since for all \(w' \in W\) for which \((w,w') \in R\), \(M,w' \models A\). (Recall here that 'for all' does not imply that there are any accessible worlds. But in case there are no accessible worlds to \(w\), we also get \(M,w \models \Box A\).)
- Hence, for all \(w \in W\), \(M,w \models \Box A\).
- Thus, \(M \models \Box A\).
Session 3: Von Wright 1951
Perfect disjunctive normal form
Von Wright talks in his seminal article often about perfect disjunctive normal forms. You may wonder how to construct one, since he doesn't give us any instruction.
A way to construct a perfect disjunctive normal form is by means of inspecting the truth-table of a formula. We first consider the case of formulas without modal operators.
Take the formula \((p \wedge q) \supset (\neg q \vee \neg p)\).
We have the following truth table:
\(p\) | \(q\) | \(p \wedge q\) | \(\neg q \vee \neg p\) | \((p \wedge q) \supset (\neg q \vee \neg p)\) | ||
---|---|---|---|---|---|---|
0 | 0 | 0 | 1 | 1 | ||
0 | 1 | 0 | 1 | 1 | ||
1 | 0 | 0 | 1 | 1 | ||
1 | 1 | 1 | 0 | 0 |
Now inspect where we have a truth-value one for the complex formula in question:
\(p\) | \(q\) | \(p \wedge q\) | \(\neg q \vee \neg p\) | \((p \wedge q) \supset (\neg q \vee \neg p)\) | ||
---|---|---|---|---|---|---|
0 | 0 | 0 | 1 | 1 | ||
0 | 1 | 0 | 1 | 1 | ||
1 | 0 | 0 | 1 | 1 | ||
1 | 1 | 1 | 0 | 0 |
For each such line form a conjunction of the corresponding atoms in the following way: for each atom check whether its truth value is 0 or 1. If it is 1, add the atom. If it is 0, add the negation of the atom.
We get:
- line 1: \(\neg p \wedge \neg q\)
- line 2: \(\neg p \wedge q\)
- line 3: \(p \wedge \neg q\)
Now form a disjunction of the obtained conjunctive clauses:
- \((\neg p \wedge \neg q) \vee (\neg p \wedge q) \vee (p \wedge \neg q)\).
This is the perfect disjunctive normal form. (Try to understand why this procedure works!)
Task 1
- Discussed at .
- State the perfect disjunctive normal form of \((p \vee q) \wedge (\neg p \vee \neg q)\).
- What are the \(P\)-constituents of \((p \vee q) \wedge (\neg p \vee \neg q)\)?
Solution
The truth table is as follows:
\(p\) | \(q\) | \(p \vee q\) | \(\neg p \vee \neg q\) | \((p \vee q) \wedge (\neg p \vee \neg q)\) | ||
---|---|---|---|---|---|---|
0 | 0 | 0 | 1 | 0 | ||
0 | 1 | 1 | 1 | 1 | ||
1 | 0 | 1 | 1 | 1 | ||
1 | 1 | 1 | 0 | 0 |
Hence we get \((\neg p \wedge q) \vee (p \wedge \neg q)\).
Task 2
- Discussed at .
- State the perfect disjunctive normal form of \(p \supset \neg p\).
- What are the \(P\)-constituents of \(p \supset \neg p\)?
Solution
The truth table is as follows:
\(p\) | \(p \supset \neg p\) | |
---|---|---|
0 | 1 | |
1 | 0 |
Hence we get \(\neg p\).
Task 3
- Discussed at .
- State the perfect disjunctive normal form of \((p \wedge q) \supset r\).
- What are the \(P\)-constituents of \((p \wedge q) \supset r\)?
Solution
The truth table is as follows:
\(p\) | \(q\) | \(r\) | \((p \wedge q)\) | \(r\) | \((p \wedge q) \supset r\) | ||
---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 1 | ||
0 | 0 | 1 | 0 | 1 | 1 | ||
0 | 1 | 0 | 0 | 0 | 1 | ||
0 | 1 | 1 | 0 | 1 | 1 | ||
1 | 0 | 0 | 0 | 0 | 1 | ||
1 | 0 | 1 | 0 | 1 | 1 | ||
1 | 1 | 0 | 1 | 0 | 0 | ||
1 | 1 | 1 | 1 | 1 | 1 |
Hence we have the following lengthy perfect disjunctive normal form: $$(\neg p \wedge \neg q \wedge \neg r) \wedge (\neg p \wedge \neg q \wedge r) \wedge (\neg p \wedge q \wedge \neg r) \wedge (\neg p \wedge q \wedge r) \wedge (p \wedge \neg q \wedge \neg r) \wedge (p \wedge \neg q \wedge r) \wedge (p \wedge q \wedge r)$$
Decision Procedure for Von Wright's Deontic Logic from 1951
On pages 11–12 Von Wright gives a decision procedure for deontic formulas. Here's how it works.
- Replace each \(O\) by \(\neg P\neg\).
- Replace each \(P(\ldots)\) by
- a disjunction of its \(P\)-constituents (here's where you need perfect disjunctive normal forms!) if there are any,
- if there are none replace \(P(\ldots)\) by \(P(A \wedge \neg A)\) for some atom \(A\) that occurs in \(P(\ldots)\) (this is not mentioned by Von Wright, but sometimes necessary because some formulas do not have any \(P\)-constituents, see task 6 below)
- Make the truth-table where the left columns are occupied by the previously obtained \(P\)-constituents
- If in the last column you only get 1s, then the formula is a tautology.
His example is as follows:
0 | \(OA\) | \(\wedge\) | \(O(A \supset B)\) | \(\supset\) | \(OB\) |
1 | \(\neg P\neg A\) | \(\wedge\) | \(\neg P \neg(A \supset B)\) | \(\supset\) | \(\neg P \neg B\) |
2 | \(\neg (P(\neg A \wedge B) \vee P(\neg A \wedge \neg B))\) | \(\wedge\) | \(\neg P(A \wedge \neg B)\) | \(\supset\) | \(\neg (P(A \wedge \neg B) \vee P(\neg A \wedge \neg B))\) |
- At line 0 we have to formula for which we want to check whether it is a tautology.
- At line 1 we perform step 1.
- At line 2 we perform step 2.
The following are the \(P\)-constituents of the formula at line 0:
- \(P(\neg A \wedge B)\)
- \(P(\neg A \wedge \neg B)\)
- \(P(A \wedge \neg B)\)
Now we form the table on page 12:
Since in the last column there are only 1s, we have a tautology.
Task 4
- Discussed at .
In the left columns of the table there is no need to state also one column for \(P(A \wedge B)\). Why do you think this is so?
Task 5
- Discussed at .
Is \(O(A \vee B) \supset OA\) a tautology? Use Von Wright's decision procedure to answer the question.
Solution
0 | \(O(A \vee B)\) | \(\supset\) | \(OA\) |
1 | \(\neg P \neg(A \vee B)\) | \(\supset\) | \(\neg P \neg A\) |
2 | \(\neg( P(\neg A \wedge \neg B))\) | \(\supset\) | \(\neg (P(\neg A \wedge B) \vee P(\neg A \wedge \neg B))\) |
We have the following \(P\)-constituents:
- \(P(\neg A \wedge \neg B)\)
- \(P(\neg A \wedge B)\)
We get the truth-table:
\(P(\neg A \wedge \neg B)\) | \(P(\neg A \wedge B)\) | \(O(A \vee B)\) | \(OA\) | \(O(A \vee B) \supset OA\) | ||
---|---|---|---|---|---|---|
0 | 0 | 1 | 1 | 1 | ||
0 | 1 | 1 | 0 | 0 | ||
1 | 0 | 0 | 0 | 1 | ||
1 | 1 | 0 | 0 | 1 |
This shows that the formula in question is not a tautology.
Task 6
- Discussed at .
Is \(OB \supset O(A \vee \neg A)\) a tautology? Use Von Wright's decision procedure to answer the question.
Solution
0 | \(OB\) | \(\supset\) | \(O(A \vee \neg A)\) |
1 | \(\neg P \neg B\) | \(\supset\) | \(\neg P \neg(A \vee \neg A)\) |
2 | \(\neg (P (A \wedge\neg B) \vee P(\neg A \wedge \neg B))\) | \(\supset\) | \(\neg P (A \wedge \neg A)\) |
We have the following \(P\)-constituents of our formula:
- \(P(A \wedge \neg B)\)
- \(P(\neg A \wedge \neg B)\)
We get the truth-table:
\(P(A \wedge \neg B)\) | \(P(\neg A \wedge \neg B)\) | \(OB\) | \(O(A \vee \neg A)\) | \(OB \supset O(A \vee \neg A)\) | ||
---|---|---|---|---|---|---|
0 | 0 | 1 | 0/1 | 0/1 | ||
0 | 1 | 0 | 0/1 | 1 | ||
1 | 0 | 0 | 0/1 | 1 | ||
1 | 1 | 0 | 0/1 | 1 |
- Note that for \(P(A \wedge \neg A)\) resp. for \(O(A \vee \neg A)\) we need to follow Von Wright's Principle of Deontic Contingency according to which a contradictory act is not necessarily forbidden (resp. a tautological act is not necessarily obliged).
- We thus write 0/1 in the truth-table to indicate the contingency of the formula (it can go both ways).
- In lines 2–4 the resulting complex formula (last column to the right) gets truth value 1 since an implication is always true when its antecedent is true. This is different in line 1: here it can go both ways, depending on the truth value of the conclusion. Altogether this is sufficient to show that the formula is not a tautology in Von Wright's system.
Session 4: Distribution and Scopes
To be discussed on
.Task 1
In Forrester's article the principle
- If \(\vdash p \supset q\) then \(\vdash Op \supset Oq\).
was used.
What do you think about the following analogous principle in epistemic logic:
- If \(\vdash p \supset q\) then \(\vdash Kp \supset Kq\)?
Task 2
In his article Von Wright presents the following basic principle of Deontic Distribution:
- \(P(A \vee B)\) iff \(PA \vee PB\)
It tells us that we can switch scopes:
- \(P\) can be moved inside the scope of \(\vee\) and
- vice versa, \(\vee\) can be moved inside the scope of \(P\)
Forrester used another inference step in which he switched scopes of two operators:
- from \(O(p \supset q)\) he inferred \(p \supset Oq\)
Here \(O\) was moved inside the scope of \(\supset\) to the consequent.
Where
- \(K\) is the knowledge operator
- \(\Diamond\) is the alethic possibility operator
critically discuss the following principles:
- \(O(p \wedge q)\) implies and/or if \(Op \wedge Oq\)
- \(O(p \vee q)\) implies and/or if \(Op \vee Oq\)
- \(K(p \vee q)\) implies and/or if \(Kp \vee Kq\)
- \(K(p \supset q)\) implies and/or if \(p \supset Kq\)
- \(O(p \supset q)\) implies and/or if \(p \supset Oq\)
- \(\exists x \Diamond R(x)\) implies and/or if \(\Diamond \exists x R(x)\) (where \(R\) is some predicate)
Session: Conditional Obligations
Recall the following procedure to determine extensions of \(\langle F, \Delta\rangle\) where \(F\) is a set of formulas representing 'facts' and \(\Delta\) is a set of conditionals \(A \rightarrow B\) ('\(A\) commits you to \(B\)'):
- step 0
- let \(E_0 = F\)
- pick a \(A \rightarrow B\) from \(\Delta\) that is (1) triggered by \(E_0\) and (2) not conflicted by \(E_0\)
- \(A \rightarrow B\) is triggered by \(E\) iff \(E \vdash A\)
- \(A \rightarrow B\) is conflicted by \(E\) iff \(E \vdash \neg B\)
- let \(E_1 = E_0 \cup \{B\}\)
- step \(i+1\)
- pick a \(A \rightarrow B\) from \(\Delta\) that is (1) triggered by \(E_i\) and (2) not conflicted with \(E_i\)
- let \(E_{i+1} = E_i \cup \{B\}\)
Do this until a fixed-point is reached (that is: nothin new is added anymore).
- \(E = Cn(E_1 \cup \ldots \cup E_i \cup \ldots)\) is an extension of \(\langle F, \Delta\rangle\)
According to the skeptical approach, the consequences of \(\langle F, \Delta\rangle\) are the formulas that are in the intersection of all extensions of \(\langle F, \Delta\rangle\).
Task 1
Let \(\langle F , \Delta\rangle\) where
- \(F = \{n\}\)
- \(\Delta = \{n\rightarrow q, n \rightarrow r, q \rightarrow p, r \rightarrow \neg p\}\).
What can we derive from that?
Task 2
Let \(\langle F ,\Delta \rangle\) where
- \(F = \{m,a\}\)
- \(\Delta = \{m \rightarrow \neg f, (m \wedge a) \rightarrow f\}\)
What can we derive from that?
Task 3
Let \(\langle F ,\Delta \rangle\) where
- \(F = \{a\}\)
- \(\Delta = \{a \rightarrow (b \vee c), b \rightarrow d, c \rightarrow d\}\)
What can we derive from that?
Sessions: Horty and his Default Model for Conditional Obligations with Priorities; McNamara and the Supererogatory (Fri)
Recall the following definitions from our session on Horty (for details look at the slides)
- we start with a triple \(\langle \Phi, \Delta, < \rangle\) where
- \(\Phi\) is a set of formulas (the facts)
- \(\Delta\) is a set of conditional obligations of the form \(A \rightarrow B\)
- \(<\) is an ordering on \(\Delta\) that is transitive, irreflexive, and asymmetric
- scenario : a set \(\mathcal{S}\) of conditional obligations (defaults)
- \({\rm Conclusion}(A\rightarrow B) = B\)
- \({\rm Premise}(A \rightarrow B) = A\)
- \({\rm Conclusion}(\mathcal{S})\) is the set of all \({\rm Conclusion}(A \rightarrow B)\) where \(A \rightarrow B \in \mathcal{S}\)
- \({\rm Triggered}(\mathcal{S}) = \{\delta \in \Delta \mid \Phi \cup {\rm Conclusion}(\mathcal{S}) \vdash {\rm Premise}(\delta)\}\)
- \({\rm Conflicted}(\mathcal{S}) = \{ \delta \in \Delta \mid \Phi \cup {\rm Conclusion} \vdash \neg{\rm Conclusion}(\delta) \}\)
- \({\rm Defeated}(\mathcal{S})\) is the set of all \(\delta \in \Delta\) for which there is a \(\Delta_d \subseteq {\rm Triggered}(\mathcal{S})\) (a defeating set) and a \(\mathcal{S}_a \subseteq \mathcal{S}\) (an accommodation set) for which
- \(\{\delta\} < \Delta_d\)
- \(S_a < \Delta_d\)
- \(\Phi \cup {\rm Conclusion}((\mathcal{S} \setminus \mathcal{S}_a) \cup \Delta_d)\) is consistent
- \(\Phi \cup {\rm Conclusion}((\mathcal{S} \setminus \mathcal{S}_a) \cup \Delta_d) \vdash \neg{\rm Conclusion}(\delta)\)
Horty's Procedure for Proper Scenarios and Extensions
Given an ordered default theory \(\langle \Phi, \Delta, <\rangle\) we construct proper scenarios as follows.
- guess \(\mathcal{S}\)
- the initial scenario is \(\mathcal{S}_0 = \emptyset\)
- do the following until a fixed point is reached
- \(\mathcal{S}_{i+1}\): add all \(\delta \in \Delta\) to \(\mathcal{S}_i\) that satisfy the following conditions
- \(\delta \in {\rm Triggered}(\mathcal{S}_i)\)
- \(\delta \notin {\rm Conflicted}(\mathcal{S})\) (here you need to make use of your guess!)
- \(\delta \notin {\rm Defeated}(\mathcal{S})\) (also here)
- \(\mathcal{S}_{i+1}\): add all \(\delta \in \Delta\) to \(\mathcal{S}_i\) that satisfy the following conditions
- let your fixed point be \(\mathcal{S}'\).
- If \(\mathcal{S} = \mathcal{S}'\) you're done. Then \(\mathcal{S}\) is a proper scenario and \(\Xi = Cn({\Phi \cup {\rm Conclusion}(\mathcal{S})})\) is an extension.
- Otherwise, start anew with another guess.
Task 1
Take \(T = \langle \Phi, \Delta, < \rangle\) where
- \(\Delta = \{\delta_1, \delta_2, \delta_3\}\) and
- \(\delta_1 = a \rightarrow b\)
- \(\delta_2 = b \rightarrow c\)
- \(\delta_3 = a \rightarrow \neg c\)
- \(\Phi = \{a\}\)
- \(\delta_1 < \delta_3\) and \(\delta_2 < \delta_3\)
(In bold we have edges with higher priorities.)
What are the proper scenarios and the proper extensions of \(T\)?
Task 2
Does it make a difference in Task 1 if
- \(\delta_3 < \delta_2\) instead of \(\delta_2 < \delta_3\)?
(where dotted < dashed < solid)
Recall: The semantics by McNamara
We have the following ingredients:
- a world homey
- its accessible worlds W
- a ranking \(\le\) of the worlds in W (which is transitive (\(w_1 \le w_2\) and \(w_2 \le w_3\) implies \(w_1 \le w_3\)), reflexive (\(w \le w\) for all \(w \in W\)) and connected (for all \(w_1, w_2 \in W\), \(w_1 \le w_2\) or \(w_2 \le w_1\))).
As in the Kripkean semantics of SDL we have, e.g., \(OB p\) holds at homey iff it holds in all of its accessible worlds \(w \in W\).
For the standard deontic notions
(where OB stands for the obliged, PE for the permissible, IM for the impermissible, GR for the gratitous, and OP for optional), we have the following well-known semantic analysis:
(the star indicates that there is at least one such world)
What's new are modalities that are sensitive relative to the deontic significance ordering of the worlds W:
(where MI concerns 'doing the minimum', MA concerns 'doing the maximum', SU stands for the supererogatory, IN stands for the indifferent, PS for the permissibly suboptimal, and SI for the significant).
Here's a semantic proof that e.g. \(OB p\) implies \(MI p\).
- Suppose \(OB p\).
- Hence, for all worlds \(w\) in \(W\), \(w \models p\).
- Suppose \(w\) is minimal in \(W\).
- Then, by 2, \(w \models p\).
- Since \(w\) was an arbitrary minimal world in \(W\) this shows that \(p\) holds in all minimal worlds in \(W\).
Here's a semantic proof that \(MI p\) does not in general imply \(OB p\).
- We construct a counter-model with \(W = \{w_1, w_2\}\) where \(w_1 \models p\), \(w_2 \not\models p\) and \(w_1 \le w_2\) and \(w_2 \not\le w_1\).
- Clearly, \(MI p\) holds since the only minimal model is \(w_1\) and \(w_1 \models p\).
- For \(OB p\) to hold we also need, \(w_2 \models p\) (since \(p\) has to hold in all accessible worlds). However, that doesn't hold.
- Thus, we found a counter-example to the claim that \(MI p\) implies \(OB p\).
Task 3
Prove \(SU p\) implies \(MI \neg p\) and \(PE p\).
Task 4
Prove \(MI \neg p\) and \(PE p\) implies \(SU p\).
Task 5
Prove Mares' principle which says that:
\(OB(p \rightarrow q) \wedge OB(q \rightarrow r) \wedge IN p \wedge IN r\) implies \(IN q\).
Task 6
Check whether the following variant of Mares' principle also holds:
\(OB(p \rightarrow q) \wedge OB(q \rightarrow r) \wedge OP p \wedge OP r\) implies \(OP q\).