## 3 The Proposed Approach
### Cause-Effect Graph
#### 3.2.2 Robdd  
1. BDD For a Boolean function \((f(x_{1},x_{2},\ldots,x_{n}))\) from \(\{0,1\}^{n}\) to \(\{0,1\}\), a binary decision diagram (BDD) can be constructed to represent \(f(x_{1},x_{2},\ldots,x_{n})\) and a family of Boolean functions \((\#f(x_{1},x_{2},x_{3},\ldots,x_{n}))\) related to \(f(x_{1},x_{2},\ldots,x_{n})\) with a directed acyclic graph. The graph satisfies the following five points: 1. Nodes in the BDD are divided into three categories: root nodes, final nodes, and internal nodes; 2. There are only two end nodes, marked as 0 and 1. Let \(t.val\) denote the value associated with an end node (\(t\)); \(t.val\in\{0,1\}\) must hold for the \(t\), denoting the Boolean constants 0 and 1; 3. Each internal node (\(u\)) is associated with a quaternion property: \((f^{u},var,low,high)\), where \(f^{u}\) denotes the Boolean function corresponding to node \(u\) and \(f^{u}\in\#_{\pi}f(x_{1},x_{2},\ldots,x_{n})(f^{u}=f(x_{1},x_{2},\ldots,x_{n})\)  if u is the root node; \(var\) denotes the marker variable of node \(u\), where low denotes the child of node \(u\) when \(u.var=0\) (indicating that the marker variable (\(var\)) of node \(u\) takes a value of 0), and high denotes the child of node \(u\) when \(u.var=1\) (indicating that the marker variable (\(var\)) of node \(u\) takes a value of 1);4 Each internal node has two output branching arcs that connect the node to its two child nodes. The arc connecting node \(u\) to \(u.low\) is called a 0-edge, and the arc connecting node \(u\) to \(u.high\) is called a 1-edge;
5 Each variable in the Boolean function \(f(x_{1},x_{2},\ldots,x_{n})\) appears once, at most, in any directed path in the BDD. 2. ObDD For a Boolean function \((f(x_{1},x_{2},\ldots,x_{n}))\) from \(\{0,1\}^{n}\) to \(\{0,1\}\) and a given variable order \((\pi)\), a BDD representing \(f(x_{1},x_{2},\ldots,x_{n})\) and the family of Boolean functions \(\#f(x_{1},x_{2},x_{3},\ldots,x_{n})\) is said to be an ordered binary decision diagram (OBDD) of \(f(x_{1},x_{2},\ldots,x_{n})\) if the variables on any directed path all appear in the order specified by the \(\pi\). The node \(u\) in each OBDD represents the Boolean function \(f^{u}\) from \(\{0,1\}^{n}\) to \(\{0,1\}\), where \(u\) satisfies the following two points: 1 If \(u\) is a final node, then \(f^{u}=u.val\); 2 If \(u\) is an internal node, then the following equation is used: \[f^{u}=u.var\cdot f^{u.high}+(u.var)^{\prime}\cdot f^{u.low}=u.var\cdot f^{u}_{|u.var=1}+(u.var)^{\prime}\cdot f^{u}_{|u.var=0}\] (7) where \(f^{u}_{|u.var=1}\) and \(f^{u}_{|u.var=0}\) denote the functions obtained after the variable \(u.var\) in \(f^{u}\) takes the values 1 and 0, respectively (i.e., the Boolean functions corresponding to the children \(u.high\) and \(u.low\) of node \(u\)). Clearly, in the decomposition process, choosing a different variable order will generally result in a different decomposition result for \(f^{u}\). Therefore, different orders of variables lead to different OBDDs for the same function. For example, Figure 4 shows the OBDD of the Boolean function \(f(x_{1},x_{2},x_{3})=(x_{1}+x_{2})\cdot x_{3}\) under the variable order \(\pi:x_{1}<x_{2}<x_{3}\). 3. ROBDD An OBDD is a reduced ordered binary decision diagram (ROBDD) if the internal nodes in the OBDD satisfy the following two conditions: 1 For each internal node (\(u\)), \(u.low\
eq u.high\); 2 For different internal nodes (\(u\) and \(v\)) that satisfy \(u.var=v.var\), \(u.low\
eq v.low\) or \(u.high\
eq v.high\) holds. An OBDD that does not satisfy the above conditions can be simplified to an ROBDD by repeatedly applying the following simplification rules: **Rule 1** (Deletion Rules). : _For node \(u\) in the OBDD, if \(u.low=u.high\), node \(u\) is deleted and the parent node of node \(u\) is directly connected to the node corresponding to \(u.low\)._ **Rule 2** (Merging Rules).