Logika

Berasal dari bahasa latin Logos yang berarti perkataan. Dikembangkan oleh filusuf Yunani, Aristoteles, sekitar 2300 tahun yang lalu. Logika merupakan studi penalaran yaitu cara berpikir dengan mengembangkan sesuatu berdasarkan akal budi dan bukan dengan perasaan atau pengalaman. Pelajaran logika difokuskan hubungan antara pernyataan-pernyataan (statement).Contoh : Semua pengendara sepeda motor memakai helm Setiap orang yang memakai helm adalah mahasiswa Jadi, semua pengendara motor adalah mahasiswa

Manfaat Ilmu Logika dalam komputer :

a. Membantu dalam bidang pemrograman.b. Analisis kebenaran algoritmac. Kecerdasan buatan, dllProposisi kalimat deklaratif yang bernilai benar (true) atau salah (false), tetapi tidak dapat sekaligus keduanya. Bidang logika yang membahas proposisi disebut Kalkulus Proposisi. Kebenaran atau kesalahan dari sebuah kalimat disebut nilai kebenaran (Truth Value).Secara simbolik, proposisi dilambangkan dengan huruf kecil, seperti : p, q, r.

Contoh penulisan proposisi : p : 6 adalah bilangan genap

q : 1 + 2 = 12

Contoh soal proposisi atau bukan proposisi :a. Soekarno adalah Presiden Indonesia yang pertama. (Kalimat Proposisi)

b. Kemarin hari hujan. (Kalimat bukan proposisi)Kombinasi Proposisia. Dibahas oleh Matematikawan Inggris, George Boole, Tahun 1854, Buku The Law of Thought.b. Operator yang digunakan untuk mengkombinasikan proposis disebut Operator Logika.c. Operator Logika dasar yang digunakan :AND / DAN

OR / ATAUNOT / TIDAK ( Operator Uner karena membutuhkan satu buah proposisi Proposisi baru diperoleh dari proses kombinasi proposisi disebut Proposisi Majemuk Proposisi yang bukan merupakan kombinasi proposisi lain disebut Proposisi Atomik a. Konjungsi ( proposisi p dan q ( p ^ q

b. Disjungsi ( proposisi p atau q ( p v q

c. Negasi ( proposisi p ( ~p atau not p Contoh soal kombinasi Proposisi :

Diketahui proposisi sebagai berikut :p : Hari ini hujanq : Hari ini dinginTerjemahkan notasi simbolik ke dalam kata-kata :a. q ~pb. ~p ^ ~qc. ~(~p)a. Hari ini dingin atau tidak hujan (cerah).

b. Hari ini tidak hujan dan tidak dingin.

c. Tidak benar hari ini cerah. Tabel Kebenaran

Adalah cara untuk menentukan nilai kebenaran proposisi majemuk. Nilai kebenaran dari proposisi majemuk ditentukan oleh nilai kebenaran dari proposisi atomiknya dan dihubungkan dengan operator logika.1. Konjungsi ( p ^ q ( bernilai benar jika p dan q keduanya benar, selain itu nilainya salah.Contoh :P : Nilai semua mata kuliah adalah A.Q : Nilai IPKnya adalah 4.00.Pqp ^ q

TTT

TFF

TFF

FFF

2. Disjungsi / inklusif (inclusive or) ( p q ( bernilai salah jika p dan q keduanya salah, selain itu nilainya benar. Contoh :P : Pelamar harus menguasai bahasa C++.Q : Pelamar harus menguasai bahasa Java.Pqp ^ q

TTT

TFF

TFF

FFF

3. Negasi p ( ~ p ( bernilai benar jika p salah, atau sebaliknya. P~q

TF

FT

Contoh :p : Saya pergi ke Mall.4. XOR / eksklusif (eksclusive or) ( p q ( bernilai benar hanya jika salah satu proposisi atomiknya bernilai benar.Pqp q

TTF

TFT

TFT

FFF

Contoh :

P : Untuk mendaftar anggota perpustakaan diharap membawa

KTP atau KTM.5. Implikasi / Kondisional / Proposisi Bersyarat ( jika p, maka q dinotasikan dengan p q. Bernilai salah jika p benar tetapi q salah.Pqp (q

TTT

TFF

FTT

FFT

Contoh :

P : Jika lampu merah menyala maka kendaraan akan berhenti.

6. Bi-implikasi / Bikondisional ( p jika dan hanya jika q dilambangkan dengan p q. Bernilai benar bila mempunyai nilai kebenaran yang sama. Pqp q

TTT

TFF

FTT

FFT

Contoh :P : Jika orang masih hidup maka dia masih bernafas.Tautologi dan KontradiksiSebuah proposisi majemuk disebut tautologi jika ia benar untuk semua kasus.

pqp ^ q~( p ^ q)p v ~( p ^ q)

TTTFT

TFFTT

FTFTT

FFFTT

Sebuah proposisi majemuk disebut kontradiksi jika ia salah untuk semua kasus.PQp ^ qp v q~( p v q)(p ^ q) ^~( p v q)

TTTTFF

TFFTFF

FTFTFF

FFFFTF

EkivalenDua buah proposisi majemuk, P (p,q) dan Q (p,q,) disebut ekivalen secara logika, jika keduanya mempunyai tabel kebenaran yang identic.

Dilambangkan dengan P (p,q) ( Q (p,q) atau P (p,q) Q (p,q)pq~p~q~ p v q

TTTFF

TFFTT

FTTFT

FFTTT

PQp ^ q~( p ^ q)

TTTF

TFFT

FTFT

FFFT

Varian Proposisi Bersyarat / Implikasi

Implikasi : p ( qAda tiga varian Implikasi yaitu : Konvers (kebalikan): q ( p Invers

: ~p ( ~q Kontraposisi

: ~q ( ~pContoh Soal :Tentukan konvers, invers, dan kontraposisi dari pernyataan berikut :Jika Amir mempunyai mobil, maka ia orang kaya

Hukum-Hukum Logika Proposisi1. Hukum identitas :

(i) p v F ( p

(ii) p ^ T ( p2. Hukum null/dominasi :

(i) p ^ F ( F(ii) p v T ( T

3. Hukum negasi :

(i) p v ~p ( T(ii) p ^ ~p ( F4. Hukum idempoten :

(i) p v p ( p(ii) p ^ p ( p

5. Hukum involusi (negasi ganda) :

(i) ~(~p) ( p

6. Hukum penyerapan (absorpsi):

(i) p v (p ^ q) ( p(ii) p ^ (p v q) ( p

7. Hukum komutatif :

(i) p v q ( q v p

(ii) p ^ q ( q ^ p8. Hukum asosiatif :

(i) p v (q v r) ( (p v q) v r(ii) p ^ (q ^ r) ( ( p ^ q) ^ r

9. Hukum distributif :

(i) p v (q ^ r) ( (p v q) ^ (p v r)(ii) p ^ (q v r) ( (p ^ q) ^ (p ^ r)10. Hukum De Morgan :(i) ~ (p ^ q) ( ~v ~q

(ii) ~ (p v q) ( ~p ^ ~q

Soal :Tunjukkan bahwa p ~(p q) dan p ~q keduanya ekivalen secara logika.Jawab :p ~ (p q) ( p v (~p ^ ~q)(hukum demorgan)( (p v ~p) ^ (p v ~q)

(hukum distributif)(T ^ (p v ~q)

(hukum negasi)( p ~q

(hukum identitas)

InferensiProses penarikan kesimpulan dari beberapa prosisi disebut inferensi (inference).Beberapa kaidah inferensi :

1. Modus Ponen / Law of Detachment

Kaidah ini didasarkan pada tautologi (p ^ (p ( q)).

Ditulis dengan cara :

p (q

p

( qContoh Modus Ponen : Misalkan implikasi Jika 20 habis dibagi 2, maka 20 adalah bilangan genap dan hipotesis 20 habis dibagi 2 keduanya benar. Maka menurut Ponen, inferensi sebagai berikut:Jika 20 habis dibagi 2, maka 20 adalah bilangan genap20 habis dibagi 2

( 20 adalah Bilangan GenapAdalah benar.

2. Modus Tollen

Kaidah ini didasarkan pada tautologi [~q ^ (p ( q)] (~p.

Ditulis dengan cara :

p ( q

~q ( r

( ~p3. Silogisme HipotesisKaidah ini didasarkan pada tautologi [(p ( q) ^ (q ( r)] ((p ( r)

Ditulis dengan cara :

p ( q

q ( r

( p ( r

Contoh Modus Tollen : Misalkan implikasi Jika n bilangan ganjil, maka n2 bernilai ganjil dan hipotesis n2 bernilai genap keduanya benar. Maka menurut Modus Tollen, inferensi sebagai berikut :

Jika n bilangan ganjil, maka n2 bernilai ganjil

n2 bernilai genap

( n bukan bilangan ganjil

Adalah benarContoh Silogisme Hipotesis : Misalkan implikasi Jika saya belajar dengan giat, maka saya lulus ujian dan implikasi Jika saya lulus ujian, maka saya cepat menikah keduanya benar. Maka menurut kaidah Silogisme Hipotesis, inferensi sebagai berikut:Jika saya belajar dengan giat, maka saya lulus ujian

Jika saya lulus ujian, maka saya cepat menikah

( jika saya belajar giat, maka saya cepat menikah Adalah benar4. Silogisme DisjungtifKaidah ini didasarkan pada tautologi [(p v q) ^ ~p] (qDitulis dengan cara :

p v q

~p

( q5. SimplikasiKaidah ini didasarkan pada tautologi (p ^ p) ( pDitulis dengan cara :

(p ^ p)

( p

Contoh Silogisme Disjungtif : Inferensi sebagai berikut : Saya belajar dengan giat atau saya menikah tahun depan dan saya tidak belajar dengan giat. Karena itu, saya menikah tahun depan. Maka menurut kaidah Silogisme Disjungtif inferensi sebagai berikut:Saya belajar dengan giat atau saya menikah tahun depanSaya tidak belajar dengan giat

( jika saya belajar giat, maka saya cepat menikah

Adalah benar.

Contoh Simplikasi : Hamid adalah mahasiswa ITB dan mahasiswa Unpar. Karena itu, Hamid adalah mahasiswa ITB. Menggunakan kaidah simplikasi ditulis dengan cara :Hamid adalah mahasiswa ITB dan mahasiswa Unpar.

( Hamid adalah mahasiswa ITB Adalah benar.

6. PenjumlahanKaidah ini didasarkan pada tautologi p ( (p ^ p)

Ditulis dengan cara :

p

( p v q

7. KonjungsiKaidah ini didasarkan pada tautologi ((p) ^ (q)) ( (p ^ q)

Ditulis dengan cara :

p

q

( p ^ q

Contoh Penjumlahan :Taslim mengambil kuliah Matematika Diskrit. Karena itu, Taslim mengambil kuliah Matematika Diskrit atau mengulang kuliah Algoritma. Menggunakan kaidah penjumlahan ditulis dengan cara :Taslim mengambil kuliah Matematika Diskrit

( Taslim mengambil kuliah Matematika Diskrit atau mengulang kuliah Algoritma Contoh Konjungsi :

Taslim mengambil kuliah Matematika Diskrit. Taslim mengulang algoritma. Karena itu, Taslim mengambil kuliah Matematika Diskrit dan mengulang kuliah Algoritma." Menggunakan kaidah konjungsi ditulis dengan cara :

Taslim mengambil kuliah Matematika Diskrit

Taslim mengulang kuliah Algoritma

( Taslim mengambil kuliah Matematika Diskrit dan mengulang kuliah Algoritma

ArgumenArgumen adalah suatu deret proposisi yang dituliskan sebagai :

p1

p2.. pn

( q Contoh Argumen 1 :

Perlihatkan bahwa argument berikut :

Jika air laut surut setelah gempa di laut, maka tsunami datang. Air laut surut setelah gempa di laut. Karena itu tsunami datang. Adalah shahih.

Contoh Argumen 1 :

Perlihatkan bahwa argument berikut :

Jika air laut surut setelah gempa di laut, maka tsunami datang. Tsunami datang. Jadi, air laut surut setelah gempa di laut.Anda tidak benar.

Aksioma, Teorema, Lemma, Corolly a. Aksioma adalah proposisi yang diasumsikan benar. Aksioma tidak memerlukan pembuktian kebenaran lagi.Contoh :Jika diberikan dua buah titik yang berbeda, maka hanya ada satu garis lurus yang melalui dua buah titik tersebut.b. Teoremaadalah proposisi yang sudah terbukti benar.

Contoh :

Jika dua sisi dari sebuah segitiga sama panjang, maka sudut yang berlawanan dengan sisi tersebut sama besar.

Bentuk khusus dari Teorema adalah Lemma dan Collary.c. Lemma

adalah teorema sederhana yang digunakan dalam pembuktian teorema lain.Contoh :

Jika n adalah bilangan bulat positif, maka n - 1 bilangan bulat positif atau n 1 = 0.

d. Corollaryadalah teorema yang dapat dibentuk langsung dari teorema yang telah dibuktikan. Dengan kata lain Corollary adalah teorema yang mengikuti dari teorema lain.Contoh :

Jika sebuah segitiga adalah sama sisi, maka segitiga tersebut sama sudut. ( (mengikuti teorema di atas).

Operator Biner karena mengoperasikan dua buah proposisi

Keterangan :

T = True

F = False

p hanya jika q(p only if q)

p syarat cukup agar q(p is sufficient for q)

q syarat perlu bagi p(q is necessery for p)

q bilamana p(q whenever p)

Ekspresi penulisan implikasi p ( q :

Jika p, maka q(if p, then q)

Jika p, q(if p, q)

p mengakibatkan q(p implies q)

q jika p(q if p)

Ekspresi penulisan bi-implikasi p q :

p jika dan hanya jika q(p if only if q)

p adalah syarat perlu dan cukup untuk q

Jika p maka q, dan sebaliknya

p iff q

Keterangan :

( Dibaca Jadi atau karena itu.

Cara baca :

Jika hipotesis p dan implikasi p ( q

benar, maka konklusi q benar

p1, p2 ,, pn disebut hipotesis / premis. Dan q adalah konklusi.

Sebuah argumen dikatakan valid jika semua hipotesis benar, sebaliknya, meskipun hipotesis benar tetapi ada kesimpulan yang salah maka argumen tersebut dikatakan invalid.