=> salah jika p benar q salah
<=> benar jika q ^ p bernilai sama
metode penarikan kesimpulan
Jika pintu kereta api ditutup, lalu lintas akan berhenti.
Jika lalu lintas berhenti, akan terjadi kemacetan lalu lintas.
Pintu kereta api ditutup.
Jadi, terdapat kemacetan lalu lintas.
Misal:
p : pintu kereta api ditutup
q : lalu lintas akan berhenti
r : terjadi kemacetan lalu lintas
Simbol untuk argument diatas adalah:
p⇒q
q⇒r
p
∴r
Proses pembuktian validitas argument diatas adalah sebagai berikut:
1. p ⇒ q Pr
2. q ⇒ r Pr
3. p Pr / ∴r
4. q 1,3 MP
5. r 2,4 MP
aturan penukaran
Susunlah bukti formal validitas argument berikut
( p ∨ q) ⇒ ( r ∧ s)
~r
∴~ q
Proses pembuktian validitas argument diatas adalah sebagai berikut:
1. ( p ∨ q) ⇒ ( r ∧ s) Pr
2. ~ r Pr / ∴~ q
3. ~ r ∨ ~ s 2, Add
4. ~ (r ∧ s) 3, de M
5. ~ (p ∨ q) 1,4 MT
6. ~ p ∧ ~ q 5, de M
7. ~ q ∧ ~ p 6, Kom
8. ~ q 7, Simp
TURAN PEMBUKTIAN KONDISIONAL (Rule of Conditional Proof).
Penerapan aturan pembuktian kondisional, akan diperoleh argument
A ⇒ (B ⇒ C)
C ⇒ (D ∧ E)
A
B
/ ∴D
Proses pembuktian validitas argument diatas adalah sebagai berikut:
1. A ⇒ (B ⇒ C) Pr
2. C ⇒ (D ∧ E) Pr / ∴A ⇒(B ⇒D)
3. A Pr / ∴ B ⇒D (CP)
4. B Pr / ∴ D (CP)
5. B ⇒ C 1,3 MP
6. C 4,5 MP
7. D ∧ E
8. D 7, Simp
ATURAN PEMBUKTIAN TIDAK LANGSUNG
Susunan pembuktian tidak langsung untuk memperlihatkan validitas argument berikut
P⇒Q P
Q⇒R ∴R
Jawab:
1. P ⇒ Q Pr
2. Q ⇒ R
3. P Pr / ∴R
4. ~ R IP
5. ~ Q 2,4 MT
6. ~P 1,5 MT
7. P ∧ ~P 3,6 Konj
Baris (7) adalah suatu kontradiksi
PEMBUKTIAN INVALIDITAS ARGUMEN (METODE PENETAPAN
NILAI KEBENARAN)
Contoh:
Buktikan bahwa argument berikut tidak valid.
P∨Q
Q∨R
∴P∨R
Jawab:
Langkah 1: Ubah argument diatas menjadi pernyataan kondisional yang
berkoresponden dengan argument diatas.
[ (P ∨ Q) ∧ (Q ∨ R) ] ⇒ (P ∨ R)
Langkah 2 : Beri nilai T pada premis-premis dan F pada konklusi
Bahan kuliah logika matematika
6
[ (P ∨ Q) ∧ (Q ∨ R) ] ⇒ (P ∨ R)
T
T
F
F
Langkah 3 : Turunkan nilai kebenaran dari setiap variabel yang ada pada argument
tersebut (pilih pernyataan yang hanya mempunyai satu kemungkinan). Dalam contoh
diatas kita bisa langsung memberi nilai pada variabel P dan R karena (P ∨ R) akan
bernilai salah hanya jika P salah dan R salah.
[ (P ∨ Q) ∧ (Q ∨ R) ] ⇒ (P ∨ R)
FT
TF
FFF
Langkah 4 : Dari hasil dari langkah (3), kita dapat menurunkan nilai kebenaran
untuk Q yaitu benar.
[ (P ∨ Q) ∧ (Q ∨ R) ] ⇒ (P ∨ R)
FT T TTF FFF
Langkah diatas menunjukan bahwa argument tersebut tidak valid.
Disisi lain metode ini juga dapat digunakan untuk menujukan argument yang valid.
Artinya, jika kita mengikuti langkah diatas ternyata pada akhirnya menimbulkan hal
yang bersifat kontradiksi, maka argument yang akan diselidiki tersebut valid.
Contoh:
P∨Q
~P
∴Q
Jawab:
Langkah 1:
Langkah 2:
[(P ∨ Q) ∧ ~ P ] ⇒ Q
T
T
F
[(P ∨ Q) ∧ ~ P ] ⇒ Q
T F T
F
Langkah 3:
[(P ∨ Q) ∧ ~ P ] ⇒ Q
T F TF
F
Langkah 4:
[(P ∨ Q) ∧ ~ P ] ⇒ Q
FTF TF
F
Timbul kontradiksi karena (P ∨ Q) yang bernilai benar tidak mungkin terjadi jika P
salah dan Q salah. Akibatnya, argument diatas valid.
KALIMAT BERKUANTOR
Contoh 2.8 :
1. ”Semua tanaman hijau membutuhkan air untuk tumbuh ”.
• Jika x adalah tanaman hijau, maka x membutuhkan air untuk
tumbuh
Tanaman hijau(x) ⇒ membutuhkan air untuk tumbuh(x)
• (∀x) (Tanaman hijau(x) ⇒ membutuhkan air untuk tumbuh(x))
• (∀x)(T(x) ⇒ A(x))
KALIMAT BERKUANTOR
(a). Semua pria mencintai wanita
Kalimat diatas sama artinya dengan
Untuk semua x, y , jika x adalah pria dan y adalah wanita, maka x mencintai y.
Misal: p(x) : x adalah pria
w(y) : y adalah wanita
r(x,y) : x mencintai y
maka simbol untuk pernyataan diatas adalah:
(∀x) (∀y) [( p(x) ∧ w(y) ) ⇒ r(x,y)]
(b). Semua wanita mencintai semua pria.
(∀x) (∀y) [( p(x) ∧ w(y) ) ⇒ r(y,x)]
(c). Beberapa pria mencintai beberapa wanita.
Kalimat diatas sama artinya dengan
Terdapatlah x dan y sedemikian sehingga x adalah pria dan y adalah wanita dan x
mencintai y.
Simbol pernyataan diatas adalah:
(∃x) (∃y) [ p(x) ∧ w(y) ∧ r(x,y)]
Bahan Kuliah Logika Matematika
Kun Siwi Trilestari, S.Kom
3
(d). Semua pria mencintai beberapa wanita
Kalimat diatas sama artinya dengan
Untuk setiap x, jika x adalah pria, maka terdapat y sedemikian sehingga y adalah
wanita dan x mencintai y.
Simbol pernyataan diatas adalah
(∀x) [ p(x) ⇒ (∃y) (w(y) ∧ r(x,y))]
(e). Beberapa pria mencintai semua wanita
Kalimat diatas sama artinya dengan
Terdapatlah x sedemikian sehingga x adalah pria dan untuk setiap y, jika y adalah
wanita, maka x mencintai y.
Simbol pernyataan diatas adalah
(∃x) [ p(x) ∧ (∀y) ( w(y) ⇒ r(x,y))]
Kalimat diatas juga mempunyai arti yang sama dengan kalimat
Untuk semua x, jika x adalah wanita, maka terdapatlah y sedemikian sehingga y
adalah pria dan y mencintai x.
yang mempunyai simbol
(∀x) [ w(x) ⇒ (∃y) (p(y) ∧ r(y,x))]
PEMBUKTIAN VALIDITAS ARGUMENT BERKUANTOR
Untuk menyusun bukti langsung validitas sebuah argument yang mengandung
kuantor dan fungsi proposisi, kita memerlukan aturan tambahan baru. Ada empat
aturan tambahan, yaitu:
1. Universal Instantion (UI)
(∀x) M(x)
∴M(a)
(a adalah lambang individual)
2. Universal Generalization (UG)
M(a)
∴(∀x) M(x)
3. Existential Generalization (EG)
M(a)
∴(∃x) M(x)
4. Existential Instantiation (EI)
(∃x) M(x)
∴M(y)
(y adalah konstanta individual selain ‘a’ yang tidak pernah
muncul dalam pembuktian)
Contoh 1:
Semua kucing adalah hewan menyusui.
Puppy adalah seekor kucing.
Jadi, Puppy adalah hewan menyusui.
Pembuktian dapat dilakukan dengan langkah berikut:
1. (∀x) (K(x) ⇒ H(x))
Pr
2. K(p) Pr / ∴H(p)
3. K(p) ⇒ H(p) 1, UI
4. H(p) 2,3 MP
Bahan Kuliah Logika Matematika
Kun Siwi Trilestari, S.Kom
2
Contoh 2:
Semua bilangan cacah adalah bilangan real.
Tak ada bilangan real yang habis dibagi nol.
Jadi, tak ada bilangan cacah yang habis dibagi nol.
Langkah pembuktian argument diatas adalah:
1. (∀x) (A(x) ⇒ B(x)) Pr
2. (∀x) (B(x) ⇒ ~ C(x)) Pr / ∴(∀x) (A(x) ⇒ ~C(x))
3. A(a) ⇒ B(a) UI
4. B(a) ⇒ ~ C(a) UI
5. A(a) ⇒ ~ C(a) 3,4 HS
6. (∀x) (A(x) ⇒ ~C(x)) 5 UG
Tidak ada komentar:
Posting Komentar