Egyszerű kötőszó hívott kötőszó egy vagy számos változók, at ez minden változó találkozik Nem több egy alkalommal (vagy önmaga, vagy neki tagadás).

Például egy egyszerű kötőszó,

Szétválasztó normál alak(DNF) hívott diszjunkció egyszerű kötőszavak.

Például a kifejezés DNF.

Tökéletes szétválasztó normál alak(SDNF) hívott mint ez szétválasztó normál forma, at melyik V minden kötőszó tartalmazza Minden változók adott lista (vagy maguk, vagy az övék tagadás), és V egy És kötet azonosRendben.

Például a kifejezés DNF, de nem SDNF. Kifejezés az SDNF.

Hasonló meghatározások (a konjunkció diszjunkcióval való helyettesítésével és fordítva) igazak a CNF-re és az SKNF-re. Adjuk meg a pontos megfogalmazást.

Egyszerű diszjunkció hívott diszjunkció egy vagy számos változók, at ez minden változó tartalmazza Nem több egy alkalommal (vagy önmaga, vagy neki tagadás).Például a kifejezés egy egyszerű diszjunkció,

Kötőszó normál alak(KNF) hívott kötőszó egyszerű diszjunkciók(például a kifejezés CNF).

A tökéletes konjunktív normálforma (PCNF) olyan CNF, amelyben minden egyszerű diszjunkció egy adott lista összes változóját tartalmazza (akár magukat, akár a tagadásaikat), és ugyanabban a sorrendben.

Például a kifejezés az SKNF.

Mutassunk be algoritmusokat az egyik formából a másikba való átmenethez. Természetesen meghatározott esetekben (bizonyos kreatív megközelítéssel) az algoritmusok használata munkaigényesebb lehet, mint az adott forma meghatározott típusát használó egyszerű átalakítások:

a) átmenet DNF-ről CNF-re

Ennek az átmenetnek az algoritmusa a következő: két negációt teszünk a DNF fölé, és De Morgan szabályait használva (a felső tagadás érintése nélkül) a DNF tagadását visszacsökkentjük DNF-re. Ebben az esetben meg kell nyitnia a zárójeleket az abszorpciós szabály (vagy Blake-szabály) segítségével. A kapott DNF negációja (felsõ) (ismét de Morgan szabálya szerint) azonnal megadja a CNF-et:

Vegyük észre, hogy a CNF-t az eredeti kifejezésből is megkaphatjuk, ha kivesszük at zárójelen túl;

b) átmenet CNF-ről DNF-re

Ezt az átmenetet a zárójelek egyszerű kinyitásával hajtják végre (ismét az abszorpciós szabályt használjuk)

Így megkaptuk a DNF-et.

A fordított átmenet (SDNF-ről DNF-re) a DNF minimalizálásának problémájához kapcsolódik. Erről a részben lesz szó részletesebben. 5, itt megmutatjuk, hogyan lehet egyszerűsíteni a DNF-et (vagy SDNF-t) Blake szabálya szerint. Ezt a típusú DNF-et ún rövidítve DNF;

c) a DNF (vagy SDNF) rövidítése szabály Blake

Ennek a szabálynak az alkalmazása két részből áll:

Ha a DNF-ben a diszjunkt kifejezések között vannak kifejezések , akkor a teljes diszjunkcióhoz hozzáadjuk a kifejezést TO 1 TO 2. Ezt a műveletet többször (esetleg szekvenciálisan, vagy egyidejűleg) minden lehetséges kifejezéspárra elvégezzük, majd normál abszorpciót alkalmazunk;

Ha a hozzáadott kifejezés már szerepelt a DNF-ben, akkor teljesen eldobható, pl.

vagy

Természetesen a rövidített DNF nincs egyedileg definiálva, de mindegyik ugyanannyi betűt tartalmaz (például van DNF , Blake szabályának alkalmazása után egy ennek megfelelő DNF-hez juthatunk):

c) átmenet DNF-ről SDNF-re

Ha valamelyik egyszerű kötőszóból hiányzik egy változó, pl. z, illessze be a kifejezést, majd nyissa meg a zárójeleket (nem írunk ismétlődő diszjunkt kifejezéseket). Például:

d) átmenet KNF-ről SKNF-re

Ez az átmenet az előzőhöz hasonló módon történik: ha egy egyszerű diszjunkcióból hiányzik valamilyen változó (pl. z, majd hozzáadunk hozzá egy kifejezést (ez magát a diszjunkciót nem változtatja meg), ami után az eloszlási törvény segítségével megnyitjuk a zárójeleket:

így az SKNF-et a CNF-től kaptuk.

Megjegyezzük, hogy a minimális vagy csökkentett CNF-et általában a megfelelő DNF-ből kapjuk.

1. definíció.Konjunktív monomiális (elemi konjunkció) A változókból ezeknek a változóknak a konjunkciója vagy tagadásaik.

Például, elemi kötőszó.

2. definíció.Disjunktív monomiális (elemi diszjunkció) változókból e változók diszjunkciójának vagy tagadásaiknak nevezzük.

Például, egy elemi diszjunkció.

3. definíció. Egy adott propozíciós algebrai formulával ekvivalens képletet, amely elemi konjunktív monomiumok diszjunkciója, ún. diszjunktív normál forma(DNF) ennek a képletnek.

Például,– DNF.

4. definíció. Egy adott propozíciós algebrai formulával ekvivalens képletet, amely elemi diszjunktív monomiumok konjunkciója, ún. konjunktív normál forma(CNF) ennek a képletnek.

Például, – KNF.

Minden propozíciós algebrai képlethez találhatunk diszjunktív és konjunktív normálalakot.

Algoritmus normál alakok felépítésére

A logikai algebra ekvivalenciáival cserélje ki a képlet összes alapvető műveletét: konjunkció, diszjunkció, tagadás:

Szabadulj meg a kettős negatívumoktól.

Ha szükséges, alkalmazza az eloszlási és abszorpciós képletek tulajdonságait a konjunkció és a diszjunkció műveleteire.

2.6. Tökéletes diszjunktív és tökéletes konjunktív normálformák

Bármely Boole-függvénynek számos reprezentációja lehet DNF és CNF formájában. Ezen ábrázolások között különleges helyet foglal el a tökéletes DNF (SDNF) és a tökéletes CNF (SCNF).

1. definíció. Tökéletes diszjunktív normál forma(SDNF) egy olyan DNF, amelyben minden konjunktív monomiális a halmaz minden változóját pontosan egyszer tartalmazza, akár önmagát, akár annak tagadását.

Szerkezetileg az egyes propozíciós algebrai formulák SDNF-je DNF-re redukálva a következőképpen definiálható:

2. definíció. Tökéletes diszjunktív normál forma Egy propozíciós algebrai képlet (SDNF) DNF-nek nevezik, amely a következő tulajdonságokkal rendelkezik:

3. definíció. Tökéletes konjunktív normál forma Az (SCNF) egy olyan CNF, amelyben minden diszjunktív monom pontosan egyszer tartalmazza a halmaz minden változóját, és vagy önmaga, vagy annak tagadása jelenik meg.

Szerkezetileg az SCNF az egyes propozíciós algebrai képletekhez CNF-re redukálva a következőképpen definiálható.

4. definíció. Tökéletes konjunktív normál forma A propozíciós algebra adott formulájának (SCNF)-jét olyan CNF-nek nevezzük, amely kielégíti a következő tulajdonságokat.

1. tétel. A változók minden logikai függvénye, amely nem azonos hamis, megjeleníthető SDNF-ben, és egyedi módon.

Módszerek az SDNF megtalálására

1. módszer

2. módszer

válassza ki azokat a sorokat, ahol a képlet értéke 1;

kötőszók diszjunkcióját állítjuk össze azzal a feltétellel, hogy ha egy változó 1-es értékű konjunkcióval szerepel, akkor ezt a változót 0-val írjuk fel, akkor a tagadását. SDNF-et kapunk.

2. tétel. A változók minden logikai függvénye, amely nem azonos igaz, leírható az SCNF-ben, és egyedi módon.

Módszerek az SCNF megtalálására

1. módszer– ekvivalens transzformációkkal:

2. módszer– igazságtáblázatok segítségével:

válassza ki azokat a sorokat, ahol a képlet 0 értéket vesz fel;

diszjunkciók konjunkcióját állítjuk össze azzal a feltétellel, hogy ha egy változó 0 értékkel szerepel a diszjunkcióban, akkor ezt a változót írjuk fel, ha 1 értékkel, akkor a tagadását. SKNF-et kapunk.

1. példa CNF függvények létrehozása.

Megoldás

Szüntessük meg az összekötő ""-t a változó transzformáció törvényei segítségével:

= /de Morgan törvényei és kettős tagadása/ =

/elosztási törvények/ =

2. példa Adja meg a képletet a DNF-nek.

Megoldás

Fejezzünk ki logikai műveleteket a és használatával:

= /osztályozzuk a negációt változók közé és csökkentsük a dupla negatívokat/ =

= /eloszlási törvény/ .

3. példaÍrja be a képletet DNF és SDNF formában.

Megoldás

A logika törvényei segítségével ezt a képletet olyan alakra redukáljuk, amely csak az elemi kötőszók diszjunkcióit tartalmazza. Az eredményül kapott képlet a kívánt DNF lesz:

Az SDNF létrehozásához hozzunk létre egy igazságtáblázatot ehhez a képlethez:

Jelöljük a táblázat azon sorait, amelyekben a képlet (utolsó oszlop) az 1-es értéket veszi fel. Minden ilyen sorhoz kiírunk egy képletet, amely igaz a sor változókészletére:

1. sor: ;

3. sor: ;

5. sor: .

E három képlet diszjunkciója csak az 1., 3., 5. sor változóhalmazain veszi fel az 1-es értéket, és így lesz a kívánt tökéletes diszjunktív normálforma (PDNF):

4. példa Kétféleképpen vigye be a képletet az SKNF-be:

a) ekvivalens transzformációk felhasználásával;

b) igazságtáblázat segítségével.

Megoldás:

Alakítsuk át a második elemi diszjunkciót:

A képlet így néz ki:

b) Készítsen igazságtáblázatot ehhez a képlethez:

Megjelöljük a táblázat azon sorait, amelyekben a képlet (utolsó oszlop) 0 értéket vesz fel. Minden ilyen sorhoz kiírunk egy képletet, amely igaz a sor változókészletére:

2. sor: ;

6. sor: .

E két képlet konjunkciója csak a 2. és 6. sorban lévő változók halmazain veszi fel a 0 értéket, és így lesz a kívánt tökéletes konjunktív normálforma (PCNF):

Kérdések és feladatok az önálló megoldáshoz

1. Egyenértékű transzformációkkal redukálja le a képleteket DNF-re:

2. Ekvivalens transzformációkkal hozza a képleteket a CNF-be:

3. A második eloszlási törvény segítségével alakítsa át a DNF-et CNF-re:

A) ;

4. Alakítsa át a megadott DNF-eket SDNF-ekké:

5. Alakítsa át a megadott CNF-et SCNF-be:

6. Adott logikai képletekhez SDNF-t és SCNF-t kétféleképpen készítsen: ekvivalens transzformációkkal és igazságtáblázat használatával.

b) ;

Szabványos alap. Az elemi képletek literálok. Elemi konjunkció (disjunkció). Disjunktív (konjunktív) normálforma és tökéletes forma. Tétel: bármely 0-tól (1-től) eltérő Boole-függvény ábrázolható SDNF (SCNF) formában. A standard alap teljessége. Példák komplett alapokra: Zhegalkin bázis, Schaeffer vonás, Peirce nyíl.

Szabványos alap a Boole-algebra három eredeti műveletének halmaza: összeadás (egyesítés), szorzás (metszés) és negáció.

Itt fogunk hívni szó szerinti x változó vagy tagadása x és jelölje xˆ. Több, különböző változókkal definiált literál logikai metszéspontja, azaz. az X = xˆ 1 xˆ 2 forma kifejezése. . . xˆ l, hívott elemi kötőszó . Azt a követelményt, hogy minden változó különbözõ legyen, a következõk határozzák meg. Ha egy kötőszó több azonos literált tartalmaz, akkor a kötőszó kommutativitása, asszociativitása és idempotenciája miatt az ekvivalens formulára áttérve csak egy literál maradhat meg (például x 1 x 1 = x 1). Ha a konjunkció tartalmaz egy változót és annak tagadását, akkor a képlet ekvivalens a 0 konstanssal, mivel x x = 0 és bármely Y képletre Y x x = 0 van.

Több elemi kötőszó diszjunkcióját ún diszjunktív normál forma , vagy DNF . Például,

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

Ha egy adott DNF minden elemi konjunkciójában a változók összetétele azonos, akkor a DNF ún. tökéletes . A megadott példa egy nem tökéletes DNF. Éppen ellenkezőleg, a képlet

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

van egy tökéletes forma.

Mivel a Boole-algebrában az összeadás és a szorzás szimmetrikus műveletek, és az összeadást mindig szorzásként, a szorzást pedig összeadásként értelmezhetjük, kettős fogalom létezik - konjunktív normál forma (KNF ), amely elemi diszjunkciók konjunkciója, és tökéletes kötőszó forma (SKNF ). A szimmetrikus félgyűrűkre vonatkozó dualitás elvéből az következik, hogy a DNF-re vonatkozó bármely állításra a CNF-re vonatkozó kettős állítás válaszol, amelyet úgy kapunk, hogy az összeadást (diszjunkciót) szorzással, a szorzást (konjunkciót) szorzással, a 0-t konstanst 1-gyel, konstanssal helyettesítjük. 1 konstans 0-val, sorrendi viszony duálissal (inverz) sorrendben. Ezért a továbbiakban csak a DNF tanulmányozására fogunk összpontosítani.

Tétel 1.4. A 0 konstanstól eltérő bármely logikai függvény ábrázolható SDNF-ként.

◀ Állapodjunk meg, hogy x σ alatt az x képletet értjük, ha σ = 1, és az x képletet, ha σ = 0. Az f(y 1 , . . . , y n) függvény vegye fel az 1 értéket a (t) vektoron. 1 , , t n alkotóegység ). Ekkor az elemi konjunkció ezen a halmazon is felveszi az 1 értéket, de az összes többi n-dimenziós Boole-vektoron eltűnik. Fontolja meg a képletet

amelyben az összeg (unió) kiterjed az argumentumértékek azon halmazaira (t 1, . . . , t n), amelyeken adott funkciót az 1 értéket veszi fel. Vegye figyelembe, hogy az ilyen halmazok halmaza nem üres, tehát az összeg legalább egy tagot tartalmaz.

Könnyen belátható, hogy a Φ képlet 1 lesz azoknál és csak a változók azon értékeinél, amelyeknél a kérdéses függvény 1 lesz. Ez azt jelenti, hogy a Ψ képlet képviseli az f függvényt.

Következmény 1.1. A standard alap elkészült.

◀ Valójában, ha egy függvény nem konstans 0, akkor akár egy SDNF formájában is ábrázolható, amely egy szabványos alap feletti képlet. A 0 konstans például az f(x 1, x 2, . . . , x n) = x 1 x 1 képlettel ábrázolható.

Példa 1.2. Tekintsünk három m(x 1, x 2, x 3) változóból álló függvényt (1.4. táblázat), ún. többségi funkció ̆. Ez a függvény 1-re értékeli ki, ha argumentumainak több mint fele 1-es. Ezért gyakran szavazófüggvénynek nevezik. Építsünk hozzá egy SDNF-et.

A standard alap teljessége lehetővé teszi más kiválasztását komplett rendszerek funkciókat. Az F halmaz teljessége a következő megfontolások alapján állapítható meg. Tegyük fel, hogy a három szabványos buszfüggvény mindegyike egy F feletti képlettel ábrázolható. Ekkor az 1.3. Tétel szerint az F azonosság teljes lesz.

1.3. példa. A modulo 2 összeadás, szorzás és konstans 1 műveletek halmazát hívjuk Zhegalkin alapon . Az összeadás modulo 2 és a szorzás a Z2 gyűrű alapműveletei. Az 1-es konstans ebben az esetben szükséges a szabad tag felírásához. Mivel xx = x, ezért a polinomban minden tényező 1-es fokozatú. Ezért polinom írásakor nélkülözhetjük a fok fogalmát. Példák a Zhegalkin-alapú képletekre:

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

Minden ilyen képletet Zhegalkin-polinomnak neveznek. Valójában a Zhegalkin-polinom a Z2 gyűrű feletti polinom.

Nem nehéz a Zhegalkin-bázison képleteket összeállítani, amelyek a standard alap összeadásának és tagadásának műveleteit reprezentálják (a két bázis szorzása gyakori):

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

Ezért a Zhegalkin alapja egy teljes készlet.
Megmutatható, hogy bármely Boole-függvény esetén a Zhegalkin-polinom egyedileg definiált

(pontosabban a kifejezések sorrendjéig). A kevés változós Zhegalkin-polinom együtthatóit a határozatlan együtthatók módszerével találhatjuk meg.

Példa 1.4. Tekintsünk egyetlen függvény halmazát – a Schaeffer-löketet*. Ez a készlet a következő könnyen ellenőrizhető személyazonosságokból következik:

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

1.5. példa. Egy egyetlen függvényből, a Peirce nyílból álló bázis is kész. Ennek tesztje hasonló a Schaeffer stroke esetéhez. Ez a következtetés azonban a szimmetrikus félgyűrűk kettősségének elve alapján is levonható.

*Schaeffer stroke bináris, de nem asszociatív művelet. Ezért az infix űrlap használatakor legyen óvatos: az eredmény a műveletek sorrendjétől függ. Ebben az esetben ajánlatos a műveletek sorrendjét kifejezetten zárójelekkel megadni, például írjon (x | y) | z, nem x | y | z, bár mindkét forma egyenértékű.

Példa. Keresse meg a CNF képleteket

~ ~

Az SDNF tökéletes diszjunktív normál formája a következő algoritmussal szerkeszthető meg:

1. = 1. DNF algoritmus

2. = 2. DNF algoritmus

3. = 3. DNF algoritmus

4. = 4. DNF algoritmus

5. Hagyja ki az azonos hamis kifejezéseket, azaz az űrlap kifejezéseit

6. Egészítse ki a fennmaradó feltételeket a hiányzó változókkal

7. Ismételje meg a 4. pontot.

Példa. Keresse meg az SDNF képleteket.

~

Az SCNF létrehozásához a következő sémát használhatja:

Példa. Keresse meg az SDNF képleteket.

~

Ismeretes (2.11., 2.12. tétel), hogy az SDNF és az SCNF a képlet által egyedileg definiált, ezért a képlet igazságtáblázata segítségével megszerkeszthetők.

Az SDNF és SCNF igazságtáblázat szerinti felépítésének sémáját az alábbiakban adjuk meg a képlethez ~ :

			~
			1 0 1 0 1 1 0 1	SDNF;

SKNF.

2.2. Gyakorlat.

2.2.1 Az alábbiakban logikai kifejezéseket talál. Egyszerűsítse a variáns kifejezéseit, amennyire csak lehetséges, a Boole-féle logikai törvények segítségével. Ezután igazságtáblázatokkal hasonlítsa össze az egyszerűsített kifejezést az eredetivel.

2.2.2. Tisztázzuk az f 1 és f 2 ekvivalenciájának kérdését SDNF-re redukálva (1. táblázat).

№	2.2.3. Keresse meg f 3 duális függvényét az általánosított és a Boole-elv alapján (1. táblázat). Hasonlítsa össze az eredményeket.	f 1	f 2

f 3

2.3. Tesztkérdések.

2.3.1. Határozzon meg egy állítást.

2.3.2. Sorolja fel az utasítás főbb műveleteit!

2.3.3. Mi az igazságtáblázat?

~ ~ ~ ;

2.3.4. Hozzon létre igazságtáblázatokat a következő képletekhez:

;

2.3.5. Figyelembe véve a műveletek sorrendjére vonatkozó konvenciókat, hagyja ki a képletekből az „extra” zárójeleket és a „ ” jelet:

2.3.7. 2.3.6. Egyenértékű transzformációk segítségével bizonyítsd be a képletek azonos igazságát:

)

Keressen kettős képleteket:

~

2.3.8. Csökkentse a következő képleteket tökéletes DNF (SDNF) formára:

~

2.3.9. Csökkentse a következő képleteket tökéletes CNF (SCNF) formára: № 3

Laboratóriumi munka Téma:

„A logikai függvények minimalizálása. Logika" Cél:

Gyakorlati készségek elsajátítása a Boole-függvények minimalizálására szolgáló módszerekkel.

3.1. Elméleti információk.

Mint látható, bármely Boole-függvény ábrázolható tökéletes normál formában (disjunktív vagy konjunktív). Ezen túlmenően egy ilyen ábrázolás az első lépés a függvény táblázat specifikációjáról a függvényére való átmenetben elemző kifejezés. A továbbiakban a diszjunktív alakból indulunk ki, és a kötőszóra vonatkozó eredményeket a kettősség elve alapján kapjuk.

A logikai áramkörök logikai alapon történő szintetizálásának kanonikus problémája a Boole-függvények minimalizálására vezethető vissza, pl. diszjunktív normál formában ábrázolni, amely a legkevesebb betűt (változókat és tagadásaikat) tartalmazza. Az ilyen formákat minimálisnak nevezzük. A kanonikus szintézisben azt feltételezzük, hogy mind a jelek, mind azok inverziói az áramkör bemeneteire kerülnek.

A diszjunktív normálalakban bemutatott képletet egyszerűsíti a ragasztási művelet és az abszorpciós művelet ismételt használata és (a konjunktív normálalakban a kettős azonosságok a következőképpen alakulnak: és ). Itt és bármely Boole-algebrai képletként érthető. Ennek eredményeként olyan elemző kifejezéshez jutunk, ahol a további transzformációk már nem lehetségesek, pl. zsákutcás formát kapunk.

A zsákutcás formák között van egy minimális diszjunktív forma is, amely nem feltétlenül egyedi. Annak érdekében, hogy egy adott zsákutca űrlap minimális legyen, meg kell találnia az összes zsákutca űrlapot, és össze kell hasonlítania őket a bennük lévő betűk száma alapján.

Legyen például a függvény tökéletes normál diszjunktív formában:

A kifejezések csoportosításával és a ragasztási művelet alkalmazásával megvan a .

Egy másik csoportosítási módszerrel a következőket kapjuk:

Mindkét zsákutca forma nem minimális. A minimális forma eléréséhez ki kell tippelnie, hogy megismételjen egy kifejezést az eredeti képletben (ez mindig megtehető, mivel ). Az első esetben ilyen tag lehet . Akkor . A kifejezés hozzáadásával a következőt kapjuk: . Miután végigjárta az összes lehetséges lehetőséget, megbizonyosodhat arról, hogy az utolsó két űrlap minimális.

Ezen a szinten képletekkel dolgozni olyan, mint a sötétben bolyongani. A minimálformák keresésének folyamata vizuálisabbá és célirányosabbá válik, ha speciálisan erre a célra kifejlesztett grafikus és elemző ábrázolásokat, szimbólumokat használunk.

Többdimenziós kocka

A -dimenziós kocka minden csúcsa hozzárendelhető egy egység összetevőjéhez. Ezért a megjelölt csúcsok részhalmaza egy leképezés -dimenziós kocka Változók logikai függvénye tökéletes diszjunktív normál formában. ábrán. A 3.1. pont egy ilyen leképezést mutat a függvényhez a 3.7. pontból.

3.1. ábra SDNF-ben bemutatott függvény megjelenítése háromdimenziós kockán

Bármilyen diszjunktív normál formában megjelenített változók függvényének megjelenítéséhez meg kell teremteni a megfelelést a minitermek és a -dimenziós kocka elemei között.

A (-1) rangú miniterm két rangminimum (az egység alkotóeleme) összeragasztásának eredményének tekinthető, pl. , Egy dimenziós kockán ez azt jelenti, hogy két olyan csúcsot, amelyek csak az ezeket a csúcsokat összekötő koordináta értékeiben különböznek egymástól, éllel helyettesítünk (az élről azt mondják, hogy a rá eső csúcsokat takarja). Így a (-1)-edik rendű minitagok a -dimenziós kocka éleinek felelnek meg. Hasonlóképpen a (-2)-edik rendű minitermek megfeleltetését egy -dimenziós kocka lapjaival állapítjuk meg, amelyek mindegyike négy csúcsot (és négy élt) fed le.

A -dimenziós kocka méretekkel jellemzett elemeit -kockáknak nevezzük. Így a csúcsok 0 kockák, az élek 1 kockák, a lapok 2 kockák stb. A fenti okfejtést általánosítva feltételezhetjük, hogy a változók függvényében diszjunktív normál formában lévő ()-edik rangú minitermet egy -kocka képviseli, és minden -kocka lefedi mindazokat az alacsonyabb dimenziójú -kockákat, amelyek a változók függvényében vannak. csúcsok. Példaként az ábrán. A 3.2 három változó függvényét mutatja. Itt a minikifejezések 1-kockának felelnek meg (), a minitermet pedig egy 2-kockás ().

3.2. ábra Funkció lefedettség

Tehát bármely diszjunktív normálalakot egy -dimenziós kockára képeznek le -kockák halmaza, amely lefedi az egység összetevőinek megfelelő összes csúcsot (0-kockák). A fordított állítás is igaz: ha egy adott -kockák halmaza lefedi egy függvény egységértékeinek megfelelő összes csúcshalmazt, akkor az ezeknek a -kockáknak megfelelő minitermek diszjunkciója ennek a függvénynek a kifejezése a diszjunktív normálban. forma. A -kockák ilyen gyűjteménye (vagy a hozzájuk tartozó minikifejezések) azt mondják, hogy egy függvény lefedését képezi.

A minimális forma iránti vágyat intuitív módon egy olyan burkolat kereséseként értjük, amelynek kockáinak száma kisebb, mérete pedig nagyobb lenne. A minimális formának megfelelő fedezetet minimális fedezetnek nevezzük. Például az ábra lefedő funkciójához. 3.3 megfelel a minimális űrlapoknak És .

Rizs. 3.3 A funkciók lefedettségei.

balra – ; jobbra –

Egy függvény megjelenítése egy dimenziós kockán világos és egyszerű, ha . Egy négydimenziós kocka ábrázolható az ábrán látható módon. 3.4, amely négy változó függvényét és a kifejezésnek megfelelő minimális lefedettségét mutatja . Ennek a módszernek a használata rengeteget igényel összetett képződmények hogy minden előnye elvész.

Rizs. 3.4 Funkciókijelző egy négydimenziós kockán

Carnot térképek

Egy másik módszer a logikai függvények grafikus megjelenítésére Carnot térképek, amelyek speciálisan szervezett levelezési táblázatok. A táblázat oszlopai és sorai megfelelnek az összes lehetséges értékkészletnek, legfeljebb két változóból, és ezek a készletek olyan sorrendben vannak elrendezve, hogy mindegyik következő csak az egyik változó értékében tér el az előzőtől. . Ennek köszönhetően a táblázat szomszédos cellái vízszintesen és függőlegesen csak egy változó értékében térnek el egymástól. Az asztal szélein található cellák szintén szomszédosnak minősülnek, és rendelkeznek ezzel a tulajdonsággal. ábrán. A 3.5. ábra két, három, négy változó Karnaugh-térképét mutatja.

Rizs. 3.5 Carnaugh térképek két, három és négy változóhoz

A közönséges igazságtáblázatokhoz hasonlóan azoknak a halmazoknak a cellái, amelyekben a függvény 1-et vesz fel, egyesekkel vannak kitöltve (a nullák általában nem férnek bele, üres celláknak felelnek meg). Például az ábrán. 3,6, Aábra egy függvény Karnaugh-térképét mutatja, amelynek négydimenziós kockán való megjelenítését az ábra mutatja. 3.4. A dolgok leegyszerűsítése érdekében a változó 1-es értékének megfelelő sorokat és oszlopokat a változót jelző kapcsos kapcsos zárójellel kiemeljük.

Rizs. 3.6 Négy változóból álló függvény megjelenítése Carnaugh térképen

a) és minimális fedezete (b)

A függvényleképezések között n-dimenziós kocka és a Carnot térkép egy-egy megfeleltetése van. A Carnot térképen s-a kocka egy sorba, oszlopba, négyzetbe vagy téglalapba elhelyezett 2 szomszédos cella halmazának felel meg (figyelembe véve a térkép szemközti éleinek közelségét). Ezért az összes fenti rendelkezés (lásd a bekezdést. többdimenziós kocka), a Karnaugh-térképekre érvényesek. Tehát az ábrán. 3,6, b minimális diszjunktív formának megfelelő térképi egységek lefedettségét mutatja a kérdéses funkciót.

Karnaugh térképről a minikifejezések olvasása a segítségével történik egyszerű szabály. A sejtek kialakulása s-kocka, ad minitert (n–s)-edik rang, amely magában foglalja azokat (n–s) változók, amelyek ugyanazokat az értékeket tartják ezen s-cube, ahol az 1-es érték maguknak a változóknak, a 0-nak pedig azok tagadásainak felel meg. Változók, amelyek nem tartják meg értéküket s-kocka, hiányoznak a minitermben. Különféle módon A leolvasások eredményeképpen a függvény diszjunktív normál formában különböző reprezentációit kapunk (a jobb szélső minimális) (3.7. ábra).

A Karnaugh-térképek használata egyszerűbb konstrukciókat igényel, mint a térképezés n-dimenziós kocka, különösen négy változó esetén. Öt változó függvényeinek megjelenítéséhez négy változóhoz két Karnaugh-térképet, hat változó függvényéhez pedig négy ilyen térképet használnak. A változók számának további növekedésével a Karnaugh-térképek gyakorlatilag használhatatlanná válnak.

Híres az irodalomban Veitch kártyák csak a változóérték-készletek eltérő sorrendjében különböznek egymástól, és ugyanazokkal a tulajdonságokkal rendelkeznek, mint a Karnaugh-térképek.

Komplex kockák

A grafikus módszerek következetlensége, amikor nagy számban a változókat különféle kompenzálja elemzési módszerek Boole-függvények reprezentációi. Az egyik ilyen ábrázolás az kocka komplexum, a többdimenziós logikai tér terminológiáját használva, speciálisan kifejlesztett szimbolikával kombinálva.

). Az egység összetevőinek megfelelő 0-kockákat olyan változóérték-készletek képviselik, amelyeken a függvény egyenlő az egységgel. Nyilvánvalóan a felvételen

Rizs. 3.8 Három változóból álló függvény kockáinak komplexuma ( A) és szimbolikus ábrázolása ( b)

A kockák összetett formája maximális funkciólefedettség. Kivéve belőle mindazokat s-kockák, amelyeket nagyobb dimenziójú kockák borítanak, a zsákutcás formáknak megfelelő borításokat kapunk. Tehát a vizsgált példában (3.8. ábra) van egy zsákutcás burkolatunk

,

amely megfelel a funkciónak . Ebben az esetben ez a fedezet minimális.

Két Boole-függvény esetén a diszjunkciós művelet a kockakomplexusaik egyesülésének, a konjunkciós művelet pedig a kockakomplexusuk metszéspontjának felel meg. Egy függvény negációja egy kockakomplexum komplementerének felel meg, azaz , és minden olyan csúcs határozza meg, ahol a függvény 0 értéket vesz fel. Így egy az egyhez megfelelés (izomorfizmus) van a függvény algebrája között. Boole-függvények és kockák komplexeit reprezentáló logikai halmazok.

A függvények kockakomplexek formájában történő ábrázolása kevésbé vizuális, de legfontosabb előnye, hogy megszűnnek a változók számának korlátozásai, és megkönnyíti az információk kódolását számítógépek használatakor.

A logikai függvények minimalizálása

A probléma megfogalmazása. Az áramkör logikai alapon történő minimalizálása a minimális lefedettségnek megfelelő minimális diszjunktív formát keresi. Teljes szám normál formában szereplő levelek, a fedezés költségével kifejezve , ahol egy adott n változós függvény lefedését képező kockák száma. A minimális lefedettség jellemzi legalacsonyabb érték az árait.

A minimalizálási problémát jellemzően két lépésben oldják meg. Először is keresünk egy csökkentett borítót, amely tartalmazza az összes maximális méretű -kockát, de nem tartalmaz egyetlen kockát sem, amelyet ennek a borítónak egyetlen kockája sem fedne le. A megfelelő diszjunktív normálformát redukáltnak, minitermeit pedig egyszerű implikánsnak nevezzük. Egy adott funkciónál a csökkentett lefedettség egyedi, de lehet, hogy redundáns, mivel a kockák egy részét más kockák gyűjteményei fedik le.

A második lépésben átmenet történik a redukált diszjunktív normálformákról a zsákutcára, amelyek közül a minimális formákat választjuk ki. A zsákutcás formák úgy jönnek létre, hogy a redundáns kockákból kizárnak a redundáns kockákból, amelyek nélkül a megmaradt kockakészlet még egy adott funkció fedését képezi, de bármelyik kocka további kizárásával már nem fedi le a kockák halmazát. minden csúcs megfelel a függvény egyetlen értékének, azaz megszűnik fedő lenni.

Az a csökkentett lefedettségű kocka, amely egy adott függvény olyan csúcsait fedi le, amelyeket más kockák nem fednek le, nem lehet redundáns, és mindig benne lesz a minimális lefedettségben. Az ilyen kockát a hozzá tartozó implikánshoz hasonlóan extremálisnak (esszenciális implikánsnak) nevezzük, az általa lefedett csúcsokat pedig törölt csúcsoknak. Az extremálok halmaza alkotja a burkolat magját, egyértelmű, hogy a redukált burkolatról a minimálisra való átálláskor mindenekelőtt minden szélsőt el kell különíteni. Ha az extremálok halmaza nem képez burkolatot, akkor a redukált burkolatból kockákkal egészítjük ki.

A megadott definíciókat a ábra szemlélteti. 3.9, ahol a csökkentett lefedettség (lásd a 3.9a ábrát, ) és a minimális lefedettségeket (3.9b. ábra) és (lásd 3.9. ábra, b) a következőképpen fejezzük ki.

A konjunktív normálforma alkalmas a tételek automatikus bizonyítására. Bármely Boole-képlet redukálható CNF-re. Ehhez használhatja: a kettős tagadás törvényét, de Morgan törvényét, az eloszlást.

Enciklopédiai YouTube

• 1 / 5

  Képletek a KNF-ben:

  ¬ A ∧ (B ∨ C), (\displaystyle \neg A\wedge (B\vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E) , (\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge ( D\vee\neg E)) A∧B.

  Képletek (\displaystyle A\wedge B.):

  ¬ (B ∨ C) , (\displaystyle \neg (B\vee C),) (A ∧ B) ∨ C , (\displaystyle (A\wedge B)\vee C,) A ∧ (B ∨ (D ∧ E)) .

  (\displaystyle A\wedge (B\vee (D\wedge E)).)

  De ez a 3 képlet, amely nem szerepel a CNF-ben, egyenértékű a következő képletekkel a CNF-ben: ¬ B ∧ ¬ C , (\displaystyle \neg B\wedge \neg C,) (A ∨ C) ∧ (B ∨ C) , (\displaystyle (A\vee C)\wedge (B\vee C),)

  A ∧ (B ∨ D) ∧ (B ∨ E) .

  (\displaystyle A\wedge (B\vee D)\wedge (B\vee E).)

  CNF építése

  Algoritmus a CNF felépítéséhez 1) Szabaduljon meg a képletben szereplő összes logikai művelettől, és cserélje le őket az alapvető műveletekre: konjunkció, diszjunkció, tagadás. Ezt egyenértékű képletekkel lehet megtenni:

  A → B = ¬ A ∨ B , (\displaystyle A\rightarrow B=\neg A\vee B,)

  A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B) . (\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \neg B).)

  2) Cserélje ki a teljes kifejezésre vonatkozó tagadójelet az egyes változók utasításaira vonatkozó tagadójelekre a következő képletek alapján:

  ¬ (A ∨ B) = ¬ A ∧ ¬ B , (\displaystyle \neg (A\vee B)=\neg A\wedge \neg B,)

  ¬ (A ∧ B) = ¬ A ∨ ¬ B .

  (\displaystyle \neg (A\wedge B)=\neg A\vee \neg B.)

  3) Szabadulj meg a kettős negatívumoktól.

  4) Ha szükséges, alkalmazza az eloszlási és abszorpciós képletek tulajdonságait a konjunkció és a diszjunkció műveleteire. Példa a CNF felépítésére Vigyük a képletet a CNF-be F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) .:

  (\displaystyle F=(X\jobbra nyíl Y)\ék ((\neg Y\jobbra Z)\jobbra \neg X).)

  Alakítsuk át a képletet

  F (\displaystyle F)

  olyan képletre, amely nem tartalmaz

  → (\displaystyle \jobbra )