logic

Logic

== include(page="template/taskheader" task_id="logic") ==

Mircea cel Tanar trebuie sa imbunatateasca permanent performantele calculatoarelor pe care le are in gestiune. Se intampla cateodata, ca unele componente noi pe care le foloseste sa nu fie compatibile cu vechile calculatoare. Din acest motiv functionarea calculatoarelor "imbunatatite" poate sa nu fie corecta. Pentru a verifica corectitudinea functionarii acestor calculatoare, Mircea isi propune sa le testeze cu  ajutorul unui program care verifica echivalenta unor expresii logice.

Mircea cel Tanar trebuie sa imbunatateasca permanent performantele calculatoarelor pe care le are in gestiune. Se intampla cateodata, ca unele componente noi pe care le foloseste sa nu fie compatibile cu vechile calculatoare. Din acest motiv functionarea calculatoarelor "imbunatatite" poate sa nu fie corecta. Pentru a verifica corectitudinea functionarii acestor calculatoare, Mircea isi propune sa le testeze cu ajutorul unui program care verifica echivalenta unor expresii logice.

Scrieti un program care determina daca doua expresii logice sunt echivalente sau nu.
Fiecare expresie este formata din:

Expresiile vor fi evaluate respectand regulile de prioritati ale operatorilor si parantezelor pentru evaluarea expresiilor logice in care intervin ca operanzi bitii $0$ si $1$. Prioritatile in ordine descrescatoare sunt: parantezele rotunde " $($", " $)$", operatorul unar " $~$", operatorii binari in ordine descrescatoare " $&$", " $^$", " $|$".
Doua expresii sunt echivalente daca:

Doua expresii sunt echivalente daca:
 
* contin acelasi set de variabile indiferent de numarul de aparitii a variabilei in expresie;

* contin acelasi set de variabile indiferent de numarul de aparitii al acestora;

* pentru orice set de date de intrare pentru variabile (valori $0$, $1$) rezultatul obtinut este acelasi.

h2. Restrictii si precizari

* $0<n &le; 50$

* $1 ≤ n ≤ 50$

* $n$ reprezinta numarul de perechi de expresii ce trebuie evaluate.
* O expresie contine cel mult $100$ de operatii si maxim $10$ variabile.
* O expresie poate avea cel mult $255$ caractere. Spatiul nu este separator in interiorul unei expresii.

h2. Exemplu

table(example). |_. logic.in |_. logic.out |_. Explicatie|

table(example). |_. logic.in |_. logic.out |

| $4$
$a&(c|~c)$
$a$
$~(a|b|c|d)$

$~a~b&~c&~d$

$~a&~b&~c&~d$

$z&b$
$a&b$
$a|b$

|diferite
egale
diferite

egale
|Pentru ultimul set de expresii tabelul este:

egale |

 a  b  ~a  a|~a  (a|~a)&(a|~a)&(a|~a) a|b  E
 0  0  1    1       1                  0   0
 0  1  1    1       1                  1   1
 1  0  0    1       1                  1   1
 1  1  0    1       1                  1   1

h3. Explicatie

 unde E=(a|~a)&(a|~a)&(a|~a)&(a|b) |

Pentru ultimul set de expresii tabelul este:
|_. a |_. b |_.  ~a |_.  a|~a |_. (a|~a)&(a|~a)&(a|~a) |_. a|b |_. E |
| 0  | 0  | 1 | 1 | 1 | 0  | 0  |
| 0  | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0  | 0  | 1 | 1 | 1 | 1 |
| 1 | 1 | 0  | 1 | 1 | 1 | 1 |
 unde $E=(a|~a)&(a|~a)&(a|~a)&(a|b)$

==include(page="template/taskfooter" task_id="logic") ==

1880