1728 bilqis if pertemuan 3 mat disk 2010
Post on 04-Jul-2015
713 Views
Preview:
TRANSCRIPT
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
top related