[JS]
[DE]
[USE] expr
[USE] graph
[TITLE] Boolesche Funktionen und Binäre Entscheidungsbäume
[FUN]
```
var eparse = Expr();
function isBoolVal(v) { return (typeof v == 'boolean') || (typeof v == 'number') || Number(v)==0 || Number(v)==1 }
function isTrue(v)  { return  v==1 || v==true || v=='1' };
function isFalse(v) { return v==0 || v==false || v=='0' };
function evalBoolExpr(node,env) {
    var v1,v2;
    // (x1 op y1) (x2 op y2) ?
    function isTriple(a,b,op) {
      return (
          a.type=='BinaryExpression' && 
          b.type=='BinaryExpression' &&
          a.operator==op && b.operator==op &&
          a.left.type == 'Identifier' &&
          b.left.type == 'Identifier' &&
          a.right.type == 'Identifier' &&
          b.right.type == 'Identifier')
    }
    // (x*y)+(x*z) -> x*(y+z)
    function simplify1(a,b) {
      if (isTriple(a,b,'*')) {
        if (a.left.name==b.left.name) 
          return a.left.name+'*('+a.right.name+'+'+b.right.name+')'
        if (a.left.name==b.right.name) 
          return a.left.name+'*('+a.right.name+'+'+b.left.name+')'
        if (a.right.name==b.left.name) 
          return a.right.name+'*('+a.left.name+'+'+b.right.name+')'
        if (a.right.name==b.right.name) 
          return a.right.name+'*('+a.left.name+'+'+b.left.name+')'
      }
    }
    // (x+y)*(x*z) -> x+(y*z)
    function simplify2(a,b) {
      if (isTriple(a,b,'+')) {
        if (a.left.name==b.left.name) 
          return a.left.name+'+('+a.right.name+'*'+b.right.name+')'
        if (a.left.name==b.right.name) 
          return a.left.name+'+('+a.right.name+'*'+b.left.name+')'
        if (a.right.name==b.left.name) 
          return a.right.name+'+('+a.left.name+'*'+b.right.name+')'
        if (a.right.name==b.right.name) 
          return a.right.name+'+('+a.left.name+'*'+b.left.name+')'
      }
    }
    switch (node.type) {
      case 'BinaryExpression': 
        v1=evalBoolExpr(node.left,env);
        v2=evalBoolExpr(node.right,env);
        switch (node.operator) {
          case '+': 
            if (isBoolVal(v1) && isBoolVal(v2)) return v1||v2;
            else if (!isBoolVal(v1) && isBoolVal(v2)) return isTrue(v2)?1:v1;
            else if (isBoolVal(v1) && !isBoolVal(v2)) return isTrue(v1)?1:v2;
            else return simplify1(node.left,node.right)||('('+v1+'+'+v2+')');
          case '*': 
            if (isBoolVal(v1) && isBoolVal(v2)) return v1&&v2;
            else if (!isBoolVal(v1) && isBoolVal(v2)) return isFalse(v2)?0:v1;
            else if (isBoolVal(v1) && !isBoolVal(v2)) return isFalse(v1)?0:v2;
            else return simplify2(node.left,node.right)||(v1+'*'+v2);
      }
      case 'UnaryExpression':
        switch (node.operator) {
          case '!': 
            v1=evalBoolExpr(node.argument,env);
            if (isBoolVal(v1))
              return isTrue(v1)?0:1;
            else return '!('+v1+')';
        }
      case 'Identifier':
	return env[node.name]!=undefined?env[node.name]:node.name
      case 'Literal':
	return Number(node.raw)
    }
    return 0;
}

function evalBoolPrint(text,stdout,stderr) {
  var ex = eparse(text);
  var res = evalBoolExpr(ex,{});
  stdout(res);
}

// Supported syntax: a*b a+b !a () y1=expr NL y2=expr NL ..
function boolEvalTable(text,stdout,stderr,options) {
  options=options||{};
  var exl=[],ex,vars=[],y=[],nvars=0;
  var lines = text.split('\n');
  for(var i in lines) {
    var tokens=lines[i].split('=');
    ex=tokens[1]||tokens[0];
    try { ex = eparse(ex) } catch (e) { stderr(e.toString()); return };
    var varspart = getVarsFromExpr(ex);
    nvars=Math.max(nvars,varspart.length);
    var ypart=tokens[1]&&tokens[0]||'y';
    varspart.push(ypart);
    y.push(ypart);
    varspart.forEach(function (v) { if (vars.indexOf(v)==-1) vars.push(v) });
    exl.push(ex);
  }
  if (exl.length==1) ex=exl[0];
  var data = [];
  var yindex = 0;
  for(var row=0;row<Math.pow(2,nvars);row++) {
    var env = {} 
    data.push(Object.map(vars,function (v,index) {
     if (y.indexOf(v)==-1) {
       yindex=0;
       env[v]=(row & Math.pow(2,index))?1:0;
       return env[v];
     } else {
       return evalBoolExpr(exl[yindex++],env)
     }
    })); 
  }
  var t = {
    columns: vars.map(function (name) { return { name:name, type:'number' }}),
    data : data
  }
  if (!options.silent) stdout('Ok.');
  return t;
}

# Boolesche Funktionen und Binäre Entscheidungsbäume

[INPUT] Name { label:"username"; eval:updateConfig; }
[INPUT] Matrikelnummer { label:"usernumber" }

## Einführung

Lese Folien 27 bis 65 hier [Modul C](http://edu-9.de/lehre/pdl2kC.html).

## Boolesche Funktionen

Eine boolesche Funktion $f(a,b,c,..)$ bildet eine Menge von *n* Eingabevariablen auf *m* Ausgabevariablen ab:

$
f(x_1,x_2,x_3,..,x_n) : B^n \rightarrow B^m
$

Boolesche Funktionen bestehen aus Variablen, Verknüpfungen, und Werten.

[INFO] Syntax Boolesche Algebra
- Ausdrücke bestehen aus Operatoren, Variablen, und Werten
- Disjunktion (Oder-Verknüpfung): `+`
- Konjunktion (Und-Verknüpfung): `*`
- Negation: `!`
- Variablen: Jeder Namensbezeichner mit Buchstaben
- Werte: `0,1`
- Bindung von Ausdrücken: `( expr )`
- Funktion: `y=expr`
- Shanonzerlegung nach einer Variable *x*: `(expr)|x`

Im ersten Beispiel können Boolesche Funktionen algebraisch und symbolisch automatisch evaluiert und vereinfacht werden:

[CODE] Boolesche Funktionsevaluierung (Symbolische Vereinfachung) { eval:evalBoolPrint }
```
(a+b)*(a+1)
```

[EXERCISE]
- Vereinfache folgende Ausdrücke mit obigen Evaluator:
  1. `!a*b*!c+!a*b*c+a*b`
  2. `z+(x+y)*(z+x)`
  3. `z+(x+y)*(z+x)*(x+y)`
  4. `z+(x+y)*(z+x)*x`
  5. `z+(x+y)*(z+x)*(x+1)`

- Welche Regeln der Booleschen Algebra werden durch den automatischen Evaluator angewendet? Welche fehlen? Finde es heraus!
[EXERCISE]

[INPUT] Lösung

Im nächsten Beispiel kann aus einer booleschen Funktion eine Funktionstabelle erstellt werden.

[TABLE] Boolesche Funktionsevaluierung (Erzeugung Tabelle) { eval:boolEvalTable; label:"bool1" }
```
a+b
```

[EXERCISE]

Teste ob die automatische Reduktion korrekt ist anhand der vorherigen Aufgabenbeispiele und dem Vergleich über die Funktionstabelle. Dazu kann im Tabellengenerator die Syntax `y1=a+b+c y2=a+b` verwendet werden (multiple BF, je eine BF pro Zeile).

[EXERCISE]

Erstelle im nächsten Schritt die DNF und KNF Terme in folgender Funktionstabelle (jeweils entsprechend für *y*=1/0 Zeilen):

[TABLE] { readonlyColumns:[0,1,2,3]; label:"table1" }
|a|b|c|y|Term|
|--- |--- |--- |--- |--- |
|0|0|0|1|!a\*!b\*!c|
|1|0|0|0||
|0|1|0|1||
|1|1|0|1||
|0|0|1|0||
|1|0|1|1||
|0|1|1|1||
|1|1|1|0||

Hier kann die Funktion auf Korrektheit getestet werden:

[TABLE] Test 1 { label:"table1-test" }
[FUN]
```
var rows =Tables["table1"].getRows();
var dnf = '', knf = '', sep1='', sep2='';
rows.forEach(function (row) {
  if (row.y=="1" && row.Term!="") { dnf = dnf + sep1 + row.Term; sep1 = '+'; }
  if (row.y=="0" && row.Term!="") { knf = knf + sep2 + row.Term; sep2 = '*'; }
})
Print('DNF (y1): '+dnf)
Print('KNF (y2): '+knf)
var t1 = boolEvalTable(dnf||'0',Print,PrintError,{silent:true})
var t2 = boolEvalTable(knf||'0',Print,PrintError,{silent:true})
t1.columns.push({name:'y1',type:'string'});
t1.columns.push({name:'y2',type:'string'});
t1.data.forEach (function (row, index) { row.y1=row.y; row.y2=t2.data[index]?t2.data[index].y:"0"; row.y=rows[index].y; });
Codes['bool1'].setText(dnf);
return t1;
```

## Entscheidungsbäume

## Einführung

Lese Folien 66 bis 78 hier [Modul C](http://edu-9.de/lehre/pdl2kC.html).

- 1986 von R. Bryant vorgeschlagen

- Eine Boolesche Funktion *f* wird repräsentiert als gerichteter azyklischer Graph (DAG):
  + Blätter: Boolesche Konstanten 0/1;
  + Innere Knoten: markiert mit Variablen, genau zwei Nachfolger (über 0-/1-Kante)

- Terminalknoten stellen konstante Funktion 0 bzw. 1 dar

- Innere Knoten interpretiert als:

$
\begin{gathered}
  f(x) = {\text{if x = 1 then }}{{\text{f}}_{\text{1}}}{\text{ else }}{{\text{f}}_{\text{0}}} = \left\{ {\begin{array}{*{20}{c}}
  {{f_1},x = 1} \\ 
  {{f_0},x = 0} 
\end{array}} \right. \hfill \\
  f(x) = (x \Rightarrow {f_1}) \vee (x \Rightarrow {f_0}) \hfill \\ 
\end{gathered}
$

- Es gibt eine Variablenordnung ≺ bei der Entwicklung von BDDs

- Größe des BDDs kann stark von der gewählten Variablenordnung ≺ abhängen

## Erzeugung

[INFO] Syntax für Ausdrucksevaluierung (Shanon Zerlegung)
```
(a+b+c)|a
```

[DEFINITION] Shanon Zerlegung
$
\begin{gathered}
  f(a,b,c,..):(a,b,c,..) \to y \hfill \\
  \operatorname{var} (f) = \{ a,b,c,..\}  \hfill \\
  f{|_{x \in \operatorname{var} (f)}} = {f_0}{|_{x = 0}} \vee {f_1}{|_{x = 1}} \hfill \\ 
\end{gathered}
$

Im folgenden Beispiel kann ein Funktionsausdruck ε nach einer Variable *x* ∈ *vars*(ε) zerlegt werden:

[CODE] Shanon Zerlegung { eval:shanon; label:"shanon1"; lock:10 }
```
(a+b+c)|a
```

Für folgende Aufgabe kann nachfolgende Graphenvisualisierung genutzt werden.

[EXERCISE]

Leite für die Funktion `f(a,b,c,d)=!a*!b*!c+!a*b*!c+a*b*!c+a*!b*c*d+!a*b*c` einen BDD ab.

1. Auswertereihenfolge der Variablen ist `[a,b,c,d]`
2. Auswertereihenfolge der Variablen ist `[d,b,a,c]`
3. Auswertereihenfolge der Variablen ist `[d,c,b,a]`

Wie unterscheiden sich die Bäume? Gibt die Höhe (Anzahl der Ebenen) und die Anzahl der Knoten an.

[EXERCISE]

[INPUT] Lösung

[INFO] BDD Syntax
- `<node id> : <var name> ( <left id>|0 , <right id>|1 )` erzeugt den Wurzelknoten oder einen inneren Knoten des Graphens mit einem beliebigen Index *id*, z.B. `1` oder `A1`. Der Variablename ergibt sich aus der aktuellen Shanonzerlegung sowie und die Nachfolgeknoten. 
- `<node id>:1` ist Blattknoten mit dem Booleschen Wert 1
- Es können mehrere Bäume in einem Diagramm nebeneinander dargestellt werden. Unterscheidung der Bäume z.B. mit verschiedenen Indexbuchstaben A,B,.., d.h., Baum 1 `A1,A2,..`, Baum 2 `B1,B2,..` usw.
- Mehrere Knotendefinitionen (auch aus verschiedenen Bäumen) können in einer Teile durch ein Semikolon `;` getrennt angegeben werden.

[GRAPH] BDD Konstruktion { eval:createBDD; arg:"text" }
```
1:a(2,3)
2:b(4,11)
3:c(10,11)
4:c(11,10)
10:0
11:1
```

## Reduktion

- BDDs können mit einfachen Regeln minimiert (reduziert) werden: **Reduced Ordered BDD**
  1. Bedingung: Variable des Elternknotens muss kleiner sein als Variable beider Kindknoten
  2. Auf jedem Pfad kommt jede Variable höchstens einmal vor

- Reduktionen:
  1. Isomorphe Teilbäume dürfen nicht mehrfach vorkommen, mehrere Vorkommen werden auf einen Teilbaum reduziert.
  2. Gleiche Nachfolger: Knoten *f* mit *f*~0~=*f*~1~ werden gelöscht und Kanten, die auf *f* zeigen auf *f*~0~ (bzw. *f*~1~) umgebogen.

[GRAPH] BDD Reduktion { eval:createBDD; arg:"text" }
```
A1:x(A2,A3) ; B1:x(B2,B2) ; C1:y(C2,C3)
A2:y(A4,A5) ; B2:y(B3,B4) ; C2:1
A3:y(A4,A5) ; B3:1        ; C3:0
A4:1        ; B4:0
A5:0
```

[QUESTION] 
Welche Reduktionen wurden im obigen Beispiel durchgeführt (*A* ⇒ *B* ⇒ *C*)?

[INPUT]

Reduziere folgenden BDD und füge ihn zu dem nicht reduzierten Baum:

[GRAPH] Aufgabe BDD Reduktion { eval:createBDD; }
```
A1:a(A2,A3)
A2:b(A4,A5)
A3:b(A6,A1001)
A4:c(A1000,A1001)
A5:c(A1000,A1001)
A6:c(A1000,A1001)
A1000:0
A1001:1
```

---
Autor: Stefan Bosse<br>
Version: 2.12.2019 Draft!<br>
Tutorial 2

Interactive NoteBook (c) Dr. Stefan Bosse

Boolesche Funktionen und Binäre Entscheidungsbäume

Name
Matrikelnummer

Einführung

Lese Folien 27 bis 65 hier Modul C.

Boolesche Funktionen

Eine boolesche Funktion f(a,b,c,..) bildet eine Menge von n Eingabevariablen auf m Ausgabevariablen ab:

\[ f(x_1,x_2,x_3,..,x_n) : B^n \rightarrow B^m \]

Boolesche Funktionen bestehen aus Variablen, Verknüpfungen, und Werten.

Information. Syntax Boolesche Algebra

Ausdrücke bestehen aus Operatoren, Variablen, und Werten
Disjunktion (Oder-Verknüpfung): +
Konjunktion (Und-Verknüpfung): *
Negation: !
Variablen: Jeder Namensbezeichner mit Buchstaben
Werte: 0,1
Bindung von Ausdrücken: ( expr )
Funktion: y=expr
Shanonzerlegung nach einer Variable x: (expr)|x

Im ersten Beispiel können Boolesche Funktionen algebraisch und symbolisch automatisch evaluiert und vereinfacht werden:

Boolesche Funktionsevaluierung (Symbolische Vereinfachung)

(a+b)*(a+1)

▸

✗

Aufgabe.

Vereinfache folgende Ausdrücke mit obigen Evaluator:
1. !a*b*!c+!a*b*c+a*b
2. z+(x+y)*(z+x)
3. z+(x+y)*(z+x)*(x+y)
4. z+(x+y)*(z+x)*x
5. z+(x+y)*(z+x)*(x+1)

Welche Regeln der Booleschen Algebra werden durch den automatischen Evaluator angewendet? Welche fehlen? Finde es heraus!

Lösung

Im nächsten Beispiel kann aus einer booleschen Funktion eine Funktionstabelle erstellt werden.

Boolesche Funktionsevaluierung (Erzeugung Tabelle)

a+b

▸		✗

Aufgabe.

Teste ob die automatische Reduktion korrekt ist anhand der vorherigen Aufgabenbeispiele und dem Vergleich über die Funktionstabelle. Dazu kann im Tabellengenerator die Syntax y1=a+b+c y2=a+b verwendet werden (multiple BF, je eine BF pro Zeile).

Erstelle im nächsten Schritt die DNF und KNF Terme in folgender Funktionstabelle (jeweils entsprechend für y=1/0 Zeilen):

Hier kann die Funktion auf Korrektheit getestet werden:

Test 1

▸		✗

Entscheidungsbäume

Einführung

Lese Folien 66 bis 78 hier Modul C.

1986 von R. Bryant vorgeschlagen
Eine Boolesche Funktion f wird repräsentiert als gerichteter azyklischer Graph (DAG):
- Blätter: Boolesche Konstanten 0/1;
- Innere Knoten: markiert mit Variablen, genau zwei Nachfolger (über 0-/1-Kante)
Terminalknoten stellen konstante Funktion 0 bzw. 1 dar
Innere Knoten interpretiert als:

\[ \begin{gathered} f(x) = {\text{if x = 1 then }}{{\text{f}}_{\text{1}}}{\text{ else }}{{\text{f}}_{\text{0}}} = \left\{ {\begin{array}{*{20}{c}} {{f_1},x = 1} \\ {{f_0},x = 0} \end{array}} \right. \hfill \\ f(x) = (x \Rightarrow {f_1}) \vee (x \Rightarrow {f_0}) \hfill \\ \end{gathered} \]

Es gibt eine Variablenordnung ≺ bei der Entwicklung von BDDs
Größe des BDDs kann stark von der gewählten Variablenordnung ≺ abhängen

Erzeugung

Information. Syntax für Ausdrucksevaluierung (Shanon Zerlegung)

(a+b+c)|a

Definition 1. Shanon Zerlegung

\[ \begin{gathered} f(a,b,c,..):(a,b,c,..) \to y \hfill \\ \operatorname{var} (f) = \{ a,b,c,..\} \hfill \\ f{|_{x \in \operatorname{var} (f)}} = {f_0}{|_{x = 0}} \vee {f_1}{|_{x = 1}} \hfill \\ \end{gathered} \]

Im folgenden Beispiel kann ein Funktionsausdruck ε nach einer Variable x ∈ vars(ε) zerlegt werden:

Shanon Zerlegung

(a+b+c)|a

▸

✗

Für folgende Aufgabe kann nachfolgende Graphenvisualisierung genutzt werden.

Aufgabe.

Leite für die Funktion f(a,b,c,d)=!a*!b*!c+!a*b*!c+a*b*!c+a*!b*c*d+!a*b*c einen BDD ab.

Auswertereihenfolge der Variablen ist [a,b,c,d]
Auswertereihenfolge der Variablen ist [d,b,a,c]
Auswertereihenfolge der Variablen ist [d,c,b,a]

Wie unterscheiden sich die Bäume? Gibt die Höhe (Anzahl der Ebenen) und die Anzahl der Knoten an.

Lösung
Information. BDD Syntax

<node id> : <var name> ( <left id>|0 , <right id>|1 ) erzeugt den Wurzelknoten oder einen inneren Knoten des Graphens mit einem beliebigen Index id, z.B. 1 oder A1. Der Variablename ergibt sich aus der aktuellen Shanonzerlegung sowie und die Nachfolgeknoten.
<node id>:1 ist Blattknoten mit dem Booleschen Wert 1
Es können mehrere Bäume in einem Diagramm nebeneinander dargestellt werden. Unterscheidung der Bäume z.B. mit verschiedenen Indexbuchstaben A,B,.., d.h., Baum 1 A1,A2,.., Baum 2 B1,B2,.. usw.
Mehrere Knotendefinitionen (auch aus verschiedenen Bäumen) können in einer Teile durch ein Semikolon ; getrennt angegeben werden.

BDD Konstruktion

1:a(2,3)
2:b(4,11)
3:c(10,11)
4:c(11,10)
10:0
11:1

▸		✗

Reduktion

BDDs können mit einfachen Regeln minimiert (reduziert) werden: Reduced Ordered BDD
1. Bedingung: Variable des Elternknotens muss kleiner sein als Variable beider Kindknoten
2. Auf jedem Pfad kommt jede Variable höchstens einmal vor

Reduktionen:
1. Isomorphe Teilbäume dürfen nicht mehrfach vorkommen, mehrere Vorkommen werden auf einen Teilbaum reduziert.
2. Gleiche Nachfolger: Knoten f mit f₀=f₁ werden gelöscht und Kanten, die auf f zeigen auf f₀ (bzw. f₁) umgebogen.

BDD Reduktion

A1:x(A2,A3) ; B1:x(B2,B2) ; C1:y(C2,C3)
A2:y(A4,A5) ; B2:y(B3,B4) ; C2:1
A3:y(A4,A5) ; B3:1        ; C3:0
A4:1        ; B4:0
A5:0

▸		✗

Frage. Welche Reduktionen wurden im obigen Beispiel durchgeführt (A ⇒ B ⇒ C)?

Reduziere folgenden BDD und füge ihn zu dem nicht reduzierten Baum:

Aufgabe BDD Reduktion

A1:a(A2,A3)
A2:b(A4,A5)
A3:b(A6,A1001)
A4:c(A1000,A1001)
A5:c(A1000,A1001)
A6:c(A1000,A1001)
A1000:0
A1001:1

▸		✗

Autor: Stefan Bosse
Version: 2.12.2019 Draft!
Tutorial 2