Loogikaavaldise f keerukus L(f) on tema kooseisus olevate algtermide arv. Vt näidet lk 167 keskel. Mis on MDNK? Mis on MKNK? MDNK ja MKNK on konkreetse funktsiooni väikseima keerukusega DNK või KNK. Millisest loogikafunktsiooni piirkonnast tuleneb DNK, millisest KNK? DNK saadakse 1-de piirkonnast, KNK 0-de piirkonnast. Kuidas kirjutatakse funktsiooni tõeväärtustabelist välja TDNK või TKNK? TDNK vastavalt 1-de piirkonnast, KNK 0-de piirkonnast. TDNK puhul kirjutad välja terve vastava argumentvektori, sellisel kujul nagu ta on, nt 111=x1x2x3 v ...... KNK puhul vahetad ümber, 1- puhul läheb x1 hoopis x1 inversiooniks ja 0 puhul x1 inversioon x1- ks. Samuti seal kus oli enne vahel disjunktsioon on nüüd vahel konjuktsioon ja vastupidi. Pm tundub olevat tegemist duaalsele kujule viimisega. Mitu erinevat TDNK on igal loogikaavaldisel? Mitu TKNK-d? Üks. Mitu TDNK elemtaarkonjuktsiooni väärtustub 1-ks suvalise argumentvektori korral? Täpselt 1
Mis on minimaalne KNK (MKNK)? MDNK (MKNK) on vähima keerukusega DNK (KNK) ehk sisaldab kõige vähem algterme. 39. Millisest loogikafunktsiooni piirkonnast tuleneb DNK? Millisest piirkonnas tuleneb KNK? DNK tuleneb 1depiirkonnast. KNK tuleneb 0depiirkonnast. 40. Kuidas kirjutatakse funktsiooni tõeväärtustabelist välja funktsiooni TDNK või TKNK? TDNK kirjutatakse välja 1depiirkonnast nii, et iga elementaarkonjunktsioon omandab väärtuse ainult ühe argumentvektori korral. TKNK kirjutatakse välja 0depiirkonnast nii, et iga elementaardisjunktsioon omandab väärtuse ainult ühe argumentvektori korral, kusjuures väärtus 0 annab elementaardisjunktsiooni koosseisu muutuja otseväärtuse ning väärtus 1 annab elementaardisjunktsiooni koosseisu muutuja inversiooni. 41. Mitu erinevat täielikku disjunktiivset normaalkuju (TDNK) on igal loogikafunktsioonil? Igal loogikafunktsioonil on täpselt üks TDNK. 42
A3 1 1 A4 1 1 A5 1 1 A6 1 1 Katan ilma tärnita veerud (1de piirkonna) vähemalt ühe valitud reaga (lihtimplikandiga). Määramatused võib katmisel välja jätta. Valin A2, A4, A5, A6. Minimaalne disjunktsioonkuju tuleb 4-ja elementaarkonjuktsiooniga. f = A2 V A4 V A5 V A6 Võtan lihtimplikantide koosseisust suvalise argumentvektori ja loobun 2ndarvu nendest järkudest, mille kaal võrdub vahega. Valitud Lihtimplikandid x x x x Alles jääb 10nd arv 1 2 3 4 A2 15 1 1 1 1 x1x2x3 A4 9 1 0 0 1 x1 x 2 x3 A5 4 0 1 0 0 x1 x2 x 4 A6 2 0 0 1 0 x1 x3 x 4 MDNK - f(x1,x2,x3,x4) = x1x2x3Vx1 x 2 x3 V x1 x2 x 4 V x1 x3 x 4 ÜLESANNE 3
Paarisarvulise matriklinumbriga üliõpilased leiavad MDNK Karnaugh’ kaardiga ja MKNK McCluskey meetodiga. 3.1 MDNK KARNAUGH’ KAARDIGA Vasakpoolne tabel kujutab osaliselt määratud loogikafunktsiooni Karnaugh’ kaarti. Parempoolne tabel kujutab lõpuni määratud loogikafunktsiooni Karnaugh’ kaarti. Kaartide esimesse tulpa on märgitud muutujate x 1 x 2 väärtused ja esimesse ritta on märgitud muutujate x 3 x 4 väärtused. Funktsiooni väärtuse teatud argumentvektori x 1 x 2 x 3 x 4 korral saab leida, kui fikseerida rida ja tulp. 00 01 11 10 00 01 11 10 00 0 1 1 0 00 0 1 1 0 01 −¿ 1 1 −¿ 01 0 1 1 0 11 0 −¿ −¿ −¿ 11 0 1 1 0
Loogikaskeemid Digitaalseade: seade, mis kasutab loogikaskeeme Digitaalskeem: kahendkoode töötlev elektriskeem Ja-element: loogikaelement, mis realiseerib loogikatehet "ja" Loogikaelement: digitaalseadme elementaarkoostisosa, mis teeb loogikaväärtustega 0 ja 1 lihtsaimaid loogikatehteid. Loogikaskeem: kokkuühendatud loogikaelemendid Või-element: loogikaelement, mis realiseerib loogikatehet "või" Loogikafunktsioonide klassid Monotoonne loogikafunktsioon: funktsioon on monotoonne, kui argumentvektori suurenemisel funktsiooni väärtus ei vähene Nulli säilitav funktsioon: funktsioon on nulli säilitav, kui kõikide ta muutujate 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
(loogiliselt) võrdne Taandatud DNK ja Täielik DNK Taandatud DNK leiame Karnaugh' kaardi ühtede piirkonna abil X3,X4 00 01 11 10 X1,X 2 00 - 1 1 1 01 1 0 - 1 11 1 0 0 0 10 0 0 0 0 TaDNK = x1 xx 2 x4 ∨ x2 xx 3 xx 4 ∨ xx 1x3 xx 4 ∨ xx 1 xx 2 x3 ∨ xx 1 xx 2 x4 Täieliku DNK leiab iga argumentvektori konstituentide või- tehtega liitmise teel. X3,X4 00 01 11 10 X1,X 2 00 - 1 1 1 01 1 0 - 1 11 1 0 0 0 10 0 0 0 0 TDNK = xx 1 xx 2 xx 3 x4 ∨ xx 1 xx 2 x3 x4 ∨ xx 1 xx 2 x3 xx 4 ∨ xx 1 x2 xx 3 xx 4 ∨ xx 1 x2 x3 xx 4 ∨ x1 x2 xx 3 xx 4 6
5 0 1 0 1 1 6 0 1 1 0 0 E 1 1 1 0 0 6.1 Otsustada (hinnata), kas leitud MDNK ja MKNK on teineteisega võrdsed või mitte. MDNK ja MKNK väärtused erinevad määramatusepiirkonnas 1 argumentvektori puhul. MDNK ei ole võrdne MKNK-ga, kuna kasutasin MDNK leidmisel määramatusepiirkonna argumentvektorit. 7. Realiseerida (punktis 3) MDNK-na saadud loogikafunktsioon minimaalseima keerukusega loogikaskeemina, kasutades vabaltvalitud loogikaelemente AND OR ja NOT. Minimaalne disjunktiivne normaalkuju: f ( x 1 x 2 x3 x 4 ) =x1 x 4 + x 2 x´3 + x´3 x 4 + x 1 x´2
x̄1 x2 x̄3 w x1 x̄2 x̄3 w x1 x2 x̄3 1 0 0 1 elementaarkonjunktsioon omandab x̄1 x2 w x1 x̄2 1 0 1 0 väärtuse 1 täpselt ühe 1-de piirkonna x̄1 x2 x̄3 x̄4 x2 1 1 0 1 argumentvektori korral: 1 1 1 1 Täielik KNK ( TKNK ) on KNK, kus iga elementaardisjunktsioon f ( x1 x2 x3 ) = x̄1 x̄2 x3 w x̄1 x2 x̄3 w x1 x̄2 x̄3 w x1 x2 x̄3 w x1 x2 x3 sisaldab funktsiooni kõiki muutujaid xi Järgneval viiel real on igal real üks täielik KNK : Saadav DNK osutub TDNK-ks.
1-te säilitav – kui ta kõikide muutujate väärtustamisel 1-ks väärtustub F-n ise ka 1-ks 𝐾1={𝑓(𝑥1…𝑥𝑛) | 𝑓(11…1)=1} {𝑓1,𝑓3,𝑓5,𝑓7,𝑓9,𝑓11,𝑓13,𝑓15}⊂𝐾1 Pööratav – kui ta oma kõikide muutujate väärtuste inverteerimisel iverteerub ka ise 𝐾𝑝={𝑓(𝑥1…𝑥𝑛) | 𝑓(𝑥1̅̅…𝑥𝑛̅̅)=𝑓̅(𝑥1…𝑥𝑛)} {𝑓3,𝑓5,𝑓10,𝑓12}⊂𝐾𝑝 Monotoonne – kui argumentvektori suurenemisel F-ni väärtus ei vähene 𝐾𝑚={𝑓(𝑥1…𝑥𝑛) | (𝑥1…𝑥𝑛<𝑧1…𝑧𝑛)↔[𝑓(𝑥1…𝑥𝑛)≤𝑓(𝑧1…𝑧𝑛)]} {𝑓0,𝑓1,𝑓3,𝑓5,𝑓7,𝑓15}⊂𝐾𝑚 Lineaarne – kui ta on esitatav kujul 𝑐0⊕𝑐1𝑥1⊕𝑐2𝑥2⊕…⊕𝑐𝑛𝑥𝑛, kus iga const 𝑐𝑖∈{0 1} 𝐾𝑙={𝑓(𝑥1…𝑥𝑛) | 𝑓(𝑥1…𝑥𝑛)=𝑐0⊕𝑐1𝑥1⊕𝑐2𝑥2⊕…⊕𝑐𝑛𝑥𝑛} 𝑐0,𝑐1…𝑐𝑛∈{0
Registermasina käsud saab Cantori numbrite järgi kodeerida.. Seega saab programmi koodiks naturaalarv, millest saab leida prorammi pikkuse, iga käsu eraldi, jne. F.-nide ühakohalised esindajad: Kui superpositsioonioperaatori suhtes kinnine f.-nide klass sisaldab korteezhide kodeerimise ja dekodeerimise f.-ne cm,c1m, cmm, siis selle klassi iga m-kohalise f.- ni f jaoks leidub samasse klassi kuulub ühekohaline esindaja ühe muutuja f.-n, nii, et iga esialgse f.-ni argumentvektori korral kehtib: f(x1,..xn) = g(cm(x1,..,xn)) Tõestus: Iga n = cm jaoks kehtib seos g(n) = f(c1m,..,cmm) Ühekohaliste esindajate leidmiseks peame sisse tooma 4 operaatorit: Kõik peab kehtia kõigi argumentvektorite korral Liitmisoperaator: h(x) = f(x) + g(x) h=fog Kompositsioonioperaator: h(x) = g(f(x)) f=f*g Pööramisoperaator: h(x) = z[f(z) - x] h = f-1 Lahutamistehe on määratud, kui f(z)>= x Iteratsioonioperaator: h(x) = f(f(...f(0)..
𝐾1 = {𝑓(𝑥1 … 𝑥𝑛 ) | 𝑓(11 … 1) = 1} {𝑓1 , 𝑓3 , 𝑓5 , 𝑓7 , 𝑓9 , 𝑓11 , 𝑓13 , 𝑓15 } ⊂ 𝐾1 Pööratav – kui ta oma kõikide muutujate väärtuste inverteerimisel iverteerub ka ise 𝐾𝑝 = {𝑓(𝑥1 … 𝑥𝑛 ) | 𝑓(𝑥 𝑥𝑛 = 𝑓 ̅(𝑥1 … 𝑥𝑛 )} ̅̅̅1 … ̅̅̅) {𝑓3 , 𝑓5 , 𝑓10 , 𝑓12 } ⊂ 𝐾𝑝 Monotoonne – kui argumentvektori suurenemisel F-ni väärtus ei vähene 𝐾𝑚 = {𝑓(𝑥1 … 𝑥𝑛 ) | (𝑥1 … 𝑥𝑛 < 𝑧1 … 𝑧𝑛 ) ↔ [𝑓(𝑥1 … 𝑥𝑛 ) ≤ 𝑓(𝑧1 … 𝑧𝑛 )]} {𝑓0 , 𝑓1 , 𝑓3 , 𝑓5 , 𝑓7 , 𝑓15 } ⊂ 𝐾𝑚 Lineaarne – kui ta on esitatav kujul 𝑐0 ⊕ 𝑐1 𝑥1 ⊕ 𝑐2 𝑥2 ⊕ … ⊕ 𝑐𝑛 𝑥𝑛 , kus iga const 𝑐𝑖 ∈ {0 1}
Olgu selle Gödeli numbriks U. φU(i,x) = φi(x) Defineerime g nii, et φg(i)(x)=φU(φU(i,i),x) s-n-m teoreemi põhjal on g arvutatav. Universaalne funktsioon: k+1-kohalist funktsiooni U nimetatakse funktsioonide klassi alamklassi (klassi F k argumendiga klassid) Fk universaalseks funktsiooniks, kui: • iga väärtusega a ja muutujatega x1,..,xk funktsioon U(a,x1,..xk) kuulub klassi Fk • iga Fk klassi funktsiooni korral eksisteerib naturaalarv b, nii et iga argumentvektori korral kehtib võrdus f(x1,..,xk) = U(b,x1,..,xk) Kui funktsioonide klassis on ka Cantori funktsioonid ja selle pöördf.-nid, saab universaalse funktsiooni asendada selle ühekohalise esindajaga (klassi F1 universaalse funktsiooniga). 25 Rice'i teoreem. DEF: Hulka (keelt), millel leidub karakteristlik Turingi masin, nimetatakse lahenduvaks ehk rekursiivseks. DEF: Arvutatavate f-de hulk, mis ei võrdu osaliste rekursiivsete funktsioonide hulgaga, on mittetriviaalne.
annaabi.ee 
