1 BAB I PENGANTAR LOGIKA MATEMATIKA 1.1. Pengenalan logika matematika Logika berasal dari kata bahasa Yunani “logos”. Dalam bahasa Inggris lebih dekat dengan istilah “thought” atau “reason”. Definisi Logika adalah ilmu pengetahuan yang mempelajari atau berkaitan dengan prinsip-prinsip dari penalaran argument yang valid. Logika di sini disebut logika simbol karena ia mempelajari usaha-usaha menyimbolisasikan logika secara formal. Disebut juga logika formal. Logika dipelajari sebagai sistem formal yang menjelaskan peranan sekumpulan rumus-rumus ataupun sekumpulan aturan untuk derivasi. Derivasi dipahami sebagai pembuktian validitas argument yang kuat dengan didukung kenyataan bahwa kesimpulan yang benar harus diperoleh dari premis-premis yang benar. Logika matematika adalah cabang logika dan matematika yang mengandung kajian matematis logika dan aplikasi kajian ini pada bidang-bidang lain di luar matematika. Logika matematika berhubungan erat dengan ilmu komputer dan logika filosofis. Tema utama dalam logika matematika antara lain adalah kekuatan ekspresif dari logika formal dan kekuatan deduktif dari sistem pembuktian formal. Logika matematika sering dibagi ke dalam cabang-cabang dari teori himpunan, teori model, teori rekursi, teori pembuktian, serta matematika konstruktif. Bidangbidang ini memiliki hasil dasar logika yang serupa. 1.2. Pernyataan dan Bukan Pernyataan Sebelum membahas pernyataan, terlebih dahulu kita bahas pengertian kalimat. Kalimat adalah rangkaian kata yang disusun menurut aturan bahasa yang mengandung arti. Pernyataan adalah kalimat yang mempunyai nilai benar atau salah, tetapi tidak sekaligus benar dan salah. (pernyataan disebut juga proposisi, kalimat deklaratif). Benar diartikan ada kesesuaian antara apa yang dinyatakan dengan keadaan yang sebenarnya. Contoh 1-1
Perhatikan beberapa contoh berikut!
2 1. Al-Quran adalah sumber hukum pertama umat Islam 2. 4 + 5 = 8 3. Budi mencintai 9 4. Asep adalah bilangan prima Contoh nomor 1 bernilai benar, sedangkan contoh nomor 2 bernilai salah, dan keduanya adalah pernyataan (proposisi). Sementara contoh nomor 3 dan 4 adalah kalimat yang tidak mempunyai arti.
Kemudian perhatikan contoh di bawah ini!
1. Silahkan tutup pintu itu! 2. Apakah hari ini akan hujan? 3. Bagus sekali tulisanmu! 4. Berapa jumlah mahasiswa yang belajar? Kalimat di atas tidak mempunyai nilai benar atau salah, sehingga bukan pernyataan. Catatan: Suatu pernyataan biasa kita simbolkan dengan huruf kecil p,q,r,s, dan sebagainya. Contoh 1-1
Perhatikan contoh berikut ini!
1. Yang berdiri di bawah pohon itu cantik rupanya 2. seseorang memakai kacamata hitam 3. 2x + 8y > 0 4. x + 2 = 9 Keempat contoh di atas belum tentu bernilai benar atau salah. Kalimat yang demikian itu dinamakan kalimat terbuka. Kalimat terbuka biasanya ditandai dengan adanya variabel (peubah).
3 Jika variabelnya diganti dengan konstanta dalam semesta yang sesuai maka kalimat itu akan menjadi sebuah pernyataan. Variabel (Peubah) adalah lambang yang menunjukkan anggota yang belum tentu dalam semesta pembicaraan, sedangkan konstanta adalah lambang yang menunjukkan anggota tertentu dalam semesta pembicaraan. Pengganti variabel yang menyebabkan kalimat terbuka menjadi pernyataan yang bernilai benar, disebut selesaian atau penyelesaian. Contoh 1-3 x+2=8 x adalah variabel, 2 dan 8 adalah konstanta, dan x = 6 untuk x anggora bilangan real adalah selesaian. Secara skematik, hubungan kalimat, pernyataan, dan kalimat terbuka dapat kita rumuskan sebagai berikut:
1.3. Jenis Proposisi proposisi dapat dibagi berdasarkan nilai kebenarannya menjadi dua macam, yaitu: 1. Proposisi variable, proposisi yang nilai kebenarannya belum bisa dipastikan Contoh : o Hari ini akan hujan
4 o Presiden RI periode yang akan dating adalah Rhoma Irama Contoh di atas memiliki nilai kebenaran namun belum bisa dipastikan nilai kebenarannya sudah pasti benar atau salah. 2. Proposisi konstanta, proposisi yang nilai kebenarannya sudah bisa dipastikan Contoh :
Sumatera Selatan merupakan provinsi kota Palembang (benar / true)
Bernapas merupakan salah satu ciri makhluk hidup (benar / true)
Meja merupakan makhluk hidup (salah / false)
Dari contoh di atas memiliki nilai kebenaran yang sudah bisa ditentukan. Latihan soal I 1. Apakah yang di maksud dengan proposisi? 2. Apakah perbedaan proposisi variable dan proposisi konstanta? 3. Berikan 5 contoh proposisi variable! 4. Berikan 5 contoh proposisi konstanta! 5. Tentukan yang mana termasuk proposisi dari beberapa kalimat di bawah ini, berikan alas an! a. Ibu adalah seorang wanita yang melahirkan kita b. Di mana kau membeli buku ini? c. Apakah anda senang belajar Logika Matematika? d. Tidurlah bila kau mengantuk! e. Makan adalah salah satu kebutuhan makhluk hidup f.
2x - 5 = 10
g. 1 + 7 = 9
5
BAB II TABEL KEBENARAN 2.1.Perangkai / Operator Logika Operator logika merupakan hal yang paling penting dalam menentukan table kebenaran, dengan adanya operator logika suatu proposisi bisa dibentuk menjadi suatu premis yang kemudian bisa dibuktikan kebenarannya melalui table kebenaran. Berikut beberapa operator logika yang akan kita pelajari. : Merupakan lambang operasi untuk negasi : Merupakan lambang operasi untuk konjungsi : Merupakan lambang operasi untuk disjungsi : Merupakan lambang operasi untuk implikasi : Merupakan lambang operasi untuk biimplikasi
2.2.Konjungsi (AND) Konjungsi dua pernyataan p dan q bernilai benar hanya jika kedua pernyataan komponennya bernilai benar. Dan jika salah satu atau kedua pernyataan komponennya salah, maka konjungsi itu salah dengan Simbol ∧ Dengan tabel kebenaran
Contoh:
6 1. p : 5 bilangan prima (B) q : 5 bilangan ganjil (B) : 5 bilangan prima dan ganjil (B) 2.3.Disjungsi (OR) Disjungsi dari dua buah pernyataan p dan q bernilai benar asal salah satu atau kedua pernyataan komponennya benar. Dan jika kedua pernyataan komponennya salah, maka konjungsi itu salah. (Disjungsi seperti ini disebut disjungsi inklusif) Dengan tabel kebenaran
Contoh : p : Bogor di Jawa barat (B) q : Bogor itu kota propinsi (S) : Bogor di Jawa Barat atau ibu kota propinsi (B) 2.4.Negasi (Ingkaran) Sebuah Pernyataan Dari sebuah pernyataan tunggal (atau majemuk), kita bisa membuat sebuah pernyataan baru berupa “ingkaran” dari pernyataan itu. “ingkaran” disebut juga “negasi” atau “penyangkalan”. Ingkaran menggunakan operasi uner (monar) “ ” atau “ ”. Jika suatu pernyataan p benar, maka negasinya maka negasinya
p salah, dan jika sebaliknya pernyataan p salah,
p benar.
Definisi tersebut dinyatakan dalam tabel sebagai berikut:
7
2.5.Implikasi boleh dibaca: jika p maka q q hanya jika p p syarat perlu untuk q q syarat cukup untuk p p disebut anteseden atau hipotesis q disebut konsekuen atau konklusi Implikasi
bernilai benar jika konsekuennya bernilai benar atau anteseden dan konsekuen
kedua-duanya salah, dan bernilai salah jika antesedennya bernilai benar, sedangkan konsekuennya salah. Dengan tabel kebenaran
Contoh: 1. Jika 2 x 2 = 4, maka 4 : 2 = 2 (B)
(B)
(B)
2. Jika manusia bersayap , maka kita bisa terbang
(B)
8 (S)
(S)
2.6.Biimplikasi atau Bikondisional (
)
boleh dibaca: p jika dan hanya jika q (disingkat “p jhj q”) jika p maka q, dan jika q maka p p syarat perlu dan cukup untuk q \q syarat perlu dan cukup untuk p biimplikasi
bernilai benar apabila anteseden dan konsekuen kedua-duanya bernilai benar
atau kedua-duanya bernilai salah. Jika tidak demikian maka biimplikasi bernilai salah. Dengan tabel kebenaran
Contoh: 1. 2 x 2 = 4 jika dan hanya jika 4 : 2 = 2 (B)
(B)
2. 2 x 4 = 8 jika dan hanya jika 8 : 4 = 0 (B)
(B)
(S)
(S)
9
Latihan Soal II 1. Gunakan konstanta proposisional A untuk “Adi rajin belajar” dan B untuk “Adi juara kelas”. Lalu ubahlah pernyataan berikut dalam bentuk logika! a. b. c. d. e.
Adi tidak rajin belajar Adi tidak juara kelas Adi rajin belajar dan juara kelas Adi rajin belajar maka Adi juara kelas Adi juara kelas atau Adi rajin belajar
2. Tentukan table kebenarannya! a. (A → B) ˄ A b. A ˄ ̚ B c. A↔ (B ˄ ̚ B) d. A ˅ ̚ B e. A ˅ A
10 BAB III PROPOSISI MAJEMUK 3.1. Proposisi majemuk Proposisi majemuk merupakan suatu gabungan proposisi tunggal yang dirangkai oleh operator logika. Proposisi majemuk lebih dikenal sebagai premis. Proposisi tunggal sendiri merupakan suatu proposisi yang berdiri sendiri tanpa perangkai apa pun. Contoh proposisi tunggal: 1. Ani memasak di dapur 2. Ibu belanja bahan masakan di pasar 3. Adik membantu ayah berkebun Contoh di atas merupakan proposisi tunggal karena tidak ada keterkaitan antara contoh satu dan lainnya ataupun operator logika yang merangkai ketiga contoh sehingga menjadi satu kesatuan. Namun dari ketiga contoh di atas dapat dibentuk suatu premis atau proposisi majemuk, sehingga menjadi: Ani memasak di dapur dan ibu belanja bahan masakan di pasar sehingga adik membantu ayah berkebun. Kata “dan’ dan “sehingga” yang merupakan kata penghubung kita sebut sebagai operator logika
yang merangkai proposisi tunggal sehingga menjadi sebuah premis (proposisi
majemuk). 3.2. Ekspresi Logika Ekspresi Logika adalahproposisi-proposisiyang dibangun oleh variabel-variabel logika yang berasal dari pernyataan atau argument Contoh: A⇒B Setiap ekspresi logika dapat bersifat atomik (tunggal) atau majemuk tergantung dari variable proposisional yang membentuknya bersama perangkai logika yang relevan.
11 Contoh : Jika saya merasa sedih sekali maka saya akan menangis dan berlari sejauh mungkin Variable proposisinya terdiri dari : A : saya merasa sedih sekali B : saya akan menangis C : saya berlari sejauh mungkin Sehingga ekspresi logikanya : A →(B ˄C) 3.2. Skema Skema (schemas) merupakan cara untuk menyederhanakan suatu proposisi mejemuk yang rumit, dengan memberi tanda huruf tertentu untuk menggantikan
suatu sub ekspresi
ataupun sub-sub eksresi. Definisi: semua ekspresi yang berisi identifikator-identifikator yang menunjukkan adanya suatu ekspresi logika disebut skema. Suatu ekspresi logika tertentu , misalnya (A ۸ B) dapat diganti dengan P, sedangkan (A v B) dapat dianti dengan Q. Jadi P berisi variabel proposisional A dan B, demikian juga Q. P di sini bukan varibel proposisional, karena nilai P tergantung dari nilai A dan B. Contoh : P = (A ˄ B) dan Q = (A v B), maka (P → Q) = ((A ˄ B) → (A v B))
Sekarang perhatikan yang berikut ini : (1). Expresi apa saja berbentuk (┐P) disebut negasi. (2). Expresi apa saja berbentuk (P ˄ Q) disebut konjungsi. (3). Expresi apa saja berbentuk (P v Q) disebut disjungsi.
12 (4). Expresi apa saja berbentuk (P → Q) disebut implikasi (conditional) (5). Expresi apa saja berbentuk (P ↔ Q) disebut ekuivalensi (biconditional)
Contoh di atas ((A ˅ B) → (A ˄ B)) disebut implikasi yang berisi konjungsi (A˅B) dan disjungsi (A v B). Sekarang lihat aturan berikut ini : (1). Semua ekspresi atomik adalah fpe (2). Jika P adalah fpe, maka juga (┐P) (3). Jika P dan Q adalah fpe, maka juga (P ˄ Q), (P ˅ Q), (P → Q) dan (P↔Q) (4). Tak ada fpe lainnya.
Ekspresi-ekspresi logika yang dijelaskan di atas disebut well formed formulae (wff). jadi, wff adalah fpe demikian juga sebaliknya. Jika ada suatu ekspresi logika yang di jelaskan di atas di sebut well-formed formulae (wff). Jadi wff adalah fpe demikian juga sebaliknya. Jika ada suatu ekspresi logika (┐P). Maka P disebut skop negasi (scope of negation) dengan perangkai disebut perangkai utama (main connective) dari (┐P). maka contoh di atas, yakni (P→Q),dapat di uraikan sebagai berikut: (P → Q) ↑ Skop kiri
Perangkai utama ↓ ((A
B) → (A v B))
skop kanan
13 BAB IV TAUTOLOGI 4.1. Tautologi Tautologi adalah pernyataan majemuk yang selalu benar untuk semua kemungkinan nilai kebenaran
dari
pernyataan-pernyataan
komponennya.
Sebuah
Tautologi
yang
memuat
pernyataan Implikasi disebut Implikasi Logis. Untuk membuktikan apakah suatu pernyataan Tautologi, maka ada dua cara yang digunakan. Cara pertama dengan menggunakan tabel kebenaran, yaitu jika semua pilihan bernilai T (true) maka disebut Tautologi, dan cara kedua yaitu dengan melakukan penjabaran atau penurunan dengan menerapkan sebagian dari 12 hukum-hukum Ekuivalensi Logika. Contoh: Lihat pada argumen berikut: Jika Tono pergi kuliah, maka Tini juga pergi kuliah. Jika Siska tidur, maka Tini pergi kuliah. Dengan demikian, jika Tono pergi kuliah atau Siska tidur, maka Tini pergi kulah. Diubah ke variabel proposional: A Tono pergi kuliah B Tini pergi kuliah C Siska tidur Diubah lagi menjadi ekspresi logika yang terdiri dari premis-premis dan kesimpilan. Ekspresi logika 1 dan 2 adalah premis-premis, sedangkan ekspresi logika 3 adalah kesimpulan. (1) A → B
(Premis)
(2) C → B
(premis)
(3) (A ˅ C) → B
(kesimpulan)
Maka sekarang dapat ditulis: ((A→B)˄(C→B))→((A˅C)→B
14
Dari
tabel
kebenaran
diatas
menunjukkan
bahwa
pernyataan
majemuk
:
((A → B) ʌ (C → B)) → ((A V C) → B) adalah semua benar (Tautologi) A
B
C
A→B
C→B
(A→B)˄(C→B)
A˅C
(A˅C) → B
((A→B)˄(C→B)) → ((A˅C) → B))
T
T
T
T
T
T
T
T
T
T
T
F
T
T
T
T
T
T
T
F
T
F
F
F
T
F
T
T
F
F
F
T
F
T
F
T
F
T
T
T
T
T
T
T
T
F
T
F
T
T
T
F
T
T
F
F
T
T
F
F
T
F
T
F
F
F
T
T
T
F
T
T
4.2. kontradiksi Kontradiksi adalah suatu proporsi majemuk yang selalu bernilai salah untuk semua kemungkinan
kombinasi
nilai
kebenaran
dari
proporsi-proporsi
pembentuknya.
Untuk
membuktikan apakah suatu pernyataan tersebut kontradiksi, maka ada dua cara yang digunakan. Cara pertama dengan menggunakan tabel kebenaran, yaitu jika semua pilihan bernilai F
atau
salah maka disebut kontradiksi, dan cara kedua yaitu dengan melakukan penjabaran atau penurunan dengan menerapkan sebagian dari 12 hukum-hukum Ekuivalensi Logika.
15 Contoh : ( A ˅ B ) ˄ (( ┐A ) ˄ ( ┐B )) A
B
┐A
┐B
A˅B
┐A˄┐B
( A ˅ B ) ˄ (( ┐A ) ˄ ( ┐B ))
T
T
F
F
T
F
F
T
F
F
T
T
F
F
F
T
T
F
T
F
F
F
F
T
T
F
T
F
4.3. Contingent Contingent adalah suatu ekspresi logika yang mempunyai nilai benar dan salah di dalam tabel kebenarannya, bisa juga dikatakan sebagai suatu proporsi majemuk yang bukan termasuk tautologi dan bukan juga kontradiksi. Contoh : (( p ˄ q ) → r ) → p P
q
R
P˄q
(p˄q)→r
(( p ˄ q ) → r ) → p
T
T
T
T
T
T
T
T
F
T
F
T
T
F
T
F
T
T
16 T
F
F
F
T
T
F
T
T
F
T
F
F
T
F
F
T
F
F
F
T
F
T
F
Pada contoh di atas terlihat bahwa kombinasi proposisi menghasilkan kesimpulan yang merupakan kombinasi true dan false sehingga tidak termasuk kontradiksi ataupun tautology.
17 Latihan soal IV 1. Berikan contoh proposisi majemuk yang terdiri dari 3 (tiga) buah proposisi atom! 2. Buatlah ekspresi logika yang mewakili contoh proposisi majemuk yang anda buat pada soal no 1.! 3. Buatlah table kebenaran dari ekspresi logika pada no 2.! 4. Tentukan apakah table kebenaran yang anda buat pada soal no 3. termasuk tautology, kontradiksi atau contingent! 5. Berikan masing-masing 1 (satu) contoh ekspresi logika yang termasuk tautology, kontradiksi dan contingent!
18 BAB V EKIUVALENSI LOGIS
5.1.EKUIVALEN SECARA LOGIS Jika dua buah ekspresi logika adalah tautologi atau kontradiksi, maka kedua buah ekspresi logika tersebut ekuivalen secara logis. Lain halnya dengan contingent, di mana ia memiliki semua nilai T dan F. Jika urutan T dan F atau sebaliknya pada tabel kebenaran tetap pada urutan yang sama, maka contingent juga disebut ekuivalen secara logis. Contoh 5-1: Perhatikan pernyataan berikut ini: (1) Dewi sangat cantik dan peramah (2) Dewi peramah dan sangat cantik Kedua pernyataan tersebut di atas, secara sekilas akan tampak ekuivalen atau sama saja, yang 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 dua buah ekspresi logika tersebut ekuivalen secara logis, maka dapat ditulis: (A B) (B A)
19 Ekuivalensi logis dari kedua ekspresi logika dapat dibuktikan dengan tabel kebenaran berikut ini: A
B
AB
BA
F
F
F
F
F
T
F
F
T
F
F
F
F
T
T
T
Gambar 5-1 Tabel kebenaran (A B) (B A) Dalam tabel kebenaran di atas, walaupun setiap ekspresi logika memiliki nilai T dan F, tetapi karena terletak pada urutan yang sama, maka tetap dikatakan ekuivalen secara logis. Seandainya urutan T dan F tidak sama, maka tidak bisa dikatakan ekuivalen secara logis.
Definisi: Proposisi A dan B disebut ekuivalen secara logis jika AB adalah tautologi. Notasi atau simbol A B menandakan bahwa A dan B adalah ekuivalen secara logis. Proposisi dapat diganti dengan ekspresi logika berupa proposisi majemuk. Tabel kebenaran merupakan alat untuk membuktikan kebenaran ekuivalen secara logis. Kesimpulan diambil berdasarkan hasil dari tabel kebenaran tersebut. Contoh 5-2: Lihat kalimat berikut ini: (1) Badu tidak pandai, atau dia tidak jujur (2) Adalah tidak benar jika Badu pandai dan jujur Secara intuitif dapat ditebak bahwa kedua pernyataan di atas sebenarnya sama saja, tetapi apakah benar demkian jika dibuktikan dengan tabel kebenaran berdasarkan ekspresi logika. Untuk itu perlu diubah dahulu menjadi ekspresi logika dengan memberi variabel proposisional: A = Badu pandai
20 B = Badu jujur Maka kedua pernyataan tersebut menjadi: (1) A B (2) ( A B) Terbuktilah sekarang bahwa berdasarkan tabel kebenaran, kedua ekspresi logika di atas ekuivalen. A
B
AB
A B
( A B)
F
F
F
T
T
F
T
F
T
T
T
F
F
T
T
T
T
T
F
F
Gambar 5-2 Tabel kebenaran (A B) dan ( A B) Perhatikan: Walaupun kedua ekspresi logika di atas memiliki nilai kebenaran yang sama - meskipun ada nilai T dan F - keduanya hanya dapat dikatakan ekuivalen secara logis jika dihubungkan dengan perangkai ekuivalensi dan akhirnya menghasilkan tautologi.
21 Perhatikan lanjutan tabel kebenarannya sebagai berikut: (A B) ( A B) T T T T Gambar 5-3 Tabel kebenaran (A B) ( A B) Kedua ekspresi di atas dapat dikatakan ekuivalen secara logis, karena semua nilai kebenarannya bernilai T atau tautologi.
5.2.KOMUTATIF Di atas sudah dibahas bahwa (AB) (BA). Dengan perangkai ,variabel kedua proposisional tersebut dapat saling menggantikan tempat tanpa mengubah nilai kebenaran ekspresi logika keduanya. Hal ini disebut komutatif (commutativity). Jadi: (AB) (BA) Demikian juga dengan perangkai : (AB) (BA) dan perangkai : (AB) (BA) Sifat komutatif dari ketiga perangkai tersebut di atas, dapat dibuktikan dengan tabel kebenaran. Lain halnya dengan perangkai (implikasi). Perangkai ini tidak memiliki sifat komutatif, oleh
22 karena itu (AB) dengan (BA) memiliki nilai kebenaran yang berbeda. Lihat pembuktiannya pada tabel kebenaran berikut ini: A
B
AB
BC
F
F
T
T
F
T
T
F
T
F
F
T
T
T
T
T
Gambar 5-4 Tabel kebenaran AB dan BA Dari tabel tersebut terlihat bahwa ekspresi logika AB dengan BA keduanya tidak ekuivalen. 5.3.ASOSIATIF Penempatan tanda kurung biasa pada suatu ekspresi logika memegang peran penting, karena tanda kurung menunjukkan urutan prioritas proses pengerjaan. Perhatikan masalah fpe pada babbab terdahulu. Jika diterapkan pada dua buah ekspresi logika, penempatan tanda kurung biasa dapat diubah tanpa mengubah nilai kebenarannya pada tabel kebenaran yang dibuat. Contoh 5-3: Lihat berikut ini: ((A B) C) dan (A (B C)) Tabel kebenarannya adalah sebagai berikut: A
B
C
A B
(A B)C
B C
A (BC)
F
F
F
F
F
F
F
F
F
T
F
F
F
F
23 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
Gambar 5-5 Tabel kebenaran (A B) C dan A (B C) Maka dapat dibuktikan bahwa: ((A B) C) (A (B C)) Proses pemindahan tanda kurung bisa tanpa mengubah nilai kebenarannya ini disebut asosiatif (associativity). Asosiatif lain biasanya terjadi pada perangkai yang sama, seperti dan . Contoh ((AB)C) (A(BC)). Lain halnya dengan perangkai (implikasi). Jika pada AB dan BA sudah bernilai tak sama, tentu saja ((AB)C) dan (A(BC)) juga pasti tidak sama. Karena itu jika pada satu ekspresi logika perangkainya berbeda, jangan sembarangan memindah tanda kurung. Hal ini akan menghasilkan nilai kebenaran yang berbeda. Contoh 5-4: Lihat: ((A B) C) dan (A ( B C)) dengan tabel kebenaran: A
B
C
A B
(A B)C
B C
A (BC)
F
F
F
F
F
F
F
F
F
T
F
T
T
F
24 F
T
F
F
F
T
F
F
T
T
F
T
T
F
T
F
F
F
F
F
F
T
F
T
F
T
T
T
T
T
F
T
T
T
T
T
T
T
T
T
T
T
Gambar 5-6 Tabel kebenaran (A B) C dan A ( B C) Nilai kebenaran dari (AB)C dan A(BC) terbukti tidak sama, walaupun urutan perangkainya sama. Hal ini disebabkan oleh letak tanda kurung yang berbeda, yang menyebabkan adanya perbedaan nilai kebenaran. Jadi, pada gabungan perangkai dan , pemberian tanda kurung yang berbeda menyebabkan nilai kebenaran yang berbeda pula. Sedangkan pada perangkai (implikasi), karena pada AB dan BA sudah bernilai tak sama, maka ((AB)C) dan (A(BC)) juga pasti tidak sama. 5.4.HUKUN-HUKUM LOGIKA Dari ekuivalensi secara logis, dapat dikembangkan hukum-hukum logika untuk membuktikan berbagai keperluan, termasuk membuktikan validitas sebuah argumen. Hukum-hukum logika antara lain berasal dari ekspresi-ekspresi logika berdasarkan pernyataan-pernyataan, oleh karena itu kebenarannya dapat dibuktikan melalui pernyataan tersebut.
Contoh 5-5: Lihat: (1) Jika Anda tidak belajar, maka Anda akan gagal (2) Anda harus belajar, atau Anda akan gagal
25 Untuk membuat ekspresi logika, maka variabel proposisional harus diganti lebih dahulu seperti berikut: A = Anda belajar B = Anda gagal
Maka ekspresi logikanya akan menjadi: (1) A B (2) A B Buktikan bahwa AB AB dengan memakai tabel kebenaran. A
B
AB
A
A B
F
F
T
T
T
F
T
T
T
T
T
F
F
F
F
T
T
T
F
T
Gambar 5-7 Tabel kebenaran AB dan AB Ternyata AB AB karena memiliki nilai kebenaran yang sama. Dari tabel kebenaran tersebut juga dapat dibuktikan bahwa perangkai (operator) dapat diganti dengan perangakai dan . Sekarang perhatikan hukum De Morgan (De Morgan’s law) berikut: (1) (A B) A B (2) (A B) A B Kebenaran hukum De Morgan juga dapat dibuktikan dengan tabel kebenaran. Ingat, bahwa selama nilai kebenarannya sama, maka tetap disebut ekuivalen.
26 Seperti hukum-hukum lainnya, hukum ini pun dapat dilakukan terbalik. Jadi,
(A B) A
B tetap akan sama dengan A B (A B). Sejarah Singkat : Augustus De Morgan (1806-1871) dilahirkan di India. Ayahnya seorang kolonel di ketentaraan India. Keluarga De Morgan pindah ke Inggris ketika dia berumur 7 tahun. Ia masuk sekolah pribadi dan sejak kecil sangat berminat di bidang matematika. De Morgan belajar di Trinity College, Cambridge, lulus tahun 1827. Ia mendapat pekerjaan di University College, London, di tahun 1828, tetapi sempat berhenti dan kembali tahun 1836 dan terus di sana sampai tahun 1866. De Morgan merupakan guru yang lebih menekankan prinsip daripada teknik. Di antara muridnya adalah Augusta Ada, Countess of Lovelace, yang membantu Charles Babbage mewujudkan mesin komputasi, awal mesin komputer. De Morgan sudah mengenali kemampuan Augusta Ada di bidang matematika sejak dini. De Morgan juga seorang penulis yang produktif. Ia menulis lebih dari 1000 artikel selama 15 periode. De Morgan membuat berbagai buku teks di berbagai bidang, misalnya logika, probabilitas, kalkulus dan aljabar. Tahun 1838, ia menjelaskan pembuktian yang penting yang disebut mathematical induction, suatu pengertian yang sangat ia kuasai. Tahun 1842,
De Morgan juga menyumbang pengembangan logika simbolik. Ia
menemukan berbagai notasi yang membantunya membuktikan ekuivalensi proposisional, seperti hukum yang disebut sesuai dengan namanya. De Morgan mungkin juga orang yang pertama kali mendefinisikan pengertian limit dan pengembangan test tentang konvergensi dari infinite series. Pada tahun 1837 De Morgan menikah dengan Sophia Freud, yang menulis biografi De Morgan tahun 1882. Tugas riset, mengajar dan menulis menyebabkannya hanya menyisakan sedikit waktu bagi keluarganya dan kehidupan sosialnya. Walaupun begitu, ia banyak dikenal karena berbagai ilmu yang dikembangkannya, sifat humorisnya dan keramahtamahannya.
27 Contoh 5-6: Hukum-hukum logika lainnya dapat dilihat berikut ini: (1) Jika Badu tidak sekolah, maka Badu tidak akan pandai (2) Jika Badu pandai, maka Badu pasti sekolah
Untuk membuktikan ekuivalensi kedua pernyataan tersebut, maka harus di ubah menjadi 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 ini: A
B
A
B
AB
BA
F
F
T
T
T
T
F
T
T
F
T
T
T
F
F
T
F
F
T
T
F
F
T
T
Gambar 5-8 Tabel kebenaran AB dan BA dan terbukti bahwa: A B B A Sekarang dengan perangkai (ekuivalensi) atau if and only if, ekivalen antara dua ekspresi logika ini dapat dibuktikan dengan tabel kebenaran:
28 (1) A B (2) (A B) (B A) Tabel kebenarannya: A
B
AB
AB
BA
(AB) (BA)
F
F
T
T
T
T
F
T
F
T
F
F
T
F
F
F
T
F
T
T
T
T
T
T
Gambar 5-9 Tabel kebenaran A B dan (A B)(B A) Jadi, dapat dibuktikan bahwa: A B (A B)(B A) Dalam bahasa lainnya: (1) Jika A dan B mempunyai nilai kebenaran yang sama, maka… (2) Jika A maka B, dan jika B maka A. Sekarang perhatikan tabel kebenaran berikut untuk membuktikan AB (AB). 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
Gambar 5-10 Tabel kebenaran A B dan (AB) Jadi, dapat dibuktikan bahwa:
29 A B (A B) Selain itu perangkai dapat diganti dengan kombinasi perangkai dan . Begitu juga perangkai di atas dapat diganti dengan kombinasi perangkai dan . A B (A B) (B A) (A B) (B A) Karena itu sekarang hukum De Morgan dapat dimodifikasi, agar lebih sederhana. Lihat hukum ke-1: (A B) A B (A B) (A B) A B (A B) Hukum ke-2 akan menjadi seperti berikut: A B (A B) Dalam tautologi, nilai kebenaran dapat diganti seperti berikut: True 1 False 0 Dan sekarang dapat dicoba pada tabel kebenaran seperti berikut: A
1
0
A 1
A 0
F
T
F
F
F
T
T
F
T
F
Gambar 5-11 Tabel kebenaran A1 dan A0
30 Dengan melihat nilai pada tabel kebenaran dapat disimpulkan bahwa: A1 A
(Identity of )
A0 0
(Zero of )
Selain itu dengan tabel kebenaran, dapat dibuktikan pula bahwa: A1 1
(Identity of )
A0 A
(Zero of )
Berikut ini akan dibuat tabel yang berisi hukum-hukum logika yang penting dan banyak digunakan untuk melakukan operasi logika. Semua hukum-hukum tersebut dapat dibuktikan dengan tabel kebenaran. Biasanya hukum-hukum tersebut berpasangan (kecuali pada hukum negasi ganda atau Law of Double Negation), sehingga disebut pasangan ganda (Dual Pairs). Lihat Tabel 5-12.
31 Tabel 5-12 Tabel hukum-hukum pokok logika (Daftar Ekuivalensi)
HUKUM
NAMA
A1 A
Identity of (Identity Laws)
A0 A
Zero of (Identity Laws)
A1 1
Identity of (Dominition Laws)
A0 0
Zero of (Dominition Laws)
AA 1
Tautology (Excluded Middle Law)
AA 0
Law of Contradiction
AA A
Idempotence Laws
AA A
Idempotence Laws
A A
Law of Double Negation
AB BA
Commutativity (Commutative Laws)
AB BA
Commutativity (Commutative Laws)
(AB)C A(BC)
Associativity (Assosiative Laws)
(AB)C A(BC)
Associativity (Assosiative Laws)
A(BC) (AB)(AC)
Distributivity (Distributive Laws)
A(BC) (AB)(AC)
Distributivity (Distributive Laws)
A(AB) A
Absorption
32 A(AB) A
Absorption
A(AB) AB
Absorption
A(AB) AB
Absorption
(AB) AB
De Morgan’s Law
(AB) AB
De Morgan’s Law
(AB)(AB) A AB AB AB (AB) AB (AB)(AB) AB (AB)(BA)
33 Latihan Soal V Buktikan bahwa ekspresi-ekspresi logika berikut ini ekuivalen, dengan menggunakan tabel kebenaran! (1) AB (AB) (BA) (2) A(AB) 1 (3) (AB) C (AB) C (4) A(BC) (AB) C (5) AB (AB) (6) ((AB) B) 0 (7) ((A(BC)) (A(BC)))A 1
34
BAB VI PENYEDERHANAAN 6.1.OPERASIONAL PENYEDERHANAAN Operasi-operasi penyederhanaan dapat dilakukan dengan menggunakan Tabel 5-1 yang berisi berbagai hukum logika, baik yang memiliki nama maupun tidak. Perhatikan operasi penyederhanaan berikut ini beserta hukum yang digunakan yang tertulis di sisi kanannya. Penyederhanaan eksposisi logika atau bentuk-bentuk logika ini dibuat sederhana mungkin. Contoh 6-1 ( A AW ) ( A A )
A ( A A)
Zero of
A1
Tautologi
A
Identity
Contoh 6-2 ( A A ) ( ABC )
( A A ) A( BC ))
Asosiatif
A ( B (B C ))
Distributif
A (( B B) ( BC ))
Distributif
A (1 ( B C ))
Tautologi
A ( B C )
Identity
35 Contoh 6-3 ((A (B C))A(A (B C))) A
((A ( BvC) ( Av ( Bv C)))vA
A8
( (A ( BvC) v ( Av ( Bv C)))vA
De Morgar’s Law
(( Av ( BvC)) v( Av ( Bv C)))vA
De- Morgan's Law
(( Av( B C)) v ( A ( B C)))v De- Morgan's Law (( Av(B C) v (A (BC)vA
Law of Double N
( Av(B C) v (A(BC))vA
Asosiatif
( Av(B C) v Av(A (BC )
Komutatif
( Av (B C) v (Av(A (BC )))
Asosiatif
( Av (B C) v A
Assorption
Av( Av (B C)
Komutatif
(Av( Av (B C))
Asosiatif
(Av A)
Absorption
1
Tautologi
Contoh 6-4 ( A B) ((A B) A)
( Av B) v ( ( Av B)v A))
A-B
( A B)v( A B) v A))
De Morgan's Law
( AB)v(A B)v A))
La of Double N
( AB)v(A( A B))
Komutatif
36
( AB)v( Av ( A B))
Absorption
( AB)v( Av B)
Asosiatif
( Av B) v Av B
komutatif
A ( Av B) v B
Asosiatif
Av B
Absorption
Penyederhanaan akan berhenti pada bentuk ekspresi logika yang paling sederhana, dan sudah tidak mungkin disederhanakan lagi. Ekuivalen-ekuivalen sebenarnya memberikan aljabar dari ekspresi-ekspresi, dan aljabar tersebut merupakan suatu instance of class (atau type) dari aljabar yang dinamakan Aljabar Boole (Boolean algebras).
6.2.Menghilangkan perangkai “DAN” Sudah dibahas di atas, bahwa perangkai dasar sebenarnya hanya , dan . Jadi, semua perangkai, dapat dijelaskan hanya dengan tiga perangkasi dasar atau alamiah tersebut. Dengan demikian, perangkai implikasi (conditional) dan ekuivalen (biconditional) dapat diganti dengan perangkai dasar. Untuk perangkai implikasi, dapat digunakan hukum logika pada tabel 5-1: (A B) AvB Sedangkan untuk perangkai ekuivalen, dapat digunakan hukum logika berikut: (2) (A B) (AB)v( A B) (3) (A B) (A B) (B A)
37 Contoh 6-5 Hilangkan tanda dari logika no: 3 di atas! (A B) (A B) (B A)
( AvB) ( AvB)
AB
( AvB) (Av B)
Komutatif
Contoh 6-6 Hilangkan tanda dan (dari ekspresi logika berikut ini: (A B) C) v ((CD) (BvD))
(( AvB) C) v ((C D) (BvD)) A B (( AvB) C) v (((C D) (D C)) (BvD))
AB
(( AvB) C) v ((( C v D) ( D v C)) (BvD)) A B (( AvB) C) v (( C v D) ( D v C)) (BvD)) Asosiatif Sekarang sudah hilang semua perangkat dan dari ekspresi logika yang diinginkan. Tetapi, apakah bentuk logika yang diperoleh masih bisa disederhanakan lagi? Hal ini bisa dicoba dengan hukum-hukum logika. \ 6.3.Perangkai Cukup Perangkai cukup (sufficiently connected) sebenarnya hanya ingin menunjukkan bahwa ekspresi atau bentuk logika dengan perangkai apa saja dapat diubah menjadi ekspresi logika dengan memakai apa saja dapat diuba menjadi eskpresi logika dengan memakai perangkai dasar atau perangkai ilmiah, yakni , dan . Bahkan ekspresi logika dengan perangkai dapat diubah menjadi dan , dan bentuk logika dengan perangkai dapat diubah dengan memakai perangkai dan . Perhatikan contoh berikut :
38 Contoh 6-7
(A A)
Av A
De Morgan’s Law
AvA
Law of Double Negation
Sampai di sini sudah terbukti, tetapi masih dapat disederhanakan :
1
Tautologi
Contoh 6-8
(Av A)
A A
De Morgan’s Law
AA
Law of Double Negatio
Untuk contoh dengan perangkai dan dapat dilihat pada tebel 5-1 Sekarang bagaimana dengan perangkai Nand dan Nor yang tabel kebenarannya telah dibahas pada Bab 2 di atas? Apakah memang kedua perangkai tersebut perangkai cukup dan dapat dijelaskan hanya dengan , dan . ? Kita mulai denan perangkai Nand – yang sebenarnya juga dapat ditulis (AB) -dengan membuat tabel kebenaran seperti berikut : A
A
A A
A
F
F
T
T
T
T
F
F
Tabel 6-1 kebenaran A/A dan A
39 Perhatikan tabel kebenaran tersebut, hasilnya ternyata : AA A Lalu lihat tabel kebenaran berikut ini : A
B
A B
(AB)(AB)
AB
F
F
T
F
F
F
T
T
F
F
T
F
T
F
F
T
T
F
T
T
Tabel 6-2 tabel kebenaran (AB)(AB) dan AB
Hasilnya ternyata : (AB)(AB) AB Dengan demikian perangkai Nand tergologn perangkai cukup, karena ia dapat dijelaskan denan perangkai dasar. Selanjutnya perangkai Nor yang sebenarnya dapat ditulis (AvB) apakah benar ia juga merupakan perangkai cukup. Lihat tabel kebenaran berikut ini: A
A
AA
A
F
F
T
T
T
T
F
F
Tabel 6-3 tabel kebenaran AA dan A Perhatikan tabel kebenaran tersebut, hasilnya : AA A Lalu lihat tabel kebenaran berikut ini :
40 A
B
AB
(AB) (AB)
AvB
F
F
T
F
F
F
T
F
T
T
T
F
F
T
T
T
T
F
T
T
Tabel 6-4 tabel kebenaran (AB) (AB) dan AvB Hasilnya ternyata : (AB) (AB) AvB Jadi, sebenarnya perangkai Nor juga perangkai cukup, karena ia juga dapat dijelaskan denan perangkai dasar. Bahkan ternyata perangkai Nand ekuivalen dengan perangkai Nor seperti yang dibuktikan dengan tebel kebenaran berikut : A
A
AA
A A
F
F
T
T
T
T
F
F
Tabel 6-5 tabel kebenaran AA dan A A Atau ternyata hasilnya cukup mengejutkan : AA A A Tetapi, bagaimana jika AA A A, apakah memang benar terbukti dengan tabel kebenaran?
LATIHAN SOAL VI BAGIAN -1 :
41 Sederhanakan bentuk-bentuk logika berikut ini menjadi bentuk yang paling sederhana! (1) A (AA) (2) (A(BB)) (3) A(AB) (4) (AB)(( AB) A) (5) (A (BvC)) AB (6) (A(BC))(A(BC) (7) (AB)((AB)A (8) (A(BA))B(A(AB)) (9) (ABC)(CAC) (10) BAGIAN - 2 : Buktikan absorptionlaus berikut ini dengan penyederhanaan! (1) A(AB)A (2) A(AB) A (3) (AB)(AB)B (4) (AB) (AB)B
BAGIAN - 3 : Hilangkan tanda dan dari ekspresi logika berikut ini dan sederhanakan lagi jika memungkinkan! (1) AB (2) (AB) ( BC) (3) (AB) ( B C)
BAGIAN – 4 :
42 Buktikan ekuivalensi dua ekspresi berikut dengan penyederhanaan! (1) (A . B) (B.C) = B (AvC) (2) ((AB)vA) = 1 (3) (Av(CD)) = (AC) v (AD) (4) A (AB) = AB (5) (AB) = AB (6) (AB) (AB) = A (7) AB = ((AB) (BA)) (8) AB = (AvB) (BvA) (9) (Av(BvC)) = (AB) v (AC) (10) (AC) (BD) = (AB) (AD) v (BC) (CD)
43 BAB VII STRATEGI PEMBALIKAN Sebelum membahas strategi pembalikan akan dibahas dahulu tentang konsistensi ekspersiekspersi logika yang berupa pernyataan. 7.1. KONSISTENSI Table kebenaran memang sangat bermanfaat untuk membuktikan validasi ekspresi logika. Tetapi masalahnya table kebenaran memerlukan tabel yang sangat besar untuk menyelesaikan ekspresi logika yang memiliki banyak variasi proposisional. Kelemahan lain nya terletak pada logika proposisional, yang tidak bias menangani kerumitan bahasa
yang dipergunakan sehari-hari walaupun untuk yang sederhana sudah cukup. Bahasa
yang cukup rumit akan di tangani oleh logika preduktif. Contoh 7-1 Rani anak pintar jika rajin belajar.orang tua rani senang jika rani pintar. Rani juara kelas. Orang tua rani senang. Pernyataan di atas disebut konsistensi satu dengan lainnya. Jika semuanya bernilai benar. Variable : 1. A→B 2. B→¬C 3. A ( A → B ) ^ ( B → ¬C ) ^ A ^ C A
B
C
A→B
¬C
B→¬C
T
T
T
T
F
F
F
T
T
F
T
T
T
F
44
T
F
T
F
F
T
F
T
F
F
F
T
T
F
F
T
T
T
F
F
F
F
T
F
T
T
T
F
F
F
T
T
F
T
F
F
F
F
T
T
T
F
Perhatikan tidak ada satu ekspersi logika (A → B) (B→C) ,A. dan C yang mempunyai nilai T pada deretan yang sama sehingga hasilnya juga dipastikan F jadi kumpulan pernyataan tersebut tidak konsisten Contoh 7-2: Jika Kampus mengadakan acara, maka mahasiswa akan hadir jika banyak pengisi acara yang menghibur. Sehingga varibelnya terdiri dari : 1. Jika Kampus mengadakan acara maka banyak pengisi acara yang mengibur 2. Dengan demikian, jika kampus mengadakan acara maka akan banyak mahasiswa yang hadir. Validasi argumen diatas harus dibuktikan dengan tbale kebenaran. Yang akan membuktukan premis bernilai T dengan kesimpulan bernilai T, akan menghasilkan nilai T. Langkah 1: A = Kampus mengadakan acara B = Banyak pengisi acara C = Banyak mahasiswa yang akan dating
45
Langkah 2: 1. A → (¬C → B) 2. A → ¬C 3. A → B Langkah 3: Menyusun ekspresi logika menjadi satu kesatuan. Untuk argumen, cara menulis ekprsi logika ada beberapa : 1. ((A → (¬C → B)) ˄ (A → ¬C)) → ( A → B) 2. { A → (¬C → B), A → ¬C} |= A → B Untuk membuat table kebenaran sebaiknya pakailah penulisan ke 1 agar penyusunan kedalam table kebenaran lebih mudah. 7.2. Operasi Strategi Pembalikan Setiap pembalikan dilakukan dengan cara menyalahkan kesimpulan argumen,yakni: 1. Menegasikan Kesimpulan 2. Memberi nilai F
Seperti yang dibahas sebelum nya argumen disebuy valid jika premis-premis benar dan kesimpilan benar, agar aegumen juga benar. Dengan strategi pembalikan muncul perlawanan (opposite) dari kesimpulan yang tidak cocok atau tidak konsisten(inconsistency) dengan premispremis jadi premis nya bernilai T sedangkan kesimpulannay bernilai F. Dengan stretegi pembalikan contoh argumen tentang masalh harga gula di atas kesimpulan akan dinegasikan dan akan ditulis seperti berikut : 3. ((A → (¬C → B)) ˄ (A → ¬C) ˄ → ¬( A → B)
46
Table kebenaran : A
B
C
¬C
¬C→B
A→(¬C
→ (A→¬C) (A→B)
¬(A→B) E
B) F
F
F
T
F
T
T
T
F
F
F
F
T
F
T
T
T
T
F
F
F
T
F
T
T
T
T
T
F
F
F
T
T
F
T
T
T
T
F
F
T
F
F
T
F
F
T
F
T
F
T
F
T
F
T
T
F
F
T
F
T
T
F
T
T
T
T
T
F
F
T
T
T
F
T
T
F
T
F
F
Tabel 7-1
E : ((A → (¬C → B)) ˄ (A → ¬C) ˄ → ¬( A → B Ternyata hasilnya negasi dari kesimpulan tidak konsisten dengan premis-premis atau hasilnya F disini terjadi kemungkinan bahwa negasi dari kesmipulan bernilai T bersamasama dengan premis-premis maka karena hasilnya F namun dengan adanya strategi pembalikan menyebabkan hasilnya bernilai T dan tentu saja ini berarti argumen di atas valid. Sebenarnyaa jiak hanya mencari premis-premis yang bernilai T bersama kesimpulan yang juga bernilai T untuk mendapatkan hasil berniali T tidak perlukan seluruh table kebenaran cukup dnegan menemukan pasangan dari variable proposional yang akan menghasilkan nilai T bersma kesimpulan maka pasti argumen tersebut valid teknik ini disebut model.
7.3. MODEL Teknik model berusaha mencari premis-premis dan kesimpulan dan kesimpulan berupa ekspresi logika yang bernilai T yang hasilnya tentu T diperoleh dari berbagai kemungkinan, maka digunakan strategi pembalikan dengan memberi nilai F pada kesmipulan padahal
47 premis-premis harus tetap bernilai T . Hal ini menyebabkan hasilnya juga pasti F. Lihat contoh tentang harga gula di atas dengan penulisan berikut : {A → (¬C → B), A → ¬C} |= A → B Dan ditulis seperti berikut : (A → (¬C → B)) ˄ (A → ¬C) ˄ → ¬( A → B) Maka akan diberi nilai seperti berikut : 1. (A → (¬C → B))= T 2.
(A → ¬C)
3. ( A → B)
(premis 1)
=T
(premis 2)
=F
(kesimpulan)
Setiap premis dan kesimpulan serta variable proposional pasti mempunyai nilai dan tulis : V (A → ¬C)
= T dan seterusnya V berarti “Value of atau nilai dari”
Adapun aturan-aturan yang dipakai dalm penarikan kesimpulan yaitu sebagai berikut:
Modus Ponen
Modus Tollen Simplifikasi Konjungsi
Hypotetical Syllogism
p⇒q P ∴q p⇒q ~q ∴~p p∧q ∴p P Q ∴p∧q p ⇒q q⇒r ∴p ⇒ r
Disjucktive Syllogism
Constructive Dilemma
Destructive Dilemma
Addition (Add)
Table 7-2
p∨q ~p ∴q p⇒q r⇒s p∨r ∴q ∨ s p⇒q r⇒s ~q ∨ ~s ∴~p ∨ ~r p ∴p ∨ q
48
Berikut ini contoh dari aturan penarikan kesimpulan diatas: Contoh 7-1: 1. Buktikan bahwa argument berikut valid ! Jika lampu akan padam, suasana akan gelap. Jika suasana gelap, aktivitas akan terganggu. Lampu padam. Jadi, aktivitas tertunda. Misal: p : lampu padam q : aktivitas terganggu r : aktivitas tertunda Simbol untuk argument di atas adalah sebagai berikut: p⇒q q⇒r p ∴r Proses pembuktian validitas argument di atas adalah sebagai berikut: 1. 2. 3. 4. 5.
p⇒q q⇒ p q r
Pr r Pr Pr / ∴r 1,3 MP 2,4 MP
49
BAB VIII TABLO SEMANTIK 8.1. Tablo Semantik Tablo semantik penggunaannya berbasis pada strategi pembalikan. Strategi pembaalikan pada tablo semantik dilakukan dengan cara memberi negasi pada kesimpulan dan memeriksa hasil yang diperoleh. Sama seperti cara strategi pembalikan, yang menjadi patokan adalah apakah kesimpulan yang bernilai F dapat diperoleh dari premis-premis yang bernilai T. Jika tidak bisa, maka argumen disebut valid. Maka bagaimanapun premis-premis yang bernilai T haruslah menghasilkan kesimpulan yang bernilai T juga. Tablo semantik sebenarnya merupakan bentukbentuk proposisi yang dibangun berdasarkan aturan-aturan tertentu, yang biasanya berbentuk pohon terbalik dengan cabang-cabang dan ranting-ranting yang relevan. 8.2. Aturan – Aturan Tablo Semantik Aturan-aturan tablo semantik adalah sebagai berikut: Aturan (1) : A ^ B A^B A B Jika tablo berisi A^B , maka tablo dapat dikembangkan menjadi tablo baru dengan menambahkan A dan B pada tablo A ^ B. Bentuknya seperti berikut: Aturan (2) : A ˅ B Jika tablo berisi A v B maka dapat dikembangkan menjadi bentuk tablo baru dengan menambahkan dua cabang baru. Satu berisi A dan satunya adalah B seperti berikut:
50 A VB
A
B
Berikut ini aturan-aturan lain dalam bentuk diagram. Penjelasan tentang setiap aturan dan alasannya akan dijelaskan nanti. Aturan (3): A → B
A→B
¬A
B
Aturan (4): A ↔B
A↔B
¬A ^ ¬ B
A^ B
Aturan(5): ¬ ¬ A ¬¬A A
Aturan(6): ¬ (A ^B) ¬ (A ^ B)
¬A
¬B
51
Aturan (7) : ¬ (A v B )
¬ (A v B) ¬A ¬B Aturan (8) : ¬ (A → B)
¬ (A → B) A ¬B
Aturan (9) : ¬ (A ↔ B) ¬ (A ↔ B)
A^¬ B
¬ A^B
Aturan(10): Jika ada bentuk logika A dan negasinya (¬A) yang berada pada satu deretan cabang dari tablo, maka terjadi ketidakkonsistenan pada cabang tersebut tidak bisa dikembangkan lagi. Hal ini disebabkan karena A dan ¬A tidak mungkin benar secara bersama-sama pada satu saat tertentu. Sehingga dapat disimpulkan bahwa jika semua cabang dari tablo tertutup, maka ekpresi
52 logika tersebut disebut bersama-sama tidak konsisten atau mereka tidak bisa bernilai benar bersama-sama.
8.3. Tablo Semantik dalam Himpunan Ekspresi Logika Contoh 8-1 : Apakah ekpresi logika ini konsisten bersama sama: ¬ (A → B) dan ¬ A v B
Dibuat tablo semantik seperti berikut: ¬ (A → B)
(1)
¬ Av B
(2)
¬A
B
│
│
A
A
¬B
¬B
Tutup
Tutup
Aturan (2) pada (2)
Aturan (8) pada (1)
Perhatikan bahwa dua cabang dari tablo di atas tertutup, karena cabang sebelah kiri berisi A dan ¬ A dan cabang sebelah kanan berisi B dan ¬ B. Jadi, kesimpulannya adalah tidak konsisten bersama-sama.
53 8.3. Pembenaran Aturan Tablo Aturan tablo dapat dipandang sebagai aturan dari sistem deduktif atau sistem pembuktian, yang tak perlu ditafsirkan pada konteks lainnya. Aturan tablo sangat sintaksis, seperti memainkan suatu permainan, misalnya catur. Tinggal menuruti peraturan yang ada, misalnya menjalankan plon, menteri dan sebagainya. Maka jalanlah permainan catur tersebut. Namun pada tablo tak ada penafsiran lebih dahulu bahwa premis-premis benar dengan kesimpulan saalah seperti pada strategi pembalikan pada model. Tablo hanya menegasi kesimpulannya saja tanpa mempedulikan premis-premis. Meskipun demikian, aturan tablo sangat beralasan dan realistis, karena sebenarnya ia berbasis pada aturan hukum logika. Sekarang perhatikan satu demi satu aturan tersebut: Aturan (1) : A ^ B A^B A B Aturan ini menunjukan bahwa jika (A^b) adalaah benar, maka A dan B juga bernilai benar. Maka cabang tablo untuk ekpresi ini juga benar bersama-sama. Aturan (2) : AvB AvB
A
B
Aturan ini menunjukan bahwa jika (Av B) adalah benar, maka dapat A benar atau B juga benar. Maka satu cabang tablo harus menunjukan hal ini, atau ada konsistensi disini.
54 Aturan (3): A → B A→B
¬A
B
Dari hukum logika sudah diketahui (A→B) ≡ ¬ A v B. Maka dapat diaplikasikan sama seperti hukum nomor (2). 8.4. Tablo Semantik pada Argumen Tablo semantik juga dapat diimplementasikan pada pembuktian viliditas suatu argumen. Lihat contoh berikut: Contoh 8-2: Perhatikan argumen berikut : Jika Sandi menyontek saat ujian, maka guru akan datang jika pengawas tidak lalai. Jika Sandi menyontek saat ujian, maka pengawas tidak lalai. Dengan demikian, jika Sandi menyontek, maka guru akan datang. Apakah argumen diatas valid, atau apkah kesimpulan (pernyataan 3) secara logis mengikuti premis-premisnya . (pernyataan 1 dan 2)? Sekali lagi anda dapat menggunakan strategi pembalikan dengan cara menegasi kesimpulan untuk menemukan bahwa kesimpulannya tidak konsisten dengan premis-premis. Tablo semantik memakai teknik strategi pembalikan dengan menegasi pembalikan. Lihat tahap-tahap pembuktian berikut ini: Langkah 1 Membuat variabel proposisional seperti berikut: A = Sandi mencontek saat ujian B = Guru akan datang
55 C = Pengawas tidak lalai Langkah 2 Menyusunnya menjadi ekspresi logika : (1) A → ( ¬C → B )
(premis)
(2) A → ¬C
(premis)
Jadi, (3) A → B
(kesimpulan)
Jika ditulis, akan menjadi seperti berikut:
{ A→(¬C→B), A→¬C } │= A→B
Langkah 3 Menyusunnya menjadi deretan, lalu dibuat tablo dengan menegasi kesimpulan menjadi ¬(A → B). Maka penulisan di atas akan menjadi:
(A→(¬C→B)) ^ (A→¬C ) ^ ¬(A→B)
Berikutnya menyusunnya menjadi urutan seperti berikut: (1)
(A→(¬C→B)
(2)
A→¬C
(3)
¬(A→B)
Langkah 4 Buatlah tablonya sepeeti berikut (jangan lupa ikutilah heuristik pembuatan tablo untuk mengefisienkan pencabangan tablo).
56 (1)
A→(¬C→B)
(2)
A→¬C
(3)
¬(A→B) │ A
(4)
Aturan (8) pada baris (3)
¬B ¬A
(5) (6)
¬C
Aturan (3) pada baris (2)
Tutup ¬A
¬C→B
Aturan (3) pada baris (1)
Tutup
(7)
¬¬C
B
Aturan (3) pada baris (6)
Tutup │ (8)
C
Aturan (5) pada baris (7)
Tutup Perhatikan bahwa seluruh tablo ternyata tertutup, dan hal ini berarti terjadi ketidakkonsistenan pada seluruh argumen. Karena ada strategi pembalikan dengan memberi negasi pada kesimpulan. Maka dapat disimpulkan bahwa premis-premis tersebut benar dan kesimpulan tidak benar (karena negasi). Dengan demikian, sebenarnya kesimpulannya adalah benar dan argumen tersebut valid. Contoh 8-3 Buktikan validitas argumen berikut ini: Ade dan Indah pergi kepesta. Jika Indah pergi ke pesta, maka Tiwi pergi ke pesta, jika tidak Wiega pergi ke pesta. Wiega pergi ke pesta jika Ade tidak pergi ke pesta. Dengan demikian, Tiwi pergi ke pesta.
57 Langkah 1 Membuat variabel proposisional seperti berikut: A = Ade pergi ke pesta B = Indah pergi ke pesta C = Tiwi pergi ke pesta D = Wiega pergi ke pesta Langkah 2 Menyusunnya menjadi ekspresi logika: (1) AvB
(premis)
(2) B →(¬D→C)
(premis)
(3) ¬A→D
(premis)
Jadi, (4) ¬C
(kesimpulan)
Jika ditulis, akan menjadi seperti berikut: { AvB, B→(¬D→C), ¬A →C } │= C
Langkah 3 Menyusunnya menjadi deretan dan dibuat tablo dengan menegasi kesimpulan menjadi ¬C. Maka penulisan diatas menjadi :
( AvB ) ^ (B→(¬D→C)) ^ (¬A →C) ^ ¬C
Lalu disusun menjadi urutan seperti berikut ; (1)
AvB
58 B →(¬D→C)
(2)
¬A→C
(3) (4)
¬C
Langkah 4 Buatlah tablonya seperti berikut (jangan lupa ikutilah heuristik pembuatan tablo untuk mengefisienkan pencabangan tablo). (1)
AvB
(2)
B →(¬D→C)
(3)
¬A→C
(4)
¬C
(5)
A
(6)
¬ ¬A
B C
│ (7) (8)
C
Aturan (3) pada (3)
│
A ¬B
¬ ¬A
Aturan (2) pada (1)
A ¬B→C
Aturan (3) pada (2)
Cabang tablo ini pasti tidak tertutup Karena cabang tidak tertutup sehingga dapat dikatakan bahwa argument bernilai valid, karena cabang yang terbuka membuktikan bahwa terjadi kekonsistenan antar premis.
59 BAB IX BENTUK NORMAL Bentuk normal (normal form) adalah bentuk standar untuk ekspresi logika. Bentuk normal mempunyai dua jenis, yaitu bentuk normal konjungtif dan bentuk normal disjungtif. Bentuk normal sangat penting difahami karena kebanyakan aplikasi logika, misalnya merancang rangkaian elektronika atau sirkuit menggunakan bentuk normal, khususnya bentuk normal disjungtif. Bentuk normal disebut juga bentuk kanonikal (canonical form). Bentuk normal hanya berisi perangkai ~, ^ , dan V, dengan proposisi dasar yang dikomposisikan dalam bentuk rumus atomik atau atom-atom. Literal adalah atom dan atau negasi dari atom 9.1. Bentuk Normal Konjungtif Definisi: suatu ekspresi logika (wff) berbentuk normal konjungtif (CNF) bila ia merupakan konjungsi dari disjungsi literal- literal. Bentuknya seperti berikut: (a1 ˅ a2 ) ^ (a3 ˅ a4 ) … ^ (an ˅ an+1 ) Bentuk CNF pada nomor (1), (2), (3), dan (4) di atas tetap dapat disebut bentuk normal konjungtif. Untuk nomor (4) diterima sebagai default. 9.2. Bentuk Normal Disjungtif Suatu ekspresi logika (wff) berbentuk bentuk normal disjungtif (DNF) bila ia merupakan disjungsi dari konjungsi literal- literal. Bentuknya seperti berikut: (a1 ˄ a2 ) ˅ (a3 ˄ a4 ) … ˅ (an ˄ an+1 ) Bentuk DNF pada nomor (1), (2), (3), dan (4) di atas tetap dapat disebut bentuk normal disjungtif. Untuk nomor (4) diterima sebagai default. Bentuk normal konjungtif (CNF) dengan empat klausa, yakni (¬A v B),(¬B v C),A dan ¬C, langkah pertama yang dilakukan adalah me-resolved (¬A v B) dengan (¬B v C), menjadi (¬A v C). selanjutnya, (¬A v C) di-resolved dengan A menjadi C, dan terakhir C di-resolved dengan ¬C menghasilkan ┴.
60 Pada saat mendapatkan klausa kosong dapat dinyatakan bahwa klausa-klausa yang ada di anggap tidak kompatibel satu dengan lainnya. Dengan kata lain, negasi dari kesimpulan tidak konsisten dengan premis-premis. Argumen justru dinyatakan valid karena pemakaian negasi kesimpulan berarti menggunakan strategi pembalikan.
A
B
C
M
͠𝑀
~A
~C
~N
O
F F F F T T T T
F F T T F F T T
F T F T F T F T
F F F F F F T T
T T T T T T F F
T T T T F F F F
T F T F T F T F
T T T T T F T F
T T T T T F F T
Tabel 9-1.
SKEMA: M=A^B N=A~v~C O=M↔N Dari tabel kebenaran di atas, hanya mengambil dari ~(A ^ B) ↔ (~A V C) yang bernilai T, yakni ada 6 (lihat nomor urut), kemudian jadikan DNF sesuai urutan nomor: (~A ^ ~B ^ ~C) V (~A ^ ~B ^C) V (~A ^ B ^ ~C) V (~A ^ B ^ C) V (A ^ ~B ^ ~C) V (A ^ B ^C) Bentuk normal di atas disebut full disjunctive normal form (FDNF. Untuk CNF sama saja, yakni mengambil nilai F dari tabel kebenaran dan membuatnya menjadi full conjunctive normal form (FCNF), dengan catatan nilai variabel-variabel proposisionalnya terbalik dari pasangan pada tabel kebenaran. T menjadi F dan F menjadi T.
61 CNF disusun sebagai berikut: (~A V B V ~C) ^ (~A V ~B V C) Teknik di atas pada DNF sebenarnya menggunakan pasangan variabel proposisional yang berada di tabel kebenaran dan yang memiliki nilai T, yang disebut minterm. Minterm adalah konjungsi dari literal- literal dengan variabel yang hanya dinyatakan satu kali. Contoh Misal ada 3 variabel proposisional A, B, dan C. berikut adalah contoh minterm (A ^ B ^ C); (~A ^ ~B ^~C); (~A ^ B ^ C) Contoh bukan minterm (A^A^C); (~A^~B^B); (~A^C); B Klausa adalah disjungsi dari literal-literal. Setiap klausa dapat berisi sekurang-kurangnya satu literal, misalnya A dan ~A, dan setiap literal disebut klausa unit (unit clause) Contoh klausa-klausa unit 1. (p2^p5^~p3) 2. (~p1 ^ p3) 3. ~p2 4. p10
Pembahasan tentang klausa dan CNF memegang peranan penting untuk melakukan deduksi resolusi (resolution deduction)
62 Bentuk Normal Konjungtif dan Complementation Sebelum membahas Complementation, sebaiknya kita mengenal dulu konsep dualitas. Dualitas adalah kembaran suatu ekspresi. Jika memiliki V perangkai akan diganti ^, dan jika bernilai T akan diganti bernilai F, demikian sebaliknya. Contoh dualitas A V~A = T hukum tautologi A ^~A = F hukum kontradiksi
Konsep dualitas berhubungan erat dengan complementation dan dengan konsep ini akan dibuat CNF dari tabel kebenaran. Setiap literal mempunyai complement. Jika ada literal A maka complement-nya ~A, jika literalnya ~B maka complement-nya B. Complementation adalah penegasian suatu ekspresi dengan memakai complement- nya. Contoh Negasikan P = (A^B)V ~C dengan complementation. Penyelesaian: Langkah 1: Cari dualitas dari P, yaitu: (A^B)V ~C Hanya mengganti perangkai, tetapi literalnya tidak diubah. Langkah 2: Lakukan complementation dengan mencari complement-nya. Caranya dengan menghapus semua literal dan diganti dengan complement- nya dan menghasilkan (~A V ~B)^C.
63 Jika masih ragu dengan hasilnya, maka pembuktiannya bisa juga dilakukan dengan cara berikut: ~P = ~((A^B)V~C) (~(A^B)^~~C) ((~AV~B)^C) (~AV~B)^C Ternyata sama. Complementation dapat digunakan untuk mencari CNF dari suatu ekspresi atau fungsi R. maka buatlah dulu DNF dari ~R, jika hasil DNF adalah P, maka P = ~R dan complement dari P adalah negasinya yang pasti ekuivalen secara logis dengan R. A
B
C
R
F
F
F
T
F
F
T
F
F
T
F
T
F
T
T
T
T
F
F
F
T
F
T
F
T
T
F
T
T
T
T
T
64 HIMPUNAN KLAUSA
Untuk menyatakan CNF sebagai himpunan klausa, sebagai contoh ekspresi di depan, yakni: (¬A v B) Λ (¬B v C) Λ A Λ ¬C Dapat dinyatakan dalam bentuk himpunan klausa sehinnga dapat ditulis seperti berikut: {(¬A v B), (¬B v C) , A , ¬C} Dengan menghilangkan perangkai Λ. Tetapi jika mengingat sifat komutatif, yakni (AΛB) ≡ (BΛA), maka himpunan klausa tersebut juga dapat dipindah-pindahkan untuk memeprmudah pembuatan pohon terbalik dengan resolvent harus ada pasangan literalnya, yang masing-masing berada di satu klausa. Sebagai contoh ekspresi logika di atas dapat ditulis: {(¬A v B) , A, (¬B v C) , ¬C}
Klausa (¬A˅B) dan (¬B˅C) dapat di-resolved menjadi sati “resolvent”, yakni menjadi kalusa (¬A ˅ C). Klausa (¬A ˅ C) dengan A di resolved menjadi C Klausa C dengan ¬C akan menjadi apa?
Membatalkan C dengan ¬C akan menghasilkan klausa kosong, dan bagaimana menyatakan klausa kosong?. Sebaiknya memakai ┴ saja, sebab jika dua buah klausa di resolved, hasilnya harus benar. Jadi, jika C di-resolved dengan ¬C, masing-maing harus bernilai benar, maka hasil resolvent-nya harus benar, padahal C dan ¬C tidak mungkin benar bersama-sama. Jadi gunakan saja ekspresi yang nilainya mungkin benar, yakni ┴.
65 Cara lain adalah melihat bahwa klausa berbentuk disjung, dan salah satu disjung harus bernilai benar (¬A v B) A (¬B v C)¬C B C ┴ agar klausa bernilai banar. Tetapi jika tidak ada disjung untuk menunjukkan klausa benar, maka klausa pasti salah. Oleh karena itu, klausa kosong tidak akan memenuhi persyaratan tersebut, ia pasti selalu salah atau falsum.
Klausa C di-resolved dengan ¬C menjadi ┴. Oleh karena itu, penggunaan ┴ memenuhi persyaratan (A→B) Λ (B→C) Λ ¬ (A→C) ╞ ┴ di atas.
Untuk mempermudah penjelasan di atas, gunakan bentuk pohon terbalik (inverted tree) seperti berikut, tetapi jangan lupa untuk tetap menggunakan bentuk CNF.
(¬A v B)
(¬A v C)
(¬B v C)
A
¬C
66 Contoh Buktikan: {(p1→p2),(¬(p2→p3)→¬p1)} ╞ (p1→p3)
Pembuktian:
Langkah 1: Ubahlah menjadi bentuk klausa (CNF) p1→p2
A→B
≡¬p1 v p2 ¬(p2→p3)→¬p1 ≡¬¬(¬p2 v p3) v ¬p1
A→B
≡(¬p2 v p3) v ¬p1
Law of double negation
≡¬p2 v p3 v ¬p1
Hapus tanda kurung
p1→p3 ≡¬p1 v p3
A→B
67
BAB X PEMBUKTIAN ARGUMEN DENGAN RESOLUSI Pembuktian
ekspresi-ekspresi
logika
verupa
validitas
argument-argumen
,misalnya
dengan memakai table kebenaran, penyederhanaan dengan hukum-hukum logika, sampai metode tablo semantic, bersifat mekanis dan langsung kelihatan hasilnya. Tentunya sangat penting untuk menemukan metode lain yang lebih mekanis dan mudah digunakan di dalam logika. Metode tersebut disebut resolusi (resolution). Metode resolusi dikembangkan oleh John Alan Robinson sekitar tahun 1960-an dan terus di selidiki secara intensif dan diimplementasikan ke berbagai masalah logika. Prinsip resolusi juga mudah di pakai di computer, misalnya pada deduksi basis data. Masalahnya untuk memahami resolusi harus dimengerti dahulu apa yang disebut resolving argument . 10.1. Resolving Argument Sebelumnya telah dikemukakan bahwa logika berhubungan dengan deduksi atau penarikan kesimpulan, masalah pembuktian dan validitas argument, perhatikan contoh argumen berikut: Contoh 10.1 Jika durian ini manis,maka durian ini enak dimakan. Jika durian ini enak dimakan, maka saya akan memakannya. Dengan demikian , jika durian ini manis, maka saya akan memakannya. Argumen tersebut pasti valid. Pola argument di atas adalah Silogisme Hipotesis. Jika masih ragu-ragu, validitasnya dapat dibuktikan dengan langkah-langkah berikut: Pembuktian: Langkah 1: Tentukan variabel proposisionalnya. A= Durian ini manis. B= Durian ini enak dimakan.
68 C= Saya akan memakannya. Langkah 2: Buat bentuk logika masing masing pernyataan. (1) A→B (2) B→C (3). A→C Langkah 3: Susun dalam bentuk ekspresi logika. ((A→B)) Λ (B→C)) →(A→C) Sekarang bisa dilihat dengan jelas bahwa ekspresi logika dari argumen tersebut adalah Silogisme hipotesis, dan sudah dibuktikan tautologi pada bab-bab di depan. Selanjutnya dapat ditulis seperti berikut: {(A→B),(B→C)} ╞ (A→C) Jadi, jika premis-premis, yakni (A→B) dan (B→C) bernilai benar, maka kesimpulan (A→C) juga pasti bernilai benar, atau (A→C) adalah konsekuensi logis dari (A→B) dan (B→C) Dengan menggunakan strategi pembalikan, dapat diperlihatkan bahwa menegasi kesimpulan yakni
¬
(A→C) adalah tidak konsisten dengan premis-premis (A→B) dan (B→C). Untuk
membuktikannya digunakan table kebenaran dengan penulisan sebagai berikut: (A→B) Λ (B→C) → ¬(A→C) Dan sudah dapat dipastikan bahwa table kebenaran untuk menunjukkan nilai kebenaran seluruhnya salah atau kontradiksi yang berarti argument valid. Di sini,
masih dapat digunakan sudut pandang semantik (atau Theoritic model) dan
memperlihatkan ketidakkompatibelannya dengan penulisan berikut: (A→B) Λ (B→C) Λ ¬ (A→C) ╞ ┴
┴
adalah Falsum , yakni konstanta proposisional yang selalu bernilai salah. Artinya jika nilai
kebenaran dari premis-premis dan negasi kesimpulan-kesimpulan bernilai Salah (falsum), maka argumen pasti valid.
69
Sekarang akan dibahas teknik resolving argument dengan memakai cara penulisan terakhir ,yakni dengan falsum. Misalkan ekspresi logika (A→B) Λ (B→C) Λ
¬
(A→C) di ubah menjadi CNF, maka akan
diperoleh hasil berikut ini> (A→B) Λ (B→C) Λ ¬ (A→C) ≡ (¬A v B) Λ (¬B v C) Λ ¬ (¬A Λ C)
A→B
≡ (¬A v B) Λ (¬B v C) Λ (¬ ¬A Λ ¬C)
De Morgan’s Law
≡ (¬A v B) Λ (¬B v C) Λ (A Λ ¬C)
Law of Double Negation
≡ (¬A v B) Λ (¬B v C) Λ A Λ ¬C
Asosiatif
Jadi bentuk CNF yang diperoleh adalah: (¬A v B) Λ (¬B v C) Λ A Λ ¬C Sekarang perhatikan dengan baik pasangan klausa (¬A v B) dan (¬B v C), dan perhatikan bahwa klausa pertama mempunyai B dan klausa kedua memiliki pasangannya yakni ¬B. sekarang perhatikan penjelasan berikut satu demi satu: 1. Jika v(B) ≡ T, maka v(¬B) ≡ F, maka nilai kebenaran klausa kedua tergantung dari v(C). 2. Jika v(B) ≡ F, maka klausa pertama nilai kebenarannya tergantung dari v(¬A). 3. Padahal hanya mungkin satu di antara v(B) dan v(¬B) yang bernilai benar. Misalnya, v(B) ≡ T dan v(¬B) ≡ F, atau v(B) ≡ F dan v(¬B) ≡ T. 4. Jadi jika v((¬A v B) Λ (¬B v C)) ≡ T,maka dengan memilih salah satu kemungkinan dari nomor (3), dipastikan v(¬A) ≡ T dan v(C) ≡ T. 5. Sekarang dapat beralasan jika v((¬A v B) Λ (¬B v C)) ≡ T, dengan v(¬A) ≡ T dan v(C) ≡ T, maka v(¬A v C) ≡ T. karena jika v(¬A v C) ≡ F, maka v((¬A v B) Λ (¬B v C)) tidak bisa bernilai benar. 6. Dengan kata lain, maka ((¬A v B) dan (¬B v C) dapat di reduksi atau di-resolved menjadi satu klausa (¬A v C) dengan menghilangkan ¬B dan B.
70 Prinsip resolusi didasarkan pada penjelasan di atas, yakni dua klausa yang masing-masing literal yang berpasangan, misal A dengan ¬A, maka literal yang berpasangan tersebut dapat di resolved. Klausa hasil proses resolve disebut resolvent clause. Sebelum memulai penjelasan resolusi lebih lanjut, perhatikan kelanjutan uraian di atas. 1. Klausa (¬A v B) dan (¬B v C) dapat di-resolved menjadi sati “resolvent”, yakni menjadi kalusa (¬A v C). 2. Klausa (¬A v C) dengan A di resolved menjadi C 3. Klausa C dengan ¬C akan menjadi apa? Membatalkan C dengan ¬C akan menghasilkan klausa kosong, dan bagaimana menyatakan klausa kosong?. Sebaiknya memakai
┴
saja, sebab jika dua buah klausa di resolved, hasilnya
harus benar. Jadi, jika C di-resolved dengan ¬C, masing-maing harus bernilai benar, maka hasil resolvent-nya harus benar, padahal C dan ¬C tidak mungkin benar bersama-sama. Jadi gunakan saja ekspresi yang nilainya mungkin benar, yakni
┴.
Cara lain adalah melihat bahwa klausa berbentuk disjung, dan salah satu disjung harus bernilai benar agar klausa bernilai banar. Tetapi jika tidak ada disjung untuk menunjukkan klausa benar, maka klausa pasti salah. Oleh karena itu, klausa kosong tidak akan memenuhi persyaratan tersebut, ia pasti selalu salah atau falsum. (1) Klausa C di-resolved dengan ¬C menjadi Oleh karena itu, penggunaan
┴
┴.
memenuhi persyaratan (A→B) Λ (B→C) Λ
¬
(A→C) ╞
┴
di
atas. Untuk mempermudah penjelasan di atas, gunakan bentuk pohon terbalik (inverted tree) seperti berikut, tetapi jangan lupa untuk tetap menggunakan bentuk CNF.
71 (¬A v B)
(¬B v C)
A
¬C
(¬A v C)
C
┴
Bentuk normal konjungtif (CNF) dengan empat klausa, yakni (¬A v B),(¬B v C),A dan ¬C, langkah pertama yang dilakukan adalah me-resolved (¬A v B) dengan (¬B v C), menjadi (¬A v C). selanjutnya, (¬A v C) di-resolved dengan A menjadi C, dan terakhir C di-resolved dengan ¬C menghasilkan
┴.
Pada saat mendapatkan klausa kosong dapat dinyatakan bahwa klausa-klausa yang ada di anggap tidak kompatibel satu dengan lainnya. Dengan kata lain, negasi dari kesimpulan tidak konsisten dengan premis-premis. Argumen justru dunyatakan valid karena pemakaian negasi kesimpulan berarti menggunakan strategi pembalikan. Keindahan metodeini tampak pada bentuk CNF dengan klausa-klausanya yang saling meresolvent jika saling memiliki literal yang komplementer untuk menemukan klausa kosong. Hasilnya memang sangat mekanis dan langsung tampak hasilnya.
10.2. Himpunan Klausa Untuk menyatakan CNF sebagai himpunan klausa, sebagai contoh ekspresi di depan, yakni: (¬A v B) Λ (¬B v C) Λ A Λ ¬C Dapat dinyatakan dalam bentuk himpunan klausa sehinnga dapat ditulis seperti berikut: {(¬A v B), (¬B v C) , A , ¬C}
72 Dengan menghilangkan perangkai Λ. Tetapi jika mengingat sifat komutatif, yakni (AΛB) ≡ (BΛA), maka himpunan klausa tersebut juga dapat dipindah-pindahkan untuk memeprmudah pembuatan pohon terbalik dengan resolvent harus ada pasangan literalnya, yang masing-masing berada di satu klausa. Sebagai contoh ekspresi logika di atas dapat ditulis: {(¬A v B) , A, (¬B v C) , ¬C} Maka gambar pohon terbaliknya sebagai berikut:
(¬A v B)
A
(¬B v C)
¬C
B
C
┴
10.3. Resolvent Sebelumnya sudah di jelaskan mengenai metode resolusi walaupun belum lengkap. Selanjutnya, perhatikan teknik resolusi berikut: Ada dua literal, misalnya p1 dan ¬p1 ,yang disebut pasangan literal yang saling melengkapi (complementary pair). Jika ada dua klausa yang masing-masing memiliki sati dari pasangan tersebut, maka klausa tersebut dapat di-resolved bersama agar menjadi satu klausa baru (resolvent clause), dan cara ini dinamakan resolvent. Sebagai contoh, klausa { p1 ,¬p2 , p3 } dengan { p2 , p3 ) dapat di-resolved menjadi { p1,p3 }.
73 Definisi: resolvent dua klausa C 1 dan C2 yang masing-masing klausa berisi salah satu dari literal berpasangan dan ¬ , maka dapat didefinisikan: res(C1 ,C2 ) = C1 - { } C1 -{¬ }. Pada definisi resolvent tersebut, operator “-“ adalah operator pembeda himpunan, yang hasilnya adalah himpunan yang berasal dari argument pertama dengan (sub) himpunan dari argument kedua yang dihilangkan. Sebagai contoh, resolvent dari {1,2,3,4}-{2} ada;ah {1,3,4}. Contoh 10.2 res({p1 ,¬p2 },{p2 ,¬p3 }) = {p1 ,¬p3 }
Contoh 10.3 res({p1 ,¬p2 ,p3 ,p4 },{p2 ,¬p3 }) = {p1 ,p3 ,¬p3 ,p4 } atau res({p1 ,¬p2 ,p3 ,p4 },{p2 ,¬p3 }) = {p1 ,p2 ,¬p3 ,p4 } Satu klausa yang berisi pasangan literal yang komplementer, misalnya p i dan ¬pi secara otomatis hasilnya pasti benar. Hal ini karena klausa tersebut menyatakan disjungsi (p₁ v ¬p₁) pasti benat karena semuanya pasti benar. Tentu saja klausa hasil resolvent pada contoh 11-3 adalah benart.
Perhatikan tabel kebenarannya:
A
¬A
A v ¬A
F
T
T
T
F
T
74 Pada Contoh 11-3 ada dua hasil yang bisa diperolah karena ada dua pasangan literal yang komplementer dari dua klausa sebelum di-resolved, yakni p2 dengan ¬p2 dan p3 dengan ¬p3 . Jika ada lebih dari satu cara me-resolved , maka setiap resolvent pasti memiliki pasangan literal yang komplenter
dan pasti juga benar. Hasilnya akan menjadi salah jika di-resolved ,misalnya
{p1 ,¬p2 } dengan {¬p1 ,p2 } menjadi ┴, dengan me-resolved pada keduanya yakni p1 dan p2 . dua klausa disebut bersama-sama kompatibel jika memenuhi nilai bahwa p 1 dan p2 keduanya benar.
TEOREMA (PRINSIP RESOLUSI) Resolvent dua klausa, C 1 dan C2 adalah konsekuenis logis dari C 1 Λ C2 yakni ditulis: C1 Λ C2 ╞ res (C1 ,C2 )
Pembuktian teorema: 1.
Misalkan:C1 ={p11 , p12 ,….p1m, },C2= {p21 ,p22 ,. . .p2n ,¬ } Maka res(C1 ,C2 ) = { p11 , p12 ,….p1m, p21,p22,. . .p2n }
2.
Perhatikan nilai kebenaran v dengan v(C 1 ) ≡ T dan v(C 2 ) ≡ T Jika v( ) ≡ F, maka v(p1i) ≡ T untuk beberapa p1i dengan v(C 2 ) ≡ T Maka v({ p11 , p12 ,….p1m, p21 ,p22 ,. . .p2n }) ≡ T. Jadi v(res(C 1 ,C2 )) ≡ T
3.
Jika v( ) ≡ T, maka v(¬ ) ≡ F, dan v(p1i) ≡ T untuk beberapa p₁ I dengan v(C2 ) ≡ T. Maka v({ p11 , p12 ,….p1m, p21 ,p22 ,. . .p2n }) ≡ T. Jadi v(res(C 1 ,C2 )) ≡ T.
4.
Jadi pada saat v( ) ≡ T, ataupun v( ) ≡ F, dapat disimpulkan jika v(C 1 ) ≡ V(C2 ) ≡ T, maka v(res(C 1 ,C2 )) ≡ T
5.
Kesimpulan C 1 Λ C2 ╞ res (C1 ,C2 )
Ide yang mendasari resolusi, dapat dicontohkan dengan membuktikan rumus Modus Ponens yang sudah sangat dikenal, yakni:
75 ((A→B) Λ A)→ B atau
{(A→B), A)} ╞ B ≡ {(¬A v B), A} ╞ B
Dan jika (A→B) dan A ditulis dalam bentuk klausa akan menjadi {¬A, B}, {A}. Selanjutnya , pohon terbaliknya dapat dibuat seperti berikut: {¬A, B}
{A}
B Sederhana sekali dan terbukti bahwa C 1 Λ C2 ╞ res (C1 ,C2 ).
10.4. Resolusi Berikut ini akan didemonstrasikan prinsip resolusi untuk mendeduksi, yang dengan istilah deduksi resolusi (resolution deduction): Definisi: deduksi resolusi klausa Cdari himpunan klausa S adalah sederetan klausa-klausa (C1 ,C2 ,……..Cn ) = C, yang setiap C i adalah anggota dari S atau resolvent dari dua klausa yang diperoleh dari S atau anggota awal dari deretan tersebut. Seperti telah dijelaskan di depan, dari prinsip resolusi pada teorema 10-1 di depan, jika S adalah benar pada setiap penilaian kebenaran dari v, maka v(C i) ≡ T untuk semua C i , dan tentu saja v(C) ≡ T. Contoh 10.4: Buktikan: (p1 v p2 v p3 ) Λ (¬p2 v p4 ) Λ (¬p1 v p4 ) Λ (¬p3 v p4 ) ╞ p4
76 Pembuktian: Langkah 1: Ubahlah CNF menjadi klausa dan urutkan seperti berikut: (1) { p1 v p2 v p3 } (2) {¬p2 v p4 } (3) {¬p1 v p4 } (4) {¬p3 v p4 } Langkah 2: Lakukan resolusi dengan urutan berikut (5) Dari (1) dan (2), diperoleh klausa {p 1 ,p3 ,p4 } (6) Dari (3) dan (5), diperoleh klausa {p 3 ,p4 } (7) Dari (1) dan (2), diperoleh klausa {p 4 } Jadi terbukti: (p1 v p2 v p3 ) Λ (¬p2 v p4 ) Λ (¬p1 v p4 ) Λ (¬p3 v p4 ) ╞ p4 Derivasi tersebut dapat lebih tampak dalam bentuk pohon resolusi (resolution tree), yang tanpak sperti berikut:
{ p1 v p 2 v p3 }
{¬p2 ,p4 } {p1 ,p4 } {p3 ,p4 }
{p1 ,p3 ,p4 }
{p3 ,p4 }
{p4 }
77 Contoh 10.5: Buktikan: {(p1 →p2 ),(¬(p2 →p3 )→¬p1 )} ╞ (p1 →p3 )
Pembuktian: Langkah 1: Ubahlah menjadi bentuk klausa (CNF) (1)
p1 →p2
A→B
≡¬p1 v p2 (2)
¬(p2 →p3 )→¬p1 ≡¬¬(¬p2 v p3 ) v ¬p1
A→B
≡(¬p2 v p3 ) v ¬p1
Law of double negation
≡¬p2 v p3 v ¬p1 (3)
Hapus tanda kurung
p1 →p3 ≡¬p1 v p3
A→B
Langkah 2: Selanjutnya akan berbentuk: {{¬p1 ,p2 },{¬p2 ,p3 ,¬p1 )} ╞ {¬p1 ,p3 } Langkah 3: Buatlah pohon resolusinya {¬p1 ,p2 }
{¬p2 ,p3 ,¬p1 )
{¬p1 ,p3 }
78
Sebagaimana biasa, cara lain untuk membuktikan Contoh 11-5 adalah dengan menegasi kesimpulan (strategi pembalikan ), yakni ¬(p 1 →p3 ) dan memperlihatkan bahwa ia tidak kompatibel (incompatible) dengan premis-premis, yakni (p1 →p2 ) dan (¬(p2 →p3 )→¬p1 ). Teknik resolusi untuk membuktikan validitas argument dilakukan dengan menegasi kesimpulan Contoh 10.6 : Buktikan: {(p1 →p2 ),(¬(p2 →p3 )→¬p1 )} ╞ (p1 →p3 ) Pembuktian: Langkah 1: (p1 →p2 ) (¬(p2 →p3 )→¬p1 )} ╞ (p1 →p3 ) Di ubah menjadi (p1 →p2 )(¬(p2 →p3 )→¬p1 )} (p1 →p3 ) ╞
┴
Langkah 2: Ubahlah menjadi klausa-klausa (CNF). Klausa-1 dan 2 sama dengan di atas, sedangkan klausa 3 sekarang menjadi: (3).
¬(p1 → p3 ) ≡¬(¬p1 v p3 )
A→B
≡(¬¬p1 Λ ¬p3 )
De Morgan’s Law
≡ (p1 Λ ¬p3 )
Law of Double Negation
Maka sekarang akan berbentuk: (¬p1 v p2 ) Λ (¬p2 v p2 v p1 ) Λ p1 Λ ¬p3 ╞
┴
79
Langkah 3: Buatlah pohon resolusinya seperti berikut:
{¬p1 ,p2 }
{¬p2 ,p3 ,¬p1 } {p1 }
{¬p3 },
{¬p1 ,p3 }
{p3 }
┴
Definisi: Deduksi resolusi
┴
dari
suatu himpunan klausa S disebut pembalikan resolusi
(resolution refutation) dari S Secara jelas dapat disebut kalau deduksi
┴
di peroleh dari himpunan klausa S menunjukkan
bahwa S tidak konsisten. Jika semua klausa S adalah benar, maka reduksi dari S seharusnya benar. Pada kasus ini
┴
klausa apa saja yang di
harus benar, padahal
┴
selalu bernilai saah.
Jadi, semua klausa pada himpunan S tidak bisa benar bersama-sama.
10.6. Contoh Validitas Argumen Berikut ini beberapa argument yang hendak dibuktikan validitasnya dengan deduksi resolusi. Perhatikan argument berikut ini:
80 Contoh 1.28 :
Jika Ratu mengadakan konser,maka penggemarnya akan dating jika harga tiket tidak mahal. Jika Ratu mengadakan konser, harga tiket tidak mahal. Dengan demikian , jika Ratu mengadakan konser, penggemarnya akan dating.
Langkah 1: Menentukan variabel-variabel proposisional dan membuat ekspresi logikanya. A = Ratu mengadakan konser. B = Penggemarnya akan dating C = Harga tiket mahal Maka akan menjadi (1)
A→(¬C→B)
(2)
A→¬C
(3). A→B Ekspresi logikanya adalah: (A→(¬C→B)) Λ (A→¬C)╞ A→B Pernyataan-pernyataan tersebut tentunya dapat dipandang sebagai ekspresi atomic, walaupun mempergunakan A dan B daripada menggunakan p1 dan p2 dan seterusnya. Langkah 2: Ubahlah ekspresi logika tersebut dengan strategi pembalikan yang menegasi kesimpulan untuk menghasilkan
.
(A(¬CB)) Λ (A¬C) Λ ¬( AB)
Langkah 3: Ubahlah menjadi klausa-klausa CNF seperti berikut:
81 (1).
(A(¬CB))
AB
(¬A v (¬¬C v B))
Law of Double Negation
(¬A v (C v B)) ((¬A v C v B) (2).
Hapus tanda kurung
(A¬C) ¬(A v ¬C)
(3)
AB
¬( AB) ¬(¬A v B)
AB
(¬¬A Λ ¬B)
De Morgan’s Law
(A Λ ¬B)
Law of Double Negation
Jadi sekarang bentuknya menjadi: (¬A v C v B) Λ ( ¬A v ¬C) Λ A Λ ¬B ╞ Langkah 4: Susunlah pohon resolusinya sepert berikut:
{ ¬A,C,B}
{¬A,¬C} {A}
{¬A,B}
{B}
{¬B}
82 Kesimpulan,
hasil yang diperoleh ternyata tidak konsisten, dan berarti argument valid.
Perhatikan argumen berikut ini Contoh 10.8:
Jika pejabat melakukan korupsi, maka rakyat tidak akan marah atau kejaksaan akan memerikasnya. Jika kejaksaan tidak akan memeriksanya, maka rakyat akan marah. Kejaksaan akan memeriksanya, Dengan demikian, pejabat tidak melakukan korupsi.
Pembuktian: Langkah 1: Menentukan variabel-variabel proposisional dan membuat ekspresi logikanya. (A) = Pejabat melakukan korupsi. (B) = Rakyat akan marah. (C) = Kejaksaan akan memeriksanya. Maka akan menjadi: (1)
A(¬B v C)
(2)
¬CB
(3)
C
(4) ¬A Ekspresi logikanya adalah:
(A(¬B v C) Λ (¬C B) Λ C ╞ ¬A
Langkah 2: Ubahlah ekspresi logika tersebut dengan strategi pembalikan yang menegasi kesimpulan untuk menghasilkan . (A(¬B v C) Λ (¬C B) Λ C Λ ¬¬A ╞ . Langkah 3: Ubahlah menjadi klausa-klausa CNF:
83 (1). (A(¬B v C)) (¬A v (¬B v C))
AB
(¬A v ¬B v C)
Hapus tanda kurung
(2) (¬CB) (¬¬C v B)
AB
(C v B)
Law of Double Negation
(3) C (4) ¬¬A A
Law of Double Negation
Selanjutnya , bentuknya menjadi seperti berikut: (¬A v ¬B v C) Λ (C v B) Λ C Λ A ╞ Langkah 4: Susunlah pohon resolusinya seperti berikut: { ¬A,¬B,C}
{C,B}
{A}
{C}
{¬A,C}
{C}
Jadi, tidak mungkin me-resolved C dengan C untuk menghasilkan klausa kosong sehingga argument dipastikan tidak valid.
84 Latihan Soal-Soal Soal 1. Manakah dari himpunan klausa-klausa berikut ini yang tidak konsisten atau tidak kompatibel? (1). {{p1 ,p2 ,p3 },{p1 ,¬p3 }, {¬p1 ,¬p2 }} (2)
{{¬p1 ,¬p2 ,p3 },{p1 ,¬p3 },{¬p1 ,p2 }}
(3)
{{p1 ,¬p2 ,p3 },{p1 ,p3 },{¬p1 ,p2 ,¬p3 }}
(4)
{{p1 ,¬p2 ,p3 ,¬p4 },{p1 ,¬p3 },{p1 ,p2 ,¬p4},{p4 }}
(5)
{{p1 ,¬p2 ,¬p3 ,¬p4 },{p1 ,¬p3 },{¬p1 ,p2 ,¬p4},{¬p1 ,p4}}
Soal 2 Buktikan bahwa argument-argumen berikut ini valid: (yang dicetak tebal adalah kesimpulannya). (1).
¬AB
(3). ¬A Λ (¬B v C)
¬A v C v D
¬B v C
(B Λ C)
¬C v (E Λ F)
¬C v (CA)
CD
(F Λ ¬D)¬E
¬C
D v ¬A
¬A
¬(¬D Λ A)
¬DB (4).
(2). AB
¬AB
(5). AB
(6). AB
¬A v C v D
BC
¬C v (D Λ A)
DC
(C Λ ¬D)¬E
CvD
¬DB
¬A v
CD (¬Bv¬D)Λ(¬Av¬B) ¬A v ¬C
85
(7).
E(F Λ ¬G)
(8). JK
(F v G) H
J v K v ¬L
E
¬K
H
(9). MN NN (MO)(NP)
¬L Λ ¬K
(MP)Q Q
(10).
(R¬S) Λ (T¬U)
A(B Λ C)
(V¬W) Λ (X¬Y)
A((DE) Λ (FG))
(TW) Λ (US)
(B Λ C) v ((¬AD) Λ (¬AF))
VvR
¬(B Λ C) Λ ¬(G Λ D)
¬T v ¬U
(12).
(11)
(¬H v I)(JK)
EvG
(13). (B v C)(D v E)
(¬L Λ ¬M) Λ (KN)
(D v E v F)(G v H)
(HL) Λ (LH)
(G v H)¬D
(¬L Λ ¬M) Λ ¬O
E¬D
JN
B
H
86 (14).
VW XY ZW XA WX ((VY) Λ (ZA)) Λ (V v Z)
YvA Soal 3 Buktikan ekspresi logika berikut ini valid:
(1).
P Λ (QR) Λ (PQ) Λ (S¬R) ¬S
(2).
S Λ (¬PQ) Λ (P¬S) Λ (QR) R
(3).
(P Λ S) Λ (PQ) Λ (QR) Λ (S¬T) (R Λ ¬T)
(4).
(¬S(P v Q)) Λ (S¬T) Λ T Λ (PR) Λ (¬R¬Q) R
87 BAB XI DEDUKSI ALAMI Sebelumnya kita telah membahas Table kebenaran, tablo semantik, dan resolusi untuk menentukan pada masalah konsistensi pernyataan-pernyataan dan validitas suatu argumen. Selain itu teknik-teknik tersebut digunakan untuk mengembangkan tujuan-tujuan sintaksis nilai benar atau salah. Selanjutnya kita akan membahas penanganan sintaksis tersebut dengan mempertimbangkan pembuktian dan deduksi atau pengambilan keputusan. Penurunan bentuk tersebut akan dilakukan dengan aturan-aturan deduksi. Aturan-aturan deduksi tidak berbeda dengan aturan sebuah permainan, misalnya catur : bagaimana bidak harus melangkah dan sebagainya. Jika aturan digunakan dengan baik, maka berjalanlah permainan tersebut. Begitu juga dengan deduksi. Aturan harus ditaati sesuai logika formal yang ada, dan kemudianberusaha menyimpulkan bahwa kesimpulan yang benar pasti berdasarkan premis-premis yang benar. Penekanan pada tujuan sintaksis sekali lagi berhubungan dengan nilai benar atau salah, sedangkan berkaitan dengan tujuan semantik berhubungan dengan kenyataan yang ada. Deduksi yang akan dibahas tersebut disebut deduksi alami ( natural deduktion ), karena dapat menunjukan cara-cara intuitif atau metode ‘ alami ‘ atau pemikiran yang paling mendekati pemikiran manusia. Metode ini dikembangkan oleh Gerhard Gentzen pada tahun 1930an. 11.1. Falsum Pada bab sebelumnya sudah diperkenalkan satu konstanta logika yang mempunyai arti penting. Yakni falsum dengan simbolnya ┴ .
Konstanta ini bernilai salah. Sama seperti 0 pada bab
sebelumnya tentang tautologi. Simbol ┴ dahulu digunakan untuk menyatakan “kebohongan”. Simbol ┴ dapat juga digunakan untuk menunjukan ‘ kemustahilan ‘, seperti A dan bukan A. Jika ingin digunakan ┴ untuk menyatakan operasi negasi, maka didefinisikan bahwa ¬A≡ A→ ┴
88 Perhatikan tabel Tabel kebenaran.
Tabel kebenaran tentang → (implikasi) sudah dibahas pada bab sebelumnya. Dari tabel kebenaran diatas dapat dilihat jika ( A → ┴ ) adalah benar maka A salah., dan salah jika A benar ( ingat bahwa ┴ selalu bernilai salah). Sekarang akan digunakan ¬A dan ( A → ┴) secara bergantian tergantung masalah yang dibahas, karena terbukti bahwa ¬A≡A → ┴. 11.2. Aturan-Aturan Deduksi Alami Aturan-aturan deduksi alamiah adalah sebagai berikut, dengan A,B,C mewakili variabel proposisional : Aturan ( 1 ) : ˄I ( ˄ - introduksi ) A
B A˄B 2
Aturan diatas mudah sekali dipengaruhi. Jika ada A dan B, maka dapat disimpulkan A˄B. Contoh : “ Ani kehausan”
dan “ Ani kelaparan”, maka kesimpulannya “ Ani kehausan dan
kelaparan “. Secara umum pada deduksi alami, formula yang ada diatas garis adalah yang telah diperoleh atau asumsi, sedangkan formula yang berada di dalam garis adalah yang diperoleh. Aturan (2) : ˄E (˄ - eliminasi ) A ˄ B A
89 Aturan (3) : ˄E (˄- eliminasi ) A ˄ B B Aturan 2 dan 3 dinamakan aturan ˄ - eliminasi atau disingkat ˄E. Kedua aturan tersebut menyatakan bahwa jika A˄B telah diperoleh,maka dapat disimpulkan A (atau B). Contoh : “Tini mahasiswi yang malas dan bodoh”. Maka dapat disimpulkan “ Tini mahasiswi yang bodoh” atau “Tini mahasiswi yang malas”. Aturan (4) : ˅ I ( ˅ - introduksi )
A
A
.
˅
B
Aturan (5) : : ˅ I ( ˅ - introduksi )
A
B
.
˅
B
Aturan 4 dan 5 tampak sedikit aneh. Contoh: dari pernyataan “ Ana mahasiswa yang pandai “ dapat disimpulkan bahwa “ Ana mahasiswa yang pandai dan sangat cantik “. Kesimpulan tersebut terasa aneh, bukan? Apa hubungannya dengan kecantikan Ana dengan kepandaiannya.? Tapi disini, dari A dapat diambil kesimpulan A atau B, dengan B adalah pernyataan apapun tanpa harus ada kaitannya dengan A. Aturan (6) :˅ E (˅ - eliminasi ) Ⱥ Ɓ ....... ....... A˅B C
C
90 C Aturan 6 menyatakan : jika C diperoleh dari A, dan C diperoleh sari B maka C diperoleh dari ( A ˅ B ). Jika A dan B berupa asumsi, maka keduanya dapat dihilangkan. Aturan tersebut sebenarnya menyatakan, jika suatu mengikuti kasus 1 dan hal yang sama mengikuti kasus 2, maka berarti sesuatu tersebut mengikuti kasus 1 dan 2. Aturan (7) : → I (→ - introduksi ) Ⱥ .... .... C A→C Penafsiran terhadap aturan 7 adalah jika C dapat diperoleh dari asumsi A,maka dapat membuang asumsi dan menyimpulkan bahwa ( A → C ). Contoh : pernyataan “ Toni lulus ujian “ berasal dari asumsi “ Toni belajar rajin. Jadi, pernyataan lengkapnya dapat dibuat : “ jika Toni belajar rajin, maka ia lulus ujian”. Disini tidak perlu didebatkan bahwa kelulusan Toni bisa saja disebabkan bukan karena Toni rajin belajar, tetapi mungkin ia menyontek dengan temannya, atau nasibnya sedang bagus, atau soal ujiannya kebetulan mudah,dan berbagai kemungkinan lainnya. Aturan (8) : → E (→ - eliminasi ) A
A → C C
Bentuk diatas tentunya tidak asing lagi. Jika A didapat, dan A implikasi C, maka C didapat.ingat modus ponens ( MP ).
91 Aturan (9) : ┴ ┴ C Aturan 9 menyatakan bahwa dari falsum, kesimpulan C berupa apapun dapat dibuat. Dengan kata lain, dari suatu kemustahilan atau kontradiksi, apapun dapat diperoleh. Aturan (10) :RAA (reductio Ad Absurdum ) ¬A ..... ..... ┴ A Aturan 10 memformalkan metode yang terkenal yaitu pembuktian menggunakan kontradiksi. Jika dikonsumsikan bahwa A adalah bukan kasus yang menyebabkan terjadinya kontradiksi. Maka dapat disimpulkan bahwa A adalah kasusnya. Dapat juga digunakan aturan 7 – definisi pelengkap yang berguna untuk aturan ini : A ..... ..... ┴ ¬A
¬A adalah ( A→ ┴) – untuk mendapatkan bentuk
92 Hal ini berdasarkan kenyataan berikut : Ⱥ
Asumsi
..... ..... ┴
Deduksi dari asumsi
A→┴
menggunakan → I
Tentunya sekali lagi bahwa ( A → ┴ ) ≡ ¬ A Aturan (11) : Id ( identitas ) A A Setiap formula dapat dideduksi dari dirinya sendiri. 11.3. Pembuktian Teorema Berikut akan ditunjukan bagaimana menggunakan aturan-aturan deduksi alami untuk membuat pembuktian teorema. Teorema adalah suatu bentuk ekspresi logika atau wff, yang diperoleh dari aturan deduksi alami yang berasal dari asumsi-asumsi tertentu. Misalnya sebuah kesimpulan C diperoleh dari sebuah himpunan asumsi { A1 , A2 ,..., An }, maka dapat dituliskan sebagai { A1 , A2 ,..., An } ˫ C. Jika himpunan asumsi tersebut kosong, atau tidak ada asumsi. Maka dapat ditulis sebagai ˫ C. ( lambang ˫ dinamakan turnstile ). Sekarang perhatikan teorema-teorema berikut ini yang pembuktiannya menggunakan aturan deduksi alami.
93 Teorema 11-1 {A˄B}B˄A Pembuktian
strategi
yang
umum
dimulai dengan
satu
atau
lebih
asumsi,
selanjutnya
menggunakan aturan-aturan deduksi alami untuk maju. Dalam kasus ini asumsi yang digunakan adalah ( A ˄ B ). A ˄B
A˄B
B
A B˄A
asumsi menggunakan ˄ E menggunakan ˄ I
Teorema 11 – 2 (A˄B)→(B˄A) Pembuktian : pembuktian mengikuti teorema 3.1, menghilangkan asumsi. A˄B
A˄B
B
A B˄A
A˄B → B˄A
asumsi menggunakan ˄E menggunakan ˄I menggunakan → I
7 Teorema 11 – 3 { B } A→ B
dengan tambahan satu langkah ikut
94 Pembuktian : Ⱥ
asumsi
B
asumsi
B
menggunakanId
A→B
→I ( selesai )
Heuristik Untuk Deduksi Alami Bentuk ( A → B )
Untuk membuktikan sebuah formula dalam bentuk ( A → B ), maka gunakan A sebagai asumsi, dengan maksud A akan dihilangkan dan kemudian gunakan aturan → I.
Hasil teorema 2-3 memegang peran penting,karena menyatakan bahwa jika sebuah hasil, katakanlah B,telah diperoleh, maka hasil selanjutnya adalah ( A→B), dengan A adalah bentuk logika apa saja. Teorema 11-4 B → (A→B) Perhatikan : pembuktian sama dengan teorema 2-3,dengan tambahan satu langkah untuk menghilangkan asumsi kedua. A
asumsi
B
asumsi
B
menggunakan Id
A→B
→I, dari baris pertama
95 B→(A→B )
→I, dari baris kedua ( selesai )
Teorema 11 - 5 { A,¬A} ┴ Pembuktian : ingat bahwa ¬A ≡ (A → ┴ ). Maka pembuktian menjadi lebih mudah. A
A→┴ ┴
Asumsi →E ( selesai )
Teorema 2-6 { ¬A} ( A→B ) Pembuktian : buatlah asumsi tambahan A bersama dengan ¬A. Dengan memanfaatkan teorema 2-5, teorema tersebut cukup mudah diselesaikan : ¬A
A
asumsi
┴ B
teorema 2-5 ┴
A→B
→I, dengan menggunakan A pada baris 1. ( selesai )
Teorema 11 – 7 ( ¬B → ¬A) → (A → B ) Pembuktian : gagasan umumnya adalah penggunaan ( ¬B → ¬A) dan A sebagai asumsi untuk mendapatkan hasilnya.
96 A
¬B→¬A
Asumsi
Asumsi tersebut tidak dapat membantu untuk maju. Sebenarnya tidak baik jika memiliki ¬B sebagai asumsi. Karena dengan demikian, dapat menggunakan modus ponens dalam ¬B dan ( ¬B → ¬A). ¬B
¬B → ¬A
asumsi
¬A
→E
Sekarang digunakan asumsi A lalu kombinasikan dengan ¬A untuk mendapatkan kontradiksi. ¬B(1) ¬B → ¬A(3)
asumsi →E dan asumsi
A(2)
¬A ┴
teorema 2-5
B
RAA, asumsi (1)¬B
A→B
→I, dengan menggunakan asumsi (2) A
( ¬B → ¬A) → (A → B )
→I, dengan menggunakan asumsi (3) ¬B → ¬A
( selesai)
Angka-angka tersebut mengindikasikan urutan asumsi yang harus dibatalkan atau dihapuskan. Untuk seterusnya urutan dapat digunakan untuk mempermudah pembuktian.
