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

Negasikan P dengan tepat
Tunjukan bahwa \neg P itu salah mustahil atau menyebabkan pertentangan/kontradiksi dengan asumsi2 yang telah diketahui.
Nah..sekarang kita masuk ke contoh aja yach

Teorema 1: Tidak ada ada bilangan asli n yang lebih besar dari semua bilangan bulat lainnya

Bukti

Apa ingkaran dari teorema 1? Ingkarannya adalalah

Bilangan n tersebut eksis.

Padahal menurut postulat peano, n+1 merupakan bilangan asli. Jadi negasi teorema 1 bertentangan dengan postulat peano maka bisa disimpulkan teorema 1 benar.

***

Contoh lainnya

Teorema 2: Semua bilangan real tak nol mempunyai invers perkalian yang tunggal

(Note: x dikatakan invers perkalian dari y jika xy=1)

Bukti:

Apa ingkaran dari teorema 2? Ingkarannya adalah

Ada bilangan real yang mempunyai invers perkalian yang tidak tunggal

Sebut saja bilangan tersebut x yang mempunyai 2 buah invers perkalian yang berbeda a dan b (a≠b). Diperoleh

ax=1 dan bx=1

ax=bx

bagi kedua sisi dengan x diperoleh

a=b

Padahal kita mensyaratkan a dan b berbeda. Jadi mustahil ada bilangan real yang memepunyai inver perkalian tak tunggal.

***

Implikasi

Jika pernyataan yang hendak kita buktikan berbentuk implikasi A\Rightarrow B maka negasinya \neg\left(A\Rightarrow B\right) ekuivalen dengan A\wedge\neg B, ini bisa kita cek melalui tabel kebenaran. Jadi untuk membuktikan pernyataan berbentuk implikasi A\Rightarrow B dengan metode kontradiksi, kita harus membuktikan A\wedge\neg B salah. Cara terbaik untuk menunjukan A\wedge\neg B salah adalah dengan mengasumsikan A benar lalu tunjukan A dan \neg B saling kontradiksi, saling bertentangan.

Sekarang kita masuk ke contoh yach

Teorema 3: Jika n^2 genap maka n genap.

Teorema 3 berbentuk implikasi dengan kaliamat A menyatakan n^2 genap dan kalimat B menyatakann genap

Bukti: Diketahui n^2 genap (kita asumsikan A benar)

Andaikan n ganjil (negasi dari B)

Karena n ganjil maka n bisa ditulis dengan bentuk

n=2m+1 dengan m bilangan bulat

Diperoleh

n^2=(2m+1)^2

n^2=4m^2+4m+1

n^2=2(2m^2+2m)+1

Itu berarti n^2=2(2m^2+2m)+1 ganjil. Kontradiksi dengan asumsi “n^2 genap” karena terjadi kontradiksoi maka dapat disimpulkan teorema 3 benar.

***

Contoh selanjutnya.

Teorema 4: Jika x rasional dan y irasional maka x+y irasional

Bukti

Diketahui x rasional dan y irasional

Andaikan x+y rasional

karena x rasional maka -x rasional pula. Penjumlahan 2 bilangan rasional adalah rasional, diperoleh

{\displaystyle \underbrace{\left(x+y\right)}_{\textrm{rasional}}+\underbrace{\left(-x\right)}_{\textrm{rasional}}=y}

Itu berari y rasional padahal diketahui y irasional. Terjadi kontradiksi maka teorema 4 benar.

Harus dinegasikan dengan tepat.

Seperti yang sudah saya katakan diatas, langkah pertama untuk melakukan metode pembuktian dengan kontradiksi adalah menegasikan pernyataan dengan tepat, karna kalau tidak tepat metode tersebut tidak berlaku. Contoh kasus penegasian yang tidak tepat, dilakukan oleh para penganut teori penciptaan (Creationism), mereka berpendapat bahwa teori penciptaan adalah negasi dari teori evolusi. Oleh karena itu mereka sekuat tenaga membuktikan evolusi itu salah, mereka berpendapat jika evolusi salah maka itu membuktikan penciptaan bener. Mereka membuktikan teori penciptaan dengan metode kontradiksi. Nah..sekarang pertanyaannya apakah teori penciptaan adalah negasi dari evolusi? apakah teori evolusi adalah ingkaran dari teori penciptaan?

Nah sekarang mari kita lihat teori penciptaan berkata “mahluk hidup dan segala jenisnya diciptakan oleh sang pencipta secara sempurna” jika kita negasikan maka menjadi “mahluk hidup dan segala jenisnya TIDAK diciptakan oleh sang pencipta secara sempurna”, apakah teori evolusi mengatakan seperti itu? TIDAK!!, evolusi tidak berbicara mengenai sang pencipta, tidak berbicara mengenai bagaimana mahluk hidup diciptakan tetapi berbicara mengenai perubahan sifat-sifat yang diwariskan dalam suatu populasi organisme dari satu generasi ke generasi berikutnya , tidak ada sangkut-pautnya dengan sang pencipta atau bagaimana mahluk hidup diciptakan. Jadi jika evolusi salah sekalipun itu sama sekali tidak membuktikan penciptaan karean evolusi bukanlah negasi dari penciptaan.

sumber

Logika adalah cabang ilmu pengetahuan yang mempelajari tentang penalaran yang berhubungan dengan pembuktian validitas suatu argumen. Logika menggunakan metode penalaran berdasarkan validitas suatu argumen. Logika memberikan suatu metode atau cara yang sistematis dalam berpikir (reasoning). Terdapat dua metode cara berpikir yang digunakan, yaitu logika proposisi (proposisional) dan predikat (predikatif). Dengan menggunakan logika diharapkan dapat mengurangi kesalahan tindakan dalam menghadapi dan menyelesaikan masalah, sehingga masalah tersebut dapat diselesaikan dengan suatu jawaban yang dikerjakan dengan sistematis. Cara berpikir dengan benar dengan dasar logika ini dapat dijadikan program dan dapat dilaksanakan oleh komputer, sehingga komputer dapat melakukan kemampuan berpikir walaupun secara sederhana.

Logika Proposisional

– Pernyataan dan Proposisi Pernyataan adalah kalimat yang dapat atau belum dapat ditentukan nilai kebenarannya. Pernyataan yang dapat ditentukan nilai kebenarannya benar atau salah, tapi tidak keduanya adalah proposisi. Sedangkan pernyataan yang belum tentu nilai kebenarannya sering disebut fungsi proposisi atau kalimat terbuka.

Contoh pernyataan dengan bahasa :

=== DPR adalah kumpulan orang hebat.

=== Massa jenis batu lebih besar daripada massa jenis kayu.

Kalimat pertama merupakan pernyataan yang belum dapat ditentukan nilai kebenarannya, karena kata DPR bersifat relatif. Sedangkan kalimat kedua merupakan proposisi, karena nilai kebenarannya dapat ditentukan yaitu TRUE (benar). Contoh pernyataan dalam matekatika :

Y = 34
43 + 87 = 342

Pernyataan pertama adalah fungsi proposisi, karena nilai kebenarannya tergantung kepada nilai variabel y. Sedangkan pernyataan kedua merupakan proposisi, karena dapat ditentukan kebenarannya yaitu FALSE (salah).

Contoh di dunia informatika (misal pemrograman java) :

a <= 30%4;
y == 24; y = 4*6;

Kalimat pertama nilai kebenarannya relatif, tergantung pada pernyataan yang mengikutinya (kalimat terbuka). Sedangkan kalimat kedua dapat ditentukan nilai kebenarannya karena nilai y sudah ditentukan yaitu 20 (proposisi). Logika proposisional adalah pernyataan majemuk yang disusun dari pernyataan-pernyataan sederhana yang dihubungkan dengan penghubung Boolean (Boolean Connectives).

– Notasi Seringkali, beberapa kalimat perlu digabungkan untuk menjadi kalimat yang lebih panjang. Misalnya kalimat “8 adalah bilangan genap dan habis dibagi 3” merupakan gabungan dari kalimat “8 adalah bilangan genap” dan kalimat “9 habis dibagi 3”. Dalam logika proposisional dikenal enam macam penghubung (connective), yaitu not, and, or, if-then, if-and-if-only, serta if-then-else.

Berikut adalah notasi dari penghubung pada logika proposisional :

Contoh penulisan dengan notasi konvensional dari kalimat :

(if ((p or q) and (if q then r)) then (if (p and q) then (not r))) adalah : ((p V q) /\ (q → r)) → ((p /\ q) → ~r)

– Interpretasi Interprestasi adalah pemberian (assignment) nilai kebenaran (true atau false) pada setiap simbol proposisi dari suatu kalimat logika.

Sebagai contoh, perhatikan kalimat : not p or q

Salah satu interprestasi untuk kalimat di atas memberi nilai false ke p dan nilai true ke q. interprestasi terhadap nilai p dan q dapat ditulis:

p <=== false q <=== true

Semua kemunculan dari suatu simbol proposisional dalam kalimat logika akan diberi nilai sama oleh suatu interprestasi yang diberikan, sebagai contoh kalimat :

not p and (not q) or p

Dua kemunculan p masing-masing akan diberi nilai sama. Demikian juga kemunculan terhadap proposisi q.

– Aturan Semantik Aturan semantik adalah suatu aturan yang digunakan untuk menentukan arti suatu kalimat logika atau nilai kebenaran (truth value) dari suatu kalimat (sentence). Berikut adalah aturan-aturan semantik untuk kalimat logika :

Negasi (NOT)

Konjungsi (AND)

Konjungsi bernilai benar apabila kedua proposisi penyusunnya bernilai benar. Apabila salah satu proposisi penyusunnya bernilai salah, atau bahkan keduanya bernilai salah, maka konjungsi bernilai salah (false).

Disjungsi

Disjungsi bernilai salah apabila kedua proposisi penyusunnya bernilai salah. Apabila salah satu proposisi penyusunnya bernilai benar, atau bahkan keduanya bernilai benar, maka konjungsi bernilai benar (true). Dari aturan konjungsi dan disjungsi, muncul sifat-sifat aljabar logika, yaitu :

– Hukum Idempoten p v p = p p /\ p = p

– Hukum Komutatif p v = q v p p /\ q = q /\ p

– Hukum Asosiatif (p v q) v r = p v (q v r) (p /\ q) /\ r = p /\ (q /\ r)

– Hukum Distributif p v (q /\ r) = (p v q) /\ (p v r) p /\ (q v r) = (p /\ q) v (p /\ r)

– Hukum Identitas p v false = p p /\ true = p p v true = true p /\ false = false

– Hukum Komplemen p v ~p = true p /\ ~p = false ~(~p) = p

– Hukum De Morgan ~(p v q) = ~p v ~q ~(p /\ q) = ~p /\ ~q

Implikasi (IF-THEN)

Implikasi bernilai “false” bila anteseden “true” dan konsekuen-nya bernilai “false”.

Jika (p → q) adalah implikasi maka (q → p) adalahkonvers, (~p → ~q) adalah invers, dan (~q → ~p) adalahkontraposisi. Jika (p → q) bernilai “true” maka belum tentu(q → p), (~p → ~q), (~q → ~p) bernilai “true”.

Ekuivalensi (IF-AND-IF-ONLY)

Ekuivalensi atau biimplikasi bernilai “true” jika nilai kebenaran dari proposisi penyusunnya adalah sama.

Kondisional (IF-THEN-ELSE)

Nilai kebenaran dari kondisional (yaitu if p then q else r) adalah sama dengan nilai kebenaran dari q(jika nilai p adalah true) dan bernilai sama dengan r(jika nilai p adalah false). Dengan kata lain, jika pbenar berlaku q dan jika p salah maka yang berlaku adalah r.

– Tabel Kebenaran

Tabel kebenaran adalah suatu metode untuk menentukan nilai kebenaran dari suatu kalimat logika dengan menginterpretasi setiap simbol proposisi dan menggunakan aturan semantik (semantic rule). Table kebenaran adalah cara yang paling jelas untuk membuktikan validitas suatu kalimat dengan menentukan kemungkinan nilai-nilai kebenaran yang diberikan pada simbol-simbol proposisinya. Jadi, bila suatu kalimat memuat simbol-simbol proposisi p dan q, ada empat kemungkinan interpretasi yang perlu kita perhatikan, yaitu: p bernilai “true” dan q bernilai “true” p bernilai “true” dan q bernilai “false” p bernilai “false” dan q bernilai “true” p bernilai “false” dan q bernilai “false” Proses tersebut dapat difasilitasi dengan suatu tabel, yang disebut tabel kebenaran.

– Pohon Semantik Pohon semantik adalah metode lain untuk menentukan nilai kebenaran (truth value) dari suatu kalimat logika, yaitu dengan menggunakan kalimat teknik semantik. Teknik ini akan digambarkan sebagai mana berikut: If( p if and only if q) then( if (not q) then (p and r) Kalimat di atas adalah kalimat yang valid. Artinya, semua intepretasi yang dimungkinkan setiap simbol proposisi akan menghasilkan nilai “true”.

Pada gambar berikut, ada dua kemungkinan interpretasi yang diberikan pada proposisi q, yaitu true dan false.

Pada pohon semantik di atas, nilai q adalah true di node 2.

Dengan demikian, untuk menunjukkan nilai kebenaran dari kalimat logika tersebut, setiap kemunculan proposisi q ditandai dengan huruf T (yang artinya, proposisi q diintepretasi dengan nilai true).

if(p if and only if q)then (if (not q) then (p and r)

Setelah kemunculan proposisi p diintepretasi dengan nilai T maka nilai dari not p adalah F (false) sesuai negation rule. Selanjutnya, berdasarkan aturan sematik (implication rule), nilai kebenaran dari if(not q) then (p and r) adalah true, tanpa harus mengetahui nilai dari ( p and r ). Karena nilai dari if(not q) then (p and r) adalah true maka nilai kalimat logika secara keseluruhan bernilai true. – Sifat-sifat kalimat logika Suatu kalimat logika, setelah proposisi – proposisi penyusunnya diinterpretasi dengan nilai true dan false, akan menghasilkan suatu nilai kebenaran.

Ada tiga katagori nilai yang dihasilkan, yang menunjukkan sifat dari kalimat logika tersebut. Sifat-sifat yang dimiliki kalimat logika adalah valid, satisfiable, dan kontradiksi ( contradictory ). Valid (Tautologi) Suatu kalimat logika f bersifat valid jika untuk setiap interpretasi I for f, f bernilai true. Contoh:

(f and g) if and only if ( g and f)
F or not f
[p and (if r then s)] if only if [if r then s) and p]
(p or q) or not (p or q)
(if p then not q) if and only if not (p and q)
If (if p then q) then q
(if p then q) and (not r and s)
(if p then q) or r

Kontradiksi Suatu kalimat logika f bersifat kontradiksi jika untuk setiap interpretation I for f, f bernilai false. Contoh:

p and not p
[(p or q) and not r] if and only if [ (if p then r) and (if q then r)]

– Metode Inferensi

Metode inferensi adalah suatu teknik/metode untuk menurunkan kesimpulan berdasarkan hipotesa yang diberikan, tanpa harus menggunakan table kebenaran. Beberapa metode inferensi untuk menentukan validitas adalah sebagai berikut :

Modus Ponens

Pada suatu implikasi “jika p maka q” yang diasumsikan bernilai benar, dan apabila juga diketahui bahwa nilai dari anteseden (p) bernilai benar, maka nilai q juga harus benar. p —> q p q

Contoh :

Jika suatu bilangan habis dibagi 2 maka bilangan tersebut adalah bilangan genap.

Suatu bilangan habis dibagi 2.

Bilangan tersebut adalah bilangan genap.

Modus Tollens

Suatu implikasi “jika p maka q” akan selalu ekuivalen dengan kontraposisinya, yaitu “jika bukan q maka bukan p”. dengan demikian, hipotesa kedua dan kesimpulan merupakan kontraposisi hipotesa pertama pada modus ponens. p –> q ~q ~p

Contoh :

Jika hasil jual lebih dari hasil beli maka penjual itu untung.

Penjual itu tidak untung.

Hasil jual tidak lebih dari pembelian.

Silogisme

Prinsip Silogisme adalah sifat transitif dari implikasi. Artinya, jika suatu implikasi p à q dan q à r keduanya bernilai benar maka implikasi p à q pasti bernilai benar. p –> q q –> r p –> r

Contoh :

Jika ia belajar dengan baik maka ia akan pandai.

Jika ia pandai maka ia akan lulus dalam ujian.

Jika ia belajar dengan baik ia akan lulus dalam ujian.

Sumber : https://exclusivenine.wordpress.com/2013/09/20/lsd-1-logika-proposisi/