Lógica de descripción

Un concepto en la jerga de DL se refiere a una clase en OWL. Un rol en la jerga de DL es una propiedad en OWL.

OWL no necesita la Suposición de Nombres Únicos (UNA por Unique Name Assumption).

La sintaxis de estas lógicas soportan la descripción lógica de conceptos, roles (relaciones) e individuos, donde los conceptos y roles pueden ser combinados, usando una variedad de operadores, para formar expresiones más complejas. Los operadores soportados por las lógicas de descripción, normalmente incluyen algunas o todas las conectivas lógicas estándares juntamente con uno o ambos operadores relacionales (cuantificadores universales y existenciales llamados restricciones de valor y restricciones existenciales).

Formalmente una terminología en ${\displaystyle {\mathcal {ALC}}}$ está definida por la siguiente formación de reglas:

• Los axiomas son de la forma:

${\displaystyle C\doteq D\mid C\sqsubseteq D}$

donde C y D son las expresiones de concepto.

• La expresiones de concepto de la forma:

${\displaystyle CN\mid \top \mid \bot \mid \lnot C\mid C\sqcap D\mid C\sqcup D\mid \exists R.C\mid \forall R.C}$

CN es un nombre de concepto (conceptos atómicos) R es una expresión de rol.

El nombre de concepto ${\displaystyle \top }$ (top) representa el concepto más general. El nombre de concepto ${\displaystyle \bot }$ (bottom) representa el concepto menos general.

La Semántica busca explicar la relación que existe entre la sintaxis del lenguaje y los modelos previstos del dominio, dando significado a las expresiones, el cual es dado por el modelo teórico semántico. Este modelo teórico fue propuesto por Tarski, donde los conceptos y roles se refieren a conjuntos de objetos en el dominio de interés y las relaciones entre ellos.

Formalmente el modelo teórico se da por: ${\displaystyle {\mathcal {I}}=(\Delta ^{\mathcal {I}},\cdot ^{\mathcal {I}})}$ el cual consta de un conjunto no vacío ${\displaystyle \Delta ^{\mathcal {I}}}$ llamado el dominio de ${\displaystyle {\mathcal {I}}}$ y una función ${\displaystyle \cdot ^{\mathcal {I}}}$ (la función de interpretación de ${\displaystyle {\mathcal {I}}}$) que asigna a cada concepto un subconjunto de ${\displaystyle \Delta ^{\mathcal {I}}}$, cada rol a un subconjunto de ${\displaystyle \Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}}}$ y a cada individuo un elemento de ${\displaystyle \Delta ^{\mathcal {I}}}$, de tal manera que:

${\displaystyle \top ^{\mathcal {I}}=\Delta ^{\mathcal {I}}}$

${\displaystyle \bot ^{\mathcal {I}}=\emptyset }$

${\displaystyle (\lnot C)^{\mathcal {I}}=\Delta ^{\mathcal {I}}\backslash C^{\mathcal {I}}}$

${\displaystyle (C\sqcap D)^{\mathcal {I}}=C^{\mathcal {I}}\cap D^{\mathcal {I}}}$

${\displaystyle (C\sqcup D)^{\mathcal {I}}=C^{\mathcal {I}}\cup D^{\mathcal {I}}}$

${\displaystyle (\exists R.C)^{\mathcal {I}}=\{d\in \Delta ^{\mathcal {I}}\mid \exists e\in \Delta ^{\mathcal {I}}:(d,e)\in R^{\mathcal {I}}\land e\in C^{\mathcal {I}}\}}$

${\displaystyle (\forall R.C)^{\mathcal {I}}=\{d\in \Delta ^{\mathcal {I}}\mid \forall e\in \Delta ^{\mathcal {I}}:(d,e)\in R^{\mathcal {I}}\to e\in C^{\mathcal {I}}\}}$

Es decir:

• Un concepto es interpretado como un conjunto de individuos
• Los roles son interpretados como conjuntos de pares de individuos.
• Los conceptos atómicos se interpretan como subconjuntos del dominio de la interpretación.

Mientras que la Semántica de los constructores son entonces especificados por definiciones de conjunto de individuos denotados por cada constructor. Por ejemplo:

• ${\displaystyle C\sqcap D}$ es el conjunto de individuos obtenidos por la intersección de conjuntos de individuos denotados por C y D, respectivamente.
• ${\displaystyle \forall R.C}$ es el conjunto de individuos que están en la relación R con los individuos que pertenecen al conjunto denotado por el concepto C.

El poder expresivo de una lógica de descripción es la capacidad para representar “conocimiento” acerca del dominio y depende de la riqueza de su lenguaje.

El lenguaje de la lógica ${\displaystyle {\mathcal {ALC}}}$ no es muy expresivo. Para comprobarlo basta ver estos ejemplos de “información” básica sobre un dominio sencillo no expresable en ${\displaystyle {\mathcal {ALC}}}$:

• “Una mujer que tiene exactamente dos hijos” (no es posible expresar restricciones numéricas).
• “Todo hombre es hijo de una mujer” (no es posible expresar el inverso de un rol).
• “La madre del padre es la abuela” (no es posible expresar composición de roles).

Es necesario extender el lenguaje de ${\displaystyle {\mathcal {ALC}}}$, pero añadiendo los elementos necesarios de forma que la complejidad computacional no sea intratable, ya que queremos poder razonar con esa lógica y, en particular, disponer de los algoritmos mínimos de satisfactibilidad, subsumición y consistencia. Veamos los constructores más importantes utilizados para extender el lenguaje ${\displaystyle {\mathcal {ALC}}}$ y también algunos de los sistemas obtenidos extendiéndola.

• Restricciones numéricas ${\displaystyle ({\mathcal {N}})}$ : ${\displaystyle \geq n\ R\mid \leq n\ R}$
• Restricciones numéricas cualificadas Error al representar (SVG (MathML puede ser habilitado mediante un plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «http://localhost:6011/es.wikipedia.org/v1/»:): {\displaystyle (\mathcal{Q})}  : ${\displaystyle \geq n\ R.C\mid \leq n\ R.C}$
• Restricciones Funcionales ${\displaystyle ({\mathcal {F}})}$ : ${\displaystyle \leq 1\ R}$
• Nominales ${\displaystyle ({\mathcal {O}})}$ : ${\displaystyle a_{1},\ldots ,a_{n}}$
• Dominios concretos: Un dominio concreto D es un conjunto ${\displaystyle \Delta ^{(D)}}$ (el dominio) más un conjunto pred(D) de los nombres de predicado de D. Cada nombre de predicado P de D se asocia con una aridad n y un predicado n-ario de ${\displaystyle \Delta ^{(D)}}$.

Ejemplo: el dominio concreto ${\displaystyle \mathbb {N} }$, tiene como dominio el conjunto ${\displaystyle \mathbb {N} }$ de los números naturales y pred(${\displaystyle \mathbb {N} }$) el conjunto de los predicados binarios < ≤ > ≥ .

Las lógicas de descripción mucho más expresivas también emplean constructores de roles, dado que los roles se interpretan como relaciones binarias; esto implica definir constructores cuya Semántica es la de las operaciones sobre relaciones. Donde: si R y S son descripciones de rol (atómico) también lo son:

• Unión de roles: ${\displaystyle R\sqcup S}$
• Intersección de roles: ${\displaystyle R\sqcap S}$
• Complemento de rol: ${\displaystyle \lnot R}$
• Composición de roles: ${\displaystyle R\circ S}$
• Rol inverso ${\displaystyle ({\mathcal {I}})}$ : ${\displaystyle R^{-}}$
• Rol transitivo: ${\displaystyle R^{+}}$

La terminología también permite incluir jerarquía de roles ${\displaystyle ({\mathcal {H}})}$ donde los axiomas son de la forma:

${\displaystyle R\doteq S\mid R\sqsubseteq S}$

La semántica para las expresivas lógicas de descripción expuestas anteriormente se da; de la siguiente manera:

Axiomas	Semántica	Ejemplo
${\displaystyle \geq n\ R}$	${\displaystyle \{x\mid \#\{y\mid R^{\mathcal {I}}(x,y)\}\geq n\}}$	${\displaystyle \geq 2\ tieneHijo}$
${\displaystyle \leq n\ R}$	${\displaystyle \{x\mid \#\{y\mid R^{\mathcal {I}}(x,y)\}\leq n\}}$	${\displaystyle \leq 2\ tieneHijo}$
${\displaystyle \geq n\ R.C}$	${\displaystyle \{x\mid \#\{y\mid R^{\mathcal {I}}(x,y)\land C^{\mathcal {I}}(y)\}\geq n\}}$	${\displaystyle \geq 3\ tieneHijo.Hombre}$
${\displaystyle \leq n\ R.C}$	${\displaystyle \{x\mid \#\{y\mid R^{\mathcal {I}}(x,y)\land C^{\mathcal {I}}(y)\}\leq n\}}$	${\displaystyle \leq 3\ tieneHijo.Mujer}$
${\displaystyle a_{1}\ldots a_{n}}$	${\displaystyle \{a_{1}^{\mathcal {I}},\ldots ,a_{n}^{\mathcal {I}}\}}$	${\displaystyle \{Maria,John\}}$
${\displaystyle R\sqcup S}$	${\displaystyle R^{\mathcal {I}}\cup S^{\mathcal {I}}}$	${\displaystyle tieneHijo\sqcup tieneHija}$
${\displaystyle R\sqcap S}$	${\displaystyle R^{\mathcal {I}}\cap S^{\mathcal {I}}}$	${\displaystyle tieneHijo\sqcap tieneHija}$
${\displaystyle \lnot R}$	${\displaystyle (\Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}})\mid R^{\mathcal {I}}}$	${\displaystyle \lnot tieneAmigo}$

Axiomas	Semántica	Ejemplo
${\displaystyle R\circ S}$	${\displaystyle \{(a,c)\in \Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}}\mid \exists b.(a,b)\in R^{\mathcal {I}}\land (b,c)\in S^{\mathcal {I}}\}}$	${\displaystyle tieneHijo\circ tieneAmigo}$
${\displaystyle R^{-}}$	${\displaystyle \{(b,a)\in \Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}}\mid (a,b)\in R^{\mathcal {I}}\}}$	${\displaystyle tienePadre^{-}}$
${\displaystyle R^{+}}$	${\displaystyle \bigcup _{i\geq 1}(R^{\mathcal {I}})^{i}}$	${\displaystyle ancestro^{+}}$
${\displaystyle R\doteq S}$	${\displaystyle R^{\mathcal {I}}=S^{\mathcal {I}}}$	${\displaystyle tieneHijo\doteq tienePadre^{-}}$
${\displaystyle R\sqsubseteq S}$	${\displaystyle R^{\mathcal {I}}\subseteq S^{\mathcal {I}}}$	${\displaystyle ancestro^{+}\sqsubseteq ancestro}$

Supongamos que tenemos un lenguaje descriptivo para un dominio, por ejemplo ${\displaystyle {\mathcal {ALC}}}$, y que se ha definido una TBox(axiomas terminológicos) para modelar un dominio. Si se define un nuevo concepto es importante saber si es consistente o contradictorio con el TBox. Esta propiedad se conoce como el concepto satisfacible (o respectivamente insatisfacible) con respecto al TBox. También puede ser necesario saber si un concepto es más general que otro, si son equivalentes o si son disjuntos. La formalización de estas propiedades es la siguiente:

Supongamos que ${\displaystyle {\mathcal {T}}}$ es un TBox, C y D conceptos:

• C es satisfactible con respecto a ${\displaystyle {\mathcal {T}}}$ si existe un modelo ${\displaystyle {\mathcal {I}}}$ tal que ${\displaystyle {\mathcal {T}}(C)^{\mathcal {I}}\neq \emptyset }$.
• C es subsumido por D con respecto a ${\displaystyle {\mathcal {T}}}$ si para todo modelo ${\displaystyle {\mathcal {I}}}$ de ${\displaystyle {\mathcal {T}}}$, tenemos que ${\displaystyle (C)^{\mathcal {I}}\subseteq (D)^{\mathcal {I}}}$. Esto se escribe ${\displaystyle {\mathcal {T}}\models C\sqsubseteq D}$.

Una vez definida una TBox, al definir el ABox, las propiedades más importantes que habrá que verificar son las de la consistencia del Abox y el TBox , y la derivación de una instanciación a partir del ABox. Veamos formalmente estos conceptos:

Supongamos que ${\displaystyle {\mathcal {T}}}$ es un TBox, A es un ABox, C un concepto y o un nombre de individuo:

• A es consistente con respecto a ${\displaystyle {\mathcal {T}}}$ si existe una interpretación que es modelo de ${\displaystyle {\mathcal {T}}}$ y de A.
• o:C se deriva de ${\displaystyle {\mathcal {T}}}$ y A si todo modelo ${\displaystyle {\mathcal {I}}}$ de ${\displaystyle {\mathcal {T}}}$ cumple ${\displaystyle (o)^{\mathcal {I}}\in (C)^{\mathcal {I}}}$. esto es ${\displaystyle ({\mathcal {T}},A\models o:C)}$.

Las lógicas de descripción fueron pensadas como sistemas formales para representar conocimiento, y esto significa ir más allá de almacenar terminologías y descripciones. En particular, significa poder derivar hechos implícitos a partir de los dados. Por este motivo la implementación de procesos de inferencia debe tener en cuenta la posibilidad de usar algoritmos de inferencia óptimos. En el estudio de tales algoritmos el punto de partida es conocer su complejidad computacional (por ejemplo la complejidad EXPTIME y PSPACE).

Encontrar algoritmos de decisión para los problemas de inferencia como satisfactibilidad, subsumición y consistencia en ABoxes para lógicas de descripción expresivas y con la menor complejidad posible, de forma que la implementación computacional sea afrontable, la cual es todo un reto.

La búsqueda de estos procedimientos de decisión ha sido uno de los objetivos fundamentales en el desarrollo de las lógicas de descripción. Una de las maneras de obtenerlos es estudiando la conexión de las lógicas de descripción con otras lógicas conocidas. Es el caso de la decidibilidad en ${\displaystyle {\mathcal {ALC}}}$ y en todas sus extensiones que se obtienen añadiendo constructores que en la LPO se pueden expresar con dos variables. Sin embargo, la complejidad del procedimiento de decisión obtenido de esta manera es normalmente mayor del que realmente se necesita; por ejemplo el problema de satisfactibilidad para la LPO con dos variables es NEXPTIME (que es una complejidad muy grande, aunque todavía es decidible) mientras que en ${\displaystyle {\mathcal {ALC}}}$ es PSPACE-hard (es una complejidad menor). Otra manera de estudiar la complejidad es usando la conexión con las lógicas modales proposicionales.

En la siguiente tabla se presentara las principales extensiones de ${\displaystyle {\mathcal {ALC}}}$, especificando las nuevas propiedades expresables en la extensión y los límites para la complejidad computacional.

DL	Propiedad expresable en la lógica	Complejidad
${\displaystyle {\mathcal {ALC}}}$	lógica de descripción básica	PSPACE
${\displaystyle {\mathcal {ALCN}}}$	+ restricciones numéricas no calificadas ${\displaystyle ({\mathcal {N}})}$	PSPACE
${\displaystyle {\mathcal {ALC}}}$reg	+ expresiones regulares sobre roles (reg)	EXPTIME
${\displaystyle {\mathcal {ALCI}}}$reg	+ inverso de roles ${\displaystyle ({\mathcal {I}})}$	EXPTIME
${\displaystyle {\mathcal {ALCFI}}}$reg	+ restricciones funcionales sobre roles atómicos ${\displaystyle ({\mathcal {F}})}$	EXPTIME
${\displaystyle {\mathcal {ALCQI}}}$reg	+ restricciones numéricas calificadas ${\displaystyle ({\mathcal {Q}})}$	EXPTIME
${\displaystyle {\mathcal {ALCQO}}}$reg	+ un alfabeto para los objetos del dominio ${\displaystyle ({\mathcal {O}})}$	EXPTIME
${\displaystyle {\mathcal {SHIQ}}}$	${\displaystyle {\mathcal {ALCQI}}}$ + roles transitivos + inclusión roles	EXPTIME
${\displaystyle {\mathcal {SHOIN}}}$	+ restricciones numéricas no calificadas ${\displaystyle ({\mathcal {N}})}$	EXPTIME
${\displaystyle {\mathcal {SHOIQ}}}$	${\displaystyle {\mathcal {SHIQ}}}$ + nominales	NEXPTIME
${\displaystyle {\mathcal {SHOIN(D)}}}$	${\displaystyle {\mathcal {SHOIN}}}$ + dominios concretos	EXPTIME

https://web.archive.org/web/20080927155748/http://www.trafford.com/07-1729 Este un libro relaciona 16 clases de complejidad algorítmica respecto a espacio y tiempo. Y resuelve algunas igualdades.