Logika Matematika Archives — Page 2 of 8

Misalkan $p$ merupakan suatu proposisi. Dalam logika matematika, proposisi majemuk $p \land \neg p$ selalu bernilai salah, yang selanjutnya dikenal sebagai kontradiksi. Dengan kata lain, $p$ dan $\neg p$ tidak dapat bernilai benar secara bersamaan. Sebagai contoh, proposisi $1 = 0$ dan $1 \neq 0$ adalah dua pernyataan yang kontradiktif. Jika kita menganggap $1 = 0$ adalah proposisi yang benar, maka otomatis $1 \neq 0$ adalah pernyataan yang salah. Kita tidak dapat mengatakan keduanya benar (atau kadang-kadang benar di saat tertentu, tetapi masih dalam konteks penjumlahan pada sistem bilangan desimal) meskipun kita melakukan manipulasi matematis yang “cerdik” sekali pun.

Proposisi majemuk $p \Rightarrow q$ sering kali menjadi pernyataan yang harus dibuktikan kebenarannya. Di lain sisi, kita mendefinisikan bahwa proposisi majemuk tersebut bernilai salah hanya ketika $p$ benar dan $q$ salah seperti yang terlihat pada tabel kebenaran di bawah.

$\begin{array}{ccc} p & q & p \Rightarrow q \\ B e n a r & B e n a r & B e n a r \\ B e n a r & S a l a h & S a l a h \\ S a l a h & B e n a r & B e n a r \\ S a l a h & S a l a h & B e n a r \end{array}$

Dari tabel tersebut, dapat dilihat bahwa $p$ benar dan $q$ salah akan mengakibatkan $p \Rightarrow q$ salah.

Asumsikan bahwa $p$ (hipotesis) benar seperti pembuktian langsung (direct proof) lainnya. Namun, alih-alih membuktikan bahwa $q$ (konklusi) bernilai benar, kita mempertanyakan satu hal yang urgen, yaitu “Mengapa $q$ tidak mungkin salah?” Lagi pula, jika $q$ memang bernilai benar, seharusnya ada alasan tertentu yang membuatnya tidak mungkin salah. Pemikiran seperti inilah yang melandasi terciptanya metode kontradiksi (proof by contradiction). Beberapa istilah yang dipakai sebagai alternatif dari metode kontradiksi adalah reductio ad absurdum atau argumentum ad absurdum atau apagogical arguments.

Dengan kata lain, konstruksi dari metode kontradiksi adalah mengasumsikan bahwa $p$ benar dan $q$ salah, kemudian menelusuri alasan mengapa kondisi tersebut tidak mungkin terjadi. Asumsi demikian biasanya akan mengakibatkan kontradiksi terhadap sesuatu yang telah kita percayai benar. Sebagai contoh, asumsi $p$ benar dan $q$ salah ternyata menghasilkan pernyataan akhir $0! = 0,$ padahal definisi mengatakan bahwa $0! = 1$ (yang telah kita percayai benar). Dengan kata lain, $0! = 0$ adalah pernyataan yang kontradiktif. Setelah kita menemukannya, kita bisa langsung simpulkan bahwa $q$ haruslah benar. Pada kenyataannya, tidak ada cara untuk kita dalam menduga pernyataan kontradiktif apa yang akan terjadi. Secara ringkas, diagram kerja dari metode kontradiksi (dibandingkan dengan metode maju-mundur dalam pembuktian langsung) saat ingin membuktikan kebenaran $A \Rightarrow B$ adalah sebagai berikut.

Berkas terkait materi pembuktian dengan menggunakan metode kontradiksi dapat diakses dan diunduh melalui tautan berikut: Download (PDF).

Artikel ini ditulis berdasarkan beberapa sumber. Untuk sumber berbahasa Inggris, salah satu yang digunakan adalah buku “How to Read and Do Proofs” yang ditulis oleh Daniel Solow. Oleh karena itu, untuk meminimalisasi kesalahan penafsiran, padanan untuk beberapa kata/istilah diberikan dalam tabel berikut.

$\begin{array}{ccc} No. & Bahasa Indonesia & Bahasa Inggris \\ 1. & Metode Kontradiksi & Contradiction Method \\ 2. & Pembuktian dengan Kontradiksi & Proof by Contradiction \\ 3. & Kontradiktif & Contradictive \\ 4. & Proposisi & Proposition \\ 5. & Proposisi Majemuk & Compound Proposition \\ 6. & Implikasi & Implication \\ 7. & Hipotesis & Hypothesis \\ 8. & Konklusi & Conclusion \\ 9. & Tabel Kebenaran & Truth Table \\ 10. & Pembuktian Langsung & Direct Proof \\ 11. & Pembuktian Taklangsung & Indirect Proof \\ 12. & Metode Maju-Mundur & Forward-Backward Method \end{array}$

Today Quote

Sang juara adalah orang yang gagal sebanyak

x

kali, tetapi bangkit sebanyak

(x + 1)

kali.

Berikut ini telah disediakan sejumlah soal dan pembahasan terkait penggunaan metode kontradiksi dalam membuktikan proposisi.
Catatan: Simbol menyatakan quod erat demonstrandum (Q.E.D), artinya “yang sudah terbukti”. Kita biasanya menggunakan simbol itu untuk menyatakan bahwa proses pembuktian sudah selesai.

Soal Nomor 1

Nyatakan proposisi berikut sehingga kata “tidak/bukan” tidak muncul secara eksplisit.

$10^{100}$ bukan bilangan ganjil.
$\sqrt{5}$ bukan bilangan rasional.
Bilangan real $a d - b c$ tidak sama dengan $0$ untuk setiap $a, b, c, d \in R .$
Segitiga $A B C$ bukan segitiga sama sisi.
Suku banyak $a_{0} + a_{1} x + \dots + a_{n} x^{n}$ tidak memiliki akar real untuk setiap bilangan bulat $a_{0}, a_{1}, \dots, a_{n} .$

Pembahasan

Jawaban a)
$10^{100}$ merupakan bilangan genap.
Jawaban b)
$\sqrt{5}$ merupakan bilangan irasional.
Jawaban c)
Bilangan real $a d - b c > 0$ atau $a d - b c < 0$ untuk setiap $a, b, c, d \in R .$
Jawaban d)
(1) Segitiga $A B C$ memiliki setidaknya satu sisi yang panjangnya berbeda dengan dua sisi lainnya, atau (2) Segitiga $A B C$ memiliki setidaknya satu sudut yang besarnya lebih dari atau kurang dari $60^{\circ} .$
Jawaban e)
Semua akar dari suku banyak $a_{0} + a_{1} x + \dots + a_{n} x^{n}$ untuk setiap bilangan bulat $a_{0}, a_{1}, \dots, a_{n}$ adalah bilangan kompleks dalam bentuk $c + d i$ dengan $d < 0$ atau $d > 0$ serta $i$ merupakan bilangan imajiner.

[collapse]

Soal Nomor 2

Ketika menggunakan metode kontradiksi untuk membuktikan proposisi berikut, apa yang harus kita andaikan?

Jika $l, m,$ dan $n$ adalah tiga bilangan bulat berurutan, maka $24$ tidak membagi $l^{2} + m^{2} + n^{2} + 1.$
Untuk setiap bilangan bulat $n > 2,$ $x^{n} + y^{n} = z^{n}$ tidak punya solusi bulat untuk $x, y,$ dan $z .$
Jika $f$ dan $g$ adalah dua fungsi sedemikian sehingga $g \geq f$ dan $f$ tidak terbatas di atas, maka $g$ juga tidak terbatas di atas.

Pembahasan

Jika kita bekerja dengan metode kontradiksi untuk membuktikan proposisi berbentuk $p \Rightarrow q,$ kita harus mengandaikan bahwa $q$ bernilai salah. Selanjutnya, dengan menggunakan proposisi $p$ dan $\neg q,$ kita melangkah guna menemukan kontradiksi.
Jawaban a)
Andaikan $24$ tidak membagi $l^{2} + m^{2} + n^{2} + 1.$
Jawaban b)
Andaikan ada bilangan bulat $n > 2$ sedemikian sehingga $x^{n} + y^{n} = z^{n}$ punya solusi bulat untuk $x, y,$ dan $z .$
Jawaban c)
Andaikan $g$ terbatas di atas.

[collapse]

Soal Nomor 3

Tunjukkan bahwa paling sedikit $4$ dari $22$ hari pasti jatuh pada hari yang sama.

Pembahasan

Dengan menggunakan metode kontradiksi, andaikan paling banyak $3$ dari $22$ hari yang berurutan jatuh pada hari yang sama. Karena satu minggu terdiri dari $7$ hari saja, paling banyak $21$ hari dapat dipilih agar masing-masing hari (Senin, Selasa, …, Minggu) muncul $3$ kali. Hal ini kontradiktif dengan asumsi bahwa kita punya $22$ hari.
Jadi, disimpulkan bahwa paling sedikit $4$ dari $22$ hari pasti jatuh pada hari yang sama.

[collapse]

Soal Nomor 4

Buktikan bahwa paling sedikit ada dua orang di bumi yang lahir pada detik, menit, jam, hari, dan tahun yang sama pada abad ke-20. Asumsikan bahwa paling sedikit ada 4 miliar orang yang lahir pada abad itu. Asumsikan juga satu tahun terdiri dari $365$ hari.

Pembahasan

Dengan menggunakan metode kontradiksi, andaikan tidak ada dua orang di bumi yang lahir pada detik, menit, jam, hari, dan tahun yang sama pada abad ke-20. Dengan kata lain, $4$ miliar orang tersebut lahir pada waktu yang berbeda-beda. Ini berarti kita dapat menomori orang-orang tersebut secara menaik sesuai dengan waktu kelahiran mereka masing-masing. Sebagai contoh, orang nomor 1 lahir pada detik ke-1, orang nomor 2 lahir pada detik ke-2, dan seterusnya. Dalam 1 abad, ada $\underset{detik}{\underset{⏟}{60}} \times \underset{menit}{\underset{⏟}{60}} \times \underset{jam}{\underset{⏟}{24}} \times \underset{hari}{\underset{⏟}{365}} \times \underset{tahun}{\underset{⏟}{100}} = 3.153 .600 .000 detik .$ Perhatikan bahwa $4.000 .000 .000 > 3.153 .600 .000 .$ Ini menunjukkan bahwa orang nomor ke-4 miliar (orang terakhir) tidak mungkin lahir pada abad ke-20, tetapi ternyata kontradiktif dengan pernyataan awal bahwa $4$ miliar orang itu lahir pada abad ke-20. Jadi, pengandaian salah. Terbukti bahwa paling sedikit ada dua orang di bumi yang lahir pada detik, menit, jam, hari, dan tahun yang sama pada abad ke-20. Asumsikan bahwa paling sedikit ada 4 miliar orang yang lahir pada abad itu. Asumsikan juga satu tahun terdiri dari $365$ hari.

[collapse]

Soal Nomor 5

Buktikan bahwa dalam suatu pesta yang dihadiri oleh $n \geq 2$ orang, paling sedikit ada dua orang yang memiliki jumlah teman yang sama pada pesta itu.
Catatan: Asumsikan bahwa relasi “berteman’ sebagai relasi setangkup (simetris), artinya jika $A$ berteman dengan $B,$ maka $B$ berteman dengan $A .$

Pembahasan

Dengan menggunakan metode kontradiksi, andaikan tidak ada dua orang yang memiliki jumlah teman yang sama pada pesta itu. Dengan kata lain, masing-masing orang memiliki jumlah teman yang berbeda-beda. Karena ada $n$ orang, kita bisa mengurutkan mereka sesuai dengan jumlah temannya seperti berikut.
$\begin{aligned} Orang nomor 1 tidak memiliki teman \\ Orang nomor 2 memiliki 1 teman \\ Orang nomor 3 memiliki 2 teman \\ ⋮ ⋮ ⋮ \\ Orang nomor n memiliki (n - 1) teman \end{aligned}$ Akibatmya, orang nomor $n$ yang memiliki $(n - 1)$ teman ternyata juga berteman dengan orang nomor $1$ yang seharusnya tidak memiliki teman. Kontradiksi terjadi. Jadi, disimpulkan bahwa paling sedikit ada dua orang yang memiliki jumlah teman yang sama pada pesta itu.

[collapse]

Soal Nomor 6

Buktikan bahwa jika bilangan bulat $n^{2}$ ganjil, maka $n$ juga ganjil.

Pembahasan

Misalkan $n^{2}$ ganjil. Dengan menggunakan metode kontradiksi, andaikan $n$ bukan bilangan ganjil. Dengan kata lain, $n$ adalah bilangan genap, yaitu bilangan berbentuk $n = 2 m$ untuk suatu $m \in Z .$ Dari hipotesis, diketahui bahwa $n^{2}$ adalah bilangan bulat ganjil, tetapi
$n^{2} = (2 m)^{2} = 2 (2 m^{2}) .$ Padahal, $2 m^{2}$ adalah bilangan bulat sehingga $n^{2}$ merupakan bilangan genap sesuai definisi. Hal ini kontradiktif dengan hipotesis. Jadi, pengandaian salah.
Dengan demikian, disimpulkan bahwa jika bilangan bulat $n^{2}$ ganjil, maka $n$ juga ganjil.

[collapse]

Soal Nomor 7

Buktikan bahwa jika $3 n + 2$ ganjil dengan $n \in Z$ , maka $n$ juga ganjil.

Pembahasan

Misalkan $3 n + 2$ ganjil. Dengan menggunakan metode kontradiksi, andaikan bahwa $n$ bukan ganjil, berarti $n$ genap. Dengan demikian, terdapat bilangan bulat $k$ sehingga $n = 2 k .$ Namun,
$3 n + 2 = 3 (2 k) + 2 = 2 (3 k + 1) .$ Karena $3 k + 1$ adalah bilangan bulat, $3 n + 2$ memenuhi definisi bilangan genap. Hal ini kontradiktif dengan hipotesis yang mengatakan bahwa $3 n + 2$ ganjil. Kontradiksi terjadi di sini dan pengandaian perlu diingkari. Jadi, terbukti bahwa $n$ harus ganjil.

[collapse]

Soal Nomor 8

Buktikan bahwa $\sqrt{2}$ merupakan bilangan irasional.

Pembahasan

Dengan menggunakan metode kontradiksi, andaikan bahwa $\sqrt{2}$ merupakan bilangan rasional, artinya ada bilangan bulat $a, b$ dengan $b \neq 0$ sehingga $\sqrt{2} = \frac{a}{b}$ dengan $FPB (a, b) = 1.$
Dengan demikian, ketika kedua ruas dikuadratkan, diperoleh $2 = \frac{a^{2}}{b^{2}} .$ Akibatnya,
$2 b^{2} = a^{2} .$ Sesuai dengan definisi bilangan genap, $a^{2}$ haruslah genap dan ini berarti $a$ juga genap. Oleh karena itu, $a = 2 k$ untuk suatu $k \in Z .$ Selanjutnya, diperoleh
$2 b^{2} = (2 k)^{2} .$ Dengan membagi kedua ruas dengan $2,$ diperoleh
$b^{2} = 2 k^{2} .$ Sesuai dengan definisi bilangan genap, $b^{2}$ haruslah genap dan ini berarti $b$ juga genap. Akibatnya, $FPB (a, b) \geq 2.$
Hal ini kontradiktif dengan asumsi awal bahwa $FPB (a, b) = 1.$
Jadi, disimpulkan bahwa $\sqrt{2}$ adalah bilangan irasional.

[collapse]

Soal Nomor 9

Buktikan bahwa jika $n$ adalah bilangan kuadrat sempurna (perfect square), maka $n + 2$ bukan bilangan kuadrat sempurna.
Catatan: Bilangan kuadrat sempurna didefinisikan sebagai bilangan bulat positif yang merupakan kuadrat dari suatu bilangan bulat positif yang lain.

Pembahasan

Misalkan $n$ adalah bilangan kuadrat sempurna. Dengan menggunakan metode kontradiksi, andaikan $n + 2$ adalah bilangan kuadrat sempurna. Oleh karena itu, dapat ditulis $n = a^{2}$ dan $n + 2 = b^{2}$ untuk suatu $a, b \geq 0.$
Perhatikan bahwa
$\begin{aligned} (n + 2) - n & = 2 \\ b^{2} - a^{2} & = 2 \\ (b + a) (b - a) & = 2. \end{aligned}$ Karena $b + a > 0,$ maka $(b + a)$ merupakan faktor dari $2,$ yaitu $1$ atau $2.$ Namun, karena $a = 1$ dan $b = 1$ merupakan nilai minimum, $(b + a)$ haruslah $2,$ tetapi $b - a = 1 - 1 = 0.$ Akibatnya, $b^{2} - a^{2} \neq 2.$ Hal ini menimbulkan kontradiksi sehingga pengandaian salah.
Jadi, terbukti bahwa $n + 2$ bukan bilangan kuadrat sempurna.

[collapse]

Soal Nomor 10

Buktikan bahwa $^{2} \log 7$ adalah bilangan irasional.

Pembahasan

Dengan menggunakan metode kontradiksi, andaikan $^{2} \log 7$ bukan bilangan irasional. Dengan kata lain, $^{2} \log 7$ adalah bilangan rasional, yaitu bilangan yang dapat dituliskan dalam bentuk pecahan $\frac{a}{b}$ dengan $a, b \in Z$ dan $b \neq 0.$
Dengan demikian, dapat ditulis
$\begin{aligned} ^{2} \log 7 & = \frac{a}{b} \\ 2^{a / b} & = 7 \\ 2^{a} & = 7^{b} . \end{aligned}$ Perhatikan bahwa $(2, 7)$ merupakan pasangan bilangan yang relatif prima sehingga persamaan terakhir tidak mungkin terpenuhi untuk sembarang $a, b \in Z .$ Hal ini kontradiktif dengan pengandaian yang dilakukan.
Jadi, disimpulkan bahwa $^{2} \log 7$ adalah bilangan irasional.

[collapse]

Soal Nomor 11

Buktikan bahwa jumlah dari bilangan irasional dan bilangan rasional menghasilkan bilangan irasional.

Pembahasan

Pertama, kita libatkan penggunaan notasi pada pernyataan yang ingin dibuktikan menjadi “Jika $R$ merupakan bilangan rasional dan $I$ merupakan bilangan irasional, maka $S = R + I .$
Dengan menggunakan metode kontradiksi, andaikan $S$ rasional. Akibatnya, hasil penjumlahan dari bilangan rasional $S$ dan $- R$ haruslah rasional. Hal ini dapat diketahui karena jika $S = \frac{a}{b}$ dan $R = \frac{c}{d}$ dengan $a, b, c, d \in Z$ dan $b, d \neq 0,$ maka dengan aljabar, kita peroleh $S + (- R) = \frac{a d - b c}{b d},$ yang memenuhi definisi bilangan rasional karena $a d - b c \in Z$ dan $b d \neq 0.$ Di lain sisi,
$S + (- R) = (R + I) - R = I$ sehingga memaksa kita untuk menyimpulkan bahwa $I$ adalah bilangan rasional, padahal harusnya tidak demikian. Kontradiksi terjadi di sini. Jadi, pengandaian salah. Dengan demikian, $S$ terbukti merupakan bilangan irasional.

[collapse]

Soal Nomor 12

Buktikan bahwa jika $x$ dan $y$ merupakan bilangan real dengan $x \geq 0, y \geq 0,$ dan $x + y = 0,$ maka $x = 0$ dan $y = 0.$

Pembahasan

Misalkan $x$ dan $y$ merupakan bilangan real dengan $x \geq 0, y \geq 0,$ dan $x + y = 0.$ Dengan menggunakan metode kontradiksi, andaikan $x \neq 0$ atau $y \neq 0.$ Jika $x \neq 0,$ maka $x > 0.$ Akibatnya, $y = - x < 0.$ Namun, hal ini kontradiktif dengan hipotesis bahwa $y \geq 0.$ Serupa dengan itu, jika $y \neq 0$ , maka $y > 0.$ Akibatnya, $x = - y < 0$ yang ternyata juga kontradiktif dengan hipotesis bahwa $x \geq 0.$ Jadi, pengandaian salah. Terbukti bahwa jika $x$ dan $y$ merupakan bilangan real dengan $x \geq 0, y \geq 0,$ dan $x + y = 0,$ maka $x = 0$ dan $y = 0.$

[collapse]

Soal Nomor 13

Buktikan bahwa tidak ada bilangan real positif $x$ dan $y$ dengan $x \neq y$ sedemikian sehingga $x^{3} - y^{3} = 0.$

Pembahasan

Dengan menggunakan metode kontradiksi, andaikan ada bilangan real positif $x$ dan $y$ dengan $x \neq y$ sedemikian sehingga $x^{3} - y^{3} = 0.$ Dengan demikian, kita bisa faktorkan menjadi
$x^{3} - y^{3} = (x - y) (x^{2} + x y + y^{2}) = 0.$ Dengan membagi kedua ruas dengan $x - y \neq 0$ , kita peroleh $x^{2} + x y + y^{2} = 0. (\dots 1)$ Dengan menganggap $(1)$ sebagai persamaan kuadrat bervariabel $x,$ kita peroleh nilai berikut setelah menggunakan rumus kuadrat.
$x = \frac{- y \pm \sqrt{y^{2} - 4 (1) (y^{2})}}{2 (1)} = \frac{- y \pm \sqrt{- 3 y^{2}}}{2}$ Agar diperoleh bilangan real $x,$ nilai $y$ haruslah $0.$ Namun, ini berakibat nilai $x$ juga $0.$ Dengan kata lain, $x = y .$ Hal ini kontradiktif dengan asumsi bahwa $x \neq y .$ Jadi, disimpulkan bahwa tidak ada bilangan real positif $x$ dan $y$ dengan $x \neq y$ sedemikian sehingga $x^{3} - y^{3} = 0.$

[collapse]

Soal Nomor 14

Buktikan bahwa jika $(n - 1), n,$ dan $(n + 1)$ merupakan bilangan bulat positif berurutan, maka kubik dari bilangan terbesar tidak sama dengan jumlah kubik dari dua bilangan lainnya.

Pembahasan

Misalkan $(n - 1), n,$ dan $(n + 1)$ merupakan bilangan bulat positif berurutan. Andaikan kubik dari bilangan terbesar sama dengan jumlah kubik dari dua bilangan lainnya, yaitu
$(n + 1)^{3} = n^{3} + (n - 1)^{3} .$ Perhatikan bahwa persamaan itu dapat disederhanakan seperti berikut.
$\begin{aligned} n^{3} + 3 n^{2} + 3 n + 1 & = n^{3} + (n^{3} - 3 n^{2} + 3 n - 1) \\ n^{3} - 6 n^{2} - 2 & = 0 \\ n^{2} (n - 6) & = 2 \end{aligned}$ Karena $n$ merupakan bilangan bulat positif, haruslah $n^{2} > 0.$ Agar diperoleh bilangan bulat positif $2$ , nilai $n - 6 > 0$ sehingga $n \geq 7.$ Namun, $n^{2} (n - 6) \geq 7^{2} (7 - 6) = 49.$ Hal ini kontradiktif dengan persamaan $n^{2} (n - 6) = 2.$ Jadi, pengandaian salah. Terbukti bahwa jika $(n - 1), n,$ dan $(n + 1)$ merupakan bilangan bulat positif berurutan, maka kubik dari bilangan terbesar tidak sama dengan jumlah kubik dari dua bilangan lainnya.

[collapse]

Soal Nomor 15

Buktikan bahwa jika $n$ merupakan bilangan bulat positif sedemikian sehingga $n^{3} - n - 6 = 0$ , maka untuk setiap bilangan bulat positif $m$ dengan $m \neq n,$ berlaku $m^{3} - m - 6 \neq 0.$

Pembahasan

Misalkan $n$ merupakan bilangan bulat positif sedemikian sehingga $n^{3} - n - 6 = 0.$ Dengan menggunakan metode kontradiksi, andaikan ada bilangan bulat positif $m$ dengan $m \neq n$ sedemikian sehingga $m^{3} - m - 6 = 0.$ Dengan pemfaktoran, diperoleh $m (m + 1) (m - 1) = 6.$ Bilangan bulat positif $m$ yang memenuhi persamaan ini adalah $m = 2$ saja karena jika $m = 1,$ persamaan tidak terpenuhi dan jika $m > 2,$ nilai $m (m + 1) (m - 1) > 6.$ Dengan cara yang serupa, hipotesis mengatakan bahwa $n^{3} - n - 6 = 0.$ Kita selanjutnya peroleh $n (n + 1) (n - 1) = 6.$ Ini berarti nilai $n$ yang memenuhi hanya $n = 2.$ Jadi, diperoleh $m = n = 2.$ Hal ini kontradiktif dengan asumsi bahwa $m \neq n .$ Jadi, pengandaian salah. Terbukti bahwa jika $n$ merupakan bilangan bulat positif sedemikian sehingga $n^{3} - n - 6 = 0$ , maka untuk setiap bilangan bulat positif $m$ dengan $m \neq n,$ berlaku $m^{3} - m - 6 \neq 0.$

[collapse]

Soal Nomor 16

Misalkan $a, b,$ dan $c$ adalah bilangan real dengan $c \neq 0.$ Buktikan bahwa jika $c x^{2} + b x + a$ tidak memiliki akar rasional, maka $a x^{2} + b x + c$ juga tidak memiliki akar rasional.

Pembahasan

Misalkan $a, b,$ dan $c$ adalah bilangan real dengan $c \neq 0 .$ Misalkan juga $c x^{2} + b x + a$ tidak memiliki akar rasional. Dengan menggunakan metode kontradiksi, andaikan $a x^{2} + b x + c$ memiliki akar rasional, katakanlah $\frac{p}{q}$ dengan $p, q \in Z$ dan $q \neq 0$ sedemikian sehingga
$a {(\frac{p}{q})}^{2} + b (\frac{p}{q}) + c = 0.$ Perhatikan bahwa $p \neq 0$ karena mengakibatkan nilai $c = 0 .$ Jadi, kita bisa mengalikan kedua ruas persamaan sebelumnya dengan $\frac{q^{2}}{p^{2}}$ sehingga menghasilkan
$a + b (\frac{q}{p}) + c {(\frac{q}{p})}^{2} = 0.$ Namun, ini menunjukkan bahwa $\frac{q}{p}$ merupakan akar rasional dari persamaan $c x^{2} + b x + a .$ Hal ini kontradiktif dengan hipotesis karena seharusnya $c x^{2} + b x + a$ tidak memiliki akar rasional. Jadi, pengandaian salah. Terbukti bahwa jika $c x^{2} + b x + a$ tidak memiliki akar rasional, maka $a x^{2} + b x + c$ juga tidak memiliki akar rasional.

[collapse]

Soal Nomor 17

Buktikan bahwa jika $p$ dan $q$ adalah bilangan bulat dengan $p \neq q$ serta $p$ prima dan membagi $q,$ maka $q$ bukan prima.
Catatan: Bilangan bulat $n > 1$ dikatakan sebagai bilangan prima jika $n$ memiliki tepat dua faktor, yaitu $1$ dan $n .$

Pembahasan

Misalkan $p$ dan $q$ adalah bilangan bulat dengan $p \neq q$ serta $p$ prima dan membagi $q .$ Dengan menggunakan metode kontradiksi, andaikan $q$ prima.
Karena $p$ membagi $q,$ ada bilangan bulat $a$ sedemikian sehingga $q = a p .$ Karena $p \neq q$ , $a$ tidak boleh bernilai $1.$ Perhatikan juga bahwa jika $a = q$ , maka $p = 1$ , padahal $p$ merupakan bilangan prima. Jadi, haruslah $a \neq q .$ Dengan menggunakan definisi keterbagian, $q = a p$ menunjukkan bahwa $a$ membagi $q .$ Karena $a \neq 1$ dan $a \neq q,$ hal ini mengakibatkan kontradiktif dengan definisi bahwa $p$ merupakan bilangan prima. Jadi, pengandaian salah. Terbukti bahwa jika $p$ dan $q$ adalah bilangan bulat dengan $p \neq q$ serta $p$ prima dan membagi $q,$ maka $q$ bukan prima.

[collapse]

Soal Nomor 18

Buktikan bahwa jika $a, b,$ dan $c$ adalah bilangan real dengan $a \neq 0,$ maka fungsi $f (x) = a x^{2} + b x + c$ bukan fungsi satu-satu (fungsi injektif).

Pembahasan

Misalkan $a, b,$ dan $c$ adalah bilangan real dengan $a \neq 0.$ Dengan menggunakan metode kontradiksi, andaikan $f (x) = a x^{2} + b x + c$ satu-satu. Menurut definisi, untuk setiap $x, y \in D_{f}$ , jika $x \neq y,$ maka $f (x) \neq f (y) .$ Dalam hal ini, kita akan menunjukkan kontradiksi bahwa ternyata ada $x, y \in D_{f}$ dengan $x \neq y$ yang mengakibatkan $f (x) = f (y) .$ Ini berarti kita harus terlebih dahulu mengonstruksi nilai $x$ dan $y$ tersebut sehingga $f (x) = f (y)$ dengan cara seperti berikut.
$\begin{aligned} a x^{2} + b x + c & = a y^{2} + b y + c \\ a x^{2} + b x & = a y^{2} + b y \\ a (x^{2} + \frac{b}{a} x) & = a (y^{2} + \frac{b}{a} y) \\ [a {(x + \frac{b}{2 a})}^{2}] - \frac{b^{2}}{4 a} & = [a {(y + \frac{b}{2 a})}^{2}] - \frac{b^{2}}{4 a} \\ {(x + \frac{b}{2 a})}^{2} & = {(y + \frac{b}{2 a})}^{2} \\ x + \frac{b}{2 a} & = \pm (y + \frac{b}{2 a}) \end{aligned}$ Jika diambil tanda positif, diperoleh $x = y,$ yang berada di luar kasus yang ingin kita tinjau. Ambil tanda negatif sehingga kita peroleh $x + y = - \frac{b}{a} .$ Agar $x \neq y,$ kita bisa mengambil $x = - \frac{b}{2 a} + 1$ dan $y = - \frac{b}{2 a} - 1.$
Jika $x = - \frac{b}{2 a} + 1$ dan $y = - \frac{b}{2 a} - 1,$ kita peroleh
$\begin{aligned} f (x) & = a {(- \frac{b}{2 a} + 1)}^{2} + b (- \frac{b}{2 a} + 1) + c \\ = a + c - \frac{b^{2}}{4 a} \end{aligned}$ dan
$\begin{aligned} f (y) & = a {(- \frac{b}{2 a} - 1)}^{2} + b (- \frac{b}{2 a} - 1) + c \\ = a + c - \frac{b^{2}}{4 a} \end{aligned}$ sehingga $f (x) = f (y) .$ Kontradiksi terbangun karena menurut definisi fungsi satu-satu, jika $x \neq y,$ maka $f (x) \neq f (y) .$ Jadi, pengandaian salah. Terbukti bahwa jika $a, b,$ dan $c$ adalah bilangan real dengan $a \neq 0,$ maka fungsi $f (x) = a x^{2} + b x + c$ bukan fungsi satu-satu (fungsi injektif).

[collapse]

Soal Nomor 19

Buktikan bahwa jika $a > 0$ merupakan bilangan real, maka $f (x) = a^{x}$ merupakan fungsi satu-satu (fungsi injektif).

Pembahasan

Misalkan $a > 0$ merupakan bilangan real dan $f (x) = a^{x} .$ Menurut definisi fungsi satu-satu, untuk setiap $x, y \in D_{f},$ jika $x \neq y,$ maka berlaku $f (x) \neq f (y) .$ Dengan menggunakan metode kontradiksi, andaikan $f (x) = f (y)$ sehingga diperoleh
$\begin{aligned} a^{x} & = a^{y} \\ \log (a^{x}) & = \log (a^{y}) \\ x \log a & = y \log a \\ x & = y & (a \neq 0) . \end{aligned}$ Hal ini kontradiktif dengan hipotesis bahwa $x \neq y .$ Jadi, pengandaian salah. Kita simpulkan untuk setiap $x, y \in D_{f},$ jika $x \neq y,$ maka berlaku $f (x) \neq f (y) .$ Dengan kata lain, fungsi $f (x) = a^{x}$ merupakan fungsi satu-satu.

[collapse]

Soal Nomor 20

Buktikan bahwa jika $a$ dan $b$ merupakan bilangan bulat serta $b$ ganjil, maka $\pm 1$ bukan akar dari $a x^{2} + b x + a .$

Pembahasan

Misalkan $a$ dan $b$ merupakan bilangan bulat serta $b$ ganjil. Dengan menggunakan metode kontradiksi, andaikan $\pm 1$ adalah akar dari $a x^{2} + b x + a .$ Dengan demikian, kita peroleh
$\begin{aligned} a (\pm 1)^{2} + b (\pm 1) + a & = 0 \\ a (1) \pm b + a & = 0 \\ 2 a \pm b & = 0 \\ b & = \pm 2 a . \end{aligned}$ Karena $a$ merupakan bilangan bulat, menurut definisi bilangan genap, kita peroleh $b$ genap. Hal ini kontradiktif dengan hipotesis bahwa $b$ seharusnya ganjil. Jadi, pengandaian salah. Terbukti bahwa jika $a$ dan $b$ merupakan bilangan bulat serta $b$ ganjil, maka $\pm 1$ bukan akar dari $a x^{2} + b x + a .$

[collapse]

Soal Nomor 21

Buktikan bahwa jika $p$ dan $q$ merupakan bilangan bulat ganjil, maka persamaan $x^{2} + 2 p x + 2 q = 0$ tidak memiliki solusi rasional untuk $x .$

Pembahasan

Misalkan $p$ dan $q$ merupakan bilangan bulat ganjil. Dengan menggunakan metode kontradiksi, andaikan $x^{2} + 2 p x + 2 q = 0$ memiliki solusi rasional untuk $x .$ Misalkan $x_{1}$ dan $x_{2}$ merupakan akar rasional dari persamaan kuadrat tersebut. Dengan menggunakan rumus kuadrat, diperoleh
$\begin{aligned} x_{1, 2} & = \frac{- 2 p \pm \sqrt{(2 p)^{2} - 4 (1) (2 q)}}{2 (1)} \\ = \frac{- 2 p \pm \sqrt{4 p^{2} - 8 q}}{2} \\ = \frac{- 2 p \pm 2 \sqrt{p^{2} - 2 q}}{2} \\ = - p \pm \sqrt{p^{2} - 2 q} . \end{aligned}$ Agar $x_{1}$ dan $x_{2}$ rasional, nilai dari $\sqrt{p^{2} - 2 q}$ haruslah berupa bilangan bulat. Misalkan $\sqrt{p^{2} - 2 q} = m$ untuk suatu bilangan bulat (nonnegatif) $m .$
Dengan demikian, diperoleh
$\begin{aligned} {(\sqrt{p^{2} - 2 q})}^{2} & = m^{2} \\ p^{2} - 2 q & = m^{2} \\ p^{2} - m^{2} & = 2 q \\ (p + m) (p - m) & = 2 q . \end{aligned}$ Tanpa mengurangi keumuman, misalkan $p + m = 2$ dan $p - m = q .$ Dengan menjumlahkan sesuai ruasnya, diperoleh $2 p = 2 + q,$ ekuivalen dengan $p = 1 + \frac{q}{2} .$ Karena $q$ ganjil, $\frac{q}{2}$ tidak bulat sehingga $p$ juga tidak bulat. Hal ini kontradiktif dengan permisalan bahwa $p$ merupakan bilangan ganjil. Jadi, pengandaian salah. Terbukti bahwa jika $p$ dan $q$ merupakan bilangan bulat ganjil, maka persamaan $x^{2} + 2 p x + 2 q = 0$ tidak memiliki solusi rasional untuk $x .$

[collapse]

Soal Nomor 22

Buktikan bahwa untuk semua bilangan prima $p$ , $p + 7$ merupakan bilangan komposit.
Catatan: Bilangan komposit merupakan bilangan bulat positif $> 2$ yang bukan prima.

Pembahasan

Dengan menggunakan metode kontradiksi, andaikan terdapat bilangan prima $p$ sehingga $p + 7$ juga prima. Untuk $p = 2,$ hal demikian tidak berlaku karena $2 + 7 = 9$ bukan bilangan prima. Tinjau bilangan prima $p > 2.$ Perhatikan bahwa $p$ pastilah merupakan ganjil. Akibatnya, $p + 7$ genap (karena ganjil + ganjil = genap). Hal ini kontradiktif dengan fakta bahwa $p + 7$ merupakan bilangan prima lebih besar dari dua (yang jelas tidak mungkin genap). Jadi, pengandaian salah. Disimpulkan bahwa untuk semua bilangan prima $p$ , $p + 7$ merupakan bilangan komposit.

[collapse]

Soal Nomor 23

Buktikan bahwa jika $a, b, c,$ dan $d$ merupakan bilangan real sehingga persamaan $a x + b y = 0$ dan $c x + d y = 0$ memiliki solusi tunggal, maka $a d - b c \neq 0.$

Pembahasan

Misalkan $a, b, c,$ dan $d$ merupakan bilangan real sehingga sistem persamaan $a x + b y = 0$ dan $c x + d y = 0$ memiliki solusi tunggal. Dengan menggunakan metode kontradiksi, andaikan $a d - b c = 0.$
Karena sistem persamaan memiliki solusi tunggal, $c$ dan $d$ tidak boleh keduanya bernilai $0$ sekaligus. Dengan kata lain, $c \neq 0$ atau $d \neq 0.$ Konstruksi $x = d$ dan $y = - c$ sehingga diperoleh
${\begin{cases} a x + b y = a (d) + b (- c) = a d - b c = 0 \\ c x + d y = c (d) + d (- c) = 0. \end{cases}$ Dengan demikian, $x = d$ dan $y = - c$ merupakan solusi sistem persamaan tersebut. Namun, $x = y = 0$ juga solusi sistem persamaan karena $a (0) + b (0) = 0$ dan $c (0) + d (0) = 0.$ Hal ini kontradiktif dengan permisalan bahwa sistem persamaan memiliki solusi tunggal. Jadi, pengandaian salah.
Disimpulkan bahwa $a d - b c = 0$ sehingga proposisi terbukti benar.

[collapse]

Soal Nomor 24

Buktikan bahwa polinomial $x^{4} + 2 x^{2} + 2 x + 2$ tidak dapat dinyatakan sebagai hasil kali dari dua polinomial $x^{2} + a x + b$ dan $x^{2} + c x + d$ untuk suatu bilangan bulat $a, b, c,$ dan $d .$

Pembahasan

Dengan menggunakan metode kontradiksi, andaikan polinomial $x^{4} + 2 x^{2} + 2 x + 2$ dapat dinyatakan sebagai hasil kali dari dua polinomial $x^{2} + a x + b$ dan $x^{2} + c x + d$ untuk suatu bilangan bulat $a, b, c,$ dan $d .$ Dengan demikian, dapat ditulis
$\begin{aligned} x^{4} + 2 x^{2} + 2 x + 2 & = (x^{2} + a x + b) (x^{2} + c x + d) \\ = x^{4} + (a + c) x^{3} + (b + a c + d) x^{2} + (b c + a d) x + b d . \end{aligned}$ Dengan menyamakan nilai koefisien, diperoleh
${\begin{cases} a + c & = 0 & (1) \\ b + a c + d & = 2 & (2) \\ b c + a d & = 2 & (3) \\ b d & = 2. & (4) \end{cases}$ Persamaan $(4)$ dapat dipenuhi ketika nilai $b = \pm 1$ (ganjil) dan $d = \pm 2$ (genap), atau sebaliknya.

Jika $b$ ganjil dan $d$ genap, dari Persamaan $(3),$ haruslah $c$ genap. Namun, hal ini kontradiktif dengan Persamaan $(2)$ yang mengharuskan nilai $c$ ganjil.
Jika $b$ genap dan $d$ ganjil, dari Persamaan $(3),$ haruslah $a$ genap. Namun, hal ini kontradiktif dengan Persamaan $(2)$ yang mengharuskan nilai $a$ ganjil.

Jadi, pengandaian salah. Disimpulkan bahwa polinomial $x^{4} + 2 x^{2} + 2 x + 2$ tidak dapat dinyatakan sebagai hasil kali dari dua polinomial $x^{2} + a x + b$ dan $x^{2} + c x + d$ untuk suatu bilangan bulat $a, b, c,$ dan $d .$

[collapse]

Soal Nomor 25

Tentukan banyak tripel bilangan bulat $(a, b, c)$ yang memenuhi $a! + b! = c! .$

Pembahasan

Nilai $(a, b, c)$ pada persamaan $a! + b! = c!$ hanya dipenuhi oleh $(0, 0, 2), (1, 0, 2), (0, 1, 2)$ , dan $(1, 1, 2) .$ Dengan menggunakan metode kontradiksi, andaikan ada tripel $(a, b, c)$ lain yang memenuhi persamaan $a! + b! = c!$ dengan $c > 2.$ Pilih $a = b = c - 1$ yang merupakan bilangan terbesar sebelum $c .$ Namun,
$(c - 1)! + (c - 1)! = 2 (c - 1)! < c (c - 1)! = c! .$ Hal ini kontradiktif dengan pengandaian bahwa ada tripel $(a, b, c)$ lain yang memenuhi persamaan $a! + b! = c!$ dengan $c > 2.$ Jadi, pengandaian salah. Disimpulkan bahwa hanya ada $4$ pasangan bilangan $(a, b, c)$ yang memenuhi persamaan $a! + b! = c! .$

[collapse]

Soal Nomor 26

Buktikan bahwa $e$ merupakan bilangan irasional dengan menggunakan fakta bahwa $e = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \dots .$

Pembahasan

Dengan menggunakan metode kontradiksi, andaikan $e$ rasional sehingga dapat ditulis $e = \frac{a}{b}$ untuk suatu bilangan bulat $a$ dan $b$ dengan $b \neq 0.$ Misalkan $k \geq b$ merupakan bilangan bulat. Tetapkan $c = k! (e - 1 - \frac{1}{1!} - \frac{1}{2!} - \frac{1}{3!} - \dots - \frac{1}{k!}) .$ Karena $k!$ membagi setiap penyebut yang ada pada ekspresi tersebut, $c$ pastilah berupa bilangan bulat. Lebih lanjut, karena $e = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \dots,$ diperoleh
$\begin{aligned} 0 < c & = k! (\frac{1}{(k + 1)!} + \frac{1}{(k + 2)!} + \frac{1}{(k + 3)!} + \dots) \\ = \frac{1}{k + 1} + \frac{1}{(k + 1) (k + 2)} + \frac{1}{(k + 1) (k + 2) (k + 3)} + \dots \\ < \frac{1}{k + 1} + \frac{1}{(k + 1)^{2}} + \frac{1}{(k + 1)^{3}} + \dots . \end{aligned}$ Deret terakhir merupakan deret geometri dengan suku pertama dan rasionya $\frac{1}{k + 1}$ sehingga jumlahnya adalah $\frac{1 / (k + 1)}{1 - 1 / (k + 1)} = \frac{1}{k} .$ Jadi, diperoleh $0 < c < \frac{1}{k} .$ Namun, hal ini membuat $c$ tidak mungkin bulat, kontradiktif dengan penemuan sebelumnya bahwa $c$ haruslah bulat. Jadi, pengandaian salah. Disimpulkan bahwa $e$ merupakan bilangan irasional.

[collapse]

Soal Nomor 27

Buktikan bahwa himpunan bilangan real dan himpunan bilangan irasional taktercacah (uncountable).

Pembahasan

Pandang subhimpunan bilangan real $(0, 1) = {x \in R ∣ 0 < x < 1} .$ Klaim bahwa subhimpunan tersebut taktercacah. Bukti diberikan dengan menggunakan metode kontradiksi. Andaikan $(0, 1)$ tercacah (countable). Jelas bahwa $(0, 1)$ bukan himpunan berhingga sehingga dapat diasumsikan $(0, 1)$ adalah himpunan takberhingga tercacah (countably infinite). Karena itu, terdapat korespondensi satu-satu dari $N$ ke $(0, 1) .$ Dengan kata lain, dapat dibuat senarai takberhingga (infinite list) yang memuat semua bilangan real di antara $0$ dan $1.$ Misalkan bilangan real yang dimaksud ditulis dalam notasi desimal sehingga seperti tampak pada ilustrasi berikut.
$\begin{array}{cc} 1 & \overset{―}{0, a_{0, 0} a_{0, 1} a_{0, 2} a_{0, 3} \dots} \\ 2 & \overset{―}{0, a_{1, 0} a_{1, 1} a_{1, 2} a_{1, 3} \dots} \\ 3 & \overset{―}{0, a_{2, 0} a_{2, 1} a_{2, 2} a_{2, 3} \dots} \\ 4 & \overset{―}{0, a_{3, 0} a_{3, 1} a_{3, 2} a_{3, 3} \dots} \\ ⋮ & ⋮ \end{array}$ Pilih bilangan $\overset{―}{0, b_{0} b_{1} b_{2} \dots}$ sehingga $b_{0} \neq a_{0, 0},$ $b_{1} \neq a_{1, 1},$ dan seterusnya, atau secara umum, $b_{i} \neq a_{i, i}$ untuk setiap $i = 0, 1, 2, \dots .$ Bilangan tersebut pasti tidak termuat di senarai. Dengan kata lain, tidak semua bilangan real di antara $0$ dan $1$ termuat di senarai. Penemuan ini kontradiktif dengan fakta bahwa terdapat korespondensi satu-satu dari $N$ ke $(0, 1) .$ Jadi, pengandaian salah. Disimpulkan bahwa subhimpunan bilangan real $(0, 1)$ taktercacah. Dengan demikian, himpunan bilangan real juga taktercacah karena $(0, 1) \subset R$ taktercacah. Lebih jauh, himpunan bilangan irasional, $R ∖ Q,$ juga taktercacah. Ini dikarenakan $R$ taktercacah, meskipun $Q$ tercacah.

[collapse]

Tag: Logika Matematika

Materi, Soal, dan Pembahasan – Pembuktian dengan Metode Kontradiksi

Today Quote

Soal Nomor 1

Soal Nomor 2

Soal Nomor 3

Soal Nomor 4

Soal Nomor 5

Soal Nomor 6

Soal Nomor 7

Soal Nomor 8

Soal Nomor 9

Soal Nomor 10

Soal Nomor 11

Soal Nomor 12

Soal Nomor 13

Soal Nomor 14

Soal Nomor 15

Soal Nomor 16

Soal Nomor 17

Soal Nomor 18

Soal Nomor 19

Soal Nomor 20

Soal Nomor 21

Soal Nomor 22

Soal Nomor 23

Soal Nomor 24

Soal Nomor 25

Soal Nomor 26

Soal Nomor 27