Читать онлайн «Математическая логика и теория алгоритмов»

Московский государственный горный университет  РЕДАКЦИОННЫЙ С О В Е Т Пр ед сед am ель Л. А. ПУЧКОВ ректор МГГУ, чл. -корр. РАН Зам. председателя Л. Х. ГИТИС директор Издательства МГГУ Члены редсовета И. В. ДЕМЕНТЬЕВ академик РАЕН А. П. ДМИТРИЕВ академик РАЕН Б. А. КАРТОЗИЯ академик РАЕН М. В. КУРЛЕНЯ академик РАН В. И. ОСИПОВ академик РАН Э. М. СОКОЛОВ академик МАН ВШ КН. ТРУБЕЦКОЙ академик РАН В. В. ХРОНИН профессор В. А. ЧАНТУРИЯ академик РАН Е. И. ШЕМЯКИН академик РАН Л. М. Гурова Е. В. Зайцева МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Допущено Учебно-методическим объединением вузов по университетскому политехническому образованию в ка­ честве учебного пособия для студентов высших учебных заведений, обучающихся по направлениям 552800, 654600 «Информатика и вычислительная техника», специаль­ ности 220200 «Автоматизированные системы обра­ ботки информации и управления» Высшее горное образование А МОСКВА ИЗДАТЕЛЬСТВО МОСКОВСКОГО ГОСУДАРСТВЕННОГО ГОРНОГО УНИВЕРСИТЕТА 2006 У Д К 519. 768. 681. 3 ББК 22. 12 Г 95 Книга соответствует «Гигиеническим требованиям к изданиям книжным для взрослых. СанПиН 1. 2. 1253 — 03», утвержденным Главным государственным санитарным врачом России 30 марта 2003 г. Экспертиза проведена Учебно-методическим объединением вузов по универ­ ситетскому и политехническому образованию (письмо № 16-07/191 от 15. 07. 2005 г. ) Рецензенты: • академик Международной академии наук информации, информационных процессов и технологий, д-р техн. наук А. А. Садердинов (ФГУП «Главный информационно-вычислительный центр металлургии»); • кафедра «Автоматизированные системы обработки информации и управ­ ления » Московской государственной академии приборостроения и информа­ тики (зав. кафедрой проф. , д-р техн. наук ОМ. Петров) Гурова Л. М. , Зайцева Е. В. Г 95 Математическая логика и теория алгоритмов: Учебное пособие. — М. : Издательство Московского государственного горного универ­ ситета, 2006. — 2 6 2 с : ил. I S B N 5-7418-0451 -9 (918-5-7418-0451 -3) Изложен материал основного курса «Математическая логика и теория алго­ ритмов», читаемого на факультете «Автоматизации и информатики (АИ)» МГГУ: основные понятия, относящиеся к семантике формализованных логико-математиче­ ских языков; математическая логика, исчисление высказываний и предикатов, эле­ менты теории множеств, основы теории моделей и алгоритмов. Показано практическое использование алгебры к задачам математической логики.