Constraint Algorithm (Shannon normal form)

Question

Above is given formula for constraint algorithm in exercise sheet 3 and variable ordering is a<b<c<d, I have found my formula Shannon normal form are different with given red highlighted and when compute them by "Teaching Tools" the green highlighted also there are as same as my result, please could someone clarify why the provided result in exercise sheet are different and why?

Thanks in advance!

Answer 1

Well, you must have made some mistakes when computing the normal form since it is incorrect. Here is how the computation is done for the first formula by a step-by-step Shannon decomposition on the variables d,c,b,a:

    a&!b&!c&!d | c&!a&!d | d&!a
    = (d ? !a
         : a&!b&!c | c&!a )
    = (d ? !a
         : (c ? !a 
              : a&!b ))
    = (d ? !a
         : (c ? !a 
              : a&!b ))
    = (d ? !a
         : (c ? !a 
              : (b ? false 
                   : a )))
    = (d ? (a ? false
              : true)
         : (c ? (a ? false
                   : true)
              : (b ? false
                   : (a ? true
                        : false))))

This is what the tool computed, and it can also be read from the corresponding BDD using the same variable ordering:

The same way, you can compute the SNF for the other formula.