DWITE
December 2011
Problem 5
Tautology

We define a propositional formula as follows:

• {a,b,...j} are atomic propositions, representing either true or false.
• If A and B are propositional formulae, then so are:
• (A ^ B) -- ^ is boolean "and"
• (A v B) -- v is boolean "or"
• ~A -- ~ is boolean "not"

For example, ((a v b) ^ (~c v a)) is a propositional formula. A tautology is a propositional formula that equates to true for all possible value assignments to the atomic propositions. Our previous example ((a v b) ^ (~c v a)) is not a tautology because for the assignments a = false, b = false and c = true, the formula evaluates to a false. However (a v ~a) is a tautology because no matter what the atomic proposition is this equates to true; (true or not-true) == true, (false or not-false) == true.

The input file DATA5.txt will contain 5 test cases, each three lines (not more than 255 characters) with a propositional formula per line.

The output file OUT5.txt will contain 5 lines of output, each three characters long. Y for tautology, N for not tautology.

Sample Input (first 2 shown):
```
((a v b) ^ (~c v a))
(a v ~a)
~(a ^ ~a)
a
~b
((a ^ b) v ~(c ^ ~c))
```
Sample Output (first 2 shown):
```
NYY
NNY
```