В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 45
Текст из файла (страница 45)
216 Построение выводов из гипотез. Решить задачи 11.7 — 11.9. 11.7. Докажите следующие свойства выводимости из гипотез, представляющие собой правила введения и удаления кван- торов: а) если Г «- Г(х), то Г « — ('Фх)(Г(х)) (правило ВКО); б) (тх)(Г(х)) «- Г(у) (правило УКО); в) Г(у) «-(Бх)(Г(х)) (правило ВКС). Решение. а) Приводим вывод: (1) Г(х); (2) б (любая доказуемая формула, не содержащая свободных вхождений х (ограничение на х понадобится на шаге (5))); (3) г(х) -+ (6-+ Г(х)) (аксиома (А1)); (4) 6-+ Г(х) (МР: (1), (3)); (5) 6-+('««х)(Г(х)) ('Ф-правило: (4)); (6) (~х)(Г(х)) (МР: (2), (5)).
11.8. Докажите, что в ФИП справедливы следующие выводи- мости, построив выводы формул из соответствующих гипотез: а) (~«~хКГ(х) -+ 6(х)) « — (Ъх)(Г(х)) -+ (««х)(б(х)); б) Г(у) -+ 6(у) «- (Лх)(Г(х)) -+ (Зх)(6(х)); в) ('«х)(Г(х) -+ 6(х)) «- (Лх)(Г(х)) -+ (Зх)(б(х)); г) (Ъ х)(б — «Г(х)) «- 6-+ (Ъх)(Г(х)); д) ('Фх)(Г(х) -+ 6) «- (Бх)(Г(х)) -+ б; е) (Лх)(Г(х)) -+ (Ъ'х)(6(х)) « — Г(у) -+ 6(у); ж) (Эх)(Г(х)) -+ (чх)(б(х)) «- (ЭхКГ(х) -+ 6(х)); з) (Эх)(Г(х)) -+ ('««х)(6(х)) «- ('чх)(Г(х) -+ 6(х)); и) (~««х)(Г(х) ++ 6(х)) « — (Зх)(Г(х)) ++ (Лх)(б(х)); к) (Ъх)(Г(х) ++ 6(х)) « — (чх)(Г(х)) ++ (Ъх)(6(х)).
Решение. к) Вывод имеет следующий вид: (1) (Чх)(Г(х) ++ 6(х)) (гипотеза); (2) Г(у)++ 6(у) (правило УКО: (1)); (3) .Цу) -+ 6(у) (правило л-уд: (2)); (4) 6(у) -+ Г(у) (правило л-уд: (2)); (5) (чх)(Г(х)) -+ Г(у) (аксиома (РА1)); (6) («««х)(Г(х)) -+ 6(у) (правило силлогизма: (5), (3)); (7) («««х)(Г(х)) -+ ('Фу)(6(у)) (««'-правило: (6)); (8) (Чх)(Г(х)) -+ Г««'х)(б(х)) (переименование: (7)); (9) (~~х)(6(х)) -+ 6(у) (аксиома (РА1)); (10) (чх)(6(х)) -+ Г(у) (правило силлогизма: (6), (4)); (11) (чхК6(х))-«(Чу)(Г(у)) (~-правило: (10)); (12) («~х)(6(х)) -+ (~х)(Г(х)) (переименование: (11)); (13) (('Фх)(Г(х)) -+ (чх)(6(х))) -+ 1(('««х)(6(х)) -+ ('Фх)(Г(х))) -+ -+ ((«~х)(Г(х)) ++ (~«~х)(6(х)))) (теорема ФИВ: А-+ (В-«(А л В))); (14) ((чх)(б(х)) -+ (чх)(Г(х))) -+ ((чх)(Г(х)) ++ (тх)(б(х))) (МР: (8), (13)); (15) («««х)(Г(х))++(«««х)(6(х)) (МР: (12), (14)).
217 11.9. Докажите следующие теоремы формализованного исчисления предикатов: а) -~(~~х)(Р(х)) ++ (Зх)(-~Р(х)); б) (Вх)(Р(х)) ++ -з(Лх)(-чР(х)). Р е ш е н и е. а) Последовательность шагов вывода следующая: (1) Г(х) ++ ~-зР(х) (теорема ФИВ); (2) (тх)(Р(х) ++ ~-~Р(х)) (правило ВКО (задача 11.7, а)); (3) (вх)(Р(х))++(~гх)(-з~Р(х)) (задача 11.8, к); (4) (~х)(Р(х)) -+ ('чх)(-гзГ(х)) (правило л-уд: (3)); (5) ('Ех)(~~Р(х)) -+ (чх)(Р(х)) (правило л-уд: (3)); (6) -ю('с~х)(-т.зР(х)) -+ -ч('ох)(Р(х)) (правило контрапозиции из ФИВ: (4)); (7) -ч(чх)(Р(х)) -+ ~(чх)(~~Р(х)) (правило контрапозиции из ФИВ: (5)); (8) -з(Ъх)(Р(х))++-ч(Чх)(-з-зГ(х)) (правило л-вв: (6), (7)); (9) (Ех)(~Р(х)) ++ ~(чх)(~~Г(х)) (задача 11.6, а); (10) -з(чх)(Р(х))++(Зх)(-чР(х)) (из (8), (9) по правилу ФИВ: Р++ 12, (2 ~+ Я ~- Р к-ь Я).
Теорема о дедукции и ее применение. Теорема о дедукции в ФИП формулируется так же, как и в ФИВ: если Рь ..., Р ь Р„~- 6, то Р„..., Р, >- Г„-+ б (в частности, если Р~ б, то ~= Р-+ 6). 11.10. Если Г, Г(х) >- 6, то Г, (Зх)(Р(х)) ~ — 6 при условии, что х не входит свободно ни в формулу 6, ни в одну формулу из Г (правило УКС вЂ” удаления квантора существования). Р е ш е н и е. Укажем соответствующий вывод: (1) Г, Г(х) >- 6 (условие); (2) Г ~ — Г(х) -+ 6 (теорема о дедукции: (1)); (3) Р(х) -+ б >- (Зх)(Р(х)) -+ б (Л-правило); (4) Г ~- (Бх)(Р(х)) -+ б (свойство выводимости: (2), (3)); (5) Г, (Зх)(Р(х)) ~- (Зх)(Р(х)) -+ 6 (свойство выводимости: (4)); (6) Г, (Зх)(Р(х)) >- (Зх)(Г(х)) (очевидно); (7) (Эх)(Р(х)), (Лх)(Р(х)) -+ 6 ~ — 6 (правило МР); (8) Г, (Зх)(Р(х)) ~- 6 (свойство выводимости: (5), (6), (7)).
11.11. Используя теорему о дедукции, докажите, что в ФИП справедливы следующие выводимости: а) б-+ (Чх)(Р(х)) >- (Ъх)(6-+ Р(х)); б) (Лх)(Р(х)) -+ 6 ~ — (чх)(Р(х) -+ 6); в) (Зх)(6-+ Р(х)) >- 6-+ (Зх)(Р(х)); г) (Лх)(Р(х) -+ 6) ~ — (Чх)(Г(х)) -+ 6; д) 6-+ (Зх)(Р(х)) ~- (Зх)(6-+ Г(х)); е) (чх)(Р(х)) -+ б ~- (Зх)(Г(х) -+ 6). Решение. а) Нетрудно видеть, что: б-+(чх)(Р(х)), 6~-Г(у). В самом деле, из формул б-+ (чх)(Р(х)), 6 по правилу МР сначала выводится (чх)(Р(х)).
Затем из последней формулы и аксиомы (РА1) по МР выводится формула Г(у). Тогда по теореме о дедукции б-+ ('чх)(Р(х)) ~ — б-+ Г(у). Из последней формулы по 218 правилу ВКО (задача 11.7, а) выводится формула (чуК6-«Р(у)), или (~х)(6-«Р(х)). Окончательно, 6-+ (~х)(Р(х)) « — («х)(6-«Р(х)). б) Докажем сначала, что (Зх)(Р(х)) -+ б, Р(у) « — б: () (1) (Зх)(Р(х)) -«6 (гипотеза); (2) Р(у) (гипотеза); (3) Р(у) -+ (Зх)(Р(х)) (аксиома (РА2)); (4) (Зх)(Р(х)) (МР: (2), (3)); (5) 6 (МР: (4), (1)). Из выводимости (*) по теореме о дедукции заключаем, что (Зх)(Р(х)) -+ 6 « — Р(у) -+ б. («э) Наконец, из выводимости (е~) по правилу ВКО (задача 14.7, а) заключаем, что (Зх)(Р(х)) — «б «- (чу) (Р(у) -+ 6) или (Зх)(Р(х)) -+ — «6 « — ('ч'х)(Р(х) -+ 6). 11.12.
Используя теорему о дедукции, докажите, что в ФИП справедливы следующие теоремы (отыщите среди них все тавтологии логики предикатов, приведенные в теоремах 21.11 и 21.12 Учебника): а) (чх)( б — «Р(х)) ++ (6-+ (~«'х)(Р(х))); б) (чх)(Р(х) -+ 6) ++ ((Зх)(Р(х)) -+ 6); в) (Зх)(6-+ Р(х)) ++ (б — «(Зх)(Р(х))); г) (Зх)(Р(х) -+ 6) ++ ((тх)(Р(х)) -+ 6); д) (чх)(Р(х) ч 6) ++ ((чх)(Р(х)) ~ 6); е) (Зх)(Р(х) л 6) ++ ((Зх)(Р(х)) л 6); ж) (Ъх)(Р(х) л 6(х)) ++ (('Фх)(Р(х)) л (Чх)(6(х))); з) (Зх)(Р(х) ч 6(х)) ++ ((Зх)(Р(х)) ч (Зх)(6(х))). Решение. з) Докажем сначала, что (Зх)(Р(х) и 6(х)) «- «- (Зх)(Р(х)) и (Зх)(б(х)): (1) (Р(у) «- (Зх)(Р(х)) (правило ВКС); (2) (Зх)(Р(х)) «- (Зх)(Р(х))ч (Зх)(6(х)) (правило ч-вв); (3) Р(у) «-(Зх)(Р(х)) ч (Зх)(6(х)) (получена из (1), (2)); (4) 6(у) «-(Зх)(б(х)) (правило ВКС); (5) (Зх)(б(х)) « — (Зх)(Р(х)) ч (Зх)(6(х)) (правило ~-вв); (6) 6(у) «- (Зх)(Р(х)) ч (Зх)(6(х)) (получаем из (4), (5)); (7) Р(у)ч 6(у) «- (Зх)(Р(х)) ч (Зх)(6(х)) (правило ч-уд: (3), (6)); (8) (Зх)(Р(х)ч 6(х)) «-(Зх)(Р(х))ч (Зх)(6(х)) (УКС: (7)).
Следовательно, по теореме о дедукции: «- (Зх)(Р(х) ч 6(х)) -+ ((Зх)(Р(х)м (Зх)(6(х))). (*) Теперь докажем, что (Зх)(Р(х)) ч (Зх)(6(х)) « — (Зх)(Р(х) ч (6(х)): (1) Р(у) «- Р(у)ч 6(у) (правило ч-вв); (2) Р(у)ч 6(у) « — (Зх)(Р(х)ч 6(х)) (правило ВКС); (3) Р(у) «- (Зх)(Р(х)ч 6(х)) (получена из (1), (2)); (4) 6(у) «- Р(у)ч 6(у) (правило ч-вв); 219 (5) 6(у) >-(Зх)(Р(х) ~ 6(х)) (получена из (4), (2)); (6) (Зх)(Г(х)) «-(Лх)(Г(х) ч 6(х)) (правило УКС: (3)); (7) (Эх)(6(х)) ) — (Зх)(Г(х) ъ 6(х)) (правило УКС: (5)); (8) (Зх)(Г(х) ~ (Зх)(6(х)) > — (Зх)(Г(х) ~ 6(х)) (правило ~-уд: (б), (7)).
Следовательно, по теореме о дедукции: ~- ((Лх)(Р(х)) ~ (Зх)(6(х))) -+ (Зх)(Р(х) ~~ 6(х)). (ве) Из теорем (в) и (*э) по правилу л-вв получаем требуемую теорему. Глава Ч ЭЛЕМЕНТЫ ТКОРИИ АЛГОРИТМОВ В этой главе собраны задачи о трех формализациях интуитивного понятия алгоритма — о машинах Тьюринга (5 12), о рекурсивных функциях 5 13) и о нормальных алгоритмах Маркова (9 14). $12.
Машины Тьюринга Машина Тьюринга полностью определяется: а) внешним алфавитом А = (а, а„..., а„», где а, — символ пустой ячейки, а, = 1; б) алфавитом внутренних состояний 0 = (д, д„..., д„», где д— состояние остановки: попав в него, машина прекращает работу; д, — начааьное состояние: в этом состоянии машина начинает работать; в) программой (или функциональной схемой), т.е. совокупностью выражений Т(1, ))(1=1, ..., т; 1 = О, 1, ..., п), каждое из которых имеет один из следующих видов: д,а -+ дьаь д,.а -+ д„а,П, д,а -+ д а,Л, где О < lс < т, О < 1< и.
Выражейия Т(г, у) называют командами. Наглядно устройство и работу машины Тьюринга можно представить себе следующим образом. Машина имеет бесконечную в обе стороны ленту, разбитую на ячейки. В каждой ячейке записана ровно одна буква из внешнего алфавита А (запись буквы а означает, что ячейка пуста). В каждый момент времени (такт работы) машина находится в одном из состояний, обозначаемых буквами алфавита внутренних состояний, и «обозревает» точно одну ячейку ленты («читает» информацию, записанную в ячейке). По команде да,. -+ д„а,Х(где Х= П или Х= Л, или Хотсутствует), означающей, что машина находится в состоянии д,, и обозревает ячейку, в которой записана буква а, машина переходит в состояние д, в обозреваемой ячейке стирает букву а,.
и заносит туда букву аг Затем машина переходит к обозрению ячейки, следующей справа или слева от предыдущей в зависимости от того Х= П или Х= Л соответственно, или же продолжает обозревать предыдущую ячейку, если место Хв команде не заполнено. После выполнения указанной команды машина на следующем такте переходит к выполнению команды д а, -+ д,а,Хи т.д. Сювом в алфавите А йли в алфавите Д, или в алфавите А н Д называется любая последовательность букв соответствующего ал- 221 фавита. Под lс-й конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу к-го такта (или слово в алфавите А, записанное на ленте к началу к-го такта), и с указанием того, какая ячейка обозревается в этот такт и в каком состоянии находится машина.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
