logika matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1himpunan2.pdflogika...

28
Logika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008 Pertemuan ke-2 Oleh : Mellia Liyanthy

Upload: phamanh

Post on 20-Mar-2019

265 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Logika Matematika Teori Himpunan

TEKNIK INFORMATIKA

UNIVERSITAS PASUNDAN

TAHUN AJARAN 2007/2008

Pertemuan ke-2

Oleh : Mellia Liyanthy

Page 2: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Perampatan Operasi Himpunan

A1 ∩ A2 ∩ ... ∩ An = ∩ Ai

A1 U A2 U ... U An = U Ai

A1 x A2 x ... x An = x Ai

A1 A2 ... A3 = Ai

n

i =1

n

i =1

n

i = 1

n

i = 1

Page 3: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Perampatan Operasi Himpunan

Notasi perampatan dapat mempermudah

penulisan ekspresi yang panjang.

Contoh : A ∩ ( B1 U B2 U ... U Bn ) = (A ∩ B1) U (A ∩ B2) U ... U (A ∩ Bn)

menjadi :

A ∩ ( U Bi ) = U ( A ∩ Bi )

n

i = 1

n

i = 1

Page 4: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Perampatan Operasi Himpunan

Latihan :

A1 = { 2, 4, 6, 8 } A2 = { 1, 2, 3 }

A3 = { 2, 3, 5, 7 } A4 = { 0, 1, 2 }

maka : ∩ Ai dan U Ai adalah ... 4

i = 1

4

i = 2

Jawaban :

∩ Ai = A1 ∩ A2 ∩ A3 ∩ A4 = { 2 }

U Ai = A2 U A3 U A4 = { 0, 1, 2, 3, 5, 7 }

4

i = 1

4

i = 2

Page 5: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Prinsip Inklusi-Eksklusi

Berapa jumlah anggota di dalam gabungan dua buah himpunan ?

Page 6: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Prinsip Inklusi-Eksklusi

• 1

• 2

• 3

• 2 • 4

A B

Page 7: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Prinsip Inklusi-Eksklusi

• 1

• 2

• 3 • 4

A B

| A U B | = | A | + | B | - | A ∩ B |

= 3 + 2 – 1 = 4

Prinsip ini dikenal dengan nama prinsip inklusi-eksklusi

Page 8: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Prinsip Inklusi-Eksklusi

• 1

• 2

• 3 • 4

A B

| A B | = | A | + | B | - 2 | A ∩ B |

= 3 + 2 – 2(1) = 3

Prinsip ini dikenal dengan nama prinsip inklusi-eksklusi

Page 9: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Perampatan Prinsip Inklusi-Eksklusi

Secara umum untuk himpunan A1, A2, ... , An, berlaku :

| A1 U A2 U ... U An | = Σ | Ai | - Σ | Ai ∩ Aj | +

Σ | Ai ∩ Aj ∩ Ak | + ... +

( -1 ) | A1 ∩ A2 ∩ ... ∩ Ar | r-1

i 1 i r

1 i j k r

Page 10: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Prinsip Dualitas

Hukum yang diperoleh dari hukum yang lain

dengan cara mengganti :

∩ U

U ∩

Ø U

U Ø

dan membiarkan komplemen tetap seperti

semula. Prinsip ini dikenal dengan prinsip

dualitas.

Page 11: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Sifat-sifat Operasi Himpunan

1. Hukum identitas

- A U Ø = A

- A ∩ U = A

- A Ø = A

2. Hukum null

- A ∩ Ø = Ø

- A U U = U

- A A = Ø

3. Hukum komplemen

- A U A’ = U

- A ∩ A’ = Ø

4. Hukum involusi

- (A’)’ = A

5. Hukum idempoten

- A U A = A

- A ∩ A = A

6. Hukum penyerapan

- A U ( A ∩ B ) = A

- A ∩ ( A U B ) = A

7. Hukum komutatif

- A U B = B U A

- A ∩ B = B ∩ A

- A B = B A

8. Hukum De Morgan

- ( A ∩ B )’ = A’ U B’

- ( A U B )’ = A’ ∩ B’

Page 12: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Sifat-sifat Operasi Himpunan

9. Hukum Distributif

- A ∩ (B U C) = (A ∩ B) U (A ∩ C)

- A U (B ∩ C) = (A U B) ∩ (A U C)

10. Asosiatif

- A ∩ (B ∩ C) = (A ∩ B) ∩ C

- A U (B U C) = (A U B) U C

- A (B C) = (A B) C

11. Hukum 0/1

- U’ = Ø

- Ø’ = U

Page 13: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Partisi

Partisi dari sebuah himpunan A adalah sekumpulan

himpunan bagian tidak kosong A1, A2, ... dari A, sehingga :

- A1 U A2 U ... = A

- himpunan bagian Ai saling lepas Ai ∩ Aj = Ø untuk i ≠

j

Contoh :

A = { 1, 2, 3, 4, 5, 6, 7, 8 }, maka partisi dari A adalah ...

{ { 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 } }

Page 14: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Multiset Himpunan yang elemennya boleh berulang

disebut multiset.

Contoh :

A = { 1, 1, 2, 3, 3, 3, 3 }

Multiplisitas dari suatu elemen pada multiset

adalah jumlah kemunculan elemen tersebut pada

multiset.

Sehingga dari contoh di atas :

multiplisitas dari elemen 1 adalah 2,

multiplisitas dari elemen 2 adalah 1,

multiplisitas dari elemen 3 adalah 4.

Page 15: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Operasi pada multiset Gabungan

P U Q adalah suatu multiset yang

multiplisitas elemennya sama dengan

multiplisitas maksimum dari elemen

tersebut pada himpunan P dan Q.

Contoh :

P = { a, a, a, c, d, d }

Q = { a, a, b, c, c}, maka :

P U Q = { a, a, a, b, c, c, d, d }

Page 16: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Operasi pada multiset Irisan

P ∩ Q adalah suatu multiset yang

multiplisitas elemennya sama dengan

multiplisitas minimum dari elemen

tersebut pada himpunan P dan Q.

Contoh :

P = { a, a, a, c, d, d }

Q = { a, a, b, c, c}, maka :

P ∩ Q = { a, a, c }

Page 17: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Operasi pada multiset Selisih

P - Q adalah suatu multiset yang multiplisitas elemennya sama dengan :

- multiplisitas elemen tersebut pada himpunan P dikurangi multiplisitasnya pada Q, jika selisihnya positif

- 0, jika selisihnya 0 atau negatif.

Contoh :

P = { a, a, a, b, d, d }

Q = { a, a, b, c, c}, maka :

P - Q = { a, d, d }

Page 18: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Operasi pada multiset Penjumlahan

P + Q adalah suatu multiset yang

multiplisitas elemennya sama dengan

penjumlahan dari multiplisitas elemen

tersebut pada P dan Q.

Contoh :

P = { a, b, d, d }

Q = { a, a, b, c, c}, maka :

P + Q = { a, a, a, b, b, c, c, d, d }

Page 19: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Pembuktian Kalimat Himpunan

Kalimat himpunan adalah pernyataan

yang menggunakan notasi himpunan.

Kalimat himpunan dapat berupa

kesamaan himpunan, yang dapat

dibuktikan kebenarannya dengan

menggunakan beberapa metode.

Page 20: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Pembuktian Kalimat Himpunan

Metode-metode pembuktian kalimat :

1. Pembuktian dengan Diagram Venn

2. Pembuktian dengan menggunakan

tabel keanggotaan

3. Pembuktian dengan sifat operasi

himpunan

4. Pembuktian dengan menggunakan

definisi

Page 21: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Pembuktian dengan Diagram Venn

1. Buat diagram venn untuk bagian ruas

kiri dan ruas kanan dari kesamaan

kalimat tersebut.

2. Jika ternyata kedua diagram venn

tersebut sama, maka dapat

disimpulkan kesamaan kalimat

tersebut benar.

Page 22: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Pembuktian dengan Diagram Venn

Contoh :

Buktikan A ∩ ( B U C ) = (A ∩ B ) U ( A ∩ C)

A B

C

S A B

C

S

Page 23: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Pembuktian dengan Tabel Keanggotaan

1. Angka 1 untuk menyatakan bahwa

suatu elemen adalah anggota himpunan

(true), dan 0 untuk menyatakan bukan

himpunan (false).

2. Buat kolom untuk ruas kiri dan ruas

kanan.

3. Jika kedua kolom tersebut memiliki nilai

yang sama, maka dapat disimpulkan

kesamaan kalimat tersebut benar.

Page 24: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Pembuktian dengan Tabel Keanggotaan

Contoh :

Buktikan A ∩ ( B U C ) = (A ∩ B ) U ( A ∩ C)

A B C A ∩ ( B U C ) (A∩B)U(A∩C)

0 0 0 0 0

0 0 1 0 0

0 1 0 0 0

0 1 1 0 0

1 0 0 0 0

1 0 1 1 1

1 1 0 1 1

1 1 1 1 1

Page 25: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Pembuktian dengan Sifat Operasi Himpunan

Tidak ada tahapan baku, dilakukan

dengan mengubah bentuk ruas kiri

menjadi bentuk ruas kanan atau

sebaliknya dengan menggunakan sifat-

sifat operasi himpunan.

Page 26: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Pembuktian dengan Sifat Operasi Himpunan

Contoh :

Buktikan ( A ∩ B ) U (A ∩ B’ ) = A

(A ∩ B ) U ( A ∩ B’ ) = A ∩ ( B U B’ ) ... Hk.distributif

= A ∩ U ... Hk. Komplemen

= A ... Hk. identitas

Page 27: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Pembuktian dengan definisi

Tidak ada tahapan baku, perlu analisis

yang kuat, dapat dimulai dari operasi

himpunan yang terkecil.

Page 28: Logika Matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1Himpunan2.pdfLogika Matematika Teori Himpunan TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008

Pembuktian dengan Definisi

Contoh :

Jika ( A ∩ B ) = Ø dan A ( B U C ), maka A C.

Buktikan !

(i) Dari definisi himp.bagian : P Q, jika setiap x P

juga Q. Karena A ( B U C ), maka x A juga

( B U C )

(ii) Dari definisi operasi gabungan : x ( B U C ),

berarti x B atau x C.

(iii) Karena x A dan A ∩ B = Ø, maka x B.

(iv) Dari (i),(ii),(iii), Maka A C