diktat pendukung matematika diskrit k0144
TRANSCRIPT
DIKTAT PENDUKUNGMATEMATIKA DISKRIT K0144
Drs. Sangadji, M.Sc., Ph.D.D1808
F S T
UNIVERSITAS BINA NUSANTARAJAKARTA
1
PERTEMUAN 1: LOGIKA PROPOSISI
Pendahuluan
Dalam logika matematika, yang dibicarakan hanyalah proposisi atau pernyataan
atau kalimat deklaratif yang artinya kalimat yang bernilai benar atau salah dan tidak
sekaligus kedua-duanya. Yang tidak termasuk pernyataan misalnya kalimat harapan,
kalimat perintah, kalimat seru dan sebagainya. Beberapa pernyataan merupakan susunan
atau gabungan dari pernyataan-pernyataan bagiannya yang dihubungkan oleh beberapa
macam konektif (kata hubung logika) misalnya ”dan”, ”atau” dll. dan disebut pernyataan
gabungan.
Contoh
1. Contoh pernyataan:
a. ”New York kota besar”
b. ”Paris ibukota negara Inggris”
c. ” ”
2. Contoh bukan pernyataan:
a. ”Semoga kamu lekas sembuh”
b. ”Cepat lari!”
c. ”Ke mana dia pergi?”
d. ”Alangkah cantiknya gadis itu.”
e. ”Penduduk kota Jakarta kaya” (tidak dilengkapi kuantor/pembatas penduduk)
f. ” ” (untuk benar, untuk salah, disebut kalimat terbuka)
Tabel kebenaran
Suatu definisi yang berbentuk tabel yang menunjukkan hubungan antara nilai
kebenaran dari setiap pernyataan bagian yang menyusun pernyataan gabungan dengan
nilai kebenaran pernyataan gabungan tersebut.
Negasi (ingkaran), konjungsi dan disjungsi
2
B B S S B B S
B S S B S B B
S B B S S B B
S S B B S S S
, : pernyataan bagian .
B: benar, S: salah
atau ~ p : ingkaran dari p, atau ~ q: ingkaran dari q.
: konjungsi dari p dan q dibaca ”p dan q” (pernyataan gabungan).
: disjungsi dari p dan q dibaca ”p atau q” (pernyataan gabungan).
: bernilai benar hanya untuk keduanya benar.
: bernilai salah hanya untuk keduanya salah.
: exclusive or dari p dan q dibaca ”p exclusive or q”
Implikasi
®
B B B
B S S
S B B
S S B
: hipotesis, : konklusi.
® : implikasi.
® : bila p maka q.
® : bernilai salah hanya untuk p benar dan q salah.
® : p disebut syarat cukup bagi q.
q disebut syarat perlu bagi p.
3
Konvers, invers, dan kontrapositif dari implikasi
® : implikasi mula – mula.
® : konvers dari ® , ® : invers dari ® .
® : kontrapositif dari ® .
® ® ® ®
B B B B B B S S
B S S B B S S B
S B B S S B B S
S S B B B B B B
Biimplikasi
« : p bila dan hanya bila q.
® ®
B B B B B B
B S S B S S
S B B S S S
S S B B B B
: bernilai benar untuk keduanya bernilai kebenaran yang sama,
bernilai salah untuk keduanya bernilai kebenaran yang berlainan.
PERTEMUAN 2: ALJABAR PROPOSISI
Proposisi mempunyai sifat fundamental yang disebut hukum atau formula.
Beberapa hukum yang penting kita kelompokkan di bawah ini.
4
sama
sama
sama
1) Idempoten
p Ú p = p, p Ù p = p
2) Asosiatif
(p Ú q) Ú r = p Ú (q Ú r), (p Ù q) Ù r = p Ù (q Ù r)
3) Komutatif
p Ú q = q Ú p, p Ù q = q Ù p
4) Distributif
p Ú (q Ù r) = ( p Ú q) Ù ( p Ú r)
p Ù (q Ú r) = (p Ù q) Ú (p Ù r)
5) DeMorgan
6) Identitas
p Ú F = p, p Ù F = F
p Ú T = T, p Ù T = p
T : Tautologi, F : Kontradiksi
7) Komplemen
8) Absorpsi
p Ú (p Ù q) = p, p Ù (p Ú q) = p
5
Contoh
1. Bukan pernyataan:
a. “Kemana kamu mudik ?”,
b. “Semoga dia lekas sadar.”,
c. “Cepat keluar!”,
d. “Alangkah kayanya saudagar itu.”,
e. “Penduduk kota Medan kaya.”
f. “x + 2 = 10”.
2. Termasuk pernyataan:
a. “Jakarta kota kecil.”,
b. “ dan New York kota besar.”,
c. “1 + 0 = 2.”,
d. “New Mexico negara bagian dari Amerika Serikat.”
3. p : Ali pandai, q : Badu malas.
a. p Ù q : Ali pandai dan Badu malas.
b. p Ú q : Ali pandai atau Badu malas.
c. : Ali tidak pandai atau Badu tidak malas.
d. : Ali tidak pandai dan Badu tidak malas.
4. Buktikan bahwa ® = Ú dengan membuat tabel kebenaran untuk dan Ú
.
6
Solusi
®
B S B B B
B S S S S
S B B B B
S B S B B
5. Buktikan hukum absorpsi, yaitu
p Ú (p Ù q) = p, p Ù (p Ú q) = p dengan membuat tabel kebenaran.
Solusi
p Ú (p Ù q) p Ù (p Ú q)
B B B B B B
B S S B B B
S B S B S S
S S S S S S
6. Tulislah ingkaran dari pernyataan :
a) Ali pandai dan malas.
b) Badu kaya atau malas.
c) Bila Amir belajar maka dia lulus.
d) Mawar berwarna merah bila dan hanya bila violet berwarna biru.
Solusi
a) Ali tidak pandai atau tidak malas.
b) Badu tidak kaya dan tidak malas.
c) Amir belajar dan tidak lulus.
d) Mawar berwarna merah dan violet tidak berwarna biru atau violet
berwarna biru dan mawar tidak berwarna merah.
7
2. Tulislah konvers, invers, dan kontrapositif dari implikasi : Bila Anna pandai dan
rajin maka dia lulus.
Solusi
Konvers : Bila Anna lulus maka dia pandai dan rajin.
Invers : Bila Anna tidak pandai atau tidak rajin maka dia tidak lulus.
Kontrapositif : Bila Anna tidak lulus maka dia tidak pandai atau tidak rajin.
3. Sederhanakanlah :
a) ( p Ú q) Ù ,
b)
Solusi
a)
b)
Soal
1. Tentukan tabel kebenaran dari :
a) ® ( Ú ),
b) ( Ù ) ® ( Ú ),
c) ( Ù ) Ù ( Ú r ),
d) ( ® ) Ù ( ® r).
2. Tentukan nilai kebenaran dari :
a) Bila 5 < 3 maka -3 < -5.
b) ( 2 + 7 = 9 ) « ( 2 + 1 = 5 ® 5 + 5 = 8 ).
3. Tulislah konvers, invers, dan kontrapositif dari implikasi : Bila pandai dan sehat
maka kaya atau tidak sakit-sakitan.
4. Sederhanakan:
8
a)
b)
c)
PERTEMUAN 3: PERNYATAAN
Proposisi (pernyataan, kalimat deklaratif)
Proposisi dapat berarti kalimat yang bernilai benar atau salah dan tidak sekaligus
kedua-duanya.Bergantung dengan konteksnya, proposisi dapat berarti suatu pernyataan
yang telah dibuktikan kebenarannya, yang tingkatnya lebih rendah dari teorema.
9
Pernyataan gabungan disusun oleh pernyataan-pernyataan bagiannya yang
dihubungkan dengan konektif atau kata hubung logika. Dalam logika sehari-hari atau
logika di masyarakat, biasanya ada hubungan antara pernyataan-bagian yang menyusun
pernyataan gabungan. Tetapi dalam logika matematika antara pernyataan-pernyataan
bagian tersebut boleh ada hubungan atau tidak.Pada tabel kebenaran sudah didefinisikan
negasi, konjungsi, disjungsi, implikasi dll. sehingga pada umumnya suatu pernyataan
yang benar dalam logika sehari-hari juga benar dalam logika matematika, dan suatu
pernyataan yang salah dalam logika sehari-hari juga salah dalam logika matematika.
Dalam hal ini boleh dikatakan logika matematika lebih luas dari logika sehari-hari.
Tautologi dan kontradiksi
Tautologi : pernyataan yang selalu bernilai benar.
Kontradiksi : pernyataan yang selalu bernilai salah.
Ekivalen logis (logical equivalence)
Dua pernyataan disebut ekivalen logis atau ekivalen bila tabel-tabel kebenaran
dari keduanya sama.
Definisi
Suatu pernyataan yang disetujui bersama oleh semua pihak yang terlibat.
Contoh
1. Bilangan bulat n disebut pembagi dari bilangan bulat m bila m = kn untuk suatu
bilangan bulat k.
2. Bilangan bulat positif p > 1 disebut prima bila pembagi positif dari p hanyalah
1dan p.
3. Suatu segitiga disebut samakaki bila dua sisinya panjangnya sama.
4. Pasangan berurutan dari bilangan nyata (real) adalah sama dengan
pasangan berurutan dari bilangan nyata bila dan .
5. Bilangan bulat n disebut genap bila 2 adalah pembagi dari n.
6. Bilangan bulat n disebut ganjil bila n = 2k +1 untuk suatu bilangan bulat k.
7. Bilangan nyata r disebut rasional (terukur) bila dengan m dan n bilangan
bulat dan .
10
8. Suatu segitiga disebut siku- siku bila dua sisinya saling tegaklurus.
Terminologi (istilah) matematika
1. Proposisi
Suatu pernyataan yang telah dibuktikan kebenarannya.
2. Teorema
Suatu pernyataan yang sifatnya lebih umum dan lebih penting dari
proposisi yang telah dibuktikan kebenarannya.
3. Corollary
Suatu pernyataan yang buktinya dengan mudah dapat diturunkan dari
suatu teorema atau singkatnya suatu akibat.
4. Lemma
Suatu pernyataan yang telah dibuktikan kebenarannya dan digunakan
untuk membuktikan teorema.
5. Aksioma
Suatu pernyataan yang dapat diterima kebenarannya tanpa bukti.
Contoh
1. Proposisi
a) Jumlah sudut- sudut dalam segitiga sembarang adalah
b) Akar-akar persamaan kuadrat akan sama dan bernilai real
bila
2. Teorema
a) Teorema Binomial : di mana bilangan
bulat positif.
b) Teorema Fundamental Aritmatika :
11
Setiap bilangan bulat yang lebih besar dari 1 adalah prima atau
sebagai hasil kali dari bilangan-bilangan prima. Tanpa memerhatikan
urutan, penyajian hasil kali tersebut adalah tunggal (unique).
Misalnya
3. Corollary
a) .
b)
4. Lemma
a) Untuk membuktikan Teorema Binomial diperlukan lemma :
b) Untuk membuktikan Teorema Fundamental Aritmatika diperlukan lemma:
Bila p adalah bilangan prima dan p adalah pembagi dari hasil kali
maka p adalah pembagi dari sekurang-kurangnya satu dari
bilangan- bilangan
5. Aksioma
a) Garis lurus ditentukan oleh 2 titik.
b) Bidang datar ditentukan oleh 3 titik.
Soal
1. Berikan definisi dari segitiga samakaki yang ekivalen dengan definisi di
muka.
2. Berikan dua definisi yang ekivalen dari segitiga samasisi.
3. Berikan definisi-definisi dari fungsi genap dan fungsi ganjil.
4. Berikan contoh-contoh yang lain dari proposisi, teorema, corollary, lemma,
dan aksioma.
12
PERTEMUAN 4: ARGUMENTASI DAN KUANTOR
ARGUMENTASI
13
Argumentasi adalah penarikan kesimpulan dari sekelompok pernyataan
yang disebut premis yang menghasilkan pernyataan lain S yang disebut
konklusi. Argumentasi sedemikian akan ditulis dengan notasi/simbol
Perlu dicatat bahwa argumentasi juga merupakan pernyataan sehingga mempunyai satu
nilai kebenaran. Bila suatu argumentasi benar, disebut valid dan bila salah disebut fallacy
atau tidak valid.
Hukum Silogisme
Argumentasi ini valid:
__________
Hukum modus ponens
Argumentasi ini valid:
_________
Hukum modus tolens:
Argumentasi ini valid:
___________
Contoh
14
1. Tentukan validitas dari argumentasi ini
__________
Solusi
Bila p maka q atau (~ p atau q) benar dengan ~ p benar maka dapat disimpulkan q
bisa benar atau salah. Jadi ~ q bisa benar atau salah. Jadi argumentasi tersebut tidak
valid.
2. Tentukan validitas dari argumentasi ini
__________
Solusi
benar bila kedua p dan q benar atau salah. Karena q benar maka p juga benar.
Jadi argumentasi tersebut valid.
Soal
1. Buktikan bahwa argumentasi di bawah ini valid.
__________
2. Tentukan validitas dari argumentasi di bawah ini.
__________
3. Tentukan validitas dari argumentasi di bawah ini.
__________
15
4. Untuk premis-premis yang diberikan tariklah suatu kesimpulan supaya argumentasinya
valid.
5. Untuk premis-premis yang diberikan tariklah suatu kesimpulan supaya
argumentasinya valid..
6. Untuk premis-premis yang diberikan tariklah suatu kesimpulan supaya
argumentasinya valid..
7. Untuk premis-premis yang diberikan tariklah suatu kesimpulan supaya
argumentasinya valid..
KUANTOR
Kuantor adalah notasi yang digunakan untuk menyatakan kuantitas suatu obyek dalam
logika matematika.
Contoh
1) Kuantor unive rsal :
“ ”, dibaca “semua” atau “setiap”.
2) Kuantor eksistensial :
“ ”, dibaca “beberapa” atau “terdapat paling sedikit satu” atau lebih singkat
“terdapat”.
“ “, dibaca “terdapat tepat satu”.
16
Contoh penggunaan
Misalkan suatu himpunan yang tidak kosong.
Bila punya sifat/predikat ditulis .
1) “ ” , dibaca “Untuk setiap , x bersifat ”, atau “semua
bersifat ”.
2) “ ” , dibaca “ Beberapa bersifat ”, atau “Terdapat paling
sedikit satu yang bersifat ”.
3) “ ”, digunakan pada 2) : “ ”, dibaca “Terdapat tepat satu
yang bersifat ”.
Contoh dalam negasi
1)
2)
3) di mana
4)
5)
6)
Contoh dalam definisi
1) Bilangan bulat n adalah bilangan kuadrat bila terdapat bilangan bulat k
sedemikian sehingga .
2) Himpunan A tidak kosong bila terdapat elemen a sedemikian sehingga .
3) Himpunan S dikatakan himpunan bagian dari T bila .
4) Fungsi disebut genap bila ,
5) Fungsi disebut ganjil bila
6) Diketahui himpunan-himpunan , dan . Himpunan A disebut
himpunan bagian sejati dari himpunan B bila dan
17
Induksi matematika
Seringkali kita akan menentukan bahwa suatu proposisi tertentu adalah
benar untuk setiap .
Misalnya atau
. Untuk membuktikannya, digunakan Prinsip Induksi Matematika.
Prinsip induksi matematika
Untuk membuktikan bahwa benar untuk :
1) Buktikan benar.
2) Asumsikan benar, buktikan benar.
Contoh
1. Buktikan
Solusi
, jadi benar atau untuk
Asumsikan benar, yaitu benar. Dibuktikan
benar, yaitu .
Catatan:
benar: pangkal, benar : konklusi induksi, Asumsi benar :
hipotesis induksi.
2. Buktikan
18
Solusi
jadi benar.
Asumsikan benar.
3. Buktikan
Solusi
Asumsikan benar.
4. Buktikan Rumus DeMoivre :
Solusi
jadi benar.
Asumsikan benar. Maka,
Soal
19
1) Buktikan
2) Buktikan
3) Buktikan
4) Buktikan Rumus Binomial :
Sesuai pada Teorema Binomial, buktikan dulu lemma:
5) Diketahui fungsi dengan sifat
Buktikan bahwa
6) Diketahui fungsi dengan sifat
Buktikan bahwa .
7) Buktikan bahwa
8) Buktikan bahwa adalah pembagi dari
9) Buktikan bahwa 6 adalah pembagi dari .
10) Buktikan bahwa 9 adalah pembagi dari
11) Buktikan bahwa untuk .
12) Buktikan bahwa :
20
PERTEMUAN 5: HIMPUNAN
Suatu himpunan adalah suatu kumpulan dari obyek-obyek. Obyek-obyek
tersebut dinamakan anggota-anggota atau elemen-elemen dari himpunan. Bila A adalah
suatu himpunan dan x adalah suatu elemen dari A, ditulis . Bila x bukan elemen
dari A, ditulis . Himpunan yang elemen-elemennya hanya a, b, c ditulis .
Himpunan dari semua x yang punya sifat ditulis .
Dua himpunan A dan B sama, ditulis A = B, bila : . Himpunan
A disebut himpunan bagian dari B, ditulis , bila setiap anggota dari A adalah juga
anggota dari B.
Himpunan yang tidak punya anggota, ditulis atau { }, adalah himpunan bagian
dari himpunan sebarang. disebut juga himpunan kosong.
Definisi
1) Produk (kartesius) dari A dan B, ditulis adalah :
2) Gabungan atau union dari A dan B, ditulis A È B, adalah :
3) Irisan atau intersection dari A dan B, ditulis , adalah :
4) Selisih dari A dan B, ditulis adalah :
dan
5) Himpunan kuasa dari A , ditulis , adalah :
Contoh
Misalkan A = {1, 2}, B = {1, 2, 3}, maka :
1)
2)
21
3)
4)
Aljabar dari himpunan, dualitas
Untuk U adalah himpunan semesta, adalah himpunan kosong, A, B, C adalah
himpunan sembarang, berlakulah huku-hukum di bawah ini.
Hukum Idempoten
1a. 1b.
Hukum Asosiatif
2a. 2b.
Hukum Komutatif
3a. 3b.
Hukum Distributif
4a. 4b.
Hukum Identitas
5a. 5b.
6a. 6b.
Hukum Involusi
7.
Hukum Komplemen
8a. 8b.
9a. 9b.
Hukum DeMorgan
10a. 10b.
Bukti
Sebagaicontoh, kta buktikan Hukum DeMorgan :
bhb bhb tidak benar bahwa ( atau )bhb ( dan
bhb
( dan )bhb .
22
Soal
1. Buktikan a. b.
2. Buktikan a. b.
3. Buktikan a. bhb b. bhb
4. Buktikan a. bhb b. bhb
5. Formula memberikan definisi operasi beda dinyatakan dengan operasi
interseksi dan komplemen. Carilah formula yang memberikan definisi dinyatakan
dengan operasi interseksi dan komplemen.
6. Suatu survei dari 100 mahasiswa, diperoleh data statistik sebagai berikut: 22 belajar
matematika, 20 belajar fisika, 45 belajar biologi, 15 belajar matematika dan biologi, 7
belajar matematika dan fisika, 10 belajar fisika dan biologi, 30 tidak belajar apa-apa.
a. Tentukan banyaknya mahasiswa yang belajar ketiga pelajaran tersebut.
b. Tentukan banyaknya mahasiswa yang hanya belajar satu pelajaran saja.
7. Yang dimaksud dengan beda simetrik dari himpunan-himpunan A dan B adalah
himpunan
a. Buktikan sifat asosiatif dari beda simetrik, yaitu
b. Buktikan sifat kanselasi dari beda simetrik, yaitu bila dan maka
c. Buktikan sifat distributif dari beda simetrik, yaitu
8. Buktikan bahwa
9, Carilah contoh yang menunjukkan bahwa .
10.Dari 60 mahasiswa yang belajar bahasa Inggris diketahui bahwa: 30 mahasiswa
pernah belajar bahasa Perancis, 48 mahasiswa pernah belajar bahasa Jerman, 20
mahasiswa pernah belajar bahasa Latin, 22 mahasiswa pernah belajar bahasa Perancis
dan bahasa Jerman, 18 mahasiswa pernah belajar bahasa Jerman dan bahasa Latin, 10
mahasiswa pernah belajar ketiga bahasa tersebut, dan 6 mahasiswa tak pernah belajar
satu pun dari ketiga bahasa tersebut. Tunjukkan bahwa terdapat kesalahan pada data di
atas.
23
PERTEMUAN 6: RELASI
Relasi
Bila A dan B adalah himpunan, yang dimaksud relasi dari A ke B adalah suatu
himpunan bagian dari .
Fungsi
Fungsi A ke B adalah suatu relasi dari A ke B sedemikian sehingga untuk setiap
terdapat satu dan hanya satu dimana (a, b) Î f. Bila untuk setiap
terdapat paling banyak satu dimana (a, b) Î f, f disebut fungsi parsial. Himpunan A
24
disebut domain dari fungsi f dan himpunan B disebut range dari fungsi f. Bila (a, b) Î f,
b = f(a) yaitu nilai dari f di a.
Definisi
1) Fungsi disebut surjektif atau onto bila :
2) Fungsi disebut injektif atau satu-ke-satu bila :
atau .
3) Fungsi disebut bijektif bila : f surjektif dan sekaligus injektif.
4) Image dari fungsi adalah :
Contoh
Misalkan dan maka :
1) adalah fungsi dari ke , dengan
. image dari fungsi
2) hanyalah relasi dari ke dan bukan fungsi dari
ke . Relasi f ini merupakan fungsi parsial dari ke .
3) Fungsi disebut predikat pada himpunan A. Misalnya
dapat didefinisikan fungsi sebagai predikat
pada dengan
Soal
1) Diketahui
a) Carilah :
b) Carilah :
2) Yang manakah relasi-relasi dari di bawah ini merupakan fungsi ?
.
a)
b)
25
y
z
d
c
b
a
c)
3) Apakah merupakan fungsi :
a) dari
b) dari
c) dari
d) dari ?
Relasi sebagai graph
Relasi R dari A ke B adalah himpunan bagian dari . Relasi R dapat disajikan
dengan diagram sebagai berikut :
Tulis elemen-elemen dari A pada satu garis dan tulis juga elemen-elemen dari B pada
satu garis lain. Untuk setiap , gambar panah dari titik a ke titik b. Penyajian ini
disebut bipartite graph representation dari R, dengan contoh sebagai berikut :
x
Bila A = B dapat digunakan penyajian lain dari R yang lebih menarik. Penyajian
ini disebut directed graph representation. Untuk menyajikan , gambar diagram
dengan satu titik untuk setiap elemen dari A; untuk setiap gambar panah dari
titik x ke titik y.
Titik-titik disebut nodes atau vertices, sedang panah-panah disebut edges. Hal ini
digambarkan sebagai berikut :
26
Bila x suatu node, banyaknya panah yang menuju x disebut in-degree ; sedangkan
banyaknya panah yang berasalah dari x disebut out-degree.
Definisi
1) Relasi R pada A disebut refleksif bila
2) Relasi R pada A disebut simetrik bila :
3) Relasi R pada A disebut transitif bila :
Bila relasi R simetrik, dapat digambarkan penyajian ke tiga dari R yang tidak
memerlukan arah panah, disebut undirected graph representation.
ba
d
c
d
a
b
c
27
Relasi R refleksif Relasi R tidak refleksif
Relasi R simetrik Relasi R tidak simetrik
Relasi R transitif
28
Undirected grah representation dari relasi
simetrik R diatas
Relasi R : refleksif, simetrik dan transitif
Misalkan relasi R pada A adalah transitif dan adalah
panah-panah dalam . Dengan sifat transitif, didapat : , sehingga juga didapat
.
Definisi
Misalkan adalah suatu relasi. Yang dimaksud dengan path dari ke
dalam adalah barisan sedemikian sehingga,
(i)
(ii)
(iii)
(iv)
Bila , path di atas disebut cycle. Bilangan n disebut panjang dari path di
atas. Suatu graph tanpa cycles disebut acyclic.
Proposisi
Relasi transitif bhb untuk setiap path dari berada di dalam maka
terdapat edge yang berada di dalam .
29
1) Misalkan dan relasi pada A adalah :
a. Gambarkan bipartite graph representation dari .
b. Gambarkan directed graph representation dari .
c. Cek apakah refleksif, simetrik atau transitif.
2) Misalkan Apakah refleksif ? Apakah
refleksif ? Gambarkan kedua relasi tersebut sebagai bepartite graphs
dan directed graphs.
3) Pandang undirected graph ini :
Sajikan graph ini sebagai suatu relasi.
4) Gambarlah suatu directed graph yang simetrik dan transitif, tetapi tidak
refleksif.
5) Suatu relasi yang refleksif, simetrik dan transitif disebut relasi ekivalen.
Berikan deskripsi dari directed graph dari relasi ekivalen.
6) Misalkan
a. Daftar semua relasi .
b. Daftar semua relasi .
c. Dari relasi-relasi dalam a. dan b. , mana yang refleksif, simetrik, transitif?
Relasi ekivalen
Suatu relasi yang refleksif, simetrik dan transitif disebut relasi ekivalen.
Definisi
Misalkan adalah suatu relasi ekivalen dan misalkan .
Klasekivalen dari a terhadap R, ditulis , adalah
30
4x
2x
3x
, disingkat .
Teorema
Bila adalah relasi ekivalen pada , dan , maka :
(i) bila .
(ii) bila .
(iii) .
Graph dari relasi ekivalen
Definisi
Bila R adalah relasi ekivalen pada A, maka yang disebut quotient set adalah
Definisi
Misalkan A adalah suatu himpunan. Himpunan bagian dari P(A) disebut
partisi dari A bila setiap adalah tidak kosong dan untuk setiap , terdapat
tepat satu sedemikian sehingga .
31
1
3
2
Teorema
Himpunan bagian dari P(A) merupakan partisi pada A bhb untuk
suatu relasi ekivalen R pada A.
Soal
1) Diketahui dan R suatu relasi dari pada A di mana
Buktikan bahwa R adalah relasi ekivalen dan carilah .
2) Diketahui dan R suatu relasi dari pada A di mana
Buktikan bahwa R adalah relasi ekivalen dan carilah .
3) Misalkan A dan B adalah himpunan dan suatu fungsi. Didefinisikan :
kernel dari
Buktikan bahwa untuk f sebarang, adalah relasi ekivalen.
4) Buktikan :
32
Bila R adalah relasi ekivalen pada A, terdapatlah himpunan B dan fungsi
sedemikian sehingga
Komposisi relasi
Misalkan A, B, dan C adalah himpunan-himpunan. Misalkan juga R adalah relasi
dari A ke B dan S adalah relasi dari B ke C. Jadi dari definisi relasi, R adalah himpunan
33
bagian dari dan S adalah himpunan bagian dari Dibentuk relasi komposisi
dari R dan S, yaitu dari A ke C yang didefinisikan sebagai
Kadang-kadang relasi dasingkat RS.
Contoh
1. Misalkan , dan . Misalkan juga
Maka
karena dan serta Juga didapat
karena Dapat disimpulkan
Teorema
Misalkan A, B, C, D adalah himpunan-himpunan. Misalkan juga R adalah relasi
dari A ke B, S relasi dari B ke C, dan T relasi dari C ke D. Maka
Invers relasi
Misalkan R adalah relasi dari A ke B. Yang dimaksud dengan invers relasi dari R, ditulis adalah relasi dari B ke A dengan
Contoh
1. Misalkan dan R adalah relasi pada A di mana maka adalah juga relasi pada A dengan
2. Invers dari relasi ”x adalah suami y” adalah relasi ”y adalah isteri x”.
PERTEMUAN 7 : FUZZY SET
Pendahuluan
Misalkan X merupakan himpunan semesta. Yang dimaksud dengan himpunan
kabur atau fuzzy set A adalah dikarakterisir dengan fungsi karakteristik yang diperumum
atau fungsi keanggotaan dari X ke selang tertutup
34
Contoh
1.Misalkan X adalah himpunan dari semua pabrik mobil. Himpunan kabur A
dikarakterisir dengan fungsi keanggotaan di mana adalah
prosentase mobil x digunakan di Jakarta.
2. Misalkan himpunan semesta X adalah himpunan dari semua mahasiswa yang
mengambil mata kuliah Matematika Diskrit K0144. Himpunan kabur B dikarakterisir
dengan fungsi keanggotaan di mana adalah IPK x dibagi 4.
3. Misalkan X adalah himpunan semesta. Himpunan biasa atau crisp set C dapat
dikarakterisir dengan fungsi keanggotaan fungsi karakteristik biasa pada C. Ingat bahwa
fungsi karakteristik biasa pada C atau adalah fungsi dari X ke selang tertutup
dengan
Dua himpunan kabur A dan B disebut sama, ditulis bila dan hanya bila
Bila himpunan semesta berhingga, himpunan kabur D,
misalnya dapat ditulis sebagai
atau sebagai “jumlah”
atau dengan notasi
Himpunan (kabur) kosong dan himpunan(kabur) semesta
Misalkan X adalah himpunan semesta.Himpunan kabur kosong dikarakterisir
dengan fungsi keanggotaan fungsi nol dari X yaitu sedangkan
himpunan kabur semesta dikarakterisir dngan fungsi keanggotaan
Support dari himpunan kabur
Misalkan X adalah himpunan semesta. Support dari himpunan kabur A:supp
35
Untuk himpunan kabur A dengan penulisan
maka supp
cut dari himpunan kabur
Misalkan X adalah himpunan semesta. Untuk yang dimaksud dengan
dari himpunan kabur A adalah
Untuk himpunan kabur A dengan penulisan
maka dari himpunan kabur A adalah
Inklusi untuk himpunan kabur
Diberikan dua himpunan kabur A dan B dari himpunan semesta X. Himpunan A
disebut himpunan bagian dari himpunan B ditulis bila
Operasi himpunan kabur
Diberikan dua himpunan kabur A dan B dari himpunan semesta X. Gabungan
dari himpunan-himpunan kabur A dan B dikarakterisir dengan fungsi keanggotaan
sedangkan irisan dari himpunan-
himpunan kabur A dan B dikarakterisir dengan fungsi
keanggotaan Untuk komplemen dari
himpunan kabur A dikarakterisir dengan fungsi keanggotaan
Soal
Misalkan himpunan semesta adalah Himpunan-
himpunan kabur A, B dan C berturut-turut dikarakterisir oleh fungsi-fungsi keanggotaan
Dengan menggambarkan kurva fungsi keanggotaannya,
1. Tentukan himpunan kabur
2. Tentukan himpunan kabur
36
3. Tentukan himpunan kabur
4. Tentukan himpunan kabur
5. Tentukan himpunan kabur
6. Tentukan himpunan kabur
7. Tentukan himpunan kabur
8. Tentukan himpunan kabur
PERTEMUAN 13: ALJABAR BOOLE
Definisi dasar
Baik himpunan-himpunan maupun pernyataan-pernyataan, keduanya mempunyai
sifat-sifat yang mirip, yang disebut hukum-hukum identikal. Hukum-hukum ini
digunakan untuk mendefinisikan struktur matematika yang abstrak yang disebut aljabar
Boole.Nama tersebut diambil dari matematikawan Inggris Geoge Boole (1815-1864).
Misalkan B adalah himpunan tidak kosong dengan dua operasi biner + dan ,
satu operasi unari ‘, dan dua elemen yang berbeda 0 dan 1. Himpunan B disebut aljabar
Boole, bila aksioma-aksioma di bawah ini dipenuhi, di mana a, b, c adalah lemen-elemen
sembarang dalam B.
37
(B1) Hukum-hukum komutatif:
(B2) Hukum-hukum distributif:
(B3) Hukum-hukum identiti:
(B4) Hukum-hukum komplemen:
Kadang-kadang aljabar Boole ditulis dengan notasi di mana 0 disebut
elemen nol, 1 disebut elemen satuan dan disebut komplemen dari a. Sebagaimana
pada hasilkali biasa pada bilangan-bilangan real, tanda tidak akan dituliskan. Misalnya
artinya
Operasi-operasi +, dan ‘ berturut-turut disebut jumlah, hasilkali dan
komplemen.Kita mengikuti aturan yang berarti yang berarti
Contoh
1. Misalkan dengan dua operasi biner + dan yang didefinisikan sebagai
+ 1 0
1 1 1
0 1 0
1 0
1 1 0
0 0 0
dan operasi unari ‘ didefinisikan sebagai dan Maka B merupakan aljabar
Boole.
38
2. Misalkan C koleksi dari himpunan yang tertutup terhadap union, interseksi dan
komplemen. Maka C merupakan aljabar Boole dengan himpunan kosong sebagai
elemen nol dan himpunan semesta U sebagai elemen 1.
3. Misalkan adalah himpunan dari pembagi-pembagi 70 yaitu
Didefinisikan dan ‘ pada sebagai
kelipatan persekutuan terkecil dari a dan b, pembagi persekutuan terbesar dari a,
Maka merupakan aljabar Boole dengan 1 sebagai elemen nol dan 70 sebagai elemen
satuan.
Dualitas
Dual dari pernyataan sembarang dalam suatu aljabar Boole B adalah pernyataan
yang diperoleh dengan menukar operasi-operasi + dan dan menukar elemen-elemen 0
dan 1 dalam pernyataan semula. Sebagai contoh, dual dari adalah
Perhatikan sifat simetri dalam aksioma-aksioma dari aljabar Boole B.Yaitu, dual dari
aksioma juga aksioma dalam aljabar Boole B. Berdasarkan hal tersebut, diperoleh hasil
Prinsip Dualitas yang penting, yang dinyatakan sebagai
Teorema 1 (Prinsip Dualitas):
Dual dari teorema sembarang dalam dalam aljabar Boole juga merupakan suatu teorema.
Menggunakan aksioma-aksioma (B1) sampai dengan (B4) dalam aljabar Boole B,
diperoleh
Teorema 2
Misalkan adalah elemen-elemen sembarang dalam aljabar Boole B. Maka berlaku
(i) Hukum-hukum idempoten:
(ii) Hukum-hukum keterbatasan:
(iii) Hukum-hukum absorpsi:
(iv) Hukum-hukum asosiatif:
Teorema 3
Misalkan a adalah elemen sembarang dalam aljabar Boole B.Maka berlaku
(i) Hukum Ketunggalan Komplemen: Bila maka
39
(ii) Hukum Involusi:
(iii)
Teorema 4 (Hukum-hukum DeMorgan)
Misalkan adalah elemen-elemen sembarang dalam aljabar Boole B.Maka berlaku
(i)
Disain rangkaian skakelar listrik (rangkaian logika)
Misalkan merupakan skakelar listrik, dan misalkan untuk skakelar A, A’
menunjukkan skakelar listrik bila A hidup A’mati dan bila A mati A’ hidup. A dan B dapat
dihubungkan seri, ditulis atau paralel ditulis Disain rangkaian skakelar
listrik Boole adalah susunan dari kawat dan skakelar yang disusun dengan penggunaan
berulang-ulang dari kombinasi seri dan paralel. Jadi rangkaian tersebut dapat dapat ditulis
dengan notasi dan
Teorema 5
Aljabar dari rangkaian skakelar listrik Boole merupakan aljabar Boole.
Soal
1. Gambarkan ungkapan (ekspresi) Boole Sederhanakan
ungkapan (ekspresi) Boole dan kemudian gambarkan hasilnya.
2. Gambarkan ungkapan (ekspresi) Boole Sederhanakan
ungkapan (ekspresi) Boole dan kemudian gambarkan hasilnya.
PERTEMUAN 15: DNF (Disjunction Normal Form)
Pandang himpunan dari peubah-peubah (huruf atau simbol), misalkan
Yang dimaksud dengan ekspresi Boole E dalam peubah-peubah ini,
biasanya ditulis sebagai , adalah peubah sembarang atau ekspresi
sembarang yang dibangun oleh peubah-peubah tersebut menggunakan operasi-operasi
Boole dan ‘. Sebagai contoh,
dan
merupakan ekspresi Boole dalam peubah x, y, z.
Yang dimaksud dengan literal adalah peubah atau komplemen dari peubah,
misalnya dsb.
40
Produk Fundamental
Yang dimaksud dengan produk fundamental adalah literal atau produk dari dua atau
lebih literal di mana tidak ada dua literal yang mengandung peubah yang sama. Misalnya,
semuanya merupakan produk fundamental. Tetapi dan keduanya bukan
produk fundamental.
Produkfundamental dikatakan termuat dalam produkfundamental lain bila
literal-literal dari juga iteral-literal dari Sebagai contoh termuat dalam
tetapi tidak dalam karena x’ bukan literal dari produk fundamental kedua.
Bila produk fundamental termuat dalam produk fundamental maka dengan
hukum absorpsi Misalnya termuat dalam diperoleh
DNF & Metodanya
Ekspresi Boolean E merupakan disjunctive normal form (dnf) bila E adalah produk
fundamental atau jumlah dari dua atau lebih produk fundamental di mana tak ada produk
fundamental yang termuat dalam produk fundamental yang lain. Sebagai contoh,
dan
Yang pertama bukan dnf karena termuat dalam sedang yang kedua juga
bukan dnf karena termuat dalam
Menggunakan hukum-hukum aljabar Boole, kita dapat mengkonstruksikan algoritma
untuk mengubah ekspresi Boole sembarang E ke bentuk dnf, dengan cara sbb.
(1) Menggunakan hukum-hukum de Morgan dan involusi, kita dapat menjalankan
operasi komplemen ke dalam kurung sembarang sampai akhirnya hanya terdapat
komplemen dari peubah-peubah. Kemudian E hanya mengandung jumlahan dan
produk dari literal saja.
(2) Menggunakan hukum distributif, kita dapat terus mengubah E ke dalam
jumlahan dari produk-produk, lalu menggunakan hukum-hukum komutatif,
idempoten dan absorpsi, kita akhirnya dapat mengubah E dalam dnf.
Sebagai contoh, dengan (1)
41
Kemudian dengan (2),
yang berbentuk dnf.
Full DNF
Ekspresi Boole disebut full disjunctive normal form bila
merupakan dnf dan setiap produk fundamental mengandung semua peubah. Kita dengan
mudah dapat mengubah dnf ke dalam full dnf dengan mengalikan setiap produk
fundamental P dari E dengan bila P tidak mengandung Sebagai contoh, kita
dapat mengubah di atas ke dalam full dnf dengan
Perlu dicatat bahwa sehingga mengalikan dengan dibolehkan.
Teorema
Setiap ekspresi Boole yang tidak sama dengan nol dapat
dituliskan dalam full dnf dengan tunggal.
Contoh
1. Nyatakan ekspresi Boolean berikut dalam dnf dan dalam full dnf
Solusi
dalam dnf. Juga,
dalam full dnf.
2. Nyatakan ekspresi Boolean berikut dalam dnf dan dalam full dnf
Solusi
42
dalam dnf. Juga,
dalam full dnf.
3. Nyatakan ekspresi Boolean berikut dalam dnf dan dalam full dnf
Solusi
dalam dnf. Bentuk terakhir ini bisa dipandang sebagai
dalam bentuk full dnf bila peubah-peubahnya hanya x dan y. Tetapi dalam soal jelas
bahwa peubah-peubahnya diketahui dalam x, y, z. Jadi
dalam full dnf.
PERTEMUAN 16: TEORI GRAPH
Pengertian dan konsep dasar
Graph G terdiri dari dua bagian:
(i) Himpunan V yang elemen-elemennya disebut titik-titik atau nodes.
(ii) Himpunan E dari pasangan-pasangan tak berurutan dari titik-titik yang
berlainan yang disebut rusuk-rusuk atau edges.
Kita menulis graph sedemikian dengan untuk menekankan dua bagian dari
graph G tersebut. Titik-titik u dan v disebut bersebelahan atau adjacent bila terdapat
rusuk Kita menggambarkan graph dengan diagram secara alami. Dalam hal ini
setiap titik v dalam V disajikan dengan lingkaran kecil atau dot, dan setiap rusuk
disajikan dengan kurva yang menghubungkan titik-titik ujung dan
Pada graph biasanya tidak dibolehkan adanya rusuk ganda atau multiple edges,
yaitu adanya lebih dari satu rusuk yang menghubungkan dua titik pada graph tersebut.
Pada graph juga tidak dibolehkan adanya loop, yaitu rusuk yang titik-titik
ujungnya sama. Graph dengan dua sifat ini disebut multigraph. Yang dimaksud
43
dengan walk adalah multigraph yang terdiri dari barisan yang bergantian dari titik dan
rusuk dengan bentuk
Sedangkan path adalah walk di mana semua titik-titiknya berlainan.
Misalkan adalah graph. Misalkan juga V’ himpunan bagian dari V , dan E’
adalah himpunan bagian dari E yang memuat semua rusuk dari E yang titik-titik
ujungnya merupakan elemen dari V’. Dalam hal ini merupakan subgraph dari
graph
Komponen dari graph
Graph disebut terhubung atau connected bila antara dua titik sembarang terdapat
suatu path yang menghubungkan dua titik tersebut. Subgraph terhubung dari graph
disebut komponen terhubung dari bila dia tidak termuat dalam
subgraph terhubung sembarang yang lebih besar. Secara intuitif jelas bahwa setiap graph
dapat dipartisi ke dalam komponen-komponen terhubungnya.
Jarak antara dua titik dan diameter
Jarak antara dua titik u dan v dari graph terhubung G, ditulis , adalah panjang
dari path terpendek antara u dan v. Diameter dari graph terhubung G adalah jarak
maksimum dari dua titik sembarang dari G.
Misalkan v adalah titik dari graph G. Yang dimaksud dengan adalah adalah graph
yang diperoleh dari G dengan menghilangkan v dan semua rusuk-rusuk yang berinsiden
dengan v. Titik v dalam graph terhubung G disebut titik potong atau cut point bila
menjadi tak terhubung.
44
PERTEMUAN 20: PEWARNAAN GRAPH
Pewarnaan titik
Pewarnaan titik dari graph G adalah penentuan warna pada titik-titik G,
sedemikian sehingga titik-titik yang bersebelahan mempunyai warna-warna berlainan.
Banyaknya warna minimum yang diperlukan untuk mewarnai G disebut bilangan
kromatik atau chromatic number dari G dan ditulis dengan simbol
Kita berikan algoritma Welch dan Powell untuk mewarnai
graph G. Langkah pertama adalah mengurutkan titik-titik dari G berdasarkan degreenya
yang menurun (urutan ini tidak tunggal karena ada titik-titik yang punya degree sama).
Langkah kedua adalah memberikan warna pertama untuk titik pertama. Untuk mewarnai
selanjutnya adalah secara barisan, warnai setiap titik yang tidak bersebelahan dengan titik
yang diwarnai sebelumnya dengan warna yang sama. Ulangi proses yang sama
menggunakan warna kedua dan barisan bagian dari titik-titik yang belum diwarnai.
Lanjutkan prosesnya dengan warna ketiga, dst. sampai semua titik-titik terwarnai. Kita
memakai algoritma Welch-Powell untuk mewarnai graph G pada Gambar 6-5.
45
Mengurutkan titik-titik menurut degreenya yang menurun diperoleh barisan
Warna pertama digunakan untuk mewarnai titik-titik dan Warna kedua dipakai
untuk mewarnai titik-titik Warna ketiga dipakai untuk mewarnai titik-titik
dan sehingga Perlu dicatat bahwa karena dan
harus diwarnai berlainan. Jadi Juga, graph komplit atau lengkap dengan n
titik simpul memerlukan n warna dalam pewarnaan sembarang, karena setiap titik simpul
bersebelahan dengan setiap titik simpul lainnya.
Contoh
1. Perhatikan Gambar 6-18. Gunakan algoritma Welch-Powell untuk mewarnai
(pewarnaan titik) graph pada gambar tersebut.
Solusi
Dikerjakan secara barisan, kita pakai warna pertama untuk mewarnai titik-titik simpul H,
B, dan lalu G.( Kita tidak dapat mewarnai A, D, atau F dengan warna pertama karena
masing-masing terhubung dengan H. Kerjakan terus secara barisan dengan titik-titik
simpul yang belum diwarnai, kita pakai warna kedua untuk titik-titik simpul A dan D.
Titik-titik simpul sisanya F, C dan E dapat diwarnai dengan warna ketiga. Jadi bilangan
kromatik n tidak dapat melebihi 3. Pada setiap pewarnaan, H, D, dan E harus diwarnai
berlainan, karena mereka terhubung satu sama lain. Jadi
Pewarnaan rusuk
Pewarnaan rusuk dari graph G adalah penentuan warna pada rusuk-rusuk G, sedemikian
sehingga rusuk-rusuk yang bersebelahan mempunyai warna-warna berlainan. Banyaknya
warna yang diperlukan dibuat minimum.
Contoh
1. Perhatikan graph pada halaman 149. Pewarnaan rusuk graph tersebut dikerjakan
sebagai berikut:
1) kita beri warna pertama.
2) dan kita beri warna pertama juga, karena dan tidak saling terhubung
langsung oleh sebuah titik.
46
3) kita beri warna kedua.
4) dan dapat diberi warna kedua juga, karena dan juga tidak saling
terhubung melalui sebuah titik.
5) dan dapat diberi warna ketiga.
6) Terakhir, kita beri warna keempat.
Jadi bilangan kromatik (pewarnaan rusuk) dari graph di atas adalah empat, atau
2. Pada pewarnaan rusuk untuk graph lengkap bilangan kromatik dari memenuhi
rumus:
Pewarnaan daerah
Pandang suatu map M, yaitu representasi planar dari multigraph planar yang berhingga. Dua daerah dari M dikatakan bersebelahan bila mereka mempunyai suatu rusuk berserikat. Yang dimaksud dengan pewarnaan daerah dari M adalah penentuan warna pada setiap daerah dari M sedemikian sehingga daerah-daerah yang bersebelahan mempunyai warna yang berlainan. HAL 149
Contoh
1. Sebagai contoh, pada Gambar 6-6 (a) daerah-daerah dan bersebelahan,
sedangkan dan tidak. Map pada Gambar 6-6 (a) mempunyai bilangan kromatik tiga,
yaitu banyaknya warna minimum untuk pewarnaan daerah dari map tersebut. Hal ini
mengingat: diberi warna merah, putih, merah, putih, merah dan biru.
47
2. Gambar 6-7 memperlihatkan map yang sangat sederhana, yang memerlukan empat
warna pada pewarnaan (daerah) sembarang.
Soal
1. Carilah bilangan kromatik untuk pewarnaan daerah pada setiap map pada Gambar 6-
30.
PERTEMUAN 21: TREE GRAPH
Suatu graph terhubung tanpa cycle disebut tree atau pohon. Pada Gambar 5-11
diperlihatkan enam pohon masing-masing dengan enam titik simpul. Subgraph T dari
graph G disebut spanning tree dari G bila T merupakan tree dan memuat semua titik
simpul dari G. Gambar 6-8 memperlihatkan graph G dengan spanning trees dan
dari G. Bila G adalah suatu graph yang rusuk-rusuknya mempunyai panjang, maka yang
dimaksud dengan minimal spanning tree dari G adalah spanning tree dari G di mana
jumlah panjang dari rusuk-rusuknya minimal di antara semua spanning tree dari G.
Pandang graph G yang merupakan graph terhubung berlabel berhingga dengan m titik-
48
titik simpul. Di bawah ini kita berikan dua algoritma untuk mendapatkan minimal
spanning tree dari G.
Algoritma I.
Pertama, urutkan rusuk-rusuk dari G sesuai dengan panjangnya secara menurun.
Kerjakan secara barisan, hilangkan setiap rusuk yang tidak memutus (membuat tidak
terhubung) graph G sampai tinggal rusuk. Rusuk-rusuk ini membentuk minimal
spanning tree dari G. Algoritma ini bergantung pada diketahuinya graphnya terhubung,
yang pada umumnya tidak mudah dibuat programnya.
Algoritma II.
Dimulai dengan mengurutkan rusuk-rusuk dari G sesuai dengan panjangnya
secara menaik. Kemudian, dimulai dengan hanya titik-titik simpul dari G, kita
tambahkan rusuk satu persatu di mana setiap rusuk punya panjang minimal dan tidak
membentuk cycle manapun. Setelah menambahkan rusuk, kita dapatkan minimal
spanning tree dari G. Gambar 6-9 memberikan graph terhubung berlabel G dan minimal
spanning tree M.
Contoh
1.Tentukan semua spanning trees dari graph G pada Gambar 6-20.
Solusi
Terdapat delapan spanning trees dari graph G sebagaimana diperlihatkan pada Gambar 6-
21. Setiap spanning tree mempunyai tiga rusuk. Jadi setiap spanning tree dapat diperoleh
dengan menghilangkan dua dari lima rusuk G. Ini dapat dikerjakan dalam sepuluh cara,
kecuali dua di antaranya menjadi graph tak terhubung. Jadi delapan spanning trees di atas
merupakan semua spanning trees dari G.
2. Carilah minimum spanning tree untuk graph dengan rusuk-rusuk berlabel pada
Gambar 6-22.
Solusi
Terus hilangkan rusuk-rusuk dengan panjang maksimum tanpa membuat graph menjadi
tidak terhubung. Cara lain, mulai dengan sembilan titik simpul, terus tambahkan rusuk-
rusuk dengan panjang minimum tanpa membuat cycle manapun. Kedua cara
menghasilkan minimum spanning tree sebagaimana ditunjukkan pada Gambar 6-23.
49
PERTEMUAN 23: FINITE AUTOMATA
Kita bisa memandang suatu komputer digital sebagai suatu mesin yang berada di
dalam “internal state” tertentu pada waktu yang diberikan sembarang. Komputer tersebut
“membaca” input symbol , dan kemudian “mencetak” output symbol dan mengubah
“state”nya. Output symbol bergantung hanya pada input symbol dan internal state dari
mesin, dan internal state dari mesin bergantung hanya pada state sebelumnya dan input
symbol sebelumnya. Gagasan ini diformalisasikan pada definisi berikut.
Definisi
Suatu finite state machine M terdiri dari lima bagian:
50
(1) Himpunan berhingga A dari input symbols.
(2) Himpunan berhingga S dari internal states.
(3) Himpunan berhingga Z dari output symbols.
(4) Next-state function f dari ke S.
(5) Output function g dari ke Z.
Mesin M ini ditulis dengan sewaktu kita ingin menekankan lima
bagiannya. Kadang-kadang diberikan juga initial state atau state awal di dalam S, dan
mesin M ditulis dengan
Contoh
Di bawah inidiberikan finite state machine M dengan dua input symbols, tiga internal
states dan tiga output symbols:
(1)
(2)
(3)
(4) Next-state function f dari ke S didefinisikan dengan
(5) Output function g dari ke Z didefinisikan dengan
Menurut tradisi, untuk menunjukkan states digunakan simbol q dan untuk menunjukkan
initial state digunakan simbol
Finite Automata
Finite automaton adalah mirip finite state machine kecuali bahwa automaton mempunyai
“accepting” dan “rejecting” states. Secara spesifik, finite automaton M terdiri dari lima
bagian, yaitu:
(1) Himpunan berhingga A dari input symbols.
(2) Himpunan berhingga S dari internal states.
(3) Himpunan bagian T dari S ( yang elemen-elemennya disebut accepting states)
(4) Initial state di dalam S.
(5) Next-state function f dari ke S.
51
Automaton M ini ditulis dengan sewaktu kita ingin menekankan
lima bagiannya.
Contoh
1. Di bawah ini mendefinisikan suatu finite automaton dengan dua input symbols dan tiga
states:
(1) , input symbols
(2)
(2) , accepting states
(4) , initial state.
(5) Next-state function f dari ke S didefinisikan dengan
Kita dengan ringkas dapat mendiskripsikan finite automaton M dengan state
diagramnya sebagaimana dikerjakan dengan finite state machine, kecuali bahwa di sini
kita menggunakan lingkaran dobel untuk accepting states dan setiap rusuk dilabel hanya
dengan input symbol. Secara spesifik, state diagram D dari M adalah graph berarah yang
dilabel yang titik-titiknya adalah states dari S di mana accepting states dilabel
menggunakan lingkaran dobel; dan bila maka terdapat busur dari ke
yang dilabel dengan Juga initial state ditunjukkan dengan panah menuju titik
Sebagai contoh, state diagram dari automaton M dari contoh di atas diberikan dalam
Gambar 7-9.
Diberikan string berhingga dari input symbols dari automaton M,
kita peroleh barisan dari states di mana adalah initial state dan
untuk Kita katakan bahwa M mengenal atau menerima string W bila
final state adalah accepting state, yaitu bila Kita gunakan untuk
menunjukkan himpunan semua string yang dikenal oleh M. Sebagai contoh, kita dapat
memperlihatkan bahwa automaton M dalam contoh di atas akan mengenal semua string
yang tidak mempunyai dua b yang berurutan . Jadi M akan menerima
dan akan menolak
52
53