exist algorithm

Question

φ = b&c&!d|c&d|c&!a&!b&!d

x ={b,d}

after applying exist algorithm i got final term like this:

Apply(v,d->n23|n23 ,d->n24|no)

after this how to proceed? suggestion please

Answer 1

Since you have arrived at the final term, you proceed by computing the Apply algorithm.

The procedure is the same as what you normally do in the Apply algorithm. You will create a new node taking the maximum of both labels of the given nodes. In the example above, the label of both nodes is the same. And then recursively call the Apply algorithm again to find the co-factors for this node.

Apply(v, d->n23|n23, d->n24|n0) = (d? Apply(v, n23, n24) : Apply(v, n23, n0))

In this part 'Apply(v, n23, n0)' there is a leaf node so you can immediately evaluate its value, while on the other part 'Apply(v, n23, n24)' you have to again continue the Apply algorithm.