logik
-
Upload
tun-harmadi -
Category
Documents
-
view
180 -
download
10
description
Transcript of logik
1.Asas Logik dan Pembuktian
ASAS LOGIK
• Logik merupakan dasar dari semua penaakulan (reasoning).
• Penaakulan didasarkan pada hubungan antara pernyataan-
pernyataan (statements).
Pernyataan
• Ayat deklaratif yang sama ada benar (true) atau palsu (false),
tetapi tidak kedua-duanya.
• Nama lain pernyataan: proposisi.
Contoh 1. Semua pernyataan di bawah ini adalah proposisi:
(a) 11 adalah nombor ganjil.
(b) SMU 3083 adalah kursus major matematik PPG.
(c) 1 + 1 = 2
(d) 8 ≥ punca bagi persamaan kuadratik 0642 ≤−x .
(e) Hari ini adalah hari Sabtu.
(f) Untuk semua integer n ≥ 0, maka 2n adalah nombor genap.
(g) x + y = y + x untuk nombor-nombor nyata x dan juga y.
Contoh 2. Semua pernyataan di bawah ini bukan proposisi.
(a) Pukul berapa pesawat ASA123 tiba di LTA Pulau Pinang?
(b) Tolong isilah gelas ini dengan air!
(c) x + 3 = 8
(d) x > 3
• Proposisi dilambangkan dengan huruf kecil p, q, r, ….
p : 13 adalah nombor ganjil.
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
2
q : Matematik Diskrit adalah kursus major PPG.
r : 2 + 2 = 4
Pengait Proposisi dan Simbol
• Contohnya p dan q adalah proposisi.
1. Konjungsi (conjunction): p dan q
Simbol: p ∧ q,
2. Disjungsi (disjunction): p atau q
Simbol: p ∨ q
3. Negasi/Penafian (negation) dari p: bukan p /tidak p
Simbol: ∼p atau p¬
• p dan q disebut proposisi atomik
• Kombinasi p dengan q menghasilkan proposisi majmuk
(compound proposition)
Contoh 3. Diketahui proposisi-proposisi berikut:
p : Hari ini hujan
q : Murid-murid membawa payung ke sekolah
p ∧ q : Hari ini hujan dan murid-murid membawa payung ke
sekolah
p ∨ q : Hari ini hujan atau murid-murid membawa payung ke
sekolah
∼p : Tidak benar hari ini hujan
(atau: Hari ini tidak hujan) �
Contoh 4. Diketahui proposisi-proposisi berikut:
p : Pemuda itu tinggi
q : Pemuda itu tampan
Nyatakan dalam bentuk simbolik:
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
3
(a) Pemuda itu tinggi dan tampan
(b) Pemuda itu tinggi tapi tidak tampan
(c) Pemuda itu tidak tinggi maupun tampan
(d) Tidak benar bahawa pemuda itu pendek atau tidak tampan
(e) Pemuda itu tinggi, atau pendek dan tampan
(f) Tidak benar bahawa pemuda itu pendek maupun tampan
Penyelesaian:
(a) p ∧ q
(b) p ∧ ∼q
(c) ∼p ∧ ∼q
(d) ∼(∼p ∨ ∼q)
(e) p ∨ (∼p ∧ q)
(f) ∼(∼p ∧ ∼q)
Jadual Kebenaran
Simbol nilai kebenaran (truth value):
Benar: T atau 1
Palsu: F atau 0
p q p ∧ q p q p ∨ q p ∼q
T T T T T T T F
T F F T F T F T
F T F F T T
F F F F F F
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
4
Contoh 5. Contohnya
p : 17 adalah nombor perdana (benar)
q : Nombor perdana selalu ganjil (palsu)
p ∧ q : 17 adalah nombor perdana dan nombor perdana selalu
ganjil (palsu)
Contoh 6. Bina jadual kebenaran dari proposisi majmuk (p ∧ q) ∨
(~q ∧ r).
p q r p ∧ q ~q ~q ∧ r (p ∧ q) ∨ (~q ∧ r)
T T T T F F T
T T F T F F T
T F T F T T T
T F F F T F F
F T T F F F F
F T F F F F F
F F T F T T T
F F F F T F F
• Proposisi majmuk disebut tautologi jika ia benar untuk semua
kes.
• Proposisi majmuk disebut kontradiksi jika ia palsu untuk semua
kes.
• Proposisi majmuk disebut kontingensi jika ia adalah benar dan
juga palsu untuk semua kes.
Contoh 7. p ∨ ~(p ∧ q) adalah sebuah tautologi
p q p ∧ q ~(p ∧ q) p ∨ ~(p ∧ q)
T T T F T
T F F T T
F T F T T
F F F T T
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
5
Contoh 8. (p ∧ q) ∧ ~(p ∨ q) adalah sebuah kontradiksi
p q p ∧ q p ∨ q ~(p ∨ q) (p ∧ q) ∧ ~(p ∨ q)
T T T F F F
T F F T F F
F T F T F F
F F F F T F
Pernyataan Kesamaan
• Dua buah proposisi majmuk, P(p, q, ..) dan Q(p, q, ..) disebut
ekivalen secara logik jika keduanya mempunyai jadual
kebenaran yang sama nilai kebenaran (truth value).
Simbol:
P(p, q, …) ⇔⇔⇔⇔ Q(p, q, …) atau P(p, q, …) ≡ Q(p, q, …)
Contoh 9. Hukum De Morgan: ~ (p ∧ q) ⇔ ~p ∨ ~q.
p q p ∧ q ~ (p ∧ q) ~ p ~q ~ p ∨ ~ q
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
6
Hukum-hukum Logik
• Disebut juga hukum-hukum aljabar proposisi.
1. Hukum identiti:
p ∨ F ⇔ p
p ∧ T ⇔ p
2. Hukum dominasi:
p ∧ F ⇔ F
p ∨ T ⇔ T
3. Hukum negasi:
p ∨ ~p ⇔ T
p ∧ ~p ⇔ F
4. Hukum idempotent:
p ∨ p ⇔ p
p ∧ p ⇔ p
5. Hukum involusi (double
negation):
~(~p) ⇔ p
6. Hukum penyerapan
(absorption):
p ∨ (p ∧ q) ⇔ p
p ∧ (p ∨ q) ⇔ p
7. Hukum kalis tukar tertib:
p ∨ q ⇔ q ∨ p
p ∧ q ⇔ q ∧ p
8. Hukum kalis sekutuan:
p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r
p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r
9. Hukum kalis agihan:
p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p
∨ r)
p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p
∧ r)
10. Hukum De Morgan:
~(p ∧ q) ⇔ ~p ∨ ~q
~(p ∨ q) ⇔ ~p ∧ ~q
Contoh 10. Tunjukkan bahawa p ∨ ~ (p ∨ q) dan p ∨ ~q keduanya
ekivalen secara logik.
Penyelesaian:
p ∨ ~(p ∨ q ) ⇔ p ∨ (~p ∧ ~q) (Hukum De Morgan)
⇔ (p ∨ ~p) ∧ (p ∨ ~q) (Hukum kalis agihan)
⇔ T ∧ (p ∨ ~q) (Hukum negasi)
⇔ p ∨ ~q (Hukum identiti)
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
7
Contoh 11. Buktikan hukum penyerapan: p ∧ (p ∨ q) ⇔ p
Penyelesaian:
p ∧ (p ∨ q) ⇔ (p ∨ F) ∧ (p ∨ q) (Hukum Identiti)
⇔ p ∨ (F ∧ q) (Hukum kalis agihan)
⇔ p ∨ F (Hukum dominasi)
⇔ p (Hukum identiti)
IMPLIKASI
• Bentuk proposisi: “jika p, maka q”
• Simbol: p → q
• Proposisi p disebut hipotesis, antesenden, premis, atau syarat
• Proposisi q disebut kesimpulan (atau akibat).
Contoh 12.
a. Jika saya lulus ujian, maka saya mendapat hadiah dari
ayah
b. Jika suhu mencapai 80°C, maka alarm akan berbunyi
c. Jika anda tidak mendaftar diri, maka anda dianggap
mengundurkan kursus
• Cara-cara mengekspresikan implikasi p → q:
(a) Jika p, maka q
(b) Jika p, q
(c) p mengakibatkan q (p implies q)
(d) q jika p
(e) p hanya jika q
(f) p syarat cukup untuk q (hipotesis menyatakan syarat
cukup (sufficient condition) )
(g) q syarat perlu untuk p (akibat menyatakan syarat
perlu (necessary condition) )
(h) q bilamana p (q whenever p)
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
8
Contoh 13. Proposisi-proposisi berikut adalah implikasi dalam
berbagai bentuk:
(a) Jika hari hujan, maka tanaman akan tumbuh subur.
(b) Jika tekanan minyak dikuatkan, kereta akan memecut.
(c) Orang itu mahu bertolak bersama jika dia diberi tuntutan
perjalanan.
(d) Ahmad boleh daftar kursus Teori Bahasa Formal hanya
jika dia sudah lulus kursus Matematik Diskrit.
(e) Syarat perlu untuk Universiti ABC mencapai taraf dunia
adalah dengan mengontrak pensyarah asing kenamaan.
(f) Banjir terjadi bilamana hujan lebat tidak berhenti-henti
sepanjang hari.
Contoh 14. Tuliskan proposisi (c) – (f) pada Contoh 13 di atas ke
dalam bentuk proposisi “jika p maka q”
Penyelesaian:
(c) Jika orang itu diberi tuntutan perjalanan, maka dia mahu
bertolak bersama.
(d) Jika Ahmad mengambil kursus Teori Bahasa Formal,
maka dia sudah lulus kursus Matematik Diskrit.
(e) Jika Universiti ABC mengontrak pensyarah asing
kenamaan, maka ia akan mencapai taraf dunia.
(f) Jika hujan lebat tidak berhenti-henti sepanjang hari,
maka banjir akan terjadi.
• Jadual kebenaran implikasi
p q p → q
T T T
T F F
F T T
F F T
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
9
Contoh 15.
Pensyarah: “Jika markah akhir ujian anda adalah 80 atau lebih,
maka anda akan mendapat gred A untuk kursus ini”.
Adakah pensyarah anda bercakap benar atau dia berbohong? Tinjau
empat kes berikut ini:
Kes 1: Markah ujian akhir anda di atas 80 (hipotesis benar) dan
anda mendapat gred A untuk kursus tersebut (kesimpulan
benar).
∴ Pernyataan pensyarah benar.
Kes 2: Markah ujian akhir anda di atas 80 (hipotesis benar) tetapi
anda tidak mendapat gred A (kesimpulan palsu).
∴ Pensyarah berbohong (pernyataannya palsu).
Kes 3: Markah ujian akhir anda di bawah 80 (hipotesis palsu) dan
anda mendapat gred A (kesimpulan benar).
∴ Pensyarah anda tidak dapat dikatakan palsu (mungkin
dia melihat kemampuan anda secara rata-rata bagus
sehingga ia tidak ragu memberi gred A).
Kes 4: Markah ujian akhir anda di bawah 80 (hipotesis palsu) dan
anda tidak mendapat gred A (kesimpulan palsu).
∴ Pensyarah anda benar.
Contoh 16. Tunjukkan bahawa p → q ekivalen secara logik dengan
~ p ∨ q.
Penyelesaian:
p q ~ p p → q ~ p ∨ q
T T F T T
T F F F F
F T T T T
F F T T T
∴ “Jika p, maka q” ⇔ “Tidak p atau q”.
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
10
Contoh 17. Tentukan negasi dari p → q.
Penyelesaian:
~(p → q) ⇔ ~(~p ∨ q) ⇔ ~(~p) ∧ ~q ⇔ p ∧ ~q
Proposisi Bersyarat
Konvers/akas (converse) : q → p
Invers/songsangan (inverse) : ~ p → ~ q
Kontrapositif (contrapositive) : ~ q → ~ p
Implikasi Konvers Invers Kontrapositif
p q ~ p ~ q p → q q → p ~ p → ~ q ~ q → ~ p
T T F F T T T T
T F F T F T T F
F T T F T F F T
F F T T T T T T
Contoh 18. Tentukan konvers, invers, dan kontrapositif dari:
“Jika Amir mempunyai kereta mewah, maka dia orang kaya”
Penyelesaian:
Konvers : Jika Amir orang kaya, maka dia mempunyai
kereta mewah
Invers : Jika Amir tidak mempunyai kereta mewah, maka
dia bukan orang kaya
Kontrapositif : Jika Amir bukan orang kaya, maka dia tidak
mempunyai kereta mewah
Contoh 19. Tentukan kontrapositif dari pernyataan:
(a) Jika dia bersalah maka dia dimasukkan ke dalam penjara.
(b) Jika 6 lebih besar dari 0 maka 6 bukan nombor negatif.
(c) Ivan lulus ujian hanya jika dia belajar.
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
11
(d) Hanya jika dia tidak terlewat maka dia akan mendapat
pekerjaan.
(e) Perlu ada angin agar layang-layang boleh terbang.
Penyelesaian:
(a) Jika dia tidak dimasukkan ke dalam penjara, maka ia tidak
bersalah.
(b) Jika 6 nombor negatif, maka 6 tidak lebih besar dari 0.
(c) “Jika Ivan lulus ujian maka ia sudah belajar”.
Kontrapositif: “Jika Ivan tidak belajar maka ia tidak lulus ujian”
(d) “Jika ia mendapat pekerjaan maka ia tidak terlewat”
Kontrapositif: “Jika ia terlewat maka ia tidak akan mendapat
pekerjaan itu”
(e) “Ada angin adalah syarat perlu agar layang-layang boleh
terbang” ekivalen dengan “Jika layang-layang boleh terbang
maka ada angin”.
Kontrapositif: “Jika tidak ada angin, maka layang-layang tidak
boleh terbang”.
Bikondisional (Bi-implikasi)
• Bentuk proposisi: “p jika dan hanya jika q”
• Simbol: p ↔ q
p q p ↔ q
T T T
T F F
F T F
F F T
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
12
• p ↔ q ⇔ (p → q) ∧ (q → p).
p q p ↔ q p → q q → p (p → q) ∧ (q → p)
T T T T T T
T F F F T F
F T F T F F
F F T T T T
• Dengan kata lain, pernyataan “p jika dan hanya jika q” dapat
dibaca “Jika p maka q dan jika q maka p”.
• Cara-cara menyatakan bikondisional p ↔ q:
(a) p jika dan hanya jika q.
(b) p adalah syarat perlu dan cukup untuk q.
(c) Jika p maka q, dan sebaliknya.
(d) p iff q
Contoh 20. Proposisi majmuk berikut adalah bi-implikasi:
(a) 1 + 1 = 2 jika dan hanya jika 2 + 2 = 4.
(b) Syarat cukup dan syarat perlu agar hari hujan adalah
kelembapan udara tinggi.
(c) Jika anda orang kaya maka anda mempunyai banyak
wang, dan sebaliknya.
(d) 0322
≤−− xx iff 31 ≤≤− x .
Contoh 21. Tuliskan setiap proposisi berikut ke dalam bentuk “p
jika dan hanya jika q”:
(a) Jika cuaca di luar panas maka anda membeli ais krim,
dan jika anda membeli ais krim maka cuaca di luar
panas.
(b) Syarat cukup dan perlu agar anda memenangi
pertandingan adalah anda menjalankan banyak latihan.
(c) Jika anda memandang skrin komputer berterusan tanpa
rehat maka mata anda lelah, begitu sebaliknya.
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
13
Penyelesaian:
(a) Anda membeli ais krim jika dan hanya jika cuaca di luar
panas.
(b) Anda menjalankan banyak latihan adalah syarat perlu
dan cukup untuk anda memenangi pertandingan.
(c) Mata anda lelah jika dan hanya jika anda memandang
skrin komputer berterusan tanpa rehat.
• Bila dua proposisi majmuk yang ekivalen di-biimplikasikan,
maka hasilnya adalah tautologi.
Teorem:
Dua buah proposisi majmuk, P(p, q, ..) dan Q(p, q, ..) disebut
ekivalen secara logik, dilambangkan dengan P(p, q, …) ⇔ Q(p, q,
…), jika P ↔ Q adalah tautologi.
HUJAH
• Hujah mengandungi suatu urutan pernyataan yang dikenali
sebagai premis dan satu pernyataan yang dipanggil
kesimpulan.
• Sesuatu hujah adalah sah jika kesimpulan adalah benar
bilamana (whenever) kesemua premisnya adalah benar.
• Premis adalah suatu andaian yang dianggapkan benar.
Jika implikasi p → q adalah satu tautologi, di mana p dan q adalah
pernyataan majmuk, maka q adalah logik mengikut p.
Misalnya bagi suatu implikasi dalam bentuk p1, p2, p3, p4, p5 → q
adalah satu tautology.Ini bermakna jika p1 ∧ p2 ∧ p3 ∧ p4 ∧ p5 adalah benar, maka q adalah benar.
p1, p2, p3, p4, p5 dikenali sebagai hipotesis atau premis manakala q
adalah kesimpulan.
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
14
Pembuktian
Bagi membuktikan sesuatu hujah adalah sah atau kesimpulan adalah
logik berdasarkan hipotesis, dua syarat yang berikut
dipertimbangkan:
• Andaikan kesemua hipotesis adalah benar
• Gunakan hukum-hukum inferens dan ekuivalens logik untuk
menentukan kesimpulannya adalah benar.
Contoh 22.
Guna jadual kebenaran, buktikan kesahan bagi hujah-hujah yang
berikut:
a) p q
p
∧
∴
Penyelesaian:
Dalam bentuk implikasi: (p∧ q) → p
p q p∧ q (p ∧ q) → p
1 1 1 1
1 0 0 1
0 1 0 1
0 0 0 1
Nota: 1= benar; 0 = palsu.
Oleh sebab implikasi di atas adalah satu tautologi, maka hujah
adalah sah.
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
15
b)
¬
→
∴¬
q
p q
p
Dalam bentuk implikasi: q ∧ (p →q) → p
p q p q p →
q
q ∧ (p→ q) q ∧ (p →q) →
p
1 1 0 0 1 0 1
1 0 0 1 0 0 1
0 1 1 0 1 0 1
0 0 1 1 1 1 1
Oleh sebab implikasi di atas adalah satu tautologi, maka hujah
adalah sah.
Peraturan Inferens
qp
q
p
∧∴
Konjungsi
p
p q∴ ∨ Penambahan
p q
p
∧
∴ Simplifikasi
q
qp
p
∴
→ Modus ponens
¬
→
∴¬
q
p q
p
Modus tollens
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
16
p q
q r
p r
→
→
∴ →
Sigolisma
hipotesisan
p q
p
q
∨
¬
∴
Sigolisma disjungsi
p
Cp
∴
→~ Kontradiksi
pqqp ~~ →⇔→
Kontrapositif
qpqp ∨⇔→ ~
Identiti bersyarat
Contoh 23.
Diberi:
Cuaca hari ini tidak selesa dan lebih panas daripada
semalam. Kita akan pergi berenang jika cuaca lebih
panas daripada semalam. Jika kita tidak pergi
berenang, maka kita akan naik perahu. Jika kita naik
perahu, maka kita akan balik pada waktu senja.
Tukarkan ayat (premis) ke dalam bentuk simbol:
p = cuaca hari ini selesa
q = cuaca lebih panas daripada semalam
r = kita akan pergi berenang
s = kita akan naik perahu
t = kita akan balik pada waktu senja
Mula dengan premis yang positif.
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
17
Premis : ~ p ∧ q,
r → p,
~ r → s,
s→ t
Kesimpulan : t
Biasanya kesimpulan ada pada premis terakhir yang mula
dengan “maka”.
Bukti:
1. ~ p ∧ q Premis 1
2. r → p Premis 2
3. ~ r → s Premis 3
4 s→ t Premis 4
5 ~ p 1, Simplifikasi
6 ~ r 2, 5 Modus tollens
7. ~ r → t 3, 4 Sigolisma hipotesisan
8. t 6, 7 Modus ponens
Kesimpulannya kita akan balik pada waktu senja.
Contoh 24.
Buktikan kesahan hujah yang berikut:
Jika saya belajar bersungguh-sungguh atau menjawab
semua soalan dalam buku teks, maka saya akan lulus
ujian tersebut. Jika saya lulus ujian tersebut, maka ayah
saya senang hati. Akan tetapi ayah saya tidak senang
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
18
hati. Maka, saya tidak menjawab semua soalan dalam
buku teks.
Penyelesaian:
Proposisi asas (primary propositions) dalam hujah:
p : Saya belajar bersungguh-sungguh
q : Saya menjawab semua soalan dalam buku teks
r : Saya akan lulus ujian tersebut
s : Ayah saya senang hati
Wakilkan setiap premis dalam bentuk simbol:
1. (p ∨ q) → r (premis 1)
2 r → s (premis 2)
3. ~s (premis 3)
∴~q (kesimpulan)
Hujah dan alasan:
1. (p∨ q) → r premis 1
2. r→ s premis 2
3. ~s premis 3
4. (p ∨ q) → s 1, 2 Sigolisma hipotesisan
5. ~ (p ∨ q) 3, 4 Modus tollens
6. ~p ∧ ~q 5 Hukum De Morgan
7. ~q ∧ ~p 6 Hukum kalis tukar tertib
8. ~q 7 Simplifikasi
Q. E. D.
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
19
LATIHAN LANJUTAN
1. Tentukan sama ada pernyataan yang berikut adalah tautologi,
kontradisi atau kontingensi menggunakan Jadual Kebenaran.
a) p v (p→ q) → ~q
b) (p∧q) ↔~p
c) p ∧ (p→ ~q) ∨ ~r
2. Tunjukkan pernyataan-pernyataan yang berikut adalah
ekuivalens secara logik dengan menggunakan Jadual
Kebenaran:
a) ~ (p→ q) ⇔ p ∧ ~ q
b) [p→ (q ∨ r)] ⇔ [~r → (p→ q)]
3. Tentukan kesahan hujah-hujah yang berikut dengan
menggunakan Jadual Kebenaran:
a) p↔q
q v r
~ r
∴ ~ p
b) ~p ↔ q
q→ r
~r
-------------
∴ p
Seminar 1:Asas Logik dan Pembuktian KORLK Sep2013
20
4. Buktikan kesahan hujah-hujah yang berikut dengan
menggunakan peraturan inferens:
a) Mata saya tidak merah. Jika badan saya letih, maka mata saya
akan jadi merah. Oleh itu, badan saya tidak letih.
b) w adalah nombor genap. Jika w adalah nombor genap, maka
w2 adalah nombor genap. Oleh itu, w
2 adalah nombor genap.
c) Jika semua komputer diserang virus, maka banyak urusan
perbankan akan gagal. Jika banyak urusan perbankan gagal,
maka bilangan pelaburan akan berkurangan. Semua komputer
diserang virus dan banyak urusan perbankan gagal. Maka,
bilangan pelaburan berkurangan.
5. Permudahkan pernyataan yang berikut dengan menggunakan
hukum-hukum logik:
( ) ( )baba ∨∧→ ~~
Selamat mencuba!