DWITE Online Computer Programming Contest


December 2011
Problem 5
XKCD Tautology Club


We define a propositional formula as follows:

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, c = true}, the formula evaluates to 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 long (not more than 255 characters per line) 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) v (c ^ ~c))
Sample Output (first 2 shown):