From f212354152a53c6a3ab018c7874570c600f463b9 Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Fri, 19 Nov 2010 23:22:06 -0500 Subject: [PATCH] assignment7 tweaks Signed-off-by: Jim Pryor --- hints/assignment_7_hint_5.mdwn | 3 +- hints/assignment_7_hint_6.mdwn | 123 ++++++++++++++++++++++++++++++++++++++--- 2 files changed, 118 insertions(+), 8 deletions(-) diff --git a/hints/assignment_7_hint_5.mdwn b/hints/assignment_7_hint_5.mdwn index af3c9476..882a6232 100644 --- a/hints/assignment_7_hint_5.mdwn +++ b/hints/assignment_7_hint_5.mdwn @@ -176,4 +176,5 @@ > If ∃y (farmer y and ∃x y owns x) then (y beats x). -* Can you figure out how to handle \[[not φ]] on your own? If not, here are some [more hints](/hints/assignment_7_hint_6). But try to get as far as you can on your own. +* Can you figure out how to handle \[[not φ]] and the other connectives? If not, here are some [more hints](/hints/assignment_7_hint_6). But try to get as far as you can on your own. + diff --git a/hints/assignment_7_hint_6.mdwn b/hints/assignment_7_hint_6.mdwn index e30514b5..ed3828b7 100644 --- a/hints/assignment_7_hint_6.mdwn +++ b/hints/assignment_7_hint_6.mdwn @@ -1,16 +1,125 @@ * 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 s[φ] if there are any `i'` that *extend* `i` in s[φ]. - Here's how we can represent that: +------ wrong.... - 
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
-
+ In our framework, we just have to convert the operation >>= \[[ψ]] into another operation >>= \[[ψ]] >>= neg, 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! *) -- 2.11.0