# Appliquer la logique des variations propositionnelles à la représentation de règles d'adaptation pour le raisonnement à partir de cas

Nicolas François, Jean Lieber

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

## To cite this version:

Nicolas François, Jean Lieber. Appliquer la logique des variations propositionnelles à la représentation de règles d'adaptation pour le raisonnement à partir de cas. Journées d'intelligence artificielle fondamentale – Plateforme Intelligence Artificielle, Jean-Guy Mailly; François Schwarzentruber; Anaëlle Wilczynski, Jul 2024, La Rochelle, France. pp.12. hal-04866379

HAL Id: hal-04866379

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

Submitted on 6 Jan 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Appliquer la logique des variations propositionnelles à la représentation de règles d'adaptation pour le raisonnement à partir de cas *

Nicolas François¹

Jean Lieber²

1 Lycée public Chopin, Nancy
2 Université de Lorraine, CNRS, Inria, LORIA, Nancy
nicolas.francois@free.fr jean.lieber@loria.fr

## Résumé

La logique des variations propositionnelles a été étudiée dans un article précédent. Ce formalisme est issu d'une notation issue du raisonnement à partir de cas (RàPC), avec l'ajout d'une sémantique. Cet article développe cette étude avec l'objectif de formaliser à l'aide de cette logique la notion de règles d'adaptation en RàPC et leur utilisation.

## Abstract

The logic of propositional variations was studied in a previous article. This formalism is based on a notation derived from case-based reasoning (CBR), with the addition of a semantics. This article develops this study with the aim of using this logic to formalize the notion of adaptation rules in CBR and their use.

## 1 Introduction

Le raisonnement à partir de cas (RàPC [12]) consiste à résoudre un problème en s'appuyant sur une base de cas, où un cas est la représentation d'un épisode de résolution de problème. Le modèle de processus du RàPC consiste généralement, étant donné un problème cible (problème à résoudre) en la sélection dans la base de cas d'un (parfois de plusieurs) cas jugé(s) similaire(s) au problème cible (étape de *remémoration*) et dans la modification de ce (ou ces) cas dans l'optique de la résolution du problème cible (étape d'*adaptation*).

L'adaptation peut s'appuyer sur des règles d'adaptation indiquant comment une variation entre problèmes peut se répercuter en variations entre solutions. Des notations ont été introduites pour coder ces variations, en vue de processus d'apprentissages de connaissances d'adaptation (voir, par exemple, [4]). Ces notations ont été dotées d'une sémantique pour obtenir une logique, qui a été étudiée, pour elle-même, dans [7].

L'objectif de cet article est d'étudier des liens entre cette logique et l'adaptation en RàPC, avec l'idée que les notations relatives aux variations (et aux différences, et aux (dis)similarités), fréquemment utilisées dans ce domaine, puissent être représentées explicitement, i.e. qu'on puisse les coder et raisonner avec. Plus particulièrement, elle permet d'étudier la représentation de règles d'adaptation.

La section 2 décrit la logique des variations propositionnelles (et résume ainsi [7]) et les notations et notions générales relatives au RàPC. Quelques études sur cette logique se sont avérées nécessaires pour l'étude de son application au RàPC : elles sont introduites dans la section 3. La section 4 étudie comment les logiques de variations peuvent être utilisées pour représenter des connaissances d'adaptation. La section 5 présente une discussion en lien avec d'autres travaux.

Les preuves complètes des résultats de cet article se trouvent dans le rapport [8], version étendue de cet article.

## 2 Préliminaires

Ces préliminaires sont en deux parties : l'une concerne la logique $(\Delta LP, \vdash)$, l'autre, le RàPC.

<footnote>*Les auteurs tiennent à remercier Tiago de Lima qui leur a conseillé des lectures sur les logiques dynamiques qui ont des liens avec la logique des variations propositionnelles, ainsi que cela est mis en évidence dans la section 5.2 de cet article. Ils veulent également exprimer leur gratitude envers Pierre Marquis pour ses conseils judicieux. Que leurs chemins soient pavés de fleurs de cerisiers. Les auteurs tiennent également à remercier les relecteurs de cet article pour leurs remarques.</footnote>
## 2.1 La logique des variations propositionnelles

Cette section reprend les points principaux sur la logique des variations propositionnelles ($\Delta LP, \models$) introduite et décrite dans [7].

**La logique propositionnelle finie** ($LP, \models$) est la logique de base sur laquelle va être définie ($\Delta LP, \models$).

On se donne un ensemble fini de symboles $V$: un élément de $V$ est appelé variable propositionnelle (ou simplement variable). Une formule de ($LP, \models$) est soit une variable propositionnelle, soit d'une des formes suivantes : $\neg\beta$, $\beta_1 \wedge \beta_2$ et $\beta_1 \vee \beta_2$, où $\beta$, $\beta_1$ et $\beta_2$ sont des formules propositionnelles. On utilisera les abréviations usuelles suivantes (où *euad* se lit « est une abréviation de », avec *a*, une variable choisie arbitrairement et $\beta_1, \beta_2 \in LP$) :

$$ \begin{array}{l} \top \ \underline{euad} \ a \lor \neg a \quad \bot \ \underline{euad} \ a \land \neg a \\ \beta_1 \to \beta_2 \ \underline{euad} \ \neg\beta_1 \lor \beta_2 \end{array} $$

Un littérale de ($LP, \models$) est une formule de la forme $a$ ou de la forme $\neg a$ ($a \in V$). Un cube de cette logique est une conjonction de littéraux dans laquelle une variable n'apparaît au plus qu'une fois. Un cube est complet si toutes les variables apparaissent dans ce cube.

L'ensemble des variables ayant des occurrences dans $\alpha \in LP$ est noté $V(\alpha)$.

On définit la sémantique en théorie des modèles comme suit. Une interprétation dans la logique propositionnelle est une fonction $I: V \to \{0, 1\}$ où $\{0, 1\}$ est l'ensemble des booléens. On note $\Omega$ l'ensemble des interprétations. Soit $I \in \Omega$ et $\alpha \in LP$. On définit la relation « $I$ satisfait $\alpha$ » ($I \models \alpha$, i.e. $I$ est un modèle de $\alpha$) de la façon suivante :

- $I \models a$ si $I(a) = 1$ pour une variable $a$;

- $I \models \neg\alpha$ si $I \models \neg\alpha$ pour $\alpha \in LP$;

- $I \models \alpha_1 \wedge \alpha_2$ si $I \models \alpha_1$ et $I \models \alpha_2$ pour $\alpha_1, \alpha_2 \in LP$;

- $I \models \alpha_1 \vee \alpha_2$ si $I \models \alpha_1$ ou $I \models \alpha_2$ pour $\alpha_1, \alpha_2 \in LP$.

L'ensemble des modèles de $\alpha$ est noté $M(\alpha)$. Si $B$ est un ensemble fini de formules, $M(B)$ est l'intersection des $M(\alpha)$ pour $\alpha \in B$, ce qui permet d'assimiler $B$ à la conjonction $\wedge B$ de ses éléments. On définit alors la relation $B \models \beta$ ($B$ entraîne $\beta$) par $M(B) \subseteq M(\beta)$ et la relation $\alpha \models_B \beta$ par $B \cup \{\alpha\} \models \beta$. Une formule $\alpha$ est satisfiable si $M(\alpha) \neq \emptyset$ (on le notera souvent $\alpha \not\models \bot$ dans l'article). Enfin, avec $\alpha, \beta \in LP, \alpha \equiv \beta$ si $M(\alpha) = M(\beta)$.

**La syntaxe de la logique** ($\Delta LP, \models$) diffère légèrement de celle qui était donnée dans [7], au sens où certains constructeurs dans cet article sont ici des abréviations et inversement. Une formule $\varphi \in \Delta LP$ est une expression d'une des formes suivantes : $\alpha \triangleright \beta$ (ce qu'on peut lire « $\alpha$ devient $\beta$ »), $\neg\psi, \psi_1 \wedge \psi_2$ et $\psi_1 \vee \psi_2$, où $\alpha, \beta \in LP$ et $\psi, \psi_1, \psi_2 \in \Delta LP$.

On utilisera les abréviations suivantes :

$$ \begin{array}{l@{\qquad}l} \top_{\Delta} \ \underline{euad} \ \top \triangleright \top & \bot_{\Delta} \ \underline{euad} \ \bot \triangleright \bot \\ \psi_1 \to \psi_2 \ \underline{euad} \ \neg\psi_1 \lor \psi_2 & \\ \alpha^{=1} \ \underline{euad} \ \alpha \triangleright \alpha & \alpha^{=0} \ \underline{euad} \ \neg\alpha \triangleright \neg\alpha \\ \alpha^{+} \ \underline{euad} \ \neg\alpha \triangleright \alpha & \alpha^{-} \ \underline{euad} \ \alpha \triangleright \neg\alpha \\ \alpha^{=} \ \underline{euad} \ \alpha^{=1} \lor \alpha^{=0} & \alpha^{\ne} \ \underline{euad} \ \alpha^{+} \lor \alpha^{-} \\ \alpha^{\circ\bullet} \ \underline{euad} \ \alpha^{=0} \lor \alpha^{+} & \alpha^{1\bullet} \ \underline{euad} \ \alpha^{=1} \lor \alpha^{-} \\ \alpha^{\circ0} \ \underline{euad} \ \alpha^{=0} \lor \alpha^{-} & \alpha^{\circ1} \ \underline{euad} \ \alpha^{=1} \lor \alpha^{+} \end{array} $$

Quand le contexte ne sera pas ambigu, $\top_{\Delta}$ et $\bot_{\Delta}$ seront notés simplement $\top$ et $\bot$. On note $D_0 = \{=1, =0, +, -\}$ et ses éléments sont appelés symboles de variations primitifs. L'ensemble $D_1 = \{=, \ne, 0\bullet, 1\bullet, \circ0, \circ1\}$ est celui des symboles de variation non primitifs. $D = D_0 \cup D_1$ est donc l'ensemble des symboles de variations.

Un littérale de ($\Delta LP, \models$) est une formule de la forme $a^v$ où $a \in V$ et $v \in D$. Un cube de cette logique est une conjonction de littéraux dans laquelle une variable n'apparaît au plus qu'une fois. Un cube est primitif si tous les symboles de variation qui y apparaissent sont primitifs. Un cube est complet s'il est primitif et si toutes les variables apparaissent dans ce cube.

Pour $\varphi \in \Delta LP$, $x \in V$ et $\alpha \in LP$, $\varphi[x\setminus\alpha]$ est le résultat de la substitution de $x$ par $\alpha$ dans $\varphi$. L'ensemble des variables ayant des occurrences dans $\varphi$ est noté $V(\varphi)$. La taille de $\varphi$, notée $|\varphi|$, est le nombre d'occurrences de connecteurs qu'elle contient.

**Sémantique de** ($\Delta LP, \models$). Soit $\Delta\Omega = \Omega \times \Omega$. Un élément $(I, J)$ de $\Delta\Omega$ est appelé interprétation (pour cette logique) et sera noté simplement $IJ$. Pour $\varphi \in \Delta LP$, la relation $IJ \models \varphi$ est définie comme suit :

- $IJ \models \alpha \triangleright \beta$ si $I \models \alpha$ et $J \models \beta$.

- $IJ \models \neg\psi$ si $IJ \models \neg\psi$.

- $IJ \models \psi_1 \wedge \psi_2$ si $IJ \models \psi_1$ et $IJ \models \psi_2$.

- $IJ \models \psi_1 \vee \psi_2$ si $IJ \models \psi_1$ ou $IJ \models \psi_2$.

On définit alors $M(\varphi) = \{IJ \in \Delta\Omega \mid IJ \models \varphi\}$. On note en particulier que $M(\alpha \triangleright \beta) = M(\alpha) \times M(\beta)$. On définit les notions de satisfiabilité, de conséquence logique ($\models$) et d'équivalence logique ($\equiv$) de la même façon qu'en logique propositionnelle.

Pour $\varphi \in \Delta LP$, on notera $G(\varphi)$ et $D(\varphi)$ des formules propositionnelles (uniques à l'équivalence logique près) telles que

$$ M(G(\varphi)) = \{I \mid IJ \in M(\varphi)\} $$

$$ M(D(\varphi)) = \{J \mid IJ \in M(\varphi)\} $$

En particulier, pour $\alpha, \beta \in LP, G(\alpha \triangleright \beta) \equiv \alpha$ et $D(\alpha \triangleright \beta) \equiv \beta$ (G comme « gauche », D comme « droite »).
**Quelques résultats.** Les points suivants résument et complètent certains résultats de [7] :

— Tout sous-ensemble $A$ de $\Delta\Omega$ est représentable dans la logique : il existe $\varphi \in \Delta\mathcal{L}\mathcal{P}$ telle que $M(\varphi) = A$.

— On a la plupart des résultats classiques de la logique propositionnelle : théorème de la déduction, lois de De Morgan, formes normales conjonctives et disjonctives, etc.

— Toute formule $\varphi$ peut se mettre sous la forme d'une formule obtenue à partir d'une formule de logique propositionnelle, en substituant à ses variables des formules de la forme $a^v$ où $a \in \mathcal{V}$ et $v \in \mathcal{D}_0$. Par exemple :

$$a \wedge b \triangleright \neg a \wedge c \equiv a^- \wedge (b^{=1} \vee b^-) \wedge (c^{=1} \vee c^+)$$

— En particulier, on peut écrire toute formule de $(\Delta\mathcal{L}\mathcal{P}, \vdash)$ sous forme normale disjonctive (FND), i.e. sous la forme de disjonction de cubes.

— On a la propriété de distributivité de $\triangleright$ sur $\wedge$ (modulo l'équivalence) :

$$(\alpha_1 \wedge \alpha_2) \triangleright \beta \equiv (\alpha_1 \triangleright \beta) \wedge (\alpha_2 \triangleright \beta)$$

$$\alpha \triangleright (\beta_1 \wedge \beta_2) \equiv (\alpha \triangleright \beta_1) \wedge (\alpha \triangleright \beta_2)$$

pour $\alpha, \alpha_1, \alpha_2, \beta, \beta_1, \beta_2 \in \mathcal{L}\mathcal{P}$. On a également la distributivité de $\triangleright$ sur $\vee$.

— Pour $a \in \mathcal{V}$, soit $\ell(a)$ et $m(a)$ deux littéraux construits sur $a$ ($\ell(a), m(a) \in \{a, \neg a\}$). On a :

$$\bigwedge_{a \in \mathcal{V}} \ell(a) \triangleright \bigwedge_{a \in \mathcal{V}} m(a) \equiv \bigwedge_{a \in \mathcal{V}} \ell(a) \triangleright m(a) \quad (1)$$

et chaque $\ell(a) \triangleright m(a)$ peut s'écrire $a^v$ où $v \in \mathcal{D}_0$.

— On peut définir un système formel correct et complet pour $(\Delta\mathcal{L}\mathcal{P}, \vdash)$.

— Le problème de décision $\mathcal{B} \models \varphi$ est NP-complet et plusieurs approches pour l'implanter ont été envisagées.

— On a le résultat suivant (avec $\varphi, \psi \in \Delta\mathcal{L}\mathcal{P}$) :

$$D(\varphi \vee \psi) \equiv D(\varphi) \vee D(\psi) \quad (2)$$

— Pour $\varphi \in \Delta\mathcal{L}\mathcal{P}$, on peut définir facilement $\varphi^{-1} \in \Delta\mathcal{L}\mathcal{P}$ telle que $IJ \models \varphi^{-1}$ ssi $JI \models \varphi$ (il suffit d'inverser les paramètres de $\triangleright$).

## 2.2 Rappels sur le raisonnement à partir de cas

**Généralités.** Le RàPC est un type de raisonnement s'appluyant sur une base de cas où un cas est une représentation d'un épisode de résolution de problème.

Un domaine d'application pour le RàPC est donné par un triplet $(\mathcal{P}, \mathcal{S}, \rightsquigarrow)$ où $\mathcal{P}$ et $\mathcal{S}$ sont des ensembles et $\rightsquigarrow$ est une relation binaire sur $\mathcal{P} \times \mathcal{S}$. Un élément de $\mathcal{X}$ est appelé problème, un élément de $\mathcal{Y}$, solution et $\mathcal{X} \rightsquigarrow \mathcal{Y}$ se lit « $\mathcal{X}$ a pour solution $\mathcal{Y}$ ».

En général, la relation $\rightsquigarrow$ n'est pas connue du système de RàPC dont l'objectif est de construire une hypothèse de solution $y^{cible}$ à un problème donné, le problème cible, noté $\mathbf{x}^{cible}$.

On considère souvent (et cela sera le cas dans cet article) qu'un cas est donné par un couple $(\mathbf{x}, \mathbf{y}) \in \mathcal{P} \times \mathcal{S}$ où $\mathbf{x} \rightsquigarrow \mathbf{y}$ : la relation $\rightsquigarrow$ est connue pour un ensemble fini qui constitue la base de cas. On note $(\mathbf{x}^s, \mathbf{y}^s)$ un élément de la base de cas et on l'appelle cas source ($\mathbf{x}^s$ est un problème source).

Le processus de RàPC le plus courant consiste en une étape de remémoration (sélection de $k$ éléments de la base de cas jugés similaires au problème cible) et d'adaptation (réutilisation des cas remémorés pour résoudre $\mathbf{x}^{cible}$). Dans cet article, ne seront considérés que des processus de remémoration et d'adaptation simples, i.e. $k = 1$. Pour l'adaptation, cela signifie qu'un problème d'adaptation sera donné par un cas source et un problème cible : on le notera $((\mathbf{x}^s, \mathbf{y}^s), \mathbf{x}^{cible})$.

L'approche de l'adaptation considérée dans cet article, parfois appelée adaptation transformationnelle (voir [2]) vise à résoudre le problème d'adaptation en le lisant sous la forme « La solution cherchée, $y^{cible}$, est à $\mathbf{y}^s$ ce que $\mathbf{x}^{cible}$ est à $\mathbf{x}^s$. » On peut l'interpréter ainsi : des variations entre les problèmes $\mathbf{x}^s$ et $\mathbf{x}^{cible}$, notées $\Delta\mathbf{x}$, on infère des variations entre la solution $\mathbf{y}^s$ et l'inconnue $y^{cible}$, notée $\Delta\mathbf{y}$, puis, on infère $y^{cible}$ à partir de $\mathbf{y}^s$ et $\Delta\mathbf{y}$.

**Modèle de connaissances du RàPC.** On considère généralement qu'une base de connaissances d'un système de RàPC est constitué de quatre « conteneurs de connaissances » : la base de cas BC, les connaissances du domaine CD, les connaissances de remémoration CR et les connaissances d'adaptation CA [11]. BC et CA ont été évoqués ci-dessus. CR est souvent représenté par une mesure de similarité ou une distance entre problèmes. CD peut être vu comme une conjonction de contraintes d'intégrité qui donnent des conditions nécessaires pour qu'un cas soit licite (exemple en cuisine : « Les salsifis, c'est pas bon<fnref n="1" />. »). Les inférences dans le formalisme représentant les cas se feront en général sur la base de ces connaissances du domaine (on utilisera la relation $\models_{CD}$ plutôt que simplement $\models$).

**Représentation des cas en logique propositionnelle.** Pour certaines applications, on peut représenter les cas dans $(\mathcal{L}\mathcal{P}, \vdash)$ : on considère un partitionnement de $\mathcal{V}$ en $\{\mathcal{V}_\mathcal{P}, \mathcal{V}_\mathcal{S}\}$ et un problème $\mathbf{x}$ (resp. une solution $\mathbf{y}$) sera représenté(e) par une formule dont les variables appartiennent à $\mathcal{V}_\mathcal{P}$ (resp. à $\mathcal{V}_\mathcal{S}$). Un cas source $(\mathbf{x}^s, \mathbf{y}^s)$ sera représenté par la conjonction $\mathbf{x}^s \wedge \mathbf{y}^s$ (²).

<footnote n="1">1. Cette connaissance du domaine, quelque peu subjective, nous a été fournie par une des sœurs d'un des auteurs.</footnote>

<footnote n="2">2. Parfois, comme on le verra pour l'exemple suivi, le partitionnement entre variables problèmes et variables solutions se fait une fois le problème d'adaptation spécifié : connaissant $\mathbf{x}^{cible}$ et le cas source $\mathbf{c}^s$, on détermine</footnote>
Dans beaucoup d'applications, les cas sources et le problème cible sont considérés comme spécifiques, i.e. issus d'une expérience particulière complètement instanciée. Dans ce cas, pour un cas source $(\mathbf{x}^s, \mathbf{y}^s)$ et un problème cible $\mathbf{x}^{\text{cible}}$, les problèmes $\mathbf{x}^s$ et $\mathbf{x}^{\text{cible}}$ peuvent s'écrire sous la forme $\bigwedge_{a \in \mathcal{V}_p} \ell(a)$ et la solution $\mathbf{y}^s$ sous la forme $\bigwedge_{a \in \mathcal{V}_s} \ell(a)$, où $\ell(a) \in \{a, \neg a\}$. La formule $\mathbf{x}^s \wedge \mathbf{y}^s$ est alors un cube complet et donc $|\mathcal{M}(\mathbf{x}^s \wedge \mathbf{y}^s)| = 1$.

**L'apprentissage de connaissances d'adaptation.**
L'adaptation peut s'appuyer sur des connaissances d'adaptation. Ces connaissances peuvent être acquises auprès d'un expert (voir p. ex. [5]). Elles peuvent être aussi apprises à partir de la base de cas, selon le principe appelé *difference heuristics* dans [10] et défini initialement dans [9]. Ce principe s'inscrit dans le cadre de l'adaptation transformationnelle : étant donné deux cas sources différents $(\mathbf{x}^i, \mathbf{y}^i)$ et $(\mathbf{x}^j, \mathbf{y}^j)$, on construit les variations $\Delta\mathbf{x}^{ij}$ de $\mathbf{x}^i$ à $\mathbf{x}^j$ et $\Delta\mathbf{y}^{ij}$ de $\mathbf{y}^i$ à $\mathbf{y}^j$. L'apprentissage de connaissances d'adaptation utilise un ensemble de couples $(\Delta\mathbf{x}^{ij}, \Delta\mathbf{y}^{ij})$ et permet de construire un modèle d'une fonction $\Delta\mathbf{x} \mapsto \Delta\mathbf{y}$, qui permet, à partir d'une variation entre problèmes d'obtenir une variation entre solution, ce qui est utile pour un processus d'adaptation transformationnelle.

Des travaux dans ce cadre se sont appuyés sur une notation $a^v$, où $a$ est un attribut d'un problème ou d'une solution et $v$ représente une relation entre valeurs du domaine de cet attribut. Cette notation permet de coder ces variations, dans une optique d'apprentissage de règles d'adaptation, utilisant des techniques telles que l'extraction de motifs fermés fréquents [4]. Par exemple, âge<sup>ajouter(5)</sup> indique une variation de 5 pour l'attribut âge. Le résultat d'une extraction de motifs fermés fréquents avec des $\Delta\mathbf{x}^{ij}$ et des $\Delta\mathbf{y}^{ij}$ est un ensemble de motifs, chaque motif étant un ensemble d'expressions $a^v$. En se limitant à des attributs booléens, les $a^v$ correspondaient dans ce travail à ceux de la section 2.1 : c'est ce travail qui a d'ailleurs motivé au départ l'étude de la logique ($\Delta\mathcal{L}\mathcal{P}, \models$).

Plus précisément, si les cas sources sont supposés spécifiques, d'après le résultat (1), on peut écrire $\Delta\mathbf{x}^{ij}$ et $\Delta\mathbf{y}^{ij}$ sous les formes $\bigwedge_{a \in \mathcal{V}_p} a^v(a)$ et $\bigwedge_{a \in \mathcal{V}_s} a^v(a)$, où $v(a) \in \mathcal{D}_0$. Un algorithme de recherche de motifs fréquents permettra alors de calculer des motifs $M$, ensemble d'éléments de la forme $a^v$, motifs qui peuvent être interprétés en règles d'adaptation.

# 3 Nouveaux résultats sur ($\Delta\mathcal{L}\mathcal{P}, \models$)

Cette section introduit et étudie des notions relatives à la logique ($\Delta\mathcal{L}\mathcal{P}, \models$) utiles pour la suite de l'article et qui étaient peu ou pas introduits dans [7].

## 3.1 Résultats généraux

Le premier résultat énonce le fait que seules les variables apparaissant dans une formule de ($\Delta\mathcal{L}\mathcal{P}, \models$) ont une influence dans les inférences déductives (ce qui peut sembler une évidence mais mérite peut-être d'être énoncé) :

si $\mathcal{I}_1\mathcal{J}_1, \mathcal{I}_2\mathcal{J}_2 \in \Delta\Omega$ vérifient

$$ \mathcal{I}_1(x) = \mathcal{I}_2(x) \text{ et } \mathcal{J}_1(x) = \mathcal{J}_2(x) \quad \text{pour } x \in \mathcal{V}(\varphi) $$

$$ \text{alors } \mathcal{I}_1\mathcal{J}_1 \models \varphi \text{ ssi } \mathcal{I}_2\mathcal{J}_2 \models \varphi \quad (3) $$

pour $\varphi \in \Delta\mathcal{L}\mathcal{P}$. La preuve de ce résultat se fait par induction structurelle.

Le résultat (2) ne se généralise pas en remplaçant $\lor$ par $\land$. Cependant, on a le résultat suivant :

si $\varphi, \psi \in \Delta\mathcal{L}\mathcal{P}$ vérifient $\mathcal{V}(\varphi) \cap \mathcal{V}(\psi) = \emptyset$

$$ \text{alors } \mathcal{G}(\varphi \wedge \psi) \equiv \mathcal{G}(\varphi) \wedge \mathcal{G}(\psi) $$

$$ \text{et } \mathcal{D}(\varphi \wedge \psi) \equiv \mathcal{D}(\varphi) \wedge \mathcal{D}(\psi) \quad (4) $$

**Preuve.** La preuve ne sera faite que pour l'opérateur $\mathcal{D}$ (elle se transpose immédiatement pour l'opérateur $\mathcal{G}$). Soit $\mathcal{J} \in \mathcal{M}(\mathcal{D}(\varphi \wedge \psi))$. Il existe donc $\mathcal{I} \in \Omega$ telle que $\mathcal{I}\mathcal{J} \models \varphi \wedge \psi$. Donc, il existe $\mathcal{I} \in \Omega$ telle que $\mathcal{I}\mathcal{J} \models \varphi$. Donc $\mathcal{J} \models \mathcal{D}(\varphi)$. Le même raisonnement conduit à $\mathcal{J} \models \mathcal{D}(\psi)$. Donc $\mathcal{J} \models \mathcal{D}(\varphi) \wedge \mathcal{D}(\psi)$. Par conséquent, $\mathcal{D}(\varphi \wedge \psi) \models \mathcal{D}(\varphi) \wedge \mathcal{D}(\psi)$.

Pour ce sens direct, l'hypothèse $\mathcal{V}(\varphi) \cap \mathcal{V}(\psi) = \emptyset$ n'était pas utile. Elle l'est pour la réciproque.

Supposons que $\mathcal{J} \models \mathcal{D}(\varphi) \wedge \mathcal{D}(\psi)$. Par conséquent, il existe $\mathcal{I}_1 \in \Omega$ telle que $\mathcal{I}_1\mathcal{J} \models \varphi$. De même, il existe $\mathcal{I}_2 \in \Omega$ telle que $\mathcal{I}_2\mathcal{J} \models \psi$. Comme $\mathcal{V}(\varphi) \cap \mathcal{V}(\psi) = \emptyset$ on peut définir $\mathcal{I} \in \Omega$ par

$$ \mathcal{I}(x) = \begin{cases} \mathcal{I}_1(x) & \text{si } x \in \mathcal{V}(\varphi) \\ \mathcal{I}_2(x) & \text{si } x \in \mathcal{V}(\psi) \\ 1 & \text{sinon} \end{cases} \quad (\text{pour tout } x \in \mathcal{V}) $$

D'après le résultat (3), $\mathcal{I}_1\mathcal{J} \models \varphi$ entraîne $\mathcal{I}\mathcal{J} \models \varphi$ (puisque pour $x \in \mathcal{V}(\varphi)$, $\mathcal{I}_1(x) = \mathcal{I}(x)$ et, évidemment, $\mathcal{J}(x) = \mathcal{J}(x)$). De la même façon, on prouve que $\mathcal{I}\mathcal{J} \models \psi$. Donc, $\mathcal{I}\mathcal{J} \models \varphi \wedge \psi$ et, par conséquent, $\mathcal{J} \models \mathcal{D}(\varphi \wedge \psi)$. On en déduit que $\mathcal{D}(\varphi) \wedge \mathcal{D}(\psi) \models \mathcal{D}(\varphi \wedge \psi)$ ce qui conclut la preuve. ■

## 3.2 Caractérisation alternative de $\mathcal{B} \models \varphi$

La relation $\models$ entre une base de connaissances $\mathcal{B}$ et une formule $\varphi$ de la logique des variations propositionnelles peut être redéfinie en s'appuyant sur quatre « valeurs de vérité » sur les variations, données par les éléments de $\mathcal{D}_0 = \{=1, =0, +, -\}$.

Soit $\Delta\Omega_{\text{alt}}$ l'ensemble des fonctions $\omega : \mathcal{V} \to \mathcal{D}_0$. On définit la relation $\models_{\text{alt}}$ entre $\omega \in \Delta\Omega_{\text{alt}}$ et $\varphi \in \Delta\mathcal{L}\mathcal{P}$ par :

$$ \omega \models_{\text{alt}} \varphi \text{ si } \bigwedge_{a \in \mathcal{V}} a^{\omega(a)} \models \varphi $$

<footnote>$\mathcal{V}_p$ et $\mathcal{V}_s$ pour décomposer $c^s$ en $\mathbf{x}^s \wedge \mathbf{y}^s$.</footnote>
On note alors $\mathcal{M}_{\text{alt}}(\varphi) = \{\omega \in \Delta\Omega_{\text{alt}} | \omega \models_{\text{alt}} \varphi\}$. Par exemple, si $\mathcal{V} = \{a, b\}$, $\mathcal{M}_{\text{alt}}(a^= \wedge b^+) = \{\omega_1, \omega_2\}$ où $\omega_1(a) = \texttt{=1}$, $\omega_2(a) = \texttt{=0}$ et $\omega_1(b) = \omega_2(b) = \texttt{+}$. Pour une base de connaissances $\mathcal{B}$, on notera $\mathcal{M}_{\text{alt}}(\mathcal{B}) = \bigcap_{\varphi \in \mathcal{B}} \mathcal{M}_{\text{alt}}(\varphi)$. On définit alors la relation $\models_{\text{alt}}$ entre une base de connaissances $\mathcal{B}$ et une formule $\varphi$ par $\mathcal{B} \models_{\text{alt}} \varphi$ si $\mathcal{M}_{\text{alt}}(\mathcal{B}) \subseteq \mathcal{M}_{\text{alt}}(\varphi)$.

Cette relation $\models_{\text{alt}}$ ne définit pas une nouvelle sémantique de la logique des variations comme le montre la proposition ci-dessous ; elle permet juste une caractérisation alternative de cette sémantique.

**Proposition 1.** Pour toute base de connaissances $\mathcal{B}$ de $(\Delta\mathcal{L}\mathcal{P}, \models)$ et toute $\varphi \in \Delta\mathcal{L}\mathcal{P}$, $\mathcal{B} \models_{\text{alt}} \varphi$ ssi $\mathcal{B} \models \varphi$.

**Preuve.** À $\mathcal{I}\mathcal{J} \in \Delta\Omega$, on associe $\omega_{\mathcal{I}\mathcal{J}} \in \Delta\Omega_{\text{alt}}$ de la façon suivante, pour $a \in \mathcal{V}$

$$ \omega_{\mathcal{I}\mathcal{J}}(a) = \begin{cases} \texttt{=1} & \text{si } \mathcal{I}(a) = \mathcal{J}(a) = 1 \\ \texttt{=0} & \text{si } \mathcal{I}(a) = \mathcal{J}(a) = \texttt{0} \\ \texttt{+} & \text{si } \mathcal{I}(a) = \texttt{0} \text{ et } \mathcal{J}(a) = 1 \\ - & \text{si } \mathcal{I}(a) = 1 \text{ et } \mathcal{J}(a) = \texttt{0} \end{cases} $$

La fonction $\mathcal{I}\mathcal{J} \in \Delta\Omega \mapsto \omega_{\mathcal{I}\mathcal{J}} \in \Delta\Omega_{\text{alt}}$ est une bijection dont la fonction inverse est définie ainsi : à $\omega \in \Delta\Omega_{\text{alt}}$ elle associe $\mathcal{I}\mathcal{J} \in \Delta\Omega$ définie ainsi, pour $a \in \mathcal{V}$ :

$$ \begin{aligned} \mathcal{I}(a) &= \begin{cases} \texttt{0} & \text{si } \omega(a) \in \{=\texttt{0}, +\} \\ 1 & \text{sinon} \end{cases} \\ \mathcal{J}(a) &= \begin{cases} \texttt{0} & \text{si } \omega(a) \in \{=\texttt{0}, -\} \\ 1 & \text{sinon} \end{cases} \end{aligned} $$

(on montre que c'est une bijection en utilisant le fait que $|\Delta\Omega_{\text{alt}}| = |\Delta\Omega| = 4^{|\mathcal{V}|}$ et en vérifiant que, pour $\omega \in \Delta\Omega_{\text{alt}}$, en y associant $\mathcal{I}\mathcal{J}$ comme ci-dessus, on a $\omega_{\mathcal{I}\mathcal{J}} = \omega$).

On montre ensuite que pour $\mathcal{I}\mathcal{J} \in \Delta\Omega$ et $\varphi \in \Delta\mathcal{L}\mathcal{P}$ on a $\mathcal{I}\mathcal{J} \models \varphi$ ssi $\omega_{\mathcal{I}\mathcal{J}} \models_{\text{alt}} \varphi$.

Enfin, pour une base de connaissances $\mathcal{B}$ et $\varphi \in \Delta\mathcal{L}\mathcal{P}$, on montre que $\mathcal{B} \models \varphi$ ssi $\mathcal{B} \models_{\text{alt}} \varphi$ en s'appuyant sur la bijection introduite ci-dessus et l'équivalence entre satisfaction dans $\Delta\Omega$ et dans $\Delta\Omega_{\text{alt}}$.

### 3.3 Variables invariantes d'une formule de variations

Soit $\varphi \in \Delta\mathcal{L}\mathcal{P}$, on s'intéresse (et ce sera justifié par la suite) aux variables $a$ dont le changement laisse $\varphi$ inchangée. On va définir $\text{Inv}(\varphi)$ en s'appuyant sur la définition alternative de la sémantique présentée à la section précédente. L'idée est que $a \in \text{Inv}(\varphi)$ signifie que la valeur d'$(\omega(a) \text{ n'influe pas sur la satisfaction de } \varphi \text{ par } \omega)$. Formellement, cela mène à la définition suivante :

**Définition 1.** Pour $\omega \in \Delta\Omega_{\text{alt}}$, $a \in \mathcal{V}$ et $v \in \mathcal{D}_0$, on définit $\omega[a^v] \in \Delta\Omega_{\text{alt}}$ par

$$ \omega[a^v] : x \in \mathcal{V} \mapsto \begin{cases} v & \text{si } x = a \\ \omega(x) & \text{sinon} \end{cases} $$

Pour $\varphi \in \Delta\mathcal{L}\mathcal{P}$, l'ensemble des variables invariantes de $\varphi$ est

$$ \text{Inv}(\varphi) = \left\{ a \in \mathcal{V} \mid \begin{array}{l} \text{pour toute } \omega \in \mathcal{M}_{\text{alt}}(\varphi) \\ \text{et tout } v \in \mathcal{D}_0, \omega[a^v] \models_{\text{alt}} \varphi \end{array} \right\} $$

Par exemple,

$$ \begin{array}{l} \text{si } \mathcal{V} = \{a, b, c\} \text{ et } \varphi = (a^+ \wedge b^=) \vee (a^+ \wedge b^+) \vee (a^+ \wedge b^-) \\ \text{alors } \text{Inv}(\varphi) = \{b, c\} \end{array} \qquad (5) $$

Cette notion est indépendante de la syntaxe : si $\varphi \equiv \psi$ alors $\text{Inv}(\varphi) = \text{Inv}(\psi)$. On montre, en s'appuyant sur (3) que si une variable $x$ n'apparaît pas dans $\varphi$ alors elle est invariante. Donc :

$$ \mathcal{V} \setminus \mathcal{V}(\varphi) \subseteq \text{Inv}(\varphi) \subseteq \mathcal{V} \qquad (6) $$

Comme le montre l'exemple (5), une variable apparaisant dans $\varphi$ peut très bien être invariante pour $\varphi$.

Le cas particulier de la proposition suivante est utile dans la suite de l'article.

**Proposition 2.** Si $\varphi$ est un cube de $(\Delta\mathcal{L}\mathcal{P}, \models)$ alors $\text{Inv}(\varphi) = \mathcal{V} \setminus \mathcal{V}(\varphi)$.

**Preuve.** Comme $\text{Inv}(\varphi) \supseteq \mathcal{V} \setminus \mathcal{V}(\varphi)$ (cf. (6)), il suffit de montrer que si $a \in \text{Inv}(\varphi)$ alors $a \notin \mathcal{V}(\varphi)$, ce qu'on va montrer par contraposée. Soit $a \in \mathcal{V}(\varphi)$. Soit $v \in \mathcal{D}$ tel que $a^v$ est l'atome de $\varphi$ ayant $a$ comme variable. Soit $v_0 \in \mathcal{D}_0$ tel que $a^{v_0} \models a^v$ (si $v$ est un symbole de variation primitif, $v_0 = v$, sinon, il y a plusieurs choix possibles pour $v_0$, p. ex., si $v = \texttt{\ne}$ alors on peut choisir $v_0 = \texttt{+}$ ou $v_0 = \texttt{-}$). Soit $w \in \mathcal{D}_0 \setminus \{v_0\}$. On a donc $\varphi[a^{v_0}] \models a^{v_0}$ et $\varphi[a^w] \not\models a^{v_0}$ (puisque, par hypothèse sur les cubes, une variable n'apparaît qu'une seule fois dans un cube et donc, les cubes sont satisfiables). Par conséquent, $\varphi[a^{v_0}] \not\models \varphi[a^w]$ et donc $a \notin \text{Inv}(\varphi)$. ■

### 3.4 Opérateur ceteris paribus

Considérons la formule $a^+$ : elle indique que $a$ « passe » de $\texttt{0}$ à $\texttt{1}$, les autres variables étant libres de suivre toutes les variations. Ainsi, si $\mathcal{V} = \{a, b\}$, $M(a^+) = \{(\overline{ab}, \overline{ab}), (\overline{ab}, ab), (\overline{ab}, \overline{ab}), (\overline{ab}, ab)\}$. Il apparaît utile dans certains cas d'exprimer par exemple que $a$ « passe » de $\texttt{0}$ à $\texttt{1}$, le reste des variables restant inchangées. On va exprimer cela par une formule $\text{cp}(a^+)$ qui, sur l'exemple avec deux variables, donnera $M(\text{cp}(a^+)) = \{(\overline{ab}, \overline{ab}), (\overline{ab}, ab)\}$ : dans les modèles de ces formules, $b$ reste à $\texttt{0}$ ou reste à $\texttt{1}$ (cp pour ceteris paribus), en d'autres termes, $\text{cp}(a^+) \models b^=$. Dans cet exemple, $b$ est une variable dont l'interprétation ne change pas l'interprétation de $\varphi$ : $b \in \text{Inv}(\varphi)$.
Plus généralement, on cherche un opérateur cp tel que,
pour $\varphi, \psi \in \Delta\mathcal{L}\mathcal{P}$, on ait

$$ \mathrm{cp}(\varphi) \models \varphi \qquad (7) $$

$$ \text{pour toute } x \in \mathrm{Inv}(\varphi), \mathrm{cp}(\varphi) \models x^{\mathcal{V}} \qquad (8) $$

$$ \text{si } \varphi \equiv \psi \text{ alors } \mathrm{cp}(\varphi) \equiv \mathrm{cp}(\psi) \qquad (9) $$

$$ \text{si } \varphi \text{ est satisfiable alors } \mathrm{cp}(\varphi) \text{ l'est aussi} \qquad (10) $$

On propose la définition suivante de cp et on prouve ensuite qu'elle vérifie ces propriétés.

**Définition 2.** cp est la fonction de $\Delta\mathcal{L}\mathcal{P}$ dans lui-même définie, pour $\varphi \in \Delta\mathcal{L}\mathcal{P}$ par

$$ \mathrm{cp}(\varphi) = \varphi \wedge \bigwedge \{x^{\mathcal{V}} \mid x \in \mathrm{Inv}(\varphi)\} $$

**Proposition 3.** cp vérifie (7), (8), (9) et (10).

**Preuve.** (7), (8) et (9) découlent immédiatement de la définition.

Pour (10), on le prouve de la façon suivante. Supposons que $\varphi$ soit satisfiable. Elle l'est donc aussi au sens de la définition alternative de la sémantique et donc, il existe $\omega \in \Delta\Omega_{\mathrm{alt}}$ telle que $\omega \models_{\mathrm{alt}} \varphi$. Soit $a_1, a_2, \dots, a_p$ telles que $\mathrm{Inv}(\varphi) = \{a_1, a_2, \dots, a_p\}$. Soit $\omega' = \omega[a_1^{\mathcal{V}1}] [a_2^{\mathcal{V}1}] \dots [a_p^{\mathcal{V}1}]$. On a, par définition de $\mathrm{Inv}(\varphi)$, $\omega' \models_{\mathrm{alt}} \varphi$. Par ailleurs, $\omega' \models_{\mathrm{alt}} a_k^{\mathcal{V}1}$ pour tout $k \in \{1, 2, \dots, p\}$ et donc $\omega' \models_{\mathrm{alt}} \wedge\{x^{\mathcal{V}1} \mid x \in \mathrm{Inv}(\varphi)\}$. Or, pour toute variable $a$, $a^{\mathcal{V}1} \models a^{\mathcal{V}}$. Par conséquent, $\omega' \models_{\mathrm{alt}} \wedge\{x^{\mathcal{V}} \mid x \in \mathrm{Inv}(\varphi)\}$. Donc, $\omega' \models_{\mathrm{alt}} \mathrm{cp}(\varphi)$ et donc, cp ($\varphi$) est satisfiable.

■

Une conséquence immédiate de la proposition 2 est la suivante :

$$ \text{si } \varphi \text{ est un cube alors } \mathrm{cp}(\varphi) = \varphi \wedge \bigwedge_{x \in V \setminus V(\varphi)} x^{\mathcal{V}} \qquad (11) $$

Par ailleurs, les modèles de cp ($\top$) sont les $\mathcal{I}\mathcal{I}$ pour $\mathcal{I} \in \Omega$.

Notons que cp est non monotone, dans le sens où on peut avoir $\varphi \models \psi$ et cp ($\varphi$) $\not\models$ cp ($\psi$). Par exemple, $a^+ \models \top$ et cp ($a^+$) $\not\models$ cp ($\top$).

Un problème pratique se pose avec cet opérateur : pour $\varphi \in \Delta\mathcal{L}\mathcal{P}$, $|\mathrm{cp}(\varphi)|$ est en $O(|\varphi| + n)$ et la manipulation de formules longues prend du temps de calcul. Ce problème devient théorique si on étend le cadre logique à un ensemble de variables infini : la définition de cp ci-dessus ne s'applique pas, les formules étant nécessairement de tailles finies. Une perspective pour pallier ce problème serait l'étude d'une possible extension de la logique par un connecteur cp (plutôt que par un opérateur).

Il apparaît parfois utile de restreindre le ceteris paribus à un ensemble prédéfini de variables, d'où la définition suivante.

**Définition 3.** Soit $\mathcal{W} \subseteq \mathcal{V}$ et $\varphi \in \Delta\mathcal{L}\mathcal{P}$. Le ceteris paribus de $\varphi$ restreint à l'ensemble de variables $\mathcal{W}$ est :

$$ \mathrm{cp}_{\mathcal{W}}(\varphi) = \varphi \wedge \bigwedge \{x^{\mathcal{V}} \mid x \in \mathrm{Inv}(\varphi) \cap \mathcal{W}\} $$

Et on a, évidemment, $\mathrm{cp}_{\mathcal{V}}(\varphi) = \mathrm{cp}(\varphi)$.

## 3.5 Composition des variations

La composition sur $(\Delta\mathcal{L}\mathcal{P}, \models)$ a été introduite dans [7] mais peu étudiée. Comme une formule $\varphi \in \Delta\mathcal{L}\mathcal{P}$ représente un sous-ensemble $\mathcal{M}(\varphi)$ de $\Delta\Omega = \Omega \times \Omega$, on peut la considérer comme une représentation d'une relation binaire sur $\Omega$. Les relations binaires sur un ensemble peuvent se composer et la composition des formules de variations correspond à la composition entre relations binaires.

Plus formellement, soit $\varphi, \psi \in \Delta\mathcal{L}\mathcal{P}$. La composition de $\varphi$ et $\psi$ est une formule $\varphi ; \psi$ définie à la syntaxe près par

$$ \mathcal{M}(\varphi ; \psi) = \left\{ \mathcal{I}\mathcal{K} \in \Delta\Omega \mid \begin{array}{l} \text{il existe } \mathcal{J} \in \Omega \text{ telle que} \\ \mathcal{I}\mathcal{J} \models \varphi \text{ et } \mathcal{J}\mathcal{K} \models \psi \end{array} \right\} $$

Le résultat suivant est une conséquence directe de l'associativité de la composition de relations binaires :

$$ \text{pour } \varphi, \psi, \chi \in \Delta\mathcal{L}\mathcal{P}, (\varphi ; \psi) ; \chi \equiv \varphi ; (\psi ; \chi) $$

Cela permet d'omettre des parenthèses dans les compositions.

La recherche d'une formule équivalente à $\varphi ; \psi$ va être étudiée via les propositions ci-dessous.

On commence par le cas particulier où les formules à composer sont de la forme $\alpha \triangleright \beta$.

**Proposition 4.** Soit $\alpha, \beta, \gamma, \delta \in \mathcal{L}\mathcal{P}$. On a :

$$ (\alpha \triangleright \beta) ; (\gamma \triangleright \delta) \equiv \left\{ \begin{array}{ll} \perp & si \beta \wedge \gamma \models \perp \\ \alpha \triangleright \delta & sinon \end{array} \right. $$

On s'intéresse ensuite aux liens entre composition et disjonction :

**Proposition 5.** Soit $\varphi, \varphi_1, \varphi_2, \psi, \psi_1, \psi_2 \in \Delta\mathcal{L}\mathcal{P}$. On a les équivalences suivantes :

$$ \varphi ; (\psi_1 \vee \psi_2) \equiv (\varphi ; \psi_1) \vee (\varphi ; \psi_2) \qquad (12) $$

$$ (\varphi_1 \vee \varphi_2) ; \psi \equiv (\varphi_1 ; \psi) \vee (\varphi_2 ; \psi) \qquad (13) $$

**Définition 4.** On introduit deux symboles de variations supplémentaires $\perp_{\mathcal{D}}$ et $\top_{\mathcal{D}}$ tels que, pour tout $\alpha \in \mathcal{L}\mathcal{P}$, $\alpha^{\perp_{\mathcal{D}}} = \perp \triangleright \perp = \perp_{\Delta}$ et $\alpha^{\top_{\mathcal{D}}} = \top \triangleright \top = \top_{\Delta}$.

À un cube $\varphi$ de $(\Delta\mathcal{L}\mathcal{P}, \models)$ on associe $\mathrm{var}(x, \varphi) \in \mathcal{D} \cup \{\top_{\mathcal{D}}\}$ de la façon suivante :

$$ \mathrm{var}(x, \varphi) = \begin{cases} \top_{\mathcal{D}} & si x \notin \mathcal{V}(\varphi) \\ \vee & si x^{\mathcal{V}} \text{ est un des termes de } \varphi \end{cases} $$

La proposition suivante permet de calculer la composition de deux atomes de $(\Delta\mathcal{L}\mathcal{P}, \models)$ construits sur la même variable.

**Proposition 6.** Il existe une opération binaire ; sur $\mathcal{D} \cup \{\perp_{\mathcal{D}}, \top_{\mathcal{D}}\}$ telle que pour une variable $a$, on a $a^{\mathcal{V}} ; a^{\mathcal{W}} \equiv a^{\mathcal{V};\mathcal{W}}$.
**Principe de la preuve.** À chaque symbole de variation v on associe $A^v$, une matrice $2 \times 2$ de booléens telle que les lignes et les colonnes sont indexées par $(i, j) \in \{0, 1\}^2$ et tel que $A^v = [A_{ij}^v]_{ij}$ est défini comme suit (où $a$ est une variable arbitraire et $\mathcal{I}\mathcal{J} \in \Delta\Omega)$ :

$$A_{\mathcal{I}(a)}^{v} \mathcal{J}(a) = \begin{cases} 1 & \text{si } \mathcal{I}\mathcal{J} \models a^v \\ 0 & \text{sinon} \end{cases}$$

$$\text{Ainsi, } A^{\perp\mathcal{D}} = \begin{pmatrix} \mathbf{0} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{pmatrix}, A^{+} = \begin{pmatrix} \mathbf{0} & 1 \\ \mathbf{0} & \mathbf{0} \end{pmatrix} \text{ et } A^{\#} = \begin{pmatrix} \mathbf{0} & 1 \\ 1 & \mathbf{0} \end{pmatrix}.$$

On montre ensuite que, pour $v, w \in \mathcal{D} \cup \{\perp\mathcal{D}, \top_{\mathcal{D}}\}$, le produit des matrices $A^v \times A^w$ (où la somme et le produit correspondent aux ou et au et sur les booléens) donne une matrice $A^u$ où $u \in \mathcal{D} \cup \{\perp\mathcal{D}, \top_{\mathcal{D}}\}$ (et on notera $u = v ; w$).

Il reste à montrer que le produit des matrices correspond bien à une composition au sens où, pour $a \in \mathcal{V}$, $a^v ; a^w = a^{v;w}$. Pour ce faire, un programme Python a été développé pour automatiser le calcul d'une table de composition. ■

Cela permet alors de calculer la composition de cubes :

**Proposition 7.** *Soit $\varphi$ et $\psi$, deux cubes de $(\Delta\mathcal{L}\mathcal{P}, \models)$. On a :*

$$\varphi; \psi \equiv \bigwedge_{a \in \mathcal{V}} a^{\mathrm{var}(a, \varphi); \mathrm{var}(a, \psi)} \quad (14)$$

Pour composer deux cubes, on applique la proposition 7 et on simplifie en se rappelant que $x^{\top\mathcal{D}} \equiv \top$ et $x^{\perp\mathcal{D}} \equiv \perp$. Par exemple, si l'ensemble des variables est $\{a, b, c, d, e\}$ alors

$$\begin{align*}
& a^{+} \wedge b^{-} \wedge d^{\neq 0} ; a^{-} \wedge c^{-} \wedge d^{+} \\
& \equiv a^{\neq 0} \wedge b^{\top\mathcal{D}} \wedge c^{\bullet 0} \wedge d^{+} \wedge e^{\top\mathcal{D}} \\
& \equiv a^{\neq 0} \wedge c^{\bullet 0} \wedge d^{+}
\end{align*}$$

(en s'appuyant sur une table de composition sur $\mathcal{D}$ disponible dans [8]).

De façon générale, une façon d'avoir une expression synthétique pour $\varphi ; \psi$ consiste à mettre ces deux formules de $(\Delta\mathcal{L}\mathcal{P}, \models)$ sous FND puis à appliquer les équivalences de la proposition 5 tant que c'est possible pour enfin appliquer la proposition 7 et se débarrasser complètement du symbole ;.

# 4 Représenter des règles d'adaptation

Cette section vise de façon générale à formaliser dans $(\Delta\mathcal{L}\mathcal{P}, \models)$ ce qu'est une règle d'adaptation et comment raisonner avec.

## 4.1 Introduction d'un exemple

On considère un exemple dans le domaine culinaire : un problème représente une requête de recette et une solution,

une recette. On suppose que les problèmes et les solutions s'expriment en logique propositionnelle. Dans cet exemple, on suppose que l'ensemble des connaissances du domaine est vide : $CD = \top$. Le problème d'adaptation est $(c^s, x^{cible})$ où

- $c^s$ est le cas source correspondant à une recette de salade, avec de la batavia, du magret de canard, des tomates, de l'huile d'olive et du vinaigre :

$$c^s = \begin{array}{l} \mathit{rSalade} \wedge \mathit{iBatavia} \wedge \mathit{iMagret} \wedge \mathit{iTomate} \\ \phantom{c^s =} \wedge \mathit{iHuileDOlive} \wedge \mathit{iVinaigre} \wedge \mathit{rien d'autre} \end{array}$$

où $\mathit{rSalade}$ se lit « recette de salade », $\mathit{iMachin}$, « recette avec l'ingrédient machin » et $\mathit{rien d'autre}$ est une notation pour la conjonction des littéraux négatifs $\neg a$ tels que $a$ ne peut être déduit du début de la formule : $\alpha \wedge \mathit{rien d'autre} \equiv \alpha \wedge \wedge\{\neg a \mid a \in \mathcal{V} \text{ et } \alpha \not\models_{CD} a\}$. En particulier, $c^s \models_{CD} \neg \mathit{iAil}$. Notons que $c^s$ est un cube complet.

- $x^{cible}$ est le problème cible « Je veux une recette de salade avec des tomates, du jus de citron, mais pas d'ail. » :

$$x^{\mathrm{cible}} = \mathit{rSalade} \wedge \mathit{iTomate} \wedge \mathit{iJusCitron} \wedge \neg \mathit{iAil}$$

La connaissance du problème d'adaptation $(c^s, x^{cible})$ permet de partitionner $\mathcal{V}$ en $\{\mathcal{V}_P, \mathcal{V}_S\}$ : $\mathcal{V}_P = \{\mathit{rSalade}, \mathit{iTomate}, \mathit{iJusCitron}, \mathit{iAil}\}$ (variables de $x^{cible}$) et $\mathcal{V}_S = \mathcal{V} \setminus \mathcal{V}_P$. Par conséquent, $c^s$ s'écrit $c^s = x^s \wedge y^s$ avec

$$\begin{align*}
x^s &= \mathit{rSalade} \wedge \mathit{iTomate} \wedge \neg \mathit{iJusCitron} \wedge \neg \mathit{iAil} \\
y^s &= \mathit{iBatavia} \wedge \mathit{iMagret} \wedge \mathit{iHuileDOlive} \\
    &\phantom{= iBatavia} \wedge \mathit{iVinaigre} \wedge \dots
\end{align*}$$

(les points de suspension correspondant à la conjonction des littéraux $\neg a$ où $a \in \mathcal{V}_S$ et $a$ n'est pas un littéral positif de $y^s$).

On considère également un motif $M$ obtenu par un système d'extraction de motifs (p. ex., de motifs fermés fréquents) pour l'acquisition de connaissances d'adaptation. Un tel motif contient un ensemble fini d'atomes $a^v$ indiquant des variations « simultanées » entre cas et s'interprète par la conjonction $\varphi$ de ces éléments. $\varphi$ peut s'écrire comme un cube de $(\Delta\mathcal{L}\mathcal{P}, \models)$ : si plusieurs atomes $a^{v_1}, a^{v_2}, \dots$ construits sur la même variable $a$ apparaissent dans $\varphi$, on peut montrer qu'ils peuvent être remplacés par un seul $a^v$. Dans cet exemple, on va considérer la formule suivante :

$$\varphi = \mathit{rSalade}^{=1} \wedge \mathit{iVinaigre}^{-} \wedge \mathit{iJusCitron}^{+} \wedge \mathit{iSel}^{+}$$

Le motif $M$ dont est issu $\varphi$ traduit le fait qu'on a observé un nombre suffisant de couples de recettes de salades avec du vinaigre dans la première mais pas dans la seconde, et du jus de citron et du sel dans la seconde mais pas dans la première. Par conséquent, si on considère que $\varphi$
est une règle d'adaptation, alors, on va considérer l'appli-
cabilité et l'application de $\varphi$ sur un problème d'adaptation
((x<sup>s</sup>, y<sup>s</sup>), x<sup>cible</sup>).

4.2 Représenter une règle d'adaptation

Une règle d'adaptation est définie comme étant un couple
R = (φ, C) où φ ∈ ΔLP et C est un réel positif appelé coût
de R.

Que signifie que R est applicable sur un problème d'adaptation ((x<sup>s</sup>, y<sup>s</sup>), x<sup>cible</sup>) et comment définir le résultat de cette application ? Pour répondre à cette question, on va s'appuyer sur une fonction qui à (α, φ, γ) ∈ LP × ΔLP × LP associe appl(α, φ, γ) ∈ LP, l'application sur α de φ sous contrainte γ, fonction qui va être définie et étudiée dans la section 4.3. Comme les cas sources et le problème cible doivent être considérés avec les connaissances du domaine CD, on calculera la formule suivante :

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

Si $\beta \models \perp$ alors on dira que $R$ n'est pas applicable sur le problème d'adaptation. Sinon, ce résultat s'écrira $\beta \equiv CD \wedge \mathbf{x}^{\text{cible}} \wedge y^{\text{cible}}$ où $y^{\text{cible}}$ sera la solution proposée pour $\mathbf{x}^{\text{cible}}$ par application de $R$ sur le problème d'adaptation.

Le RàPC est généralement hypothétique et l'adaptation
ne constitue pas nécessairement une solution correcte au
problème cible. Ainsi, une règle d'adaptation R = (φ, C)
peut produire une telle solution incorrecte. Pour choisir
entre plusieurs règles d'adaptation, on utilise C : le coût
associé à cette règle est indicatif de la qualité de R. Plus
C est élevé, moins la confiance en l'application de la règle
sera grande; on pourrait, par exemple, associer C a une
mesure de la probabilité P que la règle donnera un résultat
correct par C = − log P (sous des hypothèses de distribution
données).

4.3 Appliquer une formule des variations sur une formule propositionnelle

Cette section vise à définir une notion d'application d'une
formule $\varphi \in \Delta LP$ sur une formule $\alpha \in LP$, en présence
d'une contrainte $\gamma$ sur le résultat.

On va noter appl(α, φ, γ) l'application sur α de φ sous contrainte γ. Pour arriver à sa définition, on s'intéressera d'abord à la transformation de α par φ sous contrainte γ, une formule transf(α, φ, γ) ∈ ΔLP dont le résultat (la partie droite) sera appl(α, φ, γ) = D(transf(α, φ, γ)).

On propose les trois conditions suivantes sur $\mathcal{I}\mathcal{J} \in \Delta\Omega$
pour que $\mathcal{I}\mathcal{J} \models \text{transf}(\alpha, \varphi, \gamma)$ : $\mathcal{I} \models \alpha$, $\mathcal{I}\mathcal{J} \models \varphi$ et $\mathcal{J} \models \gamma$.
Ces trois conditions peuvent s'écrire en une seule :

$$
\mathcal{I} \mathcal{J} \models (\alpha \triangleright \gamma) \wedge \varphi \qquad (16)
$$

Cette condition est-elle suffisante ? Considérons
l'exemple suivant : α = a ∧ ¬b ∧ c, φ = a⁻ ∧ b⁺ et γ = τ.

Si (16) était une condition nécessaire et suffisante pour que
$IJ \models \text{transf}(\alpha, \varphi, \gamma)$ alors $\text{appl}(\alpha, \varphi, \gamma)$ serait équivalente
à $D(\varphi)$ donc à $\neg a \wedge b$. Donc, que $\alpha \models c$ ou que $\alpha \models \neg c$
ne changerait pas l'application de $\varphi$ sur $\alpha$. Nous suppose-
rons au contraire que si une variable (dans cet exemple $c$)
est invariante dans $\varphi$, sa valeur doit être inchangée par la
transformation, d'où l'utilisation du ceteris paribus (et la
justification a posteriori de son étude) : on supposera donc
que $IJ \models cp(\varphi)$. L'idée est que la formule $\varphi$ représente
de façon compacte une transformation et que quand elle
ne dit rien sur une variable $x$, celle-ci est inchangée par la
transformation : si $x \in \text{inv}(\varphi)$ et $\alpha \models x$ (resp. $\alpha \models \neg x$) alors,
avec $\beta = \text{appl}(\alpha, \varphi, \gamma)$, $\beta \models x$ (resp. $\beta \models \neg x$). On aboutit
ainsi à la définition suivante :

**Définition 5.** *Pour $\varphi \in \Delta LP$ et $\alpha, \gamma \in LP$, on définit la transformation d’$\alpha$ par $\varphi$ sous contrainte $\gamma$ ainsi :*

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

L'application de $\varphi$ sur $\alpha$ sous contrainte $\gamma$ est le résultat de cette transformation :

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

On dira que $\varphi$ est applicable sur $\alpha$ sous contrainte $\gamma$
si $\mathrm{appl}(\alpha, \varphi, \gamma) \not\models \perp$. Deux conditions nécessaires (mais
non suffisantes) d'applicabilité sont $\alpha \wedge \mathcal{G}(\varphi) \not\models \perp$ et
$D(\varphi) \wedge \gamma \not\models \perp$.

Malgré l'usage du ceteris paribus, si α, φ et γ contiennent
peu de variables (relativement à |V|) on peut calculer
appl(α, φ, γ) sans avoir à considérer toutes les variables,
comme la proposition suivante le montre :

**Proposition 8.** *Soit $\alpha, \gamma \in LP$ et $\varphi \in \Delta LP$ telles que $\varphi$ peut s'appliquer sur $\alpha$ sous contrainte $\gamma$. Soit $W = V(\alpha) \cup V(\varphi) \cup V(\gamma)$. On a :*

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

**Preuve.** Soit $\beta_1 = \mathrm{appl}(\alpha, \varphi, \gamma) = D((\alpha \triangleright \gamma) \wedge \mathrm{cp}(\varphi))$ et $\beta_2 = D((\alpha \triangleright \gamma) \wedge \mathrm{cp}_W(\varphi))$. On cherche à montrer que $\beta_1 \equiv \beta_2$.

Comme cp(φ) ⊨ cp<sub>W</sub>(φ), on en déduit que β₁ ⊨ β₂ (en particulier parce que si ψ ⊨ ψ' alors D(ψ) ⊨ D(ψ') pour toute ψ ∈ ΔLP).
Montrons que β₂ ⊨ β₁.

Soit $\mathcal{J} \in \mathcal{M}(\beta_2)$ : il reste donc
à montrer que $\mathcal{J} \models \beta_1$. Par définition de $\beta_2$, il existe $\mathcal{I} \in \Omega$
telle que $\mathcal{I}\mathcal{J} \models (\alpha \triangleright \gamma) \wedge \mathrm{cp}_W(\varphi)$. Soit alors $\mathcal{I}' \in \Omega$
définie (pour $x \in \mathcal{V}$) par $\mathcal{I}'(x) = \begin{cases} \mathcal{I}(x) & \text{si } x \in \mathcal{W} \\ \mathcal{J}(x) & \text{sinon} \end{cases}$. On
va montrer que $\mathcal{I}'\mathcal{J} \models (\alpha \triangleright \gamma) \wedge \mathrm{cp}(\varphi)$ ce qui impliquera
que $\mathcal{J} \models \beta_2$. Pour cela, il suffit de montrer les assertions
suivantes :

$$
(A1) \mathcal{I}'\mathcal{J} \models \alpha \triangleright \gamma;
$$
(A2) $I'J \models \varphi$;

(A3) Pour toute $x \in \text{Inv}(\varphi)$, $I'J \models x^=.$

Comme la seule différence entre $I$ et $I'$ concerne des variables qui ne sont pas dans $V(\alpha)$ (puisque hors de $W$) et que $I \models \alpha$, on a donc $I' \models \alpha$. Comme $J \models \gamma$, on a donc (A1).

De la même façon, la seule différence entre $IJ$ et $I'J$ concerne des variables qui ne sont pas dans $V(\varphi)$ (puisque hors de $W$) et que $IJ \models \varphi$, on a donc $I'J \models \varphi$, d'où (A2).

Soit $x \in \text{Inv}(\varphi)$. Pour montrer (A3), il suffit de montrer que $I'(x) = J(x)$. Si $x \notin W$, par définition de $I'$, c'est vérifié. Si $x \in W$, on a donc $x \in \text{Inv}(\varphi) \cap W$, donc $\text{cp}_W(\varphi) \models x^=\text{ (d'après la définition 3). Comme } IJ \models \text{cp}_W(\varphi) \text{ on a donc } IJ \models x^=\text{, i.e. } I(x) = J(x)$. Or, $I'(x) = I(x)$ puisque $x \in W$. On a donc $I'(x) = J(x)$, ce qui permet de prouver (A3) et qui conclut la preuve. ■

La proposition suivante permet de calculer en $O(|V(\alpha)| + |V(\varphi)| + |V(\gamma)|)$ l'applicabilité et l'application de $\varphi$ sur $\alpha$ dans le cas où $\alpha$ et $\beta$ sont des cubes et $\varphi$ est un cube primitif.

**Proposition 9.** Soit $\alpha$ et $\gamma$ deux cubes de $(LP, \models)$ et $\varphi$, un cube primitif de $(\Delta LP, \models)$. Soit $W = V(\alpha) \cup V(\varphi) \cup V(\gamma)$. On peut donc écrire $\alpha \equiv \bigwedge_{a \in W} \ell(a)$, $\gamma \equiv \bigwedge_{a \in W} p(a)$, et $\varphi \equiv \bigwedge_{a \in W} m(a) \triangleright n(a)$ où les $\ell(a)$, $m(a)$, $n(a)$ et $p(a)$ appartiennent à $\{a, \neg a, \top\}$. On a donc $a \in V(\alpha)$ ssi $\ell(a) \neq \top$, $a \in V(\gamma)$ ssi $p(a) \neq \top$ et $a \in V(\varphi)$ ssi $m(a) \neq \top$ ou (de façon équivalente) $n(a) \neq \top$ (puisque $\varphi$ est un cube primitif).

Pour $a \in W$, on définit $f(a) \in \{a, \neg a, \perp\}$ de la façon suivante. Si $\ell(a) \wedge m(a) \models \perp$, $n(a) \wedge p(a) \models \perp$ ou $(\ell(a) \wedge m(a), n(a) \wedge p(a)) = (\perp, \perp)$ alors $f(a) = \perp$. Sinon,

$$f(a) = \begin{cases} \ell(a) & \text{si } \ell(a) \neq \top \text{ et } m(a) = n(a) = \top \\ p(a) & \text{si } \ell(a) = \top \text{ et } m(a) = n(a) = \top. \\ n(a) & \text{sinon} \end{cases}$$

On a alors : $\text{appl}(\alpha, \varphi, \gamma) \equiv \bigwedge_{a \in W} f(a)$

Par conséquent, $\varphi$ est applicable sur $\alpha$ sous contrainte $\gamma$ ssi pour toute $a \in W$, $f(a) \neq \perp$.

La preuve de cette proposition (détaillée dans [8]) consiste essentiellement à détailler tous les cas possibles selon l'appartenance ou non de $a$ à $V(\alpha)$, à $V(\varphi)$ et à $V(\gamma)$ ($2^3 = 8$ cas à considérer, donc).

Enfin, la proposition suivante permet de calculer $\text{appl}(\alpha, \varphi, \gamma)$ où $\varphi$ est un cube primitif mais où $\alpha$ et $\gamma$ sont quelconques, en s'appuyant sur des mises sous forme normale disjonctive de $\alpha$ et $\gamma$ et sur la proposition 9.

**Proposition 10.** Soit $\alpha, \alpha_1, \alpha_2, \beta, \beta_1, \beta_2 \in LP$ et $\varphi \in \Delta LP$. On a les équivalences suivantes :

$$\text{appl}(\alpha_1 \vee \alpha_2, \varphi, \gamma) \equiv \text{appl}(\alpha_1, \varphi, \gamma) \vee \text{appl}(\alpha_2, \varphi, \gamma)$$

$$\text{appl}(\alpha, \varphi, \gamma_1 \vee \gamma_2) \equiv \text{appl}(\alpha, \varphi, \gamma_1) \vee \text{appl}(\alpha, \varphi, \gamma_2)$$

**Preuve.** On a :

$$\begin{align*} \text{transf}(\alpha_1 \vee \alpha_2, \varphi, \gamma) &= ((\alpha_1 \vee \alpha_2) \triangleright \gamma) \wedge \text{cp}(\varphi) \\ &= ((\alpha_1 \triangleright \gamma) \wedge \text{cp}(\varphi)) \vee ((\alpha_2 \triangleright \gamma) \wedge \text{cp}(\varphi)) \\ &= \text{transf}(\alpha_1, \varphi, \gamma) \vee \text{transf}(\alpha_2, \varphi, \gamma) \end{align*}$$

D'après (2), on en déduit la première équivalence de la proposition. La deuxième équivalence se prouve de façon similaire. ■

## 4.4 Application d'une règle d'adaptation sur l'exemple

On considère le problème d'adaptation $((x^s, y^s), x^{cible})$ et la formule $\varphi$ de la section 4.1, ainsi que la règle d'adaptation $R = (\varphi, C)$ où $C$ est choisi arbitrairement. En appliquant (15) sur cet exemple, on obtient un $\beta \in LP$ qui est satisfiable et tel que $\beta \equiv CD \wedge x^{cible} \wedge y^{cible}$ avec

$$y^{\text{cible}} = i\text{Batavia} \wedge i\text{Magret} \wedge i\text{HuileD} \text{Olive} \\ \wedge i\text{JusCitron} \wedge i\text{Sel} \wedge \dots$$

(qui est le résultat attendu sur cet exemple).

## 4.5 Un algorithme pour le RàPC

Une approche du RàPC utilisée dans le système Taaable [3], notamment, consiste à effectuer une remémoration s'appuyant sur une transformation minimale du problème cible afin qu'il s'apparie exactement avec au moins un cas source puis à utiliser une « transformation inverse » sur un cas remémoré pour obtenir une solution.

Dans le cadre de représentation de cet article, pour implanter cette approche, les transformations considérées seront celles associées aux règles d'adaptation $R = (\varphi, C)$ : on considérera la transformation par la règle $R^{-1} = (\varphi^{-1}, C)$ (pour garantir un résultat, on pourra ajouter les règles $(a^\ddagger, C)$, pour $a \in V$). En supposant que les coûts sont additifs, la remémoration retournera non seulement un (ou plusieurs) $(x^s, y^s)$ mais également une séquence de règles $R_1^{-1}, R_2^{-1}, \dots, R_q^{-1}$ telle que, avec $x^0 = CD \wedge x^{cible}$ et, pour $i \in \{1, 2, \dots, q\}$, $x^i = \text{appl}(x^{i-1}, \varphi_i^{-1}, \top)$ (où $R_i = (\varphi_i, C_i)$), avec $x^s \wedge y^s \models_{CD} x^q$. La transformation sera de coût $\sum_{i=1}^q C_i$.

Une fois un cas $(x^s, y^s)$ remémoré avec une séquence de règles d'adaptation $R_1^{-1}, R_2^{-1}, \dots, R_q^{-1}$ associée, l'idée est d'appliquer la séquence inverse de ces règles sur $x^s \wedge y^s$ pour résoudre $x^{cible}$ : avec $y^q$ tel que $x^s \wedge y^s \equiv x^q \wedge y^q$, on calcule successivement $y^{q-1}, \dots, y^0$ avec, pour $i \in \{q-1, q-2, \dots, 0\}$, $x^i \wedge y^i \equiv \text{appl}(x^{i+1} \wedge y^{i+1}, \varphi_{i+1}, x^i)$. Avec $y^{cible}$ telle que $CD \wedge x^{cible} \wedge y^{cible} \equiv x^0 \wedge y^0$, on a alors une proposition de solution de $x^{cible}$, adaptée en $q$ étapes à partir du cas remémoré.

Pour qu'une telle adaptation soit possible, il faut que les règles d'adaptation $R_i$ soient applicables. Cela est garanti
par la proposition suivante, dans le cas où $x^s \wedge y^s$, $x^{cible}$ et $\varphi_i$ sont des cubes :

**Proposition 11.** *Soit $\alpha$ et $\gamma$, deux cubes de $(\mathcal{LP}, \models)$ et $\varphi$, un cube de $(\Delta\mathcal{LP}, \models)$. On a :*

$$ \mathrm{appl}(\alpha, \varphi, \gamma) \nvDash \top \quad \mathrm{ssi} \quad \mathrm{appl}(\gamma, \varphi^{-1}, \top) \wedge \alpha \nvDash \bot $$

La preuve de cette proposition (détaillée dans [8]) consiste à reprendre le découpage en 8 cas de la preuve de la proposition 9.

On montre que $x^i \wedge y^i$ est satisfiable pour tout $i \in \{0, 1, \dots, q\}$ en partant de la fin :

(i = q) Comme, par définition, $x^q \wedge y^q$ est équivalente au cube complet $x^s \wedge y^s$ et que les cubes sont satisfiables, $x^q \wedge y^q \nvDash \bot$.

(i = q - 1) $x^{q-1} \wedge y^{q-1} \equiv \mathrm{appl}(x^q \wedge y^q, \varphi_q, x^{q-1})$ qui, d'après la proposition 11, est satisfiable ssi $\beta$ est satisfiable avec $\beta = \mathrm{appl}(x^{q-1}, \varphi_q^{-1}, \top) \wedge x^q \wedge y^q$. Or, par définition de $x^q$, $\beta \equiv x^q \wedge x^q \wedge y^q \equiv x^q \wedge y^q$ qui est satisfiable (cf. cas (i = q)), donc $\beta$ est satisfiable et par conséquent $x^{q-1} \wedge y^{q-1} \nvDash \bot$.

(i = q - 2) $x^{q-2} \wedge y^{q-2} \equiv \mathrm{appl}(x^{q-1} \wedge y^{q-1}, \varphi_{q-1}, x^{q-2})$ qui, d'après la proposition 11, est satisfiable ssi $\beta$ est satisfiable avec $\beta = \mathrm{appl}(x^{q-2}, \varphi_{q-1}^{-1}, \top) \wedge x^{q-1} \wedge y^{q-1}$. Or, par définition de $x^{q-1}$, $\beta \equiv x^{q-1} \wedge x^{q-1} \wedge y^{q-1} \equiv x^{q-1} \wedge y^{q-1}$ qui est satisfiable (cf. cas (i = q - 1)), donc $\beta$ est satisfiable et par conséquent $x^{q-2} \wedge y^{q-2} \nvDash \bot$.

(i = 0) $x^0 \wedge y^0 \equiv \mathrm{appl}(x^1 \wedge y^1, \varphi_1, x^0)$ qui, d'après la proposition 11, est satisfiable ssi $\beta$ est satisfiable avec $\beta = \mathrm{appl}(x^0, \varphi_1^{-1}, \top) \wedge x^1 \wedge y^1$. Or, par définition de $x^1$, $\beta \equiv x^1 \wedge x^1 \wedge y^1 \equiv x^1 \wedge y^1$ qui est satisfiable (cf. cas (i = 1)), donc $\beta$ est satisfiable et par conséquent $x^0 \wedge y^0 \nvDash \bot$.

Comme $\mathrm{CD} \wedge \mathrm{x}^{\mathrm{cible}} \wedge \mathrm{y}^{\mathrm{cible}} \equiv x^0 \wedge y^0$, $\mathrm{CD} \wedge \mathrm{x}^{\mathrm{cible}} \wedge \mathrm{y}^{\mathrm{cible}}$ est satisfiable : l'adaptation donne bien un résultat cohérent.

Notons enfin que cet algorithme peut être utilisé pour résoudre un problème d'adaptation (($x^s, y^s$), $x^{cible}$) (quand un cas ($x^s, y^s$) a déjà été choisi). Il suffit pour cela de l'appliquer à une base de cas singleton $\mathrm{BC} = \{(x^s, y^s)\}$.

## 4.6 Vers une composition des règles d'adaptation

L'algorithme de la section 4.5 s'appuie sur une séquence d'applications de règles d'adaptation. La question ouverte qui est posée ici est le calcul d'une composition de règles d'adaptation : étant donnés deux telles règles $R_1$ et $R_2$, peut-on définir une règle $R$ telle que l'application de $R$ équivaut à l'application successive de $R_1$ et de $R_2$ ? A priori, la composition des formules présentée à la section 3.5 devrait être utile ici, mais nous n'avons pas de réponse définitive à cette question pour l'heure.

Un intérêt de définir une telle composition de règles serait dans le post-traitement de l'apprentissage de ces règles. Si on utilise, par exemple, une extraction de motifs fermés

fréquents, elle produira souvent un grand nombre de motifs $M$ interprétables en règles $R$. S'il était possible de trouver une famille génératrice minimale pour la composition de ces règles, cela diminuerait leur nombre (et le temps de calcul) sans altérer l'inférence.

# 5 Discussion et liens avec d'autres travaux

Dans [7], ($\Delta\mathcal{LP}, \models$) était comparée avec d'autres formalismes. Cette comparaison est complétée en section 5.1, sous l'angle des deux types d'inférences associées aux règles d'adaptation. La section 5.2 traite plus en détail du lien entre ($\Delta\mathcal{LP}, \models$) et une logique dynamique.

## 5.1 Observations et actions

Les mécanismes liés à l'adaptation par transformation présentés dans la section 4 peuvent être partagés en mécanismes d'observations et mécanismes d'actions.

Les mécanismes d'observations apparaissent lors de l'ap-prentissage de connaissances d'adaptation (évoquée dans la section 2.2) dans laquelle sont observées des variations entre cas sources.

Étant donné une règle d'adaptation $R = (\varphi, C)$ et un problème d'adaptation (($x^s, y^s$), $x^{cible}$), l'application de $R$ sur (($x^s, y^s$), $x^{cible}$) peut être apparentée à un mécanisme d'action : on crée une hypothèse de solution $y^{cible}$ de $x^{cible}$, partant de ($x^s, y^s$). Donc, en assimilant un cas à un état et une règle d'adaptation à une action, on peut considérer l'application d'une règle d'adaptation comme l'application d'une action sur un état, pour obtenir un nouvel état (sachant que ce nouvel état est contraint par $x^{cible}$).

L'application de règles d'adaptation invite donc à se pencher sur les formalismes et inférences relatives aux actions (voir la synthèse [6]). En l'occurrence, les actions considérées sont déterministes : si une action est applicable sur un état, elle génère un état et un seul. Dans la section suivante, nous nous intéresserons à une logique dynamique et à ses liens avec ($\Delta\mathcal{LP}, \models$).

Une dernière remarque peut être faite. On pourrait imaginer faire le lien entre les observations et les actions épistémiques (également évoquées dans [6]). Cependant, le lien avec les observations dont il est question ici (observer des variations entre deux cas) et les actions épistémiques (agir pour observer et acquérir/modifier des connaissances sur l'état actuel) ne s'est pas révélé fructueux (ou pas encore).

## 5.2 ($\Delta\mathcal{LP}, \models$) et DL-PA

La logique DL-PA (*dynamic logic of propositional assumptions*) est une logique dynamique dont les programmes atomiques sont des affectations de variables propositionnelles, i.e. des expressions $+a$ et $-a$ pour $a \in V$ correspondant à une affectation de $a$ par respectivement 1 et 0 [1].
Les formules de DL-PA sont des variables propositionnelles, des formules construites à partir d'autres formules en utilisant les connecteurs de la logique propositionnelle et les formules de la forme $\langle\pi\rangle\alpha$ où $\pi$ est un programme et $\alpha$ est une formule. Les programmes sont soit des programmes atomiques, soit d'une des formes $\pi_1$ ; $\pi_2$, $\pi_1 \cup \pi_2$, $\pi^*$ et $\alpha$? (où $\pi$, $\pi_1$ et $\pi_2$ sont des programmes et où $\alpha$ est une formule).

La sémantique d'une formule $\alpha$ est donnée par un sous-ensemble $\mathcal{M}(\alpha)$ de $\Omega$ et celle d'un programme $\pi$ par un sous-ensemble $\mathcal{M}(\pi)$ de $\Omega \times \Omega = \Delta\Omega$, ce qui suggère d'étudier les liens entre les programmes de DL-PA et les formules de $(\Delta\mathcal{L}\mathcal{P}, \models)$. Cette sémantique est définie de façon habituelle pour les variables propositionnelles et les formules construites sur les connecteurs, et pour le reste on a (pour $a \in \mathcal{V}$, $\alpha$, une formule, $\pi, \pi_1$ et $\pi_2$, des programmes) :

$$ \mathcal{M}(\langle\pi\rangle\alpha) = \left\{ \mathcal{I} \in \Omega \mid \begin{array}{l} \text{il existe } \mathcal{J} \in \Omega \text{ telle que} \\ \mathcal{I}\mathcal{J} \models \pi \text{ et } \mathcal{J} \models \alpha \end{array} \right\} $$

$$ \mathcal{M}(+a) = \left\{ \begin{array}{l} \mathcal{I}\mathcal{J} \in \Delta\Omega \\ \mathcal{J} \models a \\ \text{et, pour toute } b \in \mathcal{V} \setminus \{a\}, \\ \mathcal{I}(b) = \mathcal{J}(b) \end{array} \right\} $$

$$ \mathcal{M}(-a) = \left\{ \begin{array}{l} \mathcal{I}\mathcal{J} \in \Delta\Omega \\ \mathcal{J} \models \neg a \\ \text{et, pour toute } b \in \mathcal{V} \setminus \{a\}, \\ \mathcal{I}(b) = \mathcal{J}(b) \end{array} \right\} $$

$$ \mathcal{M}(\pi_1; \pi_2) = \left\{ \mathcal{I}\mathcal{K} \in \Delta\Omega \mid \begin{array}{l} \text{il existe } \mathcal{J} \in \Omega \text{ telle que} \\ \mathcal{I}\mathcal{J} \models \pi_1 \text{ et } \mathcal{J}\mathcal{K} \models \pi_2 \end{array} \right\} $$

$$ \mathcal{M}(\pi_1 \cup \pi_2) = \mathcal{M}(\pi_1) \cup \mathcal{M}(\pi_2) $$

$$ \mathcal{M}(\alpha?) = \{\mathcal{I}\mathcal{I} \mid \mathcal{I} \in \mathcal{M}(\alpha)\} $$

Enfin, $\mathcal{I}\mathcal{J} \models \pi^*$ s'il existe une séquence $\mathcal{I}_0, \mathcal{I}_1, \dots, \mathcal{I}_p$ ($p \ge 0$) telle que $\mathcal{I}_0 = \mathcal{I}, \mathcal{I}_p = \mathcal{J}$ et $\mathcal{I}_k \mathcal{I}_{k+1} \models \pi$ pour tout $k \ge 0$ et $k < p$.

Le ceteris paribus sur des formules de $(\Delta\mathcal{L}\mathcal{P}, \models)$ va être utile pour faire le lien de formules de cette logique vers des programmes de DL-PA. On peut aussi définir une opération sur les programmes de DL-PA permettant de faire un lien dans l'autre sens. Cela suppose que l'ensemble des variables propositionnelles est fini et fixé, contrairement à l'hypothèse d'un ensemble dénombrable de variables qui est faite dans [1]. On fera donc cette restriction dans la suite de cette section.

On part de l'observation que le programme $+a \cup -a$ (pour $a \in \mathcal{V}$) fait l'inverse d'une affectation : même si $a$ est affecté à une valeur ($0$ ou $1$) dans l'état de départ, l'exécution de ce programme fait que $a$ n'a pas d'affection après l'exécution de ce programme. On généralise cela à un ensemble $\mathcal{W} = \{a_1, \dots, a_p\}$ de variables :

$$ \text{désaff}(\{a_1, \dots, a_p\}) = (+a_1 \cup -a_1); \dots; (+a_p \cup -a_p) $$

La table 1 donne des égalités entre ensembles de modèles de certaines formules de $(\Delta\mathcal{L}\mathcal{P}, \models)$ et ensembles de modèles de certains programmes de DL-PA. On notera que dans

Pour $a \in \mathcal{V}$, $\varphi_1, \varphi_2 \in \Delta\mathcal{L}\mathcal{P}$ et $\pi_1$ et $\pi_2$ des programmes de DL-PA tels que $\mathcal{M}(\varphi_1) = \mathcal{M}(\pi_1)$ et $\mathcal{M}(\varphi_2) = \mathcal{M}(\pi_2)$, on a le tableau suivant, dans lequel, pour chaque ligne, $\mathcal{M}(\varphi) = \mathcal{M}(\pi)$ :

<table><caption>TABLE 1 – Des correspondances entre formules de $(\Delta\mathcal{L}\mathcal{P}, \models)$ et programmes de DL-PA.</caption><thead><tr><th>&phi; &isin; &Delta;&mathcal{L}&mathcal{P}</th><th>&pi; : programme de DL-PA</th></tr></thead><tbody><tr><td>cp (a<sup>&bull;</sup><sub>1</sub>)</td><td>+a</td></tr><tr><td>cp (a<sup>&bull;</sup><sub>0</sub>)</td><td>-a</td></tr><tr><td>a<sup>=1</sup></td><td>a? ; +a ; désaff(V \ {a})</td></tr><tr><td>a<sup>=0</sup></td><td>&not; a? ; -a ; désaff(V \ {a})</td></tr><tr><td>a<sup>+</sup></td><td>&not; a? ; +a ; désaff(V \ {a})</td></tr><tr><td>a<sup>-</sup></td><td>a? ; -a ; désaff(V \ {a})</td></tr><tr><td>&phi;<sub>1</sub> &or; &phi;<sub>2</sub></td><td>&pi;<sub>1</sub> &cup; &pi;<sub>2</sub></td></tr><tr><td>&phi;<sub>1</sub> ; &phi;<sub>2</sub></td><td>&pi;<sub>1</sub> ; &pi;<sub>2</sub></td></tr></tbody></table>

cette table ne sont pas distingués les opérations sur les logiques des connecteurs de cette logique : par exemple, dans $\pi_1$ ; $\pi_2$, le ; appartient à la syntaxe de la logique alors que dans $\varphi_1$ ; $\varphi_2$, le ; est un opérateur. Par ailleurs, pour $\alpha \in \mathcal{L}\mathcal{P}$ (qui est donc un cas particulier de formule de DL-PA), on a $\mathcal{M}(\alpha?) = \mathcal{M}(\alpha)$ où $\alpha$ est défini dans [7] comme étant le plongement de $\alpha$ dans $(\Delta\mathcal{L}\mathcal{P}, \models)$ défini syntaxiquement en remplaçant toutes les occurrences de $a \in \mathcal{V}(\alpha)$ par $a^{=1}$. Enfin, pour $\alpha \in \mathcal{L}\mathcal{P}$, $\varphi \in \Delta\mathcal{L}\mathcal{P}$ et un programme $\pi$ de DL-PA tel que $\mathcal{M}(\varphi) = \mathcal{M}(\pi)$, on a $\mathcal{M}(\langle\pi\rangle\alpha) = \mathcal{G}(\varphi \wedge \alpha^{=1})$.

De façon générale, on peut traduire toute $\varphi \in \Delta\mathcal{L}\mathcal{P}$ en un programme $\pi$ de DL-PA de façon à ce que $\mathcal{M}(\varphi) = \mathcal{M}(\pi)$, comme nous le verrons ci-dessous, du moins sous l'hypothèse d'un ensemble fini de variables. Notons néanmoins que la traduction proposée n'est pas efficace et qu'il y a peu d'espoir d'en trouver une qui le soit puisque la satisfiabilité dans $(\Delta\mathcal{L}\mathcal{P}, \models)$ est NP-complète alors que la complexité de la satisfiabilité dans DL-PA est EXPTIME-difficile (même si cette complexité concerne les formules et pas les programmes, c'est une indication de la complexité relative aux inférences sur les programmes).

Une preuve simple du fait que $\varphi \in \Delta\mathcal{L}\mathcal{P}$ puisse se traduire en $\pi$ tient au fait que tout sous-ensemble de $\Delta\Omega$ est représentable par un programme $\pi$ (sous l'hypothèse d'un ensemble fini de variables). Une preuve plus constructive consiste à associer d'abord à chaque cube complet un programme de DL-PA. Soit $\psi$ un cube complet de $(\Delta\mathcal{L}\mathcal{P}, \models)$ : $\psi = \bigvee_{a \in \mathcal{V}} a^{\omega(a)}$ pour une $\omega \in \Delta\Omega_{\text{alt}}$. Pour $a \in \mathcal{V}$, soit le programme

$$ \pi_a = \left\{ \begin{array}{ll} a? ; +a & \text{si } \omega(a) = \mathbf{1} \\ \neg a? ; -a & \text{si } \omega(a) = \mathbf{0} \\ \neg a? ; +a & \text{si } \omega(a) = \mathbf{+} \\ a? ; -a & \text{si } \omega(a) = \mathbf{-} \end{array} \right. $$
Avec $V = \{a_1, a_2, \dots, a_n\}$ soit $\pi = \pi_{a_1} ; \pi_{a_2} ; \dots ; \pi_{a_n}$.
On peut montrer alors que $M(\pi) = M(\psi)$. De façon générale, toute $\varphi$ peut s'écrire comme une disjonction de cubes complets : $\varphi = \psi_1 \lor \psi_2 \lor \dots \lor \psi_p$. En associant à chaque cube $\psi_k$ un programme $\pi_k$ comme ci-dessus, on peut construire le programme $\pi = \pi_1 \cup \pi_2 \cup \dots \cup \pi_p$. On a alors $M(\pi) = \cup_{k=1}^p M(\pi_k) = \cup_{k=1}^p M(\psi_k) = M(\varphi)$.

Il y a donc des liens forts entre ($\Delta LP, \models$) et DL-PA qui doivent être étudiés davantage. Il semblerait que ($\Delta LP, \models$) soit davantage utile pour observer des variations (et c'est pour cela que cette logique a été définie initialement) alors que DL-PA qui, en quelque sorte, intègre naturellement le ceteris paribus soit appropriée pour agir avec ces variations (en considérant l'application d'une règle d'adaptation comme l'exécution d'un programme). Ainsi, raisonner avec des règles d'adaptation pourrait se faire avec ($\Delta LP, \models$) pour leur apprentissage et avec DL-PA (ou un de ses fragments) pour leur application.

## 6 Conclusion

Cet article a abordé l'usage de la logique des variations propositionnelles au raisonnement à partir de cas, en se penchant sur une première problématique : celle de la représentation des règles d'adaptation.

De nombreuses perspectives suivent cette étude, en particulier celles mentionnées dans [7] et pas traitées dans cet article et celles qui apparaissent dans ce présent article. Nous considérerons en particulier l'étude de l'extension de la logique des variations propositionnelles à d'autres logiques, en particulier, des logiques avec des variables de types entier ou réel. Cela suppose de définir un langage de symboles de variations qui sera nécessairement incomplet : une logique étant supposée s'appuyer sur un langage dénombrable (du moins, c'est une hypothèse que nous considérons) et l'ensemble des relations binaires sur $\mathbb{N}$ étant indénombrable... Une façon de conduire cette étude passe par les logiques dynamiques au-delà de DL-PA, en tentant de résoudre l'équation analogique « Une telle logique des variations serait à ($\Delta LP, \models$) ce qu'une logique dynamique serait à DL-PA. »

## Références

[1] Balbiani, Ph., A. Herzig et N. Troquard: *Dynamic logic of propositional assignments : a well-behaved variant of PDL*. Dans 28th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 143–152. IEEE, 2013.

[2] Carbonell, J. G.: *Learning by analogy : Formulating and generalizing plans from past experience*. Dans Michalski, R. S., J. G. Carbonell et T. M. Mitchell (rédacteurs) : *Machine Learning, An Artificial Intelligence* Approach, chapitre 5, pages 137–161. Morgan Kaufmann, Inc., 1983.

[3] Cordier, A., V. Dufour-Lussier, J. Lieber, E. Nauer, F. Badra, J. Cojan, E. Gaillard, L. Infante-Blanco, P. Molli, A. Napoli et H. Skaf-Molli: *Taaable : a Case-Based System for personalized Cooking*. Dans Montani, S. et L. C. Jain (rédacteurs) : *Successful Case-based Reasoning Applications-2*, tome 494 de *Studies in Computational Intelligence*, pages 121–162. Springer, 2014.

[4] d'Aquin, M., F. Badra, S. Lafrogne, J. Lieber, A. Napoli et L. Szathmary: *Case base mining for adaptation knowledge acquisition*. Dans Veloso, M. M. (rédacteur) : *Proc. of the 20th Int. Joint Conf. on Artificial Intelligence (IJCAI'07)*, pages 750–755. Morgan Kaufmann, Inc., 2007.

[5] d'Aquin, M., J. Lieber et A. Napoli: *Adaptation Knowledge Acquisition : a Case Study for Case-Based Decision Support in Oncology*. Computational Intelligence (an International Journal), 22(3/4) :161–176, 2006.

[6] Dupin de Saint-Cyr, F., A. Herzig, J. Lang et P. Marquis: *Raisonnement sur l'action et le changement*. Dans *Panorama de l'intelligence artificielle — ses bases méthodologiques, ses développements*, tome 1, chapitre 12, pages 363–392. Cépaduès, 2014.

[7] François, N., Th. Laure et J. Lieber: *Une logique pour représenter des variations propositionnelles*. Dans Bouraoui, Z., F. Schwarzentruber et A. Wilczynski (rédacteurs) : *Journées d'intelligence artificielle fondamentale – plateforme AFIA 2023*, page 11, Strasbourg, France, juillet 2023. Z. Bouraoui and F. Schwarzentruber and A. Wilczynski.

[8] François, N. et J. Lieber: *Appliquer la logique des variations propositionnelles à la représentation de règles d'adaptation pour le raisonnement à partir de cas (version étendue)*. rapport technique, Loria, 2024. (Ce rapport se trouve à l'adresse https://hal.science/hal-04497632).

[9] Hanney, K. et M. T. Keane: *Learning adaptation rules from a case-base*. Dans Smith, I. et B. Faltings (rédacteurs) : *Advances in Case-Based Reasoning – Proc. of the Third Eur. Workshop, EWCBR'96*, LNAI 1168, pages 179–192. Springer Verlag, Berlin, 1996.

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

[11] Richter, M. M. et R. O. Weber: *Case-based reasoning, a textbook*. Springer, 2013.

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