Binäärisuhde

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. elokuuta 2022 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Binäärinen ( kaksipaikkainen ) relaatio (vastaavuus [1] [2] ) on relaatio kahden joukon ja eli näiden joukkojen karteesisen tulon minkä tahansa osajoukon välillä : [3] . Binäärirelaatio joukossa on mikä tahansa osajoukko , tällaisia binäärisuhteita käytetään useimmiten matematiikassa, erityisesti nämä ovat yhtäläisyys , epäyhtälö , ekvivalenssi , järjestyssuhde . $A$ $B$ $R\subseteq A\times B$ $A$ $R\subseteq A^{2}=A\kertaa A$

Aiheeseen liittyvät määritelmät

Parien kaikkien ensimmäisten komponenttien joukkoa kutsutaan suhteen verkkotunnukseksi ja sitä merkitään . [neljä] $R\subseteq A\times B$ $R$ ${\mathrm {Dom}}\,R$

{\mathrm {Dom}}\,R=\{x\mid \olemassa y((x,\;y)\in R)\}.

Parien kaikkien toisten komponenttien joukkoa kutsutaan suhteen verkkotunnukseksi ja sitä merkitään . $R$ $R$ ${\mathrm {Im}}\,R$

{\mathrm {Im}}\,R=\{y\mid \olemassa x((x,\;y)\in R)\}.

[neljä]

Inversio ( käänteinen suhde) on joukko ja sitä merkitään . $R$ $\{(x,\;y)\mid (y,\;x)\in R\}$ $R^{{-1}}$
Sävellysbinäärisuhteiden (superpositio) ja on joukko ja sitä merkitään . [5] [6] $R$ $S$ $\{(x,\;y)\mid \exists z(xRz\land zSy)\}$ $R\circ S$

Relationship Properties

Tietyn joukon binäärirelaatiolla voi olla erilaisia ominaisuuksia, esimerkiksi: $R$ $M$

refleksiivisyys :, _ $\forall x\in M:(xRx)$
antireflexiivisyys (irreflexiivisyys): , $\forall x\in M:\neg (xRx)$
ydinjousto : , $\forall x,y\in M:(xRy\Rightarrow x=y)$
symmetria :, _ $\forall x,\;y\in M:(xRy\Rightarrow yRx)$
antisymmetria : , $\forall x,\;y\in M:(xRy\wedge yRx\Rightarrow x=y)$
epäsymmetria :, _ $\forall x,\;y\in M:(xRy\Rightarrow \neg (yRx))$
transitiivisuus : , $\forall x,\;y,\;z\in M:(xRy\wedge yRz\Rightarrow xRz)$
euklidinen :, _ $\forall x,y,z\in M:(xRy\wedge xRz\Rightarrow yRz)$
täydellisyys (tai yhteys [7] ): , $\forall x,y\in M:(xRy\lor yRx)$
yhteys(tai heikko yhteys [7] ): , $\forall x,y\in M:(x\neq y\Rightarrow xRy\lor yRx)$
trikotomia: täsmälleen yksi kolmesta väittämästä on tosi: , tai . $\forall x,y\in M$ $xRy$ $yRx$ $x=y$

Suhdetyypit

Refleksiivistä transitiivista relaatiota kutsutaan kvasijärjestyssuhteeksi .
Refleksiivistä symmetristä transitiivista relaatiota kutsutaan ekvivalenssirelaatioksi .
Refleksiivistä antisymmetristä transitiivista relaatiota kutsutaan (osittais)järjestysrelaatioksi .
Antirefleksiivistä antisymmetristä transitiivista relaatiota kutsutaan tiukan järjestyksen suhteeksi .
Täydellistä antisymmetristä (tai pätee mihin tahansa ) transitiiviseen relaatioon kutsutaan lineaarisen järjestyksen relaatioksi . $x,y$ $xRy$ $yRx$
Antirefleksiivistä antisymmetristä suhdetta kutsutaan dominanssisuhteeksi .

Binäärisuhteiden tyypit

Käänteinen suhde[ specific ] (käänteinen suhde ) on kaksipaikkainen relaatio, joka koostuu alkiopareista, jotka on saatu järjestämällä uudelleen annetun suhteen alkioparit . Nimetty: . Tietylle suhteelle ja sen käänteiselle yhtälö on tosi: . $R$ $(y,x)$ $(x, y)$ $R$ $R^{{-1}}$ $(R^{{-1}})^{{-1}}=R$
Vastavuoroiset suhteet (vastavuoroiset suhteet) ovat suhteita, jotka ovat käänteisiä toisilleen. Yhden niistä alue on toisen toimialue, ja ensimmäisen alue on toisen toimialue.
Refleksiivinen relaatio on kaksipaikkainen relaatio , joka on määritelty tietyssä joukossa ja jolle on tunnusomaista, että minkä tahansa tämän joukon elementti on suhteessa itseensä, eli minkä tahansa tämän joukon elementin osalta . Esimerkkejä refleksiivisistä suhteista: tasa -arvo , samanaikaisuus , samankaltaisuus . $R$ $x$ $x$ $R$ $x$ $xRx$
Antirefleksiivinen relaatio (irrefleksiivinen relaatio; aivan kuten antisymmetria ei ole sama kuin epäsymmetria, irreflexiivisyys ei ole sama kuin ei-reflexiivisyys) on binäärirelaatio , joka on määritelty tietyssä joukossa ja jolle on tunnusomaista, että se ei pidä paikkaansa tämän joukon millekään elementille, että se on suhteessa itseensä (se ei ole totta ). $R$ $x$ $R$ $xRx$
Transitiivinen relaatio on kaksipaikkainen relaatio, joka on määritelty tietylle joukolle ja joka eroaa jollekin seuraavista ja seuraavista ( ). Esimerkkejä transitiivisista suhteista: "suurempi", "vähemmän", "samanlainen", "samanlainen", "korkeampi", "pohjoinen". $R$ $x, y, z$ $xRy$ $yRz$ $xRz$ $xRy\kiila yRz\to xRz$
ei-transitiivinen suhde[ selventää ] - kaksipaikkainen relaatio , joka on määritelty tietylle joukolle ja joka eroaa siinä, että se ei seuraa minkään tämän joukon osalta ja ( ). Esimerkki ei-transitiivisesta suhteesta: "x on y:n isä" $R$ $x, y, z$ $xRy$ $yRz$ $xRz$ $\neg (xRy\kiila yRz\to xRz)$
Symmetrinen relaatio on binäärisuhde , joka on määritelty tietylle joukolle ja joka eroaa siinä, että minkä tahansa elementin ja tämän joukon osalta siitä, mikä on suhteeseen , seuraa, että ja on samassa suhteessa - . Esimerkki symmetrisistä suhteista voi olla yhtäläisyys, ekvivalenssisuhde , samankaltaisuus , samanaikaisuus. $R$ $x$ $y$ $x$ $y$ $R$ $y$ $x$ $xRy\to yRx$
Antisymmetrinen relaatio on binäärirelaatio , joka on määritelty tietylle joukolle ja joka eroaa sen suhteen, että mikä tahansa ja mistä seuraa (eli ja suoritetaan samanaikaisesti vain samanarvoisille jäsenille). $R$ $x$ $y$ $xRy$ $yRx$ $x=y$ $R$ $R^{{-1}}$
Epäsymmetrinen relaatio on binäärinen relaatio , joka on määritelty tietylle joukolle ja joka eroaa minkä tahansa ja se johtuu . Esimerkki: suurempi kuin (>) ja pienempi kuin (<) -suhteet. $R$ $x$ $y$ $xRy$ $\neg yRx$
Ekvivalenssirelaatio on objektien välinen binäärisuhde , joka on sekä refleksiivinen, symmetrinen että transitiivinen. Esimerkkejä: yhtäläisyys, kahden joukon vastaavuus , samankaltaisuus , samanaikaisuus . $R$ $x$ $y$
Järjestysrelaatio on relaatio, jolla on vain osa ekvivalenssirelaation kolmesta ominaisuudesta: relaatio, joka on refleksiivinen ja transitiivinen, mutta ei-symmetrinen (esimerkiksi "ei enää") muodostaa ei-tiukan järjestyksen, ja relaatio joka on transitiivinen, mutta ei-refleksiivinen ja epäsymmetrinen (esimerkiksi "vähemmän") muodostaa tiukan järjestyksen.
Toleranssirelaatio on binäärisuhde, joka tyydyttää refleksiivisuuden ja symmetrian ominaisuudet, mutta ei välttämättä ole transitiivinen. Siten ekvivalenssisuhde on toleranssin erikoistapaus.
Yhden muuttujan funktio on binäärirelaatio , joka on määritelty tietyssä joukossa ja joka eroaa siinä, että jokainen relaatioarvo vastaa vain yhtä arvoa . Relaatiofunktionaalisuusominaisuus kirjoitetaan aksioomaksi: . $R$ $x$ $xRy$ $y$ $R$ $(xRy\kiila xRz)\to (y\equiv z)$
Bijektio (yksi yhteen relaatio) on tietylle joukolle määritetty binäärisuhde, jolle on tunnusomaista, että siinä jokainen arvo vastaa yhtä arvoa ja jokainen arvo vastaa yhtä arvoa . $R$ $x$ $y$ $y$ $x$

Operaatiot suhteissa

Koska kiinteälle joukkoparille määritellyt relaatiot ovat joukon osajoukkoja , niin näiden kaikkien suhteiden kokonaisuus muodostaa Boolen algebran relaatioiden liitos- , leikkaus- ja yhteenlaskuoperaatioiden suhteen. Erityisesti mielivaltaisille : $A$ $B$ $A\ kertaa B$ $a\in A$ $b\in B$

a\,(R\cup S)\,b\nuoli vasen oikealle a\,R\,b\vee a\,S\,b

a\,(R\cap S)\,b\nuoli vasen oikealle a\,R\,b\kiila a\,S\,b

a\,\overline {R}\,b\nuoli vasen oikealle \neg a\,R\,b

Usein relaatioiden liiton, risteyksen ja lisäyksen sijaan puhutaan niiden disjunktiosta, konjunktiosta ja negaatiosta.

Esimerkiksi , , eli tiukan järjestyssuhteen liitto tasa-arvosuhteen kanssa osuu yhteen ei-tiukan järjestyssuhteen kanssa, ja niiden leikkauspiste on tyhjä. $({=})\kuppi ({<})=({\leqslant })$ $({=})\cap ({<})=\varnothing$

Listattujen lisäksi tärkeitä ovat myös relaatioiden inversio- ja kertolaskuoperaatiot, jotka määritellään seuraavasti. Jos , niin käänteinen suhde on parille määritelty suhde, joka koostuu niistä pareista , joille . Esimerkiksi . $R\subseteq A\times B$ $R^{{-1}}$ $B$ $A$ $(b,a)$ $a\,R\,b$ $({<})^{-1}=({>})$

Anna , . Suhteiden koostumus (tai tulos) on sellainen suhde , että: $R\subseteq A\times B$ $S\subseteq B\ kertaa C$ $R$ $S$ $R\circ S\subseteq A\times C$

a\,(R\circ S)\,c\nuoli vasemmalle \exists b\in B:\,a\,(R)\,b\kiila b\,(S)\,c

Esimerkiksi luonnollisten lukujen joukon tiukan järjestyksen suhteen sen kertominen itsestään määritellään seuraavasti: . $a({<})({<})b\Nuoli vasemmalle oikealle a+1<b$

Binäärisuhteita ja kutsutaan muuttuviksi jos . Kaikille binäärirelaatioille , jotka on määritelty , on , jossa symboli tarkoittaa yhtäläisyyttä, joka on määritetty . Tasa-arvo ei kuitenkaan aina ole reilua. $R$ $S$ $RS = SR$ $R$ $A$ $R{\mathsf {Id}}_{A}={\mathsf {Id}}_{A}R$ ${\mathsf {Id}}_{A}$ $A$ $RR^{{-1}}={\mathsf {Id}}$

Seuraavat identiteetit ovat voimassa:

$R(ST)=(RS)T$ ,
$(RS)^{{-1}}=S^{{-1}}R^{{-1}}$ ,
$\overline {R^{{-1}}}={\overline {R}}^{{-1}}$ ,
$(R\cup S)^{{-1}}=R^{{-1}}\cup S^{{-1}}$ ,
$(R\cap S)^{{-1}}=R^{{-1}}\cap S^{{-1}}$ ,
$R(S\cup T)=RS\cup RT$ ,
$(R\cup S)T=RT\cup ST$ .

Kahden viimeisen identiteetin analogeja suhteiden leikkauspisteelle ei tapahdu.

Muistiinpanot

↑ Tsalenko M. Sh . Kirjeenvaihto // Mathematical Encyclopedia. - 1985. - V. 5 (Slu-Ya) . - S. 77 .
↑ Vaatimustenmukaisuus . Suuri venäläinen tietosanakirja . (määrätön)
↑ Kostrikin A. I. Johdatus algebraan. Algebran perusteet. . - M .: Fizmatlit , 1994. - S. 47 -48. – 320 s. — ISBN 5-02-014644-7 .
↑ 1 2 Kulikov L.Ya. Toinen luku. Joukkoja ja suhteita // Algebra ja lukuteoria: Proc. käsikirja pedagogisille oppilaitoksille. - M . : Korkeakoulu , 1979. - S. 50. - 559 s.
↑ Yerusalimsky Ya.M. 4. Binäärisuhteiden koostumus. Matriisien Boolen tulo // Diskreetti matematiikka: teoria, ongelmat, sovellukset. – 3. painos. - M . : Vuzovskaja kirja, 2000. - S. 112. - 280 s. — ISBN 5-89522-034-7 .
↑ Novikov F.A. 1.5.4. Relaatioiden koostumus // Diskreetti matematiikka ohjelmoijille. - Pietari. : Peter , 2000. - S. 34. - 304 s. - ISBN 5-272-00183-4 .
↑ 1 2 Dubov Yu. A., Travkin SI., Yakimets V. N. Monikriteerimallit järjestelmävaihtoehtojen muodostamiseen ja valintaan. - M.: Nauka, 1986. (s. 48)

Kirjallisuus

Maltsev, A. I. Algebralliset järjestelmät. — M .: Nauka , 1970. — 392 s. - 17 500 kappaletta.

Aleskerov F.T., Khabina E.L., Schwartz D.A. Binäärirelaatiot, graafit ja kollektiiviset ratkaisut. - M . : Kauppakorkeakoulun oppikirjoja, 2006. - 300 s.

Pukhnachev Yu. V., Popov Yu. P. Kirja. 1: Joukot, kuvaukset, relaatiot, sekvenssit, sarjat, funktiot, funktioiden ominaisuudet, differentiaali- ja integraalilaskenta, monien muuttujien funktiot // Matematiikka ilman kaavoja. - Toim. 6th, rev. - M. : URSS, 2017. - 231 s. — ISBN 978-5-9710-3871-9 .