Упражнения. 2.1. Определите, является ли последовательность символов формулой:

2.1. Определите, является ли последовательность символов формулой:

а) ((PÙQ)R)®ùR;

б) ((P«Q)ÙR)®(PÚR);

в) ((ùP®Q)®(RÙ(QÚS)));

г) ((PÚùQ)®(RùS));

д) (P®(QÙR®P));

е) ù((ùPÙùQ)®(PÚ(RÙùS)));

ж) ((PÙ(ùQ®R))Ú((ùP«R)ÙùQ)).

2.2. Опустите возможно большее число скобок в следующих формулах:

а) (((ùP)ÙQ«R)Ú((S®P)ÙùQ));

б) ((P)Ù(ùQ)Ú(S))®(R);

в) ((ùQ)ÚR)Ù(ùS);

г) ((((PÚ(ùQ))®R)«P)Ú(PÙQ)).

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

а) P®QÙùRÚS;

б) P®ùQÚR®ùP®ùR;

в) ùPÙQ®R;

г) PÚùQ®ùRÙQ;

д) ùP«ùQÚRÙQ.

2.4. Вычислить значение формулы при указанных наборах значений логических переменных:

а) Q®(PÚR®(R®ùQ)), (P,Q,R)=(0,1,1); (P,Q,R)=(0,0,0);

б) ùP®QÙR«ù ù(PÚQ)®S, (P,Q,R,S)=(1,0,0,1); (P,Q,R,S)=(1,1,0,0).

2.5. Составьте таблицы истинности для следующих формул и определите вид формулы (тождественно истинная, тождественно ложная, выполнимая, опровержимая):

а) (P®Q)®((P®ùQ)®ùP);

б) ((P®Q)®P)®Q;

в) (P®Q)Ú(P®QÙP);

г) (PÙ(QÚùP))Ù((ùQ®P)ÚQ);

д) ((P®Q)®Q)®Q;

е) ((PÚùQ)®Q)Ù(ùPÚQ);

ж) P®QÙR®PÙùQ®ùR;

з) R®(ù(PÚR)Ù(ùPÚQ)).

2.6. Докажите, что следующие формулы выполнимы:

а) ù(P®ùP);

б) (P®Q)®(Q®P);

в) (Q®(PÙR))Ùù((PÚR)®Q);

г) ù((P«ùQ)ÚR)ÙQ;

д) (PÙQ)®((RÚQ)®(QÙùQ))

Решение:

в) Для доказательства воспользуемся определением выполнимой формулы. Необходимо найти хотя бы один набор значений логических переменных P, Q, R, при котором формула принимает значение 1. Допустим, что такой набор (P, Q, R) существует, т.е. при некоторых P, Q, R: Q®PÙR=1 и ù(PÚR®Q)=1. По определению операции отрицания: PÚR®Q=0. Тогда из таблицы истинности импликации видно, что Q=0, а PÚR=1. Дизъюнкция двух высказываний может принимать значение 1 в трех случаях. Выберем один из них, но так чтобы выполнялось условие, что Q®PÙR=1. Так как Q=0, то импликация независимо от PÙR будет равна 1. Следовательно P и R можем выбрать любые из следующих: P=0, R=1 или P=1, R=0 или P=1, R=1. Пусть P=1 и R=1.

Итак, нашелся такой набор значений логических переменных (P,Q,R)=(1,0,1), при котором формула принимает значение 1. Следовательно, по определению формула является выполнимой.

2.7. Докажите, что следующие формулы опровержимы:

а) ((X®(YÙZ))®(ùY®ùX))®ùY;

б) ((XÚY)ÚZ)®((XÚY)Ù(XÚZ));

в) ((XÚY)Ù((YÚZ)Ù(ZÚX)))®((XÙY)ÙZ);

г) (XÙY)Ú(XÙZ)Ú(YÙZ)Ú(UÙV)Ú(UÙW)Ú(VÙW)Ú(ùXÙùU);

д) (XÚY)®((ùXÙY)Ú(XÙùY)).

Решение: аналогично №2.6. Воспользоваться определением опровержимой формулы. Найти такой набор значений логических переменных, при котором формула принимает значение 0.

2.8. Решить логические уравнения:

а) ((P®QÙR)®(ùQ®ùP))®ùQ=0;

б) PÙù(ùQ®R)=1;

в) (PÙQÙR)®(ùPÚQÚùR)=0;

г) (PÚQ)Ù(ùPÚùQ)=0;

д) P«PÚQ=1;

е) (Q®R)®(PÚQ®PÚR)=0;

ж) ((P®QÚR)Ù(ùQ®S)ÙSÙP)®ùR=0;

з) (PÙQ)Ú(Q®P)Ú(P«R)=0;

Решение: а) По определению импликации это уравнение равносильно системе

(P®QÙR)®(ùQ®ùP)=1

ùQ=0

откуда

Q=1

(P®1ÙR)®(0®ùP)=1

Учитывая, что 0®ùP=1 при любом логическом значении P и то, что (P®1ÙR)®1=1 так же при любых значениях Pи R, то решением будет всякий набор значений логических переменных, в котором Q=1, а P и R – любой объект из множества {0;1}. Возможны следующие наборы:

(P, Q, R)=(1,1,1);

(P, Q, R)=(0,1,1);

(P, Q, R)=(0,1,0);

(P, Q, R)=(1,1,0).

2.9. Cоставив таблицы истинности, докажите, что следующие формулы являются тавтологиями:

а) P®ùP (закон исключенного третьего);

б) ù(PÙùP) (закон отрицания противоречия);

в) ù ùP«P (закон двойного отрицания);

г) P®P (закон тождества);

д) (P®Q)«(ùQ®ùP) (закон контрапозиции);

е) ((P®Q)Ù(Q®R))®(P®R) (правило цепного заключения);

ж) (P«Q)«(ùP«ùQ) (закон противоположности);

з) (PÙQ)«(QÙP) (коммутативность конъюнкции);

и) (PÚQ)«(QÚP) (коммутативность дизъюнкции);

к) ((PÙQ)ÙR)«(PÙ(QÙR)) (ассоциативность конъюнкции);

л) ((PÚQ)ÚR)«(PÚ(QÚR)) (ассоциативность дизъюнкции);

м) (PÙ(QÚR))«((PÙQ)Ú(PÙR)) (дистрибутивность конъюнкции относительно дизъюнкции);

н) (PÚ(QÙR))«((PÚQ)Ù(PÚR)) (дистрибутивность дизъюнкции относительно конъюнкции);

о) (PÙP)«P (идемпотентность конъюнкции);

п) (PÚP)«P (идемпотентность дизъюнкции);

р) (P®Q)«(ùPÚQ);

с) (P«Q)«((P®Q)Ù(Q®P));

т) (PÙ(QÚP))«P (первый закон поглощения);

у) (PÚ(QÙP))«P (второй закон поглощения);

ф) ù(PÙQ)«(ùPÚùQ) (первый закон де Моргана);

х) ù(PÚQ)«(ùPÙùQ) (второй закон де Моргана);

ц) (PÚQ)«(ùP®Q).

2.10. Составив таблицы истинности следующих формул, докажите, что они являются тавтологиями:

а) P®(Q®P);

б) (P®Q)®((P®(Q®R))®(P®R));

в) P®(Q®(PÙQ));

г) P®(PÚQ);

д) (PÙQ)®P;

е) (P®(QÙR))«((P®Q)Ù(P®R));

ж) ((P®Q)Ù(P®ùQ))®ùP;

з) (P®R)®((Q®R)®((PÚQ)®R)) (эта тавтология называется «разбор случаев»);

и) (P®Q)®((P®ùQ)®ùP);

к) ù ùP®P;

л) (P®Q)Ú(Q®P);

м) (P®Q)Ú((Q®P)®(P«Q));

н) ((P®Q)®P)®P;

о) (P«Q)®(P®Q);

п) (P®R)®((PÚQ)®(RÚQ));

р) (P®(Q®R))«(Q®(P®R)).

2.11. Докажите, что если формулы F и F®G являются тавтологиями, то и формула G является тавтологией, т.е. если ╞ F, ╞F®G, то╞G. (Правило вывода, называемое «модус поненс» (сокращенно MP)).

2.12. Докажите, что:

а) если ╞FÚG и ╞ùFÚH, то ╞ GÚH;

б) если ╞FÚG, ╞F®H, ╞G®K, то ╞HÚK;

в) если╞ùFÚG, ╞ ùGÚùH, то ╞F®ùH;

г) если ╞F, ╞F«G, то ╞G.

Решение: в) Пусть F(X₁, …, X_n), G (X₁,…, X_n), H(X₁,…, X_n) – формулы, о которых идет речь в теореме. Предположим, что формула F®ùH не является тавтологией. Это означает, что существуют такие конкретные высказывания A₁,…A_n, что высказывание F(А₁,…, А_n) истинно, а высказывание ùH(A₁,…, A_n) ложно. Тогда высказывание ùF(А₁,…, А_n) ложно. Далее, так как формула ùFÚG является тавтологией, то высказывание G(А₁,…, А_n) истинно. Но с другой стороны, поскольку ùGÚùH – тавтология, то высказывание ùG(А₁,…, А_n) истинно. Получили противоречие. Следовательно, наше предположение оказалось неверным, а значит F®ùH – тавтология.

2.13. Доказать методом от противного общезначимость следующих формул:

а) ùP®(P®Q);

б) P®(Q®PÙQ);

в) ((P®Q)Ù(Q®R))®(P®R);

г) (ùP®ùQ)«(Q®P);

д) (PÙQ®R)«(PÙùR®ùQ);

Решение: в) Пусть данная формула не общезначима, тогда должно иметь решения уравнение: ((P®Q)Ù(Q®R))®(P®R)=0. Это уравнение равносильно системе:

(P®Q)Ù(Q®R)=1

P®R=0

P®Q=1

Q®R=1

P®R=0

P=1

R=0

1®Q=1

Q®0=1

Два последних уравнения противоречат друг другу. Следовательно, наше предположение оказалось неверным, а значит формула является тавтологией.