Swap Structures for LFIs

  • Walter Carnielli
  • Marcelo Coniglio


In 1977, M. Fidel and D. Vakarelov independently proposed a semantics for D. Nelson's logic in terms of a novel class of algebraic structures now called twist structures. Also in 1977, Fidel obtained for the first time the decidability of da Costa's paraconsistent systems C_n by using certain algebraic-relational semantical structures now called Fidel structures. Being non-truth-functional, logics in the hierarchy C_n as well as their generalization within the hierarchy of paraconsistent logics known as Logics of Formal Inconsistency (LFIs) do not have non-trivial logical congruences, and so they bravely resist to the semantical analysis based on standard tools, like categorial or algebraic semantics. This is why the development of alternative semantical techniques for this kind of LFIs is deemed necessary. In this paper we introduce a new class of semantics in terms of Fidel structures, as well as a matrix semantics in terms of a new class of twist-like structures called swap structures. Both semantics characterize mbc, the weaker logic in the hierarchy of LFIs. The equivalence between both semantics is proved directly, and a new proof of the decidability of mbc in terms of swap structures defined over the 2-element Boolean algebra is also obtained. Additionally, a second aspect connectd to this new semantics is the fact that, as they basically consitute a finite (structured) collection of finite matrices, the decidability of mbc with respect to such structures means to circumvent the limitations imposed by the famous result by K. Gödel of 1932 in showing that Heyting's formulation of intuitionistic logic cannot be characterized by finite-valued matrices. As it is well known, the same stratey was followed by Dugundji who proved in 1940 the non-characterizability of modal systems between S1 and S5 by means of finite matrices. Similar results, by adapting Gödel's strategy, have been obtained to the family of LFIs. The characterizability of LFIs by this new structures shows the limitation of Gödel's and Dugundji's method: a single matrix may not be able to characterize certain logics, but a finite collection of finite matrices in some cases will do.