We define the logic operators as follows (T stands for true, F stands for false)
!T = F, !F = T
T & T = T, T & F = F, F & T = F, F & F = F
T | T = T, T | F = T, F | T = T, F | F = F
T -> T = T, T -> F = F, F -> T = T, F -> F = T
In fact, all the logic expressions can be rewritten only using '!' and '→'. For example, A | B
is equivalent to !A → B
Given some expressions only contain '!', '→', '(' and ')', you should tell whether they are tautologies. ("Tautologies" means that no matter what values the variables are, the expression is always true.)
Please note the priority of '!' is higher than '→', e.g., !A→B
should be considered as (!A)→B
. And multiple '→' bind from left to right, e.g., A→B→C
should be considered as (A→B)→C
. However, !!A
should be considered as !(!A)
Each line of the input contains one expression. The operators includes '!', '->', '(', ')', only. And there are 3 variances A,B,C at most.
You can assume all expressions are valid, and contain no more than 100 characters.
Output one line for each case. If the expression is tautologies, output "tautologies", or else output "not tautologies".