Lausearvutuse lihtlauseid seotakse liitlauseteks 5 loogilise konstruktsiooni ehk loogikatehte abil. Binaarsed loogikatehted seovad kahte lauset (4 tk), unaarne loogikatehe on rakendatav üksikule lausele (1 tk – eitus). Loogiline korrutamine ehk konjunktsioon ehk JA-tehe. Loogiline liitmine ehk disjunktsioon ehk VÕI-tehe. Ekvivalents on seotud implikatsiooniga ehk 𝑷 ↔ 𝑸 on nagu 𝑃 → 𝑄 ja samal ajal ka 𝑄 → 𝑃. Tehted inversioon, konjunktsioon ja disjunktsioon on elementaarsed loogikatehted – nad pole avaldatavad mingite teiste lihtsamate loogikatehete kaudu, kuna nad ise ongi „lihtsaimad“ tehted. Nii liht- kui ka liitlausete formaalseid esitusi nim lausearvutusvalemiteks -> Def – Lihtlause formaalne tähis (nt: A) ja üksik tõeväärtuskonstant 0 1 on valem. Kui A on valem, siis valemid on ka 𝐴̅ ja (A). Kui A ja B on valemid, siis on valemid ka 𝐴 ∧ 𝐵, 𝐴 ∨ 𝐵, 𝐴 → 𝐵, 𝐴 ↔ 𝐵.
Diskmatt terminid Lausearvutus Disjunktsioon: liitlause on tõene, kui vähemalt üks osalause on tõene Ekvivalents: liitlause on tõene, kui osalaused on sarnased Implikatsioon: liitlause on tõene, kui esimene muutuja on väär või teine muutuja on tõene Inversioon: eitus Ja-tehe: konjunktsioon Konjunktsioon: liitlause on tõene, kui mõlemad osalaused on tõesed Lause: iga lause, mille puhul saab rääkida tema vastavusest tegelikkusele (millel on tõeväärtus) Olemasolu kvantor: näitab, et predikaat kehtib oma määramispiirkonna vähemalt ühe muutujate puhul Predikaat: lause, mis sisaldab ühte või enamat muutujat Samaselt tõene predikaat: predikaat, mis kehtib kogu määramispiirkonnas
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. Binaarsed tehted on need tehted, mida saab teha kahe argumendi korral(konjunktsioon, disjunktsioon, implikatsioon, ekvivalents). Unaarne tehe on tehe, mida saab rakendada üksikule argumendile/operandile(inversioon). Ekvivalents on kahepoolne implikatsioon. Elementaarsed loogikatehted on inversioon, konjunktsioon, disjunktsioon,
Lausearvutuse lihtlauseid seotakse liitlauseteks 5 loogilise konstruktsiooni ehk loogikatehte abil. Binaarsed loogikatehted seovad kahte lauset (4 tk), unaarne loogikatehe on rakendatav üksikule lausele (1 tk – eitus). Loogiline korrutamine ehk konjunktsioon ehk JA-tehe. Loogiline liitmine ehk disjunktsioon ehk VÕI- tehe. Ekvivalents on seotud implikatsiooniga ehk 𝑷↔𝑸 on nagu 𝑃→𝑄 ja samal ajal ka 𝑄→𝑃. Tehted inversioon, konjunktsioon ja disjunktsioon on elementaarsed loogikatehted – nad pole avaldatavad mingite teiste lihtsamate loogikatehete kaudu, kuna nad ise ongi „lihtsaimad“ tehted. Nii liht- kui ka liitlausete formaalseid esitusi nim lausearvutusvalemiteks -> Def – Lihtlause formaalne tähis (nt: A) ja üksik tõeväärtuskonstant 0 1 on valem. Kui A on valem, siis valemid on ka 𝐴̅ ja (A). Kui A ja B on valemid, siis on valemid ka 𝐴∧𝐵,𝐴∨𝐵,𝐴→𝐵,𝐴↔𝐵
LOOGIKATEHTED lausearvutuses ülesanded: Olgu antud järgnevad lihtlaused (väited): S — on suvi tehtemärk tehte nimi ja selgitus O — väljas on soe ¯¯ loogiline eitus e. inversioon V — vihma sajab P — väljas on pime ∧ loogiline korrutamine e. konjunktsioon e. JA-tehe R — päikesevarjutus kestab ( aritmeetilise korrutamise analoog loogikas )
Vali üks: hüüumärk muudab kvantori tähenduse vastupidiseks hüüumärk täpsustab, et "leidub täpselt 1" hüüumärk rõhutab kvantori suurt tähtsust Küsimus 3 Õige Hinne 1,00 / 1,00 Kui loogikaavaldises pole sulgudega määratud tehete järjekorda, siis KONJUNKTSIOONi, DISJUNKTSIOONi ja INVERSIOONi leidumisel avaldises . . . Vastus 1 kõige esimesena tehakse loogikaavaldises INVERSIOON Vastus 2 ...selle järel järgmisena tehakse KONJUNKTSIOON Vastus 3 ...ja viimasena tehakse DISJUNKTSIOON Küsimus 4 Õige Hinne 1,00 / 1,00 Loogikatehetel on olemas võõrsõnalised nimetused. Vastus 1
Kahe muutuja loogikafunktsioonid,Karnaugh,McCluskey Mitu erinevat 1muutuja loogikafunktsiooni on olemas? 4 erinevat. Tabel lk 174 Milline on ainus oluline 1muutuja loogikafunktsioon? Inversioon Kuidas võib nimetada 0 muutuja loogikafunktsiooni? Konstant 1 või konstant 0 Mitu erinevat 2muutuja loogikafunktsiooni on olemas? 16, tabel lk 175-176 Millised 2muutuja funktsioonid sõltuvad mõlemast oma muutujast? F1,f2,f4,f6,f7,f8,f9,f11,f13,f14 Milline erinevus on implikatsioonil ja pöördimplikatsioonil? Implikatsioonil on x1-x2 seos, pöördimplikatsioonil vastupidi, x2-x1 Mis on Pierce´i nool? F8, on disjunktsiooni inversioon ja esitatakse märgiga pierci nool. Vt lk 177 Mis on Shefferi kriips? F14, on konjuktsiooni inversioon ja esitatakse ka märgiga shefferi kriips, vt lk 177
Vastavus - eksamil tudengi poolt saadud hinne. Millistel tingimustel on osaliselt määratud funktsioon; täielikult määratud funktsioon; sürjektsioon; injektsioon; bijektsioon? BINAARSUHTED Meie poolt vaadeldavad binaarsuhteid võib käsitleda kui vastavuse erijuhtu, kus lähte- ja sihthulk langavad kokku (D()=R()=A). Tähistame järgnevas binaarsuhet tähega R AxA. Binaarsuhet on mugav interpreteerida suhte graafiga - s.o. orienteeritud graaf, kus hulga A elemendid vastavad tippudele ja seosed elementide vahel - kaartele. Suhte võime esitada binaarmaatriksina (naabrusmaatriksina). Näide. Hulga A={a,b,c,d,e} elementideks on arvutikomponendid: a-sisendseade, b- aritmeetika- loogikaseade, c-juhtseade, d-mälu, e-väljundseade. Binaarsuhe R seob kahte elementi, kui esimene seade annab teisele infot arvuti töö käigus. a b c d e a 1 1 1 1 0
Millistel tingimustel on osaliselt määratud funktsioon; täielikult määratud funktsioon; sürjektsioon; injektsioon; bijektsioon? BINAARSUHTED 4 Meie poolt vaadeldavad binaarsuhteid võib käsitleda kui vastavuse erijuhtu, kus lähte- ja sihthulk langavad kokku (D()=R()=A). Tähistame järgnevas binaarsuhet tähega R AxA. Binaarsuhet on mugav interpreteerida suhte graafiga - s.o. orienteeritud graaf, kus hulga A elemendid vastavad tippudele ja seosed elementide vahel - kaartele. Suhte võime esitada binaarmaatriksina (naabrusmaatriksina). Näide. Hulga A={a,b,c,d,e} elementideks on arvutikomponendid: a-sisendseade, b- aritmeetika- loogikaseade, c-juhtseade, d-mälu, e-väljundseade. Binaarsuhe R seob kahte elementi, kui esimene seade annab teisele infot arvuti töö käigus. a b c d e a 1 1 1 1 0
Nimetatakse konstant 1 ja konstant 0 Mis on loogikaavaldis? Loogikaavaldise definitsioon loogikaavaldis on loogikamuutuja xi, konstante 0 1 ja tehtemärke sisaldav kooslus, mis tema muutujate xi väärtustamisel omandab samuti loogikaväärtuse 0 või 1 definitsiooni vaata lk 154 Millist loogikatehet tähendab tehtemärgi puudumine operandide vahel? On samaväärne tehtega konjuktsioon. Mitu loogikatehet on olemas? Mitu operandi nendest igalühel on? 3, konjuktsioon, disjunktsioon ja inversioon. Esimesel kahel 2, inversioonil 1, unaarne. Millisel tingimusel on kaks loogikaavaldist omavahel võrdsed? Kaks erinevat loogikaavaldist on võrdväärsed ehk võrdset, kui nad mõlemad omandavad muutujate samade väärtuskombinatsioonide korral sama loogikaväärtuse 1 või 0 Kuidas saadakse mingi loogikaavaldise jaoks tema duaalne kuju? Konjuktsioon disjunktsiooniks, disjunktsioon konjuktsiooniks, konstandid 0 konstandiks 1 ja konstandid 1 konstandiks 0.
F & (G ∨ H ) ≡ F & G ∨ F & H , F ∨ G & H ≡ (F ∨ G) & (F ∨ H ). o Neelamisseadused: F & (F ∨ G) ≡ F , F∨F&G≡F. o De Morgani seadused: ¬(F & G) ≡ ¬F ∨ ¬G, ¬(F ∨ G) ≡ ¬F & ¬G. o Kahekordse eituse seadus: ¬¬F ≡ F . o 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. o Implikatsiooni avaldis konjunktsiooni ja disjunktsiooni kaudu: F → G ≡ ¬(F & ¬G), F → G ≡ ¬F ∨ G. o Konjunktsiooni ja disjunktsiooni avaldis implikatsiooni kaudu: F & G ≡ ¬(F → ¬G), F ∨ G ≡ ¬F → G. o Ekvivalentsi avaldis teiste tehete kaudu: F ↔ G ≡ F & G ∨ ¬F & ¬G, F ↔G ≡ (F → G) & (G → F Valemite teisendamine samaväärsuste abil 6
Diskreetne matemaatika KODUTÖÖ SISUKORD SISUKORD..........................................................................................1 ÜLESANNE 1 LOOGIKAFUNKTSIOON......................................................3 ÜLESANNE 2 TÕEVÄÄRTUSTABEL..........................................................3 ÜLESANNE 3 MINIMAALSED NORMAALKUJUD........................................3 3.1 MDNK KARNAUGH’ KAARDIGA.......................................................................3 3.2 MKNK MCCLUSKEY MEETODIGA.....................................................................4 3.3 VÕRDLUS.............................................................
c. Funktsiooni f : X Y nimetatakse bijektiivseks ehk üksüheseks vastavuseks, kui ta on injektiivne ja sürjektiivne ehk kui igal elemendil hulgast Y leidub parajasti üks originaal. d. 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. 21) Relatsioonide esitusviisid: a. Loend: definitsiooni järgi on relatsioon paaride hulk. Kui see hulk on lõplik, siis saab teda esitada elementide (so paarida) loendina. Nt, vaatleme neljaelemendilisel hulgal X = {1, 2, 3, 4} 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õik arvupaarid ja tulemuseks saame R = {(1, 4), (2, 4), (4, 1), (4, 2)} b
0-muutuja funktsioonid (konstandid 0 1) 1-muutuja funktsioonid 2-muutuja funktsioonid 3-muutuja funktsioonid 4-muutuja funktsioonid Küsimus 2 Õige Hindepunkte 1,00/1,00 sisesta lahtrisse õige sõna : Loogikafunktsioonide süsteem on täielik , kui sellesse süsteemi kuuluvate funktsioonide/tehete abil on võimalik esitada suvalist muud loogikafunktsiooni. Küsimus 3 Õige Hindepunkte 5,00/5,00 vali õiged : Loogikatehete süsteem üheainsa tehtega JA-EI (NAND) on täielik ja seda nimetatakse Shefferi baasiks . JA-EI kujulise loogikaavaldise saamiseks tuleb DNK-le rakendada topeltinversiooni koos järgneva DeMorgani seaduse rakendamisega. Küsimus 4 Õige
KNK-le rakendada koos järgneva topeltinversiooni rakendamisega. DeMorgani seaduse Küsimus 5 Õige - Hinne 1,00 / 1,00 Millised loogikatehted järgnevatest kuuluvad implikatiivse baasi koosseisu ? vali kõik õiged : Vali üks või enam: implikatsioon konjunktsioon disjunktsioon inversioon Küsimus 6 Õige - Hinne 1,00 / 1,00 Millised loogikatehted ja konstandid kuuluvad Reed- Mulleri baasi koosseisu ? vali kõik õiged : Vali üks või enam: konstant 0 konjunktsioon summa mooduliga 2 (välistav VÕI) ekvivalents inversioon konstant 1 disjunktsioon implikatsioon Küsimus 7 Õige - Hinne 1,00 / 1,00 Millised loogikafunktsioonid peavad kuuluma loogikafunktsioonide süsteemi koosseisu, et see süsteem oleks täielik ?
Küsimus 1 Õige - Hinne 1,00 / 1,00 kas väide on õige või vale: Jääkfunktsioone ei saa leida Karnaugh' kaardi abil Vali üks: Tõene Väär Küsimus 2 Osaliselt õige - Hinne 0,75 / 1,00 vali kõik õiged väited: Vali üks või enam: Funktsioonil võib Taandatud DNK puududa, kuigi minimaalne DNK (MDNK) on sellel funktsioonil olemas - VALE Taandatud DNK-d on võimalik leida Karnaugh' kaardi abil Taandatud DNK ja minimaalne DNK (MDNK) võivad olla üks ja sama avaldis Taandatud DNK võib olla suurema keerukusega avaldis kui minimaalne DNK (MDNK) Taandatud DNK on funktsiooni kõikide implikantide disjunktsioon - VALE Taandatud DNK on funktsiooni kõikide lihtimplikantide disjunktsioon Funktsioonil võib olla mitu erinevat Taandatud DNK-d - VALE Taandatud DNK võib olla väiksema keerukusega avaldis kui minimaalne DNK (MDNK) - VALE Küsimus 3 Õige - Hinne 3,00 / 3,00
On olemas 2 liiki, disjunktiivne arendus ja konjuktiivne arendus. Milline loogikaavaldis on täieliku shannoni arenduse tulemuseks? Alles ei jää mitte ühtegi muutujat xi, ehk jääkfunksioon väärtustub konstandiks 0 või 1. Millistesse klassidesse loogikafunktsioonid liigituvad? Kuidas igat klassi tähistatakse? Milline on klassi kuuluvuse tunnus iga konkreetse klassi jaoks? Vt tähiseid, tunnuseid jn lk 272-273 Millist tingimust täitev 2-muutuja loogikafunktsioon on lineaarne? Kui f(00)+f(01)+f(10)=f(11) Mis on loogikafunktsiooni süsteem? Loogikafunktsioonide süsteem on loogikafunktsioonide hulk. Mis on iseloomulik mingis konkreetses süsteemis esitatud loogikaavaldisele? Kui loogikaavaldis kuulub kuhugi kindlasse süsteemi, siis on ta esitatud ainult selles süsteemis leiduvaid loogikatehteid kasutades. Milline loogikafunktsioon on süsteemis täielik?
konstant 0 Küsimus 7 Õige - Hinne 2,00 / 2,00 Milline on kontuuride valimise kriteerium (reegel) minimaalse normaalkuju leidmisel ? Vajalikud kaardiruudud tuleb katta võimalikult väikse arvu võimalikult suurte kontuuridega Küsimus 8 Õige - Hinne 1,00 / 1,00 kas järgnev väide on õige või vale? Karnaugh' kaardi iga kontuur vastab mingile kindlale intervallile Vali üks: Tõene Väär Küsimus 9 Õige - Hinne 1,00 / 1,00 4-muutuja loogikafunktsiooni Karnaugh' kaardil on . . . . . . üheruudulise kontuuri ulatuses . . . . . . 4 konstantset muutujat; . . . viieruudulise kontuuri ulatuses . . . . . . pole sellise mõõduga kontuuri ! . . . kaheksaruudulise kontuuri ulatuses . . . . . . 1 konstantne muutuja; . .
1 2 3 4 5 6 Time taken 5 mins 8 secs 7 8 9 10 11 12 Marks 20.00/20.00 Grade 100.00 out of a maximum of 100.00 13 14 15 Finish review Question 1 Millise loogikatehte osalusel esitub loogikafunktsiooni tuletis ? Correct Mark 1 out of 1 Select one: summa mooduliga 2 implikatsioon konjunktsioon disjunktsioon
Correct Loogikafunktsioonide süsteem on täielik , kui sellesse süsteemi Mark 1.00 out of kuuluvate funktsioonide/tehete abil on võimalik esitada suvalist muud 1.00 loogikafunktsiooni. Question 3 vali õiged : Correct Loogikatehete süsteem üheainsa tehtega JA-EI (NAND) on Mark 5.00 out of 5.00 täielik ja seda nimetatakse Shefferi baasiks .
Loogikafunktsioonil konstant 1 puudub TÄIELIK KONJUNKTIIVNE Mark 1 out of 1 normaalkuju (TKNK) Question 2 kas järgnev väide on õige või vale? Correct Karnaugh' kaardi iga kontuur vastab mingile kindlale intervallile Mark 1 out of 1 Select one: True False Question 3 kas järgnev väide on õige või vale? Correct
o Kui F = ¬G, siis F = 1 parajasti siis, kui G = 0 o Kui F = G&H, siis F = 1 parajasti siis, kui G = 1 ja H = 1 o Kui F = GH, siis F = 1 parajasti siis, kui G = 1 või H = 1 o Kui F = GH, siis F = 1 parajasti siis, kui G = 0 või H = 1 o Kui F = GH, siis F = 1 parajasti siis, kui G = 1 ja H = 1 või G = 0 ja H = 0 o 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 o 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
disjunktsioonide konjunktsioon saadakse tõeväärtustabeli 0de piirkonnast Küsimus 3 Õige - Hinne 1,00 / 1,00 kas järgnev väide on õige või vale? 4-mõõtmeline Boole'i ruum on kõikide 4-järguliste 2ndvektorite hulk. Vali üks: Tõene Väär Küsimus 4 Õige - Hinne 6,00 / 6,00 vali sobivad väljendid, mille korral lause on õige: Täielikult määratud loogikafunktsioon on kõikjal määratud ühene vastavus Küsimus 5 Õige - Hinne 1,00 / 1,00 sisesta lünka õige sõna: on üksik algterm või algtermide disjunktsioon. Elementaardisjunktsioon Küsimus 6 Õige - Hinne 1,00 / 1,00 sisesta õige vastus arvuna: Mitu rida on 4-muutuja loogikafunktsiooni tõeväärtustabelis? Vastus: 16 Küsimus 7 Õige - Hinne 1,00 / 1,00
[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. Euleri valem: seos tasandilise graafi tippude, servade ja tahkude arvude vahel. Eulri valemi rakendusi. [41]. Graafi tasandilisuse kriteeriumid. Kuratowski teoreem. [42]
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) Kui igale tipule a G1-st leidub tipp b G2-st, millele saab vastavusse seada samade tippude kaared ja kõik G2 tipud saavad ka kaetud.
Tallinna Tehnikaülikool Diskreetne matemaatika KODUTÖÖ Kristjan Keskküla 093540 IASB Tallinn 2009 ÜLESANNE 1 Leida oma martiklinumbrile vastav 4-muutuja loogikafunktsioon f(x1, x2, x3, x4) = (2,4,8,9,14,15) (6,11,13) _ (järgnevalt kui funktsioon) 1 ÜLESANNE 2 Leida MDNK ja MKNK, mis sobiksid martiklinumbrist leitud osaliselt määratud 4-muutuja funktsiooni esitamiseks Kuna minu martiklinumber on paarisarvuline leian: MKNK Karnaugh' kaardiga ja MDNK McCluskey' meetodiga. 1) Leian MKNK Karnaugh' kaardiga MKNK leidmiseks joonestan Karnaugh' kaardi, kuhu kannan peale funktsiooni 1d, 0d ja määramatused.
Tallinna Tehnikaülikool Diskreetne matemaatika KODUTÖÖ Mina Ise 132456 IADB?? Tallinn 2019 ÜLESANNE 1 LOOGIKAFUNKTSIOON Leian oma matriklinumbrile vastav 4-muutuja loogikafunktsioon Matriklinumbri 5 viimast numbrit: 93656 Matriklinumber kuueteistkümnendsüsteemis: 2F478 Seitsmekohaline arv: 3F58CC8 Üheksakohaline arv: 54DFF9FF8 Ühtede piirkond: 3, 5, 8, 12 ( C16 ), 15 ( F16 )/ 0011, 0101, 1000, 1100, 1111 Määramatuspiirkond : 4, 9, 13 ( D16 ) / 0100, 1001, 1101 0-de piirkond : 0, 1, 2, 6, 7, 10 ( A16 ), 11 ( B16 ), 14 ( E16 ) / 0000, 0001, 0010, 0110, 0111, 1010, 1011, 1110 𝒇(x(x1,x2,x3,x4) = ∑ ( 3, 5, 8, 12, 15 )1 ( 4, 9, 13 )_
Mark 1.00 out of 1.00 Select one: True False Question 2 Mitu 2-muutuja loogikafunktsiooni on olemas ? Correct (sisesta õige arv) Mark 1.00 out of 1.00 Answer: 16 Question 3
T Karnaugh' kaartide topoloogia 2muutuja Karnaugh' kaart on tabel mõõtmetega 2 2 (või 1 4) ruutu ; 3muutuja Karnaugh' kaart on tabel mõõtmetega 2 4 = 8 ruutu ; 4muutuja Karnaugh' kaart on tabel mõõtmetega 4 4 = 16 ruutu ; e h n ik a t või i 6 - muutuja Karnaugh' kaart v ut Karnaugh' kaartide põhiomadused r 2 - muutuja 3 - muutuja 4 - muutuja Karnaugh' kaart Karnaugh' kaart Karnaugh' kaart A Karnaugh' kaardil on 2 põhiomadust.
Tallinna Tehnikaülikool DISKREETNE MATEMAATIKA KODUTÖÖ Elena Borissov 155175IAPB IAPB11 1. Leida oma matriklinumbrile vastav 4-muuutuja loogikafunktsioon Esimene seitsmekohaline arv kalkulaatoris 32C2641 . Kümnendarvudena 3, 2, 12, 6, 4, 1 Järjekorras 1, 2, 3, 4, 6, 12 1de piirkond Esimene üheksakohaline arv kalkulaatoris 440274117 Järjekorras 0, 7 määramatus piirkond 5, 8, 9, 10, 11, 13, 14, 15 0de piirkond f(x1, x2, x3, x4)=∑(1, 2, 3, 4, 6, 12)1 (0, 7)_ 2. Tõeväärtustabel x1, x2, x3, x4 f 0000 -
Graafid Graaf koosneb tippudest(sõlmedest) ja neid ühendavatest kaartest. Kaarega võib ühendada suvalisi graafi tippe, sealhulgas on võimalik kaar samale tipule (iseendale). Iga kaar on määratud kahe tipuga. Orienteeritud graaf: kaared on järjestatud tipupaarid. Def: Graaf on paar (V,E), kus V on mittetühi hulk ning E hulk, mille elementideks on hulga V kaheelemendilised alamhulgad. Näide lk 47 (Palm) Tipu aste tipust väljuvate servade arv. Teoreem: Igas graafis on kõigi tippude astmete summa võrdne servade arvu kahekordsega. Järeldus: Igas graafis on paaritu astemga tippe paarisarv. Ahel graafis tippude järjend, kus iga kaks järjestikust tippu on servaga ühendatud (esimene ja viimane on otstipud vahepeal sisetipud).
Loogilist liitmist nimetatakse ka disjunktsiooniks (disjunction). Loogiline eitus (EI). EI-funktsioonil on argumendi vastandväärtus. Kui argument on 1, siis funktsioon võrdub 0 ning vastupidi. EI-tehet tähistatakse kriipsuga sümboli peal, näiteks argumendi x eitus on x . Loogilist eitust nimetatakse ka inversiooniks (negation). Loetletud kolm loogikatehet moodustavad loogiliselt täieliku süsteemi, mida rakendades saab realiseerida mis tahes loogikafunktsiooni. Kõiki kolme loogika põhifunktsiooni on loogikaalgbra reeglite alusel võimalik realiseerida ainult üht tüüpi loogikaelementide kas NING-EI või VÕI-EI abil. Järelikult võib NING-EI- ja VÕI-EI- elemente ning tehteid nendega nimetada universaalseteks loogikaelementideks ja -teheteks. 3.2 Loogikalülitused Lisaks põhifunktsioonidele leiavad kasutamist mitmed loogika tüüpfunktsioonid, nagu alternatiiv, ekvivalentsus, implikatsioon jt. Niisuguste funktsioonide ja elementide
raske tõestada. 2.2.2 Tugevad küljed: • Paljudel juhtudel on teda kergem koostada • Töötab kiiremini kui DP algoritm Optimiseerimise juures on vajalikud teatud tingimused: 1. Kandidaatide hulk (graafi tipud, teede pikkused, rahatähtede suurused...) 2. Valitute hulk, mis või kes on juba kasutatud (sobivaks tunnistatud, tagasi antud rahatähed, läbitud graafi tipud...) 3. Eeldatav lahendus, otsitav summa vms, mille järgi saab otsustada, kas välja valitud kandidaadid moodustavad lahendused (ei pruugi olla optimaalne) 4. Jätkamise näitaja, mille järgi saab otsustada, kas kandidaatide hulka saab suurendada, et lahendust leida. 5. Valikufunktsioon, mille abil valitakse uusi kandidaate väljavalitute hulka 6. Vastusefunktsioon, mis annab lõpliku väärtuse lahendusele 2.2.3 Näide kasutamisest:
annaabi.ee 
Sisene Facebook'ga
Sisene Google'ga
Sisene LinkedIn'ga
