Matematyka dyskretna - szybki przewodnik

Matematykę można ogólnie podzielić na dwie kategorie -

  • Continuous Mathematics- Opiera się na ciągłej osi liczbowej lub liczbach rzeczywistych. Charakteryzuje się tym, że między dowolnymi dwiema liczbami prawie zawsze znajduje się nieskończony zbiór liczb. Na przykład funkcję w matematyce ciągłej można wykreślić gładką krzywą bez przerw.

  • Discrete Mathematics- Obejmuje różne wartości; tzn. między dowolnymi dwoma punktami znajduje się policzalna liczba punktów. Na przykład, jeśli mamy skończony zbiór obiektów, funkcję można zdefiniować jako listę uporządkowanych par posiadających te obiekty i można ją przedstawić jako pełną listę tych par.

Tematy w matematyce dyskretnej

Chociaż nie może istnieć określona liczba działów matematyki dyskretnej, prawie zawsze w każdym opracowaniu dotyczącym tej kwestii poruszane są następujące tematy:

  • Zbiory, relacje i funkcje
  • Logika matematyczna
  • Teoria grup
  • Teoria liczenia
  • Probability
  • Relacje indukcji matematycznej i nawrotu
  • Teoria grafów
  • Trees
  • Algebra Boole'a

Omówimy każdą z tych koncepcji w kolejnych rozdziałach tego samouczka.

Niemiecki matematyk G. Cantorwprowadził pojęcie zbiorów. Zbiór zdefiniował jako zbiór określonych i rozróżnialnych obiektów wybranych za pomocą pewnych reguł lub opisu.

SetTeoria stanowi podstawę kilku innych dziedzin nauki, takich jak teoria liczenia, relacje, teoria grafów i maszyny skończone. W tym rozdziale omówimy różne aspektySet Theory.

Zestaw - definicja

Zestaw to nieuporządkowana kolekcja różnych elementów. Zestaw można napisać jawnie, wypisując jego elementy za pomocą nawiasu ustalającego. Zmiana kolejności elementów lub powtórzenie dowolnego elementu zestawu nie powoduje żadnych zmian w zestawie.

Kilka przykładów zestawów

  • Zbiór wszystkich dodatnich liczb całkowitych
  • Zbiór wszystkich planet Układu Słonecznego
  • Zestawienie wszystkich stanów w Indiach
  • Zbiór wszystkich małych liter alfabetu

Reprezentacja zestawu

Zestawy można przedstawić na dwa sposoby -

  • Lista lub forma tabelaryczna
  • Ustaw notację konstruktora

Lista lub forma tabelaryczna

Zestaw jest reprezentowany przez wylistowanie wszystkich elementów, które go tworzą. Elementy są ujęte w nawiasy i oddzielone przecinkami.

Example 1 - zestaw samogłosek w alfabecie angielskim, $A = \lbrace a,e,i,o,u \rbrace$

Example 2 - zbiór liczb nieparzystych mniejszych niż 10, $B = \lbrace 1,3,5,7,9 \rbrace$

Ustaw notację konstruktora

Zestaw jest definiowany przez określenie właściwości, które elementy zestawu mają wspólną. Zestaw jest opisany jako$A = \lbrace x : p(x) \rbrace$

Example 1 - Komplet $\lbrace a,e,i,o,u \rbrace$ jest napisane jako -

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

Example 2 - Komplet $\lbrace 1,3,5,7,9 \rbrace$ jest napisane jako -

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

Jeśli element x należy do dowolnego zbioru S, jest oznaczany przez $x \in S$ a jeśli element y nie jest członkiem zbioru S, jest oznaczony przez $y \notin S$.

Example- Jeśli$S = \lbrace1, 1.2, 1.7, 2\rbrace , 1 \in S$ ale $1.5 \notin S$

Kilka ważnych zestawów

N - zbiór wszystkich liczb naturalnych = $\lbrace1, 2, 3, 4, .....\rbrace$

Z - zbiór wszystkich liczb całkowitych = $\lbrace....., -3, -2, -1, 0, 1, 2, 3, .....\rbrace$

Z+ - zbiór wszystkich dodatnich liczb całkowitych

Q - zbiór wszystkich liczb wymiernych

R - zbiór wszystkich liczb rzeczywistych

W - zbiór wszystkich liczb całkowitych

Liczność zbioru

Liczność zbioru S, oznaczona przez $|S|$, to liczba elementów zbioru. Liczba jest również nazywana liczbą kardynalną. Jeśli zbiór ma nieskończoną liczbę elementów, jego liczność wynosi$\infty$.

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

Jeśli istnieją dwa zbiory X i Y,

  • $|X| = |Y|$oznacza dwa zbiory X i Y o tej samej liczności. Występuje, gdy liczba elementów w X jest dokładnie równa liczbie elementów w Y. W tym przypadku istnieje funkcja bijektywna „f” od X do Y.

  • $|X| \le |Y|$oznacza, że ​​liczność zbioru X jest mniejsza lub równa liczności zbioru Y. Występuje, gdy liczba elementów w X jest mniejsza lub równa liczbie Y. Tutaj istnieje funkcja iniekcyjna „f” od X do Y.

  • $|X| \lt |Y|$oznacza, że ​​liczność zbioru X jest mniejsza niż liczność zbioru Y. Występuje, gdy liczba elementów w X jest mniejsza niż liczba w Y. Tutaj funkcja „f” od X do Y jest funkcją iniekcyjną, ale nie bijektywną.

  • $If\ |X| \le |Y|$ i $|X| \ge |Y|$ następnie $|X| = |Y|$. Zbiory X i Y są powszechnie nazywane zbiorami równoważnymi.

Rodzaje zestawów

Zestawy można podzielić na wiele typów. Niektóre z nich są skończone, nieskończone, podzbiór, uniwersalny, właściwy, pojedynczy zbiór itp.

Zbiór skończony

Zbiór zawierający określoną liczbę elementów nazywany jest zbiorem skończonym.

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

Nieskończony zestaw

Zbiór zawierający nieskończoną liczbę elementów nazywany jest nieskończonym zbiorem.

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

Podzbiór

Zbiór X to podzbiór zbioru Y (zapisany jako $X \subseteq Y$) jeśli każdy element X jest elementem zbioru Y.

Example 1 - Niech, $X = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$ i $Y = \lbrace 1, 2 \rbrace$. Tutaj zbiór Y jest podzbiorem zbioru X, ponieważ wszystkie elementy zbioru Y są w zbiorze X. Stąd możemy napisać$Y \subseteq X$.

Example 2 - Niech, $X = \lbrace 1, 2, 3 \rbrace$ i $Y = \lbrace 1, 2, 3 \rbrace$. Tutaj zbiór Y jest podzbiorem (niewłaściwym podzbiorem) zbioru X, ponieważ wszystkie elementy zbioru Y znajdują się w zbiorze X. Zatem możemy napisać$Y \subseteq X$.

Właściwy podzbiór

Termin „właściwy podzbiór” można zdefiniować jako „podzbiór, ale nie równy”. Zbiór X to właściwy podzbiór zbioru Y (zapisany jako$ X \subset Y $) jeśli każdy element X jest elementem zbioru Y i $|X| \lt |Y|$.

Example - Niech, $X = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$ i $Y = \lbrace 1, 2 \rbrace$. Tutaj zestaw$Y \subset X$ ponieważ wszystkie elementy w $Y$ są zawarte w $X$ też i $X$ ma co najmniej jeden element jest więcej niż ustawiony $Y$.

Uniwersalny zestaw

Jest to zbiór wszystkich elementów w określonym kontekście lub aplikacji. Wszystkie zbiory w tym kontekście lub zastosowaniu są zasadniczo podzbiorami tego uniwersalnego zbioru. Zestawy uniwersalne są reprezentowane jako$U$.

Example - Możemy zdefiniować $U$jako zbiór wszystkich zwierząt na ziemi. W tym przypadku zbiór wszystkich ssaków jest podzbiorem$U$, zbiór wszystkich ryb jest podzbiorem $U$, zbiór wszystkich owadów jest podzbiorem $U$, i tak dalej.

Pusty zestaw lub pusty zestaw

Pusty zestaw nie zawiera żadnych elementów. Jest oznaczony$\emptyset$. Ponieważ liczba elementów w pustym zbiorze jest skończona, pusty zbiór jest zbiorem skończonym. Liczność zestawu pustego lub zestawu zerowego wynosi zero.

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

Zestaw singletonów lub zestaw jednostek

Zestaw singletonów lub zestaw jednostek zawiera tylko jeden element. Zbiór singletonów jest oznaczony przez$\lbrace s \rbrace$.

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

Równy zestaw

Jeśli dwa zbiory zawierają te same elementy, mówi się, że są równe.

Example - Jeśli $A = \lbrace 1, 2, 6 \rbrace$ i $B = \lbrace 6, 1, 2 \rbrace$są równe, ponieważ każdy element zbioru A jest elementem zbioru B, a każdy element zbioru B jest elementem zbioru A.

Równoważny zestaw

Jeśli liczności dwóch zbiorów są takie same, nazywane są zbiorami równoważnymi.

Example - Jeśli $A = \lbrace 1, 2, 6 \rbrace$ i $B = \lbrace 16, 17, 22 \rbrace$, są równoważne, ponieważ liczność A jest równa liczności B. tj $|A| = |B| = 3$

Nakładający się zestaw

Dwa zestawy, które mają co najmniej jeden wspólny element, nazywane są zestawami nakładającymi się.

W przypadku nakładania się zestawów -

  • $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 - Niech, $A = \lbrace 1, 2, 6 \rbrace$ i $B = \lbrace 6, 12, 42 \rbrace$. Istnieje wspólny element „6”, stąd te zbiory są zbiorami nakładającymi się.

Zestaw rozłączny

Dwa zbiory A i B nazywane są zbiorami rozłącznymi, jeśli nie mają ani jednego wspólnego elementu. Dlatego rozłączne zbiory mają następujące właściwości -

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

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

Example - Niech, $A = \lbrace 1, 2, 6 \rbrace$ i $B = \lbrace 7, 9, 14 \rbrace$, nie ma ani jednego wspólnego elementu, dlatego te zbiory są nakładającymi się zbiorami.

Diagramy Venna

Diagram Venna, wynaleziony w 1880 roku przez Johna Venna, jest schematem pokazującym wszystkie możliwe relacje logiczne między różnymi zbiorami matematycznymi.

Examples

Operacje na zbiorach

Operacje na zbiorach obejmują sumę zbioru, przecięcie zbioru, różnicę zbioru, dopełnienie zbioru i iloczyn kartezjański.

Ustaw Union

Suma zbiorów A i B (oznaczona przez $A \cup B$) jest zbiorem elementów znajdujących się w A, B lub w A i B. Stąd $A \cup B = \lbrace x \:| \: x \in A\ OR\ x \in B \rbrace$.

Example - Jeśli $A = \lbrace 10, 11, 12, 13 \rbrace$ i B = $\lbrace 13, 14, 15 \rbrace$, następnie $A \cup B = \lbrace 10, 11, 12, 13, 14, 15 \rbrace$. (Wspólny element występuje tylko raz)

Ustaw przecięcie

Przecięcie zbiorów A i B (oznaczone $A \cap B$) jest zbiorem elementów, które znajdują się zarówno w A, jak i B.W związku z tym $A \cap B = \lbrace x \:|\: x \in A\ AND\ x \in B \rbrace$.

Example - Jeśli $A = \lbrace 11, 12, 13 \rbrace$ i $B = \lbrace 13, 14, 15 \rbrace$, następnie $A \cap B = \lbrace 13 \rbrace$.

Ustaw różnicę / względne dopełnienie

Różnica zbiorów A i B (oznaczona przez $A – B$) jest zbiorem elementów, które są tylko w A, ale nie w B. Stąd $A - B = \lbrace x \:| \: x \in A\ AND\ x \notin B \rbrace$.

Example - Jeśli $A = \lbrace 10, 11, 12, 13 \rbrace$ i $B = \lbrace 13, 14, 15 \rbrace$, następnie $(A - B) = \lbrace 10, 11, 12 \rbrace$ i $(B - A) = \lbrace 14, 15 \rbrace$. Tutaj widzimy$(A - B) \ne (B - A)$

Uzupełnienie zestawu

Uzupełnienie zbioru A (oznaczone $A’$) to zbiór elementów, których nie ma w zbiorze A. $A' = \lbrace x | x \notin A \rbrace$.

Dokładniej, $A'= (U - A)$ gdzie $U$ to uniwersalny zestaw zawierający wszystkie obiekty.

Example - Jeśli $A = \lbrace x \:| \: x\ \: {belongs\: to\: set\: of\: odd \:integers} \rbrace$ następnie $A' = \lbrace y\: | \: y\ \: {does\: not\: belong\: to\: set\: of\: odd\: integers } \rbrace$

Iloczyn kartezjański / Iloczyn poprzeczny

Iloczyn kartezjański n liczby zbiorów $A_1, A_2, \dots A_n$ oznaczony jako $A_1 \times A_2 \dots \times A_n$ można zdefiniować jako wszystkie możliwe uporządkowane pary $(x_1, x_2, \dots x_n)$ gdzie $x_1 \in A_1, x_2 \in A_2, \dots x_n \in A_n$

Example - Jeśli weźmiemy dwa zestawy $A = \lbrace a, b \rbrace$ i $B = \lbrace 1, 2 \rbrace$,

Iloczyn kartezjański A i B jest zapisywany jako - $A \times B = \lbrace (a, 1), (a, 2), (b, 1), (b, 2)\rbrace$

Iloczyn kartezjański B i A jest zapisywany jako - $B \times A = \lbrace (1, a), (1, b), (2, a), (2, b)\rbrace$

Zestaw zasilający

Zbiór potęgowy zbioru S to zbiór wszystkich podzbiorów zbioru S, w tym zbiór pusty. Liczność zbioru potęg ze zbioru S o liczności n wynosi$2^n$. Zestaw mocy oznaczono jako$P(S)$.

Example −

Na zestaw $S = \lbrace a, b, c, d \rbrace$ obliczmy podzbiory -

  • Podzbiory zawierające 0 elementów - $\lbrace \emptyset \rbrace$ (pusty zestaw)

  • Podzbiory z 1 elementem - $\lbrace a \rbrace, \lbrace b \rbrace, \lbrace c \rbrace, \lbrace d \rbrace$

  • Podzbiory z 2 elementami - $\lbrace a, b \rbrace, \lbrace a,c \rbrace, \lbrace a, d \rbrace, \lbrace b, c \rbrace, \lbrace b,d \rbrace,\lbrace c,d \rbrace$

  • Podzbiory z 3 elementami - $\lbrace a ,b, c\rbrace,\lbrace a, b, d \rbrace, \lbrace a,c,d \rbrace,\lbrace b,c,d \rbrace$

  • Podzbiory z 4 elementami - $\lbrace a, b, c, d \rbrace$

W związku z tym, $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 - Moc zestawu pustego jest również zestawem pustym.

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

Partycjonowanie zbioru

Podział zbioru, powiedzmy S , jest zbiorem n rozłącznych podzbiorów, powiedzmy$P_1, P_2, \dots P_n$ który spełnia następujące trzy warunki -

  • $P_i$ nie zawiera pustego zestawu.

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

  • Suma podzbiorów musi być równa całemu oryginalnemu zestawowi.

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

  • Przecięcie dowolnych dwóch różnych zestawów jest puste.

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

Example

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

Prawdopodobne partycjonowanie to $\lbrace a \rbrace, \lbrace b, c, d \rbrace, \lbrace e, f, g, h \rbrace$

Innym prawdopodobnym podziałem jest $\lbrace a, b \rbrace, \lbrace c, d \rbrace, \lbrace e, f, g, h \rbrace$

Numery dzwonków

Liczby dzwonków podają liczbę sposobów podziału zestawu. Są oznaczone$B_n$ gdzie n jest licznością zbioru.

Example -

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

Alternatywne partycje to -

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$

W związku z tym $B_3 = 5$

Ilekroć dyskutuje się o zbiorach, następną rzeczą, która się pojawia, jest relacja między elementami zbiorów. Relations może istnieć między obiektami tego samego zestawu lub między obiektami dwóch lub więcej zestawów.

Definicja i właściwości

Relacja binarna R ze zbioru x do y (zapisana jako $xRy$ lub $R(x,y)$) jest podzbiorem iloczynu kartezjańskiego $x \times y$. Jeśli uporządkowana para G jest odwrócona, relacja również się zmienia.

Ogólnie rzecz biorąc, relacja n-arna R między zbiorami $A_1, \dots ,\ and\ A_n$ jest podzbiorem iloczynu n-składowego $A_1 \times \dots \times A_n$. Minimalna liczność relacji R wynosi zero, a maksymalna wynosi$n^2$ w tym przypadku.

Binarna relacja R na jednym zbiorze A jest podzbiorem $A \times A$.

Dla dwóch różnych zbiorów, A i B, o liczności odpowiednio m i n , maksymalna liczność relacji R od A do B wynosi mn .

Dziedzina i zakres

Jeśli istnieją dwa zbiory A i B, a relacja R ma parę porządkową (x, y), to -

  • Plik domain z R, Dom (R), jest zbiorem $\lbrace x \:| \: (x, y) \in R \:for\: some\: y\: in\: B \rbrace$

  • Plik range z R, Ran (R), jest zbiorem $\lbrace y\: |\: (x, y) \in R \:for\: some\: x\: in\: A\rbrace$

Przykłady

Pozwolić, $A = \lbrace 1, 2, 9 \rbrace $ i $ B = \lbrace 1, 3, 7 \rbrace$

  • Przypadek 1 - Jeśli relacja R jest „równa” to $R = \lbrace (1, 1), (3, 3) \rbrace$

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

  • Przypadek 2 - Jeśli relacja R jest „mniejsza niż” wtedy $R = \lbrace (1, 3), (1, 7), (2, 3), (2, 7) \rbrace$

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

  • Przypadek 3 - Jeśli relacja R jest „większa niż” to $R = \lbrace (2, 1), (9, 1), (9, 3), (9, 7) \rbrace$

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

Reprezentacja relacji za pomocą wykresu

Relację można przedstawić za pomocą skierowanego wykresu.

Liczba wierzchołków na grafie jest równa liczbie elementów w zbiorze, z którego została zdefiniowana relacja. Dla każdej uporządkowanej pary (x, y) w relacji R będzie skierowana krawędź od wierzchołka „x” do wierzchołka „y”. Jeśli istnieje uporządkowana para (x, x), na wierzchołku „x” powstanie pętla własna.

Załóżmy, że istnieje związek $R = \lbrace (1, 1), (1,2), (3, 2) \rbrace$ na planie $S = \lbrace 1, 2, 3 \rbrace$można to przedstawić na poniższym wykresie -

Rodzaje relacji

  • Plik Empty Relation między zbiorami X i Y, lub na E, jest zbiorem pustym $\emptyset$

  • Plik Full Relation między zestawami X i Y jest zbiorem $X \times Y$

  • Plik Identity Relation na zbiorze X to zbiór $\lbrace (x, x) | x \in X \rbrace$

  • Relacja odwrotna R 'relacji R jest zdefiniowana jako - $R' = \lbrace (b, a) | (a, b) \in R \rbrace$

    Example - Jeśli $R = \lbrace (1, 2), (2, 3) \rbrace$ następnie $R' $ będzie $\lbrace (2, 1), (3, 2) \rbrace$

  • Wywoływana jest relacja R na zbiorze A. Reflexive gdyby $\forall a \in A$ jest powiązany z (trzyma aRa)

    Example - Relacja $R = \lbrace (a, a), (b, b) \rbrace$ na planie $X = \lbrace a, b \rbrace$ jest refleksyjny.

  • Wywoływana jest relacja R na zbiorze A. Irreflexive Jeśli nie $a \in A$ jest powiązany z (aRa nie zachowuje się).

    Example - Relacja $R = \lbrace (a, b), (b, a) \rbrace$ na planie $X = \lbrace a, b \rbrace$ jest nierefleksyjna.

  • Wywoływana jest relacja R na zbiorze A. Symmetric gdyby $xRy$ sugeruje $yRx$, $\forall x \in A$ i $\forall y \in A$.

    Example - Relacja $R = \lbrace (1, 2), (2, 1), (3, 2), (2, 3) \rbrace$ na planie $A = \lbrace 1, 2, 3 \rbrace$ jest symetryczny.

  • Wywoływana jest relacja R na zbiorze A. Anti-Symmetric gdyby $xRy$ i $yRx$ sugeruje $x = y \: \forall x \in A$ i $\forall y \in A$.

    Example - Relacja $R = \lbrace (x, y)\to N |\:x \leq y \rbrace$ jest antysymetryczny od tego czasu $x \leq y$ i $y \leq x$ sugeruje $x = y$.

  • Wywoływana jest relacja R na zbiorze A. Transitive gdyby $xRy$ i $yRz$ sugeruje $xRz, \forall x,y,z \in A$.

    Example - Relacja $R = \lbrace (1, 2), (2, 3), (1, 3) \rbrace$ na planie $A = \lbrace 1, 2, 3 \rbrace$ jest przechodnia.

  • Relacja to Equivalence Relation jeśli jest zwrotny, symetryczny i przechodni.

    Example - Relacja $R = \lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2), (1,3), (3,1) \rbrace$ na planie $A = \lbrace 1, 2, 3 \rbrace$ jest relacją równoważności, ponieważ jest zwrotna, symetryczna i przechodnia.

ZA Functionprzypisuje każdemu elementowi zestawu dokładnie jeden element powiązanego zestawu. Funkcje znajdują zastosowanie w różnych dziedzinach, takich jak reprezentacja złożoności obliczeniowej algorytmów, liczenie obiektów, badanie sekwencji i łańcuchów, by wymienić tylko kilka. Trzeci i ostatni rozdział tej części podkreśla ważne aspekty funkcji.

Funkcja - definicja

Funkcja lub mapowanie (zdefiniowane jako $f: X \rightarrow Y$) to relacja między elementami jednego zbioru X a elementami innego zbioru Y (X i Y to niepuste zbiory). X nazywa się Domeną, a Y nazywa się Codomena funkcji „f”.

Funkcja „f” jest relacją na X i Y taką, że dla każdego $x \in X$istnieje wyjątkowy $y \in Y$ takie że $(x,y) \in R$. „x” nazywa się obrazem wstępnym, a „y” obrazem funkcji f.

Funkcją może być jeden do jednego lub wiele do jednego, ale nie jeden do wielu.

Funkcja iniekcyjna / jeden do jednego

Funkcja $f: A \rightarrow B$ jest funkcją iniekcyjną lub jeden do jednego, jeśli dla każdego $b \in B$istnieje najwyżej jeden $a \in A$ takie że $f(s) = t$.

Oznacza to funkcję f jest do wstrzyknięcia, jeśli $a_1 \ne a_2$ sugeruje $f(a1) \ne f(a2)$.

Przykład

  • $f: N \rightarrow N, f(x) = 5x$ jest iniekcyjny.

  • $f: N \rightarrow N, f(x) = x^2$ jest iniekcyjny.

  • $f: R\rightarrow R, f(x) = x^2$ nie jest do wstrzykiwań jako $(-x)^2 = x^2$

Funkcja surjektywna / na

Funkcja $f: A \rightarrow B$jest suriektywna (na), jeśli obraz f jest równy jego zakresowi. Odpowiednio dla każdego$b \in B$istnieje kilka $a \in A$ takie że $f(a) = b$. Oznacza to, że dla dowolnego y w B istnieje takie x w A$y = f(x)$.

Przykład

  • $f : N \rightarrow N, f(x) = x + 2$ jest surjektywna.

  • $f : R \rightarrow R, f(x) = x^2$ nie jest suriektywna, ponieważ nie możemy znaleźć liczby rzeczywistej, której kwadrat jest ujemny.

Bijective / One-to-one Correspondent

Funkcja $f: A \rightarrow B$ jest bijektywnym lub korespondentem jeden do jednego wtedy i tylko wtedy, gdy f jest zarówno iniekcyjna, jak i suriekcyjna.

Problem

Udowodnij, że funkcja $f: R \rightarrow R$ określony przez $f(x) = 2x – 3$ jest funkcją bijektywną.

Explanation - Musimy udowodnić, że ta funkcja jest zarówno iniekcyjna, jak i suriektywna.

Gdyby $f(x_1) = f(x_2)$, następnie $2x_1 – 3 = 2x_2 – 3 $ i to implikuje $x_1 = x_2$.

Stąd f jest injective.

Tutaj, $2x – 3= y$

Więc, $x = (y+5)/3$ który należy do R i $f(x) = y$.

Stąd f jest surjective.

Od f jest zarówno surjective i injective, możemy powiedzieć f jest bijective.

Odwrotność funkcji

Plik inverse odpowiadającej funkcji jeden do jednego $f : A \rightarrow B$, jest funkcją $g : B \rightarrow A$posiadający następujący majątek -

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

Wywoływana jest funkcja f invertible, jeśli istnieje jego funkcja odwrotna g.

Przykład

  • Funkcja $f : Z \rightarrow Z, f(x)=x+5$, jest odwracalna, ponieważ ma funkcję odwrotną $ g : Z \rightarrow Z, g(x)= x-5$.

  • Funkcja $f : Z \rightarrow Z, f(x)=x^2$ nie jest odwracalny, ponieważ nie jest to jeden do jednego jako $(-x)^2=x^2$.

Skład funkcji

Dwie funkcje $f: A \rightarrow B$ i $g: B \rightarrow C$ można skomponować, aby uzyskać kompozycję $g o f$. Jest to funkcja od A do C zdefiniowana przez$(gof)(x) = g(f(x))$

Przykład

Pozwolić $f(x) = x + 2$ i $g(x) = 2x + 1$, odnaleźć $( f o g)(x)$ i $( g o f)(x)$.

Rozwiązanie

$(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$

W związku z tym, $(f o g)(x) \neq (g o f)(x)$

Kilka faktów na temat kompozycji

  • Jeśli f i g są jeden do jednego, to funkcja $(g o f)$ jest również jeden do jednego.

  • Jeśli f i g są na, to funkcja $(g o f)$ jest również na.

  • Kompozycja zawsze ma własność skojarzeniową, ale nie posiada własności przemiennej.

Reguły logiki matematycznej określają metody wnioskowania twierdzeń matematycznych. Grecki filozof Arystoteles był pionierem logicznego rozumowania. Logiczne rozumowanie stanowi podstawę teoretyczną dla wielu dziedzin matematyki, a co za tym idzie informatyki. Ma wiele praktycznych zastosowań w informatyce, takich jak projektowanie maszyn obliczeniowych, sztuczna inteligencja, definiowanie struktur danych dla języków programowania itp.

Propositional Logicdotyczy stwierdzeń, którym można przypisać wartości prawdy, „prawda” i „fałsz”. Celem jest przeanalizowanie tych stwierdzeń indywidualnie lub w sposób złożony.

Logika przyimkowa - definicja

Zdanie to zbiór zdań deklaratywnych, które mają albo wartość prawdziwości „prawda”, albo wartość prawdy „fałsz”. Zdanie składa się ze zmiennych zdaniowych i łączników. Zmienne zdaniowe oznaczamy dużymi literami (A, B itd.). Łączniki łączą zmienne zdaniowe.

Poniżej podano kilka przykładów twierdzeń -

  • „Człowiek jest śmiertelny”, zwraca wartość prawdy „PRAWDA”
  • „12 + 9 = 3 - 2”, zwraca wartość prawdy „FALSE”

Poniższe nie jest propozycją -

  • „A jest mniejsze niż 2”. Dzieje się tak, ponieważ dopóki nie podamy określonej wartości A, nie możemy powiedzieć, czy stwierdzenie jest prawdziwe czy fałszywe.

Połączenia

W logice zdań generalnie używamy pięciu połączeń, które są -

  • LUB ($\lor$)

  • I ($\land$)

  • Negacja / NIE ($\lnot$)

  • Implikacja / jeśli-to ($\rightarrow$)

  • Wtedy i tylko wtedy gdy ($\Leftrightarrow$).

OR ($\lor$) - Operacja OR dwóch zdań A i B (zapisana jako $A \lor B$) jest prawdą, jeśli przynajmniej którakolwiek ze zmiennych zdaniowych A lub B jest prawdziwa.

Tabela prawdy jest następująca -

ZA b A ∨ B
Prawdziwe Prawdziwe Prawdziwe
Prawdziwe Fałszywy Prawdziwe
Fałszywy Prawdziwe Prawdziwe
Fałszywy Fałszywy Fałszywy

AND ($\land$) - Operacja AND dwóch zdań A i B (zapisana jako $A \land B$) jest prawdą, jeśli obie zmienne zdaniowe A i B są prawdziwe.

Tabela prawdy jest następująca -

ZA b A ∧ B
Prawdziwe Prawdziwe Prawdziwe
Prawdziwe Fałszywy Fałszywy
Fałszywy Prawdziwe Fałszywy
Fałszywy Fałszywy Fałszywy

Negation ($\lnot$) - Negacja zdania A (zapisana jako $\lnot A$) jest fałszem, gdy A jest prawdą i jest prawdą, gdy A jest fałszem.

Tabela prawdy jest następująca -

ZA ¬ A
Prawdziwe Fałszywy
Fałszywy Prawdziwe

Implication / if-then ($\rightarrow$) - Implikacja $A \rightarrow B$to zdanie „jeśli A, to B”. Jest fałszem, jeśli A jest prawdą, a B jest fałszem. Pozostałe przypadki są prawdziwe.

Tabela prawdy jest następująca -

ZA b A → B
Prawdziwe Prawdziwe Prawdziwe
Prawdziwe Fałszywy Fałszywy
Fałszywy Prawdziwe Prawdziwe
Fałszywy Fałszywy Prawdziwe

If and only if ($ \Leftrightarrow $) - $A \Leftrightarrow B$ jest dwuwarunkowym łącznikiem logicznym, który jest prawdziwy, gdy p i q są takie same, tj. oba są fałszywe lub oba są prawdziwe.

Tabela prawdy jest następująca -

ZA b A ⇔ B
Prawdziwe Prawdziwe Prawdziwe
Prawdziwe Fałszywy Fałszywy
Fałszywy Prawdziwe Fałszywy
Fałszywy Fałszywy Prawdziwe

Tautologie

Tautologia to formuła, która jest zawsze prawdziwa dla każdej wartości jej zmiennych zdaniowych.

Example - Udowodnij $\lbrack (A \rightarrow B) \land A \rbrack \rightarrow B$ jest tautologią

Tabela prawdy jest następująca -

ZA b A → B (A → B) ∧ A [(A → B) ∧ A] → B
Prawdziwe Prawdziwe Prawdziwe Prawdziwe Prawdziwe
Prawdziwe Fałszywy Fałszywy Fałszywy Prawdziwe
Fałszywy Prawdziwe Prawdziwe Fałszywy Prawdziwe
Fałszywy Fałszywy Prawdziwe Fałszywy Prawdziwe

Jak widzimy, każda wartość $\lbrack (A \rightarrow B) \land A \rbrack \rightarrow B$ jest „Prawda”, to jest tautologia.

Sprzeczności

Sprzeczność to formuła, która zawsze jest fałszywa dla każdej wartości jej zmiennych zdaniowych.

Example - Udowodnij $(A \lor B) \land \lbrack ( \lnot A) \land (\lnot B) \rbrack$ jest sprzecznością

Tabela prawdy jest następująca -

ZA b A ∨ B ¬ A ¬ B. (¬ A) ∧ (¬ B) (A ∨ B) ∧ [(¬ A) ∧ (¬ B)]
Prawdziwe Prawdziwe Prawdziwe Fałszywy Fałszywy Fałszywy Fałszywy
Prawdziwe Fałszywy Prawdziwe Fałszywy Prawdziwe Fałszywy Fałszywy
Fałszywy Prawdziwe Prawdziwe Prawdziwe Fałszywy Fałszywy Fałszywy
Fałszywy Fałszywy Fałszywy Prawdziwe Prawdziwe Prawdziwe Fałszywy

Jak widzimy, każda wartość $(A \lor B) \land \lbrack ( \lnot A) \land (\lnot B) \rbrack$ jest „fałszem”, to jest sprzeczność.

Przypadkowość

Zależność jest formułą, która ma zarówno pewne wartości prawdziwe, jak i pewne fałszywe dla każdej wartości swoich zmiennych propozycyjnych.

Example - Udowodnij $(A \lor B) \land (\lnot A)$ ewentualność

Tabela prawdy jest następująca -

ZA b A ∨ B ¬ A (A ∨ B) ∧ (¬ A)
Prawdziwe Prawdziwe Prawdziwe Fałszywy Fałszywy
Prawdziwe Fałszywy Prawdziwe Fałszywy Fałszywy
Fałszywy Prawdziwe Prawdziwe Prawdziwe Prawdziwe
Fałszywy Fałszywy Fałszywy Prawdziwe Fałszywy

Jak widzimy, każda wartość $(A \lor B) \land (\lnot A)$ ma zarówno „Prawda”, jak i „Fałsz”, jest to przypadek.

Równoważności zdań

Dwie instrukcje X i Y są logicznie równoważne, jeśli zachodzi którykolwiek z poniższych dwóch warunków -

  • Tabele prawdy każdego stwierdzenia mają te same wartości prawdy.

  • Instrukcja dwuwarunkowa $X \Leftrightarrow Y$ jest tautologią.

Example - Udowodnij $\lnot (A \lor B) and \lbrack (\lnot A) \land (\lnot B) \rbrack$ są równoważne

Testowanie pierwszą metodą (pasująca tabela prawdy)

ZA b A ∨ B ¬ (A ∨ B) ¬ A ¬ B. [(¬ A) ∧ (¬ B)]
Prawdziwe Prawdziwe Prawdziwe Fałszywy Fałszywy Fałszywy Fałszywy
Prawdziwe Fałszywy Prawdziwe Fałszywy Fałszywy Prawdziwe Fałszywy
Fałszywy Prawdziwe Prawdziwe Fałszywy Prawdziwe Fałszywy Fałszywy
Fałszywy Fałszywy Fałszywy Prawdziwe Prawdziwe Prawdziwe Prawdziwe

Tutaj możemy zobaczyć wartości prawdy $\lnot (A \lor B) and \lbrack (\lnot A) \land (\lnot B) \rbrack$ są takie same, stąd stwierdzenia są równoważne.

Testowanie przy 2 -go metodą (Bi uwarunkowania)

ZA b ¬ (A ∨ B) [(¬ A) ∧ (¬ B)] [¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)]
Prawdziwe Prawdziwe Fałszywy Fałszywy Prawdziwe
Prawdziwe Fałszywy Fałszywy Fałszywy Prawdziwe
Fałszywy Prawdziwe Fałszywy Fałszywy Prawdziwe
Fałszywy Fałszywy Prawdziwe Prawdziwe Prawdziwe

Tak jak $\lbrack \lnot (A \lor B) \rbrack \Leftrightarrow \lbrack (\lnot A ) \land (\lnot B) \rbrack$ jest tautologią, zdania są równoważne.

Odwrotność, konwersja i przeciwdziałanie dodatnim

Implikacja / jeśli-to $(\rightarrow)$nazywana jest również instrukcją warunkową. Składa się z dwóch części -

  • Hipoteza, s
  • Wniosek, q

Jak wspomniano wcześniej, jest oznaczony jako $p \rightarrow q$.

Example of Conditional Statement- „Jeśli odrobisz pracę domową, nie zostaniesz ukarany”. Tutaj „odrabiasz pracę domową” to hipoteza, p, a „nie zostaniesz ukarany” to konkluzja, q.

Inverse- Odwrotnością zdania warunkowego jest zaprzeczenie zarówno hipotezy, jak i wniosku. Jeśli stwierdzeniem jest „Jeśli p, to q”, odwrotnością będzie „Jeśli nie p, to nie q”. Stąd odwrotność$p \rightarrow q$ jest $ \lnot p \rightarrow \lnot q$.

Example - Odwrotność „Jeśli odrabiasz pracę domową, nie zostaniesz ukarany”, to „Jeśli nie odrabiasz pracy domowej, zostaniesz ukarany”.

Converse- Odwrotność zdania warunkowego jest obliczana poprzez zamianę hipotezy i wniosku. Jeśli stwierdzeniem jest „Jeśli p, to q”, odwrotnością będzie „Jeśli q, to ​​p”. Odwrotność$p \rightarrow q$ jest $q \rightarrow p$.

Example - Odwrotność: „Jeśli odrabiasz pracę domową, nie zostaniesz ukarany”, brzmi: „Jeśli nie zostaniesz ukarany, odrabiasz lekcje”.

Contra-positive- Przeciwwskazanie warunku jest obliczane poprzez zamianę hipotezy i wniosku ze stwierdzenia odwrotnego. Jeśli stwierdzeniem jest „Jeśli p, to q”, wynikiem przeciwstawnym będzie „Jeśli nie q, to ​​nie p”. W przeciwieństwie do$p \rightarrow q$ jest $\lnot q \rightarrow \lnot p$.

Example - Przeciwstawne stwierdzenie „Jeśli odrabiasz pracę domową, nie zostaniesz ukarany” to „Jeśli zostaniesz ukarany, nie odrobiłeś pracy domowej”.

Zasada dwoistości

Zasada dwoistości mówi, że dla każdego prawdziwego stwierdzenia, podwójne stwierdzenie uzyskane przez zamianę związków na przecięcia (i odwrotnie) i zamianę zbioru uniwersalnego na zbiór zerowy (i odwrotnie) jest również prawdziwe. Jeśli podwójne w jakimkolwiek stwierdzeniu jest samo stwierdzenie, to jest powiedzianeself-dual komunikat.

Example - Podwójny $(A \cap B ) \cup C$ jest $(A \cup B) \cap C$

Formy normalne

Możemy przekształcić dowolne zdanie w dwie normalne formy -

  • Postać normalna koniunkcyjna
  • Rozłączna postać normalna

Koniunkcyjna forma normalna

Zdanie złożone ma postać normalną koniunkcji, jeśli jest otrzymywane przez operację AND między zmiennymi (w tym negacja zmiennych) związanymi z OR. Pod względem operacji na zbiorach jest to instrukcja złożona uzyskana przez Przecięcie między zmiennymi związanymi ze Związkami.

Examples

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

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

Rozłączna postać normalna

Instrukcja złożona ma rozłączną postać normalną, jeśli jest otrzymywana przez operację LUB pomiędzy zmiennymi (łącznie z negacją zmiennych) związanymi z AND. Pod względem operacji na zbiorach jest to złożona instrukcja uzyskiwana przez Union wśród zmiennych związanych z przecięciami.

Examples

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

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

Predicate Logic zajmuje się predykatami, które są zdaniami zawierającymi zmienne.

Logika predykatów - definicja

Predykat jest wyrażeniem jednej lub więcej zmiennych zdefiniowanych w określonej dziedzinie. Predykat ze zmiennymi można złożyć jako propozycję, przypisując wartość zmiennej lub określając ją ilościowo.

Oto kilka przykładów predykatów -

  • Niech E (x, y) oznacza „x = y”
  • Niech X (a, b, c) oznacza „a + b + c = 0”
  • Niech M (x, y) oznacza „x jest żonaty z y”

Dobrze uformowana formuła

Dobrze uformowana formuła (wff) jest predykatem zawierającym dowolne z poniższych -

  • Wszystkie stałe zdaniowe i zmienne zdaniowe są wffs

  • Jeśli x jest zmienną, a Y jest wff, $\forall x Y$ i $\exists x Y$ są również wff

  • Wartość prawdy i wartości fałszywe to wffs

  • Każda formuła atomowa to wff

  • Wszystkie łączniki łączące wffs są wffs

Kwantyfikatory

Zmienna predykatów jest określana ilościowo za pomocą kwantyfikatorów. Istnieją dwa rodzaje kwantyfikatorów w logice predykatów - kwantyfikator uniwersalny i kwantyfikator egzystencjalny.

Uniwersalny kwantyfikator

Uniwersalny kwantyfikator stwierdza, że ​​instrukcje w jego zakresie są prawdziwe dla każdej wartości określonej zmiennej. Jest oznaczony symbolem$\forall$.

$\forall x P(x)$ czyta się jak dla każdej wartości x, P (x) jest prawdziwe.

Example - „Człowiek jest śmiertelny” można przekształcić w formę zdaniową $\forall x P(x)$ gdzie P (x) jest orzecznikiem oznaczającym x jest śmiertelny, a wszechświatem dyskursu są wszyscy ludzie.

Kwantyfikator egzystencjalny

Kwantyfikator egzystencjalny stwierdza, że ​​instrukcje w jego zakresie są prawdziwe dla niektórych wartości określonej zmiennej. Jest oznaczony symbolem$\exists $.

$\exists x P(x)$ czyta się tak, jak dla niektórych wartości x, P (x) jest prawdziwe.

Example - „Niektórzy ludzie są nieuczciwi” można przekształcić w formę zdaniową $\exists x P(x)$ gdzie P (x) jest predykatem oznaczającym x jest nieuczciwy, a wszechświat dyskursu to niektórzy ludzie.

Zagnieżdżone kwantyfikatory

Jeśli użyjemy kwantyfikatora, który pojawia się w zakresie innego kwantyfikatora, nazywamy go kwantyfikatorem zagnieżdżonym.

Example

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

  • $\forall\ a\: \forall\: b\: \forall\: c\: P (a, b, c)$ gdzie $P (a, b)$ oznacza $a + (b + c) = (a + b) + c$

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

Aby wydedukować nowe stwierdzenia ze stwierdzeń, których prawdziwość już znamy, Rules of Inference są używane.

Do czego służą reguły wnioskowania?

Logika matematyczna jest często używana do dowodów logicznych. Dowody to ważne argumenty, które określają prawdziwość twierdzeń matematycznych.

Argument to sekwencja instrukcji. Ostatnie stwierdzenie jest konkluzją, a wszystkie poprzednie stwierdzenia nazywane są przesłankami (lub hipotezami). Symbol "$\therefore$”, (Czytaj więc) znajduje się przed zakończeniem. Ważnym argumentem jest taki, w którym wniosek wynika z prawdziwości przesłanek.

Reguły wnioskowania zawierają szablony lub wytyczne dotyczące konstruowania prawidłowych argumentów na podstawie instrukcji, które już mamy.

Tabela reguł wnioskowania

Reguła wnioskowania Nazwa Reguła wnioskowania Nazwa

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

Dodanie

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

Sylogizm rozłączny

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

Spójnik

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

Sylogizm hipotetyczny

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

Uproszczenie

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

Konstruktywny dylemat

$$\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}$$

Destrukcyjny dylemat

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

Modus Tollens

Dodanie

Jeśli P jest przesłanką, do wyprowadzenia możemy użyć reguły dodawania $ P \lor Q $.

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

Przykład

Niech P będzie twierdzeniem, że „bardzo pilnie się uczy” jest prawdą

Dlatego - „Albo bardzo się uczy, albo jest bardzo złym uczniem”. Tutaj Q jest propozycją „on jest bardzo złym uczniem”.

Spójnik

Jeśli P i Q to dwie przesłanki, do wyprowadzenia możemy użyć reguły koniunkcji $ P \land Q $.

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

Przykład

Niech P - „Uczy się bardzo ciężko”

Niech Q - „On jest najlepszym chłopcem w klasie”

Dlatego - "Uczy się bardzo ciężko i jest najlepszym chłopakiem w klasie"

Uproszczenie

Gdyby $P \land Q$ jest przesłanką, możemy użyć reguły uproszczenia do wyprowadzenia P.

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

Przykład

"Bardzo się uczy i jest najlepszym chłopakiem w klasie", $P \land Q$

Dlatego - „Uczy się bardzo ciężko”

Modus Ponens

Jeśli P i $P \rightarrow Q$ są dwie przesłanki, możemy użyć Modus Ponens do wyprowadzenia Q.

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

Przykład

„Jeśli masz hasło, możesz zalogować się do Facebooka”, $P \rightarrow Q$

„Masz hasło”, P

Dlatego - „Możesz zalogować się do Facebooka”

Modus Tollens

Gdyby $P \rightarrow Q$ i $\lnot Q$ to dwie przesłanki, do wyprowadzenia możemy użyć Modus Tollens $\lnot P$.

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

Przykład

„Jeśli masz hasło, możesz zalogować się do Facebooka”, $P \rightarrow Q$

„Nie możesz zalogować się do Facebooka”, $\lnot Q$

Dlatego - „Nie masz hasła”

Sylogizm rozłączny

Gdyby $\lnot P$ i $P \lor Q$ Są dwie przesłanki, możemy użyć Disjunctive Syllogism do wyprowadzenia Q.

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

Przykład

„Lody nie mają smaku waniliowego”, $\lnot P$

„Lody mają smak waniliowy lub czekoladowy”, $P \lor Q$

Dlatego - „Lody mają smak czekoladowy”

Sylogizm hipotetyczny

Gdyby $P \rightarrow Q$ and $Q \rightarrow R$ are two premises, we can use Hypothetical Syllogism to derive $P \rightarrow R$

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

Example

"If it rains, I shall not go to school”, $P \rightarrow Q$

"If I don't go to school, I won't need to do homework", $Q \rightarrow R$

Therefore − "If it rains, I won't need to do homework"

Constructive Dilemma

If $( P \rightarrow Q ) \land (R \rightarrow S)$ and $P \lor R$ are two premises, we can use constructive dilemma to derive $Q \lor S$.

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

Example

“If it rains, I will take a leave”, $( P \rightarrow Q )$

“If it is hot outside, I will go for a shower”, $(R \rightarrow S)$

“Either it will rain or it is hot outside”, $P \lor R$

Therefore − "I will take a leave or I will go for a shower"

Destructive Dilemma

If $(P \rightarrow Q) \land (R \rightarrow S)$ and $ \lnot Q \lor \lnot S $ are two premises, we can use destructive dilemma to derive $\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}$$

Example

“If it rains, I will take a leave”, $(P \rightarrow Q )$

“If it is hot outside, I will go for a shower”, $(R \rightarrow S)$

“Either I will not take a leave or I will not go for a shower”, $\lnot Q \lor \lnot S$

Therefore − "Either it does not rain or it is not hot outside"

Group Theory is a branch of mathematics and abstract algebra that defines an algebraic structure named as group. Generally, a group comprises of a set of elements and an operation over any two elements on that set to form a third element also in that set.

In 1854, Arthur Cayley, the British Mathematician, gave the modern definition of group for the first time −

“A set of symbols all of them different, and such that the product of any two of them (no matter in what order), or the product of any one of them into itself, belongs to the set, is said to be a group. These symbols are not in general convertible [commutative], but are associative.”

In this chapter, we will know about operators and postulates that form the basics of set theory, group theory and Boolean algebra.

Any set of elements in a mathematical system may be defined with a set of operators and a number of postulates.

A binary operator defined on a set of elements is a rule that assigns to each pair of elements a unique element from that set. For example, given the set $ A = \lbrace 1, 2, 3, 4, 5 \rbrace $, we can say $\otimes$ is a binary operator for the operation $c = a \otimes b$, if it specifies a rule for finding c for the pair of $(a,b)$, such that $a,b,c \in A$.

The postulates of a mathematical system form the basic assumptions from which rules can be deduced. The postulates are −

Closure

A set is closed with respect to a binary operator if for every pair of elements in the set, the operator finds a unique element from that set.

Example

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

This set is closed under binary operator into $(\ast)$, because for the operation $c = a \ast b$, for any $a, b \in A$, the product $c \in A$.

The set is not closed under binary operator divide $(\div)$, because, for the operation $c = a \div b$, for any $a, b \in A$, the product c may not be in the set A. If $a = 7, b = 2$, then $c = 3.5$. Here $a,b \in A$ but $c \notin A$.

Associative Laws

A binary operator $\otimes$ on a set A is associative when it holds the following property −

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

Example

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

The operator plus $( + )$ is associative because for any three elements, $x,y,z \in A$, the property $(x + y) + z = x + ( y + z )$ holds.

The operator minus $( - )$ is not associative since

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

Commutative Laws

A binary operator $\otimes$ on a set A is commutative when it holds the following property −

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

Przykład

Pozwolić $A = \lbrace 1, 2, 3, 4 \rbrace$

Operator plus $( + )$ jest przemienna, ponieważ dla dowolnych dwóch elementów $x,y \in A$, własność $x + y = y + x$ trzyma.

Operator minus $( - )$ nie jest skojarzony od

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

Prawa dystrybucyjne

Dwa operatory binarne $\otimes$ i $\circledast$ na zbiorze A są rozdzielcze względem operatora $\circledast$ gdy następujący majątek posiada -

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

Przykład

Pozwolić $A = \lbrace 1, 2, 3, 4 \rbrace$

Operatory w $( * )$ i plus $( + )$ są rozdzielcze względem operatora +, ponieważ dla dowolnych trzech elementów, $x,y,z \in A$, własność $x * ( y + z ) = ( x * y ) + ( x * z )$ trzyma.

Jednak operatorzy ci nie są dystrybucyjni $*$ od

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

Element tożsamości

Zestaw A ma element tożsamości w odniesieniu do operacji binarnej $\otimes$ na A, jeśli istnieje element $e \in A$, takie, że następująca własność posiada -

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

Przykład

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

Element 1 jest elementem tożsamości w odniesieniu do działania $*$ ponieważ dla każdego elementu $x \in Z$,

$$1 * x = x * 1$$

Z drugiej strony nie ma elementu tożsamości dla operacji minus $( - )$

Odwrotność

Jeśli zbiór A ma element tożsamości $e$ w odniesieniu do operatora binarnego $\otimes $, mówi się, że ma odwrotność dla każdego elementu $x \in A$istnieje inny element $y \in A$, takie, że następująca własność posiada -

$$x \otimes y = e$$

Przykład

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

Biorąc pod uwagę operację plus $( + )$ i $e = 0$odwrotnością dowolnego elementu x jest $(-x)$ od $x + (x) = 0$

Prawo De Morgana

Prawa De Morgana podają parę transformacji między związkiem a przecięciem dwóch (lub więcej) zbiorów pod względem ich dopełnienia. Prawa są -

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

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

Przykład

Pozwolić $A = \lbrace 1, 2, 3, 4 \rbrace ,B = \lbrace 1, 3, 5, 7 \rbrace$, i

Uniwersalny zestaw $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$

Tak więc to widzimy $(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$

Tak więc to widzimy $(A \cap B)' = A' \cup B'$

Półgrupa

Skończony lub nieskończony zbiór $‘S’$ z operacją binarną $‘\omicron’$ (Kompozycja) nazywana jest półgrupą, jeśli spełnia jednocześnie dwa warunki -

  • Closure - Na każdą parę $(a, b) \in S, \:(a \omicron b)$ musi być obecny w zestawie $S$.

  • Associative - Na każdy element $a, b, c \in S, (a \omicron b) \omicron c = a \omicron (b \omicron c)$ trzeba trzymać.

Przykład

Zbiór dodatnich liczb całkowitych (bez zera) z operacją dodawania jest półgrupą. Na przykład,$ S = \lbrace 1, 2, 3, \dots \rbrace $

Tutaj właściwość zamknięcia obowiązuje jak dla każdej pary $(a, b) \in S, (a + b)$ występuje w zestawie S. Na przykład $1 + 2 = 3 \in S]$

Własność asocjacyjna obowiązuje również dla każdego elementu $a, b, c \in S, (a + b) + c = a + (b + c)$. Na przykład,$(1 + 2) + 3 = 1 + (2 + 3) = 5$

Monoid

Monoid to półgrupa z elementem tożsamości. Element tożsamości (oznaczony$e$ lub E) zbioru S jest takim elementem, że $(a \omicron e) = a$dla każdego elementu $a \in S$. Element tożsamości jest również nazywanyunit element. Zatem monoid posiada jednocześnie trzy właściwości -Closure, Associative, Identity element.

Przykład

Zbiór dodatnich liczb całkowitych (z wyłączeniem zera) z operacją mnożenia jest monoidem. $S = \lbrace 1, 2, 3, \dots \rbrace $

Tutaj właściwość zamknięcia obowiązuje jak dla każdej pary $(a, b) \in S, (a \times b)$ występuje w zbiorze S. [Na przykład $1 \times 2 = 2 \in S$ i tak dalej]

Własność asocjacyjna obowiązuje również dla każdego elementu $a, b, c \in S, (a \times b) \times c = a \times (b \times c)$ [Na przykład, $(1 \times 2) \times 3 = 1 \times (2 \times 3) = 6$ i tak dalej]

Własność tożsamości zachowuje się również dla każdego elementu $a \in S, (a \times e) = a$ [Na przykład, $(2 \times 1) = 2, (3 \times 1) = 3$i tak dalej]. Tutaj elementem tożsamości jest 1.

Grupa

Grupa jest monoidem z elementem odwrotnym. Odwrotny element (oznaczony przez I) zbioru S jest takim elementem, że$(a \omicron I) = (I \omicron a) = a$dla każdego elementu $a \in S$. Zatem grupa posiada jednocześnie cztery własności - i) Zamknięcie, ii) Asocjację, iii) Element tożsamości, iv) Element odwrotny. Kolejność grupy G to liczba elementów w G, a kolejność elementów w grupie to najmniejsza dodatnia liczba całkowita n taka, że ​​an jest elementem tożsamości tej grupy G.

Przykłady

Zestaw $N \times N$ macierze inne niż osobliwe tworzą grupę w ramach operacji mnożenia macierzy.

Iloczyn dwóch $N \times N$ macierze niejednoznaczne są również $N \times N$ niejednolita macierz, która posiada właściwość domknięcia.

Mnożenie macierzy samo w sobie jest asocjacyjne. Stąd własność asocjacyjna zachodzi.

Zestaw $N \times N$ macierze niejednoznaczne zawierają macierz tożsamości przechowującą właściwość elementu tożsamości.

Ponieważ wszystkie macierze nie są pojedyncze, wszystkie mają odwrotne elementy, które są również macierzami nieosobowymi. Stąd też zachodzi własność odwrotna.

Grupa abelowa

Grupa abelowa G to grupa, dla której para elementów $(a,b) \in G$zawsze ma prawo przemienne. Tak więc grupa posiada pięć właściwości jednocześnie - i) Zamknięcie, ii) Asocjacyjne, iii) Element tożsamości, iv) Element odwrotny, v) Przemienność.

Przykład

Zbiór dodatnich liczb całkowitych (w tym zera) z operacją dodawania jest grupą abelową. $G = \lbrace 0, 1, 2, 3, \dots \rbrace$

Tutaj właściwość zamknięcia obowiązuje jak dla każdej pary $(a, b) \in S, (a + b)$ występuje w zbiorze S. [Na przykład $1 + 2 = 2 \in S$ i tak dalej]

Własność asocjacyjna obowiązuje również dla każdego elementu $a, b, c \in S, (a + b) + c = a + (b + c)$ [Na przykład, $(1 +2) + 3 = 1 + (2 + 3) = 6$ i tak dalej]

Własność tożsamości zachowuje się również dla każdego elementu $a \in S, (a \times e) = a$ [Na przykład, $(2 \times 1) = 2, (3 \times 1) = 3$i tak dalej]. Tutaj elementem tożsamości jest 1.

Właściwość przemienna zachodzi również dla każdego elementu $a \in S, (a \times b) = (b \times a)$ [Na przykład, $(2 \times 3) = (3 \times 2) = 3$ i tak dalej]

Grupa cykliczna i podgrupa

ZA cyclic groupto grupa, którą może wygenerować pojedynczy element. Każdy element grupy cyklicznej jest potęgą jakiegoś określonego elementu, który nazywamy generatorem. Grupa cykliczna może być generowana przez generator „g”, tak że każdy inny element grupy można zapisać jako moc generatora „g”.

Przykład

Zbiór liczb zespolonych $\lbrace 1,-1, i, -i \rbrace$ w operacji mnożenia jest grupą cykliczną.

Istnieją dwa generatory - $i$ i $–i$ tak jak $i^1 = i, i^2 = -1, i^3 = -i, i^4 = 1$ i również $(–i)^1 = -i, (–i)^2 = -1, (–i)^3 = i, (–i)^4 = 1$który obejmuje wszystkie elementy grupy. Dlatego jest to grupa cykliczna.

Note - A cyclic groupjest zawsze grupą abelową, ale nie każda grupa abelowa jest grupą cykliczną. Dodawane liczby wymierne nie są cykliczne, ale abelowe.

ZA subgroup H jest podzbiorem grupy G (oznaczonej jako $H ≤ G$) jeśli spełnia jednocześnie cztery właściwości - Closure, Associative, Identity element, i Inverse.

Podgrupa H grupy G, która nie obejmuje całej grupy G, nazywana jest odpowiednią podgrupą (oznaczona $H < G$). Podgrupa grupy cyklicznej jest cykliczna, a podgrupa abelowa jest również abelowa.

Przykład

Niech grupa $G = \lbrace 1, i, -1, -i \rbrace$

Wtedy niektóre podgrupy są $H_1 = \lbrace 1 \rbrace, H_2 = \lbrace 1,-1 \rbrace$,

To nie jest podgrupa - $H_3 = \lbrace 1, i \rbrace$ dlatego, że $(i)^{-1} = -i$ nie ma $H_3$

Częściowo zamówiony zestaw (POSET)

Zbiór częściowo uporządkowany składa się ze zbioru o relacji binarnej, która jest zwrotna, antysymetryczna i przechodnia. „Zestaw częściowo zamówiony” jest w skrócie POSET.

Przykłady

  • Zbiór liczb rzeczywistych w operacji binarnej mniejszy lub równy $(\le)$ jest posetem.

    Niech zestaw $S = \lbrace 1, 2, 3 \rbrace$ a operacja jest $\le$

    Relacje będą $\lbrace(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3)\rbrace$

    Ta relacja R jest zwrotna jak $\lbrace (1, 1), (2, 2), (3, 3)\rbrace \in R$

    Ta relacja R jest antysymetryczna, jak

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

    Ta relacja R jest również przechodnia jako $\lbrace (1,2), (2,3), (1,3)\rbrace \in R$.

    Dlatego jest to plik poset.

  • Zbiór wierzchołków skierowanego grafu acyklicznego w ramach operacji „osiągalność” jest posetem.

Diagram Hassego

Diagram Hassego posety jest grafem skierowanym, którego wierzchołki są elementem tej pozycji, a łuki pokrywają pary (x, y) w tej pozycji. Jeśli w poset$x < y$, wtedy punkt x pojawia się niżej niż punkt y na diagramie Hassego. Gdyby$x<y<z$ w pozycji, strzałka nie jest pokazana między x i z, ponieważ jest niejawna.

Przykład

Pozycja podzbiorów $\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$ przedstawia poniższy diagram Hassego -

Zestaw uporządkowany liniowo

Zestaw uporządkowany liniowo lub Zestaw uporządkowany łącznie to zestaw częściowego porządku, w którym każda para elementów jest porównywalna. Elementy$a, b \in S$ są porównywalne, jeśli jedno i drugie $a \le b$ lub $b \le a$trzyma. Prawo trychotomii definiuje ten całkowity uporządkowany zbiór. Całkowicie uporządkowany zbiór można zdefiniować jako kratę rozdzielczą mającą tę właściwość$\lbrace a \lor b, a \land b \rbrace = \lbrace a, b \rbrace$ dla wszystkich wartości a i b w zbiorze S.

Przykład

Zestaw uprawnień $\lbrace a, b \rbrace$ uporządkowany przez \ subseteq jest zbiorem całkowicie uporządkowanym jako wszystkie elementy zbioru potęgowego $P = \lbrace \emptyset, \lbrace a \rbrace, \lbrace b \rbrace, \lbrace a, b\rbrace \rbrace$ są porównywalne.

Przykład niecałkowitego zestawu zamówień

Zestaw $S = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$ w trakcie operacji x dzieli y nie jest całkowitym uporządkowanym zbiorem.

Tutaj dla wszystkich $(x, y) \in S, x | y$trzeba trzymać, ale nie jest prawdą, że 2 | 3, ponieważ 2 nie dzieli 3 lub 3 nie dzieli 2. Zatem nie jest to uporządkowany zbiór całkowity.

Krata

Krata jest posetą $(L, \le)$ dla której każda para $\lbrace a, b \rbrace \in L$ ma najmniejszą górną granicę (oznaczoną $a \lor b$) i największą dolną granicę (oznaczoną $a \land b$). LUB$(\lbrace a,b \rbrace)$nazywa się złączeniem a i b. GLB$(\lbrace a,b \rbrace )$ nazywa się spotkaniem a i b.

Przykład

Powyższy rysunek jest kratą, ponieważ dla każdej pary $\lbrace a, b \rbrace \in L$istnieje GLB i LUB.

Powyższy rysunek nie jest kratą, ponieważ $GLB (a, b)$ i $LUB (e, f)$ nie istnieje.

Niektóre inne kraty są omówione poniżej -

Ograniczona krata

Krata L staje się kratą ograniczoną, jeśli ma największy element 1 i najmniejszy element 0.

Uzupełniona krata

Krata L staje się kratą dopełnioną, jeśli jest kratą ograniczoną i jeśli każdy element w sieci ma dopełnienie. Element x ma dopełnienie x 'if$\exists x(x \land x’=0 and x \lor x’ = 1)$

Krata rozdzielcza

Jeśli krata spełnia następujące dwie właściwości dystrybucji, nazywana jest kratą dystrybucyjną.

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

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

Modułowa krata

Jeśli krata spełnia następującą właściwość, nazywana jest kratą modularną.

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

Właściwości krat

Idempotentne właściwości

  • $a \lor a = a$

  • $a \land a = a$

Właściwości absorpcyjne

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

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

Właściwości przemienne

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

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

Właściwości skojarzone

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

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

Podwójna krata

Dwoistość kraty uzyskuje się przez zamianę '$\lor$' i '$\land$operacje.

Przykład

Podwójny $\lbrack a \lor (b \land c) \rbrack\ is\ \lbrack a \land (b \lor c) \rbrack$

W życiu codziennym niejednokrotnie trzeba poznać liczbę wszystkich możliwych wyników serii wydarzeń. Na przykład, na ile sposobów można wybrać komisję sędziowską składającą się z 6 mężczyzn i 4 kobiet spośród 50 mężczyzn i 38 kobiet? Ile różnych 10-literowych numerów PAN można wygenerować w taki sposób, że pierwsze pięć liter to wielkie litery, następne cztery to cyfry, a ostatnia jest znowu wielką literą. Do rozwiązania tych problemów stosuje się matematyczną teorię liczenia.Counting obejmuje głównie podstawową regułę liczenia, regułę permutacji i regułę kombinacji.

Zasady dotyczące sum i produktów

Plik Rule of Sum i Rule of Product służą do rozkładania trudnych problemów liczenia na proste problemy.

  • The Rule of Sum - Jeśli sekwencja zadań $T_1, T_2, \dots, T_m$ można zrobić w $w_1, w_2, \dots w_m$ odpowiednio (pod warunkiem, że żadne zadania nie mogą być wykonywane jednocześnie), wówczas liczba sposobów wykonania jednego z tych zadań wynosi $w_1 + w_2 + \dots +w_m$. Jeśli weźmiemy pod uwagę dwa zadania A i B, które są rozłączne (tj$A \cap B = \emptyset$), a następnie matematycznie $|A \cup B| = |A| + |B|$

  • The Rule of Product - Jeśli sekwencja zadań $T_1, T_2, \dots, T_m$ można zrobić w $w_1, w_2, \dots w_m$ drogi odpowiednio i każde zadanie przybywa po wystąpieniu poprzedniego zadania, to są $w_1 \times w_2 \times \dots \times w_m$sposoby wykonywania zadań. Matematycznie, jeśli zadanie B pojawia się po zadaniu A, to$|A \times B| = |A|\times|B|$

Przykład

Question- Chłopiec mieszka w X i chce iść do szkoły w Z. Ze swojego domu X musi najpierw dotrzeć do Y, a następnie Y do Z. Może jechać od X do Y 3 liniami autobusowymi lub 2 trasami kolejowymi. Stamtąd może wybrać 4 linie autobusowe lub 5 tras pociągów, aby dotrzeć do Z. Ile jest sposobów, aby przejść z X do Z?

Solution - Od X do Y, może wejść $3 + 2 = 5$sposoby (reguła sumy). Następnie może przejść od Y do Z in$4 + 5 = 9$sposoby (reguła sumy). Stąd od X do Z może wejść$5 \times 9 = 45$ sposoby (zasada produktu).

Permutacje

ZA permutationto układ niektórych elementów, w których liczy się kolejność. Innymi słowy, permutacja jest uporządkowaną kombinacją elementów.

Przykłady

  • Ze zbioru S = {x, y, z}, biorąc po dwa naraz, wszystkie permutacje są -

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

  • Musimy utworzyć permutację trzycyfrowych liczb ze zbioru liczb $S = \lbrace 1, 2, 3 \rbrace$. Po ułożeniu cyfr zostaną utworzone różne liczby trzycyfrowe. Permutacja wyniesie = 123, 132, 213, 231, 312, 321

Liczba permutacji

Liczba permutacji „n” różnych rzeczy przyjmowanych jednocześnie „r” jest oznaczona przez $n_{P_{r}}$

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

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

Proof - Niech będzie „n” różnych elementów.

Istnieje wiele sposobów na zajęcie pierwszego miejsca. Po wypełnieniu pierwszego miejsca (n-1) zostaje liczba elementów. Stąd istnieje (n-1) sposobów na zajęcie drugiego miejsca. Po wypełnieniu pierwszego i drugiego miejsca zostaje (n-2) liczba elementów. Stąd jest (n-2) sposoby na zajęcie trzeciego miejsca. Możemy teraz uogólnić liczbę sposobów wypełnienia r-tego miejsca jako [n - (r – 1)] = n – r + 1

Więc w sumie nie. sposobów na zapełnienie miejsca od pierwszego do r-tego -

$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]$

W związku z tym,

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

Kilka ważnych wzorów permutacji

  • Jeśli istnieje n elementów, których$a_1$ są do siebie podobne, $a_2$ są podobne do innego rodzaju; $a_3$ są podobne do trzeciego rodzaju i tak dalej i $a_r$ są z $r^{th}$ miły, gdzie $(a_1 + a_2 + ... a_r) = n$.

    Wówczas liczba permutacji tych n obiektów wynosi = $n! / [(a_1!(a_2!) \dots (a_r!)]$.

  • Liczba permutacji n różnych elementów przyjmujących jednocześnie n elementów = $n_{P_n} = n!$

  • Liczba permutacji n odmiennych elementów przyjmujących r elementów naraz, gdy x poszczególne rzeczy zawsze zajmują określone miejsca = $n-x_{p_{r-x}}$

  • Liczba permutacji n różnych elementów, gdy r określone rzeczy zawsze się łączą, wynosi - $r! (n−r+1)!$

  • Liczba permutacji n niepodobnych elementów, gdy r określone rzeczy nigdy się nie łączą, wynosi - $n!–[r! (n−r+1)!]$

  • Liczba permutacji kołowych n różnych elementów przyjmowanych x elementów w czasie = $^np_{x}/x$

  • Liczba permutacji cyklicznych n różnych rzeczy = $^np_{n}/n$

Trochę problemów

Problem 1 - Z zestawu 6 różnych kart, na ile sposobów możemy to permutować?

Solution - Ponieważ bierzemy jednocześnie 6 kart z talii 6 kart, permutacja będzie $^6P_{6} = 6! = 720$

Problem 2 - Na ile sposobów można ułożyć litery słowa „CZYTNIK”?

Solution - Słowo „CZYTNIK” składa się z 6 liter (2 E, 1 A, 1D i 2R.).

Permutacja będzie $= 6! /\: [(2!) (1!)(1!)(2!)] = 180.$

Problem 3 - W jaki sposób można ułożyć litery słowa „POMARAŃCZOWY”, tak aby spółgłoski zajmowały tylko pozycje parzyste?

Solution- W słowie „POMARAŃCZOWY” są 3 samogłoski i 3 spółgłoski. Liczba sposobów ułożenia spółgłosek między sobą$= ^3P_{3} = 3! = 6$. Pozostałe 3 wolne miejsca zostaną wypełnione 3 samogłoskami$^3P_{3} = 3! = 6$sposoby. Stąd całkowita liczba permutacji wynosi$6 \times 6 = 36$

Kombinacje

ZA combination to wybór pewnych elementów, w których kolejność nie ma znaczenia.

Liczba wszystkich kombinacji n rzeczy branych na raz r to -

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

Problem 1

Znajdź liczbę podzbiorów zbioru $\lbrace1, 2, 3, 4, 5, 6\rbrace$ posiadające 3 elementy.

Solution

Kardynalność zestawu wynosi 6 i do wyboru mamy 3 elementy z zestawu. Tutaj kolejność nie ma znaczenia. Stąd liczba podzbiorów będzie$^6C_{3} = 20$.

Problem 2

W pokoju jest 6 mężczyzn i 5 kobiet. Na ile sposobów możemy wybrać z pokoju 3 mężczyzn i 2 kobiety?

Solution

Liczba możliwości wyboru 3 mężczyzn spośród 6 to $^6C_{3}$ a liczba sposobów wyboru 2 kobiet z 5 kobiet wynosi $^5C_{2}$

W związku z tym całkowita liczba sposobów wynosi - $^6C_{3} \times ^5C_{2} = 20 \times 10 = 200$

Problem 3

Na ile sposobów możesz wybrać 3 odrębne grupy po 3 uczniów spośród łącznie 9 uczniów?

Solution

Ponumerujmy grupy jako 1, 2 i 3

Do wyboru 3 studentów do 1 st grupie, wiele sposobów -$^9C_{3}$

Liczba sposobów wyboru 3 uczniów do drugiej grupy po wybraniu pierwszej grupy -$^6C_{3}$

Liczba możliwości wyboru 3 uczniów do III grupy po wybraniu I i II grupy -$^3C_{3}$

Stąd całkowita liczba sposobów $= ^9C_{3} \times ^6C_{3} \times ^3C_{3} = 84 \times 20 \times 1 = 1680$

Tożsamość Pascala

Tożsamość Pascala, po raz pierwszy wyprowadzona przez Blaise'a Pascala w XVII wieku, stwierdza, że ​​liczba sposobów wyboru k elementów z n elementów jest równa sumie sposobów wyboru (k-1) elementów z (n-1) elementów oraz liczbę sposobów wyboru elementów z n-1 elementów.

Matematycznie dla wszystkich dodatnich liczb całkowitych k i 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 } }$

Zasada gołębnika

W 1834 roku niemiecki matematyk Peter Gustav Lejeune Dirichlet sformułował zasadę, którą nazwał zasadą szuflady. Teraz jest znana jako zasada szufladkowania.

Pigeonhole Principlestwierdza, że ​​jeśli jest mniej dziur dla gołębi niż całkowita liczba gołębi i każdy gołąb jest włożony do gołębnika, to musi istnieć co najmniej jeden dołek z więcej niż jednym gołębiem. Jeśli n gołębi jest umieszczonych w m przegródkach, gdzie n> m, jest dołek z więcej niż jednym gołębiem.

Przykłady

  • Dziesięciu mężczyzn jest w pokoju i biorą udział w uściskach dłoni. Jeśli każda osoba przynajmniej raz poda rękę i żaden mężczyzna nie poda ręki temu samemu więcej niż jeden raz, to dwóch mężczyzn brało udział w tej samej liczbie uścisków dłoni.

  • W klasie liczącej 30 osób muszą być co najmniej dwie osoby, których imiona zaczynają się tym samym alfabetem.

Zasada włączenia-wykluczenia

Plik Inclusion-exclusion principleoblicza liczbę kardynalną sumy wielu nierozłącznych zbiorów. Dla dwóch zbiorów A i B zasada mówi:

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

Dla trzech zestawów A, B i C zasada brzmi:

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

Uogólniona formuła -

$|\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

Ile liczb całkowitych od 1 do 50 to wielokrotności 2 lub 3, ale nie obu?

Solution

Od 1 do 100 jest $50/2 = 25$ liczby będące wielokrotnościami 2.

Tam są $50/3 = 16$ liczby będące wielokrotnościami 3.

Tam są $50/6 = 8$ liczby będące wielokrotnościami 2 i 3.

Więc, $|A|=25$, $|B|=16$ i $|A \cap B|= 8$.

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

Problem 2

W grupie 50 uczniów 24 osoby lubią zimne napoje, a 36 gorące, a każdy uczeń lubi przynajmniej jeden z dwóch napojów. Ilu lubi zarówno kawę, jak i herbatę?

Solution

Niech X będzie zbiorem uczniów lubiących zimne napoje, a Y będzie zbiorem osób lubiących gorące napoje.

Więc, $| X \cup Y | = 50$, $|X| = 24$, $|Y| = 36$

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

Dlatego jest 10 uczniów, którzy lubią zarówno herbatę, jak i kawę.

Ściśle związane z koncepcjami liczenia jest prawdopodobieństwo. Często staramy się odgadnąć wyniki gier losowych, takich jak gry karciane, automaty do gier i loterie; tj. staramy się znaleźć prawdopodobieństwo lub prawdopodobieństwo uzyskania określonego wyniku.

Probabilitymożna konceptualizować jako znajdowanie szansy wystąpienia zdarzenia. Matematycznie jest to badanie procesów losowych i ich skutków. Prawa prawdopodobieństwa mają szerokie zastosowanie w różnych dziedzinach, takich jak genetyka, prognozy pogody, badania opinii publicznej, giełdy itp.

Podstawowe koncepcje

Teoria prawdopodobieństwa została wymyślona w XVII wieku przez dwóch francuskich matematyków, Blaise'a Pascala i Pierre'a de Fermata, którzy zajmowali się matematycznymi problemami dotyczącymi przypadku.

Zanim przejdziemy do szczegółów prawdopodobieństwa, zapoznajmy się z pewnymi definicjami.

Random Experiment- Eksperyment, w którym znane są wszystkie możliwe wyniki, a dokładnego wyniku nie można przewidzieć z góry, nazywa się eksperymentem losowym. Rzucanie uczciwą monetą to przykład losowego eksperymentu.

Sample Space- Kiedy wykonujemy eksperyment, zbiór S wszystkich możliwych wyników nazywamy przestrzenią próbną. Jeśli wrzucimy monetę, miejsce na próbkę$S = \left \{ H, T \right \}$

Event- Każdy podzbiór przestrzeni próbkowania nazywany jest zdarzeniem. Po rzucie monetą zdobycie głowy na wierzch jest wydarzeniem.

Słowo „prawdopodobieństwo” oznacza możliwość wystąpienia określonego zdarzenia. Najlepsze, co możemy powiedzieć, to prawdopodobieństwo ich wystąpienia, używając pojęcia prawdopodobieństwa.

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

Ponieważ wystąpienie dowolnego zdarzenia waha się między 0% a 100%, prawdopodobieństwo waha się między 0 a 1.

Kroki, aby znaleźć prawdopodobieństwo

Krok 1 - Oblicz wszystkie możliwe wyniki eksperymentu.

Krok 2 - Oblicz liczbę korzystnych wyników eksperymentu.

Krok 3 - Zastosuj odpowiednią formułę prawdopodobieństwa.

Rzucanie monetą

Jeśli rzucisz monetą, są dwa możliwe wyniki - orzeł $(H)$ lub Tails $(T)$

Zatem całkowita liczba wyników = 2

Stąd prawdopodobieństwo zdobycia głowy $(H)$ na górze jest 1/2 i prawdopodobieństwo zdobycia ogona $(T)$ na górze jest 1/2

Rzucanie kostką

Gdy rzuca się kostką, na szczycie może znaleźć się sześć możliwych wyników - $1, 2, 3, 4, 5, 6$.

Prawdopodobieństwo jednej z liczb wynosi 1/6

Prawdopodobieństwo uzyskania liczb parzystych wynosi 3/6 = 1/2

Prawdopodobieństwo uzyskania liczb nieparzystych wynosi 3/6 = 1/2

Pobieranie kart z talii

Z talii 52 kart, jeśli wybierzesz jedną kartę, znajdź prawdopodobieństwo wylosowania asa, a także znajdź prawdopodobieństwo wylosowania karo.

Łączna liczba możliwych wyników - 52

Wyniki bycia asem - 4

Prawdopodobieństwo bycia asem = 4/52 = 1/13

Prawdopodobieństwo bycia diamentem = 13/52 = 1/4

Aksjomaty prawdopodobieństwa

  • Prawdopodobieństwo zdarzenia zawsze waha się od 0 do 1. $[0 \leq P(x) \leq 1]$

  • W przypadku niemożliwego zdarzenia prawdopodobieństwo wynosi 0, a dla pewnego zdarzenia prawdopodobieństwo wynosi 1.

  • Jeśli na wystąpienie jednego zdarzenia nie ma wpływu inne wydarzenie, nazywane są one wzajemnie wykluczającymi się lub rozłącznymi.

    Gdyby $A_1, A_2....A_n$ są więc wzajemnie wykluczającymi się / rozłącznymi wydarzeniami $P(A_i \cap A_j) = \emptyset $ dla $i \ne j$ i $P(A_1 \cup A_2 \cup.... A_n) = P(A_1) + P(A_2)+..... P(A_n)$

Własności prawdopodobieństwa

  • Jeśli są dwa wydarzenia $x$ i $\overline{x}$które są komplementarne, to prawdopodobieństwo zdarzenia komplementarnego wynosi -

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

  • Dla dwóch nierozłącznych zdarzeń A i B prawdopodobieństwo połączenia dwóch zdarzeń -

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

  • Jeśli zdarzenie A jest podzbiorem innego zdarzenia B (tj $A \subset B$), to prawdopodobieństwo A jest mniejsze lub równe prawdopodobieństwu B. Stąd $A \subset B$ sugeruje $P(A) \leq p(B)$

Warunkowe prawdopodobieństwo

Warunkowe prawdopodobieństwo zdarzenia B to prawdopodobieństwo, że zdarzenie wystąpi, biorąc pod uwagę, że zdarzenie A już miało miejsce. To jest zapisane jako$P(B|A)$.

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

Jeżeli zdarzenie A i B wykluczają się wzajemnie, to warunkowe prawdopodobieństwo zdarzenia B po zdarzeniu A będzie równe prawdopodobieństwu zdarzenia B, czyli $P(B)$.

Problem 1

W kraju 50% wszystkich nastolatków posiada rower, a 30% wszystkich nastolatków posiada rower i rower. Jakie jest prawdopodobieństwo, że nastolatek ma rower, biorąc pod uwagę, że ma rower?

Solution

Załóżmy, że A to zdarzenie, w którym nastolatki mają tylko rower, a B to zdarzenie, w którym nastolatki mają tylko rower.

Więc, $P(A) = 50/100 = 0.5$ i $P(A \cap B) = 30/100 = 0.3$ z zadanego problemu.

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

Stąd prawdopodobieństwo, że nastolatek ma rower, biorąc pod uwagę, że ma rower, wynosi 60%.

Problem 2

W klasie 50% wszystkich uczniów gra w krykieta, a 25% wszystkich uczniów gra w krykieta i siatkówkę. Jakie jest prawdopodobieństwo, że uczeń gra w siatkówkę, biorąc pod uwagę, że uczeń gra w krykieta?

Solution

Załóżmy, że A to wydarzenie, w którym uczniowie grają tylko w krykieta, a B to wydarzenie, w którym uczniowie grają tylko w siatkówkę.

Więc, $P(A) = 50/100 =0.5$ i $P(A \cap B) = 25/ 100 =0.25$ z zadanego problemu.

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

Stąd prawdopodobieństwo, że uczeń gra w siatkówkę, biorąc pod uwagę, że uczeń gra w krykieta, wynosi 50%.

Problem 3

Pomieszano sześć dobrych laptopów i trzy uszkodzone laptopy. Aby znaleźć uszkodzone laptopy, wszystkie są losowo testowane jeden po drugim. Jakie jest prawdopodobieństwo znalezienia obu wadliwych laptopów w pierwszych dwóch typach?

Solution

Niech A będzie zdarzeniem, w którym znajdziemy uszkodzony laptop w pierwszym teście, a B będzie zdarzeniem, w którym znajdziemy uszkodzony laptop w drugim teście.

W związku z tym, $P(A \cap B) = P(A)P(B|A) =3/9 \times 2/8 = 1/12$

Twierdzenie Bayesa

Theorem - Jeśli A i B są dwoma wzajemnie wykluczającymi się zdarzeniami, gdzie $P(A)$ jest prawdopodobieństwem A i $P(B)$ jest prawdopodobieństwem B, $P(A | B)$ jest prawdopodobieństwem A przy założeniu, że B jest prawdziwe. $P(B | A)$ jest prawdopodobieństwem B przy założeniu, że A jest prawdziwe, to twierdzenie Bayesa stwierdza -

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

Zastosowanie twierdzenia Bayesa

  • W sytuacjach, gdy wszystkie zdarzenia z przestrzeni próbnej wzajemnie się wykluczają.

  • W sytuacjach, w których albo $P( A_i \cap B )$ dla każdego $A_i$ lub $P( A_i )$ i $P(B|A_i)$ dla każdego $A_i$ jest znany.

Problem

Rozważ trzy stojaki na długopisy. Pierwszy stojak na pióro zawiera 2 czerwone i 3 niebieskie pióra; druga ma 3 czerwone i 2 niebieskie pióra; a trzeci ma 4 czerwone długopisy i 1 niebieski. Istnieje równe prawdopodobieństwo wyboru każdego stojaka na długopisy. Jeśli losuje się jeden długopis, jakie jest prawdopodobieństwo, że jest to czerwony długopis?

Solution

Pozwolić $A_i$jako zdarzenie I th pióra podstawa jest wybrany.

Tutaj i = 1,2,3.

Ponieważ prawdopodobieństwo wyboru stojaka na długopis jest równe, $P(A_i) = 1/3$

Niech B będzie zdarzeniem, w którym zostanie narysowany czerwony długopis.

Prawdopodobieństwo, że czerwony długopis zostanie wybrany spośród pięciu piór pierwszego stojaka,

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

Prawdopodobieństwo, że czerwony długopis zostanie wybrany spośród pięciu piór drugiego stojaka,

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

Prawdopodobieństwo, że czerwony długopis zostanie wybrany spośród pięciu piór trzeciego stojaka,

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

Zgodnie z twierdzeniem Bayesa,

$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, to technika potwierdzania wyników lub ustalania zdań dla liczb naturalnych. Ta część ilustruje metodę za pomocą różnych przykładów.

Definicja

Mathematical Induction jest techniką matematyczną używaną do udowodnienia twierdzenia, wzoru lub twierdzenia, które są prawdziwe dla każdej liczby naturalnej.

Technika obejmuje dwa kroki, aby udowodnić stwierdzenie, jak podano poniżej -

Step 1(Base step) - Dowodzi, że stwierdzenie jest prawdziwe dla wartości początkowej.

Step 2(Inductive step)- Dowodzi, że jeśli stwierdzenie jest prawdziwe dla n- tej iteracji (lub liczby n ), to jest również prawdziwe dla (n + 1) tej iteracji (lub liczby n + 1 ).

Jak to zrobić

Step 1- Rozważ wartość początkową, dla której stwierdzenie jest prawdziwe. Należy wykazać, że stwierdzenie to jest prawdziwe dla n = wartość początkowa.

Step 2- Załóżmy, że stwierdzenie jest prawdziwe dla dowolnej wartości n = k . Następnie udowodnij, że stwierdzenie jest prawdziwe dla n = k + 1 . W rzeczywistości dzielimy n = k + 1 na dwie części, jedna część to n = k (co jest już udowodnione) i próbujemy udowodnić drugą część.

Zadanie 1

$3^n-1$ jest wielokrotnością 2 dla n = 1, 2, ...

Solution

Step 1 - Na $n = 1, 3^1-1 = 3-1 = 2$ czyli wielokrotność 2

Step 2 - Załóżmy $3^n-1$ jest prawdziwe dla $n=k$, W związku z tym, $3^k -1$ jest prawdą (jest to założenie)

Musimy to udowodnić $3^{k+1}-1$ jest również wielokrotnością 2

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

Pierwsza część $(2 \times 3k)$ z pewnością będzie wielokrotnością 2 i drugiej części $(3k -1)$ jest również prawdziwe, jak nasze poprzednie założenie.

W związku z tym, $3^{k+1} – 1$ jest wielokrotnością 2.

Tak więc zostało to udowodnione $3^n – 1$ jest wielokrotnością 2.

Problem 2

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

Solution

Step 1 - Na $n=1, 1 = 1^2$W związku z tym krok 1 jest spełniony.

Step 2 - Załóżmy, że to stwierdzenie jest prawdziwe $n=k$.

W związku z tym, $1 + 3 + 5 + \dots + (2k-1) = k^2$ jest prawdą (jest to założenie)

Musimy to udowodnić $1 + 3 + 5 + ... + (2(k+1)-1) = (k+1)^2$ również trzyma

$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$

Więc, $1 + 3 + 5 + \dots + (2(k+1) - 1) = (k+1)^2$ przytrzymaj, co spełnia krok 2.

W związku z tym, $1 + 3 + 5 + \dots + (2n - 1) = n^2$ jest udowodnione.

Problem 3

Udowodnij to $(ab)^n = a^nb^n$ jest prawdziwe dla każdej liczby naturalnej $n$

Solution

Step 1 - Na $n=1, (ab)^1 = a^1b^1 = ab$W związku z tym krok 1 jest spełniony.

Step 2 - Załóżmy, że to stwierdzenie jest prawdziwe $n=k$, W związku z tym, $(ab)^k = a^kb^k$ jest prawdą (jest to założenie).

Musimy to udowodnić $(ab)^{k+1} = a^{k+1}b^{k+1}$ również przytrzymaj

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

Lub, $(ab)^k (ab) = (a^k b^k ) (ab)$ [Mnożenie obu stron przez „ab”]

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

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

W związku z tym udowodniono krok 2.

Więc, $(ab)^n = a^nb^n$ jest prawdziwe dla każdej liczby naturalnej n.

Silna indukcja

Silna indukcja to kolejna forma indukcji matematycznej. Dzięki tej technice indukcyjnej możemy udowodnić, że funkcja zdaniowa$P(n)$ jest prawdziwe dla wszystkich dodatnich liczb całkowitych, $n$, wykonując następujące kroki -

  • Step 1(Base step) - To dowodzi, że wstępna propozycja $P(1)$ prawdziwe.

  • Step 2(Inductive step) - To udowadnia, że ​​oświadczenie warunkowe $[P(1) \land P(2) \land P(3) \land \dots \land P(k)] → P(k + 1)$ jest prawdziwe dla dodatnich liczb całkowitych $k$.

W tym rozdziale omówimy, w jaki sposób techniki rekurencyjne mogą wyprowadzać sekwencje i być używane do rozwiązywania problemów z liczeniem. Wywoływana jest procedura wyszukiwania terminów sekwencji w sposób rekurencyjnyrecurrence relation. Badamy teorię liniowych relacji rekurencyjnych i ich rozwiązania. Na koniec wprowadzamy funkcje generujące do rozwiązywania relacji rekurencyjnych.

Definicja

Relacja rekurencji to równanie, które rekurencyjnie definiuje sekwencję, w której następny wyraz jest funkcją poprzednich wyrazów (wyrażanie $F_n$ jako kombinacja $F_i$ z $i < n$).

Example - Szereg Fibonacciego - $F_n = F_{n-1} + F_{n-2}$, Wieża Hanoi - $F_n = 2F_{n-1} + 1$

Relacje liniowej powtarzalności

Liniowe równanie rekurencji stopnia k lub rzędu k jest równaniem rekurencji w formacie $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$ jest stałą i $A_k \neq 0$) na ciągu liczb jako wielomian pierwszego stopnia.

Oto kilka przykładów równań rekurencji liniowej -

Relacje cykliczne Wartości początkowe Rozwiązania
F n = F n-1 + F n-2 a 1 = a 2 = 1 Liczba Fibonacciego
F n = F n-1 + F n-2 a 1 = 1, a 2 = 3 Lucas Number
F n = F n-2 + F n-3 a 1 = a 2 = a 3 = 1 Sekwencja Padovana
F n = 2F n-1 + F n-2 a 1 = 0, a 2 = 1 Numer pelletu

Jak rozwiązać relację liniowej powtarzalności

Załóżmy, że relacja o dwóch uporządkowanych liniowych nawrotach to - $F_n = AF_{n-1} +BF_{n-2}$ gdzie A i B to liczby rzeczywiste.

Charakterystyczne równanie dla powyższej relacji nawrotu to -

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

Podczas wyszukiwania korzeni mogą wystąpić trzy przypadki -

Case 1 - Jeśli to równanie uwzględnia jako $(x- x_1)(x- x_1) = 0$ i tworzy dwa różne prawdziwe korzenie $x_1$ i $x_2$, następnie $F_n = ax_1^n+ bx_2^n$jest rozwiązaniem. [Tutaj a i b są stałymi]

Case 2 - Jeśli to równanie uwzględnia jako $(x- x_1)^2 = 0$ i tworzy pojedynczy prawdziwy korzeń $x_1$, następnie $F_n = a x_1^n+ bn x_1^n$ jest rozwiązaniem.

Case 3 - Jeśli równanie daje dwa różne złożone pierwiastki, $x_1$ i $x_2$ w postaci polarnej $x_1 = r \angle \theta$ i $x_2 = r \angle(- \theta)$, następnie $F_n = r^n (a cos(n\theta)+ b sin(n\theta))$ jest rozwiązaniem.

Problem 1

Rozwiąż relację powtarzania $F_n = 5F_{n-1} - 6F_{n-2}$ gdzie $F_0 = 1$ i $F_1 = 4$

Solution

Charakterystyczne równanie relacji rekurencji to -

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

Więc, $(x - 3) (x - 2) = 0$

Dlatego korzenie są -

$x_1 = 3$ i $x_2 = 2$

Korzenie są prawdziwe i wyraźne. Jest to więc przypadek 1

Stąd rozwiązaniem jest -

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

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

W związku z tym,

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

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

Rozwiązując te dwa równania, otrzymujemy $ a = 2$ i $b = -1$

Stąd ostatecznym rozwiązaniem jest -

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

Problem 2

Rozwiąż relację powtarzania - $F_n = 10F_{n-1} - 25F_{n-2}$ gdzie $F_0 = 3$ i $F_1 = 17$

Solution

Charakterystyczne równanie relacji rekurencji to -

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

Więc $(x - 5)^2 = 0$

Dlatego istnieje jeden prawdziwy korzeń $x_1 = 5$

Ponieważ istnieje pojedynczy pierwiastek o wartości rzeczywistej, ma to postać przypadku 2

Stąd rozwiązaniem jest -

$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$

Rozwiązując te dwa równania, otrzymujemy $a = 3$ i $b = 2/5$

Stąd ostatecznym rozwiązaniem jest - $F_n = 3.5^n +( 2/5) .n.2^n $

Problem 3

Solve the recurrence relation $F_n = 2F_{n-1} - 2F_{n-2}$ where $F_0 = 1$ and $F_1 = 3$

Solution

The characteristic equation of the recurrence relation is −

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

Hence, the roots are −

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

In polar form,

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

The roots are imaginary. So, this is in the form of case 3.

Hence, the solution is −

$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)$

Solving these two equations we get $a = 1$ and $b = 2$

Hence, the final solution is −

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

Non-Homogeneous Recurrence Relation and Particular Solutions

A recurrence relation is called non-homogeneous if it is in the form

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

Its associated homogeneous recurrence relation is $F_n = AF_{n–1} + BF_{n-2}$

The solution $(a_n)$ of a non-homogeneous recurrence relation has two parts.

First part is the solution $(a_h)$ of the associated homogeneous recurrence relation and the second part is the particular solution $(a_t)$.

$$a_n=a_h+a_t$$

Solution to the first part is done using the procedures discussed in the previous section.

To find the particular solution, we find an appropriate trial solution.

Let $f(n) = cx^n$ ; let $x^2 = Ax + B$ be the characteristic equation of the associated homogeneous recurrence relation and let $x_1$ and $x_2$ be its roots.

  • If $x \ne x_1$ and $x \ne x_2$, then $a_t = Ax^n$

  • If $x = x_1$, $x \ne x_2$, then $a_t = Anx^n$

  • If $x = x_1 = x_2$, then $a_t = An^2x^n$

Example

Let a non-homogeneous recurrence relation be $F_n = AF_{n–1} + BF_{n-2} + f(n)$ with characteristic roots $x_1 = 2$ and $x_2 = 5$. Trial solutions for different possible values of $f(n)$ are as follows −

Previous Page Print Page
Next Page