INF-104 Matematika Diskrit

Teori Himpunan

INF-104 Matematika Diskrit Teori Himpunan

[email protected] Jurusan Informatika FMIPA Unsyiah

February 25, 2015

[email protected]

INF-104 Matematika Diskrit

Teori Himpunan

Pengertian Operasi pada himpunan

Himpunan (set) adalah koleksi dari objek-objek yang terdefinisikan dengan baik. Terdefinisikan dengan baik dimaksudkan bahwa untuk sebarang objek x yang diberikan dapat kita tentukan apakah objek x tersebut kepunyaan dari suatu himpunan atau bukan. Objek yang merupakan kepunyaan dari suatu himpunan disebut elemen atau anggota. Kita akan nyatakan himpunan dengan huruf besar, seperti A atau X dan elemen dengan huruf kecil, seperti a atau x. Jika a adalah elemen dari himpunan A, kita tulis a ∈ A dan jika a adalah bukan elemen dari himpunan A, kita tulis a ∈ / A.

[email protected]


Teori Himpunan


Himpunan dapat dinyatakan dengan mendaftarkan semua elemennya di dalam sepasang tanda kurung atau dengan menyatakan sifat-sifat keanggotaannya sehingga dapat ditentukan apakah suatu objek adalah elemen dari suatu himpunan atau bukan. Kita dapat tuliskan X = {x1 , x2 , · · · , xn } untuk himpunan yang memuat elemen-elemen x1 , x2 , · · · , xn atau X = {x|x memenuhi ℘} jika setiap x di dalam X memenuhi suatu sifat tertentu dari ℘.

[email protected]


Teori Himpunan


jika E adalah himpunan bilangan bulat genap, kita dapat nyatakan E dengan menuliskan ke dalam salah satu notasi E = {2, 4, 6, · · · } atau E = {x|x adalah bilangan bulat genap dan x > 0}. Kita tuliskan 2 ∈ E bila kita ingin mengatakan bahwa 2 adalah elemen dari E, dan −3 6∈ E untuk mengatakan bahwa −3 adalah bukan elemen dari E.

[email protected]


Teori Himpunan


Berikut ini adalah beberapa himpunan penting yang akan sering digunakan dalam pembahasan kita selanjutnya: N = {n|n adalah bilangan asli } = {1, 2, 3, · · · }; Z = {n|n adalah bilangan bulat } = {· · · , −2, −1, 0, 1, 2, · · · }; Q = {r|r adalah bilangan rasional } = { pq |p, q ∈ Z dimana q 6= 0}; R = {x|x adalah bilangan real }; C = {z|z adalah bilangan kompleks }. R+ = {x|x adalah bilangan real positif }; R∗ = {x|x adalah bilangan real tak nol};

[email protected]


Teori Himpunan


Kita dapat menemukan berbagai relasi antara himpunan-himpunan dan juga dapat melakukan operasi-operasi pada himpunan. Himpunan A adalah subhimpunan (subset) dari B, ditulis A ⊆ B atau B ⊇ A, jika setiap elemen dari A juga elemen dari B. Sebagai contoh, {4, 5, 8} ⊆ {2, 3, 4, 5, 6, 7, 8, 9} dan N⊆Z⊆Q⊆R⊆C

[email protected]


Teori Himpunan


Jika A ⊆ B dan B memuat elemen yang bukan elemen dari A maka A disebut subhimpunan sejati (proper subset) dari B dan dinotasikan A ⊂ B. Kita juga akan menemukan suatu himpunan tanpa unsur-unsur di dalamnya. Himpunan yang seperti ini disebut himpunan kosong (empty set) dan dinotasikan dengan {} atau ∅. Sebagai catatan bahwa himpunan kosong adalah sub-himpunan dari setiap himpunan.

[email protected]


Teori Himpunan


Banyaknya elemen suatu himpunan A disebut sebagai kardinalitas (cardinality) atau ukuran (size) dan dinotasikan dengan |A| atau n(A) atau card(A). Suatu himpunan disebut berhingga (finite) jika memiliki kardinalitas yang berhingga. Suatu himpunan disebut takberhingga (infinite) jika memiliki kardinalitas yang takberhingga (dinotasikan oleh ℵ0 . Suatu himpunan disebut takterhitung (uncountable) jika himpunan tersebut bukan himpunan terhitung.

[email protected]


Teori Himpunan


Untuk memperoleh sebuah himpunan baru dari himpunan-himpunan yang telah ada, kita dapat melakukan operasi-operasi tertentu: gabungan (union) A ∪ B dari himpunan A dan B didefinisikan sebagai A ∪ B = {x|x ∈ A atau x ∈ B; } irisan (intersection) A ∩ B dari himpunan A dan B didefinisikan sebagai A ∩ B = {x|x ∈ A dan x ∈ B.} Jika A = {1, 3, 5} dan B = {1, 2, 3, 9}, maka A ∪ B = {1, 2, 3, 5, 9} dan A ∩ B = {1, 3}. [email protected]


Teori Himpunan


Untuk kasus dimana gabungan dan irisan melibatkan lebih dari dua himpunan yaitu A1 , A2 , · · · , An , maka untuk gabungan dan irisan secara berurutan kita tuliskan sebagai n [

Ai = A1 ∪ A2 ∪ · · · An

i=1

dan

n \

Ai = A1 ∩ A2 ∩ · · · An

i=1

[email protected]


Teori Himpunan


Jika dua buah himpunan tidak memiliki elemen yang sama maka kedua himpunan tersebut dikatakan saling lepas (disjoint). Sebagai contoh, jika E himpunan bilangan bulat genap dan O himpunan bilangan bulat ganjil, maka E dan O adalah saling lepas. Dua buah himpunan A dan B adalah saling lepas jika A ∩ B = ∅.

[email protected]


Teori Himpunan


Kadang-kadang kita akan bekerja dalam suatu himpunan tertentu U yang disebut dengan himpunan semesta (universal set). Untuk setiap himpunan A ⊆ U , kita definisikan komplemen (complement) dari A, dinotasikan dengan A atau A0 , adalah himpunan A = {x|x ∈ U dan x 6∈ A}.

[email protected]


Teori Himpunan


Selanjutnya kita definisikan selisih (difference) dari dua himpuan A dan B sebagai A − B = A ∩ B 0 = {x|x ∈ A dan x 6∈ B} dan selisih simetrik (symmetric difference) dari dua himpuan A dan B sebagai A4B = {x|(x ∈ A∨x ∈ B)∧x ∈ / A∩B} = {x|(x ∈ A∪B)∧x ∈ / A∩B}.

[email protected]


Teori Himpunan


Contoh Misalkan R adalah himpunan semesta dan anggap bahwa bahwa A = {x ∈ R|0 < x ≤ 3} dan B = {x ∈ R|2 ≤ x < 4} maka A ∩ B = {x ∈ R|2 ≤ x ≤ 3} A ∪ B = {x ∈ R|0 < x < 4} A − B = {x ∈ R|0 < x < 2} A0 = {x ∈ R|x ≤ 0 atau x > 3}

[email protected]


Teori Himpunan


Berikut ini adalah beberapa sifat penting operasi gabungan dan irisan: 1

A ∪ A = A, A ∩ A = A, dan A − A = ∅;

2

A ∪ ∅ = A dan A ∩ ∅ = ∅;

3

A ∪ (B ∪ C) = (A ∪ B) ∪ C dan A ∩ (B ∩ C) = (A ∩ B) ∩ C;

4

A ∪ B = B ∪ A dan A ∩ B = B ∩ A;

5

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C);

6

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

[email protected]


Teori Himpunan


Disini akan dibuktikan hasil (1) dan (3), sisanya sebagai latihan. (1) Perhatikan bahwa A ∪ A = {x|x ∈ A atau x ∈ A} = {x|x ∈ A} = A dan A ∩ A = {x|x ∈ A dan x ∈ A} = {x|x ∈ A} = A Juga, A − A = A ∩ A0 = ∅.

[email protected]


Teori Himpunan


(3) Untuk himpunan A, B dan C, A ∪ (B ∪ C) = A ∪ {x|x ∈ B atau x ∈ C} = {x|x ∈ A atau x ∈ B, atau x ∈ C} = {x|x ∈ A atau x ∈ B} ∪ C = (A ∪ B) ∪ C. Dengan langkah yang sama dapat ditunjukkan bahwa A ∩ (B ∩ C) = (A ∩ B) ∩ C.

[email protected]


Teori Himpunan


Teorema berikut ini dikenal sebagai Hukum De Morgan’s. Teorema Misalkan A dan B adalah himpunan-himpunan maka 1

(A ∪ B)0 = A0 ∩ B 0 ;

2

(A ∩ B)0 = A0 ∪ B 0 .

[email protected]


Teori Himpunan


Kita harus tunjukkan bahwa (A ∪ B)0 ⊆ A0 ∩ B 0 dan (A ∪ B)0 ⊇ A0 ∩ B 0 . Misalkan x ∈ (A ∪ B)0 maka x 6∈ A ∪ B. Dari definisi gabungan himpunan, maka x bukan elemen dari A dan juga bukan elemen dari B. Dari definisi komplemen x ∈ A0 dan x ∈ B 0 . Sehingga x ∈ A0 ∩ B 0 dan kita peroleh (A ∪ B)0 ⊆ A0 ∩ B 0 . Untuk menunjukkan dalam arah sebaliknya, andaikan bahwa x ∈ A0 ∩ B 0 . Maka x ∈ A0 dan x ∈ B 0 , sehingga x 6∈ A dan x 6∈ B. Jadi x 6∈ A ∪ B dan diperoleh x ∈ (A ∪ B)0 . Dengan demikian (A ∪ B)0 ⊇ A0 ∩ B 0 sehingga (A ∪ B)0 = A0 ∩ B 0 .

[email protected]


Teori Himpunan


Contoh Buktikan bahwa (A − B) ∩ (B − A) = ∅ Perhatikan bahwa (A − B) ∩ (B − A) = (A ∩ B 0 ) ∩ (B ∩ A0 ) = A ∩ A0 ∩ B ∩ B 0 = ∅.

[email protected]


Teori Himpunan


Contoh Tentukan himpunan A dan B dimana memenuhi A − B = {1, 3, 7, 11}, B − A = {2, 6, 8} dan A ∩ B = {4, 9}. Jawab: Karena A = (A − B) ∪ (A ∩ B) maka kita peroleh bahwa A = {1, 3, 7, 11} ∪ {4, 9} = {1, 3, 4, 7, 9, 11}. Dengan cara yang sama B = (B − A) ∪ (A ∩ B) = {2, 6, 8} ∪ {4, 9} = {2, 4, 6, 8, 9}.

[email protected]


INF-104 Matematika Diskrit

Recommend Documents