Funcții, tipuri, niveluri de comunicare. Relații funcționale Funcții. Concepte de bază și definiții

1. Curs nr. 1. Seturi și operații asupra lor.
2. Curs nr. 2. Corespondenţe şi funcţii.
3. Curs nr. 3. Relaţiile şi proprietăţile lor.
4. Curs nr. 4. Tipuri de bază de relaţii.
5. Curs nr. 5. Elemente de algebră generală.
6. Curs nr. 6. Diverse tipuri de structuri algebrice.
7. Curs nr. 7. Elemente de logică matematică.
8. Curs nr. 8. Funcţii logice.
9. Curs nr. 9. Algebre booleene.
10. Curs nr. 10. Algebre booleene și teoria mulțimilor.
11. Curs nr. 11. Completitudine și încheiere.
12. Prelegerea nr. 12. Limbajul logicii predicatelor.
13. Curs nr. 13. Combinatorică.
14. Curs nr. 14. Grafice: concepte de bază și operații.
15. Prelegerea nr. 15. Trasee, lanțuri și bucle.
16. Curs nr. 16. Câteva clase de grafice și părțile lor.

SECȚIUNEA I. SETĂRI, FUNCȚII, RELAȚII.

Curs nr. 2. Corespondenţe şi funcţii.

1. Chibrituri.

Definiţie. Corespondența dintre mulțimile A și B este o anumită submulțime G a produsului lor cartezian: .

Dacă , atunci ei spun că corespunde atunci când corespunde . În acest caz, setul tuturor acestor valori se numește domeniul de definire a corespondenței, iar setul de valori corespunzătoare se numește domeniul valorilor corespondenței.

În notația acceptată, fiecare element corespunzător unui element dat este numit mod atunci când corespunde, dimpotrivă, elementul este numit prototip element pentru o corespondență dată.

Conformitatea se numește pe deplin definite, dacă , adică fiecare element al mulţimii are cel puţin o imagine în mulţime; altfel meciul este numit parţial.

Conformitatea se numește surjectiv, dacă, adică dacă fiecărui element al setului îi corespunde cel puțin o preimagine din set.

Conformitatea se numește funcțional (neambiguu), dacă vreun element al mulţimii corespunde unui singur element al mulţimii.

Conformitatea se numește injectiv, dacă este funcțional, iar fiecare element al mulțimii are cel mult o imagine inversă.

Conformitatea se numește unu-la-unu (bijectiv), dacă vreun element al mulțimii corespunde unui singur element al mulțimii și invers. De asemenea, putem spune că o corespondență este unu-la-unu dacă este complet definită, surjectivă, funcțională, iar fiecare element al setului are un singur prototip.

Exemplul 1.

a) Dicționarul englez-rus stabilește corespondența între seturile de cuvinte în rusă și engleză. Nu este funcțional, deoarece aproape fiecare cuvânt rusesc are mai multe traduceri în engleză; De asemenea, nu este, de regulă, o potrivire complet definită, deoarece există întotdeauna cuvinte în limba engleză care nu sunt incluse într-un anumit dicționar. Deci aceasta este o potrivire parțială.

b) Corespondența dintre argumentele unei funcții și valorile acelei funcție este funcțională. Cu toate acestea, nu este unul la unu, deoarece fiecare valoare a funcției corespunde la două imagini inverse și .

c) Corespondența dintre piesele aflate pe tabla de șah și câmpurile pe care le ocupă este unu-la-unu.

d) Corespondența dintre telefoanele orașului Vyazma și numerele lor din cinci cifre are, la prima vedere, toate proprietățile unei corespondențe unu-la-unu. Cu toate acestea, de exemplu, nu este surjectiv, deoarece există numere din cinci cifre care nu corespund niciunui telefon.

2. Corespondențe unu-la-unu și puteri ale mulțimilor.

Dacă există o corespondență unu-la-unu între două mulțimi finite A și B, atunci aceste mulțimi sunt de cardinalitate egală. Acest fapt evident permite, în primul rând, să se stabilească egalitatea cardinalității acestor mulțimi fără a le calcula. În al doilea rând, este adesea posibil să se calculeze cardinalitatea unei mulțimi prin stabilirea corespondenței sale unu-la-unu cu o mulțime a cărei cardinalitate este cunoscută sau poate fi ușor calculată.

Teorema 2.1. Dacă cardinalitatea unei mulţimi finite O este egal cu , apoi numărul tuturor submulților O egal , adică .

Se numeste multimea tuturor submultimii multimii M boolean si este desemnat . Pentru mulţimile finite se aplică următoarele: .

Definiţie. Seturi OŞi ÎN sunt numite echivalente dacă între elementele lor se poate stabili o corespondență unu-la-unu.

Rețineți că pentru mulțimile finite această afirmație este ușor de demonstrat. Pentru mulțimi infinite, va determina însuși conceptul de cardinalitate egală.

Definiţie. Multe O se numeste numarabil daca este echivalent cu multimea numerelor naturale: .

Într-un mod foarte simplificat, putem spune că o mulțime infinită dată este numărabilă dacă elementele sale pot fi numerotate folosind numere naturale.

Fără dovezi, să acceptăm o serie de fapte importante:

1. Orice submulțime infinită a mulțimii numerelor naturale este numărabilă.

2. Setul este numărabil.

3. Mulțimea numerelor raționale este numărabilă (este o consecință a afirmației anterioare).

4. Unirea unui număr finit de mulțimi numărabile este numărabilă.

5. Unirea unui număr numărabil de mulțimi finite este numărabilă.

6. Unirea unui număr numărabil de mulțimi numărabile este numărabilă.

Toate aceste afirmații, după cum se poate observa, ne permit să stabilim cu succes faptul că acest set este numărabil. Cu toate acestea, acum se va arăta că nu orice set infinit este numărabil; există seturi de putere mai mare.

Teorema 2.2 (teorema lui Cantor). Mulțimea tuturor numerelor reale dintr-un segment nu este numărabilă.

Dovada. Să presupunem că mulțimea este numărabilă și există o numerotare pentru el. Deoarece orice număr real poate fi reprezentat ca o fracție zecimală infinită (periodic sau neperiodic), vom face acest lucru cu numerele acestei mulțimi. Să le aranjam în această ordine de numerotare:

Acum luați în considerare orice fracție zecimală infinită a formei , organizată în așa fel încât și așa mai departe. Evident, această fracție nu este inclusă în succesiunea luată în considerare, deoarece diferă de primul număr prin prima zecimală, de al doilea cu a doua cifră și așa mai departe. În consecință, am primit un număr din acest interval care nu este numerotat și, astfel, mulțimea nu este numărabilă. Puterea lui se numește continuum, iar seturile de astfel de cardinalități sunt numite continuu. Metoda de demonstrare de mai sus se numește Metoda diagonalei lui Cantor.

Corolarul 1. Mulțimea numerelor reale este continuă.

Corolarul 2. Mulțimea tuturor submulților dintr-o mulțime numărabilă este continuă.

Așa cum se arată în teoria mulțimilor (folosind o metodă similară cu cea dată mai sus), pentru o mulțime de orice cardinalitate, mulțimea tuturor submulțimii sale (boolean) are o cardinalitate mai mare. Prin urmare, nu există un set de cardinalitate maximă. De exemplu, universul set descris de Cantor trebuie să conțină toate mulțimile imaginabile, dar el însuși este conținut în mulțimea submulțimii sale ca element (paradoxul lui Cantor). Se pare că setul nu este un set de cardinalitate maximă.

3. Afișaje și funcții.

Funcţie este orice corespondență funcțională între două mulțimi. Dacă o funcție stabilește o corespondență între mulțimile A și B, atunci se spune că funcția are forma (notația ). Fiecărui element din domeniul său de definire, funcția atribuie un singur element din domeniul valorilor. Acesta este scris în formă tradițională. Elementul este numit argument funcție, element - it sens.

Se apelează o funcție complet definită afişa A la B; imaginea setului A când este afișată este notă cu . Dacă în același timp, adică corespondența este surjectivă, spunem că există o mapare de la A la B.

Dacă este format dintr-un singur element, se numește funcție constantă.

O mapare de tip se numește o transformare a unei mulțimi A.

Exemplul 2.

a) Funcția este o mapare a mulțimii de numere naturale în sine (funcția injectivă). Aceeași funcție pentru toți este o mapare de la mulțimea de numere întregi la mulțimea de numere raționale.

b) Funcția este o mapare de la mulțimea numerelor întregi (cu excepția lui 0) la mulțimea numerelor naturale. Mai mult, în acest caz corespondența nu este unu-la-unu.

c) Funcția este o mapare unu-la-unu a setului de numere reale pe sine.

d) O funcție nu este complet definită dacă tipul ei este , dar este complet definită dacă tipul ei este sau .

Definiţie. Tipul funcției numită funcţie locală. În acest caz, se acceptă în general că funcția are argumente: , Unde .

De exemplu, adunarea, înmulțirea, scăderea și împărțirea sunt funcții cu două locuri pe , adică funcții de tip .

Definiţie. Să fie dată corespondența. Dacă corespondența este astfel încât dacă și numai dacă , atunci corespondența se numește inversă și se notează cu .

Definiţie. Dacă corespondența inversă cu o funcție este funcțională, atunci se numește funcție inversă.

Evident, în corespondență inversă, imaginile și prototipurile își schimbă locurile, de aceea, pentru existența unei funcții inverse, se cere ca fiecare element din domeniul valoric să aibă un singur prototip. Aceasta înseamnă că pentru o funcție, funcția inversă există dacă și numai dacă este o corespondență bijectivă între domeniul ei de definiție și domeniul său de valori.

Exemplul 3. Funcția are tipul . Mapează un segment unu-la-unu pe un segment. Prin urmare, există o funcție inversă pentru acesta pe segment. După cum știți, acesta este.

Definiţie. Lasă funcțiile și să fie date. O funcție se numește o compunere de funcții și (notat cu ) dacă egalitatea este valabilă: , Unde .

Compoziția funcțiilor este aplicarea secvențială a acestor funcții; aplicat rezultatului Se spune adesea că funcţia este obţinută substituţie V .

Pentru funcțiile cu mai multe locuri, sunt posibile diferite variante de substituții în, producând funcții de diferite tipuri. De interes deosebit este cazul când multe funcții de tip: . În acest caz, în primul rând, orice substituție de funcții între ele este posibilă și, în al doilea rând, orice redenumire a argumentelor. O funcție obținută din aceste funcții prin înlocuirea lor unele în altele și redenumirea argumentelor se numește suprapunerea lor.

De exemplu, în analiza matematică este introdus conceptul de funcție elementară, care este o suprapunere a unui număr fix (independent de valoarea argumentului) de operații aritmetice, precum și a funcțiilor elementare (etc.).

UN. Kolmogorov și V.I. Arnold a demonstrat că fiecare funcție continuă a variabilelor poate fi reprezentată ca o suprapunere a funcțiilor continue a două variabile.

Comentariu. Conceptul de funcție este utilizat pe scară largă în analiza matematică, în plus, este un concept de bază; În general, abordarea înțelegerii termenului „funcție” în analiza matematică este oarecum mai restrânsă decât în ​​matematica discretă. De regulă, consideră așa-numitul calculabil funcții. O funcție se numește calculabilă dacă este dată o procedură care permite să găsești valoarea funcției pentru orice valoare dată a argumentului.

Înapoi la începutul rezumatului.

Exemplul 1.

a) O relație de egalitate (deseori notată cu ) pe orice mulțime este o relație de echivalență. Egalitatea este o relație de echivalență minimă în sensul că atunci când orice pereche este îndepărtată din această relație (adică orice unitate de pe diagonala principală a matricei), ea încetează să mai fie reflexivă și, prin urmare, nu mai este o echivalență.

b) Declarație de tip sau , constând din formule legate printr-un semn egal, definesc o relație binară pe un set de formule care descriu suprapuneri de funcții elementare. Această relație este de obicei numită relație de echivalență și este definită după cum urmează: două formule sunt echivalente dacă definesc aceeași funcție. Echivalența în acest caz, deși este indicată de semnul „=”, nu înseamnă același lucru cu relația de egalitate, deoarece poate fi satisfăcută pentru diferite formule. Cu toate acestea, putem presupune că semnul egal în astfel de relații nu se referă la formulele în sine, ci la funcțiile pe care le descriu. Pentru formule, relația de egalitate este coincidența formulelor în ortografie. Se numește egalitate grafică. Apropo, pentru a evita discrepanțe în astfel de situații, semnul „ ” este adesea folosit pentru a indica relația de echivalență.

c) Se consideră o mulțime de triunghiuri pe planul de coordonate, presupunând că un triunghi este dat dacă sunt date coordonatele vârfurilor sale. Vom considera două triunghiuri egale (congruente) dacă, atunci când sunt suprapuse, ele coincid, adică sunt translate unul în celălalt folosind o anumită mișcare. Egalitatea este o relație de echivalență pe o mulțime de triunghiuri.

d) Relația „a avea același rest de un număr natural” pe mulțimea numerelor naturale este o relație de echivalență.

f) Relația „a fi divizor” nu este o relație de echivalență pe o mulțime. Are proprietăți de reflexivitate și tranzitivitate, dar este antisimetric (vezi mai jos).

Fie specificată o relație de echivalență pe o mulțime. Să realizăm următoarea construcție. Să selectăm un element și să formăm o clasă (subset) constând din elementul și toate elementele echivalente cu acesta în cadrul relației date. Apoi selectați elementul și formează o clasă formată din și elemente echivalente. Continuând aceste acțiuni, obținem un sistem de clase (posibil infinit) astfel încât orice element din mulțime este inclus în cel puțin o clasă, adică.

Acest sistem are următoarele proprietăți:

1) se formează compartimentare mulţimile, adică clasele nu se intersectează în perechi;

2) oricare două elemente din aceeași clasă sunt echivalente;

3) oricare două elemente din clase diferite nu sunt echivalente.

Toate aceste proprietăți rezultă direct din definiția unei relații de echivalență. Într-adevăr, dacă, de exemplu, clasele ar fi suprimate, acestea ar avea cel puțin un element comun. Acest element ar fi evident echivalent cu și . Apoi, datorită tranzitivității relației, . Cu toate acestea, din cauza modului în care sunt construite clasele, acest lucru nu este posibil. Celelalte două proprietăți pot fi dovedite în mod similar.

Partiția construită, adică un sistem de clase - submulțimi ale mulțimii, se numește sistem clase de echivalenţăîn raport cu . Puterea acestui sistem se numește index de partiție. Pe de altă parte, orice partiție a unui set în clase determină în sine o relație de echivalență, și anume relația „să fie inclusă într-o clasă a unei partiții date”.

Exemplul 2.

a) Toate clasele de echivalență cu privire la relația de egalitate constau dintr-un singur element.

b) Formulele care descriu aceeași funcție elementară sunt în aceeași clasă de echivalență în raport cu relația de echivalență. În acest caz, setul de formule în sine, setul de clase de echivalență (adică indicele de partiție) și fiecare clasă de echivalență sunt numărabile.

c) Împărțirea unei mulțimi de triunghiuri în raport cu egalitatea are un indice de continuu, iar fiecare clasă are și o cardinalitate de continuu.

d) Împărțirea mulțimii numerelor naturale în raport cu relația „au un rest comun când se împarte la 7” are un indice final de 7 și este formată din șapte clase numărabile.

1. Relații de ordine.

Definiția 1. Relația se numește relație non-strictă, dacă este reflexiv, antisimetric și tranzitiv.

Definiția 2. Relația se numește relație de ordine strictă, dacă este antireflexiv, antisimetric și tranzitiv.

Ambele tipuri de relații sunt numite colectiv relații de ordine. Elementele sunt comparabile în raport cu relația de ordine dacă una dintre cele două relații sau este satisfăcută. O mulțime pe care este specificată o relație de ordine este numită complet ordonată dacă oricare dintre elementele sale sunt comparabile. În caz contrar, setul se numește parțial ordonat.

Exemplul 3.

a) Relațiile „ ” și „ ” sunt relații de ordin nestrict, relațiile „<” и “>” – relații de ordine strictă (pe toate mulțimile numerice de bază). Ambele relaţii ordonează complet mulţimile şi .

b) Definiți relațiile „ ” și „<” на множестве следующим образом:

1) dacă ;

2) dacă și în același timp se efectuează mersul pentru o coordonată.

Atunci, de exemplu, , dar și incomparabil. Astfel, aceste relații ordonează parțial.,

c) Pe un sistem de submulțimi ale unei mulțimi, relația de includere „ ” specifică o ordine parțială nestrict, iar relația de incluziune strictă „ ” specifică o ordine parțială strictă. De exemplu, , dar nu comparabil.

d) Raportul de subordonare în colectivul de muncă creează o ordine parțială strictă. În ea, de exemplu, angajații diferitelor divizii structurale (departamente etc.) sunt incomparabili.

e) În alfabetul rus, ordinea literelor este fixă, adică este întotdeauna aceeași. Această listă definește apoi ordonarea completă a literelor, care se numește relație de precedență. Este indicat prin (precedează). Pe baza relației de precedență a literelor se construiește relația de precedență a cuvintelor, determinată aproximativ în același mod în care se compară două fracții zecimale. Această relație specifică ordonarea completă a cuvintelor în alfabetul rus, care se numește ordonare lexicografică.

Exemplul 4.

a) Cel mai cunoscut exemplu de ordonare lexicografică a cuvintelor este ordonarea cuvintelor în dicționare. De exemplu, (din moment ce), deci cuvântul pădure situat înaintea cuvântului din dicționar vară.

b) Dacă considerăm numerele din sistemele de numere poziționale (de exemplu, în sistemul zecimal) drept cuvinte din alfabetul numerelor, atunci ordonarea lor lexicografică coincide cu cea obișnuită dacă toate numerele comparate au același număr de cifre. În general, aceste două tipuri pot să nu coincidă. De exemplu, și, dar, a. Pentru ca acestea să coincidă, trebuie să egalizați numărul de cifre pentru toate numerele comparate, atribuind stânga zerouri. În acest exemplu, obținem . Această aliniere are loc automat atunci când scrieți numere întregi într-un computer.

c) Ordonarea lexicografică a reprezentărilor digitale ale unor date precum 19.07.2004 (19 iulie două mii patru) nu coincide cu ordonarea naturală a datelor de la mai devreme la mai târziu. De exemplu, data 19.07.2004 este „lexicografic” mai veche decât a optsprezecea zi a oricărui an. Pentru ca datele crescătoare să coincidă cu ordonarea lexicografică, reprezentarea obișnuită trebuie să fie „inversată”, adică scrisă sub forma 2004.07.19. Acest lucru se face de obicei atunci când reprezintă datele în memoria computerului.

Orice set de 2 liste sau perechi se numește relație. Relațiile vor fi deosebit de utile atunci când discutăm despre semnificația programelor.

Cuvântul „relație” poate însemna o regulă de comparație, „echivalență” sau „este un submult”, etc. Formal, relațiile, care sunt seturi de 2-liste, pot descrie aceste reguli informale tocmai incluzând exact acele perechi ale căror elemente se află în relația dorită între ele. De exemplu, relația dintre caractere și 1-șiruri care conțin aceste caractere este dată de următoarea relație:

C = ( : x - simbol) = ( , , …}

Deoarece o relație este o mulțime, este posibilă și o relație goală. De exemplu, corespondența dintre numerele naturale pare și pătratele lor impare nu există. Mai mult, operațiunile setate se aplică relațiilor. Dacă s și r sunt relații, atunci există

s È r, s – r, s Ç r

întrucât acestea sunt mulţimi de perechi ordonate de elemente.

Un caz special al unei relații este o funcție, o relație cu o proprietate specială, caracterizată prin aceea că fiecare prim element este asociat cu un al doilea element unic. Relația r este o funcție dacă și numai dacă pentru oricare

О r și О r, atunci y = z.

În acest caz, fiecare prim element poate servi drept nume pentru al doilea în contextul relației. De exemplu, relația C dintre caractere și 1-șiruri descrisă mai sus este o funcție.

Operațiile de setare se aplică și funcțiilor. Deși rezultatul unei operații pe mulțimi de perechi ordonate care sunt funcții va fi în mod necesar un alt set de perechi ordonate și, prin urmare, o relație, nu este întotdeauna o funcție.

Dacă f, g sunt funcții, atunci f Ç g, f – g sunt de asemenea funcții, dar f È g poate fi sau nu o funcție. De exemplu, să definim capul relației

H = (< Θ y, y>: y - șir) = ( , , …}

Și luați relația C descrisă mai sus. Apoi din faptul că C Í H:

este o funcție

H - C = (< Θ y, y>: y – șir de cel puțin 2 caractere)

este o relație, dar nu o funcție,

este o funcție goală și

este o relație.

Mulțimea primelor elemente ale perechilor unei relații sau funcție se numește domeniul de definiție, iar mulțimea celor doua elemente ale perechilor se numește interval. Pentru elementele de relație, să zicem О r, x se numește argument r, iar y se numește sens r.

Când Î r și și y este singura valoare pentru x, notație de valoare:

citește „y este valoarea r a lui x” sau, mai pe scurt, „y este valoarea r a lui x” (forma funcțională).

Să stabilim o relație arbitrară r și argumentul x, atunci există trei opțiuni pentru corespondența lor:

1. x Р domeniu(r), în acest caz r nedefinit prin x
2. x О domeniu(r), și există diferite y, z astfel încât О r și О r. În acest caz, r nu este determinat în mod unic pe x
3. x О domeniu(r) și există o pereche unică О r. În acest caz, r este determinat în mod unic pe x și y=r(x).

Astfel, o funcție este o relație care este definită în mod unic pentru toate elementele domeniului său de definire.

Există trei funcții speciale:

Funcție goală(), nu are argumente sau valori, adică

domeniu(()) = (), interval(()) = ()

Funcția de identitate, funcția I este,

că dacă x О domeniu(r), atunci I(x) = x.

Funcție constantă, al cărui interval de valori este specificat de un set 1, adică toate argumentele corespund aceleiași valori.

Deoarece relațiile și funcțiile sunt mulțimi, ele pot fi descrise prin enumerarea elementelor sau prin specificarea regulilor. De exemplu:

r = (<†ball†, †bat†>, <†ball†, †game†>, <†game†, †ball†>}

este o relație deoarece toate elementele sale sunt 2-liste

domeniu(r) = (†minge†, †joc†)

interval (r) = (†minge†, †joc†, †bat†)

Cu toate acestea, r nu este o funcție deoarece două valori diferite sunt asociate cu același argument †ball†.

Un exemplu de relație definită folosind o regulă:

s = ( : cuvântul x precede imediat cuvântul y

în linie †aceasta este o relație care nu este o funcție†)

Această relație poate fi specificată și printr-o enumerare:

s = (<†this†, †is†>, <†is†, †a†>, <†a†, †relation†>, <†relation†, †that†>,

<†that†, †is†>, <†is†, †not†>, <†not†, †a†>, <†a†, †function†>}

Următoarea regulă definește funcția:

f = ( : prima instanță a cuvântului imediat înaintea cuvântului y

în linie †aceasta este o relație care este și o funcție†)

care poate fi specificat și printr-o enumerare:

f = (<†this†, †is†>, <†is†, †a†>, <†a†, †relation†>,

<†relation†, †that†>, <†that†, †is†>, <†also†, †a†>}

Sensul programelor.

Relațiile și funcțiile sunt vitale pentru descrieri pentru a descrie semnificația programelor. Folosind aceste concepte, se dezvoltă o notație pentru a descrie semnificația programelor. Pentru programele simple semnificația va fi evidentă, dar aceste exemple simple vor servi la stăpânirea teoriei în ansamblu.

Idei noi: notarea casetei, sensul programului și programului.

Setul de perechi intrare-ieșire pentru toate execuțiile normale posibile ale unui program se numește valoarea programului. Conceptele pot fi de asemenea folosite funcția programuluiŞi atitudinea programului. Este important să se facă distincția între semnificația unui program și elementele de semnificație. Pentru o intrare specifică, o mașină Pascal controlată de un program Pascal poate produce o ieșire specifică. Dar sensul unui program este mult mai mult decât un mod de a exprima rezultatul unei anumite execuții. Ea exprimă tot posibil execuția unui program Pascal pe o mașină Pascal.

Un program poate prelua intrarea divizată în linii și poate produce ieșiri împărțite în linii. Astfel, perechile dintr-o valoare de program pot fi perechi de liste de șiruri de caractere.

Notarea casetei.

Orice program Pascal este un șir de caractere transmis mașinii Pascal pentru procesare. De exemplu:

P = †PROGRAM PrintHello(INTRARE, IEȘIRE); ÎNCEPE WRITELN('BUNA') SFÂRȘIT.†

Reprezintă unul dintre primele programe discutate la începutul părții I sub formă de șir.

De asemenea, puteți scrie această linie omițând marcatorii de linie, cum ar fi

P = PROGRAM PrintHello(INTRARE, IEȘIRE);

WRITELN('BUNA')

Șirul P reprezintă sintaxa programului, iar valoarea lui o vom scrie ca P. Valoarea lui P este un set de 2-liste (perechi ordonate) de liste de șiruri de caractere în care argumentele reprezintă intrările programului și valorile reprezintă ieșirile programului, adică

P = ( : pentru o listă de intrare de șiruri L, P este executată corect

și returnează o listă de șiruri M)

Notația casetă pentru semnificația programului păstrează sintaxa și semantica programului, dar distinge clar una de alta. Pentru programul PrintHello de mai sus:

P = ( } =

{>: L – orice listă de șiruri)

Introducerea textului programului în casetă:

P = PROGRAM PrintHello(INTRARE, IEȘIRE); BEGIN WRITELN('HELLO') END

Deoarece P este o funcție,

PROGRAM PrintHello (INTRARE, IEȘIRE); BEGIN WRITELN('HELLO') END (L) =<†HELLO†>

pentru orice listă de șiruri L.

Notarea casetei ascunde modul în care programul controlează mașina Pascal și arată doar ceea ce însoțește execuția. Termenul „cutie neagră” este adesea folosit pentru a descrie un mecanism privit doar din exterior în ceea ce privește intrările și ieșirile. Astfel, această notație este potrivită pentru semnificația unui program în termeni de intrare-ieșire. De exemplu, programul R

PROGRAM PrintHelloInSteps(INTRARE, IEȘIRE);

SCRIE('EL');

SCRIE('L');

WRITELN('LO')

Are același sens ca P, adică R = P.

Programul R are, de asemenea, un nume CFPascal PrintHelloInSteps. Dar, deoarece șirul †PrintHelloInSteps† face parte dintr-un șir R, este mai bine să nu folosiți PrintHelloInSteps ca nume al unui program R în notație casetă.

Afişa f dintr-o mulțime X într-o mulțime Y este considerată dată dacă fiecare element x al lui X este asociat exact cu un element y al lui Y, notat f(x).

Se numește mulțimea X domeniul definirii maparea f, iar mulțimea Y ​​este intervalul de valori. Set de perechi ordonate

Г f = ((x, y) | x∈X, y∈Y, y = f(x))

numit afisare grafic f. Rezultă direct din definiție că graficul lui f este o submulțime a produsului cartezian X×Y:

Strict vorbind, o hartă este un triplu de mulțimi (X, Y, G) astfel încât G⊂ X×Y și fiecare element x al lui X este primul element din exact o pereche (x, y) a lui G. Notă al doilea element al unei astfel de perechi prin f(x), obținem o mapare f a mulțimii X în mulțimea Y. Mai mult, G=Г f. Dacă y=f(x), vom scrie f:x→y și vom spune că elementul x merge sau mapează elementul y; elementul f(x) se numește imaginea elementului x în raport cu maparea f. Pentru a desemna mapările vom folosi notații de forma f: X→Y.

Fie f: X→Y o mapare de la mulțimea X la mulțimea Y, iar A și B sunt submulțimi ale mulțimilor X și Y, respectiv. Mulțimea f(A)=(y| y=f(x) pentru unele x∈A) se numește mod mulţimea A. Mulţimea f − 1 (B)=(x| f(x) ∈B)

numit prototip mulţimea B. O mapare f: A→Y sub care se numeşte x→f(x) pentru toate x∈A îngustarea maparea f la mulțimea A; îngustarea se va nota cu f| O.

Să fie mapări f: X→Y și g: Y→Z. Este numită maparea X→Z sub care x merge la g(f(x)). compoziţie mapările f și g și se notează cu fg.

Se numește o mapare a unei mulțimi X în X, în care fiecare element intră în sine, x→x identicși se notează cu id X .

Pentru o mapare arbitrară f: X→Y avem id X ⋅f = f⋅id Y .

Se numește maparea f: X→Y injectiv, dacă pentru orice elemente din și rezultă că . Se numește maparea f: X→Y surjectiv, dacă fiecare element y din Y este imaginea unui element x din X, adică f(x)=y. Se numește maparea f: X→Y bijectiv, dacă este atât injectiv cât și surjectiv. Harta bijectivă f: X→Y este inversabilă. Aceasta înseamnă că există o mapare g: Y→X numită verso la o hartă f astfel încât g(f(x))=x și f(g(y))=y pentru orice x∈X, y∈Y. Inversa lui f se notează cu f − 1 .

Maparea inversabilă f: X→Y setează unu-la-unu corespondența dintre elementele mulțimilor X și Y. Maparea injectivă f: X→Y stabilește o corespondență unu-la-unu între mulțimea X și mulțimea f(X).

Exemple. 1) Funcția f:R→R >0, f (x)=e x, stabilește o corespondență unu-la-unu între mulțimea tuturor numerelor reale R și mulțimea numerelor reale pozitive R >0. Inversul mapării f este maparea g:R >0 →R, g(x)=ln x.

2) Aplicarea f:R→R ≥ 0, f(x)=x 2, mulțimea tuturor R reale pe mulțimea numerelor nenegative R ≥ 0 este surjectivă, dar nu injectivă și, prin urmare, nu este bijectivă.

Proprietățile funcției:

1. Alcătuirea a două funcții este o funcție, i.e. daca , atunci .

2. Alcătuirea a două funcții bijective este o funcție bijectivă, dacă , atunci .

3. O mapare are o mapare inversă atunci și

dacă și numai dacă f este o bijecție, i.e. daca , atunci .

Definiţie. n – relație locală, sau n – predicat local P, pe mulțimile A 1 ;… Și n este orice submulțime a produsului cartezian;

Denumirea n - relație locală P(x 1 ;x 2 ;…;x n). Când n=1 se numește relația P unarși este o submulțime a mulțimii A 1 . Binar(dublu pentru n=2) relația este o mulțime de perechi ordonate.

Definiţie. Pentru orice mulțime A, relația se numește relație identică sau diagonală și - relația completă sau pătrat complet.

Fie P o relație binară. Apoi domeniul de definire a unei relații binare P se numește mulțime pentru unele y) și intervalul de valori– un set pentru niște x). Verso o mulțime se numește relație cu P.

Relația P se numește reflectorizant, dacă conține toate perechile de forma (x,x) pentru orice x din X. Se numește relația P antireflex, dacă nu conține nicio pereche de forma (x,x). De exemplu, relația x≤y este reflexivă, iar relația x

Relația P se numește simetric, dacă împreună cu fiecare pereche (x,y) conține și o pereche (y,x). Simetria relației P înseamnă că P = P –1.

Relația P se numește antisimetric, dacă (x;y) și (y;x), atunci x=y.

Relația R se numește tranzitiv, dacă, împreună cu orice perechi (x,y) și (y,z), conține și perechea (x,z), adică din xPy și yPz urmează xPz.

Proprietățile relațiilor binare:

Exemplu. Fie A=(x/x – cifra arabă); Р=((x;y)/x,yA,x-y=5). Găsiţi D;R;P-1.

Soluţie. Relația P se poate scrie sub forma P=((5;0);(6;1);(7;2);(8;3);(9;4)), atunci pentru ea avem D= (5;6;7;8;9); E=(0;1;2;3;4); P-1 =((0;5);(1;6);(2;7);(3;8);(4;9)).

Luați în considerare două mulțimi finite și o relație binară. Să introducem matricea relaţiei binare P astfel: .

Matricea oricărei relații binare are proprietati:

1. Dacă și , atunci , și adăugarea elementelor matricei se realizează conform regulilor 0+0=0; 1+1=1; 1+0=0+1=1, iar înmulțirea este în termeni în mod obișnuit, adică. conform regulilor 1*0=0*1=0; 1*1=1.

2. Dacă , atunci , și matricele sunt înmulțite conform regulii obișnuite pentru înmulțirea matricelor, dar produsul și suma elementelor la înmulțirea matricelor se găsesc conform regulilor pasului 1.

4. Dacă , atunci și

Exemplu. Relația binară este prezentată în Fig. 2. Matricea sa are forma .

Soluţie. Să, atunci;

Fie P o relație binară pe mulțimea A, . Relația P pe mulțimea A se numește reflectorizant, dacă , unde asteriscurile indică zerouri sau unu. Relația P se numește ireflexiv, Dacă . Relația P pe mulțimea A se numește simetric, daca pentru si pentru rezulta din conditia ca . Aceasta înseamnă că . Relația P se numește antisimetric, dacă din condiţiile rezultă că x=y, adică. sau . Această proprietate conduce la faptul că toate elementele matricei din afara diagonalei principale vor fi zero (pot exista și zerouri pe diagonala principală). Relația P se numește tranzitiv, dacă din și rezultă că , i.e. .

Exemplu. Relația P și . Aici pe diagonala principală a matricei sunt toate unitățile, prin urmare, P este reflexiv. Matricea este asimetrică, apoi raportul P este asimetric

Deoarece nu toate elementele situate în afara diagonalei principale sunt zero, atunci relația P nu este antisimetrică.

Aceste. , deci relatia P este intranzitiva.

Se numește relație reflexivă, simetrică și tranzitivă relație de echivalență. Se obișnuiește să se folosească simbolul ~ pentru a desemna relații de echivalență. Condițiile de reflexivitate, simetrie și tranzitivitate pot fi scrise astfel:

Exemplu. 1) Fie X un set de funcții definite pe întreaga linie numerică. Vom presupune că funcțiile f și g sunt legate prin relația ~ dacă iau aceleași valori la punctul 0, adică f(x)~g(x), dacă f(0)=g(0) . De exemplu, sinx~x, e x ~cosx. Relația ~ este reflexivă (f(0)=f(0) pentru orice funcție f(x)); simetric (din f(0)=g(0) rezulta ca g(0)=f(0)); tranzitiv (dacă f(0)=g(0) și g(0)=h(0), atunci f(0)=h(0)). Prin urmare, ~ este o relație de echivalență.

2) Fie ~ o relație pe mulțimea numerelor naturale astfel încât x~y, dacă x și y dau același rest atunci când sunt împărțite la 5. De exemplu, 6~11, 2~7, 1~6. Este ușor de observat că această relație este reflexivă, simetrică și tranzitivă și, prin urmare, este o relație de echivalență.

Relație de ordine parțială O relație binară pe o mulțime se numește dacă este reflexivă, antisimetrică, tranzitivă, adică

1. - reflexivitate;

2. - antisimetrie;

3. - tranzitivitatea.

O relație de ordine strictă O relație binară pe o mulțime se numește dacă este antireflexivă, antisimetrică, tranzitivă. Ambele relații sunt numite relații de ordine. Un set pe care este specificată o relație de ordine, poate fi: un set complet comandat sau parțial comandat. Ordinea parțială este importantă în cazurile în care dorim să caracterizăm cumva precedența, de exemplu. decide în ce condiţii să considere un element al mulţimii ca fiind superior altuia. Se numește un set parțial ordonat ordonat liniar, dacă nu există elemente incomparabile în el, i.e. una dintre condiţii sau este îndeplinită. De exemplu, seturile cu o ordine naturală pe ele sunt ordonate liniar.

Lasă r Í X X Y.

Relație funcțională- aceasta este o relație atât de binară r,în care fiecare element corespunde exact unul astfel încât perechea să aparțină relației sau așa nu exista deloc: sau.

Relatie functionala - este o relație atât de binară r, pentru care se execută următoarele: .

Peste tot o anumită atitudine– relație binară r, pentru care D r =X(„nu există singuri X").

Relația surjectivă– relație binară r, pentru care J r = Y(„nu există singuri y").

Atitudine injectivă– o relație binară în care diferă X corespund diferit la.

Bijectie– relație funcțională, definită peste tot, injectivă, surjectivă, definește o corespondență unu-la-unu de mulțimi.

De exemplu:

Lasă r= ( (x, y) О R 2 | y 2 + x 2 = 1, y > 0 ).

Atitudine r- funcţional,

nu este definit peste tot („există singuri X"),

nu injectiv (sunt diferite X, la),

nu surjectiv („există singuri la"),

nu o bijectie.

De exemplu:

Fie Ã= ((x,y) О R 2 | y = x+1)

Relația à este funcțională,

Relația Ã- este definită peste tot („nu există singuratici X"),

Relația Ã- este injectivă (nu sunt diferite X, care corespund aceluiaşi la),

Relația Ã- este surjectivă („nu există singuratici la"),

Relația à este bijectivă, corespondență reciproc omogenă.

De exemplu:

Fie j=((1,2), (2,3), (1,3), (3,4), (2,4), (1,4)) să fie definit pe mulțime N 4.

Relația j nu este funcțională, x=1 corespunde la trei y: (1,2), (1,3), (1,4)

Relația j nu este definită peste tot D j =(1,2,3)¹ N 4

Relația j nu este surjectivă eu j =(1,2,3)¹ N 4

Relația j nu este injectivă, x diferite corespund aceluiași y, de exemplu (2.3) și (1.3).

Sarcina de laborator

1. Se dau seturi N1Şi N2. Calculați seturile:

(N1 X N2) Ç (N2 X N1);

(N1 X N2) È (N2 X N1);

(N1 Ç N2) x (N1 Ç N2);

(N1 È N2) x (N1 È N2),

Unde N1 = ( cifre ale numărului cărții de înregistrare, ultimele trei };

N2 = ( cifre ale datei și lunii nașterii }.

2. Relații rŞi g sunt date pe platou N6 =(1,2,3,4,5,6).

Descrieți relația r,g,r -1 , r ○g, r - 1 ○g lista de perechi

Găsiți matrici de relații rŞi g.

Pentru fiecare relație, determinați domeniul definiției și domeniul valorilor.

Determinați proprietățile relațiilor.

Identificați relațiile de echivalență și construiți clase de echivalență.

Identificați relațiile de ordine și clasificați-le.

1) r= { (m,n) | m > n)

g= { (m,n) | comparație modulo 2 }

2) r= { (m,n) | (m - n) divizibil cu 2 }

g= { (m,n) | m separator n)

3) r= { (m,n) | m< n }

g= { (m,n) | comparație modulo 3 }

4) r= { (m,n) | (m + n)- chiar }

g= { (m,n) | m2 =n)

5) r= { (m,n) | m/n- gradul 2 }

g= { (m,n) | m = n)

6) r= { (m,n) | m/n- chiar }

g = ((m,n) | m³ n)

7) r= { (m,n) | m/n- ciudat }

g= { (m,n) | comparație modulo 4 }

8) r= { (m,n) | m * n - chiar }

g= { (m,n) | m£ n)

9) r= { (m,n) | comparație modulo 5 }

g= { (m,n) | mîmpărțit la n)

10) r= { (m,n) | m-chiar, n- chiar }

g= { (m,n) | m separator n)

11) r= { (m,n) | m = n)

g= { (m,n) | (m + n)£ 5 }

12) r={ (m,n) | mŞi n au același rest când se împarte la 3 }

g= { (m,n) | (m-n)³2 }

13) r= { (m,n) | (m + n) este divizibil cu 2 }

g = ((m,n) | £2 (m-n) 4 GBP }

14) r= { (m,n) | (m + n) divizibil cu 3 }

g= { (m,n) | m¹ n)

15) r= { (m,n) | mŞi n au un divizor comun }

g= { (m,n) | m 2£ n)

16) r= { (m,n) | (m - n) este divizibil cu 2 }

g= { (m,n) | m< n +2 }

17) r= { (m,n) | comparație modulo 4 }

g= { (m,n) | m£ n)

18) r= { (m,n) | m divizibil cu n)

g= { (m,n) | m¹ n, m- chiar }

19) r= { (m,n) | comparație modulo 3 }

g= { (m,n) | £1 (m-n) 3 lire sterline }

20) r= { (m,n) | (m - n) divizibil cu 4 }

g= { (m,n) | m¹ n)

21) r= { (m,n) | m- ciudat, n- ciudat }

g= { (m,n) | m£ n, n- chiar }

22) r= { (m,n) | mŞi n au un rest impar când se împarte la 3 }

g= { (m,n) | (m-n)³1 }

23) r= { (m,n) | m * n - ciudat }

g= { (m,n) | comparație modulo 2 }

24) r= { (m,n) | m * n - chiar }

g= { (m,n) | £1 (m-n) 3 lire sterline }

25) r= { (m,n) | (m+ n) - chiar }

g= { (m,n) | m nu este complet divizibil n)

26) r= { (m,n) | m = n)

g= { (m,n) | m divizibil cu n)

27) r= { (m,n) | (m-n)- chiar }

g= { (m,n) | m separator n)

28) r= { (m,n) | (m-n)³2 }

g= { (m,n) | m divizibil cu n)

29) r= { (m,n) | m 2³ n)

g= { (m,n) | m / n- ciudat }

30) r= { (m,n) | m³ n, m - chiar }

g= { (m,n) | mŞi n au un divizor comun altul decât 1 }

3. Stabiliți dacă relația dată este f- functional, definit peste tot, injectiv, surjectiv, bijectiv ( R- mulţime de numere reale). Construiți un grafic de relații, determinați domeniul definiției și domeniul valorilor.

Faceți aceeași sarcină pentru relații rŞi g de la punctul 3 al lucrărilor de laborator.

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, y> 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 }.

Întrebări de securitate

2. Definiția unei relații binare.

3. Metode de descriere a relaţiilor binare.

4.Domeniul definiției și intervalul de valori.

5.Proprietățile relațiilor binare.

6.Relații de echivalență și clase de echivalență.

7. Relații de ordine: stricte și nestrictive, complete și parțiale.

8. Clase de reziduuri modulo m.

9.Relații funcționale.

10. Injectare, surjecție, bijecție.

Lucrare de laborator nr 3

Relaţie. Concepte de bază și definiții

Definiție 2.1.Pereche comandată<x, y> numită o colecție de două elemente xŞi y, dispuse într-o anumită ordine.

Două perechi ordonate<x, y> și<u, v> sunt egale între ele dacă și numai dacă x = uŞi y= v.

Exemplul 2.1.

<o, b>, <1, 2>, <x, 4> – perechi ordonate.

În mod similar, putem considera tripleți, cvadruplii, n-elementele ki<x 1 , x 2 ,… x n>.

Definiție 2.2.Direct(sau carteziană)lucru două seturi OŞi B este o mulțime de perechi ordonate astfel încât primul element al fiecărei perechi să aparțină mulțimii O, iar al doilea – la set B:

O ´ B = {<o, b>, ç oÎ OŞi bÏ ÎN}.

În general, produsul direct n seturi O 1 ,O 2 ,…A n numit set O 1' O 2 '...' A n, constând din seturi ordonate de elemente<o 1 , o 2 , …,un n> lungime n, astfel încât eu- th un i aparține setului A i,un i Î A i.

Exemplul 2.2.

Lasă O = {1, 2}, ÎN = {2, 3}.

Apoi O ´ B = {<1, 2>, <1, 3>,<2, 2>,<2, 3>}.

Exemplul 2.3.

Lasă O= {x ç0 £ x£ 1) și B= {yç2 £ y 3 GBP)

Apoi O ´ B = {<x, y >, ç0 £ x£1&2£ y 3 lire sterline).

Astfel, multe O ´ B constă din puncte situate în interiorul și pe marginea unui dreptunghi format din linii drepte x= 0 (axa y), x= 1,y= 2i y = 3.

Matematicianul și filozoful francez Descartes a fost primul care a propus o reprezentare coordonată a punctelor de pe un plan. Acesta este din punct de vedere istoric primul exemplu de produs direct.

Definiție 2.3.Binar(sau dubla)raportul r se numeste multimea perechilor ordonate.

Dacă un cuplu<x, y> aparține r, atunci se scrie astfel:<x, y> Î r sau, ce este la fel, xr y.

Exemplul2.4.

r = {<1, 1>, <1, 2>, <2, 3>}

La fel putem defini n-relaţia locală ca ansamblu de ordonate n-BINE.

Deoarece o relație binară este o mulțime, metodele pentru specificarea unei relații binare sunt aceleași cu metodele pentru specificarea unei mulțimi (vezi Secțiunea 1.1). O relație binară poate fi specificată prin enumerarea perechilor ordonate sau prin specificarea unei proprietăți generale a perechilor ordonate.

Exemplul 2.5.

1. r = {<1, 2>, <2, 1>, <2, 3>) – relația se precizează prin enumerarea perechilor ordonate;

2. r = {<x, y> ç x+ y = 7, x, y– numere reale) – relația se precizează prin specificarea proprietății x+ y = 7.

În plus, poate fi dată o relație binară matrice de relații binare. Lasă O = {o 1 , o 2 , …, un n) este o mulțime finită. Matricea relațiilor binare C este o matrice pătrată de ordine n, ale căror elemente c ij sunt definite după cum urmează:

Exemplul 2.6.

O= (1, 2, 3, 4). Să definim o relație binară rîn cele trei moduri enumerate.

1. r = {<1, 2>, <1, 3>, <1, 4>, <2, 3>, <2, 4>, <3, 4>) – relația este specificată prin enumerarea tuturor perechilor ordonate.

2. r = {<un i, un j> ç un i < un j; un i, un jÎ O) – relația se precizează prin indicarea proprietății „mai puțin decât” pe set O.

3. – relația este specificată de matricea relațiilor binare C.

Exemplul 2.7.

Să ne uităm la câteva relații binare.

1. Relații pe mulțimea numerelor naturale.

a) relația £ este valabilă pentru perechi<1, 2>, <5, 5>, dar nu este valabil pentru pereche<4, 3>;

b) relația „au un divizor comun altul decât unul” este valabilă pentru perechi<3, 6>, <7, 42>, <21, 15>, dar nu este valabil pentru pereche<3, 28>.

2. Relaţii pe mulţimea punctelor planului real.

a) relația „a fi la aceeași distanță de punctul (0, 0)” este îndeplinită pentru punctele (3, 4) și (–2, Ö21), dar nu este satisfăcută pentru punctele (1, 2) și ( 5, 3);

b) relaţia „să fie simetrică faţă de axă OY" se execută pentru toate punctele ( x, y) Și (- x, –y).

3. Relații cu mulți oameni.

a) atitudinea de a „locui în același oraș”;

b) atitudinea de „a studia în aceeași grupă”;

c) atitudinea de „a fi mai în vârstă”.

Definiție 2.4. Domeniul de definire al unei relații binare r este mulțimea D r = (x çexistă y astfel încât xr y).

Definiția 2.5. Intervalul de valori al unei relații binare r este mulțimea R r = (y çexistă x astfel încât xr y).

Definiția 2.6. Domeniul de specificare a unei relații binare r se numește mulțime M r = D r ÈR r .

Folosind conceptul de produs direct, putem scrie:

rÎ D r´ R r

Dacă D r= R r = O, atunci spunem că relația binară r definite pe platou O.

Exemplul 2.8.

Lasă r = {<1, 3>, <3, 3>, <4, 2>}.

Apoi D r ={1, 3, 4}, R r = {3, 2}, Dl= {1, 2, 3, 4}.

Operații asupra relațiilor

Deoarece relațiile sunt mulțimi, toate operațiile asupra mulțimilor sunt valabile pentru relații.

Exemplul 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>}.

Exemplul 2.10.

Lasă R– multime de numere reale. Să luăm în considerare următoarele relații pe acest set:

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 = ;

Să definim încă două operații asupra relațiilor.

Definiția 2.7. Relația se numește verso la atitudine r(notat r – 1), dacă

r – 1 = {<x, y> ç< y, x> Î r}.

Exemplul 2.11.

r = {<1, 2>, <2, 3>, <3, 4>}.

r – 1 = {<2, 1>, <3, 2>, <4, 3>}.

Exemplul 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}.

Definiția 2.8.Compoziția a două relații r și s numită relație

s r= {<x, z> çexistă așa ceva y, Ce<x, y> Î rŞi< y,z> Î s}.

Exemplul 2.13.

r = {<x, y> ç y = sinx}.

s= {<x, y> ç y = Ö x}.

s r= {<x, z> çexistă așa ceva y, Ce<x, y> Î rŞi< y,z> Î s} = {<x, z> çexistă așa ceva y, Ce y = sinxŞi z= Ö y} = {<x, z> ç z= Ö sinx}.

Definiția compoziției a două relații corespunde definiției unei funcții complexe:

y = f(x), z= g(y) Þ z= g(f(x)).

Exemplul 2.14.

r = {<1, 1>, <1, 2>, <1, 3>, <3, 1>}.

s = {<1, 2>, <1, 3>, <2, 2>, <3, 2>, <3, 3>}.

Proces de găsire s rîn conformitate cu definiția compoziției, este convenabil să o reprezentați într-un tabel în care sunt enumerate toate valorile posibile x, y, z. pentru fiecare pereche<x, y> Î r trebuie să luăm în considerare toate perechile posibile< y,z> Î s(Tabelul 2.1).

Tabelul 2.1

<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>

Rețineți că primul, al treilea și al patrulea rând, precum și al doilea și al cincilea rând din ultima coloană a tabelului conțin perechi identice. Prin urmare obținem:

s r= {<1, 2>, <1, 3>, <3, 2>, <3, 3>}.

Proprietățile relațiilor

Definiția 2.9. Atitudine r numit reflectorizant pe un platou X, dacă pentru vreunul xÎ X funcţionare xr x.

Din definiție rezultă că fiecare element<x,x > Î r.

Exemplul 2.15.

a) Fie X- multime finita, X= (1, 2, 3) și r = {<1, 1>, <1, 2>, <2, 2>, <3, 1>, <3, 3>). Atitudine r reflexiv. Dacă X este o mulțime finită, atunci diagonala principală a matricei relațiilor reflexive conține doar unele. Pentru exemplul nostru

b) Fie X r raport de egalitate. Această atitudine este reflexivă, pentru că fiecare număr este egal cu el însuși.

c) Fie X- multă lume și r atitudinea „locuiește în același oraș”. Această atitudine este reflexivă, pentru că toți locuiesc în același oraș cu ei înșiși.

Definiția 2.10. Atitudine r numit simetric pe un platou X, dacă pentru vreunul x, yÎ X din xry ar trebui an x.

Este evident că r simetric dacă şi numai dacă r = r – 1 .

Exemplul 2.16.

a) Fie X- multime finita, X= (1, 2, 3) și r = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <3, 1>, <3, 3>). Atitudine r simetric. Dacă X este o mulțime finită, atunci matricea relației simetrice este simetrică față de diagonala principală. Pentru exemplul nostru

b) Fie X– mulţime de numere reale şi r raport de egalitate. Această relație este simetrică, deoarece Dacă x egală y, atunci y egală x.

c) Fie X– mulți studenți și r atitudinea „studiați în același grup”. Această relație este simetrică, deoarece Dacă x studii în aceeași grupă cu y, atunci y studii în aceeași grupă cu x.

Definiția 2.11. Atitudine r numit tranzitiv pe un platou X, dacă pentru vreunul x, y,zÎ X din xryŞi an z ar trebui xr z.

Îndeplinirea simultană a condițiilor xry, an z, xr zînseamnă că perechea<x,z> aparține compoziției r r. Prin urmare pentru tranzitivitate r este necesar si suficient pentru ansamblu r r a fost un subset r, adică r rÍ r.

Exemplul 2.17.

a) Fie X- multime finita, X= (1, 2, 3) și r = {<1, 1>, <1, 2>, <2, 3>, <1, 3>). Atitudine r tranzitiv, deoarece împreună cu perechi<x,y>si<y,z> am un cuplu<x,z>. De exemplu, împreună cu perechi<1, 2>, Și<2, 3>există o pereche<1, 3>.

b) Fie X– mulţime de numere reale şi r raport £ (mai mic sau egal cu). Această relaţie este tranzitivă, deoarece Dacă x£ yŞi y£ z, Asta x£ z.

c) Fie X- multă lume și r atitudine de „a fi mai în vârstă”. Această relaţie este tranzitivă, deoarece Dacă x mai în vârstă yŞi y mai în vârstă z, Asta x mai în vârstă z.

Definiția 2.12. Atitudine r numit relație de echivalență pe un platou X, dacă este reflexiv, simetric și tranzitiv pe platou X.

Exemplul 2.18.

a) Fie X- multime finita, X= (1, 2, 3) și r = {<1, 1>, <2, 2>, <3, 3>). Atitudine r este o relație de echivalență.

b) Fie X– mulţime de numere reale şi r raport de egalitate. Aceasta este o relație de echivalență.

c) Fie X– mulți studenți și r atitudinea „studiați în același grup”. Aceasta este o relație de echivalență.

Lasă r X.

Definiția 2.13. Lasă r– relația de echivalență pe mulțime XŞi xÎ X. Clasa de echivalare, generat de element x, se numește submulțime a mulțimii X, constând din acele elemente yÎ X, pentru care xry. Clasa de echivalență generată de element x, notat cu [ x].

Astfel, [ x] = {yÎ X|xry}.

Se formează clasele de echivalență compartimentare seturi X, adică un sistem de submulțimi disjunse în perechi non-vide ale acestuia, a căror unire coincide cu întreaga mulțime X.

Exemplul 2.19.

a) Relația de egalitate pe mulțimea numerelor întregi generează următoarele clase de echivalență: pentru orice element x din acest set [ x] = {x), adică fiecare clasă de echivalență este formată dintr-un element.

b) Clasa de echivalență generată de pereche<x, y> este determinat de relația:

[<x, y>] = .

Fiecare clasă de echivalență generată de o pereche<x, y>, definește un număr rațional.

c) Pentru relația de apartenență la o grupă de elevi, clasa de echivalență este mulțimea elevilor din aceeași grupă.

Definiția 2.14. Atitudine r numit antisimetric pe un platou X, dacă pentru vreunul x, yÎ X din xryŞi an x ar trebui x = y.

Din definiția antisimetriei rezultă că ori de câte ori o pereche<x,y>deținute în același timp rŞi r – 1, egalitatea trebuie să fie satisfăcută x = y. Cu alte cuvinte, r Ç r – 1 este format numai din perechi de formă<x,x >.

Exemplul 2.20.

a) Fie X- multime finita, X= (1, 2, 3) și r = {<1, 1>, <1, 2>, <1, 3>, <2, 2>, <2, 3>, <3, 3>). Atitudine r antisimetric.

Atitudine s= {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 3>, <3, 3>) este neantisimetric. De exemplu,<1, 2> Î s,Şi<2, 1> Î s, dar 1¹2.

b) Fie X– mulţime de numere reale şi r raport £ (mai mic sau egal cu). Această relație este antisimetrică, deoarece Dacă x £ y, Și y £ x, Asta x = y.

Definiția 2.15. Atitudine r numit relație de ordine parțială(sau doar o comandă parțială) pe platou X, dacă este reflexiv, antisimetric și tranzitiv pe platou X. Multe Xîn acest caz se numește parțial ordonat și relația specificată este adesea notată prin simbolul £, dacă aceasta nu duce la neînțelegeri.

Inversa relației de ordin parțial va fi evident o relație de ordin parțial.

Exemplul 2.21.

a) Fie X- multime finita, X= (1, 2, 3) și r = {<1, 1>, <1, 2>, <1, 3>, <2, 2>, <2, 3>, <3, 3>). Atitudine r

b) Atitudine OÍ ÎN pe multimea submultimii unei multimi U există o relație de ordine parțială.

c) Relația de divizibilitate pe mulțimea numerelor naturale este o relație de ordin parțial.

Funcții. Concepte de bază și definiții

În analiza matematică, se acceptă următoarea definiție a unei funcții.

Variabilă y numită funcție a unei variabile x, dacă după o regulă sau o lege fiecare valoare x corespunde unei anumite valori y = f(x). Zona de schimbare variabilă x se numește domeniul de definire al unei funcții și domeniul modificării unei variabile y– gama de valori ale funcției. Dacă o valoare x corespunde mai multor (și chiar infinit de valori) y), atunci funcția se numește multivalorică. Totuși, în cadrul cursului de analiză a funcțiilor variabilelor reale se evită funcțiile cu mai multe valori și se iau în considerare funcțiile cu o singură valoare.

Să luăm în considerare o altă definiție a funcției în termeni de relații.

Definiția 2.16. Funcţie este orice relație binară care nu conține două perechi cu primele componente egale și altele secunde diferite.

Această proprietate a unei relații se numește neambiguitate sau funcţionalitate.

Exemplul 2.22.

A) (<1, 2>, <3, 4>, <4, 4>, <5, 6>) – funcție.

b) (<x, y>: x, y Î R, y = x 2) – funcție.

V) (<1, 2>, <1, 4>, <4, 4>, <5, 6>) este o relație, dar nu o funcție.

Definiția 2.17. Dacă f– funcția, atunci D f – domeniul definirii, A Rf – gamă funcții f.

Exemplul 2.23.

De exemplu 2.22 a) D f – {1, 3, 4, 5}; Rf – {2, 4, 6}.

De exemplu 2.22 b) D f = Rf = (–¥, ¥).

Fiecare element x D f potriviri de funcții singurul element y Rf. Acest lucru este notat prin notația binecunoscută y = f(x). Element x numit un argument al funcției sau un element preimagine y cu functie f, și elementul y valoarea functiei f pe x sau imaginea elementului x la f.

Deci, din toate relațiile, funcțiile se remarcă prin faptul că fiecare element din domeniul definiției are singurul imagine.

Definiția 2.18. Dacă D f = XŞi Rf = Y, apoi se spune că funcția f determinat pe Xși își ia valorile la Y, A f numit maparea multimii X la Y(X ® Y).

Definiția 2.19. Funcții fŞi g sunt egale dacă domeniul lor este același set D, și pentru oricine x Î D egalitatea este adevărată f(x) = g(x).

Această definiție nu contrazice definiția egalității funcțiilor ca egalitate a mulțimilor (la urma urmei, am definit o funcție ca o relație, adică o mulțime): mulțimi fŞi g sunt egale dacă și numai dacă sunt formate din aceleași elemente.

Definiția 2.20. Funcție (afișaj) f numit surjectiv sau doar surjecție, dacă pentru orice element y Y există un element x Î X, astfel încât y = f(x).

Deci fiecare funcție f este o mapare surjectivă (surjecție) D f® Rf.

Dacă f este o surjecție și XŞi Y sunt mulțimi finite, atunci ³ .

Definiția 2.21. Funcție (afișaj) f numit injectiv sau doar injectare sau unu-la-unu, dacă de la f(o) = f(b) ar trebui o = b.

Definiția 2.22. Funcție (afișaj) f numit bijectiv sau doar bijectie, dacă este atât injectiv cât și surjectiv.

Dacă f este o bijecție și XŞi Y sunt mulțimi finite, atunci = .

Definiția 2.23. Dacă intervalul funcției D f constă dintr-un element, atunci f numit functie constanta.

Exemplul 2.24.

O) f(x) = x 2 este o mapare de la mulțimea de numere reale la mulțimea de numere reale nenegative. Deoarece f(–o) = f(o), Și o ¹ – o, atunci această funcție nu este o injecție.

b) Pentru toată lumea x R= (– , ) funcţie f(x) = 5 – funcție constantă. Afișează multe R a seta (5). Această funcție este surjectivă, dar nu injectivă.

V) f(x) = 2x+ 1 este o injecție și o bijecție, deoarece din 2 x 1 +1 = 2x Urmează 2 +1 x 1 = x 2 .

Definiția 2.24. Funcție care implementează afișajul X 1' X 2 '...' Xn ® Y numit n-local funcţie.

Exemplul 2.25.

a) Adunarea, scăderea, înmulțirea și împărțirea sunt funcții cu două locuri dintr-o mulțime R numere reale, adică funcții ca R 2® R.

b) f(x, y) = este o funcție cu două locuri care implementează maparea R ´ ( R \ )® R. Această funcție nu este o injecție, deoarece f(1, 2) = f(2, 4).

c) Tabelul de câștiguri la loterie specifică o funcție cu două locuri care stabilește o corespondență între perechile de N 2 (N– un set de numere naturale) și un set de câștiguri.

Deoarece funcțiile sunt relații binare, este posibil să găsiți funcții inverse și să aplicați operația de compunere. Compoziția oricăror două funcții este o funcție, dar nu pentru fiecare funcție f atitudine f–1 este o funcție.

Exemplul 2.26.

O) f = {<1, 2>, <2, 3>, <3, 4>, <4, 2>) – funcție.

Atitudine f –1 = {<2, 1>, <3, 2>, <4, 3>, <2, 4>) nu este o funcție.

b) g = {<1, o>, <2, b>, <3, c>, <4, D>) este o funcție.

g -1 = {<o, 1>, <b, 2>, <c, 3>, <D, 4>) este, de asemenea, o funcție.

c) Aflați compoziția funcțiilor f din exemplul a) și g-1 din exemplul b). Avem g -1f = {<o, 2>, <b, 3>, <c, 4>, <d, 2>}.

fg-1 = Æ.

Rețineți că ( g -1f)(o) = f(g -1 (o)) = f(1) = 2; (g -1f)(c) = f(g -1 (c)) = f(3) = 4.

O funcție elementară în analiza matematică este orice funcție f, care este o compoziție a unui număr finit de funcții aritmetice, precum și următoarele funcții:

1) Funcții fracționale-raționale, i.e. funcţiile formei

o 0 + o 1 x + ... + un n x n

b 0 + b 1 x + ... + b m x m.

2) Funcția de putere f(x) = x m, Unde m– orice număr real constant.

3) Funcția exponențială f(x) = e x.

4) funcția logaritmică f(x) = log un x, o >0, o 1.

5) Funcții trigonometrice sin, cos, tg, ctg, sec, csc.

6) Funcții hiperbolice sh, ch, th, cth.

7) Funcții trigonometrice inverse arcsin, arccos etc.

De exemplu, funcția jurnal 2 (x 3 +sincos 3x) este elementară, deoarece este o alcătuire de funcții cosx, sinx, x 3 , x 1 + x 2 , logx, x 2 .

O expresie care descrie compoziția funcțiilor se numește formulă.

Pentru o funcție multiloc, este valabil următorul rezultat important, obținut de A. N. Kolmogorov și V. I. Arnold în 1957 și care este o soluție la cea de-a 13-a problemă a lui Hilbert:

Teorema. Orice funcție continuă n variabilele pot fi reprezentate ca o compoziție de funcții continue a două variabile.

Metode de specificare a funcțiilor

1. Cel mai simplu mod de a specifica funcții este prin intermediul tabelelor (Tabelul 2.2):

Tabelul 2.2

Cu toate acestea, funcțiile definite pe mulțimi finite pot fi definite în acest fel.

Dacă o funcție definită pe o mulțime infinită (segment, interval) este dată la un număr finit de puncte, de exemplu, sub formă de tabele trigonometrice, tabele de funcții speciale etc., atunci regulile de interpolare sunt utilizate pentru a calcula valorile. de funcții în puncte intermediare.

2. O funcție poate fi specificată ca o formulă care descrie funcția ca o compoziție a altor funcții. Formula specifică succesiunea de calcul al funcției.

Exemplul 2.28.

f(x) = păcat(x + Ö x) este o alcătuire a următoarelor funcții:

g(y) = Ö y; h(tu, v) = u+ v; w(z) = sinz.

3. Funcția poate fi specificată ca procedură recursivă. Procedura recursivă specifică o funcție definită pe mulțimea numerelor naturale, i.e. f(n), n= 1, 2,... astfel: a) setați valoarea f(1) (sau f(0)); b) valoare f(n+ 1) determinat prin compoziție f(n) și alte funcții cunoscute. Cel mai simplu exemplu de procedură recursivă este calculul n!: a) 0! = 1; b) ( n + 1)! = n!(n+ 1). Multe proceduri numerice sunt proceduri recursive.

4. Există modalități posibile de a specifica o funcție care nu conțin o metodă de calcul a funcției, ci doar o descrie. De exemplu:

f M(x) =

Funcţie f M(x) – functie caracteristica multimii M.

Deci, conform definiției noastre, definiți o funcție f– înseamnă a seta afișajul X ® Y, adică defini un set X´ Y, deci întrebarea se rezumă la specificarea unui anumit set. Totuși, este posibil să se definească conceptul de funcție fără a folosi limbajul teoriei mulțimilor și anume: o funcție este considerată dată dacă este dată o procedură de calcul care, dată fiind valoarea argumentului, găsește valoarea corespunzătoare a funcției. O funcție definită în acest fel este numită calculabil.

Exemplul 2.29.

Procedura de determinare numerele Fibonacci, este dat de relația

Fn= Fn- 1 + Fn- 2 (n³ 2) (2,1)

cu valorile initiale F 0 = 1, F 1 = 1.

Formula (2.1) împreună cu valorile inițiale determină următoarea serie de numere Fibonacci:

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 …

Procedura de calcul pentru determinarea valorii unei funcții dintr-o anumită valoare a argumentului nu este altceva decât algoritm.

Întrebări de testare pentru subiectul 2

1. Indicați modalități de definire a unei relații binare.

2. Diagonala principală a matricei a cărei relații conține doar unele?

3. Pentru ce relatie? r condiția este întotdeauna îndeplinită r = r – 1 ?

4. Pentru ce atitudine r condiția este întotdeauna îndeplinită r rÍ r.

5. Introduceți relații de echivalență și ordine parțială pe mulțimea tuturor dreptelor din plan.

6. Specificați modalități de specificare a funcțiilor.

7. Care dintre următoarele afirmații este adevărată?

a) Fiecare relație binară este o funcție.

b) Fiecare funcție este o relație binară.

Tema 3. GRAFICE

Prima lucrare a lui Euler despre teoria grafurilor a apărut în 1736. La început, această teorie a fost asociată cu puzzle-uri și jocuri matematice. Cu toate acestea, ulterior teoria grafurilor a început să fie folosită în topologie, algebră și teoria numerelor. În zilele noastre, teoria grafurilor este utilizată într-o mare varietate de domenii ale științei, tehnologiei și activității practice. Este utilizat în proiectarea rețelelor electrice, planificarea transportului și construcția de circuite moleculare. Teoria grafurilor este folosită și în economie, psihologie, sociologie și biologie.