PEMBUKTIAN MATEMATIKA • PEMBUKTIAN LOGIKA PREDIKAT • PEMBUKTIAN LANGSUNG • PEMBUKTIAN TAK LANGSUNG Altien Jonathan Rindengan, S.Si, M.Kom
Pembuktian Logika Predikat
Metode pembuktian pada dasarnya sama dengan pada logika proporsional Menggunakan dalil kesetaraan dan aturan inferensia Ditambah aturan-aturan dalam logika predikat
Pembuktian Logika Predikat ….
Contoh 1 Misalkan ada rangkaian proposisi : Setiap manusia pasti mati. Furlan adalah manusia. Oleh karena itu Furlan pasti mati. Buktikan bahwa kesimpulan ini adalah benar.
Pembuktian Logika Predikat ….
Jawab Buat predikatnya, misal : P(x) : x adalah manusia Q(x): x pasti mati
Argumen soal diatas menjadi : P1 : x [P(x) Q(x)] P2 : P(Furlan) K : Q(Furlan)
Pembuktian Logika Predikat ….
Untuk x = Furlan, menjadi : P1 : P(Furlan) Q(Furlan) P2 : P(Furlan) Q(Furlan) (modus ponens)
Karena kesimpulan Q(Furlan), terbukti benar.
Pembuktian Logika Predikat ….
Contoh 2 Tunjukkan bahwa pernyataan : x [P(x) -Q(x)] adalah kesimpulan dari premis-premis : x [-[-Q(x) -R(x)]] x [R(x) P(x)]
Pembuktian Logika Predikat ….
Jawab Argumen soal dapat ditulis : P1 : x [-[-Q(x) -R(x)]] P2 : x [R(x) P(x)] K : x [P(x) -Q(x)]
Untuk suatu nilai x = e, pada P1 berlaku : -[-Q(e) -R(e)] = -[Q(e) -R(e)] (tambahan) = -Q(e) R(e) (deMorgan)
Pembuktian Logika Predikat ….
Pada P2 berlaku : R(e) P(e) Dapat ditulis kembali : P11 : -Q(e) P12 : R(e) P21 : R(e) P12 : P(e)
Pembuktian Logika Predikat ….
Perhatikan P11dan P22 , berlaku : -Q(e) P(e) = P(e) -Q(e) (komutatif) Atau ditulis x [P(x) -Q(x)]
Terbukti benar
Pembuktian Logika Predikat ….
Contoh 3 Ada pasien yang menyukai semua dokter. Semua pasien tidak menyukai tukang obat. Maka disimpulkan bahwa semua dokter pasti bukan tukang obat Buktikan kebenaran dari argumen ini.
Pembuktian Logika Predikat ….
Jawab P(x) : Q(y) : R(y) : S(x,y) :
x adalah pasien y adalah dokter y adalah tukang obat x suka y
P1 : x [P(x) y (Q(y) S(x,y)] P2 : x [P(x) y (R(y) -S(x,y)] K : y [Q(y) -R(y)]
Pembuktian Logika Predikat …. Untuk suatu nilai x=e berlaku : P1 : [P(e) y (Q(y) S(e,y)] P2 : [P(e) y (R(y) -S(e,y)]
Dapat ditulis : P11 : P(e) P12 : y (Q(y) S(e,y)) P21 : P(e) P22 : y (R(y) -S(e,y)) = y (S(y) -R(e,y)) (kontrapositif)
Pembuktian Logika Predikat ….
Perhatikan P12 dan P22 : P12 : y (Q(y) S(e,y)) P22 : y (S(e,y) -R(y)) y (Q(y) -R(y)) Terbukti benar karena K : y [Q(y) -R(y)]
(silogisme)
Pembuktian Logika Predikat ….
Latihan Tunjukkan bahwa pernyataan : x [F(x) -S(x)] adalah kesimpulan dari premis-premis : x (F(x) S(x)) y(M(y) W(y)) y(M(y) -W(y))
Pembuktian Langsung
Misalkan p dan q adalah proposisi. Pembuktian langsung p q (p implikasi logik ke q) adalah dengan mengkonstruksi proposisi-proposisi r1, r2, …, rn, sedemikian sehingga p r1, r1 r2, r2 r3, … , rn q
Pembuktian Langsung ….
Contoh 4 Buktikan bahwa kuadrat bilangan ganjil adalah juga bilangan ganjil.
Pembuktian Langsung ….
Jawab Misalkan p : n bilangan ganjil q : n2 bilangan ganjil p : n bilangan ganjil r1 : n = 2k + 1 , kZ r2 : n2 = (2k + 1)2 r3 : n2 = 4k2 + 4k + 1 r4 : n2= 2(2k2 + 2k) + 1 r5 : n2= 2m + 1 , m=(2k2 + 2k) Z q : n2 bilangan ganjil.
Conditional Proof
Conditional proof adalah pembuktiam proposisi yang berbentuk implikasi. Contoh 5 Buktikan, jika m adalah bilangan bulat genap dan n bilangan bulat ganjil maka m + n adalah bilangan bulat ganjil.
Conditional Proof ….
Jawab Misalkan m = 2k , kZ n = 2j + 1 , jZ m + n = 2k + 2j + 1 = 2(k +j) + 1 = 2 p +1 , pZ
Pembuktian Tak Langsung
Ada dua jenis pembuktian tak langsung yaitu : (1) Pembuktian Kontrapositif (2) Pembuktian Kontradiksi Kedua jenis pembuktian ini dimulai dengan memisalkan kesimpulan q salah, dengan kata lain memisalkan –q benar.
Pembuktian Tak Langsung ….
1. Pembuktian Kontrapositif Menurut aturan kontrapositif, menunjukkan kebenaran proposisi p q sama dengan menunjukkan - q -p.
Contoh 6 Buktikan, jika n2 genap maka n genap untuk n bilangan bulat.
Pembuktian Tak Langsung ….
Jawab Misalkan p : n2 genap -p : n2 ganjil q : n genap -q : n ganjil maka pq : jika n2 genap maka n genap setara dengan - q -p : jika n ganjil maka n2 ganjil proposisi ini sudah dibuktikan pada contoh 1 tadi.
Pembuktian Tak Langsung ….
2. Pembuktian Kontradiksi Pada pembuktian kontradiksi, akan dimulai dengan memisalkan q salah dan selanjutnya ditunjukkan terdapat pernyataan yang kontradiksi sehingga disimpulkan haruslah q benar.
Contoh 7 Misalkan a bilangan real, jika a > 0 maka
1 a
> 0.
Pembuktian Tak Langsung ….
Jawab Anggap pernyataan a > 0 benar dan
Proposisi ini akan menjadi a > 0 dan
1 a 1 a
> 0 salah. 0.
Berdasarkan sifat perkalian diperoleh a( 1a ) 0 10 Akan kontradiksi dengan kenyataan bahwa 1>0. Jadi haruslah 1a > 0.
