2006. január 18. vizsga forrásának megtekintése

{{GlobalTemplate|Infoalap|FormModVizsga20060118Megoldas}}


==2.5 Feladat==

Az eredeti példaábra:

{{InLineImageLink|Infoalap|FormModVizsga20060118Megoldas|form_v_20060118_25.JPG}}

Az egy gráftranszformáciüs lépéssel elérhető modellek, piros a régi elemeket jelöli, a zöld az újakat:

{{InLineImageLink|Infoalap|FormModVizsga20060118Megoldas|form_v_20060118_25mo.JPG}}

===2.5.1===

Az '''egyes''' gránsztranszformációs szabály az eredeti modell "bal" és "jobb" oldalára is illeszthetjük, ennek az eredménye az első két ábra.

A '''kettes''' szabály sehol sem alkalmazható, mivel nincs olyan place, amihez kapcsolodik person is meg gift is (gondolom az a P person akart lenni...)

A '''harmas''' szabalynal csak egy olyan place van, amihez kapcsolodik box, de gift nem, ezt az illesztest mutatja a harmadik abra.

===2.5.2===

Az '''egyes''' szabaly ket illesztesi lehetosege (jobb ill baloldali illesztes) kolcsonosen kizarja egymast, mivel a kozepso P1 place-tol elveszik a persont, igy a masik mar nem fog illeszkedni.

'''Egyes''' szabaly utan csak akkor alkalmazhatjuk a '''kettest''' , ha az elso szabalyt a modell bal oldalra illesztjuk, es csak ekkor kerul egy place-hez egy gift es egy person

'''Egyes''' szabaly utan a '''harmas''' alkalmazhato: ha az egyes szabalyt a bal oldalra illesztjuk, akkor a P4 es P3 helyre is illesztheto lesz a  harmas, de ha jobb oldalra illesztjuk, akkor az az eredetileg jo P3 helyet elrontja es uj jot sem hoz letre, tehat ezutan nem johet a harmas

'''Kettes''' szaballyal nem kezdhetunk, lasd elozo 2.5.1es feladat.

'''Harmas''' utan '''egyes''' alkalmazhato: a P3ra illeszkedo harmas szabaly alkalmazasa utan az egyest az abra bal oldalara minden tovabbi nelkul illeszthetjuk, de a jobb oldali illesztest elrontja a harmas a box giftre valo cserejevel.

'''Harmas''' utan '''kettes''' : ugyan a harmas utan a P3 helynel lesz gift, de nem lesz person, igy nem alkalmazhato.

'''Harmas''' utan '''harmas''' :  mivel csak a P3ra illesztheto a harmas, sajat lehetoseget rontja el, tehat nem illesztheto.

Osszefoglalva, a fuggetlen graftranszformacios lepesek: csak a bal oldalra illesztett '''egyes''' es a '''harmas''' fuggetlen egymastol, mivel ebben az esetben a sorrend mindegy, minden mas esetben az egyik szabaly nem alkalmazhato.


==2.6 Feladat==

Adottak az alábbi logikai függvények: (sum 6p)<br />

<math> f := \neg(y \vee x) \vee (\neg x \wedge z ) </math> <br/> 
<math> g := (\neg z \vee \neg y ) \wedge ( x \vee \neg z ) </math> <br/>
<math> m := f \wedge g </math> <br/>

2.6.1 Határozza meg az f, g, m logikai függvényeket ROBDD alakban! Az m függvény
kiszámítását közvetlenül az ROBDD-ken értelmezett műveletekkel végezze el! Az m
függvénynek az f és g függvények ROBDD-jéből történő kiszámítása is kell!

Először is átalakítjuk az első kifejezést a De Morgan szabállyal, hogy rendes konjunktív alakban legyen, mert úgy kisebb ROBBD ábrát kapunk majd. Ekkor tehát 
<math> f := ( \neg y \wedge \neg x ) \vee ( \neg x \wedge z ) </math>

A ROBDD redukált és rendezett a változók sorrendjét tekintve, ezért keresnünk kell egy olyan változósorrendet, amelyet mindkét, az f és a g ROBDD diagramjában is használni fogunk, és lehetőleg minél kisebb méretű gráfot eredményez. Nyilván akkor lesz a gráf kisebb, ha elsőnek olyan változó szerint vizsgáljuk, amely közvetlen levélbe vezet, vagyis ahol egy változó alapján dönteni tudunk, hogy a kifejezés értéke igaz lesz, avagy hamis.<br />
Ilyen pl. f esetében az x, hiszen annak 1 értéke esetén egész biztosan hamis lesz a kifejezés értéke. Igen ám, de ez g-ben nem teszi lehetővé rögtön a döntést, mert x igaz és hamis volta még nem határozza meg egyértelműen a g kifejezés logikai értékét. Itt a z változó volna a nyerő, hiszen annak hamis értéke esetén a g kifejezés biztosan igazra értékelődik ki.<br />
Y egész biztosan nem jó választás kezdő változónak, hiszen az eredményezné mindkét esetben a legnagyobb döntési fát!<br />
A feladat innentől tehát kétféleképp megoldható, ám tudnunk kell, hogy bármely megoldási utat választjuk is, az egyszerűsítések után a végeredmény egyértelmű kell, hogy legyen, hiszen minden logikai kifejezéshez, és így f-hez, g-hez és a kettejük konjunkciójának (azaz m-nek) is pontosan egy-egy ROBDD gráf feleltethető meg.<br />
Válasszuk most első változóként az x-et, második nyilván a z lesz (hiszen az y-nal továbbra is csak felesegesen növelnénk a fát), a harmadik pedig az y.<br />

F, G előállítása:

{{InLineImageLink|Infoalap|FormModVizsga20060118Megoldas|fesg.png}}<br />

A ROBDD előállítása úgy történik, hogy vesszük az első változót, és behelyettesítünk a kifejezésbe először 0-t (baloldali ág), majd 1-et (jobb oldali ág), és megnézzük mi az eredmény. Ha egyből ki tudjuk értékelni a logikai kifejezést, mint pl. az f kifejezésben x=1 esetén a jobb ágon, akkor örülhetünk, mert azt nem kell tovább vizsgálni. Ha nincs így, akkor vesszük a fentebb meghatározott sorrend szerinti következő változót, és elvégezzük ugyanezt a vizsgálatot. A fa legfeljebb 3 mélységű lehet, hiszen 3 változónk van, és legrosszabb esetben egy 3 mélységű teljes fát kaphatnánk, ha a lehető legrosszabb sorrendbe állítottuk volna fel a változókat. Így azonban a 2^3 csomópont helyett mindössze 5-öt kaptunk az f kifejezésre, tehát jól látszik, hogy valóban sikerült tömörítenünk a kifejezést (ti. az igazságtábla 2^3=8 elemet tartalmaz, mi pedig 5 csomóponttal leírtuk ugyanezt a függvényt).<br />
A G ROBBD-jének előállítása hasonlóan történik, az első ábrát nyomon követve látható, hogy x=1, z=1 esetén még mindig nem tudunk dönteni a kifejezés logikai értékéről, csak y kiértékelése után.

m = f /\ g előállítása:

{{InLineImageLink|Infoalap|FormModVizsga20060118Megoldas|fesg2.png}}<br />

Ha megvan a két ROBDD, és a kettőnek a gyökértől számítva azonosak a változók sorrendjei, akkor a két gráf csomópontjainak direkt szorzatát véve (lásd formális nyelvek: két nyelv metszete = véges automaták állapotainak direkt szorzata) éppen a kívánt BDD-t kapjuk, ami viszont sajnos még egyszerűsítésre szorul.
A direkt szorzat képzése szemléletesen úgy működik, hogy vesszük mindkét ROBDD gyökerét, és rátesszük az ujjunkat. Aztán mindkét ROBDD-n nyomon követjük a változók értékadását: az első, majd második stb. változó 0 illetve 1 értéke esetén hova kerülünk F ill. a G ROBDD-jében, és ezeket egy közös változónévpárral jelölt csomópontba felírjuk.
Pl. a kezdő (X,X - melynek jelentése X változót vizsgáljuk az F ROBDD-jében, és szintén X változót a G ROBDD-jében) változópár vizsgálatakor x=1 hatására a (0,z) párt kell vizsgálnunk, hiszen az F ROBDD-jében x igaz esetén már biztosan hamis lesz a kifejezés értéke, míg G ROBDD-jében a z vizsgálatára térünk át. Ha mindkét ROBDD-ben levélhez, azaz 0,0 0,1 1,0 vagy 1,1 -hez értünk, akkor azt az ágat nem kell tovább vizsgálni, hiszen az alapján már el tudjuk dönteni a két kifejezés között értelmezett műveletet, azaz jelen esetben, mivel a feladat m = f /\ g -t kérdezi, az ÉS műveletet.<br />

Az egyszerűsítés folyamata, eredmény ROBDD előállítása:

{{InLineImageLink|Infoalap|FormModVizsga20060118Megoldas|fesg3.png}}

* Ha x változónak 0 és 1 értéke esetén is ugyanazon y változó vizsgálatára térünk át, azaz a kifejezés értéke az x változótól független, akkor x-et egyszerűen elhagyhatjuk a BDD-ből (x szülőjéből a nyíl a gyerekébe, azaz y-ba mutat, őt magát pedig törölhetjük)
* Ha a BDD-ben van több ugyanolyan címkéjű csomópont, azokat összevonhatjuk, természetesen megtartva a kimenő/bemenő nyilakat.

A példánkban (lásd 2. ábra) a nagy karikával jelölt rész helyére 0-t írhatunk, hiszen minden részfája hamis eredményre vezet. Vigyázat: ha pl. nem m = f /\ g, hanem m = f \/ g lenne a feladat, akkor nem hagyhatnánk el ezt az egész részfát, hiszen a jobb alsó részen 0,1 és 0,0 nem lenne azonos! Tudniillik 0 /\ 1 = 0, 0 /\ 0 = 0, azonban 0 \/ 1 = 1, 0 \/ 0 = 0.<br />
Ezenkívül összevonhatunk minden =0 -val jelölt levelet, valamint ha több is lenne, akkor az =1 -gyel jelölt leveleket is.<br />
Végül egyszerűsítsük a csomópontok címkéit, és csak a változók neveit tüntessük fel egy példányban, a vessző utáni másik változónevet / logikai konstanst nem szükséges kiírni. A végeredmény, azaz az f és g kifejezések konjunkciójának megfelelő ROBDD gráf a 3. ábrán látható.

-- [[NeoXon|NeoXon]] - 2006.05.28.


[[Category:Infoalap]]