Teorija skupova. Osnovni koncepti
Teorija skupova je osnovna definicija moderne matematike. Kreirao ga je Georg Cantor 1860-ih. Napisao je: „Mnogo je mnogo, zamišljeno kao jedna celina.“ Koncept skupa je jedan od osnovnih, nedefiniranih pojmova matematike. Ne može se svesti na druge, jednostavnije koncepte. Stoga se ne može definisati, već samo objasniti. Dakle, skup je ujedinjenje u jednu cjelinu objekata koji se jasno razlikuju po našoj intuiciji ili našem mišljenju; zbirka određenih objekata definisanih zajedničkom karakteristikom.
Na primjer,
1. Mnogi stanovnici Voronježa
2. Skup ravnih tačaka
3. Skup prirodnih brojeva ℕitd.
Skupovi se obično označavaju velikim latiničnim slovima ( A, B, C itd.). Objekti koji čine dati skup nazivaju se njegovim elementima. Elementi seta su označeni malim latiničnim slovima ( a, b, c itd.). Ako X– postavite, a zatim snimite x∈X znači da X je element skupa X ili šta X pripada skupu X, i unos x∉X taj element X ne pripada skupu X. Na primjer, neka je ℕ skup prirodnih brojeva. Onda 5 ℕ , A 0,5∉ℕ .
Ako je set Y sastoji se od elemenata skupa X, onda to kažu Y je podskup skupa X i označiti Y⊂H(ili Y⊆H). Na primjer, skup cijelih brojeva ℤ je podskup racionalnih brojeva ℚ .
Ako za dva seta X I Y dvije inkluzije se javljaju istovremeno X Y I Y X, tj. X je podskup skupa Y I Y je podskup skupa X, zatim skupovi X I Y sastoje se od istih elemenata. Takvi setovi X I Y nazivaju se jednaki i pišu: X=Y.
Često se koristi termin prazan skup - Ø - skup koji ne sadrži niti jedan element. To je podskup bilo kojeg skupa.
Sljedeće metode se mogu koristiti za opisivanje skupova.
Metode za specificiranje skupova
1. Nabrajanje objekata. Koristi se samo za konačne skupove.
Na primjer, X=(x1, x2, x3… x n). Zapis Y ={1, 4, 7, 5} znači da se skup sastoji od četiri broja 1, 4, 7, 5 .
2. Indikacija karakterističnog svojstva elemenata skupa.
U tu svrhu se postavlja određeno svojstvo R, koji vam omogućava da odredite da li element pripada skupu. Ova metoda je univerzalnija.
X=(x: P(x))
(gomila X sastoji se od takvih elemenata X, za koju imovina pripada P(x)).
Prazan skup se može specificirati specificiranjem njegovih svojstava: Ø=(x: x≠x)
Možete konstruisati nove skupove koristeći već definisane koristeći operacije na skupovima.
Postavite operacije
1. Unija (zbir) je skup koji se sastoji od svih onih elemenata, od kojih svaki pripada barem jednom od skupova A ili IN.
A∪B=(x: x A ili x B).
2. Presek (proizvod) je skup koji se sastoji od svih elemenata, od kojih svaki istovremeno pripada skupu A, i mnogi IN.
A∩B=(x: x A i x B).
3. Postavite razliku A I IN je skup koji se sastoji od svih onih elemenata koji pripadaju skupu A i ne pripadaju mnoštvu IN.
A\B=(x: x A i x B)
4. Ako A– podskup skupa IN. To je mnogo B\A nazvan komplement skupa A mnogo IN i označiti A'.
5. Simetrična razlika dva skupa je skup A∆B=(A\B) (B\A)
N- skup svih prirodnih brojeva;
Z- skup svih cijelih brojeva;
Q- skup svih racionalnih brojeva;
R- skup svih realnih brojeva;
C- skup svih kompleksnih brojeva;
Z 0- skup svih nenegativnih cijelih brojeva.
Svojstva operacija na skupovima:
1. A B=B A (komutativna unija)
2. A B=B A (komutativnost presjeka)
3. A(B C)=(A IN) C (sindikalna asocijativnost)
4. A (IN C)=(A IN) C (ukrštanje asocijativnosti)
5. A (IN C)=(A IN) (A C) (1. zakon distributivnosti)
6. A (IN C)=(A IN) (A C) (2. zakon distributivnosti)
7. A Ø=A
8. A U=U
9. A Ø= Ø
10. A U=A
11. (A B)'=A' B' (de Morganov zakon)
12. (A B)'=A' B' (de Morganov zakon)
13. A (A B)=A (zakon apsorpcije)
14. A (A B)=A (zakon apsorpcije)
Dokažimo svojstvo br. 11. (A B)'=A' IN'
Po definiciji jednakih skupova, moramo dokazati dvije inkluzije 1) (A B)’ ⊂A’ IN';
2) A' B’⊂(A IN)'.
Da biste dokazali prvo uključivanje, razmotrite proizvoljan element x∈(A B)’=X\(A∪B). To znači da x∈X, x∉ A∪B. Iz toga slijedi x∉A I x∉B, Zbog toga x∈X\A I x∈X\B, što znači x∈A’∩B’. dakle, (A B)’⊂A’ IN'
Natrag ako x∈A’ IN', To X istovremeno pripada skupovima A', B', što znači x∉A I x∉B. Iz toga slijedi x∉ A IN, Zbog toga x∈(A IN)'. dakle, A' B’⊂(A IN)'.
dakle, (A B)'=A' IN'
Skup koji se sastoji od dva elementa, u kojem je redoslijed elemenata definiran, naziva se uređenim parom. Da ga napišete, koristite zagrade. (x 1, x 2)– skup od dva elementa u kojem se x 1 smatra prvim elementom, a x 2 drugim. Parovi (x 1, x 2) I (x 2, x 1), Gdje x 1 ≠ x 2, smatraju se različitim.
Skup koji se sastoji od n elemenata, u kojem je definiran redoslijed elemenata, naziva se uređen skup od n elemenata.
Dekartov proizvod je proizvoljan skup X 1, X 2,…,X n uređenih skupova od n elemenata, gdje x 1 X 1 , x 2 X 2 ,…, x n X n
X 1 X n
Ako setovi X 1, X 2,…,X n match (X 1 = X 2 =…=X n), tada je njihov proizvod označen Xn.
Na primjer, ℝ 2 – skup uređenih parova realnih brojeva.
Relacije ekvivalencije. Faktorski skupovi
Na osnovu datog skupa, novi skupovi se mogu konstruisati razmatranjem skupa nekih podskupova. U ovom slučaju obično ne govorimo o skupu podskupova, već o porodici ili klasi podskupova.
U nizu pitanja razmatra se klasa takvih podskupova datog skupa A, koji se ne sijeku i čija se unija poklapa sa A. Ako je ovaj set A može se predstaviti kao unija njegovih parno disjunktnih podskupova, tada je uobičajeno reći da A podijeljeni na klase. Podjela na klase se vrši na osnovu neke karakteristike.
Neka X nije prazan skup, tada bilo koji podskup R od posla X X naziva se binarna relacija na skupu X. Ako par (x,y) uključeno u R, kažu da je element x u odnosu R With at.
Na primjer, odnosi x=y, x≥y su binarne relacije na skupu ℝ.
Binarna relacija R na setu X naziva se relacija ekvivalencije ako:
1. (x,x) R; X X (svojstvo refleksivnosti)
2. (x,y) R => (y,x) R (svojstvo simetrije)
3. (x,y) R, (y,z) R, tada (x,z) R (svojstvo tranzitivnosti)
Ako par (x,y) ušli u relacije ekvivalencije, tada se x i y nazivaju ekvivalentni (x~y).
1.Let ℤ – skup cijelih brojeva, m≥1– cijeli broj. Hajde da definišemo odnos ekvivalencije R on ℤ tako da n~k, Ako n-k podijeljena m. Provjerimo da li su svojstva zadovoljena na ovoj relaciji.
1. Refleksivnost.
Za bilo koga n∈ℤ ℤ takav da (p,p)∈R
r-r=0. Jer 0∈ ℤ , To (p,p)∈ℤ.
2. Simetrija.
Od (n,k) ∈R proizilazi da tako nešto postoji r∈ℤ, Šta n-k=mp;
k-n =m(-p), -p∈ ℤ, dakle (k,n) ∈R.
3. Tranzitivnost.
Iz onoga što (n,k) ∈R, (k,q) ∈R proizilazi da takvih ima p 1 I r 2 ∈ ℤ, Šta n-k=mp 1 I k-q=mp 2. Dodavanjem ovih izraza dobijamo to n-q=m(p 1 + p 2), p 1 + p 2 =p, p∈ ℤ. Zbog toga (n,q) ∈ ℤ.
2. Razmotrite skup X svi usmjereni segmenti prostora ili ravni . =(A, B). Hajde da uvedemo relaciju ekvivalencije R on X.
Postavite faktor
Mnoštvo.
Relacija parcijalnog reda na skupu x je binarna relacija koja je antisimetrična, refleksivna i tranzitivna i označava se sa
kao par:
Binarna relacija se naziva tolerancijom ako je refleksivna i simetrična.
Binarna relacija se naziva kvazi-redom ako je nerefleksivna, antisimetrična i tranzitivna (predred).
Binarna relacija se naziva strogim redom ako je refleksivna i tranzitivna.
Enarna algebarska operacija na skupu M je funkcija
– unarni rad;
– binarna operacija;
– trijaran rad.
Binarna algebarska operacija –
– operacija koja svakom uređenom paru iz skupa M dodjeljuje neki element skupa M.
Svojstva:
1) Komutativnost:
2) Asocijativnost:
Neutralni element
Skupovi M za binarne algebarske operacije
Element se zove:
Neka je R binarna relacija na skupu X. Relacija R se zove reflektirajuće , ako je (x, x) O R za sve x O X; simetrično – ako iz (x, y) O R slijedi (y, x) O R; tranzitivni broj 23 odgovara opciji 24 ako (x, y) O R i (y, z) O R impliciraju (x, z) O R.
Primjer 1
Reći ćemo da je x O X ima zajedničko
sa elementom y O X, ako je skup
x Ç y nije prazan. Zajednički odnos će biti refleksivan i simetričan, ali ne i tranzitivan.
Relacija ekvivalencije na X je refleksivna, tranzitivna i simetrična relacija. Lako je vidjeti da će R Í X ´ X biti relacija ekvivalencije ako i samo ako dođe do uključivanja:
Id X Í R (refleksivnost),
R -1 Í R (simetrija),
R ° R Í R (tranzitivnost).
U stvarnosti, ova tri uslova su ekvivalentna sledećem:
Id X Í R, R -1 = R, R ° R = R.
Cepanjem skupa X je skup A parno disjunktnih podskupova a Í X tako da je UA = X. Svakoj particiji A možemo pridružiti relaciju ekvivalencije ~ na X, stavljajući x ~ y ako su x i y elementi nekog a Î A .
Svaka relacija ekvivalencije ~ na X odgovara particiji A, čiji su elementi podskupovi, od kojih se svaki sastoji od onih u relaciji ~. Ovi podskupovi se nazivaju klase ekvivalencije . Ova particija A naziva se faktor skup skupa X u odnosu na ~ i označava se: X/~.
Definirajmo relaciju ~ na skupu w prirodnih brojeva, stavljajući x ~ y ako su ostaci od dijeljenja x i y sa 3 jednaki. Tada se w/~ sastoji od tri klase ekvivalencije koje odgovaraju ostatcima 0, 1 i 2.
Odnos reda
Poziva se binarna relacija R na skupu X antisimetrično , ako iz x R y i y R x slijedi: x = y. Poziva se binarna relacija R na skupu X odnos poretka , ako je refleksivan, antisimetričan i tranzitivan. Lako je vidjeti da je to ekvivalentno sljedećim uslovima:
1) Id X Í R (refleksivnost),
2) R Ç R -1 (antisimetrija),
3) R ° R Í R (tranzitivnost).
Poziva se uređeni par (X, R) koji se sastoji od skupa X i relacije reda R na X djelomično naručeni set .
Primjer 1
Neka je X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2 ), (1, 3), (2, 2), (3, 3)).
Pošto R zadovoljava uslove 1 – 3, onda je (X, R) djelimično uređen skup. Za elemente x = 2, y = 3, ni x R y ni y R x nisu istiniti. Takvi elementi se nazivaju neuporedivo . Obično se odnos reda označava sa £. U datom primjeru, 0 £ 1 i 2 £ 2, ali nije tačno da je 2 £ 3.
Primjer 2
Neka< – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество.
Pozivaju se elementi x, y O X djelomično uređenog skupa (X, £). uporedivi , ako je x £ y ili y £ x.
Poziva se djelomično uređen skup (X, £). linearno uređeno ili lanac , ako su bilo koja dva njegova elementa uporediva. Skup iz primjera 2 će biti linearno uređen, ali skup iz primjera 1 neće.
Poziva se podskup A Í X djelomično uređenog skupa (X, £). omeđen iznad , ako postoji element x O X takav da je a £ x za sve a O A. Element x O X se naziva najveća u X ako je y £ x za sve y O X. Element x O X se naziva maksimalnim ako ne postoje elementi y O X različiti od x za koje je x £ y. U primjeru 1, elementi 2 i 3 će biti maksimalni, ali ne i najveći. Slično definisano donja granica podskupovi, najmanji i minimalni elementi. U primjeru 1, element 0 će biti i najmanji i najmanji. U primjeru 2, 0 također ima ova svojstva, ali (w, £) nema ni najveći ni maksimalni element.
Neka je (X, £) djelomično uređen skup, A Í X podskup. Relacija na A, koja se sastoji od parova (a, b) elemenata a, b O A, za koje a £ b, biće relacija reda na A. Ova relacija je označena istim simbolom: £. Dakle, (A, £) je djelomično uređen skup. Ako je linearno uređen, onda ćemo reći da je A lanac u (X, £).
Maksimalni princip
Neke matematičke tvrdnje ne mogu se dokazati bez aksioma izbora. Za ove izjave se kaže da jesu zavisi od aksioma izbora ili vrijedi u ZFC teoriji , u praksi, umjesto aksioma izbora, za dokaz se obično koristi ili Zermelo aksiom, ili Kuratowski-Zornova lema, ili bilo koja druga izjava koja je ekvivalentna aksiomu izbora.
Lema Kuratowski-Zorn. Ako je svaki lanac u djelimično uređenom skupu(X, £) je ograničen odozgo, zatim unutra X postoji barem jedan maksimalni element.
Ova lema je ekvivalentna aksiomu izbora i stoga se može prihvatiti kao aksiom.
Teorema.Za bilo koji djelimično naručeni set(X, £) postoji relacija koja sadrži relaciju£ i transformacija X u linearno uređen skup.
Dokaz. Skup svih relacija reda koji sadrži relaciju £ uređen je inkluzivnom relacijom U. Pošto će unija lanca relacija reda biti relacija reda, onda prema lemi Kuratowski-Zorn postoji maksimalna relacija R takva da x £ y implicira x R y. Dokažimo da je R relacija linearnog reda X. Pretpostavimo suprotno: neka postoji a, b O X tako da ni (a, b) ni (b, a) ne pripadaju R. Razmotrimo relaciju:
R¢ = R È ((x, y): x Ra i b R y).
Dobiva se dodavanjem para (a, b) na R i parova (x, y), koji se moraju dodati R¢ iz uslova da je R¢ relacija reda. Lako je vidjeti da je R¢ refleksivan, antisimetričan i tranzitivan. Dobijamo R Ì R¢, što je u suprotnosti sa maksimalnošću R, dakle, R je željena relacija linearnog reda.
Linearno uređen skup X naziva se dobro uređenim ako svaki njegov neprazan podskup A Í X sadrži najmanji element a Î A. Lema Kuratowski-Zornova i aksiom izbora su također ekvivalentni sljedećem iskazu:
Zermelov aksiom. Za svaki skup postoji odnos reda koji ga pretvara u potpuno uređen skup.
Na primjer, skup w prirodnih brojeva je potpuno uređen. Princip induktivnosti je sažet na sljedeći način:
Transfinitna indukcija. Ako(X, £) je potpuno uređen skup i F(x) je svojstvo njegovih elemenata, tačno za najmanji element x 0 O X i takav da je iz istinitosti F(y) za sve y < z следует истинность F(z), то F(x) istina za sve x O X .
Evo y< z означает, что у £ z, но y ¹ z. Действительно, в противном случае среди x Î X, не обладающих свойством F(x), можно выбрать наименьший элемент x 1 , и выполнение F(y) для всех y < x 1 приводит к выполнению F(x 1), противоречащему предположению.
Koncept snage
Neka su f: X à Y i g: Y à Z mape skupova. Pošto su f i g relacije, njihov sastav je definisan g° f(x) = g(f(x)). Ako je h: Z à T mapa skupova, onda je h ° (g ° f) = (h ° g) ° f. Relacije Id X i Id Y su funkcije, stoga su definirane kompozicije Id Y ° f = f ° Id x = f. Za X = Y, definiramo f 2 = f ° f, f 3 = f 2 ° f, ..., f n+1 = f n ° f.
Poziva se preslikavanje f: X àY injekcijom , ako za bilo koji element x 1 ¹ x 2 skupa X vrijedi f(x 1) ¹ f(x 2). Preslikavanje f se zove surjekcija , ako za svako y OY postoji x O X takav da je f(x) = y. Ako je f i surjekcija i injekcija, tada se zove f bijekcija . Lako je vidjeti da je f bijekcija ako i samo ako je inverzna relacija f -1 Í Y ´ X funkcija.
Reći ćemo da je jednakost |X| = |Y|, ako postoji bijekcija između X i Y. Neka |X| £ |Y|, ako postoji injekcija f: X à Y.
Cantor-Schroeder-Bernstein teorem. Ako|X| £ |Y| I|Y| £ |X| , To|X| = |Y|.
Dokaz. Po uslovu, postoje injekcije f: X à Y i g: Y à X. Neka je A = g¢¢Y = Img slika skupa Y u odnosu na preslikavanje g. Onda
(X \ A) Ç (gf)¢¢(X \ A) = Æ,
(gf)¢¢(X \ A) Ç (gf) 2 ¢¢(X \ A) = Æ, …,
(gf) n ¢¢(X \ A) Ç (gf) n+1 ¢¢(X \ A) = Æ, …
Razmotrimo preslikavanje j: X à A, dato kao j(x) = gf(x), sa
x Î (X \ A) È (gf)¢¢(X \ A) È (gf) 2 ¢¢(X \ A) È …, i j(x) = x u drugim slučajevima. Lako je vidjeti da je j bijekcija. Potrebna bijekcija između X i Y će biti jednaka g -1 ° j.
Kantorova antinomija
Neka |X|< |Y|, если |X| £ |Y| и не существует биекции между X и Y.
Kantorova teorema. Za bilo koji skup X, |X|< |P(X)|, где P(X) – множество всех подмножеств множества X.
Sljedeće teoreme se mogu dokazati.
Teorema 1.4. Funkcija f ima inverznu funkciju f -1 ako i samo ako je f bijektivna.
Teorema 1.5. Kompozicija bijektivnih funkcija je bijektivna funkcija.
Rice. 1.12 prikazuje različite relacije, sve su, osim prve, funkcije.
stav, ali |
injekcija, ali |
surjekcija, ali |
||||||||||||||
nije funkcija |
nije surjekcija |
nije injekcija |
||||||||||||||
Neka je f : A→B funkcija, a skupovi A i B konačni skupovi, stavimo A = n, B = m. Dirichletov princip kaže da ako je n > m, onda se barem jedna vrijednost f javlja više puta. Drugim riječima, postoji par elemenata a i ≠ a j , a i , a j A za koje je f(a i )= f(a j ).
Dirichletov princip je lako dokazati, pa ga ostavljamo čitaocu kao trivijalnu vježbu. Pogledajmo primjer. Neka u grupi bude više od 12 učenika. Onda je očigledno da najmanje dvoje od njih imaju rođendan u istom mesecu.
Binarna relacija R na skupu A naziva se relacija ekvivalencije ako je R refleksivan, simetričan i tranzitivan.
Relacija jednakosti na skupu brojeva ima naznačena svojstva i stoga je relacija ekvivalencije.
Relacija sličnosti trougla je očigledno relacija ekvivalencije.
Nestroga relacija nejednakosti (≤ ) na skupu realnih brojeva neće biti relacija ekvivalencije, jer nije simetrična: iz 3≤ 5 ne slijedi da je 5≤ 3.
Klasa ekvivalencije (koset) koju generiše element a za datu relaciju ekvivalencije R je podskup onih x A koji su u relaciji R sa a. Navedena klasa ekvivalencije je označena sa [a]R, dakle, imamo:
[a] R = (x A: a, x R).
Pogledajmo primjer. Na skupu trouglova uvodi se odnos sličnosti. Jasno je da svi jednakostranični trouglovi spadaju u jedan koset, jer je svaki od njih sličan, na primjer, trokutu, čije sve stranice imaju jediničnu dužinu.
Teorema 1.6. Neka je R relacija ekvivalencije na skupu A i [a] R koset, tj. [a] R = (x A: a, x R), tada:
1) za bilo koji a A: [a] R ≠, posebno, a [a] R;
2) različiti kosetovi se ne seku;
3) unija svih koseta poklapa se sa celim skupom A;
4) skup različitih koseta čini particiju skupa A.
Dokaz. 1) Zbog refleksivnosti R, dobijamo da za bilo koje a, a A imamo a,a R, dakle a [a] R i [a] R ≠ ;
2) pretpostavimo da je [a] R ∩ [b] R ≠ , tj. postoji element c od A i c [a]R ∩ [b]R. Tada iz (cRa)&(cRb) zbog simetrije R dobijamo da (aR c)&(cRb), a iz tranzitivnosti R imamo aRb.
Za bilo koji x [a] R imamo: (xRa)&(aRb), tada zbog tranzitivnosti R dobijamo xRb, tj. x [b] R, dakle [a] R [b] R. Slično, za bilo koje y, y [b] R, imamo: (yRb)&(aRb), a zbog simetrije R dobijamo da (yRb)&(bR a), tada, zbog tranzitivnosti R , dobijamo da je yR a , tj. y [a] R i
dakle [b] R [a] R . Iz [ a ] R [ b ] R i [ b ] R [ a ] R dobijamo [ a ] R = [ b ] R , odnosno ako se kosetovi sijeku, onda se poklapaju;
3) za bilo koje a, a A, kao što je dokazano, imamo [a] R, tada se, očigledno, unija svih koseta poklapa sa skupom A.
Tvrdnja 4) teoreme 1.6 slijedi iz 1)-3). Teorema je dokazana. Sljedeća teorema se može dokazati.
Teorema 1.7. Različite relacije ekvivalencije na skupu A generiraju različite particije A.
Teorema 1.8. Svaka particija skupa A generiše relaciju ekvivalencije na skupu A, a različite particije generišu različite relacije ekvivalencije.
Dokaz. Neka je data particija B = (B i ) skupa A. Definirajmo relaciju R : a,b R ako i samo ako postoji a B i takvo da i a i b pripadaju ovom B i . Očigledno je da je uvedena relacija refleksivna, simetrična i tranzitivna, pa je R relacija ekvivalencije. Može se pokazati da ako su particije različite, onda su i relacije ekvivalencije koje one generiraju također različite.
Skup svih skupova skupa A u odnosu na datu relaciju ekvivalencije R naziva se faktor skup i označava se sa A/R. Elementi skupa faktora su koseti. Klasa koseta [a] R, kao što je poznato, sastoji se od elemenata A koji su u međusobnom odnosu R.
Razmotrimo primjer relacije ekvivalencije na skupu cijelih brojeva Z = (..., -3, -2, -1, 0, 1, 2, 3, ...).
Dva cijela broja a i b nazivaju se uporedivi (kongruentni) po modulu m ako je m djelitelj broja a-b, tj. ako imamo:
a=b+km , k=…, -3, -2, -1, 0, 1, 2, 3, ….
U ovom slučaju napišite a≡ b(mod m) .
Teorema 1.9. Za bilo koje brojeve a, b, c i m>0 imamo:
1) a ≡ a(mod m) ;
2) ako je a ≡ b(mod m), onda je b ≡ a(mod m);
3) ako je a ≡ b(mod m) i b ≡ c(mod m), onda je a ≡ c(mod m).
Dokaz. Izjave 1) i 2) su očigledne. Dokažimo 3). Neka je a=b+k 1 m, b=c+k 2 m, zatim a=c+(k 1 +k 2)m, tj. a ≡ c(mod m) . Teorema je dokazana.
Dakle, relacija uporedivosti po modulu m je relacija ekvivalencije i dijeli skup cijelih brojeva u disjunktne klase brojeva.
Napravimo spiralu koja se beskrajno odmotava, što je prikazano na Sl. 1.13 je prikazana kao puna linija, a spirala koja se beskrajno uvija je prikazana kao isprekidana linija. Neka je dan nenegativni cijeli broj m. Postavićemo sve cele brojeve (elemente iz skupa Z) u tačke preseka ovih spirala sa m zrakama, kao što je prikazano na sl. 1.13.
Za relaciju uporedivosti po modulu m (posebno za m =8), klasa ekvivalencije su brojevi koji leže na zraku. Očigledno, svaki broj spada u jednu i samo jednu klasu. Može se dobiti da za m= 8 imamo:
[ 0] ={…, -8, 0, 8, 16, …}; |
|||||
[ 1] ={…, -7, 1, 9, 17, …}; |
|||||
[ 2] ={…, -6, 2, 10, 18, …}; |
|||||
[ 7] ={…, -9, -1, 7, 15, …}. |
|||||
Faktorski skup skupa Z u odnosu na poređenje po modulu m označava se kao Z/m ili kao Z m. Za slučaj koji se razmatra m =8
dobijamo da je Z/8 = Z8 = ( , , , …, ) .
Teorema 1.10. Za bilo koje cijele brojeve a, b, a*, b*, k i m:
1) ako je a ≡ b(mod m), onda je ka ≡ kb(mod m);
2) ako je a ≡ b(mod m) i a* ≡ b* (mod m), tada:
a) a+a * ≡ b+b* (mod m); b) aa * ≡ bb* (mod m).
Predstavljamo dokaz za slučaj 2b). Neka je a ≡ b(mod m) i a * ≡ b * (mod m), zatim a=b+sm i a * =b * +tm za neke cijele brojeve s i t. Množenje
dobijamo: aa* =bb* + btm+ b* sm+ stm2 =bb* +(bt+ b* s+ stm)m. dakle,
aa* ≡ bb* (mod m).
Dakle, modulo poređenja se mogu sabirati i množiti pojam po član, tj. rade na potpuno isti način kao i sa jednakostima. Na primjer,
Ako je stav R ima sljedeća svojstva: refleksivna simetrična tranzitivna, tj. je relacija ekvivalencije (~ ili ≡ ili E) na skupu M , tada se skup klasa ekvivalencije naziva skup faktora skupa M u pogledu ekvivalencije R i određen je GOSPODIN
Postoji podskup elemenata skupa M ekvivalentan x , zvao klasa ekvivalencije.
Iz definicije skupa faktora slijedi da je on podskup Booleovog: .
Funkcija se poziva identifikaciju i definira se na sljedeći način:
Teorema. Faktorska algebra F n /~ je izomorfna algebri Bulovih funkcija B n
Dokaz.
Traženi izomorfizam ξ : F n / ~ → B n je određen sljedećim pravilom: klasa ekvivalencije ~(φ) funkcija je usklađena f φ , ima tabelu istinitosti za proizvoljnu formulu iz skupa ~(φ) . Pošto različite klase ekvivalencije odgovaraju različitim tabelama istinitosti, preslikavanje ξ injektivna, i budući da za bilo koju Booleovu funkciju f od U str postoji formula koja predstavlja funkciju f, zatim mapiranje ξ surjektivni. Operacije memorisanja, 0, 1 kada je prikazano ξ se provjerava direktno. CTD.
Po teoremu o funkcionalnoj potpunosti svake funkcije koja nije konstanta 0 , odgovara nekom SDNF-u ψ , koji pripada klasi ~(φ) = ξ -1 (f) formule koje predstavljaju funkciju f . Pojavljuje se problem boravka u učionici ~(φ) disjunktivni normalni oblik, koji ima najjednostavniju strukturu.
Kraj rada -
Ova tema pripada sekciji:
Moskovski državni univerzitet građevinarstva.. Institut za ekonomiju menadžmenta i informacione sisteme u građevinarstvu.. IEEE..
Ako vam je potreban dodatni materijal na ovu temu, ili niste pronašli ono što ste tražili, preporučujemo da koristite pretragu u našoj bazi radova:
Ako vam je ovaj materijal bio koristan, možete ga spremiti na svoju stranicu na društvenim mrežama:
| Tweet |
Predmet diskretne matematike
Predmet diskretne (konačne, konačne) matematike je grana matematike koja proučava svojstva diskretnih struktura, dok klasična (kontinuirana) matematika proučava svojstva objekata.
Izomorfizam
Nauka koja proučava algebarske operacije naziva se algebra. Ovaj koncept će postati konkretniji i produbiti se kako budete proučavali kurs. Algebru zanima samo pitanje KAKO postupiti
Vježbe
1. Dokažite da je izomorfno preslikavanje uvijek izotonsko, a obrnuto nije tačno. 2. Napišite svoju grupu na jeziku skupova. 3. Zapišite na jeziku skupova objekte koji
Skup i elementi skupa
Trenutno se postojeće teorije skupova razlikuju po paradigmatici (sistemu pogleda) konceptualne osnove i logičkih sredstava. Dakle, kao primjer možemo navesti dvije suprotne
Konačni i beskonačni skupovi
Ono od čega se skup sastoji, tj. Objekti koji čine skup nazivaju se njegovim elementima. Elementi skupa su različiti i različiti jedni od drugih. Kao što se može vidjeti iz navedenih primjera
Snaga seta
Kardinalnost za konačni skup jednaka je broju njegovih elemenata. Na primjer, kardinalnost univerzuma B(A) skupa A kardinalnosti n
A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |An-2An-1An| + (-1)n-1 |A1A2A3…An|
Konačan skup A ima kardinalnost k ako je jednak segmentu 1.. k;:
Podskup, vlastiti podskup
Nakon što se uvede pojam skupa, postavlja se zadatak konstruisanja novih skupova od postojećih, odnosno definisanja operacija nad skupovima. "više M"
Simbolički jezik smislenih teorija skupova
U procesu izučavanja predmeta pravićemo razliku između objektnog jezika teorije skupova i metajezika pomoću kojeg se predmetni jezik proučava. Pod jezikom teorije skupova mislimo na relaciju
Dokaz
Skup B je beskonačan, što znači
Dodavanje i uklanjanje stavki
Ako je A skup, a x je element, a zatim element
Ograničeni skupovi. Postavite granice
Neka je numerička funkcija f(x) data na nekom skupu X. Gornja granica (granica) funkcije f(x) je takav broj
Tačna gornja (donja) granica
Skup svih gornjih granica E označava se sa Es, a sve donje granice sa Ei. U slučaju
Tačna gornja (donja) granica skupa
Ako element z pripada presjeku skupa E i skupa svih njegovih gornjih granica Es (odnosno donjih r
Osnovna svojstva gornjih i donjih granica
Neka je X djelomično uređen skup. 1. Ako, onda
Postavljeno sa atributivne tačke gledišta
Agregatno gledište, za razliku od atributivnog, logično je neodrživo u smislu da dovodi do paradoksa tipa Russell i Cantor (vidi dolje). U okviru atributivnog t
Struktura
Djelomično uređen skup X naziva se struktura ako sadrži bilo koji skup od dva elementa
Kompleti za pokrivanje i pregrađivanje
Particija skupa A je porodica Ai
Binarni odnosi
Niz dužine n, čiji su članovi a1, .... an, biće označen sa (a1, .... a
Svojstva binarnih relacija
Binarna relacija R na skupu Ho ima sledeća svojstva: (a) refleksivna ako je xRx
Ternarni odnosi
Dekartov proizvod XY
N-arne relacije
Po analogiji sa kartezijanskim proizvodom dva skupa X,Y, možemo konstruisati kartezijanski proizvod X
Displeji
Preslikavanja su neke veze između elemenata skupova. Najjednostavniji primjeri relacija su odnosi članstva x
Prepiska
Podskup S kartezijanskog proizvoda naziva se n-arna korespondencija elemenata skupova Mi. Formalno
Funkcija
Sve grane diskretne matematike zasnivaju se na konceptu funkcije. Neka X -
Predstavljanje funkcije u smislu odnosa
Binarna relacija f naziva se funkcijom ako je iz i
Injekcija, surjekcija, bijekcija
Kada se koristi izraz "mapiranje", pravi se razlika između mapiranja XbY i mapiranja X na Y
Inverzna funkcija
Za proizvoljne definišemo
Djelomično naručeni setovi
Skup S se naziva djelomično uređen (PUM) ako mu je data refleksivna, tranzitivna i antisimetrična binarna relacija parcijalnog reda
Postavite minimizaciju reprezentacije
Koristeći ove zakone, razmatramo problem minimiziranja reprezentacije skupa M pomoću operacija
Preuređenja
Dat je skup A. Neka je A konačan skup koji se sastoji od n elemenata A = (a1, a2, …, a
Permutacije s ponavljanjima
Neka skup A ima identične (ponavljajuće) elemente. Permutacija sa ponavljanjem kompozicije (n1, n2, … ,nk
Placements
Torke dužine k (1≤k≤n), koje se sastoje od različitih elemenata skupa n elemenata A (torke se razlikuju po
Položaji sa ponavljanjima
Neka skup A ima identične (ponavljajuće) elemente. Položaji sa ponavljanjem n elemenata od k imena
Uredno postavljanje
Postavimo n objekata u m kutija tako da svaka kutija sadrži sekvencu, a ne, kao ranije, skup objekata koji se nalaze u njemu. Dva
Kombinacije
Iz m-elementnog skupa A konstruiramo uređeni skup dužine n, čiji su elementi aranžmani s istim temama
Kombinacije sa ponavljanjima
Rezultirajuće formule važe samo kada u skupu A nema identičnih elemenata. Neka postoje elementi od n tipova i od njih torka od
Metoda generiranja funkcije
Ova metoda se koristi za nabrajanje kombinatornih brojeva i uspostavljanje kombinatornih identiteta. Polazna tačka je kombinator sekvence (ai).
Algebarski sistem
Algebarski sistem A je kolekcija ‹M,O,R›, čija je prva komponenta M neprazan skup, druga komponenta O je skup
Zatvaranje i podalgebre
Za podskup se kaže da je zatvoren pod operacijom φ if
Algebre sa jednom binarnom operacijom
Neka je jedna binarna operacija data na skupu M. Razmotrimo algebre koje generiše, ali prvo ćemo razmotriti neka svojstva binarnih operacija. Binarno o
Groupoid
Algebra oblika<М, f2>nazvana groupoid. Ako je f2 operacija poput množenja (
Cijeli brojevi po modulu m
Dat je prsten cijelih brojeva
Kongruencije
Kongruencija na algebri A =
Elementi teorije grafova
Grafovi su matematički objekti. Teorija grafova se koristi u oblastima kao što su fizika, hemija, teorija komunikacija, kompjuterski dizajn, elektrotehnika, mašinstvo, arhitektura, istraživanje
Graf, vrh, ivica
Pod neusmjerenim grafom (ili, ukratko, grafom) podrazumijevamo takav proizvoljni par G =
Prepiska
Drugi, češće korišteni opis usmjerenog grafa G sastoji se od specificiranja skupa vrhova X i korespondencije G,
Neusmjereni graf
Ako rubovi nemaju orijentaciju, tada se graf naziva neusmjerenim (neusmjerenim duplikat ili neorijentiranim
Incidencija, mješoviti graf
Ako rub e ima oblik (u, v) ili<и, v>, tada ćemo reći da je ivica e incidentna ver
Obrnuto podudaranje
Pošto predstavlja skup takvih vrhova
Izomorfizam grafa
Dva grafikona G1 =
Putno orijentisana ruta
Put (ili usmjerena ruta) usmjerenog grafa je niz lukova u kojima
Susedni lukovi, susedni vrhovi, stepen vrha
Lukovi a = (xi, xj), xi ≠ xj, imaju zajedničke krajnje vrhove, n
Povezivanje
Dva vrha u grafu nazivaju se povezanim ako postoji jednostavan put koji ih povezuje. Graf se naziva povezanim ako su svi njegovi vrhovi povezani. Teorema.
Ponderisani lučni graf
Graf G = (N, A) naziva se težinskim ako je neka funkcija l: A → R definirana na skupu lukova A tako da je
Jaka matrica povezivanja
Jaka matrica povezivanja: stavite 1 duž dijagonale; popuniti red X1 - ako je vrh dostupan iz X1 i X1 d
Drveće
Stabla su važna ne samo zato što nalaze primjenu u različitim oblastima znanja, već i zato što imaju posebnu poziciju u samoj teoriji grafova. Ovo posljednje je uzrokovano ekstremnom jednostavnošću strukture drveta
Svako netrivijalno stablo ima najmanje dva viseća vrha
Dokaz Razmotrimo stablo G(V, E). Dakle, drvo je povezan graf
Teorema
Centar slobodnog stabla sastoji se od jednog vrha ili dva susjedna vrha: Z(G) = 0&k(G) = 1 → C(G) = K1
Usmjerena, uređena i binarna stabla
Usmjerena (uređena) stabla su apstrakcija hijerarhijskih odnosa koji se vrlo često susreću kako u praktičnom životu tako i u matematici i programiranju. stablo (orijentacija)
Dokaz
1. Svaki luk ulazi u neki čvor. Iz klauzule 2 definicije 9.2.1 imamo: v
Naručeno drveće
Skupovi T1,..., Tk u ekvivalentnoj definiciji orderev su podstabla. Ako je relativni poredak podstabala T1,...,
Binarna stabla
Binarno (ili binarno) stablo je konačan skup čvorova koji je ili prazan ili se sastoji od korijena i dva disjunktna binarna stabla - lijevo i desno. Binarno stablo nije u Javi
Besplatno predstavljanje drveta
Za predstavljanje stabala možete koristiti iste tehnike kao i za predstavljanje općih grafova - matrice susjedstva i incidencije, liste susjedstva i druge. Ali koristeći posebna svojstva
Kraj za
Obrazloženje Prüferov kod je zaista slobodan prikaz stabla. Da bismo to vidjeli, pokažimo da ako je T" drvo
Predstavljanje binarnih stabala
Svako slobodno stablo može se orijentirati označavanjem jednog od njegovih čvorova kao korijena. Bilo koja narudžba se može naručiti proizvoljno. Za potomke jednog čvora (braću) uređenog reda definira se relativno
Osnovne logičke funkcije
Označimo sa E2 = (0, 1) skup koji se sastoji od dva broja. Brojevi 0 i 1 su osnovni u diskretnoj prostirci
Boolean funkcija
Booleova funkcija od n argumenata x1, x2, … ,xn je funkcija f iz n-tog stepena skupa
Bulova algebra sa dva elementa
Razmotrimo skup Vo = (0,1) i definišemo operacije na njemu, prema tabelama izvora
Tablice Bulove funkcije
Booleova funkcija od n varijabli može se specificirati pomoću tablice koja se sastoji od dvije kolone i 2n reda. U prvoj koloni su navedeni svi skupovi iz B
F5 – ponoviti u y
f6 – zbir po modulu 2 f7
Redoslijed operacija
Ako u složenom izrazu nema zagrada, tada se operacije moraju izvesti sljedećim redoslijedom: konjunkcija, disjunkcija, implikacija, ekvivalencija, negacija. Konvencije koje se odnose na raspored Šenonove prve teoreme
Da bismo riješili problem pronalaženja SDNF i SCNF ekvivalentnih originalnoj formuli φ, prvo ćemo razmotriti proširenja Booleove funkcije f(x1, x2
Šenonova druga teorema
Na osnovu principa dualnosti, teorema 6.4.3 (Shannonova druga teorema) vrijedi za Bulove algebre. Bilo koja Booleova funkcija f(x1, x2,...
Funkcionalna kompletnost
Teorema (o funkcionalnoj potpunosti). Za bilo koju Bulovu funkciju f postoji formula φ koja predstavlja funkciju f
Algoritam za pronalaženje sdnf-a
Da bi se pronašao SDNF, ova formula se prvo mora svesti na DNF, a zatim transformirati njene konjunkte u sastavne dijelove jedinice koristeći sljedeće radnje: a) ako konjunkt uključuje neke
Quineova metoda
Razmotrimo Quineovu metodu za pronalaženje MDNF-a koji predstavlja datu Booleovu funkciju. Definirajmo sljedeće tri operacije: - potpuna operacija lijepljenja -
Kanonski prikaz logičkih funkcija
Kanonski oblici logičkih funkcija (formule) su izrazi koji imaju standardni oblik Bulove formule tako da jedinstveno predstavlja logičku funkciju. U algebri
Sistemi Bulovih funkcija
Neka Bulove funkcije f(g1, g2, …, gm) i g1(x1, x2, …, xn), g2(x1
Zhegalkinova osnova
Hajde da ga isprobamo. Potpuna je, jer se svaka funkcija iz standardne osnove izražava u terminima
Postova teorema
Postova teorema postavlja neophodne i dovoljne uslove za kompletnost sistema Bulovih funkcija. (Post E.L. Interaktivni sistemi matematičke logike sa dve vrednosti. – Annals of Math. Stu
Dokaz
Nužnost. Od suprotnog. Neka bude
Zhegalkin algebra Propoziciona logika Definicija predikata Primjena predikata u algebri Bulova predikatska algebra F↔G=(F→G)(G→F), F→G=ne FG Predikatski račun Praćenje i ekvivalencija Prihvaćene notacije Meta oznake
Zbir po modulu 2, konjunkcija i konstante 0 i 1 čine funkcionalno kompletan sistem, tj. formiraju algebru - Zhegalkin algebra. A=
Matematička logika proučava osnovne koncepte sintakse (forme) i semantike (sadržaja) prirodnog jezika. Razmotrimo tri glavna područja istraživanja matematičke logike – logiku
Neka su X1, X2, ..., Xn proizvoljne varijable. Ove varijable ćemo zvati subjektne varijable. Neka vas varijabla postavlja
Razmotrimo predikate u kojima je samo jedna varijabla slobodna, koju označavamo sa x, i razmotrimo upotrebu predikata u algebri. Tipičan primjer
Kako se logičke operacije mogu primijeniti na predikate, za njih vrijede osnovni zakoni Bulove algebre. Teorema. (Svojstva logičkih operacija za predikate). Mn
2. Koristite zakon ne ne F=F, de Morganove zakone: ne (F
Predikatski račun se također naziva teorijom prvog reda. U predikatskom, kao iu propozicionom računu, prvo najvažnije mjesto je problem rješivosti.
Propozicioni oblik Q2 slijedi iz iskaznog oblika Q1 ako implikacija Q1→Q2 postane istinita
Simboli "ne naruči više". Kada se uporedi brzina rasta dviju funkcija f(n) i g(n) (sa nenegativnim vrijednostima), sljedeće je vrlo zgodno
Simboli Sadržaj Primjer ILI
