DWITE, December 2011, Problem 5
We define a propositional formula as follows:
are atomic propositions, representing either true or false.
- If
and
are propositional formulae, then so are:
—
is boolean "and"
—
is boolean "or"
—
is boolean "not"
For example, 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
is not a tautology because for the assignments
,
and
, the formula evaluates to a false. However
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 ,
^
for , and
v
for .
Sample Output
NYY
NNY
Problem Resource: DWITE
Comments