Matematika Diskrit 03

MATEMATIKA DISKRIT (Catatan Kuliah 05 Desember 2009 )

Operasi Dengan Kumpulan Dari dua kumpulan A dan B dapat dibangun kumpulan baru dengan gabungan irisan dan selisih. Definisi : 1. Gabungan A dan B = A U B , (A gabungan B) Artinya : A U B = {x | x ∈ Aataux ∈ B} A

B

2. Persekutuan (irisan) A dan B = A I B , (A irisan B) Artinya : A I B = {x | x ∈ A dan x ∈ B} A

B

3. Selisih dari A dan B (komplemen B terhadap A) = AB Artinya : A – B = {x | x ∈ A dan x ∉ B} A

B

4. Kumpulan dimana terbentuk kumpulan-kumpulan bagian dari gabungan persekutuan komplemen maupun kombinasinya disebut Universe (semesta). Kumpulan dari Universe disebut kumpulan Universe U Definisi : 1. Bila A = U, maka A – B = Bc (komplemen dari B) m 2. Bila A1 UA2 UA3 ...UAm ditulis U = U AK K=1

A1 = A1 UA2 UA3 ...UAm A2

A3

m

U=

U AK

K=1

3. Bila A1 I A2 I A3 ... I Am ditulis U =

m

I AK

K=1

A1 A2

Page 1 of 7

3

A3

U = I AK K=1

www.joshaxis.co.cc

MATEMATIKA DISKRIT (Catatan Kuliah 05 Desember 2009 )

Contoh : A = {1, 2, 3, 4} dan B = {2, 3, 4, 5, 7} Ditanyakan : 1. A U B 2. A I B dan 3. A – B Jawab : 1. A U B = {x |x ∈ A atau x ∈ B } = {1, 2, 3, 4, 5, 7}

∈ dibaca anggota

2. A I B = {x |x ∈ A atau x ∈ B } = {2, 4} 3. A – B = {x |x ∈ A atau x ∉ B } = {1, 3} (misal B – A maka jadinya = {5, 7})

THEOREMA Untuk setiap kumpulan A, B, dan C berlaku : (a) A U B = B U A (sifat komutatif untuk gabungan) (b) A I B = B I A (sifat komutatif untuk irisan) (c) A U (B U C ) = ( A U B ) U C (sifat asosiatif untuk gabungan) (d) A I (B I C ) = ( A I B ) I C (sifat asosiatif untuk irisan) (e) A U (B I C ) = ( A U B ) I ( A U C ) (sifat distributif dari gabungan terhadap irisan) (f) A I (B U C ) = ( A I B ) U ( A I C ) (sifat distributif dari irisan terhadap gabungan) Pembuktian sifat ini : (a) Ilustrasi : akan dibuktikan A U B = B U A Ambil x ∈ A U B , x = sembarang x ∈ A U B = x ∈ A atau x ∈ B x ∈ B atau x ∈ A x ∈ BU A Karena x ∈ A U B mengakibatkan x ∈ B U A Jadi A U B = B U A (b) A I B = B I A Bukti : Ambil x ∈ A I B , x = sembarang x ∈ A I B = x ∈ A atau x ∈ B x ∈ B atau x ∈ A x ∈ BI A Karena x ∈ A I B mengakibatkan x ∈ B I A Jadi A I B = B I A (c) A U (B U C ) = ( A U B ) U C Bukti : x ∈ A U (B U C ) , x = sembarang x ∈ A U (B U C ) artinya x ∈ A atau x ∈ B U C dan

Page 2 of 7

www.joshaxis.co.cc

MATEMATIKA DISKRIT (Catatan Kuliah 05 Desember 2009 )

(x ∈ B atau x ∈ C) atau x ∈ A

x ∈ B U C atau x ∈ A

x ∈ A atau x ∈ B atau x ∈ C x ∈ A U B atau x ∈ C x ∈ ( AU B )UC Karena x ∈ A U (B U C ) mengakibatkan x ∈ ( A U B ) U C Jadi A U (B U C ) = ( A U B ) U C Jika A = {1, 2, 3}, B = {2, 3, 4, 5}, C = {4, 5, 6, 7, 8} periksa theorema d, e, dan f diatas adalah : (d) A I (B I C ) = {1, 2, 3} I {4, 5}= ∅ ( A I B ) I C = {2,3} I {4,5,6,7,8} = ∅

∅ artinya kosong

Jadi A I (B I C ) = ( A I B ) I C (e) A U (B I C ) = ( A U B ) I ( A U C ) = {1, 2, 3} U {4,5} = {1, 2, 3, 4, 5} I {1, 2, 3, 4, 5, 6, 7, 8} {1, 2, 3, 4, 5} = {1, 2, 3, 4, 5} Jadi A U (B I C ) = ( A U B ) I ( A U C ) (f) 1) A I (B U C ) = {1, 2, 3} I {2, 3, 4, 5, 6, 7, 8} = {2, 3} 2)

(A I B) U ( A I C ) =

{2, 3} U ∅ = {2, 3}

Jadi karena 1) = 2) maka A I (B U C ) = ( A I B ) U ( A I C ) Latihan dan Contoh : 1. Tulislah kumpulan-kumpulan berikut dengan metoda pendaftaran atau perincian atau keduanya a) Kumpulkan bilangan asli ≤ 20 dan habis dibagi 3

Page 3 of 7

www.joshaxis.co.cc

MATEMATIKA DISKRIT (Catatan Kuliah 05 Desember 2009 )

b) Kumpulkan semua pecahan dengan pembilang 1 dan penyebut semua bilangan asli ≤ 7 Penyelesaian : a) A = {3, 6, 9, 12, 15, 18} = { x | x = 3m, M = 1, 2, 3, 4, 5, 6} Atau bisa juga ditulis Metode Roster Metode Pencirian M=1,6 (1 sampai 6) b) B = {1/7, 1/6, 1/5, 1/4, 1/3, 1/2} = { x | x = 1/m, M = 2, 3, 4, 5, 6, 7} Atau bisa juga ditulis X = m/m Pembilang, Penyebut M=2, 7 (2 sampai 7)

2. Nyatakan kumpulan berikut dengan metoda pencirian a) A = {1, 4, 9, 16, 25, 36, 49} b) B = {1, 4, 7, 10, 13, 16, 19, 21} c) C = {2, 4, 8, 16, 32, 64, 128} d) D = {3, 5, 7, 11, 13, 17, 23} e) E = {pencil, ballpoint, spidol, kapur tulis}

GRAPHS DAN DIGRAPHS Graphs

Digraphs

1

2

1

2

Ilustrasi : Graphs terdiri dari titik-titik (vertias) dan garis hubung (edges). Vertias menyatakan kota, orang. Dan Edges menyatakan jalan raya, hubungan, bisnis. Contoh : 1) Empat kota dan lima jalan raya E1 E2

1

2

E3

4

E4

E5 3

Page 4 of 7

www.joshaxis.co.cc

MATEMATIKA DISKRIT (Catatan Kuliah 05 Desember 2009 )

2) Isolated, Vertex, Loop, Double Edge - Loop

- Isolated Vertex

- Double Edge

Definisi: Suatu graphs (simbolnya G) terdiri dari kumpulan hingga. Kumpulan titik-titik V disebut Vertias dan kumpulan E dari garis-garis disebut Edges. Masing-masing Edges menghubungkan dua Vertias, disebut Endpoints dari Edges Tulis G = (V, E) V = {V1, V2, V3, ...} E = {E1, E2, E3, ...} Aplikasi Graphs : Electical Engineering Civid Engineering Chemistry Economics

: : : :

Networks Structure Moolecular Structure Organizational Structures, Sociograms, Read Maps, Telecommunications, network, etc

Digraph (directed graph) : Difinisi : Digraph G = (V, E) adalah graph di mana masing-masing E = (i, j) mempunyai arah dari “initial point” i ke “terminal point” j

initial point i

j

j

i terminal point

Page 5 of 7

www.joshaxis.co.cc

MATEMATIKA DISKRIT (Catatan Kuliah 05 Desember 2009 )

E1

1

2

E7

E5

E1 = (1, 2) E2 = (2, 4) E3 = (4, 3) E4 = (3, 4) E5 = (1, 3) E6 = (4, 1)

E2 E6

E4 E3

3

4

Graph dan Digraph, representasi, komputer Ilustrasi : macam-macam sketsa dari graph yang sama A

B 8

5 1

1

4

2

4

C

3 6

2

7

3

1

4

2

3

8

5

7

6

7

6

8

5

Adjacency (Matrik Sekawan) Matrik A = [a, i, j] dari satu graph G adalah : 1 jika G mempunyai edge (i, j) a, i, j = 0 selain itu Contoh : 1

2

3

4

Page 6 of 7

Vertex Vertex 1 2 3 4

1 0 1 0 1

2 1 0 1 1

3 0 1 0 1

4 1 1 1 0

Matriknya : 0101 1011 0101 1110

www.joshaxis.co.cc

MATEMATIKA DISKRIT (Catatan Kuliah 05 Desember 2009 )

A = [ a, i, j] a i j = entry i = baris j = kolom Contoh : 123 A = 0 4 1 = ukuran 3 x 3 111 Baris

kolom

B = 1 2 3 = ukuran 2 x 3 041

Bentuk umum ukuran m x m : A = a11 a12... am a21 a22...am . . . Am1 am2... amm

[ Terima kasih \

Page 7 of 7

www.joshaxis.co.cc