[Odko]

I have problem with my code. I need to check tautology using recursion. Please give me some hint. I know how recursion works. But I do not have clue how to apply in tautology. this is my arbitrary. ((p | q) & !(p & q)) == (p | q); I want to check it. PLease help me!

[Odko]

public class Formula {

 public enum Form {
  AND, OR, IMPLIES, EQUIVALENT, NOT, VARIABLE
 }
 
 private static class ParseRes {
  public Formula form;
  public String remainStr;
 }

 protected static String printBinConn(Form f) {
  switch (f) {
   case AND: return "&";
   case OR: return "|";
   case IMPLIES: return "->";
   case EQUIVALENT: return "<->";
  }
  return null;
 }

 private static Form readBinConn(String s) {
  if (s.startsWith("&")) {
   return Form.AND;
  } else if (s.startsWith("|")) {
   return Form.OR;
  } else if (s.startsWith("->")) {
   return Form.IMPLIES;
  } else if (s.startsWith("<->")) {
   return Form.EQUIVALENT;
  }
  return null;
 }

 private static ParseRes rparse(String str) {
  if (str.length() > 0) {
   char c = str.charAt(0);
   if (c >= 'A' && c <= 'Z') {
    ParseRes r = new ParseRes();
    r.form = new FVar(str.substring(0,1));
    r.remainStr = str.substring(1);
    return r;
   } else if (c == '(') {
    ParseRes res1 = rparse(str.substring(1));
    if (res1 == null) {
     return null;
    }
    Form f = readBinConn(res1.remainStr);
    if (f != null) {
     ParseRes res2 = rparse(res1.remainStr.substring(printBinConn(f).length()));
     if (res2 == null) {
      return null;
     }
     if (res2.remainStr.startsWith(")")) {
      ParseRes r = new ParseRes();
      r.form = new FBinaryConn(f, res1.form, res2.form);
      r.remainStr = res2.remainStr.substring(1);
      return r;
     }
    } else if (res1.remainStr.startsWith("')")) {
     ParseRes r = new ParseRes();
     r.form = new FNot(res1.form);
     r.remainStr = res1.remainStr.substring(2);
     return r;
    }
   }
  }
  return null;
 }

 public static Formula parse(String str) {
  ParseRes r = rparse(str);
  if (r == null) {
   return null;
  }
  if (r.remainStr.length() == 0) {
   return r.form;
  } else {
   return null;
  }
 }
 
 public String toString() {
  return null;
 }

 public Form form() {
  return null;
 }
 
 public Formula subFormula(int i) {
  return null;
 }

 public String variableName() {
  return null;
 }
}

[Odko]

Here is my code.
My processer wants to me use recursion.

public class FNot extends Formula {
 private Formula sub;

 public FNot(Formula s) {
  sub = s;
 }

 public String toString() {
  return "(" + sub.toString() + "')";
 }

 public Form form() {
  return Form.NOT;
 }
 
 public Formula subFormula(int i) {
  if (i == 1) {
   return sub;
  } else {
   return null;
  }
 }
}

public class FVar extends Formula {
 private String v;

 public Form form() {
  return Form.VARIABLE;
 }

 public String toString() {
  return v;
 }

 public String variableName() {
  return v;
 }

 public FVar(String s) {
  v = s;
 }
}

public class FBinaryConn extends Formula {
 private Form f;
 private Formula fst, snd;

 public FBinaryConn(Form ff, Formula ffst, Formula fsnd) {
  f = ff;
  fst = ffst;
  snd = fsnd;
 }

 public String toString() {
  return "(" + fst.toString() + Formula.printBinConn(f) + snd.toString() + ")";
 }

 public Form form() {
  return f;
 }
 
 public Formula subFormula(int i) {
  if (i == 1) {
   return fst;
  } else if (i == 2) {
   return snd;
  } else {
   return null;
  }
 }
}

class TautChecker {

 public static String union(String s1, String s2) {
  int i;
  for (i = 0; i < s2.length(); i++) {  // for each character in s1
   if (s1.indexOf(s2.charAt(i)) == -1) {  // the character is not already in s2
    s1 = s1 + s2.charAt(i);  // add the character to s2
   }
  }
  return s1;
 }
  

 public static String formulaVars(Formula f) {
  switch (f.form()) {
   case VARIABLE:
    return f.variableName();
   case NOT:
    return formulaVars(f.subFormula(1));
   default: // it's a binary connective
    return union(formulaVars(f.subFormula(1)), formulaVars(f.subFormula(2)));
     // we compute the union of the two subformulas to avoid several occurrences of the same var
  }
 }

 public static void main(String[] args) {
  Formula f = Formula.parse(args[0]);
  System.out.println(f.toString());
  System.out.println(formulaVars(f));
 }
}

[Odko]

I can check using for loop. Like this

public class Taunt_Taunt {
    
    public static void main(String[] args) {
        boolean p, q, A;
        
        for (int i = 0; i <= 1; i++) {
            p = i == 0 ? false : true;
            for (int j = 0; j <= 1; j++) {
                q = j == 0 ? false : true;
               
                    
                    A = ((p | q) & !(p & q)) == (p | q); 
                    System.out.println(p + " " + q + " " + " = " + A);
                }
            }
        }
    }

How can i convert it to recursion?

[macosxnerd101]

You might look at adapting parsing algorithms like Shunting Yard.

[Odko]

macosxnerd101, on 31 January 2013 - 08:01 AM, said:

You might look at adapting parsing algorithms like Shunting Yard.

Sorry I do not understand what is PM.Second I need to check tautology or not using recursion method. The code is above given by my teacher. This is the kind of requirement>

You should implement a tautology checker in the TautChecker.java class
and modify the main function so that it prints the result of the tautology check.
When you run the tautology checker it's good to put double quotes around the
formula, like this:
java TautChecker "((A|(B|C))<->((A|B)/>|C))"
Use recursion to implement the tautology checker. You should submit your
TautChecker.java le and a .pdf le describing in details how your tautology
checker works.
Hints: Write two recursive functions. One which computes the truth value
of a formula for a given truth value assignment of the variables that it contains.
One simple way to pass the variable value assignments is to pass two strings to
it, one with variable names and one with truth values. For instance, the strings
"DEA" and "TFF" means that D is true and E and A are false. This recursive
method will have a similar structure as the method formulaVars, so you can use
2
that as a starting point. The other recursive method should be something which
enumerates all possible truth value assignments, which are 2n for n variables.
For each assignment it shoudl use the other recursive function to compute the
value. This recursive function will be similar to the binary recursion example
in the lecture.

If you help me to figure this out, I will appreciate a lot.

[macosxnerd101]

I've pointed you in the direction of a parsing algorithm. Your job is to read up on that algorithm and implement it.