Ответы и решения к главе 4

Задача 4.3. Следующие формулы являются тавтологиями:

т :(Л^(В^А))-Я2:(А^(А^ А))

ЯЗ : (Л -> А);

Я5:(А^(А -> А)).

Задача 4.4. Следующие формулы являются тавтологиями:

т :(А^(В^ А))-

Я2 : (('ВА)В -> А) -> В));

ЯЗ : ((В -> А) ((В -> А) -> В));

Я5 : ((В -> А) -> ((В -> Д) -> В)).

Задача 4.5. Следующие формулы являются тавтологиями

т : ((А -» С)) -> ((А —> Д) —> (Л —> С)));

Д2 : (04 -»(Д -» С)) -»(04 -» 5) -» Й -» С)));

ДЗ : (04 ->(Я -> С)) -> ((Л С)));

Д5 : (04 ->(5 -> С)) -> ((Л -> 5) -> (Л -> С))).

Задача 4.6. Следующие формулы не являются ни противоре чиями, ни тавтологиями:

Д1: (А -> (Д -» Л));

Д2 : (Л -> (Л -> Л));

Д4 :(А^(В^ А)).

Задача 4.7. Следующие формулы не являются ни противоре чиями, ни тавтологиями:

Д1 :(А ->(Д-» Л));

Д2 : ((В -*А)^> ((В -> А) -> В));

Д4 : ((В ^А)^ ((В ^>А)^> В)).

Задача 4.8. Следующие формулы не являются ни противоре чиями, ни тавтологиями:

Я : ((А -» С)) -> ((/4 -> В) -> Й -> С)));

Д2 : ((Л ^ (Д ^ С)) -> (Й ^ В) ^ (А ^ С)));

Д4 : ((А ->(5 -> С)) -> (Й —> В)—> (А —> С))).

Задача 4.9. Следующие формулы являются противоречиями:

Д2 : ((Л -> (Л -> у4)) -> Л -» /4);

ДЗ : ((А -> >4) -> (Л -> Л)).

Задача 4.10. Следующие формулы являются противоречиями: ДЗ : (((А -» (Д -> С)) -> ((/4 -> Д) -> (Л -> С))) -» Л -» /4);

Д5 : (((у4 ->(В -> С)) -> ((у4 -> В) ^ (А-> С))) -> Л -» Л). Задача 4.11. Аксиомы исчисления высказываний:

4 : 04 -> (Д -> А));

Л2 : ((>4 -> (Д -> С)) -> ((/4 -> Д) -> (/4 -> С)));

>43 : ((В ->А)-> ((В -» /4) -» Д)).

Хх

Задача 4.19. Смотри рис. 7.4.2.

Задача 4.20. Смотри рис. 7.4.3.

Хх

Задача 4.22. Формула выполнима на множестве Х= {2}, У= {-2}.

Задача 4.23. Формула является общезначимой, выполнима на любом множестве.

Задача 4.24. Формула является противоречием; не существует области, на которой она выполнима.

Задача 4.25. Формула выполнима на множестве У= {-2}.

Задача.4.26. Формула выполнима на множестве Х= {-2}, У= {-2}.

Задача 4.27. Формула является общезначимой, выполнима на любом множестве.

Задача 4.28. Формула является противоречием; не существует области, на которой она выполнима.

Задача 4.29. Формула является противоречием; не существует области, на которой она выполнима.

Задача 4.30. Аксиомы исчисления предикатов:

А : -> А))-

Л2 : ((А -> -> С)) -> ((А -> В) -> -> С)));

А : ((В ^ Л) ^ ((В -> А) -> В));

/>, : Vx4(x) -> ДО;

Р2 : ДО —» ЗхДх).

Я : ЗхР(х) = /хР(х)

Я2 : ЗхР(х) = /хР(х);

ЯЗ : УхР(х) = ЗхР(х);

Я4 : /хР(х) = ЗхР(х).

Задача 4.32. Следующие формулы равносильны:

Я : Ух(Р(х) & 0(х)) = УхР(х) & fxQix);

ЯЗ : Зх(/>(х) V 0(х)) = ЗхР(х) V 3х0(х);

Р5 : /х/уР(х, у) = /у/хР(х, у);

Я7 : ЗхЗуР(х, у) = ЗуЗхР(х, у).

Задача 4.33. Следующие формулы равносильны:

Я2 : ЗхР(х) = /хР(х);

Я4 : ЗхЗуР(х, у) = ЗуЗхР(х, у);

Я6 : УхР(х) = 3х~Р(х);

/?8 : Ух(Р(х) & 0(х)) = УхР(х) & Ух0(х).

Задача 4.34. Следующие формулы равносильны:

ЯЗ : Ух(С V 0(х)) = Cv VxQ(x);

Я4 : 3 х(С & 0(х)) = С& 3х0(х);

Я6 : /хР(х) = ЗхР(х).

Задача 4.35. Следующие формулы равносильны:

ЯЗ : Ух(С 0(х)) = С -> VxQ(x);

Я4 : Зх(С —> (2(х)) = С —> Зх(7(х);

Я7 : Ух(С & 0(х)) = С & УхО(х).

Задача 4.36. Следующие формулы равносильны:

ЯЗ : Ух(С0(х)) = С -> VxQ(x);

Я4 : 3х(С —> 0(х)) = С —> ЗхО(х).

Задача 4.37. Следующие формулы равносильны:

ЯЗ : Ух(С -> 0(х)) = С -> УхО(х)-Я4 : Зх(С —> (7(х)) = С —> Зх(7(х);

RI: Vx(C & Q(x)) = C & VxQ(x);

R2 : 3xP(x) = VxP(x).

Задача 4.38. Следующие формулы равносильны:

R3 : Vjc(C -> Q(x)) = С —> VxQ(x);

R4 : Зх(С —> Q(x)) = C —> 3x0(x);

RI: V*(C & Q(x)) = C& VxQ(x).

Задача 4.48. Не равносильны.

Задача 4.49. Равносильны, так как

3x(Q(x) —> С) = 3x(Q(x) v С) = 3xQ(x) v С = 3xQ(x) v С =

= VxQ(x) v С = VxQ(x) -> С.

Задача 4.50. Равносильны.

Задача 4.51. Прямой логический вывод:

Vx(R(x)Р(х))(VxR(x) -» Vx/>(x)) =

= Vjc(?(x) V />(*)) V (VxR(x) V VxP(x)) =

= 3x(R(x) & P??) v VxR(x) v VxP(x) =

= 3x(R(x) & P??) v Зх Дфс) v VxP(x) =

= 3x(/?(.x) & P(x) v /?(x)) v /xP(x) =

= 3x(P(x) v R(x)) v /xP(x) =

= Зх/Дх) v 3x/?(x)) v 3xP(x) = 1.

Если формула тождественно истинна на любой области, значит, она общезначима. Ч.т.д.

Задача 4.52. Доказательство строится на основе правила подстановки и выводимости А —> А (теоремы 4.1 и 4.2).

Задача 4.53. Прямой логический вывод:

R : (((А ->(ss-> С)) -> ((А -» Я) -» (Л -» С)))А -> А =

= (((Л v(Bv С)) v ((? vss)v(?v С))) v?vA =

= A& B& CvA&BvAvCv0=BvBvAvC = l = 0.

Если формула тождественно ложна на любой области, то она является противоречием. Ч.т.д.

Задача 4.54. Предположим, что формула является противоречием или тавтологией. Тогда

Ri: ((А С)) -> ((А -> В) -> (А -> С))) =

= {(? v (В v С)) v ((I v 5) v v С)) =

= ,4&i?&Cvy4&Z?vylvC = ,4vi?vC.

Получили, что при у4=1,5=1,С=0/?1 = 0; при А = 0, 5 = О, С = 1 /И = 1.

Таким образом, мы получили противоречие, и верно то, что R1 не является ни противоречием, ни тавтологией. Ч.т.д.

Задача 4.55. Прямой логический вывод:

Ri : ((А -» С)) -» ((Л -> 5) -> (Л -» О) =

= (Л v v С) v (у4 v В v /4 v С) =

= ^& 5& Cv>l&5vy4vC=y4v5vC.

Получили, что при Л=1,/?=1,С=0/?1=0; при Л = О, 5 = 1, С = 0 /И = 1.

Таким образом, R1 не является ни противоречием, ни тавтологией. Ч.т.д.

Задача 4.56. Предположим, что формула не является тавтологией. Тогда

R : ((А -> -> С)) -> ((Л ^>В)^>(А^> С))) =

= Av(BvC)vAvBvAvC =

= A& B& CvA&BvAvC = AvAvA&BvC = i.

Таким образом, мы получили противоречие, и верно то, что Ri является тавтологией. Ч.т.д.

Задача 4.60. Положим, что формула общезначима.

Тогда в случае Q(X) = Р(х) левая часть формулы равна тождественно истинному высказыванию

/х(Р(х) v Q(x)) = /х(Р(х) v Р(х)) = Vx(l) = 1.

Правая часть формулы

/хР(х) v VxQ(x) = /хР(х) v /хР(х) = 0 v 0 = 0.

Получили противоречие, и верно то, что формула не общезначима. Ч.т.д.

Задача 4.61. Положим, что формула общезначима.

Тогда в случае Q(X) = Р(х) левая часть формулы равна тождественно ложному высказыванию

Зх(Р(х) & Q(x)) = Зх(Р(х) & Р(х)) = 3х(0) = 0. Правая часть формулы

ЗхР(х) & 3х0(х) - ЗхР(х) & ЗхР(х) = 1 & 1 = 1.

Получили противоречие, и верно то, что формула не общезначима. Ч.т.д.

Задача 4.62. Базис индукции. Пара (2,2) принадлежит ДАО, так как гез(2 + 1, 1)= 1.

Индукционный переход. Пара (/, /) принадлежит ДА0, так как гевО' +1,/) = гев((/ + 1 )/0 = гез(/// +1/0=1.

Пара (/+ 1, /+ 1) принадлежит ДА'), так как ге8(/ + 1 + 1, /+ 1) = = гев((/Ч 1)/(/+ 1) + 1/(/+ 1)) = 1.

Вывод. Следовательно, пара (я, п) принадлежит ДАО для любого натурального п > 1 и бинарное отношение ДАО, заданное на множестве натуральных чисел И> , рефлексивно.

Задача 4.63. Базис индукции. Пара (2, 2) не принадлежит ДАО, так как геБ(2, 2) = 0.

Индукционный переход. Пара (/', 0 не принадлежит ДАО, так как ге5(/, 0 = 0.

Пара (/ + 1, / + 1) не принадлежит ДАО, так как ге8(/ + 1, / + 1) = 0.

Вывод. Следовательно, пара (п, п) не принадлежит ДАО для любого натурального п > 1 и бинарное отношение ДАО = {ге8(Д а) = 1}, заданное на множестве натуральных чисел N > 1, иррефлексивно.

Задача 4.64. Прямой логический вывод:

С + С

m+1

П

+

П

- п(

т{п - т) (т + 1)!(я - т - 1)! + 1)!(я - т - 1)!+ т(п - т)

т{т + 1)!(я - т){п - т - 1)!

. т(п - т - )(т + 1 + п- т) = т-

(п + 1)!

С

/77+1

/7+1

т{т + 1)!(я - т)(п - т - 1)! + 1)!(я -(я + 1)! (я + 1)!

(я? + 1)!(я + 1 — т — 1)! + 1)!(я - т)

Таким образом, левая часть формулы равна правой и утверждение верно. Ч.т.д.

Задача 4.65. Предположим, что это не так.

п

Левая часть формулы равна С/* =-:-.

/я!(я - /я)!

Правая часть формулы равна

(п - т)(п - п + т) (п-т)т

То есть обе части равны друг другу и мы получили противоречие. Таким образом, утверждение верно. Ч.т.д.

Задача 4.66. Предположим, что это не так.

Левая часть формулы равна

ст _ ск = я!___т- = я!

п т т {п-т) к (т-к) (п - т)- (т - к)

Правая часть формулы равна

к лущ—к ^п ' ^п-к

П

(п - к)

к(п-к) (т - к)- (п - к - т + к)

п

к? (т - к)? (п - т)

То есть обе части равны друг другу и мы получили противоречие. Таким образом, утверждение верно. Ч.т.д.

 
< Пред   СОДЕРЖАНИЕ     След >