Pembuktian P≠NP?

Saya pernah menuliskan P vs NP, salah satu masalah dari 7 masalah millennium. Kita tahu dari ke-7 masalah baru satu yang berhasil dipecahkan yaitu Dugaan Poincare, yang dipecahkan oleh Grigoriy Perelman. Saat ini dunia matematika sedah dihebohkan oleh sekelompok peneliti dari Hp Labs yang dikepalai oleh Vinay Deolalikar, mereka membuat paper (silahkan mengunduh papernya di sini) pembuktian P≠NP. Yach..kita tunggu saja apa pembuktian mereka valid atau tidak, butuh waktu untuk menguji kebenaran dari pembuktian mereka, bahkan butuh waktu 7 tahun lamanya, pembuktian dugaan poincare oleh Parelman diakui oleh CMI.  Jika pembuktian mereka benar, mereka tidak hanya dapat 1juta dollar tapi nama mereka akan tercantum dalam sejarah matematika.

Silahkan klik di sini untuk melihat para matematikawan berdiskusi mengenai pembuktian tersebut. Saya tidak ikut nombrung soalnya saya tidak mengerti :)

———————————————————————————————————————————————-

**Ingin mendapatkan kaos unik bertema matematika silahkan kunjungi kaos.ariaturns.com**

Teorema Euler

Kita tahu teorema kecil fermat menyatakan

Untuk sebarang bilangan bulat a dan bilangan prima p yang coprime ke a berlaku
a^{p-1}\equiv 1\pmod p

Nah..sekarang bagaimana jika modulusnya tidak prima, composite, apakah teorema kecil fermat masih berlaku?
Tidak, sebgai contohnya jika kita ambil a=2 dan n=15,
apakah 2^{14}\equiv 1\pmod {15}
Tidak karena 15 tidak membagi 16383=2^{14}-1.
Akan tetapi ada cara memodifikasi teorema kecil fermat sehingga tetap berlaku meskupun modulusnya tidak prima. Teorema fermat yang udah dimodifikasi inilah yang disebut teorema euler.

Continue reading

Pembuktian rumus Heron

Boleh dibilang postingan  ini merupakan lanjutan dari postingan mengenai rumus heron. Jujur saya baru mengetahui mengenai rumus heron, padahal katanya di tingkat smp tu rumus sudah diperkenalkan. mmm…saya kok gak inget yach :)

Nah..kali ini saya ingin membuktikan rumus heron. Kita tahu luas segitiga=½×alas×tinggi. Itu artinya untuk membuktikan rumus heron, kita harus menunjukan

1/2\times alas\times tinggi=\sqrt{s\left(s-a\right)\left(s-b\right)\left(s-c\right)}

dengan s adalah semiperimeter s=\frac{a+b+c}{2}

Diberikan segitiga yang mempunyai sisi a, b c dengan a sebagai alasnya dan \alpha sudut diantara a dan b. Untuk membuktikan rumus heron, kita menggunakan hukum cosinus

\cos\alpha=\frac{a^{2}+c^{2}-c^{2}}{2bc}

diperoleh

\sin\alpha=\sqrt{1-\cos^{2}\alpha}=\frac{\sqrt{4a^{2}b^{2}-\left(b^{2}+c^{2}-a^{2}\right)^{2}}}{2ab}.

Diketahui tinggi segitiga adalah b\sin\alpha maka

1/2\times alas\times tinggi

\frac{1}{2}ab\sin\alpha

\frac{1}{4}\sqrt{4a^2 b^2 -(a^2 +b^2 -c^2)^2}

\frac{1}{4}\sqrt{(2a b -(a^2 +b^2 -c^2))(2a b +(a^2 +b^2 -c^2))}

\frac{1}{4}\sqrt{(c^2 -(a -b)^2)((a +b)^2 -c^2)}

\frac{1}{4}\sqrt{(c -(a -b))((c +(a -b))((a +b) -c))((a +b) +c)}

\sqrt{s\left(s-a\right)\left(s-b\right)\left(s-c\right)}

———————————————————————————————————————————————-

**Ingin mendapatkan kaos unik bertema matematika silahkan kunjungikaos.ariaturns.com**

Pembuktian yang pertama

Banyak Matematikawan yang percaya bahwa pembuktian matematika yang pertama kali ada, dilakukan oleh Euclid, 200 sm. Dia membuktikan

ada tak hingga banyaknya bilangan prima

Metode pembuktian yang digunakan Euler adalah kontradiksi

Bukti

Andaikan bilangan prima jumlahnya berhingga, p_{1}=2<p_{2}=3<p_{3}=5<\ldots<p_{r} adalah semua bilangan prima. Diperoleh N=p_{1}p_{2}p_{3}\ldots p_{r}+1 hasil perkalian semua bilangan prima plus 1. Jelas tidak ada satupun dari p_{1},p_{2},p_{3},\ldots p_{r} yang membagi N. Itu berarti terdapat bilang prima lain p yang merupakan faktor dari N dan bukan salah satu dari p_{1},p_{2},p_{3},\ldots p_{r}. Padahal diketahui p_{1},p_{2},p_{3},\ldots p_{r} adalah semua bilangan prima. Kontradiksi

Banyak orang yang salah kaprah yang beranggapan N=p_{1}p_{2}p_{3}\ldots p_{r}+1 merupakan bilangan prima baru. Bukan, bukan demikian, tetapi N mempunyai faktor prima p yang bukan salah satu dari p_{1},p_{2},p_{3},\ldots p_{r},

Contoh, andaikan bilangan prima hanyalah 2, 3, 5, 7, 11, 13 dan 17  Diperoleh 510511=2×3×5×7×11×13×17+1, jelas 510511 tidak dapet dibagi oleh 2, 3, 5, 7, 11, 13 dan 17. Karena 510511 akan selalu menyisakan 1 jika kita membaginya dengan sebarang bilangan-bilangan tersebut (2, 3, 5, 7, 11, 13 dan 17). Apakah 510511 prima? tidak, 510511=19x97x277.

———————————————————————————————————————————————-
**Ingin mendapatkan kaos unik bertema matematika silahkan kunjungi kaos.ariaturns.com**

Pembuktian dengan kontradiksi

Ada bermacam-macam metode pembuktian. Menurut wikipedia ada 14 metode pembuktian tetapi dari semua metode pembuktian yang ada, saya paling suka dengan metode perbuktian yang disebut “pembuktian dengan kontradiksi” (proof by contradiction). Berdasarkan pengalaman saya banyak teorema-teorema rumit yang dibuktikan melalui metode ini.  Ide dasar dari metode pembuktian ini cukup simple. Kita ingin membuktikan suatu pernyataan  P itu benar,? kita tinggal melihat negasi/ ingkaran dari P dinotasikan \neg P.  Jika \neg P itu salah, mustahil atau menyebabkan pertentangan/kontradiksi dengan asumsi2 yang telah diketahui, itu berarti P benar. Dalam matematika jika \neg P salah maka dengan sendirinya P benar, tidak ada pilihan lain begitu juga sebaliknya.

Jadi ada 2 langkah untuk melakukan pembuktian pernyataan P dengan metode kontradiksi

  1. Negasikan P dengan tepat
  2. Tunjukan bahwa \neg P itu salah mustahil atau menyebabkan pertentangan/kontradiksi dengan asumsi2 yang telah diketahui.

Nah..sekarang kita masuk ke contoh aja yach

Continue reading

Kuliah di Matematika, belajar apa saja?

Seorang cewek abg SMA, bertanya ke saya

Mas, Kuliah Matematika itu belajar apa aja to?

Saya jawab

Belajar definisi, teorema, pembuktian

Secara umum kuliah di (jurusan) Matematika hanya belajar tiga hal definisi, teorema dan pembuktian. Yang namanya mahasiswa pasti berkutat pada tiga hal tersebut.

1. Definisi

Definisi adalah penjelasan singkat tepat, jelas tidak ambigu mengenai suatu konsep matematika. Tidak mudah lho memahami suatu definisi. Contoh: {\displaystyle \lim_{x\rightarrow a}\, f(x)=L} didefinisikan

untuk sebarang bilangan real \epsilon>0 (\epsilon dibaca epsilon) maka  terdapat bilangan real  \delta>0 (\delta dibaca delta) dimana 0<|x-a|<\delta yang berakibat  |f(x)-L|<\epsilon

Jujur, saya butuh waktu 4 semester untuk memahami definisi limit. Bahkan menurut Prof. Widodo banyak lulusan matematika yang tidak memahami definisi limit. Dosen Pembimbing Skripsi saya sering berkata kita dilarang keras membuat definisi sendiri. Definisi harus berdasarkan dari literatur yang ada kecuali kita menciptakan konsep matematika baru yang belum pernah ada di literatur mana pun.

Continue reading

Pembuktian

Sory nich baru sempet update blog lagi, soalnya saya lagi sibuk skripsi. Kali ini saya pangen ngomongin mengenai “pembuktian”, blog ini bernama “proof (pembuktian)” tapi apakah kalian tahu apa itu “pembuktian” dalam matematika?

***

Di Sekolah kita diajarlan bagaimana memghitung luas lingkaran, menemukan solusi dari suatu persamaan, mencari nilai minimum suatu fungsi, okey matematika memang bisa melakukan itu tetapi Matematika bukanlah mengenai hal tersebut. Matematika adalalah Ilmu yang mempelajari hukum dibalik bilangan, aljabar, dan Geometri. Bagaimana menemukan hal yang baru dari suatu sistem, memperluas system yang ada, menjelaskan hubungan 2 buah objek, menjelas fenomena baru yang kita temukan, itulah matematika, bahkan dengan matematika kita bisa menciptakan sistem baru dengan menggunakan sistem yang sudah ada.

Matematika dan pembuktian

Di dalam matematika, jika kita berkata dua buah objek A dan B memepunyai hubungan/keterkaitan maka satu-satunya cara supaya orang percaya apa yang kita katakan adalah dengan membuktikannya.  Di matematika semua pernyataan/statement baik yang paling sulita maupun yang paling mudah membutuhkan pembuktian valid agar pernyatan tersebut diakui (pernyatan yang telah dibuktikan disebut teorema), inilah yang memebedakan Matematika dengan ilmu lainnya di TV kita sering melihat para tokoh mengeluarkan pernyataan politis tanpa ada pembuktiannya. Selama saya belajar matematika, saya menyimpulkan bahwa matematika “hanyalah”  kumpulan pernyataan beserta pembuktiannya yang terkumpul dalam wadah besar bernama logika. Lau sekarang apa itu pembuktian?

Continue reading

Lemma zorn dan pembuktian keberadaan tuhan

Ini masih lanjuntan dari postingan saya sebelumnya, kali ni saya mau menulis mengenai Lemma zorn

Lemma Zorn: Jika (S,\leq) adalah suatu poset dan setiap rantai didalamnya mempunyai batas atas maka (S,\leq) memepunyai elemen maksimal

Lemma Zorn berkata bagaimana suatu poset mempunyai elemen maksimal, menurut lemma zorn suatu poset akan mempunyai elemen maksimal jika setiap rantai didalamnya mempunyai batas atas. Lemma Zorn dan aksoma Pilihan adalah ekuivalen, itu artinya lemma zorn diperoleh dengan cara menurunkan aksioma pilihan begitu juga sebaliknya aksioma pilihan diperoleh dengan menurunkan lemma Zorn. Disini saya tidak akan menunjukan kedua hal tersebut ekuivalan, kenapa? Karna saya sendiri masih belum paham tentang ke-ekuivalansi-an kedua hal tersebut :mrgreen:

Continue reading

Pembuktian aturan l’hospital

Saya sudah pernah membuktikan aturan rantai, nah kali ini saya akan membuktikan aturan l’hospital, aturan yang sering kita gunakan dalam kalkulus

aturan l’hospital berkata

1. jika {\displaystyle \lim_{x\rightarrow c}f(x)=0} dan {\displaystyle \lim_{x\rightarrow c}g(x)=0} maka {\displaystyle \lim_{x\rightarrow c}\frac{f(x)}{g(x)}=\lim_{x\rightarrow c}\frac{f'(x)}{g'(x)}}

2. Jika {\displaystyle \lim_{x\rightarrow c}f(x)=\infty} dan {\displaystyle \lim_{x\rightarrow c}g(x)=\infty} maka {\displaystyle \lim_{x\rightarrow c}\frac{f(x)}{g(x)}=\lim_{x\rightarrow c}\frac{f'(x)}{g'(x)}}

Untuk membuktikan aturan l’hospital, kita membutuhkan teorema nilai tengah cauchy  cauchy mean value theorem yang berkata

Jika f(x) fungsi kontinyu pada interval tertutup \left[a,b\right] maka ada c elemen interval terbuka (a,b) dimana

{\displaystyle \frac{f'(c)}{g'(c)}=\frac{f(b)-f(a)}{g(b)-g(a)}}

Continue reading

Pembuktian e bilangan irasional

Saya sudah pernah menulis pembuktian pi bilangan irasional, nah kali ini saya akan membuktikan kalo e itu bilangan irasional. kita tahu e didefinisikan sebagai berikut

{\displaystyle e=\sum_{n=0}^{\infty}\frac{1}{n!}}

Kita asumsikan e bilangan rasional artinya e=a/b untuk suatu a dan b bilangan bulat positif. yang berakibat b!e adalah bilangan bulat positif.

kita jabarkan b!e diperoleh

{\displaystyle b!e=b!\sum_{n=0}^{\infty}\frac{1}{n!}}

{\displaystyle {\displaystyle b!e=\sum_{n=0}^{b}\frac{b!}{n!}+\sum_{n=b+1}^{\infty}\frac{b!}{n!}}}

Continue reading