A simple decision procedure for da Costa's Cn logics by Restricted Nmatrix semantics

Abstract

Despite being fairly powerful, finite non-deterministic matrices are unable to characterize some logics of formal inconsistency, such as those found between $\text{mbCcl}$ and $\text{Cila}$. In order to overcome this limitation, we propose here restricted non-deterministic matrices (in short, RNmatrices), which are non-deterministic algebras together with a subset of the set of valuations. This allows us to characterize not only $\text{mbCcl}$ and $\text{Cila}$ (which is equivalent, up to language, to da Costa's logic $C_1$) but the whole hierarchy of da Costa's calculi $C_n$. This produces a novel decision procedure for these logics. Moreover, we show that the RNmatrix semantics proposed here induces naturally a labelled tableau system for each $C_n$, which constitutes another decision procedure for these logics. This new semantics allows us to conceive da Costa's hierarchy of $C$-systems as a family of (non deterministically) $(n+2)$-valued logics, where $n$ is the number of "inconsistently true" truth-values and 2 is the number of "classical" or "consistent" truth-values, for every $C_n$.

34 pages. This new version of the paper removes 2 sections from the old one, one providing RNmatrices for $C_2$ and the other constructing RNmatrices over an arbitrary Boolean algebra as swap structures, and includes 2 new sections, detailing the use of row-branching truth-tables for RNmatrices and tableau systems based on RNmatrices for $C_n$