Logika Makalah

29
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 1

Transcript of Logika Makalah

Page 1: 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

Page 2: Logika Makalah

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

Page 3: Logika Makalah

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

Page 4: Logika Makalah

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

Page 5: Logika Makalah

4. Manfaat Penulisan

Dengan makalah ini, diharapkan penulis dan pembaca lebih memahami dan mengerti tentang

Logika Proposisi.

5

Page 6: Logika Makalah

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

Page 7: Logika Makalah

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

Page 8: Logika Makalah

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

Page 9: Logika Makalah

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

Page 10: Logika Makalah

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

Page 11: Logika Makalah

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

Page 12: Logika Makalah

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

Page 13: Logika Makalah

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

Page 14: Logika Makalah

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

Page 15: Logika Makalah

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

Page 16: Logika Makalah

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

Page 17: Logika Makalah

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

Page 18: Logika Makalah

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

Page 19: Logika Makalah

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

Page 20: Logika Makalah

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

Page 21: Logika Makalah

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

Page 22: Logika Makalah

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

Page 23: Logika Makalah

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

Page 24: Logika Makalah

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