hints/assignment_7_hint_6.mdwn

   1
   2 *       In def 3.1 on p. 14, GS&V define `s` updated with \[[not &phi;]] as:
   3
   4         >       { i &isin; s | i does not subsist in s[&phi;] }
   5
   6         where `i` *subsists* in <code>s[&phi;]</code> if there are any `i'` that *extend* `i` in <code>s[&phi;]</code>.
   7
   8 ------ wrong....
   9
  10         In our framework, we just have to convert the operation <code>>>= \[[&psi;]]</code> into another operation <code>>>= \[[&psi;]] >>= neg</code>, where `neg` flips the truth-value of all the `bool dpm`s it operates on:
  11
  12                 type clause_op = bool dpm -> bool dpm set;;
  13
  14                 let negate_op (phi : clause_op) : clause_op =
  15                         let neg : clause_op = fun one_dpm ->
  16                                                 unit_set (fun (r, h) ->
  17                                                         let (truth_value, r', h') = one_dpm (r, h)
  18                                                         in (not truth_value, r', h'))
  19                         in fun one_dpm -> bind_set (phi one_dpm) neg;;
  20
  21
  22                 let negate_op (phi : clause_op) : clause_op =
  23                         fun one_dpm ->
  24                                 if blah
  25                                 then unit_set one_dpm
  26                                 else empty_set
  27 ------
  28
  29
  30 *       Representing \[[and &phi; &psi;]] is simple:
  31
  32                 let and_op (phi : clause_op) (psi : clause_op) : clause_op =
  33                         fun one_dpm -> bind_set (phi one_dpm) psi;;
  34
  35 *       We define the other connectives in terms of `not` and `and`:
  36
  37                 let or_op (phi : clause_op) (psi : clause_op) =
  38                         negate_op (and_op (negate_op phi) (negate_op psi))
  39
  40                 let if_op (phi : clause_op) (psi : clause_op) =
  41                         negate_op (and_op phi (negate_op psi));;
  42
  43 *       Now let's test everything we've developed:
  44
  45                 type entity = Bob | Carol | Ted | Alice;;
  46                 let domain = [Bob; Carol; Ted; Alice];;
  47                 type assignment = char -> int;;
  48                 type store = entity list;;
  49                 type 'a dpm = assignment * store -> 'a * assignment * store;;
  50                 let unit_dpm (x : 'a) : 'a dpm = fun (r, h) -> (x, r, h);;
  51                 let bind_dpm (u: 'a dpm) (f : 'a -> 'b dpm) : 'b dpm =
  52                         fun (r, h) ->
  53                                 let (a, r', h') = u (r, h)
  54                                 in let u' = f a
  55                                 in u' (r', h')
  56
  57                 type 'a set = 'a list;;
  58                 let empty_set : 'a set = [];;
  59                 let unit_set (x : 'a) : 'a set = [x];;
  60                 let bind_set (u : 'a set) (f : 'a -> 'b set) : 'b set =
  61                         List.concat (List.map f u);;
  62
  63                 type clause_op = bool dpm -> bool dpm set;;
  64
  65                 let get (var : char) : entity dpm =
  66                         fun (r, h) ->
  67                                 let obj = List.nth h (r var)
  68                                 in (obj, r, h);;
  69
  70                 let lift_predicate (f : entity -> bool) : entity dpm -> clause_op =
  71                         fun entity_dpm ->
  72                                 let eliminator = fun (truth_value : bool) ->
  73                                         if truth_value = false
  74                                         then unit_dpm false
  75                                         else bind_dpm entity_dpm (fun e -> unit_dpm (f e))
  76                                 in fun one_dpm -> unit_set (bind_dpm one_dpm eliminator);;
  77
  78                 let lift_predicate2 (f : entity -> entity -> bool) : entity dpm -> entity dpm -> clause_op =
  79                         fun entity1_dpm entity2_dpm ->
  80                                 let eliminator = fun (truth_value : bool) ->
  81                                         if truth_value = false
  82                                         then unit_dpm false
  83                                         else bind_dpm entity1_dpm (fun e1 -> bind_dpm entity2_dpm (fun e2 -> unit_dpm (f e1 e2)))
  84                                 in fun one_dpm -> unit_set (bind_dpm one_dpm eliminator);;
  85
  86                 let new_peg_and_assign (var_to_bind : char) (d : entity) : bool -> bool dpm =
  87                   fun truth_value ->
  88                           fun (r, h) ->
  89                                 let new_index = List.length h
  90                                 in let h' = List.append h [d]
  91                                 in let r' = fun var ->
  92                                   if var = var_to_bind then new_index else r var
  93                                 in (truth_value, r', h')
  94
  95                 let exists var : clause_op = fun one_dpm ->
  96                         List.map (fun d -> bind_dpm one_dpm (new_peg_and_assign var d)) domain
  97
  98                 (* negate_op, and_op, or_op, and if_op as above *)
  99
 100                 let (>>=) = bind_set;;
 101                 let initial_set = [fun (r,h) -> (true,r,h)];;
 102
 103                 let initial_r = fun var -> failwith ("no value for " ^ (Char.escaped var));;
 104                 let run dpm_set =
 105                         let bool_set = List.map (fun one_dpm -> let (value, r, h) = one_dpm (initial_r, []) in value) dpm_set
 106                         in List.exists (fun truth_value -> truth_value) bool_set;;
 107
 108                 let male obj = obj = Bob || obj = Ted;;
 109                 let wife_of x y = (x,y) = (Bob, Carol) || (x,y) = (Ted, Alice);;
 110                 let kisses x y = (x,y) = (Bob, Carol) || (x,y) = (Ted, Alice);;
 111                 let misses x y = (x,y) = (Bob, Carol) || (x,y) = (Ted, Carol);;
 112                 let getx = get 'x';;
 113                 let gety = get 'y';;
 114
 115                 (* "a man x has a wife y" *)
 116                 let antecedent = fun one_dpm -> exists 'x' one_dpm >>= lift_predicate male getx >>= exists 'y' >>= lift_predicate2 wife_of getx gety;;
 117
 118                 (* "if a man x has a wife y, x kisses y" *)
 119                 run (initial_set >>= if_op antecedent lift_predicate2 kisses getx gety);;
 120                 (* Bob has wife Carol, and kisses her; and Ted has wife Alice and kisses her; so this is true! *)
 121
 122                 (* "if a man x has a wife y, x misses y" *)
 123                 run (initial_set >>= if_op antecedent lift_predicate2 misses getx gety);;
 124                 (* Bob has wife Carol, and misses her; but Ted misses only Carol, not his wife Alice; so this is false! *)
 125