Diskrečioji matematika. Sąvokos ir teorija

Aibės sąvoka yra pirminė,todėl neapibrėžiama. Aibės sinonimai – sistema, klasė, šeima, sritis, visuma. Aibę sudaro elementai. Aibė gali būti išreikšta: a)visų elementų sąrašu; b)elementų charakteringųjų savybių abrašymu; c)generuojančiaja procedūra. Sąrašu galima išreikšti tik baigtines aibes. Sąrašas apgaubiamas figūriniais skliaustais. Generuojančioji procedūra aprašo būdą,kaip gauti aibės elementus iš jau gautų arba iš kitų objektų. Aibės elementais laikomi visi objektai, kurie gali būti gauti naudojant generuojančiąją procedūą. Veno diagramos – grafinis aibių vaizdavimo būdas. A. Aibė A vadinama aibės B poaibiu, jei bet kuris aibės A elementas priklauso aibei B. Žymima AcB. A. Aibės A ir B vadinamos lygiomis, jei jų elementai sutampa, t.y. jei AcB ir BcA, tai A=B. A. Jei AcB ir A nelygu B, tai A vadinamas tikriniu aibės B poaibiu. Aibės gali būti baigtinės. A. Baigtinės aibės elementų skaičius vadinamas aibės A galu. Aibė, kurios gale yra nulis, vadinama tuščia aibe. A. Aibių A ir B sąjunga vadinama aibė, sudaryta iš elementų, priklausančiai bent vienai iš aibių A, B. Žymima AUB. Analogiškai apibrėžiama sąlyga bet kokiai aibių visumai. A. Aibių A ir B sankirta vdinama aibė, sudaryta tik iš elementų, kurie priklauso ir A ir B. Žymime A B. A. Aibių sistema, kurios bet kurių porų sankirtos yra tuščia aibė, o visų aibių sąjunga yra lygi, aibę Q vadinsime aibės U skaidiniu. Jei visos nagrinėjamos aibės yra tam tikros universalios aibės poaibiai, tai gali būti aprėžtas aibės papildinys. A. Aibės A papildiniu (iki aibės U) vadinama aibė, sudaryta iš elementų, kurie nepriklauso aibei A (bet priklauso aibei U). Papildinys žymimas A(su viršuj brūkšneliu)=U\A. Vektorius, tai sutvarkytas elementų rinkinys. Šis sakinys neapibrėžimas. Sąvoką vektorius kaip ir aibės sąvoką laikysime neapibrėžiama.Elementai, sudarantys vektorių, vadinami koordinatėmis.Jos numeruojamos iš kairės į dešinę. Vektoriaus koordinačių skaičius vadinamas vektoriaus ilgiu arba dimensija. Skirtingai nuo aibės elementų, vektoriaus koordinatės gali sutapti. Vektoriaus koordinates rašysime ( ) skliaustuose. A. Vektoriai lygūs, jei jie yra vienodo ilgio ir jų atitinkamos koordinatės lygios. A. Aibių A ir B tiesiogine (Dekarto) sandauga vadinama aibė porų (a,b) aЄA, bЄB. AxB={(a,b)│ aЄA, bЄB} Jei A=B, tai abi koordinatės priklauso aibei A. A. Vektoriaus projekcija į i-tają ašį vadinama jo i-toji komponentė. Vektoriaus v projekcija į ašis su numeriais i1, ..., ik, vadinamas vektorius (v i1, ..., v ik) pr i1, ik. Tarkime, kad V- vienodos dimencijos vektorių aibė, tada aibės projekcija į i-taja ašį vadinama visų aibės V vektorių projekcijų į i-tają ašį aibė. Pr i V={pr 1 v|v priklauso V} Analogiškai apibrėžiama aibės V projekcija į kelias ašis. A. atitiktimi tarp aibių A ir B vadinamas poaibis GcAxB. (a,b) priklauso G, Tai sakoma, kad b atitinka a pagal atitiktį G. A. aibė pr 1 G (G projekcija į pirmają ašį) vadinama atitikties apibrėžimo sritimi. Pr 2 G- atitikties reikšmių sritimi. A. atitiktis vadinama pilnai apibrežta jei pr 1 G=A. Priešingu atveju atitiktis vadinama dalinai apibrėžta. A. Atitiktis vadinama siurjekcine, jei pr 2 G=B. A. Aibė visų b priklauso B, atitinkančių elementą a priklauso A, vadinama a vaizdu aibėje B pagal atitiktį G. A. Aibė visų a priklauso A, kuriems atitinka b priklauso B vadinama b pirmavaizdžiu aibėje A pagal atitiktį G. Jei C c pr 1 G, tai aibės C vaizdu aibėje B vadinama visų aibės C elementų vaizdų sąjunga. Analogiškai apibrėžiamas aibės D pirmavaizdis aibėje A. D c pr 2 G. A. Atitiktis G vadinama funkcine (vienareikšme), jei bet kurio aibės pr 1 G elemento vaizdas yra vienintelis pr 1 G elementas. A. Atitiktis G tarp aibių A ir B vadinama abipusiškai vienareikšme (diekcija), jei ji pilnai apibrėžta, siurjekcine, funkcinė ir bet kurio aibės pr 2 G pirmavaizdis yra vienintelis aibės pr 1 G elementas. PVZ:. Anglų- Lietuvių kalbų žodynas apibrėžia atitiktį tarp angliškų ir lietuviškų žodžių aibių. Ši atitiktis nėra funkcinė, nes vienam angliškam žodžiu dažnai atitinka keli lietuviški žodžiai. A. G 1 c AxB G 2 c BxC H c AxC vadinama atitikčių G 1 ir G 2 kompozicija, jei pora(x,z) priklauso H, tada ir tik tada, kai (x,y) priklauso G 1 ir (x,y) priklauso G 2. A. Atitiktis G –1laipsnyje vadinama atvirkštine atitikčiai G, jei (y,x) priklauso G –1laipsnyje, tada ir tik tada, kai (x,y) priklauso G. Jei tarp baigtinių aibių A ir B egzistuoja abipusiškai vienareikšmė atitiktis, kai aibių galios yra lygios. |A|=|B| Šis faktas: 1. Leidžia nustatyti aibių galių lygybę, neskaičiuojant jų galių. 2. Leidža apskaičiuoti aibės galią, nustatant abipusiškai vienareikšmę atitiktį su aibe, kurios galia žinoma arba lengvai apskaičiuojama. A. aibė, ekvivalenti aibei N, vadinama skaičiąja. A. Funkcija vadinama funkcinė atitiktis. Jei funkcija f nustato atitiktį tarp A ir B, tai žymima f: A LB. Kiekvienam elementui a iš savo apibrėžimo srities funkcijos f nustato atitiktį į vienintelį elementą b iš reikšmių srities. Žymima f(a)=b Pilnai apibrėžta funkcija f: A ­­:B. Vadinama aibės A atvaizdžiu aibėje B. Aibės A vaizdas žymimas f(A). Jai atitiktis f tuo pačiu yra ir siurjektyvi, tai sakoma, kad turime A atvaizdį į B. f AA vadinamas aibės A transformacija. A. Funkcija f g lygios, jai jų apibrėžimo sritis viena ir ta pati aibė A ir kiekvienam a priklauso A f(a)= g(a). A. Jei atitiktis atvirkštinė f f: AB yra funkcinė, ji vadinama atvirkštine funkcija, funkcijai f. Žymima f –1laipsnyje. A. Tegul duotos funkcijos f:AB; g:BC. Funkcija h: AC vadinama funkcijų f ir g kompozicija, jai gfalioja lygybė h (x) =g (f (x)), x priklauso A. Dažnai sakoma, kad funkcija h gaunama įrašius funkciją f į funkciją g. A. Funkcija, gauta iš funkcijų f1, f2, ..., fn įrašius jas vieną į kitą ir pervadijus argumentus, vadinama funkcijų f1, f2, ..., fn superpozicija. A. Aibė S c A laipsnyje n vadinama n-viečiu sąryšiu aibėje A. Sakoma, kad a1, a2, ..., an yra sąryšyje S, jei vektorius (a1, a2, ..., an) priklauso S. Vienvietis sąryšis tai paprastas A poaibis. Tokie sąryšiai vadinami požymiais. Sakoma, kad elementas a turi požymį S, jei a priklauso S ir ScA. Dažniausi sutinkami ir gerai išanalizuoti dviviečiai arba binariniai sąryšiai. A. Sąryšis vadinamas atvirkštiniu sąryšiu S (S –1laipsnyje), jei a S –1laipsnyje b, arba (a,b) priklauso S –1laipsnyje, tada ir tik tada, kai b S a. Iš apibrėžimo tiesiogiai išplaukia, kad (S –1laipsnyje) –1laipsnyje =S (atvirkštinio sąryšio atvirkštinis sąryšis yra S). A. (1 savybė) a) sąryšis S vadinamas refleksyviu, jei bet kuriam a priklauso A arba aSa. B) sąryšis Svadinamas antirefleksyviu jei nei vienam a priklauso A negalioja aSal. A. (2 savybė) a) sąryšis S vadinamas simetriniu, jei bet kuriai porai(a,b) priklauso A kvadratu iš aSb išplaukia, kad bSa. Tai yra sąryšis galioja į abi pusias arba nei į vieną. B) sąryšis su S vadinamas antisimetriniu, jei iš aSb ir bSa išplukia, kad a=b. A. (3 savybė) sąryšis S vadinamas tranzityviu, jei bet kuriems a, b, c priklauso A iš aSb ir bSc išplaukia, kad aSc. A. Bet kuriam sąryšiui S sąryšis S su stogeliu vadinamas tranzityviu uždariniu. Jei aibėje A egzistuoja seka iš n elementų a=a1,a2, …, an=b, kurios gretimiems elementams galioja sąryšis S. aSa2, a2Sa3,..., an-1Sb; a S su stogeliu b. jei sąryšis yra tranzytivus, tai S su stogeliu =S. A. Operacija fi vadinama asociatyvia, jei bet kuriems elementams a,b, c, galioja lygybė (a fi b) fi c=a fi ( b fi c) šios sąlygos tenkinimas reiškia, kad reiškinyje a fi b fi c galime nenaudoti skliaustų. Skaičių sudėtis ir daugyba yra asociatyvios operacijos, todėl galima nenaudoti skliaustų reiškiniuose a+b+c, axbxc. A. Operacija fi vadinama komutatyvia, jei bet kuriems elementams a ir b galioja lygybė a fi b= b fi a. Skaičių sudėtis ir daugyba komutatyvios operacijos. Atimtis ir dalyba nekomutatyvios. A. Operacija fi vadinama distributyve (paskirstoma) iš kairės operacijos psi atžvilgiu, jai bet kuriems a, b, c, elementams galioja lygybė a fi (b psi c)= (a fi b) psi(a fi c). Ir distributyve iš dešinės operacijos psi atžvilgiu, jei (a psi b) fi c = (a fi c) psi (b fi c). Distributivumo sąvybė leidža atskleist skliaustus, PVZ:. skaičių daugyba distribūtivi sudėties atžvilgiu iš kairės ir dešinės. Kėlimas laipsniu distributyvus iš dešinės daugybos atžvilgiu. Aibių sąjungo ir sankirtos operacijos yra distributyvios viena kitos atžvilgiu iš kairės ir dešinės. A. Algebros A homomorfizmu į algebrą B vadinamas atvaizdis gama gama:KM, tenkinantis sąlygą gama (fi i (kj1, ..., kj1(i) )) = psi i (gama (kj1), ..., gama( kjl (i) )). Visiems i nuo 1 iki p. (i =1,p su brukšniu viršui). l(i) – operacijų fi i ir psi i narių skaičius, kuris pagal sąlyga joms yra vienodas. Ir visiems kjr priklauso K. A. Algebros A izomorfizmu į algebrą B vadinamas abipusiškai vienareikšmis homomorfizmas. Bet kuris begalinis N poaibis skaitusis. Tarkime N’cN, būtinai begalinis. Išrinkime mažiausią N’ elementą ir pažymėkime jį n1. Išrinkime aibės N’\{n1} mažiausią el ir pažymėkime jį n2. Tada iš aibės N’\{n1,n2} mažiausią pažymėkime n3. Kadangi bet kuris natūralusis skaičius turi tik baigtinę aibę mažesnių už jį natūraliųjų sk, tai bet kuris N’ el anksčiau ar vėliau gaus savo nr. Ši numeracija tai yra atitiktis (n,ni) ir yra abipusiškai vienareikšmė atitiktis tarp N’ ir N, o tai reiškia, kad N’ yra skaičioji aibė. Aibė N2 skaičioji. Aibės N2 el sunumeruosime tokiu būdu. Padalinsime aibę N2 į klases. Pirmajai klasei N21 priskirsime visas skaičių poras, kurių suma mažiausia. Tokia pora yra tik viena (1;1). Antrajai klasei N22 – visas sk poras, kurių suma 3. N22{(1;2);(2;1)}. Bendru atveju N2i{(a;b)|a+bi+1}. Dabar surikiuosime klases indekso didėjimo i tvarka, o poras klasės viduje – pirmo elemento didėjimo tvarka. Gautąją seką sunumeruosim 1,2,3… . Nesunku pastebėti, jei a+bi+1, tai pora (a;b) 1+2+…+(i-1)+a. Ši numeracija ir įrodo aibės N2 skaitumą. Atkarpos [0;1] visų realiųjų skaičių aibė neskaiti. (Kantoro teorema) Ją įrodysime prieštaros būdu. Tarkime, kad ši aibė yra skaičioji ir jos elementus sunumeruosime. Surinksime visus skaičius išreikštus dešimtainėmis trupmenomis jų numeracijos tvarka. 0,a11a12a13… Nagrinėsime bet kurią dešimtainę trupmeną 0,b1b2b3…, tokią, kur b1a11, b2a22… . Ši trupmena negali įeiti į nurodytą seką todėl, kad nuo pirmojo skaičiaus skiriasi pirmuoju skaitmeniu, nuo antro – antruoju ir t.t. Vadinasi visi atkarpos [0;1] realieji sk negali būti sunumeruoti, todėl visų realiųjų atkarpos [0;1] skaičių aibė neskaiti. Atkarpos galia vadinama kontiniumu. Metodas, kurį įrodėme vadinamas Kantoro įstrižainių metodu. Pirma: A1,A2,…,An – baigtinės aibės. |A1|m1, |A2|m2,…, |An|mn. Tada aibės A1xA2x…xAn galia lygi aibių galių sandaugai. |A1xA2x…xAn|m1m2…mn. Įr. Įrodysime matematinės indukcijos metodu. 1)n1 teorema teisinga, nes |A1|m1. 2)Sakykime, kad ji teisinga, kai nk ir įrodysime, kad ji teisinga, kai nk+1. |A1xA2x…xAk|m1m2…mk. 3)Paimsime bet kurį iš eilės A1xA2x…xAk vektorių (a1,a2,…,ak) ir jam iš dešinės pusės prirašysime elementą ak+1. Tai galime padaryti mk+1 kartų. Ir gausime mk+1 skirtingų aibės A1xA2x…xAk+1 vektorių. Tokiu būdu iš visų m1m2…mk vektorių prirašydami iš dešinės pusės aibės Ak+1 elementą galime gauti m1m2…mkmk+1 aibės A1xA2x…xAk+1 vektorių. Beto jie visi skirtingi ir jokių kitų vektorių aibėje A1xA2x…xAk+1 nėra. Todėl, kai nk+1 teorema teisinga ir iš to išplaukia, kad ji teisinga bet kokiam n. Antra: Jei baigtinė aibės A galia |A|, tai visų jos poaibių skaičius 2|A|. Įr. Sunumeruokime aibės A elementus nuo 1 iki n. A{a1,a2,…,an} ir paimkime n dydžio dvejetainų vektorių, kurių koordinatės (0,1) aibę Bn. Kiekvienam poaibiui A*cA nustatysim į atitiktį vektorių v(v1,v2,…,vn), tokiu būdu, kad vi{0,jei aiA*; 1,jei aiA*. Akivaizdu, kad nustatyta atitiktis tarp visų aibės A poaibių aibės ir dvejetainiu vektorių aibės galia yra abipusiškai vienareikšmė. Todėl A aibės poaibių sk lygus galiai Bn, kadangi Bn yra n dviejų elementų aibių {0,1} dekarto sandauga. T.y. Bn{0,1}x{0,1}x…x{0,1} (n dauginamųjų). Iš 1.1 teoremos išplaukia, kad |Bn||{0,1}n||{0,1}|n2n2|A|. Operacija tai funkcija, kuri apibrėžiama taip: : An → A. Pavyzdžiui: +:Z2 → Z yra įprasta sumos operacija dviem (nes n = 2) sveikiesiems skaičiams. Algebra vadinama sistema

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!