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: sau 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 „A1opA2op...opAK” asociaţiile se fac de la dreapta la stânga (adică „A1op(A2op(...opAL)...)”), unde op este unul dintre &, |, => sau <=> şi Ai sunt variabile propoziţionale, cu i de la 1 la K.
Î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 A1, A2, ..., AN) orice N-uplu (v1, v2, ..., vN) (cu vi valori de adevăr) pentru care înlocuind fiecare variabilă Ai cu valoarea vi, 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
In 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, urmat de caracterul sfârşit de linie.
Restricţii
La intrare se va da intotdeauna 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.
