MATEMATIKA DISKRIT

MATEMATIKA DISKRIT

TEORI RELASI

Pengertian Relasi

      Kita misalkan E & F sebagai himpunan, hubungan antara himpunan E & himpunan F merupakan himpunan yang memiliki pasangan atau huruf/ angka yang berurutan,  tetapi  mengikuti aturan tertentu.

Contoh:

Misal E  = {2, 4, 6} dan F = {2, 4, 6, 8 }.

E × F menjadi :

E × F = {(2, 2), (2, 4), (2, 6), (2, 8), (4, 2), (4, 4), (4, 6), (4, 8), (6, 2), (6, 4), (6, 6), (6, 8)}

Jika menggunakan aturan relasi/ hubungan diatas, relasi R dari E  ke F  yang  mengikuti aturan tadi menjadi,

R = {(2, 2), (2, 4), (2, 6), (2, 8)}

Hubungan/Relasi bisa juga  terjadi hanya pada satu atau sebuah himpunan, yaitu hubungan  pada E, di himpunan E, yang merupakan himpunan E × E.

Cara menyatakan Relasi :

Cara menyatakan Relasi dapat dilakukan dengan:

    1.Diagram Panah

    2.Diagram Cartesius

     3.Himpunan Pasangan Berurutan

Contoh di atas dapat dinyatakan dalam himpunan pasangan berurutan dengan memasangkan secara berurutan anggota-anggota himpunan A dan anggota-anggota himpunan B yaitu:

{(1,A), (1,B), (2,B), (3,B), (3,C)}.

Sifat-Sifat Relasi :

RELASI BINER

Sebuah relasi A×A, yaitu relasi dari himpunan A kepada A sendiri, dapat memiliki sifat-sifat berikut:

• Refleksif
• Irefleksif
• Simetrik
• Anti-simetrik
• Transitif

Kita menyebut relasi R dari A kepada A sebagai relasi R dalam A.

Relasi Refleksif

Sebuah relasi R dalam A disebut memiliki sifat refleksif, jika setiap elemen A berhubungan dengan dirinya.

Contoh relasi yang memiliki sifat seperti ini adalah relasi “x selalu bersama y.”, dengan x dan y adalah anggota himpunan seluruh manusia. Jelas sekali bahwa setiap orang pasti selalu bersama dengan dirinya sendiri.

Relasi Irefleksif

Relasi R dalam A disebut memiliki sifat irefleksif, jika setiap elemen A tidak berhubungan dengan dirinya sendiri.

Contoh relasi irefleksif adalah relasi “x mampu mencukur rambut y dengan rapi sempurna.”, dengan xdan y adalah setiap pemotong rambut. Diandaikan bahwa setiap orang hanya dapat mencukur rambut orang lain dengan rapi sempurna, maka relasi ini adalah irefleksif, karena tidak ada seorang tukang cukur a yang mampu mencukur rambutnya sendiri.

Contoh lain dalam himpunan bilangan bulat adalah, relasi < dan > adalah irefleksif.

Relasi Simetrik

Relasi R dalam A disebut memiliki sifat simetrik, jika setiap pasangan anggota A berhubungan satu sama lain. Dengan kata lain, jika a terhubung dengan b, maka b juga terhubung dengan a. Jadi terdapat hubungan timbal balik.

Sebuah relasi “ genap” adalah relasi simetrik, karena untuk sembarang x dan y yang kita pilih, jika memenuhi relasi tersebut, maka dengan menukarkan nilai y dan x, relasi tersebut tetap dipenuhi. Misalnya untuk pasangan (5, 3) relasi tersebut dipenuhi, dan untuk (3, 5) juga.

Relasi Anti-simetrik

Jika setiap a dan b yang terhubung hanya terhubung salah satunya saja (dengan asumsi a dan bberlainan), maka relasi macam ini disebut relasi anti-simetrik.

Relasi Transitif

Sebuah relasi disebut transitif jika memiliki sifat, jika a berhubungan dengan b, dan b berhubungan dengan c, maka a berhubungan dengan c secara langsung.

Sebagai contoh, relasi dua transitif. Misalnya untuk 5, 6, dan 7, berlaku 5 < 6, 6 < 7, dan 5 < 7

Sebuah relasi disebut sebagai relasi ekivalen jika relasi tersebut bersifat:

• Refleksif
• Simetrik, dan
• Transitif

Orde parsial adalah relasi yang bersifat:

• Refleksif
• Anti-simetrik, dan
• Transitif

Contoh soal Relasi dan penyelesaiannya :

    1.   Misalkan A adalah himpunan yang anggotanya Anto, Andi, Yudi, Ani, Mila, dan Yanti. Dimana Anto, Andi, dan Yudi berjenis kelamin laki-laki, dan Ani, Mila, dan Yanti berjanis kelamin perempuan. Apakah himpunan A merupakan relasi ekuivalen ?

Jawab :

Untuk membuktikan himpunan A merupakan relasi ekuivalen harus memenihi ke-3 sifat yaitu refleksif,simetri dan transitif

sifat refleksif

anto ~ anto , berelasi dengan dirinya sendiri karena jenis kelaminnya laki-laki

sifat simetri

anto ~ andi

andi ~ anto , anto berelasi dengan andi dan andi berelasi dengan anto karena jenis kelaminnya sama.

sifat transitif

Mila ~ Ani

Ani ~ Yanti

Mila ~ Yanti

Mila berelasi dengan Ani dan Ani berelasi dengan Yanti maka otomatis Mila berelasi dengan Yanti karena jenis kelaminnya sama

kesimpulannya jadi himpunan A  merupakan relasi ekuivalen karena memenuhi ke-3 sifat dan sudah mempunyai relasi yaitu jenis kelamin yang sama.

   2.   A = { x│x  ≤ 4,x ϵ asli }

B = { y│2 ≤ y ≤ 12,y ϵ genap }

Tentukan relasi dari A ke B yang menyebabkan y = 3x

Jawab :

A = daerah asal (domain)

B = daerah hasil (kodomain)

Yang di tuju anak panah di sebut daerah hasil (range).

    3.  Lima orang siswa memilih kegiatan masing-masing. Adit dengan basket , Candra dengan karate, Yoseph dengan voli, Ilham dengan tenis meja dan Joni dengan judo. Tuliskan relasi tersebut dengan himpunan pasangan berurutan!

Jawab :

{(Adit,basket),(Candra,karate),(Yoseph,voli),(Ilham,tenis meja),(Joni,judo)}.

DAFTAR PUSTAKA

Munir. (2012). Matematika Diskrit, Revisi Kelima. Yogyakarta.

~~TRIMAKASIH~~

MATEMATIKA DISKRIT

Matematika Diskrit

Teori Himpunan

 Definisi himpunan

 Teori himpunan merupakan konsep dasar dalam pembahasan matematika diskrit

– Himpunan (set) adalah kumpulan objek-objek yang berbeda.

– Objek di dalam himpunan disebut elemen, unsur, atau anggota.

– HIMATIF adalah contoh sebuah himpunan, di dalamnya berisi anggota berupa mahasiswa. Tiap mahasiswa berbeda satu sama lain.

Dalam Penyajiannya :

A. Himpunan Enumerasi

Mengenumerasi artinya menuliskan semua elemen himpunan yang bersangkutan di antara dua buah tanda kurung kurawal. Biasanya suatu himpunan diberi nama dengan menggunakan huruf  kapital maupun dengan menggunakan simbol-simbol lainnya.

Contoh

– Himpunan A mempunyai tiga bilangan asli pertama: A={1,2,3}.

– Himpunan B mempunyai dua bilangan genap positif pertama: B={4,5}.

– Meskipun himpunan biasa digunakan untuk mengelompokkan objek yang mempunyai sifat mirip, tetapi dari definisi himpunan   diketahui  bahwa sah-sah saja elemen-elemen di dalam himpunan tidak mempunyai hubungan satu sama lain, asalkan berbeda.

– contoh: {hewan, a, Amir, 10, komputer} adalah himpunan yang terdiri dari lima elemen, yaitu hewan, a, Amir, 10, komputer.

– R  = { a, b, {a, b, c}, {a, c} }    C  = {a, {a}, {{a}} }

Contoh tersebut memperlihatkan bahwa suatu himpunan bisa terdapat anggota himpunan lain.

– K={ }

Contoh tersebut adalah himpunan kosong, karena K hanya berisi satu elemen yaitu { }.

Himpunan kosong dapat dilambangkan dengan Ø.

– Himpunan 100 buah bilangan asli pertama bisa dituli {1, 2, …, 100}

Untuk menuliskan himpunan yang tak berhingga, kita dapat menggunakan tandaellipsis(∞).

– Himpunan bilangan bulat positif ditulis sebagai {…, -2, -1, 0, 1, 2, …}.

B.  Keanggotaan

     x ∈ A : x merupakan anggota himpunan A;

     x ∉ A : x bukan merupakan anggota himpunan A.

     misal, A = {1, 2, 3, 4},  R  = { a, b, {a, b, c}, {a, c} }

     maka, 1 ∈ A dan b ∉ A

C.  Simbol-simbol Baku

Terdapat sejumlah simbol baku yang biasa digunakan untuk mendefinisikan himpunan yang sering digunakan,

antara lain:

P = himpunan bilangan bulat positif = {1,2,3,…}

N = himpunan bilangan alami (natural) = {1,2,…}

Z = himpunan bilangan bulat = {…,-2,-1,0,1,2,…}

Q = himpunan bilangan rasional

R = himpunan bilangan riil

C = himpunan bilangan kompleks

Kadang-kadang kita berhubungan dengan himpunan-himpunan yang semuanya merupakan bagian dari sebuah  himpunan yang universal. Himpunan yang universal ini disebut semesta dan disimbolkan dengan U.

Himpunan  U harus diberikan secara eksplisit atau diarahkan berdasarkan pembicaraan. Sebagai contoh, misalnya U = {bil. Genap kurang dari 6} berarti U= {2, 4}

E. Notasi Pembentuk Himpunan

Cara lain menyajikan himpunan adalah dengan notasi pembentuk himpunan (set builder). Dengan cara penyajian ini, himpunan dinyatakan dengan menulis syarat yang harus dipenuhi oleh anggotanya.

Notasi:{x|syarat yang harus dipenuhi oleh x}

Aturan dalam penulisan syarat keanggotaan:

Bagian di kiri tanda ’|’ melambangkan elemen himpunan

Tanda ’|’ dibaca dimana atau sedemikian sehingga

Bagian di kanan tanda ’|’ menunjukkan syarat keanggotaan himpunan

Setiap tanda ’,’ di dalam syarat keanggotaan dibaca sebagai dan

Contoh:

A adalah himpunan bilangan asli

Daftar anggota: A={1,2,3,. . .}

Notasi pembentuk himpunan: A={x | x ∈ A }

F. Diagram Venn

Diagram Venn menyajikan himpunan secara grafis. Cara penyajian himpunan ini diperkenalkan oleh matematikawan Inggris yang bernama John Venn pada tahun 1881. di dalam diagram Venn, himpunan semesta (U) digambarkan sebagai suatu segi empat sedangkan himpunan lainnya digambarkan sebagai lingkaran di dalam segi empat tersebut.

Contoh: Misalkan U = {1, 2, …, 7, 8},

                  A = {1, 2, 3, 5} dan B = {2, 5, 6, 8}.

G. Kardinalitas

Jumlah elemen di dalam A disebut kardinal dari himpunan A. Misalkan Amerupakan himpunan yang elemen-elemennya berhingga banyaknya. Jumlah elemen A disebut kardinal dari himpunan A.

Notasi: n(A) atau |A|  , notasi |A| untuk menyatakan kardinalitas himpunan.

B = {x|x merupakan HIMA di STTG}, Maka |B| = 4, dengan elemen-elemen Badalah HIMATIF, HIMAKOM, HIMASIP, HIMATI.

A = {a, {a}, {{a}}, maka |A| = 3, dengan elemen-elemen A (yang berbeda) adalah a, {a}, dan {{a}}.

Himpunan yang tidak berhingga banyak anggotanya mempunyai kardinalitas tidak berhingga pula. Sebagai contoh, himpunan bilangan riil mempunyai jumlah anggota tidak berhingga, maka |R| = ∞.

H. Himpunan Kosong

Himpunan yang tidak memiliki satupun elemen atau himpunan dengan kardinal = 0 disebut himpunan kosong (null set).

Notasi: Ø atau { } 

Contoh: A = {x | x < x}, maka n(A) = 0

Perhatikan bahwa himpunan {{ }} dapat juga ditulis sebagai {Ø}.

I. Himpunan bagian (subset)

Himpunan A dikatakan himpunan bagian dari himpunan B jika dan hanya jika setiap elemen A merupakan elemen B. Dalam hal ini, B dikatakan superset dari A.

Notasi: A ⊆ B

Contoh : 

A={1,2,3}

B={1,2,3,4,5,7}  

C={1,2,4,5}     

Jadi : * A ⊆ B   * A bukan himpunan bagian C

J.  Himpunan yang Sama

– Himpunan A dikatakan sama dengan himpunan B jika dan hanya jika setiap elemen A merupakan elemen B dan sebaliknya setiap elemen B merupakan elemen A.

– A = B jika A adalah himpunan bagian dari B dan B adalah himpunan bagian dariA. Jika tidak demikian, maka A ≠ B.

– Notasi : A = B  ↔  A ⊆ B dan B ⊆ A   

– Contoh: A={a,b,c}, B={c,a,b}      Jadi, A=B

– tiga prinsip yang perlu diingat dalam memeriksa kesamaan dua buah himpunan:

1. urutan elemen dalam himpunan tidak penting.         

     jadi {1,2,3} = {3,2,1} = {1,3,2}

2. pengulangan elemen tidak mempengaruhi kesamaan dua buah himpunan.            

      Jadi, {1,1,1,1}={1,1}={1}          {1,2,3}={1,2,1,3,2,1}

3. untuk tiga buah himpunan, A, B, C berlaku aksioma berikut:

– A = A, B = B, dan C=C

– Jika A = B,maka B

– Jika A = B, dan B = C maka A = C

K.  Himpunan Ekivalen

– Himpunan A dikatakan ekivalen dengan himpunan B jika dan hanya jika kardinal dari kedua himpunan tersebut sama.

– Notasi: A ~ B  ↔ |A|=|B|

Contoh: A={a,b,c} dan B={2,4,6} maka A ~ B sebab |A|= |B|

L. Himpunan Saling Lepas

– Dua himpunan A dan B dikatakan saling lepas (disjoint) jika keduanya tidak memiliki elemen yang sama.

– Notasi : A // B  

– Contoh: jika A={2,4,6,8} dan B={3,5,7} maka A // B sebab elemen himpunan A dan elemen himpunan B tidak ada yang sama.

M.  Himpunan Kuasa

Himpunan kuasa (power set) dari himpunan A adalah suatu himpunan yang elemennya merupakan semua himpunan bagian dari A, termasuk himpunan kosong dan himpunan A sendiri.

Notasi : P(A) atau 2^A

Jika |A| = m, maka |P(A)| = 2m.

Contoh:

– Jika A = { 1, 2 }, maka P(A) = { , { 1 }, { 2 }, { 1, 2 }}

– Himpunan kuasa dari himpunan kosong adalah P(Ø) = {Ø}, & himpunan kuasa dari himpunan {Ø} adalah P({Ø}) = {Ø, {Ø}}.

Operasi Pada Himpunan :

 Irisan ( ∩ )

Irisan (intersection) dari himpunan A dan B adalah himpunan yg setiap elemennya merupakan elemen dari himpunan A dan himpunan B.

Notasi: A ∩ B={x | x ∈ A dan x ∈ B}

Misalkan A={1,2,3,4,5} dan B={2,3,5,7,11} maka A ∩ B={2,3,5}

Gabungan  ( ∪ )

Gabungan(union) dari himpunan A dan B adalah  himpunan yang setiap anggotanya merupakan anggota himpunan A atau himpunan B.

Notasi : A ∪ B = { x | x ∈ A atau x ∈ B }

Misalkan A={1,2,3,4,5} dan B={2,3,5,7,11} maka, A ∪ B={1,2,3,4,5,7,11}

 Komplemen

Komplemen dari suatu himpunan A terhadap suatu himpunan semesta U adalah suatu himpunan yang elemennya

merupakan elemen U yang bukan elemen A.

Notasi : Ā = { x | x ∈ U, tapi x ∉ A }

Misalkan U={0,… 11} dan A={1,3,5,7} maka, Ā = {0,2,4,6,8,9,10,11}

 Selisih

Selisih dari dua himpunan A dan B adalah suatu himpunan yang elemennya merupakan elemen A dan bukan elemen B. Selisih antara A dan B dapat juga dikatakan sebagai komplemen himpunan B relatif terhadap himpunan A.

Notasi : A – B = { x | x ∈ A dan x ∉ B } = A ∩ B’

Misalkan A={1,2,3,4,5} dan B={2,3,5,7,11} maka A – B = {1,4}

Beda Setangkup

Beda setangkup dari himpunan A dan B adalah sesuatu himpunan yang elemennya ada pada himpunan A atau B, tetapi tidak pada keduanya.

Notasi: A⊕B = (A∪B) – (A∩B) = (A-B) ∪ (B-A)

Misalkan A = { 2, 4, 6 } dan B = { 2, 3, 5 } maka ,  A⊕B = { 3, 4, 5, 6 }

 Perkalian Kartesain

Perkalian kartesian (Cartesian products) dari himpunan A dan B adalah himpunan yang elemennya semua pasangan

berurutan (ordered pairs) yang mungkin terbentuk dengan komponen kedua dari himpunan A dan B.

Notasi: A x B ={(a,b)| a ∈ A dan b ∈ B}

Misalkan C = { 1, 2, 3 },  dan D = { a, b }, maka  C × D = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }

 Catatan :                              

1. jika A dan B merupakan himpunan berhingga, maka: |A x B| = |A| . |B|

2. Pasangan berurutan (a,b) berbeda dengan (b,a).

3. Perkalian kartesian tidak komutatif, yaitu A x B ≠ B x A dengan syarat A dan B tidak kosong.

4. Jika A = ∅ atau B = ∅ maka A x B = B x A = ∅

DAFTAR PUSTAKA

Wahyudin Djumanta, T. F. (2005). Mari Memahami Konsep Matematika Diskrit. Bandung: Grafindo Media Pratama.

~TRIMAKASIH~