himpunan - · pdf filecatatan: 1. jika a dan b merupakan ... himpunan mahasiswa yang...

HIMPUNANAdri Priadana

ilkomadri.com

Definisi

• Set atau Himpunan adalah bentuk dasar

matematika yang paling banyak

digunakan di teknik informatika

• Salah satu topik yang diturunkan dari

Himpunan adalah Class atau collection

Definisi

• Himpunan (set) adalah kumpulan objek-

objek yang berbeda.

• Objek di dalam himpunan disebut

elemen, unsur, atau anggota.

• BEM adalah contoh sebuah himpunan,

di dalamnya berisi anggota berupa

mahasiswa. Tiap mahasiswa berbeda

satu sama lain.

Notasi Himpunan

• Himpunan dinyatakan dg huruf capital

misal : A, B, G

• Sedangkan elemennya dg huruf kecil a,

b, c..,1,2,..

Penyajian Himpunan

1. Enumerasi

menyebutkan semua anggota dari himpunan tersebut.

contoh : Himpunan tiga bilangan ganjil pertama: A = {1,3,5}.

Keanggotaan Himpuan

x A : x merupakan anggota himpunan A;

x A : x bukan merupakan anggota himpunan A.

Contoh 1.

Misalkan: A = {1,3,5,8}, R = { a, b, {a, b, c}, {a, c} }, K = {{}}

maka

1 A,

{a, b, c} R, a R, sedangkan {a} R ,

{} K

Penyajian Himpunan

Contoh 2.

Misalkan: P1 = {a, b}, P2 = { {a, b} }, dan P3 = {{{a, b}}},

maka :

a P1

a P2

P1 P2

P1 P3

P2 P3

Penyajian Himpunan

2. Simbol Simbol Baku

Beberapa simbol baku pada himpunan

N = himpunan bilangan alami (asli) = { 1, 2, 3,... }

Z = himpunan bilangan bulat = { ..., -2, -1, 0, 1, 2, ... }

Q = himpunan bilangan rasional

R = himpunan bilangan riil

C = himpunan bilangan kompleks

sedangkan U menyatakan himpunan semesta.

Contoh: Misalkan U = {a, b, c, d, e} dan A adalahhimpunan bagian dari U, dengan A = {a, d, e}.

Penyajian Himpunan

3. Notasi Persyaratan

A = {x | syarat yang harus dipenuhi oleh x}

contoh :

A adalah himpunan bilangan asli yang lebih kecil dari 10

A = { x | x ≤ 10 dan x ∈ N } atau A = { x ∈ N | x ≤ 10 }

yang ekivalen dengan A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Penyajian Himpunan

4. Diagram Venn

untuk menyatakan relasi antar himpunan

Misal U = {1, 2, …, 7, 8}, A = {1, 2, 3, 5} dan B = {2,

5, 6, 8}.

maka notasi dalam diagram Venn:

U

1 2

53 6

8

4

7A B

Himpunan Berhingga (Finite Set)

• Himpunan yang mempunyai anggota berhingga

disebut himpunan berhingga (finite set)

• Sembarang himpunann yang anggotanya tak

berhingga disebut himpunan tak berhingga(infinite

set)

• contoh A={a,b,c,d,e,f} adalah finite set, sedangkan Z

adalah infinite set.

Kardinalitas

Misalkan A merupakan himpunan berhingga, maka

jumlah elemen berbeda di dalam A disebut kardinal

dari himpunan A. (menyatakan banyaknya anggota

dari himpunan)

Notasi: n(A) atau A

contoh :

(i) B = { x | x merupakan bilangan prima lebih kecil

dari 20}, atau B = {2, 3, 5, 7, 11, 13, 17, 19}

maka B = 8

(iii) A = {t, {t}, {{t}},{{{t}}} }, maka A = 4

Himpunan Kosong (null set)

• Himpunan yang tidak mempunyai anggota atau

kardinalitasnya = 0

• Contoh :

A ={x|x < x} , maka n(A)= 0

• Notasi : {} atau Ø

• {Ø} atau {{}} bukan himpunan kosong karena ia

memiliki satu elemen yaitu Ø atau {}

Himpunan Bagian (Subset)

Himpunan A disebut himpunan bagian (subset) dari

himpunan B jika dan hanya jika setiap anggota A

merupakan anggota dari B.

Dalam hal ini, B dikatakan superset dari A.

Notasi: A B

Diagram Venn:

U

AB

Himpunan Bagian (Subset)

Catatan :

A dan A A, maka dan A disebut himpunan

bagian tak sebenarnya (improper subset) dari himpunan

A.

Contoh: A = {a,b,c}, maka {a,b,c} dan adalah

improper subset dari A.

Himpunan Bagian (Subset)

Contoh.

(i) { a, b, c} {a, b, c, d, e}

(ii) { a, b, c} {a, b, c }

TEOREMA 1. Untuk sembarang himpunan A berlaku hal-hal

sebagai berikut:

(a) A adalah himpunan bagian dirinya sendiri (yaitu, A A).

(b) Himpunan kosong merupakan himpunan bagian dari setiap

himpunan (dalam hal ini A ( A)).

(c) Jika A B dan B C, maka A C

Himpunan Bagian (Subset)

Catatan :

A B tidak sama dengan A B

Pada :

A B : A adalah himpunan bagian dari B tetapi A B.

A adalah himpunan bagian sebenarnya (proper subset) dari B.

Contoh: {a} dan {b,c} adalah proper subset dari {a,b,c}

sedangkan :

A B : digunakan untuk menyatakan bahwa A adalah himpunan

bagian (subset) dari B yang memungkinkan A = B.

Himpunan yang Ekivalen

Himpunan A disebut ekivalen dengan himpunan B jika

dan hanya jika kardinal dari kedua himpunan tersebut

sama.

Notasi : A ~ B A = B

A = { 1,2,3,4} dan B = { ali, budi, joko,tuti }, maka

A ~ B sebab A = B = 4

Himpunan yang Sama

A = B jika dan hanya jika setiap anggota A merupakan

anggota B dan sebaliknya setiap anggota B merupakan

anggota A.. Jika tidak demikian, maka A B.

Notasi : A = B A B dan B A

Himpunan Kuasa Himpunan kuasa (power set) dari himpunan A adalah suatu himpunan

yang anggotanya merupakan semua himpunan bagian dari A,

termasuk himpunan kosong dan himpunan A sendiri.

Notasi : P(A) atau 2A

Jika A = m, maka P(A) = 2m.

Contoh 12.

Jika A = { 1, 2 }, maka P(A) = { , { 1 }, { 2 }, { 1, 2 }}

Contoh 13.

Himpunan kuasa dari himpunan kosong adalah P() = {}, dan

himpunan kuasa dari himpunan {} adalah P({}) = {, {}}.

Himpunan Saling Lepas

Dua himpunan A dan B dikatakan saling lepas (disjoint) jika keduanya

tidak memiliki anggota yang sama.

Notasi : A // B

Diagram Venn: U

A B

Contoh 11.

Jika A = { x | x P, x < 8 } dan B = { 10, 20, 30, ... }, maka A // B.

Operasi Terhadap Himpunan

1. Irisan (intersection)

Notasi : A B = { x x A dan x B }

Contoh

(i) Jika A = {a,b,c,d,e} dan B = {c,e,f,g}, maka A B = {c,e}

(ii) Jika A = { 1,2,3} dan B = { 4,5}, maka A B = . Artinya: A // B

Operasi Terhadap Himpunan2. Gabungan (union)

Notasi : A B = { x x A atau x B }

Contoh:

(i) Jika A = { a, b, c} dan B = { b,c,d,e }, maka A B = {

a,b,c,d,e }

(ii) A = A

Operasi Terhadap Himpunan

3. Komplemen (complement)

Notasi : A = { x x U, x A }

Contoh

Misalkan U = { 1, 2, 3, ..., 7 },

jika A = {1, 3, 4, 6}, maka A = {2, 5, 7}

Operasi Terhadap Himpunan

4. Selisih (difference)

Notasi : A – B = { x x A dan x B } = A B

Contoh.

(i) Jika A = { a, b, c,d,e,f} dan B = { c,d,f},

maka A – B = { a,b,e} dan B – A =

(ii) {1, 3, 5} – {1, 2, 3} = {5},

tetapi {1, 2, 3} – {1, 3, 5} = {2}

Operasi Terhadap Himpunan

5. Beda Setangkup (Symmetric Difference)

Notasi: A B = (A B) – (A B) = (A – B) (B – A)

Contoh 19.

Jika A = { 2, 4, 6 } dan B = { 2, 3, 5 }, maka A B = { 3, 4, 5, 6 }

Operasi Terhadap Himpunan

TEOREMA 2. Beda setangkup memenuhi sifat-sifat berikut:

(a) A B = B A (hukum komutatif)

(b) (A B ) C = A (B C ) (hukum asosiatif)

Contoh 20. Misalkan

U = himpunan mahasiswa

P = himpunan mahasiswa yang nilai ujian UTS di atas 80

Q = himpunan mahasiswa yang nilain ujian UAS di atas 80

Seorang mahasiswa mendapat nilai A jika nilai UTS dan

nilai UAS keduanya di atas 80, mendapat nilai B jika salah

satu ujian di atas 80, dan mendapat nilai C jika kedua ujian

di bawah 80.

(i) “Semua mahasiswa yang mendapat nilai A” : P Q

(ii) “Semua mahasiswa yang mendapat nilai B” : P Q

(iii) “Semua mahasiswa yang mendapat nilai C” : U – (P Q)

Operasi Terhadap Himpunan

6. Perkalian Kartesian (cartesian product)

Notasi: A B = {(a, b) a A dan b B }

Contoh.

(i) Misalkan C = { 1, 2, 3 }, dan D = { a, b }, maka

C D = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }

(ii) Misalkan A = B = himpunan semua bilangan riil, maka

A B = himpunan semua titik di bidang datar

Operasi Terhadap Himpunan

Catatan:

1. Jika A dan B merupakan himpunan berhingga,

maka: A B = A . B.

2. (a, b) (b, a).

3. A B B A dengan syarat A atau B tidak kosong.

Pada Contoh di atas, C = { 1, 2, 3 }, dan D = { a, b },

D C = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3) }

C D = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }

D C C D.

4. Jika A = atau B = , maka A B = B A =

Contoh. Misalkan

A = himpunan makanan = { s = soto, b = bakso, n = nasi

goreng, m = mie ayam}

B = himpunan minuman = { c = coca-cola, t = teh, d = es

jeruk}

Berapa banyak kombinasi makanan dan minuman yang dapat

disusun dari kedua himpunan di atas?

Jawab:

A B = AB = 4 3 = 12 kombinasi dan minuman,

yaitu {(s, c), (s, t), (s, d), (b, c), (b, t), (b, d), (n, c), (n, t), (n, d),

(m, c), (m, t), (m, d)}.

Perampatan Operasi Himpunan

n

iin

AAAA1

21...

n

iin

AAAA1

21...

i

n

inAAAA

121...

i

n

in

AAAA1

21...

Operasi himpunan dapat dilakukan terhadap 2 atau

lebih himpunan.

Dalam hal ini kita akan melakukan perampatan

(generalization) operasi himpunan.

Contoh :

A (B1B2 ... Bn) = (A B1) (A B2) ... (A Bn)

n

ii

n

ii

BABA11

)()(

Hukum yang Berlaku pada

Operasi Himpunan

Contoh Soal

Operasi Terhadap HimpunanDari 45 siswa, diketahui 27 siswa yang menyukai IPA dan

26 siswa menyukai IPS. Siswa yang tidak menyukai

keduanya ada 5 orang. Tentukanlah banyaknya siswa yang

menyukai IPA saja dan IPS saja!

Kita cari terlebih dahulu jumlah siswa yang menyukai kedua

pelajaran tersebut:

n(A ∩ B) = (n(A) + n(B)) - (n(U) – n(X))

n(A ∩ B) = (27 + 26) – (45 – 5)

n(A ∩ B) = 13

Maka dapat disimpulkan bahwa:

Siswa yang menyukai IPA saja = 27 - 13 = 14 siswa

Siswa yang menyukai IPS saja = 26 - 13 = 13 siswa

Prinsip Inklusi-Eksklusi

Ada berapa anggota dalam gabungan

dua himpunan hingga?

|A1 A2| = |A1| + |A2| - |A1 A2|

Contoh

Ada berapa bilangan bulat positif lebih kecil atau sama dengan

100 yang habis dibagi 6 atau 9?

Solusi :

Misalkan A: himpunan bilangan bulat dari 1 sampai 100 yang

habis dibagi 6

B: himpunan bilangan bulat dari 1 sampai 100 yang

habis dibagi 9.

Dengan menggunakan prinsip inklusi-eksklusi, banyaknya

bilangan bulat dari 1 sampai 100 yang habis dibagi 6 atau 9

adalah

2251116

18/1009/1006/100

||||||||

BABABA

Contoh

Misalkan ada 1467 mahasiswa angkatan 2004 di ITB. 97 orang di antaranya adalahmahasiswa TI, 68 mahasiswa SI, dan 12 orang mahasiswa double degree TI dan SI.

Ada berapa orang yang tidak kuliah di TI atauSI?

Solusi

Misalkan

A: himpunan mahasiswa angkatan 2004 di TI

B: himpunan mahasiswa angkatan 2004 di SI

Maka |A| = 97, |B| = 68, dan |AB| = 12.

Banyaknya mahasiswa angkatan 2004 di TI atau MI adalah

|A B| = |A| + |B| - |A B|= 97 + 68 – 12 = 153

Jadi, terdapat 1467 – 153 = 1314 mahasiswa angkatan2004 yang tidak kuliah di TI atau MI.

Perluasan Prinsip Inklusi-Eksklusi

untuk tiga himpunan

Angka 1 merah menunjukkan daerah yang terlibat ketika |A| dihitung,

angka 1 hijau menunjukkan daerah yang terlibat ketika |B| dihitung,dan

angka 1 biru menunjukkan daerah yang terlibat ketika |C| dihitung.

Terlihat bahwa daerah yang beririsan dihitung berulang-ulang.

|A B| dikurangkan (dua 1 merah diambil),

|A C| dikurangkan (dua 1 biru diambil), dan

|B C| dikurangkan (dua 1 hijau diambil) Terlihat bahwa penghitungan hampir benar, kecuali pada daerah di mana ketiga himpunan sama-sama beririsan. Maka perlu ditambahkan kembali |A B C|.

Perluasan Prinsip Inklusi-

Eksklusi untuk tiga himpunan

|A B C| = |A| + |B| + |C|

- |A B| - |A C| - |B C|

+ |A B C|

Perluasan Prinsip Inklusi-

Eksklusi untuk tiga himpunan

Sebanyak 115 mahasiswa mengambil mata kuliah

Matematika Diskrit, 71 Kalkulus, dan 56 Geometri.

Di antaranya, 25 mahasiswa mengambil

Matematika Diskrit dan Kalkulus, 14 Matematika

Diskrit dan Geometri, serta 9 orang mengambil

Kalkulus dan Geometri. Jika terdapat 196

mahasiswa yang mengambil paling sedikit satu dari

ketiga mata kuliah tersebut, berapa orang yang

mengambil ketiga mata kuliah sekaligus?

Solusi

Misalkan

MD: himpunan mahasiswa yang mengambil mata kuliah Matematika

Diskrit,

K: himpunan mahasiswa yang mengambil mata kuliah Kalkulus, dan

G: himpunan mahasiswa yang mengambil mata kuliah Geometri.

Maka

|MD| = 115, |KPB| = 71, |G| = 56,

|MD K| = 25, |MD G| = 14, |K G| = 9, dan

|MD K G| = 196

Dengan mempergunakan prinsip inklusi-eksklusi:

|MDKPBG| = |MD| + |K| + |G| - |MDK| - |MDG| - |KG|

+ |MDKG|

196 = 115 + 71 + 56 - 25 - 14 - 9 + |MD K G|

Jadi, |MD KPB G| = 2

Prinsip Inklusi-Eksklusi

Teorema 1.

Misalkan A1, A2, …, An himpunan hingga.

Maka

||)1(||

||||||

21

1

1

11

221

n

n

kj

nkji

i

j

nji

i

ni

i

AAAAAA

AAAAAA

Contoh 4 Himpunan

|ABCD| = |A| + |B| + |C| + |D| -

|AB| - |AC| - |AD| - |BC| - |BD|- |CD|

+ |ABC|+ |ABD|+ |ACD|+ |BCD|

- |A B C D|

Matur Nuwun