LOGIKA dan ALGORITMA
Materi kuliah Dosen Pengampu: Heri Sismoro, S.Kom., M.Kom.
MATERI 1 PROPOSITIONAL LOGIC
1.1 Pengantar Beberapa pernyataan (statement) dapat langsung diterima kebenarannya tanpa harus tahu kebenaran pembentuknya Contoh:
“Ada kehidupan di Bulan atau tidak ada kehidupan di Bulan” “Indonesia mempunyai jumlah penduduk yang lebih besar dari Cina atau Indonesia mempunyai jumlah penduduk yang lebih kecil atau sama dengan Cina” Kalimat tersebut merupakan contoh dari kalimat abstrak P or (not P) Kalimat abstrak adalah “valid” jika bernilai benar tanpa mempedulikan kebenaran atau kesalahan dari proposisiproposisi penyusunnya. Contoh: Not (P and (not P)) or Q Maka, kita bisa simpulkan kalimat berikut adalah valid: Not ( [x<0] and (not [x<0] ) ) or (y>0)
Materi 1. Proposition Logic
LOGIKA dan ALGORITMA
Materi kuliah Dosen Pengampu: Heri Sismoro, S.Kom., M.Kom.
Pasangan kalimat abstrak berikut “ekuivalen” If P then Q
dan
if (not Q) then (not P)
Contoh kalimatnya:
“Jika seorang mahasiswa mengikuti ujian akhir suatu mata kuliah, maka mahasiswa tersebut akan mendapat nilai untuk mata kuliah tersebut” dan
“Jika seorang mahasiswa tidak mendapat nilai untuk mata kuliah, maka mahasiswa tersebut tidak mengikuti ujian akhir untuk mata kuliah tersebut”
1.2 Bahasa ~Language Proposisi ~Propositions Logika proposisional terdiri dari kalimat-kalimat (sentences) Kalimat dalam logika proposisional dibentuk dari simbol-simbol yang disebut proposisi Simbol yang digunakan: • Simbol-simbol kebenaran (truth symbols) true dan false • Simbol-simbol proposisional (propositional symbol) P, Q, R, P1, Q1, R1, ... (huruf-huruf P, Q, R, atau S ) Diwakili oleh kalimat deklaratif, bukan kalimat terbuka • Kalimat Deklaratif Æ kalimat yang dapat ditentukan nilai kebenarannya, yaitu true atau false
Materi 1. Proposition Logic
LOGIKA dan ALGORITMA
Materi kuliah Dosen Pengampu: Heri Sismoro, S.Kom., M.Kom.
Kalimat ~Sentences Kalimat dalam logika proposisional dari proposisi dengan menggunakan “propositional conectives”, yaitu: not, and, or, if-then, if-and-only-if, if-then-else Aturan pembentukan kalimat: • Setiap proposisi adalah kalimat • Apabila P kalimat, maka demikian juga negasinya ( not P ) • Apabila P dan Q kalimat, maka demikian juga kunjungsi (conjunction)-nya, yaitu (P and Q ) • Apabila P dan Q kalimat, maka demikian juga disjungsi (disjunction)-nya, yaitu (P or Q ) • Apabila P dan Q kalimat, maka demikian juga implikasi (implication)-nya, yaitu (if P then Q ), selanjutnya P disebut “antecedent” dan Q disebut “consequent” dari (if P then Q) Kalimat (if Q then P )disebut “converse” dari kalimat (if P then Q ) • Apabila P dan Q kalimat, maka demikian juga ekuivalensi (equivalence)-nya, yaitu (P if and only if Q ) • Apabila P, Q dan R kalimat, maka demikian juga kondisional (conditional)-nya, yaitu (if P then Q else R )
Notasi ~Notation Pasangan kurung dalam kalimat bisa dihilangkan apabila tidak menunjukan struktur dari kalimat, contoh (not (P and (not Q))) dapat ditulis: not (P and (not Q)) Digunakan pasangan kurung siku, [ dan ], atau kurung kurawal { dan } dari pada beberapa pasangan kurung ( dan ), Contoh: (if ((P or Q) and (if Q then R)) then (if (P and Q) then (not R)))
bisa ditulis:
if
P or Q And if Q then R
Materi 1. Proposition Logic
then (if (P and Q) then not R)
LOGIKA dan ALGORITMA
Materi kuliah Dosen Pengampu: Heri Sismoro, S.Kom., M.Kom.
Notasi konvensional: Notasi not and or if-then if-and-only-if
Notasi Konvensional ~ ∧ V Æ
if-then-else
tidak ada
↔
Contoh penulisan dengan notasi konvensional dari kalimat berikut: (if ((P or Q) and (if Q then R)) then (if (P and Q) then (not R)))
adalah: ((P V Q) ∧ (Q Æ R)) ∧(P ∧Q) Æ (~ R)))
Latihan: 1. Berikan contoh-contoh kalimat valid 2. Berikan contoh kalimat deklaratif dan kalimat terbuka 3. Ubahlah kalimat berikut dengan simbol konvensional a. not (P and (not P)) or Q b. if P then Q) or (if Q then P) c. (not Q) or not[if P then (notQ) and P} d. (if P then (not Q) if and only if not (P and Q) e. [if (P or Q) then R] if and only if [(if P then R) and (if Q then R)] f. [P if and only if (Q if and only if R)] if and only if [(P if and only if Q) if and only if R] g. [if P then Q and R else (not Q) and S] if and only if [if Q then P and R else (not P) and S]
Materi 1. Proposition Logic
LOGIKA dan ALGORITMA
Materi kuliah Dosen Pengampu: Heri Sismoro, S.Kom., M.Kom.
1.3 Arti suatu Kalimat~Meaning of Sentence Interpretasi~Interpretation Adalah pemberian nilai kebenaran (true atau false) pada setiap symbol proposisi dari suatu kalimat logika. Contoh: P Å True Q Å False
Aturan Semantik~Semantic Rule Adalah suatu aturan yang digunakan untuk menentukan “truth value” dari suatu sentence, yaitu : 1. Negation Rule (Aturan NOT) P ~P True False False True 2. Conjunction Rule (Aturan AND) P Q True True True False False True False False
P∧Q True False False False
3. Disjunction Rule (Aturan OR) P Q True True True False False True False False
P∨Q True True True False
Materi 1. Proposition Logic
LOGIKA dan ALGORITMA
Materi kuliah Dosen Pengampu: Heri Sismoro, S.Kom., M.Kom.
Sifat-sifat aljabar logika untuk konjungsi dan disjungsi a. Hukum Idempoten =P P∨P =P PΛP b.
Hukum Komutatif PvQ = QvP PΛQ = QΛP
c.
Hukum Assosiatif (PVQ)V R = PV(QVR) = PΛ(QΛR) (PΛQ) ΛR
d.
Hukum Distributif = (PVQ) Λ (PVR) PV(QΛR) = (PΛQ) V (PΛR) PΛ(QVR)
e.
Hukum Identitas Pv False = = PΛTrue Pv True = = PΛ False
P P True False
f.
Hukum Komplemen Pv ~P = True = False PΛ ~ P ~(~ p) = P
g.
Hukum De Morgan Negasi dari konjungsi dan disjungsi: ~(PVQ) = ~P Λ ~Q ~(PΛQ) = ~P V ~Q
4. Implication Rule (Aturan IF-THEN) Implikasi bernilai “salah” bila anteseden benar dan konsekuen salah. P True True False False
Materi 1. Proposition Logic
Q True False True False
PÆQ True False True True
LOGIKA dan ALGORITMA
Materi kuliah Dosen Pengampu: Heri Sismoro, S.Kom., M.Kom.
Jika (PÆQ) adalah implikasi, maka : (QÆP) adalah konvers (~P Æ ~Q) adalah invers (~Q Æ ~P) adalah kontraposisi Jika (PÆQ) bernilai benar, maka belum tentu : (Q Æ P), (~P Æ ~Q) ,(~Q Æ ~P) bernilai benar. 5. Equivalence Rule (Aturan IF -AND ONLY IF -) Biimplikasi bernilai “benar”, jika penyusun proposisi bernilai sama P Q P↔Q True True True True False False False True False False False True 6. Conditional Rule (Aturan IF–THEN-ELSE) Jika p bernilai benar maka q berlaku, Jika p bernilai salah maka r berlaku P Q R if P then Q else R True True True True True True False True True False True False True False False False False True True True False True False False False False True True False False False False
Materi 1. Proposition Logic
LOGIKA dan ALGORITMA
Materi kuliah Dosen Pengampu: Heri Sismoro, S.Kom., M.Kom.
1.4 Tabel Kebenaran ~Truth Table Adalah metode untuk menentukan nilai kebenaran dari suatu kalimat logika yang disajikan dengan baris dan kolom dengan menginterpretasi setiap simbol proposisi dan menggunakan aturan semantik. Contoh: Diberikan kalimat logika, sebagai berikut: (P and (if R then S)) if only if ((if R then S) and P) Tentukan nilai kebenarannya (truth value) dari kalimat tersebut di atas.
1.5 Sifat-sifat Kalimat Logika ~Properties of Sentence Valid Suatu sentence f disebut valid, jika untuk setiap interpretation I for f, maka f true Contoh: a. (F and G) if and only if (G and F) b. F or not F c. (P and (if R then S)) if only if ((if R then S) and P) d. (P or Q) or not (P or Q) e. (if P then not Q) if and only if not (P and Q) Satisfiable Suatu sentence f disebut satisfiable, jika untuk suatu interpretation I for f, maka f true Contoh: a. If (if P then Q) then Q b. (if P then Q) or (R and S) c. (if P then Q) or R
Materi 1. Proposition Logic
LOGIKA dan ALGORITMA
Materi kuliah Dosen Pengampu: Heri Sismoro, S.Kom., M.Kom.
Kontradiksi Suatu sentence f disebut kontradiksi, jika untuk setiap interpretation I for f, maka f false Contoh: a. P and not P b. ((P or Q) and not R) if and only if ((if P then R) and (if Q then R)
Materi 1. Proposition Logic