Representing Paraconsistent Reasoning via Quantified Propositional Logic

摘要

Quantified propositional logic is an extension of classical propositional logic where quantifications over atomic formulas are permitted. As such, quantified propositional logic is a fragment of second-order logic, and its sentences are usually referred to as quantified Boolean formulas (QBFs). The motivation to study quantified propositional logic for paraconsistent reasoning is based on two fundamental observations. Firstly, in recent years, practicably efficient solvers for quantified propositional logic have been presented. Secondly, complexity results imply that there is a wide range of paraconsistent reasoning problems which can be efficiently represented in terms of QBFs. Hence, solvers for QBFs can be used as a core engine in systems prototypically implementing several of such reasoning tasks, most of them lacking concrete realisations. To this end, we show how certain paraconsistent reasoning principles can be naturally formulated or reformulated by means of quantified Boolean formulas. More precisely, we describe polynomial-time constructible encodings providing axiomatisations of the given reasoning tasks. In this way, a whole variety of a priori distinct approaches to paraconsistent reasoning become comparable in a uniform setting.