SINTAKS DAN SEMANTIK PADA

LOGIKA PROPOSISI

Yenni Fatman, S.T.@2012

Matematika Logika

Semester Ganjil 2011/2012

Definisi: Preposisi

“Kemarin, Timmy pergi ke dokter karena sakit. Timmy diperbolehkan tidak ikut les apabila sedang sakit. Oleh karena itu, Timmy tidak ikut les hari ini.”

Kesimpulan: Timmy tidak ikut les hari ini.

Valid?

Definisi: Preposisi

Proposisi adalah kalimat deklaratif (atau pernyataan / statement) yang memiliki hanya SATU nilai kebenaran

BENAR

SALAH,

akan tetapi tidak keduanya (benar sekaligus salah)

4

PROPOSISI

Proposisi atau kalimat dalam logika proposisi bisaberupa

Atom/kalimat sederhana

Kalimat kompleks, komposisi kalimat menggunakanoperator logika

Kalimat sederhana bisa berupa

Simbol konstanta : true dan false

Simbol variabel proposisi : p,q,r,,p1,q1,…

Literal adalah atom atau negasinya

Definisi: Preposisi

Preposisi adalah kalimat berita yang bisa ditentukan kebenarannya:

Spongebob tinggal di Bikini Bottom

2 + 2 = 4

2 + 3 = 7

Jika Patrick tinggal di sebelah rumah Spongebob, maka Patrick tinggak di Bikini Bottom

Definisi: Preposisi

Contoh pernyataan yang bukan preposisi:

Mengapa komputer beguna?

Ketuk pintu sebelum masuk!

X-y = y - x

7

OPERATOR LOGIKA

Simbol Arti argument Ekivalensi

Negasi Target Not

Konjungsi Conjunct And

Disjungsi Disjunct Or

Implikasi Antecendent/premise

dan

consequent/conclusion

If … then …

BiImplikasi Antecendent/premise

dan

consequent/conclusion

… if and only

if …

8

SINTAKS

Definisi kalimat/proposisi :

Setiap konstanta logika true dan false adalah

proposisi

Variabel logika p,q,r,,p1,q1,… adalah proposisi

Jika dan adalah proposisi maka ,

, , dan adalah proposisi

Tidak ada bentuk lain yang merupakan proposisi

9

MEREPRESENTASIKAN FAKTA

Proposisi bisa merepresentasikan kalimat berita

p : saya malas belajar

q : saya lulus kuliah

p q : saya malas belajar dan lulus kuliah

p q : jika malas belajar saya tidak lulus

kuliah

q p : saya tidak lulus kuliah jika dan hanya

jika saya malas belajar

ATURAN PEMBENTUKAN KALIMAT

10

• Setiap proposisi adalah kalimat• Jika F adalah kalimat, begitu juga dengan negasinya.• Jika F dan G adalah kalimat, begitu juga dengan

konjungsinya.• Jika F dan G adalah kalimat, begitu juga dengan

disjungsinya.• Jika F dan G adalah kalimat, begitu juga dengan

implikasinya.• Jika F dan G adalah kalimat, begitu juga dengan

ekivalensinya.• Jika F, G dan H adalah kalimat, begitu juga dengan

kondisionalnya.

11

AMBIGUITY

Ambigu : mempunyai banyak arti

Contoh : pqr berarti p(qr ) atau (pq)r

Untuk menghilangkan ambiguity bisa

menggunakan ( dan ) atau prioritas operator

(precedence)

12

WELL-FORMED FORMULA (WFF)

Setiap atom adalah wff

Jika A dan B adalah wff maka proposisi

berikut ini juga wff : (A), (A B), (A B),

(A B), (A B)

Tidak ada bentuk lain yang wff

13

OPERATOR PRECEDENCE

Operator Precedence

1

2

3

4

5

SUB KALIMAT

14

Setiap komponen yang membentuk suatu kalimat

proposisi disebut juga subkalimat, termasuk kalimat

itu sendiri (proper subsentences).

Contoh :

F : (not (P or Q) ) if and only if ( P and (not Q) )

SUB KALIMAT

15

P or Q

not (P or Q)

not Q

P and (not Q)

F : (not (P or Q) ) if and only if ( P and (not Q) )

lprop: semantik - LFD - 2007 16

MAKNA KALIMAT

Arti kalimat = nilai kebenaran

Setiap kalimat pada logika proposisi memiliki salah

satu dari nilai {true, false}

Arti kalimat kompleks yang terdiri atas n variabel

merupakan fungsi dari nilai kebenaran n variabel

tersebut

Perlu tahu nilai kebenaran masing-masing variabel

Perlu aturan untuk menghitung fungsi tersebut

17

MAKNA KALIMAT

Makna dari sebuah kalimat proposisi akan bisa kita

ketahui, jika nilai kebenaran dari simbol proposisi

yang membentuk kalimat tersebut sudah diketahui.

Pemberian nilai kebenaran dari simbol proposisi

tersebut diberikan dalam konteks yang namanya

interpretasi ( I ).

18

INTERPRETASI

Interpretasi pada logika proposisi = pemberian

nilai kebenaran pada semua variabel

Contoh : P Q

I1 : P true dan Q true

I2 : P true dan Q false

I3 : P false dan Q false

I4 : P false dan Q true

lprop: semantik - LFD - 2007 19

ATURAN SEMANTIK kalimat true bernilai true untuk semua interpretasi

kalimat false bernilai false untuk semua interpretasi

kalimat P,Q,R,… bernilai sesuai interpretasinya

not F bernilai true jika F false dan bernilai false jika F true

F G bernilai true jika F dan G keduanya true dan bernilaifalse jika tidak demikian

F G bernilai false jika F dan G keduanya false danbernilai true jika tidak demikian

F G bernilai false jika F true dan G false dan bernilaitrue jika tidak demikian

F G bernilai true jika F dan G memiliki nilai kebenaranyang sama, dan bernilai false jika tidak demikian

TABEL KEBENARAN ATURAN SEMANTIK

lprop: sintaks - LFD - 2007 20

F G F and G F or G If F then G F if and only if G

true true true true true true

true false false true false false

false true false true true false

false false false false true true

TABEL KEBENARAN ATURAN SEMANTIK

21

F G H If F then G else H

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

22

TABEL KEBENARAN

Dengan aturan semantik dapat ditentukan

nilai kebenaran suatu kalimat kompleks untuk

semua interpretasi yang mungkin

Biasanya ditabelkan dan disebut tabel

kebenaran

Jika terdapat n variabel, maka terdapat 2n

baris tabel kebenaran

Contoh formula

4 adalah bilangan positif dan 3 adalah bilangan negatif

p: 4 adalah bilangan positif

q: 3 adalah bilangan negatif

Formula :: p q

Jika bumi adalah datar, maka 2+2 =4

r: bumi datar

s:2+2=4

Formula:: r s

Contoh

Setelah lulus SMU Budi akan melanjutkan sekolah ke Teknik Informatika Unpas atau ke Politeknik Pos.

Pada istirahat siang, peserta seminar dipersilahkan makan atau minum.

Budi memasukkan buku pelajaran ke dalam tas dan berangkat ke sekolah.

Tautology

Suatu formula

disebut Tautology apabila interpretasi dari formula

tersebut selalu benar, apapun nilai

atomnya

p q p q p (p q)

0 0 0 1

0 1 1 1

1 0 1 1

1 1 1 1

Contradiction

Suatu formula disebut

Contradiction apabila interpretasi dari formula

tersebut selalu salah, apapun nilai

atomnya

p q p p q p

0 0 1 0

0 1 1 0

1 0 0 0

1 1 0 0

Logically Equivalent

Dua formula disebut

Logically Equivalent / Ekivalen secara logika apabila

keduanya memiliki nilai kebenaran yang sama

p q

p q p q

p p q

0 0 1 1 1

0 1 1 1 1

1 0 0 0 0

1 1 1 1 1

(p q) ( p q)

Contoh

p q p q p q p q ( p q) (p q)

0 0 1 1 1 1

0 1 0 1 0 0

1 0 0 0 1 0

1 1 1 1 1 1

(p q) (( p q) (p q))