Metamathematics of Fuzzy Logic

In this chapter we are going to investigate the propositional logic given by Łukasiewicz t-norm (and the corresponding Łukasiewicz implication), and some of its extensions. Clearly, we want to find a complete axiomatization. It turns out that it is enough to add just one 1-tautology of this logic to the axioms of BL, namely the following axiom (¬¬) of double negation¹⁴

We are going to investigate the second of the three most important prepositional calculi, namely PC(_*II) where _*II is the product t-norm; we shall call this logic just the product logic and denote it by II. Recall that the corresponding implication is Goguen and the corresponding negation is Gödel negation (cf. 2.1.11,2.1.17). We present an axiom system (extension of BL by two axioms) and show its completeness²¹ by relating linearly ordered II-algebras — called product algebras — to ordered Abelian groups, similarly as in the case of MV-algebras (but now the proof is much simpler than in the case of MV-algebras). We also show that Łukasiewicz logic Ł has a faithful interpretation in II.²² We shall close the section by discussing some additional topics. Convention: In this section → (without any subscript) will be Goguen implication; the product conjunction will be denoted by ⊙.

We are now ready to start our investigation of fuzzy predicate logics (or first-order logics, quantification logics). We shall develop logics broadly analogous to the classical predicate logic; in particular, we shall deal only with two quantifiers, ∀ and ∃ (universal and existential). Generalized quantifiers will be studied in later chapters. In Section 1 we shall develop the predicate counterpart BL∀ of our basic propositional logic BL; in Section 2 we prove a rather general completeness theorem for predicate logics (with respect to semantics over residuated lattices). Sections 3 and 4 are devoted to Gödel and Lukasiewicz predicate logics respectively; we show that Gödel predicate logic has a recursive axiomatization that is complete with respect to the semantics over [0,1], whereas for Łukasiewicz we only present a variant of Pavelka logic. (We show in the next chapter that Łukasiewicz does not have a recursive complete axiomatization.) We close Sec. 4 with some for remarks on the predicate product logic. Sec. 5 discusses many-sorted calculi and Sec. 6 introduces and studies similarity (fuzzy equality). This notion will be crucial for our analysis of fuzzy control in Chap. 7.

The present chapter is devoted to an analysis of computational complexity of fuzzy propositional calculi and to the determination of the degree of undecidability of fuzzy predicate calculi. The results are important but will be only rarely used in other chapters, so the reader unfamiliar with the theory of (polynomial) complexity and/or arithmetical hierarchy may skip the chapter as a whole. On the other hand, in Section 1 we summarize all necessary material so that the non-expert in complexity or arithmetical hierarchy may also read the chapter and understand the results. In Section 2 we study the computational complexity of Ł, G, Π (propositional Łukasiewicz, Gödel and product logic) and show, among other things, that their sets of 1-tautologies T AUT ₁ ^Ł , T AUT ₁ ^G , T AUT ₁ ^Π are all co-NP-complete. In Section 3 we study the corresponding predicate calculi Ł∀, G∀, Π∀. We show that the set T AUT ₁ ^Π of Gödel predicate logic is Σ₂; it remains open if it is in Π₂ or is still more complex). Hence all these predicate calculi are undecidable.

We are going to study, from the logical point of view, expressions as “usually ϕ”, “ϕ is probable”, “for many x, ϕ” and similar. We shall handle them both as generalized quantifiers and as modalities. This should not look unnatural since in general modalities can be viewed as hidden quantifiers. We shall try to show how the theory of generalized quantifiers and modal logic can be applied to the above expressions (stressed by Zadeh as items of the specific agenda of fuzzy logic in the narrow sense) and that they admit “classical” logical analysis. We shall offer a logical apparatus, precise definitions, some results and various problems: here much study and development is still necessary. To be able to use and generalize the results and approaches of Boolean logic, we shall have to review and summarize several notions and facts on generalized quantifiers, some modal logics, and also on measures of uncertainty (that will be used to define various quantifiers and modalities). Thus we shall have two preliminary sections in this chapter: Section 1 on generalized quantifiers (with an appendix on uncertainty measures) and Section 2 on modal logics, both sections in the frame of Boolean (two-valued) logic. Generalized quantifiers in fuzzy logic and fuzzy modal logics are studied in Sections 3, 4.

This chapter is devoted to three mutually unrelated topics showing three directions of further development of fuzzy logic. (Needless to say, several other directions are possible.) In Section 1 we present a rather strong fuzzy logic, based on the work of Takeuti and Titani, and containing Łukasiewicz, Gödel and product predicate logics Ł∀, G∀, Π∀ as its sublogics. We show completeness with respect to a non-finitary notion of provability. In Section 2 we show how to develop fuzzy logic that is not necessarily truth-functional. This section is based on work by Pavelka. Section 3 is based on recent work by Hájek, Paris and Shepherdson and discusses the Liar paradox in the frame of fuzzy logic. The final Section 4 contains some conclusions.

Here I refer to important works concerning the topics of the present book. Even if I have tried to be as complete as possible, I cannot hope to have covered everything; I apologize for all omissions. On the other hand, an attempt to collect all publications concerning fuzzy logic (in both broad and narrow senses) would lead to a special publication; note that e.g. the book of Klir and Yuan [115] contains 1731 references! We thus only select references that are relevant to fuzzy logic in the narrow sense.