MATEMATIKA DISKRIT

LOGIKA
Logika
 Perhatikan argumen di bawah ini:

Jika anda mahasiswa Informatika maka anda

tidak sulit belajar Bahasa Java. Jika anda tidak
suka begadang maka anda bukan mahasiswa
Informatika. Tetapi, anda sulit belajar Bahasa
Java dan anda tidak suka begadang. Jadi, anda
bukan mahasiswa Informatika.

Apakah kesimpulan dari argumen di atas valid?

Alat bantu untuk memahami argumen tsb
adalah Logika

2
 Banyak teorema dalam Ilmu
Komputer/Informatika yang membutuhkan
pemahaman logika.

 Contoh:
1. Syarat cukup graf dengan n simpul
mempunyai sirkuit Hamilton adalah derajat
tiap simpul  n/2.

2. T(n) = (f(n)) jika dan hanya jika O(f(n)) =

(f(n)).

3
 Bahkan,logika adalah jantung dari
algoritma dan pemrograman.

 Contoh:
if x mod 2 = 0 then
x:=x + 1
else x:=x – 1

4
Aristoteles, peletak dasar-dasar logika

5
 Logika merupakan dasar dari semua
penalaran (reasoning).
 Penalaran didasarkan pada hubungan
antara pernyataan (statements).
 Di dalam logika, tidak semua jenis
kalimat menjadi obyek tinjauan.

Proposisi
 Pernyataan atau kalimat deklaratif
yang bernilai benar (true) atau salah
(false), tetapi tidak keduanya.
 PERMAINAN
“Gajah lebih besar daripada tikus.”

Apakah ini sebuah pernyataan? YA

Apakah ini sebuah proposisi? YA

Apakah nilai kebenaran

dari proposisi ini? BENAR

7
PERMAINAN

“520 < 111”

Apakah ini sebuah pernyataan? YA

Apakah ini sebuah proposisi? YA

Apakah nilai kebenaran

dari proposisi ini? SALAH

8
PERMAINAN
“y > 5”

Apakah ini sebuah pernyataan? YA

Apakah ini sebuah proposisi? TIDAK
Nilai kebenaran dari pernyataan tersebut
bergantung pada y, tapi nilainya belum
ditentukan.
Pernyataan jenis ini kita sebut sebagai
fungsi proposisi atau kalimat terbuka. 9
 PERMAINAN
“Sekarang tahun 2003 dan 99 < 5.”

Apakah ini sebuah pernyataan? YA

Apakah ini sebuah proposisi? YA

Apakah nilai kebenaran SALAH

dari proposisi ini?
10
 PERMAINAN
“Tolong untuk tidak tidur selama kuliah”

Apakah ini sebuah pernyataan? TIDAK

Ini adalah sebuah permintaan.

Apakah ini sebuah proposisi? TIDAK

Hanya pernyataanlah yang bisa menjadi

proposisi.
11
 PERMAINAN
“x < y jika dan hanya jika y > x.”

Apakah ini pernyataan ? YA

Apakah ini proposisi ? YA
… karena nilai kebenarannya
tidak bergantung harga
spesifik x maupun y.
Apakah nilai kebenaran
dari proposisi ini ? BENAR
12
Contoh 1. Semua pernyataan di bawah ini adalah proposisi:

(a) 13 adalah bilangan ganjil

(b) Soekarno adalah alumnus UGM.

(c) 1 + 1 = 2

(d) 8  akar kuadrat dari 8 + 8

(e) Ada monyet di bulan

(f) Hari ini adalah hari Rabu

(g) Untuk sembarang bilangan bulat n  0, maka 2n adalah

bilangan genap

(h) x + y = y + x untuk setiap x dan y bilangan riil

13
 Contoh 2. Semua pernyataan di bawah ini bukan
proposisi
(a) Jam berapa kereta api Argo Bromo tiba di Gambir?
(b) Isilah gelas tersebut dengan air!
(c) x + 3 = 8
(d) x > 3

Kesimpulan: Proposisi adalah kalimat berita

14
 Pernyataan yang melibatkan peubah (variable)
disebut predikat, kalimat terbuka, atau fungsi
proposisi
Contoh: “ x > 3”, “y = x + 10”
Notasi: P(x), misalnya P(x): x > 3

 Predikat dengan quantifier: x P(x)

 Kalkulus proposisi: bidang logika yang berkaitan

dengan proposisi.

 Kalkulus predikat: bidang logika yang berkaitan

dengan predikatr dan quantifier.
15
 Kembali ke kalkulus proposisi

 Proposisi dilambangkan dengan huruf kecil p, q, r, ….

 Contoh:
p : 13 adalah bilangan ganjil.
q : Soekarno adalah alumnus UGM.
r: 2+2=4

16
MENGKOMBINASIKAN PROPOSISI
 Misalkan p dan q adalah proposisi.
1. Konjungsi (conjunction): p dan q
Notasi p  q,
2. Disjungsi (disjunction): p atau q
Notasi: p  q
3. Ingkaran (negation) dari p: tidak p
Notasi: p

 p dan q disebut proposisi atomik

 Kombinasi p dengan q menghasilkan proposisi
majemuk (compound proposition
17
Contoh 3. Diketahui proposisi-proposisi
berikut:
p : Hari ini hujan
q : Murid-murid diliburkan dari sekolah

p  q : Hari ini hujan dan murid-murid

diliburkan dari sekolah
p  q : Hari ini hujan atau murid-murid
diliburkan dari sekolah
p : Tidak benar hari ini hujan
(atau: Hari ini tidak hujan)

18
Contoh 4. Diketahui proposisi-proposisi berikut:
p : Pemuda itu tinggi
q : Pemuda itu tampan

Nyatakan dalam bentuk simbolik:

(a) Pemuda itu tinggi dan tampan
(b) Pemuda itu tinggi tapi tidak tampan
(c) Pemuda itu tidak tinggi maupun tampan
(d) Tidak benar bahwa pemuda itu pendek atau tidak
tampan
(e) Pemuda itu tinggi, atau pendek dan tampan
(f) Tidak benar bahwa pemuda itu pendek maupun Noted
tampan tidak
tampan
Penyelesaian:
(a) pq
(b) p  q
(c) p  q
(d) (p  q) 19
(e) p  (p  q)
(f) (p  q)
Tabel Kebenaran

p q pq p q pq p q

T T T T T T T F
T F F T F T F T
F T F F T T
F F F F F F

Contoh 5. Misalkan
p : 17 adalah bilangan prima (benar)
q : bilangan prima selalu ganjil (salah)
p  q : 17 adalah bilangan prima dan bilangan prima
selalu ganjil (salah) 20
 Operator proposisi di dalam Google

21
22
Contoh 5. Bentuklah tabel kebenaran dari proposisi
majemuk (p  q)  (~q  r).
p q r pq ~q ~q  r (p  q)  (~q  r)

T T T T F F T
T T F T F F T
T F T F T T T
T F F F T F F
F T T F F F F
F T F F F F F
F F T F T T T
F F F F T F F
23
 Proposisi majemuk disebut tautologi jika ia benar
untuk semua kasus

 Proposisi majemuk disebut kontradiksi jika ia

salah untuk semua kasus.

24
Contoh 6. p  ~(p  q) adalah sebuah tautologi

p q pq ~(p  q) p  ~(p  q)

T T T F T
T F F T T
F T F T T
F F F T T

25
Contoh 7. (p  q)  ~(p  q) adalah sebuah kontradiksi
p q pq pq ~(p  q) (p  q)  ~(p  q)

T T T F F F
T F F T F F
F T F T F F
F F F F T F

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

Notasi: P(p, q, …)  Q(p, q, …)

Contoh 8. Hukum De Morgan: ~(p  q)  ~p  ~q.

p q p  q ~ (p  q) ~p ~q ~ p  ~ q

T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T
27
 HUKUM-HUKUM LOGIKA
Disebut juga hukum-hukum aljabar proposisi.
1. Hukum identitas: 2. Hukum null/dominasi:
− p  F  p − p  F  F
− p  T  p − p  T  T

3. Hukum negasi: 4. Hukum idempoten:

− p  ~p  T − p  p  p
− p  ~p  F − p  p  p

5. Hukum involusi (negasi 6. Hukum penyerapan

ganda): (absorpsi):
− ~(~p)  p − p  (p  q)  p
− p  (p  q)  p
28
7. Hukum komutatif: 8. Hukum asosiatif:
− p  q  q  p − p  (q  r)  (p  q)  r
− p  q  q  p − p  (q  r)  (p  q)  r

9. Hukum distributif: 10. Hukum De Morgan:

− p  (q  r)  (p  q)  (p  r) − ~(p  q)  ~p  ~q
− p  (q  r)  (p  q)  (p  r) − ~(p  q)  ~p  ~q

29
 Contoh 9. Tunjukkan bahwa p  ~(p  q) dan p  ~q
keduanya ekivalen secara logika.

Penyelesaian:
p  ~(p  q )  p  (~p  ~q) (Hukum De Morgan)
 (p  ~p)  (p  ~q) (Hukum distributif)
 T  (p  ~q) (Hukum negasi)
 p  ~q (Hukum identitas)

30
Contoh 10. Buktikan hukum penyerapan: p  (p 
q)  p
Penyelesaian:

p  (p  q)  (p  F)  (p  q) (Hukum Identitas)
 p  (F  q) (Hukum distributif)
 pF (Hukum Null)
 p (Hukum Identitas)

31
DISJUNGSI EKSKLUSIF
Kata “atau” (or) dalam operasi logika digunakan
dalam salah satu dari dua cara:

1. Inclusive or
“atau” berarti “p atau q atau keduanya”
Contoh: “Tenaga IT yang dibutuhkan harus
menguasai Bahasa C++ atau Java”.
2. Exclusive or
“atau” berarti “p atau q tetapi bukan
keduanya”.
Contoh: “Ia dihukum 5 tahun atau denda 10
juta”. 32
Operator logika disjungsi eksklusif: xor
Notasi: 

Tabel kebenaran:

p q pq

T T F
T F T
F T T
F F F
33
PROPOSISI BERSYARAT
(KONDISIONAL ATAU IMPLIKASI)
 Bentuk proposisi: “jika p, maka q”
 Notasi: p → q

 Proposisi
p disebut hipotesis,
antesenden, premis, atau kondisi

 Proposisi
q disebut konklusi (atau
konsekuen).
34
Contoh 11.
a. Jika saya lulus ujian, maka saya mendapat
hadiah dari ayah
b. Jika suhu mencapai 80C, maka alarm akan
berbunyi
c. Jika anda tidak mendaftar ulang, maka anda
dianggap mengundurkan diri

35
Cara-cara mengekspresikan implikasi p → q:
 Jika p, maka q
 Jika p, q
 p mengakibatkan q (p implies q)
 q jika p
 p hanya jika q
 p syarat cukup untuk q (hipotesis
menyatakan syarat cukup (sufficient
condition) )
 q syarat perlu untuk p (konklusi
menyatakan syarat perlu (necessary
condition) )
 q bilamana p (q whenever p)
36
Tabel kebenaran implikasi
p q p→q
T T T
T F F
F T T
F F T

37
Penjelasan (dengan contoh)
Dosen: “Jika nilai ujian akhir anda 80 atau lebih, maka anda akan
mendapat nilai A untuk kuliah ini”.
Apakah dosen anda mengatakan kebenaran atau dia berbohong?
Tinjau empat kasus berikut ini:

Kasus 1: Nilai ujian akhir anda di atas 80 (hipotesis benar) dan anda mendapat
nilai A untuk kuliah tersebut(konklusi benar).
 pernyataan dosen benar.
Kasus 2: Nilai ujian akhir anda di atas 80 (hipotesis benar) tetapi anda tidak
mendapat nilai A (konklusi salah).
 dosen berbohong (pernyataannya salah).
Kasus 3: Nilai ujian akhir anda di bawah 80 (hipotesis salah) dan anda
mendapat nilai A (konklusi benar).
 dosen anda tidak dapat dikatakan salah (Mungkin ia melihat
kemampuan anda secara rata-rata bagus sehingga ia tidak ragu
memberi nilai A).
Kasus 4: Nilai ujian akhir anda di bawah 80 (hipotesis salah) dan anda tidak 38
mendapat nilai A (konklusi salah).
 dosen anda benar.
 Perhatikan bahwa dalam implikasi yang
dipentingkan nilai kebenaran premis dan
konsekuen, bukan hubungan sebab dan
akibat diantara keduanya.

 Beberapa
implikasi di bawah ini valid
meskipun secara bahasa tidak mempunyai
makna:

“Jika 1 + 1 = 2 maka Paris ibukota

Perancis”
“Jika n bilangan bulat maka hari ini hujan”
39
• Implikasi Dalam Bahasa Pemrograman
if c then S
c: ekspresi logika yang menyatakan syarat/kondisi
S: satu atau lebih pernyataan.

S dieksekusi jika c benar,

S tidak dieksekusi jika c salah.
• Struktur if-then pada bahasa pemrograman berbeda dengan implikasi if-then
yang digunakan dalam logika.
• Pernyataan if-then dalam bahasa pemrograman bukan proposisi karena tidak
ada korespondensi antara pernyataan tersebut dengan operator implikasi
(→).

• Interpreter atau compiler tidak melakukan penilaian kebenaran pernyataan

if-then secara logika. Interpreter hanya memeriksa kebenaran kondisi c, jika
c benar maka S dieksekusi, sebaliknya jika c salah maka S tidak dieksekusi.
40
Contoh 12. Misalkan di dalam sebuah program yang ditulis
dalam Bahasa Pascal terdapat pernyataan berikut:
if x > y then y:=x+10;
Berapa nilai y setelah pelaksanaan eksekusi if-then jika:
(i) x = 2, y = 1
(ii) x = 3, y = 5?

Penyelesaian:
(i) x = 2 dan y = 1
Ekspresi x > y bernilai benar
Pernyataan y:=x+10 dilaksanakan
Nilai y sekarang menjadi y = 2 + 10 = 12.

(ii) x = 3 dan y = 5
Ekspresi x > y bernilai salah
Pernyataan y:=x+10 tidak dilakukan 41
Nilai y tetap seperti sebelumnya, yaitu 5.
VARIAN PROPOSISI BERSYARAT

Konvers (kebalikan): q→p

Invers : ~p→~q
Kontraposisi : ~q→~p

Implikasi Konvers Invers Kontraposisi

p q ~p ~q p→q q→p ~p→~q ~q→~p
T T F F T T T T
T F F T F T T F
F T T F T F F T
F F T T T T T T

42
Contoh 13. Tentukan konvers, invers, dan
kontraposisi dari:
“Jika Amir mempunyai mobil, maka ia orang kaya”

Penyelesaian:
Konvers : Jika Amir orang kaya, maka ia
mempunyai mobil
Invers : Jika Amir tidak mempunyai mobil,
maka ia bukan orang kaya
Kontraposisi: Jika Amir bukan orang kaya, maka
ia tidak mempunyai mobil

43
BIKONDISIONAL (BI-IMPLIKASI)

• Bentuk proposisi: “p jika dan hanya jika q”

• Notasi: p  q

p q pq
T T T
T F F
F T F
F F T

• p  q  (p → q)  (q → p). 44
p q pq p→q q→p (p → q)  (q → p)

T T T T T T
T F F F T F
F T F T F F
F F T T T T

• Dengan kata lain, pernyataan “p jika dan hanya jika q”

dapat dibaca “Jika p maka q dan jika q maka p”.

45
• Cara-cara menyatakan bikondisional p  q:
(a) p jika dan hanya jika q.
(b) p adalah syarat perlu dan cukup untuk q.
(c) Jika p maka q, dan sebaliknya.
(d) p iff q

46
Contoh 14. Proposisi majemuk berikut adalah bi-
implikasi:
(a) 1 + 1 = 2 jika dan hanya jika 2 + 2 = 4.
(b) Syarat cukup dan syarat perlu agar hari hujan
adalah kelembaban udara tinggi.
(c) Jika anda orang kaya maka anda mempunyai
banyak uang, dan sebaliknya.
(d) Bandung terletak di Jawa Barat iff Jawa Barat
adalah sebuah propinsi di Indonesia.

47
 Bila dua proposisi majemuk yang ekivalen di-
bikondisionalkan, maka hasilnya adalah tautologi.

Teorema:
 Dua buah proposisi majemuk, P(p, q, ..) dan Q(p, q, ..)
disebut ekivalen secara logika, dilambangkan dengan
P(p, q, …)  Q(p, q, …), jika P  Q adalah tautologi.
Tautologi bernilai benar untuk semua pernyataan

48
 Argumen
Argumen adalah suatu deret proposisi yang dituliskan sebagai

p1
p2


pn
 q

yang dalam hal ini, p1, p2, …, pn disebut hipotesis (atau premis),
dan q disebut konklusi.

Argumen ada yang sahih (valid) dan palsu (invalid).

49
Definisi. Sebuah argumen dikatakan sahih jika konklusi
benar bilamana semua hipotesisnya benar; sebaliknya
argumen dikatakan palsu (fallacy atau invalid).

Jika argumen sahih, maka kadang-kadang kita mengatakan

bahwa secara logika konklusi mengikuti hipotesis atau
sama dengan memperlihatkan bahwa implikasi

(p1  p2    pn) → q

adalah benar (yaitu, sebuah tautologi). Argumen yang

palsu menunjukkan proses penalaran yang tidak benar.
50
Contoh 15.
Perlihatkan bahwa argumen berikut:
Jika air laut surut setelah gempa di laut, maka
tsunami datang. Air laut surut setelah gempa di
laut. Karena itu tsunami datang.
adalah sahih.

Penyelesaian:
Misalkan:
p : Air laut surut setelah gempa di laut
q : Tsunami datang:
Argumen:
p→q
p Modus Ponen
 q

Ada dua cara yang dapat digunakan untuk membuktikan kesahihan

argumen ini.
51
Cara 1: Bentuklah tabel kebenaran untuk p, q, dan p → q

p q p→q

T T T (baris 1)
T F F (baris 2)
F T T (baris 3)
F F T (baris 4)

Argumen dikatakan sahih jika semua hipotesisnya benar, maka

konklusinya benar. Kita periksa apabila hipotesis p dan p → q
benar, maka konklusi q juga benar sehingga argumen dikatakan
benar. Periksa tabel, p dan p → q benar secara bersama-sama pada
baris 1. Pada baris 1 ini q juga benar. Jadi, argumen di atas sahih.
52
Cara 2: Perlihatkan dengan tabel kebenaran apakah

[ p  (p → q) ] → q

merupakan tautologi. Tabel 1.16 memperlihatkan bahwa [ p  (p → q) ] → q suatu

tautologi, sehingga argumen dikatakan sahih.

Tabel 1.16 [ p  (p → q) ] → q adalah tautologi

p q p→ q p  (p →q) [ p  (p → q) ] → q

T T T T T
T F F F T
F T T F T
F F T F T

Perhatikanlah bahwa penarikan kesimpulan di dalam argumen ini menggunakan modus

ponen. Jadi, kita kita juga telah memperlihatkan bahwa modus ponen adalah argmen yang
sahih.

53
• Perhatikanlah bahwa meskipun konklusi dari argumen
tersebut kebetulan merupakan pernyataan yang benar (“5
adalah bilangan prima” adalah benar),

• tetapi konklusi dari argumen ini tidak sesuai dengan bukti

bahwa argumen tersebut palsu.

54
BEBERAPA ARGUMEN YANG SUDAH
TERBUKTI SAHIH
1. Modus ponen
p→q
p
---------------
q

2. Modus tollen
p→q
~q
---------------
~p 55
3. Silogisme disjungtif
pq
~p
---------------
q

4. Simplifikasi
pq
---------------
p
56
5. Penjumlahan
p
---------------
pq

6. Konjungsi
p
q
---------------
pq
57
AKSIOMA, TEOREMA, LEMMA, COROLLARY
Aksioma adalah proposisi yang diasumsikan benar.
Aksioma tidak memerlukan pembuktian kebenaran lagi.

Contoh-contoh aksioma:

(a) Untuk semua bilangan real x dan y, berlaku x + y = y +

x (hukum komutatif penjumlahan).
(b) Jika diberikan dua buah titik yang berbeda, maka
hanya ada satu garis lurus yang melalui dua buah titik
tersebut.

Teorema adalah proposisi yang sudah terbukti benar.

58

Bentuk khusus dari teorema adalah lemma dan corolarry.

 Lemma: teorema sederhana yang
digunakan untuk pembuktian teorema lain

 Corollary: teorema yang dapat dibentuk

langsung dari teorema yang telah
dibuktikan.

 atau,
corollary adalah teorema yang
mengikuti teorema lain.

59
Contoh-contoh teorema:

a. Jika dua sisi dari sebuah segitiga sama panjang, maka

sudut yang berlawanan dengan sisi tersebut sama besar.
b. Untuk semua bilangan real x, y, dan z, jika x  y dan y 
z, maka x  z (hukum transitif).

Contoh corollary:

Jika sebuah segitiga adalah sama sisi, maka segitiga

tersebut sama sudut.
Corollary ini mengikuti teorema (a) di atas.

Contoh lemma:

Jika n adalah bilangan bulat positif, maka n – 1 bilangan 60

positif atau n – 1 = 0.
Contoh lainnya (dalam kalkulus)
 Teorema: |x| < a jika dan hanya jika –a <
x < a, dimana a > 0
 Corollary: |x|  a jika dan hanya jika –a 
x  a, dimana a > 0

61