Drawing Sound Conclusions from Unsound Premises

Abstract

Given sets ${\Phi }_1=\{{\varphi }_{11},...,{\varphi }_{1u(1)}\},...,{\Phi }_z=\{{\varphi }_{z1},...,{\varphi }_{zu(z)}\}$ of boolean formulas, a formula $\omega$ follows from the conjunction $\bigwedge {\Phi }_i=\bigwedge {\varphi }_{ij}$ iff $\neg \omega \wedge {\bigwedge }_{i=1}^z{\Phi }_i$ is unsatisfiable. Now assume that, given integers $0\le e_i<u(i)$, we must check if $\neg \omega \wedge {\bigwedge }_{i=1}^z{\Phi }_i^{\prime }$ remains unsatisfiable, where ${\Phi }_i^{\prime }\subseteq {\Phi }_i$ is obtained by deleting $e_i$ arbitrarily chosen formulas of ${\Phi }_i$, for each $i=1,...,z.$ Intuitively, does $\omega$ {\it stably} follow, after removing $e_i$ random formulas from each ${\Phi }_i$? We construct a quadratic reduction of this problem to the consequence problem in infinite-valued \luk\ logic Ł${}_{\infty }$. In this way we obtain a self-contained proof that the Ł${}_{\infty }$-consequence problem is coNP-complete.