How can I implement a predicate which converts a propositional formula to a normal form?

I am trying to implement an unfold predicate which takes a propositional formula and returns one where the only logical operators are conjunction, disjunction and negation.

Code:

:- op(1060, yfx, <->). 
:- op(1050, yfx, <-). 
:- op(800, yfx, xor).
:- op(600, yfx, v).  
:- op(400, yfx, &). 
:- op(200, fy, ¬). 

define((F xor G),  ¬ (F <-> G)).
define((F <-> G), (F -> G) & (F <- G)). 
define((F <- G), (G -> F)).
define((F -> G), ¬ F v G).

% Base case: atomic formula
unfold(A, A) :- atom(A).
unfold(¬ A, NA) :- unfold(A, UA), define(UA, NA1), NA = ¬ NA1.
unfold(A & B, C) :- unfold(A, UA), unfold(B, UB), define(UA, C1), define(UB, C2), C = C1 & C2.
unfold(A v B, C) :- unfold(A, UA), unfold(B, UB), define(UA, C1), define(UB, C2), C = C1 v C2.
unfold(A xor B, C) :- unfold(A, UA), unfold(B, UB), define((UA xor UB), C).
unfold(A <-> B, C) :- unfold(A, UA), unfold(B, UB), define((UA <-> UB), C).
unfold(A <- B, C) :- unfold(A, UA), unfold(B, UB), define((UA <- UB), C).
unfold(A -> B, C) :- unfold(A, UA), unfold(B, UB), define((UA -> UB), C).

However, that doesn't work. At first I missed the base case, then I added it but I only get false. For example, this query should return:

-? unfold( p <-> q & ¬ r, G ).
G= ( ¬p v ¬q & ¬r) & ( ¬ (q & ¬ r) v p). 

Thank you for any guidance or help.

When I run your program, it fails when trying unfold(~r, NA), because it fails on define(r, NA1). It seems that define for an atom hasn't been written. I use SWI-PROLOG and am using gtrace for debugging; that's how I found the fault.

Solution: write define/2 to handle atoms. There may of course be other missing clauses.