REDUCTIO AD ABSURDUM

Armahedi Mahzar (c) 2011

Bagian 6: Ikhtisar Simplifikasi Logika

Rangkaian blog Reductio ad Absurdum mengisahkan kisah pencarian sistem aksioma aljabar logika Boole yang tersederhana: baik oleh manusia semata, maupun dengan bantuan komputer.

Berikut ini adalah ringkasan blog-blog yang telah diposting sebelum ini. Tujuan dari ringkasan ini adalah memetakan perjalanan sejarah manusia untuk mengaksiomakan logika seekonomis mungkin.

Untuk bisa membandingkan berbagai aksioma yang secara signifikan maka saya di sini akan menyeragamkan perumusan aksioma tunggal itu dengan menggunakan simbolisasi Sheffer yang mendefinisikan operasi-operasi aljabar lain dengan satu operasi logika dasar yang menggabungkan TIDAK dengan DAN atau ATAU menjadi TIDAN alias NAND atau TATAU alias NOR yang disimbolkan oleh |.

Merumuskan Aksioma Logika

Dalam blog Reductio ad Absurdum bagian 1 dan bagian 2 diceritakan bagaimana logika yang ditemukan oleh Aristoteles dialjabarkan oleh George Boole dan kemudian aljabar Boole diaksiomakan berujung pada sistem aksioma Principia Mathematica yang merupakan linierisasi sistem simbolisasi planar Gotlobb Frege.

Dalam aksiomatisasi linier logika ini Russel-Whitehead mengambil dua operasi logika, yaitu TIDAK dan ATAU, sebagai operasi fundamental. Akan tetapi dalam perumusan aksioma-aksiomanya, Russel dan Whitehead menggunakan operasi gabungan JIKA x MAKA y yang didefinisikannya sebagai TIDAK(x) ATAU y.

Menyederhanakan Aksioma Logika

Dalam blog Reductio ad Absurdum bagian 3 ditunjukkan bagaimana usaha manusia untuk menyederhanakan aljabar Boole. Dimulai dengan Sheffer, matematikawan Amerika Serikat, yang menyederhanakan aksioma logika Russell-Whitehead , keduanya filsuf Inggris, dalam buku mereka Principia Mathematica.
Lalu matematikawan Perancis, Jean Nicod, pada tahun 1917 menurunkan semua Aksioma Sheffer dari sebuah aksioma tunggal dengan 5 variabel dan 11 operasi.
Tigabelas tahun kemudian, matematikawan Polandia Jan Lukasiewicz pada tahun 1931 menyederhanakan aksioma Nicod menjadi sebuah aksioma yang mengandung 4 variabel dan 11 operasi | atau NOR.

Kebuntuan Usaha Manusia

Dalam blog Reductio ad Absurdum bagian 4 dikisahkan bagaimana manusia mengalami kebuntuan untuk menyederhanakan aljabar Boole dengan hanya menggunakan operasi ATAU dan TIDAK.
Pada tahun 1933 Huntington menyederhanakan aksiomatisasi aljabar logika dengan menggunakan dua operasi fundamental yaitu ATAU dan TIDAK dengan tiga aksioma yaitu komutativitas, asosiativitas dan sebuah identitas logika yang kemudian disebut sebagai aksioma Huntington.

Muridnya pada tahun yang sama mengusulkan untuk mengganti aksioma Huntington dengan sebuah aksioma yang lebih sederhana yaitu aksioma Robbins. Namun sayang dia tak bisa membuktikan bahwa sistem aksioma baru itu merupakan basis bagi aljabar logika Boole.

Selama puluhan tahun, berbagai matematikawan dan logikawan berusaha untuk membuktikan kebenaran dugaan Robbins tersebut, namun selalu berujung pada kegagalan. Baru pada tahun 1996 William McCune berhasil membuktikan kebenaran dugaan Robbins itu dengan bantuan komputer.

Komputer Menuntaskan Penyederhanaan

Dalam blog Reductio ad Absurdum bagian 5 dikisahkan bagaimana komputer berhasil menuntaskan upaya penyederhanaan aljabar Boole. Misalnya William McCune pada tahun 2000 dengan bantuan komputer menemukan aksioma tunggal yang jika disingkat, dengan cara menuliskan NOR atau (x+y)' sebagai (x|y), mengandung 4 variabel, 6 operasi | dan 1 operasi '='


Namun berdasarkan daftar hasil komputasi Stephen Wolfram, yang menggunakan program Mathematica ciptaannya, McCune pada tahun 2000, dengan menggunakan program Otten ciptaannya, akhirnya dapat membuktikan identitas Wolfram itu adalah aksioma tunggal, bagi aljabar Boole, yang mengandung 3 variabel, 6 operasi | dan 1 operasi '='. Namun sayang identitas Wolfram bagi saya tidak mempunyai makna yang intuitif.

Kesimpulan sementara

Ternyata komputer sangat berguna untuk memecahkan masalah penyederhanaan aksiomatik logika sehingga pada akhirnya menemukan aksioma tersederhana bagi Aljabar Logika Boole.
Kenyataan ini seolah mengatakan pada kita bahwa komputer lebih hebat daripada manusia dalam penyelesaian masalah matematika, bukan hanya yang praktis numerik, tetapi juga yang abstrak teoritis non-numerik. Apakah memang betul demikian?

Blog-blog berikut akan mencoba menunjukkan bahwa kenyataan yang sebenarnya adalah kebalikannya. Aksioma Robbins ternyata akan menjadi aksioma tunggal jika kita merumuskan aljabar Boole dalam bentuk simbolisasi planar. Aksioma ini bahkan lebih sederhana lagi daripada aksioma Wolfram yang ditemukan komputer. Lebih dari itu, aksioma Robbins ini adalah simbolisasi dari sesuatu yang intuitif: reductio ad absurdum.

REDUCTIO AD ABSURDUM

Armahedi Mahzar (c) 2011

Bagian 5 : Mengkomputerkan untuk Menyelesaikan

Seorang pakar komputer, Winkler , kemudian pada tahun 1992 menemukan bahwa jika kita menambahkan pada sistem aksioma Robbins sebuah persyaratan tentang adanya dua elemen aljabar C dan D sehingga (C + D)' = (D)', maka aljabar Robbins identik dengan aljabar Boole. Dia membuktikan pernyataannya itu dengan menggunakan program komputer di lab Argonne.


Pada tahun 1996 William McCune dengan menggunakan sebuah perangkat lunak yang bernama EQP berhasil menemukan eksistensi kedua elemen itu dalam aljabar Robbins setelah menjalankan komputernya selama lebih dari lima hari waktu mesin.

Ini berarti tiga aksioma Robbins itu bisa seolah-olah merupakan merupakan basis yang terkecil bagi Aljabar Boole. Namun sebenarnya ada seorang matematikawan, Meredith, menemukan sebuah pasangan aksioma

(Meredith1) (x' + y)' +       x = x
(Meredith2) (x' + y)' + (z + y) = y + (z + x) 

sebagai basis terkecil bagi aljabar Boole.
Namun, dengan software Mathematica ciptaannya, Stephen Wolfram menemukan adanya 25 buah rumus yang mungkin digunakan sebagai aksioma tunggal yang hanya melibatkan 3 variabel dan 7 operasi jauh lebih sederhana dari aksioma tunggal Jean Nicod.

Namun McCune, ahli komputer yang berhasil membuktikan bahwa aljabar Robbins identik dengan aljabar Boole, menemukan sebuah aksioma tunggal saja

(McCune 1)       (((x+y)'+z)'+(x+(z'+(z+u)')')')' = z 

yang terdiri hanya terdiri dari 6 operasi ATAU, 7 operasi TIDAK dan 4 variabel. Ini lebih sederhana dari sistem aksioma Robbins yang menggunakan 9 operasi +, 4 operasi ' dan 3 variabel.
Bahkan dia akhirnya bisa membenarkan dugaan Wolfram itu melalui pembuktiannya secara komputasional dan menunjukkan salah satu dari 25 identitas logis Wolfram adalah sebuah aksioma tunggal lain dengan notasi NAND di mana a NAND b ditulis a|b sebagai berikut

(McCune 1')  (x|((y|x)|x))|(y|(z|x)) = y 

Namun, mengingat sifat simetri dualitas aljabar Boole, a|b dalam aksioma ini dapat dibaca juga sebagai a NOR b atau (a + b)' , sehingga aksioma ini dapat dituliskan sebagai

(McCune 1')       ((x+((y+x)'+x)')'+(y+(z+x)')')' = y 

yang terdiri dari 6 operasi dan 3 variabel. Rumus ini lebih sederhana dari aksioma yang ditemukan McCune terdahulu. Jadi rumus ini merupakan aksioma tersederhana yang ditemukan oleh komputer.

Namun, sebagai sebuah aksioma, dia sangatlah sulit untuk diinterpretasikan secara intuitif. Karena itu kita harus mencari jalur non-komputer untuk menyederhanakan hasil komputer ini lebih lanjut seperti yang akan diceritakan dalam blog berikut ini.

REDUCTIO AD ABSURDUM

Armahedi Mahzar (c) 2011

Bagian 4 : Menyederhanakan Aksioma Aljabar Logika

Perjalanan sejarah menunjukkan bahwa setelah aljabar proposisi logika Boole berhasil direduksi menjadi sistem 6 aksioma dan 2 operasi primitif dalam Principia Mathematica, reduksi ini terus berlanjut hingga ditemukannya sistem formal logika Jean Nicod dengan 1 aksioma 1 operasi. Namun sayangnya aksioma Nicod itu sangatlah panjang dan sangat sulit dipahami. Walaupun begitu sejarah juga menunjukkan bahwa ternyata ada jalan-jalan lain untuk menyederhanakan aljabar logika.

Memang, perumusan aksiomatik Russell - Whitehead dengan notasi linier lebih jelas dari pada sistemnya Frege yang menggunakan notasi 2-dimensi atau planar. Namun sayangnya, kedua penulis Principia Mathematica ini justru mengembalikan simbolisasi linier atau satu dimensi dalam penelitian matematika logika dan mereka pun telah menghilangkan perumusan pernyataan aljabar logika, sebagai persamaan, seperti yang ditemukan oleh Boole, menjadi sebuah rangkaian pernyataan JIKA MAKA.

Walaupun aksioma-aksioma Principia dituliskan dalam rangkaian JIKA MAKA, sebenarnya konsep operasional dasarnya adalah ATAU dan TIDAK. Dimana JIKA a MAKA b atau a->b dirumuskan sebagai TIDAK(a) ATAU b atau a' + b. Itulah sebabnya terjadilah upaya-upaya penyederhanaan dengan menggunakan persamaan-persamaan dengan notasi a + b untuk a ATAU b dan notasi a' untuk TIDAK(a) sebagai aksioma-aksioma.

Misalnya, pada tahun 1933 Edward Vermilye Huntington (1874-1952), matematikawan Amerika, membuat sistem aksiomatik dengan 3 aksioma 2 simbol (+ dan ') sebagai berikut

(Komutativitas)                  x + y = y + x
(Asosiativitas)            (x + y) + z = x + (y + z)
(Huntington)  (x' + y)' + (x' + y')' = x

Sistem ini berhasil menurunkan semua identitas logis dalam Aljabar Boole.


Tak lama kemudian muridnya, Herbert Ellis Robbins (1915-2001) mencoba menyederhanakan sistem aksioma Huntington menjadi sistem 3 aksioma berikut

(Komutativitas)                  x + y = y + x
(Asosiativitas)           (x + y) + z = x + (y + z)
(Robbins)    ( (x + y)' + (x + y')')' = x

Namun sayang, Robbins tidak bisa membuktikan bahwa aljabar yang dibangun dengan tiga aksioma ini adalah identik dengan aljabar Boole. Bahkan banyak matematikawan telah mencoba membuktikan secara manual bahwa aljabar Robbins identik dengan aljabar Boole, namun semuanya berujung pada kegagalan. Baru pada tahun 1996, sebelum Robbins meninggal dunia, akhirnya dugaannya itu dibuktikan benar oleh William McCune dengan bantuan komputer .

REDUCTIO AD ABSURDUM

Armahedi Mahzar (c) 2011

Bagian 3 : Mengaksiomakan Aljabar Logika

Maka, Bertrand Russel (1872-1972) dan Alfred North Whitehead (1861-1947) bekerja bersama untuk melinierkan kembali aljabar Frege   dan berupaya membangun seluruh matematika dari hanya enam buah aksioma logika saja. Walaupun nanti Kurt Godel (1906-1978) membuktikan bahwa ilmu hitung tak mungkin dibangun melalui sistem aksiomatik, keenam aksioma mereka tetap merupakan aksioma yang ekonomis untuk aljabar logika Boolean. Dia cukup menggunakan dua konsep yang primitif, operasi ATAU dan operasi TIDAK, dan enam pernyataan primitif atau aksioma.
Walaupun jumlah aksioma logika hampir sama dengan jumlah aksioma geometri, jumlah itu bukanlah jumlah yang paling ekonomis. Misalnya saja, pada tahun 1913 Henry Maurice Sheffer (1882-1964) berhasil mengurangi jumlah aksioma menjadi empat dengan hanya satu operasi yaitu TIDAN (TIDAK DAN) alias NAND atau TATAU (TIDAK ATAU) alias NOR. Ini berarti bahwa sistem aksioma Sheffer merupakan sebuah penyederhanaan bagi sistem aksioma logika dalam Principia. Namun itu belum cukup sederhana.
Misalnya, Jean George Pierre Nicod , matematikawan Perancis, berhasil mereduksi sistem aljabar logika Sheffer itu menjadi sistem formal dengan hanya menggunakan tiga buah aksioma saja. Bahkan pada akhirnya dia kemudian dapat mereduksi sistemnya sendiri menjadi sistem logika simbolik berbasis sebuah aksioma tunggal dengan satu simbol saja yaitu NAND alias NOT-AND, di mana x NAND y ditulis sebagai x|y.
Namun sayangnya aksioma tunggal ini sangatlah panjang, melibatkan lima variabel dan sama sekali tidak lah intuitif karena menggunakan operasi NAND.

((a|(b|c))|((e|(e|e))|((d|b)|((a|d)|(a|d)))))

Melihat kompleksnya aksioma tunggal itu, maka tentu saja orang akan berusaha menyederhanakannya lebih lanjut.
Misalnya, pada tahun 1931, Jan Lukasiewicz (1878-1956) berhasil mengurangi jumlah variabel dalam rumus Nicod menjadi empat dalam aksioma tunggal

((P|(Q|R))|((S|(S|S))|((S|Q)|((P|S)|(P|S)))))

Walaupun lebih sederhana, tetap saja tidak intuitif seperti halnya aksioma-aksioma geometri Euklides. Untuk mengurangi jumlah variabel menjadi tiga, tampaknya, dibutuhkan bantuan komputer seperti yang akan diceritakan nanti pada artikel yang kemudian.

REDUCTIO AD ABSURDUM

Armahedi Mahzar (c) 2011

Bagian 2 : Mengaljabarkan Logika

Semenjak ilmu Logika ditemukan oleh Aristoteles    ilmu tersebut dapat dikatakan sebagai bagian dari ilmu sastra karena kita harus menggunakan kata-kata dalam memaparkannya. Namun karena sulitnya, orangpun menciptakan berbagai macam simbol untuk menyingkat hukum-hukum itu, namun masih saja tetap sulit.

Filsuf Gottfried Wilhelm Leibniz di abad ke-17 masehi memimpikan logika sebagai cabang matematika, tetapi tak dapat menemukannya. Baru di abad XIX, George Boole (1815-1864) matematikawan Inggris menemukan Aljabar Logika. Dalam logika pernyataan-pernyataan yang BENAR dan SALAH digabungkan dengan operasi ATAU dan DAN. Untuk mematematikkan logika maka dia melambangkan BENAR dengan 1 dan SALAH dengan 0.
Boole melihat bahwa penggabungan DAN itu mirip dengan perkalian x. Soalnya pernyataan BENAR hanya menjadi BENAR hanya jika digabungkan melalui DAN dengan pernyataan lain yang BENAR, lain dari pada itu hasilnya adalah SALAH. Hal ini mirip dengan fakta ilmu hitung dimana 1 hanya menjadi 1 jika di kalikan dengan 1, lain dari pada itu hasilnya adalah 0. Dalam simbol ilmu hitung, ini berarti 1 x 1 = 1 dan 1 x 0 = 0 X 1 = 0 X 0 = 0. Mirip kan?
Namun, William Stanley Jevons (1835 –1882), filsuf Inggris, melihat bahwa logika mempunyai hukum aritmetika yang berbeda untuk operasi ATAU inklusif. Soalnya, dua pernyataan menjadi BENAR bila digabungkan melalui ATAU hanya jika salah satu pernyataan itu BENAR, selain dari pada itu hasilnya adalah SALAH. Jika ATAU disimbolkan dengan + maka pernyataan itu berarti 1 + 1 = 1 + 0 = 0 + 1 = 1 dan 0 + 0 = 0. Jadi 1 + 1 bukannya sama dengan 2 seperti dalam ilmu hitung, tetapi sama dengan 0.
Selanjutnya Boole melihat operasi logika TIDAK a mirip dengan operasi ilmu hitung 1 - a. Soalnya 1 - 1 = 0 mirip dengan TIDAK BENAR = SALAH dan 1 - 0 = 1 mirip dengan TIDAK SALAH = BENAR. Dengan demikian dia menemukan sebuah ilmu hitung logika yang hanya mempunyai nilai 1 dan 0 dan mempunyai tiga operasi aritmetika +, X dan -. Di atas aritmetika logika inilah dia membangun aljabar logika di mana terdapat hubungan-hubungan aljabar yang aneh seperti misalnya x x = x + x = x untuk semua harga x.
Pada akhir abad ke-19, Charles Sanders Peirce (1839-1914), matematikawan Amerika Serikat, dan Friedrich Ludwig Gottlob Frege (1848-1925) , matematikawan Jerman, merumuskan aljabar logika dengan simbolisasi dua dimensi atau gambar-gambar. Namun sayangnya, karena rumitnya notasi itu, maka penemuan mereka tidak populer di kalangan matematikawan yang terbiasa dengan untaian satu dimensi simbol-simbol matematik seperti pada ilmu hitung dan aljabar.

Armahedi Mahzar (c) 2011

REDUCTIO AD ABSURDUM

Bagian 1

Salah satu cara untuk membuktikan suatu pernyataan adalah dengan menunjukkan bahwa penyangkalan atau negasi pernyataan tersebut menyebabkan suatu pertentangan alias kontradiksi. Cara pembuktian seperti ini dalam tradisi logika abad pertengahan disebut sebagai "reductio ad absurdum"

Saya sudah lama mengetahui teknik pembuktian seperti itu karena anak SMP di zaman dulu diajari ilmu ukur dan Euklides lah yang membangun ilmu ukur secara aksiomatik dan dia kata http://mathworld.wolfram.com/ReductioadAbsurdum.html sangatlah mencintai metoda reductio ad absurdum ini.

Tentu saja waktu itu saya tak mengetahui nama Latin dari metoda tersebut. Belakangan saya mengenal metoda itu dari pembuktian tentang adanya Tuhan menurut St. Anselmus di abad XII, jika Tuhan didefinisikan sebagai Yang Maha Sempurna. Kalau Tuhan tidak ada maka berarti Dia tidak memiliki ada yang berarti tidak Maha Sempurna dan ini adalah suatu kontradiksi: Yang Maha Sempurna itu tidak sempurna. Jadi Tuhan itu wajib adanya.

Nah, ketika saya belajar logika modern yaitu logika Boole saya sudah lupa akan metoda itu, dan saya jatuh cinta pada logika Boole karena sifatnya yang simetris Dualitas. Bagi saya inilah keindahan alam cita. Kecintaan akan simetri itu akhirnya menyebabkan saya meneliti simetri partikel elementer untuk tugas akhir S1 dan skripsi S2.

Salah satu prinsip lain selain prinsip simetri adalah prinsip ekonomi dalam satu ilmu. Jika ada dua buah teori, untuk menjelaskan berbagai peristiwa, yang satu lebih sedikit pengertian dasarnya dibanding teori yang lain, maka teori yang pertama disebut lebih ekonomis. Teori yang ekonomis lebih disukai ketimbang teori yang kompleks.

Geometri Euklides adalah sebuah sistem matematika yang ekonomis. Semua hubungan geometris yang benar dapat dibuktikan secara logis sebagai konsekuensi dari hanya lima buah pernyataan intuitif yang disebut aksioma. Sistem aksioma Euklides adalah model bagi matematika lainnya. Misalnya, Giuseppe Peano (1858-1932), matematikawan Itali, membuat sembilan buah aksioma bagi membuktikan semua pernyatan-pernyataan ilmu hitung.

Dalam rangkaian artikel berikut ini saya akan menceritakan jalan bahwa upaya mengaksiomakan aljabar logika yang ditemukan oleh Boole yang ternyata berujung pada sebuah sistem aksiomatika paling ekonomis yang hanya memiliki sebuah satu operasi tunggal dan satu aksioma tunggal yang bisa diinterpretasikan sebagai reductio ad absurdum.