Parceria:
Logics for Approximate Reasoning: Approximating Classical Logic "From Above"

Marcelo FingerRenata Wassermann

Approximations are used for dealing with problems that are hard, usually NP-hard or coNP-hard. In this paper we describe the notion of approximating classical logic from above and from below, and concentrate in the first. We present the family \ensuremath{\mathsf{s_1}} of logics, and show it performs approximation of classical logic from above. The family \ensuremath{\mathsf{s_1}} can be used for disproving formulas (the SAT-problem) in a local way, concentrating only on the relevant part of a large set of formulas.