Logika Makalah
-
Upload
edwinginanjar -
Category
Documents
-
view
170 -
download
0
Transcript of Logika Makalah
Logika Proposisi
Makalah
Disusun Oleh
Henry Aulia Rahman (140810130005)
Rezky Pratomo (140810130013)
Edwin Ginanjar Sonjaya (140810130014)
Selano Putra (140810130018)
Alvin Niza Aulia (140810130047)
Program Studi Teknik Informatika
Jurusan Matematika
Fakultas Matematika dan Ilmu Pengetahuan Alam
Universitas Padjadjaran
2013
1
KATA PENGANTAR
Puji Syukur ke hadirat Allah SWT, yang melimpahkan rahmat dan hidayah-Nya,
sehingga penulis dapat menyelesaikan makalah dengan judul “Logika Proposisi”. Makalah ini
disusun untuk memenuhi tugas mata kuliah Logika Informatika.
Penulis mengucapkan terima kasih kepada semua pihak yang telah memberikan
dukungan, semangat, dan informasi, serta pertolongan baik moral maupun material. Sehingga
karya tulis ini dapat diselesaikan dan dapat diterima dengan baik.
Penulis berupaya menyusun karya tulis ini agar menarik untuk dibaca dan dipahami, serta
untuk mencoba mengkaji lebih dalam tentang Logika Proposisi dan manfaat-manfaat yang dapat
diambil.
Akhir kata, penulis mengharapkan sumbangan kritik dan saran untuk kesempurnaan
dalam penulisan karya tulis selanjutnya. Semoga bermanfaat.
Jatinangor, 18 Oktober 2013
Penulis
2
DAFTAR ISI
KATA PENGANTAR
DAFTAR ISI
BAB I PENDAHULUAN
1.1 Latar Belakang ………………………………………………………………………………. 4
1.2 Rumusan Masalah ……………………………………………………………………………… 4
1.3 Tujuan Penulisan………………………………………………………………………………… 4
1.4 Manfaat Penulisan ……………………………………………………………………………… 5
BAB II PEMBAHASAN
2.1 Logika Proposisi ……………………………………………………………………………… 6
2.2 Natural Deduction ……………………………………………………………………………… 8
2.3 Logika proporsional sebagai bahasa resmi ………………….………………………. 12
2.4 Semantik Logika Proposisi…….……………………………………………………………13
2.5 Normal Form ……………………………………………………………………………… 18
2.6 Sejarah Ilmu Logika ……………………………………………………………………… 20
BAB III PENUTUP
3.1 Kesimpulan……………….…………………………………………………………………….... 22
DAFTAR PUSTAKA………………………………………………………………………………… 23
3
BAB I
PENDAHULUAN
1. Latar Belakang
Logika berasal dari bahasa Yunani logos yang berarti Ilmu untuk berfikir dan menalar
dengan benar. Dan manusia mampu mengembangkan pengetahuan karena mempunyai bahasa
dan kemampuan menalar. Sedangkan Informatika berarti disiplin ilmu yang mempelajari
transformasi fakta berlambang yaitu data maupun informasi pada mesin berbasis komputasi.
Sehingga dapat diartikan bahwa Logika Informatika adalah disiplin ilmu yang mempelajari
transformasi fakta berlambang yaitu data maupun informasi pada mesin berbasis komputasi
dengan penalaran sehingga didapat suatu kesimpulan. Karena Logika Informatika sangat berguna
bagi kehidupan manusia yang khususnya di bidang teknologi maka kami berusaha memaparkan
Logika Proposisi dalam makalah kami.
2. Rumusan Masalah
a) Apa itu kalimat deklaratif ?
b) Apa yang dimaksud dengan natural deduction ?
c) Apa yang dimaksud logika proposi sebagai bahasa resmi?
d) Apa itu sematik logika proposisi ?
e) Bagaimana bentuk formal dari logika proposisi ?
f) Bagaimana normal forms dari kalimat logika ?
3. Tujuan Penulisan
a) Memenuhi tugas mata kuliah logika informatika.
b) Mengetahui apa itu logika proposisi. 4
4. Manfaat Penulisan
Dengan makalah ini, diharapkan penulis dan pembaca lebih memahami dan mengerti tentang
Logika Proposisi.
5
BAB II
PEMBAHASAN
1. Logika Proposisi
Tujuan dari logika dalam ilmu komputer adalah untuk mengembangkan bahasa untuk
model situasi yang kita hadapi sebagai profesional ilmu komputer , sehingga kita dapat
mengetahuinya secara mudah . Penalaran tentang situasi berarti membangun argumen tentang
mereka , kami ingin melakukan ini secara formal , sehingga argumen adalah valid dan dapat
dipertahankan ketat , atau dijalankan pada mesin.
Contoh 1 :
Jika kereta tiba terlambat, dan tidak ada taksi di stasiun, maka John terlambat untuk pertemuan.
John tidak terlambat untuk pertemuan. Kereta tidak datang terlambat. Oleh karena itu, ada taksi
di stasiun.
Secara intuitif , argumen tersebut valid , karena jika kita menempatkan kalimat pertama dan
kalimat ketiga bersama-sama , mereka memberitahu kami bahwa jika tidak ada taksi , maka John
akan terlambat. Kalimat kedua memberitahu kami bahwa ia tidak terlambat , sehingga harus
kasus yang ada taksi .
Contoh 2 :
Jika hujan, dan Jane tidak membawa payung, maka dia akan kebasahan. Jane tidak basah. Hari
hujan. Oleh karena itu , Jane membawa payung.
Ini juga merupakan argumen yang valid . Pemeriksaan lebih dekat mengungkapkan bahwa
sebenarnya memiliki struktur yang sama sebagai argumen dari contoh sebelumnya.
6
1. Kalimat Deklaratif
Dalam rangka untuk membuat argumen yang valid, kita perlu mengembangkan bahasa yang
kita dapat mengungkapkan kalimat sedemikian rupa yang membawa keluar struktur logis
mereka. Bahasa yang kita mulai dengan adalah bahasa logika proporsional . Hal ini didasarkan
pada proposisi , atau kalimat deklaratif yang satu dapat , pada prinsipnya , berdebat
sebagai benar atau salah .
Contoh kalimat deklaratif adalah:
( 1 ) Jumlah angka 3 dan 5 sama dengan 8 .
( 2 ) Jane bereaksi keras tuduhan Jack .
( 3 ) Setiap bahkan bilangan Real > 2 adalah jumlah dari dua bilangan prima .
( 4 ) Semua Mars seperti pepperoni di pizza mereka .
Kalimat ini semua deklaratif , karena mereka pada prinsipnya mampu dinyatakan 'benar' , atau
'salah' .
Logika yang memproses penarikan kesimpulan secara logis (logical derivation) dari
proposisi-proposisi.
Proposisi yang tidak dapat dibagi lagi disebut proposisi atomic,dan jika dirangkai dengan
beberaa proposisi lain akan menjadi proposisi majemuk.proposisi atomic dapat dijumai dalam
satu kata.tidak semua data dapat dijadikan proposisi,tetapi pernyataan yang tidak lengkap dapat
dijadikan lengkap dan dapat dianggap sebagai proposisi.
Sebagai contoh kami memberikan simbol yang berbeda tertentu p , q , r , . . . , Atau kadang-
kadang p1 , p2 , p3 , . . . untuk masing-masing kalimat tersebut atom dan kita kemudian dapat
kode lebih kompleks
7
kalimat dengan cara komposisi . Sebagai contoh, mengingat kalimat atom :
p : "Saya memenangkan lotre minggu lalu . "
q : "Saya membeli tiket lotre . "
r : "Aku memenangkan undian minggu lalu . "
2. Natural Deduction
Merupakan pengambilan kesimpulan secara valid melalui evaluasi dari beberapa argumen.
Argumen dinyatakan deduktif jika kebenaran dari kesimpulan ditarik atau merupakan
konsekuensi logis dari premis-premisnya.
Dengan menerapkan aturan bukti ke lokasi , kami berharap
untuk mendapatkan lebih banyak formula , dan dengan menerapkan aturan bukti lebih kepada
mereka , untuk
akhirnya memperoleh kesimpulan . Niat ini kita dilambangkan dengan
φ1 , φ2 , . . . , Φn |- ψ .
Ungkapan ini disebut berturut-turut , itu sah jika bukti untuk itu dapat ditemukan .
The sekuen untuk Contoh 1.1 dan 1.2 adalah p ∧ ¬ q → r ¬ r , p ? q . membangun
bukti tersebut adalah latihan kreatif, sedikit seperti pemrograman . Hal ini tidak
tentu jelas yang mengatur untuk menerapkan , dan dalam rangka apa , untuk mendapatkan
diinginkan kesimpulan . Selain itu , aturan bukti kita harus hati-hati dipilih ;
jika tidak, kita mungkin bisa ' membuktikan ' pola valid argumentasi .
Hal ini dalam logika tradisional menggunakan huruf Yunani . Huruf kecil digunakan untuk
berdiri untuk formula dan huruf besar digunakan untuk set formula . Berikut adalah beberapa
yang lebih umum digunakan Huruf Yunani , bersama dengan ucapan mereka.
8
Huruf Kecil
φ phi
ψ psi
χ chi
η eta
α alpha
beta β
γ gamma
Huruf Besar
Φ Phi
Ψ Psi
Γ Gamma
Δ Delta
Menguji apakah proposisi adalah tautologi dengan menguji setiap tugas kebenaran yang
mungkin mahal-ada banyak eksponensial. Kita perlu sebuah sistem deduktif, yang akan
memungkinkan kita untuk membangun bukti dari tautologi dalam langkah-demi-langkah mode.
Sistem akan kita gunakan dikenal sebagai pengurang alami. Sistem ini terdiri dari
seperangkat aturan inferensi untuk menurunkan konsekuensi dari lokal. Satu membangun pohon
bukti yang akar adalah proposisi harus dibuktikan dan yang daunnya asumsi awal atau aksioma
(untuk pohon bukti, kita biasanya menarik akar di bagian bawah dan daun di bagian atas).
Sebagai contoh, salah satu aturan sistem kami dikenal sebagai ponens modus. Secara
intuitif, ini mengatakan bahwa jika kita tahu P adalah benar, dan kita tahu bahwa P menyiratkan
Q, maka kita dapat menyimpulkan T.
Cara melakukan validitas dengan menggunakan Natural Deduction
Contoh :
Jika durian ini manis, maka durian ini enak di makan
Jika durian ini enak di makan, maka saya akan memakannya
Dengan demikian, jika durian ini enak dimakan, maka saya akan memakannya.
9
Argumen tersebut pasti valid
Langkah – langkahnya
1. Tentukan variasi proposisinya
a. Durian ini manis
b. Durian ini enak dimakan
c. Saya akan memakannya
2. Buat bentuk logika masing –masing pertanyaan.
1. A B
2. B C
3. C C
3. Susun dalam bentuk ekspresi logika :
(( A B) A ( B C) A C)
Dengan demikian dapat ditulis seperti berikut
( A B), (B C)}≠ (A C)
2.1. Aturan – aturan Natural Deduction
Dengan A,B,C sebagai variabel proporsional.
Aturan (1) : ∧ I (∧-introduksi)
10
A BA∧B
Aturan di atas mudah sekali dipahami.
Jika A dan B, maka dapat disimpulkan A ∧ B.
Contoh:
“Bedu kelaparan” dan “Bedu kehausan”, maka kesimpulannya “Bedu kelapaan dan
kehausan”.
Aturan (2) : ∧ E (∧-eliminasi)
A∧B
A
Aturan (3) : ∧ E (∧-eliminasi)
A∧BB
Aturan (2) dan (3) dinamakan aturan ∧-eliminasi atau disingkat ∧E
Contoh:
“Bowo mahasiswa yang rajin dan pandai”, maka dapat disimpulkan
“Bowo mahasiswa yang pandai” atau “Bowo mahasiswa yang rajin
Aturan (4) : ∨ I (∨-introduksi)
AA∨B
Aturan (5) : ∨ I (∨-introduksi)
BA∨B
11
Dari pernyataan “Dewi Mahasiswa yang pandai” dapat disimpulkan bahwa
“Dewi mahasiswa yang pandai atau sangat cantik”.
Aturan (6) : ∨ E (∧-eliminasi)
Aturan (7) : I ( introduksi)
Aturan (8): → E (→ eliminasi)
Aturan (9): Id (Identitas)
2.2. Contoh dari Natural Deduction
3. Premis 1 : Semua manusia pasti mati
4. Premis 2 : Socrates adalah manusia
5. Kesimpulan : Socrates pasti mati
"Socrates pasti mati" adalah kesimpulan atau konsekuensi dari dua premis sebelumnya. Jika
premis 1 dan premis 2 benar, maka kesimpulannya juga benar.
3. Logika proporsional sebagai bahasa resmi
Dalam logika proporsional haruslah sama dalam peng aplikasian tulisannya.
Pengaplikasiannya yaitu
1. P -> premise
2. P premise
3. q ->e 1,2
Sama berlaku jika kita mengganti p dengan p ∨ ¬ r dan q dengan r → p
12
1. p V ¬ r-> (r -> p) premise
2. p V ¬ r premise
3. r -> p ->e 1,2
Secara umum, kita membutuhkan pasokan tak terbatas atom proposisional yaitu p , q , r , ... atau
p1 , p2 , p3 , ... Agar sama
4. Semantik Logika Proposisi
4.1. Arti dari Operator Logika
Dalam logika, dua kalimat dapat digabungkan dengan operator logika untuk
membentuk kalimat gabungan. Nilai kebenaran kalimat gabungan ini ditentukan oleh
nilai kebenaran kalimat-kalimat pembentuknya. Operator logika di sini bertindak sebagai
fungsi.
a). Negasi
Tabel kebenaran untuk TIDAK p (juga ditulis ¬p, Np, Fpq, or ~p) adalah dibawah ini:
Logika negasi
P ¬p
S B
13
B S
b). Konjungsi
Tabel kebenaran untuk p DAN q (juga ditulis p ∧ q, Kpq, p & q, atau p q) adalah dibawah ini:
Logika konjungsi
P q p ∧ q
B B B
B S S
S B S
S S S
c). Disjungsi Inklusif
Tabel kebenaran untuk p ATAU q (juga ditulis p ∨ q, Apq, p || q, or p + q) adalah dibawah ini:
14
d) Biimplikasi
Tabel kebenaran untuk p XNOR q (juga ditulis p ↔ q, Epq, p = q, or p ≡ q) adalah dibawah
ini:
Logika kesamaan
15
Logika Disjungsi
P q p ∨ q
B B B
B S B
S B B
S S S
P q p ≡ q
B B B
B S S
S B S
S S B
e). Disjungsi Eksklusif
Tabel kebenaran untuk p XOR q (juga ditulis p ⊕ q, Jpq, or p ≠ q) adalah dibawah ini:
Disjungsi eksklusif
P q p ⊕ q
B B S
B S B
S B B
S S S
16
f). Implikasi
Tabel kebenaranuntuk p implies q (dapatditulisdengan p ⇒ q atau
Cpq)adalahdibawahini
Logical Implication
p q p → q
T T T
T F F
F T T
F F T
Jumlah kemungkinan hasil adalah , dimana n adalah jumlah pernyataan dasar yang ada (p, q,
r, dsb). Namun, p dan ~p (negasi p) tidak dihitung sebagai pernyataan yang berbeda.
4.2. Induksi Matematika
Induksi Matematika adalah cara standar dalam membuktikan bahwa sebuah pernyataan
tertentu berlaku untuk setiap bilangan asli. Pembuktian dengan cara ini terdiri dari dua langkah,
yaitu:
17
1. Menunjukkan bahwa pernyataan itu berlaku untuk bilangan 1.
2. Menunjukkan bahwa jika pernyataan itu berlaku untuk bilangan n, maka pernyataan itu
juga berlaku untuk bilangan n + 1.
Misalkan akan dibuktikan suatu pernyataan bahwa jumlah n bilangan asli pertama, yaitu 1+2+...
+n, adalah sama dengan n(n+1) 2
4.3. Keabsahan dari Logika Proporsional
Dalam logika informatika, sistem logika memiliki properti keabsahan jika dan hanya jika aturan
inferensi membuktikan formula yang valid berhubungan dengan semantik. Dalam kebanyakan
kasus, terdapat aturan bahwa properti yang ada harus benar, tapi ini tidak terjadi pada umumnya.
Sebuah argumen dinyatakan absah jika dan hanya jika
1. Argumennya valid.
2. Semua premis benar.
Contoh :
Semua manusia akan mati.
Socrates adalah manusia.
Jadi, Socrates akan mati.
Argumen tersebut valid (karena kesimpulannya benar berdasarkan premis, jadi kesimpulannya
mengikuti premis) dan karena premisnya berdasarkan fakta yang benar maka argumen absah.
Argumen di bawah ini valid tetapi tidak absah
Semua organisme yang punya sayap bisa terbang.
Penguin punya sayap.
18
Jadi, penguin bisa terbang.
Karena premis pertama sudah salah, walaupun argumennya valid, tetapi tidak absah.
4.4. Kelengkapan dari logika proporsional
Dalam logika , kelengkapan semantik adalah kebalikan dari keabsahan untuk sistem formal.
Sebuah sistem formal "kelengkapan semantik " ketika semua tautologi nya adalah teorema ,
sedangkan sistem formal " absah" ketika semua teorema adalah tautologi ( yaitu, mereka secara
semantik berupa formula yang valid : formula yang benar di bawah setiap penafsiran bahasa
sistem yang konsisten dengan aturan sistem ) .
5. Normal Forms
• Dua formula p dan q dikatakan setara jika memiliki makna yang sama sebagai contoh,
• p → q dan ¬ p → ¬ q memiliki tabel kebenaran yang sama , semua empat kombinasi
T(True) dan F(False) untuk p dan q memiliki hasil yang sama dengan menggunakan
tabel kebenaran .
• Contoh :
1. p → q ≡ ¬ q → ¬ p
2. p → q ≡ ¬ p ∨ q
3. p ∧ q → p ≡ r ∨ ¬ r
4. p ∧ q → r ≡ p → (q → r).
Contoh pembuktian No 1
P Q ¬ p ¬ q p→q ¬ q→ ¬ p
T T F F T T
T F F T F F
19
F T T F T T
F F T T T T
5.1 Conjunctive Normal Forms
Merupakan konjungsi dari satu atau lebih pernyataan (klausa)
A1 ˄ A2 …….. ˄Ai ………. ˄ An
Contoh
• p ˅ ¬q
• (¬p ˅ q) ˄ (r ˅ ¬t ˅ ¬p)
Semua kalimat dalam logika proporsional dapat ditulis dalam CNF dengan menggunakan tabel
kebenaran
Contoh :
Ubahlah formula ini kedalam bentuk cnf kedalam bentuk CNF
~ (a → b) v (a v b)
Jawab :
20
5.3. Horn Clause
• Program logika mengekspresikan solusi dari suatu persoalan menggunakan ekspresi
berbentuk logika matematika. Dengan demikian, logika predikat dan logika proposional
merupakan landasan formal untuk pemrograman logika.
• Horn clause adalah bentuk khusus dari logika predikat yang digunakan sebagai sintaks
bahasa Prolog.
• Horn clause mempunyai head h yang disebut sebagai predikat, dan body yang disebut
sebagai daftar
dari predikat p1, p2 ,... , pn.
• Horn clause ditulis dalam bentuk sebagai berikut:
h ← p1, p2, ..., pn
• Yang artinya bahwa h benar hanya jika p1, p2, .., pn secara simultan benar. Sebagai
contoh, kita ingin menangkap ide bahwa akan turun salju di suatu kota C hanya jika
terjadi hujan di kota C, dan temperatur di kota C adalah sangat dingin atau beku. Ide ini
dapat dituliskan dalam bentuk Horn clause sebagai berikut:
salju(C) ← hujan(C), beku(C)
• Notasi tersebut dapat juga dituliskan sebagai
hujan(C) ^ beku(C) ↄ salju(C)
21
6. Sejarah Ilmu Logika
Secara umum, sejarah logika dimulai sejak Thales (624 SM - 548 SM), filsuf Yunani
pertama yang meninggalkan segala dongeng, takhayul, dan cerita-cerita isapan jempol dan
berpaling kepada akal budi untuk memecahkan rahasia alam semesta.
Thales mengatakan bahwa air adalah arkhe (Yunani) yang berarti prinsip atau asas utama alam
semesta. Saat itu Thales telah mengenalkan logika induktif.
Baru Pada tahun 1840, logika bolean pertama kali diperkenalkan oleh seorang ahli matematika
bernama george Boolean, kemudian dikembangkan pada tahun 1854 dalam bukunya Sebuah
Investigasi Hukum Pemikiran. Dialah yang pertama kali mendefinisikan istilah itu sebagai
bagian dari sistem logika matematika. Aljabar Boolean disempurnakan di akhir abad 19 oleh
Jevons, Schröder, Huntington,. dan lain-lain sampai mencapai konsepsi modern struktur
(abstrak) matematika. Dalam perkembanganya Boolean logic telah dianggap sebagai dasar
kompoter modern dan perkembangan teknologi saat ini.
Boolean adalah suatu tipe data yang hanya mempunyai dua nilai. Yaitu true atau false (benar
atau salah).
Sementara itu, Natural deduction pertama kali dikemukakan oleh Gerhard Gentzen
(November 24, 1909 - 4 Agustus 1945), dia adalah seorang matematikawan Jerman dan ahli
logika . Dia membuat kontribusi besar untuk dasar matematika , teori bukti , terutama pada
natural deductionnya dan kalkulus berturut-turut .
BAB III
KESIMPULAN
22
Kesimpulan
Logika merupakan ilmu yang sangat penting untuk dipelajari, karena merupakan ilmu
dasar bagi ilmu-ilmu yang lain. Hal ini dapat dilihat dari beberapa contoh yang dipaparkan di
atas. Selain itu, logika juga merupakan ilmu untuk berpikir secara sistematis, sehingga mudah
dipahami dan dapat dirunut kebenarannya.
Logika juga sangat banyak digunakan pada dunia pemrograman, karena hampir setiap
bahasa pemrograman menggunakan logika dalam pemecahan permasalahan dan setiap decision-
nya. Oleh karena itu, sangat penting kiranya untuk mempelajari logika.
23
DAFTAR PUSTAKA
http://id.wikipedia.org/wiki/Operator_logika
http://pakarjava.wordpress.com/2012/05/25/operator-logika/
http://oliverjordan.web.ugm.ac.id/
http://phonks.blogspot.com/2013/05/logika-proporsional.html
24