15. Funktsionaalselt täielikud süsteemid Loogika elementide süsteemi mis realiseerib kõikki kahe argumendi funktsioone nimetatakse funktsionaalselt täielikuks süsteemiks nt. NING, VÕI ja EI. Minimaalne funktsionaalselt täielik süsteem on selline millest ükskõik millise elemendi väljajätmine muudab süsteemi mittetäielikuks. Nt.VÕI EI või NING EI. 16. Täielik disjunktiivne normaalkuju e. TDNK DNK on loogika funktsiooni esitamine realiikmete disjunktsioonina (summana), kus liikmed on argumentide või argumentide inversioonide elementaarkonjunktsioonid (korrutised). Elementaarkonjunktsioonid on nt. 1 × 2 × 3 ; Elementaarkonjunktsioonid ei ole nt. X2*X3*X3; X1*X3; X3*X4*X5 TDNK puhul peavad kõik liikmed sisaldama funktsiooni kõikki argumente või nende inversioone. Kui algfunktsioon on antud tabelina siis saab TDNK otse tabelist välja kirjutada. 17. Loogikaavaldise lihtsustamine Kornaugh kaardiga.
i= 1 (x) i i , kus ( xi) = x ,kui_ = 0 i i Iga loogikafunktsioon on esitatav oma konstituentide disjunktsioonina. Loogikafunktsiooni esitamiseks kasutame loogikavalemeid. · Loogikavalem on samaselt tõene, kui iga argumentide vektori ( x1 , x2 ,..., xn ) puhul f(x1 , x2 ,..., xn )=1. Samaselt tõene valem - tautoloogia. · Loogikavalem on samaselt väär, kui iga argumentide vektori ( x1 , x2 ,..., xn ) puhul f(x1 , x2 ,..., xn )=0. · Loogikavalemid f1 ja f2 samaväärsed, kui iga argumentide vektori ( x1 , x2 ,..., xn ) puhul f1(x1 , x2 ,..., xn )= f2(x1 , x2 ,..., xn )=.
i 1 i , kus xi x ,kui_ 0 i i Iga loogikafunktsioon on esitatav oma konstituentide disjunktsioonina. Loogikafunktsiooni esitamiseks kasutame loogikavalemeid. Loogikavalem on samaselt tõene, kui iga argumentide vektori ( x1 , x2 ,..., xn ) puhul f(x1 , x2 ,..., xn )=1. Samaselt tõene valem - tautoloogia. Loogikavalem on samaselt väär, kui iga argumentide vektori ( x1 , x2 ,..., xn ) puhul f(x1 , x2 ,..., xn )=0. Loogikavalemid f1 ja f2 samaväärsed, kui iga argumentide vektori ( x1 , x2 ,..., xn ) puhul f1(x1 , x2 ,..., xn )= f2(x1 , x2 ,..., xn )=.
1 0 + - - + 0 1 0 + - - + 1 1 1 + + - - 0 1 1 + + - - 0 Digitaaltehnika konspekt 20 4. Kombinatsioonseadmete süntees 4.1. Loogikafunktsiooni täielik disjunktiivne normaalkuju ehk TDNK DNK on loogika funktsiooni esitamine rea liikmete disjunktsioonina (summana), kus liikmed on argumentide või argumentide inversioonide elementtaar konjunktsioonid (korrutised). Elementtaar konjunktsioon on näiteks: x1 gx2 gx3 ; x2 gx3 gx4 . Elementtaar konjunktsioon ei ole näiteks: x1 gx2 gx2; x1 gx2 gx4 ; x2 gx3 gx4 TDNK puhul peavad kõik liikmed sisaldama funktsiooni kõiki argumente või nende inversioone. Üleminekuks DNK-lt TDNK-le tuleb iga liiget, kus puudub mõni argument laiendada avaldisega xi + xi , kus xi on liikmes puuduv argument.
1 0 + - - + 0 1 0 + - - + 1 1 1 + + - - 0 1 1 + + - - 0 Digitaaltehnika konspekt 20 4. Kombinatsioonseadmete süntees 4.1. Loogikafunktsiooni täielik disjunktiivne normaalkuju ehk TDNK DNK on loogika funktsiooni esitamine rea liikmete disjunktsioonina (summana), kus liikmed on argumentide või argumentide inversioonide elementtaar konjunktsioonid (korrutised). Elementtaar konjunktsioon on näiteks: x1 gx2 gx3 ; x2 gx3 gx4 . Elementtaar konjunktsioon ei ole näiteks: x1 gx2 gx2; x1 gx2 gx4 ; x2 gx3 gx4 TDNK puhul peavad kõik liikmed sisaldama funktsiooni kõiki argumente või nende inversioone. Üleminekuks DNK-lt TDNK-le tuleb iga liiget, kus puudub mõni argument laiendada avaldisega xi xi , kus xi on liikmes puuduv argument.
elementaarfunktsioonide hulka kõik rohkem kui kahe argumendiga funktsioonid, milles argumendid on omavahel seotud kas ainult disjunktsiooni- või ainult konjunktsioonitehtega. Boole'i funktsiooni standardesituseks on tema normaalkuju. Loogikafunktsiooni normaalkuju koosneb elementaarkonjunktsioonidest (konjunktsioonitehte abil seotud otsestest või inverteeritud muutujatest, kus iga muutuja esineb vaid üks kord). Kui loogikafunktsioon on esitatud elementaarkonjunktsioonide disjunktsioonina, nimetatakse esitusviisi funktsiooni disjunktiivseks normaalkujuks (DNK). Vähem kasutatakse loogikafunktsiooni konjunktiivset normaalkuju (KNK), mil funktsioon esitatakse elementaardisjunktsioonide konjunktsioonina. Kui funktsiooni disjunktiivse normaalkuju iga elementaarkonjunktsioon sisaldab kõiki muutujaid, nimetatakse funktsiooni esitusviisi tema täielikuks disjunktiivseks normaalkujuks (TDNK). Täielikku disjunktiivset normaalkuju on hõlpus leida loogikafunktsiooni oleku- ehk
Täielik disjunktiivne normaalkuju Lihtkonjunktsioon on muutujate või nende eituste konjunktsioon. Näiteks X ¬Y, X Y ¬Y ja X on lihtkonjunktsioonid. Täielik lihtkonjunktsioon on lihtkonjunktsioon, milles iga muutuja esineb täpselt ühe korra. Näiteks muutujate X, Y ja Z korral on ¬X Y ¬Z täielik lihtkonjunktsioon. Valemi disjunktiivne normaalkuju (DNK) on loogiliselt samaväärne valem, mis esitub lihtkonjunktsioonide disjunktsioonina. Näiteks X Y ¬X ¬Y on disjunktiivsel normaalkujul olev valem. Valemi täielik disjunktiivne normaalkuju (TDNK) koosneb täielikest lihtkonjunktsioonidest. TDNK leidub, kui valem on kehtestatav. Loogiliselt samaväärsed valemid: 1) ¬ ¬X OX 2) a) X Y Y X b) X Y Y X c) X Y Y X 3) a) (X Y ) Z X (Y Z) b) (X Y ) Z X (Y Z) c) (X Y ) Z X (Y Z) 4) a) (X Y ) Z X Z Y Z b) X Y Z (X Z) (Y Z)
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Boole'i funktsiooni standardesituseks on tema normaalkuju. Loogikafunktsiooni normaalkuju koosneb elementaarkonjunktsioonidest (konjunktsioonitehte abil seotud otsestest või inverteeritud muutujatest, kus iga muutuja esineb vaid üks kord). Kui loogikafunktsioon on esitatud elementaarkonjunktsioonide disjunktsioonina, nimetatakse esitusviisi funktsiooni disjunktiivseks normaalkujuks (DNK). Vähem kasutatakse loogikafunktsiooni konjunktiivset normaalkuju (KNK), mil funktsioon esitatakse elementaardisjunktsioonide konjunktsioonina. Kui funktsiooni disjunktiivse normaalkuju iga elementaarkonjunktsioon sisaldab kõiki muutujaid, nimetatakse funktsiooni esitusviisi tema täielikuks disjunktiivseks normaalkujuks (TDNK). Täielikku disjunktiivset
23 Lühemas kirjaviisis [(p → q) & (t → s)], p ⊕ t ⊨q ∨ s. Liitne välistav jaatava moodusega dilemma sisaldab alternatiivses eelduses alternatiivi suurema eelduse tingivate lausete aluste vahel ning lõppjärelduses esineb disjunktsioon kõnealuste tingivate lausete tagajärgede vahel. Lausearvutuse tabelite abil saab tõestada, et kui välistava konstruktiivse dilemma lõppjäreldus postuleerida tagajärgedevahelise välistava disjunktsioonina, siis on arutlus lausearvutuse mõttes mittekehtiv, ning kui see postuleerida hariliku disjunktsioonina, on arutlus kehtiv, vt tabel 10.6. Tabel 10.6. Keerulise konstruktiivse välistava dilemma kehtivuse hindamise tabel. Uuritav skeem on [(p → q) & (t → s)], p ⊕ t; q ⊕ s, mõlema eelduse tõesust võib käsitleda kui nende konjunktsiooni tõesust. On näha, et süllogism ei kehti, seega [(p → q) & (t → s)], p ⊕ t ⊭ q ⊕ s
Lühemas kirjaviisis [(p q) & (t s)], p t q s. Liitne välistav jaatava moodusega dilemma sisaldab alternatiivses eelduses alternatiivi suurema eelduse tingivate lausete aluste vahel ning lõppjärelduses esineb disjunktsioon kõnealuste tingivate lausete tagajärgede vahel. Lausearvutuse tabelite abil saab tõestada, et kui välistava konstruktiivse dilemma lõppjäreldus postuleerida tagajärgedevahelise välistava disjunktsioonina, siis on arutlus lausearvutuse mõttes mittekehtiv, ning kui see postuleerida hariliku disjunktsioonina, on arutlus kehtiv, vt tabel 10.6. Tabel 10.6. Keerulise konstruktiivse välistava dilemma kehtivuse hindamise tabel. Uuritav skeem on [(p q) & (t s)], p t; q s, mõlema eelduse tõesust võib käsitleda kui nende konjunktsiooni tõesust. On näha, et süllogism ei kehti, seega [(p q) & (t s)], p t q s
annaabi.ee 
