1.
Logika dan Set
Logika didefinisikan sebagai ilmu untuk berpikir dan
menalar dengan benar sehingga didapatkan kesimpulan yang absah.
Tujuan dari
logika: memberikan aturan-aturan penalaran sehingga orang dapat menentukan
apakah suatu kalimat bernilai benar atau salah.
Representasi
Logika dibagi menjadi dua:
·
Propositional
Logic (Logika Proposisi)
Suatu Proposisi merupakan suatu statemen
atau pernyataan yang menyatakan benar (TRUE) atau salah (FALSE).
·
Predicate Logic
(Logika Predikat)
Pada logika predikat proposisi dibedakan
menjadi argumen (obyek) dan predikat (keterangan). Secara umum penulisan
proposisi dalam logika predikat dapat dinyatakan sebagai berikut:
Predikat (argumen-1, argumen-2,...,
argumen-3)
Contoh:
Proposisi: “Bu Atika mencintai Pak Agus
Setiawan”
Dalam logika predikat disajikan dalam bentuk:
Mencintai (Bu Atika, Pak Agus Setiawan)
P
Argumen-1 Argumen-2
Contoh Silsilah Keluarga yang
dipresentasikan dalam Prolog
Jika silsilah di atas dibentuk dalam
Representasi Logika, sebagai berikut:
Orangtua (Komarudin, Andika)
Orangtua (Komarudin, Atika)
Orangtua (Komarudin, Agus)
Orangtua (Andika, Rika)
Orangtua (Atika, Anjar)
2.
Operator Logika
Dalam
Propositional Logic fakta dilambangkan dengan simbol misalnya P, Q dan R.
Lambang-lambang tersebut dihubungkan dengan relasi-relasi logika. Dengan
menggunakan operator logika:
Tabel Kebenaran
Logika
3.
Tautologi, Kontradiksi
dan Contingent
·
Tautologi
Suatu ekspresi logika yang selalu bernilai
benar di dalam tabel kebenarannya, tanpa memedulikan nilai kebenaran dari
proposisi yang berada di dalamnya. Jika tautologi dipakai pada suatu argumen,
berarti argumen harus mempunyai nilai T pada seluruh pasangan pada tabel
kebenaran yang ada membuktikan argumen tadi valid.
Argumen berarti memiliki premis-premis dan
mempunyai kesimpulan.
Jika premis-premis benar, maka kesimpulan
juga harus benar.
Jika Tono pergi kuliah, maka Tini juga
pergi kuliah. Jika Siska tidur, maka Tini pergi kuliah. Dengan demikian, jika
Tono pergi kuliah atau Siska tidur, maka Tini pergi kuliah.Diubah ke variabel
proposisional:
A = Tono pergi kuliah.
B = Tini pergi kuliah.
C = Siska tidur.
Diubah menjadi ekspresi
logika yang terdiri dari premis-premis dan kesimpulan. Ekspresi logika 1 dan 2
adalah premis-premis, sedangkan ekspresi logika 3 adalah kesimpulan.
A->B (premis)
C->B (premis)
(A V C)->B (kesimpulan)
Selanjutnya dapat ditulis sebagai berikut:
((A->B)^(C->B))->((A V C)->B)
Setelah itu membuat tabel kebenaran dari
ekspresi logika tersebut. Jadi, jika tabel kebenaran menunjukkan hasil
tautologi, maka argumen tersebut valid. Dalam logika, tautologi dapat ditulis T
atau 1 saja. Jadi jika A adalah tautologi, maka A = T atau A = 1
Pemanfaatan
Tautologi
Ada beberapa hal penting yang diakibatkan
oleh tautologi, yakni:
a.
Implikasi secara
logis. Misalnya A dan B adalah dua buah ekspresi logika, maka jika dikatakan A
secara logis mengimplementasikan B dapat ditulis dengan A ->B
b.
Ekuivalen secara
logis. Misalnya A dan B adalah dua buah ekspresi logika, maka jika dikatakan A
ekuivalen secara logis dengan B, dapat ditulis dengan: A = B. di sini
disyaratkan A = B, jika dan hanya jika A <-> B adalah tautologi.
·
Kontradiksi
Suatu ekspresi logika
yang selalu bernilai salah di dalam tabel kebenarannya, tanpa memedulikan nilai
kebenaran dari proposisi-proposisi yang berada di dalamnya.
Pada argumen, suatu kontradiksi dapat
dijumpai jika antara premis-premis bernilai T, sedangkan kesimpulan bernilai F.
Hal ini tentunya tidak mungkin terjadi, karena premis-premis yang benar harus
menghasilkan kesimpulan benar.
Dalam bahasa logika konjungsi dari semua
premis-premis dengan negasi dari kesimpulan selalu bernilai F, dan terjadi
kontradiksi. Negasi kesimpulan berarti memberi nilai F pada negasi kesimpulan.
Dalam logika, kontradiksi dapat ditulis F
atau 0 saja. Oleh karena itu, jika A adalah kontradiksi, maka A = F atau A = 0
·
Contingent
Suatu ekspresi logika yang mempunyai nilai
benar dan salah di dalam tabel kebenarannya, tanpa memedulikan nilai kebenaran
dari proposisi-proposisi yang berada di dalamnya.
·
Ekuivalen Logis
Proposisi A dan B disebut ekuivalen secara
logis jika A ekuivalen B adalah tautologi. Notasi atau simbol A ekuivalen B
menandakan bahwa A dan B adalah ekuivalen secara logis. Proposisi dapat diganti
dengan ekspresi logika berupa proposisi majemuk.
Pada tautologi dan juga
kontradiksi dapat dipastikan bahwa jika dua buah ekspresi logika adalah
tautologi, maka kedua buah ekspresi logika tersebut ekuivalen secara logis,
demikian juga jika keduanya kontradiksi.
Pada contingent, jika urutan T dan F atau
sebaliknya pada tabel kebenaran tetap pada urutan yang sama, maka tetap disebut
ekuivalen secara logis.
4.
Resolusi Logika
Proposisi
Sebelum resolusi
dapat diterapkan, wff harus diletakkan dalam bentuk casual
Contoh :
Some programmers
hate all failures
No programmer
hates any success
\ No failure is a
success
P(x) = x is a
progammer
F(x) = x is a
failure
S(x) = x is a
success
H(x,y) = x hates y
Premise dan
kesimpulannya
(1) ($x) [P(x) Ù ("y) (F(y) à H(x,y))]
(2) ("x) (P(x) à ("y) (S(y) à
~H(x,y))]
(3) ~("y) (F(y) à ~S(,y))
Konversi ke bentuk
clausal :
·
Hilangkan
kondisional, (p à q) º ~p v q
·
Geser negasi ke
dalam (reduksi skope ~). Negasi digeser hanya berlaku untuk atomik formula
·
Hilangkan
quantifier eksistensial
-
Jika $ tidak ada
dalam skope ", ganti variabel dengan suatu konstanta baru ($x) P(x)
diganti P(a)
-
Jika $ berada
dalam skope ", ganti variabel dengan suatu fungsi yang memiliki argumen
semua variabel dari " tersebut
"x ,"y , $z P(x,y,z)
diganti menjadi "x,"y, P(x,y,F(x,y))
·
Standarisasi
variabel (jika perlu) sehingga tiap quantifier memiliki variabel yang berbeda
·
Geser semua "
ke kiri (karena semua quantifier punya nama yang berbeda, pergeseran tidak
mempengaruhi hasil) Bentuk ini disebut prenex normal form terdiri atas prefix
quantifier yang diikuti matriks.Hilangkan "." tidak perlu ditulis,
diasumsikan semua variabel terkuantifikasi universa.l Geser disjungsi (V)
kedalam, sehingga terbentuk conjungsi normal formBuang konjungsi dan uraikan
menjadi klausa-klausa
·
Standarisasi
variabel (jika perlu) sehingga tidak ada variabel yang muncul pada lebih dari 1
klausa.
Lakukan
langkah-langkah resolusi pada CNF (BP Ù Øα), α adalah pernyataan yang harus
dibuktikan Resolusi adalah teknik untuk membuktikan sebuah pernyataan pada
logika proposional atau kalkulus predikat. Refutasi=resolusi, membuktikan
teorema dengan menegasikan pernyataan yang harus dibuktikan dan menambahkannya
ke kumpulan aksioma yang diketahui benar, Semua aksioma dalam bentuk normal
yaitu sebuah kalimat atau disjungsi beberapa kalimat, pernyataan terbukti benar
jika refutasi menghasilkan kalimat kosong
Sumber :
0 komentar:
Posting Komentar