MODUL
LOGIKA INFORMATIKA
BAB I
PENGENALAN LOGIKA INFORMATIKA
1. Pendahuluan
Logika (Logic) berasal dari kata bahasa Yunani “logos”. Definisi logika adalah ilmu pengetahuan yang mempelajari atau berkaitan dengan prinsip- prinsip dari penalaran argumen yang valid. Logika adalah studi tentang kriteria-kriteria untuk mengevaluasi argumen-argumen dengan menentukan mana argumen yang valid dan mana yang tidak valid, dan membedakan antar argumen yang baik dengan yang tidak baik.
Logika dipelajari sebagai sistem formal yang menjelaskan peranan sekumpulan rumus-rumus ataupun sekumpulan aturan untuk derivasi. Derivasi dipahami sebagai pembuktian validitas argumen yang kuat dengan didukung kenyataan bahwa kesimpulan yang benar harus diperoleh dari premis-premis yang benar.
2. Argumen
Argumen adalah suatu usaha untuk mencari kebenaran dari pernyataan berupa kesimpulan, dengan berdasarkan kebenaran dari satu kumpulan pernyataan yang disebut premis-premis. Bentuk argumen artinya sekumpulan pernyataan yang terdiri dari premis-premis dan diikuti satu kesimpulan.
Contoh 1.
Semua mahasiswa D4 Teknik Informatika pandai.
Badu adalah mahasiswa D4 Teknik Informatika.
Dengan demikian, Badu pandai.
logika yang dibahas di sini hanya berhubungan dengan kesimpulan yang valid.
Contoh 1 tetap dapat dikatakan valid, karena kesimpulannya tetap mengikuti premis-premisnya dan validitasnya dapat dibuktikan dengan menggunakan aturan-aturan logika yang telah diterima keabsahannya.
3. Validitas argumen
Validitas argumen adalah premis-premis yang diikuti oleh suatu kesimpulan yang berasal dari premis-premisnya yang bernilai benar. Validitas dapat dibedakan dengan kebenaran dari kesimpulan. Jika satu atau lebih premis-premis salah, maka kesimpulan dari argumen tersebut juga salah. Validitas dapat diartikan tidak mungkin kesimpulan yang salah diperoleh dari premis-premis yang benar. Atau premis-premis yang benar tidk mungkin menghasilkan kensimpulan yang salah. Lihat contoh berikut:
Contoh 1-2.
Semua mamalia adalah hewan berkaki empat
Semua manusia adalah mamalia
Dengan demikian, semua manusia adalah
hewan berkaki empat.
Contoh 1-2 adalah argumen yang valid, tetapi dengan premis pertama yang salah, karena kesimpulannya tetap mengikuti premis-premisnya. Dilain pihak dapat terjadi suatu argumen tidak valid, tetapi mempunyai kesimpulan yang bernilai benar. Lihat contoh berikut
Contoh 1-4
Ada jenis makhluk hidup berkaki dua.
Semua manusia adalah makhluk hidup
Dengan demikian, semua manusia berkaki dua.
Argumen di atas jelas tidak valid, tetapi menghasilkan kesimpulan yang benar meskipun tidak mengikuti premis-premisnya.
Validitas yang logis adalah hubungan antara premis-premis dengan kesimpulan yang memastikan bahwa jika premis-premis benar, maka harus diikuti dengan kesimpulan yang benar, yang diperoleh dengan menggunakan aturan-aturan logika. Kesimpulan juga harus berasal dari premis-premisnya. Lihat contoh berikut:
Contoh 1-5
Semua mahasiswa rajin belajar.
Badu seorang mahasiswa.
Dengan demikian, Dewi rajin belajar.
Kesimpulan pada contoh di atas jelas tidak ada hubungannya dengan premis-premisnya,walaupun bisa saja bernilai benar dan premis-premis bernilai benar, tetapi bukan argumen yang kuat secara logis.
Argumen logis disebut kuat secara logis, jika dan hanya jika argumennya valid dan semua premis-premisnya bernilai benar.
Sebagai pembanding perhatikan contoh berikut:
Contoh 1-6
Semua binatang dapat terbang.
Gajah adalah binatang.
Dengan demikian, gajah dapat terbang.
Argumen ini dapat dikatakan valid, tetapi validitasnya tidak kuat. Karena jelas premis pertama pada Contoh 1-5 salah, walaupun bisa disebut valid, tetapi jelas validitas yang tidak kuat. Jadi suatu argumen logis dapat disebut kuat jika dan hanya jika memenuhi dua persyaratan berikut:
a. Argumen valid
b. Semua premis-premisnya benar.
BAB II
PENGANTAR LOGIKA PROPOSISIONAL
1. Pendahuluan
Dilihat dari bentuk struktur kalimatnya, suatu pernyataan akan memiliki n=bentuk susunan minimal terdiri dari subjek yang diikut predikat baru kemudian dapat diikuti oleh obyeknya. Perhatikan contoh berikut:
Contoh 2-1.
· Dewi belajar
· Badu adalah seorang mahasiswa yang pandai pada mata kuliah logika matematika.
Kalimat pertama hanya memiliki subjek dan predikat, sedangkan kalimat kedua memiliki subjek predikat objek dan keterangan. Setiap pernyataan yang hanya memiliki satu nilai benar atau salah disebut proporsi sehingga logika yang menangani atau memproses atau memanipulasi penarikan kesimpulan secara logis dari proporsi-prosporsi disebut logika proporsional. Proporsi-proporsi dapat digabung dan dimanipulasi sehingga membentuk proporsi yang rumit. Penggabungan tersebut dilakukan dengan perangkai-perangkai sehingga disebut proporsi majemuk. Perhatikan contoh berikut:
Contoh 2-2.
· Belajarlah!
Jadi, kata tersebut dapat diubah menjadi kalimat yang lengkap tanpa mengubah artinya sehingga dapat menjadi:
· Anda harus belajar dengan rajin!
Tetapi pada contoh 2-2 anda akan menjumpai dua buah proporsi
Contoh 2-3.
· Belajarlah, atau Anda gagal!
Jadi, kalimat lengkapnya adalah
· Anda harus belajar dengan rajin atau Anda akan gagal.
2. Argumen-Argumen
Argumen merupakan kumpulan pernyataan yang disebut premis-premis dan diikuti oleh kesimpulan yang selaras dengan premis-premisnya. Ada argumen yang dikatakan kuat, tetapi adapula yang secara logis tidak kuat. Berikut contoh argumen yang kuat:
Contoh 2-4.
1) Jika Anda rajin belajar, maka Anda lulus ujian.
2) Jika Anda lulus ujian, maka Anda senang.
3) Dengan demikian, jika Anda belajar rajin, maka Anda akan senang.
Pernyataan 1) dan 2) merupakan premis-premis dari argumen, sedangkan pernyataan 3) merupakan kesnimpulan yang mengikuti atau berasal dari premis-premisnya. Jika premis-premis bernilai benar, maka kesimpulan juga harus bernilai benar, sehingga argumen tersebut disebut argumen yang secara logis kuat. Jadi tidak mungkin suatu premis-premis yang bernilai benar akan diikuti oleh kesimpulan yang bernilai salah, atau premis-premisnya yang bernilai salah tidak mungkin menghasilkan kesimpulan yang bernilai benar.
Perhatikan berikut ini:
A = Anda belajar rajin.
B = Anda lulus ujian.
C = Anda senang.
Selanjutnya, bentuk argumen tersebut menjadi:
1) Jika A, maka B
2) Jika B, maka C
3) Jika A, maka C
3. Proporsi-Proporsi
Proporsi merupakan pernyataan apa saja ynag mempunyai nilai benar dan salah. Perhatikan contoh berikut:
Contoh 2-5.
· Angka 9 adalah angka sial.
· Hari selasa adalah hari sial.
· Angka 7 adalah angka keberuntungan.
· Warna merah adalah warna bahagia.
Contoh-contoh pernyataan diatas akan menimbulkan perbedatan karena tidak semua orang mempunyai pendapat yang sama. Selain itu, pernyataan yang berupa kalimat tanya dan kalimat perintah tidak bisa dipakai pada proposisi.
Contoh 2.6.
· Badu, kerjakan tugas tersebut!
· Badu, apakah engkau sudah mengerjakan tugas tersebut?
Suatu proposisi juga tidak boleh digantikan dengan proposisi lain yang artinya sama.
Contoh 2-7.
· Badu tidak lapar.
· Badu kenyang.
Pada pernyataan pertama dengan kedua arti kalimatnya sama, tetapi pada proporsi, jika dijumpai adanya contoh seperti pernyataan pertama dan pernyataan kedua, maka pemberiak variabel proposisi harus berlainan karena proposisi tidak diizinkan menafsir arti kalimatnya.
Contoh 2-8.
A = Badu lapar, maka “Tidak A” = Badu tidak lapar.
B = Badu kenyang, maka “Tidak B” = Badu tidak kenyang.
Jadi tidak dipernolehkan mengganti “Tidak A” dengan B, walaupun artinya sama.
4. Pemberian Nilai
Huruf A, B, C, dan seterusnya digunakan untuk menggantikan proposisi dan disebut variabel-variabel proposisional, dan hanya memiliki nilai benar (True T) dan salah (False F). Jadi pemberian nilai pada variabel proposional hanya T dan F.
BAB III
TABEL KEBENARAN
1. Pendahuluan
Logika hanya berhubungan dengan bentuk-bentuk logis dari argumen-argumen, serta penarikan kesmpulan tentang validitas dari argumen tersebut. Logika tidak mempermasalahkan arti sebenarnya dari pernyataan tersebut, ataupun isi dari pernyataan.
Contoh 3-1.
Manusia mempunyai 2 mata
Badu seorang manusia
Maka Badu mempunyai 2 mata
Contoh 3-2.
Binatang mempunyai 2 mata
Manusia mempunyai 2 mata
Maka binatang sama dengan manusia.
Sesekali perlu diingat bahwa logika tidak mempermasalahkan arti atau isi suatu pernyataan, tetapi hanya bentuk logika dari pernyataan itu. Logika hanya menekankan bahwa premis-premis yang benar harus menghasilkan kesimpulan yang benar (valid). Lagi pula, premis-premis yang benar tidak mungkin menghasilkan kesimpulan yang salah, atau premis-premis yang salah menghasilkan kesimpulan yang benar.
2. Tabel Kebenaran
Tabel kebenaran adalah suatu tabel yang menunjukan secara sistematis satu demi satu nilai-nilai kebenaran sebagai hasil kombinasi dari proposisi-proposisi yang sederhana. Penekanan logika pada penarikan kesimpulan tentang validitas suatu argumen untuk mendapatkan kebenaran yang bersifat abstrak, yang dibangun dengan memakai kaidah-kaidah dasar logika tentang kebenaran dan ketidakbenaran yang menggunakan perangkai logika.
Perangkai-perangkai logika yang digunakan adalah
perangkai
simbol
dan
˄
atau
˅
Bukan
¬
jika...maka...
Þ
Jika dan hanya jika
⟺
1. Konjungsi
Konjungsi adalah kata lain dari perangkai “dan” dengan tabel kebenaran sebagai berikut:
A
B
A˄B
F
F
F
F
T
F
T
F
F
T
T
T
2. Disjungsi
Disjungsi adalah kata lain dari perangkai “atau” dengan tabel kebenaran sebagai berikut:
A
B
A˅B
F
F
F
F
T
T
T
F
T
T
T
T
3. Negasi
negasi adalah kata lain dari perangkai “bukan” dengan tabel kebenaran sebagai berikut:
A
¬A
¬¬A
F
T
F
T
F
T
4. Implikasi
Implikasi menggantikan perangkai jika...maka...
A
B
AÞB
F
F
T
F
T
T
T
F
F
T
T
T
5. Ekuivalensi
Ekuivalensi dengan simbol ⟺menggantikan perangkai “jika dan hanya jika” dengan tabel kebenaran sebagai berikut:
A
B
A⟺B
F
F
T
F
T
F
T
F
F
T
T
T
BAB IV
PROPOSISI MAJEMUK
1. Pendahuluan
Perangkai logika untuk mengkombinasikan proporsi-proporsi atomik menjadi proporsi majemuk. Untuk menghindari kesalahan tafsir akibat adanya ambiguitas satu dengan lainnya, proporsi majemuk yang akan dikerjakan lebih dulu akan diberi tanda kurung sehingga proporsi-proporsi dengan perangkai-perangkai yang berada dalam tanda kurung disebut fully presenthesised expressiaon (fpe).
Proporsi majemuk yangs angat rumait dapat dipercah-pecarh menjadi subekspresi-subekspresi dan seterusnya tergantung tingkat kerumitannya. Tiknik ini dimanakan parsing. Akan tetapi mungkin saja proporsi majemuk tidak memiliki tanda kurung. Oleh karena itu, untuk proses pengerjaannya harus ditentukan terlebih dahulu dan harus ada ketentuan yang mengatur pengurutan tersebut.
2. Ekspresi logika
Ekspresi logika sebenarnya adalah proporsi-proporsi yang dibangun dengan variabel-vareiable logika yang berasal dari pernyataan atau argumen. Jadi, variabel logis, dapat dinamakan ekspresi logika atau formula. Proporsi atomik berisi satu variabel proporsional atau astu konstanta proporsional. Proporsi majemuk berisi minumum satu perangkai, dengan lebih dari satu variabel proporsional. Setiap ekspresi logika dapat bersifat atomik atau majemuk tergantung dari variabel proporsional yang membentuknya bersama perangkai yang relevan.
Contoh 4-1.
Jika Dewi rajin berlajar, maka ia lulus ujian dan ia dapat hadiah istimewa.
Pernyataan diatas dapat diubah menjadi variabel proporsional:
A = Dewi rajin belajar.
B = Dewi lulus ujian.
C = Dewi mendapat hadiah istimewa.
Dalam bentuk ekspresi logika berubah menjadi:
AÞB˄C
Persoalannya adalah ada dua kemungkinan perngerjaan, yakni:
((AÞB)˄C) atau (AÞ(B˄C))
Inilah pentingnya ketepatan pemberian tanda kurung biasa sehingga menjadi suatu ekspresi logika yang fpe dan dengan tepat melakukanpengoperasikan sesuai aturannya.
3. Skema
Skema merupakan satu cara untuk menyederhanakan suatu proporsi majemuk yang rumit dengan memberi huruf tertentu untuk menggantikan satu subekspresi ataupun sub-ekspresi. Suatu ekspresi logika tertentu, misalnya (A˄B) dapat diganti dengan P sedangkan (AvB) dapat diganti dengan Q. Namun P dan Q tidak dapat dikatakan sebagai variabel Proporsional.
Contoh 4-2
P = (A˄B) dan Q = (A˅B), maka (PÞQ) = ((A˄B) Þ(A˅B))
Perhatikan hal berikut:
1. Ekspresi berbentuk ¬P disebut negasi
2. Ekspresi berbentuk P˄Q disebut konjungsi
3. Ekspresi berbentuk PÞQ disebut implikasi
4. Ekspresi berbentuk P⟺Q disebut ekuivalensi
Maka contoh diatas ((A˄B)Þ(A˅B)) disebut implikasi yang berisi konjungsi (A˄B) dan disjungsi (A˅B).
Perhatikan aturan berikut:
1. Semua ekspresi atomik adalah fpe.
2. Jika P adalah fpe, maka ¬P juga.
3. Jika P dan Q adalah fpe, maka (PvQ), (PÞQ) dan (P⟺Q).
4. Tidak ada fpe lainnya.
Ekspresi-ekspresi logika yang dijelaskan diatas disebut well formed formulae (wff). Jadi, wff adalah fpe, demikian pula sebaliknya. Ekspresi logika disebut wff karena penulisannya dilakukan dengan benar.
Contoh 4-3.
AÞ(BÞ(¬Av¬B))
Setiap fpe akan mengekspresikan proporsi majemuk. Proporsi maju=emuk mempunyai subproposisi yang bisa berupa konjungsi, disjungsi dan sebagainya. Tetapi, bagaimana membuat suatu proporsisi majemuk dari suatu pernyataan yang cukup panjang.
Contoh 4-4.
1. Jika dewi lulus sarjana teknik informatika, orang tuanya akan senang, dan dia dap[at segera bekerja, tetapi jika dia tidak lulus, semua usahanya akan sia-sia.
Proporsi-proporsi yang membentuk pernyataan diatas adalah konjungsi, karena akan tetapi di tengah kalimat lebih sesuai dengan ’dan’.
Contoh diatas, jika dipisah menjadi skop kanan sebagai berikut:
1.1. Jika Dewi lulus sarjana teknik informatika, orang tuanya akan senang, dan dia dapat segera bekerja.
Dengan
1.2. Jika dia tidak lulus, semua usahanya akan sia-sia.
Dari kedua skop diatas, masih berupa proporsi majemuk. Kalimat pertama yang masih memiliki skop kiri dan skop kana, dapat dipecahlagi seperti berikut:
1.1.1. Jika Dewi lulus sarjana teknik informatika
1.1.2. Orang tuanya akan senang, dan dia dapat segera bekerja.
Kalimat terakhir ini juga masih berbentuk proporsi majemuk, sehingga skop kiri dan skop kanan dapat dipisah sep[erti berikut:
1.1.2.1. Orang tuanya akan senang
dengan
1.1.2.2. Dia dapat segera bekerja
1.2. Akan dipisah menjadi skop kiri dan skop kanan sebagai berikut:
1.2.1. Dia tidak lulus
dengan
1.2.2. Semua usahanya akan sia-sia
Selanjutnya diubah menjadi ekspresi logika yang berbentuk proposisi majemuk menjadi fpe berikut:
A = Dewi lulus sarjana teknik informatika
B = Orangtua Dewi senang
C = Dewi bekerja
D = Dewi sia-sia
Maka pernyataan diatas yang berupa proposisi majemuk dapat diwujudkan dalam fpe berikut
(AÞ(B˄C))˄((¬A)ÞD).
Jika pada ekspresi logika dia atas dianggap M, maka M adalah ekspresi majemuk yang dirangkai dari subekspresi-subekspresi. Jiak M berbentuk (P˄Q), maka P dan Q masing-masing berupa subekspresi. Setiap subekspresi dinamakan immediate sebexpressions dari M. P dan Q juga dapat berbentuk ekspresi majemuk maka dapat mempunyai subkepsresi juga.
Maka pada contoh 4-4 diatas
M = (AÞ(B˄C))˄((¬A)ÞD)
P = (AÞ(B˄C))
Q = ((¬A)ÞD)
P masih mempunyai subekspresi A dan (B˄C), sedangkan (B˄C) masih mempunyai subekspresi B dan C. Hanya saja jika berbentuk ¬A, maka subekspresinya A.
Salah satu bentuk yang banyak dibahas dari ekspresi logika adalah literal. Literal adalah proporsi yang dapat berbentu A atau ¬A dengan A adalah variabel proposisional. Kedua ekspresi tersebut, merupakan variabel proposisional, maka A, ¬A, B, ¬B adalah literal-literal, tetapi jika berbentuk ¬(A˄B), maka ini bukan literal.
4.Aturan pengurutan
Ekspresi-ekspresi logika yang bersifat majemuk yang memiliki banyak subekspresi akan memiliki banyak tanda kurung biasa karena berbentuk fpe, sehingga memungkinkan fpe tersebut sulit dibaca.
Contoh
((A˄B)Þ(AvB))
((A˄(BÞ))AvB)
Kedua fpe tersebut berbeda proses pengerjaanya. Maka harus ada aturan untuk memprioritaskan penafsiran hasilnya. Aturan ini disebut aturan pengurutan. Aturan pengurutan digunakan untuk memastika proses pengerjaanya subekspresi.
Berkaitan dengan perangkai, urutan tersebut berdasarkan hirarki tertinggi:
1. ¬
2. ˄
3. V
4. Þ
5. ⟺
Aturan tambahan, jika menjumpai lebih dari satu perangkai pada hirarki yang sama, maka akan dikerjakan mulai dari yang kiri.
Contoh 4-5.
1. (¬A˄B) harus dibaca ((¬A˄B), bukan (¬(A˄B)).
2. A˄BvC, harus dibaca ((A˄B)vC), bukan (A˄(BvC)).
Misalnya (AÞ(B˄C))˄((¬A)ÞD) dapat disederhanakan dengan mengurangkan tanda kurung biasa menjadi (AÞB˄C)˄(¬AÞD)) tetapi sebaiknya menggukana bentuk yang pertama. Tanda kurung yang terlalu banyak dan jiak tanda kurung yang sebarnya tidak diperlukan, bahkan membuaty salah tafsir yang disebut redundansi.
Contoh 4-6.
AÞBÞC
Manakah yang harus dikerjakan dulu?
Aturan pengurutan menyebutkan: jika hirarkinya sama, maka pengerjaannya dimulai dari kiri. Jadi, harus dibaca (AÞB)ÞC, bukan AÞ(BÞC).
BAB V
TAUTOLOGI
1. Pendahuluan
Salah satu cara mengubah argumen menjdai suatu ekspresi logika adalah teknik Parsing. Pembuktian validitas ekspresi-ekspresi logika dari suatu argumen dapat dilakukan dengan Tabel Kebenaran. Tabel kebenaran mempergunakan aturan-aturan untuk setiap perangkai. Sebelum mengevaluasi validitas suatu argumen, terlebih dahulu harus membentuk pernyataan-pernyataan menjadi ekspresi logika.
Contoh
· Jika Anda mengambil mata kuliah logika informatika, dan jika Anda tidak memahami tautologi, maka Anda tidak lulus.
Untuk membutkikan validitasnya, berilah variabel proposional yang relevan, misal:
A = Anda mengambil mata kuliah lagika matematika.
B = Anda memahami tautologi.
C = Anda lulus.
Dengan demikian, bentuk ekspresi logikanya sepertio berikut:
(A˄¬B)Þ¬C
Selanjutnya Tabel Kebenarannya sebagai berikut:
A
B
C
¬B
¬C
A˄¬B
(A˄¬B)Þ¬C
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
Contoh 5-1.
· Tidak belajar, tidak lulus.
Kalimat tersebut dalam logika proporsional harus dibaca lengkap, yakni:
· Jika Anda tidak belajar, maka Anda tidak lulus
Jadi bentuknya sekarang yakni terlihat “jika...maka...” lalu diubah menjadi varialbel proporsional:
A = Anda belajar.
B = Anda lulus.
Sehingga menjadi
¬AÞ¬B.
Untuk mengubah pernyataan menjadi ekspresi logika:
1. Ambil pernyataan-pernyataan yang pendek, tanpa kata “dan”, “atau”,”jika...maka...”, “jika dan hanya jika”, pada pernyataan tersebut yang bila dijawab benar atau salah.
2. Ubahlah pernyataan-pernyataan yang pendek tersebut dengan variabel-variabel proposional.
3. Rangkailah variabel-variabel proposional dengan perangkai yang relevan.
4. Bentuklah menjadi proposi majemuk jika memungkinkan dengan memberi tanda kurung biasa yang tepat.
Contoh 5-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 pengerjaaanya sebagai berikut:
Langkah 1.
Menentukan proporsi-proporsi yang tepat:
1. Badu belajar rajin.
2. Badu sehat.
3. Badu lulus ujian.
Langkah 2.
Mengganti proposisi dengan variabel proposisi
A = Badu belajar rajin.
B = Badu sehat.
C = Badu lulus ujian.
Langkah 3.
Perangkai yang relevan adalah implikasi, negasi, atau, dan.
Langkah 4.
Unah menjadi ekspresi logika berupa proposisi majemuk.
((A˄B)ÞC)v((¬A˄B)ÞC.
2. Tautologi
Jika pada tabel kebenaran untuk semua pasangan nilai variabel-variabel proporsional yang ada bernilai benar atau T, maka disebut tautologi.
Contoh 5-3.
Buktikan apakah (Av¬A) adalah tautologi?
Cara membuktikannya adalah dengan membuat tabel kebenarannya.
A
¬A
Av¬A
F
T
T
T
F
T
Jadi (Av¬A) adalah tautologi.
3. Kontradiksi
Kebalikan dari tautologi, adalah kontradiksi, yaitu jika pada semua pasangan nilai dari tabel kebenaran menghasilkan F.
Contoh 5-4.
· A˄¬A
Tabel kebenarannya adalah sebagai berikut:
A
¬A
A˄¬A
F
T
F
T
F
F
· Jadi A˄¬A adalah kontradiksi.
4. Contingent
Jika semua nilai kebenaran menghasilkan nilai F dan T disebut contingent atau formula campuran.
Contoh 5-5..
((A˄B)ÞC)ÞA
Tabel kebenarannya sebagai berikut:
A
B
C
A˄B
(A˄B)ÞC
((A˄B)ÞC)ÞA
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
T
F
T
F
T
T
T
F
T
F
T
T
T
T
T
T
T
Sehingga ((A˄B)ÞC)ÞA merupakan contingent.
BAB VI
EKUIVALEN LOGIS
1. Pendahuluan
Jika suatu ekspresi logika termasuk tautologi, maka ada implikasi logis uamg diakibatkannya, yakni jika dua buah ekspresi logika ekuivalen, contohnya: A⟺B adalah ekuvallensi secara logis jika terbuktitautologi.
2. Ekuivalensi logis
Proposisi A dan B disebut ekuivalensi secara logis jika A⟺B adalah tautologi. Notasi atau simbol A ≡ Bmenandakan bahwa A dan B adalah ekuivalensi secara logis. Proposisi dapat diagnti dengan kespresi logika berupa proposisi majemuk.
Contoh 6-1.
1. Dewi sangat cantik dan peramah.
2. Dewi peramah dan sangat cantik.
Kedua pernyataan diatas, tanpa dipikir panjang, akan dikatakan ekuivalen atau sama saja. Dalam bentuk ekspresi logika dapat ditampilkan berikut ini:
A = Dewi sangat cantik.
B = Dewi peramah.
Maka ekspresi logika tersebut adalah
1. A˄B
2. B˄A
jika dikatakan kedua buah ekspresi logika tersebut ekuivalen secara logis, maka dapat ditulis:
3. (A˄B)≡( B˄A)
Ekuivalensi logis dari kedua ekspresi logika dapat dibuktikan dengan tabel kebenaran berikut ini:
A
B
A˄B
B˄A
F
F
F
F
F
T
F
F
T
F
F
F
T
T
T
T
3.Komutatif
Pada bagian di atas sudah dibahas bahwa (A˄B) ≡ (B˄A). Pada perangkai ˄ tersebut, variabel kedua proporsional dapat saling berganti tempat tanpa mengubah nilai kebenaran dari kedua ekspresi logika karena tetap memiliki nilai kebenaran yang sama. Hal ini disebut komutatif.
Jadi (A˄B)≡( B˄A).
Demikian juga perarnagkai v, maka: (AvB)≡(BvA).
Demikian juga perarnagkai ⟺, maka: (A⟺B)≡(B⟺A).
Sifat komutatif dari ketiga perangkai di atas dapat dibuktikan dengan tabel kebenaran. Akan tetapi, perangkai Þ, tidak bersifat komutatif, sehingga (AÞB)≡(BÞA) memiliki nilai kebenaran yang berbeda. Perhatikan tabel berikut.
A
B
AÞB
BÞA
F
F
T
T
F
T
T
F
T
F
F
T
T
T
T
T
Jadi terbukti bahwa kedua ekspresi logika AÞB dengan BÞA keduanya tidak ekuivalensi.
4. Assosiatif
Penempatan tanda kurung biasa pada suatu ekprsi logika memegang peranan penting,karena tanda kurung berarti meminta proses dikerjakan terlebih dahulu pada tanda kurung terdalam. Jika diterapkan pada dua buah ekspresi logika, penempatan tanda kurung biasa dapat diubah,tetpi tidak mengubah nialai kabenarannya pada tabel kebenaran yang dibuat. Perhatikan berikut:
A
B
C
A˄B
(A˄B) ˄C
B˄C
A˄(B˄C)
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
Jaid terbukti bahwa ((A˄B) ˄C)≡ (A˄(B˄C)) dan karena anda kurungnya bisa dipindahkan dan tidak mngubah nilai kebenarannya, maka disebut asosiatif.
Hukum De Morganperhatikan berikut ini:
1. ¬(A˄B) ≡¬A˅¬B
2. ¬(A˅B) ≡¬A˄¬B
Pembuktian hukum D morgan juga dapat dibuktikandengan tabel kebenaran. Seperti hukum-hukum lainnya, sebuah hukum juga dapat diberlakukan terbalik, jadi ¬(A˄B) ≡¬A˅¬B tetap akan sama dengan ¬(A˅B) ≡¬A˄¬B. Untuk hukmu-hukum lainnya, perhatikan contoh berikut:
Contoh 6-2.
1. jika Badu tidak sekolah, maka Badu tidak akan pandai.
2. jika Badu pandai, maka Badu pasti sekolah.
Untuk membuktikan ekuivalensi kedua pernyataan tersebut harus diubah mendaji ekspresi logika seperti berikut:
A = Badu sekolah.
B = Badu pandai.
Maka akan menjadi:
1. ¬AÞ¬B
2. BÞA
Pembuktian ekuivalensi dilakukan dengan tabel kebenaran seperti berikut:
A
B
¬A
¬B
¬AÞ¬B
BÞA
F
F
T
T
T
T
F
T
T
F
T
T
T
F
F
T
F
F
T
T
F
F
T
T
Jadi terbukti bahwa
¬AÞ¬B≡BÞA
Sekarang dengan perangkai ⟺ekuivalensi. Ekuivalensi antara dua ekspresi logika ini dapat dibuktikan dengan tabel kebenaran:
1. A⟺B
2. (AÞB)˄(BÞA)
Tabel kebenarannya sebagai berikut:
A
B
A⟺B
AÞB
BÞA
(AÞB)˄(BÞA)
F
F
T
T
T
T
F
T
T
T
F
F
T
F
F
F
T
F
T
T
F
F
T
T
Jadi dapat dibuktikan bahwa
A⟺B≡(AÞB)˄(BÞA)
Dalam bahasa lainnya, maka:
1. Jika A dan B mempunyai nilai kebenaran yang sama, maka...
2. Jika A maka B, dan jika B maka A.
Sekarang perhatikan pada tabel kebenaran berikut untuk membuktikan A˄B≡¬(¬A˅¬B).
A
B
A˄B
¬A
¬B
¬A˅¬B
¬(¬A˅¬B)
F
F
F
T
T
T
F
F
T
F
T
F
T
F
T
F
F
F
T
T
F
T
T
T
F
F
F
T
Jadi dapat dibuktikan bahwa:
A˄B≡¬(¬A˅¬B)
Atau perangkai ˄ dapat diganti dengan kombinasi perangkai ¬ dan ˅, demikian juga di atas bahwa perangkai ⟺ dapat digantikan kombinasi ¬ dan ˅.
A⟺B≡(AÞB)˄(BÞA)
≡(¬A˅B)˄(¬B˅A)
Selanjutnya, hukum De Morggan dapat dimodifikasi seperti berikut untuk lebih sederhananya. Lihat hukum De Morgan ke-1.
¬(A˄B) ≡¬A˅¬B
¬¬(A˄B) ≡¬(¬A˅¬B)
A˄B ≡¬(¬A˅¬B)
Dalam tautologi, nilai kebenaran dapat diganti seperti berikut:
True (T) ≡1
False (F)≡0
Sekarang dapat dicoba pada tebel kebenaran berikut:
A
1
0
A˄1
A˄0
F
T
F
F
F
T
T
F
T
F
Dengan melihat nilai pada tabel kebenaran dapat disimpulkan bahwa:
A˄1≡A
A˄0≡0
Dengan tabel kebenaran juga dapat dibuktikan bahwa:
A˅1≡A
A˅0≡0.
BAB VII
PENYEDERHANAAN
1. Pendahuluan
Pembahasan mengenai ekuivalensi logis, termasuk di dalamnya ekuivalen dan penemuan hukum-hukum pokoklogika yang diperoleh dari ekuivalensi ekspresi logika melalui pembuktian dengan taebl kebenaran sudah dibahas sebelumnya. Bab ini akan membahas penggunaan hukum-hukum logika
2. Operasi penyederhanaan.
Perhatikan opreasi penyederhanaan berikut dengan hukum yang digunakan tertulis di sisi kanannya. Pernyederhanaan ekspresi logika atau bentuk-bentuk logika ini dibuat sesederhana mungkin dan sudah tidak dimungkinkan dimanipulasi.
Contoh 7-1.
(A˅0)˄(A˅¬A) ≡ A ˄(A˅¬A)
≡ A ˄1
≡ A
Contoh 7-2.
(A˄¬B)˅(A˄B˄C) ≡ (A˄¬B)˅(A˄(B˄C))
≡ A˄(¬B˅(B˄C))
≡ A˄((¬B˅B)˄(¬B˅C))
≡ A˄(1˄(¬B˄C))
≡ A˄(¬B˄C)
3. Menghilangkan perangkai Þ dan ⟺.
Perangkai implikasi dapat digunakan hukum logika pada tabel Bab 6 yaitu:
1. AÞB ≡ ¬A˅B
Sedangkai untuk perangkai ekuivalensi dapat digunakan ekuivalen logis berikut:
2. A⟺B ≡ (A˄B)˅(¬A˄¬B)
3. A⟺B ≡ (AÞB)˄(BÞA)
Contoh 7-3.
A⟺B ≡ (AÞB)˄(BÞA)
≡(¬A˅B)˄(¬B˅A)
≡(¬A˅B)˄(A˅¬B)
4. Perangkai dasar
Perangkai dasar atau perangkai alamiah hanya ada 3, yakni ˅,˄, dan¬. Ketiga perangkai ini mampu menggantikan semua perangkai lainnya dengan mengkombinasikan ketiga perangkai tersebut. Oleh karena itu, perangkai dasar dapat juga disebut perangkai cukup. Ketiga perangkai dasar inilah yang membentuk gerbang-gerbang yang menjadi dasar sistem digital, yakni gerbang dan, gerbang atau dan gerbang tidak. Perhatikan contoh berikut:
Contoh 7-4.
¬(A˄¬A) ≡¬A˅¬¬A
≡¬A˅A
Sampai disni sudah terbukti,
................
