Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Subbab 1.4 Pembuktian

Subbagian Pratinjau Bagian

Selidiki!
Sebuah teka-teki sudoku mini adalah kisi persegi berukuran \(4\times 4\) yang dibagi menjadi empat kotak \(2\times 2\text{.}\) Tujuannya adalah mengisi setiap petak dengan digit 1 sampai 4 sedemikian rupa sehingga tidak ada digit yang berulang pada baris, kolom, ataupun kotak mana pun.
🔗
Berikut adalah teka-teki sudoku mini sederhana yang dapat Anda coba selesaikan.
🔗
Sudoku 4x4 dengan digit yang telah diberikan.
Anda mungkin memperhatikan bahwa pada solusi teka-teki di atas, keempat sudut luarnya berbeda dan keempat petak tengahnya juga berbeda.
🔗
Tujuan pertanyaan Selidiki! ini adalah membuktikan bahwa hal tersebut bukan kebetulan: Misalkan keempat sudut sebuah teka-teki sudoku mini berisi bilangan yang semuanya berbeda (ditandai dengan # di bawah). Buktikan bahwa keempat petak tengahnya (ditandai dengan * di bawah) juga harus berisi bilangan yang berbeda-beda.
🔗
Sudoku 4x4 dengan digit yang telah diberikan.
🔗

Cobalah 1.4.1.

Cobalah menempatkan bilangan ke dalam teka-teki sudoku mini yang kosong. Lihat apakah Anda dapat menemukan keadaan yang menyangkal pernyataan yang diminta untuk dibuktikan dalam kegiatan Selidiki!. Apa yang menghalangi Anda? Jelaskan secara singkat apakah menurut Anda pernyataan tersebut benar atau salah, beserta alasannya.
🔗
🔗
Siapa pun yang tidak percaya bahwa matematika mengandung kreativitas jelas belum pernah mencoba menulis pembuktian. Menemukan cara untuk meyakinkan dunia bahwa suatu pernyataan tertentu niscaya benar merupakan pekerjaan besar dan sering kali cukup menantang. Tidak ada jalan yang menjamin keberhasilan dalam mencari pembuktian. Sebagai contoh, pada musim panas tahun 1742, seorang matematikawan Jerman bernama Christian Goldbach mempertanyakan apakah setiap bilangan bulat genap yang lebih besar dari 2 dapat dituliskan sebagai jumlah dua bilangan prima. Berabad-abad kemudian, kita masih belum memiliki pembuktian untuk fakta yang tampaknya benar ini (komputer telah memeriksa bahwa konjektur Goldbach berlaku untuk semua bilangan yang kurang dari \(4\times 10^{18}\text{,}\) tetapi belum ditemukan pembuktian bahwa pernyataan tersebut berlaku untuk semua bilangan).
🔗
Menulis pembuktian dapat dikatakan sebagai suatu seni. Seperti seni apa pun, agar benar-benar mahir melakukannya, Anda memerlukan inspirasi sekaligus teknik dasar. Sebagaimana musisi dapat mempelajari penjarian yang tepat dan pelukis dapat mempelajari cara memegang kuas dengan benar, kita dapat mempelajari cara menyusun argumen dengan tepat.
🔗
Kita dapat memandang sebuah pembuktian melalui dua sudut pandang yang berbeda tetapi saling beririsan. Pertama, kita dapat memikirkan struktur logis suatu pembuktian. Di bawah ini kita akan membahas tiga gaya pembuktian yang berbeda tepat pada struktur logisnya. Kedua, kita dapat melihat isi matematis pembuktian tersebut. Bagaimana pembuktian itu menunjukkan pemahaman atas konsep matematika? Apakah definisi objek matematika digunakan dengan benar? Bagaimana definisi-definisi tersebut berinteraksi satu sama lain?
🔗
Ingat bahwa dalam Subbab 1.3 kita mengatakan bahwa tautologi adalah pernyataan yang niscaya benar, tetapi tidak memberi tahu kita sesuatu yang menarik. Demikian pula, jika sebuah pembuktian sepenuhnya bergantung pada bentuk logis pernyataan yang dibuktikannya, pembuktian itu tidak akan memberi tahu kita sesuatu yang menarik tentang matematika. Karena itu, selain struktur logisnya, semua pembuktian yang kita bahas harus melibatkan perpaduan beberapa konsep matematika.
🔗
Dalam bagian ini, kita akan melihat contoh bagaimana interaksi antara struktur logis dan struktur matematis berlangsung. Kita akan memandang struktur logis sebagai kerangka atau perancah pembuktian dan melihat berbagai bentuk yang dapat dimiliki kerangka tersebut. Kemudian kita akan melihat bagaimana isi matematis pembuktian mengisi perincian kerangka itu, yakni bagaimana isi tersebut melengkapinya.
🔗
Sering kali sulit untuk bersikap cermat terhadap pembuktian ketika pernyataan yang hendak kita buktikan tampak terlalu jelas atau terlalu akrab. Meskipun kita tentu ingin membuktikan fakta sederhana tentang bilangan, misalnya bahwa jumlah dua bilangan genap adalah genap, keakraban kita dengan bilangan dapat membuat tugas ini sulit dipandang dengan sungguh-sungguh. Oleh karena itu, kita akan mulai dengan membuktikan beberapa fakta dalam konteks yang mudah-mudahan terasa baru: teka-teki sudoku mini.
🔗

Lembar Kerja Kegiatan Pratinjau

Perhatikan pernyataan berikut:
🔗
Jika \(a b\) merupakan bilangan genap, maka \(a\) atau \(b\) genap.
🔗
🔗
Manakah di antara pembuktian berikut yang tampaknya merupakan pembuktian sahih bagi pernyataan tersebut? Catatan: Anda boleh mengasumsikan bahwa seluruh aljabar di bawah ini benar (karena memang demikian).
🔗
1.
Misalkan \(a\) dan \(b\) ganjil. Artinya, \(a=2k+1\) dan \(b=2m+1\) untuk suatu bilangan bulat \(k\) dan \(m\text{.}\) Maka
\begin{align*} ab \amp =(2k+1)(2m+1)\\ \amp =4km+2k+2m+1\\ \amp =2(2km+k+m)+1\text{.} \end{align*}
🔗
Oleh karena itu, \(ab\) ganjil.
🔗
🔗
2.
Asumsikan bahwa \(a\) atau \(b\) genap—misalkan \(a\) yang genap (kasus ketika \(b\) genap akan identik). Artinya, \(a=2k\) untuk suatu bilangan bulat \(k\text{.}\) Maka
\begin{align*} ab \amp =(2k)b\\ \amp =2(kb)\text{.} \end{align*}
🔗
Dengan demikian, \(ab\) genap.
🔗
🔗
3.
Misalkan \(ab\) genap, tetapi \(a\) dan \(b\) keduanya ganjil. Artinya, \(ab = 2n\text{,}\) \(a=2k+1\text{,}\) dan \(b=2j+1\) untuk suatu bilangan bulat \(n\text{,}\) \(k\text{,}\) dan \(j\text{.}\) Maka
\begin{align*} 2n \amp =(2k+1)(2j+1)\\ 2n \amp =4kj+2k+2j+1\\ n \amp = 2kj+k+j+\frac{1}{2}\text{.} \end{align*}
🔗
Namun, karena \(2kj+k+j\) merupakan bilangan bulat, persamaan ini menyatakan bahwa bilangan bulat \(n\) sama dengan bilangan yang bukan bulat, yang mustahil.
🔗
🔗
4.
Misalkan \(ab\) merupakan bilangan genap, yaitu \(ab=2n\text{,}\) dan \(a\) merupakan bilangan ganjil, yaitu \(a=2k+1\text{.}\)
\begin{align*} ab \amp =(2k+1)b\\ 2n \amp =2kb+b\\ 2n-2kb\amp =b\\ 2(n-kb)\amp =b\text{.} \end{align*}
🔗
Oleh karena itu, \(b\) pasti genap.
🔗
🔗
5.
Manakah di antara pembuktian di atas yang merupakan pembuktian sahih bagi pernyataan tersebut?
🔗
  • Pembuktian 1.
    🔗
  • Pembuktian 2.
    🔗
  • Ini merupakan pembuktian yang sahih, tetapi bukan bagi pernyataan yang diberikan. Pembuktian ini membuktikan hal lain.
  • Pembuktian 3.
    🔗
  • Pembuktian 4.
    🔗
🔗
🔗
🔗

Subbagian Pembuktian Langsung

Gaya pembuktian yang paling sederhana adalah pembuktian langsung. Sering kali, yang diperlukan untuk membuktikan sesuatu hanyalah penjelasan sistematis tentang makna setiap hal yang terlibat. Anda menelaah definisi, menjelaskan dan menguraikan maknanya dengan cermat, hingga terlihat bahwa kesimpulannya benar.
🔗
Untuk menggambarkan pentingnya definisi dalam pembuktian, mari kita berikan beberapa definisi yang cermat tentang teka-teki sudoku mini.
🔗

Definisi 1.4.2. Definisi Sudoku Mini.

Sebuah teka-teki sudoku mini adalah kisi persegi \(4\times 4\) yang terisi sebagian dan dibagi menjadi empat kotak \(2\times 2\text{.}\) Setiap petak dapat kosong atau berisi digit 1 sampai 4.
🔗
Kita mengatakan bahwa sebuah teka-teki sudoku mini valid apabila tidak ada digit 1 sampai 4 yang muncul lebih dari sekali pada baris, kolom, ataupun kotak mana pun.
🔗
Sebuah solusi teka-teki sudoku mini adalah teka-teki valid tanpa petak kosong, dengan setiap petak yang semula tidak kosong tetap tidak berubah.
🔗
Kita mengatakan bahwa sebuah teka-teki sudoku mini dapat diselesaikan secara unik jika tepat terdapat satu solusi.
🔗
🔗
Pertama, mari kita buktikan fakta yang berguna dan “jelas” tentang setiap teka-teki sudoku mini yang valid.
🔗
Itu jelas, kata Anda! Bukankah tepat demikian arti teka-teki yang valid? Ya, teka-teki lengkap yang valid, yaitu yang kita maksud dengan solusi, bukan? Baiklah, tidak persis, karena valid berarti tidak ada digit yang berulang... bukankah itu hal yang sama?
🔗
Ya! Tepat sekali! Menjelaskan hal ini merupakan pembuktian langsung.
🔗

Bukti.

Misalkan Anda memiliki sebuah solusi teka-teki sudoku mini. Artinya, Anda memiliki kisi \(4 \times 4\) yang valid dan setiap petaknya diisi dengan digit 1 sampai 4.
 3 
Definisi solusi
Karena teka-teki tersebut valid, tidak ada digit yang berulang pada baris, kolom, ataupun kotak mana pun
 4 
Definisi valid
. Karena sebuah baris memuat empat bilangan yang tidak berulang dan hanya ada empat digit yang mungkin, setiap digit tersebut harus muncul tepat sekali. Hal ini berlaku untuk setiap baris, setiap kolom, dan setiap kotak.
🔗
Untuk setiap digit, karena digit tersebut muncul tepat sekali dalam empat baris yang berbeda, digit itu muncul tepat empat kali. Dengan demikian, pembuktian selesai.
🔗
🔗

Catatan 1.4.4.

Selain sekadar menjelaskan definisi, pembuktian tersebut memuat satu gagasan matematis penting: Jika empat bilangan berbeda dipilih dari suatu himpunan yang terdiri atas empat bilangan, maka keempat bilangan itu semuanya terpilih. Anda mungkin ingin menjelaskan pula mengapa hal ini benar, atau cukup mengatakan bahwa ini merupakan contoh prinsip sarang merpati (yang akan segera kita jelaskan). Seberapa banyak yang perlu Anda jelaskan bergantung pada siapa pembaca pembuktian Anda. Sedikit sikap waspada ketika menulis pembuktian adalah hal yang baik.
🔗
Memang, dalam kebanyakan konteks, kita bahkan tidak perlu menuliskan pembuktian di atas secara lengkap. Mungkin cukup dikatakan, “Jelas bahwa hal ini mengikuti definisi.” Namun, saat ini kita sedang belajar menulis pembuktian, sehingga bersikap sangat terperinci dapat berguna agar kita dapat berfokus pada struktur pembuktian dan pentingnya menerapkan definisi.
🔗
🔗
Mari kita buktikan sesuatu tentang sebuah teka-teki sudoku tertentu.
🔗

Contoh 1.4.5.

Buktikan bahwa untuk setiap solusi teka-teki sudoku mini di bawah ini, jika solusi tersebut memiliki angka 2 pada petak kiri atas (r1c1), maka solusi itu akan memuat angka 2 pada petak kanan bawah (r4c4).
🔗
Sebuah teka-teki sudoku mini.
Penyelesaian.
Kita tidak tahu apakah teka-teki tersebut dapat diselesaikan secara unik (sebenarnya tidak), meskipun perhatikan bahwa saat ini teka-teki itu valid. Yang ingin kita buktikan adalah bahwa jika angka 2 berada pada petak kiri atas dalam suatu solusi tertentu, maka solusi tersebut memuat angka 2 pada petak kanan bawah.
🔗
Bukti.
Misalkan \(S\) adalah sebuah solusi teka-teki tersebut, dan andaikan \(S\) memuat angka 2 pada petak kiri atas. Karena \(S\) adalah teka-teki yang valid, tidak ada digit yang berulang pada baris, kolom, ataupun kotak mana pun. Perhatikan dahulu baris teratas. Karena baris tersebut sudah memuat 1, 2, dan 3, petak kosong yang tersisa (r1c4) harus berisi 4.
🔗
Sekarang perhatikan kolom 4 (kolom paling kanan). Karena sekarang kita tahu bahwa petak kanan atas berisi 4, kolom ini sudah memuat 1, 3, dan 4. Jadi, petak kosong terakhir (r4c4) harus berisi 2.
🔗
Dengan demikian, \(S\) memuat angka 2 pada petak kanan bawah, sebagaimana yang perlu kita buktikan.
🔗
🔗
🔗
🔗
Perhatikan bentuk umum argumen di atas. Kita berusaha membuktikan suatu implikasi \(P \imp Q\text{:}\) Jika terdapat angka 2 di r1c1, maka terdapat angka 2 di r4c4. Kita mulai dengan mengandaikan bahwa \(P\) benar. Dari sana, kita menyimpulkan sesuatu, lalu dari sesuatu tersebut kita menyimpulkan \(Q\text{.}\) Persis seperti inilah bentuk pembuktian langsung atas implikasi \(P \imp Q\) (dapat pula terdapat lebih banyak langkah di antara \(P\) dan \(Q\)).
🔗
Andaikan \(P\text{.}\) Jelaskan, jelaskan, …, jelaskan. Oleh karena itu, \(Q\text{.}\)
🔗
🔗
Satu pertimbangan tambahan yang perlu kita buat adalah bahwa kita sering membuktikan pernyataan umum dan universal, yakni pernyataan berbentuk \(\forall x (P(x) \imp Q(x))\text{.}\) Untuk menangani kuantor tersebut, kita menetapkan satu instans sembarang dari \(x\text{.}\) Di atas, kita mengatakan, “Misalkan \(S\) adalah sebuah solusi teka-teki tersebut.” Karena kita tidak membuat asumsi tambahan tentang \(S\) selain bahwa \(P\) benar untuknya, kita mengatakan bahwa \(S\) adalah solusi sembarang.
🔗
Jika kita ingin membuktikan bahwa semua persegi adalah persegi panjang, pertama-tama kita menyadari bahwa ini sama dengan mengatakan, “Untuk setiap bangun, jika bangun tersebut adalah persegi, maka bangun itu adalah persegi panjang.” Dalam simbol, \(\forall x (S(x) \imp R(x))\text{.}\) Kita akan mengandaikan bahwa \(P(x)\) benar dan menyimpulkan \(Q(x)\text{.}\) \(x\) yang mana yang kita gunakan? Suatu anggota sembarang, agar pembuktian kita dapat diterapkan pada semua kemungkinan \(x\text{.}\)
🔗

Contoh 1.4.6.

Buktikan bahwa untuk setiap teka-teki sudoku mini dengan tiga petak kosong, jika teka-teki tersebut memiliki solusi, maka teka-teki itu dapat diselesaikan secara unik.
🔗
Penyelesaian.
Apakah ini jelas? Jika sebuah teka-teki memiliki solusi, maka teka-teki itu dapat diselesaikan secara unik, bukan? Sama sekali tidak! Perhatikan kembali Definisi Sudoku Mini: Hanya karena sebuah teka-teki memiliki solusi, tidak berarti teka-teki itu memiliki tepat satu solusi (yaitu, dapat diselesaikan secara unik). Namun, sekalipun kita tidak menganggap hal ini memerlukan pembuktian, mari kita kembali bersikap waspada dan memanfaatkannya sebagai alasan untuk berfokus pada struktur logis pembuktian.
🔗
Perhatikan bahwa kita membuktikan klaim tersebut benar, apa pun teka-teki sudoku mini yang menjadi titik awal kita. Kita mungkin memulai dengan teka-teki ini:
🔗
Sudoku 4x4 dengan hanya satu digit yang belum terisi.
Jelas hanya ada satu cara untuk melengkapi teka-teki tersebut: Baris teratas hanya memiliki satu petak kosong sehingga hanya satu digit yang dapat ditempatkan di sana, lalu kolom 2 dan 3 masing-masing hanya memiliki satu petak kosong sehingga keduanya dapat diisi secara unik.
🔗
Menelaah satu contoh sering kali membantu ketika menyusun pembuktian, tetapi membuktikan pernyataan umum hanya dengan sebuah contoh TIDAK PERNAH merupakan pembuktian yang benar.
🔗
Walaupun terdapat hanya sekitar 152,58 miliar teka-teki sudoku mini (dan sebagian besar tidak valid, lebih sedikit lagi yang memiliki solusi, dan bahkan lebih sedikit lagi yang memiliki tepat satu petak kosong), kita tentu tidak ingin memeriksa semua teka-teki yang mungkin. Sebagai gantinya, kita tetapkan sebuah teka-teki sudoku mini valid yang sembarang. Kita andaikan teka-teki itu memiliki sebuah solusi dan tepat tiga petak kosong. Dari sini, kita buktikan bahwa hanya ada satu solusi yang mungkin.
🔗
Bukti.
Misalkan \(P\) adalah sebuah teka-teki sudoku mini yang sembarang. Andaikan \(P\) memiliki tepat tiga petak kosong dan \(S\) adalah sebuah solusi.
🔗
Karena \(P\) sembarang, kita tidak mengetahui susunan ketiga petak kosong itu. Ketiganya dapat berada pada baris yang berbeda, dua di antaranya dapat berada pada baris yang sama, atau ketiganya dapat berada pada baris yang sama.
🔗
Jika semua petak kosong berada pada baris yang berbeda, maka setiap baris memiliki tepat satu petak kosong. Tiga petak lainnya diisi dengan tiga digit yang berbeda (karena teka-teki itu valid), sehingga hanya ada satu pilihan untuk mengisi petak kosong. Bilangan ini harus sama dengan bilangan yang digunakan dalam solusi \(S\text{.}\)
🔗
Sekarang pertimbangkan kasus ketika dua petak kosong berada pada baris yang sama dan petak ketiga berada pada baris yang berbeda. Baris yang memuat petak kosong ketiga memiliki tiga digit berbeda, sehingga hanya ada satu pilihan untuk petak terakhir, dan isinya harus sama dengan \(S\text{.}\) Setelah petak ini diisi, dua petak kosong lainnya pasti berada pada dua kolom berbeda yang masing-masing memiliki tiga digit terisi. Pada setiap kolom ini, ketiga digit yang telah terisi berbeda, sehingga hanya ada satu pilihan untuk petak kosongnya. Jadi, sekali lagi, setiap solusi harus tepat sama dengan \(S\text{.}\)
🔗
Terakhir, jika ketiga petak kosong berada pada baris yang sama, semuanya berada pada kolom yang berbeda. Jadi, dengan menggunakan argumen yang sama seperti ketika petak-petak kosong berada pada baris yang berbeda, tetapi kali ini menggunakan kolom, kita melihat bahwa \(S\) adalah satu-satunya solusi.
🔗
Kita telah mempertimbangkan semua kasus yang mungkin, dan dalam setiap kasus, \(S\) adalah satu-satunya solusi, sehingga \(P\) dapat diselesaikan secara unik.
🔗
🔗
🔗
🔗
Tentu saja, pembuktian langsung juga dapat digunakan untuk membuktikan pernyataan dalam matematika.
🔗

Contoh 1.4.7.

Buktikan: Untuk semua bilangan bulat \(n\text{,}\) jika \(n\) genap, maka \(n^2\) genap.
🔗
Penyelesaian.
Format pembuktiannya adalah sebagai berikut: Misalkan \(n\) adalah bilangan bulat sembarang. Andaikan \(n\) genap. Jelaskan, jelaskan, jelaskan. Oleh karena itu, \(n^2\) genap.
🔗
Untuk mengisi perinciannya, kita menjelaskan arti \(n\) genap, lalu melihat apa akibatnya bagi \(n^2\text{.}\) Definisi yang relevan di sini adalah, “Suatu bilangan bulat \(n\) disebut genap jika terdapat bilangan bulat \(k\) sedemikian rupa sehingga \(n = 2k\text{.}\)” Berikut adalah pembuktian lengkapnya.
🔗
Bukti.
Misalkan \(n\) adalah bilangan bulat sembarang. Andaikan \(n\) genap. Maka \(n = 2k\) untuk suatu bilangan bulat \(k\text{.}\) Sekarang \(n^2 = (2k)^2 = 4k^2 = 2(2k^2)\text{.}\) Karena \(2k^2\) adalah bilangan bulat, \(n^2\) genap.
🔗
🔗
🔗
🔗

Contoh 1.4.8.

Buktikan: Untuk semua bilangan bulat \(a\text{,}\) \(b\text{,}\) dan \(c\text{,}\) jika \(b\) merupakan kelipatan \(a\) dan \(c\) merupakan kelipatan \(b\text{,}\) maka \(c\) merupakan kelipatan \(a\text{.}\)
🔗
Penyelesaian.
Sekalipun kita tidak ingat persis arti “merupakan kelipatan dari”, kita dapat menyusun pembuktian langsung untuk pernyataan ini. Bentuknya kira-kira seperti ini: Misalkan \(a\text{,}\) \(b\text{,}\) dan \(c\) adalah bilangan bulat sembarang. Andaikan \(b\) merupakan kelipatan \(a\) dan \(c\) merupakan kelipatan \(b\text{.}\) Dan seterusnya. Oleh karena itu, \(c\) merupakan kelipatan \(a\text{.}\)
🔗
Bagaimana kita menghubungkan langkah-langkahnya? Kita nyatakan arti sebenarnya dari hipotesis kita dan mengapa hal itu memberikan arti sebenarnya dari kesimpulan. Di sinilah kita memerlukan definisi \(b\) merupakan kelipatan \(a\): Artinya, \(b = ka\) untuk suatu bilangan bulat \(k\text{.}\) Apa yang ingin kita capai? Bahwa \(c = la\) untuk suatu bilangan bulat \(l\text{.}\) Berikut pembuktian lengkapnya.
🔗
Bukti.
Misalkan \(a\text{,}\) \(b\text{,}\) dan \(c\) adalah bilangan bulat. Andaikan \(b\) merupakan kelipatan \(a\) dan \(c\) merupakan kelipatan \(b\text{.}\) Jadi, terdapat bilangan bulat \(k\) dan \(j\) sedemikian rupa sehingga \(b = ka\) dan \(c = jb\text{.}\) Dengan menggabungkan keduanya (melalui substitusi), kita memperoleh
\begin{equation*} c = j(ka) = (jk)a\text{.} \end{equation*}
Namun, \(jk\) adalah bilangan bulat, sehingga persamaan ini menyatakan bahwa \(c\) merupakan kelipatan \(a\text{.}\)
🔗
🔗
🔗
🔗
🔗

Subbagian Pembuktian melalui Kontraposisi

Ingat bahwa suatu implikasi \(P \imp Q\) ekuivalen secara logis dengan kontraposisinya, \(\neg Q \imp \neg P\text{.}\) Ada banyak contoh pernyataan yang sulit dibuktikan secara langsung, tetapi kontraposisinya dapat dengan mudah dibuktikan menggunakan pembuktian langsung. Itulah tepatnya yang dilakukan pembuktian melalui kontraposisi. Metode ini memberikan pembuktian langsung atas kontraposisi suatu implikasi. Hal tersebut memadai karena kontraposisi ekuivalen secara logis dengan implikasi semula.
🔗
Kerangka pembuktian \(P \imp Q\) melalui kontraposisi akan selalu berbentuk kurang lebih seperti berikut:
🔗
Andaikan \(\neg Q\text{.}\) Jelaskan, jelaskan, … jelaskan. Oleh karena itu, \(\neg P\text{.}\)
🔗
🔗
Seperti sebelumnya, jika terdapat variabel dan kuantor, kita menetapkannya sebagai anggota sembarang dari semesta pembicaraan kita.
🔗

Contoh 1.4.9.

Buktikan bahwa jika sebuah teka-teki sudoku mini dapat diselesaikan secara unik, maka teka-teki tersebut valid.
🔗
Penyelesaian.
Ingat, sebuah teka-teki valid apabila tidak ada baris, kolom, atau kotak yang memuat digit berulang. Sebuah teka-teki dapat diselesaikan secara unik jika terdapat tepat satu solusi, dengan solusi berupa teka-teki valid tanpa petak kosong (yang tidak mengubah petak mana pun yang telah diisi sebelumnya).
🔗
Jika kita mencoba pembuktian langsung, kita akan memulai dengan teka-teki sembarang dan mengandaikan bahwa teka-teki itu dapat diselesaikan secara unik. Kemudian kita dapat “memperoleh” solusinya, tetapi harus menalar mundur ke keadaan awal teka-teki. Hal ini tampak sulit. Sering kali, ketika sebuah pembuktian tampak memerlukan penguraian sesuatu, mencoba kontraposisinya lebih mudah. Itulah yang akan kita lakukan.
🔗
Bukti.
Misalkan \(P\) adalah sebuah teka-teki sudoku mini sembarang dan andaikan teka-teki itu tidak valid. Artinya, pada setidaknya satu baris, satu kolom, atau satu kotak, terdapat suatu digit yang muncul lebih dari sekali.
🔗
Sekarang misalkan kita telah mengisi petak-petak kosong tanpa mengubah petak mana pun yang sebelumnya sudah terisi. Baris, kolom, atau kotak awal yang memuat digit ganda akan tetap memuat pengulangan tersebut, sehingga teka-teki lengkap yang dihasilkan tidak valid. Dengan demikian, tidak ada solusi untuk \(P\text{,}\) sehingga \(P\) tidak dapat diselesaikan secara unik.
🔗
🔗
Kita telah membuktikan bahwa jika sebuah teka-teki sudoku mini tidak valid, maka teka-teki itu tidak dapat diselesaikan secara unik. Ini merupakan kontraposisi dari pernyataan yang ingin kita buktikan, sehingga berfungsi sebagai pembuktian pernyataan semula.
🔗
🔗
🔗
Berikut beberapa contoh lain yang lebih bernuansa matematika.
🔗

Contoh 1.4.10.

Apakah pernyataan “Untuk semua bilangan bulat \(n\text{,}\) jika \(n^2\) genap, maka \(n\) genap” benar?
🔗
Penyelesaian.
Ini adalah konvers dari pernyataan yang kita buktikan dengan pembuktian langsung dalam Contoh 1.4.7 di atas. Setelah mencoba beberapa contoh, pernyataan ini tampaknya benar. Jadi, mari kita buktikan.
🔗
Pembuktian langsung atas pernyataan ini mengharuskan kita menetapkan \(n\) sembarang dan mengandaikan bahwa \(n^2\) genap. Namun, sama sekali tidak jelas bagaimana hal tersebut memungkinkan kita menyimpulkan sesuatu tentang \(n\text{.}\) Fakta bahwa \(n^2 = 2k\) saja tidak menunjukkan bagaimana kita dapat menuliskan \(n\) sebagai kelipatan 2.
🔗
Cobalah pendekatan lain: Tuliskan kontraposisi pernyataan tersebut. Kita memperoleh: untuk semua bilangan bulat \(n\text{,}\) jika \(n\) ganjil, maka \(n^2\) ganjil. Bentuk ini tampak jauh lebih menjanjikan.
🔗
Kita memerlukan definisi bilangan ganjil. Suatu bilangan bulat \(n\) disebut ganjil apabila \(n = 2k+1\) untuk suatu bilangan bulat \(k\text{.}\) Pembuktian kita akan berbentuk kira-kira seperti berikut:
🔗
Misalkan \(n\) adalah bilangan bulat sembarang. Andaikan \(n\) tidak genap. Artinya, …. Dengan kata lain, …. Namun, ini sama dengan mengatakan …. Oleh karena itu, \(n^2\) tidak genap.
🔗
Sekarang kita lengkapi perinciannya.
🔗
Bukti.
Kita akan membuktikan kontraposisinya. Misalkan \(n\) adalah bilangan bulat sembarang. Andaikan \(n\) tidak genap, sehingga bilangan tersebut ganjil. Maka \(n= 2k+1\) untuk suatu bilangan bulat \(k\text{.}\) Sekarang \(n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\text{.}\) Karena \(2k^2 + 2k\) adalah bilangan bulat, kita melihat bahwa \(n^2\) ganjil dan karenanya tidak genap.
🔗
🔗
🔗
🔗

Contoh 1.4.11.

Buktikan bahwa untuk semua bilangan bulat \(a\) dan \(b\text{,}\) jika \(a + b\) ganjil, maka \(a\) ganjil atau \(b\) ganjil.
🔗
Penyelesaian.
Masalah ketika mencoba pembuktian langsung adalah bahwa akan sulit memisahkan \(a\) dan \(b\) hanya dari mengetahui sesuatu tentang \(a+b\text{.}\) Sebaliknya, jika kita mengetahui sesuatu tentang \(a\) dan \(b\) secara terpisah, menggabungkannya mungkin memberi kita informasi tentang \(a+b\text{.}\) Kontraposisi pernyataan yang ingin kita buktikan adalah: untuk semua bilangan bulat \(a\) dan \(b\text{,}\) jika \(a\) dan \(b\) genap, maka \(a+b\) genap. Dengan demikian, pembuktian kita akan memiliki format berikut:
🔗
Misalkan \(a\) dan \(b\) adalah bilangan bulat. Andaikan \(a\) dan \(b\) keduanya genap. Dan seterusnya. Oleh karena itu, \(a+b\) genap.
🔗
Berikut pembuktian lengkapnya.
🔗
Bukti.
Misalkan \(a\) dan \(b\) adalah bilangan bulat. Andaikan \(a\) dan \(b\) genap. Maka \(a = 2k\) dan \(b = 2l\) untuk suatu bilangan bulat \(k\) dan \(l\text{.}\) Sekarang \(a + b = 2k + 2l = 2(k+l)\text{.}\) Karena \(k + l\) adalah bilangan bulat, kita melihat bahwa \(a + b\) genap, sehingga pembuktian selesai.
🔗
🔗
Perhatikan bahwa asumsi kita bahwa \(a\) dan \(b\) genap merupakan negasi dari pernyataan \(a\) ganjil atau \(b\) ganjil. Di sini kita menggunakan hukum De Morgan.
🔗
🔗
🔗
Pembuktian langsung dan pembuktian melalui kontraposisi dapat digunakan ketika membuktikan implikasi. Ingat bahwa beberapa pernyataan yang tidak ditulis secara eksplisit sebagai implikasi dapat dirumuskan ulang menjadi implikasi.
🔗

Contoh 1.4.12.

Pertimbangkan pernyataan, “Untuk setiap bilangan prima \(p\text{,}\) berlaku \(p = 2\) atau \(p\) ganjil.” Kita dapat merumuskannya kembali sebagai, “Untuk setiap bilangan prima \(p\text{,}\) jika \(p \ne 2\text{,}\) maka \(p\) ganjil.” Sekarang cobalah membuktikannya.
🔗
Gunakan definisi bilangan prima berikut: Suatu bilangan bulat \(p \gt 1\) disebut prima apabila memiliki tepat dua faktor, yaitu \(1\) dan \(p\text{.}\)
🔗
Penyelesaian.
Bukti.
Misalkan \(p\) adalah bilangan prima sembarang. Andaikan \(p\) tidak ganjil. Jadi, \(p\) habis dibagi 2. Karena \(p\) prima, bilangan tersebut harus memiliki tepat dua pembagi, dan karena 2 merupakan pembaginya, \(p\) hanya dapat dibagi oleh 1 dan 2. Oleh karena itu, \(p = 2\text{.}\) Dengan demikian, pembuktian selesai (melalui kontraposisi).
🔗
🔗
🔗
🔗
🔗

Subbagian Pembuktian dengan Kontradiksi

Mari mundur sejenak dan pertimbangkan apa artinya jika kesimpulan suatu argumen salah. Ada dua alasan mengapa hal ini dapat terjadi. Logika dalam argumen tersebut keliru, atau setidaknya satu asumsi pasti salah. Pembuktian dengan kontradiksi memanfaatkan kemungkinan kedua ini. Kita memulai dengan satu asumsi dan menyusun pembuktian yang valid menuju kesimpulan yang salah; satu-satunya kemungkinan adalah bahwa asumsi tersebut salah. Kesimpulan yang salah itu disebut “kontradiksi”, yang berarti pernyataan yang niscaya salah (secara teknis, pernyataan berbentuk \(P \wedge \neg P\)).
🔗
Bentuk umum pembuktian dengan kontradiksi untuk membuktikan pernyataan \(P\) adalah
🔗
Andaikan \(\neg P\) (bahwa \(P\) tidak benar). Ini berarti bahwa..., yang memberi tahu kita..., sehingga kita dapat mengatakan... Namun, hal itu merupakan kontradiksi, sehingga \(P\) sebenarnya harus benar.
🔗
🔗
Perhatikan bahwa jika gaya argumen ini kita pandang sebagai pembuktian langsung atas sesuatu, maka ini merupakan pembuktian langsung atas
\begin{equation*} \neg P \imp \text{ kontradiksi}\text{.} \end{equation*}
Jadi, kita memiliki pembuktian yang valid atas implikasi ini. Bagaimana mungkin suatu implikasi yang benar memiliki kesimpulan yang salah? Ingat kembali tabel kebenaran implikasi (Gambar 1.2.2). Satu-satunya baris ketika implikasi bernilai benar tetapi kesimpulannya salah adalah baris 4, dan pada baris ini hipotesisnya juga salah. Jadi, \(\neg P\) salah, yang berarti \(P\) benar.
🔗
Setelah Anda mulai menulis pembuktian dengan kontradiksi, metode ini akan terasa sangat alami. Mari kita lihat caranya melalui sebuah pembuktian sudoku.
🔗

Contoh 1.4.13.

Buktikan bahwa setiap solusi teka-teki sudoku mini di bawah ini harus memuat angka 3 di sudut kanan atas (r1c4).
🔗
Teka-teki sudoku 4x4.
Penyelesaian.
Ada beberapa cara untuk membuktikan hal ini, sebagaimana sering terjadi pada pembuktian dengan kontradiksi. Walaupun kita selalu memulai dengan asumsi awal yang sama (lawan dari yang ingin kita buktikan), letak ditemukannya kontradiksi dapat berbeda-beda.
🔗
Bukti.
Misalkan \(S\) adalah sebuah solusi teka-teki tersebut, tetapi andaikan \(S\) tidak memuat angka 3 di sudut kanan atas. Maka baris teratas harus memuat angka 3 di tempat lain. Angka itu tidak dapat berada di kolom 1 karena kolom tersebut sudah memuat angka 3. Angka itu tidak dapat berada di kolom 2 karena petak tersebut sudah terisi (dengan angka 2). Angka itu juga tidak dapat berada di kolom 3 karena jika demikian, tidak akan ada tempat untuk menaruh angka 3 pada baris terbawah. Jadi, baris teratas tidak akan memuat angka 3, bertentangan dengan fakta bahwa \(S\) adalah sebuah solusi.
🔗
Oleh karena itu, \(S\) harus memuat angka 3 di sudut kanan atas.
🔗
🔗
🔗
🔗

Contoh 1.4.14.

Buktikan bahwa tidak ada solusi untuk teka-teki sudoku di bawah ini.
🔗
Sebuah teka-teki sudoku mini
Penyelesaian.
Perhatikan bentuk logis pernyataan ini:
\begin{equation*} \neg \exists S (S \text{ adalah suatu solusi })\text{.} \end{equation*}
Dengan menggunakan aturan negasi kuantor, bentuk ini sama dengan
\begin{equation*} \forall S (S \text{ bukan suatu solusi})\text{.} \end{equation*}
Jika kita membuktikannya secara langsung, kita perlu mempertimbangkan semua solusi yang mungkin dan menunjukkan bahwa semuanya tidak valid. Hal itu tampak cukup menantang.
🔗
Sebaliknya, jika kita mencoba pembuktian dengan kontradiksi, kita dapat mengandaikan negasi pernyataan yang diminta untuk dibuktikan. Artinya, kita dapat mengandaikan bahwa terdapat sebuah solusi. Itu adalah satu solusi yang dapat kita gunakan untuk bernalar. Jauh lebih mudah ditangani.
🔗
Bukti.
Andaikan, demi memperoleh kontradiksi, bahwa memang terdapat sebuah solusi teka-teki tersebut. Solusi ini harus memiliki angka 4 pada kotak kiri bawah. Namun, satu-satunya petak yang dapat memuat angka 4 berada di baris 4 atau kolom 1 (atau keduanya). Dalam kedua kemungkinan tersebut, hal ini bertentangan dengan fakta bahwa sudah terdapat angka 4 di kolom 1 dan baris 4.
🔗
🔗
🔗
🔗
Berikut tiga contoh pembuktian dengan kontradiksi tentang bilangan:
🔗

Contoh 1.4.15.

Buktikan bahwa \(\sqrt{2}\) irasional.
🔗
Penyelesaian.
Bukti.
Andaikan tidak demikian. Maka \(\sqrt 2\) sama dengan pecahan \(\frac{a}{b}\text{.}\) Tanpa mengurangi keumuman, andaikan \(\frac{a}{b}\) sudah dalam bentuk paling sederhana (jika tidak, sederhanakan pecahan tersebut). Jadi,
\begin{equation*} 2 = \frac{a^2}{b^2} \end{equation*}
\begin{equation*} 2b^2 = a^2\text{.} \end{equation*}
🔗
Dengan demikian, \(a^2\) genap, sehingga \(a\) genap. Jadi, \(a = 2k\) untuk suatu bilangan bulat \(k\text{,}\) dan \(a^2 = 4k^2\text{.}\) Kemudian kita memperoleh,
\begin{equation*} 2b^2 = 4k^2 \end{equation*}
\begin{equation*} b^2 = 2k^2\text{.} \end{equation*}
🔗
Dengan demikian, \(b^2\) genap, sehingga \(b\) genap. Karena \(a\) juga genap, kita melihat bahwa \(\frac{a}{b}\) tidak berada dalam bentuk paling sederhana, suatu kontradiksi. Dengan demikian, \(\sqrt 2\) irasional.
🔗
🔗
🔗
🔗

Contoh 1.4.16.

Buktikan: Tidak ada bilangan bulat \(x\) dan \(y\) sedemikian rupa sehingga \(x^2 = 4y + 2\text{.}\)
🔗
Penyelesaian.
Bukti.
Kita menggunakan pembuktian dengan kontradiksi. Jadi, andaikan memang terdapat bilangan bulat \(x\) dan \(y\) sedemikian rupa sehingga \(x^2 = 4y + 2 = 2(2y + 1)\text{.}\) Maka \(x^2\) genap. Kita telah melihat bahwa hal ini mengakibatkan \(x\) genap. Jadi, \(x = 2k\) untuk suatu bilangan bulat \(k\text{.}\) Maka \(x^2 = 4k^2\text{.}\) Selanjutnya, hal ini memberikan \(2k^2 = (2y + 1)\text{.}\) Namun, \(2k^2\) genap dan \(2y + 1\) ganjil, sehingga keduanya tidak mungkin sama. Dengan demikian, kita memperoleh kontradiksi, sehingga tidak mungkin terdapat bilangan bulat \(x\) dan \(y\) sedemikian rupa sehingga \(x^2 = 4y + 2\text{.}\)
🔗
🔗
🔗
🔗

Contoh 1.4.17.

Prinsip Sarang Merpati: Jika lebih dari \(n\) merpati terbang memasuki \(n\) kandang, maka setidaknya satu kandang akan memuat sedikitnya dua merpati. Buktikan pernyataan ini!
🔗
Penyelesaian.
Bukti.
Andaikan, berlawanan dengan ketentuan, bahwa setiap kandang memuat paling banyak satu merpati. Maka paling banyak terdapat \(n\) merpati. Namun, kita mengandaikan bahwa terdapat lebih dari \(n\) merpati, sehingga hal ini mustahil. Dengan demikian, pasti ada sebuah kandang yang memuat lebih dari satu merpati.
🔗
🔗
Walaupun kita merumuskan pembuktian ini sebagai pembuktian dengan kontradiksi, kita juga dapat menggunakan pembuktian melalui kontraposisi karena kontradiksi kita hanyalah negasi dari hipotesis. Kadang-kadang hal ini terjadi; dalam kasus demikian, Anda dapat menggunakan salah satu gaya pembuktian. Namun, ada pula contoh ketika kontradiksi muncul “jauh” dari pernyataan semula.
🔗
🔗
🔗
🔗

Subbagian Ringkasan Gaya Pembuktian

Kita telah membahas tiga gaya pembuktian: pembuktian langsung, pembuktian melalui kontraposisi, dan pembuktian dengan kontradiksi. Menentukan gaya pembuktian yang akan digunakan untuk suatu masalah dapat menjadi tantangan, dan tidak ada aturan yang selalu dapat memberi tahu kita apa yang harus dilakukan. Sering kali terdapat beberapa cara untuk melanjutkan suatu pembuktian, dan inilah salah satu alasan matematika begitu menarik.
🔗
Titik awal yang baik ketika menulis pembuktian adalah mempertimbangkan asumsi awal untuk setiap gaya dan kesimpulan yang hendak dicapai. Pembuktian agak menyerupai permainan labirin pada menu anak-anak. Ada MULAI dan KELUAR, dan tujuan Anda adalah menemukan jalan dari satu titik ke titik lainnya. Kadang-kadang, memulai dari kedua sisi dan berharap bertemu di tengah dapat membantu.
🔗

Awal dan Akhir Pembuktian.

Untuk membuktikan implikasi \(P \imp Q\text{:}\)
Langsung
🔗
Awal: Andaikan \(P\text{.}\)
🔗
Akhir: Oleh karena itu, \(Q\text{.}\)
🔗
Kontraposisi
🔗
Awal: Andaikan \(\neg Q\text{.}\)
🔗
Akhir: Oleh karena itu, \(\neg P\text{.}\)
🔗
Kontradiksi
🔗
Awal: Andaikan \(\neg (P \imp Q)\text{.}\)
🔗
Akhir: ...yang merupakan suatu kontradiksi.
🔗
🔗
🔗
Anda dapat menggunakan pembuktian dengan kontradiksi sekalipun tidak sedang mencoba membuktikan suatu implikasi. Namun, jika pernyataannya merupakan implikasi, mengandaikan \(\neg (P \imp Q)\) sangatlah ampuh. Ingat, satu-satunya cara suatu implikasi bernilai salah adalah ketika \(P\) benar dan \(Q\) salah. Jadi, sebenarnya kita mengandaikan \(P \wedge \neg Q\text{.}\) Aha! \(P\) adalah yang kita andaikan dalam pembuktian langsung. \(\neg Q\) adalah yang kita andaikan dalam pembuktian melalui kontraposisi. Jadi, pembuktian dengan kontradiksi seperti melakukan kedua pembuktian lainnya secara bersamaan, lalu bertemu di tengah!
🔗
Untuk menggambarkan hal ini, mari kita buktikan fakta dari kegiatan Selidiki!. Kita akan membuktikan bahwa jika sudut-sudut sebuah teka-teki sudoku mini berisi bilangan yang semuanya berbeda (ditandai dengan \(a\) sampai \(d\) di bawah), maka keempat petak tengahnya (ditandai dengan * di bawah) juga harus berisi bilangan yang berbeda-beda (dalam setiap solusi).
🔗
Sudoku 4x4 dengan digit yang telah diberikan.
Kita akan memberikan tiga pembuktian: pertama pembuktian langsung, kemudian pembuktian melalui kontraposisi, dan terakhir pembuktian dengan kontradiksi.
🔗

Bukti.

Misalkan \(P\) adalah sebuah teka-teki sudoku dengan bilangan yang semuanya berbeda di sudut-sudutnya: \(a\) di kiri atas, \(b\) di kanan atas, \(c\) di kiri bawah, dan \(d\) di kanan bawah. Misalkan \(S\) adalah sembarang solusi teka-teki tersebut.
🔗
Dalam \(S\text{,}\) digit apa pun yang dilambangkan oleh \(a\) harus muncul di baris 2. Karena \(a\) sudah berada di kotak kiri atas, digit itu tidak dapat muncul di kolom 1 atau 2, sehingga harus muncul di kolom 3 atau 4. Jika berada di kolom 3, maka \(a\) muncul di salah satu petak tengah. Jika tidak, digit itu berada di kolom 4. Dalam kasus terakhir ini, kita menanyakan tempat \(a\) muncul di baris 3: Digit itu tidak dapat berada di kolom 1 atau 4, sehingga harus berada di kolom 2 atau 3, dan dengan demikian berada di salah satu petak tengah.
🔗
Argumen yang sama kini dapat diterapkan pada masing-masing dari tiga petak luar lainnya. Dengan demikian, dalam setiap solusi teka-teki tersebut, keempat petak tengah harus memuat digit \(a\) sampai \(d\text{,}\) yang semuanya berbeda.
🔗
🔗
Sekarang kita akan membuktikan pernyataan yang sama melalui kontraposisi.
🔗

Bukti.

Misalkan \(P\) adalah sebuah teka-teki sudoku mini dengan bilangan pada sudut-sudutnya. Misalkan \(S\) adalah sembarang solusi teka-teki tersebut. Andaikan keempat petak tengah dalam \(S\) tidak memuat bilangan yang semuanya berbeda. Maka pasti ada suatu bilangan yang sama, misalkan \(n\text{,}\) pada dua petak tengah.
🔗
Karena \(n\) tidak dapat muncul dua kali dalam satu baris, \(n\) harus berada pada dua petak tengah yang saling berhadapan secara diagonal: di r2c2 dan r3c3, atau di r2c3 dan r3c2. Dalam kedua kasus tersebut, di manakah \(n\) dapat berada pada baris 1 dan 4? Digit itu tidak dapat berada di kolom 2 atau 3, sehingga harus berada di kolom 1 dan 4. Artinya, \(n\) akan berada pada sudut luar yang saling berhadapan, sehingga digit pada keempat sudut tidak semuanya berbeda.
🔗
🔗
Terakhir, kita akan membuktikan pernyataan yang sama dengan kontradiksi.
🔗

Bukti.

Misalkan \(P\) adalah sebuah teka-teki sudoku mini dan andaikan keempat sudut luarnya semuanya berbeda, tetapi dalam suatu solusi \(S\text{,}\) keempat petak tengahnya tidak semuanya berbeda.
🔗
Andaikan \(a\text{,}\) digit di sudut kiri atas, muncul dua kali dalam keempat petak tengah. Satu-satunya cara hal ini dapat terjadi adalah jika \(a\) muncul di r3c2 dan r2c3, seperti ditunjukkan di bawah.
🔗
Sudoku mini yang terisi sebagian.
Namun sekarang, di mana kemunculan keempat \(a\) dapat ditempatkan dalam solusi? Digit itu harus berada di r4c4, bertentangan dengan fakta bahwa keempat sudut semuanya berbeda. Argumen yang serupa menghasilkan kontradiksi untuk setiap kemungkinan digit sudut luar lainnya yang berulang di bagian tengah. Dengan demikian, keempat petak tengah harus memuat bilangan yang semuanya berbeda.
🔗
🔗
🔗

Pertanyaan Bacaan Pertanyaan Bacaan

1.

Manakah di antara berikut ini yang merupakan baris pertama terbaik untuk suatu pembuktian langsung jika Anda ingin membuktikan pernyataan, “Untuk semua himpunan \(A\) yang beranggotakan bilangan satu digit, jika \(|A| = 6\text{,}\) maka \(A\) memuat suatu bilangan genap.”
🔗
  • Andaikan terdapat suatu himpunan \(A\) yang beranggotakan bilangan satu digit dengan \(|A| = 6\text{,}\) tetapi hanya memuat bilangan ganjil.
    🔗
  • Salah. Pembuktian langsung dimulai dengan mengandaikan hipotesis dari implikasi yang ingin Anda buktikan. Coba lagi.
  • Tetapkan suatu himpunan sembarang \(A\) yang beranggotakan bilangan satu digit, dan andaikan \(|A| = 6\text{.}\)
    🔗
  • Benar! Pembuktian langsung dimulai dengan mengandaikan hipotesis dari implikasi yang ingin Anda buktikan.
  • Andaikan \(A\) adalah suatu himpunan yang beranggotakan bilangan satu digit dengan \(|A| \ne 6\text{.}\)
    🔗
  • Salah. Apa bagian “jika” dari pernyataan yang sedang Anda coba buktikan? Coba lagi.
  • Misalkan \(A\) adalah suatu himpunan yang beranggotakan bilangan satu digit dan memuat suatu bilangan genap.
    🔗
  • Salah. Coba lagi.
  • Misalkan \(A\) adalah suatu himpunan yang beranggotakan bilangan satu digit, dan andaikan \(A\) tidak memuat bilangan genap apa pun.
    🔗
  • Salah. Coba lagi.
🔗

2.

Manakah di antara berikut ini yang merupakan baris pertama terbaik untuk suatu pembuktian melalui kontraposisi jika Anda ingin membuktikan pernyataan, “Untuk semua himpunan \(A\) yang beranggotakan bilangan satu digit, jika \(|A| = 6\text{,}\) maka \(A\) memuat suatu bilangan genap.”
🔗
  • Andaikan terdapat suatu himpunan \(A\) yang beranggotakan bilangan satu digit dengan \(|A| = 6\text{,}\) tetapi hanya memuat bilangan ganjil.
    🔗
  • Salah. Apa kontraposisi dari pernyataan yang sedang kita coba buktikan? Coba lagi.
  • Tetapkan suatu himpunan sembarang \(A\) yang beranggotakan bilangan satu digit, dan andaikan \(|A| = 6\text{.}\)
    🔗
  • Salah. Kita sedang mencoba membuktikan kontraposisi, jadi andaikan bagian jika dari kontraposisi tersebut. Coba lagi.
  • Andaikan \(A\) adalah suatu himpunan yang beranggotakan bilangan satu digit dengan \(|A| \ne 6\text{.}\)
    🔗
  • Salah. Kontraposisi dari \(P \imp Q\) adalah \(\neg Q \imp \neg P\text{.}\) Pembuktian melalui kontraposisi harus dimulai dengan mengandaikan \(\neg Q\text{.}\) Coba lagi.
  • Misalkan \(A\) adalah suatu himpunan yang beranggotakan bilangan satu digit dan memuat suatu bilangan genap.
    🔗
  • Salah. Kontraposisi dari \(P \imp Q\) adalah \(\neg Q \imp \neg P\text{.}\) Pembuktian melalui kontraposisi harus dimulai dengan mengandaikan \(\neg Q\text{.}\) Coba lagi.
  • Misalkan \(A\) adalah suatu himpunan yang beranggotakan bilangan satu digit, dan andaikan \(A\) tidak memuat bilangan genap apa pun.
    🔗
  • Benar!
🔗

3.

Manakah di antara berikut ini yang merupakan baris pertama terbaik untuk suatu pembuktian dengan kontradiksi jika Anda ingin membuktikan pernyataan, “Untuk semua himpunan \(A\) yang beranggotakan bilangan satu digit, jika \(|A| = 6\text{,}\) maka \(A\) memuat suatu bilangan genap.”
🔗
  • Andaikan terdapat suatu himpunan \(A\) yang beranggotakan bilangan satu digit dengan \(|A| = 6\text{,}\) tetapi hanya memuat bilangan ganjil.
    🔗
  • Benar! Ini merupakan negasi dari pernyataan yang sedang kita coba buktikan.
  • Tetapkan suatu himpunan sembarang \(A\) yang beranggotakan bilangan satu digit, dan andaikan \(|A| = 6\text{.}\)
    🔗
  • Salah. Pembuktian dengan kontradiksi harus dimulai dengan mengandaikan negasi dari pernyataan yang sedang kita coba buktikan. Coba lagi.
  • Andaikan \(A\) adalah suatu himpunan yang beranggotakan bilangan satu digit dengan \(|A| \ne 6\text{.}\)
    🔗
  • Salah. Pembuktian dengan kontradiksi harus dimulai dengan mengandaikan negasi dari pernyataan yang sedang kita coba buktikan. Coba lagi.
  • Misalkan \(A\) adalah suatu himpunan yang beranggotakan bilangan satu digit dan memuat suatu bilangan genap.
    🔗
  • Salah. Pembuktian dengan kontradiksi harus dimulai dengan mengandaikan negasi dari pernyataan yang sedang kita coba buktikan. Coba lagi.
  • Misalkan \(A\) adalah suatu himpunan yang beranggotakan bilangan satu digit, dan andaikan \(A\) tidak memuat bilangan genap apa pun.
    🔗
  • Salah. Pembuktian dengan kontradiksi harus dimulai dengan mengandaikan negasi dari pernyataan yang sedang kita coba buktikan. Coba lagi.
🔗

4.

Pertanyaan apa yang Anda miliki setelah membaca bagian ini? Tuliskan setidaknya satu pertanyaan tentang isi bagian ini yang membuat Anda ingin tahu.
🔗
🔗
🔗

Latihan Soal Latihan

1.

Susunlah beberapa pernyataan di bawah ini untuk membentuk pembuktian yang benar bagi pernyataan berikut: “Untuk setiap bilangan bulat \(n\text{,}\) jika \(n\) genap, maka \(7n\) genap.”
🔗
🔗

2.

Susunlah beberapa pernyataan di bawah ini untuk membentuk pembuktian yang benar bagi pernyataan berikut: “Untuk setiap bilangan bulat \(n\text{,}\) jika \(7n\) genap, maka \(n\) genap.”
🔗
🔗

3.

Perhatikan pernyataan berikut: “Untuk setiap bilangan bulat \(a\) dan \(b\text{,}\) jika \(a+b\) ganjil, maka \(a\) atau \(b\) ganjil”.
🔗
Berikan pembuktian yang sah bagi pernyataan tersebut dengan menggunakan pembuktian melalui kontraposisi. Susunlah beberapa pernyataan di bawah ini untuk melengkapi pembuktiannya.
🔗
🔗

4.

Perhatikan kembali pernyataan berikut: “Untuk setiap bilangan bulat \(a\) dan \(b\text{,}\) jika \(a+b\) ganjil, maka \(a\) atau \(b\) ganjil.”
🔗
Kali ini, berikan pembuktian yang sah bagi pernyataan tersebut dengan menggunakan pembuktian melalui kontradiksi dan beberapa pernyataan di bawah ini.
🔗
🔗

5.

Di bawah ini terdapat tiga pernyataan beserta salah satu kemungkinan baris pertama pembuktian untuk pernyataan tersebut. Dalam setiap kasus, tentukan apakah baris pertama itu merupakan awal pembuktian langsung, pembuktian melalui kontraposisi, atau pembuktian dengan kontradiksi.
🔗
  1. Pernyataan: Untuk setiap segitiga, jumlah sudut dalamnya adalah 180 derajat.
    🔗
    Baris pertama: Perhatikan suatu bangun datar dan asumsikan jumlah sudut dalamnya bukan 180 derajat.
    🔗
    🔗
  2. Pernyataan: Jika suatu bangun merupakan segi lima, maka jumlah sudut dalamnya adalah 480 derajat.
    🔗
    Baris pertama: Perhatikan sembarang bangun, dan asumsikan bangun tersebut merupakan segi lima.
    🔗
    🔗
  3. Pernyataan: Untuk setiap segitiga, jumlah sudut dalamnya adalah 180 derajat.
    🔗
    Baris pertama: Andaikan ada segitiga yang jumlah sudut dalamnya tidak sama dengan 180 derajat
    🔗
    🔗
🔗
🔗

6.

🔗
🔗

Latihan Latihan Tambahan

1.

Untuk suatu predikat \(P(x)\text{,}\) Anda mungkin menduga bahwa pernyataan \(\forall x P(x)\) atau \(\exists x P(x)\) bernilai benar atau salah. Bagaimana Anda dapat menentukan apakah dugaan Anda benar dalam setiap kasus? Ada empat kemungkinan tindakan: Anda dapat memberikan contoh suatu elemen \(n\) dalam semesta pembicaraan yang membuat \(P(n)\) benar atau yang membuat \(P(n)\) salah, atau Anda dapat menunjukkan bahwa apa pun \(n\) yang dipilih, \(P(n)\) selalu benar atau selalu salah.
  1. Apa yang perlu Anda lakukan untuk membuktikan bahwa \(\forall x P(x)\) benar?
    🔗
    🔗
  2. Apa yang perlu Anda lakukan untuk membuktikan bahwa \(\forall x P(x)\) salah?
    🔗
    🔗
  3. Apa yang perlu Anda lakukan untuk membuktikan bahwa \(\exists x P(x)\) benar?
    🔗
    🔗
  4. Apa yang perlu Anda lakukan untuk membuktikan bahwa \(\exists x P(x)\) salah?
    🔗
    🔗
🔗
🔗

2.

Perhatikan pernyataan berikut: “Untuk semua bilangan bulat \(a\) dan \(b\text{,}\) jika \(a + b\) genap, maka \(a\) dan \(b\) genap.”
  1. Tuliskan kontraposisi pernyataan tersebut.
    🔗
    🔗
  2. Tuliskan konvers pernyataan tersebut.
    🔗
    🔗
  3. Tuliskan negasi pernyataan tersebut.
    🔗
    🔗
  4. Apakah pernyataan semula benar atau salah? Buktikan jawaban Anda.
    🔗
    🔗
  5. Apakah kontraposisi dari pernyataan semula benar atau salah? Buktikan jawaban Anda.
    🔗
    🔗
  6. Apakah konvers dari pernyataan semula benar atau salah? Buktikan jawaban Anda.
    🔗
    🔗
  7. Apakah negasi dari pernyataan semula benar atau salah? Buktikan jawaban Anda.
    🔗
    🔗
🔗
🔗

3.

Untuk setiap pernyataan di bawah ini, tentukan metode pembuktian yang sebaiknya digunakan. Kemudian jelaskan bagaimana pembuktiannya dimulai dan diakhiri. Anda mendapat nilai bonus jika dapat melengkapi bagian tengahnya.
  1. Tidak ada bilangan bulat \(x\) dan \(y\) sedemikian sehingga \(x\) merupakan bilangan prima yang lebih besar dari 5 dan \(x = 6y + 3\text{.}\)
    🔗
    🔗
  2. Untuk semua bilangan bulat \(n\text{,}\) jika \(n\) merupakan kelipatan 3, maka \(n\) dapat ditulis sebagai jumlah bilangan bulat berurutan.
    🔗
    🔗
  3. Untuk semua bilangan bulat \(a\) dan \(b\text{,}\) jika \(a^2 + b^2\) ganjil, maka \(a\) atau \(b\) ganjil.
    🔗
    🔗
🔗
🔗

4.

Perhatikan pernyataan berikut: “Untuk semua bilangan bulat \(n\text{,}\) jika \(n\) genap, maka \(8n\) genap.”
  1. Buktikan pernyataan tersebut. Jenis pembuktian apa yang Anda gunakan?
    🔗
    🔗
  2. Apakah konversnya benar? Buktikan atau berikan contoh penyangkal.
    🔗
    🔗
🔗
🔗

5.

Permainan TENZI menggunakan 40 dadu bersisi enam (masing-masing bernomor 1 sampai 6). Misalkan Anda melempar ke-40 dadu tersebut.
  1. Buktikan bahwa sedikitnya tujuh dadu akan menunjukkan angka yang sama.
    🔗
  2. Berapa banyak dadu yang harus Anda lempar agar dijamin terdapat empat dadu yang semuanya menunjukkan angka yang sama atau semuanya menunjukkan angka berbeda? Buktikan jawaban Anda.
    🔗
    🔗
🔗
🔗

6.

Buktikan bahwa untuk semua bilangan bulat \(n\text{,}\) \(n\) genap jika dan hanya jika \(3n\) genap. Artinya, buktikan kedua implikasi berikut: Jika \(n\) genap, maka \(3n\) genap, dan jika \(3n\) genap, maka \(n\) genap.
🔗
Petunjuk.
Salah satu implikasi dapat dibuktikan secara langsung; implikasi lainnya dapat dibuktikan melalui kontraposisi.
🔗
🔗
🔗

7.

Buktikan bahwa \(\sqrt 3\) merupakan bilangan irasional.
🔗
Petunjuk.
Soal ini pada dasarnya meminta Anda memodifikasi pembuktian bahwa \(\sqrt{2}\) merupakan bilangan irasional. Dalam pembuktian tersebut Anda menunjukkan bahwa bilangan-bilangan tertentu genap; di sini Anda akan menunjukkan bahwa bilangan-bilangan tersebut merupakan kelipatan 3.
🔗
🔗
🔗

8.

Perhatikan pernyataan berikut: “Untuk semua bilangan bulat \(a\) dan \(b\text{,}\) jika \(a\) genap dan \(b\) merupakan kelipatan 3, maka \(ab\) merupakan kelipatan 6.”
  1. Buktikan pernyataan tersebut. Jenis pembuktian apa yang Anda gunakan?
    🔗
    🔗
  2. Nyatakan konversnya. Apakah konvers tersebut benar? Buktikan atau berikan contoh penyangkal.
    🔗
    🔗
🔗
Petunjuk.
Bagian (a) dapat dibuktikan dengan pembuktian langsung yang relatif mudah. Carilah contoh penyangkal untuk bagian (b).
🔗
🔗
🔗

9.

Buktikan pernyataan berikut: “Untuk semua bilangan bulat \(n\text{,}\) jika \(5n\) ganjil, maka \(n\) ganjil.” Nyatakan dengan jelas metode pembuktian yang Anda gunakan.
🔗
🔗

10.

Buktikan pernyataan berikut: “Untuk semua bilangan bulat \(a\text{,}\) \(b\text{,}\) dan \(c\text{,}\) jika \(a^2 + b^2 = c^2\text{,}\) maka \(a\) atau \(b\) genap.”
🔗
Petunjuk.
Pembuktian dengan kontradiksi cocok digunakan di sini karena Anda dapat mengasumsikan bahwa \(a\) dan \(b\) keduanya ganjil. Simpulkan bahwa \(c^2\) genap dan karena itu merupakan kelipatan 4 (mengapa? dan mengapa hal tersebut merupakan kontradiksi?).
🔗
🔗
🔗

11.

Misalkan Anda ingin membuktikan implikasi berikut:
🔗
Untuk semua bilangan asli \(n\text{,}\) jika \(n\) prima, maka \(n\) soliter.
🔗
🔗
Tuliskan bagian awal dan akhir argumen jika Anda membuktikan pernyataan tersebut:
  1. Secara langsung
    🔗
    🔗
  2. Melalui kontraposisi
    🔗
    🔗
  3. Dengan kontradiksi
    🔗
    🔗
🔗
Anda tidak perlu menuliskan bagian tengah pembuktian (karena Anda tidak mengetahui arti soliter). Namun, pastikan Anda memberikan beberapa baris pertama dan terakhir agar struktur logis pembuktian yang Anda gunakan terlihat jelas.
🔗
🔗

12.

Misalkan Anda memiliki koleksi prangko langka bernilai 5 sen dan 8 sen. Anda harus segera mengirim surat dan, karena tidak memiliki prangko lain, memutuskan menggunakan sebagian koleksi tersebut. Pertanyaannya, berapa nilai biaya kirim yang dapat Anda susun?
  1. Buktikan bahwa jika Anda menggunakan prangko dari kedua jenis masing-masing dalam jumlah genap, nilai biaya kirim yang diperoleh pasti genap.
    🔗
    🔗
  2. Misalkan Anda memperoleh nilai biaya kirim yang genap. Buktikan bahwa sedikitnya salah satu jenis prangko digunakan dalam jumlah genap.
    🔗
    🔗
  3. Misalkan Anda memperoleh biaya kirim tepat 72 sen. Buktikan bahwa sedikitnya 6 prangko dari salah satu jenis telah digunakan.
    🔗
    🔗
🔗
Petunjuk.
Gunakan metode pembuktian yang berbeda untuk setiap bagian.
🔗
🔗
🔗

13.

Buktikan bahwa \(x=y\) jika dan hanya jika \(xy=\dfrac{(x+y)^2}{4}\text{.}\) Perhatikan bahwa Anda perlu membuktikan dua “arah”, yaitu bagian “jika” dan bagian “hanya jika”.
🔗
🔗

14.

Buktikan bahwa \(\log(7)\) merupakan bilangan irasional.
🔗
Petunjuk.
Perhatikan bahwa jika \(\log(7) = \frac{a}{b}\text{,}\) maka \(7 = 10^\frac{a}{b}\text{.}\) Dapatkah suatu pangkat dari 7 sama dengan suatu pangkat dari 10?
🔗
🔗
🔗

15.

Buktikan bahwa persamaan \(x^2 = 4y + 3\) tidak memiliki solusi bilangan bulat.
🔗
Petunjuk.
Bagaimana jika solusi semacam itu ada? Simpulkan bahwa \(x\) harus ganjil, lalu lanjutkan hingga memperoleh kontradiksi.
🔗
🔗
🔗

16.

Buktikan bahwa setiap bilangan prima yang lebih besar dari 3 bernilai satu lebih besar atau satu lebih kecil daripada suatu kelipatan 6.
🔗
Petunjuk.
Buktikan kontraposisinya dengan pembuktian per kasus. Terdapat 4 kasus yang perlu diperhatikan.
🔗
🔗
🔗

17.

“Teman” Anda menunjukkan sebuah “pembuktian” yang ia tulis untuk menunjukkan bahwa \(1 = 3\text{.}\) Berikut pembuktiannya:
🔗
Bukti.
Saya mengklaim bahwa \(1 = 3\text{.}\) Tentu saja kita boleh melakukan operasi apa pun pada satu ruas persamaan asalkan melakukan operasi yang sama pada ruas lainnya. Jadi, kurangi kedua ruas dengan 2. Kita memperoleh \(-1 = 1\text{.}\) Sekarang kuadratkan kedua ruas untuk memperoleh \(1 = 1\text{.}\) Kita semua sepakat bahwa persamaan ini benar.
🔗
🔗
Apa yang sebenarnya terjadi? Apakah argumen teman Anda sah? Apakah argumen tersebut merupakan pembuktian bagi klaim \(1=3\text{?}\) Jelaskan dengan cermat berdasarkan pengetahuan kita tentang logika.
🔗
Petunjuk.
Pembuktian teman Anda memang membuktikan sesuatu, tetapi apa? Implikasi apa yang mengikuti dari pembuktian tersebut? Apakah hal itu membantu?
🔗
🔗
🔗

18.

Satu set kartu remi standar berisi 52 kartu yang terdiri atas 4 jenis (hati, wajik, sekop, dan keriting), masing-masing dengan 13 nilai berbeda (As, 2, 3, …, 10, J, Q, K). Jika Anda mengambil sejumlah kartu secara acak, Anda mungkin memperoleh atau tidak memperoleh sepasang kartu (dua kartu dengan nilai yang sama) ataupun tiga kartu dari jenis yang sama. Namun, jika Anda mengambil cukup banyak kartu, keberadaan susunan tersebut dapat dijamin. Untuk setiap kondisi berikut, tentukan jumlah minimum kartu yang perlu diambil agar kartu-kartu yang diminta pasti diperoleh. Buktikan jawaban Anda.
  1. Tiga kartu bernilai sama (misalnya, tiga kartu bernilai 7).
    🔗
    🔗
  2. Lima kartu berjenis sama (misalnya, lima kartu hati).
    🔗
    🔗
  3. Tiga kartu yang semuanya berjenis sama atau semuanya berjenis berbeda.
    🔗
    🔗
🔗
🔗

19.

Misalkan Anda menghadiri sebuah pesta bersama 19 teman terdekat (jadi, termasuk Anda, terdapat 20 orang di pesta tersebut). Jelaskan mengapa sedikitnya dua orang di pesta itu pasti memiliki jumlah teman yang sama di antara para tamu. Asumsikan bahwa hubungan pertemanan selalu timbal balik.
🔗
Petunjuk.
Perhatikan himpunan banyaknya teman yang dimiliki setiap orang. Jika setiap orang memiliki jumlah teman yang berbeda, himpunan ini harus memuat 20 elemen. Apakah hal itu mungkin? Mengapa tidak?
🔗
🔗
🔗

20.

Teman Anda memberikan daftar 115 episode Doctor Who terbaik menurutnya (diurutkan dari yang terbaik). Ternyata Anda telah menonton 60 episode di antaranya. Buktikan bahwa sedikitnya ada dua episode yang telah Anda tonton dan posisinya dalam daftar teman Anda berselisih tepat empat.
🔗
Petunjuk.
Soal ini terasa seperti penerapan prinsip sarang merpati, meskipun sedikit lebih rumit. Setidaknya, Anda dapat mencoba meniru gaya pembuktian yang digunakan pada prinsip sarang merpati. Bagaimana jarak antarepisode harus diatur agar tidak ada dua dari 60 episode yang posisinya berselisih tepat 4?
🔗
🔗
🔗

21.

Misalkan Anda memiliki papan catur berukuran \(n\times n\text{,}\) tetapi anjing Anda telah memakan salah satu petak sudutnya. Anda memiliki keping domino yang masing-masing menutupi tepat dua petak papan. Dapatkah Anda menutupi petak-petak yang tersisa dengan domino yang tidak saling tumpang tindih? Syarat apa yang harus dipenuhi oleh \(n\text{?}\) Berikan syarat perlu dan cukup (artinya, tentukan secara tepat nilai \(n\) mana yang dapat digunakan dan mana yang tidak). Buktikan jawaban Anda.
🔗
Papan catur berukuran 8 kali 8 dengan petak sudut kanan atas dihilangkan. Petak-petaknya diarsir gelap secara berselang-seling mengikuti pola papan catur.
🔗

22.

Bagaimana jika dua petak sudut yang saling berhadapan hilang dari papan catur \(n\times n\) Anda? Buktikan bahwa berapa pun nilai \(n\text{,}\) Anda tidak akan dapat menutupi petak-petak yang tersisa dengan domino yang tidak saling tumpang tindih.
🔗
Papan catur berukuran 8 kali 8 dengan petak sudut kanan atas dan kiri bawah dihilangkan. Petak-petaknya diarsir gelap secara berselang-seling mengikuti pola papan catur.
🔗
🔗
🔗
SblmTopLnjt
Umpan Balik