Towards Tractable Approximations to Many-Valued Logics: the Case of First Degree Entailment

In Igor Sedlár (ed.), The Logica Yearbook, 2021. London, UK: pp. 57-76 (2022)
  Copy   BIBTEX


FDE is a logic that captures relevant entailment between implication-free formulae and admits of an intuitive informational interpretation as a 4-valued logic in which “a computer should think”. However, the logic is co-NP complete, and so an idealized model of how an agent can think. We address this issue by shifting to signed formulae where the signs express imprecise values associated with two distinct bipartitions of the set of standard 4 values. Thus, we present a proof system which consists of linear operational rules and only two branching structural rules, the latter expressing a generalized rule of bivalence. This system naturally leads to defining an infinite hierarchy of tractable depth-bounded approximations to FDE. Namely, approximations in which the number of nested applications of the two branching rules is bounded.

Author Profiles

Marcello D'Agostino
Università degli Studi di Milano
Alejandro Solares-Rojas
Universidad de Buenos Aires (UBA)


Added to PP

130 (#70,313)

6 months
71 (#40,511)

Historical graph of downloads since first upload
This graph includes both downloads from PhilArchive and clicks on external links on PhilPapers.
How can I increase my downloads?