logika lanjutan
DESCRIPTION
lanjutan materi kuliah logika (logic) untuk digunakan di st3telkom.ac.idTRANSCRIPT
LOGIKA
Tenia wahyuningrum
Bahan kuliah matematika diskrit
http://st3telkom.ac.id
Bagian II
Bikondisional (Bi-implikasi)2
B entuk proposisi: “p jika dan hanya jika q”
N otasi: p q
p q p q
T T T
T F F
F T F
F F T
p q (p q) (q p).
3
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
D engan kata lain, pernyataan “p jika dan hanya jika q”
dapat dibaca “Jika p m aka q dan jika q m aka p”.
4
C ara-cara m enyatakan bikondisional p q :
(a) p jika dan hanya jika q .
(b) p adalah syarat perlu dan cukup untuk q .
(c) Jika p m aka q , dan sebaliknya.
(d) p iff q
5
C ontoh 22. Proposisi m ajem uk berikut adalah bi-
im plikasi:
(a) 1 + 1 = 2 jika dan hanya jika 2 + 2 = 4.
(b) Syarat cukup dan syarat perlu agar hari hujan
adalah kelem baban udara tinggi.
(c) Jika anda orang kaya m aka anda m em punyai
banyak uang, dan sebaliknya.
(d) B andung terletak di Jaw a B arat iff Jaw a B arat
adalah sebuah propinsi di Indonesia.
6
C ontoh 23. Tuliskan setiap proposisi berikut ke dalam bentuk “ p jika dan
hanya jika q”:
(a) Jika udara di luar panas m aka anda m em beli es krim , dan jika
anda m em beli es krim m aka udara di luar panas.
(b) Syarat cukup dan perlu agar anda m em enangkan pertandingan
adalah anda m elakukan banyak latihan.
(c) A nda naik jabatan jika anda punya koneksi, dan anda punya
koneksi jika anda naik jabatan.
(d) Jika anda lam a m enonton televisi m aka m ata anda lelah, begitu
sebaliknya.
(e) K ereta api datang terlam bat tepat pada hari-hari ketika saya
m em butuhkannya.
Penyelesaian :
(a) A nda m em beli es krim jika dan hanya jika udara di luar panas.
(b) A anda m em enangkan pertandingan jika dan hanya jika anda
m elakukan banyak latihan.
(c) A nda naik jabatan jika dan hanya jika anda punya koneksi.
(d) M ata anda lelah jika dan hanya jika anda lam a m enonton televisi.
(e) K ereta api datang terlam bat jika dan hanya jika saya
m em butuhkan kereta hari itu .
7
Bila dua proposisi majemuk yang ekivalendi-bikondisionalkan, maka hasilnya adalahtautologi (hasilnya benar untuk semuakasus).
Teorema:
Dua buah proposisi majemuk, P(p, q, ..) danQ(p, q, ..) disebut ekivalen secara logika,dilambangkan dengan P(p, q, …) Q(p, q,…), jika P Q adalah tautologi.
Soal latihan 38
Sebagian besar orang percaya bahwa harimau Jawasudah lama punah. Tetapi, pada suatu hari Amirmembuat pernyataan-pernyataan kontroversial sebagaiberikut:
(a) Saya melihat harimau di hutan.
(b) Jika saya melihat harimau di hutan, maka saya jugamelihat srigala.
Misalkan kita diberitahu bahwa Amir kadang-kadangsuka berbohong dan kadang-kadang jujur. Gunakantabel kebenaran untuk memeriksa apakah Amir benar-benar melihat harimau di hutan?
Penyelesaian soal latihan 39
(a) Saya melihat harimau di hutan.
(b) Jika saya melihat harimau di hutan, maka sayajuga melihat srigala.
Misalkan
p : Amir melihat harimau di hutan
q : Amir melihat srigala
Pernyataan untuk (a): p
Pernyataan untuk (b): p q
10
Tabel kebenaran p dan p q
p q p q
T T T T F F F T T F F T
Kasus 1: Amir dianggap berbohong, maka apa yang dikatakan Amir itu keduanya salah ( p salah, q salah) Kasus 2: Amir dianggap jujur, maka apa yang dikatakan Amir itu keduanya benar (p benar, q benar).
Tabel menunjukkan bahwa mungkin bagi p dan p q benar, tetapi tidak mungkin keduanya salah. Ini berarti Amir mengatakan yang sejujurnya, dan kita menyimpulkan bahwa Amir memang benar melihat harimau di hutan.
Soal latihan 411
[LIU85] Sebuah pulau didiami oleh dua suku asli.
Penduduk suku pertama selalu mengatakan hal
yang benar, sedangkan penduduk dari suku lain
selalu mengatakan kebohongan. Anda tiba di
pulau ini dan bertanya kepada seorang
penduduk setempat apakah di pulau tersebut
ada emas atau tidak. Ia menjawab, “Ada emas
di pulau ini jika dan hanya jika saya selalu
mengatakan kebenaran”. Apakah ada emas di
pulau tersebut?
Penyelesaian soal latihan 412
Ada emas di pulau ini jika dan hanya jika saya selalu mengatakan kebenaran
Misalkan
p : saya selalu menyatakan kebenaran
q : ada emas di pulau ini
Ekspresi logika: p q
Tinjau dua kemungkinan kasus:
Kasus 1, orang yang memberi jawaban adalah orangdari suku yang selalu menyatakan hal yang benar.
Kasus 2, orang yang memberi jawaban adalah orang
dari suku yang selalu menyatakan hal yang bohong.
13Kasus 1: orang tersebut selalu menyatakan hal yang benar. Ini
berarti p benar, dan jawabannya terhadap pertanyaan kita pastijuga benar, sehingga pernyataan bi-implikasi tersebut bernilaibenar. Dari Tabel bi-implikasi kita melihat bahwa bila p benardan p q benar, maka q harus benar. Jadi, ada emas di pulautersebut adalah benar.
Kasus 2: orang tersebut selalu menyatakan hal yang bohong. Iniberarti p salah, dan jawabannya terhadap pertanyaan kita pastijuga salah, sehingga pernyataan bi-implikasi tersebut salah.Dari Tabel bi-implikasi kita melihat bahwa bila p salah dan p qsalah, maka q harus benar. Jadi, ada emas di pulau tersebutadalah benar.
Dari kedua kasus, kita selalu berhasil menyimpulkanbahwa ada emas di pulau tersebut, meskipun kitatidak dapat memastikan dari suku mana orangtersebut.
14
A rgum en
A rgum en adalah suatu deret proposisi yang dituliskan sebagai
p 1
p 2
p n
q
yang dalam hal ini, p 1, p 2, … , p n d isebut hipotesis (atau prem is),
dan q d isebut konklusi.
A rgum en ada yang sahih (valid ) dan palsu (invalid).
15
D efinisi. Sebuah argum en dikatakan sahih jika konklusi
benar bilam ana sem ua hipotesisnya benar; sebaliknya
argum en dikatakan palsu ( fallacy atau invalid ).
Jika argum en sahih, m aka kadang -kadang kita m engatakan
bahw a secara logika konklusi m engikuti hipotesis atau
sam a dengan m em perlihatkan bahw a im plikasi
(p 1 p 2 p n) q
adalah benar (yaitu, sebuah tautologi). A rgum en yang
palsu m enunjukkan proses penalaran yang tidak benar.
16
Contoh 1
Perlihatkan bahwa argumen berikut:
Jika air laut surut setelah gempa di laut, maka
tsunami datang. Air laut surut setelah gempa di
laut. Karena itu tsunami datang.
adalah sahih.
Penyelesaian:
Misalkan:
p : Air laut surut setelah gempa di laut
q : Tsunami datang:
Argumen:
p q
p
q
Ada dua cara yang dapat digunakan untuk membuktikan kesahihan
argumen ini.
17
C ara 1 : B entuklah tabel kebenaran untuk p, q , dan p q
p q p q
T T T (baris 1)
T F F (baris 2)
F T T (baris 3)
F F T (baris 4)
A rgum en dikatakan sahih jika sem ua hipotesisnya benar, m aka
konklusinya benar. K ita periksa apabila hipotesis p dan p q
benar, m aka konklusi q juga benar sehingga argum en dikatakan
benar. Periksa tabel, p dan p q benar secara bersam a-sam a pada
baris 1. Pada baris 1 ini q juga benar. Jadi, argum en di atas sahih .
18
C ara 2: Perlihatkan dengan tabel kebenaran apakah
[ p (p q ) ] q
m erupakan tautologi. Tabel 1.16 m em perlihatkan bahw a [ p (p q ) ] q suatu
tautologi, sehingga argum en dikatakan sahih.
Tabel 1.16 [ p (p q ) ] q adalah tauto logi
p q p q p (p q ) [ p (p q) ] q
T T T T T
T F F F T
F T T F T
F F T F T
Perhatikanlah bahw a penarikan kesim pulan di dalam argum en ini m enggunakan m odus
ponen. Jadi, k ita kita juga telah m em perlihatkan bahw a m odus ponen adalah argm en yang
sahih.
19
C ontoh 2:
Perlihatkan bahw a penalaran pada argum en berikut:
“Jika air laut surut setelah gem pa di laut, m aka tsunam i datang.
Tsunam i datang. Jadi, air laut surut setelah gem pa di laut”
tidak benar, dengan kata lain argum ennya palsu.
Penyelesaian :
A rgum en di atas berbentuk
p q
q
p
D ari tabel tam pak bahw a hipotesis q dan p q benar pada
baris ke-3, tetapi pada baris 3 ini konklusi p salah. Jadi,
argum en tersebut tidak sahih atau palsu, sehingga penalaran
m enjadi tidak benar.
p q p q
T T T (baris 1)T F F (baris 2)F T T (baris 3)F F T (baris 4)
20
C ontoh 3:
Periksa kesahihan argum en berikut in i:
Jika 5 lebih kecil dari 4 , m aka 5 bukan bilangan prim a.
5 tidak lebih kecil dari 4 .
5 adalah bilangan prim a
Penyelesaian :
M isalkan p : 5 lebih kecil dari 4
q : 5 adalah bilangan prim a.
A rgum en:
p ~q
~p
q
Tabel m em perlihatkan tabel kebenaran untuk kedua hipotesis dan
konklusi tersebut. B aris ke -3 dan ke-4 pada tabel tersebut adalah baris d i
m ana p ~q dan ~ p benar secara bersam a-sam a, tetapi pada baris ke -4
konklusi q salah (m eskipun pada baris ke-3 konklusi q benar). In i
berarti argum en tersebut palsu.
p q ~ q p ~ q ~p
T T F F FT F T T FF T F T TF F T T T
21
Perhatikanlah bahw a m eskipun konklusi dari argum en
tersebut kebetulan m erupakan pernyataan yang benar (“5
adalah bilangan prim a” adalah benar),
tetapi konklusi dari argum en ini tidak sesuai dengan bukti
bahw a argum en tersebut palsu.
Beberapa argumen yang sudah
terbukti sahih22
1. Modus ponen
p q
p
---------------
q
23
2. Modus tollen
p q
~q
---------------
~ p
24
3. Silogisme disjungtif
p q
~p
---------------
q
25
4. Simplifikasi
p q
---------------
p
26
5. Penjumlahan
p
---------------
p q
27
6. Konjungsi
p
q
---------------
p q
Aksioma, Teorema, Lemma, Corollary
28
A ksiom a adalah proposisi yang diasum sikan benar.
A ksiom a tidak m em erlukan pem buktian kebenaran lagi.
C ontoh-contoh aksiom a:
(a) U ntuk sem ua bilangan real x dan y , berlaku x + y = y +
x (hukum kom utatif penjum lahan).
(b) Jika diberikan dua buah titik yang berbe da, m aka
hanya ada satu garis lurus yang m elalui dua buah titik
tersebut.
T eorem a adalah proposisi yang sudah terbukti benar.
B entuk khusus dari teorem a adalah lem m a dan corolarry .
29
C ontoh-contoh teorem a:
a. Jika dua sisi dari sebuah segitiga sam a panjang, m aka
sudut yang berlaw anan dengan sisi tersebut sam a besar.
b . U ntuk sem ua bilangan real x , y , dan z , jika x y dan y
z , m aka x z (hukum transitif).
C ontoh corollary :
Jika sebuah segitiga adalah sam a sisi, m aka segitiga
tersebut sam a sudut.
C orollary ini m engikuti teorem a (a) di atas.
C ontoh lem m a :
Jika n adalah bilangan bulat positif, m aka n – 1 bilangan
positif atau n – 1 = 0.
Istilah-istilah30
logika
proposisi
pernyataan
konjungsi
disjungsi
disjungsi eksklusif
negasi
tautologi
kontradiksi
implikasi/kondisional
biimplikasi
konvers
invers
kontraposisi
aksioma
teorema
lemma
corollary