type formule =
| Var of string
| Neg of formule
| Et of formule * formule
| Ou of formule * formule
;;

let ex = Et(Var "p", Neg(Ou(Var "q", Var "r")));;


let rec string_of_formule formule = match formule with
| Var (s) -> "s"
| Neg (f) -> "neg" ^ (string_of_formule f)
| Et (f1,f2) -> (string_of_formule f1) ^ "et" ^ (string_of_formule f2)
| Ou (f1,f2) -> (string_of_formule f1) ^ "ou" ^ (string_of_formule f2)
;;

let rec reunion l1 l2 = match (l1,l2) with
| ([],[]) -> []
| l1,[] -> l1
| ([],l2) -> l2
| t1::q1,l2 -> if not (List.mem t1 l2) then t1::(reunion q1 l2)
else (reunion q1 l2)
;;

let rec list_of_vars formule acc = match formule with
| Var x -> reunion [x] acc
| Neg (f) -> list_of_vars f acc 
| Et (f1,f2) -> reunion (list_of_vars f1 acc) (list_of_vars f2 acc) 
| Ou (f1,f2) -> reunion (list_of_vars f1 acc) (list_of_vars f2 acc) 
;;

let rec eval_formule formule machin = match formule with
| Var x -> List.assoc x machin == true
| Neg (f) -> eval_formule f machin == false
| Et (f1,f2) -> (eval_formule f1 machin) && (eval_formule f2 machin)
| Ou (f1,f2) -> (eval_formule f1 machin) || (eval_formule f2 machin)
;;
let ex2 = Et(Var "p", Neg(Ou(Var "q", Var "r")));;
let ex3 = [("p",true); ("q",false); ("r", true)];;

let add_to_all a truc = List.map (function l0 ->a::l0) truc;;
let rec affectation_vars sl = match sl with
| [] -> []
| t::q -> (affectation_vars q)@[(add_to_all t q)@(add_to_all (t,false))]
;;