CIS 730 (Introduction to Artificial Intelligence)
Due:
Monday, 03 November 2003 (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-fall_2003 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
given out on 02 November and due on 15 November. There is a reason why the time allotted for this MP has gone from
2 to 3 weeks (with overlap)! J
Start early
and work a few examples now to help
you practice for the midterm exam.
Data format: First, write 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.
(20
points total) Propositional Conjunctive
Normal Form. Implement a parser for
propositional sentences (ground literals only, no quantifiers, predicates, or
functions). Use predicates of arity 0
as propositions, for consistency with later parts. You are welcome to use scanner
generators such as lex/flex/ML-Lex, parser
generators such as yacc/bison/ML-Yacc, or any other tools with this
specific functionality. You may also
use awk or Perl.
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.
2.
(30
points total) I Love It When A Plan
Comes Together! 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, use “lex” and
“yacc” tools or Perl, if you wish and know how. Otherwise, use the Java string tokenizer
classes.
The only nontrivial parts of
this problem are parsing nested functions.
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: (25 points total) Augment your
program to:
a)
(5
points) Parse equality (=) and
specifically differentiate it from implication (=>)
b)
(20
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: Take a break! Whew!