bilqis 1

Pertemuan

3

2010

bilqis 2

Cara membuktikan

Sub-bab 1.5

bilqis 3

Terminologi:

• Teorema: pernyataan yang dapat dibuktikan kebenarannya

Ex : Bumi adalah bulat

• Argumen: rangkaian pernyataan yang membentuk bukti

• Aksioma: pernyataan yang digunakan dalam suatu bukti, yang kebenarannya bisa diasumsikan, diketahui, atau telah dibuktikan sebelumnya

• Aturan penentuan kesimpulan (rule of inference): cara menarik kesimpulan dari pernyataan-pernyataan sebelumnya

• Lemma: teorema sederhana yang digunakan dalam membuktikan teorema lain

bilqis 4

Terminologi:

• Corollary: proposisi yang merupakan akibat langsung dari teorema yang dibuktikan

Ex : jika 3 sisi pada segitiga mempunyai panjang yang sama, maka segitiga itu juga mempunyai sudur yang sama

• Conjecture: pernyataan yang nilai kebenarannya belum diketahui

bilqis 5

Aturan penentuan kesimpulan:

Addition : (p) → (p v q)

Simplification : (p ∧ q) → (p)

Conjunction : ((p) ∧ (q)) → (p ∧ q)

Modus ponens : (p ∧ (p → q)) → (q)

Modus tollens : (¬q ∧ (p → q )) → (¬p)

Hypothetical syllogism : ((p → q) ∧ (q → r )) → (p → r)

Disjunctive syllogism : ((p v q) ∧ (¬p)) → (q)

Resolution : ((p v q) ∧ (¬p v r)) → (q v r)

bilqis 6

Contoh:

Addition : (p) → (p v q)Hari ini Jumat

Hari ini Jumat atau kita sedang belajar

Simplification : (p ∧ q) → (p)Hari ini Jumat dan tadi pagi Ayah menelepon

Hari ini Jumat

Conjunction : ((p) ∧ (q)) → (p ∧ q)Hari ini Jumat

Tadi pagi Ayah menelepon

Hari ini Jumat dan tadi pagi Ayah menelepon

P--------P v q

P ^ q--------P

Pq--------P ^ q

bilqis 7

Modus ponens: (p ∧ (p → q)) → (q)

Saya haus

Jika saya haus, maka saya minum air

Saya minum air

Modus tollens: (¬q ∧ (p → q )) → (¬p)

Jika saya haus, maka saya minum air

Saya tidak minum air

Saya tidak haus

PP q--------q

P q~ q--------~ P

bilqis 8

Hypothetical syllogism: ((p → q) ∧ (q → r )) → (p → r)

Jika hari ini cerah, maka saya akan pergi

Jika saya akan pergi, maka saya harus mengambil uang

Jika hari ini cerah, maka saya harus mengambil uang

Disjunctive syllogism: ((p v q) ∧ (¬p)) → (q)

Kemarin hari Selasa atau besok hari Senin

Kemarin hari Kamis

Besok hari Senin

P qQ r--------P r

P v q~ p--------q

bilqis 9

Resolution / Resolusi : ((p v q) ∧ (¬p v r)) → (q v r)

q v r disebut resolvent

P v q~ p v r--------Q v r

bilqis 10

Dari Bab 1 ekivalen

• Kontrapositif – P q ekivalen dengan ~ q ~ p

• P q ekivalen dengan ~ p v q

bilqis 11

Kesalahan menentukan kesimpulan (fallacies)

Fallacy of confirming the conclusion:

Jika hari ini cerah, maka saya akan pergi

Saya akan pergi

Hari ini cerah

Fallacy of denying the hypothesis:

Jika besok hari Sabtu, maka saya akan pulang

Besok hari Kamis

Saya tidak jadi pulang

P qq--------P

P q~ p--------~ q

Kesimpulan salah, karena tidak ada dalam aturan yang 8

bilqis 12

Contoh: soal Rossen halaman 73 no. 3

Construct an argument using rules of inference to show that the hypothesis

Randy works hard

If Randy works hard, then he is a dull boy

If Randy is a dull boy, then he will not get the job

imply the conclusion

Randy will not get the job

bilqis 13

Contoh: soal Rossen halaman 73 no. 3

r: Randy works hardd: Randy is a dull boyj: Randy will not get the job

Randy works hard r (1) If Randy works hard, then he is a dull boy r → d (1) If Randy is a dull boy, then he will not get the job d → j (1)

Conclusion: Randy will not get the job

Argumen: r (1) r → d (1) maka d harus (1)

d → j (1) d (1) maka j harus (1)

pengambilan kesimpulan (konklusi) benar

bilqis 14

bilqis 15

bilqis 16

bilqis 17

Aturan penentuan kesimpulan untuk quantified statements

1. Universal instantiation

2. Universal generalization

3. Existential instantiation

4. Existential generalization

bilqis 18

bilqis 19

Contoh

bilqis 20

1.Universal instantiation

diketahui : ∀x P(x) untuk domain D

buktikan : P(c) di mana c ∈ D

contoh : ∀x P(x) ; D = { mahasiswa di kelas ini }

semua mahasiswa di kelas ini belajar MD

c = Bayu ∈ D

P(c) : Bayu belajar MD

bilqis 21

(ROI) for Quantifier

• 1. Universal instantion– Domain

• Misal :– X = wanita sebagai domain– P(x) = x is wise– C salah satu wanita

– Semua wanita adalah wise– C adalah wise dengan syarat c E

D

– P(lisa) lisa adalah wise dengan syarat lisa E D

DcifcP

xPx

∈∴∀

)(

)(

c

DcifcP

xPx

∈∴∀

)(

)(

bilqis 22

1.Universal generalization

diketahui : P(c)

di mana c ∈ D = Domain = { …., –5, –3, –1 }

buktikan : ∀x P(x)

contoh:

P(c) = c integer negatif → c3 integer negatif

D = Domain = { …., –3, –2, –1 }

c = –n di mana n = 1, 2, 3, ….

c3 = (–n )*(–n )*(–n ) = –n3

∀x P(x) : jika x integer negatif, maka x3 integer negatif

terbukti

bilqis 23

• 2. Universal generalization

• Misal :– P(lisa) lisa adalah wise– P(ili) ili adalah wise

)(

)(

xPx

DcsembaranguntukcP

∀∈

)(xxP∀

bilqis 24

1.Existential instantiation

diketahui : ∃x P(x)

buktikan : P(c)

contoh : ∃x P(x) = ada bilangan prima gasal

P(c) = 5 bilangan prima gasal

bilqis 25

• 3. Existential Instantiation

min ada 1 wanita yang wise

lisa adalah wanita yang wise

DcelemensatuimaluntukcP

xxP

∈∃

min)(

)(

DcelemensatuimaluntukcP

xxP

∈∃

min)(

)(

bilqis 26

1.Existential generalization

diketahui : P(c)

buktikan : ∃x P(x)

contoh : P(c) = 5 bilangan prima gasal

∃x P(x) = ada bilangan prima gasal

bilqis 27

• 4. Existential Generalization

)(

min)(

xPx

DcelemensatuimaluntukcP

∃∈

bilqis 28

Membuktikan teorema berbentuk p → q

Bukti langsung (direct proof)

Bukti tidak langsung (indirect proof)

Bukti hampa (vacuous proof)

Bukti mudah (trivial proof)

bilqis 29

Method of Profing Theorem

• 1. Direct Proof– Untuk p q :

• Asumsi P adalah benar

• Buktikan bahwa q juga benar, misal dengan ROI

– Ex :

bilqis 30

Bukti langsung (direct proof)

Teorema: “Jika n integer gasal, maka n2 integer gasal”

Bukti: n = 2k + 1 integer gasal; k sembarang integer

n2 = (2k + 1)2

= 4k2 + 4k + 1

= 2 (2k2 + 2k) + 1 (n2 integer gasal)

n integer gasal → n2 integer gasal (terbukti)

bilqis 31

• 2. Indirect Proof– P q equivalen dengan contrapositif ~q

~p• Asumsikan ~q adalah benar

• Maka buktikan ~p juga benar

– Ex :

bilqis 32

Bukti tidak langsung (indirect proof)

Teorema: “jika 3n + 2 gasal, maka n gasal”

Ekivalen dengan “jika n genap, maka 3n + 2 genap”

Bukti: n = 2k; k sembarang integer

3n + 2 = 3(2k) + 2

= 6k + 2

= 2 (3k) + 2

= 2 (3k +1)

jika n genap, maka 3n + 2 genap

jika 3n + 2 gasal, maka n gasal (terbukti)

bilqis 33

• Voucous Proof :– Jika nilai var diket– Jika kita bisa membuktikan bahwa P salah,

krn

– Jika P salah maka tidak peduli Q benar atau salah, proposisi pasti benar

bilqis 34

Bukti hampa (vacuous proof):

Implikasi p → q mempunyai nilai kebenaran TRUE apabila p bernilai FALSE

Contoh: “jika n > 1 maka n2 > n, untuk n = 0”

p : 0 > 1 (FALSE)

q : 02 > 0 (FALSE)

p → q TRUE

maka “teorema” terbukti

bilqis 35

• 4. Trivial Proof– Jika nilai var diket– Jika kita bisa membuktikan bahwa q benar,

krn

– Jika q benar, maka tidak peduli apakah P benar atau salah, proposisi pasti benar

bilqis 36

Bukti mudah (trivial proof)

Implikasi p → q mempunyai nilai kebenaran TRUE apabila q bernilai TRUE

Contoh: “jika a b maka an bn, untuk n = 0”

p : a b

q : a0 b0 (TRUE)

maka “teorema” terbukti

≥≥

≥

≥

bilqis 37

Bukti per kasus (proof by cases)

Teorema: |xy| = |x| |y| untuk semua bilangan nyata

Bukti:

(-x)(-y)xy < 0< 04

(-x)y-(xy) >= 0< 03

x(-y)-(xy)< 0>= 02

xyxy>= 0>= 01

|x| |y||xy|yx

bilqis 38

Bukti teorema berbentuk ekivalensi “p q”

• Buktikan p → q

• Buktikan q → p

Bukti teorema berbentuk “p, q, r, s ekivalen”

• Buktikan p → q

• Buktikan q → r

• Buktikan r → s

• Buktikan s → p

↔

bilqis 39

Cara-cara pembuktian lain:

1.Existence Proof

a) Constructive

b) Non Constructive

2. Proof by Counter Examples

bilqis 40

Constructive Proof

Teorema:

“ada sebuah integer yang dapat dinyatakan sebagai jumlah dari pangkat-tiga dua integer positif, dalam dua cara berbeda”

Bukti: dengan trial-and error didapatkan 1729 = 103 + 93

dan 1729 = 123 + 13

bilqis 41

Non Constructive ProofTeorema:

“Ada dua bilangan irasional x dan y yang menghasilkan xy rasional”

Bukti: ( x = 2 dan y = 2 ) maka 2 = 2 rasional

sehingga teorema terbukti

2 22

bilqis 42

Proof by Counter ExamplesTeorema:

“tiap integer positif merupakan jumlah dari kuadrat tiga integer” adalah pernyataan yang salah

Bukti: usahakan menemukan satu contoh yang meng-counter

pernyataan di atas

02 = 0 12 = 1 22 = 4 32 = 9

0 = 02 + 02 + 02 3 = 12 + 12 + 12 6 = 22 + 12 + 12

1 = 12 + 02 + 02 4 = 22 + 02 + 02 7 = ?

2 = 12 + 12 + 02 5 = 22 + 12 + 02

7 tidak dapat dibentuk dari jumlah kuadrat tiga integer

( 7 disebut counter example )

terbukti pernyataan di atas salah (false)

bilqis 43

PR (kerjakan 5 saja)

• Bilqis :

• 1.5 1, 5, 7, 9, 13, 23