# Une logique pour représenter des variations propositionnelles

Nicolas François, Thomas Laure, Jean Lieber

► To cite this version:

Nicolas François, Thomas Laure, Jean Lieber. Une logique pour représenter des variations propositionnelles. Journées d'intelligence artificielle fondamentale – plateforme AFIA 2023, Zied Bouraoui; François Schwarzentruber; Anaëlle Wilczynski, Jul 2023, Strasbourg, France. pp.11. hal-04268839

HAL Id: hal-04268839

https://inria.hal.science/hal-04268839v1

Submitted on 2 Nov 2023

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

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

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

Distributed under a Creative Commons CC0 1.0 - Universal - International License
# Une logique pour représenter des variations propositionnelles *

Nicolas François<fnref n="1" />

Thomas Laure<fnref n="2" />

Jean Lieber<fnref n="1" />

1 Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
2 DIENS, École Normale Supérieure, CNRS, Université PSL, 75005 Paris, France

nicolas.francois@loria.fr thomas.laure@ens.psl.eu jean.lieber@loria.fr

## Résumé

La logique propositionnelle (comme d'autres logiques) peut être vue comme une façon de représenter des ensembles d'états du monde (les interprétations). La représentation de variations d'un ensemble d'états du monde à un autre est motivée par des travaux sur le raisonnement à partir de cas : la comparaison entre deux problèmes et le passage d'une solution à une autre peuvent être vus comme des variations d'un ensemble d'états à un autre. Cela a conduit à une notation pour représenter ces variations (une syntaxe) et cet article étudie comment associer à cette notation une sémantique en théorie des modèles dans laquelle une interprétation est un couple d'interprétations en logique propositionnelle (un des états et l'autre). L'article entame une étude classique de cette logique (syntaxe, sémantique, équivalences, NP-compléterie de la satisfiabilité, etc.) et de façons d'associer à un couple de formules propositionnelles une formule de cette logique. L'article se termine par une discussion envisageant une poursuite de cette étude et des applications potentielles.

## Abstract

Propositional logic (as other logics) can be seen as a way to represent a set of states of the world (the interpretations). Representation of variations from a set of states of the world to another is motivated by studies on case-based reasoning: the comparison of two problems and the way a solution is transformed into another solution can be seen as variations from a set of states to another. This has led to a notation for representing these variations (a syntax) and this article studies how to associate to this notation a semantics in model theory in which an interpretation is an ordered pair of interpretations in propositional logic (one of the states and the other one). The article initiates a classical study of this logic (syntax, semantics, equivalences, NP-completeness of satisfiability, etc.) and a way to associate to an ordered pair of propositional formulas a formula of this logic. The article ends with a discussion presenting directions of future work and a presentation of potential applications.

# 1 Introduction et motivations

Le raisonnement à partir de cas (RàPC [15]) est un raisonnement s'appuyant sur une base de cas BC où un cas est, en général, la donnée d'un couple (x, y) où x représente un problème (du domaine d'application considéré) et y est une solution de ce problème. Une session de RàPC a en entrée un problème à résoudre $x^{cible}$ (le « problème cible ») et est souvent constituée de deux étapes : la remémoration et l'adaptation. La remémoration consiste à chercher un cas $(x^s, y^s) \in BC$ (cas *source*) tel que $x^s$ est jugé similaire à $x^{cible}$. L'adaptation consiste à modifier $y^s$ dans l'optique de la résolution du problème cible. Un principe souvent utilisé pour l'adaptation s'appuie sur la notion intuitive de variations entre problèmes et entre solutions :

(1) Calcul de la variation entre $x^s$ et $x^{cible}$, notée $\Delta x$;

(2) Calcul de $\Delta y$, la variation entre $y^s$ et la solution cherchée, sur la base de $\Delta x$;

(3) Calcul de $y^{cible}$, solution plausible<fnref n="1" /> de $x^{cible}$.

L'étape (2) s'appuie typiquement sur des connaissances d'adaptation, souvent représentées par des règles d'adaptation. En général, la prémisse d'une telle règle contient une variation entre problèmes et sa conclusion, une variation entre solutions : « Si deux problèmes varient selon $\Delta x$ alors leurs solutions varient selon $\Delta y$. » De telles règles peuvent être apprises à partir de la base de cas, selon un principe introduit dans [10] et qui a été appelé l'heuristique des variations entre cas (*case difference heuristics*, voir par exemple [13]<fnref n="2" />). L'idée est d'appliquer un processus d'apprentissage artificiel avec comme jeu d'apprentissage des couples $(\Delta x^{ij}, \Delta y^{ij})$ où $(x^i, y^i), (x^j, y^j) \in BC$ et $\Delta x^{ij}$

<footnote>*Les auteurs tiennent à remercier les relecteurs de cet article pour leurs remarques constructives et encourageantes ainsi qu'Henri Prade pour plusieurs conseils judicieux qui ont été utiles à cet article.</footnote>

<footnote n="1">1. En général, le RàPC est un raisonnement hypothétique : la solution proposée résout de façon plausible le problème cible.</footnote>

<footnote n="2">2. Les auteurs ont hésité entre le terme « différence » et le terme « variation ». L'argument qui a fait préférer le second est qu'on s'attend à ce que la différence entre un objet et lui-même soit indépendante de cet objet, ce qu'on attend moins d'une variation.</footnote>
(resp., $\Delta y^{ij}$) est la variation entre $x^i$ et $x^j$ (resp., entre $y^i$ et $y^j$).

Dans certaines applications du RàPC, les problèmes et les solutions peuvent être représentés (ou traduits) sous la forme de propriétés booléennes, qu'on peut coder sous la forme de conjonctions de variables booléennes. Par exemple, on peut considérer les deux problèmes suivants :

$$x^i = a \wedge \neg b \wedge \neg c \wedge d$$

$$x^j = a \wedge \neg b \wedge c \wedge \neg d$$

La variation entre ces problèmes a été notée de la façon suivante dans certains travaux sur l'apprentissage de connaissances d'adaptation s'appuyant sur cette heuristique des variations :

$$\Delta x^{ij} = a^{\equiv v} \wedge b^{\equiv f} \wedge c^{+} \wedge d^{-}$$

où $a^v$ signifie que la propriété booléenne varie selon $v$ où $v = \equiv v$ (resp. $v = \equiv f$) signifie « reste à $v$ (resp. à $f$) » et $v = +$ (resp. $v = -$) signifie « change de $f$ à $v$ » (resp. de $v$ à $f$).

À titre d'exemple, l'apprentissage de règles d'adaptation a été étudiée pour un système de RàPC culinaire [5]. Supposons qu'on trouve dans un livre de recettes (constituant la base de cas) des couples de recettes de desserts similaires dont la première contient des pommes et de la cannelle et la seconde, des poires et du chocolat (mais pas de poires ni de chocolat dans la première et pas de pommes ni de cannelle dans la seconde). À partir de ces couples, on peut apprendre la règle d'adaptation suivante :

Dans les recettes de desserts avec des pommes et de la cannelle, on peut remplacer ces deux ingrédients par des poires et du chocolat.

Cette règle d'adaptation peut s'écrire par l'expression suivante :

$$R = rDessert^{\equiv v} \wedge iPomme^{-} \wedge iCannelle^{-} \wedge iPoire^{+} \wedge iChocolat^{+} \quad (1)$$

(où $rDessert$ est la propriété d'être une recette de dessert, $iPomme$, celle d'être une recette avec des pommes, etc.).

Les expressions telles que celles présentées ci-dessus ne constituent à ce stade qu'une notation, pas un formalisme logique, puisqu'on dispose d'une syntaxe mais pas de sémantique permettant de définir des inférences. L'objectif de cet article est de définir une telle sémantique et d'entamer son étude. Partant de la logique propositionnelle finie ($\mathcal{LP}$, $\models$), sera définie la logique ($\Delta \mathcal{LP}$, $\models$) dont la syntaxe contient les formules telles que celle de la notation introduite ci-dessus et la sémantique sera définie en théorie des modèles.

La section 2 rappelle des notions et notations relatives à la logique propositionnelle finie. La section 3 définit la logique ($\Delta \mathcal{LP}$, $\models$) et présente quelques résultats élémentaires

à son sujet. Étant donné deux formules propositionnelles $\alpha$ et $\beta$, comment définir leurs variations par une formule de ($\Delta \mathcal{LP}$, $\models$)? La section 4 étudie cette question. L'article se termine par une discussion (section 5) qui montre que les directions de recherche pour poursuivre ce travail sont nombreuses.

**Remarque.** Les résultats de cet article ont tous été démontrés mais certaines preuves ne sont pas incluses dans cet article, soit parce qu'elles sont jugées suffisamment simples soit, à l'inverse, parce qu'elles demandent une preuve détaillée. Le rapport [8] est une version étendue de cet article et comprend ces preuves.

## 2 Rappels sur la logique propositionnelle

Soit $\mathcal{V}$ un ensemble fini et non vide de symboles, apelés variables. Une formule est soit une variable (atome de cette logique) soit une expression d'une des formes suivantes : $\neg \alpha$, $\alpha_1 \wedge \alpha_2$ et $\alpha_1 \vee \alpha_2$, où $\alpha$, $\alpha_1$ et $\alpha_2$ sont des formules. On étend cette syntaxe avec d'autres connecteurs considérés comme des abréviations (où $a$ est une variable) : $\perp = a \wedge \neg a$, $\top = \neg \perp$, $\alpha_1 \rightarrow \alpha_2 = \neg \alpha_1 \vee \alpha_2$, $\alpha_1 \leftrightarrow \alpha_2 = (\alpha_1 \rightarrow \alpha_2) \wedge (\alpha_2 \rightarrow \alpha_1)$ et $\alpha_1 \oplus \alpha_2 = \neg(\alpha_1 \leftrightarrow \alpha_2)$. $\mathcal{LP}$ est l'ensemble des formules de cette logique. Pour éviter d'écrire trop de parenthèses, on utilise la priorité des connecteurs usuelle : $\neg$ avant les autres; $\wedge$ et $\vee$ avant les autres connecteurs sauf $\neg$. Ainsi $\neg a \vee b \rightarrow c \wedge \neg d$ se lira $((\neg a) \vee b) \rightarrow (c \wedge (\neg d))$. Un littéral est une formule de la forme $a$ ou de la forme $\neg a$ où $a \in \mathcal{V}$. La taille d'une formule $\alpha$, $|\alpha|$, est le nombre d'occurrences de connecteurs de $\alpha$.

Une interprétation $\mathcal{I}$ est une fonction de $\mathcal{V}$ dans $\{f, v\}$ où $f$ et $v$ dénotent respectivement les valeurs booléennes « faux » et « vrai ». L'ensemble des interprétations est dénoté par $\Omega$. Pour $\mathcal{I} \in \Omega$ et $\alpha \in \mathcal{LP}$, on définit $\mathcal{I} \models \alpha$ — « $\mathcal{I}$ satisfait $\alpha$ » — de la façon suivante (pour $a \in \mathcal{V}$ et $\alpha, \alpha_1, \alpha_2 \in \mathcal{LP}$) :

$$\neg \mathcal{I} \models a \text{ si } \mathcal{I}(a) = v;$$

$$\neg \mathcal{I} \models \neg \alpha \text{ si } \mathcal{I} \models \alpha;$$

$$\neg \mathcal{I} \models \alpha_1 \wedge \alpha_2 \text{ si } \mathcal{I} \models \alpha_1 \text{ et } \mathcal{I} \models \alpha_2.$$

$$\neg \mathcal{I} \models \alpha_1 \vee \alpha_2 \text{ si } \mathcal{I} \models \alpha_1 \text{ ou } \mathcal{I} \models \alpha_2 \text{ (ou les deux).}$$

Un modèle d'une formule $\alpha$ est une interprétation $\mathcal{I}$ qui satisfait $\alpha$ et l'ensemble des modèles de $\alpha$ est dénoté par $M(\alpha)$. Une formule $\alpha_1$ entraîne une formule $\alpha_2$, noté $\alpha_1 \models \alpha_2$, si $M(\alpha_1) \subseteq M(\alpha_2)$. Les formules $\alpha_1$ et $\alpha_2$ sont équivalentes, noté $\alpha_1 \equiv \alpha_2$, si $M(\alpha_1) = M(\alpha_2)$. Une formule $\alpha$ est une tautologie (noté $\models \alpha$) si $M(\alpha) = \Omega$. Une formule $\alpha$ est satisfiable si $M(\alpha) \neq \emptyset$.

Une façon équivalente de considérer la logique propositionnelle consiste à considérer chaque formule $\alpha \in \mathcal{LP}$ comme une représentation d'un sous-ensemble $M(\alpha)$ de $\Omega$. La logique propositionnelle peut alors être vue comme l'étude de $2^\Omega$, l'ensemble des parties de $\Omega$ via l'utilisation
d'intersections, d'unions et de complémentaires (l'algèbre de Boole finie ($2^\Omega$, $\cap$, $\cup$, $\bar{\cup}$)).

Soit $\mathcal{B} = \{\alpha_1, \alpha_2, \dots, \alpha_p\}$ un ensemble fini de formules. $\wedge \mathcal{B}$ dénote $\alpha_1 \wedge \alpha_2 \wedge \dots \wedge \alpha_p$. $\vee \mathcal{B}$ dénote $\alpha_1 \vee \alpha_2 \vee \dots \vee \alpha_p$. On écrira $\mathcal{B} \models \beta$ si $\wedge \mathcal{B} \models \beta$, pour $\beta \in \mathcal{LP}$.

# 3 La logique des variations propositionnelles

Cette section définit la logique $(\Delta LP, \models)$ sur la base de la logique propositionnelle $(LP, \models)$.

## 3.1 Syntaxe

Soit $\mathcal{D}$ l'ensemble de symboles suivant :

$$ \mathcal{D} = \mathcal{D}_0 \cup \mathcal{D}_1 \\ \text{où } \mathcal{D}_0 = \{=\mathbf{f}, =\mathbf{v}, +, -, \} \text{ et } \mathcal{D}_1 = \{=, \neq, \mathbf{f}, \bullet, \mathbf{f}, \mathbf{v}, \bullet, \mathbf{v}\} $$

Un $v \in \mathcal{D}$ est appelé symbole de variation ; si $v \in \mathcal{D}_0$, $v$ est un symbole de variation primitif.

$\Delta LP$ est l'ensemble des expressions obtenues en substituant dans les formules propositionnelles les variables par des expressions $a^v$ où $a \in V$ et $v \in \mathcal{D}$. Un tel $a^v$ est appelé atome de cette logique. Par exemple, si $a, b, c \in V$, $a^{=v} \vee \neg(b^+ \wedge c^-) \in \Delta LP$.

Une formule de $(\Delta LP, \models)$ est un élément de $\Delta LP$. On définit donc formellement une formule de cette logique comme étant soit un atome, soit d'une des formes suivantes : $\neg \varphi$, $\varphi_1 \wedge \varphi_2$ et $\varphi_1 \vee \varphi_2$. Les connecteurs $\top$, $\bot$, $\to$ et $\leftrightarrow$ sont utilisés en tant qu'abréviations, comme en logique propositionnelle (par exemple, $\varphi_1 \to \varphi_2 = \neg\varphi_1 \vee \varphi_2$). La taille d'une formule $\varphi \in \Delta LP$, notée $|\varphi|$, est le nombre d'occurrences de connecteurs de $\varphi$.

## 3.2 Sémantique

Une interprétation en logique propositionnelle représente un état du monde particulier. Dans la logique des variations, on considérera qu'une interprétation représente un changement d'un état du monde à un autre. Ainsi, on définit une interprétation pour la sémantique de cette logique par un couple d'interprétations pour la sémantique de $(LP, \models)$. Formellement, soit $\Delta\Omega = \Omega \times \Omega$. On notera un élément $(\mathcal{I}, \mathcal{J}) \in \Delta\Omega$ par $\mathcal{I}\mathcal{J}$ (sans parenthèse ni virgule, pour simplifier).

Étant donné $\mathcal{I}\mathcal{J} \in \Delta\Omega$ et $\varphi \in \Delta LP$, il reste à définir la relation $\mathcal{I}\mathcal{J} \models \varphi$ (« $\mathcal{I}\mathcal{J}$ satisfait $\varphi$ »). On commence par le faire sur les atomes (pour $a \in V$) :

— Avec symboles de variations primitifs :

— $\mathcal{I}\mathcal{J} \models a^{=f}$ si $\mathcal{I} \nvDash a$ et $\mathcal{J} \nvDash a$;

— $\mathcal{I}\mathcal{J} \models a^{=v}$ si $\mathcal{I} \models a$ et $\mathcal{J} \models a$;

— $\mathcal{I}\mathcal{J} \models a^+$ si $\mathcal{I} \nvDash a$ et $\mathcal{J} \models a$;

— $\mathcal{I}\mathcal{J} \models a^-$ si $\mathcal{I} \models a$ et $\mathcal{J} \nvDash a$;

— Avec symboles de variations non primitifs :

— $\mathcal{I}\mathcal{J} \models a^-$ si $\mathcal{I}\mathcal{J} \models a^{=f}$ ou $\mathcal{I}\mathcal{J} \models a^{=v}$;

— $\mathcal{I}\mathcal{J} \models a^\ddagger$ si $\mathcal{I}\mathcal{J} \models a^+$ ou $\mathcal{I}\mathcal{J} \models a^-$;

— $\mathcal{I}\mathcal{J} \models a^{\bullet f}$ si $\mathcal{I}\mathcal{J} \models a^{=f}$ ou $\mathcal{I}\mathcal{J} \models a^+$;

— $\mathcal{I}\mathcal{J} \models a^{\bullet f}$ si $\mathcal{I}\mathcal{J} \models a^{=f}$ ou $\mathcal{I}\mathcal{J} \models a^-$;

— $\mathcal{I}\mathcal{J} \models a^{\bullet v}$ si $\mathcal{I}\mathcal{J} \models a^{=v}$ ou $\mathcal{I}\mathcal{J} \models a^-$;

— $\mathcal{I}\mathcal{J} \models a^{\bullet v}$ si $\mathcal{I}\mathcal{J} \models a^{=v}$ ou $\mathcal{I}\mathcal{J} \models a^+$.

La sémantique des connecteurs est définie de façon similaire à ce qu'elle était en logique propositionnelle (pour $\varphi, \varphi_1, \varphi_2 \in \Delta LP$) :

— $\mathcal{I}\mathcal{J} \models \neg\varphi$ si $\mathcal{I}\mathcal{J} \nvDash \varphi$;

— $\mathcal{I}\mathcal{J} \models \varphi_1 \wedge \varphi_2$ si $\mathcal{I}\mathcal{J} \models \varphi_1$ et $\mathcal{I}\mathcal{J} \models \varphi_2$;

— $\mathcal{I}\mathcal{J} \models \varphi_1 \vee \varphi_2$ si $\mathcal{I}\mathcal{J} \models \varphi_1$ ou $\mathcal{I}\mathcal{J} \models \varphi_2$.

Les notions introduites en logique propositionnelle relatives à la sémantique se transposent aisément : notion de modèle, $\mathcal{M}(\varphi) = \{\mathcal{I}\mathcal{J} \in \Delta\Omega \mid \mathcal{I}\mathcal{J} \models \varphi\}$, conséquence logique $\varphi_1 \models \varphi_2$, tautologie, satisfiability d'une formule, etc.

Une façon équivalente de considérer la sémantique de cette logique consiste à considérer chaque formule $\varphi \in \Delta LP$ comme une représentation du sous-ensemble $\mathcal{M}(\varphi)$ de $\Delta\Omega = \Omega \times \Omega$, i.e. d'une relation binaire sur $\Omega$.

## 3.3 Propriétés

**Représentabilité d'un ensemble d'interprétations par une formule.** Certaines définitions de formules dans la suite de l'article seront données par leurs ensembles de modèles, donc à l'équivalence logique près. Ce genre de définition est acceptable car tout sous-ensemble de $\Delta\Omega$ est représentable dans $\Delta LP$ :

pour tout $A \subseteq \Delta\Omega$, il existe $\varphi \in \Delta LP$ telle que $\mathcal{M}(\varphi) = A$ (2)

**Preuve de (2).** Soit $\mathcal{I}\mathcal{J} \in \Delta\Omega$, et soit la formule

$$ \psi_{\mathcal{I}\mathcal{J}} = \bigwedge \left\{ a^{\mathrm{var}(\mathcal{I}(a), \mathcal{J}(a))} \mid a \in V \right\} \\ \text{où var : } (\mathbf{f}, \mathbf{f}) \mapsto =\mathbf{f} \quad (\mathbf{v}, \mathbf{v}) \mapsto =\mathbf{v} \\ (\mathbf{f}, \mathbf{v}) \mapsto + \quad (\mathbf{v}, \mathbf{f}) \mapsto - $$

On démontre d'abord que, pour toute $a \in V$, $\mathcal{I}\mathcal{J} \models a^{\mathrm{var}(\mathcal{I}(a), \mathcal{J}(a))}$ (il suffit de considérer les quatre cas pour s'en convaincre). Inversement, si quelle que soit $a \in V$, $\mathcal{I}_1\mathcal{J}_1 \models a^{\mathrm{var}(\mathcal{I}(a), \mathcal{J}(a))}$ entraîne $\mathcal{I}_1(a) = \mathcal{I}(a)$ et $\mathcal{J}_1(a) = \mathcal{J}(a)$, alors $\mathcal{I}_1\mathcal{J}_1 = \mathcal{I}\mathcal{J}$. Par conséquent, $\mathcal{M}(\psi_{\mathcal{I}\mathcal{J}}) = \{\mathcal{I}\mathcal{J}\}$. Soit alors $\varphi = \bigvee\{\psi_{\mathcal{I}\mathcal{J}} \mid \mathcal{I}\mathcal{J} \in A\}$. On en déduit que $\mathcal{M}(\varphi) = A$. ■

**Équivalences et mise sous forme normale.** Les résultats suivants (et leurs preuves) se transposent aisément de résultats de la logique propositionnelle (les formules considérées ci-dessous sont toutes éléments de $\Delta LP$) :

— Théorème de la déduction et son corollaire :

$$ \varphi_1 \models \varphi_2 \quad \text{ssi} \quad \models \varphi_1 \rightarrow \varphi_2 $$

$$ \varphi_1 \equiv \varphi_2 \quad \text{ssi} \quad \models \varphi_1 \leftrightarrow \varphi_2 $$
— Lien entre tautologies et formules satisfiables :

$$ \models \varphi \quad \text{ssi} \quad \neg \varphi \text{ est insatisfiable} $$

— Lois de De Morgan.

— Involutivité de $\neg$, commutativité de $\wedge$ et $\vee$, associativité de $\wedge$ et $\vee$, distributivité de $\wedge$ sur $\vee$, distributivité de $\vee$ sur $\wedge$, etc. (toutes ces propriétés étant vérifiées modulo l'équivalence logique).

Les résultats suivants découlent des définitions :

$$ \left. \begin{array}{l} a^{\neg} \equiv a^{\neg f} \lor a^{\neg v} \\ a^{\bullet f} \equiv a^{\bullet f} \lor a^{\bullet v} \end{array} \quad \begin{array}{l} a^{\neg \bullet} \equiv a^{\neg f} \lor a^{\neg v} \\ a^{\bullet \bullet} \equiv a^{\bullet v} \lor a^{\bullet f} \end{array} \quad \begin{array}{l} a^{\wedge \bullet} \equiv a^{\wedge f} \lor a^{\wedge v} \\ a^{\bullet \wedge} \equiv a^{\wedge v} \lor a^{\wedge f} \end{array} \right| (3) $$

On peut faire les transformations suivantes sur une formule de $(\Delta\mathcal{L}\mathcal{P}, \models)$, transformations qui conservent l'équivalence logique. Dans un premier temps, on peut supprimer tous les atomes $a^v$ où $v \in \mathcal{D}_1$ en utilisant les équivalences (3). Dans un deuxième temps, on peut utiliser une transformation mettant sous une forme normale négative (où $\neg$ n'apparaît que devant les atomes) comme on le fait en logique propositionnelle (en utilisant les lois de De Morgan et l'involutivité de $\neg$ modulo $\equiv$). Enfin, on peut appliquer l'équivalence suivante (de gauche à droite), pour $a \in \mathcal{V}$ et $v \in \mathcal{D}_0$ :

$$ \neg a^v \equiv \bigvee_{w \in \mathcal{D}_0 \setminus \{v\}} a^w \quad (4) $$

De cette façon, on peut écrire toute formule de $(\Delta\mathcal{L}\mathcal{P}, \models)$ comme une formule n'utilisant pas le connecteur $\neg$ ni les symboles de variation non primitifs. L'idée d'une telle transformation est qu'elle pourrait servir de prétraitement dans une procédure de test de satisfiability s'appuyant sur la méthode des tableaux sémantiques [16], pour laquelle un conflit serait n'importe quelle paire d'atomes $\{a^v, a^w\}$ où $a \in \mathcal{V}$, $v, w \in \mathcal{D}_0$ et $v \neq w$. Cette idée sera évoquée à nouveau à la section 5.3.

**Preuve de (4).** Soit $\text{var}^{-1}$ la fonction inverse de la fonction var introduite dans la preuve de (2). Pour $\mathcal{I}\mathcal{J} \in \Delta\Omega$ on a les équivalences

$$ \begin{array}{l} \mathcal{I}\mathcal{J} \models \neg a^v \text{ssi } \mathcal{I}\mathcal{J} \not\models a^v \\ \text{ssi } (\mathcal{I}(a), \mathcal{J}(a)) \neq \text{var}^{-1}(v) \\ \text{ssi } (\mathcal{I}(a), \mathcal{J}(a)) \in \{\mathcal{f}, \mathcal{v}\}^2 \setminus \{\text{var}^{-1}(v)\} \\ \text{ssi } \mathcal{I}\mathcal{J} \models a^w \text{ pour un } w \in \mathcal{D}_0 \setminus \{v\} \\ \text{ssi } \mathcal{I}\mathcal{J} \models \bigvee_{w \in \mathcal{D}_0 \setminus \{v\}} a^w \end{array} $$

Ce qui permet de conclure.

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

On peut noter que le choix, parmi les symboles de variations, de $\{=\mathcal{f}, =\mathcal{v}, +, -\}$ comme ensemble de variations primitives pourrait être changé : il existe d'autres sousensembles de $\mathcal{D}$ permettant de générer $\mathcal{D}$ par des connecteurs logiques. Par exemple, c'est le cas de $\{\mathcal{f}^{\bullet}, \bullet\mathcal{f}, \mathcal{v}^{\bullet}, \bullet\mathcal{v}\}$ puisqu'on a les équivalences suivantes :

$$ \begin{array}{l} a^{\wedge f} \equiv a^{\wedge f^{\bullet}} \wedge a^{\bullet f} \\ a^{\vee} \equiv a^{\vee f} \wedge a^{\bullet v} \\ a^{\wedge \vee} \equiv a^{\wedge \vee f} \wedge a^{\bullet \wedge v} \end{array} $$

**Satisfiabilité et plongement.** Soit $\text{SAT}_\Delta$ le problème de décision qui, étant donné une formule $\varphi$ de $(\Delta\mathcal{L}\mathcal{P}, \models)$ détermine si $\varphi$ est satisfiable. Le problème $\text{SAT}_\Delta$ est NP-complet. On peut prouver cela en montrant que $\text{SAT}_\Delta$ est dans NP puis en montrant que $\text{SAT}_\Delta$ est NP-difficile.

On peut prouver que $\text{SAT}_\Delta$ est dans NP en exhibant un algorithme polynomial non déterministe répondant à ce problème : il suffit de construire un algorithme avec un oracle qui choisit une interprétation $\mathcal{I}\mathcal{J}$ qui satisfait $\varphi$ si $\varphi$ est satisfiable, et de tester que c'est effectivement le cas.

On peut prouver que $\text{SAT}_\Delta$ est NP-difficile en montrant que le problème SAT peut être réduit en temps polynomial à $\text{SAT}_\Delta$. Étant donné $\alpha \in \mathcal{L}\mathcal{P}$, soit $\tilde{\alpha} \in \Delta\mathcal{L}\mathcal{P}$ défini en remplaçant toutes les occurrences de variables propositionnelles $a$ dans $\alpha$ par $a^{\neg v}$. On appelle $\tilde{\alpha}$ le plongement de $\alpha$. Par exemple, si $\alpha = a \wedge \neg (b \vee c)$ alors, $\tilde{\alpha} = a^{\neg v} \wedge \neg (b^{\neg v} \vee c^{\neg v})$. On peut montrer le résultat suivant, pour $\mathcal{I} \in \Omega$ et $\alpha \in \mathcal{L}\mathcal{P}$ :

$$ \mathcal{I} \models \alpha \quad \text{ssi} \quad \mathcal{I}\mathcal{I} \models \tilde{\alpha} \quad (5) $$

Cela peut se prouver par récurrence sur $|\alpha|$. On peut ensuite montrer l'équivalence (pour $\alpha \in \mathcal{L}\mathcal{P}$) suivante :

$$ \alpha \text{ est satisfiable} \quad \text{ssi} \quad \tilde{\alpha} \text{ est satisfiable} \quad (6) $$

Par conséquent, si on dispose d'un algorithme pour $\text{SAT}_\Delta$, en utilisant cette équivalence, on peut construire un algorithme pour SAT avec un pont polynomial (le calcul $\alpha \mapsto \tilde{\alpha}$ étant linéaire en la taille de la formule). Donc, $\text{SAT}_\Delta$ est NP-difficile : le problème NP-complet SAT peut être réduit en temps polynomial à $\text{SAT}_\Delta$.

**Preuve de (6).** L'implication de gauche à droite est une conséquence directe de (5).

La réciproque peut se montrer par la contraposée : on suppose que $\alpha$ est insatisfiable et on va en déduire que $\tilde{\alpha}$ est insatisfiable. On peut mettre $\alpha$ sous FND (forme normale disjonctive 3) en appliquant un processus systématique (utilisant l'involutivité de $\neg$, la distributivité de $\vee$ sur $\wedge$, etc.) pour aboutir à une formule $\alpha_{\text{FND}}$. En utilisant ce même processus sur $\tilde{\alpha}$ on aboutit à une formule $(\tilde{\alpha})_{\text{FND}} = \tilde{\alpha}_{\text{FND}}$. La mise sous FND préserve l'équivalence dans les deux logiques, donc $\alpha_{\text{FND}} \equiv \alpha$ et $\tilde{\alpha}_{\text{FND}} \equiv \tilde{\alpha}$. Or $\alpha$ est insatisfiable, donc $\alpha_{\text{FND}}$ l'est également ce qui signifie que chaque terme de la disjonction $\alpha_{\text{FND}}$ est une conjonction insatisfiable de littéraux. Dans une telle conjonction, on a nécessairement une variable $a$ apparaissant dans un littéral positif et dans un littéral négatif (sinon, la conjonction de littéraux serait satisfiable). Par conséquent, $\tilde{\alpha}_{\text{FND}}$ est une disjonction de conjonctions de littéraux, chacune de ces conjonctions contenant un terme $a^{\neg v}$ et un terme $\neg a^{\neg v}$. Or, $a^{\neg v} \wedge \neg a^{\neg v}$ est insatisfiable dans $(\Delta\mathcal{L}\mathcal{P}, \models)$. Donc, chaque conjonction constituant $\tilde{\alpha}_{\text{FND}}$ est insatisfiable et donc $\tilde{\alpha}_{\text{FND}}$ est également

<footnote n="3">3. Pour rappel, une formule sous FND est une disjonction de conjonctions de littéraux où un littéral est une formule d'une des formes $a$ (littéral positif) et $\neg a$ (littéral négatif) avec $a \in \mathcal{V}$.</footnote>
insatisfiable. Comme $\widehat{\alpha}_{\text{FND}} \equiv \widehat{\alpha}$, on en conclut que $\widehat{\alpha}$ est insatisfiable et c'est ce qu'il fallait démontrer. ■

Un corollaire de (6) est le suivant, pour $\mathcal{B}$, un ensemble fini de formules propositionnelles et $\alpha \in \mathcal{L}\mathcal{P}$ :

$$ \mathcal{B} \models \alpha \quad \text{ssi} \quad \widehat{\mathcal{B}} \models \widehat{\alpha} \qquad (7) $$

où $\widehat{\mathcal{B}} = \{\widehat{\beta} | \beta \in \mathcal{B}\}$. Cela permet de justifier $a$ posteriori le terme de plongement : on peut considérer que l'injection $\alpha \mapsto \widehat{\alpha}$ permet de représenter (dans un sens cohérent avec la relation de conséquence logique) la logique $(\mathcal{L}\mathcal{P}, \vdash)$ au sein de la logique $(\Delta\mathcal{L}\mathcal{P}, \vdash)$. On pourrait aussi se servir de ce plongement en étendant la syntaxe de $(\Delta\mathcal{L}\mathcal{P}, \vdash)$ par celle de $(\mathcal{L}\mathcal{P}, \vdash)$, considérant, par exemple, que $a \wedge b^+$ est une notation pour $a^{\equiv v} \wedge b^+$. Nous éviterons néanmoins de le faire dans cet article.

**Preuve de (7).** Soit $\gamma = \neg (\wedge \mathcal{B} \wedge \neg \alpha)$ : les assertions « $\mathcal{B} \models \alpha$ » et « $\gamma$ est satisfiable » sont équivalentes entre elles, de même que les assertions « $\widehat{\mathcal{B}} \models \widehat{\alpha}$ » et « $\widehat{\gamma}$ est satisfiable ». En appliquant l'équivalence (6) sur $\gamma$ cela permet de conclure. ■

# 4 Variation d'une formule propositionnelle à une autre

Soit $\alpha, \beta \in \mathcal{L}\mathcal{P}$, on cherche à exprimer la variation de $\alpha$ à $\beta$, qu'on notera $\alpha \triangleright \beta$ et qui sera une formule de $(\Delta\mathcal{L}\mathcal{P}, \vdash)$. Plusieurs définitions non équivalentes de l'opérateur $\triangleright$ peuvent a priori être envisagées. Dans cette section, celle qui nous semble la plus simple est étudiée : elle est définie à la section 4.1. Elle permet aussi d'introduire une extension de la syntaxe de $(\Delta\mathcal{L}\mathcal{P}, \vdash)$ ne modifiant pas sa sémantique (section 4.2). Une étude des propriétés de cet opérateur de variation est présentée à la section 4.3. Enfin, d'autres définitions de la variation entre formules propositionnelles sont présentées brièvement, leur étude détaillée étant une perspective (section 4.4).

## 4.1 Définition d'un opérateur de variation

L'opérateur $\triangleright$ qu'on cherche à définir doit a minima correspondre à l'exemple donné en introduction : on s'attend à ce que $x^i \triangleright x^j \equiv \Delta x^{ij}$. La définition proposée ci-dessous vérifie cela et est donnée à l'équivalence logique près, par l'ensemble de ses modèles :

$$ \mathcal{M}(\alpha \triangleright \beta) = \mathcal{M}(\alpha) \times \mathcal{M}(\beta) \qquad (8) $$

En d'autres termes, on considère les variations entre tout modèle de $\alpha$ et tout modèle de $\beta$.

## 4.2 Une extension de la syntaxe de la logique des variations propositionnelles

Les atomes $a^v$ où $a \in \mathcal{V}$ et $v \in \mathcal{D}_0$ peuvent s'exprimer à l'aide de l'opérateur $\triangleright$ défini ci-dessus :

$$ \begin{align*} a^{\equiv f} &\equiv \neg a \triangleright \neg a \\ a^{\triangleright} &\equiv \neg a \triangleright a \end{align*} \qquad \begin{align*} a^{\equiv v} &\equiv a \triangleright a \\ a^{-} &\equiv a \triangleright \neg a \end{align*} $$

On peut généraliser cela en introduisant la notation $\alpha^v$ pour toute formule propositionnelle $\alpha$ et tout $v \in \mathcal{D}_0$ :

$$ \begin{align*} \alpha^{\equiv f} &= \neg \alpha \triangleright \neg \alpha \\ \alpha^{\triangleright} &= \neg \alpha \triangleright \alpha \end{align*} \qquad \begin{align*} \alpha^{\equiv v} &= \alpha \triangleright \alpha \\ \alpha^{-} &= \alpha \triangleright \neg \alpha \end{align*} $$

Et on peut étendre cela aux symboles de variation non primitifs :

$$ \begin{align*} \alpha^{\equiv} &= \alpha^{\equiv f} \vee \alpha^{\equiv v} \\ \alpha^{\not\equiv} &= \alpha^{\triangleright} \vee \alpha^{-} \\ \alpha^{\triangleright\bullet} &= \alpha^{\equiv f} \vee \alpha^{\triangleright} \equiv \neg \alpha \triangleright \top \\ \alpha^{\bullet f} &= \alpha^{\equiv f} \vee \alpha^{-} \equiv \top \triangleright \neg \alpha \\ \alpha^{\triangleright\bullet} &= \alpha^{\equiv v} \vee \alpha^{-} \equiv \alpha \triangleright \top \\ \alpha^{\bullet v} &= \alpha^{\equiv v} \vee \alpha^{\triangleright} \equiv \top \triangleright \alpha \end{align*} $$

Cette extension de la syntaxe ne change pas la sémantique : comme on peut exprimer $\alpha \triangleright \beta$ dans la syntaxe de la logique avant extension, on peut également considérer les $\alpha^v$ (pour $\alpha$ une formule propositionnelle qui n'est pas une variable) comme une abréviation pratique (qui pourrait aussi avoir un intérêt en terme de temps de calculs).

Cette syntaxe étendue se justifie par le fait que la définition de la satisfaction d'un atome $a^v$ par une interprétation $\mathcal{I}\mathcal{J}$ (cf. section 3.2) s'étend aux formules $\alpha^v$, pour tout $\alpha \in \mathcal{L}\mathcal{P}$. Ainsi, $\mathcal{I}\mathcal{J} \models \alpha^{\equiv f}$ ssi $\mathcal{I} \nvDash \alpha$ et $\mathcal{J} \nvDash \alpha$; $\mathcal{I}\mathcal{J} \models \alpha^{\triangleright}$ ssi $\mathcal{I} \nvDash \alpha$ et $\mathcal{J} \models \alpha$, etc.

Les $\alpha^v$, pour $\alpha \in \mathcal{L}\mathcal{P}$ et $v \in \mathcal{D}_0$ sont deux à deux incohérents et leur disjonction est une tautologie :

$$ \text{si } w, x \in \mathcal{D}_0 \text{ et } w \neq x, \alpha^w \wedge \alpha^x \models \bot \qquad (9) $$

$$ \models \alpha^{\equiv f} \vee \alpha^{\equiv v} \vee \alpha^{\triangleright} \vee \alpha^{-} \qquad (10) $$

Donc, si $\alpha \in \mathcal{L}\mathcal{P}$ est satisfiable et n'est pas une tautologie alors $\{M(\alpha^{\equiv f}), M(\alpha^{\equiv v}), M(\alpha^{\triangleright}), M(\alpha^{-})\}$ est une partition de $\Delta\mathcal{L}\mathcal{P}^4$.

Dans la suite de l'article, on considérera qu'une formule $\varphi \in \Delta\mathcal{L}\mathcal{P}$ est n'importe quelle expression respectant cette syntaxe étendue.

On définit la substitution d'une variable $a$ par une formule propositionnelle $\alpha$ dans une formule $\varphi \in \Delta\mathcal{L}\mathcal{P}$ (notation : $\varphi[a\setminus\alpha]$) de façon classique : $a^v[a\setminus\alpha] =$

<footnote n="4">4. La condition $\alpha$ est satisfiable et n'est pas une tautologie n'est là que parce que l'ensemble vide ne peut pas être élément d'une partition : si $\alpha \models \bot$ (resp. $\models \alpha$) alors $M(\alpha^{\equiv v}) = \emptyset$ (resp. $M(\alpha^{\equiv f}) = \emptyset$).</footnote>
$\alpha^v$, $x^v[a\setminus\alpha] = x^v$ pour $x \in \mathcal{V} \setminus \{a\}$, $(-\psi)[a\setminus\alpha] = -\langle\psi[a\setminus\alpha]\rangle$, $(\varphi_1 \wedge \varphi_2)[a\setminus\alpha] = (\varphi_1[a\setminus\alpha]) \wedge (\varphi_2[a\setminus\alpha])$ et $(\varphi_1 \vee \varphi_2)[a\setminus\alpha] = (\varphi_1[a\setminus\alpha]) \vee (\varphi_2[a\setminus\alpha])$. La substitution d'une variable par une formule propositionnelle dans une tautologie de $(\Delta\mathcal{L}\mathcal{P}, \models)$ est une tautologie. Formellement, avec $a \in \mathcal{V}$, $\alpha \in \mathcal{L}\mathcal{P}$ et $\varphi \in \Delta\mathcal{L}\mathcal{P}$ :

$$ \text{si } \models \varphi \text{ alors } \models \varphi[a\setminus\alpha] \quad (11) $$

**Preuve de (11).** Supposons que $\models \varphi$. Soit $\varphi_{\text{FNC}}$, une formule équivalente à $\varphi$ de la forme suivante : $\varphi_{\text{FNC}} = \bigwedge\{\varphi_k \mid k \in \{1, 2, \dots, p\}\}$ où chaque $\varphi_k$ est une disjonction d'atomes $a^v$ où $v \in \mathcal{D}_0$: pour obtenir $\varphi_{\text{FNC}}$, on effectue une série de transformations partant de $\varphi$, d'abord en revenant à la syntaxe de départ (dans laquelle on n'a une occurrence de $\alpha^v$ que si $\alpha \in \mathcal{V}$), puis on se débarrasse des symboles de variations non primitifs, puis, on utilise les mêmes opérations que pour la mise sous forme normale conjonctive en logique propositionnelle et enfin, on applique de gauche à droite l'équivalence (4) autant de fois que nécessaire. Comme $\varphi_{\text{FNC}} \equiv \varphi$ et que $\varphi$ est une tautologie, chacun des $\varphi_k$ est une tautologie. On montre alors que, pour un $\varphi_k$ donné, il existe une variable $a$ telle que $\varphi_k$ contient les quatre atomes $a^v$ pour tout $v \in \mathcal{D}_0$. La substitution $\varphi_k[a\setminus\alpha]$ est donc une disjonction contenant quatre termes deux à deux différents $\alpha^v$ ($v \in \mathcal{D}_0$) et on peut en déduire que $\varphi_k[a\setminus\alpha]$ est une tautologie et, partant, que $\varphi_{\text{FNC}}[a\setminus\alpha]$ est une tautologie. Or, $\varphi_{\text{FNC}}[a\setminus\alpha] \equiv \varphi[a\setminus\alpha]$ (on peut le démontrer en appliquant sur $\varphi[a\setminus\alpha]$ la séquence d'opérations qui a permis de passer de $\varphi$ à $\varphi_{\text{FNC}}$). Donc $\varphi[a\setminus\alpha]$ est une tautologie, ce qui conclut la preuve. ■

## 4.3 Étude de l'opérateur $\triangleright$

On notera $\mathcal{L}\mathcal{P}^{\text{sat}}$ (resp. $\Delta\mathcal{L}\mathcal{P}^{\text{sat}}$) l'ensemble des formules $\alpha \in \mathcal{L}\mathcal{P}$ (resp. $\varphi \in \Delta\mathcal{L}\mathcal{P}$) qui sont satisfiables.

**Articulation de $\triangleright$ avec les connecteurs.** L'opération $\triangleright$ est « distributive » sur $\wedge$ et sur $\vee$ modulo l'équivalence 5. Formellement, pour $\alpha, \alpha_1, \alpha_2, \beta, \beta_1, \beta_2 \in \mathcal{L}\mathcal{P}$ :

$$ \begin{align*} \alpha \triangleright (\beta_1 \wedge \beta_2) &\equiv (\alpha \triangleright \beta_1) \wedge (\alpha \triangleright \beta_2) \\ \alpha \triangleright (\beta_1 \vee \beta_2) &\equiv (\alpha \triangleright \beta_1) \vee (\alpha \triangleright \beta_2) \\ (\alpha_1 \wedge \alpha_2) \triangleright \beta &\equiv (\alpha_1 \triangleright \beta) \wedge (\alpha_2 \triangleright \beta) \\ (\alpha_1 \vee \alpha_2) \triangleright \beta &\equiv (\alpha_1 \triangleright \beta) \vee (\alpha_2 \triangleright \beta) \end{align*} $$

Par ailleurs, pour $\alpha, \beta \in \mathcal{L}\mathcal{P}$, on a :

$$ \begin{align} \alpha \triangleright \beta &\equiv (\alpha \triangleright \top) \wedge (\top \triangleright \beta) \tag{12} \\ - (\alpha \triangleright \beta) &\equiv (-\alpha \triangleright \beta) \vee (\alpha \triangleright \neg\beta) \vee (\neg\alpha \triangleright \neg\beta) \equiv \alpha^{\text{f}\bullet} \vee \beta^{\bullet\text{f}} \nonumber \end{align} $$

Le résultat suivant permet de calculer $\Delta x^{ij}$ en fonction de $x^i$ et $x^j$ (cf. introduction). Soit $\alpha, \beta \in \mathcal{L}\mathcal{P}$ équivalents à une conjonction de littéraux. Alors, $\alpha \triangleright \beta$ est une conjonction d'atomes de $(\Delta\mathcal{L}\mathcal{P}, \models)$. Plus précisément :

$$ \begin{align*} \text{si } \alpha &\equiv \bigwedge_{a \in \mathcal{V}} \ell(a) \text{ et } \beta \equiv \bigwedge_{a \in \mathcal{V}} m(a) \\ \text{avec } \ell(a), m(a) &\in \{a, \neg a, \top\} \\ \text{alors } \alpha \triangleright \beta &\equiv \bigwedge_{a \in \mathcal{V}} \ell(a) \triangleright m(a) \tag{13} \end{align*} $$

et $\ell(a) \triangleright m(a)$ est équivalent à un atome ou à $\top$, selon le tableau suivant :

<table><thead><tr><th></th><th>$m(a) = a$</th><th>$m(a) = \neg a$</th><th>$m(a) = \top$</th></tr></thead><tbody><tr><td>$\ell(a) = a$</td><td>$a^{=v}$</td><td>$a^-$</td><td>$a^{v\bullet}$</td></tr><tr><td>$\ell(a) = \neg a$</td><td>$a^+$</td><td>$a^{=f}$</td><td>$a^{f\bullet}$</td></tr><tr><td>$\ell(a) = \top$</td><td>$a^{\bullet v}$</td><td>$a^{\bullet f}$</td><td>$\top$</td></tr></tbody></table>

**Preuve de (13).** La preuve se fait en appliquant (12) de gauche à droite sur $\alpha \triangleright \beta$, en utilisant la distributivité à gauche et à droite de $\triangleright$ sur $\wedge$, pour obtenir la conjonction sur $a \in \mathcal{V}$ de $(\ell(a) \triangleright \top) \wedge (\top \triangleright m(a))$. En appliquant (12) de droite à gauche, on obtient le résultat désiré. ■

**Étude fonctionnelle de $\triangleright$.** L'opérateur $\triangleright$ n'est pas injectif, en particulier parce que si $\alpha$ est insatisfiable ou $\beta$ est insatisfiable, alors $\alpha \triangleright \beta \equiv \perp$. En revanche, la restriction de $\triangleright$ à $\mathcal{L}\mathcal{P}^{\text{sat}} \times \mathcal{L}\mathcal{P}^{\text{sat}}$ est injective :

$$ \begin{align} \text{si } \alpha_1, \beta_1, \alpha_2, \beta_2 \in \mathcal{L}\mathcal{P}^{\text{sat}} \text{ et } \alpha_1 \triangleright \beta_1 &\equiv \alpha_2 \triangleright \beta_2 \nonumber \\ \text{alors } \alpha_1 &\equiv \alpha_2 \text{ et } \beta_1 \equiv \beta_2 \tag{14} \end{align} $$

L'opérateur $\triangleright$ n'est pas non plus surjectif, mais son ensemble image est intéressant à étudier. Soit les opérations $\mathcal{G}: \Delta\mathcal{L}\mathcal{P} \to \mathcal{L}\mathcal{P}$ et $\mathcal{D}: \Delta\mathcal{L}\mathcal{P} \to \mathcal{L}\mathcal{P}$ définies, à la syntaxe près, pour $\varphi \in \Delta\mathcal{L}\mathcal{P}$, par :

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

$$ \mathcal{M}(\mathcal{D}(\varphi)) = \{\mathcal{J} \in \Omega \mid \text{il existe } \mathcal{I} \in \Omega \text{ telle que } \mathcal{I}\mathcal{J} \models \varphi\} $$

$\mathcal{G}(\varphi)$ (resp. $\mathcal{D}(\varphi)$) peut être compris comme une « projection » à gauche (resp. à droite) de $\varphi$. Soit alors

$$ F(\varphi) = \mathcal{G}(\varphi) \triangleright \mathcal{D}(\varphi) $$

F est un opérateur de fermeture sur $(\Delta\mathcal{L}\mathcal{P}, \models)$ (modulo $\equiv$) :

$$ \begin{align*} \varphi &\models F(\varphi) \\ F(F(\varphi)) &\equiv F(\varphi) \\ \text{si } \varphi_1 &\models \varphi_2 \text{ alors } F(\varphi_1) &\models F(\varphi_2) \end{align*} $$

pour $\varphi, \varphi_1, \varphi_2 \in \Delta\mathcal{L}\mathcal{P}$. Si $\varphi \equiv F(\varphi)$, on dira que $\varphi$ est fermée pour F. L'image de $\mathcal{L}\mathcal{P}^2$ par $\triangleright$ est l'ensemble des formules de $\Delta\mathcal{L}\mathcal{P}$ fermées pour F.

<footnote n="5">5. Les guillemets sont justifiés d'une part par le fait que la distributivité est définie d'habitude sur des opérations internes (alors que $\triangleright$ est externe), d'autre part, par le fait que $\wedge$ et $\vee$ sont des connecteurs (pas des opérations).</footnote>
Cette notion de fermeture est proche de celle qu'on trouve en analyse formelle de concepts (AFC [9]) et l'AFC pourrait être utilisée pour une représentation compacte de formules de ($\Delta\mathcal{L}\mathcal{P}$, $\models$) de la façon suivante. Soit $\varphi \in \Delta\mathcal{L}\mathcal{P}$. Comme $\triangleright$ n'est pas surjective, $\varphi$ ne peut pas nécessairement s'écrire sous la forme $\alpha \triangleright \beta$, mais on va l'écrire sous la forme d'une disjonction de telles formules, il restera alors à écrire chaque $\alpha$ et chaque $\beta$ de façon compacte (ce qui est un problème de logique propositionnelle). Pour ce faire, on considère un tableau dont les lignes sont indexées par les $\mathcal{I} \in \mathcal{G}(\varphi)$ et les colonnes, par les $\mathcal{J} \in \mathcal{D}(\varphi)$ et tel qu'il y ait une incidence sur la case de ligne $\mathcal{I}$ et de colonne $\mathcal{J}$ ssi $\mathcal{I}\mathcal{J} \models \varphi$. En appliquant un algorithme d'AFC, on cherche l'ensemble $\{(A_k, B_k)\}_{k \in \{1, 2, \dots, p\}}$ des rectangles maximaux de ce tableau$^6$. De cette façon, pour tout $k \in \{1, 2, \dots, p\}$, en introduisant $\alpha_k, \beta_k \in \mathcal{L}\mathcal{P}^{\text{sat}}$ tels que $M(\alpha_k) = A_k$ et $M(\beta_k) = B_k$, on peut montrer que $\varphi \equiv \bigvee_{k \in \{1, 2, \dots, p\}} \alpha_k \triangleright \beta_k$.

**Inversion des variations.** Pour $\varphi \in \Delta\mathcal{L}\mathcal{P}$, on définit $\text{inv}(\varphi) \in \Delta\mathcal{L}\mathcal{P}$ obtenue en remplaçant chaque occurrence dans $\varphi$ d'un $v \in \mathcal{D}$ par $\text{inv}(v)$ de la façon suivante :

$$ 
\begin{array}{rcl}
\text{inv}(v) & = & v \quad \text{pour } v \in \{\models f, \models v, \models \neg\} \\
\text{inv}(\cdot) & = & - \quad \text{inv}(\cdot) = + \\
\text{inv}(\cdot f) & = & \bullet f \quad \text{inv}(\cdot f) = f \\
\text{inv}(\cdot v) & = & \bullet v \quad \text{inv}(\cdot v) = v
\end{array}
$$

On peut montrer alors qu'on a, pour $\alpha, \beta \in \mathcal{L}\mathcal{P}$ :

$$ \beta \triangleright \alpha \equiv \text{inv}(\alpha \triangleright \beta) \qquad (15) $$

Pour prouver ce résultat, on peut d'abord prouver par récurrence sur $|\varphi|$ que $M(\text{inv}(\varphi)) = \{\mathcal{J}\mathcal{I} \mid \mathcal{I}\mathcal{J} \in \mathcal{M}(\varphi)\}$. Ensuite, en appliquant ce résultat à $\varphi = \alpha \triangleright \beta$, on obtient :

$$ 
\begin{align*}
M(\text{inv}(\alpha \triangleright \beta)) &= \{\mathcal{J}\mathcal{I} \mid \mathcal{I}\mathcal{J} \in \mathcal{M}(\alpha \triangleright \beta)\} \\
&= \{\mathcal{J}\mathcal{I} \mid \mathcal{I} \in \mathcal{M}(\alpha) \text{ et } \mathcal{J} \in \mathcal{M}(\beta)\} \\
&= \mathcal{M}(\beta) \times \mathcal{M}(\alpha) = \mathcal{M}(\beta \triangleright \alpha)
\end{align*}
$$

## 4.4 D'autres opérateurs de variations entre formules

On peut envisager d'autres opérateurs de variations que $\triangleright$. L'un d'entre eux est considéré en fin d'article (section 5.6.3) et cet opérateur est une généralisation de l'opérateur $\triangleright$ au sens où tout modèle de $\alpha \triangleright \beta$ est un modèle de la variation de $\alpha$ à $\beta$ au sens de cet opérateur. On va considérer dans cette section des opérateurs plus spécifiques que $\triangleright$: l'idée est que prendre tous les couples $\mathcal{I}\mathcal{J}$ tels que $\mathcal{I} \models \alpha$ et $\mathcal{J} \models \beta$ (comme c'est le cas avec $\alpha \triangleright \beta$) peut être considéré comme insuffisamment restrictif.

La question qui se pose alors est celle des critères de restriction sur ces couples. Pour ce faire, une idée inspirée d'opérateurs de révision des croyances fondés sur des distances dist sur $\Omega$ consiste à ne garder dans $M(\alpha \triangleright \beta)$ que les $\mathcal{I}\mathcal{J}$ qui minimisent $\text{dist}(\mathcal{I}, \mathcal{J})$. Formellement, on définit, à l'équivalence près, l'opérateur $\triangleright^{\text{dist}}$ (pour $\alpha, \beta \in \mathcal{L}\mathcal{P}$) par

$$ 
\begin{array}{l}
M(\alpha \triangleright^{\text{dist}} \beta) = \{\mathcal{I}\mathcal{J} \in M(\alpha \triangleright \beta) \mid \text{dist}(\mathcal{I}, \mathcal{J}) = \text{dist}^*\} \\
\qquad \text{où } \text{dist}^* = \text{dist}(M(\alpha), M(\beta))
\end{array}
$$

La révision de $\alpha$ par $\beta$ au sens d'un opérateur de révision $\circ^{\text{dist}}$ paramétré par une distance peut être définie par $\mathcal{J} \models \alpha \circ^{\text{dist}} \beta$ si $\text{dist}(M(\alpha), \mathcal{J}) = \text{dist}^* [12]^7$. On a alors immédiatement $D(\alpha \triangleright^{\text{dist}} \beta) \equiv \alpha \circ^{\text{dist}} \beta$ et aussi $G(\alpha \triangleright^{\text{dist}} \beta) \equiv \beta \circ^{\text{dist}} \alpha$ (la seconde propriété est liée au fait que dist est symétrique). Il devrait être possible (mais c'est laissé en perspective) d'étudier les opérateurs de variations entre formules propositionnelles associées à d'autres opérateurs de révision (pas seulement ceux paramétrés par des distances) voire à d'autres opérateurs du domaine des changements de croyances (tels que les opérateurs de mise à jour).

# 5 Discussion

Cet article a présenté un début d'étude d'une logique des variations propositionnelles. Une tentative de construire des liens avec des travaux proches est présentée en section 5.1. Une brève présentation d'un système formel correct et complet pour cette logique est donnée en section 5.2. Cette étude peut se poursuivre de plusieurs façons, en particulier la conception d'algorithmes d'inférences (§5.3), l'étude d'applications de ce formalisme (§5.4) et celle d'autres logiques des variations, s'appuyant sur d'autres logiques que la logique propositionnelle finie (§5.5). Cette discussion se termine par la présentation de plusieurs (autres) questions ouvertes (section 5.6).

## 5.1 Des travaux proches

Assez étonnamment, nous n'avons pas trouvé de travaux vraiment proches de ce travail, ce qui signifie potentiellement qu'un tel travail très proche nous a échappé (nous pensons avoir cherché sérieusement). Néanmoins, on peut tenter de faire le lien avec différents travaux.

La notion de variation propositionnelle peut évoquer la notion de différence entre fonctions booléennes (une formule de ($\mathcal{L}\mathcal{P}$, $\models$) pouvant être vue comme une représentation d'une fonction de $\{\mathcal{f}, \mathcal{v}\}^{|\mathcal{V}|}$ dans $\{\mathcal{f}, \mathcal{v}\}$), ce qui est

<footnote n="6">6. On rappelle qu'un rectangle d'un tel tableau (appelé contexte en AFC) est un $A \times B$ où $A \neq \emptyset$ est un ensemble de lignes et $B \neq \emptyset$, un ensemble de colonnes, tel qu'il y a une incidence sur toute $(\mathcal{I}, \mathcal{J}) \in A \times B$. Un rectangle $A \times B$ est maximal s'il n'existe aucun rectangle le contenant strictement.</footnote>

<footnote n="7">7. Techniquement, dans [12], l'opérateur $\circ^{\text{dist}}$ est défini pour dist étant la distance de Hamming (ce qui fait qu'il coïncide avec l'opérateur de Dalal [6]). Cependant, la généralisation à toute distance sur $\Omega$ est immédiate et satisfait les postulats AGM [1].</footnote>
étudié dans les travaux d'André Thayse [17]. Dans ces travaux, la différence entre deux fonctions booléennes est calculée par un ou exclusif et ces travaux mènent à un calcul différentiel sur les fonctions booléennes inspiré des travaux en analyse sur les nombres réels (développements de Taylor, etc.). Néanmoins, si on reprend l'objectif initial de ce travail, à savoir représenter des variations utiles, en particulier, pour le RàPC, le simple usage du ou exclusif s'avère insuffisant. Par exemple, la symétrie de $\oplus (\alpha \oplus \beta \equiv \beta \oplus \alpha)$ ne permet pas d'exprimer des variations orientées, i.e. de distinguer le passage de $f$ à $v$ du passage de $v$ à $f$.

La donnée d'une interprétation $\mathcal{I}\mathcal{J} \in \Delta\Omega$ équivaut à la donnée de la fonction qui à $a \in \mathcal{V}$ associe $(\mathcal{I}(a), \mathcal{J}(a)) \in \{f, v\}^2$ (correspondant aux quatre éléments de $\mathcal{D}_0$). Il est donc légitime de s'interroger sur les liens entre $(\Delta\mathcal{L}\mathcal{P}, \models)$ et une logique avec quatre valeurs de vérité, comme c'est le cas de la logique de Belnap-Dunn [3], d'autant que les valeurs de vérité de cette logique sont parfois représentées par des couples de booléens. D'un point de vue sémantique, le lien n'est pas direct, puisque $(\Delta\mathcal{L}\mathcal{P}, \models)$ est une logique avec deux valeurs de vérité. Par ailleurs, le nombre 4 de valeurs de vérité pour la logique de Belnap-Dunn est un fondement de cette logique alors que pour la logique des variations, il n'apparaît que comme une conséquence du choix de la logique propositionnelle comme point de départ pour construire cette logique : d'autres choix sont envisageables comme ce sera évoqué à la section 5.5 et peuvent conduire à des ensembles $\mathcal{D}_0$ de symboles de variation primitifs de cardinaux différents de 4. On peut néanmoins s'interroger sur une relation potentielle entre ces deux logiques, par exemple au niveau algorithmique. Ce travail n'a pas été fait et est une perspective potentielle.

Un lien peut être établi entre $(\Delta\mathcal{L}\mathcal{P}, \models)$ et les logiques modales. Syntaxiquement, on pourrait considérer les symboles de variation comme autant de modalités. Sémantiquement, on pourrait définir $\models$ par la sémantique de Kripke en associant à chaque $\mathcal{I}\mathcal{J} \in \Delta\Omega$ un ensemble de deux mondes, $w_1$ et $w_2$, étiquetés respectivement par $\mathcal{I}$ et $\mathcal{J}$ et une relation d'accessibilité réduite à $\{(w_1, w_2)\}$. Ce lien pourrait être détaillé et étudié, même s'il apparaît à première vue comme excessif d'utiliser des logiques modales pour ne considérer que deux états (alors qu'en général, dans la sémantique de Kripke, l'ensemble des mondes et la relation d'accessibilité change d'une interprétation à une autre) et, de plus, qu'il n'y a pas d'équivalent dans la logique étudiée dans cet article à un emboîtement des modalités (quelque chose comme par un exemple un $(\alpha^+)^{=f}$).

## 5.2 Un système formel pour $(\Delta\mathcal{L}\mathcal{P}, \models)$

Dans le rapport [8], un système formel pour la logique des variations propositionnelles est présenté et il est montré qu'il est correct et complet. Cette section explique comment a été construit ce système formel.

Le point de départ a été $S_H$, le système formel de Hilbert, qui est correct et complet pour la logique propositionnelle. Cela passe par une réduction aux connecteurs $\neg$ et $\rightarrow$ (sans perte d'expressivité, les autres connecteurs pouvant être définis comme des abréviations utilisant ces deux connecteurs) et à l'usage d'un ensemble réduit de symboles de variations : les symboles de variations primitifs sont suffisants et nous les avons tous considérés. Les schémas d'axiomes de $S_H$ ont été repris et d'autres ont été ajoutés qui concernent les symboles de variations. Le fait que $\{M(\alpha^v) | v \in \mathcal{D}_0\}$ soit une partition de $\Delta\Omega$ (pour $\alpha$ satisfiable et non tautologique) nous a semblé nécessaire à exprimer pour assurer la complétude et il s'est avéré suffisant. Cela se traduit ainsi :

- D'après (9), pour tout $w, x \in \mathcal{D}_0$ avec $w \neq x$, $\models \neg(\alpha^w \wedge \alpha^x)$, ce qui se traduit sous la forme de ce schéma d'axiomes :

$$ \alpha^w \rightarrow \neg\alpha^x \quad (\text{pour } \alpha \in \mathcal{L}\mathcal{P} \text{ et } w, x \in \mathcal{D}_0 \text{ avec } w \neq x) $$

- La relation (10) donne une tautologie qui peut être transformée en ce schéma d'axiomes :

$$ \neg\alpha^w \rightarrow (\neg\alpha^x \rightarrow (\neg\alpha^y \rightarrow \alpha^z)) $$

(pour $\alpha \in \mathcal{L}\mathcal{P}$ et $w, x, y, z \in \mathcal{D}_0$ deux à deux distincts) En utilisant le *modus ponens* (seule règle d'inférence de $S_H$), on obtient un système formel dont il est facile de montrer qu'il est correct pour $(\Delta\mathcal{L}\mathcal{P}, \models)$, en particulier puisque tous ses axiomes sont des tautologies, mais la preuve de sa complétude a été plus complexe à établir.

Une perspective serait la définition d'un autre système formel qui soit plus pratique à utiliser en pratique, de la même façon que la déduction naturelle est plus facile à utiliser que $S_H$.

## 5.3 Des algorithmes d'inférences

Les problèmes de décision associés à $(\Delta\mathcal{L}\mathcal{P}, \models)$ se ramènent au problème SAT$_{\Delta}$ de la même manière que ceux associés à $(\mathcal{L}\mathcal{P}, \models)$ se ramènent à SAT.

La méthode la plus simple à implanter pour SAT$_{\Delta}$ consiste en une énumération des $\mathcal{I}\mathcal{J} \in \Delta\Omega$, mais comme $|\Delta\Omega| = 4^{|V|}$, c'est une méthode très coûteuse. Plusieurs pistes sont envisageables pour trouver un algorithme plus efficace en pratique.

L'une d'elles a déjà été évoquée à la section 3.3 : elle consiste à chercher un algorithme appliquant la méthode des tableaux sémantique pour SAT$_{\Delta}$. Un tel algorithme a été spécifié et implanté et ses correction et complétude ont été prouvées (voir [8]).

Une autre serait de chercher une traduction du problème SAT$_{\Delta}$ en un problème SAT et de profiter des algorithmes efficaces en pratique pour SAT. On sait qu'il existe des traductions polynomiales entre ces deux problèmes, puisqu'ils sont tous les deux NP-complet. Il s'agirait alors de trouver une traduction concrète qui soit efficace.
## 5.4 Applications potentielles

### 5.4.1 Au RàPC

Comme cela a été détaillé dans l'introduction, des travaux sur le RàPC, notamment pour l'apprentissage de connaissances d'adaptation (dans des travaux déjà anciens [7], plus récents [14] ou en cours), ont conduit à la syntaxe de la logique des variations, mais ne produisent des expressions qui n'étaient pas des formules logiques, avant qu'une sémantique y soit associée (et c'est l'objet principal de cet article).

À titre d'exemple, la règle d'adaptation R donnée en introduction (équation (1)) permet de résoudre le problème d'adaptation donné par le cas ($x^s, y^s$) (représentation abstraite d'une recette de tarte aux pommes) et le problème $x^{cible}$ (requête « Je veux une recette de dessert avec des poires. ») suivants :

$$ 
\begin{aligned}
x^s \wedge y^s &= \mathit{rDessert} \wedge \mathit{iPomme} \wedge \mathit{iCannelle} \\
&\qquad \wedge \mathit{iP\^ateBris\^ee} \wedge \neg \mathit{iP\^oire} \wedge \neg \mathit{iChocolat} \\
x^{cible} &= \mathit{rDessert} \wedge \mathit{iP\^oire}
\end{aligned}
$$

Le résultat attendu de cette adaptation est $y^{cible} \in \mathcal{L}P$ telle que

$$ 
\begin{aligned}
x^{cible} \wedge y^{cible} &= \mathit{rDessert} \wedge \mathit{iP\^oire} \wedge \mathit{iChocolat} \\
&\qquad \wedge \mathit{iP\^ateBris\^ee} \wedge \neg \mathit{iP\^omme} \wedge \neg \mathit{iCannelle}
\end{aligned}
$$

Une question encore ouverte est comment spécifier une telle adaptation s'appuyant sur R. Une façon de faire qui coïncide avec le résultat attendu dans cet exemple, mais mérite d'être examinée, est la suivante. D'abord, on vérifie que R est applicable sur le problème d'adaptation en testant la satisfiability de ($x^s \wedge y^s \triangleright x^{cible}$) $\wedge R$ (qui est satisfiable dans l'exemple). Puis, on définit l'ensemble des solutions candidates :

$$ Y = \{y \in \mathcal{L}P \mid x^s \wedge y^s \triangleright x^{cible} \wedge y \models R\} $$

Un $y \in Y$ n'entraîne pas nécessairement iPâteBrisée dans l'exemple : cette variable n'apparaît pas dans R. Il faut un autre critère de choix et celui de la conservation maximale du cas source (disant qu'on ne fait une modification que quand elle est nécessaire) permet d'avoir le terme iPâteBrisée.

### 5.4.2 À la révision des croyances

Comme le RàPC, le domaine du changement des croyances est un domaine dans lequel on considère à la fois des assertions sur ce qui est vérifié à un moment donné (les croyances d'un agent donné à un instant donné) et sur ce qui change ou est susceptible de changer. Pour cette raison, on peut envisager d'utiliser le formalisme de représentation des variations présenté ici pour exprimer partiellement

des connaissances sur le changement de croyances (partiellement, car ce formalisme exprime des variations mais ne permet pas d'exprimer des préférences entre variations). Pour explorer plus avant cette idée, on peut s'appuyer sur les liens entre l'adaptation en RàPC et la révision des croyances (voir par exemple [4]).

Une autre idée fait suite à ce qui a été présenté en section 4.4, avec l'introduction d'un opérateur $\triangleright^{dist}$ qui est inspiré de la révision $\circ^{dist}$, puisque $\alpha \triangleright^{dist} \beta$ permet d'exprimer dans $(\Delta\mathcal{L}P, \models)$ à la fois la révision $\alpha \circ^{dist} \beta$ et la révision $\beta \circ^{dist} \alpha$ (la seconde exprimant les modèles de $\alpha$ les plus proches des modèles de $\beta$ et intervenant dans la minimisation de la distance). Ainsi, $\alpha \triangleright^{dist} \beta$ serait une façon de réifier le changement de croyances de la révision de $\alpha$ par $\beta$ et pas uniquement son résultat.

## 5.5 Vers d'autres logiques des différences

Le principe de construction de $(\Delta\mathcal{L}P, \models)$ à partir de $(\mathcal{L}P, \models)$ peut se généraliser à la construction d'une logique $(\Delta\mathcal{L}, \models)$ partant d'une logique $(\mathcal{L}, \models)$ dont la relation $\models$ est définie en théorie des modèles :

- Syntaxiquement, il suffit de remplacer les atomes $a$ de $\mathcal{L}$ par des atomes $a^v$ ($v \in \mathcal{D}$) de $\Delta\mathcal{L}$;

- Sémantiquement, on définira une interprétation de $(\Delta\mathcal{L}, \models)$ comme étant un couple d'interprétations de $(\mathcal{L}, \models)$ et le reste suit le schéma de définition de $(\Delta\mathcal{L}P, \models)$.

De cette façon, on peut définir une logique des variations à partir du calcul des prédicats du premier ordre, par exemple, ou d'un de ses fragments décidables. On peut aussi appliquer ce principe sur $(\Delta\mathcal{L}P, \models)$ pour obtenir une logique des variations de variations propositionnelles $(\Delta\Delta\mathcal{L}P, \models)$, dont on pourrait imaginer (au moins théoriquement) qu'elle puisse s'appliquer à un système de RàPC dont l'étape d'adaptation serait un système de RàPC (travaillant sur des cas d'adaptation, voir, p. ex., [11]).

Une autre façon de généraliser ce travail concerne l'extension vers d'autres symboles de variations, pour des logiques dans lesquelles on aurait des variables non propositionnelles, par exemple des variables s'interprétant comme des nombres ou des valeurs nominales (et non des booleens). À titre d'illustration, considérons la variable âge, représentant l'âge d'une personne, pour comparer deux personnes, une de 150 ans et l'autre de 200 ans. On pourrait noter cette variation de la première personne à la seconde par âge$^{ajouter}(50)$ et en déduire (en s'appuyant sur des connaissances sur les variations) qu'on aura âge$^<$ (ajouter 50 ans à un âge c'est faire croître cet âge). Ce genre de symboles de variation a été introduit dans [2] qui cite, à titre d'autres exemples, les relations de l'algèbre de Allen utilisées comme symboles de variations entre deux intervalles.
## 5.6 Autres questions ouvertes

Cet article présente plusieurs perspectives, souvent légèrement entamées. Cette dernière section en ajoute plusieurs qui sont pratiquement intactes.

### 5.6.1 Composition des variations

Soit $\varphi$ et $\psi$, deux formules de $(\Delta\mathcal{L}\mathcal{P}, \models)$, représentant donc des variations propositionnelles. L'idée de les composer semble naturelle : on peut définir $\psi \circ \varphi$, la composition de $\varphi$ par $\psi$, de la même façon qu'on compose les relations binaires $M(\varphi)$ et $M(\psi)$ sur $\Omega$, i.e. pour $\mathcal{I}, \mathcal{K} \in \Omega: \mathcal{I}\mathcal{K} \models \psi \circ \varphi$ s'il existe $\mathcal{J} \in \Omega$ telle que $\mathcal{I}\mathcal{J} \models \varphi$ et $\mathcal{J}\mathcal{K} \models \psi$. En particulier, on peut montrer, avec cette définition, que, pour $\alpha, \beta, \gamma \in \mathcal{L}\mathcal{P}^{\text{sat}}, (\beta \triangleright \gamma) \circ (\alpha \triangleright \beta) \equiv \alpha \triangleright \gamma$. L'étude de cet opérateur de composition reste à faire, en particulier pour exprimer la composition dans $(\Delta\mathcal{L}\mathcal{P}, \models)$. Par exemple, on peut montrer qu'on a $\alpha^+ \circ \alpha^- \equiv \alpha^{\vee}$, $\alpha^+ \circ \alpha^+ \equiv \perp$ etc. (pour $\alpha \in \mathcal{L}\mathcal{P}$), mais il reste à étudier l'articulation entre la composition et les connecteurs.

Cette étude de la composition est motivée par l'étude de la composition des règles d'adaptation pour le raisonnement à partir de cas. En particulier, on peut s'intéresser à la question de la recherche d'une famille génératrice pour la composition de règles d'adaptation : cette problématique est encore peu étudiée (voir [18]) et mériterait de l'être dans l'optique de l'apprentissage de connaissances d'adaptation (par exemple pour réduire le nombre de règles d'adaptation apprises à valider par un expert).

### 5.6.2 Relation de conséquence dans $(\Delta\mathcal{L}\mathcal{P}, \models)$ modulo une base de $(\mathcal{L}\mathcal{P}, \models)$

Soit $\mathcal{B}$, une base de connaissances de la logique propositionnelle. Une perspective de ce travail serait d'étudier la relation $\models_B$ sur la logique des variations propositionnelles définie, pour $\varphi, \psi \in \Delta\mathcal{L}\mathcal{P}$ par $\varphi \models_B \psi$ si, pour toute $\mathcal{I}\mathcal{J} \in M(\mathcal{B}) \times M(\mathcal{B})$, $\mathcal{I}\mathcal{J} \models \varphi$ entraîne $\mathcal{I}\mathcal{J} \models \psi$. En particulier, les relations $\models$ et $\models_\emptyset$ coïncident. L'étude de cette relation devrait être utile en particulier pour l'organisation des règles d'adaptation d'un système de RàPC, étant donné les connaissances du domaine $\mathcal{B}$ de ce système.

### 5.6.3 Un fragment de $(\Delta\mathcal{L}\mathcal{P}, \models)$

La logique des variations propositionnelles permet d'exprimer à la fois des changements – via les symboles de variations $+$ et $-$ – et des persistances – via les symboles de variations $\models$ et $\models$. On peut s'intéresser à ne retenir que les changements, ce qui conduit à définir un fragment $(\Delta^\pm\mathcal{L}\mathcal{P}, \models)$ de la logique des variations, pour lesquels les seuls symboles de variations permis soient $+$ et $-$. Ce fragment est strict : il existe des formules de $\Delta\mathcal{L}\mathcal{P}$ qui ne sont équivalentes à aucune formule de $\Delta^\pm\mathcal{L}\mathcal{P}$, comme

par exemple $a^{\wedge\vee}$. On peut prouver cela en montrant, pour $\varphi \in \Delta^\pm\mathcal{L}\mathcal{P}$, l'équivalence suivante pour toute $a \in \mathcal{V}$ : $\varphi \wedge a^{\wedge\vee}$ est satisfiable ssi $\varphi \wedge a^{\wedge\models}$ est satisfiable. Comme $a^{\wedge\vee} \wedge a^{\wedge\vee}$ est satisfiable mais que $a^{\wedge\vee} \wedge a^{\wedge\models}$ ne l'est pas, on en conclut que $a^{\wedge\vee}$ n'est pas expressible dans $(\Delta^\pm\mathcal{L}\mathcal{P}, \models)$.

Un intérêt de ce fragment serait de « forcer » à exprimer des variations plus générales. Par exemple, si on prend $\alpha, \beta \in \mathcal{L}\mathcal{P}^{\text{sat}}$, la variation $\alpha \triangleright \beta$ ne réalise pas de généralisation puisqu'elle permet de « retrouver » $\alpha$ et $\beta$ (cf. (14)). Supposons qu'on trouve un moyen d'associer à toute formule $\varphi \in \Delta\mathcal{L}\mathcal{P}$ une formule $\varphi^\pm \in \Delta^\pm\mathcal{L}\mathcal{P}$ qui soit une généralisation minimale de $\varphi : \varphi \models \varphi^\pm$ et, pour toute formule $\psi \in \Delta^\pm\mathcal{L}\mathcal{P}$ telle que $\varphi \models \psi$, on aurait $\varphi^\pm \models \psi$. L'existence pour toute formule $\varphi \in \Delta\mathcal{L}\mathcal{P}$ d'une telle formule $\varphi^\pm$ est une question ouverte (son unicité, à l'équivalence près, est facile à montrer). Dans le cas où une telle formule existerait (ou, du moins, existerait pour les formules fermées), on pourrait définir $(\alpha \triangleright \beta)^\pm$ qui serait une façon plus générale que $\alpha \triangleright \beta$ de traiter de la variation de $\alpha$ vers $\beta$.

La conjecture suivante sur $\varphi^\pm$ est proposée. Soit $\sim$ la relation d'équivalence sur $\Delta\Omega$ définie de la façon suivante (pour $\mathcal{I}_1\mathcal{J}_1, \mathcal{I}_2\mathcal{J}_2 \in \Delta\Omega$) : $\mathcal{I}_1\mathcal{J}_1 \sim \mathcal{I}_2\mathcal{J}_2$ si pour toute $a \in \mathcal{V}$, $\mathcal{I}_1\mathcal{J}_1 \models a^-$ ssi $\mathcal{I}_2\mathcal{J}_2 \models a^-$ et $\mathcal{I}_1\mathcal{J}_1 \models a^+$ ssi $\mathcal{I}_2\mathcal{J}_2 \models a^+$. Soit alors $C\ell_\sim(\mathcal{I}\mathcal{J})$ la classe d'équivalence d'une $\mathcal{I}\mathcal{J} \in \Delta\Omega$. Nous pensons que le résultat suivant est correct :

$$ M(\varphi^{\pm}) = \bigcup \{C\ell_{\sim}(\mathcal{I}\mathcal{J}) \mid \mathcal{I}\mathcal{J} \in M(\varphi)\} \text{ (conjecture)} $$

pour toute formule $\varphi$ de la logique des variations propositionnelles.

## Références

[1] Alchourrón, C. E., P. Gärdenfors et D. Makinson: *On the logic of theory change : partial meet functions for contraction and revision*. J. Symbolic Logic, 50:510–530, 1985.

[2] Badra, F. et J. Lieber: *Une approche pour représenter les variations entre cas — Vers une application à l'extraction de connaissances d'adaptation*. Dans Cordier, A. (rédacteur) : *15ème atelier sur le raisonnement à partir de cas*, pages 47–56, Grenoble, 2007.

[3] Belnap, N. D.: *How a computer should think*. New essays on Belnap-Dunn logic, pages 35–53, 2019.

[4] Cojan, J. et J. Lieber: *Applying belief revision to case-based reasoning*. Dans Prade, H. et G. Richard (rédacteurs) : *Computational Approaches to Analogical Reasoning : Current Trends*, tome 548 de *Studies in Computational Intelligence*, pages 133–161. Springer, 2014.

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

[6] Dalal, M.: *Investigations into a theory of Knowledge Base Revision : Preliminary Report*. Dans Proceedings of the Seventh National Conference on Artificial Intelligence (AAAI), pages 475–479, 1988.

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

[8] François, N., Th. Laure et J. Lieber: *Une logique pour représenter des variations propositionnelles (version étendue)*. Rapport de recherche du LORIA, accessible à partir de l'adresse https://k.loria.fr/publications/, 2023.

[9] Ganter, B. et R. Wille: *Formal concept analysis : mathematical foundations*. Springer Science & Business Media, 2012.

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

[11] Jarmulak, J., S. Craw et R. Rowe: *Using case-base data to learn adaptation knowledge for design*. Dans Proc. of the 17th Int. Joint Conf. on Artificial Intelligence (IJCAI'01), pages 1011–1016. Morgan Kaufmann, Inc., 2001.

[12] Katsuno, H. et A. Mendelzon: *Propositional knowledge base revision and minimal change*. Artificial Intelligence, 52(3):263–294, 1991.

[13] Leake, D., X. Ye et D. J Crandall: *Supporting Case-Based Reasoning with Neural Networks : An Illustration for Case Adaptation*. Dans AAAI Spring Symposium : Combining Machine Learning with Knowledge Engineering, tome 2, 2021.

[14] Lieber, J. et E. Nauer: *Adapation knowledge discovery using positive and negative cases*. Dans ICCBR 2021 - 29th International Conference on Case-Based Reasoning, Salamanca (Virtual), Spain, 2021.

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

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

[17] Thayse, A.: *Boolean calculus of differences*. Springer, 1981.

[18] Tixier, M., F. Badra et J. Lieber: *Familles généra-trices de règles d'adaptation pour assister leur ac-quisition semi-automatique*. Dans 19ème Journées Francophones d'Ingénierie des Connaissances (IC 2008), pages 225–236, Nancy, France, juin 2008. https://hal.science/hal-00416700.