Bináris döntési diagramok (ROBDD)

A VIK Wikiből
A lap korábbi változatát látod, amilyen (vitalap) 2012. október 21., 20:58-kor történt szerkesztése után volt. (Új oldal, tartalma: „{{GlobalTemplate|Infoalap|FormModVizsgaRobdd}} __TOC__ ==Elmélet== * Milyen előnyt jelent a logikai függvények bináris döntési diagramok (ROBDD) alakjában tö…”)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót


Elmélet

  • Milyen előnyt jelent a logikai függvények bináris döntési diagramok (ROBDD) alakjában történő ábrázolása a hagyományos Karnaugh táblás ábrázolásmóddal szemben?
    • ROBDD tömörebb, csökkentett állapottér. Azaz: egyszerűbb -> kevesebb erőforrás igény.
  • Mit jelent és milyen feltételek mellett áll fenn, hogy egy (redukált rendezett) bináris döntési diagram (azaz ROBDD) egy logikai függvény kanonikus egyértelmű reprezentációja?
    • Adott változó sorrend mellett.

Bool algebra ismétlés

  • Alaptulajdonságok:
    • a * a = a
    • a + a = a
    • a + 1 = 1
    • a * 0 = 0
    •  ! 0 = 1
    •  ! 1 = 0
    • a * ( ! a ) = 0
    • a + ( ! a ) = 1
    •  !! a = a
  • Asszociativitás
    • a + ( b + c ) = ( a + b ) + c
    • a * ( b * c ) = ( a * b ) * c
  • Kommutativitás
    • a + b = b + a
    • a * b = b * a
  • Disztributivitás
    • a * ( b + c ) = (a * b) + (a * c)
    • a + ( b * c ) = (a + b) * (a + c)
  • De Morgan
    • (a + b) = ! ( (! a) * ( ! b ))
  • Elnyelési tulajdonság
    • a + ( a * b ) = a
    • a * ( a + b ) = a
  • Egyéb még hasznos ötlet
    • c + ( ( ! c) * a * b) = c + a * b
    • a->b = ! a + b

Igaz/Hamis

Példák

-- adamo - 2006.06.10.