Fie R o relație binară pe mulțimea X. Relația R se numește reflectorizant , dacă (x, x) О R pentru toate x О X; simetric – dacă din (x, y) О R rezultă (y, x) О R; numărul tranzitiv 23 corespunde opțiunii 24 dacă (x, y) О R și (y, z) О R implică (x, z) О R.

Exemplul 1

Vom spune că x О X are în comun cu elementul y О X, dacă mulţimea
x Ç y nu este gol. Relația de a avea în comun va fi reflexivă și simetrică, dar nu tranzitivă.

Relația de echivalență pe X este o relație reflexivă, tranzitivă și simetrică. Este ușor de observat că R Í X ´ X va fi o relație de echivalență dacă și numai dacă incluziunile sunt valabile:

Id X Í R (reflexivitate),

R -1 Í R (simetrie),

R ° R Í R (tranzitivitate).

În realitate, aceste trei condiții sunt echivalente cu următoarele:

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

Prin despicare a unei mulțimi X este mulțimea A de submulțimi disjunse perechi a Í X astfel încât UA = X. Cu fiecare partiție A putem asocia o relație de echivalență ~ pe X, punând x ~ y dacă x și y sunt elemente ale unor a Î A .

Fiecărei relații de echivalență ~ pe X îi corespunde o partiție A, ale cărei elemente sunt submulțimi, fiecare fiind formată din cele din relația ~. Aceste subseturi sunt numite clase de echivalenţă . Această partiție A se numește mulțime de factori a mulțimii X față de ~ și se notează: X/~.

Să definim relația ~ pe mulțimea w de numere naturale, punând x ~ y dacă resturile de la împărțirea x și y la 3 sunt egale. Atunci w/~ constă din trei clase de echivalență corespunzătoare resturilor 0, 1 și 2.

Relația de comandă

O relație binară R pe o mulțime X se numește antisimetric , dacă din x R y și y R x rezultă: x = y. O relație binară R pe o mulțime X se numește relație de ordine , dacă este reflexiv, antisimetric și tranzitiv. Este ușor de observat că acest lucru este echivalent cu următoarele condiții:

1) Id X Í R (reflexivitate),

2) R Ç R -1 (antisimetrie),

3) R ° R Í R (tranzitivitate).

Se numește o pereche ordonată (X, R) formată dintr-o mulțime X și o relație de ordine R pe X set parțial comandat .

Exemplul 1

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

Deoarece R îndeplinește condițiile 1 – 3, atunci (X, R) este o mulțime parțial ordonată. Pentru elementele x = 2, y = 3, nici x R y nici y R x nu sunt adevărate. Astfel de elemente sunt numite incomparabil . De obicei, relația de ordine este notată cu £. În exemplul dat, 0 £ 1 și 2 £ 2, dar nu este adevărat că 2 £ 3.

Exemplul 2

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

Elementele x, y О X ale unei mulțimi parțial ordonate (X, £) sunt numite comparabil , dacă x £ y sau y £ x.

Se numește o mulțime parțial ordonată (X, £). ordonat liniar sau lanţ , dacă oricare două dintre elementele sale sunt comparabile. Setul din exemplul 2 va fi ordonat liniar, dar setul din exemplul 1 nu.

Se numește o submulțime A Í X dintr-o mulțime parțial ordonată (X, £). mărginit deasupra , dacă există un element x О X astfel încât un £ x pentru tot un О A. Elementul x О X se numește cel mai mare în X dacă y £ x pentru tot y О X. Un element x О X se numeşte maxim dacă nu există elemente y О X diferite de x pentru care x £ y. În exemplul 1, elementele 2 și 3 vor fi maxime, dar nu cele mai mari. Definit în mod similar limita inferioara submulțimi, elementele cele mai mici și minime. În exemplul 1, elementul 0 va fi atât cel mai mic, cât și minim. În Exemplul 2, 0 are și aceste proprietăți, dar (w, £) nu are nici cel mai mare, nici cel mai mare element.

Fie (X, £) o mulțime parțial ordonată, A Í X o submulțime. O relație pe A, formată din perechi (a, b) de elemente a, b О A, pentru care a £ b, va fi o relație de ordine pe A. Această relație se notează prin același simbol: £. Astfel, (A, £) este o mulțime parțial ordonată. Dacă este ordonată liniar, atunci vom spune că A este lanţ în (X, £).

Principiul maxim

Unele afirmații matematice nu pot fi dovedite fără axioma alegerii. Se spune că aceste afirmații sunt depinde de axioma de alegere sau valabil în teoria ZFC , în practică, în locul axiomei de alegere, fie axioma Zermelo, fie lema Kuratowski-Zorn, fie orice altă afirmație echivalentă cu axioma alegerii este de obicei folosită pentru demonstrație.

Lema Kuratowski-Zorn. Dacă fiecare lanț într-un set parțial ordonat(X, £) este limitat de sus, apoi în X există cel puțin un element maxim.

Această lemă este echivalentă cu axioma alegerii și, prin urmare, poate fi acceptată ca axiomă.

Teorema.Pentru orice set parțial comandat(X, £) există o relaţie care conţine relaţia£ și transformând X într-o mulțime ordonată liniar.

Dovada. Mulțimea tuturor relațiilor de ordine care conțin relația £ este ordonată după relația de includere U. Deoarece unirea unui lanț de relații de ordine va fi o relație de ordine, atunci după lema Kuratowski-Zorn există o relație maximă R astfel încât x £ y implică x R y. Să demonstrăm că R este o relație care ordonează liniar pe X. Să presupunem contrariul: să existe a, b О X astfel încât nici (a, b) și nici (b, a) să nu aparțină lui R. Să considerăm relația:

R¢ = R È ((x, y): x Ra și b R y).

Se obține prin adăugarea perechii (a, b) la R și a perechilor (x, y), care trebuie adăugate la R¢ din condiția ca R¢ să fie o relație de ordine. Este ușor de observat că R¢ este reflexiv, antisimetric și tranzitiv. Obținem R Ì R¢, care contrazice maximalitatea lui R, prin urmare, R este relația de ordin liniar dorită.

O mulțime X ordonată liniar se numește bine ordonată dacă fiecare submulțime nevide A Í X a acesteia conține cel mai mic element a Î A. Lema Kuratowski-Zorn și axioma alegerii sunt, de asemenea, echivalente cu următoarea afirmație:

Axioma lui Zermelo. Pentru fiecare mulțime există o relație de ordine care o transformă într-o mulțime complet ordonată.

De exemplu, mulțimea w de numere naturale este complet ordonată. Principiul inductanței este rezumat după cum urmează:

Inducția transfinită. Dacă(X, £) este o mulțime complet ordonată și F(x) este o proprietate a elementelor sale, adevărat pentru cel mai mic element x 0 О X și astfel încât din adevărul lui F(y) pentru tot y < z следует истинность F(z), то F(x) adevărat pentru toată lumea x О X .

Aici y< z означает, что у £ z, но y ¹ z. Действительно, в противном случае среди x Î X, не обладающих свойством F(x), можно выбрать наименьший элемент x 1 , и выполнение F(y) для всех y < x 1 приводит к выполнению F(x 1), противоречащему предположению.

Conceptul de putere

Fie f: X à Y și g: Y à Z hărți de mulțimi. Deoarece f și g sunt relații, compoziția lor este definită g ° f(x) = g(f(x)). Dacă h: Z à T este o hartă de mulțimi, atunci h ° (g ° f) = (h ° g) ° f. Relațiile Id X și Id Y sunt funcții, prin urmare, se definesc compozițiile Id Y ° f = f ° Id x = f. Pentru X = Y, definim f 2 = f ° f, f 3 = f 2 ° f, ..., f n+1 = f n ° f.

Se numește maparea f: X àY prin injectare , dacă pentru orice elemente x 1 ¹ x 2 ale mulțimii X, f(x 1) ¹ f(x 2) este adevărată. Maparea f este numită surjecție , dacă pentru fiecare y ОY există un x ​​О X astfel încât f(x) = y. Dacă f este atât o suprajecție cât și o injecție, atunci f se numește bijectie . Este ușor de observat că f este o bijecție dacă și numai dacă relația inversă f -1 Í Y ´ X este o funcție.

Vom spune că egalitatea |X| = |Y|, dacă există o bijecție între X și Y. Fie |X| £ |Y|, dacă există o injecție f: X à Y.

Teorema Cantor-Schroeder-Bernstein. Dacă|X| £ |Y| Și|Y| £ |X| , Acea|X| = |Y|.

Dovada. După condiție, există injecții f: X à Y și g: Y à X. Fie A = g¢¢Y = Img imaginea mulțimii Y față de maparea g. Apoi

(X \ A) Ç (gf)¢¢(X \ A) = Æ,

(gf)¢¢(X \ A) Ç (gf) 2 ¢¢(X \ A) = Æ, …,

(gf) n ¢¢(X \ A) Ç (gf) n+1 ¢¢(X \ A) = Æ, …

Se consideră maparea j: X à A, dată ca j(x) = gf(x), cu

x Î (X \ A) È (gf)¢¢(X \ A) È (gf) 2 ¢¢(X \ A) È …, iar j(x) = x în alte cazuri. Este ușor de observat că j este o bijecție. Bijecția necesară între X și Y va fi egală cu g -1 ° j.

Antinomia lui Cantor

Fie |X|< |Y|, если |X| £ |Y| и не существует биекции между X и Y.

teorema lui Cantor. Pentru orice set X, |X|< |P(X)|, где P(X) – множество всех подмножеств множества X.

(adică care are următoarele proprietăți: fiecare element al mulțimii este echivalent cu el însuși; dacă X echivalent y, Acea y echivalent X; Dacă X echivalent y, A y echivalent z, Acea X echivalent z ).

Apoi se numește mulțimea tuturor claselor de echivalență set de factori si este desemnat . Partiționarea unui set în clase de elemente echivalente se numește sa factorizarea.

Afișare de la Xîn mulţimea claselor de echivalenţă se numeşte cartografierea factorilor.

Exemple

Este rezonabil să folosim factorizarea multime pentru a obține spații normate din cele semi-normate, spații cu produs interior din spații cu produs aproape interior etc. Pentru a face acest lucru, introducem, respectiv, norma unei clase, egală cu norma a unui element arbitrar și produsul interior al claselor ca produs interior al elementelor arbitrare ale claselor. La rândul său, relația de echivalență este introdusă astfel (de exemplu, pentru a forma un spațiu de coeficient normalizat): se introduce o submulțime a spațiului seminormat inițial, formată din elemente cu seminorma zero (apropo, este liniară, adică, este un subspaţiu) şi se consideră că două elemente sunt echivalente dacă diferenţa lor aparţine chiar acestui subspaţiu.

Dacă, pentru factorizarea unui spațiu liniar, se introduce un anumit subspațiu și se presupune că dacă diferența a două elemente din spațiul original aparține acestui subspațiu, atunci aceste elemente sunt echivalente, atunci mulțimea factorilor este un spațiu liniar și se numește un spațiu factorial.

Exemple

Vezi si

Fundația Wikimedia. 2010.

Vedeți ce este „Setul de factori” în alte dicționare:

Principiul logic care stă la baza definițiilor prin abstracție (vezi Definiția prin abstracție): orice relație de tip de egalitate, definită pe un set inițial de elemente, desparte (împarte, clasifică) originalul... ...

O formă de gândire care reflectă proprietățile esențiale, conexiunile și relațiile obiectelor și fenomenelor în contradicția și dezvoltarea lor; un gând sau un sistem de gânduri care generalizează, distinge obiecte dintr-o anumită clasă în funcție de un anumit general și în agregat... ... Marea Enciclopedie Sovietică

Coomologia grupului Galois. Dacă M este un grup Abelian și un grup Galois al unei extensii care acționează asupra lui M, atunci grupurile de coomologie Galois sunt grupuri de coomologie definite de un complex format din toate hărțile, iar d este un operator de coomologie (vezi Coomologia grupurilor).... . .. Enciclopedie matematică

Construcția, spre paradis, a apărut mai întâi în teoria mulțimilor, apoi a devenit utilizată pe scară largă în algebră, topologie și alte domenii ale matematicii. Un caz special important al unui I. p. este un I. p. dintr-o familie dirijată de structuri matematice de același tip. Lasa … Enciclopedie matematică

Punctele deși relativ la grupul G care acționează asupra mulțimii X (în stânga), mulțimea Mulțimea este un subgrup al lui G și se numește. stabilizator sau subgrup staționar al unui punct în raport cu G. Maparea induce o bijecție între G/Gx și orbita G(x). DESPRE.… … Enciclopedie matematică

Acest articol are o introducere prea scurtă. Vă rugăm să adăugați o secțiune introductivă care prezintă pe scurt subiectul articolului și rezumă conținutul acestuia... Wikipedia

Acest articol este despre sistemul algebric. Pentru ramura logicii matematice care studiază enunțurile și operațiile asupra lor, vezi Algebra logicii. Algebra booleană este o mulțime A nevidă cu două operații binare (analoage unei conjuncții), ... ... Wikipedia

Fie dată o relație de echivalență pe o mulțime. Apoi, mulțimea tuturor claselor de echivalență se numește mulțime de factori și se notează. Partiționarea unei mulțimi în clase de elemente echivalente se numește factorizare. Maparea de la la... ... Wikipedia

În geometrie, un segment direcționat este înțeles ca o pereche ordonată de puncte, dintre care primul, punctul A, se numește începutul său, iar al doilea, B, sfârșitul său. Cuprins 1 Definiție ... Wikipedia

În diferite ramuri ale matematicii, nucleul unei mapări este un anumit kerf set, care într-un sens caracterizează diferența dintre f și o mapare injectivă. Definiția specifică poate varia, dar pentru maparea injectivă a... ... Wikipedia

Sursa locului de munca: Sarcina 10_20. Examen de stat unificat 2018 Studii sociale. Soluţie

Sarcina 20. Citiți textul de mai jos, în care lipsesc un număr de cuvinte (expresii). Selectați din lista de cuvinte (expresii) care trebuie introduse în locul golurilor.

„Calitatea vieții depinde de mulți factori, de la locul de reședință al unei persoane până la situația generală socio-economică și (A), precum și de starea afacerilor politice din țară. Calitatea vieții, într-o măsură sau alta, poate fi influențată de situația demografică, de condițiile de locuire și de producție, de volumul și calitatea _____(B), etc. În funcție de gradul de satisfacere a nevoilor din economie, este obișnuit să se distingă diferite niveluri de viață ale populației: bogăție - utilizare (B) asigurarea dezvoltării umane cuprinzătoare; nivel normal de _____(G) conform standardelor bazate științific, oferind unei persoane refacerea forței sale fizice și intelectuale; sărăcie - consumul de bunuri la nivelul menținerii capacității de muncă ca limită inferioară de reproducere _____(D); Sărăcia este consumul setului minim acceptabil de bunuri și servicii conform criteriilor biologice, care permite doar menținerea viabilității umane.

Populația, adaptându-se la condițiile pieței, folosește diverse surse suplimentare de venit, inclusiv venituri din parcele personale, profit din _____(E).”

Cuvintele (expresiile) din listă sunt date la caz nominativ. Fiecare cuvânt (expresie) poate fi folosit o singură dată.

Selectați un cuvânt (expresie) după altul, completând mental fiecare gol. Vă rugăm să rețineți că există mai multe cuvinte (expresii) în listă decât veți avea nevoie pentru a completa golurile.

Lista termenilor:

1) capitalul

2) de mediu

3) consumul raţional

4) bunuri de consum

5) mijloace de producţie

7) munca

8) activitate antreprenorială

9) mobilitate socială

Soluţie.

Să inserăm termenii în text.

„Calitatea vieții depinde de mulți factori, de la locul de reședință al unei persoane până la situația generală socio-economică și de mediu (2) (A), precum și starea afacerilor politice din țară. Calitatea vieții, într-o măsură sau alta, poate fi influențată de situația demografică, de condițiile de locuire și de producție, de volumul și calitatea bunurilor de consum (4) (B), etc. În funcție de gradul de satisfacere a nevoilor din economie, se obișnuiește să se distingă diferite niveluri de viață ale populației: bogăție - utilizarea beneficiilor (6) (B) care asigură dezvoltarea cuprinzătoare a unei persoane; nivel normal de consum rațional (3) (D) conform standardelor bazate științific, oferind unei persoane refacerea forței sale fizice și intelectuale; sărăcie - consumul de bunuri la nivelul menținerii capacității de muncă ca limită inferioară a reproducerii forței de muncă (7) (D); Sărăcia este consumul setului minim acceptabil de bunuri și servicii conform criteriilor biologice, care permite doar menținerea viabilității umane.

Dacă atitudinea R are următoarele proprietăți: reflexiv simetric tranzitiv, i.e. este o relație de echivalență (~ sau ≡ sau E) pe mulțime M , atunci mulțimea claselor de echivalență se numește mulțime de factori a mulțimii M în ceea ce priveşte echivalenţa R si este desemnat DOMNUL

Există o submulțime de elemente ale mulțimii M echivalent X , numit clasa de echivalență.

Din definiția unui set de factori rezultă că este o submulțime a unui boolean: .

Funcția este numită Identificareși se definește după cum urmează:

Teorema. Algebra factorială F n /~ este izomorf la algebra funcțiilor booleene B n

Dovada.

Izomorfismul necesar ξ : F n / ~ → B n este determinat de următoarea regulă: clasa de echivalenţă ~(φ) funcția este potrivită f φ , având o tabelă de adevăr pentru o formulă arbitrară din mulțime ~(φ) . Deoarece diferite clase de echivalență corespund diferitelor tabele de adevăr, maparea ξ injectiv, iar pentru orice funcție booleană f din În p există o formulă care reprezintă funcția f, apoi cartografierea ξ surjectiv. Memorează operațiuni, 0, 1 când sunt afișate ξ se verifică direct. CTD.

Prin teorema privind completitatea funcțională a fiecărei funcții care nu este o constantă 0 , corespunde unor SDNF ψ , aparținând clasei ~(φ) = ξ -1 (f) formule care reprezintă o funcție f . Apare problema de a fi în clasă ~(φ) forma normală disjunctivă, care are cea mai simplă structură.

Sfârșitul lucrării -

Acest subiect aparține secțiunii:

Curs de prelegeri la disciplina matematică discretă

Universitatea de Stat de Inginerie Civilă din Moscova.. Institutul de Economie de Management și Sisteme Informaționale în Construcții.. IEEE..

Dacă aveți nevoie de material suplimentar pe această temă, sau nu ați găsit ceea ce căutați, vă recomandăm să utilizați căutarea în baza noastră de date de lucrări:

Ce vom face cu materialul primit:

Dacă acest material ți-a fost util, îl poți salva pe pagina ta de pe rețelele sociale:

Tweet

Toate subiectele din această secțiune:

Subiect de matematică discretă
Subiectul matematicii discrete (finite, finite) este o ramură a matematicii care studiază proprietățile structurilor discrete, în timp ce matematica clasică (continuă) studiază proprietățile obiectelor.

Izomorfism
Știința care studiază operațiile algebrice se numește algebră. Acest concept va deveni mai specific și mai aprofundat pe măsură ce studiați cursul. Algebra este interesată doar de întrebarea CUM să acționezi

Exerciții
1. Demonstrați că o mapare izomorfă este întotdeauna izotonă, iar inversul nu este adevărat. 2. Scrieți grupul dvs. în limba seturilor. 3. Notează în limbajul seturilor obiectele care

Setul și elementele multimii
În prezent, teoriile multimilor existente diferă în paradigmatica (sistemul de vederi) a bazei conceptuale și a mijloacelor logice. Deci, ca exemplu, putem cita două opuse

Mulțimi finite și infinite
Ceea din care constă setul, adică Obiectele care alcătuiesc o mulțime se numesc elementele sale. Elementele unui set sunt distincte și distincte unele de altele. După cum se poate observa din exemplul dat

Puterea setului
Cardinalitatea pentru o mulțime finită este egală cu numărul elementelor sale. De exemplu, cardinalitatea universului B(A) a unei mulțimi A de cardinalitate n

A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3…An|
O mulțime finită A are cardinalitatea k dacă este egală cu segmentul 1.. k;:

Subset, subset propriu
După introducerea conceptului de mulțime, apare sarcina de a construi noi mulțimi din cele existente, adică de a defini operații pe mulțimi. Set de M",

Limbajul simbolic al teoriilor multimilor semnificative
În procesul de studiere a cursului, vom face distincția între limbajul obiect al teoriei mulțimilor și metalimbajul, prin intermediul căruia se studiază limbajul obiect. Prin limbajul teoriei mulțimilor înțelegem relațional

Dovada
Mulțimea B este infinită, ceea ce înseamnă

Adăugarea și eliminarea articolelor
Dacă A este o mulțime și x este un element, atunci elementul

Seturi delimitate. Stabiliți limite
Fie dată o funcție numerică f(x) pe o mulțime X. Limita superioară (limita) a funcției f(x) este un astfel de număr

Limită superioară (inferioară) exactă
Setul tuturor limitelor superioare E este notat cu Es, iar toate limitele inferioare cu Ei. În cazul în care

Limita superioară (inferioară) exactă a setului
Dacă un element z aparține intersecției mulțimii E și mulțimii tuturor limitelor sale superioare Es (respectiv inferior r

Proprietățile de bază ale limitelor superioare și inferioare
Fie X o mulțime parțial ordonată. 1. Dacă, atunci

Setat din punct de vedere atributiv
Punctul de vedere agregat, spre deosebire de punctul de vedere atributiv, este logic insuportabil în sensul că duce la paradoxuri de tipul lui Russell și Cantor (vezi mai jos). În cadrul atributivului t

Structura
O mulțime X parțial ordonată se numește structură dacă conține orice mulțime de două elemente

Seturi de acoperire și compartimentare
O partiție a unei mulțimi A este o familie Ai

Relații binare
O succesiune de lungime n, ai carei termeni sunt a1, .... an, va fi notata cu (a1, .... a

Proprietățile relațiilor binare
O relație binară R pe mulțimea Ho are următoarele proprietăți: (a) reflexivă dacă xRx

Relații ternare
Produsul cartezian XY

Relații N-are
Prin analogie cu produsul cartezian a două mulțimi X,Y, putem construi produsul cartezian X

Afișări
Mapările sunt niște conexiuni între elementele mulțimilor. Cele mai simple exemple de relații sunt relațiile de apartenență x

Corespondenţă
O submulțime S a unui produs cartezian se numește corespondență n-ară a elementelor mulțimilor Mi. Oficial

Funcţie
Toate ramurile matematicii discrete se bazează pe conceptul de funcție. Fie X -

Reprezentarea unei funcţii în termeni de relaţii
O relație binară f se numește funcție dacă de la și

Injecție, surjecție, bijecție
Când se utilizează termenul „mapping”, se face o distincție între maparea XbY și maparea X pe Y

Funcție inversă
Pentru cele arbitrare, definim

Seturi parțial comandate
O mulțime S se numește parțial ordonată (PUM) dacă i se oferă o relație de ordin parțial binar reflexiv, tranzitiv și antisimetric.

Setați minimizarea reprezentării
Folosind aceste legi, luăm în considerare problema minimizării reprezentării mulțimii M folosind operațiile

Rearanjamente
Dată o mulțime A. Fie A o mulțime finită formată din n elemente A = (a1, a2, …, a

Permutări cu repetări
Fie că mulțimea A are elemente identice (repetate). Permutarea cu repetări ale compoziției (n1, n2, … ,nk

Plasări
Tupluri de lungime k (1≤k≤n), formate din diferite elemente ale multimii de n elemente A (tuplurile diferă în

Plasări cu repetări
Fie că mulțimea A are elemente identice (repetate). Plasări cu repetări a n elemente de k nume

Amplasare ordonată
Să plasăm n obiecte în m cutii astfel încât fiecare cutie să conțină o secvență și nu, ca înainte, un set de obiecte plasate în ea. Două

Combinații
Dintr-o mulțime de m elemente A construim o mulțime ordonată de lungime n, ale cărei elemente sunt aranjamente cu aceleași teme

Combinații cu repetări
Formulele rezultate sunt valabile numai atunci când nu există elemente identice în mulțimea A. Să fie elemente de n tipuri și din ele un tuplu de

Metoda de generare a funcțiilor
Această metodă este folosită pentru a enumera numere combinatorii și pentru a stabili identități combinatorii. Punctul de plecare este combinatorul secvenței (ai).

Sistem algebric
Un sistem algebric A este o colecție ‹M,O,R›, prima componentă a cărei M este o mulțime nevidă, a doua componentă O este o mulțime

Închidere și subalgebre
Se spune că o submulțime este închisă sub operația φ dacă

Algebre cu o operație binară
Să fie dată o operație binară pe mulțimea M. Să luăm în considerare algebrele pe care le generează, dar mai întâi vom lua în considerare unele proprietăți ale operațiilor binare. binar o

Groupoid
Algebra formei<М, f2>numit un grupoid. Dacă f2 este o operație ca înmulțirea (

Numerele întregi modulo m
Dat un inel de numere întregi . Să vă reamintim. Algebră<М,

Congruente
Congruență pe algebră A = (Σ – semnătura algebrică constă numai din simboluri de funcție) se numește o astfel de relație de echivalență

Elemente de teoria grafurilor
Graficele sunt obiecte matematice. Teoria graficelor este utilizată în domenii precum fizica, chimia, teoria comunicării, proiectarea computerelor, inginerie electrică, inginerie mecanică, arhitectură, cercetare

Grafic, vârf, muchie
Prin un graf nedirecționat (sau, pe scurt, un graf) înțelegem o astfel de pereche arbitrară G = , Ce

Corespondenţă
O altă descriere, mai des folosită, a unui graf direcționat G constă în specificarea unui set de vârfuri X și a unei corespondențe Г, pentru a

Grafic nedirecționat
Dacă marginile nu au nicio orientare, atunci graficul se numește nedirecționat (duplicat nedirecționat sau neorientat

Incidență, grafic mixt
Dacă muchia e are forma (u, v) sau<и, v>, atunci vom spune că muchia e este incidentă ver

Potrivire inversă
Deoarece reprezintă un set de astfel de vârfuri

Izomorfismul grafic
Două grafice G1 = și G2 = sunt izomorfe (G

Traseu orientat spre cale
O cale (sau traseu direcționat) a unui grafic direcționat este o succesiune de arce în care

Arce adiacente, vârfuri adiacente, grad de vârf
Arcurile a = (xi, xj), xi ≠ xj, având vârfuri comune, n

Conectivitate
Două vârfuri dintr-un graf se numesc conectate dacă există o cale simplă care le conectează. Un graf se numește conexat dacă toate vârfurile sale sunt conectate. Teorema.

Graficul arcului ponderat
Un grafic G = (N, A) se numește ponderat dacă o funcție l: A → R este definită pe mulțimea de arce A astfel încât

Matrice de conectivitate puternică
Matrice de conectivitate puternică: pune 1 de-a lungul diagonalei; completați linia X1 - dacă vârful este accesibil de la X1 și X1 d

Copaci
Arborii sunt importanți nu numai pentru că își găsesc aplicații în diverse domenii ale cunoașterii, ci și pentru că au o poziție specială în teoria grafurilor în sine. Acesta din urmă este cauzat de simplitatea extremă a structurii copacului

Orice copac non-trivial are cel puțin două vârfuri suspendate
Dovada Se consideră arborele G(V, E). Un arbore este un graf conectat, prin urmare

Teorema
Centrul unui arbore liber este format dintr-un vârf sau două vârfuri adiacente: Z(G) = 0&k(G) = 1 → C(G) = K1

Arbori direcționați, ordonați și binari
Arborii dirijați (ordonați) sunt o abstractizare a relațiilor ierarhice care sunt foarte des întâlnite atât în ​​viața practică, cât și în matematică și programare. Arborele (orientare)

Dovada
1. Fiecare arc intră într-un nod. Din clauza 2 din definiția 9.2.1 avem: v

Copaci ordonați
Mulțimile T1,..., Tk din definiția echivalentă a orderev sunt subarbori. Dacă ordinea relativă a subarborilor T1,...,

Arbori binari
Un arbore binar (sau binar) este un set finit de noduri care este fie gol, fie constă dintr-o rădăcină și doi arbori binari disjunși - stânga și dreapta. Arborele binar nu este în java

Reprezentare gratuită a arborelui
Pentru a reprezenta arbori, puteți folosi aceleași tehnici ca și pentru reprezentarea graficelor generale - matrice de adiacență și incidență, liste de adiacență și altele. Dar folosind proprietățile speciale ale

Sfârșit pentru
Argumentare Codul Prüfer este într-adevăr o reprezentare arborescentă liberă. Pentru a verifica acest lucru, să arătăm că dacă T" este un arbore

Reprezentarea arborilor binari
Orice arbore liber poate fi orientat prin desemnarea unuia dintre nodurile sale ca rădăcină. Orice comandă poate fi comandată în mod arbitrar. Pentru descendenții unui nod (frați) dintr-un ordin ordonat, acesta este definit relativ

Funcții logice de bază
Să notăm cu E2 = (0, 1) o mulțime formată din două numere. Numerele 0 și 1 sunt de bază într-un covor discret

Funcția booleană
O funcție booleană de n argumente x1, x2, … ,xn este o funcție f din puterea a n-a a mulțimii

Algebră booleană cu două elemente
Să considerăm mulțimea Во = (0,1) și să definim operații pe ea, conform tabelelor de surse

Tabelele cu funcții booleene
O funcție booleană de n variabile poate fi specificată printr-un tabel format din două coloane și 2n rânduri. Prima coloană listează toate seturile din B

F5 – repetați în y
f6 – suma modulo 2 f7

Ordinea operațiunilor
Dacă într-o expresie complexă nu există paranteze, atunci operațiile trebuie efectuate în următoarea ordine: conjuncție, disjuncție, implicare, echivalență, negație. Convenții privind aranjarea primei teoreme a lui Shannon
Pentru a rezolva problema găsirii echivalentelor SDNF și SCNF cu formula originală φ, luăm în considerare mai întâi expansiunile funcției booleene f(x1, x2).

A doua teoremă a lui Shannon
În virtutea principiului dualității, Teorema 6.4.3 (a doua teoremă a lui Shannon) este valabilă pentru algebrele booleene. Orice funcție booleană f(x1, x2,...

Completitudine funcțională
Teorema (despre completitudinea funcțională). Pentru orice funcție booleană f există o formulă φ reprezentând funcția f

Algoritm pentru găsirea sdnf
Pentru a găsi SDNF, această formulă trebuie mai întâi redusă la DNF și apoi transforma conjunctele sale în constituenți ai unității folosind următoarele acțiuni: a) dacă conjuncția include unele

metoda lui Quine
Luați în considerare metoda lui Quine pentru a găsi MDNF reprezentând o funcție booleană dată. Să definim următoarele trei operații: - operație de lipire completă -

Reprezentarea canonică a funcţiilor logice
Formele canonice ale funcțiilor logice (formule) sunt expresii care au forma standard a unei formule booleene astfel încât să reprezinte în mod unic o funcție logică. În algebră

Sisteme cu funcții booleene
Fie funcțiile booleene f(g1, g2, …, gm) și g1(x1, x2, …, xn), g2(x1

Baza Zhegalkin
Să încercăm, să ne uităm la sistem. Este completă, deoarece orice funcție din baza standard este exprimată în termeni

teorema lui Post
Teorema lui Post stabilește condițiile necesare și suficiente pentru completitudinea unui sistem de funcții booleene. (Post E.L. Sistemele interactive cu două valori ale logicii matematice. – Annals of Math. Stu

Dovada
Necesitate. Din contra. Lăsați-l să fie

algebra Zhegalkin
Suma modulo 2, conjuncția și constantele 0 și 1 formează un sistem complet funcțional, adică. formează o algebră - algebră Zhegalkin. A=

Logica propozițională
Logica matematică studiază conceptele de bază de sintaxă (formă) și semantică (conținut) ale limbajului natural. Să luăm în considerare trei domenii majore de cercetare în logica matematică - logica

Definiția unui predicat
Fie X1, X2, ..., Xn variabile arbitrare. Vom numi aceste variabile variabile subiect. Lasă variabila să te stabilească

Aplicarea predicatelor în algebră
Să considerăm predicate în care o singură variabilă este liberă, pe care le notăm cu x, și să discutăm despre utilizarea predicatelor în algebră. Un exemplu tipic

Algebră predicată booleană
Deoarece operațiile logice pot fi aplicate predicatelor, legile de bază ale algebrei booleene sunt valabile pentru acestea. Teorema. (Proprietăți ale operațiilor logice pentru predicate). Mn

F↔G=(F→G)(G→F), F→G=nu FG
2. Folosiți legea nu nu F=F, legile lui de Morgan: nu (F

Calcul predicat
Calculul predicaților se mai numește și teorie de ordinul întâi. În calculul predicatului, precum și în calculul propozițional, primul loc cel mai important este problema solubilității.

Urmărirea și echivalența
Forma propozițională Q2 decurge din forma propozițională Q1 dacă implicația Q1→Q2 devine adevărată

Notatii acceptate
Simboluri de „nu mai comanda”. Când se compară rata de creștere a două funcții f(n) și g(n) (cu valori nenegative), următoarele sunt foarte convenabile

Meta desemnări
Simboluri Cuprins Exemplu SAU

Pot fi demonstrate următoarele teoreme.

Teorema 1.4. O functie f are o functie inversa f -1 daca si numai daca f este bijectiva.

Teorema 1.5. Compoziția funcțiilor bijective este o funcție bijectivă.

Orez. 1.12 prezintă diverse relații, toate, cu excepția primei, sunt funcții.

atitudine, dar

injectie, dar

surjecție, dar

nu o funcție

nu o surjecție

nu o injecție

Fie f : A→B o funcție, iar mulțimile A și B să fie mulțimi finite, să punem A = n, B = m. Principiul lui Dirichlet afirmă că dacă n > m, atunci cel puțin o valoare a lui f apare de mai multe ori. Cu alte cuvinte, există o pereche de elemente a i ≠ a j , a i , a j A pentru care f(a i )= f(a j ).

Principiul lui Dirichlet este ușor de demonstrat, așa că îl lăsăm cititorului ca un exercițiu banal. Să ne uităm la un exemplu. Să fie mai mult de 12 elevi într-un grup. Atunci este evident că cel puțin doi dintre ei au o zi de naștere în aceeași lună.

§ 7. Relația de echivalență. Factor - set

O relație binară R pe o mulțime A se numește relație de echivalență dacă R este reflexiv, simetric și tranzitiv.

O relație de egalitate pe o mulțime de numere are proprietățile indicate și, prin urmare, este o relație de echivalență.

Relația de similitudine a triunghiului este, evident, o relație de echivalență.

Relația de inegalitate nestrictă (≤ ) pe mulțimea numerelor reale nu va fi o relație de echivalență, deoarece nu este simetrică: din 3≤ 5 nu rezultă că 5≤ 3.

O clasă de echivalență (coset) generată de un element a pentru o relație de echivalență dată R este submulțimea acelor x A care se află în relația R cu a. Clasa de echivalență indicată se notează cu [a]R, prin urmare, avem:

[a] R = (x A: a, x R).

Să ne uităm la un exemplu. Pe multimea triunghiurilor se introduce o relatie de asemanare. Este clar că toate triunghiurile echilaterale se încadrează într-un singur grup, deoarece fiecare dintre ele este similar, de exemplu, cu un triunghi, ale cărui laturi au lungimea unitară.

Teorema 1.6. Fie R o relație de echivalență pe mulțimea A și [a] R o serie, i.e. [a] R = (x A: a, x R), atunci:

1) pentru orice a A: [a] R ≠, în special, a [a] R;

2) diferite clase nu se intersectează;

3) uniunea tuturor claselor coincide cu întreaga mulțime A;

4) un set de diferite clase formează o partiție a mulțimii A.

Dovada. 1) Datorită reflexivității lui R, obținem că pentru orice a, a A, avem a,a R, deci a [ a] R și [ a] R ≠ ;

2) să presupunem că [ a] R ∩ [b] R ≠ , i.e. există un element c al lui A și c [a]R ∩ [b]R. Apoi din (cRa)&(cRb) datorita simetriei lui R obtinem ca (aR c)&(cRb), iar din tranzitivitatea lui R avem aRb.

Pentru orice x [a] R avem: (xRa)&(aRb), atunci datorită tranzitivității lui R obținem xRb, adică. x [b] R, deci [a] R [b] R. În mod similar, pentru orice y, y [b] R, avem: (yRb)&(aRb), iar datorită simetriei lui R obținem că (yRb)&(bR a), atunci, datorită tranzitivității lui R , obținem că yR a , i.e. y [a]R și

prin urmare [b] R [a] R . Din [ a ] ​​​​R [ b ] R și [ b ] R [ a ] ​​​​R obținem [ a ] ​​​​R = [ b ] R , adică dacă clasele se intersectează, atunci ele coincid;

3) pentru orice a, a A, după cum s-a dovedit, avem un [a] R, atunci, evident, uniunea tuturor claselor coincide cu mulțimea A.

Afirmația 4) din teorema 1.6 rezultă din 1)-3). Teorema a fost demonstrată. Următoarea teoremă poate fi demonstrată.

Teorema 1.7. Diferite relații de echivalență pe mulțimea A generează diferite partiții ale lui A.

Teorema 1.8. Fiecare partiție a mulțimii A generează o relație de echivalență pe mulțimea A, iar diferite partiții generează relații de echivalență diferite.

Dovada. Să fie dată o partiție B = (B i ) a mulțimii A. Să definim relația R : a,b R dacă și numai dacă există un B i astfel încât a și b să aparțină ambii acestui B i . Este evident că relația introdusă este reflexivă, simetrică și tranzitivă, prin urmare, R este o relație de echivalență. Se poate arăta că dacă partițiile sunt diferite, atunci relațiile de echivalență generate de acestea sunt și ele diferite.

Mulțimea tuturor claselor unei mulțimi A în raport cu o relație de echivalență dată R este numită mulțime de factori și se notează cu A/R. Elementele unui set de factori sunt seturi. Clasa de clase [a]R, așa cum se știe, constă din elementele A care sunt în relație între ele R.

Să considerăm un exemplu de relație de echivalență pe mulțimea numerelor întregi Z = (..., -3, -2, -1, 0, 1, 2, 3, ...).

Două numere întregi a și b se numesc comparabile (congruente) modulo m dacă m este un divizor al numărului a-b, adică dacă avem:

a=b+km , k=…, -3, -2, -1, 0, 1, 2, 3, ….

În acest caz, scrieți a≡ b(mod m) .

Teorema 1.9. Pentru orice numere a, b, c și m>0 avem:

1) a ≡ a(mod m) ;

2) dacă a ≡ b(mod m), atunci b ≡ a(mod m);

3) dacă a ≡ b(mod m) și b ≡ c(mod m), atunci a ≡ c(mod m).

Dovada. Afirmațiile 1) și 2) sunt evidente. Să demonstrăm 3). Fie a=b+k 1 m, b=c+k 2 m, apoi a=c+(k 1 +k 2)m, i.e. a ≡ c(mod m) . Teorema a fost demonstrată.

Astfel, relația de comparabilitate modulo m este o relație de echivalență și împarte mulțimea de numere întregi în clase disjunse de numere.

Să construim o spirală care se desfășoară la nesfârșit, care este prezentată în Fig. 1.13 este prezentat ca o linie continuă, iar o spirală care se răsucește la nesfârșit este prezentată ca o linie întreruptă. Fie dat un întreg nenegativ m. Vom plasa toate numerele întregi (elementele din mulțimea Z) în punctele de intersecție ale acestor spirale cu m raze, așa cum se arată în Fig. 1.13.

Pentru o relație de comparabilitate modulo m (în special, pentru m =8), clasa de echivalență este numerele aflate pe rază. Evident, fiecare număr se încadrează într-o singură clasă. Se poate obține că pentru m= 8 avem:

[ 0] ={…, -8, 0, 8, 16, …};
[ 1] ={…, -7, 1, 9, 17, …};
[ 2] ={…, -6, 2, 10, 18, …};
[ 7] ={…, -9, -1, 7, 15, …}.

Setul de factori al mulțimii Z în raport cu relația de comparație modulo m este notat cu Z/m sau cu Z m. Pentru cazul luat în considerare m =8

obţinem că Z/8 = Z8 = ( , , , …, ) .

Teorema 1.10. Pentru orice numere întregi a, b, a*, b*, k și m:

1) dacă a ≡ b(mod m), atunci ka ≡ kb(mod m);

2) dacă a ≡ b(mod m) și a* ≡ b* (mod m), atunci:

a) a+a * ≡ b+b* (mod m); b) aa * ≡ bb* (mod m).

Prezentăm dovada pentru cazul 2b). Fie a ≡ b(mod m) și a * ≡ b * (mod m), apoi a=b+sm și a * =b * +tm pentru unele numere întregi s și t. Înmulțirea

obținem: aa* =bb* + btm+ b* sm+ stm2 =bb* +(bt+ b* s+ stm)m. Prin urmare,

aa* ≡ bb* (mod m).

Astfel, comparațiile modulo pot fi adăugate și multiplicate termen cu termen, i.e. funcționează exact în același mod ca și în cazul egalităților. De exemplu,