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


Leonid Yu. Devyatkin


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.




Non-classical logics
Author Biography

Leonid Yu. Devyatkin, Institute of Philosophy, Russian Academy of Sciences

Старший научный сотрудник Сектора логики


Жук, 2011 – Жук Д.Н. Предикатный метод построения решетки Поста // Дискретная математика. 2011. Т. 23. № 2. С. 115–128.
Жук, 2018 – Жук Д.Н. От двузначной к k-значной логике // Интеллектуальные системы. Теория и приложения. 2018. Т. 22. Вып. 1. С. 131–149.
Нагорный, 2013 – Нагорный А.С. О пересечениях и объединениях предполных классов многозначной логики: дис. канд. физ.-мат. наук: 01.01.09. М., 2013. 162 с.
Adams, Dziobiak, 1994 – Adams M.E, Dziobiak W. Lattices of quasivarieties of 3-element algebras // Journal of Algebra. 1994. Vol. 166. No. 1. P. 181–210.
Avron, 1999 – Avron A. On the expressive power of three-valued and four-valued languages // Journal of Logic and Computation. 1999. Vol. 9. No. 6. P. 977–994. Arieli, Avron, 1998 – Arieli O., Avron A. The value of the four values // Artificial Intelligence. 1998. Vol. 102. No. 1. P. 97–141.
Arieli, Avron, 2017 – Arieli O., Avron A. Four-valued paradefinite logics // Studia Logica. 2017. Vol. 105. No. 6. P. 1087–1122.
Arieli et al., 2011 – Arieli O., Avron A., Zamansky A. Maximal and premaximal paraconsistency in the framework of three-valued semantics // Studia Logica. 2011. Vol. 97. No. 1. P. 31–60.
Baker, Pixley, 1975 – Baker K.A., Pixley A.F. Polynomial interpolation and the Chines Remainder Theorem for algebraic systems // Mathematische Zeitschrift. 1975. Vol. 143. No. 2. P. 165–174.
Belnap, 1977 – Belnap N.D. How a computer should think // Contemporary Aspects of Philosophy / Ed. by G. Ryle. Oriel Press, 1977. P. 30–56.
Da Costa, 1974 – Da Costa N.C.A. On the theory of inconsistent formal systems // Notre Dame Journal of Formal Logic. 1974. Vol. 15. No. 4. P. 497–510.
De, Omori, 2015 – De M., Omori H. Classical Negation and Expansions of BelnapDunn Logic // Studia Logica. 2015. Vol. 103. No. 5. P. 825–851.
Karpenko, 2017 – Karpenko A.S. Four-valued logics BD and DM4: Expansions // Bulletin of the Section of Logic. 2017. Vol. 46. No. 1–2. P. 33–45.
Lau, 2006 – Lau D. Function algebras on finite sets: Basic course on many-valued logic and clone theory. Springer: Science & Business Media, 2006. 670 с.
Los, 1949 – Lo´s J. O matrycach logicznych // Prace Wroclawskiego Towarzystwa Naukowego. Seria B. 1949. No. 19. P. 1–141.
Marcos, 2005 – Marcos J. Nearly every normal modal logic is paranormal // Logique et Analyse. 2005. Vol. 48. No. 189–192. P. 279–300.
Omori, Sano, 2014 – Omori H., Sano K. Da Costa meets Belnap and Nelson // Recent Trends in Philosophical Logic / Ed. by R. Ciuni, H. Wansing, C. Willkommen. Springer, 2014. P. 145–166.
Omori, Sano, 2015 – Omori H., Sano K. Generalizing functional completeness in Belnap–Dunn logic // Studia Logica. 2015. Vol. 103. No. 5. P. 883–917.
Omori, Wansing, 2017 – Omori H., Wansing H. 40 years of FDE: an introductory overview // Studia Logica. 2017. Vol. 105. No. 6. P. 1021–1049.
Petrukhin, Shangin, 2019 – Petrukhin Ya.I., Shangin V.O. Correspondence analysis and automated proof-searching for first degree entailment // European Journal of Mathematics. 2019. P. 1–44.
Pˇrenosil, 2021 – Pˇrenosil A. De Morgan clones and four-valued logics // Algebra universalis. 2021. Vol. 82. No. 2. P. 1–42.
Priest, 2008 – Priest G. An introduction to non-classical logic: From if to is.Cambridge University Press, 2008. 613 p.
Pynko, 1999 – Pynko A. Functional Completeness and Axiomatizability within Belnap’s Four-Valued Logic and its Expansions // Journal of Applied NonClassical Logics. 1999. Vol. 9. No. 1. P. 61–105.
Shapiro, 2017 – Shapiro L. LP, K3 and FDE as Substructural Logics // The Logica Yearbook 2016 / Ed. by P. Arazim and T. Laviˇcka. London: College Publications, 2017. P. 257–272.
Shoesmith, Smiley, 1978 – Shoesmith D.J., Smiley T.J. Multiple-conclusion logic. CUP Archive, 1978. 396 p.
Shramko et al., 2017 – Shramko Y., Zaitsev D., Belikov A. First-Degree Entailment and its Relatives // Studia Logica. 2017. Vol. 105. P. 1291–1317.
Shramko et al., 2019 – Shramko Y., Zaitsev D., Belikov A. The FMLA-FMLA Axiomatizations of the Exactly True and Non-falsity Logics and Some of Their Cousins // Journal of Philosophical Logic. 2019. Vol. 48. P. 787–808.
Tomova, 2021 – Tomova N. A Semi-lattice of Four-valued Literal-paraconsistentparacomplete Logics // Bulletin of the Section of Logic. 2021. Vol. 50. No. 1. P. 35–53.