Exam: Adaptive Logics Applied to the Philosophy of Science

Table of Contents

\(\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

Ad 1

  • \(\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\)

Ad 2

  • 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\).

Ad 3

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

Task (Cautious Properties)

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

Ad 1

  • 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)\).

Ad 2

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

Task (Fixed Point)

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

Task (FlipFlop)

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.

Task (Input/Output Logic)

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

You have the following tasks:

  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

Ad 1

  • 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\).

Ad 2

  • 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\}\).

Your task is to

  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

Ad 1

The problem is one often encountered in Goble's paper: a flip-flop problem.

  • 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]\).
  • This is a minimal Dab-consequence.
  • 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.