Download - Makalah Erick matematika diskrit 2013
Universitas Putra Batam2013 / 2014
TUGAS MANDIRI
MATEMATIKA DISKRIT
Disusun Oleh :
Nama : Erik Sutrisno
NPM : 130210144
Prodi : Teknik Informatika
Dosen : Renita, S.Si
UNIVERSITAS PUTRA BATAM
2013 / 2014
Universitas Putra Batam2013 / 2014
KATA PENGANTAR
Assalamualaikum Wr. Wb.
Dengan memanjatkan puji syukur kehadirat Tuhan Yang Maha Esa, atas segala
limpahan rahmat dan karunia-Nya kepada saya sehingga dapat menyelesaikan makalah ini yang
berjudul “Matematika Diskrit”. Mungkin pembaca juga mengetahui bahwa didalam pembuatan
makalah ini tidak lepas dari bantuan berbagai pihak, untuk itu dalam kesempatan ini saya
menghaturkan rasa hormat dan terima kasih yang sebesar - besarnya kepada semua pihak yang
membantu dalam pembuatan makalah ini.
Saya menyadari bahwa dalam proses penulisan makalah ini masih jauh dari
kesempurnaan baik itu dari materi maupun cara penulisannya. Namun demikian, saya telah
berupaya dengan segala kemampuan dan pengetahuan yang saya miliki, serta dengan waktu yang
begitu singkat buat saya. Karena dengan selingan waktu kerja dan waktu kuliah yang saya jalani,
terasa begitu berat. Tapi, saya menganggap nya dengan sebuah tantangan di dalam kehidupan
saya. Sehingga dengan ketekunan, makalah ini dapat selesai dengan baik.
Kami juga menyadari sepenuhnya bahwa di dalam makalah ini terdapat kekurangan-
kekurangan dan jauh dari apa yang kami harapkan. Untuk itu, kami berharap adanya kritik, saran
dan usulan dari pembaca demi perbaikan di masa yang akan datang.
Semoga makalah yang sederhana ini dapat dipahami bagi siapapun yang membacanya.
Sekiranya makalah yang telah disusun ini dapat bermanfaat bagi kami sendiri maupun orang
yang membacanya. Sebelumnya kami mohon maaf apabila terdapat kesalahan kata - kata yang
kurang berkenan.
Akhir kata kami ucapkan terima kasih.
Batam, November 2013
Penyusun
Universitas Putra Batam2013 / 2014
PENDAHULUAN
Pada umumnya, belajar matematika identik dengan menghafalkan rumus-rumus
tertentu. Dengan buku paket dan LKS yang sangat tebal dan banyak. Itulah yang menyebabkan
para pelajar / siswa merasa bosan untuk belajar matematika. Seringkali mereka bertanya, " Apa
sih manfaat belajar matematika dalam kehidupan sehari-hari ? “. Pertanyaan - pertanyaan seperti
itu sudah sering mereka lontarkan kepada guru-guru pembimbing mereka. Pertanyaan itu mereka
lontarkan karena mereka sudah kesal terhadap pelajaran mereka yang terasa membosankan dan
tidak perlu. Tetapi sebenarnya, matematika sangat berfungsi dalam kehidupan sehari-hari, baik
yang paling mudah sampai yang tersulit sekalipun.
Matematika sebagai media untuk melatih berpikir kritis, inovatif, kreatif, mandiri dan
mampu menyelesaikan masalah sedangkan bahasa sebagai media menyampaikan ide-ide dan
gagasan serta yang ada dalam pikiran manusia. Jelas sekali bahwa Matematika sangat berperan
dalam kehidupan sehari-hari, kita tidak dapat menghindar dari Matematika, sekalipun kita
mengambil jurusan ilmu sosial tetap saja ada pelajaran Matematika di dalamnya karena mau
tidak mau matematika digunakan dalam aktivitas sehari-hari. Salah satunya penerapan himpunan
dalam kehidupan sehari-hari.
Dalam matematika, himpunan adalah segala koleksi benda-benda tertentu yang
dianggap sebagai satu kesatuan. Walaupun hal ini merupakan ide yang sederhana, tidak salah
jika himpunan merupakan salah satu konsep penting dan mendasar dalam matematika modern,
dan karenanya, studi mengenai himpunan sangatlah berguna.
Pengertian himpunan merupakan salah satu dasar dari matematika. Konsep dalam
matematika dapat dikembalikan pada pengertian himpunan, misalnya garis adalah himpunan
titik. Sebetulnya pengertian himpunan mudah dipahami dan dapat diterima secara intuitif. Tetapi
dalam matematika dapat dibuat definisinya. Kata himpunan dan kumpulan digunakan dalam
definisi secara bersamaan, meskipun keduanya mempunyai arti yang sama. Demikian pula
dengan kata himpunan dan koleksi.
Bukan hanya himpunan saja, tetapi logika, matriks, fungsi, relasi, bilangan bulat dan
lain sebagai nya juga sangat berfungsi di dalam kehidupan kita sehari – hari. Ilmu – ilmu
matematika diskrit sangat lah berfungsi untuk kita semua di dalam kehidupan kita sehari – hari.
Universitas Putra Batam2013 / 2014
Daftar Isi
Kata Pengantar 1
Pendahuluan 2
Daftar Isi 3
Bab I Logika 5
I. 1. Pernyataan 52. Operasi / Perangkai Logika 63. Tabel Kebenaran 6
Bab II Himpunan 17
II. 1. Teknik Penyajian Himpunan 18
2. Kardinalitas 19
3. Jenis – jenis Himpunan 20
4. Operasi Terhadap Himpunan 22
5. Himpunan Crisp dan Himpunan Fuzzy 26
6. Manfaat Belajar Himpunan Dalam Kehidupan Sehari-Sehari 28
Bab III Matriks 29
III. 1. Jenis – Jenis Matriks 29
2. Operasi Aritmatika Matriks 31
Bab IV Relasi 33
IV. 1. Representasi Relasi 34
2. Sifat – sifat relasi 36
3. Klosur Relasi 39
4. Relasi Inversi 41
5. Mengkombinasikan Relasi 42
6. Mengkombinasi kan Relasi dengan Matriks 42
7. Komposisi Relasi 43
Universitas Putra Batam2013 / 2014
8. Relasi n – Ary 46
8.1. Basis Data 48
8.2. Query 48
V. Fungsi 52
V. 1. Jenis – Jenis Fungsi 54
2. Fungsi Berdasarkan Daerah Hasil 56
3. Fungsi Komposisi 58
4. Fungsi Infers 60
VI. Algoritma Dan Bilangan Bulat 63
VI. 1. Algoritma 63
1. A. Notasi Untuk Algoritma 63
1. B. Teorema Euclidean 64
1. C. Algoritma Euclidean 65
1. D. Pembagi Bersama Terbesar (PBB) 66
1. E. Kombinasi Lanjar 66
1. F. Relatif Prima 68
1. G. Aritmetika Modulo 68
1. H. Kongruen 69
2. Bilangan Bulat 73
2.A. Proposisi Bilangan bulat 73
2. B. Prinsip induksi sederhana 73
2. C. Prinsip induksi yang dirampatkan 74
Penutup 75
Daftar Pustaka 75
Universitas Putra Batam2013 / 2014
BAB I
LOGIKA
1. PERNYATAAN
Pernyataan adalah suatu kalimat yang mempunyai nilai kebenaran benar saja atau salah
saja dan tidak kedua-duanya. Istilah - istilah lain nya dari pernyataan adalah kalimat matematika
tertutup, kalimat tertutup, kalimat deklaratif, statement atau proposisi.
A. Pernyataan Tunggal
Pernyataan tunggal atau pernyataan sederhana adalah pernyataan yang tidak memuat
pernyataan lain atau sebagai bagiannya
Contoh dari pernyataan tunggal :
Ibu kota Provinsi Jawa Barat adalah Semarang
Soekarno adalah Presiden Indonesia yang pertama
6 adalah bilangan genap
Batu adalah benda padat
22 + 5 = 27
B. Pernyataan Majemuk
Pernyataan majemuk dapat merupakan kalimat baru yang diperoleh dengan cara
menggabungkan beberapa pernyataan tunggal, dengan perangkai dengan perangkai logika seperti
dan, atau, jika….maka…., jika dan hanya jika, tidak.
Dua pernyataan tunggal atau lebih dapat digabungkan menjadi sebuah kalimat baru
yang merupakan pernyataan majemuk, sedangkan tiap pernyataan bagian dari pernyataan
majemuk disebut komponen-komponen pernyataan majemuk. Komponen - komponen dari
pernyataan majemuk itu tidak selamanya harus pernyataan tunggal, tetapi mungkin saja
pernyataan majemuk. Namun yang terpenting adalah bagaimana menggabungkan pernyataan -
pernyataan tunggal menjadi pernyataan majemuk.
Universitas Putra Batam2013 / 2014
Contoh pernyataan majemuk:
1. Bunga mawar berwarna merah dan bunga melati berwarna putih
2. Begadang itu boleh, jika ada guna nya
3. Suatu segitiga dikatakan segitiga sama sisi jika dan hanya jika ketiga sudutnya
sama
4. Air itu bersih, jika tidak terkontaminasi dengan zat lain
5. P : 5 adalah bilangan prima
Q : 8 adalah bilangan genap
Jadi, p dan q : 5 adalah bilangan prima dan 8 adalah bilangan genap
2. OPERASI / PERANGKAI LOGIKA
Untuk membentuk suatu Tabel Kebenaran yaitu, suatu tabel yang menunjukkan
secara sistematis satu demi satu nilai-nilai kebenaran sebagai hasil kombinasi dari
proposisi-proposisi yang sederhana. Maka , Perangkai Logika Matematika perlu
dipahami terlebih dahulu.
Perangkai - perangkai logika yang digunakan, Perangkai logika dalam bentuk simbol
digunakan untuk membuat bentuk-bentuk logika.
Tabel Perangkai Logika Matematika
Jenis penghubung Simbol Bentuk Prioritas
Negasi ( Not ) ~ Tidak ... 5
Konjungsi ( And ) ˄ ... Dan ... 4
Disjungsi ( Or ) ˅ ... Atau ... 3
Implikasi → Jika ... Maka ... 2
Biimplikasi ↔ ... Jika dan hanya Jika ... 1
3. TABEL KEBENARAN
A. Negasi
Negasi adalah menyangkal kebenaran suatu pernyataan, yang dilambangkan
dengan tanda ~ yang menggunakan penghubung Tidak.
Universitas Putra Batam2013 / 2014
Tabel Kebenaran Negasi :
Contoh Dari Negasi :
Tentukan negasi dari pernyataan-pernyataan berikut:
a) Hari ini Jakarta banjir
b) Kambing bisa terbang
c) Didi anak bodoh
d) Siswa-siswi SMANSA memakai baju batik pada hari Rabu
e) P adalah “Semarang ibu kota Jawa Tengah”
Penyelesain nya :
a) Hari ini Jakarta tidak banjir
b) Kambing tidak bisa terbang
c) Didi bukan anak bodoh
d) Siswa-siswi SMANSA tidak memakai baju batik pada hari Rabu
e) ~P adalah “Semarang Bukan ibukota Jawa Tengah”
B. Konjungsi
Konjungsi adalah sebuah pernyataan majemuk dengan dengan kata hubung ‘Dan’
Konjungsi dari pernyataan P dan Q di notasikan dengan “ P dan Q yang dilambangkan dengan ˄
Tabel Kebenaran Konjungsi :
P Q P ˄ Q
T T T
T F F
F T F
F F F
Q ~Q
T F
F T
Universitas Putra Batam2013 / 2014
Dari tabel di atas, tampak bahwa konjungsi selalu bernilai benar jika kedua pernyataan
bernilai benar. Yang lain nya jika ada yang bernilai Salah, maka hasil nya Salah.
Contoh Konjungsi dan penyelisain nya :
1. P : 33 = 40 Bernilai Salah
Q : 25 : 5 = 5 Bernilai benar
Jadi, P ˄ Q = 33 = 40 dan 25 : 5 = 5 Bernilai Salah
2. P : - 6 > - 10 ( T )
Q : 88 : 22 = 4 ( T )
Jadi, P ˄ Q = - 6 > - 10 dan 88 : 22 = 4 ( T )
C. Disjungsi
Disjungsi adalah pernyataan majemuk dengan kata hubung Atau. Disjungsi dari
pernyataan P dan Q dinotasikan dan di baca P atau Q.
Disjungsi ada dua macam :
1. Disjungsi Inklusif
Maksud nya yaitu sebuah pernyataan majemuk yang dilambangkan dengan ˅ yang
menggunakan kata penghubung ‘ Dan / Atau ‘
Misal kan P dan Q adalah pernyataan. Disjungsi dan / atau dari P dan Q adalah
pernyataan majemuk “ P dan / atau Q “.
Tabel Kebenaran Disjungsi Inklusif
P Q P ˅ Q
T T T
T F T
F T T
F F F
Universitas Putra Batam2013 / 2014
Contoh soal Dan penyelesain nya :
1. P : 4 + 8 = 12 ( T )
Q : 4 > 7 ( F )
Jadi P ˅ Q : 4 + 8 = 12 dan / atau 4 > 7 (T )
2. P : 7 adalah bilangan genap ( F )
Q : air adalah zat padat ( F )
Jadi, P ˅ Q : 7 adalah bilangan genap dan / atau 4 > 7 ( F )
2. Disjungsi Eksklusif
Misal kan P dan Q adalah pernyataan majemuk. Disjungsi atau dari P dan Q adalah
pernyataan majemuk “ P atau Q” yang dilambangkan dengan V .
Tabel kebenaran Disjungsi Eksklusif
Contoh soal dan penyelesain nya :
Bentuk lah Disjungsi dari :
1. P : 12 – 8 > 6 ( F )
Q : 8 + 12 = 20 ( T )
Jadi, P V Q = 12 – 8 > 6 atau 8 + 12 = 20 adalah ( T )
2. P : 4 adalah bilangan genap ( T )
Q : 7 adalah bilangan ganjil ( T )
Jadi, P V Q = 4 adalah bilangan genap atau 7 adalah bilangan ganjil ( F )
P Q P V Q
T T F
T F T
F T T
F F F
Universitas Putra Batam2013 / 2014
D. Implikasi
Implikasi disebut juga dengan kondisional adalah suatu pernyataan bersyarat satu arah.
Dua proposisi s dan t dikombinasikan dengan kata “jika…, maka…”. Proposisi “s” disebut
hipotesa (anteseden) dan proposisi “t” disebut konklusi (konsekuen). Implikasi bernilai salah jika
hipotesa benar dan konklusi salah. Notasi: s → t.
Tabel kebenaran Implikasi
Dari tabel disamping,tampak Dan selain nya selalu ( T )
Bahwa implikasi selalu
Bernilai Bernilai ( F ), jika
P = ( T ) dan Q = ( F ).
Contoh soal dan penyelesain nya :
1. s : Satuan untuk arus listrik adalah Ampere. ( T )
t : 1+1=2 ( T )
Sehingga s→t = jika satuan untuk arus listrik adalah Ampere maka 1+1=2 ( T )
2. P : Indonesia berada di benua Eropa ( F )
Q : 8 + 8 = 12 ( F )
Sehingga P → Q = Jika Indonesia berada di benua Eropa, maka 8 + 8 = 12 ( T ).
E. Biimplikasi ( Ekuivalensi )
Bi-implikasi merupakan pernyataan majemuk bersyarat dua arah. Dua proposisi P dan Q
dikombinasikan dengan kata “jika dan hanya jika” dan dilambangkan dengan ↔. Bi implikasi
bernilai benar jika kedua proposisinya bernilai sama, atau bi implikasi bernilai salah jika kedua
proposisinya bernilai berbeda.
P Q P → Q
T T T
T F F
F T T
F F T
Universitas Putra Batam2013 / 2014
Tabel Kebenaran Bi implikasi
Contoh dan penyelesaian :
1. P : 8 + 11 = 16( F )
Q : - 6 > - 7 = 2 ( T )
Jadi, P ↔ Q = 8 + 11 = 16 jika dan hanya jika - 6 > - 7 = 2 ( F )
2. P : 12 + 33 = 45 ( T )
Q : 20 : 2 = 10( T )
Jadi, P ↔ Q = 12 + 33 = 45 jika dan hanya jika 20 : 2 = 10 ( T ).
Menyusun tabel kebenaran untuk pernyataan majemuk :
Contoh soal dan penyelesaian nya :
1. Buat lah tabel kebenaran untuk pernyataan berikut :
a. – ( p˄−q )
p q −q p ˄−q – ( p˄−q )
T T F F T
T F T T F
F T F F T
F F T F T
b. (p → q) ↔ (-q → -p)
p q p → q -q -p -q → -p (p → q) ↔ (-q → -p)
T T T F F T T
T F F T F F T
F T T F T T T
F F T T T T T
P Q P ↔ Q
T T T
T F F
F T F
F F T
Universitas Putra Batam2013 / 2014
F. Tautologi
Tautologi adalah pernyataan majemuk yang selalu benar untuk semua kemungkinan
nilai kebenaran dari pernyataan-pernyataan komponennya. Untuk membuktikan apakah suatu
pernyataan Tautologi, maka ada dua cara yang digunakan. Cara pertama dengan menggunakan
tabel kebenaran, yaitu jika semua pilihan bernilai B (benar) maka disebut Tautologi, dan cara
kedua yaitu dengan melakukan penjabaran atau penurunan dengan menerapkan sebagian dari
hukum-hukum Ekuivalensi Logika.
Contoh soal Tautologi :
1. Buktikan : ¬(A ^ B ) v B adalah tautologi ?Bukti : Buat Tabel Kebenarannya seperti berikut :
A B A ˄ B −( A ˄ B ) – ( A ˄ B ) ˅ B
F F F T T
F T F T T
T F F T T
T T T F T
Jadi, pernyataan dari ¬(A ^ B ) v B disebut Tautologi, karena semua hasil nya benar.
2. Buktikan lah kalo pernyataan dari ( A ˄ B ) → (C ˅ (−B →−C ) ) adalah tautologi !Buktikan dengan tabel kebenaran :C ˅ (−B →−C ) ( A ˄ B ) → (C ˅ (−B →−C ) )
A B C −¿
B
−¿
C
A ˄ B −B →−C C ˅ (−B →−C ) ( A ˄ B ) → (C ˅ (−B →−C ) )
F F F T T F T T T
F F T T F F F T T
F T F F T F T T T
F T T F F F T T T
T F F T T F T T T
T F T T F F F T T
T T F F T T T T T
T T T F F T T T T
Jadi ekspresi logika diatas adalah tautology karena pada table kebenarannya semua
pasangannya menghasilkan nilai T.
Universitas Putra Batam2013 / 2014
G. Kontradiksi
Kontradiksi adalah kebalikan dari tautologi yaitu suatu bentuk pernyataan yang hanya
mempunyai contoh substansi yang salah, atau sebuah pernyataan majemuk yang salah dalam
segala hal tanpa memandang nilai kebenaran dari komponen-komponennya. Untuk membuktikan
apakah suatu pernyataan tersebut kontradiksi, maka ada dua cara yang digunakan. Cara pertama
dengan menggunakan tabel kebenaran, yaitu jika semua pilihan bernilai F atau salah maka
disebut kontradiksi, dan cara kedua yaitu dengan melakukan penjabaran atau penurunan dengan
menerapkan sebagian dari hukum-hukum Ekuivalensi Logika.
Contoh soal Kontradiksi :
1. Buktikan jika pernyataan dari ( ( A ˅ B )˄−A )˄−¿B adalah Kontradiksi !
A B −A −¿B ( A ˅ B ) ( ( A ˅ B )˄−A ) ( ( A ˅ B )˄−A )˄−¿B
F F T T F F F
F T T F T T F
T F F T T F F
T T F F T F F
Jadi, ekspresi logika di atas terjadi kontradiksi, karena semua hasil nya salah.
2. p ˄ ¬ p
P ¬ p p ˄ ¬ p
T F F
F T F
H. Kontingensi
Adalah Suatu ekspresi logika yang mempunyai nilai benar dan salah di dalam tabel
kebenarannya, tanpa mempedulikan nilai kebenaran dari proposisi-proposisi yang berada di
dalamnya.
Universitas Putra Batam2013 / 2014
Contoh soal Kontingensi :
1. ( ( A ˄ B )→C ) → A
A B C A ˄ B ( ( A ˄ B )→C ) ( ( A ˄ B )→C ) → A
F T F F T F
F T T F T F
T F F F T T
T F T F T T
2. P → (Q ˄ P )
P Q Q ˄ P P → (Q ˄ P )
T T T T
T F F F
F T F T
F F F T
Dari kedua tabel di atas, Nilai-nilai kebenaran pada nilai kebenaran sebagai hasil akhir
di tabel kebenaran tidak harus selalu berurutan antara F dan T, yang penting ada T dan ada F,
maka disebut dengan Kontingensi.
I. Konvers, Kontraposisi Dan Invers
Jika p → q adalah sebuah implikasi maka terdapat beberapa pernyataan yang
berhubungan dengan p → q yaitu:
1.Pernyataan q → p disebut konvers dari pernyataan p → q
2.Pernyataan (¬ q) → (¬p) disebut kontraposisi atau kontrapositif dari p → q
3.Pernyataan (¬ p) → (¬q) disebut invers dari p → q
Contoh soal :
Tulislah konvers, kontraposisi dan invers dari implikasi-implikasi berikut:
Universitas Putra Batam2013 / 2014
1. X=3 → x adalah bilangan bulat ganjil
konvers : x adalah bilangan bulat ganjil → x=3
kontraposisi : x bukan bilangan bulat ganjil → x≠3
invers : x≠3 → x bukan bilangan bulat ganjil
2. Jika hari hujan maka saya basah kuyup
Konvers : Jika saya basah kuyup maka hari hujan
kontraposisi : Jika saya tidak basah kuyup maka hari tidak hujan
invers : Jika hari tidak hujan maka saya tidak basah kuyup
J. Implikasi Logis
Sebuah Tautologi yang memuat pernyataan Implikasi disebut Implikasi Logis.
Jika p → q tautologi, maka p → q selalu benar untuk semua nilai p dan q yang mungkin
dan dilambangkan dengan p ⟹ q dan di baca “ p implikasi logis q “. Artinya p → q digunakan
apabila pernyataan p selalu mengimplikasi pernyataan q tanpa memperhatikan nilai dari variabel
– variabel penyusun nya.
Contoh soal :
Tunjukkan bahwa pernyataan-pernyataan majemuk berikut adalah implikasi logis :
1. (p ˄ q) → p
p q p ˄q ( p˄q ) →p
T T T T
T F F F
F T F T
F F F T
2. ¬ p →(p → q)
p q −p p → q – p → ( p→ q )
T T F F T
T F T T F
F T F F T
F F T F T
Universitas Putra Batam2013 / 2014
K. Ekuivalensi Logis
Dua atau lebih pernyataan majemuk yang mempunyai nilai kebenaran sama disebut ekuivalensi logis dengan notasi S1 ⟺ S2 dibaca dengan S1 ekuivalen logis dengan S2
Contoh soal :
1. ¬((¬ p))↔ p
p ¬q ¬(¬ p ) ¬(¬ p )→p T F T TT F T TF T F TF T F T
2. ¬ (p ˄ q) ↔ (¬p)˅(¬ q)
P Q P ˄Q ¬ (p ˄ q) → P → Q (¬p)˅(¬ q) ¬ (p ˄ q) ↔ (¬p)˅(¬ q)T T T F F F F TT F F T F T T TF T F T T F T TF F F T T T T T
L. Hukum Logika
Universitas Putra Batam2013 / 2014
Jadi, kita tidak hanya bisa membuktikan sebuah pernyataan majemuk dengan
menggunakan tabel kebenaran, tetapi juga bisa di buktikan dengan hukum logika diatas.
BAB II
HIMPUNAN
Himpunan adalah sekumpulan objek diskrit yang memiliki sifat tertentu dan memiliki
objek yang berbeda. Objek ini selanjutnya dinamakan yaitu anggota atau elemen dari himpunan
tersebut. Istilah kelompok, kumpulan, maupun gugus dalam matematika disebut dengan istilah
himpunan. Konsep tentang himpunan pertama kali dikemukakan oleh seorang matematikawan
berkebangsaan Jerman bernama Georg Cantor (1845-1918).
Notasi
1. Himpunan biasanya dinyatakan dengan huruf besar A,B,C,H,K dan sebagainya. Untuk
menyatakan suatu himpunan digunakan simbol “{}”, sementara itu untuk melambangkan
anggota himpunan biasanya menggunakan huruf kecil a,b,c,x,y dan sebagainya.
2. Untuk menyatakan anggota suatu himpunan digunakan lambang “∈” di baca anggota
sedangkan untuk menyatakan bukan anggota suatu himpunan digunakan lambang " " di∉
baca bukan anggota.
Contoh Kelompok/kumpulan yang merupakan suatu himpunan:
Kelompok hewan berkaki empat.
Yang merupakan anggota, misalnya : Gajah, sapi, kuda, kambing
Yang merupakan bukan anggota, misalnya : ayam, bebek, itik.
Contoh Kelompok/kumpulan yang bukan merupakan suatu himpunan:
Kumpulan siswa di kelasmu yang berbadan tinggi.
Pengertian tinggi tidak jelas harus berapa cm batasannya.
Universitas Putra Batam2013 / 2014
Mengapa disebut begitu, karena batasan contoh di atas tidak jelas. Di dalam
Matematika kumpulan tidak dapat disebut himpunan jika batasannya tidak jelas.
1. TEKNIK PENYAJIAN HIMPUNAN
A. Enumerasi
Enumerasi artinya menuliskan semua elemen himpunan yang bersangkutan di antara
dua buah tanda kurung kurawal . Biasanya suatu himpunan di beri nama dengan menggunakan
huruf kapital maupun dengan simbol-simbol lainnya.
Contoh :
1. Himpunan empat bilangan asli pertama: A = {1, 2, 3, 4}
2. C = {a, {a}, {{a}} }
B. Notasi Pembentuk Himpunan
Notasi = {x| syarat yang harus dipenuhi oleh x}
Contoh :
1. Jika B himpunan bilangan bulat positif yang kurang dari 8 dinyatakan ke dalam
bentuk notasi=
B = {x | x ∈ p, x < 8}
B = {1,2,3,4,5,6,7}
C. Simbol Simbol Baku
P = himpunan bilangan bulat positif = { 1, 2, 3, ... }
N = himpunan bilangan alami (natural) = { 1, 2, ... }
Z = himpunan bilangan bulat = { ..., -2, -1, 0, 1, 2, ... }
Universitas Putra Batam2013 / 2014
Q = himpunan bilangan rasional
R = himpunan bilangan riil
C = himpunan bilangan kompleks
Himpunan yang universal : semesta, disimbolkan dengan U
Contoh : Misalkan U = {1, 2, 3, 4, 5} dan A adalah himpunan bagian dari U, dengan A={1, 3, 5}
D. Diagram Venn
Dalam diagram venn, himpunan semesta (U) digambarkan sebagai suatu segi empat
sedangkan himpunan lainnya digambarkan sebagai lingkaran di dalam segi empat tersebut.
Contoh :
1. Misalkan U = {1, 2, …, 7, 8}, A = {1, 2, 3, 5} dan B = {2, 5, 6, 8}
Diagram Venn =
2. KARDINALITAS
Definisi kardinalitas : sebuah himpunan dikatakan berhingga (finite set) jika terdapat n,
elemen berbeda (distinct) yang dalam hal ini n adalah bilangan bulat tak negatif. Sebaliknya
himpunan tersebut dinamakan tak berhingga (infinite set). Misalkan A merupakan himpunan
berhingga, maka jumlah elemen berbeda di dalam A, disebut sebagai kardinal dari himpunan A.
Notasi :n (A )atau|A|
Contoh soal :
U A B
1 7
3 4
2 8
5 6
Universitas Putra Batam2013 / 2014
1. B = { x | x merupakan bilangan prima yang lebih kecil dari 20 },
atau B = {2, 3, 5, 7, 11, 13, 17, 19} maka |B| = 8
2. T = {kucing, a, Amir, 10, paku}, maka |T| = 5
3. JENIS – JENIS HIMPUNAN
A. Himpunan Kosong ( Himpunan Hampa )
Himpunan kosong adalah himpunan yang tidak memiliki anggota sama sekali atau
himpunan dengan kardinal 0. Himpunan kosong dilambangkan dengan tanda { } atau Ø.
Contoh soal dan penyelesaian nya :
1. A = {x | x adalah akar persamaan kuadrat x2 + 1 = 0 }, n(A) = 0
2. B = {bilangan genap antara 2 dan 4}, ditulis B = {} = {0}
B. Himpunan Bagian ( Subset )
Definisi : Himpunan A dikatakan himpunan bagian (subset) dari himpunan B jika dan
hanya jika setiap elemen A merupakan elemen dari B. Dalam hal ini,B dikatakan superset dari A.
Notasi : A⊂B
Penulisan A ⊂ B berbeda dengan A ⊆ B
Jika kita menekankan bahwa A adalah himpunan bagian dari B tetapi A≠ B, maka kita
tulis A ⊂ B
Jika kita menekankan bahwa A adalah himpunan bagian B, tapi A = B, maka tulis dengan
A ⊆ B
Untuk sembarang himpunan A berlaku hal - hal sebagai berikut :
A adalah himpunan bagian dari A itu sendiri ( A⊆ A )
Himpunan kosong adalah himpunan bagian dari A({}⊆ A )
Jika A ⊆ B dan B ⊆C maka A ⊆ C
Universitas Putra Batam2013 / 2014
Contoh soal dan penyelesaian nya :
1. { 1, 2, 3} ⊆ {1, 2, 3, 4, 5}
2. {1, 2, 3} ⊆ {1, 2, 3}
C. Himpunan Yang Sama
Definisi : Himpunan A dikatakan sama dengan himpunan B jika dan hanya jika
keduanya mempunyai elemen yang sama. Dengan kata lain, A sama dengan B jika A adalah
himpunan bagian dari B dan B adalah himpunan bagian dari A. Jika tidak demikian, maka kita
katakan A tidak sama dengan B.
Notasi : A=B⟷ A⊆B dan B⊆A
Untuk tiga buah himpunan, A, B, dan C berlaku aksioma berikut :
A. A = A, B = B, dan C = C
B. jika A = B, maka B = A
C. jika A = B dan B = C, maka A = C
Contoh soal dan penyelesaian nya :
1. Jika A = { 0, 1 } dan B = { x | x (x – 1) = 0 }, maka A = B
2. Jika A = { 3, 5, 8, 5 } dan B = {5, 3, 8 }, maka A = B
D. Himpunan yang Ekuivalen
Himpunan A dikatakan ekivalen dengan himpunan B jika dan hanya jika kardinal dari
kedua himpunan tersebut sama.
Notasi : A∼B jika dan hanya jika|A|=¿B∨¿
Contoh soal :
1. Jika A= {b,c,d} dan B={d,c,b}, Maka A∼B karena |A|=¿B∨¿ = 3
2. Jika A = {3,3,2,4,2,3} dan B = {2,2,4,5,3,3}
Maka A∼B karena |A|=¿B∨¿ = 6
Universitas Putra Batam2013 / 2014
E. Himpunan Saling Lepas
Definisi : Dua himpunan A dan B dikatakan saling lepas (disjoint) jika keduanya tidak
memiliki elemen yang sama. Notasi : A / ∕ B
Contoh :
Jika A = { x | x * P, x < 8 } dan
B = { 10, 20, 30, ... }, maka A // B
F. Himpunan Kuasa
Himpunan kuasa (power set) dari himpunan A adalah suatu himpunan yang elemennya
merupakan semua himpunan bagian dari A, termasuk himpunan kosong dan himpunan A sendiri.
Notasi : P ( A )atau2a
Contoh :
Jika A = { 1, 2 }, maka P(A) = { Æ, { 1 }, { 2 }, { 1, 2 }}
4. OPERASI TERHADAP HIMPUNAN
A. Irisan (Intersection)
Irisan (intersection) dari himpunan A dan B adalah sebuah himpunan yang setiap
elemennya merupakan elemen dari himpunan A dan himpunan B.
Notasi : A ∩B={x∨x∈ A dan x∈B
Contoh :
S = {a,b,c,d} T = {f,b,d,g}à SÇT = {b,d} = TÇS
B. Gabungan ( Union )
U
AB
U
A A ∩B
A ∩B B
Universitas Putra Batam2013 / 2014
Gabungan (union) dari himpunan A dan B adalah himpunan yang setiap anggotanya
merupakan anggota himpunan A atau himpunan B.
Notasi : A∪B={x∨x∈ A atau x∈B
Contoh :
1. Jika A = { 2, 5, 8 } dan
B = { 7, 5, 22 }
Maka A ∪ B = { 2, 5, 7, 8, 22 }
2. A ∪ ∅ = A
C. Komplemen
Komplemen dari suatu himpunan A terhadap suatu himpunan semesta U adalah suatu
himpunan yang elemennya merupakan elemen U yang bukan elemen A.
Notasi : A={x∨x∈U , x A
Misalkan U = { 1, 2, 3, ..., 9 },
jika A = {1, 3, 7, 9}, maka A = {2, 4, 6, 8}
jika A = { x | x/2 Î P, x < 9 }, maka A = { 1, 3, 5, 7, 9 }
D. Selisih ( Difference)
Notasi : A∨−B={x|x∈ A danx B }=A ∩ B
Contoh :
1. Jika A = { 1, 2, 3, ..., 10 } dan
U
A B
U
A
U
A B
Universitas Putra Batam2013 / 2014
B = { 2, 4, 6, 8, 10 }
maka A – B = { 1, 3, 5, 7, 9 } dan B – A = Æ
2. {1, 3, 5} – {1, 2, 3} = {5}, tetapi {1, 2, 3} – {1, 3, 5} = {2}
E. Beda Setangkup ( Symmetric Difference)
Beda setangkup dari himpunan A dan B adalah suatu himpunan yang elemennya ada
pada himpunan A atau B tetapi tidak pada keduanya.
Notasi : A⊕B=(A∪B )−¿
Contoh :
1. Jika A = { 2, 4, 6 } dan B = { 2, 3, 5 }, maka A Å B = { 3, 4, 5, 6 }
2. Jika A = { 2,4,6 } dan B ={ 2,3,5 }, maka A Å B = { 3,4,5,6 }
F. Perkalian Kartesian (Cartesian Product)
Perkalian kartesian dari himpunan A dan B adalah himpunan yang elemennya semua
pasangan berurutan (ordered pairs) yang dibentuk dari komponen pertama dari himpunan
A dan komponen kedua dari himpunan B.
Notasi : A × B={ (a , b )∨a∈ A danb∈B }
Contoh :
1. Misalkan C = { 1, 2, 3 }, dan D = { a, b }, maka
C × D = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }
2. Misalkan A = B = himpunan semua bilangan riil, maka
A x B = himpunan semua titik di bidang datar
Catatan :
1. Jika A dan B merupakan himpunan berhingga, maka: |A x B| = |A| . |B|
Universitas Putra Batam2013 / 2014
2. Pasangan berurutan (a, b) berbeda dengan (b, a), dengan kata lain (a, b) ≠ (b, a)
3. Perkalian kartesian tidak komutatif, yaitu A x B ≠ B x A dengan syarat A atau B tidak
kosong.
G. Perampatan Operasi Himpunan
Operasi himpunan dapat dilakukan terhadap 2 atau lebih himpunan. Dalam hal ini kita
melakukan perampatan (generalization) himpunan dengan menggunakan dasar perampatan
yang ada pada operasi aritmatika biasa.
¿¿Misalkan A = {1, 2}, B = {a, b}, dan C = {, }, maka
A B C = {(1, a, ), (1, a, ), (1, b, ), (1, b, ), (2, a, ), (2, a, ), (2, b, ), (2, b, ) }
H. Hukum Aljabar Himpunan
Hukum Aljabar Himpunan
1 Hukum Identitas
(i) A ∪∅ = A
(ii) A ∩∪ = A
2 Hukum Null / Dominasi
(i) A ∩∅=∅
(ii) A ∩∪ = U
3
Hukum Komplemen
(i) A U A = U
(ii) A ∩ A = ∅
4 Hukum Idempotent
(i) A U A = A
(ii) A ∩ A = A
5 Hukum Involusi
(i) ( A ) = A
6 Hukum Absorpsi ( Penyerapan )
(i) A ∪ (A ∩ B ) = A
(ii) A ∩ ( A U B ) = A
7 Hukum Komutatif
(i) A ∪ B = B ∪ A
(ii) A ∩ B = B ∩ A
8 Hukum Asosiatif
(i) A ∪ (B ∪ C) = (A ∪ B) U C
(ii) A ∩ ( B ∩ C) = (A ∩ B) ∩ C
9 Hukum Distributif
(i) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
(ii) A ∩ (B ∪ C) = (A ∩ B) ∩ (A ∪ C)
10 Hukum De Morgan(i) A ∩ B = A ∪ B(ii) A∪B = A ∩ B
I. Prinsip Inklusi dan Eklusi
Untuk dua himpunan A dan B :
Universitas Putra Batam2013 / 2014
A B = A + B – A Ç B
A Å B = A +B – 2A Ç B
Contoh :
1. Berapa banyaknya bilangan bulat antara 1 dan 100 yang habis dibagi 3 atau 5 ?
Penyelesaian:
A = himpunan bilangan bulat yang habis dibagi 3,
B = himpunan bilangan bulat yang habis dibagi 5,
A ∩ B = himpunan bilangan bulat yang habis dibagi 3 dan 5 (yaitu himpunan bilangan
bulat yang habis dibagi oleh KPK – Kelipatan Persekutuan
Terkecil – dari 3 dan 5, yaitu 15)
Yang ditanyakan adalah A ∪ B ?
A = 100/3 = 33,
B = 100/5 = 20,
A Ç B = 100/15 = 6
A B = A + B – A Ç B = 33 + 20 – 6 = 47
Jadi, ada 47 buah bilangan yang habis dibagi 3 atau 5.
5. HIMPUNAN CRISP DAN HIMPUNAN FUZZY
A. Himpunan Crisp
Pada himpunan tegas (crisp), nilai keanggotaan suatu item x dalam suatu himpunan A,
yang sering ditulis dengan µ A[x], memiliki 2 kemungkinan, yaitu:
1. Satu (1), yang berarti bahwa suatu item menjadi anggota dalam suatu himpunan, atau
2. Nol (0), yang berarti bahwa suatu item tidak menjadi anggota dalam suatu himpunan
Contoh, Jika di ketahui :
Universitas Putra Batam2013 / 2014
S = {1, 2, 3, 4, 5, 6} adalah semesta pembicaraan
A = {1, 2, 3} B = {3, 4, 5}
Bisa dikatakan bahwa :
1. Nilai keanggotaan 2 pada himpunan A, µA [2]=1, karena 2 A.∈
2. Nilai keanggotaan 3 pada himpunan A, µA [3]=1, karena 3 A.∈
3. Nilai keanggotaan 4 pada himpunan A, µA [4]=0, karena 4 A.∈
4. Nilai keanggotaan 2 pada himpunan B, µB [2]=0, karena 2 B.∈
5. Nilai keanggotaan 3 pada himpunan B, µB [3]=1, karena 3 B.∈
B. Himpunan Fuzzy
Pada gambar di atas, dapat dilihat bahwa :
1. Seseorang yang berumur 40 tahun, termasuk dalam himpunan MUDA dengan
µMUDA[40]=0,25; namun dia juga termasuk dalam himpunan PAROBAYA dengan
µPAROBAYA[40]=0,5.
2. Seseorang yang berumur 50 tahun, termasuk dalam himpunan MUDA dengan
µTUA[50]=0,25; namun dia juga termasuk dalam himpunan PAROBAYA dengan
µPAROBAYA [50]=0,5.
Universitas Putra Batam2013 / 2014
Kalau pada himpunan crisp, nilai keanggotaan hanya ada 2 kemungkinan, yaitu 0 atau 1,
pada himpunan fuzzy nilai keanggotaan terletak pada rentang 0 sampai 1. Apabila x memiliki
nilai keanggotaan fuzzy µA[x]=0 berarti x tidak menjadi anggota himpunan A, demikian pula
apabila x memiliki nilai keanggotaan fuzzy µA[x]=1 berarti x menjadi anggota penuh pada
himpunan A.
Terkadang kemiripan antara keanggotaan fuzzy dengan probabilitas menimbulkan
kerancuan. Keduanya memiliki nilai pada interval [0,1], namun interpretasi nilainya sangat
berbeda antara kedua kasus tersebut. Keanggotaan fuzzy memberikan suatu ukuran terhadap
pendapat atau keputusan, sedangkan probabilitas mengindikasikan proporsi terhadap keseringan
suatu hasil bernilai benar dalam jangka panjang. Misalnya, jika nilai keanggotaan suatu
himpunan fuzzy MUDA adalah 0,9; maka tidak perlu dipermasalahkan berapa seringnya nilai itu
diulang secara individual untuk mengharapkan suatu hasil yang hampir pasti muda. Di lain
pihak, nilai probabilitas 0,9 muda berarti 10% dari himpunan tersebut diharapkan tidak muda.
Himpunan fuzzy memiliki 2 atribut, yaitu :
1. Linguistik, yaitu penamaan suatu grup yang mewakili suatu keadaan atau kondisi
tertentu dengan menggunakan bahasa alami, seperti: MUDA, PAROBAYA, TUA.
2. Numeris, yaitu suatu nilai (angka) yang menunjukkan ukuran dari suatu variabel
seperti: 40, 25, 50, dsb.
6. MANFAAT BELAJAR HIMPUNAN DALAM KEHIDUPAN SEHARI-SEHARI
Membahas mengenai manfaat himpunan dalam kehidupan sehari-hari, mengingatkan
kita yang mungkin sebagai guru atau orang tua saat ada pertanyaan yang terlontar dari anak
dengan wajah polosnya. “Apa manfaat himpunan dalam kehidupan kita sehari-hari?” Mereka
belum tahu betapa pentingnya himpunan yang merupakan dasar dari segala ilmu Matematika.
Dengan mempelajari himpunan, diharapkan kemampuan logika akan semakin terasah dan akan
memacu kita agar kita mampu berpikir secara logis, karena dalam hidup, logika memiliki peran
penting karena logika berkaitan dengan akal pikir. Banyak kegunaan logika antara lain:
Membantu setiap orang yang mempelajari logika untuk berpikir secara rasional,
kritis, lurus, tetap, tertib, metodis dan koheren.
Meningkatkan kemampuan berpikir secara abstrak, cermat, dan objektif.
Universitas Putra Batam2013 / 2014
Menambah kecerdasan dan meningkatkan kemampuan berpikir secara tajam dan
mandiri.
Memaksa dan mendorong orang untuk berpikir sendiri dengan menggunakan asas-
asas sistematis.
Meningkatkan cinta akan kebenaran dan menghindari kesalahan-kesalahan berpikir,
kekeliruan serta kesesatan.
Mampu melakukan analisis terhadap suatu kejadian.
BAB III
MATRIKS
Pengertian dari Matriks adalah susunan bilangan – bilangan dalam baris dan kolom
yang berbentuk persegi panjang.
Baris sebuah matriks adalah susunan bilangan – bilangan yang mendatar dalam matriks.
Kolom sebuah matriks adalah susunan bilangan – bilangan yang tegak dalam matriks.
Masing-masing bilangan dalam matriks disebut entri atau elemen.
Ordo (ukuran) matriks adalah jumlah baris kali jumlah kolom.
Contoh matriks :
1. A3x2 = [5 55 53 5] Baris ke 2
Kolom ke 1
A adalah lambang huruf untuk matriks
A3x2 berarti matriks berordo 3 x 3 mempunyai 3 baris dan 3 kolom
1. JENIS – JENIS MATRIKS
A. Matrik Baris
Matriks baris adalah matriks yang hanya terdiri dari satu baris.
A1x2 = [2 5 ]
B. Matriks Kolom
Universitas Putra Batam2013 / 2014
B2x1 = [23]C. Matriks Persegi ( Bujur Sangkar )
Matriks persegi adalah matriks yang banyak baris dan kolom nya sama
A2x2 = [4 96 7]
D. Matriks Diagonal
Adalah matriks persegi dengan setiap elemen yang bukan elemen – elemen diagonal
utama nya adalah 0 ( nol ), sedangkan elemen pada diagonal utama nya tidak selalu
semua nya 0 (nol).
A3x3 ¿ [3 0 00 8 00 0 8] B4x4 = [2 0 0 0
0 0 0 00 0 5 00 0 0 5
] Merah adalah Diagonal Utama
E. Matriks Identitas
Adalah matriks persegi dengan semua elemen pada diagonal utama nya ada 1 (satu)
dan elemen lain nya adalah nol semuanya.
A3x3 ¿ [1 0 00 1 00 0 1] B4x4 = [1 0 0 0
0 1 0 00 0 1 00 0 0 1
]F. Matriks Segi Tiga Atas
Matriks segitiga atas adalah matriks yang elemen-elemen di atas diagonal bernilai
nol.
A3x3 ¿ [1 0 04 3 09 6 7] B4x4 = [2 0 0 0
3 4 0 06 8 6 08 5 7 3
]G. Matriks Segi Tiga Bawah
Matriks segitiga atas adalah matriks yang elemen-elemen di bawah diagonal bernilai nol.
A3x3 ¿ [1 7 70 3 30 0 7] B4x4 = [2 4 4 1
0 4 8 30 0 6 60 0 0 3
]
Universitas Putra Batam2013 / 2014
H. Matriks Transpose
Matriks transpose adalah matriks yang diperoleh dengan mempertukarkan baris-baris
dan kolom-kolom
A3x3 = [2 5 14 3 6] AT = [2 4
5 31 6]
I. Matriks Setangkup ( Simetri )
Matriks Simetri adalah suatu matriks bujur sangkar yang unsur pada baris ke-i kolom
ke-j sama dengan unsur pada baris ke-j kolom ke-i sehingga aij = aji .
B4x4 = [2 0 4 10 1 0 34 0 6 61 3 6 3
] BT 4x4 = [2 0 4 10 1 0 34 0 6 61 3 6 3
]J. Matriks 0 / 1 ( zero – one )
Matriks 0/1 adalah matriks yang setiap elemennya hanya bernilai 0 atau 1. Matriks ini
banyak digunakan untuk menunjukkan relasi.
B4x4 = [1 0 1 11 1 0 01 0 0 11 0 1 1
]K. Matrik Skalar
Adalah matriks diagonal yang mana semua komponen diagonal utama nya sama, jika
komponen diagonal utama nya 1, matriks tersebut matriks identitas
M = [4 0 00 4 00 0 4 ]
2. OPERASI ARITMATIKA MATRIKS
A. Penjumlahan Dua Buah Matriks (A+B)
Jika A dan B adalah matriks yang berordo sama, maka jumlah matriks A dan B
(ditulis A+B) adalah matriks baru yang diperoleh dari menjumlahkan setiap unsur A
dengan unsur yang seletak
A = [2 45 31 6] B = [3 7
1 47 9] A + B = [5 11
6 78 15 ]
Universitas Putra Batam2013 / 2014
B. Pengurangan Dua Buah Matriks ( A-B )
A = [2 45 31 6] B = [3 7
1 47 9] A - B = [−1 −3
4 −1−6 −3]
Sifat-sifat penjumlahan dan pengurangan matriks
Komutatif : A+B=B+A
Assosiatif : (A+B)+C=A+(B+C)
Terdapat sebuah matriks identitas penjumlahan yaitu dimana A+0=0+A=A
Setiap matriks A mempunyai lawan (negatif) yaitu –A dimana A+(-A) = 0
C. Perkalian Dua Buah Matriks
A =[1 32 4] B = [2 3 2
6 4 6] A x B =
[ (1 x2 )+(3 x6) (1 x3 )+(3 x 4) (1 x2 )+(3 x6)(2x 2 )+(4 x 6) (2 x 3 )+(4 x 4) (2x 2 )+(4 x 6)]
= [20 15 2028 22 28]
Sifat – sifat Perkalian Matriks
1. Perkalian matriks tidak komutatif, yaitu AB ≠ BA
2. Hukum asosiatif, berlaku pada operasi matriks, ( AB ) C = A ( BC )
3. Hukum distributif kiri pada matriks : ( B + C ) A = BA + CA
4. Hukum distributif kanan, berlaku pada matriks : A (B + C) = AB + AC
5. Perkalian matriks dengan identitas, tidak mengubah matriks : AI = IA = A
6. Perpangkatan matriks didefinisikan sebagai berikut : A0 = I dan Ak =
AAAA …. Ak kali
7. A adalah matriks orthogonal jika AAT = AT A = I
Universitas Putra Batam2013 / 2014
BAB IV
RELASI
Suatu relasi (biner) F dari himpunan A ke himpunan B adalah suatu perkawanan
elemen-elemen di A dengan elemen-elemen di B. didefinisikan sebagai berikut : Suatu fungsi f
dari himpunan A ke himpunan B adalah suatu relasi yang memasangkan setiap elemen dari A
secara tunggal, dengan elemen pada B.
Notasi A × B= {(a , b )∨a∈ A dan b∈B }
Relasi antara himpunan A dan B disebut sebagai relasi biner.
Relasi biner antara himpunan A dan B adalah himpunan bagian dari A x B
R⊆(A × B)
a R b adalah notasi untuk (a, b) ⊆ R, yang artinya a dihubungankan dengan b oleh R
a R b adalah notasi untuk (a, b) ∉ R,yang artinya a tidak dihubungkan oleh b oleh relasi
R
Himpunan A disebut daerah asal (domain) dari R, dan himpunan B disebut daerah hasil
(range) dari R
Contoh :
1. Misalkan P = {2, 3, 4} dan Q = {2, 4, 8, 9, 15}. Jika kita definisikan relasi R dari P ke Q
dengan (p, q) ∈ R jika p habis membagi q, maka kita peroleh
R = {(2, 2), (2, 4), (4, 4), (2, 8), (4, 8), (3, 9), (3, 15) }
2. Misalkan R adalah relasi pada A = {2, 3, 4, 8, 9} yang di definisikan oleh (x, y) Î R jika x
adalah faktof prima dari y, maka
Universitas Putra Batam2013 / 2014
R = {(2, 2), (2, 4), (2, 8), (3, 3), (3, 9)}
Relasi pada sebuah himpunan adalah relasi yang khusus
Relasi pada himpunan A adalah relasi dari A × A
Relasi pada himpunan A adalah himpunan bagian dari A × A
1. REPRESENTASI RELASI
A. Representasi Relasi Dengan Diagram Panah
Contoh no. 1 Contoh no. 2
Relasi R Relasi R
B. Representasi Relasi dengan Tabel
2
3
4
2
4
8
9
15
2
3
4
8
9
2
3
4
8
9
Contoh No.
2
A A
2 2
2 4
2 8
3 3
3 3
Contoh No.
1
P Q
2 2
2 4
4 4
3 8
4 8
3 9
3 15
Universitas Putra Batam2013 / 2014
C. Representasi Relasi dengan Matriks
Misalkan R adalah relasi dari A = {a1 , a2 ..., am} dan B = {b1, b2, …, bn}
Relasi R dapat disajikan dengan matriks M = [m jj ]
b1 b2 bn
M =
a1
a2
⋮am[m11 m12 ⋯ m1n
m21 m22 ⋯ m2n
⋮ ⋮ ⋮ ⋮mm1 mm2 ⋯ mmn
]Yang dalam hal ini,
mij={1 , (ai , b j )∈ R
0 , (ai , b j )∉ R
Contoh No. 1
MR = [1 1 1 0 00 0 0 1 10 1 1 0 0]
D. Representasi Relasi dengan Graf Berarah
Relasi pada sebuah himpunan dapat direpresentasikan secara grafis dengan graf berarah
(directed graph atau digraph)
Graf berarah tidak didefinisikan untuk merepresentasikan relasi dari suatu himpunan ke
himpunan lain.
Tiap elemen himpunan dinyatakan dengan sebuah titik (disebut juga simpul atau vertex),
dan tiap pasangan terurut dinyatakan dengan busur (arc)
Jika (a, b) R, maka sebuah busur dibuat dari simpul a ke simpul b. Simpul a disebut
simpul asal (initial vertex) dan simpul b disebut simpul tujuan (terminal vertex).
Pasangan terurut (a, a) dinyatakan dengan busur dari simpul a ke simpul a sendiri. Busur
semacam itu disebut gelang atau kalang (loop).
Universitas Putra Batam2013 / 2014
Contoh :
Misalkan R = {(a, a), (a, b), (b, a), (b, c), (b, d), (c, a), (c, d), (d, b)} adalah relasi pada
himpunan {a, b, c, d}.
R direpresentasikan dengan graf berarah sbb :
a b
c d
2. SIFAT – SIFAT RELASI
A. Refleksif ( Raflexive )
Relasi R pada himpunan A disebut refleksif jika (a, a) ∈ R untuk setiap a ∈ A.
Relasi R pada himpunan A tidak refleksif jika ada a ∈ A sedemikian sehingga (a, a) ∉ R.
Contoh :
1. Misalkan A = {1, 2, 3, 4}, dan relasi R di bawah ini didefinisikan pada himpunan A,
maka
(a) Relasi R = {(1, 1), (1, 3), (2, 1), (2, 2), (3, 3), (4, 2), (4, 3),
(4, 4) } bersifat refleksif karena terdapat elemen relasi yang berbentuk (a, a), yaitu
(1, 1), (2, 2), (3, 3), dan (4, 4).
(b) Relasi R = {(1, 1), (2, 2), (2, 3), (4, 2), (4, 3), (4, 4) } tidak bersifat refleksif karena
(3, 3) ∉ R.
Relasi yang bersifat refleksif mempunyai matriks yang elemen diagonal utamanya semua
bernilai 1, atau mii = 1, untuk i = 1, 2, …, n,
Universitas Putra Batam2013 / 2014
[1 ¿ ¿1 ¿ ¿¿
¿1¿¿1¿] Graf berarah dari relasi yang bersifat refleksif dicirikan adanya gelang pada setiap
simpulnya.
B. Menghantar (Transitive)
Relasi R pada himpunan A disebut menghantar jika (a, b) ∈ R dan (b, c) ∈ R, maka (a, c)
∈ R, untuk a, b, c ∈ A.
Contoh :
Misalkan A = {1, 2, 3, 4}, dan relasi R di bawah ini didefinisikan pada himpunan A, maka
a. R = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3) } bersifat menghantar. Lihat tabel berikut:
Pasangan berbentuk
(a, b) (b, c) (a, c)
(3, 2) (2, 1) (3, 1)
(4, 2) (2, 1) (4, 1)
(4, 3) (3, 1) (4, 1)
(4, 3) (3, 2) (4, 2)
b. R = {(1, 1), (2, 3), (2, 4), (4, 2) } tidak manghantar karena (2, 4) dan (4, 2) ∈ R, tetapi (2,
2) ∉ R, begitu juga (4, 2) dan (2, 3) ∈ R, tetapi (4, 3) ∉ R.
c. Relasi R = {(1, 1), (2, 2), (3, 3), (4, 4) } jelas menghantar
d. Relasi R = {(1, 2), (3, 4)} menghantar karena tidak ada
(a, b) ∈ R dan (b, c) ∈ R sedemikian sehingga (a, c) ∈ R.
Relasi yang hanya berisi satu elemen seperti R = {(4, 5)} selalu menghantar.
C. Setangkup ( Symmetric ) / Cermin
Universitas Putra Batam2013 / 2014
Relasi R pada himpunan A disebut setangkup jika (a, b) Î R, maka (b, a) Î R untuk a, b
Î A.
Contoh :
Misalkan A = {1, 2, 3, 4}, dan relasi R di bawah ini didefinisikan pada himpunan A, maka
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 4), (4, 2), (4. 4)} bersifat setangkup karena (1, 2) Î R1 dan
(2,1) Î R1 ; (2,4) Î R1 dan (4,2) Î R1
1 2 3 4
R1 =
1234
[1 1 0 01 1 0 10 0 0 00 1 0 1
]R2 = {(1, 1), (2, 3), (2, 4), (4, 2) tidak setangkup karena (2,3) Î R2 tetapi (3,2) ∉ R2
1 2 3 4
R2 =
1234
[1 0 0 00 0 1 10 0 0 00 1 0 0
]D. Tolak Setangkup ( Antisymmetric / Anti Cermin
Relasi R pada himpunan A disebut tolak setangkup apabila a, b Î R, maka (b,a) Î R,
maka a = untuk semua a, b Î A
Contoh :
Misalkan A = {1, 2, 3, 4}, dan relasi R di bawah ini didefinisikan pada himpunan A, maka
R1 = {(1, 1), (1, 2), (2, 3), (2, 2)} bersifat tolak setangkup karena (1, 1) Î R1 dan (2,2) Î R1 dan 2
= 2
1 2 3 4
Universitas Putra Batam2013 / 2014
R1 =
1234
[1 1 0 00 1 1 00 0 0 00 0 0 0
] = [1 1 0 00 1 1 00 0 0 00 0 0 0
]R2 = {(1, 1), (2, 4), (3, 3), (4, 2)} bersifat tidak tolak setangkup karena (2,4) Î R2 dan (4,2) ∉ R2
dan 4 = 2
1 2 3 4
R2 =
1234
[1 0 0 00 0 0 10 0 1 00 1 0 0
] = [1 0 0 00 0 0 10 0 1 00 1 0 0
]E. Relasi yang Mengandung Beberapa Sifat Sekaligus
Contoh :
a b
d c
1.R tidak refleksif karena pada simpul a tidak terdapat loop
2. R tidak setangkup sebab (b,a) , (b,c) (d,c) ∈ R ,tetapi (a, b) ,(c, b) (c, d) ∉R
3.R tidak tolak setangkup karena (a, c) . (a, d) ∈ R dan (c, a) , (d,a) ∉R
4.R menghantar ?
R = {(b,a) ,( b,c) , (d,c) , (c, a) , (a, c) , (a, d) , (d,a) , (d,d) ,( c, c) , (b,b)}
R = tidak menghantar karena (b,a) ∈ R ; (a, c) ∈ R ; (b,c) ∉R
R = tidak menghantar karena ( c,a) ∈ R ; (a,d) ∈ R; R (c,d) ∉R
3. KLOSUR RELASI
A. Refleksif
Misalkan R adalah relasi pada himpunan A , klosur refleksif dari R adalahR∪△ , yang dalam hal ini△={ (a , a )∨a∈ A }
Universitas Putra Batam2013 / 2014
A = {1,2,3} dan relasi pada himpunan A adalah R,
R = {(1, 1), (1, 3), (2, 3), (3, 2)}
△ = {(1, 1), (2, 2), (3, 3)}
sehingga klosur refleksif dari R adalah
R∪△ = {(1, 1), (1, 3), (2, 3), (3, 2)} ∪ {(1, 1), (2, 2), (3, 3)}
= {(1, 1), (2, 2), (3, 3), (1,3), (2,3), (3,2)}
B. Setangkup
Misalkan R adalah sebuahrelasi pada himpunan A , klosur setangkup dari R adalahR∪R−1 yangdalah halini R−1={(b ,a )∨a ,b∈ A }
A = {1,2,3} dan relasi pada himpunan A adalah R,
R = {(1, 2), (1, 3), (2, 1), (3, 2),(3,3)}
R−1= {(2, 1), (3,1), (1, 2), (2, 3),(3,3)}
Sehingga klosur setangkup dari R adalah
R ∪R−1 = {(1, 2), (1, 3), (2, 1), (3, 2),(3,3)} ∪ {(2, 1), (3,1), (1, 2), (2, 3),(3,3)}
= {(1, 2), (1, 3), (2, 1), (3, 2),(3,3),(2, 1), (3,1), (1, 2), (2, 3),(3,3)}
= {(1, 2), (1, 3), (2, 1), (3, 2),(3,3),(3,1), (2,3)}
C. Menghantar
Klosur menghantar dari relasi R adalahR¿
¿n=1¿∞ Rn¿misalkan A adalahhimpunan dengann elemendan R adalahrelasi pada himpunan A ¿ jika terdapat lintasan dengan panjang minimal1 di dalam R dari a keb ,¿maka lintasan semacamitu panjang nya tidak melebihin¿
Contoh :
Misalkan himpunan A = {1,2,3}
1 2 3
Universitas Putra Batam2013 / 2014
MR = 123
[1 0 10 1 01 1 0 ] = [1 0 1
0 1 01 1 0 ]
1 2 3 1 2 3 1 2 3
MRoR = MR . MR = 123
[1 0 10 1 01 1 0 ] .
123[
1 0 10 1 01 1 0] =
123[
1 1 10 1 01 1 1 ] = [1 1 1
0 1 01 1 1]
1 2 3 1 2 3 1 2 3
MRoRoR = M R[3 ] = MR . MR . MR = MR M R
[2 ] = 123
[1 0 10 1 01 1 0 ] .
123
[1 1 10 1 01 1 1] =
123
[1 1 10 1 01 1 1]= [1 1 1
0 1 01 1 1]
Sehingga klosur menghantar = M R ¿ = MR V MRoR V MRoRoR
= [1 0 10 1 01 1 0 ] V [1 1 1
0 1 01 1 1] V [1 1 1
0 1 01 1 1] = [1 1 1
0 1 01 1 1]
4. RELASI INVERSI
Misalkan R adalah relasi dari himpunan A ke himpunan B. Invers dari relasi R,
dilambangkan dengan R–1, adalah relasi dari B ke A yang didefinisikan oleh
R−1={(b , a)∨(a ,b)∈ R }
Contoh :
1.Misalkan P = {2, 3, 4} dan Q = {2, 4, 8, 9, 15}. Jika kita definisikan relasi R dari P ke Q
dengan
(p,q) Î R jika p habis membagi q, maka kita peroleh :
R = {(2, 2), (2, 4), (4, 4), (2, 8), (4, 8), (3, 9), (3, 15) }
Universitas Putra Batam2013 / 2014
MR = [1 1 1 0 00 0 0 1 10 1 1 0 0]
R−1 adalah invers dari relasi R yaitu relasi Q ke P dengan (p,q) Î R-1 jika q adalah kelipatan
p
R−1 = {(2, 2), (4, 2), (4, 4), (8, 2), (8, 4), (9, 3), (15, 3) }
M R−1 = M RT = [
1 0 01 0 11 0 10 1 00 1 0
]5.MENGKOMBINASIKAN RELASI
Karena relasi biner merupakan himpunan pasangan terurut, maka operasi himpunan
seperti irisan, gabungan, selisih, dan beda setangkup antara dua relasi atau lebih juga berlaku.
Jika R1 dan R2 masing – masing adalah relasi dari himpunan A ke himpunan B, maka
R1 Ç R2, R1 R2, R1 – R2, dan R1 Å R2 juga adalah relasi dari A ke B.
Contoh :
1.Misalkan A = {a, b, c} dan B = {a, b, c, d}
Relasi R1 = {(a, a), (b, b), (c, c)}
Relasi R2 = {(a, a), (a, b), (a, c), (a, d)}
R1 ∩ R1 = {(a, a)}
R1 ∪ R2 = {(a, a), (b, b), (c, c), (a, b), (a, c), (a, d)}
R1 - R2 = {(b, b), (c, c)}
R2 - R1 = {(a, b), (a, c), (a, d)}
R1 Å R2 = {(b, b), (c, c), (a, b), (a, c), (a, d)}
6. MENGKOMBINASI KAN RELASI DENGAN MATRIKS
Contoh :
Universitas Putra Batam2013 / 2014
1. Misalkan :
K = {a,b,c} dan L {p,q,r,s} ; A dan B adalah relasi dari K ke L
A = { (a , p ) (b , p ) ,(c , r )}
B = { (a , p ) (a ,q ) ,(a , r )(a , s )}
Kita dapat mengkombinasi kan kedua relasi tersebut dengan irisan.
Irisan dilambangkan dengan M A∩B = MA ˄ MB
p q r s p q r s
MA = abc [1 0 0 0
0 1 0 00 0 1 0] = [1 0 0 0
0 1 0 00 0 1 0] MB =
abc [1 1 1 1
0 0 0 00 0 0 0] = [1 1 1 1
0 0 0 00 0 0 0]
M A∪ B = [1 0 0 00 1 0 00 0 1 0] ∪ [1 1 1 1
0 0 0 00 0 0 0] = [1 1 1 1
0 1 0 00 0 1 0]
2. Misal kan himpunan A = {a,b,c}
R1 dan R2 menyatakan relasi dari himpunan A, sebagai berikut :
R1 = [1 0 01 0 11 1 0] dan R2 = [0 1 0
0 1 11 0 0 ]
Maka matriks gabungan dan irisan adalah sebagi berikut :
M R 1∪ R2
= [1 1 01 1 11 1 0] dan M R 1∩ R
2
= [0 0 00 0 11 0 0 ]
7. KOMPOSISI RELASI
Misalkan R adalah relasi dari himpunan A ke himpunan B, dan S adalah relasi dari
himpunan B ke himpunan C. Komposisi R dan S, dinotasikan dengan S R, adalah relasi dari A
ke C yang didefinisikan oleh :
Universitas Putra Batam2013 / 2014
S ο R = {(a, c) | a ∈ A, c ∈ C, dan untuk beberapa b ∈ B, (a, b) ∈ R dan (b, c) ∈ S }
Contoh :
R = {(1, 2), (1, 6), (2, 4), (3, 4), (3, 6), (3, 8)} adalah relasi dari himpunan {2, 4, 6, 8} ke
himpunan {s, t, u}, maka komposisi relasi R dan S adalah :
S ο R = {(1, u), (1, t), (2, s), (2, t), (3, s), (3, t), (3, u) }
Komposisi relasi R dan S lebih jelas jika di peragakan dengan diagram panah :
R S
R ο S
A. Komposisi Relasi – Matriks
Jika relasi R1 dan R2 masing - masing dinyatakan dengan matriks M R 1 dan M R 2
, maka
matriks yang menyatakan komposisi dari kedua relasi, relasi tersebut adalah M R 1 ο R2 = M R 1
. M R 2
operator ".|" sama seperti pada perkalian matriks biasa, tetapi dengan mengganti tanda kali
dengan " ˄ " dan mengganti tanda tambah dengan " ˅ ".
Contoh :
1. Misalkan himpunan A = {a,b,c} dan himpunan B = {d,e,f} dan himpunan C = { g,h,i}
2
4
6
8
s
t
u
1
2
3
1
2
3
s
t
u
Universitas Putra Batam2013 / 2014
Relasi antara himpunan A dengan B di nyatakan dengan R1
Relasi antara himpunan B dengan C dinyatakan dengan R2
d e f g h i
M R 1 =
abc [1 0 1
1 1 00 0 0 ] = [1 0 1
1 1 00 0 0 ] dan = M R 2
= def [
0 1 00 0 11 0 1] = [0 1 0
0 0 11 0 1 ]
d e f g h i g h i
M R 1ο R2 = M R 1 . M R 2
= abc [1 0 1
1 1 00 0 0 ] .
def [
0 1 00 0 11 0 1] =
abc [1 1 1
0 1 10 0 0 ] = [1 1 1
0 1 10 0 0 ]
2.
R S
2 4 6 8 s t u
MR = 123
[1 0 1 00 1 0 00 1 1 1] = [1 0 1 0
0 1 0 00 1 1 1] Ms =
2468
[0 0 11 1 00 1 00 0 1
]
2
4
6
8
s
t
u
1
2
3
Universitas Putra Batam2013 / 2014
MRos = MR . Ms = [1 0 1 00 1 0 00 1 1 1] . [0 0 1
1 1 00 1 00 0 1
] = [0 1 11 1 01 1 1]
s t u
MRos = MR . Ms = 123
[0 1 10 1 00 1 1]
B. Komposisi Relasi – Matriks – Komposisi dengan Dirinya Sendiri
Simbol Rn digunakan untuk mendefinisikan komposisi relasi dengan diri nya sendiri
sebanyak n kali.
Contoh :
1. Himpunan A = {1,2,3}
Relasi antara himpunan A dengan A / relasi antara A dinyatakan dengan dirinya sendiri,
dengan R = {(1, 1), (1, 3), (2, 2), (3,1), (3, 2)}
Sehingga R ο R = {(1, 1), (1, 3), (1,2), (2,2), (3, 1), (3,3), (3, 2)}
1 2 3
MR = 123
[1 0 10 1 01 1 0 ] = [1 0 1
0 1 01 1 0 ]
1 2 3 1 2 3 1 2 3
M R 2 = MR . MR = 123
[1 0 10 1 01 1 0 ] .
123[
1 0 10 1 01 1 0] =
123[
1 1 10 1 01 1 1 ] = [1 1 1
0 1 01 1 1]
8. RELASI N – ARY
Universitas Putra Batam2013 / 2014
Relasi biner hanya menghubungkan antara dua buah himpunan.
Relasi yang lebih umum menghubungkan lebih dari dua buah himpunan. Relasi tersebut
dinamakan relasi n-ary (baca: ener).
Jika n = 2, maka relasinya dinamakan relasi biner (bi = 2). Relasi n-ary mempunyai
terapan penting di dalam basisdata.
Misalkan A1, A2, …, An adalah himpunan. Relasi n-ary R pada himpunan-himpunan
tersebut adalah himpunan bagian dari A1 x A2 x … x An , atau dengan notasi
R⊆A1 × A2 ×…× An. Himpunan A1, A2, …, An disebut daerah asal relasi dan n disebut
derajat.
Contoh :
NIM = {13598011, 13598014, 13598015, 13598019, 13598021, 13598025}
Nama = {Amir, Santi, Irwan, Ahmad, Cecep, Hamdan}
MatKul = {Matematika Diskrit, Algoritma, Struktur Data, Arsitektur Komputer}
Nilai = {A, B, C, D, E}
Relasi MHS terdiri dari 5-tupel (NIM, Nama, MatKul, Nilai) :
MHS ⊆ NIM x Nama x MatKul x Nilai
Satu contoh relasi yang bernama MHS adalah :
MHS = {(13598011, Amir, Matematika Diskrit, A), (13598011, Amir, Arsitektur Komputer,
B), (13598014, Santi, Arsitektur Komputer, D), (13598015, Irwan, Algoritma, C),
(13598015, Irwan, Struktur Data C), (13598015, Irwan, Arsitektur Komputer, B),
(13598019, Ahmad, Algoritma, E), (13598021, Cecep, Algoritma, A), (13598021,
Cecep, Arsitektur Komputer, B), (13598025, Hamdan, Matematika Diskrit, B),
(13598025, Hamdan, Algoritma, A, B), (13598025, Hamdan, Struktur Data, C),
(13598025, Hamdan, Ars. Komputer, B)}
Relasi MHS di atas juga dapat ditulis dalam bentuk Tabel :
NIM Nama Matkul Nilai
Universitas Putra Batam2013 / 2014
13598011
13598011
13598014
13598015
13598015
13598015
13598019
13598021
13598021
13598025
13598025
13598025
13598025
Amir
Amir
Santi
Irwan
Irwan
Irwan
Ahmad
Cecep
Cecep
Hamdan
Hamdan
Hamdan
Hamdan
Matematika Diskrit
Arsitektur Komputer
Algoritma
Algoritma
Struktur Data
Arsitektur Komputer
Algoritma
Algoritma
Arsitektur Komputer
Matematika Diskrit
Algoritma
Struktur Data
Arsitektur Komputer
A
B
D
C
C
B
E
B
B
B
A
C
B
1. Basis Data
Basisdata (database) adalah kumpulan tabel.
Salah satu model basisdata adalah model basisdata relasional (relational database).
Model basisdata ini didasarkan pada konsep relasi n-ary.
Pada basisdata relasional, satu tabel menyatakan satu relasi. Setiap kolom pada tabel
disebut atribut. Daerah asal dari atribut adalah himpunan tempat semua anggota atribut
tersebut berada.
Setiap tabel pada basisdata diimplementasikan secara fisik sebagai sebuah file.
Satu baris data pada tabel menyatakan sebuah record, dan setiap atribut menyatakan
sebuah field.
Secara fisik basisdata adalah kumpulan file, sedangkan file adalah kumpulan record,
setiap record terdiri atas sejumlah field.
Atribut khusus pada tabel yang mengidentifikasikan secara unik elemen relasi disebut
kunci (key).
2. Query
Universitas Putra Batam2013 / 2014
Query adalah operasi yang dilakukan terhadap basisdata dilakukan dengan perintah
pertanyaan. Query terhadap basis data relasional dapat dinyatakan secara abstrak dengan operasi
pada relasi n-ary.
Contoh query :
1. “tampilkan semua mahasiswa yang mengambil mata kuliah Matematika Diskrit”
2. “tampilkan daftar nilai mahasiswa dengan NIM = 13598015”
3. “tampilkan daftar mahasiswa yang terdiri atas NIM dan mata kuliah yang diambil”
Ada beberapa operasi yang dapat digunakan, diantaranya adalah seleksi, proyeksi, dan
join. Biar lebih jelas, mari kita simak penjelasan dibawah ini.
A. Seleksi
Operasi seleksi adalah memilih baris tertentu dari suatu tabel yang memenuhi persyaratan
tertentu.
Contoh :
Misalkan untuk relasi MHS kita ingin menampilkan daftar mahasiswa yang mengambil
mata kuliah Matematik Diskrit.
NIM Nama Matkul Nilai
13598011
13598011
13598014
13598015
13598015
13598015
13598019
13598021
13598021
13598025
13598025
Amir
Amir
Santi
Irwan
Irwan
Irwan
Ahmad
Cecep
Cecep
Hamdan
Hamdan
Matematika Diskrit
Arsitektur Komputer
Algoritma
Algoritma
Struktur Data
Arsitektur Komputer
Algoritma
Algoritma
Arsitektur Komputer
Matematika Diskrit
Algoritma
A
B
D
C
C
B
E
B
B
B
A
Universitas Putra Batam2013 / 2014
13598025
13598025
Hamdan
Hamdan
Struktur Data
Arsitektur Komputer
C
B
Operasi seleksinya adalah : Matkul = ”Matematika Diskrit” (MHS)
Hasil nya adalah :
NIM Nama Mata Kuliah Nilai
13598011 Amir Matematika Diskrit A
13598025 Hamdan Matematika Diskrit B
B. Proyeksi
Operasi proyeksi adalah memilih kolom tertentu dari suatu tabel. Jika ada beberapa
baris yang sama nilainya, maka hanya diambil satu kali.
Operator :
Contoh :
NIM. Nama ( MHS)NIM Nama Matkul Nilai
13598011
13598011
13598014
13598015
13598015
13598015
13598019
13598021
13598021
13598025
13598025
13598025
13598025
Amir
Amir
Santi
Irwan
Irwan
Irwan
Ahmad
Cecep
Cecep
Hamdan
Hamdan
Hamdan
Hamdan
Matematika Diskrit
Arsitektur Komputer
Algoritma
Algoritma
Struktur Data
Arsitektur Komputer
Algoritma
Algoritma
Arsitektur Komputer
Matematika Diskrit
Algoritma
Struktur Data
Arsitektur Komputer
A
B
D
C
C
B
E
B
B
B
A
C
B
NIM Nama
13598011 Amir
13598014 Santi
13598015 Irwan
13598019 Ahmad
13598021 Cecep
13598025 Hamdan
Universitas Putra Batam2013 / 2014
C. Join
Operasi join adalah menggabungkan dua buah tabel menjadi satu bila kedua tabel
mempunyai atribut yang sama.
Operator :
Contoh :
Misalkan relasi MHS 1 dinyatakan dengan tabel 1 dan relasi MHS 2 dinyatakan dengan
tabel 2.
Tabel 1 Tabel 2
Operasi Join nya adalah :
NIM, NAMA ( MHS 1, MHS 2 )
NIM Nama JK
13598001 Hananto L
13598002 Guntur L
13598004 Heidi W
13598006 Harman L
13598007 Karim L
NIM Nama Mata Kul Nilai
13598001 Hananto Algoritma A
13598001 Hananto Basis data B
13598004 Heidi Kalkulus B
13598006 Harman Teori bahasa C
13598006 Harman Agama A
13598009 Junaidi Statistik B
13598010 Farizka Otomata C
Universitas Putra Batam2013 / 2014
NIM Nama JK Mata Kul Nilai
13598001 Hananto L Algoritma A
13598001 Hananto L Basis data B
13598004 Heidi W Kalkulus B
13598006 Harman L Teori bahasa C
13598006 Harman L Agama A
BAB V
FUNGSI
Fungsi adalah relasi yang khusus :
1. Tiap elemen di dalam himpunan A harus digunakan oleh prosedur atau kaidah yang
mendefinisikan f
2. Frasa “dihubungkan dengan tepat satu elemen di dalam B” berarti bahwa jika (a, b) ∈ f
dan (a, c) ∈ f, maka b = c
3. Jika f adalah fungsi dari A ke B kita menuliskan f : A → B , yang artinya f memetakan
A ke B
4. A disebut daerah asal (domain) dari f dan B disebut daerah hasil (codomain) dari f
5. Kita menuliskan f(a) = b jika elemen a di dalam A dihubungkan dengan elemen b di dalam B
Universitas Putra Batam2013 / 2014
6. Jika f(a) = b, maka b dinamakan bayangan (image) dari a dan a dinamakan pra-bayangan (pre-image) dari b.
7. Himpunan yang berisi semua nilai pemetaan f disebut jelajah (range) dari f. Perhatikan bahwa jelajah dari f adalah himpunan bagian (mungkin proper subset) dari B
A B
f
Notasi :
f : A → B
8. Relasi dari himpunan A ke B disebut fungsi /pemetaan atau transformasi jika dan hanya
jika tiap unsur dalam himpunan A berpasangan tepat hanya dengan sebuah unsur dalam
himpunan B
A B
Y : x → y = f (x)
Y = f(x) disebut rumus atau aturan untuk fungsi f
X disebut peubah ( variabel ) bebas
Y disebut peubah ( variabel ) tak bebas
Y : x → y = f (x)
Supaya nilai F(x) adalah real maka harus ditentukan daerah asal
Contoh :
1. f (x) = 4
x+1 , maka x ≠ -1, jadi Df = {x|x ∈ R dan x ≠ -1}
2. g(x) = 1
x2−4 x+3 =
1( x−1 )(x−3)
a b
x Y=f(x)
Universitas Putra Batam2013 / 2014
sehingga g(x) bernilai real, maka (x-1)(x-3) ≠ 0
sehingga x ≠ 1 dan x ≠ 3 jadi Dg = {x|x ∈ R dan x ≠ 1 ; x ≠ 3}
3. h(x) = 5
√x2−5 x+6 ; supaya h(x) bernilai real, maka x2 – 5x + 6 > 0
(x – 2)(x – 3) > 0 sehingga x < 2 atau x > 3, jadi Dh = {x|x < 2 atau x > 3 ; x ∈ R}
Fungsi dapat dispesifikasikan dalam berbagai bentuk, diantaranya :
1. Himpunan pasangan terurut, Seperti pada relasi.
2. Formula pengisian nilai (assignment).
Contoh: f(x) = 2x + 10, f(x) = x2, dan f(x) = 1/x.
3. Kata-kata
Contoh: “f adalah fungsi yang memetakan jumlah bit 1 di dalam suatu string biner”.
4. Kode program (source code)Contoh : Fungsi menghitung |x|
function abs (x : integer) : integer;begin
if x < 0 then
abs:=-x
else
abs:=x;
end;
1. JENIS – JENIS FUNGSI
A. Fungsi Konstan / Fungsi Tetap
Fungsi konstan mempunyai ciri khusus yaitu untuk semua unsur himpunan A berkaitan
hanya dengan sebuah unsur dari himpunan B
B
1
2
3
4
a
Universitas Putra Batam2013 / 2014
A
f : x → k, k = tetapan
B. Fungsi Identitas
Fungsi identitas mempunyai ciri khusus yaitu semua unsur dalam himpunan A berkaitan
dengan dirinya sendiri.
A B
I : x → x, I (x) = x
C. Fungsi Genap dan Fungsi Ganjil
Fungsi Genap
Jika fungsi f memenuhi f (−x)=f (x ) untuk setiap x di dalam daerah asalnya, maka f
disebut fungsi genap.
y
f(x)
y = f(x)
-x x x
Catatan : grafik fungsi genap simetri terhadap sumbu – y
Contoh :
f (x) = x2 +5
f(-x) = (-x)2 + 5 = x2 +5 = f(x) maka f(x) = x2 + 5 adalah fungsi genap
1
2
3
4
1
2
3
4
Universitas Putra Batam2013 / 2014
Fungsi Ganjil
Jika fungsi f memenuhi f (−x)=−f (x) untuk setiap x di dalam daerah asalnya, maka f
disebut fungsi ganjil. y
y = f(x)
f(x) x
x = -f(x)
-x
Cacatan : Grafik Fungsi ganjil simetri terhadap titik asal.
Contoh :
f (x) = x3 -x
f (-x) = (-x)3 – (-x) = - x3 + x = - (x3 – x ) = - f(x) maka f(x) = x3- x adalah fungsi
ganjil.
f (x) = x3 – 1
f (-x) = (-x)3 – 1 = - x3– 1
oleh karena f(-x) ≠ + f(x) dan f (-x) ≠ - f (x) maka f (x) = x3– 1 bukan fungsi genap
dan bukan fungsi ganjil.
Grafik fungsi genap selalu simetri atau setangkup terhadap sumbu Y
Grafik fungsi ganjil selalu simetri atau setangkup terhadap sumbu X
D. Fungsi Linear
Bentuk umum : y = f(x) = ax + b, a dan b konstanta
a = kemiringan garis dan tidak sama dengan 0
b = perpotongan garis dengan sumbu-y
Grafik : y = f(x) = ax + b memotong sumbu X di titik x = - ba
dan memotong sumbu Y di titik b
y
y = ax + b
Universitas Putra Batam2013 / 2014
b
x
E. Fungsi Kuadrat
f : x → y=f ( x )=a x2+bx+c
Grafik :
y y y
y = x y = x2 y = x3
x x x
0 0 0
2. FUNGSI BERDASARKAN DAERAH HASIL
a. Fungsi Surjektif
Fungsi f : A → B disebut fungsi surjektif – onto atau fungsi kepada jika dan hanya jika
daerah hasil fungsi f sama dengan himpunan B atau Rf = B
Fungsi f : A → B disebut fungsi surjektif – into atau fungsi kedalam jika dan hanya jika
daerah hasil fungsi f merupakan bagian dari himpunan B atau f : A ⊂B
B
A A B
Fungsi surjektif onto Fungsi surjektif into
b. Fungsi Injektif / Fungsi Satu – Satu
1
2
3
4
a
b
a
b
c
d
e
1
2
3
4
Universitas Putra Batam2013 / 2014
Fungsi f : A → B disebut sebagai fungsi injektif atau fungsi satu-satu jika dan hanya jika
untuk setiap a1, a2 ∈ A dan a1 ≠ a2 berlaku f (a1) ≠ f (a2)
A
B
c. Bijektif
Fungsi f : A → B disebut sebagai fungsi bijektif jika dan hanya jika fungsi f sekaligus
merupakan fungsi surjektif dan fungsi bijektif.
A B
Aljabar Fungsi
Jika diketahui fungsi f(x) dan g(x) dan n adalah bilangan rasional
a
b
c
d
e
f
1
2
3
4
1
2
3
4
b
c
d
e
Universitas Putra Batam2013 / 2014
Jumlah fungsi f ( x ) dan g ( x ) ditulis ( f +g ) (x ) = f ( x ) + g ( x )
Selisih fungsi f ( x ) dan g ( x ) ditulis ( f−g ) ( x ) = f ( x ) - g ( x )
Perkalian fungsi f ( x ) dan g ( x ) ditulis ( f × g ) (x ) = f ( x ) × g ( x )
Pembagian fungsi f ( x ) dan g ( x ) ditulis ( fg ) ( x ) = f ( x )g ( x )
Perpangkatan fungsi f ( x ) dengan bilangan n ditulis f n ( x ) = [ f ( x ) ]n
Contoh soal :
1. f3 (x) - [ f ( x ) ]3 – [ x−1x ]
3
Domain fungsi f3(x) adalah Df 3 - {x|x 0 dan x∈ R}
3. FUNGSI KOMPOSISI
Karna fungsi merupakan bentuk khusus dari relasi, kita juga dapat melakukan
komposisi dari dua buah fungsi. Misal kan G adalah fungsi dari himpunan A ke himpunan B, dan
f adalah fungsi dari himpunan B ke himpunan C. Komposisi f dan g, dinotasikan dengan fο g,
adalah fungsi dari A ke C yang didifinisikan oleh : (f οg) (a) = f (g(a))
Contoh soal :
(f οg) (a)
A B C
g(a) f (g(a))
Komposisi dua buah fungsi
a g(a) f (g(a))
Universitas Putra Batam2013 / 2014
1. Diberikan fungsi f ( x ) = x – 1 dan g ( x ) = x2 + 1. Tentukan f οg dan g ο f
Penyelesaian :
( f οg) (x) = f(g ( x ) ) = f (x2 + 1) = x2 + 1 – 1 = x2
(g ο f ) (x) = g( f (x ) )= g (x – 1) = (x – 1)2 + 1 = x2 – 2x + 2
Ini memperlihatkan bahwa komposisi dua fungsi, f dan g, tidak komitatif, kecuali jika f = g
2. f(x) = 4x – 1 dan g(x) = x2 + 2 tentukan ( f οg) (x), (g ο f ) (x), ( f ο f ) (x), (g ο g) (x)
penyelesaian :
( f ο g) (x) = f(g ( x ) ) = 4 (x2 + 2) – 1 = 4 x2 + 8 – 1 = 4 x2 + 7
(g ο f ) (x) = g( f (x ) )= (4x – 1)2 + 2 = 16 x2 – 8x + 1+2 = 16 x2 – 8x + 3
( f ο f ) (x) = 4(4x – 1) – 1 = 16x – 4 – 1 = 16x – 5
(g ο g) (x) = (x2 + 2)2 + 2 = x4 + 4x2 + 4 +2 = x4 + 4x2 + 6
Sifat Fungsi Komposisi
( f οg ) (x )≠ (g ο f ) ( x )( f ο (g οh ) ) ( x )=( ( f ο g )ο h ) ( x )( f ο I ) ( x )=( I ο f ) ( x )=f ( x )
Contoh soal :
1. f(x)= 2x , g(x) x2 - 4x , h(x)= x2 + 1
a. (f ο g)(x) = f (g ( x ) ) = 2(x2 - 4x) = 2x2 - 8x
b. (g ο f ) ( x ) = g( f (x ) ) = (2x)2 - 4(2 x )= 4x2 – 8x
c. ( f ο (gοh ) ) (x) = ( fοg (h ( x ) ) ) g(h ( x )) = (x2 + )2 – 4(x2 + 1) = x4 + 2 x2 +1 - 4x2 – 4 = x4 - 2x2 – 3
( fοg (h ( x ) ) ) = 2(x4 - 2x2 – 3) = 2x4 -4x2 – 6
( f ο (gοh ) ) (x) = 2x4 -4x2 – 6
d. I( x ) = x
(f ο I)(x) = 2x
2. Menentukan fungsi jika fungsi komposisi dan fungsi lain diketahui
a. (f ο g)(x) = 3x + 1 dan g(x) = x – 2 b. (f ο g)(x) = x2 – 6x + 3 dan g(x) = x – 1
Universitas Putra Batam2013 / 2014
Tentukan g (x) = ... ? Tentukan f (x) = ... ?
(f ο g)(x) = 3x + 1 (f ο g)(x) = x2 – 6x + 3
f (g ( x ) ) = 3x + 1 f (g ( x ) ) = x2 – 6x + 3
g ( x )−¿2 = 3x + 1 f (x – 1) = x2 – 6x + 3
g ( x ) = 3x + 1 + 2 f (x – 1) = (x – 1)2 + 2x – 1 – 6x + 3
g(x) = 3x + 3 f (x – 1) = (x – 1)2 – 4x + 2
f (x – 1) = (x – 1)2 – 4(x – 1) - 4 + 2
f (x – 1) = (x – 1)2 – 4(x – 1) – 2
f(x)= x2 – 4x – 2
4. FUNGSI INFERS
Jika fungsi f : A → B dinyatakan dengan pasangan terurut, f : {(a ,b )∨a ϵ A danb ϵ B }, maka invers dari fungsi f adalah f - 1 : B → A dinyatakan dengan pasangan terurut. f :
{(b ,a )∨b ϵ B dan aϵ A }.
f
f – 1=invers
A B
Cara mendapatkan fungsi infers :
Ubah persamaan y = f(x) dalam bentuk x sebagai fungsi y
Bentuk x sebagai fungsi y pada langkah pertama diberi nama f – 1(y)
Ganti y pada f – 1(y) untuk mendapatkan f – 1(x) yang merupakan fungsi invers f(x)
Contoh soal :
Tentukan fungsi invers nya !
1. Fungsi f(x) = x2 + 1
f(x) = y = x2 + 1
y – 1 = x2
y=f(x)
y=f(x)
x
x
Universitas Putra Batam2013 / 2014
x = ±√ y−1
f – 1(y) = ±√ y−1 ⟹ f −1 ( x ) = ±√x−1
2. Fungsi f(x) = x2 – 4x + 2, carilah fungsi invers nya !
f(x) = y = x2 – 4x+ 2
y – 2 = x2 – 4x
y – 2 = (x – 2)2 – 4 ( selesaikan dengan kuadrat sempurna )
y – 6 = (x – 2)2
(x – 2) = ±√ y−6
X = (±√ y−6 ) + 2
X = f – 1(y) = ±√ y−6 + 2
⟹ f −1 ( x ) = ±√x−6 + 2
Fungsi Invers dari Fungsi Komposisi
Contoh soal :
1. misalkan fungsi f(x) = x + 2, g(x) = 4 - 2x
carilah rumus (f ο g)(x) dan (f ο g)- 1 (x) !
Penyelesaian :
a. fungsi komposisi
(f ο g)(x) = f (g ( x ) ) = g(x) + 2 = 4 – 2x + 2 = -2x + 6
b. fungsi invers komposisi
f(x) = y = x + 2 g(x)= y = 4 – 2x
x = y – 2 x = − y+4
2
f−1 (x ) = x – 2 g−1 ( x ) = −x+4
2
Universitas Putra Batam2013 / 2014
(f ο g)- 1 (x) = (g-1 ο f−1)(x) = [g−1 ( f−1 ( x )) ]
= −f −1 ( x )+4
2
= −( x−2 )+4
2
= −x+6
2
c. fungsi invers komposisi (g ο f)- 1 (x)
(g ο f)- 1 (x) = (f-1 ο g−1)(x) = [ f−1 (g−1 ( x )) ]= (g−1 ( x ) ) - 2
= −x+4
2 – 2
= −x2
BAB VI
ALGORITMA DAN BILANGAN BULAT
1. ALGORITMA
Algoritma adalah urutan langkah-langkah logis penyelesaian masalah yang disusun
secara sistematis.
A. Notasi Untuk Algoritma
Universitas Putra Batam2013 / 2014
1. Deskripsi
Algoritma dapat dituliskan dalam berbagai notasi, misalnya notasi kalimat deskriptif.
Kalimat nya dijelaskan secara deskripsi pada setiap langkah – langkah dalam bahasa
sehari –hari secara gemblang. Setiap langkah di awali dengan kata kerja seperti ‘kerja’,
‘hidung’ dan sebagai nya. Sedangkan pernyataan bersyarat dinyatakan dengan
‘jika ...maka...’ .
Contoh nya, kita akan menuliskan algoritma untuk mencari elemen terbesar dari sebuah
himpunan yang beranggotakan n buah bilangan bulat. Bilangan bulat itu dinyatakan
sebagai a1, a2, ... an. Elemen terbesar akan disimpan di dalam peubah ( variabel ) yang
bernama maks.
Algoritma Cari Elemen Terbesar :
1. Asumsikan a1 sebagai elemen terbesar sementara. Simpan a1 ke dalam maks.
2. Bandingkan maks dengan elemen a2, jika a2 > maks, maka nilai maks deganti dengan a2
3. Ulangi langkah ke 2 untuk elemen-elemen berikutnya (a3, a4, a5,…an)
4. Berhenti jika tidak ada lagi elemen yang dibandingkan . Dalam hal ini maks berisi nilai
elemen terbesar.
2. Notasi bahasa komputer ( bahasa pemrograman )
Misalkan bahasa pascal atau bahasa C. Dalam bahsa pascal, algoritma mencari
elemen terbesar ditulis seperti dibawah ini :
Program carielementerbesar;
Uses wincrt;
Var
i : integer;
Nmaks : 1000 (const);
Begin
Maks : = a(1);
For i :=2 to n do
If a(i) > maks then
Maks := a(i);
End.
Universitas Putra Batam2013 / 2014
3. Notasi Pseudo-code
Karena sintaks yang rumit para ilmuan komputer lebih menyukai menuliskan
algoritma dalam notasi yang lebih praktis, yaitu notasi Pseudo-code.
Pseudo-code artinya semu atau tidak sebenarnya. Dengan menggunakan notasi
Pseudo-code , algoritma mencari elemen terbesar di tuliskan sbb:
Procedure CariElemenTerbesar (input a1,a2,...an : ineger, output maks : integer)
Deklarasi
i : integer
algoritma :
maks ← a1
for i ← 2 to n do
if a1 > maks then
maks ← a1
endif
endfor
B. Teorema Euclidean
Misalkan m dan n bilangan bulat, n > 0. Jika m dibagi dengan n maka terdapat bilangan bulat
unik q (quotient) dan r (remainder), sedemikian sehingga m = nq + r dengan 0 ≤ r<n .
Contoh :
1. 28 : 6 = 4, sisa 4
28 = 6 . 4 + 4
2. – 22 : 3 = - 8, sisa 2
-22 = 3 (- 8 ) + 2
Universitas Putra Batam2013 / 2014
Tapi -22 = 3(-7) – 1 salah
Karena r = -1 (syarat 0 ≤ r<n¿
C. Algoritma Euclidean
Tujuan : algoritma untuk mencari PBB dari dua buah bilangan bulat.
Penemu : Euclides, seorang matematikawan Yunani yang menuliskan algoritmanya
tersebut dalam buku, Element.
Misalkan m dan n adalah bilangan bulat tak negatif dengan m ≥ n. Misalkan ro = m dan r1
= n. Lakukan secara berturut-turut pembagian untuk memperoleh :
ro = r1q1 + r2 0 ≤ r2 ≤ r1,
r1 = r2q2 + r3 0 ≤ r3 ≤ r2,
rn– 2 = rn–1 qn–1 + rn 0 ≤ rn ≤ rn–1,
rn–1 = rnqn + 0
Menurut Teorema 2, PBB(m, n) = PBB(r0, r1) = PBB(r1, r2) = … =
PBB(rn– 2, rn– 1) = PBB(rn– 1, rn) = PBB(rn, 0) = rn
Jadi, PBB dari m dan n adalah sisa terakhir yang tidak nol dari runtunan pembagian tersebut.
Contoh :m = 80, n = 12 dan dipenuhi syarat m ≥ n80 = 6 . 12 + 8
12 = 1 . 8 + 4
8 = 2 . 4 + 0 Sisa pembagian terakhir sebelum 0 adalah 4, maka PBB(80, 12) = 4
D. Pembagi Bersama Terbesar (PBB)
Misalkan a dan b bilangan bulat tidak nol
Pembagi bersama terbesar (PBB – greatest common divisor atau gcd) dari a dan b adalah
bilangan bulat terbesar d sedemikian hingga d | a dan d | b.
Contoh :
Faktor pembagi 21 = 1, 3, 7, 21;
Faktor pembagi 16 = 1, 2, 4, 8, 16;
Universitas Putra Batam2013 / 2014
Faktor pembagi bersama 21 dan 16 : 1
Jadi, PBB (21, 16) = 1
Teorema : Misalkan m dan n bilangan bulat, dengan syarat n > 0 sedemikian sehingga m = nq + r
0 ≤ r<n, maka PBB(m, n) = PBB(n, r)
Contoh : m = 60, n = 18, 60 = 18 . 3 + 6
maka PBB(60, 18) = PBB(18, 6) = 6
E. Kombinasi Lanjar
PBB(a,b) dapat dinyatakan sebagai kombinasi lanjar (linear combination) a dan b dengan dengan
koefisien-koefisennya.
Contoh : PBB (80, 12) = 4 ,
4 = (-1) . 80 + 7 . 12
Teorema : Misalkan a dan b bilangan bulat positif, maka terdapat bilangan bulat m dan n
sedemikian sehingga PBB (a, b) = ma + nb
Contoh : Nyatakan PBB (21, 45) sebagai kombinasi lanjar dari 21 dan 45
Penyelesaian :
45 = 2 (21) + 3
21 = 7 (3) + 0
Sisa pembagian terakhir sebelum 0 adalah 3, maka PBB(45, 21) = 3
Substitusi dengan persamaan–persamaan di atas menghasilkan :
3 = 45 – 2 (21)
yang merupakan kombinasi lanjar dari 45 dan 21
Contoh soal :
Universitas Putra Batam2013 / 2014
Nyatakan PBB (312, 70) sebagai kombinasi lanjar 312 dan 70
Penyelesaian : Terapkan algoritma Euclidean untuk memperoleh PBB (312, 70)
312 = 4 . 70 + 32 (i) 32 = 5 . 6 + 2 (iii)
70 = 2 . 32 + 6 (ii) 6 = 3 . 2 + 0 (iv)
Sisa pembagian terakhir sebelum 0 adalah 2, maka PBB (312, 70) = 2
Susun pembagian nomor (iii) dan (ii) masing-masing menjadi
2 = 32 – 5 . 6 (iv)
6 = 70 – 2 . 32 (v)
Sulihkan (v) ke dalam (iv) menjadi
2 = 32 – 5 . (70 – 2 . 32) = 1 . 32 – 5 . 70 + 10 . 32 = 11 . 32 – 5 . 70 (vi)
Susun pembagian nomor (i) menjadi
32 = 312 – 4 . 70 (vii)
Sulihkan (vii) ke dalam (vi) menjadi
2 = 11 . 32 – 5 . 70 = 11 . (312 – 4 . 70) – 5 . 70 = 11 . 312 – 49 . 70
Jadi, PBB (312, 70) = 2 = 11 . 312 – 49 . 70
F. Relatif Prima
Dua buah bilangan bulat a dan b dikatakan relatif prima jika PBB (a, b) = 1
Contoh :
(i) 20 dan 3 relatif prima sebab PBB(20, 3) = 1
Universitas Putra Batam2013 / 2014
(ii) 7 dan 11 relatif prima karena PBB(7, 11) = 1
(iii) 20 dan 5 tidak relatif prima sebab PBB(20, 5) = 5 ≠ 1
Jikaa dan b relatif prima, maka terdapat bilangan bulat m dan nsedemikian sehingga
ma+nb=1
Contoh :
Bilangan 20 dan 3 adalah relatif prima karena PBB(20, 3) = 1, atau dapat ditulis
2 . 20 + (–13) . 3 = 1 (m = 2, n = –13)
Tetapi 20 dan 5 tidak relatif prima karena PBB (20, 5) = 5 ≠ 1
sehingga 20 dan 5 tidak dapat dinyatakan dalam m . 20 + n . 5 = 1
G. Aritmetika Modulo
Operator yang dipakai adalah mod ( memberikan sisa pembagian )
a mod m=r sedemikian hingga a=mq+r ,dengan0 ≤ r<m
Contoh :
Beberapa hasil operasi dengan operator modulo :
(i) 23 mod 5 = 3 (23 = 5 . 4 + 3)
(ii) 27 mod 3 = 0 (27 = 3 . 9 + 0)
(iii) 6 mod 8 = 6 (6 = 8 . 0 + 6)
(iv) 0 mod 12 = 0 (0 = 12 . 0 + 0)
(v) – 41 mod 9 = 4 (–41 = 9 (–5) + 4)
(vi) – 39 mod 13 = 0 (–39 = 13(–3) + 0)
Penjelasan untuk (v): Karena a negatif, bagi |a| dengan m mendapatkan sisa r’. Maka a mod m =
m – r’ bila r’ ≠ 0. Jadi |– 41| mod 9 = 5, sehingga –41 mod 9 = 9 – 5 = 4
Universitas Putra Batam2013 / 2014
H. Kongruen
Misalnya 38 mod 5 = 3 dan 13 mod 5 = 3, maka dikatakan 38 ≡ 13 (mod 5)
(baca: 38 kongruen dengan 13 dalam modulo 5)
Misalkan a dan b bilangan bulat dan m adalah bilangan > 0, maka a ≡ b (mod m) jika m
habis membagi a – b.
Jika a tidak kongruen dengan b dalam modulus m, maka ditulis a ≡/ b (mod m)
Contoh
1. 17 ≡ 2 (mod 3) ( 3 habis membagi 17 – 2 = 15)
2. –7 ≡ 15 (mod 11) (11 habis membagi –7 – 15 = –22)
3. 12 ≡/ 2 (mod 7) (7 tidak habis membagi 12 – 2 = 10 )
4. –7 ≡/ 15 (mod 3) (3 tidak habis membagi –7 – 15 = –22)
a ≡ b (mod m )dalam bentuk “ sama dengan” dapat dituliskan sebagaia=b+km(k adalah bilangan bulat)
Contoh :
1. 17 ≡ 2 (mod 3) 17 = 2 + 5 . 3
2. –7 ≡ 15 (mod 11) –7 = 15 + (–2)11
a mod m = r dapat juga ditulis sebagai a ≡ r (mod m)
Contoh :
(i) 23 mod 5 = 3 23 ≡ 3 (mod 5)
(ii) 27 mod 3 = 0 27 ≡ 0 (mod 3)
(iii) 6 mod 8 = 6 6 ≡ 6 (mod 8)
(iv) 0 mod 12 = 0 0 ≡ 0 (mod 12)
(v) – 41 mod 9 = 4 –41 ≡ 4 (mod 9)
(vi) – 39 mod 13 = 0 – 39 ≡ 0 (mod 13)
Universitas Putra Batam2013 / 2014
Contoh Soal Dan Penyelesaian Nya :
1. Hitunglah hasil pembagian Modulo berikut :
a. −173 Mod 21
Jawab:
−173 Mod 21 = −5
Penjelasan : (−173=21· (−8 )+ (−5 ) )
(−173 :21=−8 Sisa−5 )
b. 0 Mod 34 = 34
Jawab :
( 0 = 34 · 0 + 34 )
c. – 9821 Mod 45 = −11
Penjelasan : (−9821=45 · (−218 )+(−11 ) )
−9821 : 45 = −218 Sisa −11
d. – 340 Mod 9 = −7
Penjelasan : (−340=9 · (−37 )+(−7 ))
−340 : 9 = −37 Sisa −7
2. Tentukan PBB dari pasangan bilangan bulat a dan b berikut :
a. PBB ( 220 , 1.400 )
Jawab :
1.400 = 6 · 220 + 80 (i )
220 = 2 · 80 + 60 ( ii )
80 = 1 · 60 + 20 (iii )
60 = 3 · 20 + 0 ( IV )
PBB ( 1.400 , 220 ), PBB (220 , 80 ), PBB ( 80 , 60 ), PBB ( 60 , 20 ), PBB ( 20 , 0 )
Jadi PBB nya adalah 20
Sisa pembagian terakhir sebelum 0 adalah 20, maka PBB ( 220 , 1.400 ) = 20
b. PBB ( 110 , 273 )
Jawab :
Universitas Putra Batam2013 / 2014
273 = 2 · 110 + 53 ( i )
110 = 2 · 53 + 4 (ii )
53 = 13 · 4 + 0 ( iii )
PBB ( 273 , 110 ), PBB ( 110 , 53 ), PBB ( 53 , 4 ), PBB ( 4 , 0 ), Jadi PBB nya
adalah 4
Sisa pembagian terakhir sebelum 0 adalah 4, maka PBB ( 220 , 1.400 ) = 4
c. PBB ( 315 , 825 )
Jawab :
825 = 2 · 315 + 195 (i )
315 = 1 · 195 + 120 ( ii )
195 = 1 · 120 + 75 ( iii )
120 = 1 · 75 + 45 ( IV )
75 = 1 · 45 + 30 (V )
45 = 1 · 30 + 15 (VI )
30 = 2 · 15 + 0 (VII )
Sisa pembagian terakhir sebelum 0 adalah 15, maka PBB ( 315 , 825 ) = 15
d. PBB ( - 456 , 680 )
Jawab :
680 = 2 · ( - 456 ) + ( - 224 ) ( i )
- 456 = 2 · ( - 224 ) + ( - 8 ) ( ii )
- 224 = 28 · ( -8 ) + 0 ( iii )
Sisa pembagian terakhir sebelum 0 adalah - 8, maka PBB ( - 456 , 680 ) = - 8
3. Tentukan nilai X dan Y pada persamaan 58 x + 23 y = 128
Yang merupakan kombinasi lanjar dengan teori euclidean ?
Jawab :
128 = 23 y + 58 x → 128 = 23 x a x 5
Universitas Putra Batam2013 / 2014
Y = 23 x 5 + 3
Y = n dan x
= 5 c x = 13
X = 13
Y = 55
4. Tentukan himpunan penyelesaian dari 20 x2 + 11 y = 2011
Yang merupakan kombinasi lanjar dengan teori euclidean ?
Jawab :
Jika y = 1, maka
20 x2 + 11 (1 ) = 2011
20 x2 = 2011 – 11
20 x2 = 2.000
x2 = 2.000
20
x2 = 100
X = √100
X = 10
Jadi, HP dari 20 x2 + 11 y = 2011 adalah X = 10
5. Tentukan infersi dari a modulo m, jika a = - 39 dan m = 14
Jawab :
- 39 Mod 14 =
- 39 = 2 · 14 – 11 ( i )
14 = - 1 · (−11 ) + 3 ( ii )
- 11 = (−3 · 3 ) - 2 (iii )
3 = (−1 ·−2 ) + 1 ( IV )
- 2 = - 2 · 1 + 0 (VI ) Jadi, infersi dari a modulo m, jika a = - 39 dan m = 14 adalah 1
2. BILANGAN BULAT
Bilangan bulat adalah bilangan yang tidak mempunyai pecahan desimal, misalnya 8,
21, 8765, -34, 0
Berlawanan dengan bilangan bulat adalah bilangan riil yang mempunyai titik desimal,
seperti 8.0, 34.25, 0.02
Universitas Putra Batam2013 / 2014
A. Proposisi Bilangan Bulat
Jumlah bilangan bulat positif dari 1 sampai n adalah n (n+1 )
2
Pembuktian :
n = 1 ⟹ 1 = 1 = 1 (1+1 )
2
n = 2 ⟹ 1 + 2 = 3 = 2 (2+1 )
2
n = .................... ?
contoh nya :
1. Setiap bilangan bulat positif n ( n ≥ 2 ) dapat dinyatakan dengan perkalian dari satu atau
lebih bilangan prima
2. Untuk semua n ≥ 1, (n3 + 2n) adalah kelipatan 3
3. Untuk membayar biaya possebesar n sen dolar ( n ≥ 8 ) selalu d apat digunakan perangko
3 sen dan 5 sen
4. Di dalam sebuah pesta, setiap tamu berjabat tangan dengan tamu lain nya hanya sekali.
Jika ada n orang tamu, maka jumlah jabat tangan yang terjadi adalah n (n+1 )
2
B. Prinsip Induksi Sederhana
misalkan p (n) adalah proposisi perihal bilangan bulat positif dan kita ingin membuktikan bahwa
p(n) benar untuk semua bilangan positif n.
Untuk membuktikan proposisi ini, kita hanya perlu menunjukkan bahwa
1. p (1) benar, dan
2. Jika p (n) benar maka p (n +1) juga benar untuk setiap n ≥ 1
Sehingga p(n) benar untuk semua bilangan bulat positif n
Universitas Putra Batam2013 / 2014
Langkah 1 disebut sebagai basis induksi sedangkan langkah 2 disebut sebagai langkah
induksi. Langkah induksi berisi asumsi (andaian) yang menyatakan bahwa p(n) benar, asumsi
tersebut dinamakan hipotesis induksi.
C. Prinsip Induksi Yang Dirampatkan
Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n)
besar untuk semua bilangan bulat n ≥n0 . untuk membuktikan ini kita perlu menunjukkan bahwa
1. P(n0 ) benar, dan
2. Jika p(n) benar untuk semua bilangan bulat n ≥n0 .
Misalkan p(n) adalah proposisi bahwa untuk semua bilangan bulat tak negatif
20 + 21 + 22 + ... + 2n = 2n+1 – 1
1. Basis induksi p(3)
20 + 21 + 22 + 23 = 23+1 – 1
2. Langkah induksi
Misalkan p(n) = 20 + 21 + 22 + ... + 2n = 2n+1 – 1
Maka p(n+1) = 20 + 21 + 22 + ... + 2n + 2n+1 = 2(n+1) – 1 (buktikan)
Bukti
20 + 21 + 22 + ... + 2n + 2n+1 = (20 + 21 + 22 + ... + 2n ) + 2n+1
= (2n+1 – 1) + 2n+1 – 1
= 2n+1 – 1 +2n+1 = 2n+1 +2n+1 – 1
= (2 x 2n+1) – 1
= (21 x 2n+1) –1
= (21 x 2n+1+1) – 1
= ( 2(n+1+1) – 1
Penutup
Demikian lah makalah matematika diskrit ini saya buat, jika ada kata – kata saya yang
kurang berkenan, mohon di maklumi. Karena setiap karya seorang manusia pasti ada kekurangan
Universitas Putra Batam2013 / 2014
dan kelebihan nya. Saya juga sangat berterima kasih jika ada nya saran dan masukan dari
pembaca, karena saran anda sangat bermanfaat dan membantu saya untuk pembuatan makalah
yang selanjut nya.
Ilmu matematika diskrit sangatlah berguna untuk kita di dalam kehidupan sehar – hari,
tanpa ilmu matematika, kita dengan mudah saja di bodohi dan di per olok – olok kan oleh orang
lain. Maka dari itu, marilah kita bersama – sama untuk belajar matematika, demi masa depan
yang cerah. Karena pelajaran matematika sebenar nya bukan lah sulit, semua nya tergantung dari
niat dan kefokusan kita dalam mempelajari nya , serta dengan sering – sering mempelajari
contoh – contoh soal yang diberikan oleh dosen atau guru kita.
Akhir kata saya ucapkan Assalammu’alaikum Wr. Wb.
Daftar Pustaka
Muhir, Rinaldi, Matematika Diskrit, Bandung, 2005.
Muhir, Rinaldi, Algoritma & Pemograman dalam Bahasa Pascal dan C++, Bandung,
2007.
www.google.com
www.wikipedia.com
www.elearninguniversitasputrabatam.com