On the expressive power of maximally paraconsistent and paracomplete expansions of FDE

Abstract

The paper is devoted to the closed classes of functions of four-valued logics which can be generated by the primitive operations of characteristic matrices for the expansions of $\mathbf{FDE}$ that are simultaneously maximally paraconsistent and paracomplete. We begin with presenting the necessary and sufficient conditions which four-valued expansions of $\mathbf{FDE}$ must satisfy in order to be maximally paraconsistent and paracomplete. In both cases, the criteria of maximality are linked to operations of a certain kind being present in a matrix of an expansion in question, which prevent it from being a sublogic of a three-valued expansion of Asenjo--Priest's logic $\mathbf{LP}$ --- in the paraconsistent case, or Kleene's logic $\mathbf{K_{3}}$ --- in the paracomplete case. Further, relying on the Baker--Pixley theorem, we describe a set of 5 unary and 20 binary predicates such that any closed class of functions generated by the operations of a four-valued characteristic matrix characterizing an expansion of $\mathbf{FDE}$ is a class of functions that preserve one of its subsets. This yields a simple algorithm for comparing the expressive power of any arbitrary four-valued expansion of $\mathbf{FDE}$. Moreover, taking into account that the given set of predicates includes all predicates describing precomplete classes of functions of four-valued logic which are preserved by the operations of the characteristic matrix for $\mathbf{FDE}$, we provide criteria of functional completeness and precompleteness for the operations of any four-valued matrix which characterizes an expansion of $\mathbf{FDE}$. Finally, by utilizing the conditions of maximal paraconsistency and paracompleteness, as well as the list of predicates for expansions of $\mathbf{FDE}$, given in the paper, we identify all 14 sets of predicates describing the closed classes of functions which can be generated by systems of primitive operations of four-valued characteristic matrices for such expansions of $\mathbf{FDE}$ that are at the same time maximally paraconsistent and maximally paracomplete. This allows us to not only list all closed classes corresponding to the maximally paraconsistent and paracomplete four-valued expansions of $\mathbf{FDE}$, but also to order them with respect to inclusion.