1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633)
Текст из файла
Ершов Ю.Л.,Палютин Е.А.МАТЕМАТИЧЕСКАЯЛОГИКАРекомендовано УМС по математике и механике УМОпо классическому университетскому образованию РФв качестве учебного пособия для студентов высшихучебных заведений, обучающихся по направлениям испециальностям:«Математика»,«Прикладнаяматематика и информатика», «Механика»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) - оказал решающее влияние на формирование научных интересов и педагогических взглядовавторов. На разных этапах подготовки настоящей книги большую помощь и поддержку мы получали от М.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
