DASAR-DASAR LOGIKADASAR-DASAR LOGIKA

Septi Fajarwati, S.Pd.Septi Fajarwati, S.Pd.

Ilmu LogikaIlmu Logika Ilmu logika berhubungan dengan kalimat-Ilmu logika berhubungan dengan kalimat-

kalimat (argumen-argumen) dan hubungan kalimat (argumen-argumen) dan hubungan yang ada di antara kalimat-kalimat tersebut.yang ada di antara kalimat-kalimat tersebut.

Tujuannya adalah memberikan aturan-aturan Tujuannya adalah memberikan aturan-aturan sehingga orang dapat menentukan apakah sehingga orang dapat menentukan apakah suatu kalimat bernilai benar.suatu kalimat bernilai benar.

Ilmu logika lebih mengarah pada bentuk Ilmu logika lebih mengarah pada bentuk kalimat (sintaks) daripada arti kalimat itu kalimat (sintaks) daripada arti kalimat itu sendiri (semantik).sendiri (semantik).

Kalimat Deklaratif / Proposisi adalah suatu kalimat Kalimat Deklaratif / Proposisi adalah suatu kalimat yang memiliki nilai kebenaran (yang memiliki nilai kebenaran (truth value)truth value) benar benar ((truetrue) dengan notasi T, atau nilai kebenaran salah ) dengan notasi T, atau nilai kebenaran salah ((falsefalse) dengan notasi F tetapi tidak kedua-duanya.) dengan notasi F tetapi tidak kedua-duanya.

Contoh ProposisiContoh Proposisi : : ““Hari ini hujan.” (Situasinya diberitahukan)Hari ini hujan.” (Situasinya diberitahukan) ““Beijing adalah ibu kota China.” Beijing adalah ibu kota China.” ““1 + 2 = 3”1 + 2 = 3” ““6 adalah bilangan ganjil.”6 adalah bilangan ganjil.”Berikut ini yang BUKAN proposisi:Berikut ini yang BUKAN proposisi: ““Siapa itu?” (pertanyaan)Siapa itu?” (pertanyaan) ““xx + + yy = 7” = 7” ““Lakukan saja!” (perintah)Lakukan saja!” (perintah) ““Ya, sepertinya begitu” (tidak jelas)Ya, sepertinya begitu” (tidak jelas) ““1 + 2” (expresi tanpa nilai benar/salah)1 + 2” (expresi tanpa nilai benar/salah)

PENGHUBUNG KALIMATPENGHUBUNG KALIMAT

SimbolSimbol Arti Arti BentukBentuk

¬¬ Tidak / NOT / NegasiTidak / NOT / Negasi tidak….tidak….

Dan / AND / KonjungsiDan / AND / Konjungsi …….dan…..dan….

Atau / OR / DisjungsiAtau / OR / Disjungsi .…atau…..…atau….

atauatau XOR / Exclusive-OR / XOR / Exclusive-OR / Disjungsi eksklusifDisjungsi eksklusif

....atau….tetapi tdk ....atau….tetapi tdk keduanyakeduanya

ImplikasiImplikasi Jika.…maka....Jika.…maka....

↔↔ Biimplikasi (Biimplikasi (Biconditional)Biconditional) ...jika dan hanya jika…...jika dan hanya jika…

Notasi AlternatifNotasi Alternatif

Name: not and or xor implies iff Propositional logic: ↔ Boolean algebra: p pq + C/C++/Java (wordwise): ! && || != == C/C++/Java (bitwise): ~ & | ^ Logic gates:

TABEL KEBENARANTABEL KEBENARAN

Perhatikan bahwa secara umum, jika ada n Perhatikan bahwa secara umum, jika ada n variabel (p,q,…), maka tabel kebenaran variabel (p,q,…), maka tabel kebenaran memuat 2memuat 2nn baris. baris.

p q p p q p q pq p q p↔q F F T F F F T T F T T F T T T F T F F F T T F F T T F T T F T T

Keterangan :Keterangan : Negasi / Ingkaran suatu kalimat akan mempunyai nilai Negasi / Ingkaran suatu kalimat akan mempunyai nilai

kebenaran yang berlawanan dengan nilai kebenaran kebenaran yang berlawanan dengan nilai kebenaran kalimat aslinya. Contoh : p = “Saya seorang dosen”kalimat aslinya. Contoh : p = “Saya seorang dosen”

¬¬p = p = “ Saya“ Saya bukanbukan seorang dosen” seorang dosen” p = “Semua/setiap mahasiswa Amikom p = “Semua/setiap mahasiswa Amikom memakai dasi” memakai dasi” ¬¬p = “p = “Ada/beberapa/terdapatAda/beberapa/terdapat mahasiswa mahasiswa Amikom memakai dasi”Amikom memakai dasi”■ KalimatKalimat p p qq akan bernilai benar jika baik akan bernilai benar jika baik pp maupun maupun q q

bernilai benar. Jika salah satunya bernilai salah maka bernilai benar. Jika salah satunya bernilai salah maka pp q q bernilai salah. bernilai salah. Contoh : 2 adalah bilangan prima Contoh : 2 adalah bilangan prima dandan bilangan genap. bilangan genap.

Kalimat Kalimat pp q q mempunyai 2 macam arti : mempunyai 2 macam arti : pp q q disebut Inclusive OR (akan bernilai benar jika disebut Inclusive OR (akan bernilai benar jika pp

benar, atau benar, atau q q benar, atau keduanya bernilai benar)benar, atau keduanya bernilai benar)

Contoh : “Dalam perayaan itu, tamu boleh Contoh : “Dalam perayaan itu, tamu boleh menyumbang uang menyumbang uang atauatau barang." barang."

p p qq atauatau p p qq disebut Exclusive OR (akan disebut Exclusive OR (akan bernilai benar jika bernilai benar jika pp benar, atau benar, atau qq benar, tapi tidak dua- benar, tapi tidak dua-duanya benar). duanya benar). Contoh : “Catur seorang wanita Contoh : “Catur seorang wanita atauatau pria pria tetapi tetapi tidak keduanyatidak keduanya””

Kalimat implikasi Kalimat implikasi pp qq, , pp disebut hipotesis disebut hipotesis (anteseden) dan (anteseden) dan q q disebut konklusi (konsekuen). Kalimat disebut konklusi (konsekuen). Kalimat berbentuk berbentuk p p qq disebut kalimat berkondisi, karena disebut kalimat berkondisi, karena kebenaran kalimat kebenaran kalimat q q tergantung pada kebenaran kalimat tergantung pada kebenaran kalimat pp..

Contoh : “Contoh : “JikaJika segitiga ABC sama sisi segitiga ABC sama sisi makamaka ketiga ketiga sudutnya sama besar.”sudutnya sama besar.”

Kalimat Kalimat p p q dapat dibaca:q dapat dibaca:

q apabila p “p syarat cukup utk q” “q syarat perlu utk p” “q mengikuti p” “q disebabkan p” “p menyebabkan q” “q kapanpun p” “q ketika p”

“jika p, maka q (bila p maka q)”

“p hanya jika q”, karena jka tdk q (q salah), maka p juga tdk terjadi (p salah)

“jika p, q” “kalau p, q” “setiap saat p, q” “q jika p”

Kalimat Biimplikasi atau kondisi ganda (biconditional) Kalimat Biimplikasi atau kondisi ganda (biconditional) p p ↔↔ qq berarti ( berarti (pp qq) ) ( (qq pp)) Supaya Supaya p p ↔↔ qq bernilai benar, maka baik bernilai benar, maka baik pp qq maupun maupun q q

p keduanya harus bernilai benar karena dihubungkan dengan p keduanya harus bernilai benar karena dihubungkan dengan kata penghubung ‘dan’.kata penghubung ‘dan’.

p p ↔↔ qq bernilai benar jika bernilai benar jika p p dan dan qq keduanya bernilai benar keduanya bernilai benar atau keduanya bernilai salah.atau keduanya bernilai salah.

pp qq p p qq q q pp p p ↔↔ q atau (q atau (p p q) q) ( (q q p)p)

TT TT TT TT TT

TT FF FF TT FF

FF TT TT FF FF

FF FF TT TT TT

1. 1. MisalkanMisalkan : p : p = “dia tinggi” = “dia tinggi” qq = “dia tampan” = “dia tampan”

Nyatakan kalimat dibawah ini dgn simbol logika !Nyatakan kalimat dibawah ini dgn simbol logika !

a.a. Dia tinggi Dia tinggi dandan tampan. tampan.

b.b. Dia tinggi Dia tinggi tetapitetapi tidak tampan. tidak tampan.

c.c. Dia tinggi, Dia tinggi, atauatau dia rendah dia rendah dandan tampan. tampan.

d.d. Tidak Tidak benar bahwa dia rendah benar bahwa dia rendah atauatau tidaktidak tampan. tampan.

e.e. JikaJika dia rendah, dia rendah, makamaka dia tidak tampan. dia tidak tampan.

f.f. Dia tampan Dia tampan jika dan hanya jikajika dan hanya jika dia tinggi. dia tinggi.

Contoh :Contoh :

Contoh :Contoh :

2. Tentukan nilai kebenaran dari setiap pernyataan 2. Tentukan nilai kebenaran dari setiap pernyataan

berikut :berikut :

a. Paris ada di Perancis a. Paris ada di Perancis dandan 2 + 2 = 5.T 2 + 2 = 5.T F F F F

b. Kopenhagen ada di Denmark, b. Kopenhagen ada di Denmark, atauatau 1 + 5 = 9 1 + 5 = 9 dandan 3 + 3 = 6. T 3 + 3 = 6. T (F (F T) T) T T F F T T

c. c. JikaJika 2 + 4 = 6, 2 + 4 = 6, makamaka 3 + 1 = 5 3 + 1 = 5 dandan 1 + 1 = 2 1 + 1 = 2

d. d. JikaJika 2 + 4 = 6, 2 + 4 = 6, makamaka 3 + 1 = 7 3 + 1 = 7 jika dan jika dan

hanya jikahanya jika 1 + 1 = 4. 1 + 1 = 4.

LatihanLatihan1. Misalkan : p = “Erik membaca Newsweek”1. Misalkan : p = “Erik membaca Newsweek” q = “Erik membaca The New Yorker”q = “Erik membaca The New Yorker” r = “Erik membaca Time”r = “Erik membaca Time” Tuliskan setiap pernyataan berikut dalam bentuk Tuliskan setiap pernyataan berikut dalam bentuk

simbolik :simbolik : a. Erik membaca Newsweek a. Erik membaca Newsweek atauatau The New Yorker, The New Yorker,

tetapitetapi bukanbukan Time. Time. b. Erik membaca Newsweek b. Erik membaca Newsweek dandan The New Yorker, The New Yorker, atauatau

dia dia tidaktidak membaca Newsweek membaca Newsweek dandan Time. Time. c. c. TidakTidak benar bahwa Erik membaca Newsweek benar bahwa Erik membaca Newsweek tetapitetapi bukanbukan Time. Time. d. d. TidakTidak benar bahwa Erik membaca Time benar bahwa Erik membaca Time atauatau The The

New Yorker New Yorker tetapitetapi tidak Newsweek. tidak Newsweek.

LatihanLatihan

2. Tentukan nilai kebenaran dari setiap 2. Tentukan nilai kebenaran dari setiap pernyataan pernyataan

berikut :berikut :

a. a. JikaJika 9 < 4, 9 < 4, makamaka – 4 < – 9. – 4 < – 9.

b. 1 + 1 = 2 b. 1 + 1 = 2 jika dan hanya jikajika dan hanya jika 2 + 2 = 6. 2 + 2 = 6.

c. Paris ada di Inggris, c. Paris ada di Inggris, dandan 3 + 2 = 5 3 + 2 = 5 dandan

1 + 3 = 4.1 + 3 = 4.

Latihan :Latihan :

3. Buatlah tabel kebenaran untuk kalimat 3. Buatlah tabel kebenaran untuk kalimat dalam bentuk simbol-simbol logika di dalam bentuk simbol-simbol logika di bawah ini!bawah ini!

a. ¬a. ¬((¬¬ p p ¬¬ q) q) b. ¬b. ¬((¬¬ p p q) q) c. (c. (p p q) q) ¬¬(p(p q) q) d. (d. (¬¬ p p ( (¬¬ q q r)) r)) ( (q q r) r) (p (p r) r)

Penyelesaian :Penyelesaian :

pp qq ￢￢ pp ￢￢ qq ￢￢ p p ￢￢qq

¬¬((¬¬ p p ¬¬ q) q)

TT TT FF FF FF TT

TT FF FF TT TT FF

FF TT TT FF TT FF

FF FF TT TT TT FF

a. ¬ a. ¬ ((¬p ¬p ¬q¬q))

c. c. ((p p q) q) ¬¬(p(p q) q)

pp qq p p qq pp q q ¬¬(p(p q q)) ((p p q) q) ¬¬(p(p q q))

TT TT TT TT FF FF

TT FF FF TT FF FF

FF TT TT TT FF FF

FF FF TT FF TT TT

d. d. ((¬¬ p p ( (¬¬ q q r)) r)) ( (q q r) r) (p (p r) r)

pp qq rr ¬¬ p p ¬¬ q q ¬¬ q q r r ¬¬ p p ( (¬¬ q q r) r) q q r r pp r r ((¬¬ p p ( (¬¬ q q r)) r)) ((q q r) r) (p (p r) r)

TT TT TT FF FF FF FF TT TT TT

TT TT FF FF FF FF FF FF FF FF

TT FF TT FF TT TT FF FF TT TT

TT FF FF FF TT FF FF FF FF FF

FF TT TT TT FF FF FF TT FF TT

FF TT FF TT FF FF FF FF FF FF

FF FF TT TT TT TT TT FF FF TT

FF FF FF TT TT FF FF FF FF FF

Latihan :Latihan :4. Jika p dan q bernilai benar (T)4. Jika p dan q bernilai benar (T)

r dan s bernilai salah (F)r dan s bernilai salah (F) Tentukan nilai kebenaran kalimat berikut :Tentukan nilai kebenaran kalimat berikut :

a.a. p p ( (q q r) r)b.b. (p (p q q r) r) ¬¬((((p p q) (r∧q) (r∧ s s))))c.c. ((¬(¬( p p q) q) ¬¬ r) r) ((( (((¬¬ p p q) q) ¬¬ r) r) s) s)

PenyelesaianPenyelesaian : :a. T a. T (T (T F) F)

T T F F TT

Penyelesaian :Penyelesaian :

bb. . (T (T T T F) F) ¬¬((T((T T T) (F∧) (F∧ F F)))) (T (T F) F) ¬¬((TT F)∧ F)∧ (F (F ¬¬F)F) (F (F T) T) TT

c. (c. (¬(¬( T T T) T) ¬¬ F) F) ((( (((¬¬ T T T) T) ¬¬ F) F) F) F) ((¬¬ T T T) T) (((F (((F T) T) T) T) F) F) (F (F T) T) ((F ((F T) T) F) F) T T ( T ( T F) F) T T F F T T

EkuivalenEkuivalen Dua kalimat disebut Ekuivalen (secara Dua kalimat disebut Ekuivalen (secara

logika) logika) bila dan hanya bilabila dan hanya bila keduanya keduanya mempunyai nilai kebenaran yang sama untuk mempunyai nilai kebenaran yang sama untuk semua substitusi nilai kebenaran masing – semua substitusi nilai kebenaran masing – masing kalimat penyusunannya.masing kalimat penyusunannya.

Jika Jika pp dan dan qq adalah kalimat yang ekuivalen, adalah kalimat yang ekuivalen, maka dituliskan maka dituliskan pp ≡ qq atau atau pp qq . Jika . Jika pp ≡ qq maka maka qq ≡ pp juga. juga.

Contoh :Contoh :

Buktikan: Buktikan: ppqq ((p p qq).).

p q pp qq pp qq pp qq ((pp qq))F FF TT FT T

F

T

T

T

T

T

T

TT

T

F

F

F

F

F

FF

F

T

T

Latihan :Latihan :

Tentukan apakah pasangan kalimat-Tentukan apakah pasangan kalimat-kalimat dibawah ini ekuivalen :kalimat dibawah ini ekuivalen :

a.a. ¬¬((¬¬ p) dengan pp) dengan p

b.b. ¬¬((p p q) dengan q) dengan ¬¬ p p ¬¬ q q

c.c. p p q dengan q dengan ¬¬ p p q q

Beberapa hukum ekuivalen logika :Beberapa hukum ekuivalen logika :

1. Hk Komutatif p1. Hk Komutatif p q q qq p , p , pp q q qq p p

2. Hk. Asosiatif (2. Hk. Asosiatif (pp q) q) r r p p ( (qq r) r) ((pp q) q) r r p p ( (qq r) r)

3. Hk. Distributif 3. Hk. Distributif pp (q (q r) r) ( (p p q) q) (p (p r) r) p p ( (qq r) r) ( (p p q) q) (p (p r) r)

4. Hk. Identitas 4. Hk. Identitas pp T T p , p , pp F F p p

5. Hk. Ikatan 5. Hk. Ikatan pp T T T , T , pp F F FF

6. Hk. Negasi 6. Hk. Negasi pp ¬¬ p p T , T , pp ¬¬ p p FF

7. Hk. Negasi Ganda 7. Hk. Negasi Ganda ¬¬((¬¬ p ) p ) pp

8. Hk. Indempoten p 8. Hk. Indempoten p p p p , p , pp p p p p

9. Hk. De Morgan ¬(p 9. Hk. De Morgan ¬(p q) q) ¬¬ p p ¬¬ qq , , ¬¬((pp q) q) ¬¬ p p ¬¬ q q

10.10. Hk. Absorbsi p Hk. Absorbsi p (p (p q) q) p , p , p p ( (pp q) q) p p

11. Negasi T dan F 11. Negasi T dan F ¬¬ T T F , F , ¬¬ F F T T

Contoh :Contoh :

1. Sederhanakan bentuk ¬(¬ p 1. Sederhanakan bentuk ¬(¬ p q) q) ( (p p q)q)

JawabJawab : : De Morgan De Morgan

¬(¬¬(¬ p p q) q) ( (p p q) q) ( (¬(¬¬(¬ p) p) ¬¬ q) q) ( (p p q)q)

((p p ¬¬ q) q) ( (p p q)q)

Negasi Negasi p p ( (¬¬ q q q) q)

Identitas Identitas p p F F pp

Jadi Jadi ¬(¬¬(¬ p p q) q) ( (p p q)q) p p

Contoh :Contoh :

2. Buktikan ekuivalensi kalimat di bawah ini tanpa 2. Buktikan ekuivalensi kalimat di bawah ini tanpa

menggunakan tabel kebenaran!menggunakan tabel kebenaran!

a. ¬(p a. ¬(p ¬ ¬ q) q) ( (¬¬ p p ¬¬ qq) ) ¬¬ p p

((¬¬ p p ¬¬((¬¬ q q)) )) (¬ (¬ p p ¬¬ q) de Morganq) de Morgan

((¬¬ p p qq) ) (¬ (¬ p p ¬¬ q) negasi gandaq) negasi ganda

¬¬ p p ((qq ¬ ¬ q) distributifq) distributif

¬¬ p p T negasi T negasi

¬¬ p p identitas identitas

Contoh : Contoh :

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

¬ p ¬ p (q (q r) r) Transformasi dr Transformasi dr ke ke

¬ p ¬ p (¬ q (¬ q r) r) Transformasi dr Transformasi dr ke ke

(¬ p (¬ p ¬ q ) ¬ q ) r r Asosiatif Asosiatif

¬( p ¬( p q) q) r r De Morgan De Morgan

(p (p q) q) r r Transformasi dr Transformasi dr ke ke

Tautologi dan Kontradiksi Tautologi dan Kontradiksi

Tautologi adalah proposisi majemuk yang selalu bernilai true tidak peduli apa nilai kebenaran proposisi penyusunnya!

Contoh: p p [tabel kebenarann?]

p pp

Kontradiksi adalah proposisi majemuk yang selalu bernilai false tidak peduli apapun!

Contoh: p p [tabel kebenaran?]

(p p ↔↔ q) q) ( p p ↔↔ q)q)

Konvers, Invers, KontraposisiKonvers, Invers, Kontraposisi

Beberapa terminologi dalam implikasi p q :Konvers-nya adalah: q pInvers-nya adalah: ¬p ¬qKontraposisi-nya adalah: ¬q ¬ p

Implikasi selalu ekuivalen dengan kontraposisi.p q q p p q q pF F T T T TF T F T T TT F T F F FT T F F T T

CONTOH:CONTOH:

“Jika A merupakan suatu bujursangkar, maka A merupakan suatu empat persegi panjang.”

Konvers : “Jika A merupakan empat persegi panjang, maka A adalah suatu bujursangkar.”

Invers : “Jika A bukan bujursangkar, maka A bukan empat persegi panjang.”

Kontraposisi : “Jika A bukan empat persegi panjang, maka A bukan bujursangkar.”

ALJABAR BOOLEALJABAR BOOLE

Merupakan suatu jenis simbol – simbol untuk Merupakan suatu jenis simbol – simbol untuk memanipulasi nilai – nilai kebenaran logika memanipulasi nilai – nilai kebenaran logika secara aljabar.secara aljabar.

Cocok untuk diaplikasikan dalam komputer.Cocok untuk diaplikasikan dalam komputer.

Aljabar Boole sebagai suatu struktur aljabarAljabar Boole sebagai suatu struktur aljabar

Aljabar Boole didefinisikan sebagai suatu himpunan Aljabar Boole didefinisikan sebagai suatu himpunan dengan operasi “dengan operasi “”, “”, “”, dan “”, dan “¬¬” (atau ‘) serta 0 dan 1.” (atau ‘) serta 0 dan 1.

(ditulis sebagai atau (ditulis sebagai atau atau ) yang memenuhi sifat – sifat sbb :atau ) yang memenuhi sifat – sifat sbb :

1.1. Hukum komutatif 6. Hukum idempotenHukum komutatif 6. Hukum idempoten

2.2. Hukum Asosiatif 7. Hukum IkatanHukum Asosiatif 7. Hukum Ikatan

3.3. Hukum Distributif 8. Hukum AbsorbsiHukum Distributif 8. Hukum Absorbsi

4.4. Hukum identitas 9. Hukum De MorganHukum identitas 9. Hukum De Morgan

5.5. Hukum Negasi (Komplemen)Hukum Negasi (Komplemen)

1,0,,,, B 1,0,',,, B1,0,'*,,,B