comp.lang.lisp

TwirlwT

12/31/2015 2:32:00 PM

El jueves, 31 de diciembre de 2015, 12:35:52 (UTC+1), WJ escribió:
> Mark Tarver wrote:
>
> > > > Write code that will answer if the given sentence S of the
> > > > form A --> B is entailed
> > > > by a propositional KB that consists of such sentences.
> > > > Your program should have two inputs: S and the KB.
> > > > KB will contain sentences that are in the form X --> Y only.
> > > > A,B,X and Y are propositions or negated propositions only.
> > >
> > > You may represent the KB a -> b, b -> c, m -> n as
> > > ((a b) (b c) (m n)). You can create a copy of the KB and fatten
> > > the copy with additional sentences entailed by the previous copy.
> > > For example, the KB also entails (a c) (which is my Lisp
> > > representation
> > > for a --> c). So the fattened copy will be
> > > ((a b) (b c) (m n) (a c)). Now see if the fattened copy has
> > > (x y) (y k) and if so, fatten the copy further by adding
> > > ( x k). You will reach a point where the fattening is impossible
> > > (like the transitive closure of relations). Then check if given
> > > sentence is in the fattest copy. If so, it is entailed by the KB
> > > else it is not.
> >
> > Here is an 11 line solution in Qi. It uses the system fix which
> > iterates
> > a function over its argument until no change can be achieved.
> >
> > (define atp
> > KB S -> (element? S (fix fchain-kb KB)))
> >
> > (define fchain-kb
> > KB -> (mapcan (/. X (fchain X KB KB)) KB))
> >
> > (define mapcan
> > _ [] -> []
> > F [X | Y] -> (append (F X) (mapcan F Y)))
> >
> > (define fchain
> > X [] _ -> [X]
> > [X Y] [[Y Z] | _] KB -> [[X Y] [X Z]] where (not (element? [X Z]
> > KB))
> > X [_ | Y] KB -> (fchain X Y KB))
> > ________________________________________________
> > (15-) (atp [[a b] [b c] [c d]] [a d])
> > true
> >
> > (16-) (atp [[a b] [b c] [c d]] [a e])
> > false
> >
> > Its not hard to write the corresponding Lisp.
>
> MatzLisp (Ruby):
>
> def fatten implications
> fatter = (implications +
> implications.flat_map{|a,b|
> implications.select{|c,d| b == c}.map{|c,d| [a,d]}}).uniq
> fatter == implications ? fatter : fatten(fatter)
> end
>
> def entailed kb, s
> fatten(kb).include? s
> end
>
> entailed [[:a,:b],[:b,:c],[:c,:d]],[:a,:d]
> ==>true
> entailed [[:a,:b],[:b,:c],[:c,:d]],[:a,:e]
> ==>false
> entailed [[:a,:b],[:b,:c],[:b,:m]],[:a,:m]
> ==>true
> entailed [[:a,:b],[:b,:c],[:b,:m],[:m,:z]],[:a,:z]
> ==>true
> entailed [[:a,:b],[:b,:c],[:b,:m],[:m,:z]],[:m,:b]
> ==>false
>
>
> It's not hard to write the corresponding Lisp,
> but it may be impossible to write the corresponding CL.
>
>
> --
> Amazon bans book. After nearly a month on the site, all traces of the book and
> its 80 reviews have been removed.
> http://jamesfetzer.blogspot.com/2015/11/debunking-sandy-hook-debunk...
> https://www.youtube.com/watch?v=E...


(defun entailed(rules-goal)
(let ((h1 (make-hash-table))
(h2 (make-hash-table)))
(labels ((implies(a b)
(and (member b (gethash a h1)) t))
(addrule-to-h(a b)
(pushnew b (gethash a h1))
(pushnew a (gethash b h2)))
(addrule(a b)
(addrule-to-h a b)
(loop for x in (gethash a h2) do (addrule-to-h x b))))
(loop for ((a b) rule?) on rules-goal while rule? do (addrule a b)
finally (return (implies a b))))))

(defparameter test1 '((:a :b) (:b :c) (:c :d) (:a :d)))

(entailed test1) => T