1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (Ю.Л. Ершов, Е.А. Палютин - Математическая логика)

Ершов Ю.Л.,Палютин Е.А.МАТЕМАТИЧЕСКАЯЛОГИКАРекомендовано УМС по математике и механике УМОпо классическому университетскому образованию РФв качестве учебного пособия для студентов высшихучебных заведений, обучающихся по направлениям испециальностям:«Математика»,«Прикладнаяматематика и информатика», «Механика»1МОСКВАФизмдтлит®2011УДКББК510.6(075.8)22.12Е80Ерш о виспр.ВЮ.

Л.,Палю тинМ.: ФИЗМАТЛИТ,-книгеизложеныЕ. А. Математическая логика.2011. - 356основныес.-6-е изд.,- ISBN 978-5-9221-1301-4.классическиеисчисленияматематическойлогики: исчисление высказываний и исчисление предикатов; имеется краткоеизложение основных понятий теорииразделов книгимножеств и теории алгоритмов.теория моделей и теория доказательств-Ряд-изложены болеевузов.Может служитьподробно, чем это предусмотрено программой.Длястудентовматематических специальностейпособием для специальных курсов.Рекомендовано УМС по математике и механике УМО по классическомууниверситетскому образованию РФ в качестве учебного пособия для студентоввысших учебных заведений, обучающихся по направлениям и специальностям:<,Математика•, <,Прикладная математика и информатика,>, <<Механика•.Учебное изданиеЕРШОВ Юрий ЛеонидовичПАЛЮТИН Евгений АндреевичМАТЕМАТИЧЕСКАЯ ЛОГИКАРедактор И.Л.

ЛегостаеваОригинал-макет:И.Г. АндрееваОформление переплета: ДБ. БелухаПодписано в печать 26.01.11. Формат 60х90/16. Бумага офсетная. Печать офсетная.Усл. печ. л. 22,25. Уч.-изд. л. 24,75. Тираж 500 экз. Заказ № К-5586.Издательская фирма ,,Физико-математическая литература•МАИК ,,Наука/Интерпериодика•117997, Москва, ул. Профсоюзная, 90E-mail: fizmat@maik.ru, fmlsale@maik.ru;http://www.fml.ruОтпечатано в ГУП,,ИПК ,,Чувашия»,428019г. Чебоксары, пр-т И.Яковлева,ISBN 978-5-9221-1301-413@ФИЗМАТЛИТ,©Ю. Л.

Ершов, Е. А. Палютин,20112011ОГЛАВЛЕНИЕПредисловие к шестому изданию5Предисловие к первому изданию6ВведениеГл а в а1................... .8Исчисление высказываний. . . . . . ...... .§ 1.1. Множества и слова . . . . . . . . . . . . . . . . . . . .§ 1.2.

Язык исчисления высказываний . . . . . . . . . . . . .§ 1.3. Система аксиом и правил вывода . . . . . . . . . . . .§ 1.4. Эквивалентность формул . . . . . . . . . . . . . . . . . . . .§ 1.5. Нормальные формы . . . . . . . . . . . . . . . . .

. . .§ 1.6. Семантика исчисления высказываний . . . . . . . . . . . . . . . . . .§ 1. 7. Характеризация доказуемых формул . . . . . . . . . . . . . . . . . . . .§ 1.8. Исчисление высказываний гильбертовского типа ... .§ 1. 9. Консервативные расширения исчислений . . . . .

. . . .Гл а в а2.Теория множеств............ .§ 2.1. Предикаты и отображения . . . . . . . . . . . . . . . .§ 2.2. Частично упорядоченные множества . . . . . . . . . .§ 2.3. Фильтры булевой алгебры . . .. .... .1313172229323843465060606575§ 2.4. Мощность множества . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .§ 2.5. Ординалы и кардиналы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .§ 2.6. Аксиоматическая теория множеств ZF и аксиома выбора.8081Гл а в а93933.Истинность на алгебраических системах.§ 3.1. Алгебраические системы . . . . . . . . . . . . . . . .§ 3.2. Формулы сигнатуры I;.......... .§ 3.3. Теорема компактности ..Гл а в а4.Исчисление предикатов. . . .

. . ..... .§ 4.1. Аксиомы и правила вывода . . . . . . . . . . . . . . . . . .§ 4.2. Эквивалентность формул . . . . . . . . . . . . . . . . . . . .§ 4.3. Нормальные формы . . . . . . . . . . . . . . . . . . . . . . .8799107114114122126§ 4.4. Теорема о существовании модели. . .

. . . . . . . . . . . . . . . . . . . . 128§4.5. Исчисление предикатов гильбертовского типа. .. . . . . . . . 135§ 4.6. Чистое исчисление предикатов. . . . . . . . . . . . . . . . . . . . . . . . . 139Оглавление4Гл а в а5. Теория моделей . . . . . . . .

. . . . . . . . . . . . .§ 5.1. Элементарная эквивалентность.§ 5.2. Аксиоматизируемые классы .. .§ 5.3. Скулемовские функции ..... .§ 5.4. Механизм совместности . . . . . . . .§ 5.5. Счетная однородность и универсальность. . . . . . . . .§ 5.6. Категоричность . . . . . . . . . .§ 5. 7. RQ-формулы и Е-формулы . .

. . . . . . . . . . . . . . . .§ 5.8. Формульная определимость . . . . . . . . . . . . . . . . . .§ 5.9. Позитивные формулы и монотонные операторы. . . . .Гл а в а§6.1.§ 6.2.. . .. . . . . . . .. . .. . .Теория доказательств.Генценовская система. . . . .. . . . . .. . .G.

. . . . . . . . .Обратимость правил.. . . . . . . . . . . . .6..215215220§ 6.3. Сравнение исчислений ИПЕ и G§ 6.4. Теорема Эрбрана . . . . . . . . . .§ 6.5. Исчисления резольвент . . . . . .Гл а в а7.Вычислимостъ144144152161163175182191202209225232245...... .251251Е-предикаты и Е-функции на П ..252Е-определимость истинности Е-формул на П . . . .

. . . . . . . . . . . 265Универсальные Е-предикаты, универсальные частичные Е-функции 277Теорема Чёрча и теорема Гёделя о неполноте . . . . . . .283Машины Тьюринга. . . . . . . .294Рекурсивные функции . . . . . . . . . . . . . . . . . . . . . . . .297§ 7.1. Понятие алгоритма. .

. . . . . . .§ 7.2.§ 7.3.§ 7.4.§ 7.5.§ 7.6.§ 7. 7.Гл а в а8.Разрешимые и неразрешимые теории.. . .. . . .300. . . . . . . . . . . . . 300Разрешимость теории одноместных предикатов.§ 8.1.§ 8.2.Элиминация кванторов и разрешимость теории алгебраически за-§ 8.3.Элиминация кванторов и разрешимость теории вещественно за-мкнутых полей. . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303мкнутых полей§ 8.4.§ 8.5.§ 8.6.. . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . .Теории декартовых произведений . . . . . . . . . . . .Неразрешимые теории . . . .

. .. . . . . . . . . .Разрешимые теории абелевых групп..:.................308311328332Предметный указатель.343Указатель обозначений.352Предисловие к шестому изданиюЭто издание является переработкой и дополнением 2-го издания(издания3-5являются стереотипными). Изменения коснулись всехглав книги. Наибольшей корректировке подверглась главании которой сформирована глава8.7,на основа­В частности, за основу изложениятеории вычислимости выбрано понятие Е-определимости.

Этот подходпоможет естественному освоению теории вычислимости на допустимыхмножествах.Изменения относятся как к дополнениям материала, так и к болееподробному изложению мест в доказательствах, которые ранее былиболее схематичны.Благодарим С. В. Судоплатова за полезные замечания ипомощьв подготовке рукописи к изданию, а также М. А. Русалеева за компью­терный набор текста.Настоящее шестое издание книги является первым в издательстве<<ФИЗМАТЛИТ>>.Май2010 r.Ю.

Л.ЕршовЕ. А. ПалютинПредисловие к первому изданиюНастоящая книга представляет собой систематическое изложениеряда разделов современной математической логики и теории алгорит­мов. Написана она с целью использования ее в преподавании какв качестве учебника по математической логике для университетов, таки в качестве учебного пособия при чтении спецкурсов.Разделы, соответствующие обязательной программе(без мелкого шрифта),в гл.4и§ 35в гл.§ 10-117),в гл.2, § 15-16в гл.(§ 1-9в гл.13, § 18-20, 22-23написаны более тщательно и подробно, чемразделы, относящиеся к более специальным вопросам.Изложение исчисления высказываний и исчисления предикатов неявляется традиционными начинается сизучения секвенциальных ва­риантов исчислений натурального вывода (хотя традиционные исчис­ления также появляются здесь под названием гильбертовских).

Осно­ванием к этому являются:1)2)возможность хорошего объяснения смысла всех правил вывода;возможность более быстрого приобретения навыка формальныхдоказательств;3) практическая возможность проделать все необходимые в курсеформальные доказательства в таких исчислениях.Многолетний опыт чтения старшим из авторов курса математиче­ской логики на математическом факультете Новосибирского государ­ственного университета, на основе которого написаны главы1-4,по­казывает, что указанные выше возможности вполне реализуются. Этооправдывает использование такого способа изложения наряду с тради­ционными.Более подробные сведения о содержании книги можно получить изее оглавления.Ввиду учебного характера книги, несмотря на названия«Теориямножеств•, «Теория моделей•, «Теория доказательств• и «Алгоритмыи рекурсивные функцию>, соответствующие главы, конечно, содержатлишь малую часть содержания этих больших разделов современнойматематической логики.Как ипринято вучебниках, большинстворезультатов приведено в данной книге без указания авторов.В тексте имеется небольшое число упражнений почти после каждо­го параграфа книги.

Однако этих упражнений явно недостаточно дляучебных целей. Мы рекомендуем использовать в качестве задачникадля данного курса следующий: Лавров И.А., Максимова Л. Л. ЗадачиПредисловие к первому изданию7по теории множеств, математической логике и теории алгоритмов.1)М.: Наука, 1984.Сделаем несколько замечаний технического порядка. Нумерациятеорем-сквознаяпоглавам,нумерацияи лемм 12.2» (<<теоре­2, ... ) из § 12,>. Припредложенийсвоя в каждом параграфе. Выражение «предложениема12.2,>, ... )означает <<предложение2(теоремассылке на предложения и леммы внутри одного параграфа и часто приссылке на теоремы внутри одной главы параграф не указывается.

Сим-«===}» является сокращением для выражения <<ИЗ ... следует ... ,>,<< {=} >> является сокращением для выражения << ... равносиль... >>. Символ «D» указывает на окончание доказательства.волсимволноСоздание этой книги не было бы возможно без коллектива кафедрыалгебры и математической логики Новосибирского государственногоуниверситета. Основатель этой кафедрытематик академик А. И. Мальцев- выдающийся советский ма­(1909-1967) - оказал решающее вли­яние на формирование научных интересов и педагогических взглядовавторов. На разных этапах подготовки настоящей книги большую по­мощь и поддержку мы получали от М.