1728 bilqis if pertemuan 3 mat disk 2010
TRANSCRIPT
![Page 1: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/1.jpg)
bilqis 1
Pertemuan
3
2010
![Page 2: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/2.jpg)
bilqis 2
Cara membuktikan
Sub-bab 1.5
![Page 3: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/3.jpg)
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
![Page 4: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/4.jpg)
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
![Page 5: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/5.jpg)
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)
![Page 6: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/6.jpg)
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
![Page 7: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/7.jpg)
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
![Page 8: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/8.jpg)
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
![Page 9: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/9.jpg)
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
![Page 10: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/10.jpg)
bilqis 10
Dari Bab 1 ekivalen
• Kontrapositif – P q ekivalen dengan ~ q ~ p
• P q ekivalen dengan ~ p v q
![Page 11: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/11.jpg)
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
![Page 12: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/12.jpg)
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
![Page 13: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/13.jpg)
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
![Page 14: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/14.jpg)
bilqis 14
![Page 15: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/15.jpg)
bilqis 15
![Page 16: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/16.jpg)
bilqis 16
![Page 17: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/17.jpg)
bilqis 17
Aturan penentuan kesimpulan untuk quantified statements
1. Universal instantiation
2. Universal generalization
3. Existential instantiation
4. Existential generalization
![Page 18: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/18.jpg)
bilqis 18
![Page 19: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/19.jpg)
bilqis 19
Contoh
![Page 20: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/20.jpg)
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
![Page 21: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/21.jpg)
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
∈∴∀
)(
)(
![Page 22: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/22.jpg)
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
![Page 23: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/23.jpg)
bilqis 23
• 2. Universal generalization
• Misal :– P(lisa) lisa adalah wise– P(ili) ili adalah wise
)(
)(
xPx
DcsembaranguntukcP
∀∈
)(xxP∀
![Page 24: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/24.jpg)
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
![Page 25: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/25.jpg)
bilqis 25
• 3. Existential Instantiation
min ada 1 wanita yang wise
lisa adalah wanita yang wise
DcelemensatuimaluntukcP
xxP
∈∃
min)(
)(
DcelemensatuimaluntukcP
xxP
∈∃
min)(
)(
![Page 26: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/26.jpg)
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
![Page 27: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/27.jpg)
bilqis 27
• 4. Existential Generalization
)(
min)(
xPx
DcelemensatuimaluntukcP
∃∈
![Page 28: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/28.jpg)
bilqis 28
Membuktikan teorema berbentuk p → q
Bukti langsung (direct proof)
Bukti tidak langsung (indirect proof)
Bukti hampa (vacuous proof)
Bukti mudah (trivial proof)
![Page 29: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/29.jpg)
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 :
![Page 30: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/30.jpg)
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)
![Page 31: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/31.jpg)
bilqis 31
• 2. Indirect Proof– P q equivalen dengan contrapositif ~q
~p• Asumsikan ~q adalah benar
• Maka buktikan ~p juga benar
– Ex :
![Page 32: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/32.jpg)
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)
![Page 33: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/33.jpg)
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
![Page 34: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/34.jpg)
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
![Page 35: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/35.jpg)
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
![Page 36: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/36.jpg)
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
≥≥
≥
≥
![Page 37: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/37.jpg)
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
![Page 38: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/38.jpg)
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
↔
![Page 39: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/39.jpg)
bilqis 39
Cara-cara pembuktian lain:
1.Existence Proof
a) Constructive
b) Non Constructive
2. Proof by Counter Examples
![Page 40: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/40.jpg)
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
![Page 41: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/41.jpg)
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
![Page 42: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/42.jpg)
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)
![Page 43: 1728 Bilqis If Pertemuan 3 Mat Disk 2010](https://reader033.vdokumen.com/reader033/viewer/2022042522/5597a00c1a28ab9c098b4575/html5/thumbnails/43.jpg)
bilqis 43
PR (kerjakan 5 saja)
• Bilqis :
• 1.5 1, 5, 7, 9, 13, 23