matematika diskrit - materi 2

Matematika Diskrit

Teori Himpunan

Materi1. Logika2. Teori Himpunan3. Matriks4. Relasi dan fungsi5. Induksi matematik6. Algoritma7. Teori Bilangan bulat8. Baris dan deret9. Teori Grup dan Ring10. Aljabar Boolean11. Kombinatorial12. Teori Peluang Diskrit13. Fungsi Pembangkit dan Analisa Rekurens14. Teori Graf (termasuk Tree)15. Kompleksitas Algoritma16. Pemodelan Komputasi (Otomata dan Teori Bahasa Formal)

Operasi Logika di dalam Komputer

Bahasa pemrograman untuk logika berupa tipeBoolean yang hanya mempunyai dua buahkonstanta nilai yaitu True dan False.

Operator boolean yang digunakan dalampemrograman adalah AND, OR, XOR dan NOT.

Operasi Boolean hanya menghasilkan nilai true atau false

Inferensi

Inferensi : proses penarikan kesimpulan dari beberapa proposisi

1. Modus Ponen

p q (p (p q)) qp

q

Simbol dibaca sebagai jadi atau karena itu.

Modus ponen menyatakan bahwa jika hipotesis p dan implikasip q benar, maka konklusi q benar

Contoh :Jika 20 habis dibagi 2, maka 20 adalah bil. Genap20 habis dibagi 2

20 adalah bil genap

Inferensi diatas adalah benar

Inferensi

2. Modus Tollen

p q (q (p q)) pq

p

Contoh :Jika n bil. Ganjil, maka n2 bernilai ganjiln2 bernilai genap

n bukan bil. Ganjil


Inferensi

3. Silogisme Hipotesis

p q [(p q) (q r)] (p r)q r

p r

Contoh :Jika saya belajar dengan giat, maka saya lulus ujianJika saya lulus ujian, maka saya cepat menikah

Jika saya belajar dengan giat, maka saya cepat menikah


Inferensi

4. Silogisme Disjungtif

p q [(p q) p ] qp

q

5. Simplifikasi

p q (p q) q p

6. Penjumlahan

p p (p q) p q

Inferensi

7. Konjungsi

p [(p) (q)) (p q)q

(p q)

Argumen

Argumen adalah suatu deret proposisi yang ditulis sbb:A1 A1, A2, , An : HipotesisA2 B : konklusi..An

B

Sebuah argumen dikatakan valid jika konklusi benarbilamana semua hipotesisnya benar (termasuktautologi)

Sebuah argumen dikatakan invalid jika konklusi salahbilamana semua hipotesisnya salah

ArgumenContoh : Perhatikan argumen berikut

Jika air laut surut setelah gempa dilaut, maka tsunami datang.Air laut surut setelah gempa dilaut. Karena itu tsunami datang

p = air laut surut setelah gempa dilautq = tsunami datang

Argumen ditulis :A1 p q A2 pB q

Lihat pada baris 1.Hipotesis 1 (p q) bernilai THipotesis 2 (p) bernilai TKonklusi (q) bernilai T

Argumen diatas Valid

Baris 1Baris 2Baris 3Baris 4

Himpunan Terminologi dasar tentang sekumpulan objek diskrit Mengelompokkan objek secara bersama-sama Kumpulan objek-objek yang bebeda Kumplan objek tak tertentu

Penyajian Himpunan1. Enumerasi

menulis semua elemen himpunan yang bersangkutan dianatara dua buah tanda kurungkurawal.

Contoh :Himpunan A yang berisi empat anggota 1,2,3 dan 4 dilukis sebagai A = {1,2,3,4}.

Himpunan

x A : x anggota himpunan Ax A : x bukan anggota himpunan A

Contoh :A = {1, 2, 3, 4}R = {a, b, {a,b,c}, {a,c}}K = { {} }

3 A5 A{a,b,c} R

{a} Ra R{} K

Himpunan2. Simbol-simbol Baku

P = himpunan bil. Bulat positif = {1,2,3, } N = himpunan bil. Asli = {1,2,} Z = himpunan bil. Bulat = {, -1, 0, 1, } Q = himpunan bil. Rasional R = himpunan bil. Riil C = himpunan bil. Kompleks U = himpunan universal (semesta)

Contoh :U = {1, 2, 3, 4, 5}A = {1, 3, 5}

A adalah himpunan bagian dari U

Himpunan

3. Notasi Bentuk HimpunanNotasi : { x | syarat yang harus dipenuhi oleh x}

dibaca : dimana atau sedemikian sehingga Tanda , dibaca sebagai dan

Contoh :A adalah himpunan bilangan genap positif yang lebihkecil atau sama dengan 8.A = {x|x adalah himpunan bil. Genap positif lebih

kecil atau sama dengan 8AtauA = {x| x/2 P, 2 x 8}

Himpunan

4. Diagram Venn

U = {1, 2, 3, 4, 5, 6, 7, 8}A = {1, 2, 3, 5}B = {2, 5, 6, 8}

Kardinalitas

Kardinalitas : jumlah elemen berbeda di dalamhimpunan berhingga.

Notasi : n(A) atau |A|

Contoh :A = {x|x merupakan bil. Prima yang lebih kecil dari 20}|A| = 8

B = {kucing, a, Amir, 10, paku}|B| = 5

Himpunan Kosong

Himpunan kosong : himpunanyang tidak memiliki satupunelemen atau himpunan dengankardinalitas = 0

Notasi : atau {}

P = {Orang Indonesia yang pernah ke bulan}

|P| = 0

Himpunan Bagian(Subset)

Himpunan A dikatakan Subsetdari himpunan B, jika danhanya jika setiap elemen A merupakan elemen dari B.

B disebut superset dari A

Notasi : A B

Himpunan Yang Sama

Himpunan A dikatakan samadengan himpunan B jika danhanya jika keduanyamempunyai elemen yang sama.

Notasi :

A = B A B dan B A

Himpunan yang Ekuivalen

Himpunan A dikatakanEkuivalen dengan Himpunan B jika dan hanya jika cardinal dari kedua himpunan tersebutsama.

Notasi :

A ~ B |A| = |B|

Himpunan SalingLepas

Dua himpunan A dan B dikatakan saling lepas jikakeduanya tidak memilikielemen yang sama.

Notasi :

A // B

Himpunan Kuasa

Himpunan Kuasa (power set) dari himpunan A adalah suatuhimpunan yang elemennyamerupakan semua himpunanbagian dari A, termasukhimpunan kosong danhimpunan A sendiri

Notasi :

(A) atau 2A

Contoh : Jika A = {1,2}, maka(A) = { , {1}, {2}, {1,2}}

Irisan (Intersection)

Irisan (intersection) darihimpunan A dan B adalahhimpunan yang setiap elemennyamerupakan elemen dari himpunanA dan B

Notasi :

AB = {x|x A dan x B}

Gabungan (union)

Gabungan (union) dari himpunanA dan B adalah himpunan yang setiap anggotanya merupakananggota himpunan A atauhimpunan B

Notasi :

AB = {x|x A atau x B}

Operasi Terhadap Himpunan

Komplemen (complement)

Komplemen dari suatu himpunanA terhadap suatu himpunansemesta U adalah suatu himpunanyang elemennya merupakanelemen U yang bukan elemen A.

Notasi :

A = {x|x U dan x A}

Selisih (difference)

Selisih dari 2 himpunan A dan B adalah suatu himpunan yang elemennya merupakan elemendari A tetapi bukan elemen dari B

Notasi :

A-B = {x|x A dan x B} = AB


Beda Setangkup(Symmetric Difference)

Beda setangkup dari himpunan A dan B adalah suatu himpunanyang elemennya ada padahimpunan A atau B, tetapi tidakpada keduanya.

Notasi :

AB =(AB)-(AB)= (A-B)(B-A)

Perkalian Kartesian(Cartesian product)

Perkalian kartesian dari himpunanA dan B adalah himpunan yang elemennya semua pasanganberurutan (ordered pairs) yang dibentuk dari komponen pertamadari himpunan A dan komponenkedua dari himpunanB

Notasi :A x B = {(a,b)|a A dan b B}

Contoh :Misalkan C = {1,2,3} dan D ={a,b} maka perkalian kartesia C dan D adalahCxD = {(1,a),(1,b), (2,a), (2,b), (3,a), (3,b)}


Perampatan (generalization) Operasi Himpunan

Contoh :A1 = { 0,2,3}A2 = {1,2,3,6}A3 = {-1,0,3,9}

Maka

=

=

=

= {, , , , , , }

Hukum-hokum Aljabar Himpunan

Prinsip Dualisme

Prinsip dualism menyakatan bahwa dua konsep yang berbedadapat dipertukarkan namun tetap memberi jawaban yang benar.

Prinsip Dualisme

Prinsip Inklusi - Eksklusi

Untuk dua himpunan A dan B:

A B = A + B A B

A B = A +B 2A B


Contoh :Berapa banyaknya bilangan bulat antara 1 dan 100 yang habis dibagi3 atau 5?Penyelesaian:

A = himpunan bilangan bulat yang habis dibagi 3,B = himpunan bilangan bulat yang habis dibagi 5,A B = himpunan bilangan bulat yang habis dibagi 3 dan 5 (yaitu

himpunan bilangan bulat yang habis dibagi oleh KPK Kelipatan Persekutuan Terkecil dari 3 dan 5, yaitu 15),

Yang ditanyakan adalah A B.

A = 100/3 = 33, B = 100/5 = 20, A B = 100/15 = 6A B = A + B A B = 33 + 20 6 = 47

Jadi, ada 47 buah bilangan yang habis dibagi 3 atau 5.


Untuk tiga buah himpunan A, B, dan C, berlaku

A B C = A + B + C A B A C B C + A B C

Untuk himpunan A1, A2, , Ar, berlaku:

A1 A2 Ar =

1

+

1

+ + 1 1 |1 2 |


Contoh :Di antara bilangan bulat antara 101 600 (termasuk 101 dan600 itu sendiri), berapa banyak bilangan yang tidak habis dibagioleh 4 atau 5 namun tidak keduanya?

Penyelesaian: Diketahui:

U = 500 A = 600/4 100/4 = 150 25 = 125 B = 600/5 100/5 = 120 20 = 100 A B = 600/20 100/20 = 30 5 = 25

Ditanya : ? ?

Hitung terlebih dahulu A B = A + B 2 A B = 125 + 100 50 = 175

Untuk mendapatkan : = U A B = 500 175 = 325

Partisi

Partisi dari sebuah himpunan A adalah sekumpulan himpunanbagian tidak kosong A1, A2, dari A sedemikian sehingga:A1 A2 = A, dan Ai Aj = untuk i j

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

Himpunan Ganda

Himpunan yang elemennya boleh berulang (tidak harus berbeda) disebut himpunan ganda (multiset).

Contohnya, {1, 1, 1, 2, 2, 3}, {2, 2, 2}, {2, 3, 4}, {}.

Multiplisitas dari suatu elemen pada himpunan ganda adalahjumlah kemunculan elemen tersebut pada himpunan ganda. Contoh: M = { 0, 1, 1, 1, 0, 0, 0, 1 }, multiplisitas 0 adalah 4.

Himpunan (set) merupakan contoh khusus dari suatu multiset, yang dalam hal ini multiplisitas dari setiap elemennya adalah 0 atau 1.

Kardinalitas dari suatu multiset didefinisikan sebagai kardinalitashimpunan padanannya (ekivalen), dengan mengasumsikanelemen-elemen di dalam multiset semua berbeda.

Himpunan GandaOperasi Antara Dua Buah Multiset:

1. Misalkan P dan Q adalah multiset:P Q adalah suatu multiset yang multiplisitas elemennya samadengan multiplisitas maksimum elemen tersebut pada himpunanP dan Q.

Contoh: P = { a, a, a, c, d, d } dan Q ={ a, a, b, c, c }, P Q = { a, a, a, b, c, c, d, d }

2. P Q adalah suatu multiset yang multiplisitas elemennya samadengan multiplisitas minimum elemen tersebut pada himpunanP dan Q.

Contoh: P = { a, a, a, c, d, d } dan Q = { a, a, b, c, c } P Q = { a, a, c }

Himpunan Ganda

3. P Q adalah suatu multiset yang multiplisitas elemennyasama dengan: multiplisitas elemen tersebut pada P dikurangimultiplisitasnya pada Q, jika selisihnya positif 0, jika selisihnyanol atau negatif.

Contoh: P = { a, a, a, b, b, c, d, d, e } dan Q = { a, a, b, b, b, c, c, d, d, f } maka P Q = { a, e }

4. P + Q, yang didefinisikan sebagai jumlah (sum) dua buahhimpunan ganda, adalah suatu multiset yang multiplisitaselemennya sama dengan penjumlahan dari multiplisitas elementersebut pada P dan Q.

Contoh: P = { a, a, b, c, c } dan Q = { a, b, b, d },P + Q = { a, a, a, b, b, b, c, c, d }

Pembuktian Proposisi Perihal Himpunan

Proposisi himpunan adalah argumen yang menggunakan notasi himpunan.

Proposisi dapat berupa:1. Kesamaan (identity)

Contoh: Buktikan A (B C) = (A B) (A C)

2. ImplikasiContoh: Buktikan bahwa Jika A B = danA (B C) maka selalu berlaku bahwa A C.

Pembuktian Proposisi Perihal Himpunan

1. Pembuktian dengan menggunakan diagram Venn

Contoh :Misalkan A, B, dan C adalah himpunan. Buktikan bahwaA (B C) = (A B) (A C) dengan diagram Venn. Bukti:

A (B C) (A B) (A C)

Kedua digaram Venn memberikan area arsiran yang sama. Terbukti bahwa A (B C) = (A B) (A C).

Pembuktian ProposisiPerihal Himpunan

Diagram Venn hanya dapat digunakan jikahimpunan yang digambarkan tidak banyakjumlahnya.

Metode ini mengilustrasikan ketimbangmembuktikan fakta.

Diagram Venn tidak dianggap sebagai metodeyang valid untuk pembuktian secara formal.

2. Pembuktikan dengan menggunakan tabel keanggotaan

Contoh 27. Misalkan A, B, dan C adalah himpunan. Buktikanbahwa A (B C) = (A B) (A C).

Bukti:

Karena kolom A (B C) dan kolom (A B) (A C) sama, maka A (B C) = (A B) (A C).

A B C B C A (B C) A B A C (A B) (A C)

0 0 0 0 0 0 0 0

0 0 1 1 0 0 0 0

0 1 0 1 0 0 0 0

0 1 1 1 0 0 0 0

1 0 0 0 0 0 0 0

1 0 1 1 1 0 1 1

1 1 0 1 1 1 0 1

1 1 1 1 1 1 1 1

3. Pembuktian dengan menggunakan aljabar himpunan.

Contoh

Misalkan A dan B himpunan. Buktikan bahwa

(A B) (A B) = A

Bukti:

(A B) (A B) = A (B B) (Hukum distributif)

= A U (Hukum komplemen)

= A (Hukum identitas)

Contoh

Misalkan A dan B himpunan. Buktikan bahwa

A (B A) = A B

Bukti:

A (B A) = A (B A) (Definisi operasi selisih)

= (A B) (A A) (Hukum distributif)

= (A B) U (Hukum komplemen)

= A B (Hukum identitas)

Contoh

Buktikan bahwa untuk sembarang himpunan A dan B, bahwa

(i) A (A B) = A B dan

(ii) A (A B) = A B

Bukti:

(i) A ( A B) = ( A A) (A B) (H. distributif)

= U (A B) (H. komplemen)

= A B (H. identitas)

(ii) adalah dual dari (i)

A (A B) = (A A) (A B) (H. distributif)

= (A B) (H. komplemen)

= A B (H. identitas)

4. Pembuktian dengan menggunakan definisi

Metode ini digunakan untuk membuktikan

pernyataan himpunan yang tidak berbentuk

kesamaan, tetapi pernyataan yang berbentuk

implikasi. Biasanya di dalam implikasi tersebut

terdapat notasi himpunan bagian ( atau ).

Contoh

Misalkan A dan B himpunan. Jika A B = dan A (B C)

maka A C. Buktikan!

Bukti:

(i) Dari definisi himpunan bagian, P Q jika dan hanya jika

setiap x P juga Q. Misalkan x A. Karena A (B C),

maka dari definisi himpunan bagian, x juga (B C).

Dari definisi operasi gabungan (), x (B C) berarti x B

atau x C.

(ii) Karena x A dan A B = , maka x B

Dari (i) dan (ii), x C harus benar. Karena x A juga berlaku

x C, maka dapat disimpulkan A C .

Misalkan A adalah himpunan bagian dari

himpunan semesta (U). Tuliskan hasil dari operasi

beda-setangkup berikut?

(a) A U (b) A A (c) A U

Penyelesaian:

(a) A U = (A U) (U A) (Definisi operasi beda setangkup)

= () (A) (Definisi opearsi selisih)

= A (Hukum Identitas)

(b) A A = (A A ) ( A A) (Definisi operasi beda setangkup)

= (A A) (A A ) (Definisi operasi selisih)

= A A (Hukum Idempoten)

= U (Hukum Komplemen)

(c) A U = ( A U) ( A U) (Definisi operasi beda setangkup)

= U A (Hukum Null dan Hukum Identitas)

= A (Definisi operasi selisih)

Tipe Set dalam Bahasa Pascal

Bahasa Pascal menyediakan tipe data khusus untuk himpunan, yang

bernama set. Tipe set menyatakan himpunan kuasa dari tipe ordinal

(integer, character).

Contoh:

type

HurufBesar = A..Z;{ enumerasi }

Huruf = set of HurufBesar;

var

HurufKu : Huruf;

HurufKu:=[A, C, D];

HurufKu:=[M];

HurufKu:=[]; { himpunan kosong }


Operasi yang dapat dilakukan pada tipe himpunan

adalah operasi gabungan, irisan, dan selisih seperti

pada contoh berikut:

{gabungan} HurufKu:=[A, C, D] + [C, D, E];

{irisan}

HurufKu:=[A, C, D] * [C, D, E];

{selisih}

HurufKu:=[A, C, D] - [C, D, E];


Uji keanggotaan sebuah elemen di dalam himpunan

dilakukan dengan menggunakan opeator in seperti

contoh berikut:

if A in HurufKu then ...

Di dalam kakas pemrograman Delphi, set sering

digunakan untuk mengindikasikan flag. Misalnya

himpunan icon untuk window:

type

TBorderIcon=(biSystemMenu, biMinimize, biMaximaze);

Huruf = set of TBoderIcon;

matematika diskrit - materi 2

Documents