Návrat na detail prednášky / Stiahnuť prednášku / Univerzita Konštantína Filozofa / Fakulta prírodných vied / Logické systémy počítačov

lekcia 3 (lekcia_3.doc)

Pojem Boolovskej funkcie (BF)

V predchádzajúcej časti vidno, že základný význam pri opise správania logických obvodov majú dvojhodnotové funkcie s dvojhodnotovými premennými. Takéto funkcie sa nazývajú boolovské.

BF premenných x1,.....x0 nám predstavuje zobrazenie, ktoré n-ticiam hodnôt 0,1 priradzuje hodnotu 0 alebo 1  f(0,1)n →{0,1}

Oborom funkcie je množina {0,1}n = X{0.1}, t. j. mno6ina v3etk7ch n/tíc s prvkami 0 a 1, ktorým zodpovedajú všetky možné usporiadané n-tice hodnôt premenných x1, x2....xn. Obor obsahuje práve 2n rôznych n-tíc. Kooborom (oborom hodnôt) funkcie je množina {0,1}.

[1]

Boolovská funkcia priraďuje teda každej n-tici hodnôt premenných určitú hodnotu 0 alebo 1. Usporiadané n-tice, vektory z množiny {0,1}n, sa v niektorých súvislostiach nazývajú aj body (daného oboru). Body, v ktorých daná funkcia f nadobúda hodnotu 0 alebo 1, sa nazývajú nulobé alebo jednotkové body funkcie f. Z definície B-funkcie vyplýva, že existuje 22n rôznych B-funkcií n premenných.

Pri riešení praktických úloh návrhu logických obvodov sa stretávame s neúplnými B-funkciami.

Neúplná B-funkcia f(x1,x2,....,xn) je zobrazenie

f: Q→{0,1}, kde Q patrí {0,1}n.

Oborom neúplnej B-funkcie je vlastná podmnožina množiny {0,1}n. Funkcia nie je teda definovaná vo všetkých bodoch oboru {0,1}n B-funkcie n premenných. Príklad neúplnej B-funkcie je na obr. [2]

[2]

Obor Q tu tvorí takáto množina trojích hodnôt premenných:

Q={000,001,011,100,111}. Funkcia f3 nie je definovaná v bodoch 010,101 a 110. Tieto body sa nazývajú nedefinované body funkcie f3.

Pri riešení praktických úloh je výhodné zaviesť všeobecnejšiu definíciu boolovskej funkcie, a to ako zobrazenie:

                            f(x3,....xn): (0,1)n→{0,1,x}

Oproti predchádzajúcej definícii boolovskej funkcie je koobor rozšírení o “hodnotu x”. Symbol “x” sa interpretuje ako neurčená, t.j. ľubovoľná hodnota 0 alebo 1.

Takto definované funkcie nazývame rozšírené boolovské funkcie (B-funkcie). Množina rozšírených B-funkcií s n premennými obsahuje 32n rôznych funkcií a zahŕňa v sebe predtým uvedené neúplné B-funkcie a 22n funkcií {0,1}n→{0.1}, ktoré (na rozlíšenie) nazývame úplné. Pri interpretácii rozšírenej B-funkcie ako neúplnej B-funkcie, bod oboru s hodnotou “x” sa chápe ako nedefinovaný bod. Napríklad na obr.[3]

[3]

je rozšírená B-funkcia f, ktorá zodpovedá neúplnej B-funkcii z obr.[2] Nech f je rozšírená a f´ je úplná B-funkcia s n-premennými. Potom funkciu f´ nazývame rovnocennú s funkciou f práve vtedy, ak f´ a f majú mimo neurčených bodov rovnaké hodnoty (0 alebo 1).

V ďalšom zavedieme pojem vzdialenosti bodov oboru {0,1}n. Tento pojem je užitočný pri riešení viacerých úloh z oblasti teórie a návrhu logických obvodov a mnohých ďalších úloh Týmto zavedieme určitú metriku na množine {0,1}n, ktorá spolu s touto metrikou tvorí metrický priestor. Vzdialenosť d(i,j) dvoch n-tíc (vektorov, bodov) i aj z množiny {0,1}n definujeme ako počet miest, v ktorých sa tieto n-tice líšia. Napríklad d(01101,01010)=3, pretože tieto pätice sa líšia na treťom, štvrtom a piatom mieste. Definovaná vzdialenosť sa nazýva aj Hammingova vzdialenosť. Dve n-tice (vektory, body) i,j sa nazývajú susedné práve vtedy, ak d(i,j)=1.  Susedné n-tice majú teda rôzne hodnoty práve na jednom mieste.

Pre definovanú funkciu vzdialenosti platia takéto tvrdenia:

        1.d(i,j)=d(j,i)

        2.d(i,j)=0 <=>i=j

        3.d(i,k)<=d(i,j)+d(j,k)

        (trojuholníková nerovnosť)

Spôsoby zápisu booleovských funkcií

Tabuľkové a číselné zápisy

Jeden spôsob zápisu B-funkcií sme už uviedli, a to zápis pomocou tabuľky. Takáto tabuľka sa nazýva často pravdivostná. Názov pochádza z výrokového počtu v matematickej logike, kde B-funkcie sa nazývajú pravdivostné alebo výrokové funkcie. Hodnotám 0 a 1 premenných a funkcií sa tam priraďuje význam nepravdivosti alebo pravdivosti. Pravdivostnú tabuľku možno použiť na zápis ľubovoľnej B-funkcie s „rozumným“ počtom premenných alebo počtom bodov definičného oboru. Z praktických dôvodov sa však často používajú iné, úspornejšie alebo názornejšie zápisy, ktoré opíšeme v tejto časti.

Zmenšenie počtu riadkov pravdivostnej tabuľky možno dosiahnuť úspornejším vyjadrením podmnožín bodov z oboru {0,1}n, pri ktorých má daná B-funkcia rovnakú hodnotu. Využíva sa tu možnosť vyjadrenia podmnožín vektorov pomocou jedného špeciálneho, neurčitého vektora, ktorý má nedefinované miesta, t.j. ktorý obsahuje na niektorých miestach aj symboly pre ľubovoľnú (nedefinovanú) hodnotu. Tak napríklad vektor 1x10x1 (kde “x” značí ľubovoľnú hodnotu 0 alebo 1 na príslušnom mieste) opisuje množinu všetkých tých vektorov, ktoré majú na prvom, treťom, štvrtom a šiestom mieste predpísanú hodnotu (a na druhom a piatom mieste sa líšia). Je to množina {101001,111001,101011,111011}. Z toho vyplýva, že takáto množina obsahuje vo všeobecnosti práve 2k vektorov, ak k značí počet nedefinovaných miest.

S využitím opísaného spôsobu zápisu podmnožín vektorov možno neúplnú B-funkciu f3 zapísať napr. tabuľkou z obr.[1]

[1]

Množina jednotkových bodov je vyjadrená dvoma vektormi x 11 a 0x1, ktoré opisuje množina {011,111}a{001,011}. Množina nulových bodov {000,100} je opísaná jedným vektorom x00. Treba si uvedomiť, že vôbec nevadí, ak jednotlivé množiny bodov s rovnakou hodnotu funkcie, opísané rôznymi neurčitými vektormi, sa prekrývajú. V predloženom príklade sa vektor 011 nachádza v množine x11 a 0x1.

Tabuľku z obr.[1] nazývame zhustená pravdivostná tabuľka. Takýto zápis sa často používa v praxi. Úspora počtu riadkov závisí od danej B-funkcie alebo systému B-funkcií. Niektoré funkcie poskytujú iba malé (a prípadne aj žiadne) možnosti úspory. V mnohých prípadoch, ktoré sa vyskytujú v praxi, možno však efektívne využiť opísaný spôsob zápis.

Prirodzené usporiadanie bodov oboru B-funkcie je také, ktoré vychádza z ich zobrazenia na čísla v dvojkovej číselnej sústave. Základom tohto zobrazenia je prisúdenie významu číslice 0 alebo 1 symbolom 0 alebo 1. Usporiadaná n-tica sa potom chápe ako celé číslo v dvojkovej číselnej sústave s najmením rádom vpravo s narastaním váhy rádu sprava doľava.

Tak napríklad 5-tica 10111 sa zobrazuje na dvojkové číslo 10111, ktorého ekvivalentné číslo v desiatkovej sústave je

                1.24 + 0.23 + 1.22 + 1.21 + 1.20 = 2310

Takýmto spôsobom priradené číslo n-tici sa nazýva index n-tice.

Ďalší spôsob zápis úplných B-funkcií používa súpis množín jednotkových alebo nulových bodov danej funkcie, pričom jednotlivé body sa vyjadrujú pomocou svojichindexov. Úplnú B-funkciu f2 troch premenných, ktorá je uvedená na obr.[2]

[2]

aj s indexmi pri jednotlivých bodoch oboru, zapíšeme f2(x1,x2,x3) D(1,2,3,7) alebo f2(x1,x2,x3)=K(0,4,5,6)

Symbol D (alebo K) tu označuje, že ide o súpis indexov jednotkových (alebo nulových) bodov funkcie. Indexy sa vyjadrujú vo forme desiatkových čísel. Takýto zápis nepostačuje pri rozšírených alebo neúplných funciách. Pre jednoznačnosť zápisu tu treba uvádzať súpisy indexov dvoch množín bodov. Obyčajne sa uvádza súpis indexov jednotkových alebo nulových bodov a súpis indexov nedefinovaných (neurčených) bodov.

Pri tejto konvencii možno funkciu f3 zapísať

f3(x1,x2,x3)=D(1,3,7(2,5,6)) alebo

f3(x1x2x3)=K(0,4(2,5,6))

Medzi vnútornými zátvorkami sú uvedené indexy nedefinovaných bodov. Opísané spôsoby zápisu nazývame číselné zápisy.

Zápisy používajúce geometrické znázornenie funkcii

Pri práci na papieri (a s grafickými pomôckami vôbec) sa dobre pracuje so zápismi B-funkcií v mapách. Mapa je geometrické znázornenie oboru {0,1}n B-funkcie v rovine pomocou siete štvorčekov, pričom každému bodu oboru je podľa použitého kódovania priradený jeden štvorček. Mapu tvorí sieť obsahujúca 2n štvorčekov. Príklad mapy pre n=4 a spôsob priradenia štvorčekov jednotlivým štvoriciam hodnôt premenných x1,x2,x3 a x4 (t. j. spôsob kódovania) je uvedený na obr. [1]

[1]

Pomocou kódovacích čiar úsečiek pri ľavom a hornom okraji mapy a pomocou pripísaných premenných sú vyznačené oblasti obsahujúce 2n-1 štvorčekov, v ktorých jednotlivé premenné nadobúdajú hodnotu 1 alebo 0. Predpokladá sa, že v oblasti, ktorá sanachádza pod čiarou (pre premenné x3 a x4) alebo vedľa čiary pre premenné x1 a x2, príslušná premenná nadobúda hodnotu 1 a mimo tejto oblasti nadobúda hodnotu 0. Týmto spôsobom je jednoznačne definovaný vzťah medzi n-ticami a štvorčekmi. Tak napr. štvorčekom vyznačeným na obr.[1] značkami “+” a “*” zodpovedajú vektory 0100, prípadne 1011.

Práve opísaná mapa sa nazýva Karnaughova mapa. V ďalšom opíšeme induktívnu metódu tvorby takýchto máp s ľubovolným počtom premenných:

1. Mapa M1 pre jednu premennú (n=1) je naznačená na obr.[2a]

[2]

2. Ak je k dispozícii mapa Mk pre k premenných x1,...,xk mapa Mk+1 pre k+1 premenných sa zostaví tak, že k mape Mk sa priloží jej zrkadlový obraz [2b], ktorý sa celý označí kódovacou čiarou pre premennú xk+1. Pri postupe sa vychádza zo snahy mapu Mk+1 zostaviť v tvare najbližšom ku štvorcu. Zvyšné kódovacie čiary sa odstránia. Obyčajne sa ponechajú iba tie, ktoré sú pri ľavom a hornom okraji mapy.

Na obrázku [3]

[3]

sme naznačili spôsob zostavenia máp pre 2, 3 a 5 premenných. V poslednom prípade sme za základ vzali mapu pre 4 premenné z obr. [1]

Pri kreslení máp pripúšťame ľubovoľné priradenie premenných jednotlivým kódovacím čiaram.

Výhodou Karnaughových máp pre n<=4 je, že susedné body a im zodpovedajúce susedné štvorčeky sú v týchto mapách zároveň aj geometricky susedné.

Za geometricky susedné považujeme pritom dva štvorčeky so spoločnou hranou. Vychádza sa tu z predstavy, že pri n=3 sa ľavý okraj stotožní s pravým okrajom mapy a pri n=4 sa naviac horný okraj stotožní s dolným okrajom mapy. Práve opísaná vlastnosť umožňuje ľahké vyhľadávanie susedných štvorčekov v mape do štyroch premenných. V mapách pre n>4 sa stráca výhoda totožnosti definovanej susednosti s geometrickou susednosťou, čo vyplýva zo spomenutej nesúvislosti oblastí. Niektoré susedné štvorčeky nie sú jednoducho geometricky susedné. Vidno to v mape na obr. [4a]

[4]

kde sú pomocou už zavedenej symboliky vyznačené všetky štvorčeky susedné so štvorčekom a alebo b. Štvorček označený hrubším symbolom + nemožno považovať za geometricky susedný so štvorčekom a.

Ako sme už uviedli, mapa predstavuje určité rovinné geometrické zobrazenie oboru B-funkcie. Funkcia sa zapíše do mapy tak, že do jednotlivých štvorčekov sa vpíše hodnota funkcie (0,1,x) v príslušnom bode. Pri neúplných B-funkciách možno nedefinované body ponechať aj prázdne.

Výrazy

Pojem výrazu a jeho hodnoty

Významnú úlohu pri zápise B-funkcií, analýze, syntéze, modelovaní a simulácii logických obvodov zohrávajú logické výrazy, ktoré sa v ďalšom nazývajú jednoducho výrazy.

Výraz je postupnosť (reťazec) symbolov, obsahujúca symboly konštánt (0,1), symboly premenných a operácií (•,+,↑,↓,→,↔,≡) a zátvorky na vyznačenie oblasti a poradia pôsobenia operácií. Výraz definujeme rekurzívnym spôsobom formálne takto:

1. 0 a 1 sú výrazy.
2. Ak x je premenná, tak x´ je výraz.
3. Ak A je výraz, tak aj A´ je výraz.
4. Ak A,B,C,... sú výrazy, tak aj nasledujúce postupnosti

A•B, A+B, A-B-C... A↑B↑C..., A≡B, A→B, A↔B

        sú výrazy.

Definované operácie •,+,↑,↓,→,↔,≡ vo výrazoch sú tie, ktoré majú najväčší význam v inžinierskej praxi pri práci s logickými obvodmi. Mohli by sme podobne zaviesť aj ďalšie operácie. Obyčajne sa zavádzajú takéto názvy operácií:

        • logický súčin, konjunkcia

        + logický súčet, disjunkcia

        – negácia

        ↓ Pierceho operácia, negácia logického súčtu

        ↑ Shefferova operácia, negácia logického súčinu

        + v krúžku (nenašiel som medzi symbolmi) neekvivalencia (súčet modulo 2)

        ≡ ekvivalencia

        → implikácia

        ↔ inhibícia

V literatúre a i v praxi sa možno stretnúť s ďalšími názvami operácií. Sú to napr.:

logický súčin                 operácia „A“ (príp. „AJ“) alebo „AND“

logický súčet                operácia „ALEBO“, prípadne „NOR“ (anglický ekvivalent ANI, prípadne anglická skratka pre NOT- OR, NIE-ALEBO)

Shefferova operácia        operácia „NAND“ (anglická skratka pre NOT-AND, NIE-A)

Neekvivalencia        operácia „XOR“ (anglická skratka pre Exclusive OR)

Normálne formy výrazov

Normálne formy výrazov predstavujú určité štandardné výrazy, ktoré sú užitočné pri zápise B-funkcií a majú veľký význam pri analýze a syntéze kombinačných obvodov.

Pred uvedením pojmu normálna forma najskôr objasníme pojmy písmeno a term.

Ak x je premenná, tak jednoduchý výraz x alebo x´ nazývame písmenom a označujeme ho symbolom x´. Nech xi1, xi2 ....,xik, k>=1, sú rôzne premenné a nech g je k-nárna operácia. Potom výraz v tvare xi1g xi2g ...g xik nazývame term typu g (triviálny prípad termu, ktorý obsahuje iba jedno písmeno).

Teraz definujeme pojem normálna forma (NF). Nech T1,T2 ,..., Tm, m>1, sú navzájom rôzne termy typu g1 a nech g2 je m-árna operácia. Potom výraz v tvare

        T1g2 T2 g2 ... g2 Tm nazývame normálna forma typu g1/g2 označujeme ho skrátene NF g1/g2.

Disjunktívna normálna forma

-súčet elementárnych súčinov

-elementárnym súčinom nazývame logický súčin ľubovoľného počtu premenných, v ktorom premenné vystupujú priamo alebo invertovane a každá premenná sa v tomto súčine vyskytuje maximálne raz.

-úplný elementárny súčin je taký, v ktorom sa každá premenná vyskytuje práve raz

-rád elementárneho súčinu je počet prvkov v elementárnom súčine 1<=r<=n

Úplná disjunktívna normálna forma

-súčet úplných elementárnych súčinov

Skrátená disjunktívna normálna forma

-ak v UDNF uplatníme spojovacie pravidlo (xy+xy´=y) (susedné prvky rovnakej hodnoty spojíme)

Iredundantná disjunktívna normálna forma

-taká, keď SDNF vynecháme redundantné členy

-môže ich existovať viac

Minimálna iredundantná disjunktívna normálna forma

(susedné prvky rovnakej hodnoty spojíme)

Iredundantná disjunktívna normálna forma

-taká, keď SDNF vynecháme redundantné členy

-môže ich existovať viac

Minimálna iredundantná disjunktívna normálna forma

-minimálna IDNF

Ak funkciu rozložíme na súčin implicentov ->UKNF->SKNF->IKNF->MIKNF

Pierceova algebra

[1]

-obsahuje jedinú operáciu inverziu logického súčtu

-táto operácia sa nazýva aj NOR

Shefferova algebra

[2]

-obsahuje jedinú operáciu inverziu logického súčinu

-táto operácia sa nazýva aj NAND