Since you're not increasing the number of variables, it seems to me that the problem of finding the initial Boolean formula (or an even simpler version of it) is fairly straightforward. Have you done any tests along these lines?