PRINSIP INKLUSI DAN EKSKLUSI

Download Tayangan

Misalkan $A$ dan $B$ himpunan dengan banyak anggota berhingga. Pada materi logika matematika dan himpunan telah dikenal beberapa sifat berikut:

Kardinalitas himpunan $A$ dengan notasi $|A|$ atau $n(A)$ , didefinisikan sebagai banyaknya anggota himpunan $A$ . Sebagai contoh $: A=\{1,2,3,4,5 \}, |A|=n(A)=5.$
$A\cup B = \{n : n\in A \vee n \in B \}.$
$A\cap B = \{n: n\in A \wedge n\in B \}.$
$A-B= A \setminus B = \{n: n\in A \wedge n\notin B\}.$
$A \oplus B = A\cup B \setminus A \cap B.$

Selanjutnya akan dibahas beberapa sifat lanjutan di ranah himpunan berhingga. Misalkan $A$ dan $B$ suatu himpunan berhingga, maka:

$|A\cup B| \leq |A| +|B|$
$|A \cap B| \leq \min(|A|,|B|)$
$|A\oplus B| = |A| +|B| -2|A \cap B|$
$|A-B|=|A\setminus B| \geq |A| - |B|$

Selanjutnya diberikan prinsip inklusi-eksklusi yang berasal dari sifat-sifat himpunan yang diperumum. Diberikan himpunan-himpunan $A_1, A_2, \dots A_r$ maka berlaku

$|A_1 \cup A_2 \cup \cdots \cup A_r| = \left[\sum_{i=1}^{r} |A_i| \right] - \left[\sum_{1\leq i < j \leq r} |A_i \cap Aj| \right]$
$+ \left[ \sum_{1 \leq i <j<k\leq r} |A_i \cap A_j \cap A_k|\right]+ \cdots + (-1)^{r-1} |A_1 \cap \cdots \cap A_r|.$
Untuk $r=2$ , $|A_1 \cup A_2 | = |A_1| + |A_2| - |A_1 \cap A_2|.$

Sebagai contoh soal: Find the number of integers between $1$ and $2020,$ inclusive, that are not divisible by $4,5,6$ and $9.$

Didefinisikan

$\begin{align*} A =& \{x\in \mathbb{Z} : 1 \leq x\leq 2020, 4 \mid x \},\\ B =& \{x\in \mathbb{Z} : 1 \leq x\leq 2020, 5 \mid x \},\\ C =& \{x\in \mathbb{Z} : 1 \leq x\leq 2020, 6 \mid x \},\\ D =& \{x\in \mathbb{Z} : 1 \leq x\leq 2020, 9 \mid x \}. \end{align*}$

Diperoleh

$\begin{align*} |A| = \left\lfloor\frac{2020}{4} \right\rfloor = 505 ,&\qquad |C| = \left\lfloor\frac{2020}{6} \right\rfloor = 336,\\ |B| = \left\lfloor\frac{2020}{5} \right\rfloor = 404 ,&\qquad |D| = \left\lfloor\frac{2020}{9} \right\rfloor = 224,\\ |A \cap B| = \left\lfloor\frac{2020}{20} \right\rfloor = 101,&\qquad |B \cap C| = \left\lfloor\frac{2020}{30} \right\rfloor = 67,\\ |A \cap C| = \left\lfloor\frac{2020}{12} \right\rfloor = 168 ,&\qquad |B\cap D| = \left\lfloor\frac{2020}{45} \right\rfloor = 44,\\ |A \cap D| = \left\lfloor\frac{2020}{36} \right\rfloor = 56 ,&\qquad |C\cap D| = \left\lfloor\frac{2020}{18} \right\rfloor = 112,\\ |A \cap B \cap C| = \left\lfloor\frac{2020}{60} \right\rfloor = 33 ,&\qquad |A\cap C\cap D| = \left\lfloor\frac{2020}{36} \right\rfloor = 56,\\ |A \cap B \cap D| = \left\lfloor\frac{2020}{180} \right\rfloor = 11 ,&\qquad |B \cap C\cap D| = \left\lfloor\frac{2020}{90} \right\rfloor = 22 \end{align*}$

dan

$\begin{align*} |A \cap B \cap C \cap D| = \left\lfloor\frac{2020}{180} \right\rfloor = 11. \end{align*}$

Jadi banyaknya bilangan bulat $x,$ $1\leq x \leq 2020$ yang tidak habis dibagi $4,5,6$ dan $9$ adalah

$\begin{align*} |A^c \cap B^c \cap C^c \cap D^c|=& |\left(A \cup B \cup C \cup D \right)^c| \\ =& 2020 - (505+404+336+224-101-168-56\\ &\qquad \quad -67-44-112+33+11+56+22-11)\\ =& 2020-1032 \\ =&988. \end{align*}$

Tutorial: Soal Latihan dan Pembahasan Prinsip Inklusi dan Eksklusi

Artikel Terbaru

Komentar