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

Две формулы алгебры высказываний 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;

Упражнения

1. Докажите теорему 1 §4.

2. Производя равносильные преобразования с использованием основных равносильностей, докажите, что все формулы из задачи 2.10 являются тавтологиями.

3. Докажите методом равносильных преобразований следующие равносильности:

а) P(PR)(QR)(PR)(PQ);

б) (PQ)→(PR)(PR)(PQ)(QP);

в) (PQR)(QRS)(RSP)P((Q(RS))(SR));

г) (P→(QR))(S→(PQ))(R→Q)(S→R)(Q→R)QRS.

4. Применяя равносильные преобразования, приведите следующие формулы к возможно более простой форме:

а)(PQ)→((PQ)→P);

б) (PQ)((P→Q)P);

в) (P→Q)(Q→P)(PQ);

г) (P→Q)(Q→P)(R→P);

д) (PR)(PR)(QR)(PQR);

е) ((P→Q)(Q→P));

ж) (P→(QR))(Q→S)(SP→R)→Q.

5. Следующие формулы преобразуйте равносильным образом так, чтобы они содержали только операции: , , :

а) ((X→Y)(Y→X))→(XY);

б) ((X→Y)(Y→X))→(Z→X);

в) ((XY)(XY))→((XY)(XY));

г) ((XY)→Z)→(XZ);

д) (X→(YZ))((X→Y)Z).

6. Следующие формулы преобразуйте равносильным образом так, чтобы они содержали только операции  и :

а) (XY)→(X→Z);

б) (X→Y)(X→Y);

в) ((XYZ)→X)Z;

г) ((X→Y)→Z)→X;

д) (X(Y→Z))→X.

7. Следующие формулы преобразуйте равносильным образом так, чтобы они содержали только операции  и :

а) (X→Y)→(YZ);

б) (XY)→(XY);

в) ((XY)Z)→(ZY);

г) ((X→(YZ))→(Y→X))→Y;

д) ((X→Y)(Y→Z))→(X→Z).

8. Следующие формулы преобразуйте равносильным образом так, чтобы отрицание было отнесено только к пропозициональным переменным и не стояло бы над скобками:

а) ((X(YZ))Z);

б) ((XY)Z)→(XZ);

в) (U→(Z(YX)));

г) (((XY)→Y)→(XZ));

д) ((X(YZ)Z)(YZ)).

9. Найдите отрицание каждой из следующих формул:

а) (X(YZ))(XY);

б) ((XYZ)R)UVW;

в) (((X(YZ))P)Q)(R(ST));

г) ((X(Y(ZP)))Q)R.

10. С помощью равносильных преобразований докажите, что следующие формулы являются тождественно ложными:

а) (X→Y)(Y→X)((XY)(XY));

б) ((XY)→(X(XY)))((X(XY))→(XY));

в) ((X→Y)(Y→Z))→(X→Z);

г) (X→Y)(X→Y)X;

д) ((XY)(XZ))((X→Y)(X→Z)).

Решение:

а) Покажем, что эта формула равносильна 0 (ложному высказыванию):

(X→Y)(Y→X)((XY)(XY))(XY)(YX)((XY)(XY))((XY)(YX)(XY))((XY)(YX)(XY))((XY)(YX)(XY))((XY)(YX)(XY))(0(YX))(0(XY))000