CIS 730 (Introduction to Artificial Intelligence)
Due: Friday,
05 November 2004 (by 5pm)
This
programming assignment is designed to apply your theoretical understanding of first-order
logic (FOL) syntax to the implementation of a simple tool for converting well-formed
formulas (sentences) into conjunctive normal form.
Refer to
the course intro handout for guidelines on working with other students.
Remember
to submit your solutions in electronic form by uploading them to ksu-cis730-fall2004 and produce
them only from your personal notes (not common work or sources other than
the textbook or properly cited references).
Note: Previously
this assignment was assigned with 2 weeks given to complete it. Later we extended it to 3, but kept the
specification the same. This time you
still have about 3 weeks, but are being given some help with the API. Start
early and work a few examples now to help you practice for the final exam.
Data
format: First, using the sample parser
code to be posted, develop a driver (in Java, C++, SML, or an imperative
programming language of your choice) that takes input from standard input in
the following format:
#
The hash mark denotes comments.
#
Your program should ignore all input on a line containing the ‘#’
#
symbol.
#
#
The first non-comment line contains a single integer
#
denoting the number of sentences.
3
#
The second non-comment line starts the sentences.
#
Syntax:
# \A denotes UNIVERSAL QUANTIFICATION (\forall)
# \E denotes EXISTENTIAL QUANTIFICATION (\exists)
# => denotes IMPLICATION (\rightarrow)
# & denotes CONJUNCTION, i.e., AND
# | denotes DISJUNCTION, i.e., OR (\vee)
# ! denotes NEGATION, i.e., NOT (\not)
# = denotes EQUALITY (NOTE: this is OPTIONAL
in the regular MP)
# . separates each quantified variable from
its scoped expression
#
Conventions:
# - All variables are lowercase
# - All constants are alphanumeric names in
ALL CAPS
# - All predicates contain alphanumeric
characters or _, begin with
# a capital letter, and enclose their
arguments in parentheses
# - All functions contain alphanumeric
characters or _, begin with
# a capital letter, and enclose their
arguments in parentheses
# - Use C/C++ precedence for & and |
\A
x . \A y . P(x, y) => \E z . Q(x, z) & !R(y, z)
Husband_Of
(JOE1, SUSAN)
Longer
(left_leg_of(RICHARD), left_leg_of(JOHN)) & (Foo() | Bar = Baz)
#
#
Correct answers:
#
1. {!P(x_1, y_1), Q(x_1, sf1(x_1, y_1))},
# {!P(x_2, y_2), !R(x_2, sf1(x_2, y_2))}
#
2. {Husband_Of (JOE1, SUSAN)}
#
3. {{Longer (left_leg_of(RICHARD), left_leg_of(JOHN))},
# {Foo(), Bar = Baz}}
1.
(5
points) Using the scanner and parser
application programmer interface (API).
Later this week, a sample scanner and parser will be posted to the class
web group. Download this code and write
your main (driver) classes to use it.
The code provided will tokenize and parse propositional sentences
(ground literals only, no quantifiers, predicates, or functions). It uses predicates of arity 0 as
propositions, for consistency with later parts.
Note: You
are welcome to port or reimplement the sample Java code using scanner generators such as lex/flex/Antlr/ML-Lex, parser generators such as yacc/bison/JCup/ML-Yacc, or any other tools with this
specific functionality. You may also
use awk or Perl.
2.
(20
points total) Propositional Conjunctive
Normal Form. The only nontrivial
parts of this problem are: rewriting implications (from A Þ B
to ¬A Ú B), implementing DeMorgan’s theorem (the
distribution of ¬), and implementing the distributive law.
Note:
There should be no connectives when
you are done – see the examples above.
This is the “operators out” part of I.N.S.E.U.D.O.R. – the connectives are implicit; each sentence is converted
into an (implicitly conjoined) list of clauses (in curly braces) and each
clause contains an (implicitly disjoined) list of literals.
3.
(15
points total) First-Order Clausal Form. Implement conversion to clausal form (CNF)
for FOL sentences not containing equality
and not requiring Skolemization.
You should keep some kind of simple symbol table in order to check the
scope of variables. Again, adapt the
given codes, or use any other scanner (string tokenizer) or parser generator
you wish.
The nontrivial parts of this
problem are parsing nested functions
and implementing
Note:
Make sure you rename variables using the suffix “_n”. In a production
interpreter, you would use a function such as gensym() to generate a unique
symbol (e.g., suppose you had to rename occurrences of x and there was already an x_1).
Here, you need not worry about collisions; just implement gensym() yourself and make sure it produces distinct names.
Extra credit: (10 points total) Augment your
program to:
a)
(5
points) Parse equality (=) and
specifically differentiate it from implication (=>)
b)
(5
points) Implement Skolemization as a step in conversion of FOL wffs to clausal form. Your solution shall be evaluated in the
context of the above process. See the
first example; your skolem functions must
be called “sfn” where n is a newly-generated integer, and they
must have the right arity. You may
assume that “sf” is a reserved prefix for function names, but you do not have
to check for it in input.
Class participation: Read and Explain Pairs, Chapter
10.