Aibės

Aibės sąvoka

Aptarsime aibių teorijos, kuri matematikoje vadinama naiviąja aibių teorija, pradmenis. Šioje teorijoje aibės sąvoka – tai fundamentali neapibrėžiama sąvoka. Aibių teorijos kūrėjas vokiečių matematikas G.Kantoras (1845 – 1918) sakė, kad aibė – tai objektų, kuriems būdingas tam tikras požymis, visuma. Pavyzdžiui, lotynų abėcėlės raidžių aibė, krepšinio komandos žaidėjų aibė, studentų akademinės grupės aibė, euklidinės plokštumos taškų aibė ir pan. Lotynų abėcėlės aibę sudaro raidės, krepšinio komandą sudaro jos žaidėjai, studentų akademinę grupę sudaro studentai, euklidinę plokštumą sudaro taškai. Apskritai, objektai, sudarantys aibę, vadinami aibės elementais. Kitaip tariant, aibė – tai elementų “maišelis”. Reikia pabrėžti, kad aibėje negali būti vienodų elementų, t.y. visi aibės elementai yra skirtingi.

Aibės paprastai žymimos lotynų raidyno didžiosiomis raidėmis, pavyzdžiui, A, B, C ir pan. Matematikoje dažniausiai naudojamų aibių simbolika yra nusistovėjusi. Pavyzdžiui:

N – natūraliųjų skaičių aibė,

Z – sveikųjų skaičių aibė,

Q – racionaliųjų skaičių aibė,

R – realiųjų skaičių aibė,

C – kompleksinių skaičių aibė,

– tuščioji aibė.

Aibės nusakymo būdai

Paprastai aibė nusakoma tokiais būdais:

išvardinimo,

aprašymo,

grafiniu

Išvardinimo būdu aibė aprašoma išvardinant visus jos elementus. Pavyzdžiui, A = , B= X = . Daugtaškis skaitomas “ir taip toliau” arba “ir taip toliau iki”. Aibės elementai rašomi riestiniuose skliaustuose ir skiriami vienas nuo kito kableliais. Išvardinimo būdas yra naudojamas, kai aibės elementų skaičius yra nedidelis arba aiškus elementų dėsningumas.

Nusakant aibę aprašomuoju būdu, nurodomas predikatas , ir aibę sudaro tie elementai, kuriems šis predikatas yra teisingas: A= arba , čia aibę A sudaro elementai a, kuriems predikatas p(a) yra teisingas, o aibę X sudaro tie aibės M elementai, kuriems predikatas p(x) yra teisingas. Pavyzdžiui,

,

,

C

P

Aišku, kad aibę A sudarys natūralieji skaičiai 6, 7, 8, 9, 10; aibę B sudarys skaičiai 2 ir 3; aibę C sudarys IF-0/1 grupės pirmūnai, o aibę P sudarys natūralieji pirminiai skaičiai.

Vaizduojant aibę grafiniu būdu, naudojamos Veno diagramos. Jos paprastai naudojamos vaizdžiai parodyti santykius bei veiksmus su aibėmis. Veno diagrama – tai aibė plokštumos taškų, apribotų uždarąja kreive (paprastai apskritimu). Pavyzdžiui,

Simbolika

Aibė, neturinti nei vieno elemento, vadinama tuščiąja aibe ir, kaip buvo minėta aukščiau, žymima simboliu

Simboliu žymime, kad x yra aibės A elementas.

Simboliu žymime, kad x nėra aibės A elementas.

Aibės A elementų skaičių žymime arba .

Aibės elementų skaičius kitaip vadinamas aibės galia. Jei aibės elementų skaičius yra baigtinis, tai aibė vadinama baigtine, priešingu atveju – begaline. Pavyzdžiui, aibė P = yra baigtinė aibė, o aibės N, Z, R, A = yra begalinės aibės.

Kaip buvo minėta aukščiau, aibė negali turėti vienodų elementų. Užrašas yra nekorektiškas ir jį reikia pakeisti taip: .

Santykiai

Aibės A ir B yra lygios ir žymimos A = B, jei jos sudarytos iš tų pačių elementų. Priešingu atveju A B.

Griežtai matematiškai aibių lygybę galime užrašyti taip:

,

čia simbolis “” reiškia ekvivalenciją (“tada ir tik tada, kai”).

Jei tarp dviejų aibių A ir B nustatyta abipusiai vienareikšmė atitiktis – atvaizdis , tai sakome, kad aibės A ir B yra ekvivalenčios. Žymime A ~ B.

Aibė A vadinama skaičiąja, kai A ~ N. Kitaip tariant, A yra skaičioji aibė, kai visus jos elementus galima sunumeruoti visais natūraliaisiais skaičiais taip , kad skirtingi elementai gautų skirtingus numerius. Aišku, kad skaičiosios aibės galia yra lygi natūraliųjų skaičių aibės galiai. Šios aibės yra begalinės.

Didesnę galią nei natūraliųjų skaičių aibės galia turi aibės, ekvivalenčios atkarpos [0, 1] taškų aibei. Ši aibė yra neskaičioji ir jos galia vadinama kontinuumu.

Raselo paradoksas

Kadangi aibės sąvoka yra neapibrėžiama, tai reikia vengti tokių aibių, kurių elementai nėra visiškai aiškūs. Pavyzdžiui, vargu ar protinga kalbėti apie idėjų aibę, apie vandens lašų stiklinėje aibę ir pan. Taip pat negalima kalbėti ir apie visų aibių aibę, kadangi tokios aibės nagrinėjimas gali duoti prieštaravimą. Šis pavyzdys žinomas kaip Raselo paradoksas. Dažniausiai pateikiami pavyzdžiai aibių, kurios nėra pačios savęs elementais: tai aibės N ,Q, Z ir pan. Tačiau nagrinėjant visų aibių aibę, tai ji yra pati savęs elementas. Raselas siūlo nagrinėti tokią aibę M, kurios elementai yra aibės X, tenkinančios sąlygą X X. Kyla klausimas, ar MIM? Galimas vienas iš dviejų atvejų: arba M M arba MIM. Tarkime, M M. Tada, pagal aibės M apibrėžimą, darome išvadą, kad MIM. Tačiau šiuo atveju M M ir t.t.

Kitas šio paradokso variantas yra barzdaskučio (Gonseto) paradoksas. Barzdaskutys prie savo dirbtuvės durų pakabino tokį užrašą: “čia skutami visi tie, kas patys nesiskuta”. Kyla klausimas, ar pats barzdaskutys gali save skusti? Galimas vienas iš dviejų atvejų: arba gali, arba negali. Jei barzdaskutys negali skustis, t.y. jis pats nesiskuta, tai pagal skelbimą jis gali skustis. Tačiau, jam pradėjus skustis, šis veiksmas prieštarautų skelbimui. Vadinasi, jis negali skustis. Tačiau šiuo atveju pagal skelbimą jis gali skustis ir t.t. Gauname prieštaravimą arba padėtį be išeities.

Pavyzdys PS85

Tegul turime aibes:

,

,

,

,

.

Kurios iš šių aibių yra lygios?

Pirmiausia pastebime, kad aibės B ir D yra lygios. Tiesiog aibė D užrašyta nekorektiškai, jos elementas 0 pakartotas du kartus. Aibė A turi tris skirtingus elementus: 0, 1 ir aibę B, o aibė G – keturis skirtingus elementus: tuščiąją aibę ir aibes , ir . Todėl . O kaip aibė C? Pastebime, kad aibė B yra aibės C elementas, o 0 ir 1 priklauso aibei C kaip aibės B elementai. Taigi, .

Uždaviniai PS85, KM77

Išvardykite šių aibių elementus:

a)     ,

b)    .

Ats: a) , b) .

Nustatykite, ar teisingi šie santykiai:

a) , b) , c) , d) , e) ,
f) , ,g) .

Pateikite tokių aibių A, B, C, D pavyzdžius, kad , , , , .

Patvirtinkite arba paneikite žemiau pateiktus teiginius. Bet kurioms aibėms A, B ir C:

a)     jei ir , tai ,

b)    jei ir , tai ,

c)     jei ir , tai ,

d)    jei ir , tai ,

e)     jei ir ,tai .

Poaibiai

Apibrėžimas. Aibė A yra aibės B poaibis (žymime A B), jei kiekvienas aibės A elementas yra ir aibės B elementas.

Šį apibrėžimą iliustruoja Veno diagramos, parodytos 1.2.1 paveiksle.

1.2.1 pav. Poaibių Veno diagramos

Jei A B ir A B, tai A B. Kitaip tariant, jei kiekvienas aibės A elementas yra ir aibės B elementas, tačiau egzistuoja bent vienas aibės B elementas, kuris nėra aibės A elementas, tai aibė A yra griežtas aibės B poaibis. Šiuo atveju rašome A B. (žr. 1.2.1 pav. b) atvejį). Tokie poaibiai vadinami tikriniais poaibiais. Aibės B poaibiai: tuščioji aibė ir aibė B, vadinami aibės B netikriniais poaibiais.

Poaibių savybės

M, čia M – bet kuri aibė. Kitaip tariant, tuščioji aibė yra kiekvienos aibės poaibis.

Jei A B ir B C, tai A C. Šią savybę iliustruoja Veno diagramos, pavaizduotos 1.2.2 paveiksle.

1.2.2 pav. Veno diagramos, iliustruojančios 2-ąją savybę

Jei A B ir B C, tai A C. Šią savybę iliustruoja 1.2.2 paveikslo b) atvejo Veno diagrama.

Jei A B ir B A, tai A = B. (Žr. 1.2.3 pav.)

1.2.3 pav. Veno diagrama, iliustruojanti 4-tąją savybę

Jei A B ir B C, tai A C. Šią savybę iliustruoja 1.2.2 paveikslo b) ir c) atvejai.

Pavyzdys PS85

Tegul turime aibes:

,

,

,

.

Tada teisingi šie teiginiai:

,

, kadangi , bet ,

,

,

, kadangi , bet ,

, kadangi , bet .

Realiųjų skaičių poaibiai

Tarkime, kad a ir b yra realieji skaičiai ir a < b. Tada žemiau išvardinti realiųjų skaičių aibės poaibiai turi vardus.

Intervalas (atkarpa, atvirasis intervalas). Žymime

.

Segmentas (uždarasis intervalas). Žymime .

Pusiau atvirieji intervalai

,

.

Aibės A visų galimų poaibių aibė

Aibės A visų galimų poaibių aibė žymima P(A). Kitaip tariant . Pavyzdžiui, jei , tai

.

Teorema. Jei , tai .

Įrodymas. Tegul A = . Kiekvienam aibės A poaibiui B priskirkime skaičių (kodą) S_B = a a a_n a_i I , kuris nusakomas taip: a_i = 1, jei a_i I B ir a_i = 0, - priešingu atveju. Aišku, kad kiekvienam aibės A poaibiui atitinka vienas kodas ir atvirkščiai. Tada P(A) elementams atitiks visi n-skilčiai dvejetainiai skaičiai nuo 0 0 … 0 iki 1 1 … 1. Tokių skaičių yra 2ⁿ. Pavyzdžiui, aibės A visi galimi poaibiai bus nusakomi kodais.

Uždaviniai PS85

Išvardykite visus šių aibių poaibius:

a)    

b)   

c)    

d)   

e)    

f)     

Ats: a) , b) , , c) , , , , d) , , , , ,
,, , e) , , , , f)

Duota aibė A = . Pasinaudoję teoremos įrodymu:

a)     sukonstruokite aibės A poaibius, atitinkančius dvejetainių skaičių kodus 0101, 1111, 1001, 1000,0100, 0110, 0111, 0001,

b)    nustatykite dvejetainių skaičių kodus, atitinkančius poaibius
, , ,

Ats: a) , , , , , , , , b) 0010, 0011, 1010, 0000, 0111, 1011, 1110, 1111.

Poaibių generavimo algoritmai

Įvairiuose taikomuosiuose uždaviniuose tenka vienokia ar kitokia tvarka generuoti aibės poaibius. Aptarkime aibės A, turinčios n elementų, poaibių generavimo algoritmus.

Bendra poaibių generavimo algoritmo struktūra

Poaibių, kaip ir kitų kombinatorinių objektų, generavimo algoritmo struktūra yra tokia.

begin

generuoti pradinį poaibį

while “generavimo sąlyga” do

begin

nagrinėti (spausdinti) poaibį;

generuoti poaibį, gretimą išnagrinėtam (atspausdintam) poaibiui;

end

end

Priklausomai nuo pasirinktos poaibių generavimo tvarkos, šiame algoritme turi būti konkretizuoti sakiniai: “generuoti pradinį poaibį”, “generavimo sąlyga”, “poaibis, gretimas išnagrinėtam poaibiui”.

Žemiau aptarsime du poaibių generavimo algoritmus: poaibių generavimo leksikografine didėjimo tvarka algoritmą ir poaibių generavimo taip, kad bet kokie du gretimi poaibiai skirtųsi tik vienu elementu, algoritmą. Kadangi kiekvieną poaibį galime nusakyti dvejetainiu kodu, tai antru būdu sugeneruoti poaibiai vadinami Grėjaus kodais.

Poaibių generavimas leksikografine didėjimo tvarka

Uždavinio formulavimas

Duota:  n – aibės elementų skaičius,

a[1.. n] – aibės A elementai.

Rasti:  generuoti aibės A poaibius leksikografine didėjimo tvarka.

Kaip buvo minėta aukščiau, kiekvieną aibės A poaibį galima nusakyti dvejetainiu kodu b₁, b₂, …, b_n, b_i I . Jei kodo elementas b_i = 1, tai elementas a_i priklauso poaibiui. Tuo būdu poaibį nusakys masyvas b[0.. n]. Aptarkime kodų leksikografinę tvarką. Į kodą galima žiūrėti kaip į vektorių, todėl, aptardami leksikografinę tvarką, naudosime žodį vektorius.

Vektorius x yra leksikografiškai didesnis už 0, (žymime ), jei jo pirmoji nenulinė komponentė yra teigiama.

Vektorius , jei .

Iš vektorių leksikografinės tvarkos išplaukia, kad, jei į kodą žiūrėsime kaip į dvejetainį skaičių, tai kodai sudarys visus n skilčių dvejetainius skaičius, išdėstytus didėjimo tvarka. Pavyzdžiui, jei n = 4, tai kodai, išdėstyti leksikografine didėjimo tvarka, atrodys taip: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011,1100, 1101, 1110, 1111.

Dabar galime konkretizuoti aukščiau išvardintus sakinius.

Pradinio kodo generavimas. .

Gretimo kodo generavimas. Gretimą poaibį nusako kodas – dvejetainis skaičius, vienetu didesnis nei išnagrinėtasis. Vadinasi, masyve b ieškome pirmo iš dešinės elemento, kuris lygus nuliui. Tarkime, kad b_i yra toks elementas. Tada , o .

Generavimo sąlyga. Aišku, kad generavimą baigsime, kai masyvo b pirmojo iš dešinės elemento, lygaus nuliui, indeksas bus lygus 0, t.y. kai , , o .

Žemiau pateikiamas poaibių generavimo leksikografine didėjimo tvarka algoritmas.

begin

for i:= 0 to n do b[i]:= 0;

t:= true;

while t do

begin

for i:= 1 to n do

if b[i] = 1 then spausdinti a[i];

i:=n;

while (i 1) and (b[i] = 1) do

begin

b[i] := 0;

i:= i – 1;

end

if i then t := false

else b[i] := 1;

end

end

Grėjaus kodo generavimo algoritmai

Aptarsime Grėjaus kodų, t.y. poaibių, kai bet kokie du gretimi poaibiai skiriasi tik vienu elementu, generavimo algoritmus. Kadangi Grėjaus kodai plačiai taikomi kodavimo teorijoje, tai 1.4 paragrafe trumpai aptarsime kodavimo teorijos elementus ir Grėjaus kodų taikymą kodavimo uždaviniuose.

Pirmasis algoritmas. Šis algoritmas remiasi aukščiau išnagrinėtu poaibių generavimo leksikografine tvarka algoritmu. Kitaip tariant, nuosekliai generuojant dvejetainius skaičius, jie gali būti perskaičiuoti į Grėjaus kodus.

Tarkime, kad yra poaibio, sugeneruoto pagal aukščiau pateiktą algoritmą, kodas. Tada šis kodas perskaičiuojamas į Grėjaus kodą pagal formulę:

(1.3.1)

čia simbolis žymi operaciją “suma moduliu 2”.

Pavyzdžiui, jei n = 3, tai perskaičiavimą iš dvejetainio kodo į Grėjaus kodą iliustruoja 1.3.1 lentelė.

lentelė. Perskaičiavimas iš dvejetainio kodo į Grėjaus kodą

(1.3.1) formulės teisingumą nesunku pagrįsti taip.

Aišku, kad du iš eilės einantys dvejetainiai skaičiai turės pavidalą

čia “*” žymi simbolį 1 arba 0. Tarkime, kad pirmajame skaičiuje “0” yra
i-tojoje skiltyje, o dešiniau jos yra vienetukai. Aišku, kad “*” pažymėtos skilčių vertės abejuose skaičiuose sutampa.

Pritaikius šiems skaičiams (1.3.1) formulę, pirmojo ir antrojo skaičiaus
i-tosios skiltys bus priešingos: jei pirmojo skaičiaus i-toji skiltis bus 0, tai antrojo – 1 ir atvirkščiai. Abiejų skaičių (i+1)-oji skiltis bus lygi 1, o abiejų skaičių (i+2), (i+3), …, n skiltys bus lygios 0. Aišku, kad abiejų skaičių skilčių nuo 1 iki (i-1) vertės taip pat sutampa. Tuo būdu (1.3.1) formulė dvetainius skaičius perskaičiuoja į Grėjaus kodus.

Pastaba. Pertvarkyta (1.3.1) formulė įgalina perskaičiuoti Grėjaus kodus į dvejetainius skaičius. Tarkime, kad c₁ c₂ … c_n yra Grėjaus kodas, o b₁ b₂ … b_n – jam atitinkantis dvejetainis skaičius. Tada iš (1.3.1) formulės gausime

(1.3.2)

Iš pateikto nagrinėjimo aišku, kad aukščiau pateiktas poaibių generavimo algoritmas tiks Grėjaus kodų generavimui, jei prieš komentarą “Spausdinti poaibį” pagal (1.3.1) formulę apskaičiuosime masyvo c[1..n] elementus.

Antrasis algoritmas

Metodo idėja Jei aibė A turi vieną elementą, tai Grėjaus kodai bus 0 ir 1. Grėjaus kodus aibei, turinčiai du elementus, generuosime remdamiesi Grėjaus kodais aibei, turinčiai vieną elementą. Turėdami Grėjaus kodus aibei, turinčiai (n-1) elementų, generuosime Grėjaus kodus aibei, turinčiai n elementų, tokiu būdu:

prie aibės, turinčios (n-1) elementą, Grėjaus kodų iš dešinės prirašome “0”,

po to prie aibės iš (n-1) elementų Grėjaus kodų, rašomų atvirkščia tvarka, dešinės pusės prirašome “1”.

Tuo būdu gausime:

jei n = 1, tai Grėjaus kodai yra 0, 1;

jei n = 2, tai Grėjaus kodai yra 00, 10, 11, 01;

jei n = 3, tai Grėjaus kodai yra 000, 100, 110, 010, 011, 111, 101, 001

ir t.t.

Pastaba. Pabraukti simboliai yra Grėjaus kodai aibei iš (n-1) elemento.

Kaip matome, metodo idėja yra labai paprasta, tačiau ji neatitinka bendros poaibių generavimo algoritmų schemos: norint generuoti Grėjaus kodus aibei iš n elementų, reikia turėti (n-1) elementų aibės visus Grėjaus kodus. Subtili šio metodo realizacija, tenkinanti bendrą poaibių generavimo algoritmo schemą, pateikta literatūroje [Lip88]. Čia aptarsime šią realizaciją.

Funkcija Q(i), i I N. Q(i) – tai toks didžiausias dvejeto laipsnis, kad yra i daliklis, t.y. .

Pavyzdžiui, Q(3) = 0; Q(4) = 2; Q(5) = 0; Q(6) = 1; Q(8) = 3; Q(12) = 2.

Funkcijos Q(i) savybė. Nesunku pastebėti, kad Q(2^k + m) = Q(2^k – m),
čia 0 m 2^k –1.

Pavyzdžiui, kai k = 2, turėsime

Q(4+0) = Q(4-0) = 2,

Q(4+1) = Q(4-1) = 0,

Q(4+2) = Q(4-2) = 1,

Q(4+3) = Q(4-3) = 0.

Remdamiesi funkcija Q(i) sudarysime Grėjaus kodų generavimo algoritmą pagal aukščiau aprašytą metodą.

Įėjimo duomenys tokie pat, kaip ir algoritmo, generuojančio poaibius leksikografine didėjimo tvarka, t.y.

n – aibės elementų skaičius;

a[1.. n] – aibės A elementai.

Poaibius (Grėjaus kodus) talpinsime į masyvą b[1.. n]. Kintamasis i žymi Grėjaus kodo eilės numerį.

begin

for i := 1 to n do b[i] := 0;

i

t := true;

while t do

begin

for k := 1 to n do

if  b[k] =1 then nagrinėti (spausdinti) a_k;

i := i + 1;

p

j := i;

while j mod 2 = 0 then

begin

p := p+1;

j := j div 2;

end

if p <= n then

b[p] := 1 – b[p]

else

t := false;

end

end

1.3.2 lentelėje parodytas algoritmo veikimas, kai n = 3

1.3.2 lentelė. Grėjaus kodų generavimas, kai n

1.3.2 lentelėje laužtiniais skliaustais išryškinti Grėjaus kodai aibei iš vieno elemento, o riestiniais skliaustais – Grėjaus kodai aibei iš 2-jų elementų. Šie išryškinimai vaizdžiai parodo, kad dėl aukščiau aptartos funkcijos Q(i) savybės, generuojant Grėjaus kodus aibei iš n elementų, kai i 2^n-1 – 1, generuojami Grėjaus kodai iš (n – 1) elementų. Šiems kodams pozicija b_n yra lygi nuliui. Kai i = 2^n-1 – 1, b_n įgauna reikšmę 1 ir toliau, didinant i reikšmę, atvirkščia tvarka generuojami Grėjaus kodai aibei iš (n – 1) elemento. Kitaip tariant, pateiktas algoritmas tikrai realizuoja aukščiau aptartą Grėjaus kodų generavimo metodą.

Pastaba. Pateiktas algoritmas generuos Grėjaus kodus nuo bet kokio (nebūtinai nulinio) pradinio kodo.

Trečiasis Grėjaus kodo generavimo algoritmas išnagrinėtas 3.4.1 paragrafe.

Grėjaus kodų taikymo pavyzdžiai

Kaip minėjome, Grėjaus kodai dažniausiai naudojami sprendžiant kodavimo uždavinius, todėl pirmiausia aptarsime kodavimo teorijos elementus.

Kodavimo teorijos elementai

Kodavimas – tai procesas, kurio metu pradinė informacija keičiama kokiu nors jos atitikmeniu – kodu. Priežastys, dėl kurių yra reikalingas kodavimas, gana įvairios. Pavyzdžiui, žmogus savo kasdienėje veikloje kiekybiniam įverčiui (skaičiams) išreikšti paprastai naudojasi dešimtaine skaičiavimo sistema. Absoliuti dauguma pasaulyje šiuo metu naudojamų kompiuterių dėl savo konstruktyvinių ypatybių naudoja dvejetainę skaičiavimo sistemą. Be to, išaugus kompiuterių galimybėms, jie labai plačiai naudojami ne tik skaitinės, bet ir tekstinės informacijos apdorojimui. Tuo pačiu neišvengiamai atsiranda būtinybė dešimtainius skaičius bei tekstinę informaciją koduoti vienetukų ir nulių sekomis, nes toks informacijos pateikimo būdas yra labiausiai priimtinas kompiuteriuose dėl jų vidinės sandaros. Kitas svarbus kodavimo atvejis – informacijos perdavimas. Informacijos perdavimo terpė praktiškai niekada nebūna ideali, ir perduodamą informaciją paprastai daugiau ar mažiau veikia triukšmai. Kaip priemonė šio žalingo triukšmų poveikio neutralizavimui arba bent jau sumažinimui naudojami specialūs kodavimo būdai, kurių esmę sudaro klaidas aptinkančių ar net jas ištaisančių kodų panaudojimas.

1.3.3 lentelėje pateikti įvairūs dešimtainių skaičių kodavimo būdai: dvejetainis kodavimas, BCD kodavimas (nuo “Binary Coded Decimal” – dvejetainiu būdu užkoduotas dešimtainis skaičius), Grėjaus kodas, kodas su pertekliumi “3”, romėniškas skaičiaus kodavimas.

Trumpai aptarsime kiekvieną iš šių kodų.

Dvejetainis skaičių kodas – pats natūraliausias kompiuterio sandaros požiūriu kodas, naudojamas kompiuteriuose atliekant aritmetinius skaičiavimus.

BCD kodas – tarpinis kodas tarp vaizdavimo kompiuteryje ir žmogui įprasto vaizdavimo. Kiekvienas dešimtainis skaitmuo užkoduotas bitų ketveriuke (kaip kad įprasta kompiuteryje), tačiau patys skaičiai visgi dešimtainiai (kaip įprasta žmogui) ir patys veiksmai su tokiais skaičiais skiriasi nuo dvejetainių skaičių aritmetikos.

Šešioliktainis kodas taip pat buvo pradėtas naudoti kaip tarpinis kodas grandyje “žmogus / kompiuteris”. Jei poroje “dvejetainis kodas / BCD” pagrindas yra dešimtainis skaičius, kurio kiekvienam dešimtainiui skaitmeniui užkoduoti naudojama keturių bitų seka (nuo 0000 iki 1001), tai poroje “dvejetainis skaičius / šešioliktainis skaičius” pagrindas yra keturių dvejetainių skaitmenų dvejetainis skaičius, kurio kodavimui naudojamas vienas iš 16-kos šešioliktainės sistemos skaitmenų nuo 0 iki F. Šešioliktainis kodas kaip tarpinis kartais naudojamas projektuojant kompiuterių blokus.

1.3.3 lentelė. Dešimtainių skaičių kodavimo būdai

Kodas su pertekliumi “3” kartais naudojamas kompiuteryje aritmetinių operacijų realizacijos efektyvumui padidinti.

Grėjaus kodo taikymas, skirtingai nuo aukščiau aprašytų, dominuoja ne kompiuterio aritmetinių operacijų realizavimui, bet tokiose srityse kaip kompiuterių įrangos projektavimas, taip pat kombinatorinių uždavinių sprendimo algoritmų sudarymas. Detaliau panagrinėsime šiuos taikymus.

Apibrėžimas. Hemingo atstumu tarp dviejų kodo kombinacijų vadinamas skaičius pozicijų, kuriose viena kombinacija skiriasi nuo kitos.

Akivaizdu, kad Grėjaus kodas turi tą savybę, kad Hemingo atstumas tarp bet kurių gretimų Grėjaus kodo kombinacijų yra lygus 1. Dar viena Grėjaus kodo savybė yra tai, kad jis yra ciklinis kodas. Pavyzdžiui, jei n = 3, tai

Tai, kad Hemingo atstumas tarp bet kurių dviejų gretimų Grėjaus kodo kombinacijų yra lygus 1, leidžia efektyviai panaudoti Grėjaus kodą spręsti įvairius kombinatorikos uždavinius.

Baigtinio automato padėčių kodavimas Grėjaus kodo kombinacijomis

Sakykime, kad automato perėjimų grafe yra fragmentas (žiūr. 1.4.1 pav.).

1.4.1 pav. Automato perėjimo grafo fragmentas

čia P1 ir P2 – automato būviai. Tegu šie du būviai yra užkoduoti kodais 001 ir 100 atitinkamai. Tegu šias tris skiltis atitinka trys būvių registro trigeriai T1, T2 ir T3. Perėjimas S1 S2 reiškia, kad mes turėsime pervesti trigerį T1 iš “0” į “1”, o trigerį T3 – iš “1” į “0”. Paprastai dėl skirtingų elektroninių kelių trigerių perjungimo shemos grandinėse perjungimo signalo vėlinimai šiek tiek skiriasi. Tuo pačiu, pereinant iš P1 į P2 automatas paklius visų pirma į kažkokį tarpinį būvį T^* (pvz. 101 – T1 jau persijungęs, T3 – dar ne. Tai reiškia, kad iš šio būvio (T^* 101) automatas gali nepereiti į T2 (kas būtų reikalinga pagal automato funkcionavimo algoritmą), bet į kažkokią kitą padėtį. Šis ypatumas, susijęs su automato technine realizacija (nevienodais įvairių šakų elektrinės schemos vėlinimais) yra vadinamas “automato lenktynėmis”.

Akivaizdu, kad šio ydingo reiškinio galima išvengti, jei du gretimi automato būviai, tarp kurių yra perėjimas, būtų užkoduoti Grėjaus kodo pagalba.

Bulio funkcijų (BF) Karno diagramos konstravimas

Bulio funkcijų vaizdavimas Karno diagramų pagalba visų pirma yra naudingas BF minimizavimui. Du nagrinėjamos minimizuojamos BF mintermus galima apjungti į vieną termą, jei tuos mintermus atitinkantys vienetukai yra gretimuose Karno diagramos langeliuose. Karno diagramai sukonstruoti galima panaudoti Grėjaus kodo kombinacijas.

Kadangi Hemingo atstumas tarp bet kurių dviejų Grėjaus kodų yra lygus 1, tai atitinkamai bet kuriuos du gretimus BF Karno diagramos langelius bus galima apjungti (žiūr. 1.4.2 pav.).

1.4.2 pav. Karno diagrama

Veiksmai su aibėmis (aibių algebra)

Aptarsime veiksmus su aibėmis.

Pirmiausia apibrėšime universaliosios aibės sąvoką.

Tarkime, kad visos konkrečiu atveju nagrinėjamos aibės yra kažkurios aibės U poaibiai. Tada aibė U vadinama universaliąja aibe.

Pavyzdžiui, jei nagrinėjame realiųjų skaičių poaibius, tai jų atžvilgiu . Jei nagrinėjame skaičiavimo uždavinių, sprendžiamų kompiuteriu, rezultatus, tai kompiuterio įsimenamų realiųjų skaičių aibė yra U.

Universalioji aibė Veno diagrama paprastai vaizduojama stačiakampiu (žr. 1.5.1 pav.)

1.5.1 pav. Universaliosios aibės Veno diagrama

Aibių A ir B sąjunga. Aibių A ir B sąjunga yra aibė C, kurią sudaro elementai, priklausantys aibei A arba aibei B. Žymime

(žr. 1.5.2 pav.).

1.5.2 pav. Aibių A ir B sąjungos Veno diagrama

Aibių A ir B sankirta. Aibių A ir B sankirta yra aibė C, kurią sudaro elementai, priklausantys ir aibei A ir aibei B. Žymime

(žr. 1.5.3 pav.).

Jei , tai sakome, kad aibės A ir B nesusikertančios.

1.5.3 pav. Aibių A ir B sankirtos Veno diagrama

Aibių A ir B skirtumas. Aibių A ir B skirtumas yra aibė C, kurią sudaro aibės A elementai, nepriklausantys aibei B. Žymime

(žr. 1.5.4 pav.).

1.5.4 pav. Aibių A ir B skirtumo Veno diagrama

Aibės A papildinys. Aibės A papildinys yra aibė, papildanti aibę A iki universaliosios aibės. Žymime

(žr. 1.5.5 pav.).

1.5.5 pav. Aibės A papildinio Veno diagrama

Pavyzdžiai PS85

Duotoms aibėms U = N, A = , P = ir T = rasti A , P , A P, A – P, P – A, A T ir A T

Aibė A susideda iš sveikųjų teigiamų nelyginių skaičių, todėl jos papildinys A susideda iš sveikųjų teigiamų lyginių skaičių: A

Aibė P yra pirminių skaičių aibė, todėl P

Aibė A P yra nelyginių pirminių skaičių aibė:

A P = = P – .

Sveikųjų teigiamų nelyginių skaičių, kurie nėra pirminiai, aibė yra

A – P = .

Aibė P – A susideda iš pirminių lyginių skaičių, vadinasi P – A = .

Aibė T yra kartotinių trims teigiamų skaičių aibė, todėl A T susideda iš tų aibės T elementų, kurie yra lyginiai: A T = .

Pagaliau, A T apima tuos sveikuosius teigiamus skaičius, kurie yra arba nelyginiai, arba nekartotiniai trims:

A T

Pastebėsime, kad A T = (A T)

Duotos aibės U = , A = , B = ir
C = . Rasti ir palyginti tokias aibių poras:

a)     A (B C) ir (A B) (A C),

b)    A (B C) ir (A B) (A C),

c)     (A B) ir A B

d)    (A B) ir A B

a) atveju randame, kad:

A (B C) = A

(A B) (A C) =

Vadinasi, A (B C) = (A B) (A C).

Analogiškai išsprendę b) atvejį, rasime, kad

A (B C) = (A B) (A C) = .

c) atveju gauname:

(A B)

A B

Šiuo atveju aibės taip pat yra lygios.

Ir, analogiškai, d) atveju gauname

(A B) = A B

Uždavinys PS85

Duotoms aibėms U = , A = ir B = rasti A B, A B, A – B, B – A, A ir B

Ats: A B = , A B = , A – B = , B – A = , A = , B

Aibių A ir B simetrinis skirtumas arba A ir B suma moduliu . Aibių A ir B simetrinis skirtumas yra aibė C, kurią sudaro elementai, priklausantys arba tik aibei A, arba tik aibei B. Žymime .

(žr. 1.5.6 a) pav.).

Aibių simetrinio skirtumo arba sumos moduliu 2 operacija apibendrinama daugiau nei dviem aibėm.

Aibė B yra aibių suma moduliu 2 (simetriniu skirtumu), jei

(žr. 1.5.6 b) pav.).

1.5.6 pav. Aibių A ir B simetrinio skirtumo Veno diagrama

Uždavinys

Tarkime, kad X ir Y yra aibės. Kokie bus X ir Y turiniai po žemiau pateiktų veiksmų atlikimo?

;

;

.

Ats: Aibių X ir Y turiniai bus sukeisti vietomis.

Aibių A ir B Dekarto sandauga. Aibių A ir B Dekarto sandauga yra aibė C, kurią sudaro visos galimos poros (a, b), kai pirmasis poros elementas a I A, o antrasis poros elementas b I B. Žymime

.

Vaizdžiai šis veiksmas parodytas 1.5.7 paveiksle.

1.5.7 pav. Aibių A ir B Dekarto sandauga

Pavyzdys

Duotos aibės A = ir B = .

Rasti A B ir B A.

A B = ,

B A = .

Reikia pastebėti, kad A B B A.

Dekarto sandauga gali būti apibendrinta ir daugiau nei dviem aibėm. Tarkime, yra aibės. Tada šių aibių Dekarto sandauga yra aibė A, kurią sudaro visi galimi vektoriai , čia . Žymime

Dekarto sandauga yra patogi priemonė aprašyti erdves. Pavyzdžiui R² (čia R – reliųjų skaičių aibė) žymi plokštumą, R³– trimatę erdvę, Rⁿ – n-matę erdvę.

Pavyzdys

Duota A₁ = A₂ = A₃ = . Rasti A₁ A₂ A₃.

Sprendinys: A₁ A₂ A₃ =

Aibės A išskaidymas. Aibės , tenkinančios žemiau išvardintas savybes

,

,

vadinamos aibės A išskaidymu (žr. 1.5.8 pav.).

1.5.8 pav. Aibės A išskaidymas, kai n = 3

Sąjungos ir sankirtos operacijų apibendrinimas

Aukščiau sąjunga A B ir sankirta A B buvo apibrėžtos dviems aibėms A ir B. Šias sąvokas praplėsime bet kokiam aibių kiekiui n. Tarkim, kad aibės yra universalios aibės U poaibiai.

Aibių sąjunga. Aibių sąjunga susideda iš elementų, priklausančių bent vienai aibei , ir žymima :

.

Aibių sankirta. Aibių sankirta susideda iš elementų, priklausančių visoms aibėms , ir žymima :

.

Teorema. Duotos aibės . Tuomet

jei , tai ,

jei , tai .

Aibių algebros tapatybės

Tarkime, kad aibės A, B, ir C yra universaliosios aibės U poaibiai. Tada sąjungos, sankirtos ir papildymo operacijos tenkina žemiau išvardintas tapatybes (dėsnius):

Komutatyvumo dėsnį:

a)     ,

b)    .

Asociatyvumo dėsnį:

a)     ,

b)    .

Distributyvumo dėsnį:

a)     ,

b)    .

De Morgano dėsnius

a)     ,

b)    .

Teorema (Išplėstinis De Morgano dėsnis). Tegu . Tuomet

,

.

a)     ,

b)    ,

c)     .

Apibendrintuosius De Morgano dėsnius:

a)     ,

b)    .

Čia nepateikiame šių dėsnių formalių įrodymų. Juos nesunku patikrinti naudojant Veno diagramas.

Uždaviniai

Duotos aibės: U = Z, A = ,
B = , C = . Rasti:

a)     A B,

b)    A – C,

c)     C – A,

d)    (A B) C.

Ats: a) , b) , c) , d) C.

Tegul A = , B = ir C = .Rasti šias aibes:

a)     A B,

b)    B C,

c)     A B C,

d)    (A B) C.

Ats: a) , b) ,
c) , d) .

Tegul A ir B yra universalios aibės U netušti poaibiai.

a)     Kokioms sąlygoms esant A B = B A?

b)    Kokioms sąlygoms esant aibė (A B) (B A) yra tuščioji?

Ats: a) A = B, b) A B =

Aibės galia ir jos apskaičiavimas

Aibės galia. Baigtinės aibės A galia vadinamas jos elementų skaičius n(A). Kitaip aibės galia žymima |A|.

Tuščioji aibė yra vienintelė aibė, kurios elementų skaičius lygus nuliui.

Nesusikertančios aibės. Dvi aibės A ir B vadinamos nesusikertančiomis, jeigu . Apibendrinus, jei yra aibės ir visiems i ir j, , tai sakome, kad šios aibės yra poromis nesusikertančios. Taip pat sakome, kad yra poromis nesusikertančių aibių rinkinys.

Pavyzdys

Tegul turime aibes , , , ir . Tada aibės A ir D yra nesusikertančios, o yra poromis nesusikertančių aibių rinkinys.

Pastebėsime, kad aibės A ir B šiame pavyzdyje nėra nesusikertančios, bet ir yra nesusikertančios ir kad .

Adityvumo dėsnis. Jei aibės A ir B yra nesusikertančios, tai

.

Apibendrinus, jei yra poromis nesusikertančios aibės, tai

.

Taip pat pastebėsime, kad

ir

bet kuriam universaliosios aibės U poaibiui A.

1 teorema. Bet kuriems universaliosios aibės U poaibiams A ir B aibės , ir yra poromis nesusikertančios ir

.

2 teorema. Bet kuriems universaliosios aibės U poaibiams A ir B

.

Įrodymas. Iš formulės gauname, kad

.

Analogiškai,

.

Pasinaudoję šiomis formulėmis ir aukščiau pateikta teorema, gauname, kad

.

Pavyzdys

Gaminys gali turėti dviejų tipų defektus: 1-ojo ir 2-ojo. Buvo patikrinta 100 gaminių ir nustatyta, kad penkiolika gaminių turėjo 1-ojo tipo defektą, dešimt – 2-ojo tipo defektą, o septyni – abiejų tipų defektus. Kiek gaminių buvo brokuoti iš viso?

Tegul A yra aibė gaminių, turinčių 1-ojo tipo defektą, B – aibė gaminių, turinčių 2-ojo tipo defektą. Duota, kad , ir . Mums reikia suskaičiuoti , t.y. gaminių, turinčių abiejų tipų defektus, skaičių. Pasinaudoję teorema, gauname:

.

Taigi, brokuotų gaminių skaičius – 18.

3 teorema. Tegul A, B ir C yra baigtiniai universalios aibės U poaibiai. Tada

Pasinaudoję aukščiau pateikta teorema, gauname:

Pavyzdys PS85

Draudimo kompanija skirsto klijentus pagal amžių, lytį ir šeimyninę padėtį. Ištyrus 500 apdraustųjų duomenis, nustatyta, kad:

350 – susituokę,

240 – vyresni negu 25 metų,

230 – susituokę vyrai,

110 – susituokę, vyresni negu 25 metų,

100 – vyrai, vyresni negu 25 metų,

40 – susituokę vyrai, vyresni negu 25 metų,

10 – vienišos moterys, vyresnės negu 25 metų.

Rasti apsidraudusių vyrų skaičių.

Tegul A – apdraustųjų vyrų aibė, B – susituokusių apdraustųjų aibė, C – vyresnių negu 25 metai apdraustųjų aibė. Duota, kad , todėl

Iš 3-iosios teoremos turime:

Todėl

,

.

Uždaviniai

Buvo patikrinta 100 gaminių. Dešimt iš jų turėjo A tipo defektą, aštuoni – B tipo defektą ir 85 gaminiai buvo be defektų. Keli gaminiai iš 100 turėjo abiejų tipų defektus?

Informatikos fakultete mokosi 225 baigiamojo kurso studentai. 100 studentų pasirinko modulį CS260, 75– modulį CS360, 50– modulį CS450, septyni studentai pasirinko abu modulius – CS260 ir CS360, keturi – CS260 ir CS450, trisdešimt vienas – CS360 ir CS450 ir vienas studentas pasirinko visus tris modulius. Kiek studentų nepasirinko nė vieno iš šių trijų modulių?

Ats: 1) 3, 2) 41.