[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: clisp-list@ma2s2.mathematik.uni-karlsruhe.de*Subject*: Fwd: Re: College student need...*From*: DESCHOEN@aol.com*Date*: Sat, 8 Jul 1995 18:59:36 -0400

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

**Follow-Ups**:**Re: Fwd: Re: College student need...***From:*Eric Sauthier <sauthier@lia.di.epfl.ch>

- Prev by Date:
**clx and xauth problem** - Next by Date:
**Re: Fwd: Re: College student need...** - Previous by thread:
**clx and xauth problem** - Next by thread:
**Re: Fwd: Re: College student need...** - Index(es):