Fuzzy Description Logics from a Mathematical Fuzzy Logic point of view

Abstract

Description Logic is a formalism that is widely used in the framework of Knowledge Representation and Reasoning in Artificial Intelligence. They are based on Classical Logic in order to guarantee the correctness of the inferences on the required reasoning tasks. It is indeed a fragment of First Order Predicate Logic whose language is strictly related to the one of Modal Logic. Fuzzy Description Logic is the generalization of the classical Description Logic framework thought for reasoning with vague concepts that often arise in practical applications.

Fuzzy Description Logic has been investigated since the last decade of the 20th century. During the first fifteen years of investigation their semantics has been based on Fuzzy Set Theory. A semantics based on Fuzzy Set Theory, however, has been shown to have some counter-intuitive behavior, due to the fact that the truth function for the implication used is not the residuum of the truth function for the conjunction. In the meanwhile, Fuzzy Logic has been given a formal framework based on Many-valued Logic. This framework, called Mathematical Fuzzy Logic, has been proposed has the kernel of a mathematically well founded Fuzzy Logic.

In this dissertation we propose a Fuzzy Description Logic whose semantics is based on Mathematical Fuzzy Logic as its mathematically well settled kernel. To this end we provide a novel notation that is strictly related to the notation that is used in Mathematical Fuzzy Logic. After having settled the notation, we investigate the hierarchies of description languages over different-“t” norm based semantics and the reductions that can be performed between reasoning tasks. The new framework that we establish gives us the possibility to systematically investigate the relation of Fuzzy Description Logic to Fuzzy First Order Logic and Fuzzy Modal Logic. Next we provide some (un)decidability results for the case of infinite “t”-norm based semantics with or without knowledge bases. Finally we investigate the complexity bounds of reasoning tasks without knowledge bases for basic Fuzzy Description Logics over finite “t”-norms.

El trabajo desarrollado en esta tesis es una propuesta de sistematizar la formalización de las Lógicas de la Descripción Fuzzy a partir de la Lógica Difusa Matemática. Para ello se define un lenguaje para las Lógicas de la Descripción Fuzzy que extiende el lenguaje de la primera tradición de esta disciplina para adaptarlo al lenguaje más propio de la Lógica Difusa Matemática.

Desde el punto de vista semántico, la teoría de conjuntos borrosos cede el paso a una semántica algebraica, que es la que se utiliza en la Lógica Difusa Matemática y que resuelve las consecuencias poco intuitivas que tenía la semántica tradicional.

A partir de esta formalización, se tratan temas que eran tradicionales en las Lógicas de la Descripción clásicas como son las jerarquías de inclusiones entre lenguajes de la descripción y la relación de las Lógicas de la Descripción Fuzzy con la Lógica Difusa de primer orden por un lado y la Lógica Difusa Multi-modal por el otro.

En relación a problemas de decidibilidad se demuestra que la satisfacción y la subsunción de conceptos en el lenguaje ALE bajo una semántica basada en la Lógica del Producto son problemas decidibles. También se demuestra que la consistencia de bases de conocimiento en el lenguaje ALC bajo una semántica basada en la Lógica de Lukasiewicz es un problema indecidible.

En relación a problemas de complejidad computacional se demuestra que satisfacción y validez de fórmulas en la Lógica Modal minimal de Lukasiewicz con valores finitos son problemas PSPACE-completos. También se demuestra que la satisfacción y subsunción de conceptos en el lenguaje IALCED bajo una semántica basada en cualquier lógica difusa con valores finitos son problemas PSPACE-completos.

Otra contribución de nuestro trabajo es el estudio sistemático de algoritmos de decisión para la satisfacción y subsunción de conceptos en el lenguaje IALCED, respecto a modelos “witnessed", basados en una reducción de es- tos problemas a los problemas de satisfacción y consecuencia en la lógica proposicional correspondiente.