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

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

Abstract

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.

Other Versions

No versions found

Links

PhilArchive

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Analytics

Added to PP
2022-10-18

Downloads
329 (#84,469)

6 months
74 (#82,895)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

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

Citations of this work

No citations found.

Add more citations