1.propositionlogic(pert1-2)

BAGIAN 1.

PROPOSITION LOGIC (LOGIKA PROPOSISIONAL) Proposition (pernyataan) Merupakan komponen penyusun logika dasar yang dilambangkan dengan huruf kecil (p, q, r, …..) yang memiliki nilai kebenaran (True atau False).  Diwakili oleh kalimat deklaratif.  Lawan kalimat deklaratif  Kalimat Terbuka  Untuk mengkombinasikan dua atau lebih proposisi diperlukan “connective/penghubung”. 

Syntactics Rule (Aturan Sintaktik) Adalah aturan yang diperlukan untuk mengkombinasikan antara propositions dan propositional connectives untuk menghasilkan sentences (kalimat logika).

Propositions + Propositional Connectives  Sentences Propositional connective yang digunakan adalah : Not (~), and (∧), or (∨), if – then - (), If – then - else, dan if and only if ( )

Interpretasi Adalah pemberian nilai kebenaran (true atau false) pada setiap symbol proposisi dari suatu kalimat logika.

Semantic Rule (Aturan Semantik) Adalah suatu aturan yang digunakan untuk menentukan “truth value” dari suatu sentence, yaitu : 1. Negation Rule (Aturan NOT)

p True False

Materi Kuliah Logika dan Algoritma Copyright © 2007 – Hanif Al Fatta

not p False True

1

2. Conjunction Rule (Aturan AND)

p q p and q True True True True False False False True False False False False 3. Disjunction Rule (Aturan OR) p q p or q True True True True False True False True True False False False

Sifat-sifat aljabar logika untuk konjungsi dan disjungsi a. Hukum Idempoten pvp =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 pv(qΛr) = (pvq) Λ (pvr) pΛ(qvr) = (pΛq) v (pΛr) e. Hukum Identitas pv False = p pΛTrue = p pv True = True pΛ False = False f. Hukum Komplemen pv not p = True pΛnot p = False not (not p)

Materi Kuliah Logika dan Algoritma Copyright © 2007 – Hanif Al Fatta

= p

2

g. Hukum De Morgan Negasi dari konjungsi dan disjungsi: not (pvq) = not p Λ not q not (pΛq) = not p v not 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

If p then q True False True True

Jika (pq) adalah implikasi, maka : (qp) adalah konvers (not pnot q) adalah invers (not qnot p) adalah kontraposisi Jika (pq) bernilai benar, maka: belum tentu (q  p), (not p  not q), (not q  not p) bernilai benar. 5. Equivalence Rule (Aturan IF -AND ONLY IF -)

Biimplikasi bernilai “benar”, jika penyusun proposisi bernilai sama p q p if and only if 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

Materi Kuliah Logika dan Algoritma Copyright © 2007 – Hanif Al Fatta

3

False False False False

True True False False

True False True False

True False True False

LATIHAN. 1. Tentukan nilai kebenaran (truth value) dari sentence berikut, dengan menggunakan truth table : a) F: (f and g) if and only if (g and g) b) G: if (if p then q) then q c) H: ((p or q) and not r) if and only if (if p then r) and (if q then r) 2. Jika diberikan suatu nilai (interpretasi) True untuk p dan s dan False untuk q dan r, maka tentukanlah nilai kebenaran untuk kalimat berikut: a) ((if p then q) and (if q then p) if and only if (q or not p) b) (p and (if r then s)) if and only if ((if r then s) and p)

Materi Kuliah Logika dan Algoritma Copyright © 2007 – Hanif Al Fatta

4

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)

Quantifier Sentence  Pernyataan yang memuat ekspresi kuantitas obyek yang terlibat Misalnya: semua, ada, beberapa, tidak semua, dll Ada dua macam, kuantor: 1. Universal Quantifier (for all…) ♦ Mempunyai makna umum dan menyeluruh ♦ Notasi: ∀, dibaca semua, seluruh, setiap ♦ Penulisan: ∀x ∈ S  p(x) Semua x dalam semesta s mempunyai sifat p ♦ Contoh: 1. Semua orang yang hidup pasti mati 2. Setiap mahasiswa pasti pandai

Materi Kuliah Logika dan Algoritma Copyright © 2007 – Hanif Al Fatta

5

3. Seluruh mahasiswa amikom ganteng-ganteng dan cantik-cantik

2. Existential Quantifier (for some…) ♦ ♦ ♦

♦

Mempunyai makna khusus atau sebagian Notasi: ∃, dibaca terdapat, ada, beberapa Penulisan: ∃y ∈ S  q(y) Terdapat y dalam semesta s mempunyai sifat q Contoh: 1. Ada siswa di kelas ini yang ngantuk 2. Beberapa mahasiswa yang mendapat nilai A mata kuliah Logika dan Algoritma

Ingkaran Pernyataan Berkuantor (∀x) p(x) = (∃y) p(y) (∃y) q(y) = (∀x) q(x) Contoh: 1. p : Semua mahasiswa AMIKOM harus berdasi ~p : Ada mahasiswa AMIKOM yang tidak berdasi 2. q : Ada pejabat yang korupsi ~p : Semua pejabat tidak korupsi

Pembuatan Kesimpulan Berdasarkan Implikasi 1. Modus Ponens pq p q Contoh: Jika seseorang itu adalah mahasiswa maka ia pasti pandai Dian Sastro adalah seorang mahasiswa Dian Sastro pasti pandai 2. Modus Tellens pq

Materi Kuliah Logika dan Algoritma Copyright © 2007 – Hanif Al Fatta

6

~q ~p Contoh: Jika Inul adalah mahasiswi yang baik maka ia pasti tidak nyotek di ujian Inul nyontek dalam ujian Inul bukan mahasiswi yang baik

3. Prinsip Syllogisme pq q  r pr Contoh: Jika ia rajin maka ia pasti pandai Jika ia pandai maka ia pasti sukses Jika ia rajin maka ia pasti sukses

LATIHAN 1. Buktikan bahwa sentence berikut memiliki sifat “valid”

(p and (if r then s)) if and only if ((if r then s) and p) 2. Jika diberikan interpretasi p, q, dan r berturut turut

adalah True, False, dan True. Tentukan truth value dari sentence berikut: a. If ((if q then not p) or not q) then (p if and only if q) else not r b. If (if p then (if q then r)) then (if (if p then q) else (if p then r)) 3. Jika diberikan dua implikasi seperti berikut: If (p or q) or not (p or q) then ((f and g) if and only if (g and f) If ((f and g) if and only if (g and f) then ( p and not p) Materi Kuliah Logika dan Algoritma Copyright © 2007 – Hanif Al Fatta

7

Tentukan kesimpulannya dengan menggunakan prinsip Syllogisme, serta berikan truth value-nya dengan menggunakan truth table.

Materi Kuliah Logika dan Algoritma Copyright © 2007 – Hanif Al Fatta

8