Joukko-operaatiot¶

Määritelmä.

Joukkojen \(A\) ja \(B\) yhdiste (union) \(A\cup B\), leikkaus (intersection) \(A\cap B\) ja erotus \(A\setminus B\) määritellään asettamalla

\[\begin{split}\begin{aligned} A\cup B&=\{x : x\in A\text{ tai }x\in B\},\\ A\cap B&=\{x : x\in A\text{ ja }x\in B\},\\ A\setminus B&=\{x : x\in A\text{ ja }x\not\in B\}.\end{aligned}\end{split}\]

Joukot \(A\) ja \(B\) ovat erillisiä eli pistevieraita (disjoint), jos joukoilla ei ole yhteisiä alkioita, eli \(A\cap B=\varnothing\). Jos \(A \subset E\), niin joukon \(A\) komplementti (complement) \(\overline{A}\) perusjoukon \(E\) suhteen on

\[\overline{A}=E \setminus A=\{x\in E : x\not\in A\}.\]

Joukkojen laskutoimituksia voidaan havainnollistaa Vennin kaavioiden avulla seuraavasti.

Esimerkki.

Jos \(A=\{0,2,3,4\}\) ja \(B=\{1,2\}\), niin

\[\begin{split}\begin{aligned} &A\cup B=\{0,1,2,3,4\} && A\setminus B=\{0,3,4\}\\ &A\cap B=\{2\} && A\setminus\mathbb Z=\varnothing. \end{aligned}\end{split}\]
Jos \(A=(1,3]\) ja \(B=(2,5)\), niin

\[\begin{split}\begin{aligned} &A\cup B=(1,5) && A\setminus B=(1,2]\\ &A\cap B=(2,3] && \mathbb R\setminus A=(-\infty,1]\cup(3,\infty). \end{aligned}\end{split}\]

Joukko-operaatiot voivat liittyä toisiinsa monin tavoin, ja sama joukko voidaan esittää usealla eri tavalla annettujen joukkojen laskutoimituksen tuloksena. Muista, että joukkojen samuus osoitetaan kahdessa osassa, tai vaihtoehtoisesti ekvivalenssiketjun avulla!

Lause.

\(A\setminus B=A\cap \overline{B}\).

Todistus.

Vakuuttaudu ensin tuloksesta Vennin kaavion avulla. Joukko-operaatioiden määritelmiin perustuva todistus voidaan muotoilla seuraavasti.

\[\begin{split}\begin{aligned} x\in A\setminus B &\Leftrightarrow x\in A\text{ ja }x\not\in B&&\text{erotuksen määritelmä}\\ &\Leftrightarrow x\in A\text{ ja }x\in \overline{B}&&\text{komplementin määritelmä}\\ &\Leftrightarrow x\in A\cap \overline{B}&&\text{leikkauksen määritelmä}\end{aligned}\end{split}\]

Tämä ekvivalenssi perustelee sen, että loogiset seuraukset \(x \in A \setminus B \Rightarrow x \in A \cap \overline{B}\) ja \(x \in A \cap \overline{B} \Rightarrow x \in A \setminus \overline{B}\) ovat voimassa. Täten \(A \setminus B \subseteq A \cap \overline{B}\) ja \(A \cap \overline{B} \subseteq A \setminus B\), eli \(A \setminus B = A \cap \overline{B}\) \(\square\)

Joukko-operaatioiden määritelmät nojaavat hyvin vahvasti loogisten konnektiivien varaan, ja tästä syystä monia lauselogiikan päättelysääntöjä vastaa samankaltainen joukko-opin tulos. Joukkojen yhdiste käyttäytyy kuin disjunktio \(\lor\) (tai), leikkaus kuin konjunktio \(\land\) (ja), sekä komplementti kuten negaatio \(\neg\).

Lause.

Olkoot \(A\), \(B\) ja \(C\) joukkoja. Tällöin seuraavat yhtäsuuruudet ja ekvivalenssit ovat voimassa.

\(\overline{\overline{A}} = A\) (kaksoiskomplementin laki)
\(A\cup B=B\cup A\) ja \(A\cap B=B\cap A\) (vaihdantalait)
\(A\cup(B\cup C)=(A\cup B)\cup C\) ja \(A\cap(B\cap C)=(A\cap B)\cap C\) (liitäntälait)
\(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\) ja \(A\cup(B\cap C)=(A\cup B)\cap(A\cup C)\) (osittelulait)
\(\overline{A\cup B}=\overline{A}\cap \overline{B}\) ja \(\overline{A\cap B}=\overline{A}\cup \overline{B}\) (de Morganin lait)
\(A=B \Leftrightarrow A\subseteq B \land B\subseteq A\) (joukkojen samuus)
\(A\subseteq B \Leftrightarrow \overline{B}\subseteq\overline{A}\) (kontrapositiolaki)

Todistus.

Väitteiden todistukset palautuvat suoraviivaisesti logiikan päättelysääntöihin. Kirjoitetaan esimerkiksi ensimmäisen osittelulain todistukseen liittyvä ekvivalenssiketju. Pohdi mitkä välivaiheet perustellaan joukko-operaatioiden määritelmillä ja mitkä loogisilla päättelysäännöillä.

\[\begin{split}\begin{aligned} x\in A\cap(B\cup C) &\Leftrightarrow x\in A\text{ ja }x\in B\cup C\\ &\Leftrightarrow x\in A\text{ ja }(x\in B\text{ tai }x\in C)\\ &\Leftrightarrow (x\in A\text{ ja }x\in B)\text{ tai }(x\in A\text{ ja }x\in C)\\ &\Leftrightarrow x\in A\cap B\text{ tai }x\in A\cap C\\ &\Leftrightarrow x\in (A\cap B)\cup(A\cap C)\end{aligned}\end{split}\]

Joukkoon \(A \cap (B \cup C)\) liittyvä Vennin kaavio voidaan piirtää kuten alla.

\(\square\)

Huomautus.

Vastaavasti kuin lauselogiikan konnektiiveille \(\lor\) ja \(\land\), myös useamman kuin kahden joukon yhdiste ja leikkaus voidaan merkitä ilman sulkuja. Tämä on perusteltua liitäntälakien

\[(A \cup B) \cup C = A \cup (B \cup C) = A \cup B \cup C \qquad\text{ja}\qquad (A \cap B) \cap C = A \cap (B \cap C) = A \cap B \cap C\]

vuoksi.

Esimerkki.

Ilmaise joukot \(A \cup (\overline{A} \cap B)\) ja \((A\setminus B)\cup(A\cap B)\cup(B\setminus A)\) mahdollisimman yksinkertaisessa muodossa.

Ratkaisu.

Ensimmäisen joukon tapauksessa sovelletaan osittelulakia, jolloin

\[A \cup (\overline{A} \cap B) = (A \cup \overline{A}) \cap (A \cup B) = E \cap (A \cup B) = A \cup B,\]

missä \(A \cup \overline{A} = E\) on perusjoukko, jonka suhteen komplementti määritellään. Koska perusjoukko sisältää kaikki mahdolliset alkiot, leikkaus sen kanssa ei muuta käsiteltävää joukkoa.

Toista joukkoa varten muistetaan, että \(A \setminus B = A \cap \overline{B}\) ja sovelletaan osittelulakia kahdesti.

\[\begin{split}\begin{aligned} (A \setminus B)\cup(A\cap B)\cup(B\cap A^c) &=((A\cap \overline{B})\cup(A\cap B))\cup(B\cap \overline{A})\\ &=(A\cap(\overline{B}\cup B))\cup(B\cap \overline{A})\\ &=A\cup(B\cap \overline{A})\\ &=(A\cup B)\cap(A\cup \overline{A})\\ &=A\cup B\end{aligned}\end{split}\]

Joukon yhdiste komplementtinsa kanssa on edelleen koko perusjoukko, joka sievenee helposti laskuissa.