Shannon Normal Form

Question

Hi, I tried to submit my solution for the SNF for 

a&b&c&d|c&d&!b|d&!c|!d

I tried to input

d ? (c ? (b ? a : true) : true) : true

but I got an error (not in SNF)

However,

d ? (c ? (b ? (a ? true : false) : true) : true) : true

got accepted as a correct solution.

Shouldn't my first solution also be correct? SNF is defindes as a representation of a boolean function only using IF THEN ELSE and 1, 0 (VRS-03 page 4).

Answer 1

It depends what you mean here with "correct". The two formulas are obviously equivalent to each other and both are only using ITE operations, variables and the Boolean constants. However, SNF as defined in the tool (and the slides) continues making case distinctions even when a variable is given, so you must not end with a variable "a" and should rather create its SNF as (a ? true : false). This is done to make SNF more comparable to BDDs which also make case distinctions for variables. You may have a more liberal definition that still will generate equivalent formulas, but then the canonical normal form property would be lost also.

Comments

Alright, thanks. I used the definition of SNF on page 4 of presentation #3 and therefore thought the SNF only has to satisfy the 2 conditions shown there, which are only using IF THEN ELSE and TRUE, FALSE. I think it might be helpful to clarify this in the slides.

---

I agree and will make a note about that on the slides!