LOGIKA PROPOSISIONAL

LOGIKA PROPOSISIONAL
Banyak pernyataan (statement) yang bisa langsung diterima kebenarannnya, seperti misalnya pernyataan “Ada kehidupan di Bulan atau tida ada kehidupan di Bulan” pernyaataan di ataas benar, meskipun kita tidak tahu apakah ada orang yang tidak pernah membuktikan atau tidak Kebenaran suatu pernyataan bida ditentukan dari strukturnya saja, tanpa harus tahu kebenaran pembentuk-pembentuknya (constituents). Secara serupa, kita juga bisa mengatakan bahwa pernyataan

“Indonesia mempunyai jumlah penduduk lebih besar dari Cina atau Indonesia mempunyai jumlah penduduk lebih kecil atau sama dengan Cina”

pernyataan di atas adalah benar tanpa harus melakukan penghitungan jumlah penduduk masing-masing negara.

Ternyata kedua pernyataan di atas merupakan contoh-contoh (instances) dari kalimat-kalimat abstrak

P or (not P)

Dengan membuktikan kalimat abstrak, kita dapat menyimpulkan kebenaran-kebenaran dari semua (takberhingga banyak) contoh-contoh konkritnya sebagai berikut:
not ( P and (not P) ) or Q

valid, maka kita bisa dengan cepat menyimpulkan bahwa kalimat-kalimat konkrit seperti
not ( [x-0] and (not[x < 0]) ) or (y >= 0)
1.2 Bahasa

Logika proposisi terdiri dari kalimat-kalimat (sentense), khususnya kalimat abstrak (abstract sentence).

Definisi (proposisi)
Kalimat-kalimat dalam bahasa logika proposisional dibentuk dari simbol-simbol, yang disebut proposisi (propositions), dikelompokkan menjadi dua, yaitu:
• Simbol-simbol kebenaran (trurt symbol) true dan false
• Simbol-simbol proposisional (propositional symbol) P, Q, R, S, P1, Q1, R1, S1, P2, Q2, R2, S2……(huruf-huruf besar P, Q, R, S, dan mungkin dengan indek-indek numerik)

Definisi kalimat (sentence)
Kalimat-kalimat dalam logika proposisional dibangun dari proposisi dengan menerapkan proposisional connections:

not, and, or, if-then, if-and-only-if, if-then-else

kalimat dibentuk menurut aturan-aturan (rules) berikut:

• setiap proposisi, yaitu suatu simbol kebenaran atau suatu simbol proposisi merupakan kalimat.
• Apabila F kalimat, maka demikian juga negasi (negation)nya (not F).
• Apabila F dan G kalimat, maka demikian juga konjungsinya, yaitu (F dan G), selanjutnya F maupun G disebut conjucnts dari (F or G).
• Apabila F dan G kalimat, maka demikian juga disjungsi (disjunction) nya, yaitu (F or G), selanjutnya F maupun G disebut disjuncts dari (F or G)
• Apabila F dan G kalimat, maka demikian juga implikasi (implication) nya, yaitu (if F then G). Selanjutnya F disebut antecedent dan G disebut consequent dari (if F then G). Kalimat (if G then F) disebut converse dari kalimat (if F then G).
• Apabila F dan G kalimat, maka demikian juga ekuivalensi (equivalence) nya, yaitu (F if and only, selanjutnya F disebut sisi-kiri (left-hand side) dan G disebut sisi-kanan (right hand side) dari (F if and only if G).
• Apabila F, G dan H kalimat, maka demikian juga kondisional (conditional) nya, yaitu (if F then G else H), Selanjutnya F, G, dan H masing-masing disebut klausa-if (if-clause), klausa-then (then-clause), dan klausa-else (else-clause) dari kondisional (if F then G else H).

Contoh :
Ekpresi berikut:
E : ((not (P or Q)) if and only if ((not P) and (not Q)))

Merupakan kalimat karena
P dan Q
keduanya merupakan kalimat, jadi
(P or Q), (not P), dan (not Q)
merupakan kalimat, sehingga
(not (P or Q) ) and ((not P) and (not Q))
merupakan kalimat, jadi ekpresi E,
((not (P or Q)) if and only if ((not P) and (not Q))),
merupakan kalimat


Notasi

Pasangan-pasangan kurung dalam kalimat bisa dihilangkan apabila tidak diperlukan untuk menunjukkan struktur kalimat.
Sebagai contoh, kalimat

(not (P and (not Q)))

dapat ditulis sebagai not (P and not Q), tanpa adanya ambguitas (ambiguity). Untuk lebih jelas digunakan kurung [], {} dari beberpaa pasangan kurung ().
Sehingga kalimat E dari contoh di atas bisa ditulis sebagai berikut:

not (p or q)
if and only if
(not p) and (not q)

kalimat :
F: (if ((P or Q) and (if Q then R)) then (if (P and Q) then (not R)))
dapat ditulis sebagai


Notasi Konvensional
and
or
not
if – then
if-and-only-if
if-then-else  atau &

~ atau 
 atau 
 atau 
tidak ada

Sebagai contoh E :


sementara F dapat ditulis sebagai
((P  Q)  (Q  R))  ((P  R)  (~R)))


1.3 Arti Suatu Kalimat

Apakah nilai kebenaran suatu kalimat (P or (not Q)) adalah true dan fals? Apakah nilai kebenaran dari simbol-simbol proposional P dan Q itu sendiri true atau false?

Interpretasi
Merupakan suatu pemberian (assignment) suatu nilai kebenaran, true atau false, ke masing-masing himpunan simbol-simbol proposional: interpretasi kosong (emty interpretation) tidak memberikan nilai kebenaran ke suatu simbol proposisional manapun.

Sebagai contoh, proposisi dari F:

F : P or (not Q)
Salah satu interpretasi I1 untuk F memberi nilai false ke P dan nilai true ke



interpretasi lain I2 untuk F adalah :

dapat dikatakan bahwa P bernilai false dan Q bernilai true di bawah (under) I1 dan P bernilai false dan Q bernilai false under I2.

Suatu interpretasi suatu kalimat bisa memberi nilai-nilai kebenaran ke beberapa simbol yang tidak muncul dalam kalimat, selama setiap simbol proposisional yang muncul diberi suatu nilai.

Sebagai contoh, interpretasi



1.4 Pohon Semantik
Metode lain untuk pengujian validitas suatu kalimat adalah semantic tree technique, yang seringkali lebih efesien dibanding dengan metode trufttable.

Contoh dengan node 2:

G : if (if P then Q) then (if (not P) then (not Q))

Dua kemungkinan nilai-nilai kebenaran untuk P, yang mewakili dalam bentuk tree :









Node 2 : if (if P then Q) then (if (not P) then (not Q))
  T T

Node 2 : if (if P then Q) then (if (not P) then (not Q))
  T F T
Sehingga diperoleh:

Node 2 : if (if P then Q) then (if (not P) then (not Q))
  T T F T
Karena consequent (if (not P) then (not Q)) true, maka keseluruhan kalimat G bernilai true, yaitu :

Node 2 : if (if P then Q) then (if (not P) then (not Q))
  T T T F T

Dari hasil analisis contoh di atas sehingga dapat dirangkum dalam bentuk tree sebagai berikut:









Contoh menggunakan node 3:

Node 3 : if (if P then Q) then (if (not P) then (not Q))
  F F

Karena P bernilai false, jadi kalimat-kalimat bagian (if P then Q) dan keduanya bernilai true (masing-masing dengan aturan if-then dan not)

Node 3 : if (if P then Q) then (if (not P) then (not Q))
  T F T F










Pengecekan valliditas dengan semantic tree

Contoh :

H : if Q then (if P then Q)

Sentence di atas adalah valid, dua kemungkinan nilai kebenaran untuk Q, dapat diwakili dalam bentuk tree sebagai berikut:









Q bernilai true pada node 2, yaitu dengan memberi tanda masing-masing pemunculan dari Q dalam kalimat H dengan huruf T:

Node 2 : if Q then (if P then Q)
  T T

Karena Q bernilai true, maka consequent (if P then Q) bernilai true, selanjutnya keseluruhan kalimat bernilai true.

Hasil dari contoh di atas dapat dirangkum pada simantic tree:









Analisis bersesuaian dengan node 3 dimana Q bernilai false

Node 3 : if Q then (if P then Q)
  F F






Karena kalimat H yaitu Q bernilai false, maka keseluruhan kalimat bernilai true, maka dapat diperoleh simantic tree sebagai berikut: