Matematika Diskrit - Panduan Cepat

Matematika secara luas dapat diklasifikasikan menjadi dua kategori -

• Continuous Mathematics- Ini didasarkan pada garis bilangan kontinu atau bilangan real. Hal ini ditandai dengan fakta bahwa di antara dua angka, hampir selalu ada kumpulan angka yang tak terbatas. Misalnya, fungsi dalam matematika kontinu dapat diplot dalam kurva halus tanpa putus.

• Discrete Mathematics- Ini melibatkan nilai-nilai yang berbeda; yaitu di antara dua titik, ada sejumlah titik yang dapat dihitung. Misalnya, jika kita memiliki sekumpulan objek yang terbatas, fungsinya dapat didefinisikan sebagai daftar pasangan terurut yang memiliki objek ini, dan dapat disajikan sebagai daftar lengkap pasangan tersebut.

Topik dalam Matematika Diskrit

Meskipun tidak ada jumlah pasti cabang Matematika Diskrit, topik berikut hampir selalu tercakup dalam studi apa pun mengenai masalah ini -

• Set, Relasi dan Fungsi
• Logika Matematika
• Teori kelompok
• Teori Penghitungan
• Probability
• Induksi Matematika dan Hubungan Pengulangan
• Teori grafik
• Trees
• Aljabar Boolean

Kami akan membahas masing-masing konsep ini di bab selanjutnya dari tutorial ini.

Ahli matematika Jerman G. Cantormemperkenalkan konsep set. Dia telah mendefinisikan himpunan sebagai kumpulan objek yang pasti dan dapat dibedakan yang dipilih dengan cara aturan atau deskripsi tertentu.

SetTeori membentuk dasar dari beberapa bidang studi lain seperti teori penghitungan, hubungan, teori grafik dan mesin keadaan hingga. Dalam bab ini, kami akan membahas berbagai aspekSet Theory.

Set - Definisi

Satu set adalah kumpulan elemen berbeda yang tidak berurutan. Sebuah himpunan dapat ditulis secara eksplisit dengan mendaftar elemen-elemennya menggunakan set braket. Jika urutan elemen diubah atau elemen apa pun dari suatu himpunan diulang, itu tidak membuat perubahan apa pun dalam himpunan.

Beberapa Contoh Set

• Satu set semua bilangan bulat positif
• Satu set dari semua planet di tata surya
• Satu set semua negara bagian di India
• Satu set semua huruf kecil alfabet

Representasi dari suatu Himpunan

Set dapat diwakili dalam dua cara -

• Daftar atau Bentuk Tabular
• Setel Notasi Pembangun

Daftar atau Bentuk Tabular

Himpunan diwakili dengan mendaftar semua elemen yang menyusunnya. Elemen diapit dengan tanda kurung dan dipisahkan dengan koma.

Example 1 - Set vokal dalam alfabet Inggris, $A = \lbrace a,e,i,o,u \rbrace$

Example 2 - Kumpulan bilangan ganjil kurang dari 10, $B = \lbrace 1,3,5,7,9 \rbrace$

Setel Notasi Pembangun

Himpunan didefinisikan dengan menentukan properti yang memiliki kesamaan dalam elemen-elemen himpunan. Set tersebut dideskripsikan sebagai$A = \lbrace x : p(x) \rbrace$

Example 1 - Set $\lbrace a,e,i,o,u \rbrace$ ditulis sebagai -

$A = \lbrace x : \text{x is a vowel in English alphabet} \rbrace$

Example 2 - Set $\lbrace 1,3,5,7,9 \rbrace$ ditulis sebagai -

$B = \lbrace x : 1 \le x \lt 10 \ and\ (x \% 2) \ne 0 \rbrace$

Jika elemen x adalah anggota himpunan S apa pun, itu dilambangkan dengan $x \in S$ dan jika elemen y bukan anggota himpunan S, itu dilambangkan dengan $y \notin S$.

Example- Jika$S = \lbrace1, 1.2, 1.7, 2\rbrace , 1 \in S$ tapi $1.5 \notin S$

Beberapa Set Penting

N - himpunan semua bilangan asli = $\lbrace1, 2, 3, 4, .....\rbrace$

Z - himpunan semua bilangan bulat = $\lbrace....., -3, -2, -1, 0, 1, 2, 3, .....\rbrace$

Z⁺ - himpunan semua bilangan bulat positif

Q - himpunan semua bilangan rasional

R - himpunan semua bilangan real

W - himpunan semua bilangan bulat

Kardinalitas Set

Kardinalitas dari himpunan S, dilambangkan dengan $|S|$, adalah jumlah elemen himpunan. Nomor tersebut juga disebut sebagai nomor pokok. Jika suatu himpunan memiliki jumlah elemen yang tak terbatas, kardinalitasnya adalah$\infty$.

Example - $|\lbrace 1, 4, 3, 5 \rbrace | = 4, | \lbrace 1, 2, 3, 4, 5, \dots \rbrace | = \infty$

Jika ada dua himpunan X dan Y,

• $|X| = |Y|$menunjukkan dua himpunan X dan Y yang memiliki kardinalitas yang sama. Ini terjadi ketika jumlah elemen di X sama persis dengan jumlah elemen di Y. Dalam kasus ini, terdapat fungsi bijektiva 'f' dari X ke Y.

• $|X| \le |Y|$menunjukkan bahwa himpunan X kardinalitas kurang dari atau sama dengan himpunan kardinalitas Y. Ini terjadi ketika jumlah elemen di X kurang dari atau sama dengan Y. Di sini, terdapat fungsi injeksi 'f' dari X ke Y.

• $|X| \lt |Y|$menunjukkan bahwa kardinalitas himpunan X kurang dari kardinalitas himpunan Y. Ini terjadi ketika jumlah elemen di X lebih kecil dari pada Y. Di sini, fungsi 'f' dari X ke Y adalah fungsi injektif tetapi tidak bijektiva.

• $If\ |X| \le |Y|$ dan $|X| \ge |Y|$ kemudian $|X| = |Y|$. Himpunan X dan Y biasanya disebut sebagai himpunan ekivalen.

Jenis Set

Set dapat diklasifikasikan ke dalam banyak jenis. Beberapa diantaranya adalah finite, infinite, subset, universal, proper, singleton set, dll.

Set Hingga

Himpunan yang berisi sejumlah elemen tertentu disebut himpunan hingga.

Example - $S = \lbrace x \:| \:x \in N$ dan $70 \gt x \gt 50 \rbrace$

Set Tak Terbatas

Himpunan yang berisi elemen dalam jumlah tak hingga disebut himpunan tak hingga.

Example - $S = \lbrace x \: | \: x \in N $ dan $ x \gt 10 \rbrace$

Subset

Himpunan X adalah himpunan bagian dari himpunan Y (Ditulis sebagai $X \subseteq Y$) jika setiap elemen X adalah elemen dari himpunan Y.

Example 1 - Biarkan, $X = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$ dan $Y = \lbrace 1, 2 \rbrace$. Di sini himpunan Y adalah himpunan bagian dari himpunan X karena semua elemen himpunan Y ada dalam himpunan X. Oleh karena itu, kita bisa menulisnya$Y \subseteq X$.

Example 2 - Biarkan, $X = \lbrace 1, 2, 3 \rbrace$ dan $Y = \lbrace 1, 2, 3 \rbrace$. Di sini himpunan Y adalah himpunan bagian (Bukan himpunan bagian yang tepat) dari himpunan X karena semua elemen himpunan Y ada di himpunan X. Oleh karena itu, kita bisa menulis$Y \subseteq X$.

Bagian yang tepat

Istilah "subset yang tepat" dapat didefinisikan sebagai "subset dari tetapi tidak sama dengan". Himpunan X adalah himpunan bagian yang tepat dari himpunan Y (Ditulis sebagai$ X \subset Y $) jika setiap elemen X adalah elemen dari himpunan Y dan $|X| \lt |Y|$.

Example - Biarkan, $X = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$ dan $Y = \lbrace 1, 2 \rbrace$. Di sini diatur$Y \subset X$ karena semua elemen masuk $Y$ terkandung di $X$ juga dan $X$ memiliki setidaknya satu elemen lebih dari yang ditetapkan $Y$.

Set Universal

Ini adalah kumpulan semua elemen dalam konteks atau aplikasi tertentu. Semua himpunan dalam konteks atau aplikasi itu pada dasarnya adalah himpunan bagian dari himpunan universal ini. Set universal direpresentasikan sebagai$U$.

Example - Kami dapat mendefinisikan $U$sebagai himpunan semua hewan di bumi. Dalam hal ini, himpunan semua mamalia adalah himpunan bagian dari$U$, kumpulan semua ikan adalah bagian dari $U$, kumpulan semua serangga adalah bagian dari $U$, dan seterusnya.

Set Kosong atau Set Null

Satu set kosong tidak berisi elemen. Ini dilambangkan dengan$\emptyset$. Karena jumlah elemen dalam himpunan kosong terbatas, himpunan kosong adalah himpunan berhingga. Kardinalitas himpunan kosong atau himpunan nol adalah nol.

Example - $S = \lbrace x \:| \: x \in N$ dan $7 \lt x \lt 8 \rbrace = \emptyset$

Singleton Set atau Unit Set

Singleton set atau unit set hanya berisi satu elemen. Himpunan tunggal dilambangkan dengan$\lbrace s \rbrace$.

Example - $S = \lbrace x \:| \:x \in N,\ 7 \lt x \lt 9 \rbrace$ = $\lbrace 8 \rbrace$

Set yang Sama

Jika dua himpunan berisi elemen yang sama, keduanya dikatakan sama.

Example - Jika $A = \lbrace 1, 2, 6 \rbrace$ dan $B = \lbrace 6, 1, 2 \rbrace$, mereka sama karena setiap elemen dari himpunan A adalah elemen dari himpunan B dan setiap elemen dari himpunan B adalah elemen dari himpunan A.

Set Setara

Jika kardinalitas dari dua himpunan adalah sama, disebut himpunan ekuivalen.

Example - Jika $A = \lbrace 1, 2, 6 \rbrace$ dan $B = \lbrace 16, 17, 22 \rbrace$, mereka setara karena kardinalitas A sama dengan kardinalitas B. ie $|A| = |B| = 3$

Set Tumpang Tindih

Dua set yang memiliki setidaknya satu elemen umum disebut set tumpang tindih.

Dalam kasus set tumpang tindih -

• $n(A \cup B) = n(A) + n(B) - n(A \cap B)$

• $n(A \cup B) = n(A - B) + n(B - A) + n(A \cap B)$

• $n(A) = n(A - B) + n(A \cap B)$

• $n(B) = n(B - A) + n(A \cap B)$

Example - Biarkan, $A = \lbrace 1, 2, 6 \rbrace$ dan $B = \lbrace 6, 12, 42 \rbrace$. Ada elemen umum '6', maka set ini adalah set yang tumpang tindih.

Set Pemutusan

Dua himpunan A dan B disebut himpunan terpisah jika tidak memiliki satu elemen yang sama. Oleh karena itu, set pemutusan hubungan kerja memiliki properti berikut -

• $n(A \cap B) = \emptyset$

• $n(A \cup B) = n(A) + n(B)$

Example - Biarkan, $A = \lbrace 1, 2, 6 \rbrace$ dan $B = \lbrace 7, 9, 14 \rbrace$, tidak ada satu elemen yang sama, oleh karena itu set ini adalah set yang tumpang tindih.

Diagram Venn

Diagram Venn, ditemukan pada tahun 1880 oleh John Venn, adalah diagram skematik yang menunjukkan semua kemungkinan hubungan logis antara himpunan matematika yang berbeda.

Examples

Atur Operasi

Operasi Set termasuk Set Union, Set Intersection, Set Difference, Complement of Set, dan Cartesian Product.

Atur Serikat

Gabungan himpunan A dan B (dilambangkan dengan $A \cup B$) adalah himpunan elemen yang ada di A, di B, atau di A dan B. Karenanya, $A \cup B = \lbrace x \:| \: x \in A\ OR\ x \in B \rbrace$.

Example - Jika $A = \lbrace 10, 11, 12, 13 \rbrace$ dan B = $\lbrace 13, 14, 15 \rbrace$, kemudian $A \cup B = \lbrace 10, 11, 12, 13, 14, 15 \rbrace$. (Elemen umum hanya terjadi sekali)

Atur Persimpangan

Perpotongan himpunan A dan B (dilambangkan dengan $A \cap B$) adalah himpunan elemen yang ada di A dan B. Oleh karena itu, $A \cap B = \lbrace x \:|\: x \in A\ AND\ x \in B \rbrace$.

Example - Jika $A = \lbrace 11, 12, 13 \rbrace$ dan $B = \lbrace 13, 14, 15 \rbrace$, kemudian $A \cap B = \lbrace 13 \rbrace$.

Tetapkan Selisih / Pelengkap Relatif

Perbedaan himpunan dari himpunan A dan B (dilambangkan dengan $A – B$) adalah himpunan elemen yang hanya ada di A tetapi tidak di B. Oleh karena itu, $A - B = \lbrace x \:| \: x \in A\ AND\ x \notin B \rbrace$.

Example - Jika $A = \lbrace 10, 11, 12, 13 \rbrace$ dan $B = \lbrace 13, 14, 15 \rbrace$, kemudian $(A - B) = \lbrace 10, 11, 12 \rbrace$ dan $(B - A) = \lbrace 14, 15 \rbrace$. Di sini, kita bisa melihat$(A - B) \ne (B - A)$

Pelengkap Set

Komplemen dari himpunan A (dilambangkan dengan $A’$) adalah himpunan elemen yang tidak dalam himpunan A. Oleh karena itu, $A' = \lbrace x | x \notin A \rbrace$.

Lebih spesifik, $A'= (U - A)$ dimana $U$ adalah himpunan universal yang berisi semua objek.

Example - Jika $A = \lbrace x \:| \: x\ \: {belongs\: to\: set\: of\: odd \:integers} \rbrace$ kemudian $A' = \lbrace y\: | \: y\ \: {does\: not\: belong\: to\: set\: of\: odd\: integers } \rbrace$

Produk Cartesian / Produk Silang

Produk Kartesius dari n jumlah set $A_1, A_2, \dots A_n$ dilambangkan sebagai $A_1 \times A_2 \dots \times A_n$ dapat didefinisikan sebagai semua kemungkinan pasangan terurut $(x_1, x_2, \dots x_n)$ dimana $x_1 \in A_1, x_2 \in A_2, \dots x_n \in A_n$

Example - Jika kita mengambil dua set $A = \lbrace a, b \rbrace$ dan $B = \lbrace 1, 2 \rbrace$,

Produk Cartesian dari A dan B ditulis sebagai - $A \times B = \lbrace (a, 1), (a, 2), (b, 1), (b, 2)\rbrace$

Produk Cartesian dari B dan A ditulis sebagai - $B \times A = \lbrace (1, a), (1, b), (2, a), (2, b)\rbrace$

Set Daya

Himpunan daya dari suatu himpunan S adalah himpunan dari semua himpunan bagian dari S termasuk himpunan kosong. Kardinalitas himpunan pangkat dari himpunan S dengan kardinalitas n adalah$2^n$. Perangkat daya dilambangkan sebagai$P(S)$.

Example −

Untuk satu set $S = \lbrace a, b, c, d \rbrace$ mari kita hitung subset -

• Himpunan bagian dengan 0 elemen - $\lbrace \emptyset \rbrace$ (set kosong)

• Himpunan bagian dengan 1 elemen - $\lbrace a \rbrace, \lbrace b \rbrace, \lbrace c \rbrace, \lbrace d \rbrace$

• Himpunan bagian dengan 2 elemen - $\lbrace a, b \rbrace, \lbrace a,c \rbrace, \lbrace a, d \rbrace, \lbrace b, c \rbrace, \lbrace b,d \rbrace,\lbrace c,d \rbrace$

• Himpunan bagian dengan 3 elemen - $\lbrace a ,b, c\rbrace,\lbrace a, b, d \rbrace, \lbrace a,c,d \rbrace,\lbrace b,c,d \rbrace$

• Himpunan bagian dengan 4 elemen - $\lbrace a, b, c, d \rbrace$

Karenanya, $P(S)=$

$\lbrace \quad \lbrace \emptyset \rbrace, \lbrace a \rbrace, \lbrace b \rbrace, \lbrace c \rbrace, \lbrace d \rbrace, \lbrace a,b \rbrace, \lbrace a,c \rbrace, \lbrace a,d \rbrace, \lbrace b,c \rbrace, \lbrace b,d \rbrace, \lbrace c,d \rbrace, \lbrace a,b,c \rbrace, \lbrace a,b,d \rbrace, \lbrace a,c,d \rbrace, \lbrace b,c,d \rbrace, \lbrace a,b,c,d \rbrace \quad \rbrace$

$| P(S) | = 2^4 = 16$

Note - Perangkat daya dari perangkat kosong juga merupakan perangkat kosong.

$| P (\lbrace \emptyset \rbrace) | = 2^0 = 1$

Mempartisi Set

Partisi suatu himpunan, katakanlah S , adalah kumpulan dari n himpunan bagian yang terputus-putus, misalnya$P_1, P_2, \dots P_n$ yang memenuhi tiga kondisi berikut -

• $P_i$ tidak berisi set kosong.

  $\lbrack P_i \ne \lbrace \emptyset \rbrace\ for\ all\ 0 \lt i \le n \rbrack$

• Gabungan himpunan bagian harus sama dengan seluruh himpunan asli.

  $\lbrack P_1 \cup P_2 \cup \dots \cup P_n = S \rbrack$

• Perpotongan dari dua set berbeda mana pun kosong.

  $\lbrack P_a \cap P_b = \lbrace \emptyset \rbrace,\ for\ a \ne b\ where\ n \ge a,\: b \ge 0 \rbrack$

Example

Membiarkan $S = \lbrace a, b, c, d, e, f, g, h \rbrace$

Salah satu kemungkinan partisi adalah $\lbrace a \rbrace, \lbrace b, c, d \rbrace, \lbrace e, f, g, h \rbrace$

Partisi lain yang mungkin adalah $\lbrace a, b \rbrace, \lbrace c, d \rbrace, \lbrace e, f, g, h \rbrace$

Nomor Bel

Nomor bel memberikan jumlah cara untuk mempartisi satu set. Mereka dilambangkan dengan$B_n$ dengan n adalah kardinalitas himpunan.

Example -

Membiarkan $S = \lbrace 1, 2, 3\rbrace$, $n = |S| = 3$

Partisi alternatifnya adalah -

1. $\emptyset , \lbrace 1, 2, 3 \rbrace$

2. $\lbrace 1 \rbrace , \lbrace 2, 3 \rbrace$

3. $\lbrace 1, 2 \rbrace , \lbrace 3 \rbrace$

4. $\lbrace 1, 3 \rbrace , \lbrace 2 \rbrace$

5. $\lbrace 1 \rbrace , \lbrace 2 \rbrace , \lbrace 3 \rbrace$

Karenanya $B_3 = 5$

Setiap kali himpunan sedang dibahas, hubungan antara unsur himpunan adalah hal berikutnya yang muncul. Relations mungkin ada di antara objek dari set yang sama atau di antara objek dari dua atau lebih set.

Definisi dan Properti

Sebuah relasi biner R dari himpunan x ke y (ditulis sebagai $xRy$ atau $R(x,y)$) adalah bagian dari produk Cartesian $x \times y$. Jika pasangan terurut G dibalik, relasinya juga berubah.

Umumnya suatu relasi n-ary R antar himpunan $A_1, \dots ,\ and\ A_n$ adalah bagian dari produk n-ary $A_1 \times \dots \times A_n$. Kardinalitas minimum dari suatu relasi R adalah Nol dan maksimum adalah$n^2$ pada kasus ini.

Relasi biner R pada satu himpunan A adalah himpunan bagian dari $A \times A$.

Untuk dua himpunan yang berbeda, A dan B, yang masing-masing memiliki kardinalitas m dan n , kardinalitas maksimum relasi R dari A ke B adalah mn .

Domain dan Jangkauan

Jika ada dua himpunan A dan B, dan relasi R memiliki pasangan orde (x, y), maka -

• Itu domain dari R, Dom (R), adalah himpunan $\lbrace x \:| \: (x, y) \in R \:for\: some\: y\: in\: B \rbrace$

• Itu range dari R, Ran (R), adalah himpunan $\lbrace y\: |\: (x, y) \in R \:for\: some\: x\: in\: A\rbrace$

Contoh

Membiarkan, $A = \lbrace 1, 2, 9 \rbrace $ dan $ B = \lbrace 1, 3, 7 \rbrace$

• Kasus 1 - Jika relasi R 'sama dengan' maka $R = \lbrace (1, 1), (3, 3) \rbrace$

  Dom (R) = $\lbrace 1, 3 \rbrace , Ran(R) = \lbrace 1, 3 \rbrace$

• Kasus 2 - Jika relasi R 'kurang dari' maka $R = \lbrace (1, 3), (1, 7), (2, 3), (2, 7) \rbrace$

  Dom (R) = $\lbrace 1, 2 \rbrace , Ran(R) = \lbrace 3, 7 \rbrace$

• Kasus 3 - Jika relasi R 'lebih besar dari' maka $R = \lbrace (2, 1), (9, 1), (9, 3), (9, 7) \rbrace$

  Dom (R) = $\lbrace 2, 9 \rbrace , Ran(R) = \lbrace 1, 3, 7 \rbrace$

Representasi Relasi menggunakan Graph

Suatu relasi dapat direpresentasikan menggunakan grafik berarah.

Jumlah simpul dalam grafik sama dengan jumlah elemen dalam himpunan yang relasinya telah ditentukan. Untuk setiap pasangan terurut (x, y) dalam relasi R, akan ada tepi berarah dari simpul 'x' ke simpul 'y'. Jika ada pasangan berurutan (x, x), maka akan terjadi self loop pada simpul 'x'.

Misalkan, ada relasi $R = \lbrace (1, 1), (1,2), (3, 2) \rbrace$ di set $S = \lbrace 1, 2, 3 \rbrace$, itu dapat diwakili oleh grafik berikut -

Jenis Relasi

• Itu Empty Relation antara himpunan X dan Y, atau di E, adalah himpunan kosong $\emptyset$

• Itu Full Relation antara himpunan X dan Y adalah himpunan $X \times Y$

• Itu Identity Relation di himpunan X adalah himpunan $\lbrace (x, x) | x \in X \rbrace$

• Hubungan Invers R 'dari suatu relasi R didefinisikan sebagai - $R' = \lbrace (b, a) | (a, b) \in R \rbrace$

  Example - Jika $R = \lbrace (1, 2), (2, 3) \rbrace$ kemudian $R' $ akan $\lbrace (2, 1), (3, 2) \rbrace$

• Relasi R pada himpunan A dipanggil Reflexive jika $\forall a \in A$ terkait dengan (memegang aRa)

  Example - Relasi $R = \lbrace (a, a), (b, b) \rbrace$ di set $X = \lbrace a, b \rbrace$ bersifat refleksif.

• Relasi R pada himpunan A dipanggil Irreflexive jika tidak $a \in A$ terkait dengan a (aRa tidak berlaku).

  Example - Relasi $R = \lbrace (a, b), (b, a) \rbrace$ di set $X = \lbrace a, b \rbrace$ tidak refleksif.

• Relasi R pada himpunan A dipanggil Symmetric jika $xRy$ menyiratkan $yRx$, $\forall x \in A$ dan $\forall y \in A$.

  Example - Relasi $R = \lbrace (1, 2), (2, 1), (3, 2), (2, 3) \rbrace$ di set $A = \lbrace 1, 2, 3 \rbrace$ simetris.

• Relasi R pada himpunan A dipanggil Anti-Symmetric jika $xRy$ dan $yRx$ menyiratkan $x = y \: \forall x \in A$ dan $\forall y \in A$.

  Example - Relasi $R = \lbrace (x, y)\to N |\:x \leq y \rbrace$ anti-simetris sejak $x \leq y$ dan $y \leq x$ menyiratkan $x = y$.

• Relasi R pada himpunan A dipanggil Transitive jika $xRy$ dan $yRz$ menyiratkan $xRz, \forall x,y,z \in A$.

  Example - Relasi $R = \lbrace (1, 2), (2, 3), (1, 3) \rbrace$ di set $A = \lbrace 1, 2, 3 \rbrace$ bersifat transitif.

• Relasi adalah Equivalence Relation jika refleksif, simetris, dan transitif.

  Example - Relasi $R = \lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2), (1,3), (3,1) \rbrace$ di set $A = \lbrace 1, 2, 3 \rbrace$ adalah hubungan kesetaraan karena refleksif, simetris, dan transitif.

SEBUAH Functionmenetapkan ke setiap elemen dari satu set, tepat satu elemen dari set terkait. Fungsi menemukan aplikasinya di berbagai bidang seperti representasi kompleksitas komputasi algoritme, menghitung objek, mempelajari urutan dan string, untuk beberapa nama. Bab ketiga dan terakhir dari bagian ini menyoroti aspek penting dari fungsi.

Fungsi - Definisi

Fungsi atau pemetaan (Didefinisikan sebagai $f: X \rightarrow Y$) adalah hubungan dari unsur-unsur satu himpunan X ke unsur-unsur himpunan Y lainnya (X dan Y adalah himpunan tidak kosong). X disebut Domain dan Y disebut Codomain dari fungsi 'f'.

Fungsi 'f' adalah relasi pada X dan Y sedemikian rupa untuk masing-masing $x \in X$, ada yang unik $y \in Y$ seperti yang $(x,y) \in R$. 'x' disebut gambar awal dan 'y' disebut gambar fungsi f.

Suatu fungsi bisa satu ke satu atau banyak ke satu tetapi tidak satu ke banyak.

Fungsi Injective / One-to-one

Sebuah fungsi $f: A \rightarrow B$ adalah fungsi injeksi atau satu-ke-satu jika untuk setiap $b \in B$, paling banyak ada satu $a \in A$ seperti yang $f(s) = t$.

Ini berarti fungsi f adalah suntik jika $a_1 \ne a_2$ menyiratkan $f(a1) \ne f(a2)$.

Contoh

• $f: N \rightarrow N, f(x) = 5x$ bersifat suntik.

• $f: N \rightarrow N, f(x) = x^2$ bersifat suntik.

• $f: R\rightarrow R, f(x) = x^2$ tidak suntik seperti $(-x)^2 = x^2$

Fungsi Surjective / Onto

Sebuah fungsi $f: A \rightarrow B$bersifat surjektiv (ke) jika bayangan f sama dengan kisarannya. Sama halnya, untuk setiap$b \in B$, ada beberapa $a \in A$ seperti yang $f(a) = b$. Ini berarti bahwa untuk setiap y di B, terdapat beberapa x di A sedemikian rupa$y = f(x)$.

Contoh

• $f : N \rightarrow N, f(x) = x + 2$ bersifat dugaan.

• $f : R \rightarrow R, f(x) = x^2$ tidak dapat diduga karena kita tidak dapat menemukan bilangan real yang kuadratnya negatif.

Bijective / Koresponden Satu-ke-satu

Sebuah fungsi $f: A \rightarrow B$ adalah koresponden bijective atau one-to-one jika dan hanya jika f bersifat injeksi dan dugaan.

Masalah

Buktikan bahwa suatu fungsi $f: R \rightarrow R$ didefinisikan oleh $f(x) = 2x – 3$ adalah fungsi bijective.

Explanation - Kita harus membuktikan bahwa fungsi ini bersifat injeksi dan dugaan.

Jika $f(x_1) = f(x_2)$, kemudian $2x_1 – 3 = 2x_2 – 3 $ dan itu menyiratkan itu $x_1 = x_2$.

Oleh karena itu, f adalah injective.

Sini, $2x – 3= y$

Begitu, $x = (y+5)/3$ yang dimiliki R dan $f(x) = y$.

Oleh karena itu, f adalah surjective.

Sejak f adalah keduanya surjective dan injective, kita bisa bilang f adalah bijective.

Kebalikan dari suatu Fungsi

Itu inverse dari fungsi yang sesuai satu-ke-satu $f : A \rightarrow B$, adalah fungsinya $g : B \rightarrow A$, memegang properti berikut -

$f(x) = y \Leftrightarrow g(y) = x$

Fungsi f disebut invertible, jika fungsi kebalikannya g ada.

Contoh

• Sebuah fungsi $f : Z \rightarrow Z, f(x)=x+5$, dapat dibalik karena memiliki fungsi invers $ g : Z \rightarrow Z, g(x)= x-5$.

• Sebuah fungsi $f : Z \rightarrow Z, f(x)=x^2$ tidak dapat dibalik karena ini bukan one-to-one as $(-x)^2=x^2$.

Komposisi Fungsi

Dua fungsi $f: A \rightarrow B$ dan $g: B \rightarrow C$ dapat disusun untuk memberikan komposisi $g o f$. Ini adalah fungsi dari A ke C yang didefinisikan oleh$(gof)(x) = g(f(x))$

Contoh

Membiarkan $f(x) = x + 2$ dan $g(x) = 2x + 1$, Temukan $( f o g)(x)$ dan $( g o f)(x)$.

Larutan

$(f o g)(x) = f (g(x)) = f(2x + 1) = 2x + 1 + 2 = 2x + 3$

$(g o f)(x) = g (f(x)) = g(x + 2) = 2 (x+2) + 1 = 2x + 5$

Karenanya, $(f o g)(x) \neq (g o f)(x)$

Beberapa Fakta tentang Komposisi

• Jika f dan g adalah satu-ke-satu maka fungsinya $(g o f)$ juga satu-ke-satu.

• Jika f dan g di atas maka fungsinya $(g o f)$ juga ke.

• Komposisi selalu memiliki properti asosiatif tetapi tidak memiliki properti komutatif.

Aturan logika matematika menentukan metode penalaran pernyataan matematika. Filsuf Yunani, Aristoteles, adalah pelopor penalaran logis. Penalaran logis memberikan dasar teoritis untuk banyak bidang matematika dan akibatnya ilmu komputer. Ini memiliki banyak aplikasi praktis dalam ilmu komputer seperti desain mesin komputasi, kecerdasan buatan, definisi struktur data untuk bahasa pemrograman, dll.

Propositional Logicberkaitan dengan pernyataan di mana nilai kebenaran, "benar" dan "salah", dapat ditetapkan. Tujuannya adalah untuk menganalisis pernyataan-pernyataan ini baik secara individu maupun gabungan.

Logika Preposisional - Definisi

Proposisi adalah kumpulan pernyataan deklaratif yang memiliki nilai kebenaran "benar" atau nilai kebenaran "salah". Proposisi terdiri dari variabel proposisional dan penghubung. Kami menunjukkan variabel proposisional dengan huruf kapital (A, B, dll). Penghubung menghubungkan variabel proposisional.

Beberapa contoh Proposisi diberikan di bawah ini -

• "Man is Mortal", ini mengembalikan nilai kebenaran "TRUE"
• "12 + 9 = 3 - 2", ini mengembalikan nilai kebenaran "FALSE"

Berikut ini bukan Proposisi -

• "A kurang dari 2". Itu karena kecuali kita memberikan nilai A tertentu, kita tidak dapat mengatakan apakah pernyataan itu benar atau salah.

Connectives

Dalam logika proposisional umumnya kami menggunakan lima penghubung yaitu -

• ATAU ($\lor$)

• DAN ($\land$)

• Negasi / TIDAK ($\lnot$)

• Implikasi / jika-maka ($\rightarrow$)

• Jika dan hanya jika ($\Leftrightarrow$).

OR ($\lor$) - Operasi OR dari dua proposisi A dan B (ditulis sebagai $A \lor B$) benar jika setidaknya salah satu variabel proposisional A atau B benar.

Tabel kebenarannya adalah sebagai berikut -

SEBUAH	B	A ∨ B
Benar	Benar	Benar
Benar	Salah	Benar
Salah	Benar	Benar
Salah	Salah	Salah

AND ($\land$) - Operasi AND dari dua proposisi A dan B (ditulis sebagai $A \land B$) benar jika variabel proposisional A dan B benar.

Tabel kebenarannya adalah sebagai berikut -

SEBUAH	B	A ∧ B
Benar	Benar	Benar
Benar	Salah	Salah
Salah	Benar	Salah
Salah	Salah	Salah

Negation ($\lnot$) - Negasi proposisi A (ditulis sebagai $\lnot A$) salah jika A benar dan benar jika A salah.

Tabel kebenarannya adalah sebagai berikut -

SEBUAH	¬ A
Benar	Salah
Salah	Benar

Implication / if-then ($\rightarrow$) - Implikasi $A \rightarrow B$adalah proposisi "jika A, maka B". Salah jika A benar dan B salah. Kasus lainnya benar.

Tabel kebenarannya adalah sebagai berikut -

SEBUAH	B	A → B
Benar	Benar	Benar
Benar	Salah	Salah
Salah	Benar	Benar
Salah	Salah	Benar

If and only if ($ \Leftrightarrow $) - $A \Leftrightarrow B$ adalah hubungan logis bi-kondisional yang benar jika p dan q sama, yaitu keduanya salah atau keduanya benar.

Tabel kebenarannya adalah sebagai berikut -

SEBUAH	B	A ⇔ B
Benar	Benar	Benar
Benar	Salah	Salah
Salah	Benar	Salah
Salah	Salah	Benar

Tautologi

Tautologi adalah rumus yang selalu benar untuk setiap nilai variabel proposisionalnya.

Example - Buktikan $\lbrack (A \rightarrow B) \land A \rbrack \rightarrow B$ adalah tautologi

Tabel kebenarannya adalah sebagai berikut -

SEBUAH	B	A → B	(A → B) ∧ A	[(A → B) ∧ A] → B
Benar	Benar	Benar	Benar	Benar
Benar	Salah	Salah	Salah	Benar
Salah	Benar	Benar	Salah	Benar
Salah	Salah	Benar	Salah	Benar

Seperti yang bisa kita lihat setiap nilai $\lbrack (A \rightarrow B) \land A \rbrack \rightarrow B$ adalah "Benar", itu adalah tautologi.

Kontradiksi

Kontradiksi adalah rumus yang selalu salah untuk setiap nilai variabel proposisionalnya.

Example - Buktikan $(A \lor B) \land \lbrack ( \lnot A) \land (\lnot B) \rbrack$ adalah kontradiksi

Tabel kebenarannya adalah sebagai berikut -

SEBUAH	B	A ∨ B	¬ A	¬ B	(¬ A) ∧ (¬ B)	(A ∨ B) ∧ [(¬ A) ∧ (¬ B)]
Benar	Benar	Benar	Salah	Salah	Salah	Salah
Benar	Salah	Benar	Salah	Benar	Salah	Salah
Salah	Benar	Benar	Benar	Salah	Salah	Salah
Salah	Salah	Salah	Benar	Benar	Benar	Salah

Seperti yang bisa kita lihat setiap nilai $(A \lor B) \land \lbrack ( \lnot A) \land (\lnot B) \rbrack$ adalah "False", itu adalah kontradiksi.

Kemungkinan

Kontingensi adalah rumus yang memiliki nilai benar dan salah untuk setiap nilai variabel proposisionalnya.

Example - Buktikan $(A \lor B) \land (\lnot A)$ sebuah kontingensi

Tabel kebenarannya adalah sebagai berikut -

SEBUAH	B	A ∨ B	¬ A	(A ∨ B) ∧ (¬ A)
Benar	Benar	Benar	Salah	Salah
Benar	Salah	Benar	Salah	Salah
Salah	Benar	Benar	Benar	Benar
Salah	Salah	Salah	Benar	Salah

Seperti yang bisa kita lihat setiap nilai $(A \lor B) \land (\lnot A)$ memiliki "Benar" dan "Salah", itu adalah kontingensi.

Persamaan Proposisional

Dua pernyataan X dan Y secara logis setara jika salah satu dari dua kondisi berikut berlaku -

• Tabel kebenaran setiap pernyataan memiliki nilai kebenaran yang sama.

• Pernyataan bi-kondisional $X \Leftrightarrow Y$ adalah tautologi.

Example - Buktikan $\lnot (A \lor B) and \lbrack (\lnot A) \land (\lnot B) \rbrack$ setara

Pengujian oleh 1 ^st metode (Matching tabel kebenaran)

SEBUAH	B	A ∨ B	¬ (A ∨ B)	¬ A	¬ B	[(¬ A) ∧ (¬ B)]
Benar	Benar	Benar	Salah	Salah	Salah	Salah
Benar	Salah	Benar	Salah	Salah	Benar	Salah
Salah	Benar	Benar	Salah	Benar	Salah	Salah
Salah	Salah	Salah	Benar	Benar	Benar	Benar

Di sini, kita bisa melihat nilai-nilai kebenaran $\lnot (A \lor B) and \lbrack (\lnot A) \land (\lnot B) \rbrack$ sama, maka pernyataannya setara.

Pengujian oleh 2 ^nd metode (Bi-persyaratan)

SEBUAH	B	¬ (A ∨ B)	[(¬ A) ∧ (¬ B)]	[¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)]
Benar	Benar	Salah	Salah	Benar
Benar	Salah	Salah	Salah	Benar
Salah	Benar	Salah	Salah	Benar
Salah	Salah	Benar	Benar	Benar

Sebagai $\lbrack \lnot (A \lor B) \rbrack \Leftrightarrow \lbrack (\lnot A ) \land (\lnot B) \rbrack$ adalah tautologi, pernyataannya setara.

Invers, Converse, dan Contra-positive

Implikasi / jika-maka $(\rightarrow)$juga disebut pernyataan bersyarat. Ini memiliki dua bagian -

• Hipotesis, hal
• Kesimpulan, q

Seperti disebutkan sebelumnya, ini dilambangkan sebagai $p \rightarrow q$.

Example of Conditional Statement- "Jika Anda mengerjakan pekerjaan rumah Anda, Anda tidak akan dihukum." Di sini, "Anda mengerjakan pekerjaan rumah Anda" adalah hipotesisnya, p, dan "Anda tidak akan dihukum" adalah kesimpulannya, q.

Inverse- Kebalikan dari pernyataan bersyarat adalah negasi dari hipotesis dan kesimpulan. Jika pernyataannya adalah “Jika p, maka q”, inversnya adalah “Jika bukan p, maka bukan q”. Jadi kebalikan dari$p \rightarrow q$ adalah $ \lnot p \rightarrow \lnot q$.

Example - Kebalikan dari "Jika Anda mengerjakan pekerjaan rumah, Anda tidak akan dihukum" adalah "Jika Anda tidak mengerjakan pekerjaan rumah Anda, Anda akan dihukum."

Converse- Kebalikan dari pernyataan bersyarat dihitung dengan mempertukarkan hipotesis dan kesimpulan. Jika pernyataannya adalah “If p, then q”, kebalikannya adalah “If q, then p”. Kebalikan dari$p \rightarrow q$ adalah $q \rightarrow p$.

Example - Kebalikan dari "Jika kamu mengerjakan pekerjaan rumah, kamu tidak akan dihukum" adalah "Jika kamu tidak akan dihukum, kamu mengerjakan pekerjaan rumahmu".

Contra-positive- Kontra-positif kondisional dihitung dengan mempertukarkan hipotesis dan kesimpulan pernyataan terbalik. Jika pernyataannya adalah “Jika p, maka q”, kontra-positifnya adalah “Jika bukan q, maka bukan p”. Kontra-positif dari$p \rightarrow q$ adalah $\lnot q \rightarrow \lnot p$.

Example - Kontra-positif dari "Jika Anda mengerjakan pekerjaan rumah Anda, Anda tidak akan dihukum" adalah "Jika Anda dihukum, Anda tidak mengerjakan pekerjaan rumah Anda".

Prinsip Dualitas

Prinsip dualitas menyatakan bahwa untuk setiap pernyataan yang benar, pernyataan ganda yang diperoleh dengan menukar serikat menjadi persimpangan (dan sebaliknya) dan menukar himpunan Universal menjadi himpunan Null (dan sebaliknya) juga benar. Jika dua dari pernyataan apapun adalah pernyataan itu sendiri, itu dikatakanself-dual pernyataan.

Example - Kembaran dari $(A \cap B ) \cup C$ adalah $(A \cup B) \cap C$

Bentuk Normal

Kita dapat mengubah proposisi apa pun dalam dua bentuk normal -

• Bentuk normal konjungtif
• Bentuk normal terputus

Bentuk Normal Konjungtif

Pernyataan gabungan dalam bentuk normal konjungtif jika diperoleh dengan mengoperasikan AND di antara variabel (negasi variabel yang disertakan) yang terhubung dengan OR. Dalam hal operasi himpunan, ini adalah pernyataan gabungan yang diperoleh dengan Persimpangan di antara variabel yang terhubung dengan Serikat.

Examples

• $(A \lor B) \land (A \lor C) \land (B \lor C \lor D)$

• $(P \cup Q) \cap (Q \cup R)$

Bentuk Normal Pemutusan

Pernyataan majemuk berada dalam bentuk normal disjungtif jika diperoleh dengan mengoperasikan OR di antara variabel (negasi variabel yang disertakan) yang terhubung dengan AND. Dalam hal operasi himpunan, ini adalah pernyataan gabungan yang diperoleh oleh Union di antara variabel yang terhubung dengan Intersections.

Examples

• $(A \land B) \lor (A \land C) \lor (B \land C \land D)$

• $(P \cap Q) \cup (Q \cap R)$

Predicate Logic berurusan dengan predikat, yaitu proposisi yang mengandung variabel.

Predicate Logic - Definisi

Predikat adalah ekspresi dari satu atau lebih variabel yang ditentukan pada beberapa domain tertentu. Predikat dengan variabel dapat dibuat proposisi dengan memberikan nilai ke variabel atau dengan mengukur variabel.

Berikut ini adalah beberapa contoh predikat -

• Misalkan E (x, y) menunjukkan "x = y"
• Misalkan X (a, b, c) menyatakan "a + b + c = 0"
• Misalkan M (x, y) menunjukkan "x menikah dengan y"

Formula yang dibentuk dengan baik

Formula Berbentuk Baik (wff) adalah predikat yang memiliki salah satu dari berikut -

• Semua konstanta proposisional dan variabel proposisional adalah wffs

• Jika x adalah variabel dan Y adalah wff, $\forall x Y$ dan $\exists x Y$ juga wff

• Nilai kebenaran dan nilai salah adalah wffs

• Setiap rumus atom adalah wff

• Semua penghubung yang menghubungkan wffs adalah wffs

Pengukur

Variabel predikat diukur dengan bilangan. Ada dua jenis pembilang dalam logika predikat - Pengukur Universal dan Pengukur Eksistensial.

Penghitung Universal

Pembilang universal menyatakan bahwa pernyataan dalam ruang lingkupnya benar untuk setiap nilai variabel tertentu. Itu dilambangkan dengan simbol$\forall$.

$\forall x P(x)$ dibaca untuk setiap nilai x, P (x) adalah benar.

Example - "Manusia itu fana" dapat diubah menjadi bentuk proposisional $\forall x P(x)$ dimana P (x) adalah predikat yang menunjukkan x adalah fana dan semesta wacana adalah semua manusia.

Pengukur Eksistensial

Pembilang eksistensial menyatakan bahwa pernyataan dalam ruang lingkupnya benar untuk beberapa nilai variabel tertentu. Itu dilambangkan dengan simbol$\exists $.

$\exists x P(x)$ dibaca karena untuk beberapa nilai x, P (x) benar.

Example - "Beberapa orang tidak jujur" dapat diubah menjadi bentuk proposisional $\exists x P(x)$ dimana P (x) adalah predikat yang menunjukkan x tidak jujur ​​dan semesta wacana adalah beberapa orang.

Pengukur Bersarang

Jika kita menggunakan pembilang yang muncul di dalam lingkup pembilang lain, itu disebut pembilang bersarang.

Example

• $\forall\ a\: \exists b\: P (x, y)$ dimana $P (a, b)$ menunjukkan $a + b = 0$

• $\forall\ a\: \forall\: b\: \forall\: c\: P (a, b, c)$ dimana $P (a, b)$ menunjukkan $a + (b + c) = (a + b) + c$

Note - $\forall\: a\: \exists b\: P (x, y) \ne \exists a\: \forall b\: P (x, y)$

Untuk menyimpulkan pernyataan baru dari pernyataan yang kebenarannya sudah kita ketahui, Rules of Inference digunakan.

Untuk apa Aturan Inferensi?

Logika matematika sering digunakan untuk pembuktian logika. Bukti adalah argumen valid yang menentukan nilai kebenaran pernyataan matematika.

Argumen adalah urutan pernyataan. Pernyataan terakhir adalah kesimpulan dan semua pernyataan sebelumnya disebut premis (atau hipotesis). Simbol "$\therefore$”, (Karena itu dibaca) ditempatkan sebelum kesimpulan. Argumen yang valid adalah argumen di mana kesimpulan mengikuti dari nilai-nilai kebenaran premis.

Aturan Inferensi menyediakan templat atau pedoman untuk membangun argumen yang valid dari pernyataan yang sudah kita miliki.

Tabel Aturan Inferensi

Aturan Inferensi	Nama	Aturan Inferensi	Nama
$$\begin{matrix} P \\ \hline \therefore P \lor Q \end{matrix}$$	Tambahan	$$\begin{matrix} P \lor Q \\ \lnot P \\ \hline \therefore Q \end{matrix}$$	Silogisme Disjungtif
$$\begin{matrix} P \\ Q \\ \hline \therefore P \land Q \end{matrix}$$	Konjungsi	$$\begin{matrix} P \rightarrow Q \\ Q \rightarrow R \\ \hline \therefore P \rightarrow R \end{matrix}$$	Silogisme Hipotesis
$$\begin{matrix} P \land Q\\ \hline \therefore P \end{matrix}$$	Penyederhanaan	$$\begin{matrix} ( P \rightarrow Q ) \land (R \rightarrow S) \\ P \lor R \\ \hline \therefore Q \lor S \end{matrix}$$	Dilema Konstruktif
$$\begin{matrix} P \rightarrow Q \\ P \\ \hline \therefore Q \end{matrix}$$	Modus Ponens	$$\begin{matrix} (P \rightarrow Q) \land (R \rightarrow S) \\ \lnot Q \lor \lnot S \\ \hline \therefore \lnot P \lor \lnot R \end{matrix}$$	Dilema yang Merusak
$$\begin{matrix} P \rightarrow Q \\ \lnot Q \\ \hline \therefore \lnot P \end{matrix}$$	Modus Tollens

Tambahan

Jika P adalah premis, kita dapat menggunakan aturan Penjumlahan untuk menurunkan $ P \lor Q $.

$$\begin{matrix} P \\ \hline \therefore P \lor Q \end{matrix}$$

Contoh

Biarkan P menjadi proposisi, "Dia belajar dengan sangat keras" adalah benar

Oleh karena itu - "Entah dia belajar sangat keras atau dia adalah murid yang sangat buruk." Di sini Q adalah proposisi "dia adalah siswa yang sangat buruk".

Konjungsi

Jika P dan Q adalah dua premis, kita dapat menggunakan aturan Konjungsi untuk menurunkannya $ P \land Q $.

$$\begin{matrix} P \\ Q \\ \hline \therefore P \land Q \end{matrix}$$

Contoh

Biarkan P - "Dia belajar dengan sangat keras"

Misalkan Q - "Dia adalah anak laki-laki terbaik di kelas"

Oleh karena itu - "Dia belajar sangat keras dan dia adalah anak laki-laki terbaik di kelas"

Penyederhanaan

Jika $P \land Q$ adalah premis, kita dapat menggunakan aturan Penyederhanaan untuk menurunkan P.

$$\begin{matrix} P \land Q\\ \hline \therefore P \end{matrix}$$

Contoh

"Dia belajar dengan sangat keras dan dia adalah anak laki-laki terbaik di kelasnya", $P \land Q$

Oleh karena itu - "Dia belajar dengan sangat keras"

Modus Ponens

Jika P dan $P \rightarrow Q$ adalah dua tempat, kita dapat menggunakan Modus Ponens untuk mendapatkan Q.

$$\begin{matrix} P \rightarrow Q \\ P \\ \hline \therefore Q \end{matrix}$$

Contoh

"Jika Anda memiliki kata sandi, maka Anda dapat masuk ke facebook", $P \rightarrow Q$

"Anda memiliki kata sandi", P.

Karenanya - "Anda bisa masuk ke facebook"

Modus Tollens

Jika $P \rightarrow Q$ dan $\lnot Q$ adalah dua tempat, kita dapat menggunakan Modus Tollens untuk mendapatkan $\lnot P$.

$$\begin{matrix} P \rightarrow Q \\ \lnot Q \\ \hline \therefore \lnot P \end{matrix}$$

Contoh

"Jika Anda memiliki kata sandi, maka Anda dapat masuk ke facebook", $P \rightarrow Q$

"Anda tidak dapat masuk ke facebook", $\lnot Q$

Oleh karena itu - "Anda tidak memiliki kata sandi"

Silogisme Disjungtif

Jika $\lnot P$ dan $P \lor Q$ adalah dua premis, kita dapat menggunakan Silogisme Disjungtif untuk menurunkan Q.

$$\begin{matrix} \lnot P \\ P \lor Q \\ \hline \therefore Q \end{matrix}$$

Contoh

"Es krimnya tidak berasa vanilla", $\lnot P$

"Es krimnya rasa vanilla atau rasa coklat", $P \lor Q$

Karenanya - "Es krimnya memiliki rasa cokelat”

Silogisme Hipotesis

Jika $P \rightarrow Q$ dan $Q \rightarrow R$ adalah dua premis, kita dapat menggunakan Silogisme Hipotetis untuk diturunkan $P \rightarrow R$

$$\begin{matrix} P \rightarrow Q \\ Q \rightarrow R \\ \hline \therefore P \rightarrow R \end{matrix}$$

Contoh

"Jika hujan, saya tidak akan pergi ke sekolah", $P \rightarrow Q$

"Jika saya tidak pergi ke sekolah, saya tidak perlu mengerjakan pekerjaan rumah", $Q \rightarrow R$

Oleh karena itu - "Jika hujan, saya tidak perlu melakukan pekerjaan rumah"

Dilema Konstruktif

Jika $( P \rightarrow Q ) \land (R \rightarrow S)$ dan $P \lor R$ adalah dua premis, kita dapat menggunakan dilema konstruktif untuk diturunkan $Q \lor S$.

$$\begin{matrix} ( P \rightarrow Q ) \land (R \rightarrow S) \\ P \lor R \\ \hline \therefore Q \lor S \end{matrix}$$

Contoh

"Jika hujan, saya akan pergi", $( P \rightarrow Q )$

“Jika di luar panas, saya akan pergi mandi”, $(R \rightarrow S)$

“Mungkin akan hujan atau panas di luar”, $P \lor R$

Oleh karena itu - "Aku akan pergi atau pergi mandi"

Dilema yang Merusak

Jika $(P \rightarrow Q) \land (R \rightarrow S)$ dan $ \lnot Q \lor \lnot S $ adalah dua premis, kita dapat menggunakan dilema destruktif untuk diturunkan $\lnot P \lor \lnot R$.

$$\begin{matrix} (P \rightarrow Q) \land (R \rightarrow S) \\ \lnot Q \lor \lnot S \\ \hline \therefore \lnot P \lor \lnot R \end{matrix}$$

Contoh

"Jika hujan, saya akan pergi", $(P \rightarrow Q )$

“Jika di luar panas, saya akan pergi mandi”, $(R \rightarrow S)$

“Entah saya tidak akan mengambil cuti atau saya tidak akan pergi mandi”, $\lnot Q \lor \lnot S$

Oleh karena itu - "Mungkin tidak hujan atau tidak panas di luar"

Teori Grup adalah cabang matematika dan aljabar abstrak yang mendefinisikan struktur aljabar bernama group. Umumnya, grup terdiri dari satu set elemen dan operasi atas dua elemen di set itu untuk membentuk elemen ketiga juga di set itu.

Pada tahun 1854, Arthur Cayley, ahli matematika Inggris, memberikan definisi modern tentang grup untuk pertama kalinya -

“Sekumpulan simbol yang semuanya berbeda, dan sedemikian rupa sehingga produk dari dua dari mereka (tidak peduli dalam urutan apa), atau produk dari salah satu dari mereka menjadi dirinya sendiri, termasuk dalam himpunan, dikatakan sebagai sebuah kelompok . Simbol-simbol ini tidak dapat dikonversi secara umum [komutatif], tetapi bersifat asosiatif. ”

Dalam bab ini, kita akan mengetahui tentang operators and postulates yang membentuk dasar-dasar teori himpunan, teori grup dan aljabar Boolean.

Setiap himpunan elemen dalam sistem matematika dapat didefinisikan dengan himpunan operator dan sejumlah postulat.

SEBUAH binary operatordidefinisikan pada satu set elemen adalah aturan yang menetapkan untuk setiap pasangan elemen elemen unik dari set itu. Misalnya diberikan himpunan$ A = \lbrace 1, 2, 3, 4, 5 \rbrace $, kita bisa bilang $\otimes$ adalah operator biner untuk operasi tersebut $c = a \otimes b$, jika ini menetapkan aturan untuk menemukan c untuk pasangan $(a,b)$, seperti yang $a,b,c \in A$.

Itu postulatesdari sistem matematika membentuk asumsi dasar dari mana aturan dapat disimpulkan. Postulatnya adalah -

Penutupan

Himpunan ditutup sehubungan dengan operator biner jika untuk setiap pasangan elemen dalam himpunan, operator menemukan elemen unik dari himpunan itu.

Contoh

Membiarkan $A = \lbrace 0, 1, 2, 3, 4, 5, \dots \rbrace$

Set ini ditutup di bawah operator biner ke $(\ast)$, karena untuk operasi $c = a \ast b$, untuk apa saja $a, b \in A$, produk $c \in A$.

Himpunan tidak ditutup di bawah pembagian operator biner $(\div)$Karena untuk pengoperasiannya $c = a \div b$, untuk apa saja $a, b \in A$, produk c mungkin tidak di set A. Jika $a = 7, b = 2$, kemudian $c = 3.5$. Sini$a,b \in A$ tapi $c \notin A$.

Hukum Asosiatif

Operator biner $\otimes$ pada himpunan A adalah asosiatif ketika memegang properti berikut -

$(x \otimes y) \otimes z = x \otimes (y \otimes z)$, dimana $x, y, z \in A $

Contoh

Membiarkan $A = \lbrace 1, 2, 3, 4 \rbrace$

Operator plus $( + )$ bersifat asosiatif karena untuk tiga elemen apa pun, $x,y,z \in A$, properti $(x + y) + z = x + ( y + z )$ memegang.

Operator minus $( - )$ tidak asosiatif sejak

$$( x - y ) - z \ne x - ( y - z )$$

Hukum Komutatif

Operator biner $\otimes$ pada himpunan A bersifat komutatif saat ia memegang properti berikut -

$x \otimes y = y \otimes x$, dimana $x, y \in A$

Contoh

Membiarkan $A = \lbrace 1, 2, 3, 4 \rbrace$

Operator plus $( + )$ bersifat komutatif karena untuk dua elemen apa pun, $x,y \in A$, properti $x + y = y + x$ memegang.

Operator minus $( - )$ tidak asosiatif sejak

$$x - y \ne y - x$$

Hukum Distributif

Dua operator biner $\otimes$ dan $\circledast$ pada himpunan A, bersifat distributif atas operator $\circledast$ ketika properti berikut memiliki -

$x \otimes (y \circledast z) = (x \otimes y) \circledast (x \otimes z)$, dimana $x, y, z \in A $

Contoh

Membiarkan $A = \lbrace 1, 2, 3, 4 \rbrace$

Operator menjadi $( * )$ dan plus $( + )$ bersifat distributif atas operator + karena untuk tiga elemen apa pun, $x,y,z \in A$, properti $x * ( y + z ) = ( x * y ) + ( x * z )$ memegang.

Namun, operator ini tidak terlalu distributif $*$ sejak

$$x + ( y * z ) \ne ( x + y ) * ( x + z )$$

Elemen Identitas

Himpunan A memiliki elemen identitas sehubungan dengan operasi biner $\otimes$ di A, jika ada elemen $e \in A$, sehingga properti berikut memiliki -

$e \otimes x = x \otimes e$, dimana $x \in A$

Contoh

Membiarkan $Z = \lbrace 0, 1, 2, 3, 4, 5, \dots \rbrace$

Elemen 1 adalah elemen identitas sehubungan dengan operasi $*$ karena untuk elemen apa pun $x \in Z$,

$$1 * x = x * 1$$

Di sisi lain, tidak ada elemen identitas untuk operasi minus $( - )$

Terbalik

Jika himpunan A memiliki elemen identitas $e$ sehubungan dengan operator biner $\otimes $, dikatakan memiliki invers setiap kali untuk setiap elemen $x \in A$, ada elemen lain $y \in A$, sehingga properti berikut memiliki -

$$x \otimes y = e$$

Contoh

Membiarkan $A = \lbrace \dots -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, \dots \rbrace$

Mengingat operasi plus $( + )$ dan $e = 0$, kebalikan dari setiap elemen x adalah $(-x)$ sejak $x + (x) = 0$

Hukum De Morgan

Hukum De Morgan memberikan sepasang transformasi antara penyatuan dan persimpangan dua (atau lebih) set dalam hal pelengkap mereka. Hukumnya adalah -

$$(A \cup B)' = A' \cap B'$$

$$(A \cap B)' = A' \cup B'$$

Contoh

Membiarkan $A = \lbrace 1, 2, 3, 4 \rbrace ,B = \lbrace 1, 3, 5, 7 \rbrace$, dan

Set universal $U = \lbrace 1, 2, 3, \dots, 9, 10 \rbrace$

$A' = \lbrace 5, 6, 7, 8, 9, 10 \rbrace$

$B' = \lbrace 2, 4, 6, 8, 9, 10 \rbrace$

$A \cup B = \lbrace 1, 2, 3, 4, 5, 7 \rbrace$

$A \cap B = \lbrace 1, 3 \rbrace $

$(A \cup B)' = \lbrace 6, 8, 9, 10 \rbrace$

$A' \cap B' = \lbrace 6, 8, 9, 10 \rbrace$

Jadi, kami melihat itu $(A \cup B)' = A' \cap B'$

$(A \cap B)' = \lbrace 2, 4, 5, 6, 7, 8, 9, 10 \rbrace$

$A' \cup B' = \lbrace 2, 4, 5, 6, 7, 8, 9, 10 \rbrace$

Jadi, kami melihat itu $(A \cap B)' = A' \cup B'$

Semigroup

Himpunan terbatas atau tak terbatas $‘S’$ dengan operasi biner $‘\omicron’$ (Komposisi) disebut semigroup jika mengikuti dua kondisi secara bersamaan -

• Closure - Untuk setiap pasangan $(a, b) \in S, \:(a \omicron b)$ harus hadir di set $S$.

• Associative - Untuk setiap elemen $a, b, c \in S, (a \omicron b) \omicron c = a \omicron (b \omicron c)$ harus dipegang.

Contoh

Himpunan bilangan bulat positif (tidak termasuk nol) dengan operasi penjumlahan adalah semigroup. Sebagai contoh,$ S = \lbrace 1, 2, 3, \dots \rbrace $

Di sini penutupan properti berlaku untuk setiap pasangan $(a, b) \in S, (a + b)$ hadir di himpunan S. Misalnya, $1 + 2 = 3 \in S]$

Properti asosiatif juga berlaku untuk setiap elemen $a, b, c \in S, (a + b) + c = a + (b + c)$. Sebagai contoh,$(1 + 2) + 3 = 1 + (2 + 3) = 5$

Monoid

Monoid adalah semigroup dengan elemen identitas. Elemen identitas (dilambangkan dengan$e$ atau E) dari himpunan S adalah elemen sedemikian rupa $(a \omicron e) = a$, untuk setiap elemen $a \in S$. Elemen identitas juga disebut aunit element. Jadi, sebuah monoid memiliki tiga properti secara bersamaan -Closure, Associative, Identity element.

Contoh

Himpunan bilangan bulat positif (tidak termasuk nol) dengan operasi perkalian adalah monoid. $S = \lbrace 1, 2, 3, \dots \rbrace $

Di sini penutupan properti berlaku untuk setiap pasangan $(a, b) \in S, (a \times b)$ hadir di himpunan S. [Misalnya, $1 \times 2 = 2 \in S$ dan seterusnya]

Properti asosiatif juga berlaku untuk setiap elemen $a, b, c \in S, (a \times b) \times c = a \times (b \times c)$ [Sebagai contoh, $(1 \times 2) \times 3 = 1 \times (2 \times 3) = 6$ dan seterusnya]

Properti identitas juga berlaku untuk setiap elemen $a \in S, (a \times e) = a$ [Sebagai contoh, $(2 \times 1) = 2, (3 \times 1) = 3$dan seterusnya]. Di sini elemen identitas adalah 1.

Kelompok

Grup adalah monoid dengan elemen terbalik. Elemen invers (dilambangkan dengan I) dari himpunan S adalah elemen sedemikian rupa$(a \omicron I) = (I \omicron a) = a$, untuk setiap elemen $a \in S$. Jadi, grup memiliki empat properti secara bersamaan - i) Penutupan, ii) Asosiatif, iii) Elemen identitas, iv) Elemen terbalik. Urutan grup G adalah jumlah elemen di G dan urutan elemen dalam grup adalah bilangan bulat positif terkecil n sehingga an adalah elemen identitas grup G.

Contoh

Sekumpulan dari $N \times N$ matriks non-singular membentuk kelompok dalam operasi perkalian matriks.

Produk dari dua $N \times N$ matriks non-singular juga merupakan $N \times N$ matriks non-singular yang memiliki properti penutupan.

Perkalian matriks sendiri bersifat asosiatif. Karenanya, kepemilikan asosiatif berlaku.

Sekumpulan dari $N \times N$ matriks non-singular berisi matriks identitas yang memegang properti elemen identitas.

Karena semua matriks adalah non-singular, mereka semua memiliki elemen invers yang juga merupakan matriks nonsingular. Karenanya, properti invers juga berlaku.

Grup Abelian

Grup abelian G adalah grup yang pasangan elemennya $(a,b) \in G$selalu memegang hukum komutatif. Jadi, sebuah grup memiliki lima properti secara bersamaan - i) Penutupan, ii) Asosiatif, iii) Elemen identitas, iv) Elemen terbalik, v) Komutatif.

Contoh

Himpunan bilangan bulat positif (termasuk nol) dengan operasi penjumlahan adalah grup abelian. $G = \lbrace 0, 1, 2, 3, \dots \rbrace$

Di sini penutupan properti berlaku untuk setiap pasangan $(a, b) \in S, (a + b)$ hadir di himpunan S. [Misalnya, $1 + 2 = 2 \in S$ dan seterusnya]

Properti asosiatif juga berlaku untuk setiap elemen $a, b, c \in S, (a + b) + c = a + (b + c)$ [Sebagai contoh, $(1 +2) + 3 = 1 + (2 + 3) = 6$ dan seterusnya]

Properti identitas juga berlaku untuk setiap elemen $a \in S, (a \times e) = a$ [Sebagai contoh, $(2 \times 1) = 2, (3 \times 1) = 3$dan seterusnya]. Di sini, elemen identitas adalah 1.

Properti komutatif juga berlaku untuk setiap elemen $a \in S, (a \times b) = (b \times a)$ [Sebagai contoh, $(2 \times 3) = (3 \times 2) = 3$ dan seterusnya]

Grup dan Subkelompok Siklik

SEBUAH cyclic groupadalah grup yang dapat dihasilkan oleh satu elemen. Setiap elemen dari grup siklik adalah kekuatan dari beberapa elemen tertentu yang disebut generator. Grup siklik dapat dihasilkan oleh generator 'g', sehingga setiap elemen grup dapat ditulis sebagai kekuatan generator 'g'.

Contoh

Kumpulan bilangan kompleks $\lbrace 1,-1, i, -i \rbrace$ di bawah operasi perkalian adalah grup siklik.

Ada dua generator - $i$ dan $–i$ sebagai $i^1 = i, i^2 = -1, i^3 = -i, i^4 = 1$ dan juga $(–i)^1 = -i, (–i)^2 = -1, (–i)^3 = i, (–i)^4 = 1$yang mencakup semua elemen kelompok. Oleh karena itu, ini adalah grup siklik.

Note - A cyclic groupselalu merupakan grup abelian tetapi tidak setiap grup abelian adalah grup siklik. Bilangan rasional yang ditambahkan tidak siklik tetapi abelian.

SEBUAH subgroup H adalah bagian dari grup G (dilambangkan dengan $H ≤ G$) jika itu memenuhi empat properti secara bersamaan - Closure, Associative, Identity element, dan Inverse.

Subgrup H dari grup G yang tidak mencakup seluruh grup G disebut subgrup yang tepat (Dilambangkan dengan $H < G$). Sebuah subkelompok dari grup siklik adalah siklik dan subkelompok abelian juga abelian.

Contoh

Biarkan kelompok $G = \lbrace 1, i, -1, -i \rbrace$

Kemudian beberapa subkelompok $H_1 = \lbrace 1 \rbrace, H_2 = \lbrace 1,-1 \rbrace$,

Ini bukan subkelompok - $H_3 = \lbrace 1, i \rbrace$ karena itu $(i)^{-1} = -i$ tidak masuk $H_3$

Set Pesanan Sebagian (POSET)

Himpunan terurut sebagian terdiri dari himpunan dengan relasi biner yang bersifat refleksif, antisimetris, dan transitif. "Kumpulan dipesan sebagian" disingkat POSET.

Contoh

• Himpunan bilangan real di bawah operasi biner kurang dari atau sama dengan $(\le)$ adalah poset.

  Biarkan set $S = \lbrace 1, 2, 3 \rbrace$ dan operasinya $\le$

  Hubungan akan terjalin $\lbrace(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3)\rbrace$

  Relasi R ini refleksif sebagai $\lbrace (1, 1), (2, 2), (3, 3)\rbrace \in R$

  Relasi R ini anti simetris, sebagai

  $\lbrace (1, 2), (1, 3), (2, 3) \rbrace \in R\ and\ \lbrace (1, 2), (1, 3), (2, 3) \rbrace ∉ R$

  Relasi R ini juga transitif sebagai $\lbrace (1,2), (2,3), (1,3)\rbrace \in R$.

  Oleh karena itu, ini adalah a poset.

• Himpunan puncak dari grafik asiklik terarah di bawah 'reachability' operasi adalah sebuah poset.

Diagram Hasse

Diagram Hasse dari sebuah poset adalah graf berarah yang simpulnya merupakan elemen dari poset tersebut dan busurnya menutupi pasangan (x, y) pada poset tersebut. Jika di poset tersebut$x < y$, maka titik x tampak lebih rendah dari titik y pada diagram Hasse. Jika$x<y<z$ di poset, maka panah tidak ditampilkan di antara x dan z karena tersirat.

Contoh

Poset himpunan bagian dari $\lbrace 1, 2, 3 \rbrace = \lbrace \emptyset, \lbrace 1 \rbrace, \lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 1, 2 \rbrace, \lbrace 1, 3 \rbrace, \lbrace 2, 3 \rbrace, \lbrace 1, 2, 3 \rbrace \rbrace$ ditunjukkan oleh diagram Hasse berikut -

Set Berurutan Linier

Himpunan berurutan linier atau himpunan terurut Total adalah himpunan urutan parsial di mana setiap pasangan elemen dapat dibandingkan. Elemen-elemen$a, b \in S$ dikatakan sebanding jika keduanya $a \le b$ atau $b \le a$memegang. Hukum trikotomi mendefinisikan himpunan teratur total ini. Satu set yang benar-benar tertata dapat didefinisikan sebagai kisi distributif yang memiliki properti$\lbrace a \lor b, a \land b \rbrace = \lbrace a, b \rbrace$ untuk semua nilai a dan b di himpunan S.

Contoh

Kumpulan kekuatan $\lbrace a, b \rbrace$ dipesan oleh \ subseteq adalah himpunan yang sepenuhnya teratur karena semua elemen dari himpunan daya $P = \lbrace \emptyset, \lbrace a \rbrace, \lbrace b \rbrace, \lbrace a, b\rbrace \rbrace$ sebanding.

Contoh kumpulan pesanan non-total

Satu set $S = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$ di bawah operasi x membagi y bukan set total yang dipesan.

Di sini, untuk semua $(x, y) \in S, x | y$harus dipegang tetapi tidak benar bahwa 2 | 3, karena 2 tidak membagi 3 atau 3 tidak membagi 2. Oleh karena itu, ini bukan himpunan terurut total.

Kisi

Kisi adalah poset $(L, \le)$ untuk yang mana setiap pasang $\lbrace a, b \rbrace \in L$ memiliki batas atas terkecil (dilambangkan dengan $a \lor b$) dan batas bawah terbesar (dilambangkan dengan $a \land b$). LUB$(\lbrace a,b \rbrace)$disebut gabungan dari a dan b. GLB$(\lbrace a,b \rbrace )$ disebut pertemuan a dan b.

Contoh

Angka di atas adalah kisi karena untuk setiap pasangan $\lbrace a, b \rbrace \in L$, GLB dan LUB ada.

Angka di atas ini bukan kisi karena $GLB (a, b)$ dan $LUB (e, f)$ tidak ada.

Beberapa kisi lain dibahas di bawah ini -

Kisi Terikat

Kisi L menjadi kisi terbatas jika memiliki elemen terbesar 1 dan paling sedikit elemen 0.

Kisi Lengkap

Kisi L menjadi kisi komplementer jika kisi tersebut berhingga dan jika setiap elemen dalam kisi memiliki komplemen. Sebuah elemen x memiliki komplemen x 'if$\exists x(x \land x’=0 and x \lor x’ = 1)$

Kisi Distributif

Jika kisi memenuhi dua properti distribusi berikut, ini disebut kisi distributif.

• $a \lor (b \land c) = (a \lor b) \land (a \lor c)$

• $a \land (b \lor c) = (a \land b) \lor (a \land c)$

Kisi Modular

Jika kisi memenuhi properti berikut, ini disebut kisi modular.

$a \land( b \lor (a \land d)) = (a \land b) \lor (a \land d)$

Properti Kisi

Properti Idempoten

• $a \lor a = a$

• $a \land a = a$

Properti Penyerapan

• $a \lor (a \land b) = a$

• $a \land (a \lor b) = a$

Properti Komutatif

• $a \lor b = b \lor a$

• $a \land b = b \land a$

Properti Asosiatif

• $a \lor (b \lor c) = (a \lor b) \lor c$

• $a \land (b \land c) = (a \land b) \land c$

Dual of a Lattice

Kisi ganda diperoleh dengan menukar '$\lor$'dan'$\land$' operasi.

Contoh

Ganda dari $\lbrack a \lor (b \land c) \rbrack\ is\ \lbrack a \land (b \lor c) \rbrack$

Dalam kehidupan sehari-hari, sering kali seseorang perlu mencari tahu jumlah semua kemungkinan hasil untuk serangkaian peristiwa. Misalnya, berapa cara yang dipilih majelis hakim yang terdiri dari 6 laki-laki dan 4 perempuan dari 50 laki-laki dan 38 perempuan? Berapa banyak 10 angka PAN berhuruf berbeda yang dapat dibuat sedemikian rupa sehingga lima huruf pertama adalah huruf kapital, empat angka berikutnya adalah digit dan yang terakhir adalah huruf kapital. Untuk memecahkan masalah ini, teori penghitungan matematika digunakan.Counting terutama mencakup aturan penghitungan dasar, aturan permutasi, dan aturan kombinasi.

Aturan Jumlah dan Produk

Itu Rule of Sum dan Rule of Product digunakan untuk menguraikan soal-soal menghitung yang sulit menjadi soal-soal sederhana.

• The Rule of Sum - Jika urutan tugas $T_1, T_2, \dots, T_m$ bisa dilakukan di $w_1, w_2, \dots w_m$ cara masing-masing (syaratnya adalah tidak ada tugas yang dapat dilakukan secara bersamaan), maka jumlah cara untuk melakukan salah satu dari tugas ini adalah $w_1 + w_2 + \dots +w_m$. Jika kita mempertimbangkan dua tugas A dan B yang saling terpisah (mis$A \cap B = \emptyset$), lalu secara matematis $|A \cup B| = |A| + |B|$

• The Rule of Product - Jika urutan tugas $T_1, T_2, \dots, T_m$ bisa dilakukan di $w_1, w_2, \dots w_m$ cara masing-masing dan setiap tugas tiba setelah terjadinya tugas sebelumnya, maka ada $w_1 \times w_2 \times \dots \times w_m$cara untuk melakukan tugas. Secara matematis, jika tugas B tiba setelah tugas A, maka$|A \times B| = |A|\times|B|$

Contoh

Question- Seorang anak laki-laki tinggal di X dan ingin bersekolah di Z. Dari rumahnya X dia harus mencapai Y terlebih dahulu dan kemudian Y ke Z. Dia dapat pergi dari X ke Y melalui 3 rute bus atau 2 rute kereta. Dari sana, ia dapat memilih 4 rute bus atau 5 rute kereta untuk mencapai Z. Ada berapa cara untuk pergi dari X ke Z?

Solution - Dari X ke Y, dia bisa masuk $3 + 2 = 5$cara (Aturan Jumlah). Setelah itu, dia bisa memasukkan Y ke Z masuk$4 + 5 = 9$cara (Aturan Jumlah). Karena itu dari X ke Z dia bisa masuk$5 \times 9 = 45$ cara (Aturan Produk).

Permutasi

SEBUAH permutationadalah pengaturan dari beberapa elemen yang urutannya penting. Dengan kata lain Permutasi adalah Kombinasi elemen yang teratur.

Contoh

• Dari himpunan S = {x, y, z} dengan mengambil dua sekaligus, semua permutasi adalah -

  $ xy, yx, xz, zx, yz, zy $.

• Kita harus membentuk permutasi tiga digit angka dari satu set angka $S = \lbrace 1, 2, 3 \rbrace$. Tiga digit angka yang berbeda akan terbentuk saat kita menyusun digitnya. Permutasi akan menjadi = 123, 132, 213, 231, 312, 321

Jumlah Permutasi

Jumlah permutasi 'n' hal-hal berbeda yang diambil 'r' pada satu waktu dilambangkan dengan $n_{P_{r}}$

$$n_{P_{r}} = \frac{n!}{(n - r)!}$$

dimana $n! = 1.2.3. \dots (n - 1).n$

Proof - Biarlah ada 'n' elemen yang berbeda.

Ada banyak cara untuk mengisi tempat pertama. Setelah mengisi tempat pertama (n-1) jumlah elemen tersisa. Karenanya, ada (n-1) cara untuk mengisi tempat kedua. Setelah mengisi tempat pertama dan kedua, tersisa (n-2) jumlah elemen. Karenanya, ada (n-2) cara untuk mengisi tempat ketiga. Sekarang kita dapat menggeneralisasi jumlah cara untuk mengisi tempat ke-r sebagai [n - (r – 1)] = n – r + 1

Jadi, totalnya tidak. cara untuk mengisi dari tempat pertama hingga tempat ke-r -

$n_{ P_{ r } } = n (n-1) (n-2)..... (n-r + 1)$

$= [n(n-1)(n-2) ... (n-r + 1)] [(n-r)(n-r-1) \dots 3.2.1] / [(n-r)(n-r-1) \dots 3.2.1]$

Karenanya,

$n_{ P_{ r } } = n! / (n-r)!$

Beberapa rumus permutasi penting

• Jika ada n elemen diantaranya$a_1$ adalah sejenis, $a_2$ serupa dari jenis lain; $a_3$ sama dari jenis ketiga dan seterusnya dan $a_r$ adalah dari $r^{th}$ baik, dimana $(a_1 + a_2 + ... a_r) = n$.

  Maka jumlah permutasi dari n objek tersebut adalah = $n! / [(a_1!(a_2!) \dots (a_r!)]$.

• Jumlah permutasi dari n elemen berbeda yang mengambil n elemen sekaligus = $n_{P_n} = n!$

• Banyaknya permutasi dari n elemen berbeda yang mengambil r elemen pada satu waktu, ketika x benda tertentu selalu menempati tempat tertentu = $n-x_{p_{r-x}}$

• Jumlah permutasi dari n elemen yang berbeda ketika r benda tertentu selalu bersatu adalah - $r! (n−r+1)!$

• Jumlah permutasi dari n elemen yang berbeda ketika r hal-hal yang ditentukan tidak pernah bersatu adalah - $n!–[r! (n−r+1)!]$

• Banyaknya permutasi melingkar dari n elemen berbeda yang diambil x elemen pada waktu = $^np_{x}/x$

• Banyaknya permutasi melingkar dari n benda yang berbeda = $^np_{n}/n$

Beberapa masalah

Problem 1 - Dari sekumpulan 6 kartu yang berbeda, berapa banyak cara kita dapat mengubahnya?

Solution - Karena kita mengambil 6 kartu sekaligus dari setumpuk 6 kartu, permutasi akan terjadi $^6P_{6} = 6! = 720$

Problem 2 - Dalam berapa cara susunan huruf pada kata 'READER'?

Solution - Ada 6 huruf word (2 E, 1 A, 1D dan 2R.) Pada kata 'READER'.

Permutasi akan menjadi $= 6! /\: [(2!) (1!)(1!)(2!)] = 180.$

Problem 3 - Bagaimana huruf pada kata 'ORANGE' dapat diatur sehingga konsonan hanya menempati posisi genap?

Solution- Ada 3 vokal dan 3 konsonan pada kata 'ORANGE'. Jumlah cara menyusun konsonan di antara mereka sendiri$= ^3P_{3} = 3! = 6$. 3 tempat kosong yang tersisa akan diisi oleh 3 huruf vokal$^3P_{3} = 3! = 6$cara. Oleh karena itu, jumlah permutasi adalah$6 \times 6 = 36$

Kombinasi

SEBUAH combination adalah pemilihan beberapa elemen yang urutannya tidak menjadi masalah.

Banyaknya kombinasi dari n benda, diambil r sekaligus adalah -

$$^nC_{ { r } } = \frac { n! } { r!(n-r)! }$$

Problem 1

Temukan jumlah himpunan bagian $\lbrace1, 2, 3, 4, 5, 6\rbrace$ memiliki 3 elemen.

Solution

Kardinalitas himpunan adalah 6 dan kita harus memilih 3 elemen dari himpunan. Di sini, pemesanan tidak menjadi masalah. Karenanya, jumlah subset akan menjadi$^6C_{3} = 20$.

Problem 2

Ada 6 pria dan 5 wanita dalam satu ruangan. Dalam berapa cara kita bisa memilih 3 pria dan 2 wanita dari kamar?

Solution

Jumlah cara memilih 3 pria dari 6 pria adalah $^6C_{3}$ dan banyaknya cara memilih 2 wanita dari 5 wanita tersebut $^5C_{2}$

Karenanya, jumlah total cara adalah - $^6C_{3} \times ^5C_{2} = 20 \times 10 = 200$

Problem 3

Berapa banyak cara Anda dapat memilih 3 kelompok berbeda yang terdiri dari 3 siswa dari total 9 siswa?

Solution

Mari kita beri nomor pada kelompok sebagai 1, 2 dan 3

Untuk memilih 3 siswa untuk 1 ^st kelompok, jumlah cara -$^9C_{3}$

Jumlah cara memilih 3 siswa untuk 2 ^nd kelompok setelah memilih kelompok 1 -$^6C_{3}$

Jumlah cara memilih 3 siswa untuk 3 ^rd grup setelah memilih 1 ^st dan 2 ^nd kelompok -$^3C_{3}$

Karenanya, jumlah total cara $= ^9C_{3} \times ^6C_{3} \times ^3C_{3} = 84 \times 20 \times 1 = 1680$

Identitas Pascal

Identitas Pascal yang diturunkan pertama kali oleh Blaise Pascal pada abad ^ke - 17 menyatakan bahwa banyaknya cara pemilihan k unsur dari n unsur sama dengan penjumlahan bilangan cara pemilihan (k-1) unsur dari (n-1) unsur dan jumlah cara untuk memilih elemen dari n-1 elemen.

Secara matematis, untuk bilangan bulat positif k dan n: $^nC_{k} = ^n{^-}^1C_{k-1} + ^n{^-}^1{C_k}$

Proof -

$$^n{^-}^1C_{k-1} + ^n{^-}^1{C_k}$$

$= \frac{ (n-1)! } { (k-1)!(n-k)! } + \frac{ (n-1)! } { k!(n-k-1)! }$

$= (n-1)!(\frac{ k } { k!(n-k)! } + \frac{ n-k } { k!(n-k)! } )$

$= (n-1)! \frac{ n } { k!(n-k)! }$

$= \frac{ n! } { k!(n-k)! }$

$= n_{ C_{ k } }$

Prinsip Pigeonhole

Pada tahun 1834, matematikawan Jerman, Peter Gustav Lejeune Dirichlet, menyatakan prinsip yang disebutnya prinsip laci. Sekarang, ini dikenal sebagai prinsip lubang merpati.

Pigeonhole Principlemenyatakan bahwa jika lubang merpati lebih sedikit dari jumlah total merpati dan setiap merpati dimasukkan ke dalam lubang merpati, maka harus ada setidaknya satu lubang merpati dengan lebih dari satu merpati. Jika n merpati dimasukkan ke dalam m pigeonholes di mana n> m, ada lubang dengan lebih dari satu pigeonholes.

Contoh

• Sepuluh pria berada di sebuah ruangan dan mereka sedang berjabat tangan. Jika setiap orang berjabat tangan setidaknya sekali dan tidak ada orang yang menjabat tangan orang yang sama lebih dari sekali, maka dua orang mengambil bagian dalam jumlah jabat tangan yang sama.

• Setidaknya harus ada dua orang di kelas 30 yang namanya diawali dengan alfabet yang sama.

Prinsip Inklusi-Pengecualian

Itu Inclusion-exclusion principlemenghitung bilangan pokok dari gabungan beberapa set non-disjoint. Untuk dua himpunan A dan B, prinsipnya menyatakan -

$|A \cup B| = |A| + |B| - |A \cap B|$

Untuk tiga himpunan A, B dan C, prinsipnya menyatakan -

$|A \cup B \cup C | = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C |$

Rumus umum -

$|\bigcup_{i=1}^{n}A_i|=\sum\limits_{1\leq i<j<k\leq n}|A_i \cap A_j|+\sum\limits_{1\leq i<j<k\leq n}|A_i \cap A_j \cap A_k|- \dots +(-1)^{\pi-1}|A_1 \cap \dots \cap A_2|$

Problem 1

Berapa banyak bilangan bulat dari 1 hingga 50 yang merupakan kelipatan 2 atau 3 tetapi tidak keduanya?

Solution

Dari 1 hingga 100, ada $50/2 = 25$ bilangan yang merupakan kelipatan 2.

Ada $50/3 = 16$ bilangan yang merupakan kelipatan dari 3.

Ada $50/6 = 8$ angka yang merupakan kelipatan dari 2 dan 3.

Begitu, $|A|=25$, $|B|=16$ dan $|A \cap B|= 8$.

$|A \cup B| = |A| + |B| - |A \cap B| = 25 + 16 - 8 = 33$

Problem 2

Dalam kelompok yang terdiri dari 50 siswa, 24 siswa menyukai minuman dingin dan 36 menyukai minuman panas dan setiap siswa menyukai setidaknya satu dari dua minuman tersebut. Berapa banyak yang menyukai kopi dan teh?

Solution

Misalkan X adalah kelompok siswa yang menyukai minuman dingin dan Y adalah kelompok orang yang menyukai minuman panas.

Begitu, $| X \cup Y | = 50$, $|X| = 24$, $|Y| = 36$

$|X \cap Y| = |X| + |Y| - |X \cup Y| = 24 + 36 - 50 = 60 - 50 = 10$

Makanya, ada 10 siswa yang menyukai teh dan kopi.

Terkait erat dengan konsep penghitungan adalah Probabilitas. Kami sering mencoba menebak hasil dari permainan untung-untungan, seperti permainan kartu, mesin slot, dan lotere; yaitu kami mencoba menemukan kemungkinan atau probabilitas bahwa hasil tertentu dapat diperoleh.

Probabilitydapat dikonseptualisasikan sebagai menemukan peluang terjadinya suatu peristiwa. Secara matematis, ini adalah studi tentang proses acak dan hasilnya. Hukum probabilitas memiliki penerapan yang luas dalam berbagai bidang seperti genetika, ramalan cuaca, jajak pendapat, pasar saham, dll.

Konsep dasar

Teori probabilitas ditemukan pada abad ke-17 oleh dua matematikawan Prancis, Blaise Pascal dan Pierre de Fermat, yang berurusan dengan masalah matematika tentang kebetulan.

Sebelum melanjutkan ke detail probabilitas, mari kita lihat konsep beberapa definisi.

Random Experiment- Eksperimen di mana semua kemungkinan hasil diketahui dan hasil yang tepat tidak dapat diprediksi sebelumnya disebut eksperimen acak. Melempar koin yang adil adalah contoh eksperimen acak.

Sample Space- Saat kami melakukan percobaan, himpunan S dari semua kemungkinan hasil disebut ruang sampel. Jika kita melempar koin, ruang sampelnya$S = \left \{ H, T \right \}$

Event- Setiap subset dari ruang sampel disebut peristiwa. Setelah melempar koin, mendapatkan Kepala di atas adalah sebuah peristiwa.

Kata "probabilitas" berarti peluang terjadinya peristiwa tertentu. Hal terbaik yang bisa kami katakan adalah seberapa besar kemungkinan hal itu terjadi, dengan menggunakan gagasan probabilitas.

$Probability\:of\:occurence\:of\:an\:event = \frac{Total\:number\:of\:favourable \: outcome}{Total\:number\:of\:Outcomes}$

Karena terjadinya peristiwa apa pun bervariasi antara 0% dan 100%, probabilitasnya bervariasi antara 0 dan 1.

Langkah-langkah untuk menemukan probabilitas

Langkah 1 - Hitung semua kemungkinan hasil percobaan.

Langkah 2 - Hitung jumlah hasil yang diinginkan dari percobaan.

Langkah 3 - Terapkan rumus probabilitas yang sesuai.

Melempar Koin

Jika koin dilemparkan, ada dua kemungkinan hasil - Kepala $(H)$ atau Ekor $(T)$

Jadi, Jumlah hasil = 2

Oleh karena itu, kemungkinan mendapatkan Kepala $(H)$ di atas adalah 1/2 dan kemungkinan mendapatkan Tails $(T)$ di atas adalah 1/2

Melempar Dadu

Ketika dadu dilemparkan, enam kemungkinan hasil bisa di atas - $1, 2, 3, 4, 5, 6$.

Probabilitas salah satu angka adalah 1/6

Kemungkinan mendapatkan bilangan genap adalah 3/6 = 1/2

Probabilitas mendapatkan angka ganjil adalah 3/6 = 1/2

Mengambil Kartu Dari Dek

Dari setumpuk 52 kartu, jika satu kartu diambil temukan kemungkinan kartu as yang ditarik dan juga temukan kemungkinan berlian ditarik.

Jumlah total hasil yang mungkin - 52

Hasil menjadi kartu as - 4

Probabilitas menjadi ace = 4/52 = 1/13

Probabilitas menjadi berlian = 13/52 = 1/4

Aksioma Probabilitas

• Probabilitas suatu peristiwa selalu bervariasi dari 0 hingga 1. $[0 \leq P(x) \leq 1]$

• Untuk peristiwa yang tidak mungkin probabilitasnya adalah 0 dan untuk peristiwa tertentu probabilitasnya adalah 1.

• Jika kemunculan suatu peristiwa tidak dipengaruhi oleh peristiwa lain, itu disebut saling eksklusif atau terputus-putus.

  Jika $A_1, A_2....A_n$ adalah acara yang saling eksklusif / terputus-putus $P(A_i \cap A_j) = \emptyset $ untuk $i \ne j$ dan $P(A_1 \cup A_2 \cup.... A_n) = P(A_1) + P(A_2)+..... P(A_n)$

Sifat Probabilitas

• Jika ada dua peristiwa $x$ dan $\overline{x}$yang saling melengkapi, maka kemungkinan acara pelengkap adalah -

  $$p(\overline{x}) = 1-p(x)$$

• Untuk dua peristiwa non-disjoint A dan B, probabilitas penyatuan dua peristiwa -

  $P(A \cup B) = P(A) + P(B)$

• Jika peristiwa A adalah bagian dari peristiwa B lain (mis $A \subset B$), maka probabilitas A kurang dari atau sama dengan probabilitas B. Oleh karena itu, $A \subset B$ menyiratkan $P(A) \leq p(B)$

Probabilitas Bersyarat

Probabilitas bersyarat dari suatu peristiwa B adalah kemungkinan bahwa peristiwa tersebut akan terjadi mengingat peristiwa A telah terjadi. Ini ditulis sebagai$P(B|A)$.

Secara matematis - $ P(B|A) = P(A \cap B)/ P(A)$

Jika peristiwa A dan B saling eksklusif, maka probabilitas bersyarat dari peristiwa B setelah peristiwa A adalah kemungkinan peristiwa B yaitu $P(B)$.

Problem 1

Di suatu negara, 50% dari semua remaja memiliki sepeda dan 30% dari semua remaja memiliki sepeda dan sepeda. Berapa probabilitas seorang remaja memiliki sepeda mengingat remaja tersebut memiliki sepeda?

Solution

Mari kita asumsikan A adalah peristiwa remaja yang hanya memiliki sepeda dan B adalah peristiwa remaja yang hanya memiliki sepeda.

Begitu, $P(A) = 50/100 = 0.5$ dan $P(A \cap B) = 30/100 = 0.3$ dari masalah yang diberikan.

$P(B|A) = P(A \cap B)/ P(A) = 0.3/ 0.5 = 0.6$

Oleh karena itu, probabilitas remaja memiliki sepeda mengingat remaja memiliki sepeda adalah 60%.

Problem 2

Di kelas, 50% dari semua siswa bermain kriket dan 25% dari semua siswa bermain kriket dan bola voli. Berapa probabilitas seorang siswa bermain bola voli mengingat siswa itu bermain kriket?

Solution

Mari kita asumsikan A adalah peristiwa siswa bermain kriket saja dan B adalah peristiwa siswa hanya bermain bola voli.

Begitu, $P(A) = 50/100 =0.5$ dan $P(A \cap B) = 25/ 100 =0.25$ dari masalah yang diberikan.

$P\lgroup B\rvert A \rgroup= P\lgroup A\cap B\rgroup/P\lgroup A \rgroup =0.25/0.5=0.5$

Oleh karena itu, probabilitas seorang siswa bermain bola voli mengingat siswa tersebut bermain kriket adalah 50%.

Problem 3

Enam laptop bagus dan tiga laptop rusak digabungkan. Untuk menemukan laptop yang rusak semuanya diuji satu per satu secara acak. Berapa probabilitas untuk menemukan kedua laptop yang rusak dalam dua pilihan pertama?

Solution

Misalkan A jika kami menemukan laptop yang rusak pada pengujian pertama dan B menjadi peristiwa kami menemukan laptop yang rusak pada pengujian kedua.

Karenanya, $P(A \cap B) = P(A)P(B|A) =3/9 \times 2/8 = 1/12$

Teorema Bayes

Theorem - Jika A dan B adalah dua peristiwa yang saling eksklusif, di mana $P(A)$ adalah probabilitas A dan $P(B)$ adalah probabilitas B, $P(A | B)$ adalah probabilitas A mengingat B benar. $P(B | A)$ adalah probabilitas B mengingat A benar, maka Teorema Bayes menyatakan -

$$P(A|B) = \frac{P(B|A) P(A)}{\sum_{i = 1}^{n}P(B|Ai)P(Ai)}$$

Penerapan Teorema Bayes

• Dalam situasi di mana semua peristiwa ruang sampel adalah peristiwa yang saling eksklusif.

• Dalam situasi di mana baik $P( A_i \cap B )$ untuk setiap $A_i$ atau $P( A_i )$ dan $P(B|A_i)$ untuk setiap $A_i$ dikenal.

Problem

Pertimbangkan tiga tempat pena. Tempat pena pertama berisi 2 pena merah dan 3 pena biru; yang kedua memiliki 3 pena merah dan 2 pena biru; dan yang ketiga memiliki 4 pena merah dan 1 pena biru. Ada kemungkinan yang sama untuk setiap pen-stand untuk dipilih. Jika satu pena ditarik secara acak, berapa probabilitasnya pena merah?

Solution

Membiarkan $A_i$menjadi acara dimana pena-stand yang ^ke - i dipilih.

Di sini, i = 1,2,3.

Karena probabilitas untuk memilih dudukan pena adalah sama, $P(A_i) = 1/3$

Misalkan B adalah kejadian di mana pena merah digambar.

Probabilitas bahwa pena merah dipilih di antara lima pena dari tempat pena pertama,

$P(B|A_1) = 2/5$

Probabilitas bahwa pena merah dipilih di antara lima pena dari tempat pena kedua,

$P(B|A_2) = 3/5$

Probabilitas bahwa pena merah dipilih di antara lima pena dari tempat pena ketiga,

$P(B|A_3) = 4/5$

Menurut Teorema Bayes,

$P(B) = P(A_1).P(B|A_1) + P(A_2).P(B|A_2) + P(A_3).P(B|A_3)$

$= 1/3 . 2/5\: +\: 1/3 . 3/5\: +\: 1/3 . 4/5$

$= 3/5$

Mathematical induction, adalah teknik untuk membuktikan hasil atau membuat pernyataan untuk bilangan asli. Bagian ini mengilustrasikan metode melalui berbagai contoh.

Definisi

Mathematical Induction adalah teknik matematika yang digunakan untuk membuktikan pernyataan, rumus atau teorema benar untuk setiap bilangan asli.

Teknik ini melibatkan dua langkah untuk membuktikan pernyataan, seperti yang dinyatakan di bawah ini -

Step 1(Base step) - Ini membuktikan bahwa pernyataan benar untuk nilai awal.

Step 2(Inductive step)- Ini membuktikan bahwa jika pernyataan tersebut benar untuk n ^th iterasi (atau nomor n ), maka itu juga berlaku untuk (n + 1) ^th iterasi (atau nomor n + 1 ).

Bagaimana cara melakukannya

Step 1- Pertimbangkan nilai awal yang pernyataannya benar. Ini akan ditunjukkan bahwa pernyataan itu benar untuk n = nilai awal.

Step 2- Asumsikan pernyataan itu benar untuk setiap nilai n = k . Kemudian buktikan bahwa pernyataan tersebut benar untuk n = k + 1 . Kita sebenarnya memecah n = k + 1 menjadi dua bagian, satu bagian adalah n = k (yang sudah dibuktikan) dan mencoba membuktikan bagian yang lain.

Masalah 1

$3^n-1$ adalah kelipatan 2 untuk n = 1, 2, ...

Solution

Step 1 - Untuk $n = 1, 3^1-1 = 3-1 = 2$ yang merupakan kelipatan dari 2

Step 2 - Mari kita asumsikan $3^n-1$ benar untuk $n=k$, Karenanya, $3^k -1$ benar (Ini adalah asumsi)

Kami harus membuktikannya $3^{k+1}-1$ juga merupakan kelipatan 2

$3^{k+1} - 1 = 3 \times 3^k - 1 = (2 \times 3^k) + (3^k - 1)$

Bagian pertama $(2 \times 3k)$ pasti kelipatan 2 dan bagian kedua $(3k -1)$ juga benar seperti asumsi kita sebelumnya.

Karenanya, $3^{k+1} – 1$ adalah kelipatan dari 2.

Jadi, terbukti itu $3^n – 1$ adalah kelipatan dari 2.

Masalah 2

$1 + 3 + 5 + ... + (2n-1) = n^2$ untuk $n = 1, 2, \dots $

Solution

Step 1 - Untuk $n=1, 1 = 1^2$, Oleh karena itu, langkah 1 terpenuhi.

Step 2 - Mari kita asumsikan pernyataan itu benar $n=k$.

Karenanya, $1 + 3 + 5 + \dots + (2k-1) = k^2$ benar (Ini adalah asumsi)

Kami harus membuktikannya $1 + 3 + 5 + ... + (2(k+1)-1) = (k+1)^2$ juga memegang

$1 + 3 + 5 + \dots + (2(k+1) - 1)$

$= 1 + 3 + 5 + \dots + (2k+2 - 1)$

$= 1 + 3 + 5 + \dots + (2k + 1)$

$= 1 + 3 + 5 + \dots + (2k - 1) + (2k + 1)$

$= k^2 + (2k + 1)$

$= (k + 1)^2$

Begitu, $1 + 3 + 5 + \dots + (2(k+1) - 1) = (k+1)^2$ tahan yang memenuhi langkah 2.

Karenanya, $1 + 3 + 5 + \dots + (2n - 1) = n^2$ terbukti.

Masalah 3

Buktikan itu $(ab)^n = a^nb^n$ benar untuk setiap bilangan asli $n$

Solution

Step 1 - Untuk $n=1, (ab)^1 = a^1b^1 = ab$, Oleh karena itu, langkah 1 terpenuhi.

Step 2 - Mari kita asumsikan pernyataan itu benar $n=k$, Karenanya, $(ab)^k = a^kb^k$ benar (Ini adalah asumsi).

Kami harus membuktikannya $(ab)^{k+1} = a^{k+1}b^{k+1}$ juga tahan

Diberikan, $(ab)^k = a^k b^k$

Atau, $(ab)^k (ab) = (a^k b^k ) (ab)$ [Mengalikan kedua sisi dengan 'ab']

Atau, $(ab)^{k+1} = (aa^k) ( bb^k)$

Atau, $(ab)^{k+1} = (a^{k+1}b^{k+1})$

Oleh karena itu, langkah 2 dibuktikan.

Begitu, $(ab)^n = a^nb^n$ benar untuk setiap bilangan asli n.

Induksi Kuat

Induksi Kuat adalah bentuk lain dari induksi matematika. Melalui teknik induksi ini, kita dapat membuktikan bahwa fungsi proposisional,$P(n)$ benar untuk semua bilangan bulat positif, $n$, menggunakan langkah-langkah berikut -

• Step 1(Base step) - Ini membuktikan bahwa proposisi awal $P(1)$ benar.

• Step 2(Inductive step) - Ini membuktikan bahwa pernyataan bersyarat $[P(1) \land P(2) \land P(3) \land \dots \land P(k)] → P(k + 1)$ benar untuk bilangan bulat positif $k$.

Dalam bab ini, kita akan membahas bagaimana teknik rekursif dapat memperoleh urutan dan digunakan untuk menyelesaikan masalah penghitungan. Prosedur untuk menemukan suku-suku urutan secara rekursif disebutrecurrence relation. Kami mempelajari teori hubungan kekambuhan linier dan solusinya. Akhirnya, kami memperkenalkan fungsi pembangkit untuk menyelesaikan hubungan pengulangan.

Definisi

Relasi perulangan adalah persamaan yang secara rekursif mendefinisikan urutan di mana suku berikutnya adalah fungsi dari suku-suku sebelumnya (Mengekspresikan $F_n$ sebagai kombinasi dari $F_i$ dengan $i < n$).

Example - Deret Fibonacci - $F_n = F_{n-1} + F_{n-2}$, Menara Hanoi - $F_n = 2F_{n-1} + 1$

Hubungan Perulangan Linier

Persamaan pengulangan linier derajat k atau orde k adalah persamaan pengulangan yang ada dalam format $x_n= A_1 x_{n-1}+ A_2 x_{n-1}+ A_3 x_{n-1}+ \dots A_k x_{n-k} $($A_n$ adalah konstanta dan $A_k \neq 0$) pada urutan angka sebagai polinomial tingkat pertama.

Ini adalah beberapa contoh persamaan pengulangan linier -

Relasi perulangan	Nilai awal	Solusi
F n = F n-1 + F n-2	a 1 = a 2 = 1	Angka Fibonacci
F n = F n-1 + F n-2	a 1 = 1, a 2 = 3	Nomor Lucas
F n = F n-2 + F n-3	a 1 = a 2 = a 3 = 1	Urutan Padovan
F n = 2F n-1 + F n-2	a 1 = 0, a 2 = 1	Nomor pell

Bagaimana mengatasi hubungan kekambuhan linier

Misalkan, dua relasi perulangan linier yang teratur adalah - $F_n = AF_{n-1} +BF_{n-2}$ dimana A dan B adalah bilangan real.

Persamaan karakteristik untuk relasi perulangan di atas adalah -

$$x^2 - Ax - B = 0$$

Tiga kasus dapat terjadi saat menemukan akar -

Case 1 - Jika faktor persamaan ini sebagai $(x- x_1)(x- x_1) = 0$ dan menghasilkan dua akar nyata yang berbeda $x_1$ dan $x_2$, kemudian $F_n = ax_1^n+ bx_2^n$adalah solusinya. [Di sini, a dan b adalah konstanta]

Case 2 - Jika faktor persamaan ini sebagai $(x- x_1)^2 = 0$ dan menghasilkan akar tunggal yang nyata $x_1$, kemudian $F_n = a x_1^n+ bn x_1^n$ adalah solusinya.

Case 3 - Jika persamaan menghasilkan dua akar kompleks yang berbeda, $x_1$ dan $x_2$ dalam bentuk kutub $x_1 = r \angle \theta$ dan $x_2 = r \angle(- \theta)$, kemudian $F_n = r^n (a cos(n\theta)+ b sin(n\theta))$ adalah solusinya.

Problem 1

Selesaikan hubungan perulangan $F_n = 5F_{n-1} - 6F_{n-2}$ dimana $F_0 = 1$ dan $F_1 = 4$

Solution

Persamaan karakteristik dari relasi perulangan adalah -

$$x^2 - 5x + 6 = 0,$$

Begitu, $(x - 3) (x - 2) = 0$

Oleh karena itu, akarnya adalah -

$x_1 = 3$ dan $x_2 = 2$

Akarnya nyata dan berbeda. Jadi, ini dalam bentuk kasus 1

Oleh karena itu, solusinya adalah -

$$F_n = ax_1^n + bx_2^n$$

Sini, $F_n = a3^n + b2^n\ (As\ x_1 = 3\ and\ x_2 = 2)$

Karena itu,

$1 = F_0 = a3^0 + b2^0 = a+b$

$4 = F_1 = a3^1 + b2^1 = 3a+2b$

Memecahkan dua persamaan ini, kita dapatkan $ a = 2$ dan $b = -1$

Oleh karena itu, solusi akhirnya adalah -

$$F_n = 2.3^n + (-1) . 2^n = 2.3^n - 2^n $$

Problem 2

Selesaikan relasi pengulangan - $F_n = 10F_{n-1} - 25F_{n-2}$ dimana $F_0 = 3$ dan $F_1 = 17$

Solution

Persamaan karakteristik dari relasi perulangan adalah -

$$ x^2 - 10x -25 = 0$$

Begitu $(x - 5)^2 = 0$

Karenanya, hanya ada satu akar nyata $x_1 = 5$

Karena ada satu akar bernilai riil, ini dalam bentuk kasus 2

Oleh karena itu, solusinya adalah -

$F_n = ax_1^n + bnx_1^n$

$3 = F_0 = a.5^0 +(b)(0.5)^0 = a$

$17 = F_1 = a.5^1 + b.1.5^1 = 5a+5b$

Memecahkan dua persamaan ini, kita dapatkan $a = 3$ dan $b = 2/5$

Oleh karena itu, solusi akhirnya adalah - $F_n = 3.5^n +( 2/5) .n.2^n $

Problem 3

Selesaikan hubungan perulangan $F_n = 2F_{n-1} - 2F_{n-2}$ dimana $F_0 = 1$ dan $F_1 = 3$

Solution

Persamaan karakteristik dari relasi perulangan adalah -

$$x^2 -2x -2 = 0$$

Oleh karena itu, akarnya adalah -

$x_1 = 1 + i$ dan $x_2 = 1 - i$

Dalam bentuk kutub,

$x_1 = r \angle \theta$ dan $x_2 = r \angle(- \theta),$ dimana $r = \sqrt 2$ dan $\theta = \frac{\pi}{4}$

Akarnya adalah khayalan. Jadi, ini dalam bentuk kasus 3.

Oleh karena itu, solusinya adalah -

$F_n = (\sqrt 2 )^n (a cos(n .\sqcap /4) + b sin(n .\sqcap /4))$

$1 = F_0 = (\sqrt 2 )^0 (a cos(0 .\sqcap /4) + b sin(0 .\sqcap /4) ) = a$

$3 = F_1 = (\sqrt 2 )^1 (a cos(1 .\sqcap /4) + b sin(1 . \sqcap /4) ) = \sqrt 2 ( a/ \sqrt 2 + b/ \sqrt 2)$

Memecahkan dua persamaan ini kita dapatkan $a = 1$ dan $b = 2$

Oleh karena itu, solusi akhirnya adalah -

$F_n = (\sqrt 2 )^n (cos(n .\pi /4 ) + 2 sin(n .\pi /4 ))$

Relasi Pengulangan Non-Homogen dan Solusi Khusus

Relasi pengulangan disebut non-homogen jika sudah berbentuk

$F_n = AF_{n-1} + BF_{n-2} + f(n)$ dimana $f(n) \ne 0$

Hubungan pengulangan homogen yang terkait adalah $F_n = AF_{n–1} + BF_{n-2}$

Solusinya $(a_n)$ dari hubungan perulangan non-homogen memiliki dua bagian.

Bagian pertama adalah solusinya $(a_h)$ dari hubungan pengulangan homogen terkait dan bagian kedua adalah solusi khusus $(a_t)$.

$$a_n=a_h+a_t$$

Solusi untuk bagian pertama dilakukan dengan menggunakan prosedur yang dibahas di bagian sebelumnya.

Untuk menemukan solusi tertentu, kami menemukan solusi uji coba yang sesuai.

Membiarkan $f(n) = cx^n$; membiarkan$x^2 = Ax + B$ menjadi persamaan karakteristik dari hubungan pengulangan homogen terkait dan biarkan $x_1$ dan $x_2$ menjadi akarnya.

• Jika $x \ne x_1$ dan $x \ne x_2$, kemudian $a_t = Ax^n$

• Jika $x = x_1$, $x \ne x_2$, kemudian $a_t = Anx^n$

• Jika $x = x_1 = x_2$, kemudian $a_t = An^2x^n$

Contoh

Biarkan relasi perulangan yang tidak homogen $F_n = AF_{n–1} + BF_{n-2} + f(n)$ dengan akar yang khas $x_1 = 2$ dan $x_2 = 5$. Solusi uji coba untuk berbagai kemungkinan nilai$f(n)$ adalah sebagai berikut -