1.Naturalieji skaiciai. Matematines indukcijos principas
Nepriestaringumo desnis. Du vienas kitam priesingi teiginiai p ir ¯p vienu metu negali buti teisingi (p^¯p=0)
Treciojo negalimo desnis. Is dvieju priesingu teiginiu p ir ¯p vienas visada yra teisingas (p^¯p=1).
Apibrezimas. Naturaliaisiais skaiciais vadiname netuscios aibes N elementus, jeigu tarp kai kuriu is ju
egzistuoja sarysis ,,a‘ eina po a“, tenkinantis aksiomas:
1) egzistuoja skaicius (vadinamas vienetu), neinantis po jokio kito skaiciaus;
2) po kiekvieno skaiciaus eina tik vienas skaicius;
3) kiekvienas skaicius eina ne daugiau kaip po vieno skaiciaus;
4) aibes N poaibis M sutampa su pacia aibe N, jei jis turi tokias savybes:
a) 1 $ M,
b) jeigu skaicius a priklauso M, tai ir po a einantis skaicius a‘ taip pat priklauso aibei M
Matematines indukcijos principas
Tegu p(n) – kazkoks teiginys apie naturaluji skaiciu n. Tarkime, kad p(1) yra teisingas, ir is prielaidos, kad p(n) yra teisingas, sugebame isvesti, kad p(n‘) irgi yra teisingas. Darome isvada: teiginys p(n) yra teisingas visiems n $ N.
Archimedo aksioma. Bet kuriai naturaliuju skaiciu porai a, b galima rasti toki naturaluji skaiciu n, kad an>b.
Maziausiojo elemento principas. Kiekvienas netuscias naturaliuju skaiciu aibes poaibis turi maziausia elementa.
Dirichle (P.G.L. Dirichlet, 1805–1859) principas. Jei m rutuliu yra sudeti i n < m deziu, tai bent vienoje dezeje yra 2 ar daugiau rutuliu.
2.Dauginimo tasykle
Dekarto ( Rene Descartes, 1596–1650) sandauga. Tai sutvarkytuju poru aibe.
A × B = {(ai, bj) : ai e A, bj e B, 1 ≤i ≤ n, 1 ≤ j≤ m}
1 teorema. |A × B| = |A| |B|.
2 teorema. Jei abecele A turi n raidziu, tai galime sudaryti n^k zodziu, kuriu ilgis yra k.
3 teorema. Aibes A = {a1, . . . , an} poaibiu, iskaitant ir tusciaji, skaicius lygus 2^n.
|>Nagrinekime visu poaibiu aibes atvaizdi aibeje, sudarytoje is n zodziu su ,,raidemis“ 0, 1. Sis atvaizdis apibreztas taip: A ] P = {ai1 , . . . , aik} 7! (0 . . . , 0, 1, 0 . . . , 0, 1, 0, . . . 0) cia ,,raide“ 1 irasyta is-oje pozicijoje pabreziant, kad is-asis aibes A elementas patenka i poaibi P. Atvaizdis yra bijekcija. Pagal 2 teorema siu zodziu aibes galia lygi 2^n ir sutampa su k poaibiu aibes galia.<|
4 teorema. Jei X = {x1, . . . , xn} ir Y = {y1, . . . , ym}, tai funkciju f : X ->aibes galia lygi m^n.
|>Kiekviena funkcija f : X ->galime vienareiksmiskai isreiksti vektoriumi (f(x1),…,f(xn)). Kadangi dabar ,,raide“ f(xj ), 1≤ j≤ n, imama is abeceles Y, turincios m raidziu, teoremos teiginys isplaukia is 2 teorem. <|
Sioje teoremoje isvesta formule paaiskina daznai naudojama zymeni {f : X ->Y } =: Y^X .
3. Gretiniai, keliniai ir deriniai
1 teorema. Ak/n = n(n − 1)(n − 2) • • • (n − k + 1).
2 teorema. Deriniu is n po k skaicius lygus Ck/n = (Ak/n)/k!= n!/(k!(n − k)!)
Mokslineje literaturoje vartojami ir tokie deriniu is n po k zymemys: (n//k)= (n//(k, n − k))
Paimtas is n aibes k elementu rinkinys su galimais pasikartojimais vadinamas kartotiniu sios aibes k deriniu. Ju skaicius Hk/n = Ck/(n+k−1)=((n+k−1)//k)
4. Kartotiniai gretiniai
Teorema. Polinominiu koeficientu formule yra (n//(p1, . . . , pk))
|>Dauginkime panariui n nezinomuju sumu, imdami xi1 is pirmosios sumos, xi2 is antrosios sumos ir t.t., xin is n-osios sumos ir sudekime visas sandaugas
(2) xi1 • • • xin. Kadangi ij 2 {1, . . . , k}, 1 ≤ j ≤ n, tai turesime k^n sandaugu (visus n zodzius is k raidziu x1, . . . , xk). Sudedant (2) sandaugas, reikia sutraukti panasius narius. Jie bus to paties pavidalo, t.y.