- Forelesning nr. 1. Sett og operasjoner på dem.
- Forelesning nr. 2. Korrespondanser og funksjoner.
- Forelesning nr. 3. Relasjoner og deres egenskaper.
- Forelesning nr. 4. Grunnleggende typer relasjoner.
- Forelesning nr. 5. Elementer i generell algebra.
- Forelesning nr. 6. Ulike typer algebraiske strukturer.
- Forelesning nr. 7. Elementer i matematisk logikk.
- Forelesning nr. 8. Logiske funksjoner.
- Forelesning nr. 9. Boolske algebraer.
- Forelesning nr. 10. Boolske algebraer og mengdlære.
- Forelesning nr. 11. Fullstendighet og avslutning.
- Forelesning nr. 12. Predikatlogikkens språk.
- Forelesning nr. 13. Kombinatorikk.
- Forelesning nr. 14. Grafer: grunnleggende begreper og operasjoner.
- Forelesning nr. 15. Ruter, kjeder og løkker.
- Forelesning nr. 16. Noen klasser av grafer og deres deler.
SEKSJON I. SETT, FUNKSJONER, RELASJONER.
Forelesning nr. 2. Korrespondanser og funksjoner.
1. Matcher.
Definisjon. Korrespondansen mellom sett A og B er en viss delmengde G av deres kartesiske produkt: .
Hvis, så sier de at det tilsvarer når det korresponderer. I dette tilfellet kalles settet med alle slike verdier definisjonsdomenet for korrespondansen, og settet med tilsvarende verdier kalles korrespondansens verdidomene.
I den aksepterte notasjonen kalles hvert element som tilsvarer et gitt element vei når tilsvarende, tvert imot, kalles elementet prototype element for en gitt korrespondanse.
Compliance kalles fullt definert, hvis , det vil si at hvert element i settet har minst ett bilde i settet; ellers kalles kampen delvis.
Compliance kalles surjektiv, hvis, det vil si hvis hvert element i settet tilsvarer minst ett forhåndsbilde i settet.
Compliance kalles funksjonell (utvetydig), hvis et element i settet tilsvarer et enkelt element i settet.
Compliance kalles injektiv, hvis det er funksjonelt, og hvert element i settet har maksimalt ett inverst bilde.
Compliance kalles en-til-en (bijektiv), hvis et element i settet tilsvarer et enkelt element i settet, og omvendt. Vi kan også si at en korrespondanse er en-til-en hvis den er fullstendig definert, surjektiv, funksjonell, og hvert element i settet har en enkelt prototype.
Eksempel 1.
a) Den engelsk-russiske ordboken etablerer samsvar mellom sett med ord på russisk og engelsk. Det er ikke funksjonelt, siden nesten alle russiske ord har flere engelske oversettelser; det er heller ikke som regel et fullt definert samsvar, siden det alltid er engelske ord som ikke er inkludert i en gitt ordbok. Så dette er en delmatch.
b) Samsvaret mellom argumentene til en funksjon og verdiene til den funksjonen er funksjonell. Det er imidlertid ikke en-til-en, siden hver verdi av funksjonen tilsvarer to inverse bilder og .
c) Korrespondansen mellom brikkene på sjakkbrettet og feltene de opptar er en-til-en.
d) Korrespondansen mellom telefonene til byen Vyazma og deres femsifrede numre har ved første øyekast alle egenskapene til en en-til-en-korrespondanse. Men det er for eksempel ikke surjektivt, siden det er femsifrede tall som ikke samsvarer med noen telefoner.
2. En-til-en-korrespondanser og makter av sett.
Hvis det er en en-til-en korrespondanse mellom to endelige sett A og B, så har disse settene lik kardinalitet. Dette åpenbare faktum gjør det for det første mulig å etablere likheten i kardinaliteten til disse settene uten å beregne dem. For det andre er det ofte mulig å beregne kardinaliteten til et sett ved å etablere en-til-en korrespondanse med et sett hvis kardinalitet er kjent eller lett kan beregnes.
Teorem 2.1. Hvis kardinaliteten til et begrenset sett EN er lik , så antallet av alle delmengder EN lik , altså .
Settet med alle delmengder av settet M kalles boolsk og er utpekt. For endelige sett gjelder følgende: .
Definisjon. Sett EN Og I kalles ekvivalente hvis det kan etableres en-til-en-korrespondanse mellom elementene deres.
Merk at for endelige mengder er denne påstanden lett å bevise. For uendelige sett vil det bestemme selve konseptet om lik kardinalitet.
Definisjon. Mange EN kalles tellbar hvis den er ekvivalent med settet med naturlige tall: .
På en veldig forenklet måte kan vi si at en gitt uendelig mengde er tellbar hvis elementene kan nummereres ved hjelp av naturlige tall.
Uten bevis, la oss godta en rekke viktige fakta:
1. Enhver uendelig delmengde av settet med naturlige tall kan telles.
2. Settet er tellbart.
3. Settet med rasjonelle tall kan telles (er en konsekvens av forrige utsagn).
4. Unionen av et endelig antall tellbare sett er tellbar.
5. Unionen av et tellbart antall endelige mengder er tellbar.
6. Foreningen av et tellbart antall tellbare sett er tellbar.
Alle disse utsagnene, som det kan sees, lar oss ganske vellykket fastslå det faktum at dette settet er tellbart. Imidlertid vil det nå bli vist at ikke alle uendelige sett er tellbare; det er sett med større makt.
Teorem 2.2 (Kantors teorem). Settet med alle reelle tall i et segment kan ikke telles.
Bevis. La oss anta at settet er tellbart og det er en nummerering for det. Siden et hvilket som helst reelt tall kan representeres som en uendelig desimalbrøk (periodisk eller ikke-periodisk), vil vi gjøre dette med tallene i dette settet. La oss ordne dem i denne nummereringsrekkefølgen:
Vurder nå enhver uendelig desimalbrøk av formen , organisert på en slik måte at og så videre. Denne brøkdelen er åpenbart ikke inkludert i sekvensen som vurderes, siden den skiller seg fra det første tallet med første desimal, fra det andre med det andre sifferet, og så videre. Følgelig har vi mottatt et tall fra dette intervallet som ikke er nummerert, og dermed er settet ikke tellbart. Dens kraft kalles kontinuum, og sett med slik kardinalitet kalles kontinuerlig. Ovennevnte bevismetode kalles Cantors diagonale metode.
Konsekvens 1. Settet med reelle tall er kontinuerlig.
Konsekvens 2. Settet med alle delmengder av et tellbart sett er kontinuerlig.
Som vist i settteori (ved å bruke en metode som ligner den som er gitt ovenfor), for et sett med en hvilken som helst kardinalitet, har settet med alle dets undersett (boolsk) en høyere kardinalitet. Derfor er det ikke noe sett med maksimal kardinalitet. For eksempel må sett-universet beskrevet av Cantor inneholde alle tenkelige sett, men det er i seg selv inneholdt i settet av dets delmengder som et element (Cantors paradoks). Det viser seg at settet ikke er et sett med maksimal kardinalitet.
3. Skjermer og funksjoner.
Funksjon er enhver funksjonell korrespondanse mellom to sett. Hvis en funksjon etablerer samsvar mellom sett A og B, så sies funksjonen å ha formen (notasjon ). Til hvert element fra definisjonsdomenet tildeler funksjonen et enkelt element fra verdidomenet. Dette er skrevet i tradisjonell form. Elementet kalles argument funksjon, element - det betydning.
En fullt definert funksjon kalles utstilling A til B; bildet av settet A når det vises er angitt med . Hvis samtidig , det vil si at korrespondansen er surjektiv, sier vi at det er en kartlegging fra A til B.
Hvis det består av et enkelt element, kalles det en konstant funksjon.
En typetilordning kalles en transformasjon av et sett A.
Eksempel 2.
a) Funksjon 
er en kartlegging av settet av naturlige tall inn i seg selv (injektiv funksjon). Den samme funksjonen for alle er en mapping fra settet med heltall til settet med rasjonelle tall.
b) Funksjon 
er en tilordning fra settet med heltall (unntatt 0) til settet med naturlige tall. Dessuten er korrespondansen i dette tilfellet ikke en-til-en.
c) Funksjon 
er en en-til-en kartlegging av settet med reelle tall på seg selv.
d) En funksjon er ikke fullstendig definert hvis typen er , men er fullstendig definert hvis typen er eller .
Definisjon.
Funksjonstype 
kalt en lokal funksjon. I dette tilfellet er det generelt akseptert at funksjonen har argumenter: 
, Hvor .
For eksempel er addisjon, multiplikasjon, subtraksjon og divisjon to-plass funksjoner på , det vil si funksjoner av typen .
Definisjon. La korrespondansen gis. Hvis korrespondansen er slik at hvis og bare hvis , kalles korrespondansen inversen til og betegnes med .
Definisjon. Hvis korrespondansen invers til en funksjon er funksjonell, kalles den den inverse funksjonen.
Åpenbart, i invers korrespondanse, bytter bilder og prototyper plass, derfor kreves det for eksistensen av en invers funksjon at hvert element fra verdidomenet har en enkelt prototype. Dette betyr at for en funksjon eksisterer den inverse funksjonen hvis og bare hvis den er en bijektiv samsvar mellom dens definisjonsdomene og dens verdidomene.
Eksempel 3. Funksjonen har type . Den kartlegger et segment en-til-en til et segment. Derfor er det en invers funksjon for det på segmentet. Som du vet er dette .
Definisjon.
La funksjonene og bli gitt. En funksjon kalles en sammensetning av funksjoner og (betegnet med ) hvis likheten gjelder: 
, Hvor .
Sammensetningen av funksjoner er den sekvensielle anvendelsen av disse funksjonene; brukt på resultatet Det sies ofte at funksjonen er oppnådd substitusjon V .
For flerstedsfunksjoner er forskjellige varianter av substitusjoner til mulig, som gir funksjoner av forskjellige typer. Av spesiell interesse er tilfellet når mange funksjoner av typen: . I dette tilfellet er det for det første mulig å bytte funksjoner inn i hverandre, og for det andre kan du endre navn på argumentene. En funksjon oppnådd fra disse funksjonene ved en eller annen utskifting av dem i hverandre og omdøping av argumentene kalles deres superposisjon.
For eksempel, i matematisk analyse introduseres konseptet med en elementær funksjon, som er en superposisjon av et fast (uavhengig av verdien av argumentet) antall aritmetiske operasjoner, så vel som elementære funksjoner (osv.).
A.N. Kolmogorov og V.I. Arnold beviste at hver kontinuerlig funksjon av variabler kan representeres som en superposisjon av kontinuerlige funksjoner av to variabler.
Kommentar. Begrepet en funksjon er mye brukt i matematisk analyse dessuten er det et grunnleggende konsept i det. Generelt er tilnærmingen til å forstå begrepet «funksjon» i matematisk analyse noe snevrere enn i diskret matematikk. Som regel anser det den såkalte beregnelig funksjoner. En funksjon kalles beregnbar hvis det er gitt en prosedyre som lar en finne verdien av funksjonen for en gitt verdi av argumentet.
Tilbake til begynnelsen av sammendraget.
Eksempel 1.
a) En likhetsrelasjon (ofte betegnet med ) på ethvert sett er en ekvivalensrelasjon. Likhet er en minimal ekvivalensrelasjon i den forstand at når et hvilket som helst par fjernes fra denne relasjonen (det vil si enhver enhet på hoveddiagonalen til matrisen), slutter den å være refleksiv og er derfor ikke lenger en ekvivalens.
b) Angivelse av type eller 
, som består av formler forbundet med et likhetstegn, definerer en binær relasjon på et sett med formler som beskriver superposisjoner av elementære funksjoner. Denne relasjonen kalles vanligvis ekvivalensrelasjonen og er definert som følger: to formler er ekvivalente hvis de definerer samme funksjon. Ekvivalens i dette tilfellet, selv om det er indikert med "="-tegnet, betyr ikke det samme som likhetsrelasjonen, siden den kan tilfredsstilles for forskjellige formler. Vi kan imidlertid anta at likhetstegnet i slike relasjoner ikke refererer til selve formlene, men til funksjonene som de beskriver. For formler er likhetsforholdet tilfeldighetene av formlene i rettskrivning. Det heter grafisk likhet. For å unngå uoverensstemmelser i slike situasjoner, brukes tegnet " " ofte for å indikere ekvivalensforholdet.
c) Betrakt et sett med trekanter på koordinatplanet, forutsatt at en trekant er gitt hvis koordinatene til dens toppunkter er gitt. Vi vil vurdere to trekanter like (kongruente) hvis de sammenfaller når de er lagt over hverandre, det vil si at de blir oversatt til hverandre ved hjelp av en bevegelse. Likhet er en ekvivalensrelasjon på et sett med trekanter.
d) Forholdet "å ha den samme resten med et naturlig tall" på settet av naturlige tall er en ekvivalensrelasjon.
f) Relasjonen "å være en divisor" er ikke en ekvivalensrelasjon på et sett. Den har egenskapene til refleksivitet og transitivitet, men er antisymmetrisk (se nedenfor).
La en ekvivalensrelasjon spesifiseres på et sett. La oss utføre følgende konstruksjon. La oss velge et element og danne en klasse (delmengde) som består av elementet og alle elementer tilsvarende det innenfor den gitte relasjonen. Velg deretter elementet 
og danner en klasse bestående av og likeverdige elementer. Ved å fortsette disse handlingene får vi et system av klasser (muligens uendelig) slik at ethvert element fra settet er inkludert i minst én klasse, det vil si.
Dette systemet har følgende egenskaper:
1) det dannes skillevegg sett, det vil si at klasser ikke krysser hverandre i par;
2) alle to elementer fra samme klasse er likeverdige;
3) to elementer fra forskjellige klasser er ikke likeverdige.
Alle disse egenskapene følger direkte av definisjonen av en ekvivalensrelasjon. Faktisk, hvis for eksempel klasser ble undertrykt, ville de ha minst ett felles element. Dette elementet vil åpenbart tilsvare og . Deretter, på grunn av relasjonens transitivitet, . Men på grunn av måten klassene er bygget opp på, er dette ikke mulig. De to andre egenskapene kan bevises på samme måte.
Den konstruerte partisjonen, det vil si et system av klasser - delsett av settet, kalles et system ekvivalensklasser i forhold til. Kraften til dette systemet kalles partisjonsindeks. På den annen side bestemmer enhver partisjon av et sett i klasser i seg selv en ekvivalensrelasjon, nemlig forholdet "å bli inkludert i en klasse av en gitt partisjon."
Eksempel 2.
a) Alle ekvivalensklasser med hensyn til likhetsrelasjonen består av ett element.
b) Formler som beskriver samme elementære funksjon er i samme ekvivalensklasse med hensyn til ekvivalensrelasjonen. I dette tilfellet kan selve settet med formler, settet med ekvivalensklasser (det vil si partisjonsindeksen) og hver ekvivalensklasse telles.
c) Delingen av et sett med trekanter med hensyn til likhet har en kontinuumindeks, og hver klasse har også en kardinalitet av kontinuum.
d) Partisjonen av settet av naturlige tall med hensyn til relasjonen "ha en felles rest når deles på 7" har en endelig indeks på 7 og består av syv tellbare klasser.
- Ordensforhold.
Definisjon 1. Forholdet kalles ikke-strengt forhold, hvis den er refleksiv, antisymmetrisk og transitiv.
Definisjon 2. Forholdet kalles forhold av en streng orden, hvis den er anti-refleksiv, antisymmetrisk og transitiv.
Begge typer relasjoner kalles samlet ordre relasjoner. Elementer er sammenlignbare med hensyn til rekkefølgerelasjonen dersom en av de to relasjonene eller er tilfredsstilt. Et sett der en ordrerelasjon er spesifisert kalles fullstendig ordnet hvis to av elementene er sammenlignbare. Ellers kalles settet delvis bestilt.
Eksempel 3.
a) Relasjonene " " og " " er relasjoner av en ikke-streng rekkefølge, relasjonene "<” и “>” – forhold av streng rekkefølge (på alle grunnleggende numeriske sett). Begge relasjonene bestiller settene fullstendig og .
b) Definer relasjonene " " og "<” на множестве следующим образом:
1) hvis 
;
2) hvis og samtidig gange for en koordinat gjennomføres.
Da skal f.eks. 
, men også uforlignelig. Dermed ordner disse forholdene delvis.,
c) På et system av delmengder av et sett spesifiserer inklusjonsrelasjonen " " en ikke-streng partiell rekkefølge, og den strenge inklusjonsrelasjonen " " spesifiserer en streng partiell rekkefølge. For eksempel 
, men ikke sammenlignbare.
d) Underordningsforholdet i arbeidskollektivet skaper en streng delorden. I den er for eksempel ansatte i ulike strukturelle divisjoner (avdelinger osv.) uforlignelige.
e) I det russiske alfabetet er bokstavrekkefølgen fast, det vil si at den alltid er den samme. Denne listen definerer deretter den fullstendige rekkefølgen av bokstavene, som kalles forrangsrelasjonen. Er indikert med (forut). Med utgangspunkt i bokstavers forrangsrelasjon konstrueres ordens forrangsrelasjon, bestemt omtrent på samme måte som to desimalbrøker sammenlignes. Denne relasjonen spesifiserer den fullstendige rekkefølgen av ord i det russiske alfabetet, som kalles leksikografisk rekkefølge.
Eksempel 4.
a) Det mest kjente eksemplet på leksikografisk rekkefølge av ord er rekkefølgen av ord i ordbøker. For eksempel (siden), derfor ordet skog plassert foran ordet i ordboken sommer.
b) Hvis vi betrakter tall i posisjonelle tallsystemer (for eksempel i desimalsystemet) som ord i tallalfabetet, så faller deres leksikografiske rekkefølge sammen med den vanlige hvis alle tallene som sammenlignes har samme antall sifre. Generelt kan det hende at disse to typene ikke faller sammen. For eksempel, og, men, en. For at de skal falle sammen, må du utjevne antall sifre for alle sammenlignede tall, ved å tilskrive Igjen nuller. I dette eksemplet får vi . Denne justeringen skjer automatisk når du skriver heltall inn i en datamaskin.
c) Leksikografisk rekkefølge av digitale representasjoner av datoer som 19.07.2004 (nittende juli to tusen og fire) faller ikke sammen med den naturlige rekkefølgen av datoer fra tidligere til senere. For eksempel er datoen 19.07.2004 "leksikografisk" eldre enn den attende dagen i et hvilket som helst år. For at de økende datoene skal falle sammen med den leksikografiske rekkefølgen, må den vanlige representasjonen være "invertert", det vil si skrives i formen 2004.07.19. Dette gjøres vanligvis når du representerer datoer i datamaskinens minne.
Ethvert sett med 2-lister eller par kalles en relasjon. Relasjoner vil være spesielt nyttige når man diskuterer meningen med programmer.
Ordet "relasjon" kan bety en sammenligningsregel, "ekvivalens" eller "er en undergruppe", etc. Formelt sett kan relasjoner, som er sett med 2-lister, beskrive disse uformelle reglene nøyaktig ved å inkludere nøyaktig de parene hvis elementer er i ønsket forhold til hverandre. For eksempel er forholdet mellom tegn og 1-strenger som inneholder disse tegnene gitt av følgende forhold:
C = (
Siden en relasjon er et sett, er en tom relasjon også mulig. For eksempel eksisterer ikke samsvaret mellom partall naturlige tall og deres odde kvadrater. Dessuten gjelder faste operasjoner for relasjoner. Hvis s og r er relasjoner, så er det det
s È r, s – r, s Ç r
siden dette er sett med ordnede par av elementer.
Et spesialtilfelle av en relasjon er en funksjon, en relasjon med en spesiell egenskap, karakterisert ved at hvert første element er paret med et unikt andre element. Relasjonen r er en funksjon hvis og bare hvis for noen
I dette tilfellet kan hvert første element tjene som et navn for det andre i sammenheng med forholdet. For eksempel er C-relasjonen mellom tegn og 1-strenger beskrevet ovenfor en funksjon.
Settoperasjoner gjelder også for funksjoner. Selv om resultatet av en operasjon på sett med ordnede par som er funksjoner, nødvendigvis vil være et annet sett med ordnede par, og derfor en relasjon, er det ikke alltid en funksjon.
Hvis f, g er funksjoner, så er f Ç g, f – g også funksjoner, men f È g kan være en funksjon eller ikke. La oss for eksempel definere relasjonshodet
H = (< Θ y, y>: y - streng) = (
Og ta forholdet C beskrevet ovenfor. Så fra det faktum at C Í H:
er en funksjon
H - C = (< Θ y, y>: y – streng på minst 2 tegn)
er en relasjon, men ikke en funksjon,
er en tom funksjon, og
er et forhold.
Settet med de første elementene av parene i en relasjon eller funksjon kalles definisjonsdomenet, og settet med de andre elementene i parene kalles området. For relasjonselementer, si
Når
lyder "y er r-verdien til x" eller, kortere, "y er r-verdien til x" (funksjonell form).
La oss sette en vilkårlig relasjon r og argument x, så er det tre alternativer for korrespondansen deres:
- x Р domene(r), i dette tilfellet r ikke definert av x
- x О domene(r), og det er forskjellige y, z slik at
- x О domene(r), og det er et unikt par
Dermed er en funksjon en relasjon som er unikt definert for alle elementer i dens definisjonsdomene.
Det er tre spesialfunksjoner:
Tom funksjon(), har ingen argumenter eller verdier, altså
domene(()) = (), område(()) = ()
Identitetsfunksjon, funksjon jeg er,
at hvis x О domene(r), så er I(x) = x.
Konstant funksjon, hvis verdiområde er spesifisert av et 1-sett, det vil si at alle argumenter tilsvarer samme verdi.
Siden relasjoner og funksjoner er sett, kan de beskrives ved å liste elementer eller spesifisere regler. For eksempel:
r = (<†ball†, †bat†>, <†ball†, †game†>, <†game†, †ball†>}
er en relasjon siden alle dens elementer er 2-lister
domene(r) = (†ball†, †spill†)
område (r) = (†ball†, †spill†, †bat†)
Imidlertid er r ikke en funksjon fordi to forskjellige verdier er paret med det samme argumentet †ball†.
Et eksempel på en relasjon definert ved hjelp av en regel:
s = (
i linjen †dette er en relasjon som ikke er en funksjon†)
Dette forholdet kan også spesifiseres ved en oppregning:
s = (<†this†, †is†>, <†is†, †a†>, <†a†, †relation†>, <†relation†, †that†>,
<†that†, †is†>, <†is†, †not†>, <†not†, †a†>, <†a†, †function†>}
Følgende regel definerer funksjonen:
f = (
i linjen †dette er en relasjon som også er en funksjon†)
som også kan spesifiseres med en oppregning:
f = (<†this†, †is†>, <†is†, †a†>, <†a†, †relation†>,
<†relation†, †that†>, <†that†, †is†>, <†also†, †a†>}
Betydningen av programmer.
Relasjoner og funksjoner er avgjørende for beskrivelser for å beskrive meningen med programmer. Ved å bruke disse konseptene utvikles en notasjon for å beskrive betydningen av programmer. For enkle programmer vil betydningen være åpenbar, men disse enkle eksemplene vil tjene til å mestre teorien som helhet.
Nye ideer: boksnotasjon, program og programbetydning.
Settet med input-out-par for alle mulige normale utføringer av et program kalles programverdien. Begrepene kan også brukes programfunksjon Og program holdning. Det er viktig å skille mellom meningen med et program og betydningselementene. For en spesifikk inngang kan en Pascal-maskin styrt av et Pascal-program produsere en spesifikk utgang. Men meningen med et program er mye mer enn en måte å uttrykke resultatet av én bestemt utførelse. Det uttrykker alt mulig utførelse av et Pascal-program på en Pascal-maskin.
Et program kan ta input brutt i linjer og produsere utgang brutt i linjer. Dermed kan par i en programverdi være par med lister med tegnstrenger.
Boksnotasjon.
Ethvert Pascal-program er en tegnstreng som sendes til Pascal-maskinen for behandling. For eksempel:
P = †PROGRAM PrintHello(INPUT, OUTPUT); BEGIN WRITELN('HELLO') END.†
Representerer et av de første programmene som ble diskutert i begynnelsen av del I som en streng.
Du kan også skrive denne linjen ved å utelate linjemarkørene, som
P = PROGRAM PrintHello(INPUT, OUTPUT);
WRITELN('HEI')
Strengen P representerer syntaksen til programmet, og dens verdi vil vi skrive som P. Verdien av P er et sett med 2-lister (ordnede par) av lister med tegnstrenger der argumentene representerer inngangene til programmet og verdiene representerer utgangene til programmet, det vil si
P = (
og returnerer en liste over strenger M)
Boksnotasjon for programbetydning beholder syntaksen og semantikken til programmet, men skiller klart det ene fra det andre. For PrintHello-programmet ovenfor:
P = (
{
Sette programteksten i boksen:
P = PROGRAM PrintHello(INPUT, OUTPUT); BEGIN WRITELN('HELLO') END
Siden P er en funksjon,
PROGRAM PrintHello(INPUT, OUTPUT); BEGIN WRITELN('HELLO') END (L) =<†HELLO†>
for en hvilken som helst liste over strenger L.
Boksnotasjon skjuler måten programmet kontrollerer Pascal-maskinen på og viser bare hva som følger med utførelse. Begrepet "svart boks" brukes ofte for å beskrive en mekanisme kun sett fra utsiden når det gjelder innganger og utganger. Dermed er denne notasjonen egnet for betydningen av et program når det gjelder input-output. For eksempel R-programmet
PROGRAM PrintHelloInSteps(INPUT, OUTPUT);
SKRIV('HAN');
SKRIV('L');
WRITELN('LO')
Har samme betydning som P, det vil si R = P.
R-programmet har også et CFPascal-navn PrintHelloInSteps. Men siden strengen †PrintHelloInSteps† er en del av en R-streng, er det bedre å ikke bruke PrintHelloInSteps som navnet på et R-program i boksnotasjon.
Utstilling f av en mengde X inn i en mengde Y anses gitt hvis hvert element x i X er assosiert med nøyaktig ett element y av Y, betegnet f(x).
Settet X kalles definisjonsdomene kartlegging f, og mengden Y er rekke verdier. Sett med bestilte par
Г f = ((x, y) | x∈X, y∈Y, y = f(x))
ringte vise graf f. Det følger direkte av definisjonen at grafen til f er en delmengde av det kartesiske produktet X×Y:
Strengt tatt er et kart en trippel av sett (X, Y, G) slik at G⊂ X×Y, og hvert element x av X er det første elementet av nøyaktig ett par (x, y) av G. Angir det andre element av et slikt par ved f(x), får vi en mapping f av mengden X inn i mengden Y. Dessuten G=Г f. Hvis y=f(x), vil vi skrive f:x→y og si at element x går eller avbildes til element y; elementet f(x) kalles bildet av elementet x med hensyn til mappingen f. For å betegne tilordninger vil vi bruke notasjoner på formen f: X→Y.
La f: X→Y være en avbildning fra mengden X til mengden Y, og A og B er delmengder av henholdsvis settene X og Y. Mengden f(A)=(y| y=f(x) for noen x∈A) kalles vei sett A. Sett f − 1 (B)=(x| f(x) ∈B)
ringte prototype sett B. En avbildning f: A→Y der x→f(x) for alle x∈A kalles innsnevring kartlegging f til mengden A; innsnevringen vil bli betegnet med f| EN.
La det være tilordninger f: X→Y og g: Y→Z. Mappingen X→Z som x går til g(f(x)) under kalles komposisjon avbildninger f og g og er betegnet med fg.
En mapping av et sett X til X, der hvert element går inn i seg selv, x→x, kalles identisk og er betegnet med id X .
For en vilkårlig avbildning f: X→Y har vi id X ⋅f = f⋅id Y .
Mappingen f: X→Y kalles injektiv, hvis for noen elementer fra og det følger at . Mappingen f: X→Y kalles surjektiv, hvis hvert element y fra Y er bildet av et element x fra X, det vil si f(x)=y. Mappingen f: X→Y kalles bijektiv, hvis den er både injektiv og surjektiv. Det bijektive kartet f: X→Y er inverterbart. Dette betyr at det er en mapping g: Y→X kalt omvendt til en avbildning f slik at g(f(x))=x og f(g(y))=y for enhver x∈X, y∈Y. Inversen av f er betegnet med f − 1 .
Den inverterbare tilordningen f: X→Y-sett en-til-en korrespondanse mellom elementene i mengdene X og Y. Den injektive mappingen f: X→Y etablerer en en-til-en korrespondanse mellom mengden X og mengden f(X).
Eksempler. 1) Funksjonen f:R→R >0, f (x)=e x, etablerer en en-til-en korrespondanse mellom settet av alle reelle tall R og settet med positive reelle tall R >0. Den inverse av avbildningen f er avbildningen g:R >0 →R, g(x)=ln x.
2) Kartleggingen f:R→R ≥ 0, f(x)=x 2, settet av alle reelle R på settet med ikke-negative tall R ≥ 0 er surjektiv, men ikke injektiv, og er derfor ikke bijektiv.
Funksjonsegenskaper:
1. Sammensetningen av to funksjoner er en funksjon, dvs. hvis, da.
2. Sammensetningen av to bijektive funksjoner er en bijektiv funksjon, hvis , da .
3. En mapping har en invers mapping da og
hvis og bare hvis f er en bijeksjon, dvs. hvis, da.
Definisjon. n – lokal relasjon, eller n – lokalt predikat P, på mengdene A 2 ;...;
Betegnelse n - lokal relasjon P(x 1 ;x 2 ;…;x n). Når n=1 kalles relasjonen P unær og er en delmengde av settet A 1 . Binær(dobbel for n=2) relasjon er et sett med ordnede par.
Definisjon. For ethvert sett A kalles relasjonen den identiske relasjonen, eller diagonalen, og - den komplette relasjonen, eller det komplette kvadratet.
La P være en binær relasjon. Da definisjonsdomene for en binær relasjon P kalles et sett for noen y), og rekke verdier– et sett for noen x). Omvendt et sett kalles en relasjon til P.
Relasjonen P kalles reflekterende, hvis den inneholder alle parene av formen (x,x) for enhver x fra X. Relasjonen P kalles antirefleks, hvis den ikke inneholder noen par av formen (x,x). For eksempel er relasjonen x≤y refleksiv, og relasjonen x Relasjonen P kalles symmetrisk, hvis det sammen med hvert par (x,y) også inneholder et par (y,x). Symmetrien til forholdet P betyr at P = P –1. Relasjonen P kalles antisymmetrisk hvis (x;y) og (y;x), så er x=y. Relasjonen R kalles transitive, hvis, sammen med noen par (x,y) og (y,z), inneholder den også paret (x,z), det vil si fra xPy og yPz følger xPz. Egenskaper til binære relasjoner: Eksempel. La A=(x/x – arabisk tall); R=((x;y)/x,yA,x-y=5). Finn D;R;P -1. Løsning. Relasjonen P kan skrives på formen P=((5;0);(6;1);(7;2);(8;3);(9;4)), så for den har vi D= (5;6;7;8;9); E=(0;1;2;3;4); P-1 =((0;5);(1;6);(2;7);(3;8);(4;9)). Tenk på to endelige sett og en binær relasjon. La oss introdusere matrisen til den binære relasjonen P som følger: . Matrisen til enhver binær relasjon har egenskaper: 1. Hvis og , da , og addisjonen av matriseelementer utføres i henhold til reglene 0+0=0; 1+1=1; 1+0=0+1=1, og multiplikasjon er termvis på vanlig måte, dvs. i henhold til reglene 1*0=0*1=0; 1*1=1. 2. Hvis , da , og matrisene multipliseres etter den vanlige regelen for matrisemultiplikasjon, men produktet og summen av elementer ved multiplisering av matriser er funnet i henhold til reglene i trinn 1. 4. Hvis , da og Eksempel. Den binære relasjonen er vist i fig. 2. Matrisen har formen . Løsning. La da; La P være en binær relasjon på mengden A, . Relasjonen P på mengden A kalles reflekterende, hvis , hvor asterisker indikerer nuller eller enere. Relasjonen P kalles irrefleksiv, Hvis . Relasjonen P på mengden A kalles symmetrisk, dersom for og for det følger av vilkåret at . Dette betyr at . Relasjonen P kalles antisymmetrisk, hvis det følger av betingelsene at x=y, dvs. eller . Denne egenskapen fører til at alle elementene i matrisen utenfor hoveddiagonalen vil være null (det kan også være nuller på hoveddiagonalen). Relasjonen P kalles transitive, hvis fra og det følger at , dvs. . Eksempel. Relasjonen P og Her på hoveddiagonalen til matrisen er alle enheter, derfor er P refleksiv. Matrisen er asymmetrisk, deretter er forholdet P asymmetrisk Fordi ikke alle elementer som ligger utenfor hoveddiagonalen er null, da er ikke relasjonen P antisymmetrisk. De. , derfor er relasjonen P intransitiv. En refleksiv, symmetrisk og transitiv relasjon kalles ekvivalensforhold. Det er vanlig å bruke symbolet ~ for å betegne ekvivalensrelasjoner. Betingelsene for refleksivitet, symmetri og transitivitet kan skrives som følger: Eksempel. 1) La X være et sett med funksjoner definert på hele tallinjen. Vi vil anta at funksjonene f og g er relatert av relasjonen ~ hvis de tar de samme verdiene ved punkt 0, det vil si f(x)~g(x), hvis f(0)=g(0) . For eksempel sinx~x, e x ~cosx. Relasjonen ~ er refleksiv (f(0)=f(0) for enhver funksjon f(x)); symmetrisk (fra f(0)=g(0) følger det at g(0)=f(0)); transitiv (hvis f(0)=g(0) og g(0)=h(0), så f(0)=h(0)). Derfor er ~ en ekvivalensrelasjon. 2) La ~ være en relasjon på settet av naturlige tall slik at x~y, hvis x og y gir den samme resten når de divideres med 5. For eksempel, 6~11, 2~7, 1~6. Det er lett å se at denne relasjonen er refleksiv, symmetrisk og transitiv og derfor er en ekvivalensrelasjon. Delordreforhold En binær relasjon på et sett kalles hvis den er refleksiv, antisymmetrisk, transitiv, dvs. 1. - refleksivitet; 2. - antisymmetri; 3. - transitivitet. Et forhold av streng orden En binær relasjon på et sett kalles hvis den er antirefleksiv, antisymmetrisk, transitiv. Begge disse relasjonene kalles ordre relasjoner. Et sett der en ordrerelasjon er spesifisert, kan være: et fullstendig bestilt sett eller delvis bestilt. Delrekkefølge er viktig i tilfeller hvor vi på en eller annen måte ønsker å karakterisere forrang, dvs. bestemme under hvilke betingelser å anse et element i settet for å være overordnet et annet. Et delvis bestilt sett kalles lineært ordnet, hvis det ikke er noen uforlignelige elementer i den, dvs. en av betingelsene eller er oppfylt. For eksempel er sett med en naturlig rekkefølge på dem lineært ordnet. La r Í X X Y. Funksjonell relasjon- dette er et så binært forhold r, der hvert element samsvarer akkurat en slik at paret tilhører relasjonen eller slikt finnes ikke i det hele tatt:
eller. Funksjonell relasjon – det er et så binært forhold r, som følgende utføres for: .
Overalt en viss holdning– binær relasjon r, for hvilket Dr=X("det er ingen ensomme X"). Surjektiv relasjon– binær relasjon r, for hvilket Jr = Y("det er ingen ensomme y"). Injektiv holdning– en binær relasjon der forskjellige X samsvarer forskjellig på. Bijeksjon– funksjonell, overalt definert, injektiv, surjektiv relasjon, definerer en en-til-en korrespondanse av sett. For eksempel: La r= ((x, y) О R2 | y2 + x 2 = 1, y > 0). Holdning r- funksjonell, ikke definert overalt ("det er ensomme X"), ikke injektiv (det er forskjellige X, på), ikke surjektiv ("det er ensomme på"), ikke en bijeksjon. For eksempel: La Ã= ((x,y) О R 2 | y = x+1) Forholdet à er funksjonelt, Forholdet Ã- er definert overalt ("det er ingen ensomme X"), Relasjonen Ã- er injektiv (det er ingen forskjellige X, som tilsvarer det samme på), Forholdet Ã- er surjektiv ("det er ingen ensomme på"), Forholdet à er bijektiv, gjensidig homogen korrespondanse. For eksempel: La j=((1,2), (2,3), (1,3), (3,4), (2,4), (1,4)) defineres på settet N 4. Relasjonen j er ikke funksjonell, x=1 tilsvarer tre y: (1,2), (1,3), (1,4) Relasjonen j er ikke bestemt overalt D j =(1,2,3)1 N 4 Relasjonen j er ikke surjektiv jeg j =(1,2,3)1 N 4 Relasjonen j er ikke injektiv; forskjellige x tilsvarer samme y, for eksempel (2.3) og (1.3). Laboratorieoppgave 1. Sett er gitt N1 Og N2. Beregn sett: (N1 X N2) Ç (N2 X N1); (N1 X N2) È (N2 X N1); (N1 Ç N2) x (N1 Ç N2); (N1 È N2) x (N1 È N2), Hvor N1 = ( sifrene i rekordboknummeret, de tre siste };
N2 = ( sifre for fødselsdato og -måned }.
2. Relasjoner r Og g er gitt på settet N6 = (1,2,3,4,5,6). Beskriv forholdet r,g,r -1 , r ○g, r - 1 ○g liste over par Finn relasjonsmatriser r Og g. Bestem definisjonsdomenet og verdidomenet for hvert forhold. Bestem egenskapene til relasjoner. Identifisere ekvivalensrelasjoner og konstruere ekvivalensklasser. Identifiser ordensrelasjoner og klassifiser dem. 1) r= {
(m,n) | m > n) g= {
(m,n) | sammenligning modulo 2 }
2) r= {
(m,n) | (m - n) delelig med 2 }
g= {
(m,n) | m skillelinje n) 3) r= {
(m,n) | m< n }
g= {
(m,n) | sammenligning modulo 3 }
4) r= {
(m,n) | (m + n)- til og med }
g= {
(m,n) | m 2 =n) 5) r= {
(m,n) | m/n- grad 2 }
g= {
(m,n) | m = n) 6) r= {
(m,n) | m/n- til og med }
g = ((m,n) | m³ n) 7) r= {
(m,n) | m/n- merkelig }
g= {
(m,n) | sammenligning modulo 4 }
8) r= {
(m,n) | m * n - til og med }
g= {
(m,n) | m£ n) 9) r= {
(m,n) | sammenligning modulo 5 }
g= {
(m,n) | m delt på n) 10) r= {
(m,n) | m- til og med, n- til og med }
g= {
(m,n) | m skillelinje n) 11) r= {
(m,n) | m = n) g= {
(m,n) | (m + n)£ 5 }
12) r={
(m,n) | m Og n ha den samme resten når de divideres med 3 }
g= {
(m,n) | (m-n)³2 }
13) r= {
(m,n) | (m + n) er delelig med 2 }
g = ((m,n) | £2 (m-n)£4 }
14) r= {
(m,n) | (m + n) delelig med 3 }
g= {
(m,n) | m¹ n) 15) r= {
(m,n) | m Og n har en felles deler }
g= {
(m,n) | m 2£ n) 16) r= {
(m,n) | (m - n) er delelig med 2 }
g= {
(m,n) | m< n +2 }
17) r= {
(m,n) | sammenligning modulo 4 }
g= {
(m,n) | m£ n) 18) r= {
(m,n) | m delelig med n) g= {
(m,n) | m¹ n, m- til og med }
19) r= {
(m,n) | sammenligning modulo 3 }
g= {
(m,n) | £1 (m-n)£3 }
20) r= {
(m,n) | (m - n) delelig med 4 }
g= {
(m,n) | m¹ n) 21) r= {
(m,n) | m- merkelig, n- merkelig }
g= {
(m,n) | m£ n, n- til og med }
22) r= {
(m,n) | m Og n ha en oddetall rest når deles på 3 }
g= {
(m,n) | (m-n)³1 }
23) r= {
(m,n) | m * n - merkelig }
g= {
(m,n) | sammenligning modulo 2 }
24) r= {
(m,n) | m * n - til og med }
g= {
(m,n) | £1 (m-n)£3 }
25) r= {
(m,n) | (m+ n) - til og med }
g= {
(m,n) | m er ikke helt delelig n) 26) r= {
(m,n) | m = n) g= {
(m,n) | m delelig med n) 27) r= {
(m,n) | (m-n)- til og med }
g= {
(m,n) | m skillelinje n) 28) r= {
(m,n) | (m-n)³2 }
g= {
(m,n) | m delelig med n) 29) r= {
(m,n) | m 2³ n) g= {
(m,n) | m / n- merkelig }
30) r= {
(m,n) | m³ n, m - til og med }
g= {
(m,n) | m Og n har en annen felles deler enn 1 }
3. Bestem om den gitte relasjonen er f- funksjonell, overalt definert, injektiv, surjektiv, bijeksjon ( R- sett med reelle tall). Konstruer en relasjonsgraf, bestem definisjonsdomenet og verdidomenet. Gjør den samme oppgaven for relasjoner r Og g fra pkt. 3 i laboratoriearbeid. 1) f=((x, y) Î R 2 | y=1/x +7x ) 2) f=((x, y) Î R 2 | x³ y) 3) f=((x, y) Î R 2 | y³ x) 4) f=((x, y) Î R 2 | y³ x, x³ 0 }
5) f=((x, y) Î R 2 | y 2 + x 2 = 1) 6) f=((x, y) Î R 2 | 2
| y | + | x | = 1) 7) f=((x, y) Î R 2 | x+y£ 1 }
8) f=((x, y) Î R 2 | x = y 2 ) 9) f=((x, y) Î R 2 | y = x 3 + 1) 10) f=((x, y) Î R 2 | y = -x 2) 11) f=((x, y) Î R 2 | | y | + | x | = 1) 12) f=((x, y) Î R 2 | x = y -2 ) 13) f=((x, y) Î R 2 | y2 + x2³ 1, år> 0 }
14) f=((x, y) Î R 2 | y 2 + x 2 = 1, x> 0 }
15) f=((x, y) Î R 2 | y2 + x2£ 1.x> 0 }
16) f=((x, y) Î R 2 | x = y 2 ,x³ 0 }
17) f=((x, y) Î R 2 | y = sin(3x + p) ) 18) f=((x, y) Î R 2 | y = 1 /cos x ) 19) f=((x, y) Î R 2 | y = 2| x | + 3) 20) f=((x, y) Î R 2 | y = | 2x + 1| ) 21) f=((x, y) Î R 2 | y = 3x) 22) f=((x, y) Î R 2 | y = e -x ) 23) f =((x, y)Î R 2 | y = e | x | ) 24) f=((x, y) Î R 2 | y = cos(3x) - 2 ) 25) f=((x, y) Î R 2 | y = 3x 2 - 2) 26) f=((x, y) Î R 2 | y = 1 / (x + 2) ) 27) f=((x, y) Î R 2 | y = ln(2x) - 2 ) 28) f=((x, y) Î R 2 | y = | 4x -1| + 2) 29) f=((x, y) Î R 2 | y = 1 / (x 2 +2x-5)) 30) f=((x, y) Î R 2 | x = y 3, y³ - 2 }.
Sikkerhetsspørsmål 2. Definisjon av en binær relasjon. 3. Metoder for å beskrive binære relasjoner. 4. Definisjonsdomene og verdiområde. 5. Egenskaper til binære relasjoner. 6.Ekvivalensrelasjoner og ekvivalensklasser. 7. Ordensforhold: streng og ikke-streng, fullstendig og delvis. 8. Klasser av rester modulo m. 9.Funksjonelle relasjoner. 10. Injeksjon, injeksjon, bijeksjon. Laboratoriearbeid nr. 3 Forhold. Grunnleggende begreper og definisjoner Definisjon 2.1.Bestilt par<x, y> kalt en samling av to elementer x Og y, ordnet i en bestemt rekkefølge. To bestilte par<x, y> og<u, v> er like hverandre hvis og bare hvis x = u Og y= v. Eksempel 2.1. <en, b>, <1, 2>, <x, 4> – bestilte par. På samme måte kan vi vurdere trillinger, firedobler, n-ki elementer<x 1 , x 2 ,… x n>. Definisjon 2.2.Direkte(eller kartesisk)arbeid to sett EN Og B er et sett med ordnede par slik at det første elementet i hvert par tilhører settet EN, og den andre – til settet B: EN ´ B = {<en, b>, ç enÎ EN Og bÏ I}. Generelt, det direkte produktet n sett EN 1 ,EN 2 ,…A n kalt et sett EN 1´ EN 2 '...' A n, bestående av ordnede sett med elementer<en 1 , en 2 , …,en n> lengde n, slik at jeg- th en i tilhører settet A i,en i Î A i. Eksempel 2.2. La EN = {1, 2}, I = {2, 3}. Da EN ´ B = {<1, 2>, <1, 3>,<2, 2>,<2, 3>}. Eksempel 2.3. La EN= {x ç0 £ x£ 1) og B= {yç2 £ y£3) Da EN ´ B = {<x, y >, ç0 £ x£1&2£ y£3). Dermed mange EN ´ B består av punkter som ligger innenfor og på grensen til et rektangel dannet av rette linjer x= 0 (y-akse), x= 1,y= 2i y = 3. Den franske matematikeren og filosofen Descartes var den første som foreslo en koordinert representasjon av punkter på et plan. Dette er historisk sett det første eksemplet på et direkte produkt. Definisjon 2.3.Binær(eller dobbelt)forhold r kalles settet med ordnede par. Hvis et par<x, y> hører til r, så er det skrevet som følger:<x, y> Î r eller, hva er det samme, xr y. Eksempel2.4. r = {<1, 1>, <1, 2>, <2, 3>} På samme måte kan vi definere n-lokal relasjon som et sett med bestilte n- OK. Siden en binær relasjon er et sett, er metodene for å spesifisere en binær relasjon de samme som metodene for å spesifisere et sett (se avsnitt 1.1). En binær relasjon kan spesifiseres ved å liste opp ordnede par eller ved å spesifisere en generell egenskap for ordnede par. Eksempel 2.5. 1. r = {<1, 2>, <2, 1>, <2, 3>) – relasjonen er spesifisert ved å telle opp ordnede par; 2. r = {<x, y> ç x+ y = 7, x, y– reelle tall) – relasjonen spesifiseres ved å spesifisere egenskapen x+ y = 7. I tillegg kan en binær relasjon gis binær relasjonsmatrise. La EN = {en 1 , en 2 , …, en n) er et begrenset sett. Binær relasjonsmatrise C er en kvadratisk matrise av orden n, hvis elementer c ij er definert som følger: Eksempel 2.6. EN= (1, 2, 3, 4). La oss definere en binær relasjon r på de tre oppførte måtene. 1. r = {<1, 2>, <1, 3>, <1, 4>, <2, 3>, <2, 4>, <3, 4>) – relasjonen spesifiseres ved å telle opp alle ordnede par. 2. r = {<en i, a j> ç en i < a j; en i, a jÎ EN) – relasjonen spesifiseres ved å indikere egenskapen "mindre enn" på settet EN. 3. – relasjonen er spesifisert av den binære relasjonsmatrisen C. Eksempel 2.7. La oss se på noen binære forhold. 1. Relasjoner på settet av naturlige tall. a) forholdet £ gjelder for par<1, 2>, <5, 5>, men holder ikke for paret<4, 3>; b) relasjonen «ha en annen felles deler enn én» gjelder for par<3, 6>, <7, 42>, <21, 15>, men holder ikke for paret<3, 28>. 2. Relasjoner på settet av punkter i det virkelige planet. a) forholdet "å være i samme avstand fra punktet (0, 0)" er oppfylt for punktene (3, 4) og (–2, Ö21), men er ikke oppfylt for punktene (1, 2) og ( 5, 3); b) forholdet «å være symmetrisk om aksen OY" utføres for alle punkter ( x, y) Og (- x, –y). 3. Forhold til mange mennesker. a) holdningen til å "bo i samme by"; b) holdningen til å "studere i samme gruppe"; c) «å være eldre»-holdningen. Definisjon 2.4. Definisjonsdomenet for en binær relasjon r er mengden D r = (x çdet er y slik at xr y). Definisjon 2.5. Verdiområdet til en binær relasjon r er mengden R r = (y çeksisterer x slik at xr y). Definisjon 2.6. Domenet for å spesifisere en binær relasjon r kalles mengden M r = D r ÈR r . Ved å bruke konseptet direkte produkt kan vi skrive: rÎ D r´ R r Hvis D r= R r = EN, så sier vi at den binære relasjonen r definert på settet EN. Eksempel 2.8. La r = {<1, 3>, <3, 3>, <4, 2>}. Da D r ={1, 3, 4}, R r = {3, 2}, Mr= {1, 2, 3, 4}. Operasjoner på relasjoner Siden relasjoner er sett, er alle operasjoner på sett gyldige for relasjoner. Eksempel 2.9. r 1 = {<1, 2>, <2, 3>, <3, 4>}. r 2 = {<1, 2>, <1, 3>, <2, 4>}. r 1 È r 2 = {<1, 2>, <1, 3>, <2, 3>, <2, 4>, <3, 4>}. r 1 Ç r 2 = {<1, 2>}. r 1 \ r 2 = {<2, 3>, <3, 4>}. Eksempel 2.10. La R– sett med reelle tall. La oss vurdere følgende forhold på dette settet: r 1 – "£"; r 2 – " = "; r 3 – " < "; r 4 – "³"; r 5 – " > ". r 1 = r 2 È r 3 ; r 2 = r 1 Ç r 4 ; r 3 = r 1 \ r 2 ; r 1 = ; La oss definere ytterligere to operasjoner på relasjoner. Definisjon 2.7. Forholdet kalles omvendt til holdning r(betegnet r – 1), hvis r – 1 = {<x, y> ç< y, x> Î r}. Eksempel 2.11. r = {<1, 2>, <2, 3>, <3, 4>}. r – 1 = {<2, 1>, <3, 2>, <4, 3>}. Eksempel 2.12. r = {<x, y> ç x – y = 2, x, y Î R}. r – 1 = {<x, y> ç< y, x> Î r} = r – 1 = {<x, y> ç y–x = 2, x, y Î R} = {<x, y> ç– x+ y = 2, x, y Î R}. Definisjon 2.8.Sammensetning av to relasjoner r og s kalt relasjon s r= {<x, z> det er noe slikt y, Hva<x, y> Î r Og< y, z> Î s}. Eksempel 2.13. r = {<x, y> ç y = sinx}. s= {<x, y> ç y = Ö x}. s r= {<x, z> det er noe slikt y, Hva<x, y> Î r Og< y, z> Î s} = {<x, z> det er noe slikt y, Hva y = sinx Og z= Ö y} = {<x, z> ç z= Ö sinx}. Definisjonen av sammensetningen av to relasjoner tilsvarer definisjonen av en kompleks funksjon: y = f(x), z= g(y) Þ z= g(f(x)). Eksempel 2.14. r = {<1, 1>, <1, 2>, <1, 3>, <3, 1>}. s = {<1, 2>, <1, 3>, <2, 2>, <3, 2>, <3, 3>}. Finneprosess s r i samsvar med definisjonen av sammensetning, er det praktisk å skildre det i en tabell der alle mulige verdier er oppregnet x, y, z. for hvert par<x, y> Î r vi må vurdere alle mulige par< y, z> Î s(Tabell 2.1). Tabell 2.1 Merk at den første, tredje og fjerde, samt andre og femte rad i den siste kolonnen i tabellen inneholder identiske par. Derfor får vi: s r= {<1, 2>, <1, 3>, <3, 2>, <3, 3>}. Egenskaper til relasjoner Definisjon 2.9. Holdning r ringte reflekterende på et sett X, hvis for noen xÎ X løping xr x. Av definisjonen følger det at hvert element<x,x > Î r. Eksempel 2.15. a) La X- begrenset sett, X= (1, 2, 3) og r = {<1, 1>, <1, 2>, <2, 2>, <3, 1>, <3, 3>). Holdning r reflekterende. Hvis X er en endelig mengde, så inneholder hoveddiagonalen til den refleksive relasjonsmatrisen bare enere. For vårt eksempel b) La X r likhetsforhold. Denne holdningen er refleksiv, fordi hvert tall er lik seg selv. c) La X- mye folk og r"bo i samme by" holdning. Denne holdningen er refleksiv, fordi alle bor i samme by med seg selv. Definisjon 2.10. Holdning r ringte symmetrisk på et sett X, hvis for noen x, yÎ X fra xry burde år x. Det er åpenbart det r symmetrisk hvis og bare hvis r = r – 1 . Eksempel 2.16. a) La X- begrenset sett, X= (1, 2, 3) og r = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <3, 1>, <3, 3>). Holdning r symmetrisk. Hvis X er et begrenset sett, så er den symmetriske relasjonsmatrisen symmetrisk i forhold til hoveddiagonalen. For vårt eksempel b) La X– sett med reelle tall og r likhetsforhold. Dette forholdet er symmetrisk, fordi Hvis x lik y, da y lik x. c) La X– mange studenter og r"studer i samme gruppe" holdning. Dette forholdet er symmetrisk, fordi Hvis x studier i samme gruppe som y, da y studier i samme gruppe som x. Definisjon 2.11. Holdning r ringte transitive på et sett X, hvis for noen x, y,zÎ X fra xry Og år z burde xr z. Samtidig oppfyllelse av vilkår xry, år z, xr z betyr at paret<x,z> hører til komposisjonen r r. Derfor for transitivitet r det er nødvendig og tilstrekkelig for settet r r var en undergruppe r, dvs. r rÍ r. Eksempel 2.17. a) La X- begrenset sett, X= (1, 2, 3) og r = {<1, 1>, <1, 2>, <2, 3>, <1, 3>). Holdning r transitive, fordi sammen med par<x,y> og<y,z> har et par<x,z>. For eksempel sammen med par<1, 2>, Og<2, 3>det er et par<1, 3>. b) La X– sett med reelle tall og r forhold £ (mindre enn eller lik). Denne relasjonen er transitiv, fordi Hvis x£ y Og y£ z, Det x£ z. c) La X- mye folk og r"å være eldre" holdning. Denne relasjonen er transitiv, fordi Hvis x eldre y Og y eldre z, Det x eldre z. Definisjon 2.12. Holdning r ringte ekvivalensforhold på et sett X, hvis den er refleksiv, symmetrisk og transitiv på settet X. Eksempel 2.18. a) La X- begrenset sett, X= (1, 2, 3) og r = {<1, 1>, <2, 2>, <3, 3>). Holdning r er en ekvivalensrelasjon. b) La X– sett med reelle tall og r likhetsforhold. Dette er en ekvivalensrelasjon. c) La X– mange studenter og r"studer i samme gruppe" holdning. Dette er en ekvivalensrelasjon. La r X. Definisjon 2.13. La r– ekvivalensforhold på settet X Og xÎ X. Ekvivalensklasse, generert av elementet x, kalles en delmengde av settet X, som består av disse elementene yÎ X, for hvilket xry. Ekvivalensklasse generert av element x, betegnet med [ x]. Dermed [ x] = {yÎ X|xry}. Ekvivalensklassene dannes skillevegg sett X, dvs. et system av ikke-tomme parvise usammenhengende undergrupper av det, hvis forening sammenfaller med hele settet X. Eksempel 2.19. a) Likhetsrelasjonen på settet med heltall genererer følgende ekvivalensklasser: for ethvert element x fra dette settet [ x] = {x), dvs. hver ekvivalensklasse består av ett element. b) Ekvivalensklassen generert av paret<x, y> bestemmes av forholdet: [<x, y>] = . Hver ekvivalensklasse generert av et par<x, y>, definerer ett rasjonelt tall. c) For forholdet til å tilhøre en elevgruppe, er ekvivalensklassen settet med elever fra samme gruppe. Definisjon 2.14. Holdning r ringte antisymmetrisk på et sett X, hvis for noen x, yÎ X fra xry Og år x burde x = y. Fra definisjonen av antisymmetri følger det at når et par<x,y>eid på samme tid r Og r – 1 , skal likestillingen være oppfylt x = y. Med andre ord, r Ç r – 1 består kun av par av formen<x,x >. Eksempel 2.20. a) La X- begrenset sett, X= (1, 2, 3) og r = {<1, 1>, <1, 2>, <1, 3>, <2, 2>, <2, 3>, <3, 3>). Holdning r antisymmetrisk. Holdning s= {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 3>, <3, 3>) er ikke-antisymmetrisk. For eksempel<1, 2> Î s, Og<2, 1> Î s, men 1¹2. b) La X– sett med reelle tall og r forhold £ (mindre enn eller lik). Dette forholdet er antisymmetrisk, fordi Hvis x £ y, Og y £ x, Det x = y. Definisjon 2.15. Holdning r ringte delordreforhold(eller bare en delbestilling) på settet X, hvis den er refleksiv, antisymmetrisk og transitiv på settet X. Mange X i dette tilfellet kalles det delvis ordnet og den spesifiserte relasjonen er ofte betegnet med symbolet £, hvis dette ikke fører til misforståelser. Inversen av partiell ordensrelasjon vil åpenbart være en partiell ordensrelasjon. Eksempel 2.21. a) La X- begrenset sett, X= (1, 2, 3) og r = {<1, 1>, <1, 2>, <1, 3>, <2, 2>, <2, 3>, <3, 3>). Holdning r b) Holdning ENÍ I på settet med undersett av et sett U det er en delvis ordensrelasjon. c) Delbarhetsrelasjonen på mengden av naturlige tall er en partiell ordensrelasjon. Funksjoner. Grunnleggende begreper og definisjoner I matematisk analyse aksepteres følgende definisjon av en funksjon. Variabel y kalt en funksjon av en variabel x, hvis i henhold til noen regel eller lov hver verdi x tilsvarer én bestemt verdi y = f(x). Variabelt endringsområde x kalles definisjonsdomenet til en funksjon, og endringsdomenet til en variabel y– rekkevidde av funksjonsverdier. Hvis én verdi x tilsvarer flere (og til og med uendelig mange verdier) y), så kalles funksjonen multiverdi. Men i kurset om analyse av funksjoner til reelle variabler unngås flerverdifunksjoner og enkeltverdifunksjoner vurderes. La oss vurdere en annen definisjon av funksjon når det gjelder relasjoner. Definisjon 2.16. Funksjon er enhver binær relasjon som ikke inneholder to par med like første komponenter og forskjellige andre. Denne egenskapen til et forhold kalles entydighet eller funksjonalitet. Eksempel 2.22. A) (<1, 2>, <3, 4>, <4, 4>, <5, 6>) – funksjon. b) (<x, y>: x, y Î R, y = x 2) – funksjon. V) (<1, 2>, <1, 4>, <4, 4>, <5, 6>) er en relasjon, men ikke en funksjon. Definisjon 2.17. Hvis f– funksjon, altså D f – definisjonsdomene, A Rf – spekter funksjoner f. Eksempel 2.23. For eksempel 2.22 a) D f – {1, 3, 4, 5}; Rf – {2, 4, 6}. For eksempel 2.22 b) D f = Rf = (–¥, ¥). Hvert element x D f funksjon samsvarer den eneste element y Rf. Dette er betegnet med den velkjente notasjonen y = f(x). Element x kalt et funksjonsargument eller element preimage y med funksjon f, og elementet y funksjonsverdi f på x eller elementbilde x på f. Så fra alle relasjoner skiller funksjoner seg ut ved at hvert element fra definisjonsdomenet har den eneste bilde. Definisjon 2.18. Hvis D f = X Og Rf = Y, så sier de at funksjonen f bestemt på X og tar sine verdier på Y, A f ringte kartlegge settet X til Y(X ® Y). Definisjon 2.19. Funksjoner f Og g er like hvis domenet deres er det samme settet D, og for hvem som helst x Î D likhet er sant f(x) = g(x). Denne definisjonen motsier ikke definisjonen av funksjonslikhet som settlikhet (vi definerte tross alt en funksjon som en relasjon, dvs. et sett): sett f Og g er like hvis og bare hvis de består av de samme elementene. Definisjon 2.20. Funksjon (display) f ringte surjektiv eller bare injeksjon, hvis for et element y Y det er et element x Î X, slik at y = f(x). Så hver funksjon f er en surjektiv kartlegging (oversikt) D f® Rf. Hvis f er en injeksjon, og X Og Y er endelige mengder, så ³ . Definisjon 2.21. Funksjon (display) f ringte injektiv eller bare injeksjon eller en-til-en, hvis fra f(en) = f(b) bør en = b. Definisjon 2.22. Funksjon (display) f ringte bijektiv eller bare bijeksjon, hvis den er både injektiv og surjektiv. Hvis f er en bijeksjon, og X Og Y er endelige mengder, da = . Definisjon 2.23. Hvis rekkevidden til funksjonen D f består av ett element, da f ringte konstant funksjon. Eksempel 2.24. EN) f(x) = x 2 er en kartlegging fra settet med reelle tall til settet med ikke-negative reelle tall. Fordi f(–en) = f(en), Og en ¹ – en, så er ikke denne funksjonen en injeksjon. b) For alle x R= (– , ) funksjon f(x) = 5 – konstant funksjon. Den viser mange R for å stille inn (5). Denne funksjonen er surjektiv, men ikke injektiv. V) f(x) = 2x+ 1 er en injeksjon og en bijeksjon, fordi av 2 x 1 +1 = 2x 2 +1 følger x 1 = x 2 . Definisjon 2.24. Funksjon som implementerer skjermen X 1´ X 2 '...' Xn ® Y ringte n-lokale funksjon. Eksempel 2.25. a) Addisjon, subtraksjon, multiplikasjon og divisjon er to-plassers funksjoner på en mengde R reelle tall, dvs. funksjoner som R 2® R. b) f(x, y) = er en to-plassers funksjon som implementerer kartleggingen R ´ ( R \ )® R. Denne funksjonen er ikke en injeksjon, fordi f(1, 2) = f(2, 4). c) Lotterigevinsttabellen spesifiserer en to-plassers funksjon som etablerer korrespondanse mellom par av N 2 (N– et sett med naturlige tall) og et sett med gevinster. Siden funksjoner er binære relasjoner, er det mulig å finne inverse funksjoner og bruke komposisjonsoperasjonen. Sammensetningen av to funksjoner er en funksjon, men ikke for hver funksjon f holdning f–1 er en funksjon. Eksempel 2.26. EN) f = {<1, 2>, <2, 3>, <3, 4>, <4, 2>) – funksjon. Holdning f –1 = {<2, 1>, <3, 2>, <4, 3>, <2, 4>) er ikke en funksjon. b) g = {<1, en>, <2, b>, <3, c>, <4, D>) er en funksjon. g -1 = {<en, 1>, <b, 2>, <c, 3>, <D, 4>) er også en funksjon. c) Finn sammensetningen av funksjoner f fra eksempel a) og g-1 fra eksempel b). Vi har g -1f = {<en, 2>, <b, 3>, <c, 4>, <d, 2>}. fg-1 = Æ. Merk at ( g -1f)(en) = f(g -1 (en)) = f(1) = 2; (g -1f)(c) = f(g -1 (c)) = f(3) = 4. En elementær funksjon i matematisk analyse er en hvilken som helst funksjon f, som er en sammensetning av et begrenset antall aritmetiske funksjoner, samt følgende funksjoner: 1) Brøk-rasjonelle funksjoner, dvs. funksjonene til skjemaet en 0 + en 1 x + ... + a n x n b 0 + b 1 x + ... + b m x m. 2) Strømfunksjon f(x) = x m, Hvor m– ethvert konstant reelt tall. 3) Eksponentiell funksjon f(x) = e x. 4) logaritmisk funksjon f(x) = logg en x, en >0, en 1. 5) Trigonometriske funksjoner sin, cos, tg, ctg, sek, csc. 6) Hyperbolske funksjoner sh, ch, th, cth. 7) Inverse trigonometriske funksjoner arcsin, arccos osv. For eksempel funksjonen logg 2 (x 3 +sincos 3x) er elementær, fordi det er en sammensetning av funksjoner cosx, sinx, x 3 , x 1 + x 2 , logx, x 2 . Et uttrykk som beskriver sammensetningen av funksjoner kalles en formel. For en flerplassfunksjon er følgende viktige resultat gyldig, oppnådd av A.N. Kolmogorov og V.I. Arnold i 1957, og som er en løsning på Hilberts 13. problem: Teorem. Enhver kontinuerlig funksjon n variabler kan representeres som en sammensetning av kontinuerlige funksjoner av to variabler. Metoder for å spesifisere funksjoner 1. Den enkleste måten å spesifisere funksjoner på er gjennom tabeller (tabell 2.2): Tabell 2.2 Imidlertid kan funksjoner definert på endelige sett defineres på denne måten. Hvis en funksjon definert på et uendelig sett (segment, intervall) er gitt ved et begrenset antall punkter, for eksempel i form av trigonometriske tabeller, tabeller med spesialfunksjoner, etc., brukes interpolasjonsregler for å beregne verdiene av funksjoner på mellomliggende punkter. 2. En funksjon kan angis som en formel som beskriver funksjonen som en sammensetning av andre funksjoner. Formelen spesifiserer rekkefølgen for å beregne funksjonen. Eksempel 2.28. f(x) = synd(x + Ö x) er en sammensetning av følgende funksjoner: g(y) = Ö y; h(u, v) = u+ v; w(z) = sinz. 3. Funksjonen kan angis som rekursiv prosedyre. Den rekursive prosedyren spesifiserer en funksjon definert på settet av naturlige tall, dvs. f(n), n= 1, 2,... som følger: a) still inn verdien f(1) (eller f(0)); b) verdi f(n+ 1) bestemt gjennom sammensetning f(n) og andre kjente funksjoner. Det enkleste eksemplet på en rekursiv prosedyre er beregningen n!: a) 0! = 1; b) ( n + 1)! = n!(n+ 1). Mange numeriske metodeprosedyrer er rekursive prosedyrer. 4. Det er mulige måter å spesifisere en funksjon som ikke inneholder en metode for å beregne funksjonen, men kun beskriver den. For eksempel: f M(x) = Funksjon f M(x) – karakteristisk funksjon av settet M. Så, i henhold til vår definisjon, definer en funksjon f– betyr å stille inn displayet X ® Y, dvs. definere et sett X´ Y, så spørsmålet handler om å spesifisere et bestemt sett. Det er imidlertid mulig å definere begrepet en funksjon uten å bruke mengdeteoriens språk, nemlig: en funksjon anses som gitt dersom det er gitt en beregningsprosedyre som, gitt verdien av argumentet, finner den tilsvarende verdien av funksjonen. En funksjon definert på denne måten kalles beregnelig. Eksempel 2.29. Fastsettingsprosedyre Fibonacci tall, er gitt av relasjonen Fn= Fn- 1 + Fn- 2 (n³ 2) (2.1) med startverdier F 0 = 1, F 1 = 1. Formel (2.1) sammen med startverdiene bestemmer følgende serie med Fibonacci-tall: Beregningsprosedyren for å bestemme verdien av en funksjon fra en gitt argumentverdi er ikke mer enn algoritme. Testspørsmål for emne 2 1. Angi måter å definere en binær relasjon på. 2. Hoveddiagonalen til matrisen av hvilken relasjon inneholder kun en? 3. For hvilket forhold? r vilkåret er alltid oppfylt r = r – 1 ? 4. For hvilken holdning r vilkåret er alltid oppfylt r rÍ r. 5. Introduser ekvivalensrelasjoner og delvis rekkefølge på settet av alle linjer i planet. 6. Spesifiser måter å spesifisere funksjoner på. 7. Hvilket av følgende utsagn er sant? a) Hver binær relasjon er en funksjon. b) Hver funksjon er en binær relasjon. Emne 3. GRAFIER Eulers første arbeid med grafteori dukket opp i 1736. I begynnelsen var denne teorien assosiert med matematiske gåter og spill. Imidlertid begynte grafteori å bli brukt i topologi, algebra og tallteori. I dag brukes grafteori i en lang rekke områder innen vitenskap, teknologi og praktisk aktivitet. Det brukes i design av elektriske nettverk, transportplanlegging og konstruksjon av molekylære kretser. Grafteori brukes også innen økonomi, psykologi, sosiologi og biologi.
<x, y> Î r
< y, z> Î s
<x, z> Î s r
<1, 1>
<1, 1>
<1, 2>
<1, 3>
<1, 3>
<3, 1>
<3, 1>
<1, 2>
<1, 3>
<2, 2>
<3, 2>
<3, 3>
<1, 2>
<1, 3>
<1, 2>
<1, 3>
<1, 2>
<1, 2>
<1, 3>
<3, 2>
<3, 3>
n
0 1 2 3 4 5 6 7 8 9 10 11 …
Fn
1 1 2 3 5 8 13 21 34 55 89 144 …