DouKaku?

#light
let rec satisfy prev bs cmds =
    match bs, cmds with
    | b::[], _     -> prev b
    | b::bs, cmd::cmds ->
            match cmd with
            | "not" -> satisfy prev ((not b)::bs) cmds
            | "and" -> satisfy ((&&) (prev b)) bs cmds
            | "or"  -> satisfy ((||) (prev b)) bs cmds

let rec all_comb = function
    | 0 -> [[]]
    | n -> [ for res in all_comb (n-1) ->> [true::res;false::res] ]

let get_combs cmds =
    let len = 1 + (List.length (List.filter ((<>) "not") cmds))
    [for bs in all_comb len when satisfy (fun x -> x) bs cmds -> bs]

do get_combs ["and";"or";"not";"and"]
   |> (print_any >> print_newline)