The universe of propositional approximations

AbstractThe idea of approximate entailment has been proposed by Schaerf and Cadoli [Tractable reasoning via approximation, Artif. Intell. 74(2) (1995) 249–310] as a way of modelling the reasoning of an agent with limited resources. In that framework, a family of logics, parameterised by a set of propositional letters, approximates classical logic as the size of the set increases.The original proposal dealt only with formulas in clausal form, but in Finger and Wassermann [Approximate and limited reasoning: semantics, proof theory, expressivity and control, J. Logic Comput. 14(2) (2004) 179–204], one of the approximate systems was extended to deal with full propositional logic, giving the new system semantics, an axiomatisation, and a sound and complete proof method based on tableaux. In this paper, we extend another approximate system by Schaerf and Cadoli, presented in a subsequent work [M. Cadoli, M. Schaerf, The complexity of entailment in propositional multivalued logics, Ann. Math. Artif. Intell. 18(1) (1996) 29–50] and then take the idea further, presenting a more general approximation framework of which the previous ones are particular cases, and show how it can be used to formalise heuristics used in theorem proving