Relații binare

Definiția. O relație binară R este o submulțime de perechi (a, b) ∈ R a produsului cartesian A × B, adică, R⊆A × B. În acest caz, mulțimea A este numită domeniu de definire a relației R, setul B este intervalul de valori.







Denumire: aRb (adică a și b sunt în raport cu R). /

Notă. dacă A = B. atunci spunem că R este o relație pe setul A.

Metode pentru specificarea relațiilor binare

1. O listă (enumerarea de perechi) pentru care această relație este îndeplinită.

2. Matricea. O relație binară R ∈ A × A. unde A = (a1, a2.An) corespunde unei matrice pătrate de ordine n. în care elementul cij. care este la intersecția rândului i și a coloanei j, este 1 dacă există o relație R între ai și aj sau 0 dacă este absent:

Fie R o relație pe setul A, R ∈ A × A. Apoi raportul R:

este reflexivă dacă Ɐ a ∈ A: a R a (principala diagonală a matricei relației reflexive conține numai una);

este antireflexiv dacă Ɐ a ∈ A: a R a (diagonala principală a matricei reflexive conține numai zerouri);

simetric dacă Ɐ a. b ∈ A: a R b ⇒ b R a (matricea acestui raport este simetrică față de diagonala principală, adică, cij cji);

este antisimetric dacă Ɐ a, b ∈ A: a R b b R a ⇒ a = b (nu există unități în matricea unui astfel de raport care să fie simetric în raport cu diagonala principală);

este tranzitorie dacă Ɐ a, b, c ∈ A: a R b b R c ⇒ o Rc (în această relație matrice trebuie satisfăcută: .. dacă rândul i-lea este o unitate, de exemplu în coordonate liniile j-lea (coloana), adică cij = 1. atunci toate unitățile din j- (aceste unități să corespundă cu k e coordonate astfel încât, cjk = 1) trebuie să corespundă celor din rândul i din aceleași coordonate k, adică cik = 1 (și, poate, și în alte coordonate).

Problema 3.1. Definiți proprietățile relației R - "a fi un divizor", dat pe setul de numere naturale.

reflexiv, nu antireflexiv, deoarece orice număr se împarte fără un rest: a / a = 1 pentru toate a∈N;

nu simetric, antisimetric, de exemplu, 2 divizor 4, dar 4 nu este un divizor 2;

transitiv, deoarece b / a ∈ N și c / b ∈ N, c / a = b / a ⋅ c / b ∈ N, de exemplu, dacă 6/3 = 2∈N și 18/6 = 3∈N, 18/3 = 18 / 6⋅6 / 3 = 6∈N.

Problema 3.2. Definiți proprietățile relației R - "fii un frate", dat pe un set de persoane.
Soluția.

nu reflexiv, antireflexiv din cauza absenței evidente a aRa pentru toate a;

nu este simetrică, deoarece în cazul general aRb are loc între fratele a și sora b. dar nu bRa;

nu este antisimetric, deoarece dacă a și b sunt frați, atunci aRb și bRa, dar a ≠ b;







tranzitiv, dacă numesc frați ai unor persoane care au părinți obișnuiți (tată și mamă).

Sarcina 3.3. Definiti proprietatile relatiei R - "a fi seful", dat pe setul de elemente ale structurii

Relații binare

  • Nu este reflexiv, antireflexiv, dacă într-o interpretare concretă nu are sens;
  • nu este simetrică, antisimetrică, deoarece pentru toți a ≠ b aRb și bRa nu sunt îndeplinite simultan;
  • tranzit, deoarece dacă a este șeful B și b este șeful c. apoi un sef c.

Sarcini pentru soluții independente

Determinați proprietățile relației Ri. dată pe setul Mi printr-o matrice, dacă:

Operații privind relațiile binare

Să presupunem că R1. R1 este o relație definită pe setul A.

Definirea gradului de relație R pe setul A este compoziția sa cu ea însăși.

Definiția. Dacă R ⊂ A × B. atunci R º R -1 este numit kernelul relației R.

TEOREM 3.1. Fie R ⊂ A × A relatia definita pe setul A.

  1. R este reflexiv dacă și numai dacă (⇔) este folosit mai târziu atunci când I ⊂ R.
  2. R este simetric ⇔ R = R -1.
  3. R este tranzitiv ⇔ R º R ⊂ R
  4. R este antisimetrică ⇔ R ⌒ R -1 ⊂ I.
  5. R este antireflexivă ⇔ R ⌒ I = ∅.

Problema 3.4. Fie R relația dintre seturi și dată de enumerarea perechilor: R =. În plus, S este relația dintre seturile S =. Calculați R-1. S -1 și S º R. Verificați că (S º R) -1 = R -1. S -1.

Sarcina 3.5. Fie R raportul n. părinte. ", Iar S este raportul". frate. "Pe setul tuturor oamenilor. Faceți o scurtă descriere verbală a relației:

R-1. S -1. R º S, S -1 º R -1 și R º R.

R -1 este raportul ". copil. „;

S -1 este raportul dintre ". frate sau sora. „;

R º S este raportul ". părinte. „;

S -1 º R -1 este raportul dintre. copil. "

R º R este raportul dintre ". bunica sau bunicul. "

Sarcini pentru soluții independente

1) Fie R raportul n. tată. ", Iar S este raportul". sora. "Pe setul tuturor oamenilor. Oferiți o descriere verbală a relației:

R-1. S -1. R º S, S -1 º R -1. R º R.

2) Fie R raportul n. frate. ", Iar S este raportul". mama. "Pe setul tuturor oamenilor. Oferiți o descriere verbală a relației:

R-1. S -1. S º R, R -1 º S -1. S º S.

3) Fie R raportul n. bunicul. ", Iar S este raportul". fiule. "Pe setul tuturor oamenilor. Oferiți o descriere verbală a relației:

R-1. S -1. R º S, S -1 º R -1. S º S.

4) Fie R raportul n. fiică. ", Iar S este raportul". bunica. "Pe setul tuturor oamenilor. Oferiți o descriere verbală a relației:

R-1. S -1. S º R, R -1 º S -1. R º R.

5) Fie R raportul n. nepoata. ", Iar S este raportul". tată. "Pe setul tuturor oamenilor. Oferiți o descriere verbală a relației:

R-1. S -1. S º R, R -1 º S -1. R º R.

6) Fie R relația "sora". ", Și S este relația" mama. "Pe setul tuturor oamenilor. Oferiți o descriere verbală a relației:

R-1. S -1. R º S, S -1 º R -1. S º S.

7) Fie R raportul n. mama. ", Iar S este raportul". sora. "Pe setul tuturor oamenilor. Oferiți o descriere verbală a relației:

R-1. S1, R º S, S1 º R1, S º S.

8) Fie R raportul n. fiule. ", Iar S este raportul". bunicul. "Pe setul tuturor oamenilor. Oferiți o descriere verbală a relației:

R-1. S -1. S º R, R -1 º S -1. R º R.

9) Fie R raportul n. sora. ", Iar S este raportul". tată. "Pe setul tuturor oamenilor. Oferiți o descriere verbală a relației:

R-1. S -1. R º S, S -1 º R -1. S º S.

10) Fie R raportul n. mama. ", Iar S este raportul". frate. "Pe setul tuturor oamenilor. Oferiți o descriere verbală a relației:

R-1. S -1. S º R, R -1 º S -1. R º R.







Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: