KONSEP DAN NOTASI DASAR PROPOSISI
Proposisi
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).
Proposisi adalah kalimat deklaratif yang bernilai benar (
true) atau salah (
false), tetapi tidak dapat sekaligus keduanya. Kebenaran atau kesalahan dari sebuah kalimat disebut nilai kebenarannya (
truth value).
Contoh berikut ini dapat mengilustrasikan kalimat yang merupakan proposisi dan mana yang bukan.
Contoh 1.1
a) 6 adalah bilangan genap
b) Soekarno adalah Presiden Indonesia yang pertama
c) 2 + 2 = 4
d) Ibukota Provinsi Jawa Barat adalah Semarang
e) 12 ≥ 19
f) Kemarin hari hujan
g) Suhu di permukaan laut adalah 21 derajat celcius
h) Pemuda itu tinggi
i) Kehidupan hanya ada di Planet Bumi
Semuanya merupakan proposisi. Proposisi a, b, c bernilai benar,
tetapi proposisi d salah karena ibukota Jawa Barat seharusnya Bandung
dan proposisi e bernilai salah karena seharusnya 12 ≤ 19. Proposisi f
sampai I memang tidak dapat langsung ditetapkan kebenarannya, namun satu
hal yang pasti, proposisi-proposisi tersebut tidak mungkin benar dan
salah sekaligus. Kita bisa menetapkan nilai proposisi tersebut benar
atau salah. Misalnya, proposisi f bias kita andaikan benar (hari kemarin
memang hujan) atau salah (hari kemarin tidak hujan). Demikian pula
halnya untuk proposisi g dan h. Proposisi i bias benar atau salah,
karena sampai saat ini belum ada ilmuwan yang dapat memastikan
kebenarannya.
Contoh 1.2
a) Jam berapa kereta api Argo Bromo tiba di Gambir?
b) Serahkan uangmu sekarang!
c) x + 3 = 8
d) x > 3
bukan proposisi. Kalimat a adalah kalimat Tanya, sedangkan kalimat b
adalah kalimat perintah, keduanya tidak mempunyai nilai kebenaran. Dari
contoh 1.1 dan 1.2 di atas, dapat disimpulkan bahwa proposisi selalu
dinyatakan sebagai kalimat berita, bukan sebagai kalimat Tanya maupun
kalimat perintah. Kalimat c dan d bukan proposisi karena kedua kalimat
tersebut tidak dapat ditentukan benar maupun salah sebab keduanya
mengandung peubah (variable) yang tidak dispesifikasikan nilainya.
Tetapi kalimat
“Untuk sembarang bilangan bulat
n ≥ 0, maka 2
n adalah bilangan genap”
Bidang logika yang membahas proposisi dinamakan
kalkulus proposisi(
propositional calculus) atau
logika proposisi (
propositional logic).
Secara simbolik, proposisi biasanya dilambangkan dengan huruf kecil seperti
p,
q,
r, …. misalnya,
p: 6 adalah bilangan genap,
Untuk mendefinisikan p sebagai proposisi “6 adalah bilangan genap”. Begitu juga untuk
q : soekarno adalah Presiden Indonesia yang pertama.
r : 2 + 2 = 4.
dan sebagainya.
Mengkombinasikan 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
binerkarena operator tersebut mengoperasikan dua buah proposisi, sedangkan operator ketiga dinamakan operator
uner karena ia hanya membutuhkan satu buah proposisi.
Proposisi baru yang diperoleh dari pengkombinasian tersebut dinamakan
proposisi majemuk (
compound proposition). proposisi yang bukan merupakan kombinasi proposisi lain disebut
proposisi atomik. Proposisi majemuk ada tiga macam, yaitu konjungsi, disjungsi, dan ingkaran. Ketiganyadidefinisikan sebagai berikut:
DEFINISI. Misalkan dan adalah proposisi. Konjungsi (
conjunction) dan , dinyatakan dengan notasi , adalah proposisi
p dan
Disjungsi (
disjunction) dan , dinyatakan dengan notasi , adalah proposisi
p atau
Ingkaran atau (
negation) dari , dinyatakan dengan
p, adalah proposisi tidak
p
Catatan:
- Beberapa literatur menggunakan notasi “p”, ””, atau ”not p” untuk menyatakan lingkaran.
- Kata “tidak” dapat dituliskan di tengah pernyataan. Jika kata
“tidak” diberikan di awal pernyataan maka ia biasanya disambungkan
dengan kata “benar” menjadi “tidak benar”. Kata “tidak” dapat juga
diganti dengan “bukan” bergantung dengan rasa bahasa yang tepat untuk
pernyataan tersebut.
Berikut contoh-contoh proposisi majemuk dan notasi simboliknya.
Ekspresi proposisi majemuk dalam notasi simbolik disebut juga ekspresi
logika.
Contoh 1.2
Diketahui proposisi-proposisi berikut:
p: Hari ini hujan
q : Murid-murid diliburkan dari sekolah
Maka
pq : Hari ini hujan dan murid-murid diliburkan dari sekolah
pq : Hari ini hujan atau murid-murid diliburkan dari sekolah
p : Tidak benar hari ini hujan (atau dalam kalimat lain yang lebih lazim: Hari ini tidak hujan)
Tabel Kebenaran
Nilai kebenaran dari proposisi majemuk ditentukan oleh nilai
kebenaran dari proposisi atomiknya dan cara mereka dihubungkan oleh
operator logika.
- Misalkan p dan q adalah proposisi.
- Konjungsi p ^ q bernilai benar jika p dan q keduanya benar, selain itu nilainya salah
- Disjungsi p v q bernilai salah jika p dan q keduanya salah, selain itu nilainya benar
- Negasi p, yaitu ~p, bernilai benar jika p salah, dan sebaliknya
Misalkan
p: 17 adalah bilangan prima
q: bilangan prima selalu ganjil
jelas bahwa
p bernilai benar dan
q bernilai salah sehingga konjungsi
p ^
q: 17 adalah bilangan prima dan bilangan prima selalu ganjil adalah salah.
Satu cara yang praktis untuk menentukan nilai kebenaran proposisi
majemuk adalah menggunakan tabel kebenaran. Tabel kebenaran menampilkan
hubungan antara nilai kebenaran dari proposisi atomik. Tabel 1.1
menunjukkan tabel kebenaran untuk konjungsi, disjungsi, dan ingkaran.
Pada tabel tersebut, T=
true(benar), dan F=
false(salah).
Tabel 1.1 Tabel kebenaran konjungsi, disjungsi, dan ingkaran
p |
q |
p ^ q |
T |
T |
T |
T |
F |
F |
F |
T |
F |
F |
F |
F |
p |
q |
p v q |
T |
T |
T |
T |
F |
T |
F |
T |
T |
F |
F |
F |
Contoh soal: Jika
p, q, radalah proposisi. Bentuklah tabel kebenaran dari ekspresi logika
(p ^ q) v (~q ^ r)
Penyelesaian:
Ada 3 buah proposisi atomic di dalam ekspresi logika dan setiap
proposisi hanya mempunyai 2 kemungkinan nilai, sehingga jumlah kombinasi
dari semu proposisi tersebut adalah buah. Tabel kebenaran dari
proposisi (p ^ q) v (~q ^ r) ditunjukkan pada tabel 1.2.
Tabel 1.2 tabel kebenaran proposisi (p ^ q) v (~q ^ r)
p |
q |
r |
p ^ q |
~q |
~q ^ r |
(p ^ q) v (~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 |
Proposisi majemuk dapat selalu bernilai benar untuk berbagai
kemungkinan nilai kebenaran masing-masing proposisi atomiknya, atau
selalu bernilai salah untuk berbagai kemungkinan nilai kebenaran
masing-masing proposisi atomiknya. Jadi, sebuah proposisi majemuk
disebut
tautologi jika ia benar untuk semua kasus, sebaliknya disebut
kontradiksi jika ia salah untuk semua kasus.
Yang dimaksud dengan “semua kasus” di dalam definisi si atas adalah
semua kemungkinan nilai kebenaran dari proposisi atomiknya. Proposisi
tautologi dicirikan pada kolom terakhir pada tabel kebenarannya hanya
memuat
True. Proposisi kontradiksi dicirikan pada kolom terakhir pada tabel kebenarannya hanya memuat
False.
Hukum – Hukum Proposisi
Proposisi, dalam kerangka hubungan ekivalen logika, memenuhi
sifat-sifat yang dinyatakan dalam sejumlah hukum pada tabel di
bawah.Beberapa hukum tersebut mirip dengan hukum aljabar pada system
bilangan riil, misalnya a(b + c) = ab + ac, yaitu hukum distributif,
sehingga kadang-kadang hukum logika proposisi dinamakan juga
hukum-hukum aljabar proposisi.
- 1. Hukum identitas
i. p v F ó p
ii. p ^ T ó p |
- 2. Hukum null dominasi
i. p ^ F ó F
ii. p v T ó T |
- 3. Hukum negasi
i. p v ~p ó T
ii. p ^ ~p ó F |
- Hukum idempotent
i. p v p ó p
ii. p ^ p ó p |
- 5. Hukum involusi
~(~p) ó p |
- Hukum penyerapan
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 ^ p |
- Hukum assosiatif
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) v (p ^ r) |
10. Hikum de morgan
i. ~(p ^ q) ó ~p v ~q
ii. ~(p v q) ó ~p ^ ~q |
Hukum-hukum logika di atas bermanfaat untuk membuktikan ke-ekivalenan
dua buah proposisi. Selain menggunakan tabel kebenaran, ke-ekivalenan
dapat dibuktikan dengan hukum-hukum logika, khususnya pada proposisi
majemuk yang mempunyai banyak proposisi atomik. Bila suatu proposisi
majemuk mempunyai n buah proposisi atomic, maka table kebenarannya
terdiri dari baris. Untuk
n yang besar jelas tidak praktis menggunakan tabel kebenaran, misalnya untuk
n=10 terdapat baris di dalam tabel kebenarannya.
Implikasi
Adalah suatu pernyataan majemuk p dan q yang digabung dengan memakai kata hubung logika “jika…maka…”.
Implikasi suatu pernyataan dilambangkan dengan p→q. Dibaca :
- Jika p maka q
- p berimplikasi q
- q hanya jika p
- p syarat cukup untuk q
- q syarat perlu untuk p
Pada implikasi, p disebut anteseden (hipotesis), q disebut konklusi (kesimpulan).
Nilai kebenaran: untuk p→q bernilai salah hanya berlaku untuk p pernyataan bernilai benar dan q pernyataan bernilai salah.
p |
q |
p→q≡¬pVq |
B |
B |
B |
B |
S |
S |
S |
B |
B |
S |
S |
B |
Implikasi Logis
“jika Andi rajin belajar maka Andi naik kelas”
Jika pada kenyataannya Andi rajin belajar maka sebagai konskuensi logis dari pernyataan di atas pasti Andi naik kelas.
Misal p: Andi rajin belajar
q: Andi naik kelas
maka ((p→q)∧p)→q, nilainya akan selalu benar.
p |
q |
p→q |
((p→q)∧p) |
((p→q)∧p)→q |
B |
B |
B |
B |
B |
B |
S |
S |
S |
B |
S |
B |
B |
S |
B |
S |
S |
B |
S |
B |
TAUTOLOGI
Tautologi adalah pernyataan majemuk yang
selalu benar untuk
semua kemungkinan nilai kebenaran dari pernyataan-pernyataan
komponennya. Sebuah Tautologi yang memuat pernyataan Implikasi disebut
Implikasi Logis. Untuk membuktikan apakah suatu pernyataan Tautologi,
maka ada dua cara yang digunakan. Cara pertama dengan menggunakan tabel
kebenaran, yaitu jika semua pilihan bernilai B (benar) maka disebut
Tautologi, dan cara kedua yaitu dengan melakukan penjabaran atau
penurunan dengan menerapkan sebagian dari 12 hukum-hukum Ekuivalensi
Logika.
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 kulah.
Diubah ke variabel proposional:
A Tono pergi kuliah
B Tini pergi kuliah
C Siska tidur
Diubah lagi menjadi ekspresi logika yang terdiri dari premis-premis
dan kesimpilan. Ekspresi logika 1 dan 2 adalah premis-premis, sedangkan
ekspresi logika 3 adalah kesimpulan.
(1) A → B (Premis)
(2) C → B (premis)
(3) (A V C) → B (kesimpulan)
Maka sekarang dapat ditulis: ((A → B) ʌ (C → B)) → ((A V C) → B
A |
B |
C |
A → B |
C → B |
(A → B) ʌ (C → B) |
A V C |
(A V C) → B |
B
B
B
B
S
S
S
S |
B
B
S
S
B
B
S
S |
B
S
B
S
B
S
B
S |
B
B
S
S
B
B
B
B |
B
B
S
B
B
B
S
B |
B
B
S
S
B
B
S
B |
B
B
B
B
B
S
B
S |
B
B
S
S
B
B
S
B |
B
B
B
B
B
B
BB |
Dari tabel kebenaran diatas menunjukkan bahwa pernyataan majemuk :
((A → B) ʌ (C → B)) → ((A V C) → B adalah
semua benar (Tautologi).
Contoh tautologi dengan menggunakan tabel kebenaran:
- (p ʌ ~q) p
Pembahasan:
p |
q |
~q |
(p ʌ ~q) |
(p ʌ ~q) p |
B
B
S
S |
B
S
B
S |
S
B
S
B |
S
B
S
S |
B
B
B
B |
Ini adalah tabel kebenaran yang menunjukkan Tautologi dengan alasan
yaitu semua pernyataannya bersifat benar atau True (T). maka dengan
perkataan lain pernyataan majemuk (p ʌ ~q) p
selalu benar.
- [(p q) ʌ p] p q
Pembahasan:
p |
q |
(p q) |
(p q) ʌ p |
[(p q) ʌ p] p q |
B
B
S
S |
B
S
B
S |
B
S
B
B |
B
S
S
S |
B
B
B
B |
(1) (2) (3) (4) (5)
Berdasrkan tabel diatas pada kolom 5, nilai kebenaran pernyataan
majemuk itu adalah BBBB. Dengan perkataan lain, pernyataan
majemuk [(p q) ʌ p] p q
selalu benar
Pembuktian dengan cara kedua yaitu dengan penjabaran atau penurunan
dengan menerapkan sebagian dari 12 hukum-hukum ekuivalensi logika.
Contoh:
- (p ʌ q) q
Penyelesaian:
(p ʌ q) q ~(p ʌ q) v q
~p v ~q v q
~p v T
T ………….(Tautologi)
Dari pembuktian diatas telah nampaklah bahwa pernyataan majemuk dari
(p ʌ q) q adalah tautologi karena hasilnya T (true) atau benar.
Pembuktian dengan menggunakan tabel kebenaran dari pernyataan majemuk (p ʌ q) q yaitu:
P |
q |
(p ʌ q) |
(p ʌ q) q |
B
B
S
S |
B
S
B
S |
B
S
S
S |
B
B
B
T |
Pada tabel diatas nampaklah bahwa kalimat majemuk (p ʌ q) q merupakan Tautologi.
- q (p v q)
penyelesaian:
q (p v q) ~q v (p v q)
~q v (q v p)
T v p
T …………(Tautologi)
- KONTRADIKSI
Kontradiksi adalah kebalikan dari tautologi yaitu suatu bentuk
pernyataan yang hanya mempunyai contoh substansi yang salah, atau sebuah
pernyataan majemuk yang salah dalam segala hal tanpa memandang nilai
kebenaran dari komponen-komponennya. Untuk membuktikan apakah suatu
pernyataan tersebut kontradiksi, maka ada dua cara yang digunakan. Cara
pertama dengan menggunakan tabel kebenaran, yaitu jika semua pilihan
bernilai F atau salah maka disebut kontradiksi, dan cara kedua yaitu
dengan melakukan penjabaran atau penurunan dengan menerapkan sebagian
dari 12 hukum-hukum Ekuivalensi Logika.
Contoh dari Kontradiksi:
- (A ʌ ~A)
Pembahasan:
A |
~A |
(A ʌ ~A) |
B
S |
S
B |
S
S |
Dari tabel kebenaran diatas dapatlah disimpulkan bahwa pernyataan majemuk (A ʌ ~A)
selalu salah.
- P ʌ (~p ʌ q)
Pembahasan:
p |
q |
~p |
(~p ʌ q) |
P ʌ (~p ʌ q) |
B
B
S
S |
B
S
B
S |
S
S
B
B |
S
S
B
S |
S
S
S
S |
Ini adalah tabel kebenaran yang menunjukkan kontradiksi dengan alasan yaitu semua pernyataan bernilai salah (F).
- Ekuivalensi Logika
Dua atau lebih pernyataan majemuk yang mempunyai nilai kebenaran sama
disebut ekuivalensi logika dengan notasi “ dua buah pernyataan majemuk
dikatakan ekuivalen, jika kedua pernyataan majemuk itu mempunyai nilai
kebenaran yang sama untuk semua kemungkinan nilai kebenaran
pernyataan-pernyataan komponen-komponennya.
Hukum-Hukum Ekuivalensi Logika:
- Hukum komutatif:
p ʌ q q ʌ p
p v q q v p
- Hukum asosiatif:
(p ʌ q) ʌ r p ʌ (q ʌ r)
(p v q) v r p v (q v r)
- Hukum distributif:
p ʌ (q v r) (p ʌ q) v (p ʌ r)
p v (q ʌ r) (p v q) ʌ (p v r)
- Hukum identitas:
p ʌ T p
p v F p
- Hukum ikatan (dominasi):
P v T T
P v F F
- Hukum negasi:
P v ~p T
P ʌ ~p F
- Hukum negasi ganda (involusi):
~(~p) p
- Hukum idempoten:
P ʌ p p
p v p p
- Hukum de morgan:
~( p ʌ q) ~p v ~q
~(p v q) ~p ʌ ~q
- Hukum penyerapan (absorpsi):
p v (P ʌ q) p
P ʌ (p v q) p
- Hukum T dan F:
~T F
~F T
- Hukum implikasi ke and/or:
P q ~p v q
Dengan adanya hukum-hukum diatas, penyelesaian soal-soal baik yang
bersifat tautologi, kontradiksi dan ekuivalensi logika tidak hanya
menggunakan tabel kebenaran namun juga bisa dengan menggunakan jalan
penurunan yaitu dengan memanfaatkan 12 (dua belas) hukum-hukum
ekuivalensi logika tersebut.
Dengan menggunakan prinsip-prinsip di atas, maka kalimat-kalimat yang kompleks dapat disederhanakan, seperti contoh berikut:
- Buktikan ekuivalensi berikut: ~(p v ~q) v (~p ʌ ~q) ~p
Jawab:
~(p v ~q) v (~p ʌ ~q) (~p ʌ q) v (~p ʌ ~q)
~p ʌ (q v ~q)
~p ʌ T
~p ………..(terbukti)
- Tunjukkan bahwa: ~(p v q) (~p ʌ ~q)
Tabel kebenaran ~(p v q) dan (~p ʌ ~q) yaitu:
p |
q |
~p |
~q |
p v q |
~(p v q) |
(~p ʌ ~q) |
B
B
S
S |
B
S
B
S |
S
S
B
B |
S
B
S
B |
B
B
B
S |
S
S
S
B |
S
S
S
B |
(1) (2) (3) (4) (5) (6) (7)
Dari tabel diatas pada kolom ke(6) dan (7), jelas bahwa ~(p v q) (~p ʌ ~q).
Jadi, ~(p v q) (~p ʌ ~q).
Sumber :
http://dedekyohana93.blogspot.com/2012/11/tautologi-kontradiksi-dan-ekuivalensi_4667.html
Munir, Rinaldi,
Matematika Diskrit, Informatika, 2005