PERTEMUAN 2 TABEL KEBENARAN DADANG MULYANA
TABEL KEBENARAN (TB) digunakan untuk menyajikan hubungan antara nilai kebenaran sejumlah proposisi. TABEL 1 : TB untuk proposisi dan negasinya
p T F
¬p F T
MASALAH LOGIKA 1 Pada suatu komunitas mahasiswa baru terbagi dua kelompok, yaitu kelompok pembohong yaitu mhs yang selalu berkata salah dan kelompok penjujur yaitu mhs yang selalu berkata benar. dadang mulyana
dadang mulyana
OPERATOR LOGIKA MASALAH LOGIKA 1 (Lanjutan) Suatu ketika seorang dosen bertemu dengan tiga orang mahasiswa yang sedang duduk di tangga; sebut saja mereka dengan A, B dan C. Dosen tersebut bertanya kepada A, apakah A penjujur atau pembohong. A menjawab dengan muka tertunduk sehingga jawabannya tidak jelas. Kemudian sang dosen bertanya kepada B :”apa yang dikatakan A tadi ?” B menjawab bahwa “ A seorang penjujur”. Eh, si C nyeletuk dan mengatakan bahwa “B seorang pembohong” DAPATKAH ANDA MEMASTIKAN SIAPA PENJUJUR DAN SIAPA PEMBOHONG DIANTARA MEREKA BERTIGA ? Petunjuk : Cukup dianalisa dengan menggunakan pernyataan dan negasinya.
dadang mulyana
¬
¬p
Proposisi p
Proposisi
Proposisi p, q
Proposisi r
Operator logika digunakan untuk membentuk proposisi baru dari satu atau lebih proposisi yang sudah ada. Operator logika disebut juga konektivitas. BEBERAPA KONEKTIVITAS: 1. Negasi 2. Konjungsi 3. Disjungsi 4. Disjungsi eksklusif 5. Implikasi 6. Implikasi dua arah
dadang mulyana
KONJUNGSI
CONTOH :
DEFINISI : Misalkan p dan q adalah proposisi. Proposi “p dan q” ditulis p ∧ q adalah proposisi yang bernilai benar jika kedua p dan q benar dan bernilai salah untuk kasus lainnya. Proposisi p ∧ q disebut konjungsi dari p dan q. TABEL 2 : TB Konjungsi
p T T F F dadang mulyana
q T F T F
p∧q T F F F
1. Misalkan p : Hari ini Jumat, q : Hari ini hujan. maka p ∧ q : Hari ini Jumat dan hujan. Bagaimana nilai kebenarannya. Sangat tentatif, tergantung pada keadaan disaat pernyataan ini diungkapkan. 2. Misalkan p : Ada 7 hari dalam seminggu, q : 2+2 = 4, maka p ∧ q : Ada 7 hari dalam seminggu dan 2+2 = 4. Proposisi ini yang bernilai benar.
dadang mulyana
DISJUNGSI
CONTOH :
DEFINISI : Misalkan p dan q adalah proposisi. Proposi “p atau q” ditulis p ∨ q adalah proposisi yang bernilai salah jika kedua p dan q salah dan bernilai benar untuk kasus lainnya.
TABEL 3. TB Disjungsi
p T T F F dadang mulyana
q T F T F
p∨ q T T T F
Diperhatikan proposisi berikut : “Mahasiswa yang sudah mengambil kuliah kalkulus atau kuliah algoritma pemrograman boleh mengambil kuliah metoda numerik. Sesungguhnya kita mempunyai bentuk disjungsi p ∨ q, dimana p : Mhs yang sudah kuliah kalkulus boleh ambil numerik q : Mhs yang sudah ambil algoritma boleh ambil numerik Beberapa kemungkinan mhs yang boleh ambil numerik : 1. Mhs yang sudah mengambil kuliah kalkulus saja 2. Mhs yang sudah mengambil kuliah algoritma saja 3. Mhs yang sudah mengambil keduanya. dadang mulyana
EKSKLUSIF OR (XOR)
DEFINISI : Misalkan p dan q adalah proposisi. Proposisi “salah satu p atau q” ditulis p ⊕ q adalah proposisi yang bernilai benar jika tepat satu diantara p atau q BENAR, dan bernilai salah untuk kasus lainnya.
IMPLIKASI DEFINISI : Misalkan p dan q adalah proposisi. Proposi “jika p maka q” ditulis p → q adalah proposisi yang bernilai salah jika p benar tetapi q salah dan bernilai benar untuk kasus lainnya. TABEL 5. TB Impilkasi
TABEL 4 : TB Eksklusif OR
p T T F F dadang mulyana
q T F T F
p ⊕q F T T F
p T T F F
q T F T F dadang mulyana
p →q T F T T
IMPLIKASI (Lanjutan) p T T F F
q T F T F
p →q T F T T
Contoh menarik Misalkan p : soal ujian yang diberikan oleh guru q : jawaban yang diberikan oleh siswa
Diperhatikan TB implikasi : • apapun nilai kebenaran q, asalkan p bernilai salah maka implikasinya bernilai benar.
PENYEBUTAN LAIN UNTUK p → q : 1. p berimplikasi q 2. p berakibat q 3. q hanya jika p 4. p adalah syarat cukup q 5. q adalah syarat perlu p dadang mulyana
Nilai kebenaran dari p → q diilustrasikan sbg penilaian guru : 1. Bila soal ujian benar, jawaban juga benar maka nilainya lulus 2. Bila soal ujian benar, jawaban salah maka nilainya harus gagal 3. Bila soal ujiannya salah, dijawab benar maka nilainya lulus 4. Bila soal ujiannya salah, dijawab salah maka nilainya lulus. CONTOH : Diperhatikan kalimat implikasi berikut : “Jika belanja anda melebihi 1 juta rupiah maka akan diberikan diskon 2%.” Toko hanya memberikan perlakuan terhadap pelanggan dengan nilai belanja melebihi 1 juta tetapi tidak membahas belanja yang kurang dari 1 juta rupiah. CONTOH : “Jika hari ini Senin maka 2 + 3 = 5” merupakan proposisi yang benar walaupun kedua proposisi aslinya tidak berhubungan. dadang mulyana
Bentuk Jika …. Maka Dalam pemrograman komputer Diperhatikan pernyataan berikut : “Jika x < 3 maka x = x + 1” • Bila sebelum pernyataan ini diberikan x = 2 maka akan dihasilkan nilai x yang baru, yaitu x = 2 + 1 = 3 • Bila sebelumnya diberikan x = 4 maka tidak ada pembaharuan (updating) nilai x. Hasilnya tetap, yaitu x = 4. Coba analisa pernyataan berikut : “Jika 2+2=4 maka x = x^2+1”. Berapa hasilnya jika diberikan x=1, 2, 4. Dalam banyak pemrograman komputer, bentuk “jika … maka” biasanya muncul dalam bentuk berlapis, seperti “jika ……(jika…..(jika …..maka.…)…..maka)….maka….” dadang mulyana
BI-IMPLIKASI DEFINISI : Misalkan p dan q adalah proposisi. Proposi “p jika hanya jika q” ditulis p ↔ q adalah proposisi yang bernilai benar jika p dan q keduanya benar atau keduanya bernilai salah. TABEL 6. TB bi-Implikasi
p T T F F
q T F T F dadang mulyana
p↔ q T F F T
Masalah praktis Logika Dikarenakan masalah mesin, sang pilot membuat pendaratan darurat di pantai suatu pulau terpecil. Pulau ini didiami oleh 2 kelompok, katakan saja kelompok bangsawan yang selalu berkata jujur dan kelompok awam yang selalu berkata bohong. Sang pilot memutuskan menuju kota untuk mencari bantuan tapi tidak tahu harus ke arah mana. Ketika sedang berjalan sendiri sampai di suatu persimpangan (ada jalan ke kiri dan jalan ke kanan), dan bertemu dua orang, katakan A dan B. Sang pilot bertanya pada A tentang jalan mana yang harus diambil agar sampai di kota. Si A menjawab sbb : “kota ada di gunung, atau jalan ke kanan menuju kota”. Berbeda dengan A, Si B memberikan statmen “kota ada di gunung, dan jalan ke kanan menuju kota”. Sambil mengangkat bahu, si A mengatakan bahwa “si B pembohong”. Selanjutnya si B memberikan argumentasi dalam pernyataan berikut “jika kota ada di gunung maka jalan ke kanan menuju kota”. Dapatkah sang pilot mengambil jalan yang benar ? Bagaimana?
Penterjemahan bahasa Indonesia Kedalam bentuk Logika Contoh 1: Anda dapat mengakses internet dari kampus hanya jika anda jurusan informatika atau anda bukan mhs baru. Penyelesaian : ada banyak cara untuk menyajikan klm ini dalam bentuk logika, salah satunya sbb: Misalkan p : anda dapat mengakses internet dari kampus q : anda mahasiswa jurusan informatika r : anda mahasiswa baru Maka kalimat di atas dapat disajikan dalam simbol logika sbb : q
( r) ∨ ¬
→
p
Contoh 2 : Anda tidak diperbolehkan naik roller coaster jika tinggi anda Kurang dari 120 cm, kecuali anda sudah berumur di atas 15 tahun. Untuk latihan, coba ubah ke simbol logika.
dadang mulyana
dadang mulyana
Logika dan Operasi Bit pada sistem Komputer
Logika dan Operasi Bit pada sistem Komputer (Lanjutan)
• Bit berupa angka 1 dan 0. String merupakan barisan atau susunan beberapa bit. Komputer menggunakan sistem basis dua, yaitu ia menyajikan informasi dengan menggunakan bit 1 dan 0.
CONTOH : Diberikan dua string x dan y sbb : x = 01 1011 0110 dan y = 11 0001 1101. Tentukan hasil dari x ∧ y, x ∨ y dan x ⊕ y.
• Bit 1 digunakan untuk menyakjikan nilai benar (T), dan bit 0 digunakan untuk menyajikan nilai salah (F).
PENYELESAIAN : x = 01 1011 0110 y = 11 0001 1101 x ∧ y = 01 0001 0100
• Operasi bit berupa konektivitas pada logika, yaitu : ∧ : “dan”, ∨ : “atau”, ⊕ : ekslusif OR • Dua string dapat dioperasikan jika mereka mempunyai panjang yang sama.
dadang mulyana
x y x
∨
= 01 1011 0110 = 11 0001 1101 y = 11 1011 1111
x y
= 01 1011 0110 = 11 0001 1101
x
⊕ y = 10 1010 1011 dadang mulyana
LATIHAN
Tautologi dan Kontradiksi Gabungan dua proposisi yang selalu bernilai benar, tidak bergantung pada nilai kebenaran masing-masing proposisi disebut tautologi.
Bentuklah tabel kebenaran dari (p˄q)˅(~q ˄r)
Gabungan dua proposisi yang selalu bernilai salah, tidak bergantung pada nilai kebenaran masing-masing propoSisi disebut kontradiksi. Contoh : p p
∨ ¬p ∧ ¬p
: Tautologi : Kontradiksi
Besok akan turun hujun atau tidak turun hujan
tautologi
2 adalah bilangan genap dan bilangan ganjil
kontradiksi
dadang mulyana
dadang mulyana
Konvers, invers dan kontraposisi Contoh 6. Bentuklah tabel kebenaran dari proposisi majemuk (p ∧ q) ∨ (~q ∧ r). p
q
r
p∧q
T T T T F F F F
T T F F T T F F
T F T F T F T F
T T F F F F F F
~q ~q ∧ r (p ∧ q) ∨ (~q ∧ r) F F T T F F T T
F F T F F F T F
T T T F F F T F
Diperhatikan implikasi p →q : • Konvers : q → p • Invers
:
¬p
• Kontraposisi :
→ ¬q
¬q → ¬ p
Coba buat tabel kebenaran untuk konjungsi, disjungsi, XOR, implikasi, konvers, invers dan kontraposisi. Selidikilah apa saja pasangan proposisi yang mempunyai nilai kebenaran yang sama.
EKUIVALENSI PROPOSISI 21
dadang mulyana
dadang mulyana
Proposisi majemuk disebut tautologi jika ia benar untuk semua kasus Proposisi majemuk disebut kontradiksi jika ia salah untuk semua kasus.
Contoh 7. p ∨ ~(p ∧ q) adalah sebuah tautologi p
q
p∧q
T T F F
T F T F
T F F F
~(p ∧ q) F T T T
23 dadang mulyana
p ∨ ~(p ∧ q) T T T T
24 dadang mulyana
Dua buah proposisi majemuk, P(p, q, ..) dan Q(p, q, ..) disebut ekivalen secara logika jika keduanya mempunyai tabel kebenaran yang identik.
Contoh 8. (p ∧ q) ∧ ~(p ∨ q) adalah sebuah kontradiksi p
q
p∧q
T T F F
T F T F
T F F F
p∨q F T T F
~(p ∨ q) F F F T
(p ∧ q) ∧ ~(p ∨ q)
Notasi: P(p, q, …) ⇔ Q(p, q, …) Contoh 9. Hukum De Morgan: ~(p ∧ q) ⇔ ~p ∨ ~q.
F F F F
p
q
p ∧ q ~ (p ∧ q)
~p
~q ~ p ∨ ~ q
T T F F
T F T F
T F F F
F F T T
F T F T
F T T T
25 dadang mulyana
F T T T 26
dadang mulyana
EKUIVALEN LOGIS DEFINISI : Dua proposisi m dan n dikatakan ekuivalen logis jika m↔ n merupakan suatu tautologi. Notasi m ⇔ n : untuk menyatakan bahwa m dan n ekuivalen secara logis. CONTOH : 1. implikasi p → q ekuivalen logis dengan kontraposisinya 2.
¬ (p ∨ q) ⇔ ¬ p ∧ ¬ q
p T T F F
q T F T F
¬ p ¬ q p → q ¬ q → ¬p F F T T
F T F T
T F T T
T F T T sama
Bukti : Gunakan tabel kebenaran. Berikut untuk contoh 1, contoh 2 diberikan sebagai latihan.
Dalam penerapannya, kebenaran proposisi yang berupa implikasi kadangkala dibuktikan melalui kontraposisinya.
dadang mulyana
dadang mulyana
BEBERAPA BENTUK EKUIVALENSI LOGIS Misalkan T proposisi yang selalu bernilai benar dan F propoisi Yang selalu bernilai salah. 1. 2. 3.
Hukum Identitas : p ∧ T ⇔ p dan p ∨ F ⇔ p Hukum Dominasi : p ∨ T ⇔ T dan p ∧ F ⇔ F Hukum Idempoten : p ∨ p ⇔ p dan p ∧ p ⇔ p
4. Hukum negasi ganda :
¬ ( ¬ p) ⇔
p
∨ q ⇔ q ∨ p dan p ∧ q ⇔ q ∧ p 6. Hukum Asosiatif : (p∨ q) ∨ r ⇔ p∨ (q∨ r) ∧ (p∧ q) ∧ r ⇔ p∧ (q r) 7. Hukum Distributif : p∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p∨ r) p∧ (q ∨ r) ⇔ (p∧ q)∨ (p∧ r) ¬ ∧ ⇔¬ ∨¬ 8. Hukum De Morgan : ¬(p(p∨ q)q) ⇔ ¬ pp ∧ ¬qq
PREDIKAT dan FUNGSI PROPOSISIONAL Diperhatikan kalimat yang memuat variabel “x < 2”. Subjek : x Predikat : kurang dari 2 Pernyataan “x kurang dari 2” dinyatakan dengan P(x), dimana P merujuk sifat “kurang dari 2” dan x variabel. P disebut juga fungsi proposisional dimana P(x) adalah nilai fungsi P di x. Nilai P(x) hanya dua macam, yaitu benar (T) atau salah (F).
5. Hukum Komutatif : p
dadang mulyana
CONTOH : 1. Bila P(x) : x < 2 maka P(1) benar, P(2) salah, P(3/2) benar, dst 2. Fungsi proposisional dengan beberapa varibel : Q(x,y) : x^2 + y^2 = 25 Q(3,4), Q(4,3) bernilai benar, Q(1,2), Q(5,3) salah, dst.
dadang mulyana
Contoh penggunaan fungsi proposisional pada program komputer Misalkan perintah berikut : “ jika x > 0 maka x = x+1” dimasukkan pada suatu program. Fungsi proposisi P(x): x >0. Bila P(x) benar maka perintah x = x + 1 dieksekusi, tetapi bila P(x) salah maka nilai x yang dimasukkan tidak berubah. x=1
P(1) benar
x=0
P(0) salah
x=1+1=2 x=0
dadang mulyana
LAtihan a. Coba buat tabel kebenaran untuk konjungsi, disjungsi, XOR, implikasi, konvers, invers dan kontraposisi. b.Selidikilah apa saja pasangan proposisi yang mempunyai nilai kebenaran yang sama. 2. Buatlah masing-masing 3 contoh contoh proposisiproposisi tautologi dan kontradiksi dalamkehidupan kita. Petakan dalam tabel kebenaran! 3. Jelaskan secara tabel kebenaran nilai dari operasi bit digital dibawah ini: a. 3 or 5 b. not 12 c. 7 and 9 d. 12 xor 23 e. 23 nand 21 4. Buatlah 2 contoh proposisi majemuk yang menyatakan bentuk ekuivalen logis, dan buktikan dalam tabel kebenaran 1.
dadang mulyana
