Články

2.1: Binárne vzťahy - matematika


Definícia

Nech (S ) je neprázdna množina. Potom sa o ktorejkoľvek podmnožine (R ) z (S krát S ) hovorí, že je vzťahom cez (S ). Inými slovami, vzťah je pravidlo, ktoré je definované medzi dvoma prvkami v (S ). Intuitívne, ak (R ) je vzťah nad (S ), potom výrok (a R b ) je buď pravda alebo nepravdivé pre všetky (a, b v S ).

Príklad ( PageIndex {1} ):

Nech (S = {1,2,3 } ). Definujte (R ) pomocou (a R b ) práve vtedy, ak (a

Potom (1 R 2, 1 R 3, 2 R 3 ) a (2 nie R 1 ).

Vyššie uvedený binárny vzťah si môžeme predstaviť ako graf, kde vrcholy sú prvkami S a existuje hrana od (a ) do (b ) práve vtedy, ak (a R b ) , pre (a, b v S ).

Nasleduje niekoľko príkladov vzťahu definovaného na ( mathbb {Z} ).

Príklad ( PageIndex {2} ):

  1. Definujte (R ) pomocou (a R b ), ak a len vtedy (a
  2. Definujte (R ) pomocou (a R b ), ak a len vtedy (a> b ), pre (a, b v mathbb {Z} ).
  3. Definujte (R ) pomocou (a R b ) vtedy a len vtedy (a leq b ), pre (a, b v mathbb {Z} ).
  4. Definujte (R ) pomocou (a R b ) práve vtedy, ak (a geq b ), pre (a, b v mathbb {Z} ).
  5. Definujte (R ) pomocou (a R b ), ak a len vtedy (a = b ), pre (a, b v mathbb {Z} ).

Ďalej si predstavíme pojem „rozdeľuje“.

Definícia

Nech (a ) a (b ) sú celé čísla. Hovoríme, že (a ) rozdeľuje (b ) sa označuje (a stred b ), za predpokladu, že máme celé číslo (m ) také, že (b = am ). V tomto prípade môžeme povedať aj nasledovné:

  • (b ) je deliteľné (a )
  • (a ) je faktor (b )
  • (a ) je deliteľom (b )
  • (b ) je násobok (a )

Príklad ( PageIndex {3} ):

(4 stred 12 ) a (12 nie stred 4 )

Veta ( PageIndex {1} ): Veta o nerovnosti deliteľnosti

Ak (a mid b ), pre (a, b v mathbb {Z _ +} ) potom (a leq b ),

Dôkaz

Nech (a, b in mathbb {Z _ +} ) také, že (a mid b ), Pretože (a mid b ) existuje kladné celé číslo (m ) také, že ( b = som ). Pretože (m geq 1 ) a (a ) je kladné celé číslo, (b = am geq (a) (1) = a. )

Upozorňujeme, že ak (a mid b ), pre (a, b in mathbb {Z _ +} ) potom (a leq b ), ale konverzácia nie je pravdivá. Napríklad: (2 <3 ), ale (2 nie stred 3 ).

Príklad ( PageIndex {4} ):

Podľa našej definície (0 stred 0 ).

Definícia

Celé číslo je dokonca poskytované za predpokladu, že je deliteľné znakom (2 ).

Vlastnosti binárneho vzťahu:

Definícia

Nech (S ) je množina a (R ) je binárny vzťah na (S ). Potom sa hovorí, že (R ) je reflexívny, ak (a Ra, všetko pre v S. )

Príklad ( PageIndex {5} ): Vizuálne

( forall a in S, a R a ) platí.

Podľa nasledujúcej šablóny odpovieme na otázku o reflexívnom.

Príklad ( PageIndex {6} ):

Definujte (R ) pomocou (a R b ), ak a len vtedy (a

Príklad počítadla:

Vyberte (a = 2. )

Pretože (2 nie <2 ), (R ) nie je reflexné.

Príklad ( PageIndex {7} ):

Definujte (R ) pomocou (a R b ) vtedy a len vtedy, ak (a mid b ), pre (a, b in mathbb {Z} ). Je (R ) reflexívny?

Dôkaz:

Nech (a in mathbb {Z} ). Pretože (a = (1) (a) ), (a uprostred ).

(R ) je teda reflexívny. ( Box )

Definícia

Nech (S ) je množina a (R ) je binárny vzťah na (S ). Potom sa hovorí, že (R ) je symetrický, ak je pravdivé nasledujúce tvrdenie:

( forall a, b in S ), ak (a R b ), potom (b R a ), inými slovami, ( forall a, b v S, a R b znamená b Ra. )

Príklad ( PageIndex {8} ): Vizuálne

( všetky a, b v S, a R b znamená b R a. ) platí!

Podľa nasledujúcej šablóny odpovieme na otázku o symetrii.

Príklad ( PageIndex {7} ):

Definujte (R ) pomocou (a R b ), ak a len vtedy (a

Príklad počítadla:

(1 <2 ), ale (2 nie <1 ).

Príklad ( PageIndex {8} ):

Definujte (R ) pomocou (a R b ) vtedy a len vtedy, ak (a mid b ), pre (a, b in mathbb {Z} ). Je (R ) symetrický?

Príklad počítadla:

(2 stred 4 ), ale (4 nie stred 2 ).

Definícia

Nech (S ) je množina a (R ) je binárny vzťah na (S ). Potom sa o (R ) hovorí, že je antisymetrický, ak je pravdivé nasledujúce tvrdenie:

( všetky a, b v S ), ak (a R b ) a (b R a ), potom (a = b ).

Inými slovami, ( všetky a, b v S ), (a R b klin b R a znamená a = b. )

Príklad ( PageIndex {9} ): VIZUÁLNE

( všetky a, b v S ), (a R b klin b R a znamená a = b ) platí!

Podľa nasledujúcej šablóny odpovieme na otázku týkajúcu sa anti-symetrie.

Príklad ( PageIndex {10} ):

Definujte (R ) pomocou (a R b ), ak a len vtedy (a

Príklad ( PageIndex {11} ):

Definujte (R ) pomocou (a R b ) vtedy a len vtedy, ak (a mid b ), pre (a, b in mathbb {Z _ +} ). Je (R ) antisymetrický?

Definícia

Nech (S ) je množina a (R ) je binárny vzťah na (S ). Potom sa o (R ) hovorí, že je tranzitívne, ak je nasledujúci výrok pravdivý

( všetky a, b, c v S, ) ak (a R b ) a (b R c ), potom (a R c ).

Inými slovami, ( všetky, a, b, c v S ), (a R b klin b R c znamená a R c ).

Príklad ( PageIndex {12} ): VIZUÁLNE

( všetky a, b, c v S ), (a R b klin b R c znamená a R c ) platí!

Podľa nasledujúcej šablóny odpovieme na otázku o tranzitíve.

Príklad ( PageIndex {13} ):

Definujte (R ) pomocou (a R b ), ak a len vtedy (a

Príklad ( PageIndex {14} ):

Definujte (R ) pomocou (a R b ) práve vtedy, ak (a mid b ), pre (a, b in mathbb {Z _ +} ). Je (R ) tranzitívny?

Zhrnutie:

V tejto časti sme sa dozvedeli o binárnom vzťahu a nasledujúcich vlastnostiach:

Reflexné

Symetrický

Antisymetrický

Tranzitívne


Binárne vzťahy (typy a vlastnosti)

V tomto článku rozoberám binárne vzťahy. Najprv definujem zloženie dvoch vzťahov a potom dokážem niekoľko základných výsledkov. Potom definujem inverziu dvoch vzťahov. Potom je zahrnutý aj doplnok, obraz a predobraz binárnych vzťahov.

Nech je $ X $ množina a nech $ X krát X = <(a, b): a, b v X >. $ A (binárny) vzťah $ R $ je podmnožinou $ X krát X $. Ak $ (a, b) v R $, potom hovoríme, že $ a $ je súvisiace na $ b $ o $ R $. Je možné mať $ (a, b) v R $ aj $ (a, b ') v R $, kde $ b' neq b $, čo je akýkoľvek prvok v $ X $, môže súvisieť s akýmkoľvek číslom ďalších prvkov $ X $. Je tiež možné, že v $ X $ bude mať nejaký prvok, ktorý nesúvisí so žiadnym prvkom.

Definícia. Nech $ R $ a $ S $ sú vzťahy na $ X $. The zloženie z $ R $ a $ S $ je vzťah $ S circ R = <(a, c) v X krát X: existuje , b v X, (a, b) v R land (b, c) v S >. $

Tu je možné vizualizovať kompozície binárnych vzťahov.

Veta. Ak $ R $, $ S $ a $ T $ sú vzťahy na $ X $, potom $ R circ (S circ T) = (R circ S) circ T $.

Dôkaz. Dôkaz vyplýva z nasledujúcich tvrdení. začať (x, y) v & amp; R circ (S circ T) & amp Longleftrightarrow existuje z v X, (x, z) v S circ T land (z, y) v R & amp Longleftrightarrow existuje z v X, [ existuje w v X, (x, w) v T land (w, z) v S] land (z, y) v R & amp Longleftrightarrow existuje w, z v X, (x, w) v T land (w, z) v S land (z, y) v R & amp Longleftrightarrow existuje w v X, [ existuje z v X, (w, z) v S land (z, y) v R] land (x, w) v T & amp Longleftrightarrow existuje w v X, (x, w) in T land (w, y) in R circ S & amp Longleftrightarrow (x, y) in (R circ S) circ T end

Veta. Ak $ R $, $ S $ a $ T $ sú vzťahy na $ X $, potom $ R circ (S cup T) = (R circ S) cup (R circ T) $.

Dôkaz. Dôkaz vyplýva z nasledujúcich tvrdení. začať (x, y) & amp v R circ (S cup T) & amp Longleftrightarrow existuje z v X, (x, z) v S cup T land (z, y) v R & amp Longleftrightarrow existuje z v X, [(x, z) v S lor (x, z) v T] land (z, y) v R & amp Longleftrightarrow existuje z v X, [(x, z) v S land (z, y) v R] lor [(x, z) v T land (z, y) v R] & amp Longleftrightarrow (x, y) v R Circ S lor (x, y) v R Circ T & amp Longleftrightarrow (x, y) v (R Cir S) pohár (R Circ T ) koniec

Veta. Ak $ R $, $ S $ a $ T $ sú vzťahy na $ X $, potom $ (S cup T) circ R = (S circ R) cup (T circ R) $.

Dôkaz. Dôkaz vyplýva z nasledujúcich tvrdení. začať (x, y) & amp in (S cup T) circ R & amp Longleftrightarrow existuje z v X, (x, z) v R land (z, y) v S cup T & amp Longleftrightarrow existuje z v X, (x, z) v R land [(z, y) v S lor (z, y) v T] & amp Longleftrightarrow existuje z v X, [(x, z) v R land (z, y) v S] lor [(x, z) v R land (z, y) v T] & amp Longleftrightarrow (x, y) in (S circ R) lor (x, y) in (T circ R) & amp Longleftrightarrow (x, y) in (S circ R) cup ( T circ R) koniec

Veta. Ak $ R $, $ S $ a $ T $ sú vzťahy na $ X $, potom $ R circ (S cap T) subseteq (R circ S) cap (R circ T) $.

Dôkaz. Dôkaz vyplýva z nasledujúcich tvrdení. začať qquad quad & amp (x, y) v R circ (S cap T) & amp qquad Longleftrightarrow existuje z v X, (x, z) v S cap T land (z , y) v R & amp qquad Longleftrightarrow existuje z v X, [(x, z) v S land (x, z) v T] land (z, y) v R & amp qquad Longleftrightarrow existuje z v X, [(x, z) v S land (z, y) v R] land (x, z) v T & amp qquad Longleftrightarrow existuje z v X, [(x, z) v S land (z, y) v R] land [(x, z) v T land (z, y) v R] & amp qquad Longrightarrow [ existuje z v X, [(x, z) v S land (z, y) v R] land [ existuje w v X, (x, w) in T land (w, y) in R] & amp qquad Longleftrightarrow (x, y) in R circ S land (x, y) in R circ T & amp qquad Longleftrightarrow (x, y) in (R Circ S) Cap (R Circ T) end

Veta. Ak $ R $, $ S $ a $ T $ sú vzťahy na $ X $, potom $ R subseteq S znamená R circ T subseteq S circ T $.

Dôkaz. Dôkaz vyplýva z nasledujúcich tvrdení. začať & amp (x, y) v R circ T Longleftrightarrow existuje z v X, (x, z) v T land (z, y) v R & amp qquad Longrightarrow existuje z v X, (x, z) v T land (z, y) v S Longleftrightarrow (x, y) v S circ T end

Veta. Ak $ R $, $ S $ a $ T $ sú vzťahy na $ X $, potom $ R subseteq S znamená T circ R subseteq T circ S $.

Dôkaz. Dôkaz vyplýva z nasledujúcich tvrdení. začať & amp (x, y) v T circ R Longleftrightarrow existuje z v X, (x, z) v R land (z, y) v T & amp qquad Longrightarrow existuje z v X, (x, z) v S land (z, y) v T Longleftrightarrow (x, y) v T circ S end

Definícia. Nech $ R $ a $ S $ sú vzťahy na $ X $. The inverzný z $ R $ je vzťah $ R ^ <-1> = <(b, a) v X krát X: (a, b) v R >. $

Veta. Ak sú $ R $ a $ S $ vzťahy na $ X $, potom $ (R ^ <-1>) ^ <-1> = R $.

Dôkaz. $ (x, y) v (R ^ <-1>) ^ <-1> Longleftrightarrow (y, x) v R ^ <-1> Longleftrightarrow (x, y) v R $

Veta.Ak sú $ R $ a $ S $ vzťahy na $ X $, potom $ (R cup S) ^ <-1> = R ^ <-1> cup S ^ <-1> $.

Dôkaz. začať & amp (x, y) v (R cup S) ^ <-1> Longleftrightarrow (y, x) v R cup S Longleftrightarrow (y, x) v R lor (y, x) v S & amp qquad Longleftrightarrow (x, y) v R ^ <-1> lor (x, y) v S ^ <-1> Longleftrightarrow (x, y) v R ^ <- 1> pohár S ^ <-1> koniec

Veta. Ak $ R $ a $ S $ sú vzťahy na $ X $, potom $ (R cap S) ^ <-1> = R ^ <-1> cap S ^ <-1> $.

Dôkaz. začať & amp (x, y) v (R cap S) ^ <-1> Longleftrightarrow (y, x) v R cap S Longleftrightarrow (y, x) v R land (y, x) v S & amp qquad Longleftrightarrow (x, y) v R ^ <-1> land (x, y) v S ^ <-1> Longleftrightarrow (x, y) v R ^ <- 1> cap S ^ <-1> end

Veta. Ak $ R $ a $ S $ sú vzťahy na $ X $, potom $ (R circ S) ^ <-1> = S ^ <-1> circ R ^ <-1> $.

Dôkaz. začať & amp (x, y) in (R circ S) ^ <-1> Longleftrightarrow (y, x) v R circ S & amp qquad Longleftrightarrow existuje z v X, (y, z ) v S land (z, x) v R & amp qquad Longleftrightarrow existuje z v X, (z, y) v S ^ <-1> land (x, z) v R ^ <-1> & amp qquad Longleftrightarrow existuje z v X, (x, z) v R ^ <-1> land (z, y) v S ^ <-1> & amp qquad Longleftrightarrow (x, y) v S ^ <-1> circ R ^ <-1> end

Veta. Ak $ R $ a $ S $ sú vzťahy na $ X $, potom $ R subseteq S znamená R ^ <-1> subseteq S ^ <-1> $.

Dôkaz. Ak $ R subseteq S $, potom $ R ^ <-1> subseteq S ^ <-1> $. začať (x, y) v & amp R ^ <-1> Longleftrightarrow (y, x) v R Longrightarrow (y, x) v S Longleftrightarrow (x, y) v S ^ <-1> koniec

Veta. Ak sú $ R $ a $ S $ vzťahy na $ X $, potom $ (R ^ c) ^ <-1> = (R ^ <-1>) ^ c $.

Dôkaz. začať & amp (x, y) v (R ^ c) ^ <-1> Longleftrightarrow (y, x) v R ^ c Longleftrightarrow (y, x) v X krát X land (y, x) notin R & amp qquad Longleftrightarrow (x, y) v X krát X land (x, y) notin R ^ <-1> Longleftrightarrow (x, y) v (R ^ <- 1>) ^ c end

Veta. Ak $ R $ a $ S $ sú vzťahy na $ X $, potom $ (R setminus S) ^ <-1> = R ^ <-1> setminus S ^ <-1> $.

Dôkaz. začať & amp (x, y) v (R setminus S) ^ <-1> Longleftrightarrow (y, x) v R setminus S Longleftrightarrow (y, x) v R land (y, x) notin S & amp qquad Longleftrightarrow (x, y) v R ^ <-1> land (y, x) notin S Longleftrightarrow (x, y) v R ^ <-1> land ( x, y) notin S ^ <-1> & amp qquad Longleftrightarrow (x, y) v R ^ <-1> setminus S ^ <-1> end

Definícia. Nech $ R $ a $ S $ sú vzťahy na $ X $. The obrázok z $ A subseteq X $ pod $ R $ je množina $ R (A) = .$

Veta. Ak $ R $ a $ S $ sú vzťahy na $ X $ a $ A, B subseteq X $, potom $ A subseteq B znamená R (A) subseteq R (B) $.

Dôkaz. Ak $ A subseteq B $, potom $ R (A) subseteq R (B) $. začať qquad y v R (A) Longleftrightarrow existuje x v A, (x, y) v R znamená existuje x v B, (x, y) v R Longleftrightarrow y v R ( B) koniec

Veta. Ak $ R $ a $ S $ sú vzťahy na $ X $ a $ A, B subseteq X $, potom $ R (A cup B) = R (A) cup R (B) $.

Dôkaz. začať qquad & amp y v R (A cup B) Longleftrightarrow existuje x v X, x v A cup B land (x, y) v R & amp qquad Longleftrightarrow existuje x v X, (x v A lor x v B) land (x, y) v R & amp qquad Longleftrightarrow existuje x v A, (x, y) v R lor existuje x v B, (x, y) v R ľavá ľavá šípka y v R (A) pohár R (B) koniec

Veta. Ak $ R $ a $ S $ sú vzťahy na $ X $ a $ A, B subseteq X $, potom $ R (A cap B) subseteq R (A) cap R (B) $.

Dôkaz. začať qquad & amp y v R (A cap B) Longleftrightarrow existuje x v X, x v A cap B land (x, y) v R & amp qquad Longleftrightarrow existuje x v X, (x v A land x v B) land (x, y) v R & amp qquad Longrightarrow existuje x v A, (x, y) v R land existuje x v B, (x, y) v R Longleftrightarrow y v R (A) cap R (B) end

Veta. Ak $ R $ a $ S $ sú vzťahy na $ X $ a $ A, B subseteq X $, potom $ R (A) setminus R (B) subseteq R (A setminus B) $.

Dôkaz. začať y v R (A) setminus R (B) & amp Longleftrightarrow y v R (A) land y not v R (B) & amp Longleftrightarrow existuje x v A, (x, y ) v R krajina na všetky z v B, (z, y) nie v R & amp Longleftrightarrow existuje x v A setminus B, (x, y) v R Longleftrightarrow y v R (A setminus B) koniec

Veta. Ak $ R $ a $ S $ sú vzťahy na $ X $ a $ R (x) = S (x) $ pre všetky $ x v X $, potom $ R = S $.

Dôkaz. Predpokladajme $ R (x) = S (x) $ pre všetky $ x v X $, potom $ (x, y) v R Longleftrightarrow y v R (x) Longleftrightarrow y v S (x) Longleftrightarrow (x, y) v S $ dokončuje dôkaz.

Definícia. Nech $ R $ a $ S $ sú vzťahy na $ X $. The predobraz z $ B subseteq X $ pod $ R $ je množina $ R ^ <-1> (B) = .$

Veta. Nech je $ R $ vzťahom na $ X $ s $ A, B subseteq X $. Potom $ A subseteq B znamená R ^ <-1> (A) subseteq R ^ <1-> (B) $.

Dôkaz. začať x v R ^ <-1> (A) & amp Longleftrightarrow existuje y v A, (x, y) v R & amp implikuje existuje y v B, (x, y) v R Longleftrightarrow x v R ^ <-1> (B) end

Veta. Nech je $ R $ vzťahom na $ X $ s $ A, B subseteq X $. Potom $ R ^ <-1> (A pohár B) = R ^ <-1> (A) pohár R ^ <-1> (B) $.

Dôkaz. začať & amp x v R ^ <-1> (A pohár B) Longleftrightarrow existuje y v A pohár B, (x, y) v R & amp qquad Longleftrightarrow existuje y v A, (x, y) v R lor existuje y v B, (x, y) v R & amp qquad Longleftrightarrow x v R ^ <-1> (A) lor R ^ <- 1> (B) Longleftrightarrow x in R ^ <-1> (A) cup R ^ <-1> (B) end

Veta. Nech je $ R $ vzťahom na $ X $ s $ A, B subseteq X $. Potom $ R ^ <-1> (A cap B) subseteq R ^ <-1> (A) cap R ^ <-1> (B) $.

Dôkaz. začať & amp x v R ^ <-1> (A cap B) Longleftrightarrow existuje y v A cap B, (x, y) v R & amp qquad Longleftrightarrow existuje y v X, y v A land y v B land (x, y) v R & amp qquad Longrightarrow x v R ^ <-1> (A) land x v R ^ <-1> (B) Longleftrightarrow x in R ^ <-1> (A) cap x in R ^ <-1> (B) end

Veta. Nech je $ R $ vzťahom na $ X $ s $ A, B subseteq X $. Potom $ R ^ <-1> (A) setminus R ^ <-1> (B) subseteq R ^ <-1> (A setminus B) $.

Dôkaz. začať & amp x in R ^ <-1> (A) setminus R ^ <-1> (B) Longleftrightarrow x v R ^ <-1> (A) land neg (x v R ^ <- 1> (B)) & amp qquad Longleftrightarrow x v R ^ <-1> (A) land [ forall y v B, (x, y) not v R] & amp qquad Longleftrightarrow existuje y v A, (x, y) v R land [ forall y v B, (x, y) not v R] & amp qquad Longrightarrow existuje y v A setminus B, (x, y) v R Longleftrightarrow x v R ^ <-1> (A setminus B) end

Veta. Nech $ R $ a $ R_i $ sú vzťahy na $ X $ pre $ i v I $, kde $ I $ je indexovaná množina. Potom $ R circ doľava ( bigcup_ R_i right) = bigcup_(R circ R_i) $.

Dôkaz. začať (x, y) v R cirku vľavo ( bigcup_ R_i vpravo) & amp Longleftrightarrow existuje z v X, (x, z) v bigcup_ R_i land (z, y) v R & amp Longleftrightarrow existuje z v X, existuje i v I, (x, z) v R_i land (z, y) v R & amp Longleftrightarrow existuje i v I, (x, y) v R circ R_i & amp Longleftrightarrow (x, y) v bigcup_(R circ R_i) koniec

Veta. Nech $ R $ a $ R_i $ sú vzťahy na $ X $ pre $ i v I $, kde $ I $ je indexovaná množina. Potom $ doľava ( bigcup_ R_i vpravo) circ R = bigcup_(R_i circ R) $.

Dôkaz. začať (x, y) v vľavo ( bigcup_ R_i right) circ R & amp Longleftrightarrow existuje z v X, (x, z) v R land (z, y) v bigcup_ R_i & amp Longleftrightarrow existuje z v X, existuje i v I, (x, z) v R land (z, y) v R_i & amp Longleftrightarrow (x, y) v bigcup_(R_i circ R) koniec

Veta. Nech je $ R $ vzťahom na $ X $. Potom $ (R ^ n) ^ <-1> = (R ^ <-1>) ^ n $ pre všetky $ n geq 1 $.

Dôkaz. Indukciou. Základný krok je zrejmý: $ (R ^ <1>) ^ <-1> = (R ^ <-1>) ^ 1 $. V skutočnosti $ (R ^ 2) ^ <-1> = (R circ R) ^ <-1> = R ^ <-1> circ R ^ <-1> = (R ^ <-1>) ^ 2 $. Indukčný krok je $ (R ^ n) ^ <-1> = (R ^ <-1>) ^ n implikuje (R ^) ^ <-1> = (R ^ <-1>) ^. $ Výsledok teraz vyplýva z argumentu: begin (x, y) v (R ^) ^ <-1> & amp Longleftrightarrow (y, x) v R ^ & amp Longleftrightarrow existuje z v X, (y, z) v R land (z, x) v R ^ n & amp Longleftrightarrow existuje z v X, (z, y) v R ^ <-1> land (x, z) v (R ^ n) ^ <-1> & amp Longleftrightarrow existuje z v X, (x, z) v (R ^ n) ^ <-1> land (z, y) v R ^ <-1> & amp Longleftrightarrow existuje z v X, (x, z) v (R ^ <-1>) ^ n land (z, y) in R ^ <-1> & amp Longleftrightarrow (x, y) in (R ^ <-1>) ^ koniec

Veta. Nech je $ R $ vzťahom na $ X $. Potom $ doľava ( bigcup_ R ^ n vpravo) ^ <-1> = bigcup_ (R ^ <-1>) ^$.

Dôkaz. začať (x, y) in & amp left [ bigcup_ R ^ n vpravo) ^ <-1> Longleftrightarrow (y, x) in bigcup_ R ^ n & amp Longleftrightarrow existuje n geq 1, (y, x) v R ^ n = R ^ circ R & amp Longleftrightarrow existuje n geq 1, existuje z v X, (y, z) v R land (z, x) v R ^ & amp Longleftrightarrow existuje n geq 1, existuje z v X, (z, y) v R ^ <-1> land (x, z) v (R ^) ^ <-1> & amp Longleftrightarrow existuje n geq 1, existuje z v X, (x, z) v (R ^) ^ <-1> land (z, y) v R ^ <-1> & amp Longleftrightarrow existuje n geq 1, existuje z v X, (x, z) v (R ^ <-1>) ^ land (z, y) v R ^ <-1> & amp Longleftrightarrow existuje n geq 1, (x, y) v (R ^ <-1>) ^ n Longleftrightarrow (x, y) ) in bigcup_(R ^ <-1>) ^ n koniec

Veta. Nech je $ R $ vzťahom na $ X $. Potom $ R ^ n cup S ^ n subseteq (R cup S) ^ n $ pre všetky $ n geq 1 $.

Dôkaz. Základný krok je zrejmý. Indukčný krok je: $ R ^ n cup S ^ n subseteq (R cup S) ^ n implikuje R ^ pohár S ^ subseteq (R cup S) ^ $ Výsledok zostáva begin (R pohár S) ^ & amp = (R cup S) ^ n circ (R cup S) & amp supseteq (R ^ n cup S ^ n) circ (R cup S) & amp = [(R ^ n pohár S ^ n) cirkus R] pohár (R ^ n pohár S ^ n) cirkus S & amp = R ^ pohár (S ^ n cirkus R) pohár (R ^ n cirkus S) pohár S ^ & amp supseteq R ^ pohár S ^. koniec

Veta. Nech je $ R $ vzťahom na $ X $. Potom $ (x, y) v R ^ n $ vtedy a len vtedy, ak existuje $ x_1, x_2, x_3, ldots, x_ v X $ také, že $ (x, x_1) v R, (x_1, x_2) v R, ldots, (x_, y) v R $.

Dôkaz. Základný prípad, $ i = 1 $ je zrejmý. Predpokladáme, že tvrdenie je pravdivé pre $ j $. Potom začať& amp (x, y) v R ^ Longleftrightarrow (x, y) v R ^ j circ R & amp Longleftrightarrow existuje x_1 v X, (x, x_1) v R land (x_1, y) v R ^ j & amp Longleftrightarrow existuje x_1 v X, (x, x_1) v R land existuje x_2, ldots, x_ v X, (x_2, x_3), ldots, (x_, y) v R & amp Longleftrightarrow existuje x_1 v X, x_2, ldots, x_ v X, (x, x_1), (x_2, x_3), ldots, (x_, y) v R end podľa potreby na dokončenie indukcie.


(skúste použiť značku X 2 tesne nad poľom Odpovedať)

Stihli ste to naozaj dlho.

Tip: koľko párov je v A? A koľko ich je v T t?

(skúste použiť značku X 2 tesne nad poľom Odpovedať)


Stihli ste to naozaj dlho.

Tip: koľko párov je v A? A koľko ich je v T t?

Nerozumiem tejto otázke úplne, ale pri pohľade na tvoju ekvivalenciu spolu s komentármi Tiny Tim:

po prvé, z A, & amp, viac ako 8 v T ^ t, je možné vytvoriť viac ako 4 páry

Nech T = <(0,2), (1,0), (2,3), (3,1)>
potom spôsob, ako to čítam, nasledujúci po T, dáva: 0

1, takže v tranzitívnej uzávierke je všetko ekvivalentné (tj obsahuje všetky binárne páry).

hm? našiel si 12 v T t.

A má 4 prvky, takže koľko rôznych párov prvkov tam je (počíta sa napríklad <0,3> a <3,0> ako to isté pár).

(ak nemôžete vypočítať to, potom len zoznam oni)

hm? našiel si 12 v T t.

A má 4 prvky, takže koľko rôznych párov prvkov tam je (počíta sa napríklad <0,3> a <3,0> ako to isté pár).

(ak nemôžete vypočítať to, potom len zoznam oni)

Prepáčte, znamenal 12 prvkov v T t

Stále nesledujem. Prečo by <0,3> a <3,0> boli rovnaké?

OK podľa definície:
Tranzitívne uzavretie T je binárny vzťah T t na A, ktorý spĺňa tieto tri vlastnosti:
1. T t je tranzitívny.
2. T je podmnožina T t.
3. Ak S je akýkoľvek iný tranzitívny vzťah, ktorý obsahuje T, potom T t je podmnožinou S.


Obsah

A binárny vzťah R cez sady X a Y. je podmnožina X × Y. < displaystyle X times Y.> [1] [8] Sada X sa nazýva doména [1] alebo súbor odchodu z Ra súprava Y. the codomain alebo súbor určenia z R. Za účelom špecifikácie možností súborov X a Y., niektorí autori definujú a binárny vzťah alebo korešpondencia ako objednaná trojka (X, Y., G) , kde G je podmnožina X × Y < displaystyle X times Y> nazývaná graf binárneho vzťahu. Výrok (x, y) ∈ R < Displaystyle (x, y) v R> znie "X je R- súvisiace s r„a označuje sa xRy. [4] [5] [6] [poznámka 1] doména definície alebo aktívna doména [1] z R je množina všetkých X také, že xRy aspoň pre jedného r. The doména definície, aktívna codomain, [1] obrázok alebo rozsah z R je množina všetkých r také, že xRy aspoň pre jedného X. The lúka z R je spojenie jej definičnej oblasti a jej definičnej domény. [10] [11] [12]


Binárne vzťahy

(2,3))
Je jedna, ktorá nepatrí, ktorá je to. Ostávajú iní?

Člen elity
Člen elity

Devil2euz

Nový člen

(2,3))
Je jedna, ktorá nepatrí, ktorá je to. Ostávajú iní?

HallsofIvy

Člen elity

Usporiadané páry z A = <1, 2, 3, 4> sú <(1, 1), (1, 2). (1, 3), (1, 4). (2, 1). (2, 2). (2, 3), (2, 4). (3, 1), (3, 2), (3, 3), (3, 4). (4. 1), (4, 2), (4, 3), (4, 4)>. Ako povedala pka, je 16 z nich - 4, ktoré začínajú na 1, 4, ktoré začínajú na 2, 4, ktoré začínajú na 3. a 4, ktoré hviezdia na 4.

„Výrok“ „3a + 5b je prvočíslo“ pozostáva zo všetkých párov (a. B), ktoré vyhovujú. Jediným spôsobom, ako to urobiť, je skutočne vypočítať 3a + 5b pre každý pár.

(1,1): 3 (1) + 5 (1) = 8. To nie je prvočíslo, takže (1, 1) nie je vo vzťahu.
(1,2) 3 (1) + 5 (2) = 13. To je prvočíslo, takže (1, 2) je vo vzťahu.
(1,3): 3 (1) +5 (3) = 18. To nie je prvočíslo, takže (1, 3) nie je vo vzťahu.


1.7 Binárne vzťahy

Toto je jeden z viac ako 2 400 kurzov OCW. Preskúmajte materiály tohto kurzu na stránkach prepojených zľava.

MIT OpenCourseWare je bezplatná a otvorená publikácia materiálu z tisícov kurzov MIT, ktorá zahŕňa celé osnovy MIT.

Žiadna registrácia ani registrácia. Voľne prechádzajte a používajte materiály OCW svojim vlastným tempom. Neexistuje žiadna registrácia a dátum začatia ani ukončenia.

Vedomosti sú vašou odmenou. Použite OCW na vedenie svojho celoživotného vzdelávania alebo na výučbu ostatných. Za používanie OCW neponúkame kredit ani certifikáciu.

Vyrobené na zdieľanie. Stiahnite si súbory na neskôr. Poslať priateľom a kolegom. Upravte, remixujte a znova použite (nezabudnite uviesť ako zdroj OCW.)

O spoločnosti MIT OpenCourseWare

MIT OpenCourseWare je online publikácia materiálov z viac ako 2 500 kurzov MIT, ktorá umožňuje slobodné zdieľanie vedomostí so študentmi a pedagógmi z celého sveta. Viac informácií a raquo

& copy 2001 & ndash2018
Massachusettský Inštitút Technológie

Vaše použitie stránok a materiálov MIT OpenCourseWare podlieha našej licencii Creative Commons a ďalším podmienkam použitia.


Vitajte!

Toto je jeden z viac ako 2 400 kurzov OCW. Preskúmajte materiály tohto kurzu na stránkach prepojených zľava.

MIT OpenCourseWare je bezplatná a otvorená publikácia materiálu z tisícov kurzov MIT, ktorá zahŕňa celé osnovy MIT.

Žiadna registrácia ani registrácia. Voľne prechádzajte a používajte materiály OCW svojim vlastným tempom. Neexistuje žiadna registrácia a dátum začatia ani ukončenia.

Vedomosti sú vašou odmenou. Použite OCW na vedenie svojho celoživotného vzdelávania alebo na výučbu ostatných. Za používanie OCW neponúkame kredit ani certifikáciu.

Vyrobené na zdieľanie. Stiahnite si súbory na neskôr. Poslať priateľom a kolegom. Upravte, remixujte a znova použite (nezabudnite uviesť ako zdroj OCW.)


Svojvoľné vzťahy

Z definície binárneho vzťahu ho môžeme ľahko zovšeobecniť na definíciu ľubovoľného vzťahu. Pretože binárny vzťah zahŕňa dve množiny, ľubovoľný vzťah zahŕňa ľubovoľnú zbierku množín. Presnejšie, a vzťah R je podmnožinou nejakého karteziánskeho produktu (http://planetmath.org/GeneralizedCartesianProduct) zo sady množín. V symbole to je

kde každé A i je množina indexovaná niektorou množinou I.

Z tejto všeobecnejšej definície vidíme, že binárny vzťah je len vzťah, kde mám dva prvky. Okrem toho, an n -ary vzťah je vzťah, kde mohutnosť I je n (n konečná). V symbole máme

Nie je ťažké vidieť, že akýkoľvek n -ary vzťah, kde n & gt 1 možno považovať za binárny vzťah n - 1 rôznymi spôsobmi, napríklad

R ⊆ A 1 × A 2 × ⋯ × A n = ∏ i = 1 j A i × ∏ i = j + 1 n A i,

kde j sa pohybuje od 1 do n - 1.

Všeobecný názov pre 3 -ary vzťah je a ternárny vzťah. Je tiež možné mať a 1 -ary vzťahalebo všeobecne známe ako a unárny vzťah, čo nie je nič iné ako podmnožina nejakej množiny.

Na základe prvej poznámky z predchádzajúcej časti možno definovať vzťahy vyššej arity indukčne: pre n & gt 1 je (n + 1) -ary vzťah binárny vzťah, ktorého doménou je n -ary vzťah. V tomto nastavení nie sú definované „unárne vzťahy“ a vzťahy, ktorých arita je „svojvoľná“.

Na vzťah sa dá pozerať aj ako na funkciu (ktorá sama o sebe je vzťahom). Nech R ⊆ A: = ∏ i ∈ I A i. Ako podmnožinu A možno R identifikovať pomocou charakteristickej funkcie

kde χ R ⁢ (x) = 1 ak je x ∈ R a χ R ⁢ (x) = 0 inak. Preto je n -ary vzťah ekvivalentný k (n + 1) -aryárnej charakteristickej funkcii. Z toho sa dá povedať, že 0 -ary, alebo a nulárny vzťah je unárna charakteristická funkcia. Inými slovami, nullový vzťah je iba prvkom v <0, 1> (alebo pravde / nepravde).


Otázka: Porovnajte a porovnajte operačný systém sériového spracovania a operačný systém jednoduchého dávkového spracovania.

Odpoveď: Odpoveď: Jednou z hlavných funkcií operačného systému je správa zdrojov. Zdroj môže byť pevne pripojený k sieti.

Otázka: Otázka na tri časti: 1) Ako funguje indexovanie z hľadiska systémov na správu databáz? 2) Ako sa robí.

Odpoveď: Riešenie som poskytol v kroku 2.

Otázka: Poskytnite dôvod na vysvetlenie, že technické požiadavky a dizajn sú prekladané činnosti (pozri.

A: Requirements engineering (RE) je proces definovania, dokumentovania a udržiavania požiadaviek.

Otázka: Napíšte program s názvom CreateCustomerFile.java, ktorý vám umožní vytvoriť súbor zákazníkov (Custome.

Odpoveď: Poznámka: Vzhľadom na to, že ste v súlade s našimi pravidlami položili viac otázok, prvú otázku vyriešime pre.

Otázka: Napíšte program na zistenie známky študenta na základe známok získaných v troch predmetoch. Th.

Odpoveď: Pretože programovací jazyk nie je uvedený, tak na napísanie kódu používam jazyk C. Ak chceš .

Otázka: V MC68000 je režim adresovania mien, ktorý nie je povolený pre cieľ, spolu s dôvodmi

Odpoveď: Keď ľudia hovoria, že si vytvorili svoj vlastný počítač, myslia tým skutočne to, že myslia i.

Otázka: Píšte v programovacom jazyku c. Vytvorte trojuholník triedy, ktorý má ako strany triedy tri strany. Použite parame.

Odpoveď: Jazyk C nie je objektovo orientovaný jazyk, takže v jazyku C neexistuje koncept tried, ale jazyk C ++ robí ha.

Otázka: napíšte program c ++ Ak v konkrétnej banke zostanú peniaze dlhšie ako 5 rokov, banka zaplatí interne.

Odpoveď: Zadané: napíšte program c ++ Ak v konkrétnej banke zostanú peniaze dlhšie ako 5 rokov, banka ich zaplatí.

Otázka: Napíšte funkciu get_total_price (class_list), ktorá prevezme zoznam volacích čísel a výstupov triedy t.

A: import katalóg ako catl # get total price method def get_total_price (class_list): #iterate through th.


2.1: Binárne vzťahy - matematika

Definícia (Únia): Spojenie množín A a B, označené A B, je množina definovaná ako

Príklad 1: Ak A = <1, 2, 3> a B = <4, 5>, potom AB = <1, 2, 3, 4, 5>.

Príklad 2: Ak A = <1, 2, 3> a B = <1, 2, 4, 5>, potom AB = <1, 2, 3, 4, 5>.

Upozorňujeme, že prvky sa v množine neopakujú.

Definícia (Prienik): Priesečník množín A a B, označený AB, je množina definovaná ako

Príklad 3: Ak A = <1, 2, 3> a B = <1, 2, 4, 5>, potom AB = <1, 2>.

Príklad 4: Ak A = <1, 2, 3> a B = <4, 5>, potom A B =.

Definícia (Rozdiel): Rozdiel množín A od B, označený A - B (alebo A B), je množina definovaná ako

Príklad 5: Ak A = <1, 2, 3> a B = <1, 2, 4, 5>, potom A - B = <3>.

Príklad 6: Ak A = <1, 2, 3> a B = <4, 5>, potom A - B = <1, 2, 3>.

Všimnite si, že všeobecne A - B B - A

Definícia (doplnok): Pre množinu A sa rozdiel U - A, kde U je vesmír, nazýva doplnok A a označuje sa ním.
Toto je množina všetkého, čo nie je v A.

-> Definícia (usporiadaný pár): Objednaný pár je dvojica objektov, s ktorými je spojené poradie.
Ak sú objekty reprezentované x a y, potom zapíšeme usporiadaný pár ako (x, y).

Dva usporiadané páry (a, b) a (c, d) sú rovnaké vtedy a len vtedy, ak a = c a b = d. Napríklad zoradený pár (1, 2) sa nerovná usporiadanému páru (2, 1).

Definícia (karteziánsky súčin): Množina všetkých usporiadaných párov (a, b), kde a je prvok A a b je prvok B, sa nazýva karteziánsky súčin A a B a označuje sa A B.
Príklad 1: Nech A = <1, 2, 3> a B = . Potom
A B = <(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)>.

Príklad 2: Pre rovnaké A a B ako v príklade 1,
B A = <(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)>.

Ako vidíte v týchto príkladoch, všeobecne A B B A, pokiaľ A =, B = alebo A = B.
Všimnite si, že A = A = pretože neexistuje žiadny prvok na vytvorenie usporiadaných párov s prvkami A.

Koncept karteziánskeho súčinu možno rozšíriť na viac ako dve sady. Najskôr definujeme pojem usporiadaná n-tica.

Definícia (zoradená n-tica): Poriadaná n-n-tica je množina n objektov, s ktorými je spojené poradie. Ak je n objektov reprezentovaných x 1, x 2,. x n, potom napíšeme zoradené n -tuple ako (x 1, x 2,. x n).

Definícia (karteziánsky súčin): Nech A 1,. A n je n množín. Potom sa množina všetkých usporiadaných n -tuplov (x 1,. X n), kde x i A i pre všetky i, 1 i n, nazýva karteziánsky súčin A 1,. A n a je označená A 1. A n.

Definícia (rovnosť n -tuplov): Dve usporiadané n -tuple (x 1,. X n) a (y 1,. Y n) sú si rovné práve vtedy, ak x i = y i pre všetky i, 1 i n.
Napríklad usporiadaná trojica (1, 2, 3) sa nerovná usporiadanej trojici (2, 3, 1).

Definícia (binárny vzťah):
Binárny vzťah zo sady A do množiny B je množina usporiadaných párov (a, b), kde a je prvok A a b je prvok B.
Keď je usporiadaný pár (a, b) vo vzťahu R, napíšeme R b alebo (a, b) R. Znamená to, že prvok a súvisí s prvkom b vo vzťahu R.
Keď A = B, voláme vzťah z A do B (binárny) vzťah na A.

Príklady:
Ak A = <1, 2, 3> a B = <4, 5>, potom napríklad <(1, 4), (2, 5), (3, 5)> je binárny vzťah od A do B.
<(1, 1), (1, 4), (3, 5)> však nie je binárny vzťah z A do B, pretože 1 nie je v B.
Vzťah rodič - dieťa je binárny vzťah na množine ľudí. (John, John Jr.) , for example, is an element of the parent-child relation if John is the father of John Jr.


Pozri si video: BINARNI SISTEM (December 2021).