create CNF using shannon decomposition

Question

Transform the formula for an arbitrary variable ordering into CNF:

((a|c|a|c<->(d|d)&c)->(c|b|b|a->!b|(d<->a)))

is it correct what I have done so far? (I don't know how to continue)

Answer 1

You have applied the Shannon decomposition in an incorrect way. Look the following are the correct rules:

    for computing DNF

           phi = a&phi[a<-true] | !a&phi[a<-false]

    for computing CNF

           phi = (a->phi[a<-true]) & (!a->phi[a<-false])
               = (!a | phi[a<-true]) & (a | phi[a<-false])

However, you mixed the two rules up and did the following which is not correct:

    phi = (a | phi[a<-true]) & (!a | phi[a<-false])

Answer 2

1. In the fourth formula, you seem to have transformed d <-> false to d. It should be ¬d.
2. The signs in front of variable a are flipped. It should be (a → positive cofactor) & (¬a → negative confactor) = (¬a | positive cofactor) & (a | negative confactor)
3. There are parenthesis missing. & binds stronger than |. If you just write x | y & ¬x | y, then that's not the if-then-else you want to express. You should write (x | y) & (¬x | y)
4. Why did you stop? Try to continue with simplification like this: X→true = true, X→false = ¬X, true→X=X, false→X=true