metode pembuktian

METODE PEMBUKTIANBahan Kuliah Matematika Diskrit

Langkah-langkah Pembuktian (1) Tulis teorema yang akan dibuktikan. Tandai permulaan pembuktian dengan kata

“Bukti”. Buktikan secara lengkap dan menyeluruh.

Tulis variabel dan tipenya yang akan digunakan. Bila ada sifat dari variabel yang digunakan, tulis

sifat tersebut dengan lengkap dan jelas.

Langkah-langkah Pembuktian (1) Bila menggunakan sifat – sifat tertentu seperti

sifat komutatif maka tuliskan sifat tersebut. Jika ditengah pembuktian dijumpai suatu

ekspresi, misal r + s maka singkat ekspresi tersebut, misal dinyatakan dengan k.

Tandai akhir dari pembuktian.

Kesalahan yg sering dilakukan Menyimpulkan dari satu atau beberapa

contoh. Simbol yang sama untuk dua hal berbeda. Melompat ke kesimpulan padahal belum. mengasumsikan apa yg akan dibuktikan.

Metode Pembuktian (1) Pembuktian Langsung

Metode pengecekan satu per satu. Pembuktian berdasarkan kasus – kasus Pembuktian dengan eliminasi kasus Pembuktian dengan ekuivalensi

Metode Pembuktian (2) Pembuktian Tidak Langsung

Pembuktian dengan kontradiksi

dilakukan dengan ingkaran kalimat-nya dan buktikan salah

Pembuktian dengan kontraposisi

dilakukan dengan membuktikan kebenaran kontraposisinya

Contoh Metode Pembuktian Langsung

Buktikan bahwa untuk semua bilangan genap n antara 4 dan 30, n dapat dinyatakan sebagai jumlahan bilangan prima.

Penyelesaian:

dengan pengecekan satu persatu, maka:

4=2+2; 6=3+3; 8=3+5; 10=5+5; 12=5+7; 14=11+3; 16=11+5; 18=11+7; 20=13+7; 22=17+5; 24=19+5; 26=19+7; 28=17+11; 30=19+11

Contoh:Buktikan bahwa jumlah 2 bilangan genap adalah genap

Bukti:

Ambil sembarang 2 bilangan genap, misal m dan n. Akan dibuktikan bahwa (m+n) juga bilangan genap. Karena m dan n adalah bilangan-bilangan genap, maka m=2r dan n=2s untuk bilangan-bilangan bulat r dan s, sehingga:

m+n = 2r + 2s

= 2 (r+s).

= 2 k (misalkan k= r+s)

ContohBuktikan bahwa untuk semua bilangan bulat a, b, dan c berlakulah:

Jika a adalah faktor dari b dan b adalah faktor dari c, maka a adalah faktor dari c.

ContohBukti:

Misal a, b, dan c bilangan-bilangan bulat yang memenuhi sifat:

a adalah faktor dari b dan b adalah faktor dari c

a faktor dari b berarti b=ka untuk suatu bil bul k

b faktor dari c berarti c=nb untuk suatu bil bul n

Didapat: c = nb

= n (ka)

= (nk) a

ContohUntuk sembarang bilangan riil x, buktikan bahwa jika |x|>4, maka x2 > 16.

Bukti:

Misal x bilangan riil yang memenuhi |x|>4

Akan dibuktikan bahwa x2 > 16

|x|> 4 berarti bahwa x > 4 atau x < -4

Jika x > 4 maka x2 > 42 = 16

Jika x< -4 berarti –x > 4, sehingga (-x)2 > 42 atau x2 >16

Jadi, baik x > 4 maupun x < -4, x2 > 16.

ContohBuktikan bahwa jika p adalah sembarang bilangan prima yang ganjil maka p = 6n+1 atau p = 6n+5 atau p = 3 untuk suatu bilangan bulat n.

ContohBukti:

Ambil sembarang bilangan prima ganjil p.

Jika p dibagi 6, maka kemungkinan sisanya adalah 0, 1, 2, 3, 4 atau 5. Ini berarti bahwa

p = 6n atau p = 6n+1 atau p = 6n+2 atau

p = 6n+3 atau p = 6n+4 atau p = 6n+5

untuk suatu bilangan bulat n.

ContohUntuk kasus p = 6n = 2 (3n)

Misal s = 3n. Karena n adalah bilangan bulat, maka s juga bilangan bulat sehingga p = 2s untuk suatu bilangan bulat s. Karena p merupakan kelipatan 2, maka p merupakan bilangan genap sehingga bisa dieliminasi dari kasus.

ContohUntuk kasus p = 6n + 2 = 2 (3n+1)

Misal k = 3n+1. Karena n adalah bilangan bulat, maka k juga merupakan bilangan bulat sehingga p = 2k untuk suatu bilangan bulat k. karena p merupakan kelipatan 2, maka p merupakan bilangan genap sehingga bisa dieliminasi dari kasus.

ContohUntuk kasus p = 6n + 4 = 2 (3n+2)

Misalkan r = 3n+2. Karena n adalah bilangan bulat, maka r juga merupakan bilangan bulat, sehingga p = 2r untuk suatu bilangan bulat r. Karena p merupakan kelipatan 2, maka p merupakan bilangan genap sehingga bisa dieliminasi dari kasus.

ContohUntuk kasus p = 6n+3 = 3 (2n+1)

Misalkan m = 2n+1. Karena n adalah bilangan bulat, maka m juga merupakan bilangan bulat sehingga p = 3m untuk suatu bilangan bulat m. Ini berarti p habis dibagi 3, sehingga p bukan bilangan prima, kecuali untuk m = 1 (n=0) yang menghasilkan p = 3.

ContohDengan elininasi tersebut, kasus yang tersisa adalah p = 6n+1 atau p = 6n+5 atau p = 3.

Jadi terbuktilah bahwa jika p adalah bilangan prima ganjil, maka p = 6n+1 atau p = 6n+5 atau p = 3 untuk suatu bilangan bulat n.

ContohBuktikan ekuivalensi di bawah ini:

Misalkan a dan b adalah bilangan-bilangan bulat.

a dan b mempunyai sisa yang sama jika dibagi dengan bilangan positif n bila dan hanya bila (a-b) habis dibagi n.

ContohHarus dibuktikan 2 hal:

Jika a dan b mempunyai sisa yang sama bila dibagi dengan bilangan positif n, maka (a-b) habis dibagi n.

Jika (a-b) habis dibagi n, maka a dan b mempunyai sisa yang sama bila dibagi dengan bilangan positif n.

ContohMisalkan a dan b adalah bil2 bulat yang mempunyai

sisa sama (misal s) bila dibagi dengan n. Akan dibuktikan bahwa (a-b) habis dibagi n

a=kn+s dan b=jn+s dengan 0<s<n; k dan j bil bulat

a-b = (kn+s)-(jn+s) = (kn-jn) = (k-j)n

Misal p=k-j. Karena k dan j bil bulat, maka p bil bulat.

Sehingga a-b = pn untuk suatu bil bul p

Ini berarti bahwa (a-b) habis dibagi n.

ContohMisalkan a dan b bil2 bulat sedemikian hingga (a-b)

habis dibagi n. Akan dibuktikan bahwa a dan b mempunyai sisa yang sama bila dibagi dengan n.

Misalkan s1 adalah sisa yang terjadi bila a dibagi n dan

s2 adalah sisa yang terjadi bila b dibagi n.

Jadi a=kn+s1 dengan 0<s1<n

b=jn+s2 dengan 0<s2<n

Akan ditunjukkan bahwa s1=s2

ContohDiketahui bahwa (a-b) habis dibagi n, berarti

a-b = pn untuk suatu bilangan bulat p

a = b + pn = (jn + s2) + pn = (j+p) n + s2

Misal r = j+p. karena j dan p adalah bil2 bulat, maka r juga bilangan bulat sehingga:

a = r n + s2 dengan 0<s2<n

Akan tetapi jika a dibagi dengan n, maka pastilah hasil dan sisanya merupakan bil tunggal. Ini berarti s1=s2 dan r=k.

Contoh Metode Pembuktian Tak Langsung

Pembuktian dengan kontradiksi:

Buktikan bahwa tidak ada bilangan bulat yang terbesar.

ContohBukti:

Misalkan negasi dari pernyataan tersebut benar. Jadi andaikan ada bilangan bulat yang terbesar (sebutlah N). Karena N terbesar, maka N n untuk semua bilangan bulat n. Ambil M = N+1. Karena N adalah bilangan bulat, maka M juga bilangan bulat. Di samping itu, jelas bahwa N < M (karena M = N+1). Didapat: N n untuk semua bilangan bulat n

N < M untuk bilangan bulat M (krn M=N+1)

Keduanya kontradiksi

Contoh

Buktikan bahwa hasil kali 2 bilangan ganjil adalah bilangan ganjil.

ContohBukti:

Ambil sembarang 2 buah bilangan ganjil m dan n. Andaikan hasil kalinya (m.n) adalah genap. Karena m dan n bilangan ganjil, maka m=2k+1 dan n=2s+1 untuk bilangan-bilangan bulat k dan s.

mn=(2k+1)(2s+1)= 4ks+2s+2k=2(2ks+s+k)+1 Misal p=2ks+s+k. Maka p bilangan bulat karena k dan s bilangan bulat. mn=2p+1 untuk bil bul p.

mn ganjil, kontradiksi dengan pengandaian.

ContohPembuktian dengan kontraposisi

Buktikan bahwa untuk bilangan-bilangan bulat m dan n:

Jika m+n 73, maka m 37 atau n 37

ContohBukti:

Jika p adalah pernyataan m+n 73

q adalah pernyataan m 37

r adalah pernyataan n 37

Maka kalimat tsb dapat dinyatakan sbg: p(qr)Kontraposisinya adalah –(qr) -p atau (-q-r) -p

Dengan demikian, untuk membuktikan pernyataan mula-mula, cukup dibuktikan kebenaran pernyataan:

ContohJika m<37 dan n<37 maka m+n < 73

Ambil 2 bilangan bulat m dan n dengan sifat m<37 dan n<37

m<37 berarti m 36 dan n<37 berarti n 36,

Sehingga m+n 36+36 m+n 72 m+n < 73

Terbukti bahwa jika m<37 dan n<37 maka m+n < 73

Dengan terbuktinya kontraposisi, terbukti pula kebenaran pernyataan mula-mula.

LatihanBuktikan pernyataan-pernyataan berikut ini:

1. Untuk setiap bilangan bulat n, jika n adalah bilangan genap, maka n adalah bilangan genap.

2. Untuk setiap bilangan-bilangan bulat m dan n, jika m.n=1 maka m=1 dan n=1.

3. Untuk setiap bilangan bulat a, jika (a-2) habis dibagi 3, maka (a-1) habis dibagi 3 juga.

4. Untuk setiap bilangan bulat a, jika (a-1) mod 3=0 atau (a-2) mod 3=0, maka (a-1) mod 3=0.

5. Jika a dan b adalah bil2 ganjil, maka a+b bil genap

6. Jika a mod 10=2 dan b mod 10=8, mk a+b hbs dibagi

SELAMAT BELAJAR