Podobné dokumenty
Rekonštrukcia grafov z daných matíc susednosti vrcholov. Konštrukcia matice susednosti hrán, výskytu, dosiahnuteľnosti, protidosiahnuteľnosti pre každý graf. Vyhľadajte kompozíciu grafov. Určenie lokálnych stupňov vrcholov grafu. Vyhľadajte základňu grafov.
laboratórne práce, doplnené 01.09.2009
Popis daného grafu pomocou množín vrcholov V a oblúkov X, zoznamov susedností, matice výskytu a susednosti. Váhová matica zodpovedajúceho neorientovaného grafu. Určenie stromu najkratšej cesty Dijkstrovým algoritmom. Hľadanie stromov na grafe.
semestrálna práca, pridaná 30.09.2014
Pojem "graf" a jeho maticová reprezentácia. Vlastnosti matíc susednosti a incidencie. Vlastnosti trás, reťazí a slučiek. Problém hľadania centrálnych vrcholov grafu, jeho metrické charakteristiky. Aplikácia teórie grafov v oblasti vedy a techniky.
semestrálna práca, pridaná 09.05.2015
Algoritmus prechodu na grafické znázornenie pre neorientovaný graf. Počet vrcholov v neorientovanom grafe. Čítanie z matice susedstva. Spojenia medzi vrcholmi v matici. Nastavenie súradníc vrcholov v závislosti od počtu sektorov.
laboratórne práce, doplnené 29.04.2011
Matematický popis automatického riadiaceho systému pomocou grafov. Zostavenie grafu a jeho transformácia, zbavenie sa diferenciálov. Optimalizácia orientovaných a neorientovaných grafov, zostavovanie matíc susednosti a výskytu.
laboratórne práce, doplnené 3.11.2012
Orientované a neorientované grafy: všeobecné charakteristiky, špeciálne vrcholy a hrany, polstupne vrcholov, susedstvo, incidencia, dosiahnuteľnosť, matice konektivity. Číselné charakteristiky každého grafu, prechod do hĺbky a šírky, základ cyklov.
semestrálna práca, pridaná 14.05.2012
Kontrola platnosti identít alebo inklúzií pomocou množinovej algebry a Euler-Vennových diagramov. Obraz grafu a matice vzťahu, ktorý má vlastnosti reflexivity, tranzitivity a antisymetrie. Štúdium neorientovaného grafu.
test, pridané 05.05.2013
Množina odkazuje na množinu prvkov spojených nejakým atribútom. Operácie sú definované nad množinami, ktoré sú v mnohom podobné aritmetike. Operácie množín sú interpretované geometricky pomocou Euler-Vennových diagramov.
abstrakt, pridaný 2.3.2009
Konštrukcia pseudografového diagramu, matice výskytu a matice susednosti vrcholov. Obnova stromu z vektora pomocou Prüferovho algoritmu. Zostavenie pravdivostnej tabuľky pre funkciu a dokonalé konjunktívne a disjunktívne normálne formy.
test, pridané 25.09.2013
Metódy riešenia úloh diskrétnej matematiky. Výpočet najkratšej cesty medzi pármi všetkých vrcholov v orientovaných a neorientovaných grafoch pomocou Floydovho algoritmu. Analýza problému a metódy jeho riešenia. Vývoj a charakteristika programu.
Niektoré problémy sa dajú pohodlne a prehľadne vyriešiť pomocou Euler-Vennových diagramov. Napríklad nastaviť úlohy. Ak neviete, čo sú Euler-Vennove diagramy a ako ich zostaviť, prečítajte si najskôr.
Teraz sa pozrime na typické problémy množiny.
Cieľ 1
V škole s hĺbkovým štúdiom cudzích jazykov sa uskutočnil prieskum medzi 100 žiakmi. Študenti dostali otázku: Aké cudzie jazyky študujete? Ukázalo sa, že 48 študentov študuje anglický jazyk, 26 - francúzsky jazyk, 28 - nemecký jazyk. Anglický a nemecký jazyk študuje 8 študentov, 8 študentov anglický jazyk a francúzsky jazyk, 13 študentov francúzsky jazyk a nemecký jazyk. 24 školákov sa neučí anglický, francúzsky alebo nemecký jazyk. Koľko z opýtaných školákov študuje súčasne tri jazyky: angličtinu, francúzštinu a nemčinu?
odpoveď: 3.
Riešenie:
- veľa školákov študujúcich angličtinu ("A");
- veľa školákov študujúcich francúzštinu ("F");
- veľa školákov študujúcich nemčinu ("H").
Ukážme si pomocou Euler-Vennovho diagramu, čo nám dáva podmienka.
Označme požadovanú oblasť A = 1, Ф = 1, Н = 1 ako "x" (v tabuľke pod oblasť 7). Vyjadrime zvyšné oblasti pomocou x.
0) Oblasť A = 0, F = 0, H = 0: 24 žiakov - dané podľa zadania problému.
1) Oblasť A = 0, F = 0, H = 1: 28- (8-x + x + 13-x) = 7 + x žiakov.
2) Oblasť A = 0, F = 1, H = 0: 26- (8-x + x + 13-x) = 5 + x žiakov.
3) Oblasť A = 0, F = 1, H = 1: 13 žiakov.
4) Oblasť A = 1, F = 0, H = 0: 48- (8-x + x + 8-x) = 32 + x žiakov.
5) Oblasť A = 1, F = 0, H = 1: 8 žiakov.
6) Oblasť A = 1, F = 1, H = 0: 8 žiakov.
| № oblasti | A |
F |
N |
množstvo školákov |
|---|---|---|---|---|
| 0 | 0 |
0 |
0 |
24 |
| 1 | 0 |
0 |
1 |
7 + x |
| 2 | 0 |
1 |
0 |
5 + x |
| 3 | 0 |
1 |
1 |
13 |
| 4 | 1 |
0 |
0 |
32 + x |
| 5 | 1 |
0 |
1 |
8 |
| 6 | 1 |
1 |
0 |
8 |
| 7 | 1 |
1 |
1 |
X |
Definujme x:
24 + 7 + (x + 5) + x + (13-x) + (32 + x) + (8-x) + (8-x) + x = 100.
x = 100- (24 + 7 + 5 + 13 + 32 + 8 + 8) = 100-97 = 3.
Zistili sme, že 3 študenti študujú súčasne tri jazyky: angličtinu, francúzštinu a nemčinu.
Takto bude vyzerať Euler-Vennov diagram, keď bude známe x:
Cieľ 2
Na matematickej olympiáde mali školákov vyriešiť tri úlohy: jednu z algebry, jednu z geometrie a jednu z trigonometrie. Olympiády sa zúčastnilo 1000 školákov. Výsledky olympiády boli nasledovné: úlohu z algebry riešilo 800 účastníkov, z geometrie - 700, z trigonometrie - 600. 600 žiakov riešilo úlohy z algebry a geometrie, 500 - z algebry a trigonometrie, 400 - z geometrie resp. trigonometria. 300 ľudí riešilo úlohy z algebry, geometrie a trigonometrie. Koľko školákov nevyriešilo ani jeden problém?
odpoveď: 100.
Riešenie:
Najprv definujeme množiny a zavedieme notáciu. Sú tri z nich:
- veľa problémov v algebre ("A");
- veľa problémov v geometrii ("G");
- veľa úloh v trigonometrii ("T").
Ukážme si, čo potrebujeme nájsť:
Určme počet študentov pre všetky možné oblasti.
Označme hľadanú oblasť A = 0, G = 0, T = 0 ako "x" (v tabuľke nižšie oblasť # 0).
Poďme nájsť zvyšok oblastí:
1) Oblasť A = 0, G = 0, T = 1: nie sú žiadni žiaci.
2) Oblasť A = 0, G = 1, T = 0: nie sú žiadni žiaci.
3) Plocha A = 0, G = 1, T = 1: 100 školákov.
4) Oblasť A = 1, G = 0, T = 0: nie sú žiadni žiaci.
5) Plocha A = 1, G = 0, T = 1: 200 školákov.
6) Plocha A = 1, G = 1, T = 0: 300 školákov.
7) Plocha A = 1, G = 1, T = 1: 300 školákov.
Zapíšme si hodnoty oblastí do tabuľky:
| № oblasti | A |
G |
T |
množstvo školákov |
|---|---|---|---|---|
| 0 | 0 |
0 |
0 |
X |
| 1 | 0 |
0 |
1 |
0 |
| 2 | 0 |
1 |
0 |
0 |
| 3 | 0 |
1 |
1 |
100 |
| 4 | 1 |
0 |
0 |
0 |
| 5 | 1 |
0 |
1 |
200 |
| 6 | 1 |
1 |
0 |
300 |
| 7 | 1 |
1 |
1 |
300 |
Nakreslite hodnoty pre všetky oblasti pomocou diagramu:
Definujme x:
x = U- (A V Г V Т), kde U-vesmír.
A V G V T = 0 + 0 + 0 + 300 + 300 + 200 + 100 = 900.
Dostali sme, že 100 školákov nevyriešilo ani jeden problém.
Cieľ 3
Na fyzikálnej olympiáde mali školákov vyriešiť tri úlohy: jednu z kinematiky, jednu z termodynamiky a jednu z optiky. Výsledky olympiády boli nasledovné: úlohu z kinematiky riešilo 400 účastníkov, z termodynamiky - 350, z optiky - 300. 300 školákov riešilo úlohy z kinematiky a termodynamiky, 200 - z kinematiky a optiky, 150 - z termodynamiky resp. optika. 100 ľudí riešilo úlohy z kinematiky, termodynamiky a optiky. Koľko študentov vyriešilo dve úlohy?
odpoveď: 350.
Riešenie:
Najprv definujeme množiny a zavedieme notáciu. Sú tri z nich:
- veľa problémov v kinematike ("K");
- veľa problémov v termodynamike ("T");
- veľa problémov v optike ("O").
Ukážme si pomocou Euler-Vennovho diagramu, čo nám dáva podmienka:
Ukážme si, čo potrebujeme nájsť:
Určme počet študentov pre všetky možné oblasti:
0) Oblasť K = 0, T = 0, O = 0: nedefinované.
1) Kraj K = 0, T = 0, O = 1: 50 školákov.
2) Región K = 0, T = 1, O = 0: nie sú žiadni žiaci.
3) Kraj K = 0, T = 1, O = 1: 50 školákov.
4) Región K = 1, T = 0, O = 0: nie sú žiadni žiaci.
5) Kraj K = 1, T = 0, O = 1: 100 školákov.
6) Kraj K = 1, T = 1, O = 0: 200 školákov.
7) Plocha K = 1, T = 1, O = 1: 100 školákov.
Zapíšme si hodnoty oblastí do tabuľky:
| № oblasti | TO |
T |
O |
množstvo školákov |
|---|---|---|---|---|
| 0 | 0 |
0 |
0 |
- |
| 1 | 0 |
0 |
1 |
50 |
| 2 | 0 |
1 |
0 |
0 |
| 3 | 0 |
1 |
1 |
50 |
| 4 | 1 |
0 |
0 |
0 |
| 5 | 1 |
0 |
1 |
100 |
| 6 | 1 |
1 |
0 |
200 |
| 7 | 1 |
1 |
1 |
100 |
Nakreslite hodnoty pre všetky oblasti pomocou diagramu:
Definujme x.
x = 200 + 100 + 50 = 350.
Dostali sme, 350 školákov riešilo dva problémy.
Úloha 4.
Medzi okoloidúcimi sa uskutočnil prieskum. Bola položená otázka: "Aký druh domáceho maznáčika máte?" Podľa výsledkov prieskumu sa ukázalo, že 150 ľudí má mačku, 130 psa a 50 vtáka. 60 ľudí má mačku a psa, 20 má mačku a vtáka, 30 má psa a vtáka. 70 ľudí vôbec nemá domáce zviera. 10 ľudí má mačku, psa a vtáka. Koľko okoloidúcich sa zúčastnilo prieskumu?
odpoveď: 300.
Riešenie:
Najprv definujeme množiny a zavedieme notáciu. Sú tri z nich:
- veľa ľudí, ktorí majú mačku ("K");
- veľa ľudí, ktorí majú psa ("C");
- veľa ľudí, ktorí majú vtáka ("P").
Ukážme si pomocou Euler-Vennovho diagramu, čo nám dáva podmienka:
Ukážme si, čo potrebujeme nájsť:
Poďme určiť počet ľudí pre všetky možné oblasti:
0) Plocha K = 0, S = 0, P = 0: 70 osôb.
1) Plocha K = 0, S = 0, P = 1: 10 osôb.
2) Plocha K = 0, S = 1, P = 0: 50 osôb.
3) Plocha K = 0, S = 1, P = 1: 20 osôb.
4) Plocha K = 1, S = 0, P = 0: 80 osôb.
5) Plocha K = 1, T = 0, O = 1: 10 osôb.
6) Plocha K = 1, T = 1, O = 0: 50 osôb.
7) Plocha K = 1, T = 1, O = 1: 10 osôb.
Zapíšme si hodnoty oblastí do tabuľky:
| № oblasti | TO |
C |
P |
množstvo Ľudské |
|---|---|---|---|---|
| 0 | 0 |
0 |
0 |
70 |
| 1 | 0 |
0 |
1 |
10 |
| 2 | 0 |
1 |
0 |
50 |
| 3 | 0 |
1 |
1 |
20 |
| 4 | 1 |
0 |
0 |
80 |
| 5 | 1 |
0 |
1 |
10 |
| 6 | 1 |
1 |
0 |
50 |
| 7 | 1 |
1 |
1 |
10 |
Nakreslite hodnoty pre všetky oblasti pomocou diagramu:
Definujme x:
x = U (vesmír)
U = 70 + 10 + 50 + 20 + 80 + 10 + 50 + 10 = 300.
Do prieskumu sa zapojilo 300 ľudí.
Úloha 5.
Na jednu z univerzít bolo zapísaných 120 ľudí. Uchádzači robili tri skúšky: z matematiky, z informatiky a z ruského jazyka. Matematiku prospelo 60 ľudí, informatiku 40. Matematiku a informatiku prospelo 30 uchádzačov, matematiku a ruštinu 30, informatiku a ruštinu 25. Všetky tri skúšky zvládlo 20 ľudí, neúspešne 50 ľudí. Koľko uchádzačov absolvovalo ruský jazyk?
Na vizuálnu reprezentáciu množín sa používajú Eulerove - Vennove diagramy (pomenované podľa matematikov Leonarda Eulera (1707–1783) a Johna Venna (1834–1923)). Súpravy sú označené plochami na rovine a prvky súpravy sú konvenčne umiestnené vo vnútri týchto plôch. Všetky množiny v diagrame sú často umiestnené vo vnútri obdĺžnika, ktorý predstavuje univerzálnu množinu. Ak prvok patrí do viac ako jednej množiny, potom sa oblasti zodpovedajúce takýmto množinám musia prekrývať, aby spoločný prvok mohol byť súčasne v zodpovedajúcich oblastiach. Výber tvaru oblastí reprezentujúcich množiny v diagramoch môže byť ľubovoľný (kruhy, mnohouholníky atď.).
napríklad Pomocou Eulerových - Vennových diagramov je možné ukázať, že množina je podmnožinou množiny (obr. 3).
Ukážme si operácie na množinách uvedené vyššie pomocou Eulerových - Vennových diagramov: a) spojenie množín a; b) priesečník súpravy; c) rozdiel množiny (bez); d) doplnok zostavy k univerzálnej zostave (obr. 4, a, b, v, G).
Príklad 1 Dokážte identitu pomocou Eulerových - Vennových diagramov.
Riešenie
Zostrojme doplnok množiny k univerzálnej množine (obr. 5, a). Sada zodpovedá vyplnenej ploche (obr. 5, b). Je teda vidieť, že na Eulerových - Vennových diagramoch sú množiny a sú zobrazené rovnakým spôsobom.
Príklad 2 Ukáž to.
Riešenie
Zostavme množinu zodpovedajúcu ľavej strane danej identity. Súbor predstavuje vyplnená oblasť na obr. 6, a... Sada zodpovedá šrafovanej oblasti na obr. 6, b.
Sada zobrazuje oblasť vyplnenú v oboch predchádzajúcich diagramoch, preto je znázornená na obr. 6, v tmavšia oblasť.
Zostrojme množinu zodpovedajúcu pravej strane danej identity.
Množiny a sú znázornené vyplnenou oblasťou na obr. 7, a a 7, b resp.
Zostava je znázornená vyplnenou oblasťou na obr. 7, v.
Porovnanie Obr. 6, v a obr. 7, v, vidíme, že na Eulerových - Vennových diagramoch sú znázornené rovnakým spôsobom.
Otázky a úlohy na samostatné riešenie
1. Nakreslite množiny pomocou Euler-Vennových diagramov:
2. Popíšte zostavy zodpovedajúce vyplneným dielom na obr. osem, a, b, v, G pomocou Eulerových - Vennových diagramov:
3. Pomocou Euler-Vennových diagramov ukážte, že:
1.4. Vlastnosti operácií na množinách
Vyššie predstavené množinové operácie majú nasledujúce vlastnosti.
1. - zameniteľnosť.
2.
- asociatívnosť.
3.
- distribúcia.
4. - idempotencia.
5.
- zákony identity.
6. ,, - dopĺňajú zákony.
7. - de Morganove zákony.
8. - zákony absorpcie.
9.
- zákony lepenia.
10.
- zákony Poretského.
Príklad 1 Zjednodušte výraz na základe vlastností množinových operácií.
Riešenie
= / de Morganov zákon / =
= = / zákon distributivity / =
= = / zákon komutativnosti / =
= = / zákon distributivity / =
/ komutatívny zákon / =
/ dopĺňajú zákony / =
= / zákony komutácie a identity / =
= = / definícia symetrického rozdielu / =.
Ako už bolo spomenuté, mohutnosťou konečnej množiny je počet jej prvkov. Nasledujúca veta poskytuje jednoduché pravidlo na výpočet mohutnosti spojenia dvoch množín.
Veta o inklúzii a vylúčení. Mohutnosť spojenia dvoch množín sa rovná rozdielu medzi súčtom mohutností týchto množín a mohutnosťou ich priesečníka, t.j.
Dôkaz
Najvhodnejšie je znázorniť dôkaz tvrdenia graficky. Ako je znázornené na obr. 9, množina pozostáva z podmnožín: a ktoré nemajú žiadne spoločné prvky. V dôsledku toho a.
Predstavme si notáciu:
Q.E.D.
Príklad 2 Doplnkové prednášky môže absolvovať každý zo 63 študentov prvého ročníka študujúcich informatiku na univerzite. Ak 16 z nich ešte navštevuje kurz účtovníctva, 37 kurz podnikania a 5 študuje oba tieto odbory, tak koľko študentov tieto doplnkové kurzy vôbec nenavštevuje?
Riešenie
Predstavme si notáciu:
V dôsledku toho - počet študentov, ktorí nenavštevujú ďalšie kurzy.
Poznámka 1. Veta o inklúziách a vylúčeniach môže byť formulovaná pre prípad troch množín:
Príklad 3 Do kurzu je zapísaných 42 študentov. Z toho 16 pôsobí v atletickom oddiele, 24 vo futbalovom oddiele, 15 v šachovom oddiele, 11 v atletickom aj futbalovom oddiele; 8 - ako v atletike, tak aj v šachu; 12 - vo futbale aj v šachu; a 6 vo všetkých troch častiach. Zvyšok študentov sa zaujíma o cestovný ruch. Koľko študentov je turistov?
Riešenie
Predstavme si notáciu:
Z výpisu problému: ,,,,,, a.
Kde, teda počet študentov zapojených do cestovného ruchu.
Poznámka 2. Pri riešení vyššie uvedených problémov je vhodné použiť Euler - Vennove diagramy.
Úlohy na samostatné riešenie
Dokážte identity pomocou vlastností množín operácií:
2. Do jedálne prišlo na obed 33 ľudí. 10 osôb si objednalo polievku, 16 - pilaf, 30 - kompót, všetky tri jedlá si objednalo 7 osôb, polievku a pilaf - 8 osôb, polievku a kompót - 14 osôb. Koľko ľudí si objednalo pilaf a kompót?
3. V študentskej skupine študuje 12 ľudí anglický jazyk, 13 - nemecký jazyk, 16 - francúzsky jazyk, 4 - iba anglický a nemecký jazyk, 3 - iba anglický a francúzsky jazyk, 5 - všetky tri jazyky. V skupine nie sú žiadni študenti iba v angličtine. Dvaja ľudia sa učia iba nemčinu, šesť ľudí iba francúzštinu. Jeden študent v skupine sa neučí žiadny z uvedených jazykov. Koľko študentov je v skupine?
Ľudské myslenie je navrhnuté tak, že svet je reprezentovaný ako pozostávajúci z oddelených „objektov“. Filozofi už dávno vedia, že svet je jeden nerozlučiteľný celok a výber predmetov v ňom nie je nič iné ako svojvoľný akt nášho myslenia, ktorý nám umožňuje vytvoriť si obraz prístupný racionálnej analýze. Ale nech je to akokoľvek, výber predmetov a ich agregátov je prirodzený spôsob organizácie nášho myslenia, a tak neprekvapuje, že je základom hlavného nástroja na opis exaktných poznatkov – matematiky.
Pojem množina patrí k základným nedefinovaným pojmom matematiky. Je známe, že súbor je prinajmenšom zložený z prvkov. Pre istotu akceptujeme nasledujúce formulácie.
Definícia... Pod súpravou S budeme rozumieť každej zbierke určitých a rozlíšiteľných predmetov, mysliteľných ako celok. Tieto objekty sa nazývajú prvky množiny S.
Definícia... Množinou sa rozumie zjednotenie určitých úplne rozlíšiteľných predmetov (objektov) do jedného celku, ktoré sa potom nazývajú prvky nimi tvoreného súboru.
Sady sa zvyčajne označujú veľkými písmenami latinskej abecedy: A, B, C, ...; a prvky množín sa píšu malými písmenami: a, b, c, … .
Ak je objekt X je súčasťou súpravy M potom to hovoria X patrí M: HM... Inak sa to hovorí X nepatrí M: HM.
V tejto intuitívnej definícii, ktorá patrí nemeckému matematikovi G. Cantorovi, je podstatná skutočnosť, že súbor predmetov je sám o sebe považovaný za jeden objekt, chápaný ako celok. Čo sa týka samotných predmetov, ktoré je možné zaradiť do zostavy, existuje pri nich značná voľnosť.
Príklad 1
Môže to byť veľa vysokoškolákov, veľa prvočísel atď.
Definícia... Kopa A sa nazýva podmnožina množiny V ak každý prvok z A je prvkom V(označiť). Ak A je podmnožinou V a V nie je podmnožinou A potom to hovoria A je prísna (správna) podmnožina V(označiť).
Definícia... Množina, ktorá neobsahuje prvky, sa nazýva prázdna (označuje sa Æ), je podmnožinou ľubovoľnej množiny. Kopa U sa nazýva univerzálna, to znamená, že všetky uvažované množiny sú jej podmnožinou.
Zvážte dve definície rovnosti množín.
Definícia... Súpravy A a V sa považujú za rovnocenné, ak pozostávajú z rovnakých prvkov, píšu A = B, inak A¹ V.
Definícia... Súpravy A a V sa považujú za rovnaké, ak 
Sú nasledujúce spôsoby definovania množín :
1) vymenovaním prvkov: M = (a 1 , a 2 , …, a k} , to znamená zoznam jeho prvkov;
2) charakteristický predikát: M = (X | P(X)} (opis charakteristických vlastností, ktoré musia mať jeho prvky);
generatívny postup: M = { X | X= f} , ktorý popisuje, ako získať prvky množiny z už prijatých prvkov alebo iných objektov. V tomto prípade sú prvkami súboru všetky objekty, ktoré môžu byť
1) boli skonštruované pomocou tohto postupu. Napríklad množina všetkých celých čísel, ktoré sú mocninou dvoch.
Komentujte... Pri špecifikovaní množín pomocou enumerácie sú označenia prvkov zvyčajne uzavreté v zložených zátvorkách a oddelené čiarkami. Enumeráciou možno špecifikovať iba konečné množiny (počet prvkov množiny je konečný, inak sa množina nazýva nekonečná). Charakteristický predikát je nejaká podmienka vyjadrená vo forme boolovského príkazu alebo procedúry, ktorá vracia boolovskú hodnotu. Ak je podmienka pre daný prvok splnená, potom patrí do definovanej množiny, inak nepatrí. Procedúra spawnovania je procedúra, ktorá po spustení vytvorí niektoré objekty, ktoré sú členmi definovanej množiny. Nekonečné množiny sú dané charakteristickým predikátom alebo generatívnym postupom.
Príklad 2
1) M = (1, 2, 3, 4)- vymenovanie prvkov súboru.
2) je charakteristický predikát.
Definícia... Mohutnosť konečnej množiny A Je počet jeho prvkov.
Mohutnosť množiny sa označuje: | A|.
Príklad 3
|| = 0; |{}| = 1.
Definícia... Množiny sa nazývajú ekvipotentné, ak sa ich mohutnosti zhodujú.
Definícia... Množina všetkých podmnožín množiny A sa nazýva booleovská P (A).
Je známe, že ak je súbor A obsahuje n prvky, potom súbor P(A) obsahuje 2 n prvkov. V tomto ohľade používame aj označenie pre stupeň množiny A ako 2 A.
Príklad 4
A = (0, 1, 2),P(A) = { , {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}} .
Geometricky môžu byť množiny reprezentované pomocou Euler-Vennových diagramov. Konštrukcia diagramu spočíva v obrázku veľkého obdĺžnika reprezentujúceho univerzálnu množinu U a vo vnútri - kruhy (alebo iné uzavreté postavy), ktoré predstavujú sady. Tvary sa musia pretínať najvšeobecnejším spôsobom, ktorý si vyžaduje úloha, a musia byť podľa toho označené. Body ležiace v rôznych oblastiach diagramu možno považovať za prvky zodpovedajúcich množín. Po vytvorení diagramu je možné zatieniť určité oblasti na označenie novovytvorených množín.
Operácie na súpravách sa považujú za získanie nových súprav z existujúcich súprav.
Definícia... Spojenie množín A a V sa nazýva množina pozostávajúca zo všetkých tých prvkov, ktoré patria aspoň do jednej z množín A,V(obr. 1.1):
Ryža. 1.1. Euler-Vennov diagram pre spojenie
Definícia... Priesečník množín A a V sa nazýva množina pozostávajúca zo všetkých a len tých prvkov, ktoré patria súčasne ako množina A a mnoho V(obr. 1.2):
Ryža. 1.2. Euler-Vennov diagram pre križovatku
Definícia... Rozdiel súprav A a V nazývaný súbor všetkých tých a len tých prvkov A ktoré nie sú obsiahnuté v V(obr. 1.3):
Ryža. 1.3. Euler-Vennov diagram pre rozdiel
Definícia... Symetrický rozdiel množín A a V sa nazýva množina prvkov týchto množín, ktoré buď patria iba do množiny A, alebo iba súpravu V(obr. 1.4):
Ryža. 1.4. Euler-Vennov diagram pre symetrický rozdiel
Definícia... Absolútny doplnok setu A nazývaná množina všetkých tých prvkov, ktoré do množiny nepatria A(obr. 1.5):
Ryža. 1.5. Eulerov-Vennov diagram pre absolútny doplnok
Príklad 5
Pomocou Euler-Vennových diagramov dokážeme identitu:
Zvážte ľavú stranu pomeru a vykonajte akcie v poradí:
1) nájdite priesečník množín V a S() (obr. 1.6, a);
2) nájdite spojenie výslednej množiny s množinou A() (obr. 1.6, b).
Zvážte pravú stranu vzťahu 
:
1) nájdite spojenie množín A a V(obr. 1.6, c);
2) nájdite spojenie množín A a S(ryža.
1,6, d);
3) nájdite priesečník posledných dvoch množín a ( ) (obr. 6, e):
V oboch prípadoch (obr. 1.6, b) a (obr. 1.6, e) získame rovnaké súbory. Preto je pôvodný vzťah správny.
Ryža. 1.6. Dôkaz totožnosti pomocou Euler-Vennových diagramov
Uvažujme o základných identitách algebry množín. Pre ľubovoľné zostavy A,V a S nasledujúce vzťahy sú pravdivé (tabuľka 1.11):
Tabuľka 1.11 Základné identity algebry množín
|
Združenie |
Prechod |
|
1. Komutivita zväzku |
jeden'. Priesečníková komutivita |
|
2. Asociatívnosť |
2'. Priesečníková asociativita |
|
3. Distribúcia zväzku vzhľadom na priesečník |
3'. Distribúcia priesečníka vo vzťahu k spojeniu |
|
4. Zákony pôsobenia s prázdnymi a univerzálnymi množinami |
4'. Zákony pôsobenia s prázdnymi a univerzálnymi množinami |
|
5. Zákon o idempotencii združovania |
5'. Zákon idempotencie priesečníka |
|
6. De Morganov zákon |
6'. De morganov zákon |
|
7. Zákon absorpcie
|
7'. Absorpčný zákon
|
|
8. Zákon lepenia
|
osem'. Zákon o viazaní
|
|
9. Poretského zákon
|
9'. Poretského zákon
|
|
10. Zákon dvojitého doplnku |
|
