Graafid ja matemaatiline loogika eksamimaterjal (0)

Tartu Ülikool - Matemaatika - Algebra I

1 HALB

Kevad - Vesised teed, sulav lumi, tärkavad lumikellukesed - teebki kevadest kevade

MATEMAATILINE LOOGIKA

LAUSEARVUTUS
Lausearvutuse tehted :

Eitus (¬)
Konjuktsioon (&)
Disjunktsioon (V)
Implikatsioon (->)
Ekvivalents ()

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), (FVG), (F->G) ja (FG) on lausearvutuse valemid
Lausearvutuse valemi F tõeväärtus etteantud väärtustusel leitakse järgmiste reeglite abil:
- 1) Kui F = ¬G, siis F = 1 parajasti siis, kui G = 0
- 2) Kui F = G & H, siis F = 1 parajasti siis, kui G = 1 ja H = 1
- 3) Kui F = G ∨ H, siis F = 1 parajasti siis, kui G = 1 või H = 1
- 4) Kui F = G → H, siis F = 1 parajasti siis, kui G = 0 või H = 1
- 5) Kui F = G ↔ H, siis F = 1 parajasti siis, kui G = 1 ja H = 1 või G = 0 ja H = 0

F
G
F&G
FVG
F->G
FG
¬F
T
T
T
T
T
T
V
T
V
V
T
V
V
V
V
T
V
T
T
V
T
V
V
V
V
T
T
T

Lausearvtuse valemit F nimetatakse samaselt tõeseks, kui ta on igal väärtustusel tõene
Lausearvutuse valemit F nimetatakse samaselt vääraks, kui ta on igal väärtustusel väär
Lausearvutuse valemit F nimetatakse kehtestatavaks, kui ta on vähemalt ühel väärtustusel tõene

Valemeid F ja G nimetatakse samaväärseteks, kui nende tõeväärtused on võrdsed igal neis valemeid esinevate muutujate väärtustusel
Ü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

Lausearvutuse põhisamaväärsused eraldi lehel!!

NORMAALKUJUD

Lausearvutuse valemi F täielikuks disjunktiivseks normaalkujuks (TDNK) nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate täielike elementaarkonjuktsioonide disjunktsiooni
- Täielik disjunktiivne normaalkuju on tõene parajasti nendel väärtustustel, mis vastavad normaalkuju liikmetele
- X1α11 & … & Xnα1n ∨ X1α21 & … & Xnα2n ∨ …∨ X1αm1 & … & Xnαmn on tõene väärtustustel (α11, …, α1n), (α21, …, α2n), …, (αm1, …, αmn) ja väär kõigil ülejäänud väärtustustel
- TDNK-le viimine :
  - Koostame valemi põhjal tõeväärtustabeli
  - Vaatame vaid neid ridu, mil valem on tõene
  - Koostame konjuktsioonid ridadele vastavatest elementide tõeväärtustest (nt kui X=t, Y=t ja Z=v, siis saame X&Y&¬Z)
  - Ühendame saadud konjuktsioonid ühiseks disjunktsiooniks
- TDNK-le viimise algoritm :
  - Elimineerida implikatsioonid ja ekvivalentsid
  - Viia eitused vahetult lausemuutujate ette (st konjunktsioonide ja disjunktsioonide sisse)
  - Korrutada disjunktsioonid läbi (distributiivsuse seaduse abil)
  - Kaotada samaselt väärad konjunktsioonid ja sama liikme mitmekordsed esinemised konjunktsioonides
  - Lisada konjunktsioonidele puuduvad muutujad
  - Korrastada valem (järjestada muutujad konjunktsioonides ja kaotada korduvad konjunktsioonid)
- TDNK leidub igal kehtestataval valemil ja on üheselt määratud täielike elementaarkonjuktsioonide järjekorra täpsusega
Lausearvutuse valemi F täielikuks konjuktiivseks normaalkujuks (TKNK) nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate täielike elementaardisjunktsioonide konjuktsiooni
- (X1α11 V … V Xnα1n) & (X1α21 V … V Xnα2n) & …& (X1αm1 V … V Xnαmn) on väär väärtustustel (¬α11, …, ¬α1n), (¬α21, …, ¬α2n), …, (¬αm1, …, ¬αmn) ja tõene kõigil ülejäänud väärtustustel.TKNK-le viimine:
  - Koostame valemi põhjal tõeväärtustabeli
  - Vaatame vaid neid ridu, mil valem on väär
  - Koostame disjunktsioonid ridadele vastavatest elementide vastandtõeväärtustest (nt kui X=t, Y=t ja Z=v, siis saame ¬Xv¬YvZ)
  - Ühendame saadud disjunktsioonid ühiseks konjuktsiooniks (tuleb silmas pidada seda, et konjuktsioon on prioriteetsem tehe, seega peab kasutama sulge )
- TKNK-le viimise algoritm:
  - Elimineerida implikatsioonid ja ekvivalentsid
  - Viia eitused vahetult lausemuutujate ette (st konjunktsioonide ja disjunktsioonide sisse)
  - „Liita“ konjunktsioonid läbi (teise distributiivsuse seaduse abil)
  - Kaotada samaselt tõesed disjunktsioonid ja sama liikme mitmekordsed esinemised disjunktsioonides
  - Lisada disjunktsioonidele puuduvad muutujad
  - Korrastada valem (järjestada muutujad disjunktsioonides ja kaotada korduvad disjunktsioonid)

Lausearvutuse valemid A(X1 ,…, Xn ) ja B(X1 ,…, Xn ) on loogiliselt samaväärsed parajasti siis, kui nende TDNK-d koosnevad samadest elementaarkonjunktsioonidest
Lausearvutuse valemist A(X1 ,…, Xn ) järeldub valem B(X1 ,…, Xn ) parajasti siis, kui B täielik disjunktiivne normaalkuju sisaldab kõiki A normaalkuju liikmeid
Iga Boole ’i funktsiooni f(x1 , … , xn ) saab esitada lausearvutuse valemina milles ei ole muid tehtemärke kui &,  ja 
- Boole’i funktsioon on funktsioon 𝑓(x1 , … , xn )𝑛 →. Ka tõeväärtustel defineeritud funktsioone võib vaadelda Boole’i funktsioonidena, iga lausearvutuse tehe on Boole’i funktsioon
Venni diagrammide leidmine tähendab, et viime vaadeldavad avaldised TDNK-le, et neid saaks võrrelda

PREDIKAADID JA KVANTORID

Hulgal M määratud n-kohaliseks predikaadiks nimetatakse kujtust P: Mn ->
- Hulka, millel predikaat on määratud, nimetatakse selle predikaadi indiviidide piirkonnaks
- Vastavalt predikaadi definitsioonile saame igale predikaadile 𝑃 seada vastavusse tema tõesuspiirkonna 𝑇𝑃

Olgu P(𝑥1, … , 𝑥𝑛) hulgal 𝑀 defineeritud 𝑛- kohaline predikaat. Siis iga 𝑖 ≤ 𝑛 korral tähistavad ∀𝑥𝑖P(𝑥1, … , 𝑥𝑛) ja ∃𝑥𝑖P(𝑥1, … , 𝑥𝑛) järgmisi (𝑛 − 1)-kohalisi predikaate:
- ∀𝑥𝑖P(𝑥1, … , 𝑥𝑛), siis ∀𝑥𝑖P(𝑥1, … , 𝑥𝑛)= P(𝑥1, … , 𝑥𝑖−1, 𝑚1, 𝑚𝑖+1, … , 𝑚𝑛) & … & P(𝑥1, …, 𝑥𝑖−1, 𝑚𝑘, 𝑚𝑖+1, … , 𝑚n)
- Olemasolu kvantori saab samal viisil väljendada disjunktsioonide kaudu

Konstantsümbolid (a, b, c, …) tähistavad vaadeldava hulga mingeid kindlaid elemente
Funktsionaalsümbolid (f, g, h, …) tähistavad vaadeldaval hulgal määratud funtksioone
Predikaatsümboleid kasutatakse elementide omaduste ja nendevaheliste seoste kirjapanemiseks
Termid on parajasti need, mida saab koostada järgnevate reeglite abil:
- Iga indiviidmuutuja on term
- Iga konstantsümbol on term
- Kui f on n-kohaline funktsionaalsümbol ja t1, t2, ... , tn on termid, siis f(t1, t2, … , tn) on term
Predikaatarvutuse valemid on parajasti need, mida saab koostada alltoodud reeglite abil:
- Kui P on n-kohaline predikaatsümbol ja t1, t2, ... , tn on termid, siis P(t1, t2, … , tn) on predikaatarvutuse valem
- Kui F on predikaatarvutuse valem, siis ¬F on predikaatarvutuse valem
- Kui F ja G on predikaatarvutuse valemid, siis (F & G), (F ∨ G), (F → G) ja (F ↔ G) on predikaatarvutuse valemid
- Kui x on indiviidmuutuja ja F on predikaatarvutuse valem, siis ∀xF ja ∃xF on predikaatarvutuse valemid
Indiviidmuutuja x esineb valemis F seotult, kui ta asub mingi kvantori mõjupiirkonnas, st osavalemit ∀xG või ∃xG moodustavas valemis G. Ülejäänud esinemisi nimetatakse vabadeks.
Valemit nimetatakse kinniseks, kui tema kõigi indiviidmuutujate kõik esinemised on seotud

Interpretatsioon on paar α = (Mα, Iα), kus Mα on mingi mittetühi hulk, mida nimetatakse põhihulgaks ehk interpretatsiooni kandjaks, ja Iα on interpreteeriv kujutus, mis teisendab:
- iga konstantsümboli hulga Mα mingiks elemendiks
- iga n-kohalise funktsionaalsümboli mingiks (kõikjal määratud) n-kohaliseks funktsiooniks hulgal Mα
- iga n-kohalise predikaatsümboli mingiks n-kohaliseks predikaadiks hulgal Mα
Predikaatarvutuse valemi F tõeväärtus Fα interpretatsioonis α vabade muutujate fikseeritud väärtustel leitakse järgmiste reeglite abil:
- Kui F = P(t1, t2, … , tn), kus P on n-kohaline predikaatsümbol ja t1, t2, … , tn on termid, siis Fα = 1 parajasti siis, kui Pα(t1α , t2α, ... , tnα) = 1
- Kui F = ¬G, siis Fα = 1 parajasti siis, kui Gα = 0
- Kui F = G&H, siis Fα = 1 parajasti siis, kui Gα = 1 ja Hα = 1
- Kui F = G∨H, siis Fα = 1 parajasti siis, kui Gα = 1 või Hα = 1
- Kui F = G→H, siis Fα = 1 parajasti siis, kui Gα = 0 või Hα = 1
- Kui F = G↔H, siis Fα = 1 parajasti siis, kui Gα = 1 ja Hα = 1 või Gα = 0 ja Hα = 0
- Kui F = ∀xG, siis Fα = 1 parajasti siis, kui põhihulga Mα iga elemendi m korral G[x/m]α = 1, kus [x/m] tähendab, et muutuja x väärtuseks loetakse element m
- Kui F = ∃xG, siis Fα = 1 parajasti siis, kui põhihulgas Mα leidub selline element m, et G[x/m]α = 1, kus [x/m] tähendab, et muutuja x väärtuseks loetakse element m

Predikaatarvutuse valemit F nimetatakse samaselt tõeseks, kui ta on tõene signatuuris  igas interpretatsioonis oma vabade muutujate kõikidel väärtustustel
Predikaatarvutuse valemit F nimetatakse samaselt vääraks, kui ta on väär signatuuris  igas interpretatsioonis oma vabade muutujate kõikidel väärtustustel
Predikaatarvutuse valemit F nimetatakse kehtestatavaks, kui ta on tõene vähemalt ühes signatuuris  interpretatsioonis valemi vabade muutujate mingitel väärtustel
Ütleme, et valemitest F1, F2, ... , Fn järeldub valem G, kui igas interpretatsioonis valemite vabade muutujate kõikidel väärtustel, kus valemid F1, F2, ... , Fn on tõesed, on ka valem G tõene
Valemeid F ja G nimetatakse samaväärseteks, kui nende tõeväärtused on võrdsed igas interpretatsioonis valemite vabade muutujate kõikidel väärtustel
Churchi teoreem : ei leidu algoritmi , mis suudaks suvalise predikaatloogika valemi puhul kindlaks teha, kas valem on samaselt tõene

Igasuguse lõpliku võimsusega ja loenduva hulga interpretatsioonide vaatlemine on vajalik, sest saab konstrueerida valemi, mis on tõene parajasti siis, kui kandjas on n elementi, ja saab konstrueerida kehtestatava valemi, mis on väär igas lõpliku kandjaga interpretatsioonis
Kui signatuur on lõplik või loenduv , siis loenduvast suuremate kandjate vaatlemine pole vajalik

t on juba olemasolev sisse toodud tähis ja c on uus konstant, mis tuuakse sisse

Ütleme, et valem F on prefikskujul, kui F = Q1x1Q2x2 ... QnxnF ′ , kus Q1, Q2, … , Qn on kvantorid, x1, x2, ... , xn indiviidmuutujad ja F′ kvantoriteta valem, mida nimetatakse valemi F maatriksiks
- Prefikskujule viimise algoritm:
  - Avaldame implikatsiooni ja ekvivalentsi teiste tehete kaudu
  - Viime eitused kvantorite alla
  - Nimetame ümber seotud muutujad
  - Toome kõik kvantorid sulgude ette

TÕESTUSTAKTIKAD

Teoreemi üldkuju: kui on täidetud eeldused E1, …, Ne, siis kehtib väide V

Väide on kujul B&C

Eeldus on kujul B&C

Väide on kujul BvC

Eeldus on kujul BvC

Väide on kujul B->C

Eeldus on kujul B->C

Väide on kujul B

Eeldus on kujul B

Väide on kujul BC

Eeldus on kujul BC

Väide on kujul 𝒙𝑩(𝒙)

Eeldus on kujul 𝒙𝑨(𝒙)

Väide on kujul 𝒙𝑩(𝒙)

Eeldus kujul 𝒙𝑩(𝒙)

AKSIOMAATILISED TEOORIAD

Mitteformaalse aksiomaatilise teooria skeem:
- Fikseeritakse mingi hulk antud teoorias uuritavaid objekte, nendel defineeritud funktsioone ja seoseid ning sümboolika nende tähistamiseks
- Teatud hulk väiteid loetakse tõesteks a priori (ilma tõestuseta). Neid väiteid nimetatakse selle teooria aksioomideks
- Teooria arendamine seisneb nn. teoreemide tõestamises. Teoreemideks loetakse väiteid, mida saab tõestada „ainult aksioome kasutades“. Väidete mugavamaks sõnastamiseks võidakse olemasolevate mõistete baasil defineerida uusi
Peano aritmeetika aksioomid:
- ∀𝑥¬ 𝑥 ′ = 0
- ∀𝑥∀𝑦 𝑥 ′ = 𝑦 ′ ⊃ 𝑥 = 𝑦
- ∀𝑥[𝑥 + 0 = 𝑥]
- ∀𝑥∀𝑦[𝑥 + 𝑦 ′ = (𝑥 + 𝑦)′]
- ∀𝑥[𝑥 ⋅ 0 = 0]
- ∀𝑥∀𝑦[𝑥 ⋅ 𝑦 ′ = 𝑥 ⋅ 𝑦 + 𝑥]
- Kõik valemid kujul 𝐴 0 &∀𝑥[𝐴 𝑥 ⊃ 𝐴 𝑥 ′ ] ⊃ ∀𝑥𝐴 𝑥
  - Aksioomidest P1-P2 saame, et on olemas lõpmatu naturaalarvude jada 0, 0 ′ , 0 ′′ , 0 ′′′ , … . Tavaliselt tähistame neid arve 0, 1, 2, 3, 4, … , 2017 , …
  - Aksioomid P3-P4 defineerivad naturaalarvude liitmise
  - Aksioomid P5-P6 defineerivad naturaalarvude korrutamise
  - Induktsiooniskeem P7 annab meile lisaks varasemale veel ühe taktika väidete ∀𝑥𝐴 𝑥 tõestamiseks naturaalarvude jaoks:
    - Me teame, et valem 𝐴 0 & ∀𝑥[𝐴 𝑥 ⊃ 𝐴 𝑥 ′ ] ⊃ ∀𝑥𝐴 𝑥 on tõene
    - Seega on ∀𝑥𝐴 𝑥 tõestamiseks piisav tõestada kahe valemi tõesus:

1) 𝐴 0 (induktsiooni baas),
2) ∀𝑥[𝐴 𝑥 ⊃ 𝐴 𝑥 ′ ] (induktsiooni samm)
Liitmise assotsiatiivsus

Naturaalarvude liitmine on assotsiatiivne: ∀𝑥∀𝑦∀𝑧[𝑥 + (𝑦 + 𝑧) = (𝑥 + 𝑦) + 𝑧]

Tõestus:

Kahe välimise üldisuse kvantori jaoks kasutame otsese tõestamise taktikat. Tähistagu 𝑎 ja 𝑏 suvalisi naturaalarve. Piisab , kui tõestame ∀𝑧[𝑎 + (𝑏 + 𝑧) = (𝑎 + 𝑏) + 𝑧]
Kasutame siin üldisuse kvantoriga väite tõestamiseks induktsiooni muutuja z järgi. Siis on vaja tõestada:
- Lemma 1.1 𝑎 + (𝑏 + 0) = (𝑎 + 𝑏) + 0 (baaslemma)
- Lemma 1.2 ∀𝑧[( 𝑎 + (𝑏 + 𝑧) = (𝑎 + 𝑏) + 𝑧) ⊃ (𝑎 + (𝑏 + 𝑧′) = (𝑎 + 𝑏) + 𝑧′)] (sammulemma)

Lemma 1.1 tõestuseks rakendame kummalgi pool aksioomi P3:
Vasak pool: 𝑎 + (𝑏 + 0) = 𝑎 + 𝑏,
Parem pool: (𝑎 + 𝑏) + 0 = 𝑎 + 𝑏.
Järelikult on vasak ja parem pool tõepoolest võrdsed.
Lemma 1.2 tõestus. Üldisuse kvantoriga lemma 1.2 tõestamiseks tähistagu c suvalist naturaalarvu . Peame tõestama (𝑎 + (𝑏 + 𝑐) = (𝑎 + 𝑏) + 𝑐 ) ⊃ (𝑎 + (𝑏 + 𝑐′) = (𝑎 + 𝑏) + 𝑐′)]
Selle implikatsiooni tõestamiseks olgu implikatsiooni vasak pool 𝑎 +( 𝑏 + 𝑐) = (𝑎 + 𝑏) + 𝑐 tõene.
Näitame, et siis kehtib ka parem pool 𝑎 +( 𝑏 + 𝑐′) = (𝑎 + 𝑏) + 𝑐′.
Rakendame võrduse vasakule poolele kaks korda liitmise teist aksioomi.
Saame: 𝑎 + (𝑏 + 𝑐′) = 𝑎 + (𝑏 + 𝑐)′ = (𝑎 + (𝑏 + 𝑐))′
Sulgude sees rakendame implikatsiooni eeldust ja edasi viime teist liitmise aksioomi paremalt vasakule rakendades funktsiooni ’ summa teisele liikmele: (𝑎 + (𝑏 + 𝑐 ))’ = ((𝑎 + 𝑏) + 𝑐)’ = (𝑎 + 𝑏) + 𝑐 ′ .
Seega on vasak ja parem pool tõesti võrdsed.
Liitmise kommutatiivsus

Naturaalarvude liitmine on kommutatiivne: ∀𝑥∀𝑦[𝑥 + 𝑦 = 𝑦 + 𝑥]

Tõestus:
Liitmise kommutatiivsuse tõestamiseks kasutame kõigepealt induktsiooni muutuja 𝑥 järgi ja selle induktsiooniga tekkivas kummaski lemmas veel induktsiooni 𝑦 järgi.
Induktsioonis muutuja 𝑥 järgi on aksioomis P7 oleva valemi A(x) rollis on ∀𝑦[𝑥 + 𝑦 = 𝑦 + 𝑥] . Tuleb tõestada kaks lemmat:

Lemma 2.1 (induktsiooni baas). ∀𝑦[0 + 𝑦 = 𝑦 + 0]
Lemma 2.2 (induktsiooni samm) ∀𝑥 [∀𝑦[ 𝑥 + 𝑦 = 𝑦 + 𝑥] ⊃ ∀𝑦[ 𝑥 ′ + 𝑦 = 𝑦 + 𝑥 ′]]

Baaslemma ∀𝑦[0 + 𝑦 = 𝑦 + 0] tõestus
Tõestame induktsiooniga y järgi:
Lemma 2.1.1. 0 + 0 = 0 + 0. Selle lemma kehtimine on ilmne.
Lemma 2.1.2. ∀𝑦[0 + 𝑦 = 𝑦 + 0 ⊃ 0 + 𝑦′ = 𝑦′ + 0].
Selle üldisuse kvantoriga valemi tõestamiseks tähistagu 𝑎 suvalist naturaalarvu. Piisab, kui tõestame 0 + 𝑎 = 𝑎 + 0 ⊃ 0 + 𝑎′ = 𝑎′ + 0. (*)
Olgu implikatsiooni vasak pool 0 + 𝑎 = 𝑎 + 0 tõene. Meil on vaja tõestada, et kehtib 0 + 𝑎′ = 𝑎′ + 0.
Teisendame selle võrduse vasakut poolt aksioome ja implikatsiooni vasakut poolt kasutades:
0 + 𝑎 ′ = (0 + 𝑎) ′ = (𝑎 + 0) ′ = 𝑎 ′ = 𝑎 ′ + 0
Sellega on lemma 2.1.2 ja ka kogu lemma 2.1 tõestatud.
𝐋𝐞𝐦𝐦𝐚 𝟐. 𝟐 𝐭õ𝐞𝐬𝐭𝐮𝐬
Peame tõestama üldisuse kvantoriga väite. Tähistagu 𝑏 suvalist naturaalarvu. Asendades 𝑥 asemele 𝑏, saame, et tuleb tõestada [∀𝑦 [𝑏 + 𝑦 = 𝑦 + 𝑏] ⊃ ∀𝑦[ 𝑏 ′ + 𝑦 = 𝑦 + 𝑏 ′] .
Selle implikatsiooni tõestamiseks eeldame, et kehtib tema vasak pool ∀𝑦 [𝑏 + 𝑦 = 𝑦 + 𝑏] (**). Näitame, et siis ka parem pool ∀𝑦 [𝑏 ′ + 𝑦 = 𝑦 + 𝑏 ′] on tõene.
Tõestame üldisuse kvantoriga väite ∀𝑦 [𝑏 ′ + 𝑦 = 𝑦 + 𝑏] ′ induktsiooniga 𝑦 järgi. Selleks on vaja tõestada kaks lemmat:

Lemma 2.2.1 (Induktsiooni baas). 𝑏 ′ + 0 = 0 + 𝑏 ′
Lemma 2.2.2 (Induktsiooni samm). ∀𝑦[(𝑏 ′ + 𝑦 = 𝑦 + 𝑏 ′ ) ⊃ (𝑏 ′+𝑦′ = 𝑦′ + 𝑏 ′ )].

Lemma 2.2.1 järeldub juba tõestatud lemmast 2.1 (0 liitmine kommuteerub).
Lemma 2.2.2 tõestus
Tähistagu 𝑐 suvalist naturaalarvu. Peame tõestama (𝑏 ′ + 𝑐 = 𝑐 + 𝑏 ′ ) ⊃ (𝑏 ′+𝑐′ = 𝑐′ + 𝑏 ′ ).
Implikatsiooni tõestamisel eeldame, et 𝑏 ′ + 𝑐 = 𝑐 + 𝑏 ′ (***) ja tõestame 𝑏 ′ + 𝑐′ = 𝑐′ + 𝑏′.
Teisendame viimase võrduse vasakut poolt: 𝑏 ′ + 𝑐 ′ = (𝑏 ′+𝑐)′ = (𝑐 + 𝑏′)′ = (𝑐 + 𝑏)′′ = (𝑏 + 𝑐 )′′ = (𝑏 + 𝑐 ′) ′ = (𝑐 ′ + 𝑏 )′ = 𝑐 ′ + 𝑏 ′ .
Teisenduse sammudel on kasutatud: P4, implik eeldus (***), P4, kommuteerumise eedus b kohta (**), P4, implik eeldus (***).
Sellega on lemma 2.2.2 tõestatud ja ka lemma 2.2 ning teoreem 2.
Liitmise distributiivsus

Kehtib järgmine naturaalarvude liitmise ja korrutamise distributiivsuse seadus:

∀𝑥∀𝑦∀𝑧[𝑥 ∙ (𝑦 + 𝑧) = 𝑥 ∙ 𝑦 + 𝑥 ∙ 𝑧]
Tõestus:
Rakendame kahe välimise üldisuse kvantori suhtes otsest taktikat. Tähistagu 𝑎 ja 𝑏 suvalisi naturaalarve. On piisav, kui tõestame ∀𝑧[𝑎 ∙ (𝑏 + 𝑧) = 𝑎 ∙ 𝑏 + 𝑎 ∙ 𝑧].
Muutuja 𝑧 jaoks kasutame induktsiooni. Siis tuleb tõestada kaks lemmat:

Lemma 3.1 (baaslemma). 𝑎 ∙ (𝑏 + 0) = 𝑎 ∙ 𝑏 + 𝑎 ∙ 0.
Lemma 3.2 (sammulemma). ∀𝑧[ 𝑎( ∙( 𝑏 + 𝑧) = 𝑎 ∙ 𝑏 + 𝑎 ∙ 𝑧 )⊃ (𝑎 ∙( 𝑏 + 𝑧 ′) = 𝑎 ∙ 𝑏 + 𝑎 ∙ 𝑧′

Lemma 3.1 𝑎 ∙ (𝑏 + 0) = 𝑎 ∙ 𝑏 + 𝑎 ∙ 0 tõestus
Lihtsustame võrduse vasakut poolt, kasutades aksioomi P3:
𝑎 ∙ (𝑏 + 0) = 𝑎 ∙ 𝑏.
Paremal pool rakendame kõigepealt aksioomi P5 ja siis P3.
Saame: 𝑎 ∙ 𝑏 + 𝑎 ∙ 0 = 𝑎 ∙ 𝑏 + 0 = 𝑎 ∙ 𝑏.
Seega lemmas väidetav võrdus kehtib.
Lemma 3.2 tõestus
Üldisuse kvantoriga väite ∀𝑧 [𝑎 (∙ (𝑏 + 𝑧) = 𝑎 ∙ 𝑏 + 𝑎 ∙ 𝑧) ⊃ (𝑎 ∙( 𝑏 + 𝑧 ′) = 𝑎 ∙ 𝑏 + 𝑎 ∙ 𝑧′ tõestamiseks tähistagu 𝑐 suvalist naturaalarvu.
Tõestame, et (𝑎 ∙ (𝑏 + 𝑐) = 𝑎 ∙ 𝑏 + 𝑎 ∙ 𝑐 )⊃ 𝑎 ∙ (𝑏 + 𝑐 ′) = 𝑎 ∙ 𝑏 + 𝑎 ∙ 𝑐 ′
Implikatsiooni tõestamiseks eeldame 𝑎 ∙ (𝑏 + 𝑐) = 𝑎 ∙ 𝑏 + 𝑎 ∙ 𝑐 ja näitame, et siis on tõene ka 𝑎 ∙ (𝑏 + 𝑐 ′) = 𝑎 ∙ 𝑏 + 𝑎 ∙ 𝑐 ′
Teisendame võrduse vasakut poolt, kuni saame parema poole:
𝑎 ∙ (𝑏 + 𝑐 ′) = 𝑎 ∙ (𝑏 + 𝑐) ′ = 𝑎 ∙ (𝑏 + 𝑐) + 𝑎 = (𝑎 ∙ 𝑏 + 𝑎 ∙ 𝑐 )+ 𝑎 = 𝑎 ∙ 𝑏 + (𝑎 ∙ 𝑐 + 𝑎 )= 𝑎 ∙ 𝑏 + 𝑎 ∙ 𝑐′
Teisendusteks kasutasime: liitmise aksioomi P4, korrutamise aksioomi P6, implikatsiooni vasakut poolt, liitmise assotsiatiivsust, aksioomi P6.
Sellega on L 3.2 ja teoreem 3 tõestatud.
GRAAFID

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 nimetatakse graafi servadeks
Multigraaf on graaf, mis võimaldab serva, mis ühendab tippu iseendaga , ning võimaldab mitut erinevat serva kahe antud tipu vahel
Täisgraafiks nimetatakse n-tipulist graafi, kui selles graafis on olemas serv iga kahe tipupaari vahel
Nullgraafiks nimetatakse n-tipulist graafi, kui selles graafis pole serva ühegi tipupaari vahel
Graafi G täiendgraafiks nimetatakse graafi, millel on sama tippude hulk nagu graafil G, aga servaga on ühendatud parajasti need tipud , mille vahel graafis G serv puudub
Kaalutud graafiks nimetatakse graafi, mille igale servale on vastavusse seatud üks reaalarv (kaal)
Kui graafi tipp v kuulub servale e, siis öeldakse, et tipp v ja serv e on intsidentsed
Graafi tippe u ja v nimetatakse naabertippudeks, kui nad on servaga ühendatud
Olgu G=(V,E) graaf tippude hulgaganaabrusmaatriks on n x n- maatriks A=(aij), kus aij=1, kui graafis G on tipud vi ja vj servaga ühendatud, 0 vastasel juhul
Graafi G’=(V’,E’), mis on saadud graafist G=(V,E) teatava hulga tippude ja servade kustutamisel , nimetatakse graafi G alamgraafiks
Graafi tipuga v intsidentsete servade arvu nimetatakse tipu v astmeks
Tipuastmete teoreem: igas graafis on kõigi tippude astmete summa võrdne servade arvu kahekordsega
- Järeldus: igas graafis on paaritu astmega tippe paarisarv
Regulaarseks graafiks nimetatakse graafi, mille kõigi tippude astmed on võrdsed

Ahelaks nimetatakse graafi tippude järjendit v0, v1, …, vk (k≥0), kus iga kaks järjestikust tippu on servaga ühendatud
- Tipud v0 ja vk on ahela otstipud
- Ülejäänud tipud on ahela sisetipud
Teeks nimetatakse ahelat , kus ükski serv ei kordu
Lihtahelaks nimetatakse ahelat, kus ükski tipp ega serv ei kordu
Teoreem lihtahelast: kui graafis G leidub ahel tipust u tippu v, siis leidub graafis G ka lihtahel tipust u tippu v
Tippude u ja v vaheliseks kauguseks nimetatakse tippude u ja v vahelise lühima lihtahela pikkust
Kinniseks ahelaks nimetatakse ahelat, mis algab ja lõpeb samas tipus
Tsükliks nimetatakse kinnist ahelat, kus on vähemalt üks serv ja ükski serv ei kordu
Lihttsükliks nimetatakse tsüklit, kus iga sisetipp esineb ainult ühe korra
Teoreem lihtahela ja lihttsükli leidumisest: kui graafi iga tipu aste on vähemalt l≥2, siis leidub graafis lihtahel pikkusega l ja lihttsükkel pikkusega vähemalt l+1
Graafi, milles iga kahe tipu korral leidub neid tippe ühendav (liht)ahel, nimetatakse sidusaks
- kui graaf ei ole sidus, siis koosneb ta eraldiseisvatest sidusatest osadest, mida nimetatakse sidusateks komponentideks
Graafi serva, mille eemaldamisel graafi sidusate komponentide arv kasvab, nimetatakse sillaks
Graafi tippu, mille eemaldamisel graafi sidusate komponentide arv kasvab, nimetatakse eraldavaks tipuks
Tarvilik ja piisav tingimus silla jaoks: graafi serv on sild parajasti siis, kui ta ei kuulu ühessegi tsüklisse
Sidususteoreem: kui n-tipulisel graafil on m serva ja k sidusat komponenti, siis kehtivad võrratused n-k

.DOCX Laadi alla originaalfail 21 lk · .docx · 26 allalaadimist

Graafid ja matemaatiline loogika eksamimaterjal #1

Graafid ja matemaatiline loogika eksamimaterjal #2

Graafid ja matemaatiline loogika eksamimaterjal #3

Graafid ja matemaatiline loogika eksamimaterjal #4

Graafid ja matemaatiline loogika eksamimaterjal #5

Graafid ja matemaatiline loogika eksamimaterjal #6

Graafid ja matemaatiline loogika eksamimaterjal #7

Graafid ja matemaatiline loogika eksamimaterjal #8

Graafid ja matemaatiline loogika eksamimaterjal #9

Graafid ja matemaatiline loogika eksamimaterjal #10

Graafid ja matemaatiline loogika eksamimaterjal #11

Graafid ja matemaatiline loogika eksamimaterjal #12

Graafid ja matemaatiline loogika eksamimaterjal #13

Graafid ja matemaatiline loogika eksamimaterjal #14

Graafid ja matemaatiline loogika eksamimaterjal #15

Graafid ja matemaatiline loogika eksamimaterjal #16

Graafid ja matemaatiline loogika eksamimaterjal #17

Graafid ja matemaatiline loogika eksamimaterjal #18

Graafid ja matemaatiline loogika eksamimaterjal #19

Graafid ja matemaatiline loogika eksamimaterjal #20

Graafid ja matemaatiline loogika eksamimaterjal #21

Tasuta Faili alla laadimine on tasuta

~ 21 lehte Lehekülgede arv dokumendis

2017-06-01 Kuupäev, millal dokument üles laeti

26 laadimist Kokku alla laetud

0 arvamust Teiste kasutajate poolt lisatud kommentaarid

AnnaAbi Õppematerjali autor

Graafid ja matemaatiline loogika 2017. aasta kevade konspekt, mis sisaldab kõiki põhilisi matemaatilise loogika ja graafiteooria mõisteid ning olulisemaid tõestusi.

graafiteooria matemaatiline loogika diskreetne matemaatika graafid lausearvutus normaalkujud predikaadid kvantorid tõestustaktikad

Sarnased õppematerjalid

docx

Diskreetse matemaatika elemendid

o Relatsiooni hulkade X = {x1, x2, . . . , xm} ja Y = {y1, y2, . . . , yn} 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. o Kui R on näiteks viimati vaadeldud jaguvusrelatsioon, siis tema maatriks on Graaf o Ü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. o Näiteks olgu X tähtede hulk {a, b} ning Y kõigi kahetäheliste sõnade hulk, mida saab

Diskreetne matemaatika

docx

Diskreetse matemaatika elemendid, eksami konspekt

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õik arvupaarid ja tulemuseks saame R = {(1, 4), (2, 4), (4, 1), (4, 2)} b. Boole'i maatriks: olgu R relatsioon hulkade X = {x1, x2, ..., xm} ja Y = {y1, y2, ..., yn} vahel. Seame relatsioonile R vastavusse m×n-maatriksi, kus maatriski element . Nt, jaguvusrelatsioon. c. Graaf: Relatsioone lõpliku hulga X elementide vahel saab kujutada suunatud graafi abil. Kujutame hulga X elemente graafi tippudena ja joonistame tipust x tippu y kaare, kui kehtib xRy. Nt, jaguvusrelatsioon d. Avaldis: algebralised avaldised, nt võrratused. 22) Hulgal X määratud relatsiooni R nimetatakse a. refleksiivseks, kui iga x X korral (x, x) R. Nt samasusrelatsioon. Maatriksil on peadiagonaalis kõik ühed, graafis on iga tipu juures silmus.

Diskreetse matemaatika elemendid

docx

ITT0030 Diskreetne matemaatika II - eksamikonspekt

[23]. Kord- ja algarvud. Algarvude jaotus, algarvulisuse kontroll, Eratosthenese sõel. [24]. Naturaalarvude kanooniline kuju. Suurim ühistegur ja vähim ühiskordne. [25]. Fermat teoreem. Pseudoalgarvud ja Carmichaeli arvud. [26]. Eukleidese algoritm. [27]. Lineaarsed diofantilised võrrandid. [28]. Täisarvude kongruentsid. Kongruentsi omadusi. [29]. Moodularitmeetika. [30]. Algarvulisuse Fermat` test. Miller-Rabini test. [31]. Graafid ja graafide omadused. Ahelad ja tsüklid graafis. [32]. Euleri graafid. Hamiltoni tsüklid. [33]. Puud. Puude omadused. [34]. Graafi vähima kaaluga aluspuud. [35]. Märgendatud puud. Puude esitamine arvuti mälus. [36]. Prüferi kood. Märgendatud puude loendamine. Cayley teoreem. [37]. Märgendamata puude arv. [38]. Kooskõlad graafis. Berge'i teoreem. [39]. Kooskõlad kahealuselises graafis. Halli teoreem. [40]. Tasandiline graaf

Diskreetne matemaatika ii

docx

Algoritmid ICD0001 - kordamisküsimused

probleemorienteeritud liides. ADT - Abstract Data Type ● Lubatud väärtuste hulk (väärtusvaru) ● Lubatud operatsioonide hulk ● (Notatsioon - tähistused väärtuste ja operatsioonide jaoks) Andmestruktuurid võib jagada: ● staatilised: komponentide arv ja tüübid fikseeritud: näiteks kompleksarv ● dünaamilised: väärtuse komponentide arv on muutuv, komponendid ise tavaliselt üht tüüpi: näiteks magasin, järjekord, graaf, ... Ahelad Ahel on tee, milles servad ei kordu. Ei jõua tagasi samasse punkti. Tsükli saab ühe kaare lisamisega. Lihtahel on ahel, milles ka tipud ei kordu. Ahel koosneb muutuvast arvust elementidest, mis on omavahel seotud viitadega. Keeles Java ei ole viidatüüpi operatsioone ilmutatud kujul olemas - iga objektitüüpi väärtus on "tegelikult" viit. Lisamine ja kustutamine on lihtsalt kolm omistamist (viitade ümberlülitus) ja nihutamist ei olegi vaja

Algoritmid ja andmestruktuurid

docx

Diskreetne matemaatika eksami kordamise materjal

Lausearvutus:  Diskreetne matemaatika ei tegele pidevate funktsioonidega.  Diskreetne mate ei tegele reaalarvudega.  Verbaalne esitus on lingvistilise keele kasutamine info edastamiseks.  Formaalne esitus on ilma lingivtilise keele kasutamise info edastamine, peamiselt sümbolite abil.  Formaalne esitus peab olema üheselt mõistetav.  Lausearvutus on loogilise mõtlemise matemaatiline mudel.  Lausearvutuse lause on lause, millele saab omistada tõeväärtust(0,1).  Tõeväärtuseid on kaks, 0-väär, 1-tõene.  Lihtlause on lihtsaim lausearvutuse lause.  Lausearvutuse lauseid tähistatakse suutre tähtedega A, B, C.  Liitlause koosneb lihtlausetest ning neid siduvatest konstruktisoonidest ja sidesõnadest.  Lausearvutuse loogikatehted on inversioon, konjunktsioon, disjunktsioon, implikatsioon, ekvivalents.

Diskreetne matemaatika

doc

Diskmatt terminid

väärtustumisel 0ks, väärtustub ka funktsioon ise 0ks. Ühte säilitav funktsioon: funktsioon on ühte säilitav, kui kõikide ta muutujate väärtustumisel 1ks, väärtustub ka funktsioon ise 1ks. Loogikafunktsioonide täielikud süsteemid. Baasid Baas: minimaalne täielik loogikafunktsioonide süsteem Loogikafunktsioonide täielik süsteem: loogikafunktsioonide süsteem, mille abil on võimalik kujutada suvalise keerukusega loogikafunktsiooni Täielikkuse kriteerium: loogika funktsioonide süsteem on täielik, kui ta sisaldab vähemalt ühte igast järgnevast funktsioonist: 0 mittesäilitav, 1 mittesäilitav, mittepööratav, mittemonotoonne, mittelineaarne **** Graafid Graaf: objektidevaheliste seoste joonismudel, mis koosneb tippudest ja kaartest. Orienteerimata graaf: kõik kaared suunamata, neid tähistatakse harilike joontega Orienteeritud graaf: kõik kaared suunatud, neid tähistatakse nooltega Ahel: tee orienteerimata graafis

Diskreetne matemaatika

pdf

Diskreetne matemaatika II - viies kodutöö

elementi vastavusse seadnud. Nendeks on 0 ja 10. Nüüd hakkan juhindudes tabelist(alustan paremalt) lisama puule uusi tippe(ülemine rida) ja ühendama neid vastava alumisest reast ehk koodist pärit tipuga. Ehk esimesena lisan puule tipu 1 ning ühendan selle tipuga 0. Seejärel lisan tipu 9 ja ühendan selle tipuga 1. Ülejäänud tippudega käitun analoogiliselt. Tulemuseks saan järgmise puu: Vastus: ÜLESANNE 3. Võrdlen alguses mõlema graafi kõigi tippude astmeid. Märgin ära iga tipu astme. Diskreetne matemaatika II Kodused ülesanded 5 Olga Dalton 104493 IAPB21 Nii parem- kui vasakpoolsel graafil on olemas 2 tippu, mille aste on 3, ja 4 tippu, mille aste on 2.

Diskreetne matemaatika

doc

Teoreetilibe informaatika kordamisküsimused

vahel (ehk siis kõik elemendid mõlemast hulgast on haaratud ja igaühele vastab vaid 1 kindel element). Lõpmatut hulka nimetatakse loenduvaks, kui see on võrdvõimas naturaalarvude hulgaga. |H| on hulga võimsus ehk lõpliku hulga korral elementide arv hulgas. Lõpmatu hulga võimsus leitakse, seades tema elemendid bijektiivsesse vastavusse (üks- ühesesse) mõne tuntud võimsusega hulga (näiteks naturaalarvude hulga) elementidega. 4. Graafid. Puude esitused. Programmide esitamine puuna Mittejärjestatud ja mitteorienteeritud graaf on paar G = (A,R), kus A on tippude hulk ja kaarte hulk R on seos hulgal A. Graafi saab esitada paaride hulgana (A + R analüütiliselt, või predikaadina) või joonisena. Graafide võrdsus: Graafid G1 = (A1, R1) ja G1 = (A2, R2) on võrdsed ehk isomorfsed, kui leidub selline bijektiivne kujutus f: A1 A2 nii, et aR1b = f(a)R2f(b)

Teoreetiline informaatika

Rohkem sarnaseid