Игошин Математическая логика и теория алгоритмов (1019110)
Текст из файла
Файл взят с сайта и и и.ко~фея.ги, на котором есть аде много интересной литературы ВЫСШЕЕ ПРОФЕССИОНАПЬНОЕ ОБРАЗОВАНИЕ в.и. игошин МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Допущено Иинистерством образования Российской Федерации в качеопве учебного пособия для студенпюв высших учебных заведении, обучающихся по специальности 050201 «математика» 2-е издание, стереотипное Москва Издательский центр Академия» 200о УДК 510.6(075.8) ББК 22.12я73 И269 Репензенты: декан факультета «Приклалная математика» Московского государственного открытого университета, л-р физ.-мат. наук, проф. В.Д. Кулиев; л-р физ.-мат. наук, проф. Д.А.
бредихин Игошин В.И. И269 Математическая логика и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В. И. Игошин. — 2-е изд., стер. — М.: Издательский центр «Академия», 2008. — 448 с. 18ВХ 978-5-7695-4593-1 Предлагаемое учебное пособие составляет основу комплекта по курсу математической логики и теории алгоритмов, в который также входит сборник задач (Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов). Подробно изложены основы теории, показаны направления проникновения логики в основания алгебры, анализа, геометрии, привлечен материал школьного курса математики лля его логического анализа, охарактеризованы взаимосвязи математической логики с компьютерами, информатикой, системами искусственного интеллекта.
Зля стулентов университетов, технических и педагогических вузов, обучаюшихся по специальностям «Математика», Прикладная математикам УДК 510.6(075.8) ББК 22.12я73 Оригинал-макет данного издания является собственностью Издательского иентра «Академия», и его воспроизведение любым способом без согласия правообладателя запрещается © Игошин В.И., 2004 4) Издательский пентр «Академия*, 2004 18ВХ 978-5-7095-4593-1 Предисловие Логика образует такой пласт общечеловеческой культуры, без освоения которого в настоящее время не может состояться ни одна мыслящая личность.
Основы логической культуры закладываются в школе и в первую очередь на уроках математики, ибо, как точно подметил еще Л.Н.Толстой, математика имеет задачей не обучение исчислению, но обучение приемам человеческой мысли при исчислении»'. Математическая логика — вершина развития логики, достигнутая ею в ХХ в. Органично соединив в себе традиционную логику, восходящую к Аристотелю„и методы современной математики, она получила столь глубокие и поразительные результаты, не принимать в расчет которые стало просто невозможно не только тем, кто изучает, преподает и творит математику, но и всем тем, для кого методы рассуждений, обоснований и доказательств являются главными методами деятельности. Результаты, полученные с помощью математической логики, легли в основу проектирования и создания электронно-вычислительных машин (компьютеров) и программного обеспечения к ним, нашли широчайшее применение в областях информатики и систем искусственного интеллекта.
Настоящая книга предназначена для тех, кто изучает математическую логику в высших учебных заведениях. Автор знакомит будущих специалистов с основными понятиями и методами математической логики, показывает взаимосвязи математической логики с математической наукой, со школьным курсом математики, с современными ЭВМ. В гл.! дано подробное изложение алгебры (логики) высказываний, так как важно, чтобы именно на начальном этапе знакомства с предметом у студента сформировалась требуемая система понятий, составляющих фундамент математической логики. В гл. 11 рассматриваются, возникшие из алгебры логики булевы функции, которые оказались действенным математическим инструментом для конструирования функциональных и релейно-контактных (переключательных) схем — элементов современных ЭВМ. В гл. 111 пРоисходит знакомство с иным подходом к алгебре высказыва"ий: она строится как аксиоматическая теория на базе трех схем „, р„„„„„„.О„„„,,~„,.
М ...р,к Т %Н. П .— М., 1989.С.2 ц излагается логика предикатов, — привить студентам навыки использования квантора общности и квантора существования, правильного их понимания и умения оперировать выражениями (формулами) с кванторами. В вопросах применения логики предикатов значительное внимание уделяется записям на ее языке различных предложений, строению математических теорем и методам их доказательств. В гл. Ч рассмотрен аксиоматический метод в математике, изложены его логические основы.
На неформальном (содержательном) уровне показано, как математическая логика вторгается в различные разделы математической науки, образуя их фундаментальные аксиоматические основы. В гл. Ч1 изложение математической логики поднимается на новый качественный уровень: математические теории начинают изучаться с формальной точки зрения. Сначала изучаются свойства формализованного исчисления предикатов: доказываются теоремы Геделя о сушествовании модели, о полноте и адекватности этого исчисления, теорема компактности, теорема ЛевенгеймаСколема.
Затем дается обзор формализаций теории множеств, числовых систем, геометрии, математического анализа. Гл. Ч)1 посвящена основам теории алгоритмов. Рассматриваются три формализации этого понятия (машины Тьюринга, рекурсивные функции, нормальные алгоритмы Маркова), устанавливается их равносильность. Рассматриваются неразрешимые алгоритмические проблемы. Доказывается теорема Геделя о неполноте формальной арифметики.
Наконец в гл. ЧП1 дан обзор применений математической логики в сферах программного обеспечения компьютеров, информатики и искусственного интеллекта. Данное пособие задумано в комплекте со сборником задач: Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. — Мл Изд. центр «Академия», 2004. По ходу изложения теоретического материала автор прибегает к многочисленным ссылкам на конкретные примеры решения тех или иных задач из данного сборника, используя краткое его название— «Задачник». Например, усвоение теоретического материала гл.
1 закрепляется решением задач з 1 — 3 Задачника, гл. П является теоретической основой для решения задач 5 4 — 7 Задачника. После изучения гл. П! рекомендуются задачи 5 8 Задачника. В процессе изучения гл. 1Ч решаются задачи 8 9 — ! 1, а для закрепления материала гл. ЧП и гл. 'ЧП1 предназначены задачи 5 12 — 14 Задачника. Знаки «» и ~ почти всегда используются для сокрашенной записи оборотов «тогда и только тогда» и «еели ..., то . » соответственно. Исключения составляют 5 18 и 19 книги, где первый знак («») используется для обозначения равносильности предикатов, а второй (=») — для следования предикатов, а также 5 32 и 34, где знак =» обозначает переход от одного слова к другому в результате применения соответствующего алгоритма.
Знак ьз обо- значает графическое совпадение (одинаковость) формул (логики внысказываний или логики предикатов). для множеств комплекс„ых, действительных, рациональных, целых и натуральных чисел используются стандартные обозначения: С, В, Ц, Уи Фсоответственно. Конец доказательства отмечается значком П. Составляющими элементами каждого параграфа являются теоремы, леммы, определения, следствия, замечания, примеры, которым присвоена двойная нумерация для их идентификации: на первом месте указан номер параграфа в книге, на втором— порядковый номер данного элемента в этом параграфе. В конце книги приведен обширный список рекомендуемой литературы по разделам математики, имеющим отношение к разным системам логического исчисления: числовым и алгебраическим, к смежным вопросам алгебры, к теории алгоритмов и др.
Выделена литература по математической логике и информатике и искусственному интеллекту. Сборники задач и книги, рекомендуемые школьникам, также составляют отдельные подразделы списка литературы. В работе над данной книгой, как и в работе над сборником задач, автором учтен опыт его прежних публикаций по теме, в частности сборника задач (1986) и учебника (1991) по математической логике и теории алгоритмов. Автор вполне отдает себе отчет о трудности создания учебного пособия, полностью отвечающего требованиям сегодняшнего дня, однако выражает надежду, что его новые работы, рассчитанные на тех, кто начинает изучать основы математической логики и теории алгоритмов, будуг востребованы и оценены должным образом в учебных заведениях различных профилей и уровней.
В. Игошин Введение МАТЕМАТИЧЕСКАЯ ЛОГИКА В СИСТЕМЕ СОВРЕМЕННОГО ОБРАЗОВАНИЯ Предварим изучение математической логики кратким введением, в котором попытаемся осознать роль и место логики в мышлении, в науке, в математике и в обучении. Логика и интуиция. Мыслительная деятельность человека представляет собой сложный и многогранный процесс, происходящий как на сознательном, так и на бессознательном (подсознательном) уровнях. Это высшая ступень человеческого познания, способность к адекватному отражению предметов и явлений действительности, т.е. к нахождению истины. Логика и интуиция — два противоположных и неразрывно связанных между собой свойства человеческого мышления. Логическое (дедуктивное) мышление отличается тем, что оно от истинных посылок всегда приводит к истинному заключению, не опираясь при этом на опыт, интуицию и другие внешние факторы.
Характеристики
Тип файла DJVU
Этот формат был создан для хранения отсканированных страниц книг в большом количестве. DJVU отлично справился с поставленной задачей, но увеличение места на всех устройствах позволили использовать вместо этого формата всё тот же PDF, хоть PDF занимает заметно больше места.
Даже здесь на студизбе мы конвертируем все файлы DJVU в PDF, чтобы Вам не пришлось думать о том, какой программой открыть ту или иную книгу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
