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.
Towards Tractable Approximations to Many-Valued Logics: The Case of First Degree Entailment / M. D’Agostino, A. Solares-Rojas - In: The Logica Yearbook / [a cura di] I. Sedlar. - [s.l] : College Publications, 2022 Aug 01. - ISBN 978-1-84890-414-9. - pp. 57-76 (( Intervento presentato al 34th. convegno LOGICA 2021 tenutosi a Hejnice, Czech Republic nel 2021.
Towards Tractable Approximations to Many-Valued Logics: The Case of First Degree Entailment
M. D’AgostinoWriting – Original Draft Preparation
;
2022
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.File | Dimensione | Formato | |
---|---|---|---|
TractableFDE,LogicaYearbook.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
295.38 kB
Formato
Adobe PDF
|
295.38 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.