Podobne dokumenty
Rekonstrukcja grafów z podanych macierzy sąsiedztwa wierzchołków. Konstrukcja macierzy sąsiedztwa krawędzi, padania, osiągalności, kontrosiągalności dla każdego grafu. Wyszukaj kompozycję wykresów. Wyznaczanie lokalnych stopni wierzchołków grafów. Wyszukaj bazę wykresów.
praca laboratoryjna, dodano 01/09/2009
Opis danego grafu zbiorami wierzchołków V i łuków X, listami sąsiedztwa, macierzą częstości i sąsiedztwa. Macierz wag odpowiedniego wykresu nieskierowanego. Wyznaczanie drzewa najkrótszej ścieżki za pomocą algorytmu Dijkstry. Znajdowanie drzew na wykresie.
praca semestralna, dodana 30.09.2014
Pojęcie „grafu” i jego reprezentacja macierzowa. Własności macierzy sąsiedztwa i zapadalności. Właściwości tras, łańcuchów i pętli. Problem znajdowania wierzchołków centralnych grafu, jego charakterystyk metrycznych. Zastosowanie teorii grafów w dziedzinach nauki i techniki.
praca semestralna, dodana 05.09.2015
Algorytm przejścia do graficznej reprezentacji grafu nieskierowanego. Liczba wierzchołków w grafie nieskierowanym. Czytanie z macierzy sąsiedztwa. Połączenia między wierzchołkami w macierzy. Ustawienie współrzędnych wierzchołków w zależności od ilości sektorów.
praca laboratoryjna, dodano 29.04.2011
Opis matematyczny układu automatyki za pomocą wykresów. Sporządzanie wykresu i przekształcanie go, pozbycie się różniczek. Optymalizacja grafów skierowanych i nieskierowanych, kompilacja macierzy sąsiedztwa i incydentów.
praca laboratoryjna, dodano 11.03.2012
Grafy skierowane i nieskierowane: charakterystyka ogólna, wierzchołki i krawędzie specjalne, półstopnie wierzchołków, sąsiedztwo, incydencja, osiągalność, macierze łączności. Charakterystyki numeryczne każdego wykresu, przechodzenie w głąb i wszerz, podstawa cykli.
praca semestralna, dodana 14.05.2012
Sprawdzanie poprawności tożsamości lub wtrąceń za pomocą algebry zbiorów i diagramów Eulera-Venna. Obraz wykresu i macierzy relacji o własnościach refleksyjności, przechodniości i antysymetrii. Badanie grafu nieskierowanego.
test, dodano 05.05.2013
Zbiór odnosi się do zbioru elementów połączonych jakimś atrybutem. Operacje są definiowane na zbiorach, które pod wieloma względami przypominają arytmetykę. Operacje na zbiorach są interpretowane geometrycznie za pomocą diagramów Eulera-Venna.
streszczenie, dodane 02.03.2009
Konstrukcja pseudografu, macierz incydencji i macierz sąsiedztwa wierzchołków. Odtwarzanie drzewa z wektora przy użyciu algorytmu Prüfera. Budowanie tabeli prawdy dla funkcji i doskonałych spójnych i rozłącznych form normalnych.
test, dodano 25.09.2013
Metody rozwiązywania problemów matematyki dyskretnej. Obliczanie najkrótszej drogi między parami wszystkich wierzchołków w grafach skierowanych i nieskierowanych z wykorzystaniem algorytmu Floyda. Analiza problemu i metody jego rozwiązania. Rozwój i charakterystyka programu.
Niektóre problemy można wygodnie i przejrzyście rozwiązać za pomocą diagramów Eulera-Venna. Na przykład ustaw zadania. Jeśli nie wiesz, czym są diagramy Eulera-Venna i jak je zbudować, przeczytaj najpierw.
Przyjrzyjmy się teraz typowym zestawom problemów.
Cel 1.
W szkole z pogłębioną nauką języków obcych przeprowadzono ankietę wśród 100 uczniów. Uczniom zadano pytanie: „Jakich języków obcych się uczysz?” Okazało się, że 48 studentów uczy się angielskiego, 26 - francuskiego, 28 - niemieckiego. 8 uczniów uczy się angielskiego i niemieckiego, 8 - angielskiego i francuskiego, 13 - francuskiego i niemieckiego. 24 uczniów nie uczy się angielskiego, francuskiego ani niemieckiego. Ilu z badanych uczniów uczy się jednocześnie trzech języków: angielskiego, francuskiego i niemieckiego?
Odpowiedź: 3.
Rozwiązanie:
- wielu uczniów uczących się angielskiego („A”);
- wielu uczniów uczących się francuskiego („F”);
- wielu uczniów uczących się niemieckiego („H”).
Zobrazujmy za pomocą diagramu Eulera-Venna, co jest nam dane przez warunek.
Wyznaczmy wymagany obszar A = 1, Ф = 1, Н = 1 jako „x” (w tabeli poniżej obszar 7). Wyraźmy pozostałe obszary w postaci x.
0) Obszar A = 0, F = 0, H = 0: 24 uczniów - podane według opisu problemu.
1) Obszar A = 0, F = 0, H = 1: 28- (8-x + x + 13-x) = 7 + x uczniów.
2) Obszar A = 0, F = 1, H = 0: 26- (8-x + x + 13-x) = 5 + x uczniów.
3) Obszar A = 0, F = 1, H = 1: 13 uczniów.
4) Obszar A = 1, F = 0, H = 0: 48- (8-x + x + 8-x) = 32 + x uczniów.
5) Obszar A = 1, F = 0, H = 1: 8 uczniów.
6) Obszar A = 1, F = 1, H = 0: 8 uczniów.
| № obszary | A |
F |
n |
Ilość uczniowie |
|---|---|---|---|---|
| 0 | 0 |
0 |
0 |
24 |
| 1 | 0 |
0 |
1 |
7 + x |
| 2 | 0 |
1 |
0 |
5 + x |
| 3 | 0 |
1 |
1 |
13th |
| 4 | 1 |
0 |
0 |
32 + x |
| 5 | 1 |
0 |
1 |
ósmy |
| 6 | 1 |
1 |
0 |
ósmy |
| 7 | 1 |
1 |
1 |
x |
Zdefiniujmy 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.
Doszło do tego, że 3 uczniów uczy się jednocześnie trzech języków: angielskiego, francuskiego i niemieckiego.
Tak będzie wyglądał diagram Eulera-Venna, gdy znane jest x:
Cel 2.
Na Olimpiadzie Matematycznej uczniowie zostali poproszeni o rozwiązanie trzech problemów: jednego z algebry, jednego z geometrii, jednego z trygonometrii. W olimpiadzie wzięło udział 1000 uczniów. Wyniki Olimpiady były następujące: zadanie z algebry rozwiązało 800 uczestników, z geometrii – 700, z trygonometrii – 600. 600 uczniów rozwiązało zadania z algebry i geometrii, 500 – z algebry i trygonometrii, 400 – z geometrii i trygonometria. 300 osób rozwiązywało zadania z algebry, geometrii i trygonometrii. Ile dzieci w wieku szkolnym nie rozwiązało ani jednego problemu?
Odpowiedź: 100.
Rozwiązanie:
Najpierw definiujemy zbiory i wprowadzamy notację. Są trzy z nich:
- wiele problemów w algebrze ("A");
- wiele problemów w geometrii („G”);
- wiele zadań w trygonometrii ("T").
Zobrazujmy, co musimy znaleźć:
Określmy liczbę uczniów dla wszystkich możliwych obszarów.
Oznaczmy poszukiwany obszar A = 0, G = 0, T = 0 jako „x” (w tabeli poniżej obszar nr 0).
Znajdźmy pozostałe obszary:
1) Obszar A = 0, G = 0, T = 1: nie ma uczniów.
2) Obszar A = 0, G = 1, T = 0: nie ma uczniów.
3) Obszar A = 0, G = 1, T = 1: 100 uczniów.
4) Obszar A = 1, G = 0, T = 0: nie ma uczniów.
5) Obszar A = 1, G = 0, T = 1: 200 uczniów.
6) Obszar A = 1, G = 1, T = 0: 300 uczniów.
7) Obszar A = 1, G = 1, T = 1: 300 uczniów.
Zapiszmy wartości obszarów do tabeli:
| № obszary | A |
g |
T |
Ilość uczniowie |
|---|---|---|---|---|
| 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 |
Wykreślmy wartości dla wszystkich obszarów za pomocą diagramu:
Zdefiniujmy x:
x = U- (A V Г V Т), gdzie U-wszechświat.
A V G V T = 0 + 0 + 0 + 300 + 300 + 200 + 100 = 900.
Doszliśmy do wniosku, że 100 uczniów nie rozwiązało żadnego problemu.
Cel 3.
Na Olimpiadzie Fizycznej uczniowie zostali poproszeni o rozwiązanie trzech problemów: jednego z kinematyki, jednego z termodynamiki i jednego z optyki. Wyniki Olimpiady były następujące: zadanie z kinematyki rozwiązało 400 uczestników, z termodynamiki - 350, z optyki - 300. 300 uczniów rozwiązywało zadania z kinematyki i termodynamiki, 200 - z kinematyki i optyki, 150 - z termodynamiki i optyka. 100 osób rozwiązywało zadania z kinematyki, termodynamiki i optyki. Ilu uczniów rozwiązało dwa problemy?
Odpowiedź: 350.
Rozwiązanie:
Najpierw definiujemy zbiory i wprowadzamy notację. Są trzy z nich:
- wiele problemów w kinematyce ("K");
- wiele problemów w termodynamice („T”);
- wiele problemów w optyce ("O").
Za pomocą diagramu Eulera-Venna zobrazujmy, co daje nam warunek:
Zobrazujmy, co musimy znaleźć:
Określmy liczbę uczniów dla wszystkich możliwych obszarów:
0) Region K = 0, T = 0, O = 0: niezdefiniowany.
1) Region K = 0, T = 0, O = 1: 50 uczniów.
2) Region K = 0, T = 1, O = 0: nie ma uczniów.
3) Region K = 0, T = 1, O = 1: 50 uczniów.
4) Region K = 1, T = 0, O = 0: nie ma uczniów.
5) Region K = 1, T = 0, O = 1: 100 uczniów.
6) Region K = 1, T = 1, O = 0: 200 uczniów.
7) Obszar K = 1, T = 1, O = 1: 100 uczniów.
Zapiszmy wartości obszarów do tabeli:
| № obszary | DO |
T |
O |
Ilość uczniowie |
|---|---|---|---|---|
| 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 |
Wykreślmy wartości dla wszystkich obszarów za pomocą diagramu:
Zdefiniujmy x.
x = 200 + 100 + 50 = 350.
Udało nam się, 350 uczniów rozwiązało dwa problemy.
Zadanie 4.
Przeprowadzono ankietę wśród przechodniów. Zadano pytanie: „Jakiego rodzaju zwierzaka masz?” Zgodnie z wynikami ankiety okazało się, że 150 osób ma kota, 130 psa, a 50 ptaka. 60 osób ma kota i psa, 20 ma kota i ptaka, 30 ma psa i ptaka. 70 osób w ogóle nie ma zwierzaka. 10 osób ma kota, psa i ptaka. Ilu przechodniów wzięło udział w ankiecie?
Odpowiedź: 300.
Rozwiązanie:
Najpierw definiujemy zbiory i wprowadzamy notację. Są trzy z nich:
- wiele osób, które mają kota („K”);
- wiele osób, które mają psa („C”);
- wielu ludzi, którzy mają ptaka ("P").
Za pomocą diagramu Eulera-Venna zobrazujmy, co daje nam warunek:
Zobrazujmy, co musimy znaleźć:
Określmy liczbę osób dla wszystkich możliwych obszarów:
0) Obszar K = 0, S = 0, P = 0: 70 osób.
1) Obszar K = 0, S = 0, P = 1:10 osób.
2) Obszar K = 0, S = 1, P = 0: 50 osób.
3) Obszar K = 0, S = 1, P = 1:20 osób.
4) Obszar K = 1, S = 0, P = 0: 80 osób.
5) Obszar K = 1, T = 0, O = 1: 10 osób.
6) Obszar K = 1, T = 1, O = 0: 50 osób.
7) Obszar K = 1, T = 1, O = 1:10 osób.
Zapiszmy wartości obszarów do tabeli:
| № obszary | DO |
C |
P |
Ilość Człowiek |
|---|---|---|---|---|
| 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 |
Wykreślmy wartości dla wszystkich obszarów za pomocą diagramu:
Zdefiniujmy x:
x = U (wszechświat)
U = 70 + 10 + 50 + 20 + 80 + 10 + 50 + 10 = 300.
300 osób wzięło udział w ankiecie.
Zadanie 5.
Na jedną specjalność na jednej z uczelni przyjęto 120 osób. Wnioskodawcy zdali trzy egzaminy: z matematyki, informatyki i języka rosyjskiego. Matematykę zdało 60 osób, informatykę 40. Matematykę i informatykę zdało 30 osób, matematykę i język rosyjski 30, informatykę i język rosyjski 25. 20 osób zdało wszystkie trzy egzaminy, a 50 osób oblało. Ilu kandydatów zdało język rosyjski?
Do wizualnej reprezentacji zbiorów używa się diagramów Eulera - Venna (nazwanych na cześć matematyków Leonarda Eulera (1707-1783) i Johna Venna (1834-1923)). Zestawy wyznaczane są obszarami na płaszczyźnie, a elementy zestawu umownie umieszczane są wewnątrz tych obszarów. Często wszystkie zestawy na diagramie są umieszczane wewnątrz prostokąta, który reprezentuje zestaw uniwersalny. Jeżeli element należy do więcej niż jednego zbioru, wówczas regiony odpowiadające takim zbiorom muszą zachodzić na siebie, aby wspólny element mógł jednocześnie znajdować się w odpowiednich regionach. Wybór kształtu regionów reprezentujących zbiory na diagramach może być dowolny (okręgi, wielokąty itp.).
na przykład, korzystając z diagramów Eulera - Venna, można pokazać, że zbiór jest podzbiorem zbioru (rys. 3).
Zilustrujmy powyższe operacje na zbiorach za pomocą diagramów Eulera - Venna: a) suma zbiorów i; b) przecięcie zbioru; c) różnica zestawu (bez); d) uzupełnienie zestawu do zestawu uniwersalnego (rys. 4, a, b, v, g).
Przykład 1. Udowodnij tożsamość za pomocą diagramów Eulera - Venna.
Rozwiązanie
Skonstruujmy dopełnienie zbioru do zbioru uniwersalnego (rys. 5, a). Zestaw odpowiada wypełnionej powierzchni (rys. 5, b). Widać zatem, że na diagramach Eulera - Venna zbiory i są przedstawione w ten sam sposób, a więc.
Przykład 2. Pokazują, że.
Rozwiązanie
Skonstruujmy zbiór odpowiadający lewej stronie danej tożsamości. Zbiór jest reprezentowany przez wypełniony obszar na ryc. 6, a... Zestaw odpowiada zacienionemu obszarowi na ryc. 6, b.
Zestaw przedstawia obszar wypełniony na obu poprzednich wykresach, dlatego pokazano go na rys. 6, v ciemniejszy obszar.
Skonstruujmy zbiór odpowiadający prawej stronie danej tożsamości.
Zbiory i są reprezentowane przez wypełniony obszar na ryc. 7, a i 7, b odpowiednio.
Zestaw przedstawia wypełniony obszar na ryc. 7, v.
Porównanie ryc. 6, v i ryc. 7, v widzimy więc, że są one przedstawione w ten sam sposób na diagramach Eulera-Venna.
Pytania i zadania do samodzielnego rozwiązania
1. Narysuj zbiory za pomocą diagramów Eulera-Venna:
2. Opisz zestawy odpowiadające wypełnionym częściom na ryc. osiem, a, b, v, g, używając diagramów Eulera - Venna:
3. Użyj diagramów Eulera-Venna, aby pokazać, że:
1.4. Własności operacji na zbiorach
Wprowadzone powyżej operacje na zestawach mają następujące właściwości.
1. - przemienność.
2.
- stowarzyszenie.
3.
- dystrybucyjność.
4. - idempotencja.
5.
- prawa tożsamości.
6. ,, - uzupełniają ustawy.
7. - prawa de Morgana.
8. - prawa absorpcji.
9.
- prawa klejenia.
10.
- prawa Poreckiego.
Przykład 1. Uprość wyrażenie na podstawie właściwości operacji na zestawach.
Rozwiązanie
= / prawo de Morgana / =
= = / prawo dystrybucji / =
= = / prawo przemienności / =
= = / prawo dystrybucji / =
/ prawo przemienne / =
/ prawa uzupełniające / =
= / prawa przemienności i tożsamości / =
= = / definicja różnicy symetrycznej / =.
Jak już wspomniano, licznością zbioru skończonego jest liczba jego elementów. Poniższe twierdzenie podaje prostą zasadę obliczania liczności sumy dwóch zbiorów.
Twierdzenie o włączeniu i wyłączeniu. Moc sumy dwóch zbiorów jest równa różnicy między sumą mocy tych zbiorów a mocą ich przecięcia, tj.
Dowód
Najwygodniej jest zilustrować dowód oświadczenia graficznie. Jak pokazano na ryc. 9, zbiór składa się z podzbiorów: i które nie mają wspólnych elementów. W konsekwencji, i.
Wprowadźmy notację:
co było do okazania
Przykład 2. Każdy z 63 studentów I roku studiów informatycznych na uczelni może uczęszczać na dodatkowe zajęcia. Jeśli 16 z nich nadal studiuje rachunkowość, 37 - biznesowy, a 5 studiuje obie te dyscypliny, to ilu studentów w ogóle nie uczęszcza na te dodatkowe zajęcia?
Rozwiązanie
Wprowadźmy notację:
W konsekwencji - liczba studentów, którzy nie uczęszczają na dodatkowe zajęcia.
Uwaga 1. Twierdzenie o inkluzjach i wykluczeniach można sformułować dla przypadku trzech zbiorów:
Przykład 3. Na kurs zapisało się 42 studentów. Spośród nich 16 jest zaangażowanych w sekcję lekkoatletyczną, 24 w sekcji piłki nożnej, 15 w sekcji szachów, 11 w sekcji lekkoatletycznej i piłki nożnej; 8 - zarówno w lekkoatletyce, jak iw szachach; 12 - zarówno w piłce nożnej, jak iw szachach; i 6 we wszystkich trzech sekcjach. Reszta studentów interesuje się turystyką. Ilu studentów to turyści?
Rozwiązanie
Wprowadźmy notację:
Z opisu problemu: ,,,,, i.
Gdzie, czyli liczba studentów zajmujących się turystyką.
Uwaga 2. Przy rozwiązywaniu powyższych problemów wygodnie jest korzystać z diagramów Eulera - Venna.
Zadania do samodzielnego rozwiązania
Udowodnij tożsamości za pomocą właściwości operacji na zbiorze:
2. Na obiad do jadalni przyszły 33 osoby. 10 osób zamówiło zupę, 16 - pilaw, 30 - kompot, wszystkie trzy dania zamawiało 7 osób, zupa i pilaw - 8 osób, zupa i kompot - 14 osób. Ile osób zamówiło pilaw i kompot?
3. W grupie studenckiej 12 osób uczy się angielskiego, 13 - niemieckiego, 16 - francuskiego, 4 - tylko angielskiego i niemieckiego, 3 - tylko angielskiego i francuskiego, 5 - wszystkich trzech języków. W grupie nie ma studentów tylko po angielsku. Dwie osoby uczą się tylko niemieckiego, sześć osób uczy się tylko francuskiego. Jeden uczeń w grupie nie uczy się żadnego z wymienionych języków. Ilu uczniów jest w grupie?
Myślenie ludzkie jest zaprojektowane w taki sposób, że świat jest przedstawiany jako składający się z oddzielnych „obiektów”. Filozofowie od dawna wiedzieli, że świat jest jedną nierozerwalną całością, a dobór w nim przedmiotów jest niczym innym jak arbitralnym aktem naszego myślenia, który pozwala nam stworzyć obraz dostępny dla racjonalnej analizy. Tak czy inaczej, selekcja obiektów i ich agregatów jest naturalnym sposobem organizowania naszego myślenia, nic więc dziwnego, że leży u podstaw głównego narzędzia opisu wiedzy dokładnej - matematyki.
Pojęcie zbioru należy do podstawowych niezdefiniowanych pojęć matematyki. Wiadomo, że zbiór składa się przynajmniej z elementów. Dla jednoznaczności przyjmiemy następujące sformułowania.
Definicja... Pod zestawem S zrozumiemy każdy zbiór określonych i rozróżnialnych przedmiotów, które można sobie wyobrazić jako całość. Obiekty te nazywane są elementami zbioru S.
Definicja... Zbiór rozumiany jest jako zjednoczenie w jedną całość pewnych całkowicie rozróżnialnych przedmiotów (przedmiotów), które następnie nazywamy elementami utworzonego przez nie zbioru.
Zazwyczaj zestawy są oznaczane wielkimi literami alfabetu łacińskiego: A, b, C, ...; a elementy zestawów pisane są małymi literami: a, b, C, … .
Jeśli obiekt x jest częścią zestawu m wtedy mówią, że x należy m: HM... W przeciwnym razie mówi się, że x nie należy m: HM.
W tej intuicyjnej definicji, należącej do niemieckiego matematyka G. Cantora, istotne jest to, że zbiór przedmiotów sam w sobie jest uważany za jeden przedmiot, rozumiany jako całość. Jeśli chodzi o same przedmioty, które można dołączyć do zestawu, istnieje duża dowolność w odniesieniu do nich.
Przykład 1
Może to być wielu studentów, wiele liczb pierwszych itp.
Definicja... Pęczek A nazywa się podzbiorem zbioru V jeśli każdy element z A jest elementem V(oznaczać). Jeśli A jest podzbiorem V oraz V nie jest podzbiorem A wtedy mówią, że A jest ścisłym (właściwym) podzbiorem V(oznaczać).
Definicja... Zbiór, który nie zawiera elementów nazywamy pustym (oznaczonym przez Æ), jest podzbiorem dowolnego zbioru. Pęczek U nazywa się uniwersalnym, to znaczy wszystkie rozważane zbiory są jego podzbiorem.
Rozważ dwie definicje równości zbiorów.
Definicja... Zestawy A oraz V są uważane za równe, jeśli składają się z tych samych elementów, piszą A = B, Inaczej A¹ V.
Definicja... Zestawy A oraz V są uważane za równe, jeśli 
Są następujące sposoby definiowania zestawów :
1) wymieniając elementy: M = (a 1 , a 2 , …, K} , czyli spis jego elementów;
2) predykat charakterystyczny: M = (x | P(x)} (opis charakterystycznych właściwości, jakie muszą posiadać jego elementy);
procedura generatywna: m = { x | x= F} , który opisuje, jak pobrać elementy zestawu z już otrzymanych elementów lub innych obiektów. W tym przypadku elementami zbioru są wszystkie obiekty, które mogą być
1) zostały skonstruowane przy użyciu tej procedury. Na przykład zbiór wszystkich liczb całkowitych będących potęgami dwójki.
Komentarz... Podczas określania zestawów przez wyliczenie, oznaczenia elementów są zwykle ujęte w nawiasy klamrowe i oddzielone przecinkami. Tylko zbiory skończone mogą być określone przez wyliczenie (liczba elementów zbioru jest skończona, w przeciwnym razie zbiór nazywamy nieskończonym). Predykat charakterystyczny to pewien warunek wyrażony w formie instrukcji lub procedury logicznej, która zwraca wartość logiczną. Jeżeli warunek jest spełniony dla danego elementu, to należy on do definiowanego zbioru, w przeciwnym razie nie należy. Procedura tworzenia to procedura, która po uruchomieniu tworzy niektóre obiekty należące do zdefiniowanego zestawu. Zbiory nieskończone są dane przez charakterystyczny orzecznik lub procedurę generatywną.
Przykład 2
1) M = (1, 2, 3, 4)- wyliczenie elementów zbioru.
2) jest predykatem charakterystycznym.
Definicja... Kardynalność zbioru skończonego A To liczba jego elementów.
Liczność zbioru oznaczamy przez: | A|.
Przykład 3
|| = 0; |{}| = 1.
Definicja... Zestawy nazywane są ekwipotencjalnymi, jeśli ich moce są zbieżne.
Definicja... Zbiór wszystkich podzbiorów zbioru A nazywamy logicznym P (A).
Wiadomo, że jeśli zestaw A zawiera n elementy, to zestaw P(A) zawiera 2 n elementy. W związku z tym używamy również notacji dla stopnia zbioru zbioru A jak 2 A.
Przykład 4
A = (0, 1, 2),P(A) = { , {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}} .
Geometrycznie zbiory można przedstawić za pomocą diagramów Eulera-Venna. Konstrukcja diagramu polega na obrazie dużego prostokąta reprezentującego zbiór uniwersalny U, a wewnątrz - kółka (lub inne zamknięte figury), reprezentujące zestawy. Kształty muszą przecinać się w najbardziej ogólny sposób wymagany przez problem i muszą być odpowiednio oznaczone. Punkty leżące w różnych obszarach diagramu można uznać za elementy odpowiednich zbiorów. Po skonstruowaniu diagramu możliwe jest zacieniowanie pewnych obszarów w celu oznaczenia nowo powstałych zbiorów.
Uznaje się, że operacje na zestawach uzyskują nowe zestawy z istniejących.
Definicja... Unia zbiorów A oraz V nazywamy zbiorem składającym się ze wszystkich tych elementów, które należą do przynajmniej jednego ze zbiorów A,V(rys. 1.1):
Ryż. 1.1. Schemat Eulera-Venna dla unii
Definicja... Przecięcie zbiorów A oraz V nazywamy zbiorem składającym się ze wszystkich tych i tylko tych elementów, które należą jednocześnie do zbioru A i wiele V(rys. 1.2):
Ryż. 1.2. Wykres Eulera-Venna dla przecięcia
Definicja... Różnica zestawów A oraz V nazwany zbiorem wszystkich tych i tylko tych elementów A które nie są zawarte w V(rys. 1.3):
Ryż. 1.3. Diagram Eulera-Venna dla różnicy
Definicja... Symetryczna różnica zestawów A oraz V nazywamy zbiorem elementów tych zbiorów, które albo należą tylko do zbioru A, czy tylko zestaw V(rys. 1.4):
Ryż. 1.4. Diagram Eulera-Venna dla różnicy symetrycznej
Definicja... Absolutne dopełnienie zestawu A nazwany zbiorem wszystkich tych elementów, które nie należą do zbioru A(rys. 1.5):
Ryż. 1.5. Diagram Eulera-Venna dla dopełnienia absolutnego
Przykład 5
Korzystając z diagramów Eulera-Venna, udowadniamy tożsamość:
Rozważ lewą stronę stosunku i wykonaj czynności w kolejności:
1) znajdź punkt przecięcia zbiorów V oraz Z() (ryc. 1.6, a);
2) znaleźć związek wynikowego zbioru ze zbiorem A() (ryc. 1.6, b).
Rozważ prawą stronę relacji 
:
1) znajdź połączenie zbiorów A oraz V(ryc. 1.6, c);
2) znajdź połączenie zbiorów A oraz Z(Ryż.
1.6,d);
3) znajdź przecięcie dwóch ostatnich zbiorów i ( ) (rys. 6, e):
W obu przypadkach (ryc. 1.6, b) i (ryc. 1.6, e) otrzymujemy równe zbiory. Dlatego pierwotna relacja jest poprawna.
Ryż. 1.6. Dowód tożsamości za pomocą diagramów Eulera-Venna
Rozważ podstawowe tożsamości algebry zbiorów. Dla dowolnych zestawów A,V, oraz Z prawdziwe są następujące zależności (tabela 1.11):
Tabela 1.11 Podstawowe tożsamości algebry zbiorów
|
Stowarzyszenie |
Przejście |
|
1. Przemienność związku |
jeden'. Przemienność skrzyżowania |
|
2. Stowarzyszenie stowarzyszeniowe |
2 . Powiązanie skrzyżowania |
|
3. Rozdzielczość związku ze względu na skrzyżowanie |
3 . Rozdzielczość przecięcia w stosunku do sumy |
|
4. Prawa działania ze zbiorami pustymi i uniwersalnymi |
4'. Prawa działania z pustymi i uniwersalnymi zbiorami |
|
5. Prawo idempotentności stowarzyszeń” |
5'. Prawo idempotentności przecięcia |
|
6. Prawo De Morgana |
6 lat. Prawo De Morgana |
|
7. Prawo absorpcji
|
7 godzin. Prawo absorpcji
|
|
8. Prawo sklejania
|
osiem'. Prawo wiązania
|
|
9. Prawo Poreckiego
|
9'. Prawo Poreckiego
|
|
10. Prawo podwójnego uzupełnienia |
|
