- OBESRVASI TENTANG PEMBUKTIAN
- Pembuktian pernyataan yang berhubungan dengan definisi => harus dikembalikan pada aksioma-aksioma pada definisi.
- Pembuktian pernyataan yang bukan teorema => ditunjukkan dengan counter example.
- Pembuktian dengan kontradiksi (diandaikan lebih dulu).
- Pembuktian teorema (jika ... maka ...) => membuktikan dengan menggunakan metode deduktif, jangan membuktikan dengan memberikan contoh-contoh khusus.
- Pembuktian ketunggalan => menggunakan kontradiksi.
Partisi adalah dekomposisi suatu himpunan ke dalam sel-sel yang saling asing dan jika digabungkan akan menjadi himpunan semula.
Contoh:
- Himpunan bilangan bulat, dapat dipartisi menjadi 2, yaitu himpunan bilangan bulat genap dan ganjil
- Dalam 1 kelas (dimana kelas menyatakan himpunan), terpartisi menjadi 2, yaitu laki-laki dan perempuan.
Suatu relasi antara 2 anggota himpunan yang memenuhi 3 aksioma sebagai berikut:
- Refleksif (a ~ a)
- Simetri (a ~ b => b ~ a)
- Transitif (a ~ b dan b ~ c => a ~ c)
Contoh:
Dalam R, x ~ y jika |x| = |y|.
Bukti.
- Ambil sebarang x ϵ R maka |x| = |x| berarti x ~ x, ∀x ϵ R (refleksif)
- Ambil sebarang x, y ϵ R sehingga |x| = |y| maka |y| = |x|. Berarti jika x ~ y maka y ~ x (simetri)
- Ambil sebarang x,y, z ϵ R
x ~ y maka |x| = |y| ... (1)
y ~ z maka |y| = |z| ... (2)
Persamaan (1) disubtitusi ke persamaan (2) menjadi :
|x| = |z| sehingga x ~ z.
Jadi, ∀x, y, z ϵ R maka (x ~ y) dan (y ~ z) maka x ~ z (transitif).
Karena ketiga aksioma dipenuhi, maka pernyataan diatas benar(terbukti).
Operasi biner pada suatu himpunan adalah suatu relasi yang memasangkan setiap 2 anggota tersebut dengan sebuah anggota himpunan.
Misal :
Pada himpunan S
(a, b) ϵ S^2 dan c ϵ S^2
sehingga (a,b) -> c
Operasi biner (*) memiliki syarat yang harus dipenuhi dalam himpunan S. Kedua aksioma tersebut :
- Tertutup : ∀a, b ϵ S maka a * b = c ϵ S.
- Tunggal hasil : ∀a, b ϵ S, ada c! sehingga a * b = c
Jadi, operasi biner (*) dapat dikatakan merupakan suatu fungsi *: (s x s) => S
Contoh :
1. Operasi penjumlahan pada Z.
(1, 3) -> 4 (1 + 3 =4)
2. M adalah himpunan semua matriks. Didefinisikan sebagai operasi "*", yaitu operasi penjumlahan matriks bukan operasi biner.
Grup adalah suatu sistem struktur aljabar yang memenuhi 4 aksioma dan terdiri dari suatu himpunan tak kosong [G,*]
- Tertutup => ∀a, b ϵ G, maka a*b = c ϵ G
- Asosiatif => ∀a,b,c ϵ G maka a*(b*c) = (a*b)*c
- Mempunyai elemen identitas terhadap * => ∀a ϵ G, ∃e ϵ G sehingga a*e = e*a = a
- Setiap elemen di G punya invers => ∀a ϵ G, ∃a' ϵ G sehingga a*a' = a'*a = e , dimana a' disebut invers dari a.
Contoh :
1. Buktikan [Z, +] merupakan grup !
Jawab : Z disini merupakan himpunan bilangan bulat, maka penuhi 4 aksioma :
a. Tertutup
Ambil sebarang a, b ϵ Z, sehingga a+b ϵ Z (terbukti)
b. Asosiatif terhadap penjumlahan
Ambil sebarang a, b, c ϵ Z sehingga a+(b+c) = a+b+c = (a+b)+c (terbukti)
c. Mempunyai elemen identitas terhadap penjumlahan, yaitu 0.
Ambil sebarang a ϵ Z, maka ada 0 ϵ Z sehingga a+0 = 0+a = a. Maka terbukti memiliki elemen identitas yaitu 0.
d. Setiap elemen punya invers.
Ambil sebarang a ϵ Z, maka ada -(a) ϵ Zsehingga a+(-(a)) = (-(a))+a = 0 (terbukti)
Dari a, b, c, dan d, terbukti bahwa Z merupakan grup.
1. Jika [G, *] adalah grup, maka berlaku
Hukum Kanselasi, yaitu (i) x*y = x*z => y = z dan (ii) x*y = y*z => x = z, untuk∀x, y, z ϵ G.
Bukti.
(i) ambil sebarang x, y, z ϵ G sehingga
x*y = x*z
x' * (x*y) = x' * (x*z)
(x' * x)*y = (x' * x)*z
e*y = e*z
y = z
(ii) ambil sebarang x, y, z ϵ G sehingga
x*y = z*y
(x*y)*y' = (z*y)*y'
x*(y * y') = z*(y * y')
x * e = z*e
x = z
2. Jika [G, *] adalah grup, maka persamaannya : (i) a*x = b; (ii) x*a = b
Bukti.
# Akan ditunjukkan [G, *] mempunyai penyelesaian.
Ambil sebarang a, x, b ϵ G sehingga
a * x = b
a' * (a * x) = a' * b
(a' * a) * x = a' * b
e * x = a' * b
x = a' *b <= solusi
#Akan ditunukkan ketunggalan solusi.
Andaikan untuk sebarang a, x, b ϵ G sehingga a * x = b, ada 2 penyelesaian (tidak tunggal).
Misalkan ada 2 penyelesaian x1 tidak sama dengan x2 ϵ G sehingga
a * x1 = b
a * x2 = b
Dari 2 persamaan diatas a * x1 = a * x2 <=> x1= x2 (Hukum Kanselasi)
Terjadi kontradiksi bahwa ada 2 penyelesaian sehingga pengandaian di atas salah. Yang benar adalah hanya penyelesaian tunggal.
3. Jika [G, *] adalah grup dan a ϵ G adalah elemen identitas G maka e tunggal.
Bukti.
Andaikan tidak tunggal, misal e1 dan e2 dimana e1 tidak sama dengan e2 adalah elemen identitas.
Misal a ϵ G => a*e1 = a dan a*e2 = a
a*e1 = a*e2
e1 = e2 ..... (Hukum Kanselasi)
terjadi kontradiksi (pengandaian salah). Yang benar e itu tunggal.
4. Jika [G, *] adalah grup, maka ∀a ϵ G, (a')' = a.
Bukti.
Misalkan invers dari a adalah b (a' = b) sehingga (a*b) = (b*a) = e
padahal
(a*b) = (b' * a')
(a*b)(b' * a') = a * e * a'
= a*a'
e = b' * a'
e = b' * a'
e * a = (b' * a')*a
a = b' * (a' * a)
a = b' * e
a = b'
a = (a')' terbukti.
Misalkan G adalah grup, H adalah subset (himpunan bagian) tak nol dari G, maka H disebut subgrup G, ditulis H ≤ G. Jika H merupakan grup terhadap operasi pada G.
Jadi, jika kita ingin membuktikan H subgrup G, maka kita buktikan bahwa H merupakan Grup (penuhi 4aksioma diatas).
- DEFINISI ORDER ELEMEN GRUP
Misalkan G adalah grup dan a ϵ G, n adalah order a, ditulis
n = O(a) jika dan hanya jika n bilangan bulat positif terkecil sehingga a^n = e
^ atau pangkat => dilakukan dengan operasi penjumlahan. Misal: 1^5 = 1+1+1+1+1 = 5
Contoh:
Z6 = {0, 1, 2, 3, 4, 5}
1+1+1+1+1+1 = 0 <=> 1^6 = 0 <=> O(1) = 6
2+2+2 = 0 <=> 2^3 = 0 <=> O(2) = 3
3+3 = 0 <=> 3^2 = 0 <=> O(3) = 2
4+4+4 = 0 <=> 4^3 = 0 <=> O(4) = 3
5+5+5+5+5+5 = 0 <=> 5^6 = 0 <=> O(5) = 6
Teorema. Misalkan G grup, a ϵ G dan O(a) = n, maka ada n variasi perpangkatan dari a, yaitu a^1, a^2, ..., a^n, a^(n-1) = e.
Bukti.
1. Diketahui O(a) = n ==> a^n = e , n ϵ Z+
Ambil sebarang m ϵ Z, ada r, s ϵ Z sehingga m = r.n + s, 0 <= s <= n
Tinjau a^m.
a^m = a^(rn+s)
a^m = a^rn . a^s
a^m = (a^n)^r . a^s
a^m = e^r . a^s
a^m = a^s
ada variasi perpangkatan sbb : a^0 = e, a^1, a^2, ..., a^(n-1). (Hanya ada paling banyak n variasi)
2. Akan ditunjukkan semua variasi diatas berbeda.
Ambil sebarang p, q ϵ Z sehingga 0 < p < q < n
Andaikan a^p = a^q <=> a^(p-q) = e, misal : q-p = k < n.
kontradiksi bahwa n bilangan bulat terkecil sehingga a^n =e.
Jadi, pengandaian salah. Yang benar a^p tidak sama dengan a^q, 0 < ∀p, q < n
- ALGORITMA PEMBAGIAN BILANGAN BULAT
∀p, q, r, s bilangan bulat berlaku
p = r.q + s ; 0<= s <= q
dimana: q = hasil pembagian dan s = sisa
Contoh :
1. 16 dibagi 3 = 5 sisa 1. Jadi, algoritmanya 16 = 3.5 +1
2. Misal p = 5 dan q = 9, maka algoritmanya 5 = 0.9 + 5
Okee,, mungkin sekian dulu ya materinya. Semoga bermanfaat ^^,,
