PROPOSITIONAL LOGIC

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

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:

P or Q

if    And

if Q then R

then (if (P and Q)

then not R)

Notasi konvensional:

Notasi	Notasi Konvensional
not	~
and	∧
or	V
if-then	Æ
if-and-only-if	↔
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	P∧Q
True	True	True
True	False	False
False	True	False
False	False	False

3.    Disjunction Rule (Aturan OR)

P	Q	P∨Q
True	True	True
True	False	True
False	True	True
False	False	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

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 ~P	=	True
PΛ ~ P	=	False
~(~ 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	Q	P Æ Q
True	True	True
True	False	False
False	True	True
False	False	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

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

Jika p bernilai benar maka q berlaku, Jika p bernilai salah maka r berlaku

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)