Discrete Mathematics

I. FINITE STATE AUTOMATA (FSA)

FINITE STATE AUTOMATA (FSA)

⇒ Finite state merupakan sebuah mesin abstrak berupa system model matematika
dengan input dan output diskrit yang dapat diimplementasikan secara nyata dimana
system dapat berada di salah satu dari sejumlah konfigurasi internal yang disebut state.
Beberapa contoh untuk system dengan state adalah vending machine, lampu lalu lintas
dan lexical analyser.

⇒ Sebuah finite automata terdiri dari beberapa bagian, yaitu sekumpulan state dan
aturan-aturan perpindahan dari satu state ke state lainnya, yang bergantung dari symbol
yang ada. Definisi lain dari finite automata adalah finite automata merupakan list dari 5
komponen : kumpulan state, input, aturan perpindahan, state awal, dan state akhir.

DETERMINISTIC FINITE AUTOMATA (DFA)

⇒ DFA(Deterministic Finite Automata) aturan perpindahan dapat juga disebut fungsi
transisi, yang dilambangkan dengan f. Berikut pembahasan tentang 5 komponen DFA :
M = (S, I, f, s0, F) S – adalah himpunan set berhingga yang disebut dengan himpunan
states. I – adalah himpunan alfabet berhingga dari sebuah symbol. f : S x I – adalah
fungsi transisi, dimana ia mengambil states dan alfabet input sebagai argument dan
menghasilkan sebuah state. s0 – adalah state awal. F ⊆ S – adalah himpunan states
akhir.
 PENYAJIAN FSA

1. Diagram Transisi

● Diagram Transisi untuk finite automata M = (S, I, f, s0, F) adalah sebagai berikut :
● Terdapat simpul untuk setiap state S.
● Untuk setiap state s ε S dan setiap symbol input a ε I, berlaku f(s, a) = p.
● Diagram transisi memiliki busur berlabel a dari state q ke state p.
● Terdapat anak panah “start” yang mengarah ke state awal s0 dan anak panah
tersebut tidak berasal dari state manapun.
● State akhir(F) akan ditandai dengan lingkaran ganda, sedangkan yang lain hanya
lingkaran tunggal.

Contoh:

2. Tabel Transisi

Tabel Transisi merupakan representasi tabular dari fungsi f yang mengambil dua
argumen dan menghasilkan suatu nilai. Baris pada tabel berkorespondesi dengan state
dan kolom pada tabel berkorespondesi dengan input. Contoh:
Keterangan :

● Simbol pada kolom sebelah kiri adalah state.

● Simbol pada baris paling atas adalah symbol.
● Simbol yang ada di dalam tabel merupakan fungsi transisi.
● Simbol panah (->) di sebelah kiri menunjukkan symbol start.
● Simbol bintang (*) di sebelah kiri menunjukkan final state.

NON-DETERMINISTIC FINITE AUTOMATA

⇒ adalah sebuah pelonggaran dari aturan DFA yang sangat ketat.

Suatu non-determistic finite automata tersusun quintuple M = (S, I, f, s0, F) dimana :

S – adalah himpunan dari beberapa states.

I – adalah input alfabet.

f : S x I = P(S) – adalah relasi transisi.

s0 – adalah state awal.

F – adalah himpunan states akhir.

Diketahui suatu NFA M = (S, I, f, s0, F) dimana Q = {q0,q1,q2}, I = {0,1}, F = {q1}, dan f
adalah fungsi yang didefinisikan sesuai tabel dibawah.
Contoh:

Consider the state diagram NFA shown: a. Find the state table b. Find the language
recognized by this NFA

Solution: a. State Table

𝑛 𝑛 𝑛
b. The language recognized by the machine is {0 , 0 01, 0 11 | n≥0 }.
Perbedaan NFA Dan DFA
NFA dan DFA memiliki beberapa perbedaan, antara lain:

● NFA memungkinkan satu symbol menimbulkan transisi ke lebih dari satu state,
sedangkan dalam DFA untuk setiap state s dan symbol a hanya ada paling
banyak satu label a yang meninggalkan state s.
● NFA memungkinkan transisi spontan yang selanjutnya akan diistilahkan menjadi
ǫ-NFA.

Regular Expression
Ekspresi reguler dalam himpunan I didefinisikan sebagai berikut :

● symbol ∅ was regular expression

∅ represents the empty set, that is the set with no strings.

● symbol λ was regular expression

Λ represents the set {λ}, which is the set that contains the empty strings.

● symbol x was a regular expression whenever x∈ I

x represents the set {x} containing the string with one symbol x.

¿
● symbol( AB), ( A∪B), ∧ 𝐴 was a regular expression whenever A∧B was a
regular expression

(AB) represent the concatenation of the sets represented by A and by B.

( A∪B) represent the union of the sets represented by A and by B.

¿
𝐴 represents the Kleene closure of the set represented by A.
II. FUNGSI, REKURIS, FUZZY SET
Fungsi F dari himpunan X ke Y adalah hubungan dimana setiap anggota X dipasangkan
dengan satu anggota Y.

Contoh:
F=A→B
A = domain atau daerah asal
B = kodomain atau daerah kawan

Dua gambar di bawah bukan fungsi karena ada anggota di A memiliki 2 pasangan dan ada
anggota yang tidak memiliki pasangan.
 Fungsi Injektif (satu-satu)
Fungsi injektif adalah fungsi dengan tiap elemen kodomain tidak mempunyai relasi lebih
dari satu dengan elemen domain.

Fungsi Surjektif (on-to)

Fungsi surjektif adalah fungsi dengan semua elemen kodomain berelasi dengan elemen
domain.

Fungsi Bijektif (Korespondensi satu-satu)

Fungsi Bijektif adalah fungsi yang memenuhi sifat injektif dan surjektif. Disebut
korespondensi satu-satu karena setiap anggota domain dan kodomain memiliki tepat satu
pasangan (berkorespondensi satu-satu).
 Fungsi Invers
Fungsi invers atau fungsi kebalikan merupakan suatu fungsi yang berkebalikan dari
fungsi asalnya.

Fungsi Komposisi
Fungsi komposisi adalah fungsi yang melibatkan dari suatu fungsi. Misalkan terdapat
fungsi f(x) dan g(x). Jika g(x) dilanjutkan ke dalam f(x), maka hal tersebut adalah f
komposisi g atau f bundaran g {(f o g)(x)}.
Untuk bentuk lebih mudahnya = f(g(x))
Himpunan Fuzzy
Himpunan Fuzzy adalah suatu grup yang mewakili suatu kondisi atau keadaan tertentu
dalam suatu variabel fuzzy.
Contoh: variabel usia dibagi menjadi 3, muda, paruh baya, dan tua.
Himpunan Fuzzy mempunyai nilai keanggotaan dalam interval 0 sampai 1.
0 untuk x ≤ a
(x-a)/(b-a) untuk a ≤ x ≤ b
1 untuk b ≤ x ≤ c
(d-x)/(d-c) untuk c ≤ x ≤ d
0 untuk x ≥ d

Operasi Himpunan Fuzzy

● Komplemen:
Ā(x) = 1 - A(x)
Contoh:
A(x) = x-6, Ā(x) = -x+7

● Union:
(A B)(x) max[A(x), B(x)] untuk semua x
Contoh:
A(x) = 0/5,75 + 0/6 + 0,25/6,25 + 0,5/6,5 + 0,75/6,75 + 1/7 + 0,75/7,25 +
0,5/7,5
Komplemennya:
Ā(x) = 1/5,75 + 1/6 + 0,75/6,25 + 0,5/6,5 + 0,25/6,75 + 0/7 + 0,25/7,25 +
0,5/7,5
Maka:
(A A)(x) = 1/5,75 + 1/6 + 0,75/6,25 + 0,5/6,5 + 0,75/6,75 + 1/7 + 0,75/7,25 +
0,5/7,5

● Irisan:
(A B)(x) min A(x), B(x) untuk semua x
Contoh:
A(x) = 0/5,75 + 0/6 + 0,25/6,25 + 0,5/6,5 + 0,75/6,75 + 1/7 + 0,75/7,25 +
0,5/7,5
Komplemennya:
Ā(x) = 1/5,75 + 1/6 + 0,75/6,25 + 0,5/6,5 + 0,25/6,75 + 0/7 + 0,25/7,25 +
0,5/7,5
Maka:
(A A)(x) = 0/5,75 + 0/6 + 0,25/6,25 + 0,5/6,5 + 0,25/6,75 + 0/7 + 0,25/7,25 +
0,5/7,5

Support Set
Support set adalah himpunan dari elemen-elemen yang nilai keanggotaannya lebih
besar dari 0.
Supp(A) = {x X A(x) > 0}
 A(x) = 0/5,75 + 0/6 + 0,25/6,25 + 0,5/6,5 + 0,75/6,75 + 1/7 + 0,75/7,25
+ 0,5/7,5

Supp A = {6.25, 6.5, 6.75, 7, 7.25, 7.5}

Himpunan Terpotong
Contoh:

A(x) = 0/5,75 + 0/6 + 0,25/6,25 + 0,5/6,5 + 0,75/6,75 + 1/7 + 0,75/7,25

+ 0,5/7,5

F0,3 = {6.5, 6.75, 7, 7.25, 7.5}

III. GRAPH

Definisi
→Himpunan pasangan titik(simpul) dan garis(sisi) yang ditulis dengan notasi G = (V,E)
Keterangan :
V = vertex / titik / simpul -> himpunan tidak kosong dari simpul-simpul = {
𝑉1, 𝑉2, 𝑉3, . . ., 𝑉𝑛 }
E = edges / sisi / garis -> himpunan sisi yang menghubungkan sepasang simpul = {
𝑒1, 𝑒2, 𝑒3, . . . , 𝑒𝑛}

Himpunan sisi E (sisi) dapat berupa himpunan kosong, graph tersebut dinamakan graph
kosong (empty graph / null graph).

Ex :
Graph kosong dengan 3 simpul:

Note :
● Sebuah simpul dapat berdiri sendiri
tanpa sisi.
● Sebuah sisi tidak dapat berdiri sendiri
(minimal memiliki satu simpul)
 LOOP (GELANG)
Loop adalah sisi yang menghubungkan suatu simpul dengan dirinya sendiri.

SISI GANDA / SISI RANGKAP

→Suatu keadaan dimana terdapat lebih dari satu sisi yang menghubungkan dua buah
simpul.
Keterangan :
Merah : Sisi rangkap
Kuning : Sisi loop

JENIS-JENIS GRAPH
● Graph Tak-Berarah (Undirected Graphs)
● Graph yang tidak memiliki arah berupa tanda panah pada sisinya.
● Graph Berarah (Directed Graph)
● Graph yang memiliki arah berupa tanda panah pada sisinya.

Jenis Sisi Sisi Ganda Sisi Loop

Diperbolehkan Diperbolehkan
Graph Tak-Berarah Tak berarah Tidak Tidak
Sederhana (Simple
Undirected Graph)

Graph Ganda Tak- Tak berarah Ya Tidak

Berarah (Undirected
Multigraph)

Graph Semu Tak berarah Ya Ya

(Pseudograph)

Graph Berarah Berarah Tidak Tidak

Sederhana (Simple
Directed Graph)

Graph Berarah Berarah Ya Ya

Ganda
(Directed Multigraph)

Graph Campuran Tak berarah Ya Ya

(Mixed Graph)

Graph Tak-Berarah Sederhana (Simple Undirected Graph)

Graph Ganda Tak-Berarah (Undirected Multigraph)

Graph Semu (Pseudograph)

Graph Berarah Sederhana (Simple Directed Graph)

Graph Berarah Ganda (Directed Multigraph)

Graph Campuran (Mixed Graph)

BEBERAPA GRAPH SEDERHANA KHUSUS

1. Complete Graph : 𝐾𝑛

Complete Graph adalah sebuah graph sederhana yang setiap simpulnya terhubung ke
semua simpul lainnya. Complete graph dengan n buah simpul dilambangkan dengan
𝑛(𝑛−1)
Kn. Jumlah sisi pada complete graph yang terdiri dari n buah simpul adalah 2
sisi.

Ex :
Complete graph dengan 𝐾𝑛, dengan 1 ≤ 𝑛 ≤ 6
2. Siklus
Sebuah siklus 𝐶𝑛, n ≥ 3, terdiri dari n simpul 𝑉1, 𝑉2, . . . , 𝑉𝑛 dan sisi { 𝑉1, 𝑉2}, { 𝑉2, 𝑉3},
... , { 𝑉𝑛−1, 𝑉𝑛}, dan { 𝑉𝑛, 𝑉1}.
Contoh:

3. Roda
Sebuah roda 𝑊𝑛, saat kita menambahkan siklus tambahan ke siklus 𝐶𝑛, untuk n ≥ 3,
dan hubungkan simpul bar uke masing-masing n simpul pada 𝐶𝑛, dengan sisi baru.
Contoh:

4. Kubus berdimensi-n

Hypercube berdimensi-n, dilambangkan dengan 𝑄𝑛, adalah graph yang memiliki

𝑛
simpul-simpul yang merepresentasikan string 2 dengan panjang n. Dua simpul
berdekatan jika dan hanya jika string bit yang mereka wakili berbeda tepat dalam satu
posisi bit.
Contoh:
 GRAPH BIPARTIT

→berarti dibagi menjadi dua, yaitu kelompok 𝑉1 dan kelompok 𝑉2. Setiap anggota
𝑉1 saling terhubung dengan anggota 𝑉2. Tetapi setiap anggota kelompok tidak terhubung
dengan
teman kelompoknya. Notasi graph bipartit : G(𝑉1, 𝑉2 ).

Contoh :
Graph dibawah ini dapat direpresentasikan menjadi graph bipartite (𝑉1, 𝑉2), dimana 𝑉1 =
{a, b} dan 𝑉2 = {c, d, e}.

GRAPH BIPARTIT LENGKAP : K m,n

→ graph yang pada himpunan puncaknya terbagi menjadi dua, yaitu himpunan bagian
dari simpul m dan n, masing-masing dengan sisi diantara dua simpul jika dan hanya jika
satu simpul ada di himpunan bagian pertama dan simpul lainnya pada subset kedua.

Contoh:
 Setiap simpul merah terhubung dengan seluruh simpul hijau.

REPRESENTASI GRAPH DAN ISOMORFISME

● Bertetangga (Adjacent)

Dua buah simpul dikatakan bertetangga jika kedua simpul tersebut terhubung
langsung oleh suatu sisi.

Contoh :

● Bersisian (Insidency)
Suatu sisi e dikatakan bersisian dengan simpul V1 dan V2, jika e menghubungkan
kedua simpul tersebut. Dengan kata lain e = (V1, V1). Ex :
 MATRIKS KETETANGAAN (Adjacency Matrix)
Dua buah simpul dikatakan bertetangga, jika kedua simpul tersebut terhubung langsung
oleh suatu sisi. Matriks ketetanggaan untuk graph sederhana merupakan matriks bujur
sangkar yang unsur-unsurnya hanya terdiri dari dua bilangan yaitu 0 dan 1. Baris dan
kolom pada matriks ini, masing-masing merupakan representasi dari setiap simpul pada
graph tersebut. Misal aij merupakan unsur pada matriks tersebut, maka :

● Jika aij = 1 berarti simpul I dan simpul j bertetangga.

● Jika aij = 0 berarti simpul I dan simpul j tidak bertetangga.

Contoh:

MATRIKS INSIDEN
→matriks pertemuan antara simpul
dan sisi. Contoh:

ISOMORFIK
Sifat – sifat graph isomorfik :
● Dua buah graph dikatakan isomorfik jika memenuhi syarat :
● Memiliki jumlah simpul yang sama.
● Memiliki jumlah sisi yang sama.
● Memiliki simpul atau simpul tertentu berderajat sama.
● Memiliki matriks ketetanggaan yang sama.
Contoh:
Tentukan apakah graph G dan H berikut ini adalah isomorfik!

Jawab:
1. Jumlah simpul graph G = H = 6
2. Jumlah sisi graph G = H = 7
3. Derajat tiap simpul graph G = H = 2
4. Matriks ketetanggaan :

Matriks

ketetanggaan kedua graph tersebut sama, sehingga dapat disimpulkan

bahwa kedua graph tersebut adalah isomorfik.

LINTASAN EULER DAN SIRKUIT EULER

Lintasan Euler dari simpul V ke W adalah sederetan sisi-simpul berawal dari V
dan berakhir di W, melewati keseluruhan simpul setidaknya sekali, dan melintasi
setiap sisi tepat satu kali.

Sirkuit Euler adalah lintasan tertutup yang melewati tiap sisi pada graph tepat
satu kali dan paling sedikit tiap simpul dilewati sekali.

TEOREMA 1 : Multigraph terhubung yang memiliki dua simpul atau lebih

disebut mempunyai sirkuit Euler, jika dan hanya jika tiap simpulnya memiliki
derajat genap.

TEOREMA 2 : Multigraph terhubung disebut memiliki lintasan Euler tetapi

tidak memiliki sirkuit Euler, jika dan hanya jika tepat memiliki simpul berderajat
ganjil.

Contoh :

Manakah diantara graph berikut ini yang memiliki sirkuit Euler ? Manakah
yang memiliki lintasan Euler?

● G1 memiliki sirkuit Euler, yaitu : a, e, c, d, e, b, a.

● G2 dan G3 tidak memilki sirkuit Euler.
● G3 memiliki lintasan Euler, yaitu : a, c, d, e, b, d, a, b.
● G2 tidak memilki lintasan Euler.

IV. LOGIKA PERNYATAAN

Logika pernyataan adalah pernyataan yang hanya bisa benar atau salah, tapi tidak bisa
dua-duanya (benar dan salah).

Contoh yang benar:

● Tujuh dikurang tiga hasilnya empat

● Semua manusia membutuhkan oksigen.

Contoh yang salah:

● Berikan saya barang itu!

● x+y>0

Negasi
Negasi adalah suatu pernyataan yang meniadakan pernyataan yang ada.

Contoh:

● p = Semua manusia membutuhkan oksigen.

● ~p = Semua manusia tidak membutuhkan oksigen.
Tabel kebenaran negasi:

p ~p

T F

Pernyataan Gabungan
Beberapa pernyataan dapat digabung dengan kata penghubung dan, atau, tidak/bukan,
dan lainnya.

1. Konjungsi “AND” (Λ):

p q pΛq

T T T

T F F

F T F

F F F

Tips: hanya “TRUE” jika semua pernyataan “TRUE”

2. Konjungsi “OR” (∨):

p q p∨q

T T T

T F T

F T T

F F F

Tips: hanya “FALSE” jika semua pernyataan “FALSE”

Pernyataan Bersyarat
 1. Implikasi/kondisional (→):

p q p→q

T T T

T F F

F T T

F F T

Tips: hanya “FALSE” jika p=”TRUE” dan q=”FALSE”

2. Biimplikasi/bikondisional (⇿):

p q p⇿q

T T T

T F F

F T F

F F T

Tips: hanya “TRUE” jika p dan q memiliki nilai kebenaran yang sama.

Implikasi, Invers, Konvers, dan Kontrapositif

Implikasi: p → q

Invers: ~p → ~q

Konvers: q → p

Kontrapositif: ~q → ~p

- - - - Implikasi Invers Konvers Kontrapositif

p q ~p ~q p→q ~p → ~q q→p ~q → ~p

T T F F T T T T
 T F F T F T T F

F T T F T F F T

F F T T T T T T

Kesimpulan:

● Implikasi memiliki nilai kebenaran yang sama dengan kontrapositif.

● invers memiliki nilai kebenaran yang sama dengan konvers.

Kesetaraan Logika
1. p → q ≡ ~p ∨ q ≡ ~q → ~p
2. p ⇿ q ≡ (p → q) Λ (q → p)
3. ~(~p) ≡ p
4. ~(p Λ q) ≡ ~p ∨ ~q
5. ~(p ∨ q) ≡ ~p Λ ~q
6. ~(p → q) ≡ p Λ ~q
7. ~(p ⇿ q) **≡ (~**p ⇿ q) **≡ (**p ⇿ ~q)

Algebra Dari Pernyataan

1. Hukum Komutatif : p Λ q ≡ q Λ p, p ∨ q ≡ q ∨ p
2. Hukum Asosiatif : (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
3. Hukum Distributif : p Λ (q ∨ r) ≡ (p Λ q) ∨ (p Λ r)
4. Hukum Identitas : p Λ T ≡ p, p ∨ F ≡ p, p ∨ T ≡ T, p Λ F ≡ F
5. Hukum Komplemen : p ∨ ~p ≡ T, p Λ ~p ≡ F
6. Hukum Involusi : ~(~p) ≡ p
7. Hukum Idempoten : p Λ p ≡ p, p ∨ p ≡ p
8. Hukum De Morgan : ~(p Λ q) ≡ ~p ∨ ~q, ~(p ∨ q) ≡ ~p Λ ~q
9. Hukum Absorbsi : p ∨ (pΛq) ≡ p

Bentuk-Bentuk Dasar Menarik Kesimpulan

1. Modus Ponens:

p→q

p
 ∴q

2. Modus Tollens:

p→q

~q

∴ ~p

3. Syllogism:

p→q

q→r

∴p→r

4. Eliminasi:

p∨q

~p

∴q

atau

p∨q

~q

∴p

5. Generalisasi:

∴p∨q

atau

q
 ∴p∨q

6. Spesialisasi:

pΛq

∴p

atau

pΛq

∴q

7. Proof by division into classes:

p→r

q→r

p∨q

∴r

8. Kontradiksi:

~p → false

∴p

Gerbang Dasar Not, And, Or

Contoh:

Jawaban: (p ∨ q) Λ ~(p Λ q)

Karnaugh Map
adalah suatu metode untuk menyederhanakan ekspresi boolean algebra.

Dua variabel:

Contoh:

A. xy + xy’
B. xy + x’y + x’y’
C. xy + x’y’

Tiga variabel:
Contoh: xyz + xyz’ + xy’z + x’yz + x’y’z

Empat variabel:
 Contoh: xyzt + xyz’t + xy’zt’ + x’y’zt + x’y’zt’ + x’y’z’t’ + x’y’z’t + x’yzt + x’yz’t

V. METHOD OF PROOF
Method of proof adalah cara-cara untuk membuktikan suatu pernyataan.

Metode Pembuktian Langsung

Pembuktian Langsung dalam matematika dilakukan dengan menguraikan premis
dengan dilandasi oleh definisi, fakta, aksioma yang ada untuk sampai pada suatu
kesimpulan (konklusi).

Contoh: Jika A maka B. Jika C maka D

Definisi Bilangan Genap

Suatu bilangan bulat n disebut bilangan genap jika terdapat sebuah bilangan bulat k
sehingga:

n = 2k

Contoh:

Buktikan: “Jika n adalah bilangan genap, maka n² adalah bilangan genap”

Misal n = 2m, maka

n² = 4m² = 2(2m²) ≈ 2k

→Terbukti

Buktikan “Jumlah dua bilangan genap adalah bilangan genap” Misal m = 2p dan n = 2q ,
dimana p dan q adalah bilangan bulat.

Maka m + n = 2p + 2q = 2 (p + q) ≈ 2k

→terbukti

Definisi Bilangan Ganjil

Suatu bilangan bulat n disebut bilangan ganjil jika terdapat sebuah bilangan bulat k
sehingga:
n = 2k + 1

Contoh:

Buktikan “Jumlah bilangan genap dan bilangan ganjil adalah bilangan ganjil”

Misal m = 2p dan n = 2k + 1

Maka:

m + n = 2p + 2k + 1

= 2(p + k) + 1

Misal p + k = i, maka:

2(p + k) + 1 = 2i + 1 (bentuk bilangan ganjil)

→terbukti

Metode Pembuktian Tidak Langsung

Pembuktian tidak langsung terdapat 2 cara, yaitu:

1. Kontraposisi

Pembuktian tidak langsung kontraposisi digunakan untuk membuktikan

pernyataan implikasi.

Secara simbolik:

p → q ≡ ~q → ~p

Contoh:

Buktikan “Jika n² bilangan ganjil, maka n bilangan ganjil”

Dengan kontraposisi, maka bisa kita bilang juga “Jika n bilangan genap, maka n²
bilangan genap”

Misal n = 2k, maka:

n² = (2k)²
 n² = 4k² → n² = 2(2k²)

Misal 2k² = i, maka:

n² = 2i → bentuk bilangan genap

Karena kontraposisinya sudah terbukti, maka pernyataan “Jika n² bilangan

ganjil, maka n bilangan ganjil” adalah benar.

2. Kontradiksi

Buktikan “Jika n bilangan bulat dan n bilangan genap maka 7n + 9 adalah

bilangan ganjil”

Kontradiksi: “Jika n bilangan bulat dan n bilangan ganjil maka 7n + 9 adalah

bilangan ganjil”

misal n = 2k + 1, maka:

7n + 9 = 7(2k+1) + 9 → 14k + 16

14k + 16 = 2(7k + 8)

Misal 7k + 8 = i, maka:

2(7k + 8) = 2i → bentuk bilangan genap

Karena kontradiksi salah, maka pernyataan pertama terbukti benar.

Contoh Penyangkal (Counterexample)

Buktikan bahwa “Setiap bilangan bulat positif adalah hasil tambah dari tiga bilangan
kuadrat” adalah SALAH.

1 = 02 + 02 + 12 (benar)

2 = 02 + 12 + 12 (benar)

3 = 12 + 12 + 12 (benar)

4 = 02 + 02 + 22 (benar)

5 = 02 + 12 + 22 (benar)
6 = 12 + 12 + 22 (benar)

7 = tidak bisa
Jadi, bilangan bulat positif 7 adalah contoh penyangkal dari pernyataan tersebut.

Induksi Matematika
Induksi matematika adalah salah satu metode untuk membuktikan suatu pernyataan
tertentu yang berlaku untuk bilangan asli.

Prinsip dari induksi matematika:

1. Membuktikan suatu pernyataan benar untuk n = 1

2. Mengasumsikan suatu pernyataan benar untuk n = k
3. Membuktikan pernyataan tersebut benar untuk n = k + 1

Contoh:

● Buktikan bahwa : “1 + 3 + 5 + ... + (2n-1) = n2, untuk semua bilangan asli n”.
1. n = 1 → 2(1) - 1 = 12 (BENAR)
2. n = k → 1 + 3 + 5 + ... + (2k-1) = k2
3. n = k+1 → 1 + 3 + 5 + ... + (2k-1) + (2(k+1)-1) = (k+1)2

k2 + 2k+1 = (k+1)2

(k+1)2 = (k+1)2 (TERBUKTI)

● Buktikan 52n + 3n - 1 habis dibagi 9, untuk setiap n bilangan asli.

1. n = 1 → 52 +3 - 1 = 27 (BENAR)
2. n = k → 52k + 3k -1 = 9a (a adalah hasil setelah 52k + 3k -1 dibagi 9)
3. n = k+1 → 52k+2 + 3k + 2

= 25(52k) +3k + 2

Gantikan 52k menjadi 52k + 3k - 1

25(52k + 3k - 1) - 75k + 25 +3k + 2

25(9a) - 72k + 27

9(25a - 8k + 3) (TERBUKTI)
VI. PENCACAHAN

BEBERAPA PENGERTIAN DASAR

PELUANG (PROBABILITY) : ukuran numerik tentang suatu peristiwa
yang dapat terjadi.

Contoh :
Melempar sebuah koin satu kali
Peluang munculnya gambar : P(gambar) = 0,5
Peluang munculnya angka : P(angka) = 0,5
P(gambar) + P(angka) = 0,5 + 0,5 = 1

EXPERIMENT (percobaan) : memberi perlakuan (treatment) terhadap sesuatu. Contoh :

mengocok kartu bridge, melempar dadu, memberi obat perangsang.

RUANG SAMPEL (S) : himpunan dari semua kemungkinan yang dapat terjadi dalam
suatu eksperimen. Contoh : melempar sebuah koin dua kali berturut-turut, dimana H =
Head dan T = Tail.
Ruang sampelnya : S ={HH, HT, TH, TT}

EVENT (kejadian/peristiwa) : himpunan bagian dari ruang sampel yang mempunyai ciri
tertentu. Contoh : kejadian sekurang-kurangnya satu H muncul jika sebuah koin dilempar
dua kali berturut-turut. Kejadiannya : A = {HH, HT, TH}

HUKUM-HUKUM DASAR PELUANG

[Link] SUATU KEJADIAN

P(A) + P(AC) = 1 → atau P(A) = 1 – P(AC)

Contoh : Sebuah koin dilempar 3 kali. Berapa peluang sedikitnya satu

H muncul ? Jawab :
A = paling sedikit satu H
muncul A c = tidak ada H
yang muncul
Ruang sampel : S = {TTT, TTH, THT, HTT, THH, HTH, HHT, HHH}
P(AC) = P(TTT) = 1/8
P(A) = 1 – P(A) = 1 – (1/8) = ⅞
 [Link] DUA

A ∩ B = {x│xϵA dan xϵB}

[Link] DUA

A U B = {x│xϵA atau xϵB}

RUMUS : P(AUB) =P(A) + P(B) – P(A∩B)

[Link] TERPISAH (MUTUALLY EXCLUSIVE)

Jika kejadian A muncul, maka B tidak muncul. Demikian pula, jika B muncul,
maka A tidak muncul. Jadi kejadian A dan B tidak dapat muncul bersamaan.

P(A∩B) = 0
RUMUS : P(AUB) = P(A) + P(B)
PENCACAHAN
→merupakan bagian dari teori peluang yang terdiri dari aturan perkalian,
aturan penjumlahan, kombinasi dan permutasi.

ATURAN PERKALIAN
Digunakan untuk mengetahui banyaknya cara yang dapat digunakan jika terdapat n1 cara
pada kejadian pertama, dan masing-masing kejadian pertama tersebut memiliki n2 cara.
Sehingga banyaknya cara keseluruhan = n1 x n2.

Contoh 1 :
Audy mengunjungi super market mobil untuk membeli sebuah mobil. Ternyata ada 8
merek yang dipajang, masing-masing mempunyai 5 pilihan warna. Berapa cara Audy
untuk memilih merek dan warna mobil tersebut ?
Jawab : 𝑛1= 8 ; 𝑛2= 5
Banyaknya cara Audy memilih merek dan warna mobil = 8 x 5 = 40 cara.

Contoh 2 :
Akan dibuat PIN (Personal Identification Number) 4 digit yang disusun dari huruf A s/d Z
dan angka 0 s/d 9, boleh ada pengulangan. Berapa banyak PIN yang dapat dibuat ?
Jawab :
Jumlah huruf = 26 ;
Jumlah angka = 10 Jumlah (huruf + angka) = 26 + 10 = 36
Maka, banyaknya pin yg dapat dibuat = (36)(36)(36)(36) = 1679616 PIN

ATURAN PENJUMLAHAN
Digunakan untuk mengetahui banyaknya cara yang dapat digunakan jika terdapat n1 cara
pada kejadian pertama dan n2 cara pada kejadian kedua.
Banyaknya cara keseluruhan = n1 + n2.

Contoh :
Tentukan banyaknya cara keseluruhan untuk mengenakan baju jika memiliki 20 baju
lengan pendek dan 15 baju lengan panjang.
Jawab : 𝑛1 = 20 ; 𝑛2 = 15
Maka, banyaknya cara keseluruhan mengenakan baju = 20 + 15 = 35

KOMBINASI
Banyaknya susunan, tanpa memperhatikan urutannya, yang mungkin dapat
dibentuk dari n obyek yang diambil dari N obyek yang lebih besar.

𝑛!
Rumus: C(n,r) =
𝑟!(𝑛−𝑟)!
 Contoh : Berapa banyak kombinasi 3 huruf yang diambil dari huruf-huruf : A, B,
C, D ?
Jawab :
n=4;r=3
4!
C(4,3) = =4
3!(4−3)!

Kombinasinya adalah : ABC, ABD, ACD, BCD.

PERMUTASI
Banyaknya urutan yang dapat dibentuk dari n obyek yang diambil dari N obyek yang
lebih besar.

𝑛!
RUMUS : P(n,r) =
(𝑛−𝑟)!

Contoh 1

Berapa banyaknya permutasi 3 huruf yang diambil dari huruf-huruf : A, B, C, D ?

Jawab : n = 4 ; r = 3
4!
P(4,3) = = 24
(4−3)!

PERBEDAAN KOMBINASI (4) DAN PERMUTASI (24) :

KOMBINASI (4) PERMUTASI (24)

ABC ABC, ACB, BAC,

ABD BCA, CAB, CBA,
ACD ABD, ADB, BAD,
BCD BDA, DAB, DBA ,
ACD, ADC, CAD,
CDA, DAC, DCA
BCD, BDC, CBD,
CDB, DBC, DCB
 Contoh 2 :
Tiga orang kandidat dicalonkan untuk mengisi dua pos jabatan menteri. Tentukan banyaknya
cara untuk memilih dua menteri dari tiga orang kandidat tersebut, dengan menggunakan
rumus permutasi.

Jawab :
P(3, 2), dengan n = 3 (banyaknya kandidat) dan r = 2 (banyaknya pos jabatan menteri).
3!
P(3,2) = =6
(3−2)!
Jadi, terdapat 6 cara.

Misal pada kata “BUKU” terdapat dua huruf yang

sama, yaitu U.
Hasil dari permutasi kata “BUKU” (dengan adanya susunan huruf yang sama):
1. BUKU 6. BUUK 11. UBUK 16. KBUU 21. UUBK 2. BUUK 7. UKBU 12.
UBKU 17. KUUB 22. UUKB 3. BKUU 8. UKUB 13. KUBU 18. KUBU 23.
UKBU 4. BKUU 9. UUBK 14. KUUB 19. UBUK 24. UKUB 5. BUKU 10.
UUKB 15. KBUU 20. UBKU

Susunan huruf yang sama kita hilangkan, sehingga menjadi :

1. BUKU 4. UKBU 7. UUKB 10. KUBU

2. BUUK 5. UKUB 8. UBUK 11. KUUB
3. BKUU 6. UUBK 9. UBKU 12. KBUU

Jadi banyaknya permutasi

4*3*2*1
pada”BUKU” ⇒ 2*1
= 12

PELUANG BERSYARAT
P(A│B) = Peluang terjadinya peristiwa A dengan syarat peristiwa B telah terjadi.

𝑃(𝐴∩𝐵)
P(A|B) = 𝑃(𝐵)
→sehingga: P(A∩B) = P(B) P(A|B)
atau
𝑃(𝐴∩𝐵)
P(A|B) = 𝑃(𝐴)
→sehingga: P(A∩B) = P(A) P(B|A)

Untuk peristiwa saling bebas : P(A∩B) = P(A) P(B) = P(B) P(A)

Contoh :
Sebuah Polres di Jakarta memiliki kekuatan 1000 personil polisi, terdiri atas polisi wanita
dan polisi pria. Seminggu yang lalu sebagian anggota polres tersebut mendapat kenaikan
pangkat. Perhatikan tabel berikut ini :
Naik pangkat Tidak naik pangkat Tota
(NP) (TNP) l

Wanit 150 100 250

a

Pria 200 550 750

Total 350 650 100

0

Hitunglah :
a. Peluang terjadinya anggota polisi adalah wanita atau yang naik pangkat. [Link] anggota
polisi yang naik pangkat dengan syarat dia adalah wanita.

Jawab :
P(Wanita) = 250/1000 = 0.25
P(NP) = 350/1000 = 0.35
P(NP ∩ Wanita) = 150/1000 = 0.15

a.P(Wanita U NP) = P(Wanita) + P(NP) – P(Wanita ∩ NP) = 0.25 + 0.35 – 0.15 = 0.45

𝑃(𝑁𝑃∩𝑊𝑎𝑛𝑖𝑡𝑎) 0.15
b.P(NP│Wanita) = 𝑃(𝑊𝑎𝑛𝑖𝑡𝑎)
= 0.25
= 0. 6

CATATAN :
1. KEJADIAN SALING BEBAS :
a.P(A∩B) = P(A)P(B)
b.P(A│B) = P(A) atau : P(B│A) = P(B)

2. KEJADIAN TIDAK SALING BEBAS :

a.P(A∩B) = P(B) P(A│B) atau : P(A∩B) = P(A) P(B│A) B.P(A│B) ≠ P(A)
TEOREMA KOEFISIEN BINOMIAL
Misalkan x dan y adalah variabel, dan n adalah bilangan bulat positip, maka :
KOEFISIEN BINOMIAL:

Contoh 2:
12 13 25
Berapakah nilai koefisien dari 𝑥 𝑦 pada ekspansi (2𝑥 − 3𝑦) ?
Jawab:
25
25 25 25 25 𝑗
(2𝑥 − 3𝑦) = (2𝑥 + (− 3𝑦)) = ∑ (𝑗 )(2𝑥) − 𝑗(− 3𝑦)
𝑗=0
12 13 25
Maka dari itu, koefisien 𝑥 𝑦 pada ekspansi (2𝑥 + (− 3𝑦)) diperoleh saat j = 13, yaitu:
25 12 13 25! 12 13
(13)2 (− 3) = − 13! 12!
2 3

Contoh 3:
12 13 25
Berapakah nilai koefisien dari 𝑥 𝑦 pada ekspansi (𝑥 + 𝑦) ?
Jawab:
25 25!
(13) = 13! 12!
= 5200300
VII. RELASI

Relasi
⇒ hubungan antara anggota-anggota himpunan.

Relasi vs Fungsi
Relasi Fungsi

Satu atau lebih anggota himpunan Setiap anggota himpunan

dipasangkan dengan satu atau lebih dipasangkan tepat dengan satu
anggota himpunan lainnya anggota himpunan lainnya

Relasi Biner
⇒ hubungan antara anggota dua himpunan

● Relasi biner R antara himpunan A dan B adalah himpunan bagian dari A x B.

Notasi: R ⊆ (A x B).
● a R b merupakan notasi untuk (a,b) ∈ R, berarti a dihubungkan ke b oleh R.
● Himpunan A disebut daerah domain (asal) dari R, dan himpunan B disebut
daerah range (hasil) dari R.

Contoh:

A = {Amir, Budi, Cecep}, B = {IF221, IF251, IF342, IF323} A x B = {(Amir, IF221), (Amir,
IF251), (Amir, IF342), (Amir, IF323), (Budi, IF221), (Budi, IF251), (Budi, IF342), (Budi,
IF323), (Cecep, IF221), (Cecep, IF251), (Cecep, IF342), (Cecep, IF323) } Misalkan R
adalah relasi yang menyatakan mata kuliah yang diambil oleh mahasiswa pada
Semester Ganjil, yaitu R = {(Amir, IF251), (Amir, IF323), (Budi, IF221), (Budi, IF251),
(Cecep, IF323) }

● Dapat dilihat bahwa R ⊆ (A x B),

● A adalah daerah asal R, dan B adalah daerah hasil R.
● (Amir, IF251)∈ R atau Amir R IF251

Relasi Pada Suatu Himpunan

Relasi pada himpunan A merupakan relasi dari A ke A ⇒ R : A → A atau aRa
Sifat-sifat Relasi

1. Refleksif

Relasi R pada himpunan A disebut refleksif bila (a,a) ∈ R untuk setiap elemen a ∈ A.

Contoh:

Perhatikankan relasi berikut pada {2, 3, 4, 5}: R1 = {(2, 2), (2, 3), (3, 2), (3, 3), (4, 5), (5,
2), (5, 5)}, R2 = {(2, 2), (2, 3), (3, 2)}, R3 = {(2, 2), (2, 3), (2, 5), (3, 2), (3, 3), (4, 4), (5, 2),
(5, 5) }, R4 = {(3, 2), (4, 2), (4, 3), (5, 2), (5, 3), (5, 4)}, R5 = {(2, 2), (2, 3), (2, 4), (2, 5),
(3, 3), (3, 4), (3, 5), (4, 4) , (4, 5), (5, 5)}, R6 = {(4, 5)}. R7 = {(2, 2), (2, 3), (2, 5), (3, 2),
(3, 3), (4, 4), (5, 5)} Manakah dari relasi tersebut yang refleksif? Jawab : R1 tidak
refleksif, karena tidak mengandung (4, 4). R2 tidak refleksif, karena tidak mengandung
(3, 3), (4, 4) dan (5, 5). R3 refleksif, karena mengandung (2, 2), (3, 3), (4, 4) dan (5, 5).
R4 tidak refleksif, karena tidak mengandung (2, 2), (3, 3), (4, 4) dan (5, 5). R5 refleksif,
karena mengandung (2, 2), (3, 3), (4, 4) dan (5, 5). R6 tidak refleksif, karena tidak
mengandung (2, 2), (3, 3), (4, 4) dan (5, 5).

R7 tidak refleksif, karena tidak mengandung (5, 2).

2. Simetris

Suatu relasi R pada himpunan A disebut simetris bila (a,b) ∈ R, maka (b,a) ∈ R, untuk
semua a, b ∈ A. Suatu relasi R pada himpunan A sedemikian rupa sehingga untuk
semua a, b ∈ A, jika (a, b) ∈ R dan (b, a) ∈ R, maka a = b disebut antisimetris.

Contoh

Relasi pada himpunan {1, 2, 3, 4}: R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)}, R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4) },
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}, R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2,
3), (2, 4), (3, 3) , (3, 4), (4, 4)}, R6 = {(3, 4)}. Manakah dari relasi tersebut yang simetris
dan mana yang antisimetris ?

Jawab : R1 : antisimetris, karena tidak mengandung (4, 3) dan (1, 4). R2 dan R3
simetris. R4, R5, dan R6 semuanya antisimetris.

3. Transitif

Misalkan R relasi dalam himpunan A. R disebut relasi transitif jika berlaku ; (a,b)R dan
(b,c)R maka (a,c)R. Dengan kata lain, andai a berelasi dengan b dan b berelasi dengan
c, maka a berelasi dengan c.

Contoh :

Misalkan A = {a, b, c} dan R = {(a,b), (a,c), (b,a), (c,b)}, maka R bukan relasi transitif,
sebab tidak terdapat (b,c)R dari (b,a)R dan (a,c)R.

Dilengkapi agar R menjadi relasi transitif R = {(a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a),
(c,b), (c,c)}

Relasi Ekivalen
Relasi pada himpunan A disebut relasi ekivalen jika bersifat refleksif, simetris, dan
transitif.

Contoh 1 : Misalkan A = {1, 2, 3} R1 = {(1, 1), (1, 2), (2, 2), (2, 1), (3, 3)} Relasi R1
bersifat refleksif, simetris dan transitif, sehingga R1 adalah relasi ekivalen.

Contoh 2 : Misalkan A = {2, 4, 5} R1 = {(x, y) │x kelipatan y , x,y ∈ A} = {(2, 2), (4, 4), (5,
5), (4, 2)}. Relasi R1 tidak bersifat simetris, sehingga bukan relasi ekivalen.
Kelas Ekivalen
Misalkan R adalah relasi ekivalen pada himpunan A. Himpunan semua elemen yang
terkait dengan elemen a dari A disebut kelas ekivalen dari a. Kelas ekivalen a terhadap
R dilambangkan dengan [a]R.

[a]R ={x ∈ A │ aRx} jika hanya satu relasi, maka R tidak ditulis, menjadi [a].

Contoh : A adalah himpunan semua mahasiswa yang merupakan lulusan dari berbagai
SMU. Misal relasi R pada A adalah semua pasangan (x,y) dimana x dan y adalah
lulusan dari SMU yang sama. Untuk seorang mahasiswa x, dapat dibentuk himpunan
semua mahasiswa yang ekivalen dengan x. Himpunan tersebut terdiri dari semua
mahasiswa yang lulus dari SMU yang sama dengan x. Himpunan ini disebut kelas
ekivalen dari relasi R.

Kelas Ekivalen dan Partisi

Misal R relasi ekivalen pada himpunan S. Maka kelas ekivalen dari R membentuk suatu
partisi dari S.

Contoh 1: Misal Andy, Eny dan Chika tinggal di Jakarta, Ilona dan Marco di Roma, serta
Michiko di Tokyo. Misal R relasi ekivalen : {(a,b) │a dan b tinggal di kota yang sama}
Pada himpunan P = {Andy, Eny, Chika, Ilona, Marco, Michiko}

Maka : R = {(Andy, Andy), (Andy, Eny), (Andy, Chika), (Eny, Eny), (Eny, Andy), (Eny,
Chika), (Chika, Chika), (Chika, Andy), (Chika, Eny), (Ilona, Ilona), (Ilona, Marco), (Marco,
Marco), (Marco, Ilona), (Michiko, Michiko)}. Kelas ekuivalen dari R adalah : {{Andy, Eny,
Chika}, {Ilona, Marco}, {Michiko}} yang juga merupakan partisi dari P. Kelas ekivalen dari
setiap relasi ekivalen R pada himpunan S membentuk partisi pada S, karena setiap
anggota S dihubungkan dengan tepat satu kelas ekivalen.

Contoh 2 : Apa kelas kesetaraan dari 0, 1, 2, dan 3 untuk kongruensi modulo 4?

Jawab : Kelas ekivalen 0 berisi semua bilangan bulat a sehingga a ≡ 0 (mod 4) . Oleh
karena itu, kelas ekivalen 0 untuk relasi ini adalah

*0+ = ,..., −8, −4, 0, 4, 8,...-.

Kelas ekivalen 1 berisi semua bilangan bulat sehingga a ≡ 1 (mod 4). Oleh karena itu,
kelas ekivalen 1 untuk relasi ini adalah

*1+ = ,..., −7, −3, 1, 5, 9,...-.

Kelas ekivalen 2 berisi semua bilangan bulat a sehingga a ≡ 2 (mod 4). Oleh karena itu,
kelas ekivalen 2 untuk relasi ini adalah
*2+ = ,..., −6, −2, 2, 6, 10,...-.

Kelas ekivalen 3 berisi semua bilangan bulat a sehingga a ≡ 3 (mod 4). Oleh karena itu,
kelas ekivalen 3 untuk relasi ini adalah

*3+ = ,..., −5, −1, 3, 7, 11,...-.

Himpunan Terurut Parsial (Poset: Partially Ordered Set)

Definisi 1

Suatu relasi R pada himpunan S disebut urutan parsial atau tatanan parsial jika bersifat
refleksif, antisimetris, dan transitif. Himpunan S bersama dengan urutan parsial R
disebut himpunan terurut parsial, atau poset, dan dilambangkan dengan (S, R). Anggota
S disebut elemen poset.

Contoh 1 : Tunjukkan bahwa relasi lebih besar dari atau sama dengan (≥) adalah urutan
parsial pada himpunan bilangan bulat.

Jawab : Karena a ≥ a untuk setiap bilangan bulat a, ≥ bersifat refleksif. Jika a ≥ b dan b ≥
a, maka a = b. Oleh karena itu, ≥ bersifat antisimetris. Relasi ≥ bersifat transitif karena a
≥ b dan b ≥ c mengandung arti bahwa a ≥ c. Oleh karena itu, ≥ adalah urutan parsial
pada himpunan bilangan bulat dan (Z, ≥) adalah sebuah poset.

Contoh 2:

Misalkan R adalah relasi pada himpunan orang sehingga xRy jika x dan y adalah orang
dan x lebih tua dari y. Tunjukkan bahwa R bukanlah urutan parsial.

Jawab : R antisimetris karena jika orang x lebih tua dari orang y, maka y tidak lebih tua
dari x. Artinya, jika xRy, maka yRx. Relasi R bersifat transitif karena jika orang x lebih tua
dari orang y dan y lebih tua dari orang z, maka x lebih tua dari z. Artinya, jika xRy dan
yRz, maka xRz. R tidak refleksif, karena tidak ada orang yang lebih tua dari dirinya
sendiri. Artinya, xRx untuk semua orang x. Oleh karena itu, R bukanlah urutan parsial.

Definisi 2 Unsur a dan b dari sebuah poset (S, ≼) disebut sebanding jika a ≼ b atau b ≼
a. Ketika a dan b adalah elemen dari S sehingga baik a ≼ b maupun b ≼ a, a dan b tidak
disebut tak ada bandingannya.

Contoh Dalam poset ("Z" ^ +, ∣), apakah bilangan bulat 3 dan 9 sebanding? 5 dan 7
sebanding?

Jawab : Bilangan bulat 3 dan 9 sebanding, karena 3 ∣ 9. Bilangan bulat 5 dan 7 tidak
dapat dibandingkan, karena 5 ∤7 dan 7 ∤ 5.

Definisi 3
Jika (S, ≼) adalah sebuah poset dan setiap dua elemen S sebanding, S disebut
himpunan terurut total atau teratur linier, dan ≼ disebut orde total atau orde linier. Satu
set yang benar-benar tertata juga disebut rantai.

Contoh:

1. Poset (Z, ≤) tersusun total, karena a ≤ b atau b ≤ a setiap kali a dan b adalah
bilangan bulat.
2. Poset ("Z" ^ +, ∣) tidak tersusun seluruhnya karena mengandung elemen yang
tidak ada bandingannya, seperti 5 dan 7.

Comparable dan Non-Comparable

Misalkan diketahui suatu relasi terurut parsial pada himpunan A. Elemen a dan b dari A
disebut comparable, jika dan hanya jika a b atau b a. Diluar ketentuan itu, a dan b
+
disebut noncomparable. Pada poset (𝑍 , ), 3 dan 6 adalah comparable, 6 dan 3 adalah
comparable, 3 dan 5 noncomparable, 8 dan 12 noncomparable.

Total Order
⇒ urutan parsial dimana tiap pasangan elemennya comparable.

+
Contoh : (𝑍 , ) adalah total order, karena setiap pasangan (a, b) dalam ZxZ, maka a b
atau b a.

Diagram Hasse
⇒ Diagram khusus untuk menggambarkan poset.

Prosedur Membuat Diagram Hasse:

1. Mulai dengan graf berarah relasi dimana semua panah menuju ke tempat yang
lebih atas
2. Hilangkan loop pada setiap titik
3. Hilangkan panah yang keberadaannya bisa diimplikasikan dengan sifat transitif
4. Hilangkan petunjuk panah → graf tak berarah

Contoh 1: Poset (1, 2, 3, 4, ≤), diagram Hasse dari poset tersebut:

Contoh 2:

Gambarkan diagram Hasse yang mewakili urutan parsial {(a, b) ∣ a membagi b} pada {1,
2, 3, 4, 6, 8, 12}.

Jawab : R = (1, 4), (1, 6), (1, 8), (1, 12), (2, 8), (2, 12), dan (3, 12). Gambar (c) adalah
diagram Hasse yang dihasilkan.
Elemen Maksimal dan Minimal
Sebuah elemen poset disebut maksimal jika tidak kurang dari elemen poset manapun.
Artinya, a maksimal dalam poset (S, ≼) jika tidak ada b ∈ S sehingga a ≺ b.

Sebuah elemen dari sebuah poset disebut minimal jika tidak lebih besar dari elemen
manapun dari poset tersebut. Artinya, a minimal jika tidak ada unsur b ∈ S sehingga b ≺
a.

Contoh: Tentukan elemen maksimal dan elemen minimal dari poset : ({2, 4, 5, 10, 12,
20, 25}, ∣) Jawab : Elemen maksimalnya adalah 12, 20, dan 25. Elemen minimalnya
adalah 2 dan 5.

Elemen Terbesar dan Elemen Terkecil

Contoh :

Tentukan elemen terbesar dan elemen terkecil dari diagram berikut ini.

Diagram (a) : Elemen terbesar (Maksimum): tidak ada.

Maksimal : b, c, d.

Elemen terkecil (Minimum) : a.

Minimal : tidak ada.

Diagram (b) : Elemen terbesar (Maksimum): tidak ada.

Maksimal : d, e.

Elemen terkecil (Minimum) : tidak ada.

Minimal : a, b.

Diagram (c) : Elemen terbesar (Maksimum) : d.

Maksimal : tidak ada.

Elemen terkecil (Minimum) : tidak ada. Minimal : a, b.

Diagram (d) : Elemen terbesar (Maksimum): d.

Maksimal : tidak ada.

Elemen terkecil (Minimum) : a. Minimal : tidak ada.

Batas Atas dan Batas Bawah

Sebuah elemen yang lebih besar dari atau sama dengan semua elemen dalam
himpunan bagian A dari poset poset (S, ≼).

Jika u adalah unsur S sedemikian rupa sehingga a ≼ u untuk semua unsur a ∈ A, maka
u disebut batas atas A.

Sebuah elemen kurang dari atau sama dengan semua elemen di A Jika l adalah elemen
dari S sehingga l ≼ a untuk semua elemen a ∈ A, maka l disebut batas bawah A.

Unsur x disebut batas atas terkecil dari himpunan bagian A (lub (A)) jika a ≼ x jika a ∈
A, dan x ≼ z jika z adalah batas atas A.

Unsur y disebut batas bawah terbesar A (glb (A)) jika y adalah batas bawah A dan z ≼ y
setiap kali z adalah batas bawah A. Batas atas terkecil dan batas bawah terbesar dari A
bersifat unik jika mereka ada.

Contoh:
Pada poset dengan diagram Hasse di bawah ini: a. Tentukan batas bawah dan atas dari
subset {a, b, c}, {j, h}, dan {a, c, d, f} [Link] batas bawah terbesar dan batas atas
terkecil dari {b, d, g} (jika ada)

Jawab :

Maksimum = tidak ada;

Maksimal = h dan j ;

Minimum = a.

a. Lower Bound :

LB {a, b, c} = a

LB {j, h} = a, b, c, d, e, dan f

LB {a, c, d, f } = a

Upper Bound :

UB {a, b, c} = e, f, j, dan h,

UB {j, h} = -

UB {a, c, d, f } = f , h, dan j

b. UB {b, d, g} = g dan h. Least Upper Bound : LUB {b, d, g} =g

LB {b, d, g} = a dan b.

Greatest Lower Bound : GLB {b, d, g} = b

Lattices
Himpunan berurutan sebagian di mana setiap pasangan elemen memiliki batas atas
terkecil dan batas bawah terbesar disebut kisi.

Contoh :

Diagram Hasse di (a) dan (c) keduanya adalah kisi. Diagram Hasse yang ditunjukkan
pada (b) bukanlah sebuah kisi, karena elemen b dan c tidak memiliki batas atas
terkecil.

Menyatakan Relasi Menggunakan Matriks

Contoh 1 : Misalkan A = {1, 2, 3} dan B = {1, 2}. Misalkan R adalah relasi dari A ke B
yang mengandung (a, b) jika a ∈ A, b ∈ B, dan a> b.

Berapakah matriks yang mewakili R jika a1 = 1, a2 = 2, dan a3 = 3, dan b1 = 1 dan b2 =

2? Jawab : Karena R = {(2, 1), (3, 1), (3, 2)}, matriks untuk R adalah

Angka 1 di MR menunjukkan bahwa pasangan (2, 1), (3, 1), dan (3, 2) adalah milik R.
Angka 0 menunjukkan bahwa tidak ada pasangan lain yang dimiliki R.

Contoh 2 : Misalkan A = {a1, a2, a3} dan B = {b1, b2, b3, b4, b5}. Pasangan terurut
mana yang berada dalam relasi R yang diwakili oleh matriks
?

Jawab : Karena R terdiri dari pasangan terurut (ai, bj) dengan mij = 1, maka : R = {(a1,
b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5)}.

Matriks Relasi Pada Suatu Himpunan

Matriks nol-satu untuk:
 Relasi antisimetris

Contoh:

Misalkan relasi R pada suatu himpunan diwakili oleh matriks

Apakah R refleksif, simetris, atau antisimetris ?

Jawab : R refleksif. Karena semua elemen diagonal matriks ini sama dengan 1. R
simetris, karena MR simetris. R tidak antisimetris.

VIII. TREE (Pohon)

Teorema 1:
Tree adalah graf terhubung tidak berarah yang tidak mengandung sirkuit sederhana.
(Sirkuit sederhana : lintasan tertutup dengan setiap sisi yang dilalui berbeda). Tree tidak
akan mengulangi tempat yang sama (acyclic).
Pohon berakar (Rooted Tree)
Pohon berakar adalah pohon yang satu simpulnya telah ditetapkan sebagai
akar dan sisi-sisinya diberi arah menjauhi akar, sehingga menjadi graf
berarah, namun selanjutnya boleh tidak diberi arah.

● Akar mempunyai derajat masuk 0, dan simpul lainnya mempunyai derajat masuk
1.
● Daun adalah simpul berderajat 0 dan disebut simpul terminal (tidak mempunyai
anak). Simpul yang memiliki anak disebut simpul internal.
● Simpul v dikatakan anak dari u jika terdapat sisi dari simpul u ke v. Oleh karena
itu, u adalah orang tua dari v.
● Jika terdapat lintasan dari v hingga u, maka u adalah keturunan dari v dan v
adalah leluhur dari u.
● Derajat pada simpul adalah jumlah anak pada simpul tersebut.
Pohon Berakar Terurut
Pohon berakar terurut adalah pohon berakar yang urutan anak-anaknya penting. Dalam
pohon biner yang terurut, jika simpul internal memiliki dua anak, anak pertama disebut
anak kiri dan anak kedua disebut anak kanan. Pohon yang berakar pada anak kiri dari
sebuah simpul disebut subpohon kiri dari simpul ini, dan pohon yang berakar pada anak
kanan dari simpul disebut subpohon kanan dari simpul tersebut.

Anak kiri dari d adalah f dan anak kanan dari d adalah g.

Subpohon kiri dari c adalah

Subpohon kanan dari c adalah

Pohon M-ary
Pohon m-ary adalah pohon berakar yang setiap simpul cabangnya mempunyai paling
banyak m buah anak. Pohon itu disebut pohon m-ary penuh jika setiap simpul internal
memiliki tepat m anak. Pohon dengan m = 2 disebut pohon biner. Pohon dengan m = 3
disebut pohon 3-ary, dan seterusnya.
Teorema 2:
Tree dengan n simpul memiliki n-1 sisi.

Teorema 3:
Sebuah tree full m-ary dengan i simpul internal berisi n = mi + 1 simpul.

Teorema 4:
Sebuah tree full m-ary dengan:
● n simpul memiliki i = (n - 1) ∕ m simpul internal dan l = [(m - 1) n + 1] ∕ m daun,
● i simpul internal memiliki n = mi + 1 simpul dan l = (m - 1) i + 1 daun,
● l daun memiliki n = (ml - 1) ∕ (m - 1) simpul dan i = (l - 1) ∕ (m - 1) simpul

Balanced M-ary Trees

Level suatu simpul v pada pohon yang berakar adalah panjang jalur dari akar ke titik ini.
Level akar didefinisikan sebagai nol. Ketinggian pohon yang berakar adalah maksimum
dari level simpul. Dengan kata lain, tinggi pohon yang berakar adalah panjang jalur
terpanjang dari akar ke simpul manapun.

Pohon m-ary yang berakar dengan tinggi h disebut balanced jika semua daun
berada pada level h atau h - 1.
Algoritma Preorder, Inorder, dan Postorder Traversal

1. Preorder Traversal
Diawali dengan mengunjungi akar, lalu mengunjungi subpohon kiri hingga kanan.

2. Inorder Traversal
 Diawali dengan mengunjungi subpohon paling kiri, ke akar, hingga subpohon
kanan.

3. Postorder Traversal
Diawali dengan mengunjungi subpohon paling kiri, ke tengah, ke subpohon
kanan, diakhiri dengan mengunjungi akar.
Notasi Prefix, Infix, dan Postfix

● Notasi prefix
Didapatkan dengan melintasi pohon yang berakar secara preorder.

● Notasi infix
Didapatkan dengan melintasi pohon yang berakar secara inorder.
● Notasi postfix
Didapatkan dengan melintasi pohon yang berakar secara postorder.
Spanning Tree (Pohon Rentang)
Pohon rentang dari suatu graf sederhana G adalah subgraf dari G yang
merupakan pohon yang berisi setiap simpul G.
Graf sederhana disebut terhubung jika dan hanya jika memiliki pohon rentang.
Depth-First Search
Penelusuran kedalaman pertama juga disebut penelusuran mundur, karena
algoritma mengembalikan ke simpul yang sebelumnya dikunjungi untuk
menambahkan jalur.

Cara: pilih simpul sembarang pada suatu graf, lalu bentuk jalur hingga
mengunjungi semua simpul. Jika jalur melewati semua simpul pada grafik, pohon
yang terdiri dari jalur ini adalah pohon rentang.

Contoh:

Dimulai dari simpul f, maka:

Breadth First Search

Pilih simpul sembarang, lalu bentuk semua sisi yang bersisian dengan simpul
tersebut. Lakukan hal ini untuk simpul selanjutnya.

Contoh:
Maka:

Pohon Rentang Minimum

Jika terdapat graf seperti berikut:

Bagaimana meminimalisirnya?

1. Algoritma Prim
Misal mulai di New York, maka pilihlah jalur/sisi yang memiliki biaya
terkecil untuk mengunjungi seluruh simpul:
 Jawab:

2. Algoritma Kruskal
Jawab: