Tükeldused: Milliste omadustega relatsioon on ekvivalentsisuhe? Binaarushet ehk relatsiooni nimetatakse ekvivalentsisuhteks, kui ta on refleksiivne, sümmeetriline ja transitiivne. Mis on ekvivalentsiklass? Ekvivalentsisuhte alushulga sellist osahulka, mille kõik elemendid on omavahel relatsioonis, nimetatakse ekvivalentsiklassiks. Mis on hulga tükeldus? Hulga tükeldus on selle hulga mittelõikuvate osahulkade hulk, millel on kindlat omadused. Millest tükeldus koosneb? Tükeldus kui hulkade hulga elementideks ehk mittelõikuvateks osahulkadeks on ekvivalentsisuhte kõik ekvivalentsiklassid. Mis on tükelduse plokk?
NÄITEID VEKTORRUUMIDEST Teoreem: Hulk Rn on vektorruum üle reaalarvude hulga R. See vektorruum on aritmeetiline ruum ja selle elemendid on aritmeetilised vektorid. Seotud vektor – suunatud sirglõik, mille algus- ehk rakenduspunkt on fikseeritud. Geomeetriline vektor – suunatud sirglõikude hulga ühepikkuste ja sama suunaga sirglõikude ekvivalentsiklass (G). Kõik samasuunalised ja ühepikkused lõigud esindavad üht ja sama geomeetrilist vektorit. ⃗a ⃗b ⃗a DEF: Geomeetriliste vektorite ja summa on vektor, mille alguspunkt on vektori ⃗b ⃗b
L või ei kuulu sellesse. HL on ekvivalentsiseos, kuna xzHxz, xzHyz <=> yzHxz, xzHwz AND wzHyz => xzHyz. Myhill ja Nerode väitsid, et keel on regulaarne parajasti siis, kui seose H ekvivalentsiklasside hulk on lõplik. Tarvilikkuse tõestus: Moodustame keelt L aktsepteeriva lõpliku automaadi M = (,Q,delta,Q0,F). Moodustame hulgad: R0i = {x | x on string, (x,qo) * (e,qi), q0 on algolek, qi on olek} Seose H ekvivalentsiklass on esitatav ühendina: Ck = R0i1 U ... U R0ik Iga kahe sõna x kuulub R0i ja y kuulub R0i korral masin kas aktsepteerib neid sõnu korraga või ei aktsepteeri tuleneb masina definitsioonist. Sõnu xz ja yz aktseopteerib või ei aktsepteeri ta samuti korraga kuna alamsõna analüüs algab samast olekust ning lõpeb samas. R0i ei pruugi kokku langeda ekvivalentsiklassiga, kuna ka mõnest teisest olekust qj lähtudes võib automaat samu sõnu aktsepteerida. Seega on
selline, et xHLy kehtib parajasti siis, kui iga z ∈ Σ* korral kehtib xz ∈ L yz ∈ L (iga suvalise z lisamisel x ja y sappa, kuuluvad saadud xz ja yz mõlemad keelde L või ei kuulu mõlemad). Teoreem: Keel L on regulaarne parajasti siis, kui seose HL ekvivalentsiklasside hulk on lõplik. T: (tarvilikkus) Kui keel L on regulaarne, leidub teda aktsepteeriv lõplik automaat M = (Q , Σ, δ, q0, F). Olgu R0i ⊆ Σ* sõnede hulk, mis viib automaadi M lähteolekust q0 olekusse qi. Seose HL ekvivalentsiklass on lõplik ühend Cl = R0i1 ∪ R0i2 ∪ . . . ∪ R0il. (piisavus) Olgu HL ekvivalentsiklassid C0,…,Cm. Teeme lõpliku automaadi olekute hulgaga Q = {C0…Cm}: Valime algolekuks klassi C0, mis sisaldab ε-d. Olgu lõppolek Ck ekvivalentsiklass, mis ühtib keelega L ehk kui x ∈ Ck ja x ∈ L, siis kui y ∈ Ck y ∈ L. Kui x ∈ Ci ja y ∈ Ci, st xz ∈ L yz ∈ L, siis kuuluvad sõned xa ja ya ka ühte klassi Cj
· Osaline mitterange järjestussuhe ( ) on refleksiivne, antisümmeetriline ja transitiivne.
· Osaline range järjestussuhe ( < ) on antirefleksiivne, antisümmeetriline ja transitiivne.
· Lineaarne järjestussuhe - ( a,bA) [ (a
sisaldab suhet R.
Osaline mitterange järjestussuhe ( ) on refleksiivne, antisümmeetriline ja transitiivne.
Osaline range järjestussuhe ( < ) on antirefleksiivne, antisümmeetriline ja transitiivne.
Lineaarne järjestussuhe - ( a,bA) [ (a
täisarvude hulgal määratud relatsioon R, mis kehtib kahe täisarvu a ja b puhul parajasti siis, kui need arvud on annavad arvuga n jagades sama jäägi. b. Defineerime hulga X iga elemendi x X jaoks tema ekvivalentsiklassi relatsiooni R järgi: [x]R = {y X | xRy}. Näide: Olgu X lausemuutujatest A ja B moodustatud lausearvutuse valemite hulk ja FRK tähendagu valemite F ja G samaväärsust. Siis valemi F ekvivalentsiklass on kõigi temaga samaväärsete ainult muutujaid A ja B sisaldavate valemite hulk. Selgitasime välja, et hulk X jaguneb 16 ekvivalentsiklassiks. c. Teoreem hulga jaotumisest ekvivalentsiklassideks: Kui R on hulgal X defineeritud ekvivalentsirelatsioon, siis kehtib: i. Kui kehtib xRy, siis [x]R = [y]R, ii. Kui xRy ei kehti, siis [x]R [y]R = , iii. Ekvivalentsiklasside ühend on hulk X. Tõestus.
Relatsiooni transitiivne sulund on vähima paaridearvuga transitiivne relatsioon, mis sisaldab endas alamhulgana relatsiooni. 30. Millega osutub võrdseks transitiivse relatsiooni transitiivne sulund? Transitiivse relatsiooni transitiivne sulund on võrdne transitiivse relatsiooni endaga. Tükeldused 1. Milliste omadustega relatsioon on ekvivalentsisuhe? Relatsiooni nimetatakse ekvivalentsisuhteks, kui ta on refleksiivne, sümmeetriline ja transitiivne. 2. Mis on ekvivalentsiklass? Ekvivalentsiklassiks nimetatakse ekvivalentsisuhte sellist osahulka, mille kõik elemendid on omavahel relatsioonis. 3. Mis on hulga tükeldus? Hulga tükeldus on selle hulga mittelõikuvate osahulkade hulk, millel on kindlad omadused. 4. Millest tükeldus koosneb? Tükelduse elementideks on ekvivalentsisuhte kõik ekvivalentsiklassid. 5. Mis on tükelduse plokk (ehk tükelduse tükk)? Tükelduse koosseisu kuuluvaid ekvivalentsiklasse
samasuunalised OMADUSED: 1) Refleksiivsus - iga seotud vektor on ekvivalentne iseendaga 2) Transitiivsus - Kui esimene seotud vektor on ekvivalentne teisega ning teine kolmandaga siis on ka esimene ja kolmas seotud vektor omavahel ekvivalentsed. 3) Sümmeetria - Kui üks seotud vektor on ekvivalentne teise seotud vektoriga, siis on ka teine ekvivalentne esimesega. Ekvivalentsiklass - Seotud vektoriga AB E 0 ekvivalentsete seotud vektorite hulka { : ~ AB } nimetame ekvivalentsiklassiks moodustajaga AB . Ekvivalentsiklassi moodustajaga AB tähistame abil. Seega := { : ~ AB }. Vabavektor ehk vektor Hulga E elemente, täpsemalt hulga ekvivalentsiklasse, nimetame edaspidi vabavektoriteks ehk lühidalt vektoriteks. Nullvektor - Vektorite summa .
o Võrdus on ekvivalentsirelatsioon, võrratused ja mittevõrdus ei ole. Ekivalentsiklassid o DEF: Hulgal X määratud ekvivalents jagab selle hulga klassideks, seejuures on klassid omavahel lõikumatud ja üheskoos katavad nad kogu hulga X. Ühte klassi kuuluvad elemendid on kõik omavahel ekvivalentsed. o Olgu X lausemuutujatest A ja B moodustatud lausearvutuse valemite hulk ja FRG tähendagu valemite F ja G samaväärsust. Siis valemi F ekvivalentsiklass on kõigi temaga samaväärsete ainult muutujaid A ja B sisaldavate valemite hulk. Selgitasime välja, et hulk X jaguneb 16 ekvivalentsiklassiks. Teoreem hulga jaotumisest ekivalentsiklassideks o Teoreem. Kui R on hulgal X defineeritud ekvivalentsirelatsioon, siis kehtib: 1) Kui xRy kehtib, siis [x ] R=[ y ]R , 2) Kui xRy ei kehti, siis [x ]R ∩ [ y ] R=∅ , 3) Ekvivalentsiklasside ühend on hulk X .
annaabi.ee 
