DWITE, December 2011, Problem 5

We define a propositional formula as follows:

• $\{a,b,\dots ,j\}$ are atomic propositions, representing either true or false.
• If $A$ and $B$ are propositional formulae, then so are:
  • $A\wedge B$ — $\wedge$ is boolean "and"
  • $A\vee B$ — $\vee$ is boolean "or"
  • $\mathrm{\neg }A$ — $\mathrm{\neg }$ is boolean "not"

For example, $((a\vee b)\wedge (\mathrm{\neg }c\vee 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\vee b)\wedge (\mathrm{\neg }c\vee a))$ is not a tautology because for the assignments $a=\text{false}$, $b=\text{false}$ and $c=\text{true}$, the formula evaluates to a false. However $(a\vee \mathrm{\neg }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 will contain 5 test cases, each three lines (not more than 255 characters) with a propositional formula per line.

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

Sample Input

((a v b) ^ (~c v a))
(a v ~a)
~(a ^ ~a)
a
~b
((a ^ b) v ~(c ^ ~c))

Note that ~ is used for $\mathrm{\neg }$, ^ for $\wedge$, and v for $\vee$.

Sample Output

NYY
NNY

Problem Resource: DWITE