Logika Matematika : Metode Pembuktian

Kali ini, saya ingin berbagi tentang materi salah satu mata kuliah saya semester satu, Logika Matematika. Sebenarnya ini adalah tugas yang diberikan dosen. Tugasnya adalah membuat sebuah rangkuman materi-materi yang telah diajarkan selama satu semester serta membuat soal beserta pembahasannya. Setiap mahasiswa mendapat bagian materi yang berbeda. Kebetulan saya mendapat materi pembuktian dalam matematika.

Rangkuman ini saya susun dari beberapa sumber yang tidak saya sebutkan satu-persatu. Ragkuman ini sudah melalui proses revisi setelah mendapat bimbingan dari dosen saya, Dr. H. Imam Sujarwo, M.Pd. Semoga bermanfaat :)

METODE PEMBUKTIAN DALAM MATEMATIKA

Di dalam matematika, bukti adalah serangkaian argumen logis yang menjelaskan kebenaran suatu pernyataan. Argumen-argumen ini dapat berasal dari premis pernyataan itu sendiri, teorema-teorema lainnya, definisi, dan akhirnya dapat berasal dari postulat dimana sistem matematika tersebut berasal. Yang dimaksud logis di sini, adalah semua langkah pada setiap argumen harus dijustfikasi oleh langkah sebelumnya. Jadi kebenaran semua premis pada setiap deduksi sudah dibuktikan atau diberikan sebagai asumsi.

Pernyataan-pernyataan matematika seperti definisi, teorema dan pernyataan lainnya pada umumnya berbentuk kalimat logika, dapat berupa implikasi, biimplikasi, negasi, atau berupa kalimat berkuantor. Operator logika seperti and, or, not, xor juga sering termuat dalam suatu pernyataan matematika. Jadi membuktikan kebenaran suatu teorema tidak lain adalah membuktikan kebenaran suatu kalimat logika.

Paling tidak terdapat enam motivasi mengapa orang membuktikan, yaitu to establish a fact with certainty, to gain understanding, to communicate an idea to others, for the challenge, to create something beautiful, to construct a large mathematical theory.

To establish a fact with certainty merupakan motivasi paling dasar mengapa orang perlu membuktikan suatu pernyataan matematika, yaitu untuk meyakinkan bahwa apa yang selama ini dianggap benar adalah memang benar.

Terkadang, beberapa orang mempunyai pendirian sangat kuat bahwa suatu konjektur adalah benar. Keyakinan ini mungkin berasal dari penjelasan informal atau dari beberapa kasus yang ditemuinya. Bagi mereka tidak ada keraguan terhadap keyakinan itu, tapi belum tentu berlaku untuk orang dari kelompok lain. Disinilah bukti dapat dijadikan sarana untuk meyakinkan orang lain akan kebenaran suatu idea.

Tidak dapat dipungkiri selama ini banyak kebenaran fakta di dalam matematika hanya dipercaya begitu saja tanpa adanya kecurigaan terhadap kebenaran tersebut, tidak berusaha membuktikan sendiri, termasuk fakta-fakta yang sangat sederhana. Kita hanya menggunakan fakta tersebut karena sudah ada dalam buku (it was in the text) Banyak pembuktian yang tidak hanya membuktikan suatu fakta tetapi juga memberikan penjelasan tentang fakta tersebut. Disinilah, pembuktian teorema berfungsi untuk mendapatkan pemahaman (to gain understanding).

Metode Pembuktian

1.       Bukti Langsung

Bukti langsung ini biasanya diterapkan untuk membuktikan teorema yang berbentuk implikasi p g 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 g q benar dimana diketahui p benar.

Contoh :

1)      Buktikan, jika x bilangan ganjil maka x²  bilangan ganjil.

Pembahasan: Diketahui x ganjil, jadi dapat ditulis sebagai x = 2n-1 atau x=2n+1 untuk suatu bilangan bulat n. Selanjutnya, x² = (2n - 1)² = 4n² + 4n + 1 = 2 (2n² + 2)+1= 2m + 1

Keterangan : 2n²+2 diibaratkan sebagai m, karena adanya sifat ketertutupan operasi penjumlahan pada himpunan semua bilangan bulat. Penjumlahan dua bilangan bulat adalah bilangan bulat.

2)      Misalkan M suatu titik di dalam segitiga ABC. Buktikan bahwa AB + AC > MB + MC

Pembahasan: Misalkan N adalah titik perpotongan BM dan sisi AC.

Maka diperoleh AB + AC = AB + AN + NC = BM + MN + NC > BM + MC

3)      Buktikan bahwa jika a membagi b dan b membagi c maka a membagi c dengan a, b, dan c bilangan bulat.

Pembahasan :

a | b artinya b = ka untuk suatu k … (i)

b | c artinya c = lb untuk suatu l … (ii)

akan dibuktikan bahwa c = ma untuk suatu m

substitusi (i) ke (ii), sehingga diperoleh c = lb = l(ka) = (lk)a

karena lk adalah perkalian bilangan bulat yang hasilnya bilangan bulat juga (sifat tertutup perkalian bilangan bulat), maka ambil m := lk untuk dengan m , sehingga diperoleh

c = ma untuk suatu m

4)      Buktikan bahwa perkalian tiga bilangan asli berurutan habis dibagi 3

Pembahasan :

misal tiga bilangan asli berurutan didefinisikan sebagai n, n + 1 dan n + 2 untuk suatu n dan perkalian tiga bilangan asli adalah m. Disini kita akan menggunakan 3 kasus, yaitu 3k, 3k + 1, 3k + 2

(i) m     = (n)(n + 1)(n + 2)

= (3k)(3k + 1)(3k + 2)

= 3k(9k² + 9k + 2)

= 3(9k³ + 9k + 3)

   m adalah bilangan kelipatan 3

(ii) m    = (n)(n + 1)(n + 2)

= (3k + 1)(3k + 1 + 1)(3k + 1 + 2)

= (3k + 1)(3k + 2)(3k + 3)

= (3k + 1)(9k² + 15k + 6)

= 27k³ + 54k² + 21k + 6

= 3(9k³ + 18k³+ 7k + 2)

   m adalah bilangan kelipatan 3

(iii) m   = (n)(n + 1)(n + 2)

= (3k + 2)(3k + 2 + 1)(3k + 2 + 2)

= (3k + 2)(3k + 3)(3k + 4)

= (3k + 2)(9k² + 21k + 12)

= 27k³ + 81k² + 78k + 24

= 3(9k³ + 27k² + 26k + 8)

   m adalah bilangan kelipatan 3 dari (i), (ii), dan (iii) terlihat bahwa m merupakan bilangan kelipatan 3 berakibat m habis dibagi 3.

5)      Buktikan bahwa a + b bilangan ganjil jika dan hanya jika a atau b bilangan ganjil dengan a dan b bilangan bulat.

Pembahasan :

Pernyataan diatas ekuivalen dengan

(i) jika a + b bilangan ganjil maka a atau b bilangan ganjil

(ii) jika a atau b bilangan ganjil maka a + b bilangan ganjil

Jadi pada pembuktian ini kita akan membuktiaan (i) dan (ii).

Bukti bagian (i)

misalkan a dan b bilangan bulat sebarang dan a + b bilangan ganjil.

akan dibuktikan a atau b bilangan ganjil.

tanpa mengurangi perumuman akan dibuktikan a ganjil

klaim : b bilangan genap (b := 2m untuk suatu m )

a + b bilangan ganjil

a + b = 2k + 1 untuk suatu k

substitusi b = 2m sehingga diperoleh

a + 2m = 2k + 1

a = 2k – 2m + 1 = 2(k – m) + 1

karena tertutup terhadap operasi pengurangan, maka ambil l := k – m, sehingga diperoleh

a = 2l + 1

jadi a bilangan ganjil

selanjutnya akan dibuktikan b bilangan ganjil

klaim : a bilangan genap (a := 2p untuk suatu p )

a + b bilangan ganjil

a + b = 2q + 1 untuk suatu k

substitusi a = 2p sehingga diperoleh

2p + b = 2q + 1

b = 2q – 2p + 1 = 2(p – q) + 1

karena tertutup terhadap operasi pengurangan, maka ambil r := p – q, sehingga diperoleh

b = 2r + 1

jadi b bilangan ganjil

Bukti bagian (ii)

misal a dan b bilangan bulat sebarang dan a bilangan ganjil (a := 2m+ 1 untuk suatu m ) dan b bilangan genap (b := 2n untuk suatu n ). Sehingga

a + b = 2m + 1 + 2n = 2(m + n) + 1

karena tertutup terhadap operasi penjumlahan bilangan bulat, ambil p := m + n, sehingga

a + b = 2p + 1 untuk suatu p

jadi a + b bilangan ganjil

2.      Aturan Generalisasi Universal

Permis-premis dari argumen diasumsikan benar, maka konklusinya adalah benar

p(a)

            -----------

              x p(x)

Atau

            p(a)  q(a)

            -----------------------

              x[p(x)  q(x)]

Contoh :

3.      Aturan Spesifikasi Universal

Permis-premis dari argumen diasumsikan benar, maka konklusinya adalah benar

            x[p(x)  q(x)]

            p(t)

            --------------------

 q(t)

Contoh :

1)      SP adalah semua mahasiswa yang mendapat beasiswa bidik misi. p(x): x mahasiswa semester I, q(x): x mahasiswa semester III, dan r(x): mahasiswa yang menerima beasiswa bidik misi. Diberikan argumen-argumen sbb:

-Semua mahasiswa semester I atau semester III tidak ada yang mendapat beasiswa bidik misi

-Amir adalah mahasiswa yang menerima beasiswa bidik misi

Konklusi : Jadi, Amir bukan mahasiswa semester III

Jika Amir ditandai dengan a, buktikan argumentasi tersebut adalah valid.

Pembahasan :

Disimbolkan premis sebagai berikut :

Premis 1 : x[p(x)  q(x)]

Premis 2 : p(a)

Langkah langkah                        Alasan

x[p(x)  q(x)]                                 Premis 1

P(a)                                             Premis 2

P(a) q(a)                                      Aturan Spesifikasi Universal

Konklusi : q(a)

4.      Bukti dengan kontradiksi

Pembuktian melalui kontradiksi (bahasa Latin: reductio ad absurdum, 'reduksi ke yang absurd', bahasa Inggris: proof by contradiction, 'bukti oleh kontradiksi'), adalah argumen logika yang dimulai dengan suatu asumsi, lalu dari asumsi tersebut diturunkan suatu hasil yang absurd, tidak masuk akal, atau kontradiktif, sehingga dapat diambil kesimpulan bahwa asumsi tadi adalah salah (dan ingkarannya benar). Dalam disiplin matematika dan logika, pembuktian melalui kontradiksi merujuk secara khusus kepada argumen dimana sebuah kontradiksi dihasilkan dari suatu asumsi (sehingga membuktikan asumsi tadi salah) Argumen ini menggunakan hukum non-kontradiksi - yaitu suatu pernyataan tidak mungkin benar dan salah sekaligus.

Metode ini mempunyai keunikan tersendiri, tidak mudah diterima oleh orang awam.

Dalam membuktikan kebenaran implikasi p g 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 prima" dan "m dan n keduanya bilangan genap".

Contoh :

1)      Misalkan himpunan A didefinisikan sebagai interval setengah terbuka A := [0;1). Buktikan maksimum A tidak ada.

Pembahasan :

Pernyataan ini dapat dinayatakan dalam bentuk implikasi berikut

"jika A = (0;1) maka maksimum A tidak ada."

Andaikan maksimum A ada , katakan p. Maka haruslah 0 < p < 1, dan akibatnya

 p < 1 dan   (p + 1) < 1.

Diperoleh

p          =  p +  p <  p +  

=  (p + 1) < 1

Diperoleh dua pernyataan berikut :

·         p maksimum A, yaitu elemen terbesar himpunan A.

·         Ada q Є A (yaitu q =   (p + 1)) yang lebih besar dari p.

Kedua pernyataan ini kontradiktif, jadi pengandaian A mempunyai maksimum adalah salah, jadi haruslah tidak ada maksimum.

2)      Jika m dan n saling relatif prima, buktikan bahwa  bukan bilangan rasional.

Pembahasan:

Andaikan bahwa bilangan rasional maka dengan x dan y adalah bilangan asli. Maka berlaku m^x = n^y

Karena m dan n relatif prima maka tidak ada x dan y bilangan asli yang memenuhi (kontradiksi).

Terbukti, Jika m dan n saling relatif prima,  bukan bilangan rasional.

3)      Buktikan bahwa  adalah irrasional.

Pembahasan :

Andaikan adalah rasional, maka dapat dinyatakan sebagai  dengan p,q€Z dan p dan q relative prima. Kuadratkan kedua ruas, didapat

2q² = p²

Karena 2q² adalah genap, maka p² juga genap dan juga p genap. Akibatnya p=2r, r€Z. 2q² = (2r)²

2q² = 4r²

q = 2r

Persamaan terakhir mengatakan bahwa q juga merupakan bilangan kelipatan 2. Berarti, p dan q sama-sama mempunyai factor kelipatan selain 1. Akibatnya p dan q tidak relative prima. Ini kontradiksi dengan pernyataan bahwa p dan q relative prima. Jadi, haruslah irrasional.

5.      Bukti dengan Kontraposisi

            Menurut aturan kontrapositif, menunjukkan kebenaran proposisi p g q sama dengan menunjukkan ~q g ~p.

Contoh :

1)      Buktikan bahwa jika n² bilangan ganjil maka n juga bilangan ganjil.

Pembahasan:

Kita akan membuktikan soal ini dengan metode pembuktikan tidak langsung. Hal ini

berarti kita harus mengubah bentuk soal dalam kontraposisinya, yakni:

  Jika n bilangan genap maka n² merupakan bilangan genap.

Berdasarkan solusi (A.1), maka kontraposisi tersebut suatu pernyataan yang benar.

Jadi, terbukti bahwa jika n² bilangan ganjil maka n juga bilangan ganjil.

6.      Bukti dengan Induksi Matematika

Secara umum penalaran di dalam matematika menggunakan pendekatakan 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 :

1)      Untuk setiap n Є N , berlaku 1 + 2 + 3 + …..+ n =  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.

Misalkan S himpunan bagian dari N yang mempunyai sifat-sifat berikut

(i) 1 Є S

(ii) k 2S )k + 1 2S.

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 Є 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 g q pada (ii). Di sini kita perlu membuktikan kebenaran pernyataan P(k+ 1) dengan diketahui kebenaran P(k).

2)      Buktikan bahwa jumlah n buah bilangan ganjil positif pertama adalah n².

Pembahasan :

(i)  Basis Induksi: Untuk n = 1, Perhatikan 1 = 1²  (Benar).

(ii)  Langkah Induksi: Andaikan untuk n ≥ 1 pernyataan:

1 + 3 + … + (2n-1)  = n²  adalah suatu yang benar.

Akan ditunjukkan benar untuk 1 + 3 + … + (2n-1) + (2n +1) = (n + 1)²

Perhatikan bahwa 1 + 3 + … + (2n-1) + (2n +1)        = [1 + 3 + … + (2n-1)] + (2n +1)

                                                                        = n² + 2n + 1

                                                                        = (n+1)²

3)      Buktikan N³ + 2n adalah kelipatan 3 berlaku untuk n = 1 dan berlaku kelipatan 3 untuk setiap bilangan bulat postitif n

Pembahasan :

Untuk n = 1 akan diperoleh:13 + 2(1) = 3 yg merupakan kelipatan 3 (Berlaku)

Misalkan untuk n = k asumsikan k ³ + 2k = 3x

Untuk n = k + 1 berlaku          (k + 1)³ + 2(k + 1) adalah kelipatan 3

                                                            (k ³ + 3k ² + 3 k+1) + 2k + 2

                                                            (k ³ + 2k) + (3k ² + 3k + 3)

                                                            (k ³ + 2k) + 3 (k ² + k + 1)

                        Induksi                        3x + 3 (k ² + k + 1)

3 (x + k ² + k + 1)

                        Kesimpulan : N ³ + 2n adalah kelipatan 3 untuk setiap bilangan bulat positif n (Berlaku kelipatan 3).

atau, anda bisa mendownload file nya disini