![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
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
Дата публикования: 2015-03-26; Прочитано: 1165 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!