100 points, due April 1, 1997 (no fooling)
Write a function CONVERT that takes a representation of a sentence in predicate logic, of a form described below, and returns a representation in clause form, with sets represented by lists.
You may assume that the input has no free variables, that the only connectives are AND, OR, IMPLIES, and NOT. You may assume that nested quantifiers never quantify variables of the same name. You needn't check for ill-formed input sentences.
Assume that variables are represented as symbols beginning with question marks. Other symbols may represent either predicate names or object constants, depending on their position.
Assume that the connectives AND, OR, and IMPLIES are written in binary prefix form, while NOT, (FORALL variable) and (EXISTS variable) are written in unary prefix form. All prefix operators are to appear inside the parentheses, as in Lisp. That is, assume the following grammar for statements
Sentence -> QuantifiedSentence | CompoundSentence | PrimitiveSentence
QuantifiedSentence -> ( Quantifier Sentence )
Quantifier -> ( forall Variable ) | ( exists Variable )
CompoundSentence -> ( not Sentence ) ( and Sentence Sentence ) |
( or Sentence Sentence ) ( implies Sentence Sentence )
PrimitiveSentence -> ( PredicateName ) | ( PredicateName Terms )
Terms -> Term | Term Terms
Term -> Variable | ObjectConstant
Test on at least the 9 sentences given in the file A2.DAT
on the
web site and the K: drive (mcsnw1). Some suggestions for selectors
and constructors are given there. You needn't use them, but it's
probably a good idea at least to distinguish negations from other
compound statements.