INDUKSI Matematika Diskrit

INDUKSI 

Induksi Matematika itu a/ cara atau sebagai pembuktian sebuah pernyataan tertentu,  diberlakukan untuk bilangan asli. Pembuktiannya terdiri dari 2 cara seperti,

Menunjukkan jika pernyataan itu berlaku u/ bilangan 1.

Menunjukkan kalau pernyataan itu diberlakukan u/ bilangan n, maka pernyataan untuk itu berlaku juga u/ bilangan n + 1.

Prinsip Induksi yang Sederhana

Induksi Matematika ini bisa kita artikan seperti ini

Misal u/ setiap bilangan Real N kita memiliki pernyataan P(n) yg hasilnya bisa benar (true) atau salah (false).

Misal>>

P(1)  kita nyatakan sebagai true (benar).

Jika P(n) adalah true (benar), maka P(n + 1) hasilnya juga true (benar)

jadinya P(n) true (benar) u/ setiap bilangan Real (asli) n.

Langkah pertama kita sebut sebagai Langkah Dasar, sedangkan Langkah kedua kita sebut sebagai Langkah Induktif.

Contoh 1

menggunakana induksi matematika u/ mengetes/ mengetahui jikalau jumlah n adalah bilangan ganjil, bilangan + positih pertama a/ n2.

Mari kita buktikan:

1.  Basis induksi: U/ n = 1, jumlah 1  bilangan ganjil positif pertama a/ 19 = 1. Hasilnya menjadi true (benar) krn jumlah 1 bilangan ganjil positif pertama a/ 1.

cara induksi:

jikalau p(n) adalah true (benar), seperti

1 + 3 + 5 + … + (2n – 1) = n2

a/ true (benar )>>>(hipotes dari induksi)

[perlu digaris bawahi jika bilangan ganjil positif ke-n a/ (

2n – 1)]

Kita juga harus membuktikan jika p(n +1) hasilnya adalah true (benar) seperti,

1 + 3 + 5 + … + (2n – 1) + (2n + 1) = (n + 1)2

A/ benar. Hal ini dapat kita buktikan spt dibawah ini:

1 + 3 + 5 + … + (2n – 1) + (2n + 1) = [1 + 3 + 5 + … + (2n – 1)] + (2n + 1)

= n2 + (2n + 1)

= n2 + 2n + 1

= (n + 1)2

Krn langkah basis & langkah induksi ke2 telah diketahui jika hasilnya true (benar) jadi jumlah n bilangan ganjil positif pertama a/ n2.

Prinsip Induksi yang Dirapatkan/dipadatkan.

Misal p(n) a/ pernyataan tentang bilangan bulat & kita ingin mengetahui lebih lanjut jika  p(n) hasilnya true (benar) u/ all bilangan bulat  n3 n0. U/ membuktikan,kita hanya perlu tahu jika:

p(n0)  hasilnya true (benar), & u/semua bilangan bulat  n3 n0,

jika p(n) dinyatakan true (benar) maka p(n+1) juga hasilnya true  (benar)

Contoh>>

U/ all bil bulat bukan-negatif n, kita buktikan dengan induksi matematik jika

30 + 31 + 32 + … + 2n = 2n+1 – 1

Cara menyelesaikan:

1>Basis induksi.

u/ n = 0 (bukanlah bil bulat  neg pertama), we have:

30 = 30+1 – 1

Ini jelas benar, sebab  

30 = 1  

= 30+1 – 1

= 31 – 1

= 3– 1

= 1

2>Langkah induksi.

jikalau u/ semua bilangan bulat Bukanlah-negatif  n,

30 + 31 + 32 + … + 2n = 2n+1 – 1 

Kita nyatakan benar (hipotes induksi). Kita harus membuktikan bila,

30 + 31 + 32 + … + 2n + 2n+1 = 2(n+1) + 1 – 1

Hasilnya sama benar atau true. Kita buktikan sebagai berikut:

30 + 31 + 32 + … + 2n + 2n+1 = (30 + 31 + 32 + … + 2n) + 2n+1

= (2n+1 – 1) + 2n+1 (a/ H induksi)

= (2n+1 + 2n+1) – 1

= (2 . 2n+1) – 1

= 2n+2 – 1

= 2(n+1) + 1 – 1

Krn langkah pertama dan keduanya menyatakan hasilnya true (benar), jadi u/ semua bil bulat bukanlah-negatif n, karena telah kita buktikan jika

 30 + 31 + 32 + … + 2n = 2n+1 – 1

RELASI Matematika Diskrit

RELASI  

Jika di kehidupan nyata, ada yang namanya suatu hubungan (relasi) antara individu dan individu didalam suatu kelompok. Ataupun hubungan unsur lain terhadap unsur/ hal lain, misal, hubungan antar tetangga, hubungan mahasiswa dengan  mata kuliah ataupun hubungan dosen dengan pelajaran yang diampunya, dan lain-lain.

      Di materi Relasi ini, saya akan membahas tentang hubungan/ relasi, hubungan antara dua unsur/himpunan yang tidak kosong dengan satu aturan hubungan/perkaitan tertentu, Penjelasan yang saya akan jelaskan meliputi definisi dan fungsi, operasi dan sifatnya. 

Definisi

Kita misalkan E & F sebagai himpunan, hubungan antara himpunan E & himpunan F merupakan himpunan yang memiliki pasangan atau huruf/ angka yang berurutan,  tetapi  mengikuti aturan tertentu. Dengan demikian hubungan  biner R antar himpunan E dan F, merupakan himpunan  dari E × F / R ⊆(E × F).

Example:

Misal E  = {2, 4, 6} dan F = {2, 4, 6, 8 }. Jika didefinisikan relasi R dari E ke F  menggunakan aturan seperti, (e,fb) ∈ R jika faktor dari f, dan Seperti yang kalian pelajari sebelumnya atau yang sudah kalian ketahui,

 E × F menjadi :

E × F = {(2, 2), (2, 4), (2, 6), (2, 8), (4, 2), (4, 4), (4, 6), (4, 8), (6, 2), (6, 4), (6, 6), (6, 8)}

Jika menggunakan aturan relasi/ hubungan diatas, relasi R dari E  ke F  yang mengikuti aturan tadi menjadi,

R = {(2, 2), (2, 4), (2, 6), (2, 8)}

Hubungan/Relasi bisa juga  terjadi hanya pada satu atau sebuah himpunan, yaitu hubungan  pada E,  di himpunan E, yang merupakan himpunan E × E

Example: 

Misal R a/ relasi pada E = {2, 3, 4, 8, 9} yang diumpamakan :

(x, y) ∈ R dan bila x habis dapat dibagi oleh y.

Relasi R pada E  yang menggikuti aturan tersebut a/ seperti dibawah ini.

R = {(2, 2), (4, 4), (4, 2), (8, 8), (8, 2), (8, 4), (3, 3), (9, 9), (9, 3)}

Example about Relation/ contoh relasi : 

 

E :NAMA, SUBYEK/ Domain

F :OBYEK/ Kodomain

R :Relasi atau hubungan antar makanan favorit

                        Sifat-Sifat Relasi 

Relasi atau hubungan pada himpunan punya suatu sifat, sifat-sifat yang ada seperti..

1. Refleksif (reflexive)

Suatu relasi R pada himpunan E disebut refleksif jika (e, e) ∈ R untuk setiap e ∈ E. Dan bisa disebut juga hubungan relasi R pada himpunan E diketahui tidak refleksif jika e ∈ E dan begitu pula jika (a, a) ∉ R.

Example: 

Misalkan E = {1, 2, 3, 4}, 

dan sifat Relasi R adalah  ‘≤’ yang dimisalkan himpunan E, jadi

R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), 

(4, 4)}

Kelihatan bukan jika  (1, 1), (2, 2), (3, 3), (4, 4) adalah bagian unsur dari R. Jika begitu R dinyatakan himpunan Refleksif

Example : 

Misalkan E = {2, 3, 4, 8, 9, 15}.

Jika kita misalkan relasi R yang ada di himpunan A memiliki aturan:

(e, f) ∈ R jika e faktor prima dari f

Perlu diteliti/ diketahuin jika(4, 4) ∉ R .

Jadi, jelas bahwa R tidak  dan bukan bersifat refleksif.

Sifat refleksif memiliki ciri khas dalam pembuktian suatu relasi, seperti:

• Relasi yang memiliki sifat refleksif memiliki matriks dengan unsur utamanya semua bernilai 1, atau m_ii = 1, untuk i = 1, 2, …, n,

• Relasi yang memiliki sifat refleksif jika dibuktikan dalam bentuk graf terarah jadi  di graf tersebut akan ditemukan sebuah  loop pada setiap simpulnya.

2. Simetri (symmetric) dan Anti Simetri (antisymmetric)

Suatu relasi R di himpunan E memiliki sifat simetri jika 

(e, f) ∈ R, jika setiap e, f ∈ E , jadi (e, f) ∈ R.

Suatu relasi R pada himpunan E dikatakan tidak simetri jika (e,f) ∈ R sementara itu (e, f) ∉ R.

Pada suatu relasi R dihimpunan E mempunyai anti simetri dan misalkan untuk setiap

 a, b ∈ A, (a, b) ∈ R dan (b, a) ∈ R diakui jika a = b.

    Perhatikan bila istilah/ definisi simetri dan anti simetri bukanlah berlawanan, karena suatu relasi  bisa punya kedua sifat itu sekaligus. tapi , suatu relasi tak bisa mempunyai  kedua sifat itu jika dia punya atau memiliki pasangan berurutan atau terurut dengan bentuk

 (a, b) yang mana a ≠ b.

example: 

Misal R adalah sebuah relasi di himpunan Riil, yang dinyatakan oleh :

e R f  bila  & hanya jika e – f ∈ Y.

Memeriksa atau menyatakan relasi R memiliki sifat simetri !

Misal e R f  jadi/ maka (e – f) ∈ Y, Sementara  (f – e) ∈ Z.

Dan bila menyatakan seperti ini R memiliki sifat simetri.

Example : 

Buktikan bila relasi  ‘≤’ adalah himpunan Z.  Yang bersifat anti simetri

Jadi jika e ≤ f dan f ≤ e berarti e = f.

Hasilnya adalah  ‘≤’ menjadi/ memiliki sifat anti simetri.

3. Transitif (transitive)

Sebuah atau suatu relasi atau hubungan  R pada himpunan E mempunyai sifat transitif bila

(a, b) ∈ R dan (b, c) ∈ R, maka (a, c) ∈ R, untuk a, b, c ∈ A.

example :

Misal E  = { 2, 3, 4, 5, 6, 7, 8, 9}, & relasi  dapat diartikan bila :

e R f  jikalau & hanya bila e membagi f, dimana e, f ∈ E

Dan bila kita perhatikan definisi relasi R yang terdapat pada himpunan E, jadi :

R = {(2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, 6), (3, 9), (4, 4), (4, 8)}

Dan Bila (2, 4) ∈ R & (4, 8 ) ∈ R terbukti bila  (2, 8 ) ∈ R.

Dan relasi  R memiliki sifat transitif.

Example : 

R adalah relasi yang ada pada himpunan bilangan Riil N yang diketahui atau didefinisikan seperti:

R : E + f = 5, e, f ∈ E,

Dengan mengikuti relasi R pada himpunan E, jadi:

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

Buktikan bila  (1, 4) ∈ R & (4, 1) ∈ R , terapi (1, 1) ∉ R.

Jika seperti ini relasi R bukan atau tidak memiliki sifat transitif.

Sifat transitif memiliki beberapa ciri didalam pembuktian satu relasi , misalkan, sifat transitif di graf yang terarah dinyatakan seperti:

Bila  ada  satu/ sebuah busur dari e ke f dan busur dari f  ke g, jadi  juga memiliki sebuah busur

Berarah/ diarahkan dari e ke g.

Dan saat/ bila  menyajikan suatu relasi transitif didalam bentuk matriks, sebuah relasi transitif tidak memiliki satu ciri khusus di matriksnya.