bab 1 kalkulus proposisi baru

BAB 1 KALKULUS PROPOSISI PROPOSISI :

Kalimat deklaratif yang bernilai benar (true) atau salah (false), tetapi tidak keduanya

Kalimat terbuka

Dinyatakan dengan huruf-huruf kecil : p, q, r

Contoh kalimat-kalimat yang merupakan proposisi : 13 adalah bilangan ganjil T Soekarno adalah alumnus UGM F 1+1=2 T Hari ini adalah hari Senin F

Contoh kalimat-kalimat yang bukan merupakan proposisi : Jam berapa kereta api Argo Bromo tiba di Gambir ? Isilah gelas tersebut dengan air !

OPERATOR LOGIKA DASAR (UTAMA):

Digunakan untuk mengkombinasikan proposisi

Not / Negation / Ingkaran / Bukan / Tidak notasi ~ p

And / Conjunction / Konjungsi / Dan notasi p q

Or / Disjunction / Disjungsi / Atau notasi p q

NOT

p ~ p

T F

F T

CONJUNCTION

p q p q

T T T

T F F

F T F

F F F

DISJUNCTION

p q p q

T T T

T F T

F T T

F F F

TABEL KEBENARAN :

Tabel dari semua kemungkinan (interpretasi)

Jumlah interpretasi = 2jumlah proposisi

Proposisi = 1 21 = 2 Proposisi = 2 22 = 4 Dua pernyataan logika disebut ekivalen logis bila tabel kebenarannya identik

Contoh Soal 1.1

Tentukan tabel kebenaran dari :

(p q) (~p r)

p q r (p q) ~p (~p r) (p q) (~p r)

T T T T F F T

T T F T F F T

T F T F F F F

F T T F T T T

F F T F T T T

F T F F T F F

T F F F F F F

F F F F T F F

p q p q

T T T

T F F

F T F

F F F

p q p q

T T T

T F T

F T T

F F F

p ~ p

T F

F TJawab :Proposisi = 3 23 = 8

Contoh Soal 1.1

Tentukan tabel kebenaran dari :

(p q) (~p r)

p q r (p q) ~p (~p r) (p q) (~p r)

T T T T F F T

T T F T F F T

T F T F F F F

F T T F T T T

F F T F T T T

F T F F T F F

T F F F F F F

F F F F T F F

p q p q

T T T

T F F

F T F

F F F

p q p q

T T T

T F T

F T T

F F F

Contoh Soal 1.2

Tunjukkan bahwa kedua pernyataan logika di bawah ini ekivalen logis

~(p q) ~p ~ q (Hukum de Morgan)

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

p q p q

T T T

T F F

F T F

F F F

p q p q

T T T

T F T

F T T

F F F

Jawab :Proposisi = 2 22 = 4

Contoh Soal 1.3

Tunjukkan bahwa kedua pernyataan logika di bawah ini ekivalen logis

~(p q) ~p ~ q (Hukum de Morgan)

p q (p q) ~(p q) ~p ~q ~p ~q

T T T F F F F

T F T F F T F

F T T F T F F

F F F T T T T

p q p q

T T T

T F F

F T F

F F F

p q p q

T T T

T F T

F T T

F F F

Jawab :Proposisi = 2 22 = 4

HUKUM-HUKUM LOGIKA :

1. Hukum Identitas

2. Hukum Null/Dominasi

3. Hukum Negasi

4. Hukum Idempoten

5. Hukum Involusi (negasi ganda)

6. Hukum Penyerapan (Adsorpsi)

7. Hukum komutatif

8. Hukum Asosiatif

9. Hukum Distributif

10. Hukum De Morgan

1. Hukum Identitas

p q = F p F

T F

F F

p q = T P T

T T

F T

p F p

p T p

p q p q

T T T

T F F

F T F

F F F

p q p q

T T T

T F T

F T T

F F F

2. Hukum Null/Dominasi

p q = F p F

T F F

F F F

p q = T P T

T T T

F T T

p F F

p T T

3. Hukum Negasi

p ~ p p ~p

T F F

F T F

p ~ p p ~p

T F T

F T T

p ~p F

p ~p T

4. Hukum Idempoten

p p p p

T T T

F F F

p p p p

T T T

F F F

p p p

p p p

5. Hukum Penyerapan(adsorpsi)

p (p r) p

p (p r) p

p q p q p (p q)

T T T T

T F F T

F T F F

F F F F

6. Hukum Involusi (negasi ganda)

~ (~ p) p

7. Hukum Komutatif

p q q p

p q q p

8. Hukum Asosiatif

p (q r) (p q) r

p (q r) (p q) r

9. Hukum Distributif

p (q r) (p q) (p r)

p (q r) (p q) (p r)

10 Hukum De Morgan

~ (p q) ~p ~q

~ (p q) ~p ~q

Soal Latihan 1.1

Di bawah ini adalah suatu rangkaian logika yang terbentuk dari gerbang-gerbang (gates) AND,OR dan NOT dengan dua input (p dan q) dan satu output (x).

Tentukan proposisi dari outputnya, kemudian tentukan tabel kebenarannya

p

q

x

Rangkaian Logika

p q (p q) ~p ~q ~pq (pq)(~pq) = a ~p~q = b ab = x

T T T F F F T F T

T F F F T F F F F

F T F T F T T F T

F F F T T F F T T

Jawab :

x = [(p q) (~p q)] (~p ~q )

p

qp q

~p

~q

~p ~q = b

~p q

(p q) (~p q) = a

a b = x

Tabel kebenaran x

p q x ~p ~ p q

T T T F T

T F F F F

F T T T T

F F T T T

p

q

x

Rangkaian Logika

p

q ~p q

Rangkaian Logika

x = [(p q) (~p q)] (~p ~q ) ~p q

Alternatif Pembuatan Tabel Kebenaran

p q ~ (p ~ q)

T T T T

T F T F

F T F T

F F F F

Langkah 1 1

Misalkan akan dibuat tabel kebenaran dari proposisi : ~ ( p ~ q )

p q ~ (p ~ q)

T T T F T

T F T T F

F T F F T

F F F T F

Langkah 1 2 1

p q ~ (p ~ q)

T T T F F T

T F T T T F

F T F F F T

F F F F T F

Langkah 1 3 2 1

p q ~ (p ~ q)

T T T T F F T

T F F T T T F

F T T F F F T

F F T F F T F

Langkah 4 1 3 2 1

Soal Latihan 1.2

Tentukan tabel kebenaran dari proposisi : [(p q) (~p q)] (~p ~q )

p q [(p q) (~ p q)] (~ p ~ q)

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

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

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

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

Langkah 1 3 1 4 2 1 3 1 5 2 1 3 2 1

Jawab :

Soal Latihan 1.2

Tentukan tabel kebenaran dari proposisi : [(p q) (~p q)] (~p ~q )

p q [(p q) (~ p q)] (~ p ~ q)

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

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

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

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

Langkah 1 3 1 4 2 1 3 1 5 2 ! 3 2 1

Contoh Soal 1.4

Dengan menggunakan hukum-hukum Logika (tanpa tabel kebenaran), tunjukkan bahwa kedua proposisi berikut ini adalah ekivalen logis ~(p (~p q)) dan ~p ~ q

Jawab : Identitas :

p F p

p T p

Negasi ganda :

~ (~ p) = p

Dominasi :

p F F

p T T

Komutatif :

p q = q pp q = q p

Idempoten :

p p p

p p p

Asosiatif

p (q r) (p q) rp (q r) (p q) r

Negasi :

p ~p F

p ~p T

Distributif

p (q r) (p q) (p r)p (q r) (p q) (p r)

Adsorpsi :

p (p r) p

p (p r) p

De Morgan :

~ (p q) ~p ~q

~ (p q) ~p ~q

~(p (~ p q))

~p ~(~p q) De Morgan 2

~p ~(~p) ~q De Morgan 2

~ p (p ~q) Negasi ganda

(~p p) (~p ~q) Distributif 1

F (~p ~q) Negasi 1

(~p ~q) F Komutatif 1

~p ~ q Identitas 1

Soal Latihan 1.3

Dengan menggunakan hukum-hukum Logika (tanpa tabel kebenaran), tunjukkan bahwa kedua proposisi berikut ini adalah ekivalen logis ~(p q) (~ p q) dan ~ p

Jawab :

~(p q) (~ p q)

(~p ~q) (~ p q) De Morgan 2

~p (~q q) Distributiif 1

~p T Negasi 2

~ p Identitas 2

Identitas :

p F p

p T p

Negasi ganda :

~ (~ p) = p

Dominasi :

p F F

p T T

Komutatif :

p q = q pp q = q p

Idempoten :

p p p

p p p

Asosiatif

p (q r) (p q) rp (q r) (p q) r

Negasi :

p ~p F

p ~p T

Distributif

p (q r) (p q) (p r)p (q r) (p q) (p r)

Adsorpsi :

p (p r) p

p (p r) p

De Morgan :

~ (p q) ~p ~q

~ (p q) ~p ~q

Soal Latihan 1.3

Dengan menggunakan hukum-hukum Logika (tanpa tabel kebenaran), tunjukkan bahwa kedua proposisi berikut ini adalah ekivalen logis ~(p q) (~ p q) dan ~ p

Jawab :

~(p q) (~ p q)

(~ p ~ q) (~ p q) De Morgan 2

~p (~q q) Distributif 1

~p T Negasi 2

~p Identitas 2

Identitas :

p F p

p T p

Negasi ganda :

~ (~ p) = p

Dominasi :

p F F

p T T

Komutatif :

p q = q pp q = q p

Idempoten :

p p p

p p p

Asosiatif

p (q r) (p q) rp (q r) (p q) r

Negasi :

p ~p F

p ~p T

Distributif

p (q r) (p q) (p r)p (q r) (p q) (p r)

Adsorpsi :

p (p r) p

p (p r) p

De Morgan :

~ (p q) ~p ~q

~ (p q) ~p ~q

p q p q

T T T

T F F

F T T

F F T

Jika p, maka q if p, then q

proposisi p disebut hipotesis / antesenden / premis

proposisi q disebut konklusi / konsekuen

Variasi proposisi dengan :

Implikasi p q

Konvers (kebalikan) : q p

Invers : ~ p ~ q

Kontraposisi : ~ q ~ p

Contoh : Tentukan konvers, invers dan kontraposisi dari :

Jika Amir orang kaya (p), maka ia mempunyai mobil (q)

Konvers : Jika ia mempunyai mobil, maka Amir orang kaya

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

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

OPERATOR LOGIKA KONDISIONAL

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

Tabel Kebenaran konvers, invers dan kontraposisi dari implikasi :

Tautologi 1 : p q ~ p q Tautologi 6 : (p q ) (p r ) p (q r )

Tautologi 2 : ~ (p q) p q Tautologi 7 : (p r) (q r) (p q) r

Tautologi 3 : p q ~ q ~ p Tautologi 8 : (p q) (p r) p (q r)

Tautologi 4 : p q ~p q Tautologi 9 : (p r) (q r) (p q) r

Tautologi 5 : p q ~ (p ~ q)

Hukum-hukum Logika yang melibatkan implikasi p q

Biimplikasi p q

p jika dan hanya jika q p if and only if q p q p q

T T T

T F F

F T F

F F T

1 : p q (p q) (q p)

2 : p q ~ p ~ q

3 : p q (p q) (~ p ~ q)

4 : ~(p q) p ~ q

5 : p q q p

Hukum-hukum Logika yang melibatkan biimplikasi p q

Urutan Prioritas dari Operator Logika

Operator Logika Notasi Prioritas

Kurung () Paling tinggi

Negasi ~

Konjungsi

Disjungsi

Implikasi

Biimplikasi Paling rendah

Contoh Soal 1.5 [UTS Logika Matematika 3 Desember 2007]

Tentukan tabel kebenaran dari setiap kalimat di bawah ini :

a). (~q p) (p ~q)

b). [p (q r)] [(p q) r]

c). [(p q) (p r) (q r)] r

Jawab a) :

p q p q

T T T

T F F

F T T

F F T

p q ~ q ~q p p ~q (~q p) (p ~q)

T T F T F F

T F T T T T

F T F T T T

F F T F T T

Jawab b) : p q p q

T T T

T F F

F T T

F F T

p q p q

T T T

T F F

F T F

F F T

p q r q r p q p (q r) (p q) r [p (q r)] [(p q) r]

T T T T T T T T

T T F F T F F T

T F T T F T T T

F T T T F T T T

F F T T F T T T

F T F F F T T T

T F F T F T T T

F F F T F T T T

Jawab c) : p q p q

T T T

T F F

F T T

F F T

p q r p q p r q r (p q) (p r)= a

a (q r)]= b

b r

T T T T T T T T T

T T F T F F F F T

T F T T T T T T T

F T T T T T T T T

F F T F T T F F T

F T F T T F T F T

T F F T F T F F T

F F F F T T F F T

[(p q) (p r) (q r)] r

Bila kolom terakhir tabel kebenaran dari suatu proposisi semuanya benar (T), maka proposisi tersebut disebut tautologi,

Bila kolom terakhir tabel kebenaran dari suatu proposisi semuanya salah (F), maka proposisi tersebut disebut kontradiksi

Bila kolom terakhir tabel kebenaran dari suatu proposisi ada yang benar (T) dan ada yang salah (F),maka proposisi tersebut disebut kontingensi

TAUTOLOGI, KONTRADIKTIF DAN KONTINGENSI :

Contoh Soal 1.6

Tentukan apakah kalimat implikasi di bawah ini tautologi, kontradiksi atau kontigensi

a). a (b a b) b). a (b c) (a b) (a c)

a b a b b a b a (b a b)

T T T T T

T F T T T

F T T T T

F F F T T

Jawab a) :

p q p q

T T T

T F F

F T T

F F T

Jawab b) :

a b c b c a b a c a (b c)= x

(a b) (a c) = y

x y

T T T T T T T T T

T T F F T T T T T

T F T F T T T T T

F T T T T T T T T

F F T F F T F F T

F T F F T F F F T

T F F F T T T T T

F F F F F F F F T

a (b c) (a b) (a c)

p q p q

T T T

T F F

F T F

F F T

Soal Latihan 1.7 [UTS Logika Matematika 3 Desember 2007]

Tentukan tabel kebenaran dari setiap kalimat di bawah ini :

a). ~ (p q) (~q r)

b). ~(p q) (r ~p)

Jawab a) :

p q p q

T T T

T F F

F T T

F F T

p q ~ q ~q p p ~q (~q p) (p ~q)

T T F T F F

T F T T T T

F T F T T T

F F T F T T