# How to check tautology using recursion?

Page 1 of 1

## 6 Replies - 3356 Views - Last Post: 04 February 2013 - 04:34 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=310493&amp;s=3ec3257f7d6f942fe6caf50586f7e056&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Odko

Reputation: -1
• Posts: 37
• Joined: 25-October 12

# How to check tautology using recursion?

Posted 31 January 2013 - 04:46 AM

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!
Is This A Good Question/Topic? 0

## Replies To: How to check tautology using recursion?

### #2 Odko

Reputation: -1
• Posts: 37
• Joined: 25-October 12

## Re: How to check tautology using recursion?

Posted 31 January 2013 - 04:52 AM

```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;
}
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;
}
}

```

### #3 Odko

Reputation: -1
• Posts: 37
• Joined: 25-October 12

## Re: How to check tautology using recursion?

Posted 31 January 2013 - 04:59 AM

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));
}
}

```

### #4 Odko

Reputation: -1
• Posts: 37
• Joined: 25-October 12

## Re: How to check tautology using recursion?

Posted 31 January 2013 - 05:33 AM

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?

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12242
• Posts: 45,328
• Joined: 27-December 08

## Re: How to check tautology using recursion?

Posted 31 January 2013 - 08:01 AM

You might look at adapting parsing algorithms like Shunting Yard.

### #6 Odko

Reputation: -1
• Posts: 37
• Joined: 25-October 12

## Re: How to check tautology using recursion?

Posted 04 February 2013 - 03:57 PM

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.

### #7 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12242
• Posts: 45,328
• Joined: 27-December 08

## Re: How to check tautology using recursion?

Posted 04 February 2013 - 04:34 PM

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