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.