Logique de description

Les logiques de description utilisent les notions de concept, de rôle et d'individu. Un concept correspond à une « classe d'éléments » et est interprété comme un ensemble dans un univers donné. Les rôles correspondent aux « liens entre les éléments » et sont interprétés comme des relations binaires sur un univers donné. Les individus correspondent aux éléments d'un univers donné. La sémantique des logiques de description est définie comme suit :

Définition 1 :

Soit ${\displaystyle CON=\lbrace C1,C2,\dots \rbrace }$ un ensemble fini de concepts atomiques, ${\displaystyle ROL=\lbrace R1,R2,\dots \rbrace }$ un ensemble fini de rôles atomiques et ${\displaystyle IND=\lbrace a1,a2,\dots \rbrace }$ un ensemble fini d'individus. Si ${\displaystyle CON}$, ${\displaystyle ROL}$, ${\displaystyle IND}$ sont disjoints deux à deux, ${\displaystyle {\mathcal {S}}=\langle CON,ROL,IND\rangle }$ est une signature. Une fois qu'une signature ${\displaystyle {\mathcal {S}}}$ est fixée, une interprétation ${\displaystyle {\mathcal {I}}}$ pour ${\displaystyle {\mathcal {S}}}$ est un couple ${\displaystyle {\mathcal {I}}=\langle \Delta ^{\mathcal {I}},\cdot ^{\mathcal {I}}\rangle }$, où :

• ${\displaystyle \Delta ^{\mathcal {I}}}$ est un ensemble non vide, le domaine de l'interprétation.
• ${\displaystyle \cdot ^{\mathcal {I}}}$ est une fonction affectant :
  • un élément ${\displaystyle a_{i}^{\mathcal {I}}\in \Delta ^{\mathcal {I}}}$ à chaque individu ${\displaystyle a_{i}\in IND}$;
  • un sous-ensemble ${\displaystyle C_{i}^{\mathcal {I}}\subseteq \Delta ^{\mathcal {I}}}$ à chaque concept atomique ${\displaystyle C_{i}\in CON}$;
  • et une relation ${\displaystyle R_{i}^{\mathcal {I}}\subseteq \Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}}}$ à chaque rôle atomique ${\displaystyle R_{i}\in ROL}$.

En d'autres termes, une interprétation de la logique de description n'est rien de plus qu'un modèle pour un type particulier de signature du premier ordre, où seuls les prédicats unaires et binaires sont autorisés, et où l'ensemble des symboles de fonction est vide.

Typiquement, la base de connaissances standard utilisée par les logiques de description est définie de la manière suivante :

Définition 2 :

Étant donné un langage de description ${\displaystyle {\mathcal {L}}}$ et une signature ${\displaystyle {\mathcal {S}}}$, une base de connaissances ${\displaystyle \Sigma }$ dans ${\displaystyle {\mathcal {L}}}$ est une paire ${\displaystyle \Sigma =\langle T,A\rangle }$ telle que :

• ${\displaystyle T}$ est la T(erminologique)-Box, un ensemble fini, qui peut être vide, d'expressions appelées GCI (General Concept Inclusion) de la forme ${\displaystyle C_{1}\sqsubseteq C_{2}}$ où ${\displaystyle C_{1}}$ et ${\displaystyle C_{2}}$ sont des concepts sans restriction. ${\displaystyle C_{1}{\dot {=}}C_{2}}$ est une notation pour ${\displaystyle C_{1}\sqsubseteq C_{2}}$ et ${\displaystyle C_{2}\sqsubseteq C_{1}}$. Les formules de ${\displaystyle T}$ sont appelées axiomes terminologiques.
• ${\displaystyle A}$ est la A(ssertion)-Box, un ensemble fini, qui peut être vide, d'expressions de la forme ${\displaystyle a:C}$ ou ${\displaystyle (a,b):R}$, où ${\displaystyle C}$ est un concept sans restriction, ${\displaystyle R}$ est un rôle qui n'est pas nécessairement atomique, et ${\displaystyle a}$,${\displaystyle b}$ appartiennent à ${\displaystyle IND}$. Les formules de ${\displaystyle A}$ sont appelées des assertions.

Les axiomes terminologiques ont été pensés à l'origine comme des définitions, et nombre de conditions plus restrictives leur ont été imposées. Les deux restrictions les plus importantes sont les suivantes :

• simplicité des axiomes terminologiques : dans tous les axiomes terminologiques ${\displaystyle C_{1}\sqsubseteq C_{2}}$, ${\displaystyle C_{1}}$ est un concept atomique dans ${\displaystyle CON}$, et chaque concept atomique dans ${\displaystyle CON}$ apparaît au plus une fois dans la partie gauche d'un axiome terminologique de la T-Box.
• acyclicité des définitions : le graphe obtenu en affectant un nœud ${\displaystyle n_{A}}$ à chaque concept atomique ${\displaystyle A}$ de la T-Box, et en créant un arc orienté entre deux nœuds ${\displaystyle n_{A}}$ et ${\displaystyle n_{B}}$ s'il existe un axiome terminologique ${\displaystyle C_{1}\sqsubseteq C_{2}}$ dans ${\displaystyle T}$ tel que ${\displaystyle A}$ apparaisse dans ${\displaystyle C_{1}}$ et ${\displaystyle B}$ dans ${\displaystyle C_{2}}$, ne doit pas contenir de cycle.

Ces restrictions sont liées à l'idée de considérer les axiomes terminologiques comme des définitions de concepts.

Les logiques de descriptions ont une base commune enrichie de différentes extensions (voir tableau ci-dessous). On peut dès lors avoir des concepts complexes composés de concepts atomiques, et de même pour les rôles.

Lettre	Constructeur	Syntaxe	Sémantique
${\displaystyle {\mathcal {AL}}}$	nom de concept	${\displaystyle C}$	${\displaystyle C^{\mathcal {I}}}$
${\displaystyle {\mathcal {AL}}}$	nom de rôle	${\displaystyle R}$	${\displaystyle R^{\mathcal {I}}}$
${\displaystyle {\mathcal {AL}}}$	top	${\displaystyle \top }$	${\displaystyle \Delta ^{\mathcal {I}}}$
${\displaystyle {\mathcal {AL}}}$	conjonction	${\displaystyle C_{1}\sqcap C_{2}}$	${\displaystyle C_{1}^{\mathcal {I}}\cap C_{2}^{\mathcal {I}}}$
${\displaystyle {\mathcal {AL}}}$	quantificateur universel	${\displaystyle \forall R.C}$	${\displaystyle \lbrace d_{1}\in \Delta ^{\mathcal {I}}\mid \forall d_{2}\in \Delta ^{\mathcal {I}}.(R^{\mathcal {I}}(d_{1},d_{2})\rightarrow d_{2}\in C^{\mathcal {I}})\rbrace }$
${\displaystyle {\mathcal {C}}}$	négation de concepts non nécessairement primitifs	${\displaystyle \neg C}$	${\displaystyle \Delta ^{\mathcal {I}}\setminus C^{\mathcal {I}}}$
${\displaystyle {\mathcal {U}}}$	disjonction	${\displaystyle C_{1}\sqcup C_{2}}$	${\displaystyle C_{1}^{\mathcal {I}}\cup C_{2}^{\mathcal {I}}}$
${\displaystyle {\mathcal {E}}}$	quantificateur existentiel typé	${\displaystyle \exists R.C}$	${\displaystyle \lbrace d_{1}\in \Delta ^{\mathcal {I}}\mid \exists d_{2}\in \Delta ^{\mathcal {I}}.(R^{\mathcal {I}}(d_{1},d_{2})\wedge d_{2}\in C^{\mathcal {I}})\rbrace }$
${\displaystyle {\mathcal {N}}}$	restriction de cardinalité	${\displaystyle (\geq n~R)}$ ${\displaystyle (\leq n~R)}$	${\displaystyle \lbrace d_{1}\in \Delta ^{\mathcal {I}}\mid \lbrace d_{2}\vert R^{\mathcal {I}}(d_{1},d_{2})\rbrace \vert \geq n\rbrace }$ ${\displaystyle \lbrace d_{1}\in \Delta ^{\mathcal {I}}\mid \lbrace d_{2}\vert R^{\mathcal {I}}(d_{1},d_{2})\rbrace \vert \leq n\rbrace }$
${\displaystyle {\mathcal {Q}}}$	restriction de cardinalité qualifiée	${\displaystyle (\geq n~R.C)}$ ${\displaystyle (\leq n~R.C)}$	${\displaystyle \lbrace d_{1}\in \Delta ^{\mathcal {I}}\mid \lbrace d_{2}\vert R^{\mathcal {I}}(d_{1},d_{2}),d_{2}\in C^{\mathcal {I}}\rbrace \vert \geq n\rbrace }$ ${\displaystyle \lbrace d_{1}\in \Delta ^{\mathcal {I}}\mid \lbrace d_{2}\vert R^{\mathcal {I}}(d_{1},d_{2}),d_{2}\in C^{\mathcal {I}}\rbrace \vert \leq n\rbrace }$
${\displaystyle {\mathcal {O}}}$	un-de	${\displaystyle \lbrace a_{1},\dots ,a_{n}\rbrace }$	${\displaystyle \lbrace d\in \Delta ^{\mathcal {I}}\mid d=a_{i}^{\mathcal {I}}{\texttt {~pour~un~}}a_{i}\rbrace }$
${\displaystyle {\mathcal {B}}}$	role filler	${\displaystyle \exists R.\lbrace a\rbrace }$	${\displaystyle \lbrace d\in \Delta ^{\mathcal {I}}\mid R^{\mathcal {I}}(d,a^{\mathcal {I}})\rbrace }$
${\displaystyle {\mathcal {R}}}$	conjonction de rôles	${\displaystyle R_{1}\sqcap R_{2}}$	${\displaystyle R_{1}^{\mathcal {I}}\cap R_{2}^{\mathcal {I}}}$
${\displaystyle {\mathcal {I}}}$	rôles inverses	${\displaystyle R^{-1}}$	${\displaystyle \lbrace (d_{1},d_{2})\in \Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}}\mid R^{\mathcal {I}}(d_{2},d_{1})\rbrace }$
${\displaystyle {\mathcal {H}}}$	hiérarchie des rôles	${\displaystyle R_{1}\sqsubseteq R_{2}}$	${\displaystyle R_{1}^{\mathcal {I}}\subseteq R_{2}^{\mathcal {I}}}$
${\displaystyle {\mathcal {R^{+}}}}$	transitivité des rôles	${\displaystyle R^{+}}$	Plus petite relation transitive contenant ${\displaystyle R^{\mathcal {I}}}$

L'une des premières logiques de description est le langage ${\displaystyle {\mathcal {FL^{-}}}}$ [Brachman and Levesque, 1984], qui est défini comme une logique de description permettant l'utilisation des quantificateurs universels, de la conjonction, et des quantificateurs existentiels de la forme ${\displaystyle \exists R.\top }$. Le langage ${\displaystyle {\mathcal {FL^{-}}}}$ a été proposé comme un formalisme pour la sémantique des cadres de Minsky. La conjonction de concepts est implicite dans la structure d'un cadre, qui requiert un ensemble de conditions pour être satisfait. La quantification des rôles permet de caractériser les slots.

La logique ${\displaystyle {\mathcal {AL}}}$ [Schmidt-Schauss and Smolka, 1991] a étendu la logique ${\displaystyle {\mathcal {FL^{-}}}}$ en y ajoutant la négation des concepts atomiques. Cette logique peut être considérée comme la logique de base des autres logiques de description.

Les logiques de description qui existent sont des combinaisons des différents éléments du tableau ci-dessus. Par exemple, si l'on rajoute la négation complète ${\displaystyle {\mathcal {C}}}$ à la logique ${\displaystyle {\mathcal {AL}}}$, on obtient la logique ${\displaystyle {\mathcal {ALC}}}$.

Certaines logiques sont équivalentes, notamment ${\displaystyle {\mathcal {ALC}}}$ et ${\displaystyle {\mathcal {ALUE}}}$. Ces deux logiques augmentées par ${\displaystyle {\mathcal {R}}^{+}}$sont notées ${\displaystyle {\mathcal {S}}}$. Les langages utilisés par OWL en sont une extension, respectivement ${\displaystyle {\mathcal {SHIF}}}$ pour OWL-Lite et ${\displaystyle {\mathcal {SHOIN}}}$ pour OWL-DL.

En LD, la notion d'inférence est décrite comme ci-dessous:

Définition 3 :

Soit ${\displaystyle {\mathcal {I}}}$ une interprétation et ${\displaystyle \varphi }$ un axiome terminologique ou une assertion. Alors ${\displaystyle {\mathcal {I}}}$ modélise ${\displaystyle \varphi }$ (notation ${\displaystyle {\mathcal {I}}\models \varphi }$) si :

• ${\displaystyle \varphi =C_{1}\sqsubseteq C_{2}}$ et ${\displaystyle C_{1}^{\mathcal {I}}\subseteq C_{2}^{\mathcal {I}}}$, ou
• ${\displaystyle \varphi =a:C}$ et ${\displaystyle a^{\mathcal {I}}\in C^{\mathcal {I}}}$, ou
• ${\displaystyle \varphi =(a,b):R}$ et ${\displaystyle (a^{\mathcal {I}},b^{\mathcal {I}})\in R^{\mathcal {I}}}$.

Soit ${\displaystyle \Sigma =\langle T,A\rangle }$ une base de connaissance et ${\displaystyle {\mathcal {I}}}$ une interprétation, alors ${\displaystyle {\mathcal {I}}}$ est un modèle de ${\displaystyle \Sigma }$ (notation, ${\displaystyle {\mathcal {I}}\models \Sigma }$) si pour tous ${\displaystyle \varphi \in T\cup A,{\mathcal {I}}\models \varphi }$. Nous disons dans ce cas que ${\displaystyle {\mathcal {I}}}$ est un modèle de la base de connaissance ${\displaystyle \Sigma }$. Étant donné une base de connaissance ${\displaystyle \Sigma }$ et un axiome terminologique ou une assertion ${\displaystyle \varphi }$, ${\displaystyle \Sigma \models \varphi }$ si pour tout modèle ${\displaystyle {\mathcal {I}}}$ de ${\displaystyle \Sigma }$ nous avons ${\displaystyle {\mathcal {I}}\models \varphi }$.

• (en) Description Logics maintenu par Carsten Lutz
• (en) Introduction to Description Logics DL course par Enrico Franconi, Faculty of Computer Science, Free University of Bozen-Bolzano, Italy
• (en) Navigator on Description Logic Complexity
• (fr) Une introduction aux logiques de description