O T O MA T A

1. Kumpulan (Himpunan)

Pendahuluan : George Boole (1815 – 1864)

Aplikasi : Analisa, Aljabar, Ilmu Ukur,
Kaitan Matematika dan Filsafat

Contoh :

a.
Kumpulan
huruf hidup

b.
Kumpulan
semua titik yang berjarak sama kesuatu
titik yang diketahuai

Simbol :

Himpunan huruf besar :
A, B, C,...

Anggota himpunan : a, b, c,...

Cara menggambarkan suatu kumpulan

a.
Metoda pendaftaran (Roster
Methods)

Contoh : A = {a, I, u, e, o}

b.
Metode Pencirian (Rule
Methods, Characterisation Methods)

Contoh :

A = { x I sifat  X}

A = { x : sifat X}

                Catatan :

1.
A
= { meja, pohon, pasir}

2.
B
= { x I X bilangan rasional
0 < X < 1 }

3.



C
= { x I X bilangan prima diantara
1 dan 25}

= {2, 3, 5, 7, 11, 13, 17, 19, 23}

                Definisi :

1.
Kumpulan
A terkandung dalam kumpulan B atau B mengandung A. Atau A kumpulan bagian dari B artinya setiap anggota A juga merupakan anggota B

2.
 A kumpulan bagian sejati B, jika anggota A juga
merupakan anggota B

Notasi : A B

3.
Dua kumpulan
A dan B dikatakan sama, jika
 anggota
A juga merupakan anggota B. Demikian pula sebaliknya.

Notasi : A = B  A B dan B A

Catatan :

a.
Jika A suatu kumpulan, maka A A

b.
A
B tidak mencegah
kemungkinan A = B

Teorema :

Untuk kumpulan sembarang A, B dan C

a.
A
B dan B C, maka A C

b.
A
= B maka B = A

c.
A
= B dan B = C maka A = C

Catatan : Kumpulan yang tidak
punya anggota disebut kumpulan kosong.

Contoh : A = {x I x2 + 1 = 0, x A}

Ditulis A = Ǿ

Contoh lain :

1.
B
= {x I X bilangan

2.
C
= {x I X Segitiga

3.
 D = { x I X ≠ x }

Teorema : Bila A kumpulan sembaran, maka Ǿ  A, jadi
kumpulan kosong merupakan kumpulan dari setiap kumpulan

Operasi dengan kumpulan

Dari dua kumpulan A
dan B dapat dibangun kumpulan baru dengan gabungan,
irisan dan selisih.

Definisi :

1. Gabungan A dan
   B = AB, ( A gabungan B)

Artinya : A B = { x I X A atau X B}

2. Persekutuan (irisan) A dan B = AB, (A irisan B)

Artinya : A  B = { x I X A dan X B}

3. Selisih dari
   A dan B (komplemen B terhadap A ) =
   A – B

Artinya : A – B = { x I X A dan X B}

4. Kumpulan dimana bentuk kumpulan-kumpulan bagian dari gabungan persekutuan complement
   maupun kombinasinya disebut Universe (Semesta) kumpulan dari Universe disebut kumpulan Universi U

Definisi :

1.
Bila A = U, maka A – B = B^c (komplemen dari B)

2.
Bila A, UA₂ UA₃ ... UAm ditulis U =

3.
Bila A, A₂  A₃... A_k ditulis
U =

Contoh : A = {1, 2, 3, 4} dan B = {2, 4, 5, 7}

Dit : 1). A U B,       2).
A B dan A –B

Jaw : 1) A U B = {x   A atau
X  B } = { 1, 2, 3, 4, 5,
7}

                Teorema : Untuk setiap kumpulan
A, B, dan C berlaku :

a.
A
U B = B U A (Sifat komutatif
untuk gabungan)

b.
A
B = B A (Sifat Komutatif
untuk irisan)

c.
A
U ( B UC) = (A UB) U C (Sifat Asosiatif
untuk gabungan)

d.
A
(BC) = (AB) C (Sifat Asosiatif
untuk irisan)

e.
A
U ( BC) = (A UB) C (Sifat Distributif
dari gabungan terhadap irisan

f.
A
(B UC) = (A B) U ( A C) (Sifat Distributif
dari irisan terhadap gabungan)

Buktikan sifat ini :

Ilustrasi, akan dibuktikan A U B = B U
A

Ambil X A U B, X sembarang

X A U B = X  A atau
X  B

                      X  B atau
X  A

                      X  B U A

Karena X  A
U B mengakibatkan X  B U A

Jadi A U B = B U A

Latihan dan contoh :

1.
Tuliskan kumpulan-kumpulan berikut dengan metoda pendaftaran atau pencirian atau keduanya.

a.
Kumpulan
bilangan asli < 20 dan habis dibagi
3

b.
Kumpulan
semua pecahan dgn pembilang 1 dan penyebut semua
bilangan asli  7

Penyelesaian :

a.
A
= {3, 6, 9, 12, 15, 18} = {x I X = 3m, m = 1, 2, i

b.
B
= { 1/7, 1/6, 1/5, ¼, 1/3, ½ } = { x I X 1/m, m = 1, 2, -7

2.
Nyatakan kumpulan berikut dengan metoda pencirian

a.
A
= {1, 4, 9, 16, 25, 36, 49}

b.
B
= {1, 4, 7, 10, 13, 16, 19, 21}

c.
C
= {2, 4, 8, 16, 32, 64, 128}

SISTIM
BILANGAN ASLI

Definisi

1. Bilangan Asli : 1, 2, 3, ... =
   1, 1 + 1, 2 + 1, 3 + 1, ... (asli)
2. Kumpulan U  R dinamakan kumpulan Induktif jika

a.
1
U

b.
Jika X U, X  sembarang maka (X + 1) juga anggota kumpulan
U

3. X R disebut bilangan
   asli, jika X merupakan anggota dari setiap kumpulan Induktif, jika

P = {bilangan asli}

U = {Induktif}

U = Koleksi dari U

Dikatakan

P = . {U/ U U } adaalh
kumpulan Induktif terkecil

Koleksi U tidak kosong karena R dan R ⁺ merupakan kumpulan Induktif

Induksi Metematika

Misal S
(n) peryataan mengenai bilangan asli n

Jika S
(1) benar dan pemisalan S (K) benar mengakibatkan S (K + 1) benar juga, maka pernyataan
S (n) benar untuk setiap bilangan asli n

Bukti : Tulis A = { n P / S (n) benar}

S (1) benar 1 P

S (k) benar k P

S (k + 1) benar (k +1) P

Jadi A adalah suatu kumpulan
Induktif sehingga  A P dan menurut
definisi P A maka A = P atau
pernyataan S (n) benar untuk setiap bilangan
asli n

Algoritma :

1. Periksa untuk
   n = 1
2. Andaikan pernyataan
   benar untuk n = 1 kemudian
3. Tunjukkan bahwa
   pernyataan juga benar untuk n = k + 1

Bila  1), 2), dan 3) dipenuhi, dapat disimpulkan.

Himpunan hingga dan perhitungan
jumlah anggota :

Jika A adalah himpunan hingga artinya A mempunyai anggota berhingga, dinyatakan dengan n (A), maka :

1. Jika A dan
   B himpunan hingga yang
   saling lepas, artinya A B = Ǿ, maka jumlah anggota A U B adalah :

N (A U B) = n (A) + n (B) – n (A B) = n (A) + n (B)

2. Jika A dan
   B sembarang dan tidak lepas, maka n (A U B) = n (A) + n (B) – n (A B)
3. Sifat (2) dapat
   diperluas untuk sembarang himpunan A, B, dan C, maka :

N (A U B U C) = n (A U B) + n © - n ( A U B C)

                =
n (A) + n(B) + n(C) – n(A B) – n( A c) – n (BC) + n (A BC)

Contoh Aplikasi :

Dari 120 orang Mahasiswa
Teknik Mesin semester pendek, 100 orang memilih paling sedikit satu mata kuliah
dasar yaitu Matematika, Fisika, dan Kimia.

Diketahui
juga bahwa :

65 orang mengambil Matematika

45 orang mengambil Fisika

42 orang mengambil Kimia

20 orang mengambil Matematika dan Fisika

25 orang mengambil Matematika dan Kimia

15 orang mengambil Fisika dan Kimia

Ditanya : Berapa jumlah Mahasiswa yang mengambil Matematika saja, Kimia saja, dan Fisika saja.

Penyelesaian :

Misal A =
{Matematika}, B = {Fisika},
C = {Kimia}

 n
(A U B U C) = 100, n(A) = 65, n(B) = 45, dan n(C) =
42

                N (A B) = 20, n(A C) = 25, n(B C) = 15

Jadi n (A
U B U C) = n(A) + n(B) + n(C) – n(AB) – n(AC) – n(BC) + n (A BC)

100 = 65 +
45 + 42 – 20 – 25 – 15 + n (A B C)

Jadi :

N (A B C) = 8

Contoh
:

Sebuah perusahaan computer akan menyewa programmers dengan kualifikasi sebagai berikut :

25 Programers menangani system pemrograman

40 Programers menangani program aplikasi

40 Programers menangani system pemrograman dan sekaligus program aplikasi

Tiap orang akan
dibayar Rp. 10.000.000 sampai program selesai.

Berapakah anggaran yang harus disiapkan?

Penyelesaian :

Anggaran
= jumlah Programers x Rp. 10.000.000

Misal :

A =
Kumpulan Programers system pemrograman

B =
Kumpulan Programers program aplikasi

Jadi IAI
= 25, IBI = 40, IABI = 40

IA U BI =
IAI + IBI - IABI = 25 + 40 – 10 = 55 orang

Anggaran = 55 x 10.000.000

                = 550.000.000

Contoh : Sistem transportasi kota

Tiap respondedt
ditanya tentang sarana transportasi yang digunakan. Pilihannya, Bus – Train – Automobile.

Respondent boleh memilih
lebih dari satu model transportasi yang digunakan.

Hasil survey :

1. 30 orang menggunakan Bus
2. 35 orang menggunakan Train
3. 100 orang menggunakan Automobile
4. 15 orang menggunakan Bus dan Train
5. 15 orang menggunakan Bus dan
   Automobile
6. 20 orang menggunakan Train dan
   Automobile
7. 5 orang menggunakan Bus, Train, dan
   Automobile

Berapa banyak respondent yang disurvey?

Jawab :

A – {Bus}, B = {Train}, C = {Automobile}

IA UB U CI = IAI + IBI + ICI – IA BI – IA CI – I B CI + I ABCI

RELASI :

Definisi :

1. A ≠ Ǿ dan
   ≠ Ǿ, maka
   kumpulan bagian dari A x B dinamakan relasi diantara A dan B

jika A = B, maka kumpulan
C yang bersifat C A x A dinamakan relasi
di A

2. Jika R suatu
   relasi dan (x,y) R, maka dikatakan
   X berada dalam relasi R dengan y, dalam hal ini ditulis Ry
3. Jika R suatu
   relasi diantara A dan B, maka
   himpunan {X A I (X, y) R} dinamakan daerah definisi R dan dinyatakan dengan D (R). Dan himpunan
   (y B I (X, y) R } disebut
   daerah nilai (rangkuman dari relasi R dan dinyatakan dengan R (R).

Ilustrasi :

A = {a, b, c, d, e, f}
dan B = {1, 2, 3, 4, 5}

A = {(a,1), (a,2),
(b,3), (c,1), (e,2)}

B = { (a,3), (2,b),
(C,5), (d,1), (e,4), (f,1)}

Ditanya : Selidiki apakah A dan B merupakan suatu relasi diantara A dan B, bila A dan
B merupakan relasi tentukan daerah definisi dan daerah
nilainya.

Jawab :

A x B = {(a,1), (a,2), (a,3), (a,4), (b,1),
(b,2), (b,3), (b,4), (b,5), (c,1), (c,2), (c,3), (c,4), (c,5), (d,1), (d,2),
(d,3), (d,4), (d,5), (e,1), (e,2), (e,3), (e,4), (e,5), (f,1), (f,2), (f,3),
(f,4), (f,5)}

B                                                     ( X, i)

i

2

1                        (a, 1)

                                                                       

                        a              b            X                   A

Dapat dilihat bahwa A
A x B  A suatu
relasi diantara A dan B. Daerah definisinya D (A)
= {a, b, c, d, e}

Ingat D ®
= { X  A I (X, y) R}

Daerah nilai R (A) = {1, 2, 3}

Sex : M =
Male, F = Female

Level pendidikan

e –
elementary school, h – high school

c – colloge, g – graduate school

Misalkan ; S = {m, f}, L – {e, h, c, g}

Maka hasil
kali kartesis S x L merupakan
seluruh kategori populasi yang dikelompokkan.

S x L =
{(m, e), (m, h), (m, c), (m, g), (f, e), (f, h), (f, c), (f, g)}

Jadi ada 8 kategori  = (2 x 4 = 8)

Perkalian Kartesis dari tiga atau
lebih himpunan tidak kosong artinya :

A₁ x A₂ x A₃ =
{(a₁, a₂, ... a_m) I a₁
A₁ , i = 1, 2, ... n}

Contoh :

Suatu perusahaan software menghasilkan tiga product dengan cirri-ciri sebagai berikut :

Langguage : F = Fortran, P = Pascal, L = Lisp

Memory : 48 = 48.000, 64 = 64.000, 128 =
128.000

Operating System : U =
Unix, C = CP/M

Misalkan L = { f,
p, l}, n ={48, 64, 128}, O = {u, c}

Maka :

L x M x O = akan berisi 3.3.2 = 18 kategori

Yaitu :

L x M x O = {(f, 48, u), (f, 48, c), (f, 64,
u), (f, 64, c), (f, 128, U), (f, 128,c), (p, 48, u), (p, 48, c), (p, 64, u),
(p, 64, c), (p, 128, u), (p, 128, c), (l, 48, u), (l, 64, u), (l, 64, c), (l,
128, u), (l, 128, c)}

A = {Tiga orang pegawai } = {a₁, a₂, a₃}

B = {Gaji ketiga pegawai tersebut} = {a₁₁, a₁₂, a₁₃,
a₂₁, a₂₂, a₃₁, a₃₂, a₃₃,
a₃₄}

Dimana a_ij
adalah gaji ke j dari orang
ke i

Dit :

Selidiki apakah kumpulan bagian berikut merupakan relasi dan fungsi
diantara A dan B

a.
A
= { (a₁, a₁₁), (a₂, a₂₁), (a₃,
a₃₁)}

b.
B
= { (a₁₁, a₁), (a₁, a₂₁), (a₃,
a₂₁)}

c.
C
= { (a₁, a₁₁), (a₂, a₁₂), (a₃,
a₁₃)}

Jawab :

d.
A
x B = { (a₁, a₁₁), (a₁, a₁₂), (a₁,
a₁₃), ... , (a₁, a₃₄),

(a₂, a₁₁), (a₂,
a₁₂), (a₂, a₁₃), ... ,(a₂,
a₃₄),

(a₃, a₁₁), (a₃,
a₁₂), (a₃, a₁₃), ... ,(a₃,
a₃₄)}

Kita lihat :

a.
A
A x B  A suatu
relasi diantara A dan B

D (A) = {a₁, a₂, a₃},
R (A) = {a₁₁, a₂₁, a₃₁}

b.
(a₁₁,
a₁) A x B B bukan relasi
diantara A = B

Anggota yang lain ada
di A x B

Bagaimana dengan B x A? (a₁, a₂₁) B x A

Jadi B bukan relasi diantara A dan B, demikian
pula dengan B dan A

c.
C
A x B  C merupakan
relasi diantara A danB

C juga merupakan suatu funsi C : A B

Ingat definisi fungsi :                                          

       X                                              Y                                      X                                             Y

                                                                        Boleh juga :       

Tapi bukan demikian :

                         X                                             Y

PARTISI

Suatu partisi atau “quatien set” dari suatu kumpulan
tak kosong A adalah koleksi P dari kumpulan bagian
A, sehingga :

1.
Setiap elemen A merupakan anggota dari kumpulan P

2.
Jika A₁ dan A₂
adalah elemen yang berbeda dari P, maka A₁  A₂ = Ǿ

Kumpulan dalam P disebut blocks atau cells

Contoh : P = { A₁, A₂,
A₃, A₄, A₅, A₆, A_7}

_{Gambarnya :}

Contoh : A = {a, b, c, d, e, f, g, h}

_{Tinjau :} A_{1 = {a, b, c, d},} A_{2 = {a, c,
e, f, g, h},} A_{3 = {a, c, e, g}}

                        A_{4  =  {b, d},}
A_{5  = {f, h}}

_{Periksa kumpulan
yang bukan partisi dari A}

A₁  A₂ = {a,c} ≠ Ǿ , A₁
 A₃ = {a,c} ≠ Ǿ , A₁  A₄ = {b,d} ≠ Ǿ ,

A₁  A₅ = {Ǿ}
≠ Ǿ , A₂  A₃ = {a,c, e, g} ≠ Ǿ ,

A₂  A₄ = {Ǿ}
≠ Ǿ , A₂  A₅ = {f,h} ≠ Ǿ ,

A₃  A₄ = {Ǿ}
≠ Ǿ , A₃  A₅ = {Ǿ}
≠ Ǿ , A₄  A₅ = {Ǿ}
≠ Ǿ

Jadi partisi dari koleksi P adalah :
P = {A₃, A₄, A₅}

Contoh :

Misal :

A = { Pegawai
General Motor}

A₁ = {Gaji
sekretaris}, A₂ =  {Gaji satpam}

A₃ = {Gaji
forman}, A₄ = {Gaji
teknisi}

A = { A₁, A₂,
A₃, A₄}

Ai = partisi dari A

Contoh :

A = Kumpulan semua bilangan bulat

A₁= Kumpulan semua
bilangan genap

A₂ = Kumpulan semua
bilangan ganjil

Definisi :

A ≠ Ǿ
dan B ≠ Ǿ merupakan
relasi diantara A dan B dari
F.

F disebut suatu fungsi,
notasi F : A B

Jika memenuhi (i) D (F) = A, (ii) (x,
y) F, (x, z) F, maka y = z

Jika F suatu fungsi dan
(x, y) F, maka ditulis
y = F(x)

Dimana F
(x) disebut nilai fungsi F di X

Contoh :

A = {a₁,
a₂, a₃} dan B = { a₁₁, a₁₂, a₁₃, a₂₁,
a₂₂, a₃₁, a₃₃, a₃₄}

Ditanya : Apakah kumpulan bagian berikut merupakan fungsi dari A ke
B?

1. F = { (a₁, a₁₁), (a₂,
   a₂₁), (a₃, a₃₁)
2. G = {(a₁, a₁₁), (a₂,
   a₂₁)}
3. H = {(a₁, a₁₁), (a₂,
   a₁₂), (a₂, a₂₁), (a₃, a₃₁)}

Jawab :

1. Periksa apakah
   D (F) = A?

D (F) = {a₁, a_2, a₃}
= A F : A B Suatu fungsi

2. Periksa D (G) = G?

D (G) = {a₁, a₂} ≠
A jadi G : A ≠ B bukan fungsi

3. Periksa D (H) = H?

D (H) = {a₁, a₂, a₃}
= A tapi (a₁, a₁₁) H, (a₁, a₁₂) H

Karena a₁₁ ≠ a₁₂
maka  H bukan suatu fungsi H : A ≠ B

PR1 A = {1,
2, 3}, B = {4, 5, 6, 7, 8, 9, 10}

Periksa apakah himpunan berikut merupakan fungsi dari A B

1. C = {(1,11), (2,10), (4, 6), (7, 8)}
2. D = {(1, 4), (2, 8), (3, 10)}
3. E = {(3, 4), (2, 9), (1, 10), (10, 3)}
4. F = {(1, 2), (1, 7), (4, 6), (3, 10)}

PR2

Buktikan :  n (A U
B U C) = n(A) + n(B) + n(C) – n (aB) – n (AC) – n (BC)

 _End

---

Catatan Kuliah Teori Bhs OTOMATA >> IF.11

RELATED POST

LIST

Silahkan berbagi dengan teman melalui tombol-tombol share ini...

• Stumb
• Icious
• Tech
• Twitt
• F.B.
• Redit
• Google
• Furl
• Mixx
• Design
• B.Mark
• B.List
• Diigo

  Menea