Différence symétrique des différences symétriques

Question

Je cherchais autour de wikipedia la différence symétrique lorsque je suis tombé sur ce fait.

De la propriété des inverses dans un groupe booléen, il s'ensuit que la différence symétrique de deux différences symétriques répétées est équivalente à la différence symétrique répétée de la jointure des deux multisets, où pour chaque double ensemble les deux peuvent être supprimées. En particulier:$$A△C = (A△B)△(B△C)$$

---

où $A△C$ est la différence symétrique de A et C.

Est $A△C = (A△B)△(B△C)$ vrai dans le cas général?

J'ai essayé de le prouver, mais le nombre de termes a augmenté pour moi lorsque j'ai essayé de tout réduire aux unions, aux compléments et aux intersections. Y a-t-il des preuves disponibles que quelqu'un connaît pour cette identité?

Answer 1

La preuve n'est pas difficile une fois que vous avez prouvé que prendre la différence symétrique des ensembles est associative. En utilisant ce fait, pour tous les ensembles$A, B$ et $C$ nous avons \begin{align} (A \bigtriangleup B) \bigtriangleup (B \bigtriangleup C) &= A \bigtriangleup (B \bigtriangleup (B \bigtriangleup C)) \\ &= A \bigtriangleup ((B \bigtriangleup B) \bigtriangleup C) \\ &= A \bigtriangleup(\emptyset\bigtriangleup C) \\ &= A \bigtriangleup C. \end{align}

Je ne suis pas sûr à ce stade si cette identité vaut ou non pour les multisets.

Answer 2

La clé pour cela est d'établir comment étendre la différence d'ensemble (et son complément) dans CNF et DNF. Et, bien sûr, indiquez clairement la forme dont vous avez besoin pour reconvertir en triangle.

$$\def\c{^{\small\complement}}\def\symdiff{\mathop{\triangle}}~~~~ X\symdiff Y ~{= (X\cap Y\c)\cup(X\c\cap Y)\\=(X\cup Y)\cap (X\c\cup Y\c)} \\(X\symdiff Y)\c~{=(X\cap Y)\cup(X\c\cap Y\c)\\=(X\cup Y\c)\cap(X\c\cup Y)}$$

Maintenant pour développer: convertissez d'abord la racine $\symdiff$en DNF, puis chaque disjonction en CNF. (Ou vous pourriez le faire dans l'autre sens). L'objectif est bien entendu de diffuser tous les$B$ du $A$ et $C$.

$\quad(A\symdiff B)\symdiff (B\symdiff C) \\=((A\symdiff B)\cap(B\symdiff C)\c)~\cup~((A\symdiff B)\c\cap(B\symdiff C))\\={((A\cup B)\cap(A\c\cup B\c)\cap(B\cup C\c)\cap(B\c\cup C))~\cup~((A\cup B\c)\cap(A\c\cup B)\cap(B\cup C)\cap(B\c\cup C\c))}\\={(((A\cap C\c)\cup B)\cap((A\c\cap C)\cup B\c))~\cup~((A\cap C\c)\cup B\c)\cap((A\c\cap C)\cup B))}$

Pour faciliter les yeux, laissez $U=(A\cap C\c)$ et $V=(A\c\cap C)$, et nous noterons que $A\symdiff C=U\cup V$.

$\quad(A\symdiff B)\symdiff (B\symdiff C) \\=((U\cup B)\cap(V\cup B\c))~\cup~((U\cup B\c)\cap(V\cup B))$

Vous pouvez le prendre d'ici.