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

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

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

4.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.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.

4.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).

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

а) (XÚY)→(ùX→Z);

б) (ùX→Y)Úù(X→Y);

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

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

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

4.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).

4.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)).

4.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.

4.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