materi 1. proposition logic -...

PROPOSITION LOGICProperties of Sentences

Inference MethodsQuantifier Sentences

LOGIKA INFORMATIKAHeri Sismoro, M.Kom.

STMIK AMIKOM Yogyakarta

1

Properties of Sentences

Adalah sifat-sifat yang dimiliki oleh kalimat logikaAda 3 sifat, yaitu:1. Valid2. Contradictory3. Satisfiable

2

Valid:Valid:Suatu sentence Suatu sentence ff disebut disebut validvalid, jika untuk setiap, jika untuk setiapinterpretation interpretation II for for ff, maka , maka ff truetrue

Contoh:Contoh:1. (f and g) if and only if (g and f)1. (f and g) if and only if (g and f)2. f or not f2. f or not f3. (p and (if r then s)) if only if ((if r then s) and p)3. (p and (if r then s)) if only if ((if r then s) and p)4. (p or q) or not (p or q)4. (p or q) or not (p or q)5. (if p then not q) if and only if not (p and q)5. (if p then not q) if and only if not (p and q)

3

Contradictory:Contradictory:Suatu sentence Suatu sentence ff disebut disebut contradictorycontradictory, jika untuk, jika untuksetiapsetiap interpretation interpretation II for for ff, maka , maka ff falsefalse

Contoh:Contoh:1.1. p and not pp and not p2. ((p or q) and not r) if and only if ((if p then r) 2. ((p or q) and not r) if and only if ((if p then r)

and (if q then r)and (if q then r)

4

Satisfiable:Suatu sentence Suatu sentence ff disebut disebut satisfiablesatisfiable, jika untuk , jika untuk suatusuatu interpretation interpretation II for for ff, maka , maka ff truetrue

Contoh:Contoh:1. if (if p then q) then q1. if (if p then q) then q2. (if p then q) and (not r and s)2. (if p then q) and (not r and s)3. (if r then q) or p

5

Inference Method

Suatu teknik/metode untuk menurunkan kesimpulan berdasarkan hipotesa yang diberikan, tanpa harus menggunakan tabel kebenaran

Misal:Modus PonensModus TolensPrinsip Sylogisme

6

Modus Ponens1. p q2. p 3. q

Contoh: 1. Jika suatu bilangan habis dibagi 2 maka

bilangan tersebut bilangan genap2. Suatu bilangan habis dibagi 23. Bilangan tersebut adalah bilangan genap

7

Modus Tolens1. p q2. ~q3. ~p

Contoh: 1. Jika suatu bilangan habis dibagi 2 maka

bilangan tersebut bilangan genap2. Ada suatu bilangan ganjil3. Bilangan tersebut tidak habis dibagi 2

8

Prinsip Sylogisme1. p q2. q r3. p r

Contoh: 1. Jika ia belajar dengan baik maka ia akan pandai2. Jika ia pandai maka ia akan lulus ujian3. Jika ia belajar dengan baik maka ia akan lulus ujian

9

Quantifier SentencesKalimat yang memuat ekspresi kuantitas obyekyang terlibat, misalnya: semua, ada, beberapa,tidak semua, dan lain-lain.

Ada dua macam, kalimat berkuantor:1. Universal Quantifier2. Existential Quantifier

10

Universal Quantifier (for all…)Terdapat kata-kata yg mempunyai makna umumdan menyeluruh.

Notasi: ∀, dibaca semua, seluruh, setiapPenulisan: ∀x ∈ S p(x)Semua x dalam semesta S mempunyai sifat p

Contoh: Semua orang yang hidup pasti mati Setiap mahasiswa pasti pandai

11

Existential Quantifier (for some…)Terdapat kata-kata yg mempunyai makna khusus/sebagian.

Notasi: ∃, dibaca terdapat, ada, beberapaPenulisan: ∃y ∈ S q(y)Terdapat y dalam semesta S mempunyai sifat q

Contoh: Ada siswa di kelas ini yang ngantukBeberapa mahasiswa ada yang mendapat nilai A untuk mata kuliah Pemrograman.

12

Ingkaran Pernyataan Berkuantor(∀x) p(x) = (∃y) p(y)(∃y) q(y) = (∀x) q(x)

Contoh:1. p : Semua mahasiswa di kelas ini enjoy belajar

logika Informatika~p : Ada mahasiswa di kelas ini yang tidak enjoy

belajar Logika Informatika2. q : Ada pejabat yang korupsi

~q : Semua pejabat tidak korupsi

13

Latihan

Pada suatu hari, Anda hendak pergi kuliah dan barusadar bahwa Anda tidak memakai kacamata. Setelah diingat-ingat, ada beberapa fakta dimanaAnda yakin itu benar:

1)Jika kacamataku ada di meja dapur, maka aku pasti sudah melihatnya ketika mengambil makanan kecil.

2)Aku membaca buku pemrograman di ruang tamu atau aku membacanya di dapur.

3)Jika aku membaca buku pemrograman di ruang tamu, maka pastilah kacamata kuletakkan di meja tamu.

14

4)Aku tidak melihat kacamataku ketika aku mengambil makanan kecil.

5)Jika aku membaca majalah di ranjang, maka kacamataku kuletakkan di meja samping ranjang.

6)Jika aku membaca buku pemrograman di dapur, maka kacamata ada di meja dapur.

Berdasar fakta-fakta tersebut, tentukan dimana letak kacamata tersebut!.

15

Penyelesaian:Untuk memudahkan dalam menggunakan penggunaan metode inferensi, maka kalimat-kalimat tersebut dinyatakan dengan simbol-simbol logika,

Misalnya:p : Kacamata ada di meja dapur.q : Aku melihat kacamataku ketika aku mengambil

makanan kecil.r : Aku membaca buku pemrograman di ruang tamu.s : Aku membaca buku pemrograman di dapurt : Kacamata kuletakkan di meja tamu.u : Aku membaca buku pemrograman di ranjang.w : Kacamata kuletakkan di meja samping ranjang.

16

Dengan simbol-simbol tersebut, maka fakta-fakta di atas dapat ditulis, sebagai berikut:

1. p q2. r ∨ s3. r t4. ~q5. u w6. s p

17

Inferensi yang dapat dilakukan adalah:1.p q

~ q~p

2. s p~p

~s3. r ∨ s

~sr

4. r tr

tKesimpulannya: Kacamata ada di meja tamu.

18

Gunakan prinsip inferensi untuk menurunkan ~q dari hipotesa-hipotesa:

1. if (r or q) then p2. not a3. if p then a

19

Exercise(cont)

Perhatikan hipotesa-hipotesa di bawah berikut:1. Jika saya rajin kuliah atau saya cerdas, maka saya akan lulus mata

kuliah Logika dan Algoritma.2. Saya tidak diijinkan mengambil mata kuliah pemrogmanan.3. Jika saya lulus mata kuliah logika dan algoritma, maka saya akan

diijinkan mengambil mata kuliah pemrograman.4. Saya cerdas

Misalkan:p: Saya rajin kuliahq: Saya cerdasr: Saya lulus ujian logika dan algoritmas: Saya diijinkan mengambil mata kuliah pemrograman

Nyatakan kalimat-kalimat di atas dengan simbol-simbol logika!, Kemudian simpulkan, apakan saya rajin kuliah?

20