Graafid ja matemaatiline loogika eksamimaterjal (0)

Tartu Ülikool - Matemaatika - Algebra I

1 HALB

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

Lõik failist

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 ):{0,1}𝑛 → {0,1}. 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 -> {1,0}
- Hulka, millel predikaat on määratud, nimetatakse selle predikaadi indiviidide piirkonnaks
- Vastavalt predikaadi definitsioonile saame igale predikaadile 𝑃 seada vastavusse tema tõesuspiirkonna 𝑇𝑃 = { (𝑥1, … , 𝑥𝑛) |P(𝑥1, … , 𝑥𝑛) = 𝑡 }

Olgu P(𝑥1, … , 𝑥𝑛) hulgal 𝑀 defineeritud 𝑛- kohaline predikaat. Siis iga 𝑖 ≤ 𝑛 korral tähistavad ∀𝑥𝑖P(𝑥1, … , 𝑥𝑛) ja ∃𝑥𝑖P(𝑥1, … , 𝑥𝑛) järgmisi (𝑛 − 1)-kohalisi predikaate:
- ∀𝑥𝑖P(𝑥1, … , 𝑥𝑛) = {t, kui x1, …, xi-1, xi+1, …, xn on hulga M sellised elemendid, et iga xi∈M korral P(𝑥1, … , 𝑥𝑛)=t
- ∃𝑥𝑖P(𝑥1, … , 𝑥𝑛) = {t, kui x1, …, xi-1, xi+1, …, xn on hulga M sellised elemendid, et mingi xi∈M korral P(𝑥1, … , 𝑥𝑛)=t, vastasel juhul P(𝑥1, … , 𝑥𝑛)=v
Lõpliku indiviidide piirkonna puhul saab kvantorite rakendamise taandada lausearvutuse tehetele:
- Kui 𝑀 = {𝑚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

Lae alla, et näha rohkem ▪ ▪ ▪

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

21 laadimist Kokku alla laetud

0 arvamust Teiste kasutajate poolt lisatud kommentaarid

kadikukk10 Õ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