Relacja równoważności i zbiór ilorazów. Relacje równoważności. Czynnik ustala relacje równoważności. Zestawy czynników
(to znaczy, który ma następujące właściwości: każdy element zbioru jest sobie równoważny; if X równowartość y, To y równowartość X; Jeśli X równowartość y, A y równowartość z, To X równowartość z ).
Następnie wywoływany jest zbiór wszystkich klas równoważności zestaw czynników i jest wyznaczony. Podział zbioru na klasy równoważnych elementów nazywa się jego faktoryzacja.
Wyświetl z X do zbioru klas równoważności mapowanie czynników.
Przykłady
Rozsądne jest stosowanie faktoryzacji zbiorów w celu uzyskania przestrzeni unormowanych z półnormowanych, przestrzeni z iloczynem wewnętrznym z przestrzeni z iloczynem prawie wewnętrznym itp. W tym celu wprowadzamy odpowiednio normę klasy równą normą dowolnego elementu, a iloczyn wewnętrzny klas jako iloczyn wewnętrzny dowolnych elementów klas. Z kolei relację równoważności wprowadza się w następujący sposób (na przykład w celu utworzenia znormalizowanej przestrzeni ilorazowej): wprowadza się podzbiór pierwotnej przestrzeni seminormowanej, składający się z elementów o zerowej półnormie (nawiasem mówiąc, jest ona liniowa, to znaczy jest to podprzestrzeń) i uważa się, że dwa elementy są równoważne, jeśli ich różnica należy do tej właśnie podprzestrzeni.
Jeżeli do rozłożenia przestrzeni liniowej na czynniki wprowadza się pewną podprzestrzeń i zakłada się, że jeśli różnica dwóch elementów przestrzeni pierwotnej należy do tej podprzestrzeni, to elementy te są równoważne, to zbiór współczynników jest przestrzenią liniową i nazywa się przestrzeń czynnikowa.
Przykłady
Zobacz też
Fundacja Wikimedia. 2010.
Zobacz, co „Factorset” znajduje się w innych słownikach:
Logiczna zasada leżąca u podstaw definicji poprzez abstrakcję (patrz Definicja poprzez abstrakcję): dowolna Relacja typu równości, zdefiniowana na pewnym początkowym zestawie elementów, dzieli (dzieli, klasyfikuje) oryginał... ...
Forma myślenia odzwierciedlająca istotne właściwości, powiązania i relacje obiektów i zjawisk w ich sprzecznościach i rozwoju; myśl lub system myśli, który uogólnia, rozróżnia przedmioty określonej klasy według pewnego ogólnego i zbiorczego... ... Wielka encyklopedia radziecka
Kohomologia grupy Galois. Jeśli M jest grupą abelową i grupą Galois rozszerzenia działającego na M, to grupy kohomologiczne Galois są grupami kohomologicznymi zdefiniowanymi przez kompleks składający się ze wszystkich odwzorowań, a d jest operatorem współograniczenia (patrz Kohomologia grup).... . .. Encyklopedia matematyczna
Konstrukcja raju pojawiła się po raz pierwszy w teorii mnogości, a następnie stała się szeroko stosowana w algebrze, topologii i innych obszarach matematyki. Ważnym szczególnym przypadkiem I. p. jest I. p. skierowanej rodziny struktur matematycznych tego samego typu. Niech będzie… Encyklopedia matematyczna
Punkty, chociaż w stosunku do grupy G działającej na zbiór X (po lewej), zbiór Zbiór jest podgrupą G i nazywa się. stabilizator, czyli stacjonarna podgrupa punktu względem G. Odwzorowanie indukuje bijekcję pomiędzy G/Gx a orbitą G(x). O.… … Encyklopedia matematyczna
Ten artykuł ma zbyt krótkie wprowadzenie. Proszę o dodanie części wprowadzającej, która krótko przedstawia temat artykułu i podsumowuje jego zawartość... Wikipedia
Ten artykuł jest o systemie algebraicznym. Informacje na temat gałęzi logiki matematycznej badającej stwierdzenia i operacje na nich można znaleźć w artykule Algebra logiki . Algebra Boole'a to niepusty zbiór A z dwiema operacjami binarnymi (analogicznie do koniunkcji), ... ... Wikipedia
Niech na zbiorze będzie dana relacja równoważności. Wówczas zbiór wszystkich klas równoważności nazywany jest zbiorem współczynników i jest oznaczany. Podział zbioru na klasy równoważnych elementów nazywa się jego rozkładem na czynniki. Mapowanie z do... ...Wikipedii
W geometrii przez skierowany odcinek rozumie się uporządkowaną parę punktów, z których pierwszy, punkt A, nazywany jest jego początkiem, a drugi B – końcem. Spis treści 1 Definicja… Wikipedia
W różnych gałęziach matematyki jądrem odwzorowania jest pewna ustalona szczelina, która w pewnym sensie charakteryzuje różnicę między f a odwzorowaniem iniekcyjnym. Konkretna definicja może się różnić, ale w przypadku mapowania iniekcyjnego... ... Wikipedia
Teoria zbiorów. Podstawowe koncepcje
Teoria mnogości jest podstawową definicją współczesnej matematyki. Został stworzony przez Georga Cantora w latach sześćdziesiątych XIX wieku. Napisał: „Wiele to wiele, pojmowane jako jedna całość”. Pojęcie zbioru jest jednym z podstawowych, nieokreślonych pojęć matematyki. Nie da się tego sprowadzić do innych, prostszych koncepcji. Nie da się więc tego zdefiniować, a jedynie wyjaśnić. Zatem zbiór to połączenie w jedną całość obiektów, które można wyraźnie rozróżnić naszą intuicją lub naszą myślą; zbiór pewnych obiektów zdefiniowanych przez wspólną cechę.
Na przykład,
1. Wielu mieszkańców Woroneża
2. Zbiór punktów płaskich
3. Zbiór liczb naturalnych ℕitp.
Zestawy są zwykle oznaczane dużymi literami łacińskimi ( A, B, C itp.). Obiekty tworzące dany zbiór nazywane są jego elementami. Elementy zestawu są oznaczone małymi literami łacińskimi ( a, b, c itp.). Jeśli X– ustaw, a następnie nagraj x∈X Oznacza to, że X jest elementem zestawu X albo co X należy do zestawu X i wpis x∉X ten element X nie należy do zestawu X. Na przykład, niech ℕ będzie zbiorem liczb naturalnych. Następnie 5 ℕ , A 0,5∉ℕ .
Jeśli zestaw Y składa się z elementów zestawu X, wtedy tak mówią Y jest podzbiorem zbioru X i oznaczać Y⊂Х(Lub Y⊆Х). Na przykład zbiór liczb całkowitych ℤ jest podzbiorem liczb wymiernych ℚ .
Jeśli na dwa zestawy X I Y jednocześnie występują dwie inkluzje X Y I YX, tj. X jest podzbiorem zbioru Y I Y jest podzbiorem zbioru X, a następnie zestawy X I Y składają się z tych samych elementów. Takie zestawy X I Y nazywamy równymi i piszemy: X=Y.
Często używany jest termin zbiór pusty - Ø - zbiór nie zawierający ani jednego elementu. Jest podzbiorem dowolnego zbioru.
Do opisu zbiorów można zastosować następujące metody.
Metody określania zbiorów
1. Wyliczenie obiektów. Używane tylko dla skończonych zbiorów.
Na przykład, X=(x1, x2, x3… x n). Wpis Y ={1, 4, 7, 5} oznacza, że zbiór składa się z czterech liczb 1, 4, 7, 5 .
2. Wskazanie charakterystycznych właściwości elementów zbioru.
Aby to zrobić, ustawiana jest określona właściwość R, co pozwala określić, czy element należy do zbioru. Ta metoda jest bardziej uniwersalna.
X=(x: P(x))
(pęczek X składa się z takich elementów X, dla którego nieruchomość jest utrzymywana P(x)).
Zestaw pusty można określić, określając jego właściwości: Ř=(x: x≠x)
Możesz konstruować nowe zbiory, korzystając z już zdefiniowanych, korzystając z operacji na zbiorach.
Ustaw operacje
1. Suma (suma) to zbiór wszystkich tych elementów, z których każdy należy do co najmniej jednego ze zbiorów A Lub W.
A∪B=(x: x A lub x B).
2. Przecięcie (iloczyn) to zbiór składający się ze wszystkich elementów, z których każdy jednocześnie należy do zbioru A, i wiele W.
A∩B=(x: x A i x B).
3. Ustaw różnicę A I W jest zbiorem składającym się ze wszystkich elementów należących do zbioru A i nie należycie do tłumu W.
A\B=(x: x A i x B)
4. Jeśli A– podzbiór zbioru W. To dużo B\A zwane dopełnieniem zbioru A za dużo W i oznaczać A'.
5. Symetryczna różnica dwóch zbiorów jest zbiorem A∆B=(A\B) (B\A)
N- zbiór wszystkich liczb naturalnych;
Z- zbiór wszystkich liczb całkowitych;
Q- zbiór wszystkich liczb wymiernych;
R- zbiór wszystkich liczb rzeczywistych;
C- zbiór wszystkich liczb zespolonych;
Z 0- zbiór wszystkich nieujemnych liczb całkowitych.
Własności operacji na zbiorach:
1. A B=B A (przemienność związku)
2. A B=B A (przemienność przecięcia)
3. A(B C)=(A W) C (skojarzenie związku)
4. A (W C)=(A W) C (powiązanie przecięcia)
5. A (W C)=(A W) (A C) (1. zasada rozdzielności)
6. A (W C)=(A W) (A C) (2. zasada rozdzielności)
7. A Ř=A
8. A U= U
9. A Ø= Ø
10 A U=A
11. (A B)'=A' B” (prawo de Morgana)
12. (A B)'=A' B” (prawo de Morgana)
13. A (A B)=A (prawo absorpcji)
14. A (A B)=A (prawo absorpcji)
Udowodnijmy własność nr 11. (A B)'=A' W'
Z definicji równych zbiorów musimy udowodnić dwa inkluzje 1) (A B)’ ⊂A’ W';
2) A' B’⊂(A W)'.
Aby udowodnić pierwszą inkluzję, rozważ dowolny element x∈(A B)’=X\(A∪B). To znaczy, że x∈X, x∉ A∪B. Wynika, że x∉A I x∉B, Dlatego x∈X\A I x∈X\B, co znaczy x∈A’∩B’. Zatem, (A B)’⊂A’ W'
Wróć, jeśli x∈A’ W', To X jednocześnie należy do zbiorów A', B', co znaczy x∉A I x∉B. Wynika, że x∉ A W, Dlatego x∈(A W)'. Stąd, A' B’⊂(A W)'.
Więc, (A B)'=A' W'
Zbiór składający się z dwóch elementów, w którym określona jest kolejność elementów, nazywany jest parą uporządkowaną. Aby to napisać, użyj nawiasów. (x1,x2)– zbiór dwuelementowy, w którym za pierwszy element uważa się x 1, a za drugi x 2. Pary (x1,x2) I (x2,x1), Gdzie x 1 ≠ x 2, są uważane za różne.
Zbiór składający się z n elementów, w którym określona jest kolejność elementów, nazywany jest uporządkowanym zbiorem n elementów.
Iloczyn kartezjański jest dowolnym zbiorem X 1, X 2,…,X n uporządkowane zbiory n elementów, gdzie x 1 X 1, x 2 X 2 ,…, x rz Xn
X 1 X rz
Jeśli zestawy X 1, X 2,…,X n mecz (X 1 = X 2 =…= X n), wówczas oznacza się ich produkt Xn.
Na przykład, ℝ 2 – zbiór uporządkowanych par liczb rzeczywistych.
Relacje równoważności. Zestawy czynników
Na podstawie danego zbioru można konstruować nowe zbiory, uwzględniając zbiór niektórych podzbiorów. W tym przypadku zwykle nie mówimy o zbiorze podzbiorów, ale o rodzinie lub klasie podzbiorów.
W szeregu pytań rozważana jest klasa takich podzbiorów danego zbioru A, które się nie przecinają i których związek pokrywa się z A. Jeśli ten zestaw A można przedstawić jako sumę jej parami rozłącznych podzbiorów, wówczas zwyczajowo się tak mówi A podzielone na klasy. Podział na klasy dokonywany jest na podstawie jakiejś cechy.
Pozwalać X nie jest zbiorem pustym, to dowolnym podzbiorem R z pracy X X nazywa się relacją binarną na zbiorze X. Jeśli para (x, y) zawarte w R, mówią, że element x jest w relacji R Z Na.
Na przykład relacje x=y, x≥y są relacjami binarnymi na zbiorze ℝ.
Relacja binarna R na zestawie X nazywa się relacją równoważności, jeżeli:
1. (x,x) R; X X (właściwość zwrotności)
2. (x, y) R => (y,x) R (właściwość symetrii)
3. (x, y) R, (y, z) R, następnie (x, z) R (właściwość przechodniości)
Jeśli para (x, y) weszły w relacje równoważności, wówczas x i y nazywane są równoważnymi (x~y).
1.Niech ℤ – zbiór liczb całkowitych, m≥1- Liczba całkowita. Zdefiniujmy relację równoważności R NA ℤ aby nie~ok, Jeśli nie wiem podzielony przez M. Sprawdźmy, czy własności tej relacji są spełnione.
1. Refleksyjność.
Dla kazdego n∈ℤ ℤ takie, że (p,p)∈R
р-р=0. Ponieważ 0∈ ℤ , To (p,p)∈ℤ.
2. Symetria.
Z (n,k) ∈R wynika, że coś takiego istnieje р∈ℤ, Co n-k=mp;
k-n =m(-p), -p∈ ℤ, stąd (k,n) ∈R.
3. Przechodniość.
Od czego (n,k) ∈R, (k,q) ∈R wynika, że takie istnieją str. 1 I р 2 ∈ ℤ, Co n-k=mp 1 I k-q=mp 2. Dodając te wyrażenia, otrzymujemy to n-q=m(p 1 + p 2), p 1 + p 2 = p, p∈ ℤ. Dlatego (n,q) ∈ ℤ.
2. Rozważ zestaw X wszystkie skierowane segmenty przestrzeni lub płaszczyzny . =(A, B). Wprowadźmy relację równoważności R NA X.
Niech G=(p 0 =e, p 1, …, p r) będzie pewną grupą permutacji zdefiniowanych na zbiorze X = (1, 2, …, n) o jednostce e=p 0 identycznej permutacji. Zdefiniujmy relację x~y, stawiając x~y jako równoważne faktowi, że istnieje p należące do G(p(x)=y). Wprowadzona relacja jest relacją równoważności, czyli spełnia trzy aksjomaty:
1) x~x;
2) x~y→y~x;
3) x~y&y~z→x~z;
Niech A będzie dowolnym zbiorem.
Definicja: Relacja binarna δ=A*A jest relacją równoważności (oznaczoną przez a ~ b) jeśli spełnia następujące aksjomaty:
∀ a, b, c ∈ A
1) a ~ a – zwrotność;
2) a ~ b ⇒ b ~ a – przemienność;
3) a ~ b & b ~ c → a ~ c - przechodniość
oznaczone przez a ~ b, σ(a,b), (a,b) ∈ σ, a σ b
Definicja: Podział zbioru A jest rodziną parami rozłącznych podzbiorów zbioru A, które w sumie (w sumie) dają wszystkie A.
А= ∪А ja, А i ∩А jot = ∅, ∀i ≠ jot.
Podzbiory A i nazywane są cosetami podziału.
Twierdzenie: każda relacja równoważności zdefiniowana na A odpowiada pewnemu podziałowi zbioru A. Każdy podział zbioru A odpowiada pewnej relacji równoważności na zbiorze A.
W skrócie: istnieje zgodność jeden do jednego pomiędzy klasami wszystkich relacji równoważności zdefiniowanych na zbiorze A i klasą wszystkich podziałów zbioru A.
Dowód: niech σ będzie relacją równoważności na zbiorze A. Niech a ∈ A.
Skonstruujmy zbiór: K a =(x ∈ A,: x~a) – wszystkie elementy równoważne a. Zbiór (notacja) nazywany jest klasą równoważności ze względu na równoważność σ. Zauważ, że jeśli b należy do K a, to b~a. Pokażmy, że a~b⇔K a =K b . Rzeczywiście, niech a~b. Weźmy dowolny element c należący do K a . Wtedy ca~a, a~b, c~b, c należą do Kb i dlatego Kb należy do Ka. W podobny sposób pokazano, że K a należy do K b. Dlatego K b = K a.
Niech teraz K b = K a . Wtedy a należy do K a = K b , a należy do K b , a~b. To właśnie trzeba było pokazać.
Jeżeli 2 klasy K a i K b mają wspólny element c, to K a = K b. Faktycznie, jeśli c należy do K a i K b , to b~c, ca~a, b~a => K a = K b .
Dlatego różne klasy równoważności albo nie przecinają się, albo przecinają, a następnie pokrywają się. Każdy element c zbioru A należy tylko do jednej klasy równoważności Kc. Zatem system rozłącznych klas równoważności na przecięciu daje cały zbiór A. A zatem system ten jest podziałem zbioru A na klasy równoważności.
Odwrotnie: Niech A = suma lub A i jest podziałem A. Wprowadźmy relację a~b na A, ponieważ a~b ⇔ a,b należą do tej samej klasy podziału. Relacja ta spełnia następujące aksjomaty:
1) a ~ a (są w tej samej klasie);
2) a ~ b → b ~ a;
3) a ~ b i b ~ c → a ~ c, tj. wprowadzona relacja ~ jest relacją równoważności.
Komentarz:
1) podział zbioru A na jednoelementowe podzbiory oraz podział zbioru A składający się wyłącznie ze zbioru A nazywane są podziałami trywialnymi (niewłaściwymi).
2) Podział A na jednoelementowe podzbiory odpowiada relacji równoważności, która jest równością.
3) Przegrody A, składające się z jednej klasy A, odpowiadają relacji równoważności zawierającej A x A.
4) a σ b → [a] σ = [b] σ - dowolna relacja równoważności zdefiniowana na pewnym zbiorze dzieli ten zbiór na parami rozłączne klasy zwane klasami równoważności.
Definicja: Zbiór klas równoważności zbioru A nazywany jest zbiorem ilorazowym A/σ zbioru A przez równoważność σ.
Definicja: Odwzorowanie p:A → A/σ, dla którego p(A)=[a] σ, nazywa się odwzorowaniem kanonicznym (naturalnym).
Każda relacja równoważności zdefiniowana na pewnym zbiorze dzieli ten zbiór na pary rozłączne klasy zwane klasami równoważności.
Jeśli postawa R ma następujące właściwości: zwrotny symetryczny przechodni, tj. jest relacją równoważności (~ lub ≡ lub E) na zbiorze M , wówczas zbiór klas równoważności nazywany jest zbiorem współczynników zbioru M dotyczące równoważności R i jest wyznaczony PAN
Istnieje podzbiór elementów zbioru M równowartość X , zwany klasa równoważności.
Z definicji zbioru współczynników wynika, że jest to podzbiór liczby logicznej: .
Funkcja nazywa się identyfikacja i jest zdefiniowany w następujący sposób:
Twierdzenie. Algebra czynnikowa F n /~ jest izomorficzne z algebrą funkcji boolowskich B N
Dowód.
Wymagany izomorfizm ξ : F N / ~ → B n wyznaczana jest według następującej zasady: klasa równoważności ~(φ) funkcja jest dopasowana fa φ , posiadanie tabeli prawdy dla dowolnego wzoru ze zbioru ~(φ) . Ponieważ różne klasy równoważności odpowiadają różnym tablicom prawdy, mapowanie ξ injective, a ponieważ dla dowolnej funkcji logicznej F z W p istnieje wzór reprezentujący tę funkcję F, potem mapowanie ξ surjektywny. Operacje przechowywania, 0, 1, gdy są wyświetlane ξ jest sprawdzane bezpośrednio. CTD.
Z twierdzenia o zupełności funkcjonalnej każdej funkcji, która nie jest stała 0 , odpowiada pewnemu SDNF ψ , należący do klasy ~(φ) = ξ -1 (f) formuły reprezentujące funkcję F . Pojawia się problem przebywania w klasie ~(φ) rozłączna postać normalna, która ma najprostszą strukturę.
Koniec pracy -
Ten temat należy do działu:
Kurs wykładów z dyscypliny matematyka dyskretna
Moskiewski Państwowy Uniwersytet Inżynierii Lądowej.. Instytut Ekonomii Zarządzania i Systemów Informacyjnych w Budownictwie.. IEEE..
Jeśli potrzebujesz dodatkowych materiałów na ten temat lub nie znalazłeś tego czego szukałeś, polecamy skorzystać z wyszukiwarki w naszej bazie dzieł:
Co zrobimy z otrzymanym materiałem:
Jeśli ten materiał był dla Ciebie przydatny, możesz zapisać go na swojej stronie w sieciach społecznościowych:
| Ćwierkać |
Wszystkie tematy w tym dziale:
Przedmiot matematyki dyskretnej
Przedmiotem matematyki dyskretnej (skończonej, skończonej) jest dział matematyki badający właściwości struktur dyskretnych, natomiast matematyka klasyczna (ciągła) bada właściwości obiektów
Izomorfizm
Nauka badająca operacje algebraiczne nazywa się algebrą. Koncepcja ta stanie się bardziej szczegółowa i pogłębiona w miarę studiowania kursu. Algebra interesuje się jedynie pytaniem JAK postępować
Ćwiczenia
1. Udowodnić, że odwzorowanie izomorficzne jest zawsze izotoniczne i sytuacja odwrotna nie jest prawdziwa. 2. Napisz swoją grupę w języku zbiorów. 3. Zapisz w języku zbiorów obiekty, które
Zestaw i elementy zestawu
Obecnie istniejące teorie mnogości różnią się paradygmatyką (systemem poglądów) podstawy pojęciowej i środków logicznych. Jako przykład możemy przytoczyć dwa przeciwne
Zbiory skończone i nieskończone
To, z czego składa się zestaw, tj. Obiekty tworzące zbiór nazywane są jego elementami. Elementy zbioru są odrębne i różnią się od siebie. Jak widać z podanego przykładu
Moc zestawu
Liczność zbioru skończonego jest równa liczbie jego elementów. Na przykład liczność wszechświata B(A) zbioru A liczności n
A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3…An|
Skończony zbiór A ma liczność k, jeśli jest równy segmentowi 1.. k;:
Podzbiór, własny podzbiór
Po wprowadzeniu pojęcia zbioru pojawia się zadanie konstruowania nowych zbiorów z już istniejących, czyli definiowania działań na zbiorach. Zestaw M",
Symboliczny język znaczących teorii mnogości
W trakcie studiowania kursu będziemy rozróżniać język przedmiotowy teorii mnogości od metajęzyka, za pomocą którego badany jest język przedmiotowy. Przez język teorii mnogości rozumiemy relacyjny
Dowód
Zbiór B jest nieskończony, co oznacza
Dodawanie i usuwanie elementów
Jeśli A jest zbiorem, a x jest elementem, to wtedy jest to element
Zbiory ograniczone. Wyznaczać granice
Niech na pewnym zbiorze X będzie dana funkcja numeryczna f(x). Górną granicą (granicą) funkcji f(x) jest taka liczba
Dokładny górny (dolny) limit
Zbiór wszystkich górnych granic E oznaczono jako Es, a wszystkie dolne granice przez Ei. W razie
Dokładna górna (dolna) granica zbioru
Jeżeli element z należy do przecięcia zbioru E i zbioru wszystkich jego górnych granic Es (odpowiednio dolnych r
Podstawowe własności granic górnych i dolnych
Niech X będzie zbiorem częściowo uporządkowanym. 1. Jeśli, to
Zestaw z atrybutywnego punktu widzenia
Zagregowany punkt widzenia, w przeciwieństwie do atrybutywnego punktu widzenia, jest logicznie nie do utrzymania w tym sensie, że prowadzi do paradoksów w rodzaju Russella i Cantora (patrz poniżej). W ramach atrybutywnego t
Struktura
Częściowo uporządkowany zbiór X nazywamy strukturą, jeżeli zawiera dowolny zbiór dwuelementowy
Zestawy osłonowe i dzielące
Podział zbioru A jest rodziną Ai
Relacje binarne
Ciąg o długości n, którego wyrazami są a1, .... an, będziemy oznaczać przez (a1, .... a
Własności relacji binarnych
Relacja binarna R na zbiorze Ho ma następujące właściwości: (a) zwrotna, jeśli xRx
Relacje trójskładnikowe
Iloczyn kartezjański XY
Relacje N-ary
Przez analogię do iloczynu kartezjańskiego dwóch zbiorów X, Y, możemy skonstruować iloczyn kartezjański X
Wyświetla
Odwzorowania to pewne połączenia pomiędzy elementami zbiorów. Najprostszymi przykładami relacji są relacje przynależności x
Korespondencja
Podzbiór S iloczynu kartezjańskiego nazywany jest n-arną korespondencją elementów zbiorów Mi. Formalnie
Funkcjonować
Wszystkie gałęzie matematyki dyskretnej opierają się na pojęciu funkcji. Niech X -
Reprezentowanie funkcji w kategoriach relacji
Relację binarną f nazywa się funkcją, jeśli pochodzi z i
Wstrzyknięcie, surjekcja, bijekcja
Używając terminu „odwzorowanie”, dokonuje się rozróżnienia pomiędzy odwzorowaniem XbY i odwzorowaniem X na Y
Funkcja odwrotna
Dla dowolnych definiujemy
Częściowo zamówione zestawy
Zbiór S nazywany jest częściowo uporządkowanym (PUM), jeśli podano mu zwrotną, przechodnią i antysymetryczną binarną relację częściowego porządku
Ustaw minimalizację reprezentacji
Korzystając z tych praw, rozważamy problem minimalizacji reprezentacji zbioru M za pomocą operacji
Przegrupowania
Mając dany zbiór A. Niech A będzie skończonym zbiorem składającym się z n elementów A = (a1, a2, …, a
Permutacje z powtórzeniami
Niech zbiór A będzie miał identyczne (powtarzające się) elementy. Permutacja z powtórzeniami kompozycji (n1, n2, …,nk
Miejsca docelowe
Krotki o długości k (1≤k≤n), składające się z różnych elementów n-elementowego zbioru A (krotki różnią się
Pozycje z powtórzeniami
Niech zbiór A będzie miał identyczne (powtarzające się) elementy. Miejsca docelowe z powtórzeniami n elementów k nazw
Uporządkowane rozmieszczenie
Umieśćmy n obiektów w m pudełkach tak, aby każde pudełko zawierało sekwencję, a nie jak poprzednio zbiór umieszczonych w nim obiektów. Dwa
Kombinacje
Ze zbioru m-elementowego A konstruujemy uporządkowany zbiór o długości n, którego elementy są układami o tej samej tematyce
Kombinacje z powtórzeniami
Otrzymane wzory obowiązują tylko wtedy, gdy w zbiorze A nie ma identycznych elementów. Niech będą elementy n typów i z nich krotka
Metoda generowania funkcji
Metodę tę stosuje się do wyliczania liczb kombinatorycznych i ustalania tożsamości kombinatorycznych. Punktem wyjścia jest kombinator ciągu (ai).
System algebraiczny
System algebraiczny A jest zbiorem ‹M,O,R›, którego pierwszy składnik M jest zbiorem niepustym, drugi składnik O jest zbiorem
Zamknięcie i podalgebry
Mówi się, że podzbiór jest domknięty w ramach operacji φ if
Algebry z jedną operacją binarną
Niech będzie dana jedna operacja binarna na zbiorze M. Rozważmy algebry, które generuje, ale najpierw rozważmy niektóre właściwości operacji binarnych. Binarny o
Grupoid
Algebra postaci<М, f2>zwany groupoidem. Jeśli f2 jest operacją podobną do mnożenia (
Liczby całkowite modulo m
Biorąc pod uwagę pierścień liczb całkowitych
Kongruencje
Zgodność z algebrą A =
Elementy teorii grafów
Wykresy są obiektami matematycznymi. Teorię grafów wykorzystuje się w takich dziedzinach jak fizyka, chemia, teoria komunikacji, projektowanie komputerów, elektrotechnika, inżynieria mechaniczna, architektura, badania nad
Wykres, wierzchołek, krawędź
Przez graf nieskierowany (w skrócie graf) rozumiemy taką dowolną parę G =
Korespondencja
Inny, częściej stosowany opis grafu skierowanego G polega na określeniu zbioru wierzchołków X i korespondencji Г, aby
Wykres nieskierowany
Jeśli krawędzie nie mają orientacji, wówczas graf nazywa się nieskierowanym (nieukierunkowanym duplikatem lub nieukierunkowanym).
Częstość występowania, wykres mieszany
Jeśli krawędź e ma postać (u, v) lub<и, v>, to powiemy, że krawędź e jest incydentna ver
Odwrotne dopasowanie
Ponieważ reprezentuje zbiór takich wierzchołków
Izomorfizm wykresu
Dwa wykresy G1 =
Trasa zorientowana na ścieżkę
Ścieżka (lub skierowana trasa) grafu skierowanego to sekwencja łuków, w których
Sąsiednie łuki, sąsiednie wierzchołki, stopień wierzchołka
Łuki a = (xi, xj), xi ≠ xj, mające wspólne wierzchołki końcowe, n
Łączność
Dwa wierzchołki grafu nazywamy połączonymi, jeśli łączy je prosta ścieżka. Graf nazywamy spójnym, jeśli wszystkie jego wierzchołki są połączone. Twierdzenie.
Wykres łuku ważonego
Wykres G = (N, A) nazywamy ważonym, jeśli jakaś funkcja l: A → R jest zdefiniowana na zbiorze łuków A tak, że
Silna matryca łączności
Silna macierz łączności: umieść 1 wzdłuż przekątnej; wypełnij linię X1 - jeśli wierzchołek jest osiągalny z X1 i X1 d
Drzewa
Drzewa są ważne nie tylko dlatego, że znajdują zastosowanie w różnych dziedzinach wiedzy, ale także dlatego, że zajmują szczególne miejsce w samej teorii grafów. To ostatnie spowodowane jest niezwykłą prostotą konstrukcji drzewa
Każde nietrywialne drzewo ma co najmniej dwa wiszące wierzchołki
Dowód Rozważmy drzewo G(V, E). Drzewo jest zatem grafem spójnym
Twierdzenie
Środek wolnego drzewa składa się z jednego wierzchołka lub dwóch sąsiednich wierzchołków: Z(G) = 0&k(G) = 1 → C(G) = K1
Drzewa kierowane, uporządkowane i binarne
Drzewa ukierunkowane (uporządkowane) są abstrakcją zależności hierarchicznych, które bardzo często spotyka się zarówno w życiu praktycznym, jak i w matematyce i programowaniu. Drzewo (orientacja)
Dowód
1. Każdy łuk wchodzi do jakiegoś węzła. Z klauzuli 2 definicji 9.2.1 mamy: w
Zamówione drzewka
Zbiory T1,..., Tk w równoważnej definicji porządku są poddrzewami. Jeżeli względna kolejność poddrzew T1,...,
Drzewa binarne
Drzewo binarne (lub binarne) to skończony zbiór węzłów, który jest albo pusty, albo składa się z korzenia i dwóch rozłącznych drzew binarnych - lewego i prawego. Drzewo binarne nie w Javie
Bezpłatna reprezentacja drzewa
Do reprezentowania drzew można zastosować te same techniki, co do przedstawiania grafów ogólnych – macierze sąsiedztwa i częstości występowania, listy sąsiedztwa i inne. Ale korzystając ze specjalnych właściwości
Koniec dla
Uzasadnienie Kod Prüfera jest rzeczywiście swobodną reprezentacją drzewa. Aby to sprawdzić, pokażmy, że jeśli T" jest drzewem
Reprezentacja drzew binarnych
Każde wolne drzewo można zorientować, wyznaczając jeden z jego węzłów jako korzeń. Każde zamówienie można zamówić dowolnie. Dla potomków jednego węzła (braci) uporządkowanego rzędu definiuje się go względnie
Podstawowe funkcje logiczne
Oznaczmy przez E2 = (0, 1) zbiór składający się z dwóch liczb. Liczby 0 i 1 są podstawowe w dyskretnej macie
Funkcja logiczna
Funkcja boolowska o n argumentach x1, x2,…,xn jest funkcją f od n-tej potęgi zbioru
Dwuelementowa algebra Boole’a
Rozważmy zbiór Во = (0,1) i zdefiniujmy na nim operacje, zgodnie z tabelami źródeł
Tablice funkcji boolowskich
Funkcję logiczną n zmiennych można określić za pomocą tabeli składającej się z dwóch kolumn i 2 n wierszy. Pierwsza kolumna zawiera listę wszystkich zestawów z B
F5 – powtórz w y
f6 – suma modulo 2 f7
Kolejność operacji
Jeśli w wyrażeniu złożonym nie ma nawiasów, operacje należy wykonać w następującej kolejności: koniunkcja, alternatywna, implikacja, równoważność, negacja. Konwencje dotyczące układu pierwszego twierdzenia Shannona
Aby rozwiązać problem znalezienia odpowiedników SDNF i SCNF dla pierwotnego wzoru φ, najpierw rozważymy rozwinięcia funkcji logicznej f(x1, x2
Drugie twierdzenie Shannona
Na mocy zasady dualności Twierdzenie 6.4.3 (drugie twierdzenie Shannona) obowiązuje dla algebr Boole'a. Dowolna funkcja boolowska f(x1, x2,...
Kompletność funkcjonalna
Twierdzenie (o kompletności funkcjonalnej). Dla dowolnej funkcji logicznej f istnieje wzór φ reprezentujący funkcję f
Algorytm znajdowania sdnf
Aby znaleźć SDNF, wzór ten należy najpierw sprowadzić do DNF, a następnie przekształcić jego koniunkcje w składniki jednostki, wykonując następujące czynności: a) jeśli koniunkcja zawiera pewne
Metoda Quine’a
Rozważmy metodę Quine’a służącą do znajdowania MDNF reprezentującego daną funkcję boolowską. Zdefiniujmy trzy następujące operacje: - operacja całkowitego klejenia -
Kanoniczna reprezentacja funkcji logicznych
Postacie kanoniczne funkcji logicznych (wzory) to wyrażenia, które mają standardową postać formuły logicznej, tak że jednoznacznie reprezentują funkcję logiczną. W algebrze
Systemy funkcji Boole’a
Niech funkcje logiczne f(g1, g2, …, gm) i g1(x1, x2, …, xn), g2(x1
Baza Zhegalkina
Wypróbujmy, spójrzmy na system. Jest kompletny, ponieważ każda funkcja z podstawy standardowej jest wyrażona w kategoriach
Twierdzenie Posta
Twierdzenie Posta ustanawia warunki konieczne i wystarczające kompletności systemu funkcji boolowskich. (Post E.L. Dwuwartościowe interaktywne systemy logiki matematycznej. – Annals of Math. Stu
Dowód
Konieczność. Z odwrotności. Niech będzie
Algebra Zhegalkina Logika zdań Definicja orzeczenia Zastosowanie predykatów w algebrze Algebra predykatów Boole’a F↔G=(F→G)(G→F), F→G=nie FG Rachunek predykcyjny Podążanie i równoważność Zaakceptowane oznaczenia Oznaczenia meta Niech R będzie relacją binarną na zbiorze X. Relacja R nazywa się odblaskowy
, if (x, x) О R dla wszystkich x О X; symetryczny
– jeśli z (x, y) О R wynika (y, x) О R; liczba przechodnia 23 odpowiada opcji 24, jeśli (x, y) О R i (y, z) О R implikują (x, z) О R. Przykład 1 Powiemy, że x О X ma wspólnego
z elementem y О X, jeśli zbiór Relacja równoważności na X jest relacją zwrotną, przechodnią i symetryczną. Łatwo zauważyć, że RÍ X ´ X będzie relacją równoważności wtedy i tylko wtedy, gdy inkluzje zachodzą: Id X Í R (zwrotność), R -1 Í R (symetria), R ° R Í R (przechodniość). W rzeczywistości te trzy warunki są równoważne następującym: Id X Í R, R -1 = R, R ° R = R. Dzieląc zbioru X jest zbiorem A parami rozłącznych podzbiorów a Í X takich, że UA = X. Z każdym podziałem A możemy powiązać relację równoważności ~ na X, wstawiając x ~ y, jeśli x i y są elementami pewnego a Î A . Każda relacja równoważności ~ na X odpowiada podziałowi A, którego elementy są podzbiorami, z których każdy składa się z elementów relacji ~. Te podzbiory nazywane są klasy równoważności
. Ten podział A nazywany jest zbiorem współczynników zbioru X w odniesieniu do ~ i jest oznaczany: X/~. Zdefiniujmy relację ~ na zbiorze w liczb naturalnych, wstawiając x ~ y, jeśli reszty z dzielenia x i y przez 3 są równe. Następnie w/~ składa się z trzech klas równoważności odpowiadających resztom 0, 1 i 2. Relacja zamówienia Nazywa się relację binarną R na zbiorze X antysymetryczny
, jeśli z x R y i y R x wynika: x = y. Nazywa się relację binarną R na zbiorze X relacja porządku
, jeśli jest zwrotny, antysymetryczny i przechodni. Łatwo zauważyć, że jest to równoważne następującym warunkom: 1) Id X Í R (zwrotność), 2) R Ç R -1 (antysymetria), 3) R ° R Í R (przechodniość). Nazywa się parę uporządkowaną (X, R) składającą się ze zbioru X i relacji porządku R na X częściowo zamówiony zestaw
. Przykład 1 Niech X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2 ), (1, 3), (2, 2), (3, 3)). Ponieważ R spełnia warunki 1 – 3, to (X, R) jest zbiorem częściowo uporządkowanym. Dla elementów x = 2, y = 3 ani x R y, ani y R x nie jest prawdziwe. Takie elementy nazywane są niezrównany
. Zwykle relację kolejności oznacza się przez £. W podanym przykładzie 0 £ 1 i 2 £ 2, ale nie jest prawdą, że 2 £ 3. Przykład 2 Pozwalać< – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество. Wywoływane są elementy x, y О X zbioru częściowo uporządkowanego (X, £). porównywalny
, jeśli x £ y lub y £ x. Zbiór częściowo uporządkowany (X, £) nazywany jest uporządkowane liniowo
Lub łańcuch
, jeśli dowolne dwa jego elementy są porównywalne. Zbiór z przykładu 2 będzie uporządkowany liniowo, ale zbiór z przykładu 1 nie. Nazywa się podzbiór A Í X częściowo uporządkowanego zbioru (X, £). ograniczony powyżej
, jeśli istnieje element x О X taki, że a £ x dla wszystkich a О A. Element x О X nazywa się największy
w X jeśli y £ x dla wszystkich y О X. Element x О X nazywany jest maksymalnym, jeśli nie ma elementów y О X różnych od x, dla którego x £ y. W przykładzie 1 elementy 2 i 3 będą maksymalne, ale nie największe. Podobnie zdefiniowany dolna granica
podzbiory, elementy najmniejsze i minimalne. W przykładzie 1 element 0 będzie zarówno najmniejszy, jak i minimalny. W przykładzie 2 0 również ma te właściwości, ale (w, £) nie ma ani elementu największego, ani maksymalnego.
Suma modulo 2, koniunkcja oraz stałe 0 i 1 tworzą funkcjonalnie kompletny układ, tj. utwórz algebrę - algebrę Zhegalkina. A=
Logika matematyczna bada podstawowe pojęcia składni (formy) i semantyki (treści) języka naturalnego. Rozważmy trzy główne obszary badań logiki matematycznej - logikę
Niech X1, X2, ..., Xn będą dowolnymi zmiennymi. Nazwiemy te zmienne zmiennymi podmiotowymi. Niech zmienna Cię ustawi
Rozważmy predykaty, w których tylko jedna zmienna jest wolna, co oznaczamy przez x, i omówmy użycie predykatów w algebrze. Typowy przykład
Ponieważ operacje logiczne można zastosować do predykatów, obowiązują dla nich podstawowe prawa algebry Boole'a. Twierdzenie. (Właściwości operacji logicznych dla predykatów). Mn
2. Skorzystaj z prawa nie F=F, prawa de Morgana: nie (F
Rachunek predykatów nazywany jest także teorią pierwszego rzędu. W rachunku predykatów, a także w rachunku zdań, na pierwszym miejscu najważniejsze jest zagadnienie rozwiązywalności.
Forma zdaniowa Q2 wynika z formy zdaniowej Q1, jeśli implikacja Q1 → Q2 stanie się prawdziwa
Symbole „nie zamawiaj więcej”. Porównując tempo wzrostu dwóch funkcji f(n) i g(n) (o wartościach nieujemnych), bardzo wygodne są poniższe
Symbole Treść Przykład LUB
x Ç y nie jest puste. Relacja posiadania wspólnego będzie zwrotna i symetryczna, ale nie przechodnia.
