Cum se rezolvă diagramele Venn. Matematică discretă. Principiul diagramei

Pentru o reprezentare vizuală a mulțimilor, se folosesc diagramele Euler-Venn (numite după matematicienii Leonhard Euler (1707-1783) și John Venn (1834-1923)). Mulțimile sunt notate prin zone pe plan, iar în cadrul acestor zone elementele mulțimii sunt situate condiționat. Adesea, toate seturile dintr-o diagramă sunt plasate în interiorul unui dreptunghi, care este un set universal. Dacă un element aparține mai multor mulțimi, atunci regiunile corespunzătoare acestor seturi trebuie să se suprapună astfel încât element comun ar putea fi simultan în zonele respective. Alegerea formei zonelor care înfățișează mulțimile din diagrame poate fi arbitrară (cercuri, poligoane etc.).

De exemplu, cu ajutorul diagramelor Euler-Venn se poate arăta că o mulțime este o submulțime a unei mulțimi (Fig. 3).

Să ilustrăm operaţiile de mai sus asupra mulţimilor cu ajutorul diagramelor Euler-Venn: a) unirea mulţimilor şi; b) intersecția setată; c) diferenta multimii (fara); d) adăugarea unui set la un set universal (Fig. 4, dar, b, în, G).

Exemplul 1 Demonstrați identitatea folosind diagramele Euler–Venn.

Soluţie

Să construim complementul unei mulțimi la o mulțime universală (Fig. 5, dar). Setul corespunde zonei umbrite (Fig. 5, b). Astfel, se poate observa că pe diagramele Euler-Venn, mulțimile și sunt reprezentate în același mod, așadar.

Exemplul 2 Arata asta .

Soluţie

Să construim o mulțime corespunzătoare laturii stângi a identității date. Setul este reprezentat de zona umbrită din Fig. 6, dar. Setul corespunde zonei umbrite din Fig. 6, b.

Setul descrie zona umbrită în ambele diagrame anterioare, așa că este prezentat în Fig. 6, în zonă mai întunecată.

Să construim o mulțime corespunzătoare laturii drepte a identității date.

Seturile și sunt reprezentate de zona umbrită din Fig. 7, darși 7, b respectiv.

Setul este prezentat de zona umbrită din Fig. 7, în.

Comparând Fig. 6, în iar fig. 7, în, vedem că diagramele Euler-Venn sunt reprezentate în același mod, deci .

Întrebări și sarcini pentru soluții independente

1. Desenați mulțimi folosind diagramele Euler-Venn:

2. Descrieți seturile corespunzătoare părților umbrite din fig. 8, dar, b, în, G, folosind diagramele Euler-Venn:

3. Folosiți diagramele Euler-Venn pentru a arăta că:

1.4. Proprietățile operațiilor de set

Operațiile de set introduse mai sus au următoarele proprietăți.

1. - comutativitate.

2. - Asociativitate.

3. - distributivitatea.

4. - idempotenta.

5. - legile identităţii.

6. ,, sunt legi complementare.

7. - Legile lui De Morgan.

8. - legi de absorbtie.

9. - legile lipirii.

10. - Legile lui Poretsky.

Exemplul 1 Pe baza proprietăților operațiilor pe mulțimi, simplificați expresia.

Soluţie

= /legea lui Morgan/ =

= = /legea distributivității/ =

= = /legea comutativității/ =

= = /legea distributivității/ =

/legea comutativității/ =

/legi de adaos/ =

= /legile comutativității și identității/ =

= = /definirea diferenței simetrice/ =.

După cum sa menționat deja, cardinalitatea unei mulțimi finite este numărul elementelor sale. Următoarea teoremă oferă o regulă simplă pentru calcularea cardinalității unirii a două mulțimi.

Teorema incluziunilor și excluderilor. Puterea unirii a două mulțimi este egală cu diferența dintre suma puterilor acestor mulțimi și puterea intersecției lor, adică .

Dovada

Dovada afirmației este cel mai convenabil ilustrată grafic. După cum se arată în fig. 9, multimea este formata din submultimi:, si care nu au elemente comune. Prin urmare, și.

Să introducem notația:

Q.E.D.

Exemplul 2 Fiecare dintre cei 63 de studenți din primul an care studiază informatica la universitate poate participa la cursuri suplimentare. Dacă 16 dintre ei urmează și un curs de contabilitate, 37 urmează și un curs de afaceri și 5 studiază ambele discipline, atunci câți studenți nu frecventează deloc orele suplimentare menționate?

Soluţie

Să introducem notația:

Prin urmare, este numărul studenților care nu urmează cursuri suplimentare.

Observație 1. Teorema de includere și excludere poate fi formulată pentru cazul a trei mulțimi:

Exemplul 3 Sunt 42 de studenți la curs. Dintre aceștia, 16 sunt angajați la secția de atletism, 24 la secția de fotbal, 15 la secția de șah, 11 atât la secția de atletism, cât și la cea de fotbal; 8 - atât la atletism, cât și la șah; 12 - atât la fotbal, cât și la șah; și 6 în toate cele trei secțiuni. Restul studenților sunt pasionați de turism. Câți studenți sunt turiști?

Soluţie

Să introducem notația:

Din starea problemei: ,,,,,, și.

De unde, adică numărul de studenți implicați în turism.

Observația 2. Când rezolvați problemele de mai sus, este convenabil să folosiți diagramele Euler-Venn.

Sarcini pentru soluție independentă

Demonstrați identitățile folosind proprietățile operațiilor de set:

2. 33 de persoane au venit la prânz în sala de mese. 10 persoane au comandat supă, 16 - pilaf, 30 - compot, 7 persoane au comandat toate cele trei feluri de mâncare, 8 persoane au comandat supă și pilaf, 14 persoane au comandat supă și compot. Câți oameni au comandat pilaf și compot?

3. În grupul de studenți, 12 persoane studiază limba engleză, 13 - limba germana, 16 - franceză, 4 - numai engleză și germană, 3 - numai engleză și franceză, 5 - toate cele trei limbi. Nu există studenți doar în limba engleză în grup. Doi oameni studiază doar limba germană, șase oameni studiază doar franceza. Un student din grup nu studiază nici una dintre limbile enumerate. Câți elevi sunt în grup?

Istorie

Definiția 1

Lui Leonhard Euler i s-a pus întrebarea: este posibil, în timp ce te plimbi prin Koenigsberg, să ocolim toate podurile orașului fără a trece de două ori prin niciunul dintre ele. A fost atașat un plan al orașului cu șapte poduri.

Într-o scrisoare către un matematician italian pe care îl cunoștea, Euler a oferit o scurtă și frumoasă soluție problemei podurilor Königsberg: cu o astfel de aranjare, problema este de nerezolvat. Totodată, a indicat că întrebarea i s-a părut interesantă, pentru că. „Nici geometria, nici algebra nu sunt suficiente pentru rezolvarea ei...”.

Când a rezolvat multe probleme, L. Euler a descris mulțimi folosind cercuri, motiv pentru care au fost numite „Cercuri Euler”. Această metodă a fost folosită și mai devreme de către filozoful și matematicianul german Gottfried Leibniz, care le-a folosit pentru a explica geometric relațiile logice dintre concepte, dar mai des a folosit diagrame liniare. Euler, pe de altă parte, a dezvoltat metoda destul de temeinic. Metodele grafice au devenit deosebit de renumite datorită logicianului și filosofului englez John Venn, care a introdus diagramele Venn și schemele similare sunt adesea numite Diagramele Euler-Venn. Ele sunt utilizate în multe domenii, de exemplu, în teoria mulțimilor, teoria probabilității, logică, statistică și informatică.

Principiul diagramei

Până acum, diagramele Euler-Venn sunt utilizate pe scară largă pentru a descrie schematic toate intersecțiile posibile ale mai multor mulțimi. Diagramele arată toate combinațiile $2^n$ ale n proprietăți. De exemplu, pentru $n=3$, diagrama prezintă trei cercuri cu centrele la vârfurile unui triunghi echilateral și aceeași rază, care este aproximativ egal cu lungimea laturile triunghiului.

Operațiile logice definesc tabelele de adevăr. Diagrama arată un cerc cu numele mulțimii pe care o reprezintă, de exemplu, $A$. Zona din mijlocul cercului $A$ va afișa adevărul expresiei $A$, iar zona din afara cercului - fals. Pentru a afișa o operație logică, sunt umbrite doar acele zone în care valorile operației logice pentru seturile $A$ și $B$ sunt adevărate.

De exemplu, conjuncția a două seturi $A$ și $B$ este adevărată numai dacă ambele seturi sunt adevărate. În acest caz, pe diagramă, rezultatul conjuncției $A$ și $B$ va fi aria din mijlocul cercurilor, care aparține simultan mulțimii $A$ și mulțimii $B$ (intersecția de seturi).

Figura 1. Conjuncția mulțimilor $A$ și $B$

Utilizarea diagramelor Euler-Venn pentru a demonstra egalitățile logice

Să luăm în considerare modul în care metoda de construire a diagramelor Euler-Venn este utilizată pentru a demonstra egalitățile logice.

Să demonstrăm legea de Morgan, care este descrisă de egalitate:

Dovada:

Figura 4. Inversia $A$

Figura 5. $B$ inversare

Figura 6. Conjuncția dintre inversiunile $A$ și $B$

După ce comparăm zona pentru afișarea părților din stânga și din dreapta, vedem că acestea sunt egale. De aici rezultă valabilitatea egalității logice. Legea lui De Morgan este dovedită folosind diagramele Euler-Venn.

Rezolvarea problemei căutării de informații pe Internet folosind diagrame Euler-Venn

Pentru a căuta informații pe Internet, este convenabil să utilizați interogări de căutare cu conexiuni logice similare ca înțeles cu conjuncțiile „și”, „sau” ale limbii ruse. Sensul conectivului logic devine mai clar dacă le ilustrăm cu ajutorul diagramelor Euler-Venn.

Exemplul 1

Tabelul prezintă exemple de interogări către serverul de căutare. Fiecare cerere are propriul cod - o scrisoare de la $A$ la $B$. Trebuie să aranjați codurile de solicitare în ordinea descrescătoare a numărului de pagini găsite pentru fiecare cerere.

Figura 7

Soluţie:

Să construim o diagramă Euler-Venn pentru fiecare interogare:

Figura 8

Răspuns: BVA.

Rezolvarea unei probleme logice semnificative folosind diagramele Euler-Venn

Exemplul 2

În perioada sărbătorilor de iarnă, dintre studenții de 36$ din clasa de 2$, nu au mers la cinema, teatru sau circ. $25$ oamenii au mers la cinema, $11$ la teatru, $17$ la circ; atât la cinema cât și la teatru - $6$; iar la cinema și la circ - $10$; iar la teatru și la circ - $4$.

Câți oameni au vizitat cinematograful, teatrul și circul?

Soluţie:

Să notăm numărul de tipi care au fost la cinema, la teatru și la circ - $x$.

Să construim o diagramă și să aflăm numărul de băieți din fiecare zonă:

Figura 9

Nu au fost la teatru, nici la cinema, nici la circ - 2$ de persoană.

Deci 36 $ - 2 = 34 $ persoane. a participat la evenimente.

$6$ oamenii au mers la cinema și la teatru, ceea ce înseamnă că doar ($6 - x)$ oamenii au mers la cinema și teatru.

Oamenii de $10$ au mers la cinema și la circ, deci doar la cinema și la circ ($10 - x$).

$4$ oamenii au mers la teatru și circ, ceea ce înseamnă că doar teatrul și circul ($4 - x$) au mers la teatru și circ.

$25$ oamenii au mers la cinema, ceea ce înseamnă că doar $25 - (10 - x) - (6 - x) - x = (9+x)$ au mers la cinema.

În mod similar, doar ($1+x$) au mers la teatru.

Doar ($3+x$) au mers la circ.

Deci, am mers la teatru, cinema și circ:

$(9+x)+(1+x)+(3+x)+(10-x)+(6-x)+(4-x)+x = 34$;

Acestea. doar o persoană a mers la teatru, și la cinema și la circ.

Istorie

Definiția 1

Lui Leonhard Euler i s-a pus întrebarea: este posibil, în timp ce te plimbi prin Koenigsberg, să ocolim toate podurile orașului fără a trece de două ori prin niciunul dintre ele. A fost atașat un plan al orașului cu șapte poduri.

Într-o scrisoare către un matematician italian pe care îl cunoștea, Euler a oferit o scurtă și frumoasă soluție problemei podurilor Königsberg: cu o astfel de aranjare, problema este de nerezolvat. Totodată, a indicat că întrebarea i s-a părut interesantă, pentru că. „Nici geometria, nici algebra nu sunt suficiente pentru rezolvarea ei...”.

Când a rezolvat multe probleme, L. Euler a descris mulțimi folosind cercuri, motiv pentru care au fost numite „Cercuri Euler”. Această metodă a fost folosită și mai devreme de către filozoful și matematicianul german Gottfried Leibniz, care le-a folosit pentru a explica geometric relațiile logice dintre concepte, dar mai des a folosit diagrame liniare. Euler, pe de altă parte, a dezvoltat metoda destul de temeinic. Metodele grafice au devenit deosebit de renumite datorită logicianului și filosofului englez John Venn, care a introdus diagramele Venn și schemele similare sunt adesea numite Diagramele Euler-Venn. Ele sunt utilizate în multe domenii, de exemplu, în teoria mulțimilor, teoria probabilității, logică, statistică și informatică.

Principiul diagramei

Până acum, diagramele Euler-Venn sunt utilizate pe scară largă pentru a descrie schematic toate intersecțiile posibile ale mai multor mulțimi. Diagramele arată toate combinațiile $2^n$ ale n proprietăți. De exemplu, dacă $n=3$, diagrama prezintă trei cercuri cu centrele la vârfurile unui triunghi echilateral și aceeași rază, care este aproximativ egală cu lungimea laturii triunghiului.

Operațiile logice definesc tabelele de adevăr. Diagrama arată un cerc cu numele mulțimii pe care o reprezintă, de exemplu, $A$. Zona din mijlocul cercului $A$ va afișa adevărul expresiei $A$, iar zona din afara cercului - fals. Pentru a afișa o operație logică, sunt umbrite doar acele zone în care valorile operației logice pentru seturile $A$ și $B$ sunt adevărate.

De exemplu, conjuncția a două seturi $A$ și $B$ este adevărată numai dacă ambele seturi sunt adevărate. În acest caz, pe diagramă, rezultatul conjuncției $A$ și $B$ va fi aria din mijlocul cercurilor, care aparține simultan mulțimii $A$ și mulțimii $B$ (intersecția de seturi).

Figura 1. Conjuncția mulțimilor $A$ și $B$

Utilizarea diagramelor Euler-Venn pentru a demonstra egalitățile logice

Să luăm în considerare modul în care metoda de construire a diagramelor Euler-Venn este utilizată pentru a demonstra egalitățile logice.

Să demonstrăm legea de Morgan, care este descrisă de egalitate:

Dovada:

Figura 4. Inversia $A$

Figura 5. $B$ inversare

Figura 6. Conjuncția dintre inversiunile $A$ și $B$

După ce comparăm zona pentru afișarea părților din stânga și din dreapta, vedem că acestea sunt egale. De aici rezultă valabilitatea egalității logice. Legea lui De Morgan este dovedită folosind diagramele Euler-Venn.

Rezolvarea problemei căutării de informații pe Internet folosind diagrame Euler-Venn

Pentru a căuta informații pe Internet, este convenabil să utilizați interogări de căutare cu conexiuni logice similare ca înțeles cu conjuncțiile „și”, „sau” ale limbii ruse. Sensul conectivului logic devine mai clar dacă le ilustrăm cu ajutorul diagramelor Euler-Venn.

Exemplul 1

Tabelul prezintă exemple de interogări către serverul de căutare. Fiecare cerere are propriul cod - o scrisoare de la $A$ la $B$. Trebuie să aranjați codurile de solicitare în ordinea descrescătoare a numărului de pagini găsite pentru fiecare cerere.

Figura 7

Soluţie:

Să construim o diagramă Euler-Venn pentru fiecare interogare:

Figura 8

Răspuns: BVA.

Rezolvarea unei probleme logice semnificative folosind diagramele Euler-Venn

Exemplul 2

În perioada sărbătorilor de iarnă, dintre studenții de 36$ din clasa de 2$, nu au mers la cinema, teatru sau circ. $25$ oamenii au mers la cinema, $11$ la teatru, $17$ la circ; atât la cinema cât și la teatru - $6$; iar la cinema și la circ - $10$; iar la teatru și la circ - $4$.

Câți oameni au vizitat cinematograful, teatrul și circul?

Soluţie:

Să notăm numărul de tipi care au fost la cinema, la teatru și la circ - $x$.

Să construim o diagramă și să aflăm numărul de băieți din fiecare zonă:

Figura 9

Nu au fost la teatru, nici la cinema, nici la circ - 2$ de persoană.

Deci 36 $ - 2 = 34 $ persoane. a participat la evenimente.

$6$ oamenii au mers la cinema și la teatru, ceea ce înseamnă că doar ($6 - x)$ oamenii au mers la cinema și teatru.

Oamenii de $10$ au mers la cinema și la circ, deci doar la cinema și la circ ($10 - x$).

$4$ oamenii au mers la teatru și circ, ceea ce înseamnă că doar teatrul și circul ($4 - x$) au mers la teatru și circ.

$25$ oamenii au mers la cinema, ceea ce înseamnă că doar $25 - (10 - x) - (6 - x) - x = (9+x)$ au mers la cinema.

În mod similar, doar ($1+x$) au mers la teatru.

Doar ($3+x$) au mers la circ.

Deci, am mers la teatru, cinema și circ:

$(9+x)+(1+x)+(3+x)+(10-x)+(6-x)+(4-x)+x = 34$;

Acestea. doar o persoană a mers la teatru, și la cinema și la circ.

Documente similare

Restaurarea graficelor din matricele de adiacență a vârfurilor date. Construcția pentru fiecare grafic al matricei de adiacentă a muchiilor, incidență, accesibilitate, contraaccesibilitate. Căutați compoziția graficelor. Determinarea gradelor locale de vârfuri de graf. Căutați baza graficelor.

munca de laborator, adaugat 01.09.2009


Descrierea unui grafic dat prin mulțimi de vârfuri V și arce X, liste de adiacență, incidență și matrice de adiacență. Matricea de ponderi a graficului nedirecționat corespunzător. Determinarea arborelui cu calea cea mai scurtă folosind algoritmul lui Dijkstra. Găsirea copacilor pe un grafic.

lucrare de termen, adăugată 30.09.2014


Conceptul de „graf” și reprezentarea sa matriceală. Proprietăți ale matricelor de adiacență și incidență. Proprietăți ale traseelor, lanțurilor și ciclurilor. Problema găsirii vârfurilor centrale ale unui graf, caracteristicile metrice ale acestuia. Aplicarea teoriei grafurilor în domeniile științei și tehnologiei.

lucrare de termen, adăugată 05.09.2015


Algoritm pentru trecerea la o reprezentare grafică pentru un graf nedirecționat. Numărul de vârfuri dintr-un grafic nedirecționat. Citirea din matricea de adiacență. Relații între vârfuri dintr-o matrice. Specificarea coordonatelor vârfurilor în funcție de numărul de sectoare.

munca de laborator, adaugat 29.04.2011


Descrierea matematică a sistemului de control automat folosind grafice. Întocmirea unui grafic și transformarea lui, scăpând de diferențe. Optimizarea graficelor direcționate și nedirecționate, compilarea matricelor de adiacență și incidență.

munca de laborator, adaugat 03.11.2012


Grafice direcționate și nedirecționate: caracteristici generale, vârfuri și muchii speciale, semigrade de vârfuri, matrici de adiacență, incidență, accesibilitate, conectivitate. Caracteristicile numerice ale fiecărui grafic, parcurgerea în profunzime și lățime, baza ciclurilor.

lucrare de termen, adăugată 14.05.2012


Verificarea validității identităților sau incluziunilor folosind algebra multimelor și diagramele Euler-Venn. Reprezentarea unui grafic și a unei matrice a unei relații care are proprietățile de reflexivitate, tranzitivitate și antisimetrie. Explorarea unui grafic nedirecționat.

test, adaugat 05.05.2013


Un set este o colecție de elemente unite printr-un anumit atribut. Operațiile sunt definite pe mulțimi, care sunt în multe privințe similare cu aritmetica. Operațiile pe mulțimi sunt interpretate geometric folosind diagrame Euler-Venn.

rezumat, adăugat 02.03.2009


Construirea diagramei pseudograf, a matricei de incidență și a matricei de vecinătate a vârfurilor. Restaurarea unui arbore dintr-un vector folosind algoritmul Prufer. Construirea unui tabel de adevăr pentru o funcție și forme normale conjunctive și disjunctive perfecte.

test, adaugat 25.09.2013


Metode de rezolvare a problemelor de matematică discretă. Calculul celei mai scurte căi între perechile tuturor vârfurilor dintr-un grafic direcționat și nedirecționat folosind algoritmul Floyd. Analiza problemei și metodele de soluționare a acesteia. Dezvoltarea și caracteristicile programului.