STRUKTUR DISKRETT

TAJUK-TAJUK

MATHEMATICAL INDUCTION

Ini adalah satu lagi jenis pembuktian yang sangat penting dalam matematik.

DOMINOES

Saya berada di bahagian akhir satu siri permainan dominoes. Setiap dominoes adalah berjarak 2 inci dari jirannya yang lain, dan didepan dominoes ialah ‘pea shooter’. Saya menembak ‘pea shooter’ pada dominoes yang pertama. Adakah semua baris dominoes itu akan jatuh?

Ada dua persoalan yang perlu ditanya disini: iaitu adakah ‘pea shooter’ itu mengenai dominoes pertama itu dan adakah jarak antara dominoes itu cukup untuk menyebabkan dominoes yang jatuh akan menyebabkan dominoes yang lain juga jatuh ?

Teknik yang penting dalam pembuktian matematik adalah bergantung kepada dua idea ini:

1. 1. Bolehkah anda mendapatkan peringkat petama itu?

2. 2. Bolehkah anda mendapatkan dari sebarang peringkat untuk ke peringkat seterusnya?

Contoh 1

Berikut adalah beberapa pernyataan dengan beberapa bukti sebagai sokongan:

(a) (a) 1² + 2² + 3² + ... + n² = 1 {n(n+1)(2n+1) }

Pernyataan di atas adalah benar untuk n = 1, n = 2 dan n = 3.

(b) (b) n² ³ 2^{n – 1}

Kita boleh semak dengan mudah bahawa pernyataan di atas adalah benar untuk n = 1, n = 2, n = 3.

Pernyataan ini juga benar bila n =1, 2 atau 3.

Yang manakah dari 3 pernyataan di atas adalah benar untuk semua nilai n? Berapakah banyak nilai n yang diperlukan untuk menyemaknya? Sebenarnya contoh (a) dan (c) adalah benar untuk semua integer n tetapi contoh (b) adalah palsu untuk n ³ 7.

Pertimbangkan contoh 1(a). Andaikan kita tahu untuk sebarang nilai n yang tertentu,

1² + 2² + 3² + . . . + n² = 1 {n(n+1)(2n+1) } ................. (1)

Apakah yang boleh kita katakan tentang

1² + 2² + 3² + . . . + n² + ( n + 1 )² ? jika kita tambahkan kedua-dua belah persamaan (1) dengan ( n + 1 )² kita akan dapat

1² + 2² + 3² + . . . + n² + ( n + 1 )² = 1 {n(n+1)(2n+1) } + ( n + 1 )²

= 1 ( n + 1 ) {n(2n + 1) + 6(n + 1) }

= 1 (n + 1)(2n² + 7n + 6)

= 1 (n + 1)(n + 2)(2n + 3)

= 1 (n + 1) {(n + 1) + 1 }{2 (n + 1) + 1 }

Jadi ,

1² + 2² + 3² + . . . + n² + ( n + 1 )² = 1 (n + 1) {(n + 1) + 1 }{2 (n + 1) + 1 }

dimana adalah sama dengan persamaan (1) di atas, tetapi dengan (n+1) menggantikan tempat n. Jadi sekarang kita telah tunjukkan bahawa jika pernyataan itu benar untuk n maka ia juga adalah benar untuk (n + 1). Tetapi kita juga tahu bahawa ia adalah benar untuk 3 maka ia juga mestilah benar untuk 4. Jika ia benar untuk 4, maka ia mestilah juga benar untuk 5, ...., dan seterusnya.

THE PRINCIPLE OF MATHEMATICAL INDUCTION

Untuk setiap integer positif n, katakan P(n) adalah suatu pernyataan yang boleh jadi benar atau palsu. Andaikan bahawa

(i) (i) P(1) adalah benar

(ii) (ii) Untuk semua integer positif n, jika P(n) adalah benar maka

P(n + 1) juga adalah benar.

Maka, P(n) adalah benar untuk semua n ³ 1 .

Syarat (i) di atas adalah dipanggil ‘ the basis for the induction’ dan syarat (ii) pula dipanggil ‘inductive step’.

Contoh 2

Tunjukkan bahawa, untuk sebarang integer n ³ 1,

1 + 2 + 3 + 4 + . . . + n = 1 n(n + 1)

Penyelesaian:

Kita akan buktikan dengan menggunakan prinsip induksi matematik.

Katakan P(n) adalah suatu usulan

1 + 2 + 3 + 4 + . . . + n = 1 n(n + 1)

(i) (i) P(1) bermakna 1 = 1 (1)(1 + 1). Ini adalah benar dan kita telah

tunjukkan ‘the basis for the induction’.

(ii) (ii) Jika P(n) adalah benar maka

1 + 2 + . . . + n = 1 n(n + 1), dan dengan menambahkan (n + 1) untuk

kedua-dua belah persamaan ini kita akan dapat

1 + 2 + . . . + n + n + 1 = 1 n(n + 1) + (n + 1)

= (n + 1)( 1 n + 1)

= (n + 1) {1 (n + 2) }

= 1 (n + 1)(n + 2)

Oleh itu P(n +1) adalah benar. Kita telah tunjukkan ‘the inductive step’

KULIAH 9

SETS

Bermula pada abad ke 19, sekarang telah menjadi cabang matematik yang sangat penting, terutama dalam matematik moden. Pelopornya ialah Georg Cantor (1845 – 1918) seorang ahli matematik berbangsa German. Idea set yang dipelopori oleh Cantor telah diteruskan oleh David Hilbert (1862 – 1943) juga seorang ahli matematik berbangsa German.

Pendahuluan:

Set adalah satu pengumpulan bagi objek-objek yang tertentu.

Contoh 1

Pertimbangkan 5 set bagi objek-objek tertentu berikut:

· · {Pyramid of Cheops, Tembok Besar Cina, Empire State Building}

· · {1, 2, 3, 4}

· · {a, e, i, o, u}

· · {spaghetti, rice, bread, potato}

· · {1, 2, e, Tembok Besar Cina}

Objek-objek yang membentuk set adalah dipanggil unsur-unsur atau ahli kepada set tersebut. Unsur ini adalah dituliskan dengan menggunakan dua braces { }. Braces ini disebut sebagai set dimana unsur-unsurnya ialah...

Juga digunakan huruf besar untuk menentukan setiap set berkenaan. Sebagai contoh pertama di atas, kita boleh namakan set ‘A’, dan ditulis sebagai

A = {1, 2, 3, 3 } dan dibaca sebagai

A adalah suatu set yang unsur-unsurnya adalah 1, 2, 3, dan 4.

Order untuk kita menyatakan sesuatu set adalah tidak penting. Sebagai contoh set

A = {1, 3, 5, 7} dan B = {3, 1, 5, 7} adalah set yang sama.

Kita juga tidak akan membenarkan satu set yang mempunyai unsur yang berulang. Sebagai contoh, jika dalam satu kelas terdapat 10 murid berumur 6 tahun dan 15 murid berumur 7 tahun, maka setnya , katakan c iaitu bilangan murid dalam sebuah kelas mempunyai 25 unsur. Kita juga boleh menyatakan set bagi umur muris iaitu, A = {6, 7}.

Jika bilangan unsur set itu adalah kecil maka kita boleh menulisnya seperti contoh di atas. Jika besar dan bilangannya tidak terhingga, kita akan menulis dengan menggunakan simbul yang tertentu. Sebagai contoh, set bagi semua nombor perdana boleh ditulis sebagai

{x : x adalah nombor perdana}

Ini boleh dibaca sebagai set bagi semua unsur adalah x iaitu x adalah nombor perdana.

Contoh 2

Set X dimana unsurnya adalah integer genap boleh ditulis sebagai

{. . . , -4, -2, 0, 2, 4, . . . } atau boleh ditulis sebagai berikut

X = {x: x adalah integer positif}

Jika kita takrifkan dua set A dan B sebagai

A = {2, 4, 6, 8} dan

B = {x : x adalah nombor perdana}

Maka, 4 adalah suatu unsur bagi A. Kita boleh tulis ini sebagai 4 Î A , menggunakan simbol Î untuk menyatakan ‘ adalah unsur kepada’ . Juga 4 adalah bukan unsur kepada B. Kita tulis sebagai 4 Ï B dimana Ï dibaca sebagai ‘adalah bukan unsur kepada’.

Bila kita mengklasifikasikan sesuatu objek, kita perlu pertimbangkan berapa terperincinya pengkelasan tersebut. Sebagai contoh, jika kita takrifkan suatu set A sebagai

A = {x : x adalah seorang pelajar}

B = {x : x adalah seorang pelajar matematik}

Jika x Î B, maka secara automatik bahawa x Î A. Ini kerana B adalah mengandungi unsur bagi A. Maka kita katakan bahawa B adalah subset bagi A. Sebagai contoh lain, B = {1, 5} adalah subset kepada A = {1, 3, 5}. Maka kita boleh tulis sebagai B Í A . Kita juga benarkan subset itu adalah sama dengan set asalnya. Jadi jika A adalah sebarang set, maka adalah benar A Í A. Secara amnya kita katakan bahawa:

Set A adalah subset bagi set B jika setiap unsur A adalah juga unsur bagi B.

Secara formalnya,

A Í B Û ( "x, x Î A Þ x Î B )

Jika kita hendak bincangkan tentang suatu subset bagi B dimana tidak termasuk semua set maka kita akan bincangkan mengenai ‘proper subset’ bagi B.

Contoh 3

Dua contoh bagi subset:

{1, 5} Í {1, 2, 3, 4, 5}

{1, 5} Í {1, 5}

Kita hendak membezakan diantara satu unsur bagi suatu set , dan suatu set yang hanya mempunyai satu unsur sahaja.

Contoh 4

Katakan A = {1, 2} , maka 1 Î A tetapi { 1 } Í A .

Kita boleh katakan bahawa dua set X dan Y adalah sama jika mereka mempunyai bilangan unsur yang sama.

Contoh 5

Yang manakah set berikut adalah sama?

· · A = {-1, 1, 2}

· · B = {-1, 2, 1}

· · C = {0, 1, 2}

· · D = {2, 1, -1, -2}

· · E = {x : x² = 4 atau x² = 1}

Penyelesaian:

Set A dan B adalah sama, set D dan E adalah sama. Set C tidak sama dengan A atau B atau D atau E.

Contoh 6

Adakah set berikut sama?

· · X = {x : x² –5x + 6 = 0}

· · Y = {2, 3}

Penyelesaian:

x² –5x + 6 = 0 mempunyai dua penyelesaian, iaitu x = 2 dan x = 3. Unsur bagi X adalah sama dengan unsur bagi Y, maka X = Y.

Secra formalnya untuk menyatakan kesamaan bagi dua set ialah:

A = B Û ( x Î A Þ x Î B) dan ( x Î B Þ x Î A). Set notation ini adalah sama dengan A Í B dan B Í A. Jika perlu dibuktikan maka kita perlu buktikan kedua-dua arah.

KULIAH 10

OPERASI KE ATAS SET

Contoh 1

Pertimbangkan empat set berikut:

· · R = { y: y adalah ganjil, integer positif kurang dari 6 }

· · S = { y: y² –7y + 10 = 0 }

· · T = {y: y integer positif genap yang kurang dari 6 }

· · W= { 2, 4, 5 }

Kita boleh senaraikan kesemua unsur bagi set R,S dan T.

Kita boleh menggabungkan dua set A dan B menjadi set baru, dipanggil penyatuan bagi set A dan B. AÈB, ditakrifkan sebagai

AÈB = { x: x Î A atau x Î B }

Contoh 2

Dengan menggunakan Set R, S dan T dalam contoh 1 di atas kita dapat:

RÈT = {1, 2, 3, 4, 5 }

RÈS = {1, 2, 3, 5 }

Kita boleh juga melihat tindanan bagi dua set A dan B, dipanggil persilangan bagi set A dan B, AÇB , ditakrifkan sebagai

AÇB = { x: x Î A dan x Î B }

Contoh 3

Dengan menggunakan set R,S dan T dari contoh 1 kita dapat:

RÇS = { 5 }

SÇT = { 2 }

Kita juga boleh menyenaraikan unsur bagi A dimana tiada dalam set B. Operasi ini dikenali sebagai set beza diantara A dan B, dimana ditulis sebagai A\B.

A\B = { x: x Î A dan x Ï B }

Contoh 4

Dengan menggunakan set R, S dan T dari contoh 1 di atas kita dapat

R\T = {1, 3, 5 }

R\S = {1, 3 }

Contoh 5

Dengan menggunakan set R, S, T dan W dari contoh 1 di atas kita dapat

(RÈS) È W = {1, 2, 3, 5 }È { 2, 4, 5 } = {1, 2, 3, 4, 5 }

(RÇW) È S = { 5 }È{2,5 }= {2,5 }

SET EMPTY DAN SET UNIVERSAL

Set yang tidak mengandungi sebarang unsur dipanggil set empty. Kita tulis sebagai { } atau f .

Contoh 6

Dengan menggunakan contoh 1 di atas, terangkan kenapa RÇT = f

Kita juga menggunakan nama khas bagi set terbesar, iaitu u , dipanggil set universal.

Contoh 7

Dari contoh 1, jika

u = { x: x adalah integer positif kurang dari 6 } maka RÈT = u .

Set bagi unsurnya yang tiada di dalam set A dipanggil pelengkap bagi A, dan ditulis sebagai A^c.

A^c = { x: xÏA }

Contoh 8

Misalkan u = {1, 2, 3, 4, 5 } dan pertimbangkan dua set A = {1, 2} dan

B = {3} . Maka A^c = {3, 4, 5 } dan B^c = {1, 2, 4, 5 }

Contoh 9

Kita boleh lihat keputusan berikut adalah benar:

· · f^c = u

· · u^c = f

· · (A^c)^c = A

· · jika A Í B maka B^c Í A^c

contoh 10

Apakah set bagi AÈA, AÈf, AÇA, AÇf ?

Penyelesaian:

AÈA = A , AÈf = A, AÇA = A, AÇf = f .

Semua ini boleh ditunjukkan dengan gambarajah yang dikenali sebagai gambarajah Venn.

Contoh 11

A = {pelajar memakai cermin mata}

B = {pelajar yang suka matematik}

Kita boleh mewakilkan set universal bagi semua pelajar sebagai segiempat tepat, set A dan B sebagai bulatan. Pelajar yang memakai cermin mata dan suka matematik ialah AÇB, seperti dalam rajah di bawah

Latihan 9

Tuliskan yang berikut dengan menggunakan simbol set notation

a. a. {0, 2, 4, 6, 8, ... }

b. b. {0, 1, 2, 3,}

c. c. {0, 3, 6, 9}

Yang manakah pasangan set berikut adalah set sama?

a. a. {1, 2, 3,} , {2, 1, 3}

b. b. { x : x² + 2x + 1 = 0}, {1, -1}

Benar atau salah?

a. a. 2 Î {2, 3, 4 }

b. b. 2 Î {2 }

c. c. {2 }Î{2, 3, 4 }

d. d. {2,3 }Î{1, 3, {2,3 }}

e. e. {1, 2 }Î{1, 2, 3, 4 }

KULIAH 8

KULIAH 10