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)

Richard Zach
University of Calgary
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 many-vlalued logic
Categories (categorize this paper)
Buy the book Find it on
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

 PhilArchive page | Other versions
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

A Propositional Calculus with Denumerable Matrix.Michael Dummett - 1959 - Journal of Symbolic Logic 24 (2):97-106.
Semantical Investigations in Heyting's Intuitionistic Logic.Dov M. Gabbay - 1986 - Journal of Symbolic Logic 51 (3):824-824.
Decidability and the Finite Model Property.Alasdair Urquhart - 1981 - Journal of Philosophical Logic 10 (3):367 - 370.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Finite-Valued Reductions of Infinite-Valued Logics.Aguzzoli Stefano & Gerla Brunella - 2002 - Archive for Mathematical Logic 41 (4):361-399.
Ideal Paraconsistent Logics.O. Arieli, A. Avron & A. Zamansky - 2011 - Studia Logica 99 (1-3):31-60.
On Finite-Valued Propositional Logical Calculi.O. Anshakov & S. Rychkov - 1995 - Notre Dame Journal of Formal Logic 36 (4):606-629.
Three-Valued Logics in Modal Logic.Barteld Kooi & Allard Tamminga - 2013 - Studia Logica 101 (5):1061-1072.
Interpolation in Fuzzy Logic.Matthias Baaz & Helmut Veith - 1999 - Archive for Mathematical Logic 38 (7):461-489.
Elimination of Cuts in First-Order Finite-Valued Logics.Matthias Baaz, Christian G. Fermüller & Richard Zach - 1993 - Journal of Information Processing and Cybernetics EIK 29 (6):333-355.
Many-Valued Reflexive Autoepistemic Logic.C. Koutras & S. Zachos - 2000 - Logic Journal of the IGPL 8 (1):33-54.
First-Order Gödel Logics.Richard Zach, Matthias Baaz & Norbert Preining - 2007 - Annals of Pure and Applied Logic 147 (1):23-47.


Added to PP index

Total views
206 ( #47,510 of 2,433,424 )

Recent downloads (6 months)
18 ( #40,701 of 2,433,424 )

How can I increase my downloads?


My notes