Effective Finite-Valued Approximations of General Propositional Logics

DOI10.1007/978-3-540-78127-1_7zbMATH Open1133.03328arXiv1908.01200OpenAlexW2138558100MaRDI QIDQ5452176FDOQ5452176

Authors: Matthias Baaz, Richard Zach 

Publication date: 25 March 2008

Published in: Pillars of Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1908.01200

Recommendations

• Many-valued computational logics
• Labeled calculi and finite-valued logics
• Resolution approximation of first-order logics
• Finite-valued reductions of infinite-valued logics
• Advances in Artificial Intelligence – SBIA 2004

Mathematics Subject Classification ID

Many-valued logic (03B50)

Cites Work

• The semantics and proof theory of linear logic
• Labeled calculi and finite-valued logics
• A treatise on many-valued logics
• A propositional calculus with denumerable matrix
• Title not available (Why is that?)
• Title not available (Why is that?)
• Semantical investigations in Heyting's intuitionistic logic
• Satisfiability in many-valued sentential logic is NP-complete
• Title not available (Why is that?)
• Systematization of finite many-valued logics through the method of tableaux
• Title not available (Why is that?)
• Title not available (Why is that?)
• Decidability and the finite model property

Cited In (11)

• Theory of valuation
• Labeled calculi and finite-valued logics
• Optimal axiomatizations of finitely valued logics
• Applying Association Rules to ε-Reduction of Finite Theory in Two-Valued Propositional Logic
• The universe of propositional approximations
• On a sequential model of the algebra of finite-valued logic
• Characterizing finite-valuedness
• Title not available (Why is that?)
• Logics in Artificial Intelligence
• Efficient Approximation of Well-Founded Justification and Well-Founded Domination
• On evaluations of propositional formulas in countable structures

This page was built for publication: Effective Finite-Valued Approximations of General Propositional Logics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5452176)