Logická funkcia sa nazýva konjunktívna normálna forma. Konjunktívne formy reprezentácie logických funkcií

Normálne formy logických funkcií Reprezentácia booleovskej funkcie vo forme disjunkcie konjunktívnych členov zložiek jednotky Ki 2,7 sa nazýva disjunktívna normálna forma DNF tejto funkcie. obsahujú práve jednu zo všetkých logických premenných braných s negáciami alebo bez nich, potom sa táto forma zobrazenia funkcie nazýva dokonalá disjunktívna normálna forma SDNF tejto funkcie. Ako vidíte, pri zostavovaní funkcie SDNF musíte vytvoriť disjunkciu všetkých mintermov, pre ktoré má funkcia hodnotu 1.

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 logický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ú práve jednu zo všetkých logických premenných, braných s negáciami alebo bez nich, potom sa táto forma reprezentácie funkcie nazývadokonalá disjunktívna normálna forma(SDNF ) túto funkciu. Volá sa SDNF 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álny tvar” znamená jednoznačný spôsob zápisu vzorca, ktorý implementuje danú funkciu.

Berúc do úvahy vyššie uvedené, z vety 2.1 vyplýva nasledujúca veta.

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

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

Tabuľka 10

Na základe vzorca (2.6) dostaneme:

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

Znázornenie booleovskej funkcie vo forme spojenia disjunktívnych členov (nulový prvok) D i

, (2.8)

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

Ak sú všetky disjunktívne výrazy CNF maxterms , teda obsahujú práve jednu zo všetkých logických premenných 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 je totožná s 1) možno predložiť SKNF, a takéto zastúpenie je jediné.

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é takto:

. (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 v CNF (okrem identickej). ). V závislosti od situácie môže byť reprezentácia funkcie v tej či onej forme kratšia.

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 má intuitívne túžbu otvoriť zátvorky a tým prejsť k DNF).

Príklad 4. Pre funkciu f (x 1 , x 2 , x 3 ), ktoré uvádza tabuľka. 10, napíšte to na SKNF.

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

Treba poznamenať, že nie je možné priamo prejsť z SDNF funkcie na jej SCNF alebo naopak. Pri pokusoch o takéto transformácie sú výsledkom funkcie, ktoré sú opakom požadovaných. Výrazy pre funkcie SDNF a SCNF možno priamo získať iba z ich pravdivostnej tabuľky.

Príklad 5. Pre funkciu f (x 1 , x 2 , x 3 ), ktoré uvádza tabuľka. 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 sme získali SCNF logickej funkcie, ktorá je inverznou funkciou získanou v príklade 2.4:

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

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

2. Pomocou vlastností negácie a De Morganových zákonov (pozri tabuľku 9) zabezpečíme, aby sa operácie negácie vzťahovali iba 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 prejdite na dokonalé formy (SDNF alebo SKNF). Napríklad na získanie SCNF často potrebujete použiť vlastnosť: .

Príklad 6. Preveďte logickú funkciu na SKNF

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

Pomocou absorpčnej vlastnosti dostaneme:

Takto sme získali funkciu CNF f (x 1, x 2, x 3 ). Ak chcete získať jeho SCNF, 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 logických funkcií

Keďže rovnaká logická funkcia môže byť reprezentovaná ako h osobné vzorce, potom nájdenie najjednoduchšej formy R mule definujúca boolovskú funkciu, zjednodušuje logický obvod, ktorý implementuje booleovskú funkciu na tion. Minimálna forma l O logická funkciav nejakom základe môžeme považovať taký, ktorý obsahuje minimálny počet superpozícií zábavy Komu s prihliadnutím na zátvorky. Je však ťažké vybudovať efektívny l algoritmus pre takúto minimalizáciu na získanie minimálnej zátvorky r my.

Uvažujme jednoduchší minimalizačný problém v syntéze kombinačných obvodov, v ktorom nehľadáme minimálnu zátvorkovú formu funkcie, ale jej minimálnu DNF. Na túto úlohu existujú jednoduché a efektívne algoritmy.

Quineova metóda

Funkcia, ktorá sa má minimalizovať, je znázornená v SDNF a aplikujú sa na ňu všetky možné neúplné operácie 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, až kým nezostane jediný výraz, ktorý by sa dal spojiť 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 spojovacie pojmy buď zmiznú, aj keď stále existujú možné prípady ich použitia na lepenie a absorpciu so zvyšnými pojmami.

Je potrebné poznamenať, že Quineova metóda je pomerne náročná na prácu, takže pravdepodobnosť chýb počas transformácií je pomerne vysoká. Jeho výhodou však 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 Karnaughovej mapy

Metóda Carnotových máp (tabuľiek) je vizuálnejší, menej prácny 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á vám umožňuje ľahko nájsť minimálne DNF logických funkcií v grafickej vizuálnej forme. Každá bunka tabuľky je spojená s minimálnou hodnotou SDNF funkcie, ktorá je minimalizovaná, a to takým spôsobom, že všetky osi symetrie tabuľky zodpovedajú zónam, ktoré sú vzájomne inverzné vzhľadom na nejakú premennú. Toto usporiadanie buniek v tabuľke uľahčuje určenie adhéznych podmienok SDNF (líši sa v inverznom znamienku iba jednej premennej): sú umiestnené symetricky v tabuľke.

Pravdivé tabuľky a Carnaughove mapy pre funkcie AND a OR dvoch jazdných pruhov e Premenné sú uvedené na obr. 8. V každej bunke karty je zapísaná hodnota A Hodnota funkcie na množine hodnôt argumentov zodpovedajúcich tejto bunke N súdruh

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á k ničomu prilepiť. Výraz pre minimálnu funkciu bude obsahovať iba výraz zodpovedajúci tejto 1:

f = x y.

V Carnotovej mape pre funkciu OR sú už tri 1 a môžete vytvoriť dva lepiace sa páry, pričom 1 zodpovedá výrazu xy , je použitý dvakrát. Vo výraze pre minimálnu funkciu musíte zapísať výrazy pre páry, ktoré sa spájajú, ponechať v nich všetky premenné, ktoré sa pre tento pár nemenia, a odstrániť 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 Carnotove 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álnej funkcie DNF 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 množstvo 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 oblasť 2 3 = 8 jednotiek sa nazýva 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 mať štvorcový tvar (ale nie nevyhnutne), a ak sú nepárne k iba obdĺžniky.

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

Tieto oblasti sa môžu prekrývať, to znamená, že rovnaké bunky môžu vstúpiť do rôznych oblastí. Potom sa minimálna funkcia DNF zapíše ako disjunkcia všetkých zodpovedajúcich konjunktívnych členov k - kocky.

Každá z uvedených 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 sa rovná mk . 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 význam.

Pri pokrývaní 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 Karnaughovej 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 v mape na obr. 9, V môže byť ďalej definované nahradením nulou alebo jednotkou. Pre túto funkciu je zrejmé, že je výhodnejšie obe nedefinované hodnoty nahradiť 1. V tomto prípade sa vytvoria dve oblasti, ktoré sú rôznymi typmi 2-kociek. Potom bude výraz pre minimálnu funkciu DNF takýto:

Pri konštrukcii uzavretých priestorov je dovolené zložiť Carnotovu mapu do valca horizontálne aj vertikálne. R tikal osi so spojením protiľahlých plôch R vy, t. j. jednotky umiestnené pozdĺž okrajov mapy Carnotovej symetrie h ale dá sa aj kombinovať.

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

a b

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

Ale najpohodlnejšie možnosti pre Karnaughove mapy pre funkcie 2-4 premenných sú tie, ktoré sú znázornené na obr. 11 tabuliek, pretože zobrazujú pre každú bunku A Všetky premenné máme v priamej alebo inverznej forme.

a b

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

Pre funkcie 5 a 6 premenných platí 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

Štandardný základ. Elementárne vzorce sú doslovné. Elementárna konjunkcia (disjunkcia). Disjunktívna (konjunktívna) normálna forma a dokonalá forma. Veta: akákoľvek booleovská funkcia odlišná od 0 (od 1) môže byť reprezentovaná vo forme SDNF (SCNF). Úplnosť štandardného základu. Príklady úplných základov: základ Zhegalkin, zdvih Schaeffer, šípka Peirce.

Štandardný základ je súbor troch základných operácií Booleovej algebry: sčítanie (zjednotenie), násobenie (priesečník) a negácia.

Tu zavoláme doslovne premenná x alebo jej negácia x a označujú xˆ. Booleovský prienik niekoľkých literálov definovaných rôznymi premennými, t.j. vyjadrenie tvaru X = xˆ 1 xˆ 2 . . . xˆ l, tzv elementárna konjunkcia . Požiadavka, aby všetky premenné boli odlišné, je určená nasledujúcim. Ak spojka obsahuje niekoľko identických literálov, potom je v dôsledku komutativity, asociatívnosti a idempotencie spojky možné po prechode na ekvivalentný vzorec ponechať iba jeden literál (napríklad x 1 x 1 = x 1). Ak spojka obsahuje premennú a jej negáciu, potom je vzorec ekvivalentný konštante 0, pretože x x = 0 a pre akýkoľvek vzorec Y máme Y x x = 0.

Disjunkcia viacerých elementárnych konjunkcií je tzv disjunktívna normálna forma , alebo DNF . Napríklad,

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5 .

Ak je zloženie premenných v každej elementárnej konjunkcii daného DNF rovnaké, potom sa volá DNF perfektné . Uvedený príklad je DNF, ktorý nie je dokonalý. Naopak, vzorec

x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4

existuje dokonalá forma.

Keďže v Booleovej algebre sú sčítanie a násobenie symetrické operácie a sčítanie môžete vždy interpretovať ako násobenie a násobenie ako sčítanie, existuje dvojitý koncept - konjunktívna normálna forma (KNF ), čo je konjunkcia elementárnych disjunkcií, a dokonalý konjunktívny tvar (SKNF ). Z princípu duality pre symetrické polomery vyplýva, že na akékoľvek tvrdenie ohľadom DNF odpovedá duálne tvrdenie týkajúce sa CNF, ktoré sa získa nahradením sčítania (disjunkcie) násobením, násobenia (konjunkcie) sčítaním, konštanty 0 konštantou 1, konštanty 1 s konštantou 0, vzťah poradia s duálom (inverzným) v poradí. Preto sa ďalej zameriame len na štúdium DNF.

Veta 1.4. Akákoľvek booleovská funkcia iná ako konštanta 0 môže byť reprezentovaná ako SDNF.

◀Dohodnime sa, že výrazom x σ rozumieme vzorec x, ak σ = 1, a vzorec x, ak σ = 0. Nech funkcia f(y 1 , . . . , y n) nadobudne na vektore hodnotu 1 (t 1, ..., t n) (takýto vektor sa nazýva zakladajúca jednotka ). Potom elementárna konjunkcia tiež nadobudne hodnotu 1 na tejto množine, ale zmizne na všetkých ostatných n-rozmerných booleovských vektoroch. Zvážte vzorec

v ktorom sa súčet (zjednotenie) rozširuje na všetky tie množiny (t 1, . . . , t n) hodnôt argumentov, na ktorých má daná funkcia hodnotu 1. Všimnite si, že množina takýchto množín nie je prázdna, takže súčet obsahuje aspoň jeden výraz.

Je ľahké vidieť, že vzorec Φ sa stáva 1 pre tie a len pre tie hodnoty premenných, pre ktoré sa príslušná funkcia stáva 1. To znamená, že vzorec Ψ predstavuje funkciu f.

Dôsledok 1.1.Štandardný základ je hotový.

◀ V skutočnosti, ak funkcia nie je konštantná 0, potom môže byť reprezentovaná buď vo forme SDNF, čo je vzorec nad štandardným základom. Konštanta 0 môže byť vyjadrená napríklad vzorcom f(x 1, x 2,..., x n) = x 1 x 1.

Príklad 1.2. Uvažujme funkciu troch premenných m(x 1, x 2, x 3) (tabuľka 1.4), tzv. väčšinová funkcia ̆. Táto funkcia sa vyhodnotí ako 1, ak viac ako polovica jej argumentov má hodnotu 1. Preto sa často nazýva hlasovacia funkcia. Postavme na to SDNF.

Úplnosť štandardného základu umožňuje výber ďalších ucelených systémov funkcií. Úplnosť množiny F možno určiť z nasledujúcich úvah. Predpokladajme, že každá z troch štandardných busisových funkcií je reprezentovateľná vzorcom cez F . Potom podľa vety 1.3 bude identita F úplná.

Príklad 1.3. Volá sa množina operácií modulo 2 sčítanie, násobenie a konštanta 1 Zhegalkinov základ . Sčítanie modulo 2 a násobenie sú základné operácie kruhu Z2, výrazy zložené s ich pomocou sú polynómy nad kruhom Z2. Konštanta 1 je v tomto prípade potrebná na zapísanie voľného termínu. Keďže xx = x, potom všetky faktory v polynóme majú stupeň 1. Preto sa pri písaní polynómu zaobídete bez pojmu stupeň. Príklady vzorcov na báze Zhegalkin:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Každý takýto vzorec sa nazýva Zhegalkinov polynóm. V skutočnosti je Zhegalkinov polynóm polynóm nad kruhom Z2.

Nie je ťažké zostaviť vzorce na základe Zhegalkin, ktoré predstavujú operácie sčítania a negácie štandardného základu (násobenie dvoch základov je bežné):

x+y=x⊕y⊕xy, x =x⊕1.

Preto je základom Zhegalkin kompletný súbor.
Dá sa ukázať, že pre akúkoľvek booleovskú funkciu je Zhegalkinov polynóm jednoznačne definovaný

(presnejšie do poradia pojmov). Koeficienty Zhegalkinovho polynómu s malým počtom premenných možno nájsť pomocou metódy neurčitých koeficientov.

Príklad 1.4. Zoberme si množinu jedinej funkcie – Schaefferov zdvih*. Táto sada je kompletná, ako vyplýva z nasledujúcich ľahko overiteľných identít:

x =x|x, xy=x|y =(x|y)|(x|y), x+y=x |y =(x|x)|(y|y).

Príklad 1.5. Základ pozostávajúci z jedinej funkcie, Peirceovho šípu, je tiež hotový. Test na to je podobný ako v prípade Schaefferovej mŕtvice. Tento záver však možno urobiť aj na základe princípu duality pre symetrické semiringy.

*Schaefferova mŕtvica je binárna, ale nie asociatívna operácia. Preto by ste pri používaní formulára infix mali byť opatrní: výsledok závisí od poradia operácií. V tomto prípade sa odporúča explicitne uviesť poradie operácií pomocou zátvoriek, napríklad napísať (x | y) | z, nie x | y | z, hoci obe formy sú ekvivalentné.

Definícia 1.Spojkový jednočlen (elementárna spojka) premenných je spojenie týchto premenných alebo ich negácií.

Napríklad, je elementárna konjunkcia.

Definícia 2.Disjunktívny monomiál (elementárna disjunkcia) od premenných je disjunkcia týchto premenných alebo ich negácie.

Napríklad, je elementárna disjunkcia.

Definícia 3. Vzorec, ktorý je ekvivalentný danému vzorcu výrokovej algebry a je disjunkciou elementárnych konjunktívnych monočlenov, sa nazýva disjunktívna normálna forma(DNF) tohto vzorca.

Napríklad,– DNF.

Definícia 4. Vzorec, ktorý je ekvivalentný danému vzorcu výrokovej algebry a je konjunkciou elementárnych disjunktívnych monočlenov, sa nazýva konjunktívna normálna forma(CNF) tohto vzorca.

Napríklad, – KNF.

Pre každý vzorec výrokovej algebry možno nájsť množinu disjunktívnych a konjunktívnych normálnych foriem.

Algoritmus na vytváranie normálnych foriem

Pomocou ekvivalencií logickej algebry nahraďte všetky základné operácie vo vzorci: konjunkcia, disjunkcia, negácia:

Zbavte sa dvojitých negatívov.

Ak je to potrebné, aplikujte vlastnosti distribučných a absorpčných vzorcov na operácie konjunkcie a disjunkcie.

2.6. Dokonalé disjunktívne a dokonalé konjunktívne normálne formy

Akákoľvek booleovská funkcia môže mať mnoho reprezentácií vo forme DNF a CNF. Zvláštne miesto medzi týmito reprezentáciami zaujíma dokonalá DNF (SDNF) a dokonalá CNF (SCNF).

Definícia 1. Dokonalá disjunktívna normálna forma(SDNF) je DNF, v ktorom každý konjunktívny monomiál obsahuje každú premennú z množiny práve raz, buď samú seba, alebo jej negáciu.

Štrukturálne môže byť SDNF pre každý vzorec výrokovej algebry redukovaný na DNF definovaný takto:

Definícia 2. Dokonalá disjunktívna normálna forma(SDNF) vzorca výrokovej algebry sa nazýva jeho DNF, ktorý má tieto vlastnosti:

Definícia 3. Dokonalá konjunktívna normálna forma(SCNF) je CNF, v ktorom každý disjunktívny monomiál obsahuje každú premennú z množiny práve raz a objavuje sa buď sama, alebo jej negácia.

Štrukturálne môže byť SCNF pre každý vzorec výrokovej algebry redukovaný na CNF definovaný nasledovne.

Definícia 4. Dokonalá konjunktívna normálna forma(SCNF) daného vzorca výrokovej algebry sa nazýva CNF, ktorý spĺňa nasledujúce vlastnosti.

Veta 1. Každá booleovská funkcia premenných, ktorá nie je identicky nepravdivá, môže byť reprezentovaná v SDNF, a to jedinečným spôsobom.

Metódy na nájdenie SDNF

1. spôsob

2. spôsob

vyberte riadky, kde vzorec nadobúda hodnotu 1;

disjunkciu spojok skladáme pod podmienkou, že ak je premenná zahrnutá do spojky s hodnotou 1, tak túto premennú zapíšeme, ak s hodnotou 0, tak jej negáciu. Dostávame SDNF.

Veta 2. Každá booleovská funkcia premenných, ktorá nie je identicky pravdivá, môže byť reprezentovaná v SCNF, a to jedinečným spôsobom.

Metódy na nájdenie SCNF

1. spôsob– pomocou ekvivalentných transformácií:

2. spôsob- pomocou pravdivostných tabuliek:

vyberte riadky, kde má vzorec hodnotu 0;

konjunkciu disjunkcií skladáme za podmienky, že ak je v disjunkcii zahrnutá premenná s hodnotou 0, tak túto premennú zapíšeme, ak s hodnotou 1, tak jej negáciu. Dostávame SKNF.

Príklad 1 Zostrojte funkcie CNF.

Riešenie

Vylúčme spojku "" pomocou zákonov transformácie premenných:

= /de Morganove zákony a dvojitá negácia/ =

/distribučné zákony/ =

Príklad 2 Dajte vzorec DNF.

Riešenie

Vyjadrime logické operácie pomocou a:

= /zaraďme negáciu medzi premenné a redukujme dvojité zápory/ =

= /zákon distributivity/ .

Príklad 3 Napíšte vzorec v DNF a SDNF.

Riešenie

Pomocou zákonov logiky zredukujeme tento vzorec na formu obsahujúcu iba disjunkcie elementárnych spojok. Výsledný vzorec bude požadovaný DNF:

Aby sme vytvorili SDNF, vytvorte pravdivostnú tabuľku pre tento vzorec:

Označíme tie riadky tabuľky, v ktorých má vzorec (posledný stĺpec) hodnotu 1. Pre každý takýto riadok vypíšeme vzorec, ktorý je pravdivý na množine premenných tohto riadku:

riadok 1: ;

riadok 3: ;

riadok 5: .

Disjunkcia týchto troch vzorcov nadobudne hodnotu 1 iba na množinách premenných v riadkoch 1, 3, 5, a preto bude požadovanou dokonalou disjunktívnou normálnou formou (PDNF):

Príklad 4. Prineste vzorec do SKNF dvoma spôsobmi:

a) použitím ekvivalentných transformácií;

b) pomocou pravdivostnej tabuľky.

Riešenie:

Transformujme druhú elementárnu disjunkciu:

Vzorec vyzerá takto:

b) zostavte pravdivostnú tabuľku pre tento vzorec:

Označíme tie riadky tabuľky, v ktorých má vzorec (posledný stĺpec) hodnotu 0. Pre každý takýto riadok vypíšeme vzorec, ktorý je pravdivý na množine premenných tohto riadku:

riadok 2: ;

riadok 6: .

Konjunkcia týchto dvoch vzorcov nadobudne hodnotu 0 iba na množinách premenných v riadkoch 2 a 6, a preto bude požadovanou dokonalou konjunktívnou normálnou formou (PCNF):

Otázky a úlohy na samostatné riešenie

1. Pomocou ekvivalentných transformácií zredukujte vzorce na DNF:

2. Pomocou ekvivalentných transformácií priveďte vzorce do CNF:

3. Pomocou druhého distribučného zákona preveďte DNF na CNF:

A) ;

4. Preveďte dané DNF na SDNF:

5. Preveďte daný CNF na SCNF:

6. Pre dané logické vzorce zostrojte SDNF a SCNF dvoma spôsobmi: pomocou ekvivalentných transformácií a pomocou pravdivostnej tabuľky.

b) ;

Disjunktívne a konjunktívne normálne formy výrokovej algebry. Pre každú výrokovú logickú funkciu možno zostaviť pravdivostnú tabuľku. Inverzný problém je tiež vždy riešiteľný. Uveďme niekoľko definícií.

Elementárne konjunkcie (spojky) sa nazývajú konjunkcie premenných alebo ich negácie, v ktorých sa každá premenná vyskytuje najviac

raz.

Disjunktívna normálna forma(DNF) je vzorec, ktorý má formu disjunkcie elementárnych spojok.

Elementárne disjunkcie (disjunkcie) sa nazývajú disjunkcie premenných s negáciami alebo bez nich.

Konjunktívna normálna forma(CNF) je vzorec, ktorý má formu konjunkcie elementárnych disjunkcií.

Pre každú funkciu výrokovej algebry možno nájsť množinu disjunktívnych a konjunktívnych normálnych foriem.

Algoritmus na zostavenie DNF:

1. Prejdite na Booleovské operácie pomocou ekvivalentných transformačných vzorcov.

2. Prejdite na vzorce s tesnými negáciami, teda na vzorec, v ktorom sa negácie nenachádzajú vyššie ako nad premennými – aplikujte De Morganove zákony.

3. Otvorte zátvorky - aplikujte zákony distributivity.

4. Vezmite si opakujúce sa pojmy jedenkrát za sebou – zákon idempotencie.

5. Aplikujte zákony absorpcie a polovičnej absorpcie.

Príklad 6. Nájdite vzorce DNF: .

V Booleovej algebre je to pravda princíp duality. Je to nasledovné.

Funkcia sa volá dvojaký do funkcie ak . Tie. Na nájdenie duálnej funkcie k danej je potrebné zostrojiť negáciu funkcie z negácií argumentov.

Príklad 7. Nájdite funkciu dual to .

Medzi elementárnymi funkciami algebry logiky je 1 duálna k 0 a naopak, x je duálna na x, duálna na , duálna a naopak.

Ak vo vzorci F 1 reprezentujúcom funkciu nahradíme všetky spojky

na disjunkcii, disjunkcii na konjunkcii, 1 na 0, 0 na 1, potom dostaneme vzorec F * reprezentujúci funkciu * duál na .

Konjunktívna normálna forma (CNF) je duálny koncept pre DNF, takže sa dá ľahko skonštruovať podľa nasledujúcej schémy:

Príklad 8. Nájdite vzorec CNF: .

Použitím výsledku z príkladu 6 máme

Dokonalé disjunktívne a dokonalé konjunktívne normálne formy. V každom z typov normálnych foriem (disjunktívne a konjunktívne) možno rozlíšiť triedu dokonalých foriem SDNF a SCNF.

Dokonalá elementárna konjunkcia je logickým súčinom všetkých premenných s negáciou alebo bez negácie a každá premenná sa v súčine vyskytuje iba raz.

Akékoľvek DNF možno redukovať na SDNF rozdelením konjunkcií, ktoré neobsahujú všetky premenné, t.j. sčítaním za chýbajúcu premennú sa x i vynásobí pomocou distributívneho zákona

Príklad 9. Nájdite SDNF pre DNF z príkladu 6

Dokonalá elementárna disjunkcia je logický súčet všetkých premenných s negáciami alebo bez nich a každá premenná je zahrnutá do súčtu iba raz.

Akýkoľvek CNF môže byť redukovaný na SCNF pridaním spojenia, ktoré neobsahuje žiadnu premennú Xi spojením a použitím distributívneho zákona

Príklad 10. Prineste KNF do SKNF:

Na zostavenie SCNF môžete použiť diagram

Príklad 11. Nájdite SCNF pre vzorec z príkladu 6.

Každá funkcia má SDNF a navyše jedinečný. Každá funkcia má SCNF a navyše jedinečný.

Pretože SDNF a SKNF sú jednoznačne definované vzorcami; možno ich zostaviť pomocou pravdivostnej tabuľky vzorca.

Na zostavenie SDNF je potrebné vybrať riadky, v ktorých má F hodnotu 1 a zapísať pre ne dokonalé elementárne spojky. Ak je hodnota premennej v požadovanom riadku pravdivostnej tabuľky rovná jednej, potom sa v dokonalej konjunkcii berie bez negácie, ak je nula, tak s negáciou. Potom dokonalé spojky (ich počet sa rovná počtu jednotiek v tabuľke) sú spojené znamienkami disjunkcie.

Na zostavenie SCNF pomocou pravdivostnej tabuľky je potrebné vybrať v nej riadky, kde F = 0, zapísať dokonalé elementárne disjunkcie a potom ich spojiť znamienkami konjunkcie. Ak v požadovanom riadku pravdivostnej tabuľky (F=0) hodnota premennej zodpovedá nule, tak v dokonalej vete sa berie bez negácie, ak je jedna, tak s negáciou.

Príklad 12. Nájdite SDNF a SCNF pomocou pravdivostnej tabuľky pre vzorec z príkladu 6.

Tabuľka 14 uvádza len konečnú hodnotu F=10101101. Platnosť tohto tvrdenia by ste si mali overiť sami zostavením podrobnej pravdivostnej tabuľky.

Tabuľka 14

Pre akýkoľvek logický vzorec je možné pomocou transformácií identity zostrojiť nekonečne veľa vzorcov, ktoré mu zodpovedajú. 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 sa rozlišujú 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 píše 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 je každá elementárna konjunkcia konjunkciou k premenných x 1, x 2, ..., x k a na i-tom mieste 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 (PCNF)

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 (CPNF), ak:
1) vzorec je CNF, v ktorom každá elementárna disjunkcia je disjunkciou k premenných x 1, x 2, ..., x k a na i-tom mieste 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 pomocou 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é konjunkcie spájame s disjunkčnými operáciami.

Algoritmus na konštrukciu SCNF pomocou pravdivostnej tabuľky

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

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

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

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

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

Pri porovnaní pôvodnej pravdivostnej tabuľky a tabuľky skonštruovanej pre logický vzorec si všimneme, že stĺpce funkčných hodnôt sa zhodujú. To znamená, že logická funkcia je skonštruovaná správne.