Pertemuan ke-2
Logika Matematika Teori Himpunan Oleh : Mellia Liyanthy
TEKNIK INFORMATIKA UNIVERSITAS PASUNDAN TAHUN AJARAN 2007/2008
Perampatan Operasi Himpunan n
A1 ∩ A2 ∩ ... ∩ An = ∩ Ai i =1 n
A1 U A2 U ... U An = U Ai i =1 n
A1 x A2 x ... x An =
x Ai
i=1 n
A1 A2 ... A3 = Ai 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 : n
A∩(
U
i=1
n
Bi ) =
U
( A ∩ Bi )
i=1
Perampatan Operasi Himpunan Latihan : A1 = { 2, 4, 6, 8 } A3 = { 2, 3, 5, 7 } 4
maka :
∩
i=1
A2 = { 1, 2, 3 } A4 = { 0, 1, 2 } 4
Ai dan
U Ai i=2
adalah ...
Jawaban : 4
∩ Ai = A1 ∩ A2 ∩ A3 ∩ A4 = { 2 }
i=1 4
U Ai = A2 U A3 U A4 = { 0, 1, 2, 3, 5, 7 } i=2
Prinsip Inklusi-Eksklusi Berapa jumlah anggota di dalam gabungan dua buah himpunan ?
Prinsip Inklusi-Eksklusi A
B
•1 •2
•3
•2
•4
Prinsip Inklusi-Eksklusi B
A •1
•2 •3
•4
|AU B|=|A|+|B|-|A∩B| =3+2–1 =4
Prinsip ini dikenal dengan nama prinsip inklusi-eksklusi
Prinsip Inklusi-Eksklusi B
A •1
•2 •3
•4
|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 | - Σ
1ir
i
Σ
1ijkr
( -1 )
| Ai ∩ Aj | +
| Ai ∩ Aj ∩ Ak | + ... + r-1
| A1 ∩ A2 ∩ ... ∩ Ar |
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 - AUØ=A - A∩U=A - AØ=A 2. Hukum null - A∩Ø=Ø - AUU=U - AA=Ø 3. Hukum komplemen - A U A’ = U - A ∩ A’ = Ø 4. Hukum involusi - (A’)’ = A
5. Hukum idempoten - AUA=A - A∩A=A 6. Hukum penyerapan - AU(A∩B)=A - A∩(AUB)=A 7. Hukum komutatif - AUB=BUA - A∩B=B∩A - AB=BA 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.
2.
Buat diagram venn untuk bagian ruas kiri dan ruas kanan dari kesamaan kalimat tersebut. 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) S
A
B
C
S
A
B
C
Pembuktian dengan Tabel Keanggotaan 1.
2.
3.
Angka 1 untuk menyatakan bahwa suatu elemen adalah anggota himpunan (true), dan 0 untuk menyatakan bukan himpunan (false). Buat kolom untuk ruas kiri dan ruas kanan. 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
A∩(BUC)
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 sifatsifat 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)
(ii)
(iii) (iv)
Dari definisi himp.bagian : P Q, jika setiap x P juga Q. Karena A ( B U C ), maka x A juga (BUC) Dari definisi operasi gabungan : x ( B U C ), berarti x B atau x C. Karena x A dan A ∩ B = Ø, maka x B. Dari (i),(ii),(iii), Maka A C
