Transcript

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


Top Related