Melding ZDDs
Let $F, G$ be ZDDs in the same universe $U = \{1,...,n\}$. How do we construct their union, $F \cup G$?
Case 1: If one family is the empty or unit family then the question is easy, and these special cases also hint at the general solution. In particular, if $G = \epsilon$ (represented by the single node $\top$) and $F \ne \emptyset$ and $F \ne \epsilon$ (so $F$ contains a nonterminal node) then, if it does not already exist, we add a dotted edge so that we can travel from the root of $F$ to the $\top$ by following the LO branch every time. In other words, we start from the root of $F$, follow dotted lines as far as possible, and then either do nothing if we end up at $\top$ or reroute the last dotted line we followed to $\top$.
Case 2: Suppose both $F$ and $G$ have a root node labelled $v$ for some $v \in [1..n]$. Let $F_0, F_1$ be the ZDDs on the LO and HI edges respectively. Define $G_0, G_1$ similarly:
Recall $F_0, F_1$ partition the families of sets of $F$ on whether they contain $v$ or not, and similarly for $G_0, G_1$, hence our solution must be:
where we recursively find $H_0 = F_0 \cup G_0$ and $H_1 = F_1 \cup G_1$.
Case 3: Suppose $F$ has root node $v$ and $G$ has root node $w$, and $v \lt w$. Let $F_0, F_1$ be the LO and HI children of the root node of $F$ respectively.
Now $w$ is the smallest integer contained in any set of $G$, hence no set in $G$ contains $v$. Thus $F \cup G$ is:
where $H = F_0 \cup G$. Just like the easy special case $G = \epsilon$, whenever $w \gt v$, we do nothing but follow the dotted line. In fact, by defining $\top$ to be larger than every integer, we see how this special case is related.
We have described all cases of a topdown recursive algorithm for constructing the union of any two families. Observe we avoid creating nodes whose HI edges point to $\bot$, and we avoid duplicating any nodes.
The above arguments hold for any binary operation $\diamond$ that distributes over union satisfying $F \diamond G \subseteq F \cup G$, namely the output lies within the union of the inputs.
As $F\cap G, F \setminus G , F\oplus G$ all lie within $F\cup G$, for these operations the above arguments apply when $F, G$ have root nodes with the same label. Similarly, we do nothing but follow the dotted line when the root $w$ of $G$ is greater than the root $v$ of $F$. The only difference is in the handling of $F_1$. For intersections, since this represents the sets of $F$ containing $v$ and since no set in $G$ contains $v$, we lop off the entire branch leaving only the ZDD $F_0\cap G$. For the difference and symmetric difference, as in the union, we leave $F_1$ intact as it represents sets of $F$ not present in $G$.
One more wrinkle: the case $v \gt w$ is symmetric except for the asymmetric difference operation. We have $F\setminus G = F \setminus G_0$ in this case.
Let us summarize the nonterminal cases. Let $\diamond$ be one of $\cup, \cap, \setminus, \oplus$. We reuse the above notation, that is, $F, G$ are nontrivial ZDDs with roots labelled $v, w$ respectively, and $F_0, F_1$ are the LO and HI children of $v$ respectively and $G_0, G_1$ are similarly defined.
When $v = w$, then $F \diamond G$ is recursively defined by:
where $H_0 = F_0 \diamond G_0, H_1 = F_1 \diamond G_1$.
When $v \lt w$, let $H = F_0 \diamond G$. If $\diamond = \cap$ then $F \cap G = H$, otherwise $F \diamond G$ is:
Lastly, when $v \gt w$ the cases are symmetric except when $\diamond = \setminus$, whence $F \setminus G = F \setminus G_0$.
Join, meet, and other operations are less straightforward. Let us investigate the join operation. Suppose we wish to compute $H = F \sqcup G$ where $F$ and $G$ have the same label. Again, denoting the LO and HI children with 0 and 1 subscripts, we have:

$H_0 = F_0 \sqcup G_0$

$H_1 = (F_0 \sqcup G_1) \cup (F_1 \sqcup G_0) \cup (F_1 \sqcup G_1)$
which lead to algorithms similar to the above, except the $H_1$ recursion branches out and can be computed in different ways. By distributivity:
$H_1 = ((F_0 \cup F_1) \sqcup G_1) \cup (F_1 \sqcup G_0) = (F_1 \sqcup (G_0 \cup G_1)) \cup (F_0 \sqcup G_1)$
Thus we have 3 methods to compute $H_1$. Depending on the inputs, one alternative may significantly outperform the others.