Assignment 8

Harvey Mudd College
Computer Science 60
Assignment 8, Due Friday, Apriil 5, by midnight

Tautology Identifier and Prolog!

The purpose of this assignment is to extend the small, logical language that you built last week to include the evaluation of logical expressions. In addition, we will begin exploring a much larger programming language built on a logical foundation: Prolog.

Problem 1 (35 pts.) Evaluating logical expressions 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 (*) a tautology or (*) satisfiable, but not a tautology, or (*) unsatisfiable.

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/a8/Parser.java. The problem is to extend the parser to determine if a given expression is a tautology, unsatisfiable, or satisfiable, but not a tautology. In addition to 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'

(OR (var a) (NOT (var a)))

tautology


Type an expression >  a * a'

(AND (var a) (NOT (var a)))

unsatisfiable


Type an expression >  a

(var a)

satisfiable, but not a tautology


Type an expression >  0 > 1

(IMP (const false) (const true))

tautology


Type an expression >  1 > 0

(IMP (const true) (const false))

unsatisfiable

Suggesions on the Java coding:

You will want to keep the parsing code as is. One way to do this cleanly is to change only one thing in the Parser class, inside main: after the lines

      System.out.println(parseTree);      // Print the resulting parse tree
      System.out.println("");             // Print an extra blank line

add the lines

        // The next line prints one of the following:
        //   tautology
        //   unsatisfiable
        //   satisfiable, but not a tautology
      System.out.println(parseTree.truthChecker());  
      System.out.println("");             // Print an extra blank line

All of the other changes can be in the hierarchy of expressions, i.e., the base class Expr and its many derived classes. First, inside the abstract base class Expr you will want to add a method with the signature

public String truthChecker()

This truthChecker function will implement a procedure known as Boole-Shannon reduction. Basically, it will choose a variable from the invoking expression and then create two new expressions, one in which that variable has been set to true and one in which that variable has been set to false. Those two expressions are then recursively determined to be of one of the three types: (1) tautology, (2) unsatisfiable, or (3) satisfiable, but not a tautology. Depending on the combination of results obtained, the correct classification of the original expression is returned. Specifically, 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.

The suggested approach to this assignment is to exploit object-oriented programming in a fundamental way: each derived type of expression will handle its share of the work in the process of truth checking. I would add the following methods both to the Expr class and all of the derived classes in which they need to be overridden:

public 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.


public 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.


public 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 this method should print an error 
    message. It is also possible to have this method return a String
    (either "tautology" or "unsatisfiable"), though I've found
    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.)

Note that the code you write (if any) for these methods in the base Expr class itself will be called for a derived class if the derived class does not override the methods. This is a convenient way to provide default behavior, e.g., for printing errors. 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 for all expressions of any type derived from Expr.

Extra Credit ??

Let n represent the number of distinct variables in an expression. The Boole/Shannon reduction described above runs in exponential time, that is, it requires 2-to-the-nth-power calls to evaluate. Extra credit will be given to anyone who can optimize the truth-checking algorithm to require only polynomially many calls to evaluate, e.g., n squared, n cubed, or the like, or show that such a polynomial algorithm can't exist. Don't worry too much about this problem, however -- it's considered the most important open question in computer science!

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.

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.

Problem 2 (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.

Getting Started with prolog

To run prolog, type prolog at a turing prompt. You will see a prompt like this one:
```
         ?-
```

To read in a file named simpsons.pl, type
```
         ?-  ['simpsons.pl'].
```

You can exit prolog with control-D or halt. You can query any predicates already loaded (e.g., from a file) by simply typing your query at the prompt, e.g.

         ?-  parent(homer,bart).

         yes.

         ?-  parent(maggie,X).
 
         no.

         ?-  parent(marge,X).

         X = bart ;   <-- typing a semicolon asks to see more valid bindings

         X = lisa ; 

         X = maggie ; 

         no.

You can comment your file with /* ... */ or %, the percent sign is a one-line comment (to the end of the line). The // comment is not available; // is prolog's symbol for division.

Watch out for negated predicates. Not in prolog is \+ and not equals is \==, but for these to work all variables involved have to be bound to values. So, if we want to write a predicate notSiblings(X,Y), the following would allow both testing and generation of not-sibling pairs:
```
  notSiblings(X,Y) :- person(X), person(Y), \+siblings(X,Y).
```
Of course, for lists and numerical values, we don't have the luxury of a person predicate, so it's best to place negated predicates as late as possible in the code so that variables will be bound before reaching them.

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.

Checking 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 comments in the simpsonsCheck.pl file.

Submission

You should submit your work for these two problems by running

cs60submit Parser.java
cs60submit simpsons.pl

and even cs60submit truthChecker.rex if you decide to work on the (real) Extra Credit.

Extra Credit: Boole/Shannon 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. Your truth-checker does not have to output the parse tree (after all, it's being given the parse tree as input!) 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 command cs60submit truthChecker.rex will submit it.

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 Friday, Apriil 5, by midnight