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

Упражнения

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

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

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

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

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

а)(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.

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

а) ((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).

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

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

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

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

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

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

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

а) (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).

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

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

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

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

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

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

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

а) (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.

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

а) (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