Diskreetse matemaatika elemendid (0)

Diskreetse matemaatika elemendid 2013/2014
LAUSEARVUTUS. TÕESTUSED.

1. Lausearvutuse lausetele esitatavad tingimused. [1]

• Välistatud kolmanda seadus. Iga lause on kas tõene või väär.
  
• Mittevasturääkivuse seadus. Ükski lause ei saa olla nii tõene kui ka väär.
  
• Nende nõuete põhjal kuuluvad vaadeldavate hulka ainult nii sugused laused , mis midagi väidavad, kusjuures sellel väitel on olemas ühene tõeväärtus.
  
• . Välistatud kolmanda seaduse nõudel jäävad kõrvale kõik küsilaused ja paljud hüüdlaused, samuti kõik käsud ning mõttetud sõnaühendid. Mitte-vasturääkivuse seadus välistab mitmesugused paradoksid, näiteks „See lause siin on väär“, ja muud taolised väited, mille tõeväärtust pole võimalik üheselt määrata.
  
• Tehte tulemuseks saadud lause tõeväärtus sõltub ainult komponentlausete tõeväärtustest.
  

2. Lausearvutuse tehted . Tehete järjekord . Lausearvutuse valem. [1]

Tehted

• Eitus (märk ¬). Igapäevakeeles väljendab eitus lause mittekehtimist, näiteks „Lehis ei
  

ole okaspuu “. Selle lause võib kirja panna valemiga ¬A, kus A = „Lehis on okaspuu“.

• Konjunktsioon (märk &) tähendab seost „ja“. Näiteks „Puhub tuul ja sajab vihma“ on
  

valemkujul A & B.

• Disjunktsioon (märk ∨) väljendab seost „või“. Näiteks „ Helen laulab või Mart laulab“
  

on valemkujul A ∨ B. Sidesõna „või“ kasutatakse siin mittevälistavas tähenduses: „Kas
A või B või mõlemad“. Igapäevases keeles on käibel ka välistav „või“: „Kas A või B,
aga mitte mõlemad“, näiteks „Ma külvan põllule rukist või panen põllule kartulid“.
Disjunktsiooni all mõistame mittevälistavat „võid“.

• Implikatsioon (märk →) väljendab tingimuslikku konstruktsiooni „kui . . . , siis . . . “.
  

Näiteks „Kui Sven terve aasta korralikult õpib, siis suudab ta kevadel eksamid hõlpsasti
ära teha“ või „Kui kehtib teoreem P, siis kehtib teoreem Q“. Mõlemad laused võib kirja
panna valemiga A → B.

• Ekvivalents (märk ↔) tähendab matemaatikas sagedasti kasutatavat seost „ parajasti
  

siis, kui“ ehk „siis ja ainult siis, kui“. Näiteks lause „hulk X on kinnine parajasti siis, kui
X ühtib oma sulundiga“ on valemkujul A ↔ B.
Tehete järjekord

• ¬, &, ∨, →, ↔
  
• vasakassotsiatiivsus: kui mitme liikme konjuktsioonis või disjunktsioonis sooritatakse
  

tehteid vasakult paremale, siis võib tehete järjekorda täpsustavatest sulgudest loobuda

• Valemi välimised sulud võib ära jätta
  

Lausearvutuse valem
DEF: Lausearvutuse valemid on parajasti need, mida saab koostada alltoodud reeglite abil:
○ iga lausemuutuja on lausearvutuse valem
○ kui F on lausearvutuse valem, siis ka ¬F on lausearvutuse valem
○ kui F ja G on lausearvutuse valemid, siis ka (F & G), (F ∨ G), (F → G) ja (F ↔ G) on
lausearvutuse valemid

3. Väärtustus . Tõeväärtustabel . Samaselt tõene valem. Samaselt väär valem. Kehtestatav valem. Nende omaduste kontrollimine. Seosed valemiklasside vahel. [1]

Väärtustus:

• Juhul, kui vaatluse all on korraga hulk lausemuutujaid ja me omistame tõeväärtuse
  

igale muutujale, siis nimetatakse sellist tõeväärtuste komplekti väärtustuseks. N: Olgu
muutujatekomplekt A, B, C, siis nende üks võimalik väärtustus on A=1, B=0, C=1 ehk (1,0,1)
Tõeväärtustabel:

• Tehete toimet võib ülevaatlikumalt kirjeldada tõeväärtustabeliga, mille vasakus osas on valemi argumentide kõikvõimalikud väärtused, paremas osas aga tehete tulemused.
  

Samaselt tõene valem:

• Lausearvutuse valemit F nimetatakse samaselt tõeseks, kui ta on igal väärtusel tõene.
  
• tautoloogia, loogiliselt tõene valem N: A ∨ ¬A
  

Samaselt väär valem:

• Lausearvutuse valemit F nimetatakse samaselt vääraks, kui ta on igal väärtusel väär.
  
• kontradiktsioon, loogiliselt väär valem N: A & ¬A
  

Kehtestav valem:

• Laussearvutuse valemit F nimetatakse kehtestatavaks, kui ta on vähemalt ühel väärtusel
  

tõene.
Nende omaduste kontrollimine:

• Valemi omaduste tuvastamisel tuleb tüüpiliselt otsustada, kas leidub väärtustus, millel valem on tõene, või väärtustus, millel valem on väär. Alati saab seda küsimust lahendada tõeväärtustabeliga, kuid mõnikord võib kiiremini sihile jõuda valemi struktuuri analüüsides. Näiteks kui on vaja kindlaks teha, kas etteantud valem saab olla mingil väärtustusel tõene, siis uurime kõigepealt , millised peavad olema valemi peatehte poolte tõeväärtused , et valem oleks tõene, seejärel püüame leida väiksemate komponentide tõeväärtused, siis omakorda veel väiksemate omad jne, liikudes valemi struktuuris järk-järgult üha sügavamale. Kui sellise analüüsi käigus satume alati vastuolule, siis valem ühelgi väärtustusel tõene ei ole ning on järelikult samaselt väär. Kui aga jõuame ilma vastuolu kohtamata välja lausemuutujateni, siis saame kätte väärtustuse, millel valem on tõene.
  
• Tõestuspuu. Puu tipuks on uuritav valem koos kontrollitava tõeväärtusega. Kui oleme kindlaks teinud valemi mingi osa tõeväärtuse, siis kirjutame tulemuse valemi alla, selle alla omakorda valemi osa analüüsimisel saadud tulemuse jne. Kui osutub, et mingil sammul on valemi osadel mitu sobivat varianti tõeväärtusi, siis jaguneb analüüs sellel sammul harudeks , mida jätkatakse üksteisest sõltumatult.
  

Seosed valemiklasside vahel:

• Teoreem 1: Valem F on samaselt tõene parajasti siis, kui tema eitus ¬F on samaselt
  

väär.
Tõestus. Andes valemis F esinevatele lausemuutujatele suvalise väärtustuse, näeme, et
valemite F ja ¬F tõeväärtused on vastupidised. Järelikult kui F on igal väärtustusel
tõene, siis ¬F on igal väärtustusel väär ja ümberpöördult.

• Teoreem 2: Valem F on kehtestatav parajasti siis, kui tema eitus ¬F ei ole samaselt tõene.
  

Tõestus. Kui F on kehtestatav, siis väärtustusel, kus F on tõene, on valem ¬F väär ja ei saa seetõttu olla samaselt tõene. Ümberpöördult, kui ¬F ei ole samaselt tõene, siis leidub väärtustus, kus ¬F on väär ja F on järelikult tõene.

4. Samaväärsed valemid. Lausearvutuse põhisamaväärsused. Valemite teisendamine samaväärsuste abil. Teoreem piisavatest tehete komplektidest. [1, L2 slaidid]

Samaväärsed valemid

• DEF: Valemeid F ja G nimetatakse samaväärseteks, kui nende tõeväärtused on võrdsed igal neis valemeis esinevate muutujate väärtustel.
  
• Teoreem: Valemid F ja G on samaväärsed parajasti siis, kui valemist F järeldub valem G ja valemist G järeldub valem F.
  
• Teoreem : Valemid F ja G on samaväärsed parajasti siis, kui valem F ↔ G on samaselt tõene. Tõestus. Eeldame, et valemid F ja G on samaväärsed. Valime valemites F ja G esinevatele muutujatele suvalise väärtustuse. Kui valitud väärtustusel kehtib F = 1 ja G = 1, siis F ↔G = 1, kui aga valitud väärtustusel kehtib F = 0 ja G = 0, siis samuti F ↔ G = 1. Järelikult on valem F ↔ G tõene sõltumata väärtustusest ehk samaselt tõene. Eeldame nüüd ümberpöördult, et valem F ↔G on samaselt tõene. Valime selles valemis esinevatele muutujatele suvalise väärtustuse. Etekvivalents on tõene, siis kas F = 1, G = 1 või F = 0, G = 0. See tähendab, valemite F ja G tõeväärtused on suvalisel väärtustusel samad. Vastavalt definitsioonile on valemid F ja G samaväärsed.
  

Lausearvutuse põhisamaväärused

• Idempotentsuse seadused:
  

F & F ≡ F ,
F ∨ F ≡ F .

• Kommutatiivsuse seadused:
  

F & G ≡ G & F ,
F ∨ G ≡ G ∨ F .

• Assotsiatiivsuse seadused:
  

(F & G) & H ≡ F & (G & H ),
(F ∨ G) ∨ H ≡ F ∨ (G ∨ H ).

• Distributiivsuse seadused:
  

F & (G ∨ H ) ≡ F & G ∨ F & H ,
F ∨ G & H ≡ (F ∨ G) & (F ∨ H ).

• Neelamisseadused:
  

F & (F ∨ G) ≡ F ,
F ∨ F & G ≡ F .

• De Morgani seadused:
  

¬(F & G) ≡ ¬F ∨ ¬G,
¬(F ∨ G) ≡ ¬F & ¬G.

• Kahekordse eituse seadus:
  

¬¬F ≡ F .

• Liikmete elimineerimise reeglid, kus T on suvaline samaselt tõene valem ja V on suvaline samaselt väär valem:
  

F & T ≡ F ,
F & V ≡ V ,
F ∨T ≡T ,
F ∨ V ≡ F .

• Implikatsiooni avaldis konjunktsiooni ja disjunktsiooni kaudu:
  

F → G ≡ ¬(F & ¬G),
F → G ≡ ¬F ∨ G.

• Konjunktsiooni ja disjunktsiooni avaldis implikatsiooni kaudu:
  

F & G ≡ ¬(F → ¬G),
F ∨ G ≡ ¬F → G.

• Ekvivalentsi avaldis teiste tehete kaudu:
  

F ↔ G ≡ F & G ∨ ¬F & ¬G,
F ↔G ≡ (F → G) & (G → F
Valemite teisendamine samaväärsuste abil
Samaväärsuste kasutamine teisendustes seisneb valemi mingi osavalemi asendamises temaga samaväärsega. Nagu algebras, säilitab selline osavalemi asendamine ka siin samaväärsuse ka terve valemi jaoks. Peamised kujud, millele teisendatakse, on:
○ esitused kahe tehte kaudu
○ nn normaalkujud
Teoreem piisavatest tehete komplektidest
Iga lausearvutuse valemi jaoks leidub temaga samaväärne valem, mis ei sisalda muid tehtemärke kui:
○ ¬, &
○ ¬, ∨
○ ¬, →
Tõestus: kolm ülejäänud tehet saab avaldada antud komplekti kaudu

5. Järeldumine . Teoreemid järeldumise ja samaväärsuse taandamisest ühe valemi omaduste kontrollimisele. [1]

Järeldumine

• DEF: Ütleme, et valemitest F1 , F2 , . . . , Fn järeldub valem G, kui igal neis valemeis esinevate muutujate väärtustusel, millel F1 , F2 , . . . , Fn on tõesed, on ka G tõene.
  
• Teoreem järeldumise kohta: Valemitest F 1 , F 2 , . . . , F n järeldub valem G parajasti siis, kui valem F 1 & F 2 & . . . & F n → G on samaselt tõene.
  

Tõestus. Kui valemitest F 1 , F 2 , . . . , F n järeldub valem G, siis neil väärtustustel, millel valemid F 1 , F 2 , . . . , F n on tõesed, on ka valem G tõene, mistõttu F 1 &F 2 &. . .&F n →G on tõene. Väärtustustel, millel mõni valemitest F 1 , F 2 , . . . , F n on väär, on valem F 1 &F 2 &. . .&F n →G tõene seetõttu, et implikatsiooni eesliige on väär. Ümberpöördult, kui valem F 1 & F 2 & . . . & F n → G on samaselt tõene, siis igal väärtustusel, millel valemid F 1 , F 2 , . . . , F n on tõesed, on ka F 1 & F 2 & . . . & F n tõene, mistõttu valem G on samuti tõene.
Teoreemid järeldumise ja samaväärsuse taandamisest ühe valemi omaduse kontrollimisele

• Samaväärus F ↔ G
  
• Järeldumine F → G
  

6. Literaal , täielik elementaarkonjunktsioon, täielik disjunktiivne normaalkuju , nende tõesuspiirkondade kirjeldused. TDNK olemasolu ja ühesus. TDNK-le teisendamise algoritm , tema etappidel kasutatavad samaväärsused. [1]

Literaal

• DEF: Literaaliks nimetatakse lausemuutujat või selle eitust, literaale loetakse positiivseks või negatiivseks vastavalt selelle, kas ta on puhas lausemuutuja või koos eitusega. N: A, B, ¬C
  

Täielik elementaalkonjuktsioon

• DEF: Muutujate X1, X2…, Xn täielikuks elementaarkonjunktsiooniks nimetatakse literaalide konjunktsiooni L1&L2&,..., &Ln
  

Täielik disjunktiivne normaalkuju

• DEF: Lausearvutuse valemi F täielikuks disjunktiivseks normaalkujuks (TDNK) nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate täielike elementaarkonjunktsioonide disjunktsiooni.
  

Tõestuspiirkondade kirjeldused
TDNK olemasolu ja ühesus
Teoreem. Kui valem F ei ole samaselt väär, siis tal leidub täielikdisjunktiivne normaalkuju.
Järeldus. Kui valem F ei ole samaselt tõene, siis tal leidub täielikkonjunktiivne normaalkuju.
Tõestus. Et valem ¬F ei ole samaselt väär, siis leidub tal täielik disjunktiivne normaalkuju. Leiame mõlemast poolest eituse, seejärel viime paremal eituse sissepoole De Morgani seaduste abil. Nii saame Paremal poolel võis lausemuutujate ette tekkida kahekordseid eitusi. Jättes need ära, ongi tulemuseks valemi F täielik konjunktiivne normaalkuju
TDNK’le teisendamise algoritm, etappidel kasutatavad samaväärsused

• Elimineerime implikatsioonid ja ekvivalentsid
  

F → G ≡ ¬F ∨ G,
F ↔ G ≡ F & G ∨ ¬F & ¬G

• Viime eitused vahetult lausemuutujate ette, kasutades De Morgani seadusi
  

¬(F & G) ≡ ¬F ∨ ¬G,
¬(F ∨ G) ≡ ¬F & ¬G
Kui kuskile tekib kahekordne eitus, siis jätame selle ära.

• Viime konjunktsioonid disjunktsioonidest sügavamale, kasutades distributiivsuse seadusi
  

F & (G ∨ H ) ≡ F & G ∨ F & H
(F ∨ G) & H ≡ F & H ∨ G & H

• Eemaldame liikmed, mis sisaldavad vastandlikke literaalipaare, sest need liikmed on samaselt väärad. Igast järelejäänud liikmest kaotame literaalide kordused. Jätame välja korduvad liikmed.
  
• Lisame igale elementaarkonjunktsioonile täiskomplektist puuduvad muutujad, kasutades seost F ≡ F & (A ∨ ¬A). Seejärel rakendame uuesti distributiivsuse seadusi ja korrutame sulud lahti
  
• Jätame välja täielike elementaarkonjunktsioonide korduvad eksemplarid, kasutades idempotentsuse seadust F ∨ F ≡ F .
  

7. Boole ’i funktsioonide esitamine lausearvutuse valemitega. [1, L3 slaidid]

• DEF: Kaheelemendilisel hulgal defineeritud funktsioone nim Boole’i funktsioonideks.
  
• Teoreem: Iga Boole’i funktsiooni f(X1, … , Xn1, Xn) saab esitada lausearvutuse valemina milles ei ole muid tehtemärke, kui &, ∨ ja ¬.
  

8. Lausearvutuse (tehted, valemid, samaväärsus, teisendamine, normaalkuju jne) seosed programmeerimise, infosüsteemide jms-ga.

Telefoniraamatu ülesanne, kuidas leiab kiiremini jne..

9. **Tõestamise strateegiad, mis tulenevad eelduste või juba tõestatud faktide kujust : konjunktsioon, disjunktsioon, implikatsioon, ekvivalents, eitus, üldisus , olemasolu. [3]

Implikatsiooni tõestamise tavaline taktika on järgmine. Eeldame, et lisaks teoreemi eeldustele kehtib ka B. Tõestame

10. Üldisuse kvantoriga väite tõestamine induktsiooniga naturaalarvudel. [2, 3, L15 slaidid]

Kvantoreid sisaldavate valemite korral eeldame, et on fikseeritud mingi universaalne hulk ja tähendab: „iga korral hulgast kehtib “, tähendab: „leidub selline , et kehtib “.
Vaatame nüüd läbi kõik loogilised seosed. Alustame nendest , mis esinesid ülaltoodud näites.
Tavaline üldisuse kvantoriga väite tõestamise esimene samm on selline: Tähistagu muutuja suvalist universaalse hulga elementi.
Formaalselt tähendab suvalisus seda, et peame valima uue tähise, et eeldustes ei oleks elemendi kohta midagi väidetud. Sealhulgas võib tähisena kasutada ka sedasama muutujat , kui ta ei esine eeldustes (vaba muutujana).

11. **Kvantorite distributeerumine konjunktsiooni ja disjunktsiooniga. **Kvantorite ettetoomine. [3]

• Kvantorite distributiivsus:
  

8x(F(x) & G(x)) = 8xF(x) &8xG(x),
9x(F(x) v G(x)) = 9xF(x) v9xG(x).

• vajaduse korral konjunktsiooni ja disjunktsiooni kommutatiivsust,
  

toome kvantorid osavalemite eest valemi ette.
HULGAD, FUNKTSIOONID

12. Hulgateooria alusmõisted: hulk, element, hulkade võrdsus, tühi hulk. [3, 4, 5]

Hulk

• üksteisest erinevate objektide kohumit, mida vaadeldakse ühe tervikuna ja kus iga objekti
  

korral on võimalik üheselt kindlaks määrata, kas ta kuulub antud hulka.
Element

• hulka kuuluv objekt
  

Hulkade võrdsus

• DEF: Kahte hulka A ja B loetakse võrdseteks ja kirjutatakse A = B, kui hulgad A ja B
  

koosnevad samadest elementidest: A = B ⇔ ∀x [x ∈ A ⇔ x ∈ B].
Tühi hulk

• DEF: Tühjaks hulgaks e. tühihulgaks nimetatakse hulka, mis ei sisalda ühtegi elementi. Tühja hulka tähistatakse sümboliga ∅. ∅.
  

13. Põhilised arvuhulgad : N, Z, Q, R, C, reaalarvude intervallid . [3, 4, 5]

Põhilised arvuhulgad

< naturaalarvud e positiivsed täisarvud
< täisarvud
< ratsionaalarvud

• R = reaalarvud
  
<,

• vahemik (a, b)
  

Ühisosa

• DEF: Hulkade A ja B ühisosaks e. lõikeks nimetatakse hulka A∩B, mille moodustavad kõik elemendid, mis kuuluvad nii hulka A kui hulka B, st A∩.
  

Vahe

• DEF: Def. Hulkade A ja B vaheks nimetatakse hulka A\B, mille moodustavad elemendid, mis kuuluvad hulka A, aga ei kuulu hulka B, st A\.
  

Universaalhulk

• DEF: hulk, mis sisaldab alamhulkadena kõiki antud probleemis või mõttekä.
  

Täiend

• DEF: Hulga A täiendiks A’ nimetatakse hulka, moodustavad kõik need universaalse hulga elemendid, mis ei kuulu hulka A: A’
  

Vienni diagrammid

• DEF: Hulgateoreetilistele tehetele ja avaldistele vastavaid hulki kujutatakse tihti nn Venni diagrammide abil, kus hulkadele vastavad joontega piiratud piirkonnad.
  

Tehete algebralased omadused, nende tõestamine ja kontroll

• Näiteks ühend, ühisosa ja sümmeetriline vahe on kommutatiivsed tehted, aga vahe ei ole (tuua kontranäide!).
  
• Mõned samasused saame lausearvutusest otse üle võtta. Ühend, ühisosa ja täiend on defineeritud vastavalt komponenthulkadesse kuulumise tingimuste disjunktsiooni, konjunktsiooni ja eituse abil. Seetõttu on neil tehetel nii ühekaupa kui ka omavahelistes seostes samad omadused, mis vastavatel lausearvutuse tehetel.
  
• 1. Nagu lausearvutuses disjunktsiooni ja konjunktsiooni vahel, kehtivad ühendi ja ühisosa vahel kaks distributiivsuse seadust. Aga ühisosa võtmine jaotub ka hulkade vahele ja sümmeetrilisele vahele.
  

A∩ (B∪ C) = (A∩ B)∪ (A∩ C), A∪ (B∩ C) = (A ∪ B)∩ (A∪ C),
A ∩ (B\C) = (A ∩B) \ (A∩ C), A∩ (BΔ C ) = (A∩ B) Δ (A∩ C ).

• 2. Neelduvuse seadused
  

A∪ (A∩ B) = A, A∩ (A∪ B) = A.

• 3. De Morgani seadused
  

(A ∩ B)’ = A’∪ B’, (A ∪ B)’ = A’∩ B’

• 4. Vahe ja sümmeetriline vahe avalduvad ühisosa, ühendi ja täiendi kaudu:
  

A\B = A∩ B’, AΔB = A∩ B’ ∪ B∩ A’

• 5. Vahe seosed teiste tehetega :
  

A\B = A \ (A∩ B),
A∪ B = A∪ (B \A),
(A\B)\C = A\(B∪ C).

• 6. Sümmeetriline vahe avaldub sümmeetriliselt A ja B suhtes:
  

AΔ B = (A∪ B) \ (A∩ B]

16. Hulkade otsekorrutis . Otseaste. Otsekorrutise omadused [3, 4, 5]

Hulkade otsekorrutis

• DEF: Hulkade A ja B otsekorrutiseks e. Descartes ’i korrutiseks nimetatakse hulka A × B, mille moodustavad kõik järjestatud paarid (a, b), kus a∈A ja b∈B:
  

A ×
Otseaste

• DEF: Hulga A n-ndaks otseastmeks An nimetatakse otsekorrutist A × … × A, kus A esineb n korda.
  

Otsekorrutise omadused

• Otsekorrutis ei ole kommutatiivne ega assotsiatiivne operatsioon .
  
• Tõestus. Juba ü×{2} ≠×{1}×{2}×{1}; ({1}×{2})×{3} ≠×({2}×{3} ), sest ({1}×{2})×{3}×({2}×{3} ).
  
• Aga otsekorrutis distributeerub kõigi binaarsete hulgateooria tehetega:
  

A × (B ∪ C) = (A × B)∪ (A × C), A × (B ∩ C) = (A × B)∩ (A × C),
A × (B \ C) = (A × B) \ (A × C), A × (B Δ C) = (A × B) Δ (A × C).

• Tõestuseks võime avaldada võrduse vasakusse ja paremasse poolde kuulumise tingimused hulkadesse A, B ja C kuulumise kaudu ja teisendada saadud valemi konjunktsioonide disjunktsiooniks.
  
• Näiteks kolmanda samasuse vasakust poolest saame avaldamise järel
  

(x,y)∈ A × (B \ C) ⇔ x∈ A & y∈ B \ C ⇔ x∈ A & y∈ B & ¬(y∈ C).

• Paremast poolest saame vahe ja otsekorrutise definitsioone rakendades
  

(x,y)∈ (A × B) \ (A × C) ⇔ (x,y)∈ A × B & ¬((x,y)∈ (A × C)) ⇔ ⇔ x∈ A & y∈ B &¬((x∈ A & y∈C)).

• Edasi viime eituse de Morgani seaduse abil konjunktsiooni sisse, korrutame disjunktsiooni kahe esimese liikmega läbi ja jätame esimese konjunktsiooni ära, sest seal on x∈ A konjugeeritud iseenda eitusega:
  

… ⇔ x∈ A & y∈ B &(¬(x∈ A) ∨¬ (y∈C)) ⇔ ⇔ x∈ A & y∈ B &¬(x∈ A) ∨ x∈ A & y∈ B & ¬ (y∈C) ⇔ x∈ A & y∈ B & ¬ (y∈C).

• Näeme, et tingimused on identsed ja järelikult samasus kehtib. Samal viisil saame tõestada ka teised võrdused. Sümmeetria põhjal on selge, et samasuguste omadustega on ka otsekorrutis, milles ühend, ühisosa, vahe või sümmeetriline vahe on vasakpoolne liige.
  
• Otsekorrutise definitsiooni rakendades on ilmne, et otsekorrutis tühja hulgaga on tühi hulk
  

A × ∅ = ∅, ∅ × A = ∅

17. Binaarse seose ( relatsiooni ) mõiste. Pöördseos. n- aarne seos. [3, 4, 5]

Relatsiooni (binaarse seose) mõiste

• DEF: Binaarseks seoseks ehk relatsiooniks hulkade X ja Y elementide vahel nimetatakse nende hulkade otsekorrutise suvalist alamhulka ρ ⊆ X×Y. Kui (x,y)∈ ρ, siis kirjutatakse ka x ρ y.
  

Pöördseos

• DEF: Binaarse seose ρ pöördseoseks ehk pöördrelatsiooniks nimetatakse seost ρ
  

n-aarne seos

• DEF: n-aarseks seoseks ehk relatsiooniks hulkade X1 , X2 ,…, Xn elementide vahel nimetatakse nende hulkade otsekorrutise suvalist alamhulka ρ ⊆ X1 × X2 ×… × Xn
  

18. Funktsioon. Elemendi kujutis. Elemendi originaal . Funktsiooni määramispiirkond . Funktsiooni väärtuste piirkond. [3, 4, 5]

Funktsioon

• DEF: Olgu X ja Y mittetühjad hulgad. Seost f⊆X ×Y nimetatakse funktsiooniks e. kujutuseks hulgast X hulka Y, kui iga x∈X jaoks leidub täpselt üks selline y∈Y, et (x,y)∈f.
  

Elemendi kujutis

• DEF: Kui x∈X, y∈Y ja y = f(x), siis y nimetatakse elemendi x kujutiseks(funktsiooniga f).
  

Elemendi originaal

• DEF: Kui x∈X, y∈Y ja y = f(x), siis x nimetatakse elemendi y originaaliks.
  

Funktsiooni määramispiirkond

• DEF: Definitsioonis esinevat hulka X nimetatakse funktsiooni f määramispiirkonnaks.
  

Funktsiooni väärtuste piirkond

• DEF: Funktsiooni määramispiirkonna kujutist nimetatakse funktsiooni väärtuste piirkonnaks ehk muutumispiirkonnaks.
  

19. Hulga kujutis. Hulga originaal. Funktsioonide kompositsioon . **Kujutise ja originaali omadused. [3, 4,5]

Hulga kujutis

• DEF: Hulga A⊆X kujutiseks nimetatakse hulga Y alamhulka, mis koosneb kõikide A elementide kujutistest: f(A)
  

Funktsioonide kompositsioon

• DEF: Funktsioonide f : X→Y ja g : Y→Z korrutiseks ehk kompositsiooniks nimetatakse funktsiooni gf: X→Z, mis määratakse võrdusega (gf)(x) = g(f(x)), x∈X
  

Kujutise omadused

• Olgu f funktsioon X→ Y ja A, B ⊆ X. Siis
  

1. f(∅) = ∅
2. f(X) ⊆ Y
3. Kui A ⊆ B, siis f(A) ⊆ f(B)
4. f(A∪B) = f(A) ∪ f(B)
5. f(A∩B) ⊆ f(A) ∩ f(B)
Originaali omadused

• Olgu f funktsioon X→Y ja A, B ⊆ Y. Siis
  

1. f-1 (∅) = ∅
2. f -1(Y) = X
3. Kui A ⊆ B, siis f -1(A) ⊆ f -1(B)
4. f -1(A∪B) = f -1(A) ∪ f -1(B)
5. f -1(A∩B) = f -1(A) ∩ f -1(B)
6. f -1(B’) = (f -1(B))’ st f -1(Y\B) = X \ f -1(B)

20. Injektiivne funktsioon. Sürjektiivne funktsioon. Bijektiivne funktsioon. Pöördfunktsiooni mõiste. [3, 4,5]

Injektiivne funktsioon

• DEF: Funktsiooni f : X→Y nimetatakse injektiivseks ehk üksüheseks, kui erinevate argumendi väärtuste korral on funktsiooni väärtused erinevad: x1!=x2 ⇒f(x1)!= f(x2).
  
• Injektiivsus tähendab, et ühelgi hulga Y elemendil pole rohkem, kui üks originaal.
  

Sürjektiivne funktsioon

• DEF: Funktsiooni f : X→Y nimetatakse sürjektiivseks ehk pealekujutuseks, kui iga y∈Y jaoks leidub selline x∈X, et f(x) = y
  
• Sürjektiivsus tähendab, et igal hulga Y elemendil leidub vähemalt üks originaal
  

Bijektiivne funktsioon

• DEF: Funktsiooni f : X→Y nimetatakse bijektiivseks, kui funktsioon on injektiivne ja sürjektiivne.
  
• Bijektiivsus tähendab, et igal hulga Y elemendil leidub täpselt üks originaal
  

Pöördfunktsiooni mõiste

• DEF: Bijektiivse funktsiooni f : X→Y pöördfunktsiooniks nimetatakse funktsiooni f 1: Y→X, mis seab igale y∈Y vastavusse sellise elemendi x∈X, mille korral f(x) = y.
  

BINAARSED RELATSIOONID

21. Binaarse relatsiooni definitsioon. Näited. [2]

Binaarne relatsioon

• DEF: Binaarseks relatsiooniks e. seoseks hulkade X ja Y elementide vahel nimetatakse nende hulkade otsekorrutise suvalist alamhulka R ⊆ XY.
  

Näited

• Nä. Kaks elementi x ∈ X ja y ∈ Y loeme seotuks parajasti siis, kui nad koos määravad tavalisel malelaual musta värvi välja. Niiviisi saame relatsiooni R ⊆ X × Y , mis koosneb 32 paarist (a, 1), (a, 3), (a, 5), (a, 7), (b, 2), . . . , (h, 8) See relatsioon on 64-elemendilise hulga X × Y alamhulk.
  
• Näide 2. Olgu X kõigi inimeste hulk. Siis võ. Niiviisi saab relatsiooni mõiste abil kirjeldada ka inimestevahelisi sugulussidemeid.
  

22. Relatsioonide esitamisviisid: loend , Boole’i maatriks , graaf , avaldis. Näited probleemidest, kus on sobiv kasutada konkreetset esitusviisi. [2]

Loend

• Kui relatsioon kehtib väheste elemendipaaride vahel, siis võib teda lihtsalt ette anda paaride loendina.
  
• Vaatleme nä määratud relatsiooni R, mis kehtib kahe arvu x ja y vahel parajasti siis, kui nende arvude sõnalises kujus ei leidu ühist tähte („sõltumatud arvud“). Lihtne on üle kontrollida kõ.
  

Boole’i maatriks

< vahel saab ette anda ka maatriksiga, mille mõõtmed on m×n, kusjuures reas i ja veerus j asub väärtus 1, kui elemendipaar (xi, yj) kuulub relatsiooni, ning väärtus 0 vastasel korral. Juhul X = Y saame ruutmaatriksi.

• Kui R on näiteks viimati vaadeldud jaguvusrelatsioon, siis tema maatriks on
  

Graaf

• Ühe võimalusena võib relatsiooni esitada suunatud graafi abil. Kujutame hulga X elemente ja hulga Y elemente punktidena joonisel ning tõmbame kaare elemendist x ∈ X elemendini y ∈ Y parajasti siis, kui paar (x, y) kuulub vaadeldavasse relatsiooni. Niimoodi saame graafi, milles kõik kaared viivad ainult hulgast X hulka Y ning kus pole ühtegi kaart kummagi hulga sees.
  
• Näiteks olgu X tä ning Y kõigi kahetäheliste sõnade hulk, mida saab neist tä. Loeme, et täht x ja sõna y on relatsioonis R, kui täht x esineb sõnas y. Seda relatsiooni esitab graaf:
  

Avaldis

• Relatsiooni kui (paaride) hulka võib esitada ka temasse kuulumise tingimuse kaudu.
  
• Nt. Olgu R ⊆ X × Y ja S ⊆ Y × Z kaks relatsiooni. Relatsioonide R ja S kompositsiooniks nimetatakse relatsiooni R ◦ S ⊆ X × Z, mis on määratud avaldisega R ◦.
  

23. Refleksiivsus , antirefleksiivsus, sümmeetrilisus, antisümmeetrilisus, transitiivsus. Näited. Relatsiooni maatriksi ja graafi kuju iga omaduse korral. [2]

Refleksiivsus

• DEF: Hulgal X määratud relatsiooni R nimetatakse refleksiivseks, kui iga x∈X korral (x,x)∈R
  
• Kui X on lõplik hulk, siis saame R esitada maatriksina. Refleksiivsuse korral on relatsiooni maatriksi peadiagonaalil väärtused 1.
  
• Refleksiivse relatsiooni suunatud graafis on iga tipu juures silmus .
  

Antireflektsiivsus

• DEF: Hulgal X määratud relatsiooni R nimetatakse antirefleksiivseks, kui iga x∈X korral (x,x)∉R
  
• Antirefleksiivse relatsiooni maatriksi peadiagonaal koosneb nullidest.
  
• Antirefleksiivse relatsiooni suunatud graafis ei ole ühegi tipu juures silmust.
  

Sümmeetrilisus

• DEF: Hulgal X määratud relatsiooni R nimetatakse sümmeetriliseks, kui (x,y)∈R korral alati (y,x)∈R
  
• Sümmeetrilise relatsiooni maatriks on sümmeetriline peadiagonaali suhtes, sest elemendid ja on võrdsed.
  

Antisümmeetrilisus

• DEF: Hulgal X määratud relatsiooni R nimetatakse antisümmeetriliseks, kui (x,y)∈R ja (y,x)∈R korral alati x=y
  
• Antisümmeetrilise relatsiooni Boole’i maatriksis on iga väljaspool peadiagonaali asuva elemendi 1 suhtes sümmeetriline element 0.
  
• Antisümmeetrilise relatsiooni graafis pole kahte vastassuunalist kaart.
  

Transitiivsus

• DEF: Hulgal X määratud relatsiooni R nimetatakse transitiivseks, kui (x,y)∈R ja (y,z)∈R korral alati (x,z)∈R
  
• Kui on olemas paar (y,z) ja (x,y), siis peab olema ka (x,z).
  

24. Ekvivalentsirelatsioon. Tähtsamad näited. Ekvivalentsiklassid. Näited. [2] Teoreem hulga jaotumisest ekvivalentsiklassideks. [3]

Ekivalentsirelatsioon

• Relatsioon, mis on refleksiivne, sümmeetriline ja transitiivne
  
• Võrdus on ekvivalentsirelatsioon, võrratused ja mittevõrdus ei ole.
  

Ekivalentsiklassid

• 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.
  
• 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

• Teoreem. Kui on hulgal defineeritud ekvivalentsirelatsioon, siis kehtib:
  1) Kui kehtib, siis ,
  

2) Kui
ei kehti, siis ,
3) Ekvivalentsiklasside ühend on hulk .

25. Mitterange ja range järjestusrelatsioon. Tähtsamad näited. Lineaarsed ja mittelineaarsed järjestused. Näited. [2]

Mitterange järjestusrelatsioon

• DEF: Relatsiooni R nimetatakse mitterangeks järjestusrelatsiooniks, kui R on refleksiivne, antisümmeetriline ja transitiivne.
  

Range järjestusrelatsioon

• DEF: Relatsiooni R nimetatakse rangeks järjestusrelatsiooniks, kui R on antirefleksiivne ja transitiivne.
  

Lineaarsed ja mittelineaarsed järjestused

• Hulgal X defineeritud ranget järjestusrelatsiooni R nimetatakse lineaarseks, kui kehtib
  

• Hulgal X defineeritud mitteranget järjestusrelatsiooni R nimetatakse lineaarseks, kui kehtib
  

26. Teoreem rangete ja mitterangete järjestuste seosest (**tõestus). [3]

Teoreem rangete ja mitterangete järjestuste seosest

• Teoreem.
  

1. Kui
on hulgal
defineeritud range järjestusrelatsioon ja kehtib , siis
on mitterange järjestusrelatsioon.
2. Kui
on hulgal
defineeritud mitterange järjestusrelatsioon ja kehtib , siis
on range järjestusrelatsioon.

27. Hulgateoreetilised tehted relatsioonidega. Näited. [2]

Hulgateoreetilised tehted relatsioonidega

• Relatsioonid on paaride hulgad ja hulkade vahel saab teha hulgateoreetilisi tehteid.
  

Olgu
ja
relatsioonid hulkade
ja
vahel.

• Ühend:
  
• Ühisosa:
  
  
• Vahe:
  
• Täiend:
  
  

28. Pöördrelatsioon. Relatsioonide kompositsioon. Näited. Ühikelement . Näited kompositsiooni mittekommutatiivsuse ja pöördrelatsiooni sobimatuse kohta pöördelemendiks kompositsiooni korral. Kompositsiooni assotsiatiivsus (**tõestus). [2]

Pöördrealatsioon

• DEF: Relatsiooni R pöördrelatsiooni R−1, mis saadakse relatsioonist R, muutes kõigis sinna kuuluvates elemendipaarides komponentide järjekorra vastupidiseks: R−. Kui R on relatsioon hulkade X ja Y vahel, siis R−1 on relatsioon hulkade Y ja X vahel.
  
• Nä, on R−.
  

Relatsioonide kompositsioon

• DEF. Olgu R ⊆ X × Y ja S ⊆ Y × Z kaks relatsiooni. Relatsioonide R ja S kompositsiooniks nimetatakse relatsiooni R ◦ S ⊆ X × Z, mis on määratud avaldisega
  

R ◦.
Ühikelement

• Kui IX on samasusrelatsioon hulgal X ja IY samasusrelatsioon hulgal Y , siis suvalise relatsiooni R ⊆ X × Y korral R ◦ IY = IX ◦ R = R. Teiste sõnadega, samasusrelatsioon on kompositsiooni suhtes ühikelement
  

Näited kompositsiooni mittekommutatiivsuse ja pöördrelatsiooni sobimatuse kohta pöördelemendiks kompositsiooni korral

• Kompositsioon ei ole kommutatiivne, st üldiselt
  

Näide: ühest kaarest koosnevad relatsioonid 3-elemendilisel hulgal.

• Pöördrelatsioon ei ole pöördelement algebralises mõttes, st üldiselt
  

Näide: tühirelatsioon

• Algebra terminites tähendab see, et hulgal määratud relatsioonide monoid tavaliselt ei ole kommutatiivne ega ole rühm.
  

Kompositsiooni assotsiatiivsus

• Teoreem 1. Suvaliste relatsioonide R ⊆ X × Y , S ⊆ Y × Z ja T ⊆ Z ×W korral (R ◦ S) ◦ T = R ◦ (S ◦ T ). See tähendab, relatsioonide kompositsioon on assotsiatiivne.
  
• Tõestus. Kahe hulga võrdsuse tõestamiseks näitame, et sisalduvused (x,w) ∈ (R ◦ S) ◦ T ja (x,w) ∈ R ◦ (S ◦ T ) on teineteisega samaväärsed. Tõepoolest, sisalduvus (x,w) ∈ (R ◦ S) ◦ T on kompositsiooni definitsiooni põhjal samaväärne tingimusega leidub z ∈ Z, et (x, z) ∈ R ◦ S ja (z,w) ∈ T, viimane aga samal põhjusel tingimusega leiduvad z ∈ Z ning y ∈ Y , et (x, y) ∈ R, (y, z) ∈ S ja (z,w) ∈ T . Siin võime kombineerida kaks viimast elemendipaari kompositsiooni definitsiooni abil ja kirjutada tingimuse kujul leidub y ∈ Y , et (x, y) ∈ R ja (y,w) ∈ S ◦ T , see aga tähendabki, et (x,w) ∈ R◦(S ◦T ). Et kõik teisendussammud säilitavad samaväärsuse, siis on vaadeldavad kaks sisalduvust tõesti teineteisega samaväärsed.
  

29. Kompositsiooni pöördrelatsioon (tõestusega). Kompositsiooni seosed ühendi ja ühisosaga (**tõestused). [2]

Kompositsiooni pöördrelatsioon

• Teoreem 3. Suvaliste relatsioonide R ⊆ X × Y ja S ⊆ Y × Z korral (R ◦ S)−1 = S−1 ◦ R−1.
  
• Tõestus. Analoogiliselt eelnevate tõestustega saame samaväärsete tingimuste ahela:
  

(z, x) ∈ (R ◦ S)−1 ⇔ (x, z) ∈ (R ◦ S) ⇔
⇔ leidub y, et (x, y) ∈ R ja (y, z) ∈ S ⇔
⇔ leidub y, et (y, x) ∈ R−1 ja (z, y) ∈ S−1 ⇔
⇔ (z, x) ∈ S−1 ◦ R−1
Kui alustada selle samaväärsuste ahela lugemist algusest, siis saame tõestuse, et (R◦ S)−1 ⊆ S−1 ◦R−1. Liikudes aga ahelas lõpust algusesse , saame teistpidi sisalduvuse S−1◦R−1 ⊆ (R◦S)−1.Mõlematpidi sisaldumisest aga järeldubki hulkade võrdsus.

• Niiviisi kõiki võimalusi läbi vaadates leiame R ◦. DEF: Kompositsiooni pöördrelatsioon on relatsioon hulkade Z ja X vahel ja koosneb samadest paaridest, ainult vastupidises järjekorras: (R ◦ S)−.
  

Kompositsiooni seosed ühendiga

• Teoreem. Suvaliste relatsioonide R ⊆ X × Y , S ⊆ Y × Z ja T ⊆ Y × Z korral R ◦ (S ∪ T ) = (R ◦ S) ∪ (R ◦ T ). Seega, kompositsioon on distributiivne ühendi suhtes.
  
• Tõestus. Tõestame, et võrduse vasak pool sisaldub paremas ja vastupidi, parem pool sisaldub vasakus. Kui (x, z) ∈ R ◦ (S ∪ T ), siis leidub y ∈ Y nii, et (x, y) ∈ R ja (y, z) ∈ S ∪ T . Kui viimases seoses (y, z) ∈ S, siis (x, z) ∈ R ◦ S; kui aga (y, z) ∈ T , siis (x, z) ∈ R◦T . Igal juhul (x, z) ∈ (R◦S)∪(R◦T ). Vastupidi, kui (x, z) ∈ (R◦ S)∪(R◦ T ), siis kas (x, z) ∈ R◦ S või (x, z) ∈ R ◦ T . Esimesel juhul leidub element y nii, et (x, y) ∈ R ja (y, z) ∈ S, viimasest saame (y, z) ∈ S∪T . Teisel juhul leidub element y nii, et (x, y) ∈ R ja (y, z) ∈ T , mis samuti annab (y, z) ∈ S ∪T . Et kummalgi juhul kehtib lisaks (x, y) ∈ R, siis (x, z) ∈ R ◦ (S ∪ T ).
  

Kompositsiooni seosed ühisosaga

• Kompositsiooni ja ühisosa vahel distributiivsus ei kehti, kuid saabväita järgmist.
  

• Teoreem. Suvaliste relatsioonide R ⊆ X × Y , S ⊆ Y × Z ja T ⊆ Y × Z korral R ◦ (S ∩ T ) ⊆ (R ◦ S) ∩ (R ◦ T ).
  
• Tõestus. Kui (x, z) ∈ R◦(S∩T ), siis leidub y ∈ Y nii, et (x, y) ∈ R ja (y, z) ∈ S ∩ T . Viimasest seosest saame (y, z) ∈ S ja (y, z) ∈ T . Tingimused (x, y) ∈ R ja (y, z) ∈ S annavad nüüd (x, z) ∈ R ◦ S, tingimused (x, y) ∈ R ja (y, z) ∈ T aga (x, z) ∈ R ◦ T . Järelikult (x, z) ∈ (R ◦ S) ∩ (R ◦ T ).
  

30. Relatsiooni aste (definitsioon ja näited). Teoreem relatsiooni astmest (tõestuseta). [2]

Relatsiooni aste

• DEF: Olgu R relatsioon hulgal X, st R ⊆ X×X. Relatsiooni R aste defineeritakse järgmiselt: R0 = I ja iga naturaalarvu n korral Rn = Rn−1 ◦R. Relatsiooni aste on niisiis korduv kompositsioon iseendaga. Assotsiatiivsuse tõttu kehtib ka Rn = R◦Rn−1.
  
• Näide 1.
• Näide 2. Olgu ja Siis
  

Teoreem relatsiooni astmest

• Teoreem. Paar (x, y) kuulub astmesse Rn, kus n > 1, parajasti siis, kui hulgas X leiduvad elemendid z0, . . . , zn nii, et z0 = x, zn = y ja iga i = 0, . . . , n − 1 korral (zi, zi+1) ∈ R.
  

31. Relatsiooni sulund omaduse suhtes. Näited sulundi olemasolu ja puudumise kohta. Transitiivne sulund. Teoreem transitiivse sulundi avaldumisest relatsiooni astmete kaudu. Refleksiivne transitiivne sulund. Transitiivse ja refleksiivse-transitiivse sulundi avaldiste seos ahelatega relatsiooni graafis. [2]

Relatsiooni sulund omaduse suhtes

• DEF. Relatsiooni 𝑅 sulundiks vaadeldava omaduse suhtes nimetatakse (sisalduvuse mõttes) vähimat relatsiooni, mis sisaldab 𝑅 ja millel on vaadeldav omadus
  
• Kui leidub vähemalt üks vaadeldava omadusega relatsioon, mis sisaldab , ja ühisosa võtmine säilitab omaduse, siis sulund eksisteerib.
  

Transitiivne sulund

• Relatsiooni R⊆X×X transitiivne sulund avaldub valemiga R+= ⋃ lõpmatus i=1 Ri
  
• Relatsiooni R transitiivset sulundit märgitakse tähisega R+
  

Refleksiivne transitiivne sulund

• Relatsiooni R⊆X×X refleksiivne transitiivne sulund R* avaldub valemiga
  

R*= ⋃lõpmatus i=0 Ri

• refleksiivset transitiivset sulundit märgitakse tähisega R∗
  

Teoreem transitiivse sulundi avaldumisest relatsiooni astmete kaudu

• Teoreem. Relatsiooni R ⊆ X ×X transitiivne sulund R+ avaldub valemiga
  

Tõestus. Tõestame, et valemi parem pool kujutab vähimat transitiivset relatsiooni, mis sisaldab relatsiooni R. Kõigepealt, relatsioon ∪∞ i=1Ri on transitiivne. Tõepoolest, kui ta sisaldab paare (x, y) ja (y, z), siis peab mingite k > 1 ja l > 1 korral olema (x, y) ∈ Rk ja (y,z) ∈ Rl. Kompositsiooni definitsiooni põhjal (x, z) ∈ Rk ◦ Rl = Rk+l ning järelikult (x,z) ∈ ∪∞i=1Ri. Olgu nüüd S mingi transitiivne relatsioon, mis sisaldab relatsiooni R. Valime suvalise paari (x, y) ∈ ∪∞ i=1Ri. Sel juhul (x, y) ∈ Rk mingi k > 1 korral ning teoreemi 6 põhjal leiduvad elemendid z0, . . . , zk nii, et z0 = x, zk = y ja iga i = 0, . . . , k−1 korral (zi, zi+1) ∈ R. Ent siis ka (zi, zi+1) ∈ S ning relatsiooni S transitiivsuse tõttu (x, y) ∈ S. Järelikult kehtib ∪∞ i=1Ri ⊆ S. Et vaadeldav relatsioon ∪∞ i=1Ri sisaldab ka relatsiooni R, siis rahuldab ta kõiki transitiivse sulundi tingimusi ja peab seega võrduma relatsiooniga R+.
Transitiivse ja refleksiivse-transitiivse sulundi avaldiste seos ahelatega relatsiooni graafis

• tähendab, et leidub suunatud ahel tipust tippu
  
• tähendab, et või leidub suunatud ahel tipust tippu .
  

• Transitiivne sulund on relatsiooni kõigi astmete ühend. Vaatleme relatsiooni graafi.
  
• tähendab, et relatsioonis leidub kaar
  tipust tippu .
  
• tähendab, et relatsioonis leidub suunatud ahel pikkusega 2 tipust tippu .
  
• tähendab, et relatsioonis leidub suunatud ahel pikkusega 3 tipust tippu jne
  

32. Relatsioonide täiendrelatsiooni, ühendi, ühisosa ja pöördrelatsiooni maatriks. Relatsioonide kompositsiooni maatriks. Relatsiooni astme maatriks. Nende arvutamine. [2]

Täiendusrelatsiooni, ühedi, ühisosa ja pöördrelatsiooni maatriks

• Olgu relatsioonide R, S maatriksid vastavalt R =(rij) ⊆ X × Y ja S=(sij). Siis
  

○ R täiendrelatsiooni R’ maatriks on ¬R = (¬r ij)
○ Ühendrelatsiooni R⋃S maatriks on R⋁S=(rij ⋁sij)
○ Ühisosa R⋂ S maatriks on R&S=(rij & sij)
○ R pöördrelatsiooni R1 maatriks on RT = (rji), st transponeeritud maatriks (read ja veerud on vahetatud )
Relatsiooni kopositsiooni maatriks

• Kui relatsioonide ja maatriksid on vastavalt ja S = (sij), siis kompositsiooni maatriks on maatriksite ja (Boole’i) korrutis:
  

Relatsiooni astme maatriks
Relatsiooni astme maatriksi saab leida järjestikuse korrutamise teel:
GRAAFID

33. Graafi definitsioon. Tipud , servad. Multigraaf. Täisgraaf, nullgraaf, täiendgraaf. Kaalutud graaf. Intsidentsus. Naabertipud. Graafi naabrusmaatriks. Alamgraaf . Regulaarne graaf. [2]

Graaf, tipud, servad

• Graaf on punktide hulk (tavaliselt lõplik), kus mõned punktid on ühendatud joontega.
  
• DEF. Graaf on paar G = (V,E), kus V on mittetühi hulk ning E hulk, mille elementideks on hulga V kaheelemendilised alamhulgad . Hulga V elemente nimetatakse graafi tippudeks, hulga E elemente aga servadeks. Ülaltoodud graafi puhul nä}.
  

Multigraaf

• DEF: Et toodud definitsioonis loetakse servadeks ainult tippude hulga kaheelemendilisi alamhulki, siis ei tohi graafis esineda silmuseid, st servi mis ühendavad mingit tippu iseendaga, ega kordseid servi, olukordi , kus mingit kahte tippu ühendab rohkem kui üks serv. Siiski tuleb vahel ka neid arvestada, sellisel juhul räägitakse graafi asemel multigraafist.
  

Täisgraaf

• DEF: Täisgraafiks nimetatakse graafi, milles iga tipupaari vahel on serv.
  

Nullgraaf

• DEF: Nullgraafiks nimetatakse graafi, milles pole ühtegi serva.
  

Täiendgraaf

• DEF: Graafi G täiendgraafiks nimetatakse graafi G’, millel on sama tippude hulk nagu graafil G, aga servaga on ühendatud parajasti need tipud, mille vahel graafis G serv puudub.
  

Kaalutud graaf

• DEF: Rakendustes on sageli vaja graafe, mille igale servale (või tipule) on vastavusse seatud üks reaalarv . Sellist graafi nimetatakse kaalutud graafiks ning vastavaid reaalarve kaaludeks.
  

Intsidentsus

• Kui tipp v kuulub servale e, siis ütleme, et tipp v ja serv e on intsidentsed.
  
• Iga serv on intsidentne täpselt kahe tipuga, serva otstipuga. Kui serv e ühendab tippe u ja v, siis märgime seda ka tä või e = uv.
  

Naabertipud

• DEF: Naabertipud on need tipud, mis on servaga ühendatud.
  

Graafi naabrusmaatriks

• Olgu G = (V, E) graaf tippude hulgaga VGraafi G naabrusmaatriks on n x n-maatriks A = (aij), kus
  

• Naabrusmaatriks on sümmeetriline peadiagonaali suhtes ja peadiagonaalil on nullid.
  
• Saab rakendada ka multigraafi ja suunatud graafi esitamiseks.
  

Alamgraaf

• DEF: Graafi G’ = (V’, E’), mis on saadud graafist G = (V, E) teatava hulga tippude ja servade kustutamisel , nimetatakse graafi G alamgraafiks.
  

Regulaarne graaf

• DEF: Graafi, mille kõigi tippude astmed on võrdsed, nimetatakse regulaarseks graafiks.
  
• Iga täisgraaf Kn ja iga nullgraaf On on regulaarne.
  

34. Graafi tipu aste. Tipuastmete teoreem, järeldus paaritute astmete kohta. [2]

Graafi tipu aste

• Tipu v aste ehk valents on tipuga v intsidentsete servade arv. Tähis d(v).
  
• Kui d(v) = 1, siis nimetatakse tippu v rippuvaks tipuks.
  
• Kui d(v) = 0, siis nimetatakse tippu v isoleeritud tipuks.
  
• Maksimaalne võimalik tipu aste n-tipulises graafis on n-1.
  

Tipuastmete teoreem

• Teoreem. Igas graafis on kõigi tippude astmete summa võrdne servade arvu kahekordsega.
  
• Tõestus. Iga serv suurendab oma kummagi otspunkti astet (ja seega ka astmete summat) kahe võrra.
  
• Järeldus. Igas graafis on paaritu astmega tippe paarisarv .
  

35. Ahel, ahela otstipud ja sisetipud. Lihtahel. Teoreem lihtahelast. Kaugus. [2]

Ahel, otstipud, sisetipud, lihtahel

• DEF: Ahelaks nimetatakse graafi tippude järjendit v0, v1, …, vk, kus iga kaks järjestikust tippu on servaga ühendatud.
  
• Tipud v0 ja vk on ahela otstipud, ülejäänud tipud on sisetipud.
  
• Ahela servade arvu k nimetatakse ahela pikkuseks .
  
• Ahel võib tippe ja servi sisaldada ka korduvalt.
  
• Kui ahel ei sisalda korduvaid tippe ega servi, nimetatakse teda lihtahelaks.
  

Teoreem lihtahelast

• Teoreem. Kui graafis G leidub ahel tipust u tippu v, siis leidub graafis G ka lihtahel tipust u tippu v.
  

Kaugus

• DEF: Tippude u ja v vahelise lühima lihtahela pikkust nimetatakse tippude u ja v kauguseks.
  

36. Tsükkel . Lihttsükkel. Teoreem lihtahela ja lihttsükli leidumisest. [2]

Tsükkel

• Tsükliks nimetatakse ahelat , mis algab ja lõpeb samas tipus.
  
• Tsükli servade arvu nimetatakse tsükli pikkuseks.
  

Lihttsükkel

• Kui tsükkel ei läbi ühtegi tippu ega serva kaks korda, siis nimetatakse teda lihttsükliks.
  

Teoreem lihtahela ja lihttsükli leidumisest

• Teoreem. Kui graafi iga tipu aste on vähemalt l ≥ 2, siis leidub graafis lihtahel pikkusega l ja lihttsükkel pikkusega vähemalt l + 1.
  
• Järeldus. Igas graafis, milles on servi vähemalt sama palju kui tippe, leidub tsükkel.
  

37. Graafide isomorfism . Isomorfsuse näitamine ja ümberlükkamine. [2]

Graafide isomorfism

• DEF: Graafe G = (V, E) ja G’ = (V’, E’) nimetatakse isomorfseteks,
  kui leidub bijektiivne funktsioon f: V → V’ nii, et graafis G on serv tippude u ja v vahel parajasti siis, kui graafis G’ on serv tippude f(u) ja f(v) vahel.
  
• Isomorfseid graafe võib lugeda matemaatilises mõttes samadeks
  

Isomorfsuse näitamine ja ümberlükkamine

• Teisiti öeldes tähendab isomorfsus seda, et mõlemas graafis võib tipud nummerdada nii, et samade numbritega tipud on kas mõlemas graafis servaga ühendatud või mõlemas ühendamata. Kui igale servale esimeses graafis vastab teises graafis serv samade numbritega tippude vahel ja vastupidi, siis on need graafid isomorfsed.
  

38. Sidusus. Sidus komponent . Sild . Eraldav tipp. Tarvilik ja piisav tingimus silla jaoks. [2]

Sidusus

• DEF: Graafi, milles iga kahe tipu korral leidub neid tippe ühendav (liht)ahel, nimetatakse sidusaks. Sidusaks loetakse ka ühetipulist graafi.
  

Sidus komponent

• Kui graaf ei ole sidus, siis koosneb ta eraldiseisvatest sidusatest osadest, mida nimetatakse sidusateks komponentideks.
  
• DEF: Sidus komponent on graafi maksimaalne sidus alamgraaf.
  

Sild, eraldav tipp

• DEF: Serva, mille eemaldamisel graafi sidusate komponentide arv kasvab, nimetatakse sillaks.
  
• Analoogilise omadusega tippu nimetatakse eraldavaks tipuks.
  

Tarvilik ja piisav tingimus silla jaoks

• Teoreem. Graafi serv on sild parajasti siis, kui ta ei kuulu ühessegi selle graafi lihttsüklisse.
  
• Tarvilikkus. Sild ei saa kuuluda lihttsüklisse, sest tsüklist serva eemaldamisega ei saa katkeda ühendus serva otstippude vahel.
  
• Piisavus. Kui serv ei kuulu ühessegi lihttsüklisse, siis peab tema eemaldamisel ühendus serva otstippude vahel katkema.
  

39. Sidususteoreem. [2]

• Teoreem. Kui n-tipulisel graafil on m serva ja k sidusat komponenti, siis kehtivad võrratused
  

• Tõestus.
  1) induktsiooniga m järgi,
  2) mitu serva saab olla k komponendi ja n tipu korral?
  
• Järeldus. Kui n-tipulisel graafil on vähem kui n-1 serva, siis see graaf on mittesidus.
  
• Järeldus. Kui n-tipulisel graafil on rohkem kui (n-1)(n-2)/2 serva, siis see graaf on sidus.
  

40. Euleri tsükkel ja Euleri graaf. Näited. Euleri tsükli leidumise kriteerium . [2]

Euleri tsükkel

• DEF: Tsüklit, mis läbib graafi kõik servad täpselt üks kord, nimetatakse Euleri tsükliks.
  

Euleri graaf

• DEF: Graafi, kus leidub Euleri tsükkel, nimetatakse Euleri graafiks.
  

Euleri tsükli kriteerium

• Teoreem. ( Euler , 1736). Sidusas graafis leidub Euleri tsükkel parajasti siis, kui graafi iga tipu aste on paarisarv.
  
• Tarvilikkus. Kui Euleri tsükkel leidub, siis peab ta igasse tippu sisenedes saama sealt ka väljuda.
  
• Piisavus. Paarisarvuliste astmete korral saame tsükli konstrueerida „ ahne strateegia” abil: hakkame mingist tipust liikuma, kuni jõuame sinna tagasi. Jätkame samamoodi, kuni kõik servad on kasutatud.
  
• Näide. Milliseid täisgraafe saab joonistada ühe joonega?
  

41. Hamiltoni ahel, tsükkel ja Hamiltoni graaf. Näited. Kontrollimine. [2]

Hamiltoni ahel

• Ahelat, mis läbib graafi kõik tipud täpselt üks kord, nimetatakse Hamiltoni ahelaks.
  

Hamiltoni tsükkel

• Tsüklit, mis läbib graafi kõik tipud täpselt üks kord, nimetatakse Hamiltoni tsükliks.
  

Hamiltoni graaf

• Graafi, kus leidub Hamiltoni tsükkel, nimetatakse Hamiltoni graafiks.
  

Näited

• Vaja külastada 5 linna, milline tee kõige lühem..(rändkaupmees).
  

Kontrollimine

• Hamiltoni tsükli olemasolu kontrolliks ei ole teada ühtegi kergesti kontrollitavat tarvilikku ja piisavat tingimust. See tähendab, et üldjuhul peame kontrolliks läbi vaatama kõik erinevad tippude järjestused.
  

42. Puu definitsioon. Leht, mets. Juurega puu. Näiteid. [2]

Puu

• Puuks nimetatakse graafi, mis on sidus ja ei sisalda tsükleid.
  
• Näited: ühetipuline graaf, ahel, …
  

Leht

• Puu rippuvaid tippe nimetatakse lehtedeks.
  

Mets

• Metsaks nimetatakse graafi, mille iga sidus komponent on puu.
  
• Iga graaf, mis ei sisalda tsükleid, on mets.
  

Juurega puu

• Juurega puuks nimetatakse puud, milles on välja eraldatud üks tipp, mida nimetatakse juureks.
  

• Juurega puud sobivad:
  hierarhiate kirjeldamiseks,
  otsingul või loendamisel läbivaadatavate variantide järjestamiseks jne.
  
• Lähtudes hierarhiatest kujutatakse informaatikas puid tavaliselt juurega üleval.
  
• Juurega puu tippe võib klassifitseerida kauguse järgi juurest.
  

43. Teoreem kahest lehest. [2]

• Teoreem 1. Igal lõplikul vähemalt kahetipulisel puul on vähemalt kaks lehte.
  
• Tõestus.
  

• Valime suvalise tipu ja liigume mööda servi, valides igal sammul uue serva. Kuna tsükleid ei ole, jõuame iga sammuga uude tippu. Lõpliku arvu sammude järel peame jõudma mingisse rippuvasse tippu u.
  
• Alustame tipust u ja liigume seni, kuni jõuame teise rippuvasse tippu v.
  

44. Puu servade arv. Kaks tõestust selle kohta. Puu konstrueerimine tippude lisamisega. [2]

Puu servade arvu tõestused

• Definitsiooni järgi on puu sidus tsükliteta graaf.
  
• Teoreem . Igal n-tipulisel puul on n - 1 serva.
  
• Tõestus. Üldisest teooriast graafide kohta teame:
  

• Kui n-tipulisel graafil on vähem kui n - 1 serva, siis see graaf on mittesidus.
  
• Igas graafis, milles on servi vähemalt sama palju kui tippe, leidub tsükkel.
  

• Teoreem. Igal n-tipulisel puul on n - 1 serva.
  

• Baas. Kui n = 1, siis väide kehtib. Ühetipulisel puul on 0 serva.
  
• Samm. Kehtigu väide kõikide puude korral, millel on k tippu. Vaatleme mingit k + 1 tipuga puud.
  
• Kustutame ühe lehe (miks alati leidub?) koos temaga intsidentse servaga.
  
• Järele jääb k-tipuline puu (miks puu?), tema servade arv on induktsiooni eelduse põhjal k - 1. Seega on esialgse graafi servade arv k.
  
• Järeldus. Tõestuses kirjeldatud sammude abil (lehte koos temaga intsidentse servaga kustutades) võib igast puust jõuda 1-tipulise graafini .
  

Puu konstrueerimine

• Iga puu saab konstrueerida järgmisel viisil.
  

• Alustame 1-tipulisest graafist.
  
• Igal sammul lisame ühe tipu ja ühendame ta mingi olemasoleva tipuga.
  

45. Tarvilikud ja piisavad tingimused, et graaf oleks puu. [2]

• Teoreem 3. Kui G on graaf, siis on järgmised väited samaväärsed.
  

G on puu

G on sidus, kuid ükskõik millise serva kustutamisel muutub mittesidusaks

G ei sisalda tsükleid, kuid ükskõik millise serva lisamisel tekib tsükkel

46. Puu tingimus lihtahelate kaudu. [2]

• Teoreem. Graaf G on puu parajasti siis, kui tema iga kahte erinevat tippu ühendab täpselt üks lihtahel.
  
• Tõestus.
  

Tarvilikkus. Olgu G puu. Et puu on sidus, siis G iga kahte tippu
u ja v ühendab vähemalt üks lihtahel. Kahte lihtahelat u ja v vahel olla ei saa, sest siis saaksime nende abil konstrueerida tsükli.
Piisavus. Ühendagu graafi G iga kahte erinevat tippu täpselt üks lihtahel. G on sidus, sest igast tipust pääseb igasse teise. G on tsükliteta, sest tsükli suvalise serva kahte otspunkti ühendab vähemalt kaks lihtahelat.

47. Märgendatud puu. Märgendatud puu Prüferi kood. Puu taastamine Prüferi koodi järgi. **Tõestus, et taastamisel saadakse igast koodist puu. ** Cayley teoreem. [2]

Märgendatud puu

• Puu, mille tipud on märgendatud arvudega 1, …, n.
  

Märgendatud puu Prüferi kood

• Prüferi koodi saame teatud viisil järjestatud servade loendist.
  
• Koostame kahe reaga tabeli, kus igal sammul
  1) leiame puus vähima märgendiga lehe,
  2) kirjutame lehe märgendi yi ülemisse ritta ja tema naabertipu märgendi xi tema alla alumisse ritta,
  3) kustutame puust selle lehe ja temaga intsidentse serva.
  
• Kordame seda seni, kuni kõik servad on kustutatud (n - 1 korda). Saame tabeli, kus iga veerg vastab ühele eemaldatud servale.
  
• Alati kehtib xn-1 = n, sest suurima märgendiga tipp jääb alati viimaseks.
  
• Prüferi koodi moodustavad tabeli alumise rea n - 2 arvu x1, x2, …, xn-2
  
• Sellega on näidatud , et igale puule märgenditega 1, …, n vastab üheselt tema Prüferi kood.
  

Puu taastamine Prüferi koodi järgi

• Olgu meil antud arvud x1, x2, …, xn-2, kus iga i korral 1  xi  n.
  
• Kirjutame järjendi lõppu arvu xn-1 = n ja konstrueerime tabeli ülemise rea.
  
• y1 peab olema vähim arv, mis ei esine alumises reas, sest esimesel sammul eemaldati vähima märgendiga leht.
  
• y2 peab olema vähim arv, mis pole y1 ja erineb arvudest
  x2, …, xn-1
  
• yi peab olema vähim arv, mis erineb arvudest y1, …, yi-1 ja arvudest xi, …, xn-1
  
• Selline arv leidub alati, sest arvudest 1, …, n on keelatud ülimalt n - 1 tükki .
  
• Tulemusena oleme saanud mingi graafi servade loendi. Osutub, et see graaf on alati puu.
  

Tõestus, et taastamisel saadakse igast koodist puu

• Näitame kõigepealt, et graaf on sidus.
  
• Suvalisest tipust märgendiga u saab liikuda tippu märgendiga n.
  
• Tabeli ülemises reas on kõik arvud 1, …, n - 1 mingis järjestuses, sest igaüks erineb kõigist eelmistest.
  
• Kui mingis tabeli veerus on üleval märgend u ja all v, siis v esineb ülemises reas märgendist u paremal.
  
• Järelikult saab tabelis paremale liikudes mööda servi tippu n.
  
• Seega on meil sidus n tipuga graaf, milles on n - 1 serva. Järelikult on tegemist puuga.
  

Cayley teoreem

• Teoreem. (Cayley, 1889). Erinevate n-tipuliste märgendatud puude arv on nn-2.
  
• Tõestus. Vastavus märgendatud n-tipuliste puude ja nende Prüferi koodide vahel on üksühene, sest tabeli taastamisel saame igal sammul samade tippude vahelise serva, mis eemaldati tabeli loomisel esialgsest graafist.
  
• Järelikult on märgendatud puid sama palju kui Prüferi koode, st järjendeid pikkusega n - 2, kus iga element võib omandada n erinevat väärtust.
  

48. Suunatud graafi definitsioon. Tipud, kaared. Alusgraaf. Suunatud graafi Boole’i maatriks. [2]

Suunatud graaf, tipud, kaared

• DEF: Suunatud graafiks nimetatakse paari G = (V, E), kus V on mittetühi hulk ning E hulk, mis koosneb hulga V elementide järjestatud paaridest.
  

• Paare nimetame graafi kaarteks. Kaart tipust u tippu v tähistame (u, v) või uv.
  

V E = Alusgraaf

• DEF: Igale suunatud graafile vastab alusgraaf, kus kaared on asendatud suunamata servadega.
  

Suunatud graafi Boole’i maatriks

• Suunatud graafi saab esitada nullidest ja ühtedest koosneva maatriksina, mis ei tarvitse enam olla sümmeetriline peadiagonaali suhtes.
  

49. Sisendaste ja väljundaste . Teoreem sisendastmete ja väljundastmete summast. [2]

Sisendaste

• Tipu v sisendaste d+(v) on tippu v sisenevate kaarte arv.
  

Väljundaste

• Tipu v väljundaste d-(v) on tipust v väljuvate kaarte arv.
  

Teoreem sisendastme ja väljundastme summast

• Teoreem. Igas suunatud graafis on tippude sisendastmete summa võrdne tippude väljundastmete summaga .
  
• Kui suunatud graafi alusgraaf ei ole sidus, siis kehtib teoreem ka alusgraafi iga sidusa komponendi kohta eraldi.
  

50. Suunatud ahel, suunatud tsükkel, lihtahel ja lihttsükkel. Suunatud graafide isomorfism. Isomorfismi ja mitteisomorfismi näitamine. [2]

Suunatud ahel

• DEF: Suunatud ahel on tippude järjend v0v1…vk, kus iga kaks järjestikust tippu vi ja vi+1 on ühendatud kaarega vivi+1.
  

Suunatud tsükkel

• DEF: Suunatud tsükkel on suunatud ahel, mis algab ja lõpeb samas tipus.
  

51. Tugev ja nõrk sidusus. Näited. Tugeva sidususe komponendid. [2]

Tugev sidusus

• Suunatud graafi nimetatakse tugevalt sidusaks, kui iga kahe tipu u ja v korral leidub suunatud ahel tipust u tippu v.
  
• Tugevalt sidusaks loeme ka ühetipulist suunatud graafi.
  

Nõrk siusus

• Suunatud graafi nimetatakse nõrgalt sidusaks, kui graafi alusgraaf on sidus.
  
• Seega tugeva sidususe puhul liigume ühest tipust teise kaarte suundi arvestades, nõrga sidususe puhul aga suundi arvestamata.
  

Tugeva sidususe komponendid

• Suunatud graafi tugevalt sidus komponent on selline tugevalt sidus alamgraaf, mis ei sisaldu üheski teises tugevalt sidusas alamgraafis.
  
• Tippu u sisaldav tugevalt sidus komponent koosneb kõigist sellistest tippudest v, et
  1) on võimalik liikuda tipust u mööda suunatud ahelat tippu v ja
  2) on võimalik liikuda tipust v mööda suunatud ahelat tippu u.
  
• Graaf on tugevalt sidus parajasti siis, kui tal on täpselt üks tugevalt sidus komponent.
  

52. Teoreem suundade määramisest, et tekiks tugevalt sidus graaf. [2]

• Teoreem. Kui sidusas graafis ei leidu ühtegi silda, siis saab graafi servadele määrata suunad nii, et tekkinud graaf on tugevalt sidus.
  
• Tõestuse idee. Leiame graafis tsükli ja lisame sellele järk-järgult juurde ülejäänud tippe ühendavaid ahelaid.
  
• Järeldus. Sildade olemasolu korral saame tugevalt sidusa graafi, kui sillad asendada kahe kaarega (mõlemas suunas).
  

53. Lühima tee leidmise ülesanne suunatud graafis. Floyd -Warshalli algoritm. [2]

Lühima tee leidmise ülesanne suunatud graafis

• Antud on suunatud graaf, mille igale kaarele on omistatud kaal (mittenegatiivne reaalarv).
  Leida kahe antud tipu vahel suunatud ahel, millesse kuuluvate servade kaalude summa on vähim võimalik.
  
• Lahendusmeetod on dünaamiline planeerimine , kus lahend leitakse samm-sammult üha pikemaid ahelaid vaadeldes.
  
• Floyd-Warshalli algoritm (1962).
  

Floyd-Warshalli algoritm
Algväärtused:
Täidetakse 3-kordne tsükkel:
iga k = 1, 2, …, n korral,
iga i = 1, 2, …, n korral,
iga j = 1, 2, …, n korral:
kui aik + akj aij uus väärtus on aik + akj ja
bij uus väärtus on bik.
Asenduse idee:
kui tipust
tippu
ja sealt tippu
liikudes on tee lühem, kui seni leitud lühim tee tipust
tippu , siis liigume läbi tipu .
Näide

54. ** Floyd-Warshalli algoritmi keerukuse hinnang ja korrektsuse tõestus. [2]

Floys-Warshalli algoritmi keerukuse hinnang

• Miks leiab Floyd-Warshalli algoritm tõesti lühima võimaliku ahela iga kahe tipu vahel?
  
• Kui lühima ahela i  …  j suurima indeksiga sisetipp on k, siis on algoritmi varasematel sammudel juba leitud lühimad ahelad i  …  k ja k  …  j ning otsitav lühim ahel leitakse seega üles k-ndal sammul.
  

Tõestus

• Korrektsuse teoreemi võib sõnastada nii:
  

Iga n korral kehtib: kui n on graafi tippude arv, siis Floyd-Warshalli algoritm annab etapi n tulemuseks maatriksi, kus
on lühima tee pikkus tipust
tippu .
Sisemise väite tõestamiseks asendame ta parameetrist k sõltuva väitega:

• Lemma . Etapi k (0kn) järel on lühima sellise tee pikkus, kus tipust tippu liikumiseks võib läbida vahetippe .
  

Selge, et k = n puhul saame siit algoritmi korrektsuse.
Lemma 1 tõestame induktsiooniga
järgi.

• Lemma. Etapi k (0kn) järel on lühima sellise tee pikkus, kus tipust tippu liikumiseks võib läbida vahetippe .
  
• Tõestame induktsiooniga k järgi.
  
• Induktsiooni baas. Kui , siis on lemma väide tõene.
  
• tähendab, et vahetippe olla ei tohi. Algväärtustamine rahuldab lemma tingimust.
  
• Lemma. Etapi k (0kn) järel on lühima sellise tee pikkus, kus tipust tippu liikumiseks võib läbida vahetippe .
  
• Induktsiooni samm. Kui lemma 1 väide on tõene etapi järel, siis ta on tõene ka etapi järel.
  

Kui lühim tee, mis võib läbida vahetippe , ei sisalda tippu , siis on ta induktsiooni eelduse järgi juba leitud enne etappi .

Kui lühim tee, mis võib läbida vahetippe , sisaldab tippu , siis see tee sisaldab tippu ühe korra ja teda saab jagada kaheks osaks.
Induktsiooni eelduse järgi on etapi k alguseks:
= lühima sellise tee pikkus tipust tippu , kus võib läbida vahetippe ja
lühima sellise tee pikkus tipust tippu , kus võib läbida vahetippe
Need kaks teed kokku annavad lühima tee tipust tippu , kus võib läbida vahetippe .
46