Domov > Geografia > Konjunktívna normálna forma logickej funkcie sa nazýva. Konjunktívne formy reprezentácie logických funkcií


Konjunktívna normálna forma logickej funkcie sa nazýva. Konjunktívne formy reprezentácie logických funkcií





Príklad. Nájdite vzorce CNF

~ ~

Dokonalá disjunktívna normálna forma SDNF môže byť skonštruovaná pomocou nasledujúceho algoritmu:

1. = 1. Algoritmus DNF

2. = 2. Algoritmus DNF

3. = 3. Algoritmus DNF

4. = 4. Algoritmus DNF

5. Vynechajte rovnako nepravdivé výrazy, t. j. výrazy formulára

6. Doplňte zvyšné výrazy chýbajúcimi premennými

7. Opakujte bod 4.

Príklad. Nájdite vzorce sdnf.

~

Na zostavenie SKNF možno použiť nasledujúcu schému:

Príklad. Nájdite vzorce sdnf.


~

Je známe (vety 2.11, 2.12), že SDNF a SKNF sú jednoznačne definované vzorcom, a preto ich možno zostaviť podľa pravdivostnej tabuľky vzorca .

Schéma konštrukcie SDNF a SKNF podľa pravdivostnej tabuľky je uvedená nižšie pre vzorec ~ :

~
1 0 1 0 1 1 0 1 SDNF; SKNF.

2.2. Cvičenie.

2.2.1 Nižšie sú uvedené logické výrazy. Zjednodušte vyjadrenia svojej voľby čo najviac pomocou Booleových zákonov logiky. Potom pomocou pravdivostných tabuliek porovnajte svoj zjednodušený výraz s pôvodným.



2.2.2. Zistite otázku ekvivalencie f 1 a f 2 ich redukciou na SDNF (tabuľka 1).

2.2.3. Nájdite duálnu funkciu pre f 3 podľa zovšeobecneného a booleovského princípu (tabuľka 1). Porovnajte výsledky.

№ f1 f2 f 3

2.3. Kontrolné otázky.

2.3.1. Definujte vyhlásenie.

2.3.2. Uveďte základné operácie na výpise.

2.3.3. Čo je to pravdivá tabuľka?

2.3.4. Vytvorte pravdivostné tabuľky pre nasledujúce vzorce:

~ ~ ~ ;

2.3.5. Berúc do úvahy konvencie o poradí operácií, vynechajte vo vzorcoch „extra“ zátvorky a znamienko „“:

;

2.3.6. Použitím ekvivalentných transformácií dokážte identickú pravdivosť vzorcov:

2.3.7. Nájdite dvojité vzorce:

)

2.3.8. Zredukujte nasledujúce vzorce na dokonalú formu DNF (SDNF):

~

2.3.9. Preveďte nasledujúce vzorce do dokonalej formy CNF (SKNF):

~

Laboratórium č. 3

Predmet:„Minimalizácia booleovských funkcií. logika"

Cieľ: Získanie praktických zručností pri práci s metódami minimalizácie booleovských funkcií.

3.1. Teoretické informácie.

Minimálne formuláre

Ako je znázornené v , akákoľvek booleovská funkcia môže byť reprezentovaná v dokonalej normálnej forme (disjunktívna alebo konjunktívna). Takáto reprezentácia je navyše prvým krokom pri prechode od tabuľkovej definície funkcie k jej analytickému vyjadreniu. V budúcnosti budeme vychádzať z disjunktívnej formy a zodpovedajúce výsledky pre konjunktívnu formu získame na základe princípu duality.

Kanonický problém syntézy logických obvodov na booleovskej báze sa redukuje na minimalizáciu boolovských funkcií, t.j. na ich reprezentáciu v disjunktívnej normálnej forme, ktorá obsahuje najmenší počet písmen (premenné a ich negácie). Takéto formy sa nazývajú minimálne. Pri kanonickej syntéze sa predpokladá, že na vstupy obvodu sú privádzané oba signály a ich inverzie.

Vzorec uvedený v disjunktívnej normálnej forme je zjednodušený opakovanou aplikáciou operácie lepenia a operácie absorpcie a (duálne identity pre konjunktívnu normálnu formu sú: a ). Tu možno chápať akýkoľvek vzorec Booleovej algebry. Výsledkom je, že k takémuto analytickému vyjadreniu dospejeme vtedy, keď ďalšie transformácie už nie sú možné, t.j. dostaneme formu v slepej uličke.

Medzi slepými formami existuje aj minimálna disjunktívna forma a nemusí byť jedinečná. Aby ste sa uistili, že tento slepý formulár je minimálny, musíte nájsť všetky slepé formuláre a porovnať ich podľa počtu písmen, ktoré obsahujú.

Nech je napríklad funkcia daná v dokonalej normálnej disjunktívnej forme:

Zoskupenie členov a použitie operácie lepenia, máme .

Inou metódou zoskupovania dostaneme:

Obe formy slepej uličky nie sú minimálne. Ak chcete získať minimálny tvar, musíte hádať, aby ste zopakovali jeden výraz v pôvodnom vzorci (toto sa dá urobiť vždy). V prvom prípade môže byť takýmto členom . Potom . Pridaním výrazu dostaneme: . Po prejdení všetkých možných možností sa môžeme uistiť, že posledné dve formy sú minimálne.

Práca so vzorcami na tejto úrovni je ako blúdenie v tme. Proces hľadania minimálnych foriem sa stáva vizuálnejším a účelnejším, ak sa použijú grafické a analytické znázornenia a symboly špeciálne navrhnuté na tento účel.

Viacrozmerná kocka

Každému vrcholu -rozmernej kocky možno priradiť jednotkový prvok. Preto je podmnožina označených vrcholov zobrazením na -rozmernej kocke booleovskej funkcie premenných v dokonalej disjunktívnej normálnej forme. Na obr. 3.1 ukazuje takéto mapovanie pre funkciu z časti 3.7.

Obr.3.1 Zobrazenie funkcie prezentovanej v SDNF na trojrozmernej kocke

Na zobrazenie funkcie premenných prezentovaných v akejkoľvek disjunktívnej normálnej forme je potrebné vytvoriť súlad medzi jej miniterminami a prvkami -rozmernej kocky.

Minitermíny (-1) poradia možno považovať za výsledok zlepenia dvoch minitermínov -tej hodnosti (jednotkovej zložky), t.j. , Na -rozmernej kocke to zodpovedá nahradeniu dvoch vrcholov, ktoré sa líšia iba hodnotami súradníc spájajúcich tieto vrcholy, hranou (o hrane sa hovorí, že pokrýva vrcholy, ktoré k nej patria). Minitermíny rádu ( -1) teda zodpovedajú hranám -rozmernej kocky. Podobne minitermíny (-2)-tého rádu zodpovedajú stenám -rozmernej kocky, z ktorých každá pokrýva štyri vrcholy (a štyri hrany).

Prvky -rozmernej kocky charakterizované rozmermi sa nazývajú -kocky. Teda vrcholy sú 0-kocky, hrany sú 1-kocky, plochy sú 2-kocky atď. Zovšeobecnením vyššie uvedenej úvahy môžeme predpokladať, že miničlen ()-tej hodnosti v disjunktívnej normálnej forme pre funkciu premenných je zobrazený pomocou -kocky a každá -kocka pokrýva všetky tie -kocky najnižšej dimenzie, ktoré sú spojené s jeho vrcholmi. Ako príklad na obr. 3.2 je znázornené zobrazenie funkcie troch premenných. Tu minitermy a zodpovedajú 1-kocke () a minitermy sú reprezentované 2-kocikami ().

Obr.3.2 Pokrytie funkcií

Akákoľvek disjunktívna normálna forma je teda zobrazená na -rozmernej kocke množinou -kociek, ktoré pokrývajú všetky vrcholy zodpovedajúce jednotkovým zložkám (0-kocke). Platí aj opačné tvrdenie: ak určitá kolekcia -kociek pokrýva množinu všetkých vrcholov zodpovedajúcich jednotkovým hodnotám funkcie, potom je disjunkcia minitermov zodpovedajúcich týmto -kockam vyjadrením tejto funkcie v disjunktívnej normálnej forme. . Hovorí sa, že takáto zbierka -kociek (alebo im zodpovedajúcich minitermínov) tvorí obal funkcie.

Túžba po minimálnej forme je intuitívne chápaná ako hľadanie takého obalu, ktorého počet -kociek by bol menší a ich rozmery väčšie. Kryt zodpovedajúci minimálnemu tvaru sa nazýva minimálny kryt. Napríklad pre funkciu pokrytia na obr. 3.3 zodpovedá minimálnym formulárom A .

Ryža. 3.3 Pokrytie funkcií.

vľavo – ; napravo –

Zobrazenie funkcie na -rozmernej kocke je jasné a jednoduché, keď . Štvorrozmernú kocku možno nakresliť tak, ako je znázornené na obr. 3.4, ktorý zobrazuje funkciu štyroch premenných a jej minimálne pokrytie zodpovedajúce výrazu . Použitie tejto metódy vyžaduje také zložité konštrukcie, že sa strácajú všetky jej výhody.

Ryža. 3.4 Zobrazenie funkcií na štvorrozmernej kocke

Karnotove mapy

Ďalšia metóda na vykresľovanie logických funkcií používa Carnotove karty, čo sú špeciálne usporiadané vyhľadávacie tabuľky. Stĺpce a riadky tabuľky zodpovedajú všetkým možným množinám hodnôt nie viac ako dvoch premenných a tieto množiny sú usporiadané v takom poradí, aby sa každá nasledujúca množina líšila od predchádzajúcej o hodnotu iba jednej z premenných. . Vďaka tomu sa susedné bunky tabuľky horizontálne aj vertikálne líšia hodnotou len jednej premennej. Bunky umiestnené na okrajoch tabuľky sa tiež považujú za susediace a majú túto vlastnosť. Na obr. 3.5 ukazuje Karnaughove mapy pre dve, tri, štyri premenné.


Ryža. 3.5 Karnotove mapy pre dve, tri a štyri premenné

Rovnako ako v bežných pravdivostných tabuľkách sú bunky množín, na ktorých má funkcia hodnotu 1, vyplnené jednotkami (nuly sa väčšinou nezmestia, zodpovedajú prázdnym bunkám). Napríklad na obr. 3,6, A ukazuje Karnaughovu mapu pre funkciu, ktorej zobrazenie na štvorrozmernej kocke je uvedené na obr. 3.4. Pre zjednodušenie sú riadky a stĺpce zodpovedajúce hodnotám 1 pre niektorú premennú zvýraznené zloženou zátvorkou s označením tejto premennej.


Ryža. 3.6 Zobrazenie Carnotovho diagramu funkcie štyroch premenných

a) a jeho minimálne krytie b)

Medzi mapovaniami funkcií zapnuté n-rozmerná kocka a na Karnaughovej mape je korešpondencia jedna ku jednej. Na mape Carnot s-kocka zodpovedá množine 2 susedných buniek umiestnených v riadku, stĺpci, štvorci alebo obdĺžniku (berúc do úvahy blízkosť protiľahlých okrajov mapy). Preto všetky ustanovenia uvedené vyššie (pozri ods viacrozmerná kocka) platia pre Carnotove mapy. Takže na obr. 3,6, b je zobrazené pokrytie mapových jednotiek zodpovedajúce minimálnej disjunktívnej forme príslušnú funkciu.

Čítanie minitermínov z Karnotovej mapy prebieha podľa jednoduchého pravidla. Bunky, ktoré sa tvoria s-kocka, daj miniter (n–s) hodnosť, ktorá zahŕňa aj tie (n–s) premenné, ktoré si zachovávajú rovnaké hodnoty s-kocka, kde hodnota 1 zodpovedá samotným premenným a hodnota 0 zodpovedá ich negáciám. Premenné, ktoré si nezachovajú svoje hodnoty s-kocka, v miniterme absentujú. Rôzne spôsoby čítania vedú k rôznym reprezentáciám funkcie v disjunktívnej normálnej forme (pravá krajná je minimálna) (obr. 3.7).


Použitie Karnaughových máp vyžaduje jednoduchšie konštrukcie v porovnaní so zobrazením na n-rozmerná kocka, najmä v prípade štyroch premenných. Na zobrazenie funkcií piatich premenných sa používajú dve Karnotove mapy pre štyri premenné a pre funkciu šiestich premenných sa používajú štyri takéto mapy. S ďalším nárastom počtu premenných sa Karnotove mapy stávajú prakticky nepoužiteľné.

Známy v literatúre Veitchove karty sa líšia iba v inom poradí množín premenných hodnôt a majú rovnaké vlastnosti ako Karnaughove mapy.

Komplex kociek

Zlyhanie grafických metód pre veľký počet premenných je kompenzované rôznymi analytickými metódami na reprezentáciu booleovských funkcií. Jednou z týchto reprezentácií je komplex kociek, ktorý používa terminológiu viacrozmerného logického priestoru v kombinácii so špeciálne navrhnutou symbolikou.

). 0-kocky zodpovedajúce zložkám jednoty sú reprezentované množinami premenných hodnôt, na ktorých sa funkcia rovná jednote. Jednoznačne v zázname

Ryža. 3.8 Komplex kociek funkcií troch premenných ( A) a jeho symbolické znázornenie ( b)

Vytvára sa komplex kociek maximálne pokrytie funkcií. S výnimkou všetkých týchto s-kocky, ktoré sú pokryté kockami vyššej dimenzie, získame obaly zodpovedajúce slepým tvarom. Takže pre uvažovaný príklad (obr. 3.8) máme slepý kryt

,

čo zodpovedá funkcii . V tomto prípade je toto pokrytie tiež minimálne.

Pre dve booleovské funkcie operácia disjunkcie zodpovedá spojeniu ich komplexov v kocke a operácia konjunkcie priesečníku ich komplexov v kocke. Negácia funkcie zodpovedá sčítaniu komplexu kociek, t.j. a je určená všetkými vrcholmi, v ktorých funkcia nadobúda hodnotu 0. Existuje teda korešpondencia jedna ku jednej (izomorfizmus) medzi algebrou Booleovské funkcie a boolovské množiny reprezentujúce komplexy kociek.

Reprezentácia funkcie vo forme komplexov kociek je menej vizuálna, ale jej najdôležitejšou výhodou je, že sú odstránené obmedzenia počtu premenných a uľahčuje sa kódovanie informácií pri používaní počítačov.

Minimalizácia boolovských funkcií

Formulácia problému. Minimalizácia schémy na booleovskej báze je redukovaná na nájdenie minimálnej disjunktívnej formy, ktorá zodpovedá minimálnemu pokrytiu. Celkový počet písmen zahrnutých v normálnej forme je vyjadrený nákladmi na krytie , kde je počet - kociek tvoriacich pokrytie danej funkcie v n premenných. Minimálne krytie sa vyznačuje najnižšou hodnotou jeho ceny.

Zvyčajne sa problém minimalizácie rieši v dvoch krokoch. Najprv sa hľadá zmenšený obal, ktorý obsahuje všetky -kocky maximálneho rozmeru, ale neobsahuje žiadnu kocku pokrytú žiadnou kockou tohto obalu. Príslušná disjunktívna normálna forma sa nazýva redukovaná a jej minitermíny sa nazývajú jednoduché implikanty. Pre túto funkciu je znížené pokrytie jediné, ale môže byť zbytočné, pretože niektoré kocky sú prekryté kolekciami iných kociek.

V druhom kroku sa uskutoční prechod z redukovaných disjunktívnych normálnych foriem na slepé, z ktorých sa vyberú minimálne formy. Slepé formy sa tvoria vylúčením všetkých nadbytočných kociek zo zníženého pokrytia, bez ktorých zostávajúca množina kociek stále tvorí pokrytie danej funkcie, ale pri ďalšom vylúčení niektorej z kociek už nepokrýva množinu všetkých vrcholy zodpovedajúce jednotkovým hodnotám funkcie, t.j. prestávajú byť pokrytím.

Zmenšená kocka pokrytia, ktorá pokrýva vrcholy danej funkcie, ktoré nie sú pokryté žiadnou inou kockou, nemôže byť nadbytočná a bude vždy zahrnutá do minimálneho pokrytia. Takáto kocka, ako aj implikant, ktorý k nej prislúcha, sa nazýva extrém (esenciálny implikant) a ním pokryté vrcholy sa nazývajú zrušené vrcholy. Množina extrémov tvorí jadro pokrytia, je zrejmé, že pri prechode zo zníženého na minimálne pokrytie by sa v prvom rade mali vybrať všetky extrémy. Ak súbor extrémov netvorí kryt, tak je doplnený o kryt o kocky zo zmenšeného krytu.

Uvedené definície sú znázornené na obr. 3.9, kde je znížené pokrytie (pozri obr. 3.9a, ) a minimálne pokrytie (obr. 3.9b) a (pozri obr. 3.9b) sú vyjadrené nasledovne.

Predstavme si pojem elementárnej disjunkcie.

Elementárna disjunkcia je vyjadrením formy

Konjunktívna normálna forma (CNF) logickej funkcie je konjunkciou akejkoľvek konečnej množiny párovo odlišných elementárnych disjunkcií. Napríklad logické funkcie

sú konjunkcie elementárnych disjunkcií. Preto sa píšu v konjunktívnom normálnom tvare.

Ľubovoľná logická funkcia daná analytickým výrazom môže byť zredukovaná na CNF vykonaním nasledujúcich operácií:

Použitie pravidla inverzie, ak je operácia negácie aplikovaná na logický výraz;

Použitie axiómy distributivity vzhľadom na násobenie:

Použitie operácie absorbovania:

Výnimky v disjunkciách opakujúcich sa premenných alebo ich negáciách;

Odstránenie všetkých identických elementárnych disjunkcií okrem jednej;

Vymazanie všetkých disjunkcií, ktoré súčasne obsahujú premennú a jej negáciu.

Platnosť uvedených operácií vyplýva zo základných axióm a vzťahov identity algebry logiky.

Konjunktívna normálna forma sa nazýva dokonalá, ak každá elementárna disjunkcia v nej zahrnutá obsahuje v priamej alebo inverznej forme všetky premenné, od ktorých funkcia závisí.

Transformácia CNF na dokonalý CNF sa vykonáva vykonaním nasledujúcich operácií:

Doplnenia ku každej elementárnej disjunkcii konjunkcií premenných a ich negácií, ak nie sú zahrnuté v tejto elementárnej disjunkcii;

Použitie axiómy distributivity;

Odstránenie všetkých identických elementárnych disjunkcií okrem jednej.

Každá logická funkcia môže byť reprezentovaná v dokonalom CNF okrem

identicky rovné jednej (). Charakteristickou vlastnosťou dokonalého CNF je, že reprezentácia logickej funkcie v ňom je jedinečná.

Elementárne disjunkcie zahrnuté v dokonalej funkcii CNF sa nazývajú nulové zložky. Každá nulová zložka v dokonalom CNF zaniká na jedinej množine premenných hodnôt, ktorou je nulová množina funkcie. V dôsledku toho sa počet nulových množín logickej funkcie zhoduje s počtom nulových zložiek zahrnutých v jej dokonalom CNF.

Logická funkcia nulová konštanta v dokonalom CNF je reprezentovaná spojením 2nzložka nuly. Formulujme pravidlo na zostavenie SKNF logickej funkcie podľa korešpondenčnej tabuľky.

Pre každý riadok korešpondenčnej tabuľky, v ktorom sa funkcia rovná nule, sa zostaví elementárna disjunkcia všetkých premenných. Disjunkcia zahŕňa samotnú premennú, ak sa jej hodnota rovná nule, alebo negáciu, ak sa jej hodnota rovná jednej. Výsledné elementárne disjunkcie sú spojené spojkovým znamienkom.


Príklad 3.4. Pre logickú funkciu z(x), danú vyhľadávacou tabuľkou 2.2, definujeme dokonalý konjunktívny tvar.

Pre prvý riadok tabuľky, ktorý zodpovedá nulovej funkcii nastavenej na 000, nájdeme nulový komponent . Po vykonaní podobných operácií pre druhý, tretí a piaty riadok určíme požadovanú dokonalú funkciu CNF:

Treba si uvedomiť, že pre funkcie, ktorých počet jednotiek jednotiek prevyšuje počet množín nula, je kompaktnejšie písať ich v tvare SKNF a naopak.

normálna forma logický vzorec neobsahuje znaky implikácie, ekvivalencie a negácie neelementárnych vzorcov.

Normálna forma existuje v dvoch formách:

    konjunktívna normálna forma (CNF)-- spojenie viacerých disjunkcií, napríklad $\left(A\vee \overline(B)\vee C\right)\wedge \left(A\vee C\right)$;

    disjunktívna normálna forma (DNF)-- disjunkcia viacerých spojok, napríklad $\left(A\klin \overline(B)\klin C\right)\vee \left(B\klin C\right)$.

SKNF

Dokonalá konjunktívna normálna forma (SKNF) je CNF, ktorý spĺňa tri podmienky:

    neobsahuje identické elementárne disjunkcie;

    žiadna z disjunkcií neobsahuje rovnaké premenné;

    každá elementárna disjunkcia obsahuje každú premennú v danom CNF.

Akýkoľvek booleovský vzorec, ktorý nie je identicky pravdivý, môže byť reprezentovaný v SKNF.

Pravidlá pre konštrukciu SKNF podľa pravdivostnej tabuľky

Pre každú množinu premenných, pre ktoré je funkcia 0, sa zaznamená súčet, pričom premenné, ktoré majú hodnotu 1, sa berú s negáciou.

SDNF

Dokonalá disjunktívna normálna forma (PDNF) je DNF, ktorý spĺňa tri podmienky:

    neobsahuje zhodné elementárne spojky;

    žiadna zo spojok neobsahuje rovnaké premenné;

    každá elementárna konjunkcia obsahuje každú premennú z daného DNF, navyše v rovnakom poradí.

Akýkoľvek booleovský vzorec, ktorý nie je identicky nepravdivý, môže byť reprezentovaný v SDNF navyše jedinečným spôsobom.

Pravidlá pre konštrukciu SDNF podľa pravdivostnej tabuľky

Pre každú množinu premenných, v ktorej sa funkcia rovná 1, sa zapíše súčin a premenné, ktoré majú hodnotu 0, sa berú s negáciou.

Príklady nájdenia SKNF a SDNF

Príklad 1

Napíšte logickú funkciu podľa jej pravdivostnej tabuľky:

Obrázok 1.

Riešenie:

Použime pravidlo na zostavenie SDNF:

Obrázok 2

Dostávame SDNF:

Využime stavebné pravidlo SKNF.

Normálne formy booleovských funkcií Reprezentácia booleovskej funkcie vo forme disjunkcie konjunktívnych členov jednotkových zložiek Ki 2.7 sa nazýva disjunktívna normálna forma DNF tejto funkcie. obsahujú presne jednu po druhej všetky logické premenné brané s negáciami alebo bez nich, potom sa táto forma reprezentácie funkcie nazýva dokonalá disjunktívna normálna forma SDNF tejto funkcie. Ako vidíte, pri kompilácii funkcie SDNF musíte urobiť disjunkciu všetkých mintermov, pre ktoré má funkcia hodnotu 1.


Zdieľajte prácu na sociálnych sieťach

Ak vám táto práca nevyhovuje, v spodnej časti stránky je zoznam podobných prác. Môžete tiež použiť tlačidlo vyhľadávania


Prednáška 1.xx

Normálne formy booleovských funkcií

Znázornenie booleovskej funkcie vo forme disjunkcie konjunktívnych členov (jednotkový prvok) K i

, (2.7)

volal disjunktívna normálna forma(DNF) tejto funkcie.

Ak sú všetky spojovacie výrazy v DNF minterms , t.j. obsahujú presne jednu po druhej všetky logické premenné, brané s negáciami alebo bez nich, potom sa táto forma reprezentácie funkcie nazývadokonalá disjunktívna normálna forma(SDNF ) tejto funkcie. SDNF sa nazýva perfektné , pretože každý člen v disjunkcii zahŕňa všetky premenné; disjunktívny , pretože hlavnou operáciou vo vzorci je disjunkcia. Koncept "normálna forma” znamená jednoznačný spôsob zápisu vzorca, ktorý implementuje danú funkciu.

Vzhľadom na vyššie uvedené, veta 2.1 implikuje nasledujúcu vetu.

Veta 2. Akákoľvek boolovská funkcia(nie identicky rovné 0) môžu byť zastúpené v SDNF, .

Príklad 3 Nech máme tabuľkovú funkciu f (x 1, x 2, x 3) (tabuľka 10).

Tabuľka 10

f (x 1 , x 2 , x 3 )

Na základe vzorca (2.6) dostaneme:

Ako vidíte, pri kompilácii funkcie SDNF musíte urobiť disjunkciu všetkých mintermov, pre ktoré má funkcia hodnotu 1.

Znázornenie booleovskej funkcie vo forme spojenia disjunktívnych členov (zložka nula) D i

, (2.8)

volal konjunktívna normálna forma(CNF ) tejto funkcie.

Ak sú všetky disjunktívne pojmy CNF maxterms , t.j. obsahujú presne jednu po druhej všetky logické premenné funkcie, brané s negáciami alebo bez negácií, potom sa takýto CNF nazývadokonalá konjunktívna normálna forma(SKNF) tejto funkcie.

Veta 3. Akákoľvek boolovská funkcia(nie identicky rovné 1) možno predložiť SKNF, a toto zobrazenie je jedinečné.

Dôkaz vety možno vykonať podobne ako dôkaz vety 2.1 na základe nasledujúcej Shannonovej lemy o konjunktívnom rozklade.

Shannonova lemma . Akákoľvek boolovská funkcia f (x 1 , x 2 , ..., x m ) z m premenné môžu byť reprezentované ako:

. (2.9)

Treba poznamenať, že obe formy reprezentácie logickej funkcie (DNF a CNF) sú teoreticky rovnaké vo svojich schopnostiach: akýkoľvek logický vzorec môže byť reprezentovaný ako v DNF (okrem identickej nuly), tak aj v CNF (okrem identickej jednotky) . V závislosti od situácie môže byť znázornenie funkcie v jednej alebo druhej forme kratšie.

V praxi sa najčastejšie používa DNF., pretože táto forma je človeku známejšia: od detstva je zvyknutý viac sčítať produkty ako násobiť sumy (v druhom prípade chce intuitívne otvárať zátvorky a tým ísť do DNF).

Príklad 4. Pre funkciu f (x 1, x 2, x 3 ), uvedené v tabuľke. 10, napíšte to na SKNF.

Na rozdiel od SDNF sa pri kompilácii SKNF v pravdivostnej tabuľke logickej funkcie musíte pozrieť na kombinácie premenných, pre ktoré má funkcia hodnotu 0, a vytvoriť spojenie zodpovedajúcich maxtermov,ale premenné treba brať s inverznou inverziou:

Treba poznamenať, že nie je možné prejsť priamo z SDNF funkcie do jej SKNF alebo naopak. Pri pokuse o takéto transformácie sa získajú funkcie, ktoré sú inverzné k požadovaným. Výrazy pre funkcie SDNF a SKNF možno priamo získať iba z ich pravdivostnej tabuľky.

Príklad 5. Pre funkciu f (x 1, x 2, x 3 ), uvedené v tabuľke. 10, skúste prejsť z SDNF na SKNF.

Použitím výsledku z príkladu 2.3 dostaneme:

Ako vidíte, pod všeobecnou inverziou dostaneme SKNF logickej funkcie, ktorá je inverzná vzhľadom na funkciu získanú v príklade 2.4:

pretože obsahuje všetky maxtermy, ktoré nie sú vo výraze pre SKNF uvažovanej funkcie.

1. Pomocou vlastností operácií (pozri tabuľku 9) identita (), súčet modulo 2 (), implikácia () prejdeme na operácie AND, OR, NOT (na boolovskú bázu).

2. Pomocou vlastností negácie a de Morganových zákonov (pozri tabuľku 9) dosiahneme, že operácie negácie sa vzťahujú len na jednotlivé premenné, a nie na celé výrazy.

3. Pomocou vlastností logických operácií AND a OR (pozri tabuľku 9) získame normálnu formu (DNF alebo CNF).

4. V prípade potreby prechádzame na dokonalé formy (SDNF alebo SKNF). Napríklad, ak chcete získať SKNF, často potrebujete použiť vlastnosť: .

Príklad 6 Konvertovať na booleovskú funkciu SKNF

Vykonaním krokov vyššie uvedeného algoritmu v poradí dostaneme:

Pomocou absorpčnej vlastnosti dostaneme:

Takto sme získali funkcie CNF f (x 1, x 2, x 3 ). Ak chcete získať jeho SKNF, musíte zopakovať každú disjunkciu, v ktorej chýba akákoľvek premenná, dvakrát s touto premennou a s jej negáciou:

2.2.6. Minimalizácia booleovských funkcií

Keďže rovnakú logickú funkciu možno reprezentovať pomocou h osobné vzorce, potom nájdenie najjednoduchšieho pho R mule, ktorá definuje boolovskú funkciu, zjednodušuje logický obvod, ktorý implementuje boolovskú funkciu do tsyu. Minimálny tvar l O logická funkciav nejakom základe môžeme uvažovať o takom základe, ktorý obsahuje minimálny počet superpozícií funk Komu základ, povolenie a zátvorky. Je však ťažké postaviť efektívne l algoritmus takejto minimalizácie so získaním minima v zátvorke fo r my.

Uvažujme o jednoduchšom minimalizačnom probléme pri syntéze kombinačných obvodov, v ktorom sa nehľadá minimálna hranatá forma funkcie, ale jej minimálna DNF. Pre túto úlohu existujú jednoduché účinné algoritmy.

Metóda Quine

Funkcia, ktorá sa má minimalizovať, je zastúpená v SDNF a aplikujú sa na ňu všetky možné operácie neúplného lepenia

, (2.10)

a potom absorpciu

, (2.11)

a táto dvojica krokov sa aplikuje opakovane. Takto je možné redukovať rad pojmov. Tento postup sa opakuje, kým nezostane žiadny výraz, ktorý by sa dal zlepiť s iným výrazom.

Všimnite si, že ľavú stranu rovnice (2.10) možno okamžite minimalizovať jednoduchším a zrejmejším spôsobom:

Táto metóda je zlá, pretože pri takejto priamej minimalizácii konjunktívne výrazy buď zmiznú, hoci stále existujú prípady ich použitia na lepenie a absorbovanie so zvyšnými pojmami.

Je potrebné poznamenať, že Quineova metóda je pomerne časovo náročná, takže pravdepodobnosť chýb pri transformáciách je pomerne vysoká. Ale jeho výhodou je, že teoreticky ho možno použiť pre ľubovoľný počet argumentov a so zvyšujúcim sa počtom premenných sa transformácie stávajú menej komplikovanými.

Metóda Carnotovej mapy

Carnotova metóda máp (tabuľiek) je vizuálnejší, časovo menej náročný a spoľahlivý spôsob minimalizácie logických funkcií, ale jej použitie je prakticky obmedzené na funkcie 3-4 premenných, maximálne 5-6 premenných.

Carnotova mapa toto je dvojrozmerná tabuľková forma reprezentujúca pravdivostnú tabuľku booleovskej funkcie, ktorá uľahčuje nájdenie minimálneho DNF logických funkcií v grafickej vizuálnej forme. Každá bunka tabuľky je spojená s mintermom SDNF minimalizovanej funkcie, navyše tak, že ľubovoľné osi symetrie tabuľky zodpovedajú zónam, ktoré sú v nejakej premennej vzájomne inverzné. Takéto usporiadanie buniek v tabuľke uľahčuje určenie priľnavých členov SDNF (ktoré sa líšia inverzným znakom len jednej premennej): v tabuľke sú usporiadané symetricky.

Pravdivé tabuľky a Karnaughove mapy pre funkcie AND a OR dvoch jazdných pruhov e Premenné sú znázornené na obr. 8. V každej bunke mapy je zapísaná hodnota. A hodnota funkcie na množine hodnôt argumentu zodpovedajúceho tejto bunke n tov.

A) A b) ALEBO

Ryža. 8. Príklad Karnaughových máp pre funkcie dvoch premenných

V Karnaughovej mape je len jedna 1 pre funkciu And, takže sa nedá ničím zlepiť. Vo výraze pre minimálnu funkciu bude iba výraz zodpovedajúci tejto 1:

f = x y.

V Karnaughovej mape sú už tri jednotky pre funkciu OR a možno vytvoriť dva lepiace páry, pričom 1 zodpovedá pojmu xy , je použitý dvakrát. Vo výraze pre minimálnu funkciu je potrebné napísať výrazy pre dvojice, ktoré sa majú zlepiť, pričom v nich ponecháte všetky premenné, ktoré sa pre túto dvojicu nemenia, a odstránite premenné, ktoré menia svoju hodnotu. Pre horizontálne lepenie dostaneme X a pre vertikálne r , ako výsledok dostaneme výraz

f = x + y.

Na obr. 9 zobrazuje pravdivostné tabuľky dvoch funkcií troch premenných ( A ) a ich Karnotove mapy ( b a c). Funkcia f 2 sa od prvého líši tým, že nie je definovaný na troch súboroch premenných (v tabuľke je to označené pomlčkou).

Pri určovaní minimálneho DNF funkcie sa používajú nasledujúce pravidlá. Všetky bunky obsahujúce 1 sú spojené do uzavretých obdĺžnikových oblastí tzv k-kocky , kde k = log 2 K , K číslo 1 v obdĺžnikovej oblasti. V tomto prípade by každá oblasť mala byť obdĺžnik s počtom buniek 2 k , kde k = 0, 1, 2, 3, …. Pre k = 1 obdĺžnik sa nazýva jedna je kocka a obsahuje 2 1 = 2 jednotky; pre k = 2 obdĺžnik obsahuje 2 2 = 4 jednotky a je tzv dvojkocka; pre k = 3 plocha z 2 3 = 8 jednotiek tzv trojkocka ; atď. Jednotky, ktoré sa nedajú spojiť do obdĺžnikov, možno volať nulové kocky , ktoré obsahujú iba jednu jednotku (2 0 = 1). Ako vidno, pre dokonca k oblasti môžu byť štvorcové (ale nie nevyhnutne), a ak sú nepárne k iba obdĺžniky.

b c

Ryža. 9. Príklad Karnaughových máp pre funkcie troch premenných

Tieto oblasti sa môžu prekrývať, t.j. rovnaké bunky môžu byť zahrnuté v rôznych oblastiach. Potom sa minimálna DNF funkcie zapíše ako disjunkcia všetkých zodpovedajúcich konjunktívnych členov k - kocky.

Každá z týchto oblastí na Karnaughovej mape je reprezentovaná v minimálnom DNF konjunkciou, počtom argumentov, v ktorých je k menší ako celkový počet argumentov funkcie m , teda toto číslo je m k . Každá konjunkcia minimálneho DNF je zložená len z tých argumentov, ktoré pre príslušnú oblasť mapy majú hodnoty buď bez inverzií, alebo len s inverziami, t.j. nemenia ich hodnotu.

Pri pokrytí buniek mapy uzavretými oblasťami by sme sa teda mali snažiť zabezpečiť, aby počet oblastí bol minimálny a každá oblasť obsahovala čo najviac buniek, pretože v tomto prípade bude počet výrazov v minimálnom DNF minimálny a počet argumentov v zodpovedajúcej konjunkcii bude minimálny.

Pre funkciu podľa Karnotovej mapy na obr. 9, b nájdeme

keďže pre hornú uzavretú oblasť premenné x 1 a x 2 majú hodnoty bez inverzií, pre nižšie x 1 záležitosti s inverziou, a x 3 bez inverzie.

Nedefinované hodnoty na mape na obr. 9, V možno predefinovať nahradením nulou alebo jednotkou. Pre túto funkciu je zrejmé, že je výhodnejšie obe neisté hodnoty nahradiť 1. V tomto prípade sa vytvoria dve oblasti, čo sú rôzne typy 2-kociek. Potom bude výraz pre minimálnu funkciu DNF takýto:

Pri konštrukcii uzavretých oblastí je dovolené zbaliť Karnotovu mapu do valca horizontálne aj vertikálne. R do zvislých osí so spojením protiľahlých plôch ka R vy, t.j. jednotky umiestnené pozdĺž okrajov Carnotovej mapy symetricky h ale dá sa aj kombinovať.

Karnotove mapy je možné kresliť rôznymi spôsobmi (obrázok 10).

x 2 x 3

a b

Ryža. 10. Rôzne spôsoby zobrazenia máp Carnot
pre funkciu 3 premenných

Najvhodnejšie verzie Karnaughových máp pre funkcie 2-4 premenných sú však znázornené na obr. 11 tabuliek, pretože zobrazujú pre každú bunku A všetky premenné sú v priamej alebo inverznej forme.

a b

Ryža. jedenásť. Najpohodlnejší obrázok Carnotových máp
pre funkcie 3 ( a) a 4 b) premenné

Pre funkcie 5 a 6 premenných sa použije metóda znázornená na obr. 10, V .

Ryža. 12. Obrázok Karnaughovej mapy pre funkciu 5 premenných

Ryža. 13. Obrázok Karnaughovej mapy pre funkciu 6 premenných

Ďalšie súvisiace diela, ktoré by vás mohli zaujímať.vshm>
9020. PRINCÍP DUALITY. ROZŠÍRENIE BOOLEANSKÝCH FUNKCIÍ V PREMENNÝCH. DOKONALÉ DISJUNKTÍVNE A KONJUNKTÍVNE NORMÁLNE FORMY 96,34 kB
Táto veta je konštruktívna, pretože nám umožňuje zostaviť pre každú funkciu vzorec, ktorý ju realizuje vo forme dokonalej d.s. f. Aby sme to urobili, v pravdivostnej tabuľke pre každú funkciu označíme všetky riadky, v ktorých
6490. Popis a minimalizácia logických funkcií 187,21 kB
Vo verbálnej forme je vyjadrený vzťah medzi argumentmi funkcie a jej hodnotami. Príklad: Funkcia s tromi argumentmi sa vyhodnotí, keď sa dva alebo viac argumentov funkcie zhodujú. Spočíva v zostrojení pravdivostnej tabuľky obsahujúcej hodnoty funkcie pre všetky množiny hodnôt argumentov. V tomto príklade podľa pravdivostnej tabuľky dostaneme takýto záznam vo forme DNF ...
6707. Navrhovanie relačných databáz. Konštrukčné problémy v klasickom prístupe. Princípy normalizácie, normálne formy 70,48 kB
Čo je návrh relačnej databázy Ide o súbor vzájomne súvisiacich vzťahov, v ktorých sú definované všetky atribúty, nastavené primárne kľúče vzťahu a niektoré ďalšie vlastnosti vzťahu, ktoré súvisia s princípmi zachovania integrity. Preto musí byť návrh databázy veľmi presný a overený. Databázový projekt je v skutočnosti základom budúceho softvérového balíka, ktorý bude dlho a mnohými používateľmi používať.
4849. Formy a spôsoby realizácie funkcií štátu 197,3 kB
Pojem „funkcia“ má v domácej a zahraničnej vedeckej literatúre odlišný význam. Vo filozofických a všeobecných sociologických termínoch sa považuje za „vonkajší prejav vlastností objektu v danom systéme vzťahov“; ako súbor bežných alebo špecifických činov jednotlivcov alebo orgánov
17873. Formovanie logického UUD u žiakov 3. ročníka 846,71 kB
Psychologické a pedagogické aspekty problému formovania logických univerzálnych akcií u mladších školákov Metódy hodnotenia formovania logických UUD. Vypracovanie koncepcie rozvoja univerzálnych vzdelávacích aktivít v systéme všeobecného vzdelávania spĺňa nové spoločenské požiadavky. Najdôležitejšou úlohou moderného vzdelávacieho systému je formovanie univerzálnych vzdelávacích aktivít UUD. Vytváranie univerzálnych vzdelávacích aktivít je kľúčom k prevencii školských ťažkostí.
2638. Technická implementácia logických spojení v automatických blokovacích systémoch 1,04 MB
Technická implementácia logických spojení v automatických blokovacích systémoch Technickú implementáciu trojmiestneho a štvormiestneho riadiaceho algoritmu AB je možné dosiahnuť pomocou reléového kontaktu a bezkontaktných diskrétnych a integrálnych logických prvkov...
10203. APLIKÁCIA KONCEPCIE RIZIKO ORIENTOVANÉHO PRÍSTUPU NA KONŠTRUKCIU ŠTRUKTURÁLNYCH A LOGICKÝCH MODELOV VZNIKU A VÝVOJA NÚDZOVÝCH STAV 70,8 kB
Všeobecná analýza rizík Výrobné prostredie je presýtené výkonnými technologickými systémami a technológiami, vďaka ktorým je ľudská práca produktívnejšia a menej fyzicky náročná, no o to nebezpečnejšia. Riziko je charakterizované neočakávanosťou a náhlosťou vzniku nebezpečnej situácie. Každý deň sa stretávame s mnohými rizikami, ale väčšina z nich zostáva potenciálna.Teória rizík poskytuje kvantitatívne hodnotenie negatívneho dopadu na človeka, ako aj poškodenia jeho zdravia a života.
11576. Pojem, typy a formy transakcií. Dôsledky nedodržania požadovanej formy transakcií 49,82 kB
Rozpoznanie transakcie ako neplatných typov neplatnej transakcie. Aplikovanou hodnotou práce v kurze je zjednodušenie konceptu transakcie, teda jej verejnej prezentácie v prístupnejšej forme.
6213. Aproximácia funkcií 3,08 MB
Prvý spočíva v nahradení niektorej analyticky alebo tabuľkovo danej funkcie inou funkciou blízkou pôvodnej, ale jednoduchšou a pohodlnejšou na výpočty. Napríklad nahradenie funkcie polynómom umožňuje získať jednoduché vzorce pre numerickú integráciu a diferenciáciu; nahradenie tabuľky aproximačnou funkciou umožňuje získať hodnoty v jej medziľahlých bodoch. Vzniká aj druhý problém obnovenia funkcie na určitom segmente z hodnôt funkcie danej na tomto segmente v diskrétnej množine bodov. Odpoveď na takúto otázku...
14058. Vývoj funkcií štátu 29,99 kB
Ruský štát ako právny fenomén musí v prvom rade zabezpečiť realizáciu účelu štátu, ako aj jeho základných ústavných charakteristík ako demokratického federálneho právneho sociálneho sekulárneho štátu s republikánskou formou vlády. Hlavný účel štátu určuje čl.

Pre akýkoľvek logický vzorec je možné pomocou rovnakých transformácií zostrojiť nekonečné množstvo jemu ekvivalentných vzorcov. V algebre logiky je jednou z hlavných úloh hľadanie kanonických foriem (t. j. vzorcov zostavených podľa jediného pravidla, kánonu).

Ak je logická funkcia vyjadrená prostredníctvom disjunkcie, konjunkcie a negácie premenných, potom sa táto forma zobrazenia nazýva normálna.

Medzi normálnymi formami vynikajú dokonalé normálne formy (tie formy, v ktorých sú funkcie zapísané jedinečným spôsobom).

Dokonalá disjunktívna normálna forma (PDNF)

Definícia. Vzorec sa nazýva elementárna konjunkcia, ak je tvorená konjunkciou určitého počtu premenných alebo ich negácií.

Príklady: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

Definícia. Vzorec sa nazýva disjunktívna normálna forma (DNF), ak ide o disjunkciu neopakujúcich sa elementárnych spojok.

DNF sa zapisuje v nasledujúcom tvare: F 1 ∨ F 2 ∨ ... ∨ F n , kde F i je elementárna spojka

Príklady: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3, ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Definícia. Logický vzorec v k premenných sa nazýva dokonalá disjunktívna normálna forma (PDNF), ak:
1) vzorec je DNF, v ktorom každá elementárna konjunkcia je konjunkciou k premenných x 1 , x 2 , ..., x k a i-té miesto tejto konjunkcie je buď premenná x i alebo jej negácia;
2) všetky elementárne konjunkcie v takejto DNF sú párovo odlišné.

Príklad: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)

Dokonalá konjunktívna normálna forma (SKNF)

Definícia. Vzorec sa nazýva elementárna disjunkcia, ak vzniká disjunkciou určitého počtu premenných alebo ich negáciami.

Príklady: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

Definícia. Vzorec sa nazýva konjunktívna normálna forma (CNF), ak ide o konjunkciu neopakujúcich sa elementárnych disjunkcií.

CNF sa zapisuje v nasledujúcom tvare: F 1 ∧ F 2 ∧ ... ∧ F n , kde F i je elementárna disjunkcia

Príklady: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

Definícia. Logický vzorec v k premenných sa nazýva dokonalá konjunktívna normálna forma (KDNF), ak:
1) vzorec je CNF, v ktorom každá elementárna disjunkcia je disjunkciou k premenných x 1 , x 2 , ..., x k , a i-té miesto tejto disjunkcie je buď premenná x i alebo jej negácia;
2) všetky elementárne disjunkcie v takejto CNF sú párovo odlišné.

Príklad: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)

Všimni si akákoľvek logická funkcia, ktorá nie je identicky rovná 0 alebo 1, môže byť reprezentovaná ako SDNF alebo SKNF.

Algoritmus na konštrukciu SDNF podľa pravdivostnej tabuľky

  1. Vyberte všetky riadky tabuľky, v ktorých sa hodnota funkcie rovná jednej.
  2. Pre každý takýto riadok napíšte konjunkciu všetkých premenných nasledovne: ak sa hodnota niektorej premennej v tejto množine rovná 1, potom do konjunkcie zahrnieme samotnú premennú, v opačnom prípade jej negáciu.
  3. Všetky výsledné spojky spájame disjunkčnými operáciami.

Algoritmus na konštrukciu SKNF podľa pravdivostnej tabuľky

  1. Vyberte všetky riadky tabuľky, v ktorých sa hodnota funkcie rovná nule.
  2. Pre každý takýto riadok napíšte disjunkciu všetkých premenných nasledovne: ak je hodnota niektorej premennej v tejto množine 0, potom do spojky zahrnieme samotnú premennú, v opačnom prípade jej negáciu.
  3. Všetky získané disjunkcie spojíme konjunkčnými operáciami.

Analýza algoritmov ukazuje, že ak je hodnota funkcie rovná 0 na väčšine riadkov pravdivostnej tabuľky, potom na získanie jej logického vzorca je lepšie zostrojiť SDNF, inak - SKNF.

Príklad: Daná pravdivostná tabuľka logickej funkcie troch premenných. Zostavte logický vzorec, ktorý implementuje túto funkciu.

XrzF(x, y, z)
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1

Pretože na väčšine riadkov pravdivostnej tabuľky je hodnota funkcie rovná 1, potom zostrojíme SKNF. V dôsledku toho dostaneme nasledujúci logický vzorec:
F = (¬x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z)

Skontrolujeme výsledný vzorec. Aby sme to dosiahli, zostrojíme pravdivostnú tabuľku funkcie.

XrzX¬ x ∨ y ∨ z¬z¬ x ∨ y ∨ ¬ zF(x, y, z)
0 0 0 1 1 1 1 1
0 0 1 1 1 0 1 1
0 1 0 1 1 1 1 1
0 1 1 1 1 0 1 1
1 0 0 0 0 1 1 0
1 0 1 0 1 0 0 0
1 1 0 0 1 1 1 1
1 1 1 0 1 0 1 1

Pri porovnaní pôvodnej pravdivostnej tabuľky a tabuľky vytvorenej pre logický vzorec si všimneme, že stĺpce hodnôt funkcií sú rovnaké. To znamená, že logická funkcia je zostavená správne.