Différence symétrique

Deux listes contiennent des nombres : A contient 1, 2, 3 et 5 ; B contient 3, 4, 5 et 6. Entourons ceux qui figurent dans une seule liste. Il reste 1, 2, 4 et 6. Les nombres 3 et 5 disparaissent, car ils sont communs aux deux listes.

L'ensemble ainsi obtenu est la différence symétrique. Elle conserve les appartenances exclusives : dans A ou dans B, mais jamais dans les deux à la fois.

Soient A et B deux ensembles. Leur différence symétrique, notée A△B ou A⊕B, rassemble exactement les éléments qui appartiennent à un seul de ces ensembles. Un élément commun à A et B en est donc exclu, tout comme un élément qui n'appartient à aucun des deux.

En notant A∪B leur union, A∩B leur intersection et A\B les éléments de A qui ne sont pas dans B, les deux écritures suivantes décrivent le même ensemble : $A\mathrm{△}B=(A\cup B)\setminus (A\cap B)=(A\setminus B)\cup (B\setminus A)A\backslash mathbin\{\backslash triangle\}B=(A\backslash cup\; B)\backslash setminus(A\backslash cap\; B)=(A\backslash setminus\; B)\backslash cup(B\backslash setminus\; A)$ La seconde union porte sur deux parties disjointes : aucune valeur ne peut appartenir simultanément à A\B et à B\A.

L'ordre des ensembles ne change pas le résultat : l'opération est commutative. Elle est aussi associative, si bien que plusieurs différences symétriques peuvent être regroupées sans ambiguïté. Pour toutes les parties d'un ensemble de référence, l'ensemble vide ∅ est l'élément neutre. Avec cette opération, l'ensemble de ces parties forme ainsi un groupe abélien.

Prenons les ensembles A = {1, 2, 3, 5} et B = {3, 4, 5, 6}. Les seules données sont leurs huit inscriptions ; certaines valeurs apparaissent dans les deux ensembles.

1. Repérer les valeurs communes : A∩B = {3, 5}.
2. Réunir toutes les valeurs sans les répéter : A∪B = {1, 2, 3, 4, 5, 6}.
3. Retirer de cette union les valeurs communes : A△B = {1, 2, 4, 6}.

Le résultat contient donc quatre éléments. Le contrôle se refait valeur par valeur : 1 et 2 sont seulement dans A, 4 et 6 seulement dans B, tandis que 3 et 5 sont rejetés parce qu'ils figurent dans les deux. La représentation en deux zones rend ce tri visible.

Pour comparer deux listes, la différence symétrique isole ce qui n'apparaît que dans l'une d'elles. Si l'on veut au contraire conserver tous les éléments présents au moins une fois, on choisit l'union.

Dans une suite d'ajouts et de retraits, on peut interpréter l'opération comme une bascule : la première occurrence d'un élément le fait entrer, la suivante le fait sortir. Si le nombre exact d'occurrences importe, un comptage convient mieux.

Pour les ensembles A et B de l'exemple, ce geste sélectionne 1, 2, 4 et 6. Il répond à la question « appartient-il à exactement une liste ? », et non « à combien de listes appartient-il ? »

L'union conserve tout élément présent dans A ou dans B, y compris ceux qui sont communs. Ainsi, 3 et 5 appartiennent à A∪B, mais pas à A△B.

L'intersection ne conserve au contraire que les éléments communs. Dans l'exemple, A∩B = {3, 5}, tandis que A△B = {1, 2, 4, 6} : les deux tris portent sur des zones opposées.

La différence A\B n'est pas symétrique : elle ne garde que ce qui appartient à A sans appartenir à B. Ici, A\B = {1, 2}, alors que la différence symétrique ajoute aussi B\A = {4, 6}.

Si A et B sont égaux, leur différence symétrique est vide : chaque élément appartient aux deux ensembles et se trouve exclu. Un résultat vide ne signifie donc pas que les ensembles de départ sont vides.

Si A et B sont disjoints, leur intersection est vide et leur différence symétrique coïncide avec leur union. Il faut alors vérifier l'absence d'élément commun avant de remplacer l'une par l'autre.

Les répétitions internes ne comptent pas dans un ensemble. Écrire plusieurs fois 3 dans une liste ne crée pas plusieurs éléments ; si les multiplicités doivent être conservées, il faut employer une structure de données qui les enregistre.

L'intersection précise la zone commune que la différence symétrique retire. Le complémentaire d'un ensemble aide à lire les écritures A\B et B\A relativement à un ensemble de référence.

L'algèbre de Boole prolonge cette lecture en reliant les opérations sur les ensembles aux opérations logiques, notamment l'idée d'un « ou » exclusif.