Assignment 8

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

Knight/Knave/Human Identifier

The purpose of this assignment is to put the parse trees that result from Assignment 7 to use. Assignment 7, whose solution is available in

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

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.

In addition, because the midterm exam is at the start of next week (March 27 or 28), there is also a rex portion of this assignment very similar to the Java portion. Even though this rex problem is the extra credit for this assignment, it will help you think again "like Rex," as we haven't worked with Rex for several weeks.

Assignment 8: Knight identification in Java

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 six test files you can use to check that your application is working properly. They are named Test1.java, Test2.java, ..., Test6.java -- and each tests more of the grammar than the previous ones.

To use these files, run

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

for which ever number (1-5) you would like to test. The correct output is available in /cs/cs60/as/a8/Test1.java, again with the digit adjusted from 1 to 5. .out

To be sure your output is correct, you can run

java Parser < /cs/cs60/as/a8/Test1.java | diff - /cs/cs60/as/a8/Test1.java.out

If you see no output, your code is producing identical output to the ".out" file. If you do see output, it is a list of the differences between your code's results and the solutions file.

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 updated Parser.java source file and your truthChecker.rex file (if you have written one) in the usual way, i.e., by running

% cs60submit < filename >

for each file in turn. You will be asked to input the assignment number (8).

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 and submit it using cs60submit.

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