scientific article; zbMATH DE number 2042617

From MaRDI portal
Publication:4450446





This is a survey on complexity-theoretic issues about many-valued logic and its proof theory. After several decades of relative quiescence, research in many-valued logic has been rapidly expanding in the last twenty years, because of its applications to computer science (circuit verification, logic-based control, error-correcting codes with feedback, logic programming) and also because some algebras of many-valued logics, notably MV-algebras, have an interesting mathematical theory. For background see \textit{P. Hajek}'s book [Metamathematics of fuzzy logic. Kluwer Academic Publishers, Dordrecht (1998; Zbl 0937.03030)]. While the complexity of the propositional fragment of certain many-valued logics is often the same as for Boolean logic, this is no longer so for their first-order extensions. The author mainly concentrates on the complexity of satisfiability and tautology problems. McNaughton's representation of free MV-algebras is discussed in a special subsection. See \textit{R. L. O. Cignoli}, \textit{I. M. L. D'Ottaviano} and \textit{D. Mundici}, Algebraic foundations of many-valued reasoning. Kluwer Academic Publishers, Dordrecht (2000; Zbl 0937.06009) for more information on Łukasiewicz many-valued calculus and MV-algebras. Two main proof techniques are presented: reduction to mixed integer programming and reduction to classical logic. In the final sections the author discusses the size of representations of many-valued connectives and quantifiers. A list of 70 background references is provided. For the entire collection see [Zbl 1015.00007].











This page was built for publication:

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