Nonmonotonic reasoning in multivalued logics
Marjon Blondeel · Ghent University Academic Bibliography (Ghent University) · 2014
Inference in classical logic is monotonic: if a conclusion can be derived from a set of premises, then no additional premises will ever invalidate this conclusion.However, commonsense reasoning has a nonmonotonic component.Human beings draw sensible conclusions from what they know, making default assumptions where needed.And if there is new information, we might reconsider previous conclusions.Depending on how one deals with statements as "typically it holds that" and "in the absence of information to the contrary", different nonmonotonic logics can be considered, which have been studied since the 1970s.Two important formalisms for nonmonotonic reasoning are autoepistemic logic and negation-as-failure in logic programming.Answer set programming (ASP) is a declarative programming language based on the stable model semantics that is used to model complex combinatorial problems.Its strength lies in the use of the negation-as-failure operator which allows retracting previously made conclusions when new information is available.Moreover, there is a clear connection between ASP and autoepistemic logic: ASP programs can be translated to a set of formulas in autoepistemic logic such that the answer sets are in one-to-one correspondence with the so-called stable expansions in autoepistemic logic.Although ASP has been successfully applied to model combinatorial problems in a concise and declarative manner, it is not directly suitable for expressing problems in continuous domains.Fuzzy answer set programming (FASP) is a generalisation of ASP based on fuzzy logic that is capable of modelling continuous systems by using an infinite number of truth degrees corresponding to intensities of properties.Since it is a relatively new concept, little is known about the computational complexity of FASP and almost no techniques are available to compute answer sets of FASP programs.Furthermore, the Abstract connections of FASP to other paradigms for nonmonotonic reasoning with continuous values are largely unexplored.In our dissertation, we contribute to the ongoing research on FASP on several levels.First, we will pin down the complexity of the direct syntactical generalisation of classical ASP to FASP, and we will develop an implementation based on bilevel linear programming for this type of programs.Second, we will combine the paradigms of fuzzy logic and autoepistemic logic into fuzzy autoepistemic logic, and show that the latter generalises FASP.Since the language of (fuzzy) autoepistemic logic is much more expressive than the theories we need to represent (fuzzy) answer set programs, this could serve as a useful basis for defining or comparing extensions to the basic language of (F)ASP.Moreover, we show that many important properties from classical autoepistemic logic remain valid when generalising to fuzzy autoepistemic logic.Finally, we will investigate relationships between fuzzy autoepistemic logic and fuzzy modal logics, generalising well-known links beween autoepistemic logic and several classical modal logic systems.In particular we will generalise Levesque's logic of only knowing to the many-valued case, and show that the correspondence with autoepistemic logic is preserved under this generalisation; stable expansions (and hence answer sets) correspond to a particular type of valid sentences in this logic.Moreover we will provide a sound and complete axiomatisation for this many-valued logic of only knowing.To summarise, in this thesis we will introduce several systems of nonmonotonic reasoning when properties may be graded and investigate their properties, complexity of appropriate decision problems and relations among them.