PENDAHULUAN

Logika Informatika

Logika (logic) berasal dari bahasa yunani “logos”yang berarti kata “ucapan” atau

“alasan”. Logika dapat diartikan ilmu yang berhubungan dengan prinsip-prinsip

validitas penalaran dan argumen-argumen. Penarikan kesimpulan tentang validitas

argumen dinamakan logika deduktif (deductive reasonin). Di mana kesimpulan harus

mengikuti kebenaran premis-premisnya. Jadi tidak mungkin kesimpulan yang salah

diperoleh dari premis-premis yang benar, atau satu saja premis yang salah. Maka

kesimpulan juga harus bernilai salah. Di pihak lain juga dikembangkan logika induktif

(inductive logic). Yang pengertiannya sama dengan logika deduktif, tetapi penarikan

kesimpulan disertai dengan tampilnya beberapa kemungkinan yang menyertainya.

Logika pertama kali dikembangkan oleh Aristoteles (filsuf yunani) sekitar 300

tahun sebelum masehi dan disebut logika tradisional atau logika klasik (classical logic)

atau logika ini juga disebut logika simbolik (symbolic logic) karena menggunakan

simbol-simbol logika secara intensif.

Logika memainkan peranan penting di berbagai bidang ilmu, antara lain di bidang

matematika dan ilmu komputer. Logika juga dapat dapat dimanfaatkan untuk membuat

dan menguji program-program komputer. Berbagai cabang ilmu komputer/informatika

menggunakan logika untuk mengerjakannya, misalnya kecerdasan buatan (artificial

intelligence). Sistem pakar (expert systems). Pemrograman logika (logic programming)

dan sebagainya.

Peran logika yang penting ini menyebabkan logika menjadi salah satu ilmu kunci

di bidang komputer dan diajarkan sejak awal kuliah di bidang komputer. Logika yang

dimaksud di sini adalah logika matematika (mathematical logic) yaitu logika yang

menggunakan kaidah-kaidah dan turan aturan matematika untuk menyelesaikannya.

Logika matematika adalah suatu studi tentang proses-proses deduksi yang bersifat

matematik. Subyek logika dapat ditelusuri dari ilmu filosofi, sehingga peran filosofi

penting dalam logika matematika. Dengan kata lain sebenarnya logika matematika

adalah metode pencarian pembuktian (methods of proofs) ini dapat dibagi menjadi dua

bagian (1) penalaran semantik (semantic reasoning) yang berusaha menjawab “apakah

1

kebenaran itu?” dan (2) penalaran sintaktik (syntactic reasoning), yang menjawab “apa

yang dapat di ungkapkan?”.

Logika lebih mengacu pada penalaran sintatik, karena ia menghasilkan suatu

pernyataan-pernyataan (statements) yang dapat bernilai benar (true) atau salah (false)

dan menghasilkan kesimpulan berdasarkan pernyataan-pernyataan tersebut. Pernyataan-

pernyataan yang bernilai benar atau salah tersebut menjadi subjek utama dari derivasi

logika (logical derivation).

Dasar-dasar dari derivasi logika adalah proposisi-proposisi (propositions), yakni

pernyataan-pernyataan yang bernilai benar atau salah. Proposisi-proposisi dapat

digabung dan dimanipulasi dengan berbagai cara, yang merupakan subjek utama dari

logika proposional (propositional logic) atau kalkulus proposional (propositional

calculus).

Logika proposional disusun dari suatu argumen (argument) yang logis. Argumen

yang logis berisi proposisi atomik (atomic propositions) yang tak mungkin dipecahkan.

Proposisi-proposisi atomik tersebut dapat dirangkai atau dikombinasikan dengan

berbagai perangkai (connective) menjadi proposisi majemuk (compound propositions),

atau disebut juga ekspresi logika (logical expression).

Di sini ada proposisi-proposisi yang disebut tautologi (tautologies, tautology),

yakni proposisi yang nilainya selalu benar. Tautologi akan menghasilkan implikasi logis

(logical implications) dan ekuivaleni logis (logical equivalences) atau kesamaan logis.

Implikasi logis merupakan dasar dari penalaran yang kuat (sound reasoning),

sedangkan kesamaan logis menunjukkan bagaimana proposisi-proposisi dapat

dimanipulasi secara aljabar (algebraically).

2

PEMBAHASAN

2.1 Proposisi (Pernyataan)

Di dalam matematika, tidak semua kalimat berhubungan dengan logika. Hanya

kalimat yang bernilai benar atau salah saja yang digunakan dalam penalaran. Kalimat

tersebut dinamakan proposisi (preposition).

Sebuah proposisi (proposition) atau statement ialah sebuah kalimat deklaratif

yang memiliki tepat satu nilai kebenaran, yaitu: ”Benar” (B) atau ”Salah” (S).

Kalimat tanya atau kalimat perintah tidak dianggap sebagai pernyataan.

Berikut ini adalah beberapa contoh proposisi :

a. 1 + 2 = 3

b. Presiden RI tahun 2005 adalah SBY

c. 6 adalah bilangan prima

d. Warna bendera RI adalah biru dan merah

Kalimat-kalimat di atas adalah kalimat proposisi karena dapat diketahui

benar/salahnya. Kalimat (a) dan (b) bernilai benar, sedangkan kalimat (c) dan (d)

bernilai salah.

Kalimat-kalimat berikut bukan pernyataan :

a. x + 2 = 10

b. minumlah sirup ini 2 kali sehari.

c. Alangkah cantiknya gadis itu!

2.2 Mengkombinasikan Proposisi (Proposisi Majemuk)

Kita dapat membentuk proposisi baru dengan cara mengkombinasikan satu atau

lebih proposisi. Operator yang digunakan untuk mengkombinasikan proposisi

disebut operator logika. Operator logika dasar yang digunakan

adalah dan (and), atau (or), dan tidak (not). Dua operator pertama dinamakan

operator biner karena operator tersebut mengoperasikan dua buah proposisi, sedangkan

operator ketiga dinamakan operator uner karena ia hanya membutuhkan satu buah

proposisi.

3

Proposisi baru yang diperoleh dari pengkombinasian tersebut dinamakan proposisi

majemuk (compound proposition). Proposisi yang bukan merupakan kombinasi

proposisi lain disebut proposisi atomik. Dengan kata lain, proposisi majemuk disusun

dari proposisi-proposisi atomik. Metode pengkombinasian proposisi dibahas oleh

matematikawan Inggris yang bernama George Boole pada tahun 1854 di dalam bukunya

yang terkenal, The Laws of  Thought. Proposisi majemuk ada tiga macam, yaitu

konjungsi, disjungsi, dan ingkaran.

Misalkan p dan q adalah proposisi.

2.2.1 Konjungsi

Konjungsi adalah proposisi majemuk yang menggunakan kata hubung

“dan”. Konjungsi dari proposisi majemuk p dan q dinotasikan dengan “pq”,

yaitu sebuah Proposisi yang bernilai benar jika Proposisi p dan q keduanya

bernilai benar, dan bernilai salah jika salah satu p atau q (keduanya) salah.

p q p qBBSS

BSBS

BSSS

Contoh:

p : Boyolali berada di Jawa Tengah (B)

q : Boyolali termasuk kota metropolitan (S)

p q : Boyolali berada diJawa Tengah dan termasuk kota metropolitan (S).

2.2.2 Disjungsi

Disjungsi merupakan Proposisi majemuk yang menggunakan kata hubung

“atau”. Disjungsi dari proposisi majemuk p dan q dinotasikan dengan “p q”,

yaitu sebuah Proposisi yang bernilai benar jika Proposisi p dan q salah satu atau

keduanya benar, dan bernilai salah jika keduanya bernilai salah.

p q p qBBSS

BSBS

BBBS

4

Contoh: 

p : Boyolali berada di Jawa Tengah (B) 

q : Boyolali termasuk kota metropolitan (S) 

p q : Boyolali berada di Jawa Tengah atau termasuk kota metropolitan (B).

2.2.3 Negasi

Dari sebuah pernyataan tunggal (atau majemuk), kita bisa membuat sebuah

pernyataan baru berupa “ingkaran” dari pernyataan itu. “Ingkaran” disebut juga

“negasi” atau “penyangkalan”. Ingkaran menggunakan operasi uner (monar)

“atau”.

p ~p

B

S

S

B

Contoh:

p : Palembang adalah ibukota propinsi Sumatera Selatan.

~p : Tidak benar Palembang adalah ibukota propinsi Sumatera Selatan.

atau

Palembang bukan ibukota propinsi Sumatera Selatan.

Di sini ~p salah karena p benar.

2.2.4 Implikasi

Implikasi merupakan Proposisi majemuk yang dinyatakan dengan kalimat:

“jika p maka q” dan dinotasikan dengan “p q”. Proposisi p disebut sebab atau

hipotesis atau enteseden, sedangkan Proposisi q disebut akibat atau konklusi atau

konsekuen. Proposisi implikasi bernilai salah jiika hipotesis p bernilai benar dan

konklusi q bernilai salah. Untuk kasus lainnya bernilai benar.

P q p qBBSS

BSBS

BSBB

Contoh:

p  : Ahmad lulus Ujian Nasional (B)

q  : Ahmad Mentraktir temannya (B)

p  q : Jika Ahmad lulus Ujian Nasional maka ia mentraktir temannya (B)

5

2.2.5 Biimplikasi

Biimplikasi atau bikondosional adalah pernyataan majemuk dari dua

pernyataan p dan q yang dinyatakan dengan notasi “p q” yang bernilai sama

dengan (p q) (q p) sehingga dapat dibaca “ p jika dan hanya jika q” atau “p

bila dan hanya bila q”. Biimplikasi 2 pernytaan hanya akan bernilai benar jika

implikasi kedua kalimat penyusunnya sama-sama bernilai benar.

Contoh

p : Dua garis saling berpotongan adalah tegak lurus.

q : Dua garis saling membentuk sudut 90 derajat.

p q : Dua garis saling berpotongan adalah tegak lurus jika dan hanya jika dan

hanya jika dua garis saling membentuk sudut 90 derajat.

p q p q q p (p q) (q p) p q

B

B

S

S

B

S

B

S

B

S

B

B

B

B

S

B

B

S

S

B

2.3 Skema

Skema (schemas) merupakan cara untuk menyederhanakan suatu proposisi

mejemuk yang rumit, dengan memberi tanda huruf tertentu untuk menggantikan suatu

sub ekspresi ataupun sub-sub eksresi.

Definisi: semua ekspresi yang berisi identifikator-identifikator yang menunjukkan

adanya suatu ekspresi logika disebut skema.

Suatu ekspresi logika tertentu , misalnya (A B) dapat diganti dengan P,

sedangkan (A B) dapat dianti dengan Q. Jadi P berisi variabel proposisional A dan B,

demikian juga Q. P di sini bukan varibel proposisional, karena nilai P tergantung dari

nilai A dan B.

Contoh 3-2 :

P = (A B) dan Q = (A B), maka (P → Q) = ((A B) → (A B))

6

Sekarang perhatikan yang berikut ini :

Expresi apa saja berbentuk (P) disebut negasi.

Expresi apa saja berbentuk (P Q) disebut konjungsi.

Expresi apa saja berbentuk (P Q) disebut disjungsi.

Expresi apa saja berbentuk (P → Q) disebut implikasi (conditional)

Expresi apa saja berbentuk (P ↔ Q) disebut ekuivalensi (biconditional)

Contoh di atas ((A B) → (A B)) disebut implikasi yang berisi konjungsi

(A B) dan disjungsi (A B).

Sekarang lihat aturan berikut ini :

1) Semua ekspresi atomik adalah fpe

2) Jika P adalah fpe, maka juga (P)

3) Jika P dan Q adalah fpe, maka juga (P Q), (P Q), (P → Q) dan (P↔Q)

4) Tak ada fpe lainnya.

Ekspresi-ekspresi logika yang dijelaskan di atas disebut well formed formulae

(wff). Jadi, wff adalah fpe demikian juga sebaliknya.

Jika ada suatu ekspresi logika yang di jelaskan di atas di sebut well-formed

formulae (wff). Jadi wff adalah fpe demikian juga sebaliknya.

Jika ada suatu ekspresi logika (P). Maka P disebut skop negasi (scope of

negation) dengan perangkai disebut perangkai utama (main connective) dari (P).

maka contoh di atas, yakni (P→Q).

2.4 Parsing

Teknik memisah-misah atau memilah-milah kalimat menjadi proposisi-proposisi

yang paling kecil (atomik) di sebut teknik Parsing, yang hasilnya dapat diwujudkan

dalam bentuk Parse Tree berikut ini :

7

Selanjutnya akan diubah menjadi ekspresi logika yang berbentuk proposisi

majemuk fpe berikut :

A = Dewi lulus sarjana teknik informatika

B = Orang tua Dewi senang

C = Dewi bekerja

D = Usaha Dewi sia-sia

Maka pernyataan di atas yang berupa proposisi majemuk dapat diwujudkan

dalam fpe seperti berikut :

(A → (B ˄ C )) ˄ (( ¬ A) → D)

2.5 Tautologi

Untuk menjaga kebenaran sebuah pernyataan maka setiap operator/penghubung

diberikan aturan yang lebih tinggi.

2.5.1 Tautologi

Argumen yang validitasnya dibuktikan dengan tabel kebenaran harus

menunjukkan nilai benar maka argumen tersebut valid, jika tidak maka

sebaliknya. Jika pada tabel kebenaran untuk semua pasangan nilai variabel-

variabel proposisional yang ada bernilai benar atau T, maka disebut tautologi

(tautology).

Contoh:

Lihat ekspresi logika dari suatu pernyataan berikut ini:

(A B) (C (B C))

Buat tabel kebenarannya sebagai berikut:

C(BC

(A B) (C (B C))

A B C B C A B B CF F F T T F T T TF F T T F F F T TF T F F T F T T TF T T F F F T T TT F F T T F T T TT F T T F F F T TT T F F T T T T TT T T F F T T T T

8

Ekspresi logika di atas adalah tautologi karena pada tabel kebenaran,

semua pasangan menghasilkan nilai T

Contoh:

Apakah (AA) adalah tautologi?

Pembuktian: Buatlah tabel kebenarannya:

A A AA

F T TT F T

Jadi, (AA) adalah tautologi, dan juga disebut Exluded Middle Law.

Contoh:

Apakah ABB adalah tautologi?

Pembuktian: Buatlah tabel kebenarannya:

A B AB AB ABB

F F F T T

F T F T T

T F F T T

T T T F T

Jadi, ekspresi di atas juga Tautologi

Tautologi juga dapat ditulis dengan symbol ╞ (suatu metasymbol, bukan

perangkai logika). Maka pada ekspresi logika di atas dapat ditulis:

╞ A B B

Diketahui : Jika ABB adalah tautologi

Buktikan : (A B C) C juga tautologi

Bukti:

Misalnya memakai skema P dan Q.

I. Masukkan ke ekspresi logika pertama menjadi PQQ

II. Misalnya: P = AB sedangkan Q = C, masukkan ke ekspresi logika yang

dibuktikan. Maka:

9

(A B C) C akan menjadi PQQ

III. Lihat (I) dan (II) akan terlihat sama, maka memang tautologi.

Jika tautologi dipakai pada suatu argumen, berarti argumen harus

mempunyai nilai T pada seluruh pasangan yang ada pada tabel kebenaran yang

membuktikan bahwa argumen tadi valid, yang juga kadang-kadang disebut

argumen yang kuat (sound argument).

Argumen haruslah memiliki premis-premis dan mempunyai kesimpulan.

Jika premis-premis benar, maka kesimpulan juga harus benar.

Contoh:

Lihat pada argumen berikut:

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 lagi menjadi ekspresi logika yang terdiri dari premis-premis dan

kesimpulan. Ekspresi logika 1 dan 2 adalah premis-premis, sedangkan ekspresi

logika 3 adalah kesimpulan.

1) A B (premis)2) C B (premis)3) (AC) B (kesimpulan)

maka sekarang dapat ditulis:

((AB) (CB)) ((AC)B)

atau

{AB, CB}╞ (AC)B

kemudian buatlah tabel kebenaran dari ekspresi logika tersebut:

((AB) (CB ((AC)B)

10

A B C AB CB (AB) (CB) AC (AC)BF F F T T T F T TF F T T F F T F TF T F T T T F T TF T T T T T T T TT F F F T F T F TT F T F F F T F TT T F T T T T T TT T T T T T T T T

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.

2.5.2 Kontradiksi

Kebalikan dari tautologi adalah kontradiksi (contradiction) atau

absurditas (absurdities), di mana semua nilai pasangan nilai dari tabel kebenaran

menghasilkan nilai F.

Lihat pada ekspresi logika berikut:

A A

A A A A

F T FT F F

Jadi, (AA) pada tabel kebenaran semua bernilai F, sehingga disebut

kontradiksi.

Suatu kontradiksi pada argumen akan dijumpai jika antara premis-premis

bernilai T, sementara kesimpulan bernilai F. Namun hal ini tidak mungkin

terjadi, karena premis-premis yang benar harus menghasilkan kesimpulan benar.

Dalam bahasa logika, konjungsi dari semua premis dengan negasi dari

kesimpulan selalu bernilai F, dan terjadilah kontradiksi. Negasi kesimpulan

berarti memberi nilai F pada negasi kesimpulan.

Lihat ekspresi logika berikut ini:

((A B) A) B

11

Tabel kebenarannya seperti berikut:

(( A B) A) B

A B A B ( A B) (( A B) A)F F T F F F FF T T T T T FT F F T T F FT T F F T F F

Jadi ekspresi logika di atas terjadi kontradiksi. Dalam logika, kontradiksi

dapat ditulis F atau 0 saja, sehingga jika A adalah kontradiksi, maka A = F atau

A = 0.

2.5.3 Contingent

Jika semua nilai kebenaran menghasilkan nilai F dan T maka terjadi

contingent atau formula campuran (mixed formulae).

Lihat contoh pada ekspresi logika berikut:

((A B) C) A

Tabel kebenarannya sebagai berikut:

((A B) C) A

A B C A B A B CF F F F T FF F T F T FF T F F T FF T T F T FT F F F T TT F T F T TT T F T F TT T T T T T

Perhatikan ekspresi logika berikut ini:

((A B) (B C)) (C A)

Tabel kebenarannya sebagai berikut:

((A B) (B C))

(( A B) (B C)) (C A)

12

A B C B C A B B C C AF F F T T T F F F TF F T T F T T T T TF T F F T T T F T FF T T F F T T T T TT F F T T F F T F TT F T T F F T T F TT T F F T T T T T TT T T F F T T T T T

Nilai-nilai kebenaran pada nilai kebenaran sebagai hasil akhir di tabel

kebenaran tidak selalu harus urut antara F dan T, yang penting ada T dan ada F.

Argumen yang memiliki nilai kebenaran contingent, harus memilih nilai-

nilai kebenarannya hanya pada T. perhatikan bahwa masih ada premis-premis

yang T dan F, tetapi kesimpulan T. Ingat bahwa (F T = T). Pada kasus ini

argumen tetap dianggap tidak valid karena yang bukan tautologi - atau apa saja

asal bukan tautologi - dianggap tidak valid. Terdapat istilah yang penting pada

tautologi, yakni ekuivalen secara logis (logically equivalence).

13

KESIMPULAN

Logika disebut juga “The Calculus of Computer Science” karena logika

memegang peranan yang sangat penting di bidang ilmu komputer. Peran kalkulus

(matematika) sama pentingnya untuk ilmu-ilmu bidang sains, misalnya ilmu fisika, ilmu

elektronika, ilmu kimia, dan sebagainya. Oleh karena itu, biasanya pelajar, mahasiswa,

guru, dan dosen setuju bahwa logika memainkan peranan penting dalam berbagai

bidang keilmuan, bahkan dalam kehidupan manusia sehari-hari.

Logika, komputasi sitem, dan matematika diskrit memiliki peran penting dalam

ilmu komputer karena semuanya berperan dalam pemrograman. Logika merupakan

dasar-dasar matematis suatu perangkat lunak, digunakan untuk memformalkan sistem

bahasa pemrograman dan spesifikasi program, serta menguji ketepatan suatu program.

Hal ini menunjukkan betapa pentingnya logika matematika karena banyak ilmu,

khususnya dalam bidang ilmu komputer, yang memerlukan logika untuk berkembang.

Jadi, logika informatika ini sangat lah penting untuk suatu program dalam

komputer dan di dalam perkembangan komputer dan lain-lainya, jika semakin banyak

ahli logika maka semakin  canggihlah teknologi yang akan kita miliki.

14

DAFTAR PUSTAKA

Munir, Rinaldi. 2005. Matematika Diskrit. Bandung: Informatika.

Wirodikromo, Sartono. 2007. Matematika. Jakarta: Erlangga.

Limbong, A dan A. Prijono. 2006. Matematika Diskrit. Bandung: CV Utomo.

Soesianto, F dan Djoni Dwijono.2003. Logika Proposisional. Yogyakarta: Andi.

Upschutz, Seymour dan Marc Lars Lipson. 2008. Matematika Diskrit. Jakarta:

Erlangga.

15