Matdis 1, Logika Proposisi
Matematika diskrit Bagian dari matematika yang mempelajari objek diskrit. Banyak masalah yang dapat diatasi dengan menggunakan konsep yang ada di MATDIS, antara lain : 1. Berapa besar kemungkinan kita menang suatu undian lotere 2. Jalan mana yang paling pendek untuk mencapai sebuah kota tertentu Dalam bidang computer : 1. Apakah dua buah computer dalam sebuah jaringan memiliki hubungan, kalau ya bagaimana jalurnya? 2. Berapa banyak password yang ralid / sah yang bisa diterima oleh suatu system computer? Konsep-konsep yang diajarkan dalam MATDIS ini secara khusus merupakan konsep dasar untuk/dari kuliah/bidang computer lain : Struktur data, basis data, system operasi, teori compiler, system keamanan computer,dll. Bagaimana mempelajari Matdis dengan sukse: pahami teorinya, kerjakan / pahami latihan dan PR nya, semakin banyak semakin baik, belajar kelompok. Logika Proposisi Proposisi : kalimat yang bernilai benar atau salah tapi tidak keduanya. Contoh: 1. Jakarta ibukota Indonesia 2. Jam berapa sekarang 3. X+1 =2 4. 1+1 = 3 Proposisi biasanya dilambangkan dengan p,q,r,s…. Definisi : Bila p proposisi Not p juga proposisi p = hari ini hari Senin. ¬ p = hari ini bukan hari Senin. p dan q proposisi maka: 1. p ∩ q disebut proposisi conjunction 2. p V q disebut proposisi disjunction 3. p q disebut implikasi Syandra Sari
Page 1 of 5
versi 1Maret 2011
Matdis 1, Logika Proposisi
4. p q
disebut bikondisional
Pada p q p disebut antecedent / premise q disebut consequent / konklusi nama lain untuk implikasi: if p then q p implies q If p,q p only if q
p is sufficient for q q if p q whenever p q is necessary for p
jika p maka q p mengimplikasikan q jika p,q p hanya jika q
p syarat cukup untuk q q jika p q ketika p q diperlukan untuk p
Konverse dari p q adalah q p Kontra Positif p q dari adalah: ¬q ¬ p Merubah dari kalimat alami ke proposisi - Kalimat dianalisa - Tiap bagian diberi sebuah simbol - Dirangkai dengan menggunakan penghubung yang sesuai Contoh: Kamu dapat mengakses internet dari kampus hanya jika kamu dari jurusan informatika, atau kamu bukan mahasiswa tingkat pertama. Ada tiga kalimat: Kamu dapat mengakses internet dari kampus Hanya jika kamu dari jurusan informatika atau kamu mahasiswa tingkat pertama =r bukan =¬
=p = =q =V
Maka kalimat diatas menjadi: (p q) V ¬r Bagaimana bila kalimatnya diubah sedikit seperti berikut: (komanya di pindah menjadi dibelakang kata ”kampus”)
Syandra Sari
Page 2 of 5
versi 1Maret 2011
Matdis 1, Logika Proposisi
Kamu dapat mengakses internet dari kampus, hanya jika kamu dari jurusan informatika atau kamu bukan mahasiswa tingkat pertama. LOGIC AND OPERASI BIT - Dalam bentuk bit 0/1 - Bit string 0110 bit string ukuan 4 Bitwise operasi untuk bit string dengan ukuran yang sama sesuai dengan posisi. PROPOSITIONAL EKIVALENCE Mengganti sebuah statement dengan statement yang lain yang memiliki table kebenaran / nilai kebenaran yang sama. Definisi : Proposisi gabungan yang selalu bernilai true apapun nilai kebenaran masing-masing proposisi bangunnya disebut TAUTOLOGI Proposisi gabungan yang selalu bernilai false disebut KONTRADIKSI Proposisi gabungan yang dapat true / false disebut CONTINGENCY Contoh: Mana dari proposisi ini yang tautology, kontradiksi dan kontingensi p or not p, p and not p, p and q Proposisi p dan q disebut logically equivalent jika p q adalah tautology Notasinya: p ⇔ q Dua buah proposisi dapat dibuktikan logically equivalent dengan dua cara: 1. tabel kebenaran 2. proposisi-proposisi yang sudah terbukti logically equivalent
CARA PERTAMA, TABEL KEBENARAN: Berikut 5 buah tabel kebenaran DASAR: Tabel OR, Tabel AND, Tabel Negasi, Tabel Implikasi dan Tabel biimplikasi
Syandra Sari
Page 3 of 5
versi 1Maret 2011
Matdis 1, Logika Proposisi
Tabel Kebenaran: OR (^) p q p^q T T T T F F F T F F F F NEGASI (¬) p ¬p T F F T
p T T F F
q T F T F
AND (V) p Vq T T T F
IMPLIKASI (-> ) p q p-> q T T T T F F F T T F F T
BI-IMPLIKASI ( <-> ) p q p <-> q T T T T F F F T F F F T
Bila ada 2 proposisi sederhana yang berbeda maka diperlukan 22 baris = 4 baris pada tabel kebenarana Bila ada 3 proposisi sederhana yg berbeda maka diperlukan 23 baris = 8 baris pada tabel kebenaran Bila ada n proposisi sederhana yg berbeda maka diperlukan 2n baris pada tabel kebenaran Contoh: Buat tabel kebenaran untuk kalimat proposisi berikut: p ^ (q V r) Karena ada 3 buah proposisi sederhana, yaitu p, q, dan r maka tabel kebenarannya akan memiliki 23 baris = 8 baris, seperti berikut: p q r qVr p ^ (q V r) T T T T T T T F T T T F T T T T F F F F F T T T F F T F T F F F T T F F F F F F Soal: Dengan menggunakan tabel kebenaran tunjukkan bahwa : jika p maka q logically equivalent dengan not p or q.
Syandra Sari
Page 4 of 5
versi 1Maret 2011
Matdis 1, Logika Proposisi
CARA KEDUA, Menggunakan PROPOSISI yg terbukti EKIVALEN: Proposisi-proposisi yang terbukti logically equivalent : 1. Indentity laws 7. Distributive laws P ^ Q <=> P P V (Q ^ R) <=> (P V Q) ^ (P V R) P V Q <=> P P ^ (Q V R) <=> (P ^ Q) V (P ^ R) 2. Domination laws 8. De morgan’s law P V T <=> T ¬ ( P ^ Q ) <=> ¬ P V ¬ Q P ^ F <=> F ¬ ( P V Q ) <=> ¬ P ^ ¬ Q 3.Idempotent laws 9. Implikasi P V P <=> P P -> Q ¬P V Q P ^ P <=> P 10. Bi-implikasi 4. Double negation laws P <-> Q (P -> Q) ^ (Q -> P) ¬(¬ P) <=> P 11. Tautologi 5. Commutative laws ¬ P V P <=> T P V Q <=> Q V P 12. Kontradiksi P ^ Q <=> Q ^ P ¬ P ^ P <=> F 6. Associative laws (P V Q) V R <=> P V (Q V R) Keterangan: T= True, F=False (P ^ Q) ^ R <=> P ^ (Q ^ R) Contoh: Tunjukkan tanpa menggunakan tabel kebenaran bahwa:
¬( p ∨ (¬p ∧ q ))
logically equivalent dengan
¬ p ∧ ¬q
Jawab: ¬( p ∨ (¬p ∧ q )) ⇔ ¬p ∧ ((¬(¬p ∧ q )) − − − − Demorgan ⇔ ¬p ∧ ((¬¬p ) ∨ ¬q ) − − − − Demorgan ⇔ ¬p ∧ ( p ∨ ¬q ) − − − − − − DoubleNegasi ⇔ (¬p ∧ p) ∨ (¬p ∧ ¬q ) − − Distributive ⇔ F ∨ (¬p ∧ ¬q ) − − − − − − Kontradiksi ⇔ ¬p ∧ ¬q − − − − − − − − − Identity =======⇒ Terbukti Soal: Tunjukkan bahwa ( p ∧ q ) → ( p ∨ q ) adalah Tautologi: Jawab untuk membuktikan pernyataan diatas, maka kita harus membuktikan bahwa proposisi tsb logically equivalent dengan True.
Strategi: 1. bila ada (…..) gunakan De Morgan 2. bila ada (implikasi) gunakan aturan implikasi Syandra Sari
Page 5 of 5
versi 1Maret 2011
