Teorija množic

Relacija pripadnosti: $x\in A$ (”$x$ pripada $A$”)
Podajanje množic:

• naštevanje elementov (npr. $A=\{0,1,2\}$)
• z izjavno formulo (npr. $A=\{x;\phi (x)\}$)

Prazna množica: $A=\varnothing$

Enakost množic: $A=B⟺\forall x(x\in A⟺x\in B)$
Podmnožica: $A\subseteq B⟺\forall x(x\in A⟹x\in B)$

Unija: $A\cup B=\{x;x\in A\vee x\in B\}$
Presek: $A\cap B=\{x;x\in A\wedge x\in B\}$
Razlika: $A\setminus B=\{x;x\in A\wedge x\notin B\}$
Simetrična razlika: $A+B=\{x;x\in A⊻x\in B\}$

Lastosti operacij:

$$\begin{array}{rl}A=B& ⟺A\subseteq B\wedge B\subseteq A\\ A\subseteq B& ⟹A\cup C\subseteq B\cup C\\ A\subseteq B& ⟹A\cap C\subseteq B\cap C\\ A\cap B\subseteq A& \subseteq A\cup B\end{array}$$

Univerzalna množica: vse obravnavane množice so vsebovane v univerzalni množici $S$ (ustreza področju pogovora v predikatnem računu)
Komplement množice: $A^C=S\setminus A$

Dogovor o prioriteti operacij:

$$\cup ,+<\cap ,\setminus <{}^C$$

Potenčna množica: $\mathcal{P}A=\{B;B\subseteq A\}$ je množica vseh podmnožic množice $A$.
Tako $\varnothing$ kot $A$ pripadata $\mathcal{P}A$

Kartezični produkt: $A\times B=\{(a,b);a\in A\wedge b\in B\}$ je množica vseh urejenih parov (urejenih n-teric) množic $A$ in $B$ z $m\ast n$ elementi
$A^n:=A\times A\times ...\times A$

Enakosti množic

(podobno kot zakoni izjavnega računa)

1. Zakon dvojnega komplementa:

$$\begin{array}{rl}(A^C{)}^C& =A\end{array}$$

2. Idempotenca:

$$\begin{array}{rl}A\cap A& =A\\ A\cup A& =A\end{array}$$

3. Komutativnost:

$$\begin{array}{rl}A\cap B& =B\cap A\\ A\cup B& =B\cup A\\ A+B& =B+A\end{array}$$

4. Asociativnost:

$$\begin{array}{rl}(A\cap B)\cap C& =A\cap (B\cap C)\\ (A\cup B)\cup C& =A\cup (B\cup C)\\ (A+B)+C& =A+(B+C)\end{array}$$

5. Absorpcija:

$$\begin{array}{rl}A\cap (A\cup B)& =A\\ A\cup (A\cap B)& =A\end{array}$$

6. Distributivnost:

$$\begin{array}{rl}(A\cap B)\cup C& =(A\cup C)\cap (B\cup C)\\ (A\cup B)\cap C& =(A\cap C)\cup (B\cap C)\\ (A+B)\cap C& =(A\cap C)+(B\cap C)\end{array}$$

7. de Morganova zakona:

$$\begin{array}{rl}(A\cup B{)}^C& =A^C\cap B^C\\ (A\cap B{)}^C& =A^C\cup B^C\end{array}$$

8. Kontrapozicija:

$$\begin{array}{rl}A\subseteq B& =B^C\subseteq A^C\end{array}$$

9. Lastnosti prazne množice $\varnothing$ in univerzalne množice $S$:

$$\begin{array}{rl}A\cup A^C& =S\\ A\cap A^C& =\varnothing \\ A+A& =\varnothing \\ A+A^C& =S\end{array}$$

10. Še lastnosti $\varnothing$ in $S$:

$$\begin{array}{rl}A\cap \varnothing & =\varnothing \\ A\cup \varnothing & =A\\ A\cap S& =A\\ A\cup S& =S\end{array}$$

11. Lastnosti vsebovanosti:

$$\begin{array}{rl}A\subseteq B\sim A\cup B=B& \sim A\cap B=A\sim A\setminus B=\varnothing \\ A\subseteq B& ⟹A\cup C\subseteq B\cup C\\ A\subseteq B& ⟹A\cap C\subseteq B\cap C\\ A\cap B& \subseteq A\\ B& \subseteq A\cup B\end{array}$$

12. Lastnosti razlike množic:

$$\begin{array}{rl}A\setminus B& =A\cap B^C\end{array}$$

13. Lastnosti simetrične razlike:

$$\begin{array}{rl}A+B& =(A\setminus B)\cup (B\setminus A)\\ A+B& =(A\cup B)\setminus (A\cap B)\end{array}$$

14. Lastnosti kartezičnega produkta:

$$\begin{array}{rl}A\times B& \ne B\times A\\ A\times (B\cup C)& =(A\times B)\cup (A\times C)\\ (A\cup B)\times C& =(A\times C)\cup (B\times C)\\ (A\cap B)\times C& =(A\times C)\cap (B\times C)\\ (A\cap B)\times (C\cap D)& =(A\times C)\cap (B\times D)\\ & \\ A\times B=\varnothing & ⟺A=\varnothing \vee B=\varnothing \\ A\subseteq C\wedge B\subseteq D& ⟹A\times B\subseteq C\times D\\ A\times B\subseteq C\times D\wedge A\times B\ne \varnothing & ⟹A\subseteq C\wedge B\subseteq D\end{array}$$

Sistem enačb z množicami

Reševanje sistemov enačb z 1 neznanko:

• $A\subseteq B⟺A\cap B^C=\varnothing$
• $A\cup B=\varnothing ⟺A=\varnothing \wedge B=\varnothing$
• $A\cap B\subseteq A\subseteq A\cup B$
• $A+B=\varnothing ⟺A=B$
• $A\cup B\subseteq C⟺A\subseteq C\wedge B\subseteq C$
• $A\subseteq B\cap C⟺A\subseteq B\wedge A\subseteq C$

Moč množic

Moč množice oz. število elementov A: $|A|$
Primeri: $|\varnothing |=0$, $|\{0,1\}|=2$, $|\{\{0,1\}\}|=1$

Lastnosti:

• $|A\times B|=|A|\ast |B|$
• $|\{f;f:A\to B\}|=|B^A|=|B{|}^{|A|}$
• $|\mathcal{P}A|=2^{|A|}$
• $|A\setminus B|=|A|-|A\cap B|$

Načelo vljučitev in izključitev:

$$\begin{array}{rl}|A\cup B|& =|A|+|B|-|A\cap B|\\ |A\cup B\cup C|& =|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|\end{array}$$