Logika Informatika

BAB I
DASAR-DASAR LOGIKA

 1.1 Pendahuluan
 Logika adalah metode berpikir untuk menentukan apakah suatu argumen yang diberikan valid atau tidak.
-Logika untuk MATEMATIKA = untuk membuktikan teorema-teorema.
-Logika untuk KOMPUTER = untuk menguji kebenaran dari program dan untuk membuktikan teorema-teorema.
-Logika dalam ilmu pengetahuan alam = untuk menarik kesimpulan dari eksperimen-eksperimen.
1.2 Pernyataan
Unit terkecil yang berhubungan dengan logika (proposisional) adalah kalimat. Kalimat-kalimat yang diperhatikan dalam logika bukan sebarang kalimat tetapi kalimat-kalimat yang bernilai benar atau salah, tetapi tidak keduanya. Jenis kalimat ini disebut pernyataan atau statemen (statement).Setiap pernyataan adalah sebuah kalimat, tetapi sebuah kalimat belum
tentu sebuah pernyataan. Hanyalah kalimat-kalimat yang bersifat “menerangkan sesuatu” (kalimat deklaratif) yang dapat digolongkan sebagai pernyataan.
Jadi, pernyataan adalah kalimat deklaratif yang bernilai benar atau salah, tetapi tidak keduanya. Istilah lain dari pernyataan adalah proposisi (propositions) atau kalimat tertutup.

Contoh 1.1
Berikut ini adalah contoh pernyataan:
(a) Bumi adalah bulat.
(b) 2 + 3 = 5 .
(c) Air adalah benda padat
(d) Temperatur pada permukaan planet Venus adalah 8000F.
(e) Matahari akan terbit besok pagi.
Kalimat (a) dan (b) adalah pernyataan dengan nilai kebenaran “benar”. Kalimat (c)
adalah pernyataan dengan nilai kebenaran “salah”. Kalimat (d) adalah kalimat
deklaratif yang nilai benar atau salahnya kita tidak tahu pada saat ini.; akan tetapi
pada prinsipnya kita dapat menentukan nilai kebenarannya sehingga (d) adalah
pernyataan. Kalimat (e) adalah pernyataan karena bernilai benar atau salah,
tetapi tidak keduanya, meskipun kita harus menunggu sampai besok pagi untuk
memastikan nilai kebenarannya.
Contoh 1.2
Berikut ini adalah contoh bukan pernyataan:
(a) Bukalah pintu itu!
(b) Apakah anda dapat berbahasa Cina?.
(c) x lebih besar dari 3 ( x adalah variabel yang menunjukkan bilangan).
Kalimat (a) adalah perintah dan kalimat (b) adalah pertanyaan. Kalimat (c) bukan
pernyataan karena nilai tertentu yang diberikan untuk x kita tidak dapat
mengatakan apakah bernilai benar (lebih besar 3) atau salah (lebih kecil atau sama dengan 3).

1.3 Pernyataan Majemuk dan Penghubung Logika
1.3.1 Pernyataan Majemuk
Kalimat-kalimat sederhana yang benar atau salah adalah dasar dari
pernyataan. Kalimat-kalimat yang lebih besar dan kompleks dapat dikonstruksi
dari pernyataan dasar dengan mengkombinasikannya dengan penghubung logika
(connectives). Jadi, proposisi dan penghubung logika adalah unsur dasar dari
logika proposisional.
Dalam matematika, huruf-huruf x, y, z,... melambangkan variabel yang
dapat diganti dengan bilangan riil dan variabel-variabel ini dapat dikombinasikan
dengan operasi hitung +, ´, -, dan ¸. Dalam logika, huruf-huruf p,q, r,... melambangkan
variabel-variabel pernyataan, artinya variabel yang dapat diganti
dengan pernyataan.
Contoh 1.3
Berikut ini adalah contoh variabel pernyataan:
p : 2 + 3 = 5 .
q : 2 adalah bilangan prima.
r : 2 adalah bilangan rasional.
Pernyataan-pernyataan yang disajikan dengan huruf-huruf p, q dan r
dinamakan sebagai pernyataan primitif.
Variabel-variabel pernyataan dapat digabungkan dengan penghubungpenghubung
logika untuk memperoleh pernyataan majemuk (compound
statements). Nilai kebenaran dari sebuah pernyataan majemuk hanya bergantung
pada nilai-nilai kebenaran dari variabel-variabel pernyataannya (komponenkomponennya)
dan pada jenis penghubung logika yang digunakan. Sebagai
contoh, kita dapat mengkombinasikan variabel-variabel pernyataan dalam Contoh
1.3 dengan penghubung dan (and) untuk membentuk pernyataan majemuk
2 adalah bilangan prima dan 2 adalah bilangan rasional
atau
q dan r .
4
Hubungan dari nilai kebenaran pernyataan majemuk dan variabel-variabel
penyusunnya dapat disajikan dengan sebuah tabel. Tabel ini menyajikan nilai dari
sebuah pernyataan majemuk untuk semua nilai yang mungkin dari variabelvariabel
penyusunnya dan disebut tabel kebenaran (truth table). Dalam
membuat tabel kebenaran, ditulis “T” untuk benar (True) dan “F” untuk salah.
(False)
1.3.2 Penghubung Logika
Ada lima jenis penghubung logika yang dapat dipakai untuk menggabungkan
pernyataan-pernyataan menjadi pernyataan majemuk, yaitu: negasi
(negation), konjungsi (conjunction), disjungsi (disjunction), implikasi (implication) ,
dan biimplikasi (biimplication). Tabel 1.1 menyajikan jenis, simbol dan bentuk
dari lima penghubung logika.
Tabel 1.1
Jenis Penghubung Simbol Bentuk
Negasi (Not) Ø atau ~ tidak …
Konjungsi (And) Ù …dan…
Disjungsi (Or) Ú …atau…
Implikasi Jika… maka…
Biimplikasi Û …jika dan hanya jika…
Prioritas dari penghubung-penghubung logika disajikan dalam Tabel 1.2 .
Penghubung dengan prioritas lebih tinggi harus diselesaikan lebih dahulu.
Tabel 1.2
Penghubung Prioritas
Negasi (Not) 5
Konjungsi (And) 4
Disjungsi (Or) 3
Implikasi 2
Biimplikasi 1
5
Untuk mereduksi jumlah tanda (simbol) dan bentuk digunakan perjanjian
“Tanda kurung dapat dihilangkan apabila pernyataan dapat dikonstruksi dengan
prioritas penghubung”.
1. Negasi
Misalkan p sebuah pernyataan. Negasi (ingkaran) dari p adalah
pernyataan tidak p , yang dilambangkan dengan Øp atau ~ p . Jadi, jika p
bernilai benar, maka Øp bernilai salah, dan jika p bernilai salah, maka Øp
bernilai benar. Tabel kebenaran Øp relatif terhadap p disajikan dalam Tabel 1.3.
Tabel 1.3
p Øp
T F
F T
Contoh 1.4
Tentukan negasi dari pernyataan-pernyataan berikut:
(a) p : 2 + 3 > 5
(b) q : 5 - 2 = 3
(c) r : Hari ini hujan
Penyelesaian:
(a) Øp : 2 + 3 £ 5
(b) Øq : 5- 2 ¹ 3
(c) Ør : Hari ini tidak hujan.
2. Konjungsi
Misalkan p dan q adalah pernyataan. Konjungsi dari p dan q adalah
pernyataan majemuk “ p dan q ”, yang dilambangkan dengan p Ù q . Pernyataan
majemuk p Ù q bernilai benar jika p dan q keduanya benar. Pernyataan
majemuk p Ù q bernilai salah jika salah satu p atau q salah, atau p dan q
keduanya salah. Tabel kebenaran p Ù q disajikan dalam Tabel 1.4.
6
Tabel 1.4
p q p Ù q
T T T
T F F
F T F
F F F
Contoh 1.5
Bentuklah konjungsi dari p dan q :
(a) p : 2 + 3 > 5 ; q : 5 - 2 = 3
(b) p : -3 > -7 ; q : 3 < 5
(c) p : 2 adalah bilangan prima; q : 2 < 4
Penyelesaian:
(a) p Ù q : 2 + 3 > 5 dan 5 - 2 = 3 (F)
(b) p Ù q : - 3 > -7 dan 3<5 (T)
(c) p Ù q : 2 adalah bilangan prima dan 2 < 4 (T)
3. Disjungsi
Disjungsi (inklusif) dari pernyataan-pernyataan p dan q adalah pernyataan
majemuk “ p atau q ”, yang dilambangkan dengan p Ú q . Pernyataan majemuk
p Ú q bernilai benar jika salah satu p atau q benar atau kedua-duanya benar.
Dalam praktek, kadang-kadang ditulis “dan/atau”. Sedangkan kata ”atau” dalam
arti eksklusif dilambangkan dengan Ú . Pernyataan majemuk pÚq bernilai benar
jika salah satu benar tetapi tidak keduanya p atau q benar. Tabel kebenaran
p Ú q dan pÚq disajikan dalam Tabel 1.5.
7
Tabel 1.5
p q p Ú q pÚq
T T T F
T F T T
F T T T
F F F F
Contoh 1.6
Bentuklah disjungsi dari p dan q :
(a) p : 2 + 3 ¹ 5; q : 5 < 3
(b) p : 2 adalah bilangan prima; q : 2 adalah bilangan rasional.
Penyelesaian:
(a) p Ú q : 2 + 3 ¹ 5 atau 5 < 3 (F)
(b) p Ú q : 2 adalah bilangan prima atau 2 adalah bilangan rasional (T).
4. Implikasi
Misalkan p dan q adalah pernyataan. Pernyataan majemuk “jika p , maka
q ”, yang dilambangkan dengan p q disebut pernyataan bersyarat atau
implikasi. Pernyataan p disebut hipotesis atau anteseden (antecedent) dan q
disebut konklusi atau konsekuen (consequent). Pernyataan majemuk p q
bernilai salah jika p benar dan q salah. Dalam kemungkinan lainnya, p q
bernilai benar. Tabel kebenaran p q disajikan dalam Tabel 1.6.
Tabel 1.6
p q p q
T T T
T F F
F T T
F F T
8
Contoh 1.7
Tulislah implikasi dari p dan q :
a) p : Saya lapar; q : Saya akan makan
b) p : 2 adalah bilangan prima; q : 2 < 4
Penyelesaian:
a) Jika saya lapar, maka saya akan makan
b) Jika 2 adalah bilangan prima, maka 2 < 4 .
Dalam matematika (praktek), pernyataan-pernyataan berikut merupakan
bentuk yang ekuivalen, artinya jika salah satu benar maka semua yang lain juga
benar dan jika salah satu salah, semua yang lain juga salah.
(a) Jika p , maka q .
(b) p mengimplikasi q .
(c) Jika p , q .
(d) p hanya jika q .
(d) q jika p .
(e) p adalah syarat cukup untuk q .
(f) q adalah syarat perlu untuk p .
(g) q bilamana saja p .
5. Biimplikasi (ekuivalensi)
Misalkan p dan q adalah pernyataan. Pernyataan majemuk “ p jika dan
hanya jika q ”, yang dilambangkan dengan pÛq disebut biimplikasi atau
ekuivalensi. Tabel kebenaran pÛq disajikan dalam Tabel 1.7. Pernyataan
majemuk pÛq bernilai benar jika p dan q keduanya benar atau keduanya
salah. Biimplikasi pÛq juga dinyatakan sebagai p adalah syarat perlu dan
cukup untuk q .
9
Tabel 1.7
p q pÛq
T T T
T F F
F T F
F F T
Contoh 1.8
Apakah biimplikasi berikut benar?
3 < 4 jika dan hanya jika 4 - 3 > 0.
Penyelesaian:
Misalkan p adalah pernyataan 3 < 4 dan q adalah pernyataan 4 - 3 > 0 .
Karena p dan q keduanya bernilai benar, maka disimpulkan bahwa
pÛq bernilai benar.
Secara umum, sebuah pernyataan majemuk mungkin mempunyai banyak
bagian komponen, masing-masing dari komponen ini merupakan pernyataan yang
disajikan dengan variabel-variabel pernyataan. Pernyataan majemuk
s : p (q Ú ( p r))
memuat tiga pernyataan p , q dan r , masing-masing pernyataan secara
independen bisa bernilai benar atau salah. Secara keseluruhan terdapat 23 = 8
kombinasi yang mungkin dari nilai-nilai untuk p , q dan r , dan tabel kebenaran
untuk s harus memberikan nilai benar atau salahnya s dalam semua kasus.
Jika pernyataan majemuk s memuat n pernyataan komponen , maka
akan ada 2n unsur yang diperlukan dalam tabel kebenaran s . Tabel kebenaran
ini dapat dikonstruksi secara sistematis dengan langkah-langkah sebagai berikut:
Langkah 1. n kolom pertama dari tabel kebenaran diberi label variabel-variabel
pernyataan komponen. Kolom-kolom selanjutnya dikonstruksi untuk
semua kombinasi-kombinasi pernyataan berikutnya, dan kolom
terakhir untuk pernyataan yang ditanyakan.
10
Langkah 2. Terhadap masing-masing n bagian atas pertama, kita tulis 2n
kemungkinan kemungkinan (n-tuple) nilai-nilai kebenaran dari
pernyataan komponen s . Masing-masing n-tuple ditulis pada baris
terpisah.
Langkah 3. Untuk setiap baris kita memperhitungkan (dalam urutan) semua nilai
kebenaran sisanya.
Contoh 1.9
Buatlah tabel kebenaran untuk pernyataan-pernyataan majemuk berikut:
a) Ø( p Ù Øq )
b) ( p q ) Û (Øq Øp )
Penyelesaian: Tabel kebenaran berikut dikonstruksi menggunakan ketiga langkah
di atas.
a) Tabel 1.8
p q Øq p Ù Øq Ø( p Ù Øq )
T T F F T
T F T T F
F T F F T
F F T F F
b) Tabel 1.9
p q p q Øp Øq Øq Øp (p q)Û(Øq Øp)
T T T F F T T
T F F F T F T
F T T T F T T
F F T T T T T
11
1.4 Tautologi, Kontradiksi dan Kontingensi
1.4.1 Tautologi
Definisi 1.1
Sebuah pernyataan majemuk disebut tautologi jika pernyataan tersebut
selalu bernilai benar untuk semua nilai yang mungkin dari pernyataanpernyataan
komponennya.
Contoh 1.10
Menggunakan tabel kebenaran , tunjukkan bahwa pernyataan-pernyataan berikut
adalah tautologi.
a) ( p Ù q ) p
b) (( p Ú q ) Ù Øp ) q
Penyelesaian:
a) Tabel 1.10
p q p Ù q ( p Ù q ) p
T T T T
T F F T
F T F T
F F F T
b) Tabel 1.11
p q p Ú q Øp ( p Ú q ) Ù Øp (( p Ú q ) Ù Øp ) q
T T T F F T
T F T F F T
F T T T T T
F F F T F T
12
1.4.2 Kontradiksi
Definisi 1.2
Sebuah pernyataan majemuk disebut kontradiksi jika pernyataan tersebut
selalu bernilai salah untuk semua nilai yang mungkin dari pernyataanpernyataan
komponennya.
Istilah lain dari kontradiksi adalah mustahil (absurdity).
Contoh 1.11
Menggunakan tabel kebenaran , tunjukkan bahwa pernyataan-pernyataan berikut
adalah kontradsiksi.
a) p Ù Øp
b) ( p Ù q ) Ù Øp .
Penyelesaian:
a) Tabel 1.12
p Øp p Ù Øp
T F F
T F F
F T F
F T F
b) Tabel 1.13
p q p Ù q Øp ( p Ù q ) Ù Øp
T T T F F
T F F F F
F T F T F
F F F T F
Negasi dari sebuah tautologi adalah kontradiksi, dan sebaliknya.
13
1.4.3 Kontingensi
Definisi 1.3
Kontingensi (contingency) adalah sebuah pernyataan majemuk yang
dapat bernilai benar atau salah, bergantung pada nilai-nilai kebenaran dari
variabel-variabel pernyataannya.
Contoh 1.12
Menggunakan tabel kebenaran , tunjukkan bahwa pernyataan-pernyataan berikut
adalah kontingensi.
a) p (q Ù p )
b) ( p q ) Ù ( p Ú q )
Penyelesaian:
a) Tabel 1.14
p q q Ù p p (q Ù p )
T T T T
T F F F
F T F T
F F F T
b) Tabel 1.15
p q p q p Ú q ( p q ) Ù ( p Ú q )
T T T T T
T F F T F
F T T T T
F F T F F
14
1.5 Konvers, Kontraposisi dan Invers
Jika p q adalah sebuah implikasi, maka terdapat beberapa
pernyataan yang berhubungan dengan p q , yaitu:
Konvers (converse) dari p q adalah q p ;
Kontraposisi/Kontrapositif (contrapositive) dari p q adalah
(Øq) (Øp) ;
Invers (inverse) dari p q adalah (Øp) (Øq) .
Contoh 1.13
Tulislah konvers, kontrapositif dan invers dari implikasi-implikasi berikut:
a) x positif x2 positif
b) Jika hari hujan, maka saya basah kuyup.
c) x = 3 x bilangan bulat ganjil.
Penyelesaian:
a) Konvers : x2 positif x positif.
Kontraposisi : x2 tidak positif x tidak positif.
Invers : x tidak positif x2 tidak positif.
b) Konvers : Jika saya basah kuyup, maka hari hujan.
Kontraposisi : Jika saya tidak basah kuyup, maka hari tidak hujan.
Invers : Jika hari tidak hujan, maka saya tidak basah kuyup.
c) Konvers : x bilangan bulat ganjil x = 3.
Kontraposisi : x bukan bilangan bulat ganjil x ¹ 3
Invers : x¹3 x bukan bilangan bulat ganjil.
1.6 Implikasi Logis dan Ekuivalensi Logis
1.6.1 Implikasi Logis
Jika p q tautologi, maka p q selalu bernilai benar untuk semua nilai
p dan q yang mungkin. Dilambangkan dengan p®q dan dibaca “ p implikasi
15
logis q ”. Artinya p®q digunakan apabila pernyataan p selalu mengimplikasi
pernyataan q tanpa memperhatikan nilai dari variabel-variabel penyusunnya.
Contoh 1.14
Menggunakan tabel kebenaran, tunjukkan bahwa pernyataan-pernyataan
majemuk berikut adalah tautologi :
a) ( p Ù q) p
b) Øp ( p q)
Penyelesaian:
a) Tabel 1.16
p q p Ù q (pÙq) p
T T T T
T F F T
F T F T
F F F T
Jadi, ( p Ù q) ® p
b) Tabel 1.17
p q Øp p q Øp ( p q)
T T F T T
T F F F T
F T T T T
F F T T T
Jadi, Øp ® ( p q) .
16
1.6.2 Ekuivalensi Logis
Definisi 1.4
Dua pernyataan 1 s dan 2 s dikatakan ekuivalen logis (ekuivalen) dan ditulis
1 2 s « s (dibaca “ 1 s ekuivalen logis dengan 2 s ”) atau 1 2 s º s (dibaca
“ 1 s ekuivalen dengan 2 s ”) jika 1 s dan 2 s selalu bernilai sama (artinya
1 2 s Û s tautologi).
Contoh 1.15
Menggunakan tabel kebenaran, tunjukkan bahwa pernyataan-pernyataan
majemuk berikut adalah tautologi :
a) Ø(Øp) Û p
b) Ø( p Ù q) Û (Øp) Ú (Øq) .
Penyelesaian:
a) Tabel 1.18
p Øp Ø(Øp) Ø(Øp) Û p
T F T T
T F T T
F T F T
F T F T
Jadi, Ø(Øp) « p atau Ø(Øp) º p .
b) Tabel 1.19
p q Øp Øq pÙq Ø(pÙq) (Øp)Ú(Øq) Ø( p Ù q) Û (Øp) Ú (Øq)
T T F F T F F T
T F F T F T T T
F T T F F T T T
F F T T F T T T
Jadi, Ø( p Ù q) « (Øp) Ú (Øq) atau Ø( p Ù q) º (Øp) Ú (Øq) .
17
Teorema 1.1
Pernyataan-pernyataan p q dan (Øq) (Øp) adalah ekuivalen.
Bukti :
Tabel 1.19 berikut menyajikan tabel kebenaran untuk membandingkan
nilai (Øq) (Øp) dan nilai p q .
Tabel 1.20
p q p q Øq Øp (Øq) (Øp)
T T T F F T
T F F T F F
F T T F T T
F F T T T T
Karena kolom 3 dan kolom 6 dari Tabel 1.20 adalah identik, maka disimpulkan
bahwa pernyataan-pernyataan p q dan (Øq) (Øp) adalah ekuivalen.
Jadi, kontrapositif dari sebuah implikasi selalu ekuivalen dengan implikasi semula.
Teorema 1.2
Pernyataan-pernyataan p q dan (Øp) Ú q adalah ekuivalen.
Bukti:
Tabel 1.21 menyajikan tabel kebenaran untuk membandingkan nilai
(Øp) Ú q (kolom 5) dan nilai p q (kolom 3).
Tabel 1.21
p q p q Øp (Øp) Ú q
T T T F T
T F F F F
F T T T T
F F T T T