# Des logiques de variations avec attributs numériques pour représenter des règles d'adaptation

Nicolas François, Jean Lieber

► To cite this version:

Nicolas François, Jean Lieber. Des logiques de variations avec attributs numériques pour représenter des règles d'adaptation. JIAF-JFPDA Journées d'Intelligence Artificielle Fondamentale (Evènement affilié à PFIA 2025), Jean-Guy Mailly; François Schwarzentruber; Anaëlle Wilczynski, Jul 2025, Dijon, France. hal-05408668

HAL Id: hal-05408668

https://hal.science/hal-05408668v1

Submitted on 10 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Des logiques de variations avec attributs numériques pour représenter des règles d'adaptation*

Nicolas François<fnref n="1" />, Jean Lieber<fnref n="2" />

## Résumé

Les connaissances d'adaptation d'un système de raisonnement à partir de cas (RàPC) sont souvent représentées par des règles d'adaptation qui peuvent être apprises à partir de la base de cas, en se fondant sur plusieurs approches proposées dans la littérature du RàPC. Cependant, la représentation formelle de telles règles a été bien moins étudiée. Cet article introduit un formalisme pour représenter de telles règles, s'appuyant sur un formalisme de couples attributs-valeurs dans lequel sont représentés les cas.

## Mots-clés

raisonnement à partir de cas, représentation des connaissances, adaptation

## Abstract

The adaptation knowledge container of a CBR system is often represented by adaptation rules, that can be learnt from the case base using various approaches proposed in the CBR literature. However, the formal representation of such rules has been much less investigated. This article introduces a formalism for representing such rules, given a formalism that can be used to express cases in an attribute-value formalism.

## Keywords

case-based reasoning, knowledge representation, adaptation

## 1 Introduction

Le raisonnement à partir de cas (RàPC [9]) consiste à résoudre des problèmes en s'appuyant sur la résolution de problèmes antérieurs, appelés cas. L'adaptation est considérée, pour certains membres de la communauté du RàPC, comme un processus clef de ce type de raisonnements ; elle consiste à modifier un cas sélectionné dans la base de cas dans l'optique de la résolution du problème posé. Cet article s'inscrit dans cette tradition et la considère du point de vue de la représentation des connaissances : comment les

connaissances d'adaptation peuvent-elle être représentées dans le cadre du RàPC ?

Pour s'attaquer à cette question, le point de départ a été certains travaux sur l'apprentissage de connaissances d'adaptation (ACA). L'ACA a une longue histoire dans le domaine du RàPC, au moins depuis un article de K. Hanney et M. T. Keane [5]. L'ACA s'appuie en général sur ce qu'on appelle parfois l'heuristique des différences [6] : les différences entre couples de cas dans la base de cas sont utilisées comme ensemble d'apprentissage pour un système d'apprentissage artificiel. En particulier, une notation a été introduite pour représenter de telles différences : elle consiste en expressions de la forme $a^v$ où $a$ est un attribut d'un cas et $v$ est un symbole de variation. Par exemple, dans le domaine culinaire, pour exprimer que, pour une recette de dessert, 2 œufs peuvent être substitués par 1 banane, l'ensemble suivant d'expressions peut être employé :

$$ \{dessert=^1, \#œufs=^2, \#bananes=^1\} $$

Ici, dessert est un attribut booléen : ses valeurs potentielles sont 0 et 1 (assimilées à faux et à vrai), alors que \#œufs et \#bananes sont des attributs à domaines entiers. Cette notation a été utilisée dans des études relative-ment anciennes [1] tout comme dans des travaux plus ré-cents [8]. À cette notation (ou syntaxe), une sémantique peut être associée, donnant naissance à des formalismes logiques, les logiques de variations, dans lesquelles les rè-gles d'adaptation peuvent être représentées.

La section 2 présente des préliminaires portant principalement sur le RàPC. La base de cas et les connaissances du domaine peuvent être représentées dans ce qu'on pourrait qualifier de logique statique ; la section 3 présente la logique statique ($LG, \models$) qui est suffisamment expressive pour représenter des couples attributs-valeurs (avec des attributs booléens ou numériques) et des taxonomies (et au-delà). La section 4 définit la logique des variations ($\Delta LG, \models$) qui s'appuie sur ($LG, \models$) : sa syntaxe, sa sémantique et quelques propriétés simples. La section 5 présente la façon dont des règles d'adaptation peuvent être définies en utilisant cette logique. Pour les résultats de ces sections, il est supposé que les logiques ($LG, \models$) et ($\Delta LG, \models$) s'appuient sur un groupe abélien infini ($\mathcal{G}, +$) ; en particulier, le test de satisfiabilité s'appuie sur cette hypothèse. La section 6 explique comment modifier l'approche sous d'autres hypothèses (p. ex. si ($\mathcal{G}, +$) est un groupe abélien

<footnote n="1">¹ Lycée public Chopin, F-54000 Nancy, France</footnote>

<footnote n="2">² Université de Lorraine, CNRS, LORIA, F-54000 Nancy, France</footnote>

<footnote>*Les auteurs tiennent à remercier les relectrices et relecteurs anonymes pour leurs lectures sérieuses et détaillées. Leurs remarques ont permis d'améliorer la qualité de cet article. Elles ont permis en particulier d'enlever une grosse bêtise énoncée en plein milieu d'une proposition ! Certaines suggestions nous seront utiles pour la rédaction d'articles futurs.</footnote>
fini). La section 7 discute la contribution de cet article, conclut et présente quelques perspectives.

**Remarques :**

- Cet article est une version modifiée d'un article qui va être publié dans les actes d'ICCBR-2025 (la manifestation internationale et annuelle sur le RàPC).

- On peut noter que le contenu de cet article est assez proche de celui publié par les mêmes auteurs dans les JIAF-JFPDA en 2024 [3]. La différence principale entre le travail présenté ici et ce travail précédent est que la logique statique sur laquelle la logique des variations s'appuyait était la logique propositionnelle, alors que la logique statique considérée dans cet article est ($\mathcal{LG}, \models$) qui étend la logique propositionnelle.

- La section 6 est une contribution originale de cet article (elle n'est pas dans l'article d'ICCBR-2025).

- Cet article contient des résultats sans leurs preuves : ces dernières peuvent être trouvées dans la version étendue de cet article, qui est accessible en ligne [4].

# 2 Préliminaires

Cette section présente quelques notations et hypothèses, principalement à propos du RàPC.

## 2.1 Notions et notations mathématiques

B, l'ensemble des booléens, est assimilé à la paire d'entiers $B = \{0, 1\}$ (0 pour faux, 1 pour vrai). $\mathbb{Z}$ est l'ensemble des entiers relatifs. Pour $a, b \in \mathbb{Z}$ avec $a \le b$, $[a, b] = \{n \in \mathbb{Z} | a \le n \le b\}$. $\mathbb{Q}$ est l'ensemble des rationnels.

Un groupe abélien est un couple $(\mathcal{G}, +)$ où $\mathcal{G}$ est un ensemble non vide et $+$ est une loi de composition interne sur $\mathcal{G}$ $(+ : (r, s) \in \mathcal{G} \mapsto r + s \in \mathcal{G})$ telle que (1) elle a un élément neutre noté 0 (pour tout $r \in \mathcal{G}$, $r + 0 = 0 + r = r$), (2) tout $r \in \mathcal{G}$ a un élément symétrique $s (r + s = s + r = 0)$, s est noté $-r$, (3) est associative $((r + s) + t) = r + (s + t)$ pour tous $r, s, t \in \mathcal{G})$, et (4) est commutative $(r + s = s + r)$ pour tous $r, s \in \mathcal{G})$. Pour $r, s \in \mathcal{G}$, $r - s$ est une abréviation de $r + (-s)$.

Pour l'addition usuelle sur les nombres, $(\mathbb{Q}, +)$ et $(\mathbb{Z}, +)$ sont des groupes. $(\{0, 1, 2\}, +)$ n'est pas un groupe puisque $+ n$ est pas interne dans cet ensemble (p. ex. $2 \in \{0, 1, 2\}$ mais $2 + 2 = 4 \notin \{0, 1, 2\}$).

## 2.2 Le RàPC : notions, notations et hypothèses

Ces préliminaires au sujet du RàPC ne reflètent pas toute la variété des systèmes de RàPC. En particulier, dans cet article, un cas est considéré comme un couple problèmesolution. Un problème est, par définition, un élément x d'un ensemble donné $\mathcal{P}$. Une solution est, par définition, un élément y d'un ensemble donné $\mathcal{S}$. Ces deux ensembles $\mathcal{P}$ et $\mathcal{S}$ sont supposés disjoints. On suppose l'existence d'une relation sur $\mathcal{P} \times \mathcal{S}$ qui n'est pas complètement connue pour le système de RàPC, et qui se lit "a pour solution". Un cas est un couple $(x, y) \in \mathcal{P} \times \mathcal{S}$. Un cas correct est un cas $(x, y)$

tel que x a pour solution y. La base de cas BC est un ensemble fini de cas corrects. Un cas de BC est appelé cas source et est noté par $(x^s, y^s)$. Enfin, il est supposé que les cas sources représentent des épisodes spécifiques de résolution de problèmes.

**Modèle de processus.** Une session de RàPC consiste en la résolution d'un problème appelé le problème cible et noté $x^{\text{cible}}$. Un schéma de processus fréquent pour le RàPC consiste en (1) la sélection d'un cas source $(x^s, y^s)$ qui est considéré comme étant similaire à $x^{\text{cible}}$ (étape de remémoration), (2) la modification de ce cas remémoré afin de proposer une solution $y^{\text{cible}}$ de $x^{\text{cible}}$ (étape d'adaptation), et d'autres étapes non considérés dans cet article. Dans certains systèmes de RàPC, plusieurs cas sont remémorés avant d'être adaptés; dans cet article, cependant, on ne considérera que les remémorations et adaptation simples (avec un seul cas remémoré puis adapté).

**Modèle de connaissances.** Un système de RàPC s'appuie sur quatre conteneurs de connaissances. Le premier est la base de cas BC mentionnée plus haut.

Les connaissances du domaine CD expriment des connaissances à propos du vocabulaire avec lequel les cas sont représentés. CD peut être considéré comme un ensemble de contraintes sur ce vocabulaire. Par exemple, si "pomme" et "fruit" appartiennent à ce vocabulaire, la connaissances "Toute pomme est un fruit." indique qu'un cas impliquant une pomme qui n'est pas un fruit est incorrect.

Les connaissances pour la remémoration sont souvent représentées à l'aide d'une distance entre problèmes (il n'en sera guère question dans cet article).

Les connaissances d'adaptation CA sont utilisées durant l'adaptation. Dans cet article, CA est un ensemble de règles d'adaptation ar. De façon générale, une telle règle peut être interprétée comme une fonction qui à $((x^s, y^s), x^{\text{cible}}) \in (\mathcal{P} \times \mathcal{S}) \times \mathcal{P}$ associe $y^{\text{cible}} \in \mathcal{S} \cup \{\text{échec}\}$. Si $y^{\text{cible}} = \text{échec}$, cela signifie que la règle d'adaptation n'est pas applicable au problème d'adaptation $((x^s, y^s), x^{\text{cible}})$. Dans le cas contraire, le cas $(x^{\text{cible}}, y^{\text{cible}})$ n'est pas nécessairement correct : le RàPC est en général un raisonnement hypothétique et le résultat qu'il produit n'est pas nécessairement correct. Afin d'augmenter la plausibilité que ce résultat soit correct, une valeur strictement positive coût est associée à une règle d'adaptation : on considérera que plus coût est bas, plus il est plausible que $(x^{\text{cible}}, y^{\text{cible}})$ soit correct.

**Représentation des connaissances.** BC et CD sont des conteneurs de connaissances à propos de ce qu'est ou n'est pas un cas : un $(x^s, y^s) \in BC$ indique que $y^s$ est une solution correcte de $x^s$, alors qu'une formule $\alpha$ de CD indique une contrainte sur ce qu'un cas correct doit être. Les connaissances d'adaptation, quant à elles, concernent les transformations, comment un cas est modifié en un autre cas.

Pour ces raisons, deux types de logiques pour représenter des connaissances en RàPC sont distinguées : les logiques statiques pour BC et CD et les logiques de variations pour les connaissances d'adaptation.

Dans cet article, la logique statique considérée est $(\mathcal{LG}, \models)$,
qui sera présentée en section 3 et utilisée pour BC et CD. La logique des variations ($\Delta LG, \models$) pour représenter les connaissances d'adaptation s'appuie sur la logique précédente et est présentée en section 4.

# 3 La logique statique ($LG, \models$)

La logique statique peut être n'importe quelle logique clas- sique utilisée en représentation des connaissances, que ce soit la logique propositionnelle, une logique de descrip- tions ou autre. Cependant, l'étude présentée dans cet article s'appuie sur la logique ($LG, \models$) décrite ci-dessous, asso- ciée à une discussion sur son expressivité. Cette logique est paramétrée par un groupe abélien infini ($G, +$).

## 3.1 Syntaxe de ($LG, \models$)

Soit $\mathcal{V}$ un ensemble non vide donné de symboles : les éléments $a$ de $\mathcal{V}$ sont appelés les variables. Un atome de ($LG, \models$) est une expression de la forme $(a = r)$ où $a \in \mathcal{V}$ et $r \in G$. Une formule de ($LG, \models$) est soit un atome soit une expression d'une des formes suivantes : $\perp$, $\top$, $\neg \alpha$, $\alpha \wedge \beta$ et $\alpha \vee \beta$ où $\alpha$ et $\beta$ sont deux formules de cette logique. Les autres connecteurs peuvent être définis de manière usuelle, comme des abréviations. En particulier, le connecteur $\to$ est défini par $\alpha \to \beta = \neg \alpha \vee \beta$. $LG$ est l'ensemble des formules de cette logique. L'ensemble des variables apparaissant dans $\alpha \in LG$ est dénoté par $\mathcal{V}(\alpha)$.

Un littéral est soit un atome (qu'on considérera comme un littéral *positif*) soit de la forme $\neg \alpha$ où $\alpha$ est un atome (ce sera alors un littéral *négatif*). Un cube est une conjonction de littéraux : il a la forme $\ell_1 \wedge \ell_2 \wedge \dots \wedge \ell_p$ où $\ell_k$ est un littéral pour $k \in [1, p]$. Une formule est sous FND (forme normale disjonctive) si c'est une disjonction de cubes : $\gamma_1 \vee \gamma_2 \vee \dots \vee \gamma_q$ où $\gamma_k$ est un cube, pour $k \in [1, q]$.

## 3.2 Sémantique de ($LG, \models$)

Une interprétation $\mathcal{I}$ est une fonction de $\mathcal{V}$ dans $G$. Soit $\Omega$ l'ensemble des interprétations. Pour $\mathcal{I} \in \Omega$ et $\alpha \in LG$, la relation "$\mathcal{I}$ est un modèle de $\alpha$" (dénotée par $\mathcal{I} \models \alpha$) est définie récursivement comme suit (pour $a \in \mathcal{V}$, $r \in G$ et $\alpha, \beta \in LG$) :

- $\mathcal{I} \models \perp$ n'est jamais vrai ;

- $\mathcal{I} \models \top$ est toujours vrai ;

- $\mathcal{I} \models (a = r)$ si $\mathcal{I}(a) = r$ ;

- $\mathcal{I} \models \neg \alpha$ si $\mathcal{I} \not\models \alpha$ ;

- $\mathcal{I} \models \alpha \wedge \beta$ si $\mathcal{I} \models \alpha$ et $\mathcal{I} \models \beta$ ;

- $\mathcal{I} \models \alpha \vee \beta$ si $\mathcal{I} \models \alpha$ ou $\mathcal{I} \models \beta$.

Pour $\alpha \in LG$, soit $M(\alpha)$ l'ensemble des modèles de $\alpha$. $\alpha$ est satisfiable (ou cohérente) si $M(\alpha) \neq \emptyset$ et $\alpha$ est une tautologie si $M(\alpha) = \Omega$. Par exemple, $\perp$ est in- satisfiable et $\top$ est une tautologie. La relation $\models \beta$ signi- fique que $M(\alpha) \subseteq M(\beta)$. La relation $\equiv \beta$ signi- fique que $M(\alpha) = M(\beta)$. Si $B$ est un ensemble de for- mules, $M(B) = \bigcap \{M(\alpha) \mid \alpha \in B\}$. $B \models \alpha$ signifie que $M(B) \subseteq M(\alpha)$.

## 3.3 À propos de l'expressivité de ($LG, \models$)

Chaque variable $a$ de ($LG, \models$) a le même domaine $G$ : pour toute $\mathcal{I} \in \Omega$, $\mathcal{I}(a) \in G$. Une modification de ($LG, \models$)

consiste à préciser le domaine de chaque variable (p. ex. $\mathbb{B}$, $\mathbb{Z}$, $\mathbb{Q}$, un intervalle d'entiers $[m, n]$ ou de rationnels $[r, s]$ —$m, n \in \mathbb{Z}$, $r, s \in \mathbb{Q}$). Par conséquent, ce formalisme contient les formalismes attributs-valeurs (avec des domaines d'attributs limités aux nombres, booléens et types énumérés) et les taxonomies (une taxonomie étant représentée par un ensemble d'implications, p. ex. (apple = 1) $\rightarrow$ (fruit = 1) signifie que toute pomme est un fruit). Pour simplifier la présentation, dans cet article, nous ne considérons que la logique statique ($LG, \models$), considérant que l'extension avec des types de variables différents ne devrait pas poser beaucoup de problèmes de modification.

## 3.4 Représenter des cas dans ($LG, \models$)

Comme indiqué en section 2, les ensembles $\mathcal{P}$ et $\mathcal{S}$ sont supposés disjoints. Cela suggère de partitionner l'ensemble des variables en $\{V_P, V_S\} : V_P$ (resp., $V_S$) est l'ensemble des variables de problèmes (resp., variables de solutions). Ainsi, un problème (resp., une solution) est représenté par une formule dont les variables appartiennent à $V_P$ (resp., à $V_S$). Donc, un cas $(x, y) \in \mathcal{P} \times \mathcal{S}$ peut être écrit $x \wedge y$ : trouver la partie problème $x$ et la partie solution $y$ de $x \wedge y$ est facile puisque $V_P \cap V_S = \emptyset$.

Par ailleurs, il est supposé que les cas sources $(x^s, y^s)$ représentent des expériences spécifiques. Cela signifie que pour tout $(x^s, y^s) \in \mathcal{BC}$, $M(x^s \wedge y^s)$ est un singleton $\{\mathcal{I}^s\}$. Par conséquent, $x^s$ et $y^s$ peuvent être écrits comme conjonctions d'atomes sur toutes les variables de, respectivement, $V_P$ et $V_S$ : $x^s \equiv \bigwedge_{a \in V_P} (a = \mathcal{I}^s(a))$ et $y^s \equiv \bigwedge_{a \in V_S} (a = \mathcal{I}^s(a))$.

# 4 La logique de variations ($\Delta LG, \models$)

Étant donné une logique statique qui peut être utilisée pour représenter des cas et des connaissances du domaine, une logique de variations peut être définie pour représenter, en particulier, des connaissances d'adaptation. Cette section décrit la logique de variations ($\Delta LG, \models$) construite à partir de la logique statique ($LG, \models$) : sa syntaxe, sa sémantique, certaines de ses propriétés et les opérateurs sur ces logiques qui vont être utiles pour représenter des règles d'adaptation.

## 4.1 Syntaxe de ($\Delta LG, \models$)

Pour commencer par un exemple, soit $\varphi = a^{+5} \wedge \neg b^{8\bullet} \wedge b^{2\bullet}$ une formule de cette logique, pour $G = \mathbb{Z}$. $\varphi$ indique un changement de l'attribut $a$ de la valeur $r$, pour un $r \in \mathbb{Z}$, à la valeur $r+5$ et un changement de l'attribut $b$ d'une valeur différente de 8 à la valeur 2. Les expressions $+5$, $8\bullet$ et $\bullet 2$ apparaissant dans $\varphi$ sont appelés symboles de variation. Plus généralement, l'ensemble des symboles de variation est défini par :

$$ \mathcal{D} = \{ \mathbf{+}r, r\bullet, \mathbf{\cdot}r \mid r \in G \} $$

Un symbole de variation additionnel $-r$ est défini comme abréviation de $\mathbf{+}(-r)$.

Un atome de ($\Delta LG, \models$) est une expression de la forme $a^v$ où $a$ est une variable et $v$ est un symbole de variation. Une formule de ($\Delta LG, \models$) est soit un atome de cette logique,
soit d'une des formes suivantes : $\perp, \top, \neg\varphi, \varphi\wedge\psi$ et $\varphi\vee\psi$ où $\varphi$ et $\psi$ sont deux formules de cette logique. Les autres connecteurs sont définies comme des abréviations. L'ensemble des formules est noté par $\Delta\mathcal{L}\mathcal{G}$. Une formule de variations est par définition un élément de $\Delta\mathcal{L}\mathcal{G}$. L'ensemble des variables apparaissant dans $\varphi \in \Delta\mathcal{L}\mathcal{G}$ est noté $\mathcal{V}(\varphi)$.

Les notions de littéraux, positifs ou négatifs, et de cubes, sont similaires à ceux de $(\mathcal{L}\mathcal{G}, \models)$, par exemple, $a^5\bullet \wedge \neg a^{*2} \wedge \neg b^6$ est un cube avec un littéral positif et deux littéraux négatifs. $\perp$ est aussi considéré comme un cube ($\perp$ peut être vu comme la conjonction $A \wedge \neg A$ pour $A$ est un atome fixé de façon arbitraire).

## 4.2 Sémantique de $(\Delta\mathcal{L}\mathcal{G}, \models)$

Chaque symbole de variation est interprété comme une relation binaire sur $\mathcal{G}$. Formellement, à tout $v \in \mathcal{D}$ est associé $\langle v \rangle \subseteq \mathcal{G} \times \mathcal{G}$ défini de la façon suivante (pour $r \in \mathcal{G}$):

$$ 
\begin{align*}
\langle \bullet r \rangle &= \{(x, y) \in \mathcal{G}^2 \mid y = x + r\} \\
\langle r \bullet \rangle &= \{(r, x) \mid x \in \mathcal{G}\} \\
\langle \bullet r \rangle &= \{(x, r) \mid x \in \mathcal{G}\}
\end{align*}
$$

Soit $\Delta\Omega = \Omega \times \Omega$: c'est l'ensemble des interprétations utilisées pour définir la sémantique de $(\Delta\mathcal{L}\mathcal{G}, \models)$ : une interprétation de $\Delta\Omega$ est par conséquent un couple $(\mathcal{I}, \mathcal{J})$ de $\Omega$. Dans la suite, $(\mathcal{I}, \mathcal{J})$ est simplement notée $\mathcal{IJ}$.

La relation affirmant qu'une $\mathcal{IJ} \in \Delta\Omega$ est un modèle de $\varphi \in \Delta\mathcal{L}\mathcal{G}$ est définie récursivement comme suit :

- $\mathcal{IJ} \models a^v$ si $(\mathcal{I}(a), \mathcal{J}(a)) \in \langle v \rangle$, pour tout atome $a^v$ de $(\Delta\mathcal{L}\mathcal{G}, \models)$;

- $\mathcal{IJ} \models \neg\varphi$ si $\mathcal{IJ} \models \varphi$, pour $\varphi \in \Delta\mathcal{L}\mathcal{G}$;

- $\mathcal{IJ} \models \varphi \wedge \psi$ si $\mathcal{IJ} \models \varphi$ et $\mathcal{IJ} \models \psi$, pour $\varphi, \psi \in \Delta\mathcal{L}\mathcal{G}$;

- $\mathcal{IJ} \models \varphi \vee \psi$ si $\mathcal{IJ} \models \varphi$ ou $\mathcal{IJ} \models \psi$, pour $\varphi, \psi \in \Delta\mathcal{L}\mathcal{G}$.

L'ensemble des modèles de $\varphi \in \Delta\mathcal{L}\mathcal{G}$ est noté $\mathcal{M}(\varphi)$. Pour une base de connaissances $\mathcal{B}$ de $(\Delta\mathcal{L}\mathcal{G}, \models)$, $\mathcal{M}(\mathcal{B}) = \bigcap\{\mathcal{M}(\varphi) \mid \varphi \in \mathcal{B}\}$. La relation de conséquence logique est définie comme d'habitude : $\varphi \models \psi$ si $\mathcal{M}(\varphi) \subseteq \mathcal{M}(\psi)$ et $\mathcal{B} \models \varphi$ si $\mathcal{M}(\mathcal{B}) \subseteq \mathcal{M}(\psi)$. De même, $\varphi \equiv \psi$ si $\mathcal{M}(\varphi) = \mathcal{M}(\psi)$. Finalement, $\varphi$ est satisfiable (ou cohérente) si $\mathcal{M}(\varphi) \neq \emptyset$.

Dans l'introduction, un autre symbole de variation a été utilisé : $=r$ (pour $r \in \mathcal{G}$). Il a la sémantique suivante (pour $a \in \mathcal{V}$) : $\mathcal{IJ} \models a^{=r}$ si $\mathcal{I}(a) = \mathcal{J}(a) = r$. Par conséquent, $a^{=r}$ peut être vu comme une abréviation du cube $a^{r\bullet} \wedge a^{\bullet r} \wedge a^{+0}$.

## 4.3 Propriétés de base de $(\Delta\mathcal{L}\mathcal{G}, \models)$

**Proposition 1** Étant donné la conjonction de deux littéraux $\ell_1$ et $\ell_2$ portant sur la même variable, un troisième littéral $\ell_3$ peut parfois être déduit, qui est une conséquence logique des deux premiers. Dans ce cas, on aura $\ell_1 \wedge \ell_2 \equiv$

$\ell_1 \wedge \ell_2 \wedge \ell_3$. On a, en effet, pour $r, s \in \mathcal{G}$ :

$$ 
\begin{align*}
a^{r\bullet} \wedge a^{\bullet s} &\models a^{\bullet (s-r)} & a^{\bullet r} \wedge a^{\bullet s} &\models a^{\bullet (r+s)} \\
a^{\bullet r} \wedge a^{\bullet s} &\models a^{(s-r)\bullet} & a^{r\bullet} \wedge \neg a^{\bullet s} &\models \neg a^{\bullet (s-r)} \\
a^{\bullet r} \wedge \neg a^{\bullet s} &\models \neg a^{\bullet (r-s)} & a^{\bullet r} \wedge \neg a^{\bullet s} &\models \neg a^{\bullet (r+s)} \\
a^{\bullet r} \wedge \neg a^{\bullet s} &\models \neg a^{(s-r)\bullet} & a^{r\bullet} \wedge \neg a^{\bullet s} &\models \neg a^{\bullet (s-r)} \\
a^{r\bullet} \wedge \neg a^{\bullet s} &\models \neg a^{\bullet (r+s)} & &
\end{align*}
$$

Par ailleurs, pour $r, s \in \mathcal{G}$ avec $r \neq s$, les cubes suivants sont insatisfiables : $a^{r\bullet} \wedge a^{\bullet s}$, $a^{\bullet r} \wedge a^{\bullet s}$ et $a^{\bullet r} \wedge a^{\bullet s}$. Enfin, pour $r, s, t \in \mathcal{G}$, si $t \neq s-r$ alors $a^{r\bullet} \wedge a^{\bullet s} \wedge a^{\bullet t}$ est insatisfiable.

La définition et la proposition suivantes concernent les formes normales de $(\Delta\mathcal{L}\mathcal{G}, \models)$ et s'appuient sur le fait que $(\mathcal{G}, +)$ est un groupe abélien infini. La section 6.2 étend ces résultats sous d'autres hypothèses.

**Definition 1 (Formes normales FND et FNDCN)** Une formule de variations $\varphi$ est sous FND (forme normale disjonctive) si c'est une disjonction de cubes: $\varphi = \theta_1 \vee \theta_2 \vee \dots \vee \theta_p$ où $\theta_k$ est un cube de $(\Delta\mathcal{L}\mathcal{G}, \models)$. Soit $\theta$ un cube de $(\Delta\mathcal{L}\mathcal{G}, \models)$ avec comme seule variable $a$. $\theta$ est normal si une des conditions suivantes est respectée :

(i) $\theta = \perp$;

(ii) $\theta$ contient exactement 3 littéraux positifs, des formes $a^{r\bullet}$, $a^{\bullet s}$ et $a^{\bullet t}$ avec $r, s, t \in \mathcal{G}$ et $t = s-r$, et il ne contient aucun littéral négatif;

(iii) $\theta$ contient exactement un littéral positif $a^v$ et $p$ littéraux négatifs ($p \in \mathbb{N}$) $m_1, m_2, \dots, m_p$ utilisant un symbole de variation d'une forme différente de celle de $v$ (p. ex. si $v = \bullet r$ alors $m_k = \neg a^w$ où $w \neq \bullet s$ pour tout $s \in \mathcal{G}$); de plus, pour tout littéral négatif $\neg a^w$, $\theta$ contient aussi la conséquence $\neg a^x$ de $a^v \wedge \neg a^w$ selon la proposition 1 (p. ex. si $v = \bullet r$ et $w = s\bullet$, alors $x = \bullet (s+r)$);

(iv) $\theta$ ne contient que des littéraux négatifs, de tout type. Soit $\theta$ un cube de $(\Delta\mathcal{L}\mathcal{G}, \models)$. Pour $a$, une variable apparaissant dans $\theta$, soit $\theta_a$ la conjonction des littéraux de $\theta$ ayant $a$ comme variable. $\theta$ est un cube normal si tout $\theta_a$ est normal, pour tout $a$, variable de $\theta$. Une formule $\varphi \in \Delta\mathcal{L}\mathcal{G}$ est sous FNDCN (FND avec cubes normaux) si elle est sous FND et si tous les cubes qui la composent sont normaux.

**Proposition 2** Toute formule $\varphi \in \Delta\mathcal{L}\mathcal{G}$ peut être mise sous FND et sous FNDCN : il existe $\varphi_{\text{FND}} \in \Delta\mathcal{L}\mathcal{G}$ (resp. $\varphi_{\text{FNDCN}} \in \Delta\mathcal{L}\mathcal{G}$) qui est sous FND (resp. FNDCN) et telle que $\varphi \equiv \varphi_{\text{FND}}$ (resp. $\varphi \equiv \varphi_{\text{FNDCN}}$).

Le fait que $\varphi$ puisse être mise sous FND peut être prouvé comme cela se fait, p. ex., en logique propositionnelle. Le fait que tout cube peut être normalisé s'appuie en particulier sur la proposition 1.

Comme dans beaucoup de logique le problème de la conséquence logique et le problème de la satisfiabilité sont fortement liés dans $(\Delta\mathcal{L}\mathcal{G}, \models)$. For exemple, $\{\varphi_1, \varphi_2\} \models \psi$ ssi $\varphi_1 \wedge \varphi_2 \wedge \neg\psi$ n'est pas satisfiable. Or, le problème
de satisfiabilité peut être résolu en utilisant les principes de la méthode des tableaux sémantiques (voir, p. ex., [10]), qui, pour une logique s'appuyant sur les connecteurs propositionnels revient à construire une formule sous FND représentée par un arbre dont chaque branche représente un cube. La proposition suivante est alors utile pour concevoir un algorithme fondé sur la méthode des tableaux séman-tiques pour (ΔLG, |=) :

**Proposition 3** Les résultats ci-dessous peuvent être utilisés pour tester si une formule des variations est satisfiable :

(a) Pour $\varphi \in \Delta LG$, soit $\varphi_{\text{FND}}$ une formule sous FND telle que $\varphi_{\text{FND}} \equiv \varphi$. Alors, $\varphi$ est satisfiable ssi $\varphi_{\text{FND}}$ est satisfiable.

(b) Soit $\varphi \in \Delta LG$ une formule sous FND : $\varphi = \theta_1 \lor \theta_2 \dots \lor \theta_p$ où chaque $\theta_k$ est un cube de $(\Delta LG, |=$). Alors $\varphi$ est satisfiable ssi au moins un des $\theta_k$ est satisfiable ($k \in [1, p]$).

(c) Soit $\theta$ un cube de $(\Delta LG, |=$). Pour $a$, variable apparaissant dans $\theta$, soit $\theta_a$ la conjunction des littéraux de $\theta$ ayant $a$ comme variable. Alors, $\theta$ est satisfiable ssi chaque $\theta_a$ est satisfiable.

(d) Un cube normal $\theta_a$ avec une seule variable est satisfiable ssi $\theta_a \neq \bot$ (cela signifie que, si une des conditions (ii), (iii) et (iv) de la définition 1 est vérifiée, alors $\theta_a$ est satisfiable).

## 4.4 Opérateurs sur $(\Delta LG, |=$)

Cette section présente différents opérateurs sur la logique $(\Delta LG, |=$) qui seront utilisés dans les sections suivantes. Chacun d'entre eux a une définition sémantique et vérifie le principe d'indépendance à la syntaxe : si une formule apparaissant dans la définition d'un opérateur est représentée par une formule équivalente, alors le résultat de l'application de l'opérateur est inchangé à l'équivalence logique près. Chacun de ces opérateurs est défini soit à travers une définition classique, soit dans une proposition qui affirme son existence. Les preuves de ces propositions sont données dans [4]. Puis, la façon dont ces opérateurs sont calculés est décrite dans le cas où les formules impliquées sont des cubes.

Une formule de variations $\varphi$ peut être vue comme une représentation d'une relation binaire sur $\Omega$ puisque $M(\varphi) \subseteq \Omega \times \Omega$. La proposition suivante montre que l'inverse d'une relation $M(\varphi)$ peut être représentée par une formule de variations $\overleftarrow{\varphi}$.

**Proposition 4** Pour toute $\varphi \in \Delta LG$, il existe une formule de variations notée $\overleftarrow{\varphi}$ telle que

$$M(\overleftarrow{\varphi}) = \{\mathcal{J}\mathcal{I} \mid \mathcal{I}\mathcal{J} \in \mathcal{M}(\varphi)\}$$

En d'autres termes, $\mathcal{J}\mathcal{I} \models \overleftarrow{\varphi}$ ssi $\mathcal{I}\mathcal{J} \models \varphi$.

Le calcul de $\overleftarrow{\varphi}$ est linéaire : il consiste à remplacer chaque occurrence d'un symbole de variations $v$ par $\overleftarrow{v}$ défini comme suit :

$$\overleftarrow{\mathbf{r}} = -r \qquad \overleftarrow{\mathbf{r}} \cdot = \bullet r \qquad \overleftarrow{\bullet} \cdot r = r \cdot \quad (\text{pour } r \in \mathcal{G})$$

Par exemple, $\overleftarrow{a^{\bullet 1}} \wedge \overleftarrow{a^{\bullet 2}} \wedge \overleftarrow{c^{\bullet 2}} = a^{\bullet 1} \wedge a^{\bullet 2} \wedge c^{\bullet 2}$.

**Proposition 5** Pour tous $\alpha, \beta \in LG$ il existe une formule de $(\Delta LG, |=$) notée $\alpha \triangleright \beta$ et qui se lit “$\alpha$ devient $\beta$”, telle que $M(\alpha \triangleright \beta) = M(\alpha) \times M(\beta)$. En d'autres termes, $\mathcal{I}\mathcal{J} \models \alpha \triangleright \beta$ ssi $\mathcal{I} \models \alpha$ et $\mathcal{J} \models \beta$.

À présent, considérons $\bigwedge_{i=1}^p \ell_i$ et $\bigwedge_{j=1}^q m_j$, deux cubes de $(LG, |=$) : $\ell_1, \ell_2, \dots, \ell_p, m_1, m_2, \dots, m_q$ sont $p+q$ littéraux. L'application de $\triangleright$ sur ces cubes peut être calculée ainsi :

$$\left( \bigwedge_{i=1}^{p} \ell_i \right) \triangleright \left( \bigwedge_{j=1}^{q} m_j \right) \equiv \left( \bigwedge_{i=1}^{p} \ell_i \triangleright \top \right) \wedge \left( \bigwedge_{j=1}^{q} \top \triangleright m_j \right)$$

Enfin, il est suffisant de définir $\alpha \triangleright \beta$ quand l'un parmi $\alpha$ et $\beta$ est un littéral et l'autre est $\top$ (pour $a \in \mathcal{V}$ et $r \in \mathcal{G}$) :

$$\begin{align*} (a = r) \triangleright \top &\equiv a^{r\bullet} \\ \top \triangleright (a = r) &\equiv a^{\bullet r} \end{align*} \qquad \begin{align*} \neg(a = r) \triangleright \top &\equiv \neg a^{r\bullet} \\ \top \triangleright \neg(a = r) &\equiv \neg a^{\bullet r} \end{align*}$$

L'opérateur $\triangleright$ peut être utilisé pour l'apprentissage de connaissances d'adaptation utilisant l'heuristique des différences introduite en section 1. Considérons les cas sources suivants exprimés dans $(LG, |=$) avec $\mathcal{G} = \mathbb{Z}$ et où $\mathcal{V}_P = \{a, b\}$ et $\mathcal{V}_S = \{c, d\}$.

$$\mathbf{x}^1 \wedge \mathbf{y}^1 = (a = 1) \wedge (b = 2) \wedge (c = 3) \wedge (d = 4)$$

$$\mathbf{x}^2 \wedge \mathbf{y}^2 = (a = 2) \wedge (b = 0) \wedge (c = 2) \wedge (d = 6)$$

$$\mathbf{x}^3 \wedge \mathbf{y}^3 = (a = 3) \wedge (b = 1) \wedge (c = 1) \wedge (d = 8)$$

La variation du cas $(\mathbf{x}^k, \mathbf{y}^k)$ au case $(\mathbf{x}^l, \mathbf{y}^l)$ est représentée par $\Delta^{k\ell} = (\mathbf{x}^k \wedge \mathbf{y}^k) \triangleright (\mathbf{x}^l \wedge \mathbf{y}^l)$. Selon ce qui est présenté ci-dessus, comme les cas sources $\mathbf{x}^s \wedge \mathbf{y}^s$ sont des conjonctions de littéraux positifs de $(LG, |=$), le résultat $\Delta^{k\ell}$ est une conjonction d'atomes des formes $a^{r\bullet}$ et $a^{\bullet r}$ ($r \in \mathcal{G}$). En utilisant la première conséquence logique de la proposition 1, les atomes des formes $a^{\bullet r}$ sont ajoutés aux $\Delta^{k\ell}$, qui mettent en évidence les variations. Par exemple

$$\Delta^{12} \equiv a^{\bullet 1} \wedge a^{\bullet 1} \wedge a^{\bullet 2} \wedge b^{\bullet 2} \wedge b^{\bullet 2} \wedge b^{\bullet 0} \\ \wedge c^{\bullet 1} \wedge c^{\bullet 3} \wedge c^{\bullet 2} \wedge d^{\bullet 2} \wedge d^{\bullet 4} \wedge d^{\bullet 6}$$

Utiliser un algorithme d'extraction de motifs fréquents [7] sur l'ensemble d'apprentissage $\{\Delta^{k\ell}\}_{k\ell}$ permet de mettre en évidence des atomes $a^v$ apparaissant dans des sousensembles de cet ensemble d'apprentissage. Par exemple, pour $(k, \ell) \in \{(1, 2), (2, 3)\}$, le motif $\{a^{\bullet 1}, c^{\bullet 1}, d^{\bullet 2}\}$ peut être mis en évidence et permet de créer la formule $\varphi = a^{\bullet 1} \wedge c^{\bullet 1} \wedge d^{\bullet 2}$ qui peut être utilisée pour représenter une règle d'adaptation, comme on le verra plus loin. On peut noter que $\overleftarrow{\varphi}$ peut également être apprise : elle correspond à $(k, \ell) \in \{(2, 1), (3, 2)\}$.

**Proposition 6** Pour toute $\varphi \in \Delta LG$, il existe $\mathcal{G}(\varphi) \in LG$ et $\mathcal{D}(\varphi) \in LG$ (les projections gauche et droite de $\varphi$) telles que :

$$M(\mathcal{G}(\varphi)) = \{\mathcal{I} \in \Omega \mid \text{il existe } \mathcal{J} \in \Omega, \mathcal{I}\mathcal{J} \models \varphi\} \text{ et}$$

$$M(\mathcal{D}(\varphi)) = \{\mathcal{J} \in \Omega \mid \text{il existe } \mathcal{I} \in \Omega, \mathcal{I}\mathcal{J} \models \varphi\}$$
Si $\alpha$ et $\beta$ sont deux formules satisfiables de ($\mathcal{L}\mathcal{G}$, $|=$) alors
$\mathcal{G}(\alpha \triangleright \beta) \equiv \alpha$ et $\mathcal{D}(\alpha \triangleright \beta) \equiv \beta$.

Le calcul des projections gauche et droite d'un cube peut
être effectué en mettant un cube sous forme normale et en
utilisant les équivalences suivantes :

$$
\begin{align*}
\text{si } \varphi &= \bigwedge_{k=1}^{p} \ell_k \text{ est un cube normal de } (\Delta\mathcal{L}\mathcal{G}, |=), \\
\text{alors } \mathcal{G}(\varphi) &\equiv \bigwedge_{k=1}^{p} \mathcal{G}(\ell_k) \text{ et } \mathcal{D}(\varphi) \equiv \bigwedge_{k=1}^{p} \mathcal{D}(\ell_k) \\
\mathcal{G}(a^{+r}) &\equiv \mathcal{D}(a^{+r}) \equiv \mathcal{G}(a^{\bullet r}) \equiv \mathcal{D}(a^{\bullet r}) \equiv \top \\
\mathcal{G}(\neg a^{+r}) &\equiv \mathcal{D}(\neg a^{+r}) \equiv \mathcal{G}(\neg a^{\bullet r}) \equiv \mathcal{D}(\neg a^{\bullet r}) \equiv \top \\
\mathcal{G}(a^{r\bullet}) &\equiv (a=r) \quad \mathcal{G}(\neg a^{r\bullet}) \equiv \neg(a=r) \\
\mathcal{D}(a^{\bullet r}) &\equiv (a=r) \quad \mathcal{D}(\neg a^{\bullet r}) \equiv \neg(a=r)
\end{align*}
$$

**Definition 2** *Soit* $\varphi \in \Delta\mathcal{L}\mathcal{G}$ *et* $a \in \mathcal{V}$. *a est dite variable* invariante *de* $\varphi$ *s'il existe* $\psi \in \Delta\mathcal{L}\mathcal{G}$ *telle que* $\varphi \equiv \psi$ *et* $a \notin \mathcal{V}(\psi)$. *L'ensemble des variables invariantes de* $\varphi$ *est* noté $\text{Inv}(\varphi)$. *On a donc* $\mathcal{V} \setminus \mathcal{V}(\varphi) \subseteq \text{Inv}(\varphi) \subseteq \mathcal{V}$.

Une variable d'un cube normal est invariantessi $a \notin \mathcal{V}(\theta)$.
En revanche, il existe des formules de variation $\varphi$ telles que
$\text{Inv}(\varphi) \neq \mathcal{V} \setminus \mathcal{V}(\varphi)$. Par exemple, avec $\varphi = (a^{+1} \wedge a^{+2}) \vee b^{4*}$,
on $a \in \mathcal{V}(\varphi)$ mais $a \in \text{Inv}(\varphi)$ puisque $\varphi \equiv b^{4*}$.

5 Représenter des règles d'adaptation

Le formalisme (ΔLG, |=) a été conçu pour représenter des
variations entre cas sources a s'inspirant de notations is-
sues de l'apprentissage de connaissances d'adaptation. Le
résultat d'un tel processus d'apprentissage est un ensemble
de règles d'adaptation qui peuvent être représentées à l'aide
de cette logique et c'est ce qui est examiné dans cette sec-
tion.

5.1 Exemple motivant l'introduction de
l'opérateur ceteris paribus

Considérons à nouveau la règle d'adaptation dans le domaine culinaire qui a été présentée en introduction. Écrite de façon conjonctive, elle correspond au cube suivant de (ΔLG, |=), pour G = Q : $\varphi = \text{dessert}^{-1} \wedge \text{\#oeufs}^{-2} \wedge \text{\#bananes}^{+1}$. À présent, soit une recette de dessert avec 2 œufs, aucune banane, 50 grammes de farine et 20 grammes de beurre. Elle peut être représentée par la formule de (LG, |=) $\alpha = (\text{dessert} = 1) \wedge (\text{\#oeufs} = 2) \wedge (\text{\#bananes} = 0) \wedge (\text{farine}_{\text{gramme}} = 50) \wedge (\text{beurre}_{\text{gramme}} = 20)$ (en ne considérant pas d'autres variables). La question qui se pose est comment la formule $\varphi$ peut-elle être appliquée à $\alpha$ ?

Pour traiter cette question, l'idée est d'abord de définir la
formule des variations $\theta$ qui représente la transformation
de $\alpha$ par $\varphi$, sachant que le résultat final attendu sera alors
$\beta = \mathcal{D}(\theta)$. Soit $\mathcal{I}\mathcal{J}$ un modèle de $\theta$. Cette transformation "part" de $\alpha$ donc $\mathcal{I}$ devrait être un modèle de $\alpha$, ce qui équivaut à écrire que (a) $\mathcal{I}\mathcal{J} \models \alpha \triangleright \top$. De plus, $\theta$ doit

spécialiser $\varphi$, i.e. $\theta \models \varphi$, ce qui entraîne que (b) $\mathcal{I}\mathcal{J} \models \varphi$.
Si (a) et (b) étaient les seules conditions à donner sur $\mathcal{I}\mathcal{J}$,
cela impliquerait que $\theta \equiv (\alpha \triangleright \top) \wedge \varphi$ et donc, dans cet
exemple, le résultat de l'application sur $\alpha$ de $\varphi$ serait $\beta =
(\text{dessert} = 1) \wedge (\text{\#oeufs} = 0) \wedge (\text{\#bananes} = 1)$.
Pour les variables $\text{farine}_{\text{gramme}}$ et $\text{beurre}_{\text{gramme}}$, cela soulève le
problème suivant : elles n'apparaissent pas dans $\beta$. En ef-
fet, ces deux variables sont invariantes par $\varphi$. Pour traiter
cela, le postulat suivant est posé : si une variable est in-
variante dans $\varphi$ alors, l'application sur $\alpha$ de $\varphi$ doit laisser
cette variable inchangée. Cela suggère une troisième con-
dition : (c) si $a \in \text{Inv}(\varphi)$ alors $a$ est interprétée dans $\beta$
de la même façon qu'elle est interprétée dans $\alpha$ ; formelle-
ment, $\{\mathcal{I}(a) \mid \mathcal{I}\mathcal{J} \in \mathcal{M}(\theta)\} = \{\mathcal{J}(a) \mid \mathcal{I}\mathcal{J} \in \mathcal{M}(\theta)\}$.
Si $\alpha$, comme dans cet exemple, est un cube, la condition
(c) signifie simplement que si un littéral $\ell$ avec la variable
$a$ apparaît dans $\alpha$ alors $\beta$ contient le même littéral $\ell$. Une
autre manière de formuler cela consiste à ajouter à $\varphi$ une
conjonction avec l'atome $a^{+0}$ pour toute $a \in \text{Inv}(\varphi)$, ce
qui mène à une formule notée $\text{cp}(\varphi)$, définie formellement
ci-dessous, dans la définition 3.

Par conséquent, en prenant en compte la condition (c)
amène à la transformation $\theta$ et à l'application $\beta$ :

$$
\begin{align*}
\theta &= \text{dessert}^{1\bullet} \wedge \text{dessert}^{-1} \wedge \text{\#oeufs}^{2\bullet} \wedge \text{\#oeufs}^{-2} \\
&\quad \wedge \text{\#bananes}^{0\bullet} \wedge \text{\#bananes}^{+1} \wedge \text{farine}_{\text{gramme}}^{50\bullet} \\
&\quad \wedge \text{farine}_{\text{gramme}}^{+0} \wedge \text{beurre}_{\text{gramme}}^{20\bullet} \wedge \text{beurre}_{\text{gramme}}^{+0} \\
\beta &= (\text{dessert} = 1) \wedge (\text{\#oeufs} = 0) \wedge (\text{\#bananes} = 1) \\
&\quad \wedge (\text{farine}_{\text{gramme}} = 50) \wedge (\text{beurre}_{\text{gramme}} = 20)
\end{align*}
$$

À présent, la définition de $\mathrm{cp}(\varphi)$ peut être donnée :

**Definition 3** *Soit* $\varphi \in \Delta\mathcal{L}\mathcal{G}$ *et* $W \subseteq \mathcal{V}$ *avec* $W \neq \emptyset$. *Le ceteris paribus*<fnref n="1" /> *de* $\varphi$ *pour* $W$ *est défini par*

$$
\mathrm{cp}_W(\varphi) = \varphi \wedge \bigwedge \{a^{+0} \mid a \in \mathrm{Inv}(\varphi) \cap W\}
$$

$\mathrm{cp}(\varphi)$ est une abréviation de $\mathrm{cp}_V(\varphi)$ (toutes les variables sont considérées dans $\mathrm{cp}(\varphi)$).

5.2 Appliquer une formule de variation sur une formule statique

Dans ce qui précède, on a mis en évidence la transforma-
tion de $\alpha$ par $\varphi - \theta = (\alpha \triangleright \top) \wedge \text{cp}(\varphi)$ — et le résultat de
cette transformation — $\beta = \mathcal{D}(\theta)$. Une contrainte peut être
ajoutée au résultat de cette transformation. Si cette con-
trainte est représentée par $\gamma \in \mathcal{L}\mathcal{G}$, alors il est possible de
définir la transformation et l'application d'une formule de
variation sur une formule statique en tenant compte de $\gamma$ :

**Definition 4** *Soit* $\alpha, \gamma \in \mathcal{L}\mathcal{G}$ et $\varphi \in \Delta\mathcal{L}\mathcal{G}$. La transformation sur $\alpha$ de $\varphi$ avec contrainte $\gamma$ est la formule $\text{transf}(\alpha, \varphi, \gamma) \in \Delta\mathcal{L}\mathcal{G}$ définie par

$$
\operatorname{transf}(\alpha, \varphi, \gamma) = (\alpha \triangleright \gamma) \wedge \operatorname{cp}(\varphi)
$$

<footnote n="1">1. L'expression latine *ceteris paribus* signifie “toute chose étant égale par ailleurs”.</footnote>
L'application sur $\alpha$ de $\varphi$ avec contrainte $\gamma$ est la formule
appl($\alpha, \varphi, \gamma) \in \mathcal{LG}$ définie par

$$
\mathrm{appl}(\alpha, \varphi, \gamma) = \mathrm{D}(\mathrm{transf}(\alpha, \varphi, \gamma)) = \mathrm{D}((\alpha \triangleright \gamma) \wedge \mathrm{cp}(\varphi))
$$

La transformation (resp. application) de $\alpha$ sur $\varphi$
sans contrainte est simplement $\mathrm{transf}(\alpha, \varphi, \top)$ (resp.
$\mathrm{appl}(\alpha, \varphi, \top)$).

5.3 Représentation des règles d'adaptation

Soit adPb = ((x<sup>s</sup>, y<sup>s</sup>), x<sup>cible</sup>) ∈ BC × P un problème d'adaptation et ar, une règle d'adaptation. Trois questions peuvent être posées : (Q1) ar est-elle applicable pour ré-soudre adPb ? (Q2) Si la réponse à la question précédente est oui, quel est le résultat y<sup>cible</sup> ∈ S de l'application de ar sur adPb ? (Q3) À quel point l'assertion “y<sup>cible</sup> ré-sout x<sup>cible</sup>” est-elle plausible ? Pour répondre aux ques-tions (Q1) et (Q2), une formule de variation ϕ est utilisée, comme expliqué ci-dessous. La réponse proposée à la ques-tion (Q3) utilise un nombre strictement positif coût qui caractériser l'effort d'adaptation, i.e. le risque pris en ap-pliquant ar sur le problème d'adaptation (plus haut est ce coût, plus il y a de risque que l'adaptation donne un résultat incorrect).

Ci-dessous, une proposition de formalisation d'une règle d'adaptation est donnée, qui explique comment les questions (Q1) à (Q3) sont traitées :

**Definition 5** Une règle d'adaptation est un couple $\mathbf{ar} =$ ($\varphi$, coût) où $\varphi$ est une formule de variation et coût est un rationnel strictement positif appelé coût de $\mathbf{ar}$.

Soit adPb = ((x<sup>s</sup>, y<sup>s</sup>), x<sup>cible</sup>) un problème d'adaptation.
L'application de ar sur adPb est la formule statique suiv-
ante :

$$
\beta = \mathrm{appl}(x^s \wedge y^s, \varphi, x^{\mathrm{cible}})
$$

La règle ar est dite applicable sur adPb si $\beta$ est satisfiable.
Si ar est applicable sur adPb alors l'application de ar sur
adPb donne une solution satisfiable $y^{\text{cible}}$ telle que $\beta \equiv$
$x^{\text{cible}} \wedge y^{\text{cible}}$.

La valeur coût caractérise la fiabilité de l'assertion "y<sup>cible</sup> résout x<sup>cible</sup>" (plus petit ce coût est, plus fiable cette assertion est supposée être).

Pour reprendre l'exemple de la section 5.1, avec $x^s \wedge y^s = \alpha$ et $x^{\text{cible}} = (\text{dessert} = 1) \wedge (\#\text{œufs} = 0)$ (i.e. "Je veux un dessert sans œufs."), ar = ($\varphi$, coût) est applicable au problème d'adaptation adPb = ((x<sup>s</sup>, y<sup>s</sup>), x<sup>cible</sup>) et le résultat est $y^{\text{cible}} \equiv (\#\text{bananes} = 1) \wedge (\text{farine}_{\text{gramme}} = 50) \wedge (\text{beurre}_{\text{gramme}} = 20)$.

6 Situations dans lesquelles ($\mathcal{G}, +$) n'est pas un groupe abélien infini

Dans les sections précédentes, $(\mathcal{G}, +)$ est supposé être un groupe abélien infini. Cette section examine d'autres situations conduisant à des modifications dans la vérification de la satisfiabilité des formules de $(\Delta\mathcal{L}\mathcal{G}, \models)$. Deux situations sont envisagées : tout d'abord le cas où $(\mathcal{G}, +)$ est

un groupe abélien fini, ensuite le cas où $\mathcal{G}$ est un sous-
ensemble d'un groupe abélien $(\mathcal{H}, +)$, mais n'a pas une
structure de groupe, donc en particulier $\mathcal{G}$ n'est pas sta-
ble pour $+$ (autrement dit il existe $r, s \in \mathcal{G}$ tels que
$r + s \in \mathcal{H} \setminus \mathcal{G}$) ou pour l'opposé (i.e. il existe $r \in \mathcal{G}$
tel que $-r \in \mathcal{H} \setminus \mathcal{G}$). D'autres situations (comme par ex-
emple le cas où $(\mathcal{G}, +)$ est un groupe non abélien) ne sont
pas envisagées ici.

La notion principale considérée ici est celle de cube normal : l'idée derrière cette notion est qu’un cube normal est soit égal à $\perp$, soit satisfiable. Ainsi, le test de satisfiabilité sur les cubes normaux devrait consister en un simple test $\theta \neq \perp$ au niveau syntaxique. Pour les groupes infinis, cela est détaillé dans la section 4.3 : définition 1 et proposition 2.

6.1 ($\mathcal{G}$, $+$) est un groupe fini

Quand $(\mathcal{G}, +)$ est un groupe abélien infini, tout cube contenant uniquement des littéraux positifs est satisfiable. Ceci n’est plus le cas si $\mathcal{G}$ est fini. Par exemple, le cube $\neg a^{0\bullet} \wedge \neg a^{1\bullet}$ est satisfiable dans, par exemple, $\mathcal{G} = \mathbb{Z}$, mais pas dans $\mathcal{G} = \mathbb{Z}/2\mathbb{Z}$.

La solution consiste à faire disparaître les littéraux négatifs dans les cubes normaux, ce qui est possible puisque, si $\mathcal{G}$ est fini, tout littéral négatif est équivalent à une disjonction de littéraux positifs :

$$
\bigvee_{r \in A} \neg a^{r\bullet} \equiv \bigvee_{s \in \mathcal{G} \setminus A} a^{s\bullet} \qquad \neg a^{\bullet r} \equiv \bigvee_{s \in \mathcal{G} \setminus \{r\}} a^{+s} \qquad \neg a^{\bullet r} \equiv \bigvee_{s \in \mathcal{G} \setminus \{r\}} a^{\bullet s} \tag{1}
$$

Ainsi, après mise de $\varphi \in \Delta \mathcal{L} \mathcal{G}$ en forme normale négative (i.e. formule dans laquelle $\neg$ n'apparaît que devant des atomes) et application des équivalences (1) de gauche à droite, la formule obtenue ne contient plus de $\neg$. Appliquer alors la distributivité de $\wedge$ sur $\vee$ donne une FND de cubes contenant seulement des conjonctions de littéraux positifs. On peut alors prouver qu'un tel cube est incohérent si et seulement si il existe $a \in \mathcal{V}$ tel que $\theta$ contient trois atomes de la forme $a^{r\bullet}$, $a^{+s}$ et $a^{\bullet t}$ avec $r + s \neq t$. La définition suivante s'appuie sur ces considérations :

**Definition 6 (Cubes normaux lorsque G est fini)** *Si* $(\mathcal{G}, +)$ *est un groupe fini, alors un cube* $\theta$ *de* $(\Delta\mathcal{L}\mathcal{G}, \models)$ *est soit* $\perp$, *soit une conjonction d'atomes tel que, pour* chaque variable $a$ *apparaissant dans* $\theta$ :

- soit $a$ apparaît dans un unique atome de $\theta$;

- soit $a$ apparaît dans exactement trois atomes de $\theta$, de la forme $a^{r\bullet}$, $a^{+s}$ et $a^{\bullet t}$ avec $r + s = t$.

**Proposition 7** si $(\mathcal{G}, +)$ est un groupe abélien fini, un cube normal de $(\Delta\mathcal{L}\mathcal{G}, \models)$ est satisfiable si et seulement si il est différent de $\perp$.

6.2 $\mathcal{G}$ est un sous-ensemble infini d'un groupe ($\mathcal{H}, +$)

Dans cette situation, la première idée a été de considérer la
transformation d'un cube $\theta$ de $(\Delta\mathcal{L}\mathcal{G}, \models)$ en un cube nor-
mal $\theta'$ de $(\Delta\mathcal{L}\mathcal{H}, \models)$ et d'examiner les nouveaux atomes
produits, gardant ceux appartenant à ($\Delta LG, \models$) et enlevant
les autres.

Cette approche peut s'appliquer dans certaines situations,
mais pas dans toutes comme le contre-exemple qui suit le
montre. Par exemple, soit $G = 2\mathbb{Z} + 1$ (l'ensemble des en-
tiers impairs) : $G \subseteq \mathcal{H}$ avec $\mathcal{H} = \mathbb{Z}$. Suivre l'idée présen-
tée ci-dessus peut mener, par exemple, à considérer l'atome
$a^{+1}$ qui est, effectivement un atome de ($\Delta LG, \models$) mais qui
n'est pas satisfiable dans cette logique.

Comme ce point n'est pas prioritaire dans nos travaux, nous
laissons cela pour d'hypothétiques et lointains travaux fu-
turs.

6.3 $\mathcal{G}$ est un sous-ensemble fini d'un groupe

Soit $\mathcal{G}$ un ensemble fini tel que $\mathcal{G} \subseteq \mathcal{H}$ où $(\mathcal{H}, +)$ est un groupe abélien. Cette situation combine les difficultés des sections 6.1 et 6.2. Elle ne sera pas développée en détails ici.

7 Discussion et conclusion

Cet article a présenté une approche formelle pour représen-
ter des variations entre cas et des règles d'adaptation.

Ce travail théorique peut être prolongé dans différentes di-
rections.

Une première direction serait de confronter cette ap-
proche à des applications pratiques et/ou des benchmarks,
en utilisant un système d'apprentissage de connaissances
d'adaptations pour alimenter CA.

Ce travail a principalement considéré deux conteneurs de
connaissances d'un système de raisonnement à partir de
cas : BC et CA (les connaissances pour la remémoration sont
aussi considérées dans [4]). Peu d'attention a été apportée
aux connaissances du domaine, représentées par un ensem-
ble de formules statiques CD. Pour les connaissances sta-
tiques (en particulier les cas), cela consiste principalement
en la définition d'une inférence modulo CD ($\alpha \models_{CD} \beta$ si
CD $\cup$ $\{\alpha\} \models \beta$, $\alpha$ est CD-satisfiable si CD $\cup$ $\{\alpha\}$ est satisfi-
able, etc.). Comment les connaissances statiques représen-
tées par CD peuvent-elles utilisées pour définir une inférence
sur ($\Delta LG, \models$) et des règles d'adaptation est une question
qui reste à explorer.

Olaaf est un moteur d'adaptation fondé sur la révision des
croyances dans une logique dont les atomes sont des con-
traintes linéaires et qui est propositionnellement close [2].
La théorie sur laquelle il est bâti est essentiellement cen-
trée sur les connaissances du domaine CD et sur une mesure
de dissimilarité *diss* entre interprétations. Certaines rè-
gles d'adaptation sont "simulées" dans Olaaf en ajoutant
des connaissances à CD, et/ou en modifiant diss, bien que
cet aspect d'Olaaf n'ait pas encore été étudié en détail. À
l'inverse, l'approche proposée dans cet article est centrée
sur CA (et sa représentation). Une piste de travail digne
d'investigation consiste en la découverte d'une vision in-
tégrée de ces deux approches centrées sur la logique pour
l'adaptation.

Références

[1] M. d'Aquin, F. Badra, S. Lafrogne, J. Lieber, A. Napoli, and L. Szathmary. Case Base Mining for Adaptation Knowledge Acquisition. In M. M. Veloso, editor, *Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07)*, pages 750–755. Morgan Kaufmann, Inc., 2007.

[2] E. Diebold, Y. Kabrit, A. Kril, J. Lieber, P. Malvaud, E. Nauer, and J. Sipp. Olaaf: A General Adaptation Prototype. In J. A. Recio-Garcia, M. G. Orozco del Castillo, and D. Bridge, editors, *Case-Based Reasoning Research and Development*, volume 14775 of *Lecture Notes in Computer Science*, pages 223–239, Merida, Mexico, July 2024. J. A. Recio-Garcia and M. G. Orozco-del-Castillo and D. Bridge, Springer Nature Switzerland.

[3] N. François and J. Lieber. Appliquer la logique des variations propositionnelles à la représentation de règles d'adaptation pour le raisonnement à partir de cas. In Jean-Guy Mailly, François Schwarzentruber, and Anaëlle Wilczynski, editors, *Journées d'intelligence artificielle fondamentale – Plateforme Intelligence Artificielle*, page 12, La Rochelle, France, July 2024. Jean-Guy Mailly and François Schwarzentruber and Anaëlle Wilczynski.

[4] N. François and J. Lieber. A Knowledge Representation Approach for Reasoning with Adaptation Rules (extended version). Technical report, Loria, 2025. (This report can be found at https://hal.science/hal-04961604).

[5] K. Hanney and M. T. Keane. Learning adaptation rules from a case-base. In I. Smith and B. Faltings, editors, *Advances in Case-Based Reasoning – Proc. of the Third Eur. Workshop, EWCBR’96*, LNAI 1168, pages 179–192. Springer Verlag, Berlin, 1996.

[6] V. Jalali, D. Leake, and N. Forouzandehmehr. Learning and applying adaptation rules for categorical features: An ensemble approach. *AI Communications*, 30(3-4):193–205, 2017.

[7] J. M. Luna, Ph. Fournier-Viger, and S. Ventura. Frequent itemset mining: A 25 years review. *Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery*, 9(6):e1329, 2019.

[8] E. Nauer, J. Lieber, and M. d'Aquin. Lazy Adaptation Knowledge Learning Based on Frequent Closed Itemsets. In *Case-Based Reasoning Research and Development*, volume 14141 of *Lecture Notes in Computer Science*, pages 309–324, Aberdeen, United Kingdom, July 2023. Springer Nature Switzerland.

[9] C. K. Riesbeck and R. C. Schank. *Inside Case-Based Reasoning*. Lawrence Erlbaum Associates, Inc., Hillsdale, New Jersey, 1989. Available on line.

[10] R. M. Smullyan. *First-order logic*. Courier Corporation, 1995.