type bool_expr =
 | Var of string
 | Not of bool_expr
 | And of bool_expr*bool_expr
 | Or of bool_expr*bool_expr

let rec value_of key = function
 | [] -> raise (Failure "value_of")
 | (k, v)::tail -> if k = key then v else value_of key tail

let rec eval env =
 function
  | Var (s) -> value_of s env
  | Not (e) -> not (eval env e)
  | And (e1, e2) -> (eval env e1) && (eval env e2)
  | Or (e1, e2) -> (eval env e1) || (eval env e2)

let rec expand =
 let rec append e = function [] -> []
  | head::tail -> (e::head)::append e tail in

 function [] -> []
  | head::[] -> [[(head, true)]; [(head, false)]]
  | head::tail -> (append (head, true) (expand tail))@(append (head, false) (expand tail))

 let table vars expr =
  let rec tbl = function [] -> [] | head::tail -> (head, eval head expr)::tbl tail in

 tbl (expand vars)