Inconsistency-Adaptive Logics

Table of Contents

1 Inconsistency-Adaptive Logics

1.1 Basic Motivation

  • reasoning on the basis of inconsistent information
  • use a paraconsistent logic
  • however, they are weak, if monotonic
  • why?
  • disjunctive syllogism (If \(A\) and \({\sim} A \vee B\) then \(B\)) doesn't hold
  • do you see why?

1.2 What to do?

  • strengthen paraconsistent logics adaptively
  • if we assume \(A \wedge {\sim}A\) not to hold we get that
    • \(A\) and \({\sim}A \vee B\) implies \(B\)
    • \({\sim}A\) and \(A \vee B\) implies \(B\)

1.3 So …

  • we need to first settle for a paraconsistent lower limit logic
  • a good candidate for the logical form of abnormalities is \({\sim}A \wedge A\)

1.4 Enters: CLuN

CLuN is defined by Modus Ponens (MP) and the following axiom schemata:

1.5 The semantics of CLuN

1.6 CLuN is weak …

no double negation elimination/introduction, no De Morgan Rules:

1.7 Now, let's go adaptive

Note that:

  • \(A, {\sim} A \vee B \vdash_{CLuN} B \vee (A \wedge {\sim} A)\)
  • \(A \vdash_{CLuN} {\sim}{\sim} A \vee (A \wedge {\sim}A)\)
  • \({\sim}{\sim} A \vdash_{CLuN} A \vee ({\sim} A \wedge {\sim}{\sim} A)\)
  • \({\sim}(A \vee B) \vdash_{CLuN} ({\sim} A \wedge {\sim} B) \vee ((A \vee B) \wedge {\sim}(A \vee B))\)
  • etc.

Thus:

  • \(A, {\sim} A \vee B \vdash_{CLuN^{x}} B\)
  • \(A \vdash_{CLuN^{x}} {\sim}{\sim} A\)
  • \({\sim}{\sim} A \vdash_{CLuN^{x}} A\)
  • \({\sim}(A \vee B) \vdash_{CLuN^{x}} ({\sim} A \wedge {\sim} B)\)
  • etc.

1.8 An example

Take \(\Gamma = \{ p, {\sim}p \vee q, r, {\sim}r\}\).

  • What can you derive?

1.9 What about strengthening CLuN? Enters: CLuNs

{CLuNs} is {CLuN} plus De Morgan and plus double negation introduction and elimination

1.10 The (2-valued) semantics of CLuNs

1.11 The Flip/Flop problem

  • suppose we use the same unrestricted form of abnormalities \(A \wedge {\sim}A\) as for CLuN
  • Do you see a problem if we use this logic and reason, for instance, with \(\Gamma = \{ p, {\sim}p \vee q, r, {\sim}r\}\)?

1.12 What's the cure?

  • Restrict the form of abnormalities to atoms!

2 Prioritising Adaptive Logics

2.1 Some abnormalities count more …

  • Idea: structure the set of abnormalities!
  • Instead of \(\Omega\) we use \(\langle\Omega_1, \Omega_2, \ldots \rangle\) where each \(\Omega_i\) is specified by a logical form
  1. Example

    \(\circ_i A \wedge \neg A\) (rate the trustworthiness of your evidence: the lower \(i\) the higher the trustworthiness of the evidence)

2.2 Semantics based on this idea

  • start with the set \(\mathcal{M}_{\bf LLL}(\Gamma)\) of all LLL-models of \(\Gamma\)
  • now select all \(\Omega_1\)-minimally abnormal models out of these: \(\mathcal{M}_1(\Gamma)\)
  • then select all \(\Omega_2\)-minimally abnormal models out of \(\mathcal{M}_1(\Gamma)\) denoted by \(\mathcal{M}_2(\Gamma)\)
  • go on like this
  • the set of all selected models \(\mathcal{M}_p(\Gamma)\) is given by \(\bigcap_{i\ge 1}\mathcal{M}_i(\Gamma)\).
  • the consequence relation is then defined as usual: \(\Gamma \Vdash A\) iff for all \(M \in \mathcal{M}_p(\Gamma)\), \(M \models A\)

2.3 An alternative semantics

Where \(\Delta \subseteq \bigcup_{i\ge 1} \Omega_i\) we define \(\Delta_i = \Delta \cap \Omega_i\).

  1. Lexicographic Ordering

    \(\Delta \prec_{\rm lex} \Theta\) iff there is a \(i \ge 1\) such that

    • for all \(j \le i\): \(\Delta_j = \Theta_j\)
    • \(\Delta_i \subset \Theta_i\).
  2. Order Models according to abnormal parts and lex-order

    Let \(M \sqsubset M'\) iff \(\Ab(M) \prec \Ab(M')\).

    \(\Gamma \Vdash A\) iff for all \(\sqsubset\)-minimal models \(M\) in \(\mathcal{M}(\Gamma)\), \(M \models A\).

2.4 The two semantics are identical

We have to show that \(M \in \mathcal{M}_p(\Gamma)\) iff \(M\) is \(\sqsubset\)-minimal in \(\mathcal{M}(\Gamma)\).

  1. (\(\Rightarrow\))
    • Suppose \(M \in \mathcal{M}_p(\Gamma)\).
    • Assume for a contradiction that there is a \(M' \in \mathcal{M}(\Gamma)\) for which \(\Ab(M') \sqsubset \Ab(M)\).
    • Hence, there is a minimal \(i\) for which \(\Ab(M')_i \subset \Ab(M)_i\) and \(\Ab(M')_j = \Ab(M)_j\) for all \(j < i\).
    • Hence, both \(M, M' \in \mathcal{M}_j(\Gamma)\) for all \(j < i\).
    • However, \(\Ab(M')_i \subset \Ab(M)_i\) contradicts the fact that \(M \in \mathcal{M}_i(\Gamma)\).
  2. (\(\Leftarrow\))

    Similar (try it!).

2.5 A simple example

Take \(\Gamma = \{\circ_1 p, \circ_2 q, \circ_3r, \neg p \vee \neg q \vee \neg r\}\)

Here are some models

model \(\circ_1 p \wedge \neg p\) \(\circ_2q \wedge \neg q\) \(\circ_3r \wedge \neg r\)
\(M_1\) 1 1 0
\(M_2\) 1 0 0
\(M_3\) 0 1 0
\(M_4\) 0 1 1
\(M_5\) 0 0 1
  • Can you determine \(\mathcal{M}_i(\Gamma)\) for \(i \in \{1,2,3\}\)?
  • What follows in the example?

2.6 How to prove things?

  • basic idea: similar to minimal abnormality strategy
  • just instead of \(\Phi_s(\Gamma)\) use a different set: \(\Phi_s^{\rm lex}(\Gamma)\) which we will define in a moment
  1. \(\Phi_s^{\rm lex}(\Gamma)\)

    \(\Phi_s^{\rm lex}(\Gamma)\) is the set of all choice sets of \(\Sigma(\Gamma)\) that are \(\prec_{\rm lex}\)-minimal.

    (Recall that \(\Sigma(\Gamma)\) is the set of all \(\Theta \subseteq \Omega\) such that \(\Dab(\Theta)\) is a minimal Dab-formula at stage \(s\).)

2.7 Marking

A line \(l\) with an argument \(A\) and a condition \(\Delta\) is marked iff

  1. there is a \(\Theta \in \Phi_s^{\rm lex}(\Gamma)\) for which \(\Delta \cap \Theta = \emptyset\)
  2. for each \(\Theta \in \Phi_s^{\rm lex}(\Gamma)\) there is a line \(l'\) with argument \(A\) and a condition \(\Delta'\) for which \(\Delta' \cap \Theta = \emptyset\).
  1. Final Derivability

    as before

2.8 Back to our example

prove \(p \wedge q\) from \(\Gamma = \{\circ_1 p, \circ_2 q, \circ_3r, \neg p \vee \neg q \vee \neg r\}\)

2.9 Is there a problem with strong reassurance?

Let \(\Delta\) be a choice set of \(\Sigma(\Gamma)\). We show that there is a \(\prec\)-minimal choice set \(\Delta'\) of \(\Sigma(\Gamma)\) for which \(\Delta' \subseteq \Delta\).

  1. The construction
    • Let \(\Sigma_1(\Gamma)\) be the set of all \(\Theta \subseteq \Omega_1\) such that \(\Dab(\Theta)\) is a minimal Dab-consequence of \(\Gamma\).
    • We know that there \(\Delta_1\) is a choice set of \(\Sigma_1(\Gamma)\).
    • We also know that there is a \(\Delta'_1 \subseteq \Delta_1\) that is a minimal choice set of \(\Sigma_1(\Gamma)\) (see one of the previous sessions).
    • Let \(\Sigma_2(\Gamma)\) the set of all \(\Theta \setminus \Omega_1\) for which \(\emptyset \neq \Theta \setminus \Omega_1 \subseteq \Omega_2\), \(\Delta'_1 \cap \Theta = \emptyset\), and \(\Dab(\Theta)\) is a minimal Dab-consequence of \(\Gamma\).
      • If \(\Delta'_1 \subset \Delta_1\) let \(\Delta'_2\) be any minimal choice set of \(\Sigma_2(\Gamma)\).
      • Otherwise, \(\Delta_2\) is a choice set of \(\Sigma_2(\Gamma)\). Let \(\Delta'_2\) be a minimal choice set of \(\Sigma_2(\Gamma)\) such that \(\Delta'_2 \subseteq \Delta_2\).
    • Let \(\Sigma_3(\Gamma)\) the set of all \(\Theta \setminus (\Omega_1 \cup \Omega_{2})\) for which \(\emptyset \neq \Theta \setminus (\Omega_1 \cup \Omega_2) \subseteq \Omega_3\), \((\Delta'_1 \cup \Delta'_{2}) \cap \Theta = \emptyset\), and \(\Dab(\Theta)\) is a minimal Dab-consequence of \(\Gamma\).
      • If \(\Delta'_1 \cup \Delta_{2}' \subset \Delta_1 \cup \Delta_2\) let \(\Delta'_3\) be any minimal choice set of \(\Sigma_3(\Gamma)\).
      • Otherwise, \(\Delta_3\) is a choice set of \(\Sigma_3(\Gamma)\). Let \(\Delta'_3\) be a minimal choice set of \(\Sigma_3(\Gamma)\) such that \(\Delta'_3 \subseteq \Delta_3\).
    • We proceed similarly for all \(i \ge 4\).
    • Let \(\Delta' = \bigcup_{i\ge 1} \Delta'_i\).
  2. Showing that we found the right \(\Delta'\)
    • It is easy to see via induction that \(\Delta' \prec \Delta\) or \(\Delta' = \Delta\). (Try to prove this!)
    • Assume there is a \(\Theta\) that is a choice set of \(\Sigma(\Gamma)\) and for which \(\Theta \prec \Delta'\).
      • Thus, there is a minimal \(i\) for which \(\Theta_i \subset \Delta'_i\) and \(\Theta_j = \Delta'_j\) for all \(j < i\).
      • Since \(\Delta'_i\) is a minimal choice set of \(\Sigma_i(\Gamma)\) there is a \(\Lambda \setminus \bigcup_{j < i} \Omega_j \in \Sigma_i(\Gamma)\) for which \(\Theta_i \cap (\Lambda \setminus \bigcup_{j < i} \Omega_j) = \emptyset\).
      • Thus, \(\Theta_i \cap \bigcup_{j < i} \Omega_j \neq \emptyset\). However since \(\Delta'_i \cap \bigcup_{j < i} \Omega_j = \emptyset\) this is a contradiction.
    • Let \(\Theta \in \Sigma(\Gamma)\) and let \(i\) be the highest index appearing in \(\Theta\).
      • Suppose \(\Delta' \cap \bigcup_{j < i} \Theta_j = \emptyset\). Hence, \(\Theta \in \Sigma_i(\Gamma)\). Since \(\Delta'_i\) is a minimal choice set of \(\Sigma_i(\Gamma)\), \(\Delta' \cap \Theta \neq \emptyset\).
      • This shows that \(\Delta'\) is a choice set of \(\Sigma(\Gamma)\).
    • Altogether we have found a \(\Delta'\) that is a \(\prec\)-minimal choice set of \(\Sigma(\Gamma)\) and for which \(\Delta' \subseteq \Delta\).

2.10 How does this help with reassurance? Abnormal parts and choice sets

  1. from abnormal parts to choice sets

    Where \(M \in \mathcal{M}(\Gamma)\), \(\Ab(M)\) is a choice set of \(\Sigma(\Gamma)\).

    1. Proof

      Let \(\Delta \in \Sigma(\Gamma)\). Hence, \(\Gamma \Vdash_{\bf LLL} \Dab(\Delta)\). Hence, \(M \models \Dab(\Delta)\). Hence, there is a \(A \in \Delta\) such that \(M \models A\) and thus \(A \in \Ab(M)\).

  2. from choice sets to abnormal parts

    Where \(\Delta\) is a choice set of \(\Sigma(\Gamma)\) there is a model \(M \in \mathcal{M}(\Gamma)\) such that \(\Ab(M) \subseteq \Delta\).

    1. Proof
      • Suppose there is no model \(M \in \mathcal{M}(\Gamma)\) for which \(\Ab(M) \subseteq \Delta\).
      • Hence, \(\Gamma \cup (\Omega \setminus \Delta)^{\neg}\) is LLL-trivial.
      • Hence, \(\Gamma \cup (\Omega \setminus \Delta)^{\neg} \Vdash A\) for any \(A\). Let \(A \in \Omega \setminus \Delta\)
      • By the compactness of LLL there is a finite subset of \(\Theta^{\neg} \subseteq (\Omega \setminus \Delta)^{\neg}\) such that \(\Gamma \cup \Theta^{\neg} \Vdash A\).
      • By the deduction theorem, \(\Gamma \Vdash \bigwedge\Theta^{\neg} \supset A\) and hence \(\Gamma \Vdash \Dab(\Theta\cup \{A\})\).
      • Hence, there is a minimal \(\Theta' \subseteq \Theta \cup \{A\}\) such that \(\Gamma \Vdash \Dab(\Theta')\). (Note that \(\Theta' \in \Sigma(\Gamma)\).)
      • Since \(\Delta\) is a choice set of \(\Sigma(\Gamma)\) and \(\Delta \cap \Theta = \emptyset\) this is a contradiction.
  3. strong reassurance

    Where \(M \in \mathcal{M}(\Gamma)\) there is a \(M' \in \mathcal{M}_p(\Gamma)\) for which \(\Ab(M') \subseteq \Ab(M)\).

    1. Proof
      • Let \(M \in \mathcal{M}(\Gamma)\).
      • Hence, \(\Ab(M)\) is a choice set of \(\Sigma(\Gamma)\).
      • Thus, there is a \(\Delta\) that is a \(\prec\)-minimal choice set of \(\Sigma(\Gamma)\) for which \(\Delta \subseteq \Ab(M)\).
      • Hence, there is a \(M' \in \mathcal{M}(\Gamma)\) for which \(\Ab(M') \subseteq \Delta\).
      • Assume \(\Ab(M') \subset \Delta\). Then \(\Ab(M') \prec \Delta\). Since \(\Ab(M')\) is a choice set of \(\Sigma(\Gamma)\) this is a contradiction. Hence, \(\Ab(M') = \Delta\).
      • Hence, \(M' \in \mathcal{M}_p(\Gamma)\).

Author: Christian Straßer

Created: 2015-07-07 Tue 03:01

Emacs 24.5.1 (Org mode 8.2.10)

Validate