Logic

Demonstrarea automată a teoremelor şi verificarea satisfiabilităţii unei formule constituie două capitole importante în cadrul logicii matematice. Formulele propoziţionale sunt alcătuite din variabile propoziţionale (variabile care pot lua doar două valori: "adevărat" sau "fals") şi din operatorii logici "şi", "sau", "negaţie", "echivalent", "implică".

Iată câteva exemple de formule propoziţionale:

• ~p&(q<=>p)=>q
• p|q<=>~p&~q
• p
• p=>q=>a=>t=>~p

În acest exemplu, p şi q sunt variabilele propoziţionale, ~ este operatorul unar "negaţie", & este operatorul binar "şi", | este operatorul binar "sau", => este implicaţia logică (şi apare numai în acest sens, nu şi <=), iar <=> este echivalenţa logică. În plus, într-o formulă propoziţională pot să apară şi paranteze care stabilesc ordinea operaţiilor. În lipsa parantezelor, operatorii în ordinea priorităţii lor sunt ~, &, |, =>, <=>.

În formulele de forma $[A_1 \ op \ A_2 \ op \ \dots \ op \ A_K]$, asociaţiile se fac de la dreapta la stânga, adică $[A_1 \ op \ (A_2 \ op \ (\dots \ op \ A_K))]$, unde $op$ este unul dintre &, |, =>, <=> şi $A_i$ sunt variabile propoziţionale. În general, o formulă propoziţională se defineşte astfel:

• orice variabilă propoziţională este formulă propoziţională;
• dacă A şi B sunt formule propoziţionale, atunci (A), ~A, A&B, A|B, A=>B, A<=>B sunt formule propoziţionale.

Dacă înlocuim într-o formulă propoziţională toate variabilele cu valori de adevăr ("adevărat" sau "fals"), obţinem o afirmaţie. Valoarea de adevăr a unei afirmaţii este dată de următoarea definiţie:

• dacă afirmaţia constă dintr-o singură valoare de adevăr, afirmaţia ia valoarea respectivă;
• dacă A şi B sunt afirmaţii, atunci:
  • A este adevărată dacă şi numai dacă valoarea sa de adevăr este "adevărat";
  • (A) este adevărată dacă şi numai dacă A este adevărată;
  • ~A este falsă dacă şi numai dacă A este adevărată;
  • A&B este adevărată dacă şi numai dacă atât A cât şi B sunt adevărate;
  • A|B este falsă dacă şi numai dacă A este falsă şi B este falsă;
  • A=>B este adevărată dacă şi numai dacă ~A|B este adevărată;
  • A<=>B este adevărată dacă şi numai dacă (A=>B)&(B=>A) este adevărată.

Se numeşte soluţie a formulei propoziţionale $P$ (formulă în care apar numai variabilele propoziţionale distincte $A_1, A_2, \dots, A_N$) orice $N$-uplu $(v_1, v_2, \dots, v_N)$ format doar din valori de adevăr pentru care, înlocuind fiecare variabilă $A_i$ cu valoarea $v_i$, afirmaţia rezultată este adevărată.

Cerinţă

Logica fiind un obiect nesuferit de studenţii de la informatică, ei apelează la informaticienii din clasa a IX-a pentru a-i ajuta să numere câte soluţii distincte are o formulă propoziţională dată.

Date de intrare

În fişierul de intrare logic.in, se găseşte o formulă propoziţională unde variabilele propoziţionale sunt reprezentate de litere mici ale alfabetului englez.

Date de ieşire

În fişierul de ieşire logic.out, se va afişa numărul de soluţii pentru formula propoziţională din fişierul de intrare.

Restricții și precizări

• La intrare se va da întotdeauna o formulă propoziţională corectă sintactic.
• Formula are mai puţin de $232$ de caractere.
• În formulă nu apar mai mult de $10$ litere mici ale alfabetului latin.

Exemplul 1

logic.in

p|q<=>~p&~q

logic.out

4

Exemplul 2

logic.in

a

logic.out

1