« Return to Thread: Disjunctive Normal Form

Disjunctive Normal Form

by Jim Burton :: Rate this Message:

Reply to Author | View in Thread

I am trying to rewrite sentences in a logical language into DNF, and wonder if someone would point out where I'm going wrong. My dim understanding of it is that I need to move And and Not inwards and Or out, but the function below fails, for example:
       
> dnf (Or (And A B) (Or (And C D) E))
And (Or A (And (Or C E) (Or D E))) (Or B (And (Or C E) (Or D E)))
       
       
data LS = Var | Not LS | And LS LS | Or LS LS
--convert sentences to DNF
dnf :: LS -> LS
dnf (And (Or s1 s2) s3) = Or (And (dnf s1) (dnf s3)) (And (dnf s2) (dnf s3))
dnf (And s1 (Or s2 s3)) = Or (And (dnf s1) (dnf s2)) (And (dnf s1) (dnf s3))
dnf (And s1 s2)         = And (dnf s1) (dnf s2)
dnf (Or s1 s2)          = Or (dnf s1) (dnf s2)
dnf (Not (Not d))       = dnf d
dnf (Not (And s1 s2))   = Or (Not (dnf s1)) (Not (dnf s2))
dnf (Not (Or s1 s2))    = And (Not (dnf s1)) (Not (dnf s2))
dnf s                   = s
       
Thanks,
       
Jim

 « Return to Thread: Disjunctive Normal Form