Pembuktian diagonal

Misalkan Andi, Budi, dan Cacing sedang membicarakan rasa yang mereka sukai untuk es krim, minuman, dan biskuit. Rasa yang mereka bicarakan adalah coklat, vanila, dan rendang. Mereka membuat tabel seperti di bawah ini.

Es krim Minuman Biskuit
Andi Coklat Coklat Vanila
Budi Rendang Coklat Rendang
Cacing Vanila Rendang Rendang

Dari tabel di atas, terlihat bahwa Andi menyukai es krim coklat, minuman coklat, dan biskuit vanila. Budi menyukai es krim rendang, minuman coklat, dan biskuit rendang. Cacing menyukai es krim vanila, minuman rendang, dan biskuit rendang.

Jika kita menyebutkan seseorang dengan ciri-ciri menyukai es krim rendang, minuman coklat, dan biskuit rendang, apakah orang tersebut ada di sana? Mungkin orang yang kita maksud adalah Budi, karena ciri-cirinya sesuai dengan yang disebutkan.

Es krim Minuman Biskuit
Andi Coklat Coklat Vanila
Budi Rendang Coklat Rendang
Cacing Vanila Rendang Rendang

Namun apakah orang itu pasti Budi? Bisa saja ada orang di luar daftar tersebut yang ciri-cirinya kebetulan sama dengan ciri-ciri Budi. Misalnya Dono.

Es krim Minuman Biskuit
Andi Coklat Coklat Vanila
Budi Rendang Coklat Rendang
Cacing Vanila Rendang Rendang
Dono? Rendang Coklat Rendang

Jadi ketika kita menyebutkan ciri-ciri tertentu yang sesuai dengan seseorang di antara mereka, itu tidak menjamin bahwa orang yang memiliki ciri-ciri tersebut adalah orang tersebut. Dalam hal ini, orang yang suka es krim rendang, minuman coklat, dan biskuit rendang bisa jadi Budi, tetapi bisa jadi bukan Budi.

Demikian juga orang dengan ciri-ciri menyukai es krim Vanila, minuman rendang, dan biskuit rendang tidak tentu Cacing.

Es krim Minuman Biskuit
Andi Coklat Coklat Vanila
Budi Rendang Coklat Rendang
Cacing Vanila Rendang Rendang
Susan? Vanila Rendang Rendang

Namun ketika kita menyebutkan seseorang dengan ciri-ciri menyukai es krim coklat, minuman coklat, dan biskuit rendang, pastilah orang itu tidak ada dalam daftar.

Untuk memeriksanya, kita memeriksa kesamaan ciri-ciri tersebut dengan Andi. Ternyata ada satu ciri-ciri yang berbeda, yaitu biskuit kesukaan Andi. Lalu dengan Budi, ciri-ciri es krim kesukaan berbeda. Demikian juga dengan Cacing, es krim maupun minuman berbeda.

Es krim Minuman Biskuit
Andi Coklat Coklat Vanila
Budi Rendang Coklat Rendang
Cacing Vanila Rendang Rendang
? Coklat Coklat Rendang

Jadi dapat disimpulkan orang dengan ciri-ciri tersebut pastilah tidak terdapat dalam daftar.

Jadi kamu bisa perhatikan di sini:

  • Ketika ada yang ketiga cirinya tepat sesuai, belum tentu orang yang dimaksud adalah orang itu.
  • Ketika ada yang tidak sesuai, pastilah yang dimaksud bukan orang itu.

Jadi kesesuaian tidak menjamin orang yang dimaksud ada dalam daftar, sementara ketidaksesuaian akan menjamin bahwa orang yang dimaksud tidak ada dalam daftar.

Menyebutkan ciri-ciri orang yang pasti di luar mereka

Ada sebuah algoritma yang pasti akan bisa menentukan bahwa orang yang memiliki ciri-ciri tertentu tidak mungkin salah satu dari mereka.

Pertama: Tuliskan diagonalnya. Tabel tersebut memiliki diagonal: Coklat, coklat, rendang.

Es krim Minuman Biskuit
Andi Coklat Coklat Vanila
Budi Rendang Coklat Rendang
Cacing Vanila Rendang Rendang
Diagonal Coklat Coklat Rendang

Diagonal dari tabel tersebut dibaca sebagai menyukai es krim coklat, minuman coklat, dan biskuit rendang.

Sekarang kita akan membentuk daftar ciri-ciri yang sama sekali tidak sesuai dengan diagonalnya. Misalnya vanilla, rendang, dan coklat, yang akan kita sebut sebagai diagonal (diagonal aksen).

Es krim Minuman Biskuit
Andi Coklat Coklat Vanila
Budi Rendang Coklat Rendang
Cacing Vanila Rendang Rendang
Diagonal Coklat Coklat Rendang
Diagonal' Vanila Rendang Coklat

Daftar diagonal’ tidak akan cocok dengan Andi, Budi, maupun Cacing, sehingga diagonal’, entah siapapun dia, pasti bukan salah satu dari mereka.

Jadi algoritma ini dapat menjamin bahwa orang dengan ciri-ciri yang disebutkan bukanlah salah satu dari mereka. Langkah-langkahnya dapat diringkaskan sebagai:

  1. Daftarkan ciri-ciri diagonalnya (D).
  2. Bentuk diagonal’ (D') yang ciri-cirinya berbeda seluruhnya dengan diagonal D.
  3. D' pasti tidak terdapat dalam daftar semula.

Algoritma ini akan kita gunakan untuk menunjukkan apakah banyaknya bilangan real pada interval (0,1) juga sama dengan banyaknya bilangan asli.

Berikutnya: Pembuktian diagonal untuk (0,1)

Ditulis oleh
Pak Ari
Ditulis pada
Terakhir diupdate
Dipublikasikan
Frase kunci
sejarah pemikiran tokoh