msleziak.com

Pripomeňme, že symetrická diferencia. je definovaná takto:
$$A\triangle B=(A\setminus B)\cup(B\setminus A).$$

V jednej úlohe sa nám hodilo vedieť, že symetrická diferencia je asociatívna, t.j. že pre ľubovoľné množiny $A$, $B$, $C$ platí
$$A\triangle (B\triangle C)=(A\triangle B)\triangle C.$$

Poďme sa pozrieť na nejaké možnosti, ako sa to dá zdôvodniť. (Ktorúkoľvek z možností spomenutých nižšie by som v domácej úlohe bez problémov akceptoval ako riešenie.)

Súčasne, ak sa popozeráte po internete, tak nájdete dôkaz tohto tvrdenia na mnohých miestach. Tu je pár liniek:

• Symmetric Difference is Associative - ProofWiki
• Associativity of symmetric set difference - Mathematics Stack Exchange
• Symmetric difference using Venn diagrams (Discrete Math) - Mathematics Stack Exchange

Pridím ešte linku na môj text z iného predmetu (na učiteľskom štúdiu).
Tu je linka na text a pridám aj linku na slajdy.
Nájdete tam aj zdôvodnenie toho, že symetrická diferencia je asociatívna (pomocou Vennových diagramov aj pomocou tabuľky pravdivostných hodnôt).
Je to veľmi podobné ako to, čo píšem sem na fórum - ale ak by sa vám to náhodou čítalo v PDF-ku, tak môžete pozrieť tam.

Vennove diagramy
Jedna z vecí, ktorú ste asi už používali na dôkaz množinových identít sú Vennove diagramy. T.j. nakreslím si dané množiny vo všeobecnej polohe, čiže tak, aby som tam mal všetky možné prieniky:



A potom si vyznačím, ktoré časti diagramu ležia v množine na ľavej strane rovnosti a ktoré v množine na pravej strane rovnosti. Pokiaľ je zadaná množinová identita pomerne jednoduchá, tak vzniknú obrázky, ktoré sú dostatočne prehľadné na to, aby som ich bol schopný porovnať.

V tomto prípade pre $A\triangle (B\triangle C)$ aj $(A\triangle B)\triangle C$ dostaneme ten istý výsledok:


Tieto diagramy sú možno o čosi prehľadnejšie poukladané v pdf-ku, na ktoré som dal odkaz vyššie.
A takisto aj jedna z liniek, ktoré som sem dal, obsahuje Vennove diagramy.

Tabuľka pravdivostných hodnôt

Človek by mohol namietať, že obrázok zďaleka nie je formálny dôkaz.$\newcommand{\dop}{\complement}\newcommand{\xor}{\mathbin{\mathrm{XOR}}}\newcommand{\Lra}{\Leftrightarrow}$

Rovnosť daných dvoch množín by sme vedeli zdôvodniť, ak sa nám nejako podarí zdôvodniť ekvivalenciu:
$$x \in A\triangle (B\triangle C) \Leftrightarrow (A\triangle B)\triangle C.$$

Podobné veci by sme o čosi ľahšie urobili s nejakými množinovými identitami obsahujúcimi prienik alebo zjednotenie, lebo tam poznáme zodpovedajúce logické spojky:
\begin{align*}
x \in A\cap B \Leftrightarrow (x\in A) \land (x\in B)\\
x \in A\cup B \Leftrightarrow (x\in A) \lor (x\in B)
\end{align*}

Nikto nám nebráni zaviesť si nejakú logickú spojku aj pre takúto operáciu.
Nazveme ju $\xor$, takéto menu sa pre ňu bežne používa.
Wikipédia: XOR.

Platí
$$x\in A\triangle B \Leftrightarrow (x\in A) \xor (x\in B),$$
ak spojka $\xor$ je určená takouto tabuľkou:

$$\begin{array}{|c|c|c|}
\hline
p & q & p\xor q \\\hline
1 & 1 & 0 \\\hline
1 & 0 & 1 \\\hline
0 & 1 & 1 \\\hline
0 & 0 & 0 \\\hline
\end{array}$$

Zaujíma nás teda, či sú ekvivalentné takéto podmienky:
\begin{gather*}
x \in A\triangle (B\triangle C) \Lra (x\in A) \xor ((x\in B) \xor (x\in C))\\
x \in (A\triangle B)\triangle C \Lra ((x\in A) \xor (x\in B)) \xor (x\in C)
\end{gather*}
Na to nám stačí overiť, či takýto výrok je tautológia:
$$(p\xor q)\xor r \Leftrightarrow p\xor(q\xor r).$$
A potom túto tautológiu použiť pre:
\begin{align*}
p&\equiv (x\in A)\\
q&\equiv (x\in B)\\
r&\equiv (x\in C)
\end{align*}

Chceme teda overiť, či sú ekvivalentné nasledujúce dva výroky:
$$(p\xor q)\xor r \Leftrightarrow p\xor(q\xor r)$$

Takto vyzerá tabuľka pravdivostných hodnôt:
$$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
p & q & r & p\xor q &
a:=(p\xor q)\xor r &
q\xor r &
b:=p\xor (q\xor r) &
a\Lra b\\\hline
1 & 1 & 1 & 0 & 1 & 0 & 1 & 1 \\\hline
1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\\hline
1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\\hline
1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\\hline
0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\\hline
0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\\hline
0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\hline
\end{array}$$

Na riadky tejto tabuľky sa dá pozerať aj tak, že sme sa pozreli na veci typu: Ak $x$ patrí do $A$ aj do $B$, ale nepatrí do $C$, bude patriť do ľavej strany? Bude patriť do pravej strany? A toto sme urobili pre všetkých 8 možností, ktoré môžu platiť pre výroky $x\in A$, $x\in B$, $x\in C$.
Môžeme si všimnúť. že vo Vennovom diagrame boli vyfarbené štyri oblasti a v tabuľke sme dostali štyri riadky také, kde $a\equiv 1$ aj $b\equiv 1$.
Riadky tabuľky a oblasti vo Vennovom diagrame si navzájom zodpovedajú. (Mali by sme brať do úvahy aj vonkajšiu oblasť mimo $A\cup B\cup C$, ktorá zodpovedá riadku, kde pravdivostné hodnoty sú nuly.)

Aj riešenie pomocou tabuľky pravdivostných hodnôt nájdete v~texte, ktorý je spomenutý vyššie.

Vyjadrenie pomocou doplnku$\newcommand{\dop}{\complement}\newcommand{\xor}{\mathbin{\mathrm{XOR}}}\newcommand{\Lra}{\Leftrightarrow}$

Iná možnosť, ktorou sa dá zapísať dôkaz pomerne stručne, je uvedomiť si to, že
$$X\triangle Y=X\cap Y^\dop \cup X^\dop \cap Y,$$
kde $X^\dop$ označuje doplnok množiny $X$.
Ak túto rovnosť použijeme a upravujeme dané výrazy, podarí sa nám ich upraviť na to isté.

\begin{align*}
A\triangle (B\triangle C)
&= (A \cap (B\triangle C)^\dop) \cup (A^\dop \cap (B\triangle C)) \\
&= (A \cap ((B\cap C^\dop) \cup (B^\dop \cap C))^\dop) \cup (A^\dop \cap ((B\cap C^\dop) \cup (B^\dop \cap C))) \\
&= (A \cap ((B\cap C^\dop)^\dop \cap (B^\dop \cap C)^\dop)) \cup (A^\dop \cap B\cap C^\dop) \cup (A^\dop \cap B^\dop \cap C) \\
&= (A \cap ((B^\dop \cup C) \cap (B \cup C^\dop))) \cup (A^\dop \cap B\cap C^\dop) \cup (A^\dop \cap B^\dop \cap C) \\
&= (A \cap ((B^\dop \cap C^\dop) \cup (B \cap C))) \cup (A^\dop \cap B\cap C^\dop) \cup (A^\dop \cap B^\dop \cap C) \\
&= (A\cap B\cap C) \cup (A \cap B^\dop \cap C^\dop) \cup (A^\dop \cap B\cap C^\dop) \cup (A^\dop \cap B^\dop \cap C)
\end{align*}

\begin{align*}
(A\triangle B)\triangle C
&= ((A\triangle B) \cap C^\dop) \cup ((A\triangle B)^\dop \cap C) \\
&= (((A\cap B^\dop) \cup (A^\dop \cap B)) \cap C^\dop) \cup (((A\cap B^\dop) \cup (A^\dop \cap B))^\dop \cap C) \\
&= (A\cap B^\dop \cap C^\dop) \cup (A^\dop \cap B \cap C^\dop) \cup ((A\cap B^\dop)^\dop \cap (A^\dop \cap B)^\dop) \cap C \\
&= (A\cap B^\dop \cap C^\dop) \cup (A^\dop \cap B \cap C^\dop) \cup ((A^\dop \cup B) \cap (A \cap B^\dop)) \cap C \\
&= (A\cap B^\dop \cap C^\dop) \cup (A^\dop \cap B \cap C^\dop) \cup (A^\dop \cap B^\dop \cap C) \cup (A \cap B \cap C) \\
\end{align*}

V úpravách sme používali rovnosti ako napríklad:

• $X\cap(Y\cup Z)=(X\cap Y)\cup(X\cap Z)$
• $X\cap X^\dop=0$
• komutatívnosť zjednotenia a prieniku

Najmä sme veľa krát použili de Morganove zákony: $(X\cap Y)^\dop = X^\dop \cup Y^\dop$ a $(X\cup Y)^\dop = X^\dop \cap Y^\dop$