Diskretinės matematikos metodai dokumentas
5 (100%) 1 vote

Diskretinės matematikos metodai dokumentas

DISKRETINĖS MATEMATIKOS METODAI

2. SANTYKIAI

Poaibis RĶMn yra vadinamas n-mačiu santykiu, apibrėžtu aibėje M. Labiausiai paplitę santykiai yra, kai n=2. Jie vadinami binariniais. Šiuo atveju priklausomybė (a,b) ĪR yra dažnai užrašoma aRb.

Tegul aibėje M yra duotas santykis R. Bet kuriam poaibiui M1 Ķ M galima apibrėžti santykį R’, vadinamą santykio R susiaurinimu aibei M1, kurį sudaro visos poros iš R, neturinčios elemento, priklausančio M1. Kitaip tariant, R’=RĒM12.

Binarinis santykis gali būti vaizduojamas įvairiai. Galima išvardinti visas poras. Priklausančias R, arba galima surašyti visą informaciją į matricą. Pastaruoju atveju matricos, tegul C, elementasKadangi santykiai yra tam tikros aibės poaibiai, tai tarp jų galioja tokios pat operacijos kaip ir tarp aibių. Be to, yra tokia specifinė operacija. Tegul R – santykis. Tada jam gali būti priskiriamas atvirkštinis santykis R-1, kuomet aiR-1aj tada ir tiktai tada, kada ajRai. Pagal apibrėžimą (R-1) -1=R.

Apibrėšime dabar paprasčiausias santykių savybes. Santykis R vadinamas refleksyviu, jeigu bet kuriam aibės M (pagimdančios R) elementui a galioja aRa. Priešingai, R vadinamas antirefleksyviu, jeigu nėra tokio aĪM, kad būtų aRa. Pavyzdžiui, santykiai £ ir “turėti bendrą vardiklį” yra refleksyvūs, o < ir “būti sūnumi” yra antirefleksyvūs. O santykis “būti simetrišku x ašies atžvilgiu” yra nei vienoks nei kitoks. Santykis R vadinamas simetrišku, jeigu bet kuriai porai (a,b)ĪM2 iš to, kad aRb, seka bRa. Simetriško santykio matrica yra simetriška pagrindinės diagonalės atžvilgiu: C i j = C j i visiems i ir j. Santykis R vadinamas antisimetrišku, jeigu iš aiRaj ir ajRai seka, kad ai=aj. Tokiu, pavyzdžiui, yra santykis £. Aišku, kad santykis R yra simetriškas tada ir tiktai tada, kada R=R-1. Santykis R vadinamas tranzityviu, jeigu bet kuriems a,b,c iš to, kad aRb ir bRc, seka aRc. Santykiai =, £, “gyventi viename mieste ” yra tranzityvūs, o santykis “turėti netuščią persikirtimą” – ne. Bet kuriam santykiui R santykis R^, vadinamas R tranzityviu uždarymu, apibrėžiamas taip: aR^b, jeigu aibėje M egzistuoja seka a=a1,a2,…,an-1,an=b tokia, kad aRa2, a2Ra3,…,an-1Rb. Jeigu R tranzityvus, tai R^= R. Pavyzdžiui, santykio “būti sūnumi” tranzityvus uždarymas – tai santykis “būti palikuonimi”.

Santykis R vadinamas ekvivalentiškumo santykiu, jeigu jis yra refleksyvus, simetriškas ir tranzityvus. Tegul M yra aibė, o R ekvivalentiškumo santykis, apibrėžtas joje. Aibė M yra suskaidoma į poaibius sekančiu būdu. Išrenkamas bet kuris elementas a1ĪM ir formuojama klasė C1, susidedanti iš a1 ir visų bĪM tokių, kad galioja a1Rb. Po to išrenkamas elementas a2ĪMC1 ir iš a2 bei visų elementų, ekvivalentiškų jam, sudaroma klasė C2. Tęsiant šį procesą gaunama klasių sistema Ci, iĪI={1,2,…}, tenkinanti tokias sąlygas: 1) (nuo iĪI) Č Ci =M; 2) Ci Ē Cj =Ę, visiems i,jĪI, i¹j; 3) bet kurie du vienos klasės elementai yra ekvivalentiški; 4) bet kurie du elementai iš skirtingų klasių yra neekvivalentiški. Gautas suskaidymas yra vadinamas aibės M suskaidymas į ekvivalentiškumo klases santykio R atžvilgiu. Klasių skaičius yra vadinamas suskaidymo indeksu. Galimas ir atvirkščias kelias. Turint aibės M suskaidymą į klases gaunamas ekvivalentiškumo santykis R. Dviem elementams a,bĪM galioja aRb tada ir tiktai tada, kada a ir b priklauso vienai suskaidymo klasei.

Pavyzdys. Aibė M – tai natūrinių skaičių aibė N, o santykis R – tai “turėti tokią pat liekaną po dalybos iš 7”. Šiuo atveju R indukuoja 7 ekvvalentiškumo klases: 0,7,14,…; 1,8,15,…; 2,9,16,… ir t.t. Visos jos suskaičiuojamos.

Santykis vadinamas negriežtos tvarkos santykiu, jeigu jis refleksyvus, antisimetriškas ir tranzityvus. Jeigu santykis antirefleksyvus, antisimetriškas ir tranzityvus, tai jis vadinamas griežtos tvarkos santykiu. Aibė M, kurioje yra apibrėžtos tvarkos (negriežtos ar griežtos) santykis, vadinama pilnai sutvarkyta, ir dalinai sutvarkyta priešingu atveju. Dalinai sutvarkytos aibės pavyzdys – tai kokios tai aibės poaibių sankaupa M. sutvarkymą duoda įjungimo santykis Ķ.

3. ALGEBROS

Atvaizdavimas j: Mn®M yra vadinamas n-arine operacija, apibrėžta aibėje M. Aibė M kartu su užduota joje operacijų sankaupa Q={j1,j2,…}, t.y. sistema A=(M; j1,j2,…) yra vadinama algebra.

Aibė M’ĢM vadinama uždara n-arinės operacijos j atžvilgiu, jeigu j (M’n)ĶM’. jeigu aibė M’ yra uždara visų algebros A operacijų j1,j2,… atžvilgiu, tai sistema A’=(M’; j1,j2,…) yra vadinama algebros A poalgebra.

1 pavyzdys . Algebra (R;+, *) vadinama realių skaičių lauku, čia R – tai visų skaičių tiesė. Šios algebros poalgebra gali būti, pavyzdžiui, visų racionalių skaičių laukas.

2 pavyzdys . Tegul U – aibė, o b( U) – visų jos poaibių sankaupa (dar vadinama buleanu). Algebra B=(b( U); Č,Ē, -) vadinama buline aibių algebra. Bet kuriam poaibiui U’Ģ U sistema B’=(b( U’); Č,Ē, -) yra algebros B poalgebra.

Tegul duotos 2 algebros A=(K; j1,…jp) ir B=(M; y1,…yp) su operacijomis ji:Kl(i)®K, yi:Ml(i)®M, i=1,2,…p, (tada sakoma, kad algebros A ir B yra vienodo tipo). Algebros A į algebrą B homomorfizmu vadinamas atvaizdavimas r:K®M, tenkinantis sąlygą r(ji( ,…, ))=y i (r( ),…,r( )), visiems i=1,2,…,p ir
visiems ĪK.

Šiuo metu Jūs matote 53% šio straipsnio.
Matomi 889 žodžiai iš 1666 žodžių.
Peržiūrėkite iki 100 straipsnių per 24 val. Pasirinkite apmokėjimo būdą:
El. bankininkyste - 1,45 Eur.
Įveskite savo el. paštą (juo išsiųsime atrakinimo kodą) ir spauskite Tęsti.
SMS žinute - 2,90 Eur.
Siųskite sms numeriu 1337 su tekstu INFO MEDIA ir įveskite gautą atrakinimo kodą.
Turite atrakinimo kodą?
Po mokėjimo iškart gausite atrakinimo kodą, kurį įveskite į laukelį žemiau:
Kodas suteikia galimybę atrakinti iki 100 straispnių svetainėje ir galioja 24 val.