logika matematika - blogs.unpas.ac.idblogs.unpas.ac.id/ririnda/files/2012/09/1himpunan2.pdflogika...
TRANSCRIPT
Logika Matematika Teori Himpunan
TEKNIK INFORMATIKA
UNIVERSITAS PASUNDAN
TAHUN AJARAN 2007/2008
Pertemuan ke-2
Oleh : Mellia Liyanthy
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
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
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
Prinsip Inklusi-Eksklusi
Berapa jumlah anggota di dalam gabungan dua buah himpunan ?
Prinsip Inklusi-Eksklusi
• 1
• 2
• 3
• 2 • 4
A B
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
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
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
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.
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’
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
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 } }
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.
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 }
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 }
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 }
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 }
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.
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
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.
Pembuktian dengan Diagram Venn
Contoh :
Buktikan A ∩ ( B U C ) = (A ∩ B ) U ( A ∩ C)
A B
C
S A B
C
S
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.
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
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.
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
Pembuktian dengan definisi
Tidak ada tahapan baku, perlu analisis
yang kuat, dapat dimulai dari operasi
himpunan yang terkecil.
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