Matematika Diskrit : Logika Proposisi

Logika

Ilmu logika berhubungan dengan kalimat-kalimat (argumen-argumen) dan hubungan yang ada di antara kalimat-kalimat tersebut.

Hukum-hukum logika membantu kita membedakan antara argumen yang valid dan tidak valid. Logika juga digunakan untuk membuktikan teorema-teorema di dalam matematika.

Dalam ilmu komputer, logika diaplikasikan dalam bidang pemrograman, analisis kebenaran algoritma, kecerdasan buatan, perancangan komputer, dan sebagainya.


Proposisi

Proposisi (proposition) adalah kalimat deklaratif yang bernilai benar (true) atau salah (false), tetapi tidak dapat sekaligus keduanya. Kebenaran atau kesalahan dari sebuah kalimat disebut nilai kebenaran (truth value).

Secara simbolik, proposisi biasanya dilambangkan dengan huruf kecil seperti p, q, r, โ€ฆ.

Misalnya :
p : 6 adalah bilangan genap.
q : Jakarta adalah ibukota Indonesia.
r : 1 + 1 = 2


Contoh 1

Tentukan nilai dari proposisi di bawah ini:

a) Soekarno adalah Presiden Indonesia yang pertama.

b) Ibukota Provinsi Jawa Barat adalah Semarang.

c) 2 + 2 = 4

d) 25 + 2 = 26

Penyelesaian

Proposisi a) dan proposisi c) bernilai true, sedangkan proposisi b) dan proposisi d) bernilai false.


Contoh 2

Tentukan apakah proposisi atau tidak

a) Siapakah namamu?

b) Serahkan uangmu sekarang!

c) x + 3 = 8

d) x > 3

Penyelesaian

Kalimat a) dan kalimat b) masing-masing bukan pernyataan, jadi keduanya bukan proposisi. Kalimat c) merupakan pernyataan tetapi bukan suatu proposisi, karena variabel x dalam kalimat tersebut belum ada nilainya, jadi masih dapat bernilai true (bila x bernilai 5) juga dapat bernilai false (bila x โ‰  5). Begitu pula dengan kalimat (d).


Operator Logika

Operator yang digunakan untuk mengkombinasikan proposisi disebut operator logika atau penghubung logika (logical connectives).

Proposisi baru yang diperoleh dari pengkombinasian tersebut dinamakan proposisi majemuk (compound proposition). Proposisi yang bukan merupakan kombinasi proposisi lain disebut proposisi atomik.


Operator Negasi ยฌ

Jika p adalah sebuah proposisi, maka ยฌp adalah sebuah proposisi pula. ยฌp disebut negasi (negation) dari p, atau tidak p (not p).

Nilai kebenaran dari ยฌp adalah true bila p bernilai false, dan bernilai false bila p bernilai true.

Hubungan antara nilai kebenaran dari p dan negasinya ยฌp dapat pula dinyatakan dalam suatu tabel yang disebut Tabel Kebenaran.

pยฌp
TF
FT
Tabel Kebenaran untuk Negasi dari p

Contoh:

(a) Negasi proposisi โ€œJakarta adalah ibu kota Indonesiaโ€ adalah โ€œJakarta bukan ibu kota Indonesiaโ€ atau โ€œTidak benar bahwa Jakarta adalah ibu kota Indonesiaโ€.

(b) Jika p mewakili proposisi โ€œLuas ruang kuliah ini lebih dari 16 m2โ€,
maka ยฌp mewakili proposisi โ€œLuas ruang kuliah ini kurang dari atau sama dengan 16 m2โ€ atau
โ€œTidak benar bahwa luas ruang kuliah ini lebih dari 16 m2โ€.


Operator Konjungsi โˆง

Jika p dan q adalah proposisi maka โ€œp dan qโ€ atau p โˆง q adalah sebuah proposisi pula, yang disebut sebagai konjungsi (conjunction) dari p dan q.

Dan nilai kebenaran dari p โˆง q adalah true pada saat p dan q kedua-duanya bernilai true, dan false bila salah satu atau kedua-duanya dari p dan q bernilai false.

pqp โˆง q
TTT
TFF
FTF
FFF
Tabel Kebenaran untuk Konjungsi dari p dan q

Contoh

Jika

p : Hari ini adalah hari Selasa.

q : Hari ini hujan.

Maka

p โˆง q : Hari ini adalah hari Selasa dan hari ini hujan
atau
Hari ini adalah hari Selasa dan hujan

p โˆง q bernilai T hanya pada hari Selasa yang hujan, dan bernilai F pada hari lainnya atau pada hari Selasa yang tidak hujan.


Operator Disjungsi โˆจ

Jika p dan q adalah proposisi maka โ€œp atau qโ€ atau p โˆจ q adalah sebuah proposisi pula, yang disebut sebagai disjungsi (disjunction) dari p dan q.

Dan nilai kebenaran dari p โˆจ q adalah false pada saat p dan q kedua-duanya bernilai false, dan true bila salah satu atau kedua-duanya dari p dan q bernilai true.

pqp โˆจ q
TTT
TFT
FTT
FFF
Tabel Kebenaran untuk Disjungsi dari p dan q

Contoh

Jika

p : Hari ini adalah hari Selasa

q : Hari ini hujan

Maka p โˆจ q : Hari ini adalah hari Selasa atau hari ini hujan p โˆจ q bernilai F apabila harinya bukan hari Selasa dan pada hari itu tidak hujan, dan bernilai T apabila harinya adalah hari Selasa atau apabila harinya hujan.


Operator Exclusice Or โŠ•

Jika p dan q adalah proposisi maka exclusive or dari p dan q atau p โŠ• q adalah sebuah proposisi pula.

Nilai kebenaran dari p โŠ• q adalah true pada saat p dan q memiliki nilai kebenaran yang berbeda, dan false bila p dan q memiliki nilai kebenaran yang sama.

pqp โŠ• q
TTF
TFT
FTT
FFF
Tabel Kebenaran untuk Exclusive or dari p dan q

Contoh

Jika

p : Hari ini adalah hari Selasa

q : Hari ini hujan

Maka

p โŠ• q : Hari ini adalah hari Selasa yang tidak hujan atau hari ini bukan hari Selasa tetapi hujan.

p โŠ• q bernilai F pada setiap hari Selasa yang hujan atau pada hari-hari bukan hari Selasa yang tidak hujan, dan bernilai T pada hari Selasa yang tidak hujan atau pada hari lainnya yang hujan.


Operator Implikasi โ†’

Jika p dan q adalah proposisi maka Implikasi (Implication) p โ†’ q, dibaca โ€œJika p maka qโ€œ, adalah sebuah proposisi pula.

p disebut hipotesa atau antecedent atau premise, q disebut konklusi (conclusion) atau konsekuensi (consequence).

Dan nilai kebenaran dari p โ†’ q adalah false hanya pada saat p bernilai true dan q bernilai false, selainnya p โ†’ q akan bernilai true.

pqp โ†’ q
TTT
TFF
FTT
FFT
Tabel Kebenaran untuk Implikasi dari p dan q

Contoh

Jika

p : Hari ini adalah hari Selasa
q : Hari ini hujan

maka

p โ†’ q : Jika hari ini adalah hari Selasa maka hari ini hujan.
p โ†’ q bernilai F hanya pada hari Selasa yang tidak hujan, dan bernilai T pada hari Selasa yang hujan atau pada hari yang bukan hari Selasa.

โ€œJika p maka qโ€œ dapat pula dikatakan sebagai โ€œp mengakibatkan qโ€
atau โ€œp hanya jika qโ€
atau โ€œp adalah syarat cukup untuk qโ€
atau โ€œq jika pโ€
atau โ€œq apabila pโ€
atau โ€œq adalah syarat perlu untuk pโ€.


Operator Bi-implikasi (Biconditional)

Jika p dan q adalah proposisi maka biconditional p โ†” q juga sebuah proposisi, dibaca โ€œp jika dan hanya jika qโ€œ, atau โ€œp adalah syarat perlu dan cukup untuk qโ€.

Dan nilai kebenaran dari p โ†” q adalah true pada saat p dan q memiliki nilai kebenaran yang sama, dan false bila p dan q memiliki nilai kebenaran yang berbeda.

pqp โ†” q
TTT
TFF
FTF
FFT
Tabel Kebenaran untuk Bi-implikasi dari p dan q

Contoh

Jika

p : Hari ini adalah hari Selasa
q : Hari ini hujan

maka

p โ†” q : Hari ini adalah hari Selasa jika dan hanya jika hari ini hujan, atau Hari ini adalah hari Selasa adalah syarat perlu dan cukup agar hari ini hujan.

p โ†” q bernilai F hanya pada hari Selasa yang tidak hujan atau hari lain yang hujan, dan bernilai T pada hari Selasa yang hujan atau pada hari lain yang tidak hujan.


Tabel Kebenaran

Nilai kebenaran dari proposisi majemuk ditentukan oleh nilai kebenaran dari proposisi atomiknya dan cara mereka dihubungkan oleh operator logika.

Satu cara praktis untuk menentukan nilai kebenaran proposisi majemuk adalah menggunakan tabel kebenaran (truth table).

Tabel kebenaran menampilkan hubungan antara nilai kebenaran dari proposisi atomik.

Contoh 1

Bentuklah tabel kebenaran dari ekspresi logika p โˆจ ยฌ(p โˆง q)

pqp โˆง qยฌ(p โˆง q)p โˆจยฌ(p โˆง q)
TTTFT
TFFTT
FTFTT
FFFTT

Contoh 2

pqp โˆง qp โˆจ qยฌ(p โˆจ q)(p โˆง q) โˆง ยฌ(p โˆจ q)
TTTTFF
TFFTFF
FTFTFF
FFFFTF

Contoh 3

pqrp โˆง qยฌqยฌq โˆง r(p โˆง q) โˆจ (ยฌq โˆง r)
TTTTFFT
TTFTFFT
TFTFTTT
TFFFTFF
FTTFFFF
FTFFFFF
FFTFTTT
FFFFTFF

Definisi Valid, Terpenuhi, dan Kontradiksi

Sebuah proposisi majemuk disebut absah/valid/tautologi jika bernilai true untuk semua baris pada tabel kebenaran, tidak peduli bagaimana pun nilai kebenaran masing-masing kalimat
penyusunnya.

Sebuah proposisi majemuk disebut terpenuhi/satisfiable jika terdapat nilai true pada pada tabel kebenaran.
Sebuah proposisi majemuk disebut kontradiksi (contradictory/unsatisfiable) jika bernilai false untuk semua baris pada tabel kebenaran.

Contoh 1 adalah suatu proposisi yang valid/tautologi.
Contoh 2 adalah suatu proposisi yang contradictory.
Contoh 3 adalah suatu proposisi yang satisfiable.


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Matematika Diskrit – Logika, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up