This exercise elaborates on the preceding one, and introduces the idea of recursively evaluating an expression of propositional logic.

As we are going to be creating different implementations of some of the classes of the last question, we will create a Java package to hold all of the classes for this question. Check back with the notes on creating packages from last week.

Create a new package called logic in your workspace. All classes created for this question will be put in there.

Here is a set of inductive rules for the language of propositional logic:

1. There is a finite set PropVar of propositional variables, written \( P \), \( Q \), \( R \), etc.
2. Every expression in PropVar is also in Wff (i.e, the set of Well-Formed Formulas).
3. If a formula \( A \) is in Wff, then so is \( \sim A \) (i.e., not \( A \)).
4. If the formulas \( A \) and \( B \) are in Wff, then so are
   • \( A \, \& \, B \) (i.e., \( A \) and \( B \)),
   • \( A | B \) (i.e., \( A \) or \( B \)),
   • \( A \rightarrow B \) (i.e., \( A \) implies \( B \)).
5. Nothing else is in the set Wff.

Here is an abstract class representing Wff. Note that both its methods also happen to be abstract. This isn’t necessarily the case with an abstract class, but is convenient in this case, since we don’t want to specify the bodies of these methods at the Wff level.

package logic;

public abstract class Wff {

     public abstract boolean eval(Valuation val);

     public abstract String toString();

}

The methods toString() and eval() will need to be implemented by every class which extends Wff, namely PropVar and also AndWff, OrWff, IfWff and NotWff.

The semantic value of the propositional variables can vary from situation to situation. Let’s say that a Valuation is a mapping from propositional constants to truth values and each Valuation corresponds to the way the world could be. How are we going to model this in Java? As a HashMap of course! Valuation is little more than a convenient wrapper for a HashMap:

package logic;

import java.util.HashMap;

public class Valuation {

    HashMap<PropVar, Boolean> val = new HashMap<PropVar, Boolean>();

    public boolean get(PropVar propVar) {
        return val.get(propVar);
    }

    public void put(PropVar propVar, boolean tv) {
        val.put(propVar, tv);
    }
}

(Recall that Boolean is the wrapper class corresponding to the primitive type boolean. Values get automatically converted between these two types as appropriate when they get added to, or returned from, the HashMap.)

So this is going to allow us to create a Valuation instance and then add specific truth values for specific PropVar s.

As before, AndWff, OrWff, IfWff will be subclasses of BinaryWff. Since we want the constituents of a BinaryWff to be arbitrarily complex, we will replace occurrences of PropVar by Wff.

Create another implementation of the class BinaryWff which meets the same API as before, with occurrences of PropVar replaced by Wff, and which also extends Wff. BinaryWff must also be marked as abstract since it does not provide an implementation of eval(Valuation val)().

The next exercise involves constructing an evaluation method for AndWff. The class PropLogicLauncher gives an overview of how evaluation is meant to work:

package logic;

public class PropLogicLauncher {

    public static void main(String[] args) {

       // Make some new constants
        PropVar p = new PropVar("P");
        PropVar q = new PropVar("Q");
        PropVar r = new PropVar("R");

        // Build some Wffs
        Wff e0 = new NotWff(p);
        Wff e1 = new AndWff(q, e0);
        Wff e2 = new OrWff(e1, p);
        Wff e3 = new NotWff(e2);

        // What does their toString() method produce?
        System.out.println("Display form of Wff e0 is: " + e0);
        System.out.println("Display form of Wff e1 is: " + e1);
        System.out.println("Display form of Wff e2 is: " + e2);
        System.out.println("Display form of Wff e3 is: " + e3);
        System.out.println();

        // Create a Valuation and set some truth values
        Valuation val = new Valuation();
        val.put(p, true);
        val.put(q, false);
        val.put(r, true);

        // Compute the truth values and display the results
        System.out.println("The value of Wff e0 is: " + e0.eval(val));
        System.out.println("The value of Wff e1 is: " + e1.eval(val));
        System.out.println("The value of Wff e2 is: " + e2.eval(val));
        System.out.println("The value of Wff e3 is: " + e3.eval(val));
    }
}

Here’s the output:

Display form of Wff e0 is: ~P
Display form of Wff e1 is: (Q & ~P)
Display form of Wff e2 is: ((Q & ~P) | P)
Display form of Wff e3 is: ~((Q & ~P) | P)

The value of Wff e0 is: false
The value of Wff e1 is: false
The value of Wff e2 is: true
The value of Wff e3 is: false

Let’s think about what needs to happen when we call e1.eval(val). The “abstract syntax” of e1 is as follows:

AndWff(PropVar("Q"), NotWff(PropVar("P")))

When we call eval(val) on e1, we need to figure out the truth values of its two subexpressions, namely:

PropVar("Q")

and:

NotWff(PropVar("P")).

In order to compute PropVar("Q").eval(val), we just have to look up the truth value of PropVar("P") in our Valuation val (which yields the value false), and we then hand this value back up to the call e1.eval(val). In order to compute:

NotWff(PropVar("P")).eval(val)

we first have to compute:

PropVar("P").eval(val)

and again we need to look up the truth value of PropVar("P") in our Valuation val (which yields the value true). We hand this value back up to the call NotWff(PropVar("Q")).eval(val), which we can think of as computing the value of the Java expression ! true, yielding false. So now:

AndWff(PropVar("Q"), NotWff(PropVar("P"))).eval(val)

is reduced to evaluating something like the Java expression false && false, yielding the result false.

This is a standard example of recursive evaluation. We call the eval() method on the top-level expression e1, keep on working our way down until we hit the propositional constants where the recursion bottoms-out, and then work our way up again up, plugging values into the subexpressions until we get to top-level.

Here’s an implementation of PropVar that provides the basis of the evaluation.

package logic;

public class PropVar extends Wff {

    private String propVar;

    public PropVar(String str) {
        this.propVar = str;
    }

    public String toString() {
        return propVar;
    }

    public boolean eval(Valuation val) {
        return val.get(this);
    }

}

Reimplement the class AndWff, again as a subclass of BinaryWff. Here is the API:

public AndWff(Wff left, Wff right)

Class constructor.

public boolean eval(Valuation val)

Return the result of evaluating the conjunction of its constituents.

We recommend that you attempt to also implement the classes OrWff, IfWff and NotWff. In order to get the following to work, you will have to add a NEG type to Operator. If you implement everything correctly, you ought to be able to run PropLogicLauncher with the output shown above.