* In def 3.1 on p. 14, GS&V define `s` updated with \[[not φ]] as:
- > { i &elem; s | i does not subsist in s[φ] }
+ > { i ∈ s | i does not subsist in s[φ] }
where `i` *subsists* in <code>s[φ]</code> if there are any `i'` that *extend* `i` in <code>s[φ]</code>.
- Here's how we can represent that:
+------ wrong....
- <pre><code>bind_set s (fun (r, h) ->
- let u = unit_set (r, h)
- in let descendents = u >>= \[[φ]]
- in if descendents = empty_set then u else empty_set
- </code></pre>
+ In our framework, we just have to convert the operation <code>>>= \[[ψ]]</code> into another operation <code>>>= \[[ψ]] >>= neg</code>, where `neg` flips the truth-value of all the `bool dpm`s it operates on:
+ type clause_op = bool dpm -> bool dpm set;;
+
+ let negate_op (phi : clause_op) : clause_op =
+ let neg : clause_op = fun one_dpm ->
+ unit_set (fun (r, h) ->
+ let (truth_value, r', h') = one_dpm (r, h)
+ in (not truth_value, r', h'))
+ in fun one_dpm -> bind_set (phi one_dpm) neg;;
+
+
+ let negate_op (phi : clause_op) : clause_op =
+ fun one_dpm ->
+ if blah
+ then unit_set one_dpm
+ else empty_set
+------
+
+
+* Representing \[[and φ ψ]] is simple:
+
+ let and_op (phi : clause_op) (psi : clause_op) : clause_op =
+ fun one_dpm -> bind_set (phi one_dpm) psi;;
+
+* We define the other connectives in terms of `not` and `and`:
+
+ let or_op (phi : clause_op) (psi : clause_op) =
+ negate_op (and_op (negate_op phi) (negate_op psi))
+
+ let if_op (phi : clause_op) (psi : clause_op) =
+ negate_op (and_op phi (negate_op psi));;
+
+* Now let's test everything we've developed:
+
+ type entity = Bob | Carol | Ted | Alice;;
+ let domain = [Bob; Carol; Ted; Alice];;
+ type assignment = char -> int;;
+ type store = entity list;;
+ type 'a dpm = assignment * store -> 'a * assignment * store;;
+ let unit_dpm (x : 'a) : 'a dpm = fun (r, h) -> (x, r, h);;
+ let bind_dpm (u: 'a dpm) (f : 'a -> 'b dpm) : 'b dpm =
+ fun (r, h) ->
+ let (a, r', h') = u (r, h)
+ in let u' = f a
+ in u' (r', h')
+
+ type 'a set = 'a list;;
+ let empty_set : 'a set = [];;
+ let unit_set (x : 'a) : 'a set = [x];;
+ let bind_set (u : 'a set) (f : 'a -> 'b set) : 'b set =
+ List.concat (List.map f u);;
+
+ type clause_op = bool dpm -> bool dpm set;;
+
+ let get (var : char) : entity dpm =
+ fun (r, h) ->
+ let obj = List.nth h (r var)
+ in (obj, r, h);;
+
+ let lift_predicate (f : entity -> bool) : entity dpm -> clause_op =
+ fun entity_dpm ->
+ let eliminator = fun (truth_value : bool) ->
+ if truth_value = false
+ then unit_dpm false
+ else bind_dpm entity_dpm (fun e -> unit_dpm (f e))
+ in fun one_dpm -> unit_set (bind_dpm one_dpm eliminator);;
+
+ let lift_predicate2 (f : entity -> entity -> bool) : entity dpm -> entity dpm -> clause_op =
+ fun entity1_dpm entity2_dpm ->
+ let eliminator = fun (truth_value : bool) ->
+ if truth_value = false
+ then unit_dpm false
+ else bind_dpm entity1_dpm (fun e1 -> bind_dpm entity2_dpm (fun e2 -> unit_dpm (f e1 e2)))
+ in fun one_dpm -> unit_set (bind_dpm one_dpm eliminator);;
+
+ let new_peg_and_assign (var_to_bind : char) (d : entity) : bool -> bool dpm =
+ fun truth_value ->
+ fun (r, h) ->
+ let new_index = List.length h
+ in let h' = List.append h [d]
+ in let r' = fun var ->
+ if var = var_to_bind then new_index else r var
+ in (truth_value, r', h')
+
+ let exists var : clause_op = fun one_dpm ->
+ List.map (fun d -> bind_dpm one_dpm (new_peg_and_assign var d)) domain
+
+ (* negate_op, and_op, or_op, and if_op as above *)
+
+ let (>>=) = bind_set;;
+ let initial_set = [fun (r,h) -> (true,r,h)];;
+
+ let initial_r = fun var -> failwith ("no value for " ^ (Char.escaped var));;
+ let run dpm_set =
+ let bool_set = List.map (fun one_dpm -> let (value, r, h) = one_dpm (initial_r, []) in value) dpm_set
+ in List.exists (fun truth_value -> truth_value) bool_set;;
+
+ let male obj = obj = Bob || obj = Ted;;
+ let wife_of x y = (x,y) = (Bob, Carol) || (x,y) = (Ted, Alice);;
+ let kisses x y = (x,y) = (Bob, Carol) || (x,y) = (Ted, Alice);;
+ let misses x y = (x,y) = (Bob, Carol) || (x,y) = (Ted, Carol);;
+ let getx = get 'x';;
+ let gety = get 'y';;
+
+ (* "a man x has a wife y" *)
+ let antecedent = fun one_dpm -> exists 'x' one_dpm >>= lift_predicate male getx >>= exists 'y' >>= lift_predicate2 wife_of getx gety;;
+
+ (* "if a man x has a wife y, x kisses y" *)
+ run (initial_set >>= if_op antecedent lift_predicate2 kisses getx gety);;
+ (* Bob has wife Carol, and kisses her; and Ted has wife Alice and kisses her; so this is true! *)
+
+ (* "if a man x has a wife y, x misses y" *)
+ run (initial_set >>= if_op antecedent lift_predicate2 misses getx gety);;
+ (* Bob has wife Carol, and misses her; but Ted misses only Carol, not his wife Alice; so this is false! *)