Assignment 8

Harvey Mudd College
Computer Science 60
Assignment 8, Due Thursday, March 23, by midnight

Knight/Knave/Human Identifier and Prolog!

The purpose of this assignment is to introduce the Prolog programming language and to put to use the parse trees that result from Assignment 7.

Assignment 8: Problem 1 (15 pts) Introduction to Prolog

This part of the assignment will introduce you to programming with the logical programming language Prolog. Prolog views computation as depth-first search through a set of rules, or predicates, in order to find whether those predicates are true or false. In addition, Prolog will seek out variable bindings in order to make a predicate true. To try it out, copy the file

/cs/cs60/as/a8/simpsons.pl

to your working directory. There you will see a large number of prolog predicates (rules) that describe the familty tree of the Simpsons. At the end of the file, you should add the following predicates:

grandparent(X,Y)... which is true if X is a grandparent of Y.

granddaughter(X,Y)... which is true if X is a granddaughter of Y.

manyGranddaughters(X)... which is true if X has more than one granddaughter.

descendant(X,Y)... which is true if X is a descendant of Y.

cousin(X,Y)... which is true if X is a cousin of Y.

relByMarriage(X,Y)... which is true if X is related by marriage (and not a blood relative) of Y.

hasYoungerSibling(X)... which is true if X has a younger sibling.

hasOldestGrandchild(X)... which is true if X has a child, call her/him Z, such that Z is the oldest grandchild for all of Z's grandparents.

Remember that you can trace your code by typing trace. at the Prolog prompt. You can turn off tracing by typing notrace. Admittedly, trace can be pretty cryptic, but if you encounter weird behavior, you might want to try turning tracing on to see what's happening.

You may add additional helper predicates that your predicates will use -- for example, the ones we discussed in class may help. Also, look for ways to reuse work from earlier predicates to write the later ones from the above list.

Submitting your code: running cs60submit 8 will submit your code. You may check your code by including predicates like ans1(S), ans2(S), ... from the file

/cs/cs60/as/a8/simpsonsCheck.pl

into your simpsons.pl file and running those predicates at the prolog prompt. The answers are in the simpsonsCheck.pl file.

The submit script will copy your simpsons.pl, but will not grade it (unless I can figure out how to run prolog in "batch" mode). However, your prolog code will be worth 15 points of this assignment, so please check it on your own before your final submission!

Assignment 8: Problem 2 (35 pts.) Knight/knave/human identification in Java

Assignment 7, whose solution is available in

/cs/cs60/as/a7/Parser.java.sols

and

/cs/cs60/as/a8/Parser.java

parses logical expressions, which may or may not include variables. Such logical expressions fall into 3 broad categories:

Tautologies --- expressions that are true for any boolean assignment to the variables involved. If there aren't any variables, the logical expression is a tautology if it is true.
Satisfiable (but not tautological) --- expressions that are true for at least one possible boolean assignment to the variables involved, but not all possible assignments. Expressions without variables never fall in this category.
Unsatisfiable --- expressions that are never true, regardless of the boolean assignment to the variables involved. Expressions without variables are unsatisfiable if they are false.

In this assignment you will extend your parser so that it determines whether or not an input expression is (1) a tautology or (2) satisfiable but not a tautology, or (3) unsatisfiable. Tautologies are true for every possible value of the variables in the expression; unsatisfiable expressions are false for every possible value of the variables; satisfiable (but not tautological) expressions are sometimes true and sometimes false, depending on the values assigned to the expression's variables.

For this problem, you will want to start from your Parser.java file (from assignment 7). You may also start from the solutions file in /cs/cs60/as/a7/Parser.java.sols. The problem is to extend the parsing program that's already written to determine if a given expression is a tautology, unsatisfiable, or satisfiable, but not a tautology. Instead of printing out the parse tree as before, now the program should output the appropriate string from those three possibilities.

For example, some correct I/O exchanges for this assignment include

Type an expression > a+a'
tautology

Type an expression > a*a'
unsatisfiable

Type an expression > a
satisfiable, but not a tautology

Type an expression > 0 -> 1
tautology

Type an expression > 1 -> 0
unsatisfiable

Suggesions on the Java coding:

You will want to keep the parsing code as is. You will need the Expr returned from the parsing in order to evaluate the logical expression.

One clean way to approach this problem is to write a single additional function inside the Parser class:

static String truthChecker(Expr e) { ... }

This truthChecker function will implement a procedure known as Boole-Shannon reduction. The basic idea is that a single variable is chosen and then set to its two possible values -- once to true, once to false. That produces two different expressions. Those two expressions are then determined to be of one of the three types: (1) tautology, (2) unsatisfiable, or (3) satisfiable, but not a tautology. Then the two results are combined to yield the correct classification.

In slightly more detail -- truthChecker will create two new Exprs by substituting both true and false for some variable. If both resulting expressions are tautologies, so is the original expression. If both resulting expressions are unsatisfiable, so is the original. Otherwise, the original expression is satisfiable, but not a tautology.

You will need to add helper functions. One suggestion is to add NO OTHER functions to the Parser class, and add the following nonstatic methods to the Expr class and the classes derived from it. The fundamental strategy is to have each kind of expression handle its share of the work.

String getAVar()

  - e.getAVar() returns a String that is the variable name of some
    variable appearing in the expression e, it returns null
    if there are no variables in the expression.


Expr substitute(boolean b, String varName)

  - e.substitute(b,varName) returns a new expression in which all
    occurrences of the VarExpr with variable name varName have
    been substituted with with a ConstExpr whose value is the
    boolean b.


boolean evaluate()

  - e.evaluate() returns a boolean which is the value of the
    whole expression e. The expression e should have no
    variables in it; otherwise print an error message. If you'd like,
    you could have this method return a String
    (like "tautology" or "unsatisfiable"), but you need not. (I find
    it easier to use the boolean value.)

Because these methods distribute their work throughout the hierarchy of Exprs, you avoid having to write code to wade through parse trees. (In the rex extra credit you do have to write that code, but it's comparatively short.) In this assignment you will be taking advantage of the object-oriented capabilities of Java even more than in Assignment 7.

Note that if you write any code for these methods in the Expr class itself, then it will get called if there is no overriding definition in a particular derived class. Even if you never expect Expr's methods to get called, you need to have the above methods in the Expr base class so that the compiler knows that they are available, regardless of what class is derived from Expr. These unused methods in Expr can do nothing (as long as they return the right type).

Testing your code

In the /cs/cs60/assignments/a8 directory there are test files you can use to check that your application is working properly. They are named Test#.in, with # between 1 and 20. The expected output is in Test#.out. As usual, the cs60submit command will check your submission, but it is slow, so that you may want to check your code with the test files yourself.

Reading

Propositional Logic is covered in Chapter 9 of the text. Also, most (hopefully all) of what you'll need will be discussed in class.

Submission

You should submit your work by running

cs60submit 8

from the directory containing your files, Parser.java, simpsons.pl, and truthChecker.rex, if you decide to work on the extra credit.

Extra Credit: Knight identification in Rex

For the extra credit, you need to write a rex function named truthChecker(E) that does the same thing (basically) as the one you've written in your Parser.java file. The truthChecker function takes in a single input, E, an expression in the same form as output by Assignment 7's parsing program except the will be in Rex lists rather than S-expressions (S-expressions are the lists we've been using with all of the parentheses). Here are some example inputs:

[AND, [var, a], [var, b]]
[NOT, [OR, [const, true], [var, a]]]
[EQ, [var, b], [NOT, [var, b]]]
[IMP, [var, p], [IMP, [var, q], [var, p]]]

Your truthChecker function should output one of three strings:

tautology
satisfiable, but not a tautology
unsatisfiable

whichever describes the input expression. Remember that Rex has nice features like pattern matching and string comparison with == instead of Java's ".equals(...)" .

Put your truthChecker function in a file named truthChecker.rex; the cs60submit 8 command will submit it, if it exists in the directory.

Hints

When a variable is encountered, call truthChecker recursively twice: once with true substituted for that variable, once with false substituted for that variable. Then, depending on what the two return values are from the recursion, you can return the appropriate value for the original function call.
The above hint suggests that it would be very helpful to write a function substitute(bool,varName,E) that takes "true" or "false" as its first argument (either as a string or the integers 0/1), a string (a variable name) as its second argument, and an Expression (in the form described above) as its third argument. substitute returns an expression equivalent to E in which all occurrences of the variable [var, varName] are replaced with the constant expression [const, bool], where bool is either "true" or "false" .
How do you know when to substitute? You will likely want a function getAVar(E) that takes in an expression and returns 0 if there is no variable in that expression. If there is a variable in that expression, getAVar(E) returns one such variable (a string).
When there are no variables in an expression, how do you know if it's true or false? You'll need a function evaluate(E) that returns 1 or 0 (meaning true or false), depending on the input expression E. evaluate should not be called on expressions with variables, however.
The final hint is that while the above may seem like a lot of coding, remember that with recursion, you only do one piece of the work (or one of each possible case) and let recursion do the rest -- and this applies for all three of the above functions, truthChecker, substitute, and getAVar.

Examples

  rex >  truthChecker([AND, [var, a], [var, b]]);
         satisfiable, but not a tautology
	 
  rex >  truthChecker([NOT, [OR, [const, true], [var, a]]]);
         unsatisfiable

  rex >  truthChecker([EQ, [var, b], [NOT, [var, b]]]);
         unsatisfiable

  rex >  truthChecker([IMP, [var, p], [IMP, [var, q], [var, p]]]);
         tautology

Harvey Mudd College Computer Science 60 Assignment 8, Due Thursday, March 23, by midnight