formule

Една логическа формула представлява последователност от логически променливи и логически операции. Логическите променливи са малки букви от английската азбука и могат да имат стойности 1 (true) или 0 (false). Логическите операции са:

Отрицание (!)

Конюнкция (&)

Дизюнкция (|)

Импликация (->)

Еквивалентност (<->)

!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

По-конкретно логическа формула се дефинира по следния начин:
1. Всяка логическа променлива е формула.
2. Ако
P е формула, то (!P) също е формула.
3. Ако
P и Q са формули, то (P&Q), (P|Q), (P->Q) и (P<->Q) са формули.
4. Всяка формула може да бъде получена с правилата 1., 2., 3.
Една формула се нарича тавтология, ако има стойност true (
1) за произволни стойности на променливите, участващи във формулата.
Една формула се нарича противоречие, ако има стойност
false (0) за произволни стойности на променливите, участващи във формулата.

Задача

Напишете програма, която определя тавтологиите и противоречията сред дадено множество от формули.

Вход

Входният файл formule.in съдържа на първия ред положително цяло число n, представляващо общия брой формули във файла. На всеки от следващите n реда има по една формула.

Изход

Изходният файл formule.out трябва да съдържа n реда, по един за всяка формула от входния файл. Ред i трябва да съдържа буква T (ако формулата от ред i+1 от входния файл е тавтология),  буква C (ако формулата от ред i+1 от входния файл е противоречие) или буква N (ако формулата от ред i+1 от входния файл не е нито тавтология, нито противоречие).

Ограничения

Пример

formule.in

formule.out

5
((b->a)<->((!a)->(!b)))
((!(a|b))<->((!a)&(!b)))
a
(a<->(!a))
((a&b)&c)

T
T
N
C
N

Ограничение за време: 0.3 секунди на тест

prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
За връзка :emanuela.cerchez@gmail.com

(превод на български: Стоян Капралов)