# Exam: Adaptive Logics Applied to the Philosophy of Science

$$\def\nc{\mathop{\mid\!\sim}}$$

 Year 2015 Institution Ghent University Study Program Post-Graduate Studies Lecturer Christian Straßer Date of Exam [2015-06-10 Wed]

## Task (The Deduction and the Resolution Theorem)

Recall:

Deduction Theorem
$$\Gamma \cup \{A\} \vdash B$$ implies $$\Gamma \vdash A \supset B$$.
Resolution Theorem
$$\Gamma \vdash A \supset B$$ implies $$\Gamma \cup \{A\} \vdash B$$.

Consider the premise sets

• $$\Gamma_1 = \{\circ p, \neg(\circ q \wedge \neg q) \vee \neg p\}$$
• $$\Gamma_2 = \{ (\circ p \wedge \neg p) \vee (\circ q \wedge \neg q), \circ p, \circ q \}$$

Given our logic $$CL_{\circ}$$, demonstrate:

1. that the deduction theorem does not hold for reliability
2. that the resolution theorem does not hold for reliability
3. that the resolution theorem does not hold for minimal abnormality

### Solution

• $$\Gamma_2 \cup \{\circ q \wedge \neg q\} \vdash^r p$$, while
• $$\Gamma_2 \nvdash^r (\circ q \wedge \neg q) \supset p$$.
• The reason is that there is a reliable model $$M$$ of $$\Gamma_2$$ for which $$M \models \neg p$$ and $$M \models \neg q$$.
• In this model we have $$M \not\models p$$ and $$M \models \circ q \wedge \neg q$$

• To show this take $$\Gamma_1$$.
• This premise set is normal, ie. there are models of $$\Gamma_1$$ with empty abnormal part.
• Clearly, $$\Gamma_1 \vdash^r p$$. Thus also $$\Gamma_1 \vdash^r (\circ q \wedge \neg q) \supset p$$.
• On the other hand, we do not have $$\Gamma_1 \cup \{\circ q \wedge \neg q \} \vdash^r p$$.
• The reason is that $$\Gamma_1 \cup \{\circ q \wedge \neg q\} \vdash_{CL_{\circ}} \neg p$$.

The argument is analogous to 2.

## Task (The Deduction Theorem and Minimal Abnormality)

Prove that the deduction theorem holds for the semantic consequence relation of minimal abnormality.

### Solution

• Suppose $$\Gamma \cup \{A\} \vdash^m B$$.
• Let $$M$$ be a minimally abnormal model of $$\Gamma$$.
• Assume that $$M \not\models A \supset B$$.
• Then $$M \models A$$ and $$M \models \neg B$$.
• Clearly, $$M \in \mathcal{M}^m(\Gamma \cup \{A\})$$.
• However, this is a contradiction, since $$M \not\models B$$.
• Thus, $$M \models A \supset B$$.

Two important properties in the domain of non-monotonic logics are

Cautious Monotonicity
Where $$\Gamma \nc A$$ for all $$A \in \Delta$$, $$\Gamma \nc B$$ implies $$\Gamma \cup \Delta \nc B$$.
Cautious Transitivity
Where $$\Gamma \nc A$$ for all $$A \in \Delta$$, $$\Gamma \cup \Delta \nc B$$ implies $$\Gamma \nc B$$.

Your task is to prove that for $$\Vdash^m$$ both properties hold. Here's how you should proceed.

1. Try to prove the following:
Lemma
If $$\Gamma \Vdash^m A$$ for all $$A \in \Delta$$ then $$\mathcal{M}^m(\Gamma) = \mathcal{M}^m(\Gamma \cup \Delta)$$.
2. Show that from this immediately follows Cautious Monotonicity and Cautious Transitivity for $$\Vdash^m$$.

### Solution

• Suppose $$\Gamma \Vdash^m A$$ for all $$A \in \Delta$$.
• Let $$M \in \mathcal{M}^m(\Gamma)$$.
• By the supposition, $$M \in \mathcal{M}(\Gamma \cup \Delta)$$.
• Suppose $$M' \in \mathcal{M}(\Gamma \cup \Delta)$$ such that $${\sf Ab}(M') \subset {\sf Ab}(M)$$.
• However, since $$M' \in \mathcal{M}(\Gamma)$$ this is a contradiction to the fact that $$M \in \mathcal{M}^m(\Gamma)$$.
• Thus, $$M \in \mathcal{M}^m(\Gamma \cup \Delta)$$.
• Let now $$M \in \mathcal{M}^m(\Gamma \cup \Delta)$$.
• Suppose there is a $$M' \in \mathcal{M}(\Gamma)$$ such that $${\sf Ab}(M') \subseteq {\sf Ab}(M)$$.
• By the main supposition, $$M' \in \mathcal{M}(\Gamma \cup \Delta)$$.
• Thus, $${\sf Ab}(M) = {\sf Ab}(M')$$ which shows that $$M \in \mathcal{M}^m(\Gamma)$$.

Since $$\mathcal{M}(\Gamma) = \mathcal{M}(\Gamma \cup \Delta)$$ also, $$\Gamma \Vdash^m A$$ iff $$\Gamma \cup \Delta \Vdash^m A$$.

Another important property often discussed in the domain of non-monotonic logic is

Fixed Point
$$Cn(\Gamma) = Cn(Cn(\Gamma))$$.

Show that it holds for minimal abnormality. (Tipp: you only need to use Cautious Monotonicity and Cautious Transitivity from the previous task.)

### Solution

• Note that
1. $$Cn^m(\Gamma) \subseteq Cn^m(\Gamma)$$, and
2. $$\Gamma \subseteq Cn^m(\Gamma)$$.
• By 1 and Cautious Monotonicity, $$Cn^m(\Gamma) \subseteq Cn^m(\Gamma \cup Cn^m(\Gamma))$$.
• By 1 and Cautious Transitivity, $$Cn^m(\Gamma) \supseteq Cn^m(\Gamma \cup Cn^m(\Gamma))$$.
• Hence, by 2, $$Cn^m(\Gamma) \subseteq Cn^m(Cn^m(\Gamma))$$ and $$Cn^m(\Gamma) \supseteq Cn^m(Cn^m(\Gamma))$$.
• Altogether, $$Cn^m(\Gamma) = Cn^m(Cn^m(\Gamma))$$.

Lou Goble talks in his article about the so-called Flip-Flop problem for adaptive logics.

Suppose we add the following rule to our logic CL$$_{\circ}$$:

• If $$\vdash_{CL} A \supset B$$ then $$\vdash_{CL_{\circ}} \circ A \supset \circ B$$.

This strengthened system suffers from the Flip-Flop problem.

Try to demonstrate this with the example $$\Gamma = \{\circ p, \neg p, \circ q\}$$.

### Solution

• It would be intuitive to derive $$q$$ from $$\Gamma$$. However, this is not possible.
• The reason is that $$\circ q \wedge \neg q$$ is involved in a minimal Dab-consequence.
• To see this suppose $$q$$ is true.
• Then also $$\neg p \wedge q$$ which is equivalent to $$\neg ( p \vee \neg q)$$.
• Now from $$\circ p$$ follows with the new rule $$\circ(p \vee \neg q)$$.
• Hence, $$\Gamma \vdash q \supset [\circ(p \vee \neg q) \wedge \neg(p \vee \neg q)]$$.
• This implies, $$\Gamma \vdash (\circ q \wedge \neg q) \vee [\circ(p \vee \neg q) \wedge \neg(p \vee \neg q)]$$.
• This is a minimal Dab-consequence (neither of the two disjuncts is derivable).
• Hence, there is a minimally abnormal model in which $$\circ q \wedge \neg q$$ is true.
• This shows that $$q$$ doesn't follow with either strategy.

Recall the following rules from Makinson & Van Der Torre's paper:

CT
$$\displaystyle \frac{A \Rightarrow B \quad A \wedge B \Rightarrow C}{A \Rightarrow C}$$
AND
$$\displaystyle \frac{A \Rightarrow B \quad A \Rightarrow C}{A \Rightarrow (B \wedge C)}$$
ID
$$A \Rightarrow A$$
SI
If $$B \vdash A$$ then $$A \Rightarrow C$$ implies $$B \Rightarrow C$$.

1. Show that in the presence of (SI), (CT) implies
TRANS
$$\displaystyle \frac{A \Rightarrow B \quad B \Rightarrow C}{A \Rightarrow C}$$
2. Show that in the presence of (ID) and (AND), (TRANS) implies (CT).

### Solution

• Suppose we have $$A \Rightarrow B$$ and $$B \Rightarrow C$$.
• We need to show that $$A \Rightarrow C$$.
• From $$B \Rightarrow C$$ we get via (SI), $$A \wedge B \Rightarrow C$$.
• By (CT), $$A \Rightarrow C$$.

• Suppose we have $$A \Rightarrow B$$ and $$A \wedge B \Rightarrow C$$.
• By (ID), $$A \Rightarrow A$$.
• By (AND), $$A \Rightarrow A \wedge B$$.
• By (TRANS) applied to $$A \Rightarrow A\wedge B$$ and $$A \wedge B \Rightarrow C$$ we get $$A \Rightarrow C$$.

## Task: Yet another deontic logic

Lou Goble defines permitted inheritance along the following lines (slightly changed):

PI1
$$\vdash [O(A \wedge B) \wedge P(A \wedge B)] \supset OA$$

Read: inheritance is applied whenever the antecedent $$O(A \wedge B)$$ is not conflicting.

Let's give the following twist to it:

PI2
$$\vdash [O(A \wedge B) \wedge PA] \supset OA$$.

Using the intuition behind some of Lou Goble's systems, we can define the abnormality $$\Omega = \{ O(A \wedge B) \wedge \neg PA\}$$. This allows us to apply PI2 conditionally, namely:

• derive $$OA$$ from $$O(A \wedge B)$$ on the condition $$\{O(A \wedge B) \wedge \neg PA\}$$.

1. Show that with this solution we cannot derive $$Op$$ from $$\Gamma = \{O(p \wedge q), Or, O\neg r\}$$ in a logic L in which
• we have all of propositional classical logic
• we also have unrestricted aggregation: $$\vdash (OA \wedge OB) \supset O(A \wedge B)$$,
• we have replacement of equivalents: where $$\vdash A \equiv B$$ also $$\vdash OA \equiv OB$$,
• and $$P$$ is defined by $$\neg O \neg$$.
2. Would you know of a possible technique to avoid the problem in 1? (There is no need to demonstrate that it works: just state a possible solution.)

### Solution

• Suppose $$Op$$ holds.
• Then, by aggregation, $$O(r \wedge p)$$.
• Thus, $$\Gamma \vdash_L Op \supset [O(r \wedge p) \wedge O(\neg r)]$$.
• By the interdefinability of O and P, $$\Gamma \vdash_L Op \supset [O(r \wedge p) \wedge \neg Pr]$$.
• Hence, $$\Gamma \vdash_{L} (O(p\wedge q) \wedge \neg Op) \vee [O(r \wedge p) \wedge \neg Pr]$$.
• By contraposing PI2, $$O(p \wedge q) \wedge \neg Op$$ implies $$\neg Pp$$.
• Thus, $$\Gamma \vdash_{L} (O(p\wedge q) \wedge \neg Pp) \vee [O(r \wedge p) \wedge \neg Pr]$$.
• So, if we try to derive $$Op$$ from $$O(p \wedge q)$$ on the condition $$\{O(p\wedge q) \wedge \neg Pp\}$$ this line gets marked.