# Effective finite-valued approximations of general propositional logics

In Arnon Avron, Nachum Dershowitz & Alexander Rabinovich (eds.),

*Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday*. Berlin: Springer. pp. 107–129 (2008)**Abstract**

Propositional logics in general, considered as a set of sentences, can be undecidable even if they have “nice” representations, e.g., are given by a calculus. Even decidable propositional logics can be computationally complex (e.g., already intuitionistic logic is PSPACE-complete). On the other hand, finite-valued logics are computationally relatively simple—at worst NP. Moreover, finite-valued semantics are simple, and general methods for theorem proving exist. This raises the question to what extent and under what circumstances propositional logics represented in various ways can be approximated by finite-valued logics. It is shown that the minimal m-valued logic for which a given calculus is strongly sound can be calculated. It is also investigated under which conditions propositional logics can be characterized as the intersection of (effectively given) sequences of finite-valued logics.

**Keywords**

**Categories**

(categorize this paper)

**PhilPapers/Archive ID**

BAAEFA

**Revision history**

Archival date: 2017-10-10

View upload history

View upload history

References found in this work BETA

No references found.

Citations of this work BETA

No citations found.

**Added to PP index**

2017-10-10

**Total downloads**

41 ( #28,056 of 35,448 )

**Recent downloads (6 months)**

13 ( #21,273 of 35,448 )

How can I increase my downloads?

**Monthly downloads since first upload**

*This graph includes both downloads from PhilArchive and clicks to external links.*