М. С. Спирина - Учебно-методическое пособие по дисциплине «Математическая логика и теория алгоритмов» для студентов технических направлений и специальностей

 1, ( A  B )  ( A  B )  ;
в) A  B  0,  B  A  ;
г) A  B  0, A  B  1, B   A  ;
д) A  B  0, A  B  1, ( A  B )  A  ;
е) A  B  1, A  B  1, B  A  ;
ж) A  B  0, A  B  0, A  B  1, A  ;
з) A  B  0, A  B  0, A  B  1, B  ;
и) A  B  0, A  B  1, A  B  1, B  A  ;
к) A  ( B  A)  0, A  B ;
Задание: 1.7. Составьте таблицу истинности для формулы (( P  Q )  Q )( P  Q ) и
укажите, является ли она выполнимой, опровержимой, тождественно истинной
(тавтологией) или тождественно ложной (противоречием).
Решение: Пользуясь определениями логических связок, составим таблицу
истинности данной формулы (логические значения этой формулы записаны в последнем
столбце таблицы, где сама формула обозначена F (P, Q)):
P

Q

Q

P

PQ

F (P, Q)

0

0

1

1

0

1

1

0

0

1

0

0

1

1

1

1

1

0

1

1

0

0

0

0

1

1

0

1

1

0

1

1

PQ

(P  Q)  Q

Из построенной таблицы истинности видно, что данная формула выполнима, так как
если, например, вместо пропозициональной переменной Р вставить в формулу ложное
высказывание, а вместо Q – истинное, то вся формула превратится в истинное
высказывание. Но эта формула является также и опровержимой, поскольку если,
например, вместо пропозициональной переменной Р вставить в формулу истинное
высказывание, а вместо переменной Q – ложное, то вся формула превратится в ложное
высказывание. Следовательно, формула не является ни тавтологией, ни тождественно
ложной формулой.
Задание 1.8. Выполните задание по образцу задания 1.7. Составьте таблицы
истинности для следующих формул и укажите, какие из формул являются выполнимыми,
какие – опровержимыми, какие – тождественно истинными (тавтологиями), какие –
тождественно ложными (противоречиями):
б) (( P  Q )  P )  Q;
а) ( P  Q )  (( P  Q )  P );
в) ( P (Q  P ))((Q  P )  Q );
д) PQ ( P  Q );
ж) (((P  Q )(Q  R ))  R )  Q;
и) ( R  P  Q  R )  P  Q;

г) (( P  Q )  Q )  ( P  Q );
е) ((( P  Q )  Q )  Q )  Q;
з) ( P (Q  R ))  (( R  ( P  Q ))  (Q  ( R  P )));
к) ((( P  Q )  ( P  R ))  (Q  R ))  P.

Задание 1.9. (1.32) Докажите, что:
а) если |= F  G , |= G  H , то |= F  H ;
б) если |= G  F , |= (F  H )  G , |= H, то |= G  H .
Решение. а) Пусть F ( X 1 , ..., X n ), G ( X 1 , ..., X n ), H ( X 1 , ..., X n ) – формулы, о которых
идет речь в этой задаче. Предположим, что формула F  H не является тавтологией.
6

Это означает, что существуют такие конкретные высказывания A1 , ..., An , что
высказывание F ( A1 , ..., An ) истинно, а высказывание H ( A1 , ..., An ) ложно. Тогда
высказывание F ( A1 , ..., An ) ложно. Далее, так как формула F  G является
тавтологией, то высказывание G ( A1 , ..., An ) истинно. Но с другой стороны, поскольку
G  H – тавтология, то высказывание G ( A1 , ..., An ) истинно. Получили
противоречие. Следовательно, формула F  H – тавтология.
б) Предположим, что посылка данного утверждения верна, а заключение нет, т.е.
формулы G  F , (F  H )  G и H являются тавтологиями, а формула G  H – нет.
Последнее означает: найдутся такие конкретные высказывания A1 , ..., An , что
высказывание G ( A1 , ..., An )  H ( A1 , ..., An ) будет ложным. Это, в свою очередь, возможно
лишь в том случае, когда, по меньшей мере, одно из высказываний G ( A1 , ..., An ) или
H ( A1 , ..., An ) будет ложным. Высказывание H ( A1 , ..., An ) ложным быть не может,
поскольку это противоречило бы тождественной истинности формулы H ( X 1 , ..., X n ).
Следовательно, ложно высказывание G ( A1 , ..., An ) и, значит, истинно высказывание
G ( A1 , ..., An ). В таком случае из истинности высказывания G ( A1 , ..., An )  F ( A1 , ..., An )
вытекает истинность высказывания F ( A1 , ..., An ).
Рассмотрим высказывание (F ( A1 , ..., An )  H ( A1 , ..., An ))  G ( A1 , ..., An ), которое
истинно, т.к. формула (F  H )  G , по предположению, является тавтологией. Т.к.
истинно высказывание F ( A1 , ..., An ) , то левая часть рассматриваемой эквивалентности
есть ложное высказывание. Значит, ее правая часть, т.е. высказывание G ( A1 , ..., An ),
также ложна. Но это противоречит ранее установленной истинности этого высказывания.
Т.о., сделанное допущение приводит к противоречию. Следовательно, допущение
неверно, а верно доказываемое утверждение.
Задание 1.10. (1.32) Выполните задание по образцу задания 1.9. Докажите, что:
а) если |= F  G , |= F  G , то |= G  H ;
в) если |= F  G , |= G  H , то |= H  F ;
д) если |= G  H , |= F  G , то |= F  H ;
ж)если |= F, |= F  G , |= F  H , то |= G  H ;
и) если |= F, |= G, |= H, то |= F  (G  H );

б) если |= F  G , |= G  H , то |= F  H ;
г) если |= F  G , |= F  G , то --">