modul ajar matematika komputasi 6

8/18/2019 MODUL AJAR Matematika Komputasi 6

1/42

MODUL AJAR

MATEMATIKA KOMPUTASI

Oleh: Hurriyatul Fitriyah, ST, MSc

I. PENDAHULUAN

Matematika Komputasi merupakan bagian dari Matematika Diskrit yang mempelajari bagaimana

membuat fakta ke dalam bahasa matematika. Kemampuan matematis ini akan membantu proses

komputasi dalam hal ini pemrograman komputer.

Mata kuliah ini terdiri dari 4 pokok bahasan utama, yakni:

1. Mathematical reasoning;

Pembahasan ini bertujuan agar mahasiswa mampu memahami dan membangun mathematical

arguments. Pembahasan ini berisi proposisi, logika matematika, kuantor dan inferensi.

2. Combinatorial Analysis

Pembahasan ini bertujuan agar mahasiswa mampu menghitung bilangan tanpa harus

melakukan enumerasi (menghitung satu per satu). Pembahasan ini berisi teknik pencacahan

seperti divie & conquer, pigeon hole principle, permutasi dan kombinasi.

3. Discrete structure

Pembahasan ini bertujuan agar mahasiswa mampu memahami konsep struktur diskrit yang

digunakan untuk merepresentasikan objek diskrit dan hubungan diantara objek-objek diskrit

tersebut. Pembahasan ini berisi teori himpunan, graf , dan tree.

4.

Algorithmic thinking

Pembahasan ini bertujuan agar mahasiswa mampu memahami bagaimana membuat algoritma

yang berisi metode penyelesaian problem dan mampu melakukan pembuktiannya. Pembahasan

ini berisi number theory, induksi matematika dan algoritma recursive.


2/42

II. PROPOSISI & LOGIKA

Pembahasan proposisi dan logika matematika merupakan materi dasar untuk memahami logika

berpikir secara matematik. Materi ini sangat dibutuhkan sebagai dasar pemrograman dan sistem

digital.

Proposisi adalah sebuah kalimat pernyatan, yang berisi fakta, yang memiliki nilai kebenaran benar

atau salah, dan bukan keduanya.

Contoh proposisi adalah sebagai berikut:

“1 + 1 = 2”

“Universitas Brawijaya berlokasi di Surabaya”

“Hari ini hujan”

Ketiga kalimat diatas memiliki nilai kebenaran benar, salah, benar dan bukan keduanya.

Contoh kalimat yang bukan proposisi adalah sebagai berikut:

“ x + 1 = 2”

“Cari lokasi Universitas Brawijaya!”

“Cuaca apa hari ini?”

Kalimat pertama bukan proposisi karena x dapat berupa angka berapapun yang perlu didefinisikan

lebih lanjut, sehingga nilai kebenarannya bisa benar hanya jika x adalah 1 namun salah jika x adalah

selain 1 (seperti 2,3 atau angka negatif). Kalimat kedua juga bukan proposisi karena merupakan

kalimat perintah dan bukan pernyataan. Kalimat ketiga bukan proposisi karena merupakan kalimat

pertanyaan dan bukan pernyataan.

Notasi proposisi

Kalimat proposisi merupakan sebuah variabel yang di-notasi-kan dengan abjad kecil seperti p, q, r,

s,.. dan lainnya. Dan nilai kebenaran dinyatakan dengan notasi T untuk true atau benar, dan F untk

false atau salah.

Logika proposisi

Adalah cara untuk melakukan reasoning atau penarikan kesimpulan dari satu atau beberapa

proposisi. Logika ini menggunakan operator logika yang terdiri dari 5 operator, yakni negation,

conjunction, disjunction, implication dan bi-implication.


3/42

Reasoning ini dapat dilakukan pada satu atau lebih dari satu proposisi. Beberapa proposisi yang

dikumpulkan dengan menggunakan operator logika disebut dengan compound proposition.

1. Negation (¬)

Adalah operator logika yang menjadikan sebuah proposisi menjadi pernyataan kebalikannya.

Operator ini juga akan merubah nilai kebenaran sebuah proposisi menjadi kebalikannya.Perhatikan contoh berikut:

Jika p adalah sebuah proposisi:

“Hari ini adalah hari Kamis”

maka negation dari proposisi p atau yang dinotasikan sebagai ¬ p ini adalah:

“Bukan perkara Hari ini adalah hari Kamis” , atau

“Hari ini adalah bukan hari Kamis”

Tabel 1 menunjukkan nilai kebenaran dari sebuah proposisi yang berubah dengan operator

negation.

Tabel 1. Tabel kebenaran proposisi dengan operator negation

p ¬ p

T F

F T

2. Conjunction

Adalah operator logika yang menghubungkan 2 buah proposisi dengan logika “and” atau “dan”.

Conjunction dinotasikan dengan “” sehingga jika p dan q adalah proposisi maka compound proposition dari ” p and q” atau ” p dan q” ditulis sebagai “ p q”. Perhatikan contoh berikut:Jika p adalah sebuah proposisi:

“Mahasiswa yang memiliki IPK diatas 3.5 adalah lulus dengan predikat cumlaude”

Dan q adalah sebuah proposisi:

“Mahasiswa yang lulus dengan masa studi kurang dari 4 tahun adalah lulus dengan

predikat cumlaude”

Maka conjunction dari proposisi p dan q adalah:“Mahasiswa yang memiliki IPK diatas 3.5 dan Mahasiswa yang lulus dengan masa studi

kurang dari 4 tahun adalah lulus dengan predikat cumlaude”

Tabel 2 menunjukkan nilai kebenaran dari operator conjunction. Sebuah compound proposition

yang memiliki operator conjunction akan bernilai “True” atau “Benar” hanya jika kedua proposisi

tersebut, p dan q, sama-sama bernilai “True”


4/42


5/42


6/42


7/42

Tabel 5. Tabel kebenaran dua proposisi dengan operator implication

p q p q q p ¬p ¬q ¬q ¬pT T T T T T

T F F T T F

F T T F F TF F T T T T

Dalam konsep implication p q, terdapat beberapa istilah yang disebut sebagai converse q p,inverse ¬p ¬q, dan contrapositive ¬q ¬p. Nilai kebenaran dari implication adalah sama atauequivalent dengan contrapositive, sedangkan converse adalah equivalent dengan inverse.

5.

Bi-implication

Adalah operator logika untuk bi-conditional statement atau kalimat sebab akibat “if and only if”atau “jika dan hanya jika”. Bi-implication dinotasikan dengan “” sehingga jika p dan q adalahproposisi maka compound proposition “ p if and only if q” atau “ p jika dan hanya jika q”. ditulis

sebagai “ p q”. Perhatikan contoh berikut: Jika p adalah sebuah proposisi:

“Mahasiswa dapat mengajukan beasiswa”

Dan q adalah sebuah proposisi:

“Mahasiswa memiliki IP 3.5”

Maka bi-mplication dari proposisi p dan q adalah:

“Mahasiswa dapat mengajukan beasiswa jika dan hanya jika memiliki IP 3.5”, atau

“Mahasiswa memiliki IP 3.5 adalah syarat cukup dan syarat perlu untuk dapat

mengajukan beasiswa”

Tabel 6 menunjukkan nilai kebenaran dari operator bi-implication. Sebuah compound

proposition yang memiliki operator bi-implication akan bernilai “True” hanya jika kedua

proposisi tersebut memiliki nilai kebenaran sama. Pada contoh proposisi p dan q diatas, adalah

benar jika mahasiswa memiliki IP di atas 3.5 saja lah maka ia dapat mengajukan beasiswa. Dan

adalah tetap benar jika mahasiswa tidak memiliki IP di atas 3.5 maka ia tidak dapat mengajukan

beasiswa.

Dan sebaliknya compound proposition tersebut akan bernilai “False” jika kedua proposisi

tersebut memiliki nilai kebenaran yang berbeda. Yakni pada kondisi jika mahasiswa memiliki IP

di atas 3.5 maka ia tidak dapat mengajukan beasiswa; dan jika mahasiswa tidak memiliki IP di


8/42

atas 3.5 maka ia dapat mengajukan beasiswa dimana kedua nilai kebenaran compound

porposition-nya adalah salah.

Tabel 6. Tabel kebenaran dua proposisi dengan operator bi-implication

P q p qT T T

T F F

F T F

F F T

Compound Proposition yang Komplek

Umumnya, operator logika digunakan secara bersamaan dalan sebuah compound proposition

yang lebih komplek. Misalkan pada:

(¬pq) (q )Maka nilai kebenaran dari compound proposition diatas dihitung dengan cara seperti pada tabel

7.

Tabel 7. Tabel kebenaran dari compound proposition (¬pq) (q ) P Q ¬p (¬p

q) (q

) (¬p

q)

(q

)

T T F T T T

T F F F F T

F T T T F F

F F T T F F

Dapat juga operator logika diterapkan pada compound proposition yang terdiri dari lebih dari 2

proposisi. Misalkan pada:

(pq) ¬rMaka nilai kebenaran dari compound proposition diatas dihitung dengan cara seperti pada tabel

8.


9/42

Tabel 8. Tabel kebenaran dari compound proposition (pq) ¬r p q R (pq) ¬r (pq) ¬rT T T T F F

T T F T T T

T F T F F TT F F F T F

F T T F F T

F T F F T F

F F T F F T

F F F F T F

Urutan dalam Pengerjaan Operator Logika

Jika terdapat compound proposition yang cukup komplek dan umumnya tanda kurung tidak diletakkan

pada pemrograman untuk menghemat komputasi, maka urutan pengerjaan operator logika adalahsebagai berikut:

1. Negation, ¬

2. Conjunction, 3. Disjunction, 4.

Implication, 5. Bi-implication,

Sehingga jika terdapat ¬ pq dalam program maka akan dikomputasi sebagai ( ¬ p)q dan bukannya¬( p

q). Jika terdapat p

q

r maka akan dikomputasi sebagai (p

q)

r dan bukannya p

(q

r). Jika

terdapat pq r dan pq r maka akan dikomputasi sebagai (pq) r dan (pq) r.

Proposisi dan logika dalam sistem digital

Komputer bekerja dalam sistem operasi digital dimana informasi disimpan dalam bentuk bit yang berisi

nilai 0 atau 1. Sebuah bit dapat pula digunakan untuk menunjukkan nilai kebenaran “True” atau “False”

dimana “True” direpresentasikan sebagai 1 dan “False” sebagai 0. Variabel dengan dua nilai benar atau

salah seperti ini disebut dengan variabel Boolean. Tabel 9 menunjukkan hubungan nilai kebenaran

dengan data digital bit.

Tabel 9. Hubungan Nilai Kebenaran dengan Bit.

Nilai Kebenaran Bit

T 1

F 0


10/42

Aturan dari operator logika yang diterapkan pada nilai kebenaran “True” atau “False” juga berlaku pada

nilai bit 0 atau 1 ini.

Tautology dan Contradiction

Tautology adalah sebuah compound proposition yang memiliki nilai kebenaran selalu “True” pada semua

kombinasi nilai kebenaran dari proposisi penyusunnya. Dan sebaliknya, jika nilai kebenarannya selalu

“False” pada semua kombinasi nilai kebenaran dari proposisi penyusunnya maka dinamakan

contradiction.

Contoh tautology adalah p¬p sedangkan contoh contradiction adalah adalah p¬p. Perhatikan Tabel 10yang menunjukkan nilai kebenaran dari kedua compound proposition tersebut.

Tabel 9. Tabel Kebenaran p¬p yang merupakan tautology dan p¬p yang merupakan contradiction p ¬ p p¬p p¬p T F T F

F T T F

Logical Equivalences

Dua buah compound proposition dikatakan ekivalen secara logika (logical equivalence) adalah ketika

keduanya memiliki nilai kebenaran yang sama pada semua kombinasi nilai kebenaran proposisi-

proposisi penyusunnya. Jika p adalah sebuah compound proposition yang ekivalen secara logika

terhadap compound proposition q, maka hubungan kesamaan ini di-notasi-kan dengan p q atau p q.

Contoh logical equivalense adalah yang terdapat pada hukunDe’Morgan yang menyatakan bahwa :

¬(pq) ¬p¬q , dan¬(pq) ¬p¬q

Perhatikan Tabel 10 yang menunjukkan Tabel Kebenaran dari hukunDe’Morgan ini.

Tabel 10. Tabel kebenaran dari logical equivalence pada ¬(pq) ¬p¬q P Q (pq) ¬(pq) ¬p ¬q ¬p¬qT T T F F F F

T F F T F T T

F T F T T F T

F F F T T T T


11/42

Menggunakan logical equivalence pada hukum De’Morgan, maka negation dari compound proposition

“Mahasiswa mengambil mata kuliah Matematika Komputasi dan Pemrograman Dasar” adalah

“Mahasiswa tidak mengambil mata kuliah Matematika Komputasi atau tidak mengambil mata kuliah

Pemrograman Dasar”.

Contoh lain dari compund proposition yang memiliki logical equivalence adalah pq ¬pq. Tabel 11menunjukkan logical equivalence yang penting untuk dipahami. Pada Tabel ini, T menunjukkan sebuahcompound proposition yang selalu bernilai kebenaran “True” (tautology) , dan F menjunjukkan sebuah

compound proposition yang selalu bernilai kebenaran “False” (contradiction).

Tabel 11. Logical Equivalence


12/42

Contoh: buktikan bahwa ¬(p(¬pq)) ¬p¬q ! Jawaban:

¬(p(¬pq)) ¬ p¬(¬pq) Menggunakan hukum De’Morgan

¬ p

(¬(¬p)

¬q) Menggunakan hukum De’Morgan

¬ p(p¬q) Menggunakan aturan double negation ( ¬ p p) ( ¬ p¬q) Menggunakan aturan distribution F ( ¬ p¬q) Karena( ¬ p p) F ( ¬ p¬q) F Menggunakan aturan comutative ¬ p¬q Menggunakan identity lawPredicates and Quantifier

Jika proposition adalah kalimat yang hanya bernilai “True” atau “False” tapi bukan keduanya, maka

dalam pemrograman terdapat kalimat yang bisa bernilai keduanya karena memiliki variabel seperti

contoh berikut:

“ x > 4”

“Y adalah sebuah server di jaringan Filkom UB”

Dimana Y adalah variabel sedangkan “>4” dan “adalah sebuah server di jaringan FILKOM UB” adalah

predicate. Kalimat “ x > 4” di-notasi-kan sebagai P(x) yang merupakan propositional function P pada saat

x. Nilai kebenaran dari P(x) akan bernilai “True” jika x bernilai 5, 6, 7, dst namun akan bernilai “False”

saat x bernilai 4,3,2, dst.

Propositional function yang terdiri dari variable dan predicates juga bisa memiliki 2 variabel atau lebihseperti:

“ x dan y adalah mata kuliah di Filkom UB”

Dan dinotasikan sebagai P(x,y).

Nilai kebenaran propositional function dapat ditentukan saat variable-nya ditentukan. Misalkan x adalah

Matematika Komputasi dan y adalah Pemrograman Dasar maka P(x,y) diatas bernilai “True”. Namun

sebuah propositional function dapat dibuat menjadi proposition dengan memberikan quantifier yang

akan memberikan nilai kebenaran pada sebuah range atau domain x . Quantifier ini seperti partikel

nominal “semua”, “beberapa”, “tidak ada” dan “sedikit”. Sebuah propositional function yang memilikiquantifier disebut dengan quantified statement.

Terdapat 2 quantifier utama yakni universal quantifier dan existensial quantifier. Universal quantifier

menyatakan nilai kebenaran “True” pada propositional function jika semua item di domain x adalah

“True”. Universal quantifier pada sebuah propositional function P(x):

“ x 2 0”


13/42

di-notasi-kan sebagai xPx (dibaca: untuk semua xPx ) yang berarti:“Semua x bernilai “True” untuk x

2 0” Pada domain dimana x adalah semua bilangan integer.

Disini xP(x) bernilai “True” karena setiap bilangan real akan memenuhi propositional function diatas.Jika salah satu item saja pada domain x yang memberikan nilai “False”, maka nilai kebenaran dari xP(x)menjadi “False”. Seperti pada P(x):

“ x > 10”

Pada domain dimana x adalah semua bilangan integer. Saat x = 11 maka P(x) akan bernilai “False”.

Sehingga xP(x) menjadi “False” dan 11 disebut sebagai counter-example dari P(x). Sehingga nilaikebenaran dari quantified statement xP(x) dapat diartikan sebagai operasi conjunction (AND) padasetiap nilai x di domain yang ditentukan, yakni

xP(x) = P(x 1 ) P(x 2 ) P(x 3 ) ... P(x n )

Existensial quantifier pada sebuah propositional function P(x) menyatakan nilai kebenaran “True” jika

setidaknya satu item di domain x bernilai “True”. Existensial quantifier pada sebuah propositional

function P(x):

“ x + 3 = 4”

di-notasi-kan sebagai xPx (dibaca: untuk setidaknya satu xP(x)) yang berarti:“Setidaknya ada satu x yang bernilai “True” untuk x + 3 = 4”

pada domain dimana x adalah semua bilangan integer.

Disini xP(x) bernilai “True” jika setidaknya satu x pada domain bilangan integer bernilai “True”, yaknihanya pada saat x = 1. Sehingga nilai kebenaran dari quantified statement xP(x) dapat diartikansebagai operasi disjunction (OR) pada setiap nilai x di domain yang ditentukan, yakni

xP(x) = P(x 1 ) P(x 2 ) P(x 3 ) ... P(x n )Jika tidak ada satu pun item pada domain x yang memberikan nilai “True” atau dengan kata lain

semuanya bernilai “False”, maka nilai kebenaran dari xP(x) menjadi “False”. Seperti pada P(x):“ x = x + 1”

Pada domain dimana x adalah semua bilangan integer.

Tabel 12 merangkum pengertian quantifier ini pada nilai kebenaran “True” dan “False”.


14/42

Tabel 12. Pengertian quantifier

Tipe Notasi Bernilai “True” saat? Bernilai “False” saat?

Universal xP(x) P(x) bernilai “True” padasemua x

Setidaknya ada satu x yang

bernilai “False” P(x)

Existensial xP(x) Setidaknya ada satu x yangbernilai “True” pada P(x)

P(x) bernilai “False” pada

semua x

Dari Tabel 12 diatas dapat dilihat bahwa ¬ xP(x) x¬P(x) dan ¬ xP(x) x ¬P(x). Hubungan negationdari quantfied statement ini menganut hukum De’Morgan. Perhatikan contoh kalimat xP(x) berikut:

“ Semua mahasiswa mendapat nilai A dalam mata kuliah Matematika Komputasi”

negation dari kalimat tersebut sesuai hukum De’Morgan’s law for quantifiers adalah:

“Setidaknya ada satu mahasiswa yang tidak mendapat nilai A dalam mata kuliah Matematika

komputasi”

sebab universal quantifier bersifat seperti conjunction (AND). Sehingga 1 saja item dalam domain x yang

bernilai “False” maka universal quantifer pada proportional function akan bernilai “False”. Perhatikan

contoh kalimat x¬P(x) berikut:“Setidaknya ada satu politisi yang jujur”

negation dari kalimat tersebut sesuai hukum De’Morgan’s law for quantifiers adalah:

“Semua politisi tidak jujur”

sebab existensial quantifier bersifat seperti disjunction (OR). Sehingga untuk menjadikan existensial

quantifer pada proportional function bernilai “False”, maka semua item dalam domain x harus bernilai

“False”.

Inferensi Logika

Melakukan inferensi pada logika bertujuan untuk menyatakan sebuah argument adalah valid atau tidak.

Argument merupakan kumpulan dari premise atau sebab dan conclusion atau akibatBaik premisemaupun conclusion dapat berupa proposition, compound proposition, atau quantified statement.

Argument dibangun dengan menghubungan semua premise dengan operator conjunction (AND).

Sedangkan operator logika yang menghubungkan premise dan conclusion adalah implication. Sehingga

jika terdapat p1 sebagai premise 1, p2 sebagai premise 2, dan c sebagai conclusion nya, maka hubungan

ketiganya dapat ditulis sebagai (p1 p2) c atau dalam bentuk:


15/42

p1

p2

cSebuah argument dinyatakan valid jika saat (p1 p2) c menghasilkan tautology. Contoh sederhana dari inferensi adalah terdapat premise:

“Jika hari ini cerah, maka saya akan pergi berenang”

Dan premise:

“Jika pergi berenang, maka saya akan tidur cepat”

Maka conclusion-nya adalah:

“Jika hari ini cerah, maka saya akan tidur cepat”

Contoh argument diatas yang dalam istilah psikologi disebut syllogism ditulis sebagai berikut:

p qq r

p rDimana p adalah proposition “Hari ini cerah”, q adalah “saya pergi berenang”, dan r adalah “saya tidur

cepat”.

Untuk membuktikan apakah argument diatas valid atau tidak valid , maka dapat dibuktikan

menggunakan tabel kebenaran ((p q)(q r)) (p r) seperti pada tabel 14. Jika tabelkebenarannya adalah tautology, maka argument diatas adalah valid.

Tabel 14. Tabel kebenaran argument ((p q)(q r)) (p r) p q R (p q) (q r) (p q)(q r) (p r) ((p q)(q r)) (p r)T T T T T T T T

T T F T F F F T

T F T F T F T TT F F F T F F T

F T T T T T T T

F T F T F F T T

F F T T T T T T

F F F T T T T T


16/42

Dari Tabel 14 diatas menunjukkan bahwa argument syllogism diatas adalah valid karena berupa

tautology.

Membuktikan kevalidan argument tidak hanya dengan menggunakan tabel kebenaran. Terutama jika

proposition yang digunakan adalah banyak karena berarti kita harus menghitung 2n

ragam kombinasi

nilai kebenarannya, dimana n adalah banyaknya proposition. Pembuktian argument atau melakukaninference dari logika dapat pula menggunakan aturan-aturan inference seperti pada Tabel 15.

Tabel 15. Aturan-aturan logical inference

Contoh: buktikan bahwa premise “hari ini sabtu”, “jika hari ini sabtu, maka saya akan jalan- jalan”, “saya

tidak jalan-jalan atau saya pergi ke rumah nenek”, akan menghasilkan conclusion “saya pergi ke toko

buku atau pergi ke rumah nenek”.

Jawaban: langkah pertama adalah mendata semua proposition yang terdapat dalam argument diatas.

Terdapat 4 proposition, yakni:

p : “hari ini sabtu”

q: “saya jalan- jalan”


17/42

r: “saya pergi ke rumah nenek”

s: “ saya pergi ke toko buku”

sehingga dapat disusun argument sebagai berikut:

p p q

¬q r s r

Untuk menunjukkan ke-valid-an argument diatas maka digunakan aturan-aturan inference:

1.

p

p q

q aturan modus ponen2.

q

q s aturan addition3.

q s ¬q r

s

r aturan resolution

Sehingga dengan pembuktian diatas, dapat dikatakan bahwa premise-conclusion tersebut adalah valid .

Cara ini lebih sederhana daripada menggunakan tabel kebenaran (p p q ) ¬q r )) yangterdiri dari 2

4 baris kombinasi nilai kebenaran.


18/42

III. STRUKTUR DISKRIT: HIMPUNAN

Himpunan adalah kumpulan objek-objek yang bisa saja memiliki kesamaan atau tidak memiliki

kesamaan. Objek-objek tersebut berkumpul tanpa memiliki urutan dan dinamakan elements, members

atau anggota. Himpunan dinotasikan dengan Huruf kapital seperti A, B, C,.., Z dimana anggotanya

dinotasikan dengan huruf kecil a, b, c,.., z. Misalkan terdapat sebuah himpunan:

V = {a, b, c, d}

Maka dikatakan bahwa a adalah anggota V atau a V, dan g bukanlah anggota V atau g V.Terdapat banyak cara untuk menyatakan himpunan, yakni:

1. Mendeskripiskan dan menyebutkan anggota-anggota nya, misal A adalah himpunan kumpulan

huruf vokal di abjad. Sehingga A = {a,i,u,e,o}

2.

Notasi set builder,dengan menyebutkan deskripsi misal A = {x | x: kumpulan huruf vokal di

abjad}

3.

Diagram Venn seperti pada Gambar 1.

Gambar 1. Diagram venn dari himpunan

Diagram ini terdiri dari “Universe” (U) atau “semesta” (S) yang dilambangkan dengan kotak atau

persegi panjang, kemudian himpunan di dalamnya dilambangkan dengan lingkaran atau oval.

Anggota dari himpunan akan berada di dalam lingkaran, sedangkan yang bukan anggota akan

berada di luar lingkaran.

Ukuran Himpunan (Cardinality of Set)

Ukuran suatu himpunan A atau cardinality of set dan yang dilambangkan dengan |A| adalah banyaknya

anggota dari himpunan tersebut. Misal:

A = {x | x adalah bilangan prima < 15}

dan anggota dari A adalah A = {1, 3, 5, 7, 11, 13}, sehingga |A| = 6.

A

· o

· e· u · i

· a

· g

U


19/42

Himpunan yang tidak memiliki anggota disebut dengan himpunan kosong (null set, empty set) dan

cardinality-nya adalah 0. Misal:

B = {x | x adalah nama buah yang dimulai dengan huruf X}

Maka anggota dari B adalah tidak ada atau kosong, sehingga |B| = SubSet (Himpunan Bagian)

Diketahui himpunan A merupakan himpunan huruf vokal dalam abjad dan mmemiliki anggota {a, i, u, e

o}. Terdapat himpunan-himpunan bagian (subset) dari himpunan A, yakni:

a.

Himpunan kosong (empty set ), Ab.

Proper subset atau strict subset , adalah himpunan yang memiliki anggota sebagian dari A.

Contoh himpunan bagian proper subset C = {u, o, e} seperti pada gambar 2 dan dinotasikan

sebagai C A. Karena C merupakan proper subset dari A, maka A dinamakan super set dariC yang dilambangkan sebagai A B.

Gambar 2. Diagram Venn dari C A atau A Cc. Himpunan itu sendiri, A A

Contoh dimana B adalah himpunan yang memiliki anggota sama dengan A, yakni B = {a, i, u,

e, o} seperti pada Gambar 3 dan dinotasikan sebagai B A.Karena B merupakan subset dari A, maka A dinamakan super set dari B atau A B. Disinisebab A memiliki anggota yang sama persis dengan B, maka dapat dinotasikan A = B.

A

· i

· a· u

· o · e

C

U


20/42

Gambar 3. Diagram Venn dari B A atau A B

Power Set (Himpunan Kuasa)

Power set adalah kumpulan himpunan-himpunan bagian (subset) dari sebuah himpunan. Power Set dari

sebuah himpunan A dinotasikan sebagai . Jika himpunan A memiliki anggota A = {1, 2, 3}, maka power set dari A adalah:

{} { {} {} {} { } { } { } {}}

Jumlah subset dari sebuah himpunan adalah 2n dimana n adalah banyaknya anggota dari himpunan

tersebut. Seperti himpunan A diatas yang memiliki 3 anggota maka jumlah subset dalam power set nya

adalah 8.

Operasi pada Himpunan

Satu atau lebih himpunan dapat dioperasikan dengan cara:

1.

Complement (komplemen)

Jika A adalah himpunan, maka complement dari A atau yang dinotasikan sebagai ̅ adalah selainanggota dari himpunan A. Perhatikan Gambar 3 dimana komplemen A adalah bagian yang diarsir.

Gambar 3. Komplemen dari A, ̅

A

· u

· o · e

B

· a

· i

U

A

̅ U


21/42

2.

Intersection (irisan)

Jika A dan B adalah himpunan, maka irisan atau intersection dari A dan B atau yang dinotasikan

dengan A B adalah anggota himpunan A yang juga merupakan anggota himpunan B. Misal A ={1,2,3} dan B adalah {3,4,5} maka A

B = {3}. Perhatikan Gambar 4 dimana A

B ditunjukkan

dengan bagian yang diarsir.

Gambar 4. A irisan B, A B3.

Union (gabungan)

Jika A dan B adalah himpunan, maka gabungan atau union dari A dan B atau yang dinotasikan

dengan A B adalah gabungan dari semua anggota himpunan A dan B. Misal A = {1,2,3} dan Badalah {4,5, 6} maka A B = {1, 2, 3, 4, 5, 6}. Perhatikan Gambar 4 dimana A U B ditunjukkan denganbagian yang diarsir.

Gambar 4. A gabungan B, A

B

Hubungan himpunan A dan B seperti pada Gambar 4 disebut sebagai disjoint, dimana kedua

himpunan tidak memiliki irisan. Sedangkan jika terdapat irisan misalkan antara himpunan A dan C

dimana C = {3,4,5} maka A C = {1, 2, 3, 4, 5}. Dimana dalam hal ini member 3 tidak perlu diulangpenulisannya karena:

| A C | = |A| + |C| - |A C|

A

· 2

· 1

B U

· 5

· 4· 3

A

· 2

· 1

B U

· 5

· 4

· 3

· 6


22/42

Sehingga | A U C | = 5. Ketentuan diatas dinamakan dengan principle of inclusion-exclusion.

Perhatikan Gambar 5 untuk A U C yang ditunjukkan dengan bagian yang diarsir.

Gambar 6. Difference dari A dan C, A – C

4.

Difference (pengurangan)

Jika A adalah himpunan A = {1, 2, 3} dan C adalah himpunan C = {3, 4, 5}, maka difference dari

himpunan A dan C atau A – C adalah sebuah himpunan yang memiliki anggota A saja namun tidak di

B. Perhatikan Gambar 6 untuk diagram venn dari A – C dimana difference dari A dan C adalah bagian

yang diarsir.

Gambar 6. Difference dari A dan C, A – C

5.

Cartesian product (perkalian cartesian)

Jika A dan B adalah himpunan dimana A = {1,2} dan B = {a,b,c} , maka perkalian cartesian dari A dan

B atau yang dinotasikan sebagai A x B adalah himpunan n-pasangan berurutan dari masing-masing

anggota A dan B, yakni:

A x B = { (1,a), (1,b), (1,c), (2,a), (2,b) , (2,c) }

Dimana n adalah banyaknya himpunan yang akan dikalikan. Sedangkan perkalian cartesian dari B x A

akan menjadi:

A

· 2

· 1

B U

· 5

· 4· 3

A

· 2

· 1

B U

· 5

· 4· 3


23/42

B x A = { (a,1), (a,2), (b,1), (b,2), (c,1), (c,2) }

Perkalian cartesian dapat melibatkan n buah himpunan sehingga akan menghasilkan himpunan n-

pasangan yang berurutan. Seperti jika terdapat C = {x,y}, maka A x B x C adalah:

A x B x C = { (1,a,x), (1,a,y), (1,b,x), (1,b,y), (1,c,x), (1,c,y),

(2,a,x), (2,a,y), (2,b,x), (2,b,y), (2,c,x), (2,c,y) }

Operasi Himpunan pada Binary

Dalam penggunaannya pada komputasi, operasi intersection berlaku sama seperti conjunction AND . Sedangkan operasi union U berlaku sama seperti disjunction OR (Lihat Tabel 15).

Tabel 15. Operasi Himpunan pada binary

A B A B A U B1 1 1 1

1 0 0 1

0 1 0 1

0 0 0 0

Set Identities

Identities dari sebuah himpunan menunjukkan aturan-aturan yang berlaku seperti pada tabel 16.

Pembuktian aturan ini dapat menggunakan Tabel Kebenaran maupun Diagram Venn. Seperti aturan

complementation law yang ditunjukkan pada Tabel 17 untuk pembuktian menggunakan Tabel

kebenaran dan Gambar 7 yang menggunakan diagram Venn.


24/42

Tabel 16. Set Identities

Tabel 17. Tabel Kebenaran

̅ ̅= A

A ̅ ̅ ̅1 0 1

0 1 0

a b c

Gambar 7. Complementation law, a. A, b. ,̅ c. ̿

A

̅ UA

U

= A ̿ U


25/42

Generalized Union and Intersection

Gabungan dari beberapa himpunan yang terhubung menggunakan operator union seperti A1 U A2 U

A3 U A4, maka dapat dinotasikan menggunakangeneralized union:

⋃ sehingga A1 U A2 U A3 U A4 = ⋃ dimana n adalah banyaknya himpunan yang di-union-kan.Irisan dari beberapa himpunan yang terhubung menggunakan operator intersection seperti A1 A2 A3 A4, maka dapat dinotasikan menggunakan generalized intersection:

⋂ sehingga A1

A2

A3

A4 =

⋂

dimana n adalah banyaknya himpunan yang di-intersection-

kan.


26/42


27/42

Gambar 8. Diagram Panah Relasi

4.

Tabel

Relasi dapat dinotasikan dengan tabel 2 kolom dimana anggota himpunan A, x A, pada kolom1 dan himpunan anggota , y B, pada kolom 2. Masing-masing anggota yang memiliki relasidituliskan dalam satu baris yang sama. Lihat Tabel 16.

Tabel 16. Tabel Relasi

Nama Makanan

Adam Bakso

Adam Mie ayam

Budi Sate

Citra Soto

Citra Mie ayam

5.

Diagram Cartesian

Relasi dapat dinotasikan menggunakan diagram cartesian dimana sumbu-x adalah anggota dari

himpunan A, x A sedangkan sumbu-y adalah anggota dari himpunan B, y B,. Masing-masinganggota yang berpasangan ditunjukkan dengan sebuah titik (dot ) pada pertemuan masing-

masing grid yang bersesuaian. Lihat Gambar 9.

Mie ayam

Soto

Sate

Bakso

Adam Budi Citra

Gambar 9. Diagram cartesian Relasi

Adam .

Budi .

Citra .

. Bakso

. Sate

. Soto

. Mie ayam


28/42

6.

Matrik

Relasi dapat dinotasikan dengan matrix dimana anggota himpunan A, x A, ditulis sebagaibaris dan himpunan anggota B, y B, sebagai kolom. Nilai 1 akan diberikan jika terdapat relasiantara baris dan kolom yang berpasangan, dan 0 jika tidak berpasangan. Lihat Gambar 10.

[ ]

Gambar 10. Matrik Relasi

Property of Relation on a Set

Relasi antar anggota dalam suatu himpunan memiliki property, atribut, atau sifat-sifat sebagai berikut:

1. Reflexive, adalah sebuah relasi yang memiliki anggota (a,a) R untuk setiap anggota darihimpunan A, a A. Contoh jika A = {1,2,3,4} maka:

R1 = {(1,1), (2,2), (3,3), (4,4)}

R2 = {(1,1), (1,2), (2,2), (3,4), (3,3), (4,4)}

adalah relasi yang bersifat reflexive, sedangkan

R3 = {(1,1), (2,2), (2,3), (3,4) }

adalah tidak karena tidak semua anggota himpunan A dipasangkan dengan anggota tersebut

atau tidak ada (3,3) dan (4,4).

2. Symmetric, adalah sebuah relasi yang memiliki anggota (a,b) R dan juga (b,a) R untuk setiap(a,b) A dimana a b dan (a,b) A. Contoh jika A = {1, 2, 3, 4} maka:

R1 = {(1,1), (1,2), (2,1), (3,4),(4,4)}

Dikatakan sebagai symmetric karena terdapat (1,2) dan (2,1). Perhatikan bahwa jika terdapat

satu pasang (a,b)

R dan juga (b,a)

R saja pada sebuah relasi, maka dikatakan bahwa relasi

tersebut bersifat symmetric.

3. Anti-symmetric, adalah sebuah relasi yang merupakan kebalikan dari symmetric dimana untuk

setiap (a,b) R tidak terdapat (b,a) R dalam relasi tersebut untuk a b dan (a,b) A. Contoh jika A = {1, 2, 3, 4} maka:

Adam

Budi

Citra

Bak Sat Sot Mie


29/42

R1 = {(1,2)}

R2 = {(2,1), (2,4), (3,3)}

Adalah bersifat antisymmetric.

4.

Transitive, adalah sebuah relasi yang memiliki anggota dimana untuk setiap (a,b)

R dan (b,c)

R dalam sebuah relasi, terdapat juga maka terdapat juga (a,c) R dalam relasi tersebut, dimana(a, b, c) A. Contoh jika A = {1, 2, 3, 4} maka:

R1 = {(1,1), (1,4), (2,1), (2,2), (2,4), (3,4)}

Adalah bersifat transitive sebab terdapat (2,4) untuk (2,1) dan (1,4).

Combining Relation

Dua buah relasi dapat dioperasikan dengan beragam cara, yakni union, intersection, Exclusive-OR,

Difference, Composite, dan Power. Untuk dua buah relasi:

R1 = {(1,2), (2,3), (3,4)}, dan

R2 = {(1,1), (1,2), (2,1), (2,2), (3,1), (3,2), (3,4)}

Maka untuk operasi:

1.

Union

Operasi gabungan, yakni menggabungkan semua anggota dari masing-masing relasi.

R1 U R2 = {(1,1), (1,2), (2,1), (2,2), (2,3), (3,1), (3,2), (3,4)}

2.

Intersection

Operasi irisan, yakni mencari irisan atau anggota yang sama dari kedua relasi.

R1 R2 = {(1,2), (2,3), (3,4)}3.

Exclusive-OR

Operasi XOR, dimana:

R1 R2 = R1 U R2 – (R1 R2)R1 R2 = {(1,1), (1,2), (2,1), (2,2), (2,3), (3,1), (3,2), (3,4)} - {(1,2), (2,3), (3,4)}R1 R2 = {(1,1), (2,1), (2,2), (3,1), (3,2)}


30/42

4.

Difference

Operasi pengurangan, dimana:

R1 - R2 = R1 - (R1 R2)R1 - R2 = {(1,2), (2,3), (3,4)} - {(1,2), (2,3), (3,4)}

R1 - R2 = {}

5.

Composite

Operasi komposisi. Operasi ini berarti jika R2 memasangkan a ke b (a,b) , dan R1 memasangkan b

ke c (b,c), maka:

R1 R2 = (a,c) , untuk (a,b) R2 dan (b,c) R1R1 R2 = {(1,2), (2,3), (3,4)} {(1,1), (1,2), (2,1), (2,2), (3,1), (3,2), (3,4)}R1 R2 = {(1,2), (1,3), (2,2), (2,3), (3,1), (3,3)}

Karena (1,1) (1,2) = (1,2), dan seterusnya.6.

Power

Operasi pangkat. Dimana:

R12 = R1 R1

R12 = {(1,2), (2,3), (3,4)} {(1,2), (2,3), (3,4)}

R12 = {(1,3)(2,4)}

Dan R13 = R1 R1 R1

Atau R13 = R1

2

R1

Dan seterusnya


31/42

V. STRUKTUR DISKRIT: FUNGSI

Fungsi merupakan sebuah pemetaan dari suatu himpunan ke himpunan lainnya dengan aturan atau

cara tertentu. Himpunan yang akan dipetakan disebut domain sedangkan himpunan hasil pemetaan

disebut codomain. Fungsi menghasilkan pasangan-pasangan anggota yang dinotasikan sebagai

untuk sebuah pemetaan dari anggota X ke anggota Y (lihat Gambar 11).

Gambar 11. Pengertian Fungsi yang memetakan X ke Y

Seperti contoh fungsi yang memetakan mahasiswa di kelas Matematika Komputasi dengan nilai

yang didapatkannya pada akhir semester. Jika nama-nama mahasiswa merupakan anggota

himpunan A, sedangkan nilai akhir merupakan anggota B, maka fungsi pemetaan nilai ini dinotasikan

sebagai , dimana a A dan b B. Llihat Gambar 12 untuk diagram panah dari fungsi ini.

Gambar 12 : Fungsi pemetaan nama mahasiswa kepada nilainya

Notasi fungsi merupakan huruf kecil yang umumnya dimulai dari ,... dan seterusnya. Selainmenggunakan diagram panah seperti Gambar 12 diatas, fungsi juga dapat dijelaskan menggunakan

deskripsi, misal untuk yang akan memetakan anggota X bilangan integer positifkepada anggota Y bilangan integer positif dengan cara . Fungsi memetakan 1 Xkepada 5 Y, atau dapat ditulis dan memetakan 2 X kepada 6 Y atau danseterusnya. Nilai 5 pada didapatkan dengan cara men-subtitusi nilai pada denganangka 1.

X Y

Rudi .

Shinta .

Toni .

Utami .

. A

. B

. C

. D

. E

A B


32/42

Fungsi juga dapat digambarkan dengan Grafik pada diagram cartesian, dimana sumbu x merupakan

domain, sedangkan sumbu y merupakan codomain. Grafik untuk fungsi diatas dapat dilihatpada Gambar 13.

Gambar 13. Grafik fungsi

Fungsi berbeda dengan relasi meskipun keduanya sama-sama memasangkan suatu anggota ke

anggota lain dengan aturan tertentu. Relasi dapat memetakan suatu anggota ke satu atau beberapa

anggota himpunan lain, sedangkan fungsi memetakan suatu anggota tepat ke hanya satu anggota

himpunan lain. Perbedaan ini dapat dipahami dengan mengamati diagram panah antara relasi dan

fungsi pada Gambar 8 dan Gambar 12.

Tipe-tipe pemetaan Fungsi

Fungsi dapat dikategorikan berdasarkan hasil pemetaannya, yakni:

1. Injection atau one-to-one

Adalah sebuah fungsi yang memetakan semua anggota dalam domain kepada tepat satu

anggota himpunan codomain secara unique, dimana tidak ada anggota codomain yang menjadi

tujuan pemetaan dari beberapa anggota domain. Dalam fungsi yang bersifat injective, boleh

terdapat anggota codomain yang tidak menjadi tujuan pemetaan.

Contoh: untuk domain dan codomain adalah bilangan integer positif, 2.

Surjection atau onto

Adalah sebuah fungsi dimana semua anggota dalam codomain menjadi tujuan pemetaan dari

anggota domain. Dalam fungsi surjective boleh terdapat anggota domain yang tidak dipetakan

dan anggota codomain boleh menjadi tujuan pemetaan dari beberapa anggota domain.

0 1 2 3 40

1

2

3

4

5

6

7

8

X

Y


33/42

Contoh: : √ untuk domain dan codomain adalah bilangan integer positif, 3. Bijection atau one-to-one correspondence

Adalah sebuah fungsi yang memetakan secara injection dan surjection.

Contoh: untuk domain dan codomain adalah bilangan integer positif, Gambar 14 menunjukkan contoh tipe-tipe pemetaan suatu fungsi yang memasangkan anggota

domain kepada codomain.

Gambar 14. Contoh tipe-tipe pemetaan

Operasi Fungsi

Fungsi dapat dioperasikan dengan beberapa operator, yakni:

1.

Penjumlahan dan pengurangan Contoh: sebuah fungsi dan fungsi , maka untuk

2.

Perkalian Contoh: sebuah fungsi dan fungsi , maka untuk


34/42

3.

Komposisi

Seperti pada Gambar 15.

Gambar 15. Komposisi fungsi

Dimana akan disubtitusikan kepada fungsi kemudian hasil pemetaannya akandisubstitusikan sebagai pada fungsi .Contoh: sebuah fungsi dan fungsi , maka untuk

() () 4.

Inverse

Jika sebuah fungsi

akan memetakan

kepada

, atau ditulis sebagai

, maka inverse dari . Perhatikan Gambar 16.


35/42

Gambar 16. Inverse suatu fungsi

Sebuah fungsi yang memiliki tipe pemetaan one-to-one correspondence dapat di-invers-kan karena

memiliki tujuan pemetaan yang unique. Jika suatu fungsi memiliki hasil pemetaan yang tidak unique,

maka fungsi tersebut tidak dapat di-invers-kan. Misal terdapat yang akan memetakan ke . Jika dan , maka inverse-nya tidak akan memiliki hasil pemetaanyang unique seperti halnya yang dimaksud dengan fungsi.Beberapa fungsi khusus yang sering digunakan

a.

Fungsi ceil

Fungsi ini akan membulatkan sebuah angka kepada angka yang berada di atasnya, ceil = atap,

dengan notasi ⌈ ⌉. Misal b.

Fungsi floor

Fungsi ini akan membulatkan sebuah angka kepada angka yang berada di bawahnya, floor =

lantai, dengan notasi ⌊ ⌋. Misal


36/42

VI. STRUKTUR DISKRIT: BARIS DAN DERET

Baris (Sequence)

Baris merupakan sebuah himpunan angka yang memiliki urutan dan cara progression tertentu.

Notasi baris adalah atau suku ke-n dimana n adalah bilangan integer positif yang dapat dimulaidari 0 atau 1. Jika sebuah deret memiliki cara pengurutan

Maka baris untuk , , adalah 1, 2, 4, 8Terdapat dua cara pengurutan baris yang sering dijumpai, yakni secara aritmatik dan geometrik.

1.

Baris Aritmatik

Baris ini di enumerasi dengan operasi penjumlahan dengan bilangan tertentu, yakni: , atau

Dengan mengetahui atau sebagai suku pertama serta beda antar suku, maka dapatdiketahui suku ke-n tanpa harus mengenumerasi setiap suku nya satu per satu.

Contoh: diketahui sebuah baris aritmatik dimulai dari suku ke-1 adalah 2, 5, 8, 11... maka

tentukan suku ke-20!

Jawab: = 2 = + ((1-1).b) = 5 = 2 + (1.3) = + ((2-1).) = 8 = 2 + (2.3) = + ((3-1). ) = 11 = 2 + (3.3) = + ((4-1). )Sehingga = + ((20-1). ) = 2 + (19.3) = 59

2.

Baris Geometrik

Baris ini di enumerasi dengan operasi perkalian dengan bilangan tertentu, yakni: , atau


37/42

Dengan mengetahui atau sebagai suku pertama serta sebagai rasio antar suku, makadapat diketahui suku ke-n tanpa harus mengenumerasi setiap suku nya satu per satu.

Contoh: diketahui sebuah baris geometrik dimulai dari suku ke-0 adalah 3, 6, 12, 24... maka

tentukan suku ke-20!

Jawab:= 3 = = 6 = 3. = = 12 = 3. = = 24 = 3. = Sehingga = = = 3145728

Baris yang Rekursif

Baris memiliki relasi rekursif jika dalam progression-nya melibatkan suku-suku sebelumnya. Baris ini juga

banyak ditemui di komputasi. Contoh baris yang bersifat rekursif adalah:

Sehingga untuk = 2, maka didapatkan:

, dan

Baris Fibonacci

Baris Fibonacci adalah sebuah baris rekursif yang memiliki , dan:

Untuk n = 2, 3, 4,...

Deret (Summation)

Deret adalah jumlah dari suatu baris hingga suku ke- n yang dinotasikan sebagai:


38/42

Dimana disebut sebagai index, adalah batas bawah dan adalah batas atas.Contoh: sebuah baris , tentukan deret ke-3!Jawab:

Terdapat dua deret yang sering dijumpai, yakni:

1. Deret Aritmatik

Yakni sebuah deret dari barisan aritmatik.

Untuk baris yang dimulai dari .

2. Deret Geometrik

Yakni sebuah deret dari barisa geometrik.

Untuk baris yang dimulai dari dan .

Selain dua deret diatas, terdapat beberapa deret khusus yang akan sering dijumpai yakni pada Tabel *.

Pada Tabel tersebut, beberapa deret memiliki persamaan yang ekivalen sehingga dapat digunakan untuk

perhitungan lebih lanjut.


39/42

Tabel 17. Beberapa Persamaan untuk Deret Khusus


40/42

VII. INDUKSI MATEMATIKA

Perhatikan persamaan ekivalensi untuk beberapa deret khusus pada Tabel 17 diatas. Membuktikan

apakah persamaan tersebut adalah benar untuk deret hingga suku ke- yang relatif kecil, sebut sajasampai suku ke-5, maka dapat dilakukan secara manual. Contoh pada persamaan deret baris kedua di

Tabel 17 dimana baris dari deret tersebut adalah 1, 2, 3, 4, 5, 6, 7, 8, dst, sehingga deret ke-5 dihitung

sebagai berikut:

Sehingga telah dibuktikan bahwa deret suku ke-5 dan persamaan ekivalensi-nya menghasilkan nilai yang

sama, 15. Namun untuk membuktikan bahwa persamaan tersebut adalah benar untuk semua integerpositif, tidaklah efektif jika dilakukan secara manual.

Dalam matematika, terdapat langkah pembuktian terhadap suatu persamaan apakah akan berlaku

untuk semua anggota dalam domain-nya. Langkah pembuktian ini disebut dengan induksi matematika.

Induksi merupakan salah satu cara penarikan kesimpulan oleh manusia selain deduksi dan abduksi. Cara

ini dilakukan manusia dengan mengumpulkan beberapa fakta saja, kemudian memberlakukannya pada

semua domain.

Terdapat dua langkah pengujian dalam melakukan induksi matematika, yakni:

1.

Basis step (langkah basis)

Persamaan tersebut diuji pada suku pertama, yang dapat dimulai dari = 1 atau = 0. Daricontoh diatas, untuk = 1 maka didapati:

, dan

Baik melalui perhitungan deret (sisi kiri) maupun persamaan ekivalensi nya (sisi kanan), didapat

hasil yang sama yakni 1. Sehinggabasis step terpenuhi

2.

Inductive step (langkah induktif)

Setelah menguji basis step, maka langkah selanjutany adalah inductive step. Langkah ini menguji

apakah persamaan tersebut yang berlaku pada deret ke- juga berlaku untuk deret ke- .Sisi kiri menunjukkan pembuktian dengan men-subtitusi dengan . Sedangkan sisi kananmenunjukkan pembuktian dengan menambah satu suku berikutnya dari deret ke—.


41/42

Cara 1. Subtitusi dengan -

( )

Cara 2. Tambahkan dengan untukmenghasilkan

Karena Maka satu suku berikutnya adalah:

Sehingga:

Baik melalui subtitusi (sisi kiri) maupun penambahan suku selanjutnya (sisi kanan), didapat hasil

yang sama yakni . Sehingga inductive step terpenuhi.

Jika kedua pengujian pada basis step dan inductive step terpenuhi, maka dapat disimpulkan bawah

persamaan ∑ adalah benar untuk semua integer positif dari 1 sampai tak hingga.Contoh. Buktikan bahwa hasil penjumlahan baris bilangan ganjil integer positif hingga suku ke-n adalah

sama dengan !Jawab:

Diketahui bahwa baris bilangan ganjil integer positif adalah 1, 3, 5, 7, 9, ... dst

1.

Basis step

, dan Terpenuhi √


42/42

2.

Inductive step

Cara 1. Subtitusi dengan -

Cara 2. Tambahkan dengan untukmenghasilkan

Karena Maka satu suku berikutnya dengan nilai = 2adalah:

Sehingga:

Terpenuhi √

Karena kedua pengujian terpenuhi , maka dapat disimpilkan bahwa adalah benar bahwa hasil

penjumlahan baris bilangan ganjil integer positif hingga suku ke-n untuk semua integer adalah sama

dengan .

modul ajar matematika komputasi 6

Documents