O formula
logica este constituita dintr-o succesiune de variabile logice si operatori
logici. Variabilele logice sunt litere mici ale alfabetului englez si pot avea
valoarea 1 (adevarat) sau 0
(fals). Operatorii logici sunt:
Negatie (!)
Conjunctie (&)
Disjunctie (|)
Implicatie (->)
Echivalenta (<->)
!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
Mai exact,
putem defini o formula logica astfel:
1. Orice variabila logica este o formula.
2. Daca P este o formula, atunci
(!P) este de asemenea o formula.
3. Daca P si Q
sunt formule, atunci (P&Q),
(P|Q), (P->Q)
si (P<->Q) sunt formule.
4. Orice formula se obtine numai prin regulile 1., 2., 3.
Se numeste tautologie o formula care are valoarea adevarat (1)
pentru orice valori ale variabilelor care intervin în formula.
Se numeste contradictie o formula care are valoarea fals (0)
pentru orice valori ale variabilelor care intervin în formula.
Cerinta
Scrieti un program care
sa identifice tautologiile si contradictiile într-un sir de formule dat.
Date de
intrare
Fisierul de intrare formule.in
va contine pe prima linie un numar natural n,
care reprezinta numarul de formule din fisier. Pe fiecare dintre urmatoarele
n linii va fi scrisa o formula.
Date de
iesire
În fisierul de iesire
formule.out vor fi scrise n
linii, câte una pentru fiecare formula din fisierul de intrare. Pe linia
i va fi scrisa litera T
(daca formula de pe linia i+1
din fisierul de intrare este o tautologie), litera C
(daca formula de pe linia i+1
din fisierul de intrare este o contradictie) sau litera N
(daca formula de pe linia i+1
din fisierul de intrare nu este nici tautologie, nici contradictie).
Restrictii si precizari
n <= 10
Lungimea unei formule
este <= 200
Numarul de variabile
distincte care pot interveni într-o formula este <=
15.
Exemplu
formule.in
formule.out
5 ((b->a)<->((!a)->(!b)))
((!(a|b))<->((!a)&(!b)))
a
(a<->(!a))
((a&b)&c)