A logical formula is made-up of a succession of logical variables and logical operators. The logical variables are the lowercase letters of the English alphabet and can have value 1 (true) or 0 (false). The logical operators are:
| Negation (!) | Conjunction (&) | Disjunction (|) | Implication (->) | Equivalence (<->) |
| !0=1 |
0&0=0 | 0|0=0 | 0->0=1 | 0<->0=1 |
| !1=0 | 0&1=0 | 0|1=1 | 0->1=1 | 0<->1=0 |
| 1&0=0 | 1|0=1 | 1->0=0 | 1<->0=0 | |
| 1&1=1 | 1|1=1 | 1->1=1 | 1<->1=1 |
More specifically, we can define a logical formula as follows:
1. Any logical variable is a formula.
2. If P is a formula, then (!P) is also a formula.
3. If P and Q are formulas, then (P&Q), (P|Q), (P->Q) and (P<->Q) are formulas.
4. Any formula can be obtained only via rules 1., 2., 3.
We call a tautology a formula which has a true value (1) for any value of the variables that are entered into the formula.
We call a contradiction a formula which has a false value (0) for any value of the variables that are entered into the formula.
Task
Write a program that identifies the tautologies and contradictions from a given sequence of formulas.
Input Data
Input file formule.in will contain positive integer n on the first line, representing the total number of formulas in the file. Each of the following n lines will contain a formula.
Output Data
Output file formule.out will contain n lines, one for each formula of the input file. Line i will contain letter T (if the formula on line i+1 of the input file is a tautology ), letter C (if the formula on line i+1 of the input file is a contradiction) or letter N (if the formula on line i+1 of the input file is neither).
Constraints and Statements
| formule.in | formule.out |
|
5 |
T T N C N |
Time limit: 0.3 seconds/test
prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com