Assignment 4
Assignment 4
CS 256
due December 8, 1998
150 points
For this assignment, assume that a knowledge base is represented
as a list of assertions, each of which is a relational expression.
Each relational expression is represented as a list whose CAR is
the relation name and whose CDR is a list of arguments. The
relations need not be binary. You may assume that each relation
is of a fixed arity less than 10.
Assume that the relation of set membership
is called instance_of and that the subset relation
is called a_kind_of. Assume that the universal
set is called thing and that the set of all
relations is called relation.
Construct functions to
- build derived relations (45 points)
- find all entities that are related to a given entity
by the transitive closure of a given relation
- find all entities to which a given entity is related
by the transitive closure of a given relation
- find all members of a given set, including those that
inherit membership through subsets
- check consistency of the knowledge base (30 points)
- verify whether the set of all entities that are listed in
the knowledge base as elements of some set is equal to the
set of all members (in the sense above) of the set 'thing'.
Print those relations that are in one set but not the other, and
return #t iff the two sets are equal.
- verify whether the set of all relations appearing in the
knowledge base is equal to the set of all members (in
the sense above) of the set 'relation', and conversely.
- print those relations that are in one set but not the other,
and return #t iff the two sets are equal.
- construct and print frames (75 points)
- for a given entity, collect all relations with that
entity as an argument into a frame. Don't forget to document
your frame representation.
- pretty-print a given frame. For each relation in the
frame, you should print which argument the entity is, the
name of the relation, and all other arguments. Your printed
output should be sorted by argument number, and within argument
number, by relation name. In the case of multiple relations
with the same name and argument number, you should combine
all the relations into one line of output, with the other
arguments combined into a list, so that, for example,
1 likes kim
1 likes lee
becomes 1 likes (kim lee).
One or more sample knowledge bases and a function to serve as a
test program will appear in the file a4.dat.