Struktur Diskrit
Catatan kuliah Struktur Diskrit Program Ilmu Komputer
disusun oleh Yusuf Hartono Fitri Maya Puspita
UNIVERSITAS SRIWIJAYA 2006
Kata Pengantar Buku ini adalah versi pertama dari catatan kuliah Struktur Diskrit pada Program Ilmu Komputer Universitas Sriwijaya. Banyak buku yang dapat dijadikan sumber untuk mata kuliah ini dapat ditemui baik di toko buku maupun di perpustakaan. Penyusunan catatan kuliah ini dimaksudkan untuk membantu mahasiswa mengerti materi kuliah ini secara lebih terarah. Namun demikian, catatan kuliah ini bukanlah satu-satunya sumber materi untuk mata kuliah Struktur Diskrit. Karena itu, diharapkan mahasiswa tidak menjadikan catatan kulian ini sebagai satu-satunya sumber materi kuliah oleh mahasiswa, tetapi sebagai penuntun kepada isi mata kuliah. Isi catatan kuliah ini merupakan kompilasi dari berbagai sumber yang sempat penulis baca.
Indralaya, 5 Feburari 2006
Y.H. dan F.M.P.
iii
iv
Daftar Isi Kata Pengantar
iii
1 Pendahuluan 1.1 Apakah Matematika Diskrit itu? . . . . . . . . . . . . . . . . . 1.2 Mengapa Belajar Matematika Diskrit? . . . . . . . . . . . . . 1.3 Apa Isi Struktur Diskrit? . . . . . . . . . . . . . . . . . . . . . 2
Himpunan 2.1 Notasi Himpunan . . . . . . . . . . . . . 2.2 Keanggotaan Himpunan . . . . . . . . . 2.3 Diagram Venn . . . . . . . . . . . . . . . 2.4 Kesamaan Dua Himpunan . . . . . . . . 2.5 Himpunan Berhingga dan Kardinalitas . 2.6 Himpunan Bagian dan Himpunan Kuasa 2.7 Operasi Himpunan . . . . . . . . . . . . 2.8 Sifat-sifat Operasi Himpunan . . . . . . 2.9 Hasil Kali Himpunan . . . . . . . . . . .
1 1 2 3
. . . . . . . . .
5 5 5 7 7 7 8 9 10 11
3 Barisan 3.1 Barisan dan Himpunan . . . . . . . . . . . . . . . . . . . . . . 3.2 Fungsi Karakteristik . . . . . . . . . . . . . . . . . . . . . . . 3.3 Representasi Himpunan . . . . . . . . . . . . . . . . . . . . .
15 17 17 17
4 Logika 4.1 Pernyataan (Proposisi) . . . . . . . 4.2 Pernyataan Bersyarat . . . . . . . . 4.3 Inversi, Konversi, dan Kontraposisi 4.4 Ekivalensi Logis dan Tautologi . . . 4.5 Sifat-sifat Operasi Pernyataan . . . 4.6 Pernyataan Berkuantor . . . . . . . 4.7 Argumentasi Logis . . . . . . . . .
19 19 22 24 25 27 28 30
v
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . . . .
. . . . . . .
. . . . . . . . .
. . . . . . .
. . . . . . . . .
. . . . . . .
. . . . . . . . .
. . . . . . .
. . . . . . . . .
. . . . . . .
. . . . . . . . .
. . . . . . .
. . . . . . . . .
. . . . . . .
. . . . . . . . .
. . . . . . .
. . . . . . . . .
. . . . . . .
. . . . . . . . .
. . . . . . .
. . . . . . . . .
. . . . . . .
. . . . . . .
vi
DAFTAR ISI 4.8
Operasi Bit pada Komputer . . . . . . . . . . . . . . . . . . . 32
5 Teknik Membilang 5.1 Prinsip Perkalian . . . 5.2 Prinsip Sarang Merpati 5.3 Permutasi . . . . . . . 5.4 Kombinasi . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
35 35 36 37 38
6 Fungsi 41 6.1 Fungsi Kebalikan . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.2 Komposisi Fungsi . . . . . . . . . . . . . . . . . . . . . . . . . 43 7 Relasi 45 7.1 Representasi Relasi . . . . . . . . . . . . . . . . . . . . . . . . 46 8 Pengantar Teori Graf
49
9 Pohon
51
10 Bilangan Bulat 10.1 Pendahuluan . . . . . . . 10.2 Aksioma Bilangan Bulat . 10.3 Sifat-sifat Bilangan Bulat 10.4 Latihan . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
53 53 54 56 57
11 Induksi Matematika 59 11.1 Induksi Matematika . . . . . . . . . . . . . . . . . . . . . . . . 59 11.2 Latihan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 12 Matriks
63
13 Aljabar Bool
65
Daftar Pustaka
67
Bab 1 Pendahuluan 1.1
Apakah Matematika Diskrit itu?
Matematika diskrit adalah bagian dari matematika yang mempelajari objekobjek diskrit. Di sini objek-objek diskrit diartikan sebagai objek-objek yang berbeda dan saling lepas. Matematika diskrit memiliki aplikasi di hampir semua bidang kehidupan, seperti ilmu komputer, kimia, botani, zoologi, linguistik, geografi, dan bisnis. Masalah-masalah seperti • Ada berapa cara membuat password untuk sebuah sistem komputer? • Bagaimana mengurutkan sebuah himpunan bilangan bulat dari terkecil hingga terbesar? • Berapa besar peluang memenangkan sebuah undian? • Bagaimana menemukan lintasan terpendek antara dua kota dengan angkutan umum? merupakan contoh kajian dalam matematika diskrit. Secara lebih umum, matematika diskrit digunakan untuk • menghitung banyak objek • mempelajari hubungan antara himpunan-himpunan berhingga • menganalisis proses yang melibatkan langkah-langkah yang banyaknya berhingga Lima tema dalam matematika diskrit berikut tujuan masing-masing adalah 1
2
BAB 1. PENDAHULUAN 1. Penalaran matematika: memberikan pemahaman tentang penalaran matematika dalam membaca, memahami, dan membangun argumen matematika. 2. Analisis kombinatorial: memberikan keterampilan menghitung banyak objek sebagai salah satu kemampuan dasar untuk memecahkan masalah. 3. Struktur diskrit: memberikan pemahaman tentang struktur diskrit sebagai salah satu struktur matematika abstrak yang digunakan untuk menyajikan objek-objek diskrit dan hubungan di antara objek-objek itu. 4. Aplikasi dan Pemodelan: memperkenalkan aplikasi matematika diskrit dan pemodelan matematika sebagai salah satu kemampuan pemecahan masalah yang sangat penting. 5. Berpikir algoritmik: memberikan kemampuan membuat algoritma dan verifikasinya serta menganalisis memori komputer dan waktu yang dibutuhkan untuk melakukan algoritma itu.
1.2
Mengapa Belajar Matematika Diskrit?
Beberapa alasan penting belajar matematika diskrit adalah sebagai berikut: 1. matematika diskrit memberikan kemampuan membaca, memahami dan membangun argumen matematika. 2. matematika diskrit merupakan pintu gerbang untuk mempelajari mata kuliah lanjutan dalam logika, teori himpunan, teori bilangan, aljabar linier, aljabar abstrak, kombinatorika, teori graf,dan teori peluang. 3. matematika diskrit memberikan landasan matematika untuk mata kuliah ilmu komputer seperti struktur data, algoritma, teori basis data, teori automata, keamanan komputer (computer security), dan sistem operasi. 4. matematika diskrit memberikan latar belakang matematika yang diperlukan dalam pemecahan masalah riset operasi (operations research) seperti teknik optimisasi diskrit.
1.3. APA ISI STRUKTUR DISKRIT?
1.3
3
Apa Isi Struktur Diskrit?
Struktur diskrit mempelajari struktur matematika yang memiliki objek atau elemen diskrit. Struktur atau sistem matematika didefinisikan sebagai koleksi objek dengan operasi yang terdefinisi pada objek itu serta sifat-sifatnya. Struktur diskrit berisi pokok bahasan: Himpunan, Barisan, Fungsi, Logika, Teknik Membilang (counting techniques), Relasi, Graf, dan Pohon.
4
BAB 1. PENDAHULUAN
Bab 2 Himpunan 2.1
Notasi Himpunan
Himpunan adalah koleksi objek yang terdefinisi dengan jelas; artinya, kita selalu dapat menentukan apakah sebuah objek termasuk dalam koleksi atau tidak. Nama himpunan ditulis dengan menggunakan huruf besar A, B, H, S, U, . . . , sedangkan anggota himpunan ditulis dengan huruf kecil a, b, h, s, u, . . . . Contoh 2.1. Beberapa contoh himpunan. 1. A adalah himpunan bilangan asli yang kurang dari 10. 2. B adalah himpunan huruf hidup dalam abjad bahasa Indonesia. 3. C adalah himpunan kuadrat bilangan asli. 4. K adalah himpunan mahasiswa yang memiliki IPK lebih dari 3. 5. M adalah himpunan mahasiswa Universitas Sriwijaya.
2.2
Keanggotaan Himpunan
Untuk menyatakan bahwa sebuah objek a adalah anggota sebuah himpunan A kita menggunakan notasi a ∈ A. 5
6
BAB 2.
HIMPUNAN
Sedangkan notasi a∈ /A berarti a bukan anggota himpunan A. Contoh 2.2. Jika A dan B adalah himpunan-himpunan pada Contoh 2.1, maka 2 ∈ A, 10 ∈ / A, a ∈ / A, b ∈ / B, i ∈ B, 3 ∈ / B. Himpunan dari semua objek pembicaraan disebut himpunan semesta dan biasanya dilambangkan dengan U . Sedangkan himpunan yang tidak mempunyai anggota disebut himpunan kosong dengan notasi ∅. Contoh 2.3. U = N, himpunan semua bilangan asli. Contoh 2.4. Himpunan bilangan ganjil yang habis dibagi dua adalah himpunan kosong. Ada dua cara untuk menuliskan anggota sebuah himpunan. Cara pertama adalah dengan menuliskan atau mendaftarkan semua anggota himpunan itu. Contoh 2.5. Himpunan A, B, dan C pada Contoh 2.1 dapat ditulis sebagai A = {1, 2, 3, 4, 5, 6, 7, 8, 9} B = {a, i, u, e, o} C = {1, 4, 9, 16, 25, . . .} Perhatikan bahwa pada penulisan ini anggota himpunan dipisahkan oleh koma dan diapit oleh kurung kurawal. Tiga titik dalam himpunan C boleh dibaca dan seterusnya, yang berarti masih banyak anggota lain. Kesulitan akan timbul bila anggota himpunan sangat banyak, seperti himpunan M pada Contoh 2.1. Cara kedua adalah dengan menggunakan notasi pembangun himpunan, yaitu membuat diskripsi mengenai sifat-sifat anggota himpunan yang bersangkutan. Contoh 2.6. Himpunan-himpunan pada Contoh 2.1 dapat ditulis sebagai A B C K M
= = = = =
{x | x < 10, x ∈ N} {x | x adalah huruf hidup dalam abjad bahasa Indonesia} {x2 | x ∈ N} {x | x adalah mahasiswa yang memiliki IPK lebih dari 3} {x | x adalah himpunan mahasiswa Universitas Sriwijaya}
Dalam bahasa Inggris tanda ”|” dibaca ”where”. Dalam bahasa Indonesia tanda ini bisa dibaca ”di mana” walaupun menurut kaidah bahasa Indonesia hal ini kurang tepat.
2.3. DIAGRAM VENN
2.3
7
Diagram Venn
Himpunan dapat digambarkan dengan diagram Venn. Dalam diagram ini himpunan semesta digambarkan sebagai empat persegi panjang sedangkan himpunan-himpunan di dalamnya digambarkan sebagai lingkaran atau bentuk geometri lain. Anggota himpunan biasanya dinyatakan sebagai titik. Gambar 2.1 menyajikan beberapa contoh diagram Venn.
U A .a . c b.
U A
B
.d
U
A B C
Gambar 2.1: Contoh Diagram Venn
2.4
Kesamaan Dua Himpunan
Dua himpunan A dan himpuan B dikatakan sama, yaitu A=B bila kedua himpunan itu memiliki anggota yang persis sama. Dengan kata lain, setiap anggota A adalah anggota B dan setiap anggota B adalah juga anggota A. Contoh 2.7. Misalkan S = {1, 3, 5} dan T = {5, 1, 3}. Meskipun anggota himpunan S dan T ditulis dalam urutan yang berbeda, S = T .
2.5
Himpunan Berhingga dan Kardinalitas
Himpunan dengan anggota yang banyaknya berhingga seperti himpunan A dan B pada Contoh 2.5 disebut himpunan berhingga. Banyak anggota sebuah himpunan berhingga disebut kardinalitas. Notasi n(A) atau |A| digunakan untuk menyatakan kardinalitas himpunan A. Pada Contoh 2.5, n(A) = 9 dan n(B) = 5. Sedangkan himpunan dengan anggota yang banyaknya tak hingga seperti himpunan C pada Contoh 2.5 disebut himpunan tak hingga.
8
2.6
BAB 2.
HIMPUNAN
Himpunan Bagian dan Himpunan Kuasa
Jika setiap anggota himpunan A adalah juga anggota himpunan B, maka A disebut himpunan bagian dari B, ditulis A⊆B
atau B ⊇ A.
Notasi terakhir dibaca ”B memuat A.” Secara matematis, himpunan bagian didefinisikan sebagai berikut: Definisi 2.1. A ⊆ B jika dan hanya jika x ∈ A berarti x ∈ B. Bila A ⊆ B dan A 6= B, maka A dinamakan himpunan bagian sejati dari B dan ditulis dengan notasi A ⊂ B atau B ⊃ A. Catatan. Untuk membuktikan bahwa A adalah himpunan bagian dari B, kita ambil sembarang x anggota A dan tunjukkan dengan alasan yang logis bahwa x juga anggota B. Contoh 2.8. Misalkan H = {x | x adalah huruf dalam abjad bahasa Indonesia}. Himpunan B pada Contoh 2.5 adalah himpunan bagian dari H. Jadi, B ⊂ H. Sementara M bukan himpunan bagian dari H, yaitu M 6⊂ H. Dengan definisi himpunan bagian kita dapat menulis kembali defini kesamaan dua himpunan sebagai berikut. Definisi 2.2 (Kesamaan Dua Himpunan). A=B
jika dan hanya jika A ⊂ B dan B ⊂ A
Catatan. Untuk membuktikan kesamaan dua himpunan kita harus menunjukkan bahwa himpunan yang satu merupakan himpunan bagian dari himpunan yang lain dan sebaliknya. Koleksi dari semua himpunan bagian sebuah himpunan A disebut himpunan kuasa, dan ditulis dengan notasi 2A . Contoh 2.9. Untuk himpunan S pada Contoh 2.7, 2S = {∅, {1}, {3}, {5}, {1, 3}, {1, 5}, {3, 5}, {1, 3, 5}} .
2.7. OPERASI HIMPUNAN
9
Perhatikan bahwa himpunan kosong merupakan himpunan bagian dari semua himpunan. Untuk membuktikan hal ini kita memerlukan pemahaman tentang implikasi, lihat Contoh 4.10. Perhatikan pula pada contoh ini bahwa himpunan kuasa 2S memiliki kardinalitas 8. Secara umum, kita mempunyai teorema berikut. Teorema 2.1 (Kardinalitas Himpunan Kuasa). Untuk sembarang himpunan A, n(2A ) = 2n(A) . Bukti teorema ini akan mudah dipahami setelah kita mempelajari kombinasi pada Bagian 5.4.
2.7
Operasi Himpunan
Seperti bilangan, sebuah himpunan juga dapat dioperasikan dengan himpunan lain. Kalau dalam bilangan kita mengenal operasi kali, bagi, tambah, dan kurang, maka dalam himpunan kita mengenal operasi-operasi berikut: 1. Selisih A dan B adalah semua anggota A yang bukan anggota B, yaitu A \ B = {x | x ∈ A dan x ∈ / B}. 2. Gabungan A dan B adalah semua elemen yang ada dalam A atau dalam B atau dalam kedua-duanya, yaitu A ∪ B = {x | x ∈ A atau x ∈ B}. 3. Irisan A dan B adalah semua elemen yang ada dalam A dan B secara bersama-sama, yaitu A ∩ B = {x | x ∈ A dan x ∈ B}. 4. Komplemen A adalah semua anggota himpunan semesta yang berada di luar A, yaitu Ac = {x | x ∈ / A}. 5. Selisih Simetris A dan B adalah semua eleman yang ada dalam A atau dalam B tetapi tidak dalam kedua-duanya, yaitu A ⊕ B = {x | (x ∈ A dan x ∈ / B) atau (x ∈ B dan x ∈ / A)}.
10
BAB 2.
2.8
Sifat-sifat Operasi Himpunan
Operasi himpunan memiliki sifat-sifat berikut: 1. Idempoten (a) A ∩ A = A (b) A ∪ A = A 2. Komutatif (a) A ∩ B = B ∩ A (b) A ∪ B = B ∪ A 3. Asosiatif (a) (A ∩ B) ∩ C = A ∩ (B ∩ C) (b) (A ∪ B) ∪ C = A ∪ (B ∪ C) 4. Distributif (a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (b) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) 5. Sifat Komplemen (a) A ∪ Ac = U (b) A ∩ Ac = ∅ (c) (Ac )c = A (d) U c = ∅ dan ∅c = U 6. Sifat Identitas (a) A ∪ ∅ = A (b) A ∩ U = A (c) A ∪ U = U (d) A ∩ ∅ = ∅ 7. Hukum de Morgan (a) (A ∪ B)c = Ac ∩ B c (b) (A ∩ B)c = Ac ∪ B c
HIMPUNAN
2.9. HASIL KALI HIMPUNAN
11
Berikut akan dibuktikan sifat 7(a) sebagai contoh. Untuk bukti sifat-sifat lain lihat Latihan 4 pada bagian akhir bab ini. Bukti sifat 7(a). Misalkan x ∈ (A ∪ B)c , maka menurut definisi komplemen x ∈ / (A ∪ B). Ini berarti x bukan anggota A dan juga bukan anggota B, karena kalau tidak demikian x ∈ (A ∪ B). Jadi x ∈ Ac dan x ∈ B c sehingga x ∈ (Ac ∩B c ). Dengan ini kita telah menunjukkan bahwa (A∪B)c ⊂ Ac ∩B c . Sebaliknya, misalkan y ∈ Ac ∩ B c , maka y ∈ / A dan y ∈ / B. Ini berarti y tidak mungkin berada dalam A ∪ B, yaitu y ∈ / (A ∪ B)c . Karena itu, (A ∪ B)c ⊂ Ac ∩ B c . Jadi, menurut Definisi 2.2, (A ∪ B)c = Ac ∩ B c . 2 Kadang-kadang kita perlu menyatakan kardinalitas gabungan dua buah himpunan. Untuk menghitung kardinalitas A ∪ B, kita dapat menjumlahkan kardinalitas A dan kardinalitas B. Dengan cara ini anggota himpunan yang berada di A dan B akan terhitung dua kali. Karena itu kita harus mengurangkannya seperti pada teorema berikut ini. Teorema 2.2 (Prinsip Penjumlahan). Jika A dan B adalah dua himpunan berhingga, maka n(A ∪ B) = n(A) + n(B) − n(A ∩ B). Contoh 2.10. Dari survei di sebuah kelas diketahui bahwa ada 25 siswa yang menyukai matematika dan 30 yang menyukai bahasa Inggris. Ditemukan pula bahwa di kelas itu ada 15 orang yang suka matematika dan bahasa Inggris. Ada berapa siswa dalam kelas itu? Umtuk menjawab soal ini, kita misalkan A = {x | x adalah siswa yang gemar matematika}, B = {x | x adalah siswa yang gemar bahasa Inggris}. Dari soal diketahui bahwa n(A) = 25, n(B) = 30, dan n(A ∩ B) = 15. Dengan prinsip penjumlahan kita peroleh n(A ∪ B) = 40. Jadi dalam kelas itu terdapat 40 siswa.
2.9
Hasil Kali Himpunan
Misalkan A dan B adalah dua buah himpunan, maka hasil kali A dan B yang ditulis dengan notasi A × B didefinisikan sebagai pasangan berurut yang
12
BAB 2.
HIMPUNAN
posisi pertamanya ditempati oleh elemen A dan posisi kedua oleh elemen B, yaitu A × B = {(a, b) | a ∈ A dan b ∈ B}. Hasil kali himpunan ini merupakan salah satu cara menyajikan sebuah fungsi yang akan kita pelajari pada Bab 6. Contoh 2.11. Misalkan B = {a, i, u, e, o} dan S = {1, 2, 3}. B × S = {(a, 1), (a, 2), (a, 3), (i, 1), (i, 2), (i, 3), (u, 1), (u, 2), (u, 3), (e, 1), (e, 2), (e, 3), (o, 1), (o, 2), (o, 3)} Perhatikan B × S memiliki 15 anggota (mengapa?).
Latihan 1. Misalkan U = {1, 2, . . . , 15}, A = {1, 3, 5, 6, 8, 10}, B = {1, 5, 7, 8, 9}, dan C = {1, 2, 4, 6, 9, 15}. Tentukan anggota himpunan-himpunan berikut: (a) Ac (b) A ∪ B (c) A ∩ B (d) A ∩ (B ∪ C) (e) A ∩ B ∩ C (f) B \ A (g) {X | X ⊂ A, n(X) = 3} 2. Tuliskanlah semua anggota himpunan kuasa dari himpunan B pada Contoh 2.5. 3. Tentukan kardinalitas himpunan-himpunan berikut: (a) {x | x adalah himpunan huruf dalam ”matematika”}. (b) {x | x adalah himpunan bagian dari {a,1,g}}. (c) {x | x2 = 4, x ∈ N}. (d) {∅}. (e) ∅. 4. Buktikan sifat-sifat operasi himpunan berikut:
2.9. HASIL KALI HIMPUNAN
13
(a) A ∩ A = A. (b) (A ∩ B) ∩ C = A ∩ (B ∩ C). (c) A ∩ (B ∪ C) = (A ∩ B) ∪ (B ∩ C). (d) (Ac )c = A. (e) (A ∩ B)c = Ac ∪ B c . 5. Buktikan bahwa (a) A \ B = A ∩ B c . (b) B = (B ∩ A) ∪ (B ∩ Ac ). (c) A ∪ B = A ∪ (B ∩ Ac ). 6. Tunjukkan bahwa A ⊕ B = (A ∪ B) \ (A ∩ B). 7. Tunjukkan bahwa jika A ⊂ B, maka A ∩ B = A dan A ∪ B = B. 8. Sebuah survei terhadap 500 penonton televisi menemukan bahwa 285 suka nonton acara olahraga, 195 menyukai sinetron, 115 suka berita, 45 suka olahraga dan sinetron, 70 suka olahraga dan berita, 50 suka sinetron dan berita, dan 50 tidak suka ketiga acara tersebut. (a) Berapa orang yang suka ketiga acara televisi tersebut? (b) Berapa orang yang suka nonton tepat satu di antara tiga acara tersebut?
14
BAB 2.
HIMPUNAN
Bab 3 Barisan Dalam teori bilangan kita mengenal barisan aritmetika dan barisan geometri. Dua barisan ini adalah contoh dari barisan yang akan kita pelajari dalam bab ini. Secara umum, barisan adalah daftar objek terurut. Tidak seperti dalam himpunan, elemen-elemen sebuah barisan, yang disebut juga suku, mempunyai urutan yang tetap dan ditulis dengan huruf kecil yang diberi indeks untuk menyatakan posisinya. Jadi untuk menuliskan barisan kita menggunakan notasi berikut: s1 , s2 , . . . , s i , . . . , dengan si sebagai suku ke-i. Berikut beberapa contoh barisan. Contoh 3.1. 1, 0, 1, 1, 0, 0, 1, 1, 0, 1 adalah barisan dengan suku yang berulang. Angka nol muncul sebagai suku kedua, kelima, keenam, dan kesembilan. Contoh 3.2. 2, 6, 10, 14, . . . Contoh 3.3. 1, 4, 9, . . . Banyaknya suku dalam sebuah barisan disebut panjang barisan itu. Barisan dengan panjang berhingga disebut barisan berhingga, sedangkan barisan yang panjangnya tak hingga disebut barisan tak hingga. Barisan pada Contoh 3.1 adalah barisan berhingga yang panjangnya 10 dan barisan pada Contoh 3.2 dan 3.3 adalah barisan tak hingga. Kita menggunakan ”. . .” untuk menyatakan bahwa sebuah barisan terus berlanjut. Biasanya suku-suku dalam sebuah barisan dinyatakan dengan rumus. Ada dua macam rumus yang biasa digunakan untuk menyatakan suku-suku 15
16
BAB 3. BARISAN
dalam sebuah barisan. Perhatikan suku-suku dalam barisan pada Contoh 3.2. Sebuah suku dapat diperoleh dengan menambahkan 4 pada suku sebelumnya, yaitu a1 = 2, an = an−1 + 4, 2 ≤ n < ∞. Rumus ini disebut rumus rekursif. Penggunaan rumus semacam ini selalu melibatka suku pertama. Sementara itu, suku-suku dalam barisan pada Contoh 3.3 dapat langsung diperoleh sesuai posisinya, dalam hal ini an = n2 ,
1 ≤ n < ∞.
Rumus semacam ini disebut rumus eksplisit. Contoh 3.4. Rumus rekursif c1 = 5 dan cn = cn−1 + 5,
2≤n≤5
memberikan barisan berhingga 5, 10, 15, 20, 25. Contoh 3.5. Rumus rekursif f1 = f2 = 1 dan fn = fn−1 + fn−2 ,
3≤n<∞
memberikan barisan tak hingga 1, 1, 2, 3, 5, 8, 13, . . .. Bilangan fn ini dikenal sebagai bilangan Fibonacci. Contoh 3.6. Rumus eksplisit tn =
1 , n
1≤n<∞
memberikan barisan tak hingga 1 1 1 1, , , , . . . . 2 3 4 Kata-kata seperti komputer, matematika, menulis dan sebagainya dapat juga dipandang sebagai barisan yang ditulis tanpa koma. Barisan seperti ini dikenal dengan nama string. Contoh 3.7. Kata matematika dapat dianggap sebagai barisan m, a, t, e, m, a, t, i, k, a. Dalam ilmu komputer, barisan dikenal dengan nama linear array atau list sekalipun dengan pengertian yang agak berbeda. Array dalam ilmu komputer adalah barisan posisi. Nilai dari posisi ke-n sebuah array ditulis dengan notasi S[n]. Jadi, S[1], S[2], S[3], . . . adalah barisan nilai sebuah array.
3.1. BARISAN DAN HIMPUNAN
3.1
17
Barisan dan Himpunan
Himpunan yang bersesuaian dengan sebuah barisan adalah kumpulan semua suku dalam barisan itu. Contoh 3.8. Himpunan yang bersesuaian dengan barisan pada Contoh 3.1 adalah {0, 1}, sedangkan himpunan yang bersesuaian dengan barisan pada Contoh 3.7 adalah {m, a, t, e, i, k}.
3.2
Fungsi Karakteristik
Walaupun kita akan membicarakan fungsi pada Bab 6, pada bagian ini kita dapat menganggap fungsi pada sebuah himpunan sebagai aturan untuk memberi nilai bagi setiap elemen dalam himpunan itu. Fungsi karakteristik himpunan A didefinisikan sebagai 1, x ∈ A, fA (x) = 0, x ∈ / A. Contoh 3.9. Jika A = {a, i, u, e, o}, maka fA (a) = fA (u) = 1, sedangkan fA (b) = 0 dan fA (r) = 0, tetapi fAc (b) = 1 (mengapa demikian?). Kita dapat menggunakan fungsi karakteristik untuk membuktikan sifatsifat operasi himpunan. Contoh 3.10. Kita dapat menunjukkan bahwa fA∩B = fA fB , lihat Latihan 3 pada bagian akhir bab ini.
3.3
Representasi Himpunan
Dalam komputer sebuah himpunan dinyatakan sebagai barisan 0 dan 1 yang merupakan nilai fungsi karakteristik himpunan itu. Mula-mula komputer akan memberikan posisi yang tetap pada setiap elemen himpunan semesta. Jika himpunan semesta U memiliki n anggota, maka setiap himpunan di dalamnya akan dinyatakan sebagai barisan 0 dan 1 sepanjang n sesuai dengan nilai karakteristik himpunan itu. Contoh berikut akan memperjelas situasi ini. Contoh 3.11. Misalkan U = {1, 2, 3, 4, 5, 6, 7, 8, 9}, A = {1, 3, 5, 7, 9}, B = {2, 4, 6, 8}, dan C = {1, 4, 9}. Karena n(U ) = 10, maka setiap himpunan di dalam U akan dinyatakan sebagai barisan yang panjangnya 10. Himpunan
18
BAB 3. BARISAN
A direpresentasikan sebagai barisan 1,0,1,0,1,0,1,0,1,0; himpunan B oleh barisan 0,1,0,1,0,1,0,1,0,1; dan himpunan C oleh barisan 1,0,0,1,0,0,0,0,1,0. Bagaimana komputer memilih anggota A∩C dan B∩C? Bandingkan dengan Contoh 3.10.
Latihan 1. Tulislah barisan berikut: (a) a1 = 10 dan an = 2an−1 , n = 2, 3, . . . , 6. (b) b1 = 4 dan bn = bn−1 + 4, n = 2, 3, . . .. (c) cn = n2 , n = 1, 2, 3, . . .. 2. Buatlah lima buah barisan dari himpunan B = {a, i, u, e, o}. 3. Tunjukkan bahwa fA∩B = fA fB . 4. Misalkan U = {x1 , x2 , x3 , x4 , x5 , x6 , x7 }. Bila himpunan A dinyatakan oleh barisan 1, 1, 0, 0, 1, 0, 0, himpunan B sebagai barisan 0, 0, 1, 1, 0, 0, 0, dan C sebagai barisan 0, 1, 0, 0, 0, 1, 1, tulislah representasi dan anggota himpunan-himpunan berikut: (a) A ∩ B (b) B ∩ C (c) A ∪ C (d) A \ C (e) A ∩ B ∩ C 5. Bagaimana representasi himpunan semesta dan himpunan kosong oleh komputer? Dengan menggunakan representasi itu tunjukkan bahwa bahwa U ∩ ∅ = ∅ dan U ∪ ∅ = U .
Bab 4 Logika Logika adalah studi tentang metode bernalar. Logika memberikan aturan untuk menentukan kasahihan (validitas) sebuah argumen. Argumentasi logis digunakan dalam matematika untuk membuktikan teorema-teoremanya. Dalam ilmu komputer logika digunakan untuk menguji kebenaran sebuah program.
4.1
Pernyataan (Proposisi)
Dalam bahasa orang mengenal kalimat sebagai rangkaian kata yang disusun sedemikian rupa sehingga mempunyai arti yang utuh. Salah satu bentuk kalimat adalah kalimat deklaratif atau kalimat pernyataan. Definisi 4.1. Pernyataan adalah kalimat yang benar atau salah, tetapi tidak kedua-duanya. Kalimat tanya atau kalimat perintah tidak dianggap sebagai pernyataan. Contoh 4.1. Kalimat-kalimat berikut adalah pernyataan. 1. Hari ini hari Sabtu. 2. Matahari bersinar cerah. 3. 2 + 3 = 6. 4. Palembang bukan ibukota propinsi Sumatera Selatan. 5. Jika 2 + 2 = 5, maka hari kiamat tiba. 6. x + 1 > x 19
20
BAB 4. LOGIKA
Contoh 4.2. Kalimat-kalimat berikut bukan pernyataan. 1. x + 2 = 10. 2. Minumlah sirop ini dua kali sehari. 3. Alangkah cantiknya gadis itu! 4. Siapa namamu? Kita menggunakan huruf kecil p, q, r, . . . untuk menamakan pernyataan sama seperti kita menggunakan x, y, . . . dalam kalkulus. Contoh 4.3. Kita menamakan pernyataan dengan cara sebagai berikut. p : Hari ini hari Sabtu. q : Matahari bersinar cerah. Dari pernyataan-pernyataan tunggal kita dapat membuat pernyataan majemuk dengan menggunakan konektor atau operator logika. Penggunaan operator ini sama dengan penggunaan operator × dan + dalam bilangan atau ∩ dan ∪ dalam himpunan. Nilai kebenaran pernyataan majemuk tergantung pada nilai kebenaran pernyataan-pernyataan tunggal yang membentuknya. Tabel yang berisi nilai kebenaran pernyataan majemuk berdasarkan semua kombinasi nilai kebenaran pernyataan yang membentuknya disebut tabel kebenaran. Negasi atau ingkaran dari pernyataan p ditulis dengan notasi ¬p dan dibaca ”tidak p.” Negasi p bernilai salah jika p benar dan bernilai benar jika p salah seperti disajikan pada Tabel 4.1. Sebenarnya ”tidak” bukan sebuah konektor karena tidak menghubungkan dua pernyataan. p B S
¬p S B
Tabel 4.1: Tabel kebenaran ¬p
4.1. PERNYATAAN (PROPOSISI)
21
Contoh 4.4. Berikut ini adalah contoh negasi. p : Palembang adalah ibukota propinsi Sumatera Selatan. ¬p : Tidak benar Palembang adalah ibukota propinsi Sumatera Selatan. atau Palembang bukan ibukota propinsi Sumatera Selatan. Di sini ¬p salah karena p benar. Dua pernyataan yang dihubungan dengan kata ”dan” disebut konjungsi dan ditulis dengan notasi p ∧ q. Tabel kebenaran konjungsi disajikan pada Tabel 4.2. Contoh 4.5. Berikut ini adalah contoh konjungsi. p : Hari ini hari Sabtu. q : Matahari bersinar cerah. p ∧ q : Hari ini hari Sabtu dan matahari berinar cerah. p B B S S
q B S B S
p∧q B S S S
Tabel 4.2: Tabel kebenaran p ∧ q Perhatikan bahwa konjungsi benar hanya jika kedua pernyataan yang membentuknya benar. Jadi pernyataan ”hari ini hari Sabtu dan matahari bersinar cerah” benar hanya bila matahari bersinar cerah pada hari Sabtu. Pernyataan ini salah bila matahari bersinar cerah tidak pada hari Sabtu atau hari ini hari Sabtu tetapi matahari tidak bersinar cerah, apalagi kalau hari ini bukan Sabtu dan matahari tidak bersinar cerah. Dua pernyataan yang dihubungkan dengan kata ”atau” disebut disjungsi dan ditulis dengan notasi p ∨ q. Tabel kebenaran disjungsi disajikan pada Tabel 4.3.
22
BAB 4. LOGIKA p B B S S
q B S B S
p∨q B B B S
Tabel 4.3: Tabel kebenaran p ∨ q Contoh 4.6. Berikut ini adalah contoh disjungsi. p : Hari ini hari Sabtu. q : Matahari bersinar cerah. p ∨ q : Hari ini hari Sabtu atau matahari berinar cerah. Perhatikan bahwa pernyataan ”hari ini hari Sabtu atau matahari bersinar cerah” salah hanya jika hari ini bukan Sabtu dan matahari tidak bersinar cerah. Pernyataan ini benar jika matahari bersinar cerah sekalipun tidak pada hari Sabtu atau matahari tidak bersinar cerah pada hari Sabtu, apalagi kalau matahari bersinar cerah pada hari Sabtu. Contoh 4.7. Berikut ini contoh lain dari disjungsi. p : x < 0. q : x > 1. p ∨ q : x < 0 atau x > 1. Contoh 4.6 dan Contoh 4.7 kadua-duanya memberikan contoh disjungsi. Sekarang perhatikan baik-baik perbedaan antara kedua disjungsi ini. Pada Contoh 4.6, terbuka kemungkinan pernyataan p dan q kedua-duanya benar, yaitu ketika matahari bersinar cerah pada hari Sabtu, sedangkan pada Contoh 4.7, p dan q tidak mungkin kedua-duanya benar secara bersama-sama sebab bila x < 0 tidak mungkin x > 1. Dalam hal ini kita benar-benar harus memilih satu di antara dua. Disjungsi yang terakhir ini disebut disjungsi eksklusif. Untuk membedakannya dengan disjungsi biasa kita menggunakan notasi p ⊕ q untuk disjungsi eksklusif. Pernyataan p ⊕ q dibaca ”p atau q tetapi tidak kedua-duanya.” Tabel kebenaran untuk p ⊕ q disajikan pada Tabel 4.4.
4.2
Pernyataan Bersyarat
Pernyataan ”jika p, maka q” disebut implikasi dan kita menggunakan notasi p → q untuk menuliskan implikasi. Pernyataan p disebut hipotesis atau
4.2. PERNYATAAN BERSYARAT p B B S S
q B S B S
23 p⊕q S B B S
Tabel 4.4: Tabel kebenaran p ⊕ q anteseden, sedangkan pernyataan q disebut konklusi atau kesimpulan. Selain dibaca ”jika p maka q,” implikasi p → q dapat juga dibaca sebagai: (i) q jika p (ii) p hanya jika q (iii) p syarat cukup bagi q (iv) q syarat perlu bagi p Tabel 4.5 menyajikan tabel kebenaran implikasi. p B B S S
q B S B S
p→q B S B B
Tabel 4.5: Tabel kebenaran p → q Contoh 4.8. Berikut ini adalah contoh implikasi. p : Hari ini hari Sabtu. q : Matahari bersinar cerah. p → q : Jika hari ini hari Sabtu, maka matahari berinar cerah. Pernyataan ”jika hari ini hari Sabtu, maka matahari berinar cerah” selalu benar pada hari yang bukan Sabtu tanpa menghiraukan apakah matahari bersinar cerah atau tidak. Pernyataan ini juga benar pada saat matahari bersinar cerah tanpa menghiraukan hari. Pernyataan ini salah hanya bila hari ini hari Sabtu tetapi matahari tidak bersinar cerah. Perlu dicatat di sini bahwa dalam implikasi tidak selalu perlu adanya hubungan sebab akibat.
24
BAB 4. LOGIKA
Contoh 4.9. Pernyataan ”jika 2+2 = 5, maka 3+3 = 4” adalah pernyataan yang benar sekalipun 3 + 3 = 4 bukan akibat dari 2 + 2 = 5. Contoh 4.10. Contoh ini memdemonstrasikan penggunaan implikasi untuk membuktikan bahwa ∅ ⊂ A untuk sembarang himpunan A. Untuk tujuan ini, kita harus menunjukkan bahwa jika x ∈ ∅, maka x ∈ A. Tetapi x ∈ ∅ adalah pernyataan salah karena himpunan kosong tidak mempnyai anggota. Menurut Tabel 4.5, antiseden yang salah selalu menghasilkan implikasi yang benar apapun nilai kebenaran konklusinya. Jadi, untuk kasus x ∈ A ataupun x∈ / A, implikasi (x ∈ ∅) → (x ∈ A) bernilai benar. Contoh berikut menjelaskan pengertian syarat cukup dan syarat perlu. Contoh 4.11. Misalkan p : x adalah kambing, q : x adalah hewan berkaki empat. Pernyataan ”kambing berkaki empat” dapat dipandang sebagai implikasi p → q. Kambing adalah syarat cukup untuk hewan berkaki empat sekalipun tidak perlu. Sedangkan berkaki empat adalah syarat perlu untuk kambing, namun tidak cukup.
4.3
Inversi, Konversi, dan Kontraposisi
Inversi dari implikasi p → q adalah ¬p → ¬q, sedangkan konversinya adalah q → p. Selanjutnya, ¬q → ¬p disebut kontraposisi. Contoh 4.12. Misalkan p : Minggu depan ada ujian, q : Mahasiswa sibuk belajar. Maka p→q
:
Jika minggu depan ada ujian, maka mahasiswa sibuk belajar. ¬p → ¬q : Jika minggu depan tidak ada ujian, maka mahasiswa tidak sibuk belajar q→p : Jika mahasiswa sibuk belajar, maka minggu depan ada ujian. ¬q → ¬p : Jika mahasiswa tidak sibuk belajar, maka minggu depan tidak ada ujian.
4.4. EKIVALENSI LOGIS DAN TAUTOLOGI
25
Tabel 4.6 memperlihatkan bahwa p → q memiliki nilai kebenaran yang sama dengan ¬q → ¬p, sedangkan q → p mempunyai nilai kebenaran yang sama dengan ¬p → ¬q. Pernyataan-pernyataan yang mempunyai nilai kebenaran selalu sama disebut pernyataan yang ekivalen. Pernyataan semacam ini akan dibicarakan pada Bagian 4.4. Jadi pernyataan ”jika minggu depan ada ujian, maka mahasiswa sibuk belajar” ekivalen dengan pernyataan ”jika mahasiswa tidak sibuk belajar, maka minggu depan tidak ada ujian”. Hal ini bisa dijelaskan sebagai berikut. Jika mahasiswa tidak sibuk belajar, pasti minggu depan tidak ada ujian sebab kalau ada mahasiswa akan sibuk belajar. Lain halnya dengan inversi dan konversinya. Jika minggu depan tidak ada ujian belum tentu mahasiswa tidak sibuk belajar, sebaliknya jika mahasiswa sibuk belajar belum tentu minggu depan ada ujian. p B B S S
q B S B S
¬p S S B B
¬q S B S B
p→q B S B B
¬p → ¬q B B S B
q → p ¬q → ¬p B B B S S B B B
Tabel 4.6: Implikasi, Inversi, Konversi, dan Kontraposisi
4.4
Ekivalensi Logis dan Tautologi
Dalam argumentasi matematika kadang-kadang kita perlu mengganti sebuah pernyataan dengan pernyataan lain yang mempunyai nilai kebenaran yang sama. Dua pernyataan yang selalu mempunyai nilai kebenaran yang sama disebut ekivalen secara logis. Kita menggunakan notasi p≡q untuk menyatakan bahwa p ekivalen dengan q.
Contoh 4.13. Dari Tabel 4.6 kita peroleh (p → q) ≡ (¬q → ¬p) dan (q → p) ≡ (¬p → ¬q).
26
BAB 4. LOGIKA
Ekivalensi logis ini bisa juga ditulis sebagai implikasi dua arah dengan notasi p ↔ q. Implikasi dua arah, p ↔ q, ini dibaca ”p jika dan hanya jika q” atau ”p adalah syarat perlu dan cukup untuk q”. Pernyataan terakhir menunjukkan bahwa p ↔ q ekivalen dengan p → q dan q → p, lihat Contoh 4.14. Tabel kebenaran p ↔ q diberikan pada Tabel 4.7. p B B S S
q B S B S
p↔q B S S B
Tabel 4.7: Tabel kebenaran p ↔ q Perhatikan bahwa implikasi dua arah p ↔ q bernilai nenar hanya jika p dan q memiliki nilai kebenaran yang sama, yaitu kedua-duanya benar atau kedua-duanya salah. Selanjutnya, tautologi adalah pernyataan yang selalu benar apapun kombinasi nilai kebenaran pernyataan-pernyataan yang ada di dalamnya. Sebaliknya pernyataan yang selalu salah disebut kontradiksi dan pernyataan yang bukan tautologi ataupun kontradiksi disebut kontingensi. Kita akan menggunakan notasi T untuk tautologi dan F untuk kontradiksi. Definisi ekivalensi dan implikasi dua arah menyarankan bahwa p dan q ekivalen jika p ↔ q merupakan tautologi. Contoh 4.14. Perhatikan tabel kebenaran berikut p B B S S
q B S B S
p→q B S B B
q→p B B S B
(p → q) ∧ (q → q) p ↔ q B B S S S S B B
Dari tabel ini terlihat bahwa (p → q) ∧ (q → q) ekivalen dengan p ↔ q dan kita dapat menulisnya sebagai (p → q) ∧ (q → q) ≡ p ↔ q. Menggunakan Tabel 4.7 kita dapat juga memperlihatkan bahwa ((p → q) ∧ (q → q)) ↔ (p ↔ q) adalah tautologi.
4.5. SIFAT-SIFAT OPERASI PERNYATAAN
4.5
27
Sifat-sifat Operasi Pernyataan
Operasi pernyataan memiliki sifat-sifat berikut: 1. Idempoten (a) p ∧ p ≡ p (b) p ∨ p ≡ p 2. Komutatif (a) p ∧ q ≡ q ∧ p (b) p ∨ q ≡ q ∨ p 3. Asosiatif (a) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (b) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) 4. Distributif (a) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) (b) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) 5. Sifat Negasi (a) ¬(¬p) ≡ p 6. Sifat Identitas (a) p ∨ F ≡ p (b) p ∧ T ≡ p (c) p ∨ T ≡ T (d) p ∧ F ≡ F 7. Hukum de Morgan (a) ¬(p ∨ q) ≡ ¬p ∧ ¬q (b) ¬(p ∧ q) ≡ ¬p ∨ ¬q Bukti sifat-sifat ini sengaja ditinggalkan sebagai latihan. Contoh 4.15 mendemonstrasikan penggunaan tabel kebenaran untuk membuktikan salah satu hukum de Morgan.
28
BAB 4. LOGIKA
Contoh 4.15. Pada contoh ini akan ditunjukkan bahwa ¬(p∨q) ↔ (¬p∧¬q) adalah tautologi. Untuk itu, perhatikan tabel di bawah ini. p 1 B B S S
q 2 B S B S
¬p 3 S S B B
¬q 4 S B S B
p∨q 5 B B B S
¬(p ∨ q) ¬p ∧ ¬q 6 7 S S S S S S B B
¬(p ∨ q) ↔ (¬p ∧ ¬q) 8 B B B B
Untuk melihat ekivalensi ¬(p∨q) dan ¬p∧¬q, perhatikan kolom ke-6 dan ke7 pada tabel di atas. Kedua kolom ini memiliki nilai kebenaran yang sama. Selain itu kita dapat juga memperhatikan kolom ke-8 yang menunjukkan bahwa ¬(p ∨ q) ↔ (¬p ∧ ¬q) adalah tautologi.
4.6
Pernyataan Berkuantor
Sekarang mari kita perhatikan kalimat-kalimat seperti x + 1 > x dan x + 2 = 10. Pada Contoh 4.1 dan Contoh 4.2 telah disebutkan bahwa kalimat pertama adalah pernyataan, sedangkan kalimat kedua bukan pernyataan. Mengapa demikian? Kita dapat melihat dengan mudah bahwa pernyataan pertama selalu benar untuk semua harga x, sedangkan ,pernyataan kedua bisa benar dan bisa salah tergantung pada harga x yang diberikan. Kalimat semacam ini kita sebut pernyataan bervariabel karena nilai kebenarannya tergantung pada harga variabel itu. Kita menulisnya seperti berikut ini. p(x) : x + 1 > x, q(x) : x + 2 = 10. pernyataan p(x) benar untuk semua harga x yang diberikan, sedangkan pernyataan q(x) benar untuk harga x tertentu, dalam hal ini q(8) dan salah untuk harga x yang lain. Untuk menyatakan apakah sebuah pernyataan bervariabel benar untuk semua harga variabel atau untuk sebagian harga variabel, kita menggunakan dua macam kuantor, yaitu kuantor universal dan kuantor eksistensial.
4.6. PERNYATAAN BERKUANTOR
29
Kuantor universal digunakan untuk menyatakan bahwa p(x) benar untuk semua harga x dalam himpunan semesta. Kita menulisnya dengan notasi ∀x, p(x). Notasi ini dibaca ”untuk semua x, p(x) benar” atau ”p(x) berlaku untuk semua x”. Contoh 4.16. Pernyataan ∀x ∈ R, x2 ≥ 0 dibaca ”x2 ≥ 0 berlaku untuk semua bilangan nyata x”. Kuantor eksistensial digunakan untuk menyatakan bahwa p(x) berlaku untuk sebagian (paling sedikit satu) harga x dalam himpunan semesta. Kita menulisnya dengan notasi ∃x, p(x). Notasi ini dibaca ”ada harga x yang membuat p(x) benar” atau ”ada (paling sedikit satu) harga x yang memenuhi p(x).” Contoh 4.17. Pernyataan ∃x ∈ R, x2 + 1 = 0 dibaca ”ada bilangan nyata x sedemikian hingga x2 + 1 = 0”. Pernyataan ”semua mahasiswa Unsri tinggal di Indralaya” menjadi salah kalau ada satu saja mahasiswa Unsri yang tidak tinggal di Indralaya. Jadi, ingkaran ∀x, p(x) adalah ∃x, ¬p(x), atau secara simbolis ¬∀x, p(x) ≡ ∃x, ¬p(x). Sebaliknya, untuk menyangkal pernyataan ”ada mahasiswa Unsri yang menggunakan narkoba”, kita harus menunjukkan bahwa semua mahasiswa Unsri tidak menggunakan narkoba. Jadi, ingkaran ∃x, p(x) adalah ∀x, ¬p(x), atau secara simbolis ¬∃x, p(x) ≡ ∀x, ¬p(x). Contoh 4.18. Ingkaran dari pernyataan ∀x ∈ R, x2 ≥ 0 adalah ∃x ∈ R, x2 < 0. Contoh 4.19. Ingkaran dari pernyataan ∃x ∈ R, x2 + 1 = 0 adalah ∀x ∈ R, x2 + 1 6= 0.
30
BAB 4. LOGIKA
4.7
Argumentasi Logis
Pada bagian ini kita akan membicarakan beberapa argumentasi yang sahih, yaitu teknik menarik kesimpulan yang benar dari pernyataan-pernyataan benar yang diketahui premis tanpa menggunakan tabel kebenaran. Dengan cara ini kita mengatakan bahwa kesimpulan diturunkan dari premis. Jika kita mempunyai n premis p1 , p2 . . . , pn dan kesimpulan q, maka argumentasi p1 p2 .. . pn ∴q disebut sahih jika q benar bilamana semua premis p1 , p2 , . . . , pn benar. Karena itu, kita dapat menunjukkan bahwa p1 ∧ p2 ∧ . . . ∧ pn → q adalah sebuah tautologi karena bila p1 ∧ p2 ∧ . . . ∧ pn benar. yaitu pada saat p1 , p2 , . . . , pn semuanya benar, q harus benar. Bila terdapat pertentangan (kontradiksi) di antara premis yang ada, maka argumentasi akan benar apapun kesimpulannya. Tanda ∴ dibaca ”jadi”. Contoh 4.20. Perhatikan argumentasi berikut ini: Semua haji beragama Islam. Umar beragama Islam. ∴ Umar seorang haji. Dalam argumentasi ini kesimpulan tidak diturunkan atau bukan akibat dari kedua premis yang ada. Kesimpulan benar hanya jika ternyata Umar adalah seorang haji. Karena itu, argumentasi pada contoh ini tidak sahih. Contoh 4.21. Perhatikan argumentasi berikut ini: Semua makhluk hidup memerlukan oksigen. Kelapa adalah makhluk hidup. ∴ Kelapa memerlukan oksigen. Argumentasi ini sahih karena kesimpulan adalah akibat dari dua premis yang diberikan. Berikut adalah beberapa argumentasi logis.
4.7. ARGUMENTASI LOGIS
31
Modus Ponens p→q p ∴q
Modus Tollens p→q ¬q ∴ ¬p
Silogisme Disjungtif p∨q ¬p ∴q
Silogisme Hipotetis p→q q→r ∴p→r
Dilema p∨q p→r q→r ∴r Contoh 4.22. Periksalah apakah argumentasi berikut sahih. Jika saya belajar, maka saya akan lulus ujian. Jika saya tidak pacaran, maka saya dapat belajar. Saya tidak lulus ujian. ∴ Saya pacaran. Dengan mendefinisikan pernyataan-pernyataan p : Saya belajar, q : Saya pacaran, r : Saya lulus ujian, kita memeriksa kesahihan argumentasi di atas secara simbolis dengan cara berikut:
32
BAB 4. LOGIKA 1. 2. 3. 4. 5. 6.
p→r ¬q → p ¬r ¬r → ¬p ¬p q
∴q 1 kontraposisi 4,3 modus ponens 2,5 modus tollens
Jadi argumentasi di atas sahih. Contoh 4.23. Periksalah apakah argumentasi berikut sahih. Jika saya tamat SMA, saya akan kuliah. Jika saya bekerja, saya punya uang. Tidak mungkin saya kuliah dan punya uang. Saya tamat SMA. ∴ Saya tidak bekerja. Pertama, definisikan pernyataan-pernyataan berikut: p q r s
: : : :
Saya Saya Saya Saya
tamat SMA, kuliah, bekerja, punya uang.
Kemudian, ikuti langkah-langkah berikut: 1. 2. 3. 4. 5. 6. 7. 8.
p→q r→s ¬(q ∧ s) p q ¬q ∨ ¬s ¬s ¬r
∴ ¬r 1,4 modus ponens 3 hukum de Morgan 6,5 silogisme disjungtif 2,7 modus tollens
Jadi argumentasi di atas sahih.
4.8
Operasi Bit pada Komputer
Komputer menyimpan informasi dengan menggunakan bit yang memiliki dua nilai, yaitu satu dan nol. Kata bit berasal dari binary digit, yaitu angka yang digunakan pada representasi bilangan dalam basis dua. Barisan bit disebut bit string. Panjang sebuah bit string adalah banyaknya bit dalam barisan itu.
4.8. OPERASI BIT PADA KOMPUTER
33
Contoh 4.24. 10001101100 adalah bit string yang panjangnya sebelas. Operasi bit didefinisikan seperti operasi ∧, ∨, dan ⊕ pada pernyataan. Nilai benar diganti dengan satu dan nilai salah dengan nol. Ada tiga macam operasi bit, yaitu AN D, OR, dan XOR seperti pada Tabel 4.8. Kita mengoperasikan bit string yang sama panjang dengan cara mengoperasikan setiap bit yang bersesuaian. AND 0 1
0 1 0 0 0 1
OR 0 0 0 1 1
1 1 1
XOR 0 1 0 0 1 1 1 0
Tabel 4.8: operasi bit Contoh 4.25. Berikut ini berturut-turut operasi AND, OR, dan XOR. 11000110101 01010111100 01000110100
AN D
11000110101 01010111100 11010111101
OR
11000110101 01010111100 10010001001
XOR
Contoh 4.26. Misalkan S = {1, 2, 3, 4, 5, 6}. Himpunan A = {2, 5, 6} akan disajikan sebagai bit string 011011 dan himpunan B = {2, 3, 4, 5} sebagai bit string 011110 sesuai dengan fungsi karakteristik masing-masing himpunan. Sesuai dengan definisi, irisan himpunan adalah hasil operasi AN D dan gabungan hasil operasi OR. Jadi, A ∩ B disajikan sebagai 010011 011110 010010
AN D
sedangkan A ∪ B sebagai 010011 011110 011111
OR
Latihan 1. Tunjukkan dengan tabel kebenaran bahwa p ⊕ q ≡ (p ∨ q) ∧ ¬(p ∧ q). Bandingkah dengan Latihan 6 Bab 2. 2. Dengan tabel kebenaran tunjukkan bahwa p → q ≡ ¬p ∨ q.
34
BAB 4. LOGIKA 3. Tanpa tabel kebenaran, buktikan bahwa p → (q → r) ≡ (p∧¬r) → ¬q. 4. Buktikan bahwa ((p → q) ∧ ¬q) → ¬p adalah tautologi. 5. Ubahlah pernyataan-pernyataan berikut menjadi konversi, inversi, dan kontraposisi. (a) Jika a2 + b2 = c2 , maka a, b, c adalah sisi segitiga siku-siku. (b) Jika ab = 0, maka a = 0 atau b = 0. 6. Buatlah pernyataan yang ekivalen dengan pernyataan berikut: (a) (b) (c) (d)
Semua makhluk hidup memerlukan oksigen. Ada mahasiswa yang malas belajar. Tidak ada bilangan nyata yang kuadratnya negatif. Semua bilangan prima adalah ganjil.
7. Periksalah apakah argumentasi berikut sahih. Jika kacamataku ada di meja dapur, pasti aku telah melihatnya waktu sarapan pagi. Aku membaca koran di ruang tamu atau di dapur. Jika aku membaca koran di ruang tamu, pastilah aku meletakkan kacamataku di meja tamu. Aku tidak melihat kacamataku waktu sarapan pagi. Jika aku membaca koran di dapur, pasti kacamataku ada di meja dapur. ∴ Kacamataku ada di meja dapur. 8. Periksalah kesahihan argumentasi berikut. Di kota dia harus bekerja di kantor. Bila tidak ke kota, dia bisa bertani. Dia tidak bekerja di kantor dan tidak bertani. ∴ Dia bunuh diri. 9. Tunjukkan kesahihan argumentasi berikut: Orang yang tak pernah menepati janji tak bisa dipercaya. Orang mabuk sangat komunikatif. Orang yang selalu menetapi janji itu jujur. Orang yang tidak mabuk tidak bisa diserahi tugas. Orang yang sangat komunikatif selalu bisa dipercaya. ∴ Semua orang yang bisa diserahi tugas jujur.
Bab 5 Teknik Membilang Dalam bab ini kita akan membahas beberapa teknik membilang (counting techniques). Dalam ilmu komputer teknik-teknik ini berguna khususnya dalam menganalisis algoritma. Prinsip penjumlahan sebagai salah satu teknik membilang sudah diberikan oleh Teorema 2.2 pada Bab 2.
5.1
Prinsip Perkalian
Jika sebuah pekerjaan dapat dikerjakan dalam n1 cara dan pekerjaan lain dalam n2 cara, maka ada n1 n2 cara untuk mengerjakan kedua pekerjaan tersebut. Contoh 5.1. Misalkan ada dua jalan dari kota A ke kota B dan ada tiga jalan dari kota B ke kota C. Dengan prinsip perkalian kita dapatkan bahwa terdapat 2 × 3 = 6 jalan dari kota A ke kota C. Prinsip ini dapat diperluas hingga k pekerjaan. Misalkan terdapat k pekerjaan yang harus diselesaikan secara berurutan. Jika T1 dapat diselesaikan dalam n1 cara, T2 dapat diselesaikan dalam n2 cara, dan seterusnya hingga Tk dalan nk cara, maka terdapat k Y
ni = n1 · n2 · · · · · nk
i=1
cara menyelesaikan pekerjaan T1 , T2 , . . . , Tk . Prinsip perkalian bisa diperluas hingga k pekerjaan. Jika ada k pekerjaan Ti , i = 1, 2, . . . , k yang masing-masing dapat diselesaikan dalam ni , i = 1, 2, . . . , k, cara, maka terdapat k Y
ni = n1 n2 · · · nk
i=1
35
36
BAB 5. TEKNIK MEMBILANG
cara untuk menyelesaikan perkerjaan T1 , T2 , . . . , Tk secara berurut. Contoh 5.2. Ada 410 cara untuk menjawab sepuluh soal pilihan ganda dengan empat opsi, karena setiap soal dapat dijawab dalam 4 cara. Contoh 5.3. Misalkan A adalah sebuah himpunan dengan n elemen. Telah kita ketahui bahwa himpunan bagian dari A ditentukan oleh fungsi karakteristiknya. Jadi ada n posisi yang masing-masing dapat diisi dengan 0 atau 1. Karena untuk setiap posisi terdapat dua pilihan, maka seluruhnya terdapat 2| · 2 ·{z· · · · 2} = 2n n faktor himpunan bagian dari A.
5.2
Prinsip Sarang Merpati
Prinsip yang merupakan salah satu teknik pembuktian ini disajikan dalam teorema berikut. Teorema 5.1. Jika n merpati ditempatkan dalam m sarang dengan m < n, maka paling sedikit satu sarang yang berisi dua atau lebih merpati. Bukti. Burung merpati diberi nomor dari 1 sampai n dan sarangnya diberi nomor dari 1 sampai m. Sekarang masukkan masukkan merpati nomor 1 ke sarang nomor 1, merpati nomor 2 ke sarang nomor 2, dan seterusnya hingga merpati nomor m ke sarang nomor m sehingga masih tersisa n − m merpati yang belum mendapat sarang. Oleh karena itu, pasti ada paling tidak satu sarang yang memuat dua atau lebih merpati. Contoh 5.4. Di antara delapan orang, pasti ada dua orang yang lahir pada hari yang sama. Contoh 5.5. Dari delapan bilangan asli yang pertama, ada empat pasang yang jumlahnya sembilan, yaitu (1, 8), (2, 7), (3, 6), (4, 5). Oleh karena itu, bila lima bilangan dipilih secara sembarang dari delapan bilangan itu pasti akan terambil paling sedikit satu dari keempat pasang di atas sehingga dari lima bilangan yang dipilih itu akan terdapat paling sedikit dua bilangan yang jumlahnya 9.
5.3. PERMUTASI
37
Perlu dicatat bahwa prinsip sarang merpati ini hanya menjamin keberadaan sarang yang memuat dua atau lebih merpati, tetapi tidak untuk mengetahui sarang yang mana. Pada Contoh 5.4, prinsip sarang merpati hanya menjamin bahwa ada dua orang yang lahir pada hari yang sama, tetapi tidak menemukan hari apa. Sedangkan pada Contoh 5.5 terambilnya dua bilangan yang berjumlah 9 dijamin oleh prinsip ini, tetapi pasangan bilangan mana yang terambil tidak bisa ditentukan dengan menggunakan prinsip ini.
5.3
Permutasi
Permutasi adalah susunan berurut dari sekelompok objek. Permutasi dapat dianggap sebagai susunan yang berbeda dari elemen-elemen sebuah himpunan. Contoh 5.6. Terdapat 6 cara menuliskan himpunan A = {a, b, c}, yaitu {a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, a, b}, {c, b, a}. Misalkan himpunan A memiliki n elemen. Dari n posisi yang tersedia untuk elemen-elemen A, ada n cara mengisi posisi pertama, n−1 cara mengisi posisi kedua, dan seterusnya hingga tersisa satu cara untuk mengisi posisi ke-n. Jadi, menurut prinsip perkalian, terdapat n × (n − 1) × (n − 2) × · · · × 2 × 1 cara mengisi n posisi yang tersedia untuk elemen-elemen A. Untuk menuliskan hasil kali di atas kita menggunakan notasi n! yang dibaca ”n faktorial”. Untuk n bilangan bulat positif, n! = n × (n − 1) × (n − 2) × · · · × 2 × 1. Secara khusus, kita mendefinisikan 0! = 1. Contoh 5.7. 5! = 5 × 4 × 3 × 2 × 1 = 120. Teorema 5.2. Banyaknya permutasi dari n objek yang berbeda adalah n!. Bukti. Kita dapat membuktikan teorema ini dengan prinsip perkalian. Ada n objek untuk posisi pertama. Setelah itu tinggal n − 1 objek untuk posisi kedua, dan seterusnya hingga tinggal 1 objek untuk posisi ke-n. Jadi terdapat n × (n − 1) × (n − 2) × · · · × 2 × 1 = n! cara untuk mengisi n posisi.
38
BAB 5. TEKNIK MEMBILANG
Contoh 5.8. Ada 5! = 120 cara menyusun lima buah buku. Selanjutnya misalkan sebuah perusahaan memiliki 3 lowongan kerja yang dilamar oleh 6 pelamar. Tentu saja ada 6 pilihan untuk lowongan pertama, 5 pilihan untuk lowongan kedua, dan 4 pilihan untuk lowongan ketiga, sehingga terdapat 6 × 5 × 4 = 120 pilihan untuk mengisi ketiga lowongan kerja itu. Secara umum, bila terdapat n objek yang akan mengisi r ≤ n posisi, maka ada n objek untuk posisi pertama, n − 1 objek untuk posisi kedua, dan seterusnya hingga tersisa n − r + 1 objek untuk posisi ke-r. Menurut prinsip perkalian terdapat n Pr
= n × (n − 1) × (n − 2) × · · · × (n − r + 1)
(5.1)
cara untuk mengisi r posisi. Notasi n Pr bisa dibaca ”n permutasi r”, artinya permutasi dari n objek yang berbeda yang setiap kali diambil r. Teorema 5.3. Banyaknya permutasi dari n objek yang berbeda yang setiap kalinya diambil r adalah n! . n Pr = (n − r)! Bukti. Mengalikan (5.1) dengan (n − r)!/(n − r)! memberikan n Pr
=
n(n − 1)(n − 2) · · · (n − r + 1)(n − r) · · · 1 n! = . (n − r) · · · 1 (n − r)!
Contoh 5.9. Misalkan Bobi mempunyai sebuah rak yang dapat memuat 5 buah buku. Jika Bobi memiliki 5 buah buku, maka terdapat 5! = 120 cara untuk menyusun buku itu pada rak tersebut. Seandainya Bobi memiliki 8 buah buku, maka terdapat 8 P5 = 336 cara untuk menyusun buku pada rak tersebut. Contoh 5.10. Banyaknya permutasi dari 4 huruf a, b, c, dan d yang diambil dua-dua adalah 4!/2! = 12 seperti disajikan di bawah ini. ab ba
5.4
ac ca
ad da
bc cb
bd db
cd dc
Kombinasi
Pada Contoh 5.10 urutan dianggap penting, artinya pasangan ab dianggap berbeda dari ba, pasangan ac berbeda dari ca, dan seterusnya. Seandainya urutan dianggap tidak penting, maka pada Contoh 5.10 hanya terdapat 6
5.4. KOMBINASI
39
pilihan. Dalam hal ini kita menghitung banyak kombinasi yang mungkin ketika memilih r objek dari n objek yang berbeda. Kita menggunakan notasi µ ¶ n atau n Cr r untuk menuliskan kombinasi ini. Notasi ini bisa dibaca ”n kombinasi r”. Teorema 5.4. Banyak kombinasi n objek yang berbeda yang setiap kalinya dipilih r adalah n! . (5.2) n Cr = r!(n − r)! Bukti. n Pr dapat dipandang sebagai cara memilih r objek dari n objek yang berbeda kemudian mempermuasikan r objek itu dalam r! cara. Jadi, dengan prinsip perkalian, kita peroleh n Pr
= n Cr r! =
n! . (n − r)!
Membagi persamaan ini dengan r! memberikan persamaan (5.2). Contoh 5.11. Misalkan password sebuah komputer terdiri dari dua huruf yang diikuti oleh 3 angka. Jika pengulangan dibolehkan, maka terdapat 26 × 26 × 10 × 10 × 10 = 676.000 macam password yang dapat dibuat. Contoh 5.12. Himpunan A = {a, b, c, d} memiliki 4 C2 = 6 himpunan bagian dengan dua anggota, yaitu {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}.
Latihan 1. Tiga pasang suami istri makan bersama di sebuah sebuah meja bundar. Hitunglah berapa banyak cara menyusun tempat duduk mereka bila (a) setiap orang bebas memilih tempat duduk masing-masing. (b) setiap istri harus duduk di samping suaminya. (c) mereka dikelompokkan menurut jenis kelamin. 2. Sebuah kelas berisi 30 mahasiswa yang terdiri dari 20 puteri dan 10 putera. Dari kelas ini akan dibentuk sebuah tim bola voli puteri, sebuah tim bola voli putera dan sebuah tim bola voli campuran. Hitunglah banyaknya tim yang dapat dibentuk bila
40
BAB 5. TEKNIK MEMBILANG (a) pemain tim campuran boleh berasal dari tim putera dan tim puteri yang sudah dibentuk. (b) pemain tim campuran tidak boleh berasal dari tim putera dan tim puteri yang sudah dibentuk. (c) pemain tim campuran harus terdiri dari 2 putera dan 4 puteri dan tidak boleh berasal dari tim putera dan tim puteri yang sudah dibentuk. 3. Tentukan paling sedikit berapa orang yang perlu dikumpulkan supaya ada 3 orang yang lahir pada hari yang sama. 4. Buktikan bahwa bila enam bilangan dipilih secara acak dari himpunan {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, pasti ada paling sedikit satu pasang yang berjumlah 11. 5. Hitunglah berapa banyak cara menyusun 5 buku komputer dan 3 buku matematika bila (a) buku-buku itu disusun menurut kelompoknya. (b) buku-buku itu disusun secara acak. (c) buku komputer harus diselingi oleh buku matematika. 6. Misalkan enam buku akan dipajang pada sebuah rak. Misalkan dari 8 buku komputer dan 5 buku bahasa Inggris akan dipajang 4 buku komputer dan 2 buku bahasa Inggris dalam kelompok masing-masing. Hitunglah ada berapa macam susunan yang dapat dibuat.
Bab 6 Fungsi Dalam matematika, ilmu komputer, dan banyak aplikasi lain fungsi memainkan peranan penting. Dalam bab ini ktia akam membahas fungsi sebagai bentuk khusus dari relasi. Relasi akan dibahas secara lebih mendalam dalam Bab 7. Misalkan A dan B adalah himpunan tak kosong. Fungsi dari A ke B, f : A → B, dapat dipandang sebagai aturan atau cara memasangkan setiap elemen A dengan tepat satu elemen B. Himpunan A disebut daerah asal (domain) dari f , dan himpunan B dinamakan daerah kawan (codomain) dari f . Kawan (image) dari a ∈ A adalah b = f (a) ∈ B, seperti diagram panah pada Gambar 6.1.
A
B f
-
a.
. b = f (a)
Gambar 6.1: Fungsi Daerah hasil (range) dari f , dinotasikan sebagai Ran(f ), adalah himpunan semua elemen B yang menjadi kawan elemen A. Jadi, Ran(f ) ⊆ B. 41
42
BAB 6. FUNGSI
Seperti disebut dalam Bab 2, fungsi f : A → B dapat pula pandang sebagai himpunan bagian A × B dan ditulis pasangan berurut (a, f (a)). Contoh 6.1. Misalkan A = {1, 2, 3} dan B = {a, b, c}, maka f = {(1, a), (2, a), (3, c)} adalah fungsi, sedangkan g = {(1, a), (1, b), (3, c)} bukan fungsi karena g(1) = {a, b}. Perhatikan bahwa dalam contoh ini Ran(f ) = {a, c}.
6.1
Fungsi Kebalikan
Sebuah fungsi f : A → B dikatakan dapat dibalik bila f −1 : B → A juga merupakan fungsi.
A
B f
-
f −1 (b) = a .
. b = f (a) ¾
f −1
Gambar 6.2: Fungsi Kebalikan
Contoh 6.2. Fungsi f pada Contoh 6.1 tidak dapat dibalik karena f −1 (a) = {1, 2}.
6.2. KOMPOSISI FUNGSI
6.2
43
Komposisi Fungsi
Misalkan f : A → B dan g : B → C adalah fungsi, maka dapat ditunjukkan bahwa komposisi dari f dan g, f ◦ g, adalah fungsi dari A ke C. Jika a ∈ A dan b = f (a) ∈ B sedangkan c = g(b) ∈ C, maka (f ◦ g)(a) = g(f (a)), sehingga (f ◦ g)(a) = g(f (a)) = g(b) = c. Gambar 6.3 menyajikan komposisi fungsi dalam bentuk diagram panah f ◦g -
A
f
-
a.
B
C g
-
. b = f (a)
. c = g(b) = g(f (a))
Gambar 6.3: Komposisi Fungsi Contoh 6.3. Misalkan f, g : Z → Z dengan f (x) = x + 1 dan g(y) = y 2 . Tentukanlan f ◦ g dan g ◦ f . Jawab: (f ◦ g)(x) = g(f (x)) = g(x + 1) = (x + 1)2 = x2 + 2x + 1. dan (g ◦ f )(x) = f (g(x)) = f (x2 ) = x2 + 1. Pada umumnya, f ◦ g 6= g ◦ f .
44
BAB 6. FUNGSI
Latihan 1. Mengapa persamaan berikut bukan fungsi dari R ke R? (a) f (x) = (b) f (x) =
1 x
√
x √
(c) f (x) = ± x2 + 1 2. Dari fungsi f : R → R berikut tentukan fungsi mana yang dapat dibalik, lalu tentukan kebalikannya. (a) f (x) = x2 (b) f (x) = x − 2 (c) f (x) = x3 − 2 3. Misalkan A = {1, 2, 3, 4} dan f, g, h : A → A diberikan oleh pasangan berurut berikut: f = {(1, 2), (2, 1), (3, 1), (4, 4)} g = {(1, 2), (2, 4), (3, 1), (4, 3)} h = {(1, 2), (2, 3), (2, 1), (4, 3)} (a) Tentukan f −1 , g −1 , h−1 jika ada. (b) Tentukan f ◦ g, g ◦ h, g −1 ◦ h, g ◦ g, g ◦ f, h ◦ g, h ◦ f bila mungkin.
Bab 7 Relasi Pada bagian akhir Bab 2 telah diperkenalkan hasil kali himpunan sebagai pasangan berurut. Misalkan A dan B adalah dua buah himpunan, maka hasil kali A dan B yang ditulis dengan notasi A × B didefinisikan sebagai pasangan berurut (a, b) yang komponen pertamanya ditempati oleh elemen A dan komponen kedua oleh elemen B, yaitu A × B = {(a, b) | a ∈ A dan b ∈ B}. Relasi R antara himpunan A dan B didefinisikan sebagai himpunan bagian dari hasil kali A × B. Karena melibatkan dua himpunan relasi ini sering disebut juga relasi biner. Secara simbolis kita menulisnya sebagai R ⊆ A × B. Jika a ∈ A berelasi dengan b ∈ B, maka kita menulisnya sebagai a R b, sedangkan jika a dan b tidak berelasi, kita menggunakan notasi a 6 R b. Himpunan A disebut daerah asal (domain), dan himpunan B disebut daerah hasil (range) dari relasi R. Contoh 7.1. Misalkan A = {Amir, Budi, Cecep} adalah himpunan nama mahasiswa dan B = IF221, IF251, IF242, IF323} adalah himpunan kode mata kuliah di jurusan Teknik Informatika. Hasil kali himpunan A dan B adalah A × B = {(Amir, IF221),(Amir, IF251), (Amir,IF242),(Amir, IF323), (Budi, IF221),(Budi, IF251),(Budi, IF242),(Budi, IF323), (Cecep, IF221),(Cecep, IF251),(Cecep,IF242),(Cecep,IF323)} 45
46
BAB 7. RELASI
Misalkan R adalah relasi yang menyatakan mata kuliah yang diambil oleh mahasiswa pada semester ganjil, yaitu R = {(Amir, IF251),(Amir, IF323),(Budi, IF221), (Budi, IF323),(Cecep,IF323)} Kita dapat melihat bahwa R ⊆ A × B. Karena (Amir, IF251) ∈ R, kita dapat menuliskan Amir R IF251, tetapi (Amir, IF221) 6∈ R sehingga kita bisa menuliskan Amir 6 R IF221 Definisi 7.1. Relasi pada himpunan A adalah relasi dari A × A. Dengan kata lain, relasi pada himpunan A adalah himpunan bagian dari A × A. Contoh 7.2. Misalkan R adalah relasi pada A = {2, 3, 4, 8, 9} yang didefinisikan oleh (x, y) ∈ R jika x adalah faktor prima dari y. Jadi, R = {(2, 2), (2, 4), (2, 8), (3, 3), (3, 9)}.
7.1
Representasi Relasi
Selain dinyatakan dengan himpunan pasangan terurut, ada banyak cara lain untuk mempresentasikan relasi biner. Berikut disajikan empat cara yang lazim digunakan sebagai representasi relasi.
Diagram Panah Relasi pada Contoh 7.1 dapat disajikan sebagai diagram panah berikut. Â Â
¿
Amir . Budi .
¿
. IF221 *
. IF251
q
. IF242
q
Cecep . Á
À
. IF323 Á
Gambar 7.1: Diagram Panah
À
7.1. REPRESENTASI RELASI
47
Tabel Tabel untuk menyajikan sebuah relasi memiliki dua kolom. Kolom pertama menyatakan daerah asal dan kolom kedua daerah hasil. Contoh 7.3. Tabel berikut menyajikan relasi pada Contoh 7.1. A B Amir IF251 Amir IF323 Budi IF221 Budi IF323 Cecep IF 323
Matriks Misalkan himpunan A = {a1 , a2 , . . . , am } dan B = {b1 , b2 , . . . , bn }. Relasi R dari A ke B dapat disajikan dengan matriks Cm×n = [cij ] yang didefinisikan sebagai berikut: 1, (ai , bj ) ∈ R cij = 0 (ai , bj ) ∈ /R untuk i = 1, 2, . . . , m dan j = 1, 2, . . . , n. Contoh 7.4. Relasi pada Contoh 7.1 dapat disajikan dengan matriks berikut: 0 1 0 1 1 0 0 1 . 0 0 0 1
Graf Berarah Berbeda dengan ketiga cara di atas, graf tidak digunakan untuk menyatajikan relasi dari sebuah himpunan ke himpunan lain, tetapi graf digunakan untuk menyajikan relasi pada sebuah himpunan saja. Kita akan mempelajari graf secara lebih mendalam pada Bab 8. Contoh 7.5. Misalkan R = {(a, a), (a, b), (b, a), (b, c), (b, d), (c, a), (c, d), (d, b)} adalah sebuah relasi pada himpunan {a, b, c, d}. Relasi ini dapat disajikan dengan graf berarah berikut:
48
BAB 7. RELASI
aW.
} 6
ª c.
s. b
- .? d
Gambar 7.2: Graf Berarah
Bab 8 Pengantar Teori Graf
+
49
50
BAB 8. PENGANTAR TEORI GRAF
Bab 9 Pohon
51
52
BAB 9. POHON
Bab 10 Bilangan Bulat 10.1
Pendahuluan
Teori bilangan merupakan salah satu cabang tertua dalam matematika yang mempelahari bilangan bulat. Jenis bilangan yang paling mendasar adalah bilangan asli yang berawal dari mencacah (counting) anggota himpunan berhingga. Kita menggunakan notasi standar N = {1, 2, 3, . . .} untuk menyatakan himpunan bilangan asli. Huruf N berasal dari kata natural dalam natural numbers. Sebagian orang memasukkan angka 0 dalam himpunan bilangan asli karena himpunan kosong memiliki 0 anggota. Dalam bahasa Inggris himpunan C = {0} ∪ N sering disebut whole numbers. Di Indonesia himpunan ini disebut himpunan bilangan cacah. Kita tidak menggunakan notasi C untuk bilangan cacah karena notasi ini biasa digunakan untuk complex numbers. Selanjutnya, kita dapat menjumlahkan dan mengalikan dua atau lebih bilangan cacah dan mendapat bilangan cacah yang baru. Jadi, jika a, b ∈ C, maka a + b ∈ C dan ab ∈ C. Tentu saja kita sudah mengenal beberapa sifat kedua operasi ini, seperti a + b = b + a, ab = ba, a1 = 1a = a, 0a = a0 = 0, dan lain-lain. Kita akan kembali ke sifat-sifat ini nanti. Persamaan seperti 5 + x = 0 tidak mempunyai penyelesaian dalam himpunan bilangan cacah karena kita tidak dapat menemukan bilangan cacah 53
54
BAB 10. BILANGAN BULAT
yang bila dijumlahkan dengan 5 menghasilkan 0. Karena itu, orang memperluas himpunan bilangan cacah menjadi himpunan bilangan bulat. Notasi standar untuk bilangan bulat adalah Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .} yang berasal dari kata Jerman zahlen walaupun kata Inggris untuk bilangan bulat disebut integers. Sebagai tambahan, kita juga mengenal bilangan rasional. Bilangan x disebut rasional jika dan hanya jika x dapat dinyatakan sebagai rasio dua bilangan bulat; yaitu, jika dan hanya jika ada bilangan bulat m dan n, n 6= 0, sedemikian hingga x = m/n. Himpunan bilangan rasional biasanya dinotasikan sebagai o nm | m, n ∈ Z, n 6= 0 , Q= n yang berasal dari kta quotient (hasil bagi). Dengan mudah dapat dilihat bahwa himpunan bilangan bulat adalah himpunan bagian dari himpunan bilangan rasional, yaitu untuk n = 1. Bilangan yang bukan √ rasional disebut bilangan irassional. Contoh bilangan irasional adalah 2, π, dan bilangan Euler e. Bersama himpunan bilangan irasional Q membentuk himpunan bilangan real (bilangan nyata) R. Dalam bab ini kita akan membahas sifat-sifat bilangan bulat. Sebelumnya, akan disajikan terlebih dahulu aksioma-aksioma bilangan bulat terhadap operasi penjumlahan dan perkalian, yaitu sifat-sifat bilangan bulat yang kita anggap benar tanpa harus membuktikannya.
10.2
Aksioma Bilangan Bulat
Seperti bilangan cacah, sangatlah alamiah bila kita menganggap bahwa jumlah dan hasil kali dua bilangan bulat adalah bilangan bulat pula. Dengan kata lain, himpunan bilangan bulat tertutup terhadap operasi penjumlahan dan perkalian. Seperti biasa, kita menggunakan notasi a + b untuk jumlah dan a · b untuk hasil kali. Sesuai konvensi hasil bagi akan ditulis sebagai ab. Berikut adalah aksioma bilangan bulat terhadap operasi penjumlahan dan perkalian. 1. Tertutup. Bila a, b ∈ Z, maka a + b ∈ Z dan ab ∈ Z. 2. Komutatif. a + b = b + a dan ab = ba untuk semua a, b ∈ Z. 3. Asosiatif. (a + b) + c = a + (b + c) dan (ab)c = a(bc) untuk semua a, b, c ∈ Z.
10.2. AKSIOMA BILANGAN BULAT
55
4. Distributif. (a + b)c = ab + ac untuk semua a, b, c ∈ Z. 5. Elemen identitas. a + 0 = a dan a · 1 = a untuk semua a ∈ Z; dalam hal ini, 0 disebut elemen identitas penjumlahan dan 1 elemen identitas perkalian. 6. Invers penjumlahan. Untuk setiap a ∈ Z ada x ∈ Z sedemikian hingga a + x = 0; di sini x disebut invers penjumlahan dan biasa dibulis sebagai −a. Perhatikan bahwa bilangan bulat tidak mempunyai invers perkalian. 7. Hukun Kanselasi Perkalian. Untuk semua a, b, c, ∈ Z, jika ac = bc dengan x 6= 0, maka a = b. Selanjutnya kita mendefinisikan operasi pengurangan sebagai berikut: Definisi 10.1 (Pengurangan). Untuk semua a, b ∈ Z, a − b = a + (−b). Kita tidak mendefinisikan operasi pembagian, tetapi kita akan membahas konsep keterbagian secara lebih mendalam dalam Bab ??. Urutan bilangan bulat didefinisikan dengan menggunakan himpunan bilangan bulat positif Z+ = {1, 2, 3, . . .} sebagai berikut: Definisi 10.2 (Urutan Bilangan Bulat). Jika a, b ∈ Z, maka a dikatakan kurang dari (bukan lebih kecil dari) b jika dan hanya jika b−a adalah bilangan bulat positif; secara simbolis, a < b jika dan hanya jika b − a ∈ Z+ . Jika a < b, kita juga menulisnya sebagai b > a. Di samping definisi di atas, definisi alternatif untuk relasi ”karang dari” adalah seperti berikut: Definisi 10.3 (Kurang dari). Jika a dan b adalah bilangan bulat, maka a < b jika dan hanya jika ada c ∈ Z+ sedemikian hingga a + c = b. Perlu dicatat bahwa a adalah bilangan bulat positif jika dan hanya jika a > 0 (lihat Latihan 2). Berikut adalah sifat dasar yang berkenaan dengan urutan bilangan bulat. 1. Tertutup untuk bilangan bulat positif. Jika a, b ∈ Z+ , maka a + b ∈ Z+ dan ab ∈ Z+ . Dalam hal ini kita katakan bahwa himpunan bilangan bulat positif tertutup terhadap operasi penjumlahan dan perkalian.
56
BAB 10. BILANGAN BULAT 2. Hukum Trikotomi. Untuk setiap bilangan bulat a berlaku a < 0, a = 0, atau a > 0.
Contoh 10.1 di bawah ini menyajikan pembuktian sifat lain dari urutan bilangan bulat dapat dibuktikan dengan menggunakan aksioma di atas. Untuk sifat lain, lihat Latihan 3. Contoh 10.1. Misalkan a, b, c ∈ Z dengan a < b dan c > 0. Kita dapat menunjukkan bahwa ac < bc. Pertama, karena a < b, maka b − a > 0. Kemudian, karena bilangan bulat positif tertutup terhadap operasi perkalian, maka c(b−a) > 0. Akhirnya, sifat distributif dan komutatif melengkapi bukti kita. Sifat berikut melengkapi aksioma bilangan bulat kita. Keterurutan bilangan bulat positif (well-ordering property). Setiap himpunan bilangan bulat positif tak kosong S mempunyai elemen terkecil; yaitu, ada a ∈ S sedemikian hingga a ≤ b untuk semua b ∈ S. Dalam hal ini kita katakan bahwa himpunan S terurut (well-ordered) terhadap ≤.
10.3
Sifat-sifat Bilangan Bulat
Dalam bagian ini akan dibuktikan beberapa sifat lain dari bilangan bulat. Contoh 10.2 (Hukum Kanselasi Penjumlahan). Untuk a, b, c ∈ Z, jika a + c = b + c, maka a = b. Untuk melihat ini, kurangkan c dari kedua ruas, lalu menggunakan sifat asosiatif, kta peroleh a + 0 = b + 0. Karena sifat elemen identitas, a = b. Contoh 10.3. Untuk membuktikan bahwa 0a = 0, kita mulai dengan 0 + 0 = 0; ini berlaku karena 0 adalah elemen identitas. Mengalikan kedua ruas dengan a menghasilkan (0 + 0)a = 0a. Sifat distributif menjadikan ruas kiri 0a + 0a. Mengurangkan 0a dari kedua ruas (sama saja dengan menambahkan kedua ruas dengan invers 0a), kita mendapatkan untuk ruas kiri (0a + 0a) − 0a = 0a + (0a − 0a) = 0a + 0 = 0a, sedangkan untuk ruas kanan, 0a − 0a = 0. Jadi, 0a = 0. Proposisi 10.1 (Sifat Archimedes). Jika a dan b adalah bilangan bulat, maka ada bilangan bulat n sedemikian hingga na ≥ b. Bukti. Misalkan a dan b tidak seperti disebutkan dalam proposisi di atas. Dengan kata lain, misalkankan ada bilangan bulat positif a dan b sedemikian
10.4. LATIHAN
57
hingga na < b untuk semua n ∈ Z. Sekarang kita mendefinisikan himpunan S seperti berikut: S = {b − na|n ∈ Z+ } yang hanya berisi bilangan bulat positif. Menurut sifat keterurutan, S memiliki elemen terkecil, sebut saja b − ma untuk m ∈ Z+ . Tetapi, bilangan berikutnya, b − (m + 1)a, adalah anggota S dan b − (m + 1)a = (b − ma) − a < b − ma. Hal ini bertentangan dengan dengan pemisalan bahwa b−ma adalah anggota S yang terkecil. Jadi, untuk bilangan bulat positif a dan b harus ada bilangan bulat positif n sedemikian hingga na ≥ b. 2.
10.4
Latihan
1. Gunakan aksioma bilangan bulat untuk membuktikan bahwa pernyataanpernyataan di bawah ini benar untuk semua a, b ∈ Z: (a) a(b + c) = ab + ac (b) (a + b)2 = a2 + 2ab + b2 (c) −1a = −a (d) −(ab) = a(−b) (e) (−a)(−b) = ab 2. Buktikan bahwa a adalah bilangan bulat positif jika dan hanya jika a > 0. 3. Tunjukkan bahwa untuk sembarang a, b ∈ Z; jika a < b dan c < 0, maka ac > bx. 4. Dengan menggunakan definisi urutan bilangan bulat, buktikan bahwa jika a, b, dan c adalah bilangan bulat dengan a > b dan b > c, maka a > c. 5. Buktikan bahwa tidak ada bilangan bulat positif yang kurang dari 1.
58
BAB 10. BILANGAN BULAT
Bab 11 Induksi Matematika 11.1
Induksi Matematika
Induksi matematika adalah salah satu metode pembuktian dalam matematika. Metode ini banyak dipakai untuk membuktikan pernyataan-pernyataan yang berlaku untuk semua bilangan bulat positif. Teorema 11.1 (Prinsip Induksi Matematika). Misalkan P adalah himpunan bilangan bulat dengan sifat-sifat (i) 1 ∈ P , dan (ii) bila bilangan bulat n ∈ P , maka n + 1 juga anggota P , maka P adalah himpunan bilangan bulat positif. Bukti. Misalkan S adalah himpunan semua bilangan positif yang bukan anggota P dan anggaplah S tak kosong. Sifat keterurutan menyatakan bahwa S pasti mempunyai elemen terkecil, sebut saja a. Karena sifat (i), a > 1; akibatnya, 0 < a − 1 < a, dan a − 1 ∈ / S. Tetapi, oleh sifat (ii), (a − 1) + 1 = a ∈ P , bertentangan dengan asumsi bahwa a ∈ S. Jadi, S adalah himpunan kosong dan P adalah himpunan bilangan bulat positif. 2. Teorema 11.1 berisi dua langkah untuk membuktikan bahwa sebuah pernyataan berlaku untuk semua bilangan bulat positif. Pertama, kita harus memperlihatkan bahwa pernyataan itu berlaku untuk bilangan bulat 1. Langkah ini disebut langkah dasar. Kedua, kita harus menunjukkan bahwa untuk setiap bilangan bulat n, pernyataan itu berlaku untuk n + 1 bila pernyataan itu berlaku untuk n. Langkah ini disebut langkah induktif.
59
60
BAB 11. INDUKSI MATEMATIKA
Ilustrasi penggunaan prinsip induksi matematika diberikan dalam contohcontoh berikut. Contoh 11.1. Kita akan membuktikan bahwa n! ≤ nn untuk semua n ∈ Z+ . Untuk langkah dasar, kita dapat dengan mudah melihat bahwa ketidaksamaan ini berlaku untuk n = 1, yaitu 1! = 1 ≤ 11 = 1. Langkah selanjutnya adalah menganggap bahwa n! ≤ nn ; ini disebut hipotesis induktif. Dengan asumsi bahwa hipotesis ini benar, kita harus menunjukkan bahwa (n + 1)! ≤ (n + 1)n+1 . Untuk itu, perhatikan bahwa (n + 1)! = ≤ < <
(n + 1)n! (n + 1)nn (n + 1)(n + 1)n (n + 1)n+1
yang melengkapi langkah induktif dan bukti. Induksi matematika paling banyak dipakai untuk membuktikan rumus eksplisit untuk jumlah. Tidak jarang kita harus membuat dugaan dari beberapa suku pertama, lalu menggunakan induksi matematika untuk membuktikan dugaan itu, seperti pada contoh berikut ini. Contoh 11.2. Memperhatikan bahwa 1 =1 1+3 = 1+3+5 = 1+3+5+7 = 1+3+5+7+9 =
4 9 16 25
kita dapat memduga bahwa n X
(2j − 1) = 1 + 3 + 5 + · · · + (2n − 1) = n2 .
j=1
Mari kita coba membuktikan dugaan ini dengan induksi matematika. Langkah dasar jelas benar karena 1 X (2j − 1) = 1 = 12 . j=1
11.2. LATIHAN
61
P Untuk langkah induktif, dengan menggunakan asumsi bahwa nj=1 (2j −1) = P 2 n2 benar, kita harus menunjukkan bahwa n+1 j=1 (2j − 1) = (n + 1) . Tetapi, n+1 n X X (2j − 1) = (2j − 1) + 2(n + 1) − 1 j=1
j=1 2
= n + 2(n + 1) − 1 = n2 + 2n + 1 = (n + 1)2 Dengan selesainya kedua langkah ini, benarlah dugaan kita di atas. Teorema 11.2 (Prinsip Kedua Induksi Matematika). Sebuah himpunan bilangan bulat positif yang berisi 1 dan berisi n + 1 bila 1, 2, 3, . . . , n adalah anggota himpunan itu untuk setiap bilangan bulat positif n adalah himpunan semua bilangan bulat positif. Bukti teorema ini tidak jauh berbeda dari bukti Teorema 11.1 dan sengaja ditinggalkan sebagai latihan; lihat Latihan 2
11.2
Latihan
1. Gunakan induksi matematika untuk membuktikan bahwa (a) n < 2n , n ∈ Z+ . Pn n n+1 (b) − 2. j=1 2 = 2 Pn (c) j=1 j = n(n + 1)/2. Pn 2 (d) j=1 j = n(n + 1)(2n + 1)/6. Pn 3 2 (e) j=1 j = (n(n + 1)/2) . Pn (f) j=1 1/(j(j + 1)) = n/(n + 1). Qn k n+1 (g) k=0 22 = 22 − 1. 2. Buktikan Teorema 11.2. 3. Buktikan Teorema ??.
62
BAB 11. INDUKSI MATEMATIKA
Bab 12 Matriks
63
64
BAB 12. MATRIKS
Bab 13 Aljabar Bool
65
66
BAB 13. ALJABAR BOOL
Daftar Pustaka [1] Jong, Jek Siang. 2004. Matematika Diskrit dan Aplikasinya pada Ilmu Komputer. Yogyakarta: Penerbit Andi. [2] Lipschutz, Seymour dan M. L. Lipson. 2001. Matematika Diskrit. Jilid 1. Seri Penyelesaian Soal Schaum. Terjemahan Tim Editor Penerbit Salemba Teknika. Jakarta: Penerbit Salemba Teknika. [3] Munir, Rinaldi. 2001. Matematika Diskrit. Edisi Kedua. Bandung: Penerbit Informatika. [4] Rosen, Kenneth H. 1991. Discrete Mathematics and Its Applications. Second Edition. New York: McGraw-Hill, Inc.
67
