• Beranda
  • PRINSIP INKLUSI DAN EKSKLUSI

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