MATERI 1 PROPOSITIONAL LOGIC

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



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




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


then (if (P and Q) then not R)



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]




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




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


Q True False True False

PÆQ True False True True



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




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




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 PROPOSITIONAL LOGIC

Recommend Documents