proposition logic - kata felix...sifat-sifat aljabar logika untuk konjungsi dan disjungsi hukum...

Proposition Logic (Logika Proposisional)

Bimo Sunarfri [email protected]

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)

2. Conjunction Rule (Aturan AND)

3. Disjunction Rule (Aturan OR)

4. Implication Rule (Aturan IF-THEN)

5. Equivalence Rule (Aturan IF -AND ONLY IF -)

6. Conditional Rule (Aturan IF–THEN-ELSE)


Negation Rule (Aturan NOT)

p not p

true false

false true


Conjunction Rule (Aturan AND)

p q p and q

true true true

true false false

false true false

false false false


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

Hukum Idempoten

p or p = p

p and p = p

Hukum Komutatif

p or q = q or p

p and q = q and p

Hukum Assosiatif

(p or q) or r = p or (q or r)

(p and q) and r = p or (q or r)


Hukum Distributif

p or (q and r) = (p or q) and (p or r)

p and (q or r) = (p and q) or (p and r)

Hukum Identitas

p or false = p

p and true = p

p or true = true

p and false = false


Hukum Komplemen

p or not p = true

p and not p = false

not (not p) = p

Hukum De Morgan

negasi dari konjungsi dan disjungsi

not (p or q) = not p and not q

not (p and q) = not p or not q


Implication Rule (Aturan IF-THEN)

Implikasi bernilai “salah” bila anteseden benar dan konsekuen salah.

p q if p then q

true true true

true false false

false true true

false false true


Implication Rule (Aturan IF-THEN)

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.


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


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 rtrue true true truetrue true false truetrue false true falsetrue false false falsefalse true true truefalse true false falsefalse false true truefalse false false 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)

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…)

2. Existential Quantifier (for some…)

Quantifier Sentence

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

3. Seluruh mahasiswa ganteng-ganteng dan cantik-cantik

Quantifier Sentence

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:

p : Semua mahasiswa harus pandai

~p : Ada mahasiswa yang tidak pandai

q : Ada pejabat yang korupsi

~p : Semua pejabat tidak korupsi

Pembuatan Kesimpulan Berdasarkan Implikasi

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


Modus Tellens p -> q ~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


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)

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

proposition logic - kata felix...sifat-sifat aljabar logika untuk konjungsi dan disjungsi hukum...

Documents