Diszkrét matematika
Témát. Boole függvények minimalizálása.
Előadás 6. A minimalizálás problémája. Egyszerű implikánsok létrehozása. Quine és McCloski algoritmus A minimalizálási probléma
Definíció. diszjunktív normál forma # 106; az f függvényt hívjuk
a) minimális (minimális a literálban), ha a f függvény más DNF-jei között a legkisebb számú változó szimbólum van;
c) a legrövidebb (minimális kötőszöggel), ha az elemi konjunktúrák minimális száma van.
Az n változók különálló elemi konjunktúráinak száma 3 n. mert bármely változó beírhatja a kapcsolatot, vagy be nem írhatja, vagy megadhatja a negációt. Ezután az n változók DNF-jét egyedileg határozza meg a 3 n hosszúságú vektor. amelyek nullákból és egyekből állnak, ahol 1 azt jelenti, hogy a megfelelő elemi összekapcsolás szerepel a DNF-ben, és 0 nem szerepel. Ezért az összes "N" változótól származó DNP-k száma.
A logika algebra önkényes függvényében sok DNF-et írhatunk. A minimalizálás problémája az, hogy egy minimális DNF-et építünk fel az f függvény fentebb meghatározott értelemben. Ez a probléma lehetővé teszi a triviális megoldást, amely az összes DNF-et megkeresi, de nyilvánvaló, hogy egy ilyen megoldás rendkívül időigényes még n kis értékei esetén is.
Definíció. képlet # 89: a képletet jelenti # 70; (kijelölés
# 89; # 70; ). ha ( # 89; # 70; ) º1. Nincs olyan értékkészlet, amelyre változók lennének # 121; az 1. értéket veszi fel # 70; a 0 érték.
Definíció. Az elemi kapcsolatot K az "f" függvény nevezõjének nevezzük. ha K f.
6.1. Példa.
Adjuk meg és hagyjuk, hogy K = x = x 1 y 0. K = 1 # 219; x = 1, y = 0. Mivel f (1,0, z) = 1 × 1 × z # 218; 1 × 1 × = z # 218; 1. akkor K = x az f függvény befogadója.
Legyen f (x, y, z, t) = x z # 218; x t, és legyen K = x = x 1 y 0. K = 1 # 219; x = 1, y = 0. Mivel f (1,0, z, t) = z # 218; t 1. Mivel ha z = 0 és t = 0. majd z # 218; t = 0, azaz. K = x nem jelent f.
ELMÉLETEK 6.1. Ha a képlet # 70; amely megvalósítja a f funkciót. Úgy néz ki, mint a DNP.
Bizonyítás. Hagyja, hogy ki = 1 a DNF-ben. Ezután és következésképpen f = 1.
Definíció. Az f implicit P függvénye egyszerűnek mondható. ha bármely P változótól való eltávolításakor a létrejövő elemi összefüggés nem implicant.
A 6.1. Példában. - Egy egyszerű implikátor, mert sem x, sem pedig nem.
TEOREM 6.2. Minden egyes funkció megjeleníthető formában, ahol Pi egyszerű implikáns.
Bizonyítás. Meg kell mutatni, hogy f = 1, ha és csak akkor, ha. Nyilvánvalóan, ha, akkor f = 1.
Most tegyük fel a változók egyes értékeinek sorát. Ebben az esetben, és a 6.1 tételből. ebből következik, hogy ki egy beavatkozó. Ezt a következtetést egy egyszerűre rövidítjük. Ezt az eljárást ismételjük meg minden olyan változóértékkészlet esetében, amelyre f = 1.
Definíció. Egy f függvény DNF-jét nem redundánsnak nevezik, ha:
Nyilvánvaló, hogy a minimális DNF elérhetetlen. Ezért minimális DNF-t kell keresni a nem redundánsok között. Így a minimalizálási probléma a következő szakaszokra osztható:
1) az f függvény összes egyszerű implikátorának megtalálása;
2) az f függvény nem redundáns DNF-einek megtalálása;
3) a minimális DNF funkció kiválasztása f.
Egyszerű implikánsok létrehozása
Definíció. Alapösszeköttetés # 97; melyet egy elemi konjunktúra fedez # 98;. ha minden változó benne van # 98;. tartalmazza # 97; (figyelembe véve a negációt).
6.2. Példa.
kötőszó # 97; = xyz a kötőszövetek hatálya alá tartozik # 98; = xy.
kötőszó # 97; = x z nem tartozik a kötőszavakhoz # 98; = x.
Definíció. Alapösszeköttetés # 97; az elemi összekapcsolódásnak nevezzük # 98; a DNP vonatkozásában # 70; . ha:
6.3. Példa.
enged # 70; = xy # 218; # 218; zt # 218; . Akkor a kötőszavak # 97; 1 = xyzt. # 97; 2 = xyz, # 97; 3 = xy t, # 97; 4 = xy a kapcsolódás kiegészítése # 98; = xy a # 70; .
TEOREM 6.3. enged # 70; - CDNF funkció f. Ha a # 98; - implicit f. majd az elemi összefogás összes kiegészítõjét # 98; a # 70; tartalmazzák # 70; .
Bizonyítás. Legyen az imént szereplő f, és legyen a kiegészítése # 98; a # 70; Tegyük fel # 97; nem szerepel a # 70; Vegyünk egy olyan változóérték-készletet, amilyen például # 97; = 1. azaz beállítjuk xi = # 100; i. i = 1, ..., n. Aztán u # 98; = 1. és # 70; = 0 óta # 97; feltételezés nélkül nem szerepel # 70; De ez ellentmond annak a ténynek, hogy # 98; egy f jelzője.
A CDNF-ben egyesülő tételből következik # 70; f függvényeket egy pár elemi konjunktúra párjához és egymást követõ egyenlõséget alkalmazva, ennek eredményeképpen az f függvény összes egyszerû implikánsját meg lehet szerezni.
6.4. Példa.
Tegyük fel, hogy f = xyzt # 218; x # 218; x zt.
Az első és a harmadik kötőszövet xyzt # 218; x zt = xzt. A második és a harmadik kötés x z # 218; x zt = x z. Az így kapott kifejezések egyszerűek, és következésképpen f = xzt # 218; x z.
A Quine és McCloskey algoritmus (egyszerű implikánsok felsorolása)
A fenti ötletet rendszerezzük.
1) Megírjuk az CDNF funkciót # 70; .
2) Minden elemi összefüggésben minden változót ugyanabban a sorrendben kell írni.
3) Minden elemi összekapcsolódás az 1. 0 és -. I-es helyre 1. ha az i-es változó tagadás nélkül csatlakozik, 0 - ha negálttal és -. ha nincs benne.
Például xyz # 218; x # 218; x lesz 111-es, # 218; 1-0- # 218; 1- -0.
4) Egy csoport elemi konjunktúráiból származunk, beleértve egy olyan csoportkészletet is, amelyek azonos számú egységgel rendelkeznek (olyan csoportok, amelyeknél az egységek száma 1-nél különbözik egymástól). rendezzék a csoportokat a növekvő számú egység sorrendjében.
Például egy funkcióhoz
az elemi kapcsolatok 1101, 1001, 1100, 1000, 0010, 0001, 0000, és a csoportok listája a következő:
5) Az egyenlőség csak a szomszédos csoportok megfelelő szettpárjaira alkalmazható. Egy megfelelő párt két készlet alkot, amelyek egy helyzetben különböznek egymástól, és nincs ebben a helyzetben vonal. Az egyező párokat csillagokkal (*) jelöljük.
6) Egy kötőjelet egy megfelelő pár eltérõ helyzetébe helyezzünk, és a következõ csoportot a következõ csoportok listájába helyezzük.
7) Ismételje meg a leírt folyamatot ameddig csak lehetséges. A nem jelölt készletek egyszerű implikánsokat tartalmaznak.
Ebben a példában a 6. és a 7. lépés így néz ki.