CONTOH-CONTOH TEKNIK PEMBUKTIAN DALAM MATEMATIKA TUGAS 2
Disusun sebagai Tugas Kelompok Mata Kuliah Filsafat dan Sejarah Matematika
Oleh: KADIR SYARIFAH FADILLAH A. YONANDI YANRY BUDIANINGSIH JAPAR SIDIK AMRI
0706197 0706877 0707196 0705740 0706357 0706412
(S3) (S3) (S3) (S2) (S2) (S2)
PROGRAM STUDI S2 DAN S3 PENDIDIKAN MATEMATIKA SEKOLAH PASCASARJANA UPI BANDUNG JANUARI 2008
1
A. BUKTI MATEMATIKA Salah satu ciri khas ilmu matematika adalah bukti matematika dan pembuktian matematis. Filsafat matematika berurusan dengan peran bahasa dan logika matematika dalam pembuktian, dan dengan ilmu matematika yang dapat dipandang sebagai suatu bahasa. Bukti dan pembuktian dalam matematika menggunakan logika matematika namun tidak dapat lepas dari penggunaan bahasa sehari-hari yang biasanya mengandung kekaburan makna. Suatu bukti atau pembuktian adalah suatu cara untuk memastikan kebenaran suatu pernyataan. Suatu bukti matematika adalah suatu hasil upaya untuk menunjukkan bahwa, dengan bertumpu pada aksiomaaksioma tertentu dan dengan aturan-aturan logika matematika, suatu pernyataan adalah benar. Bukti matematika adalah argumen yang menggunakan logika, bukan bukti yang empiris. Suatu bukti matematika adalah suatu urutan berantai penarikan kesimpulan yang didasarkan pada suatu kumpulan aksioma dan sejumlah teorema yang sudah dibuktikan, tunduk kepada aturan-aturan logika matematika, dan berakhir dengan pernyataan yang akan dibuktikan. Pernyataan [matematika] adalah suatu kalimat matematika yang memiliki nilai kebenaran Benar atau Salah. (Kalimat itu strukturnya adalah kalimat berita.) Aksioma adalah pernyataan yang tidak dapat atau tidak perlu dibuktikan. Dalam banyak cabang matematika sistem aksioma yang dipakai sebagai dasar pembuktian adalah sistem aksioma ZFC, yaitu sistem aksioma untuk teori himpunan Zermelo-Fraenkel yang ditambah dengan Aksioma Pemilihan (Axiom of Choice). Pendekatan aksioma-danbukti, yang dimulai oleh Euclides, sekarang disebut metode aksiomatik.
2
Sekumpulan aksioma disebut lengkap jika ia dapat digunakan untuk membuktikan kebenaran atau ketakbenaran tiap pernyataan. Sekumpulan aksioma disebut konsisten jika tidak ada pernyataan yang dapat dibuktikan benar dan sekaligus salah. Suatu pernyataan yang belum dapat dibuktikan secara matematis namun memiliki bukti-bukti empiris dalam bentuk kasus-kasus dan contoh, dinamakan konjektur. Pernyataan
yang
memiliki
bukti
matematis,
artinya
telah
dibuktikan benar dengan berdasarkan aksioma-aksioma saja dan teoremateorema lain yang memenuhi aturan logika matematika, disebut teorema. Jika suatu pernyataan adalah suatu teorema, maka ia berlaku umum dan dapat digunakan sebagai dasar untuk membuktikan pernyataanpernyataan lain. Suatu lema adalah pernyataan pendahuluan yang memiliki bukti (disebut juga "teorema kecil") dan berguna untuk membuktikan pernyataan baru. Suatu teorema akibat (corrolary) adalah suatu teorema yang dapat diturunkan dari suatu teorema dalam beberapa langkah saja. Aturan penarikan kesimpulan (inference rules), atau deduksi logika matematika, adalah aturan yang meramu aksioma dan pernyataan yang benar untuk membentuk lebih banyak pernyataan yang benar. B. BEBERAPA MACAM BUKTI MATEMATIKA Pernyataan-pernyataan matematika dapat dibuktikan dengan: 1. Pembuktian langsung; 2. Pembuktian dengan induksi matematika; 3. Pembuktian
dengan
transposisi
atau
pembuktian
kontrapositif; 4. Pembuktian dengan kontradiksi atau reductio ad absordum;
dengan
3
5. Pembuktian dengan konstruksi atau pembuktian dengan contoh; 6. Pembuktian dengan exhaustion; 7. Pembuktian probabilistik; 8. Pembuktian kombinatorik; 9. Pembuktian nonkonstruktif; 10. Bukti atau bukan-bukti; 11. Pembuktian sederhana. Selain kesebelas bukti di atas, dalam matematika juga dikenal beberapa bukti lain, yaitu: 12. Pembuktian dengan contoh penyangkal (Counter example); 13. Pembuktian terdefinisi dengan baik (well defined); 14. Pembuktian Pigeon Hole; 15. Pembuktian jika dan hanya jika / biimplikasi (if and only if); dan 16. Pembuktian Unwinding definition. C. CONTOH-CONTOH METODE PEMBUKTIAN MATEMATIKA Contoh-contoh semua metode pembuktian pernyataan matematika di atas disajikan sebagai berikut. 1. Pembuktian langsung Dalam pembuktian langsung, kesimpulan dapat dicapai dengan mengkombinasi pernyataan yang akan dibuktikan, dengan logika matematika, aksioma-aksioma, definisi, dan teorema-teorema yang sudah ada. Contoh: Teorema: Jika a membagi b dan b membagi c, maka a membagi c Bukti: Berdasarkan definisi keterbagian, maka ada bilangan asli k1 dan k2 sedemikian sehingga b = a k1 dan c = b k2. Karena c = b k2 dan b = a k1, maka c = a k1 k2.
4
Misalkan k = k1 k2; maka k adalah bilangan asli dan c = a k, sehingga dengan definisi keterbagian disimpulkan a membagi c. 2. Pembuktian dengan Induksi Matematika Pembuktian dengan cara ini menggunakan himpunan bilangan bulat positif, untuk pembuktian kasus dasar, kemudian menerapkan aturan induksi untuk kasus-kasus yang berikutnya, acapkali untuk tak berhingga banyaknya kasus. Himpunan bilangan bulat positif adalah Z+ = {1, 2, 3, ...}. Ditetapkan bahwa P(n) adalah pernyataan matematika yang menyangkut bilangan bulat positif n. Harus dipastikan bahwa: i.
P(1) adalah benar, artinya P(n) benar untuk n = 1;
ii.
Jika diandaikan P(m) adalah benar untuk bilangan m ∈ Z+ maka harus diperoleh bahwa P(m + 1) adalah benar. (Bilangan m + 1 adalah pemberikut dari m.)
Jika kedua syarat itu sudah dipenuhi maka disimpulkan pernyataan P(n) adalah benar, atau berlaku, untuk semua bilangan bulat positif. Contoh: Gunakan induksi matematik untuk membuktikan bahwa jumlah n buah bilangan ganjil positif pertama adalah n2. Bukti: (i) Basis induksi: Untuk n = 1, jumlah satu buah bilangan ganjil positif pertama adalah 12 = 1. Ini benar karena jumlah satu buah bilangan ganjil positif pertama adalah 1. (ii) Langkah induksi: Andaikan p(n) benar, yaitu pernyataan 1 + 3 + 5 + … + (2n – 1) = n2 adalah benar (hipotesis induksi) [catat bahwa bilangan ganjil positif ke-n adalah 2n – 1]. Akan ditunjukkan bahwa p(n +1) juga benar, yaitu 1 + 3 + 5 + … + (2n – 1) + (2n + 1) = (n + 1)2
5
juga benar. Hal ini dapat ditunjukkan sebagai berikut: 1 + 3 + 5 + … + (2n – 1) + (2n + 1) = [1 + 3 + 5 + … + (2n – 1)] + (2n + 1) = n2 + (2n + 1) = n2 + 2n + 1 = (n + 1)2. Terbukti bahwa juga berlaku untuk n+1. Karena langkah basis dan langkah induksi keduanya telah diperlihatkan benar, maka terbukti bahwa jumlah n buah bilangan ganjil positif pertama adalah n2. 3. Pembuktian dengan transposisi Cara pembuktian ini juga dinamakan pembuktian dengan kontrapositif. Pembuktian ini memastikan bahwa pernyataan "Jika P, maka Q" adalah benar dengan menunjukkan kebenaran pernyataan kontrapositifnya, yaitu pernyataan "Jika Q tidak benar, maka P tidak benar". Dalam lambang-lambang, ditulis ¬ Q ⇒ ¬ P eq P ⇒ Q. Contoh: Teorema Jika x dan y adalah dua bilangan bulat di mana x + y genap, maka x dan y memiliki parity yang sama. Sebelum membuktikan teorema tersebut terlebih dahulu dikemukakan definisi bilangan bulat ganjil, bilangan bulat genap, dan parity. Definisi: 1. Bilangan bulat x disebut genap (atau ganjil) jika ada bilangan bulat k lain sehingga x = 2k (atau 2k + 1). 2. Dua bilangan bulat dikatakan mempunyai parity-nya sama jika kedua-duanya genap atau kedua-duanya ganjil Bukti Teorema:
6
Kontrapositif dari teorema tersebut adalah: ”Jika x dan y adalah dua bilangan bulat yang memiliki parity yang berbeda, maka x + y ganjil”. Misalkan x dan y memiliki parity yang berbeda. Karena salah satu bilangan bulat tersebut genap dan yang lainnya ganjil, maka dengan tidak mengurangi keumuman, misalkan x genap dan y ganjil. Jadi terdapat bilangan bulat k dan m sedemikian sehingga x = 2k dan y = 2m+1. Jika x dan y dijumlahkan, maka akan diperoleh x + y = (2k) + (2m + 1) = 2(k+m) + 1 yang menurut definisi merupakan bilangan bulat ganjil. 4. Pembuktian dengan kontradiksi Pembuktian dengan cara ini dinamakan juga pembuktian reductio ad absordum (reduksi sehingga absurd). Suatu pernyataan ingin dibuktikan benar. Jika diandaikan bahwa pernyataan itu tidak benar sehingga akan pasti memunculkan kontradiksi, maka disimpulkan bahwa pernyataan yang akan dibuktikan adalah benar. Contoh pembuktian dengan cara ini adalah pembuktian bahwa
2 adalah bilangan irasional, akar bilangan
irasional adalah bilangan irasional juga, dan bahwa tidak ada bilangan prima terbesar atau bilangan prima tidak berhingga. Contoh: Teorema : Terdapat tak berhingga banyak bilangan prima. Bukti: Asumsikan bilangan prima itu berhingga dan misalkan bilangan-bilangan prima itu adalah p1, p2, ..., pn. Misalkan bilangan q = p1p2... pn + 1 Maka q adalah prima atau komposit. Jika q dibagi oleh sebarang bilangan prima pi, maka hasilnya akan selalu bersisa 1 untuk setiap i = 1, 2, ..., n. Jadi, q bukan komposit. Oleh karena itu disimpulkan bahwa q adalah bilangan prima yang berbeda dengan bilangan prima p1, p2, ..., pn. Hal
7
ini kontradiksi dengan asumsi bahwa semua bilangan prima tersebut adalah p1, p2 ..., pn. 5. Pembuktian dengan konstruksi Cara pembuktian dengan konstruksi juga dinamakan pembuktian dengan contoh. Pembuktian ini membangun suatu contoh kongkrit yang memiliki sifat khusus untuk menunjukkan bahwa ada sesuatu yang lain yang memiliki sifat itu. Pembuktian ini menetapkan bahwa suatu objek tertentu itu ada dengan memberikan cara-cara menemukannya. Contoh: Teorema: Terdapat bilangan rasional antara akar kuadrat dari 10100 dan akar kuadrat dari 10100 + 1 Bukti: Akar kuadrat dari 10100 adalah 1050. Dengan cara coba-coba, misalkan x = 10 50 + 10 -51, yang jelas merupakan bilangan rasional yang lebih besar dari akar kuadrat dari 10100. Untuk membuktikan x lebih kecil dari akar kuadrat dari 10100+1, kita hitung x2 = (1050 + 10-51)2 = 10100 + (2) 10-1 + 10-102 yang jelas lebih kecil dari 10100+1. 6. Pembuktian dengan exhaustion Dalam pembuktian dengan cara ini, kesimpulan pernyataan dipastikan atau ditetapkan dengan membagi-baginya menjadi sejumlah berhingga kasus dan tiap kasus dibuktikan kebenarannya. Seringkali banyaknya kasus adalah besar sekali. Untuk pembuktian yang pertama Masalah
Empat
Wama,
pembuktian
dengan
cara
exhaustion
ini
menggunakan 1936 buah kasus dan tiap kasus harus dibuktikan tersendiri. Pembuktian ini dipandang kontroversial karena sebagian besar
8
dari kasus itu dikerjakan dengan menggunakan komputer, bukan dengan tangan. Pembuktian mutakhir masalah ini sekarang masih menggunakan 600 kasus. Contoh: Teorema: Jika n adalah bilangan bulat positif, maka n7 - n dapat dibagi oleh 7. Bukti: Pertama faktorkan n7 – n sebagai berikut: n7 - n = n(n6 - 1) = n(n3 - 1)(n3 + 1) = n(n - 1) (n2 + n + 1) (n + 1)(n2 - n + 1). Terdapat 7 kasus yang harus dipertimbangkan, bergantung pada n = 7q+r di mana r = 0, 1, 2, 3, 4, 5, 6, 7. Kasus 1: n = 7q. Maka n7 – n memiliki n faktor yang dapat dibagi oleh 7. Kasus 2: n = 7q + 1. Maka n7 - n memiliki n - 1 = 7q faktor yang dapat dibagi oleh 7. Kasus 3: n = 7q + 2. Maka faktor n2 + n + 1 = (7q + 2)2 + (7q+2) + 1 = 49 q2 + 35 q + 7 jelas dapat dibagi oleh 7. Kasus 4: n = 7q + 3. Maka faktor n2 - n + 1 = (7q + 3)2 - (7q+3) + 1 = 49 q2 + 35 q + 7 jelas dapat dibagi oleh 7. Kasus 5: n = 7q + 4. Maka faktor n2 + n + 1 = (7q + 4)2 + (7q+4) + 1 = 49 q2 + 63 q + 21 jelas dapat dibagi oleh 7. Kasus 6: n = 7q + 5. Maka faktor n2 - n + 1 = (7q + 5)2 - (7q+5) + 1 = 49 q2 + 63 q + 21 jelas dapat dibagi oleh 7. Kasus 7: n = 7q + 6. Maka faktor n + 1 = 7q+7 jelas dapat dibagi oleh 7.
9
7. Pembuktian probabilistik Dalam cara pembuktian ini, suatu contoh dibuktikan dengan cara teori probabilitas, bukan dengan argumen bahwa suatu teorema "mungkin" benar. Pembuktian probabilistik, seperti halnya pembuktian dengan konstruksi, adalah salah satu pendekatan untuk membuktikan teorema eksistensi. Contoh: Misalkan kita mempunyai grup lengkap pada n titik sudut (vertices). Akan ditunjukkan (untuk nilai n yang cukup kecil) bahwa kemungkinan untuk mewarnai sisi-sisi graph dalam dua warna (misalnya merah dan biru) sedemikian sehingga subgrup yang tidak lengkap pada r titik sudut adalah monokrom (setiap sisi berwarna sama). Bukti: Untuk membuktikan hal tersebut, warnai graph secara acak. Warna setiap sisi saling bebas dengan peluang ½ untuk yang berwarna biru dan ½ untuk yang berwarna merah. Banyaknya subgraph monokromatik yang diharapkan pada r titik sudut sebagai berikut: Untuk setiap himpunan S dari r titik sudut graph, definisikan variabel X(S) = 1 jika setiap sisi memiliki r titik sudut berwarna sama, dan 0 untuk hal lainnya. Banyaknya monokromatik r subgraph adalah jumlah X(S) untuk semua subset yang mungkin. Untuk setiap S, nilai harapan dari r X(S) adalah peluang bahwa semua sisi dalam S berwarna sama, 2 − r 2 2 ⋅ 2 (faktor dari 2 muncul karena terdapat dua kemungkinan warna).
Hal ini benar untuk setiap subset yang mungkin dari C(n, r) yang telah r
n 1− 2 dipilih, sehingga jumlah E[X(S)] untuk semua S adalah 2 . r
10
Jumlah dari suatu ekspektasi adalah espektasi dari jumlah (regardless of whether the variables are independent), sehingga ekspektasi dari jumlah r
n 1− 2 (banyaknya espektasi dari r subgraph monokromatik) adalah 2 . r Perhatikan apa yang terjadi jika nilai ini lebih kecil dari 1. Banyaknya r subgraph monokromatik dalam pewarnaan acak kita akan selalu bernilai bulat, sehingga paling sedikit satu warna yang kurang dari nilai yang diharapkan. Tetapi hanya bilangan bulat 0 yang memenuhi kriteria ini. Jadi jika C( n , r ) <
r −1 2 2 ,
beberapa warna sesuai dengan kriteria yang
diinginkan. Berdasarkan definisi, R(r, r; 2) harus lebih besar dari n. Secara khusus, R(r, r; 2) harus meningkat sedikitnya secara eksponensial terhadap r. 8. Pembuktian kombinatorik Pembuktian
cara
ini
menentukan
keekuivalenan
berbagai
pernyataan dengan menunjukkan bahwa pernyataan-pernyataan itu menghitung banyaknya objek yang sama dengan berbagai cara. Biasanya digunakan pemetaan bijeksi (satu-satu-pada) untuk menunjukkan bahwa dua interpretasi menghasilkan hasil yang sama. Contoh: Perhitungan Ganda Suatu sub komisi beranggota k dipilih dari suatu komisi beranggota n, dan kemudian satu anggota k dari sub komisi dipilih untuk mendapatkan n kursi. Banyaknya cara untuk melakukan ini adalah k . k Sebagai alternatif, pertama pilih kursi dari semua n anggota komisi asal dan kemudian pilih k – 1 anggota sub komisi lainnya di antara n - 1 anggota komisi
n − 1 . asal yang lainnya. Banyaknya cara untuk melakukan ini adalah n k − 1
11
n n − 1 . Jadi dapat disimpulkan bahwa k = n k k − 1 Teknik serupa digunakan untuk membuktikan identitas Vandermonde. Bukti Bijektif Misalkan kita ingin menunjukkan bahwa banyaknya subset berukuran k dari suatu himpuan berukuran n adaah sama dengan banyaknya subset berukuran (n – k) dari suatu himpuan berukuran n, yaitu bahwa n n = . k n − k Hal ini dapat dicapai dengan memperlihatkan suatu bijeksi antara himpunan dari semua subset berukuran k dan himpunan semua subset berukuran (n - k). Bijeksi tersebut - mungkin paling sederhana - adalah korespondensi antara setiap subset berukuran k dengan komplemennya relatif terhadap himpunan berukuran n yang lebih besar. 9. Pembuktian nonkonstruktif Pembuktian
ini
menetapkan
bahwa
suatu
objek
tertentu
matematika harus ada (harus eksis). misalnya "Ada S yang memenuhi f(S)" tanpa menunjukkan bagaimana objek itu dapat ditemukan atau dikonstruksi. Biasanya bentuk bukti ini seperti bukti dengan kontradiksi yang menunjukkan bahwa ketiadaan suatu objek adalah tidak mungkin. Contoh: Akan dibuktikan dengan cara nonkonstruktif bahwa ”Terdapat bilangan irasional a dan b sedemikian sehingga ab rasional”. Bukti: Ingat bahwa
2
2 adalah irasional dan 2 adalah rasional. Misalkan q =
2 . Akan diperiksa, apakah q rasional atau irasional.
Jika q rasional, maka teorema benar, dengan a dan b keduanya
2.
12
Jika q irasional, maka teorema benar, dengan a 2 2
2
= 2
(
2⋅ 2
)=
2
2 dan b
2 , karena
2
2 = 2.
Karena nilai a dan b tidak diketahui (sebab tidak diketahui kapan q irasional), maka bukti ini nonkonstruktif. Pernyataan "Apakah q rasional atau irasional", dari bukti di atas, adalah suatu penyederhanaan dari law of excluded middle, yang tidak valid dalam pembuktian konstruktif. Dengan kata lain, bukti konstruktif dari teorema yang sama akan memberikan suatu contoh yang aktual, seperti: log29 adalah bilangan irasional menurut faktorisasi tunggal dan 3 jelas merupakan bilangan rasional. 10. Bukti atau bukan-bukti Dalam matematika ada pernyataan yang tidak dapat dibuktikan dan tidak dapat disanggah dengan hanya menggunakan sistem aksioma ZFC saja. Contohnya adalah Teorema Ketaklengkapan Pertama Godel (Godel's First Incompleteness Theorem) yang berkaitan dengan Hipotesis Kontinuum. Tidaklah selalu mudah suatu pernyataan dapat dibuktikan dengan suatu sistem aksioma karena mungkin akan melibatkan banyak langkah yang sangat teknis. Ketidakmungkinan bukti dan bantahan (di ZFC). Cantor percaya hipotesis continuum benar dan mencoba selama bertahun-tahun untuk membuktikannya, tapi sia-sia. Hal ini menjadi utama pada daftar pertanyaan terbuka yang penting dari David Hilbert yang diperkenalkan pada International Mathematical Congress tahun 1900 di Paris. Axiomatic set theory pada saat itu belum dirumuskan. Kurt Gödel menunjukkan di tahun 1940 bahwa hipotesis continuum (CH) tidak bisa dibuktikan-balik dari standar teori himpunan Zermelo-Fraenkel (ZF), sekalipun aksioma pemilihan itu diadopsi (ZFC). Paul Cohen menunjukkan di 1963 bahwa CH tidak bisa dibuktikan dari
13
aksioma-aksioma yang sama. Karenanya, CH independen pada ZFC. Kedua hasil ini berasumsi bahwa aksioma Zermelo-Fraenkel tidak bertentangan; asumsi ini diterima kebenarannya secara luas/umum. Hipotesis
continuum
bukan
pernyataan
pertama
yang
menunjukkan independensi dari ZFC. Satu konsekuensi kemudian dari teorema ketidaklengkapan Gödel, yang diterbitkan dalam 1931, adalah bahwa ada suatu pernyataan formal kekonsistenan ZFC yang independen pada ZFC. Statemen kekonsistenan ini berasal dari suatu yang metamatematis, dibanding sifat matematis semata. Hipotesis continuum dan
aksioma
pemilihan
adalah
di
antara
pernyataan-pernyataan
matematis pertama yang menunjukkan kebebasan teori himpunan ZF. Pembuktian independensi ini tidak lengkap sampai Paul Cohen mengembangkannya pada tahun 1960-an. Hipotesis Continuum berhubungan erat dengan banyak statemen di dalam analisis, topologi himpunan titik, dan teori ukuran. Sebagai hasil dari keindependenannya, banyak konjektur substansif dalam lapangan yang sudah ditunjukkan keindependenannya dengan baik. Sampai sejauh ini, CH indepenen terhadap semua large cardinal axioms yang dikenal dalam konteks ZFC. 11. Pembuktian sederhana Pembuktian sederhana biasanya tidak menggunakan analisis yang rumit. Di masa lalu ada teorema-teorema khusus, misalnya Teorema Bilangan Prima, yang dibuktikan dengan menggunakan "matematika tinggi". Namun dalam perjalanan waktu, bukti-bukti itu telah dapat dibuktikan ulang dengan teknik-teknik yang sederhana. Contoh: Akan dibuktikan bahwa ”Kuadrat setiap bilangan bulat positif berbentuk 3k atau 3k + 1”.
14
Bukti: Misalkan a bilangan bulat positif. Akan dibuktikan bahwa a = 3k atau a ≠ 3k, yaitu a = 3k + 1 atau a = 3k + 2. a. Jika a kelipatan 3, maka a = 3m sehingga a2 = 9m2 = 3(3m2). Misalkan k = 3m2, maka a = 3k. b. Jika a bukan kelipatan 3, maka a berbentuk a = 3m +1 atau a = 3m + 2. Untuk a = 3m + 1, maka a2 = (3m + 1)2 = 9m2 + 6m + 1 = 3(3m2+ 2m) + 1. Misalkan k = 3m2 + 2m, maka a = 3k + 1. Untuk a = 3m + 2, maka a2 =(3m + 2)2 = 9m2 + 12m + 4 = 3(3m2+ 4m+1)+1.
Misalkan k = 3m2 + 4m + 1, maka a = 3k + 1. Dengan demikian terbukti bahwa kuadrat setiap bilangan bulat positif berbentuk 3k atau 3k + 1. 12. Pembuktian dengan counter example Counter example memiliki peran yang sangat penting dalam matematika. Suatu pembuktian yang rumit mungkin merupakan satusatunya cara untuk menunjukkan kebenaran teorema tertentu, sebuah counter example tunggal adalah cukup untuk menyangkal kebenaran dari suatu pernyataan. Contoh: Bentuk
, n bilangan bulat positif merupakan bilangan prima.
Bukti: Untuk n = 1, 2, 3, dan 4 diperoleh tetapi untuk
merupakan bilangan prima,
diperoleh
,
memiliki faktor lain selain 1 dan dirinya sendiri. Dengan kata lain, bukan bilangan prima tapi bilangan komposit. Kesimpulannya: ketika mensubstitusikan suatu bilangan ke bentuk , tidak bisa mengasumsikan itu merupakan bilangan prima atau
15
komposit, kecuali jika diketahui secara pasti dengan alasan yang jelas. Hal ini berlaku juga dalam pembuktian konvers dari suatu pernyataan. Konvers dari pernyataan “Jika P maka Q” adalah pernyataan “Jika Q maka P” Contoh: Bilangan rasional dan irrasional Jika
dan
adalah bilangan rasional, maka tentukan bentuk
Bukti: Misalkan a dan b bilangan rasional, yaitu
dan
bilangan bulat
tidak nol. Jumlah dari
tertentu dengan
Menurut definisi, bentuk
juga merupakan bilangan rasional.
Konversi pernyataan di atas: ”Jika sedemikian sehingga
untuk suatu
dan
adalah bilangan real
adalah bilangan rasional, maka
dan
adalah
bilangan rasional”. Pernyataan ini adalah salah. Hal ini dapat dibuktikan dengan counter example: Ambil irasional, tetapi
dan
dua bilangan
yang merupakan bilangan rasional.
13. Pembuktian well defined (terdefinisi dengan baik) Untuk memahami pembuktian bahwa sesuatu itu terdefinisi dengan baik, perhatikan contoh berikut. Contoh: Aritmetika Kongruensi Untuk suatu bilangan bulat kongruen oleh
modulo
dan bilangan bulat positif
(ditulis
mod
), jika
. Dengan kata lain ada bilangan bulat . Contoh,
Bilangan
dan
mod
karena
, dikatakan habis dibagi
sedemikian sehingga .
merupakan perwakilan ‘bilangan’ yang sama dalam
16
modulo
. Jadi ‘bilangan’
adalah suatu sistem dan di dalamnya adalah
. Contoh, m = 0 mod(m) sehingga 0 tidak dimasukkan. Hal ini menghasilkan perhitungan dengan ‘bilangan’ baru. Contoh: definisikan penjumlahan modulo
dengan penjumlahan standar. Tetapi
sangat memungkinkan munculnya masalah. Jika mod
mod
dan
, akan didapatkan hasil yang sama, yaitu penjumlahan
atau
.
Teorema Penjumlahan adalah well defined modulo mod
, maka
, yaitu, jika
mod
mod
dan
.
Bukti: Akan ditunjukkan bahwa ada suatu bilangan bulat . Karena ada bilangan bulat
dan
mod
sedemikian sehingga
dan
mod
sedemikian sehingga
. Dengan demikian, Misalkan
, maka mod
, maka dan .
sehingga disimpulkan
.
Berdasarkan contoh di atas, well defined berarti tidak menyebabkan suatu inkonsistensi internal dan bebas kontradiksi. Untuk memahami dengan baik ide ini, perhatikan contoh yang tidak well defined berikut. Contoh: Tidak well defined Gunakan perhitungan modulo, dengan pembagian. Perhatikan bilangan bulat
dengan
genap. Misalkan
maka
menghasilkan solusi tunggal
. Tetapi, ada beberapa bilangan bulat tersebut. Jadi,
tidak well defined.
dalam perhitungan modulo 2, untuk persamaan
mod
yang memenuhi persamaan
17
Contoh: Fungsi modulo Dalam sistem bilangan modulo
, diwakili oleh
secara tradisional dikatakan himpunan anggota, yaitu
yang
. Misalkan,
memiliki 4
. Semua bilangan bulat yang lain hanya
merupakan nama lain dari keempat bilangan itu. Contoh, dan
mod
mod
.
Teorema Fungsi
dengan
adalah well defined.
Bukti: mod
Akan dibuktikan Misalkan,
mod
, maka
, yaitu
habis dibagi 4.
habis dibagi 4. Perhatikan bahwa,
. Karena a – b habis dibagi 4, maka 2(a – b) juga habis dibagi 4, sehingga
mod (4).
14. Pembuktian Pigeon Hole (Lubang merpati) Prinsip Pigeon Hole (Lubang Merpati) tidak lebih dari komentar yang jelas: ”jika memiliki sedikit lubang merpati daripada merpati dan semua merpati akan dimasukkan ke dalam lubangnya, maka hasilnya haruslah minimal satu lubang merpati dengan lebih dari satu merpati. Hal itu mengejutkan untuk digunakan menjadi suatu strategi pembuktian. Contoh: Teorema Di antara setiap bilangan bulat positif dapat dibagi oleh
, ada dua yang berbeda yang
.
Bukti Misalkan terdapat bilangan-bilangan diperoleh
sisa hasil bagi
hanya bernilai
oleh ). Ada
. Untuk setiap . (Jadi
mod
dan
kemungkinan nilai untuk setiap
18
, tetapi ada N ri. Dengan menggunakan aturan lubang merpati, ada dua ri yang sama,
untuk beberapa pasangan
dan . Tetapi kemudian
ai yang bersesuaian memiliki sisa yang sama ketika dibagi oleh habis dibagi oleh
. Jadi
.
15. Pembuktian Jika dan Hanya Jika Beberapa teorema berbentuk “P jika dan hanya jika Q”. Dengan kata lain “Q adalah syarat perlu dan cukup untuk P”. Hal tersebut berarti dua hal: “Jika P maka Q” dan “Jika Q maka P”. Jadi untuk membuktikan teorema “Jika dan hanya jika”, harus dibuktikan kedua implikasi tersebut. Contoh: Pembagian Dalam contoh ini digunakan fakta yang sering digunakan pada bilangan bulat, yaitu algoritma pembagian:”jika dua bilangan bulat lain . Contoh, jika
dan
bilangan bulat, maka ada
dan , dimana dan
sedemikian sehingga , maka
.
Teorema Jika
suatu bilangan bulat, maka
hanya jika
tidak habis dibagi oleh
jika dan
habis dibagi oleh .
Bukti ( ) Akan dibuktikan jika a tidak habis dibagi 3, maka a2 - 1 habis dibagi 3. Misalkan a = 3q + r denga r = 0, 1, atau 2. Karena a tidak habis dibagi 3, maka r ≠ 0. Jika r = 1, maka a – 1 = 3q sehingga a2 – 1 = (a – 1) (a + 1) habis dibagi 3. Jika r = 2, maka a2 = (3q + 2)2 = 9q2 + 12q + 4 atau a2 – 1 = 9q2 + 12q + 3 = 3 (3q2 + 4q + 1) yang habis dibagi 3. () Akan dibuktikan jika a2 - 1 habis dibagi 3, maka a tidak habis dibagi 3. Karena a2 – 1 habis dibagi 3, maka
habis dibagi 3.
19
Karena
adalah bilangan prima, maka
. Dalam kasus lain, jelas bahwa
harus habis membagi
atau
tidak habis membagi .
Berdasarkan kedua pembuktian di atas disimpulkan teorema terbukti. 16. Pembuktian unwinding definition (menguraikan definisi) Satu dari banyak pertanyaan yang sering dikeluhkan siswa dalam pembuktian adalah “Bagaimana memulainya?”. Jawabannya sederhana, yaitu: uraikan definisi. Pertama, perhatikan apa yang ditanyakan dalam pembuktian. Apakah semua sudah melibatkan yang sudah didefinisikan (dalam kuliah atau dalam teks atau dalam masalahnya)? Tulis definisinya. Apa yang diasumsikan? Apakah melibatkan definisi? Jika ya, tulis kembali. Kadang-kadang teorema sesuai dengan permasalahannya. Jika ya, tuliskan. Jangan takut melakukan sesuatu yang diketahui untuk mencoba membuktikannya. Contoh: Faktor persekutuan terbesar (FPB) FPB dari dua bilangan bulat positif yang memenuhi dua sifat: (1)
dan
adalah bilangan
habis membagi
gcd
dan , (2) jika
bilangan bulat positif lain yang habis membagi
dan
adalah
, maka
.
Dengan kata lain gcd seperti operasi biner. Teorema Operasi biner gcd adalah asosiatif, yaitu untuk bilangan bulat positif dan gcd(gcd(
), ) = gcd( ,gcd(
))
Uraian Strategi Apa yang harus dibuktikan? Dua gcd adalah sama. Dari mana memulai? Misalkan berarti (1)
adalah gcd nya, habis membagi gcd(
gcd(gcd(
), ). Apa artinya? Hal itu
) dan , (2) Jika
bulat positif lain yang habis membagi gcd(
) dan
adalah bilangan maka
. Harus
20
dibuktikan (1)
= gcd( ,gcd(
habis membagi
)). Apa artinya? Harus membuktikan dua hal
dan gcd
positif lain yang habis membagi (1)
membagi gcd( jadi
),
, (2) Jika dan gcd
membagi
dan , jadi
asumsinya
maka
.
harus membagi . Diketahui
harus membagi gcd
(2) Sekarang misalkan
adalah bilangan bulat
membagi ,
.
membagi
dan gcd
membagi gcd(
. Maka,
) juga. Tetapi kemudian
. Dan ini semua memerlukan pembuktian.
Bukti Teorema Misalkan membagi
Maka dan gcd(
membagi gcd(
). Jika
membagi
membagi
) dan , dan akibatnya
dan , dan akibatnya
dan gcd( . Jadi
), maka
harus
gcd( , gcd(
)).
21
Catatan Acapkali di akhir penulisan pembuktian, ada tulisan "QED". Ini artinya adalah Quod Erat Demonstrandum, yaitu bahasa Latin untuk "yaitu yang diminta untuk dibuktikan". Sering juga tulisan QED itu diganti dengan halmos atau nisan, lambang kecil persegi panjang tegak, kosong , yang menandai berakhirnya pembuktian.
atau kotak kecil
22
Daftar Pustaka Albert R. Meyer (2007). Course Notes, Week 1, 6.042J/18.062], Spring '07: Albert R. Meyer, Radhika Nagpal (2002). Course Notes 1, 6.042J/18.062J, Fall '02: Mathematics for Computer Science. Massachusetts Institute of Technology. Math Forum Ask Dr_ Math FAQ False Proofs and Classic Fallacies. http://mathforum.org/dr.math/faq/faq.false.proof.html. Online. Diakses 28 Nopember 2007. Mathematics for Computer Science. Revised March 22, 2007, Massachusetts Institute of Technology. Proofs in Mathematics. http://www.cut-the-knot.org/proofs/index.shtml. Online. Diakses 28 Nopember 2007 Proofs
Without Words. http://www.cut-the-knot.org/ctk/pww.shtml. Online. Diakses 28 Nopember 2007.
Pythagorean Theorem. http://www.cut-the-knot.org/pythagoras/index. shtml. Online. Diakses 28 Nopember 2007. Randomness and Mathematical Proof. http://www.umcs.maine.edu/ ~chaitin/sciamer.html. Online. Diakses 28 Nopember 2007. The
nature of mathematical proof. http://www.royalsoc.ac.uk/ downloaddoc.asp?id=1547. Online. Diakses 28 Nopember 2007.
Wikipedia. http://en.wikipedia.org/wiki/Mathematical proof. Online. Diakses 26 September 2007. Wikipedia. http://en.wikipedia.org/wiki/Mathematical_proof. Online. Dikases 28 Nopember 2007. Wikipedia. http://id.wikipedia.org/wiki/Matematika. Online. Diakses 28 Nopember 2007.
23
Lampiran I: Sistem Aksioma Zermelo-Fraenkel dengan Aksioma Pemilihan (Axiom of Choice), ZFC Aksioma Ekstensionalitas Dua himpunan adalah sama jika keduanya memiliki anggota yang sama.
(∀z ){z ∈ x ⇔ z ∈ y} ⇒ x = y Aksioma Pasangan Untuk sebarang dua himpunan x dan y, ada suatu himpunan {x,y} yang anggotanya hanyalah x dan y itu. Aksioma Gabungan Gabungan suatu kumpulan himpunan, z, adalah himpunan juga.
(∃u )[(∀x )(∃y )[x ∈ y ∧ y ∈ z ]] ⇔ x ∈ u Aksioma Himpunan Takberhingga Ada
suatu
himpunan
takberhingga,
khususnya
suatu
himpunan
takkosong x sedemikian sehingga untuk sebarang himpunan y ∈ x, himpunan {y} adalah juga anggota himpunan x. Aksioma Subhimpunan, Aksioma Himpunan Bagian Untuk sebarang himpunan x dan sebarang pernyataan P(y), ada suatu himpunan yang anggotanya adalah khusus unsur y e x yang memenuhi pernyataan P(y). Aksioma Himpunan Kuasa Semua subhimpunan suatu himpunan membentuk sebuah himpunan. Aksioma Penggantian Peta sebuah himpunan oleh suatu fungsi, adalah sebuah himpunan. Aksioma Dasar, Aksioma Fondasi Untuk tiap himpunan takkosong x, ada himpunan y ∈ x sedemikian sehingga x dan y merupakan himpunan lepas (disjoin). (Aksioma yang
24
sangat teknis ini bertujuan menangkap pengertian bahwa himpunan dibangun secara bertahap dari himpunan yang lebih sederhana. Khususnya, aksioma ini mencegah suatu himpunan dari menjadi anggotanya sendiri.) Aksioma Pemilihan. Axiom of Choice Sebuah anggota dapat dipilih dari tiap himpunan dalam suatu kumpulan himpunan takkosong. Lebih khusus lagi, jika x adalah suatu himpunan, dan tiap anggota dari x adalah himpunan yang takkosong, maka ada suatu fungsi pemilihan, g, sedemikian sehingga g(y) ∈ y untuk tiap y ∈ x.
25
Lampiran II: Himpunan Bilangan Secara intuitif, himpunan adalah kumpulan objek; objek yang terkandung dalam himpunan disebut anggota, unsur, atau elemen himpunan. Beberapa himpunan bilangan dan lambangnya yang sering digunakan dalam matematika adalah yang berikut ini: R : Himpunan bilangan real, Q : Himpunan bilangan rasional, dan Q adalah himpunan semua bilangan yang berbentuk
p dengan p dan q bilangan bulat serta q
q ≠ 0. Z : Himpunan bilangan bulat, dan Z ={..., - 2, -1, 0, 1, 2, ...} N :
Himpunan bilangan asli, atau himpunan bilangan bulat tak negatif, dan N=(0, 1, 2, 3, ...}
Z+ : Himpunan bilangan bulat positif, dan Z+ = {l, 2, 3, ...} Z+ ⊂ N ⊂ Z ⊂ Q ⊂ R
