INF-104 Matematika Diskrit

Pendahuluan Himpunan

INF-104 Matematika Diskrit Himpunan

[email protected] Jurusan Informatika FMIPA Unsyiah

February 13, 2012

[email protected]

INF-104 Matematika Diskrit


Apakah Matematika Diskrit Itu?

Matematika diskrit: cabang matematika yang mengkaji objek-objek diskrit. ”Apa yang dimaksud dengan kata diskrit (discrete)? Objek disebut diskrit jika: terdiri dari sejumlah berhingga elemen yang berbeda dan elemen-elemennya tidak bersambungan (unconnected). Contoh: himpunan bilangan bulat (integer) Lawan kata diskrit adalah kontinyu (continue). Contoh: himpunan bilangan riil (real)

[email protected]



Pengertian

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]



Pengertian

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]



Pengertian

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]



Pengertian

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 }.

[email protected]



Pengertian

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]



Pengertian

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 subhimpunan dari setiap himpunan.

[email protected]



Pengertian

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]



Pengertian

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]



Pengertian

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]



Pengertian

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 A0 , adalah himpunan A0 = {x : x ∈ U dan x 6∈ A}.

[email protected]



Pengertian

Selanjutnya kita definisikan selisih (difference) dari dua himpuan A dan B sebagai A − B = A ∩ B 0 = {x : x ∈ A dan x 6∈ B}.

[email protected]



Pengertian

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]



Pengertian

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]



Pengertian

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]



Pengertian

(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]



Pengertian

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]



Pengertian

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]



Pengertian

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]


INF-104 Matematika Diskrit

Recommend Documents