# Exercises: Normative Reasoning and Deontic Logics

back to the main course page

## General Info

### Change Log

• Session 1 added [2015-04-10 Fri]

### 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

### 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 [2015-04-09 Thu]

To be discussed at [2015-04-16 Thu].

Let $$M = \langle W, R, v\rangle$$ be an arbitrary Kripke-model as defined on slide 3.

• Discussed at <2015-04-23 Thu>.

Show: $$M,w \models \Box(A \wedge B) \mbox{ implies } M,w \models \Box A \wedge \Box B$$

Recall the following:

1. $$M, w \models \Box A$$ iff for all $$w' \in W$$ for which $$(w, w') \in R$$, $$M,w' \models A$$.
2. $$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$$.

• Discussed at <2015-04-23 Thu>.

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)$$.

• Discussed at <2015-04-23 Thu>.

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:

1. $$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:

1. $$M,w \models \neg A$$ iff $$M,w \not\models A$$
2. $$M, w \models A \vee B$$ iff $$M,w \models A$$ or $$M,w \models B$$
3. $$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$$.

• Discussed at <2015-04-23 Thu>.

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$$.

1. How would you express introspection formally?
2. Does introspection hold in arbitrary Kripkean models? Give a reason.
1. By $$\Box A \supset \Box \Box A$$.
2. 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$$).

• Discussed at <2015-04-30 Thu>.

A principle in deontic logic says that obligations should imply permissions.

1. How would you express this principle formally where the $$\Box$$ is written $${\sf O}$$ while the diamond is written $${\sf P}$$.
2. Are there Kripkean models that do not validate this principle? Give a reason.
1. $${\sf O}A \supset {\sf P}A$$
2. 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.

• Discussed at <2015-04-30 Thu>.
1. $$\{1,3,5,6\} \cap \{1,4,6\} = \mbox{?}$$
2. $$\{1,3,5,6\} \cup \{1,4,6\} = \mbox{?}$$
3. $$\{1,4,6\} \subseteq \{1,3,5,6\}\mbox{?}$$
4. Let $$A = \{1,3\}$$ and $$B = \{2,3\}$$. Write down all elements of $$A \times B$$.
1. $$\{1,3,5,6\} \cap \{1,4,6\} = \{1.6\}$$
2. $$\{1,3,5,6\} \cup \{1,4,6\} = \{1,3,4,5,6\}$$
3. $$\{1,4,6\} \not\subseteq \{1,3,5,6\}$$ since $$4$$ is in the former but not in the latter set.
4. $$A \times B = \{(1,2), (1,3), (3,2), (3,3)\}$$

#+endsolution

### Task 7: Naive Set Theory and Self-reference (for the courageous)

• Discussed at <2015-04-30 Thu>.

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?

• 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 [2015-04-23 Thu]

To be discussed on [2015-04-30 Thu].

• Discussed at <2015-04-30 Thu>.

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.

1. $$M \models \Diamond p$$
2. $$M \models \Box p$$
3. $$M \models \Box(p \vee q)$$
4. $$M \models \neg q \supset \Diamond \Diamond q$$
1. This does not hold since $$M,w_2 \not\models \Diamond p$$.
2. This does not hold since $$M,w_2 \not\models \Box p$$.
3. This holds since $$M,w_i \models \Box(p\vee q)$$ for all $$i \in \{1,2,3\}$$.
4. This holds since $$M,w_i \models \neg q \supset \Diamond \Diamond q$$ for all $$i \in \{1,2,3\}$$.

• Discussed at <2015-04-30 Thu>.

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$$.

• Discussed at <2015-04-30 Thu>.

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 [2015-04-30 Thu]

### 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!)

• Discussed at <2015-05-15 Fri>.
1. State the perfect disjunctive normal form of $$(p \vee q) \wedge (\neg p \vee \neg q)$$.
2. 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)$$.

• Discussed at <2015-05-15 Fri>.
1. State the perfect disjunctive normal form of $$p \supset \neg p$$.
2. 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$$.

• Discussed at <2015-05-15 Fri>.
1. State the perfect disjunctive normal form of $$(p \wedge q) \supset r$$.
2. 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.

1. Replace each $$O$$ by $$\neg P\neg$$.
2. 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)
3. Make the truth-table where the left columns are occupied by the previously obtained $$P$$-constituents
4. 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.

• Discussed at <2015-05-15 Fri>.

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?

• Discussed at <2015-05-15 Fri>.

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.

• Discussed at <2015-05-15 Fri>.

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 [2015-05-15 Fri]

To be discussed on [2015-05-21 Thu].

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$$?

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:

1. $$O(p \wedge q)$$ implies and/or if $$Op \wedge Oq$$
2. $$O(p \vee q)$$ implies and/or if $$Op \vee Oq$$
3. $$K(p \vee q)$$ implies and/or if $$Kp \vee Kq$$
4. $$K(p \supset q)$$ implies and/or if $$p \supset Kq$$
5. $$O(p \supset q)$$ implies and/or if $$p \supset Oq$$
6. $$\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$$.

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?

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?

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
1. $$\{\delta\} < \Delta_d$$
2. $$S_a < \Delta_d$$
3. $$\Phi \cup {\rm Conclusion}((\mathcal{S} \setminus \mathcal{S}_a) \cup \Delta_d)$$ is consistent
4. $$\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
1. $$\mathcal{S}_{i+1}$$: add all $$\delta \in \Delta$$ to $$\mathcal{S}_i$$ that satisfy the following conditions
1. $$\delta \in {\rm Triggered}(\mathcal{S}_i)$$
2. $$\delta \notin {\rm Conflicted}(\mathcal{S})$$ (here you need to make use of your guess!)
3. $$\delta \notin {\rm Defeated}(\mathcal{S})$$ (also here)
• let your fixed point be $$\mathcal{S}'$$.
1. 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.
2. Otherwise, start anew with another guess.

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$$?

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$$.

1. Suppose $$OB p$$.
2. Hence, for all worlds $$w$$ in $$W$$, $$w \models p$$.
3. Suppose $$w$$ is minimal in $$W$$.
4. Then, by 2, $$w \models p$$.
5. 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$$.

Prove $$SU p$$ implies $$MI \neg p$$ and $$PE p$$.

Prove $$MI \neg p$$ and $$PE p$$ implies $$SU p$$.

$$OB(p \rightarrow q) \wedge OB(q \rightarrow r) \wedge IN p \wedge IN r$$ implies $$IN q$$.
$$OB(p \rightarrow q) \wedge OB(q \rightarrow r) \wedge OP p \wedge OP r$$ implies $$OP q$$.