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"
  • ~\neg A~ — ~\neg~ is boolean "not"

For example, ~((a \vee b) \wedge (\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 (\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 \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 ~\neg~, ^ for ~\wedge~, and v for ~\vee~.

Sample Output

NYY
NNY

Problem Resource: DWITE