Olkoon R binäärirelaatio joukossa X. Relaatiota R kutsutaan heijastava , jos (x, x) О R kaikille x О X; symmetrinen – jos (x, y) О R tarkoittaa (y, x) О R; transitiivinen luku 23 vastaa varianttia 24, jos (x, y) Î R ja (y, z) Î R tarkoittavat (x, z) Î R.

Esimerkki 1

Sanomme, että x н X on yhteistä alkiolla y н X, jos joukko
x З y ei ole tyhjä. Suhde yhteiseen on refleksiivinen ja symmetrinen, mutta ei transitiivinen.

Ekvivalenssisuhde X:tä kutsutaan refleksiiviseksi, transitiiviseksi ja symmetriseksi suhteeksi. On helppo nähdä, että R Н X ´ X on ekvivalenssisuhde, jos ja vain, jos sisällytykset tapahtuvat:

Id X Í R (heijastuskyky),

R -1 Í R (symmetria),

R ° R Í R (transitiivisuus).

Itse asiassa nämä kolme ehtoa vastaavat seuraavia:

Id X Í R, R -1 = R, R ° R = R.

jakaminen joukko X on pareittain hajallaan olevien osajoukkojen a н X joukko A siten, että UA = X. A:n jokaiseen osioon voidaan liittää ekvivalenssirelaatio ~ X:ään asettamalla x ~ y, jos x ja y ovat jonkin a н A elementtejä. .

Jokaiselle ekvivalenssirelaatiolle ~ X:ssä vastaa osio A, jonka elementit ovat osajoukkoja, joista jokainen koostuu suhteessa ~ olevista. Näitä osajoukkoja kutsutaan vastaavuusluokat . Tätä osiota A kutsutaan joukon X tekijäjoukoksi suhteessa ~ ja se merkitään seuraavasti: X/~.

Määritellään relaatio ~ luonnollisten lukujen joukolle w asettamalla x ~ y, jos jäännökset x:n ja y:n 3:lla jakamisen jälkeen ovat yhtä suuret. Sitten w/~ koostuu kolmesta ekvivalenssiluokasta, jotka vastaavat jäännöksiä 0, 1 ja 2.

Tilaussuhde

Kutsutaan joukon X binäärirelaatiota R antisymmetrinen , jos kohdista x R y ja y R x seuraa: x = y. Kutsutaan joukon X binäärirelaatiota R tilaussuhde , jos se on refleksiivinen, antisymmetrinen ja transitiivinen. On helppo nähdä, että tämä vastaa seuraavia ehtoja:

1) Id X Í R (heijastus),

2) R Ç R -1 (antisymmetria),

3) R ° R Í R (transitiivisuus).

Kutsutaan järjestyspari (X, R), joka koostuu joukosta X ja järjestysrelaatiosta R X:llä osittain tilattu setti .

Esimerkki 1

Olkoon X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2) ), (1, 3), (2, 2), (3, 3)).

Koska R täyttää ehdot 1–3, niin (X, R) on osittain järjestetty joukko. Elementeille x = 2, y = 3, ei x R y eikä y R x ole tosi. Tällaisia ​​elementtejä kutsutaan vertaansa vailla . Yleensä tilaussuhde merkitään £:lla. Yllä olevassa esimerkissä 0 £ 1 ja 2 £ 2, mutta ei pidä paikkaansa, että 2 £ 3.

Esimerkki 2

Antaa< – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество.

Osittain järjestetyn joukon (X, £) alkiot x, y О X kutsutaan vertailukelpoinen , jos x £ y tai y £ x.

Osittain tilattu joukko (X, £) kutsutaan lineaarisesti järjestetty tai ketju jos kaksi sen elementtiä ovat vertailukelpoisia. Esimerkin 2 joukko järjestetään lineaarisesti, mutta esimerkin 1 joukko ei.

Osittain järjestetyn joukon (X, £) osajoukkoa A Í X kutsutaan rajattu ylhäältä , jos on olemassa elementti x н X siten, että £ x kaikille н A:lle. Alkiota x н X kutsutaan suurin X:ssä, jos y £ x kaikille y О X. Alkiota x О X kutsutaan maksimaaliksi, jos siinä ei ole alkioita y О X, jotka eroavat x:stä, jolle x £ y. Esimerkissä 1 elementit 2 ja 3 ovat suurimmat, mutta eivät suurimmat. The pohjarajoitus osajoukot, pienin ja vähimmäiselementti. Esimerkissä 1 elementti 0 olisi sekä pienin että pienin. Esimerkissä 2 myös 0:lla on nämä ominaisuudet, mutta (w, t):llä ei ole suurinta eikä maksimialkiota.

Olkoon (X, £) osittain järjestetty joukko, A Í X osajoukko. A:n relaatio, joka koostuu pareista (a, b) elementeistä a, b Î A, joille a £ b, on järjestysrelaatio A:ssa. Tätä relaatiota merkitään samalla symbolilla: £. Siten (A, £) on osittain järjestetty joukko. Jos se on lineaarisesti järjestetty, niin sanomme, että A on ketju (X, £).

Maksimiperiaate

Joitakin matemaattisia väitteitä ei voida todistaa ilman valinnan aksioomaa. Näiden lausuntojen sanotaan olevan riippuu valinnan aksioomista tai voimassa ZFC teoriassa Käytännössä valinnan aksiooman sijasta käytetään yleensä todistukseksi joko Zermelon aksioomaa tai Kuratovsky-Zornin lemmaa tai mitä tahansa muuta valinnan aksioomaa vastaavaa väitettä.

Kuratowski-Zornin Lemma. Jos jokainen ketju osittain tilatussa sarjassa(X, £) rajattu siis ylhäältä X on vähintään yksi enimmäiselementti.

Tämä lemma vastaa valinnan aksioomaa ja siksi sitä voidaan pitää aksioomana.

Lause.Kaikille osittain tilatuille seteille(X, £) on relaatio, joka sisältää suhteen£ ja muuttava X lineaarisesti järjestetyksi joukoksi.

Todiste. Kaikkien järjestysrelaatioiden joukko, joka sisältää suhteen £, on järjestetty inkluusiorelaatiolla U. Koska järjestyssuhteiden ketjun liitto on järjestysrelaatio, niin Kuratowski-Zorn-lemman mukaan on olemassa maksimirelaatio R siten, että x £ y tarkoittaa x R y:tä. Osoitetaan, että R on lineaarisesti X järjestettävä relaatio. Oletetaan päinvastoin: olkoon a, b н X sellainen, ettei (a, b) eikä (b, a) kuulu R:lle. Tarkastellaan suhdetta:

R¢ = RÈ ((x, y): x Ra ja b Ry).

Se saadaan lisäämällä pari (a, b) R:ään ja parit (x, y), jotka on lisättävä R¢:ään ehdolla, että R¢ on järjestysrelaatio. On helppo nähdä, että R¢ on refleksiivinen, antisymmetrinen ja transitiivinen. Saadaan R Ì R¢, mikä on ristiriidassa R:n maksimaalisuuden kanssa, joten R on haluttu lineaarinen järjestyssuhde.

Lineaarisesti järjestettyä joukkoa X kutsutaan hyvin järjestetyksi, jos jokin sen ei-tyhjistä osajoukoista A н X sisältää pienimmän alkion a н A. Kuratowski-Zornin lemma ja valinnan aksiooma vastaavat myös seuraavaa lausetta:

Zermelon aksiooma. Jokaiselle joukolle on järjestyssuhde, joka muuttaa sen hyvin järjestetyksi joukoksi.

Esimerkiksi luonnollisten lukujen joukko w on hyvin järjestetty. Induktanssin periaate on tiivistetty seuraavasti:

Transfiniittinen induktio. Jos(X, £) on hyvin järjestetty joukko ja F(x) on sen elementtien ominaisuus, tosi pienimmälle alkiolle x 0 н X ja siten, että F(y):n totuudesta kaikille y:lle < z следует истинность F(z), то F(x) totta kaikille x О X .

Täällä y< z означает, что у £ z, но y ¹ z. Действительно, в противном случае среди x Î X, не обладающих свойством F(x), можно выбрать наименьший элемент x 1 , и выполнение F(y) для всех y < x 1 приводит к выполнению F(x 1), противоречащему предположению.

Vallan käsite

Olkoon f: X à Y ja g: Y à Z asetettu mappaukset. Koska f ja g ovat suhteita, niiden koostumus g ° f(x) = g(f(x)) on määritelty. Jos h: Z à T on joukkokuvaus, niin h ° (g ° f) = (h ° g) ° f. Relaatiot Id X ja Id Y ovat funktioita, joten koostumukset Id Y ° f = f ° Id x = f on määritelty. Kun X = Y, määritämme f 2 = f ° f, f 3 = f 2 ° f, ..., f n+1 = f n ° f.

Kuvaus f: X àY kutsutaan injektio , jos f(x 1) ¹ f(x 2) on tosi kaikille joukon X alkioille x 1 ¹ x 2. Kartoitusta f kutsutaan surjektio , jos jokaiselle y нY:lle on olemassa x н X siten, että f(x) = y. Jos f on sekä surjektio että injektio, kutsutaan f:tä näkemys . On helppo nähdä, että f on bijektio silloin ja vain jos käänteinen suhde f -1 н Y ´ X on funktio.

Sanomme, että yhtälö |X| = |Y|, jos X:n ja Y:n välillä on bijektio. Laita |X| £ |Y| jos on injektio f: X à Y.

Cantor-Schroeder-Bernstein-lause. Jos|X| £ |Y| Ja|Y| £ |X| , Tuo|X| = |Y|.

Todiste. Oletuksena on, että on injektiot f: X à Y ja g: Y à X. Olkoon A = g¢¢Y = Img Y:n kuva g:n suhteen. Sitten

(X \ A) Ç (gf)¢¢(X \ A) = Æ,

(gf)¢¢(X \ A) Ç (gf) 2 ¢¢(X \ A) = Æ, …,

(gf) n ¢¢(X \ A) Ç (gf) n+1 ¢¢(X \ A) = Æ, …

Tarkastellaan kuvausta j: X à A määritelty j(x) = gf(x) kanssa

x н (X \ A) È (gf)¢¢(X \ A) È (gf) 2 ¢¢(X \ A) È … ja j(x) = x muuten. On helppo nähdä, että j on bijektio. Haluttu bijektio X:n ja Y:n välillä on g -1 °j.

Kantorin antinomia

Asetetaan |X|< |Y|, если |X| £ |Y| и не существует биекции между X и Y.

Kantorin lause. Mille tahansa joukolle X, |X|< |P(X)|, где P(X) – множество всех подмножеств множества X.

(eli jolla on seuraavat ominaisuudet: joukon jokainen elementti vastaa itseään; jos x vastaava y, Tuo y vastaava x; Jos x vastaava y, A y vastaava z, Tuo x vastaava z ).

Sitten kutsutaan kaikkien ekvivalenssiluokkien joukkoa tekijä asetettu ja on merkitty. Joukon osiointia vastaavien elementtien luokkiin kutsutaan joukoksi faktorointi.

Näyttö alkaen X kutsutaan ekvivalenssiluokkien joukkoon tekijäkartoitus.

Esimerkkejä

On järkevää käyttää joukkokerrointa, jotta saadaan normaaleja puolinormiavaruuksista, sisätuloavaruuksia lähes sisätuloista jne. Tätä varten otetaan käyttöön vastaavasti luokan normi, joka on yhtä suuri kuin luokan normi. sen mielivaltainen elementti ja luokkien skalaaritulo luokkien mielivaltaisten elementtien skalaaritulona. Ekvivalenssisuhde puolestaan ​​​​otetaan käyttöön seuraavasti (esimerkiksi normoidun osamääräavaruuden muodostamiseksi): otetaan käyttöön alkuperäisen puolinormoidun avaruuden osajoukko, joka koostuu elementeistä, joilla on nolla puolinormi (muuten, se on lineaarinen eli se on aliavaruus) ja kahden elementin katsotaan olevan ekvivalentteja, jos niiden ero kuuluu tähän samaan aliavaruuteen.

Jos lineaarisen avaruuden faktorointiin otetaan käyttöön tietty lineaariavaruuden aliavaruus ja oletetaan, että jos alkuperäisen avaruuden kahden elementin ero kuuluu tähän aliavaruuteen, niin nämä elementit ovat ekvivalentteja, niin tekijäjoukko on lineaariavaruus ja kutsutaan tekijäavaruudeksi.

Esimerkkejä

Katso myös

Wikimedia Foundation. 2010 .

Katso, mitä "Factorset" on muissa sanakirjoissa:

Looginen periaate, joka perustuu määritelmiin abstraktion kautta (katso Määritelmä abstraktion kautta): mikä tahansa tasa-arvon tyyppinen suhde, joka on määritelty jollekin alkuelementtijoukolle, jakaa (jakaa, luokittelee) alkuperäisen ... ...

Ajattelun muoto, joka heijastaa esineiden ja ilmiöiden oleellisia ominaisuuksia, yhteyksiä ja suhteita niiden ristiriitaisuudessa ja kehityksessä; ajatus tai ajatusjärjestelmä, joka yleistää, erottaa tietyn luokan esineitä tietyn yleisen mukaan ja kokonaisuutena ... ... Suuri Neuvostoliiton tietosanakirja

Galois-ryhmän kohomologia. Jos M on Abelin ryhmä ja M:ään vaikuttavan laajennuksen Galois-ryhmä, niin Galois-kohomologia on kompleksin määrittelemä kohemologiaryhmä, joka koostuu kaikista kartoituksista, ja d on rinnakkaisoperaattori (katso Ryhmäkohomologia). Matemaattinen tietosanakirja

Rai-konstruktio ilmestyi ensin joukkoteoriassa, ja sitten sitä käytettiin laajalti algebrassa, topologiassa ja muilla matematiikan aloilla. Tärkeä I.P:n erityistapaus on samantyyppisten matemaattisten rakenteiden ohjatun perheen I.P. Anna olla … Matemaattinen tietosanakirja

Pisteet suhteessa ryhmään G, joka vaikuttaa joukkoon X (vasemmalla), joukko A joukko on G:n aliryhmä ja sitä kutsutaan. stabilisaattori tai pisteen kiinteä aliryhmä suhteessa G:hen. Kartoitus indusoi bijektion G/Gx:n ja kiertoradan G(x) välille. TIETOA.…… Matemaattinen tietosanakirja

Tässä artikkelissa on hyvin lyhyt johdanto. Ole hyvä ja täytä johdanto-osio, joka kuvaa lyhyesti artikkelin aihetta ja tee yhteenveto sen sisällöstä ... Wikipedia

Tämä artikkeli käsittelee algebrallista järjestelmää. Matemaattisen logiikan haarasta, joka tutkii lauseita ja niihin liittyviä operaatioita, katso Logiikkaalgebra. Boolen algebra on ei-tyhjä joukko A, jossa on kaksi binäärioperaatiota (konjunktion analoginen), ... ... Wikipedia

Olkoon joukolle annettu ekvivalenssirelaatio. Sitten kaikkien ekvivalenssiluokkien joukkoa kutsutaan tekijäjoukoksi ja merkitään. Joukon osiointia vastaavien elementtien luokkiin kutsutaan sen tekijöiksi. Näytä alkaen ... ... Wikipedia

Suunnattu segmentti geometriassa ymmärretään järjestetyksi pistepariksi, joista ensimmäistä pistettä A kutsutaan sen alusta ja toista B sen lopuksi. Sisältö 1 Määritelmä ... Wikipedia

Matematiikan eri aloilla kuvauksen ytimenä on jokin settiraja, joka jossain mielessä luonnehtii f:n ja injektiokartoituksen välistä eroa. Tarkka määritelmä voi kuitenkin vaihdella injektiokartoituksen f ... ... Wikipediassa

Tehtävän lähde: Tehtävä 10_20. KÄYTÄ 2018 Yhteiskuntaopinnot. Ratkaisu

Tehtävä 20. Lue alla oleva teksti, josta puuttuu joukko sanoja (ilmauksia). Valitse ehdotetusta sanaluettelosta (ilmaukset), jotka haluat lisätä aukkojen tilalle.

”Elämänlaatu riippuu monista tekijöistä aina asuinpaikasta yleiseen sosioekonomiseen ja (A) tilanteeseen sekä maan poliittiseen tilanteeseen. Elämänlaatuun voivat tavalla tai toisella vaikuttaa väestötilanne, elin- ja työolot, _____(B) määrä ja laatu jne. Talouden tarpeiden tyydytysasteesta riippuen on tapana erottaa väestön eri elintasot: varallisuus - käyttö (B) henkilön monipuolisen kehityksen varmistaminen; normaali taso _____ (G) tieteellisesti perusteltujen standardien mukaan, joka tarjoaa henkilölle fyysisen ja älyllisen voimansa palautumisen; köyhyys - tavaroiden kulutus työkyvyn ylläpitämisen tasolla lisääntymisen alarajana _____ (D); Köyhyys on biologisten kriteerien mukaan minimaalisesti hyväksyttävän tavaroiden ja palvelujen kuluttamista, mikä mahdollistaa vain ihmisen elinkelpoisuuden ylläpitämisen.

Väestö sopeutuessaan markkinaolosuhteisiin käyttää erilaisia ​​lisätulonlähteitä, mukaan lukien tulot henkilökohtaisista sivutontista, voitto _____ (E)”.

Listassa olevat sanat (ilmaukset) on annettu nimitysmuodossa. Jokaista sanaa (ilmausta) voidaan käyttää vain kerran.

Valitse peräkkäin yksi sana (ilmaus) toisensa jälkeen ja täytä henkisesti jokainen aukko. Huomaa, että luettelossa on enemmän sanoja (ilmauksia) kuin mitä tarvitset aukkojen täyttämiseen.

Luettelo termeistä:

1) pääoma

2) ekologinen

3) järkevä kulutus

4) kulutustavarat

5) tuotantovälineet

7) työvoima

8) yritystoiminta

9) sosiaalinen liikkuvuus

Ratkaisu.

Lisätään termit tekstiin.

”Elämänlaatu riippuu monista tekijöistä aina henkilön asuinpaikasta yleiseen sosioekonomiseen ja ympäristötilanteeseen (2) (A) sekä maan poliittisten asioiden tilasta. Elämänlaatuun voivat jossain määrin vaikuttaa väestötilanne, elin- ja työolot, kulutustavaroiden määrä ja laatu (4) (B) jne. Riippuen talouden tarpeiden tyytyväisyydestä, se on on tapana erottaa väestön eri elintasot: vauraus - etujen käyttö (6) (B), jotka varmistavat henkilön kokonaisvaltaisen kehityksen; rationaalisen kulutuksen normaali taso (3) (D) tieteellisesti perusteltujen standardien mukaan, mikä mahdollistaa henkilön fyysisen ja henkisen voiman palautumisen; köyhyys - tavaroiden kulutus työkyvyn ylläpitämisen tasolla työvoiman lisääntymisen alarajana (7) (E); Köyhyys on biologisten kriteerien mukaan minimaalisesti hyväksyttävän tavaroiden ja palvelujen kuluttamista, mikä mahdollistaa vain ihmisen elinkelpoisuuden ylläpitämisen.

Jos suhde R sillä on seuraavat ominaisuudet: refleksiivinen symmetrinen transitiivinen, ts. on ekvivalenssirelaatio (~ tai ≡ tai E) joukossa M , silloin ekvivalenssiluokkien joukkoa kutsutaan joukon tekijäjoukoksi M vastaavuuden suhteen R ja merkitty HERRA

Tässä on osa joukon elementtejä M vastaava x nimeltään vastaavuusluokka.

Tekijäjoukon määritelmästä seuraa, että se on Boolen osajoukko: .

Funktiota kutsutaan henkilöllisyystodistus ja se määritellään seuraavasti:

Lause. Tekijäalgebra F n /~ on isomorfinen Boolen funktioiden algebralle B n

Todiste.

Vaadittu isomorfismi ξ : F n / ~ → B n määritetään seuraavan säännön mukaan: ekvivalenssiluokka ~(φ) kartoitettu toiminto f φ , jolla on mielivaltaisen kaavan totuustaulukko joukosta ~(φ) . Koska eri ekvivalenssiluokat vastaavat erilaisia ​​totuustaulukoita, kartoitus ξ injektoivasti ja koska minkä tahansa Boolen funktion osalta f alkaen P-kirjaimessa funktiota edustava kaava on olemassa f, sitten kartoitus ξ surjektiivisesti. Tallennustoiminnot , 0, 1 kun näytetään ξ tarkastettu suoraan. CHTD.

Jokaisen funktion, joka ei ole vakio, toiminnallista täydellisyyttä koskevan lauseen mukaan 0 , vastaa jotain SDNF:ää ψ , joka kuuluu luokkaan ~(φ) = ξ -1 (f) funktiota edustavat kaavat f . Luokassa oleminen on ongelmallista ~(φ) disjunktiivinen normaalimuoto, jolla on yksinkertaisin rakenne.

Työ loppu -

Tämä aihe kuuluu:

Diskreetin matematiikan luentokurssi

Moskovan osavaltion rakennustekniikan yliopisto. Rakentamisen johtamistalouden ja tietojärjestelmien instituutti.. ieuis..

Jos tarvitset lisämateriaalia tästä aiheesta tai et löytänyt etsimääsi, suosittelemme käyttämään hakua teostietokannassamme:

Mitä teemme saadulla materiaalilla:

Jos tämä materiaali osoittautui hyödylliseksi sinulle, voit tallentaa sen sivullesi sosiaalisissa verkostoissa:

twiittaa

Kaikki tämän osion aiheet:

Diskreetin matematiikan oppiaine
Diskreetin (äärellisen, äärellisen) matematiikan aine on matematiikan haara, joka tutkii diskreettien rakenteiden ominaisuuksia, kun taas klassinen (jatkuva) matematiikka tutkii objektien ominaisuuksia.

isomorfismi
Algebrallisia operaatioita tutkivaa tiedettä kutsutaan algebraksi. Tätä käsitettä konkretisoituu ja syvennetään kurssin opiskelun myötä. Algebraa kiinnostaa vain kysymys MITEN

Harjoitukset
1. Todista, että isomorfinen kuvaus on aina isotoninen ja päinvastoin ei pidä paikkaansa. 2. Kirjoita ryhmäsi muistiin joukkojen kielellä. 3. Kirjoita joukkojen kielellä objektit, jotka

Sarja ja sarjan elementit
Tällä hetkellä olemassa olevat joukkoteoriat eroavat toisistaan ​​käsitteellisen perustan paradigmatiikan (näkemysjärjestelmän) ja loogisten keinojen osalta. Joten esimerkkinä voimme antaa kaksi vastakkaista

Äärilliset ja äärettömät joukot
Mistä setti koostuu, ts. Objekteja, jotka muodostavat joukon, kutsutaan sen elementeiksi. Joukon elementit ovat erillisiä ja eroavat toisistaan. Kuten esimerkeistä voidaan nähdä

Aseta teho
Äärillisen joukon teho on yhtä suuri kuin sen elementtien lukumäärä. Esimerkiksi joukon A universumin B(A) kardinaliteetti, jonka kardinaliteetti on n

A1A2A3| + … + |А1A2A3| + … + |А1A2An| + … + |An-2An-1An| + (-1)n-1 |А1A2A3…An|
Äärillisellä joukolla A on kardinaliteetti k, jos se on ekvivalentti segmentin 1..k kanssa;:

Osajoukko, oma osajoukko
Kun joukon käsite on otettu käyttöön, syntyy ongelma uusien joukkojen rakentamisessa olemassa olevista, eli joukoille suoritettavien operaatioiden määrittämisestä. joukko M",

Merkityksellisten joukkoteorioiden symbolinen kieli
Kurssin opiskeluprosessissa erotetaan joukkoteorian objektikieli ja metakieli, jonka avulla objektikieltä opiskellaan. Joukkoteorian kielellä tarkoitamme relaatiota

Todiste
Joukko B on ääretön, joten

Kohteiden lisääminen ja poistaminen
Jos A on joukko ja x on alkio, niin elementti

Rajoitettu erä. Aseta rajat
Olkoon jollekin joukolle X annettu numeerinen funktio f(x). Funktion f (x) ylärajaa (rajaa) kutsutaan sellaiseksi luvuksi

Tarkka ylä (ala) raja
E:n kaikkien ylärajojen joukkoa merkitään Es:llä, kaikkien alarajojen joukkoa Ei. Varalta

Sarjan tarkka ylä- (ala)raja
Jos alkio z kuuluu joukon E ja sen kaikkien ylärajojen joukon Es leikkauspisteeseen (vastaavasti alempi z

Ylä- ja alareunojen perusominaisuudet
Olkoon X osittain järjestetty joukko. 1. Jos, niin

Joukko attribuutiivisesta näkökulmasta
Aggregoitu näkökulma, toisin kuin attribuutio, on loogisesti kestämätön siinä mielessä, että se johtaa paradokseihin, kuten Russell ja Cantor (katso alla). Attribuutin t sisällä

Rakenne
Osittain järjestettyä joukkoa X kutsutaan rakenteeksi, jos se sisältää minkä tahansa kaksialkioisen joukon

Päällystys- ja halkaisusarjat
Joukon A osio on perhe Ai

binäärisuhteet
Pituus n, jonka jäsenet ovat a1, .... an, merkitään (a1, .... a

Binäärisuhteiden ominaisuudet
Ho-joukon binäärirelaatiolla R on seuraavat ominaisuudet: (a) refleksiivisesti, jos xRx

Kolminkertaiset suhteet
Karteesinen tuote XY

N-aariset suhteet
Analogisesti kahden joukon X,Y karteesisen tulon kanssa voidaan muodostaa karteesinen tulo X

Näytöt
Kuvaukset ovat joitain yhteyksiä joukkojen elementtien välillä. Yksinkertaisimpia esimerkkejä suhteista ovat jäsensuhteet x

Kirjeenvaihto
Karteesisen tulon osajoukkoa S kutsutaan joukkojen Mi alkioiden n-aariseksi vastaavuudeksi. Muodollisesti

Toiminto
Diskreetin matematiikan kaikkien osien ytimessä on funktion käsite. Anna x-

Edustaa funktiota suhteiden kannalta
Funktio on binäärirelaatio f, jos lähteestä ja

Injektio, surjektio, bijektio
Käytettäessä termiä "kartoitus" erotetaan kartoitus X:stä Y:hen ja kartoitus X:stä Y:ksi

Käänteinen funktio
Satunnaiselle, määrittelemme

Osittain tilatut setit
Joukkoa S kutsutaan osittain järjestetyksi (POS), jos sille annetaan refleksiivinen, transitiivinen ja antisymmetrinen binääriosittaisjärjestyssuhde.

Aseta edustuksen minimointi
Näitä lakeja käyttäen tarkastellaan joukon M esityksen minimoimisen ongelmaa operaatioiden avulla

Permutaatiot
Annettu joukko A. Olkoon A äärellinen joukko, joka koostuu n alkiosta A = (a1, a2, …, a

Permutaatiot toistoilla
Olkoon joukko A identtisiä (toistuvia) alkioita. Permutaatio koostumuksen toistoilla (n1, n2, … ,nk

Majoitukset
Pituus k (1≤k≤n) koostuvat n-alkiojoukon A eri alkioista (tuplet eroavat yhdellä

Sijoitukset toistoilla
Olkoon joukko A identtisiä (toistuvia) alkioita. Sijoittelut, joissa toistetaan n elementtiä k nimellä

Tilattu sijoitus
Sijoitamme n objektia m laatikkoon siten, että jokainen laatikko sisältää sarjan, ei joukkoa, kuten aiemmin, siihen sijoitettuja objekteja. Kaksi

Yhdistelmät
M-elementtijoukosta A rakennamme järjestetyn joukon, jonka pituus on n, jonka alkiot ovat järjestelyjä samoilla aiheilla

Yhdistelmät toistoilla
Tuloksena olevat kaavat ovat voimassa vain, kun joukossa A ei ole identtisiä alkioita. Olkoon alkioita n tyyppiä ja niistä monikko

Menetelmän muodostavat funktiot
Tätä menetelmää käytetään kombinatoristen lukujen luetteloimiseen ja kombinatoristen identiteettien määrittämiseen. Lähtökohtana on sekvenssi (ai) kombinaattori

Algebrallinen järjestelmä
Algebrallinen järjestelmä A on joukko ‹M,O,R›, jonka ensimmäinen komponentti M on ei-tyhjä joukko, toinen komponentti O on joukko

Sulkeminen ja subalgebrat
Osajoukkoa kutsutaan suljetuksi operaatiossa φ if

Algebrat yhdellä binäärioperaatiolla
Annetaan yksi binäärioperaatio joukolle M. Harkitse sen generoimia algebroita, mutta harkitse ensin joitain binääritoimintojen ominaisuuksia. Binaari noin

ryhmäoidi
Näytä algebra<М, f2>kutsutaan groupoidiksi. Jos f2 on toiminto kuten kertolasku (

Kokonaisluvut modulo m
Annettu kokonaislukujen rengas . Palauttaa mieleen. Algebra<М,

Congruences
Kongruenssi algebralla A = (Σ on algebran allekirjoitus, joka koostuu vain funktiosymboleista) tällaista ekvivalenssisuhdetta kutsutaan

Graafiteorian elementit
Graafit ovat matemaattisia objekteja. Graafiteoriaa sovelletaan sellaisilla aloilla kuin fysiikka, kemia, viestintäteoria, tietokonesuunnittelu, sähkötekniikka, konetekniikka, arkkitehtuuri, tutkimus

graafi, kärkipiste, reuna
Suuntaamattomalla graafilla (tai lyhyesti sanottuna graafilla) tarkoitamme sellaista mielivaltaista paria G = , Mitä

Kirjeenvaihto
Toinen yleisemmin käytetty kuvaus suunnatusta graafista G on määrittää joukko pisteitä X ja vastaavuus Γ, joka

Suuntaamaton kaavio
Jos reunoilla ei ole suuntausta, graafia kutsutaan suuntaamattomaksi (suuntaamaton kaksoiskappale tai suuntaamaton).

Tapahtuma, sekakaavio
Jos reunalla e on muoto (u, v) tai<и, v>, silloin sanomme, että reuna e liittyy ver:n kanssa

Käänteinen sovitus
Koska on joukko tällaisia ​​pisteitä

Graafinen isomorfismi
Kaksi kuvaajaa G1 = ja G2 = ovat isomorfisia (G

Polkusuuntautunut reitti
Suunnatun graafin polku (tai suunnattu reitti) on kaarien sarja, jossa

Vierekkäiset kaaret, vierekkäiset kärjet, kärjen aste
Kaaret а = (хi, хj), хi ≠ хj, joilla on yhteiset päätypisteet, n

Yhteydet
Graafin kahta kärkeä kutsutaan yhdistetyiksi, jos ne yhdistää yksinkertainen polku. Graafia kutsutaan yhdistetyksi, jos kaikki sen kärjet ovat yhteydessä toisiinsa. Lause.

Kaavio painotetuilla kaarilla
Graafia G = (N, A) kutsutaan painotetuksi, jos kaarijoukolla A on jokin funktio l: A → R, joka

Vahva liitäntämatriisi
Vahva liitettävyysmatriisi: aseta vinottain 1; täytä rivi X1 - jos kärkipiste on saavutettavissa X1:stä ja X1:stä d

puut
Puut ovat tärkeitä paitsi siksi, että niille löytyy käyttökohteita eri tiedonaloilla, myös siksi, että niillä on erityinen asema itse graafiteoriassa. Jälkimmäinen johtuu puurakenteen äärimmäisestä yksinkertaisuudesta.

Jokaisella ei-triviaalilla puulla on vähintään kaksi riippuvaa kärkeä
Todistus Tarkastellaan puuta G(V, E). Puu on yhdistetty graafi, joten

Lause
Vapaan puun keskipiste koostuu yhdestä kärjestä tai kahdesta vierekkäisestä kärjestä: Z(G) = 0&k(G) = 1 → C(G) = K1

Suunnatut, järjestetyt ja binääripuut
Orientoidut (järjestetyt) puut ovat abstraktio hierarkkisista suhteista, jotka ovat hyvin yleisiä niin käytännön elämässä kuin matematiikassa ja ohjelmoinnissa. Puu (orient

Todiste
1. Jokainen kaari tulee solmuun. Määritelmän 9.2.1 kohdasta 2 meillä on: v

Tilatut puut
Järjestyspuun vastaavan määritelmän joukot T1,..., Tk ovat alipuita. Jos alipuiden suhteellinen järjestys T1,...,

binääripuut
Binääripuu (tai binääripuu) on äärellinen joukko solmuja, jotka ovat joko tyhjiä tai koostuu juuresta ja kahdesta ei-leikkautuvasta binääripuusta - vasemmalla ja oikealla. binääripuu ei java

Ilmaisten puiden esitys
Puiden esittämiseen voit käyttää samoja tekniikoita kuin yleisten graafien esittämisessä - vierekkäisyys- ja esiintymämatriiseja, viereisyysluetteloita ja muita. Mutta käyttämällä d:n erikoisominaisuuksia

Lopeta varten
Perustelut Prufer-koodi on todellakin esitys vapaasta puusta. Tämän tarkistamiseksi näytämme, että jos T" on puu

Binääripuiden esitys
Mikä tahansa vapaa puu voidaan suunnata määrittämällä yksi solmuista juureksi. Mikä tahansa tilaus voidaan tilata mielivaltaisesti. Järjestetyn järjestyspuun yhden solmun (veljien) jälkeläisille suhteellinen

Peruslogiikkafunktiot
Merkitään E2 = (0, 1) kahdesta luvusta koostuva joukko. Numerot 0 ja 1 ovat perustason diskreetissä matossa

boolen funktio
Boolen funktio, jossa on n argumenttia x1, x2, …, xn, on funktio f joukon n:nnestä potenssista

Kaksielementtinen boolen algebra
Tarkastellaan joukkoa Bo = (0,1) ja määritellään sille operaatiot taulukoiden mukaan

Boolen funktiotaulukot
N:n muuttujan Boolen funktio voidaan antaa taulukona, jossa on kaksi saraketta ja 2n riviä. Ensimmäisessä sarakkeessa luetellaan kaikki joukot B:stä

F5 - toista y:ssä
f6 – summa modulo 2 f7

Toiminnan järjestys
Jos kompleksisessa lausekkeessa ei ole hakasulkeita, operaatiot on suoritettava seuraavassa järjestyksessä: konjunktio, disjunktio, implikaatio, ekvivalenssi, negaatio. Järjestelysopimukset noudattavat Shannonin ensimmäistä lausetta
Alkuperäistä kaavaa φ vastaavien SDNF:n ja SKNF:n löytämisen ongelman ratkaisemiseksi tarkastelemme ensin Boolen funktion f(x1, x2) laajennuksia

Shannonin toinen lause
Boolen algebroiden kaksinaisuusperiaatteen nojalla Lause 6.4.3 (Shannonin toinen lause) on pätevä. Mikä tahansa Boolen funktio f(x1, x2,...

Toiminnallinen täydellisyys
Lause (funktionaalisesta täydellisyydestä). Jokaiselle Boolen funktiolle f on kaava φ, joka edustaa funktiota f

Algoritmi sdnf:n löytämiseksi
SDNF:n löytämiseksi tämä kaava on ensin pelkistettävä DNF:ksi ja sitten sen konjunktit on muutettava yksikön aineosiksi seuraavilla toimilla: a) jos konjunkti sisältää jonkin verran

Quine menetelmä
Tarkastellaan Quinen menetelmää tiettyä Boolen funktiota edustavan MDNF:n löytämiseksi. Määrittelemme seuraavat kolmioperaatiot: - täydellisen liimauksen toiminta -

Boolen funktioiden kanoninen esitys
Loogisten (kaavojen) funktioiden kanoniset muodot ovat lausekkeita, joilla on Boolen kaavan vakiomuoto, joka edustaa yksiselitteisesti loogista funktiota. Algebrassa

Boolen funktiojärjestelmät
Olkoon Boolen funktiot f(g1, g2, …, gm) ja g1(x1, x2, …, xn), g2(x1

Perusta Zhegalkin
Esimerkki Harkitse järjestelmää. Se on valmis, koska mikä tahansa funktio vakiopohjalta ilmaistaan ​​termeillä

Postin lause
Postin lause asettaa tarpeelliset ja riittävät ehdot Boolen funktioiden järjestelmän täydellisyydelle. (Post E.L. The Two-valued interactive systems of matemaattisen logiikan. – Annals of Math. Stu

Todiste
Välttämättömyys. Päinvastoin. Anna ja

Algebra Zhegalkin
Summa modulo 2, konjunktio ja vakiot 0 ja 1 muodostavat toiminnallisesti täydellisen järjestelmän, ts. muodostavat algebran - Zhegalkin-algebran. A=

propositionaalinen logiikka
Matemaattinen logiikka tutkii luonnollisen kielen syntaksin (muodon) ja semantiikan (sisällön) peruskäsitteitä. Harkitse kolmea pääasiallista matemaattisen logiikan tutkimusaluetta - logiikkaa

Predikaatin määritelmä
Olkoon X1, X2, ..., Xn mielivaltaisia ​​muuttujia. Näitä muuttujia kutsutaan objektimuuttujiksi. Olkoon muuttujien joukot

Predikaattien käyttö algebrassa
Tarkastellaan predikaatteja, joissa vain yksi muuttuja on vapaa ja joita merkitään x:llä, ja tarkastellaan predikaattien käyttöä algebrassa. Tyypillinen esimerkki

Boolen predikaattialgebra
Koska loogisia operaatioita voidaan soveltaa predikaatteihin, Boolen algebran peruslait pätevät niille. Lause. (Predikaattien loogisten operaatioiden ominaisuudet). Mn

F↔G=(F→G)(G→F), F→G=ei FG
2. Käytä lakia ei F=F, de Morganin lakeja: ei (F

Predikaattilaskenta
Predikaattilaskentaa kutsutaan myös ensimmäisen asteen teorioiksi. Predikaattilaskennassa, kuten myös propositiolaskussa, on ensi sijassa pääteltävissä oleva ongelma.

Seuraaminen ja vastaavuus
Propositiomuoto Q2 seuraa lausemuodosta Q1, jos implikaatio Q1→Q2 muuttuu todelliseksi korkeaksi

Hyväksytyt nimitykset
Symbolit "älä tilaa enää". Kun verrataan kahden funktion f(n) ja g(n) kasvunopeutta (ei-negatiivisilla arvoilla), seuraavat ovat erittäin käteviä.

Meta-merkinnät
Symbolit Sisältö Esimerkki TAI

Seuraavat lauseet voidaan todistaa.

Lause 1.4. Funktiolla f on käänteisfunktio f -1, jos ja vain jos f on bijektiivinen.

Lause 1.5. Bijektiivisten funktioiden koostumus on bijektiivinen funktio.

Riisi. 1.12 näyttää erilaisia ​​suhteita, kaikki paitsi ensimmäinen ovat toimintoja.

asenne, mutta

injektio, mutta

oletus, mutta

ei toiminto

ei oletus

ei injektiota

Olkoon f : A→ B funktio ja joukot A ja B äärellisiä joukkoja, olkoon A = n , B = m . Dirichlet'n periaate sanoo, että jos n > m, niin ainakin yksi f:n arvo esiintyy useammin kuin kerran. Toisin sanoen on olemassa alkiopari a i ≠ a j , a i , a j A joille f(a i )= f(a j ).

Dirichlet-periaate on helppo todistaa, joten jätämme sen lukijalle triviaaliksi harjoitukseksi. Harkitse esimerkkiä. Olkoon ryhmässä yli 12 opiskelijaa. Silloin on selvää, että ainakin kahdella heistä on syntymäpäivä samassa kuussa.

§ 7. Ekvivalenssisuhde. Factor set

Binäärirelaatiota R joukossa A kutsutaan ekvivalenssirelaatioksi, jos R on refleksiivinen, symmetrinen ja transitiivinen.

Lukujoukon tasa-arvosuhteella on osoitetut ominaisuudet, joten se on ekvivalenssirelaatio.

Kolmion samankaltaisuusrelaatio on ilmeisesti ekvivalenssirelaatio.

Ei-tiukan epäyhtälön (≤ ) relaatio reaalilukujen joukossa ei ole ekvivalenssirelaatio, koska se ei ole symmetrinen: arvosta 3 ≤ 5 ei seuraa, että 5 ≤ 3.

Elementin a generoima ekvivalenssiluokka (coset) tietylle ekvivalenssisuhteelle R on niiden x A:n osajoukko, jotka ovat suhteessa R:n kanssa a:n kanssa. Määritetty ekvivalenssiluokka on merkitty [a] R:llä, joten meillä on:

[a] R = (x A: a, x R).

Harkitse esimerkkiä. Kolmioiden joukkoon otetaan käyttöön samankaltaisuussuhde. On selvää, että kaikki tasasivuiset kolmiot kuuluvat yhteen koottiin, koska jokainen niistä on samanlainen kuin esimerkiksi kolmio, jonka kaikilla sivuilla on yksikköpituus.

Lause 1.6. Olkoon R ekvivalenssirelaatio joukolla A ja [a] R kosetti, ts. [a] R = (x A: a, x R), sitten:

1) mille tahansa aA:lle: [a]R ≠, erityisesti a [a]R;

2) eri cosetit eivät leikkaa toisiaan;

3) kaikkien kosettien liitto osuu koko joukkoon A;

4) eri kosettien joukko muodostaa osion joukosta A.

Todiste. 1) R:n refleksiivisuudesta johtuen saamme, että millä tahansa a, a A:lla meillä on a, a R , joten a [ a] R ja [ a] R ≠ ;

2) oletetaan, että [a] R ∩ [b] R ≠ , ts. A:sta on elementti c ja c [a] R ∩ [b] R . Sitten (cRa)&(cRb) saamme R:n symmetrian vuoksi (aR c)&(cRb), ja R:n transitiivisuudesta saamme aRb.

Jokaiselle х [а] R:lle meillä on: (хRa)&(аRb) , niin R:n transitiivisuudesta johtuen saamme хRb, ts. x[b]R, joten [a]R[b]R. Vastaavasti mille tahansa y:lle, y [b] R :lle on: (уRb)&(aRb) , ja R:n symmetriasta johtuen saamme, että (уRb)&(bR а), niin R:n transitiivisuudesta johtuen , saamme, että уR а ts. y[a]r ja

joten [b] R [a] R . Arvoista [a] R [b] R ja [b] R [a] R saadaan [a] R = [b] R, eli jos kosetit leikkaavat, niin ne osuvat yhteen;

3) jollakin a:lla, a A:lla, kuten todistettu, meillä on [ a] R , niin on selvää, että kaikkien kosettien liitto osuu yhteen joukon A kanssa.

Lauseen 1.6 väite 4) seuraa kohdista 1)–3). Lause on todistettu. Voimme todistaa seuraavan lauseen.

Lause 1.7. Erilaiset ekvivalenssisuhteet joukossa A luovat A:n eri osiot.

Lause 1.8. Jokainen joukon A osio generoi joukolle A ekvivalenssisuhteen ja eri osiot luovat erilaisia ​​ekvivalenssisuhteita.

Todiste. Olkoon joukon A osio В= (B i ). Määritellään relaatio R : a,b R, jos ja vain jos on olemassa sellainen B i, että a ja b kuuluvat molemmat tähän B i:ään. On selvää, että esitetty relaatio on refleksiivinen, symmetrinen ja transitiivinen, joten R on ekvivalenssirelaatio. Voidaan osoittaa, että jos osiot ovat erilaisia, niin myös niiden generoimat ekvivalenssisuhteet ovat erilaisia.

Joukon A kaikkien kosettien joukkoa suhteessa annettuun ekvivalenssirelaatioon R kutsutaan osamääräjoukoksi ja sitä merkitään A/R . Tekijäjoukon elementit ovat cosetteja. Coset-luokka [a] R , kuten tiedät, koostuu elementeistä A, jotka ovat suhteessa toisiinsa R .

Tarkastellaan esimerkkiä ekvivalenssirelaatiosta kokonaislukujoukolla Z = (…, -3, -2, -1, 0, 1, 2, 3, …).

Kahta kokonaislukua a ja b kutsutaan vertailukelpoisiksi (yhtenäisiksi) moduloiksi m, jos m on luvun a-b jakaja, eli jos meillä on:

a=b+km, k=…, -3, -2, -1, 0, 1, 2, 3, ….

Kirjoita tässä tapauksessa a≡ b(mod m) .

Lause 1.9. Kaikille luvuille a , b , c ja m>0 meillä on:

1) a ≡ a(mod m) ;

2) jos a ≡ b(mod m), niin b ≡ a(mod m);

3) jos a ≡ b(mod m) ja b ≡ c(mod m), niin a ≡ c(mod m).

Todiste. Lausekkeet 1) ja 2) ovat ilmeisiä. Todistakaamme 3). Olkoon a=b+k 1 m, b=c+k 2 m, sitten a=c+(k 1 +k 2 )m, ts. a ≡ c(mod m) . Lause on todistettu.

Siten vertailtavuuden suhde modulo m on ekvivalenssirelaatio ja jakaa kokonaislukujoukon ei-päällekkäisiin lukuluokkiin.

Muodostetaan loputtomasti avautuva spiraali, joka kuvassa 1.13 on kuvattu yhtenäisellä viivalla ja äärettömästi kiertyvällä spiraalilla, joka on kuvattu katkoviivalla. Olkoon ei-negatiivinen kokonaisluku m annettu. Sijoitamme kaikki kokonaisluvut (elementit joukosta Z ) näiden spiraalien leikkauspisteisiin m-säteiden kanssa, kuten kuvassa 10 on esitetty. 1.13.

Vertailumoduulin m suhteelle (etenkin jos m = 8) ekvivalenssiluokka on säteellä makaavat luvut. On selvää, että jokainen numero kuuluu yhteen ja vain yhteen luokkaan. Voidaan saada, että arvolla m = 8 meillä on:

[ 0] ={…, -8, 0, 8, 16, …};
[ 1] ={…, -7, 1, 9, 17, …};
[ 2] ={…, -6, 2, 10, 18, …};
[ 7] ={…, -9, -1, 7, 15, …}.

Joukon Z asetuskerroin vertailumoduulin m suhteen merkitään Z/m tai Zm. Tarkasteltavana olevassa tapauksessa m = 8

saadaan, että Z/8 = Z8 = ( , , , …, ) .

Lause 1.10. Kaikille kokonaisluvuille a, b, a*, b*, k ja m:

1) jos a ≡ b(mod m), niin ka ≡ kb(mod m);

2) jos a ≡ b(mod m) ja a* ≡ b* (mod m), niin:

a) a + a * ≡ b + b * (mod m); b) aa * ≡ bb* (mod m).

Esitämme todisteen tapauksesta 2b). Olkoon a ≡ b(mod m) ja a * ≡ b * (mod m) , sitten a=b+sm ja a * =b * +tm joillekin kokonaisluvuille s ja t . kertomalla,

saamme: aa* =bb* + btm+ b* sm+ stm2 =bb* +(bt+ b* s+ stm)m. Siten,

aa* ≡ bb* (mod m).

Siten modulovertailuja voidaan lisätä ja kertoa termi kerrallaan, ts. toimivat täsmälleen samalla tavalla kuin tasa-arvo. Esimerkiksi,