1.6 RULES OF INFERENCE

1

Argumen

Argumen dalam logika adalah kumpulan sejumlah proposisi. Seluruh proposisi dalam suatu argumen, kecuali proposisi terakhir, disebut premis. Sedangkan proposisi terakhir disebut kesimpulan.

Suatu argumen dikatakan valid, apabila kebenaran seluruh premis mengakibatkan kebenaran dari kesimpulan.

Untuk mendeduksi proposisi baru dari proposisi yang telah ada sebelumnya, digunakan aturan inferensi untuk membangun argumen yang valid.

Aturan inferensi merupakan alat untuk menentukan kebenaran suatu argumen. Selain itu, dapat juga digunakan tabel kebenaran untuk menunjukkan bahwa suatu argumen valid. Namun ini tidak efisien dilakukan untuk argumen yang memuat banyak proposisi. 2

Contoh Argumen

Jika Anda memiliki password terkini, maka Anda dapat mengakses jaringan.Anda memiliki password terkini.

Maka,Anda dapat mengakses jaringan.

Argumen ini berbentuk:p qp q

3

Aturan Inferensi

4

Aturan Inferensi (2)

5

Soal 1

Tunjukkan bahwa premis:

Matahari tidak bersinar sore ini dan sore ini lebih dingin dari kemarin,

Kita akan berenang hanya jika matahari bersinar,

Jika kita tidak berenang, maka kita akan naik perahu, dan

Jika kita naik perahu, maka kita akan sampai ke rumah sebelum matahari terbenam

akan memberikan kesimpulan:

Kita akan sampai ke rumah sebelum matahari terbenam.

6

Soal 2

Tunjukkan bahwa premis

Jika Anda mengirim e-mail, maka saya akan menyelesaikan penulisan program,

Jika Anda tidak mengirim email, maka saya akan tidur lebih awal,

Jika saya tidur lebih awal, maka saya akan bangun dengan segar

akan memberikan kesimpulan:Jika saya tidak menyelesaikan penulisan program, maka saya

akan bangun dengan segar.

7

Argumen yang Tidak Valid

((p q) q) p bukan merupakan tautologi

Contoh 1.

Jika Anda mengerjakan setiap soal dalam buku teks, maka Anda akan belajar matematika diskrit.

Anda belajar matematika diskrit.

Jadi, Anda mengerjakan setiap soal dalam buku teks.

8

Aturan Inferensiuntuk Pernyataan Berkuantor

x P(x) Universal instantiation

P(c)

P(c) utk setiap c Universal generalization

x P(x)

x P(x) Existential instantiation

P(c) utk suatu c

P(c) utk suatu c Existential generalization

x P(x)

9

Soal 3

Tunjukkan bahwa premis:

Seorang mahasiswa di kelas ini tidak membaca buku teks dan

Semua peserta kelas ini lulus ujian

memberikan kesimpulan:

Seseorang yang lulus ujian tidak membaca buku teks.

10

Universal Modus Ponens

x(P(x) Q(x))

P(a), dengan a suatu anggota dari domain

Q(a)

Soal 4.

Asumsikan bahwa pernyataan Untuk setiap bilangan bulat positif n, jika n>4, maka n2

1.7 PENGANTAR BUKTI

12

Terminologi

Teorema adalah pernyataan yang dapatdibuktikan kebenarannya.

Teorema yang dianggap kurang penting (kurangberkontribusi) biasanya disebut proposisi.

Kebenaran teorema ditunjukkan denganmenggunakan bukti. Bukti adalah argumen valid yang menyatakan kebenaran suatu teorema.

Peryataan dalam suatu bukti dapat memuataksioma (atau postulat), yaitu pernyataan yang diasumsikan benar.

13

Terminologi (2)

Teorema yang kurang penting, namun membantu dalam membuktikan hasil lain disebut lema. Bukti yang sulit biasanya akan lebih mudah dipahami jika menggunakan sekumpulan lema, yang setiap lemanya dibuktikan tersendiri.

Akibat adalah teorema yang dapat dibuktikan secara langsung dari teorema lain.

Konjektur adalah pernyataan yang diajukan untuk menjadi pernyataan yang benar, biasanya berdasarkan bukti parsial, argumentasi heuristik atau intuisi seorang ahli. Apabila bukti untuk suatu konjektur ditemukan, maka konjektur akan menjadi teorema. Seringkali konjektur ditunjukkan salah, sehingga tidak menjadi teorema.

14

Kuantifikasi Universal dalam Teorema

Banyak teorema yang berlaku untuk seluruh anggota dari suatu domain, seperti bilangan bulat atau bilangan real. Walaupun pernyataan yang demikian memerlukan kuantifikasi universal, dalam teorema seringkali dihilangkan.

Contoh 2.

Pernyataan

Jika x > y, dengan x dan y bilangan real positif, maka x2 > y2.

Sebenarnya bermakna

Untuk setiap bilangan real positif x dan y, jika x > y, maka x2 > y2.

15

Bukti Langsung dan Bukti Tak Langsung

1. Bukti Langsung

Implikasi p q dapat dibuktikan dengan menunjukkanjika p benar maka q juga harus benar.

Soal 5. Berikan bukti langsung dari

Jika n bilangan bulat ganjil maka n2 ganjil.

16

2. Bukti Tak Langsung (Bukti dengan Kontraposisi)

Karena p q ekivalen dengan q p maka

p q dapat dibuktikan dengan menunjukkan bhw

q p benar.

Soal 6. Berikan bukti tak langsung dari

Jika n2 ganjil maka n ganjil.

Bukti Kosong dan Bukti Trivial

Bukti kosong

Jika hipotesis p dari implikasi p q salah, maka p q selalubenar, apapun nilai kebenaran dari q.

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

Tunjukkan P(0) benar.

17

Bukti trivial

Jika konklusi q dari implikasi p q benar, maka p q selalubenar, apapun nilai kebenaran dari p.

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

Tunjukkan P(0) benar.

Bukti dengan Kontradiksi

Bukti Tak Langsung (Bukti dengan Kontradiksi)

Misalkan kita ingin membuktikan bahwa pernyataan p benar. Di samping itu, kita bisa menemukan suatu kontradiksi q sehingga p q benar. Karena q salah, tetapi p q benar, kita dapat menyimpulkan bahwa p salah, yang berarti p benar.

Soal 9.

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

2. Buktikan bahwa 2 irasional.18

Bukti denganKontraposisi vs Kontradiksi

Bukti dengan kontraposisi dapat dituliskan kembali sebagai bukti dengan kontradiksi.

Dalam bukti dari p q dengan kontraposisi, kita mengasumsikan bahwa q benar. Kita kemudian menunjukkan bahwa p juga harus benar.

Untuk menuliskan kembali bukti dengan kontraposisi dari p q sebagai bukti dengan kontradiksi, kita misalkan bahwa p danq keduanya benar. Akibatnya, kita menggunakan langkah dalam bukti dari q p untuk menunjukkan bahwa p benar. Ini akan memberikan kontradiksi p p, yang merupakan akhir dari bukti.

Soal 10.

Berikan bukti dengan kontradiksi dari Soal 6

Jika n2 ganjil maka n ganjil. 19

Bukti dengan Ekivalensi

Untuk membuktikan teorema yang menggunakan pernyataan bikondisional, yaitu pernyataan dalam bentuk p q, kita menunjukkan bahwa

p q dan q p keduanya benar.

Pendekatan ini berdasarkan tautologi

(p q) (p q) (q p).

Soal 11.

Buktikan teorema

Jika n bilangan bulat, maka n ganjil jika dan hanya jika n2

ganjil.20

Contoh Penyangkal

Untuk menunjukkan bahwa suatu pernyataan dalam bentuk

x P(x) salah, kita hanya memerlukan satu contoh penyangkal, yaitu, contoh x sehingga P(x) salah.

Contoh 3.

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.

21

Kesalahan dalam Bukti

Soal 12.

Apa yang salah dalam bukti bahwa 1 = 2 ini?

Bukti: Misalkan a dan b bilangan bulat positif.

Langkah Alasan

1. a = b Diberikan

2. a2 = ab Kalikan kedua ruas di (1) dengan a

3. a2 b2 = ab b2 Kurangkan kedua ruas di (2) dengan b2

4. (a b)(a + b) = b(a b) Faktorkan kedua ruas di (3)

5. a + b = b Bagi kedua ruas di (4) dengan a b

6. 2b = b Ganti a dengan b di (5) dan sederhanakan

7. 2 = 1 Bagi kedua ruas di (6) dengan b

22

1.8 PROOF METHODS AND STRATEGY

23

PembuktianFinding proofs can be a challenging business

Matematikawan bekerja dengan memformulasi konjektur dan kemudian mencoba membuktikan bahwa konjektur tersebut benar atau salah.

Ketika dihadapkan dengan pernyataan yang akan dibuktikan:

terjemahkan setiap istilah dengan definisinya

analisa arti dari hipotesis dan kesimpulan

coba membuktikan dengan menggunakan salah satu dari metoda pembuktian

Jika pernyataan berupa implikasi; coba buktikan dengan bukti langsung. Bila gagal, coba dengan bukti tak langsung. Bila tidak berhasil juga coba dengan bukti kontradiksi.

Bukti dengan Kasus

Kadangkala kita tidak dapat membuktikan teorema dengan menggunakan argumen yang berlaku untuk semua kasus, sehingga digunakan bukti dengan mempertimbangkan kasus yang berbeda secara terpisah.

Untuk membuktikan pernyataan dalam bentuk

(p1 p2 pn) q

tautologi

[(p1 p2 pn) q] [(p1 q) (p2 q) (pn q)]

dapat digunakan sebagai aturan inferensi.

Soal 13.

Buktikan bahwa jika n adalah bilangan bulat, maka n2 n.

25

Contoh 4

Buktikan bahwa jika n bulat dan tidak habis dibagi oleh 2 atau 3 maka n2 1 habis dibagi 24.

Solusi.

n bilangan bulat dapat dinyatakan sebagai

n=6k+j, j {0,1,2,3,4,5}.

Karena n tidak habis dibagi oleh 2 atau 3 makan=6k+1 atau n=6k+5.

Jadi ada 2 kasus yg