Равносильность формул алгебры высказываний

Две формулы алгебры высказываний F(X1, X2, …, Xn) и G(X₁,X₂,…, X_n) называются равносильными, если для любых наборов значений переменных X₁, X₂, …, X_n они принимают одинаковые логические значения. Т.е. равносильные формулы имеют одинаковые таблицы истинности. В этом случае будем писать: F(X₁, X₂, …, X_n)ºG(X₁, X₂, …, X_n) и читать: «Формула F(X₁, X₂, …, X_n) равносильна формуле G(X₁, X₂, …, X_n)».

Из определения следует, что если F(X₁, X₂, …, X_n) есть тавтология, то F(X₁, X₂, …, X_n)º1, и если F(X₁, X₂, …, X_n) есть противоречие, то F(X₁, X₂, …, X_n)º0.

Понятия “равносильность” и “тавтология” связаны между собой следующим образом.

Теорема1: FºG тогда и только тогда, когда ╞F«G.

Перечислим основные равносильности, где P, Q, R есть любые формулы алгебры высказываний:

1. PÚùPº1, PÙùPº0;

2. PÚ0ºP, PÚ1º1;

3. PÙ0ºP, PÙ1ºP;

4. ù ù ùPºP;

5. PÙQºQÙP;

6. PÚQºQÚP;

7. (PÙQ)ÙRºPÙ(QÙR);

8. (PÚQ)ÚRºPÚ(QÚR);

9. PÙ(QÚR)º(PÙQ)Ú(PÙR);

10. PÚ(QÙR)º(PÚQ)Ù(PÚR);

11. PÙPºP;

12. PÚPºP;

13. PÙ(QÚP)ºP;

14. PÚ(QÙP)ºP;

15. P→QºùPÚQ;

16. P«Qº(P→Q)Ù(Q→P);

17. P«Qº(PÙQ)Ú(ùPÙùQ);

18. ù(PÙQ)ºùPÚùQ;

19. ù(PÚQ)ºùPÙùQ;

20. A→BÙCº(A→B)Ù(A→C);

21. AÙB→CºA→(B→C);

22. A→ùBºB→ùA;