Fwd: Re: College student need...

[DESCHOEN@aol.com]

Please see below.  Student willing to pay $$ for coding.
---------------------
Forwarded message:
Subj:    Fwd: Re: College student need...
Date:    95-07-08 18:48:42 EDT
From:    DESCHOEN

To:      clisp-lisp@ma2s2.mathematik.uni-karlsruhe.de

I am looking for any experienced Common LISP programmer to code the program
listed below.  I am willing to pay a very decent amount for the code.

Thank you.
---------------------
Forwarded message:
Subj:    Re: College student needs LIS...
Date:    95-06-24 09:20:38 EDT
From:    DESCHOEN
To:      dudeyp@chert.cs.orst.edu
CC:      DESCHOEN

Here it is:

The task is to write a program which computes and displays truth tables for
wffs of propositional logic.

Wffs are to be represented by lists in prefix notation, as specificed by the
following grammar:

wff ::= variable | (unary-op wff) | (binary-op wff wff)
variable ::= A | B | C | ... | Z |
unary-op ::= not-sign
binary-op ::= iff-sign | if-sign | and-sign | or-sign |

The signs to be used for the operators not-sign, iff-sign, etc. are given by
the following definitions which should be a part of your program.
(defparameter iff-sign '<->)
(                    if-sign '->)
(                    and-sign '&)
(                    or-sign '+)
(                    not-sign '~)

an example of a wff in this representation is
(-> (& (-> P Q) (-> Q R)) (+ (~ P) R)))

Your program should produce results like the following:

> (truth-table '(+ A B))
( A B)     (+ A B))
--------------------------
( 0  0)      0
( 0  1)      1
(1  0)       1
(1  1)       1
NIL

>(truth-table '(& (~ B) (+ (& A C)(-> B C))))
(A B C)      (& (~ B) (+ (& A C) (-> B C)))
----------------------------------------------------------
(0 0 0)    1
(0 0 1)    1
(0 1 0)    0
(0 1 1)    0
(1 0 0)    1
(1 0 1)    1
(1 1 0)    0
(1 1 1)    0
NIL

You will need to write several functions.  Here are some suggestions:

i) a function VARIABLES which takes a wff and returns the set of all
variables which occur in it.  A set is represented by a llist without
duplicate elements.  The order of the elements in a set is immaterial.

> (variables '(+ (& A B) (-> C D)))
( A B C D)

ii)  a function TRUTH_ASSIGNMENTS which takes a set of variables and returns
a list of all possible truth assignments for these variables.  A truth
assignment can be represented as an A-LIST.  For example, the following is a
truth assignment for the set of variables (A B C).

> (truth-assignments '(a b c))

(((A . 0) (B . 0) (C .0))
 ((A . 0) (B . 0) (C .1))
 ((A . 0) (B . 1) (C . 0))
 ((A . 0) (B . 1) (C . 1))
 ((A . 1)( B . 0) (C . 0))
 ((A . 1)(B. 0) ( C . 1))
 ((A . 1)( B . 1) (C . 0))
 ((A . 1)( B . 1)( C . 1)))

Hint:  The function truth_assignments is very much like the function POWERSET
which we have seen in class.  Suppose that we looked at the truth assignments
above as descripptions of subsets of (A B C), where 0 indicates that the
paired variable is not in the subset and 1 indicates that it is.  Then the
truth assignment ((A . 1)(B . 0)(C . 1)) can be thought of as representing
the subset (A C) ;; set --> set of sets
(defun powerset (s)
 (if (null s)
      (list nil)
   (let ((ps (powerset(cdr s))))
        (append ps (cons-list (car s) ps)) )) )

;; sexprr x list ---> list
(defun cons-list (x lis)
  (if (null lis)
      nil
     (cons (cons x(car lis)) (cons-list x (cdr lis))) ))

iii)  a function EVAL-WFF which takes a wff and a truth-assignment and
evaluates the wff under that truth assignment.  You should define individual
functions for evaluating each sort of wff according to its manin connective.
 The definitions of the individual connectives are the usual ones given:

P Q   (~P)   (+ P Q)  ( & P Q)   (-> P Q)    (<-> P Q)
----------------------------------------------------------------------------
0 0       1       0   0                        1              1
0 1       1       1   0                        1              0
1 0       0       1   0                        0              0
1 1       0       1   1                        1              1

A top-level definition which formats the output is given below.  This
function uses features of LISP which we have not discussed.  You might want
to look ahead in the bood and try to decipher it.  You may write your own
function if you prefer.

(defun truth-table (wff)
  "Prints out a truth table for wff and returns nil"
 (let* ((vars (variables wff))
         (truth-assgns (truth-assignments vars)) )
    (format t "~% ~S    ~S " vars wff)
    (format t "~ % -------------------------------")
    (mapc #'(lambda (assgn)
       (format t "~% ~S     ~S"
             (mapcar #'cdr assgn)
              (eval-wff wff assgn)) )
            truth-assgns)
      (format t "~%")
      nil))


An important point about style:  Define recognizers and selectors for wffs,
and use these in your main function definitions.  Doing so will make your
program easier to develop, easier to understand and easier to modify.  Your
definition of EVAL-WFF, in particular, should not use any of the primitive
functions car, cdr, and eq.  These will be used in your recognizer and
selector functions for wffs, which in turn will be used in eval-wff.

Example recognizers:
   (defun is-variable? (wff) (symbolp wff))
   (defun is-iff? (wff) (eq (op wff) iff-sign))
   (defun is-not? (wff) (eq (op wff) not-sign))

Example selectors:
   (defun op (wff)(car wff))
   (defun arg1 (wff)(cadr wff))

Except for IS_VARIABLE?, all of the recognizers given above assume that their
inputs are not variables.  This means that explicit variable tests must
always preced their use.  We could avoid this contraint by including a
variable test in each recognizer's definition, e.g.
   (defun is-iff? (wff) (and (not (is-variable? wff)(eq (op wff) iff-sign)))

The first definition might be more efficient but the second is safer.  You
should provide similar definitions (of either form) for each of the missing
recognizers and selectors.  Do this the first thing!  You will not want to
worry about chains of CAR's and CDR's while you are trying to think your way
to a solution to the problem.

As a hint about how to structure your program, here is a start on EVAL-WFF:

(defun eval-wff (wff assgn)
    (cond ((is-variable? wff)
        (cdr (assoc wff assgn)) )
      ((is-not? wff)
            (eval-not (eval-wff (arg1 wff) assgn)) )
    ...
))


OK!  That's almost verbatim from the assignment.

Dennis