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
| CREATOR | Walter Carnielli, Lorenzzo Frade, Abilio Rodrigues, [4mm] University of Campinas, Campinas, Brazil |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
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