Algebraic Foundations of Many-Valued Reasoning | springerprofessional.de

Springer Professional

nach oben

2000 | Buch

Kapitel lesen Erstes Kapitel lesen

Algebraic Foundations of Many-Valued Reasoning

verfasst von: Roberto L. O. Cignoli, Itala M. L. D’Ottaviano, Daniele Mundici

Verlag: Springer Netherlands

Buchreihe : Trends in Logic

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Anzeige

Inhaltsverzeichnis

Frontmatter

Introduction

Abstract

The aim of this book is to give self-contained proofs of all basic results concerning the infinite-valued propositional calculus of Łukasiewicz and its algebras, Chang’s MV-algebras. This book is for self-study: with the possible exception of Chapter 9 on advanced topics, the only prerequisite for the reader is some acquaintance with classical propositional logic, and elementary algebra and topology.

Roberto L. O. Cignoli, Itala M. L. D’Ottaviano, Daniele Mundici

Chapter 1. Basic notions

Abstract

We introduce MV-algebras by means of a small number of simple equations, in an attempt to capture certain properties of the unit real interval [0,1] equipped with truncated addition x ⊕ y = min(1, x + y) and negation 1 - x. We show that every MV-algebra contains a natural lattice-order. The chapter culminates with Chang’s Subdirect Representation Theorem, stating that if an equation holds in all totally ordered MV-algebras, then the equation holds in all MV-algebras.

Roberto L. O. Cignoli, Itala M. L. D’Ottaviano, Daniele Mundici

Chapter 2. Chang completeness theorem

Abstract

In this chapter we shall prove Chang’s completeness theorem stating that if an equation holds in the unit real interval [0,1], then the equation holds in every MV-algebra. Thus, intuitively, the two element structure {0,1} stands to boolean algebras as the interval [0,1] stands to MV-algebras. Our proof is elementary, and makes use of tools (such as “good sequences”) that shall also find applications in a subsequent chapter to show the equivalence between MV-algebras and lattice-ordered abelian groups with strong unit.

Roberto L. O. Cignoli, Itala M. L. D’Ottaviano, Daniele Mundici

Chapter 3. Free MV-algebras

Abstract

Free algebras are universal objects: every n-generated MV-algebra A is a homomorphic image of the free MV-algebra Free _n over n generators; if an equation is satisfied by Free _n then the equation is automatically satisfied by all MV-algebras. As a consequence of the completeness theorem, Free _n is easily described as an MV-algebra of piecewise linear continuous [0,1]-valued functions defined over the cube [0, 1]ⁿ. Known as McNaughton functions, they stand to MV-algebras as {0,1}-valued functions stand to boolean algebras. Many interesting classes of MV-algebras can be described as algebras of [0, l]-valued continuous functions over some compact Hausdorff space. The various representation theorems presented in this chapter all depend on our concrete representation of free MV-algebras.

Roberto L. O. Cignoli, Itala M. L. D’Ottaviano, Daniele Mundici

Chapter 4. Łukasiewicz ∞-valued calculus

Abstract

Since every MV-term τ is a string of symbols over a finite alphabet, one may naturally consider the following decision problem: does there exist an effective procedure (for definiteness, a Turing machine) deciding whether an arbitrary equation τ = 1 holds in all MV-algebras? More generally, given two terms σ and τ, does there exist an effective procedure to decide whether the McNaughton function determined by σ belongs to the principal ideal determined by τ in the free MValgebra Free _ω ? These are respectively known as the word problem for free MV-algebras, and the word problem for finitely presented MV-algebras.

Roberto L. O. Cignoli, Itala M. L. D’Ottaviano, Daniele Mundici

Chapter 5. Ulam’s game

Abstract

The crucial problem of interpreting n truth values when n > 2 was investigated, among others, by Łukasiewicz himself. As shown in this chapter, a simple interpretation is given by Ulam game, the variant of the game of Twenty Questions where n - 2 lies, or errors, are allowed in the answers. The case n = 2 corresponds to the traditional game without lies. The game is originally described by Ulam on page 281 of his book [235] as follows:

Someone thinks of a number between one and one million (which is just less than 2²⁰). Another person is allowed to ask up to twenty questions, to each of which the first person is supposed to answer only yes or no. Obviously the number can be guessed by asking first: Is the number in the first half million? then again reduce the reservoir of numbers in the next question by one-half, and so on. Finally the number is obtained in less than log₂(1000000). Now suppose one were allowed to lie once or twice, then how many questions would one need to get the right answer?

Roberto L. O. Cignoli, Itala M. L. D’Ottaviano, Daniele Mundici

Chapter 6. Lattice-theoretical properties

Abstract

In this chapter we study properties that are strongly related to the lattice structure of MV-algebras. We start by considering relations between the ideals of an MV-algebra A and the ideals of the lattice L(A). A stonean ideal of a bounded distributive lattice L is an ideal generated by complemented elements of L. We shall show that the minimal prime lattice ideals of L(A), as well as the stonean ideals of L(A), are always ideals of A.

Roberto L. O. Cignoli, Itala M. L. D’Ottaviano, Daniele Mundici

Chapter 7. MV-algebras and ℓ-groups

Abstract

As proved at the beginning of Chapter 2, Γ is a functor from the category A of ℓ-groups with a distinguished strong unit, to the category MV of MV-algebras. In this chapter we shall prove that Γ is a natural equivalence (i.e., a full, faithful and dense functor) between A and MV. As a consequence, a genuine addition can be uniquely recovered from the MV-algebraic structure. Several applications will be discussed.

Roberto L. O. Cignoli, Itala M. L. D’Ottaviano, Daniele Mundici

Chapter 8. Varieties of MV-algebras

Abstract

A class C of MV-algebras is said to be a variety (or, an equational class), iff there is a set ε of MV-equations such that for every MV-algebra A, A ∈ C iff A satisfies all equations in ε. For instance, when ε = ø, we obtain the variety MV of MV-algebras. When ε = { x = y}, we obtain the variety of trivial MV-algebras. The main aim of this chapter is to describe all varieties of MV-algebras.

Roberto L. O. Cignoli, Itala M. L. D’Ottaviano, Daniele Mundici

Chapter 9. Advanced topics

Abstract

The first part of this chapter deals with disjunctive normal forms in the infinite-valued calculus of Łukasiewicz. We shall generalize the Farey-Schauder machinery of Chapter 3 to formulas in any number of variables. Disjunctive normal forms will be the key tool to prove Mc-Naughton’s theorem, generalizing the proof given in 3.2.8 for functions of one variable. We shall also discuss the relationships between normal form reductions and toric desingularizations, and the correspondence between MV-algebras and AF C*-algebras. Strengthening Corollary 4.5.3, we shall show that the tautology problem in the infinite-valued calculus is in fact co-NP-complete, thus having the same complexity as it boolean counterpart. We shall give a proof of Di Nola’s representation theorem for all MV-algebras.

Roberto L. O. Cignoli, Itala M. L. D’Ottaviano, Daniele Mundici

Chapter 10. Further Readings

Abstract

Łukasiewicz introduced many-valued logics in 1920. The history of studies of Łukasiewicz’s original philosophical ideas and motivations is fairly long, and is definitely outside the scope of this book. Interested readers are referred to Wolenski’s monograph [246], where Łukasiewicz’s motivations are analyzed and his work on many-valuedness is presented in a wide perspective. In her essay [73] the author discusses many-valuedness in the framework on nonclassical logics. In their essay [204], Priest and Routley study Łukasiewicz logic from the viewpoint of para-consistency. Paztig [200] discusses the relations between Łukasiewicz’s ideas on many-valuedness and ideas in Chapter 9 of Aristotle’s De Interpretatione. The short paper by Rosser [218] surveys the early stages of many-valued logic, and offers succinct historical and bibliographical remarks to an intended audience of physicists. The books [149], [30] and [227] contain English translations of papers by Łukasiewicz and Wajsberg.

Roberto L. O. Cignoli, Itala M. L. D’Ottaviano, Daniele Mundici

Backmatter

Titel: Algebraic Foundations of Many-Valued Reasoning
verfasst von: Roberto L. O. Cignoli
Itala M. L. D’Ottaviano
Daniele Mundici
Copyright-Jahr: 2000
Verlag: Springer Netherlands
Electronic ISBN: 978-94-015-9480-6
Print ISBN: 978-90-481-5336-7
DOI: https://doi.org/10.1007/978-94-015-9480-6