Berbagi

PENALARAN MATEMATIKA

Metoda Pembuktian

Definisi memainkan peranan penting di dalam matematika. Topik-topik baru matematika selalu diawali dengan membuat definisi baru. Sebagai contoh, teori fungsi kompleks diawali dengan mendefinisikan bilangan imajiner i, yaitu i² = -1. Berangkat dari definisi dihasilkan sejumlah teorema beserta akibat-akibatnya. Teorema-teorema inilah yang perlu dibuktikan. Pada kasus sederhana, kadangkala teorema pada suatu buku ditetapkan sebagai definisi pada buku yang lain, begitu juga sebaliknya. Selanjutnya, untuk memahami materi selanjutnya dibutuhkan prasyarat pengetahuan logika matematika.

1.  Bukti langsung

Bukti langsung ini biasanya diterapkan untuk membuktikan teorema yang berbentuk implikasi p q. Di sini p sebagai hipotesis digunakan sebagai fakta yang diketahui atau sebagai asumsi. Selanjutnya, dengan menggunakan p kita harus menunjukkan berlaku q. Secara logika pembuktian langsung ini ekuivalen dengan membuktikan bahwa pernyataan p q benar dimana diketahui p benar.

Contoh  Buktikan, jika x bilangan ganjil maka x² bilangan ganjil.

Bukti. Diketahui x ganjil, jadi dapat ditulis sebagai x = 2n - 1 untuk suatu bilangan

bulat n. Selanjutnya,

m

                               x² = (2n - 1)² = 4n² + 4n + 1 = 2 (2n² + 2) +1 = 2m + 1:

             

Karena m merupakan bilangan bulat maka disimpulkan x² ganjil.

2.  Bukti tak langsung

Kita tahu bahwa nilai kebenaran suatu implikasi p q ekuivalen dengan nilai kebenaran kontraposisinya ~q ~p. Jadi pekerjaan membuktikan kebenaran pernyataan implikasi dibuktikan lewat kontraposisinya.

Contoh  Buktikan, jika x² bilangan ganjil maka x bilangan ganjil.

Bukti. Pernyataan ini sangat sulit dibuktikan secara langsung. Mari kita coba saja. Karena x² ganjil maka dapat ditulis x² = 2m + 1 untuk suatu bilangan asli m. Selanjutnya x =  tidak dapat disimpulkan apakah ia ganjil atau tidak. Sehingga bukti langsung tidak dapat digunakan. Kontraposisi dari pernyataan ini adalah

”Jika x genap maka x² genap”.

Selanjutnya diterapkan bukti langsung pada kontraposisinya. Diketahui x genap, jadi

dapat ditulis x = 2n untuk suatu bilangan bulat n. Selanjutnya,

m

x² = (2n)² = 2 (2n²) = 2m

            

yang merupakan bilangan genap.

3.   Bukti kosong

Bila hipotesis p pada implikasi p q sudah bernilai salah maka implikasi p q selalu benar apapun nilai kebenaran dari q. Jadi jika kita dapat menunjukkan bahwa p salah maka kita telah berhasil membuktikan kebenaran p q.

Contoh  Didalam teori himpunan kita mengenal definisi berikut :

Diberikan dua himpunan A dan B. Himpunan A dikatakan himpunan bagian dari B, ditulis A B jika pernyataan berikut dipenuhi : ”jika x  A maka x B”. Suatu himpunan dikatakan himpunan kosong jika ia tidak mempunyai anggota.

Buktikan, himpunan kosong merupakan himpunan bagian dari himpunan apapun.

Bukti. Misalkan A =  suatu himpunan kosong dan B himpunan sebarang. Kita akan tunjukkan bahwa pernyataan ”jika x  A maka x B” bernilai benar. Karena A himpunan kosong maka pernyataan p yaitu x  A selalu bernilai salah karena tidak mungkin ada x yang menjadi anggota himpunan kosong. Karena p salah maka terbuktilah kebenaran pernyataan ”jika x A maka x B”, yaitu A B. Karena B himpunan sebarang maka bukti selesai.

4.   Bukti trivial

Bila pada implikasi p q, dapat ditunjukkan bahwa q benar maka implikasi ini selalu bernilai benar apapun nilai kebenaran dari p. Jadi jika kita dapat menunjukkan bahwa q benar maka kita telah berhasil membuktikan kebenaran p q.

Contoh 4. Buktikan, jika 0 < x < 1 maka 0 <

Bukti. Karena pernyataan q, yaitu 0 <  selalu benar untuk setiap x bilangan real termasuk x di dalam interval (0,1) maka secara otomatis kebenaran pernyataan ini terbukti.

5.   Bukti dengan kontradiksi

Metoda ini mempunyai keunikan tersendiri, tidak mudah diterima oleh orang awam. Dalam membuktikan kebenaran implikasi p q kita berangkat dari diketahui p dan ~q. Berangkat dari dua asumsi ini kita akan sampai pada suatu kontradiksi. Suatu kontradiksi terjadi bilamana ada satu atau lebih pernyataan yang bertentangan.

Contoh pernyataan kontradiksi : 1 = 2, -1 < a < 0 dan 0 < a < 1, ”m dan n dua bilangan bulat yang relatif prime”dan”m dan n keduanya bilangan genap”.

Contoh  Buktikan, jika x² bilangan ganjil maka x bilangan ganjil.

Misalkan x bilangan genap, maka x dapat ditulis x = 2n untuk suatu bilangan bulat n. Selanjutnya,

m

x² = (2n)² = 2 (2n²) = 2m

yang merupakan bilangan genap. Padahal diketahui x² adalah bilangan ganjil, terjadi kontradiksi. Artinya, asumsi bahwa x bilangan genap  adalah salah.

Bila dicermati ada kemiripan bukti dengan kontradiksi dan bukti dengan kontraposisi. Untuk menjelaskan perbedaan kedua metoda ini kita perhatikan struktur pada keduanya sebagai berikut :

•   Pada metoda kontradiksi, kita mengasumsikan p dan ~q, kemudian membuktikan adanya kontradiksi.

•   Pada bukti dengan kontraposisi, kita mengasumsikan ~q, lalu membuktikan ~p.

Asumsi awal kedua metoda ini sama, pada metoda kontraposisi tujuan akhirnya sudah jelas yaitu membuktikan kebenaran :p, sedangkan pada metoda kontradiksi tujuan akhirnya tidak pasti pokoknya sampai bertemu kontradiksi. Secara khusus jika kita sampai pada pernyataan: p maka kontradiksi sudah ditemukan. Jadi metoda kontraposisi merupakan kasus khusus dari metoda kontraposisi.

6.  Bukti eksistensial

Ada dua tipe bukti eksitensial ini, yaitu konstruktif dan takkonstruktif. Pada metoda konstruktif, eksistensinya ditunjukkan secara eksplisit. Sedangkan pada metoda takkonstruktif, eksistensinya tidak diperlihatkan secara eksplisit.

Contoh 7. Buktikan, ada bilangan irrasional x dan y sehingga xy rasional.

Bukti. Kita sudah mengetahui bahwa  irrasional, Jadi salah satu pasangan (x,y), dengan x = y = , pasti memenuhi pernyataan yang dimaksud.

Pada bukti ini hanya ditunjukkan eksistensi bilangan irrasional x dan y tanpa memberikannya secara eksplisit. Ini dikenal dengan istilah pembuktian eksistensi non konstruktif.

Contoh 8.   (Bartle and Sherbert, 1994). Bila a dan b bilangan real dengan a < b

maka terdapat bilangan rasional r dengan a < r < b.

Bukti. Diperhatikan bahwa  suatu bilangan real positif. Menurut sifat Archimedes terdapat bilangan asli n sehingga n >  . Untuk n ini berlaku nb - na > 1             (*)

Sekarang ambil m sebagai bilangan bulat pertama yang lebih besar dari na, dan berlaku

m - 1  na < m           (**)

Dari (*) dan (**) diperoleh

na < m  na + 1 < nb:

Bentuk terakhir ini dapat ditulis na < m < nb, dan dengan membagi semua ruas dengan n, didapat

a < < b

dan dengan mengambil r =  maka bukti Teorema selesai.

Dalam mebuktikan eksistensi bilangan rasional r, ditempuh dengan langkah-langkah konstruktif sehingga bilangan rasional yang dimaksud dapat dinyatakan secara eksplisit. Ini bukti eksistensial dengan konstruktif.

7.  Bukti ketunggalan

Dalam membuktikan ketunggalan, pertama harus ditunjukkan eksistensi suatu objek, katakan objek itu x. Ada dua pendekatan yang dapat ditempuh untuk membuktikan bahwa x hanya satu-satunya objek yang memenuhi, yaitu

•   Diambil objek sebarang, katakan y maka ditunjukkan y = x, atau

•   Misalkan y objek sebarang lainnya dengan y  y, ditunjukkan adanya suatu kontradiksi. cara ini tidak lain menggunakan metoda kontradiksi seperti yang sudah dibahas sebelumnya.

Contoh 10. Pada pengantar analisis real, biasanya kita menggunakan definisi limit barisan sebegai berikut :

Misalkan (x_n : n N) suatu barisan bilangan real. Bilangan real x dikatakan limit dari (x_n : n N), dan ditulis lim(x_n) = x jika dan hanya jika untuk setiap  > 0 yang diberikan terdapat bilangan asli K sehingga  <  untuk setiap n  K:

Kemudian, disusun teorema berikut ”Jika limit barisan (xn) ada maka ia tunggal.”

Bukti. Di sini tidak diperlukan bukti eksistensi karena kita hanya akan membahas barisan yang mempunyai limit, atau eksistensinya sudah diasumsikan. Sekarang kita gunakan pendekatan kedua. Andaikan barisan X := (x_n) mempunyai dua limit yang berbeda, katakan x_a dan x_b dengan x_a  x_b. Diberikan  :=

Karena lim(x_n) = x_a maka untuk  ini terdapat K_a sehingga <  untuk setiap n  K_a:

Juga, karena lim(x_n) = x_b maka terdapat K_b sehingga <  untuk setiap n  K_b:

Sekarang untuk n  maks  maka berlaku

 =

    +

  <   +

  =

Akhirnya diperoleh <  suatu pernyataan yang kontradikstif. Pengandaian x_a x_b salah dan haruslah x_a = x_b , yaitu limitnya mesti tunggal.

8.   Bukti dengan counter example

Untuk membuktikan suatu konjektur terkadang kita membutuhkan penjabaran yang cukup panjang dan sulit. Tapi bila kita dapat menemukan satu saja kasus yang tidak memenuhi konjektur tersebut maka selesailah urusannya.

Contoh 11. Misalkan ada konjektur berikut :

”Untuk setiap n bilangan asli maka  + 1 merupakan bilangan prima”

Bukti. Pernyataan ini berlaku untuk setiap bilangan asli n. Tapi bila bila ditemukan satu bilangan asli, katakan  dan + 1 tidak prima (komposit) maka konjektur ini tidak benar. Diperhatikan beberapa kasus berikut, untuk n = 1 diperoleh bilangan 5, n = 2 menghasilkan 17, n = 3 menghasilkan 257 dan n = 4 menghasilkan 65537. Keempat bilangan ini prima. Coba perhatikan untuk n = 5, diperoleh

2²⁵ + 1 = 4294967297 = (641)(6700417).

Ternyata bukan prima. Nah, n = 5 merupakan contoh penyangkalan (counter example). Akhirnya disimpulkan bahwa konjektur ini salah.

9.   Bukti dengan induksi matematika

Secara umum penalaran di dalam matematika menggunakan pendekatan deduktif. Tidak dapat dibayangkan bagaimana orang dapat membuktikan kebenaran pernyataan yang memuat kalimat ”untuk setiap  > 0 . . . ”, ”untuk setiap bilangan asli n . . .”, ”untuk setiap fungsi kontinu f . . .”, dan lain-lain. Tidak mungkin dapat ditunjukkan satu per satu untuk menunjukkan kebenaran pernyataan tersebut. Tapi ada salah satu pola penalaran pada matematika yang menggunakan prinsip induksi, biasanya disebut induksi matematika. Prinsip induksi matematika ini adalah untuk inferensi terhadap pernyataan tentang n dimana n berjalan pada himpunan bilangan bulat, biasanya himpunan bilangan asli N atau pada himpunan bagian bilangan asli, N₁  N. Biasanya pernyataan tentang bilangan asli n dinyatakan dengan P(n).

Contoh 12. Untuk setiap n  N, berlaku 1+2+3+......+n = (n+1). Diperoleh

P(1) : 1 = (1)(1 + 1)

P(3) : 1 + 2 + 3 =  (3)(3 + 1)

P(6) : 1 + 2 + 3 + 4 + 5 + 6 = (6)(6 + 1)

Teorema 1. Misalkan S himpunan bagian dari N yang mempunyai sifat-sifat berikut

(i) 1  S

(ii) k  S  k + 1  S.

Maka S = N.

Bukti. Lihat (Bartle dan Sherbet, 1994).

Bila P(n) suatu pernyataan tentang n bilangan asli maka P(n) dapat bernilai benar pada beberapa kasus atau salah pada kasus lainnya. Diperhatikan P(n) : bahwa n²  2ⁿ hanya benar untuk P(2); P(3); P(4) tetapi salah untuk kasus lainnya. Prinsip induksi matematika dapat diformulasikan sebagai berikut:

Misalkan untuk tiap n 2 N menyatakan pernyataan tentang n. Jika

(i) P(1) benar,

(ii) jika P(k) benar maka P(k + 1) benar,

maka P(n) benar untuk setiap n N.

Kembali kita dituntut membuktikan kebenaran implikasi p  q pada (ii). Di sini kita perlu membuktikan kebenaran pernyataan P(k+1) dengan diketahui kebenaran P(k).

Contoh 13.  (Ketidaksamaan Bernoulli). Jika x > -1 maka untuk setiap n N berlaku

(1 + x)ⁿ  1 + nx: (KB)

Bukti. Dibuktikan dengan induksi matematika. Untuk n = 1 kedua ruas pada (KB) menjadi kesamaan. Diasumsikan berlaku untuk n = k, yaitu berlaku (1+x)^k  1+kx.

Untuk n = k + 1, diperoleh

(1 + x)^k  1 + kx [ diketahui ]

                   (1 + x)^k+1 = (1 + x)^k(1 + x)  (1 + kx)(1 + x)

  = 1 + (k + 1)x + kx²

   1 + (k + 1)x:

Jadi berlaku untuk n = k + 1. Perhatikan pada baris kedua, kedua ruas dikalikan dengan (1+ x) suatu bilangan positif karena x > -1. Jadi tanda ketidaksamaan tidak berubah.

Satu lagi varian metoda induksi adalah dikenal dengan prinsip induksi kuat yang dinyatakan sebagai berikut :

Misalkan untuk tiap n  N menyatakan pernyataan tentang n. Jika

(i) P(1) benar,

(ii) jika P(1), P(2),...., P(k) benar maka P(k + 1) benar,

maka P(n) benar untuk setiap n N.

Contoh 14. Diberikan barisan (x_n) yang didefinisikan secara rekursif berikut

         x₁ := 1; x₂ := 1;

x_n+1 :=  untuk n > 1:

Misalkan P(n) : 1  xn  2 . Buktikan P(n) berlaku untuk semua n  N.

Bukti. Kita terapkan prinsip induksi matematika kuat.

1. Untuk n = 1, diketahui x₁ = 1. Jadi P(1) benar.
2. Diasumsikan P(1), P(2),....., P(k) benar, yaitu berlaku 1  x₁  2, 1  x₂ 2, 1  x₃  2, . . . , 1  x_k-1  2, 1  x_k  2. Dari kedua ketaksamaan terakhir 1  x_k-1  2, 1  x_k  2, bila dijumlahkan diperoleh

2    4, 1  = x_k+1  2

Ini berarti P(k + 1) benar. Jadi terbukti P(n) berlaku untuk semua n  N.

10.  Bukti dua arah

Ada kalanya suatu pernyataan berupa bi-implikasi, p q. Ada dua kemungkinan bi-implikasi bernilai benar p q yaitu p benar dan q benar, atau p salah dan q salah. Dalam prakteknya, pernyataan ini terdiri dari p q dan q p. Membuktikan kebenaran bi-implikasi p q berarti membuktikan kebenaran kedua implikasi p q dan q p. Selanjutnya dapat menggunakan bukti langsung, taklangsung atau mungkin dengan kontradiksi.

Contoh 15. Buktikan, suatu bilangan habis dibagi sembilan jika hanya jika jumlah angka-angka pembangunnya habis dibagi sembilan.

Bukti. Sebelum kita buktikan, dijelaskan terlebih dulu maksud dari pernyataan ini dengan contoh berikut. Ambil bilangan 135, 531, 351, 513, 315, 153, maka semuanya habis dibagi 9. Coba periksa satu per satu. Misalkan p suatu bilangan bulat, maka dapat disajikan dalam bentuk

p = x_nx_n-1x_n-2..... x₂x₁ x₀

dimana x_n  0; x_n-1,.....,x₀ bilangan bulat taknegatif.

Sedangkan nilai p ini dapat ditulis dalam bentuk berikut :

p = x₀ + x₁10¹ + x₂10² + . . .  +  x_n10ⁿ

Jumlah angka-angka pembangunnya adalah

s = x₀ + x₁ + x₂ + . . . + x_n.

Pertama dibuktikan ( ), yaitu diketahui p habis dibagi 9, dibuktikan s habis dibagi 9. Karena p habis dibagi 9 maka dapat ditulis p = 9k untuk suatu bilangan bulat k. Diperhatikan selisih p - s,

      p - s = x₀ + x₁10¹ + x₂10² + . . .  +  x_n10ⁿ – (x₀ + x₁ + x₂ + . . . + x_n)

              = (10 - 1)x¹ + (10² - 1)x² + . . . + (10ⁿ - 1)xⁿ

Diperhatikan bilangan pada ruas kanan selalu habis dibagi sembilan, misalnya ditulis

9m untuk suatu bilangan bulat m. Jadi diperoleh

    9k - s = 9m  s = 9(k - m)

yaitu s habis dibagi 9. Selanjutnya dibuktikan ( ), yaitu diketahui s habis dibagi 9, dibuktikan p habis dibagi 9. Diperhatikan

p = x₀ + x₁10¹ + x₂10² + . . .  +  x_n10ⁿ

   = x₀ + x₁ (10¹-1) + x₂ (10² -1)+ . . .  +  x_n (10ⁿ -1) + x₁ + x₂ + . . . + x_n.

   = [x₀ + x₁ + x₂ + . . . + x_n ] + [x₁ (10¹-1) + x₂ (10² -1)+ . . .  +  x_n (10ⁿ -1)]

s

                                   

                                   

Karena bilangan pada kelompok pertama dan kelompok kedua habis dibagi 9 maka terbukti p habis dibagi 9.