RUMUS-RUMUS TAUTOLOGI (Minggu ke-5 dan 6)
1
1
Rumus-rumus tautologi
Rumus 1.1 (Komutatif )
1. p ∧ q ⇐⇒ q ∧ p 2. p ∨ q ⇐⇒ q ∨ p
Bukti: p
q p∧q q∧p
T T F F
T F T F
T ←→ T F ←→ F F ←→ F F ←→ F
2
Rumus 1.2 (Distributif ) 1. p ∧ (q ∨ r) ⇐⇒ (p ∧ q) ∨ (p ∧ r)
2. p ∨ (q ∧ r) ⇐⇒ (p ∨ q) ∧ (p ∨ r)
Bukti: Untuk 1. p
q
r q ∧ r p ∨ (q ∧ r) (p ∨ q) ∧ (p ∨ r) p ∨ q p ∨ r
T T T T F F F
T T F F T T F
T F T F T F F
T T T T T F F
T T T T T F F
←→ ←→ ←→ ←→ ←→ ←→ ←→
3
T T T T T F F
T T T T T T F
T T T T T F F
Rumus 1.3 1. p ∧ T ⇐⇒ T ∧ p ⇐⇒ p 2. p ∧ F ⇐⇒ F ∧ p ⇐⇒ F
3. p ∨ F ⇐⇒ F ∨ p ⇐⇒ p 4. p ∨ T ⇐⇒ T ∨ p ⇐⇒ T
Rumus 1.4 1. p ∨ p¯ ⇐⇒ T
2. p ∧ p¯ ⇐⇒ F
Rumus 1.5 (Assosiatif ) 1. p ∧ (q ∧ r) ⇐⇒ (p ∧ q) ∧ r
2. p ∨ (q ∨ r) ⇐⇒ (p ∨ q) ∨ r
Rumus 1.6 (Identitas, negasi rangkap dan idempoten) 1. p ⇐⇒ p 2. p¯ ⇐⇒ p
3. p ∧ p ⇐⇒ p 4. p ∨ p ⇐⇒ p
4
Rumus 1.7 Hukum De Morgan 1. p ∧ q ⇐⇒ (¯ p ∨ q¯) 2. p ∨ q ⇐⇒ (¯ p ∧ q¯). Bukti: Untuk 1. p
q p∧q p∧q
T T F F
T F T F
T F F F
F T T T
5
p¯ ∨ q¯ p¯ q¯ F T T T
F F T T
F T F T
Rumus 1.8 1. p =⇒ q ⇐⇒ (p ∧ q¯)
2. p ⇐⇒ q ⇐⇒ ((p ∧ q¯) ∨ (¯ p =⇒ q)).
Rumus 1.9 1. (T =⇒ p) ⇐⇒ p 2. (F =⇒ p) ⇐⇒ T
3. (p ⇐⇒ T ) ⇐⇒ p 4. (p ⇐⇒ F ) ⇐⇒ p¯
Rumus 1.10 Hubungan implikasi dan biimplikasi dengan negasi, konjungsi dan disjungsi 1. (p =⇒ q) ⇐⇒ (¯ p ∨ q)
3. (p =⇒ q) ⇐⇒ ((¯ p ∨ q) ∧ (p ∨ q¯)
2. (p =⇒ q) ⇐⇒ p ∧ q¯
4. (p ⇐⇒ q) ⇐⇒ ((p ∧ q) ∨ (¯ p ∧ q¯)
6
Rumus 1.11
1.
(p ⇐⇒ q) ⇐⇒ ((p =⇒ q) ∧ (q =⇒ p))
2. ((p =⇒ q) ∧ (q =⇒ r)) ⇐⇒ (p =⇒ r). (Sifat Transitif )
Rumus 1.12 1. (p =⇒ (q =⇒ r)) ⇐⇒ (q =⇒ (p =⇒ r)) 2. (p =⇒ (q =⇒ r)) ⇐⇒ ((p ∧ q) =⇒ r).
7
Bukti Tautologi Menggunakan Tautologi Elementer (p =⇒ (q =⇒ r)) ⇐⇒ (q =⇒ (p =⇒ r)) Bukti: (p =⇒ (q =⇒ r)) ⇐⇒
p¯ ∨ (¯ q ∨ r) ⇕
(¯ q ∨ p¯) ∨ r)
⇐⇒
(¯ p ∨ q¯) ∨ r)
⇕ q¯ ∨ (¯ p ∨ r)
⇐⇒ (q =⇒ (p =⇒ r))
8
Latihan Buktikan, bahwa rumus-rumus di atas merupakan tautologi dengan menggunakan pengisian tabel. Jika mungkin buktikan juga tanpa menggunakan pengisian tabel.
9
2
Metode Pembuktian
Tiga hukum penting tautologi yang digunakan sebagai metode pembuktian: 1. Modus Ponens 2. Hukum Kontraposisi 3. Reductio ad absurdum. Modus ponens merupakan bukti secara langsung. Sedangkan kontraposisi dan reductio ad absurdum merupakan bukti tidak langsung. Pembuktian suatu teori lebih diutamakan menggunakan bukti secara langsung.
10
2.1
Modus Ponens
Rumus 2.1
(p ∧ (p =⇒ q)) =⇒ q.
Ilustrasi: α =⇒ β α β
T Terjadi Berlaku
Contoh 2.1 Buktikan, bahwa salah satu titik potong grafik fungsi dengan persamaan y = f (x) = 3x3 − 3x2 − 1 terhadap sumbu X berada di interval [1, 2].
11
Penyelesaian: Di dalam kalkulus berlaku sifat (implikasi) jika f kontinu pada interval [a, b], dan berlaku f (a) dan f (b) berbeda tanda, maka dapat ditemukan c ∈ [a, b] yang memenuhi f (c) = 0. Jadi implikasi ini bernilai benar. Fungsi y = f (x) = 3x3 − 3x2 − 1 kontinu pada [1, 2] dan f (1) < 0 serta f (2) > 0. Jadi anteseden implikasi terjadi, maka dapat disimpulkan terdapat xo ∈ [1, 2] yang berakibat f (x0 ) = 3x30 − 3x20 − 1 = 0 Jadi salah satu titik potong grafik fungsi f terhadap sumbu X berada di interval [1, 2].
12
2.2
Hukum Kontraposisi
Rumus 2.2
(p =⇒ q) ⇐⇒ (¯ q =⇒ p¯).
Ilustrasi: α =⇒ β β¯ α ¯
T Terjadi Berlaku
Contoh 2.2 Buktikan, bahwa jika 1 + (−1)n ̸= 0, maka n genap. Penyelesaian: Ingkaran n genap adalah n ganjil. Akibatnya (−1)n = −1, sehingga 1 + (−1)n = 0 yang merupakan ingkaran dari 1 + (−1)n ̸= 0. Jadi kontraposisinya dapat dibuktikan, sehingga kalimat aslinya secara tidak langsung juga terbukti.
13
2.3
Reductio ad absurdum
Rumus-rumus tautologi yang merupakan bentuk-bentuk reductio ad absurdum: Rumus 2.3
(¯ p =⇒ (q ∧ q¯)) =⇒ p. α =⇒ (β ∧ β) =⇒ α Benar : Tautologi α =⇒ (β ∧ β)
Diturunkan dari ”α” α T : Modus Ponens
Contoh √ Buktikan, bahwa 2 bilangan irrasional.
14
Bukti: √ Yang akan dibuktikan pernyataan P : 2 bilangan irrasional. Diandaikan P¯ √ berlaku, Dengan kata lain 2 bilangan rasional. Di Q berlaku sifat untuk setiap bilangan rasional r dapat dinyatakan dengan r=
m , n
dengan m dan n bilangan bulat, n ̸= 0 √ dan (m, n) yaitu faktor persekutuan √ terbesar dari m dan n sama dengan 1. 2 bilangan rasional, maka 2 = m n, untuk suatu bilangan bulat m dan n dengan n ̸= 0 dan (m, n) = 1 (Modus ponen), sehingga √ 2n2 = ( 2n)2 = m2 = mm. Sesuai modus ponen dapat disimpulkan, m = 2c, dengan c bilangan bulat. Akibatnya 2n2 = (2c)(2c) dan sesuai sifat kanselasi berlaku nn = n2 = 2c2 , sehingga n = 2d untuk suatu bilangan bulat d. Akbiatnya √ (m, n) ≥ ¯ 2, kontradiksi (m, n) = 1 dan (m, n) ≥ 2. Yang benar P : 2 bilangan irrasional.
15
Rumus 2.4
(¯ p =⇒ p) =⇒ p.
Ilustrasi: (α =⇒ α) =⇒ α Benar : Tautologi α =⇒ α
”α” diturunkan dari ”α” α T : Modus Ponens
Contoh: Di dalam himpunan semua bilangan bulat notasi (x1 , x2 , · · · , xn ) adalah simbol faktor persekutuan terbesar dari x1 , x2 , · · · , xn . Buktikan, bahwa (x, y) = (y, z) = (x, z) = 1 =⇒ (x, y, z) = 1.
16
Bukti: Andaikan (x, y, z) > 1. Karena (x, y, z) faktor persekutuan x, y dan z, maka (x, y, z)|x dan (x, y, z)|y, sehingga (x, y, z) ≤ (x, y). Akibatnya 1 < (x, y) dan terjadi kontradiksi dengan (x, y) = 1. Jadi disimpulkan (x, y, z) = 1
Contoh: Di dalam semesta himpunan semua bilangan bulat berlaku sifat jika z bilangan prima dan z|ab, dengan a dan b keduanya bulat, maka z|a atau z|b. Buktikan, bahwa jika z|bn dengan n bulat positif, maka z|b. Bukti: Andaikan z ̸ |b. Karena z|bbn−1 , maka sesuai sifat bilangan prima z|b atau z|bn−1 . Oleh karena z ̸ |b, maka z|bn−1 , dan bn−1 = bbn−2 . Jadi z|bn−2 , z|bn−3 , dan seterusnya. Pada akhirnya z|b, sehingga dapat disimpulkan z|b.
17
Rumus 2.5
((p ∧ q¯) =⇒ q) =⇒ (p =⇒ q).
Ilustrasi: ((α ∧ β) =⇒ β) =⇒ (α =⇒ β) T : Tautologi T : ”β” diturunkan dari ”α ∧ β”
(α =⇒ β) =⇒ β α =⇒ β
T : Modus Ponens
Contoh: Dengan semesta pembicaraan himpunan semua bilangan real, buktikan bahwa jika untuk setiap ϵ ≥ 0 berlaku a ≤ b + ϵ, maka a ≤ b.
18
Bukti: Misalkan α : Untuk setiap ϵ ≥ 0 berlaku a ≤ b + ϵ, dan β : a ≤ b, sehingga yang akan dibuktikan adalah implikasi ”α =⇒ β”. Diandaikan α =⇒ β berlaku. Jadi α ∧ β terjadi, yaitu berlaku untuk setiap ϵ ≥ 0 memenuhi a ≤ b + ϵ, tetapi a > b. Akibatnya a − b > 0. Dipilih ϵ yang sama dengan a−b 2 , maka ϵ > 0 dan a≤b+ϵ=b+
a−b . 2
Akibatnya 2a ≤ 2b + (a − b), sehingga a ≤ b, yaitu terbukti ”β”. Sesuai tautologi tebuktilah ”α =⇒ β”.
19
Rumus 2.6
((p ∧ q¯) =⇒ p¯) =⇒ (p =⇒ q).
Ilustrasi: ((α ∧ β) =⇒ α) =⇒ (α =⇒ β) T : Tautologi T : ”α” diturunkan dari ”α ∧ β”
(α =⇒ β) =⇒ α α =⇒ β
T : Modus Ponens
Contoh: Buktikan, bahwa jika a dan b bilangan real positif, maka √ 1 (a + b) ≥ ab. 2
20
Penyelesaian: Bukti tidak langsung : Misalkan √ α : a dan b positif, dan β : 21 (a + b) ≥ ab. Berarti yang harus dibuktikan adalah ”α =⇒ β”. Diandaikan ingkaran ”α =⇒ β”, yaitu ”α ∧ β” terjadi. Maka √ a dan b positif, tetapi 12 (a + b) < ab. Akibatnya 14 (a2 + 2ab + b2 ) = 14 (a + b)2 < ab, sehingga a2 + 2ab + b2 < 4ab. Jadi (a − b)2 = a2 − 2ab + b2 < 0, yang berarti a kompleks atau b kompleks, yaitu ingkaran dari a dan b real positif, sehingga terbukti ”α =⇒ β”.
21
Rumus 2.7
p¯ =⇒ (p =⇒ q).
Dari tautologi ini dapat ditarik kesimpulan, bahwa dari sesuatu yang salah dengan langkah yang sahih pernyataan apapun dapat dibuktikan (Ex falso sequitur quod libet). Ilustrasi:
α =⇒ (α =⇒ β) T : Tautologi α
T : Karena ketentuan α =⇒ β
T : Modus Ponens
α
T : Karena ketentuan β
T : Modus ponens
22
Latihan 1. Buktikan, bahwa bentuk-bentuk berikut merupakan tautologi, jika mungkin tanpa menggunakan tabel. 1.1 1.2 1.3 1.4 1.5
p =⇒ ((p =⇒ q) =⇒ q)) p =⇒ ((p ∨ q) =⇒ q) Modus tollendo ponens ((p ∧ q) =⇒ r) ⇐⇒ ((r ∧ q) =⇒ p) ((p =⇒ q) ∧ (r =⇒ s)) =⇒ ((p ∧ r) =⇒ (q ∧ s)) (p =⇒ q) =⇒ (q ∧ r =⇒ r ∧ p)
2. Buktikan secara langsung maupun dengan reductio ad absurdum, bahwa banyaknya bilangan-bilangan prima adalah tak berhingga. 3. Buktikan, bahwa jika 12 (1 + (−1)n ) ganjil, maka n genap. √ 4. Buktikan, bahwa jika p bilangan prima, maka p merupakan irrasional. 5. Diketahui segitiga sama sisi ABC dengan panjang sisi 1 terletak pada bujur sangkar AP QR, yaitu B terletak pada P Q dan C pada QR. Buktikan, bahwa luas segitiga BQC sama dengan jumlah luas segitiga AP B dan ARC. 6. Buktikan dengan reductio ad absurdum, bahwa akar-akar persamaan 23
xn + a1 xn−1 + · · · + an−1 x + an = 0 bernilai bulat atau irrsional. 7. Tunjukkan, bahwa di dalam himpunan semua bilangan bulat pernyataanpernyataan berikut ekuivalen 1. (x, y, z) = 1 2. (x, z) = 1 3. (y, z) = 1
4. (x, y) = 1 5. (x, y) = (y, z) = (x, z) = 1.
8. Dengan menggunakan pengetahuan di mata kuliah kalkulus buktikan, bahwa perpotongan grafik fungsi dengan persamaan y = 3x3 − 3x2 − 1 terhadap sumbu X hanya ada tepat satu titik. 9. Buktikan secara langsung maupun dengan reduction ad absurdum, bahwa jika n bulat dan n2 habis dibagi 2, maka n juga habis dibagi 2. 10. Misalkan diketahui αi , dengan i = 1, · · · , n adalah penyataan-pernyataan. Tunjukkan, bahwa untuk membuktikan α1 ⇐⇒ α2 ⇐⇒ · · · ⇐⇒ αn cukup dibuktikan α1 =⇒ α2 =⇒ · · · =⇒ αn =⇒ α1 24
11. Diberikan 80 koin mata uang, terdiri dari 79 koin asli dengan bobot sama dan 1 koin palsu dengan bobot lebih berat. Dengan menggunakan timba- ngan berlengan sama, tentukan jumlah minimal banyaknya penimbangan dan bagaimana cara menimbangnya agar akhirnya diketahui koin yang palsu. 12. Lima buah kartu yaitu: A, B, C, D, E akan diberi nomor dari 0, 1, 2, 3 atau 4 tanpa ada yang sama dan dimulai dari kartu paling kiri, A. Misalnya A diberi nomor k. Kemudian kartu paling kanan diletakkan disebelah kiri kartu paling kiri, berturut-turut E, D dan seterusnya sampai sebanyak 4 − k kartu. Kemudian kartu paling kiri diberi nomor l, yaitu satu di antara 0, 1, 2, 3, 4 selain k; selanjutnya secara berurutan dari kartu paling kanan, 4 − l kartu dipindahkan ke sebelah kiri kartu yang paling kiri. Jika proses dilanjutkan dengan cara tersebut tunjukkan, bahwa langkah penomoran akan gagal.
25
