MATEMATIKA DISKRIT
BAB 4 PROPOSISI 1. Pernyataan dan Nilai Kebenaran Ilmu logika adalah berhubungan dengan kalimat-kalimat (argumen-argumen) dan hubungan yang ada diantara kalimat-kalimat tersebut. Tujuannya adalah memberikan aturan-aturan sehingga orang dapat menentukan apakah suatu kalimat bernilai benar. Suatu kalimat deklaratif (Proposisi) adalah kalimat yang bernilai benar atau salah, tetapi tidak keduanya. Beberapa contoh proposisi : a. 2 + 2 = 4 b. 4 adalah bilangan prima c. Jakarta adalah ibukota negara Indonesia d. Penduduk Indonesia berjumlah 50 juta Kalimat-kalimat di atas dapat diketahui benar/salahnya. Kalimat a dan c bernilai benar, sedangkan kalimat b dan d bernilai salah. Beberapa contoh bukan proposisi : a. Dimanakah letak pulau Bali? b. Siapakah namamu? c. Simon lebih tinggi dari Lina d. x + y = 2 Kalimat a dan b jelas bukan proposisi karena merupakan kalimat tanya sehingga tidak dapat ditentukan kebenarannya. Kalimat c juga bukan proposisi karena ada banyak orang di dunia ini yang bernama Simon dan Lina. Dalam kalimat d, nilai kebenaran kalimat tergantung dari harga x dan y. Seringkali, beberapa kalimat perlu digabungkan menjadi satu kalimat yang lebih panjang. Misalnya pada kalimat “4 adalah bilangan genap dan 3 adalah bilangan ganjil” yang merupakan gabungan dari 2 uah kalimat. Dalam logika, dikenal 5 buah penghubung seperti pada tabel berikut :
MATEMATIKA DISKRIT
Tabel 4.1 Simbol ¬ ˄ ˅ → ↔
Arti Tidak / Not / Negasi Dan / And / Konjungsi Atau / Or / Disjungsi Implikasi Bi-Implikasi
Bentuk Tidak … … dan … … atau … Jika … maka … … bila dan hanya bila …
Dalam matematika digunakan huruf-huruf kecil seperti p, q, r, … untuk menyatakan subkalimat dan simbol-simbol penghubung untuk menyatakan penghubung kalimat. Contoh : 1. Misalkan p menyatakan kalimat “4 adalah bilangan genap” dan q menyatakan kalimat “3 adalah bilangan ganjil”. Dengan demikian, kalimat “4 adalah bilangan genap dan 3 adalah bilangan ganjil” dapat dinyatakan dengan simbol p ˄ q 2. Misal : p : hari ini panas q : hari ini cerah Nyatakan kalimat di bawah ini dengan simbol logika : a. Hari ini tidak panas tapi cerah b. Hari ini tidak panas dan tidak cerah c. Tidak benar bahwa hari ini panas dan cerah Penyelesaian : a. ¬p ˄ q b. ¬p ˄ ¬q c. ¬(p ˄ q) Latihan Soal :
1. Misal : p : saya lulus q : ayah akan membelikan sepeda motor Nyatakan kalimat di bawah ini dengan simbol logika : a. Apabila saya lulus, maka ayah akan membelikan sepeda motor b. Saya tidak lulus dan ayah tidak akan membelikan sepeda motor c. Tidak benar saya lulus dan ayah akan membelikan sepeda motor
2. Misal : p : kamu tidak belajar q : kamu tidak akan lulus Nyatakan kalimat di bawah ini dengan simbol logika : a. Apabila kamu tidak belajar, maka kamu tidak akan lulus
MATEMATIKA DISKRIT
b. Apabila kamu belajar, maka kamu akan lulus c. Kamu belajar atau kamu tidak akan lulus
2. Proposisi dan Tabel Kebenaran Jika p maupun q merupakan kalimat, maka tabel kebenaran penghubung tampak pada tabel berikut (T = True/benar; F = False/salah). Perhatikan bahwa secara umum, jika ada n variabel (p, q, …), maka tabel kebenaran memuat 2n baris.
p T T F F
q T F T F
¬p F F T T
Tabel 4.2 p˄q T F F F
p˅q T T T F
p→q T F T T
p↔q T F F T
Negasi suatu kalimat akan memiliki nilai kebenaran yang berlawanan dngan nilai kebenaran kalimat aslinya. Jadi, jika p bernilai benar, maka ¬p bernilai salah. Sebaliknya, jika p bernilai salah, maka ¬p akan bernilai benar. Kalimat p ˄ q akan bernilai benar jika p maupun q bernilai benar jika baik p maupun q bernilai benar. Jika salah satunya (apalagi keduanya) bernilai salah, maka p ˄ q bernilai salah. Kalimat p ˅ q bernilai salah jika baik p maupun q bernilai salah. Jika salah satunya benar, maka p ˅ q bernilai benar. Dalam kalimat implikasi p → q, p disebut hipotesis (anteseden) dan q disebut konklusi (konsekuen). Kalimat p → q disebut kalimat berkondisi karena kebenaran kalimat q tergantung pada kebenaran kalimat p. Kalimat p → q akan bernilai salah bila p benar dan q salah. Kalimat kondisi ganda (biconditional) p ↔ q berarti (p → q) ˄ (q → p). Supaya p ↔ q bernilai benar, maka baik (p → q) maupun (q → p) harus bernilai benar.
p
q
p→q
T T F F
T F T F
T F T T
Tabel 4.3 q→p T T F T
p ↔ q atau (p → q) ˄ (q → p) T F F T
MATEMATIKA DISKRIT
Latihan soal : 1. Misal k : Monde orang kaya S : Monde bersukacita Tulislah bentuk simbolis kalimat-kalimat berikut : a. Monde orang yang miskin tetapi bersukacita b. Monde orang kaya atau ia sedih c. Monde tidak kaya ataupun bersukacita d. Monde seorang yang miskin atau ia kaya tetapi sedih. Anggaplah ingkaran kaya adalah miskin dan ingkaran dari bersukacita adalah sedih. 2. Buatlah tabel kebenaran untuk kalimat dalam bentuk simbol-simbol logika di bawah ini : a. ¬(¬p ˅ ¬q) b. ¬(¬p ↔ q) c. (p → q) ˄ ¬(p ˅ q) 3. Pada kondisi bagaimanakah agar kalimat berikut ini bernilai benar? “Tidaklah benar bila rumah kuno selalu bersalju atau angker, dan tidak juga benar bila sebuah hotel selalu hangat atau rumah kuno selalu rusak”. 4. Jika p dan q benar (T) R dan s salah (F) Tentukan nilai kebenaran kalimat berikut ini a. p ˅ (q ˄ r) b. (p ˄ q ˄ r) ˅ ¬((p ˅ q) ˄ (r ˅ s))
3. Tautologi dan Kontradiksi Tautologi adalah bentuk kalimat yang selalu bernilai benar(T), tidak peduli bagaimanapun nilai kebenaran masing-masing kalimat penyusunnya. Sebaliknya, kontradiksi adalah suatu bentuk kalimat yang selalu bernilai salah (F), tidak peduli bagaimanapun nilai kebenaran masing-masing kalimat penyusunnya. Dalam tabel kebenaran, suatu tautologi selalu bernilai T pada semua barisnya, dan kontradiksi selalu bernilai F pada semua baris. Contoh : Tunjukkan bahwa kalimat berikut adalah tautologi dengan menggunakan tabel kebenaran : (p ˄ q) → q Penyelesaian :
MATEMATIKA DISKRIT
p T T F F
q T F T F
Tabel 4.4 p˄q T F F F
(p ˄ q) → q T T T T
Oleh karena semua baris pada kolom (p ˄ q) → q bernilai T, maka (p ˄ q) → q merupakan tautologi. Latihan Soal : Tunjukkan mana dari kalimat berikut yang merupakan tautologi dan kontradiksi dengan menggunakan tabel kebenaran : 1. q → (p ˅ q) 2. (p → q) ↔ (¬q → ¬p) 3. (¬(p ˅ ¬q) ˅ (¬p ¬q)) ↔ ¬p 4. (p ˄ q) ˅ (¬p ˅ (p ˄ ¬q)) 5. ((¬p ˄ q) ˄ (q ˄ r)) ˄ ¬q
4. Ekuivalen Logika Dua proposisi P (p, q, …) dan Q (p, q, …) disebut ekuivalen jika kedua proposisi tersebut mempunyai tabel kebenaran yang identik, dinotasikan oleh : p (p, q, …) ≡ Q (p, q, …) Contoh : Perhatikan tabel kebenaran ¬(p ˄ q) dan ¬p ˅ ¬q : p q p ˄ q ¬( p ˄ q) T T T F T F F T F T F T F F F T p T T F F
q T F T F
¬p F F T T
¬q F T F T
¬p ˅ ¬q F T T T
MATEMATIKA DISKRIT
Karena tabel kebenaran sama, yakni kedua proposisi salah pada keadaan pertama dan kebenaran pada ketiga keadaan lainnya, maka proposisi ¬(p ˄ q) dan ¬p ˅ ¬q ekivalen dan kita dapat menuliskan ¬(p ˄ q) ≡ ¬p ˅ ¬q Latihan Soal : Tentukan apakah pasangan-pasangan berikut ini ekuivalen 1. ((¬p ˅ q) ˄ (p ˅ ¬r)) ˄ (¬p ˅ ¬q) dengan ¬(p ˅ r) 2. (r ˅ p) ˄ ((¬r ˅ (p ˄ q)) ˄ (r ˅ q)) dengan p ˄ q 3. ¬(p ˄ q) → (¬p ˅ (¬p ˄ q)) dengan ¬p ˅ q
5. Aljabar Proposisi Proposisi memenuhi hukum-hukum pada pada tabel 4.5 Tabel 4.5 Hukum-hukum pada aljabar proposisi 1. Hukum Komutatif 2. Hukum Asosiatif 3. Hukum Distributif 4. Hukum Identitas 5. Hukum Ikatan 6. HukumNegasi 7. Hukum Negasi ganda 8. Hukum Idempoten 9. Hukum De Morgan 10. Hukum Absorbsi 11. Negasi T dan F
p˄q↔q˅p (p ˄ q) ˄ r ↔ p ˄ (q ˄ r) p˄ (q˅r) ↔ (p˄q) ˅ (p˄r) p˄ T↔p p˅T↔T p ˅ ¬p ↔ T ¬(¬p) ↔ p p ˄ p ↔p ¬(p ˄ q) ↔ ¬p ˅ ¬q p ˅ (p ˄ q) ↔ p ¬T ↔ F
p˅q↔q˅p (p ˅ q) ˅ r ↔ p ˅ (q ˅ r) p˅ (q˄r) ↔ (p˅q) ˄ (p˅r) p˅F↔p p˄F↔F p ˄ ¬p ↔ F
Contoh : Sederhanakan bentuk ¬(¬p ˄ q) ˄ (p ˅ q) Penyelesaian : ¬(¬p ˄ q) ˄ (p ˅ q) ↔ (¬(¬p)˅¬q) ˄ (p ˅ q) (hukum de morgan) ↔ (p ˅ ¬q) ˄ (p ˅ q) (hukum negasi ganda) ↔ p ˅ (¬q ˄ q) (hukum distributif) ↔p˅F (hukum negasi) ↔p (hukum identitas)
p˅p↔p ¬(p ˅ q) ↔ ¬p ˄ ¬q p ˄ (p ˅ q) ↔ p ¬F ↔ T
MATEMATIKA DISKRIT
Latihan Soal : Sederhanakan bentuk-bentuk berikut : 1. ¬(p ˅ ¬q) ˅ (¬p ˄ ¬q) 2. ¬((¬p ˄ q) ˅ (¬p ˄ ¬q)) ˅ (p ˄ q) 3. (p ˄ (¬(¬p ˅ q))) ˅ (p ˄ q)
6. Argumen dan Proposisi Argumen adalah rangkaian kalimat. Semua kalimat tersebut, kecuali yang terakhir, disebut Hipotesis (atau asumsi/premise). Kalimat terakhir disebut Kesimpulan. Secara umum, hipotesis dan kesimpulan dapat digambarkan sebagai berikut : } hipotesa } kesimpulan Tanda dibaca “jadi q” Suatu argumen dikatakan valid apabila untuk sembarang pernyataan yang disubstitusikan ke dalam hipotesis, jika semua hipotesis tersebut benar. Sebaliknya, meskipun semua hipoesis tersebut benar, kesimpulan juga benar, tetapi ada kesimpulan yang salah, maka argumen tersebutdikatakan invalid. Jika suatu argumen dan semua hipotesisnyabernilai benar,, maka kebenaran nilai konklusi dikatakan sebagai ”diinferensikan (diturunkan dari kebenaran hipotesis”. Untuk mengecek apakah suatu argumen merupakan kalimat yang valid, dapat dilakukan langkah-langkah sebagai berikut : 1. Tentukan hipotesis dan kesimpulan kalimat. 2. Buat tabel yang menunjukkan nilai kebenaran untuk semua hipotesis dan kesimpulan. 3. Carilah baris kritis, yaitu baris dimana semua hipotesis bernilai benar. 4. Dalam baris kritis tersebut, jika semua nilai kesimpulan benar, maka argumen itu valid. Jika diantara baris kritis tersebut ada baris dengan nilai kesimpulan yang salah, maka kesimpulan tersebut adalah invalid.
MATEMATIKA DISKRIT
Contoh : 1. p ˅ (q ˅ r) ¬r p˅q Penyelesaian : Terdapat 2 hipotesis, masing-masing p ˅ (q ˅ r) dan ¬r. Kesimpulannya adalah p ˅ q. Tabel kebenaran hipotesis-hipotesis dan kesimpulan tampak pada tabel 4.6. Tabel 4.6 Baris ke p q r q˅r p˅(q˅r) ¬r p˅q 1 T T T T T F T 2 T T F T T T T 3 T F T T T F T 4 T F F F T T T 5 F T T T T F T 6 F T F T T T T 7 F F T T T F F 8 F F F F F T F Baris kritis adalah baris 2, 4, dan 6 (baris yang semua hipotesisnya bernilai T, ditandai dengan arsiran). Pada baris-baris tersebut, kesimpulannya juga bernilai T. Dengan demikian argumen tersebut valid. 2. p → (q ˅ ¬r) q → (p ˄ r) p→r Penyelesaian : Hipotesisnya adalah p → (q ˅ ¬r) dan q → (p ˄ r). Konklusinya adalah p → r Tabel 4.7 Baris ke p q r ¬r q˅¬r p˄r p→(q˅¬r) q→(p˄r) p → r 1 T T T F T T T T T 2 T T F T T F T F F 3 T F T F F T F T T 4 T F F T T F T T F 5 F T T F T F T F T 6 F T F T T F T F T 7 F F T F F F T T T 8 F F F T T F T T T
MATEMATIKA DISKRIT
Baris kritis adalah baris 1, 4, 7, dan 8 (baris yang semua hipotesisnya bernilai T, ditandai dengan arsiran). Pada baris ke- 4 (baris kritis) nilai konklusinya adalah F. Dengan demikian argumen tersebut invalid. Latihan Soal : 1. p → q q→p p˅q 2. p ˅ q p → ¬q p→r r 3. p ˄ ¬q →r p˅q q→p r
