1

Aturan Inferensi

x P(x) Universal instantiationP(c)

P(c) utk setiap c Universal generalization x P(x)

x P(x) Existential instantiationP(c) utk suatu c

P(c) utk suatu c Existential generalization x P(x)

2

Metode Pembuktian (1) Bukti langsung dan Tak langsung

1.1. Bukti LangsungBukti LangsungImplikasi p q dapat dibuktikan dengan menunjukkan jika p benar maka q juga harus benar.

Soal 9Soal 9. Berikan bukti langsung dari “Jika n bilangan bulat ganjil maka n2 ganjil.”

2.2. Bukti Tak langsungBukti Tak langsungKarena p q ekivalen dengan q p maka p q dapat dibuktikan dengan menunjukkan bhw q p benar.

Soal 10.Soal 10. Berikan bukti dari “Jika n2 ganjil maka n ganjil.”

3

Bukti kosong dan bukti trivial

Bukti kosongBukti kosong Jika hipotesis p dari implikasi p q salah, maka p q selalu benar, apapun nilai kebenaran dari q.

Contoh. P(n): Jika n > 1, maka n2 > 1.

Tunjukkan P(0) benar.

Bukti trivialBukti trivial Jika konklusi q dari implikasi p q benar, maka p q selalu benar, apapun nilai kebenaran dari p.

Contoh. P(n): Jika a, b integer positif dengan a b, maka an bn.

Tunjukkan P(0) benar.

4

Metode Pembuktian (2)Bukti dengan kontradiksi

1. Tunjukkan bahwa sedikitnya ada 4 hari yang sama dari pilihan 22 hari sebarang.

2. Buktikan bahwa 2 irasional.

bukti tak langsung bukti dg kontradiksi

3. Tunjukkan bahwa jika n2 ganjil maka n ganjil.

5

1.1. Bukti Eksistensi KonstruktifBukti Eksistensi Konstruktif1. Tunjukkan bahwa ada bilangan bulat positif yang dapat

dituliskan sebagai jumlah dua bilangan pangkat 3.Solusi. 1729 = 103 + 93 = 123 + 13.

2. Tunjukkan bahwa ada bilangan bulat positif yg sama dengan jumlah bilangan-bilangan bulat positif yg tidak melebihinya.

Metode Pembuktian (3)Bukti eksistensi

2. Bukti Eksistensi Nonkonstruktif2. Bukti Eksistensi NonkonstruktifTunjukkan bhw ada bilangan irrasional x dan y sehingga xy rasional.Solusi. Kita tahu bahwa 2 irrasional. Pandang 22. Jika ia rasional maka terbukti. Jika tidak, perhatikan (22)2= 22=2. Jadi terbukti ada pasangan (x=2, y =2) atau (x= 22 dan y= 2) yg salah satunya memenuhi xy rasional.

6

Metode Pembuktian (4)Bukti ketunggalan

Contoh. Tunjukkan bahwa setiap bilangan bulat mempunyai invers penjumlahan yang tunggal.Solusi. Jika p bulat maka p+q = 0 ketika q = -p, dan q juga bulat. Untuk menunjukkan ketunggalan, misalkan ada r bulat dengan r q dan p+r=0. Maka p+q = p+r. Dengan mengurangi kedua ruas dgn p didapat q=r, kontradiksi dgn r q. Jadi ada bilangan bulat q yang tunggal sehingga p+q=0.

Ada 2 bagian dalam bukti ketunggalan:Ada 2 bagian dalam bukti ketunggalan:• Menunjukkan bahwa ada elemen x yg memenuhi Menunjukkan bahwa ada elemen x yg memenuhi

sifat yg diinginkan. (sifat yg diinginkan. (existenceexistence))• Menunjukkan bahwa jika y Menunjukkan bahwa jika y x maka y tidak x maka y tidak

memenuhi sifat yg diinginkan. (memenuhi sifat yg diinginkan. (uniquenessuniqueness))

7

Metode Pembuktian (5)Contoh Penyangkal (Counter Example). Contoh Penyangkal (Counter Example).

Tunjukkan bahwa pernyataan“setiap bilangan bulat positif adalah hasil tambah dari

tiga bilangan kuadrat” adalah salah.

Solusi. Pernyataan ini benar untuk beberapa nilai, mis. 1=02+02+12; 2=02+12+12 ; 3=12+12+12 ; 4=02+02+22 ;

5=02+12+22 ; 6=12+12+22 . Tapi kita tidak dapat mengekspresikan seperti di atas untuk bilangan 7. Jadi bilangan 7 merupakan contoh penyangkal dari pernyataan di atas.