MATEMATIKA DISKRIT ISTRATEGI PEMBUKTIAN

MENGAPA KITA PERLU MEMBUKTIKANhttp:/www2.edc.org/makingmath

to establish a fact with certaintyto gain understanding

to communicate an idea to othersfor the challenge

to create something beautifulto construct a large mathematical theory

2

TUJUAN PERKULIAHANMemperkenalkan bagaimana cara membuktikan

Membiasakan diri dengan metode – metode pembuktian yang ada

Mampu membuktikan sendiri teorema – teorema yang ada

3

METODE PEMBUKTIANBeberapa cara untuk membuktikan implikasi p q

Pembuktian TrivialPembuktian Vacuous

Pembuktian LangsungPembuktian Tak Langsung (Pembuktian dengan Kontradiksi)

Pembuktian dengan KontrapositifPembuktian dengan Kasus

4

METODE PEMBUKTIANBukti untuk membuktikan pernyataan xP(x)

Bukti Eksistensi Bukti konstruktif Bukti nonkonstruktif

Bukti untuk membuktikan pernyataan xP(x)Bukti Noneksistensi

5

TABEL KEBENARAN

p q p qB B BB S SS B BS S B

6

PEMBUKTIAN TRIVIALJika kita tahu q bernilai benar maka p q benar terlepas dari nilai kebenaran p.

7

p q p qB B BB S SS B BS S B

Dikatakan p q kebenaran trivial jika q benar.

PEMBUKTIAN VACUOUS

8

Jika kita tahu p bernilai salah maka p q benar terlepas dari nilai kebenaran q.

p q p qB B BB S SS B BS S B

Dikatakan p q kebenaran vacuous jika p salah.

PEMBUKTIAN LANGSUNGAsumsikan p, kemudian gunakan aturan inferensi, definisi, aksioma, dan ekivalensi logika untuk membuktikan q.

Soal.Buktikan: untuk semua m dan n bilangan bulat, jika m dan n bilangan bulat ganjil maka m + n adalah bilangan bulat genap.

9

PEMBUKTIAN LANGSUNGJika m dan n bilangan bulat ganjil

m = 2k1 + 1n = 2k2 + 1

maka m + n adalah bilangan bulat genapm + n = (2k1 + 1) + (2k2 + 1)

= 2k1 + 2k2 + 2= 2(k1 + k2 + 1)

10

PEMBUKTIAN DENGAN KONTRADIKSIAsumsikan p dan q sehingga diperoleh kontradiksi r dan r.

Soal.Misal x dan y bilangan real. Jika 5x + 25y = 1723, maka x atau y bukan bilangan bulat.Buktikan bahwa adalah bilangan irrasional.

11

2

PEMBUKTIAN DENGAN KONTRAPOSITIFUntuk membuktikan p q, lakukan dengan cara membuktikan secara langsung q p.Asumsikan q kemudian gunakan aturan inferensi, definisi, aksioma, dan ekivalensi logika untuk membuktikan p.

Soal.Buktikan: untuk semua m dan n bilangan bulat, jika perkalian m dan n bilangan genap, maka m genap atau n genap.

12

PEMBUKTIAN DENGAN KASUSJika hipotesa p dapat dipisahkan menjadi kasus

p1 p2 … pk qbuktikan untuk masing – masing proposisi

p1 q, p2 q, …, pk qsecara terpisah.

Soal.Tunjukkan bahwa jika n bilangan bulat positif maka n3 + n bilangan genap.

13

PEMBUKTIAN DENGAN KASUSTunjukkan bahwa jika n bilangan bulat positif maka n3 + n bilangan genap.Kasus 1. Misal n genap. Maka terdapat k ℕ sedemikian sehingga n

= 2k. Pada kasus ini n3 + n = (2k)3 + 2k = 2(4k3 + k)

yang merupakan bilangan genap.

Kasus 2. Misal n ganjil. Maka terdapat k ℕ sedemikian sehingga n = 2k + 1. Jadi

n3 + n = (2k + 1)3 + (2k + 1) = 2(4k3 + 6k2 + 4k + 1)yang merupakan bilangan genap.

14

PEMBUKTIAN EKSISTENSIPembuktian eksistensi digunakan untuk membuktikan pernyataan berbentuk x P(x).

Terdiri dari:1. Bukti Konstruktif

Terdapat bilangan bulat (a, b, c) sedemikian sehingga memenuhia2 + b2 = c2

2. Bukti NonkonstruktifPrinsip Sarang Merpati

15

PEMBUKTIAN NONEKSISTENSIPembuktian eksistensi digunakan untuk membuktikan pernyataan berbentuk [x P(x)], atau pernyataan x[P(x)].Salah satu cara membuktikan adalah dengan mengasumsikan terdapat sebuah elemen c sedemikian sehingga P(c) bernilai benar.

Soal.Buktikan tidak terdapat bilangan bulat k sedemikian sehingga 4k + 3 adalah bilangan kuadrat sempurna.

16

BIKONDISIONALUntuk membuktikan kebenaran pernyataan berbentuk p q, digunakan ekivalensi (p q) (q p). Kemudian digunakan metode – metode pembuktian yang telah dipelajari sebelumnya.

Soal.Buktikan:Untuk setiap bilangan bulat n berlaku n ganjil jika dan hanya jika n2 ganjil.

17