Matematica discreta - Guida rapida

La matematica può essere ampiamente classificata in due categorie:

• Continuous Mathematics- Si basa sulla linea numerica continua o sui numeri reali. È caratterizzato dal fatto che tra due numeri qualsiasi, c'è quasi sempre un insieme infinito di numeri. Ad esempio, una funzione in matematica continua può essere tracciata in una curva morbida senza interruzioni.

• Discrete Mathematics- Coinvolge valori distinti; cioè tra due punti qualsiasi, c'è un numero di punti numerabile. Ad esempio, se abbiamo un insieme finito di oggetti, la funzione può essere definita come un elenco di coppie ordinate aventi questi oggetti e può essere presentata come un elenco completo di quelle coppie.

Argomenti di matematica discreta

Sebbene non possa esserci un numero definito di rami della matematica discreta, i seguenti argomenti sono quasi sempre trattati in qualsiasi studio su questo argomento:

• Insiemi, relazioni e funzioni
• Logica matematica
• Teoria dei gruppi
• Teoria del conteggio
• Probability
• Induzione matematica e relazioni di ricorrenza
• Teoria dei grafi
• Trees
• Algebra booleana

Discuteremo ciascuno di questi concetti nei capitoli successivi di questo tutorial.

Matematico tedesco G. Cantorha introdotto il concetto di set. Aveva definito un insieme come una raccolta di oggetti definiti e distinguibili selezionati mediante determinate regole o descrizioni.

Setla teoria costituisce la base di molti altri campi di studio come la teoria dei conteggi, le relazioni, la teoria dei grafi e le macchine a stati finiti. In questo capitolo tratteremo i diversi aspetti diSet Theory.

Set - Definizione

Un set è una raccolta non ordinata di elementi diversi. Un set può essere scritto esplicitamente elencando i suoi elementi usando la parentesi di set. Se l'ordine degli elementi viene modificato o qualsiasi elemento di un set viene ripetuto, non vengono apportate modifiche al set.

Alcuni esempi di set

• Un insieme di tutti i numeri interi positivi
• Un insieme di tutti i pianeti del sistema solare
• Un insieme di tutti gli stati dell'India
• Un insieme di tutte le lettere minuscole dell'alfabeto

Rappresentazione di un set

Gli insiemi possono essere rappresentati in due modi:

• Elenco o forma tabulare
• Imposta la notazione del costruttore

Elenco o forma tabulare

L'insieme è rappresentato elencando tutti gli elementi che lo compongono. Gli elementi sono racchiusi tra parentesi graffe e separati da virgole.

Example 1 - Set di vocali in alfabeto inglese, $A = \lbrace a,e,i,o,u \rbrace$

Example 2 - Set di numeri dispari inferiori a 10, $B = \lbrace 1,3,5,7,9 \rbrace$

Imposta la notazione del costruttore

L'insieme è definito specificando una proprietà che gli elementi dell'insieme hanno in comune. Il set è descritto come$A = \lbrace x : p(x) \rbrace$

Example 1 - Il set $\lbrace a,e,i,o,u \rbrace$ è scritto come -

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

Example 2 - Il set $\lbrace 1,3,5,7,9 \rbrace$ è scritto come -

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

Se un elemento x è un membro di qualsiasi insieme S, è indicato con $x \in S$ e se un elemento y non è un membro dell'insieme S, è indicato con $y \notin S$.

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

Alcuni set importanti

N - l'insieme di tutti i numeri naturali = $\lbrace1, 2, 3, 4, .....\rbrace$

Z - l'insieme di tutti i numeri interi = $\lbrace....., -3, -2, -1, 0, 1, 2, 3, .....\rbrace$

Z⁺ - l'insieme di tutti i numeri interi positivi

Q - l'insieme di tutti i numeri razionali

R - l'insieme di tutti i numeri reali

W - l'insieme di tutti i numeri interi

Cardinalità di un set

Cardinalità di un insieme S, indicato da $|S|$, è il numero di elementi dell'insieme. Il numero è indicato anche come numero cardinale. Se un insieme ha un numero infinito di elementi, la sua cardinalità è$\infty$.

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

Se ci sono due insiemi X e Y,

• $|X| = |Y|$denota due insiemi X e Y aventi la stessa cardinalità. Si verifica quando il numero di elementi in X è esattamente uguale al numero di elementi in Y. In questo caso, esiste una funzione biettiva "f" da X a Y.

• $|X| \le |Y|$denota che la cardinalità dell'insieme X è minore o uguale alla cardinalità dell'insieme Y. Si verifica quando il numero di elementi in X è minore o uguale a quello di Y. Qui esiste una funzione iniettiva 'f' da X a Y.

• $|X| \lt |Y|$denota che la cardinalità dell'insieme X è minore della cardinalità dell'insieme Y. Si verifica quando il numero di elementi in X è inferiore a quello di Y. Qui, la funzione "f" da X a Y è una funzione iniettiva ma non biiettiva.

• $If\ |X| \le |Y|$ e $|X| \ge |Y|$ poi $|X| = |Y|$. Gli insiemi X e Y sono comunemente indicati come insiemi equivalenti.

Tipi di set

I set possono essere classificati in molti tipi. Alcuni dei quali sono finiti, infiniti, sottoinsiemi, universali, propri, singoletti, ecc.

Insieme finito

Un insieme che contiene un numero definito di elementi è chiamato insieme finito.

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

Set infinito

Un insieme che contiene un numero infinito di elementi è chiamato un insieme infinito.

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

Sottoinsieme

Un insieme X è un sottoinsieme dell'insieme Y (Scritto come $X \subseteq Y$) se ogni elemento di X è un elemento dell'insieme Y.

Example 1 - Lascia, $X = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$ e $Y = \lbrace 1, 2 \rbrace$. Qui l'insieme Y è un sottoinsieme dell'insieme X poiché tutti gli elementi dell'insieme Y sono nell'insieme X. Quindi, possiamo scrivere$Y \subseteq X$.

Example 2 - Lascia, $X = \lbrace 1, 2, 3 \rbrace$ e $Y = \lbrace 1, 2, 3 \rbrace$. Qui l'insieme Y è un sottoinsieme (non un sottoinsieme appropriato) dell'insieme X poiché tutti gli elementi dell'insieme Y sono nell'insieme X. Quindi, possiamo scrivere$Y \subseteq X$.

Sottoinsieme proprio

Il termine "sottoinsieme proprio" può essere definito come "sottoinsieme di ma non uguale a". Un insieme X è un sottoinsieme appropriato dell'insieme Y (scritto come$ X \subset Y $) se ogni elemento di X è un elemento dell'insieme Y e $|X| \lt |Y|$.

Example - Lascia, $X = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$ e $Y = \lbrace 1, 2 \rbrace$. Qui impostato$Y \subset X$ poiché tutti gli elementi in $Y$ sono contenuti in $X$ anche e $X$ ha almeno un elemento è più di set $Y$.

Set universale

È una raccolta di tutti gli elementi in un particolare contesto o applicazione. Tutti gli insiemi in quel contesto o applicazione sono essenzialmente sottoinsiemi di questo insieme universale. Gli insiemi universali sono rappresentati come$U$.

Example - Possiamo definire $U$come l'insieme di tutti gli animali sulla terra. In questo caso, l'insieme di tutti i mammiferi è un sottoinsieme di$U$, l'insieme di tutti i pesci è un sottoinsieme di $U$, l'insieme di tutti gli insetti è un sottoinsieme di $U$, e così via.

Insieme vuoto o insieme nullo

Un set vuoto non contiene elementi. È indicato da$\emptyset$. Poiché il numero di elementi in un insieme vuoto è finito, l'insieme vuoto è un insieme finito. La cardinalità dell'insieme vuoto o dell'insieme nullo è zero.

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

Set Singleton o Set di unità

L'insieme singleton o l'insieme di unità contiene solo un elemento. Un insieme singleton è indicato da$\lbrace s \rbrace$.

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

Set uguale

Se due insiemi contengono gli stessi elementi si dice che sono uguali.

Example - Se $A = \lbrace 1, 2, 6 \rbrace$ e $B = \lbrace 6, 1, 2 \rbrace$, sono uguali in quanto ogni elemento dell'insieme A è un elemento dell'insieme B e ogni elemento dell'insieme B è un elemento dell'insieme A.

Set equivalente

Se le cardinalità di due insiemi sono le stesse, vengono chiamate insiemi equivalenti.

Example - Se $A = \lbrace 1, 2, 6 \rbrace$ e $B = \lbrace 16, 17, 22 \rbrace$, sono equivalenti in quanto la cardinalità di A è uguale alla cardinalità di B. es $|A| = |B| = 3$

Set sovrapposti

Due insiemi che hanno almeno un elemento comune sono chiamati insiemi sovrapposti.

In caso di serie sovrapposte -

• $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 - Lascia, $A = \lbrace 1, 2, 6 \rbrace$ e $B = \lbrace 6, 12, 42 \rbrace$. C'è un elemento comune "6", quindi questi insiemi sono insiemi sovrapposti.

Insieme disgiunto

Due insiemi A e B sono chiamati insiemi disgiunti se non hanno nemmeno un elemento in comune. Pertanto, gli insiemi disgiunti hanno le seguenti proprietà:

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

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

Example - Lascia, $A = \lbrace 1, 2, 6 \rbrace$ e $B = \lbrace 7, 9, 14 \rbrace$, non esiste un singolo elemento comune, quindi questi insiemi sono insiemi sovrapposti.

Diagrammi di Venn

Il diagramma di Venn, inventato nel 1880 da John Venn, è un diagramma schematico che mostra tutte le possibili relazioni logiche tra diversi insiemi matematici.

Examples

Imposta operazioni

Le operazioni di gruppo includono Unione di gruppi, Intersezione di gruppo, Differenza di gruppo, Complemento di gruppo e Prodotto cartesiano.

Set Union

L'unione degli insiemi A e B (indicata con $A \cup B$) è l'insieme di elementi che si trovano in A, in B o sia in A che in B. Quindi, $A \cup B = \lbrace x \:| \: x \in A\ OR\ x \in B \rbrace$.

Example - Se $A = \lbrace 10, 11, 12, 13 \rbrace$ e B = $\lbrace 13, 14, 15 \rbrace$, poi $A \cup B = \lbrace 10, 11, 12, 13, 14, 15 \rbrace$. (L'elemento comune compare solo una volta)

Imposta intersezione

L'intersezione degli insiemi A e B (indicata con $A \cap B$) è l'insieme di elementi che sono sia in A che in B. Quindi, $A \cap B = \lbrace x \:|\: x \in A\ AND\ x \in B \rbrace$.

Example - Se $A = \lbrace 11, 12, 13 \rbrace$ e $B = \lbrace 13, 14, 15 \rbrace$, poi $A \cap B = \lbrace 13 \rbrace$.

Imposta differenza / complemento relativo

La differenza dell'insieme degli insiemi A e B (indicata da $A – B$) è l'insieme di elementi che sono solo in A ma non in B. Quindi, $A - B = \lbrace x \:| \: x \in A\ AND\ x \notin B \rbrace$.

Example - Se $A = \lbrace 10, 11, 12, 13 \rbrace$ e $B = \lbrace 13, 14, 15 \rbrace$, poi $(A - B) = \lbrace 10, 11, 12 \rbrace$ e $(B - A) = \lbrace 14, 15 \rbrace$. Qui possiamo vedere$(A - B) \ne (B - A)$

Complemento di un set

Il complemento di un insieme A (indicato da $A’$) è l'insieme di elementi che non sono nell'insieme A. Quindi, $A' = \lbrace x | x \notin A \rbrace$.

Più specificamente, $A'= (U - A)$ dove $U$ è un set universale che contiene tutti gli oggetti.

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

Prodotto cartesiano / Prodotto incrociato

Il prodotto cartesiano di n numero di insiemi $A_1, A_2, \dots A_n$ indicato come $A_1 \times A_2 \dots \times A_n$ possono essere definite come tutte le possibili coppie ordinate $(x_1, x_2, \dots x_n)$ dove $x_1 \in A_1, x_2 \in A_2, \dots x_n \in A_n$

Example - Se prendiamo due set $A = \lbrace a, b \rbrace$ e $B = \lbrace 1, 2 \rbrace$,

Il prodotto cartesiano di A e B è scritto come - $A \times B = \lbrace (a, 1), (a, 2), (b, 1), (b, 2)\rbrace$

Il prodotto cartesiano di B e A è scritto come - $B \times A = \lbrace (1, a), (1, b), (2, a), (2, b)\rbrace$

Power Set

Insieme di potenza di un insieme S è l'insieme di tutti i sottoinsiemi di S compreso l'insieme vuoto. La cardinalità di un insieme di potenze di un insieme S di cardinalità n è$2^n$. Il set di alimentazione è indicato come$P(S)$.

Example −

Per un set $S = \lbrace a, b, c, d \rbrace$ calcoliamo i sottoinsiemi -

• Sottoinsiemi con 0 elementi - $\lbrace \emptyset \rbrace$ (il set vuoto)

• Sottoinsiemi con 1 elemento - $\lbrace a \rbrace, \lbrace b \rbrace, \lbrace c \rbrace, \lbrace d \rbrace$

• Sottoinsiemi con 2 elementi - $\lbrace a, b \rbrace, \lbrace a,c \rbrace, \lbrace a, d \rbrace, \lbrace b, c \rbrace, \lbrace b,d \rbrace,\lbrace c,d \rbrace$

• Sottoinsiemi con 3 elementi - $\lbrace a ,b, c\rbrace,\lbrace a, b, d \rbrace, \lbrace a,c,d \rbrace,\lbrace b,c,d \rbrace$

• Sottoinsiemi con 4 elementi - $\lbrace a, b, c, d \rbrace$

Quindi, $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 - Anche il power set di un set vuoto è un set vuoto.

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

Partizionamento di un set

La partizione di un insieme, diciamo S , è una raccolta di n sottoinsiemi disgiunti, diciamo$P_1, P_2, \dots P_n$ che soddisfa le seguenti tre condizioni:

• $P_i$ non contiene l'insieme vuoto.

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

• L'unione dei sottoinsiemi deve essere uguale all'intero insieme originale.

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

• L'intersezione di due insiemi distinti è vuota.

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

Example

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

Un probabile partizionamento è $\lbrace a \rbrace, \lbrace b, c, d \rbrace, \lbrace e, f, g, h \rbrace$

Un altro probabile partizionamento è $\lbrace a, b \rbrace, \lbrace c, d \rbrace, \lbrace e, f, g, h \rbrace$

Numeri di campana

I numeri di campana forniscono il conteggio del numero di modi per partizionare un set. Sono indicati da$B_n$ dove n è la cardinalità dell'insieme.

Example -

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

Le partizioni alternative sono:

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$

Quindi $B_3 = 5$

Ogni volta che si discute di set, la relazione tra gli elementi dei set è la cosa successiva che viene fuori. Relations può esistere tra oggetti dello stesso insieme o tra oggetti di due o più insiemi.

Definizione e proprietà

Una relazione binaria R da x a y (scritta come $xRy$ o $R(x,y)$) è un sottoinsieme del prodotto cartesiano $x \times y$. Se la coppia ordinata di G è invertita, cambia anche la relazione.

Generalmente una relazione n-ari R tra insiemi $A_1, \dots ,\ and\ A_n$ è un sottoinsieme del prodotto n-ario $A_1 \times \dots \times A_n$. La cardinalità minima di una relazione R è Zero e la massima è$n^2$ in questo caso.

Una relazione binaria R su un singolo insieme A è un sottoinsieme di $A \times A$.

Per due insiemi distinti, A e B, aventi rispettivamente cardinalità m e n , la cardinalità massima di una relazione R da A a B è mn .

Dominio e intervallo

Se ci sono due insiemi A e B e la relazione R ha una coppia di ordini (x, y), allora -

• Il domain di R, Dom (R), è l'insieme $\lbrace x \:| \: (x, y) \in R \:for\: some\: y\: in\: B \rbrace$

• Il range di R, Ran (R), è l'insieme $\lbrace y\: |\: (x, y) \in R \:for\: some\: x\: in\: A\rbrace$

Esempi

Permettere, $A = \lbrace 1, 2, 9 \rbrace $ e $ B = \lbrace 1, 3, 7 \rbrace$

• Caso 1 - Se la relazione R è "uguale a", allora $R = \lbrace (1, 1), (3, 3) \rbrace$

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

• Caso 2 - Se la relazione R è 'minore di' allora $R = \lbrace (1, 3), (1, 7), (2, 3), (2, 7) \rbrace$

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

• Caso 3 - Se la relazione R è 'maggiore di' allora $R = \lbrace (2, 1), (9, 1), (9, 3), (9, 7) \rbrace$

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

Rappresentazione delle relazioni utilizzando il grafico

Una relazione può essere rappresentata utilizzando un grafico orientato.

Il numero di vertici nel grafo è uguale al numero di elementi nell'insieme da cui è stata definita la relazione. Per ogni coppia ordinata (x, y) nella relazione R, ci sarà un bordo diretto dal vertice "x" al vertice "y". Se c'è una coppia ordinata (x, x), ci sarà un ciclo automatico sul vertice 'x'.

Supponiamo che ci sia una relazione $R = \lbrace (1, 1), (1,2), (3, 2) \rbrace$ sul set $S = \lbrace 1, 2, 3 \rbrace$, può essere rappresentato dal seguente grafico -

Tipi di relazioni

• Il Empty Relation tra gli insiemi X e Y, o su E, è l'insieme vuoto $\emptyset$

• Il Full Relation tra gli insiemi X e Y è l'insieme $X \times Y$

• Il Identity Relation sul set X è il set $\lbrace (x, x) | x \in X \rbrace$

• La relazione inversa R 'di una relazione R è definita come - $R' = \lbrace (b, a) | (a, b) \in R \rbrace$

  Example - Se $R = \lbrace (1, 2), (2, 3) \rbrace$ poi $R' $ sarà $\lbrace (2, 1), (3, 2) \rbrace$

• Viene chiamata una relazione R sull'insieme A. Reflexive Se $\forall a \in A$ è correlato a un (aRa detiene)

  Example - La relazione $R = \lbrace (a, a), (b, b) \rbrace$ sul set $X = \lbrace a, b \rbrace$ è riflessivo.

• Viene chiamata una relazione R sull'insieme A. Irreflexive se no $a \in A$ è correlato ad a (aRa non tiene).

  Example - La relazione $R = \lbrace (a, b), (b, a) \rbrace$ sul set $X = \lbrace a, b \rbrace$ è irriverente.

• Viene chiamata una relazione R sull'insieme A. Symmetric Se $xRy$ implica $yRx$, $\forall x \in A$ e $\forall y \in A$.

  Example - La relazione $R = \lbrace (1, 2), (2, 1), (3, 2), (2, 3) \rbrace$ sul set $A = \lbrace 1, 2, 3 \rbrace$ è simmetrico.

• Viene chiamata una relazione R sull'insieme A. Anti-Symmetric Se $xRy$ e $yRx$ implica $x = y \: \forall x \in A$ e $\forall y \in A$.

  Example - La relazione $R = \lbrace (x, y)\to N |\:x \leq y \rbrace$ è antisimmetrico da allora $x \leq y$ e $y \leq x$ implica $x = y$.

• Viene chiamata una relazione R sull'insieme A. Transitive Se $xRy$ e $yRz$ implica $xRz, \forall x,y,z \in A$.

  Example - La relazione $R = \lbrace (1, 2), (2, 3), (1, 3) \rbrace$ sul set $A = \lbrace 1, 2, 3 \rbrace$ è transitivo.

• Una relazione è un Equivalence Relation se è riflessivo, simmetrico e transitivo.

  Example - La relazione $R = \lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2), (1,3), (3,1) \rbrace$ sul set $A = \lbrace 1, 2, 3 \rbrace$ è una relazione di equivalenza poiché è riflessiva, simmetrica e transitiva.

UN Functionassegna a ogni elemento di un insieme, esattamente un elemento di un insieme correlato. Le funzioni trovano la loro applicazione in vari campi come la rappresentazione della complessità computazionale di algoritmi, il conteggio di oggetti, lo studio di sequenze e stringhe, solo per citarne alcuni. Il terzo e ultimo capitolo di questa parte evidenzia gli aspetti importanti delle funzioni.

Funzione - Definizione

Una funzione o mappatura (definita come $f: X \rightarrow Y$) è una relazione tra gli elementi di un insieme X e gli elementi di un altro insieme Y (X e Y sono insiemi non vuoti). X è chiamato Dominio e Y è chiamato Codominio della funzione 'f'.

La funzione 'f' è una relazione su X e Y tale che per ciascuno $x \in X$, esiste un unico $y \in Y$ tale che $(x,y) \in R$. 'x' è chiamata pre-immagine e 'y' è chiamata immagine della funzione f.

Una funzione può essere uno a uno o molti a uno ma non uno a molti.

Funzione iniettiva / uno-a-uno

Una funzione $f: A \rightarrow B$ è una funzione iniettiva o uno-a-uno se per ogni $b \in B$, ne esiste al massimo uno $a \in A$ tale che $f(s) = t$.

Ciò significa una funzione f è iniettiva se $a_1 \ne a_2$ implica $f(a1) \ne f(a2)$.

Esempio

• $f: N \rightarrow N, f(x) = 5x$ è iniettiva.

• $f: N \rightarrow N, f(x) = x^2$ è iniettiva.

• $f: R\rightarrow R, f(x) = x^2$ non è iniettiva come $(-x)^2 = x^2$

Funzione Surjective / Onto

Una funzione $f: A \rightarrow B$è suriettiva (su) se l'immagine di f è uguale al suo intervallo. Equivalentemente, per ogni$b \in B$, ce ne sono alcuni $a \in A$ tale che $f(a) = b$. Ciò significa che per ogni y in B, esiste una x in A tale che$y = f(x)$.

Esempio

• $f : N \rightarrow N, f(x) = x + 2$ è suriettivo.

• $f : R \rightarrow R, f(x) = x^2$ non è suriettivo poiché non riusciamo a trovare un numero reale il cui quadrato sia negativo.

Corrispondente biettivo / uno-a-uno

Una funzione $f: A \rightarrow B$ è biettivo o corrispondente uno a uno se e solo se f è sia iniettiva che suriettiva.

Problema

Dimostralo una funzione $f: R \rightarrow R$ definito da $f(x) = 2x – 3$ è una funzione biiettiva.

Explanation - Dobbiamo dimostrare che questa funzione è sia iniettiva che suriettiva.

Se $f(x_1) = f(x_2)$, poi $2x_1 – 3 = 2x_2 – 3 $ e lo implica $x_1 = x_2$.

Quindi, f è injective.

Qui, $2x – 3= y$

Così, $x = (y+5)/3$ che appartiene a R e $f(x) = y$.

Quindi, f è surjective.

Da f è Entrambi surjective e injective, possiamo dire f è bijective.

Inversa di una funzione

Il inverse di una funzione corrispondente uno a uno $f : A \rightarrow B$, è la funzione $g : B \rightarrow A$, che detiene la seguente proprietà:

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

Viene chiamata la funzione f invertible, se esiste la sua funzione inversa g.

Esempio

• Una funzione $f : Z \rightarrow Z, f(x)=x+5$, è invertibile poiché ha la funzione inversa $ g : Z \rightarrow Z, g(x)= x-5$.

• Una funzione $f : Z \rightarrow Z, f(x)=x^2$ non è invertibile poiché non è uno a uno come $(-x)^2=x^2$.

Composizione delle funzioni

Due funzioni $f: A \rightarrow B$ e $g: B \rightarrow C$ può essere composto per dare una composizione $g o f$. Questa è una funzione da A a C definita da$(gof)(x) = g(f(x))$

Esempio

Permettere $f(x) = x + 2$ e $g(x) = 2x + 1$, trova $( f o g)(x)$ e $( g o f)(x)$.

Soluzione

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

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

Alcuni fatti sulla composizione

• Se f e g sono uno a uno, la funzione $(g o f)$ è anche uno a uno.

• Se feg sono su, allora la funzione $(g o f)$ è anche su.

• La composizione detiene sempre la proprietà associativa ma non la proprietà commutativa.

Le regole della logica matematica specificano i metodi di ragionamento delle affermazioni matematiche. Il filosofo greco, Aristotele, è stato il pioniere del ragionamento logico. Il ragionamento logico fornisce la base teorica per molte aree della matematica e di conseguenza dell'informatica. Ha molte applicazioni pratiche in informatica come la progettazione di macchine informatiche, intelligenza artificiale, definizione di strutture dati per linguaggi di programmazione ecc.

Propositional Logicsi occupa di affermazioni alle quali possono essere assegnati i valori di verità "vero" e "falso". Lo scopo è analizzare queste affermazioni individualmente o in modo composito.

Logica preposizionale - Definizione

Una proposizione è una raccolta di asserzioni dichiarative che ha un valore di verità "vero" o un valore di verità "falso". Una proposizione consiste di variabili proposizionali e connettivi. Indichiamo le variabili proposizionali con lettere maiuscole (A, B, ecc.). I connettivi collegano le variabili proposizionali.

Di seguito sono riportati alcuni esempi di proposizioni:

• "L'uomo è mortale", restituisce il valore di verità "VERO"
• "12 + 9 = 3 - 2", restituisce il valore di verità "FALSE"

Quanto segue non è una proposta:

• "A è minore di 2". È perché a meno che non diamo un valore specifico di A, non possiamo dire se l'affermazione è vera o falsa.

Connettivi

Nella logica proposizionale generalmente usiamo cinque connettivi che sono:

• O ($\lor$)

• E ($\land$)

• Negazione / NOT ($\lnot$)

• Implicazione / se-allora ($\rightarrow$)

• Se e solo se ($\Leftrightarrow$).

OR ($\lor$) - L'operazione OR di due proposizioni A e B (scritte come $A \lor B$) è vero se almeno una qualsiasi delle variabili proposizionali A o B è vera.

La tabella della verità è la seguente:

UN	B	A ∨ B
Vero	Vero	Vero
Vero	Falso	Vero
Falso	Vero	Vero
Falso	Falso	Falso

AND ($\land$) - L'operazione AND di due proposizioni A e B (scritte come $A \land B$) è vero se entrambe le variabili proposizionali A e B sono vere.

La tabella della verità è la seguente:

UN	B	A ∧ B
Vero	Vero	Vero
Vero	Falso	Falso
Falso	Vero	Falso
Falso	Falso	Falso

Negation ($\lnot$) - La negazione di una proposizione A (scritta come $\lnot A$) è falso quando A è vero ed è vero quando A è falso.

La tabella della verità è la seguente:

UN	¬ A
Vero	Falso
Falso	Vero

Implication / if-then ($\rightarrow$) - Un'implicazione $A \rightarrow B$è la proposizione "se A, allora B". È falso se A è vero e B è falso. Gli altri casi sono veri.

La tabella della verità è la seguente:

UN	B	A → B
Vero	Vero	Vero
Vero	Falso	Falso
Falso	Vero	Vero
Falso	Falso	Vero

If and only if ($ \Leftrightarrow $) - $A \Leftrightarrow B$ è connettivo logico bi-condizionale che è vero quando peq sono uguali, cioè entrambi sono falsi o entrambi sono veri.

La tabella della verità è la seguente:

UN	B	A ⇔ B
Vero	Vero	Vero
Vero	Falso	Falso
Falso	Vero	Falso
Falso	Falso	Vero

Tautologie

Una tautologia è una formula che è sempre vera per ogni valore delle sue variabili proposizionali.

Example - Dimostralo $\lbrack (A \rightarrow B) \land A \rbrack \rightarrow B$ è una tautologia

La tabella della verità è la seguente:

UN	B	A → B	(A → B) ∧ A	[(A → B) ∧ A] → B
Vero	Vero	Vero	Vero	Vero
Vero	Falso	Falso	Falso	Vero
Falso	Vero	Vero	Falso	Vero
Falso	Falso	Vero	Falso	Vero

Come possiamo vedere ogni valore di $\lbrack (A \rightarrow B) \land A \rbrack \rightarrow B$ è "Vero", è una tautologia.

Contraddizioni

Una contraddizione è una formula che è sempre falsa per ogni valore delle sue variabili proposizionali.

Example - Dimostralo $(A \lor B) \land \lbrack ( \lnot A) \land (\lnot B) \rbrack$ è una contraddizione

La tabella della verità è la seguente:

UN	B	A ∨ B	¬ A	¬ B	(¬ A) ∧ (¬ B)	(A ∨ B) ∧ [(¬ A) ∧ (¬ B)]
Vero	Vero	Vero	Falso	Falso	Falso	Falso
Vero	Falso	Vero	Falso	Vero	Falso	Falso
Falso	Vero	Vero	Vero	Falso	Falso	Falso
Falso	Falso	Falso	Vero	Vero	Vero	Falso

Come possiamo vedere ogni valore di $(A \lor B) \land \lbrack ( \lnot A) \land (\lnot B) \rbrack$ è "Falso", è una contraddizione.

Contingenza

Una contingenza è una formula che ha valori sia veri che falsi per ogni valore delle sue variabili proposizionali.

Example - Dimostralo $(A \lor B) \land (\lnot A)$ una contingenza

La tabella della verità è la seguente:

UN	B	A ∨ B	¬ A	(A ∨ B) ∧ (¬ A)
Vero	Vero	Vero	Falso	Falso
Vero	Falso	Vero	Falso	Falso
Falso	Vero	Vero	Vero	Vero
Falso	Falso	Falso	Vero	Falso

Come possiamo vedere ogni valore di $(A \lor B) \land (\lnot A)$ ha sia "Vero" che "Falso", è una contingenza.

Equivalenze proposizionali

Due affermazioni X e Y sono logicamente equivalenti se sussiste una delle due condizioni seguenti:

• Le tabelle di verità di ogni affermazione hanno gli stessi valori di verità.

• L'affermazione bi-condizionale $X \Leftrightarrow Y$ è una tautologia.

Example - Dimostralo $\lnot (A \lor B) and \lbrack (\lnot A) \land (\lnot B) \rbrack$ sono equivalenti

Test con il ^primo metodo (tabella della verità di corrispondenza)

UN	B	A ∨ B	¬ (A ∨ B)	¬ A	¬ B	[(¬ A) ∧ (¬ B)]
Vero	Vero	Vero	Falso	Falso	Falso	Falso
Vero	Falso	Vero	Falso	Falso	Vero	Falso
Falso	Vero	Vero	Falso	Vero	Falso	Falso
Falso	Falso	Falso	Vero	Vero	Vero	Vero

Qui possiamo vedere i valori di verità di $\lnot (A \lor B) and \lbrack (\lnot A) \land (\lnot B) \rbrack$ sono uguali, quindi le affermazioni sono equivalenti.

Test con il 2 ^° metodo (Bi-condizionalità)

UN	B	¬ (A ∨ B)	[(¬ A) ∧ (¬ B)]	[¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)]
Vero	Vero	Falso	Falso	Vero
Vero	Falso	Falso	Falso	Vero
Falso	Vero	Falso	Falso	Vero
Falso	Falso	Vero	Vero	Vero

Come $\lbrack \lnot (A \lor B) \rbrack \Leftrightarrow \lbrack (\lnot A ) \land (\lnot B) \rbrack$ è una tautologia, le affermazioni sono equivalenti.

Inverse, Converse e Contra-positive

Implicazione / se-allora $(\rightarrow)$è anche chiamata dichiarazione condizionale. Ha due parti:

• Ipotesi, p
• Conclusione, q

Come accennato in precedenza, è indicato come $p \rightarrow q$.

Example of Conditional Statement- "Se fai i compiti, non sarai punito." Qui, "fai i compiti" è l'ipotesi, p, e "non sarai punito" è la conclusione, q.

Inverse- Un inverso dell'affermazione condizionale è la negazione sia dell'ipotesi che della conclusione. Se l'affermazione è "Se p, allora q", l'inverso sarà "Se non p, allora non q". Quindi l'inverso di$p \rightarrow q$ è $ \lnot p \rightarrow \lnot q$.

Example - L'inverso di "Se fai i compiti, non sarai punito" è "Se non fai i compiti, sarai punito".

Converse- Il contrario dell'istruzione condizionale viene calcolato scambiando l'ipotesi e la conclusione. Se l'affermazione è "Se p, allora q", il contrario sarà "Se q, allora p". Il contrario di$p \rightarrow q$ è $q \rightarrow p$.

Example - Il contrario di "Se fai i compiti, non sarai punito" è "Se non sarai punito, fai i compiti".

Contra-positive- Il contro-positivo del condizionale si calcola scambiando l'ipotesi e la conclusione dell'enunciato inverso. Se l'affermazione è "Se p, allora q", il contro-positivo sarà "Se non q, allora non p". Il contro-positivo di$p \rightarrow q$ è $\lnot q \rightarrow \lnot p$.

Example - Il contro-positivo di "Se fai i compiti, non sarai punito" è "Se sei punito, non hai fatto i compiti".

Principio di dualità

Il principio di dualità afferma che per ogni affermazione vera, è anche vera l'affermazione duale ottenuta scambiando le unioni in intersezioni (e viceversa) e scambiando l'insieme universale in un insieme Null (e viceversa). Se il duale di qualsiasi affermazione è l'affermazione stessa, si diceself-dual dichiarazione.

Example - Il doppio di $(A \cap B ) \cup C$ è $(A \cup B) \cap C$

Forme normali

Possiamo convertire qualsiasi proposizione in due forme normali:

• Forma normale congiuntiva
• Forma normale disgiuntiva

Forma normale congiuntiva

Un'istruzione composta è in forma normale congiuntiva se è ottenuta operando AND tra variabili (negazione delle variabili inclusa) connesse con OR. In termini di operazioni sugli insiemi, è un'istruzione composta ottenuta per intersezione tra variabili legate alle unioni.

Examples

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

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

Forma normale disgiuntiva

Un'istruzione composta è in forma normale disgiuntiva se è ottenuta operando OR tra variabili (negazione delle variabili inclusa) connesse con AND. In termini di operazioni sugli insiemi, è un'istruzione composta ottenuta dall'unione tra variabili legate alle intersezioni.

Examples

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

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

Predicate Logic si occupa di predicati, che sono proposizioni contenenti variabili.

Logica del predicato - Definizione

Un predicato è un'espressione di una o più variabili definite su un dominio specifico. Un predicato con variabili può essere fatto una proposizione assegnando un valore alla variabile o quantificando la variabile.

Di seguito sono riportati alcuni esempi di predicati:

• Sia E (x, y) "x = y"
• Sia X (a, b, c) "a + b + c = 0"
• Sia M (x, y) "x è sposato con y"

Formula ben formata

Well Formed Formula (wff) è un predicato che contiene uno dei seguenti:

• Tutte le costanti proposizionali e le variabili proposizionali sono wffs

• Se x è una variabile e Y è un wff, $\forall x Y$ e $\exists x Y$ sono anche wff

• Il valore di verità e i valori falsi sono wffs

• Ogni formula atomica è un wff

• Tutti i connettivi che connettono wffs sono wffs

Quantificatori

La variabile dei predicati viene quantificata da quantificatori. Esistono due tipi di quantificatori nella logica dei predicati: quantificatore universale e quantificatore esistenziale.

Quantificatore universale

Quantificatore universale afferma che le dichiarazioni all'interno del suo ambito sono vere per ogni valore della variabile specifica. È indicato dal simbolo$\forall$.

$\forall x P(x)$ viene letto come per ogni valore di x, P (x) è vero.

Example - "L'uomo è mortale" può essere trasformato nella forma proposizionale $\forall x P(x)$ dove P (x) è il predicato che denota x è mortale e l'universo del discorso è tutto uomini.

Quantificatore esistenziale

Il quantificatore esistenziale afferma che le dichiarazioni all'interno del suo ambito sono vere per alcuni valori della variabile specifica. È indicato dal simbolo$\exists $.

$\exists x P(x)$ viene letto come per alcuni valori di x, P (x) è vero.

Example - "Alcune persone sono disoneste" può essere trasformato nella forma propositiva $\exists x P(x)$ dove P (x) è il predicato che denota x è disonesto e l'universo del discorso è alcune persone.

Quantificatori annidati

Se utilizziamo un quantificatore che appare nell'ambito di un altro quantificatore, viene chiamato quantificatore annidato.

Example

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

• $\forall\ a\: \forall\: b\: \forall\: c\: P (a, b, c)$ dove $P (a, b)$ denota $a + (b + c) = (a + b) + c$

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

Per dedurre nuove affermazioni dalle affermazioni la cui verità che già conosciamo, Rules of Inference sono usati.

A cosa servono le regole di inferenza?

La logica matematica viene spesso utilizzata per le dimostrazioni logiche. Le dimostrazioni sono argomenti validi che determinano i valori di verità delle affermazioni matematiche.

Un argomento è una sequenza di dichiarazioni. L'ultima affermazione è la conclusione e tutte le sue affermazioni precedenti sono chiamate premesse (o ipotesi). Il simbolo "$\therefore$", (Leggi quindi) è posto prima della conclusione. Un argomento valido è quello in cui la conclusione segue dai valori di verità delle premesse.

Le regole di inferenza forniscono i modelli o le linee guida per la costruzione di argomenti validi dalle dichiarazioni che già abbiamo.

Tabella delle regole di inferenza

Regola di inferenza	Nome	Regola di inferenza	Nome
$$\begin{matrix} P \\ \hline \therefore P \lor Q \end{matrix}$$	Aggiunta	$$\begin{matrix} P \lor Q \\ \lnot P \\ \hline \therefore Q \end{matrix}$$	Sillogismo disgiuntivo
$$\begin{matrix} P \\ Q \\ \hline \therefore P \land Q \end{matrix}$$	Congiunzione	$$\begin{matrix} P \rightarrow Q \\ Q \rightarrow R \\ \hline \therefore P \rightarrow R \end{matrix}$$	Sillogismo ipotetico
$$\begin{matrix} P \land Q\\ \hline \therefore P \end{matrix}$$	Semplificazione	$$\begin{matrix} ( P \rightarrow Q ) \land (R \rightarrow S) \\ P \lor R \\ \hline \therefore Q \lor S \end{matrix}$$	Dilemma costruttivo
$$\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}$$	Dilemma distruttivo
$$\begin{matrix} P \rightarrow Q \\ \lnot Q \\ \hline \therefore \lnot P \end{matrix}$$	Modus Tollens

Aggiunta

Se P è una premessa, possiamo utilizzare la regola dell'addizione per derivare $ P \lor Q $.

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

Esempio

Sia P la proposizione: "Studia molto duramente" è vera

Pertanto - "O studia molto duramente o è uno studente molto cattivo". Qui Q è la proposizione "è uno studente molto cattivo".

Congiunzione

Se P e Q sono due premesse, possiamo usare la regola di congiunzione per derivare $ P \land Q $.

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

Esempio

Let P - "Studia molto duramente"

Let Q - "È il miglior ragazzo della classe"

Pertanto - "Studia molto duramente ed è il miglior ragazzo della classe"

Semplificazione

Se $P \land Q$ è una premessa, possiamo usare la regola di semplificazione per derivare P.

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

Esempio

"Studia molto duramente ed è il miglior ragazzo della classe", $P \land Q$

Pertanto - "Studia molto duramente"

Modus Ponens

Se P e $P \rightarrow Q$ sono due premesse, possiamo usare Modus Ponens per ricavare Q.

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

Esempio

"Se hai una password, puoi accedere a Facebook", $P \rightarrow Q$

"Hai una password", P

Pertanto - "Puoi accedere a Facebook"

Modus Tollens

Se $P \rightarrow Q$ e $\lnot Q$ sono due premesse, possiamo utilizzare Modus Tollens per ricavare $\lnot P$.

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

Esempio

"Se hai una password, puoi accedere a Facebook", $P \rightarrow Q$

"Non puoi accedere a Facebook", $\lnot Q$

Pertanto - "Non hai una password"

Sillogismo disgiuntivo

Se $\lnot P$ e $P \lor Q$ sono due premesse, possiamo usare il Sillogismo Disgiuntivo per derivare Q.

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

Esempio

"Il gelato non è aromatizzato alla vaniglia", $\lnot P$

"Il gelato è aromatizzato alla vaniglia o al cioccolato", $P \lor Q$

Pertanto - "Il gelato è al gusto di cioccolato"

Sillogismo ipotetico

Se $P \rightarrow Q$ e $Q \rightarrow R$ sono due premesse, possiamo usare il Sillogismo ipotetico per derivare $P \rightarrow R$

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

Esempio

"Se piove, non andrò a scuola", $P \rightarrow Q$

"Se non vado a scuola, non avrò bisogno di fare i compiti", $Q \rightarrow R$

Pertanto - "Se piove, non avrò bisogno di fare i compiti"

Dilemma costruttivo

Se $( P \rightarrow Q ) \land (R \rightarrow S)$ e $P \lor R$ sono due premesse, possiamo usare dilemma costruttivo per derivare $Q \lor S$.

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

Esempio

"Se piove, me ne vado", $( P \rightarrow Q )$

"Se fuori fa caldo, vado a farmi una doccia", $(R \rightarrow S)$

"O pioverà o farà caldo fuori", $P \lor R$

Pertanto - "Prenderò un permesso o vado a fare una doccia"

Dilemma distruttivo

Se $(P \rightarrow Q) \land (R \rightarrow S)$ e $ \lnot Q \lor \lnot S $ sono due premesse, possiamo usare il dilemma distruttivo per derivare $\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}$$

Esempio

"Se piove, me ne vado", $(P \rightarrow Q )$

"Se fuori fa caldo, vado a farmi una doccia", $(R \rightarrow S)$

"O non prenderò un congedo o non andrò a farmi una doccia", $\lnot Q \lor \lnot S$

Pertanto - "O non piove o non fa caldo fuori"

La teoria dei gruppi è una branca della matematica e dell'algebra astratta che definisce una struttura algebrica denominata come group. Generalmente, un gruppo comprende un insieme di elementi e un'operazione su due elementi qualsiasi su quell'insieme per formare un terzo elemento anche in quell'insieme.

Nel 1854 Arthur Cayley, il matematico britannico, diede per la prima volta la definizione moderna di gruppo:

"Un insieme di simboli tutti diversi, e tale che il prodotto di due qualsiasi di essi (non importa in quale ordine), o il prodotto di ognuno di essi in sé, appartiene all'insieme, si dice che . Questi simboli non sono generalmente convertibili [commutativi], ma sono associativi ".

In questo capitolo, ne sapremo operators and postulates che costituiscono le basi della teoria degli insiemi, della teoria dei gruppi e dell'algebra booleana.

Qualsiasi insieme di elementi in un sistema matematico può essere definito con un insieme di operatori e un numero di postulati.

UN binary operatordefinita su un insieme di elementi è una regola che assegna a ciascuna coppia di elementi un elemento univoco di quella serie. Ad esempio, dato il set$ A = \lbrace 1, 2, 3, 4, 5 \rbrace $, possiamo dire $\otimes$ è un operatore binario per l'operazione $c = a \otimes b$, se specifica una regola per trovare c per la coppia di $(a,b)$, tale che $a,b,c \in A$.

Il postulatesdi un sistema matematico costituiscono i presupposti di base da cui è possibile dedurre le regole. I postulati sono -

Chiusura

Un insieme è chiuso rispetto a un operatore binario se per ogni coppia di elementi dell'insieme, l'operatore trova un elemento unico da quell'insieme.

Esempio

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

Questo set è chiuso con l'operatore binario in $(\ast)$, perché per l'operazione $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$, dove $x, y \in A$

Esempio

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

L'operatore plus $( + )$ è commutativo perché per due elementi qualsiasi, $x,y \in A$, la proprietà $x + y = y + x$ tiene.

L'operatore meno $( - )$ non è associativo da allora

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

Leggi distributive

Due operatori binari $\otimes$ e $\circledast$ su un insieme A, sono distributivi sull'operatore $\circledast$ quando vale la seguente proprietà:

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

Esempio

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

Gli operatori in $( * )$ e più $( + )$ sono distributivi sull'operatore + perché per tre elementi qualsiasi, $x,y,z \in A$, la proprietà $x * ( y + z ) = ( x * y ) + ( x * z )$ tiene.

Tuttavia, questi operatori non sono più distributivi $*$ da

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

Elemento identità

Un insieme A ha un elemento di identità rispetto a un'operazione binaria $\otimes$ su A, se esiste un elemento $e \in A$, in modo tale che la seguente proprietà detenga:

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

Esempio

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

L'elemento 1 è un elemento di identità rispetto al funzionamento $*$ poiché per qualsiasi elemento $x \in Z$,

$$1 * x = x * 1$$

D'altra parte, non vi è alcun elemento di identità per l'operazione meno $( - )$

Inverso

Se un insieme A ha un elemento di identità $e$ rispetto a un operatore binario $\otimes $, si dice che abbia un inverso ogni volta per ogni elemento $x \in A$, esiste un altro elemento $y \in A$, in modo tale che la seguente proprietà detenga:

$$x \otimes y = e$$

Esempio

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

Data l'operazione plus $( + )$ e $e = 0$, l'inverso di qualsiasi elemento x è $(-x)$ da $x + (x) = 0$

Legge di De Morgan

Le leggi di De Morgan danno una coppia di trasformazioni tra unione e intersezione di due (o più) insiemi in termini di complementi. Le leggi sono -

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

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

Esempio

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

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

Quindi, lo vediamo $(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$

Quindi, lo vediamo $(A \cap B)' = A' \cup B'$

Semigruppo

Un insieme finito o infinito $‘S’$ con un'operazione binaria $‘\omicron’$ (Composizione) si chiama semigruppo se mantiene due condizioni contemporaneamente:

• Closure - Per ogni coppia $(a, b) \in S, \:(a \omicron b)$ deve essere presente nel set $S$.

• Associative - Per ogni elemento $a, b, c \in S, (a \omicron b) \omicron c = a \omicron (b \omicron c)$ deve reggere.

Esempio

L'insieme di numeri interi positivi (escluso lo zero) con operazione di addizione è un semigruppo. Per esempio,$ S = \lbrace 1, 2, 3, \dots \rbrace $

Qui la proprietà di chiusura vale come per ogni coppia $(a, b) \in S, (a + b)$ è presente nell'insieme S. Ad esempio, $1 + 2 = 3 \in S]$

La proprietà associativa vale anche per ogni elemento $a, b, c \in S, (a + b) + c = a + (b + c)$. Per esempio,$(1 + 2) + 3 = 1 + (2 + 3) = 5$

Monoide

Un monoide è un semigruppo con un elemento di identità. L'elemento identità (indicato da$e$ o E) di un insieme S è un elemento tale che $(a \omicron e) = a$, per ogni elemento $a \in S$. Un elemento di identità è anche chiamato aunit element. Quindi, un monoide possiede tre proprietà contemporaneamente:Closure, Associative, Identity element.

Esempio

L'insieme di numeri interi positivi (escluso lo zero) con operazione di moltiplicazione è un monoide. $S = \lbrace 1, 2, 3, \dots \rbrace $

Qui la proprietà di chiusura vale come per ogni coppia $(a, b) \in S, (a \times b)$ è presente nell'insieme S. [Ad esempio, $1 \times 2 = 2 \in S$ e così via]

La proprietà associativa vale anche per ogni elemento $a, b, c \in S, (a \times b) \times c = a \times (b \times c)$ [Per esempio, $(1 \times 2) \times 3 = 1 \times (2 \times 3) = 6$ e così via]

La proprietà Identity vale anche per ogni elemento $a \in S, (a \times e) = a$ [Per esempio, $(2 \times 1) = 2, (3 \times 1) = 3$e così via]. Qui l'elemento identità è 1.

Gruppo

Un gruppo è un monoide con un elemento inverso. L'elemento inverso (indicato con I) di un insieme S è un elemento tale che$(a \omicron I) = (I \omicron a) = a$, per ogni elemento $a \in S$. Quindi, un gruppo possiede quattro proprietà simultaneamente: i) Chiusura, ii) Associativo, iii) Elemento di identità, iv) Elemento inverso. L'ordine di un gruppo G è il numero di elementi in G e l'ordine di un elemento in un gruppo è il numero intero meno positivo n tale che an è l'elemento identità di quel gruppo G.

Esempi

Il set di $N \times N$ matrici non singolari formano un gruppo sotto l'operazione di moltiplicazione di matrici.

Il prodotto di due $N \times N$ matrici non singolari è anche un file $N \times N$ matrice non singolare che detiene la proprietà di chiusura.

La stessa moltiplicazione di matrici è associativa. Quindi, la proprietà associativa vale.

Il set di $N \times N$ le matrici non singolari contengono la matrice identità che detiene la proprietà dell'elemento identità.

Poiché tutte le matrici non sono singolari, hanno tutte elementi inversi che sono anche matrici non singolari. Quindi, vale anche la proprietà inversa.

Gruppo Abeliano

Un gruppo abeliano G è un gruppo per il quale la coppia di elementi $(a,b) \in G$detiene sempre la legge commutativa. Quindi, un gruppo possiede cinque proprietà simultaneamente: i) Chiusura, ii) Associativo, iii) Elemento di identità, iv) Elemento inverso, v) Commutativo.

Esempio

L'insieme di interi positivi (compreso lo zero) con operazione di addizione è un gruppo abeliano. $G = \lbrace 0, 1, 2, 3, \dots \rbrace$

Qui la proprietà di chiusura vale come per ogni coppia $(a, b) \in S, (a + b)$ è presente nell'insieme S. [Ad esempio, $1 + 2 = 2 \in S$ e così via]

La proprietà associativa vale anche per ogni elemento $a, b, c \in S, (a + b) + c = a + (b + c)$ [Per esempio, $(1 +2) + 3 = 1 + (2 + 3) = 6$ e così via]

La proprietà Identity vale anche per ogni elemento $a \in S, (a \times e) = a$ [Per esempio, $(2 \times 1) = 2, (3 \times 1) = 3$e così via]. Qui, l'elemento Identity è 1.

La proprietà commutativa vale anche per ogni elemento $a \in S, (a \times b) = (b \times a)$ [Per esempio, $(2 \times 3) = (3 \times 2) = 3$ e così via]

Gruppo e sottogruppo ciclico

UN cyclic groupè un gruppo che può essere generato da un singolo elemento. Ogni elemento di un gruppo ciclico è una potenza di un elemento specifico che viene chiamato generatore. Un gruppo ciclico può essere generato da un generatore "g", in modo tale che ogni altro elemento del gruppo possa essere scritto come potenza del generatore "g".

Esempio

L'insieme dei numeri complessi $\lbrace 1,-1, i, -i \rbrace$ sotto l'operazione di moltiplicazione è un gruppo ciclico.

Ci sono due generatori: $i$ e $–i$ come $i^1 = i, i^2 = -1, i^3 = -i, i^4 = 1$ e anche $(–i)^1 = -i, (–i)^2 = -1, (–i)^3 = i, (–i)^4 = 1$che copre tutti gli elementi del gruppo. Quindi, è un gruppo ciclico.

Note - A cyclic groupè sempre un gruppo abeliano ma non tutti i gruppi abeliani sono un gruppo ciclico. I numeri razionali sotto addizione non sono ciclici ma abeliani.

UN subgroup H è un sottoinsieme di un gruppo G (indicato con $H ≤ G$) se soddisfa le quattro proprietà contemporaneamente - Closure, Associative, Identity element, e Inverse.

Un sottogruppo H di un gruppo G che non include l'intero gruppo G è chiamato un sottogruppo proprio (indicato da $H < G$). Un sottogruppo di un gruppo ciclico è ciclico e anche un sottogruppo abeliano è abeliano.

Esempio

Lascia un gruppo $G = \lbrace 1, i, -1, -i \rbrace$

Quindi alcuni sottogruppi sono $H_1 = \lbrace 1 \rbrace, H_2 = \lbrace 1,-1 \rbrace$,

Questo non è un sottogruppo - $H_3 = \lbrace 1, i \rbrace$ perché quello $(i)^{-1} = -i$ non è in $H_3$

Set parzialmente ordinato (POSET)

Un insieme parzialmente ordinato è costituito da un insieme con una relazione binaria riflessiva, antisimmetrica e transitiva. "Set parzialmente ordinato" è abbreviato in POSET.

Esempi

• L'insieme di numeri reali in operazione binaria minore o uguale a $(\le)$ è un poset.

  Lascia che il set $S = \lbrace 1, 2, 3 \rbrace$ e l'operazione è $\le$

  Le relazioni saranno $\lbrace(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3)\rbrace$

  Questa relazione R è riflessiva come $\lbrace (1, 1), (2, 2), (3, 3)\rbrace \in R$

  Questa relazione R è antisimmetrica, come

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

  Questa relazione R è anche transitiva come $\lbrace (1,2), (2,3), (1,3)\rbrace \in R$.

  Quindi, è un file poset.

• L'insieme dei vertici di un grafo aciclico diretto sotto l'operazione "raggiungibilità" è un poset.

Diagramma di Hasse

Il diagramma di Hasse di un poset è il grafo diretto i cui vertici sono l'elemento di quel poset e gli archi coprono le coppie (x, y) nel poset. Se nel poset$x < y$, quindi il punto x appare inferiore al punto y nel diagramma di Hasse. Se$x<y<z$ nel poset, la freccia non è mostrata tra x e z poiché è implicita.

Esempio

Il poset di sottoinsiemi di $\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$ è mostrato dal seguente diagramma di Hasse -

Set ordinato linearmente

Un insieme ordinato linearmente o un insieme ordinato totale è un insieme parziale in cui ogni coppia di elementi è confrontabile. Gli elementi$a, b \in S$ si dice che siano comparabili se entrambi $a \le b$ o $b \le a$tiene. La legge della tricotomia definisce questo insieme ordinato totale. Un insieme totalmente ordinato può essere definito come un reticolo distributivo avente la proprietà$\lbrace a \lor b, a \land b \rbrace = \lbrace a, b \rbrace$ per tutti i valori di aeb nell'insieme S.

Esempio

Il set di potenza di $\lbrace a, b \rbrace$ ordinato da \ subseteq è un insieme totalmente ordinato come tutti gli elementi dell'insieme di potenza $P = \lbrace \emptyset, \lbrace a \rbrace, \lbrace b \rbrace, \lbrace a, b\rbrace \rbrace$ sono comparabili.

Esempio di set di ordini non totale

Un set $S = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$ durante l'operazione x divide y non è un insieme ordinato totale.

Qui, per tutti $(x, y) \in S, x | y$devo tenere ma non è vero che 2 | 3, poiché 2 non divide 3 o 3 non divide 2. Quindi, non è un insieme ordinato totale.

Reticolo

Un reticolo è un poset $(L, \le)$ per cui ogni coppia $\lbrace a, b \rbrace \in L$ ha un limite superiore minimo (indicato da $a \lor b$) e un limite inferiore maggiore (indicato da $a \land b$). LUB$(\lbrace a,b \rbrace)$è chiamato l'unione di a e b. GLB$(\lbrace a,b \rbrace )$ è chiamato l'incontro di a e b.

Esempio

Questa figura sopra è un reticolo perché per ogni coppia $\lbrace a, b \rbrace \in L$, esistono un GLB e un LUB.

Questa figura sopra non è un reticolo perché $GLB (a, b)$ e $LUB (e, f)$ non esiste.

Alcuni altri reticoli sono discussi di seguito:

Lattice delimitato

Un reticolo L diventa un reticolo limitato se ha un elemento maggiore 1 e un elemento minimo 0.

Lattice integrato

Un reticolo L diventa un reticolo completato se è un reticolo limitato e se ogni elemento del reticolo ha un complemento. Un elemento x ha un complemento x 'se$\exists x(x \land x’=0 and x \lor x’ = 1)$

Reticolo distributivo

Se un reticolo soddisfa le seguenti due proprietà di distribuzione, viene chiamato reticolo distributivo.

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

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

Lattice modulare

Se un reticolo soddisfa la seguente proprietà, si chiama reticolo modulare.

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

Proprietà dei reticoli

Proprietà idempotenti

• $a \lor a = a$

• $a \land a = a$

Proprietà di assorbimento

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

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

Proprietà commutative

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

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

Proprietà associative

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

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

Doppio di un Lattice

Il duale di un reticolo si ottiene intercambiando il '$\lor$' e '$\land$'operazioni.

Esempio

Il doppio di $\lbrack a \lor (b \land c) \rbrack\ is\ \lbrack a \land (b \lor c) \rbrack$

Nella vita quotidiana, molte volte è necessario scoprire il numero di tutti i possibili risultati per una serie di eventi. Ad esempio, in quanti modi può essere scelta una giuria composta da 6 uomini e 4 donne tra 50 uomini e 38 donne? Quanti numeri PAN di 10 lettere differenti possono essere generati in modo tale che le prime cinque lettere siano alfabeti maiuscoli, le quattro successive siano cifre e l'ultima sia di nuovo maiuscola. Per risolvere questi problemi, viene utilizzata la teoria matematica del conteggio.Counting comprende principalmente la regola di conteggio fondamentale, la regola di permutazione e la regola di combinazione.

Le regole della somma e del prodotto

Il Rule of Sum e Rule of Product sono usati per scomporre problemi di conteggio difficili in problemi semplici.

• The Rule of Sum - Se una sequenza di attività $T_1, T_2, \dots, T_m$ può essere fatto in $w_1, w_2, \dots w_m$ modi rispettivamente (la condizione è che non sia possibile eseguire attività contemporaneamente), quindi il numero di modi per eseguire una di queste attività è $w_1 + w_2 + \dots +w_m$. Se consideriamo due compiti A e B che sono disgiunti (es$A \cap B = \emptyset$), quindi matematicamente $|A \cup B| = |A| + |B|$

• The Rule of Product - Se una sequenza di attività $T_1, T_2, \dots, T_m$ può essere fatto in $w_1, w_2, \dots w_m$ modi rispettivamente e ogni attività arriva dopo il verificarsi dell'attività precedente, quindi ci sono $w_1 \times w_2 \times \dots \times w_m$modi per eseguire le attività. Matematicamente, se un'attività B arriva dopo un'attività A, allora$|A \times B| = |A|\times|B|$

Esempio

Question- Un ragazzo vive a X e vuole andare a scuola a Z. Da casa sua X deve prima raggiungere Y e poi Y a Z. Può andare da X a Y con 3 linee di autobus o 2 linee di treno. Da lì, può scegliere 4 linee di autobus o 5 linee di treno per raggiungere Z. Quanti modi ci sono per andare da X a Z?

Solution - Da X a Y, può entrare $3 + 2 = 5$modi (regola della somma). Successivamente, può andare da Y a Z in$4 + 5 = 9$modi (regola della somma). Quindi da X a Z può entrare$5 \times 9 = 45$ modi (regola del prodotto).

Permutazioni

UN permutationè una disposizione di alcuni elementi in cui l'ordine conta. In altre parole, una permutazione è una combinazione ordinata di elementi.

Esempi

• Da un insieme S = {x, y, z} prendendo due alla volta, tutte le permutazioni sono -

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

• Dobbiamo formare una permutazione di numeri a tre cifre da un insieme di numeri $S = \lbrace 1, 2, 3 \rbrace$. Quando sistemiamo le cifre, verranno formati diversi numeri a tre cifre. La permutazione sarà = 123, 132, 213, 231, 312, 321

Numero di permutazioni

Il numero di permutazioni di 'n' cose diverse prese 'r' alla volta è indicato con $n_{P_{r}}$

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

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

Proof - Lascia che ci siano 'n' diversi elementi.

Ci sono molti modi per riempire il primo posto. Dopo aver riempito il primo posto (n-1) rimane il numero di elementi. Quindi, ci sono (n-1) modi per riempire il secondo posto. Dopo aver riempito il primo e il secondo posto, rimane (n-2) il numero di elementi. Quindi, ci sono (n-2) modi per riempire il terzo posto. Possiamo ora generalizzare il numero di modi per riempire la r-esima posizione come [n - (r – 1)] = n – r + 1

Quindi, il totale no. di modi per fare il pieno dal primo posto fino al r-esimo posto -

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

Quindi,

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

Alcune importanti formule di permutazione

• Se sono presenti n elementi di cui$a_1$ sono simili di qualche tipo, $a_2$ sono simili di un altro tipo; $a_3$ sono simili di terzo tipo e così via e $a_r$ sono di $r^{th}$ gentile, dove $(a_1 + a_2 + ... a_r) = n$.

  Quindi, il numero di permutazioni di questi n oggetti è = $n! / [(a_1!(a_2!) \dots (a_r!)]$.

• Numero di permutazioni di n elementi distinti che prendono n elementi alla volta = $n_{P_n} = n!$

• Il numero di permutazioni di n elementi dissimili che prendono r elementi alla volta, quando x cose particolari occupano sempre posti definiti = $n-x_{p_{r-x}}$

• Il numero di permutazioni di n elementi dissimili quando r le cose specificate si uniscono sempre è - $r! (n−r+1)!$

• Il numero di permutazioni di n elementi dissimili quando r specificate cose non si incontrano mai è - $n!–[r! (n−r+1)!]$

• Il numero di permutazioni circolari di n diversi elementi presi x elementi al tempo = $^np_{x}/x$

• Il numero di permutazioni circolari di n cose diverse = $^np_{n}/n$

Alcuni problemi

Problem 1 - Da un mazzo di 6 carte diverse, in quanti modi possiamo permutarlo?

Solution - Poiché stiamo prendendo 6 carte alla volta da un mazzo di 6 carte, la permutazione sarà $^6P_{6} = 6! = 720$

Problem 2 - In quanti modi possono essere disposte le lettere della parola "READER"?

Solution - La parola "READER" contiene 6 lettere (2 E, 1 A, 1D e 2R.).

La permutazione sarà $= 6! /\: [(2!) (1!)(1!)(2!)] = 180.$

Problem 3 - In che modo le lettere della parola "ARANCIONE" possono essere disposte in modo che le consonanti occupino solo le posizioni pari?

Solution- Ci sono 3 vocali e 3 consonanti nella parola "ARANCIONE". Numero di modi per disporre le consonanti tra di loro$= ^3P_{3} = 3! = 6$. I restanti 3 posti vacanti saranno riempiti da 3 vocali in$^3P_{3} = 3! = 6$modi. Quindi, il numero totale di permutazioni è$6 \times 6 = 36$

Combinazioni

UN combination è la selezione di alcuni elementi dati in cui l'ordine non ha importanza.

Il numero di tutte le combinazioni di n cose, prese r alla volta è -

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

Problem 1

Trova il numero di sottoinsiemi dell'insieme $\lbrace1, 2, 3, 4, 5, 6\rbrace$ avere 3 elementi.

Solution

La cardinalità dell'insieme è 6 e dobbiamo scegliere 3 elementi dall'insieme. Qui, l'ordine non ha importanza. Quindi, il numero di sottoinsiemi sarà$^6C_{3} = 20$.

Problem 2

Ci sono 6 uomini e 5 donne in una stanza. In quanti modi possiamo scegliere 3 uomini e 2 donne dalla stanza?

Solution

Il numero di modi per scegliere 3 uomini da 6 uomini è $^6C_{3}$ e il numero di modi per scegliere 2 donne da 5 donne è $^5C_{2}$

Quindi, il numero totale di modi è - $^6C_{3} \times ^5C_{2} = 20 \times 10 = 200$

Problem 3

In quanti modi puoi scegliere 3 gruppi distinti di 3 studenti da un totale di 9 studenti?

Solution

Numeriamo i gruppi come 1, 2 e 3

Per la scelta di 3 studenti per 1 ^° gruppo, il numero di modi -$^9C_{3}$

Il numero di modi per scegliere 3 studenti per il 2 ^° gruppo dopo aver scelto il 1 ° gruppo -$^6C_{3}$

Il numero di modi per scegliere 3 studenti per 3 ^° gruppo dopo aver scelto 1 ^° e 2 ^° gruppo -$^3C_{3}$

Quindi, il numero totale di modi $= ^9C_{3} \times ^6C_{3} \times ^3C_{3} = 84 \times 20 \times 1 = 1680$

Identità di Pascal

L'identità di Pascal, derivata per la prima volta da Blaise Pascal nel ^XVII secolo, afferma che il numero di modi per scegliere k elementi da n elementi è uguale alla somma del numero di modi per scegliere (k-1) elementi da (n-1) elementi e il numero di modi per scegliere gli elementi da n-1 elementi.

Matematicamente, per qualsiasi numero intero positivo k e 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 } }$

Principio della casella

Nel 1834, il matematico tedesco Peter Gustav Lejeune Dirichlet, affermò un principio che chiamò principio del cassetto. Ora, è noto come il principio della casella.

Pigeonhole Principleafferma che se ci sono meno caselle rispetto al numero totale di piccioni e ogni piccione viene messo in una tana, allora deve esserci almeno una casella con più di un piccione. Se n piccioni vengono messi in m caselle dove n> m, c'è un buco con più di un piccione.

Esempi

• Dieci uomini sono in una stanza e stanno prendendo parte alle strette di mano. Se ogni persona stringe la mano almeno una volta e nessun uomo stringe la mano allo stesso uomo più di una volta, due uomini hanno preso parte allo stesso numero di strette di mano.

• Ci devono essere almeno due persone in una classe di 30 i cui nomi iniziano con lo stesso alfabeto.

Il principio di inclusione-esclusione

Il Inclusion-exclusion principlecalcola il numero cardinale dell'unione di più insiemi non disgiunti. Per due insiemi A e B, il principio afferma:

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

Per tre insiemi A, B e C, il principio afferma:

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

La formula generalizzata -

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

Quanti numeri interi da 1 a 50 sono multipli di 2 o 3 ma non entrambi?

Solution

Da 1 a 100, ci sono $50/2 = 25$ numeri che sono multipli di 2.

Ci sono $50/3 = 16$ numeri che sono multipli di 3.

Ci sono $50/6 = 8$ numeri che sono multipli di 2 e 3.

Così, $|A|=25$, $|B|=16$ e $|A \cap B|= 8$.

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

Problem 2

In un gruppo di 50 studenti 24 gradiscono le bevande fredde e 36 gradiscono le bevande calde e ogni studente gradisce almeno una delle due bevande. A quanti piacciono sia il caffè che il tè?

Solution

Sia X l'insieme di studenti a cui piacciono le bevande fredde e Y l'insieme di persone a cui piacciono le bevande calde.

Così, $| X \cup Y | = 50$, $|X| = 24$, $|Y| = 36$

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

Quindi, ci sono 10 studenti a cui piacciono sia il tè che il caffè.

Strettamente correlato ai concetti di conteggio è la probabilità. Spesso proviamo a indovinare i risultati di giochi d'azzardo, come giochi di carte, slot machine e lotterie; cioè si cerca di trovare la probabilità o la probabilità che si ottenga un particolare risultato.

Probabilitypuò essere concettualizzato come trovare la possibilità che si verifichi un evento. Matematicamente, è lo studio dei processi casuali e dei loro risultati. Le leggi della probabilità hanno un'ampia applicabilità in una varietà di campi come la genetica, le previsioni meteorologiche, i sondaggi di opinione, i mercati azionari ecc.

Concetti basilari

La teoria della probabilità fu inventata nel XVII secolo da due matematici francesi, Blaise Pascal e Pierre de Fermat, che si occupavano di problemi matematici riguardanti il ​​caso.

Prima di passare ai dettagli della probabilità, vediamo il concetto di alcune definizioni.

Random Experiment- Un esperimento in cui tutti i possibili risultati sono noti e l'output esatto non può essere previsto in anticipo è chiamato esperimento casuale. Lanciare una moneta equa è un esempio di esperimento casuale.

Sample Space- Quando eseguiamo un esperimento, l'insieme S di tutti i possibili risultati è chiamato spazio campionario. Se lanciamo una moneta, lo spazio campione$S = \left \{ H, T \right \}$

Event- Qualsiasi sottoinsieme di uno spazio campione viene chiamato evento. Dopo aver lanciato una moneta, ottenere Testa in cima è un evento.

La parola "probabilità" indica la possibilità che si verifichi un particolare evento. Il meglio che possiamo dire è la probabilità che si verifichino, usando l'idea di probabilità.

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

Poiché il verificarsi di qualsiasi evento varia tra lo 0% e il 100%, la probabilità varia tra 0 e 1.

Passaggi per trovare la probabilità

Passaggio 1: calcola tutti i possibili risultati dell'esperimento.

Passaggio 2: calcolare il numero di risultati favorevoli dell'esperimento.

Passaggio 3: applicare la formula di probabilità corrispondente.

Lanciare una moneta

Se viene lanciata una moneta, ci sono due possibili risultati: teste $(H)$ o Tails $(T)$

Quindi, numero totale di risultati = 2

Quindi, la probabilità di ottenere una testa $(H)$ in cima è 1/2 e la probabilità di ottenere una croce $(T)$ in alto è 1/2

Lanciare un dado

Quando un dado viene lanciato, sei possibili risultati possono essere in cima: $1, 2, 3, 4, 5, 6$.

La probabilità di uno qualsiasi dei numeri è 1/6

La probabilità di ottenere numeri pari è 3/6 = 1/2

La probabilità di ottenere numeri dispari è 3/6 = 1/2

Prendere carte da un mazzo

Da un mazzo di 52 carte, se viene scelta una carta, trova la probabilità che venga pescato un asso e anche la probabilità che venga pescato un diamante.

Numero totale di risultati possibili - 52

Risultati dell'essere un asso - 4

Probabilità di essere un asso = 4/52 = 1/13

Probabilità di essere un diamante = 13/52 = 1/4

Assiomi di probabilità

• La probabilità di un evento varia sempre da 0 a 1. $[0 \leq P(x) \leq 1]$

• Per un evento impossibile la probabilità è 0 e per un certo evento la probabilità è 1.

• Se il verificarsi di un evento non è influenzato da un altro evento, vengono chiamati mutuamente esclusivi o disgiunti.

  Se $A_1, A_2....A_n$ sono eventi mutuamente esclusivi / disgiunti, quindi $P(A_i \cap A_j) = \emptyset $ per $i \ne j$ e $P(A_1 \cup A_2 \cup.... A_n) = P(A_1) + P(A_2)+..... P(A_n)$

Proprietà della probabilità

• Se ci sono due eventi $x$ e $\overline{x}$che sono complementari, allora la probabilità dell'evento complementare è -

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

• Per due eventi non disgiunti A e B, la probabilità dell'unione di due eventi -

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

• Se un evento A è un sottoinsieme di un altro evento B (es $A \subset B$), allora la probabilità di A è minore o uguale alla probabilità di B. Quindi, $A \subset B$ implica $P(A) \leq p(B)$

Probabilità condizionale

La probabilità condizionata di un evento B è la probabilità che l'evento si verifichi dato che un evento A si è già verificato. Questo è scritto come$P(B|A)$.

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

Se l'evento A e B si escludono a vicenda, la probabilità condizionale dell'evento B dopo l'evento A sarà la probabilità dell'evento B che è $P(B)$.

Problem 1

In un paese il 50% di tutti gli adolescenti possiede una bicicletta e il 30% di tutti gli adolescenti possiede una bicicletta e una bicicletta. Qual è la probabilità che un adolescente possieda una bicicletta dato che l'adolescente possiede una bicicletta?

Solution

Supponiamo che A sia l'evento di adolescenti che possiedono solo una bicicletta e B sia l'evento di adolescenti che possiedono solo una bicicletta.

Così, $P(A) = 50/100 = 0.5$ e $P(A \cap B) = 30/100 = 0.3$ dal problema dato.

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

Quindi, la probabilità che un adolescente possieda una bicicletta dato che l'adolescente possiede una bicicletta è del 60%.

Problem 2

In una classe, il 50% di tutti gli studenti gioca a cricket e il 25% di tutti gli studenti gioca a cricket e pallavolo. Qual è la probabilità che uno studente giochi a pallavolo dato che lo studente gioca a cricket?

Solution

Supponiamo che A sia l'evento in cui gli studenti giocano solo a cricket e B sia l'evento in cui gli studenti giocano solo a pallavolo.

Così, $P(A) = 50/100 =0.5$ e $P(A \cap B) = 25/ 100 =0.25$ dal problema dato.

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

Quindi, la probabilità che uno studente giochi a pallavolo dato che lo studente gioca a cricket è del 50%.

Problem 3

Sei buoni laptop e tre laptop difettosi sono confusi. Per trovare i laptop difettosi, tutti vengono testati uno per uno a caso. Qual è la probabilità di trovare entrambi i laptop difettosi nelle prime due scelte?

Solution

Sia A l'evento in cui troviamo un laptop difettoso nel primo test e B l'evento in cui troviamo un laptop difettoso nel secondo test.

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

Teorema di Bayes

Theorem - Se A e B sono due eventi che si escludono a vicenda, dove $P(A)$ è la probabilità di A e $P(B)$ è la probabilità di B, $P(A | B)$ è la probabilità di A dato che B è vero. $P(B | A)$ è la probabilità di B dato che A è vero, quindi il teorema di Bayes afferma:

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

Applicazione del teorema di Bayes

• In situazioni in cui tutti gli eventi dello spazio campione sono eventi che si escludono a vicenda.

• In situazioni in cui entrambi $P( A_i \cap B )$ per ciascuno $A_i$ o $P( A_i )$ e $P(B|A_i)$ per ciascuno $A_i$ è conosciuto.

Problem

Considera tre portapenne. Il primo portapenne contiene 2 penne rosse e 3 penne blu; il secondo ha 3 penne rosse e 2 penne blu; e il terzo ha 4 penne rosse e 1 penna blu. C'è la stessa probabilità che ogni portapenna venga selezionato. Se una penna viene estratta a caso, qual è la probabilità che sia una penna rossa?

Solution

Permettere $A_i$l'evento che mi ^esimo è selezionato pen-stand.

Qui, i = 1,2,3.

Poiché la probabilità di scegliere un portapenne è uguale, $P(A_i) = 1/3$

Sia B l'evento in cui viene disegnata una penna rossa.

La probabilità che una penna rossa venga scelta tra le cinque penne del primo portapenne,

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

La probabilità che una penna rossa venga scelta tra le cinque penne del secondo portapenne,

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

La probabilità che una penna rossa venga scelta tra le cinque penne del terzo portapenne,

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

Secondo il teorema di 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, è una tecnica per provare risultati o stabilire affermazioni per numeri naturali. Questa parte illustra il metodo attraverso una varietà di esempi.

Definizione

Mathematical Induction è una tecnica matematica che viene utilizzata per dimostrare che un'affermazione, una formula o un teorema è vero per ogni numero naturale.

La tecnica prevede due passaggi per dimostrare una dichiarazione, come indicato di seguito:

Step 1(Base step) - Dimostra che un'affermazione è vera per il valore iniziale.

Step 2(Inductive step)- Dimostra che se l'affermazione è vera per l' ^ennesima iterazione (o numero n ), allora è vero anche per (n + 1) ^esima iterazione (o numero n + 1 ).

Come farlo

Step 1- Considera un valore iniziale per il quale l'affermazione è vera. È da dimostrare che l'affermazione è vera per n = valore iniziale.

Step 2- Supponiamo che l'affermazione sia vera per qualsiasi valore di n = k . Quindi prova che l'affermazione è vera per n = k + 1 . In realtà spezziamo n = k + 1 in due parti, una parte è n = k (che è già stato dimostrato) e proviamo a dimostrare l'altra parte.

Problema 1

$3^n-1$ è un multiplo di 2 per n = 1, 2, ...

Solution

Step 1 - Per $n = 1, 3^1-1 = 3-1 = 2$ che è un multiplo di 2

Step 2 - Supponiamo $3^n-1$ è vero per $n=k$, Quindi, $3^k -1$ è vero (è un presupposto)

Dobbiamo dimostrarlo $3^{k+1}-1$ è anche un multiplo di 2

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

La prima parte $(2 \times 3k)$ è certo un multiplo di 2 e la seconda parte $(3k -1)$ è anche vero come la nostra ipotesi precedente.

Quindi, $3^{k+1} – 1$ è un multiplo di 2.

Quindi, è dimostrato che $3^n – 1$ è un multiplo di 2.

Problema 2

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

Solution

Step 1 - Per $n=1, 1 = 1^2$, Quindi, il passaggio 1 è soddisfatto.

Step 2 - Supponiamo che l'affermazione sia vera per $n=k$.

Quindi, $1 + 3 + 5 + \dots + (2k-1) = k^2$ è vero (è un presupposto)

Dobbiamo dimostrarlo $1 + 3 + 5 + ... + (2(k+1)-1) = (k+1)^2$ vale anche

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

Così, $1 + 3 + 5 + \dots + (2(k+1) - 1) = (k+1)^2$ tieni premuto che soddisfa il passaggio 2.

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

Problema 3

Prova che $(ab)^n = a^nb^n$ è vero per ogni numero naturale $n$

Solution

Step 1 - Per $n=1, (ab)^1 = a^1b^1 = ab$, Quindi, il passaggio 1 è soddisfatto.

Step 2 - Supponiamo che l'affermazione sia vera per $n=k$, Quindi, $(ab)^k = a^kb^k$ è vero (è un presupposto).

Dobbiamo dimostrarlo $(ab)^{k+1} = a^{k+1}b^{k+1}$ anche tenere

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

O, $(ab)^k (ab) = (a^k b^k ) (ab)$ [Moltiplicando entrambi i lati per "ab"]

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

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

Quindi, il passaggio 2 è dimostrato.

Così, $(ab)^n = a^nb^n$ è vero per ogni numero naturale n.

Forte induzione

L'induzione forte è un'altra forma di induzione matematica. Attraverso questa tecnica di induzione, possiamo dimostrare che una funzione proposizionale,$P(n)$ è vero per tutti i numeri interi positivi, $n$, utilizzando i seguenti passaggi:

• Step 1(Base step) - Dimostra che la proposizione iniziale $P(1)$ vero.

• Step 2(Inductive step) - Dimostra che l'affermazione condizionale $[P(1) \land P(2) \land P(3) \land \dots \land P(k)] → P(k + 1)$ è vero per i numeri interi positivi $k$.

In questo capitolo discuteremo di come le tecniche ricorsive possono derivare sequenze ed essere utilizzate per risolvere problemi di conteggio. Viene chiamata la procedura per trovare i termini di una sequenza in modo ricorsivorecurrence relation. Studiamo la teoria delle relazioni di ricorrenza lineare e le loro soluzioni. Infine, introduciamo le funzioni di generazione per risolvere le relazioni di ricorrenza.

Definizione

Una relazione di ricorrenza è un'equazione che definisce ricorsivamente una sequenza in cui il termine successivo è una funzione dei termini precedenti (Espressione $F_n$ come una combinazione di $F_i$ con $i < n$).

Example - Serie Fibonacci - $F_n = F_{n-1} + F_{n-2}$, Torre di Hanoi - $F_n = 2F_{n-1} + 1$

Relazioni di ricorrenza lineare

Un'equazione di ricorrenza lineare di grado ko ordine k è un'equazione di ricorrenza che è nel formato $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$ è una costante e $A_k \neq 0$) su una sequenza di numeri come polinomio di primo grado.

Questi sono alcuni esempi di equazioni di ricorrenza lineare:

Relazioni ricorrenti	Valori iniziali	Soluzioni
F n = F n-1 + F n-2	a 1 = a 2 = 1	Numero di Fibonacci
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	Sequenza padovana
F n = 2F n-1 + F n-2	a 1 = 0, a 2 = 1	Numero di Pell

Come risolvere la relazione di ricorrenza lineare

Supponiamo che una relazione di ricorrenza lineare ordinata sia - $F_n = AF_{n-1} +BF_{n-2}$ dove A e B sono numeri reali.

L'equazione caratteristica per la relazione di ricorrenza di cui sopra è:

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

Possono verificarsi tre casi mentre si trovano le radici:

Case 1 - Se questa equazione calcola come $(x- x_1)(x- x_1) = 0$ e produce due distinte radici reali $x_1$ e $x_2$, poi $F_n = ax_1^n+ bx_2^n$è la soluzione. [Qui, aeb sono costanti]

Case 2 - Se questa equazione calcola come $(x- x_1)^2 = 0$ e produce un'unica radice reale $x_1$, poi $F_n = a x_1^n+ bn x_1^n$ è la soluzione.

Case 3 - Se l'equazione produce due distinte radici complesse, $x_1$ e $x_2$ in forma polare $x_1 = r \angle \theta$ e $x_2 = r \angle(- \theta)$, poi $F_n = r^n (a cos(n\theta)+ b sin(n\theta))$ è la soluzione.

Problem 1

Risolvi la relazione di ricorrenza $F_n = 5F_{n-1} - 6F_{n-2}$ dove $F_0 = 1$ e $F_1 = 4$

Solution

L'equazione caratteristica della relazione di ricorrenza è:

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

Così, $(x - 3) (x - 2) = 0$

Quindi, le radici sono -

$x_1 = 3$ e $x_2 = 2$

Le radici sono reali e distinte. Quindi, questo è nella forma del caso 1

Quindi, la soluzione è:

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

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

Perciò,

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

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

Risolvendo queste due equazioni, otteniamo $ a = 2$ e $b = -1$

Quindi, la soluzione finale è:

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

Problem 2

Risolvi la relazione di ricorrenza - $F_n = 10F_{n-1} - 25F_{n-2}$ dove $F_0 = 3$ e $F_1 = 17$

Solution

L'equazione caratteristica della relazione di ricorrenza è:

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

Così $(x - 5)^2 = 0$

Quindi, c'è un'unica vera radice $x_1 = 5$

Poiché esiste un'unica radice con valore reale, è nella forma del caso 2

Quindi, la soluzione è:

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

Risolvendo queste due equazioni, otteniamo $a = 3$ e $b = 2/5$

Quindi, la soluzione finale è: $F_n = 3.5^n +( 2/5) .n.2^n $

Problem 3

Risolvi la relazione di ricorrenza $F_n = 2F_{n-1} - 2F_{n-2}$ dove $F_0 = 1$ e $F_1 = 3$

Solution

L'equazione caratteristica della relazione di ricorrenza è:

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

Quindi, le radici sono -

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

In forma polare,

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

Le radici sono immaginarie. Quindi, questo è nella forma del caso 3.

Quindi, la soluzione è:

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

Risolvendo queste due equazioni otteniamo $a = 1$ e $b = 2$

Quindi, la soluzione finale è:

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

Relazione di ricorrenza non omogenea e soluzioni particolari

Una relazione di ricorrenza è chiamata non omogenea se è nella forma

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

La sua relazione di ricorrenza omogenea associata è $F_n = AF_{n–1} + BF_{n-2}$

La soluzione $(a_n)$ di una relazione di ripetizione non omogenea ha due parti.

La prima parte è la soluzione $(a_h)$ della relazione di ricorrenza omogenea associata e la seconda parte è la soluzione particolare $(a_t)$.

$$a_n=a_h+a_t$$

La soluzione alla prima parte viene eseguita utilizzando le procedure discusse nella sezione precedente.

Per trovare la soluzione particolare, troviamo una soluzione di prova appropriata.

Permettere $f(n) = cx^n$; permettere$x^2 = Ax + B$ essere l'equazione caratteristica della relazione di ricorrenza omogenea associata e let $x_1$ e $x_2$ essere le sue radici.

• Se $x \ne x_1$ e $x \ne x_2$, poi $a_t = Ax^n$

• Se $x = x_1$, $x \ne x_2$, poi $a_t = Anx^n$

• Se $x = x_1 = x_2$, poi $a_t = An^2x^n$

Esempio

Sia una relazione di ricorrenza non omogenea $F_n = AF_{n–1} + BF_{n-2} + f(n)$ con radici caratteristiche $x_1 = 2$ e $x_2 = 5$. Soluzioni di prova per diversi valori possibili di$f(n)$ sono i seguenti -