Relazione di equivalenza e insieme dei quozienti. Relazioni di equivalenza. Insiemi di fattori Relazioni di equivalenza. Insiemi di fattori

(cioè che ha le seguenti proprietà: ogni elemento dell'insieme è equivalente a se stesso; se X equivalente sì, Quello sì equivalente X; Se X equivalente sì, UN sì equivalente z, Quello X equivalente z ).

Quindi viene chiamato l'insieme di tutte le classi di equivalenza insieme di fattori ed è designato . Il partizionamento di un insieme in classi di elementi equivalenti è detto its fattorizzazione.

Visualizza da X nell'insieme delle classi di equivalenza viene chiamato mappatura dei fattori.

Esempi

È ragionevole utilizzare la fattorizzazione insiemistica per ottenere spazi normati da quelli semi-normati, spazi con prodotto interno da spazi con prodotto quasi interno, ecc. Per fare ciò, introduciamo, rispettivamente, la norma di una classe, uguale alla norma di un elemento arbitrario e il prodotto interno delle classi come prodotto interno di elementi arbitrari delle classi. A sua volta, la relazione di equivalenza viene introdotta come segue (ad esempio, per formare uno spazio quoziente normalizzato): viene introdotto un sottoinsieme dello spazio seminorma originale, costituito da elementi con seminorma zero (a proposito, è lineare, cioè è un sottospazio) e si ritiene che due elementi siano equivalenti se la loro differenza appartiene proprio a questo sottospazio.

Se, per fattorizzare uno spazio lineare, si introduce un certo sottospazio e si assume che se la differenza di due elementi dello spazio originario appartiene a questo sottospazio, allora questi elementi sono equivalenti, allora l'insieme dei fattori è uno spazio lineare e si chiama uno spazio fattoriale.

Esempi

Guarda anche

Fondazione Wikimedia. 2010.

Scopri cos'è "Factorset" in altri dizionari:

Il principio logico alla base delle definizioni per astrazione (vedi Definizione per astrazione): qualsiasi relazione del tipo di uguaglianza, definita su un insieme iniziale di elementi, divide (divide, classifica) l'originale... ...

Una forma di pensiero che riflette le proprietà essenziali, le connessioni e le relazioni di oggetti e fenomeni nella loro contraddizione e sviluppo; un pensiero o un sistema di pensieri che generalizza, distingue gli oggetti di una certa classe secondo certi criteri generali e nell'aggregato... ... Grande Enciclopedia Sovietica

Coomologia del gruppo di Galois. Se M è un gruppo abeliano e un gruppo di Galois di un'estensione che agisce su M, allora i gruppi di coomologia di Galois sono gruppi di coomologia definiti da un complesso costituito da tutte le mappe e d è un operatore di coconfine (vedi Coomologia dei gruppi).... . .. Enciclopedia matematica

La costruzione del paradiso apparve per la prima volta nella teoria degli insiemi e poi divenne ampiamente utilizzata in algebra, topologia e altre aree della matematica. Un caso speciale importante di un I.p. è un I.p. di una famiglia diretta di strutture matematiche dello stesso tipo. Lascia stare… Enciclopedia matematica

Punti pur essendo relativi al gruppo G agente sull'insieme X (a sinistra), l'insieme Set è un sottogruppo di G e viene chiamato. stabilizzatore, o sottogruppo stazionario di un punto rispetto a G. La mappatura induce una biiezione tra G/Gx e l'orbita G(x). DI.… … Enciclopedia matematica

Questo articolo ha un'introduzione troppo breve. Si prega di aggiungere una sezione introduttiva che introduca brevemente l'argomento dell'articolo e ne riassuma i contenuti... Wikipedia

Questo articolo riguarda il sistema algebrico. Per la branca della logica matematica che studia le affermazioni e le operazioni su di esse, vedere Algebra della logica. L'algebra booleana è un insieme non vuoto A con due operazioni binarie (analoghe a una congiunzione), ... ... Wikipedia

Sia data una relazione di equivalenza su un insieme. Quindi l'insieme di tutte le classi di equivalenza è chiamato insieme dei fattori e viene indicato. Il partizionamento di un insieme in classi di elementi equivalenti è detto fattorizzazione. Mappatura da a... ... Wikipedia

In geometria, per segmento orientato si intende una coppia ordinata di punti, il primo dei quali, il punto A, è chiamato il suo inizio, e il secondo, B, la sua fine. Indice 1 Definizione ... Wikipedia

In vari rami della matematica, il nucleo di una mappatura è un certo taglio dell'insieme, che in un certo senso caratterizza la differenza tra f e una mappatura iniettiva. La definizione specifica può variare, ma per la mappatura iniettiva f... ... Wikipedia

Insiemistica. Concetti basilari

La teoria degli insiemi è la definizione fondamentale della matematica moderna. È stato creato da Georg Cantor negli anni '60 dell'Ottocento. Ha scritto: “Molteplice è molti, concepito come un tutto unico”. Il concetto di insieme è uno dei concetti basilari e indefiniti della matematica. Non può essere ridotto ad altri concetti più semplici. Pertanto non è possibile definirlo, ma solo spiegarlo. Pertanto, un insieme è un'unificazione in un tutto di oggetti chiaramente distinguibili dalla nostra intuizione o dal nostro pensiero; una raccolta di determinati oggetti definiti da una caratteristica comune.

Per esempio,

1. Molti residenti di Voronezh

2. Insieme di punti del piano

3. Insieme di numeri naturali ℕecc.

Gli insiemi sono solitamente indicati in lettere latine maiuscole( A, B, C eccetera.). Gli oggetti che compongono un dato insieme sono detti suoi elementi. Gli elementi di un insieme sono indicati con lettere latine minuscole( a, b, c eccetera.). Se X– imposta, quindi registra x∈X significa che Xè un elemento dell'insieme X o cosa X appartiene al set X e l'immissione x∉X quell'elemento X non appartiene al set X. Ad esempio, sia ℕ l'insieme dei numeri naturali. Poi 5 ℕ , UN 0,5∉ℕ .

Se l'insieme Yè costituito da elementi dell'insieme X, poi lo dicono Yè un sottoinsieme dell'insieme X e denotare Sì⊂Х(O Y⊆Х). Ad esempio, un insieme di numeri interi ℤ è un sottoinsieme dei numeri razionali ℚ .

Se per due set X E Y due inclusioni si verificano contemporaneamente XY E YX, cioè. Xè un sottoinsieme dell'insieme Y E Yè un sottoinsieme dell'insieme X, quindi i set X E Y sono costituiti dagli stessi elementi. Tali insiemi X E Y si dicono uguali e scrivono: X=Y.

Viene spesso utilizzato il termine insieme vuoto: Ø - un insieme che non contiene un singolo elemento. È un sottoinsieme di qualsiasi insieme.

I seguenti metodi possono essere utilizzati per descrivere gli insiemi.

Metodi per specificare gli insiemi

1. Enumerazione degli oggetti. Utilizzato solo per insiemi finiti.

Per esempio, X=(x1, x2, x3…xn). Ingresso Y ={1, 4, 7, 5} significa che la serie è composta da quattro numeri 1, 4, 7, 5 .

2. Indicazione della proprietà caratteristica degli elementi dell'insieme.

Per fare ciò, viene impostata una determinata proprietà R, che consente di determinare se un elemento appartiene a un insieme. Questo metodo è più universale.

X=(x: P(x))

(un mucchio di Xè costituito da tali elementi X, per il quale detiene la proprietà P(x)).

Un insieme vuoto può essere specificato specificandone le proprietà: Ø=(x: x≠x)

Puoi costruire nuovi insiemi utilizzando quelli già definiti utilizzando le operazioni sugli insiemi.

Imposta operazioni

1. Un'unione (somma) è un insieme costituito da tutti quegli elementi, ciascuno dei quali appartiene ad almeno uno degli insiemi UN O IN.

A∪B=(x: x A oppure x B).

2. Un'intersezione (prodotto) è un insieme costituito da tutti gli elementi, ciascuno dei quali appartiene contemporaneamente all'insieme UN, e molti IN.

A∩B=(x: x A e x B).

3. Impostare la differenza UN E INè un insieme costituito da tutti quegli elementi che appartengono all'insieme UN e non appartengono alla moltitudine IN.

A\B=(x: x A e x B)

4. Se UN– un sottoinsieme di un insieme IN. Questo è molto B\A chiamato complemento di un insieme UN a molti IN e denotare UN'.

5. La differenza simmetrica di due insiemi è l’insieme A∆B=(A\B) (B\A)

N- l'insieme di tutti i numeri naturali;
Z- l'insieme di tutti i numeri interi;
Q- l'insieme di tutti i numeri razionali;
R- l'insieme di tutti i numeri reali;
C- l'insieme di tutti i numeri complessi;
Z0- l'insieme di tutti i numeri interi non negativi.

Proprietà delle operazioni sugli insiemi:

1.A B=B A (commutatività dell'unione)

2.A B=B A (commutatività dell'intersezione)

3. A(B C)=(A IN) C (associatività sindacale)

4.A (IN C)=(A IN) C (associatività dell'intersezione)

5.A (IN C)=(A IN) (UN C) (1a legge della distributività)

6.A (IN C)=(A IN) (UN C) (2a legge della distributività)

7.A Ø=A

8.A U=U

9.A Ø= Ø

10.A U=A

11. (A B)'=A' B' (legge di de Morgan)

12. (A B)'=A' B' (legge di de Morgan)

13.A (UN B)=A (legge di assorbimento)

14.A (UN B)=A (legge di assorbimento)

Dimostriamo la proprietà n. 11. (UN B)'=A' IN'

Per definizione di insiemi uguali, dobbiamo dimostrare due inclusioni 1) (UN B)’ ⊂A’ IN';

2) UN' B’⊂(A IN)'.

Per dimostrare la prima inclusione, consideriamo un elemento arbitrario x∈(A B)’=X\(A∪B). Significa che x∈X, x∉ A∪B. Ne consegue che x∉A E x∉B, Ecco perché x∈X\A E x∈X\B, che significa x∈A’∩B’. Così, (UN B)’⊂A’ IN'

Indietro se x∈A’ IN', Quello X appartiene contemporaneamente a insiemi A', B', che significa x∉A E x∉B. Ne consegue che x∉A IN, Ecco perché x∈(A IN)'. Quindi, UN' B’⊂(A IN)'.

COSÌ, (UN B)'=A' IN'

Un insieme formato da due elementi, in cui è definito l'ordine degli elementi, si chiama coppia ordinata. Per scriverlo, usa le parentesi. (x1, x2)– un insieme di due elementi in cui x 1 è considerato il primo elemento e x 2 è il secondo. Coppie (x1, x2) E (x2, x1), Dove x1 ≠ x2, sono considerati diversi.

Un insieme composto da n elementi, in cui è definito l'ordine degli elementi, si dice insieme ordinato di n elementi.

Un prodotto cartesiano è un insieme arbitrario X1, X2,…,X n insiemi ordinati di n elementi, dove x1 X1, x2 X2,...,x n Xn

X1 Xn

Se i set X1, X2,…,X n incontro (X1 = X2 =…=Xn), allora viene indicato il loro prodotto Xn.

Per esempio, ℝ 2 – un insieme di coppie ordinate di numeri reali.

Relazioni di equivalenza. Insiemi di fattori

A partire da un dato insieme è possibile costruire nuovi insiemi considerando l'insieme di alcuni sottoinsiemi. In questo caso, di solito non si parla di un insieme di sottoinsiemi, ma di una famiglia o classe di sottoinsiemi.

In una serie di domande, viene considerata la classe di tali sottoinsiemi di un dato insieme UN, che non si intersecano e la cui unione coincide con UN. Se questo è impostato UN può essere rappresentato come unione dei suoi sottoinsiemi disgiunti a due a due, allora è consuetudine dire così UN divisi in classi. La divisione in classi viene effettuata sulla base di alcune caratteristiche.

Permettere X non è un insieme vuoto, quindi qualsiasi sottoinsieme R dal lavoro X X si chiama relazione binaria sull'insieme X. Se una coppia (x,y) incluso in R, dicono che l'elemento x è nella relazione R Con A.

Ad esempio, le relazioni x=y, x≥y sono relazioni binarie sull'insieme ℝ.

Relazione binaria R su un set X si dice relazione di equivalenza se:

1. (x,x) R; X X (proprietà riflessività)

2. (x,y) R => (y, x) R (proprietà di simmetria)

3. (x,y) R, (y,z) R, quindi (x,z) R (proprietà di transitività)

Se una coppia (x,y) entrati in relazioni di equivalenza, allora xey sono detti equivalenti (x~y).

1.Lascia ℤ – un insieme di numeri interi, m≥1– un numero intero. Definiamo la relazione di equivalenza R SU ℤ affinché n~k, Se n-k diviso per M. Controlliamo se le proprietà sono soddisfatte su questa relazione.

1. Riflessività.

Per chiunque n∈ℤ ℤ tale che (p,p)∈R

р-р=0. Perché 0∈ ℤ , Quello (p,p)∈ℤ.

2. Simmetria.

Da (n,k) ∈R ne consegue che esiste una cosa del genere р∈ℤ, Che cosa nk=mp;

k-n =m(-p), -p∈ ℤ, quindi (k,n) ∈R.

3. Transitività.

Da cosa (n,k) ∈R, (k,q) ∈R ne consegue che esistono tali pag 1 E р2 ∈ ℤ, Che cosa nk=mp 1 E k-q=mp 2. Aggiungendo queste espressioni, otteniamo ciò n-q=m(p 1 + p 2), p 1 + p 2 =p, p∈ ℤ. Ecco perché (n,q) ∈ ℤ.

2. Considera il set X tutti i segmenti diretti dello spazio o del piano . =(A, B). Introduciamo la relazione di equivalenza R SU X.

Sia G=(p 0 =e, p 1, …, p r) un certo gruppo di permutazioni definite sull'insieme X = (1, 2, …, n) con l'unità e=p 0 identica permutazione. Definiamo la relazione x~y ponendo x~y equivalente al fatto che esiste p appartenente a G(p(x)=y). La relazione introdotta è una relazione di equivalenza, cioè soddisfa tre assiomi:

1) x~x;
2) x~y→y~x;
3) x~y&y~z→x~z;

Sia A un insieme arbitrario.
Definizione: Una relazione binaria δ=A*A è una relazione di equivalenza (indicata con a ~ b) se soddisfa i seguenti assiomi:
∀ a, b, c ∈ A
1) a ~ a – riflessività;
2) a ~ b ⇒ b ~ a – commutatività;
3) a ~ b & b ~ c → a ~ c - transitività

indicato con a ~ b, σ(a,b), (a,b) ∈ σ, a σ b

Definizione: Una partizione di un insieme A è una famiglia di sottoinsiemi di A disgiunti a due a due, che nell'unione (in totale) danno tutto A.
À= ∪А i, À i ∩А j = ∅, ∀i ≠ j.

I sottoinsiemi A i sono detti cosetti della partizione.

Teorema: ogni relazione di equivalenza definita su A corrisponde a qualche partizione dell'insieme A. Ogni partizione dell'insieme A corrisponde a qualche relazione di equivalenza sull'insieme A.

In breve: esiste una corrispondenza biunivoca tra le classi di tutte le relazioni di equivalenza definite sull'insieme A e la classe di tutte le partizioni dell'insieme A.

Prova: sia σ una relazione di equivalenza sull'insieme A. Sia a ∈ A.

Costruiamo un insieme: K a =(x ∈ A,: x~a) – tutti gli elementi equivalenti ad a. L'insieme (notazione) è chiamato classe di equivalenza rispetto all'equivalenza σ. Nota che se b appartiene a K a , allora b~a. Mostriamo che a~b⇔K a =K b . Infatti, sia a~b. Prendi un elemento arbitrario c appartenente a K a . Allora c~a, a~b, c~b, c appartiene a K b e quindi K b appartiene a K a . Il fatto che K a appartenga a K b si dimostra in modo simile. Pertanto, K b = K a.
Sia ora K b = K a . Allora a appartiene a K a = K b , a appartiene a K b , a~b. Questo è ciò che doveva essere mostrato.

Se 2 classi K a e K b hanno un elemento comune c, allora K a = K b. Infatti, se c appartiene a K a e K b , allora b~c, c~a, b~a => K a = K b .

Pertanto, diverse classi di equivalenza o non si intersecano oppure si intersecano e poi coincidono. Ogni elemento c di A appartiene ad una sola classe di equivalenza K c. Pertanto, un sistema di classi di equivalenza disgiunte all'intersezione dà l'intero insieme A. E quindi questo sistema è una partizione dell'insieme A in classi di equivalenza.

Inversa: Sia A = somma su oppure A i è una partizione di A. Introduciamo la relazione a~b su A, poiché a~b ⇔ a,b appartengono alla stessa classe di partizione. Questa relazione soddisfa i seguenti assiomi:

1) a ~ a (sono nella stessa classe);
2) a~b → b~a;
3) a ~ b & b ~ c → a ~ c, cioè la relazione introdotta ~ è una relazione di equivalenza.

Commento:
1) una partizione di un insieme A in sottoinsiemi di singoli elementi e una partizione di A costituita solo dall'insieme A sono chiamate partizioni banali (improprie).

2) La partizione A in sottoinsiemi di un solo elemento corrisponde ad una relazione di equivalenza che è di uguaglianza.

3) Le partizioni A, costituite da una classe A, corrispondono ad una relazione di equivalenza contenente A x A.

4) a σ b → [a] σ = [b] σ - qualsiasi relazione di equivalenza definita su un certo insieme divide questo insieme in classi disgiunte a coppie chiamate classi di equivalenza.

Definizione: L'insieme delle classi di equivalenza di un insieme A è chiamato quoziente insieme A/σ dell'insieme A per l'equivalenza σ.

Definizione: La mappatura p:A→A/σ, per la quale p(A)=[a]σ, è detta mappatura canonica (naturale).

Qualsiasi relazione di equivalenza definita su un certo insieme partiziona questo insieme in classi disgiunte a coppie chiamate classi di equivalenza.

Se l'atteggiamento R ha le seguenti proprietà: riflessiva simmetrica transitiva, cioè è una relazione di equivalenza (~ o ​​≡ o E) sull'insieme M , allora l'insieme delle classi di equivalenza è detto insieme dei fattori dell'insieme M riguardo all'equivalenza R ed è designato SIG

C'è un sottoinsieme di elementi dell'insieme M equivalente X , chiamato classe di equivalenza.

Dalla definizione di un insieme di fattori segue che è un sottoinsieme di un booleano: .

La funzione viene chiamata identificazione ed è definito come segue:

Teorema. Algebra dei fattori F n /~ è isomorfo all'algebra delle funzioni booleane B N

Prova.

L'isomorfismo richiesto ξ : F N / ~ → B n è determinato dalla seguente regola: classe di equivalenza ~(φ) la funzione è abbinata fφ , avere una tabella di verità per una formula arbitraria dall'insieme ~(φ) . Poiché diverse classi di equivalenza corrispondono a diverse tavole di verità, la mappatura ξ iniettivo e since per qualsiasi funzione booleana F da A pag c'è una formula che rappresenta la funzione F, poi la mappatura ξ suriettivo. Memorizza le operazioni, 0, 1 quando visualizzato ξ viene controllato direttamente. CTD.

Per il teorema sulla completezza funzionale di ogni funzione che non sia costante 0 , corrisponde ad alcuni SDNF ψ , appartenente alla classe ~(φ) = ξ -1 (f) formule che rappresentano una funzione F . Si pone il problema di essere in classe ~(φ) forma normale disgiuntiva, che ha la struttura più semplice.

Fine del lavoro -

Questo argomento appartiene alla sezione:

Corso di lezioni frontali sulla disciplina matematica discreta

Università statale di ingegneria civile di Mosca.. Istituto di economia gestionale e sistemi informativi nell'edilizia.. IEEE..

Se hai bisogno di materiale aggiuntivo su questo argomento, oppure non hai trovato quello che cercavi, ti consigliamo di utilizzare la ricerca nel nostro database delle opere:

Cosa faremo con il materiale ricevuto:

Se questo materiale ti è stato utile puoi salvarlo sulla tua pagina sui social network:

Tutti gli argomenti in questa sezione:

Oggetto di matematica discreta
L'argomento della matematica discreta (finita, finita) è una branca della matematica che studia le proprietà delle strutture discrete, mentre la matematica classica (continua) studia le proprietà degli oggetti

Isomorfismo
La scienza che studia le operazioni algebriche si chiama algebra. Questo concetto diventerà più specifico e approfondito man mano che studierai il corso. L’algebra è interessata solo alla questione COME agire

Esercizi
1. Dimostrare che una mappatura isomorfa è sempre isotona e non è vero il contrario. 2. Scrivi il tuo gruppo nella lingua dei set. 3. Annotare nella lingua degli insiemi gli oggetti che

Insieme ed elementi dell'insieme
Attualmente, le teorie degli insiemi esistenti differiscono nella paradigmatica (sistema di opinioni) della base concettuale e dei mezzi logici. Quindi, come esempio, possiamo citarne due opposti

Insiemi finiti e infiniti
Ciò di cui è composto il set, ad es. Gli oggetti che compongono un insieme sono chiamati i suoi elementi. Gli elementi di un insieme sono distinti e distinti gli uni dagli altri. Come si può vedere dall'esempio fornito

Potenza dell'insieme
La cardinalità di un insieme finito è uguale al numero dei suoi elementi. Ad esempio, la cardinalità dell'universo B(A) di un insieme A di cardinalità n

A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |Àn-2An-1An| + (-1)n-1 |À1A2A3…An|
Un insieme finito A ha cardinalità k se è uguale al segmento 1..k;:

Sottoinsieme, sottoinsieme proprio
Dopo aver introdotto il concetto di insieme, sorge il compito di costruire nuovi insiemi da quelli esistenti, cioè definire le operazioni sugli insiemi. Set di M",

Linguaggio simbolico delle teorie degli insiemi significativi
Durante lo studio del corso distingueremo tra il linguaggio oggetto della teoria degli insiemi e il metalinguaggio, attraverso il quale viene studiato il linguaggio oggetto. Con il linguaggio della teoria degli insiemi intendiamo relazionale

Prova
L'insieme B è infinito, il che significa

Aggiunta e rimozione di elementi
Se A è un insieme e x è un elemento, quindi l'elemento

Insiemi limitati. Stabilisci i confini
Sia data una funzione numerica f(x) su un insieme X. Il limite superiore (confine) della funzione f(x) è un numero di questo tipo

Limite superiore (inferiore) esatto
L'insieme di tutti i confini superiori E è indicato con Es, e tutti i confini inferiori con Ei. Nel caso

L'esatto limite superiore (inferiore) del set
Se un elemento z appartiene all'intersezione dell'insieme E e dell'insieme di tutti i suoi confini superiori Es (rispettivamente inferiore r

Proprietà fondamentali degli estremi superiori e inferiori
Sia X un insieme parzialmente ordinato. 1. Se, allora

Impostato da un punto di vista attributivo
Il punto di vista aggregato, a differenza del punto di vista attributivo, è logicamente insostenibile nel senso che porta a paradossi del tipo di Russell e Cantor (vedi sotto). Nell'ambito della t attributiva

Struttura
Un insieme parzialmente ordinato X è detto struttura se contiene un insieme di due elementi

Set di copertura e separazione
Una partizione di un insieme A è una famiglia Ai

Relazioni binarie
Una successione di lunghezza n, i cui termini sono a1, .... an, sarà denotata con (a1, .... a

Proprietà delle relazioni binarie
Una relazione binaria R sull'insieme Ho ha le seguenti proprietà: (a) riflessiva se xRx

Relazioni ternarie
Prodotto cartesiano XY

Relazioni n-arie
Per analogia con il prodotto cartesiano di due insiemi X,Y, possiamo costruire il prodotto cartesiano X

Visualizza
Le mappature sono alcune connessioni tra elementi di insiemi. Gli esempi più semplici di relazioni sono le relazioni di appartenenza x

Corrispondenza
Un sottoinsieme S di un prodotto cartesiano è detto corrispondenza n-aria di elementi di insiemi Mi. Formalmente

Funzione
Tutti i rami della matematica discreta si basano sul concetto di funzione. Sia X -

Rappresentare una funzione in termini di relazioni
Una relazione binaria f è chiamata funzione se da e

Iniezione, suriezione, biiezione
Quando si utilizza il termine “mappatura” si distingue tra la mappatura XbY e la mappatura X su Y

Funzione inversa
Per quelli arbitrari, definiamo

Insiemi parzialmente ordinati
Un insieme S si dice parzialmente ordinato (PUM) se è data una relazione binaria di ordine parziale riflessiva, transitiva e antisimmetrica

Imposta la minimizzazione della rappresentazione
Utilizzando queste leggi, consideriamo il problema di minimizzare la rappresentazione dell'insieme M mediante le operazioni

Riarrangiamenti
Dato un insieme A. Sia A un insieme finito costituito da n elementi A = (a1, a2, …, a

Permutazioni con ripetizioni
Supponiamo che l'insieme A abbia elementi identici (ripetuti). Permutazione con ripetizioni della composizione (n1, n2, … ,nk

Posizionamenti
Tuple di lunghezza k (1≤k≤n), costituite da diversi elementi dell'insieme di n elementi A (le tuple differiscono in

Posizionamenti con ripetizioni
Supponiamo che l'insieme A abbia elementi identici (ripetuti). Posizionamenti con ripetizioni di n elementi di k nomi

Posizionamento ordinato
Collochiamo n oggetti in m riquadri in modo che ogni riquadro contenga una sequenza e non, come prima, un insieme di oggetti collocati al suo interno. Due

Combinazioni
Da un insieme di m elementi A costruiamo un insieme ordinato di lunghezza n, i cui elementi sono arrangiamenti con gli stessi temi

Combinazioni con ripetizioni
Le formule risultanti sono valide solo quando non ci sono elementi identici nell'insieme A. Lasciamo che ci siano elementi di n tipi e da essi una tupla di

Metodo di generazione di funzioni
Questo metodo viene utilizzato per enumerare i numeri combinatori e stabilire identità combinatorie. Il punto di partenza è il combinatore di sequenze (ai).

Sistema algebrico
Un sistema algebrico A è una collezione ‹M,O,R›, la cui prima componente M è un insieme non vuoto, la seconda componente O è un insieme

Chiusura e sottoalgebre
Un sottoinsieme si dice chiuso rispetto all'operazione φ se

Algebre con una operazione binaria
Sia data un'operazione binaria sull'insieme M. Consideriamo le algebre che genera, ma prima considereremo alcune proprietà delle operazioni binarie. O binario

Gruppoide
Algebra della forma<М, f2>chiamato gruppoide. Se f2 è un'operazione come la moltiplicazione (

Interi modulo m
Dato un anello di numeri interi . Lascia che te lo ricordiamo. Algebra<М,

Congruenze
Congruenza sull'algebra A = (Σ – la segnatura dell'algebra consiste solo di simboli di funzione) viene chiamata tale relazione di equivalenza

Elementi di teoria dei grafi
I grafici sono oggetti matematici. La teoria dei grafi viene utilizzata in settori quali la fisica, la chimica, la teoria della comunicazione, la progettazione informatica, l'ingegneria elettrica, l'ingegneria meccanica, l'architettura, la ricerca su

Grafico, vertice, spigolo
Per grafo non orientato (o, in breve, grafo) intendiamo tale coppia arbitraria G = , Che cosa

Corrispondenza
Un'altra descrizione, usata più spesso, di un grafo orientato G consiste nello specificare un insieme di vertici X e una corrispondenza Г, a

Grafico non orientato
Se gli spigoli non hanno orientamento, il grafo viene chiamato non orientato (duplicato non orientato o non orientato

Incidenza, grafico misto
Se lo spigolo e ha la forma (u, v) oppure<и, v>, allora diremo che l'arco e è incidente ver

Corrispondenza inversa
Poiché rappresenta un insieme di tali vertici

Isomorfismo del grafico
Due grafici G1 = e G2 = sono isomorfi (G

Itinerario orientato al percorso
Un percorso (o percorso diretto) di un grafo diretto è una sequenza di archi in cui

Archi adiacenti, vertici adiacenti, grado dei vertici
Archi a = (xi, xj), xi ≠ xj, aventi vertici finali in comune, n

Connettività
Due vertici di un grafo si dicono connessi se esiste un percorso semplice che li collega. Un grafo si dice connesso se tutti i suoi vertici sono connessi. Teorema.

Grafico dell'arco ponderato
Un grafo G = (N, A) si dice pesato se sull'insieme degli archi A è definita una funzione l: A → R tale che

Forte matrice di connettività
Matrice di connettività forte: metti 1 lungo la diagonale; compilare la riga X1 - se il vertice è raggiungibile da X1 e X1 d

Alberi
Gli alberi sono importanti non solo perché trovano applicazioni in vari campi della conoscenza, ma anche perché occupano una posizione speciale nella stessa teoria dei grafi. Quest'ultimo è causato dall'estrema semplicità della struttura dell'albero

Qualsiasi albero non banale ha almeno due vertici pendenti
Dimostrazione Consideriamo l'albero G(V, E). Un albero è quindi un grafo connesso

Teorema
Il centro di un albero libero è costituito da un vertice o due vertici adiacenti: Z(G) = 0&k(G) = 1 → C(G) = K1

Alberi diretti, ordinati e binari
Gli alberi diretti (ordinati) sono un'astrazione delle relazioni gerarchiche che si incontrano molto spesso sia nella vita pratica che in matematica e programmazione. Albero (orientamento)

Prova
1. Ogni arco entra in un nodo. Dal punto 2 della definizione 9.2.1 abbiamo: v

Alberi ordinati
Gli insiemi T1,..., Tk nella definizione equivalente di orderev sono sottoalberi. Se l'ordine relativo dei sottoalberi T1,...,

Alberi binari
Un albero binario (o binario) è un insieme finito di nodi che è vuoto o è costituito da una radice e due alberi binari disgiunti: sinistro e destro. Albero binario non in Java

Rappresentazione dell'albero gratuita
Per rappresentare gli alberi, è possibile utilizzare le stesse tecniche utilizzate per rappresentare i grafici generali: matrici di adiacenza e incidenza, elenchi di adiacenza e altro. Ma utilizzando le proprietà speciali di

Fine per
Motivazione Il codice Prüfer è infatti una rappresentazione di albero libera. Per verificarlo, mostriamo che se T" è un albero

Rappresentazione di alberi binari
Qualsiasi albero libero può essere orientato designando uno dei suoi nodi come radice. Qualsiasi ordine può essere ordinato arbitrariamente. Per i discendenti di un nodo (fratelli) di un ordine ordinato si definisce relativo

Funzioni logiche di base
Indichiamo con E2 = (0, 1) un insieme composto da due numeri. I numeri 0 e 1 sono fondamentali in un tappetino discreto

Funzione booleana
Una funzione booleana di n argomenti x1, x2, … ,xn è una funzione f dall'ennesima potenza dell'insieme

Algebra booleana a due elementi
Consideriamo l'insieme Во = (0,1) e definiamo le operazioni su di esso, secondo le tabelle delle fonti

Tabelle di funzioni booleane
Una funzione booleana di n variabili può essere specificata da una tabella composta da due colonne e 2n righe. La prima colonna elenca tutti i set da B

F5 – ripetere in y
f6 – somma modulo 2 f7

Ordine delle operazioni
Se in un'espressione complessa non ci sono parentesi, le operazioni devono essere eseguite nel seguente ordine: congiunzione, disgiunzione, implicazione, equivalenza, negazione. Convenzioni riguardanti la disposizione del primo teorema di Shannon
Per risolvere il problema di trovare SDNF e SCNF equivalenti alla formula originale φ, consideriamo innanzitutto gli sviluppi della funzione booleana f(x1, x2

Secondo teorema di Shannon
In virtù del principio di dualità, per le algebre booleane vale il Teorema 6.4.3 (secondo teorema di Shannon). Qualsiasi funzione booleana f(x1, x2,...

Completezza funzionale
Teorema (sulla completezza funzionale). Per ogni funzione booleana f esiste una formula φ che rappresenta la funzione f

Algoritmo per trovare sdnf
Per trovare il SDNF, questa formula deve prima essere ridotta al DNF, e poi trasformare i suoi congiunti in costituenti dell'unità utilizzando le seguenti azioni: a) se il congiunto include alcuni

Il metodo di Quine
Consideriamo il metodo di Quine per trovare l'MDNF che rappresenta una data funzione booleana. Definiamo le seguenti tre operazioni: - operazione completa di incollaggio -

Rappresentazione canonica delle funzioni logiche
Le forme canoniche delle funzioni logiche (formule) sono espressioni che hanno la forma standard di una formula booleana in modo tale da rappresentare in modo univoco una funzione logica. Nell'algebra

Sistemi di funzioni booleane
Sia le funzioni booleane f(g1, g2, …, gm) e g1(x1, x2, …, xn), g2(x1

Base di Zhegalkin
Proviamolo, diamo un'occhiata al sistema. È completo poiché qualsiasi funzione della base standard è espressa in termini

Teorema di Post
Il teorema di Post stabilisce condizioni necessarie e sufficienti per la completezza di un sistema di funzioni booleane. (Post E.L. I sistemi interattivi a due valori della logica matematica. – Annals of Math. Stu

Prova
Necessità. Dal contrario. Lascia fare

Algebra di Zhegalkin
La somma modulo 2, la congiunzione e le costanti 0 e 1 formano un sistema funzionalmente completo, cioè formare un'algebra - algebra di Zhegalkin. A=

Proposizione logica
La logica matematica studia i concetti base della sintassi (forma) e della semantica (contenuto) del linguaggio naturale. Consideriamo tre aree principali di ricerca nella logica matematica: la logica

Definizione di predicato
Siano X1, X2, ..., Xn variabili arbitrarie. Chiameremo queste variabili variabili soggetto. Lascia che sia la variabile a impostarti

Applicazione dei predicati in algebra
Consideriamo i predicati in cui solo una variabile è libera, che denotiamo con x, e discutiamo l'uso dei predicati in algebra. Un tipico esempio

Algebra dei predicati booleani
Poiché le operazioni logiche possono essere applicate ai predicati, per essi valgono le leggi fondamentali dell'algebra booleana. Teorema. (Proprietà delle operazioni logiche per i predicati). Mn

FA↔SOL=(FA→SOL)(SOL→FA), FA→SOL=non FA SOL
2. Utilizzare la legge not not F=F, leggi di de Morgan: not (F

Calcolo dei predicati
Il calcolo dei predicati è anche chiamato teoria del primo ordine. Nel calcolo dei predicati, così come nel calcolo proposizionale, il primo posto più importante è il problema della risolubilità.

Successione ed equivalenza
La forma proposizionale Q2 segue dalla forma proposizionale Q1 se l'implicazione Q1→Q2 diventa vera

Notazioni accettate
Simboli di "non ordinare più". Quando si confronta il tasso di crescita di due funzioni f(n) e g(n) (con valori non negativi), sono molto convenienti i seguenti

Meta designazioni
Simboli Contenuto Esempio OR

Sia R una relazione binaria sull'insieme X. La relazione R si chiama riflettente , se (x, x) О R per ogni x О X; simmetrico – se da (x, y) О R segue (y, x) О R; il numero transitivo 23 corrisponde all'opzione 24 se (x, y) О R e (y, z) О R implica (x, z) О R.

Esempio 1

Diremo che x О X ha in comune con elemento y О X, se l'insieme
x Ç y non è vuoto. La relazione da avere in comune sarà riflessiva e simmetrica, ma non transitiva.

Relazione di equivalenza su X è una relazione riflessiva, transitiva e simmetrica. È facile vedere che R Í X ´ X sarà una relazione di equivalenza se e solo se valgono le inclusioni:

Id XÍ R (riflessività),

R -1 Í R (simmetria),

R°RÍR (transitività).

In realtà, queste tre condizioni equivalgono alle seguenti:

Id XÍ R, R -1 = R, R°R = R.

Dividendosi di un insieme X è l'insieme A di sottoinsiemi a Í X disgiunti a due a due tali che UA = X. Ad ogni partizione A possiamo associare una relazione di equivalenza ~ su X, ponendo x ~ y se xey sono elementi di qualche a Î A .

Ad ogni relazione di equivalenza ~ su X corrisponde una partizione A, i cui elementi sono sottoinsiemi, ciascuno dei quali è costituito da quelli della relazione ~. Questi sottoinsiemi vengono chiamati classi di equivalenza . Questa partizione A è detta insieme dei fattori dell'insieme X rispetto a ~ ed è denotata: X/~.

Definiamo la relazione ~ sull'insieme w dei numeri naturali, ponendo x ~ y se i resti della divisione xey per 3 sono uguali. Allora w/~ è costituito da tre classi di equivalenza corrispondenti ai resti 0, 1 e 2.

Relazione d'ordine

Si dice una relazione binaria R su un insieme X antisimmetrico , se da x R y e y R x segue: x = y. Si dice una relazione binaria R su un insieme X relazione d'ordine , se è riflessiva, antisimmetrica e transitiva. È facile vedere che ciò equivale alle seguenti condizioni:

1) Id XÍ R (riflessività),

2) RÇ R -1 (antisimmetria),

3) R°RÍR (transitività).

Viene detta una coppia ordinata (X, R) costituita da un insieme X e da una relazione d'ordine R su X insieme parzialmente ordinato .

Esempio 1

Sia X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2 ), (1, 3), (2, 2), (3, 3)).

Poiché R soddisfa le condizioni 1 – 3, allora (X, R) è un insieme parzialmente ordinato. Per gli elementi x = 2, y = 3, né x R y né y R x sono veri. Tali elementi sono chiamati incomparabile . Di solito la relazione d'ordine è indicata con £. Nell’esempio riportato 0£1 e 2£2, ma non è vero che 2£3.

Esempio 2

Permettere< – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество.

Si chiamano elementi x, y О X di un insieme parzialmente ordinato (X, £). paragonabile , se x £ y oppure y £ x.

Viene chiamato un insieme parzialmente ordinato (X, £). ordinato linearmente O catena , se due qualsiasi dei suoi elementi sono comparabili. L'insieme dell'esempio 2 sarà ordinato linearmente, ma l'insieme dell'esempio 1 no.

Si dice un sottoinsieme A Í X di un insieme parzialmente ordinato (X, £). delimitato sopra , se esiste un elemento x О X tale che a £ x per ogni a О A. L'elemento x О X si chiama il più grande in X se y £ x per ogni y О X. Un elemento x О X si dice massimale se non esistono elementi y О X diversi da x per i quali x £ y. Nell'esempio 1, gli elementi 2 e 3 saranno il massimo, ma non il più grande. Allo stesso modo definito limite inferiore sottoinsiemi, elementi più piccoli e minimi. Nell'esempio 1, l'elemento 0 sarà sia il più piccolo che il minimo. Nell'Esempio 2, anche 0 ha queste proprietà, ma (w, £) non ha né l'elemento più grande né quello massimo.