A Boole-függvények Quine-módszerrel történő minimalizálásának elméleti alapjai
Definíció. Egy logikai függvény implantációja g. amely egy elemi összekapcsolódás, azt mondják, hogy egyszerű, ha a g-re vonatkozó egyetlen rész sem tartalmaz az f függvényt.
A példabõl látható, hogy a következõk és. az egyszerű függvények f. A következõk g1. g2. g4. g6 nem egyszerű, hiszen ezek részei az f függvényben szerepelnek. Például a g5 g1 része. Bizonyíték nélkül adunk két olyan állítást, amelyek hasznosak a minimális DNF megszerzésében.
1. Bármely szám diszjunkciója Az F logikai függvény függvénye ennek a függvénynek a következménye.
2. Minden logikai logikai függvény egyenértékű az összes egyszerű implikátor diszjunkciójával. A Boole-függvény ábrázolásának ezt a formáját rövidített DNP-nek hívják.
A szóban forgó példából az összes Boole-függvény f-hez tartozó összes lehetséges feltérképezése lehetővé teszi annak igazolását, hogy az egyszerű implikáns csak két: g3 és g5, következésképpen az f rövidített DNF-je:
Amint az a táblázatból látható. 1, implicit g3. g5 együttesen lefedi az egység minden egyes egységét egységükre. A rövidített DNP-k beszerzése az első lépés a Boole-függvények minimális formáinak megtalálására. Amint már említettük, a rövidített DNF tartalmazza a Boole-függvény összes egyszerű implikátorait. Néha egy csökkentett DNP-ből egy vagy több egyszerű implikátor eltávolítható anélkül, hogy megsértené az eredeti funkció egyenértékűségét. Az ilyen egyszerű implikátorokat feleslegesnek fogják nevezni. A felesleges egyszerű implikánsok felszabadítása a rövidített DNP-kről a minimalizálás második fázisa.
Definíció. A Boole-függvény rövidített DNF-jét "dead-end" függvénynek nevezik, ha nincs benne extra egyszerű implikátor.
A redundáns elsődleges implicants redukált DNF egy Boole-függvény nem egyszerű folyamat, azaz. E. Boole-függvény lehet több holtpont DNF.
Jóváhagyása. A logikai függvény fékhibája DNF f. a minimális betűk száma minimális. A minimális DNF is lehet több.
Tekintsünk több módszert a minimalizálásra. Mindegyik gyakorlatilag csak az első szakaszban különbözik - a redukált DNF megszerzésének szakaszában. Meg kell jegyezni, hogy sajnos a minimális DNF keresés mindig kapcsolatban áll a megoldások megoldásával. Vannak módszerek a keresés csökkentésére, de mindig így marad.
A Quine módszer két alap kapcsolaton alapul.
1. A kötési arány
ahol A bármely elemi termék.
2. Abszorpciós arány
Mindkét kapcsolat érvényessége könnyen ellenőrizhető. A módszer lényege az összes lehetséges ragasztás, majd az abszorpció szekvenciális végrehajtása, amely rövidített DNF-hez vezet. A módszer a tökéletes DNF-re alkalmazható. Az abszorpciós viszonyból következik, hogy bármely tetszőleges elemi termék abszorbeálódik bármelyik részében.
A bizonyíték elegendő ahhoz, hogy megmutassuk, hogy önkényes, egyszerű implikátor szerezhető be. Valójában a telepítési művelet p-re történő alkalmazása (a ragasztási művelet inverze):
az eredeti f függvény minden hiányzó változójához megkapjuk az egység összetevői S-t. Amikor összeragasztjuk az S alkotóelemét, megkapjuk a p. Az utóbbi nyilvánvaló, mivel a ragasztási művelet a telepítési művelet fordítottja. A konstansok S-csoportja feltétlenül jelen van a tökéletes DNF-függvényben f, mivel p jelentése.
Egy példa. Legyen egy Boole-függvény egy igazságtáblázat által megadott módon (9.12. Táblázat). A CDNF így néz ki:
Az expozíció kényelmét tekintve az egység egyes alkotóelemeire a f függvény SDNF-jére utalunk (tizedes szám (önkényes)). Ragasztást végzünk. Az 1. alkotmányt csak a 2. összetevővel (változóban) és a 3. összetevővel (változóban), a 2. összetevővel és a 4. alkotóval együtt ragasztjuk össze, és így tovább.
Ennek eredményeképpen megkapjuk
Megjegyezzük, hogy a ragasztás eredménye mindig elemi termék, amely a ragasztandó összetevők közös része.
Ezután ragasztjuk össze az elemi termékeket. Csak azokat a munkákat, amelyek ugyanazokat a változókat tartalmazzák, össze vannak ragasztva. Két ragasztási eset van:
ugyanazon elemi termék megjelenésével, a további ragasztás lehetetlen. Az abszorpciót követően (a kapott DNF-ből töröljük az összes elnyelt elemi termékeket), rövidített DNF-t kapunk:
Átmegyünk a második szakaszba. A minimális DNF megszerzéséhez minden felesleges egyszerű implikánsot el kell távolítani a csökkentett DNF-ből. Ezt egy Quine speciális implicit mátrixával végezzük. Sorok e mátrix jegyezni egyszerű implicants egy Boole függvény, azaz a tagok a csökkentett DNF, és oszlopok - .. Unit tevő, azaz tagjai PDNF Boole ...
Példa (folytatás). Az implicit mátrix formája (3. táblázat).
Mint már láttuk, egy egyszerű implikátor elnyeli az egység egyes alkotóelemeit, ha ez a saját része. Az implikáló mátrix megfelelő celláját a sor metszéspontjában (a szóban forgó egyszerű szóban forgó) és az oszlopon (az egység összetevőjével) keresztjelöléssel jelöljük (3. táblázat). A minimális DNF-ek a következõ mátrixból épülnek fel:
1) egy, csak egy keresztjelű mögöttes mátrix oszlopait keressük. Az ezeknek a keresztezéseknek megfelelő egyszerű implikánsokat alapvető implikánsoknak nevezik, és a Boole-függvény úgynevezett magját alkotják. A mag szükségszerűen szerepel a minimális DNF-ben.
2) fontolóra veszi a különböző lehetőségeket egy olyan egyszerű implikáns készlet kiválasztására, amely átlépi a befogadó mátrix fennmaradó oszlopait keresztekkel, és kiválasztja a
az ilyen aggregátumokban levő betűk minimális száma teljesen implicit.
Példa (folytatás). Funkunk lényege implikáns; A jelszó fölösleges, mivel a mag a befogadó mátrix összes oszlopát lefedi. Ezért a funkciónak egyedülálló zsákutca és minimális DNF van:
Meg kell jegyezni, hogy az egy sorban lévő N keresztek száma mindig 2-es. Ezenkívül az olvasó könnyen ellenőrizheti
,ahol k az egyszerű befoglalóban lévő betűk száma.
Felhívjuk a figyelmet arra is, hogy a különböző kapcsolatok használatával kibővíthetjük a Quine módszer alkalmazási körét a tökéletes DNF határain túl.
Egy példa. Minimalizálja a Boole-függvényt Quine módszerével:
1. A fent említett kapcsolatok segítségével megszabadulunk a negatívoktól és a zárójelektől
2. Állítsa vissza az SDNF funkciót f a telepítési művelet alkalmazásával
3. Lássuk az f függvény rövidített DNF-jét, és az SDNF-ben minden lehetséges ragasztást készítünk
4. Az F függvény minimális DNF-jét keressük a következõ mátrixból (4. táblázat). A Boole-függvény rendszermagja :. .Minimum DNF: