Ekvivalenssisuhteet. Tekijäsarjat. Ekvivalenssirelaatio ja tekijäjoukko Tekijänjoukot mukaan lukien
(eli jolla on seuraavat ominaisuudet: jokainen joukon 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 nimetty. Joukon osiointia vastaavien elementtien luokkiin kutsutaan joukoksi faktorointi.
Näyttö alkaen X kutsutaan ekvivalenssiluokkien joukkoon tekijäkartoitus.
Esimerkkejä
On järkevää käyttää joukkokerrointa saadakseen normaaleja puolinormeista, sisätuloavaruuksia lähes sisätuloista jne. Tätä varten otamme käyttöön vastaavasti luokan normin, joka on yhtä suuri kuin mielivaltaisen elementin normi ja luokkien sisätulo luokkien mielivaltaisten elementtien sisätulona. Ekvivalenssisuhde puolestaan otetaan käyttöön seuraavalla tavalla(esimerkiksi normalisoidun tekijäavaruuden muodostamiseksi): otetaan käyttöön alkuperäisen puolinormoidun avaruuden osajoukko, joka koostuu elementeistä, joilla on nolla puolinormia (se on muuten lineaarinen, eli se on aliavaruus) ja kahden elementin katsotaan olevan ekvivalentteja, jos niiden ero kuuluu juuri tähän aliavaruuteen.
Jos lineaarisen avaruuden tekijäksi otetaan käyttöön jokin 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 lineaarinen avaruus ja sitä kutsutaan osamäärä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 objektit tietyn yleisen mukaan ja kokonaisuutena... ... Suuri Neuvostoliiton tietosanakirja
Galois-ryhmän kohomologia. Jos M on Abelin ryhmä ja M:hen vaikuttavan laajennuksen Galois-ryhmä, niin Galois-kohomologiaryhmät ovat kohomologiaryhmiä, jotka määritellään kaikista kartoista koostuvan kompleksin avulla, ja d on rinnakkaisoperaattori (katso ryhmien kohomologia). .. Matemaattinen tietosanakirja
Rakentaminen paratiisiin ilmestyi ensin joukkoteoriassa, ja sitten sitä käytettiin laajalti algebrassa, topologiassa ja muilla matematiikan aloilla. Tärkeä erikoistapaus I.p. on samantyyppisten matemaattisten rakenteiden ohjatun perheen i.p. Anna olla … Matemaattinen tietosanakirja
Pisteet, vaikka suhteessa ryhmään G, joka toimii joukossa X (vasemmalla), joukko 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 liian lyhyt johdanto. Ole hyvä ja lisää johdanto-osio, joka esittelee lyhyesti artikkelin aiheen ja tiivistää sen sisällön... Wikipedia
Tämä artikkeli käsittelee algebrallista järjestelmää. Matemaattisen logiikan haarasta, joka tutkii lauseita ja niillä suoritettuja operaatioita, katso logiikan algebra. 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 lisäämiseksi. Kartoitus kohteesta... ... Wikipedia
Geometriassa suunnattu segmentti 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 ydin on tietty joukkorata, joka tavallaan luonnehtii f:n ja injektiokartoituksen välistä eroa. Tarkka määritelmä voi vaihdella, mutta injektiokartoituksen f... ... Wikipedia
Aseta kerroin
Suuri joukko.
Osajärjestyksen relaatio joukossa x on binäärisuhde, joka on antisymmetrinen, refleksiivinen ja transitiivinen ja jota merkitään
parina:
Binäärisuhdetta kutsutaan toleranssiksi, jos se on refleksiivinen ja symmetrinen.
Binäärirelaatiota kutsutaan kvasijärjestykseksi, jos se on irrefleksiivinen, antisymmetrinen ja transitiivinen (ennakkotilaus).
Binäärisuhdetta kutsutaan tiukaksi järjestykseksi, jos se on refleksiivinen ja transitiivinen.
Funktio on enäärialgebrallinen operaatio joukolla M
– yksipuolinen toiminta;
– binääritoiminto;
– kolmivaiheinen toiminta.
Binäärialgebrallinen operaatio -
– operaatio, joka määrittää kullekin järjestetylle parille joukosta M jonkin joukon M elementin.
Ominaisuudet:
1) Kommutatiivisuus:
2) Assosiatiivisuus:
Neutraali elementti
Asettaa M binäärialgebrallisille operaatioille
Elementtiä kutsutaan:
-
Tekijä sarjat– joukko tämän vastaavuusluokkia sarjat. Osittainen tilaussuhde päällä monet x:ää kutsutaan binäärirelaatioksi... -
Seuraava kysymys." Tekijä sarjat. Tekijä sarjat– kokonaisuus Multiplikatiiviset ja additiiviset muodot. -
Tekijä sarjat– kokonaisuus
Joukko- joukko määriteltyjä ja erillisiä objekteja, jotka ovat ajateltavissa yhtenä kokonaisuutena. -
Kertova funktio on... lisää ». Tekijä sarjat. Tekijä sarjat– joukko tämän vastaavuusluokkia sarjat. -
Todellisuudessa tuotantoprosessi on monimutkaisempi ja sen tuote on käytön tulos sarjat tekijät. -
Johtamispäätösten laatu riippuu sarjat tekijät, joista merkittävin voi olla n. -
Pääoman hankintapäätösten optimointi on tutkimusprosessi sarjat tekijät vaikuttaa odotettuihin tuloksiin...
Jos asenne 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 on nimetty HERRA
Joukon elementtejä on osajoukko 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ääräytyy seuraavalla säännöllä: ekvivalenssiluokka ~(φ) toiminto on sovitettu f φ , jolla on totuustaulukko mielivaltaiselle kaavalle joukosta ~(φ) . Koska eri ekvivalenssiluokat vastaavat erilaisia totuustaulukoita, kartoitus ξ injektiivinen ja koska mille tahansa Boolen funktiolle f alkaen P-kirjaimessa funktiota edustava kaava on olemassa f, sitten kartoitus ξ surjektiivinen. Tallennustoiminnot, 0, 1 kun näytetään ξ tarkistetaan suoraan. CTD.
Lauseen mukaan jokaisen funktion, joka ei ole vakio, toiminnallista täydellisyyttä 0 , vastaa jotain SDNF:ää ψ , joka kuuluu luokkaan ~(φ) = ξ -1 (f) funktiota edustavat kaavat f . Ongelmana on luokkahuoneessa oleminen ~(φ) disjunktiivinen normaalimuoto, jolla on yksinkertaisin rakenne.
Työ loppu -
Tämä aihe kuuluu:
Diskreetin matematiikan opintojakson kurssi
Moskovan osavaltion rakennustekniikan yliopisto. Johtamistalouden instituutti ja tietojärjestelmä rakentamisessa.. 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 oli sinulle hyödyllistä, voit tallentaa sen sivullesi sosiaalisissa verkostoissa:
| Tweet |
Kaikki tämän osion aiheet:
Diskreetin matematiikan aihe
Diskreetin (äärellisen, äärellisen) matematiikan aine on matematiikan haara, joka tutkii diskreettien rakenteiden ominaisuuksia, kun taas klassinen (jatkuva) matematiikka tutkii esineiden ominaisuuksia.
Isomorfismi
Algebrallisia operaatioita tutkivaa tiedettä kutsutaan algebraksi. Tämä käsite tarkentuu ja syvenee kurssia opiskellessa. Algebraa kiinnostaa vain kysymys MITEN toimia
Harjoitukset
1. Todista, että isomorfinen kuvaus on aina isotoninen ja päinvastoin ei pidä paikkaansa. 2. Kirjoita ryhmäsi joukkojen kielellä. 3. Kirjoita joukkojen kielellä objektit, jotka
Joukko ja joukon elementit
Tällä hetkellä olemassa olevat joukkoteoriat eroavat toisistaan käsitteellisen perustan paradigmatiikan (näkemysjärjestelmän) ja loogisten keinojen osalta. Joten esimerkkinä voimme mainita kaksi vastakkaista
Äärilliset ja äärettömät joukot
Se, mistä sarja koostuu, ts. Objekteja, jotka muodostavat joukon, kutsutaan sen elementeiksi. Joukon elementit ovat erillisiä ja eroavat toisistaan. Kuten annetusta esimerkistä voidaan nähdä
Sarjan teho
Äärillisen joukon kardinaliteetti on yhtä suuri kuin sen alkioiden lukumäärä. Esimerkiksi joukon A kardinaliteetti n universumin B(A) kardinaalisuus
A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3…An|
Äärillisellä joukolla A on kardinaliteetti k, jos se on yhtä suuri kuin jana 1.. k;:
Osajoukko, oikea osajoukko
Kun joukon käsite on esitelty, tulee tehtäväksi rakentaa uusia joukkoja olemassa olevista eli määrittää operaatioita joukoille. sarja 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, mikä tarkoittaa
Kohteiden lisääminen ja poistaminen
Jos A on joukko ja x on alkio, ja sitten alkio
Rajalliset sarjat. Aseta rajat
Olkoon jollekin joukolle X annettu numeerinen funktio f(x). F(x) funktion yläraja (raja) on tällainen luku
Tarkka ylä (ala) raja
Kaikkien ylärajojen joukkoa E merkitään Es:llä ja kaikkia alarajoja Ei. Varalta
Sarjan tarkka ylä- (ala)raja
Jos alkio z kuuluu joukon E ja sen kaikkien ylärajojen joukon Es leikkauspisteeseen (vastaavasti alempi r
Ylä- ja alarajojen perusominaisuudet
Olkoon X osittain järjestetty joukko. 1. Jos, niin
Asetettu attribuutionäkökulmasta
Aggregaattinäkökulma, toisin kuin attribuutionäkökulma, on loogisesti kestämätön siinä mielessä, että se johtaa Russellin ja Cantorin tyyppisiin paradokseihin (katso alla). Attributiivisen t puitteissa
Rakenne
Osittain järjestettyä joukkoa X kutsutaan rakenteeksi, jos se sisältää minkä tahansa kaksialkioisen joukon
Peite- ja väliseinäsarjat
Joukon A osio on perhe Ai
Binäärisuhteet
Pituus n, jonka ehdot ovat a1, .... an, merkitään (a1, .... a
Binäärisuhteiden ominaisuudet
Binäärirelaatiolla R joukossa Ho on seuraavat ominaisuudet: (a) refleksiivinen, jos xRx
Kolminkertaiset suhteet
Karteesinen tuote XY
N-aariset suhteet
Analogisesti kahden karteesisen tulon kanssa asettaa X,Y on mahdollista rakentaa karteesinen tuote X
Näytöt
Kuvaukset ovat joitain yhteyksiä joukkojen elementtien välillä. Yksinkertaisimpia esimerkkejä suhteista ovat jäsenyyden x suhteet
Kirjeenvaihto
Karteesisen tulon osajoukkoa S kutsutaan joukkojen Mi alkioiden n-aariseksi vastaavuudeksi. Muodollisesti
Toiminto
Kaikki diskreetin matematiikan haarat perustuvat funktion käsitteeseen. Anna X-
Edustaa funktiota suhteiden kannalta
Binäärirelaatiota f kutsutaan funktioksi, jos lähteestä ja
Injektio, surjektio, bijektio
Kun käytetään termiä "kartoitus", tehdään ero XbY-kartoituksen ja X:n yhdistämisen välillä Y.
Käänteinen funktio
Satunnaisille määritämme
Osittain tilatut setit
Joukkoa S kutsutaan osittain järjestetyksi (PUM), jos sille annetaan refleksiivinen, transitiivinen ja antisymmetrinen binääriosittaisjärjestyssuhde.
Aseta edustuksen minimointi
Näitä lakeja käyttäen tarkastelemme ongelmaa joukon M esityksen minimoimisessa operaatioita käyttämällä
Uudelleenjärjestelyt
Annettu joukko A. Olkoon A äärellinen joukko, joka koostuu n alkiosta A = (a1, a2, …, a
Permutaatiot toistoilla
Olkoon joukolla A identtiset (toistuvat) elementit. Permutaatio koostumuksen toistoilla (n1, n2, … ,nk
Sijoittelut
Tupleja, joiden pituus on k (1≤k≤n), jotka koostuvat n-alkiojoukon A eri alkioista (tuplet eroavat toisistaan
Sijoitukset toistoilla
Olkoon joukolla A identtiset (toistuvat) elementit. Sijoittelut, joissa toistetaan k nimen n alkiota
Järjestetty sijoitus
Sijoitetaan n kohdetta m laatikkoon siten, että jokainen laatikko sisältää sarjan, eikä, kuten ennen, joukkoa siihen asetettuja esineitä. Kaksi
Yhdistelmät
M-elementtijoukosta A rakennamme järjestetyn joukon pituudeltaan n, jonka alkiot ovat järjestelyjä samoilla teemoilla
Yhdistelmät toistoilla
Tuloksena olevat kaavat ovat voimassa vain, kun joukossa A ei ole identtisiä alkioita. Olkoon alkioita n tyyppiä ja niistä monikko
Funktiogenerointimenetelmä
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 kokoelma ‹M,O,R›, jonka ensimmäinen komponentti M on ei-tyhjä joukko, toinen komponentti O on joukko
Sulkeminen ja subalgebrat
Osajoukon sanotaan olevan suljettu operaatiossa φ if
Algebrat yhdellä binäärioperaatiolla
Annetaan yksi binäärioperaatio joukolle M. Tarkastellaan sen luomia algebroita, mutta ensin tarkastellaan joitain binääritoimintojen ominaisuuksia. Binääri o
Groupoid
Muodon algebra<М, f2>kutsutaan groupoidiksi. Jos f2 on toiminto kuten kertolasku (
Kokonaisluvut modulo m
Annettu kokonaislukujen rengas
Congruences
Kongruenssi algebralla A =
Graafiteorian elementit
Graafit ovat matemaattisia objekteja. Graafiteoriaa käytetään esimerkiksi fysiikassa, kemiassa, viestintäteoriassa, tietokonesuunnittelussa, sähkötekniikassa, konetekniikassa, arkkitehtuurissa,
Graafi, kärki, reuna
Suuntaamattomalla graafilla (tai lyhyesti sanottuna graafilla) tarkoitamme sellaista mielivaltaista paria G =
Kirjeenvaihto
Toinen, useammin käytetty kuvaus suunnatusta graafista G koostuu pisteiden X määrittämisestä ja vastaavuudesta Г,
Suuntaamaton kaavio
Jos reunoilla ei ole suuntausta, graafia kutsutaan suuntaamattomaksi (suuntaamaton kaksoiskappale tai suuntaamaton
Ilmaantuvuus, sekakaavio
Jos reunalla e on muoto (u, v) tai<и, v>, silloin sanomme, että reuna e on sattumanvarainen ver
Käänteinen ottelu
Koska se edustaa joukkoa tällaisia pisteitä
Graafinen isomorfismi
Kaksi kuvaajaa G1 =
Polkusuuntautunut reitti
Suunnatun graafin polku (tai suunnattu reitti) on kaarien sarja, jossa
Vierekkäiset kaaret, vierekkäiset kärjet, kärjen aste
Kaaret a = (xi, xj), xi ≠ xj, 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.
Painotettu kaarikaavio
Graafia G = (N, A) kutsutaan painotetuksi, jos jokin funktio l: A → R on määritelty kaarien joukolle A siten, että
Vahva liitäntämatriisi
Vahva liitettävyysmatriisi: laita 1 diagonaaliin; 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 puun rakenteen äärimmäisestä yksinkertaisuudesta
Jokaisella ei-triviaalilla puulla on vähintään kaksi riippuvaa kärkeä
Todistus Tarkastellaan puuta G(V, E). Puu on siis yhdistetty graafi
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
Suunnatut (järjestetyt) puut ovat abstraktio hierarkkisista suhteista, joita kohdataan hyvin usein sekä käytännön elämässä että matematiikassa ja ohjelmoinnissa. Puu (suunta)
Todiste
1. Jokainen kaari tulee johonkin solmuun. Määritelmän 9.2.1 lausekkeesta 2 meillä on: v
Tilattuja puita
Orderev:n ekvivalenttimää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 erillisestä binääripuusta - vasemmasta ja oikeasta. Binääripuu ei javassa
Ilmainen 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ä erityisiä ominaisuuksia
Lopeta varten
Perustelu Prüfer-koodi on todellakin ilmainen puuesitys. 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 sen solmuista juureksi. Mikä tahansa tilaus voidaan tilata mielivaltaisesti. Järjestetyn järjestyksen yhden solmun (veljien) jälkeläisille se määritellään suhteelliseksi
Peruslogiikkafunktiot
Merkitään E2 = (0, 1) kahdesta luvusta koostuva joukko. Numerot 0 ja 1 ovat peruslukuja erillisessä matossa
Boolen funktio
Boolen funktio, jossa on n argumenttia x1, x2, … ,xn on funktio f joukon n:nnestä potenssista
Kaksielementtinen Boolen algebra
Tarkastellaan joukkoa Во = (0,1) ja määritellään sille operaatiot lähdetaulukoiden mukaan
Boolen funktiotaulukot
Boolen funktio, jossa on n muuttujaa, voidaan määrittää taulukolla, joka koostuu kahdesta sarakkeesta ja 2n rivistä. 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 sulkeita, operaatiot on suoritettava seuraavassa järjestyksessä: konjunktio, disjunktio, implikaatio, ekvivalenssi, negaatio. Sopimukset Shannonin ensimmäisen lauseen järjestämisestä
Alkuperäistä kaavaa φ vastaavien SDNF:n ja SCNF:n löytämisen ongelman ratkaisemiseksi tarkastelemme ensin Boolen funktion f(x1, x2) laajennuksia
Shannonin toinen lause
Kaksinaisuuden periaatteen nojalla Lause 6.4.3 (Shannonin toinen lause) pätee Boolen algebroihin. Mikä tahansa Boolen funktio f(x1, x2,...
Toiminnallinen täydellisyys
Lause (toiminnallisesta 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 muutettava sen konjunktit yksikön aineosiksi seuraavilla toimilla: a) jos konjunkti sisältää joitain
Quinen menetelmä
Tarkastellaan Quinen menetelmää tiettyä Boolen funktiota edustavan MDNF:n löytämiseksi. Määrittelemme seuraavat kolme toimenpidettä: - täydellinen liimaustoiminto -
Loogisten funktioiden kanoninen esitys
Loogisten (kaavojen) funktioiden kanoniset muodot ovat lausekkeita, joilla on Boolen kaavan vakiomuoto siten, että se edustaa yksiselitteisesti loogista funktiota. Algebrassa
Boolen funktiojärjestelmät
Olkoon Boolen funktiot f(g1, g2, …, gm) ja g1(x1, x2, …, xn), g2(x1
Zhegalkinin perusteella
Kokeillaan sitä, katsotaan järjestelmää. Se on valmis, koska mikä tahansa funktio vakioperustasta ilmaistaan termeinä
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äinvastaisesta. Anna sen olla
Zhegalkin algebra Ehdotuslogiikka Predikaatin määritelmä Predikaattien käyttö algebrassa Boolen predikaattialgebra F↔G=(F→G)(G→F), F→G=ei FG Predikaattilaskenta Seuraaminen ja vastaavuus Hyväksytyt merkinnät Meta-merkinnät Olkoon R binäärirelaatio joukossa X. Relaatiota R kutsutaan heijastava
, jos (x, x) О R kaikille x О X; symmetrinen
– jos arvosta (x, y) О R seuraa (y, x) О R; transitiivinen luku 23 vastaa vaihtoehtoa 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 Ekvivalenssisuhde X on refleksiivinen, transitiivinen ja symmetrinen relaatio. On helppo nähdä, että R Í X ´ X on ekvivalenssisuhde, jos ja vain, jos inkluusiot pätevät: Id X Í R (heijastuskyky), R -1 Í R (symmetria), R ° R Í R (transitiivisuus). Todellisuudessa nämä kolme ehtoa vastaavat seuraavia: Id X Í R, R -1 = R, R ° R = R. Jakamalla joukon X on pareittain hajallaan olevien osajoukkojen joukko A Í X siten, että UA = X. Jokaiseen osioon A voimme liittää ekvivalenssirelaation ~ X:ään, laittamalla x ~ y, jos x ja y ovat jonkin a Î A:n elementtejä. . Jokainen ekvivalenssirelaatio ~ X:llä vastaa osiota 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 ja laitetaan x ~ y, jos jäännökset x:n ja y:n jakamisesta kolmella 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 x R y:sta ja y R x:stä 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. Annetussa 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 mitkä tahansa 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 rajoittuu edellä
, jos on sellainen elementti x О X, 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. Samalla tavalla määritelty alaraja
osajoukot, pienimmät ja minimielementit. Esimerkissä 1 elementti 0 on sekä pienin että pienin. Esimerkissä 2 0:lla on myös nämä ominaisuudet, mutta (w, £):lla ei ole suurinta eikä enimmäisalkiota. Olkoon G=(p 0 =e, p 1, …, p r) tietty joukko permutaatioita, jotka on määritelty joukolle X = (1, 2, …, n) yksiköllä e=p 0 identtinen permutaatio. Määritellään relaatio x~y asettamalla x~y ekvivalentti sille tosiasialle, että on olemassa p, joka kuuluu G(p(x)=y). Esitetty relaatio on ekvivalenssirelaatio, eli se täyttää kolme aksioomaa: 1) x~x; Olkoon A mielivaltainen joukko. merkitty a ~ b, σ(a,b), (a,b) ∈ σ, a σ b Määritelmä: Joukon A osio on A:n pareittain hajallaan olevien osajoukkojen perhe, jotka liitossa (yhteensä) antavat kaiken A:n. Osajoukkoja A i kutsutaan osion cosetiksi. Lause: jokainen A:ssa määritetty ekvivalenssirelaatio vastaa jotakin joukon A osiota. Jokainen joukon A osio vastaa jotakin joukon A ekvivalenssisuhdetta. Lyhyesti: kaikkien joukossa A määriteltyjen ekvivalenssisuhteiden luokkien ja joukon A kaikkien osioiden luokan välillä on yksi yhteen vastaavuus. Todiste: olkoon σ ekvivalenssirelaatio joukossa A. Olkoon a ∈ A. Muodostetaan joukko: K a =(x ∈ A,: x~a) – kaikki alkiot, jotka vastaavat a:ta. Joukkoa (notaatiota) kutsutaan ekvivalenssiluokiksi suhteessa ekvivalenssiin σ. Huomaa, että jos b kuuluu K a:han, niin b~a. Osoitetaan, että a~b⇔K a =K b . Todellakin, olkoon a~b. Otetaan mielivaltainen elementti c, joka kuuluu K a:een. Silloin c~a, a~b, c~b, c kuuluu Kb:hen ja siksi K b kuuluu K a:han. Se, että K a kuuluu K b:hen, esitetään samalla tavalla. Siksi K b =K a. Jos kahdella luokalla K a ja K b on yhteinen alkio c, niin K a = K b. Itse asiassa, jos c kuuluu ryhmiin Ka ja K b, niin b~c, c~a, b~a => K a = K b . Siksi eri ekvivalenssiluokat joko eivät leikkaa tai leikkaa ja sitten yhtyvät. Jokainen A:n alkio c kuuluu vain yhteen ekvivalenssiluokkaan K c. Siksi hajautettujen ekvivalenssiluokkien järjestelmä leikkauspisteessä antaa koko joukon A. Ja siksi tämä järjestelmä on joukon A osio ekvivalenssiluokkiin. Käänteinen: Olkoon A = summa over tai A i on A:n osio. Esitetään relaatio a~b A:lle, koska a~b ⇔ a,b kuuluvat samaan osioluokkaan. Tämä suhde täyttää seuraavat aksioomit: 1) a ~ a (ovat samassa luokassa); Kommentti: 2) A:n jakaminen yksialkioisiin osajoukkoon vastaa ekvivalenssisuhdetta, joka on tasa-arvo. 3) Osiot A, jotka koostuvat yhdestä luokasta A, vastaavat ekvivalenssisuhdetta, joka sisältää A x A:n. 4) a σ b → [a] σ = [b] σ - mikä tahansa tietylle joukolle määritetty ekvivalenssisuhde jakaa tämän joukon pareittain disjunktoituihin luokkiin, joita kutsutaan ekvivalenssiluokiksi. Määritelmä: Joukon A ekvivalenssiluokkien joukkoa kutsutaan joukon A osamääräjoukoksi A/σ ekvivalenssilla σ. Määritelmä: Kuvausta p:A→A/σ, jolle p(A)=[a] σ, kutsutaan kanoniseksi (luonnolliseksi) kartoitukseksi. Mikä tahansa ekvivalenssirelaatio, joka on määritetty tietylle joukkoosiolle, tämä joukko pareittain hajautuneiksi luokiksi, joita kutsutaan ekvivalenssiluokiksi.
Summa modulo 2, konjunktio ja vakiot 0 ja 1 muodostavat toiminnallisesti täydellisen järjestelmän, ts. muodostavat algebran - Zhegalkin-algebra. A=
Matemaattinen logiikka tutkii luonnollisen kielen syntaksin (muodon) ja semantiikan (sisällön) peruskäsitteitä. Tarkastellaan kolmea pääasiallista matemaattisen logiikan tutkimusaluetta - logiikkaa
Olkoon X1, X2, ..., Xn mielivaltaisia muuttujia. Kutsumme näitä muuttujia aihemuuttujiksi. Anna muuttujan asettaa sinut
Tarkastellaan predikaatteja, joissa vain yksi muuttuja on vapaa ja joita merkitään x:llä, ja tarkastellaan predikaattien käyttöä algebrassa. Tyypillinen esimerkki
Koska loogisia operaatioita voidaan soveltaa predikaatteihin, Boolen algebran peruslait pätevät niille. Lause. (Predikaattien loogisten operaatioiden ominaisuudet). Mn
2. Käytä lakia ei F=F, de Morganin lakeja: ei (F
Predikaattilaskentaa kutsutaan myös ensimmäisen asteen teoriaksi. Predikaattilaskennassa, kuten myös lauselaskussa, ensimmäinen tärkein paikka on ratkaistavuuden ongelma.
Propositiomuoto Q2 seuraa lausemuodosta Q1, jos implikaatiosta Q1→Q2 tulee totta
Symbolit "älä tilaa enää". Kun verrataan kahden funktion f(n) ja g(n) kasvunopeutta (ei-negatiivisilla arvoilla), seuraavat ovat erittäin käteviä
Symbolit Sisältö Esimerkki TAI
x Ç y ei ole tyhjä. Suhde yhteiseen on refleksiivinen ja symmetrinen, mutta ei transitiivinen.
2) x-y-→y-x;
3) x~y&y~z^x~z;
Määritelmä: Binäärirelaatio δ=A*A on ekvivalenssirelaatio (merkitty a ~ b), jos se täyttää seuraavat aksioomit:
∀ a, b, c ∈ A
1) a ~ a – refleksiivisyys;
2) a ~ b ⇒ b ~ a – kommutatiivisuus;
3) a ~ b & b ~ c → a ~ c - transitiivisuus
А= ∪А i, А i ∩А j = ∅, ∀i ≠ j.
Olkoon nyt K b =K a . Silloin a kuuluu ryhmään K a = K b, a kuuluu ryhmään K b, a~b. Sehän piti näyttää.
2) a ~ b → b ~ a;
3) a ~ b & b ~ c → a ~ c, ts. käyttöön otettu relaatio ~ on ekvivalenssirelaatio.
1) joukon A jakoa yksialkioisiksi osajouksiksi ja A:n osiota, joka koostuu vain joukosta A, kutsutaan triviaaleiksi (epäoikeiksi) osioksi.
Ladataan...
