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.

1. 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}$$

2. 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.

1. $\overline{\overline{A}} = A$ (kaksoiskomplementin laki)
2. $A\cup B=B\cup A$ ja $A\cap B=B\cap A$ (vaihdantalait)
3. $A\cup(B\cup C)=(A\cup B)\cup C$ ja $A\cap(B\cap C)=(A\cap B)\cap C$ (liitäntälait)
4. $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)
5. $\overline{A\cup B}=\overline{A}\cap \overline{B}$ ja $\overline{A\cap B}=\overline{A}\cup \overline{B}$ (de Morganin lait)
6. $A=B \Leftrightarrow A\subseteq B \land B\subseteq A$ (joukkojen samuus)
7. $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.

Posting submission...