Senin, 04 April 2011

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
PQ
True
True
True
True
False
False
False
True
False
False
False
False




3.    Disjunction Rule (Aturan OR)






P
Q
PQ
True
True
True
True
False
True
False
True
True
False
False
False








Sifat-sifat aljabar logika untuk konjungsi dan disjungsi
a.    Hukum Idempoten
PP    = 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)

Tidak ada komentar:

Posting Komentar