logo
методичка мат лог

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

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

Из определения следует, что если F(X1, X2, …, Xn) есть тавтология, то F(X1, X2, …, Xn)1, и если F(X1, X2, …, Xn) есть противоречие, то F(X1, X2, …, Xn)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;