Fourth Unit Computational Logic Assignment
The purpose of this assignment is to give students a chance to
demonstrate their understanding of Computational Logic by writing axioms and
selecting reasoning strategies for a computer to use in solving logic problems.
All work will be done in teams of 1 to 3 members.
All members in a team must be enrolled in CS157. No outside help is
permitted. The assignment is due on Thursday, May 26th. Submission
instructions will be announced.
The assignment will consist of logical entailment problems in various categories.
Descriptions of each category will be provided in advance, and teams will be
asked to make recommendations for solving problems within each category.
Each category description will include (1) a characterization of possible
premises, (2) a characterization of possible conclusions, (3) various
background axioms, and (4) a maximum number of steps.
The team's recommendations for each category must include (1) a collection of
background axioms to include with the premises (e.g. variations on the
background axioms provided in the category's description) and (2) a selection
of reasoning strategies appropriate to that category.
Problem categories and descriptions are available here.
Each team will be awarded points separately for each problem. These points will
be added together to produce a final score. Grades will be determined by the
There will be 10 problems in all. The score for each problem will range from
-5 points to +10 points, meaning that each team will receive a score between
-50 points and +100 points. Terminating with an incorrect answer on a problem
will give -5 points. Exceeding the maximum number of steps for a problem will
give 0 points. Terminating with the correct answer will give a variable number
of points from 0 to 10. In the case of a correct answer, the score will be
obtained by inversely scaling the number of steps actually taken from n
steps to the maximum number of steps for the problem, where n is the
number of steps taken by a benchmark that we provide (this makes it
possible to get extra credit). For example, if the
maximum number of steps is 200, our benchmark gets the correct answer in
50 steps, and a team gets the correct answer in 125 steps,
the team will receive 5 points. Final grades will be determined by curving
the scores across all entrants.
Note that the problems will be chosen so that the probability that logical
entailment holds in any particular case is 50%. The upshot of this is that
guessing will lead to an expected value of 25.
For people taking CS157 for 4 units, this assignment will count equal to one assignment, or
one sixth of the total class grade.