Modul Logika Informatika

 MODUL

LOGIKA INFORMATIKA

 

Created by : Diah Afrianti Rahayu., S.Kom., M.Pd

Program Studi Pendidikan Teknik Informatika dan Komputer

STKIP INVADA CIREBON

Sejarah dan Pengertian Logika Informatika

Logika Informatika berasal dari bahasa Yunani yang berarti “Logos”. Dalam bahasa Inggris biasa diartikan dengan “Word”, “Speech” atau bisa juga dengan “What is Spoken” lebih biasa kita kenal lagi dengan istilah “Thought” atau “Reason”.

Oleh karena itu definisi Logika ialah ilmu pengetahuan Yang mempelajari atau berkaitan dengan prinsip-prinsip dari penalaran argument yang valid. Para ahli setuju bahwa Logika adalah studi tentang kriteria-kriteria untuk mengevaluasi argumenargumen dengan menentukan mana argumen yang valid dan membedakan antara argumen yang baik dan argumen yang tidak baik.Semula logika dipelajari sebagai salah satu cabang filosofi atau ilmu filsafat.

Namun, sejak tahun 1800-an logika dipelajari dibidang matematika dan sekarang ini juga dibidang ilmu komputer, karena logika juga mempengaruhi ilmu komputer dibidang perangkat keras (hardware) maupun perangkat Lunak (software). Logika disini disebut logika simbol karena ia mempelajari usaha-usaha mensimbolisasikan usaha-usaha secara formal.

Oleh karena itu, logika juga disebut dengan logika formal (formal logic). Aristoteles adalah orang pertama yang mengobservasi, meneliti dan mencatat hukum-hukum dari logika formal, khususnya bentuk penalaran yang disebut Silogisme yang terdiri dari beberapa premis dan satu konklusi. Logika yang dikembangkan oleh Aristoteles ini disebut Juga logika klasik atau logika Aristoteles.

Macam-macam Logika.

Logika Alamiah

Kinerja akal budi manusia yang berfikir secara tepat dan lurus sebelum dipengaruhi Oleh keinginan-keinginan dan kecenderungan-kecenderungan yang subjektif.Kemampuan Logika alamiah manusia itu ada sejak lahir.pengetahuan yang mengkaji tentang gejala-gejala alam semesta, termasuk dimuka bumi ini sehingga terbentuk konsep dan prinsip.

Logika Ilmiah

Logika Ilmiah memperhalus dan mempertajam pikiran manusia serta akal budi manusia.Logika ilmiah menjadi ilmu khusus yang merumuskan azas-azas yang harusditepati dalam Setiap pemikiran. Berkat pertolongan logika imliah inilah akal budi dapat bekerja dengan lebih tepat, lebih teliti, lebih mudah dan lebih aman. Logika ilmiah dimaksudkan untuk Menghindarkan kesesatan atau paling tidak dapat dikurangi. Logika ilmiah dapat dikatakan rasional atau masuk akal karena dalam logika ilmiah telah Adanya akal sehat yang mendalami penelitian ilmiah dengan berbagai alasan yang berasal dari Pemikiran itu sendiri.

Manfaat Logika

Membantu setiap orang yang mempelajari logika untuk berpikir secara rasional, kritis, lurus, tetap,tertib, metodis dan koheren

Meningkatkan kemampuan berpikir secara abstrak, cermat, dan objektif

Menambah kecerdasan dan meningkatkan kemampuan berpikir secara tajam dan mandiri.

Memaksa dan mendorong orang untuk berpikir sendiri dengan menggunakan azas-azas sistematis

Meningkatkan cinta akan kebenaran dan menghindari kesalahan-kesalahan berpikir, Kekeliruan serta kesesatan.

Mampu melakukan analisis terhadap suatu kejadian.

Apabila sudah mampu berpikir secara rasional, kritis,lurus, metodis dan analitis seperti pada Point pertama, maka akan meningkatkan citra diri seseorang.

Istilah-Istilah Logika

Premis : Pernyataan

Argumen : Usaha untuk mencari kebenaran dari pernyataan berupa kesimpulan dengan berdasarkan kebenaran dari suatu kumpulan pernyataan.

Konklusi : Kesimpulan

Tentang Informatika

Disiplin ilmu yang mempelajari tentang transformasi fakta berlambang yaitu data maupun informasi pada mesin berbasis komputasi.

Cakupan bidang informatika antara lain : Ilmu Komputer, Ilmu Informasi, Sistem Informasi, Teknik Komputer dan Aplikasi Informasi dalam bidang Komputer Bisnis, Akuntansi maupun Ilmu Komputer Manajemen.

Secara umum, informatika mempelajari tentang struktur, sifat dan interaksi dari berbagai sistem yang dipakai untuk mengumpulkan data, memproses dan menyimpan hasil dari pemrosesan data.

Aspek-Aspek Informatika

                                  

Teori informasi yang mempelajari matematis dari suatu informasi. Ilmu informasi yang mempelajari tentang pengumpulan klasifikasi, manipulasi penyimpanan pengaksesan dan penyebarluasan informasi untuk keperluan sosial dan kemasyarakatan secara menyeluruh.

Ilmu komputer dan Teknik Komputer yang mempelajari tentang pemrosesan, pengaksesan, penyebarluasan dan apapun yang berhubungan dengan teknologi informasi sehingga dapat dikembangkan. Ilmu yang mempelajari logika buatan dibidang komputasi dengan mengembangkan dan memanfaatkan logika itu sendiri.

PERNYATAAN (PROPOSISI)

Kata merupakan rangkaian huruf yang mengandung arti, sedangkan kalimat adalah kumpulan kata yang disusun menurut aturan tata bahasa dan mengandung arti. Di dalam matematika tidak semua pernyataan yang bernilai benar atau salah saja yang digunakan dalam penalaran. Pernyataan disebut juga kalimat deklaratif yaitu kalimat yang bersifat menerangkan. Disebut juga proposisi.

Pernyataan/ Kalimat Deklaratif/ Proposisi adalah kalimat yang bernilai benar atau salah tetapi tidak keduanya.

Contoh :

Yogyakarta adalah kota pelajar (Benar).

2+2=4                                     (Benar).

Tidak semua kalimat berupa proposisi

Contoh :

Dimanakah letak pulau bali?.

Pandaikah dia?.

#penalaran deduktif

penalaran yang didasarkan premis-premis yang diandaikan benar untuk menarik kesimpulan.

contoh: 

1. semua mahasiswa baru mengikuti ospek.

2. wulandari adalah mahasiswa baru.

kesimpulannya : wulandari mengikut ospek.

#penalaran induktif

penalaran yang didasarkan pada premis-premis yang bersifat faktual untuk menarik kesimpulan yang bersifat umum.

contoh:

premis 1          : ayam  1   berkembang biak dengan telur

premis 2          : ayam  2   berkembang biak dengan telur

premis 3          : ayam  3   berkembang biak dengan telur

...

...

...

premis 50        : ayam 50  berkembang biak dengan telur

kesimpulannya : semua ayam berkembang biak dengan telur

Pernyataan:

Pernyataan adalah kalimat yang mempunyai nilai kebenaran (salah/benar)

Pernyataan yang tidak mengandung kata hubung kalimat,disebut pernyataan primer/tunggal/atom. Sedangkan pernyataan yang mengandung satu atau lebih kata hubung kalimat,disebut pernyataan majemuk.

preposisi dilambangkan dengan huruf kecil p,q,r,s,...

contoh:

p : 13 adalah bilangan ganjil

q : soekarno adalah alumni UGM

r :  ayam adalah binatang unggas

s : 2+2=4

PENGHUBUNG KALIMAT DAN TABEL KEBENARAN

KATA HUBUNG KALIMAT

Simbol Arti Bentuk

   ¬/~ Tidak/Not/Negasi Tidak………….

   ^ Dan/And/Konjungsi ……..dan……..

      v Atau/Or/Disjungsi ………atau…….

     => Implikasi Jika…….maka…….

   < => Bi-Implikasi ……..bila dan hanya bila……..

TABEL KEBENARAN

P q ~p ~q p^q pvq p=>q p <=>q

B B S S B B S B

B S S B S B B S

S B B S S B B B

S S B B S S S B

INGKARAN (NEGASI) SUATU PERNYATAAN,KONJUNGSI,DISJUNGSI DAN IMPLIKASI

A. NEGASI (INGKARAN)

Jika p adalah “ Semarang ibukota Jawa Tengah”, maka ingkaran atau negasi dari pernyataan p tersebut adalah ~p yaitu “ Semarang bukan ibukota Jawa Tengah” atau “Tidak benar bahwa Semarang ibukota Jawa Tengah”. Jika p diatas bernilai benar (true), maka ingkaran p (~p) adalah bernilai salah (false) dan begitu juga sebaliknya.

Contoh:

a. p: semua siswa punya almamater

   ~ p : beberapa siswa tidak punya almamater

b.  q  : uki anak yang pandai

   ~ q : uki bukan anak yang pandai

B. KONJUNGSI

Konjungsi adalah suatu pernyataan majemuk yang menggunakan penghubung “DAN/AND” dengan notasi “^”

Contoh:

a.   p: Fahmi makan nasi

      q:Fahmi minum kopi

      Maka p^q : Fahmi makan nasi dan minum kopi

b.   p: Aan anak yang pemalas

      q: Aan anak yang ngantukan

        Maka p^q   : Aan anak yang pemalas dan ngantukan

Pada konjungsi p^q akan bernilai benar jika baik p maupun q bernilai benar. Jika salah satunya (atau keduanya) bernilai salah maka pÙq bernilai salah.

C. DISJUNGSI

Disjungsi adalah pernyataan majemuk yang menggunakan penghubung “ATAU/OR” dengan notasi “v”.  Kalimat disjungsi dapat mempunyai 2 arti yaitu :

a.    INKLUSIF OR

Yaitu jika “p benar atau q benar atau keduanya true”

Contoh  :

p : 7 adalah bilangan prima

q : 7 adalah bilangan ganjil

p v q : 7 adalah bilangan prima atau ganjil

Benar bahwa 7 bisa dikatakan bilangan prima sekaligus bilangan ganjil.

b.    EKSLUSIF OR

Yaitu jika “p benar atau q benar tetapi tidak keduanya”.

Contoh :

 p : Saya akan melihat pertandingan bola di TV.

q : Saya akan melihat pertandingan bola di lapangan.

p v q : Saya akan melihat pertandingan bola di TV atau lapangan.

Hanya salah satu dari 2 kalimat penyusunnya yang boleh bernilai benar yaitu jika “Saya akan melihat pertandingan sepak bola di TV saja atau di lapangan saja tetapi tidak keduanya.

D. IMPLIKASI

Misalkan ada 2 pernyataan p dan q, untuk menunjukkan atau membuktikan bahwa jika p bernilai benar akan menjadikan q bernilai benar juga, diletakkan kata “JIKA” sebelum pernyataan pertama lalu diletakkan kata “MAKA” sebelum pernyataan kedua sehingga didapatkan suatu pernyataan majemuk yang disebut dengan “IMPLIKASI/PERNYATAAN BERSYARAT/KONDISIONAL/ HYPOTHETICAL dengan notasi “ =>”.

Notasi pÞq dapat dibaca :

Jika p maka q

q jika p

p adalah syarat cukup untuk q

q adalah syarat perlu untuk p

 Contoh

       1.  p : Pak Ali adalah seorang haji.

            q : Pak Ali adalah seorang muslim.

             p => q : Jika Pak Ali adalah seorang haji maka pastilah dia seorang  muslim.

2.  p : Hari hujan.  

            q : Adi membawa payung.               

Benar atau salahkah pernyataan berikut?

Hari benar-benar hujan dan Adi benar-benar membawa payung.

Hari benar-benar hujan tetapi Adi tidak membawa payung.

Hari tidak hujan tetapi Adi membawa payung.

Hari tidak hujan dan Adi tidak membawa payung.

KONVERS, INVERS, DAN KONTRAPOSISI

Perhatikan pernytaan di bawah ini! ~  ^  v  => <=>

             

“Jika suatu bender adalah bendera RI maka ada warna merah pada bendera tersebut”

Bentuk umum implikasi di atas adalah “p => q” dengan

p : Bendera RI

q : Bendera yang ada warna merahnya.

Dari implikasi diatas dapat dibentuk tiga implikasi lainnya yaitu :

1.   KONVERS, yaitu q => p

Sehingga implikasi diatas menjadi :

“ Jika suatu bendera ada warna merahnya, maka bendera tersebut adalah bendera RI”.

2.   INVERS, yaitu ~p => ~q

Sehingga implikasi diatas menjadi :

“ Jika suatu bendera bukan bendera RI, maka pada bendera tersebut tidak ada warna merahnya”.

3.   KONTRAPOSISI, yaitu ~q => ~p

Sehingga implikasi di atas menjadi :

“ Jika suatu bendera tidak ada warna merahnya, maka bendera tersebut bukan bendera RI”.

Suatu hal yang penting dalam logika adalah kenyataan bahwa suatu implikasi selalu ekuivalen dengan kontraposisinya, akan tetapi tidak demikian halnya dengan  invers dan konversnya.

contoh lainnya:

p: lumba-lumba adalah binatang mamalia

q: lumba-lumba adalah binatang menyusui

Implikasi:

jika lumba-lumba adalah binatang mamalia maka lumba-lumba adalah 

binatang yang menyusui.

konvers:

jika lumba-lumba adalah binatang menyusui maka lumba-lumba adalah binatang mamalia.

invers  :

jika lumba-lumba bukan binatang mamalia maka lumba-lumba bukan binatang menyusui

kontraposisi:

jika lumba-lumba bukan binatang menusui maka lumba-lumba 

bukan binatang mamalia.

Hal ini dapat dilihat dari tabel kebenaran berikut

                                                                                                                 

p q ~p ~q implikasi

   p=>q konvers

 q => p invers

~p => ~q kontraposisi

~q => ~p

B B S S B B B B

B S S B S B B S

S B B S B S S B

S S B B B B B B

Perangkai logika

Berikut adalah peringkai logika informatika

Konjungsi (And) dengan symbol “ ^ ”

Tabel Kebenaran :

 

Konklusi/Kesimpulan akan bernilai benar/ true  (T) jika kedua kondisi (A dan B) bernilai benar (T) .

Disjungsi (Or) dengan symbol “ v “

Tabel Kebenaran :

 

Konklusi/Kesimpulan akan bernilai salah/ false  (F) jika kedua kondisi (A dan B) bernilai salah (F) .

————————————————————————————–

Negasi (Not)

Tabel Kebenaran :

 

not A adalah kebalikan dari premis A, dan

not not A adalah kebalikan dari premis not A

(Maaf kawan, simbol not gak kebaca di blog, liat di gambar aja ya simbolnya ;;))

——————————————————————————-

Implikasi (If ..then) dengan symbol (->)

Tabel Kebenaran :

 

Kondisi akan bernilai salah (F) jika pernyataan pertama (A) bernilai (T) dan pernyataan kedua (B) bernilai salah (F)

———————————————————————————————

Biimplikasi/ Ekuivalensi (If..then..if) dengan symbol “ <-> “

Tabel Kebenaran :

 

Jika premis pertama dan kedua ( A dan B ) bernilai sama maka A <->B akan bernilai benar (T)

——————————————————————————————-

NAND/ Not And dengan symbol “ | “

Tabel Kebenaran :

 

Fungsi NAND adalah kebalikan dari fungsi AND “ ^ “

——————————————————————————————

NOR/ Not Or

Tabel Kebenaran :

 

Fungsi NOR adalah kebalikan dari fungsi OR “ v ”

———————————————————————————————-

XOR/ Exclusive Or

Tabel Kebenaran :

 

Fungsi XOR adalah kebalikan dari fungsi If..then..if atau biimplikasi “ <-> “

ARGUMEN (PENGANTAR DASAR MATEMATIKA)

ARGUMEN

Dalam bahasan logika matematika, banyak dilakukan kegiatan penalaran yang berhubungan dengan berbagai pernyataan. Kegiatan penalaran ini meliputi aktivitas berpikir yang abstrak, karena kegiatannya berkaitan dengan penarikan kesimpulan dari sebuah proposisi atau lebih. Untuk selanjutnya kegiatan penalaran ini dilambangkan dengan sesuatu yang disebut argumen.

Setiap argumen terdiri dari pernyataan-pernyataan tertentu dan pernyataan lain yang dapat mengikutinya secara logis. Pernyataan-pernyataan tertentu itu disebut  premis, sedangkan pernyataan lain disebut  konklusi,  dalam bahasa Yunani syllogisme.

Argumen terdiri dari pernyataan-pernyataan yang terdiri atas dua kelompok, yaitu kelompok pernyataan  sebelum kata ‘jadi’ yang disebut premis (hipotesa) dan pernyataan setelah kata ‘jadi’ yang disebut konklusi (kesimpulan).

Jadi, argumen adalah kumpulan pernyataan, baik tunggal maupun majemuk dimana pernyataan-pernyataan sebelumnya disebut premis-premis dan pernyataan terakhir disebut konklusi/ kesimpulan dari argumen.

PEMBUKTIAN VALIDITAS ARGUMEN

Suatu argument disebut valid jika untuk sembarang pernyataan yang disubtitusikan kepada hipotesa, jika semua hipotesa tersebut benar, maka kesimpulan juga benar.

Sebaliknya, jika semua hipotesa benar tetapi ada kesimpulan yang salah, maka argument tersebut dikatakan  tidak valid (invalid). Sebagai contoh argument berikut:

Adi bermain gitar atau keyboard

Adi tidak bermain gitar.

Jadi, adi bermain keyboard.

Misal:

p : Adi bermain gitar

q : Adi bermain keyboard

maka argument diatas mempunyai symbol sebagai berikut:

p ∨ q

~p

∴q

¢  Selanjutnya kita ubah argumen diatas menjadi pernyataan kondisional yang berkoresponden dengan argument tersebut, yaitu dengan cara meng-konjungsi-kan premis-premis, kemudian hasilnya di-implikasi-kan dengan konklusi.

¢  Jadi, argument contoh diatas mempunyai pernyataan kondisional yang berkoresponden yaitu:

[(p ∨ q) ∧ ~p ] ⇒ q

Pernyataan kondisional yang berkoresponden tersebut kemudian dibuat table kebenaran. Jika tabel kebenaran yang dihasilkan berupa tautologi, maka argument tersebut valid. Jika bukan, maka argument tersebut tidak valid.

p q ~p pvq (pvq)˄ ~p [(pvq)˄ ~p]Þq

B B S B S B

B S S B S B

S B B B B B

S S B S S B

Jadi karena kesimpulan argumen bernilai benar atau tautologi maka contoh soal ini adalah argumen yang valid.

Cara lain untuk membuktikan kesahan argumen yang lebih baik dan lebih singkat dengan bukti formal adalah dengan menggunakan hukum-hukum penggantian dan juga aturan penyimpulan seperti yang tercantum berikut ini.

D.1. Modus Ponens

Jika  benar dan p benar maka q benar.

Skema argumen dapat ditulis sebagai berikut :

. . . . . . premis 1

p              . . . . . . premis 2

                 . . . . .  kesimpulan / konklusi

Dalam bentuk implikasi, argumentasi tersebut dapat dituliskan sebagai

. Argumentasi ini dikatakan sah kalau pernyataan implikasi

merupakan tautologi.

D.2. Modus Tollens

Jika  benar dan  benar maka p benar

Skema argumen dapat ditulis sebagai berikut:

. . . . . premis 1

~q        . . . . . premis  2

     ~p    . . . . . . kesimpulan / konlusi

Dalam bentuk implikasi, modus tollens dapat dituliskan sebagai ,sah atau tidaknya modus tollens dapat diuji dengan tabel kebenaran sebagai berikut .

Tabel nilai kebenaran

P q ~p ~q

B B S S B S B

B S S B S S B

S B B S B S B

S S B B B B B

Dari tabel pada kolom 7 tampak bahwamerupakan tautologi. Jadi modus tollens merupakan argumentasi yang sah .

D.3. Silogisme

Dari premis-premis dan dapat ditarik konklusi . Penarikan kesimpulan seperti ini disebut kaidah silogisma . Skema argumnya dapat dinyatakan sebagai berikut :

. . . . .       premis 1

. . . . .       premis 2

. . .        kesimpulan / konklusi

Dalam bentuk implikasi, silogisme dapat dituliskan sebagai  . Sah atau tidaknya silogisme dapat diuji dengan tabel kebenaran sebagai berikut :

Tabel nilai kebenaran .

P q r

B B B B B B B B

B B S B S S S B

B S B S B B S B

B S S S B S S B

S B B B B B B B

S B S B S B S B

S S B B B B B B

S S S B B B B B

Dari tabel pada kolom (8) tampak bahwa  merupakan tautologi. Jadi silogisme merupakan argumentasi yang sah.

D.4. Dilema konstruktif

Argumen formal yang logis yang dimisalkan dengan bentuk:

1. a) P → Q.

b) R → S.

2) Dengan P atau R adalah benar.

Oleh karena itu, baik Q atau S adalah benar.

Operator logis dengan notasi pada tiga tempat:

.

Operator logis dengan notasi dengan dua premis

.

Singkatnya, jika dua kondisi adalah benar dan setidaknya salah satu antesedennya, maka setidaknya salah satu dari mereka harus tetap juga.

Contoh:

Jika saya menang satu juta dolar, saya akan menyumbangkannya ke panti asuhan.

Jika teman saya menang satu juta dolar, dia akan menyumbangkannya ke dana satwa liar.

Entah saya menang satu juta dolar, atau teman saya memenangkan satu juta dolar.

Oleh karena itu, baik panti asuhan akan mendapatkan satu juta dolar, atau dana satwa liar akan mendapatkan satu juta dolar.

Hal ini dinamakan dengan dilema konstruktif. Karena pengoperasian berkesinambungan.

2.  Hukum Aljabar Proposisi (Aturan Penggantian)

Digunakan untuk membuktikan:

Dua proposisi ekivalen (selain menggunakan tabel kebenaran)

Suatu proposisi tautologi atau kontradiksi (selain menggunakan tabel kebenaran)

Membuktikan kesahan suatu argumen

Hukum aljabar proposisi (aturan penggantian) yaitu:

Hukum Idempoten (Idem)

1)      ( p v p ) = p

2)      ( p Ù p ) = p

Hukum Assosiatif (As)

1)      ( p v q ) v r = p v ( q v r )

2)      ( p Ù q ) Ù r = p Ù ( q  Ù r )

Hukum Komutatif (Kom)

1)      ( p Ù q ) = ( q Ù p )

2)      ( p v q ) = ( q v p )

Hukum Distributif (Dist)

1)      ( p v q ) Ù r  = ( p Ù r ) v ( q Ù r )

2)      ( p Ù q ) v r = ( p v r ) Ù ( q v r )

Hukum Identitas (Id)

1)   p v F = p

2)   p v T = T

3)   p Ù  F= F

4)   p Ù T = p

Hukum Komplemen (Komp)

1)      p v ~ p = T

2)      p Ù ~ p = F

3)      ~(~ p)= p

4)      ~(T) = F dan ~ (F) = T

Transposisi (trans)

1)      p -> q º ~ q à ~ p

Hukum Implikasi (imp)

1)   p -> q -> ~ p v q

Hukum Ekivalensi (Eki)

1)      p Û q  -> ( p à q ) Ù ( q à p )

2)      p Û q  -> ( p Ù q ) v ( ~ p Ù ~ q )

Hukum Eksportasi (Eks)

1)      p à ( q à r ) -> ( p Ù q ) à r

Hukum de Morgan (DM)

1)      ~ ( p ^ q ) -> ~ p v ~ q

2)      ~ ( p v q ) -> ~ p Ù ~ q

 

TABEL KEBENARAN

Kaidah-kaidah dasar logika tentang kebenaran dan ketidakbenaran yang menggunakan perangkai logika, yaitu :

Dan (and)

Atau (or)

Tidak (not)

Jika…maka… (if …then…/implies)

…jika dan hanya jika…(…if and only if…)

Contoh 3-1

Jika hujan, maka Bedu basah kuyup

Meski basah kuyupnya Bedu masih dapat diperdebatkan, karena mungkin saja Bedu tidak kehujanan, atau Bedu dapat berteduh, atau meminjam payung dari temannya. Namun logika tidak berhubungan dengan kemungkinan-kemungkinan.

Contoh 3-2

Bedu menangkap bola dan menendangnya

Bedu menendang bola dan menangkapnya

Pada kalimat pertama secara logika alamiah (hard logic) hal tersebut masuk akal. Pada kalimat kedua secara logika alamiah tidak mungkin menendang bola kemudian menangkapnya. Tetapi logika tidak mengutamakan pengertian bahasa sehari-hari.

Tabel kebenaran  adalah suatu tabel yang menunjukkan secara sistematis satu per satu demi nilai kebenaran sebagai hasil kombinasi dari proposisi-proposisi yang sederhana.

Setiap kombinasi nilainya tergantung dari jenis perangkai atau operator yang digunakan.

OPERATOR LOGIKA

Setiap perangkai logika memiliki nilai kebenaran masing-masing sesuai jenis perangkai logika yang digunakan. Perangkai logika yang umum digunakan adalah :

Perangkai Simbol

Dan (and) ∧

Atau (or) ∨

Tidak/bukan (not) ~

Jika…maka…(if…then…/implies →

Jika dan hanya jika (if and only if) ↔

Konjungsi 

Operator Konjungsi atau AND digunakan untuk mengkombinasikan dua buah proposisi. 

Aturannya yaitu :

“Jika kedua proposisi bernilai benar, hasilnya akan bernilai benar. Selain itu, hasilnya bernilai salah.” 

Tabel Kebenaran Operator AND

 

Disjungsi 

Operator Disjungsi atau OR juga digunakan untuk menggabungkan dua buah proposisi.

Aturannya yaitu :

“Jika kedua proposisi bernilai salah, hasilnya akan bernilai salah. Selain itu hasilnya bernilai benar”

Tabel Kebenaran Operator OR

 

Negasi 

Operator Negasi atau NOT digunakan untuk memberikan nilai negasi (lawan) dari pernyataan / kalimat yang ada.

Tabel Kebenaran operator NOT

 

Implikasi 

Operator Implikasi terdiri dari hipotesis dan konklusi.  Kalimat konklusi bergantung pada kalimat hipotesisnya.

Aturannya yaitu :

“Jika kalimat kesatu bernilai benar dan kalimat kedua bernilai salah, hasilnya bernilai salah. Selain itu hasilnya bernilai benar.”

Tabel Kebenaran Operator Implikasi

 

Biimplikasi 

Operator Bi-Implikasi atau Ekivalensi digunakan untuk memberikan penegasan diantara dua buah kalimat implikasi.

Aturannya yaitu :

“Jika kedua proposisi bernilai sama (keduanya benar atau keduanya salah), hasilnya bernilai benar. Selain itu hasilnya salah.”

Tabel Kebenaran Operator Bi-Implikasi

 

OPERATOR LAIN

Selain operator logika diatas, masih ada operator logika yang merupakan kebalikan dari operator “dan” yaitu “tidak dan (nand) “ dan  “tidak atau (nor)”.

Operator “Tidak Dan (Nand)” / [|]

P Q P|R

F F T

F T T

T F T

T T F

Nilai kebenaran  dari “Tidak dan (not and)” adalah kebalikan dari “dan (and)”.

Definisi : misalkan P dan Q adalah proposisi. Proposisi “P dan Q” yang disimbolkan dengan P|Q, adalah proposisi bernilai salah, jika nilai P benar dan nilai Q benar, dan jika selain itu maka nilainya benar.

Operator “Tidak Atau (Nor)” / [ ↓ ]

P Q P↓Q

F F T

F T F

T F F

T T F

Nilai kebenaran “tidak atau (not or)” merupakan kebalikan dari nilai kebenaran “atau (or)”.

Definisi : misalkan A dan B adalah proposisi. Proposisi “A tidak atau B”, yang disimbolkan dengan A↓B , adalah proposisi yang bernilai benar, jika A bernilai salah dan B bernilai salah, dan jika selain itu nilainya salah.

Operator XOR / ⊕

P Q P ⊕ Q

F F F

F T T

T F T

T T F

Nilai kebenaran P xor Q kebalikan dari nilai kebenaran P ↔ Q.

Definisi : misalkan P dan Q adalah proposisi. Proposisi “P xor Q”, yang disimbolkan dengan P ⊕ Q , adalah bernilai benar jika P dan Q bernilai sama, baik benar ataupun salah, jika P dan Q berbeda, nilainya salah.

LATIHAN 

Soal 1

Terdapat proposisi berikut :

P = Bowo kaya raya

Q = Bowo hidup bahagia

Gunakan proposisi tersebut menjadi bentuk logika :

Bowo tidak kaya

Bowo kaya raya dan hidup bahagia

Bowo kaya raya atau tidak hidup bahagia

Jika Bowo kaya raya , maka ia hidup bahagia.

Bowo hidup bahagia jika dan hanya jika ia kaya raya.

Soal 2

Misalkan P, Q, dan R adalah varibel proposisi

P = Saya sakit flu

Q = Saya ikut ujian

R = Saya lulus

Ubahlah ekspresi logika berikut menjadi pernyataan dalam bahasa Indonesia

P→~Q 

Q →~R

~Q→R

(P∧Q)→R

(P→~R)∨(Q→~R)

(P⋀Q)⋁(∼Q⋀R)

Soal 3

Buatlah tabel kebenaran untuk semua kemungkinan nilai kebenaran dari ekspresi logika berikut

~(~P⋀▒〖~Q〗)

P⋀(P⋁Q)

((~P⋀(~Q⋀R) )⋁(Q⋀R) )⋁(P⋀R)

(P⋀Q)⋁(((~P⋀Q)→P) ⋀▒〖~Q〗

(P→Q)↔(~Q→~P)

P⋀((R⋁Q)↔~R)

~((P⋀Q)→~R)⋁P

Pengertian Proposisi

            Proposisi adalah suatu penuturan (assertion) yang utuh, misalnya: Achmad Yani adalah panglima Angkatan Darat; karate adalah salah satu seni bela diri. Suatu penuturan dikatakan tidak utuh apabila tidak mencangkup suatu arti yang utuh; misalnya: ketika saya sedang mengajar. 

            Buku apapun yang kita baca, dan apapun pembicaraan kita, pasti terdiri dari kalimat-kalimat. Tetapi kita semua mengetahui bahwa semua kalimat itu tidak sama. Ada kalimat yang benar-benar merupakan penuturan ada yang sekedar menguyngkapkan keinginan, perintah, seruan, dan lain-lainya.

            Logika hanya mempersoalkan tentang penuturan alasanya adalah penalaran (pemikiran) dan penalaran adalah suatu proses intelektual semata. Proposisi juga dapat didenifisikan ungkapan atau keputusan dalam kata-kata, atau juga manifestasi iuran dari sebuah keputusan.

            Logika seperti juga yang kita katakan tentang ide atau konsep, pertama-tama hanya membicarakan kepuutusan objektif, hanya secara tidak langsung membicarakan keputusan sebagai aksi intelek.

            Dalam logika dikenal adanya dua macam proposisi, menurut sumbernya, yaitu proposisi analitik dan proposisi sintetik. Proposisi analitik adalah proposisi yang predikatnya mempunyai pengertian yang sudah terkandung pada subyeknya, seperti :

            Mangga adalah buah-buahan

            Kuda adalah hewan

            Ayah adalah orang laki-laki

            Jin adalah makhluk halus

Proposisi sinetik adalah proposisi yang predikatnya mempunayi pengeretian yang bukan menjadi keharusan bagi subyeknya, seperti:

            Pepaya ini manis

            Gadis itu langsing

            R.Budi Hartono adalah kaya raya

            Prabowo Subianto adalah tentara

Semua pernyataan pikiran yang mengungkapkan keinginan dan kehendak tidak dapat dinilai benar dab salahnya bukanlah proposisi, seperti:

            Semoga Tuhan selalu melindungimu

            Ambilkan aku segelas air

            Alangkah cantiknya gadis itu

Macam-macam Proposisi    

  Proposisi menurut bentuknya ada tiga macam, yaitu: Proposisi Kategorik, Proposisi Hipotetik, dan Proposisi Disjungtif. 

1.    Proposisi Kategoris

Proposisi kategoris adalah proposisi yang menerangkan identitas atau kebedaan dua konsep objektif. Indentitas atau kebedaan yang diterangkan dapat formal atau objektif, dapat utuh atau parsial.

Proposisi kategoris yang paling sederhana terdiri dari :

1.      Subjek: hal yang diterangkan.

2.      Predikat: hal yang menerangkan.

3.      Kopula.

4.      Quantifier. 

Subyek, sebagaimana kita ketahui, adalah term yang menjadi pokok pembicaraan. Predikat adalah term yang menerangkan subyek. Kopula adalah kata yang menyatakan hubungan antara term subyek dan term predikat. Sedangkan quantifier adalah kata yang menunjukkan banyaknya satuan yang diikat oleh term subyek. Quantfier ada kalanya menunjuk kepada permasalahan universal, seperti kata: seluruh, semua, segenap, setiap, tidak satu pun; ada kalanya menunjuk kepada permasalahan partikular, seperti: sebagian, kebanyakan, beberapa, tidak semua, sebagian besar, hampir seluruh, rata-rata, [salah] seorang di antara; [salah] sebuah di antara ; ada kalanya menunjuk kepada permasalahan singular, tetapi untuk permasalahan singular biasanya quantfier tidak dinyatakan. Apabila quantifier suatu proposisi menunjuk kepada permasalahan universal maka proposisi itu disebut proposisi universal; apabila menunjuk kepada permasalahan partikular disebut proposisi partikular, dan apabila menunjuk kepada permasaiahan singular, disebut proposisi singular.

Perlu diketahui, meskipun dalam suatu proposisi tidak dinyatakan quantifiernya tidak berarti subyek dari proposisi tersebut tidak mengandung pengertian banyaknya satuan yang diikatnya. Dalam keadaan apapun subyek selalu mengandung jumlah satuan yang diikat. Lalu bagaimana menentukan kuantitas dari proposisi yang tidak dinyatakan quantifiernya. Kita dapat mengetahui lewat hubungan pengertian antara subyek dan predikatnya.

Kopula, adalah kata yang menegaskan hubungan term subyek dan term predikat baik hubungan mengiakan maupun hubungan mengingkari. Bila ia berupa ‘adalah’ berarti mengiakan dan bila berupa ‘tidak, bukan atau tak’ berarti mengingkari. Kopula menentukan kualitas proposisinya. Bila ia mengiakan, proposisinya disebut proposisi positif dan bila mengingkari disebut proposisi negatif. Kopula dalam proposisi positif kadang-kadang dinyatakan dan kadang-kadang tidak (tersembunyi). Kopula pada proposisi negatif tidak rnungkin disembunyikan, karena bila demikian berarti mengiakan hubungan antara term subyek dan predikatnya.

Dengan quantifier dapat kita ketahui kuantitas proposisi tertentu, apakah universal, partikular ataukah singular, dan dengan kopula bisa kita ketahui kualitas proposisi itu apakah positif ataukah negatif. Dari kombinasi antara kuantitas dan kualitas proposisi maka kita kenal enam macam proposisi, yaitu:

a)      Universal positif

b)      Partikular positif

c)      Singular positif            

d)     Universal negatif

e)      Partikular negatif

f)       Singular negative

a.       Proposisi universal positif,

kopulanya mengakui hubungan subyek dan predikat secara keseluruhan, dalarn Logika dilambangkan dengan huruf A.

b.       Proposisi partikular positif

kopulanya mengakui hubungan subyek dan predikat sebagian saja dilambangkan dengan huruf I.

c.       Proposisi singular positif

karena kopulanya mengakui hubungan subyek dan predikat secara keseluruhan maka juga dilambangkan dengan huruf A. Huruf Adan I masing masing sebagai lambang proposisi universal positif dan partikular positif diambil dari dua huruf hidup pertama kata Latin Affirmo yang berarti mengakui.

d.      Proposisi universal negatif

kopulanya mengingkari hubungan subyek dan predikatnya secara keseluruhan, dalam Logika dilambangkan dengan huruf E.

e.       Proposisi partikular negatif

kopuanya mengingkari hubungan subyek dan predikat sebagian saja, dilambangkan dengan huruf O.

f.       Proposisi singular negatif

karena kopulanya mengingkari hubungan subyek dan predikat secara keseluruhan, juga dilambangkan dengan huruf E. Huruf E dan 0 yang dipakai sebagai lambang tersebut diambil dari huruf hidup dalam kata nEgO, bahasa Latin yang berarti menolak atau meng¬ngkari.

Dengan pembahasan di atas maka kita mengenal lambang, permasalahan dan rumus proposisi sebagai berikut:

Lambang Permasalahan Rumus A Universal positif Semua S adalah P I Partikular positif Sebagian S adalah P E Universal negatif Semua S bukan P 0 Partikular negatif Sebagian S bukan P

Dalam menentukan apakah suatu proposisi itu positif atau negatif, kita tidak boleh semata-mata berdasarkan ada tidaknya indikator negatifnya, yaitu: tak, tidak atau bukan. Indikator itu menentukan negatifnya suatu proposisi apabila ia berkedudukan sebagai kopula. Bila indikator tidak berkedudukan sebagai kopula proposisi Itu adalah positif. 

                Selainproposisi kategoris ada juga bentuk-bentuk proposisi lainnya yaitu: kompleks, majemuk, dan modal.

1)      Proposisi Kompleks

Proposisi kompleks adalah proposisi yang subjek dan predikatnya atau juga kedua-duanya merupakan term-term kalimat yang kompleks; misalnya: Buku yang saya berikan kepadamu adalah kumpulan sajak dari W.S. Rendra.

2)      Proposisi Majemuk

Proposisi Majemuk adalah proposisi yang memuat berbagai subjek atau berbabagi predikat. Dengan demikian, proposisi majemuk sesungguhnya mengandung berbagai atau sejumlah penuturan. Tetapi hal tersebut bisa jelas atau tidak jelas.

3)      Proposisi Modal

Proposisi modal adalah proposisi yang dengan terang mengungkapkan apakah macam identitas (atau kebedaan) yang terdapat antara subjek atau predikat. 

2.      Proposisi Hipotetis

            Proposisi hipotetis adalah proposisi yang antara bagian-bagiannya terdapat hubungan dependensi (ketergantungan), oposisi, kesamaan, dan lain-lain.   Jadi, proposisi hipotetis berbeda dari proposisi kategoris baik dalam materi maupun bentuknya. Hal tersebut bisa kita rumuskan sebagai berikut:

1)      Materi suatu proposi hipotetis bukanlah subjek dan predikat, melainkan bagian-bagian yang diantaranya diterangkan terdapat hubungan.

2)      Bentuk bukanlah identitas atau kebedaan yang diungkapkan oleh unsur penghubung (kopula), melainkan suatu hubungan lain yang ditunjukkan oleh partikel-partikel konjungtif.

Proposisi hipotetis  (ut sic) hanya memuat sebuah  penuturan.  

3.      Proposisi Disjungtif

            Proposisi disjungtif adalah yang dua bagiannya dihubungkan dengan kata “apabila”, “jika tidak”, dan lain-lain. Pada hakikanya proposisi disjungtif juga terdiri dari dua buah proposisi kategorika. Sebuah proposisi disjungtif seperti : “proposisi itu benar” dan “proposisi itu salah”. Kopula (penghubung kalimat) yang berupa “jika”dan “maka” mengubah dua proposisi kategorik menjadi permasalahan dijungtif. Kopula dari proposisi disjungtif berfariasi sekali, seperti;

            Hidup kalau tidak bahagia adalah susah

            Hasan di rumah atau di sekolah

            Jika bukan Hasan yang mencuri maka Budi

EVALUASI VALIDITAS ARGUMEN

Pembuktian validitas ekspresi-ekspresi logika dari suatu argumen dapat dilakukan dengan tabel kebenaran. Pertama harus memberikan variabel proposisional pada tiap proposisi argumen dan kemudian membentuk proposisi majemuk untuk tiap pernyataan, dan kemudian mengevaluasi dengan tabel kebenaran.

Contoh 1

Jika anda mengambil mata kuliah logika matematika, dan jika anda tidak memahami tautologi, maka anda tidak lulus.

Untuk membuktikan validitasnya, buat variabel proposisional yang relevan

P = Anda mengambil mata kuliah logika matematika

Q = Anda memahami tautologi

 R = Anda lulus

Sehingga bentuk ekspresi logikanya seperti berikut :

(P∧~Q)→~R

Selanjutnya buat tabel kebenarannya dengan semua nilai kebenaran P, Q, dan R yang memungkinkan.

P Q R ~Q ~R (P∧~Q) (P∧~Q)→~R

F F F T T F T

F F T T F F T

F T F F T F T

F T T F F F T

T F F T T T T

T F T T F T F

T T F F T F F

T T T F F F T

Untuk membuat pernyataan yang nantinya pernyataan-pernyataan dalam argumen tersebut dapat diubah menjadi ekspresi logika dapat menggunakan cara heuristik berikut :

Heuristik untuk mengubah pernyataan menjadi ekspresi logika :

Ambil pernyataan-pernyataan yang pendek, tanpa kata “dan”, “atau”, “jika…maka…”,”…jika dan hanya jika…”, pada pernyataan tersebut yang bisa dijawab benar atau salah.

Ubahlah pernyataan-pernyataan yang pendek tersebut dengan variabel-variabel proposisional.

Rangkailah variabel-variabel proposisional dengan perangkai yang relevan

Bentuklah menjadi proposisi majemuk jika memungkinkan dengan memberi tanda kurung biasa yang tepat.

Contoh 2

Jika Badu belajar rajin dan sehat, maka Badu lulus ujian, atau jika Badu tidak belajar rajin dan tidak sehat, maka Badu tidak lulus ujian.

Langkah 1 

Menentukan proposisi yang tepat

Badu rajin belajar

Badu sehat

Badu lulus ujian

Langkah 2

Mengganti proposisi dengan variabel proposisi

P = Badu rajin belajar

Q = Badu sehat

R = Badu lulus ujian

Langkah 3

Perangkai yang relevan adalah implikasi, negasi,  disjungsi dan konjungsi.

Langkah 4

Ubah menjadi ekspresi logika berupa proposisi majemuk

((P∧Q)→R))∨((~P∧~Q)→~R)

TAUTOLOGI

Argumen yang dibuktikan validitasnya dengan tabel kebenaran harus menunjukan nilai benar sehingga argumen tersebut valid. Jika pada tabel kebenaran untuk semua pasangan nilai variabel proposisional bernilai benar atau T, maka disebut Tautologi.

Contoh 3

Buktikan : ~(P∧Q)∨Q adalah tautologi ?

Bukti : buat tabel kebenarannya seperti berikut :

P Q P∧Q ~(P∧Q) ~(P∧Q)∨Q

F F F T T

F T F T T

T F F T T

T T T F T

Jadi ekspresi diatas adalah tautologi. Tautologi dapat ditulis dengan simbol ⊧ (metasymbol, bukan perangkai logika) sehingga ekspresi logika dapat ditulis  ⊧~(P∧Q)∨Q  

Contoh 4

Diketahui : jika ~(P∧Q)∨Q  adalah tautologi

Buktikan : ~((P∨Q)∧R)∨R juga tautologi

Bukti      : 

Gunakan skema A dan B 

Masukan ke ekspresi logika pertama menjadi   ~(A∧B)∨B  

Misalkan  A = ~(P∧Q), sedangkan B = Q, lalu masukan ke ekspresi logika yang dibuktikan. Maka : ~((P∨Q)∧R)∨R akan menjadi ~(A∧B)∨B  

dan (2) akan terlihat sama, jadi disebut tautologi.

KONTRADIKSI

Kebalikan dari tautologi adalah kontradiksi atau absurditas, yaitu jika semua pasangan nilai dari tabel kebenaran menghasilkan nilai F.

Definisi : suatu ekspresi logika yang selalu bernilai salah di dalam tabel kebenarannya tanpa memperudlikan nilai kebenara dari proposisi-proposisi yang berada didalamnya, disebut kontradiksi.

Contoh 5

P ~P P∧~P

F T F

T F F

 Pada argumen, suatu kontradiksi dapat dijumpai jika antara premis-premis bernilai T, sedangkan kesimpulan bernilai F. hal ini tak mungkin terjadi, karena premis yang benar harus menghasilkan kesimpulan benar. 

CONTIGENT

Jika semua nilai kebenaran menghasilkan nilai F dan T, disebut contigent atau formula campuran (mixed formulae). 

Contoh 6

((P∧Q)→R)→P

Tabel kebenarannya

P Q R P∧Q (P∧Q)→R ((P∧Q)→R)→P

F F F F T F

F F T F T F

F T F F T F

F T T F T F

T F F F T T

T F T F T T

T T F T F T

T T T T T T

PENGGUNAAN TAUTOLOGI

Beberapa hal penting yang mengakibatkan tautologi, yaitu :

Implikasi secara logis (logical implication). Misalnya P dan Q adalah dua buah ekspresi logika, maka jika dikatakan P secara logis mengimplementasikan Q dapat ditulis dengan  P⇒Q .

Ekivalen secara logis (logical equivalence) misalnya P dan Q adalah dua buah ekspresi logika, maka jika dikatakan P ekivalen dengan Q, dapat ditulis dengan P ≡Q. Di sini disyaratkan  P≡Q, jika dan hanya jika P↔Q adalah tautologi.

Terdapat dua jenis implikasi yaitu :

Implikasi material (material implication), contoh : P→Q. Tbel kebenaran untuk implikasi berlaku.

Implikasi logis (logical implication), contoh : P⇒Q. Ini dapat dibaca “menyebabkan”, sebagai contoh : P = T, maka P pasi tautologi. Jika P = F, maka P pasti kontradiksi. Jika T⇒P, maka A pasti taotologi, dan jika F⇒P, maka P kontradiksi.

LATIHAN

Soal 1

Tentukan apakah dari ekspresi-ekspresi logika berikut ini termasuk tautologi, kontradiksi atau contigent

P→(Q→P)

(Q→P)→P

~~P→P

(~P→~Q)→(Q→P)

(P→(Q→R) )→((P→Q)→(P→R) )

(P∧(P→Q) )→Q

((P→Q)↔(~P∨Q)

((P→Q)∧(Q→R))→(P→R)

((P→Q)↔((P∧Q)∨(~P∧~Q))

(Q∧(P→Q))→P

Soal 2

Jika (P∨~P) adalah tautologi, buktikan bahwa ekspresi-ekspresi logikaberikut ini adalah tautologi

(P→Q)∨~(P→Q)

~P∨~~P

((P∧R)∨Q)∨~((P∧R)∨Q)

Soal 3

Dibawah ini adalah argumen yang disebut destructive dilemma. 

Jika Badu senang, maka Siti senang, dan jika Badu sedih, maka Siti sedih. Siti tidak senang atau Siti tidak sedih. Dengan demikian, Badu tidak senang atau Badu tidak sedih.

Buat ekspresi logikanya dan buktikan apakah termasuk tautologi, kontradiksi atau contigent dengan tabel kebenaran.

EKUIVALEN LOGIS 

Jika dua buah ekspresi logika adalah tautologi, maka kedua buah ekspresi logika ekuivalen secara logis, demikian juga jika kontradiksi. Dalam contingent, jika nilai T atau F pada tabel kebenaran dalam urutan yang sama, maka tetap disebut ekuivalen secara logis.

Contoh 7

P = Dea sangat cantik dan ramah

Q = Dea ramah dan sangat cantik

Ekspresi logikanya : 

P∧Q

Q∧P

Kedua ekspresi logika tersebut ekuivalen secara logis, maka ditulis :

(P∧Q)≡(Q∧P)

Dengan tabel kebenaran :

P Q (P∧Q) (Q∧P)

F F F F

F T F F

T F F F

T T T T

Definisi : proposisi P dan Q disebut ekuivalen secara logis  jika P⟷Q adalah tautologi. Notasi atau simbol P≡Q menandakan bahwa P dan Q adalah ekuivalen secara logis. Proposisi dapat digantikan dengan ekspresi logika berupa proposisi majemuk.

KOMUTATIF 

Jika variabel dua proposisional dapat saling berganti tempat tanpa mengubah nilai kebenaran dari kedua ekspresi logika karena tetap memiliki nilai kebenaran yang sama disebut komutatif (commutativity)

Perangkai logika yang memiliki sifat komutatif adalah ∧,∨,dan ⟷.

Jadi 

(P∧Q)≡(Q∧P)

(P∨Q)≡(Q∨P)

(P↔Q)≡(Q↔P)

Adalah ekspresi logika yang komutatif.

ASOSIATIF

Jika diterapkan pada sua buah ekspresi logika, penempatan tanda kurung dapat diubah tanpa mengubah nilai kebenarannya pada tabel kebenaran.

Contoh 8

((P∧Q)∧R) dan (P∧(Q∧R)). 

Maka tabel kebenarannya

P Q R (P∧Q) ((P∧Q)∧R) Q∧R (P∧(Q∧R))

F F F F F F F

F F T F F F F

F T F F F F F

F T T F F T F

T F F F F F F

T F T F F F F

T T F T F F F

T T T T T T T

Karena tanda kurungnya dapat dipindah tanpa mengubah nilai kebenaran, maka disebut asosiatif. Perangkai logika lain yang memiliki sifat asosiatif adalah ∨,dan ↔.

Perlu diperhatikan bahwa jika perangkainya berbeda dalam satu ekspresi logika, kurung tidak dapat dipindah sembarangan.

HUKUM-HUKUM LOGIKA

Hukum-hukum logika diambil dari ekspresi-ekspresi logikaberdasarka pernyataan-pernyataan sehingga tetap dapat dibuktikan kebenarannya melalui pernyataan tersebut.

Berikut adalah hukum-hukum logika yang ekuivalen

EKUIVALEN LOGIS NAMA

P∧1≡P

P∨0≡P Indenitity of ∧ 

Zero of ∨

P∨1≡1

P∧0≡0 Indenitity of ∧ 

Zero of ∧

P∨~P≡1

P∧~P≡0 Tautology 

Law of contradiction

P∨P≡P

P∧P≡P Idempotence laws

Idempotence laws

~~P≡P Law of double negotion

P∧Q≡Q∧P

P∨Q≡Q∨P Comutativity

Comutativity 

(P∧Q)∧R≡P∧(Q∧R)

(P∨Q)∨R≡P∨(Q∨R) Assosiativity 

Assosiativity

P∧(Q∨R)≡(P∧Q)∨(Q∧R)

P∨(Q∧R)≡(P∨Q)∧(Q∨R) Distributivity 

Distributivity

P∧(P∨Q)≡P

P∨(P∧Q)≡P Absorption 

Absorption

P∧(~P∨Q)≡P∧Q

P∨(~P∧Q)≡P∨Q De Morgan’s Law

De Morgan’s Law

~(P∧Q)≡~P∨~Q

~(P∨Q)≡~P∧~Q

(P∧Q)∨(P∧~Q)≡P

P→Q≡~P∨Q

P→Q≡~(P∧~Q)

P↔Q≡(P∧Q)∨(~P∧~Q)

P↔Q≡(P→Q)∧(Q→P)

(P∧Q)∨(P∧~Q)≡P

(P∨Q)∧(P∨~Q)≡P

(P∧Q)∨(~P∧Q)≡Q

(P∨Q)∧(~P∨Q)≡Q

LATIHAN 

Soal 1 

Buktikan bahwa ekspresi-ekspresi logika berikut ekuivalen dengan menggunakan tabel kebenaran :

~P↔Q≡(~P∨Q)∧(~Q∨P)

P→(~P→Q)≡1

(P∨~Q)→R≡(~P∧Q)∨R

P→(Q→R)≡(P→Q)→R

P→Q≡~(P∧~Q)

~(~(P∧Q)∨Q)≡0

((P∧(Q→R) )∧(P→(Q→~R) ))→P≡1

Soal 2

Buktikan hukum-hukum logika

Silogisme hipotetis

Silogisme disjungtif

Modus ponen

Modus tolen

Adalah ekuivalen dengan 1 atau tautologi.

Logika Predikat

Logika Predikat adalah perluasan dari logika proposisi dimana objek yang dibicarakan dapat berupa anggota kelompok. 

Logika proposisi (ingat kembali) menganggap proposisi sederhana (kalimat) sebagai entitas tunggal  Sebaliknya, logika predikat membedakan subjek dan predikat dalam sebuah kalimat. 

Ingat tentang subjek dan predikat dalam kalimat?

Penerapan Logika 

Predikat Merupakan notasi formal untuk menuliskan secara sempurna definisi, aksioma, teorema matematika dengan jelas, tepat dan tidak ambigu pada semua cabang matematika. 

Logika predikat dengan simbol-simbol fungsi, operator “=”, dan beberapa aturan pembuktian cukup untuk mendefinisikan sistem matematika apapun, dan juga cukup untuk membuktikan apapun yang dapat dibuktikan pada sistem tersebut.

Penerapan Praktis 

Merupakan basis untuk mengekspresikan spesifikasi formal untuk sistem kompleks apapun dengan jelas 

Merupakan basis untuk automatic theorem provers dan sistem cerdas lainnya 

Didukung oleh beberapa database query engines canggih dan container class libraries

Subjek dan Predikat 

Pada kalimat “Kucing itu sedang tidur”: 

frase “kucing itu” merupakan subjek kalimat 

frase “sedang tidur” merupakan predikat kalimat- suatu properti yang bernilai TRUE untuk si subjek (objek pelaku) 

dalam logika predikat, predikat dimodelkan sebagai sebuah fungsi P(•) dari objek ke proposisi. 

P(x) = “x sedang tidur” (x adalah sembarang objek).

Predikat 

Konvensi: varibel huruf kecil x, y, z... Menyatakan objek/entitas; variabel huruf besar P, Q, R… menyatakan fungsi proposisi (predikat). 

Perhatikan bahwa hasil dari menerapkan sebuah predikat P kepada objek x adalah sebuah proposisi P(x). Tapi predikat P sendiri (e.g. P=“sedang tidur”) bukan sebuah proposisi 

Contoh: jika P(x) = “x adalah bilangan prima”, P(3) adalah proposisi “3 adalah bilangan prima.”

Fungsi Proposisi 

Logika predikat dapat digeneralisir untuk menyatakan fungsi proposisi dengan banyak argumen. 

Contoh: Misalkan P(x,y,z) = “x memberikan pada y nilai z”, maka jika x=“Mike”, y=“Mary”, z=“A”, maka P(x,y,z) = “Mike memberi Mary nilai A.”

Fungsi proposisi (kalimat terbuka) : Pernyataan yang mengandung satu buah variabel atau lebih. 

Contoh : 

x - 3 > 5. Misalkan kita sebut fungsi proposisi ini sebagai P(x), dimana P adalah predikat dan x adalah variabel. 

Apakah nilai kebenaran kebenaran dari P(2) ? Salah 

Apakah nilai kebenaran kebenaran dari P(8) ? Salah 

Apakah nilai kebenaran kebenaran dari P(9) ? Benar

Fungsi Proposisi 

Tinjau fungsi proposisi Q(x, y, z) yg didefinisikan:  x + y = z. 

Disini, Q adalah predikat dan x, y, and z adalah variabel. 

Apakah nilai kebenaran kebenaran dari Q(2, 3, 5) ? Benar

Apakah nilai kebenaran kebenaran dari Q(0, 1, 2) ?  Salah 

Apakah nilai kebenaran kebenaran dari Q(9, -9, 0) ? Benar 

Semesta Pembicaraan

Salah satu kelebihan predikat adalah bahwa predikat memungkinkan kita untuk menyatakan sesuatu tentang banyak objek pada satu kalimat saja. 

Contoh, misalkan P(x)=“x+1>x”. Kita dapat menyatakan bahwa “Untuk sembarang angka x, P(x) bernilai TRUE” hanya dengan satu kalimat daripada harus menyatakan satu-persatu: (0+1>0) ∧ (1+1>1) ∧ (2+1>2) ∧ ... 

Kumpulan nilai yang bisa dimiliki variabel x disebut semesta pembicaraan untuk x (x’s universe of discourse)

Ekspresi Quantifier 

Quantifiers merupakan notasi yang memungkinkan kita untuk mengkuantifikasi (menghitung) seberapa banyak objek di semesta pembicaraan yang memenuhi suatu predikat. 

“∀” berarti FOR∀LL (semua) atau universal quantifier. ∀x P(x) berarti untuk semua x di semesta pembicaraan, P berlaku. 

“∃” berarti ∃XISTS (terdapat) atau existential quantifier. ∃x P(x) berarti terdapat x di semesta pembicaraan. (bisa 1 atau lebih) dimana P(x) berlaku.

Predikat & Kuantifier 

Pernyataan “x > 3” punya 2 bagian, yakni “x” sebagai subjek dan “ adalah lebih besar 3” sebagai predikat P. Kita dpt simbolkan pernyataan “x > 3” dengan P(x). Sehingga kita dapat mengevaluasi nilai kebenaran dari P(4) dan P(1). 

Subyek dari suatu pernyataan dapat berjumlah lebih dari satu. Misalkan Q(x,y): x - 2y > x + y

Kuantifikasi Universal ∀ 

Mis. P(x) suatu fungsi proposisi. 

Kalimat yg dikuantifikasi secara universal : 

Untuk semua x dalam semesta pembicaraan, P(x) adalah benar. 

Dengan kuantifier universal ∀: 

 ∀x P(x) “untuk semua x P(x)” atau 

 “untuk setiap x P(x)” 

(Catatan: ∀x P(x) bisa benar atau salah, jadi merupakan sebuah proposisi, bukan fungsi proposisi.)

Kuantifikasi Universal ∀ 

Contoh : 

S(x): x adalah seorang mahasiswa IT. 

G(x): x adalah seorang yang pandai. 

Apakah arti dari ∀x (S(x) → G(x)) ? 

“Jika x adalah mahasiswa IT, maka x adalah seorang yang pandai” 

atau 

“Semua mahasiswa IT pandai.”

Kuantifikasi Universal ∀ 

Contoh: 

Misalkan semesta pembicaraan x adalah tempat parkir di Kantor. Misalkan P(x) adalah predikat “x sudah ditempati.” 

Maka universal quantification untuk P(x), ∀x P(x), adalah proposisi: { “Semua tempat parkir di Kantor sudah ditempati” { atau, “Setiap tempat parkir di kantor sudah ditempati”

Kuantifikasi Eksistensial ∃ 

Kalimat yang di-kuantifikasi secara eksistensial: 

Ada x di dalam semesta pembicaraan dimana P(x) benar. 

Dengan peng-kuantifikasi eksistensial ∃: 

∃x P(x) “Ada sebuah x sedemikian hingga P(x).” 

“Ada sedikitnya sebuah x sedemikian z hingga P(x).” 

(Catatan: ∃x P(x) bisa benar atau salah, jadi merupakan sebuah proposisi, tapi bukan fungsi proposisi.)

Kuantifikasi Eksistensial ∃ 

Contoh : 

P(x): x adalah seorang dosen IT. 

G(x): x adalah seorang yang pandai. 

Apakah arti ∃x (P(x) ∧ G(x)) ? 

“Ada x sedemikian hingga x adalah seorang dosen IT dan x adalah seorang yang pandai.” zatau 

“Sedikitnya satu orang dosen IT adalah seorang yang pandai.”

Disproof dengan counterexample 

Counterexample dari ∀x P(x) adalah sebuah objek c sehingga P(c) salah. 

Pernyataan seperti ∀x (P(x) → Q(x)) dapat di-disproof secara sederhana dengan memberikan counterexamplenya. 

Pernyataan Pernyataan: “Semua burung bisa terbang terbang.” Disproved Disproved dengan counterexample counterexample: Penguin Penguin.

Variabel bebas dan variabel terikat

Sebuah ekspresi seperti P(x) dikatakan memiliki variabel bebas x (berarti, x tidak ditentukan). 

Sebuah quantifier (∀ atau ∃) berlaku pada sebuah ekspresi yang memiliki satu atau lebih variabel bebas, dan mengikat satu atau lebih variabel tersebut, untuk membentuk ekspresi yang memiliki satu atau lebih variabel terikat.

Contoh Pengikatan 

P(x,y) memiliki 2 variabel bebas, x dan y. 

∀x P(x,y) memilki 1 variabel bebas, dan 1 variabel terikat. [yang mana?] 

“P(x), dimana x=3” adalah cara lain mengikat x. 

Ekspresi dengan nol variabel bebas adalah sebuah proposisi bonafit (nyata) 

Ekspresi dengan satu atau lebih variabel bebas adalah sebuah predikat: ∀x P(x,y)

Negasi 

Hubungan antara kuantor universal dengan kuantor eksistensial 

E1 : ¬( ∀ x ) p ( x ) ≡ ( ∃ x ) ¬p ( x ) 

E2 : ¬( ∃ x ) p ( x ) ≡ ( ∀ x ) ¬p ( x ) 

E3 : ¬(∀x)p(x)→q(x) ≡ (∃x) p(x) ∧ ¬q(x) 

E4 : ¬(∃x)p(x) ∧ q(x) ≡ (∀x) p(x)→¬q(x)

“Setiap mhs dalam kelas ini telah mengambil Kalkulus I” 

[∀x P(x)] 

Apakah negasi dari pernyataan ini….? 

“Ada seorang mhs dalam kelas ini yang belum mengambil Kalkulus I” [ ∃x ¬ P(x)] 

Jadi, ¬ ∀x P(x) ≡ ∃x ¬ P(x).

Kuantifier Bersusun (Nested Quantifier) 

∀x ∀y (x+y = y+x) 

berarti x+y = y+x berlaku untuk semua bilangan real x dan y. 

∀x ∃y (x+y = 0) 

berarti untuk setiap x ada nilai y sehingga x+y = 0. 

∀x ∀y ∀z (x+(y+z) = (x+y)+z) 

berarti untuk setiap x, y dan z berlaku hukum asosiatif x+(y+z) = (x+y)+z.

Rumusan penting 

(∀x) (∀y) p(x,y) ↔ (∀y) (∀x) p(x,y) 

(∀x) (∀y) p(x,y) → (∃y) (∀x) p(x,y) 

(∃y) (∀x) p(x,y) → (∀x) (∃y) p(x,y) 

(∀x) (∃y) p(x,y) → (∃y) (∃x) p(x,y) 

(∃x) (∃y) p(x,y) ↔ (∃y) (∃x) p(x,y)

Konvensi 

Terkadang semesta pembicaraan dibatasi dalam quantification, contoh, ƒ 

∀x>0 P(x) adalah kependekan dari “untuk semua x lebih besar dari nol, P(x) berlaku.” = ∀x (x>0 → P(x)) ƒ 

∃x>0 P(x) adalah kependekan dari “ada x lebih besar dari nol yang membuat P(x) ” = ∃x (x>0 Λ P(x))

Aturan Ekivalensi Quantifier 

Definisi quantifiers: 

semesta pemb. =a,b,c,… 

∀x P(x) ⇔ P(a) ∧ P(b) ∧ P(c) ∧ … 

∃x P(x) ⇔ P(a) ∨ P(b) ∨ P(c) ∨ … 

Kemudian kita bisa membuktikan aturan: 

∀x P(x) ⇔ ¬∃x ¬P(x) 

∃x P(x) ⇔ ¬∀x ¬P(x)

Membuat Quantifier Baru 

Sesuai namanya, quantifier dapat digunakan untuk menyatakan bahwa sebuah predikat berlaku untuk sembarang kuantitas (jumlah) objek. 

Definisikan ∃!x P(x) sebagai “P(x) berlaku untuk tepat satu x di semesta pembicaraan.” 

∃!x P(x) ⇔ ∃x (P(x) ∧ ¬∃y (P(y) ∧ y≠ x)) “Ada satu x dimana P(x) berlaku, dan tidak ada y dimana P(y) berlaku dan y berbeda dengan x.”

RELASI

       Relasi adalah hubungan antara dua elemen dua himpunan. Relasi juga dikatakan sebagai suatu aturan yang memasangkan anggota himpunan satu ke himpunan lain. Suatu relasi dari himpunan A ke himpunan B adalah pemasangan atau korespondensi dari anggota-anggota himpunan A ke anggota-anggota himpunan B. relasi dari himpunan A ke himpunan B adalah aturan yang memasangkan anggota himpunan A dan anggota himpunan B dengan aturan tertentu.

Contoh :

Ada tiga anak mengatakan makanan kesukaan nya yaitu : Anis menyukai Bakso, Rina menyukai Sate dan Diko menyukai Nasi Padang.

Dari pernyataan di atas terdapat dua himpunan yaitu :

A= himpunan anak {Anis,Rina,Diko}

B= himpunan makanan {Bakso. Sate, Nasi Padang}

Relasi antara anggota himpunan A ke himpunan B yang mungkin adalah menyukai atau menyenangi.

Dari contoh di atas, himpunan A disebut domain (daerah asal) dan himpunan B disebut kodomain (daerah kawan). Sementara itu menyukai disebut Relasi. Himpunan semua anggota kodomain disebut Range (daerah hasil).

Metode Menyatakan Relasi

Relasi dapat dinyatakan dengan tiga cara, yaitu:

1)   Dengan himpunan pasangan berurutan

2)   Dengan diagram panah

3)   Dengan diagram Cartesius

4)   Dengan Tabel

Contoh :

A = { Buyung, Doni, Vita, Putri}   dan B = { IPS, Kesenian, Keterampilan, Olahraga, Matematika, IPA, Bahasa Inggris} dan relasi yang menghubungkan antara himpunan A dan hipunan B adalah “pelajaran yang disukai”

Keterangan : Buyung suka IPS dan Kesenian, Doni suka Keterampilan dan Olahraga, Vita suka IPA, dan Putri suka Matematika dan Bahasa Inggris.

Jawaban dengan tiga metode :

1)  Dengan himpunan pasangan berurutan

Himpunan yang anggotanya semua pasangan berurutan (x,y) dinamakan himpunan pasangan berurutan.

{(Buyung, IPS), (Buyung, Kesenian), (Doni, Keterampilan), (Doni, Olahraga), (Vita, IPA), (Putri, Matematika), (Putri, Bahasa Inggris)}

2)  Dengan Diagram Panah

Langkah-langkah menyatakan relasi dengan diagram panah :

a.    Membuat dua lingkaran atau elips

b.   Untuk meletakkan anggota himpunan A dan anggota himpunan B x=A diletakkan pada lingkaran A dan y=B diletakkan pada lingkaran B

c.    X dan Y dihubungkan dengan anak panah

d.   Arah anak panah menunjukkan arah relasi

e.    Anak panah tersebut mewakili aturan relasi

3)  Dengan diagram Cartesius

Pada diagram Cartesius diperlukan dua salip sumbu yaitu : sumbu mendatar (horizontal) dan sumbu tegak (vertical) yang berpotongan tegak lurus.

a.   X= A diletakkan pada sumbu mendatar

b.   Y= B diletakkan pada sumbu tegak

c.   Pemasangan (x,y) ditandai dengan sebuah Noktah (titik) yang koordinatnya ditulis sebagai pasangan berurutan x,y.

4)  Tabel

Nama Mata Pelajaran

Buyung IPS

Buyung Kesenian

Doni Keterampilan

Doni Olahraga

Vita IPA

Putri Matematika

Putri Bahasa Inggris

Sifat-Sifat Relasi

a.      Relasi Refleksif ( Bercermin)

Relasi disebut refleksif jika dan hanya jika untuk setiap x anggota semesta-nya, x berelasi dengan dirinya sendiri. Jadi R refleksif jika dan hanya jika xRx.

Contoh :

Jika diketahui A= {1,2,3,4} dan relasi R= {(1,1), (2,2), (3,3), (4,4)} Pada A, maka R x∈A adalah refleksif, karena untuk setiap x∈A terdapat (x,x) pada R.

Perhatikan relasi pada himpunan = {1,2,3,4} berikut:

R1= {(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4)}

R2= {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}

Relasi-relasi tersebut merupakan relasi refleksif karena memiliki elemen (1,1), (2,2), (3,3), dan (4,4).

b.      Relasi Irrefleksif

Relasi R pada A disebut Irrefleksif (anti refleksif) jika dan hanya jika setiap elemen di dalam tidak berelasi dengan dirinya sendiri. Jadi, irrefleksif jika dan hanya jika xRx.

Contoh :

Diketahui himpunan B= {a,b,c} dan relasi R= {(a,c), (b,c), (b,a)}. Relasi R adalah irrefleksif, karena (a,a), (b,b), dan (c,c) bukan elemen.

Diketahui A= {1,2,3,4} dan relasi R= {(2,1), (3,2), (4,1), (4,2), (4,3)}. Relasi R merupakan relasi irrefleksif, karena tidak terdapat elemen (x,x), dimana x∈A.

c.       Relasi Nonrefleksif

Relasi R pada A disebut nonrefleksif  jika dan hanya jika ada sekurang-kurangnya satu elemen di dalam A  yang tidak berelasi dengan dirinya sendiri.

Contoh :

Perhatikan relasi pada himpunan A= {1,2,3,}

R= {(1,1), (1,2), (2,2), (2,3), (3,3)}

Relasi tersebut merupakan relasi non refleksif, karena ada (1,2) dan (2,3).

d.      Relasi Simetri

Relasi R disebut simetri pada S jika dan hanya jika setiap dua anggota a dan b dari S berlaku jika a berelasi R dengan b maka b juga berelasi dengan a.

Secara simbolik: aRb → bRa.

Contoh:

1. Relasi R = { (a,b), (b,a), (a,c), (c,a) } dalam himpunan {a, b, c}.

2. Ani menyukai Budi, Budi menyukai Ani {(Ani,Budi),(Budi,Ani)}

e.       Relasi Asimetri

Relasi R disebut asimetri pada S jika dan hanya jika setiap dua anggota a dan b dari S berlaku: jika a berelasi R dengan b maka b tidak berelasi R dengan a.

Secara simbolik: R asimetri pada S jhj (∀a,b∈S) aRb → bRa.

Contoh:

1. Relasi R = { (a,b), (b,c), (c,a) } dalam himpunan { a,b,c }.

f.       Relasi Nonsimetri

Relasi R disebut nonsimetri pada S jika dan hanya jika ada dua anggota a dan b dari S sedemikian hingga berlaku: a berelasi R dengan b tetapi b tidak berelasi R dengan a.

Perhatikan bahwa nonsimetri adalah negasi/ingkaran dari simetri.

Contoh:

1. Relasi R = { (a,b), (a,c), (c,a) } dalam himpunan {a, b, c}

g.      Relasi Antisimetri

Relasi R disebut antisimetri pada S jika dan hanya jika setiap dua anggota a dan b dari S berlaku: jika a berelasi R dengan b dan b berelasi R dengan a maka a=b.

Contoh:

1.  A = keluarga himpunan.

Relasi “ himpunan bagian” adalah relasi yang antisimetris pada A, karena  untuk setiap dua himpunan x dan y, jika x y dan y x, maka x = y.

2.   Relasi “kurang dari atau sama dengan (≤)” dalam himpunan bilangan real. Jadi, relasi “kurang dari atau sama dengan (≤)” bersifat anti simetri, karena jika a ≤ b dan b ≤ a berarti a = b.

3.    Relasi “habis membagi” pada himpunan bilangan bulat asli N merupakan contoh relasi yang tidak simetri karena jika a habis membagi b, b tidak habis membagi a, kecuali jika a = b. Sementara itu, relasi “habis membagi” merupakan relasi yang anti simetri karena jika a habis membagi b dan b habis membagi a maka a = b.

h.      Relasi Transitif

R adalah relasi pada A. R disebut relasi Transitif pada A jika dan hanya jika setiap 3 anggota himpunan A, (a,b,c ∈A) jika (a,b)∈R, dan (b,c)∈R maka (a,c)∈R (setiap tiga anggota a,b,c dari A, jika a berelasi dengan b dan b berelasi dengan c maka a berelasi dengan c).

Contoh:

1. Relasi R = {(a,b), (b,c), (a,c), (c,c) } dalam himpunan { a,b,c }.

i.        Relasi Nontransitif

R adalah relasi pada A. R disebut relasi nontransitif pada A jika dan hanya jika ada tiga anggota himpunan A, (a,b,c ∈A) sedemikian hingga (a,b)∈R , dan (b,c)∈R dan (a,c)∉R (ada tiga anggota a,b,c dari A sedemikian hingga a berelasi dengan b dan b berelasi dengan c dan a tidak berelasi dengan c).

Contoh:

R = {(1,2),(2,3),(3,4)} dalam himpunan { 1,2,3,4}

j.        Relasi Intransitif

R adalah relasi pada himpunan A. R disebut relasi intransitif pada A jika dan hanya jika setiap tiga anggota himpunan A, (a,b,c ∈A) jika (a,b)∈R dan (b,c)∈R maka (a,c)∉R (setiap tiga anggota a,b,c dari A, jika a berelasi dengan b dan b berelasi dengan c maka a tidak berelasi dengan c).

Misal E = {1,2,3}, R = {(1,2),(2,3),(2,5),(3,4),(5,7)}

Relasi di atas intransitif karena :

(1,2)∈R dan (2,3)∈R, tetapi (1,3)∉R

(1,2)∈R dan (2,5)∈R, tetapi (1,5)∉R

(2,3)∈R dan (3,4)∈R, tetapi (2,4)∉R

(2,5)∈R dan (5,7)∈R, tetapi (2,7)∉R

Komposisi Relasi

•     Misalkan :

        R adalah relasi dari himpunan A ke himpunan B

        T adalah relasi dari himpunan B ke himpunan C.

•     Komposisi R dan S, dinotasikan dengan T ο R, adalah relasi dari A ke C yang didefinisikan oleh :

       T ο R = {(a, c) a ∈A, c ∈C, dan untuk suatu b ∈ B sehingga (a, b) ∈R dan  (b, c) ∈ S }

Contoh komposisi relasi

Misalkan, A = {a, b, c}, B = {2, 4, 6, 8} dan C = {s, t, u}

Relasi dari A ke B didefinisikan oleh :

R = {(a, 2), (a, 6), (b, 4), (c, 4), (c, 6), (c, 8)}

Relasi dari B ke C didefisikan oleh :

T = {(2, u), (4, s), (4, t), (6, t), (8, u)}

Maka komposisi relasi R dan T adalah

T ο R = {(a, u), (a, t), (b, s), (b, t), (c, s), (c, t), (c, u)}

FUNGSI

Fungsi adalah bentuk khusus dari relasi. Sebuah relasi dikatakan fungsi jika xRy, untuk setiap x anggota A memiliki tepat satu pasangan, y, anggota himpunan B

Kita dapat menuliskan f(a) = b, jika b merupakan unsur di B yang dikaitkan oleh f untuk suatu a di A. Ini berarti bahwa jika f(a) = b dan f(a) = c maka b = c.

Jika f adalah fungsi dari himpunan A ke himpunan B, kita dapat menuliskan dalam bentuk :  f : A → B

Domain, Kodomain, Dan Range

•      f : A → B

•     A dinamakan daerah asal (domain) dari f dan B dinamakan daerah hasil (codomain) dari f.

•     Misalkan f(a) = b,

maka b dinamakan bayangan (image) dari a,

dan a dinamakan pra-bayangan (pre-image) dari b.

•     Himpunan yang berisi semua nilai pemetaan f dinamakan jelajah (range) dari f.

Penulisan Fungsi

1)    Himpunan pasangan terurut.

Misalkan fungsi kuadrat pada himpunan {1, 2, 3, 4, 5, 6, 7, 8, 9,10} maka fungsi itu dapat dituliskan dalam bentuk :

f = {(2, 4), (3, 9)}

2)    Formula pengisian nilai (assignment)

 f(x) = x2 + 10,

 f(x) = 5x

Jenis-jenis Fungsi

Fungsi konstan (fungsi tetap)

Suatu fungsi f : A → B ditentukan dengan rumus f(x) disebut fungsi konstan apabila untuk setiap anggota domain fungsi selalu berlaku f(x) = C, di mana C bilangan konstan. Untuk lebih jelasnya, pelajarilah contoh soal berikut ini.

Diketahui f : R → R dengan rumus f(x) = 3 dengan daerah domain: {x | –3 ≤ x < 2}. Sehingga, gambar grafiknya.

Fungsi linear

Suatu fungsi f(x) disebut fungsi linear apabila fungsi itu ditentukan oleh f(x) = ax + b, di mana a ≠ 0, a dan b bilangan konstan dan grafiknya berupa garis lurus. Perhatikan contoh berikut.

Diketahui f(x) = 2x + 3, gambar grafiknya

Fungsi Kuadrat

Suatu fungsi f(x) disebut fungsi kuadrat apabila fungsi itu ditentukan oleh f(x) = ax2 + bx + c, di mana a ≠ 0 dan a, b, dan c bilangan konstan dan grafiknya berupa parabola. Perhatikan contoh fungsi kuadrat  berikut.

Fungsi f ditentukan oleh f(x) = x2 + 2x – 3, gambar grafiknya.

 

Fungsi identitas

Suatu fungsi f(x) disebut fungsi identitas apabila setiap anggota domain fungsi berlaku f(x) = x atau setiap anggota domain fungsi dipetakan pada dirinya sendiri. Grafik fungsi identitas berupa garis lurus yang melalui titik asal dan semua titik absis maupun ordinatnya sama. Fungsi identitas ditentukan oleh f(x) = x. 

Sifat-sifat Fungsi

1)  Fungsi Injektif/satu-satu

•    Fungsi satu-satu

•    Fungsi f: A → B disebut fungsi satu-satu jika dan hanya jika untuk sembarang a1 dan a2 dengan a1 tidak sama dengan a2berlaku f(a1) tidak sama dengan f(a2). Dengan kata lain, bila a1 = a2 maka f(a1) sama dengan f(a2).

2)  Fungsi Surjektif/ onto

•   Fungsi kepada

•   Fungsi f: A → B disebut fungsi kepada jika dan hanya jika untuk sembarang b dalam kodomain B terdapat paling tidak satu adalam domain A sehingga berlaku f(a) = b.

•  Suatu kodomain fungsi surjektif sama dengan range-nya (semua kodomain adalah peta dari domain).

3)   Fungsi Bijektif/ korespondensi satu-satu

• Fungsi f: A → B disebut disebut fungsi bijektif jika dan hanya jika untuk sembarang b dalam kodomain B terdapat tepat satu a dalam domain A sehingga f(a) = b, dan tidak ada anggota A yang tidak terpetakan dalam B.

•  Dengan kata lain, fungsi bijektif adalah fungsi injektif sekaligus fungsi surjektif.

                                                                                                                 

Aljabar Boolean

Pendahuluan

Aljabar boole pertama kali dikemukakan oleh  seseorang matematikawan inggris, geogre boole pada tahun 1854. Aljabar boolean adalah cabang ilmu matematika yang diperlukan untuk mempelajari desain logika dari suatu sistem digital yang merupakan operasi aritmatik pada bilangan boolean (bilangan yang hanya mengenal 2 keadaan yaitu False/True, Yes/No, 1/0) atau bisa disebut bilangan biner. Pada tahun 1938 clamde shanmon memperlihatkan penggunaan aljabar boole untuk merancang rangkaian sirkuit yang menerima masukan 0 dan 1 dan menghasilkan keluaran juga 0 dan 1 aljabar boole telah menjadi dasar teknologi komputer digital.

Definisi :

Aljabar boole merupakanaljabaryng terdiri atas suatu hmpunan B dengan dua operator biner yang didefinisikan pada himpunan tersebut, yaitu * (infimum) dan + (supremum).

Atau

Aljabar boole adalah suatu letisdistribusi berkomplimen.

Notasi aljabarboole adalah (B, + , 1 , 0 , 1 ). Dalam aljabar boole terdapat :

Letis (B, * , + ) dengan dua operasi biner infimum (*) dan supremum (+)

Poset (B, ≤) yaitu himpunan terurut bagian.

Batas-batas letis yang dinotasikan dengan 0 dan 1. 0adalah elemen terkecil dan 1 adalah elemen terbesr dari relasi (B, ≤).

Karena (B, * , +) merupakan letis distribusi berkomplemen maka tiap elemen dari B merupakan komplemen yang unik. Komplemen dan ( a  B )

Untuk setiap a, b, c  B berlaku sifat-sifat atau postulat-postulat berikut:

1. Closure (tertutup) : (i)  a + b  B    

  (ii) a * b  B      

2. Identitas : (i)  ada elemen untuk 0  B sebgai bentuk 

       a + 0 = 0 + a = a

  (ii) ada elemen untuk 1  B sebgai bentuk

       a * 1 = 1 * a = a

3. Komutatif : (i)  a + b = b + a

  (ii)  a * b = b . a

4. Distributif : (i)   a * (b + c) = (a * b) + (a * c)

  (ii)  a + (b * c) = (a + b) * (a + c)

  (iii) (a * b) + c = (a + c) * (b + c)

5. Komplemen : untuk setiap a  B sebagai berikut :

 (i)  a + a1 = 1 

  (ii)  a * a1 = 0

6. Terdapat paling sedikit dua buah elemen  a dan  B sedemikian hingga a ≠ b.

7. Idempoteni : a * a = a ; + a = a

8. Assosiatif : a + (b + c) = (a + b) +c ; a * (b *c) = (a * b) * c

Kecuali postulat nomor 7 dan 8, postulat pertama diformulasikan secara formal oleh E.V Humtingtonn pada tahun 1904 sebagai keenan aksioma/ postulat tersebut. Adapun postulat assosiatif dan idempoten dapat diturunkan dari postulat yang lain.

4.2 Aljabar Boole Dua Nilai

Aljabar Boolean dua-nilai didefinisikan pada sebuah himpunan dua buah elemen,      B = {0, 1}. Akan diselidiki apakah (B, + , 1 , 0 , 1 ) aljabar boole atau bukan.

operator biner, + dan 

operator uner, ’

Kaidah untuk operator biner dan operator uner: 

 

a b a * b a B a + b a a1

0 0 0 0 0 0 0 1

0 1 0 0 1 1 1 0

1 0 0 1 0 1

1 1 1 1 1 1

Cek apakah memenuhi postulat Huntington:

Closure :  jelas berlaku 

Identitas: jelas berlaku karena dari tabel dapat kita lihat bahwa:

(i)  0 + 1 = 1 + 0 = 1 

(ii) 1 * 0  = 0 * 1 = 0

Yang memenuhi elemen identitas 0 dan 1 seperti yang didefinisikan      pada postulat huntington.

Komutatif:  jelas berlaku dengan melihat simetri tabel operator biner.

  Distributif: (i) a  (b + c) = (a  b) + (a  c) dapat ditunjukkan benar dari tabel operator biner di atas  dengan membentuk tabel kebenaran: 

       a b c b + c a  (b + c) a  b a  c (a  b) + (a  c)

0 0 0 0 0 0 0 0

0 0 1 1 0 0 0 0

0 1 0 1 0 0 0 0

0 1 1 1 0 0 0 0

1 0 0 0 0 0 0 0

1 0 1 1 1 0 1 1

1 1 0 1 1 1 0 1

1 1 1 1 1 1 1 1

(ii) Hukum distributif a + (b  c) = (a + b)  (a + c) dapat ditunjukkan benar dengan membuat tabel kebenaran dengan cara yang sama seperti (i).

Komplemen: jelas berlaku karena Tabel di atas memperlihatkan bahwa:

     (i)  a + a1 = 1, karena 0 + 01= 0 + 1 = 1 dan 1 + 11= 1 + 0 = 1 

     (ii) a * a = 0, karena 0 * 01= 0  1 = 0 dan 1 * 11 = 1 * 0 = 0  

Karena kelima postulat Huntington dipenuhi, maka terbukti bahwa B = {0, 1} bersama-sama dengan operator biner + dan * operator komplemen1  merupakan aljabar Boolean. 

Contoh :

Buktikan sifat aljbar boole : a + (a1 * b) = a + b

Bukti :

a + ( a1 * b) = ( a + a1 ) * (a + b)

        = 1 * ( a + b )

        = a + b

Prinsip Dualitas

Definisi : Misalkan S adalah kesamaan (identity) di dalam aljabar Boolean yang melibatkan     operasi ( *, +, dan komplemen1) , maka jika pernyataan S* diperoleh dengan cara mengganti

  *  dengan  +

  +  dengan  *

  0  dengan  1

  1  dengan  0

maka kesamaan S* juga benar. S* disebut sebagai dual dari S.

Contoh.  

Tentukan dual dari a +(b *c) = (a + b)*(a + c)

Jawab :

a *(b + c) = (a * b)+(a * c)

a * 1 = 0

Jawab :

a + 0 = 1

Sifat-sifat atau Hukum-hukum Aljabar Boolean

1. Hukum identitas:

(i)    a + 0 = a

(ii)  a * 1 = a

2. Hukum idempoten:

(i)   a + a = a

(ii)  a * a = a

3. Hukum komplemen:

(i)    a + a1 = 1 

(ii)  aa1 = 0

4. Hukum dominansi:

(i)    a * 0  = 0

(ii)   a + 1 = 1

5. Hukum involusi:

(i) (a1)1= a

6. Hukum penyerapan:

(i)    a + ab = a

(ii)  a(a + b) = a

7. Hukum komutatif:

(i)    a + b = b + a

(ii)   ab = ba

8. Hukum asosiatif:

(i)    a + (b + c) = (a + b) + c

(ii)   a (b c) = (a b) c

9. Hukum distributif:

(i) a + (b c) = (a + b) (a + c)

(ii) a (b + c) = a b + a c

10. Hukum De Morgan:

(i) (a + b)1 = a1 b1

(ii) (ab)1 = a1 + b1

Hukum 0/1 

  (i)   01 = 1

       (ii)  11 = 0

 

Contoh. Buktikan (i) a + ab = a  dan   (ii) a(a + b) = a

Penyelesaian:

(i) a + ab = a * 1 + a*b (hukum identitas)

= a ( 1 + b) (distributif)

= a * 1 (dominasi)

= a (Identitas)

(ii) a(a + b) = ( a + 0) (a +b) (hukum identitas)

  = a + (0*b) (distributif)

  = a+ 0 (dominasi)

  = a (Identitas)

Contoh :

Buktikan bahwa untuk sembarang elemen a dan b dari aljabar Boolean maka kesamaan berikut :

 

a + a1b=a+b dan a(a1+b)=ab adalah benar.

Jawab: 

a + a1b  = (a + ab) + a1b (hukum penyerapan)

  = a + (ab + a1b) (asosiatif)

  = a + (a + a1) b (distributif)

  = a + 1 . b (komplemen)

  = a + b (identitas)

a(a1 + b) = a a1 + ab (hukum distributif)

   = 0 + ab (komplemen)

   = ab (identitas)

Atau, dapat juga dibuktikan melalui dualitas dari (i) sebagai berikut:

a(a1 + b)  = a(a + b)(a1 + b)

    = a{(a + b)(a1 + b)}

     = a {(a a1) + b}

   = a (0 + b)

   = ab

Fungsi Boolean

Fungsi Boolean (disebut juga fungsi biner) adalah pemetaan dari Bn ke B melalui ekspresi Boolean, kita menuliskannya sebagai

f : Bn  B

 Bn adalah himpunan yang beranggotakan pasangan terurut ganda-n (ordered n-tuple) di dalam daerah asal B. 

Setiap ekspresi Boolean merupakan fungsi Boolean. 

Misalkan sebuah fungsi Boolean adalah 

f(x, y, z) = xyz + x’y + y’z 

Fungsi f memetakan nilai-nilai pasangan terurut ganda-3 

(x, y, z) ke himpunan {0, 1}.

Penyelesaian : (1, 0, 1) yang berarti x = 1, y = 0, dan z = 1 

sehingga f(1, 0, 1) = 1  0  1 + 1’  0 + 0’ 1 = 0 + 0 + 1 = 1 . 

Contoh.  Contoh-contoh fungsi Boolean yang lain:

f(x) = x 

f(x, y) = x’y + xy’+ y’

f(x, y) = x’ y’

f(x, y) = (x + y)’ 

f(x, y, z) = xyz’             

Setiap peubah di dalam fungsi Boolean, termasuk dalam bentuk komplemennya, disebut literal. 

Contoh: Fungsi h(x, y, z) = xyz’ pada contoh di atas terdiri dari 3 buah literal, yaitu x, y, dan z’. 

Contoh. Diketahui fungsi Booelan f(x, y, z) = xy z’, nyatakan h dalam tabel kebenaran.

Penyelesaian:

       

x y z f(x, y, z) = xy z’

0

0

0

0

1

1

1

1 0

0

1

1

0

0

1

1 0

1

0

1

0

1

0

1 0

0

0

0

0

0

1

0

Fungsi Komplemen

Cara pertama: menggunakan hukum De Morgan

Hukum De Morgan untuk dua buah peubah, x1 dan x2, adalah  

 

Contoh. Misalkan f(x, y, z) = x(y’z’ + yz), maka

    f ’(x, y, z)  = (x(y’z’ + yz))’

           =  x’ + (y’z’ + yz)’

                 =  x’ + (y’z’)’ (yz)’

                 =  x’ + (y + z) (y’ + z’)          

Cara kedua: menggunakan prinsip dualitas. 

Tentukan dual dari ekspresi Boolean yang merepresentasikan f, lalu komplemenkan setiap literal di dalam dual tersebut. 

Contoh. Misalkan f(x, y, z) = x(y’z’ + yz), maka

dual dari  f: x + (y’ + z’) (y + z)

komplemenkan tiap literalnya: x’ + (y + z) (y’ + z’) = f ’

     

Jadi, f ‘(x, y, z) = x’ + (y + z)(y’ + z’)              

Bentuk Kanonik 

Jadi, ada dua macam bentuk kanonik:

Penjumlahan dari hasil kali (sum-of-product atau SOP)

Perkalian dari hasil jumlah (product-of-sum atau POS)

Contoh: 1.  f(x, y, z) = x’y’z + xy’z’ + xyz   SOP

          Setiap suku (term) disebut minterm

     2. g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’)

         (x’ + y + z’)(x’ + y’ + z)   POS

Setiap suku (term) disebut maxterm

Setiap minterm/maxterm mengandung literal lengkap

Minterm Maxterm

x y Suku Lambang Suku Lambang

0

0

1

1 0

1

0

1 x’y’

x’y

xy’

x y m0

m1

m2

m3 x + y

x + y’

x’ + y

x’ + y’ M0

M1

M2

M3

Minterm Maxterm

x y z Suku Lambang Suku Lambang

0

0

0

0

1

1

1

1 0

0

1

1

0

0

1

1 0

1

0

1

0

1

0

1 x’y’z’

x’y’z

x‘y z’

x’y z

x y’z’

x y’z

x y z’

x y z m0

m1

m2

m3

m4

m5

m6

m7 x + y + z

 x + y + z’

x + y’+z

x + y’+z’

x’+ y + z

x’+ y + z’

x’+ y’+ z

x’+ y’+ z’ M0

M1

M2

M3

M4

M5

M6

M7

Contoh . Nyatakan tabel kebenaran di bawah ini dalam bentuk kanonik SOP dan POS.

 Tabel

x y z f(x, y, z)

0

0

0

0

1

1

1

1 0

0

1

1

0

0

1

1 0

1

0

1

0

1

0

1 0

1

0

0

1

0

0

1

Penyelesaian:

  SOP

Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 1 adalah 001, 100, dan 111, maka fungsi Booleannya dalam bentuk kanonik SOP adalah

f(x, y, z) =  x’y’z + xy’z’ + xyz

atau (dengan menggunakan lambang minterm),

f(x, y, z) =  m1 + m4 + m7 =  (1, 4, 7)

(b) POS

Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 0 adalah 000, 010,  011, 101, dan 110, maka fungsi Booleannya dalam bentuk kanonik POS adalah

 f(x, y, z)  =  (x + y + z)(x + y’+ z)(x + y’+ z’)

   (x’+ y + z’)(x’+ y’+ z)

                     

      atau dalam bentuk lain,

f(x, y, z) =  M0 M2 M3 M5 M6 = (0, 2, 3, 5, 6)             

Contoh Nyatakan fungsi Boolean f(x, y, z) = x + y’z dalam bentuk kanonik SOP dan POS.

Penyelesaian:

(a) SOP

x  = x(y + y’)

    = xy + xy’

    = xy (z + z’) + xy’(z + z’)

    = xyz + xyz’ + xy’z + xy’z’

y’z = y’z (x + x’)

      = xy’z + x’y’z

Jadi  f(x, y, z)   = x + y’z

                      = xyz + xyz’ + xy’z + xy’z’ + xy’z + x’y’z

                      = x’y’z + xy’z’ + xy’z + xyz’ + xyz

          

       atau  f(x, y, z)   = m1 + m4 + m5 + m6 + m7 =  (1,4,5,6,7)

(b) POS

f(x, y, z) = x + y’z 

              = (x + y’)(x + z)

x + y’ = x + y’ + zz’

          = (x + y’ + z)(x + y’ + z’)

x + z = x + z + yy’

        = (x + y + z)(x + y’ + z)

Jadi, f(x, y, z) = (x + y’ + z)(x + y’ + z’)(x + y + z)(x + y’ + z)

        = (x + y  + z)(x + y’ + z)(x + y’ + z’)

atau f(x, y, z) = M0M2M3 = (0, 2, 3)             

Aplikasi Aljabar Boolean

Jaringan Pensaklaran (Switching Network)

Saklar adalah objek yang mempunyai dua buah keadaan: buka dan tutup.  

Tiga bentuk gerbang paling sederhana:

1. a x b

Output b hanya ada jika dan hanya jika x dibuka  x

2. a x y          b

Output b hanya ada jika dan hanya jika x dan y dibuka  xy

3. a      x

c

b y

   Output c hanya ada jika dan hanya jika x atau y dibuka  x + y

Contoh rangkaian pensaklaran pada rangkaian listrik: 

1. Saklar dalam hubungan SERI: logika AND

        Lampu

A        B

           

Sumber tegangan

2.   Saklar dalam hubungan PARALEL: logika OR

         A

        Lampu

      B

         

Sumber Tegangan

Contoh. Nyatakan rangkaian pensaklaran pada gambar di bawah ini dalam ekspresi Boolean.

                  x’    y

           x’

              x

     x           y

           x    y’       z

        z

Jawab:  x’y + (x’ + xy)z + x(y + y’z + z)

Rangkaian Digital Elektronik

 

Contoh. Nyatakan fungsi f(x, y, z) = xy + x’y ke dalam rangkaian logika.

Jawab:  (a) Cara pertama 

(b) Cara kedua

(b) Cara ketiga 

Penyederhanaan fungsi Boolean

Dari segi penerapannya,fungsi boole yang lebih sederhana berarti rangkaan logika nya juga sederhana. Penyederhanaan fungsi boole dapat dilakukan dengan 3 cara:

Contoh. f(x, y) = x’y + xy’ + y’ 

disederhanakan menjadi 

f(x, y) = x’ + y’

Penyederhanaan fungsi Boolean dapat dilakukan dengan 3 cara:

Secara aljabar

Menggunakan Peta Karnaugh

Menggunakan metode Quine Mc Cluskey (metode Tabulasi)

1. Penyederhanaan Secara Aljabar

Contoh:

f(x, y) = x + x’y 

      = (x + x’)(x + y) 

 = 1  (x + y ) 

 = x + y

f(x, y, z) = x’y’z + x’yz + xy’

 = x’z(y’ + y) + xy’ 

 = x’z + xz’

f(x, y, z) = xy + x’z + yz  = xy + x’z + yz(x + x’)

   = xy + x’z + xyz + x’yz

   = xy(1 + z) + x’z(1 + y) = xy + x’z

2.  Peta Karnaugh

Cara untuk menyederhanakan ekspresi atau pernyataan dari Aljabar Boole. Caranya dengan menggambarkan kotak-kotak yang berisi “Minterm” (Minimum-Terms)

a.  Peta Karnaugh dengan dua peubah

            y

         0          1

m0 m1 x   0 x’y’ x’y

m2 m3 1  xy’ xy

b. Peta dengan tiga peubah

yz

00

01

11

10

m0 m1 m3 m2 x   0                      x’y’z’ x’y’z x’yz x’yz’

m4 m5 m7 m6 1                      xy’z’ xy’z xyz xyz’

Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh.

x y Z f(x, y, z)

0 0 0 0

0 0 1 0

0 1 0 1

0 1 1 0

1 0 0 0

1 0 1 0

1 1 0 1

1 1 1 1

yz

00

01

11

10

x  0 0 0 0 1

1 0 0 1 1

b. Peta dengan empat peubah

yz

00

01

11

10

m0 m1 m3 m2   wx  00 w’x’y’z’ w’x’y’z w’x’yz w’x’yz’

m4 m5 m7 m6 01                      w’xy’z’ w’xy’z w’xyz w’xyz’

m12 m13 m15 m14 11 wxy’z’ wxy’z wxyz wxyz’

m8 m9 m11 m10 10 wx’y’z’ wx’y’z wx’yz wx’yz’

Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh.

w x Y z f(w, x, y, z)

0 0 0 0 0

0 0 0 1 1

0 0 1 0 0

0 0 1 1 0

0 1 0 0 0

0 1 0 1 0

0 1 1 0 1

0 1 1 1 1

1 0 0 0 0

1 0 0 1 0

1 0 1 0 0

1 0 1 1 0

1 1 0 0 0

1 1 0 1 0

1 1 1 0 1

1 1 1 1 0

yz

00

01

11

10

wx      00 0 1 0 1

01 0 0 1 1

11 0 0 0 1

10 0 0 0 0

Teknik Minimisasi Fungsi Boolean dengan Peta Karnaugh

1. Pasangan: dua buah 1 yang bertetangga

yz

00

01

11

10

wx   00 0 0 0 0

01 0 0 0 0

11 0 0 1 1

10 0 0 0 0

Sebelum disederhanakan: f(w, x, y, z) = wxyz + wxyz’

Hasil Penyederhanaan:     f(w, x, y, z) = wxy

Bukti secara aljabar:

f(w, x, y, z) = wxyz + wxyz’

        = wxy(z + z’)

        = wxy(1)

        = wxy

2. Kuad: empat buah 1 yang bertetangga

yz

00

01

11

10

wx   00 0 0 0 0

01 0 0 0 0

11

1 1 1 1

10 0 0 0 0

Sebelum disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wxyz + wxyz’

Hasil penyederhanaan:  f(w, x, y, z) = wx

Bukti secara aljabar:

f(w, x, y, z) = wxy’ + wxy

        = wx(z’ + z)

        = wx(1)

        = wx

yz

00

01

11

10

wx   00 0 0 0 0

01 0 0 0 0

11

1 1 1 1

10 0 0 0 0

Contoh lain:

yz

00

01

11

10

wx   00 0 0 0 0

01 0 0 0 0

11

1 1 0 0

10 1 1 0 0

Sebelum disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wx’y’z’ + wx’y’z

Hasil penyederhanaan:    f(w, x, y, z) = wy’

3.  Oktet: delapan buah 1 yang bertetangga

yz

00

01

11

10

wx   00 0 0 0 0

01 0 0 0 0

11

1 1 1 1

10 1 1 1 1

Sebelum disederhanakan: f(a, b, c, d) = wxy’z’ + wxy’z + wxyz + wxyz’ + 

             wx’y’z’ + wx’y’z + wx’yz + wx’yz’

Hasil penyederhanaan: f(w, x, y, z) = w

Bukti secara aljabar:

f(w, x, y, z) = wy’ + wy

         = w(y’ + y)

         = w

yz

00

01

11

10

wx   00 0 0 0 0

01 0 0 0 0

11

1 1 1 1

10 1 1 1 1

Contoh . Sederhanakan fungsi Boolean f(x, y, z)  = x’yz + xy’z’ + xyz + xyz’. 

Jawab:

Peta Karnaugh untuk fungsi tersebut adalah:

yz

00

01

11

10

x     0

1

1

1 1 1

Hasil penyederhanaan:  f(x, y, z)  =  yz + xz’

Contoh . Andaikan suatu tabel kebenaran telah diterjemahkan ke dalam Peta Karnaugh. Sederhanakan fungsi Boolean yang bersesuaian sesederhana mungkin.

yz

00

01

11

10

wx   00

0 1 1 1

01 0 0 0 1

11

1 1 0 1

10 1 1 0 1

Jawab: (lihat Peta Karnaugh)  f(w, x, y, z) = wy’ + yz’ + w’x’z

Contoh .  Minimisasi fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.

yz

00

01

11

10

wx   00 0 0 0 0

01

0 1 0 0

11

1 1 1 1

10 1 1 1 1

Jawab: (lihat Peta Karnaugh)  f(w, x, y, z) = w + xy’z

Jika penyelesaian Contoh 5.13 adalah seperti di bawah ini:

yz

00

01

11

10

wx   00 0 0 0 0

01

0 1 0 0

11

1 1 1 1

10 1 1 1 1

maka fungsi Boolean hasil penyederhanaan adalah

f(w, x, y, z) = w + w’xy’z  (jumlah literal = 5)

yang ternyata masih belum sederhana dibandingkan f(w, x, y, z) = w + xy’z   (jumlah literal = 4).

Contoh . (Penggulungan/rolling) Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.

yz

00

01

11

10

wx   00 0 0 0 0

01

1 0 0 1

11 1 0 0 1

10 0 0 0 0

Jawab:  f(w, x, y, z) = xy’z’ + xyz’ ==> belum sederhana 

Penyelesaian yang lebih minimal:

yz

00

01

11

10

wx   00 0 0 0 0

01

1 0 0 1

11

1 0 0 1

10 0 0 0 0

f(w, x, y, z) = xz’  ===> lebih sederhana

Contoh : (Kelompok berlebihan) Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.

yz

00

01

11

10

wx   00 0 0 0 0

01

0 1 0 0

11

0 1 1 0

10 0 0 1 0

Jawab: f(w, x, y, z) = xy’z + wxz + wyz   masih belum sederhana.

Penyelesaian yang lebih minimal:

yz

00

01

11

10

wx   00 0 0 0 0

01

0 1 0 0

11

0 1 1 0

10 0 0 1 0

f(w, x, y, z) = xy’z + wyz    ===> lebih sederhana

Contoh   Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.

cd

00

01

11

10

ab   00 0 0 0 0

01

0 0 1 0

11

1 1 1 1

10 0 1 1 1

Jawab: (lihat Peta Karnaugh di atas)  f(a, b, c, d) = ab + ad + ac + bcd  

Contoh .  Minimisasi fungsi Boolean f(x, y, z)  =  x’z +  x’y + xy’z + yz

Jawab:

x’z = x’z(y + y’) = x’yz + x’y’z

x’y = x’y(z + z’) = x’yz + x’yz’

yz = yz(x + x’) = xyz + x’yz

f(x, y, z) = x’z + x’y + xy’z + yz

   = x’yz + x’y’z + x’yz + x’yz’ + xy’z + xyz + x’yz

   = x’yz + x’y’z + x’yz’ + xyz + xy’z

Peta Karnaugh untuk fungsi tersebut adalah:

yz

00

01

11

10

x      0

1 1 1

1 1 1

Hasil penyederhanaan:  f(x, y, z) = z + x’yz’

Peta Karnaugh untuk lima peubah 

 000      001    011    010     110     111    101     100

00 m0 m1 m3 m2 m6 m7 m5 m4

01 m8 m9 m11 m10 m14 m15 m13 m12

11 m24 m25 m27 m26 m30 m31 m29 m28

10 m16 m17 m19 m18 m22 m23 m21 m20

Garis pencerminan

Contoh \. (Contoh penggunaan Peta 5 peubah) Carilah fungsi sederhana dari  f(v, w, x, y, z) =  (0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31)

Jawab:

Peta Karnaugh dari fungsi tersebut adalah:

xyz

000

001

011

010

110

111

101

100

vw 00

1

1

1

1

01

1

1

1

1

     

11

1

1

1

1

10

1

1

Jadi  f(v, w, x, y, z)  =  wz + v’w’z’ + vy’z

Metode Penyederhanaan Untuk Penyelesaian Permasalahan Dalam Ekspresi Logika.

Penyederhanaan adalah proses mengubah bentuk ekspresi-ekspresi logika menjadi lebih sederhana, dengan menggunakan hukum-hukum ekivalensi dalam logika. Tujuan dari penyederhanaan ini adalah kemudahan dalam mengoperasikan atau menentukan ekivalensinya dengan ekspresi logika yang lain.

OPERASI PENYEDERHANAAN

Operasi penyederhanaan adalah langkah mengubah persamaan logika dengan menggunakan hukum-hukum logika pada operasi logika. Penyederhanaan logika menggunakan tabel pada bagian Ekuivalen Logis. 

Contoh 1.

(A∨0)∧(A∨~A) Zero of V

=A∧(A∨~A) Tautologi

=A∧1 Identity of ∧

=A

Contoh 2.

(A∧~B)∨(A∧B∧C)             

≡(A∧~B)∨(A∧(B∧C) ) Tambah Kurung 

≡A∧(~B∨(B∧C) ) Distributif

≡A∧((~B∨B)∧(~B∨C) ) Distributif 

≡A∧(1∧(~B∨B)∧(~B∨C) ) Tautologi 

≡A∧(~B∨C) Identity of ∧

Penyederhanaan juga dapat digunakan untuk membuktikan ekuivalen atau kesamaan secara logis. 

Contoh 3.

Buktikan : (A→B)∧(B→A)≡(A∧B)∨(~A∧~B)  

(A→B)∧(B→A)

≡(~A∨B)∧(~B∨A)

≡(B∨~A)∧(A∨~B)

≡(A∨~B)∧(B∨~A)

≡((A∨~B)∧B)∨((A∨~B)∧~A)

≡((A∧B)∨(~B∧B) )∨((A∧~A)∨(~B∧~A) )

≡((A∧B)∨0)∨(0∨(~B∧~A) )

≡(A∧B)∨(~B∧~A)

≡ (A∧B)∨(~A∧~B)

Untuk membuat penyederhanaan, pertama kali harus dihilangkan adalah →dan↔  dan menjadikan kombinasi dari ∧ , ∨, dan ~. Beberapa contoh kesamaan logis.

A→B≡(~A∧B)

A↔B≡ (~A∨B)∧(~B∨A)

              ≡(A∧B)∨(~A∧~B)

Operasi penyederhanaan dengan menggunakan hukum-hukum logika dapat digunakan untuk membuktikan ekspresi logika tautologi jika hasil akhirnya 1, kontradiksi jika hasilnya 0, dan jika tidak 0 ataupun 1 maka contigent.

MENGHILANGKAN PERANGKAI →DAN↔

Pada operasi penyederhanaan,  implikasi dan biimplikasi dapat digantikan oleh perangkai dasar ~, ∨, ∧. 

Contoh 4. 

 A↔B≡(A→B)∧(B→A)

≡(~A∨B)∧(~B∨A)

≡(~A∨B)∧(A~B)

PERANGKAI DASAR

Perangkai dasar disebut juga dengan perangkai cukup. Ketiga perangkai tersebut membentuk gates yang menjadi dasar sistem digital. Perangkai cukup menunjukkan bahwa perangkai ∧ dapat diganti dengan ~ dan ∨, sedangkan perangkai  ∨ dapat digantikan oleh ~ dan ∧. 

Contoh 5.

~(A∧~A) 

≡~A∨~~A)

≡~A∨A

LATIHAN

Soal 1

Sederhanakan bentuk-bentuk logika berikut menjadi bentuk paling sederhana

A∧(~A→A)

~(~A∧(B∨~B))

~A→~(A→~B)

Soal 2

Hilangkan tanda → dan ↔ dari ekspresi logika berikut dan sederhanakan lagi jika memungkinkan 

( ~A→~B)

(A→B)∧(B→C)

(A→B)↔((A∧B)↔B)

Soal 3

Buktikan bahwa hukum-hukum logika berikut ini adalah tautologi 

Silogisme hipotesis

Silogisme disjungtif

Modus ponens

Modus tollens

DAFTAR PUSTAKA

• Drs .Mundiri, Logika, PT.RajaGrafindo Persada, 2001,  Jakarta, hlm.48
• Drs. Toto’ Bara Setiawan, M.Si, Diktat kuliah Logika Matematika,Pendidikan matematika, Universitas Negeri Jember, 2007.
• Dr.W.Poespoprodjo,SH.,S.S.,B.Ph.,L.Ph., Logika Scientifika. Pustaka Grafika, Bandung, 1999 Hal.170
• DR. W. Poespoprodjo, S.H., S.S., B.Ph., L.Ph., Logika Scientifika “ Pengantar Dialektika dan Ilmu”, Pustaka Grafika, 1999, Bandung, hlm 171.
• Foter, Bob. 2006. Soal dan Pembahasan Relasi. Jakarta : Erlangga
• F. Soesianto, Djoni Dwijono, Logika Matematika untuk Ilmu Komputer, Penerbit ANDI, Yogyakarta, 2010.
• Hariyono Rudi, Drs. 2005. Pintar Matematika SMA. Jakarta : Gitamedia Press
• Jong Jeng Siang, Matematika Diskrit dan Aplikasinya pada Ilmu Komputer, Andi OffsetYogyakarta, 2004 
• Jong Jek Siang, Matematika Diskrit dan Aplikasinya pada Ilmu Komputer, Andi Yogyakarta, 2004.
• Kenneth H. Rosen, Discrete Mathematics and Application to Computer Science 5th Edition, Mc Graw-Hill, 2003
• Kesumawati, Nila.2003.Diktat Matematika Diskrit.Palembang: Universitas PGRI Palembang
• Munir, Rinaldi.2010.Matematika Diskrit.Bandung: Informatika
• Retno Hendrowati; Bambang Hariyanto, Logika Informatika, Penerbit Informatika, Bandung, 2000.
• Rinaldi Munir, Matematika Diskrit, Edisi Ketiga, Informatika, Bandung, 2005.
• Setiadji, Logika Informatika, Graha Ilmu, Jakarta, 2007.
• Wibisono, Samuel. 2008. Matematika Diskrit Ed. 02. Jakarta : Graha Ilmu