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

Nicolas François, Jean Lieber

## ► 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 (version étendue). LORIA (Université de Lorraine, CNRS, INRIA). 2024, pp.25. hal-04497632

HAL Id: hal-04497632

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

Submitted on 10 Mar 2024

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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 CC BY 4.0 - Attribution - International License
Appliquer la logique des variations propositionnelles à la
représentation de règles d'adaptation pour le raisonnement à
partir de cas (version étendue) *

Nicolas François
Jean Lieber

Lycée public Chopin, Nancy
Université de Lorraine, CNRS, Inria, LORIA, Nancy

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.

**Note préliminaire** : Ce document est une version étendue d'un article soumis aux JIAF-2024. La différence principale avec l'article est la présence des preuves. Certains résultats supplémentaires sont énoncés et prouvés. L'ordre de l'article a été conservé au mieux.

# 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, [5]). Ces notations ont été dotées d'une sémantique pour obtenir une logique, qui a été étudiée, pour elle-même, dans [8].

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 notions 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 [8]) 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. Deux approches générales de l'adaptation se côtoient dans le domaine du RàPC : l'adaptation transformationnelle et l'adaptation générative. La section 4 étudie comment les logiques de variations peuvent être utilisées pour représenter

<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 ce rapport. Ils veulent également exprimer leur gratitude envers Pierre Marquis pour ses conseils judicieux. Que leurs chemins soient pavés de fleurs de cerisiers.</footnote>
des connaissances d'adaptation dans le cadre de l'adaptation transformationnelle (l'étude de ces logiques pour l'adaptation générative est une perspective de recherche). La section 5 présente une discussion en lien avec d'autres travaux.

# 2 Préliminaires

Ces préliminaires sont en deux parties : l'une concerne la logique $(\Delta\mathcal{L}P, \models)$, l'autre, le RàPC.

## 2.1 La logique des variations propositionnelles

Cette section reprend les points principaux sur la logique des variations propositionnelles $(\Delta\mathcal{L}P, \models)$ introduite et décrite dans [8].

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

On se donne un ensemble fini de symboles $\mathcal{V}$ : un élément de $\mathcal{V}$ est appelé *variable propositionnelle* (ou simplement *variable*). Une formule de $(\mathcal{L}P, \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 \mathcal{L}P$) :

$$ \supset \underline{euad} a \vee \neg a \quad \bot \underline{euad} a \wedge \neg a \quad \beta_1 \to \beta_2 \underline{euad} \neg \beta_1 \vee \beta_2 $$

Un littéral de $(\mathcal{L}P, \models)$ est une formule de la forme $a$ ou de la forme $\neg a$ ($a \in \mathcal{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 \mathcal{L}P$ est noté $\mathcal{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 $\mathcal{I} : \mathcal{V} \to \{0, 1\}$ où $\{0, 1\}$ est l'ensemble des booléens. On note $\Omega$ l'ensemble des interprétations. Soit $\mathcal{I} \in \Omega$ et $\alpha \in \mathcal{L}P$. On définit la relation « $\mathcal{I}$ satisfait $\alpha$ » ($\mathcal{I} \models \alpha$) en définissant récursivement $\alpha^I \in \{0, 1\}$ de la façon suivante (avec non, et et ou les opérateurs classiques sur les booléens) :

$$ \alpha^I = \begin{cases} \mathcal{I}(\alpha) & \text{si } \alpha \in \mathcal{V} \\ \text{non } \beta & \text{si } \alpha = \neg \beta \\ \beta_1^I \text{ et } \beta_2^I & \text{si } \alpha = \beta_1 \wedge \beta_2 \\ \beta_1^I \text{ ou } \beta_2^I & \text{si } \alpha = \beta_1 \vee \beta_2 \end{cases} $$

On définit alors $\mathcal{I} \models \alpha$ si $\alpha^I = 1$ (et $\mathcal{I} \not\models \alpha$ sinon), et on dit que $\mathcal{I}$ est un modèle de $\alpha$.

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 \mathcal{L}P$, $\alpha \equiv \beta$ si $M(\alpha) = M(\beta)$.

**La syntaxe de la logique** $(\Delta\mathcal{L}P, \models)$ diffère légèrement de celle qui était donnée dans [8], au sens où certains constructeurs dans cet article sont ici des abréviations et inversement. Une formule $\varphi \in \Delta\mathcal{L}P$ 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 \mathcal{L}P$ et $\psi, \psi_1, \psi_2 \in \Delta\mathcal{L}P$.
On utilisera les abréviations suivantes :

$$
\begin{align*}
\top_{\Delta} \underline{euad} \quad & \top \triangleright \top \\
\alpha^{=1} \underline{euad} \quad & \alpha \triangleright \alpha \\
\alpha^{+} \underline{euad} \quad & \neg\alpha \triangleright \alpha \\
\alpha^{=} \underline{euad} \quad & \alpha^{=1} \vee \alpha^{=0} \\
\alpha^{0\bullet} \underline{euad} \quad & \alpha^{=0} \vee \alpha^{+} \\
\alpha^{\bullet 0} \underline{euad} \quad & \alpha^{=0} \vee \alpha^{-}
\end{align*}
\qquad
\begin{align*}
\bot_{\Delta} \underline{euad} \quad & \bot \triangleright \bot \\
\alpha^{=0} \underline{euad} \quad & \neg\alpha \triangleright \neg\alpha \\
\alpha^{-} \underline{euad} \quad & \alpha \triangleright \neg\alpha \\
\alpha^{\ne} \underline{euad} \quad & \alpha^{+} \vee \alpha^{-} \\
\alpha^{1\bullet} \underline{euad} \quad & \alpha^{=1} \vee \alpha^{-} \\
\alpha^{\bullet 1} \underline{euad} \quad & \alpha^{=1} \vee \alpha^{+}
\end{align*}
\qquad
\begin{align*}
\psi_1 \to \psi_2 \quad & \underline{euad} \neg\psi_1 \vee \psi_2 \\
\psi_1 \to \psi_2 \quad & \neg\psi_1 \vee \psi_2
\end{align*}
$$

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

Un littéral 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 $(\mathcal{I}, \mathcal{J})$ de $\Delta\Omega$ est appelé interprétation (pour cette logique) et sera noté simplement $\mathcal{IJ}$. Pour $\varphi \in \Delta LP$, la définition de $\mathcal{IJ} \models \varphi$ est définie comme suit :

$$ \neg\mathcal{I}\mathcal{J} \models \alpha \triangleright \beta \text{ si } \mathcal{I} \models \alpha \text{ et } \mathcal{J} \models \beta. $$

$$ \neg\mathcal{I}\mathcal{J} \models \neg\psi \text{ si } \mathcal{I}\mathcal{J} \not\models \psi. $$

$$ \mathcal{I}\mathcal{J} \models \psi_1 \wedge \psi_2 \text{ si } \mathcal{I}\mathcal{J} \models \psi_1 \text{ et } \mathcal{I}\mathcal{J} \models \psi_2. $$

$$ \mathcal{I}\mathcal{J} \models \psi_1 \vee \psi_2 \text{ si } \mathcal{I}\mathcal{J} \models \psi_1 \text{ ou } \mathcal{I}\mathcal{J} \models \psi_2. $$

On définit alors $M(\varphi) = \{\mathcal{I}\mathcal{J} \in \Delta\Omega \mid \mathcal{I}\mathcal{J} \models \varphi\}$. On note en particulier que $M(\alpha \triangleright \beta) = M(\alpha) \times M(\beta)$. On définit les notions de satisfiability, 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)) = \{\mathcal{I} \mid \mathcal{I}\mathcal{J} \in M(\varphi)\} $$

$$ M(D(\varphi)) = \{\mathcal{J} \mid \mathcal{I}\mathcal{J} \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 certains résultats de [8] :

- Tout sous-ensemble $A$ de $\Delta\Omega$ est représentable dans la logique : il existe $\varphi \in \Delta LP$ 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 V$ et $v \in D_0$. Par exemple :

$$ a \wedge b \triangleright \neg a \wedge c \quad \equiv \quad a^{-} \wedge (b^{=1} \vee b^{-}) \wedge (c^{=1} \vee c^{+}) $$
— En particulier, on peut écrire toute formule de $(\Delta\mathcal{L}P, \models)$ 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}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) \quad \equiv \quad \bigwedge_{a \in \mathcal{V}} \ell(a) \triangleright m(a) \qquad (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}P, \models)$.

— 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}P$) :

$$ \mathcal{D}(\varphi \vee \psi) \equiv \mathcal{D}(\varphi) \vee \mathcal{D}(\psi) \qquad (2) $$

— Pour $\varphi \in \Delta\mathcal{L}P$, on peut définir facilement $\varphi^{-1} \in \Delta\mathcal{L}P$ telle que $\mathcal{I}\mathcal{J} \models \varphi^{-1}$ ssi $\mathcal{J}\mathcal{I} \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’appuyant 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 $x$ est appelé **problème**, un élément de $y$, **solution** et $x \rightsquigarrow y$ se lit « $x$ a pour solution $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^{\text{cible}}$ à un problème donné, le problème cible, noté $x^{\text{cible}}$.

On considère souvent (et cela sera le cas dans cet article) qu’un cas est donné par un couple $(x, y) \in \mathcal{P} \times \mathcal{S}$ où $x \rightsquigarrow y$: la relation $\rightsquigarrow$ est connue pour un ensemble fini qui constitue la base de cas. On note $(x^s, y^s)$ un élément de la base de cas et on l’appelle cas source ($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 $x^{\text{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 $((x^s, y^s), x^{\text{cible}})$.

Deux façons de considérer l’adaptation existent, inspirées de la différence entre analogie transformationnelle et analogie dérivationnelle, notions introduites par J. G. Carbonell (voir [2] et [3]):

**L'adaptation transformationnelle** vise à résoudre le problème d'adaptation en le lisant sous la forme « La solution cherchée, $y^{\text{cible}}$, est à $y^s$ ce que $x^{\text{cible}}$ est à $x^s$. » On peut l'interpréter ainsi : des variations entre les problèmes $x^s$ et $x^{\text{cible}}$, notées $\Delta x$, on infère des variations entre la solution $y^s$ et l'inconnue $y^{\text{cible}}$, notée $\Delta y$, puis, on infère $y^{\text{cible}}$ à partir de $y^s$ et $\Delta y$.

**L'adaptation générative** vise à résoudre le problème d'adaptation en le lisant sous la forme « La solution cherchée, $y^{\text{cible}}$, est à $x^{\text{cible}}$ ce que $y^s$ est à $x^s$. ». Elle s'appuie sur l'analyse du lien entre $x^s$ et $y^s$ puis à tenter de « rejouer » ce lien sur $x^{\text{cible}}$.

Cet article se concentre sur l'adaptation transformationnelle : l'étude de l'application de $(\Delta\mathcal{L}P, \models)$ à l'adaptation générative constitue une perspective.
**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ée 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 $|\equiv_{CD}$ plutôt que simplement $|=|$).

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

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 $(x^s, y^s)$ et un problème cible $x^{cible}$, les problèmes $x^s$ et $x^{cible}$ peuvent s'écrire sous la forme $\bigwedge_{a \in V_P} \ell(a)$ et la solution $y^s$ sous la forme $\bigwedge_{a \in V_S} \ell(a)$, où $\ell(a) \in \{a, \neg a\}$. La formule $x^s \wedge y^s$ est alors un cube complet et donc $|M(x^s \wedge 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. [6]). 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 $(x^i, y^i)$ et $(x^j, y^j)$, on construit les variations $\Delta x^{ij}$ de $x^i$ à $x^j$ et $\Delta y^{ij}$ de $y^i$ à $y^j$. L'apprentissage de connaissances d'adaptation utilise un ensemble de couples $(\Delta x^{ij}, \Delta y^{ij})$ et permet de construire un modèle d'une fonction $\Delta x \mapsto \Delta y$, qui permet, à partir d'une variation entre problèmes d'obtenir une variation entre solutions, 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 [5]. 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 x^{ij}$ et des $\Delta 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{LP}, |=$).

Plus précisément, si les cas sources sont supposés spécifiques, d'après le résultat (1), on peut écrire $\Delta x^{ij}$ et $\Delta y^{ij}$ sous les formes $\bigwedge_{a \in V_P} a^v(a)$ et $\bigwedge_{a \in V_S} a^v(a)$, où $v(a) \in 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{LP}, |=$)

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

<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 $x^{cible}$ et le cas source $c^s$, on détermine $V_P$ et $V_S$ pour décomposer $c^s$ en $x^s \wedge y^s$.</footnote>
## 3.1 Résultats généraux

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

$$ \text{si } \mathcal{I}_1\mathcal{J}_1, \mathcal{I}_2\mathcal{J}_2 \in \Delta\Omega \text{ vérifient } \mathcal{I}_1(x) = \mathcal{I}_2(x) \text{ et } \mathcal{J}_1(x) = \mathcal{J}_2(x) \text{ pour tout } x \in \mathcal{V}(\varphi) \quad (3) $$

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

pour $\varphi \in \Delta LP$. La preuve de ce résultat se fait par induction structurelle.

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

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

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

$$ \text{et } \mathbf{D}(\varphi \wedge \psi) \equiv \mathbf{D}(\varphi) \wedge \mathbf{D}(\psi) \quad (5) $$

**Preuve.** La preuve ne sera faite que pour l'opérateur $\mathbf{D}$ (elle se transpose immédiatement pour l'opérateur $\mathbf{G}$). Soit $\mathcal{J} \in \mathcal{M}(\mathcal{D}(\varphi \wedge \psi))$. Il existe donc $\mathcal{I} \in \Omega$ telle que $\mathcal{IJ} \models \varphi \wedge \psi$. Donc, il existe $\mathcal{I} \in \Omega$ telle que $\mathcal{IJ} \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 (4), $\mathcal{I}_1\mathcal{J} \models \varphi$ entraîne $\mathcal{IJ} \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{IJ} \models \psi$. Donc, $\mathcal{IJ} \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 LP$ par :

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

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) = =1$, $\omega_2(a) = =0$ et $\omega_1(b) = \omega_2(b) = +$. 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 LP, \models)$ et toute $\varphi \in \Delta LP$, $\mathcal{B} \models_{\text{alt}} \varphi \text{ ssi } \mathcal{B} \models \varphi$.
**Preuve.** À $\mathcal{IJ} \in \Delta\Omega$, on associe $\omega_{\mathcal{IJ}} \in \Delta\Omega_{\text{alt}}$ de la façon suivante, pour $a \in \mathcal{V}$

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

La fonction $\mathcal{IJ} \in \Delta\Omega \mapsto \omega_{\mathcal{IJ}} \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{IJ} \in \Delta\Omega$ définie ainsi, pour $a \in \mathcal{V}$ :

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

(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{IJ}$ comme ci-dessus, on a $\omega_{\mathcal{IJ}} = \omega$).

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

Enfin, pour une base de connaissances $\mathcal{B}$ et $\varphi \in \Delta\mathcal{LP}$, on montre que $\mathcal{B} \models \varphi \text{ 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{LP}$, 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)$ n'influe pas sur la satisfaction de $\varphi$ 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{LP}$, l'ensemble des variables invariantes de $\varphi$ est

$$ \text{Inv}(\varphi) = \{ 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} \} $$

Par exemple,

$$ \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\} \quad (6) $$

Cette notion est indépendante de la syntaxe : si $\varphi \equiv \psi$ alors $\text{Inv}(\varphi) \equiv \text{Inv}(\psi)$. On montre, en s'appuyant sur (4) 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} \quad (7) $$

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

La proposition suivante montre qu'une transformation de formule permet de lier les non-occurrences de variables à $\text{Inv}(\varphi)$.

**Proposition 2.** Pour toute $\varphi \in \Delta\mathcal{LP}$, il existe $\varphi' \in \Delta\mathcal{LP}$ telle que $\varphi \equiv \varphi'$ et $\text{Inv}(\varphi) = \mathcal{V} \setminus \mathcal{V}(\varphi')$.
**Preuve.** On considère d'abord le cas où $\mathrm{Inv}(\varphi) = \emptyset$. Dans ce cas, le résultat est vérifié avec $\varphi' = \varphi$ : c'est une conséquence immédiate de (7).

On considère ensuite le cas où $\mathrm{Inv}(\varphi) = \{a_1\}$. On peut mettre $\varphi$ sous la forme d'une disjonction de cubes complets : $\varphi \equiv \varphi_0$ avec

$$ \varphi_0 = \bigvee_{\omega \in \mathcal{M}_{\mathrm{alt}}(\varphi)} \varphi_{\omega} \quad \text{où} \quad \varphi_{\omega} = \bigwedge_{x \in \mathcal{V}} x^{\omega(x)} $$

Soit $\omega \in \mathcal{M}_{\mathrm{alt}}(\varphi)$. Par définition d'Inv($\varphi$), on a donc $\omega[a_1^v] \in \mathcal{M}_{\mathrm{alt}}(\varphi)$, pour tout $v \in \mathcal{D}_0$. Par conséquent, dès qu'on a un $\varphi_\omega$ dans la disjonction $\varphi_0$, on a tous les $\varphi_{\omega[a_1^v]}$ pour $v \in \mathcal{D}_0$. Donc, en répétant et regroupant les éléments dans la disjonction (ce qui n'est pas un problème puisque $\vee$ est associatif modulo l'équivalence et que $\psi \equiv \psi \vee \psi$ pour toute formule $\psi$), on obtient :

$$
\begin{align*}
\varphi_0 &\equiv \bigvee_{\omega \in \mathcal{M}_{\mathrm{alt}}(\varphi)} \bigvee_{v \in \mathcal{D}_0} \bigwedge_{x \in \mathcal{V}} x^{\omega[a_1^v]}(x) \\
&\equiv \bigvee_{\omega \in \mathcal{M}_{\mathrm{alt}}(\varphi)} \bigvee_{v \in \mathcal{D}_0} \left[ a_1^{\omega[a_1^v](a_1)} \wedge \bigwedge_{x \in \mathcal{V} \setminus \{a_1\}} x^{\omega[a_1^v]}(x) \right] \\
&\equiv \bigvee_{\omega \in \mathcal{M}_{\mathrm{alt}}(\varphi)} \bigvee_{v \in \mathcal{D}_0} \left[ a_1^v \wedge \bigwedge_{x \in \mathcal{V} \setminus \{a_1\}} x^{\omega(x)} \right] \\
&\equiv \bigvee_{\omega \in \mathcal{M}_{\mathrm{alt}}(\varphi)} \left[ \bigwedge_{x \in \mathcal{V} \setminus \{a_1\}} x^{\omega(x)} \right] \wedge \bigvee_{v \in \mathcal{D}_0} a_1^v \\
&\equiv \bigvee_{\omega \in \mathcal{M}_{\mathrm{alt}}(\varphi)} \left[ \bigwedge_{x \in \mathcal{V} \setminus \{a_1\}} x^{\omega(x)} \right] \text{ puisque } \bigvee_{v \in \mathcal{D}_0} a_1^v \equiv \top
\end{align*}
$$

Appelons $\varphi_1$ la dernière formule de la séquence d'équivalences ci-dessus. Puisque $a_1 \notin \mathcal{V}(\varphi_1)$ et que $\varphi_1 \equiv \varphi$, la proposition est prouvée avec $\varphi' = \varphi_1$.

Dans le cas où $\mathrm{Inv}(\varphi) = \{a_1, a_2, \dots, a_p\}$, on peut reprendre le processus ci-dessus pour obtenir $\varphi_1$ puis, le répéter avec l'ensemble de variables $\mathcal{V} \setminus \{a_1\}$ sur $\varphi_1$ pour obtenir $\varphi_2$, formule équivalente à $\varphi$ sans occurrence ni d'a_1, ni d'a_2. On continue ainsi, pour aboutir à une formule $\varphi_p$ équivalente à $\varphi$ mais n'ayant aucune occurrence dans $\mathrm{Inv}(\varphi)$. Avec $\varphi' = \varphi_p$, on conclut ainsi la preuve de la proposition. ■

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

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

**Preuve.** Comme $\mathrm{Inv}(\varphi) \supseteq \mathcal{V} \setminus \mathcal{V}(\varphi)$ (cf. (7)), il suffit de montrer que si $a \in \mathrm{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 = \neq$ alors on peut choisir $v_0 = \bullet$ ou $v_0 = -$). Soit $w \in \mathcal{D}_0 \setminus \{v_0\}$. On a donc $\varphi[a^{v_0}] \models a^{v_0}$ et $\varphi[a^w] \nvDash 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}] \nvDash \varphi[a^w]$ et donc $a \notin \mathrm{Inv}(\varphi)$. ■

## 3.4 Opérateur ceteris paribus

Considérons la formule $a^+$ : elle indique que $a$ « passe » de 0 à 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 0 à 1, le reste des variables
restant *inchangées*. On va exprimer cela par une formule $\mathbf{cp}(a^+)$ qui, sur l'exemple avec deux variables, donnera $\mathcal{M}(\mathbf{cp}(a^+)) = \{(\bar{a}\bar{b}, a\bar{b}), (\bar{a}b, ab)\}$ : dans les modèles de ces formules, $b$ reste à 0 ou reste à 1 ($\mathbf{cp}$ pour ceteris paribus), en d'autres termes, $\mathbf{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 $\mathbf{cp}$ tel que, pour $\varphi, \psi \in \Delta\mathcal{LP}$, on ait

$$ \mathbf{cp}(\varphi) \models \varphi \qquad (8) $$

$$ \text{pour toute } x \in \text{Inv}(\varphi), \mathbf{cp}(\varphi) \models x^= \qquad (9) $$

$$ \text{si } \varphi \equiv \psi \text{ alors } \mathbf{cp}(\varphi) \equiv \mathbf{cp}(\psi) \qquad (10) $$

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

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

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

$$ \mathbf{cp}(\varphi) = \varphi \wedge \bigwedge \{x^= | x \in \text{Inv}(\varphi)\} $$

**Proposition 4.** $\mathbf{cp}$ vérifie (8), (9), (10) et (11).

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

Pour (11), 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_{\text{alt}}$ telle que $\omega \models_{\text{alt}} \varphi$. Soit $a_1, a_2, \dots, a_p$ telles que $\text{Inv}(\varphi) = \{a_1, a_2, \dots, a_p\}$. Soit $\omega' = \omega[a_1^{=1}] [a_2^{=1}] \dots [a_p^{=1}]$. On a, par définition de $\text{Inv}(\varphi)$, $\omega' \models_{\text{alt}} \varphi$. Par ailleurs, $\omega' \models_{\text{alt}} a_k^{=1}$ pour tout $k \in \{1, 2, \dots, p\}$ et donc $\omega' \models_{\text{alt}} \bigwedge\{x^{=1} | x \in \text{Inv}(\varphi)\}$. Or, pour toute variable $a$, $a^{=1} \models a^=$. Par conséquent, $\omega' \models_{\text{alt}} \bigwedge\{x^= | x \in \text{Inv}(\varphi)\}$. Donc, $\omega' \models_{\text{alt}} \mathbf{cp}(\varphi)$ et donc, $\mathbf{cp}(\varphi)$ est satisfiable. ■

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

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

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

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

Un problème pratique se pose avec cet opérateur : pour $\varphi \in \Delta\mathcal{LP}$, $|\mathbf{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 $\mathbf{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 $\mathbf{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 $W \subseteq V$ et $\varphi \in \Delta\mathcal{LP}$. Le ceteris paribus de $\varphi$ restreint à l'ensemble de variables $W$ est :

$$ \mathbf{cp}_W(\varphi) = \varphi \wedge \bigwedge \{x^= | x \in \text{Inv}(\varphi) \cap W\} $$

Et on a, évidemment, $\mathbf{cp}_V(\varphi) = \mathbf{cp}(\varphi)$.

## 3.5 Composition des variations

La composition de variations a été introduite dans [8] mais peu étudiée. On note tout d'abord qu'une formule $\varphi \in \Delta\mathcal{LP}$ représentant 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 compose et la composition des formules de variations correspond à la composition entre relations binaires.

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

$$ \mathcal{M}(\varphi; \psi) = \left\{ \mathcal{IK} \in \Delta\Omega \mid \begin{array}{l} \text{il existe } \mathcal{J} \in \Omega \text{ telle que} \\ \mathcal{IJ} \models \varphi \text{ et } \mathcal{JK} \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 LP, (\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 5.** Soit $\alpha, \beta, \gamma, \delta \in LP$. On a :

$$ (\alpha \triangleright \beta); (\gamma \triangleright \delta) \equiv \begin{cases} \perp & \text{si } \beta \wedge \gamma \models \perp \\ \alpha \triangleright \delta & \text{sinon} \end{cases} $$

**Preuve.** Si $\beta \wedge \gamma \models \perp$ alors, pour aucun $\mathcal{IK} \in \Delta\Omega$ il n'existe de $\mathcal{J} \in \Omega$ tel que $\mathcal{IJ} \models \alpha \triangleright \beta$ (i.e. $\mathcal{I} \models \alpha$ et $\mathcal{J} \models \beta$) et $\mathcal{JK} \models \gamma \triangleright \delta$ (i.e. $\mathcal{J} \models \gamma$ et $\mathcal{K} \models \beta$), car sinon, un tel $\mathcal{J}$ serait modèle de $\beta \wedge \gamma$. Donc, $(\alpha \triangleright \beta)$ ; $(\gamma \triangleright \delta)$ est insatisfiable dans ce cas.

Supposons à présent que $\beta \wedge \gamma \nvDash \perp$ et soit $\mathcal{J}_0 \in \mathcal{M}(\beta \wedge \gamma)$. On a les équivalences suivantes, pour $\mathcal{IK} \in \Delta\Omega$ :

$$ \mathcal{IK} \models (\alpha \triangleright \beta); (\gamma \triangleright \delta) $$

ssi il existe $\mathcal{J} \in \Omega$ tq $\mathcal{IJ} \models \alpha \triangleright \beta$ et $\mathcal{JK} \models \gamma \triangleright \delta$

ssi il existe $\mathcal{J} \in \Omega$ tq $\mathcal{I} \models \alpha, \mathcal{J} \models \beta, \mathcal{J} \models \gamma, \mathcal{K} \models \delta$

ssi $\mathcal{I} \models \alpha, \mathcal{K} \models \delta$, il existe $\mathcal{J} \in \Omega$ tq $\mathcal{J} \models \beta \wedge \gamma$

vrai : il suffit de prendre $\mathcal{J} = \mathcal{J}_0$

$$ \text{ssi } \mathcal{IK} \models \alpha \triangleright \delta $$

On a donc bien $(\alpha \triangleright \beta)$ ; $(\gamma \triangleright \delta) \equiv \alpha \triangleright \delta$. ■

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

**Proposition 6.** Soit $\varphi, \varphi_1, \varphi_2, \psi, \psi_1, \psi_2 \in \Delta LP$. On a les équivalences suivantes :

$$ \varphi; (\psi_1 \lor \psi_2) \equiv (\varphi; \psi_1) \lor (\varphi; \psi_2) \quad (13) $$

$$ (\varphi_1 \lor \varphi_2); \psi \equiv (\varphi_1; \psi) \lor (\varphi_2; \psi) \quad (14) $$

**Preuve.** Les équivalences suivantes permettent de prouver (13) (avec $\mathcal{IK} \in \Delta\Omega$) :

$$ \mathcal{IK} \models \varphi; (\psi_1 \lor \psi_2) $$

ssi il existe $\mathcal{J} \in \Omega$ telle que $\mathcal{IJ} \models \varphi$ et $(\mathcal{JK} \models \psi_1 \text{ ou } \mathcal{JK} \models \psi_2)$

ssi il existe $\mathcal{J} \in \Omega$ telle que $(\mathcal{IJ} \models \varphi \text{ et } \mathcal{JK} \models \psi_1)$ ou $(\mathcal{IJ} \models \varphi \text{ et } \mathcal{JK} \models \psi_2)$

ssi $\mathcal{I} \models \text{il existe } \mathcal{J} \in \Omega \text{ telle que } (\mathcal{IJ} \models \varphi \text{ et } \mathcal{JK} \models \psi_1) \text{ ou}$

ssi $\mathcal{IK} \models \varphi; \psi_1 \text{ ou } \mathcal{IK} \models \varphi; \psi_2$

ssi $\mathcal{IK} \models (\varphi; \psi_1) \lor (\varphi; \psi_2)$

L'équivalence (14) se montre de façon similaire. ■
**Définition 4.** On introduit deux symboles de variations supplémentaires $⊥_D$ et $⊤_D$ tels que, pour tout $α ∈ ŁP$, $α^{⊥_D} = ⊥⊲ ⊥ = ⊥_Δ$ et $α^{⊤_D} = ⊤⊲ ⊤ = ⊤_Δ$.

À un cube $\varphi$ de $(\Delta ŁP, |)$ on associe $\text{var}(x, \varphi) ∈ D \cup \{\top_D\}$ de la façon suivante :

$$ \text{var}(x, \varphi) = \begin{cases} \top_D & \text{si } x \notin V(\varphi) \\ v & \text{si } x^v \text{ est un des termes de } \varphi \end{cases} $$

La proposition suivante permet de calculer la composition de deux atomes de $(\Delta ŁP, |)$ construits sur la même variable.

**Proposition 7.** *Il existe une opération binaire ; sur $D \cup \{⊥_D, ⊤_D\}$ telle que pour une variable $a$, on a $a^v$ ; $a^w = a^{v;w}$.*

**Preuve.** Dans cette preuve, on considérera tous les symboles de variation : ceux de $D \cup \{⊥_D, ⊤_D\}$ mais aussi ceux notés $¬v$ pour $v \in D_0$ et définis par $a^{-v} = \neg a^v$. On a donc $2^{|D_0|} = 16$ symboles de variations.

On rappelle d'abord le résultat suivant relatif à la représentation des graphes par des matrices. Soit $S = \{s_0, s_1, \dots, s_{m-1}\}$ un ensemble fini (dont on a numéroté les éléments). Un graphe $G$ sur $S$ est un couple $G = (S, R)$ où $R \subseteq S \times S$ est une relation binaire sur $S$. $S$ et la numérotation de ses sommets étant fixés, à $R$ on peut associer de façon bijective une matrice $M^R$ telle que, pour $i, j \in \{0, 1, \dots, m-1\}$, $A_{ij}^R = \begin{cases} 1 & \text{si } (s_i, s_j) \in R \\ 0 & \text{sinon} \end{cases}$. Étant donné deux matrices carrées $m \times m$ de booléens, on définit leur somme et leur produit de façon usuelle en utilisant le ou sur les booléens comme addition et le et sur les booléens comme multiplication. Étant donné $R_1$ et $R_2$, on a le résultat suivant :

$$ M^{R_1} \times M^{R_2} = M^{R_2 \circ R_1} \qquad (15) $$

où $R_2 \circ R_1$ est la composition de $R_1$ et de $R_2$.

À chaque symbole de variation $v$ on associe de façon bijective $R^v$, une relation sur $\{0, 1\}$ définie, avec $a$ une variable arbitraire et $\mathcal{I}\mathcal{J} \in \Delta\Omega$, $\mathcal{I}(a) R^v \mathcal{J}(a)$ ssi $\mathcal{I}\mathcal{J} \models a^v$. Comme cette association $v \mapsto R^v$ est bijective, cela permet de définir l'opérateur ; entre symboles de variation de la façon suivante :

$$ R^w \circ R^v = R^{v;w} \qquad (16) $$

Par ailleurs, pour $\mathcal{I}\mathcal{K} \in \Delta\Omega$ et $a \in V$, on a les équivalences suivantes :

$$ \begin{array}{l} \mathcal{I}\mathcal{K} \models a^v ; a^w \text{ssi il existe } \mathcal{J} \in \Omega \text{ tq } \left\{ \begin{array}{l} \mathcal{I}\mathcal{J} \models a^v \\ \mathcal{J}\mathcal{K} \models a^w \end{array} \right. \\ \\ \text{ssi il existe } \mathcal{J} \in \Omega \text{ tq } \left\{ \begin{array}{l} \mathcal{I}(a) R^v \mathcal{J}(a) \\ \mathcal{J}(a) R^w \mathcal{K}(a) \end{array} \right. \\ \\ \text{ssi } \mathcal{I}(a) R^w \circ R^v \mathcal{J}(a) \\ \\ \text{ssi } \mathcal{I}(a) R^{v;w} \mathcal{J}(a) \end{array} $$

Par conséquent, $\mathcal{I}\mathcal{K} \models a^v ; a^w$ ssi $\mathcal{I}\mathcal{K} \models a^{v;w}$ et donc :

$$ a^v ; a^w \equiv a^{v;w} $$

( faisant le lien entre l'opération ; sur les symboles de variation et l'opération ; sur $\Delta ŁP$).

Pour finir la preuve de la proposition, il reste à prouver que, pour $v, w \in D \cup \{⊥_D, ⊤_D\}$, $v$ ; $w \in D \cup \{⊥_D, ⊤_D\}$. Par ailleurs, pour des raisons de calcul, il est utile de connaître cette composition de symboles de variation. Par conséquent, la suite de la preuve va permettre de définir explicitement la valeur $v$ ; $w$ : le résultat se trouve à la table 1. Il suffira de vérifier que l'opération ; restreinte à $D \cup \{⊥_D, ⊤_D\}$ est interne.
<table><caption>TABLE 1 – Composition des variations pour le calcul de la composition des cubes. La case à la ligne v et à la colonne w contient la valeur v ; w.</caption><thead><tr><th></th><th>⊥<sub>D</sub></th><th>=0</th><th>+</th><th>-</th><th>=1</th><th>0•</th><th>•0</th><th>1•</th><th>•1</th><th>=</th><th>≠</th><th>¬=0</th><th>¬+</th><th>¬-</th><th>¬=1</th><th>⊤<sub>D</sub></th></tr></thead><tbody><tr><th>⊥<sub>D</sub></th><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td></tr><tr><th>=0</th><td>⊥<sub>D</sub></td><td>=0</td><td>+</td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>0•</td><td>=0</td><td>⊥<sub>D</sub></td><td>+</td><td>=0</td><td>+</td><td>+</td><td>=0</td><td>0•</td><td>0•</td><td>0•</td></tr><tr><th>+</th><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>=0</td><td>+</td><td>⊥<sub>D</sub></td><td>=0</td><td>0•</td><td>+</td><td>+</td><td>=0</td><td>0•</td><td>0•</td><td>+</td><td>=0</td><td>0•</td></tr><tr><th>-</th><td>⊥<sub>D</sub></td><td>-</td><td>=1</td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>1•</td><td>-</td><td>⊥<sub>D</sub></td><td>=1</td><td>-</td><td>=1</td><td>=1</td><td>-</td><td>1•</td><td>1•</td><td>1•</td></tr><tr><th>=1</th><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>-</td><td>=1</td><td>⊥<sub>D</sub></td><td>-</td><td>1•</td><td>=1</td><td>=1</td><td>-</td><td>1•</td><td>1•</td><td>=1</td><td>-</td><td>1•</td></tr><tr><th>0•</th><td>⊥<sub>D</sub></td><td>=0</td><td>+</td><td>=0</td><td>+</td><td>0•</td><td>=0</td><td>0•</td><td>+</td><td>0•</td><td>0•</td><td>0•</td><td>0•</td><td>0•</td><td>0•</td><td>0•</td></tr><tr><th>•0</th><td>⊥<sub>D</sub></td><td>•0</td><td>•1</td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊤<sub>D</sub></td><td>•0</td><td>⊥<sub>D</sub></td><td>•1</td><td>•0</td><td>•1</td><td>•1</td><td>•0</td><td>⊤<sub>D</sub></td><td>⊤<sub>D</sub></td><td>⊤<sub>D</sub></td></tr><tr><th>1•</th><td>⊥<sub>D</sub></td><td>-</td><td>=1</td><td>-</td><td>=1</td><td>1•</td><td>-</td><td>1•</td><td>=1</td><td>1•</td><td>1•</td><td>1•</td><td>1•</td><td>1•</td><td>1•</td><td>1•</td></tr><tr><th>•1</th><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>⊥<sub>D</sub></td><td>•0</td><td>•1</td><td>⊥<sub>D</sub></td><td>•0</td><td>⊤<sub>D</sub></td><td>•1</td><td>•1</td><td>•0</td><td>⊤<sub>D</sub></td><td>•1</td><td>•0</td><td>⊤<sub>D</sub></td><td>⊤<sub>D</sub></td></tr><tr><th>=</th><td>⊥<sub>D</sub></td><td>=0</td><td>+</td><td>-</td><td>=1</td><td>0•</td><td>•0</td><td>1•</td><td>•1</td><td>=</td><td>≠</td><td>¬=0</td><td>¬+</td><td>¬-</td><td>¬=1</td><td>⊤<sub>D</sub></td></tr><tr><th>≠</th><td>⊥<sub>D</sub></td><td>-</td><td>=1</td><td>=0</td><td>+</td><td>1•</td><td>•0</td><td>0•</td><td>•1</td><td>≠</td><td>=</td><td>¬-</td><td>¬=1</td><td>¬=0</td><td>¬+</td><td>⊤<sub>D</sub></td></tr><tr><th>¬=0</th><td>⊥<sub>D</sub></td><td>-</td><td>=1</td><td>•0</td><td>•1</td><td>1•</td><td>•0</td><td>⊤<sub>D</sub></td><td>•1</td><td>¬=0</td><td>¬+</td><td>⊤<sub>D</sub></td><td>⊤<sub>D</sub></td><td>¬=0</td><td>¬+</td><td>⊤<sub>D</sub></td></tr><tr><th>¬+</th><td>⊥<sub>D</sub></td><td>•0</td><td>•1</td><td>-</td><td>=1</td><td>⊤<sub>D</sub></td><td>•0</td><td>1•</td><td>•1</td><td>¬+</td><td>¬=0</td><td>¬+</td><td>⊤<sub>D</sub></td><td>⊤<sub>D</sub></td><td>¬-</td><td>¬=1</td></tr><tr><th>¬-</th><td>⊥<sub>D</sub></td><td>=0</td><td>+</td><td>•0</td><td>•1</td><td>0•</td><td>•0</td><td>⊤<sub>D</sub></td><td>•1</td><td>¬-</td><td>¬=1</td><td>⊤<sub>D</sub></td><td>⊤<sub>D</sub></td><td>¬-</td><td>¬=1</td><td>⊤<sub>D</sub></td></tr><tr><th>¬=1</th><td>⊥<sub>D</sub></td><td>•0</td><td>•1</td><td>=0</td><td>+</td><td>⊤<sub>D</sub></td><td>•0</td><td>0•</td><td>•1</td><td>¬=1</td><td>¬-</td><td>¬-</td><td>¬=1</td><td>⊤<sub>D</sub></td><td>⊤<sub>D</sub></td><td>⊤<sub>D</sub></td></tr><tr><th>⊤<sub>D</sub></th><td>⊥<sub>D</sub></td><td>•0</td><td>•1</td><td>•0</td><td>•1</td><td>⊤<sub>D</sub></td><td>•0</td><td>⊤<sub>D</sub></td><td>•1</td><td>⊤<sub>D</sub></td><td>⊤<sub>D</sub></td><td>⊤<sub>D</sub></td><td>⊤<sub>D</sub></td><td>⊤<sub>D</sub></td><td>⊤<sub>D</sub></td><td>⊤<sub>D</sub></td></tr></tbody></table>

Pour automatiser le calcul de v ; w on va passer par un calcul matriciel. On numérote l'ensemble des booléens {0, 1} en numérotant 0 par 0 et 1 par 1. Fort de cette numérotation, à une relation binaire R sur {0, 1} on peut associer une matrice $M^R$ et donc, à un symbole de variation v, on peut associer bijectivement une matrice $A^v$ définie par $A^v = M^{Rv}$. On a donc ceci :

$$ 
\begin{align*}
A^{\perp_D} &= \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix} & A^{=1} &= \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} & A^{=0} &= \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} & A^{*} &= \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} \\
A^{-} &= \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix} & A^{=} &= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} & A^{\neq} &= \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} & A^{0\bullet} &= \begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix} \\
A^{1\bullet} &= \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix} & A^{\bullet 0} &= \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix} & A^{\bullet 1} &= \begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix} & A^{\neg=1} &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \\
A^{\neg=0} &= \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} & A^{\neg+} &= \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} & A^{\neg-} &= \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} & A^{\top_D} &= \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}
\end{align*}
$$

Pour v et w deux symboles de variations, on a donc :

$$ A^v \times A^w = M^{Rv} \times M^{Rw} = M^{Rv \circ Rw} \quad (\text{d'après (15)}) $$

$$ = M^{Rv;w} \quad (\text{d'après (16)}) $$

$$ = A^v;w $$

Donc, pour calculer v ; w, il suffit de faire le produit des matrices $A^v \times A^w$ et de voir quel est le symbole de variation correspondant à cette matrice. L'implantation en Python de ce calcul est présentée en annexe A. De cette façon, on peut construire automatiquement un tableau 16 × 16 de la composition des symboles de variation (voir table 1). On constate bien sur cette table que si $v, w \in \mathcal{D} \cup \{\perp_D, \top_D\}$, $v ; w \in \mathcal{D} \cup \{\perp_D, \top_D\}$, ce qui finit la preuve.

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

Cela permet alors de calculer la composition de cubes :

**Proposition 8.** 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 (17) $$
**Preuve.** On commence par un cas particulier.

**Cas particulier :** $\varphi$ et $\psi$ sont des cubes complets. Autrement écrit, pour toute $a \in \mathcal{V}$, $\text{var}(a, \varphi)$, $\text{var}(a, \psi) \in \mathcal{D}_0$. La définition des $\alpha^v$, $v \in \mathcal{D}_0$ implique qu'il existe des littéraux $\ell(a)$, $m(a)$, $n(a)$, $o(a) \in \{\neg a, a\}$ tels que $a^{\text{var}(a,\varphi)} = \ell(a) \triangleright m(a)$ et $a^{\text{var}(a,\psi)} = n(a) \triangleright o(a)$. Soit alors $\alpha = \bigwedge_{a \in \mathcal{V}} \ell(a)$, $\beta = \bigwedge_{a \in \mathcal{V}} m(a)$, $\gamma = \bigwedge_{a \in \mathcal{V}} n(a)$ et $\delta = \bigwedge_{a \in \mathcal{V}} o(a)$. On a, d'après (1) :

$$ \varphi \equiv \bigwedge_{a \in \mathcal{V}} \ell(a) \triangleright m(a) \equiv \left[ \bigwedge_{a \in \mathcal{V}} \ell(a) \right] \triangleright \left[ \bigwedge_{a \in \mathcal{V}} m(a) \right] $$

Par conséquent, $\varphi \equiv \alpha \triangleright \beta$ et, de même, $\psi \equiv \gamma \triangleright \delta$. On a donc :

$$ \varphi ; \psi \equiv (\alpha \triangleright \beta) ; (\gamma \triangleright \delta) $$

On peut alors appliquer la proposition 5, en distinguant les cas de non-satisfiabilité et de satisfiabilité de $\beta \wedge \gamma$.

1er cas : $\beta \wedge \gamma \models \bot$. D'après la proposition 5, on en déduit que $\varphi$ ; $\psi \equiv \bot$. Ce cas signifie qu'il existe $a \in \mathcal{V}$ tel que $m(a) \wedge n(a) \models \bot$ et donc que $\text{var}(a, \varphi)$ ; $\text{var}(a, \psi) = \bot_{\mathcal{D}}$. Dans ce cas, le terme de droite de l'équivalence de la proposition est également équivalent à $\bot$ et donc, l'équivalence en question est respectée dans ce premier cas.

2ème cas : $\beta \wedge \gamma \not\models \bot$. D'après la proposition 5 puis l'équivalence (1), on en déduit ceci :

$$ \varphi ; \psi \equiv \alpha \triangleright \delta \equiv \bigwedge_{a \in \mathcal{V}} \ell(a) \triangleright o(a) $$

Puisque $\beta \wedge \gamma \not\models \bot$ on a donc $m(a) \wedge n(a) \models \bot$ pour tout $a \in \mathcal{V}$ et donc, d'après la proposition 5 :

$$ \begin{align*} \ell(a) \triangleright o(a) &\equiv (\ell(a) \triangleright m(a)) ; (n(a) \triangleright o(a)) \\ &\equiv a^{\text{var}(a,\varphi)} ; a^{\text{var}(a,\psi)} \\ &\equiv a^{\text{var}(a,\varphi)};\text{var}(a,\psi) \tag{cf. proposition (7)} \end{align*} $$

Par conséquent, on a l'équivalence (17) dans le cas particulier où $\varphi$ et $\psi$ sont des cubes complets.

**Cas général :** $\varphi$ et $\psi$ sont des cubes quelconques.

On définit la fonction qui à un cube $\chi \in \Delta \mathcal{L}\mathcal{P}$ associe un entier naturel $\text{nb}_\vee(\chi)$ de le façon suivante :

$$ \text{nb}_\vee(\chi) = |\{a \in \mathcal{V} | \text{var}(a, \chi) \in \mathcal{D}_1\}| + 3 |\mathcal{V} \setminus \mathcal{V}(\chi)| $$

Par exemple, si $\mathcal{V} = \{a, b, c\}$ et $\chi = a^+ \wedge b^\neq$ alors $\text{nb}_\vee(\chi) = 1 + 3$. En fait $\text{nb}_\vee(\chi)$ est le nombre d'occurrences de $\vee$ dans la formule obtenue en remplaçant dans $\chi$ chaque $a^{v_1}$ (pour $v_1 \in \mathcal{D}_1$) par une disjonction $a^v \vee a^w$ ($v, w \in \mathcal{D}_0$) et en ajoutant à la conjonction un terme $\bigvee_{v \in \mathcal{D}_0} a^v$ pour chaque variable $a$ n'apparaissant pas dans $\chi$. Sur l'exemple ci-dessus, $\chi \equiv a^+ \wedge (b^+ \vee b^-) \wedge (c^{=1} \vee c^{=0} \vee c^+ \vee c^-)$.

On va démontrer la proposition par récurrence sur $\text{nb}_\vee(\varphi) + \text{nb}_\vee(\psi)$. Soit $\text{HR}(p)$ l'hypothèse de récurrence « L'équivalence (17) est vérifiée pour tous cubes $\varphi$ et $\psi$ tels que $\text{nb}_\vee(\varphi) + \text{nb}_\vee(\psi) \le p$ ».

On a $\text{HR}(0)$ d'après le cas particulier montré ci-dessus, puisque $\text{nb}_\vee(\varphi) + \text{nb}_\vee(\psi) = 0$ ssi $\varphi$ et $\psi$ sont des cubes complets.

Supposons $\text{HR}(p)$ pour un entier naturel $p$ et considérons les deux cubes $\varphi$ et $\psi$ tels que $\text{nb}_\vee(\varphi) + \text{nb}_\vee(\psi) = p + 1$. On supposera dans la suite que $\text{nb}_\vee(\varphi) \ge 1$ : si ce n'est pas le cas, on fera un raisonnement similaire sur $\psi$ à celui qu'on va faire sur $\varphi$. Soit $x \in \mathcal{V}$ telle que $\text{var}(x, \varphi) \notin \mathcal{D}_0$. Deux cas sont à considérer.

1er cas : $\text{var}(x, \varphi) \in \mathcal{D}_1$. Dans ce cas, soit $v, w \in \mathcal{D}_0$ tels que $x^{\text{var}(x,\varphi)} \equiv x^v \vee x^w$ et soit le cube $\theta = \bigwedge_{a \in \mathcal{V}\setminus\{x\}} a^{\text{var}(a,\varphi)} : \varphi \equiv x^{\text{var}(x,\varphi)} \wedge \theta$ et $x \notin \mathcal{V}(\theta)$. On a donc $\varphi \equiv (x^v \vee x^w) \wedge \theta$ et donc

$$ \varphi \equiv \varphi_1 \vee \varphi_2 \text{ avec } \varphi_1 = x^v \wedge \theta \text{ et } \varphi_2 = x^w \wedge \theta $$
On a donc $nb_\vee(\varphi_1) = nb_\vee(\varphi_2) = nb_\vee(\varphi) - 1$ donc, $nb_\vee(\varphi_1) + nb_\vee(\psi) = nb_\vee(\varphi_1) + nb_\vee(\psi) = p$ et on peut appliquer HR($p$) sur $\varphi_1$ ; $\psi$ et $\varphi_2$ ; $\psi$ :

$$
\begin{align*}
\varphi_1 ; \psi &\equiv \bigwedge_{a \in \mathcal{V}} a^{\mathrm{var}(a,\varphi_1);\mathrm{var}(a,\psi)} \\
&\equiv x^v;\mathrm{var}(x,\psi) \wedge \bigwedge_{a \in \mathcal{V}\setminus\{x\}} a^{\mathrm{var}(a,\varphi_1);\mathrm{var}(a,\psi)}
\end{align*}
$$

Or, pour $a \in \mathcal{V} \setminus \{x\}$, $\mathrm{var}(a, \varphi_1) = \mathrm{var}(a, \theta) = \mathrm{var}(a, \varphi)$. En faisant un raisonnement analogue sur $\varphi_2$, on arrive à :

$$
\varphi_1 ; \psi \equiv x^v ; \mathit{var}(x, \psi) \wedge \sigma \text{ et } \varphi_2 ; \psi \equiv x^w ; \mathit{var}(x, \psi) \wedge \sigma \\
\text{avec } \sigma = \bigwedge_{a \in \mathcal{V} \setminus \{x\}} a^{\mathit{var}(a, \varphi)} ; \mathit{var}(a, \psi)
$$

Et donc :

$$
\begin{align*}
\varphi ; \psi &\equiv (\varphi_1 \lor \varphi_2) ; \psi \\
&\equiv (\varphi_1 ; \psi) \lor (\varphi_2 ; \psi) \tag{d'après la proposition 6} \\
&\equiv (x^v ; \mathit{var}(x, \psi) \land \sigma) \lor (x^w ; \mathit{var}(x, \psi) \land \sigma) \\
&\equiv (x^v ; \mathit{var}(x, \psi) \lor x^w ; \mathit{var}(x, \psi)) \land \sigma \\
&\equiv [(x^v ; x^{\mathit{var}(x, \psi)}) \lor (x^w ; x^{\mathit{var}(x, \psi)})] \land \sigma \\
&\equiv [(x^v \lor x^w) ; \psi] \land \sigma \tag{d'après (14)} \\
&\equiv x^{\mathit{var}(x, \varphi)} ; \mathit{var}(x, \psi) \land \sigma \\
&\equiv \bigwedge_{a \in \mathcal{V}} a^{\mathit{var}(a, \varphi)} ; \mathit{var}(a, \psi)
\end{align*}
$$

Par conséquent, on a l'équivalence (17) sur $\varphi$ et $\psi$, d'où $\mathrm{HR}(p+1)$.

2ème cas : $x \notin \mathcal{V}(\varphi)$. Cela revient à écrire que $\mathrm{var}(x, \varphi) = \top_D$. Dans ce cas, on s'appuie sur le fait que $a^{\top_D} = \bigvee_{v \in D_0} a^v$ et on procède de façon similaire que pour le premier cas, sauf que $\varphi$ va s'écrire $\varphi_1 \vee \varphi_2 \vee \varphi_3 \vee \varphi_4$, chaque $\varphi_k$ étant égal à un $x^v \wedge \theta$ (pour $v \in D_0$). En suivant la même trame de raisonnement on arrive à la conclusion $\mathrm{HR}(p+1)$.

Dans tous les cas, si $\mathrm{HR}(p)$ alors $\mathrm{HR}(p+1)$ et donc, comme on a aussi $\mathrm{HR}(0)$, cela achève la preuve.

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

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

$$
a^{+} \wedge b^{-} \wedge d^{\neg0} ; a^{-} \wedge c^{-} \wedge d^{+} \equiv a^{\neg0} \wedge b^{\top D} \wedge c^{\bullet0} \wedge d^{+} \wedge e^{\top D} \equiv a^{\neg0} \wedge c^{\bullet0} \wedge d^{+}
$$

(en s'appuyant sur la table 1).

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

4 Représenter des règles d'adaptation pour l'adaptation transformation-
nelle

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 positionnelle. 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 = rSalade \wedge iBatavia \wedge iMagret \wedge iTomate \\ \wedge iHuileDOlive \wedge iVinaigre \wedge \text{rien d'autre}$$

où $rSalade$ se lit « recette de salade », $iMachin$, « recette avec l’ingrédient machin » et $\text{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 \text{rien d'autre} \equiv \alpha \wedge \bigwedge \{\neg a \mid a \in \mathcal{V} \text{ et } \alpha \not\models_{CD} a\}$. En particulier, $c^s \models_{CD} \neg 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^{cible} = rSalade \wedge iTomate \wedge iJusCitron \wedge \neg iAil$$

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

$$x^s = rSalade \wedge iTomate \wedge \neg iJusCitron \wedge \neg iAil \\ y^s = iBatavia \wedge iMagret \wedge iHuileDOlive \wedge iVinaigre \wedge \dots$$

(les points de suspension correspondant à la conjonction des littéraux $\neg a$ où $a \in 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}P, \models)$ : si plusieurs atomes $a^{v1}, a^{v2}, \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 = rSalade^{=1} \wedge iVinaigre^{-} \wedge iJusCitron^{+} \wedge 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'applicabilité et l'application de $\varphi$ sur un problème d'adaptation $((x^s, y^s), x^{cible})$.

## 4.2 Représenter une règle d'adaptation

Une règle d'adaptation est définie comme étant un couple $R = (\varphi, C)$ où $\varphi \in \Delta\mathcal{L}P$ 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^s, y^s), x^{cible})$ et comment définir le résultat de cette application ? Pour répondre à cette question, on va s'appuyer sur une fonction qui à $(\alpha, \varphi, \gamma) \in \mathcal{L}P \times \Delta\mathcal{L}P \times \mathcal{L}P$ associe $\text{appl}(\alpha, \varphi, \gamma) \in \mathcal{L}P$, l'application sur $\alpha$ de $\varphi$ sous contrainte $\gamma$,
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 = \mathbf{appl}(\mathbf{CD} \wedge x^s \wedge y^s, \varphi, \mathbf{CD} \wedge x^{\mathbf{cible}}) \qquad (18) $$

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 \mathbf{CD} \wedge x^{\mathbf{cible}} \wedge y^{\mathbf{cible}}$ où $y^{\mathbf{cible}}$ sera la solution proposée pour $x^{\mathbf{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 = (\varphi, 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$ à 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 $\mathbf{appl}(\alpha, \varphi, \gamma)$ l'application sur $\alpha$ de $\varphi$ sous contrainte $\gamma$. Pour arriver à sa définition, on s'intéressera d'abord à la transformation de $\alpha$ par $\varphi$ sous contrainte $\gamma$, une formule $\mathbf{transf}(\alpha, \varphi, \gamma) \in \Delta LP$ dont le résultat (la partie droite) sera $\mathbf{appl}(\alpha, \varphi, \gamma) = \mathbf{D}(\mathbf{transf}(\alpha, \varphi, \gamma))$.

On propose les trois conditions suivantes sur $\mathcal{I}\mathcal{J} \in \Delta\Omega$ pour que $\mathcal{I}\mathcal{J} \models \mathbf{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 (19) $$

Cette condition est-elle suffisante ? Considérons l'exemple suivant : $\alpha = a \wedge \neg b \wedge c, \varphi = a^- \wedge b^+$ et $\gamma = \top$. Si (19) était une condition nécessaire et suffisante pour que $\mathcal{I}\mathcal{J} \models \mathbf{transf}(\alpha, \varphi, \gamma)$ alors $\mathbf{appl}(\alpha, \varphi, \gamma)$ serait équivalente à $\mathbf{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 supposerons 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 $\mathcal{I}\mathcal{J} \models \mathbf{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 \mathbf{Inv}(\varphi)$ et $\alpha \models x$ (resp. $\alpha \models \neg x$) alors, avec $\beta = \mathbf{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'α par $\varphi$ sous contrainte $\gamma$ ainsi :

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

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

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

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

Malgré l'usage du ceteris paribus, si $\alpha, \varphi$ et $\gamma$ contiennent peu de variables (relativement à $|V|$) on peut calculer $\mathbf{appl}(\alpha, \varphi, \gamma)$ sans avoir à considérer toutes les variables, comme la proposition suivante le montre :

**Proposition 9.** 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 :

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

Comme $\text{cp}(\varphi) \models \text{cp}_W(\varphi)$, on en déduit que $\beta_1 \models \beta_2$ (en particulier parce que si $\psi \models \psi'$ alors $\mathbf{D}(\psi) \models \mathbf{D}(\psi')$ pour toute $\psi \in \Delta\mathcal{LP}$).

Montrons que $\beta_2 \models \beta_1$. 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{IJ} \models (\alpha \triangleright \gamma) \wedge \text{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 \text{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) $\mathcal{I}'\mathcal{J} \models \varphi$;

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

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

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

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

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

**Proposition 10.** Soit $\alpha$ et $\gamma$ deux cubes de $(\mathcal{LP}, \models)$ et $\varphi$, un cube primitif de $(\Delta\mathcal{LP}, \models)$. Soit $\mathcal{W} = \mathcal{V}(\alpha) \cup \mathcal{V}(\varphi) \cup \mathcal{V}(\gamma)$. On peut donc écrire $\alpha \equiv \bigwedge_{a \in \mathcal{W}} \ell(a)$, $\gamma \equiv \bigwedge_{a \in \mathcal{W}} p(a)$, et $\varphi \equiv \bigwedge_{a \in \mathcal{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 \mathcal{V}(\alpha)$ ssi $\ell(a) \neq \top$, $a \in \mathcal{V}(\gamma)$ ssi $p(a) \neq \top$ et $a \in \mathcal{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 \mathcal{W}$, on définit $f(a) \in \{a, \neg a, \bot\}$ de la façon suivante :

$$ \text{Si } \ell(a) \wedge m(a) \models \bot, n(a) \wedge p(a) \models \bot \text{ ou } (\ell(a) \wedge p(a) \models \bot \text{ et } m(a) = n(a) = \top) $$

$$ \text{alors } f(a) = \bot $$

$$ \text{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 \mathcal{W}} f(a) $$

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

**Preuve.** Le principe de la preuve consiste à calculer $\text{appl}(\varphi, \alpha, \gamma)$ sur chaque variable $a \in \mathcal{W}$. De manière générale, on a :

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

$$ \equiv \bigwedge_{a \in \mathcal{W}} (\ell(a) \triangleright p(a)) \wedge \varphi(a) $$

$$ \text{où } \varphi(a) = \begin{cases} m(a) \triangleright n(a) & \text{si } a \in \mathcal{V}(\varphi) \\ a^= & \text{sinon} \end{cases} $$

On va découper l'ensemble des variables de la manière suivante :
<figure><img src="image_4.png" /></figure>

Selon la partie dans laquelle se trouve $a \in W$, on a :

— $W_1 : \ell(a) \neq \top$ et $m(a) = n(a) = p(a) = \top$. On a alors :

$$ (\ell(a) \triangleright p(a)) \wedge \varphi(a) = (\ell(a) \triangleright \top) \wedge a^{\text{equiv}} \\ \equiv \ell(a) \triangleright \ell(a) $$

— $W_2 : p(a) \neq \top$ et $\ell(a) = m(a) = n(a) = \top$. On a alors :

$$ (\ell(a) \triangleright p(a)) \wedge \varphi(a) = (\top \triangleright p(a)) \wedge a^{\text{equiv}} \\ \equiv p(a) \triangleright p(a) $$

— $W_3 : m(a) \neq \top, n(a) \neq \top$ et $\ell(a) = p(a) = \top$. On a alors :

$$ (\ell(a) \triangleright p(a)) \wedge \varphi(a) \equiv m(a) \triangleright n(a) $$

— $W_4 : \ell(a) \neq \top, p(a) \neq \top$ et $m(a) = n(a) = \top$. On a alors :

$$ (\ell(a) \triangleright p(a)) \wedge \varphi(a) = (\ell(a) \triangleright p(a)) \wedge a^{\text{equiv}} \\ \equiv \begin{cases} \ell(a) \triangleright \ell(a) & \text{si } \ell(a) = p(a) \\ \bot & \text{sinon} \end{cases} $$

— $W_5 : \ell(a) = \top, \top \notin \{m(a), n(a), p(a)\}$. On a alors :

$$ (\ell(a) \triangleright p(a)) \wedge \varphi(a) = (\top \triangleright p(a)) \wedge (m(a) \triangleright n(a)) \\ \equiv \begin{cases} m(a) \triangleright n(a) & \text{si } n(a) = p(a) \\ \bot & \text{sinon} \end{cases} $$

— $W_6 : p(a) = \top, \top \notin \{\ell(a), m(a), n(a)\}$. On a alors :

$$ (\ell(a) \triangleright p(a)) \wedge \varphi(a) = (\ell(a) \triangleright \top) \wedge (m(a) \triangleright n(a)) \\ \equiv \begin{cases} \ell(a) \triangleright n(a) & \text{si } \ell(a) = m(a) \\ \bot & \text{sinon} \end{cases} $$

— $W_7 : \top \notin \{\ell(a), m(a), n(a), p(a)\}$, tous les termes ont leur mot à dire. On a alors :

$$ (\ell(a) \triangleright p(a)) \wedge \varphi(a) \\ = (\ell(a) \triangleright p(a)) \wedge (m(a) \triangleright n(a)) \\ \equiv \begin{cases} \ell(a) \triangleright n(a) & \text{si } \ell(a) = m(a) \text{ et } p(a) = n(a) \\ \bot & \text{sinon} \end{cases} $$
On vérifie dans chacun des 7 cas correspondant à chacune de ces 7 zones que, avec $f(a) = D((ℓ(a) \triangleright p(a)) \wedge \varphi(a))$, on a bien le résultat indiqué dans la proposition.

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

Enfin, la proposition suivante permet de calculer $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 10.

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

$$ 
\begin{aligned}
appl(\alpha_1 \lor \alpha_2, \varphi, \gamma) &\equiv appl(\alpha_1, \varphi, \gamma) \lor appl(\alpha_2, \varphi, \gamma) \\
appl(\alpha, \varphi, \gamma_1 \lor \gamma_2) &\equiv appl(\alpha, \varphi, \gamma_1) \lor appl(\alpha, \varphi, \gamma_2)
\end{aligned}
$$

**Preuve.** On a :

$$ 
\begin{aligned}
\mathrm{transf}(\alpha_1 \lor \alpha_2, \varphi, \gamma) &= ((\alpha_1 \lor \alpha_2) \triangleright \gamma) \land \mathrm{cp}(\varphi) \\
&\equiv ((\alpha_1 \triangleright \gamma) \land \mathrm{cp}(\varphi)) \lor ((\alpha_2 \triangleright \gamma) \land \mathrm{cp}(\varphi)) \\
&\equiv \mathrm{transf}(\alpha_1, \varphi, \gamma) \lor \mathrm{transf}(\alpha_2, \varphi, \gamma)
\end{aligned}
$$

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.

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

## 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 (18) sur cet exemple, on obtient un $\beta \in \mathcal{LP}$ qui est satisfiable et tel que $\beta \equiv CD \land x^{cible} \land y^{cible}$ avec

$$ y^{\text{cible}} = i\text{Batavia} \land i\text{Magret} \land i\text{HuileDOlive} \land i\text{JusCitron} \land i\text{Sel} \land \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 [4], 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 \neq \emptyset, 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 \land 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 \land 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 \land y^s$ pour résoudre $x^{cible}$ : avec $y^q$ tel que $x^s \land y^s \equiv x^q \land y^q$, on calcule successivement $y^{q-1}, \dots, y^0$ avec, pour $i \in \{q-1, q-2, \dots, 0\}$, $x^i \land y^i \equiv \text{appl}(x^{i+1} \land y^{i+1}, \varphi_{i+1}, x^i)$. Avec $y^{cible}$ telle que $CD \land x^{cible} \land y^{cible} \equiv x^0 \land y^0$, on a alors une proposition de solution de $x^{cible}$, adaptée en $q$ étapes à partir du cas remémoré.

Notons que dans ce qui précède, les $x^i$ (resp., les $y^i$) ne sont pas nécessairement des problèmes (resp. des solutions). Par exemple, $V(x^0) \supseteq V(CD)$ et $CD$ peut contenir des variables de $V_S$.

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 \land y^s, x^{cible}$ et $\varphi_i$ sont des cubes :
**Proposition 12.** Soit $\alpha$ et $\gamma$, deux cubes de $(LP, \models)$ et $\varphi$, un cube de $(\Delta LP, \models)$. On a :

$$ \mathit{appl}(\alpha, \varphi, \gamma) \not\models \top \quad \mathit{ssi} \quad \mathit{appl}(\gamma, \varphi^{-1}, \top) \wedge \alpha \not\models \bot $$

**Preuve.** On reprend le découpage de l'ensemble des variables de la preuve de la proposition 10. On note

- $C_1$ la condition $\ell(a) \wedge m(a) \not\models \bot$,

- $C_2$ la condition $n(a) \wedge p(a) \not\models \bot$,

- $C_3$ la condition $\ell(a) \wedge p(a) \not\models \bot$.

Pour le calcul direct, les conditions sont :

<table><thead><tr><th>zone</th><th>ℓ(a)</th><th>m(a)</th><th>n(a)</th><th>p(a)</th><th>terme</th><th>condition</th><th>(appl(α, φ, γ))(a)</th></tr></thead><tbody><tr><td>W<sub>1</sub></td><td>ℓ(a)</td><td>⊤</td><td>⊤</td><td>⊤</td><td>ℓ(a) ⋇ ℓ(a)</td><td>Ø</td><td>ℓ(a)</td></tr><tr><td>W<sub>2</sub></td><td>⊤</td><td>⊤</td><td>⊤</td><td>p(a)</td><td>p(a) ⋇ p(a)</td><td>Ø</td><td>p(a)</td></tr><tr><td>W<sub>3</sub></td><td>⊤</td><td>m(a)</td><td>n(a)</td><td>⊤</td><td>m(a) ⋇ n(a)</td><td>Ø</td><td>n(a)</td></tr><tr><td>W<sub>4</sub></td><td>ℓ(a)</td><td>⊤</td><td>⊤</td><td>p(a)</td><td>ℓ(a) ⋇ ℓ(a)</td><td>C<sub>3</sub></td><td>ℓ(a)</td></tr><tr><td>W<sub>5</sub></td><td>⊤</td><td>m(a)</td><td>n(a)</td><td>p(a)</td><td>m(a) ⋇ n(a)</td><td>C<sub>2</sub></td><td>n(a)</td></tr><tr><td>W<sub>6</sub></td><td>ℓ(a)</td><td>m(a)</td><td>n(a)</td><td>⊤</td><td>ℓ(a) ⋇ n(a)</td><td>C<sub>1</sub></td><td>n(a)</td></tr><tr><td>W<sub>7</sub></td><td>ℓ(a)</td><td>m(a)</td><td>n(a)</td><td>p(a)</td><td>ℓ(a) ⋇ n(a)</td><td>C<sub>1</sub> et C<sub>2</sub></td><td>n(a)</td></tr></tbody></table>

Pour le calcul « inverse », les conditions sont :

<table><thead><tr><th>zone</th><th>ℓ(a)</th><th>cp (φ<sup>-1</sup>) (a)</th><th>p(a)</th><th>terme</th><th>cond. 1</th><th>(appl(γ, φ<sup>-1</sup>, ⊤) ∧ α) (a)</th><th>cond. 2</th></tr></thead><tbody><tr><td>W<sub>1</sub></td><td>ℓ(a)</td><td>a<sup>=</sup></td><td>⊤</td><td>ℓ(a) ⋇ ℓ(a)</td><td>Ø</td><td>ℓ(a)</td><td>Ø</td></tr><tr><td>W<sub>2</sub></td><td>⊤</td><td>a<sup>=</sup></td><td>p(a)</td><td>p(a) ⋇ p(a)</td><td>Ø</td><td>p(a)</td><td>Ø</td></tr><tr><td>W<sub>3</sub></td><td>⊤</td><td>n(a) ⋇ m(a)</td><td>⊤</td><td>m(a) ⋇ n(a)</td><td>Ø</td><td>m(a)</td><td>Ø</td></tr><tr><td>W<sub>4</sub></td><td>ℓ(a)</td><td>a<sup>=</sup></td><td>p(a)</td><td>ℓ(a) ⋇ ℓ(a)</td><td>Ø</td><td>ℓ(a)</td><td>C<sub>3</sub></td></tr><tr><td>W<sub>5</sub></td><td>⊤</td><td>n(a) ⋇ m(a)</td><td>p(a)</td><td>m(a) ⋇ n(a)</td><td>C<sub>2</sub></td><td>m(a)</td><td>Ø</td></tr><tr><td>W<sub>6</sub></td><td>ℓ(a)</td><td>n(a) ⋇ m(a)</td><td>⊤</td><td>ℓ(a) ⋇ n(a)</td><td>Ø</td><td>ℓ(a)</td><td>C<sub>1</sub></td></tr><tr><td>W<sub>7</sub></td><td>ℓ(a)</td><td>n(a) ⋇ m(a)</td><td>p(a)</td><td>ℓ(a) ⋇ n(a)</td><td>C<sub>2</sub></td><td>ℓ(a)</td><td>C<sub>1</sub></td></tr></tbody></table>

On a bien l'équivalence : $appl(\gamma, \varphi^{-1}, \top) \wedge \alpha \not\models \bot$ ssi $appl(\alpha, \varphi, \gamma) \not\models \bot$. ■

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

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 \not\models \bot$.

(i = q - 1) $x^{q-1} \wedge y^{q-1} \equiv appl(x^q \wedge y^q, \varphi_q, x^{q-1})$ qui, d'après la proposition 12, est satisfiable ssi $\beta$ est satisfiable avec $\beta = appl(x^{q-1}, \varphi_{q-1}^{-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} \not\models \bot$.

(i = q - 2) $x^{q-2} \wedge y^{q-2} \equiv appl(x^{q-1} \wedge y^{q-1}, \varphi_{q-1}, x^{q-2})$ qui, d'après la proposition 12, est satisfiable ssi $\beta$ est satisfiable avec $\beta = appl(x^{q-2}, \varphi_{q-2}^{-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} \not\models \bot$.

(i = 0) $x^0 \wedge y^0 \equiv appl(x^1 \wedge y^1, \varphi_1, x^0)$ qui, d'après la proposition 12, est satisfiable ssi $\beta$ est satisfiable avec $\beta = appl(x^0, \varphi_0^{-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 \not\models \bot$.
Comme $CD \wedge x^{\text{cible}} \wedge y^{\text{cible}} \equiv x^0 \wedge y^0$, $CD \wedge x^{\text{cible}} \wedge y^{\text{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^{\text{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 $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 [8], $(\Delta 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 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'apprentissage 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^{\text{cible}})$, l'application de $R$ sur $((x^s, y^s), x^{\text{cible}})$ peut être apparentée à un mécanisme d'action : on crée une hypothèse de solution $y^{\text{cible}}$ de $x^{\text{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^{\text{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 [7]). 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 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 [7]). 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 LP, \models)$ et DL-PA

La logique DL-PA (*dynamic logic of propositional assignments*) est une logique dynamique dont les programmes atomiques sont des affectations de variables propositionnelles, i.e. des expressions $+a$ et $-a$ pour $a \in \mathcal{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{LP}, \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{IJ} \models \pi \text{ et } \mathcal{J} \models \alpha \end{array} \right\} $$

$$ \mathcal{M}(+a) = \left\{ \mathcal{IJ} \in \Delta\Omega \mid \begin{array}{l} \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\{ \mathcal{IJ} \in \Delta\Omega \mid \begin{array}{l} \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{IK} \in \Delta\Omega \mid \begin{array}{l} \text{il existe } \mathcal{J} \in \Omega \text{ telle que} \\ \mathcal{IJ} \models \pi_1 \text{ et } \mathcal{JK} \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{II} \mid \mathcal{I} \in \mathcal{M}(\alpha)\} $$

Enfin, $\mathcal{IJ} \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{LP}, \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 2 donne des égalités entre ensembles de modèles de certaines formules de $(\Delta\mathcal{LP}, \models)$ et ensembles de modèles de certains programmes de DL-PA. On notera que dans 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{LP}$ (qui est donc un cas particulier de formule de DL-PA), on a $\mathcal{M}(\alpha?) = \mathcal{M}(\hat{\alpha})$ où $\hat{\alpha}$ est défini dans [8] comme étant le plongement de $\alpha$ dans $(\Delta\mathcal{LP}, \models)$ défini syntaxiquement en remplaçant toutes les occurrences de $a \in \mathcal{V}(\alpha)$ par $a^{=1}$. Enfin, pour $\alpha \in \mathcal{LP}$, $\varphi \in \Delta\mathcal{LP}$ et un programme $\pi$ de DL-PA tel que $\mathcal{M}(\varphi) = \mathcal{M}(\pi)$, on a $\mathcal{M}(\langle\pi\rangle\alpha) = \mathcal{M}(\alpha \wedge \mathcal{G}(\varphi))$.

De façon générale, on peut traduire toute $\varphi \in \Delta\mathcal{LP}$ 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{LP}, \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).
Pour $a \in \mathcal{V}$, $\varphi_1, \varphi_2 \in \Delta\mathcal{LP}$ 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 2 – Des correspondances entre formules de $(\Delta\mathcal{LP}, |=$) et programmes de DL-PA.</caption><thead><tr><th>ϕ ∈ ΔLP</th><th>π : programme de DL-PA</th></tr></thead><tbody><tr><td>cp (a<sup>•1</sup>)</td><td>+a</td></tr><tr><td>cp (a<sup>•0</sup>)</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>¬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>a<sup>-</sup></td><td>a? ; -a ; désaff(V \ {a})</td></tr><tr><td>ϕ<sub>1</sub> ∨ ϕ<sub>2</sub></td><td>π<sub>1</sub> ∪ π<sub>2</sub></td></tr><tr><td>ϕ<sub>1</sub> ; ϕ<sub>2</sub></td><td>π<sub>1</sub> ; π<sub>2</sub></td></tr></tbody></table>

Une preuve simple du fait que $\varphi \in \Delta\mathcal{LP}$ 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{LP}, |=$) : $\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 = \begin{cases} a? ; +a & \text{si } \omega(a) = \text{=1} \\ -a? ; -a & \text{si } \omega(a) = \text{=0} \\ \neg a? ; +a & \text{si } \omega(a) = \text{+} \\ a? ; -a & \text{si } \omega(a) = \text{-} \end{cases} $$

Avec $\mathcal{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 $\mathcal{M}(\pi) = \mathcal{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 $\mathcal{M}(\pi) = \bigcup_{k=1}^p \mathcal{M}(\pi_k) = \bigcup_{k=1}^p \mathcal{M}(\psi_k) = \mathcal{M}(\varphi)$.

Il y a donc des liens forts entre $(\Delta\mathcal{LP}, |=$) et DL-PA qui doivent être étudiés davantage. Il semblerait que $(\Delta\mathcal{LP}, |=$) 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\mathcal{LP}, |=$) 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 [8] 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\mathcal{LP}, |=$) ce qu'une logique dynamique serait à DL-PA. »
Références

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

[2] J. G. CARBONELL : Learning by analogy : Formulating and generalizing plans from past experience. In R. S. MICHALSKI, J. G. CARBONELL et T. M. MITCHELL, éditeurs : *Machine Learning, An Artificial Intelligence Approach*, chapitre 5, pages 137–161. Morgan Kaufmann, Inc., 1983.

[3] J. G. CARBONELL : Derivational analogy : A Theory of Reconstructive Problem Solving and Expertise Acquisition. In *Machine Learning*, volume 2, chapitre 14, pages 371–392. Morgan Kaufmann, Inc., 1986.

[4] A. CORDIER, 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. In S. MONTANI et L. C. JAIN, éditeurs : *Successful Case-based Reasoning Applications-2*, volume 494 de *Studies in Computational Intelligence*, pages 121–162. Springer, 2014.

[5] M. D'AQUIN, F. BADRA, S. LAFROGNE, J. LIEBER, A. NAPOLI et L. SZATHMARY : Case base mining for adaptation knowledge acquisition. In M. M. VELOSO, éditeur : *Proc. of the 20th Int. Joint Conf. on Artificial Intelligence (IJCAI'07)*, pages 750–755. Morgan Kaufmann, Inc., 2007.

[6] M. D'AQUIN, 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.

[7] F. DUPIN DE SAINT-CYR, A. HERZIG, J. LANG et P. MARQUIS : Raisonnement sur l'action et le changement. In *Panorama de l'intelligence artificielle — ses bases méthodologiques, ses développements*, volume 1, chapitre 12, pages 363–392. Cépaduès, 2014.

[8] N. FRANÇOIS, Th. LAURE et J. LIEBER : Une logique pour représenter des variations propositionalles. In Z. BOURAOUI, F. SCHWARZENTRUBER et A. WILCZYNSKI, éditeurs : *Journées d'intelligence artificielle fondamentale – plateforme AFIA 2023*, page 11, Strasbourg, France, juillet 2023. Z. Bouraoui et F. Schwarzentruber and A. Wilczynski.

[9] K. HANNEY et M. T. KEANE : Learning adaptation rules from a case-base. In I. SMITH et B. FALTINGS, éditeurs : *Advances in Case-Based Reasoning – Proc. of the Third Eur. Workshop, EWC-BR’96*, LNAI 1168, pages 179–192. Springer Verlag, Berlin, 1996.

[10] V. JALALI, 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] M. M. RICHTER et R. O. WEBER : *Case-based reasoning, a textbook*. Springer, 2013.

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

A Calcul automatique de la composition des symboles de variations

La preuve de la proposition 7 passe par la construction de la table 1 donnant un tableau 16 × 16 pour la composition des symboles de variation. Ce tableau a été généré par le programme Python donné à la figure 1.
```python
variations = [
    [[0,0], [0,0]], "$\botvar$" ],
    [[1,0], [0,0]], "$\egf$" ],
    [[0,1], [0,0]], "$\plus$" ],
    [[1,1], [0,0]], "$\fag$" ],
    [[0,0], [1,0]], "$\moins$" ],
    [[1,0], [1,0]], "$\fad$" ],
    [[0,1], [1,0]], "$\different$" ],
    [[1,1], [1,0]], "$\neg\egv$" ],
    [[0,0], [0,1]], "$\egv$" ],
    [[1,0], [0,1]], "$\egal$" ],
    [[0,1], [0,1]], "$\vad$" ],
    [[1,1], [0,1]], "$\neg\moins$" ],
    [[0,0], [1,1]], "$\vag$" ],
    [[1,0], [1,1]], "$\neg\plus$" ],
    [[0,1], [1,1]], "$\neg\egf$" ],
    [[1,1], [1,1]], "$\topvar$" ]
]

ordre_sympoles = [0, 1, 2, 4, 8, 3, 5, 12, 10, 9, 6, 14, 13, 11, 7, 15]

def var(i):
    return variations[i][0]

def symb(i):
    return variations[i][1]

def produit(M, N):
    return [ (M[0][0] and N[0][0]) or (M[0][1] and N[1][0]),
             (M[0][0] and N[0][1]) or (M[0][1] and N[1][1]),
             (M[1][0] and N[0][0]) or (M[1][1] and N[1][0]),
             (M[1][0] and N[0][1]) or (M[1][1] and N[1][1]) ]

def nummat(M):
    return M[0][0] + M[0][1]*2 + M[1][0]*4 + M[1][1]*8

def entete_table():
    return "\begin{tabular}{p{0.62cm}||"+"p{0.62cm} |"*16+"}\n"

def fin_table():
    return "\end{tabular}\n"

def premiere_ligne():
    ligne = "\hfil$\compvar$\hfil"
    for i in ordre_sympoles:
        ligne = ligne + " & \hfil" + symb(i) + "\hfil"
    return ligne + " 
\n"

def double_ligne():
    return "\hline 
\hline
\n"

def simple_ligne():
    return "\hline
\n"

def ligne(i):
    ligne = "\hfil"+symb(i)+"\hfil"
    for j in ordre_sympoles:
        ligne = ligne + " & 
\hfil" + symb(nummat(produit(var(i), var(j)))) + "\hfil"
    return ligne + " 
\n"

def instructions_table():
    table = entete_table() + premiere_ligne() + double_ligne()
    for i in ordre_sympoles:
        table = table + ligne(i) + simple_ligne()
    return table + fin_table()

print(instructions_table())
```

<caption>FIGURE 1 – Code Python pour calculer la table de composition des symboles de variations.</caption>