Analytic proofs for logics of evidence and truth

Walter Carnielli, Lorenzzo Frade, Abilio Rodrigues, [4mm] University of Campinas, Campinas, Brazil · 2024

Read Analytic proofs for logics of evidence and truth by Walter Carnielli, Lorenzzo Frade, Abilio Rodrigues, [4mm] University of Campinas, Campinas, Brazil (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-10588.txt.

Introduction

Walter Carnielli, Lorenzzo Frade, and Abilio Rodrigues build a proof system for a logic of evidence in a 2024 paper. The logic extends a four-valued system that tolerates contradiction, adding operators that mark when a claim behaves classically or not. Their contribution is a tableau method, a proof search by systematic case splitting, for that extended logic.

The system is proven sound, complete, and decidable: every valid claim has a proof, no invalid claim slips through, and the search always ends. Such analytic proofs matter for using the logic in computing and process theory, the authors note.

Catalog record

CREATORWalter Carnielli, Lorenzzo Frade, Abilio Rodrigues, [4mm] University of Campinas, Campinas, Brazil
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-10588

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Analytic proofs for logics of evidence and truth Thanks: The research of the first author is supported by the grant 307376/2018-4, Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq, Brazil). The research of the third author is supported by the grants 311911/2018-8, Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq, Brazil), and APQ-02093-21, Fundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG, Brazil). Walter Carnielli, Lorenzzo Frade, Abilio Rodrigues, [4mm] University of Campinas, Campinas, Brazil Abstract This paper presents a sound, complete, and decidable analytic tableau system for the logic of evidence and truth L ​ E ​ T F LET_{F} , introduced in Rodrigues, Bueno-Soler & Carnielli (Synthese, DOI: 10.1007/s11229-020-02571-w, 2020). L ​ E ​ T F LET_{F} is an extension of the logic of first-degree entailment ( F ​ D ​ E FDE ), also known as Belnap-Dunn logic. F ​ D ​ E FDE is a widely studied four-valued paraconsistent logic, with applications in computer science and in the algebra of processes. L ​ E ​ T F LET_{F} extends F ​ D ​ E FDE in a very natural way, by adding a classicality operator ∘ {\circ} , which recovers classical logic for propositions in its scope, and a non-classicality operator ∙ {\bullet} , dual of ∘ {\circ} . Dedicated to Francisco Miró Quesada, the godfather of paraconsistency. 1 Introduction The aim of this paper is to present an analytic tableau system for the logic LET_{F} , which is a member of a family of logics called logics of evidence and truth ( LET s) [ 6 , 18 ] . The motivation for LET s is the idea that in real-life reasoning we deal with positive and negative evidence, and such evidence can be conclusive or non-conclusive. LET s thus combine two different notions of logical consequence in the same formal system: one preserves truth (classical consequence), the other preserves evidence – hence, the name ‘logics of evidence and truth’. Evidence is thought of as a notion weaker than truth, in the sense that there may be evidence for a proposition A even in the case A is not true. Positive and negative evidence, respectively evidence for truth and for falsity, are independent and non-complementary, and negative evidence for A is identified with positive evidence for \neg A . LET s are paraconsistent, since it may be that there is conflicting non-conclusive evidence for a proposition A , and paracomplete, since it may happen that there is no evidence at all for A . 1 1 1 A more detailed account of the notion of evidence that underlies the intended interpretation of LET s can be found in [ 17 ] . The logic LET_{F} , introduced in [ 18 ] , is an extension of the logic of first-degree entailment ( FDE ), also called Belnap-Dunn logic [ 2 , 10 , 15 ] . LET_{F} is equipped with a classicality operator {\circ} and a non-classicality operator {\bullet} which is the dual of {\circ} . The deductive behavior of {\circ} and {\bullet} is given by the following inferences: (1) {\circ}A,{\bullet}A\vdash B , (2) \vdash{\circ}A\lor{\bullet}A , (3) {\circ}A,A,\neg A\vdash B (although A,\neg A\nvdash B ), (4) {\circ}A\vdash A\lor\neg A (although \nvdash A\lor\neg A ), (5) \vdash A\lor\neg A\lor{\bullet}A , (6) A,\neg A\vdash{\bullet}A . According to the intended interpretation in terms of evidence, items (1) and (2) together mean that either there is or there is not conclusive evidence for A . Items (3) and (4) , as in any LET , recover classical negation for propositions in the scope of {\circ} , and (5) and (6) are dual, respectively, of (3) and (4) . Due to items (3) and (4) , LET_{F} is a logic of formal inconsistency and undeterminedness [ 8 , 14 , cf.] . LET_{F} , as LET s in general, can also be interpreted in terms of information, which may be unreliable or reliable, the latter being subjected to classical logic [see 18 , Sect. 2.2.1] . In this case, {\circ}A means that the information about A , positive or negative, is reliable. In [ 1 ] , Kripke models for LET_{F} have been proposed. These models intend to represent a database that receives information as time passes, and such information can be positive, negative, unreliable, or reliable. This idea fits the interpretation of Belnap-Dunn logic as an information-based logic, but adds to the four scenarios expressed by it two new scenarios: reliable information (i) for the truth and (ii) for the falsity of a given proposition. FDE was probably the first logic to be applied in computer science and, more recently, in description logics and in the algebra of processes [ 3 , 11 , 16 , 19 , see e.g.] . An extension of FDE such as LET_{F} has an ample range of possible applications, especially in Bayesian decision procedures under uncertainty [ 4 , cf.] . This paper extends the investigation on LET_{F} carried out in [ 1 , 18 ] . It has been remarked in [ 18 , Sect. 3.2] that LET_{F} is decidable, but a detailed algorithm has not been presented. Our main aim here is to present a sound, complete, and decidable tableaux system for LET_{F} . 2 2 2 Analytic tableaux for some logics of formal inconsistency have already been proposed in [ 5 ] and [ 7 , Sect. 3.5] . The tableaux to be proposed are analytic because the formulas yielded by the application of a rule to a formula F are always less complex than F , and counterexamples can be obtained from open branches of terminated tableaux. The remainder of this paper is structured as follows. Section 2 presents the valuation semantics of LET_{F} , and Section 3 , the corresponding tableau system. In Section 4 we prove the soundness and completeness of the LET_{F} -tableau system with respect to the semantics of Section 2 , and also that the analytic tableau system provides a decision procedure for LET_{F} . Finally, in Section 5 , some examples of LET_{F} -tableaux are given and commented. 2 Valuation semantics for LET_{F} The language \mathcal{L} of LET_{F} is composed of denumerably many sentential letters p_{1},p_{2},\dots , the unary connectives {\circ} , {\bullet} , and \neg , the binary connectives \land and \lor , and parentheses. The set of formulas of \mathcal{L} , which is also denoted by \mathcal{L} , is inductively defined in the usual way. Roman capitals A,B,C,\dots will be used as metavariables for the formulas of \mathcal{L} , and Greek capitals \Gamma,\Delta,\Sigma,\dots as metavariables for sets of formulas \mathcal{L} . In [ 18 ] a natural deduction system, together with the following sound and complete semantics, was presented for LET_{F} . Definition 1 . [Valuation semantics for LET_{F} ] A valuation semantics for LET_{F} is a collection of LET_{F} -valuations defined as follows. A function v:\mathcal{L}\to\{0,1\} is a LET_{F} -valuation if it satisfies the following clauses: (v1) v(A\land B)=1 iff v(A)=1 and v(B)=1 , (v2) v(A\lor B)=1 iff v(A)=1 or v(B)=1 , (v3) v(\neg(A\land B)) = 1 iff v(\neg A)=1 or v(\neg B)=1 , (v4) v(\neg(A\lor B))=1 iff v(\neg A)=1 and v(\neg B)=1 , (v5) v(A)=1 iff v(\neg\neg

Read the complete text