(* Convertiti o expresie booleana la forma normala conjunctiva *)

type boolexp =
  | Id of string
  | Not of boolexp
  | And of boolexp * boolexp
  | Or of boolexp * boolexp

let rec push_neg = function
  | Not ne -> (match ne with
        Not e1 -> push_neg e1
      | And (e1, e2) -> Or (push_neg (Not e1),  push_neg (Not e2))
      | Or (e1, e2) -> And (push_neg (Not e1),  push_neg (Not e2))
      | e -> Not e)
  | And (e1, e2) -> And (push_neg e1, push_neg e2)
  | Or (e1, e2) -> Or (push_neg e1, push_neg e2)
  | e -> e
    
let rec push_or = function
  | And (e1, e2) -> And (push_or e1, push_or e2)
  | Or (e1, e2) -> let re2 = push_or e2 in (
    match push_or e1 with
      | And (f1, f2) -> And (push_or (Or (f1, re2)), push_or (Or (f2, re2)))
      | re1 -> (match re2 with
          | And (g1, g2) -> And (push_or (Or (re1, g1)), push_or (Or (re1, g2)))
          | _ -> Or (re1, re2)))
  | e -> e

let cnfconv e = push_or (push_neg e)

let e = cnfconv (Or(And(Id "x1", Id "y1"), Or(And(Id "x2", Id "y2"), Or(And(Id "x3", Id "y3"), And (Id "x4", Id "y4")))));;

This document was generated using caml2html