binary decision diagram

Angol

Főnév

binary decision diagram (tsz. binary decision diagrams)

1. (informatika) A Binary Decision Diagram (BDD, bináris döntési diagram) egy adatstruktúra, amelyet logikai függvények (Boole-függvények) kompakt és hatékony reprezentálására használnak. A BDD egy irányított körmentes gráf (DAG), amely minden változó lehetséges döntését egy bináris döntési fán keresztül modellezi.

---

🧠 Alapgondolat

A BDD célja, hogy egy Boole-függvényt (pl. f(x, y, z) = x AND (y OR z)) hatékonyan, tömören és strukturáltan tároljunk, manipuláljunk és kiértékeljünk.

A BDD-ben:

• Minden belső csomópont egy logikai változót jelöl.
• Minden él két lehetőséget képvisel:
  • 0-ág (hamis eset → „low” él)
  • 1-ág (igaz eset → „high” él)
• A levelek vagy 0 (hamis) vagy 1 (igaz) értékűek.

---

🔄 Működés

Egy BDD-ben egy adott változó értékétől függően döntünk, hogy balra (0) vagy jobbra (1) haladunk.

Példa:

   x
  / \
 0   y
    / \
   0   1

Ez a BDD a következő Boole-függvényt reprezentálja: f(x, y) = x AND y

---

✅ BDD Típusai

1. OBDD – Ordered BDD

• A változók fix sorrendben jelennek meg minden úton.
• Pl. minden ágban: x → y → z

2. ROBDD – Reduced Ordered BDD

• OBDD + ismétlődő struktúrák eltávolítása.
• Azonos részfák egyesítése.
• Kanónikus: egy adott változósorrendre egyértelműen meghatározott.

---

⚙️ Példa

Vegyük a függvényt: f(x, y) = x XOR y

Az igazságtábla:

x	y	f
0	0	0
0	1	1
1	0	1
1	1	0

A BDD (OBDD) így néz ki:

    x
   / \
  y   y
 / \ / \
0  1 1  0

---

🧾 Műveletek BDD-vel

Művelet	Leírás
AND(f, g)	Két függvény konjunkciója
OR(f, g)	Diszjunkció
NOT(f)	Negáció
restrict(f, x=1)	A függvény rögzítése adott változóra
compose(f, x, g)	f(x) → g helyettesítés
evaluate(f, assignment)	Függvény kiértékelése változóértékekre

Ezek mind strukturális algoritmusokkal megvalósíthatók a gráfon.

---

💡 Előnyök

• Kompakt reprezentáció: különösen hatékony sok egymásba ágyazott logikai kifejezésnél.
• Egyértelműség: ROBDD egy adott változósorrendre nézve egyértelmű.
• Gyors Boole-műveletek: AND, OR, NOT stb. hatékonyan végezhetők gráfokon.

---

❗ Hátrányok

• Erősen érzékeny a változók sorrendjére.
  • Rossz sorrend → exponenciális méretű gráf.
• Nem mindig jobb, mint igazságtábla.

---

🧰 Alkalmazások

• Formal verification (hardver, szoftver)
• Model checking
• Logikai szintézis
• Kompilátoroptimalizálás
• AI – tudásábrázolás (pl. döntési fa tömörítés)

---

🔧 Példa ROBDD építésre (koncepcionálisan)

1. Kezdjük a teljes bináris döntési fával.
2. Azonos részfákat egyesítünk (strukturális ekvivalencia alapján).
3. A változók sorrendjét megtartjuk (ordered).
4. Levágjuk a felesleges csomópontokat (pl. azonos értéket adó ágak).

---

✅ Összefoglalás

Tulajdonság	BDD
Típus	Gráf (DAG), bináris
Tartalom	Logikai függvények
Levelek	0 vagy 1
Csomópontok	Logikai változók
Legfontosabb típus	ROBDD (Reduced Ordered BDD)
Műveletek	Boole-algebra szerinti összevonások
Előny	Kompakt, gyors műveletek
Hátrány	Változósorrendre érzékeny

További információk

• binary decision diagram - Szótár.net (en-hu)
• binary decision diagram - Sztaki (en-hu)
• binary decision diagram - Merriam–Webster
• binary decision diagram - Cambridge
• binary decision diagram - WordNet
• binary decision diagram - Яндекс (en-ru)
• binary decision diagram - Google (en-hu)
• binary decision diagram - Wikidata
• binary decision diagram - Wikipédia (angol)