Soal Induksi Matematika

1. Diberikan P(n) ≡  5²ⁿ - 1 . Tunjukkan P(n) habis dibagi 8, untuk semua n ∈ N.

Penyelesaian:

Tulis:

N : himpunan bilangan asli (Natural).

Diberikan P(n) ≡  5²ⁿ - 1.

Ditunjukkan P(1) benar.

Jelas P(1) ≡  5^2.1 - 1 = 5² - 1 = 25 - 1 = 24

Jelas 24 habis dibagi 8.

Jadi P(1) benar. ... (1*)

Ditunjukkan: Jika P(k) habis dibagi 8 maka P(k + 1) habis di bagi 8. ... (#)

Dipunyai P(k) benar.

Jelas P(k) ≡  5^2k - 1  = 8m, untuk suatu m ∈ N. ... (2*)

Jelas P(k + 1) ≡ 5^2(k+1) - 1

= 5^2k+2 - 1

= 5^2k . 25 - 1

= [(5^2k - 1).25] + 24               [langkah ini merupakan kunci dari pembuktian]

= [8m.25] + 8.3                      [langkah ini sah karena berdasarkan (2*), 5^2k - 1  = 8m]
= 8 . (25m + 3)
= 8p, untuk suatu p = 25m + 3, m, p ∈ N.

Diperoleh P(k + 1) = 8p, untuk suatu p ∈ N.

Jadi P(k + 1) habis dibagi 8. ... (3*)

Dari (1*) dan (3*) disimpulkan bahwa P(n) benar untuk semua n ∈ N.

Jadi P(N) benar.
Contoh Aplikasi Induksi Matematika di sini

Teorema Phytagoras (COPAS)

pembuktian-teorema-pythagoras

Pembuktian Teorema (COPAS)

A ⊂ B ⇔ A ∩ B = A

Bukti:
(⇒) DITUNUKKAN DARI RUAS KIRI KE RUAS KANAN!
Dipunyai A ⊂ B.
Karena A ⊂ B maka ∀x∈A berlaku x∈B.
Maka berlaku x∈A ⇒ x∈B.
Karena A ⊂ B maka berlaku Bc ⊂ Ac.
Ditunjukkan A ∩ B = A.

(i) Ditunjukkan A ⊂ (A ∩ B).

Ambil sembarang x ∈ A.
Jelas berlaku x ∈ A
⇔ x ∈ A ∧ x ∈ A (menurut hukum idempoten)
⇔ x ∈ A ∧ x ∈ B (menurut definisi A ⊂ B)
⇔ x ∈ (A ∩ B) (menurut definisi irisan)
Diperoleh x ∈ A berlaku x ∈ (A ∩ B).
Karena x adalah sembarang anggota A, maka berlaku ∀x∈A maka x∈ (A ∩ B).
Jadi A ⊂ (A ∩ B).

(ii) Ditunjukkan (A ∩ B) ⊂ A.

Jelas Ac ⊂ (Ac ∪ Bc)
⇔ Ac ⊂ (A ∩ B)c
⇔ (A ∩ B) ⊂ A (menurut sifat komplemen)
Dari (i) dan (ii) diperoleh fakta bahwa (A ∩ B) = A jika A ⊂ B.
Jadi (⇒) berlaku.

(⇐) DITUNJUKKAN DARI RUAS KANAN KE RUAS KIRI!
Dipunyai (A ∩ B) = A. Ditunjukkan A ⊂ B.
Akan ditunjukkan melalui kontraposisinya yang benar, yaitu A ⊄ B ⇒ A ∩ B ≠ A.
Cukup ditunjukkan bahwa (A∩B) ⊄ A atau A ⊄ (A∩B).
Jelas bahwa (A∩B) ⊂ A. Jadi ditunjukkan A ⊄ (A∩B).
Dipunyai A ⊄ B.
Artinya ∃x1∈A namun x1∉B.
Jelas x1∉ (A∩B).
Jadi ∃x1∈A namun x1∉A∩B.
Jadi A⊄ (A∩B).
Jadi jika A ⊄ B maka A ∩ B ≠ A.
Artinya jika A∩B = A maka A⊂B.

Dari penjelasan diatas dapat disimpulkan bahwa A⊂B ⇔ A∩B = A.

SET OPERATIONS

We know define basic methods of constructing new sets from given ones.
Definition
(a) If A and B are sets, then their intersection, denote by A∩B, is the set of all elements that belong to both A and B. In other words, we have

A∩B={x : x∈A and x∈B}

(b) The union of A and B, denoted by A∪B, is the set of all elements that belong to either A or B. In other words, we have

A∪B={x : x∈A or x∈B}

In connection with the union of two sets, it is important to be aware of the fact that the word "or" is being used in the inclusive sense. To say x belongs to A or B allows the possibility that x belongs to both sets. In legal terminology this inclusive sense is sometimes indicated by "and/or"
Definition
the set that has no elements is called the empty or the void set and will be denoted by the symbol ∅. If A and B one sets with no elements (that is, if A∩B=∅), then we say that A and B are disjoint or that thay are nonintersecting.
Theorem
Let A, B, C be any sets then
(a) A∩A=A, A∪A=A,
(b) A∩B=B∩A, A∪B=B∪A,
(c) (A∩B)∩C=A∩(B∩C),
      (A∪B)∪C=A∪(B∪C),
(d) A∩(B∪C)=(A∩B)∪(A∩C),
      A∪(B∩C)=(A∪B)∩(A∪C)


Buktikan A∩A=A
Untuk membuktikan A∩A=A diperlukan langkah sbb.
(i) Ditunjukkan A∩A⊆A
(ii) Ditunjukkan A⊆A∩A
Penyelesaian:
(i) Ditunjukkan A∩A⊆A

     Ambil sembarang x∈A∩A akan ditunjukkan x∈A

     Jelas  x∈A∩A

SET

If A denotes as a set and if x is an element, we shall write.

x∈A

as an abbreviation for the statement that x is an element of A, or that x is a member of A, or that x belongs to A, or that the set A contains the element x, or that x is in A. If x is an element that does not belong to A, we shall write.

x∉A

If A and B are sets such that x∈A implies that x∈B (that is every element of A is also an element of B), then we shall say that A is contained in B, or that B contains A, or that A is a subset of B, and we shall write.

A⊆B or B⊇A

Definition, two sets A and B are equal if they contain the same element. If the sets A and B are equal, we write A=B

Examples:

(a) The set {x∈N : x²‒3x+2=0}

consists of those natural numbers satisfying the stated equation since the only solutions of the quadratic equation x²‒3x+2=0 are x=1 and x=2, instead of writing the above expression we ordinarily denoted this set by {1,2}, thereby l;isting the elements of the set.

(b) Sometimes of formula can be used to abbreviate the description of a set. For example, the set of all even natural numbers could be denoted by {2x : x∈N}, instead of the more cumbersome {y∈N : y=2x, x∈N}

(c) The set {x∈N : 6<x<9} can be written explicitly as {7,8}, thereby exhibiting the elements of the set. Of course, there are many other possible description of this set, for example:

{x∈N : 40<x²<80}

{x∈N : x²‒15x+56=0}

{7+x : x=0 or x=1}

Exercise 2

Tentukan invers, konvers, dan kontraposisi dari proposisi berikut ini:

1. Jika hasil produksi melimpah maka harganya turun.

    invers            : Jika hasil produksi sedikit maka harganya naik.

    konvers         : Jika harga turun maka hasil produksi melimpah.

    kontraposisi  : Jika harga naik maka hasil produksi sedikit.

2. Jika lapangan pekerjaan tidak banyak maka pengangguran meningkat.

    invers            : Jika lapangan pekerjaan banyak maka pengangguran menurun.

    konvers         : Jika pengangguran meningkat maka lapangan pekerjaan tidak banyak.

    kontraposisi  : Jika pengangguran menurun maka lapangan pekerjaan banyak.

3. Jika ABCD bujur sangkar maka ABCD segi empat.

    invers            : Jika ABCD bukan bujur sangkar maka ABCD bukan segi empat.

    konvers         : Jika ABCD segi empat maka ABCD bujur sangkar.

    kontraposisi  : Jika ABCD bukan segi empat maka ABCD bukan bujur sangkar.

4. Jika x > 10 maka x² > 100

    invers            : Jika x ≤ 10 maka x² ≤ 100

    konvers         : Jika x² > 100 maka x > 10

    kontraposisi  : Jika x² ≤ 100 maka x ≤ 10

5. Jika x² – 16 = 0 , maka x = 4 atau x = – 4.

    invers            : Jika x² – 16 ≠ 0, maka x ≠ 4 dan x ≠ – 4.

    konvers         : Jika x = 4 atau x = – 4, maka x² – 16 = 0.

    kontraposisi  : Jika x ≠ 4 dan x ≠ – 4, maka x² – 16 ≠ 0.

6. Jika sin x = 90^o – cos x, maka x merupakan sudut lancip.

    invers            : Jika sin x ≠ 90^o – cos x, maka x bukan sudut lancip.

    konvers         : Jika x merupakan sudut lancip, maka sin x = 90^o – cos x.

    kontraposisi  : Jika x bukan sudut lancip, maka sin x ≠ 90^o – cos x.

7. Jika tan x = –1, maka x = 135^o dan x = 315^o

    invers            : Jika tan x ≠ – 1, maka x ≠ 135^o atau x ≠ 315^o

    konvers         : Jika x = 135^o dan x = 315^o, maka tan x = –1

    kontraposisi  : Jika x ≠ 135^o atau x ≠ 315^o, maka tan x ≠ – 1

Exercise 1

Tentukan invers, konvers, dan kontraposisi dari proposisi berikut ini:

1. (p ∧ q) ⇒ r

    invers            : ~(p ∧ q) ⇒ ~r ek (~p ∨ ~q) ⇒ ~r

    konvers         : r ⇒ (p ∧ q)

    kontraposisi  : ~r ⇒ ~(p ∧ q) ek ~r ⇒ (~p ∨ ~q)

2. p ⇒ (q ∧ r)

    invers            : ~p ⇒ ~(q ∧ r) ek ~p ⇒ (~q ∨ ~r)

    konvers         : (q ∧ r) ⇒ p

    kontraposisi  : ~(q ∧ r) ⇒ ~p ek (~q ∨ ~r) ⇒ ~p

3. ~p ⇒ (q ∧ ~r)

    invers            : ~(~p) ⇒ ~(q ∧ ~r) ek p ⇒ (~q ∨ r)

    konvers         : (q ∧ ~r) ⇒ ~p

    kontraposisi  : ~(q ∧ ~r) ⇒ ~(~p) ek (~q ∨ r) ⇒ p

4. (p ∨ ~q) ⇒ (q ∧ r)

    invers            : ~(p ∨ ~q) ⇒ ~(q ∧ r) ek (~p ∧ q) ⇒ (~q ∨ ~r)

    konvers         : (q ∧ r) ⇒ (p ∨ ~q)  

    kontraposisi  : ~(q ∧ r) ⇒ ~(p ∨ ~q) ek (~q ∨ ~r) (~p ∧ q) 

 5. (~q ∧ ~r) ⇒ (~p ∨ q)

    invers            : ~(~q ∧ ~r) ⇒ ~(~p ∨ q) ek (q ∨ r) ⇒ (p ∧ ~q)

    konvers         : (~p ∨ q) ⇒ (~q ∧ ~r)

    kontraposisi  : ~(~p ∨ q) ⇒ ~(~q ∧ ~r) ek (p ∧ ~q) ⇒ (q ∨ r)

 6. (q ∨ ~r) ⇒ (p ∧ r)

    invers            : ~(q ∨ ~r) ⇒ ~(p ∧ r) ek (~q ∧ r) ⇒ (~p ∨ ~r)

    konvers         : (p ∧ r) ⇒ (q ∨ ~r)

    kontraposisi  : ~(p ∧ r) ⇒ ~(q ∨ ~r) ek (~p ∨ ~r) ⇒ (~q ∧ r)